[ThinLTO] Efficiency fix for writing type id records in per-module indexes

[tejohnson]

Summary

In D49565/r337503, the type id record writing was fixed so that only
referenced type ids were emitted into each per-module index for ThinLTO
distributed builds. However, this still left an efficiency issue: each
per-module index checked all type ids for membership in the referenced
set, yielding O(M*N) performance (M indexes and N type ids).

This patch changes the writer so that when writing per-module indexes
we instead walk the referenced set, and write the corresponding type id
summary. Since the references are GUIDs but the type id map is indexed
by string, we utilize a map from GUID to type id map entry. This map was
already being created for in-process backends (for caching purposes),
so I moved it to the ThinLTO backend base class and pass it to the
bitcode index writer.

For writing combined indexes we don't build this map and fall back to
the old behavior, which minimized the number of callsites into the index
writer that required changes (but added an assert to check that we
always have the new map when writing per-module indexes where the
performance is going to be an issue).

For a large internal application, this reduced the thin link time by
almost 15%.

[tejohnson]

include/llvm/IR/ModuleSummaryIndex.h

744

@pcc - do you remember why you used a vector as the map value type? Presumably there should be a 1-1 ratio between the GUIDs computed from type ids and the type id map entry, but is this to handle the potential for GUID conflicts?

[pcc]

Did you consider changing the type id mapping data structure in ModuleSummaryIndex instead of creating a new one? Since we now use a mapping from guids in several places it seems sensible to do that. I think that it would work to change the type of TypeIdMap to something like:

DenseMap<GlobalValue::GUID, TinyPtrVector<std::pair<std::string, TypeIdSummary>>>

include/llvm/IR/ModuleSummaryIndex.h

744

Yes, it was for guid conflicts.

[tejohnson]

In D51330#1218260, @pcc wrote:

Did you consider changing the type id mapping data structure in ModuleSummaryIndex instead of creating a new one? Since we now use a mapping from guids in several places it seems sensible to do that. I think that it would work to change the type of TypeIdMap to something like:

DenseMap<GlobalValue::GUID, TinyPtrVector<std::pair<std::string, TypeIdSummary>>>

Sure, I will do that. Looking at the use sites, I don't think we technically need to keep the name. The only place where we seem to really need it is when writing out the type id summaries to assembly, but it is nice from a readability perspective to have the name. It likely isn't going to be high overhead to keep both, so we might as well.

[tejohnson]

include/llvm/IR/ModuleSummaryIndex.h

744

These should be rare and from what I can tell, if we only track one type id per conflicting GUID (since we will also have the type id string to disambiguate), the worst that will happen is that we wouldn't get a resolution and it would result in conservative behavior. Is that correct? Or do we need to track them all for correct behavior?

I realized when looking at changing this that currently the assembly writer will not behave well in the presence of conflicts, since the slot ID for the summary entry is assigned by GUID.

If we can get by with it, the implementation would be simpler if we simply tracked one (and like I said, disambiguate via the std::string saved in the value).

[tejohnson]

include/llvm/IR/ModuleSummaryIndex.h

744

My new patch does away with the vector of summaries for each GUID. The interface to get a summary and the clients are changed to handle this - which I believe is conservative. If my interpretation of this as being conservative is incorrect please let me know.

[tejohnson]

Change the TypeIdMap in summary to be indexed by GUID.

A few tests changed because the order of serialization changed a bit
(iterating in GUID order instead of string order).

[pcc]

include/llvm/IR/ModuleSummaryIndex.h

744

There's no conservative behaviour for type id resolutions, they need to be correct or we will miscompile (e.g. by forming a CFI check incorrectly).

[tejohnson]

include/llvm/IR/ModuleSummaryIndex.h

744

Ok. I assumed that the return of the Unsat kind at the start of LowerTypeTestsModule::importTypeId when there is not a type id summary in the index would lead to conservative checking in that scenario. What situation is that handling?

[pcc]

include/llvm/IR/ModuleSummaryIndex.h

744

Unsat is for handling the case where there is a call with no possible targets. For example a vcall where all vtables of that type have been dead stripped. In that case we compile the check so that it always fails. The reason why we return unsat when there are no type id summaries is that the absence of any vtables with a type id would lead to no summary for that type id being created.

[tejohnson]

include/llvm/IR/ModuleSummaryIndex.h

744

I see, thanks for the explanation.

I suppose I should first fix the assembly printing for type ids so that the slot is based on the string and not on its GUID. Should be straightforward - I'll fix that first separately and update this patch to go to a vector of type summaries per GUID in the map afterwards.

[tejohnson]

include/llvm/IR/ModuleSummaryIndex.h

744

Nevermind on this - I realized I needed a GUID-to-typeid map to fix this, so I decided to incorporate it into the change I was making here to the map type.

[tejohnson]

Change to use a map to a vector of matching type id, summary pairs

[tejohnson]

ping

[tejohnson]

ping

[vitalybuka]

include/llvm/IR/ModuleSummaryIndex.h

760

Have you considered multimap?

using TypeIdSummaryMapTy =
    std::multimap<GlobalValue::GUID, std::pair<std::string, TypeIdSummary>>;

Not sure, but maybe code could be a little bit simpler with it.

lib/IR/AsmWriter.cpp

2926

So now we can have multiple entries here. Would be nice to reach this with a test?

2969

Test?

[vitalybuka]

LGTM regardless of your decision about my comment.

include/llvm/IR/ModuleSummaryIndex.h

26

unused?

[tejohnson]

include/llvm/IR/ModuleSummaryIndex.h

760

Changed the code to use multimap.

