[PGO] PGOFuncName in LTO optimizations.
ClosedPublic

Authored by xur on Mar 4 2016, 2:09 PM.

Details

Summary

PGOFuncNames are used as the key to retrieve the Function definition from the MD5 stored in the profile: (1) We use the InstrProfSymtab to map the MD5 to the PGOFuncName. (2) We use another map to find the Function definition using PGOFuncName. With the above two steps, we can find the direct-call target function in the profile.

This assumes the PGOFuncName is consistent through the above steps.

LTO's internalization privatizes many global linkage symbols into internal linkage. And for the internal functions, we prefix the source module name to the PGOFuncName.

An example:
foo.c:

static int foo();  // user specified internal function.
int bar();  // internalized
int goo();  // remains global

in pgo-gen/pgo-use/vp-annotation time, the PGOFuncName is

foo() --> foo.c:foo
bar() --> bar
goo() --> goo

in lto optimization, after internalization:

foo() --> ld-temp.o:foo
bar() --> ld-temp.o:bar
goo() --> goo

So if the indirect-call promotion is call in lto optimizations, we cannot find the target for foo() and bar().

We have to do the indirect-call promotion in combined module as many of the targets are non intra-modules. So we have to work around this. Here are a few solutions that we have thought of:
(1) Perform indirect-call promotion before internalization.
It works but the internalization is tightly couple into the lto framework. The structure is bad.

(2) Rename the internal linkage function physically into PGOFuncName.
This also works. But this might affect the debug.

(3) Record the source module name in linker plugin and use it to reconstruct the PGOFuncName for
internal linage not from internalization. We also need to record the list of the symbol got
internalized (could reuse some maps in lto codegen). ThinLTO is going to use this method.

(4) In profile-use, create a function meta-data if the PGOFuncName is different from its raw name. In LTO optimization, use that name if it's available. Otherwise, just strip off the source module prefix.

I choose (4) over (3) because of its simplicity. It uses more memory than (3). But I don't expect tons of user defined internal functions. If this becomes a real issue, we can switch to (3).

Note this is the issue for both Clang value profile annotaion and llvm value profile annotation. The patch only changes the llvm vaule profiling. If this is acceptable, I will change the Clang one later.

Diff Detail

Repository
rL LLVM
xur retitled this revision from to [PGO] PGOFuncName in LTO optimizations. .Mar 4 2016, 2:09 PM
xur updated this object.
xur added reviewers: davidxl, silvas, mehdi_amini.
xur added a subscriber: xur.

There is still something I don't get: if you insert the instrumentation during LTO at the same place (i.e. after internalization), where does the mismatch in names come from?

