Page MenuHomePhabricator

Unique Names for Functions with Internal Linkage
Needs ReviewPublic

Authored by tmsriram on Jan 23 2020, 4:43 PM.

Details

Summary

This is a standalone patch and this would help Propeller do a better job of code layout as it can accurately attribute the profiles to the right internal linkage function.

This also helps SampledFDO/AutoFDO correctly associate sampled profiles to the right internal function. Currently, if there is more than one internal symbol foo, their profiles are aggregated by SampledFDO.

This patch adds a new clang option, -funique-internal-funcnames, to generate unique names for functions with internal linkage. This patch appends the md5 hash of the module name to the function symbol as a best effort to generate a unique name for symbols with internal linkage.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
MaskRay added inline comments.Jan 23 2020, 11:02 PM
clang/lib/CodeGen/CodeGenModule.cpp
1174

std::string llvm::getUniqueModuleId(Module *M) {

What is the second parameter?

What is the rationale that InternalLinkage is picked here?

clang/lib/Frontend/CompilerInvocation.cpp
957

Just Args.hasArg(OPT_funique_internal_funcnames).

-fno-* is handled in clangDriver. CC1 does not need to know -fno-* if it defaults to false.

tmsriram marked an inline comment as done.Jan 24 2020, 9:39 AM
tmsriram added inline comments.
clang/lib/CodeGen/CodeGenModule.cpp
1174

This change to LLVM, https://reviews.llvm.org/D73310, contains the modifications to getUniqueModuleId to use the Module Identifier also in the hash. We found that when "-z muldefs" are used or when there are no globals defined in a module, a unique hash could not be generated. Using the full module name allows for a unique identifier in these cases. The second parameter basically allows use of module name and we did not force this to keep the existing usage as it is.

Internal Linkage is picked because there could be multiple functions of the same name with internal linkage in the final binary. So, associating sampled profile symbols to the right function name becomes a problem. Further, if multiple functions of the same name are hot, their profiles are aggregated affecting the optimization itself. So, a unique name for internal linkage functions will clearly disambiguate the profile information.

tmsriram marked an inline comment as done.Jan 24 2020, 10:08 AM
tmsriram added inline comments.
clang/lib/Frontend/CompilerInvocation.cpp
957

Are you suggesting I remove the -fno-* flag? The -fno-* is useful if -funique-internal-funcnames came added to a Makefile ,for example, and this needs to be disabled. This is similar to say -ffunction-sections. Please clarify. Thanks.

tmsriram updated this revision to Diff 240249.Jan 24 2020, 11:00 AM

Use Hash of Module's source file name directly.

tmsriram updated this revision to Diff 240253.Jan 24 2020, 11:09 AM

Remove an unnecessary header file inclusion.

pcc added inline comments.Jan 24 2020, 2:36 PM
clang/lib/CodeGen/CodeGenModule.cpp
1181

Why ".$" and not just "."?

tmsriram marked an inline comment as done.Jan 24 2020, 2:47 PM
tmsriram added inline comments.
clang/lib/CodeGen/CodeGenModule.cpp
1181

I just wanted to keep it consistent with what getUniqueModuleId does with the Md5 hash. I can remove it.

MaskRay added inline comments.Jan 24 2020, 2:50 PM
clang/include/clang/Driver/Options.td
1982

, Flags<[CC1Option]> can be deleted.

clang/lib/CodeGen/CodeGenModule.cpp
1173

Is this-> a must?

1181

Agreed. "." seems sufficient.

1182

MangledName += UniqueSuffix;

clang/lib/Frontend/CompilerInvocation.cpp
957

This file is about the cc1 option, which is not expected to be used by a user.

The driver has handled -fno-, so we don't have to repeat it here. -fmerge-functions and -fno-jump-tables are good examples that we don't have to add both -ffoo and -fno-foo to cc1 options.

tmsriram updated this revision to Diff 240312.Jan 24 2020, 3:32 PM

Minor changes. Remove CC1option on "-fno", Remove "$" from unique suffix.

tmsriram marked 8 inline comments as done.Jan 24 2020, 3:32 PM
MaskRay added a reviewer: wmi.Jan 24 2020, 3:41 PM

The code change seems fine, but the test requires some changes. I haven't followed Propeller development, but hope someone with profile experience can confirm InternalLinkage is the only linkage we need to care about (otherwise the option will be a misnomer if we ever extend it) and check whether this feature is useful on its own. Does it improve profile precision?

clang/test/CodeGen/unique_internal_funcnames.c
1 ↗(On Diff #240312)

The convention is file-name.c , rather than file_name.c . The latter exists, but is a minority.

2 ↗(On Diff #240312)

There should be two tests:

  • one in test/Driver/funique-internal-funcnames.c, for -funique-internal-funcnames -fno-unique-internal-funcnames testing
  • the other one should stay here (test/CodeGen), but should be a -S -emit-llvm test for IR output.

We don't normally do driver --> assembly testing.

3 ↗(On Diff #240312)

-target x86_64 should just work (generic ELF). This feature is not tied to linux-gnu.

The code change seems fine, but the test requires some changes. I haven't followed Propeller development, but hope someone with profile experience can confirm InternalLinkage is the only linkage we need to care about (otherwise the option will be a misnomer if we ever extend it) and check whether this feature is useful on its own. Does it improve profile precision?

I can comment on the usefulness aspect: we had an earlier prototype of this, which we tried on a real-world application benchmark. The binary had ~10% of local statics exhibiting duplicate names. Ensuring unique names led to observable differences in the AFDO file (i.e. some of those functions had profiles that, before, were lost for one of the duplicates, and now were correctly attributed to the different functions), and a measurable performance improvement.

mtrofin added inline comments.Jan 24 2020, 4:28 PM
clang/lib/CodeGen/CodeGenModule.cpp
1175

Just a thought: md5 is a non-bijective transformation, afaik. How about using base64 encoding, with the caveat that we replace + with $ and / with _ (so it results in a valid name), and discard padding =

The value being, one can copy/paste that identifier, do the trivial conversion back to base64 ($->+, _->/) and get the module name. Useful when debugging, for example.

The code change seems fine, but the test requires some changes. I haven't followed Propeller development, but hope someone with profile experience can confirm InternalLinkage is the only linkage we need to care about (otherwise the option will be a misnomer if we ever extend it) and check whether this feature is useful on its own. Does it improve profile precision?

I can comment on the usefulness aspect: we had an earlier prototype of this, which we tried on a real-world application benchmark. The binary had ~10% of local statics exhibiting duplicate names. Ensuring unique names led to observable differences in the AFDO file (i.e. some of those functions had profiles that, before, were lost for one of the duplicates, and now were correctly attributed to the different functions), and a measurable performance improvement.

Thanks! Do you happen to have numbers about the code size increase? Every InternalLinkage function will have a longer time. They may take a significant portion of the string table (.strtab) size. If you strip .strtab, the profiling precision will be lowered to the situation before.

The code change seems fine, but the test requires some changes. I haven't followed Propeller development, but hope someone with profile experience can confirm InternalLinkage is the only linkage we need to care about (otherwise the option will be a misnomer if we ever extend it) and check whether this feature is useful on its own. Does it improve profile precision?

I can comment on the usefulness aspect: we had an earlier prototype of this, which we tried on a real-world application benchmark. The binary had ~10% of local statics exhibiting duplicate names. Ensuring unique names led to observable differences in the AFDO file (i.e. some of those functions had profiles that, before, were lost for one of the duplicates, and now were correctly attributed to the different functions), and a measurable performance improvement.

Thanks! Do you happen to have numbers about the code size increase? Every InternalLinkage function will have a longer time. They may take a significant portion of the string table (.strtab) size. If you strip .strtab, the profiling precision will be lowered to the situation before.

I assume you mean binary size increase. It was 0.8% larger in my case.

tmsriram updated this revision to Diff 251220.Wed, Mar 18, 4:55 PM
tmsriram marked 5 inline comments as done.

Address Reviewer comments:

  • Add new driver test.
  • Fix existing test to only check for code output.
clang/lib/CodeGen/CodeGenModule.cpp
1175

I dont think getting the module name back from the hash is super useful given that we can always inspect this symbol in gdb for source info.

tmsriram edited the summary of this revision. (Show Details)Wed, Mar 18, 5:14 PM
MaskRay added inline comments.Wed, Mar 18, 5:29 PM
clang/lib/Frontend/CompilerInvocation.cpp
961

Delete excess empty line.

clang/test/Driver/funique-internal-funcnames.c
3 ↗(On Diff #251220)

CHECK-OPT: "-funique-internal-funcnames"

tmsriram updated this revision to Diff 251409.Thu, Mar 19, 10:13 AM
tmsriram marked 2 inline comments as done.

Address reviewer comments. Fix test and delete blank line.

MaskRay added inline comments.Thu, Mar 19, 10:27 AM
clang/test/CodeGen/unique-internal-funcnames.c
3 ↗(On Diff #251409)

You can hardly find any .c -> .s test in clang/test. We mostly do .c -> .ll testing. .ll -> .s are in llvm/test/CodeGen.

lebedev.ri added inline comments.
clang/lib/CodeGen/CodeGenModule.cpp
1170

maybe
identifier as this is a best-effort solution

clang/test/CodeGen/unique-internal-funcnames.c
16 ↗(On Diff #251409)

What does getModule().getSourceFileName() contain?
The full path to the source file, or just the source file basename?
If latter, maybe check the full name?

As far as I understand, this is not a propeller specific patch, but it fixes a general problem in AFDO as well. Perhaps change the summary to reflect that?

davidxl added inline comments.Thu, Mar 19, 12:01 PM
clang/lib/CodeGen/CodeGenModule.cpp
1170

Address review comment here.

1176

Source filenames are not guaranteed to be unique, or it does contain the path as well?

clang/test/CodeGen/unique-internal-funcnames.c
3 ↗(On Diff #251409)

Is this convention documented somewhere? Any concerns of producing .s?

tmsriram marked an inline comment as done.Thu, Mar 19, 12:48 PM
tmsriram added inline comments.
clang/test/CodeGen/unique-internal-funcnames.c
3 ↗(On Diff #251409)

There are more than 200 tests in clang that do -S from .c -> .s and tens of tests in CodeGen alone. I can change this to .ll but curious where this "hardly any" comes from?

tmsriram updated this revision to Diff 251469.Thu, Mar 19, 1:55 PM
tmsriram marked 4 inline comments as done.

Address reviewer comments.

  • reword comment
  • rewrite test to use -emit-llvm
tmsriram edited the summary of this revision. (Show Details)Thu, Mar 19, 1:57 PM
tmsriram added inline comments.
clang/test/CodeGen/unique-internal-funcnames.c
16 ↗(On Diff #251409)

It contains the full path.

rnk added a comment.Thu, Mar 19, 1:57 PM

I guess my initial reaction is that it is disappointing that downstream consumers can't cope with non-unique symbol names (What is the point of having internal linkage if we can't rely on it?), but given @mtrofin's input about AFDO, this seems like it may be a practical solution. I can think of at least two other cases where I have wanted similar functionality, the first being unique names for CodeView types in anonymous namespaces, the second being Jumbo support, producing one object from two .cpp source inputs.

To handle the case for type identifiers, we came up with this solution:
https://github.com/llvm/llvm-project/blob/master/clang/lib/AST/MicrosoftMangle.cpp#L401
Your solution is pretty similar.

I haven't followed Propeller development, but hope someone with profile experience can confirm InternalLinkage is the only linkage we need to care about (otherwise the option will be a misnomer if we ever extend it) and check whether this feature is useful on its own.

There is one other "local" linkage type, private linkage, which I believe corresponds with temporary assembler labels (.L*) that don't survive into the object file symbol table. I think the main use case for private globals is to save on symbol table size, so if the user passes this flag, it seems reasonable to upgrade the linkage to internal, and assign a unique name.

There is also the case of unnamed globals, which I think are private. I don't think clang ever generates these, so they are not very interesting.

I grepped the clang/test subdirectory for 'define.*private', and it seems there are no tests for private functions, so I doubt clang ever emits them.


At a higher level, should this just be an IR pass that clang adds into the pipeline when the flag is set? It should be safe to rename internal functions and give private functions internal linkage. It would be less invasive to clang and have better separation of concerns. As written, this is based on the source filename on the module, which is accessible from IR. The only reason I can think of against this is that the debug info might refer to the function linkage name, but maybe that is calculated later during codegen.

clang/lib/CodeGen/CodeGenModule.cpp
1077

We seem to be defeating NRVO with our "clever" small string type. :(

1166

There are several other callers of getMangledNameImpl. Should they also use this suffix? They mostly have to do with function multiversioning. Those seem like they could be internal and need this treatment.

1172

isa would be more idiomatic than testing dyn_cast results for truth.

1176

It appears to contain the path as the compiler receives it on the command line. However, it is possible to design a build where this string is not unique:

cd foo
clang -c name_conflict.c 
cd ../bar
clang -c name_conflict.c
clang foo/name_conflict.o bar/name_conflict.o

I don't think we should try to handle this case, but we should document the limitation somewhere. Some build systems do operate changing the working directory as they go.

Can you add some to the clang/docs/UsersManual.rst file? I'd expect it to show up here:
https://clang.llvm.org/docs/UsersManual.html#command-line-options

You can elaborate that the unique names are calculated using the source path passed to the compiler, and in a build system where that is not unique, the function names may not be unique.


I have also used this construct in the past for building single-file ABI compatibility test cases:

// foo.cpp
#ifdef PART1
// ...
#elif defined(PART2)
// ...
#endif

$ cc -c foo.cpp -DPART1
$ cc -c foo.cpp -DPART2
1180

I think it would be preferable to calculate the source filename MD5 hash once, when CodeGenModule is constructed, stringify it, and then use that every time we mangle a name.

clang/test/CodeGen/unique-internal-funcnames.c
3 ↗(On Diff #251409)

I can't specifically find documentation for this convention, but it is generally understood that every feature should have targeted unit tests that exercise the minimum amount of functionality. In this case, that means using %clang_cc1 -emit-llvm -triple NNN and checking the IR.

davidxl added inline comments.Thu, Mar 19, 2:47 PM
clang/lib/CodeGen/CodeGenModule.cpp
1176

yes, the first example was the scenario I meant. I agree name conflict due that case should be really rare. If yes, we can always use content based uniqueid -- by appending llvm::getUniqueModuleId -- but that is probably overkill.

hubert.reinterpretcast added inline comments.
clang/lib/CodeGen/CodeGenModule.cpp
1176

yes, the first example was the scenario I meant. I agree name conflict due that case should be really rare.

Except for projects where it is the rule and not the exception. One pattern where this occurs is when each subdirectory implements one class and there are multiple classes that implement the same interface. In each directory, the implementation of each class is separated into files by grouping methods of the class. The set of filenames in one such directory may well be the same as the set in another.

MaskRay added inline comments.Thu, Mar 19, 3:23 PM
clang/test/CodeGen/unique-internal-funcnames.c
3 ↗(On Diff #251409)

Not that many -S .c -> .s tests (rg '%clang.* -S ' | egrep -v '[-]###|emit-llvm|-verify' | awk -F: '{print $1}' | sort -u | wc -l). Many are about -emit-llvm -### -verify or misused -v. They do not need to produce assembly.

clang/test/Driver/funique-internal-funcnames.c
4 ↗(On Diff #251469)

This negative pattern needs to be changed as well.

tmsriram marked 4 inline comments as done.Thu, Mar 19, 3:36 PM
tmsriram added inline comments.
clang/lib/CodeGen/CodeGenModule.cpp
1176

I am not sure much can be done here other than try using getUniqueModuleId. Just to be clear, even if the file names are the same, the actual conflict happens only when the "make " is done from the leaf directory. Doing:

cc a/name_conflict.cpp -c
cc b/name_conflict.cpp -c

should still produce unique names.

clang/lib/CodeGen/CodeGenModule.cpp
1176

Understood. I do happen to have been working on a project that does the whole $(MAKE) -C a/ thing with such a project layout. Content based hashing is unfortunate for other reasons: The hash would be unstable during the course of maintenance on the codebase. I guess the limitation is okay for the intended use case of the patch.

tmsriram updated this revision to Diff 251868.Sat, Mar 21, 5:16 PM
tmsriram marked 11 inline comments as done.

Address @rnk comments:

  • Moved implementation to getMangledNameImpl to catch multi-versioned symbols and internal linkage globals
  • Moved hash computation to consrtuctor
  • Renamed option to -funique-internal-linkage-names
  • Add documentation to UsersManual.rst and verified with html conversion
  • Added tests for MV symbols and static globals, is there anything else? I am not too familiar with internal/private symbol possibilites
tmsriram added inline comments.Sat, Mar 21, 5:17 PM
clang/lib/CodeGen/CodeGenModule.cpp
1166

I moved the suffix append to getMangledNameImpl. Other mangled name manipulations are also done here. Added tests for multiversioned internal linkage symbols.

1176

Acknowledged.

davidxl added inline comments.Wed, Mar 25, 11:01 AM
clang/docs/UsersManual.rst
1683

Is it necessary to document 'MD5 hash' as it is an implementation detail? Perhaps just 'the name hash'

1689

if the two modules contain symbols with the same private linkage name.

clang/lib/CodeGen/CodeGenModule.cpp
1075

is the first check redundant now?

tmsriram updated this revision to Diff 252688.Wed, Mar 25, 3:15 PM
tmsriram marked 4 inline comments as done.

Changes to description of flag, remove redundant check.

In D73307#1932131, @rnk wrote:

At a higher level, should this just be an IR pass that clang adds into the pipeline when the flag is set? It should be safe to rename internal functions and give private functions internal linkage. It would be less invasive to clang and have better separation of concerns. As written, this is based on the source filename on the module, which is accessible from IR. The only reason I can think of against this is that the debug info might refer to the function linkage name, but maybe that is calculated later during codegen.

I second this suggestion. clang/lib/CodeGen/BackendUtil.cpp EmitAssemblyHelper::EmitAssemblyWithNewPassManager ModulePassManager may be a more appropriate place for this feature. There are examples from both sides:

  • clang frontend: #pragma redefine_extname
  • middle end IR->IR: the old pass manager has a feature -frewrite-map-file, which does a similar thing but is implemented as an IR transformation.
In D73307#1932131, @rnk wrote:

At a higher level, should this just be an IR pass that clang adds into the pipeline when the flag is set? It should be safe to rename internal functions and give private functions internal linkage. It would be less invasive to clang and have better separation of concerns. As written, this is based on the source filename on the module, which is accessible from IR. The only reason I can think of against this is that the debug info might refer to the function linkage name, but maybe that is calculated later during codegen.

I second this suggestion. clang/lib/CodeGen/BackendUtil.cpp EmitAssemblyHelper::EmitAssemblyWithNewPassManager ModulePassManager may be a more appropriate place for this feature. There are examples from both sides:

@rnk getMangledNameImpl for example adds multi-versioning suffixes, "regcall3_" and "device_stub". Adding the hash is just so simple. Is a pass really needed? If so, I should parse ".<target>" suffixed Multi-versioining names and insert the hash in between as the demangling looks better?

  • clang frontend: #pragma redefine_extname
  • middle end IR->IR: the old pass manager has a feature -frewrite-map-file, which does a similar thing but is implemented as an IR transformation.
clang/lib/CodeGen/CodeGenModule.cpp
1075

Good catch, converted to an assert.

In D73307#1932131, @rnk wrote:

At a higher level, should this just be an IR pass that clang adds into the pipeline when the flag is set? It should be safe to rename internal functions and give private functions internal linkage. It would be less invasive to clang and have better separation of concerns. As written, this is based on the source filename on the module, which is accessible from IR. The only reason I can think of against this is that the debug info might refer to the function linkage name, but maybe that is calculated later during codegen.

I second this suggestion. clang/lib/CodeGen/BackendUtil.cpp EmitAssemblyHelper::EmitAssemblyWithNewPassManager ModulePassManager may be a more appropriate place for this feature. There are examples from both sides:

@rnk getMangledNameImpl for example adds multi-versioning suffixes, "regcall3_" and "device_stub". Adding the hash is just so simple. Is a pass really needed? If so, I should parse ".<target>" suffixed Multi-versioining names and insert the hash in between as the demangling looks better?

  • clang frontend: #pragma redefine_extname
  • middle end IR->IR: the old pass manager has a feature -frewrite-map-file, which does a similar thing but is implemented as an IR transformation.

There may be some other interactions @rnk noticed. I am happy with either way.

clang/test/CodeGen/unique-internal-linkage-names.cpp
5

Might be worth adding a few other internal linkage names.

  • an object in an unnamed namespace
  • an extern "C" static function
  • a function-local static variable
  • label: &&label

Hope @mtrofin and @davidxl can clarify what internal names may benefit AFDO and we can add such internal names specifically.

MaskRay added inline comments.Mon, Mar 30, 4:12 PM
clang/lib/CodeGen/CodeGenModule.cpp
1165

Delete this unrelated cosmetic change.

wmi added inline comments.Mon, Mar 30, 5:46 PM
clang/test/CodeGen/unique-internal-linkage-names.cpp
5

Only internal functions matter for AFDO. Other types of internal names are irrelevant.

tmsriram marked an inline comment as done.Mon, Mar 30, 6:08 PM
tmsriram added inline comments.
clang/test/CodeGen/unique-internal-linkage-names.cpp
5

extern "C" static is not very useful as the name is not exposed outside the object file. C++ compiler will still mangle the name. for eg:

a.cpp

extern "C" {

static int bar() {
  return 0;
}

}

int foo() {

printf("%p\n", bar);

}

$ nm a.o
0000000000000040 t _ZL3barv

Also, for label: &&label, it is not preserved in the symbol table as a .L<name> is used which is deleted by the assembler. I can throw a asm("") directive but that will bypass the front-end. Is there anyway to preserve this?

I can add the rest of the cases.