lib/IR/AsmWriter.cpp

2926

This requires identifying two strings that result in an MD5 collision, which should be extremely rare. I found an example on the web but it is in hex and does not convert to a valid string. So I'm not really sure how to test this.

2969

Ditto.

[tejohnson]

Use multimap

include/llvm/IR/ModuleSummaryIndex.h

 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/ScaledNumber.h"
 #include "llvm/Support/StringSaver.h"
 #include <algorithm>
 #include <array>
struct TypeIdSummary {
   /// Mapping from byte offset to whole-program devirt resolution for that
   /// (typeid, byte offset) pair.
   std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
 };
 
 /// 160 bits SHA1
 using ModuleHash = std::array<uint32_t, 5>;
 
 /// Type used for iterating through the global value summary map.
 using const_gvsummary_iterator = GlobalValueSummaryMapTy::const_iterator;
 using gvsummary_iterator = GlobalValueSummaryMapTy::iterator;
 
 /// String table to hold/own module path strings, which additionally holds the
 /// module ID assigned to each module during the plugin step, as well as a hash
 /// of the module. The StringMap makes a copy of and owns inserted strings.
 using ModulePathStringTableTy = StringMap<std::pair<uint64_t, ModuleHash>>;
 
 /// Map of global value GUID to its summary, used to identify values defined in
 /// a particular module, and provide efficient access to their summary.
 using GVSummaryMapTy = DenseMap<GlobalValue::GUID, GlobalValueSummary *>;
 
+/// Map of a type GUID to vector of type id string and summary (vector
+/// in case of GUID conflicts).
+using TypeIdSummaryMapTy =
+    std::map<GlobalValue::GUID,
+             std::vector<std::pair<std::string, TypeIdSummary>>>;
+
 /// Class to hold module path string table and global value map,
 /// and encapsulate methods for operating on them.
 class ModuleSummaryIndex {
 private:
   /// Map from value name to list of summary instances for values of that
   /// name (may be duplicates in the COMDAT case, e.g.).
   GlobalValueSummaryMapTy GlobalValueMap;
 
   /// Holds strings for combined index, mapping to the corresponding module ID.
   ModulePathStringTableTy ModulePathStringTable;
 
-  /// Mapping from type identifiers to summary information for that type
-  /// identifier.
-  std::map<std::string, TypeIdSummary> TypeIdMap;
+  /// Mapping from type identifier GUIDs to type identifier and its summary
+  /// information.
+  TypeIdSummaryMapTy TypeIdMap;
 
   /// Mapping from original ID to GUID. If original ID can map to multiple
   /// GUIDs, it will be mapped to 0.
   std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
 
   /// Indicates that summary-based GlobalValue GC has run, and values with
   /// GVFlags::Live==false are really dead. Otherwise, all values must be
   /// considered live.
public:
 
   /// Check if the given Module has any functions available for exporting
   /// in the index. We consider any module present in the ModulePathStringTable
   /// to have exported functions.
   bool hasExportedFunctions(const Module &M) const {
     return ModulePathStringTable.count(M.getModuleIdentifier());
   }
 
-  const std::map<std::string, TypeIdSummary> &typeIds() const {
-    return TypeIdMap;
-  }
+  const TypeIdSummaryMapTy &typeIds() const { return TypeIdMap; }
 
-  /// This accessor should only be used when exporting because it can mutate the
-  /// map.
+  /// Return an existing or new TypeIdSummary entry for \p TypeId.
+  /// This accessor can mutate the map and therefore should not be used in
+  /// the ThinLTO backends.
   TypeIdSummary &getOrInsertTypeIdSummary(StringRef TypeId) {
-    return TypeIdMap[TypeId];
+    auto &Tid = TypeIdMap[GlobalValue::getGUID(TypeId)];
+    for (auto &P : Tid)
+      if (P.first == TypeId)
+        return P.second;
+    Tid.push_back({TypeId, TypeIdSummary()});
+    return Tid.back().second;
   }
 
   /// This returns either a pointer to the type id summary (if present in the
   /// summary map) or null (if not present). This may be used when importing.
   const TypeIdSummary *getTypeIdSummary(StringRef TypeId) const {
-    auto I = TypeIdMap.find(TypeId);
+    auto I = TypeIdMap.find(GlobalValue::getGUID(TypeId));
     if (I == TypeIdMap.end())
       return nullptr;
-    return &I->second;
+    for (auto &P : I->second)
+      if (P.first == TypeId)
+        return &P.second;
+    return nullptr;
   }
 
   /// Collect for the given module the list of functions it defines
   /// (GUID -> Summary).
   void collectDefinedFunctionsForModule(StringRef ModulePath,
                                         GVSummaryMapTy &GVSummaryMap) const;
 
   /// Collect for each module the list of Summaries it defines (GUID ->

include/llvm/IR/ModuleSummaryIndexYAML.h

static void mapping(IO &io, FunctionSummaryYaml& summary) {
     io.mapOptional("TypeCheckedLoadConstVCalls",
                    summary.TypeCheckedLoadConstVCalls);
   }
 };
 
 } // End yaml namespace
 } // End llvm namespace
 
-LLVM_YAML_IS_STRING_MAP(TypeIdSummary)
 LLVM_YAML_IS_SEQUENCE_VECTOR(FunctionSummaryYaml)
 
 namespace llvm {
 namespace yaml {
 
 // FIXME: Add YAML mappings for the rest of the module summary.
 template <> struct CustomMappingTraits<GlobalValueSummaryMapTy> {
   static void inputOne(IO &io, StringRef Key, GlobalValueSummaryMapTy &V) {
for (auto &P : V) {
           }
       }
       if (!FSums.empty())
         io.mapRequired(llvm::utostr(P.first).c_str(), FSums);
     }
   }
 };
 
