[ThinLTO] Use MD5 hash in function index.

[tejohnson]

Summary

This patch uses the lower 64-bits of the MD5 hash of a function name as
a GUID in the function index, instead of storing function names. Any
local functions are first given a global name by prepending the original
source file name. This is the same naming scheme and GUID used by PGO in
the indexed profile format.

This change has a couple of benefits. The primary benefit is size
reduction in the combined index file, for example 483.xalancbmk's
combined index file was reduced by around 70%. It should also result in
memory savings for the index file in memory, as the in-memory map is
also indexed by the hash instead of the string.

Second, this enables integration with indirect call promotion, since the
indirect call profile targets are recorded using the same global naming
convention and hash. This will enable the function importer to easily
locate function summaries for indirect call profile targets to enable
their import and subsequent promotion.

The original source file name is recorded in the bitcode in a new
module-level record for use in the ThinLTO backend pipeline.

[davidxl]

lib/Bitcode/Reader/BitcodeReader.cpp

5466

Is the assert unrelated change?

lib/Bitcode/Writer/BitcodeWriter.cpp

823

This code looks like a common utility (string emission) -- is there any code reuse opportunity?

[tejohnson]

lib/Bitcode/Reader/BitcodeReader.cpp

5466

It is related as we can't support lazy function summary reading for the per-module index since we need the function summary to get the global identifier below. Nor do we need to support lazy function summary reading here, that was meant for the combined index reading and the support was probably inadvertently cloned here.

lib/Bitcode/Writer/BitcodeWriter.cpp

823

In other places where we set up string encoding abbrevs are structured a bit differently since we are emitting multiple strings (e.g. the VST). Thus they emit all 3 abbrevs unconditionally, then for each string to be emitted invoke getStringEncoding, and use the appropriate abbrev.

[davidxl]

Any test on the recorded source file name?

include/llvm/IR/FunctionInfo.h

151

I am a little concerned with using DenseMap data structure here.

Both DenseMap and StringMap are implemented as open hashtab with quadratic probing. The load factor of both are guaranteed to < 0.75 -- that means there are lots of empty buckets in a large table. The main differences are:

1. StringMap uses indirection -- each bucket contains pointer to the key-value pair object, so the bucket size is small. The copy is also cheaper when rehashing happens. However DenseMap is key-value pair is embedded inside the bucket. That means if the value type has large size, it will cause lots of waste in memory. The copy of dense map can also cause large overhead.
2. When resizing, DenseMap will round up the new size to the next power of 2 value -- this further increases the memory overhead.

There is another bad side effect is that if elements are inserted into map one by one, it will incur lots of reallocation operation (just like vector) unless the size of the map is known before hand and properly resized at the beginning.

I suggest using std::map if the size of the map is not known priori. If it is known, and if the map lookup happens after the map is created, it might be better to use a vector (pushback) followed by a sort after the map is populated.

include/llvm/IR/Module.h

200

This comment is not quite clear in its meaning.

test/tools/gold/X86/thinlto.ll

27

test [offset, guid] pattern here?

[mehdi_amini]

lib/Bitcode/Reader/BitcodeReader.cpp

461

doxygen, at least pointing to the Module one.

5461

Typo in the comment: VST_FNENTRY instead of VST_CODE_FNENTRY

5488

Typo in the comment: VST_FNENTRY instead of VST_CODE_COMBINED_FNENTRY

lib/IR/Module.cpp

50

Can you initialize SourceFileName to empty and test in getSourceFileName()?

lib/Transforms/IPO/FunctionImport.cpp

206

I was not very happy with that originally, and it may be a good time to revisit it.
When does it happen? Why don't we always rename SrcModule ?

tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

176

Test?

[tejohnson]

include/llvm/IR/FunctionInfo.h

151

Good point, I hadn't compared the relative overheads of these data structures.

Unfortunately, we don't know the size of this map ahead of time. E.g. when merging multiple indexes to create the combined index. And we do lookups while adding (e.g. when creating the combined index we may have multiple comdat with the same name/GUID).

So it sounds like the best bet for now is to use std::map, and we can investigate alternatives that might involve restructuring the accesses if this turns out not to be efficient enough.

include/llvm/IR/Module.h

200

The point I'm trying to make is that if we are compiling this from bitcode, it comes from the new bitcode record, otherwise it is the name of the input file (which is the same as the ModuleID). E.g.:

clang -c foo.c -flto=thin ModuleID = SourceFileName = foo.c
(foo.o is bitcode with new MODULE_SOURCE_FILENAME record = "foo.c")
clang foo.o -flto=thin ModuleID = foo.o, SourceFileName = foo.c

test/tools/gold/X86/thinlto.ll

27

I'm afraid testing the specific offsets will be brittle, unless I just check for any integer in that field. I could test for the GUIDs, but would have to handle either ordering as the order in the combined index is not currently guaranteed. Let me go ahead and check for the GUIDs as that maintains the same level of checking as we had with the function names.

[tejohnson]

lib/Bitcode/Reader/BitcodeReader.cpp

461

Will do.

5461

Will fix.

5488

Will fix.

lib/IR/Module.cpp

50

Actually, this is by design. When we are compiling from source (say clang -c foo.c -flto=thin), we want the SourceFileName to be foo.c. Only when we later compile the foo.o bitcode file do we then want this set to foo.c from the new bitcode record.

lib/Transforms/IPO/FunctionImport.cpp

