InstrProf: Support for value profiling in the indexed profile format

Add support to the indexed instrprof reader and writer for the format
that will be used for value profiling.

Patch by Betul Buyukkurt, with minor modifications.

llvm-svn: 248833

3 files changed, 108 insertions, 22 deletions

diff --git a/llvm/include/llvm/ProfileData/InstrProf.h b/llvm/include/llvm/ProfileData/InstrProf.h
index 77055ba8726..49780e4abab 100644
--- a/llvm/include/llvm/ProfileData/InstrProf.h
+++ b/llvm/include/llvm/ProfileData/InstrProf.h
@@ -16,8 +16,10 @@
 #ifndef LLVM_PROFILEDATA_INSTRPROF_H_
 #define LLVM_PROFILEDATA_INSTRPROF_H_
 
-#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
+#include "llvm/Support/ErrorHandling.h"
 #include <cstdint>
+#include <list>
 #include <system_error>
 #include <vector>
 
@@ -25,25 +27,84 @@ namespace llvm {
 const std::error_category &instrprof_category();
 
 enum class instrprof_error {
-    success = 0,
-    eof,
-    bad_magic,
-    bad_header,
-    unsupported_version,
-    unsupported_hash_type,
-    too_large,
-    truncated,
-    malformed,
-    unknown_function,
-    hash_mismatch,
-    count_mismatch,
-    counter_overflow
+  success = 0,
+  eof,
+  bad_magic,
+  bad_header,
+  unsupported_version,
+  unsupported_hash_type,
+  too_large,
+  truncated,
+  malformed,
+  unknown_function,
+  hash_mismatch,
+  count_mismatch,
+  counter_overflow,
+  value_site_count_mismatch
 };
 
 inline std::error_code make_error_code(instrprof_error E) {
   return std::error_code(static_cast<int>(E), instrprof_category());
 }
 
+enum InstrProfValueKind : uint32_t {
+  IPVK_IndirectCallTarget = 0,
+
+  IPVK_First = IPVK_IndirectCallTarget,
+  IPVK_Last = IPVK_IndirectCallTarget
+};
+
+struct InstrProfStringTable {
+  // Set of string values in profiling data.
+  StringSet<> StringValueSet;
+  InstrProfStringTable() { StringValueSet.clear(); }
+  // Get a pointer to internal storage of a string in set
+  const char *getStringData(StringRef Str) {
+    auto Result = StringValueSet.find(Str);
+    return (Result == StringValueSet.end()) ? nullptr : Result->first().data();
+  }
+  // Insert a string to StringTable
+  const char *insertString(StringRef Str) {
+    auto Result = StringValueSet.insert(Str);
+    return Result.first->first().data();
+  }
+};
+
+struct InstrProfValueSiteRecord {
+  /// Typedef for a single TargetValue-NumTaken pair.
+  typedef std::pair<uint64_t, uint64_t> ValueDataPair;
+  /// Value profiling data pairs at a given value site.
+  std::list<ValueDataPair> ValueData;
+
+  InstrProfValueSiteRecord() { ValueData.clear(); }
+
+  /// Sort ValueData ascending by TargetValue
+  void sortByTargetValues() {
+    ValueData.sort([](const ValueDataPair &left, const ValueDataPair &right) {
+      return left.first < right.first;
+    });
+  }
+
+  /// Merge data from another InstrProfValueSiteRecord
+  void mergeValueData(InstrProfValueSiteRecord &Input) {
+    this->sortByTargetValues();
+    Input.sortByTargetValues();
+    auto I = ValueData.begin();
+    auto IE = ValueData.end();
+    for (auto J = Input.ValueData.begin(), JE = Input.ValueData.end(); J != JE;
+         ++J) {
+      while (I != IE && I->first < J->first)
+        ++I;
+      if (I != IE && I->first == J->first) {
+        I->second += J->second;
+        ++I;
+        continue;
+      }
+      ValueData.insert(I, *J);
+    }
+  }
+};
+
 /// Profiling information for a single function.
 struct InstrProfRecord {
   InstrProfRecord() {}
@@ -52,6 +113,22 @@ struct InstrProfRecord {
   StringRef Name;
   uint64_t Hash;
   std::vector<uint64_t> Counts;
+  std::vector<InstrProfValueSiteRecord> IndirectCallSites;
+
+  const std::vector<InstrProfValueSiteRecord> &
+  getValueSitesForKind(uint32_t ValueKind) const {
+    switch (ValueKind) {
+    case IPVK_IndirectCallTarget:
+      return IndirectCallSites;
+    }
+    llvm_unreachable("Unknown value kind!");
+  }
+
+  std::vector<InstrProfValueSiteRecord> &
+  getValueSitesForKind(uint32_t ValueKind) {
+    return const_cast<std::vector<InstrProfValueSiteRecord> &>(
+        this->getValueSitesForKind(ValueKind));
+  }
 };
 
 } // end namespace llvm
diff --git a/llvm/include/llvm/ProfileData/InstrProfReader.h b/llvm/include/llvm/ProfileData/InstrProfReader.h
index f937e7d08d5..c0585d6f6d2 100644
--- a/llvm/include/llvm/ProfileData/InstrProfReader.h
+++ b/llvm/include/llvm/ProfileData/InstrProfReader.h
@@ -65,6 +65,9 @@ public:
   InstrProfIterator end() { return InstrProfIterator(); }
 
 protected:
+  /// String table for holding a unique copy of all the strings in the profile.
+  InstrProfStringTable StringTable;
+
   /// Set the current std::error_code and return same.
   std::error_code error(std::error_code EC) {
     LastError = EC;
@@ -195,6 +198,7 @@ class InstrProfLookupTrait {
   std::vector<InstrProfRecord> DataBuffer;
   IndexedInstrProf::HashT HashType;
   unsigned FormatVersion;
+  std::vector<std::pair<uint64_t, const char *>> HashKeys;
 
 public:
   InstrProfLookupTrait(IndexedInstrProf::HashT HashType, unsigned FormatVersion)
@@ -209,9 +213,13 @@ public:
 
   static bool EqualKey(StringRef A, StringRef B) { return A == B; }
   static StringRef GetInternalKey(StringRef K) { return K; }
+  static StringRef GetExternalKey(StringRef K) { return K; }
 
   hash_value_type ComputeHash(StringRef K);
 
+  void setHashKeys(std::vector<std::pair<uint64_t, const char *>> HashKeys) {
+    this->HashKeys = std::move(HashKeys);
+  }
   static std::pair<offset_type, offset_type>
   ReadKeyDataLength(const unsigned char *&D) {
     using namespace support;
@@ -224,6 +232,8 @@ public:
     return StringRef((const char *)D, N);
   }
 
+  bool ReadValueProfilingData(const unsigned char *&D,
+                              const unsigned char *const End);
   data_type ReadData(StringRef K, const unsigned char *D, offset_type N);
 };
 
diff --git a/llvm/include/llvm/ProfileData/InstrProfWriter.h b/llvm/include/llvm/ProfileData/InstrProfWriter.h
index ce0bb524249..da0d956e8a9 100644
--- a/llvm/include/llvm/ProfileData/InstrProfWriter.h
+++ b/llvm/include/llvm/ProfileData/InstrProfWriter.h
@@ -15,33 +15,32 @@
 #ifndef LLVM_PROFILEDATA_INSTRPROFWRITER_H
 #define LLVM_PROFILEDATA_INSTRPROFWRITER_H
 
-#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/StringMap.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/Support/DataTypes.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
-#include <vector>
 
 namespace llvm {
 
 /// Writer for instrumentation based profile data.
 class InstrProfWriter {
 public:
-  typedef SmallDenseMap<uint64_t, std::vector<uint64_t>, 1> CounterData;
+  typedef SmallDenseMap<uint64_t, InstrProfRecord, 1> ProfilingData;
+
 private:
-  StringMap<CounterData> FunctionData;
+  InstrProfStringTable StringTable;
+  StringMap<ProfilingData> FunctionData;
   uint64_t MaxFunctionCount;
 public:
   InstrProfWriter() : MaxFunctionCount(0) {}
 
+  /// Update string entries in profile data with references to StringTable.
+  void updateStringTableReferences(InstrProfRecord &I);
   /// Add function counts for the given function. If there are already counts
   /// for this function and the hash and number of counts match, each counter is
   /// summed.
-  std::error_code addFunctionCounts(StringRef FunctionName,
-                                    uint64_t FunctionHash,
-                                    ArrayRef<uint64_t> Counters);
+  std::error_code addRecord(InstrProfRecord &&I);
   /// Write the profile to \c OS
   void write(raw_fd_ostream &OS);
   /// Write the profile, returning the raw data. For testing.