This is an archive of the discontinued LLVM Phabricator instance.

Append ".__part.<ID>" to all basic block section symbols.
ClosedPublic

Authored by tmsriram on Dec 10 2020, 7:01 PM.

Details

Summary

Every basic block section symbol created by -fbasic-block-sections will contain ".__part." to know that this symbol corresponds to a basic block fragment of the function.

This patch solves two problems:

a) Like D89617, we want function symbols with suffixes to be properly qualified so that external tools like profile aggregators know exactly what this symbol corresponds to.
b) The current basic block naming just adds a ".N" to the symbol name where N is some integer. This collides with how clang creates __cxx_global_var_init.N. clang creates these symbol names to call constructor functions and basic block symbol naming should not use the same style.

I have fixed all the test cases and added an extra test for __cxx_global_var_init breakage.

Diff Detail

Event Timeline

tmsriram created this revision.Dec 10 2020, 7:01 PM
tmsriram requested review of this revision.Dec 10 2020, 7:01 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 10 2020, 7:01 PM

It may be worthwhile to think about removing the second dot from the naming, i.e., foo.__bb.N -> foo.__bbN . The reason is that this further distinguishes the symbol name from symbols like __cxx_global_var_init.N plus it saves one character.

It may be worthwhile to think about removing the second dot from the naming, i.e., foo.__bb.N -> foo.__bbN . The reason is that this further distinguishes the symbol name from symbols like __cxx_global_var_init.N plus it saves one character.

The -funique-internal-linkage-names option uses ".__uniq." so I wanted to stick to that convention. I am not sure what you mean when you say further distinguishing.

rahmanl added a comment.EditedDec 13 2020, 11:55 PM

It may be worthwhile to think about removing the second dot from the naming, i.e., foo.__bb.N -> foo.__bbN . The reason is that this further distinguishes the symbol name from symbols like __cxx_global_var_init.N plus it saves one character.

The -funique-internal-linkage-names option uses ".__uniq." so I wanted to stick to that convention. I am not sure what you mean when you say further distinguishing.

My focus is more on how this plays out with -fbasic-block-sections=list=.
With .__bb.N we may end up having four different symbols for a function foo, foo.cold, foo.eh, and foo.__bb.N. How would a symbolizer/tool identify these as basic block sections of the same function? My guess is that it first inspects the last extension. If it's .cold or .eh, then the remainder is the base function name, otherwise, if it's a number, it would have to inspect the prior extension again to make sure it's .__bb (hence my note about distinguishing with __cxx_global_var_init.N.
.__uniq does not have the same problem because there is only one way for the extension.

Another (rather weak) concern is that the prefix __bb may reflect that the section comes from a basic block of the same id. This is only the case in -fbasic-block-sections=all. With =list the section ID number may not be the same as the basic block which begins that section.

tmsriram updated this revision to Diff 313401.EditedDec 22 2020, 11:44 AM
tmsriram retitled this revision from Prepend "__bb" to all basic block section symbols. to Append ".__part.<ID>" to all basic block section symbols..

Use "part" instead of "bb". __part is more descriptive as the symbol can denote one or more basic blocks.

rahmanl accepted this revision.Dec 22 2020, 12:18 PM

Please also replace bb in the description of the patch with part.

This revision is now accepted and ready to land.Dec 22 2020, 12:18 PM
tmsriram edited the summary of this revision. (Show Details)Dec 22 2020, 12:26 PM

b) The current basic block naming just adds a ".N" to the symbol name where N is some integer. This collides with how clang creates __cxx_global_var_init.N. clang creates these symbol names to call constructor functions and basic block symbol naming should not use the same style.

This reason alone is not sufficient I guess. __part.N greatly increases .strtab usage. Are there other benefits?

b) The current basic block naming just adds a ".N" to the symbol name where N is some integer. This collides with how clang creates __cxx_global_var_init.N. clang creates these symbol names to call constructor functions and basic block symbol naming should not use the same style.

This reason alone is not sufficient I guess. __part.N greatly increases .strtab usage. Are there other benefits?

There are exactly two reasons to do this:

  1. The simple naming collides with __cxx_global_var_init.N naming, which is a show stopper.
  2. External tools need to understand symbol names such as these for profile attribution. D89617 did that unique internal linkage symbols by adding the uniq suffix. This adds the part suffix.

