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

180

s/accout/account

287

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?

350

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.

364

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

388

Why not make it one expression?

411

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

llvm/lib/CodeGen/MIRPrinter.cpp

647

s/Excetion/Exception

[tmsriram]

llvm/lib/CodeGen/MachineBasicBlock.cpp

559

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

290–291

You can also add EHPadsSectionID != ExceptionSectionID

331–332

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

llvm/lib/CodeGen/MachineBasicBlock.cpp

550–551

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

550–551

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

490

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

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1181

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

1209

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

554–555

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

1202–1205

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

340

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;
+  /// With basic block sections, this stores the Section ID of the basic block.
+  Optional<unsigned> SectionID;
+
+  // Indicate that this basic block begins a section.
+  bool IsBeginSection = false;
+
+  // Indicate that this basic block ends a section.
+  bool IsEndSection = false;
 
   /// 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
 
   /// Returns true if this is the entry block of a cleanup funclet.
   bool isCleanupFuncletEntry() const { return IsCleanupFuncletEntry; }
 
   /// Indicates if this is the entry block of a cleanup funclet.
   void setIsCleanupFuncletEntry(bool V = true) { IsCleanupFuncletEntry = V; }
 
   /// Returns true if this block begins any section.
-  bool isBeginSection() const;
+  bool isBeginSection() const { return IsBeginSection; }
 
   /// Returns true if this block ends any section.
-  bool isEndSection() const;
+  bool isEndSection() const { return IsEndSection; }
+
+  void setIsBeginSection(bool V = true) { IsBeginSection = V; }
 
-  /// Returns the type of section this basic block belongs to.
-  MachineBasicBlockSection getSectionType() const { return SectionType; }
+  void setIsEndSection(bool V = true) { IsEndSection = V; }
+
+  /// Returns the section ID of this basic block.
+  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;
+  bool sameSection(const MachineBasicBlock *MBB) const {
+    return this == MBB || getSectionID() == MBB->getSectionID();
+  }
 
   /// 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.

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) {
-    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.
     emitBasicBlockStart(MBB);
     for (auto &MI : MBB) {
       // Print the assembly for the instruction.
       if (!MI.isPosition() && !MI.isImplicitDef() && !MI.isKill() &&
           !MI.isDebugInstr()) {
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())) {
-      // Emit size directive for the size of this basic block.  Create a symbol
-      // for the end of the basic block.
+
+    if (MF->hasBBLabels() ||
+        (MBB.isEndSection() && !MBB.sameSection(&MF->front()))) {
+      // Emit size directive for the size of this basic block (or basic block
+      // section). Create a symbol for the end of the basic block.
       MCSymbol *CurrentBBEnd = OutContext.createTempSymbol();
+      OutStreamer->emitLabel(CurrentBBEnd);
+      MCSymbol *SymForSize =
+          MBB.isEndSection() ? CurrentSectionBeginSym : MBB.getSymbol();
       const MCExpr *SizeExp = MCBinaryExpr::createSub(
           MCSymbolRefExpr::create(CurrentBBEnd, OutContext),
-          MCSymbolRefExpr::create(MBB.getSymbol(), OutContext), OutContext);
-      OutStreamer->emitLabel(CurrentBBEnd);
+          MCSymbolRefExpr::create(SymForSize, OutContext), OutContext);
+      OutStreamer->emitELFSize(SymForSize, SizeExp);
+
+      if (MBB.isEndSection())
         MBB.setEndMCSymbol(CurrentBBEnd);
-      OutStreamer->emitELFSize(MBB.getSymbol(), SizeExp);
     }
     emitBasicBlockEnd(MBB);
   }
 
   EmittedInsts += NumInstsInFunction;
   MachineOptimizationRemarkAnalysis R(DEBUG_TYPE, "InstructionCount",
                                       MF->getFunction().getSubprogram(),
                                       &MF->front());
   R << ore::NV("NumInstructions", NumInstsInFunction)
     << " instructions in function";
   ORE->emit(R);
 
   // If the function is empty and the object file uses .subsections_via_symbols,
   // then we need to emit *something* to the function body to prevent the
   // labels from collapsing together.  Just emit a noop.
   // Similarly, don't emit empty functions on Windows either. It can lead to
   // duplicate entries (two functions with the same RVA) in the Guard CF Table
   // after linking, causing the kernel not to load the binary:
   // https://developercommunity.visualstudio.com/content/problem/45366/vc-linker-creates-invalid-dll-with-clang-cl.html
   // FIXME: Hide this behind some API in e.g. MCAsmInfo or MCTargetStreamer.
   const Triple &TT = TM.getTargetTriple();
   if (!HasAnyRealCode && (MAI->hasSubsectionsViaSymbols() ||
                           (TT.isOSWindows() && TT.isOSBinFormatCOFF()))) {
     MCInst Noop;
     MF->getSubtarget().getInstrInfo()->getNoop(Noop);
 
     // Targets can opt-out of emitting the noop here by leaving the opcode
     // 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)
-    EndOfRegularSectionMBB->setEndMCSymbol(CurrentFnEnd);
+  if (MF->hasBBSections())
+    (const_cast<MachineBasicBlock *>(MF->front().getSectionEndMBB()))
+        ->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,
                        HI.TimerGroupDescription, TimePassesIsEnabled);
