[llvm-profdata] ProfileReader cleanup - preparation for MD5 refactoring - 3

[huangjd]

Summary

Cleanup profile reader classes to prepare for complex refactoring as propsed in D147740, continuing D148872
This is patch 3/n. This patch changes the behavior of function offset table.

Previously when reading ExtBinary profile, the funcOffsetTable (map) is always populated, and in addition if the profile is CS, the orderedFuncOffsets (list) is also populated. However when reading the function samples, only one of the container is being used, never both, so it's a huge waste of time to populate both. Added logic to select which one to use, and completely skip reading function offset table if we are in tool mode (all function samples are to be read sequentially regardless)

[davidxl]

llvm/include/llvm/ProfileData/SampleProfReader.h

686

does it need to check the section flag?

804–805

Is this a dead field?

[huangjd]

Added check for orderedFuncOffsets for CS profile back

[huangjd]

llvm/include/llvm/ProfileData/SampleProfReader.h

686

I added back the section flag to check if CS profile has ordered function offset table.

804–805

Updated.

[huangjd]

Combined similar code

[huangjd]

Fixed unused variable for release build

[hoy]

llvm/include/llvm/ProfileData/SampleProfReader.h

686

Does the function offset table for a remapper profile always come in sorted?

[wenlei]

llvm/include/llvm/ProfileData/SampleProfReader.h

673

all prefixes of the matched function can be loaded,

prefix is caller, but it's meant to read in all callees of matches functions.

686

This function now controls whether list or map is used, which is orthogonal to whether it's ordered (still controlled by section flag). So useOrderedFuncOffsets() is more like useFuncOffsetList() (as opposed to map).

useOrderedFuncOffsets and OrderedFuncOffsets need to be renamed to remove "Ordered" because with this change there's no guarantee it's actually ordered.

687

For readability, i'd suggest expand the logic with inline comments for each category. The big chunk of comment above the function is harder to parse and more prone to be out dated. Something like this:

// category and reason
if ....
   return true;

// category and reason
if ...
   return true;

...

// category and reason
return false;

[huangjd]

Rebase D149124 after compact binary deprecated

[huangjd]

llvm/include/llvm/ProfileData/SampleProfReader.h

641

This function is misleading and only used once. Data>=End does not imply at EOF in ExtBinary, so removing it.

[wenlei]

llvm/lib/ProfileData/SampleProfReader.cpp

723–733

we are using llvm-profdata tool

nit: as library code/comment, make no assumption of the specific tool as user. just say tools as opposed to compiler.

761

all prefixes of the matched function

You meant "all function profile with matching prefix/caller"?

766–769

Do we need a separate entry for this? Or merge it with the return false in the end?

[huangjd]

Rephrase some comments

[huangjd]

llvm/lib/ProfileData/SampleProfReader.cpp

766–769

I am keeping the logic in this order so that it is consistent with the control flow in readFuncProfiles because it is very complicated.

[davidxl]

llvm/lib/ProfileData/SampleProfReader.cpp

864

Add a comment here to reference to useFunctionOffsetList method to be in sync, or add assert of useFunctionOffsetList() in each branch below.

[wenlei]

llvm/lib/ProfileData/SampleProfReader.cpp

761

This comment is still inaccurate. The idea is to order the profiles so all profile sharing the same context prefix can be loaded together. i.e. If [A:1 @ B] is loaded, then [A:1 @ B:2 @ C], [A:1 @ B:3 @ D], [A:1 @ B:3 @ D:4 @ E] can all be loaded easily.

the profiles of all its prefix contexts (all callers on the call stack) are loaded

It's about loading callee profiles with matching caller context/prefix, rather than loading caller profiles.

766–769

sounds good.

[huangjd]

• Added comments and assert

[huangjd]

• Added comments and assert

[huangjd]

Included wrong diff

[wenlei]

lgtm, thanks.

[davidxl]

lgtm

llvm/include/llvm/ProfileData/SampleProfReader.h

public:
   };
 
   /// It includes all the names that have samples either in outline instance
   /// or inline instance.
   virtual std::vector<StringRef> *getNameTable() { return nullptr; }
   virtual bool dumpSectionInfo(raw_ostream &OS = dbgs()) { return false; };
 
   /// Return whether names in the profile are all MD5 numbers.