206

The old comment was stale. We aren't actually doing any renaming in SrcModule until the importing happens later on. At this point we haven't even materialized everything in SrcModule that we want to import, so I think it is premature to do any renaming.

The CalledFunctionName however comes out of the Worklist which was populated by findExternalCalls. We had to get the global identifier in order to access the correct function summary out of the index here, and to disambiguate from same named locals we are going to import from other modules.

(Looking at findExternalCalls, I just realized that we should still be checking if this is already in the DestModule using the suffix form, however, since that is the name the local will get when it is promoted. However, with the current bulk importing mechanism we would never already have a promoted local from another module imported into DestModule yet, but I will fix this in case that ever changes.)

tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

176

Will add one.

[tejohnson]

• Address David and Mehdi's review comments and rebase.

[mehdi_amini]

LGTM. You may wait a little bit to give a change to David to chime in.

lib/IR/Module.cpp

50

Not if I was clear because I think what I suggested matches your behavior (unless I missed something).

I'd have left the SourceFileName member empty and change the getter to:

const std::string &getSourceFileName() const { 
  if (SourceFileName.empty()) return getModuleIdentifier();
  return SourceFileName;
}

But it is not important so feel free to keep as you did.

lib/Transforms/IPO/FunctionImport.cpp

206

We can't rename before materializing?

test/tools/gold/X86/thinlto.ll

27–29

