This is an archive of the discontinued LLVM Phabricator instance.

Propeller: LLVM support for basic block sections
ClosedPublic

Authored by tmsriram on Sep 25 2019, 5:02 PM.

Details

Summary

This is the parent patch of a series of patches to enable Basic Block Sections support in LLVM which is the building block for the Propeller post link optimization framework. Please see the RFC here: https://groups.google.com/forum/#!msg/llvm-dev/ef3mKzAdJ7U/1shV64BYBAAJ and the detailed RFC doc here: https://github.com/google/llvm-propeller/blob/plo-dev/Propeller_RFC.pdf.

We introduce a new compiler option, -fbasicblock-sections=, which places every basic block in a unique ELF text section in the object file along with a symbol labeling 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. These branches can only be removed later by the linker after the blocks have been reordered.
  2. All inter-basic block 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 which bloats the size of the object files. Further, the compiler tries to use short branch instructions on some ISAs for branch offsets that can be accommodated in one byte. 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.
  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 Info and CFI need special handling and will be presented as separate patches.

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.

Diff Detail

Event Timeline

tmsriram created this revision.Sep 25 2019, 5:02 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 25 2019, 5:02 PM

A few comments after a quick high level scan of patch. Also - please mark all these related patches as parent and child versions in Phabricator.

