[SampleFDO] Add indexing for function profiles so they can be loaded on demand in ExtBinary format

[wmi]

Summary

Currently for Text, Binary and ExtBinary format profiles, when we compile a module with samplefdo, even if there is no function showing up in the profile, we have to load all the function profiles from the profile input. That is a waste of compile time.

CompactBinary format profile has already had the support of loading function profiles on demand. In this patch, we add the indexing in ExtBinary format too. It will work no matter the sections in ExtBinary format profile are compressed or not. Experiment shows it reduces the time to compile a server benchmark by 30%.

When profile remapping and loading function profiles on demand are both used, extra work needs to be done so that the loading on demand process will take the name remapping into consideration. It will be addressed in a follow-up patch.

[wenlei]

Thanks for making indexing available for extended binary format. We've recently adding indexing to binary format as well in an internal patch, and also observed similar (~30%) build time reduction for some large services.

We also have have the need to differentiate dead/cold symbols vs new symbols, so symbol list in extended binary format is useful to us as well - will try it out. (I noticed that a small change in profile generation tool (the equivalent of https://github.com/google/autofdo) is needed to populate that list though, it'd be nice if these are all part of LLVM)

Left some comments inline. In addition, I think llvm-profdata/Inputs/sample-profile.proftext need to be updated as well to include the new section for roundtrip.test

llvm/include/llvm/ProfileData/SampleProfWriter.h

206

With the addition of offset table at the end of sections but in the middle of section header, I found the name SectionLayout a bit confusing. This array actually represents the layout/order of section header (e.g. the reader order), but not the section (payload) layout (the writer order). I guess renaming it SectionHdrLayout or something alike may help..

Besides, some comments explaining why SecFuncOffsetTable need to be in the middle could help too, it looks like a hidden trick until I saw the comments in SampleProfileReaderExtBinaryBase::getFileSize().

llvm/lib/ProfileData/SampleProfReader.cpp

547–548

nit: similar to line 539, we could assert the random access here never attempts to touch anything beyond Size?

[wmi]

In D68601#1699113, @wenlei wrote:

Thanks for making indexing available for extended binary format. We've recently adding indexing to binary format as well in an internal patch, and also observed similar (~30%) build time reduction for some large services.

Thanks for providing the data!

We also have have the need to differentiate dead/cold symbols vs new symbols, so symbol list in extended binary format is useful to us as well - will try it out. (I noticed that a small change in profile generation tool (the equivalent of https://github.com/google/autofdo) is needed to populate that list though, it'd be nice if these are all part of LLVM)

You can use llvm-profdata to attach the profile symbol list section. Symbol list can be provided to llvm-profdata in a plain text file.

Left some comments inline. In addition, I think llvm-profdata/Inputs/sample-profile.proftext need to be updated as well to include the new section for roundtrip.test

The roundtrip test doesn't contain any golden file in extbinary format. It generates the extbinary format profile on the fly. The input sample-profile.proftext doesn't need change.

llvm/include/llvm/ProfileData/SampleProfWriter.h

206

Indeed SectionHdrLayout is a better name. I changed it and added comment to explain why SecFuncOffsetTable is after SecLBRProfile in the profile but is before SecLBRProfile in the section header table.

llvm/lib/ProfileData/SampleProfReader.cpp

547–548

assertion added.

[wmi]

Address Wenlei's comment.

[wenlei]

LGTM. Thanks!

Symbol list can be provided to llvm-profdata in a plain text file.

I thought it's more convenient to have PSL auto-populated by the tool that generates AutoFDO profile, or is there any reason for not using auto-generated PSL, and instead providing a plain text file as side input?

[davidxl]

llvm/include/llvm/ProfileData/SampleProfReader.h

554

Nit: collectFuncsFrom(const Module &M)

llvm/lib/ProfileData/SampleProfReader.cpp

507

Skip declarations?

533

End = Data + Size

536

It is more readable if readFuncProfile is taking the pointer to the data address:

readFuncProfile(&Data);

[wmi]

In D68601#1700595, @wenlei wrote:

LGTM. Thanks!

Symbol list can be provided to llvm-profdata in a plain text file.

I thought it's more convenient to have PSL auto-populated by the tool that generates AutoFDO profile, or is there any reason for not using auto-generated PSL, and instead providing a plain text file as side input?

Putting the list in a plain text file gives more flexibility so user can order the list and strip some of them. You are right it is convenient for create_llvm_prof to get the list from binary directly. I just wanted to point out there is an existing alternative support before we port the support of create_llvm_prof to github.

[wmi]

llvm/include/llvm/ProfileData/SampleProfReader.h

554

Fixed

llvm/lib/ProfileData/SampleProfReader.cpp

507

Fixed

533

It is set in the parent function: readOneSection.

536

Fixed.

[wmi]

Address David's comment.

[davidxl]

llvm/lib/ProfileData/SampleProfReader.cpp

533

What I meant is to define a local variable 'End' and use it instead of of Start. It makes code slightly more readable.

[wmi]

llvm/lib/ProfileData/SampleProfReader.cpp

533

I see. Actually the class member "End" is also set to be end of section in readOneSection, and it is a little confusing to have two "End" variables, so I clean it further to remove the param "Size" and use class member "End" instead.

[wmi]

Address David's comment.

[davidxl]

lgtm

llvm/include/llvm/ProfileData/SampleProf.h

 // Section Type used by SampleProfileExtBinaryBaseReader and
 // SampleProfileExtBinaryBaseWriter. Never change the existing
 // value of enum. Only append new ones.
 enum SecType {
   SecInValid = 0,
   SecProfSummary = 1,
   SecNameTable = 2,
   SecProfileSymbolList = 3,
+  SecFuncOffsetTable = 4,
   // marker for the first type of profile.
   SecFuncProfileFirst = 32,
   SecLBRProfile = SecFuncProfileFirst
 };
 
 static inline std::string getSecName(SecType Type) {
   switch (Type) {
   case SecInValid:
     return "InvalidSection";
   case SecProfSummary:
     return "ProfileSummarySection";
   case SecNameTable:
     return "NameTableSection";
   case SecProfileSymbolList:
     return "ProfileSymbolListSection";
+  case SecFuncOffsetTable:
+    return "FuncOffsetTableSection";
   case SecLBRProfile:
     return "LBRProfileSection";
   }
   llvm_unreachable("A SecType has no name for output");
 }
 
 // Entry type of section header table used by SampleProfileExtBinaryBaseReader
 // and SampleProfileExtBinaryBaseWriter.

llvm/include/llvm/ProfileData/SampleProfReader.h

 };
 
 class SampleProfileReaderExtBinary : public SampleProfileReaderExtBinaryBase {
 private:
   virtual std::error_code verifySPMagic(uint64_t Magic) override;
   virtual std::error_code readOneSection(const uint8_t *Start, uint64_t Size,
                                          SecType Type) override;
   std::error_code readProfileSymbolList(uint64_t Size);
+  std::error_code readFuncOffsetTable();
+  std::error_code readFuncProfiles(uint64_t Size);
+
+  /// 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;
+  /// Use all functions from the input profile.
+  bool UseAllFuncs = true;
 
 public:
   SampleProfileReaderExtBinary(std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
                                SampleProfileFormat Format = SPF_Ext_Binary)
       : 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);
 
   virtual std::unique_ptr<ProfileSymbolList> getProfileSymbolList() override {
     return std::move(ProfSymList);
   };
+
+  /// Collect functions to be used when compiling Module \p M.
+  void collectFuncsToUse(const Module &M) override;
 };
 
 class SampleProfileReaderCompactBinary : public SampleProfileReaderBinary {
 private:
   /// Function name table.
   std::vector<std::string> NameTable;
   /// The table mapping from function name to the offset of its FunctionSample
   /// towards file start.

llvm/include/llvm/ProfileData/SampleProfWriter.h

 
 class SampleProfileWriterExtBinary : public SampleProfileWriterExtBinaryBase {
 public:
   SampleProfileWriterExtBinary(std::unique_ptr<raw_ostream> &OS)
       : SampleProfileWriterExtBinaryBase(OS) {
     initSectionLayout();
   }
 
+  virtual std::error_code writeSample(const FunctionSamples &S) override;
   virtual void setProfileSymbolList(ProfileSymbolList *PSL) override {
     ProfSymList = PSL;
   };
 
 private:
   virtual void initSectionLayout() override {
     SectionLayout = {{SecProfSummary, 0, 0, 0},
                      {SecNameTable, 0, 0, 0},
+                     {SecFuncOffsetTable, 0, 0, 0},
                      {SecLBRProfile, 0, 0, 0},
                      {SecProfileSymbolList, 0, 0, 0}};
   };
   virtual std::error_code
   writeSections(const StringMap<FunctionSamples> &ProfileMap) override;
   ProfileSymbolList *ProfSymList = nullptr;
+
+  // Save the start of SecLBRProfile so we can compute the offset to the
+  // start of SecLBRProfile for each Function's Profile and will keep it
+  // in FuncOffsetTable.
+  uint64_t SecLBRProfileStart;
+  // FuncOffsetTable maps function name to its profile offset in SecLBRProfile
+  // section. It is used to load function profile on demand.
+  MapVector<StringRef, uint64_t> FuncOffsetTable;
+  std::error_code writeFuncOffsetTable();
 };
 
 // CompactBinary is a compact format of binary profile which both reduces
 // the profile size and the load time needed when compiling. It has two
 // major difference with Binary format.
 // 1. It represents all the strings in name table using md5 hash.
 // 2. It saves a function offset table which maps function name index to
 // the offset of its function profile to the start of the binary profile,

llvm/lib/ProfileData/SampleProfReader.cpp

case SecProfSummary:
     if (std::error_code EC = readSummary())
       return EC;
     break;
   case SecNameTable:
     if (std::error_code EC = readNameTable())
       return EC;
     break;
   case SecLBRProfile:
-    while (Data < Start + Size) {
-      if (std::error_code EC = readFuncProfile())
-        return EC;
-    }
+    if (std::error_code EC = readFuncProfiles(Size))
     break;
   case SecProfileSymbolList:
     if (std::error_code EC = readProfileSymbolList(Size))
       return EC;
     break;
+  case SecFuncOffsetTable:
+    if (std::error_code EC = readFuncOffsetTable())
+      return EC;
+    break;
   default:
     break;
   }
   return sampleprof_error::success;
 }
 
+void SampleProfileReaderExtBinary::collectFuncsToUse(const Module &M) {
+  UseAllFuncs = false;
+  FuncsToUse.clear();
+  for (auto &F : M) {
+    StringRef CanonName = FunctionSamples::getCanonicalFnName(F);
+    FuncsToUse.insert(CanonName);
+  }
+}
+
+std::error_code SampleProfileReaderExtBinary::readFuncOffsetTable() {
+  auto Size = readNumber<uint64_t>();
+  if (std::error_code EC = Size.getError())
+    return EC;
+
+  FuncOffsetTable.reserve(*Size);
+  for (uint32_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;
+  }
+  return sampleprof_error::success;
+}
+
+std::error_code SampleProfileReaderExtBinary::readFuncProfiles(uint64_t Size) {
+  const uint8_t *Start = Data;
+  if (UseAllFuncs) {
+    while (Data < Start + Size) {
+      if (std::error_code EC = readFuncProfile())
+        return EC;
+    }
+    assert(Data == Start + Size && "More data is read than expected");
+    return sampleprof_error::success;
+  }
+
+  for (auto Name : FuncsToUse) {
+    auto iter = FuncOffsetTable.find(Name);
+    if (iter == FuncOffsetTable.end())
+      continue;
+    Data = Start + iter->second;
+    if (std::error_code EC = readFuncProfile())
+      return EC;
+  }
+  Data = Start + Size;
+  return sampleprof_error::success;
+}
+
 std::error_code
 SampleProfileReaderExtBinary::readProfileSymbolList(uint64_t Size) {
   if (!ProfSymList)
     ProfSymList = std::make_unique<ProfileSymbolList>();
 
   if (std::error_code EC = ProfSymList->read(Data, Size))
     return EC;
 
uint64_t SampleProfileReaderExtBinaryBase::getSectionSize(SecType Type) {
   for (auto &Entry : SecHdrTable) {
     if (Entry.Type == Type)
       return Entry.Size;
   }
   return 0;
 }
 
 uint64_t SampleProfileReaderExtBinaryBase::getFileSize() {
-  auto &LastEntry = SecHdrTable.back();
-  return LastEntry.Offset + LastEntry.Size;
+  // Sections in SecHdrTable is not necessarily in the same order as
+  // sections in the profile because section like FuncOffsetTable needs
+  // to be written after section LBRProfile but needs to be read before
+  // section LBRProfile, so we cannot simply use the last entry in
+  // SecHdrTable to calculate the file size.
+  uint64_t FileSize = 0;
+  for (auto &Entry : SecHdrTable) {
+    FileSize = std::max(Entry.Offset + Entry.Size, FileSize);
+  }
+  return FileSize;
 }
 
 bool SampleProfileReaderExtBinaryBase::dumpSectionInfo(raw_ostream &OS) {
   uint64_t TotalSecsSize = 0;
   for (auto &Entry : SecHdrTable) {
     OS << getSecName(Entry.Type) << " - Offset: " << Entry.Offset
        << ", Size: " << Entry.Size << "\n";
     TotalSecsSize += getSectionSize(Entry.Type);

llvm/lib/ProfileData/SampleProfWriter.cpp

if (std::error_code EC = writeSections(ProfileMap))
     return EC;
 
   if (std::error_code EC = writeSecHdrTable())
     return EC;
 
   return sampleprof_error::success;
 }
 
+std::error_code
+SampleProfileWriterExtBinary::writeSample(const FunctionSamples &S) {
+  uint64_t Offset = OutputStream->tell();
+  StringRef Name = S.getName();
+  FuncOffsetTable[Name] = Offset - SecLBRProfileStart;
+  encodeULEB128(S.getHeadSamples(), *OutputStream);
+  return writeBody(S);
+}
+
+std::error_code SampleProfileWriterExtBinary::writeFuncOffsetTable() {
+  auto &OS = *OutputStream;
+
+  // Write out the table size.
+  encodeULEB128(FuncOffsetTable.size(), OS);
+
+  // Write out FuncOffsetTable.
+  for (auto entry : FuncOffsetTable) {
+    writeNameIdx(entry.first);
+    encodeULEB128(entry.second, OS);
+  }
+  return sampleprof_error::success;
+}
+
 std::error_code SampleProfileWriterExtBinary::writeSections(
     const StringMap<FunctionSamples> &ProfileMap) {
   uint64_t SectionStart = markSectionStart(SecProfSummary);
   computeSummary(ProfileMap);
   if (auto EC = writeSummary())
     return EC;
   if (std::error_code EC = addNewSection(SecProfSummary, SectionStart))
     return EC;
 
   // Generate the name table for all the functions referenced in the profile.
   SectionStart = markSectionStart(SecNameTable);
   for (const auto &I : ProfileMap) {
     addName(I.first());
     addNames(I.second);
   }
   writeNameTable();
   if (std::error_code EC = addNewSection(SecNameTable, SectionStart))
     return EC;
 
   SectionStart = markSectionStart(SecLBRProfile);
+  SecLBRProfileStart = OutputStream->tell();
   if (std::error_code EC = writeFuncProfiles(ProfileMap))
     return EC;
   if (std::error_code EC = addNewSection(SecLBRProfile, SectionStart))
     return EC;
 
   if (ProfSymList && ProfSymList->toCompress())
     setToCompressSection(SecProfileSymbolList);
 
   SectionStart = markSectionStart(SecProfileSymbolList);
   if (ProfSymList && ProfSymList->size() > 0)
     if (std::error_code EC = ProfSymList->write(*OutputStream))
       return EC;
   if (std::error_code EC = addNewSection(SecProfileSymbolList, SectionStart))
     return EC;
 
+  SectionStart = markSectionStart(SecFuncOffsetTable);
+  if (std::error_code EC = writeFuncOffsetTable())
+    return EC;
+  if (std::error_code EC = addNewSection(SecFuncOffsetTable, SectionStart))
+    return EC;
+
   return sampleprof_error::success;
 }
 
 std::error_code SampleProfileWriterCompactBinary::write(
     const StringMap<FunctionSamples> &ProfileMap) {
   if (std::error_code EC = SampleProfileWriter::write(ProfileMap))
     return EC;
   if (std::error_code EC = writeFuncOffsetTable())

llvm/unittests/ProfileData/SampleProfTest.cpp

void testRoundTrip(SampleProfileFormat Format, bool Remap) {
     BarSamples.addHeadSamples(1437);
     BarSamples.addBodySamples(1, 0, 1437);
     // Test how reader/writer handles unmangled names.
     StringRef MconstructName("_M_construct<char *>");
     StringRef StringviewName("string_view<std::allocator<char> >");
     BarSamples.addCalledTargetSamples(1, 0, MconstructName, 1000);
     BarSamples.addCalledTargetSamples(1, 0, StringviewName, 437);
 
+    StringRef BazName("_Z3bazi");
+    FunctionSamples BazSamples;
+    BazSamples.setName(BazName);
+    BazSamples.addTotalSamples(12557);
+    BazSamples.addHeadSamples(1257);
+    BazSamples.addBodySamples(1, 0, 12557);
+
     Module M("my_module", Context);
     FunctionType *fn_type =
         FunctionType::get(Type::getVoidTy(Context), {}, false);
     M.getOrInsertFunction(FooName, fn_type);
     M.getOrInsertFunction(BarName, fn_type);
 
     StringMap<FunctionSamples> Profiles;
     Profiles[FooName] = std::move(FooSamples);
     Profiles[BarName] = std::move(BarSamples);
+    Profiles[BazName] = std::move(BazSamples);
 
     ProfileSymbolList List;
     if (Format == SampleProfileFormat::SPF_Ext_Binary) {
       List.add("zoo", true);
       List.add("moo", true);
     }
     Writer->setProfileSymbolList(&List);
 
if (Remap) {
           std::move(MemBuffer), Context, std::move(Reader)));
       FooName = "_Z4fauxi";
       BarName = "_Z3barl";
 
       EC = Reader->read();
       ASSERT_TRUE(NoError(EC));
     }
 
-    ASSERT_EQ(2u, Reader->getProfiles().size());
-
     FunctionSamples *ReadFooSamples = Reader->getSamplesFor(FooName);
     ASSERT_TRUE(ReadFooSamples != nullptr);
     if (Format != SampleProfileFormat::SPF_Compact_Binary) {
       ASSERT_EQ("_Z3fooi", ReadFooSamples->getName());
     }
     ASSERT_EQ(7711u, ReadFooSamples->getTotalSamples());
     ASSERT_EQ(610u, ReadFooSamples->getHeadSamples());
 
     FunctionSamples *ReadBarSamples = Reader->getSamplesFor(BarName);
     ASSERT_TRUE(ReadBarSamples != nullptr);
     if (Format != SampleProfileFormat::SPF_Compact_Binary) {
       ASSERT_EQ("_Z3bari", ReadBarSamples->getName());
     }
     ASSERT_EQ(20301u, ReadBarSamples->getTotalSamples());
     ASSERT_EQ(1437u, ReadBarSamples->getHeadSamples());
     ErrorOr<SampleRecord::CallTargetMap> CTMap =
         ReadBarSamples->findCallTargetMapAt(1, 0);
     ASSERT_FALSE(CTMap.getError());
 
+    // Because _Z3bazi is not defined in module M, expect _Z3bazi's profile
+    // is not loaded when the profile is ExtBinary or Compact format because
+    // these formats support loading function profiles on demand.
+    FunctionSamples *ReadBazSamples = Reader->getSamplesFor(BazName);
+    if (Format == SampleProfileFormat::SPF_Ext_Binary ||
+        Format == SampleProfileFormat::SPF_Compact_Binary) {
+      ASSERT_TRUE(ReadBazSamples == nullptr);
+      ASSERT_EQ(2u, Reader->getProfiles().size());
+    } else {
+      ASSERT_TRUE(ReadBazSamples != nullptr);
+      ASSERT_EQ(12557u, ReadBazSamples->getTotalSamples());
+      ASSERT_EQ(3u, Reader->getProfiles().size());
+    }
+
     std::string MconstructGUID;
     StringRef MconstructRep =
         getRepInFormat(MconstructName, Format, MconstructGUID);
     std::string StringviewGUID;
     StringRef StringviewRep =
         getRepInFormat(StringviewName, Format, StringviewGUID);
     ASSERT_EQ(1000u, CTMap.get()[MconstructRep]);
     ASSERT_EQ(437u, CTMap.get()[StringviewRep]);
 
     auto VerifySummary = [](ProfileSummary &Summary) mutable {
       ASSERT_EQ(ProfileSummary::PSK_Sample, Summary.getKind());
-      ASSERT_EQ(123603u, Summary.getTotalCount());
-      ASSERT_EQ(6u, Summary.getNumCounts());
-      ASSERT_EQ(2u, Summary.getNumFunctions());
+      ASSERT_EQ(136160u, Summary.getTotalCount());
+      ASSERT_EQ(7u, Summary.getNumCounts());
+      ASSERT_EQ(3u, Summary.getNumFunctions());
       ASSERT_EQ(1437u, Summary.getMaxFunctionCount());
       ASSERT_EQ(60351u, Summary.getMaxCount());
 
       uint32_t Cutoff = 800000;
       auto Predicate = [&Cutoff](const ProfileSummaryEntry &PE) {
         return PE.Cutoff == Cutoff;
       };
       std::vector<ProfileSummaryEntry> &Details = Summary.getDetailedSummary();
       auto EightyPerc = find_if(Details, Predicate);
       Cutoff = 900000;
       auto NinetyPerc = find_if(Details, Predicate);
       Cutoff = 950000;
       auto NinetyFivePerc = find_if(Details, Predicate);
       Cutoff = 990000;
       auto NinetyNinePerc = find_if(Details, Predicate);
       ASSERT_EQ(60000u, EightyPerc->MinCount);
-      ASSERT_EQ(60000u, NinetyPerc->MinCount);
-      ASSERT_EQ(60000u, NinetyFivePerc->MinCount);
+      ASSERT_EQ(12557u, NinetyPerc->MinCount);
+      ASSERT_EQ(12557u, NinetyFivePerc->MinCount);
       ASSERT_EQ(610u, NinetyNinePerc->MinCount);
     };
 
     ProfileSummary &Summary = Reader->getSummary();
     VerifySummary(Summary);
 
     // Test that conversion of summary to and from Metadata works.
     Metadata *MD = Summary.getMD(Context);