Let -basic-block-sections=labels emit basicblock metadata in a new .bb_addr_map section, instead of emitting special unary-encoded symbols.

[rahmanl]

Summary

This patch introduces the new .bb_addr_map section feature which allows us to emit the bits needed for mapping binary profiles to basic blocks into a separate section.
The format of the emitted data is represented as follows. It includes a header for every function:

Address of the function	-> 8 bytes (pointer size)
Number of basic blocks in this function (>0)	-> ULEB128

The header is followed by a BB record for every basic block. These records are ordered in the same order as MachineBasicBlocks are placed in the function. Each BB Info is structured as follows:

Offset of the basic block relative to function begin	-> ULEB128
Binary size of the basic block	-> ULEB128
BB metadata	-> ULEB128 [ MBB.isReturn() OR MBB.hasTailCall() << 1 OR MBB.isEHPad() << 2 ]

The new feature will replace the existing "BB labels" functionality with -basic-block-sections=labels.
The .bb_addr_map section scrubs the specially-encoded BB symbols from the binary and makes it friendly to profilers and debuggers.
Furthermore, the new feature reduces the binary size overhead from 70% bloat to only 12%.

For more information and results please refer to the RFC: https://lists.llvm.org/pipermail/llvm-dev/2020-July/143512.html

[rahmanl]

Modify clang test.

[rahmanl]

Add clang test.

[rahmanl]

Modify the clang test.

[snehasish]

llvm/include/llvm/CodeGen/MachineBasicBlock.h

481

Document the metadata format? AFAICT the only to find out now is reading the code which generates the metadata as unsigned.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1027

I have a slight preference to move this check to the callsite so that the reader does not have to follow it only to realize that their function of interest does not emit a bb info section. Though I see the convention in the code is to call it and then return early. Maybe documenting at the callsite is enough?

1317

Add a comment here.

llvm/lib/CodeGen/MachineBasicBlock.cpp

61

If this block is empty should we even be calling this function?

llvm/lib/MC/MCObjectFileInfo.cpp

956

Is this just returning the BBInfoSection pointer which is null? If so then prefer returning nullptr here to make it clear to the reader.

967

Can we call the section something other than bb_info? For example when examining the contents of a binary a name like "stack_sizes" provides some obvious meaning without further investigation. Similarly, can we call this something like "bb_addr_offset_map"?

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

2

Can we make the triples that we use consistent across the various tests?

6

Lets align the contents of the check to make it easier to inspect.

16

Consider moving the CHECK lines into the functions themselves to make it clear which CHECKS correspond to which functions.

[rahmanl]

Address Snehasish's comments.

[rahmanl]

• Address Snehasish's comments. clang-format.

[rahmanl]

• Address Snehasish's comments.

llvm/lib/CodeGen/MachineBasicBlock.cpp

61

Yes. An empty basic block is possible:

https://llvm.org/doxygen/AsmPrinter_8cpp_source.html#l03140

[rahmanl]

Thanks for the great feedback @snehasishk.

llvm/lib/MC/MCObjectFileInfo.cpp

967

Great suggestion. I renamed the section to bb_addr_map and also changed the function names accordingly.

[tmsriram]

• The summary of this patch must be enhanced a little bit more to capture the highlights.
• Even though you point to the RFC, I think just add a little more.
• I would add that this patch basically un-pollutes the symtab, that is the greatest contribution to me which helps profilers, debuggers plug and play

Independently, what did we decide about the option? Are we keeping the option?

You should also include changes to the clang user manual to reflect this, documentation around -fbasic-block-section=labels can go in the same patch

clang/test/CodeGen/basic-block-sections.c

31–33 ↗

(On Diff #285926)

We need a test where we disasm the native object file and show how the contents look like. This is good for readability of these sections.

llvm/include/llvm/CodeGen/MachineBasicBlock.h

481

+1 Let's document this heavily where possible:

• Under what options is this section emitted?
• What is captured here?
• Maybe a quick note on why this is used, just one sentence should be fine.

486

Typo.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1027

Ya, I like moving the check to the call site. You can assert here instead and be done.

1049

Can you add a comment here that basic block size cannot always be derived from label offsets due to alignment? Isnt that the only reason, otherwise size is redundant right?

1224

I am surprised we are not already doing this :). This is needed for your patch right? Otherwise, this needs to go as a separate patch.

llvm/lib/CodeGen/MachineBasicBlock.cpp

73

I am happy this code is blown away! :)

llvm/lib/CodeGen/MachineFunction.cpp

343–344

Ditto! Happy to see this gone!

llvm/lib/MC/MCObjectFileInfo.cpp

955

Run clang-format on the patches.

[rahmanl]

Address Sri's comments.

[rahmanl]

Address Sri's comments.

[rahmanl]

clang/test/CodeGen/basic-block-sections.c

31–33 ↗

