[Propeller] Use Fixed MBB ID instead of volatile MachineBasicBlock::Number.

[rahmanl]

Summary

Let Propeller use specialized IDs for basic blocks, instead of MBB number.

This allows optimizations not just prior to asm-printer, but throughout the entire codegen.
This patch only implements the functionality under the new LLVM_BB_ADDR_MAP version, but the old version is still being used. A later patch will change the used version.

Background

Today Propeller uses machine basic block (MBB) numbers, which already exist, to map native assembly to machine IR. This is done as follows.

• Basic block addresses are captured and dumped into the LLVM_BB_ADDR_MAP section just before the AsmPrinter pass which writes out object files. This ensures that we have a mapping that is close to assembly.
• Profiling mapping works by taking a virtual address of an instruction and looking up the LLVM_BB_ADDR_MAP section to find the MBB number it corresponds to.
• While this works well today, we need to do better when we scale Propeller to target other Machine IR optimizations like spill code optimization. Register allocation happens earlier in the Machine IR pipeline and we need an annotation mechanism that is valid at that point.
• The current scheme will not work in this scenario because the MBB number of a particular basic block is not fixed and changes over the course of codegen (via renumbering, adding, and removing the basic blocks).
• In other words, the volatile MBB numbers do not provide a one-to-one correspondence throughout the lifetime of Machine IR. Profile annotation using MBB numbers is restricted to a fixed point; only valid at the exact point where it was dumped.
• Further, the object file can only be dumped before AsmPrinter and cannot be dumped at an arbitrary point in the Machine IR pass pipeline. Hence, MBB numbers are not suitable and we need something else.

Solution

We propose using fixed unique incremental MBB IDs for basic blocks instead of volatile MBB numbers. These IDs are assigned upon the creation of machine basic blocks. We modify MachineFunction::CreateMachineBasicBlock to assign the fixed ID to every newly created basic block. It assigns MachineFunction::NextMBBID to the MBB ID and then increments it, which ensures having unique IDs.

To ensure correct profile attribution, multiple equivalent compilations must generate the same Propeller IDs. This is guaranteed as long as the MachineFunction passes run in the same order. Since the NextBBID variable is scoped to MachineFunction, interleaving of codegen for different functions won't cause any inconsistencies.

The new encoding is generated under the new version number 2 and we keep backward-compatibility with older versions.

Impact on Size of the LLVM_BB_ADDR_MAP Section

Emitting the Propeller ID results in a 23% increase in the size of the LLVM_BB_ADDR_MAP section for the clang binary.

[rahmanl]

Refactoring.

[rahmanl]

• Fix tests.

[rahmanl]

• Fix tests.
• Add support for MIR printing and parsing.

[rahmanl]

Rebase.

[rahmanl]

Fix clang-tidy warnings.

[rahmanl]

Add comments/Variable renaming.

[jhenderson]

CodeGen isn't really my thing, so I can't really review that side of things. The dumping/yaml2obj etc changes all seem fine, assuming the proposal as a whole is acceptable.

One thought I had: I was (perhaps incorrectly) under the impression that Propeller is something external to LLVM. It seems a bit backwards to be referring to it by name throughout this change, via code comments and variable names etc. Would it make more sense to use simply "ID" or something like "FixedID" or similar?

llvm/include/llvm/CodeGen/MachineBasicBlock.h

172

llvm/lib/CodeGen/MIRParser/MIParser.cpp

666

[rahmanl]

Rebase.

[rahmanl]

• Change PropellerID to BBID.

[rahmanl]

• clang-format.

[rahmanl]

• clang-format.

[rahmanl]

@jhenderson Thanks for the early review. The patch is ready for review again.

[rahmanl]

• Fix test.

[jhenderson]

llvm/include/llvm/CodeGen/BasicBlockSectionsProfileReader.h

34–35

