diff --git a/llvm/include/llvm/CodeGen/MachineBasicBlock.h b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
--- a/llvm/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
@@ -162,6 +162,10 @@
   /// 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};
 
@@ -570,6 +574,8 @@
 
   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; }
 
@@ -579,6 +585,8 @@
            ((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; }
 
diff --git a/llvm/include/llvm/CodeGen/MachineFunction.h b/llvm/include/llvm/CodeGen/MachineFunction.h
--- a/llvm/include/llvm/CodeGen/MachineFunction.h
+++ b/llvm/include/llvm/CodeGen/MachineFunction.h
@@ -352,6 +352,8 @@
   bool HasEHScopes = false;
   bool HasEHFunclets = false;
 
+  unsigned NextPropellerID = 0;
+
   /// Section Type for basic blocks, only relevant with basic block sections.
   BasicBlockSection BBSectionsType = BasicBlockSection::None;
 
diff --git a/llvm/include/llvm/Object/ELFTypes.h b/llvm/include/llvm/Object/ELFTypes.h
--- a/llvm/include/llvm/Object/ELFTypes.h
+++ b/llvm/include/llvm/Object/ELFTypes.h
@@ -802,6 +802,7 @@
   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.
 
@@ -812,8 +813,8 @@
     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)){};
   };
diff --git a/llvm/include/llvm/ObjectYAML/ELFYAML.h b/llvm/include/llvm/ObjectYAML/ELFYAML.h
--- a/llvm/include/llvm/ObjectYAML/ELFYAML.h
+++ b/llvm/include/llvm/ObjectYAML/ELFYAML.h
@@ -157,6 +157,7 @@
 
 struct BBAddrMapEntry {
   struct BBEntry {
+    uint32_t PropellerID;
     llvm::yaml::Hex64 AddressOffset;
     llvm::yaml::Hex64 Size;
     llvm::yaml::Hex64 Metadata;
diff --git a/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp b/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
--- a/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
+++ b/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
@@ -1155,11 +1155,15 @@
   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();
diff --git a/llvm/lib/CodeGen/BasicBlockSections.cpp b/llvm/lib/CodeGen/BasicBlockSections.cpp
--- a/llvm/lib/CodeGen/BasicBlockSections.cpp
+++ b/llvm/lib/CodeGen/BasicBlockSections.cpp
@@ -110,8 +110,8 @@
 
 // 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.
@@ -172,14 +172,15 @@
 
 // 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
@@ -227,13 +228,13 @@
     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;
 }
 
@@ -246,9 +247,10 @@
 // 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
@@ -265,9 +267,10 @@
       // 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.
@@ -295,12 +298,15 @@
 
 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();
@@ -366,11 +372,10 @@
       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);
@@ -383,7 +388,7 @@
                                    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.
@@ -417,9 +422,9 @@
     // 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);
@@ -476,23 +481,23 @@
       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.
diff --git a/llvm/lib/CodeGen/MIRParser/MILexer.h b/llvm/lib/CodeGen/MIRParser/MILexer.h
--- a/llvm/lib/CodeGen/MIRParser/MILexer.h
+++ b/llvm/lib/CodeGen/MIRParser/MILexer.h
@@ -126,6 +126,7 @@
     kw_post_instr_symbol,
     kw_heap_alloc_marker,
     kw_bbsections,
+    kw_propeller_id,
     kw_unknown_size,
     kw_unknown_address,
 
diff --git a/llvm/lib/CodeGen/MIRParser/MILexer.cpp b/llvm/lib/CodeGen/MIRParser/MILexer.cpp
--- a/llvm/lib/CodeGen/MIRParser/MILexer.cpp
+++ b/llvm/lib/CodeGen/MIRParser/MILexer.cpp
@@ -271,6 +271,7 @@
       .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)
       .Case("distinct", MIToken::kw_distinct)
diff --git a/llvm/lib/CodeGen/MIRParser/MIParser.cpp b/llvm/lib/CodeGen/MIRParser/MIParser.cpp
--- a/llvm/lib/CodeGen/MIRParser/MIParser.cpp
+++ b/llvm/lib/CodeGen/MIRParser/MIParser.cpp
@@ -501,6 +501,7 @@
   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);