(On Diff #285926)

The test you're envisioning won't look great.
If we want to dis-assemble the object file, we end up just having binary contents for every .bb_addr_map section.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1224

What's happening here is that the lambda function emitELFSizeDirective is removed since we no longer have two use-cases (only sections).

llvm/lib/MC/MCObjectFileInfo.cpp

955

Apparently, this is the formatting chosen by clang-format.

[rahmanl]

Fix failing clang test which used to check for the old ".bb_info" name.

[rahmanl]

Fix failing clang test which used to check for the old ".bb_info" name.

[snehasish]

clang/docs/UsersManual.rst

1706 ↗

(On Diff #288105)

nit: s/would include/includes/

1707 ↗

(On Diff #288105)

nit: s/relative to the/relative to the parent/

llvm/lib/CodeGen/MachineBasicBlock.cpp

58

I think this method only relies on already public methods of MachineBasicBlock. It would be cleaner to move this from here to a static helper function in AsmPrinter.cpp. This way we don't add yet another method to the MachineBasicBlock class and keeps the relevant metadata generation logic close to where it is used.

Feel free to ignore if you plan on calling this method elsewhere apart from AsmPrinter.cpp but I can't think of a reason to do so.

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

5–9

I think this can be removed and the branch on L10 can directly use the param like so:

define void @_Z3bazb(i1 zeroext %0) personality i32 (...)* @__gxx_personality_v0 {
  br i1 %0, label %6, label %11
  ....
}

You will need to adjust the respective virtual register names since %2-%5 is no longer used.

[rahmanl]

Address Snehasish's comments.

• Move getBBAddrMetadata to AsmPrinter as a static function in AsmPrinter
• Remove unnecessary IR instructions in basic-block-sections-labels.ll

[rahmanl]

llvm/lib/CodeGen/MachineBasicBlock.cpp

58

Thanks for the suggestion. It makes the code much more readable since I just place that function above emitBBAddrMapSection.
I can even make it a lambda function within emitBBAddrMapSection. WDYT?

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

5–9

Great suggestion. Thanks. This was copied over from other basic-block-sections tests, so maybe they can be updated too.

[snehasish]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1030

Did you intend to change the formatting of the comment? I think the list items were on separate lines.

llvm/lib/CodeGen/MachineBasicBlock.cpp

58

I have a slight preference for the static method vs inline lambda since the comment describing the metadata can be placed above the static method.

[rahmanl]

• Move getBBAddrMetadata to AsmPrinter as a static function + nits.

[rahmanl]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1030

My bad. Didn't fully check the lint result.

llvm/lib/CodeGen/MachineBasicBlock.cpp

58

Makes sense.

[snehasish]

LGTM. Please wait a bit for additional comments from others.

[MaskRay]

clang/docs/UsersManual.rst

1703 ↗

(On Diff #288694)

Use backquotes like below

clang/test/CodeGen/basic-block-sections.c

3 ↗

(On Diff #288694)

The triple change is unneeded. You can also just use -triple x86_64 because the behavior applies to generic ELF.

[MaskRay]

llvm/lib/CodeGen/MachineBasicBlock.cpp

84

Expand auto

https://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable

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

34

Can you use a more specific pattern than .+? It is difficult to know which pattern it uses (a larger issue is that it matches spaces and possibly leverages a subtle property of FileCheck)

[rahmanl]

• Address @MaskRay's comments.
• Rebase with upstream.

[rahmanl]

Thanks a lot for the comments @MaskRay.

[MaskRay]

clang/test/CodeGen/basic-block-sections.c

31 ↗

(On Diff #289498)

Assembly tests are not common in clang/test but @rsmith LGTMed D68049 so I think it should be fine. Now this file tests more machine level stuff. Should the file switch to LLVM IR?

[MaskRay]

I am still reading the patch, but I have noticed one thing worth discussing. .bb_addr_map is a non-SHF_ALLOC section (meaning that it is not part of the memory image). An absolute relocation type (.quad .Lfunc_begin0) works but the value is a link-time address, not taking account of the load base (PIE/shared object)). (If .bb_addr_map has the SHF_ALLOC flag, linkers will report a text relocation) How do you intend to use .bb_addr_map at runtime?

[tmsriram]

In D85408#2253055, @MaskRay wrote:

I am still reading the patch, but I have noticed one thing worth discussing. .bb_addr_map is a non-SHF_ALLOC section (meaning that it is not part of the memory image). An absolute relocation type (.quad .Lfunc_begin0) works but the value is a link-time address, not taking account of the load base (PIE/shared object)). (If .bb_addr_map has the SHF_ALLOC flag, linkers will report a text relocation) How do you intend to use .bb_addr_map at runtime?

bb_addr_map is intentionally not loaded as it is never meant to be used at run-time. bb_addr_map will be later be used in conjunction with a hardware profile of the binary to associate executed basic block addresses to machine basic blocks. The hardware profile of the binary has enough info to determine the load base address with PIE, this is pretty straight forward and multiple strategies exist. What exactly is the concern here?

[shenhan]

In D85408#2253055, @MaskRay wrote:

I am still reading the patch, but I have noticed one thing worth discussing. .bb_addr_map is a non-SHF_ALLOC section (meaning that it is not part of the memory image). An absolute relocation type (.quad .Lfunc_begin0) works but the value is a link-time address, not taking account of the load base (PIE/shared object)). (If .bb_addr_map has the SHF_ALLOC flag, linkers will report a text relocation) How do you intend to use .bb_addr_map at runtime?

Regarding "not taking account of the load base (PIE/shared object)" - the profile conversion tool uses addresses in .bb_addr_map section and MMAP entries in perf.data file to construct runtime addresses, so these runtime addresses can be matched with the profile addresses recorded in perf.data file.

[MaskRay]

In D85408#2253073, @tmsriram wrote:

In D85408#2253055, @MaskRay wrote:

I am still reading the patch, but I have noticed one thing worth discussing. .bb_addr_map is a non-SHF_ALLOC section (meaning that it is not part of the memory image). An absolute relocation type (.quad .Lfunc_begin0) works but the value is a link-time address, not taking account of the load base (PIE/shared object)). (If .bb_addr_map has the SHF_ALLOC flag, linkers will report a text relocation) How do you intend to use .bb_addr_map at runtime?

bb_addr_map is intentionally not loaded as it is never meant to be used at run-time. bb_addr_map will be later be used in conjunction with a hardware profile of the binary to associate executed basic block addresses to machine basic blocks. The hardware profile of the binary has enough info to determine the load base address with PIE, this is pretty straight forward and multiple strategies exist. What exactly is the concern here?

Thanks for the explanation! I guessed that non-SHF_ALLOC is intended but hoped that it can be confirmed (and you did!). This sections works similar to .stack_sizes emitted by clang -fstack-size-section.

This is important because for SHF_ALLOC, SHF_WRITE is also needed to avoid text relocations. I am still reading the patch to ensure that it will work as intended.

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

22

Consider align the content. Since CHECK-LABEL: is the longest.

; CHECK:        .section .text._Z3foov,"ax",@progbits
; CHECK-LABEL:	_Z3foov:
; CHECK-NEXT:     [[FOO_BEGIN:.Lfunc_begin[0-9]+]]:

Non-labels have additional indentation to make it clear they are bodies covered by labels.

[MaskRay]

Thanks, I have followed the flow. The logic looks good. But I have got some nits and a question about the clang/test/ assembly test.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1033

1st 2nd 3rd may be confusing. You can just write: 1<<0, 1<<1, and 1<<2. Actually, you may just say: use 3 bits to encode information for more precise profile, (1) (2) (3).

The first two sentences can thus be simplified.

1047

BBAddrMapSection is always non-null. Delete the if.

1058

auto -> MachineBasicBlock

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

2

LINUX-LABELS is probably not a good CHECK prefix. The feature is generic and not specific to linux (i.e. you could use -mtriple=x86_64)

[rahmanl]

• Address +MaskRay's comments:
• Change the check prefix simply to "CHECK" for basic-block-sections-labels.ll
• Change the triple to x86_64 for this test.
• nits.
• Remove the "-LABEL" feature from basic-block-sections-labels.ll and use precise BB indices.
• Remove the assertion in emitBBAddrMapSection.

[rahmanl]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1047

I believe we return null for non-ELF environment (Please refer to MCObjectFileInfo::getBBAddrMapSection).

[MaskRay]

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1047

In that case emitBBAddrMapSection will not be called?

[rahmanl]

• Merge remote-tracking branch 'origin/master' into arcpatch-D85408

[rahmanl]

Thanks for the review @MaskRay. Is this ready to land now?

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1047

Fair enough.

[MaskRay]

I like the simplification:) However, I still feel puzzled by the large chunk of assembly test in clang/test/CodeGen/basic-block-sections.c. I hope another reviewer or the code owner can say that this is ok.

[rahmanl]

@efriedma Would you please chime in specially with respect to @MaskRay 's comment about the clang test involving assembly?

[dblaikie]

In D85408#2262134, @rahmanl wrote:

@efriedma Would you please chime in specially with respect to @MaskRay 's comment about the clang test involving assembly?

I'll chime in, perhaps @efriedma will/can too: This patch has no changes to Clang's code, so it should have no changes to Clang's tests, generally speaking.

Whatever codepath/behavior is being tested by that Clang test change should be testable (& generally only tested) via LLVM's tools/tests, like llc, I would expect? (I guess that's what the basic-block-sections-labels.ll test is doing? Making the Clang test update redundant)