+template <> struct CustomMappingTraits<TypeIdSummaryMapTy> {
+  static void inputOne(IO &io, StringRef Key, TypeIdSummaryMapTy &V) {
+    auto &TIS = V[GlobalValue::getGUID(Key)];
+    TypeIdSummary TId;
+    io.mapRequired(Key.str().c_str(), TId);
+    TIS.push_back({Key, TId});
+  }
+  static void output(IO &io, TypeIdSummaryMapTy &V) {
+    for (auto &Tids : V)
+      for (auto &P : Tids.second)
+        io.mapRequired(P.first.c_str(), P.second);
+  }
+};
+
 template <> struct MappingTraits<ModuleSummaryIndex> {
   static void mapping(IO &io, ModuleSummaryIndex& index) {
     io.mapOptional("GlobalValueMap", index.GlobalValueMap);
     io.mapOptional("TypeIdMap", index.TypeIdMap);
     io.mapOptional("WithGlobalValueDeadStripping",
                    index.WithGlobalValueDeadStripping);
 
     if (io.outputting()) {

lib/Bitcode/Writer/BitcodeWriter.cpp

if (!Index.cfiFunctionDecls().empty()) {
     for (auto &S : Index.cfiFunctionDecls()) {
       NameVals.push_back(StrtabBuilder.add(S));
       NameVals.push_back(S.size());
     }
     Stream.EmitRecord(bitc::FS_CFI_FUNCTION_DECLS, NameVals);
     NameVals.clear();
   }
 
-  if (!Index.typeIds().empty()) {
-    for (auto &S : Index.typeIds()) {
-      // Skip if not referenced in any GV summary within this index file.
-      if (!ReferencedTypeIds.count(GlobalValue::getGUID(S.first)))
-        continue;
-      writeTypeIdSummaryRecord(NameVals, StrtabBuilder, S.first, S.second);
+  // Walk the GUIDs that were referenced, and write the
+  // corresponding type id records.
+  for (auto &T : ReferencedTypeIds) {
+    auto S = Index.typeIds().find(T);
+    if (S == Index.typeIds().end())
+    for (auto &P : S->second) {
+      writeTypeIdSummaryRecord(NameVals, StrtabBuilder, P.first, P.second);
       Stream.EmitRecord(bitc::FS_TYPE_ID, NameVals);
       NameVals.clear();
     }
   }
 
   Stream.ExitBlock();
 }
 

lib/IR/AsmWriter.cpp

private:
   /// ModulePathMap - The slot map for Module paths used in the summary index.
   StringMap<unsigned> ModulePathMap;
   unsigned ModulePathNext = 0;
 
   /// GUIDMap - The slot map for GUIDs used in the summary index.
   DenseMap<GlobalValue::GUID, unsigned> GUIDMap;
   unsigned GUIDNext = 0;
 
+  /// TypeIdMap - The slot map for type ids used in the summary index.
+  StringMap<unsigned> TypeIdMap;
+  unsigned TypeIdNext = 0;
+
 public:
   /// Construct from a module.
   ///
   /// If \c ShouldInitializeAllMetadata, initializes all metadata in all
   /// functions, giving correct numbering for metadata referenced only from
   /// within a function (even if no functions have been initialized).
   explicit SlotTracker(const Module *M,
                        bool ShouldInitializeAllMetadata = false);
public:
   /// Return the slot number of the specified value in it's type
   /// plane.  If something is not in the SlotTracker, return -1.
   int getLocalSlot(const Value *V);
   int getGlobalSlot(const GlobalValue *V);
   int getMetadataSlot(const MDNode *N);
   int getAttributeGroupSlot(AttributeSet AS);
   int getModulePathSlot(StringRef Path);
   int getGUIDSlot(GlobalValue::GUID GUID);
+  int getTypeIdSlot(StringRef Id);
 
   /// If you'd like to deal with a function instead of just a module, use
   /// this method to get its data into the SlotTracker.
   void incorporateFunction(const Function *F) {
     TheFunction = F;
     FunctionProcessed = false;
   }
 
private:
   /// CreateFunctionSlot - Insert the specified Value* into the slot table.
   void CreateFunctionSlot(const Value *V);
 
   /// Insert the specified AttributeSet into the slot table.
   void CreateAttributeSetSlot(AttributeSet AS);
 
   inline void CreateModulePathSlot(StringRef Path);
   void CreateGUIDSlot(GlobalValue::GUID GUID);
+  void CreateTypeIdSlot(StringRef Id);
 
   /// Add all of the module level global variables (and their initializers)
   /// and function declarations, but not the contents of those functions.
   void processModule();
   void processIndex();
 
   /// Add all of the functions arguments, basic blocks, and instructions.
   void processFunction();
for (auto &ModPair : ModuleIdToPathMap)
     CreateModulePathSlot(ModPair.second);
 
   // Start numbering the GUIDs after the module ids.
   GUIDNext = ModulePathNext;
 
   for (auto &GlobalList : *TheIndex)
     CreateGUIDSlot(GlobalList.first);
 
+  // Start numbering the TypeIds after the GUIDs.
+  TypeIdNext = GUIDNext;
+
   for (auto &TId : TheIndex->typeIds())
-    CreateGUIDSlot(GlobalValue::getGUID(TId.first));
+    for (auto P : TId.second)
+      CreateTypeIdSlot(P.first);
 
   ST_DEBUG("end processIndex!\n");
 }
 
 void SlotTracker::processGlobalObjectMetadata(const GlobalObject &GO) {
   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
   GO.getAllMetadata(MDs);
   for (auto &MD : MDs)
int SlotTracker::getGUIDSlot(GlobalValue::GUID GUID) {
   // Check for uninitialized state and do lazy initialization.
   initializeIndexIfNeeded();
 
   // Find the GUID in the map
   guid_iterator I = GUIDMap.find(GUID);
   return I == GUIDMap.end() ? -1 : (int)I->second;
 }
 
+int SlotTracker::getTypeIdSlot(StringRef Id) {
+  // Check for uninitialized state and do lazy initialization.
+  initializeIndexIfNeeded();
+
+  // Find the TypeId string in the map
+  auto I = TypeIdMap.find(Id);
+  return I == TypeIdMap.end() ? -1 : (int)I->second;
+}
+
 /// CreateModuleSlot - Insert the specified GlobalValue* into the slot table.
 void SlotTracker::CreateModuleSlot(const GlobalValue *V) {
   assert(V && "Can't insert a null Value into SlotTracker!");
   assert(!V->getType()->isVoidTy() && "Doesn't need a slot!");
   assert(!V->hasName() && "Doesn't need a slot!");
 
   unsigned DestSlot = mNext++;
   mMap[V] = DestSlot;
void SlotTracker::CreateModulePathSlot(StringRef Path) {
   ModulePathMap[Path] = ModulePathNext++;
 }
 
 /// Create a new slot for the specified GUID
 void SlotTracker::CreateGUIDSlot(GlobalValue::GUID GUID) {
   GUIDMap[GUID] = GUIDNext++;
 }
 
+/// Create a new slot for the specified Id
+void SlotTracker::CreateTypeIdSlot(StringRef Id) {
+  TypeIdMap[Id] = TypeIdNext++;
+}
+
 //===----------------------------------------------------------------------===//
 // AsmWriter Implementation
 //===----------------------------------------------------------------------===//
 
 static void WriteAsOperandInternal(raw_ostream &Out, const Value *V,
                                    TypePrinting *TypePrinter,
                                    SlotTracker *Machine,
                                    const Module *Context);
void AssemblyWriter::printModuleSummaryIndex() {
   for (auto &GlobalList : *TheIndex) {
     auto GUID = GlobalList.first;
     auto VI = TheIndex->getValueInfo(GlobalList);
     printSummaryInfo(Machine.getGUIDSlot(GUID), VI);
   }
 
   // Print the TypeIdMap entries.
   for (auto &TId : TheIndex->typeIds()) {
-    auto GUID = GlobalValue::getGUID(TId.first);
-    Out << "^" << Machine.getGUIDSlot(GUID) << " = typeid: (name: \""
-        << TId.first << "\"";
-    printTypeIdSummary(TId.second);
-    Out << ") ; guid = " << GUID << "\n";
+    for (auto P : TId.second) {
+      Out << "^" << Machine.getTypeIdSlot(P.first) << " = typeid: (name: \""
+          << P.first << "\"";
+      printTypeIdSummary(P.second);
+      Out << ") ; guid = " << TId.first << "\n";
+    }
   }
 }
 
 static const char *
 getWholeProgDevirtResKindName(WholeProgramDevirtResolution::Kind K) {
   switch (K) {
   case WholeProgramDevirtResolution::Indir:
     return "indir";
void AssemblyWriter::printTypeIdInfo(
     const FunctionSummary::TypeIdInfo &TIDInfo) {
   Out << ", typeIdInfo: (";
   FieldSeparator TIDFS;
   if (!TIDInfo.TypeTests.empty()) {
     Out << TIDFS;
     Out << "typeTests: (";
     FieldSeparator FS;
     for (auto &GUID : TIDInfo.TypeTests) {
+      auto I = TheIndex->typeIds().find(GUID);
+      if (I == TheIndex->typeIds().end()) {
         Out << FS;
-      auto Slot = Machine.getGUIDSlot(GUID);
-      if (Slot != -1)
-        Out << "^" << Slot;
-      else
         Out << GUID;
+        continue;
+      }
+      // Print all type id that correspond to this GUID.
+      for (auto &Tid : I->second) {
+        Out << FS;
+        auto Slot = Machine.getTypeIdSlot(Tid.first);
+        assert(Slot != -1);
+        Out << "^" << Slot;
+      }
     }
     Out << ")";
   }
   if (!TIDInfo.TypeTestAssumeVCalls.empty()) {
     Out << TIDFS;
     printNonConstVCalls(TIDInfo.TypeTestAssumeVCalls, "typeTestAssumeVCalls");
   }
   if (!TIDInfo.TypeCheckedLoadVCalls.empty()) {
if (!TIDInfo.TypeCheckedLoadConstVCalls.empty()) {
     Out << TIDFS;
     printConstVCalls(TIDInfo.TypeCheckedLoadConstVCalls,
                      "typeCheckedLoadConstVCalls");
   }
   Out << ")";
 }
 
 void AssemblyWriter::printVFuncId(const FunctionSummary::VFuncId VFId) {
+  auto I = TheIndex->typeIds().find(VFId.GUID);
+  if (I == TheIndex->typeIds().end()) {
     Out << "vFuncId: (";
-  auto Slot = Machine.getGUIDSlot(VFId.GUID);
-  if (Slot != -1)
-    Out << "^" << Slot;
-  else
     Out << "guid: " << VFId.GUID;
     Out << ", offset: " << VFId.Offset;
     Out << ")";
+    return;
+  }
+  // Print all type id that correspond to this GUID.
+  FieldSeparator FS;
+  for (auto &Tid : I->second) {
+    Out << FS;
+    Out << "vFuncId: (";
+    auto Slot = Machine.getTypeIdSlot(Tid.first);
+    assert(Slot != -1);
+    Out << "^" << Slot;
+    Out << ", offset: " << VFId.Offset;
+    Out << ")";
+  }
 }
 
 void AssemblyWriter::printNonConstVCalls(
     const std::vector<FunctionSummary::VFuncId> VCallList, const char *Tag) {
   Out << Tag << ": (";
   FieldSeparator FS;
   for (auto &VFuncId : VCallList) {
     Out << FS;

lib/LTO/LTO.cpp

 using namespace object;
 
 #define DEBUG_TYPE "lto"
 
 static cl::opt<bool>
     DumpThinCGSCCs("dump-thin-cg-sccs", cl::init(false), cl::Hidden,
                    cl::desc("Dump the SCCs in the ThinLTO index's callgraph"));
 
-// The values are (type identifier, summary) pairs.
-typedef DenseMap<
-    GlobalValue::GUID,
-    TinyPtrVector<const std::pair<const std::string, TypeIdSummary> *>>
-    TypeIdSummariesByGuidTy;
-
 // Returns a unique hash for the Module considering the current list of
 // export/import and other global analysis results.
 // The hash is produced in \p Key.
 static void computeCacheKey(
     SmallString<40> &Key, const Config &Conf, const ModuleSummaryIndex &Index,
     StringRef ModuleID, const FunctionImporter::ImportMapTy &ImportList,
     const FunctionImporter::ExportSetTy &ExportList,
     const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
     const GVSummaryMapTy &DefinedGlobals,
-    const TypeIdSummariesByGuidTy &TypeIdSummariesByGuid,
     const std::set<GlobalValue::GUID> &CfiFunctionDefs,
     const std::set<GlobalValue::GUID> &CfiFunctionDecls) {
   // Compute the unique hash for this entry.
   // This is based on the current compiler version, the module itself, the
   // export list, the hash for every single module in the import list, the
   // list of ResolvedODR for the module, and the list of preserved symbols.
   SHA1 Hasher;
 
for (auto &WPD : S.WPDRes) {
         AddUnsigned(ByArg.second.Byte);
         AddUnsigned(ByArg.second.Bit);
       }
     }
   };
 
   // Include the hash for all type identifiers used by this module.
   for (GlobalValue::GUID TId : UsedTypeIds) {
-    auto SummariesI = TypeIdSummariesByGuid.find(TId);
-    if (SummariesI != TypeIdSummariesByGuid.end())
-      for (auto *Summary : SummariesI->second)
-        AddTypeIdSummary(Summary->first, Summary->second);
+    auto SummariesI = Index.typeIds().find(TId);
+    if (SummariesI != Index.typeIds().end())
+      for (auto S : SummariesI->second)
+        AddTypeIdSummary(S.first, S.second);
   }
 
   AddUnsigned(UsedCfiDefs.size());
   for (auto &V : UsedCfiDefs)
     AddUint64(V);
 
   AddUnsigned(UsedCfiDecls.size());
   for (auto &V : UsedCfiDecls)
public:
   virtual Error wait() = 0;
 };
 
 namespace {
 class InProcessThinBackend : public ThinBackendProc {
   ThreadPool BackendThreadPool;
   AddStreamFn AddStream;
   NativeObjectCache Cache;
-  TypeIdSummariesByGuidTy TypeIdSummariesByGuid;
   std::set<GlobalValue::GUID> CfiFunctionDefs;
   std::set<GlobalValue::GUID> CfiFunctionDecls;
 
   Optional<Error> Err;
   std::mutex ErrMu;
 
 public:
   InProcessThinBackend(
       Config &Conf, ModuleSummaryIndex &CombinedIndex,
       unsigned ThinLTOParallelismLevel,
       const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
       AddStreamFn AddStream, NativeObjectCache Cache)
       : ThinBackendProc(Conf, CombinedIndex, ModuleToDefinedGVSummaries),
         BackendThreadPool(ThinLTOParallelismLevel),
         AddStream(std::move(AddStream)), Cache(std::move(Cache)) {
-    // Create a mapping from type identifier GUIDs to type identifier summaries.
-    // This allows backends to use the type identifier GUIDs stored in the
-    // function summaries to determine which type identifier summaries affect
-    // each function without needing to compute GUIDs in each backend.
-    for (auto &TId : CombinedIndex.typeIds())
-      TypeIdSummariesByGuid[GlobalValue::getGUID(TId.first)].push_back(&TId);
     for (auto &Name : CombinedIndex.cfiFunctionDefs())
       CfiFunctionDefs.insert(
           GlobalValue::getGUID(GlobalValue::dropLLVMManglingEscape(Name)));
     for (auto &Name : CombinedIndex.cfiFunctionDecls())
       CfiFunctionDecls.insert(
           GlobalValue::getGUID(GlobalValue::dropLLVMManglingEscape(Name)));
   }
 
   Error runThinLTOBackendThread(
       AddStreamFn AddStream, NativeObjectCache Cache, unsigned Task,
       BitcodeModule BM, ModuleSummaryIndex &CombinedIndex,
       const FunctionImporter::ImportMapTy &ImportList,
       const FunctionImporter::ExportSetTy &ExportList,
       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
       const GVSummaryMapTy &DefinedGlobals,
-      MapVector<StringRef, BitcodeModule> &ModuleMap,
-      const TypeIdSummariesByGuidTy &TypeIdSummariesByGuid) {
+      MapVector<StringRef, BitcodeModule> &ModuleMap) {
     auto RunThinBackend = [&](AddStreamFn AddStream) {
       LTOLLVMContext BackendContext(Conf);
       Expected<std::unique_ptr<Module>> MOrErr = BM.parseModule(BackendContext);
       if (!MOrErr)
         return MOrErr.takeError();
 
       return thinBackend(Conf, Task, AddStream, **MOrErr, CombinedIndex,
                          ImportList, DefinedGlobals, ModuleMap);
     };
 
     auto ModuleID = BM.getModuleIdentifier();
 
     if (!Cache || !CombinedIndex.modulePaths().count(ModuleID) ||
         all_of(CombinedIndex.getModuleHash(ModuleID),
                [](uint32_t V) { return V == 0; }))
       // Cache disabled or no entry for this module in the combined index or
       // no module hash.
       return RunThinBackend(AddStream);
 
     SmallString<40> Key;
     // The module may be cached, this helps handling it.
     computeCacheKey(Key, Conf, CombinedIndex, ModuleID, ImportList, ExportList,
-                    ResolvedODR, DefinedGlobals, TypeIdSummariesByGuid,
-                    CfiFunctionDefs, CfiFunctionDecls);
+                    ResolvedODR, DefinedGlobals, CfiFunctionDefs,
+                    CfiFunctionDecls);
     if (AddStreamFn CacheAddStream = Cache(Task, Key))
       return RunThinBackend(CacheAddStream);
 
     return Error::success();
   }
 
   Error start(
       unsigned Task, BitcodeModule BM,
       const FunctionImporter::ImportMapTy &ImportList,
       const FunctionImporter::ExportSetTy &ExportList,
       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
       MapVector<StringRef, BitcodeModule> &ModuleMap) override {
     StringRef ModulePath = BM.getModuleIdentifier();
     assert(ModuleToDefinedGVSummaries.count(ModulePath));
     const GVSummaryMapTy &DefinedGlobals =
         ModuleToDefinedGVSummaries.find(ModulePath)->second;
     BackendThreadPool.async(
         [=](BitcodeModule BM, ModuleSummaryIndex &CombinedIndex,
             const FunctionImporter::ImportMapTy &ImportList,
             const FunctionImporter::ExportSetTy &ExportList,
             const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>
                 &ResolvedODR,
             const GVSummaryMapTy &DefinedGlobals,
-            MapVector<StringRef, BitcodeModule> &ModuleMap,
-            const TypeIdSummariesByGuidTy &TypeIdSummariesByGuid) {
+            MapVector<StringRef, BitcodeModule> &ModuleMap) {
           Error E = runThinLTOBackendThread(
               AddStream, Cache, Task, BM, CombinedIndex, ImportList, ExportList,
-              ResolvedODR, DefinedGlobals, ModuleMap, TypeIdSummariesByGuid);
+              ResolvedODR, DefinedGlobals, ModuleMap);
           if (E) {
             std::unique_lock<std::mutex> L(ErrMu);
             if (Err)
               Err = joinErrors(std::move(*Err), std::move(E));
             else
               Err = std::move(E);
           }
         },
         BM, std::ref(CombinedIndex), std::ref(ImportList), std::ref(ExportList),
-        std::ref(ResolvedODR), std::ref(DefinedGlobals), std::ref(ModuleMap),
-        std::ref(TypeIdSummariesByGuid));
+        std::ref(ResolvedODR), std::ref(DefinedGlobals), std::ref(ModuleMap));
     return Error::success();
   }
 
   Error wait() override {
     BackendThreadPool.wait();
     if (Err)
       return std::move(*Err);
     else

test/Assembler/thinlto-summary.ll

 ^19 = gv: (guid: 18, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 4, typeIdInfo: (typeTests: (^24, ^26)))))
 ^20 = gv: (guid: 19, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 8, typeIdInfo: (typeTestAssumeVCalls: (vFuncId: (^27, offset: 16))))))
 ^21 = gv: (guid: 20, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 5, typeIdInfo: (typeCheckedLoadVCalls: (vFuncId: (^25, offset: 16))))))
 ^22 = gv: (guid: 21, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 15, typeIdInfo: (typeTestAssumeConstVCalls: ((vFuncId: (^27, offset: 16), args: (42)), (vFuncId: (^27, offset: 24)))))))
 ^23 = gv: (guid: 22, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 5, typeIdInfo: (typeCheckedLoadConstVCalls: ((vFuncId: (^28, offset: 16), args: (42)))))))
 
 ; Test TypeId summaries:
 