Having said that, let's come to the part of .strtab bloats. Yes, we are aware of that and have gone to great lengths to minimize this for Propeller:

  • For e.g. -fbasic-block-sections=labels uses a special section to store these symbols without bloating strtab and symtab
  • Propeller uses -fbasic-block-sections=list to selectively create sections which reduces strtab bloat and section table bloat significantly (close to zero for intra-procedural re-ordering)

With full basic block sections, the object size bloat from section table outweighs the bloats from strtab and symtab. However, please note that this is only the object file sizes. In the final binary, after the reordering has taken place, the unwanted symbols (those that are contiguous to the main function) will be deleted (patch pending) and hence this bloats will not carry over to the final binary size. Thanks.

MaskRay added a comment.EditedDec 22 2020, 4:04 PM

.L prefixed symbols will be discarded by the linker in the default mode (none of --discard-none/--discard-locals/--discard-all is specified).
So if you use .L (called PrivateGlobalPrefix in MC), this will work without any linker change (if possible I would hope we just make use of existing conventions instead of adding more linker rules).
For the string __uniq and __part, I am fine with them and actually prefer them if you have measured that they don't cause too mush bloat. The names are clearer than other alternatives like unary coding and special code points (e.g. LLVM IR names make use of \1)

With full basic block sections, the object size bloat from section table outweighs the bloats from strtab and symtab.

sizeof(Elf64_Shdr) = 64. A C++ mangled symbol name can be longer than it, but I don't know the average length.

MaskRay added inline comments.Dec 22 2020, 4:06 PM
llvm/lib/CodeGen/MachineBasicBlock.cpp
77

Suffix = (Suffix + Twine(".__part.") + Twine(SectionID.Number)).str();

.L prefixed symbols will be discarded by the linker in the default mode (none of --discard-none/--discard-locals/--discard-all is specified).

Aren't these discarded by the assembler itself?

So if you use .L (called PrivateGlobalPrefix in MC), this will work without any linker change (if possible I would hope we just make use of existing conventions instead of adding more linker rules).

So there is some logic to deleting a basic block symbol. For instance, we will keep a symbol that is discontiguous with the main function as the representative symbol, does that make sense? We can only delete those symbols that end up contiguous with the main function.

For the string __uniq and __part, I am fine with them and actually prefer them if you have measured that they don't cause too mush bloat. The names are clearer than other alternatives like unary coding and special code points (e.g. LLVM IR names make use of \1)

Right, we tried unary encoding for our initial prototype and we didnt like the complicated naming.

The thing is full basic block sections will cause size bloats in several ways, especially section table overheads. strtab and symtab bloats is only one aspect of it. This is why we went with "=list" option for Propeller. Full basic block sections is the generic feature and is very useful for experimenting with various layouts but should be carefully used under size constrained environments.

With full basic block sections, the object size bloat from section table outweighs the bloats from strtab and symtab.

sizeof(Elf64_Shdr) = 64. A C++ mangled symbol name can be longer than it, but I don't know the average length.

tmsriram updated this revision to Diff 313447.Dec 22 2020, 4:25 PM
tmsriram marked an inline comment as done.

Address reviewer comments.

.L prefixed symbols will be discarded by the linker in the default mode (none of --discard-none/--discard-locals/--discard-all is specified).
So if you use .L (called PrivateGlobalPrefix in MC), this will work without any linker change (if possible I would hope we just make use of existing conventions instead of adding more linker rules).
For the string __uniq and __part, I am fine with them and actually prefer them if you have measured that they don't cause too mush bloat. The names are clearer than other alternatives like unary coding and special code points (e.g. LLVM IR names make use of \1)

With full basic block sections, the object size bloat from section table outweighs the bloats from strtab and symtab.

sizeof(Elf64_Shdr) = 64. A C++ mangled symbol name can be longer than it, but I don't know the average length.

This is a good point. We have looked at unary encoding / moving symbol mapping to separate sections. We are brainstorming this and we will keep you posted. Maybe there is a nice compressed representation we can build.

This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptDec 23 2020, 11:36 AM
Herald added a subscriber: cfe-commits. · View Herald Transcript