[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

165

llvm/lib/CodeGen/MIRParser/MIParser.cpp

643

[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

35 ↗

(On Diff #466567)

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

llvm/lib/CodeGen/BasicBlockSections.cpp

220

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.

257–258

[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

257–258

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

296–299

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

296–299

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

367

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

1144

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

220

Please fix this too.

269

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

290

Why did you remove the 4 here?

367

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

379

extra line.

llvm/lib/CodeGen/MachineBasicBlock.cpp

1637

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

llvm/lib/CodeGen/MachineFunction.cpp

418

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

220

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

269

Please fix this too.

[rahmanl]

• Final comments.

[rahmanl]

Thanks Sri.

llvm/lib/CodeGen/BasicBlockSections.cpp

220

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

269

Added a single TODO in MachineBasicBlock.h.

290

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

llvm/lib/CodeGen/MachineBasicBlock.cpp

1637

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/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;
 
+  /// Propeller ID assigned to this basic block. used with basic block sections
+  /// and basic block labels.
+  Optional<unsigned> PropellerID;
+
   /// 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;
#endif
 
   /// 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> getPropellerID() const { return PropellerID; }
+
   /// 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;
   }
 
+  void setPropellerID(unsigned V) { PropellerID = 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 MachineFunction {
   std::vector<std::pair<MCSymbol *, MDNode *>> CodeViewAnnotations;
 
   bool CallsEHReturn = false;
   bool CallsUnwindInit = false;
   bool HasEHCatchret = false;
   bool HasEHScopes = false;
   bool HasEHFunclets = false;
 
+  unsigned NextPropellerID = 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

 };
 
 // Struct representing the BBAddrMap for one function.
 template <class ELFT> struct Elf_BBAddrMap_Impl {
   LLVM_ELF_IMPORT_TYPES_ELFT(ELFT)
   uintX_t Addr; // Function address
   // Struct representing the BBAddrMap information for one basic block.
   struct BBEntry {
+    uint32_t ID;     // Propeller ID.
     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)){};
   };
   std::vector<BBEntry> BBEntries; // Basic block entries for this function.
 };
 
 } // end namespace object.
 } // end namespace llvm.
 
 #endif // LLVM_OBJECT_ELFTYPES_H

llvm/include/llvm/ObjectYAML/ELFYAML.h

 
 struct DynamicEntry {
   ELF_DYNTAG Tag;
   llvm::yaml::Hex64 Val;
 };
 
 struct BBAddrMapEntry {
   struct BBEntry {
+    uint32_t PropellerID;
     llvm::yaml::Hex64 AddressOffset;
     llvm::yaml::Hex64 Size;
     llvm::yaml::Hex64 Metadata;
   };
   llvm::yaml::Hex64 Address;
   Optional<uint64_t> NumBlocks;
   Optional<std::vector<BBEntry>> BBEntries;
 };

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

void AsmPrinter::emitBBAddrMapSection(const MachineFunction &MF) {
   OutStreamer->SwitchSection(BBAddrMapSection);
   OutStreamer->emitSymbolValue(FunctionSymbol, getPointerSize());
   // Emit the total number of basic blocks in this function.
   OutStreamer->emitULEB128IntValue(MF.size());
   // Emit BB Information for each basic block in the funciton.
   for (const MachineBasicBlock &MBB : MF) {
     const MCSymbol *MBBSymbol =
         MBB.isEntryBlock() ? FunctionSymbol : MBB.getSymbol();
+    OutStreamer->AddComment("Propeller ID");
+    // Emit the Propeller ID for this basic block.
+    OutStreamer->emitULEB128IntValue(*MBB.getPropellerID());
     // Emit the basic block offset.
     emitLabelDifferenceAsULEB128(MBBSymbol, FunctionSymbol);
     // 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));
   }
   OutStreamer->PopSection();
 }
 
 void AsmPrinter::emitPseudoProbe(const MachineInstr &MI) {
   auto GUID = MI.getOperand(0).getImm();
   auto Index = MI.getOperand(1).getImm();

llvm/lib/CodeGen/BasicBlockSections.cpp

cl::opt<bool> BBSectionsDetectSourceDrift(
     cl::desc("This checks if there is a fdo instr. profile hash "
              "mismatch for this function"),
     cl::init(true), cl::Hidden);
 
 namespace {
 
 // This struct represents the cluster information for a machine basic block.
 struct BBClusterInfo {
-  // MachineBasicBlock ID.
-  unsigned MBBNumber;
+  // MachineBasicBlock Propeller ID.
+  unsigned PropellerID;
   // Cluster ID this basic block belongs to.
   unsigned ClusterID;
   // Position of basic block within the cluster.
   unsigned PositionInCluster;
 };
 
 using ProgramBBClusterInfoMapTy = StringMap<SmallVector<BBClusterInfo, 4>>;
 

 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,
+               DenseMap<const MachineBasicBlock *, 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()];
+    auto *FTMBB = PreLayoutFallThroughs[&MBB];
     // 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
     //        reorderd by the linker, or
     //     2- the fallthrough block is not adjacent to the block in the new
     //        order.
     if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB))
       TII->insertUnconditionalBranch(MBB, FTMBB, MBB.findBranchDebugLoc());
