Rebased PNaCl localmods in LLVM to 223109

lib/Bitcode/NaCl/Analysis/NaClBitcodeValueDist.cpp

+//===-- NaClBitcodeValueDist.cpp ------------------------------------------===//
+//      Implements (nested) distribution maps to separate out values at each
+//      index in a bitcode record.
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Bitcode/NaCl/NaClBitcodeValueDist.h"
+#include "llvm/Support/DataTypes.h"
+
+using namespace llvm;
+
+/// Constant defining cutoff for value distributions. All values less than
+/// this constant will be stored as a singleton range.
+static NaClBitcodeDistValue ValueDistSingletonCutoff =
+    (NaClBitcodeDistValue)1 << 6;
+
+/// Largest value possible.
+static NaClBitcodeDistValue MaxValue = ~((NaClBitcodeDistValue) 0);
+
+/// Cutoffs for value ranges, starting the first range at
+/// ValueDistSingetonCutoff, and ending the last range with MaxValue.
+static NaClBitcodeDistValue ValueCutoffs[] = {
+  (NaClBitcodeDistValue)1 << 8,
+  (NaClBitcodeDistValue)1 << 12,
+  (NaClBitcodeDistValue)1 << 16,
+  (NaClBitcodeDistValue)1 << 24,
+  (NaClBitcodeDistValue)1 << 32
+};
+
+// Converts the value to the corresponding range (value) that will
+// be stored in a value distribution map.
+NaClValueRangeIndexType
+llvm::GetNaClValueRangeIndex(NaClBitcodeDistValue Value) {
+  if (Value < ValueDistSingletonCutoff)
+    return Value;
+
+  size_t ValueCutoffsSize = array_lengthof(ValueCutoffs);
+  for (size_t i = 0; i < ValueCutoffsSize; ++i) {
+    if (Value < ValueCutoffs[i]) {
+      return ValueDistSingletonCutoff + i;
+    }
+  }
+
+  return ValueDistSingletonCutoff + ValueCutoffsSize;
+}
+
+NaClValueRangeType llvm::GetNaClValueRange(NaClValueRangeIndexType RangeIndex) {
+  if (RangeIndex < ValueDistSingletonCutoff)
+    return NaClValueRangeType(RangeIndex, RangeIndex);
+
+  size_t Index = RangeIndex - ValueDistSingletonCutoff;
+  size_t ValueCutoffsSize = array_lengthof(ValueCutoffs);
+  if (Index >= ValueCutoffsSize)
+    return NaClValueRangeType(ValueCutoffs[ValueCutoffsSize-1], MaxValue);
+  else if (Index == 0)
+    return NaClValueRangeType(ValueDistSingletonCutoff, ValueCutoffs[0]);
+  else
+    return NaClValueRangeType(ValueCutoffs[Index-1], ValueCutoffs[Index]-1);
+}
+
+NaClBitcodeValueDistElement NaClBitcodeValueDistElement::Sentinel;
+
+NaClBitcodeValueDistElement::~NaClBitcodeValueDistElement() {}
+
+NaClBitcodeDistElement *NaClBitcodeValueDistElement::CreateElement(
+      NaClBitcodeDistValue Value) const {
+  return new NaClBitcodeValueDistElement();
+}
+
+double NaClBitcodeValueDistElement::
+GetImportance(NaClBitcodeDistValue Value) const {
+  NaClValueRangeType Pair = GetNaClValueRange(Value);
+  return GetNumInstances() / static_cast<double>((Pair.second-Pair.first) + 1);
+}
+
+const char *NaClBitcodeValueDistElement::GetTitle() const {
+  return "Values";
+}
+
+const char *NaClBitcodeValueDistElement::GetValueHeader() const {
+  return "Value / Range";
+}
+
+void NaClBitcodeValueDistElement::
+PrintRowValue(raw_ostream &Stream,
+              NaClBitcodeDistValue Value,
+              const NaClBitcodeDist *Distribution) const {
+  NaClValueRangeType Range = GetNaClValueRange(Value);
+  Stream << format("%" PRIu64, Range.first);
+  if (Range.first != Range.second) {
+    Stream << " .. " << format("%" PRIu64, Range.second);
+  }
+}
+
+/// Defines the sentinel distribution element of range indices for untracked
+/// indices in the bitcode records, which need a clarifying print title.
+class NaClBitcodeUntrackedValueDistElement
+    : public NaClBitcodeValueDistElement {
+public:
+  static NaClBitcodeUntrackedValueDistElement Sentinel;
+
+  virtual ~NaClBitcodeUntrackedValueDistElement();
+
+  virtual const char *GetTitle() const;
+
+private:
+  NaClBitcodeUntrackedValueDistElement()
+      : NaClBitcodeValueDistElement()
+  {}
+};
+
+NaClBitcodeUntrackedValueDistElement
+NaClBitcodeUntrackedValueDistElement::Sentinel;
+
+NaClBitcodeUntrackedValueDistElement::~NaClBitcodeUntrackedValueDistElement() {}
+
+const char *NaClBitcodeUntrackedValueDistElement::GetTitle() const {
+  return "Values for untracked indices";
+}
+
+NaClBitcodeValueDist::
+NaClBitcodeValueDist(unsigned Index, bool AllRemainingIndices)
+    : NaClBitcodeDist(RecordStorage,
+                      (AllRemainingIndices
+                       ? &NaClBitcodeUntrackedValueDistElement::Sentinel
+                       : &NaClBitcodeValueDistElement::Sentinel),
+                      RD_ValueDist),
+      Index(Index),
+      AllRemainingIndices(AllRemainingIndices) {
+}
+
+NaClBitcodeValueDist::~NaClBitcodeValueDist() {}
+
+void NaClBitcodeValueDist::GetValueList(const NaClBitcodeRecord &Record,
+                                        ValueListType &ValueList) const {
+  const NaClBitcodeRecord::RecordVector &Values = Record.GetValues();
+  if (AllRemainingIndices) {
+    for (size_t i = Index, i_limit = Values.size(); i < i_limit; ++i) {
+      ValueList.push_back(GetNaClValueRangeIndex(Values[i]));
+    }
+  } else {
+    ValueList.push_back(GetNaClValueRangeIndex(Values[Index]));
+  }
+}
+
+NaClBitcodeValueIndexDistElement NaClBitcodeValueIndexDistElement::Sentinel;
+
+NaClBitcodeValueIndexDistElement::~NaClBitcodeValueIndexDistElement() {}
+
+NaClBitcodeDistElement *NaClBitcodeValueIndexDistElement::CreateElement(
+    NaClBitcodeDistValue Value) const {
+  return new NaClBitcodeValueIndexDistElement(Value);
+}
+
+void NaClBitcodeValueIndexDistElement::
+GetValueList(const NaClBitcodeRecord &Record, ValueListType &ValueList) const {
+  unsigned i_limit = Record.GetValues().size();
+  if (i_limit > NaClValueIndexCutoff) i_limit = NaClValueIndexCutoff;
+  for (size_t i = 0; i < i_limit; ++i) {
+    ValueList.push_back(i);
+  }
+}
+
+double NaClBitcodeValueIndexDistElement::
+GetImportance(NaClBitcodeDistValue Value) const {
+  // Since all indices (usually) have the same number of instances,
+  // that is a bad measure of importance. Rather, we will base
+  // importance in terms of the value distribution for the value
+  // index. We would like the indicies with a few, large instance
+  // counts, to appear before value indices with a uniform value
+  // distribution. To do this, we will use the sum of the squares of
+  // the number of instances for each value (i.e. sort by standard
+  // deviation).
+  double Sum = 0.0;
+  for (NaClBitcodeDist::const_iterator
+           Iter = ValueDist.begin(), IterEnd = ValueDist.end();
+       Iter != IterEnd; ++Iter) {
+    const NaClBitcodeValueDistElement *Elmt =
+        cast<NaClBitcodeValueDistElement>(Iter->second);
+    double Count = static_cast<double>(Elmt->GetImportance(Iter->first));
+    Sum += Count * Count;
+  }
+  return Sum;
+}
+
+void NaClBitcodeValueIndexDistElement::
+AddRecord(const NaClBitcodeRecord &Record) {
+  NaClBitcodeDistElement::AddRecord(Record);
+  ValueDist.AddRecord(Record);
+}
+
+const char *NaClBitcodeValueIndexDistElement::GetTitle() const {
+  return "Value indices";
+}
+
+const char *NaClBitcodeValueIndexDistElement::GetValueHeader() const {
+  return "  Index";
+}
+
+void NaClBitcodeValueIndexDistElement::
+PrintRowValue(raw_ostream &Stream,
+              NaClBitcodeDistValue Value,
+              const NaClBitcodeDist *Distribution) const {
+  Stream << format("%7u", Value);
+}
+
+const SmallVectorImpl<NaClBitcodeDist*> *NaClBitcodeValueIndexDistElement::
+GetNestedDistributions() const {
+  return &NestedDists;
+}