@@ -663,6 +664,18 @@
   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));
@@ -676,6 +689,7 @@
   bool IsLandingPad = false;
   bool IsEHFuncletEntry = false;
   Optional<MBBSectionID> SectionID;
+  Optional<unsigned> PropellerID;
   unsigned Alignment = 0;
   BasicBlock *BB = nullptr;
   if (consumeIfPresent(MIToken::lparen)) {
@@ -708,6 +722,10 @@
         if (parseSectionID(SectionID))
           return true;
         break;
+      case MIToken::kw_propeller_id:
+        if (parsePropellerID(PropellerID))
+          return true;
+        break;
       default:
         break;
       }
@@ -742,6 +760,13 @@
     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;
 }
 
diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp
--- a/llvm/lib/CodeGen/MachineBasicBlock.cpp
+++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp
@@ -542,6 +542,11 @@
       }
       hasAttributes = true;
     }
+    if (getPropellerID().hasValue()) {
+      os << (hasAttributes ? ", " : " (");
+      os << "propeller_id " << *getPropellerID();
+      hasAttributes = true;
+    }
   }
 
   if (hasAttributes)
diff --git a/llvm/lib/CodeGen/MachineFunction.cpp b/llvm/lib/CodeGen/MachineFunction.cpp
--- a/llvm/lib/CodeGen/MachineFunction.cpp
+++ b/llvm/lib/CodeGen/MachineFunction.cpp
@@ -412,8 +412,13 @@
 /// `new MachineBasicBlock'.
 MachineBasicBlock *
 MachineFunction::CreateMachineBasicBlock(const BasicBlock *bb) {
-  return new (BasicBlockRecycler.Allocate<MachineBasicBlock>(Allocator))
-             MachineBasicBlock(*this, bb);
+  MachineBasicBlock *MBB =
+      new (BasicBlockRecycler.Allocate<MachineBasicBlock>(Allocator))
+          MachineBasicBlock(*this, bb);
+  if (Target.getBBSectionsType() == BasicBlockSection::Labels ||
+      Target.getBBSectionsType() == BasicBlockSection::List)
+    MBB->setPropellerID(NextPropellerID++);
+  return MBB;
 }
 
 /// Delete the given MachineBasicBlock.
diff --git a/llvm/lib/Object/ELF.cpp b/llvm/lib/Object/ELF.cpp
--- a/llvm/lib/Object/ELF.cpp
+++ b/llvm/lib/Object/ELF.cpp
@@ -650,10 +650,11 @@
     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});
   }
diff --git a/llvm/lib/ObjectYAML/ELFEmitter.cpp b/llvm/lib/ObjectYAML/ELFEmitter.cpp
--- a/llvm/lib/ObjectYAML/ELFEmitter.cpp
+++ b/llvm/lib/ObjectYAML/ELFEmitter.cpp
@@ -1408,7 +1408,8 @@
     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);
   }
diff --git a/llvm/lib/ObjectYAML/ELFYAML.cpp b/llvm/lib/ObjectYAML/ELFYAML.cpp
--- a/llvm/lib/ObjectYAML/ELFYAML.cpp
+++ b/llvm/lib/ObjectYAML/ELFYAML.cpp
@@ -1713,6 +1713,7 @@
 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);
diff --git a/llvm/test/CodeGen/X86/basic-block-labels-mir-parse.mir b/llvm/test/CodeGen/X86/basic-block-labels-mir-parse.mir
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/X86/basic-block-labels-mir-parse.mir
@@ -0,0 +1,138 @@
+# 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
diff --git a/llvm/test/CodeGen/X86/basic-block-sections-labels.ll b/llvm/test/CodeGen/X86/basic-block-sections-labels.ll
--- a/llvm/test/CodeGen/X86/basic-block-sections-labels.ll
+++ b/llvm/test/CodeGen/X86/basic-block-sections-labels.ll
@@ -39,8 +39,8 @@
 ; 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{{$}}
