[PGO] Add support for reading multiple versions of indexed profile format profile data

[davidxl]

Summary

LLVM profile reader for indexed format is intended to be backward compatible -- a new version of compiler producing different format of indexed profile data should be able to read old version of indexed profile data produced by older versions of compilers. However currently it is hard to read different versions of profile data with different key types with the current reader implementation.

This patch solves the problem. To read a particular version of indexed profile is will be as simple as instantiating the index template class with the OnDiskHashTable implementation type associated with that version. There will be a follow up patch to templatize the InstrProfLookupTrait class (for different key types associated with the format).

[vsk]

I like this approach. Some comments below --

include/llvm/ProfileData/InstrProfReader.h

263

nit, profile

281

It'd make for less typing if we use typename IndexType and keep std::unique_ptr<IndexType> Index where you have HashTable.

lib/ProfileData/InstrProfReader.cpp

538–544

nullptr?

542

I expected this to be an NFC commit, but this looks like breakage. InstrProfWriter uses IndexedInstrProf::Version (3).

[davidxl]

include/llvm/ProfileData/InstrProfReader.h

281

Removed OnDisk prefix to shorten the typename.

lib/ProfileData/InstrProfReader.cpp

542

Good catch. Fixed.

This indicates a hole in the test coverage. I will add V2 and V3 format test cases in a follow up patch.

[davidxl]

Update patch with vsk's comments.

[vsk]

Thanks. With one simplification this lgtm --

lib/ProfileData/InstrProfReader.cpp

542

The check on line 522 errors out with a diagnostic for this already. We can safely omit the conditional and say Index.reset(new InstrProfReaderIndex ...).

include/llvm/ProfileData/InstrProfReader.h

public:
   data_type ReadData(StringRef K, const unsigned char *D, offset_type N);
 
   // Used for testing purpose only.
   void setValueProfDataEndianness(support::endianness Endianness) {
     ValueProfDataEndianness = Endianness;
   }
 };
 
-class InstrProfReaderIndex {
- private:
-  typedef OnDiskIterableChainedHashTable<InstrProfLookupTrait> IndexType;
+struct InstrProfReaderIndexBase {
+  // Read all the profile records with the same key pointed to the current
+  // iterator.
+  virtual std::error_code getRecords(ArrayRef<InstrProfRecord> &Data) = 0;
+  // Read all the profile records with the key equal to FuncName
+  virtual std::error_code getRecords(StringRef FuncName,
+                                     ArrayRef<InstrProfRecord> &Data) = 0;
+  virtual void advanceToNextKey() = 0;
+  virtual bool atEnd() const = 0;
+  virtual void setValueProfDataEndianness(support::endianness Endianness) = 0;
+  virtual ~InstrProfReaderIndexBase() {}
+};
 
-  std::unique_ptr<IndexType> Index;
-  IndexType::data_iterator RecordIterator;
+typedef OnDiskIterableChainedHashTable<InstrProfLookupTrait>
+    OnDiskHashTableImplV3;
+
+template <typename HashTableImpl>
+class InstrProfReaderIndex : public InstrProfReaderIndexBase {
+
+private:
+  std::unique_ptr<HashTableImpl> HashTable;
+  typename HashTableImpl::data_iterator RecordIterator;
   uint64_t FormatVersion;
 
   // String table for holding a unique copy of all the strings in the profile.
   InstrProfStringTable StringTable;
 
- public:
-  InstrProfReaderIndex() : Index(nullptr) {}
-  void Init(const unsigned char *Buckets, const unsigned char *const Payload,
-            const unsigned char *const Base, IndexedInstrProf::HashT HashType,
-            uint64_t Version);
+  InstrProfReaderIndex(const unsigned char *Buckets,
+                       const unsigned char *const Payload,
+                       const unsigned char *const Base,
+                       IndexedInstrProf::HashT HashType, uint64_t Version);
 
-  // Read all the pofile records with the same key pointed to the current
-  // iterator.
-  std::error_code getRecords(ArrayRef<InstrProfRecord> &Data);
-  // Read all the profile records with the key equal to FuncName
+  std::error_code getRecords(ArrayRef<InstrProfRecord> &Data) override;
   std::error_code getRecords(StringRef FuncName,
-                             ArrayRef<InstrProfRecord> &Data);
-
-  void advanceToNextKey() { RecordIterator++; }
-  bool atEnd() const { return RecordIterator == Index->data_end(); }
-  // Used for testing purpose only.
-  void setValueProfDataEndianness(support::endianness Endianness) {
-    Index->getInfoObj().setValueProfDataEndianness(Endianness);
+                             ArrayRef<InstrProfRecord> &Data) override;
+  void advanceToNextKey() override { RecordIterator++; }
+  bool atEnd() const override {
+    return RecordIterator == HashTable->data_end();
+  }
+  void setValueProfDataEndianness(support::endianness Endianness) override {
+    HashTable->getInfoObj().setValueProfDataEndianness(Endianness);
   }
+  ~InstrProfReaderIndex() override {}
 };
 
 /// Reader for the indexed binary instrprof format.
 class IndexedInstrProfReader : public InstrProfReader {
 private:
   /// The profile data file contents.
   std::unique_ptr<MemoryBuffer> DataBuffer;
   /// The index into the profile data.
-  InstrProfReaderIndex Index;
+  std::unique_ptr<InstrProfReaderIndexBase> Index;
   /// The maximal execution count among all functions.
   uint64_t MaxFunctionCount;
 
   IndexedInstrProfReader(const IndexedInstrProfReader &) = delete;
   IndexedInstrProfReader &operator=(const IndexedInstrProfReader &) = delete;
 
- public:
   IndexedInstrProfReader(std::unique_ptr<MemoryBuffer> DataBuffer)
-      : DataBuffer(std::move(DataBuffer)), Index() {}
+      : DataBuffer(std::move(DataBuffer)), Index(nullptr) {}
 
   /// Return true if the given buffer is in an indexed instrprof format.
   static bool hasFormat(const MemoryBuffer &DataBuffer);
 
   /// Read the file header.
   std::error_code readHeader() override;
   /// Read a single record.
   std::error_code readNextRecord(InstrProfRecord &Record) override;
public:
   static ErrorOr<std::unique_ptr<IndexedInstrProfReader>>
   create(std::string Path);
 
   static ErrorOr<std::unique_ptr<IndexedInstrProfReader>>
   create(std::unique_ptr<MemoryBuffer> Buffer);
 
   // Used for testing purpose only.
   void setValueProfDataEndianness(support::endianness Endianness) {
-    Index.setValueProfDataEndianness(Endianness);
+    Index->setValueProfDataEndianness(Endianness);
   }
 };
 
 } // end namespace llvm
 
 #endif