The only reason I'd expect to see the assembly tested in Clang is if the flag that enables this feature is an MCOptions (or other similar API level feature) member, rather than part of LLVM IR proper. In that case the only way to test that the flag has any effect (since we can't observe the MCOptions struct state directly in a test) is to test for the MCOptions effect on LLVM's output. Depending on the complexity, sometimes such tests are just skipped entirely (leaving the setting of the MCOption untested) - I think I did that for, for example, DWARF type units. Other times, an end-to-end test is used to ensure the flag is working. But that's all the test should do: test the flag is working, with some very basic/rudimentary property of the feature being enabled (so pretty much /any/ change to the way the feature works will still pass the test, but if the feature were turned off entirely (the MCOptions flag stopped being set correctly), the test would fail). Not test all the functionality of the feature that the flag enables - all that testing should be down in LLVM.

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

1058

FWIW, auto seems pretty fine to me here - looking only at for loops over MBB, a rough grep/count seems like there's certainly a lot of both (194 (non-auto) to 168 (auto)) and I think it qualifies as "obvious" for LLVM backend code that an MBB variable would be of the type MachineBasicBlock. (bonus points for obviousness that MF is a MachineFunction)

[rahmanl]

• Remove the complex assembly from the clang test.

[rahmanl]

In D85408#2266559, @dblaikie wrote:

In D85408#2262134, @rahmanl wrote:

@efriedma Would you please chime in specially with respect to @MaskRay 's comment about the clang test involving assembly?

I'll chime in, perhaps @efriedma will/can too: This patch has no changes to Clang's code, so it should have no changes to Clang's tests, generally speaking.

Whatever codepath/behavior is being tested by that Clang test change should be testable (& generally only tested) via LLVM's tools/tests, like llc, I would expect? (I guess that's what the basic-block-sections-labels.ll test is doing? Making the Clang test update redundant)

The only reason I'd expect to see the assembly tested in Clang is if the flag that enables this feature is an MCOptions (or other similar API level feature) member, rather than part of LLVM IR proper. In that case the only way to test that the flag has any effect (since we can't observe the MCOptions struct state directly in a test) is to test for the MCOptions effect on LLVM's output. Depending on the complexity, sometimes such tests are just skipped entirely (leaving the setting of the MCOption untested) - I think I did that for, for example, DWARF type units. Other times, an end-to-end test is used to ensure the flag is working. But that's all the test should do: test the flag is working, with some very basic/rudimentary property of the feature being enabled (so pretty much /any/ change to the way the feature works will still pass the test, but if the feature were turned off entirely (the MCOptions flag stopped being set correctly), the test would fail). Not test all the functionality of the feature that the flag enables - all that testing should be down in LLVM.

Thanks for the clear explanation @dblaikie. In light of your comment, I removed the complex assembly from the clang test, since the LLVM tests are already testing those.

[MaskRay]

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

2

You can drop -unknown-linux-gnu. This is a generic ELF feature.

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

2

Delete -check-prefix=CHECK
It is the default

[rahmanl]

• Remove the "labels" part of the clang test as the functionality is tested on LLVM tests.

[rahmanl]

• Merge branch 'master' into arcpatch-D85408

[rahmanl]

• Rebase

llvm/include/llvm/CodeGen/AsmPrinter.h

public:
   void emitFunctionBody();
 
   void emitCFIInstruction(const MachineInstr &MI);
 
   void emitFrameAlloc(const MachineInstr &MI);
 
   void emitStackSizeSection(const MachineFunction &MF);
 
+  void emitBBInfoSection(const MachineFunction &MF);
+
   void emitRemarksSection(remarks::RemarkStreamer &RS);
 
   enum CFIMoveType { CFI_M_None, CFI_M_EH, CFI_M_Debug };
   CFIMoveType needsCFIMoves() const;
 
   /// Returns false if needsCFIMoves() == CFI_M_EH for any function
   /// in the module.
   bool needsOnlyDebugCFIMoves() const { return isCFIMoveForDebugging; }

llvm/include/llvm/CodeGen/MachineBasicBlock.h

#endif
   }
 
   /// Sets the section ID for this basic block.
   void setSectionID(MBBSectionID V) { SectionID = V; }
 
   /// Returns the MCSymbol marking the end of this basic block.
   MCSymbol *getEndSymbol() const;
 
+  /// Returns the BB info metadata to be emitted in the bb_info section.
+  unsigned getBBInfoMetadata() const;
+
   /// Returns true if this block may have an INLINEASM_BR (overestimate, by
   /// checking if any of the successors are indirect targets of any inlineasm_br
   /// in the function).
   bool mayHaveInlineAsmBr() const;
 
   /// Returns true if this is the indirect dest of an INLINEASM_BR.
   bool isInlineAsmBrIndirectTarget() const {
     return IsInlineAsmBrIndirectTarget;
   }
 
   /// Indicates if this is the indirect dest of an INLINEASM_BR.

llvm/include/llvm/CodeGen/MachineFunction.h

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; }
 
-  /// Creates basic block Labels for this function.
-  void createBBLabels();
-
   /// Assign IsBeginSection IsEndSection fields for basic blocks in this
   /// function.
   void assignBeginEndSections();
 
   /// 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

llvm/include/llvm/MC/MCObjectFileInfo.h

protected:
   /// EH frame section.
   ///
   /// It is initialized on demand so it can be overwritten (with uniquing).
   MCSection *EHFrameSection = nullptr;
 
   /// Section containing metadata on function stack sizes.
   MCSection *StackSizesSection = nullptr;
 
+  MCSection *BBInfoSection = nullptr;
+
   // ELF specific sections.
   MCSection *DataRelROSection = nullptr;
   MCSection *MergeableConst4Section = nullptr;
   MCSection *MergeableConst8Section = nullptr;
   MCSection *MergeableConst16Section = nullptr;
   MCSection *MergeableConst32Section = nullptr;
 
   // MachO specific sections.