-  bool useMD5() { return ProfileIsMD5; }
+  bool useMD5() const { return ProfileIsMD5; }
 
   /// Force the profile to use MD5 in Sample contexts, even if function names
   /// are present.
   virtual void setProfileUseMD5() { ProfileIsMD5 = true; }
 
   /// Don't read profile without context if the flag is set. This is only meaningful
   /// for ExtBinary format.
   virtual void setSkipFlatProf(bool Skip) {}
protected:
   /// EC is set.
   ///
   /// \returns the read value.
   ErrorOr<StringRef> readString();
 
   /// Read the string index and check whether it overflows the table.
   template <typename T> inline ErrorOr<size_t> readStringIndex(T &Table);
 
-  /// Return true if we've reached the end of file.
-  bool at_eof() const { return Data >= End; }
-
   /// Read the next function profile instance.
   std::error_code readFuncProfile(const uint8_t *Start);
 
   /// Read the contents of the given profile instance.
   std::error_code readProfile(FunctionSamples &FProfile);
 
   /// Read the contents of Magic number and Version number.
   std::error_code readMagicIdent();
protected:
 
   /// Read a context indirectly via the CSNameTable.
   ErrorOr<SampleContextFrames> readContextFromTable();
 
   /// Read a context indirectly via the CSNameTable if the profile has context,
   /// otherwise same as readStringFromTable.
   ErrorOr<SampleContext> readSampleContextFromTable();
 
+  /// Determine which container readFuncOffsetTable() populates, the list
+  /// OrderedFuncOffsets or the map FuncOffsetTable, using this order:
+  /// (a) If profile is CS, the function offset table is expected to consist of
+  /// sequences of contexts in pre-order layout
+  /// (e.g. [A, A:1 @ B, A:1 @ B:2.3 @ C] [D, D:1 @ E]), so that when a match in
+  /// the module is found, all prefixes of the matched function can be loaded,
+  /// so the list container is needed.
+  /// (b) If the profile is MD5, use the map container to lookup functions in
+  /// the module. A remapper has no use on MD5 names.
+  /// (c) If a remapper is present, each function name in the profile needs to
+  /// be checked if its remapped name matches a function in the module, so use
+  /// the list container since each entry is accessed.
+  /// (d) For other cases, use the map container to lookup functions in the
+  /// module.
+  /// TODO: For (b) and (d), if the cardinality of the function offset table is
+  /// much smaller than the number of functions in the module, using the list
+  /// container should be faster, but we need to figure out the constant factor
+  /// to determine a cutoff.
+  bool useOrderedFuncOffsets() {
+    return ProfileIsCS || (!useMD5() && Remapper);
+  }
+
+  /// Read the whole function offset table from the profile file, and store it
+  /// to either OrderedFuncOffsets (list) or FuncOffsetTable (map). Clear the
+  /// previous function offset table.
+  std::error_code readFuncOffsetTable();
+
+  /// Read function profiles. If a module is present and function offset table
+  /// is available, only read profiles of functions present in the module.
+  std::error_code readFuncProfiles();
+
   /// Points to the current location in the buffer.
   const uint8_t *Data = nullptr;
 
   /// Points to the end of the buffer.
   const uint8_t *End = nullptr;
 
   /// Function name table.
   std::vector<StringRef> NameTable;
protected:
 
   /// The starting address of NameTable containing fixed length MD5.
   const uint8_t *MD5NameMemStart = nullptr;
 
   /// CSNameTable is used to save full context vectors. It is the backing buffer
   /// for SampleContextFrames.
   std::vector<SampleContextFrameVector> CSNameTable;
 