if (!MAI->needsFunctionDescriptors()) {
 
     // Get the function entry point symbol.
     CurrentFnSym = OutContext.getOrCreateSymbol(
         "." + cast<MCSymbolXCOFF>(CurrentFnDescSym)->getUnqualifiedName());
   }
 
   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,
                                 bool IsDefinition) const {
   MCSymbolAttr Attr = MCSA_Invalid;
 
   switch (Visibility) {
   default: break;
   case GlobalValue::HiddenVisibility:
     if (IsDefinition)
       Attr = MAI->getHiddenVisibilityAttr();
     else
       Attr = MAI->getHiddenDeclarationVisibilityAttr();
     break;

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
-// 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.
+// -fbasicblock-sections= option is used. Further, with profile information only
+// the subset of basic blocks with profiles are placed 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
 // table sizes and the string table sizes significantly. While the binary size
 // does increase, it does not affect performance as the symbol table is not
 // loaded in memory during run-time. The string table size bloat is kept very
 // minimal using a unary naming scheme that uses string suffix compression. The
 // basic blocks for function foo are named "a.BB.foo", "aa.BB.foo", ... This
 // turns out to be very good for string table sizes and the bloat in the string
 // table size for a very large binary is ~8 %.  The naming also allows using
 // the --symbol-ordering-file option in LLD to arbitrarily reorder the
 // sections.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/InitializePasses.h"
+#include "llvm/Support/Error.h"
 #include "llvm/Support/LineIterator.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Target/TargetMachine.h"
 
-#include <string>
+#include <iterator>
 
 using llvm::SmallSet;
+using llvm::SmallVector;
 using llvm::StringMap;
 using llvm::StringRef;
 using namespace llvm;
 
 namespace {
 
+// This struct represents the cluster information for a machine basic block.
+struct BBClusterInfo {
+  // MachineBasicBlock ID.
+  unsigned MBBNumber;
+  // Cluster ID this basic block belongs to.
+  unsigned ClusterID;
+  // Position of basic block within the cluster.
+  unsigned PositionInCluster;
+};
+
+using ProgramBBClusterInfoMapTy = StringMap<SmallVector<BBClusterInfo, 4>>;
+
 class BBSectionsPrepare : public MachineFunctionPass {
 public:
   static char ID;
-  StringMap<SmallSet<unsigned, 4>> BBSectionsList;
+
+  // This contains the basic-block-sections profile.
   const MemoryBuffer *MBuf = nullptr;
 
-  BBSectionsPrepare() : MachineFunctionPass(ID) {
-    initializeBBSectionsPreparePass(*PassRegistry::getPassRegistry());
-  }
+  // This encapsulates the BB cluster information for the whole program.
+  //
+  // For every function name, it contains the cluster information for (all or
+  // some of) its basic blocks. The cluster information for every basic block
+  // includes its cluster ID along with the position of the basic block in that
+  // cluster.
+  ProgramBBClusterInfoMapTy ProgramBBClusterInfo;
+
+  // Some functions have alias names. We use this map to find the main alias
+  // name for which we have mapping in ProgramBBClusterInfo.
+  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;
 };
 
 } // 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 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) {
+  const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
+  SmallVector<MachineOperand, 4> Cond;
+  for (auto &MBB : MF) {
+    auto NextMBBI = std::next(MBB.getIterator());
+    auto *FTMBB = PreLayoutFallThroughs[MBB.getNumber()];
+    // If this block had a fallthrough before we need an explicit unconditional
+    // branch to that block if either
+    //     1- the block ends a section, which means its next block may be
+    //        reorderd by the linker, or
+    //     2- the fallthrough block is not adjacent to the block in the new
+    //        order.
+    if (FTMBB && (MBB.isEndSection() || &*NextMBBI != FTMBB))
+      TII->insertUnconditionalBranch(MBB, FTMBB, MBB.findBranchDebugLoc());
+
+    // We do not optimize branches for machine basic blocks ending sections, as
+    // their adjacent block might be reordered by the linker.
+    if (MBB.isEndSection())
+      continue;
 
-// 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.
-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;
+    // It might be possible to optimize branches by flipping the branch
+    // condition.
+    Cond.clear();
+    MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For analyzeBranch.
+    if (TII->analyzeBranch(MBB, TBB, FBB, Cond))
+      continue;
+    MBB.updateTerminator();
+  }
+}
 
-  const TargetInstrInfo *TII = MBB.getParent()->getSubtarget().getInstrInfo();
-  SmallVector<MachineOperand, 4> Cond;
-  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
+/// This method iterates over the basic blocks and assigns their IsBeginSection
+/// and IsEndSection fields. This must be called after MBB layout is finalized
+/// and the SectionID's are assigned to MBBs.
+static void assignBeginEndSections(MachineFunction &MF) {
+  MF.front().setIsBeginSection();
+  auto CurrentSectionID = MF.front().getSectionID();
+  for (auto MBBI = std::next(MF.begin()), E = MF.end(); MBBI != E; ++MBBI) {
+    if (MBBI->getSectionID() == CurrentSectionID)
+      continue;
+    MBBI->setIsBeginSection();
+    std::prev(MBBI)->setIsEndSection();
+    CurrentSectionID = MBBI->getSectionID();
+  }
+  MF.back().setIsEndSection();
+}
+
+// This function provides the BBCluster information associated with a function.
+// Returns true if a valid association exists and false otherwise.
+static bool getBBClusterInfoForFunction(
+    const MachineFunction &MF, const StringMap<StringRef> FuncAliasMap,
+    const ProgramBBClusterInfoMapTy &ProgramBBClusterInfo,
+    std::vector<Optional<BBClusterInfo>> &V) {
+  // Get the main alias name for the function.
+  auto FuncName = MF.getName();
+  auto R = FuncAliasMap.find(FuncName);
+  StringRef AliasName = R == FuncAliasMap.end() ? FuncName : R->second;
+
+  // Find the assoicated cluster information.
+  auto P = ProgramBBClusterInfo.find(AliasName);
+  if (P == ProgramBBClusterInfo.end())
+    return false;
 
-  // If a branch to the fall through block already exists, return.
-  if (!TII->analyzeBranch(MBB, TBB, FBB, Cond) &&
-      (TBB == Fallthrough || FBB == Fallthrough)) {
-    return;
+  if (P->second.empty()) {
+    // This indicates that sections are desired for all basic blocks of this
+    // function. We clear the BBClusterInfo vector to denote this.
+    V.clear();
+    return true;
   }
 
-  Cond.clear();
-  DebugLoc DL = MBB.findBranchDebugLoc();
-  TII->insertBranch(MBB, Fallthrough, nullptr, Cond, DL);
+  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;
+  }
+  return true;
 }
 
-/// 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.
+// This function sorts basic blocks according to the cluster's information.
+// All explicitly specified clusters of basic blocks will be ordered
+// accordingly. All non-specified BBs go into a separate "Cold" section.
+// Additionally, if exception handling landing pads end up in more than one
+// clusters, they are moved into a single "Exception" section. Eventually,
+// clusters are ordered in increasing order of their IDs, with the "Exception"
+// and "Cold" succeeding all other clusters.
+// FuncBBClusterInfo represent the cluster information for basic blocks. If this
+// is empty, it means unique sections for all basic blocks in the function.
 static bool assignSectionsAndSortBasicBlocks(
     MachineFunction &MF,
-    const StringMap<SmallSet<unsigned, 4>> &BBSectionsList) {
-  SmallSet<unsigned, 4> S = BBSectionsList.lookup(MF.getName());
-
-  bool HasHotEHPads = false;
+    const std::vector<Optional<BBClusterInfo>> &FuncBBClusterInfo) {
+  assert(MF.hasBBSections() && "BB Sections is not set for function.");
+  // This variable stores the section ID of the cluster containing eh_pads (if
+  // all eh_pads are one cluster). If more than one cluster contain eh_pads, we
+  // set it equal to ExceptionSectionID.
+  Optional<unsigned> EHPadsSectionID;
 
   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 individual unique sections
+    // for every basic block in this function (if FuncBBClusterInfo is empty).
+    if (MF.getTarget().getBBSectionsType() == llvm::BasicBlockSection::All ||
+        FuncBBClusterInfo.empty()) {
+      // If unique sections are desired for all basic blocks of the function, we
+      // set every basic block's section ID equal to its number (basic block
+      // id). This further ensures that basic blocks are ordered canonically.
+      MBB.setSectionID(MBB.getNumber());
+    } else if (FuncBBClusterInfo[MBB.getNumber()].hasValue())
+      MBB.setSectionID(FuncBBClusterInfo[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() && EHPadsSectionID != MBB.getSectionID() &&
+        EHPadsSectionID != MachineBasicBlock::ExceptionSectionID) {
+      // If we already have one cluster containing eh_pads, this must be updated
+      // to ExceptionSectionID. Otherwise, we set it equal to the current
+      // section ID.
+      EHPadsSectionID = EHPadsSectionID.hasValue()
+                            ? MachineBasicBlock::ExceptionSectionID
+                            : MBB.getSectionID();
     }
   }
 
-  // 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) {
-    std::for_each(MF.begin(), MF.end(), [&](MachineBasicBlock &MBB) {
+  // If EHPads are in more than one section, this places all of them in the
+  // special exception section.
+  if (EHPadsSectionID == MachineBasicBlock::ExceptionSectionID)
+    for (auto &MBB : MF)
       if (MBB.isEHPad())
-        MBB.setSectionType(MachineBasicBlockSection::MBBS_Exception);
-    });
-  }
+        MBB.setSectionID(EHPadsSectionID.getValue());
 
-  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.
-    insertUnconditionalFallthroughBranch(MBB);
-  }
+  SmallVector<MachineBasicBlock *, 4> PreLayoutFallThroughs(
+      MF.getNumBlockIDs());
+  for (auto &MBB : MF)
+    PreLayoutFallThroughs[MBB.getNumber()] = MBB.getFallThrough();
+
+  // We make sure that the cluster including the entry basic block precedes all
+  // other clusters.
+  auto EntryBBSectionID = 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 ||
+              XSectionID == MachineBasicBlock::ColdSectionID)
+                 ? X.getNumber() < Y.getNumber()
+                 : FuncBBClusterInfo[X.getNumber()]->PositionInCluster <
+                       FuncBBClusterInfo[Y.getNumber()]->PositionInCluster;
+    // We make sure that the section containing the entry block precedes all the
+    // other sections.
+    if (XSectionID == EntryBBSectionID || YSectionID == EntryBBSectionID)
+      return XSectionID == EntryBBSectionID;
+    return XSectionID < YSectionID;
+  });
 