-; Test the AllOnes resolution, and all kinds of WholeProgramDevirtResolution
-; types, including all optional resolution by argument kinds.
-^24 = typeid: (name: "_ZTS1A", summary: (typeTestRes: (kind: allOnes, sizeM1BitWidth: 7), wpdResolutions: ((offset: 0, wpdRes: (kind: branchFunnel)), (offset: 8, wpdRes: (kind: singleImpl, singleImplName: "_ZN1A1nEi")), (offset: 16, wpdRes: (kind: indir, resByArg: (args: (1, 2), byArg: (kind: indir, byte: 2, bit: 3), args: (3), byArg: (kind: uniformRetVal, info: 1), args: (4), byArg: (kind: uniqueRetVal, info: 1), args: (5), byArg: (kind: virtualConstProp)))))))
+^24 = typeid: (name: "_ZTS1C", summary: (typeTestRes: (kind: single, sizeM1BitWidth: 0)))
 ; Test TypeId with other optional fields (alignLog2/sizeM1/bitMask/inlineBits)
 ^25 = typeid: (name: "_ZTS1B", summary: (typeTestRes: (kind: inline, sizeM1BitWidth: 0, alignLog2: 1, sizeM1: 2, bitMask: 3, inlineBits: 4)))
+; Test the AllOnes resolution, and all kinds of WholeProgramDevirtResolution
+; types, including all optional resolution by argument kinds.
+^26 = typeid: (name: "_ZTS1A", summary: (typeTestRes: (kind: allOnes, sizeM1BitWidth: 7), wpdResolutions: ((offset: 0, wpdRes: (kind: branchFunnel)), (offset: 8, wpdRes: (kind: singleImpl, singleImplName: "_ZN1A1nEi")), (offset: 16, wpdRes: (kind: indir, resByArg: (args: (1, 2), byArg: (kind: indir, byte: 2, bit: 3), args: (3), byArg: (kind: uniformRetVal, info: 1), args: (4), byArg: (kind: uniqueRetVal, info: 1), args: (5), byArg: (kind: virtualConstProp)))))))
 ; Test the other kinds of type test resoultions