+  /// The table mapping from function context to the offset of its
+  /// FunctionSample towards file/section start.
+  DenseMap<SampleContext, uint64_t> FuncOffsetTable;
+
+  /// Function offset mapping ordered by contexts.
+  std::vector<std::pair<SampleContext, uint64_t>> OrderedFuncOffsets;
+
+  /// The set containing the functions to use when compiling a module.
+  DenseSet<StringRef> FuncsToUse;
+
 private:
   std::error_code readSummaryEntry(std::vector<ProfileSummaryEntry> &Entries);
   virtual std::error_code verifySPMagic(uint64_t Magic) = 0;
 };
 
 class SampleProfileReaderRawBinary : public SampleProfileReaderBinary {
 private:
   std::error_code verifySPMagic(uint64_t Magic) override;

 protected:
   std::vector<SecHdrTableEntry> SecHdrTable;
   std::error_code readSecHdrTableEntry(uint64_t Idx);
   std::error_code readSecHdrTable();
 
   std::error_code readFuncMetadata(bool ProfileHasAttribute);
   std::error_code readFuncMetadata(bool ProfileHasAttribute,
                                    FunctionSamples *FProfile);
-  std::error_code readFuncOffsetTable();
-  std::error_code readFuncProfiles();
   std::error_code readNameTableSec(bool IsMD5, bool FixedLengthMD5);
   std::error_code readCSNameTableSec();
   std::error_code readProfileSymbolList();
 
   std::error_code readHeader() override;
   std::error_code verifySPMagic(uint64_t Magic) override = 0;
   virtual std::error_code readOneSection(const uint8_t *Start, uint64_t Size,
                                          const SecHdrTableEntry &Entry);
   // placeholder for subclasses to dispatch their own section readers.
   virtual std::error_code readCustomSection(const SecHdrTableEntry &Entry) = 0;
 
   std::unique_ptr<ProfileSymbolList> ProfSymList;
 
-  /// The table mapping from function context to the offset of its
-  /// FunctionSample towards file start.
-  DenseMap<SampleContext, uint64_t> FuncOffsetTable;
-
-  /// Function offset mapping ordered by contexts.
-  std::unique_ptr<std::vector<std::pair<SampleContext, uint64_t>>>
-      OrderedFuncOffsets;
-
-  /// The set containing the functions to use when compiling a module.
-  DenseSet<StringRef> FuncsToUse;
-
   /// If SkipFlatProf is true, skip the sections with
   /// SecFlagFlat flag.
   bool SkipFlatProf = false;
 
-  bool FuncOffsetsOrdered = false;
-
 public:
   SampleProfileReaderExtBinaryBase(std::unique_ptr<MemoryBuffer> B,
                                    LLVMContext &C, SampleProfileFormat Format)
       : SampleProfileReaderBinary(std::move(B), C, Format) {}
 
   /// Read sample profiles in extensible format from the associated file.
   std::error_code readImpl() override;
 
   /// Get the total size of all \p Type sections.
SampleProfileReaderExtBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
       : SampleProfileReaderExtBinaryBase(std::move(B), C, Format) {}
 
   /// \brief Return true if \p Buffer is in the format supported by this class.
   static bool hasFormat(const MemoryBuffer &Buffer);
 };
 
 class SampleProfileReaderCompactBinary : public SampleProfileReaderBinary {
 private:
-  /// The table mapping from function name to the offset of its FunctionSample
-  /// towards file start.
-  DenseMap<StringRef, uint64_t> FuncOffsetTable;
-  /// The set containing the functions to use when compiling a module.
-  DenseSet<StringRef> FuncsToUse;
   std::error_code verifySPMagic(uint64_t Magic) override;
   std::error_code readHeader() override;
-  std::error_code readFuncOffsetTable();
 
 public:
   SampleProfileReaderCompactBinary(std::unique_ptr<MemoryBuffer> B,
                                    LLVMContext &C)
       : SampleProfileReaderBinary(std::move(B), C, SPF_Compact_Binary) {
     ProfileIsMD5 = true;
   }
 

llvm/lib/ProfileData/SampleProfReader.cpp

if (std::error_code EC = readProfile(CalleeProfile))
       return EC;
   }
 
   return sampleprof_error::success;
 }
 
 std::error_code
 SampleProfileReaderBinary::readFuncProfile(const uint8_t *Start) {
+  assert(Start < End && "out of LBRProfile section");
   Data = Start;
   auto NumHeadSamples = readNumber<uint64_t>();
   if (std::error_code EC = NumHeadSamples.getError())
     return EC;
 
   ErrorOr<SampleContext> FContext(readSampleContextFromTable());
   if (std::error_code EC = FContext.getError())
     return EC;
SampleProfileReaderBinary::readFuncProfile(const uint8_t *Start) {
   if (std::error_code EC = readProfile(FProfile))
     return EC;
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileReaderBinary::readImpl() {
   ProfileIsFS = ProfileIsFSDisciminator;
   FunctionSamples::ProfileIsFS = ProfileIsFS;
-  while (!at_eof()) {
-    if (std::error_code EC = readFuncProfile(Data))
-      return EC;
-  }
-
-  return sampleprof_error::success;
+  return readFuncProfiles();
 }
 
 ErrorOr<SampleContextFrames> SampleProfileReaderBinary::readContextFromTable() {
   auto ContextIdx = readNumber<size_t>();
   if (std::error_code EC = ContextIdx.getError())
     return EC;
   if (*ContextIdx >= CSNameTable.size())
     return sampleprof_error::truncated_name_table;
if (std::error_code EC = readCSNameTableSec())
       return EC;
     break;
   }
   case SecLBRProfile:
     if (std::error_code EC = readFuncProfiles())
       return EC;
     break;
   case SecFuncOffsetTable:
-    FuncOffsetsOrdered = hasSecFlag(Entry, SecFuncOffsetFlags::SecFlagOrdered);
+    // Only read function offset table if module is present, otherwise all
+    // profiles must be loaded anyways.
+    if (!M) {
+      Data = End;
+    } else {
+      assert((!ProfileIsCS ||
+              hasSecFlag(Entry, SecFuncOffsetFlags::SecFlagOrdered)) &&
+             "func offset table should always be sorted in CS profile");
       if (std::error_code EC = readFuncOffsetTable())
         return EC;
+    }
     break;
   case SecFuncMetadata: {
     ProfileIsProbeBased =
         hasSecFlag(Entry, SecFuncMetadataFlags::SecFlagIsProbeBased);
     FunctionSamples::ProfileIsProbeBased = ProfileIsProbeBased;
     bool HasAttribute =
         hasSecFlag(Entry, SecFuncMetadataFlags::SecFlagHasAttribute);
     if (std::error_code EC = readFuncMetadata(HasAttribute))
std::error_code SampleProfileReaderExtBinaryBase::readOneSection(
   }
   return sampleprof_error::success;
 }
 
 bool SampleProfileReaderExtBinaryBase::collectFuncsFromModule() {
   if (!M)
     return false;
   FuncsToUse.clear();
   for (auto &F : *M)
     FuncsToUse.insert(FunctionSamples::getCanonicalFnName(F));
   return true;
 }
 
-std::error_code SampleProfileReaderExtBinaryBase::readFuncOffsetTable() {
-  // If there are more than one FuncOffsetTable, the profile read associated
-  // with previous FuncOffsetTable has to be done before next FuncOffsetTable
+std::error_code SampleProfileReaderBinary::readFuncOffsetTable() {
+  // If there are more than one function offset table, the profile associated
+  // with the previous table has to be done reading before next one
   // is read.
   FuncOffsetTable.clear();
+  OrderedFuncOffsets.clear();
 
   auto Size = readNumber<uint64_t>();
   if (std::error_code EC = Size.getError())
     return EC;
 
+  bool UseOrderedFuncOffsets = useOrderedFuncOffsets();
+  if (UseOrderedFuncOffsets)
+    OrderedFuncOffsets.reserve(*Size);
+  else
     FuncOffsetTable.reserve(*Size);
 
-  if (FuncOffsetsOrdered) {
-    OrderedFuncOffsets =
-        std::make_unique<std::vector<std::pair<SampleContext, uint64_t>>>();
-    OrderedFuncOffsets->reserve(*Size);
-  }
-
   for (uint64_t I = 0; I < *Size; ++I) {
-    auto FContext(readSampleContextFromTable());
+    auto FContext = readSampleContextFromTable();
     if (std::error_code EC = FContext.getError())
       return EC;
 
     auto Offset = readNumber<uint64_t>();
     if (std::error_code EC = Offset.getError())
       return EC;
 
+    if (UseOrderedFuncOffsets)
+      OrderedFuncOffsets.emplace_back(*FContext, *Offset);
+    else
       FuncOffsetTable[*FContext] = *Offset;
-    if (FuncOffsetsOrdered)
-      OrderedFuncOffsets->emplace_back(*FContext, *Offset);
   }
 
   return sampleprof_error::success;
 }
 
-std::error_code SampleProfileReaderExtBinaryBase::readFuncProfiles() {
+std::error_code SampleProfileReaderBinary::readFuncProfiles() {
   // Collect functions used by current module if the Reader has been
   // given a module.
   // collectFuncsFromModule uses FunctionSamples::getCanonicalFnName
   // which will query FunctionSamples::HasUniqSuffix, so it has to be
   // called after FunctionSamples::HasUniqSuffix is set, i.e. after
   // NameTable section is read.
   bool LoadFuncsToBeUsed = collectFuncsFromModule();
 
-  // When LoadFuncsToBeUsed is false, load all the function profiles.
+  // When LoadFuncsToBeUsed is false, we are using llvm tools, or the format
+  // does not support load profile on demand, need to read all profiles.
   const uint8_t *Start = Data;
   if (!LoadFuncsToBeUsed) {
     while (Data < End) {
       if (std::error_code EC = readFuncProfile(Data))
         return EC;
     }
     assert(Data == End && "More data is read than expected");
   } else {
if (ProfileIsCS) {
 
       // For each function in current module, load all context profiles for
       // the function as well as their callee contexts which can help profile
       // guided importing for ThinLTO. This can be achieved by walking
       // through an ordered context container, where contexts are laid out
       // as if they were walked in preorder of a context trie. While
       // traversing the trie, a link to the highest common ancestor node is
       // kept so that all of its decendants will be loaded.
-      assert(OrderedFuncOffsets.get() &&
-             "func offset table should always be sorted in CS profile");
       const SampleContext *CommonContext = nullptr;
-      for (const auto &NameOffset : *OrderedFuncOffsets) {
+      for (const auto &NameOffset : OrderedFuncOffsets) {
         const auto &FContext = NameOffset.first;
         auto FName = FContext.getName();
         // For function in the current module, keep its farthest ancestor
         // context. This can be used to load itself and its child and
         // sibling contexts.
         if ((useMD5() && FuncGuidsToUse.count(std::stoull(FName.data()))) ||
             (!useMD5() && (FuncsToUse.count(FName) ||
                            (Remapper && Remapper->exist(FName))))) {
           if (!CommonContext || !CommonContext->IsPrefixOf(FContext))
             CommonContext = &FContext;
         }
 
         if (CommonContext == &FContext ||
             (CommonContext && CommonContext->IsPrefixOf(FContext))) {
           // Load profile for the current context which originated from
           // the common ancestor.
           const uint8_t *FuncProfileAddr = Start + NameOffset.second;
-          assert(FuncProfileAddr < End && "out of LBRProfile section");
           if (std::error_code EC = readFuncProfile(FuncProfileAddr))
             return EC;
         }
       }
-    } else {
-      if (useMD5()) {
-        for (auto Name : FuncsToUse) {
-          auto GUID = std::to_string(MD5Hash(Name));
-          auto iter = FuncOffsetTable.find(StringRef(GUID));
-          if (iter == FuncOffsetTable.end())
-            continue;
-          const uint8_t *FuncProfileAddr = Start + iter->second;
-          assert(FuncProfileAddr < End && "out of LBRProfile section");
-          if (std::error_code EC = readFuncProfile(FuncProfileAddr))
-            return EC;
-        }
-      } else {
-        for (auto NameOffset : FuncOffsetTable) {
-          SampleContext FContext(NameOffset.first);
-          auto FuncName = FContext.getName();
-          if (!FuncsToUse.count(FuncName) &&
-              (!Remapper || !Remapper->exist(FuncName)))
-            continue;
-          const uint8_t *FuncProfileAddr = Start + NameOffset.second;
-          assert(FuncProfileAddr < End && "out of LBRProfile section");
-          if (std::error_code EC = readFuncProfile(FuncProfileAddr))
-            return EC;
-        }
+    } else if (useMD5()) {
+    } else if (Remapper) {
+      for (auto NameOffset : OrderedFuncOffsets) {
+        if (!FuncsToUse.count(FuncName) && !Remapper->exist(FuncName))
+    } else {
+      for (auto Name : FuncsToUse) {
+        auto iter = FuncOffsetTable.find(Name);
+        if (iter == FuncOffsetTable.end())
+          continue;
+        const uint8_t *FuncProfileAddr = Start + iter->second;
+        if (std::error_code EC = readFuncProfile(FuncProfileAddr))
+          return EC;
       }
     }
     Data = End;
   }
   assert((CSProfileCount == 0 || CSProfileCount == Profiles.size()) &&
          "Cannot have both context-sensitive and regular profile");
   assert((!CSProfileCount || ProfileIsCS) &&
          "Section flag should be consistent with actual profile");
if (isCompressed) {
       End = BufStart + Buffer->getBufferSize();
     }
   }
 
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileReaderCompactBinary::readImpl() {
-  // Collect functions used by current module if the Reader has been
-  // given a module.
-  bool LoadFuncsToBeUsed = collectFuncsFromModule();
-  ProfileIsFS = ProfileIsFSDisciminator;
-  FunctionSamples::ProfileIsFS = ProfileIsFS;
-  std::vector<uint64_t> OffsetsToUse;
-  if (!LoadFuncsToBeUsed) {
-    // load all the function profiles.
-    for (auto FuncEntry : FuncOffsetTable) {
-      OffsetsToUse.push_back(FuncEntry.second);
-    }
-  } else {
-    // load function profiles on demand.
-    for (auto Name : FuncsToUse) {
-      auto GUID = std::to_string(MD5Hash(Name));
-      auto iter = FuncOffsetTable.find(StringRef(GUID));
-      if (iter == FuncOffsetTable.end())
-        continue;
-      OffsetsToUse.push_back(iter->second);
-    }
-  }
+  auto TableOffset = readUnencodedNumber<uint64_t>();
+  if (std::error_code EC = TableOffset.getError())
+    return EC;
 
-  for (auto Offset : OffsetsToUse) {
-    const uint8_t *SavedData = Data;
-    if (std::error_code EC = readFuncProfile(
-            reinterpret_cast<const uint8_t *>(Buffer->getBufferStart()) +
-            Offset))
+  const uint8_t *TableStart =
+      *TableOffset;
+
+  // Only read function offset table if a module is present, otherwise all
+  // profiles must be loaded anyways. In this case offset is from the beginning
+  // of the file.
+  if (M) {
+    Data = TableStart;
+    if (std::error_code EC = readFuncOffsetTable())
       return EC;
-    Data = SavedData;
+    Data = reinterpret_cast<const uint8_t *>(Buffer->getBufferStart());
   }
-  return sampleprof_error::success;
+  End = TableStart;
+
+  return SampleProfileReaderBinary::readImpl();
 }
 
 std::error_code SampleProfileReaderRawBinary::verifySPMagic(uint64_t Magic) {
   if (Magic == SPMagic())
     return sampleprof_error::success;
   return sampleprof_error::bad_magic;
 }
 
if (std::error_code EC = readMagicIdent())
     return EC;
 
   if (std::error_code EC = readSummary())
     return EC;
 
   if (std::error_code EC = readMD5NameTable())
     return EC;
 
-  if (std::error_code EC = readFuncOffsetTable())
-     return EC;
-  return sampleprof_error::success;
-}
-
-std::error_code SampleProfileReaderCompactBinary::readFuncOffsetTable() {
-  auto TableOffset = readUnencodedNumber<uint64_t>();
-  if (std::error_code EC = TableOffset.getError())
-    return EC;
-
-  const uint8_t *SavedData = Data;
-  const uint8_t *TableStart =
-      reinterpret_cast<const uint8_t *>(Buffer->getBufferStart()) +
-      *TableOffset;
-  Data = TableStart;
-
-  auto Size = readNumber<uint64_t>();
-  if (std::error_code EC = Size.getError())
-    return EC;
-
-  FuncOffsetTable.reserve(*Size);
-  for (uint64_t I = 0; I < *Size; ++I) {
-    auto FName(readStringFromTable());
-    if (std::error_code EC = FName.getError())
-      return EC;
-
-    auto Offset = readNumber<uint64_t>();
-    if (std::error_code EC = Offset.getError())
-      return EC;
-
-    FuncOffsetTable[*FName] = *Offset;
-  }
-  End = TableStart;
-  Data = SavedData;
   return sampleprof_error::success;
 }
 
 bool SampleProfileReaderCompactBinary::collectFuncsFromModule() {
   if (!M)
     return false;
   FuncsToUse.clear();
   for (auto &F : *M)