-  MF.sort(([&](MachineBasicBlock &X, MachineBasicBlock &Y) {
-    unsigned TypeX = X.getSectionType();
-    unsigned TypeY = Y.getSectionType();
+  // Set IsBeginSection and IsEndSection according to the assigned section IDs.
+  assignBeginEndSections(MF);
 
-    return (TypeX != TypeY) ? TypeX < TypeY : X.getNumber() < Y.getNumber();
-  }));
+  // After reordering basic blocks, we must update basic block branches to
+  // insert explicit fallthrough branches when required and optimize branches
+  // when possible.
+  updateBranches(MF, PreLayoutFallThroughs);
 
-  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;
   }
 
+  std::vector<Optional<BBClusterInfo>> FuncBBClusterInfo;
   if (BBSectionsType == BasicBlockSection::List &&
-      BBSectionsList.find(MF.getName()) == BBSectionsList.end())
+      !getBBClusterInfoForFunction(MF, FuncAliasMap, ProgramBBClusterInfo,
+                                   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) {
-  if (!MBuf)
-    return false;
-
+static Error getBBClusterInfo(const MemoryBuffer *MBuf,
+                              ProgramBBClusterInfoMapTy &ProgramBBClusterInfo,
+                              StringMap<StringRef> &FuncAliasMap) {
+  assert(MBuf);
   line_iterator LineIt(*MBuf, /*SkipBlanks=*/true, /*CommentMarker=*/'#');
 
-  StringMap<SmallSet<unsigned, 4>>::iterator fi = bbMap.end();
+  auto invalidProfileError = [&](auto Message) {
+    return make_error<StringError>(
+        Twine("Invalid profile " + MBuf->getBufferIdentifier() + " at line " +
+              Twine(LineIt.line_number()) + ": " + Message),
+        inconvertibleErrorCode());
+  };
+
+  auto FI = ProgramBBClusterInfo.end();
+
+  // Current cluster ID corresponding to this function.
+  unsigned CurrentCluster = 0;
+  // Current position in the current cluster.
+  unsigned CurrentPosition = 0;
+
+  // Temporary set to ensure every basic block ID appears once in the clusters
+  // of a function.
+  SmallSet<unsigned, 4> FuncBBIDs;
 
   for (; !LineIt.is_at_eof(); ++LineIt) {
-    StringRef s(*LineIt);
-    if (s[0] == '@')
+    StringRef S(*LineIt);
+    if (S[0] == '@')
       continue;
     // Check for the leading "!"
-    if (!s.consume_front("!") || s.empty())
+    if (!S.consume_front("!") || S.empty())
       break;
-    // Check for second "!" which encodes basic block ids.
-    if (s.consume_front("!")) {
-      if (fi != bbMap.end())
-        fi->second.insert(std::stoi(s.str()));
-      else
-        return false;
-    } else {
-      // Start a new function.
-      auto R = bbMap.try_emplace(s.split('/').first);
-      fi = R.first;
-      assert(R.second);
+    // Check for second "!" which indicates a cluster of basic blocks.
+    if (S.consume_front("!")) {
+      if (FI == ProgramBBClusterInfo.end())
+        return invalidProfileError(
+            "Cluster list does not follow a function name specifier.");
+      SmallVector<StringRef, 4> BBIndexes;
+      S.split(BBIndexes, ' ');
+      // Reset current cluster position.
+      CurrentPosition = 0;
+      for (auto BBIndexStr : BBIndexes) {
+        unsigned long long BBIndex;
+        if (getAsUnsignedInteger(BBIndexStr, 10, BBIndex))
+          return invalidProfileError(Twine("Unsigned integer expected: '") +
+                                     BBIndexStr + "'.");
+        if (!FuncBBIDs.insert(BBIndex).second)
+          return invalidProfileError(Twine("Duplicate basic block id found '") +
+                                     BBIndexStr + "'.");
+        if (!BBIndex && CurrentPosition)
+          return invalidProfileError("Entry BB (0) does not begin a cluster.");
+
+        FI->second.emplace_back(BBClusterInfo{
+            ((unsigned)BBIndex), CurrentCluster, CurrentPosition++});
+      }
+      CurrentCluster++;
+    } else { // This is a function name specifier.
+      // Function aliases are separated using '/'. We use the first function
+      // name for the cluster info mapping and delegate all other aliases to
+      // this one.
+      SmallVector<StringRef, 4> Aliases;
+      S.split(Aliases, '/');
+      for (size_t i = 1; i < Aliases.size(); ++i)
+        FuncAliasMap.try_emplace(Aliases[i], Aliases.front());
+
+      // Prepare for parsing clusters of this function name.
+      // Start a new cluster map for this function name.
+      FI = ProgramBBClusterInfo.try_emplace(Aliases.front()).first;
+      CurrentCluster = 0;
+      FuncBBIDs.clear();
     }
   }
-  return true;
+  return Error::success();
 }
 
 bool BBSectionsPrepare::doInitialization(Module &M) {
-  if (MBuf)
-    getBBSectionsList(MBuf, BBSectionsList);
-  return true;
+  if (!MBuf)
+    return false;
+  if (auto Err = getBBClusterInfo(MBuf, ProgramBBClusterInfo, FuncAliasMap))
+    report_fatal_error(std::move(Err));
+  return false;
 }
 
 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/Support/SMLoc.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/YAMLTraits.h"
 #include "llvm/Target/TargetMachine.h"
 #include <memory>
 
 using namespace llvm;
 
+/// This method iterates over the basic blocks and assigns their IsBeginSection
+/// and IsEndSection fields. This must be called after MBB layout is finalized
+/// and the SectionID's are assigned to MBBs.
+static void assignBeginEndSections(MachineFunction &MF) {
+  MF.front().setIsBeginSection();
+  auto CurrentSectionID = MF.front().getSectionID();
+  for (auto MBBI = std::next(MF.begin()), E = MF.end(); MBBI != E; ++MBBI) {
+    if (MBBI->getSectionID() == CurrentSectionID)
+      continue;
+    MBBI->setIsBeginSection();
+    std::prev(MBBI)->setIsEndSection();
+    CurrentSectionID = MBBI->getSectionID();
+  }
+  MF.back().setIsEndSection();
+}
+
 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;
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();
     MF.createBBLabels();
+    assignBeginEndSections(MF);
   }
   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

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";
-      break;
-    case MBBS_Exception:
+    switch (MBB.getSectionID().getValue()) {
+    case MachineBasicBlock::ExceptionSectionID:
       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)
-    return false;
-
-  return true;
-}
-
+// Returns the basic block ending the section containing this basic block.
+// Returns null if basic block sections is not enabled for this function.
+// This function has a linear time complexity.
 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()));