-^26 = typeid: (name: "_ZTS1C", summary: (typeTestRes: (kind: single, sizeM1BitWidth: 0)))
 ^27 = typeid: (name: "_ZTS1D", summary: (typeTestRes: (kind: byteArray, sizeM1BitWidth: 0)))
 ^28 = typeid: (name: "_ZTS1E", summary: (typeTestRes: (kind: unsat, sizeM1BitWidth: 0)))
 
 ; Make sure we get back from llvm-dis essentially what we put in via llvm-as.
 ; CHECK: ^0 = module: (path: "thinlto-summary1.o", hash: (1369602428, 2747878711, 259090915, 2507395659, 1141468049))
 ; CHECK: ^1 = module: (path: "thinlto-summary2.o", hash: (2998369023, 4283347029, 1195487472, 2757298015, 1852134156))
 ; CHECK: ^2 = gv: (guid: 1, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 10, calls: ((callee: ^15, hotness: hot), (callee: ^17, hotness: cold), (callee: ^16, hotness: none)), refs: (^13))))
 ; CHECK: ^3 = gv: (guid: 2, summaries: (function: (module: ^1, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 10, calls: ((callee: ^15)))))

 ; CHECK: ^16 = gv: (guid: 15, summaries: (function: (module: ^1, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 1, funcFlags: (readNone: 1, readOnly: 0, noRecurse: 1, returnDoesNotAlias: 0))))
 ; CHECK: ^17 = gv: (guid: 16, summaries: (function: (module: ^1, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 1, funcFlags: (readNone: 0, readOnly: 1, noRecurse: 0, returnDoesNotAlias: 1), calls: ((callee: ^15)))))
 ; CHECK: ^18 = gv: (guid: 17, summaries: (alias: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 1), aliasee: ^14)))
 ; CHECK: ^19 = gv: (guid: 18, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 4, typeIdInfo: (typeTests: (^24, ^26)))))
 ; CHECK: ^20 = gv: (guid: 19, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 8, typeIdInfo: (typeTestAssumeVCalls: (vFuncId: (^27, offset: 16))))))
 ; CHECK: ^21 = gv: (guid: 20, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 5, typeIdInfo: (typeCheckedLoadVCalls: (vFuncId: (^25, offset: 16))))))
 ; CHECK: ^22 = gv: (guid: 21, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 15, typeIdInfo: (typeTestAssumeConstVCalls: ((vFuncId: (^27, offset: 16), args: (42)), (vFuncId: (^27, offset: 24)))))))
 ; CHECK: ^23 = gv: (guid: 22, summaries: (function: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), insts: 5, typeIdInfo: (typeCheckedLoadConstVCalls: ((vFuncId: (^28, offset: 16), args: (42)))))))