llvm/include/llvm/CodeGen/MachineBasicBlock.h
139 ↗(On Diff #221865)

comment

820 ↗(On Diff #221865)

please run clang-format on this patch

llvm/include/llvm/Transforms/Utils/ModuleUtils.h
111 ↗(On Diff #221865)

What happens if unique module id is not actually unique?

112 ↗(On Diff #221865)

I don't see any calls using this new parameter in this patch - should this change be included with a different patch in the set?

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp
2988 ↗(On Diff #221865)

Should this be uncommented, or removed?

llvm/lib/CodeGen/MachineBlockPlacement.cpp
3128 ↗(On Diff #221865)

Only a whitespace change in this file, remove from patch.

llvm/lib/MC/MCDwarf.cpp
1481 ↗(On Diff #221865)

add comment summarizing when dedup is needed

1711 ↗(On Diff #221865)

Add parameter name constants to constant parameters here and in other calls to this function.

llvm/lib/Target/X86/X86FrameLowering.cpp
465 ↗(On Diff #221865)

change to early return. Also a comment would be good

llvm/lib/Transforms/Utils/ModuleUtils.cpp
274 ↗(On Diff #221865)

Confusing comment, as the first 2 sentences seem contradictory (module id not guaranteed to be unique, so we use it).

MaskRay added inline comments.
llvm/lib/CodeGen/MachineBasicBlock.cpp
81 ↗(On Diff #221865)

std::string(getNumber(), 'a')

llvm/lib/MC/ELFObjectWriter.cpp
1374 ↗(On Diff #221865)

R_*_SIZE is x86 specific. If you want to use it on other architectures, it will require an ABI change.

aprantl added inline comments.Sep 27 2019, 10:52 AM
llvm/include/llvm/CodeGen/AsmPrinterHandler.h
71 ↗(On Diff #221865)

Please doxygenify all comments in this patch according to https://llvm.org/docs/CodingStandards.html#doxygen-use-in-documentation-comments.

llvm/test/DebugInfo/X86/basicblock-sections-cfi.ll
85 ↗(On Diff #221865)

Please try to remove all string attributes that aren't strictly necessary, they are a maintenance burden.

tmsriram updated this revision to Diff 222268.Sep 27 2019, 4:54 PM
tmsriram marked 4 inline comments as done.

clang-format, comments, minor fixes suggested.

tmsriram marked 9 inline comments as done and an inline comment as not done.Sep 27 2019, 4:57 PM
tmsriram added inline comments.
llvm/include/llvm/Transforms/Utils/ModuleUtils.h
111 ↗(On Diff #221865)

It does not make the situation any worse and we would could end up with two or more internal linkage functions having the same name. Profile attribution would not be accurate and could cause sub-optimal performance decisions particularly if this function is hot. Maybe we could warn about this and let the user pick another name for this.

112 ↗(On Diff #221865)

It is used in clang/lib/CodeGen/CodeGenModule.cpp where the function name is formed. Is this ok?

llvm/lib/CodeGen/MachineBasicBlock.cpp
81 ↗(On Diff #221865)

Great catch!

llvm/lib/MC/ELFObjectWriter.cpp
1374 ↗(On Diff #221865)

Currently guarded with a -mrelocate-with-symbols option. Anything better we could do here?

tejohnson added inline comments.Oct 4 2019, 11:38 AM
llvm/include/llvm/Transforms/Utils/ModuleUtils.h
111 ↗(On Diff #221865)

I think just clarify what the consequences of a collision are in the comments (would be a bigger problem if there was a possible correctness issue).

112 ↗(On Diff #221865)

Can you connect these patches by parent/child relationships in phabricator?

tmsriram updated this revision to Diff 238663.Jan 16 2020, 4:55 PM
tmsriram marked 2 inline comments as done.

Main changes:

  • Support for Basic block sections with exceptions
  • Support for selectively enabling basic block sections for a subset of basic blocks
  • Bug fixes with debug info and cfi
aprantl added inline comments.Jan 17 2020, 11:13 AM
llvm/lib/CodeGen/AsmPrinter/EHStreamer.h
73 ↗(On Diff #238663)

///

76 ↗(On Diff #238663)

///

tmsriram updated this revision to Diff 238892.Jan 17 2020, 2:18 PM

Fix comments.

tmsriram marked 2 inline comments as done.Jan 17 2020, 2:19 PM
tmsriram added inline comments.
llvm/lib/CodeGen/AsmPrinter/EHStreamer.h
76 ↗(On Diff #238663)

This seems alright, other structs use the same style for per-field comments.

bcain added a subscriber: bcain.Jan 17 2020, 2:55 PM

Try to avoid monolithic patch like this. Please consider splitting it into a few smaller incremental patches with (possibly) independent testing. Logically, it can be split into 1) IR support; 2) machine BB level support; 3) debug support 4) CFI support 5) exception and 6) the 'main tranformation' part if there is one'.

tmsriram updated this revision to Diff 241295.Jan 29 2020, 2:35 PM
tmsriram marked an inline comment as done.

Splitting the LLVM patch for Basic Block Sections Support into many smaller patches as follows:

  1. Base patch for basic block sections support - This itself is split into Base_1 and Base_2
  2. CFI Support for block sections
  3. DebugInfo Support for basic block sections
  4. Exceptions Support for basic block sections
  5. Other smaller patches

We will link the dependent patches as children of this parent patch.

This is the parent patch and is the base patch (Base_1)

davidxl added inline comments.Jan 29 2020, 3:04 PM
llvm/include/llvm/Target/TargetMachine.h
262

nit: naming consistency: getBasicBlockSections -->getBBSections

268

isFunctionBBSectionsList.

275

getBBSectionSet

tmsriram updated this revision to Diff 241327.Jan 29 2020, 5:12 PM

Include llc options for basic block sections.

tmsriram updated this revision to Diff 241591.Jan 30 2020, 2:51 PM

Change "BasicBlockSections" to "BBSections".

tmsriram marked 3 inline comments as done.Jan 30 2020, 2:51 PM
MaskRay added inline comments.Jan 30 2020, 4:56 PM
llvm/include/llvm/Target/TargetOptions.h
70

Newer code should use enum class instead of namespace+unscoped enumeration

71

Order enum members by the extent they enable basic block sections.

llvm/lib/CodeGen/CodeGenPrepare.cpp
450 ↗(On Diff #241591)

We probably can make TargetPassConfig required so we don't have to check TM nullness everywhere.

Created D73754

tmsriram updated this revision to Diff 241842.Jan 31 2020, 4:25 PM

Support the basicblock-sections=<file> option in llc too for feature completeness here and to add tests.

tmsriram updated this revision to Diff 241845.Jan 31 2020, 4:33 PM

Fix a typo.

tmsriram updated this revision to Diff 242470.Feb 4 2020, 4:50 PM

Refactore getBBSectionsList function into a common place so that it can be shared with clang and lld.

I'm too far away from this part of the code to really assess if this is the proper way of plugin into the codegen unfortunately, I'd ask @echristo maybe?

llvm/include/llvm/CodeGen/CommandFlags.inc
26

Is this needed in this file?

llvm/include/llvm/IR/BasicBlock.h
436 ↗(On Diff #242470)

These methods aren't defined (or used) anywhere.

llvm/include/llvm/ProfileData/PropellerProf.h
20 ↗(On Diff #242470)

The "propeller-specific" aspect of it seems unrelated to "adding support for basic block sections"

tmsriram updated this revision to Diff 242970.Feb 6 2020, 11:49 AM

Address reviewer comments. Delete changes to BasicBlock.h.

tmsriram marked 2 inline comments as done.Feb 6 2020, 11:51 AM
tmsriram added inline comments.
llvm/include/llvm/ProfileData/PropellerProf.h
20 ↗(On Diff #242470)

We can rename this to BBSectionsList.h or something similar. This allows basic block sections for a specific set of basic blocks which is useful for Propeller.

tmsriram updated this revision to Diff 243038.Feb 6 2020, 3:51 PM

Rebase and rename PropellerProf to BBSectionsProf.

tmsriram updated this revision to Diff 243689.Feb 10 2020, 3:19 PM

Use MemoryBuffer::getFile instead of fstream.

I'm not really happy with the way functions lists are handled:

  1. It probably makes sense to encode as a function attribute, rather than sticking booleans directly onto llvm::Function . Otherwise, we need to figure out a serialization story; we try to keep IR serialization as complete as possible, even as late as CodeGenPrepare.
  1. Attaching the attributes should be done by a separate module pass, I think, not by jamming it into CodeGenPrepare. CodeGenPrepare is an optimization, this isn't (at least, not in the same sense).
  1. Not sure it makes sense to stick the list of functions into TargetMachine, as opposed to just modifying the module when the file is parsed.
tmsriram updated this revision to Diff 243943.Feb 11 2020, 11:50 AM

Remove usage of "propeller" from this patch, this is only about support for basic block sections.

(tests missing?)

llvm/include/llvm/ProfileData/BBSectionsProf.h
1 ↗(On Diff #243943)

License blurb missing

llvm/lib/ProfileData/BBSectionsProf.cpp
1 ↗(On Diff #243943)

License blurb missing

tmsriram updated this revision to Diff 246454.Feb 25 2020, 7:37 AM

Deleted changes to CodeGenPrepare.cpp, Function.*.

BBSections is now handled in a separate pass so this base patch becomes very simple.

@efriedma : Hi Eli, this is the parent patch of D73674. Appreciate if you could take a look at this too, thanks!

I'm not completely comfortable passing the BB-sections list to the backend as a file path; generally we try to allow the "frontend" (clang/llc/etc.) to control all file I/O. But I'm not sure what the alternative looks like. I guess we could pass it as MemoryBuffer?

Otherwise looks fine.

I'm not completely comfortable passing the BB-sections list to the backend as a file path; generally we try to allow the "frontend" (clang/llc/etc.) to control all file I/O. But I'm not sure what the alternative looks like. I guess we could pass it as MemoryBuffer?

Otherwise looks fine.

  • Looking into this, it is not possible to keep the unique_ptr<MemoryBuffer> in TargetOptions.h as the assignment operator is deleted.
  • I may have to store the MemoryBuffer in TargetMachine or find another home for it, in which case I may need special handling for both llc and LTO.
  • I looked at how some other profile files are stored and noticed that for SampleProfileLoader, the file path is stored as a string in PassBuilder.h and the file seems to be read in the backend.

Thoughts? Thanks!

tmsriram updated this revision to Diff 249238.Mar 9 2020, 4:09 PM

Address Reviewer comments.

  • Use MemoryBuffer in TargetOptions.h instead of storing the profile file as string. Make it shared_ptr to allow copying of Options.

Couple of inline comments. I'm trying pretty hard to be able to get rid of TargetOptions.h some day if possible. Any thoughts on ways to do this without?

llvm/include/llvm/Target/TargetOptions.h
73–74

Can you describe the use case behind this in the comments?

281–283

Why would you want to be able to copy it again?

Also the commit message is awesome, but would be good to get the commit message represented as comments in lots of the final code if possible :)

To be clear I think this is close to being acceptable, I'm just asking some questions before hitting the ack and getting things tidied up a bit so the next person doesn't have to ask :)

tmsriram marked 2 inline comments as done.Mar 9 2020, 4:52 PM

Also the commit message is awesome, but would be good to get the commit message represented as comments in lots of the final code if possible :)

Will do, I can go over the code and add these comments in appropriate places but if you have specific locations please mention.

llvm/include/llvm/Target/TargetOptions.h
73–74

Sure. Just to be clear, are you referring only to "List" or everything?

281–283

I am not copying Options but this is existing code. I can dig exactly where but Options is being copied and that disallows unique_ptr. shared_ptr seems fine as I only want one copy of the MemoryBuffer and that is guaranteed.

Couple of inline comments. I'm trying pretty hard to be able to get rid of TargetOptions.h some day if possible. Any thoughts on ways to do this without?

Missed this comment. I can dig more and maybe move it to TargetMachine.h potentially. This has to be done from llc and LTO too so not sure how that would work. Where were you planning on moving the existing fields of TargetOptions to? Thanks.

In LLVM core libraries, we generally want to accommodate use-cases that don't involve writing files to disk. This makes it easier to write tools targeting new use-cases. Here, for example, someone might want to try writing a JIT using a Propeller workflow. If SampleProfileLoader isn't supporting that, it should probably be fixed.

Mechanically, this seems fine... but it's also okay if we end up with a bit of similar code in multiple places. llc option parsing vs. lld option parsing is two distinct operations.

In LLVM core libraries, we generally want to accommodate use-cases that don't involve writing files to disk. This makes it easier to write tools targeting new use-cases. Here, for example, someone might want to try writing a JIT using a Propeller workflow. If SampleProfileLoader isn't supporting that, it should probably be fixed.

Mechanically, this seems fine... but it's also okay if we end up with a bit of similar code in multiple places. llc option parsing vs. lld option parsing is two distinct operations.

Sure, I made the MemoryBuffer a shared_ptr in TargetOptions and moves the IO out of the LLVM core. The duplicated code in lld and llc is just the getFile and Error check. Thanks!

To be clear I think this is close to being acceptable

Agreed. I am still waiting for the resolution to my (very old) comment about:

namespace BasicBlockSection {
  enum SectionMode {

A scoped enumeration (enum class) will be clearer.

The summary is very long and includes lots of stuff not touched by this patch. The relevant paragraphs should be moved to a subsequent patch I think.

To be clear I think this is close to being acceptable

Agreed. I am still waiting for the resolution to my (very old) comment about:

Then, let me end your wait right away! :)

namespace BasicBlockSection {
  enum SectionMode {

A scoped enumeration (enum class) will be clearer.

I put it in its own namespace like many other enums in that file which are not scoped. If you insist, I can remove the namespace and make it scoped.

The summary is very long and includes lots of stuff not touched by this patch. The relevant paragraphs should be moved to a subsequent patch I think.

IMO, The ideal place to put the summary would be in BBSectionsPrepare.cpp which is the pass that does the actual analysis. I will do that.

tmsriram updated this revision to Diff 249516.Mar 10 2020, 4:27 PM
tmsriram marked 4 inline comments as done.

Address Reviewer comments:

  • Make BasicBlock a scoped enum and reorder fields
  • More comments on all the enum values
  • Rebase

@eli.friedman @echristo Is this patch alright? I have added detailed comments as suggested by Eric to BBSectionsPrepare.cpp in https://reviews.llvm.org/D73674#change-lCLJRdamtrcE Thanks!

This revision is now accepted and ready to land.Mar 11 2020, 5:31 PM
MaskRay accepted this revision.Mar 11 2020, 5:53 PM

Please still consider my suggestion that removes unrelated paragraphs from the summary :)

echristo accepted this revision.Mar 11 2020, 5:59 PM
tmsriram edited the summary of this revision. (Show Details)Mar 12 2020, 1:02 PM

Please still consider my suggestion that removes unrelated paragraphs from the summary :)

Edited to keep it focussed on bb sections and labels.

tmsriram updated this revision to Diff 250315.Mar 13 2020, 3:21 PM

Fix the comment for the option basicblock-sections.

This revision was automatically updated to reflect the committed changes.
Allen added a subscriber: Allen.Sep 9 2022, 9:32 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 9 2022, 9:32 AM
Herald added a subscriber: StephenFan. · View Herald Transcript