@@ -48,15 +48,19 @@
 ; 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
diff --git a/llvm/test/CodeGen/X86/basic-block-sections-mir-print.ll b/llvm/test/CodeGen/X86/basic-block-sections-mir-print.ll
--- a/llvm/test/CodeGen/X86/basic-block-sections-mir-print.ll
+++ b/llvm/test/CodeGen/X86/basic-block-sections-mir-print.ll
@@ -1,8 +1,9 @@
 ; 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) {
@@ -27,7 +28,12 @@
   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):
diff --git a/llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test b/llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test
--- a/llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test
+++ b/llvm/test/tools/llvm-readobj/ELF/bb-addr-map.test
@@ -22,6 +22,7 @@
 # LLVM-NEXT:     Name: <?>
 # LLVM-NEXT:     BB entries [
 # LLVM-NEXT:       {
+# LLVM-NEXT:         ID: 0
 # LLVM-NEXT:         Offset: 0x0
 # LLVM-NEXT:         Size: 0x1
 # LLVM-NEXT:         HasReturn: No
@@ -30,6 +31,7 @@
 # LLVM-NEXT:         CanFallThrough: No
 # LLVM-NEXT:       }
 # LLVM-NEXT:       {
+# LLVM-NEXT:         ID: 2
 # LLVM-NEXT:         Offset: 0x3
 # LLVM-NEXT:         Size: 0x4
 # LLVM-NEXT:         HasReturn: Yes
@@ -44,6 +46,7 @@
 # LLVM-NEXT:     Name: foo
 # LLVM-NEXT:     BB entries [
 # LLVM-NEXT:       {
+# LLVM-NEXT:         ID: 4
 # LLVM-NEXT:         Offset: 0x6
 # LLVM-NEXT:         Size: 0x7
 # LLVM-NEXT:         HasReturn: No
@@ -60,6 +63,7 @@
 # LLVM-NEXT:     Name: bar
 # LLVM-NEXT:     BB entries [
 # LLVM-NEXT:       {
+# LLVM-NEXT:         ID: 6
 # LLVM-NEXT:         Offset: 0x9
 # LLVM-NEXT:         Size: 0xA
 # LLVM-NEXT:         HasReturn: Yes
@@ -83,6 +87,7 @@
 # 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
@@ -113,15 +118,18 @@
     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
@@ -133,7 +141,8 @@
     Entries:
       - Address: 0x33333
         BBEntries:
-          - AddressOffset: 0x9
+          - ID:            6
+            AddressOffset: 0x9
             Size:          0xa
             Metadata:      0xb
 Symbols:
diff --git a/llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml b/llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml
--- a/llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml
+++ b/llvm/test/tools/obj2yaml/ELF/bb-addr-map.yaml
@@ -16,18 +16,22 @@
 # 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
 
@@ -45,17 +49,21 @@
         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
 
@@ -100,7 +108,8 @@
 # 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)'
@@ -122,6 +131,7 @@
       - Address:   0x0
         BBEntries:
           - AddressOffset:    0x1
+            ID:               4
             Size:             0x2
             Metadata:         0x3
   - Name:    '.llvm_bb_addr_map (1)'
diff --git a/llvm/test/tools/yaml2obj/ELF/bb-addr-map.yaml b/llvm/test/tools/yaml2obj/ELF/bb-addr-map.yaml
--- a/llvm/test/tools/yaml2obj/ELF/bb-addr-map.yaml
+++ b/llvm/test/tools/yaml2obj/ELF/bb-addr-map.yaml
@@ -36,7 +36,7 @@
 # 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.
@@ -44,13 +44,13 @@
 # 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
@@ -87,7 +87,8 @@
     Entries:
       - Address:   0x0000000000000020
         BBEntries:
-          - AddressOffset:    0x00000001
+          - ID:               11
+            AddressOffset:    0x00000001
             Size:             0x00000002
             Metadata:         0x00000003
 
@@ -97,7 +98,8 @@
     Type:    SHT_LLVM_BB_ADDR_MAP
     Entries:
       - BBEntries:
-          - AddressOffset:    0x00000001
+          - ID:               12
+            AddressOffset:    0x00000001
             Size:             0x00000002
             Metadata:         0x00000003
 
@@ -109,7 +111,8 @@
       - Address:   0x0000000000000020
         NumBlocks: 2
         BBEntries:
-          - AddressOffset:    0x00000001
+          - ID:               13
+            AddressOffset:    0x00000001
             Size:             0x00000002
             Metadata:         0x00000003
 
diff --git a/llvm/tools/llvm-readobj/ELFDumper.cpp b/llvm/tools/llvm-readobj/ELFDumper.cpp
--- a/llvm/tools/llvm-readobj/ELFDumper.cpp
+++ b/llvm/tools/llvm-readobj/ELFDumper.cpp
@@ -6842,6 +6842,7 @@
       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);
diff --git a/llvm/tools/obj2yaml/elf2yaml.cpp b/llvm/tools/obj2yaml/elf2yaml.cpp
--- a/llvm/tools/obj2yaml/elf2yaml.cpp
+++ b/llvm/tools/obj2yaml/elf2yaml.cpp
@@ -893,10 +893,11 @@
     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});
   }
diff --git a/llvm/unittests/Object/ELFObjectFileTest.cpp b/llvm/unittests/Object/ELFObjectFileTest.cpp
--- a/llvm/unittests/Object/ELFObjectFileTest.cpp
+++ b/llvm/unittests/Object/ELFObjectFileTest.cpp
@@ -497,7 +497,8 @@
     Entries:
       - Address: 0x11111
         BBEntries:
-          - AddressOffset: 0x0
+          - ID:            0
+            AddressOffset: 0x0
             Size:          0x1
             Metadata:      0x2
 )");
@@ -530,29 +531,32 @@
   SmallVector<SmallString<128>, 3> OverInt32LimitYamlStrings(3,
                                                              CommonYamlString);
   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 0xc exceeds UINT32_MAX (0x100000000)");
+          "ULEB128 value at offset 0xe exceeds UINT32_MAX (0x100000000)");
   DoCheck(OverInt32LimitYamlStrings[1],
-          "ULEB128 value at offset 0x11 exceeds UINT32_MAX (0x100000000)");
+          "ULEB128 value at offset 0x13 exceeds UINT32_MAX (0x100000000)");
   DoCheck(OverInt32LimitYamlStrings[2],
-          "ULEB128 value at offset 0x16 exceeds UINT32_MAX (0x100000000)");
+          "ULEB128 value at offset 0x18 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
@@ -561,24 +565,24 @@
       3, OverInt32LimitYamlStrings[1]);
   // Truncate before the end of the 5-byte field.
   OverInt32LimitAndTruncated[0] += R"(
-    ShSize: 0x15
+    ShSize: 0x17
 )";
   // Truncate at the end of the 5-byte field.
   OverInt32LimitAndTruncated[1] += R"(
-    ShSize: 0x16
+    ShSize: 0x18
 )";
   // Truncate after the end of the 5-byte field.
   OverInt32LimitAndTruncated[2] += R"(
-    ShSize: 0x17
+    ShSize: 0x19
 )";
 
   DoCheck(OverInt32LimitAndTruncated[0],
-          "unable to decode LEB128 at offset 0x00000011: malformed uleb128, "
+          "unable to decode LEB128 at offset 0x00000013: malformed uleb128, "
           "extends past end");
   DoCheck(OverInt32LimitAndTruncated[1],
-          "ULEB128 value at offset 0x11 exceeds UINT32_MAX (0x100000000)");
+          "ULEB128 value at offset 0x13 exceeds UINT32_MAX (0x100000000)");
   DoCheck(OverInt32LimitAndTruncated[2],
-          "ULEB128 value at offset 0x11 exceeds UINT32_MAX (0x100000000)");
+          "ULEB128 value at offset 0x13 exceeds UINT32_MAX (0x100000000)");
 
   // Check for proper error handling when the 'NumBlocks' field is overridden
   // with an out-of-range value.