-; CHECK: ^24 = typeid: (name: "_ZTS1A", summary: (typeTestRes: (kind: allOnes, sizeM1BitWidth: 7), wpdResolutions: ((offset: 0, wpdRes: (kind: branchFunnel)), (offset: 8, wpdRes: (kind: singleImpl, singleImplName: "_ZN1A1nEi")), (offset: 16, wpdRes: (kind: indir, resByArg: (args: (1, 2), byArg: (kind: indir, byte: 2, bit: 3), args: (3), byArg: (kind: uniformRetVal, info: 1), args: (4), byArg: (kind: uniqueRetVal, info: 1), args: (5), byArg: (kind: virtualConstProp))))))) ; guid = 7004155349499253778
+; CHECK: ^24 = typeid: (name: "_ZTS1C", summary: (typeTestRes: (kind: single, sizeM1BitWidth: 0))) ; guid = 1884921850105019584
 ; CHECK: ^25 = typeid: (name: "_ZTS1B", summary: (typeTestRes: (kind: inline, sizeM1BitWidth: 0, alignLog2: 1, sizeM1: 2, bitMask: 3, inlineBits: 4))) ; guid = 6203814149063363976
-; CHECK: ^26 = typeid: (name: "_ZTS1C", summary: (typeTestRes: (kind: single, sizeM1BitWidth: 0))) ; guid = 1884921850105019584
+; CHECK: ^26 = typeid: (name: "_ZTS1A", summary: (typeTestRes: (kind: allOnes, sizeM1BitWidth: 7), wpdResolutions: ((offset: 0, wpdRes: (kind: branchFunnel)), (offset: 8, wpdRes: (kind: singleImpl, singleImplName: "_ZN1A1nEi")), (offset: 16, wpdRes: (kind: indir, resByArg: (args: (1, 2), byArg: (kind: indir, byte: 2, bit: 3), args: (3), byArg: (kind: uniformRetVal, info: 1), args: (4), byArg: (kind: uniqueRetVal, info: 1), args: (5), byArg: (kind: virtualConstProp))))))) ; guid = 7004155349499253778
 ; CHECK: ^27 = typeid: (name: "_ZTS1D", summary: (typeTestRes: (kind: byteArray, sizeM1BitWidth: 0))) ; guid = 9614786172484273522
 ; CHECK: ^28 = typeid: (name: "_ZTS1E", summary: (typeTestRes: (kind: unsat, sizeM1BitWidth: 0))) ; guid = 17437243864166745132