Is this comment still accurate? (It might be, I don't know).

llvm/lib/CodeGen/BasicBlockSections.cpp

188

Nit: this is not the LLVM naming style convention. The old name (as was in the original diff, and changed in an intermediate commit somewhere) was correct style. Since you're modifying this area of code, let's fix it.

218–219

[rahmanl]

• Address comments.

[jhenderson]

No more comments from me, thanks.

[rahmanl]

In D100808#3854974, @jhenderson wrote:

No more comments from me, thanks.

I appreciate the review @jhenderson

llvm/lib/CodeGen/BasicBlockSections.cpp

218–219

Changed the comment as it doesn't hold anymore.

[rahmanl]

• report error instead of assertions if entry block is displaced.

[rahmanl]

• report error instead of assertions if entry block is displaced.

[jhenderson]

llvm/lib/CodeGen/BasicBlockSections.cpp

260–263

Why report_fatal_error here? If this case can be hit by proper user code, should the error by propagated up to the call site? If not, why not an assertion?

[rahmanl]

• Changed check back to assert.
• Changed the emitted BB address map version back to 1.

[rahmanl]

clang-format.

[rahmanl]

clang-format.

[rahmanl]

• clang-format.

[rahmanl]

In order to stage this, I changed this to emit the old version. I will need to submit another patch once the llvm is integrated into our create_llvm_prof tooling.

llvm/lib/CodeGen/BasicBlockSections.cpp

260–263

This is a hard failure and is not expected to happen. I changed to report_fatal_error to suppress the unused variable warning, but now I know I can used [[maybe_unused]] to do this.

[rahmanl]

• Changed the emitted BB address map version back to 1.

[rahmanl]

• Changed the emitted BB address map version back to 1.

[rahmanl]

• Rebase.

[jhenderson]

llvm/lib/CodeGen/BasicBlockSections.cpp

335

The note is unnecessary, since you've stated the same at the start of the comment.

[rahmanl]

Refactoring and changing data structures.

[tmsriram]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1363

It is okay to maintain both versions for now but we should deprecate the old version after some time, say 6 months? Can we add "TODOs" on code that should be deleted when that happens?

llvm/lib/CodeGen/BasicBlockSections.cpp

188

Please fix this too.

223

Add a TODO here to replace this with getBBID() when version 1 is deprecated.

256

Why did you remove the 4 here?

329

Please explicitly state the different purpose here and identify the comment block that needs to be deleted.

346

extra line.

llvm/lib/CodeGen/MachineBasicBlock.cpp

1654

TODO to replace all uses of this function with getBBID() when deprecated.

llvm/lib/CodeGen/MachineFunction.cpp

443

Please add a comment here on why this is needed.

[rahmanl]

Remove redundant new line.

[rahmanl]

Remove unused include.

[rahmanl]

• Address comments.

[tmsriram]

LGTM. Please make sure all reviewers have approved the patch.

I want to add that this is a strong motivation to make Propeller's profile conversion tool a part of LLVM. This would get rid of the need to maintain multiple versions.

llvm/lib/CodeGen/BasicBlockSections.cpp

188

Rename BBID and BBCI / make sure it adheres to naming style convention.

223

Please fix this too.

[rahmanl]

• Final comments.

[rahmanl]

Thanks Sri.

llvm/lib/CodeGen/BasicBlockSections.cpp

188

I think they adhere to the naming convention. James's original comment was about bbClusterInfo.

223

Added a single TODO in MachineBasicBlock.h.

256

This vector is allocated based on number of the blocks in sortBasicBlocksAndUpdateBranches.

llvm/lib/CodeGen/MachineBasicBlock.cpp

1654

Added TODO in the header file.

[hokein]

This patch seems to break a build for one of our targets, I will share more details with you internally.

[ashay-github]

Hello! It seems this patch breaks tests on Windows builds. For instance, at my end, the test in llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml produces AddressOffset: 0x2 instead of the expected AddressOffset: 0x1. The same test in Linux completes successfully.

It's possible that because the Phabricator instance does not add -DLLVM_INCLUDE_TOOLS=ON to the CMake invocation, we failed to catch this issue in CI. I can reproduce the issue locally using the following CMake command on Windows: cmake -GNinja -Bbuild -DCMAKE_BUILD_TYPE=Release -DLLVM_TARGETS_TO_BUILD=host -DLLVM_INCLUDE_TOOLS=ON llvm && ninja -C build check-llvm-tools.

Here is the list of tests that fail:

Failed Tests (6):
  LLVM :: tools/llvm-objdump/X86/elf-bbaddrmap-disassemble-symbolize-operands.yaml
  LLVM :: tools/llvm-readobj/ELF/bb-addr-map.test
  LLVM :: tools/obj2yaml/ELF/bb-addr-map.yaml
  LLVM :: tools/yaml2obj/ELF/bb-addr-map.yaml
  LLVM-Unit :: Object/./ObjectTests.exe/ELFObjectFileTest/InvalidDecodeBBAddrMap
  LLVM-Unit :: Object/./ObjectTests.exe/ELFObjectFileTest/ReadBBAddrMap

Forcing BBAddrMapVersion to 2 in MCContext.h does not resolve the issue. On the other hand, reverting this patch causes all tests to pass.

Is there a quick fix for the problem? If not, could you revert it please?

[powderluv]

Just want to echo @ashay-github comments. This regression in Windows is holding up Torch-MLIR and IREE-Torch and SHARK downstream projects rolling on to the latest LLVM. Can we please revert or quickly fix? Thanks

[stella.stamenova]

@rahmanl would it be possible to address the windows failures or revert this commit while someone investigates?

[rahmanl]

I will start looking at this now. If I can't get a fix by tomorrow, we'll
revert the patch. Thanks.

[ashay-github]

I confirmed just now that the build failure seems to be a result of MSVC version differences. MSVC v14.29 (from Visual Studio 2019) which is used in the pre-merge checks here causes the tests to pass, but MSVC v14.33 (from Visual Studio 2022) causes test failures, which perhaps means that either the older compiler miscompiled LLVM or that there is a bug in the newer version of the compiler. It still seems worthwhile to revert this patch so that we unblock folks downstream, and in the meantime, find out the source of the bug.

[rahmanl]

Thanks for the investigation @ashay-github. This seems to be a complex bug, I am setting up a windows machine to be able to debug, but I appreciate your help.

[ashay-github]

Thanks for looking into this! Let me know if you have trouble reproducing the error.

[rahmanl]

In D100808#3992722, @ashay-github wrote:

Thanks for looking into this! Let me know if you have trouble reproducing the error.

@ashay-github I've been having some issues trying to build LLVM on windows. Getting access to Visual Studio 2022 seems to take a while. Would you please reproduce the error on Windows again and send me the verbose llvm-lit diff. Also, if you could please share the intermediate object file(s) for one test (created using yaml2obj) I appreciate it.

[ashay-github]

@rahmanl I've uploaded the console output and the output of the following commands here: https://file.io/rjyLym3SKpqx. Let me know if you have trouble accessing those files.

> build\bin\yaml2obj.exe --docnum=1 llvm\test\tools\yaml2obj\ELF\bb-addr-map.yaml -o out.obj
> build\bin\obj2yaml.exe out.obj > out.yaml

[rahmanl]

@ashay-github Thank you for providing the intermediate files. Unfortunately, I wasn't able to diagnose the issue. I ran into issues when building LLVM on windows. I wanted to try this patch again, but avoid running the problematic tests on windows.

[rahmanl]

• Avoid running failed tests on Windows.

[ashay-github]

Hi @rahmanl, thanks for the changes. I did check that the updated patch doesn't break Windows builds and tests.

[rahmanl]

Thanks for verifying @ashay-github .

llvm/include/llvm/CodeGen/BasicBlockSectionsProfileReader.h

 #include "llvm/Support/LineIterator.h"
 #include "llvm/Support/MemoryBuffer.h"
 
 using namespace llvm;
 
 namespace llvm {
 
 // The cluster information for a machine basic block.
 struct BBClusterInfo {
-  // MachineBasicBlock ID.
-  unsigned MBBNumber;
+  // Unique ID for this basic block.
+  unsigned BBID;
   // Cluster ID this basic block belongs to.
   unsigned ClusterID;
   // Position of basic block within the cluster.
   unsigned PositionInCluster;
 };
 
 using ProgramBBClusterInfoMapTy = StringMap<SmallVector<BBClusterInfo>>;
 

llvm/include/llvm/CodeGen/MachineBasicBlock.h

private:
   bool IsEHCatchretTarget = false;
 
   /// Indicate that this basic block is the entry block of an EH funclet.
   bool IsEHFuncletEntry = false;
 
   /// Indicate that this basic block is the entry block of a cleanup funclet.
   bool IsCleanupFuncletEntry = false;
 
+  /// Fixed unique ID assigned to this basic block upon creation. Used with
+  /// basic block sections and basic block labels.
+  Optional<unsigned> BBID;
+
   /// With basic block sections, this stores the Section ID of the basic block.
   MBBSectionID SectionID{0};
 
   // Indicate that this basic block begins a section.
   bool IsBeginSection = false;
 
   // Indicate that this basic block ends a section.
   bool IsEndSection = false;
public:
 
   /// Returns true if this block ends any section.
   bool isEndSection() const { return IsEndSection; }
 
   void setIsBeginSection(bool V = true) { IsBeginSection = V; }
 
   void setIsEndSection(bool V = true) { IsEndSection = V; }
 
+  Optional<unsigned> getBBID() const { return BBID; }
+
+  /// Returns the BBID of the block when BBAddrMapVersion >= 2, otherwise
+  /// returns Number.
+  /// TODO: Remove this function when version 1 is deprecated.
+  unsigned getBBIDOrNumber() const;
+
   /// Returns the section ID of this basic block.
   MBBSectionID getSectionID() const { return SectionID; }
 
   /// Returns the unique section ID number of this basic block.
   unsigned getSectionIDNum() const {
     return ((unsigned)MBBSectionID::SectionType::Cold) -
            ((unsigned)SectionID.Type) + SectionID.Number;
   }
 
+  /// Sets the fixed BBID of this basic block.
+  void setBBID(unsigned V) {
+    assert(!BBID.has_value() && "Cannot change BBID.");
+    BBID = V;
+  }
+
   /// Sets the section ID for this basic block.
   void setSectionID(MBBSectionID V) { SectionID = V; }
 
   /// Returns the MCSymbol marking the end of this basic block.
   MCSymbol *getEndSymbol() const;
 
   /// Returns true if this block may have an INLINEASM_BR (overestimate, by
   /// checking if any of the successors are indirect targets of any inlineasm_br

llvm/include/llvm/CodeGen/MachineFunction.h

class LLVM_EXTERNAL_VISIBILITY MachineFunction {
   std::vector<std::pair<MCSymbol *, MDNode *>> CodeViewAnnotations;
 
   bool CallsEHReturn = false;
   bool CallsUnwindInit = false;
   bool HasEHCatchret = false;
   bool HasEHScopes = false;
   bool HasEHFunclets = false;
 
+  /// BBID to assign to the next basic block of this function.
+  unsigned NextBBID = 0;
+
   /// Section Type for basic blocks, only relevant with basic block sections.
   BasicBlockSection BBSectionsType = BasicBlockSection::None;
 
   /// List of C++ TypeInfo used.
   std::vector<const GlobalValue *> TypeInfos;
 
   /// List of typeids encoding filters used.
   std::vector<unsigned> FilterIds;

llvm/include/llvm/Object/ELFTypes.h

template <class ELFT> struct Elf_Mips_ABIFlags {
   Elf_Word flags2;   // General flags
 };
 
 // Struct representing the BBAddrMap for one function.
 struct BBAddrMap {
   uint64_t Addr; // Function address
   // Struct representing the BBAddrMap information for one basic block.
   struct BBEntry {
+    uint32_t ID;     // Unique ID of this basic block.
     uint32_t Offset; // Offset of basic block relative to function start.
     uint32_t Size;   // Size of the basic block.
 
     // The following fields are decoded from the Metadata field. The encoding
     // happens in AsmPrinter.cpp:getBBAddrMapMetadata.
     bool HasReturn;      // If this block ends with a return (or tail call).
     bool HasTailCall;    // If this block ends with a tail call.
     bool IsEHPad;        // If this is an exception handling block.
     bool CanFallThrough; // If this block can fall through to its next.
 
-    BBEntry(uint32_t Offset, uint32_t Size, uint32_t Metadata)
-        : Offset(Offset), Size(Size), HasReturn(Metadata & 1),
+    BBEntry(uint32_t ID, uint32_t Offset, uint32_t Size, uint32_t Metadata)
+        : ID(ID), Offset(Offset), Size(Size), HasReturn(Metadata & 1),
           HasTailCall(Metadata & (1 << 1)), IsEHPad(Metadata & (1 << 2)),
           CanFallThrough(Metadata & (1 << 3)){};
 
     bool operator==(const BBEntry &Other) const {
-      return Offset == Other.Offset && Size == Other.Size &&
+      return ID == Other.ID && Offset == Other.Offset && Size == Other.Size &&
              HasReturn == Other.HasReturn && HasTailCall == Other.HasTailCall &&
              IsEHPad == Other.IsEHPad && CanFallThrough == Other.CanFallThrough;
     }
   };
   std::vector<BBEntry> BBEntries; // Basic block entries for this function.
 
   // Equality operator for unit testing.
   bool operator==(const BBAddrMap &Other) const {

llvm/include/llvm/ObjectYAML/ELFYAML.h

 
 struct DynamicEntry {
   ELF_DYNTAG Tag;
   llvm::yaml::Hex64 Val;
 };
 
 struct BBAddrMapEntry {
   struct BBEntry {
+    uint32_t ID;
     llvm::yaml::Hex64 AddressOffset;
     llvm::yaml::Hex64 Size;
     llvm::yaml::Hex64 Metadata;
   };
   uint8_t Version;
   llvm::yaml::Hex8 Feature;
   llvm::yaml::Hex64 Address;
   Optional<uint64_t> NumBlocks;

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

MCSection *BBAddrMapSection =
       getObjFileLowering().getBBAddrMapSection(*MF.getSection());
   assert(BBAddrMapSection && ".llvm_bb_addr_map section is not initialized.");
 
   const MCSymbol *FunctionSymbol = getFunctionBegin();
 
   OutStreamer->pushSection();
   OutStreamer->switchSection(BBAddrMapSection);
   OutStreamer->AddComment("version");
-  OutStreamer->emitInt8(OutStreamer->getContext().getBBAddrMapVersion());
+  uint8_t BBAddrMapVersion = OutStreamer->getContext().getBBAddrMapVersion();
+  OutStreamer->emitInt8(BBAddrMapVersion);
   OutStreamer->AddComment("feature");
   OutStreamer->emitInt8(0);
   OutStreamer->AddComment("function address");
   OutStreamer->emitSymbolValue(FunctionSymbol, getPointerSize());
   OutStreamer->AddComment("number of basic blocks");
   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();
+    if (BBAddrMapVersion > 1) {
+      OutStreamer->AddComment("BB id");
+      // Emit the BB ID for this basic block.
+      OutStreamer->emitULEB128IntValue(*MBB.getBBID());
+    }
     // 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);
+    // Emit the Metadata.
     OutStreamer->emitULEB128IntValue(getBBAddrMapMetadata(MBB));
     PrevMBBEndSymbol = MBB.getEndSymbol();
   }
   OutStreamer->popSection();
 }
 
 void AsmPrinter::emitKCFITrapEntry(const MachineFunction &MF,
                                    const MCSymbol *Symbol) {

llvm/lib/CodeGen/BasicBlockSections.cpp

 // 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"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
-#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
 #include "llvm/CodeGen/BasicBlockSectionUtils.h"
+#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/InitializePasses.h"
+#include "llvm/MC/MCContext.h"
 #include "llvm/Target/TargetMachine.h"
 #include <optional>
 
 using namespace llvm;
 
 // Placing the cold clusters in a separate section mitigates against poor
 // profiles and allows optimizations such as hugepage mapping to be applied at a
 // section granularity. Defaults to ".text.split." which is recognized by lld

 char BasicBlockSections::ID = 0;
 INITIALIZE_PASS(BasicBlockSections, "bbsections-prepare",
                 "Prepares for basic block sections, by splitting functions "
                 "into clusters of basic blocks.",
                 false, false)
 
 // This function updates and optimizes the branching instructions of every basic
 // block in a given function to account for changes in the layout.
-static void updateBranches(
-    MachineFunction &MF,
-    const SmallVector<MachineBasicBlock *, 4> &PreLayoutFallThroughs) {
+static void
+updateBranches(MachineFunction &MF,
+               const SmallVector<MachineBasicBlock *> &PreLayoutFallThroughs) {
   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
   SmallVector<MachineOperand, 4> Cond;
   for (auto &MBB : MF) {
     auto NextMBBI = std::next(MBB.getIterator());
     auto *FTMBB = PreLayoutFallThroughs[MBB.getNumber()];
     // If this block had a fallthrough before we need an explicit unconditional
     // branch to that block if either
     //     1- the block ends a section, which means its next block may be
updateBranches(MachineFunction &MF,
   }
 }
 
 // This function provides the BBCluster information associated with a function.
 // Returns true if a valid association exists and false otherwise.
 bool getBBClusterInfoForFunction(
     const MachineFunction &MF,
     BasicBlockSectionsProfileReader *BBSectionsProfileReader,
-    std::vector<Optional<BBClusterInfo>> &V) {
+    DenseMap<unsigned, BBClusterInfo> &V) {
 
   // Find the assoicated cluster information.
   std::pair<bool, SmallVector<BBClusterInfo, 4>> P =
       BBSectionsProfileReader->getBBClusterInfoForFunction(MF.getName());
   if (!P.first)
     return false;
 
   if (P.second.empty()) {
     // This indicates that sections are desired for all basic blocks of this
     // function. We clear the BBClusterInfo vector to denote this.
     V.clear();
     return true;
   }
 
-  V.resize(MF.getNumBlockIDs());
-  for (auto bbClusterInfo : P.second) {
-    // Bail out if the cluster information contains invalid MBB numbers.
-    if (bbClusterInfo.MBBNumber >= MF.getNumBlockIDs())
-      return false;
-    V[bbClusterInfo.MBBNumber] = bbClusterInfo;
-  }
+  for (const BBClusterInfo &BBCI : P.second)
+    V[BBCI.BBID] = BBCI;
   return true;
 }
 
 // This function sorts basic blocks according to the cluster's information.
 // All explicitly specified clusters of basic blocks will be ordered
 // accordingly. All non-specified BBs go into a separate "Cold" section.
 // Additionally, if exception handling landing pads end up in more than one
 // clusters, they are moved into a single "Exception" section. Eventually,
 // clusters are ordered in increasing order of their IDs, with the "Exception"
 // and "Cold" succeeding all other clusters.
-// FuncBBClusterInfo represent the cluster information for basic blocks. If this
-// is empty, it means unique sections for all basic blocks in the function.
-static void
-assignSections(MachineFunction &MF,
-               const std::vector<Optional<BBClusterInfo>> &FuncBBClusterInfo) {
+// FuncBBClusterInfo represent the cluster information for basic blocks. It
+// maps from BBID of basic blocks to their cluster information. If this is
+// empty, it means unique sections for all basic blocks in the function.
+static void assignSections(
+    MachineFunction &MF,
+    const DenseMap<unsigned, BBClusterInfo> &FuncBBClusterInfo) {
   assert(MF.hasBBSections() && "BB Sections is not set for function.");
   // This variable stores the section ID of the cluster containing eh_pads (if
   // all eh_pads are one cluster). If more than one cluster contain eh_pads, we
   // set it equal to ExceptionSectionID.
   std::optional<MBBSectionID> EHPadsSectionID;
 
   for (auto &MBB : MF) {
     // With the 'all' option, every basic block is placed in a unique section.
     // With the 'list' option, every basic block is placed in a section
     // associated with its cluster, unless we want individual unique sections
     // for every basic block in this function (if FuncBBClusterInfo is empty).
     if (MF.getTarget().getBBSectionsType() == llvm::BasicBlockSection::All ||
         FuncBBClusterInfo.empty()) {
       // If unique sections are desired for all basic blocks of the function, we
-      // set every basic block's section ID equal to its number (basic block
-      // id). This further ensures that basic blocks are ordered canonically.
-      MBB.setSectionID({static_cast<unsigned int>(MBB.getNumber())});
-    } else if (FuncBBClusterInfo[MBB.getNumber()])
-      MBB.setSectionID(FuncBBClusterInfo[MBB.getNumber()]->ClusterID);
-    else {
+      // set every basic block's section ID equal to its original position in
+      // the layout. This ensures that basic blocks are ordered canonically.
+      MBB.setSectionID(MBB.getNumber());
+    } else {
+      auto I = FuncBBClusterInfo.find(MBB.getBBIDOrNumber());
+      if (I != FuncBBClusterInfo.end()) {
+        MBB.setSectionID(I->second.ClusterID);
+      } else {
         // BB goes into the special cold section if it is not specified in the
         // cluster info map.
         MBB.setSectionID(MBBSectionID::ColdSectionID);
       }
+    }
 
     if (MBB.isEHPad() && EHPadsSectionID != MBB.getSectionID() &&
         EHPadsSectionID != MBBSectionID::ExceptionSectionID) {
       // If we already have one cluster containing eh_pads, this must be updated
       // to ExceptionSectionID. Otherwise, we set it equal to the current
       // section ID.
       EHPadsSectionID = EHPadsSectionID ? MBBSectionID::ExceptionSectionID
                                         : MBB.getSectionID();
     }
   }
 
   // If EHPads are in more than one section, this places all of them in the
   // special exception section.
   if (EHPadsSectionID == MBBSectionID::ExceptionSectionID)
     for (auto &MBB : MF)
       if (MBB.isEHPad())
         MBB.setSectionID(*EHPadsSectionID);
 }
 
 void llvm::sortBasicBlocksAndUpdateBranches(
     MachineFunction &MF, MachineBasicBlockComparator MBBCmp) {
-  SmallVector<MachineBasicBlock *, 4> PreLayoutFallThroughs(
+  [[maybe_unused]] const MachineBasicBlock *EntryBlock = &MF.front();
+  SmallVector<MachineBasicBlock *> PreLayoutFallThroughs(
       MF.getNumBlockIDs());
   for (auto &MBB : MF)
     PreLayoutFallThroughs[MBB.getNumber()] = MBB.getFallThrough();
 
   MF.sort(MBBCmp);
+  assert(&MF.front() == EntryBlock &&
+         "Entry block should not be displaced by basic block sections");
 
   // Set IsBeginSection and IsEndSection according to the assigned section IDs.
   MF.assignBeginEndSections();
 
   // After reordering basic blocks, we must update basic block branches to
   // insert explicit fallthrough branches when required and optimize branches
   // when possible.
   updateBranches(MF, PreLayoutFallThroughs);
 }
 
bool BasicBlockSections::runOnMachineFunction(MachineFunction &MF) {
   // were obtained, optimizing basic blocks might be sub-optimal.
   // This only applies to BasicBlockSection::List as it creates
   // clusters of basic blocks using basic block ids. Source drift can
   // invalidate these groupings leading to sub-optimal code generation with
   // regards to performance.
   if (BBSectionsType == BasicBlockSection::List &&
       hasInstrProfHashMismatch(MF))
     return true;
-
-  // Renumber blocks before sorting them for basic block sections.  This is
-  // useful during sorting, basic blocks in the same section will retain the
-  // default order.  This renumbering should also be done for basic block
-  // labels to match the profiles with the correct blocks.
+  // Renumber blocks before sorting them. This is useful during sorting,
+  // basic blocks in the same section will retain the default order.
+  // This renumbering should also be done for basic block labels to match the
+  // profiles with the correct blocks.
+  // TODO: For LLVM_BB_ADDR_MAP versions 2 and higher, this renumbering serves a
+  // different purpose. Change the above comment accordingly when lower versions
+  // are deprecated.
   MF.RenumberBlocks();
 
   if (BBSectionsType == BasicBlockSection::Labels) {
     MF.setBBSectionsType(BBSectionsType);
     return true;
   }
 
   BBSectionsProfileReader = &getAnalysis<BasicBlockSectionsProfileReader>();
 
-  std::vector<Optional<BBClusterInfo>> FuncBBClusterInfo;
+  DenseMap<unsigned, BBClusterInfo> FuncBBClusterInfo;
   if (BBSectionsType == BasicBlockSection::List &&
       !getBBClusterInfoForFunction(MF, BBSectionsProfileReader,
                                    FuncBBClusterInfo))
     return true;
   MF.setBBSectionsType(BBSectionsType);
+
   assignSections(MF, FuncBBClusterInfo);
 
   // We make sure that the cluster including the entry basic block precedes all
   // other clusters.
   auto EntryBBSectionID = MF.front().getSectionID();
 
   // Helper function for ordering BB sections as follows:
   //   * Entry section (section including the entry block).
auto Comparator = [&](const MachineBasicBlock &X,
                         const MachineBasicBlock &Y) {
     auto XSectionID = X.getSectionID();
     auto YSectionID = Y.getSectionID();
     if (XSectionID != YSectionID)
       return MBBSectionOrder(XSectionID, YSectionID);
     // If the two basic block are in the same section, the order is decided by
     // their position within the section.
     if (XSectionID.Type == MBBSectionID::SectionType::Default)
-      return FuncBBClusterInfo[X.getNumber()]->PositionInCluster <
-             FuncBBClusterInfo[Y.getNumber()]->PositionInCluster;
+      return FuncBBClusterInfo.lookup(X.getBBIDOrNumber()).PositionInCluster <
+             FuncBBClusterInfo.lookup(Y.getBBIDOrNumber()).PositionInCluster;
     return X.getNumber() < Y.getNumber();
   };
 
   sortBasicBlocksAndUpdateBranches(MF, Comparator);
   avoidZeroOffsetLandingPad(MF);
   return true;
 }
 

llvm/lib/CodeGen/BasicBlockSectionsProfileReader.cpp

for (; !LineIt.is_at_eof(); ++LineIt) {
     // Check for the leading "!"
     if (!S.consume_front("!") || S.empty())
       break;
     // Check for second "!" which indicates a cluster of basic blocks.
     if (S.consume_front("!")) {
       if (FI == ProgramBBClusterInfo.end())
         return invalidProfileError(
             "Cluster list does not follow a function name specifier.");
-      SmallVector<StringRef, 4> BBIndexes;
-      S.split(BBIndexes, ' ');
+      SmallVector<StringRef, 4> BBIDs;
+      S.split(BBIDs, ' ');
       // Reset current cluster position.
       CurrentPosition = 0;
-      for (auto BBIndexStr : BBIndexes) {
-        unsigned long long BBIndex;
-        if (getAsUnsignedInteger(BBIndexStr, 10, BBIndex))
+      for (auto BBIDStr : BBIDs) {
+        unsigned long long BBID;
+        if (getAsUnsignedInteger(BBIDStr, 10, BBID))
           return invalidProfileError(Twine("Unsigned integer expected: '") +
-                                     BBIndexStr + "'.");
-        if (!FuncBBIDs.insert(BBIndex).second)
+                                     BBIDStr + "'.");
+        if (!FuncBBIDs.insert(BBID).second)
           return invalidProfileError(Twine("Duplicate basic block id found '") +
-                                     BBIndexStr + "'.");
-        if (!BBIndex && CurrentPosition)
+                                     BBIDStr + "'.");
+        if (BBID == 0 && CurrentPosition)
           return invalidProfileError("Entry BB (0) does not begin a cluster.");
 
-        FI->second.emplace_back(BBClusterInfo{
-            ((unsigned)BBIndex), CurrentCluster, CurrentPosition++});
+        FI->second.emplace_back(
+            BBClusterInfo{((unsigned)BBID), CurrentCluster, CurrentPosition++});
       }
       CurrentCluster++;
     } else { // This is a function name specifier.
       // Function aliases are separated using '/'. We use the first function
       // name for the cluster info mapping and delegate all other aliases to
       // this one.
       SmallVector<StringRef, 4> Aliases;
       S.split(Aliases, '/');

llvm/lib/CodeGen/MIRParser/MILexer.h

enum TokenKind {
     kw_intpred,
     kw_shufflemask,
     kw_pre_instr_symbol,
     kw_post_instr_symbol,
     kw_heap_alloc_marker,
     kw_pcsections,
     kw_cfi_type,
     kw_bbsections,
+    kw_bb_id,
     kw_unknown_size,
     kw_unknown_address,
     kw_ir_block_address_taken,
     kw_machine_block_address_taken,
 
     // Metadata types.
     kw_distinct,
 

llvm/lib/CodeGen/MIRParser/MILexer.cpp

return StringSwitch<MIToken::TokenKind>(Identifier)
       .Case("intpred", MIToken::kw_intpred)
       .Case("shufflemask", MIToken::kw_shufflemask)
       .Case("pre-instr-symbol", MIToken::kw_pre_instr_symbol)
       .Case("post-instr-symbol", MIToken::kw_post_instr_symbol)
       .Case("heap-alloc-marker", MIToken::kw_heap_alloc_marker)
       .Case("pcsections", MIToken::kw_pcsections)
       .Case("cfi-type", MIToken::kw_cfi_type)
       .Case("bbsections", MIToken::kw_bbsections)
+      .Case("bb_id", MIToken::kw_bb_id)
       .Case("unknown-size", MIToken::kw_unknown_size)
       .Case("unknown-address", MIToken::kw_unknown_address)
       .Case("distinct", MIToken::kw_distinct)
       .Case("ir-block-address-taken", MIToken::kw_ir_block_address_taken)
-      .Case("machine-block-address-taken", MIToken::kw_machine_block_address_taken)
+      .Case("machine-block-address-taken",
+            MIToken::kw_machine_block_address_taken)
       .Default(MIToken::Identifier);
 }
 
 static Cursor maybeLexIdentifier(Cursor C, MIToken &Token) {
   if (!isalpha(C.peek()) && C.peek() != '_')
     return std::nullopt;
   auto Range = C;
   while (isIdentifierChar(C.peek()))

llvm/lib/CodeGen/MIRParser/MIParser.cpp

bool parseMachineOperandAndTargetFlags(const unsigned OpCode,
                                          const unsigned OpIdx,
                                          MachineOperand &Dest,
                                          Optional<unsigned> &TiedDefIdx);
   bool parseOffset(int64_t &Offset);
   bool parseIRBlockAddressTaken(BasicBlock *&BB);
   bool parseAlignment(uint64_t &Alignment);
   bool parseAddrspace(unsigned &Addrspace);
   bool parseSectionID(Optional<MBBSectionID> &SID);
+  bool parseBBID(Optional<unsigned> &PrID);
   bool parseOperandsOffset(MachineOperand &Op);
   bool parseIRValue(const Value *&V);
   bool parseMemoryOperandFlag(MachineMemOperand::Flags &Flags);
   bool parseMemoryPseudoSourceValue(const PseudoSourceValue *&PSV);
   bool parseMachinePointerInfo(MachinePointerInfo &Dest);
   bool parseOptionalScope(LLVMContext &Context, SyncScope::ID &SSID);
   bool parseOptionalAtomicOrdering(AtomicOrdering &Order);
   bool parseMachineMemoryOperand(MachineMemOperand *&Dest);
else if (S == "Cold")
       SID = MBBSectionID::ColdSectionID;
     else
       return error("Unknown Section ID");
   }
   lex();
   return false;
 }
 
+// Parse Machine Basic Block ID.
+bool MIParser::parseBBID(Optional<unsigned> &BBID) {
+  assert(Token.is(MIToken::kw_bb_id));
+  lex();
+  unsigned Value = 0;
+  if (getUnsigned(Value))
+    return error("Unknown BB ID");
+  BBID = Value;
+  lex();
+  return false;
+}
+
 bool MIParser::parseBasicBlockDefinition(
     DenseMap<unsigned, MachineBasicBlock *> &MBBSlots) {
   assert(Token.is(MIToken::MachineBasicBlockLabel));
   unsigned ID = 0;
   if (getUnsigned(ID))
     return true;
   auto Loc = Token.location();
   auto Name = Token.stringValue();
   lex();
   bool MachineBlockAddressTaken = false;
   BasicBlock *AddressTakenIRBlock = nullptr;
   bool IsLandingPad = false;
   bool IsInlineAsmBrIndirectTarget = false;
   bool IsEHFuncletEntry = false;
   Optional<MBBSectionID> SectionID;
   uint64_t Alignment = 0;
+  Optional<unsigned> BBID;
   BasicBlock *BB = nullptr;
   if (consumeIfPresent(MIToken::lparen)) {
     do {
       // TODO: Report an error when multiple same attributes are specified.
       switch (Token.kind()) {
       case MIToken::kw_machine_block_address_taken:
         MachineBlockAddressTaken = true;
         lex();
do {
         if (parseIRBlock(BB, MF.getFunction()))
           return true;
         lex();
         break;
       case MIToken::kw_bbsections:
         if (parseSectionID(SectionID))
           return true;
         break;
+      case MIToken::kw_bb_id:
+        if (parseBBID(BBID))
+          return true;
+        break;
       default:
         break;
       }
     } while (consumeIfPresent(MIToken::comma));
     if (expectAndConsume(MIToken::rparen))
       return true;
   }
   if (expectAndConsume(MIToken::colon))
if (AddressTakenIRBlock)
     MBB->setAddressTakenIRBlock(AddressTakenIRBlock);
   MBB->setIsEHPad(IsLandingPad);
   MBB->setIsInlineAsmBrIndirectTarget(IsInlineAsmBrIndirectTarget);
   MBB->setIsEHFuncletEntry(IsEHFuncletEntry);
   if (SectionID) {
     MBB->setSectionID(SectionID.value());
     MF.setBBSectionsType(BasicBlockSection::List);
   }
+  if (BBID.has_value()) {
+    // BBSectionsType is set to `List` if any basic blocks has `SectionID`.
+    // Here, we set it to `Labels` if it hasn't been set above.
+    if (!MF.hasBBSections())
+      MF.setBBSectionsType(BasicBlockSection::Labels);
+    MBB->setBBID(BBID.value());
+  }
   return false;
 }
 
 bool MIParser::parseBasicBlockDefinitions(
     DenseMap<unsigned, MachineBasicBlock *> &MBBSlots) {
   lex();
   // Skip until the first machine basic block.
   while (Token.is(MIToken::Newline))

llvm/lib/CodeGen/MachineBasicBlock.cpp

if (getSectionID() != MBBSectionID(0)) {
       case MBBSectionID::SectionType::Cold:
         os << "Cold";
         break;
       default:
         os << getSectionID().Number;
       }
       hasAttributes = true;
     }
+    if (getBBID().has_value()) {
+      os << (hasAttributes ? ", " : " (");
+      os << "bb_id " << *getBBID();
+      hasAttributes = true;
+    }
   }
 
   if (hasAttributes)
     os << ')';
 }
 
 void MachineBasicBlock::printAsOperand(raw_ostream &OS,
                                        bool /*PrintType*/) const {
bool MachineBasicBlock::sizeWithoutDebugLargerThan(unsigned Limit) const {
   auto R = instructionsWithoutDebug(begin(), end());
   for (auto I = R.begin(), E = R.end(); I != E; ++I) {
     if (++Cntr > Limit)
       return true;
   }
   return false;
 }
 
+unsigned MachineBasicBlock::getBBIDOrNumber() const {
+  uint8_t BBAddrMapVersion = getParent()->getContext().getBBAddrMapVersion();
+  return BBAddrMapVersion < 2 ? getNumber() : *getBBID();
+}
+
 const MBBSectionID MBBSectionID::ColdSectionID(MBBSectionID::SectionType::Cold);
 const MBBSectionID
     MBBSectionID::ExceptionSectionID(MBBSectionID::SectionType::Exception);

llvm/lib/CodeGen/MachineFunction.cpp

void MachineFunction::deleteMachineInstr(MachineInstr *MI) {
   // destructors.
   InstructionRecycler.Deallocate(Allocator, MI);
 }
 
 /// Allocate a new MachineBasicBlock. Use this instead of
 /// `new MachineBasicBlock'.
 MachineBasicBlock *
 MachineFunction::CreateMachineBasicBlock(const BasicBlock *bb) {
-  return new (BasicBlockRecycler.Allocate<MachineBasicBlock>(Allocator))
-             MachineBasicBlock(*this, bb);
+  MachineBasicBlock *MBB =
+      new (BasicBlockRecycler.Allocate<MachineBasicBlock>(Allocator))
+  if (Target.getBBSectionsType() == BasicBlockSection::Labels ||
+      Target.getBBSectionsType() == BasicBlockSection::List)
+    MBB->setBBID(NextBBID++);
+  return MBB;
 }
 
 /// Delete the given MachineBasicBlock.
 void MachineFunction::deleteMachineBasicBlock(MachineBasicBlock *MBB) {
   assert(MBB->getParent() == this && "MBB parent mismatch!");
   // Clean up any references to MBB in jump tables before deleting it.
   if (JumpTableInfo)
     JumpTableInfo->RemoveMBBFromJumpTables(MBB);

llvm/lib/Object/ELF.cpp

ELFFile<ELFT>::decodeBBAddrMap(const Elf_Shdr &Sec) const {
   };
 
   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)
+      if (Version > 2)
         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) {
+    for (uint32_t BlockIndex = 0;
+         !ULEBSizeErr && Cur && (BlockIndex < NumBlocks); ++BlockIndex) {
+      uint32_t ID = Version >= 2 ? ReadULEB128AsUInt32() : BlockIndex;
       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});
+      BBEntries.push_back({ID, Offset, Size, Metadata});
     }
     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.
   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/lib/ObjectYAML/ELFEmitter.cpp

void ELFState<ELFT>::writeSectionContent(
     Elf_Shdr &SHeader, const ELFYAML::BBAddrMapSection &Section,
     ContiguousBlobAccumulator &CBA) {
   if (!Section.Entries)
     return;
 
   for (const ELFYAML::BBAddrMapEntry &E : *Section.Entries) {
     // Write version and feature values.
     if (Section.Type == llvm::ELF::SHT_LLVM_BB_ADDR_MAP) {
-      if (E.Version > 1)
+      if (E.Version > 2)
         WithColor::warning() << "unsupported SHT_LLVM_BB_ADDR_MAP version: "
                              << static_cast<int>(E.Version)
                              << "; encoding using the most recent version";
       CBA.write(E.Version);
       CBA.write(E.Feature);
       SHeader.sh_size += 2;
     }
     // Write the address of the function.
     CBA.write<uintX_t>(E.Address, ELFT::TargetEndianness);
     // Write number of BBEntries (number of basic blocks in the function). This
     // is overridden by the 'NumBlocks' YAML field when specified.
     uint64_t NumBlocks =
         E.NumBlocks.value_or(E.BBEntries ? E.BBEntries->size() : 0);
     SHeader.sh_size += sizeof(uintX_t) + CBA.writeULEB128(NumBlocks);
     // Write all BBEntries.
     if (!E.BBEntries)
       continue;
-    for (const ELFYAML::BBAddrMapEntry::BBEntry &BBE : *E.BBEntries)
+    for (const ELFYAML::BBAddrMapEntry::BBEntry &BBE : *E.BBEntries) {
+      if (Section.Type == llvm::ELF::SHT_LLVM_BB_ADDR_MAP && E.Version > 1)
+        SHeader.sh_size += CBA.writeULEB128(BBE.ID);
       SHeader.sh_size += CBA.writeULEB128(BBE.AddressOffset) +
                          CBA.writeULEB128(BBE.Size) +
                          CBA.writeULEB128(BBE.Metadata);
     }
   }
+}
 
 template <class ELFT>
 void ELFState<ELFT>::writeSectionContent(
     Elf_Shdr &SHeader, const ELFYAML::LinkerOptionsSection &Section,
     ContiguousBlobAccumulator &CBA) {
   if (!Section.Options)
     return;
 

llvm/lib/ObjectYAML/ELFYAML.cpp

void MappingTraits<ELFYAML::BBAddrMapEntry>::mapping(
   IO.mapOptional("Address", E.Address, Hex64(0));
   IO.mapOptional("NumBlocks", E.NumBlocks);
   IO.mapOptional("BBEntries", E.BBEntries);
 }
 
 void MappingTraits<ELFYAML::BBAddrMapEntry::BBEntry>::mapping(
     IO &IO, ELFYAML::BBAddrMapEntry::BBEntry &E) {
   assert(IO.getContext() && "The IO context is not initialized");
+  IO.mapOptional("ID", E.ID);
   IO.mapRequired("AddressOffset", E.AddressOffset);
   IO.mapRequired("Size", E.Size);
   IO.mapRequired("Metadata", E.Metadata);
 }
 
 void MappingTraits<ELFYAML::GnuHashHeader>::mapping(IO &IO,
                                                     ELFYAML::GnuHashHeader &E) {
   assert(IO.getContext() && "The IO context is not initialized");

llvm/test/CodeGen/X86/basic-block-labels-mir-parse.mir

+# Start after bbsections0-prepare and check that the BB address map is generated.
+# RUN: llc -mtriple x86_64-unknown-linux-gnu -start-after=bbsections-prepare  %s -o - | FileCheck %s -check-prefix=CHECK
+
+# How to generate the input:
+# foo.cc
+# int foo(bool k) {
+#  if (k) return 1;
+#  return 0;
+# }
+#
+# clang -O0 -S -emit-llvm foo.cc
+# llc < foo.ll -stop-after=bbsections-prepare -basic-block-sections=labels
+
+# CHECK: .section .llvm_bb_addr_map,"o",@llvm_bb_addr_map,.text
+--- |
+  ; ModuleID = '<stdin>'
+  source_filename = "/tmp/foo.cc"
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-pc-linux-gnu"
+  
+  ; Function Attrs: mustprogress noinline nounwind optnone uwtable
+  define dso_local noundef i32 @_Z3foob(i1 noundef zeroext %0) #0 {
+    %2 = alloca i32, align 4
+    %3 = alloca i8, align 1
+    %4 = zext i1 %0 to i8
+    store i8 %4, i8* %3, align 1
+    %5 = load i8, i8* %3, align 1
+    %6 = trunc i8 %5 to i1
+    br i1 %6, label %7, label %8
+  
+  7:                                                ; preds = %1
+    store i32 1, i32* %2, align 4
+    br label %9
+  
+  8:                                                ; preds = %1
+    store i32 0, i32* %2, align 4
+    br label %9
+  
+  9:                                                ; preds = %8, %7
+    %10 = load i32, i32* %2, align 4
+    ret i32 %10
+  }
+  
+  attributes #0 = { mustprogress noinline nounwind optnone uwtable "frame-pointer"="all" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }
+  
+  !llvm.module.flags = !{!0, !1, !2, !3, !4}
+  !llvm.ident = !{!5}
+  
+  !0 = !{i32 1, !"wchar_size", i32 4}
+  !1 = !{i32 7, !"PIC Level", i32 2}
+  !2 = !{i32 7, !"PIE Level", i32 2}
+  !3 = !{i32 7, !"uwtable", i32 1}
+  !4 = !{i32 7, !"frame-pointer", i32 2}
+  !5 = !{!"Debian clang version 14.0.6-2"}
+
+...
+---
+name:            _Z3foob
+alignment:       16
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+callsEHReturn:   false
+callsUnwindInit: false
+hasEHCatchret:   false
+hasEHScopes:     false
+hasEHFunclets:   false
+failsVerification: false
+tracksDebugUserValues: true
+registers:       []
+liveins:
+  - { reg: '$edi', virtual-reg: '' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       8
+  offsetAdjustment: -8
+  maxAlignment:    4
+  adjustsStack:    false
+  hasCalls:        false
+  stackProtector:  ''
+  functionContext: ''
+  maxCallFrameSize: 0
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  hasTailCall:     false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:
+  - { id: 0, type: spill-slot, offset: -16, size: 8, alignment: 16, stack-id: default, 
+      callee-saved-register: '', callee-saved-restored: true, debug-info-variable: '', 
+      debug-info-expression: '', debug-info-location: '' }
+stack:
+  - { id: 0, name: '', type: default, offset: -24, size: 4, alignment: 4, 
+      stack-id: default, callee-saved-register: '', callee-saved-restored: true, 
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+  - { id: 1, name: '', type: default, offset: -17, size: 1, alignment: 1, 
+      stack-id: default, callee-saved-register: '', callee-saved-restored: true, 
+      debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
+callSites:       []
+debugValueSubstitutions: []
+constants:       []
+machineFunctionInfo: {}
+body:             |
+  bb.0 (%ir-block.1, bb_id 0):
+    successors: %bb.2(0x40000000), %bb.1(0x40000000)
+    liveins: $edi
+  
+    frame-setup PUSH64r killed $rbp, implicit-def $rsp, implicit $rsp
+    frame-setup CFI_INSTRUCTION def_cfa_offset 16
+    frame-setup CFI_INSTRUCTION offset $rbp, -16
+    $rbp = frame-setup MOV64rr $rsp
+    frame-setup CFI_INSTRUCTION def_cfa_register $rbp
+    renamable $dil = AND8ri renamable $dil, 1, implicit-def dead $eflags, implicit killed $edi, implicit-def $edi
+    MOV8mr $rbp, 1, $noreg, -1, $noreg, renamable $dil, implicit killed $edi :: (store (s8) into %ir.3)
+    TEST8mi $rbp, 1, $noreg, -1, $noreg, 1, implicit-def $eflags :: (load (s8) from %ir.3)
+    JCC_1 %bb.2, 4, implicit killed $eflags
+  
+  bb.1 (%ir-block.7, bb_id 1):
+    successors: %bb.3(0x80000000)
+  
+    MOV32mi $rbp, 1, $noreg, -8, $noreg, 1 :: (store (s32) into %ir.2)
+    JMP_1 %bb.3
+  
+  bb.2 (%ir-block.8, bb_id 2):
+    successors: %bb.3(0x80000000)
+  
+    MOV32mi $rbp, 1, $noreg, -8, $noreg, 0 :: (store (s32) into %ir.2)
+  
+  bb.3 (%ir-block.9, bb_id 3):
+    renamable $eax = MOV32rm $rbp, 1, $noreg, -8, $noreg :: (load (s32) from %ir.2)
+    $rbp = frame-destroy POP64r implicit-def $rsp, implicit $rsp
+    frame-destroy CFI_INSTRUCTION def_cfa $rsp, 8
+    RET64 implicit $eax
+
+...

llvm/test/CodeGen/X86/basic-block-sections-mir-print.ll

 ; Stop after bbsections-prepare and check MIR output for section type.
+; RUN: llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basic-block-sections=labels -stop-after=bbsections-prepare | FileCheck %s -check-prefix=BBLABELS
 ; RUN: echo '!_Z3foob' > %t
 ; RUN: echo '!!1' >> %t
 ; RUN: echo '!!2' >> %t
-; RUN: llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basic-block-sections=%t -stop-after=bbsections-prepare | FileCheck %s -check-prefix=CHECK
+; RUN: llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basic-block-sections=%t -stop-after=bbsections-prepare | FileCheck %s -check-prefix=BBSECTIONS
 
 @_ZTIb = external constant ptr
 define dso_local i32 @_Z3foob(i1 zeroext %0) {
   %2 = alloca i32, align 4
   %3 = alloca i8, align 1
   %4 = zext i1 %0 to i8
   store i8 %4, ptr %3, align 1
   %5 = load i8, ptr %3, align 1
   %6 = trunc i8 %5 to i1
   br i1 %6, label %7, label %8
 
 7:                                                ; preds = %1
   store i32 1, ptr %2, align 4
   br label %9
 
 8:                                                ; preds = %1
   store i32 0, ptr %2, align 4
   br label %9
 
 9:                                                ; preds = %8, %7
   %10 = load i32, ptr %2, align 4
   ret i32 %10
 }
 
-; CHECK: bb.0 (%ir-block.1, bbsections Cold):
-; CHECK: bb.3 (%ir-block.9, bbsections Cold):
-; CHECK: bb.1 (%ir-block.7)
-; CHECK: bb.2 (%ir-block.8, bbsections 1):
+; BBSECTIONS: bb.0 (%ir-block.1, bbsections Cold, bb_id 0):
+; BBSECTIONS: bb.3 (%ir-block.9, bbsections Cold, bb_id 3):
+; BBSECTIONS: bb.1 (%ir-block.7, bb_id 1)
+; BBSECTIONS: bb.2 (%ir-block.8, bbsections 1, bb_id 2):
+
+; BBLABELS: bb.0 (%ir-block.1, bb_id 0):
+; BBLABELS: bb.1 (%ir-block.7, bb_id 1):
+; BBLABELS: bb.2 (%ir-block.8, bb_id 2):
+; BBLABELS: bb.3 (%ir-block.9, bb_id 3):

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

 
 # 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:         ID: 0
 # 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:         ID: 2
 # CHECK-NEXT:         Offset: 0x4
 # 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:         ID: 4
 # 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: ]
 
 # 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:         ID: 6
 # 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:         ID: 7
 # TRUNCATED-NEXT:         Offset: 0x1F
 # TRUNCATED-NEXT:         Size: 0xD
 # TRUNCATED-NEXT:         HasReturn: No
 # TRUNCATED-NEXT:         HasTailCall: Yes
 # TRUNCATED-NEXT:         IsEHPad: Yes
 # TRUNCATED-NEXT:         CanFallThrough: Yes
 # TRUNCATED-NEXT:       }
 # TRUNCATED-NEXT:     ]
Sections:
   - Name:   .text.bar
     Type:   SHT_PROGBITS
     Flags:  [SHF_ALLOC]
   - Name:   .llvm_bb_addr_map
     Type:   SHT_LLVM_BB_ADDR_MAP
     ShSize: [[SIZE=<none>]]
     Link:   .text
     Entries:
-      - Version: 1
+      - Version: 2
         Address: [[ADDR=0x11111]]
         BBEntries:
-          - AddressOffset: 0x0
+          - ID:            0
+            AddressOffset: 0x0
             Size:          0x1
             Metadata:      0xF0000002
-          - AddressOffset: 0x3
+          - ID:            2
+            AddressOffset: 0x3
             Size:          0x4
             Metadata:      0x5
-      - Version: 1
+      - Version: 2
         Address: 0x22222
         BBEntries:
-          - AddressOffset: 0x6
+          - ID:            4
+            AddressOffset: 0x6
             Size:          0x7
             Metadata:      0x8
   - Name: dummy_section
     Type: SHT_PROGBITS
     Size: 16
   - Name: '.llvm_bb_addr_map (1)'
     Type: SHT_LLVM_BB_ADDR_MAP
     Link: .text.bar
     Entries:
-      - Version: 1
+      - Version: 2
         Address: 0x33333
         BBEntries:
-          - AddressOffset: 0x9
+          - ID:            6
+            AddressOffset: 0x9
             Size:          0xa
             Metadata:      0xb
-          - AddressOffset: 0xc
+          - ID:            7
+            AddressOffset: 0xc
             Size:          0xd
             Metadata:      0xe
 Symbols:
   - Name:    foo
     Section: .text
     Type:    STT_FUNC
     Value:   0x22222
   - Name:    bar

 # RUN: llvm-readobj %t2.version0 --bb-addr-map 2>&1 | FileCheck %s --check-prefix=V0
 
 # V0:      BBAddrMap [
 # V0-NEXT:   Function {
 # V0-NEXT:     At:   0x11111
 # V0-NEXT:     Name: foo
 # V0-NEXT:     BB entries [
 # V0-NEXT:       {
+# V0-NEXT:         ID: 0
 # V0-NEXT:         Offset: 0x1
 # V0-NEXT:         Size: 0x2
 # V0-NEXT:         HasReturn:
 # V0-NEXT:         HasTailCall:
 # V0-NEXT:         IsEHPad:
 # V0-NEXT:         CanFallThrough:
 # V0-NEXT:       }
 # V0-NEXT:       {
+# V0-NEXT:         ID: 1
 # V0-NEXT:         Offset: 0x4
 # V0-NEXT:         Size: 0x5
 # V0-NEXT:         HasReturn:
 # V0-NEXT:         HasTailCall:
 # V0-NEXT:         IsEHPad:
 # V0-NEXT:         CanFallThrough:
 # V0-NEXT:       }
 # V0-NEXT:     ]
 # V0-NEXT:   }
 
+## Check version 1 (without BB IDs).
+# RUN: yaml2obj --docnum=2 %s -DVERSION=1 -DSECTION_TYPE=SHT_LLVM_BB_ADDR_MAP -o %t3
+# RUN: llvm-readobj %t3 --bb-addr-map 2>&1 | FileCheck %s --check-prefix=V1
+
+# V1:      BBAddrMap [
+# V1-NEXT:   Function {
+# V1-NEXT:     At:   0x11111
+# V1-NEXT:     Name: foo
+# V1-NEXT:     BB entries [
+# V1-NEXT:       {
+# V1-NEXT:         ID: 0
+# V1-NEXT:         Offset: 0x1
+# V1-NEXT:         Size: 0x2
+# V1-NEXT:         HasReturn:
+# V1-NEXT:         HasTailCall:
+# V1-NEXT:         IsEHPad:
+# V1-NEXT:         CanFallThrough:
+# V1-NEXT:       }
+# V1-NEXT:       {
+# V1-NEXT:         ID: 1
+# V1-NEXT:         Offset: 0x7
+# V1-NEXT:         Size: 0x5
+# V1-NEXT:         HasReturn:
+# V1-NEXT:         HasTailCall:
+# V1-NEXT:         IsEHPad:
+# V1-NEXT:         CanFallThrough:
+# V1-NEXT:       }
+# V1-NEXT:     ]
+# V1-NEXT:   }
+
 --- !ELF
 FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
   - Name:  .text.foo
     Type:  SHT_PROGBITS

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

 # VALID-NEXT:   Class: ELFCLASS64
 # VALID-NEXT:   Data:  ELFDATA2LSB
 # VALID-NEXT:   Type:  ET_EXEC
 # VALID-NEXT: Sections:
 # VALID-NEXT:   - Name: .llvm_bb_addr_map
 # VALID-NEXT:     Type: SHT_LLVM_BB_ADDR_MAP
 # VALID-NEXT:     Entries:
 ## The 'Address' field is omitted when it's zero.
-# VALID-NEXT:       - Version: 1
+# VALID-NEXT:       - Version: 2
 # VALID-NEXT:         Feature: 0xFF
 # VALID-NEXT:         BBEntries:
-# VALID-NEXT:           - AddressOffset: 0x1
+# VALID-NEXT:           - ID:            0
+# VALID-NEXT:             AddressOffset: 0x1
 # VALID-NEXT:             Size:          0x2
 # VALID-NEXT:             Metadata:      0x3
-# VALID-NEXT:           - AddressOffset: 0x4
+# VALID-NEXT:           - ID:            2
+# VALID-NEXT:             AddressOffset: 0x4
 # VALID-NEXT:             Size:          0x5
 # VALID-NEXT:             Metadata:      0x6
-# VALID-NEXT:           - AddressOffset: 0xFFFFFFFFFFFFFFF7
+# VALID-NEXT:           - ID:            4
+# VALID-NEXT:             AddressOffset: 0xFFFFFFFFFFFFFFF7
 # VALID-NEXT:             Size:          0xFFFFFFFFFFFFFFF8
 # VALID-NEXT:             Metadata:      0xFFFFFFFFFFFFFFF9
-# VALID-NEXT:       - Version: 1
+# VALID-NEXT:       - Version: 2
 # VALID-NEXT:         Feature: 0xEE
 # VALID-NEXT:         Address: 0xFFFFFFFFFFFFFF20
 # VALID-NEXT:         BBEntries:
-# VALID-NEXT:           - AddressOffset: 0xA
+# VALID-NEXT:           - ID:            6
+# VALID-NEXT:             AddressOffset: 0xA
 # VALID-NEXT:             Size:          0xB
 # VALID-NEXT:             Metadata:      0xC
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
   - Name:   .llvm_bb_addr_map
     Type:   SHT_LLVM_BB_ADDR_MAP
     ShSize: [[SIZE=<none>]]
     Entries:
-      - Version: 1
+      - Version: 2
         Feature: 0xFF
         Address: 0x0
         BBEntries:
-          - AddressOffset: 0x1
+          - ID:            0
+            AddressOffset: 0x1
             Size:          0x2
             Metadata:      0x3
-          - AddressOffset: 0x4
+          - ID:            2
+            AddressOffset: 0x4
             Size:          0x5
             Metadata:      0x6
-          - AddressOffset: 0xFFFFFFFFFFFFFFF7
+          - ID:            4
+            AddressOffset: 0xFFFFFFFFFFFFFFF7
             Size:          0xFFFFFFFFFFFFFFF8
             Metadata:      0xFFFFFFFFFFFFFFF9
-      - Version:   1
+      - Version:   2
         Feature:   0xEE
         Address:   0xFFFFFFFFFFFFFF20
         NumBlocks: [[NUMBLOCKS=<none>]]
         BBEntries:
-          - AddressOffset: 0xA
+          - ID:            6
+            AddressOffset: 0xA
             Size:          0xB
             Metadata:      0xC
 
 ## Check obj2yaml can dump empty .llvm_bb_addr_map sections.
 
 # RUN: yaml2obj --docnum=2 %s -o %t2
 # RUN: obj2yaml %t2 | FileCheck %s --check-prefix=EMPTY
 

 # 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:
 ## Fields 'Address' and 'Feature' are omitted when they are zero.
 # MULTI-NEXT:       - Version: 0
 # MULTI-NEXT:         BBEntries:
-# MULTI-NEXT:           - AddressOffset: 0x1
+# MULTI-NEXT:           - ID:            0
+# 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:       - Version:   0
 # MULTI-NEXT:         Address:   0x20
 # MULTI-NEXT:         BBEntries: []

 # V0-NEXT:   Type:  ET_EXEC
 # V0-NEXT: Sections:
 # V0-NEXT:   - Name: .llvm_bb_addr_map
 # V0-NEXT:     Type: SHT_LLVM_BB_ADDR_MAP_V0
 # V0-NEXT:     Entries:
 # V0-NEXT:       - Version: 0
 # V0-NEXT:         Address: 0x1111
 # V0-NEXT:         BBEntries:
-# V0-NEXT:           - AddressOffset: 0x1
+# V0-NEXT:           - ID:            0
+# V0-NEXT:             AddressOffset: 0x1
 # V0-NEXT:             Size:          0x2
 # V0-NEXT:             Metadata:      0x3
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
   - Name: .llvm_bb_addr_map
     Type: SHT_LLVM_BB_ADDR_MAP_V0
     Entries:
       - Version: 0
         Address: 0x1111
         BBEntries:
           - AddressOffset: 0x1
             Size:          0x2
             Metadata:      0x3
+
+## Check obj2yaml for version 1.
+# RUN: yaml2obj --docnum=5 %s -o %t7
+# RUN: obj2yaml %t7 | FileCheck %s --check-prefix=V1
+
+# V1:      --- !ELF
+# V1-NEXT: FileHeader:
+# V1-NEXT:   Class: ELFCLASS64
+# V1-NEXT:   Data:  ELFDATA2LSB
+# V1-NEXT:   Type:  ET_EXEC
+# V1-NEXT: Sections:
+# V1-NEXT:   - Name: .llvm_bb_addr_map
+# V1-NEXT:     Type: SHT_LLVM_BB_ADDR_MAP
+# V1-NEXT:     Entries:
+# V1-NEXT:       - Version: 1
+# V1-NEXT:         Address: 0x1111
+# V1-NEXT:         BBEntries:
+# V1-NEXT:           - ID:            0
+# V1-NEXT:             AddressOffset: 0x1
+# V1-NEXT:             Size:          0x2
+# V1-NEXT:             Metadata:      0x3
+# V1-NEXT:           - ID:            1
+# V1-NEXT:             AddressOffset: 0x4
+# V1-NEXT:             Size:          0x5
+# V1-NEXT:             Metadata:      0x6
+
+--- !ELF
+FileHeader:
+  Class: ELFCLASS64
+  Data:  ELFDATA2LSB
+  Type:  ET_EXEC
+Sections:
+  - Name: .llvm_bb_addr_map
+    Type: SHT_LLVM_BB_ADDR_MAP
+    Entries:
+      - Version: 1
+        Address: 0x1111
+        BBEntries:
+          - AddressOffset: 0x1
+            Size:          0x2
+            Metadata:      0x3
+          - AddressOffset: 0x4
+            Size:          0x5
+            Metadata:      0x6

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

 ## Check how yaml2obj produces .llvm_bb_addr_map sections.
 
 # RUN: yaml2obj --docnum=1 %s -o %t1
 # RUN: llvm-readobj --sections --section-data %t1 | FileCheck %s
 
 ## Case 1: Specify content.
 # CHECK:      Section {
 # CHECK:        Index: 1
 # CHECK-NEXT:   Name: .llvm_bb_addr_map (1)
 # CHECK-NEXT:   Type: SHT_LLVM_BB_ADDR_MAP (0x6FFF4C0A)
 # CHECK-NEXT:   Flags [ (0x0)
 # CHECK-NEXT:   ]
 # CHECK-NEXT:   Address: 0x0
 # CHECK-NEXT:   Offset: 0x40
-# CHECK-NEXT:   Size: 12
+# CHECK-NEXT:   Size: 13
 # CHECK-NEXT:   Link: 0
 # CHECK-NEXT:   Info: 0
 # CHECK-NEXT:   AddressAlignment: 0
 # CHECK-NEXT:   EntrySize: 0
 # CHECK-NEXT:   SectionData (
-# CHECK-NEXT:     0000: 00000000 00000000 01010203
+# CHECK-NEXT:     0000: 00000000 00000000 01010203 04
 # CHECK-NEXT:   )
 # CHECK-NEXT: }
 
 ## Case 2: Empty.
 # CHECK:        Name: .llvm_bb_addr_map (1)
 # CHECK:        Size:
 # CHECK-SAME:   {{^ 0$}}
 
 ## Case 3: Specify Size only.
 # CHECK:        Name: .llvm_bb_addr_map (1)
 # CHECK:        SectionData (
 # CHECK-NEXT:     0000: 00000000 00000000
 # CHECK-NEXT:   )
 
 # Case 4: Specify Entries.
 # CHECK:        Name: .llvm_bb_addr_map (1)
 # CHECK:        SectionData (
-# CHECK-NEXT:     0000: 01002000 00000000 00000101 0203
+# CHECK-NEXT:     0000: 02002000 00000000 0000010B 010203
 # CHECK-NEXT:   )
 
 # Case 5: Specify Entries and omit the Address field.
 # CHECK:        Name: .llvm_bb_addr_map (1)
 # CHECK:        Address:
 # CHECK-SAME:   {{^ 0x0$}}
 # CHECK:        SectionData (
-# CHECK-NEXT:     0000: 00000000 00000000 00000101 0203
+# CHECK-NEXT:     0000: 02000000 00000000 0000010C 010203
 # CHECK-NEXT:   )
 
 # Case 6: Override the NumBlocks field.
 # CHECK:        Name: .llvm_bb_addr_map (1)
 # CHECK:        SectionData (
-# CHECK-NEXT:     0000: 01002000 00000000 00000201 0203
+# CHECK-NEXT:     0000: 02002000 00000000 0000020D 010203
 # CHECK-NEXT:   )
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
 
 ## Test the following cases:
 
 ## 1) We can produce an .llvm_bb_addr_map section from a description with section
 ##    content.
 ##  Specify Content.
   - Name:    '.llvm_bb_addr_map (1)'
     Type:    SHT_LLVM_BB_ADDR_MAP
-    Content: "000000000000000001010203"
+    Content: "00000000000000000101020304"
 
 ## 2) We can produce an empty .llvm_bb_addr_map section from a description
 ##    with empty section content.
   - Name: '.llvm_bb_addr_map (2)'
     Type: SHT_LLVM_BB_ADDR_MAP
 
 ## 3) We can produce a zero .llvm_bb_addr_map section of a specific size when
 ##    we specify the size only.
   - Name: '.llvm_bb_addr_map (3)'
     Type: SHT_LLVM_BB_ADDR_MAP
     Size: 8
 
 ## 4) We can produce an .llvm_bb_addr_map section from a description with
 ##    Entries.
   - Name: '.llvm_bb_addr_map (4)'
     Type: SHT_LLVM_BB_ADDR_MAP
     Entries:
-      - Version: 1
+      - Version: 2
         Address: 0x0000000000000020
         BBEntries:
-          - AddressOffset: 0x00000001
+          - ID:            11
+            AddressOffset: 0x00000001
             Size:          0x00000002
             Metadata:      0x00000003
 
 ## 5) When specifying the description with Entries, the 'Address' field will be
 ##    zero when omitted.
   - Name: '.llvm_bb_addr_map (5)'
     Type: SHT_LLVM_BB_ADDR_MAP
     Entries:
-      - Version: 0
+      - Version: 2
         BBEntries:
-          - AddressOffset: 0x00000001
+          - ID:            12
+            AddressOffset: 0x00000001
             Size:          0x00000002
             Metadata:      0x00000003
 
 ## 6) We can override the NumBlocks field with a value different from the
 ##    actual number of BB Entries.
   - Name: '.llvm_bb_addr_map (6)'
     Type: SHT_LLVM_BB_ADDR_MAP
     Entries:
-      - Version:   1
+      - Version:   2
         Address:   0x0000000000000020
         NumBlocks: 2
         BBEntries:
-          - AddressOffset: 0x00000001
+          - ID:            13
+            AddressOffset: 0x00000001
             Size:          0x00000002
             Metadata:      0x00000003
 
 ## Check we can't use Entries at the same time as either Content or Size.
 # RUN: not yaml2obj --docnum=2 -DCONTENT="00" %s 2>&1 | FileCheck %s --check-prefix=INVALID
 # RUN: not yaml2obj --docnum=2 -DSIZE="0" %s 2>&1 | FileCheck %s --check-prefix=INVALID
 
 # INVALID: error: "Entries" cannot be used with "Content" or "Size"
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
 ##  Specify Content and Size
   - Name:    '.llvm_bb_addr_map'
     Type:    SHT_LLVM_BB_ADDR_MAP
     Entries: []
     Content: [[CONTENT=<none>]]
     Size:    [[SIZE=<none>]]
 
 ## Check that yaml2obj generates a warning when we use unsupported versions.
 # RUN: yaml2obj --docnum=3  %s 2>&1 | FileCheck %s --check-prefix=INVALID-VERSION
-# INVALID-VERSION: warning: unsupported SHT_LLVM_BB_ADDR_MAP version: 2; encoding using the most recent version
+# INVALID-VERSION: warning: unsupported SHT_LLVM_BB_ADDR_MAP version: 3; encoding using the most recent version
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
   - Name: '.llvm_bb_addr_map'
     Type: SHT_LLVM_BB_ADDR_MAP
     Entries:
 ##  Specify unsupported version
-      - Version: 2
+      - Version: 3

llvm/tools/llvm-readobj/ELFDumper.cpp

for (const BBAddrMap &AM : *BBAddrMapOrErr) {
             Twine::utohexstr(AM.Addr) + ") in " + this->describe(Sec));
       else
         FuncName = this->getStaticSymbolName(FuncSymIndex.front());
       W.printString("Name", FuncName);
 
       ListScope L(W, "BB entries");
       for (const BBAddrMap::BBEntry &BBE : AM.BBEntries) {
         DictScope L(W);
+        W.printNumber("ID", BBE.ID);
         W.printHex("Offset", BBE.Offset);
         W.printHex("Size", BBE.Size);
         W.printBoolean("HasReturn", BBE.HasReturn);
         W.printBoolean("HasTailCall", BBE.HasTailCall);
         W.printBoolean("IsEHPad", BBE.IsEHPad);
         W.printBoolean("CanFallThrough", BBE.CanFallThrough);
       }
     }

llvm/tools/obj2yaml/elf2yaml.cpp

ELFDumper<ELFT>::dumpBBAddrMapSection(const Elf_Shdr *Shdr) {
 
   std::vector<ELFYAML::BBAddrMapEntry> Entries;
   DataExtractor::Cursor Cur(0);
   uint8_t Version = 0;
   uint8_t Feature = 0;
   while (Cur && Cur.tell() < Content.size()) {
     if (Shdr->sh_type == ELF::SHT_LLVM_BB_ADDR_MAP) {
       Version = Data.getU8(Cur);
-      if (Cur && Version > 1)
+      if (Cur && Version > 2)
         return createStringError(
             errc::invalid_argument,
             "invalid SHT_LLVM_BB_ADDR_MAP section version: " +
                 Twine(static_cast<int>(Version)));
       Feature = Data.getU8(Cur);
     }
     uint64_t Address = Data.getAddress(Cur);
     uint64_t NumBlocks = Data.getULEB128(Cur);
     std::vector<ELFYAML::BBAddrMapEntry::BBEntry> BBEntries;
     // Read the specified number of BB entries, or until decoding fails.
-    for (uint64_t BlockID = 0; Cur && BlockID < NumBlocks; ++BlockID) {
+    for (uint64_t BlockIndex = 0; Cur && BlockIndex < NumBlocks; ++BlockIndex) {
+      uint32_t ID = Version >= 2 ? Data.getULEB128(Cur) : BlockIndex;
       uint64_t Offset = Data.getULEB128(Cur);
       uint64_t Size = Data.getULEB128(Cur);
       uint64_t Metadata = Data.getULEB128(Cur);
-      BBEntries.push_back({Offset, Size, Metadata});
+      BBEntries.push_back({ID, Offset, Size, Metadata});
     }
     Entries.push_back(
         {Version, Feature, Address, /*NumBlocks=*/{}, std::move(BBEntries)});
   }
 
   if (!Cur) {
     // If the section cannot be decoded, we dump it as an array of bytes.
     consumeError(Cur.takeError());

llvm/unittests/Object/ELFObjectFileTest.cpp

auto DoCheck = [&](StringRef YamlString, const char *ErrMsg) {
     ASSERT_THAT_EXPECTED(BBAddrMapSecOrErr, Succeeded());
     EXPECT_THAT_ERROR(Elf.decodeBBAddrMap(**BBAddrMapSecOrErr).takeError(),
                       FailedWithMessage(ErrMsg));
   };
 
   // Check that we can detect unsupported versions.
   SmallString<128> UnsupportedVersionYamlString(CommonYamlString);
   UnsupportedVersionYamlString += R"(
-        Version: 2
+        Version: 3
         BBEntries:
           - AddressOffset: 0x0
             Size:          0x1
             Metadata:      0x2
 )";
 
   DoCheck(UnsupportedVersionYamlString,
-          "unsupported SHT_LLVM_BB_ADDR_MAP version: 2");
+          "unsupported SHT_LLVM_BB_ADDR_MAP version: 3");
 
   SmallString<128> CommonVersionedYamlString(CommonYamlString);
   CommonVersionedYamlString += R"(
-        Version: 1
+        Version: 2
         BBEntries:
-          - AddressOffset: 0x0
+          - ID:            1
+            AddressOffset: 0x0
             Size:          0x1
             Metadata:      0x2
 )";
 
   // Check that we can detect the malformed encoding when the section is
   // truncated.
   SmallString<128> TruncatedYamlString(CommonVersionedYamlString);
   TruncatedYamlString += R"(
-    ShSize: 0xa
+    ShSize: 0xb
 )";
-  DoCheck(TruncatedYamlString, "unable to decode LEB128 at offset 0x0000000a: "
+  DoCheck(TruncatedYamlString, "unable to decode LEB128 at offset 0x0000000b: "
                                "malformed uleb128, extends past end");
 
   // Check that we can detect when the encoded BB entry fields exceed the UINT32
   // limit.
   SmallVector<SmallString<128>, 3> OverInt32LimitYamlStrings(
       3, CommonVersionedYamlString);
   OverInt32LimitYamlStrings[0] += R"(
-          - AddressOffset: 0x100000000
+          - ID:            1
+            AddressOffset: 0x100000000
             Size:          0xFFFFFFFF
             Metadata:      0xFFFFFFFF
 )";
 
   OverInt32LimitYamlStrings[1] += R"(
-          - AddressOffset: 0xFFFFFFFF
+          - ID:            2
+            AddressOffset: 0xFFFFFFFF
             Size:          0x100000000
             Metadata:      0xFFFFFFFF
 )";
 
   OverInt32LimitYamlStrings[2] += R"(
-          - AddressOffset: 0xFFFFFFFF
+          - ID:            3
+            AddressOffset: 0xFFFFFFFF
             Size:          0xFFFFFFFF
             Metadata:      0x100000000
 )";
 
   DoCheck(OverInt32LimitYamlStrings[0],
-          "ULEB128 value at offset 0xe exceeds UINT32_MAX (0x100000000)");
+          "ULEB128 value at offset 0x10 exceeds UINT32_MAX (0x100000000)");
   DoCheck(OverInt32LimitYamlStrings[1],
-          "ULEB128 value at offset 0x13 exceeds UINT32_MAX (0x100000000)");
+          "ULEB128 value at offset 0x15 exceeds UINT32_MAX (0x100000000)");
   DoCheck(OverInt32LimitYamlStrings[2],
-          "ULEB128 value at offset 0x18 exceeds UINT32_MAX (0x100000000)");
+          "ULEB128 value at offset 0x1a exceeds UINT32_MAX (0x100000000)");
 
   // Check the proper error handling when the section has fields exceeding
   // UINT32 and is also truncated. This is for checking that we don't generate
   // unhandled errors.
   SmallVector<SmallString<128>, 3> OverInt32LimitAndTruncated(
       3, OverInt32LimitYamlStrings[1]);
   // Truncate before the end of the 5-byte field.
   OverInt32LimitAndTruncated[0] += R"(
-    ShSize: 0x17
+    ShSize: 0x19
 )";
   // Truncate at the end of the 5-byte field.
   OverInt32LimitAndTruncated[1] += R"(
-    ShSize: 0x18
+    ShSize: 0x1a
 )";
   // Truncate after the end of the 5-byte field.
   OverInt32LimitAndTruncated[2] += R"(
-    ShSize: 0x19
+    ShSize: 0x1b
 )";
 
   DoCheck(OverInt32LimitAndTruncated[0],
-          "unable to decode LEB128 at offset 0x00000013: malformed uleb128, "
+          "unable to decode LEB128 at offset 0x00000015: malformed uleb128, "
           "extends past end");
   DoCheck(OverInt32LimitAndTruncated[1],
-          "ULEB128 value at offset 0x13 exceeds UINT32_MAX (0x100000000)");
+          "ULEB128 value at offset 0x15 exceeds UINT32_MAX (0x100000000)");
   DoCheck(OverInt32LimitAndTruncated[2],
-          "ULEB128 value at offset 0x13 exceeds UINT32_MAX (0x100000000)");
+          "ULEB128 value at offset 0x15 exceeds UINT32_MAX (0x100000000)");
 
   // Check for proper error handling when the 'NumBlocks' field is overridden
   // with an out-of-range value.
   SmallString<128> OverLimitNumBlocks(CommonVersionedYamlString);
   OverLimitNumBlocks += R"(
         NumBlocks: 0x100000000
 )";
 
FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
   - Name: .llvm_bb_addr_map_1
     Type: SHT_LLVM_BB_ADDR_MAP
     Link: 1
     Entries:
-      - Version: 1
+      - Version: 2
         Address: 0x11111
         BBEntries:
-          - AddressOffset: 0x0
+          - ID:            1
+            AddressOffset: 0x0
             Size:          0x1
             Metadata:      0x2
   - Name: .llvm_bb_addr_map_2
     Type: SHT_LLVM_BB_ADDR_MAP
     Link: 1
     Entries:
-      - Version: 1
+      - Version: 2
         Address: 0x22222
         BBEntries:
-          - AddressOffset: 0x0
+          - ID:            2
+            AddressOffset: 0x0
             Size:          0x2
             Metadata:      0x4
-  - Name: .llvm_bb_addr_map
-    Type: SHT_LLVM_BB_ADDR_MAP_V0
-  # Link: 0 (by default)
+  - Name: .llvm_bb_addr_map_3
+    Type: SHT_LLVM_BB_ADDR_MAP
+    Link: 2
     Entries:
-      - Version: 0
+      - Version: 1
         Address: 0x33333
         BBEntries:
-          - AddressOffset: 0x0
+          - ID:            0
+            AddressOffset: 0x0
             Size:          0x3
             Metadata:      0x6
