[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

685

does it need to check the section flag?

780–781

Is this a dead field?

[huangjd]

Added check for orderedFuncOffsets for CS profile back

[huangjd]

llvm/include/llvm/ProfileData/SampleProfReader.h

685

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

780–781

Updated.

[huangjd]

Combined similar code

[huangjd]

Fixed unused variable for release build

[hoy]

llvm/include/llvm/ProfileData/SampleProfReader.h

685

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

[wenlei]

llvm/include/llvm/ProfileData/SampleProfReader.h

672

all prefixes of the matched function can be loaded,

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

685

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.

686

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

643

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

730–740

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.

768

all prefixes of the matched function

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

773–776

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

773–776

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

900

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

768

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.

773–776

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

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:
   /// otherwise same as readStringFromTable.
   ErrorOr<SampleContext> readSampleContextFromTable();
 
   /// 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;
 
   /// If MD5 is used in NameTable section, the section saves uint64_t data.
   /// The uint64_t data has to be converted to a string and then the string
   /// will be used to initialize StringRef in NameTable.
   /// Note NameTable contains StringRef so it needs another buffer to own
   /// the string data. MD5StringBuf serves as the string buffer that is
   /// referenced by NameTable (vector of StringRef). We make sure
   /// the lifetime of MD5StringBuf is not shorter than that of NameTable.
   std::vector<std::string> MD5StringBuf;
 
   /// 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;
 
 private:
   std::error_code readSummaryEntry(std::vector<ProfileSummaryEntry> &Entries);
   virtual std::error_code verifySPMagic(uint64_t Magic) = 0;
protected:
 
   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;
 
+  /// Determine which container readFuncOffsetTable() should populate, the list
+  /// FuncOffsetList or the map FuncOffsetTable.
+  bool useFuncOffsetList() const;
+
   std::unique_ptr<ProfileSymbolList> ProfSymList;
 
   /// The table mapping from function context to the offset of its
   /// FunctionSample towards file start.
+  /// At most one of FuncOffsetTable and FuncOffsetList is populated.
   DenseMap<SampleContext, uint64_t> FuncOffsetTable;
 
-  /// Function offset mapping ordered by contexts.
-  std::unique_ptr<std::vector<std::pair<SampleContext, uint64_t>>>
-      OrderedFuncOffsets;
+  /// The list version of FuncOffsetTable. This is used if every entry is
+  /// being accessed.
+  std::vector<std::pair<SampleContext, uint64_t>> FuncOffsetList;
 
   /// 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.

llvm/lib/ProfileData/SampleProfReader.cpp

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()) {
+  while (Data < End) {
     if (std::error_code EC = readFuncProfile(Data))
       return EC;
   }
 
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileReaderExtBinaryBase::readOneSection(
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);
+    // If module is absent, we are using LLVM tools, and need to read all
+    // profiles, so skip reading the function offset table.
+    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))
       return EC;
     break;
   }
   case SecProfileSymbolList:
     if (std::error_code EC = readProfileSymbolList())
       return EC;
     break;
   default:
     if (std::error_code EC = readCustomSection(Entry))
       return EC;
     break;
   }
   return sampleprof_error::success;
 }
 
+bool SampleProfileReaderExtBinaryBase::useFuncOffsetList() const {
+  // If profile is CS, the function offset section 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 matched
+  // context in the module is found, the profiles of all its callees are
+  // recursively loaded. A list is needed since the order of profiles matters.
+  if (ProfileIsCS)
+    return true;
+
+  // If the profile is MD5, use the map container to lookup functions in
+  // the module. A remapper has no use on MD5 names.
+  if (useMD5())
+    return false;
+
+  // Profile is not MD5 and if a remapper is present, the remapped name of
+  // every function needed to be matched against the module, so use the list
+  // container since each entry is accessed.
+  if (Remapper)
+    return true;
+
+  // Otherwise use the map container for faster lookup.
+  // TODO: If the cardinality of the function offset section is much smaller
+  // than the number of functions in the module, using the list container can
+  // be always faster, but we need to figure out the constant factor to
+  // determine the cutoff.
+  return false;
+}
+
+
 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
-  // is read.
+  // If there are more than one function offset section, the profile associated
+  // with the previous section has to be done reading before next one is read.
   FuncOffsetTable.clear();
+  FuncOffsetList.clear();
 
   auto Size = readNumber<uint64_t>();
   if (std::error_code EC = Size.getError())
     return EC;
 
+  bool UseFuncOffsetList = useFuncOffsetList();
+  if (UseFuncOffsetList)
+    FuncOffsetList.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());
     if (std::error_code EC = FContext.getError())
       return EC;
 
     auto Offset = readNumber<uint64_t>();
     if (std::error_code EC = Offset.getError())
       return EC;
 
+    if (UseFuncOffsetList)
+      FuncOffsetList.emplace_back(*FContext, *Offset);
+    else
       FuncOffsetTable[*FContext] = *Offset;
-    if (FuncOffsetsOrdered)
-      OrderedFuncOffsets->emplace_back(*FContext, *Offset);
-  }
 
-  return sampleprof_error::success;
 }
 
 std::error_code SampleProfileReaderExtBinaryBase::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 tool, 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 {
     // Load function profiles on demand.
     if (Remapper) {
       for (auto Name : FuncsToUse) {
         Remapper->insert(Name);
       }
     }
 
     if (ProfileIsCS) {
+      assert(useFuncOffsetList());
       DenseSet<uint64_t> FuncGuidsToUse;
       if (useMD5()) {
         for (auto Name : FuncsToUse)
           FuncGuidsToUse.insert(Function::getGUID(Name));
       }
 
       // 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 : FuncOffsetList) {
         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()) {
+      assert(!useFuncOffsetList());
+    } else if (Remapper) {
+      assert(useFuncOffsetList());
+      for (auto NameOffset : FuncOffsetList) {
+        if (!FuncsToUse.count(FuncName) && !Remapper->exist(FuncName))
+    } else {
+      assert(!useFuncOffsetList());
+      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");