public:
   MCSection *getTLSBSSSection() const { return TLSBSSSection; }
 
   MCSection *getStackMapSection() const { return StackMapSection; }
   MCSection *getFaultMapSection() const { return FaultMapSection; }
   MCSection *getRemarksSection() const { return RemarksSection; }
 
   MCSection *getStackSizesSection(const MCSection &TextSec) const;
 
+  MCSection *getBBInfoSection(const MCSection &TextSec) const;
+
   // ELF specific sections.
   MCSection *getDataRelROSection() const { return DataRelROSection; }
   const MCSection *getMergeableConst4Section() const {
     return MergeableConst4Section;
   }
   const MCSection *getMergeableConst8Section() const {
     return MergeableConst8Section;
   }

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

void AsmPrinter::emitFrameAlloc(const MachineInstr &MI) {
   MCSymbol *FrameAllocSym = MI.getOperand(0).getMCSymbol();
   int FrameOffset = MI.getOperand(1).getImm();
 
   // Emit a symbol assignment.
   OutStreamer->emitAssignment(FrameAllocSym,
                              MCConstantExpr::create(FrameOffset, OutContext));
 }
 
+void AsmPrinter::emitBBInfoSection(const MachineFunction &MF) {
+  if (!MF.hasBBLabels())
+    return;
+
+  MCSection *BBInfoSection =
+      getObjFileLowering().getBBInfoSection(*MF.getSection());
+  if (!BBInfoSection)
+    return;
+
+  const MCSymbol *FunctionSymbol = getFunctionBegin();
+
+  OutStreamer->PushSection();
+  OutStreamer->SwitchSection(BBInfoSection);
+  OutStreamer->emitSymbolValue(FunctionSymbol, getPointerSize());
+  // Emit the total number of basic blocks in this function.
+  OutStreamer->emitULEB128IntValue(MF.size());
+  // Emit BB Information for each basic block in the funciton.
+  for (auto &MBB : MF) {
+    const MCSymbol *MBBSymbol =
+        MBB.pred_empty() ? FunctionSymbol : MBB.getSymbol();
+    // Emit the basic block offset.
+    emitLabelDifferenceAsULEB128(MBBSymbol, FunctionSymbol);
+    // Emit the basic block size.
+    emitLabelDifferenceAsULEB128(MBB.getEndSymbol(), MBBSymbol);
+    OutStreamer->emitULEB128IntValue(MBB.getBBInfoMetadata());
+  }
+  OutStreamer->PopSection();
+}
+
 void AsmPrinter::emitStackSizeSection(const MachineFunction &MF) {
   if (!MF.getTarget().Options.EmitStackSizeSection)
     return;
 
   MCSection *StackSizeSection =
       getObjFileLowering().getStackSizesSection(*getCurrentSection());
   if (!StackSizeSection)
     return;
 
   const MachineFrameInfo &FrameInfo = MF.getFrameInfo();
   // Don't emit functions with dynamic stack allocations.
   if (FrameInfo.hasVarSizedObjects())
for (auto &MI : MBB) {
                              HI.TimerGroupName, HI.TimerGroupDescription,
                              TimePassesIsEnabled);
           HI.Handler->endInstruction();
         }
       }
     }
 
     // We must emit temporary symbol for the end of this basic block, if either
-    // we have BBLabels enabled and we want to emit size directive for the BBs,
-    // or if this basic blocks marks the end of a section (except the section
-    // containing the entry basic block as the end symbol for that section is
-    // CurrentFnEnd).
-    if ((MAI->hasDotTypeDotSizeDirective() && MF->hasBBLabels()) ||
-        (MBB.isEndSection() && !MBB.sameSection(&MF->front())))
+    // we have BBLabels enabled or if this basic blocks marks the end of a
+    // section (except the section containing the entry basic block as the end
+    // symbol for that section is CurrentFnEnd).
+    if (MF->hasBBLabels() ||
+        (MAI->hasDotTypeDotSizeDirective() && MBB.isEndSection() &&
+         !MBB.sameSection(&MF->front())))
       OutStreamer->emitLabel(MBB.getEndSymbol());
 
-    // Helper for emitting the size directive associated with a basic block
-    // symbol.
-    auto emitELFSizeDirective = [&](MCSymbol *SymForSize) {
-      const MCExpr *SizeExp = MCBinaryExpr::createSub(
-          MCSymbolRefExpr::create(MBB.getEndSymbol(), OutContext),
-          MCSymbolRefExpr::create(SymForSize, OutContext), OutContext);
-      OutStreamer->emitELFSize(SymForSize, SizeExp);
-    };
-
-    // Emit size directive for the size of each basic block, if BBLabels is
-    // enabled.
-    if (MAI->hasDotTypeDotSizeDirective() && MF->hasBBLabels())
-      emitELFSizeDirective(MBB.getSymbol());
-
-    // Emit size directive for the size of each basic block section once we
-    // get to the end of that section.
     if (MBB.isEndSection()) {
+      // The size directive for the section containing the entry block is
+      // handled separately by the function section.
       if (!MBB.sameSection(&MF->front())) {
-        if (MAI->hasDotTypeDotSizeDirective())
-          emitELFSizeDirective(CurrentSectionBeginSym);
+        if (MAI->hasDotTypeDotSizeDirective()) {
+          // Emit the size directive for the basic block section.
+          const MCExpr *SizeExp = MCBinaryExpr::createSub(
+              MCSymbolRefExpr::create(MBB.getEndSymbol(), OutContext),
+              MCSymbolRefExpr::create(CurrentSectionBeginSym, OutContext),
+              OutContext);
+          OutStreamer->emitELFSize(CurrentSectionBeginSym, SizeExp);
+        }
         MBBSectionRanges[MBB.getSectionIDNum()] =
             MBBSectionRange{CurrentSectionBeginSym, MBB.getEndSymbol()};
       }
     }
     emitBasicBlockEnd(MBB);
   }
 
   EmittedInsts += NumInstsInFunction;