include/llvm/Support/OnDiskHashTable.h

 template <typename Info> class OnDiskChainedHashTable {
   const typename Info::offset_type NumBuckets;
   const typename Info::offset_type NumEntries;
   const unsigned char *const Buckets;
   const unsigned char *const Base;
   Info InfoObj;
 
 public:
+  typedef Info InfoType;
   typedef typename Info::internal_key_type internal_key_type;
   typedef typename Info::external_key_type external_key_type;
-  typedef typename Info::data_type         data_type;
-  typedef typename Info::hash_value_type   hash_value_type;
-  typedef typename Info::offset_type       offset_type;
+  typedef typename Info::data_type data_type;
+  typedef typename Info::hash_value_type hash_value_type;
+  typedef typename Info::offset_type offset_type;
 
   OnDiskChainedHashTable(offset_type NumBuckets, offset_type NumEntries,
                          const unsigned char *Buckets,
                          const unsigned char *Base,
                          const Info &InfoObj = Info())
       : NumBuckets(NumBuckets), NumEntries(NumEntries), Buckets(Buckets),
         Base(Base), InfoObj(InfoObj) {
     assert((reinterpret_cast<uintptr_t>(Buckets) & 0x3) == 0 &&

lib/ProfileData/InstrProfReader.cpp

while (D < End) {
     if (FormatVersion > 2 && !readValueProfilingData(D, End)) {
       DataBuffer.clear();
       return data_type();
     }
   }
   return DataBuffer;
 }
 
-std::error_code
-InstrProfReaderIndex::getRecords(StringRef FuncName,
-                                 ArrayRef<InstrProfRecord> &Data) {
-  auto Iter = Index->find(FuncName);
-  if (Iter == Index->end())
+template <typename HashTableImpl>
+std::error_code InstrProfReaderIndex<HashTableImpl>::getRecords(
+    StringRef FuncName, ArrayRef<InstrProfRecord> &Data) {
+  auto Iter = HashTable->find(FuncName);
+  if (Iter == HashTable->end())
     return instrprof_error::unknown_function;
 
   Data = (*Iter);
   if (Data.empty())
     return instrprof_error::malformed;
 
   return instrprof_error::success;
 }
 
-std::error_code InstrProfReaderIndex::getRecords(
+template <typename HashTableImpl>
+std::error_code InstrProfReaderIndex<HashTableImpl>::getRecords(
     ArrayRef<InstrProfRecord> &Data) {
-  if (atEnd()) return instrprof_error::eof;
+  if (atEnd())
+    return instrprof_error::eof;
 
   Data = *RecordIterator;
 
   if (Data.empty()) return instrprof_error::malformed;
 
   return instrprof_error::success;
 }
 
-void InstrProfReaderIndex::Init(const unsigned char *Buckets,
-                                const unsigned char *const Payload,
-                                const unsigned char *const Base,
-                                IndexedInstrProf::HashT HashType,
-                                uint64_t Version) {
+template <typename HashTableImpl>
+InstrProfReaderIndex<HashTableImpl>::InstrProfReaderIndex(
+    const unsigned char *Buckets, const unsigned char *const Payload,
+    const unsigned char *const Base, IndexedInstrProf::HashT HashType,
   FormatVersion = Version;
-  Index.reset(IndexType::Create(Buckets, Payload, Base,
-                                InstrProfLookupTrait(HashType, Version)));
+  HashTable.reset(HashTableImpl::Create(
+      Buckets, Payload, Base,
+      typename HashTableImpl::InfoType(HashType, Version)));
   // Form the map of hash values to const char* keys in profiling data.
   std::vector<std::pair<uint64_t, const char *>> HashKeys;
-  for (auto Key : Index->keys()) {
+  for (auto Key : HashTable->keys()) {
     const char *KeyTableRef = StringTable.insertString(Key);
     HashKeys.push_back(std::make_pair(ComputeHash(HashType, Key), KeyTableRef));
   }
   std::sort(HashKeys.begin(), HashKeys.end(), less_first());
   HashKeys.erase(std::unique(HashKeys.begin(), HashKeys.end()), HashKeys.end());
   // Set the hash key map for the InstrLookupTrait
-  Index->getInfoObj().setHashKeys(std::move(HashKeys));
-  RecordIterator = Index->data_begin();
+  HashTable->getInfoObj().setHashKeys(std::move(HashKeys));
+  RecordIterator = HashTable->data_begin();
 }
 
 bool IndexedInstrProfReader::hasFormat(const MemoryBuffer &DataBuffer) {
   if (DataBuffer.getBufferSize() < 8)
     return false;
   using namespace support;
   uint64_t Magic =
       endian::read<uint64_t, little, aligned>(DataBuffer.getBufferStart());
std::error_code IndexedInstrProfReader::readHeader() {
   IndexedInstrProf::HashT HashType = static_cast<IndexedInstrProf::HashT>(
       endian::byte_swap<uint64_t, little>(Header->HashType));
   if (HashType > IndexedInstrProf::HashT::Last)
     return error(instrprof_error::unsupported_hash_type);
 
   uint64_t HashOffset = endian::byte_swap<uint64_t, little>(Header->HashOffset);
 
   // The rest of the file is an on disk hash table.
-  Index.Init(Start + HashOffset, Cur, Start, HashType, FormatVersion);
-
+  InstrProfReaderIndexBase *IndexPtr = nullptr;
+  if (FormatVersion <= 3)
+    IndexPtr = new InstrProfReaderIndex<OnDiskHashTableImplV3>(
+        Start + HashOffset, Cur, Start, HashType, FormatVersion);
+  else
+    llvm_unreachable("Unsupported profile data version");
+  Index.reset(IndexPtr);
   return success();
 }
 
 ErrorOr<InstrProfRecord>
 IndexedInstrProfReader::getInstrProfRecord(StringRef FuncName,
                                            uint64_t FuncHash) {
   ArrayRef<InstrProfRecord> Data;
-  std::error_code EC = Index.getRecords(FuncName, Data);
+  std::error_code EC = Index->getRecords(FuncName, Data);
   if (EC != instrprof_error::success)
     return EC;
   // Found it. Look for counters with the right hash.
   for (unsigned I = 0, E = Data.size(); I < E; ++I) {
     // Check for a match and fill the vector if there is one.
     if (Data[I].Hash == FuncHash) {
       return std::move(Data[I]);
     }

 }
 
 std::error_code IndexedInstrProfReader::readNextRecord(
     InstrProfRecord &Record) {
   static unsigned RecordIndex = 0;
 
   ArrayRef<InstrProfRecord> Data;
 
-  std::error_code EC = Index.getRecords(Data);
+  std::error_code EC = Index->getRecords(Data);
   if (EC != instrprof_error::success)
     return error(EC);
 
   Record = Data[RecordIndex++];
   if (RecordIndex >= Data.size()) {
-    Index.advanceToNextKey();
+    Index->advanceToNextKey();
     RecordIndex = 0;
   }
   return success();
 }