What is the op1 here? Is it the 64 low-bits of the MD5 as an int?
Can we have a better pretty-print from llvm-bcanalyzer? (don't hold this patch for this though)

[tejohnson]

lib/IR/Module.cpp

50

Oh got it, I misunderstood. It will be more efficient to initialize SourceFileName once and not have to do the empty check every time we call this, so I think I will leave it as-is.

lib/Transforms/IPO/FunctionImport.cpp

206

I was worried about doing additional parsing after we have done some renaming. But thinking through this some more it should be ok as all GV references should be through the centralized ValueList which would contain value handles to the renamed GVs.

In any case, there isn't a big need to do the renaming in the SrcModule before the actual importing.

test/tools/gold/X86/thinlto.ll

27–29

Yes, op0 is the bitcode offset of the summary, and op0 is the MD5 as an int. I will add a comment to these tests to enumerate the format before committing.

Would you rather see the values printed in hex? The bcanalyzer just prints all record values as ints, it doesn't look at the record type to determine the best format. That would require more plumbing in the bcanalyzer than I'm thinking this is worth. Probably the easiest thing would be to add an option to llvm-bcanalyzer to dump all record values in hex.

[tejohnson]

Fix missed incorrect VST_CODE_COMBINED_FNENTRY comment, and add comments
to test describing expected format of this record type.

[davidxl]

lgtm

test/tools/gold/X86/thinlto.ll

27–29

nit -- for better reading, probably just need to keep one line with actual MD5 value, the rest can be replaced with [0-9]+

[tejohnson]

test/tools/gold/X86/thinlto.ll

27–29

I think that's what I have here already? I could shorten this a bit by replacing the intermediate parts with {{.*}}. E.g.:

; COMBINED-NEXT: <COMBINED_FNENTRY {{.*}} {{-3706093650706652785|-5300342847281564238}}

Is that preferable?

[davidxl]

I meant the op1 part can be simplified -- but not necessariliy need to.

David

include/llvm/Bitcode/LLVMBitCodes.h

enum ModuleCodes {
 
     MODULE_CODE_VSTOFFSET   = 13,  // VSTOFFSET: [offset]
 
     // ALIAS: [alias value type, addrspace, aliasee val#, linkage, visibility]
     MODULE_CODE_ALIAS       = 14,
 
     // METADATA_VALUES: [numvals]
     MODULE_CODE_METADATA_VALUES = 15,
+
+    // SOURCE_FILENAME: [namechar x N]
+    MODULE_CODE_SOURCE_FILENAME = 16,
   };
 
   /// PARAMATTR blocks have code for defining a parameter attribute set.
   enum AttributeCodes {
     // FIXME: Remove `PARAMATTR_CODE_ENTRY_OLD' in 4.0
     PARAMATTR_CODE_ENTRY_OLD  = 1, // ENTRY: [paramidx0, attr0,
                                    //         paramidx1, attr1...]
     PARAMATTR_CODE_ENTRY      = 2, // ENTRY: [paramidx0, attrgrp0,
enum TypeSymtabCodes {
     TST_CODE_ENTRY = 1     // TST_ENTRY: [typeid, namechar x N]
   };
 
   // Value symbol table codes.
   enum ValueSymtabCodes {
     VST_CODE_ENTRY   = 1,   // VST_ENTRY: [valueid, namechar x N]
     VST_CODE_BBENTRY = 2,   // VST_BBENTRY: [bbid, namechar x N]
     VST_CODE_FNENTRY = 3,   // VST_FNENTRY: [valueid, offset, namechar x N]
-    // VST_COMBINED_FNENTRY: [offset, namechar x N]
+    // VST_COMBINED_FNENTRY: [funcsumoffset, funcguid]
     VST_CODE_COMBINED_FNENTRY = 4
   };
 
   // The module path symbol table only has one code (MST_CODE_ENTRY).
   enum ModulePathSymtabCodes {
     MST_CODE_ENTRY   = 1,  // MST_ENTRY: [modid, namechar x N]
   };
 

include/llvm/IR/Function.h

 #include "llvm/ADT/Optional.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/GlobalObject.h"
 #include "llvm/IR/OperandTraits.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/Support/MD5.h"
 
 namespace llvm {
 
 class FunctionType;
 class LLVMContext;
 class DISubprogram;
 
 template <>
/// @}
   /// Return the modified name for a function suitable to be
   /// used as the key for a global lookup (e.g. profile or ThinLTO).
   /// The function's original name is \c FuncName and has linkage of type
   /// \c Linkage. The function is defined in module \c FileName.
   static std::string getGlobalIdentifier(StringRef FuncName,
                                          GlobalValue::LinkageTypes Linkage,
                                          StringRef FileName);
 
+  /// Return a 64-bit global unique ID constructed from global function name
+  /// (i.e. returned by getGlobalIdentifier).
+  static uint64_t getGUID(StringRef GlobalFuncName) {
+    return MD5Hash(GlobalFuncName);
+  }
+
 private:
   void allocHungoffUselist();
   template<int Idx> void setHungoffOperand(Constant *C);
 
   // Shadow Value::setValueSubclassData with a private forwarding method so that
   // subclasses cannot accidentally use it.
   void setValueSubclassData(unsigned short D) {
     Value::setValueSubclassData(D);

include/llvm/IR/FunctionInfo.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_FUNCTIONINFO_H
 #define LLVM_IR_FUNCTIONINFO_H
 
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringMap.h"
+#include "llvm/IR/Function.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 
 /// \brief Function summary information to aid decisions and implementation of
 /// importing.
public:
   void setBitcodeIndex(uint64_t FuncOffset) { BitcodeIndex = FuncOffset; }
 };
 
 /// List of function info structures for a particular function name held
 /// in the FunctionMap. Requires a vector in the case of multiple
 /// COMDAT functions of the same name.
 typedef std::vector<std::unique_ptr<FunctionInfo>> FunctionInfoList;
 
-/// Map from function name to corresponding function info structures.
-typedef StringMap<FunctionInfoList> FunctionInfoMapTy;
+/// Map from function GUID to corresponding function info structures.
+typedef DenseMap<uint64_t, FunctionInfoList> FunctionInfoMapTy;
 
 /// Type used for iterating through the function info map.
 typedef FunctionInfoMapTy::const_iterator const_funcinfo_iterator;
 typedef FunctionInfoMapTy::iterator funcinfo_iterator;
 
 /// String table to hold/own module path strings, which additionally holds the
 /// module ID assigned to each module during the plugin step. The StringMap
 /// makes a copy of and owns inserted strings.
public:
 
   funcinfo_iterator begin() { return FunctionMap.begin(); }
   const_funcinfo_iterator begin() const { return FunctionMap.begin(); }
   funcinfo_iterator end() { return FunctionMap.end(); }
   const_funcinfo_iterator end() const { return FunctionMap.end(); }
 
   /// Get the list of function info objects for a given function.
   const FunctionInfoList &getFunctionInfoList(StringRef FuncName) {
-    return FunctionMap[FuncName];
+    return FunctionMap[Function::getGUID(FuncName)];
   }
 
   /// Get the list of function info objects for a given function.
   const const_funcinfo_iterator findFunctionInfoList(StringRef FuncName) const {
-    return FunctionMap.find(FuncName);
+    return FunctionMap.find(Function::getGUID(FuncName));
   }
 
   /// Add a function info for a function of the given name.
   void addFunctionInfo(StringRef FuncName, std::unique_ptr<FunctionInfo> Info) {
-    FunctionMap[FuncName].push_back(std::move(Info));
+    FunctionMap[Function::getGUID(FuncName)].push_back(std::move(Info));
+  }
+
+  void addFunctionInfo(uint64_t FuncGUID, std::unique_ptr<FunctionInfo> Info) {
+    FunctionMap[FuncGUID].push_back(std::move(Info));
   }
 
   /// Iterator to allow writer to walk through table during emission.
   iterator_range<StringMap<uint64_t>::const_iterator>
   modPathStringEntries() const {
     return llvm::make_range(ModulePathStringTable.begin(),
                             ModulePathStringTable.end());
   }

include/llvm/IR/Module.h

private:
   AliasListType AliasList;        ///< The Aliases in the module
   NamedMDListType NamedMDList;    ///< The named metadata in the module
   std::string GlobalScopeAsm;     ///< Inline Asm at global scope.
   ValueSymbolTable *ValSymTab;    ///< Symbol table for values
   ComdatSymTabType ComdatSymTab;  ///< Symbol table for COMDATs
   std::unique_ptr<GVMaterializer>
   Materializer;                   ///< Used to materialize GlobalValues
   std::string ModuleID;           ///< Human readable identifier for the module
+  std::string SourceFileName;     ///< Original source file name for module,
+                                  ///< recorded in bitcode.
   std::string TargetTriple;       ///< Platform target triple Module compiled on
                                   ///< Format: (arch)(sub)-(vendor)-(sys0-(abi)
   void *NamedMDSymTab;            ///< NamedMDNode names.
   DataLayout DL;                  ///< DataLayout associated with the module
 
   friend class Constant;
 
 /// @}

 /// @}
 /// @name Module Level Accessors
 /// @{
 
   /// Get the module identifier which is, essentially, the name of the module.
   /// @returns the module identifier as a string
   const std::string &getModuleIdentifier() const { return ModuleID; }
 
+  /// Get the module's original source file name, either the same as the
+  /// ModuleID when compiling from source, or from name recorded in bitcode.
+  /// Defaulting to ModuleID also supports older bitcode without the record.
+  const std::string &getSourceFileName() const { return SourceFileName; }
+
   /// \brief Get a short "name" for the module.
   ///
   /// This is useful for debugging or logging. It is essentially a convenience
   /// wrapper around getModuleIdentifier().
   StringRef getName() const { return ModuleID; }
 
   /// Get the data layout string for the module's target platform. This is
   /// equivalent to getDataLayout()->getStringRepresentation().

 
 /// @}
 /// @name Module Level Mutators
 /// @{
 
   /// Set the module identifier.
   void setModuleIdentifier(StringRef ID) { ModuleID = ID; }
 
+  /// Set the module's original source file name.
+  void setSourceFileName(StringRef Name) { SourceFileName = Name; }
+
   /// Set the data layout
   void setDataLayout(StringRef Desc);
   void setDataLayout(const DataLayout &Other);
 
   /// Set the target triple.
   void setTargetTriple(StringRef T) { TargetTriple = T; }
 
   /// Set the module-scope inline assembly blocks.

lib/Bitcode/Reader/BitcodeReader.cpp

class FunctionIndexBitcodeReader {
   DenseMap<uint64_t, std::unique_ptr<FunctionSummary>> SummaryMap;
 
   /// Map populated during module path string table parsing, from the
   /// module ID to a string reference owned by the index's module
   /// path string table, used to correlate with combined index function
   /// summary records.
   DenseMap<uint64_t, StringRef> ModuleIdMap;
 
+  std::string SourceFileName;
+
 public:
   std::error_code error(BitcodeError E, const Twine &Message);
   std::error_code error(BitcodeError E);
   std::error_code error(const Twine &Message);
 
   FunctionIndexBitcodeReader(MemoryBuffer *Buffer,
                              DiagnosticHandlerFunction DiagnosticHandler,
                              bool IsLazy = false,
case bitc::MODULE_CODE_METADATA_VALUES:
       // record value, regardless of whether we are doing lazy metadata
       // loading, so that we have consistent handling and assertion
       // checking in parseMetadata for module-level metadata.
       NumModuleMDs = Record[0];
       SeenModuleValuesRecord = true;
       assert(MetadataList.size() == 0);
       MetadataList.resize(NumModuleMDs);
       break;
+    /// MODULE_CODE_SOURCE_FILENAME: [namechar x N]
+    case bitc::MODULE_CODE_SOURCE_FILENAME:
+      SmallString<128> ValueName;
+      if (convertToString(Record, 0, ValueName))
+        return error("Invalid record");
+      TheModule->setSourceFileName(ValueName);
+      break;
     }
     Record.clear();
   }
 }
 
 /// Helper to read the header common to all bitcode files.
 static bool hasValidBitcodeHeader(BitstreamCursor &Stream) {
   // Sniff for the signature.
while (1) {
     }
 
     // Read a record.
     Record.clear();
     switch (Stream.readRecord(Entry.ID, Record)) {
     default: // Default behavior: ignore (e.g. VST_CODE_BBENTRY records).
       break;
     case bitc::VST_CODE_FNENTRY: {
       // VST_FNENTRY: [valueid, offset, namechar x N]
       if (convertToString(Record, 2, ValueName))
         return error("Invalid record");
       unsigned ValueID = Record[0];
       uint64_t FuncOffset = Record[1];
-      std::unique_ptr<FunctionInfo> FuncInfo =
-          llvm::make_unique<FunctionInfo>(FuncOffset);
-      if (foundFuncSummary() && !IsLazy) {
+      assert(!IsLazy && "Lazy summary read only supported for combined index");
+      // Gracefully handle bitcode without a function summary section,
+      // which will simply not populate the index.
+      if (foundFuncSummary()) {
         DenseMap<uint64_t, std::unique_ptr<FunctionSummary>>::iterator SMI =
             SummaryMap.find(ValueID);
         assert(SMI != SummaryMap.end() && "Summary info not found");
+        std::unique_ptr<FunctionInfo> FuncInfo =
+            llvm::make_unique<FunctionInfo>(FuncOffset);
         FuncInfo->setFunctionSummary(std::move(SMI->second));
+        assert(!SourceFileName.empty());
+        TheIndex->addFunctionInfo(
+            Function::getGlobalIdentifier(
+                ValueName, FuncInfo->functionSummary()->getFunctionLinkage(),
+                SourceFileName),
+            std::move(FuncInfo));
       }
-      TheIndex->addFunctionInfo(ValueName, std::move(FuncInfo));
 
       ValueName.clear();
       break;
     }
     case bitc::VST_CODE_COMBINED_FNENTRY: {
-      // VST_FNENTRY: [offset, namechar x N]
-      if (convertToString(Record, 1, ValueName))
-        return error("Invalid record");
+      // VST_FNENTRY: [offset, funcguid]
       uint64_t FuncSummaryOffset = Record[0];
+      uint64_t FuncGUID = Record[1];
       std::unique_ptr<FunctionInfo> FuncInfo =
           llvm::make_unique<FunctionInfo>(FuncSummaryOffset);
       if (foundFuncSummary() && !IsLazy) {
         DenseMap<uint64_t, std::unique_ptr<FunctionSummary>>::iterator SMI =
             SummaryMap.find(FuncSummaryOffset);
         assert(SMI != SummaryMap.end() && "Summary info not found");
         FuncInfo->setFunctionSummary(std::move(SMI->second));
       }
-      TheIndex->addFunctionInfo(ValueName, std::move(FuncInfo));
+      TheIndex->addFunctionInfo(FuncGUID, std::move(FuncInfo));
 
       ValueName.clear();
       break;
     }
     }
   }
 }
 
 // Parse just the blocks needed for function index building out of the module.
 // At the end of this routine the function Index is populated with a map
 // from function name to FunctionInfo. The function info contains
 // either the parsed function summary information (when parsing summaries
 // eagerly), or just to the function summary record's offset
 // if parsing lazily (IsLazy).
 std::error_code FunctionIndexBitcodeReader::parseModule() {
   if (Stream.EnterSubBlock(bitc::MODULE_BLOCK_ID))
     return error("Invalid record");
 
+  SmallVector<uint64_t, 64> Record;
+
   // Read the function index for this module.
   while (1) {
     BitstreamEntry Entry = Stream.advance();
 
     switch (Entry.Kind) {
     case BitstreamEntry::Error:
       return error("Malformed block");
     case BitstreamEntry::EndBlock:
case BitstreamEntry::SubBlock:
       case bitc::MODULE_STRTAB_BLOCK_ID:
         if (std::error_code EC = parseModuleStringTable())
           return EC;
         break;
       }
       continue;
 
     case BitstreamEntry::Record:
+      // Once we find the single record of interest, skip the rest.
+      if (!SourceFileName.empty())
         Stream.skipRecord(Entry.ID);
+      else {
+        Record.clear();
+        auto BitCode = Stream.readRecord(Entry.ID, Record);
+        switch (BitCode) {
+        default:
+          break; // Default behavior, ignore unknown content.
+        /// MODULE_CODE_SOURCE_FILENAME: [namechar x N]
+        case bitc::MODULE_CODE_SOURCE_FILENAME:
+          SmallString<128> ValueName;
+          if (convertToString(Record, 0, ValueName))
+            return error("Invalid record");
+          SourceFileName = ValueName.c_str();
+          break;
+        }
+      }
       continue;
     }
   }
 }
 
 // Eagerly parse the entire function summary block (i.e. for all functions
 // in the index). This populates the FunctionSummary objects in
 // the index.

lib/Bitcode/Writer/BitcodeWriter.cpp

static uint64_t WriteValueSymbolTableForwardDecl(const ValueSymbolTable &VST,
   Stream.EmitRecordWithAbbrev(VSTOffsetAbbrev, Vals);
 
   // Compute and return the bit offset to the placeholder, which will be
   // patched when the real VST is written. We can simply subtract the 32-bit
   // fixed size from the current bit number to get the location to backpatch.
   return Stream.GetCurrentBitNo() - 32;
 }
 
+enum StringEncoding { SE_Char6, SE_Fixed7, SE_Fixed8 };
+
+/// Determine the encoding to use for the given string name and length.
+static StringEncoding getStringEncoding(const char *Str, unsigned StrLen) {
+  bool isChar6 = true;
+  for (const char *C = Str, *E = C + StrLen; C != E; ++C) {
+    if (isChar6)
+      isChar6 = BitCodeAbbrevOp::isChar6(*C);
+    if ((unsigned char)*C & 128)
+      // don't bother scanning the rest.
+      return SE_Fixed8;
+  }
+  if (isChar6)
+    return SE_Char6;
+  else
+    return SE_Fixed7;
+}
+
 /// Emit top-level description of module, including target triple, inline asm,
 /// descriptors for global variables, and function prototype info.
 /// Returns the bit offset to backpatch with the location of the real VST.
 static uint64_t WriteModuleInfo(const Module *M, const ValueEnumerator &VE,
                                 BitstreamWriter &Stream) {
   // Emit various pieces of data attached to a module.
   if (!M->getTargetTriple().empty())
     WriteStringRecord(bitc::MODULE_CODE_TRIPLE, M->getTargetTriple(),
static uint64_t WriteModuleInfo(const Module *M, const ValueEnumerator &VE,
 
   // Write a record indicating the number of module-level metadata IDs
   // This is needed because the ids of metadata are assigned implicitly
   // based on their ordering in the bitcode, with the function-level
   // metadata ids starting after the module-level metadata ids. For
   // function importing where we lazy load the metadata as a postpass,
   // we want to avoid parsing the module-level metadata before parsing
   // the imported functions.
+  {
     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
     Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_METADATA_VALUES));
     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
     unsigned MDValsAbbrev = Stream.EmitAbbrev(Abbv);
     Vals.push_back(VE.numMDs());
     Stream.EmitRecord(bitc::MODULE_CODE_METADATA_VALUES, Vals, MDValsAbbrev);
     Vals.clear();
+  }
+
+  // Emit the module's source file name.
+  {
+    StringEncoding Bits =
+        getStringEncoding(M->getName().data(), M->getName().size());
+    BitCodeAbbrevOp AbbrevOpToUse = BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8);
+    if (Bits == SE_Char6)
+      AbbrevOpToUse = BitCodeAbbrevOp(BitCodeAbbrevOp::Char6);
+    else if (Bits == SE_Fixed7)
+      AbbrevOpToUse = BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7);
+
+    // MODULE_CODE_SOURCE_FILENAME: [namechar x N]
+    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
+    Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_SOURCE_FILENAME));
+    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+    Abbv->Add(AbbrevOpToUse);
+    unsigned FilenameAbbrev = Stream.EmitAbbrev(Abbv);
+
+    for (const auto P : M->getSourceFileName())
+      Vals.push_back((unsigned char)P);
+
+    // Emit the finished record.
+    Stream.EmitRecord(bitc::MODULE_CODE_SOURCE_FILENAME, Vals, FilenameAbbrev);
+    Vals.clear();
+  }
 
   uint64_t VSTOffsetPlaceholder =
       WriteValueSymbolTableForwardDecl(M->getValueSymbolTable(), Stream);
   return VSTOffsetPlaceholder;
 }
 
 static uint64_t GetOptimizationFlags(const Value *V) {
   uint64_t Flags = 0;
case Instruction::VAArg:
     Vals.push_back(VE.getTypeID(I.getType())); // restype.
     break;
   }
 
   Stream.EmitRecord(Code, Vals, AbbrevToUse);
   Vals.clear();
 }
 
