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

[rahmanl]

Summary

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.

[rahmanl]

Cleanup.

[rahmanl]

Cleanup unrelated changes.

[amharc]

I think that Extensions.rst should be updated as well, including a description of the versioning scheme, the fact that the section name is now a semantically significant property, and a description of both the v0 and v1 formats.

[rahmanl]

Update Extensions.rst.

[rahmanl]

Remove empty lines.

[rahmanl]

Add unit-tests for checking invalid bb-address-map version suffixes.

[rahmanl]

In D121346#3476988, @amharc wrote:

I think that Extensions.rst should be updated as well, including a description of the versioning scheme, the fact that the section name is now a semantically significant property, and a description of both the v0 and v1 formats.

Thanks for the note. Updated Extensions.rst.

[rahmanl]

Would you mind taking a look @jhenderson?

[rahmanl]

Rebase.

[rahmanl]

Rebase again.

[jhenderson]

Has the spec for this been finalised anywhere? My main conceren is the use of section names to have semantic importance. ELF generally tries to avoid this, hence the use of section types, and it would be a shame to introduce this approach when there are other options. It would be far more preferable to include the version number in the section data somewhere, a bit like how most DWARF sections are encoded. I can think of one other possible way of doing this: change the section type value for version 1 and upwards, and rename the original value to something like SHT_LLVM_BB_ADDR_MAP_V0. Add the version field as the first N bytes (2 or 4 probably) of the new section type. Parsers understanding the old data structure only won't recognise the new section type as a recognised format. This is good because it doesn't mislead people by printing incorrect offsets (in addition to not needing to rely on the section name).

llvm/docs/Extensions.rst

404–413 ↗