void AsmPrinter::emitFunctionBody() {
 
   // Emit post-function debug and/or EH information.
   for (const HandlerInfo &HI : Handlers) {
     NamedRegionTimer T(HI.TimerName, HI.TimerDescription, HI.TimerGroupName,
                        HI.TimerGroupDescription, TimePassesIsEnabled);
     HI.Handler->endFunction(MF);
   }
 
+  emitBBInfoSection(*MF);
+
   // Emit section containing stack size metadata.
   emitStackSizeSection(*MF);
 
   emitPatchableFunctionEntries();
 
   if (isVerbose())
     OutStreamer->GetCommentOS() << "-- End function\n";
 
void AsmPrinter::SetupMachineFunction(MachineFunction &MF) {
   CurrentSectionBeginSym = nullptr;
   MBBSectionRanges.clear();
   CurExceptionSym = nullptr;
   bool NeedsLocalForSize = MAI->needsLocalForSize();
   if (F.hasFnAttribute("patchable-function-entry") ||
       F.hasFnAttribute("function-instrument") ||
       F.hasFnAttribute("xray-instruction-threshold") ||
       needFuncLabelsForEHOrDebugInfo(MF) || NeedsLocalForSize ||
-      MF.getTarget().Options.EmitStackSizeSection) {
+      MF.getTarget().Options.EmitStackSizeSection || MF.hasBBLabels()) {
     CurrentFnBegin = createTempSymbol("func_begin");
     if (NeedsLocalForSize)
       CurrentFnSymForSize = CurrentFnBegin;
   }
 
   ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
 }
 

llvm/lib/CodeGen/BBSectionsPrepare.cpp

bool BBSectionsPrepare::runOnMachineFunction(MachineFunction &MF) {
   // 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 &&
       !getBBClusterInfoForFunction(MF, FuncAliasMap, ProgramBBClusterInfo,
                                    FuncBBClusterInfo))
     return true;
   MF.setBBSectionsType(BBSectionsType);
-  MF.createBBLabels();
   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. Moreover, a cluster

llvm/lib/CodeGen/MIRParser/MIRParser.cpp

MIRParserImpl::initializeMachineFunction(const yaml::MachineFunction &YamlMF,
   PFS.SM = &BlockSM;
   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.createBBLabels();
     MF.assignBeginEndSections();
   }
   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;

llvm/lib/CodeGen/MachineBasicBlock.cpp

MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
   Insts.Parent = this;
   if (B)
     IrrLoopHeaderWeight = B->getIrrLoopHeaderWeight();
 }
 
 MachineBasicBlock::~MachineBasicBlock() {
 }
 
+unsigned MachineBasicBlock::getBBInfoMetadata() const {
+  const TargetInstrInfo *TII = getParent()->getSubtarget().getInstrInfo();
+  return ((unsigned)isReturnBlock()) |
+         ((!empty() && TII->isTailCall(back())) << 1) | (isEHPad() << 2);
+}
+
 /// Return the MCSymbol for this basic block.
 MCSymbol *MachineBasicBlock::getSymbol() const {
   if (!CachedMCSymbol) {
     const MachineFunction *MF = getParent();
     MCContext &Ctx = MF->getContext();
-    auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
-
-    assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
 
-    // We emit a non-temporary symbol for every basic block if we have BBLabels
-    // or -- with basic block sections -- when a basic block begins a section.
-    // With basic block symbols, we use a unary encoding which can
-    // compress the symbol names significantly. For basic block sections where
-    // this block is the first in a cluster, we use a non-temp descriptive name.
-    // Otherwise we fall back to use temp label.
-    if (MF->hasBBLabels()) {
-      auto Iter = MF->getBBSectionsSymbolPrefix().begin();
-      if (getNumber() < 0 ||
-          getNumber() >= (int)MF->getBBSectionsSymbolPrefix().size())
-        report_fatal_error("Unreachable MBB: " + Twine(getNumber()));
-      // The basic blocks for function foo are named a.BB.foo, aa.BB.foo, and
-      // so on.
-      std::string Prefix(Iter + 1, Iter + getNumber() + 1);
-      std::reverse(Prefix.begin(), Prefix.end());
-      CachedMCSymbol =
-          Ctx.getOrCreateSymbol(Twine(Prefix) + ".BB." + Twine(MF->getName()));
-    } else if (MF->hasBBSections() && isBeginSection()) {
+    // We emit a non-temporary symbol -- with a descriptive name -- if it begins
+    // a section (with basic block sections). Otherwise we fall back to use temp
+    // label.
+    if (MF->hasBBSections() && isBeginSection()) {
       SmallString<5> Suffix;
       if (SectionID == MBBSectionID::ColdSectionID) {
         Suffix += ".cold";
       } else if (SectionID == MBBSectionID::ExceptionSectionID) {
         Suffix += ".eh";
       } else {
         Suffix += "." + std::to_string(SectionID.Number);
       }
       CachedMCSymbol = Ctx.getOrCreateSymbol(MF->getName() + Suffix);
     } else {
+      auto Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
       CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
                                              Twine(MF->getFunctionNumber()) +
                                              "_" + Twine(getNumber()));
     }
   }
   return CachedMCSymbol;
 }
 

