LLVM support for BB-cluster sections

[rahmanl]

Summary

This is an extension of basic block sections which allows emitting several hot basic blocks in the same section, in a given order.

Currently the -basicblock-sections=list option allows specifying unique sections for some basic blocks. For example:
!foo
!!1
!!2
!!4
instructs the compiler to emit the entry basic block and each of basic blocks #1, #2, and #4 into a separate unique section, while all the non-specified basic blocks are coalesced into a "cold" section.

With this patch, we can use the same option to specify clusters of basic blocks to be emitted into the same section. For instance:
!foo
!!0 1 2
!!4
means emitting one section containing the entry block, BB#1, and BB#2 in this order, while emitting BB#4 in a unique section of its own. Still all the excluded basic blocks go into the cold section.

One difference is that with the new approach, we don't always create a unique separate section for the entry block. It needs to be explicitly specified in the lists, or otherwise it would be coalesced into the cold section.

Another difference is with respect to the special exception section. We only create an exception section if the BB-cluster specification scatters EH pads into more than one section.

The final difference is with regards to the size directives. We now emit a size directive only for the BBs which start a section. That size is the size of the section marked by that BB. If we want sizes for every internal basic block as well, this requires being able to combine -basicblock-sections=labels with -basicblock-sections=list which is not currently possible.

Finally, with BB-clusters, we emit persistent non-temporary labels only for basic blocks which begin sections. Other basic blocks will use temp labels in the form of .LBBN_M as before.

The benefit of the BB-cluster approach is that it reduces the number of basic block sections created, which in turn reduces the CFI and DebugInfo overhead, and also reduces the burden of the linker.

Another benefit is being able to reuse the assembler's JCC mitigation strategy as discussed in http://lists.llvm.org/pipermail/llvm-dev/2020-March/140134.html.

We note the BB-cluster approach is only beneficial if the optimal block order can be computed prior to compilation, using profiles and the binary generated using -basicblock-secitons=labels We have shown that this is possible and the performance improvements match our previous results (please refer to the link above).

[rahmanl]

Added a test for bb-cluster sections: llvm/test/CodeGen/X86/basicblock-sections-clusters.ll

[tmsriram]

Took one pass over the code.

• This needs more tests like with exception blocks kept in separate clusters (check if they are grouped)

llvm/include/llvm/CodeGen/MachineBasicBlock.h

82

Move this to MachineFunction.h as a member?

83

Also this?

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1199

Combine the two conditions.

3070

Good check, reduces unnecessary section directives if .S is emitted. Does the entry block begin a section? If so, it should be skipped.

llvm/lib/CodeGen/BBSectionsPrepare.cpp

12

Could make longer lines and keep it better formatted.

25

Longer lines?

140

Could be made a static function passing the Maps as const reference?

168

I see why you removed the sameSection check. However, when you call this function, you already know the clusterID and the position in the cluster. So, don't insert the fallthrough if they are the same cluster and are adjacent?

213

"Unless we want individual unique sections for every basic block...."

222

If clusterID is made a pair of integers which denote the ids of the start and end basic blocks, the begin and end function in MachineBasicBlock can be simplified.

llvm/lib/CodeGen/MachineBasicBlock.cpp

577

This comment applies to isEndSection too. Consider making beginSection and endSection bool members of MachineBasicBlock and set it once in BBSectionsPrepare. Isn't this function called multiple times per MBB, like for DebugInfo and CFI?

One way is to make ClusterID a pair of basic block ids that give you the start and end of the cluster. The beginSection is just "return id == clusterID.first" and end Section is "return id == clusterID.second"

[rahmanl]

Major changes with this update:

1- Using a StringMap of vectors instead of nested map in getBBClusterInfo (BBSectionsPrepare.cpp).
2- Structured error handling in getBBClusterInfo.
3- New basicblock-section-clusters tests exercising various combinations of clustering (involving exception handling blocks and cold code), add ensuring that branches are optimized/inserted at the right places.

[rahmanl]

Thanks a lot for the comments @tmsriram . I managed to get most of them addressed (Most importantly the one about nested maps).

llvm/include/llvm/CodeGen/MachineBasicBlock.h

82

I thought about placing this in https://llvm.org/doxygen/MachineFunction_8h_source.html#l00110 but this is a property of MachineBasicBlock. In fact, MachineFunction does not need to care about section IDs at all.
Is it the "static" keyword which is concerning?

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

3070

Yes it does, but it is excluded from this block by pred_empty() check at line 3044.

llvm/lib/CodeGen/BBSectionsPrepare.cpp

168

I agree. It's possible. But the requirement for exception handling blocks might make it a bit complicated. Since this is before basic block sorting, we would have to resort to BBClusterInfo.PositionInCluster which may not represent the ultimate placement of blocks.

222

isBeginSection() and isEndSection() only look at previous and subsequent basic blocks to see if they have a different section ID. This way, we can use SectionIDs to decided if a basic block begins or ends a section without having to store to boolean.

[rahmanl]

The major change int this update is the ability of "not inserting unconditional branches" when fallthrough block hasn't moved.

To do this, I have moved the logic of insertUnconditionalFallthroughBranch function into the updateBranches function.

[rahmanl]

Finished addressing one more @tmsriram 's suggestion involving redundant insertion of explicit fallthrough branches.

[tmsriram]

llvm/lib/CodeGen/BBSectionsPrepare.cpp

168

s/accout/account

235

Does this need a set? could you make EHPadSections a integer = -1. Set it to the clusterid when you see the first exception MBB. After that, if you see another MBB with a different clusterid, set it to MachineBasicBlock::ExcpetionSectionID and check for this before resetting?

267

Wouldn't this a bit more clear:

return (XSectionID == ExceptionSectionID || XSectionID == ColdSectionID) ? X.getNumber() < Y.getNumber : ...PositionInCluster < ...PositionInCluster

The implicit ColdSectionID > ExceptionSectionID should be exposed unless they are part of enum I think.

281

I get why you are doing it here now. You want to generate the optimal branches when possible, something you couldn't do before.

336

Why not make it one expression?

380

I dont see any other uses of istringstream except in a tool. Why not just use .split(" ")?

llvm/lib/CodeGen/MIRPrinter.cpp

648

s/Excetion/Exception

[tmsriram]

llvm/lib/CodeGen/MachineBasicBlock.cpp

582

I don't have a strong opinion but the fact that this is being computed for every call of isBeginSection and isEndSection makes me a bit nervous. Why do this when BBSectionsPrepare can just set a bool? can always be done later if there are many calls to these functions, just putting it out here.

[rahmanl]

Addressed @tmsriram 's second round of comments.

Thanks a lot Sri.

[rahmanl]

Addressed @tmsriram 's second round of comments.

[tmsriram]

Please do not submit without an approval from @efriedma as they approved the original patch.

This LGTM with these changes.

llvm/lib/CodeGen/BBSectionsPrepare.cpp

239

You can also add EHPadsSectionID != ExceptionSectionID

245

EHPadsSectionID == MachineBasicBlock::ExceptionSectionID should be moved outside the loop.

llvm/lib/CodeGen/MachineBasicBlock.cpp

552–558

This has become too simple, maybe just delete the function or move the body to the header file itself?

llvm/lib/CodeGen/MachineFunction.cpp

374

This function is called twice and I highly doubt this will be called more than that. Once in BBSectionsPrepare.cpp and other in MIRParser. Should it be a member? You can repeat it in both places I think, it is small.

Also, you could initialize isBeginSection and isEndSection to false and just handle the true case maybe.

[rahmanl]

Moved assignBeginEndSections to BBSectionsPrepare.cpp and MIRParser.cpp.

[rahmanl]

Handled all of @tmsriram 's 3rd round of comments.

llvm/lib/CodeGen/MachineBasicBlock.cpp

552–558

Moved the definition to the header file.

[tmsriram]

Hi Eli @efriedma , I took the liberty to review and approve this patch as it was mostly a change to BBSectionsPrepare.cpp. Appreciate if you could also take a look as you approved the original patch, thanks!

[rahmanl]