-enum StringEncoding { SE_Char6, SE_Fixed7, SE_Fixed8 };
-
-/// Determine the encoding to use for the given string name and length.
-static StringEncoding getStringEncoding(const char *Str, unsigned StrLen) {
-  bool isChar6 = true;
-  for (const char *C = Str, *E = C + StrLen; C != E; ++C) {
-    if (isChar6)
-      isChar6 = BitCodeAbbrevOp::isChar6(*C);
-    if ((unsigned char)*C & 128)
-      // don't bother scanning the rest.
-      return SE_Fixed8;
-  }
-  if (isChar6)
-    return SE_Char6;
-  else
-    return SE_Fixed7;
-}
-
 /// Emit names for globals/functions etc. The VSTOffsetPlaceholder,
 /// BitcodeStartBit and FunctionIndex are only passed for the module-level
 /// VST, where we are including a function bitcode index and need to
 /// backpatch the VST forward declaration record.
 static void WriteValueSymbolTable(
     const ValueSymbolTable &VST, const ValueEnumerator &VE,
     BitstreamWriter &Stream, uint64_t VSTOffsetPlaceholder = 0,
     uint64_t BitcodeStartBit = 0,

 }
 
 /// Emit function names and summary offsets for the combined index
 /// used by ThinLTO.
 static void WriteCombinedValueSymbolTable(const FunctionInfoIndex &Index,
                                           BitstreamWriter &Stream) {
   Stream.EnterSubblock(bitc::VALUE_SYMTAB_BLOCK_ID, 4);
 
-  // 8-bit fixed-width VST_COMBINED_FNENTRY function strings.
   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
   Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_COMBINED_FNENTRY));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcoffset
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
-  unsigned FnEntry8BitAbbrev = Stream.EmitAbbrev(Abbv);
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcsumoffset
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcguid
+  unsigned FnEntryAbbrev = Stream.EmitAbbrev(Abbv);
 
