Rebased PNaCl localmods in LLVM to 223109

include/llvm/Bitcode/NaCl/NaClBitcodeDist.h

+//===- NaClBitcodeDist.h ---------------------------------------*- C++ -*-===//
+//     Maps distributions of values in PNaCl bitcode files.
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Creates a (nestable) distribution map of values in PNaCl bitcode.
+// The domain of these maps is the set of record values being
+// tracked. The range is the information associated with each block
+// and/or record value, including the number of instances of that value. The
+// distribution map is nested if the range element contains another
+// distribution map.
+//
+// The goal of distribution maps is to build a (histogram)
+// distribution of values in bitcode records and blocks, of a PNaCl
+// bitcode file. From appropriately built distribution maps, one can
+// infer possible new abbreviations that can be used in the PNaCl
+// bitcode file.  Hence, one of the primary goals of distribution maps
+// is to support tools pnacl-bcanalyzer and pnacl-bccompress.
+//
+// Distribution maps are constructed either from NaClBitcodeBlock's or
+// NaClBitcodeRecord's (in NaClBitcodeParser.h), but not both. It is
+// assumed that only blocks, or records (but not both) are added to a
+// distribution map. To add data to the distribution map, one calls
+// AddRecord and/or AddBlock. If the distribution map contains record
+// values, you must call AddRecord for each record to be put into the
+// distribution map. If the distribution map contains block values (i.e.
+// block ID's), you must call AddBlock for each block to be put into
+// the distribution map.
+//
+// While it may counterintuitive, one can call both AddRecord and
+// AddBlock, for each corresponding record and block processed. The
+// reason for this is that an internal flag StorageKind is kept within
+// distribution maps.  If the flag value doesn't correspond to the
+// type of called add method, no update is done. This behaviour is
+// done so that nested distribution maps can be updated via blind
+// calls in NaClBitcodeAnalyzer.cpp.
+//
+// Via inheritance, and overriding the (virtual) AddRecord
+// method for a distribution map, we can redirect the add to look up
+// the distribution element associated with the block of the record,
+// and then update the corresponding record distribution map. In general,
+// it only makes sense (for nested distribution maps) to be able to
+// redirect record additions. Redirecting blocks within a record (since
+// a record is only associated with one block) does not make sense. Hence,
+// we have not made AddBlock virtual.
+//
+// When updating a block distribution map, the domain value is the
+// BlockID of the corresponding block being added.
+//
+// On the other hand, values associated with record distribution maps
+// are many possible values (the code, the abbreviation, the values
+// etc). To make the API uniform, record distribution maps are updated
+// using NaClBitcodeRecords (in NaClBitcodeParser.h). The values from
+// the record are defined by the extract method GetValueList, and
+// added via method AddRecord.
+//
+// Distribution maps are implemented using two classes:
+//
+//  NaClBitcodeDist
+//     A generic distribution map.
+//
+//  NaClBitcodeDistElement
+//     The implementation of elements in the range of the distribution
+//     map.
+//
+// The code has been written to put the (virtual) logic of
+// distribution maps into derived classes of NaClBitcodeDistElement
+// whenever possible. This is intentional, in that it keeps all
+// knowledge of how to handle/print elements in one class. However,
+// because some distributions have external data that is needed by all
+// elements, the virtual methods of class NaClBitcodeDist can be
+// overridden, and not delegate to NaClBitcodeDistElement.
+//
+// To do this, an NaClBitcodeDist requires a "sentinel" (derived)
+// instance of NaClBitcodeDistElement. This sentinel is used to define
+// behaviour needed by distribution maps.
+//
+// By having control passed to the (derived) instances of
+// NaClBitcodeDistElement, it also makes handling nested distributions
+// relatively easy. One just extends the methods AddRecord and/or
+// AddBlock to also update the corresponding nested distribution.
+//
+// The exception to this rule is printing, since header information is
+// dependent on properties of any possible nested distribution maps
+// (for example, we copy column headers after each nested distribution
+// map so that it is easier to read the output). To fix this, we let
+// virtual method NaClBitcodeDistElement::GetNestedDistributions
+// return the array of nested distribution pointers for the nested
+// distributions of that map. The order in the array is the order the
+// nested distributions will be printed. Typically, this is
+// implemented as a field of the distribution element, and is
+// initialized to contain the pointers of all nested distributions in
+// the element. This field can then be returned from method
+// GetNestedDistributions.
+//
+// Distribution maps are sortable (via method GetDistribution). The
+// purpose of sorting is to find interesting elements. This is done by
+// sorting the values in the domain of the distribution map, based on
+// the GetImportance method of the range element.
+//
+// Method GetImportance defines how (potentially) interesting the
+// value is in the distribution. "Interesting" is based on the notion
+// of how likely will the value show a case where adding an
+// abbreviation will shrink the size of the corresponding bitcode
+// file. For most distributions, the number of instances associated
+// with the value is the best measure.
+//
+// However, for cases where multiple domain entries are created for
+// the same NaClBitcodeRecord (i.e. method GetValueList defines more
+// than one value), things are not so simple.
+
+// For example, for some distributions (such as value index distributions)
+// the numbers of instances isn't sufficient. In such cases, you may
+// have to look at nested distributions to find important cases.
+//
+// In the case of value index distributions, when the size of the
+// records is the same, all value indices have the same number of
+// instances.  In this case, "interesting" may be measured in terms of
+// the (nested) distribution of the values that can appear at that
+// index, and how often each value appears.
+//
+// The larger the importance, the more interesting the value is
+// considered, and sorting is based on moving interesting values to
+// the front of the sorted list.
+//
+// When printing distribution maps, the values are sorted based on
+// the importance. By default, importance is based on the number of
+// times the value appears in records, putting the most used values
+// at the top of the printed list.
+//
+// Since sorting is expensive, the sorted distribution is built once
+// and cached.  This cache is flushed whenever the distribution map is
+// updated, so that a new sorted distribuition will be generated.
+//
+// Printing of distribution maps are stylized, so that virtuals can
+// easily fill in the necessary data.
+//
+// For concrete instances of NaClBitcodeDistElement, the following
+// virtual method must be defined:
+//
+//    CreateElement
+//       Creates a new instance of the distribution element, to
+//       be put into the corresponding distribution map when a new
+//       value is added to the distribution map.
+//
+// In addition, if the distribution element is based on record values,
+// the virtual method GetValueList must be defined, to extract values
+// out of the bitcode record.
+
+#ifndef LLVM_BITCODE_NACL_NACLBITCODEDIST_H
+#define LLVM_BITCODE_NACL_NACLBITCODEDIST_H
+
+#include "llvm/Bitcode/NaCl/NaClBitcodeParser.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <map>
+#include <vector>
+
+namespace llvm {
+
+/// The domain type of PNaCl bitcode record distribution maps.
+typedef uint64_t NaClBitcodeDistValue;
+
+/// Base class of the range type of PNaCl bitcode record distribution
+/// maps.
+class NaClBitcodeDistElement;
+
+/// Type defining the list of values extracted from the corresponding
+/// bitcode record. Typically, the list size is one. However, there
+/// are cases where a record defines more than one value (i.e. value
+/// indices). Hence, this type defines the more generic API for
+/// values.
+typedef std::vector<NaClBitcodeDistValue> ValueListType;
+
+typedef ValueListType::const_iterator ValueListIterator;
+
+/// Defines a PNaCl bitcode record distribution map. The distribution
+/// map is a map from a (record) value, to the corresponding data
+/// associated with that value. Assumes distributions elements are
+/// instances of NaClBitcodeDistElement.
+class NaClBitcodeDist {
+  NaClBitcodeDist(const NaClBitcodeDist&) LLVM_DELETED_FUNCTION;
+  void operator=(const NaClBitcodeDist&) LLVM_DELETED_FUNCTION;
+  friend class NaClBitcodeDistElement;
+
+public:
+  /// Define kinds for isa, dyn_cast, etc. support (see
+  /// llvm/Support/Casting.h). Only defined for concrete classes.
+  enum NaClBitcodeDistKind {
+    RD_Dist,                 // class NaClBitcodeDist.
+      RD_BlockDist,          // class NaClBitcodeBlockDist.
+      RD_BlockDistLast,
+      RD_CodeDist,           // class NaClBitcodeCodeDist.
+      RD_CodeDistLast,
+      RD_AbbrevDist,         // class NaClBitcodeAbbrevDist.
+      RD_AbbrevDistLast,
+      RD_SubblockDist,       // class NaClBlockSubblockDist.
+      RD_SubblockDistLast,
+      RD_ValueDist,          // class NaClBitcodeValueDist.
+      RD_ValueDistLast,
+    RD_DistLast
+  };
+
+  NaClBitcodeDistKind getKind() const { return Kind; }
+
+private:
+  const NaClBitcodeDistKind Kind;
+
+  static bool classof(const NaClBitcodeDist *Dist) {
+    return Dist->getKind() >= RD_Dist && Dist->getKind() < RD_DistLast;
+  }
+
+public:
+  /// Type defining the mapping used to define the distribution.
+  typedef std::map<NaClBitcodeDistValue, NaClBitcodeDistElement*> MappedElement;
+
+  typedef MappedElement::const_iterator const_iterator;
+
+  /// Type defining a pair of values used to sort the
+  /// distribution. The first element is defined by method
+  /// GetImportance, and the second is the distribution value
+  /// associated with that importance.
+  typedef std::pair<double, NaClBitcodeDistValue> DistPair;
+
+  /// Type defining the sorted list of (domain) values in the
+  /// corresponding distribution map.
+  typedef std::vector<DistPair> Distribution;
+
+  /// Defines whether blocks or records are stored in the distribution map.
+  /// Used to decide if AddRecord/AddBlock methods should fire.
+  enum StorageSelector {
+    BlockStorage,
+    RecordStorage
+  };
+
+  NaClBitcodeDist(StorageSelector StorageKind,
+                  const NaClBitcodeDistElement *Sentinel,
+                  NaClBitcodeDistKind Kind=RD_Dist)
+      : Kind(Kind), StorageKind(StorageKind), Sentinel(Sentinel),
+        TableMap(), CachedDistribution(0), Total(0) {
+  }
+
+  virtual ~NaClBitcodeDist();
+
+  /// Number of elements in the distribution map.
+  size_t size() const {
+    return TableMap.size();
+  }
+
+  /// Iterator at beginning of distribution map.
+  const_iterator begin() const {
+    return TableMap.begin();
+  }
+
+  /// Iterator at end of distribution map.
+  const_iterator end() const {
+    return TableMap.end();
+  }
+
+  /// Returns true if the distribution map is empty.
+  bool empty() const {
+    return TableMap.empty();
+  }
+
+  /// Returns the element associated with the given distribution
+  /// value.  Creates the element if needed.
+  inline NaClBitcodeDistElement *GetElement(NaClBitcodeDistValue Value);
+
+  /// Returns the element associated with the given distribution
+  /// value.
+  NaClBitcodeDistElement *at(NaClBitcodeDistValue Value) const {
+    return TableMap.at(Value);
+  }
+
+  // Creates a new instance of this element for the given value. Used
+  // by class NaClBitcodeDist to create instances. Default method
+  // simply dispatches to the CreateElement method of the sentinel.
+  virtual NaClBitcodeDistElement *CreateElement(
+      NaClBitcodeDistValue Value) const;
+
+  /// Interrogates the block record, and returns the corresponding
+  /// values that are being tracked by the distribution map.  Default
+  /// method simply dispatches to the GetValueList of the sentinel.
+  virtual void GetValueList(const NaClBitcodeRecord &Record,
+                            ValueListType &ValueList) const;
+
+  /// Returns the total number of instances held in the distribution
+  /// map.
+  unsigned GetTotal() const {
+    return Total;
+  }
+
+  /// Adds the value(s) in the given bitcode record to the
+  /// distribution map.  The value(s) based on method GetValueList.
+  /// Note: Default requires that GetStorageKind() == RecordStorage.
+  /// Override if you want special handling for nested distributions
+  /// in a block distribution map.
+  virtual void AddRecord(const NaClBitcodeRecord &Record);
+
+  /// Adds the BlockID of the given bitcode block to the distribution
+  /// map, if applicable (based on the value of method UseBlockID).
+  /// Note: Requires that GetStorageKind() == BlockStorage.
+  virtual void AddBlock(const NaClBitcodeBlock &Block);
+
+  /// Builds the distribution associated with the distribution map.
+  /// Warning: The distribution is cached, and hence, only valid while
+  /// it's contents is not changed.
+  const Distribution *GetDistribution() const {
+    if (CachedDistribution == 0) Sort();
+    return CachedDistribution;
+  }
+
+  /// Prints out the contents of the distribution map to Stream.
+  void Print(raw_ostream &Stream, const std::string &Indent) const;
+
+  void Print(raw_ostream &Stream) const {
+    std::string Indent;
+    Print(Stream, Indent);
+  }
+
+protected:
+  /// If the distribution is cached, remove it. Should be called
+  /// whenever the distribution map is changed.
+  void RemoveCachedDistribution() const {
+    if (CachedDistribution) {
+      delete CachedDistribution;
+      CachedDistribution = 0;
+    }
+  }
+
+  /// Sorts the distribution, based on the importance of each element.
+  void Sort() const;
+
+private:
+  // Defines whether values in distribution map are from blocks or records.
+  const StorageSelector StorageKind;
+  // Sentinel element used to do generic operations for distribution.
+  const NaClBitcodeDistElement *Sentinel;
+  // Map from the distribution value to the corresponding distribution
+  // element.
+  MappedElement TableMap;
+  // Pointer to the cached distribution.
+  mutable Distribution *CachedDistribution;
+  // The total number of instances in the map.
+  unsigned Total;
+};
+
+/// Defines the element type of a PNaCl bitcode distribution map.
+/// This is the base class for all element types used in
+/// NaClBitcodeDist.  By default, only the number of instances
+/// of the corresponding distribution values is recorded.
+class NaClBitcodeDistElement {
+  NaClBitcodeDistElement(const NaClBitcodeDistElement &)
+      LLVM_DELETED_FUNCTION;
+  void operator=(const NaClBitcodeDistElement &)
+      LLVM_DELETED_FUNCTION;
+
+public:
+  /// Define kinds for isa, dyn_cast, etc. support. Only defined
+  /// for concrete classes.
+  enum NaClBitcodeDistElementKind {
+    RDE_Dist,                    // class NaClBitcodeDistElement.
+      RDE_AbbrevDist,            // class NaClBitcodeAbbrevDistElement.
+      RDE_AbbrevDistLast,
+      RDE_BitsDist,              // class NaClBitcodeBitsDistElement.
+        RDE_BitsAndAbbrevsDist,  // class NaClBitcodeBitsAndAbbrevsDistElement.
+          RDE_CodeDist,          // class NaClBitcodeCodeDistElement.
+            RDE_CompressCodeDist, // class NaClCompressCodeDistElement.
+            RDE_CompressCodeDistLast,
+          RDE_CodeDistLast,
+        RDE_BitsAndAbbrevsDistLast,
+      RDE_BitsDistLast,
+      RDE_BlockDist,             // class NaClBitcodeBlockDistElement.
+        RDE_NaClAnalBlockDist,   // class NaClAnalyzerBlockDistElement.
+        RDE_NaClAnalBlockDistLast,
+        RDE_PNaClCompressBlockDist, // class NaClCompressBlockDistElement.
+        RDE_PNaClCompressBlockDistLast,
+      RDE_BlockDistLast,
+      RDE_SizeDist,              // class NaClBitcodeSizeDistElement.
+      RDE_SizeDistLast,
+      RDE_SubblockDist,          // class NaClBitcodeSubblockDistElement
+      RDE_SubblockDistLast,
+      RDE_ValueDist,             // class NaClBitcodeValueDistElement.
+      RDE_ValueDistLast,
+      RDE_ValueIndexDist,        // class NaClBitcodeValueIndexDistElement.
+      RDE_ValueIndexDistLast,
+    RDE_DistLast
+  };
+
+  NaClBitcodeDistElementKind getKind() const { return Kind; }
+
+  static bool classof(const NaClBitcodeDistElement *Element) {
+    return Element->getKind() >= RDE_Dist && Element->getKind() < RDE_DistLast;
+  }
+
+private:
+  const NaClBitcodeDistElementKind Kind;
+
+public:
+
+  // Constructor to use in derived classes.
+  NaClBitcodeDistElement(
+      NaClBitcodeDistElementKind Kind=RDE_Dist)
+      : Kind(Kind), NumInstances(0)
+  {}
+
+  virtual ~NaClBitcodeDistElement();
+
+  // Adds an instance of the given record to this element.
+  virtual void AddRecord(const NaClBitcodeRecord &Record);
+
+  // Adds an instance of the given block to this element.
+  virtual void AddBlock(const NaClBitcodeBlock &Block);
+
+  // Returns the number of instances associated with this element.
+  unsigned GetNumInstances() const {
+    return NumInstances;
+  }
+
+  // Creates a new instance of this element for the given value. Used
+  // by class NaClBitcodeDist to create instances.
+  virtual NaClBitcodeDistElement *CreateElement(
+      NaClBitcodeDistValue Value) const = 0;
+
+  /// Interrogates the block record, and returns the corresponding
+  /// values that are being tracked by the distribution map. Must be
+  /// defined in derived classes.
+  virtual void GetValueList(const NaClBitcodeRecord &Record,
+                            ValueListType &ValueList) const;
+
+  // Returns the importance of this element. In many cases, it will be
+  // the number of instances associated with it. However, it need not
+  // be correlated to the number of instance. Used to sort the
+  // distribution map, where values with larger importance appear
+  // first. Value is the domain value associated with the element in
+  // the distribution map.
+  virtual double GetImportance(NaClBitcodeDistValue Value) const;
+
+  /// Returns the title to use when printing the title associated
+  /// with instances of this distribution element.
+  virtual const char *GetTitle() const;
+
+  /// Prints out the title of the distribution map associated with
+  /// instances of this distribution element.
+  virtual void PrintTitle(raw_ostream &Stream,
+                          const NaClBitcodeDist *Distribution) const;
+
+  /// Returns the header to use when printing the value associated
+  /// with instances of this distribution element.
+  virtual const char *GetValueHeader() const;
+
+  /// Prints out header for row of statistics associated with instances
+  /// of this distribution element.
+  virtual void PrintStatsHeader(raw_ostream &Stream) const;
+
+  /// Prints out the header to the printed distribution map associated
+  /// with instances of this distribution element.
+  void PrintHeader(raw_ostream &Stream) const;
+
+  /// Prints out statistics for the row with the given value.
+  virtual void PrintRowStats(raw_ostream &Stream,
+                             const NaClBitcodeDist *Distribution) const;
+
+  /// Prints out Value (in a row) to Stream.
+  virtual void PrintRowValue(raw_ostream &Stream,
+                             NaClBitcodeDistValue Value,
+                             const NaClBitcodeDist *Distribution) const;
+
+  /// Prints out a row in the printed distribution map.
+  virtual void PrintRow(raw_ostream &Stream,
+                        NaClBitcodeDistValue Value,
+                        const NaClBitcodeDist *Distribution) const;
+
+  /// Returns a pointer to the list of nested distributions that
+  /// should be printed when this element is printed. Return 0 if no
+  /// nested distributions should be printed.
+  virtual const SmallVectorImpl<NaClBitcodeDist*> *
+  GetNestedDistributions() const;
+
+  /// Prints out any nested distributions, if defined for the element.
+  /// Returns true if a nested distribution was printed.
+  bool PrintNestedDistIfApplicable(
+      raw_ostream &Stream, const std::string &Indent) const;
+
+private:
+  // The number of instances associated with this element.
+  unsigned NumInstances;
+};
+
+inline NaClBitcodeDistElement *NaClBitcodeDist::
+GetElement(NaClBitcodeDistValue Value) {
+  if (TableMap.find(Value) == TableMap.end()) {
+    TableMap[Value] = CreateElement(Value);
+  }
+  return TableMap[Value];
+}
+
+}
+
+#endif