@efriedma Would you please take a look at this patch? Any feedback is appreciated.

[efriedma]

I'm happy with this at a high level; it's not really any more complicated than BasicBlock sections itself, and the added flexibility makes sense.

From the AsmPrinter's perspective, there isn't any difference between having BBSections disabled, vs. having every BB in the function assigned to the section with the same ID. You shouldn't really need to explicitly check whether
BBSections are enabled from the AsmPrinter; all the checks that do remain are suspicious.

Also along those lines, does the SectionID need to be Optional<unsigned>, as opposed to just being unsigned?

llvm/include/llvm/CodeGen/MachineBasicBlock.h

480

"this == MBB" check is redundant, I think.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1190

I don't like the way this if statement is written. The fundamental MCBinaryExpr::createSub() operation is shared, but the two operations aren't really related anymore, so the logic here is sort of twisted. I'd suggest pulling the createTempSymbol()/MCBinaryExpr::createSub()/emitELFSize() into a helper (maybe a lambda), and calling it from two separate if statements.

llvm/lib/CodeGen/MIRParser/MIParser.cpp

630

"unknown"

llvm/lib/CodeGen/MIRParser/MIRParser.cpp

51

Why are there two copies of assignBeginEndSections ?

[rahmanl]

The major change in this diff is removing all "MF->hasBBSections()" calls from AsmPrinter.cpp per @eli.friedman 's suggestion.
Other changes:

Refactoring the size directive emission for basic block symbols.
Merging the function getNamedSectionForMachineBasicBlock into getSectionForMachineBasicBlock.
Re-allowing the emission of basic block alignment for BBSections.
Removing the duplicate assignBeginEndSection from MIRParser and declaring it as an external function defined in BBSectionsPrepare.cpp.

[rahmanl]

Thanks a lot for your insightful comments @eli.friedman. I think removing the hasBBSections() calls from AsmPrinter.cpp has made the code a lot better.

llvm/lib/CodeGen/MIRParser/MIRParser.cpp

51

This function is defined to set IsBeginSection and IsEndSection which are derived from SectionID fields and the MBB order of the function. So we just need to iterate over all MBBs once and assign the fields.

I initially had defined it in MachineFunction.h and then decided to duplicate the code in the two places it is required as per @tmsriram .

I now made the MIRParser's version and external function. Do you have a better suggestion?

[efriedma]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1213

It looks like getEndMCSymbol is unused? (And therefore setEndMCSymbol/EntrySectionEndMBB are dead code.)

llvm/lib/CodeGen/MIRParser/MIRParser.cpp

51

Oh, hmm, didn't follow the original conversation. I don't really understand the objection from @tmsriram to making it a member function; 10 lines with tricky boundary conditions is generally beyond my threshold of "copy-paste it".

llvm/lib/CodeGen/MachineBasicBlock.cpp

562–565

getSectionEndMBB is dead?

[tmsriram]

llvm/lib/CodeGen/MIRParser/MIRParser.cpp

51

I agree, Eli's recommendation is correct.

[rahmanl]

The major change with this is a new struct called MBBSectionID to represent the basic block section IDs instead of a plain integer.
This makes the code cleaner (especially for the upcoming CFI and DebugInfo patches).

[rahmanl]

Thanks again @efriedma and @tmsriram.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1206–1209

Please excuse the nested if statement here. Our upcoming CFI and Exception patches will add one statement to each of the nested if blocks,

[efriedma]

LGTM with one minor suggestion

llvm/lib/CodeGen/MIRPrinter.cpp

643

Maybe just print all non-zero SectionIDs, instead of checking hasBBSections()?

[MaskRay]

Hi, it seems that you already got some feedback. I will look at it soon.

llvm/lib/CodeGen/BBSectionsPrepare.cpp

285

You can use

if (XSectionID != YSectionID)
  return ...
if (... != ...)
  return ...
return ...PositionInCluster < ...;

[rahmanl]

This final update applies @MaskRay and @efriedma's last suggestions.
Thanks to all the reviewers.

[rahmanl]

Re-uploading the diff since I missed test files in the latest update.

llvm/include/llvm/CodeGen/AsmPrinter.h

public:
   /// at the beginning of each call to SetupMachineFunction().
   MCSymbol *CurrentFnDescSym = nullptr;
 
   /// The symbol used to represent the start of the current function for the
   /// purpose of calculating its size (e.g. using the .size directive). By
   /// default, this is equal to CurrentFnSym.
   MCSymbol *CurrentFnSymForSize = nullptr;
 
+  // The symbol used to represent the start of the current BB section of the
+  // function. This is used to calculate the size of the BB section.
+  MCSymbol *CurrentSectionBeginSym = nullptr;
+
   /// Map global GOT equivalent MCSymbols to GlobalVariables and keep track of
   /// its number of uses by other globals.
   using GOTEquivUsePair = std::pair<const GlobalVariable *, unsigned>;
   MapVector<const MCSymbol *, GOTEquivUsePair> GlobalGOTEquivs;
 
 private:
   MCSymbol *CurrentFnEnd = nullptr;
   MCSymbol *CurExceptionSym = nullptr;

llvm/include/llvm/CodeGen/MachineBasicBlock.h

 class ModuleSlotTracker;
 class Pass;
 class SlotIndexes;
 class StringRef;
 class raw_ostream;
 class TargetRegisterClass;
 class TargetRegisterInfo;
 
-enum MachineBasicBlockSection : unsigned {
-  ///  This is also the order of sections in a function.  Basic blocks that are
-  ///  part of the original function section (entry block) come first, followed
-  ///  by exception handling basic blocks, cold basic blocks and finally basic
-  //   blocks that need unique sections.
-  MBBS_Entry,
-  MBBS_Exception,
-  MBBS_Cold,
-  MBBS_Unique,
-  ///  None implies no sections for any basic block, the default.
-  MBBS_None,
-};
-
 template <> struct ilist_traits<MachineInstr> {
 private:
   friend class MachineBasicBlock; // Set by the owning MachineBasicBlock.
 
   MachineBasicBlock *Parent;
 
   using instr_iterator =
       simple_ilist<MachineInstr, ilist_sentinel_tracking<true>>::iterator;
public:
   public:
     MCPhysReg PhysReg;
     LaneBitmask LaneMask;
 
     RegisterMaskPair(MCPhysReg PhysReg, LaneBitmask LaneMask)
         : PhysReg(PhysReg), LaneMask(LaneMask) {}
   };
 
+  // Special section IDs for the cold and exception section
+  const static unsigned ColdSectionID = UINT_MAX;
+  const static unsigned ExceptionSectionID = UINT_MAX - 1;
+
 private:
   using Instructions = ilist<MachineInstr, ilist_sentinel_tracking<true>>;
 
   Instructions Insts;
   const BasicBlock *BB;
   int Number;
   MachineFunction *xParent;
 
private:
   bool IsEHScopeEntry = 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;
 
-  /// Stores the Section type of the basic block with basic block sections.
-  MachineBasicBlockSection SectionType = MBBS_None;
+  /// Stores the Section ID of the basic block with basic block sections.
+  Optional<unsigned> SectionID;
 
   /// Default target of the callbr of a basic block.
   bool InlineAsmBrDefaultTarget = false;
 
   /// List of indirect targets of the callbr of a basic block.
   SmallPtrSet<const MachineBasicBlock*, 4> InlineAsmBrIndirectTargets;
 
   /// since getSymbol is a relatively heavy-weight operation, the symbol
#endif
   void setIsCleanupFuncletEntry(bool V = true) { IsCleanupFuncletEntry = V; }
 
   /// Returns true if this block begins any section.
   bool isBeginSection() const;
 
   /// Returns true if this block ends any section.
   bool isEndSection() const;
 
-  /// Returns the type of section this basic block belongs to.
-  MachineBasicBlockSection getSectionType() const { return SectionType; }
+  /// Returns the the section id that this basic block belongs to.
+  Optional<unsigned> getSectionID() const { return SectionID; }
 
   /// Indicate that the basic block belongs to a Section Type.