-  // 7-bit fixed width VST_COMBINED_FNENTRY function strings.
-  Abbv = new BitCodeAbbrev();
-  Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_COMBINED_FNENTRY));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcoffset
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
-  unsigned FnEntry7BitAbbrev = Stream.EmitAbbrev(Abbv);
-
-  // 6-bit char6 VST_COMBINED_FNENTRY function strings.
-  Abbv = new BitCodeAbbrev();
-  Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_COMBINED_FNENTRY));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcoffset
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
-  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
-  unsigned FnEntry6BitAbbrev = Stream.EmitAbbrev(Abbv);
-
-  // FIXME: We know if the type names can use 7-bit ascii.
-  SmallVector<unsigned, 64> NameVals;
+  SmallVector<uint64_t, 64> NameVals;
 
   for (const auto &FII : Index) {
-    for (const auto &FI : FII.getValue()) {
+    for (const auto &FI : FII.second) {
       NameVals.push_back(FI->bitcodeIndex());
 
-      StringRef FuncName = FII.first();
+      uint64_t FuncGUID = FII.first;
 
-      // Figure out the encoding to use for the name.
-      StringEncoding Bits = getStringEncoding(FuncName.data(), FuncName.size());
+      // VST_COMBINED_FNENTRY: [funcsumoffset, funcguid]
+      unsigned AbbrevToUse = FnEntryAbbrev;
 
-      // VST_COMBINED_FNENTRY: [funcsumoffset, namechar x N]
-      unsigned AbbrevToUse = FnEntry8BitAbbrev;
-      if (Bits == SE_Char6)
-        AbbrevToUse = FnEntry6BitAbbrev;
-      else if (Bits == SE_Fixed7)
-        AbbrevToUse = FnEntry7BitAbbrev;
-
-      for (const auto P : FuncName)
-        NameVals.push_back((unsigned char)P);
+      NameVals.push_back(FuncGUID);
 
       // Emit the finished record.
       Stream.EmitRecord(bitc::VST_CODE_COMBINED_FNENTRY, NameVals, AbbrevToUse);
       NameVals.clear();
     }
   }
   Stream.ExitBlock();
 }
