[SHT_LLVM_BB_ADDR_MAP] Allow basic-block-sections and labels be used together by decoupling the handling of the two features. (#74128)

Today `-split-machine-functions` and `-fbasic-block-sections={all,list}`
cannot be combined with `-basic-block-sections=labels` (the labels
option will be ignored).
The inconsistency comes from the way basic block address map -- the
underlying mechanism for basic block labels -- encodes basic block
addresses
(https://lists.llvm.org/pipermail/llvm-dev/2020-July/143512.html).
Specifically, basic block offsets are computed relative to the function
begin symbol. This relies on functions being contiguous which is not the
case for MFS and basic block section binaries. This means Propeller
cannot use binary profiles collected from these binaries, which limits
the applicability of Propeller for iterative optimization.
    
To make the `SHT_LLVM_BB_ADDR_MAP` feature work with basic block section
binaries, we propose modifying the encoding of this section as follows.

First let us review the current encoding which emits the address of each
function and its number of basic blocks, followed by basic block entries
for each basic block.

| | |
|--|--|
| Address of the function | Function Address |
|  Number of basic blocks in this function | NumBlocks |
|  BB entry 1
|  BB entry 2
|   ...
|  BB entry #NumBlocks
    
To make this work for basic block sections, we treat each basic block
section similar to a function, except that basic block sections of the
same function must be encapsulated in the same structure so we can map
all of them to their single function.
    
We modify the encoding to first emit the number of basic block sections
(BB ranges) in the function. Then we emit the address map of each basic
block section section as before: the base address of the section, its
number of blocks, and BB entries for its basic block. The first section
in the BB address map is always the function entry section.
| | |
|--|--|
|  Number of sections for this function   | NumBBRanges |
| Section 1 begin address                     | BaseAddress[1]  |
| Number of basic blocks in section 1 | NumBlocks[1]    |
| BB entries for Section 1
|..................|
| Section #NumBBRanges begin address | BaseAddress[NumBBRanges] |
| Number of basic blocks in section #NumBBRanges |
NumBlocks[NumBBRanges] |
| BB entries for Section #NumBBRanges
    
The encoding of basic block entries remains as before with the minor
change that each basic block offset is now computed relative to the
begin symbol of its containing BB section.
    
This patch adds a new boolean codegen option `-basic-block-address-map`.
Correspondingly, the front-end flag `-fbasic-block-address-map` and LLD
flag `--lto-basic-block-address-map` are introduced.
Analogously, we add a new TargetOption field `BBAddrMap`. This means BB
address maps are either generated for all functions in the compiling
unit, or for none (depending on `TargetOptions::BBAddrMap`).
    
This patch keeps the functionality of the old
`-fbasic-block-sections=labels` option but does not remove it. A
subsequent patch will remove the obsolete option.

We refactor the `BasicBlockSections` pass by separating the BB address
map and BB sections handing to their own functions (named
`handleBBAddrMap` and `handleBBSections`). `handleBBSections` renumbers
basic blocks and places them in their assigned sections.
`handleBBAddrMap` is invoked after `handleBBSections` (if requested) and
only renumbers the blocks.
  - New tests added:
- Two tests basic-block-address-map-with-basic-block-sections.ll and
basic-block-address-map-with-mfs.ll to exercise the combination of
`-basic-block-address-map` with `-basic-block-sections=list` and
'-split-machine-functions`.
- A driver sanity test for the `-fbasic-block-address-map` option
(basic-block-address-map.c).
- An LLD test for testing the `--lto-basic-block-address-map` option.
This reuses the LLVM IR from `lld/test/ELF/lto/basic-block-sections.ll`.
- Renamed and modified the two existing codegen tests for basic block
address map (`basic-block-sections-labels-functions-sections.ll` and
`basic-block-sections-labels.ll`)
- Removed `SHT_LLVM_BB_ADDR_MAP_V0` tests. Full deprecation of
`SHT_LLVM_BB_ADDR_MAP_V0` and `SHT_LLVM_BB_ADDR_MAP` version less than 2
will happen in a separate PR in a few months.

1 files changed, 87 insertions, 45 deletions

diff --git a/llvm/lib/Object/ELF.cpp b/llvm/lib/Object/ELF.cpp
index f24395b..137f606 100644
--- a/llvm/lib/Object/ELF.cpp
+++ b/llvm/lib/Object/ELF.cpp
@@ -693,6 +693,17 @@ decodeBBAddrMapImpl(const ELFFile<ELFT> &EF,
     for (typename ELFFile<ELFT>::Elf_Rela Rela : *Relas)
       FunctionOffsetTranslations[Rela.r_offset] = Rela.r_addend;
   }
+  auto GetAddressForRelocation =
+      [&](unsigned RelocationOffsetInSection) -> Expected<unsigned> {
+    auto FOTIterator =
+        FunctionOffsetTranslations.find(RelocationOffsetInSection);
+    if (FOTIterator == FunctionOffsetTranslations.end()) {
+      return createError("failed to get relocation data for offset: " +
+                         Twine::utohexstr(RelocationOffsetInSection) +
+                         " in section " + describe(EF, Sec));
+    }
+    return FOTIterator->second;
+  };
   Expected<ArrayRef<uint8_t>> ContentsOrErr = EF.getSectionContents(Sec);
   if (!ContentsOrErr)
     return ContentsOrErr.takeError();
@@ -704,9 +715,26 @@ decodeBBAddrMapImpl(const ELFFile<ELFT> &EF,
   Error ULEBSizeErr = Error::success();
   Error MetadataDecodeErr = Error::success();
 
+  // Helper lampda to extract the (possiblly relocatable) address stored at Cur.
+  auto ExtractAddress = [&]() -> Expected<typename ELFFile<ELFT>::uintX_t> {
+    uint64_t RelocationOffsetInSection = Cur.tell();
+    auto Address =
+        static_cast<typename ELFFile<ELFT>::uintX_t>(Data.getAddress(Cur));
+    if (!Cur)
+      return Cur.takeError();
+    if (!IsRelocatable)
+      return Address;
+    assert(Address == 0);
+    Expected<unsigned> AddressOrErr =
+        GetAddressForRelocation(RelocationOffsetInSection);
+    if (!AddressOrErr)
+      return AddressOrErr.takeError();
+    return *AddressOrErr;
+  };
+
   uint8_t Version = 0;
   uint8_t Feature = 0;
-  PGOAnalysisMap::Features FeatEnable{};
+  BBAddrMap::Features FeatEnable{};
   while (!ULEBSizeErr && !MetadataDecodeErr && Cur &&
          Cur.tell() < Content.size()) {
     if (Sec.sh_type == ELF::SHT_LLVM_BB_ADDR_MAP) {
@@ -719,11 +747,10 @@ decodeBBAddrMapImpl(const ELFFile<ELFT> &EF,
       Feature = Data.getU8(Cur); // Feature byte
       if (!Cur)
         break;
-      auto FeatEnableOrErr = PGOAnalysisMap::Features::decode(Feature);
+      auto FeatEnableOrErr = BBAddrMap::Features::decode(Feature);
       if (!FeatEnableOrErr)
         return FeatEnableOrErr.takeError();
-      FeatEnable =
-          FeatEnableOrErr ? *FeatEnableOrErr : PGOAnalysisMap::Features{};
+      FeatEnable = *FeatEnableOrErr;
       if (Feature != 0 && Version < 2 && Cur)
         return createError(
             "version should be >= 2 for SHT_LLVM_BB_ADDR_MAP when "
@@ -731,50 +758,65 @@ decodeBBAddrMapImpl(const ELFFile<ELFT> &EF,
             Twine(static_cast<int>(Version)) +
             " feature = " + Twine(static_cast<int>(Feature)));
     }
-    uint64_t SectionOffset = Cur.tell();
-    auto Address =
-        static_cast<typename ELFFile<ELFT>::uintX_t>(Data.getAddress(Cur));
-    if (!Cur)
-      return Cur.takeError();
-    if (IsRelocatable) {
-      assert(Address == 0);
-      auto FOTIterator = FunctionOffsetTranslations.find(SectionOffset);
-      if (FOTIterator == FunctionOffsetTranslations.end()) {
-        return createError("failed to get relocation data for offset: " +
-                           Twine::utohexstr(SectionOffset) + " in section " +
-                           describe(EF, Sec));
-      }
-      Address = FOTIterator->second;
-    }
-    uint32_t NumBlocks = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
-
+    uint32_t NumBlocksInBBRange = 0;
+    uint32_t NumBBRanges = 1;
+    typename ELFFile<ELFT>::uintX_t RangeBaseAddress = 0;
     std::vector<BBAddrMap::BBEntry> BBEntries;
-    uint32_t PrevBBEndOffset = 0;
-    for (uint32_t BlockIndex = 0;
-         !MetadataDecodeErr && !ULEBSizeErr && Cur && (BlockIndex < NumBlocks);
-         ++BlockIndex) {
-      uint32_t ID = Version >= 2
-                        ? readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr)
-                        : BlockIndex;
-      uint32_t Offset = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
-      uint32_t Size = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
-      uint32_t MD = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
-      if (Version >= 1) {
-        // Offset is calculated relative to the end of the previous BB.
-        Offset += PrevBBEndOffset;
-        PrevBBEndOffset = Offset + Size;
-      }
-      Expected<BBAddrMap::BBEntry::Metadata> MetadataOrErr =
-          BBAddrMap::BBEntry::Metadata::decode(MD);
-      if (!MetadataOrErr) {
-        MetadataDecodeErr = MetadataOrErr.takeError();
+    if (FeatEnable.MultiBBRange) {
+      NumBBRanges = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
+      if (!Cur || ULEBSizeErr)
         break;
+      if (!NumBBRanges)
+        return createError("invalid zero number of BB ranges at offset " +
+                           Twine::utohexstr(Cur.tell()) + " in " +
+                           describe(EF, Sec));
+    } else {
+      auto AddressOrErr = ExtractAddress();
+      if (!AddressOrErr)
+        return AddressOrErr.takeError();
+      RangeBaseAddress = *AddressOrErr;
+      NumBlocksInBBRange = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
+    }
+    std::vector<BBAddrMap::BBRangeEntry> BBRangeEntries;
+    uint32_t TotalNumBlocks = 0;
+    for (uint32_t BBRangeIndex = 0; BBRangeIndex < NumBBRanges;
+         ++BBRangeIndex) {
+      uint32_t PrevBBEndOffset = 0;
+      if (FeatEnable.MultiBBRange) {
+        auto AddressOrErr = ExtractAddress();
+        if (!AddressOrErr)
+          return AddressOrErr.takeError();
+        RangeBaseAddress = *AddressOrErr;
+        NumBlocksInBBRange = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
+      }
+      for (uint32_t BlockIndex = 0; !MetadataDecodeErr && !ULEBSizeErr && Cur &&
+                                    (BlockIndex < NumBlocksInBBRange);
+           ++BlockIndex) {
+        uint32_t ID = Version >= 2
+                          ? readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr)
+                          : BlockIndex;
+        uint32_t Offset = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
+        uint32_t Size = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
+        uint32_t MD = readULEB128As<uint32_t>(Data, Cur, ULEBSizeErr);
+        if (Version >= 1) {
+          // Offset is calculated relative to the end of the previous BB.
+          Offset += PrevBBEndOffset;
+          PrevBBEndOffset = Offset + Size;
+        }
+        Expected<BBAddrMap::BBEntry::Metadata> MetadataOrErr =
+            BBAddrMap::BBEntry::Metadata::decode(MD);
+        if (!MetadataOrErr) {
+          MetadataDecodeErr = MetadataOrErr.takeError();
+          break;
+        }
+        BBEntries.push_back({ID, Offset, Size, *MetadataOrErr});
       }
-      BBEntries.push_back({ID, Offset, Size, *MetadataOrErr});
+      TotalNumBlocks += BBEntries.size();
+      BBRangeEntries.push_back({RangeBaseAddress, std::move(BBEntries)});
     }
-    FunctionEntries.emplace_back(Address, std::move(BBEntries));
+    FunctionEntries.push_back({std::move(BBRangeEntries)});
 
-    if (PGOAnalyses || FeatEnable.anyEnabled()) {
+    if (PGOAnalyses || FeatEnable.hasPGOAnalysis()) {
       // Function entry count
       uint64_t FuncEntryCount =
           FeatEnable.FuncEntryCount
@@ -783,8 +825,8 @@ decodeBBAddrMapImpl(const ELFFile<ELFT> &EF,
 
       std::vector<PGOAnalysisMap::PGOBBEntry> PGOBBEntries;
       for (uint32_t BlockIndex = 0;
-           (FeatEnable.BBFreq || FeatEnable.BrProb) && !MetadataDecodeErr &&
-           !ULEBSizeErr && Cur && (BlockIndex < NumBlocks);
+           FeatEnable.hasPGOAnalysisBBData() && !MetadataDecodeErr &&
+           !ULEBSizeErr && Cur && (BlockIndex < TotalNumBlocks);
            ++BlockIndex) {
         // Block frequency
         uint64_t BBF = FeatEnable.BBFreq