static bool getBBClusterInfoForFunction(
 
   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;
-  }
+  unsigned MaxPropellerID = 0;
+  for (auto bbClusterInfo : P->second)
+    if (bbClusterInfo.PropellerID > MaxPropellerID)
+      MaxPropellerID = bbClusterInfo.PropellerID;
+  V.resize(MaxPropellerID + 1);
+  for (auto bbClusterInfo : P->second)
+    V[bbClusterInfo.PropellerID] = bbClusterInfo;
   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) {
+static void assignSections(
+    MachineFunction &MF,
+    const std::vector<Optional<BBClusterInfo>> &FuncBBClusterInfo,
+    const DenseMap<const MachineBasicBlock *, unsigned> &PreLayoutPosition) {
   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.
   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()].hasValue())
-      MBB.setSectionID(FuncBBClusterInfo[MBB.getNumber()]->ClusterID);
+      MBB.setSectionID(PreLayoutPosition.lookup(&MBB));
+    } else if (*MBB.getPropellerID() < FuncBBClusterInfo.size() &&
+               FuncBBClusterInfo[*MBB.getPropellerID()].hasValue())
+      MBB.setSectionID(FuncBBClusterInfo[*MBB.getPropellerID()]->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.hasValue()
                             ? 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.getValue());
 }
 
 void llvm::sortBasicBlocksAndUpdateBranches(
     MachineFunction &MF, MachineBasicBlockComparator MBBCmp) {
-  SmallVector<MachineBasicBlock *, 4> PreLayoutFallThroughs(
-      MF.getNumBlockIDs());
+  const MachineBasicBlock *EntryBlock = &MF.front();
+  DenseMap<const MachineBasicBlock *, MachineBasicBlock *>
+      PreLayoutFallThroughs;
   for (auto &MBB : MF)
-    PreLayoutFallThroughs[MBB.getNumber()] = MBB.getFallThrough();
+    PreLayoutFallThroughs[&MBB] = MBB.getFallThrough();
 
   MF.sort(MBBCmp);
+  // Check that the entry block is not displaced.
+  assert(&MF.front() == EntryBlock);
 
   // 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) {
   // 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.
-  MF.RenumberBlocks();
+  DenseMap<const MachineBasicBlock *, unsigned> PreLayoutPosition;
+  unsigned Position = 0;
+  for (const auto &MBB : MF)
+    PreLayoutPosition[&MBB] = Position++;
 
   if (BBSectionsType == BasicBlockSection::Labels) {
     MF.setBBSectionsType(BBSectionsType);
     return true;
   }
 
   std::vector<Optional<BBClusterInfo>> FuncBBClusterInfo;
   if (BBSectionsType == BasicBlockSection::List &&
       !getBBClusterInfoForFunction(MF, FuncAliasMap, ProgramBBClusterInfo,
                                    FuncBBClusterInfo))
     return true;
   MF.setBBSectionsType(BBSectionsType);
-  assignSections(MF, FuncBBClusterInfo);
+  assignSections(MF, FuncBBClusterInfo, PreLayoutPosition);
 
   // 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).
   //   * Regular sections (in increasing order of their Number).
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 X.getNumber() < Y.getNumber();
+      return FuncBBClusterInfo[*X.getPropellerID()]->PositionInCluster <
+             FuncBBClusterInfo[*Y.getPropellerID()]->PositionInCluster;
+    return PreLayoutPosition[&X] < PreLayoutPosition[&Y];
   };
 
   sortBasicBlocksAndUpdateBranches(MF, Comparator);
   avoidZeroOffsetLandingPad(MF);
   return true;
 }
 
 // Basic Block Sections can be enabled for a subset of machine basic blocks.
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_successors,
     kw_floatpred,
     kw_intpred,
     kw_shufflemask,
     kw_pre_instr_symbol,
     kw_post_instr_symbol,
     kw_heap_alloc_marker,
     kw_bbsections,