static void WriteCombinedFunctionSummary(const FunctionInfoIndex &I,
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_CODE_COMBINED_ENTRY));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // modid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // instcount
   unsigned FSAbbrev = Stream.EmitAbbrev(Abbv);
 
   SmallVector<unsigned, 64> NameVals;
   for (const auto &FII : I) {
-    for (auto &FI : FII.getValue()) {
+    for (auto &FI : FII.second) {
       FunctionSummary *FS = FI->functionSummary();
       assert(FS);
 
       NameVals.push_back(I.getModuleId(FS->modulePath()));
       NameVals.push_back(getEncodedLinkage(FS->getFunctionLinkage()));
       NameVals.push_back(FS->instCount());
 
       // Record the starting offset of this summary entry for use

lib/IR/FunctionInfo.cpp

 
 // Create the combined function index/summary from multiple
 // per-module instances.
 void FunctionInfoIndex::mergeFrom(std::unique_ptr<FunctionInfoIndex> Other,
                                   uint64_t NextModuleId) {
 
   StringRef ModPath;
   for (auto &OtherFuncInfoLists : *Other) {
-    std::string FuncName = OtherFuncInfoLists.getKey();
+    uint64_t FuncGUID = OtherFuncInfoLists.first;
     FunctionInfoList &List = OtherFuncInfoLists.second;
 
     // Assert that the func info list only has one entry, since we shouldn't
     // have duplicate names within a single per-module index.
     assert(List.size() == 1);
     std::unique_ptr<FunctionInfo> Info = std::move(List.front());
 
     // Skip if there was no function summary section.
else
       assert(ModPath == Info->functionSummary()->modulePath() &&
              "Each module in the combined map should have a unique ID");
 
     // Note the module path string ref was copied above and is still owned by
     // the original per-module index. Reset it to the new module path
     // string reference owned by the combined index.
     Info->functionSummary()->setModulePath(ModPath);
 
-    // If it is a local function, rename it.
-    if (GlobalValue::isLocalLinkage(
-            Info->functionSummary()->getFunctionLinkage())) {
-      // Any local functions are virtually renamed when being added to the
-      // combined index map, to disambiguate from other functions with
-      // the same name. The symbol table created for the combined index
-      // file should contain the renamed symbols.
-      FuncName =
-          FunctionInfoIndex::getGlobalNameForLocal(FuncName, NextModuleId);
-    }
-
     // Add new function info to existing list. There may be duplicates when
     // combining FunctionMap entries, due to COMDAT functions. Any local
-    // functions were virtually renamed above.
-    addFunctionInfo(FuncName, std::move(Info));
+    // functions were given unique global IDs.
+    addFunctionInfo(FuncGUID, std::move(Info));
   }
 }

lib/IR/Module.cpp

 template class llvm::SymbolTableListTraits<GlobalVariable>;
 template class llvm::SymbolTableListTraits<GlobalAlias>;
 
 //===----------------------------------------------------------------------===//
 // Primitive Module methods.
 //
 
 Module::Module(StringRef MID, LLVMContext &C)
-    : Context(C), Materializer(), ModuleID(MID), DL("") {
+    : Context(C), Materializer(), ModuleID(MID), SourceFileName(MID), DL("") {
   ValSymTab = new ValueSymbolTable();
   NamedMDSymTab = new StringMap<NamedMDNode *>();
   Context.addModule(this);
 }
 
 Module::~Module() {
   Context.removeModule(this);
   dropAllReferences();

lib/Transforms/IPO/FunctionImport.cpp

 
 /// Walk through the instructions in \p F looking for external
 /// calls not already in the \p CalledFunctions set. If any are
 /// found they are added to the \p Worklist for importing.
 static void findExternalCalls(const Module &DestModule, Function &F,
                               const FunctionInfoIndex &Index,
                               StringSet<> &CalledFunctions,
                               SmallVector<StringRef, 64> &Worklist) {
-  // We need to suffix internal function calls imported from other modules,
-  // prepare the suffix ahead of time.
-  std::string Suffix;
-  if (F.getParent() != &DestModule)
-    Suffix =
-        (Twine(".llvm.") +
-         Twine(Index.getModuleId(F.getParent()->getModuleIdentifier()))).str();
-
   for (auto &BB : F) {
     for (auto &I : BB) {
       if (isa<CallInst>(I)) {
         auto CalledFunction = cast<CallInst>(I).getCalledFunction();
         // Insert any new external calls that have not already been
         // added to set/worklist.
         if (!CalledFunction || !CalledFunction->hasName())
           continue;
         // Ignore intrinsics early
         if (CalledFunction->isIntrinsic()) {
           assert(CalledFunction->getIntrinsicID() != 0);
           continue;
         }
-        auto ImportedName = CalledFunction->getName();
-        auto Renamed = (ImportedName + Suffix).str();
-        // Rename internal functions
-        if (CalledFunction->hasInternalLinkage()) {
-          ImportedName = Renamed;
-        }
+        auto ImportedName = Function::getGlobalIdentifier(
+            CalledFunction->getName(), CalledFunction->getLinkage(),
+            CalledFunction->getParent()->getSourceFileName());
         auto It = CalledFunctions.insert(ImportedName);
         if (!It.second) {
           // This is a call to a function we already considered, skip.
           continue;
         }
         // Ignore functions already present in the destination module
         auto *SrcGV = DestModule.getNamedValue(ImportedName);
         if (SrcGV) {
DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Importing "
                  << CalledFunctionName << " from " << ModuleIdentifier << "\n");
 
     auto &SrcModule = ModuleLoaderCache(ModuleIdentifier);
 
     // The function that we will import!
     GlobalValue *SGV = SrcModule.getNamedValue(CalledFunctionName);
 
     if (!SGV) {
-      // The destination module is referencing function using their renamed name
-      // when importing a function that was originally local in the source
-      // module. The source module we have might not have been renamed so we try
-      // to remove the suffix added during the renaming to recover the original
+      // The function is referenced by a global identifier, which has the
+      // source file name prepended for functions that were originally local
+      // in the source module. Strip any prepended name to recover the original
       // name in the source module.
-      std::pair<StringRef, StringRef> Split =
-          CalledFunctionName.split(".llvm.");
-      SGV = SrcModule.getNamedValue(Split.first);
+      std::pair<StringRef, StringRef> Split = CalledFunctionName.split(":");
+      SGV = SrcModule.getNamedValue(Split.second);
       assert(SGV && "Can't find function to import in source module");
     }
     if (!SGV) {
       report_fatal_error(Twine("Can't load function '") + CalledFunctionName +
                          "' in Module '" + SrcModule.getModuleIdentifier() +
                          "', error in the summary?\n");
     }
 

test/tools/gold/X86/thinlto.ll

 ; COMBINED-NEXT: <ENTRY {{.*}} record string = '{{.*}}/test/tools/gold/X86/Output/thinlto.ll.tmp{{.*}}.o'
 ; COMBINED-NEXT: <ENTRY {{.*}} record string = '{{.*}}/test/tools/gold/X86/Output/thinlto.ll.tmp{{.*}}.o'
 ; COMBINED-NEXT: </MODULE_STRTAB_BLOCK
 ; COMBINED-NEXT: <FUNCTION_SUMMARY_BLOCK
 ; COMBINED-NEXT: <COMBINED_ENTRY
 ; COMBINED-NEXT: <COMBINED_ENTRY
 ; COMBINED-NEXT: </FUNCTION_SUMMARY_BLOCK
 ; COMBINED-NEXT: <VALUE_SYMTAB
-; COMBINED-NEXT: <COMBINED_FNENTRY {{.*}} record string = '{{f|g}}'
-; COMBINED-NEXT: <COMBINED_FNENTRY {{.*}} record string = '{{f|g}}'
+; COMBINED-NEXT: <COMBINED_FNENTRY {{.*}}
+; COMBINED-NEXT: <COMBINED_FNENTRY {{.*}}
 ; COMBINED-NEXT: </VALUE_SYMTAB
 
 define void @f() {
 entry:
   ret void
 }

test/tools/llvm-lto/thinlto.ll

 ; Test combined function index generation for ThinLTO via llvm-lto.
 ; RUN: llvm-as -function-summary %s -o %t.o
 ; RUN: llvm-as -function-summary %p/Inputs/thinlto.ll -o %t2.o
 ; RUN: llvm-lto -thinlto -o %t3 %t.o %t2.o
 ; RUN: llvm-bcanalyzer -dump %t3.thinlto.bc | FileCheck %s --check-prefix=COMBINED
 ; RUN: not test -e %t3
 
 ; COMBINED: <MODULE_STRTAB_BLOCK
 ; COMBINED-NEXT: <ENTRY {{.*}} record string = '{{.*}}thinlto.ll.tmp{{.*}}.o'
 ; COMBINED-NEXT: <ENTRY {{.*}} record string = '{{.*}}thinlto.ll.tmp{{.*}}.o'
 ; COMBINED-NEXT: </MODULE_STRTAB_BLOCK
 ; COMBINED-NEXT: <FUNCTION_SUMMARY_BLOCK
 ; COMBINED-NEXT: <COMBINED_ENTRY
 ; COMBINED-NEXT: <COMBINED_ENTRY
 ; COMBINED-NEXT: </FUNCTION_SUMMARY_BLOCK
 ; COMBINED-NEXT: <VALUE_SYMTAB
-; COMBINED-NEXT: <COMBINED_FNENTRY {{.*}} record string = '{{f|g}}'
-; COMBINED-NEXT: <COMBINED_FNENTRY {{.*}} record string = '{{f|g}}'
+; COMBINED-NEXT: <COMBINED_FNENTRY {{.*}}
+; COMBINED-NEXT: <COMBINED_FNENTRY {{.*}}
 ; COMBINED-NEXT: </VALUE_SYMTAB
 
 define void @f() {
 entry:
   ret void
 }

tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

default: return nullptr;
       STRINGIFY_CODE(MODULE_CODE, DEPLIB) // FIXME: Remove in 4.0
       STRINGIFY_CODE(MODULE_CODE, GLOBALVAR)
       STRINGIFY_CODE(MODULE_CODE, FUNCTION)
       STRINGIFY_CODE(MODULE_CODE, ALIAS)
       STRINGIFY_CODE(MODULE_CODE, PURGEVALS)
       STRINGIFY_CODE(MODULE_CODE, GCNAME)
       STRINGIFY_CODE(MODULE_CODE, VSTOFFSET)
       STRINGIFY_CODE(MODULE_CODE, METADATA_VALUES)
+      STRINGIFY_CODE(MODULE_CODE, SOURCE_FILENAME)
     }
   case bitc::IDENTIFICATION_BLOCK_ID:
     switch (CodeID) {
     default:
       return nullptr;
       STRINGIFY_CODE(IDENTIFICATION_CODE, STRING)
       STRINGIFY_CODE(IDENTIFICATION_CODE, EPOCH)
     }