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 ↗

(On Diff #285830)

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?

1333

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

958

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

969

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

969

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

27–28

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

486 ↗

(On Diff #285926)

Typo.

481 ↗

(On Diff #285830)

+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.

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?

1240

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

67

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

957

Run clang-format on the patches.

[rahmanl]

Address Sri's comments.

[rahmanl]

Address Sri's comments.

[rahmanl]

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

27–28

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

1240

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

957

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

nit: s/would include/includes/

1707

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

3–4

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

3–4

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–1708

Use backquotes like below

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

3–4

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

78

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

27–28

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

clang/docs/UsersManual.rst

**-f[no]-unique-internal-linkage-names**
    .. code-block:: console
 
      $ cd $P/foo && clang -c -funique-internal-linkage-names name_conflict.c
      $ cd $P/bar && clang -c -funique-internal-linkage-names name_conflict.c
      $ cd $P && clang foo/name_conflict.o && bar/name_conflict.o
 
 **-fbasic-block-sections=[labels, all, list=<arg>, none]**
 
-  Controls whether Clang emits a label for each basic block.  Further, with
-  values "all" and "list=arg", each basic block or a subset of basic blocks
-  can be placed in its own unique section.
+  Controls how Clang emits text sections for basic blocks. With values ``all``
+  and ``list=<arg>``, each basic block or a subset of basic blocks can be placed
+  in its own unique section. With the "labels" value, normal text sections are
+  emitted, but a ``.bb_addr_map`` section is emitted which includes address
+  offsets for each basic block in the program, relative to the parent function
+  address.
 
   With the ``list=<arg>`` option, a file containing the subset of basic blocks
   that need to placed in unique sections can be specified.  The format of the
   file is as follows.  For example, ``list=spec.txt`` where ``spec.txt`` is the
   following:
 
   ::
 

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

 // REQUIRES: x86-registered-target
 
-// RUN: %clang_cc1 -triple x86_64-pc-linux-gnu -S -o - < %s | FileCheck %s --check-prefix=PLAIN
-// RUN: %clang_cc1 -triple x86_64-pc-linux-gnu -S -fbasic-block-sections=all -fbasic-block-sections=none -o - < %s | FileCheck %s --check-prefix=PLAIN
+// RUN: %clang_cc1 -triple x86_64 -S -o - < %s | FileCheck %s --check-prefix=PLAIN
+// RUN: %clang_cc1 -triple x86_64 -S -fbasic-block-sections=all -fbasic-block-sections=none -o - < %s | FileCheck %s --check-prefix=PLAIN
 
-// RUN: %clang_cc1 -triple x86_64-pc-linux-gnu -S -fbasic-block-sections=labels -o - < %s | FileCheck %s --check-prefix=BB_LABELS
-// RUN: %clang_cc1 -triple x86_64-pc-linux-gnu -S -fbasic-block-sections=all -o - < %s | FileCheck %s --check-prefix=BB_WORLD --check-prefix=BB_ALL
-// RUN: %clang_cc1 -triple x86_64-pc-linux-gnu -S -fbasic-block-sections=list=%S/Inputs/basic-block-sections.funcnames -o - < %s | FileCheck %s --check-prefix=BB_WORLD --check-prefix=BB_LIST
-// RUN: %clang_cc1 -triple x86_64-pc-linux-gnu -S -fbasic-block-sections=all -funique-basic-block-section-names -o - < %s | FileCheck %s --check-prefix=UNIQUE
+// RUN: %clang_cc1 -triple x86_64 -S -fbasic-block-sections=all -o - < %s | FileCheck %s --check-prefix=BB_WORLD --check-prefix=BB_ALL
+// RUN: %clang_cc1 -triple x86_64 -S -fbasic-block-sections=list=%S/Inputs/basic-block-sections.funcnames -o - < %s | FileCheck %s --check-prefix=BB_WORLD --check-prefix=BB_LIST
+// RUN: %clang_cc1 -triple x86_64 -S -fbasic-block-sections=all -funique-basic-block-section-names -o - < %s | FileCheck %s --check-prefix=UNIQUE
 
 int world(int a) {
   if (a > 10)
     return 10;
   else if (a > 5)
     return 5;
   else
     return 0;
 }
 
 int another(int a) {
   if (a > 10)
     return 20;
   return 0;
 }
 
 // PLAIN-NOT: section
 // PLAIN: world:
 //
-// BB_LABELS-NOT: section
-// BB_LABELS: world:
-// BB_LABELS: a.BB.world:
-// BB_LABELS: aa.BB.world:
-// BB_LABELS: a.BB.another:
-//
 // BB_WORLD: .section .text.world,"ax",@progbits{{$}}
 // BB_WORLD: world:
 // BB_WORLD: .section .text.world,"ax",@progbits,unique
 // BB_WORLD: world.1:
 // BB_WORLD: .section .text.another,"ax",@progbits
 // BB_ALL: .section .text.another,"ax",@progbits,unique
 // BB_ALL: another.1:
 // BB_LIST-NOT: .section .text.another,"ax",@progbits,unique
 // BB_LIST: another:
 // BB_LIST-NOT: another.1:
 //
 // UNIQUE: .section .text.world.world.1,
 // UNIQUE: .section .text.another.another.1,

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 emitBBAddrMapSection(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/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

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 *getBBAddrMapSection(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));
 }
 
+/// Returns the BB metadata to be emitted in the bb_addr_map section for a given
+/// basic block. This can be used to capture more precise profile information.
+/// We use the last 3 bits (LSBs) to ecnode the following information:
+///  * (1): set if return block (ret or tail call).
+///  * (2): set if ends with a tail call.
+///  * (3): set if exception handling (EH) landing pad.
+/// The remaining bits are zero.
+static unsigned getBBAddrMapMetadata(const MachineBasicBlock &MBB) {
+  const TargetInstrInfo *TII = MBB.getParent()->getSubtarget().getInstrInfo();
+  return ((unsigned)MBB.isReturnBlock()) |
+         ((!MBB.empty() && TII->isTailCall(MBB.back())) << 1) |
+         (MBB.isEHPad() << 2);
+}
+
+void AsmPrinter::emitBBAddrMapSection(const MachineFunction &MF) {
+  MCSection *BBAddrMapSection =
+      getObjFileLowering().getBBAddrMapSection(*MF.getSection());
+  assert(BBAddrMapSection && ".bb_addr_map section is not initialized.");
+
+  const MCSymbol *FunctionSymbol = getFunctionBegin();
+
+  OutStreamer->PushSection();
+  OutStreamer->SwitchSection(BBAddrMapSection);
+  OutStreamer->emitSymbolValue(FunctionSymbol, getPointerSize());
+  // Emit the total number of basic blocks in this function.
+  OutStreamer->emitULEB128IntValue(MF.size());
+  // Emit BB Information for each basic block in the funciton.
+  for (const MachineBasicBlock &MBB : MF) {
+    const MCSymbol *MBBSymbol =
+        MBB.pred_empty() ? FunctionSymbol : MBB.getSymbol();
+    // Emit the basic block offset.
+    emitLabelDifferenceAsULEB128(MBBSymbol, FunctionSymbol);
+    // Emit the basic block size. When BBs have alignments, their size cannot
+    // always be computed from their offsets.
+    emitLabelDifferenceAsULEB128(MBB.getEndSymbol(), MBBSymbol);
+    OutStreamer->emitULEB128IntValue(getBBAddrMapMetadata(MBB));
+  }
+  OutStreamer->PopSection();
+}
+
 void AsmPrinter::emitStackSizeSection(const MachineFunction &MF) {
   if (!MF.getTarget().Options.EmitStackSizeSection)
     return;
 
   MCSection *StackSizeSection =
       getObjFileLowering().getStackSizesSection(*getCurrentSection());
   if (!StackSizeSection)
     return;
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);
   }
 
+  // Emit section containing BB address offsets and their metadata, when
+  // BB labels are requested for this function.
+  if (MF->hasBBLabels())
+    emitBBAddrMapSection(*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/BasicBlockSections.cpp

 //    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 cluster. This also bloats the object file and binary sizes.
 //
 // Basic Block Labels
 // ==================
 //
-// With -fbasic-block-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.
+// With -fbasic-block-sections=labels, we emit the offsets of BB addresses of
+// every function into a .bb_addr_map section. Along with the function symbols,
+// this allows for mapping of virtual addresses in PMU profiles back to the
+// corresponding basic blocks. This logic is implemented in AsmPrinter. This
+// pass only assigns the BBSectionType of every function to ``labels``.
 //
 //===----------------------------------------------------------------------===//
 
 #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"
bool BasicBlockSections::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();
   assignSections(MF, FuncBBClusterInfo);
 
   // We make sure that the cluster including the entry basic block precedes all
   // other clusters.
   auto EntryBBSectionID = MF.front().getSectionID();
 
   // Helper function for ordering BB sections as follows:
   //   * Entry section (section including the entry block).

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() {
 }
 
 /// 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 {
+      const StringRef 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

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::getBBAddrMapSection(const MCSection &TextSec) const {
+  if (Env != IsELF)
+    return nullptr;
+
+  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_addr_map", 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 -function-sections -basic-block-sections=labels | FileCheck %s
+
+$_Z4fooTIiET_v = comdat any
+
+define dso_local i32 @_Z3barv() {
+  ret i32 0
+}
+;; Check we add SHF_LINK_ORDER for .bb_addr_map and link it with the corresponding .text sections.
+; CHECK:    .section .text._Z3barv,"ax",@progbits
+; CHECK-LABEL:  _Z3barv:
+; CHECK-NEXT: [[BAR_BEGIN:.Lfunc_begin[0-9]+]]:
+; CHECK:    .section .bb_addr_map,"o",@progbits,.text._Z3barv{{$}}
+; CHECK-NEXT:   .quad [[BAR_BEGIN]]
+
+
+define dso_local i32 @_Z3foov() {
+  %1 = call i32 @_Z4fooTIiET_v()
+  ret i32 %1
+}
+; CHECK:    .section .text._Z3foov,"ax",@progbits
+; CHECK-LABEL:  _Z3foov:
+; CHECK-NEXT: [[FOO_BEGIN:.Lfunc_begin[0-9]+]]:
+; CHECK:    .section  .bb_addr_map,"o",@progbits,.text._Z3foov{{$}}
+; CHECK-NEXT:   .quad [[FOO_BEGIN]]
+
+
+define linkonce_odr dso_local i32 @_Z4fooTIiET_v() comdat {
+  ret i32 0
+}
+;; Check we add .bb_addr_map 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:.Lfunc_begin[0-9]+]]:
+; CHECK:    .section .bb_addr_map,"Go",@progbits,_Z4fooTIiET_v,comdat,.text._Z4fooTIiET_v{{$}}
+; CHECK-NEXT:   .quad [[FOOCOMDAT_BEGIN]]

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
+; RUN: llc < %s -mtriple=x86_64 -function-sections -basic-block-sections=labels | FileCheck %s
 
-define void @_Z3bazb(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 @_Z3barv()
-  br label %10
-
-8:                                                ; preds = %1
-  %9 = call i32 @_Z3foov()
-  br label %10
+define void @_Z3bazb(i1 zeroext) personality i32 (...)* @__gxx_personality_v0 {
+  br i1 %0, label %2, label %7
 
-10:                                               ; preds = %8, %6
+2:
+  %3 = invoke i32 @_Z3barv()
+          to label %7 unwind label %5
+  br label %9
+
+5:
+  landingpad { i8*, i32 }
+          catch i8* null
+  br label %9
+
+7:
+  %8 = call i32 @_Z3foov()
+  br label %9
+
+9:
   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(...)
+
+; CHECK-LABEL:  _Z3bazb:
+; CHECK-LABEL:  .Lfunc_begin0:
+; CHECK-LABEL:  .LBB_END0_0:
+; CHECK-LABEL:  .LBB0_1:
+; CHECK-LABEL:  .LBB_END0_1:
+; CHECK-LABEL:  .LBB0_2:
+; CHECK-LABEL:  .LBB_END0_2:
+; CHECK-LABEL:  .LBB0_3:
+; CHECK-LABEL:  .LBB_END0_3:
+; CHECK-LABEL:  .Lfunc_end0:
+
+; CHECK:  .section  .bb_addr_map,"o",@progbits,.text
+; CHECK-NEXT: .quad .Lfunc_begin0
+; CHECK-NEXT: .byte 4
+; CHECK-NEXT: .uleb128 .Lfunc_begin0-.Lfunc_begin0
+; CHECK-NEXT: .uleb128 .LBB_END0_0-.Lfunc_begin0
+; CHECK-NEXT: .byte 0
+; CHECK-NEXT: .uleb128 .LBB0_1-.Lfunc_begin0
+; CHECK-NEXT: .uleb128 .LBB_END0_1-.LBB0_1
+; CHECK-NEXT: .byte 0
+; CHECK-NEXT: .uleb128 .LBB0_2-.Lfunc_begin0
+; CHECK-NEXT: .uleb128 .LBB_END0_2-.LBB0_2
+; CHECK-NEXT: .byte 1
+; CHECK-NEXT: .uleb128 .LBB0_3-.Lfunc_begin0
+; CHECK-NEXT: .uleb128 .LBB_END0_3-.LBB0_3
+; CHECK-NEXT: .byte 5