-  void setSectionType(MachineBasicBlockSection V) { SectionType = V; }
+  void setSectionID(unsigned V) { SectionID = V; }
 
   /// Returns true if this is the indirect dest of an INLINEASM_BR.
   bool isInlineAsmBrIndirectTarget(const MachineBasicBlock *Tgt) const {
     return InlineAsmBrIndirectTargets.count(Tgt);
   }
 
   /// Indicates if this is the indirect dest of an INLINEASM_BR.
   void addInlineAsmBrIndirectTarget(const MachineBasicBlock *Tgt) {
#endif
   /// Move 'this' block before or after the specified block.  This only moves
   /// the block, it does not modify the CFG or adjust potential fall-throughs at
   /// the end of the block.
   void moveBefore(MachineBasicBlock *NewAfter);
   void moveAfter(MachineBasicBlock *NewBefore);
 
   /// Returns true if this and MBB belong to the same section.
   bool sameSection(const MachineBasicBlock *MBB) const;
 
   /// Returns the basic block that ends the section which contains this one.
   const MachineBasicBlock *getSectionEndMBB() const;
 
   /// Update the terminator instructions in block to account for changes to the
   /// layout. If the block previously used a fallthrough, it may now need a
   /// branch, and if it previously used branching it may now be able to use a
   /// fallthrough.
   void updateTerminator();

llvm/include/llvm/CodeGen/MachineFunction.h

class MachineFunction {
   bool CallsEHReturn = false;
   bool CallsUnwindInit = false;
   bool HasEHScopes = false;
   bool HasEHFunclets = false;
 
   /// Section Type for basic blocks, only relevant with basic block sections.
   BasicBlockSection BBSectionsType = BasicBlockSection::None;
 
-  /// With Basic Block Sections, this stores the bb ranges of cold and
-  /// exception sections.
-  std::pair<int, int> ColdSectionRange = {-1, -1};
-  std::pair<int, int> ExceptionSectionRange = {-1, -1};
-
   /// List of C++ TypeInfo used.
   std::vector<const GlobalValue *> TypeInfos;
 
   /// List of typeids encoding filters used.
   std::vector<unsigned> FilterIds;
 
   /// List of the indices in FilterIds corresponding to filter terminators.
   std::vector<unsigned> FilterEnds;
public:
 
   /// Returns true if basic block labels are to be generated for this function.
   bool hasBBLabels() const {
     return BBSectionsType == BasicBlockSection::Labels;
   }
 
   void setBBSectionsType(BasicBlockSection V) { BBSectionsType = V; }
 
-  void setSectionRange();
-
-  /// Returns true if this basic block number starts a cold or exception
-  /// section.
-  bool isSectionStartMBB(int N) const {
-    return (N == ColdSectionRange.first || N == ExceptionSectionRange.first);
-  }
-
-  /// Returns true if this basic block ends a cold or exception section.
-  bool isSectionEndMBB(int N) const {
-    return (N == ColdSectionRange.second || N == ExceptionSectionRange.second);
-  }
-
   /// Creates basic block Labels for this function.
   void createBBLabels();
 
   /// getTarget - Return the target machine this machine code is compiled with
   const LLVMTargetMachine &getTarget() const { return Target; }
 
   /// getSubtarget - Return the subtarget for which this machine code is being
   /// compiled.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

if (!MLI) {
       OwnedMLI->getBase().analyze(MDT->getBase());
       MLI = OwnedMLI.get();
     }
   }
 
   // Print out code for the function.
   bool HasAnyRealCode = false;
   int NumInstsInFunction = 0;
-  bool emitBBSections = MF->hasBBSections();
   MachineBasicBlock *EndOfRegularSectionMBB = nullptr;
-  if (emitBBSections) {
+  if (MF->hasBBSections()) {
     EndOfRegularSectionMBB =
         const_cast<MachineBasicBlock *>(MF->front().getSectionEndMBB());
     assert(EndOfRegularSectionMBB->isEndSection() &&
            "The MBB at the end of the regular section must end a section");
   }
 
   for (auto &MBB : *MF) {
     // Print a label for the basic block.
for (auto &MI : MBB) {
         for (const HandlerInfo &HI : Handlers) {
           NamedRegionTimer T(HI.TimerName, HI.TimerDescription,
                              HI.TimerGroupName, HI.TimerGroupDescription,
                              TimePassesIsEnabled);
           HI.Handler->endInstruction();
         }
       }
     }
-    if (&MBB != EndOfRegularSectionMBB &&
-        (MF->hasBBLabels() || MBB.isEndSection())) {
+    if (MF->hasBBLabels()) {
       // Emit size directive for the size of this basic block.  Create a symbol
       // for the end of the basic block.
       MCSymbol *CurrentBBEnd = OutContext.createTempSymbol();
       const MCExpr *SizeExp = MCBinaryExpr::createSub(
           MCSymbolRefExpr::create(CurrentBBEnd, OutContext),
           MCSymbolRefExpr::create(MBB.getSymbol(), OutContext), OutContext);
       OutStreamer->emitLabel(CurrentBBEnd);
-      MBB.setEndMCSymbol(CurrentBBEnd);
       OutStreamer->emitELFSize(MBB.getSymbol(), SizeExp);
     }
+
+    if (MBB.isEndSection()) {
+      if (MBB.getSectionID() != MF->front().getSectionID()) {
+        // Emit size directive for the size of this basic block section. The
+        // size directive for the regular section will be emitted as the
+        // function size.
+        MCSymbol *CurrentSectionEnd = OutContext.createTempSymbol();
+        const MCExpr *SizeExp = MCBinaryExpr::createSub(
+            MCSymbolRefExpr::create(CurrentSectionEnd, OutContext),
+            MCSymbolRefExpr::create(CurrentSectionBeginSym, OutContext),
+            OutContext);
+        OutStreamer->emitLabel(CurrentSectionEnd);
+        MBB.setEndMCSymbol(CurrentSectionEnd);
+        OutStreamer->emitELFSize(CurrentSectionBeginSym, SizeExp);
+      }
+    }
     emitBasicBlockEnd(MBB);
   }
 
   EmittedInsts += NumInstsInFunction;
   MachineOptimizationRemarkAnalysis R(DEBUG_TYPE, "InstructionCount",
                                       MF->getFunction().getSubprogram(),
                                       &MF->front());
   R << ore::NV("NumInstructions", NumInstsInFunction)
     << " instructions in function";
if (!HasAnyRealCode && (MAI->hasSubsectionsViaSymbols() ||
     // unspecified.
     if (Noop.getOpcode()) {
       OutStreamer->AddComment("avoids zero-length function");
       emitNops(1);
     }
   }
 
   // Switch to the original section if basic block sections was used.
-  if (emitBBSections)
+  if (MF->hasBBSections())
     OutStreamer->SwitchSection(MF->getSection());
 
   const Function &F = MF->getFunction();
   for (const auto &BB : F) {
     if (!BB.hasAddressTaken())
       continue;
     MCSymbol *Sym = GetBlockAddressSymbol(&BB);
     if (Sym->isDefined())
       continue;
     OutStreamer->AddComment("Address of block that was removed by CodeGen");
     OutStreamer->emitLabel(Sym);
   }
 
   // Emit target-specific gunk after the function body.
   emitFunctionBodyEnd();
 
   if (needFuncLabelsForEHOrDebugInfo(*MF, MMI) ||
-      MAI->hasDotTypeDotSizeDirective() || emitBBSections) {
+      MAI->hasDotTypeDotSizeDirective() || MF->hasBBSections()) {
     // Create a symbol for the end of function.
     CurrentFnEnd = createTempSymbol("func_end");
     OutStreamer->emitLabel(CurrentFnEnd);
   }
 
   // If the target wants a .size directive for the size of the function, emit
   // it.
   if (MAI->hasDotTypeDotSizeDirective()) {
     // We can get the size as difference between the function label and the
     // temp label.
     const MCExpr *SizeExp = MCBinaryExpr::createSub(
         MCSymbolRefExpr::create(CurrentFnEnd, OutContext),
         MCSymbolRefExpr::create(CurrentFnSymForSize, OutContext), OutContext);
     OutStreamer->emitELFSize(CurrentFnSym, SizeExp);
   }
 
   for (const HandlerInfo &HI : Handlers) {
     NamedRegionTimer T(HI.TimerName, HI.TimerDescription, HI.TimerGroupName,
                        HI.TimerGroupDescription, TimePassesIsEnabled);
     HI.Handler->markFunctionEnd();
   }
 
-  if (emitBBSections)
+  if (MF->hasBBSections())
     EndOfRegularSectionMBB->setEndMCSymbol(CurrentFnEnd);
 
   // Print out jump tables referenced by the function.
   emitJumpTableInfo();
 
   // Emit post-function debug and/or EH information.
   for (const HandlerInfo &HI : Handlers) {
     NamedRegionTimer T(HI.TimerName, HI.TimerDescription, HI.TimerGroupName,
if (!MAI->needsFunctionDescriptors()) {
     // Set the containing csect.
     MCSectionXCOFF *FnEntryPointSec =
         cast<MCSectionXCOFF>(getObjFileLowering().SectionForGlobal(&F, TM));
     cast<MCSymbolXCOFF>(CurrentFnSym)->setContainingCsect(FnEntryPointSec);
   }
 
   CurrentFnSymForSize = CurrentFnSym;
   CurrentFnBegin = nullptr;
+  CurrentSectionBeginSym = nullptr;
   CurExceptionSym = nullptr;
   bool NeedsLocalForSize = MAI->needsLocalForSize();
   if (F.hasFnAttribute("patchable-function-entry") ||
       needFuncLabelsForEHOrDebugInfo(MF, MMI) || NeedsLocalForSize ||
       MF.getTarget().Options.EmitStackSizeSection) {
     CurrentFnBegin = createTempSymbol("func_begin");
     if (NeedsLocalForSize)
       CurrentFnSymForSize = CurrentFnBegin;
static void emitBasicBlockLoopComments(const MachineBasicBlock &MBB,
 
   PrintChildLoopComment(OS, Loop, AP.getFunctionNumber());
 }
 
 /// emitBasicBlockStart - This method prints the label for the specified
 /// MachineBasicBlock, an alignment (if present) and a comment describing
 /// it if appropriate.
 void AsmPrinter::emitBasicBlockStart(const MachineBasicBlock &MBB) {
-  bool BBSections = MF->hasBBSections();
   // End the previous funclet and start a new one.
   if (MBB.isEHFuncletEntry()) {
     for (const HandlerInfo &HI : Handlers) {
       HI.Handler->endFunclet();
       HI.Handler->beginFunclet(MBB);
     }
   }
 
   // Emit an alignment directive for this block, if needed.
-  if (MBB.pred_empty() || !BBSections) {
+  if (MBB.pred_empty() || !MF->hasBBSections()) {
     const Align Alignment = MBB.getAlignment();
     if (Alignment != Align(1))
       emitAlignment(Alignment);
   }
 
   // If the block has its address taken, emit any labels that were used to
   // reference the block.  It is possible that there is more than one label
   // here, because multiple LLVM BB's may have been RAUW'd to this block after
if (const BasicBlock *BB = MBB.getBasicBlock()) {
         OutStreamer->GetCommentOS() << '\n';
       }
     }
 
     assert(MLI != nullptr && "MachineLoopInfo should has been computed");
     emitBasicBlockLoopComments(MBB, MLI, *this);
   }
 
-  bool emitBBLabels = BBSections || MF->hasBBLabels();
+  bool emitBBLabels = MF->hasBBSections() || MF->hasBBLabels();
   if (MBB.pred_empty() ||
       (!emitBBLabels && isBlockOnlyReachableByFallthrough(&MBB) &&
        !MBB.isEHFuncletEntry() && !MBB.hasLabelMustBeEmitted())) {
     if (isVerbose()) {
       // NOTE: Want this comment at start of line, don't emit with AddComment.
       OutStreamer->emitRawComment(" %bb." + Twine(MBB.getNumber()) + ":",
                                   false);
     }
   } else {
     if (isVerbose() && MBB.hasLabelMustBeEmitted()) {
       OutStreamer->AddComment("Label of block must be emitted");
     }
+    if (MBB.isBeginSection()) {
       // With -fbasicblock-sections, a basic block can start a new section.
-    if (MBB.getSectionType() == MachineBasicBlockSection::MBBS_Exception) {
+      if (MBB.getSectionID() == MachineBasicBlock::ExceptionSectionID) {
         // Create the exception section for this function.
         OutStreamer->SwitchSection(
             getObjFileLowering().getNamedSectionForMachineBasicBlock(
                 MF->getFunction(), MBB, TM, ".eh"));
-    } else if (MBB.getSectionType() == MachineBasicBlockSection::MBBS_Cold) {
+      } else if (MBB.getSectionID() == MachineBasicBlock::ColdSectionID) {
         // Create the cold section here.
         OutStreamer->SwitchSection(
             getObjFileLowering().getNamedSectionForMachineBasicBlock(
                 MF->getFunction(), MBB, TM, ".unlikely"));
-    } else if (MBB.isBeginSection() && MBB.isEndSection()) {
+      } else
         OutStreamer->SwitchSection(
-          getObjFileLowering().getSectionForMachineBasicBlock(MF->getFunction(),
-                                                              MBB, TM));
-    } else if (BBSections) {
-      OutStreamer->SwitchSection(MF->getSection());
+            getObjFileLowering().getSectionForMachineBasicBlock(
+                MF->getFunction(), MBB, TM));
+      CurrentSectionBeginSym = MBB.getSymbol();
     }
     OutStreamer->emitLabel(MBB.getSymbol());
   }
 }
 
 void AsmPrinter::emitBasicBlockEnd(const MachineBasicBlock &MBB) {}
 
 void AsmPrinter::emitVisibility(MCSymbol *Sym, unsigned Visibility,

llvm/lib/CodeGen/BBSectionsPrepare.cpp

 //===-- BBSectionsPrepare.cpp ---=========---------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // BBSectionsPrepare implementation.
 //
 // The purpose of this pass is to assign sections to basic blocks when
-// -fbasicblock-sections= option is used.  Exception landing pad blocks are
-// specially handled by grouping them in a single section.  Further, with
+// -fbasicblock-sections= option is used.  Further, with
 // profile information only the subset of basic blocks with profiles are placed
-// in a separate section and the rest are grouped in a cold section.
+// in separate sections and the rest are grouped in a cold section. The
+// exception handling blocks are treated specially to ensure they are all in one
+// seciton.
 //
 // Basic Block Sections
 // ====================
 //
-// With option, -fbasicblock-sections=, each basic block could be placed in a
-// unique ELF text section in the object file along with a symbol labelling the
-// basic block. The linker can then order the basic block sections in any
-// arbitrary sequence which when done correctly can encapsulate block layout,
-// function layout and function splitting optimizations. However, there are a
-// couple of challenges to be addressed for this to be feasible:
-//
-// 1. The compiler must not allow any implicit fall-through between any two
-//    adjacent basic blocks as they could be reordered at link time to be
-//    non-adjacent. In other words, the compiler must make a fall-through
-//    between adjacent basic blocks explicit by retaining the direct jump
-//    instruction that jumps to the next basic block.
+// With option, -fbasicblock-sections=list, every function may be split into
+// clusters of basic blocks. Every cluster will be emitted into a separate
+// section with its basic blocks sequenced in the given order.
+// To get the optimized performance, the clusters must form an optimal BB layout
+// for the function.
+// Every cluster's section is labeled with a symbol to allow the linker to
+// reorder the sections in any arbitrary sequence.
+// A global order of these sections would encapsulate the function layout.
+//
+// There are a couple of challenges to be addressed:
+//
+// 1. The last basic block of every cluster should not have any implicit
+//    fallthrough to its next basic block, as it can be reordered by the linker.
+//    The compiler should make these fallthroughs explicit by adding
+//    unconditional jumps..
 //
-// 2. All inter-basic block branch targets would now need to be resolved by the
+// 2. All inter-cluster branch targets would now need to be resolved by the
 //    linker as they cannot be calculated during compile time. This is done
 //    using static relocations. Further, the compiler tries to use short branch
 //    instructions on some ISAs for small branch offsets. This is not possible
-//    with basic block sections as the offset is not determined at compile time,
-//    and long branch instructions have to be used everywhere.
+//    for inter-cluster branches as the offset is not determined at compile
+//    time, and therefore, long branch instructions have to be used for those.
 //
-// 3. Each additional section bloats object file sizes by tens of bytes.  The
-//    number of basic blocks can be potentially very large compared to the size
-//    of functions and can bloat object sizes significantly. Option
-//    fbasicblock-sections= also takes a file path which can be used to specify
-//    a subset of basic blocks that needs unique sections to keep the bloats
-//    small.
-//
-// 4. Debug Information (DebugInfo) and Call Frame Information (CFI) emission
+// 3. Debug Information (DebugInfo) and Call Frame Information (CFI) emission
 //    needs special handling with basic block sections. DebugInfo needs to be
 //    emitted with more relocations as basic block sections can break a
 //    function into potentially several disjoint pieces, and CFI needs to be
-//    emitted per basic block. This also bloats the object file and binary
-//    sizes.
+//    emitted per cluster. This also bloats the object file and binary sizes.
 //
 // Basic Block Labels
 // ==================
 //
 // With -fbasicblock-sections=labels, or when a basic block is placed in a
 // unique section, it is labelled with a symbol.  This allows easy mapping of
 // virtual addresses from PMU profiles back to the corresponding basic blocks.
 // Since the number of basic blocks is large, the labeling bloats the symbol

 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/LineIterator.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Target/TargetMachine.h"
 
+#include <iterator>
+#include <sstream>
 #include <string>
 
 using llvm::SmallSet;
 using llvm::StringMap;
 using llvm::StringRef;
 using namespace llvm;
 
 namespace {
 
+struct BBClusterInfo {
+  unsigned ClusterID;
+  unsigned PositionInCluster;
+};
+
 class BBSectionsPrepare : public MachineFunctionPass {
 public:
   static char ID;
-  StringMap<SmallSet<unsigned, 4>> BBSectionsList;
+
+  // This would hold the basic-block-sections profile.
   const MemoryBuffer *MBuf = nullptr;
 
-  BBSectionsPrepare() : MachineFunctionPass(ID) {
-    initializeBBSectionsPreparePass(*PassRegistry::getPassRegistry());
-  }
+  // This encapsulates the BB cluster information for every function.
+  // For every function name, we have a map from (some of) its basic block ids
+  // to its cluster information. The cluster information for every basic block
+  // includes its cluster ID along with the position of the basic block in that
+  // cluster.
+  StringMap<DenseMap<unsigned, BBClusterInfo>> BBClusterInfoMap;
+
+  // Some functions have alias names. We use this map to find the main alias
+  // name for which we have mapping in BBClusterInfoMap.
+  StringMap<StringRef> FuncAliasMap;
 
   BBSectionsPrepare(const MemoryBuffer *Buf)
       : MachineFunctionPass(ID), MBuf(Buf) {
     initializeBBSectionsPreparePass(*PassRegistry::getPassRegistry());
   };
 
+  BBSectionsPrepare() : MachineFunctionPass(ID) {
+    initializeBBSectionsPreparePass(*PassRegistry::getPassRegistry());
+  }
+
   StringRef getPassName() const override {
     return "Basic Block Sections Analysis";
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   /// Read profiles of basic blocks if available here.
   bool doInitialization(Module &M) override;
 
   /// Identify basic blocks that need separate sections and prepare to emit them
   /// accordingly.
   bool runOnMachineFunction(MachineFunction &MF) override;
+
+  // This function provides the BBCluster information associated with a function
+  // name. It returns true if mapping is found and false otherwise.
+  bool getBBClusterInfoForFunction(StringRef s,
+                                   DenseMap<unsigned, BBClusterInfo> &m) {
+    auto r = FuncAliasMap.find(s);
+    StringRef aliasName = r == FuncAliasMap.end() ? s : r->second;
+    auto p = BBClusterInfoMap.find(aliasName);
+    if (p == BBClusterInfoMap.end())
+      return false;
+    m = p->second;
+    return true;
+  }
 };
 
 } // end anonymous namespace
 
 char BBSectionsPrepare::ID = 0;
 INITIALIZE_PASS(BBSectionsPrepare, "bbsections-prepare",
-                "Determine if a basic block needs a special section", false,
-                false)
+                "Prepares for basic block sections, by splitting functions "
+                "into clusters of basic blocks.",
+                false, false)
 
 // This inserts an unconditional branch at the end of MBB to the next basic
 // block S if and only if the control-flow implicitly falls through from MBB to
-// S and S and MBB belong to different sections.  This is necessary with basic
-// block sections as MBB and S could be potentially reordered.
+// S. This is necessary with basic block sections as they can be reordered by
+// clustering or by the linker.
 static void insertUnconditionalFallthroughBranch(MachineBasicBlock &MBB) {
   MachineBasicBlock *Fallthrough = MBB.getFallThrough();
-
   if (Fallthrough == nullptr)
     return;
 
-  // If this basic block and the Fallthrough basic block are in the same
-  // section then do not insert the jump.
-  if (MBB.sameSection(Fallthrough))
-    return;
-
   const TargetInstrInfo *TII = MBB.getParent()->getSubtarget().getInstrInfo();
   SmallVector<MachineOperand, 4> Cond;
   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
 
   // If a branch to the fall through block already exists, return.
   if (!TII->analyzeBranch(MBB, TBB, FBB, Cond) &&
       (TBB == Fallthrough || FBB == Fallthrough)) {
     return;
   }
 
   Cond.clear();
   DebugLoc DL = MBB.findBranchDebugLoc();
   TII->insertBranch(MBB, Fallthrough, nullptr, Cond, DL);
 }
 
-/// This function sorts basic blocks according to the sections in which they are
-/// emitted.  Basic block sections automatically turn on function sections so
-/// the entry block is in the function section.  The other sections that are
-/// created are:
-/// 1) Exception section - basic blocks that are landing pads
-/// 2) Cold section - basic blocks that will not have unique sections.
-/// 3) Unique section - one per basic block that is emitted in a unique section.
-static bool assignSectionsAndSortBasicBlocks(
-    MachineFunction &MF,
-    const StringMap<SmallSet<unsigned, 4>> &BBSectionsList) {
-  SmallSet<unsigned, 4> S = BBSectionsList.lookup(MF.getName());
+// This function optimizes the branching instructions of every
+// basic block (except those at the end of the sections) in a given function.
+static void optimizeBBJumps(MachineFunction &MF) {
+  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
+  SmallVector<MachineOperand, 4> Cond;
+  for (auto &MBB : MF)
+    if (!MBB.isEndSection()) {
+      Cond.clear();
+      MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
+      if (!TII->analyzeBranch(MBB, TBB, FBB, Cond))
+        MBB.updateTerminator();
+    }
+}
 
-  bool HasHotEHPads = false;
+// 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.
+static bool assignSectionsAndSortBasicBlocks(
+    MachineFunction &MF, DenseMap<unsigned, BBClusterInfo> &FuncBBClusterInfo) {
+  // This is the set of sections which have EHPads in them.
+  SmallSet<unsigned, 2> EHPadsSections;
 
   for (auto &MBB : MF) {
-    // Entry basic block cannot start another section because the function
-    // starts one already.
-    if (MBB.getNumber() == MF.front().getNumber()) {
-      MBB.setSectionType(MachineBasicBlockSection::MBBS_Entry);
-      continue;
-    }
-    // Check if this BB is a cold basic block.  With the list option, all cold
-    // basic blocks can be clustered in a single cold section.
-    // All Exception landing pads must be in a single section.  If all the
-    // landing pads are cold, it can be kept in the cold section.  Otherwise, we
-    // create a separate exception section.
-    bool isColdBB = ((MF.getTarget().getBBSectionsType() ==
-                      llvm::BasicBlockSection::List) &&
-                     !S.empty() && !S.count(MBB.getNumber()));
-    if (isColdBB) {
-      MBB.setSectionType(MachineBasicBlockSection::MBBS_Cold);
-    } else if (MBB.isEHPad()) {
-      // We handle non-cold basic eh blocks later.
-      HasHotEHPads = true;
-    } else {
-      // Place this MBB in a unique section.  A unique section begins and ends
-      // that section by definition.
-      MBB.setSectionType(MachineBasicBlockSection::MBBS_Unique);
+    // 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 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(MBB.getNumber());
+    } else if (FuncBBClusterInfo.count(MBB.getNumber()))
+      MBB.setSectionID(FuncBBClusterInfo.lookup(MBB.getNumber()).ClusterID);
+    else {
+      // BB goes into the special cold section if it is not specified in the
+      // cluster info map.
+      MBB.setSectionID(MachineBasicBlock::ColdSectionID);
     }
+
+    if (MBB.isEHPad())
+      EHPadsSections.insert(MBB.getSectionID().getValue());
   }
 
-  // If some EH Pads are not cold then we move all EH Pads to the exception
-  // section as we require that all EH Pads be in a single section.
-  if (HasHotEHPads) {
+  // If EHPads are in more than one section, we move all of them to a specific
+  // exception section, as we need all EH Pads to be in a single section.
+  if (EHPadsSections.size() > 1) {
     std::for_each(MF.begin(), MF.end(), [&](MachineBasicBlock &MBB) {
       if (MBB.isEHPad())
-        MBB.setSectionType(MachineBasicBlockSection::MBBS_Exception);
+        MBB.setSectionID(MachineBasicBlock::ExceptionSectionID);
     });
   }
 
   for (auto &MBB : MF) {
     // With -fbasicblock-sections, fall through blocks must be made
-    // explicitly reachable.  Do this after sections is set as
-    // unnecessary fallthroughs can be avoided.
+    // explicitly reachable.
     insertUnconditionalFallthroughBranch(MBB);
   }
 
-  MF.sort(([&](MachineBasicBlock &X, MachineBasicBlock &Y) {
-    unsigned TypeX = X.getSectionType();
-    unsigned TypeY = Y.getSectionType();
+  // We make sure that the cluster including the entry basic block precedes all
+  // other clusters.
+  auto EntrySectionID = MF.front().getSectionID().getValue();
+
+  // We sort all basic blocks to make sure the basic blocks of every cluster are
+  // contiguous and ordered accordingly. Furthermore, clusters are ordered in
+  // increasing order of their section IDs, with the exception and the
+  // cold section placed at the end of the function.
+  MF.sort([&](MachineBasicBlock &X, MachineBasicBlock &Y) {
+    auto XSectionID = X.getSectionID().getValue();
+    auto YSectionID = Y.getSectionID().getValue();
+    // If the two basic block are in the same section, the order is decided by
+    // their position within the section.
+    if (XSectionID == YSectionID)
+      return XSectionID < MachineBasicBlock::ExceptionSectionID
+                 ? FuncBBClusterInfo.lookup(X.getNumber()).PositionInCluster <
+                       FuncBBClusterInfo.lookup(Y.getNumber()).PositionInCluster
+                 : X.getNumber() < Y.getNumber();
+    // We make sure that the section containing the entry block precedes all the
+    // other sections.
+    if (XSectionID == EntrySectionID || YSectionID == EntrySectionID)
+      return XSectionID == EntrySectionID;
+    return XSectionID < YSectionID;
+  });
 
-    return (TypeX != TypeY) ? TypeX < TypeY : X.getNumber() < Y.getNumber();
-  }));
+  // After ordering basic blocks, we optimize/remove branches which were
+  // previously added by insertUnconditionalFallthroughBranch.
+  optimizeBBJumps(MF);
 
-  MF.setSectionRange();
   return true;
 }
 
 bool BBSectionsPrepare::runOnMachineFunction(MachineFunction &MF) {
   auto BBSectionsType = MF.getTarget().getBBSectionsType();
   assert(BBSectionsType != BasicBlockSection::None &&
          "BB Sections not enabled!");
 
   // 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();
 
   if (BBSectionsType == BasicBlockSection::Labels) {
     MF.setBBSectionsType(BBSectionsType);
     MF.createBBLabels();
     return true;
   }
 
+  DenseMap<unsigned, BBClusterInfo> FuncBBClusterInfo;
   if (BBSectionsType == BasicBlockSection::List &&
-      BBSectionsList.find(MF.getName()) == BBSectionsList.end())
+      !getBBClusterInfoForFunction(MF.getName(), FuncBBClusterInfo))
     return true;
-
   MF.setBBSectionsType(BBSectionsType);
   MF.createBBLabels();
-  assignSectionsAndSortBasicBlocks(MF, BBSectionsList);
+  assignSectionsAndSortBasicBlocks(MF, FuncBBClusterInfo);
 
   return true;
 }
 
 // Basic Block Sections can be enabled for a subset of machine basic blocks.
 // This is done by passing a file containing names of functions for which basic
 // block sections are desired.  Additionally, machine basic block ids of the
-// functions can also be specified for a finer granularity.
-// A file with basic block sections for all of function main and two blocks for
-// function foo looks like this:
+// functions can also be specified for a finer granularity. Moreover, a cluster
+// of basic blocks could be assigned to the same section.
+// A file with basic block sections for all of function main and three blocks
+// for function foo (of which 1 and 2 are placed in a cluster) looks like this:
 // ----------------------------
 // list.txt:
 // !main
 // !foo
-// !!2
+// !!1 2
 // !!4
-static bool getBBSectionsList(const MemoryBuffer *MBuf,
-                              StringMap<SmallSet<unsigned, 4>> &bbMap) {
+static bool
+getBBClusterInfo(const MemoryBuffer *MBuf,
+                 StringMap<DenseMap<unsigned, BBClusterInfo>> &bbClusterInfoMap,
+                 StringMap<StringRef> &funcAliasMap) {
   if (!MBuf)
     return false;
 
   line_iterator LineIt(*MBuf, /*SkipBlanks=*/true, /*CommentMarker=*/'#');
 
-  StringMap<SmallSet<unsigned, 4>>::iterator fi = bbMap.end();
+  StringMap<DenseMap<unsigned, BBClusterInfo>>::iterator fi =
+      bbClusterInfoMap.end();
+
+  unsigned CurrentCluster = 0;
+  unsigned CurrentPosition = 0;
 
   for (; !LineIt.is_at_eof(); ++LineIt) {
     StringRef s(*LineIt);
     if (s[0] == '@')
       continue;
     // Check for the leading "!"
     if (!s.consume_front("!") || s.empty())
       break;
-    // Check for second "!" which encodes basic block ids.
+    // Check for second "!" which indicates a cluster of basic blocks.
     if (s.consume_front("!")) {
-      if (fi != bbMap.end())
-        fi->second.insert(std::stoi(s.str()));
-      else
+      if (fi == bbClusterInfoMap.end()) {
+        errs() << "Could not process profile: " << MBuf->getBufferIdentifier()
+               << " at line " << Twine(LineIt.line_number())
+               << ": Does not follow a function name.\n";
+        return false;
+      }
+      std::istringstream iss(s.str());
+      std::vector<std::string> BBIndexes(
+          (std::istream_iterator<std::string>(iss)),
+          std::istream_iterator<std::string>());
+      // Current position in the current cluster of basic blocks.
+      CurrentPosition = 0;
+      for (auto &BBIndexStr : BBIndexes) {
+        unsigned BBIndex;
+        if (StringRef(BBIndexStr).getAsInteger(10, BBIndex)) {
+          errs() << "Could not process profile: " << MBuf->getBufferIdentifier()
+                 << " at line " << Twine(LineIt.line_number()) << ": "
+                 << BBIndexStr << " is not a number!\n";
+          return false;
+        }
+        if (!BBIndex && CurrentPosition) {
+          errs() << "Could not process profile " << MBuf->getBufferIdentifier()
+                 << " at line " << Twine(LineIt.line_number())
+                 << ": Entry BB in the middle of the BB Cluster list!\n";
           return false;
+        }
+        fi->second.try_emplace(
+            BBIndex, BBClusterInfo{CurrentCluster, CurrentPosition++});
+      }
+      CurrentCluster++;
     } else {
+      // Function aliases are separated using '/'. We use the first function
+      // name for the cluster info mapping and delegate all other aliases to
+      // this one.
+      auto P = s.split('/');
       // Start a new function.
-      auto R = bbMap.try_emplace(s.split('/').first);
-      fi = R.first;
-      assert(R.second);
+      fi = bbClusterInfoMap.try_emplace(P.first).first;
+
+      auto aliasStr = P.second;
+      while (aliasStr != "") {
+        auto Q = aliasStr.split('/');
+        funcAliasMap.try_emplace(Q.first, P.first);
+        aliasStr = Q.second;
+      }
+      CurrentCluster = 0;
     }
   }
   return true;
 }
 
 bool BBSectionsPrepare::doInitialization(Module &M) {
   if (MBuf)
-    getBBSectionsList(MBuf, BBSectionsList);
+    if (!getBBClusterInfo(MBuf, BBClusterInfoMap, FuncAliasMap))
+      BBClusterInfoMap.clear();
   return true;
 }
 
 void BBSectionsPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<MachineModuleInfoWrapperPass>();
 }
 
 MachineFunctionPass *
 llvm::createBBSectionsPreparePass(const MemoryBuffer *Buf) {
   return new BBSectionsPrepare(Buf);
 }

llvm/lib/CodeGen/MIRParser/MIParser.cpp

bool parseMachineOperand(const unsigned OpCode, const unsigned OpIdx,
                            Optional<unsigned> &TiedDefIdx);
   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 parseMBBS(MachineBasicBlockSection &T);
+  bool parseSectionID(Optional<unsigned> &SID);
   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);

 
 bool MIParser::consumeIfPresent(MIToken::TokenKind TokenKind) {
   if (Token.isNot(TokenKind))
     return false;
   lex();
   return true;
 }
 
-// Parse Machine Basic Block Section Type.
-bool MIParser::parseMBBS(MachineBasicBlockSection &T) {
+// Parse Machine Basic Block Section ID.
+bool MIParser::parseSectionID(Optional<unsigned> &SID) {
   assert(Token.is(MIToken::kw_bbsections));
   lex();
+  if (Token.is(MIToken::IntegerLiteral)) {
+    unsigned Value = 0;
+    if (getUnsigned(Value))
+      return error("Uknown Section ID");
+    SID = Value;
+  } else {
     const StringRef &S = Token.stringValue();
-  if (S == "Entry")
-    T = MBBS_Entry;
-  else if (S == "Exception")
-    T = MBBS_Exception;
+    if (S == "Exception")
+      SID = MachineBasicBlock::ExceptionSectionID;
     else if (S == "Cold")
-    T = MBBS_Cold;
-  else if (S == "Unique")
-    T = MBBS_Unique;
+      SID = MachineBasicBlock::ColdSectionID;
     else
-    return error("Unknown Section Type");
+      return error("Unknown Section ID");
+  }
   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;
-  MachineBasicBlockSection SectionType = MBBS_None;
+  Optional<unsigned> SectionID;
   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 {
         break;
       case MIToken::IRBlock:
         // TODO: Report an error when both name and ir block are specified.
         if (parseIRBlock(BB, MF.getFunction()))
           return true;
         lex();
         break;
       case MIToken::kw_bbsections:
-        if (parseMBBS(SectionType))
+        if (parseSectionID(SectionID))
           return true;
         break;
       default:
         break;
       }
     } while (consumeIfPresent(MIToken::comma));
     if (expectAndConsume(MIToken::rparen))
       return true;
if (!WasInserted)
     return error(Loc, Twine("redefinition of machine basic block with id #") +
                           Twine(ID));
   if (Alignment)
     MBB->setAlignment(Align(Alignment));
   if (HasAddressTaken)
     MBB->setHasAddressTaken();
   MBB->setIsEHPad(IsLandingPad);
   MBB->setIsEHFuncletEntry(IsEHFuncletEntry);
-  if (SectionType != MBBS_None) {
-    MBB->setSectionType(SectionType);
+  if (SectionID.hasValue()) {
+    MBB->setSectionID(SectionID.getValue());
     MF.setBBSectionsType(BasicBlockSection::List);
   }
   return false;
 }
 
 bool MIParser::parseBasicBlockDefinitions(
     DenseMap<unsigned, MachineBasicBlock *> &MBBSlots) {
   lex();

llvm/lib/CodeGen/MIRParser/MIRParser.cpp

 #include "llvm/Target/TargetMachine.h"
 #include <memory>
 
 using namespace llvm;
 
 namespace llvm {
 
 /// This class implements the parsing of LLVM IR that's embedded inside a MIR
 /// file.
 class MIRParserImpl {
   SourceMgr SM;
   yaml::Input In;
   StringRef Filename;
   LLVMContext &Context;
   SlotMapping IRSlots;
   std::unique_ptr<PerTargetMIParsingState> Target;
 
if (parseMachineBasicBlockDefinitions(PFS, BlockStr, Error)) {
     reportDiagnostic(
         diagFromBlockStringDiag(Error, YamlMF.Body.Value.SourceRange));
     return true;
   }
   // Check Basic Block Section Flags.
   if (MF.getTarget().getBBSectionsType() == BasicBlockSection::Labels) {
     MF.createBBLabels();
     MF.setBBSectionsType(BasicBlockSection::Labels);
-  } else if (MF.hasBBSections()) {
-    MF.setSectionRange();
+  } else if (MF.hasBBSections())
     MF.createBBLabels();
-  }
   PFS.SM = &SM;
 
   // Initialize the frame information after creating all the MBBs so that the
   // MBB references in the frame information can be resolved.
   if (initializeFrameInfo(PFS, YamlMF))
     return true;
   // Initialize the jump table after creating all the MBBs so that the MBB
   // references can be resolved.

llvm/lib/CodeGen/MIRPrinter.cpp

if (MBB.isEHFuncletEntry()) {
     OS << "ehfunclet-entry";
     HasAttributes = true;
   }
   if (MBB.getAlignment() != Align(1)) {
     OS << (HasAttributes ? ", " : " (");
     OS << "align " << MBB.getAlignment().value();
     HasAttributes = true;
   }
-  if (MBB.getSectionType() != MBBS_None) {
+  if (MBB.getSectionID().hasValue()) {
     OS << (HasAttributes ? ", " : " (");
     OS << "bbsections ";
-    switch (MBB.getSectionType()) {
-    case MBBS_Entry:
-      OS << "Entry";
+    switch (MBB.getSectionID().getValue()) {
+    case MachineBasicBlock::ExceptionSectionID:
+      OS << "Excetion";
       break;
-    case MBBS_Exception:
-      OS << "Exception";
-      break;
-    case MBBS_Cold:
+    case MachineBasicBlock::ColdSectionID:
       OS << "Cold";
       break;
-    case MBBS_Unique:
-      OS << "Unique";
-      break;
     default:
-      llvm_unreachable("No such section type");
+      OS << MBB.getSectionID();
     }
     HasAttributes = true;
   }
   if (HasAttributes)
     OS << ")";
   OS << ":\n";
 
   bool HasLineAttributes = false;

llvm/lib/CodeGen/MachineBasicBlock.cpp

void MachineBasicBlock::moveBefore(MachineBasicBlock *NewAfter) {
   getParent()->splice(NewAfter->getIterator(), getIterator());
 }
 
 void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
   getParent()->splice(++NewBefore->getIterator(), getIterator());
 }
 
 // Returns true if this basic block and the Other are in the same section.
 bool MachineBasicBlock::sameSection(const MachineBasicBlock *Other) const {
   if (this == Other)
     return true;
 
-  if (this->getSectionType() != Other->getSectionType())
-    return false;
-
-  // If either is in a unique section, return false.
-  if (this->getSectionType() == llvm::MachineBasicBlockSection::MBBS_Unique ||
-      Other->getSectionType() == llvm::MachineBasicBlockSection::MBBS_Unique)
+  if (this->getSectionID() != Other->getSectionID())
     return false;
 
   return true;
 }
 
 const MachineBasicBlock *MachineBasicBlock::getSectionEndMBB() const {
   if (this->isEndSection())
     return this;
   auto I = std::next(this->getIterator());
   const MachineFunction *MF = getParent();
   while (I != MF->end()) {
     const MachineBasicBlock &MBB = *I;
     if (MBB.isEndSection())
       return &MBB;
     I = std::next(I);
   }
   llvm_unreachable("No End Basic Block for this section.");
 }
 
 // Returns true if this block begins any section.
 bool MachineBasicBlock::isBeginSection() const {
-  return (SectionType == MBBS_Entry || SectionType == MBBS_Unique ||
-          getParent()->isSectionStartMBB(getNumber()));
+  const MachineFunction *MF = getParent();
+  if (!MF->hasBBSections())
+    return false;
+  auto I = std::next(this->getReverseIterator());
+  return (I == MF->rend()) || (I->getSectionID() != getSectionID());
 }
 
 // Returns true if this block begins any section.
 bool MachineBasicBlock::isEndSection() const {
-  return (SectionType == MBBS_Entry || SectionType == MBBS_Unique ||
-          getParent()->isSectionEndMBB(getNumber()));
+  const MachineFunction *MF = getParent();
+  if (!MF->hasBBSections())
+    return false;
+  auto I = std::next(this->getIterator());
+  return (I == MF->end()) || (I->getSectionID() != getSectionID());
 }
 
 void MachineBasicBlock::updateTerminator() {
   const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
   // A block with no successors has no concerns with fall-through edges.
   if (this->succ_empty())
     return;
 

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

llvm/lib/CodeGen/MachineFunction.cpp

void MachineFunction::RenumberBlocks(MachineBasicBlock *MBB) {
   }
 
   // Okay, all the blocks are renumbered.  If we have compactified the block
   // numbering, shrink MBBNumbering now.
   assert(BlockNo <= MBBNumbering.size() && "Mismatch!");
   MBBNumbering.resize(BlockNo);
 }
 
-/// This sets the section ranges of cold or exception section with basic block
-/// sections.
-void MachineFunction::setSectionRange() {
-  // Compute the Section Range of cold and exception basic blocks.  Find the
-  // first and last block of each range.
-  auto SectionRange =
-      ([&](llvm::MachineBasicBlockSection S) -> std::pair<int, int> {
-        auto MBBP =
-            std::find_if(begin(), end(), [&](MachineBasicBlock &MBB) -> bool {
-              return MBB.getSectionType() == S;
-            });
-        if (MBBP == end())
-          return std::make_pair(-1, -1);
-
-        auto MBBQ =
-            std::find_if(rbegin(), rend(), [&](MachineBasicBlock &MBB) -> bool {
-              return MBB.getSectionType() == S;
-            });
-        assert(MBBQ != rend() && "Section end not found!");
-        return std::make_pair(MBBP->getNumber(), MBBQ->getNumber());
-      });
-
-  ExceptionSectionRange = SectionRange(MBBS_Exception);
-  ColdSectionRange = SectionRange(llvm::MBBS_Cold);
-}
-
 /// This is used with -fbasicblock-sections or -fbasicblock-labels option.
 /// A unary encoding of basic block labels is done to keep ".strtab" sizes
 /// small.
 void MachineFunction::createBBLabels() {
   const TargetInstrInfo *TII = getSubtarget().getInstrInfo();
   this->BBSectionsSymbolPrefix.resize(getNumBlockIDs(), 'a');
   for (auto MBBI = begin(), E = end(); MBBI != E; ++MBBI) {
     assert(
else if (isRetBlock)
       type = 'r';
     BBSectionsSymbolPrefix[MBBI->getNumber()] = type;
   }
 }
 
 /// Allocate a new MachineInstr. Use this instead of `new MachineInstr'.
 MachineInstr *MachineFunction::CreateMachineInstr(const MCInstrDesc &MCID,
                                                   const DebugLoc &DL,
                                                   bool NoImp) {
   return new (InstructionRecycler.Allocate<MachineInstr>(Allocator))
     MachineInstr(*this, MCID, DL, NoImp);
 }
 
 /// Create a new MachineInstr which is a copy of the 'Orig' instruction,
 /// identical in all ways except the instruction has no parent, prev, or next.
 MachineInstr *
 MachineFunction::CloneMachineInstr(const MachineInstr *Orig) {

llvm/test/CodeGen/X86/basicblock-sections-eh.ll

 declare i32 @__gxx_personality_v0(...)
 ; Function Attrs: nounwind readnone
 declare i32 @llvm.eh.typeid.for(i8*) #1
 declare i8* @__cxa_begin_catch(i8*)
 declare void @__cxa_end_catch()
 
 ;LINUX-SECTIONS: .section .text._Z3foob,"ax",@progbits
 ;LINUX-SECTIONS: _Z3foob:
-;LINUX-SECTIONS: .section .text._Z3foob.eh,"ax",@progbits
+;LINUX-SECTIONS: .section       .text._Z3foob.laara.BB._Z3foob,"ax",@progbits
 ;LINUX-SECTIONS: l{{[a|r]*}}.BB._Z3foob:

llvm/test/CodeGen/X86/basicblock-sections-listbb.ll

 
 ; LINUX-SECTIONS: .section        .text._Z3bazb,"ax",@progbits
 ; LINUX-SECTIONS: _Z3bazb:
 ; Check that the basic block with id 1 doesn't get a section.
 ; LINUX-SECTIONS-NOT: .section        .text._Z3bazb.r.BB._Z3bazb,"ax",@progbits,unique
 ; LINUX-SECTIONS: r.BB._Z3bazb:
 ; LINUX-SECTIONS: .section        .text._Z3bazb.rr.BB._Z3bazb,"ax",@progbits,unique
 ; LINUX-SECTIONS: rr.BB._Z3bazb:
-; LINUX-SECTIONS: .size   rr.BB._Z3bazb, .Ltmp1-rr.BB._Z3bazb
+; LINUX-SECTIONS: .size   rr.BB._Z3bazb, .Ltmp0-rr.BB._Z3bazb

llvm/test/CodeGen/X86/basicblock-sections-mir-parse.mir

- { id: 0, type: default, offset: -24, size: 4,
       debug-info-variable: '', debug-info-expression: '', debug-info-location: '' }
   - { id: 1, 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:       []
 constants:       []
 machineFunctionInfo: {}
 body:             |
-  bb.0 (%ir-block.1, bbsections Entry):
+  bb.0 (%ir-block.1, align 4, bbsections 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
     JMP_1 %bb.1
   
-  bb.1 (%ir-block.7, bbsections Unique):
+  bb.1 (%ir-block.7, bbsections 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, bbsections Unique):
+  bb.2 (%ir-block.8, bbsections 2):
     successors: %bb.3(0x80000000)
   
     MOV32mi $rbp, 1, $noreg, -8, $noreg, 0 :: (store 4 into %ir.2)
     JMP_1 %bb.3
   
-  bb.3 (%ir-block.9, bbsections Unique):
+  bb.3 (%ir-block.9, bbsections 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: _Z3foob:
 # CHECK: .section .text,"ax",@progbits,unique
 # CHECK: a.BB._Z3foob:
 # CHECK: .section .text,"ax",@progbits,unique
 # CHECK: aa.BB._Z3foob:
 # CHECK: .section .text,"ax",@progbits,unique
 # CHECK: aaa.BB._Z3foob:

llvm/test/CodeGen/X86/basicblock-sections-mir-print.ll

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: bbsections Entry
-; CHECK: bbsections Cold
-; CHECK: bbsections Cold
-; CHECK: bbsections Unique
+; CHECK: bb.0 (%ir-block.1, bbsections Cold):
+; CHECK: bb.2 (%ir-block.8, bbsections Cold):
+; CHECK: bb.3 (%ir-block.9, bbsections Cold):
+; CHECK: bb.1 (%ir-block.7, bbsections 0)