llvm/lib/CodeGen/MachineFunction.cpp

for (; MBBI != E; ++MBBI, ++BlockNo) {
     }
   }
 
   // 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 is used with -fbasic-block-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(
-        (MBBI->getNumber() >= 0 && MBBI->getNumber() < (int)getNumBlockIDs()) &&
-        "BasicBlock number was out of range!");
-    // 'a' - Normal block.
-    // 'r' - Return block.
-    // 'l' - Landing Pad.
-    // 'L' - Return and landing pad.
-    bool isEHPad = MBBI->isEHPad();
-    bool isRetBlock = MBBI->isReturnBlock() && !TII->isTailCall(MBBI->back());
-    char type = 'a';
-    if (isEHPad && isRetBlock)
-      type = 'L';
-    else if (isEHPad)
-      type = 'l';
-    else if (isRetBlock)
-      type = 'r';
-    BBSectionsSymbolPrefix[MBBI->getNumber()] = type;
-  }
-}
-
 /// 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.
 void MachineFunction::assignBeginEndSections() {
   front().setIsBeginSection();
   auto CurrentSectionID = front().getSectionID();
   for (auto MBBI = std::next(begin()), E = end(); MBBI != E; ++MBBI) {
     if (MBBI->getSectionID() == CurrentSectionID)
       continue;

llvm/lib/MC/MCObjectFileInfo.cpp

void MCObjectFileInfo::initELFMCObjectFileInfo(const Triple &T, bool Large) {
 
   FaultMapSection =
       Ctx->getELFSection(".llvm_faultmaps", ELF::SHT_PROGBITS, ELF::SHF_ALLOC);
 
   EHFrameSection =
       Ctx->getELFSection(".eh_frame", EHSectionType, EHSectionFlags);
 
   StackSizesSection = Ctx->getELFSection(".stack_sizes", ELF::SHT_PROGBITS, 0);
+
+  BBInfoSection = Ctx->getELFSection(".bb_info", ELF::SHT_PROGBITS, 0);
 }
 
 void MCObjectFileInfo::initCOFFMCObjectFileInfo(const Triple &T) {
   EHFrameSection =
       Ctx->getCOFFSection(".eh_frame", COFF::IMAGE_SCN_CNT_INITIALIZED_DATA |
                                            COFF::IMAGE_SCN_MEM_READ,
                           SectionKind::getData());
 
if (const MCSymbol *Group = ElfSec.getGroup()) {
     GroupName = Group->getName();
     Flags |= ELF::SHF_GROUP;
   }
 
   return Ctx->getELFSection(".stack_sizes", ELF::SHT_PROGBITS, Flags, 0,
                             GroupName, MCSection::NonUniqueID,
                             cast<MCSymbolELF>(TextSec.getBeginSymbol()));
 }
+
+MCSection *MCObjectFileInfo::getBBInfoSection(const MCSection &TextSec) const {
+  if (Env != IsELF)
+    return BBInfoSection;
+
+  const MCSectionELF &ElfSec = static_cast<const MCSectionELF &>(TextSec);
+  unsigned Flags = ELF::SHF_LINK_ORDER;
+  StringRef GroupName;
+  if (const MCSymbol *Group = ElfSec.getGroup()) {
+    GroupName = Group->getName();
+    Flags |= ELF::SHF_GROUP;
+  }
+
+  return Ctx->getELFSection(".bb_info", ELF::SHT_PROGBITS, Flags, 0, GroupName,
+                            MCSection::NonUniqueID,
+                            cast<MCSymbolELF>(TextSec.getBeginSymbol()));
+}

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

+; RUN: llc < %s -mtriple=x86_64-linux -function-sections -basic-block-sections=labels | FileCheck %s
+
+;; Check we add SHF_LINK_ORDER for .bb_info and link it with the corresponding .text sections.
+; CHECK: .section        .text._Z3barv,"ax",@progbits
+; CHECK-LABEL: _Z3barv:
+; CHECK-NEXT: [[BAR_BEGIN:.+]]:
+; CHECK: .section        .bb_info,"o",@progbits,.text._Z3barv{{$}}
+; CHECK-NEXT: .quad [[BAR_BEGIN]]
+; CHECK: .section        .text._Z3foov,"ax",@progbits
+; CHECK-LABEL: _Z3foov:
+; CHECK-NEXT: [[FOO_BEGIN:.+]]:
+; CHECK: .section        .bb_info,"o",@progbits,.text._Z3foov{{$}}
+; CHECK-NEXT: .quad [[FOO_BEGIN]]
+
+;; Check we add .bb_info section to a COMDAT group with the corresponding .text section if such a COMDAT exists.
+; CHECK: .section        .text._Z4fooTIiET_v,"axG",@progbits,_Z4fooTIiET_v,comdat
+; CHECK-LABEL: _Z4fooTIiET_v:
+; CHECK-NEXT: [[FOOCOMDAT_BEGIN:.+]]:
+; CHECK: .section        .bb_info,"Go",@progbits,_Z4fooTIiET_v,comdat,.text._Z4fooTIiET_v{{$}}
+; CHECK-NEXT: .quad [[FOOCOMDAT_BEGIN]]
+
+
+$_Z4fooTIiET_v = comdat any
+
+define dso_local i32 @_Z3barv() {
+  ret i32 0
+}
+
+define dso_local i32 @_Z3foov() {
+  %1 = call i32 @_Z4fooTIiET_v()
+  ret i32 %1
+}
+
+define linkonce_odr dso_local i32 @_Z4fooTIiET_v() comdat {
+  ret i32 0
+}

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

 ; Check the basic block sections labels option
 ; RUN: llc < %s -mtriple=x86_64-pc-linux -function-sections -basic-block-sections=labels | FileCheck %s -check-prefix=LINUX-LABELS
 
-define void @_Z3bazb(i1 zeroext) {
+define void @_Z3bazb(i1 zeroext) personality i32 (...)* @__gxx_personality_v0 {
   %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
+  br i1 %5, label %6, label %11
 
-6:                                                ; preds = %1
-  %7 = call i32 @_Z3barv()
-  br label %10
+6:
+  %7 = invoke i32 @_Z3barv()
+          to label %11 unwind label %9
+  br label %13
+
+9:
+  landingpad { i8*, i32 }
+          catch i8* null
+  br label %13
+
+11:
+  %12 = call i32 @_Z3foov()
+  br label %13
 
-8:                                                ; preds = %1
-  %9 = call i32 @_Z3foov()
-  br label %10
-
-10:                                               ; preds = %8, %6
+13:
   ret void
 }
 
 declare i32 @_Z3barv() #1
 
 declare i32 @_Z3foov() #1
 
-; LINUX-LABELS: .section
-; LINUX-LABELS: _Z3bazb:
-; LINUX-LABELS-NOT: .section
-; LINUX-LABELS: r.BB._Z3bazb:
-; LINUX-LABELS-NOT: .section
-; LINUX-LABELS: rr.BB._Z3bazb:
+declare i32 @__gxx_personality_v0(...)
+
+; LINUX-LABELS-LABEL: _Z3bazb:
+; LINUX-LABELS: .Lfunc_begin0:
+; LINUX-LABELS: .LBB_END0_[[L1:[0-9]+]]:
+; LINUX-LABELS: .LBB0_[[L2:[0-9]+]]:
+; LINUX-LABELS: .LBB_END0_[[L2]]:
+; LINUX-LABELS: .LBB0_[[L3:[0-9]+]]:
+; LINUX-LABELS: .LBB_END0_[[L3]]:
+; LINUX-LABELS: .LBB0_[[L4:[0-9]+]]:
+; LINUX-LABELS: .LBB_END0_[[L4]]:
+; LINUX-LABELS: .Lfunc_end0:
+
+; LINUX-LABELS: .section  .bb_info,"o",@progbits,.text
+; LINUX-LABELS-NEXT: .quad  .Lfunc_begin0
+; LINUX-LABELS-NEXT: .byte  4
+; LINUX-LABELS-NEXT: .uleb128 .Lfunc_begin0-.Lfunc_begin0
+; LINUX-LABELS-NEXT: .uleb128 .LBB_END0_[[L1]]-.Lfunc_begin0
+; LINUX-LABELS-NEXT: .byte  0
+; LINUX-LABELS-NEXT: .uleb128 .LBB0_[[L2]]-.Lfunc_begin0
+; LINUX-LABELS-NEXT: .uleb128 .LBB_END0_[[L2]]-.LBB0_[[L2]]
+; LINUX-LABELS-NEXT: .byte  0
+; LINUX-LABELS-NEXT: .uleb128 .LBB0_[[L3]]-.Lfunc_begin0
+; LINUX-LABELS-NEXT: .uleb128 .LBB_END0_[[L3]]-.LBB0_[[L3]]
+; LINUX-LABELS-NEXT: .byte  1
+; LINUX-LABELS-NEXT: .uleb128 .LBB0_[[L4]]-.Lfunc_begin0
+; LINUX-LABELS-NEXT: .uleb128 .LBB_END0_[[L4]]-.LBB0_[[L4]]
+; LINUX-LABELS-NEXT: .byte  5