test/Transforms/WholeProgramDevirt/branch-funnel.ll

 ; RUN: opt -S -wholeprogramdevirt %s | FileCheck --check-prefixes=CHECK,RETP %s
 ; RUN: sed -e 's,+retpoline,-retpoline,g' %s | opt -S -wholeprogramdevirt | FileCheck --check-prefixes=CHECK,NORETP %s
 
 ; RUN: opt -wholeprogramdevirt -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck --check-prefixes=CHECK,RETP %s
 
 ; RUN: opt -wholeprogramdevirt -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t  -O3 -S -o - %s | FileCheck --check-prefixes=CHECK %s
 
 ; RUN: FileCheck --check-prefix=SUMMARY %s < %t
 
 ; SUMMARY:      TypeIdMap:       
-; SUMMARY-NEXT:   typeid1:         
+; SUMMARY-NEXT:   typeid3:
 ; SUMMARY-NEXT:     TTRes:           
 ; SUMMARY-NEXT:       Kind:            Unsat
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:          
 ; SUMMARY-NEXT:       0:               
 ; SUMMARY-NEXT:         Kind:            BranchFunnel
 ; SUMMARY-NEXT:         SingleImplName:  ''
 ; SUMMARY-NEXT:         ResByArg:        
-; SUMMARY-NEXT:   typeid2:         
+; SUMMARY-NEXT:   typeid1:
 ; SUMMARY-NEXT:     TTRes:           
 ; SUMMARY-NEXT:       Kind:            Unsat
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:          
 ; SUMMARY-NEXT:       0:               