+    kw_propeller_id,
     kw_unknown_size,
     kw_unknown_address,
 
     // Named metadata keywords
     md_tbaa,
     md_alias_scope,
     md_noalias,
     md_range,

llvm/lib/CodeGen/MIRParser/MILexer.cpp

return StringSwitch<MIToken::TokenKind>(Identifier)
       .Case("successors", MIToken::kw_successors)
       .Case("floatpred", MIToken::kw_floatpred)
       .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("bbsections", MIToken::kw_bbsections)
+      .Case("propeller_id", MIToken::kw_propeller_id)
       .Case("unknown-size", MIToken::kw_unknown_size)
       .Case("unknown-address", MIToken::kw_unknown_address)
       .Default(MIToken::Identifier);
 }
 
 static Cursor maybeLexIdentifier(Cursor C, MIToken &Token) {
   if (!isalpha(C.peek()) && C.peek() != '_')
     return None;

llvm/lib/CodeGen/MIRParser/MIParser.cpp

public:
   bool parseMachineOperandAndTargetFlags(const unsigned OpCode,
                                          const unsigned OpIdx,
                                          MachineOperand &Dest,
                                          Optional<unsigned> &TiedDefIdx);
   bool parseOffset(int64_t &Offset);
   bool parseAlignment(unsigned &Alignment);
   bool parseAddrspace(unsigned &Addrspace);
   bool parseSectionID(Optional<MBBSectionID> &SID);
+  bool parsePropellerID(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 Propeller ID
+bool MIParser::parsePropellerID(Optional<unsigned> &PrID) {
+  assert(Token.is(MIToken::kw_propeller_id));
+  lex();
+  unsigned Value = 0;
+  if (getUnsigned(Value))
+    return error("Unknown Propeller ID");
+  PrID = 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 HasAddressTaken = false;
   bool IsLandingPad = false;
   bool IsEHFuncletEntry = false;
   Optional<MBBSectionID> SectionID;
+  Optional<unsigned> PropellerID;
   unsigned Alignment = 0;
   BasicBlock *BB = nullptr;
   if (consumeIfPresent(MIToken::lparen)) {
     do {
       // TODO: Report an error when multiple same attributes are specified.
       switch (Token.kind()) {
       case MIToken::kw_address_taken:
         HasAddressTaken = true;
do {
         if (parseIRBlock(BB, MF.getFunction()))
           return true;
         lex();
         break;
       case MIToken::kw_bbsections:
         if (parseSectionID(SectionID))
           return true;
         break;
+      case MIToken::kw_propeller_id:
+        if (parsePropellerID(PropellerID))
+          return true;
+        break;
       default:
         break;
       }
     } while (consumeIfPresent(MIToken::comma));
     if (expectAndConsume(MIToken::rparen))
       return true;
   }
   if (expectAndConsume(MIToken::colon))
bool MIParser::parseBasicBlockDefinition(
   if (HasAddressTaken)
     MBB->setHasAddressTaken();
   MBB->setIsEHPad(IsLandingPad);
   MBB->setIsEHFuncletEntry(IsEHFuncletEntry);
   if (SectionID.hasValue()) {
     MBB->setSectionID(SectionID.getValue());
     MF.setBBSectionsType(BasicBlockSection::List);
   }
+  if (PropellerID.hasValue()) {
+    // 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->setPropellerID(PropellerID.getValue());
+  }
   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 (getPropellerID().hasValue()) {
+      os << (hasAttributes ? ", " : " (");
+      os << "propeller_id " << *getPropellerID();
+      hasAttributes = true;
+    }
   }
 
   if (hasAttributes)
     os << ')';
 }
 
 void MachineBasicBlock::printAsOperand(raw_ostream &OS,
                                        bool /*PrintType*/) const {

 
 MachineBasicBlock::livein_iterator MachineBasicBlock::livein_begin() const {
   assert(getParent()->getProperties().hasProperty(
       MachineFunctionProperties::Property::TracksLiveness) &&
       "Liveness information is accurate");
   return LiveIns.begin();
 }
 
 const MBBSectionID MBBSectionID::ColdSectionID(MBBSectionID::SectionType::Cold);
 const MBBSectionID
     MBBSectionID::ExceptionSectionID(MBBSectionID::SectionType::Exception);

llvm/lib/CodeGen/MachineFunction.cpp

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->setPropellerID(NextPropellerID++);
+  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)

llvm/lib/Object/ELF.cpp

ELFFile<ELFT>::decodeBBAddrMap(const Elf_Shdr &Sec) const {
   };
 
   while (!ULEBSizeErr && Cur && Cur.tell() < Content.size()) {
     uintX_t Address = static_cast<uintX_t>(Data.getAddress(Cur));
     uint32_t NumBlocks = ReadULEB128AsUInt32();
     std::vector<typename Elf_BBAddrMap::BBEntry> BBEntries;
     for (uint32_t BlockID = 0; !ULEBSizeErr && Cur && (BlockID < NumBlocks);
          ++BlockID) {
+      uint32_t ID = ReadULEB128AsUInt32();
       uint32_t Offset = ReadULEB128AsUInt32();
       uint32_t Size = ReadULEB128AsUInt32();
       uint32_t Metadata = ReadULEB128AsUInt32();
-      BBEntries.push_back({Offset, Size, Metadata});
+      BBEntries.push_back({ID, 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/lib/ObjectYAML/ELFEmitter.cpp

for (const ELFYAML::BBAddrMapEntry &E : *Section.Entries) {
     // is overridden by the 'NumBlocks' YAML field when specified.
     uint64_t NumBlocks =
         E.NumBlocks.getValueOr(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)
-      SHeader.sh_size += CBA.writeULEB128(BBE.AddressOffset) +
+      SHeader.sh_size += CBA.writeULEB128(BBE.PropellerID) +
+                         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,

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.mapRequired("ID", E.PropellerID);
   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
+
+--- |
+  ; ModuleID = '<stdin>'
+  source_filename = "a.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: noinline nounwind optnone uwtable
+  define dso_local i32 @_Z3foob(i1 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 = { noinline nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+  
+  !llvm.module.flags = !{!0}
+  !llvm.ident = !{!1}
+  
+  !0 = !{i32 1, !"wchar_size", i32 4}
+  !1 = !{!"Debian clang version 11.0.1-2"}
+
+...
+---
+name:            _Z3foob
+alignment:       16
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+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:  ''
+  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, propeller_id 0):
+    successors: %bb.2(0x40000000), %bb.1(0x40000000)
+    liveins: $edi
+  
+    frame-setup PUSH64r killed $rbp, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 16
+    CFI_INSTRUCTION offset $rbp, -16
+    $rbp = frame-setup MOV64rr $rsp
+    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 1 into %ir.3)
+    TEST8mi $rbp, 1, $noreg, -1, $noreg, 1, implicit-def $eflags :: (load 1 from %ir.3)
+    JCC_1 %bb.2, 4, implicit killed $eflags
+  
+  bb.1 (%ir-block.7, propeller_id 1):
+    successors: %bb.3(0x80000000)
+  
+    MOV32mi $rbp, 1, $noreg, -8, $noreg, 1 :: (store 4 into %ir.2)
+    JMP_1 %bb.3
+  
+  bb.2 (%ir-block.8, propeller_id 2):
+    successors: %bb.3(0x80000000)
+  
+    MOV32mi $rbp, 1, $noreg, -8, $noreg, 0 :: (store 4 into %ir.2)
+  
+  bb.3 (%ir-block.9, propeller_id 3):
+    renamable $eax = MOV32rm $rbp, 1, $noreg, -8, $noreg :: (load 4 from %ir.2)
+    $rbp = frame-destroy POP64r implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa $rsp, 8
+    RETQ implicit $eax
+
+...
+
+# CHECK: .section .llvm_bb_addr_map,"o",@llvm_bb_addr_map,.text
+# CHECK: .byte  0 # Propeller ID
+# CHECK: .byte  1 # Propeller ID
+# CHECK: .byte  2 # Propeller ID
+# CHECK: .byte  3 # Propeller ID

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

 ; NOUNIQ:   .section .text,"ax",@progbits,unique,1
 ; CHECK-LABEL:  _Z3bazb:
 ; CHECK-LABEL:  .Lfunc_begin0:
 ; CHECK-LABEL:  .LBB_END0_0:
 ; 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:  .LBB0_4:
+; CHECK-LABEL:  .LBB_END0_4:
 ; CHECK-LABEL:  .Lfunc_end0:
 
 ; UNIQ:     .section  .llvm_bb_addr_map,"o",@llvm_bb_addr_map,.text._Z3bazb{{$}}
 ;; Verify that with -unique-section-names=false, the unique id of the text section gets assigned to the llvm_bb_addr_map section.
 ; NOUNIQ:   .section  .llvm_bb_addr_map,"o",@llvm_bb_addr_map,.text,unique,1
 ; CHECK-NEXT: .quad .Lfunc_begin0
 ; CHECK-NEXT: .byte 4
+; CHECK-NEXT: .byte 0
 ; CHECK-NEXT: .uleb128 .Lfunc_begin0-.Lfunc_begin0
 ; CHECK-NEXT: .uleb128 .LBB_END0_0-.Lfunc_begin0
 ; CHECK-NEXT: .byte 8
+; CHECK-NEXT: .byte 1
 ; CHECK-NEXT: .uleb128 .LBB0_1-.Lfunc_begin0
 ; CHECK-NEXT: .uleb128 .LBB_END0_1-.LBB0_1
 ; CHECK-NEXT: .byte 8
+; CHECK-NEXT: .byte 3
 ; CHECK-NEXT: .uleb128 .LBB0_2-.Lfunc_begin0
 ; CHECK-NEXT: .uleb128 .LBB_END0_2-.LBB0_2
 ; CHECK-NEXT: .byte 1
-; CHECK-NEXT: .uleb128 .LBB0_3-.Lfunc_begin0
-; CHECK-NEXT: .uleb128 .LBB_END0_3-.LBB0_3
+; CHECK-NEXT: .byte 2
+; CHECK-NEXT: .uleb128 .LBB0_4-.Lfunc_begin0
+; CHECK-NEXT: .uleb128 .LBB_END0_4-.LBB0_4
 ; CHECK-NEXT: .byte 5

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 i8*
 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, 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
 }
 
-; 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, propeller_id 0):
+; BBSECTIONS: bb.3 (%ir-block.9, bbsections Cold, propeller_id 3):
+; BBSECTIONS: bb.1 (%ir-block.7, propeller_id 1)
+; BBSECTIONS: bb.2 (%ir-block.8, bbsections 1, propeller_id 2):
+
+; BBLABELS: bb.0 (%ir-block.1, propeller_id 0):
+; BBLABELS: bb.1 (%ir-block.7, propeller_id 1):
+; BBLABELS: bb.2 (%ir-block.8, propeller_id 2):
+; BBLABELS: bb.3 (%ir-block.9, propeller_id 3):

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

 # 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:     BB entries [
 # LLVM-NEXT:       {
+# LLVM-NEXT:         ID: 0
 # 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:         ID: 2
 # 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:     BB entries [
 # LLVM-NEXT:       {
+# LLVM-NEXT:         ID: 4
 # 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:     BB entries [
 # LLVM-NEXT:       {
+# LLVM-NEXT:         ID: 6
 # 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: ]
 
 # GNU: GNUStyle::printBBAddrMaps not implemented
 
 # TRUNCATED:      BBAddrMap [
 # TRUNCATED-NEXT:   warning: '[[FILE]]': unable to dump SHT_LLVM_BB_ADDR_MAP section with index 1: 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:          BB entries [
-# TRUNCATED-NEXT:            {
+# TRUNCATED-NEXT:     At: 0x33333
+# 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:   }
 # TRUNCATED-NEXT: ]
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS[[BITS]]
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:
   - Name:   bb_addr_map_1
     Type:   SHT_LLVM_BB_ADDR_MAP
     ShSize: [[SIZE=<none>]]
     Entries:
       - Address: [[ADDR=0x11111]]
         BBEntries:
-          - AddressOffset: 0x0
+          - ID:            0
+            AddressOffset: 0x0
             Size:          0x1
             Metadata:      0xF0000002
-          - AddressOffset: 0x3
+          - ID:            2
+            AddressOffset: 0x3
             Size:          0x4
             Metadata:      0x5
       - Address: 0x22222
         BBEntries:
-          - AddressOffset: 0x6
+          - ID:            4
+            AddressOffset: 0x6
             Size:          0x7
             Metadata:      0x8
   - Name:   dummy_section
     Type:   SHT_PROGBITS
     Size:   16
   - Name:   bb_addr_map_2
     Type:   SHT_LLVM_BB_ADDR_MAP
     Entries:
       - Address: 0x33333
         BBEntries:
-          - AddressOffset: 0x9
+          - ID:            6
+            AddressOffset: 0x9
             Size:          0xa
             Metadata:      0xb

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

 # 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:         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:               1
+# VALID-NEXT:             AddressOffset:    0x4
 # VALID-NEXT:             Size:             0x5
 # VALID-NEXT:             Metadata:         0x6
-# VALID-NEXT:           - AddressOffset:    0xFFFFFFFFFFFFFFF7
+# VALID-NEXT:           - ID:               2
+# VALID-NEXT:             AddressOffset:    0xFFFFFFFFFFFFFFF7
 # VALID-NEXT:             Size:             0xFFFFFFFFFFFFFFF8
 # VALID-NEXT:             Metadata:         0xFFFFFFFFFFFFFFF9
 # VALID-NEXT:       - Address:   0xFFFFFFFFFFFFFF20
 # VALID-NEXT:         BBEntries:
-# VALID-NEXT:           - AddressOffset:    0xA
+# VALID-NEXT:           - ID:               3
+# 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:
       - Address:   0x0
         NumBlocks: [[NUMBLOCKS=<none>]]
         BBEntries:
           - AddressOffset:    0x1
+            ID:               0
             Size:             0x2
             Metadata:         0x3
           - AddressOffset:    0x4
+            ID:               1
             Size:             0x5
             Metadata:         0x6
           - AddressOffset:    0xFFFFFFFFFFFFFFF7
+            ID:               2
             Size:             0xFFFFFFFFFFFFFFF8
             Metadata:         0xFFFFFFFFFFFFFFF9
       - Address:   0xFFFFFFFFFFFFFF20
         BBEntries:
           - AddressOffset:    0xA
+            ID:               3
             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:   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:           - ID:              4
+# 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
+            ID:               4
             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

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

 # 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: 20000000 00000000 01010203
+# CHECK-NEXT:     0000: 20000000 00000000 010B0102 03
 # 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 01010203
+# CHECK-NEXT:     0000: 00000000 00000000 010C0102 03
 # CHECK-NEXT:   )
 
 # Case 6: Override the NumBlocks field.
 # CHECK:        Name: .llvm_bb_addr_map (1)
 # CHECK:        SectionData (
-# CHECK-NEXT:     0000: 20000000 00000000 02010203
+# CHECK-NEXT:     0000: 20000000 00000000 020D0102 03
 # CHECK-NEXT:   )
 
 --- !ELF
 FileHeader:
   Class: ELFCLASS64
   Data:  ELFDATA2LSB
   Type:  ET_EXEC
 Sections:

 
 ## 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:
       - 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:
       - 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:
       - 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"

llvm/tools/llvm-readobj/ELFDumper.cpp

if (!BBAddrMapOrErr) {
       continue;
     }
     for (const Elf_BBAddrMap &AM : *BBAddrMapOrErr) {
       DictScope D(W, "Function");
       W.printHex("At", AM.Addr);
       ListScope L(W, "BB entries");
       for (const typename Elf_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);
   while (Cur && Cur.tell() < Content.size()) {
     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) {
+      uint32_t PropellerID = Data.getULEB128(Cur);
       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({PropellerID, Offset, Size, Metadata});
     }
     Entries.push_back({Address, /*NumBlocks=*/{}, BBEntries});
   }
 
   if (!Cur) {
     // If the section cannot be decoded, we dump it as an array of bytes.
     consumeError(Cur.takeError());
     S->Content = yaml::BinaryRef(Content);