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

[rahmanl]

Summary

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

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 25% reduction
in the size of the bb-address-map section (reduction from about 9MB to 7MB).

[jhenderson]

Seesm reasonable to me, but I don't know the codegen code well enough to be 100% confident in that aspect - might be best to try to get a second opinion.

[tmsriram]

LGTM

llvm/tools/llvm-readobj/ELFDumper.cpp

6762

Just making sure, is it possible that there could be some padding between basic blocks which might not get accounted for in size calculations? I guess this is being done after the assembler has done its work so it should be fine?

[rahmanl]

Thanks for the review @tmsriram and @jhenderson.

llvm/tools/llvm-readobj/ELFDumper.cpp

6762

Yes. The padding you are mentioning is BBE.Offset. This is the offset from the end of a block to the beginning of the next. So it will be accounted for as well (at line 6759).

[rahmanl]

rebase.

[rahmanl]

Rebase.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

void AsmPrinter::emitBBAddrMapSection(const MachineFunction &MF) {
 
   const MCSymbol *FunctionSymbol = getFunctionBegin();
 
   OutStreamer->PushSection();
   OutStreamer->SwitchSection(BBAddrMapSection);
   OutStreamer->emitSymbolValue(FunctionSymbol, getPointerSize());
   // Emit the total number of basic blocks in this function.
   OutStreamer->emitULEB128IntValue(MF.size());
+  const MCSymbol *PrevMBBEndSymbol = FunctionSymbol;
   // Emit BB Information for each basic block in the funciton.
   for (const MachineBasicBlock &MBB : MF) {
     const MCSymbol *MBBSymbol =
         MBB.isEntryBlock() ? FunctionSymbol : MBB.getSymbol();
-    // Emit the basic block offset.
-    emitLabelDifferenceAsULEB128(MBBSymbol, FunctionSymbol);
+    // Emit the basic block offset relative to the end of the previous block.
+    // This is zero unless the block is padded due to alignment.
+    emitLabelDifferenceAsULEB128(MBBSymbol, PrevMBBEndSymbol);
     // Emit the basic block size. When BBs have alignments, their size cannot
     // always be computed from their offsets.
     emitLabelDifferenceAsULEB128(MBB.getEndSymbol(), MBBSymbol);
     OutStreamer->emitULEB128IntValue(getBBAddrMapMetadata(MBB));
+    PrevMBBEndSymbol = MBB.getEndSymbol();
   }
   OutStreamer->PopSection();
 }
 
 void AsmPrinter::emitPseudoProbe(const MachineInstr &MI) {
   auto GUID = MI.getOperand(0).getImm();
   auto Index = MI.getOperand(1).getImm();
   auto Type = MI.getOperand(2).getImm();

llvm/lib/CodeGen/BasicBlockSections.cpp

 //    needs special handling with basic block sections. DebugInfo needs to be
 //    emitted with more relocations as basic block sections can break a
 //    function into potentially several disjoint pieces, and CFI needs to be
 //    emitted per cluster. This also bloats the object file and binary sizes.
 //
 // Basic Block Labels
 // ==================
 //
-// With -fbasic-block-sections=labels, we emit the offsets of BB addresses of
+// With -fbasic-block-sections=labels, we encode the offsets of BB addresses of
 // every function into the .llvm_bb_addr_map section. Along with the function
 // symbols, this allows for mapping of virtual addresses in PMU profiles back to
 // the corresponding basic blocks. This logic is implemented in AsmPrinter. This
 // pass only assigns the BBSectionType of every function to ``labels``.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/Optional.h"

llvm/test/CodeGen/X86/basic-block-sections-labels.ll

 ; UNIQ:     .section  .llvm_bb_addr_map,"o",@llvm_bb_addr_map,.text._Z3bazb{{$}}
 ;; Verify that with -unique-section-names=false, the unique id of the text section gets assigned to the llvm_bb_addr_map section.
 ; NOUNIQ:   .section  .llvm_bb_addr_map,"o",@llvm_bb_addr_map,.text,unique,1
 ; CHECK-NEXT: .quad .Lfunc_begin0
 ; CHECK-NEXT: .byte 4
 ; CHECK-NEXT: .uleb128 .Lfunc_begin0-.Lfunc_begin0
 ; CHECK-NEXT: .uleb128 .LBB_END0_0-.Lfunc_begin0
 ; CHECK-NEXT: .byte 8
-; CHECK-NEXT: .uleb128 .LBB0_1-.Lfunc_begin0
+; CHECK-NEXT: .uleb128 .LBB0_1-.LBB_END0_0
 ; CHECK-NEXT: .uleb128 .LBB_END0_1-.LBB0_1
 ; CHECK-NEXT: .byte 8
-; CHECK-NEXT: .uleb128 .LBB0_2-.Lfunc_begin0
+; CHECK-NEXT: .uleb128 .LBB0_2-.LBB_END0_1
 ; CHECK-NEXT: .uleb128 .LBB_END0_2-.LBB0_2
 ; CHECK-NEXT: .byte 1
-; CHECK-NEXT: .uleb128 .LBB0_3-.Lfunc_begin0
+; CHECK-NEXT: .uleb128 .LBB0_3-.LBB_END0_2
 ; CHECK-NEXT: .uleb128 .LBB_END0_3-.LBB0_3
 ; CHECK-NEXT: .byte 5

llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test

 # LLVM-NEXT:         Offset: 0x0
 # LLVM-NEXT:         Size: 0x1
 # LLVM-NEXT:         HasReturn: No
 # LLVM-NEXT:         HasTailCall: Yes
 # LLVM-NEXT:         IsEHPad: No
 # LLVM-NEXT:         CanFallThrough: No
 # LLVM-NEXT:       }
 # LLVM-NEXT:       {
-# LLVM-NEXT:         Offset: 0x3
+# LLVM-NEXT:         Offset: 0x4
 # LLVM-NEXT:         Size: 0x4
 # LLVM-NEXT:         HasReturn: Yes
 # LLVM-NEXT:         HasTailCall: No
 # LLVM-NEXT:         IsEHPad: Yes
 # LLVM-NEXT:         CanFallThrough: No
 # LLVM-NEXT:       }
 # LLVM-NEXT:     ]
 # LLVM-NEXT:   }

llvm/tools/llvm-readobj/ELFDumper.cpp

for (const Elf_BBAddrMap &AM : *BBAddrMapOrErr) {
         this->reportUniqueWarning(
             "could not identify function symbol for address (0x" +
             Twine::utohexstr(AM.Addr) + ") in " + this->describe(Sec));
       else
         FuncName = this->getStaticSymbolName(*FuncSymIndex);
       W.printString("Name", FuncName);
 
       ListScope L(W, "BB entries");
+      uint32_t FunctionRelativeAddress = 0;
       for (const typename Elf_BBAddrMap::BBEntry &BBE : AM.BBEntries) {
         DictScope L(W);
-        W.printHex("Offset", BBE.Offset);
+        FunctionRelativeAddress += BBE.Offset;
+        W.printHex("Offset", FunctionRelativeAddress);
         W.printHex("Size", BBE.Size);
+        FunctionRelativeAddress += BBE.Size;
         W.printBoolean("HasReturn", BBE.HasReturn);
         W.printBoolean("HasTailCall", BBE.HasTailCall);
         W.printBoolean("IsEHPad", BBE.IsEHPad);
         W.printBoolean("CanFallThrough", BBE.CanFallThrough);
       }
     }
   }
 }