+  - Name: .llvm_bb_addr_map_4
+    Type: SHT_LLVM_BB_ADDR_MAP_V0
+  # Link: 0 (by default, can be overriden)
+    Entries:
+      - Version: 0
+        Address: 0x44444
+        BBEntries:
+          - ID:            0
+            AddressOffset: 0x0
+            Size:          0x4
+            Metadata:      0x8
 )");
 
-  BBAddrMap E1 = {0x11111, {{0x0, 0x1, 0x2}}};
-  BBAddrMap E2 = {0x22222, {{0x0, 0x2, 0x4}}};
-  BBAddrMap E3 = {0x33333, {{0x0, 0x3, 0x6}}};
-
-  std::vector<BBAddrMap> Section0BBAddrMaps = {E3};
-  std::vector<BBAddrMap> Section1BBAddrMaps = {E1, E2};
-  std::vector<BBAddrMap> AllBBAddrMaps = {E1, E2, E3};
+  BBAddrMap E1 = {0x11111, {{1, 0x0, 0x1, 0x2}}};
+  BBAddrMap E2 = {0x22222, {{2, 0x0, 0x2, 0x4}}};
+  BBAddrMap E3 = {0x33333, {{0, 0x0, 0x3, 0x6}}};
+  BBAddrMap E4 = {0x44444, {{0, 0x0, 0x4, 0x8}}};
+
+  std::vector<BBAddrMap> Section0BBAddrMaps = {E4};
+  std::vector<BBAddrMap> Section1BBAddrMaps = {E3};
+  std::vector<BBAddrMap> Section2BBAddrMaps = {E1, E2};
+  std::vector<BBAddrMap> AllBBAddrMaps = {E1, E2, E3, E4};
 
   auto DoCheckSucceeds = [&](StringRef YamlString,
                              std::optional<unsigned> TextSectionIndex,
                              std::vector<BBAddrMap> ExpectedResult) {
     SmallString<0> Storage;
     Expected<ELFObjectFile<ELF64LE>> ElfOrErr =
         toBinary<ELF64LE>(Storage, YamlString);
     ASSERT_THAT_EXPECTED(ElfOrErr, Succeeded());
auto DoCheckFails = [&](StringRef YamlString,
     EXPECT_THAT_ERROR(ElfOrErr->readBBAddrMap(TextSectionIndex).takeError(),
                       FailedWithMessage(ErrMsg));
   };
 
   // Check that we can retrieve the data in the normal case.
   DoCheckSucceeds(CommonYamlString, /*TextSectionIndex=*/std::nullopt,
                   AllBBAddrMaps);
   DoCheckSucceeds(CommonYamlString, /*TextSectionIndex=*/0, Section0BBAddrMaps);
-  DoCheckSucceeds(CommonYamlString, /*TextSectionIndex=*/1, Section1BBAddrMaps);
+  DoCheckSucceeds(CommonYamlString, /*TextSectionIndex=*/2, Section1BBAddrMaps);
+  DoCheckSucceeds(CommonYamlString, /*TextSectionIndex=*/1, Section2BBAddrMaps);
   // Check that when no bb-address-map section is found for a text section,
   // we return an empty result.
-  DoCheckSucceeds(CommonYamlString, /*TextSectionIndex=*/2, {});
+  DoCheckSucceeds(CommonYamlString, /*TextSectionIndex=*/3, {});
 
   // Check that we detect when a bb-addr-map section is linked to an invalid
   // (not present) section.
   SmallString<128> InvalidLinkedYamlString(CommonYamlString);
   InvalidLinkedYamlString += R"(
     Link: 10
 )";
 