lib/ProfileData/InstrProf.cpp
111 ↗(On Diff #49852)

std::string PGOName = getPGOFuncName (F.getName(), GlobalValue::ExternalLinkage, "");

davidxl added inline comments.Mar 4 2016, 2:43 PM
include/llvm/ProfileData/InstrProf.h
161 ↗(On Diff #49852)

Can you merge this interface with the above one -- but with an optional argument?

lib/ProfileData/InstrProf.cpp
180 ↗(On Diff #49852)

See my comment about changing meta data. Here you can simply map the meta-data/MD5 to Function's real name.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp
252 ↗(On Diff #49852)

String meta data is expensive. I think you should directly store the MD5 sum of the PGOFuncName as the meta data.

In InstrProfSymtab::create(Module&) method, if the meta data exists, map the stored MD5 sum to the new internalized name -- of course you will need a new addFunctionName interface in the symtab.

Or you can even just store a boolean to indicate it is internalized. Later the PGO code can the right thing (unstripping the LTO name prefix and do not add the static function name prefix when computing PGO name)

xur marked an inline comment as done.Mar 4 2016, 2:58 PM
xur added inline comments.
lib/Transforms/Instrumentation/PGOInstrumentation.cpp
252 ↗(On Diff #49852)

If I store MD5, I can build the map b/w function define and MD5 directly, without using symtab. But we need to expose the implementation details of using MD5. Is this good?

As to mark the internalized symbols. Yes it's also doable. But here is trade off. In spec I tested, we have much more internalized symbols than originally internal symbols.

Here is the cleanup I think is the right way to go:

  1. There is no need introduce a new internface getPGOFuncNameInLTO -- existing getPGOFuncName should check meta data always and uses it if exists
  1. For global functions in LTO (before internalization) -- add meta data to indicate it
  2. for static functions in LTO mode, add a different meta to record their source module name (if this is not available later)
  1. Enhance getPGOFuncName method to check the meta data, and pass right linkage etc to Function:getGlobalIdentifier
  1. Add a new interface in InstrProfSymtab to map PGOName ('s MD5) to function's current new name
  2. In InstrProfSymtab::create(Module &) method, use 5) to map PGOName' sMD5 to real function name.

With these change, there is no need to create a separate map in IC promotion transformation pass.

xur updated this revision to Diff 51687.Mar 25 2016, 2:43 PM
xur marked an inline comment as done.

This revised patch addresses David's review comment. This patch still assumes the Indirect-call-promotion (ICP) is after LTO internalization.

If we move ICP before internalization, aside from the interaction with global devirtuation, I still need to get the source module name to reconstruct the PGOFuncName for the internal functions. (this can be though using annotation, or a similar way as ThinLTO). If people think that is the way to go, I will write the patch.

mehdi_amini requested changes to this revision.Mar 25 2016, 3:03 PM
mehdi_amini added inline comments.
include/llvm/ProfileData/InstrProf.h
156 ↗(On Diff #51687)

doc

161 ↗(On Diff #51687)

Remove

335 ↗(On Diff #51687)

Doc

lib/ProfileData/InstrProf.cpp
89 ↗(On Diff #51687)

This is not clear to me, I forgot all the detail since last update to this patch, but I was expecting that internal functions would be "source-prefixed". The text is saying the opposite.

114 ↗(On Diff #51687)

I don't like useless string manipulation in general, and you didn't address my previous comment about that:

return getPGOFuncName (F.getName(), GlobalValue::ExternalLinkage, "")

i.e.

std::string getPGOFuncName(const Function &F, bool InLTO, uint64_t Version) {
  if (!InLTO) 
    return  getPGOFuncName(F.getName(), F.getLinkage(), F.getParent()->getName(), Version);

  // First check if these is a metadata.
  MDNode *MD = F.getMetadata("PGOFuncName");
  if (MD != nullptr) {
    StringRef S = cast<MDString>(MD->getOperand(0))->getString();
    return S.str();
  }

  // No metadata, it was originally a global that has been internalized
  return getPGOFuncName (F.getName(), GlobalValue::ExternalLinkage, "");
This revision now requires changes to proceed.Mar 25 2016, 3:03 PM
davidxl added inline comments.Mar 25 2016, 3:49 PM
lib/ProfileData/InstrProf.cpp
89 ↗(On Diff #51687)

have have --> have

89 ↗(On Diff #51687)

The original internal function's names are not source prefixed, their PGOName are.

109 ↗(On Diff #51687)

I think it is not right to do this. I think we should only record the PGOName meta data when one of the following changes:

  1. function name or
  2. linkage changes

This applies to privatized global and promoted static function (in thinLTO), or static function with appended sequence number.

Unchanged static function should not need the meta data.

With that, I think we don't need to use the InLTO flag at all:

// First check if these is a metadata.
MDNode *MD = F.getMetadata("PGOFuncName");
if (MD != nullptr) {
  StringRef S = cast<MDString>(MD->getOperand(0))->getString();
  return S.str();
}
else 
  return  getPGOFuncName(F.getName(), F.getLinkage(), F.getParent()->getName(), Version);
179 ↗(On Diff #51687)

Ingore --> Ignore.

Explain this case.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp
257 ↗(On Diff #51687)

You don't need to do this for prof-gen build, but just prof-use.

Also see previous comment -- why not do this where privatization happens?

davidxl added inline comments.Mar 25 2016, 3:57 PM
lib/ProfileData/InstrProf.cpp
114 ↗(On Diff #51687)

Your version almost works assuming all original private/internal functions have PGOFuncName metadata. It is 'almost' because F's name has been changed (via privitization), so the following still needs to strip the prefix from F.getName() before calling getPGOFuncName.

// No metadata, it was originally a global that has been internalized

return getPGOFuncName (F.getName(), GlobalValue::ExternalLinkage, "");
mehdi_amini added inline comments.Mar 25 2016, 3:58 PM
lib/ProfileData/InstrProf.cpp
89 ↗(On Diff #51687)

Sure, we're talking about the PGOName (isn't there a missing refactoring with ThinLTO-introduced getGlobalIdentifier()?).

The thing is that the text is still wrong as I read it:

"LTO's internalization privatizes many global linkage" <- this is about symbols whose PGOName should not be prefixed
"...so those internal linkage function should have have a source prefix" <- this is saying the opposite.

mehdi_amini added inline comments.Mar 25 2016, 4:02 PM
lib/ProfileData/InstrProf.cpp
114 ↗(On Diff #51687)

I lack context about the PGO flow to understand.
Do you have a pointer where I can see what you refer to as " F's name has been changed (via privatization)"?

davidxl added inline comments.Mar 25 2016, 4:30 PM
lib/ProfileData/InstrProf.cpp
89 ↗(On Diff #51687)

getGlobalIdentifier was originally from PGO code. This reminds me we need to document this function to make sure its behavior is not changed accidentally -- which will break PGO profile lookup (for older profiles). vsk is adding some test coverage for that.

Right -- the comment should say that 'These internal linkage functions should not have source prefix"

114 ↗(On Diff #51687)

A global function with name 'foo' becomes 'ld-temp.o:foo' after privatization?

xur marked 4 inline comments as done.Mar 29 2016, 3:56 PM

I will send a new patch based on the reviews soon.

lib/ProfileData/InstrProf.cpp
114 ↗(On Diff #51687)

I think joker.eph version works. I don't think LTO's internalization will physically change the variable's name -- it's only a likage change.

David's suggested version, if I understand correctly, will insert meta-data for internalized functions also. This would save the InLTO flag, but this create a lot more metadata.

xur updated this revision to Diff 52007.Mar 29 2016, 4:39 PM

Updated patch that integrated the review comments from Mehdi and David.

davidxl added inline comments.Mar 30 2016, 9:48 AM
lib/ProfileData/InstrProf.cpp
89 ↗(On Diff #52007)

so these internal .. ---> but those internal ...

91 ↗(On Diff #52007)

Change this paragraph to something like:

To differentiate compiler generated internal symbols from original ones, PGOFuncName meta data are created and attached to the original internal symbols. If a symbol does not have the meta, its original linkage must be non-internal.

xur updated this revision to Diff 52086.Mar 30 2016, 10:11 AM

Fix the comments suggested by David -- it does explain things clearer.

Thanks,

-Rong

LGTM on my side, thanks.

davidxl accepted this revision.Mar 30 2016, 10:19 AM

lgtm with additional comment changes.

lib/ProfileData/InstrProf.cpp
93 ↗(On Diff #52086)

attached to the original internal symbols in the value profile annotation step (PGOUseFunc::annotateIndirectCallSites).

107 ↗(On Diff #52086)

This is not precise. It should be:

If there is no meta data, the function must be a global before the value profile annotation pass. Its current linkage may be internal if it is internalized in LTO mode.

This revision was automatically updated to reflect the committed changes.