-}
-
-// Returns true if this block begins any section.
-bool MachineBasicBlock::isEndSection() const {
-  return (SectionType == MBBS_Entry || SectionType == MBBS_Unique ||
-          getParent()->isSectionEndMBB(getNumber()));
+  if (!MF->hasBBSections())
+    return nullptr;
+  // Iterate over basic blocks looking for a basic block with a different
+  // section ID.
+  auto I = getIterator();
+  while (I != MF->end() && I->getSectionID() == getSectionID())
+    ++I;
+  return I == MF->end() ? &MF->back() : &*std::prev(I);
 }
 
 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 *TBB = nullptr, *FBB = nullptr;
   SmallVector<MachineOperand, 4> Cond;
   DebugLoc DL = findBranchDebugLoc();
   bool B = TII->analyzeBranch(*this, TBB, FBB, Cond);
   (void) B;
   assert(!B && "UpdateTerminators requires analyzable predecessors!");
   if (Cond.empty()) {
     if (TBB) {
       // The block has an unconditional branch. If its successor is now its
       // layout successor, delete the branch.
       if (isLayoutSuccessor(TBB))
         TII->removeBranch(*this);
     } else {
       // The block has an unconditional fallthrough. If its successor is not its

 }
 
 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-clusters-branches.ll

+; BB cluster sections test for optimizing basic block branches.
+;
+; Test1: Basic blocks #0 (entry) and #2 will be placed in the same section.
+; There should be a jne from #0 to #1 and a fallthrough to #2.
+; BB #1 will be in a unique section. Therefore, it should retain its jmp to #3.
+; #2 must also have an explicit jump to #3.
+; RUN: echo '!foo' > %t1
+; RUN: echo '!!0 2' >> %t1
+; RUN: echo '!!1' >> %t1
+; RUN: llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basicblock-sections=%t1 | FileCheck %s -check-prefix=LINUX-SECTIONS1
+;
+; Test2: Basic blocks #1 and #3 will be placed in the same section.
+; The rest (#0 and #2) go into the function's section.
+; This means #1 must fall through to #3, and #0 must fall through to #2.
+; #2 must have an explicit jump to #3.
+; RUN: echo '!foo' > %t2
+; RUN: echo '!!1 3' >> %t2
+; RUN: llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basicblock-sections=%t2 | FileCheck %s -check-prefix=LINUX-SECTIONS2
+
+define void @foo(i1 zeroext) {
+  %2 = alloca i8, align 1
+  %3 = zext i1 %0 to i8
+  store i8 %3, i8* %2, align 1
+  %4 = load i8, i8* %2, align 1
+  %5 = trunc i8 %4 to i1
+  br i1 %5, label %6, label %8
+
+6:                                                ; preds = %1
+  %7 = call i32 @bar()
+  br label %10
+
+8:                                                ; preds = %1
+  %9 = call i32 @baz()
+  br label %10
+
+10:                                               ; preds = %8, %6
+  ret void
+}
+
+declare i32 @bar() #1
+
+declare i32 @baz() #1
+
+; LINUX-SECTIONS1:      .section  .text.foo,"ax",@progbits
+; LINUX-SECTIONS1-LABEL:  foo:
+; LINUX-SECTIONS1:    jne a.BB.foo
+; LINUX-SECTIONS1-NOT:    {{jne|je|jmp}}
+; LINUX-SECTIONS1-LABEL:  aa.BB.foo:
+; LINUX-SECTIONS1:    jmp raa.BB.foo
+; LINUX-SECTIONS1:    .section        .text.foo,"ax",@progbits,unique,1
+; LINUX-SECTIONS1-LABEL:  a.BB.foo:
+; LINUX-SECTIONS1:    jmp raa.BB.foo
+; LINUX-SECTIONS1:    .section        .text.foo.unlikely,"ax",@progbits
+; LINUX-SECTIONS1-LABEL:  raa.BB.foo:
+
+; LINUX-SECTIONS2:    .section        .text.foo,"ax",@progbits
+; LINUX-SECTIONS2-LABEL:  foo:
+; LINUX-SECTIONS2:    jne a.BB.foo
+; LINUX-SECTIONS2-NOT:    {{jne|je|jmp}}
+; LINUX-SECTIONS2-LABEL:  aa.BB.foo:
+; LINUX-SECTIONS2:    jmp raa.BB.foo
+; LINUX-SECTIONS2:    .section        .text.foo,"ax",@progbits,unique,1
+; LINUX-SECTIONS2-NEXT:   a.BB.foo:
+; LINUX-SECTIONS2-NOT:    {{jne|je|jmp}}
+; LINUX-SECTIONS2-LABEL:  raa.BB.foo:

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

+; BB cluster section test for exception handling.
+;
+; Test1: Basic blocks #1 and #3 are landing pads and must be in the same section.
+; Basic block 2 will be placed in a unique section, but #1 and #3 are placed in the special exception section.
+; The rest will be placed in a section along with the entry basic block.
+; RUN: echo '!main' > %t1
+; RUN: echo '!!1 2' >> %t1
+; RUN: llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basicblock-sections=%t1 | FileCheck %s -check-prefix=LINUX-SECTIONS1
+;
+; Test2: Basic blocks #1, #2, and #3 go into a separate section.
+; No separate exception section will be created as #1 and #3 are already in one section.
+; The rest will be placed in a section along with the entry basic block.
+; RUN: echo '!main' > %t2
+; RUN: echo '!!1 2 3' >> %t2
+; RUN: llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basicblock-sections=%t2 | FileCheck %s -check-prefix=LINUX-SECTIONS2
+;
+
+@_ZTIi = external constant i8*
+
+define i32 @main() uwtable optsize ssp personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  invoke void @_Z1fv() optsize
+          to label %try.cont unwind label %lpad1
+
+lpad1:
+  %0 = landingpad { i8*, i32 }
+          cleanup
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  br label %eh.resume1
+
+try.cont:
+  invoke void @_Z2fv() optsize
+          to label %try.cont unwind label %lpad2
+  ret i32 0
+
+lpad2:
+  %2 = landingpad { i8*, i32 }
+          cleanup
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  br label %eh.resume2
+
+eh.resume1:
+  resume { i8*, i32 } %0
+
+eh.resume2:
+  resume { i8*, i32 } %2
+}
+
+declare void @_Z1fv() optsize
+
+declare void @_Z2fv() optsize
+
+declare i32 @__gxx_personality_v0(...)
+
+; LINUX-SECTIONS1:    .section  .text.main,"ax",@progbits
+; LINUX-SECTIONS1-LABEL:  main:
+; LINUX-SECTIONS1-NOT:    .section
+; LINUX-SECTIONS1-LABEL:  alal.BB.main:
+; LINUX-SECTIONS1-NOT:    .section
+; LINUX-SECTIONS1-LABEL:  aalal.BB.main:
+; LINUX-SECTIONS1-NOT:    .section
+; LINUX-SECTIONS1-LABEL:  aaalal.BB.main:
+; LINUX-SECTIONS1:    .section  .text.main,"ax",@progbits,unique,1
+; LINUX-SECTIONS1-LABEL:  al.BB.main:
+; LINUX-SECTIONS1:    .section  .text.main.eh,"ax",@progbits
+; LINUX-SECTIONS1-LABEL:  l.BB.main:
+; LINUX-SECTIONS1-NOT:    .section
+; LINUX-SECTIONS1-LABEL:  lal.BB.main:
+; LINUX-SECTIONS1-NOT:    .section
+; LINUX-SECTIONS1:    .section  .text.main,"ax",@progbits
+; LINUX-SECTIONS1-LABEL:  .Lfunc_end0
+
+
+; LINUX-SECTIONS2:    .section  .text.main,"ax",@progbits
+; LINUX-SECTIONS2-LABEL:  main:
+; LINUX-SECTIONS2-NOT:    .section
+; LINUX-SECTIONS2-LABEL:  alal.BB.main:
+; LINUX-SECTIONS2-NOT:    .section
+; LINUX-SECTIONS2-LABEL:  aalal.BB.main:
+; LINUX-SECTIONS2-NOT:    .section
+; LINUX-SECTIONS2-LABEL:  aaalal.BB.main:
+; LINUX-SECTIONS2:    .section  .text.main,"ax",@progbits,unique,1
+; LINUX-SECTIONS2-LABEL:  l.BB.main:
+; LINUX-SECTIONS2-NOT:    .section
+; LINUX-SECTIONS2-LABEL:  al.BB.main:
+; LINUX-SECTIONS2-NOT:    .section
+; LINUX-SECTIONS2-LABEL:  lal.BB.main:
+; LINUX-SECTIONS2:    .section  .text.main,"ax",@progbits
+; LINUX-SECTIONS2-LABEL:  .Lfunc_end0

llvm/test/CodeGen/X86/basicblock-sections-clusters-error.ll

+; BB cluster sections error handling
+; RUN: echo '!f' > %t1
+; RUN: echo '!!1 4' >> %t1
+; RUN: echo '!!1' >> %t1
+; RUN: not --crash llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basicblock-sections=%t1 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR1
+; CHECK-ERROR1: LLVM ERROR: Invalid profile {{.*}} at line 3: Duplicate basic block id found '1'.
+; RUN: echo '!f' > %t2
+; RUN: echo '!!4 0' >> %t2
+; RUN: not --crash llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basicblock-sections=%t2 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR2
+; CHECK-ERROR2: LLVM ERROR: Invalid profile {{.*}} at line 2: Entry BB (0) does not begin a cluster.
+; RUN: echo '!f' > %t3
+; RUN: echo '!!-1' >> %t3
+; RUN: not --crash llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basicblock-sections=%t3 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR3
+; CHECK-ERROR3: LLVM ERROR: Invalid profile {{.*}} at line 2: Unsigned integer expected: '-1'.
+; RUN: echo '!!1' > %t4
+; RUN: echo '!f' >> %t4
+; RUN: not --crash llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basicblock-sections=%t4 2>&1 | FileCheck %s --check-prefix=CHECK-ERROR4
+; CHECK-ERROR4: LLVM ERROR: Invalid profile {{.*}} at line 1: Cluster list does not follow a function name specifier.
+
+define i32 @dummy(i32 %x, i32 %y, i32 %z) {
+  entry:
+    %tmp = mul i32 %x, %y
+    %tmp2 = add i32 %tmp, %z
+    ret i32 %tmp2
+}

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

+; BB cluster section tests.
+;
+; Test1: Basic blocks #0 (entry) and #2 will be placed in the same section.
+; Basic block 1 will be placed in a unique section.
+; The rest will be placed in the cold section.
+; RUN: echo '!foo' > %t1
+; RUN: echo '!!0 2' >> %t1
+; RUN: echo '!!1' >> %t1
+; RUN: llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basicblock-sections=%t1 | FileCheck %s -check-prefix=LINUX-SECTIONS1
+;
+; Test2: Basic blocks #1 and #3 will be placed in the same section.
+; All other BBs (including the entry block) go into the function's section.
+; RUN: echo '!foo' > %t2
+; RUN: echo '!!1 3' >> %t2
+; RUN: llc < %s -O0 -mtriple=x86_64-pc-linux -function-sections -basicblock-sections=%t2 | FileCheck %s -check-prefix=LINUX-SECTIONS2
+
+define void @foo(i1 zeroext) {
+  %2 = alloca i8, align 1
+  %3 = zext i1 %0 to i8
+  store i8 %3, i8* %2, align 1
+  %4 = load i8, i8* %2, align 1
+  %5 = trunc i8 %4 to i1
+  br i1 %5, label %6, label %8
+
+6:                                                ; preds = %1
+  %7 = call i32 @bar()
+  br label %10
+
+8:                                                ; preds = %1
+  %9 = call i32 @baz()
+  br label %10
+
+10:                                               ; preds = %8, %6
+  ret void
+}
+
+declare i32 @bar() #1
+
+declare i32 @baz() #1
+
+; LINUX-SECTIONS1:      .section  .text.foo,"ax",@progbits
+; LINUX-SECTIONS1-NOT:    .section
+; LINUX-SECTIONS1-LABEL:  foo:
+; LINUX-SECTIONS1-NOT:    .section
+; LINUX-SECTIONS1-LABEL:  aa.BB.foo:
+; LINUX-SECTIONS1-NOT:    .section
+; LINUX-SECTIONS1:    .section        .text.foo,"ax",@progbits,unique,1
+; LINUX-SECTIONS1-LABEL:  a.BB.foo:
+; LINUX-SECTIONS1-LABEL:  .Ltmp0:
+; LINUX-SECTIONS1-NEXT:   .size a.BB.foo, .Ltmp0-a.BB.foo
+; LINUX-SECTIONS1-NOT:    .section
+; LINUX-SECTIONS1:    .section        .text.foo.unlikely,"ax",@progbits
+; LINUX-SECTIONS1-LABEL:  raa.BB.foo:
+; LINUX-SECTIONS1:      .section  .text.foo,"ax",@progbits
+; LINUX-SECTIONS1-LABEL:  .Lfunc_end0:
+; LINUX-SECTIONS1-NEXT:   .size foo, .Lfunc_end0-foo
+
+; LINUX-SECTIONS2:    .section        .text.foo,"ax",@progbits
+; LINUX-SECTIONS2-NOT:    .section
+; LINUX-SECTIONS2-LABEL:  foo:
+; LINUX-SECTIONS2-NOT:    .section
+; LINUX-SECTIONS2-LABEL:  aa.BB.foo:
+; LINUX-SECTIONS2:    .section        .text.foo,"ax",@progbits,unique,1
+; LINUX-SECTIONS2-NEXT:   a.BB.foo:
+; LINUX-SECTIONS2-NOT:    .section
+; LINUX-SECTIONS2-LABEL:  raa.BB.foo:
+; LINUX-SECTIONS2-LABEL:  .Ltmp0:
+; LINUX-SECTIONS2-NEXT:   .size a.BB.foo, .Ltmp0-a.BB.foo
+; LINUX-SECTIONS2:    .section        .text.foo,"ax",@progbits
+; LINUX-SECTIONS2-LABEL:  .Lfunc_end0:
+; LINUX-SECTIONS2-NEXT:   .size foo, .Lfunc_end0-foo
+

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: .Ltmp0:
+; LINUX-SECTIONS-NEXT: .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)

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

 
 declare i32 @_Z3foov() #1
 
 
 ; LINUX-SECTIONS: .section        .text._Z3bazb,"ax",@progbits
 ; LINUX-SECTIONS: _Z3bazb:
 ; LINUX-SECTIONS: .section        .text._Z3bazb.r.BB._Z3bazb,"ax",@progbits,unique,1
 ; LINUX-SECTIONS: r.BB._Z3bazb:
-; LINUX-SECTIONS: .size   r.BB._Z3bazb, .Ltmp0-r.BB._Z3bazb
+; LINUX-SECTIONS: .Ltmp0:
+; LINUX-SECTIONS-NEXT: .size   r.BB._Z3bazb, .Ltmp0-r.BB._Z3bazb
 ; LINUX-SECTIONS: .section        .text._Z3bazb.rr.BB._Z3bazb,"ax",@progbits,unique,2
 ; LINUX-SECTIONS: rr.BB._Z3bazb:
-; LINUX-SECTIONS: .size   rr.BB._Z3bazb, .Ltmp1-rr.BB._Z3bazb
+; LINUX-SECTIONS: .Ltmp1:
+; LINUX-SECTIONS-NEXT: .size   rr.BB._Z3bazb, .Ltmp1-rr.BB._Z3bazb