[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 ↗

(On Diff #49852)

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

[davidxl]

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]

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.

[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 ↗

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

[davidxl]

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]

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]

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]

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]

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]

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

[davidxl]

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]

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

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.

llvm/trunk/include/llvm/ProfileData/InstrProf.h

 inline StringRef getInstrProfFileOverriderFuncName() {
   return "__llvm_profile_override_default_filename";
 }
 
 /// Return the marker used to separate PGO names during serialization.
 inline StringRef getInstrProfNameSeparator() { return "\01"; }
 
 /// Return the modified name for function \c F suitable to be
-/// used the key for profile lookup.
-std::string getPGOFuncName(const Function &F,
+/// used the key for profile lookup. Variable \c InLTO indicates if this
+/// is called in LTO optimization passes.
+std::string getPGOFuncName(const Function &F, bool InLTO = false,
                            uint64_t Version = INSTR_PROF_INDEX_VERSION);
 
 /// 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,

 
 private:
   StringRef Data;
   uint64_t Address;
   // Unique name strings.
   StringSet<> NameTab;
   // A map from MD5 keys to function name strings.
   std::vector<std::pair<uint64_t, StringRef>> MD5NameMap;
+  // A map from MD5 keys to function define. We only populate this map
+  // when build the Symtab from a Module.
+  std::vector<std::pair<uint64_t, Function *>> MD5FuncMap;
   // A map from function runtime address to function name MD5 hash.
   // This map is only populated and used by raw instr profile reader.
   AddrHashMap AddrToMD5Map;
 
 public:
   InstrProfSymtab()
-      : Data(), Address(0), NameTab(), MD5NameMap(), AddrToMD5Map() {}
+      : Data(), Address(0), NameTab(), MD5NameMap(), MD5FuncMap(),
+      AddrToMD5Map() {}
 
   /// Create InstrProfSymtab from an object file section which
   /// contains function PGO names. When section may contain raw
   /// string data or string data in compressed form. This method
   /// only initialize the symtab with reference to the data and
   /// the section base address. The decompression will be delayed
   /// until before it is used. See also \c create(StringRef) method.
   std::error_code create(object::SectionRef &Section);
   /// This interface is used by reader of CoverageMapping test
   /// format.
   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);
+  /// passes such as indirect function call promotion. Variable \c InLTO
+  /// indicates if this is called from LTO optimization passes.
+  void create(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();
public:
   AddrHashMap &getAddrHashMap() { return AddrToMD5Map; }
   /// Return function's PGO name from the function name's symbol
   /// address in the object file. If an error occurs, return
   /// an empty string.
   StringRef getFuncName(uint64_t FuncNameAddress, size_t NameSize);
   /// Return function's PGO name from the name's md5 hash value.
   /// If not found, return an empty string.
   inline StringRef getFuncName(uint64_t FuncMD5Hash);
+  /// Return function from the name's md5 hash. Return nullptr if not found.
+  inline Function *getFunction(uint64_t FuncMD5Hash);
   /// Return the function's original assembly name by stripping off
   /// the prefix attached (to symbols with priviate linkage). For
   /// global functions, it returns the same string as getFuncName.
   inline StringRef getOrigFuncName(uint64_t FuncMD5Hash);
   /// Return the name section data.
   inline StringRef getNameData() const { return Data; }
 };
 
void InstrProfSymtab::create(const NameIterRange &IterRange) {
   for (auto Name : IterRange)
     addFuncName(Name);
 
   finalizeSymtab();
 }
 
 void InstrProfSymtab::finalizeSymtab() {
   std::sort(MD5NameMap.begin(), MD5NameMap.end(), less_first());
+  std::sort(MD5FuncMap.begin(), MD5FuncMap.end(), less_first());
   std::sort(AddrToMD5Map.begin(), AddrToMD5Map.end(), less_first());
   AddrToMD5Map.erase(std::unique(AddrToMD5Map.begin(), AddrToMD5Map.end()),
                      AddrToMD5Map.end());
 }
 
 StringRef InstrProfSymtab::getFuncName(uint64_t FuncMD5Hash) {
   auto Result =
       std::lower_bound(MD5NameMap.begin(), MD5NameMap.end(), FuncMD5Hash,
                        [](const std::pair<uint64_t, std::string> &LHS,
                           uint64_t RHS) { return LHS.first < RHS; });
   if (Result != MD5NameMap.end() && Result->first == FuncMD5Hash)
     return Result->second;
   return StringRef();
 }
 