(On Diff #429861)

431–432 ↗

(On Diff #429861)

Do we need a note saying that v0 BB Addr maps may not have the version suffix in the section name?

llvm/lib/Object/ELF.cpp

642

int seems like an odd type for Version. It probably should be some unsigned type?

[jhenderson]

llvm/lib/Object/ELF.cpp

645–649

Coding standards say to use lower-case for first letter of error messages.

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

75

For V1 output, I feel like it would be useful to have both the raw offset and the calculated offset printed. I'm not sure exactly what would be the best way of doing that though.

[rahmanl]

In D121346#3518196, @jhenderson wrote:

Has the spec for this been finalised anywhere? My main conceren is the use of section names to have semantic importance. ELF generally tries to avoid this, hence the use of section types, and it would be a shame to introduce this approach when there are other options. It would be far more preferable to include the version number in the section data somewhere, a bit like how most DWARF sections are encoded. I can think of one other possible way of doing this: change the section type value for version 1 and upwards, and rename the original value to something like SHT_LLVM_BB_ADDR_MAP_V0. Add the version field as the first N bytes (2 or 4 probably) of the new section type. Parsers understanding the old data structure only won't recognise the new section type as a recognised format. This is good because it doesn't mislead people by printing incorrect offsets (in addition to not needing to rely on the section name).

Thanks for the review. And apologies for my delayed followup.
We did consider several ideas for storing the version.

1. Store it for each function: wasteful for object-file size
2. Store it once in a different COMDAT section of the object file and have the linker merge them all: Would not work for mixing different versions.
3. Store it outside the section as a weak symbol. (Similar to 2).
4. Store it inside the section metadata: For example, we can suffix the section name with the version name and then have the LLVM_BB_ADDR_MAP reading code read sections of different versions.

We chose idea 4 mostly for convenience reasons.

IIUC, your suggestion is to embed the version in the section data. The problem with this approach is that the linker must read and deduplicate the version data when linking the sections (unless if we store the version for each function separately).
Also, if we compile with different compiler versions, the linker must create multiple LLVM_BB_ADDR_MAP sections if multiple versions exist.
For these reasons I am a bit hesitant to add linker dependency to the feature, even though section-name-independence is great to have. I'd be happy to change course if we can avoid involving the linker. Any thoughts?

[jhenderson]

In D121346#3574742, @rahmanl wrote:

IIUC, your suggestion is to embed the version in the section data. The problem with this approach is that the linker must read and deduplicate the version data when linking the sections (unless if we store the version for each function separately).
Also, if we compile with different compiler versions, the linker must create multiple LLVM_BB_ADDR_MAP sections if multiple versions exist.
For these reasons I am a bit hesitant to add linker dependency to the feature, even though section-name-independence is great to have. I'd be happy to change course if we can avoid involving the linker. Any thoughts?

One thing to consider is how DWARF debug sections are designed. Most DWARF sections have a format that is something akin to the following:

header consisting of:
  unit length - 32 or 64-bit number indicating the size of this input section
  version - uint16_t for the section's version
  other metadata as appropriate for the section type
actual section payload

The linker concatenates these together into a single output section. Consumers iterate over a section by inspecting the first header, using that to parse the immediate next payload and then, if the unit length doesn't mean the end of section has been reached, parses the next header and so on. In your case, you could have a single "header" (which might just consist of a length and version), followed by many functions that conform to that header. Consumers would just have to know how to iterate over them and then, if there are multiple versions, handle the corresponding payload accordingly. The linker would just concatenate together.

[rahmanl]

In D121346#3577252, @jhenderson wrote:

In D121346#3574742, @rahmanl wrote:

IIUC, your suggestion is to embed the version in the section data. The problem with this approach is that the linker must read and deduplicate the version data when linking the sections (unless if we store the version for each function separately).
Also, if we compile with different compiler versions, the linker must create multiple LLVM_BB_ADDR_MAP sections if multiple versions exist.
For these reasons I am a bit hesitant to add linker dependency to the feature, even though section-name-independence is great to have. I'd be happy to change course if we can avoid involving the linker. Any thoughts?

One thing to consider is how DWARF debug sections are designed. Most DWARF sections have a format that is something akin to the following:

header consisting of:
  unit length - 32 or 64-bit number indicating the size of this input section
  version - uint16_t for the section's version
  other metadata as appropriate for the section type
actual section payload

The linker concatenates these together into a single output section. Consumers iterate over a section by inspecting the first header, using that to parse the immediate next payload and then, if the unit length doesn't mean the end of section has been reached, parses the next header and so on. In your case, you could have a single "header" (which might just consist of a length and version), followed by many functions that conform to that header. Consumers would just have to know how to iterate over them and then, if there are multiple versions, handle the corresponding payload accordingly. The linker would just concatenate together.

Thanks for the explanation. If we use -function-sections it also means that we'll generate a unique LLVM_BB_ADDR_MAP per function. In this case, I believe the version data will be repeated for every function. Correct? I think we can live with that for now. It's only one or two bytes per function.

[jhenderson]

In D121346#3580806, @rahmanl wrote:

Thanks for the explanation. If we use -function-sections it also means that we'll generate a unique LLVM_BB_ADDR_MAP per function. In this case, I believe the version data will be repeated for every function. Correct? I think we can live with that for now. It's only one or two bytes per function.

Yes, that's what I'd expect. (It's worth noting that -function-sections imposes other overheads like the ELF section header, so a couple of bytes is comparatively small).

[rahmanl]

In D121346#3580925, @jhenderson wrote:

In D121346#3580806, @rahmanl wrote:

Thanks for the explanation. If we use -function-sections it also means that we'll generate a unique LLVM_BB_ADDR_MAP per function. In this case, I believe the version data will be repeated for every function. Correct? I think we can live with that for now. It's only one or two bytes per function.

Yes, that's what I'd expect. (It's worth noting that -function-sections imposes other overheads like the ELF section header, so a couple of bytes is comparatively small).

Correct, but with the difference that the ELF section header won't be repeated many times in the final linked section, but the version number will.

[rahmanl]

Encode the version number as a field of each function's LLVM_BB_ADDR_MAP entry instead of section names.

[rahmanl]

• Fix tests.

[rahmanl]

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

75

I think we should only care about the final calculated offset for verification. The raw offset is just an encoding technicality and should not be given much semantic importance.

[rahmanl]

• clang-format.

[jhenderson]

llvm/docs/Extensions.rst

399 ↗

(On Diff #437706)

Does this need extending?

456 ↗

(On Diff #437706)

Nit: looks like this line has gained some trailing whitespace somehow.

llvm/lib/Object/ELF.cpp

683–686

Nit: no need for braces here.

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

49–50

It would be good if these could have comments in the asm indicating what they represent (i.e. version and feature), for those not familiar with the format.

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

165

I wonder if it would be better to link against the same section? This would allow you to compare the differences more easily.

llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml

101

Typo

122

I actually think the Version field should be mandatory. It seems odd to pin the default to the oldest version, but we also shouldn't have it change when a new version is added as otherwise it'll cause existing YAML to change behaviour.

125

Nit: let's line things up.

171

Nit

llvm/tools/obj2yaml/elf2yaml.cpp

897 ↗

(On Diff #437706)

We probably should emit an error for unsupported versions. The file format may change in a future version such that the existing parsing will break in nasty ways. Same probably goes for llvm-readobj.

[rahmanl]

• Address comments

[rahmanl]

llvm/docs/Extensions.rst

399 ↗

(On Diff #437706)

I interpreted your comment as we should remove it. Did you mean we should add a separate extension for this?

llvm/lib/Object/ELF.cpp

683–686

Also removed braces elsewhere.

[jhenderson]

llvm/docs/Extensions.rst

399 ↗

(On Diff #437706)

I was referring to the underline, which didn't match the modified header length sorry for the confusion! I'm happy either way with having just the "normal" title, or both mentioned in the header.

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

61

87

This didn't occur to me until now, but it's unfortunate that we have to have duplicate check patterns and near-duplicate YAML to do the v0 comparison check. I believe we can avoid it as follows:

1. Have an additional YAML file that just describes the section, with the Type (and potentially Version) field parameterised.
2. Create two ELF objects from this YAML, one with each of the two section types, the newer type having an explicit Version 0.
3. Run llvm-readobj twice, to dump each of them individually.
4. Use the same check pattern for the pair of these invocations.

What do you think?

168

Ah, that's an unfortunate side-effect. I think we should aim to avoid it somehow. About the best idea I have for this is to use different struct types in the ELFYAML code for SHT_LLVM_BB_ADDR_MAP_V0 entries and those in SHT_LLVM_BB_ADDR_MAP sections. This also means you can't set Features when it doesn't make sense (which is a good thing).

llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml

124–126

Any particular reason you have a double space between the colon and value here and below?

[rahmanl]

• Use the same checks for SHT_LLVM_BB_ADDR_MAP (with version=0) and SHT_LLVM_BB_ADDR_MAP_V0.

[rahmanl]

Thanks for the review @jhenderson

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

168

The problem is I would have to add alternative structs for BBAddrMapSection and BBAddrMapEntry and also define new mapping functions and writeSectionContent (with mostly identical code) for the SHT_LLVM_BB_ADDR_MAP_V0 type. We should be able to fully deprecate SHT_LLVM_BB_ADDR_MAP_V0 in a few months. So maybe this test won't stay around for too long. Of course, future versions will still use the same SHT_LLVM_BB_ADDR_MAP section type and therefore, new YAML fields will be optional (even if they are required for the new versions). So we won't have a major issue. Can I keep it as is?

llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml

124–126

It should be 3 spaces because of NumBlocks being used sometime. Aligned the YAML keys in this test more carefully.

[jhenderson]

llvm/lib/Object/ELF.cpp

684–685

Test case?

Also, the type is "SHT_LLVM_BB_ADDR_MAP", so probably wants to include the SHT_ too, to match (and be consistent with other error messages)

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

13

Should we instead be including the version etc bytes? (I don't mind, just trying to understand the thought process)

35

If you're adding the comment here, I'd also add it to the other cases above (plus it makes it more robust, since it reduces the chance of spurious matches)

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

168

Yeah, leave as-is. Thanks for the explanation.

172

Nit: double blank line.

180

Super Nit: here and throughout, --check-prefixes -> --check-prefix when there's only one prefix to check (optional though - if you prefer to leave as-is, that's fine).

208

Nit: spurious extra line?

llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml

124–126

FWIW, I only align within the individual block, so here, I'd align with only the single space, and then use 3 spaces where NumBlocks is present. I don't care really though, as long as the spacing doesn't get excessive (at which point it can make readability an issue).

llvm/test/tools/yaml2obj/ELF/bb-addr-map.yaml

79–81 ↗

(On Diff #438764)

Nit: these should line up.

136 ↗

(On Diff #438764)

Nit: this should line up.

142 ↗

(On Diff #438764)

Nit: for consistent formatting, add a blank line before the YAML.

[rahmanl]

• Cleanups.

[rahmanl]

• Cleanups.

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

13

You're right. We can do that.

llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml

124–126

Thanks. Adopted your approach.

[rahmanl]

• Cleanups.

[rahmanl]

• Cleanups.

[jhenderson]

llvm/lib/Object/ELF.cpp

684–685

Looks like there's still no test case?

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

152

FWIW, there are still 2 spaces here, rather than just 1.

[rahmanl]

• Cleanups.

llvm/lib/Object/ELF.cpp

684–685

Sorry, my response wasn't sent: I can't add a test to exercise this because I can't make a valid Yaml with an unsupported version number (ELFEmitter.cpp returns error if I specify version> 1), but I also don't think it's a good idea to remove that error handling. What do you suggest?

[jhenderson]

llvm/lib/Object/ELF.cpp

684–685

Hmm, good point. What do you think about the following proposal:

1. Emit a warning rather than an error with yaml2obj.
2. In this case, treat it as the max supported version (i.e. 1) and generate data like that, except with a value 2 for the Version field.

YAML is really only used for testing, so emitting an error blocks us from testing the actual production code we want to test, which seems unfortunate!

The alternative approach would be to use assembly, right?

[rahmanl]

• Add a llvm-readobj unit test with unsupported versions.

llvm/lib/Object/ELF.cpp

684–685

Done. Thanks for the suggestion.

[jhenderson]

Two nits, otherwise LGTM.

llvm/lib/ObjectYAML/ELFEmitter.cpp

1401 ↗

(On Diff #440457)

Nit: semi-colon rather than comma is probably more correct

llvm/test/tools/yaml2obj/ELF/bb-addr-map.yaml

138 ↗

(On Diff #440457)

[rahmanl]

• Final nits.

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/lib/MC/MCObjectFileInfo.cpp

MCObjectFileInfo::getBBAddrMapSection(const MCSection &TextSec) const {
   StringRef GroupName;
   if (const MCSymbol *Group = ElfSec.getGroup()) {
     GroupName = Group->getName();
     Flags |= ELF::SHF_GROUP;
   }
 
   // Use the text section's begin symbol and unique ID to create a separate
   // .llvm_bb_addr_map section associated with every unique text section.
-  return Ctx->getELFSection(".llvm_bb_addr_map", ELF::SHT_LLVM_BB_ADDR_MAP,
+  return Ctx->getELFSection(".llvm_bb_addr_map.v1", ELF::SHT_LLVM_BB_ADDR_MAP,
                             Flags, 0, GroupName, true, ElfSec.getUniqueID(),
                             cast<MCSymbolELF>(TextSec.getBeginSymbol()));
 }
 
 MCSection *
 MCObjectFileInfo::getPseudoProbeSection(const MCSection *TextSec) const {
   if (Ctx->getObjectFileType() == MCContext::IsELF) {
     const auto *ElfSec = static_cast<const MCSectionELF *>(TextSec);

llvm/lib/Object/ELF.cpp

return createError("can't map virtual address 0x" +
                        Twine::utohexstr(getBufSize()) + ")");
 
   return base() + Offset;
 }
 
 template <class ELFT>
 Expected<std::vector<BBAddrMap>>
 ELFFile<ELFT>::decodeBBAddrMap(const Elf_Shdr &Sec) const {
+  Expected<StringRef> SectionNameOrErr = getSectionName(Sec);
+  if (!SectionNameOrErr)
+    return SectionNameOrErr.takeError();
+  StringRef VersionStr = SectionNameOrErr->rsplit('.').second;
+  int Version = 0;
+  if (!VersionStr.empty() && VersionStr.startswith("v")) {
+    if (VersionStr.substr(1).getAsInteger(10, Version))
+      return createError("Unable to parse bb-address-map version suffix: " +
+                         VersionStr);
+    if (Version > 1)
+      return createError("Unsupported bb-address-map version: " +
+                         Twine(Version));
+  }
   Expected<ArrayRef<uint8_t>> ContentsOrErr = getSectionContents(Sec);
   if (!ContentsOrErr)
     return ContentsOrErr.takeError();
   ArrayRef<uint8_t> Content = *ContentsOrErr;
   DataExtractor Data(Content, isLE(), ELFT::Is64Bits ? 8 : 4);
   std::vector<BBAddrMap> FunctionEntries;
 
   DataExtractor::Cursor Cur(0);
   Error ULEBSizeErr = Error::success();
auto ReadULEB128AsUInt32 = [&Data, &Cur, &ULEBSizeErr]() -> uint32_t {
     }
     return static_cast<uint32_t>(Value);
   };
 
   while (!ULEBSizeErr && Cur && Cur.tell() < Content.size()) {
     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});
   }
   // Either Cur is in the error state, or ULEBSizeError is set (not both), but
   // we join the two errors here to be safe.
   if (!Cur || ULEBSizeErr)
     return joinErrors(Cur.takeError(), std::move(ULEBSizeErr));
   return FunctionEntries;
 }
 
 template class llvm::object::ELFFile<ELF32LE>;
 template class llvm::object::ELFFile<ELF32BE>;
 template class llvm::object::ELFFile<ELF64LE>;
 template class llvm::object::ELFFile<ELF64BE>;

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

 
 define void @func() {
 entry:
   ret void
 }
 
 ; CHECK:  func:
 ; CHECK:  .Lfunc_begin1:
-; CHECK:    .section  .llvm_bb_addr_map,"o",@llvm_bb_addr_map,.text{{$}}
+; CHECK:    .section  .llvm_bb_addr_map.v1,"o",@llvm_bb_addr_map,.text{{$}}
 ; CHECK:    .quad .Lfunc_begin1

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

 ; RUN: llc < %s -mtriple=x86_64 -function-sections -basic-block-sections=labels | FileCheck %s
 
 $_Z4fooTIiET_v = comdat any
 
 define dso_local i32 @_Z3barv() {
   ret i32 0
 }
 ;; Check we add SHF_LINK_ORDER for .llvm_bb_addr_map and link it with the corresponding .text sections.
 ; CHECK:    .section .text._Z3barv,"ax",@progbits
 ; CHECK-LABEL:  _Z3barv:
 ; CHECK-NEXT: [[BAR_BEGIN:.Lfunc_begin[0-9]+]]:
-; CHECK:    .section .llvm_bb_addr_map,"o",@llvm_bb_addr_map,.text._Z3barv{{$}}
+; CHECK:    .section .llvm_bb_addr_map.v1,"o",@llvm_bb_addr_map,.text._Z3barv{{$}}
 ; CHECK-NEXT:   .quad [[BAR_BEGIN]]
 
 
 define dso_local i32 @_Z3foov() {
   %1 = call i32 @_Z4fooTIiET_v()
   ret i32 %1
 }
 ; CHECK:    .section .text._Z3foov,"ax",@progbits
 ; CHECK-LABEL:  _Z3foov:
 ; CHECK-NEXT: [[FOO_BEGIN:.Lfunc_begin[0-9]+]]:
-; CHECK:    .section  .llvm_bb_addr_map,"o",@llvm_bb_addr_map,.text._Z3foov{{$}}
+; CHECK:    .section  .llvm_bb_addr_map.v1,"o",@llvm_bb_addr_map,.text._Z3foov{{$}}
 ; CHECK-NEXT:   .quad [[FOO_BEGIN]]
 
 
 define linkonce_odr dso_local i32 @_Z4fooTIiET_v() comdat {
   ret i32 0
 }
 ;; Check we add .llvm_bb_addr_map section to a COMDAT group with the corresponding .text section if such a COMDAT exists.
 ; CHECK:    .section .text._Z4fooTIiET_v,"axG",@progbits,_Z4fooTIiET_v,comdat
 ; CHECK-LABEL:  _Z4fooTIiET_v:
 ; CHECK-NEXT: [[FOOCOMDAT_BEGIN:.Lfunc_begin[0-9]+]]:
-; CHECK:    .section .llvm_bb_addr_map,"Go",@llvm_bb_addr_map,_Z4fooTIiET_v,comdat,.text._Z4fooTIiET_v{{$}}
+; CHECK:    .section .llvm_bb_addr_map.v1,"Go",@llvm_bb_addr_map,_Z4fooTIiET_v,comdat,.text._Z4fooTIiET_v{{$}}
 ; CHECK-NEXT:   .quad [[FOOCOMDAT_BEGIN]]

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

 ; CHECK-LABEL:  .LBB0_1:
 ; CHECK-LABEL:  .LBB_END0_1:
 ; CHECK-LABEL:  .LBB0_2:
 ; CHECK-LABEL:  .LBB_END0_2:
 ; CHECK-LABEL:  .LBB0_3:
 ; CHECK-LABEL:  .LBB_END0_3:
 ; CHECK-LABEL:  .Lfunc_end0:
 
-; UNIQ:     .section  .llvm_bb_addr_map,"o",@llvm_bb_addr_map,.text._Z3bazb{{$}}
+; UNIQ:     .section  .llvm_bb_addr_map.v1,"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
+; NOUNIQ:   .section  .llvm_bb_addr_map.v1,"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

 ## This test checks how we handle the --bb-addr-map option.
 
-# Check 64-bit:
+## Check 64-bit (version #0 encoding):
 # RUN: yaml2obj %s -DBITS=64 -DADDR=0x999999999 -o %t1.x64.o
-# RUN: llvm-readobj %t1.x64.o --bb-addr-map 2>&1 | FileCheck %s -DADDR=0x999999999 -DFILE=%t1.x64.o --check-prefix=LLVM
-
+# RUN: llvm-readobj %t1.x64.o --bb-addr-map 2>&1 | FileCheck %s -DADDR=0x999999999 -DFILE=%t1.x64.o --check-prefixes=CHECK,V0
 # RUN: llvm-readelf %t1.x64.o --bb-addr-map | FileCheck %s --check-prefix=GNU
 
+## Check 64-bit (version #1 encoding):
+# RUN: yaml2obj %s -DBITS=64 -DVERSION=1 -DADDR=0x999999999 -o %t1.v1.x64.o
+# RUN: llvm-readobj %t1.v1.x64.o --bb-addr-map 2>&1 | FileCheck %s -DADDR=0x999999999 -DFILE=%t1.v1.x64.o --check-prefixes=CHECK,V1
+
 ## Check 32-bit:
 # RUN: yaml2obj %s -DBITS=32 -o %t1.x32.o
-# RUN: llvm-readobj %t1.x32.o --bb-addr-map 2>&1 | FileCheck -DADDR=0x11111 %s -DFILE=%t1.x32.o --check-prefix=LLVM
+# RUN: llvm-readobj %t1.x32.o --bb-addr-map 2>&1 | FileCheck -DADDR=0x11111 %s -DFILE=%t1.x32.o --check-prefixes=CHECK,V0
 # RUN: llvm-readelf %t1.x32.o --bb-addr-map | FileCheck %s --check-prefix=GNU
 
 ## Check that a malformed section can be handled.
 # RUN: yaml2obj %s -DBITS=32 -DSIZE=4 -o %t2.o
 # RUN: llvm-readobj %t2.o --bb-addr-map 2>&1 | FileCheck %s -DOFFSET=0x00000004 -DFILE=%t2.o --check-prefix=TRUNCATED
 
-# LLVM:      BBAddrMap [
-# LLVM-NEXT:   Function {
-# LLVM-NEXT:     At: [[ADDR]]
-# LLVM-NEXT: warning: '[[FILE]]': could not identify function symbol for address ([[ADDR]]) in SHT_LLVM_BB_ADDR_MAP section with index 3
-# LLVM-NEXT:     Name: <?>
-# LLVM-NEXT:     BB entries [
-# LLVM-NEXT:       {
-# 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:         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-NEXT:   Function {
-# LLVM-NEXT:     At: 0x22222
-# LLVM-NEXT:     Name: foo
-# LLVM-NEXT:     BB entries [
-# LLVM-NEXT:       {
-# LLVM-NEXT:         Offset: 0x6
-# LLVM-NEXT:         Size: 0x7
-# LLVM-NEXT:         HasReturn: No
-# LLVM-NEXT:         HasTailCall: No
-# LLVM-NEXT:         IsEHPad: No
-# LLVM-NEXT:         CanFallThrough: Yes
-# LLVM-NEXT:       }
-# LLVM-NEXT:     ]
-# LLVM-NEXT:   }
-# LLVM-NEXT: ]
-# LLVM-NEXT: BBAddrMap [
-# LLVM-NEXT:   Function {
-# LLVM-NEXT:     At: 0x33333
-# LLVM-NEXT:     Name: bar
-# LLVM-NEXT:     BB entries [
-# LLVM-NEXT:       {
-# LLVM-NEXT:         Offset: 0x9
-# LLVM-NEXT:         Size: 0xA
-# LLVM-NEXT:         HasReturn: Yes
-# LLVM-NEXT:         HasTailCall: Yes
-# LLVM-NEXT:         IsEHPad: No
-# LLVM-NEXT:         CanFallThrough: Yes
-# LLVM-NEXT:       }
-# LLVM-NEXT:     ]
-# LLVM-NEXT:   }
-# LLVM-NEXT: ]
+# CHECK:      BBAddrMap [
+# CHECK-NEXT:   Function {
+# CHECK-NEXT:     At: [[ADDR]]
+# CHECK-NEXT: warning: '[[FILE]]': could not identify function symbol for address ([[ADDR]]) in SHT_LLVM_BB_ADDR_MAP section with index 3
+# CHECK-NEXT:     Name: <?>
+# CHECK-NEXT:     BB entries [
+# CHECK-NEXT:       {
+# CHECK-NEXT:         Offset: 0x0
+# CHECK-NEXT:         Size: 0x1
+# CHECK-NEXT:         HasReturn: No
+# CHECK-NEXT:         HasTailCall: Yes
+# CHECK-NEXT:         IsEHPad: No
+# CHECK-NEXT:         CanFallThrough: No
+# CHECK-NEXT:       }
+# CHECK-NEXT:       {
+# CHECK-NEXT:         Offset: 0x3
+# CHECK-NEXT:         Size: 0x4
+# CHECK-NEXT:         HasReturn: Yes
+# CHECK-NEXT:         HasTailCall: No
+# CHECK-NEXT:         IsEHPad: Yes
+# CHECK-NEXT:         CanFallThrough: No
+# CHECK-NEXT:       }
+# CHECK-NEXT:     ]
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Function {
+# CHECK-NEXT:     At: 0x22222
+# CHECK-NEXT:     Name: foo
+# CHECK-NEXT:     BB entries [
+# CHECK-NEXT:       {
+# CHECK-NEXT:         Offset: 0x6
+# CHECK-NEXT:         Size: 0x7
+# CHECK-NEXT:         HasReturn: No
+# CHECK-NEXT:         HasTailCall: No
+# CHECK-NEXT:         IsEHPad: No
+# CHECK-NEXT:         CanFallThrough: Yes
+# CHECK-NEXT:       }
+# CHECK-NEXT:     ]
+# CHECK-NEXT:   }
+# CHECK-NEXT: ]
+# CHECK-NEXT: BBAddrMap [
+# CHECK-NEXT:   Function {
+# CHECK-NEXT:     At: 0x33333
+# CHECK-NEXT:     Name: bar
+# CHECK-NEXT:     BB entries [
+# CHECK-NEXT:       {
+# CHECK-NEXT:         Offset: 0x9
+# CHECK-NEXT:         Size: 0xA
+# CHECK-NEXT:         HasReturn: Yes
+# CHECK-NEXT:         HasTailCall: Yes
+# CHECK-NEXT:         IsEHPad: No
+# CHECK-NEXT:         CanFallThrough: Yes
+# CHECK-NEXT:       }
+# CHECK-NEXT:       {
+# V0-NEXT:            Offset: 0xC
+# V1-NEXT:            Offset: 0x1F
+# CHECK-NEXT:         Size: 0xD
+# CHECK-NEXT:         HasReturn: No
+# CHECK-NEXT:         HasTailCall: Yes
+# CHECK-NEXT:         IsEHPad: Yes
+# CHECK-NEXT:         CanFallThrough: Yes
+# CHECK-NEXT:       }
+# CHECK-NEXT:     ]
+# CHECK-NEXT:   }
+# CHECK-NEXT: ]
 
 # GNU: GNUStyle::printBBAddrMaps not implemented
 
 # TRUNCATED:      BBAddrMap [
 # TRUNCATED-NEXT:   warning: '[[FILE]]': unable to dump SHT_LLVM_BB_ADDR_MAP section with index 3: unable to decode LEB128 at offset [[OFFSET]]: malformed uleb128, extends past end
 # TRUNCATED-NEXT: ]
 ## Check that the other valid section is properly dumped.
 # TRUNCATED-NEXT: BBAddrMap [
 # TRUNCATED-NEXT:   Function {
 # TRUNCATED-NEXT:     At: 0x33333
 # TRUNCATED-NEXT:     Name: bar
 # TRUNCATED-NEXT:     BB entries [
 # TRUNCATED-NEXT:       {
 # TRUNCATED-NEXT:         Offset: 0x9
 # TRUNCATED-NEXT:         Size: 0xA
 # TRUNCATED-NEXT:         HasReturn: Yes
 # TRUNCATED-NEXT:         HasTailCall: Yes
 # TRUNCATED-NEXT:         IsEHPad: No
 # TRUNCATED-NEXT:         CanFallThrough: Yes
 # TRUNCATED-NEXT:       }
+# TRUNCATED-NEXT:       {
+# TRUNCATED-NEXT:         Offset: 0xC
+# TRUNCATED-NEXT:         Size: 0xD
+# TRUNCATED-NEXT:         HasReturn: No
+# TRUNCATED-NEXT:         HasTailCall: Yes
+# TRUNCATED-NEXT:         IsEHPad: Yes
+# TRUNCATED-NEXT:         CanFallThrough: Yes
+# TRUNCATED-NEXT:       }
 # TRUNCATED-NEXT:     ]
 # TRUNCATED-NEXT:   }
 # TRUNCATED-NEXT: ]
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS[[BITS]]
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
   - Name:   .text
     Type:   SHT_PROGBITS
     Flags:  [SHF_ALLOC]
   - Name:   .text.bar
     Type:   SHT_PROGBITS
     Flags:  [SHF_ALLOC]
-  - Name:   bb_addr_map_1
+  - Name:   bb_addr_map
     Type:   SHT_LLVM_BB_ADDR_MAP
     ShSize: [[SIZE=<none>]]
     Link:   .text
     Entries:
       - Address: [[ADDR=0x11111]]
         BBEntries:
           - AddressOffset: 0x0
             Size:          0x1
             Metadata:      0xF0000002
           - AddressOffset: 0x3
             Size:          0x4
             Metadata:      0x5
       - Address: 0x22222
         BBEntries:
           - AddressOffset: 0x6
             Size:          0x7
             Metadata:      0x8
   - Name:   dummy_section
     Type:   SHT_PROGBITS
     Size:   16
-  - Name:   bb_addr_map_2
+  - Name:   bb_addr_map.v[[VERSION=0]]
     Type:   SHT_LLVM_BB_ADDR_MAP
     Link:   .text.bar
     Entries:
       - Address: 0x33333
         BBEntries:
           - AddressOffset: 0x9
             Size:          0xa
             Metadata:      0xb
+          - AddressOffset: 0xc
+            Size:          0xd
+            Metadata:      0xe
 Symbols:
   - Name:    foo
     Section: .text
     Type:    STT_FUNC
     Value:   0x22222
   - Name:    bar
     Section: .text.bar
     Type:    STT_FUNC
     Value:   0x33333

llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml

 # VALID-NEXT:             Metadata:         0xC
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
-  - Name:    .llvm_bb_addr_map
+  - Name:    .llvm_bb_addr_map.v2
     Type:    SHT_LLVM_BB_ADDR_MAP
     ShSize:    [[SIZE=<none>]]
     Entries:
       - Address:   0x0
         NumBlocks: [[NUMBLOCKS=<none>]]
         BBEntries:
           - AddressOffset:    0x1
             Size:             0x2

 # MULTI-NEXT: FileHeader:
 # MULTI-NEXT:   Class: ELFCLASS64
 # MULTI-NEXT:   Data:  ELFDATA2LSB
 # MULTI-NEXT:   Type:  ET_EXEC
 # MULTI-NEXT: Sections:
 # MULTI-NEXT:   - Name:    .llvm_bb_addr_map
 # MULTI-NEXT:     Type:    SHT_LLVM_BB_ADDR_MAP
 # MULTI-NEXT:     Entries:
 ## The 'Address' field is omitted when it's zero.
 # MULTI-NEXT:       - BBEntries:
 # MULTI-NEXT:           - AddressOffset:    0x1
 # MULTI-NEXT:             Size:             0x2
 # MULTI-NEXT:             Metadata:         0x3
 # MULTI-NEXT:   - Name:    '.llvm_bb_addr_map (1)'
 # MULTI-NEXT:     Type:    SHT_LLVM_BB_ADDR_MAP
 # MULTI-NEXT:     Entries:
 # MULTI-NEXT:       - Address: 0x20
 # MULTI-NEXT:         BBEntries: []
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
   - Name:    .llvm_bb_addr_map
     Type:    SHT_LLVM_BB_ADDR_MAP
     Entries:
 ## Check that obj2yaml does not emit the Address field when it's zero.
       - Address:   0x0
         BBEntries:
           - AddressOffset:    0x1
             Size:             0x2
             Metadata:         0x3
   - Name:    '.llvm_bb_addr_map (1)'
     Type:    SHT_LLVM_BB_ADDR_MAP
     Entries:
       - Address:   0x20
 
 ## Check that obj2yaml uses the "Content" tag to describe an .llvm_bb_addr_map section
 ## when it can't extract the entries, for example, when the section is truncated, or
 ## when an invalid 'NumBlocks' field is specified.
 
 # RUN: yaml2obj --docnum=1 -DSIZE=0x8 %s -o %t4
 # RUN: obj2yaml %t4 | FileCheck %s --check-prefixes=TRUNCATED,INVALID
 
 # RUN: yaml2obj --docnum=1 -DNUMBLOCKS=2 %s -o %t5
 # RUN: obj2yaml %t5 | FileCheck %s --check-prefixes=BADNUMBLOCKS,INVALID
 
 # INVALID:           --- !ELF
 # INVALID-NEXT:      FileHeader:
 # INVALID-NEXT:        Class:   ELFCLASS64
 # INVALID-NEXT:        Data:    ELFDATA2LSB
 # INVALID-NEXT:        Type:    ET_EXEC
 # INVALID-NEXT:      Sections:
 # INVALID-NEXT:        - Name: .llvm_bb_addr_map
 # INVALID-NEXT:          Type: SHT_LLVM_BB_ADDR_MAP
 # BADNUMBLOCKS-NEXT:     Content: {{([[:xdigit:]]+)}}{{$}}
 # TRUNCATED-NEXT:        Content: '{{([[:xdigit:]]{16})}}'{{$}}

llvm/unittests/Object/ELFObjectFileTest.cpp

 TEST(ELFObjectFileTest, InvalidBBAddrMap) {
   StringRef CommonYamlString(R"(
 --- !ELF
 FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
-  - Name: .llvm_bb_addr_map
+  - Name: llvm_bb_addr_map
     Type: SHT_LLVM_BB_ADDR_MAP
     Entries:
       - Address: 0x11111
         BBEntries:
           - AddressOffset: 0x0
             Size:          0x1
             Metadata:      0x2
 )");