[PGO] PGOFuncName in LTO optimizations.

[xur]

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.

[mehdi_amini]

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

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

[davidxl]

include/llvm/ProfileData/InstrProf.h

161

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

lib/ProfileData/InstrProf.cpp

180

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

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]

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

252

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.

[davidxl]

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

2. For global functions in LTO (before internalization) -- add meta data to indicate it
3. for static functions in LTO mode, add a different meta to record their source module name (if this is not available later)

4. Enhance getPGOFuncName method to check the meta data, and pass right linkage etc to Function:getGlobalIdentifier

5. Add a new interface in InstrProfSymtab to map PGOName ('s MD5) to function's current new name
6. 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]

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]

include/llvm/ProfileData/InstrProf.h

156

doc

161

Remove

325

Doc

lib/ProfileData/InstrProf.cpp

89

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, "");

91

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.

[davidxl]

lib/ProfileData/InstrProf.cpp

91

have have --> have

91

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

111

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);

176

Ingore --> Ignore.

Explain this case.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

249

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]

lib/ProfileData/InstrProf.cpp

89

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]

lib/ProfileData/InstrProf.cpp

91

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]

lib/ProfileData/InstrProf.cpp

89

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]

lib/ProfileData/InstrProf.cpp

89

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

91

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"

[xur]

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

lib/ProfileData/InstrProf.cpp

89

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 patch that integrated the review comments from Mehdi and David.

[davidxl]

lib/ProfileData/InstrProf.cpp

91

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

93

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]

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

Thanks,

-Rong

[mehdi_amini]

LGTM on my side, thanks.

[davidxl]

lgtm with additional comment changes.

lib/ProfileData/InstrProf.cpp

95

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

109

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.

include/llvm/ProfileData/InstrProf.h

 /// Return the name of the profile runtime interface that overrides the default
 /// profile data file name.
 inline StringRef getInstrProfFileOverriderFuncName() {
   return "__llvm_profile_override_default_filename";
 }
 
 /// Return the modified name for function \c F suitable to be
 /// used the key for profile lookup.
 std::string getPGOFuncName(const Function &F,
                            uint64_t Version = INSTR_PROF_INDEX_VERSION);
 
+/// Return the modified name for function \c F suitable to be
+/// used the key for profile lookup in LTO compilation.
+std::string getPGOFuncNameInLTO(const Function &F);
+
 /// Return the modified name for a function suitable to be
 /// used the key for profile lookup. The function's original
 /// name is \c RawFuncName and has linkage of type \c Linkage.
 /// The function is defined in module \c FileName.
 std::string getPGOFuncName(StringRef RawFuncName,
                            GlobalValue::LinkageTypes Linkage,
                            StringRef FileName,
                            uint64_t Version = INSTR_PROF_INDEX_VERSION);
public:
   inline std::error_code create(StringRef D, uint64_t BaseAddr);
   /// \c NameStrings is a string composed of one of more sub-strings
   ///  encoded in the format described in \c collectPGOFuncNameStrings.
   /// This method is a wrapper to \c readPGOFuncNameStrings method.
   inline std::error_code create(StringRef NameStrings);
   /// A wrapper interface to populate the PGO symtab with functions
   /// decls from module \c M. This interface is used by transformation
   /// passes such as indirect function call promotion.
-  void create(const Module &M);
+  void create(const Module &M, bool InLTO = false);
   /// Create InstrProfSymtab from a set of names iteratable from
   /// \p IterRange. This interface is used by IndexedProfReader.
   template <typename NameIterRange> void create(const NameIterRange &IterRange);
   // If the symtab is created by a series of calls to \c addFuncName, \c
   // finalizeSymtab needs to be called before looking up function names.
   // This is required because the underlying map is a vector (for space
   // efficiency) which needs to be sorted.
   inline void finalizeSymtab();

lib/ProfileData/InstrProf.cpp

std::string getPGOFuncName(StringRef RawFuncName,
                            StringRef FileName,
                            uint64_t Version LLVM_ATTRIBUTE_UNUSED) {
   return Function::getGlobalIdentifier(RawFuncName, Linkage, FileName);
 }
 
 std::string getPGOFuncName(const Function &F, uint64_t Version) {
   return getPGOFuncName(F.getName(), F.getLinkage(), F.getParent()->getName(),
                         Version);
 }
 
+// Return the PGOFuncName when called in LTO optimization. LTO's
+// internalization privatizes many global linkage symbols into internal linkage.
+// This happens after value profile annotation so those internal linkage
+// function should have have a source prefix. However, we still need to
+// differentiate these symbols from the ones not from LTO's internalization:
+// In profile-use, we create a function meta-data if the PGOfuncName is
+// different from it's raw name. Use that name if it's available. Otherwise,
+// just strip off the source module prefix.
+std::string getPGOFuncNameInLTO(const Function &F) {
+  // 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();
+  }
+  // Strip out prefix from the the internalized symbols.
+  std::string PGOName = getPGOFuncName(F);
+  size_t S = PGOName.find_first_of(':');
+  if (S == std::string::npos)
+    return PGOName;
+  return PGOName.substr(S + 1);
+}
+
 StringRef getFuncNameWithoutPrefix(StringRef PGOFuncName, StringRef FileName) {
   if (FileName.empty())
     return PGOFuncName;
   // Drop the file name including ':'. See also getPGOFuncName.
   if (PGOFuncName.startswith(FileName))
     PGOFuncName = PGOFuncName.drop_front(FileName.size() + 1);
   return PGOFuncName;
 }
GlobalVariable *createPGOFuncNameVar(Module &M,
 
   return FuncNameVar;
 }
 
 GlobalVariable *createPGOFuncNameVar(Function &F, StringRef FuncName) {
   return createPGOFuncNameVar(*F.getParent(), F.getLinkage(), FuncName);
 }
 
-void InstrProfSymtab::create(const Module &M) {
-  for (const Function &F : M)
+void InstrProfSymtab::create(const Module &M, bool InLTO) {
+  for (const Function &F : M) {
+    // Function may not have a name. Ingore in this case.
+    if (!F.hasName())
+      continue;
+    if (InLTO)
+      addFuncName(getPGOFuncNameInLTO(F));
+    else
       addFuncName(getPGOFuncName(F));
+  }
 
   finalizeSymtab();
 }
 
 int collectPGOFuncNameStrings(const std::vector<std::string> &NameStrs,
                               bool doCompression, std::string &Result) {
   uint8_t Header[16], *P = Header;
   std::string UncompressedNameStrings =

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

MST.dumpEdges(dbgs(), Twine("Dump Function ") + FuncName + " Hash: " +
                               Twine(FunctionHash) + "\t" + Str);
   }
 
   FuncPGOInstrumentation(Function &Func, bool CreateGlobalVar = false,
                          BranchProbabilityInfo *BPI = nullptr,
                          BlockFrequencyInfo *BFI = nullptr)
       : F(Func), FunctionHash(0), MST(F, BPI, BFI) {
     FuncName = getPGOFuncName(F);
+    if (FuncName != Func.getName()) {
+      LLVMContext &C = F.getContext();
+      MDNode *N = MDNode::get(C, MDString::get(C, FuncName.c_str()));
+      F.setMetadata("PGOFuncName", N);
+    }
     computeCFGHash();
     DEBUG(dumpInfo("after CFGMST"));
 
     NumOfPGOBB += MST.BBInfos.size();
     for (auto &E : MST.AllEdges) {
       if (E->Removed)
         continue;
       NumOfPGOEdge++;