-  DoCheckFails(InvalidLinkedYamlString, /*TextSectionIndex=*/1,
+  DoCheckFails(InvalidLinkedYamlString, /*TextSectionIndex=*/4,
                "unable to get the linked-to section for "
-               "SHT_LLVM_BB_ADDR_MAP_V0 section with index 3: invalid section "
+               "SHT_LLVM_BB_ADDR_MAP_V0 section with index 4: invalid section "
                "index: 10");
   // Linked sections are not checked when we don't target a specific text
   // section.
   DoCheckSucceeds(InvalidLinkedYamlString, /*TextSectionIndex=*/std::nullopt,
                   AllBBAddrMaps);
 
   // Check that we can detect when bb-address-map decoding fails.
   SmallString<128> TruncatedYamlString(CommonYamlString);
   TruncatedYamlString += R"(
     ShSize: 0x8
 )";
 
   DoCheckFails(TruncatedYamlString, /*TextSectionIndex=*/std::nullopt,
-               "unable to read SHT_LLVM_BB_ADDR_MAP_V0 section with index 3: "
+               "unable to read SHT_LLVM_BB_ADDR_MAP_V0 section with index 4: "
                "unable to decode LEB128 at offset 0x00000008: malformed "
                "uleb128, extends past end");
   // Check that we can read the other section's bb-address-maps which are
   // valid.
-  DoCheckSucceeds(TruncatedYamlString, /*TextSectionIndex=*/1,
+  DoCheckSucceeds(TruncatedYamlString, /*TextSectionIndex=*/2,
                   Section1BBAddrMaps);
 }
 
 // Test for ObjectFile::getRelocatedSection: check that it returns a relocated
 // section for executable and relocatable files.
 TEST(ELFObjectFileTest, ExecutableWithRelocs) {
   StringRef HeaderString(R"(
 --- !ELF