+Function* InstrProfSymtab::getFunction(uint64_t FuncMD5Hash) {
+  auto Result =
+      std::lower_bound(MD5FuncMap.begin(), MD5FuncMap.end(), FuncMD5Hash,
+                       [](const std::pair<uint64_t, Function*> &LHS,
+                          uint64_t RHS) { return LHS.first < RHS; });
+  if (Result != MD5FuncMap.end() && Result->first == FuncMD5Hash)
+    return Result->second;
+  return nullptr;
+}
+
 // See also getPGOFuncName implementation. These two need to be
 // matched.
 StringRef InstrProfSymtab::getOrigFuncName(uint64_t FuncMD5Hash) {
   StringRef PGOName = getFuncName(FuncMD5Hash);
   size_t S = PGOName.find_first_of(':');
   if (S == StringRef::npos)
     return PGOName;
   return PGOName.drop_front(S + 1);

llvm/trunk/lib/ProfileData/InstrProf.cpp

 
 std::string getPGOFuncName(StringRef RawFuncName,
                            GlobalValue::LinkageTypes Linkage,
                            StringRef FileName,
                            uint64_t Version LLVM_ATTRIBUTE_UNUSED) {
   return GlobalValue::getGlobalIdentifier(RawFuncName, Linkage, FileName);
 }
 
-std::string getPGOFuncName(const Function &F, uint64_t Version) {
+// Return the PGOFuncName. This function has some special handling when called
+// in LTO optimization. The following only applies when calling in LTO passes
+// (when \c InLTO is true): LTO's internalization privatizes many global linkage
+// symbols. This happens after value profile annotation, but those internal
+// linkage functions should not have a source prefix.
+// To differentiate compiler generated internal symbols from original ones,
+// PGOFuncName meta data are created and attached to the original internal
+// symbols in the value profile annotation step
+// (PGOUseFunc::annotateIndirectCallSites). If a symbol does not have the meta
+// data, its original linkage must be non-internal.
+std::string getPGOFuncName(const Function &F, bool InLTO, uint64_t Version) {
+  if (!InLTO)
     return getPGOFuncName(F.getName(), F.getLinkage(), F.getParent()->getName(),
                           Version);
+
+  // InLTO mode. First check if these is a meta data.
+  MDNode *MD = F.getMetadata("PGOFuncName");
+  if (MD != nullptr) {
+    StringRef S = cast<MDString>(MD->getOperand(0))->getString();
+    return S.str();
+  }
+
+  // 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.
+  return getPGOFuncName (F.getName(), GlobalValue::ExternalLinkage, "");
 }
 
 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);
GlobalVariable *createPGOFuncNameVar(Module &M,
 
   return FuncNameVar;
 }
 
 GlobalVariable *createPGOFuncNameVar(Function &F, StringRef PGOFuncName) {
   return createPGOFuncNameVar(*F.getParent(), F.getLinkage(), PGOFuncName);
 }
 
-void InstrProfSymtab::create(const Module &M) {
-  for (const Function &F : M)
-    addFuncName(getPGOFuncName(F));
+void InstrProfSymtab::create(Module &M, bool InLTO) {
+  for (Function &F : M) {
+    // Function may not have a name: like using asm("") to overwrite the name.
+    // Ignore in this case.
+    if (!F.hasName())
+      continue;
+    const std::string &PGOFuncName = getPGOFuncName(F, InLTO);
+    addFuncName(PGOFuncName);
+    MD5FuncMap.push_back(std::make_pair(Function::getGUID(PGOFuncName), &F));
+  }
 
   finalizeSymtab();
 }
 
 int collectPGOFuncNameStrings(const std::vector<std::string> &NameStrs,
                               bool doCompression, std::string &Result) {
   assert(NameStrs.size() && "No name data to emit");
 

llvm/trunk/lib/Transforms/Instrumentation/PGOInstrumentation.cpp

void PGOUseFunc::setBranchWeights() {
   }
 }
 
 // Traverse all the indirect callsites and annotate the instructions.
 void PGOUseFunc::annotateIndirectCallSites() {
   if (DisableValueProfiling)
     return;
 
+  // Write out the PGOFuncName if this is different from it's raw name.
+  // This should only apply to internal linkage functions only.
+  const std::string &FuncName = getPGOFuncName(F);
+  if (FuncName != F.getName()) {
+    LLVMContext &C = F.getContext();
+    MDNode *N = MDNode::get(C, MDString::get(C, FuncName.c_str()));
+    F.setMetadata("PGOFuncName", N);
+  }
+
   unsigned IndirectCallSiteIndex = 0;
   PGOIndirectCallSiteVisitor ICV;
   ICV.visit(F);
   unsigned NumValueSites =
       ProfileRecord.getNumValueSites(IPVK_IndirectCallTarget);
   if (NumValueSites != ICV.IndirectCallInsts.size()) {
     std::string Msg =
         std::string("Inconsistent number of indirect call sites: ") +