[Propeller] Encode address offsets of basic blocks relative to the end of the previous basic blocks.

This is a resurrection of D106421 with the change that it keeps backward-compatibility. This means decoding the previous version of `LLVM_BB_ADDR_MAP` will work. This is required as the profile mapping tool is not released with LLVM (AutoFDO). As suggested by @jhenderson we rename the original  section type value to `SHT_LLVM_BB_ADDR_MAP_V0` and assign a new value to the `SHT_LLVM_BB_ADDR_MAP` section type. The new encoding adds a version byte to each function entry to specify the encoding version for that function.  This patch also adds a feature byte to be used with more flexibility in the future. An use-case example for the feature field is encoding multi-section functions more concisely using a different format.

Conceptually, the new encoding emits basic block offsets and sizes as label differences between each two consecutive basic block begin and end label. When decoding, offsets must be aggregated along with basic block sizes to calculate the final offsets of basic blocks relative to the function address.

This encoding uses smaller values compared to the existing one (offsets relative to function symbol).
Smaller values tend to occupy fewer bytes in ULEB128 encoding. As a result, we get about 17% total reduction in the size of the bb-address-map section (from about 11MB to 9MB for the clang PGO binary).
The extra two bytes (version and feature fields) incur a small 3% size overhead to the `LLVM_BB_ADDR_MAP` section size.

Reviewed By: jhenderson

Differential Revision: https://reviews.llvm.org/D121346

1 files changed, 18 insertions, 2 deletions

diff --git a/llvm/lib/Object/ELF.cpp b/llvm/lib/Object/ELF.cpp
index bcef7ce..6acf454 100644
--- a/llvm/lib/Object/ELF.cpp
+++ b/llvm/lib/Object/ELF.cpp
@@ -295,6 +295,7 @@ StringRef llvm::object::getELFSectionTypeName(uint32_t Machine, unsigned Type) {
     STRINGIFY_ENUM_CASE(ELF, SHT_LLVM_SYMPART);
     STRINGIFY_ENUM_CASE(ELF, SHT_LLVM_PART_EHDR);
     STRINGIFY_ENUM_CASE(ELF, SHT_LLVM_PART_PHDR);
+    STRINGIFY_ENUM_CASE(ELF, SHT_LLVM_BB_ADDR_MAP_V0);
     STRINGIFY_ENUM_CASE(ELF, SHT_LLVM_BB_ADDR_MAP);
     STRINGIFY_ENUM_CASE(ELF, SHT_GNU_ATTRIBUTES);
     STRINGIFY_ENUM_CASE(ELF, SHT_GNU_HASH);
@@ -640,7 +641,6 @@ ELFFile<ELFT>::decodeBBAddrMap(const Elf_Shdr &Sec) const {
 
   DataExtractor::Cursor Cur(0);
   Error ULEBSizeErr = Error::success();
-
   // Helper to extract and decode the next ULEB128 value as uint32_t.
   // Returns zero and sets ULEBSizeErr if the ULEB128 value exceeds the uint32_t
   // limit.
@@ -660,18 +660,34 @@ ELFFile<ELFT>::decodeBBAddrMap(const Elf_Shdr &Sec) const {
     return static_cast<uint32_t>(Value);
   };
 
+  uint8_t Version = 0;
   while (!ULEBSizeErr && Cur && Cur.tell() < Content.size()) {
+    if (Sec.sh_type == ELF::SHT_LLVM_BB_ADDR_MAP) {
+      Version = Data.getU8(Cur);
+      if (!Cur)
+        break;
+      if (Version > 1)
+        return createError("unsupported SHT_LLVM_BB_ADDR_MAP version: " +
+                           Twine(static_cast<int>(Version)));
+      Data.getU8(Cur); // Feature byte
+    }
     uintX_t Address = static_cast<uintX_t>(Data.getAddress(Cur));
     uint32_t NumBlocks = ReadULEB128AsUInt32();
     std::vector<BBAddrMap::BBEntry> BBEntries;
+    uint32_t PrevBBEndOffset = 0;
     for (uint32_t BlockID = 0; !ULEBSizeErr && Cur && (BlockID < NumBlocks);
          ++BlockID) {
       uint32_t Offset = ReadULEB128AsUInt32();
       uint32_t Size = ReadULEB128AsUInt32();
       uint32_t Metadata = ReadULEB128AsUInt32();
+      if (Version >= 1) {
+        // Offset is calculated relative to the end of the previous BB.
+        Offset += PrevBBEndOffset;
+        PrevBBEndOffset = Offset + Size;
+      }
       BBEntries.push_back({Offset, Size, Metadata});
     }
-    FunctionEntries.push_back({Address, BBEntries});
+    FunctionEntries.push_back({Address, std::move(BBEntries)});
   }
   // Either Cur is in the error state, or ULEBSizeError is set (not both), but
   // we join the two errors here to be safe.