-; SUMMARY-NEXT:         Kind:            Indir
+; SUMMARY-NEXT:         Kind:            BranchFunnel
 ; SUMMARY-NEXT:         SingleImplName:  ''
 ; SUMMARY-NEXT:         ResByArg:        
-; SUMMARY-NEXT:   typeid3:         
+; SUMMARY-NEXT:   typeid2:
 ; SUMMARY-NEXT:     TTRes:           
 ; SUMMARY-NEXT:       Kind:            Unsat
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:          
 ; SUMMARY-NEXT:       0:               
-; SUMMARY-NEXT:         Kind:            BranchFunnel
+; SUMMARY-NEXT:         Kind:            Indir
 ; SUMMARY-NEXT:         SingleImplName:  ''
 ; SUMMARY-NEXT:         ResByArg:        
 
 target datalayout = "e-p:64:64"
 target triple = "x86_64-unknown-linux-gnu"
 
 @vt1_1 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1_1 to i8*)], !type !0
 @vt1_2 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1_2 to i8*)], !type !0

test/Transforms/WholeProgramDevirt/export-single-impl.ll

 ; RUN: opt -wholeprogramdevirt -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck %s
 ; RUN: FileCheck --check-prefix=SUMMARY %s < %t
 
 ; SUMMARY:      TypeIdMap:
-; SUMMARY-NEXT:   typeid1:
+; SUMMARY-NEXT:   typeid3:
 ; SUMMARY-NEXT:     TTRes:
 ; SUMMARY-NEXT:       Kind:            Unsat
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            SingleImpl
-; SUMMARY-NEXT:         SingleImplName:  vf1
+; SUMMARY-NEXT:         SingleImplName:  'vf3$merged'
 ; SUMMARY-NEXT:         ResByArg:
-; SUMMARY-NEXT:   typeid2:
+; SUMMARY-NEXT:   typeid1:
 ; SUMMARY-NEXT:     TTRes:
 ; SUMMARY-NEXT:       Kind:            Unsat
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            SingleImpl
-; SUMMARY-NEXT:         SingleImplName:  vf2
+; SUMMARY-NEXT:         SingleImplName:  vf1
 ; SUMMARY-NEXT:         ResByArg:
-; SUMMARY-NEXT:   typeid3:
+; SUMMARY-NEXT:   typeid2:
 ; SUMMARY-NEXT:     TTRes:
 ; SUMMARY-NEXT:       Kind:            Unsat
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0
 ; SUMMARY-NEXT:       InlineBits:      0
 ; SUMMARY-NEXT:     WPDRes:
 ; SUMMARY-NEXT:       0:
 ; SUMMARY-NEXT:         Kind:            SingleImpl
-; SUMMARY-NEXT:         SingleImplName:  'vf3$merged'
+; SUMMARY-NEXT:         SingleImplName:  vf2
 ; SUMMARY-NEXT:         ResByArg:
 ; SUMMARY-NEXT:   typeid4:
 ; SUMMARY-NEXT:     TTRes:
 ; SUMMARY-NEXT:       Kind:            Unsat
 ; SUMMARY-NEXT:       SizeM1BitWidth:  0
 ; SUMMARY-NEXT:       AlignLog2:       0
 ; SUMMARY-NEXT:       SizeM1:          0
 ; SUMMARY-NEXT:       BitMask:         0