IR: Use pointers instead of GUIDs to represent edges in the module summary. NFCI.

[pcc]

Summary

When profiling a no-op incremental link of Chromium I found that the functions
computeImportForFunction and computeDeadSymbols were consuming roughly 10% of
the profile. The goal of this change is to improve the performance of those
functions by changing the map lookups that they were previously doing into
pointer dereferences.

This is achieved by changing the ValueInfo data structure to be a pointer to
an element of the global value map owned by ModuleSummaryIndex, and changing
reference lists in the GlobalValueSummary to hold ValueInfos instead of GUIDs.
This means that a ValueInfo will take a client directly to the summary list
for a given GUID.

Depends on D32469

Depends on D32470

[tejohnson]

Nice compile time improvements! I didn't get too far, but have a few questions so far.

llvm/include/llvm/IR/ModuleSummaryIndex.h

557 ↗

(On Diff #96500)

Confused by something here - if getOrInsertValueInfo ends up inserting a new ValueInfo, it's Ref pointer will be null, but the below addGlobalValueSummary will unconditionally dereference it.

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

68 ↗

(On Diff #96500)

We should always be running the NameAnonGlobal pass before we build the index (when preparing for ThinLTO in the pass manager builder, event at -O0) to avoid needing such checks. Are you seeing somewhere that is not happening properly? There seem to be quite a few changes here where the hasName() guard was added.

Hmm, looks like were somewhat inconsistent about this. In several places in this file we assert that hasName(), but I see Davide added a guard to the AllRefsCanBeExternallyReferenced lambda a couple months ago. Can that occur outside of testing? I don't think so but maybe I am missing a case.

467 ↗

(On Diff #96500)

Why this added check? Previously we always asserted that we had a list of size 1. Are we inserting GUIDs into the index too eagarly now?

[pcc]

• Address review comments

llvm/include/llvm/IR/ModuleSummaryIndex.h

557 ↗

(On Diff #96500)

getOrInsertValueInfo ends up inserting a new ValueInfo, it's Ref pointer will be null,

That should never be the case. If it inserts, the Ref pointer should refer to the newly created map entry.

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

68 ↗

(On Diff #96500)

This particular change was necessary to handle the test case that Davide added in r295861 because we needed to be able to compute a GUID for any global reference. I discussed the change with him on IRC, and he agreed that we should revert it, so I did that in r301991.

Regarding the other changes related to anonymous globals, they seem unnecessary at this point, so I've undone them as well.

467 ↗

(On Diff #96500)

Yes, when we see a reference we need to add a GUID to the index. If the reference is undefined in the current module the summary list will be empty.

[tejohnson]

Looks pretty good, just a few more comments/questions.

llvm/include/llvm/IR/ModuleSummaryIndex.h

557 ↗

(On Diff #96500)

You're right, nevermind.

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

467 ↗

(On Diff #96500)

Ah ok, previously the index only held entries for defined globals, now it contains entries for all referenced globals as well. Maybe add a comment above the empty check (checking if the global is defined in this module).

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

705 ↗

(On Diff #97540)

Name and description need update. Is there a good reason to switch from a map to a std::vector? It makes the update code messier because you always have to check for a resize.

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

3274 ↗

(On Diff #97540)

When would a declaration have !VI - would that be a declaration that isn't referenced?

llvm/lib/Transforms/IPO/FunctionImport.cpp

196 ↗

(On Diff #97540)

What if VI also has an empty summary list?

436 ↗

(On Diff #97540)

Can this loop be merged with the earlier one that builds the initial LiveSymbols set?

472 ↗

(On Diff #97540)

Should the OriginalName in the AliasSummary also be saved as a ValueInfo instead of GUID (not necessary in this patch, but as a follow on)?

[pcc]

• Address review comments

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

705 ↗

(On Diff #97540)

I saw this as a potential perf improvement, but admittedly I hadn't profiled it in isolation.

I've reverted it for now and if it comes up again we can reconsider.

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

3274 ↗

(On Diff #97540)

Yes, I think that's the only case where that can happen.

llvm/lib/Transforms/IPO/FunctionImport.cpp

196 ↗

(On Diff #97540)

We will fall through and enter selectCallee which will return nullptr, so we will not import anything for this call.

472 ↗

(On Diff #97540)

Maybe. If I get a chance I want to rethink how we represent aliases in the summary. I think it should be possible to represent them using either a FunctionSummary or GlobalValueSummary built using the aliasee.

[tejohnson]

LGTM

[mehdi_amini]

llvm/trunk/include/llvm/IR/ModuleSummaryIndex.h

54

I don't understand why/where this is needed/used, the comment does not seem enough here.
It seems to me that this make the in-memory CombinedIndex unnecessary larger.

73

The doc here does not seem complete/accurate

81

There is no doc about when this is valid.

I feel the invariant of the whole system are quite hard to grasp.

cfe/trunk/lib/CodeGen/BackendUtil.cpp

static void runThinLTOBackend(ModuleSummaryIndex *CombinedIndex, Module *M,
   setCommandLineOpts(CGOpts);
 
   // We can simply import the values mentioned in the combined index, since
   // we should only invoke this using the individual indexes written out
   // via a WriteIndexesThinBackend.
   FunctionImporter::ImportMapTy ImportList;
   for (auto &GlobalList : *CombinedIndex) {
     auto GUID = GlobalList.first;
-    assert(GlobalList.second.size() == 1 &&
+    assert(GlobalList.second.SummaryList.size() == 1 &&
            "Expected individual combined index to have one summary per GUID");
-    auto &Summary = GlobalList.second[0];
+    auto &Summary = GlobalList.second.SummaryList[0];
     // Skip the summaries for the importing module. These are included to
     // e.g. record required linkage changes.
     if (Summary->modulePath() == M->getModuleIdentifier())
       continue;
     // Doesn't matter what value we plug in to the map, just needs an entry
     // to provoke importing by thinBackend.
     ImportList[Summary->modulePath()][GUID] = 1;
   }

llvm/trunk/include/llvm/IR/ModuleSummaryIndex.h

struct CalleeInfo {
   CalleeInfo() = default;
   explicit CalleeInfo(HotnessType Hotness) : Hotness(Hotness) {}
 
   void updateHotness(const HotnessType OtherHotness) {
     Hotness = std::max(Hotness, OtherHotness);
   }
 };
 
-/// Struct to hold value either by GUID or GlobalValue*. Values in combined
-/// indexes as well as indirect calls are GUIDs, all others are GlobalValues.
+class GlobalValueSummary;
+
+typedef std::vector<std::unique_ptr<GlobalValueSummary>> GlobalValueSummaryList;
+
+struct GlobalValueSummaryInfo {
+  /// The GlobalValue corresponding to this summary. This is only used in
+  /// per-module summaries.
+  const GlobalValue *GV = nullptr;
+
+  /// List of global value summary structures for a particular value held
+  /// in the GlobalValueMap. Requires a vector in the case of multiple
+  /// COMDAT values of the same name.
+  GlobalValueSummaryList SummaryList;
+};
+
+/// Map from global value GUID to corresponding summary structures. Use a
+/// std::map rather than a DenseMap so that pointers to the map's value_type
+/// (which are used by ValueInfo) are not invalidated by insertion. Also it will
+/// likely incur less overhead, as the value type is not very small and the size
+/// of the map is unknown, resulting in inefficiencies due to repeated
+/// insertions and resizing.
+typedef std::map<GlobalValue::GUID, GlobalValueSummaryInfo>
+    GlobalValueSummaryMapTy;
+
+/// Struct that holds a reference to a particular GUID in a global value
+/// summary.
 struct ValueInfo {
-  /// The value representation used in this instance.
-  enum ValueInfoKind {
-    VI_GUID,
-    VI_Value,
-  };
-
-  /// Union of the two possible value types.
-  union ValueUnion {
-    GlobalValue::GUID Id;
-    const GlobalValue *GV;
-    ValueUnion(GlobalValue::GUID Id) : Id(Id) {}
-    ValueUnion(const GlobalValue *GV) : GV(GV) {}
-  };
-
-  /// The value being represented.
-  ValueUnion TheValue;
-  /// The value representation.
-  ValueInfoKind Kind;
-  /// Constructor for a GUID value
-  ValueInfo(GlobalValue::GUID Id = 0) : TheValue(Id), Kind(VI_GUID) {}
-  /// Constructor for a GlobalValue* value
-  ValueInfo(const GlobalValue *V) : TheValue(V), Kind(VI_Value) {}
-  /// Accessor for GUID value
-  GlobalValue::GUID getGUID() const {
-    assert(Kind == VI_GUID && "Not a GUID type");
-    return TheValue.Id;
-  }
-  /// Accessor for GlobalValue* value
-  const GlobalValue *getValue() const {
-    assert(Kind == VI_Value && "Not a Value type");
-    return TheValue.GV;
+  const GlobalValueSummaryMapTy::value_type *Ref = nullptr;
+  ValueInfo() = default;
+  ValueInfo(const GlobalValueSummaryMapTy::value_type *Ref) : Ref(Ref) {}
+  operator bool() const { return Ref; }
+
+  GlobalValue::GUID getGUID() const { return Ref->first; }
+  const GlobalValue *getValue() const { return Ref->second.GV; }
+  ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const {
+    return Ref->second.SummaryList;
   }
-  bool isGUID() const { return Kind == VI_GUID; }
 };
 
 template <> struct DenseMapInfo<ValueInfo> {
-  static inline ValueInfo getEmptyKey() { return ValueInfo((GlobalValue *)-1); }
-  static inline ValueInfo getTombstoneKey() {
-    return ValueInfo((GlobalValue *)-2);
-  }
-  static bool isEqual(ValueInfo L, ValueInfo R) {
-    if (L.isGUID() != R.isGUID())
-      return false;
-    return L.isGUID() ? (L.getGUID() == R.getGUID())
-                      : (L.getValue() == R.getValue());
+  static inline ValueInfo getEmptyKey() {
+    return ValueInfo((GlobalValueSummaryMapTy::value_type *)-1);
   }
-  static unsigned getHashValue(ValueInfo I) {
-    return I.isGUID() ? I.getGUID() : (uintptr_t)I.getValue();
+  static inline ValueInfo getTombstoneKey() {
+    return ValueInfo((GlobalValueSummaryMapTy::value_type *)-2);
   }
+  static bool isEqual(ValueInfo L, ValueInfo R) { return L.Ref == R.Ref; }
+  static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.Ref; }
 };
 
 /// \brief Function and variable summary information to aid decisions and
 /// implementation of importing.
 class GlobalValueSummary {
 public:
   /// \brief Sububclass discriminator (for dyn_cast<> et al.)
   enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind };
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
 typedef std::array<uint32_t, 5> ModuleHash;
 
-/// List of global value summary structures for a particular value held
-/// in the GlobalValueMap. Requires a vector in the case of multiple
-/// COMDAT values of the same name.
-typedef std::vector<std::unique_ptr<GlobalValueSummary>> GlobalValueSummaryList;
-
-/// Map from global value GUID to corresponding summary structures.
-/// Use a std::map rather than a DenseMap since it will likely incur
-/// less overhead, as the value type is not very small and the size
-/// of the map is unknown, resulting in inefficiencies due to repeated
-/// insertions and resizing.
-typedef std::map<GlobalValue::GUID, GlobalValueSummaryList>
-    GlobalValueSummaryMapTy;
-
 /// Type used for iterating through the global value summary map.
 typedef GlobalValueSummaryMapTy::const_iterator const_gvsummary_iterator;
 typedef GlobalValueSummaryMapTy::iterator gvsummary_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.
 typedef StringMap<std::pair<uint64_t, ModuleHash>> ModulePathStringTableTy;
private:
 
   /// 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;
 
   // YAML I/O support.
   friend yaml::MappingTraits<ModuleSummaryIndex>;
 
+  GlobalValueSummaryMapTy::value_type *
+  getOrInsertValuePtr(GlobalValue::GUID GUID) {
+    return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo{}).first;
+  }
+
 public:
   gvsummary_iterator begin() { return GlobalValueMap.begin(); }
   const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
   gvsummary_iterator end() { return GlobalValueMap.end(); }
   const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
   size_t size() const { return GlobalValueMap.size(); }
 
-  /// Get the list of global value summary objects for a given value name.
-  const GlobalValueSummaryList &getGlobalValueSummaryList(StringRef ValueName) {
-    return GlobalValueMap[GlobalValue::getGUID(ValueName)];
-  }
-
-  /// Get the list of global value summary objects for a given value name.
-  const const_gvsummary_iterator
-  findGlobalValueSummaryList(StringRef ValueName) const {
-    return GlobalValueMap.find(GlobalValue::getGUID(ValueName));
-  }
-
-  /// Get the list of global value summary objects for a given value GUID.
-  const const_gvsummary_iterator
-  findGlobalValueSummaryList(GlobalValue::GUID ValueGUID) const {
-    return GlobalValueMap.find(ValueGUID);
+  /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
+  ValueInfo getValueInfo(GlobalValue::GUID GUID) const {
+    auto I = GlobalValueMap.find(GUID);
+    return ValueInfo(I == GlobalValueMap.end() ? nullptr : &*I);
+  }
+
+  /// Return a ValueInfo for \p GUID.
+  ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) {
+    return ValueInfo(getOrInsertValuePtr(GUID));
+  }
+
+  /// Return a ValueInfo for \p GV and mark it as belonging to GV.
+  ValueInfo getOrInsertValueInfo(const GlobalValue *GV) {
+    auto VP = getOrInsertValuePtr(GV->getGUID());
+    VP->second.GV = GV;
+    return ValueInfo(VP);
   }
 
   /// Return the GUID for \p OriginalId in the OidGuidMap.
   GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const {
     const auto I = OidGuidMap.find(OriginalID);
     return I == OidGuidMap.end() ? 0 : I->second;
   }
 
   /// Add a global value summary for a value of the given name.
   void addGlobalValueSummary(StringRef ValueName,
                              std::unique_ptr<GlobalValueSummary> Summary) {
-    addOriginalName(GlobalValue::getGUID(ValueName),
-                    Summary->getOriginalName());
-    GlobalValueMap[GlobalValue::getGUID(ValueName)].push_back(
+    addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)),
                           std::move(Summary));
   }
 
-  /// Add a global value summary for a value of the given GUID.
-  void addGlobalValueSummary(GlobalValue::GUID ValueGUID,
+  /// Add a global value summary for the given ValueInfo.
+  void addGlobalValueSummary(ValueInfo VI,
                              std::unique_ptr<GlobalValueSummary> Summary) {
-    addOriginalName(ValueGUID, Summary->getOriginalName());
-    GlobalValueMap[ValueGUID].push_back(std::move(Summary));
+    addOriginalName(VI.getGUID(), Summary->getOriginalName());
+    // Here we have a notionally const VI, but the value it points to is owned
+    // by the non-const *this.
+    const_cast<GlobalValueSummaryMapTy::value_type *>(VI.Ref)
+        ->second.SummaryList.push_back(std::move(Summary));
   }
 
   /// Add an original name for the value of the given GUID.
   void addOriginalName(GlobalValue::GUID ValueGUID,
                        GlobalValue::GUID OrigGUID) {
     if (OrigGUID == 0 || ValueGUID == OrigGUID)
       return;
     if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
       OidGuidMap[OrigGUID] = 0;
     else
       OidGuidMap[OrigGUID] = ValueGUID;
   }
 
   /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
   /// not found.
   GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
                                           StringRef ModuleId) const {
-    auto CalleeInfoList = findGlobalValueSummaryList(ValueGUID);
-    if (CalleeInfoList == end()) {
+    auto CalleeInfo = getValueInfo(ValueGUID);
+    if (!CalleeInfo) {
       return nullptr; // This function does not have a summary
     }
     auto Summary =
-        llvm::find_if(CalleeInfoList->second,
+        llvm::find_if(CalleeInfo.getSummaryList(),
                       [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
                         return Summary->modulePath() == ModuleId;
                       });
-    if (Summary == CalleeInfoList->second.end())
+    if (Summary == CalleeInfo.getSummaryList().end())
       return nullptr;
     return Summary->get();
   }
 
   /// Returns the first GlobalValueSummary for \p GV, asserting that there
   /// is only one if \p PerModuleIndex.
   GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV,
                                             bool PerModuleIndex = true) const {

llvm/trunk/include/llvm/IR/ModuleSummaryIndexYAML.h

static void inputOne(IO &io, StringRef Key, GlobalValueSummaryMapTy &V) {
     if (Key.getAsInteger(0, KeyInt)) {
       io.setError("key not an integer");
       return;
     }
     auto &Elem = V[KeyInt];
     for (auto &FSum : FSums) {
       GlobalValueSummary::GVFlags GVFlags(GlobalValue::ExternalLinkage, false,
                                           false);
-      Elem.push_back(llvm::make_unique<FunctionSummary>(
+      Elem.SummaryList.push_back(llvm::make_unique<FunctionSummary>(
           GVFlags, 0, ArrayRef<ValueInfo>{},
           ArrayRef<FunctionSummary::EdgeTy>{}, std::move(FSum.TypeTests),
           std::move(FSum.TypeTestAssumeVCalls),
           std::move(FSum.TypeCheckedLoadVCalls),
           std::move(FSum.TypeTestAssumeConstVCalls),
           std::move(FSum.TypeCheckedLoadConstVCalls)));
     }
   }
   static void output(IO &io, GlobalValueSummaryMapTy &V) {
     for (auto &P : V) {
       std::vector<FunctionSummaryYaml> FSums;
-      for (auto &Sum : P.second) {
+      for (auto &Sum : P.second.SummaryList) {
         if (auto *FSum = dyn_cast<FunctionSummary>(Sum.get()))
           FSums.push_back(FunctionSummaryYaml{
               FSum->type_tests(), FSum->type_test_assume_vcalls(),
               FSum->type_checked_load_vcalls(),
               FSum->type_test_assume_const_vcalls(),
               FSum->type_checked_load_const_vcalls()});
       }
       if (!FSums.empty())

llvm/trunk/lib/Analysis/ModuleSummaryAnalysis.cpp

 #include "llvm/Pass.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "module-summary-analysis"
 
 // Walk through the operands of a given User via worklist iteration and populate
 // the set of GlobalValue references encountered. Invoked either on an
 // Instruction or a GlobalVariable (which walks its initializer).
-static void findRefEdges(const User *CurUser, SetVector<ValueInfo> &RefEdges,
+static void findRefEdges(ModuleSummaryIndex &Index, const User *CurUser,
+                         SetVector<ValueInfo> &RefEdges,
                          SmallPtrSet<const User *, 8> &Visited) {
   SmallVector<const User *, 32> Worklist;
   Worklist.push_back(CurUser);
 
   while (!Worklist.empty()) {
     const User *U = Worklist.pop_back_val();
 
     if (!Visited.insert(U).second)
       continue;
 
     ImmutableCallSite CS(U);
 
     for (const auto &OI : U->operands()) {
       const User *Operand = dyn_cast<User>(OI);
       if (!Operand)
         continue;
       if (isa<BlockAddress>(Operand))
         continue;
       if (auto *GV = dyn_cast<GlobalValue>(Operand)) {
         // We have a reference to a global value. This should be added to
         // the reference set unless it is a callee. Callees are handled
         // specially by WriteFunction and are added to a separate list.
         if (!(CS && CS.isCallee(&OI)))
-          RefEdges.insert(GV);
+          RefEdges.insert(Index.getOrInsertValueInfo(GV));
         continue;
       }
       Worklist.push_back(Operand);
     }
   }
 }
 
 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
 
   bool HasInlineAsmMaybeReferencingInternal = false;
   SmallPtrSet<const User *, 8> Visited;
   for (const BasicBlock &BB : F)
     for (const Instruction &I : BB) {
       if (isa<DbgInfoIntrinsic>(I))
         continue;
       ++NumInsts;
-      findRefEdges(&I, RefEdges, Visited);
+      findRefEdges(Index, &I, RefEdges, Visited);
       auto CS = ImmutableCallSite(&I);
       if (!CS)
         continue;
 
       const auto *CI = dyn_cast<CallInst>(&I);
       // Since we don't know exactly which local values are referenced in inline
       // assembly, conservatively mark the function as possibly referencing
       // a local value from inline assembly to ensure we don't export a
for (const Instruction &I : BB) {
         auto ScaledCount = ProfileSummaryInfo::getProfileCount(&I, BFI);
         auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
                                    : CalleeInfo::HotnessType::Unknown;
 
         // Use the original CalledValue, in case it was an alias. We want
         // to record the call edge to the alias in that case. Eventually
         // an alias summary will be created to associate the alias and
         // aliasee.
-        CallGraphEdges[cast<GlobalValue>(CalledValue)].updateHotness(Hotness);
+        CallGraphEdges[Index.getOrInsertValueInfo(
+                           cast<GlobalValue>(CalledValue))]
+            .updateHotness(Hotness);
       } else {
         // Skip inline assembly calls.
         if (CI && CI->isInlineAsm())
           continue;
         // Skip direct calls.
         if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue()))
           continue;
 
         uint32_t NumVals, NumCandidates;
         uint64_t TotalCount;
         auto CandidateProfileData =
             ICallAnalysis.getPromotionCandidatesForInstruction(
                 &I, NumVals, TotalCount, NumCandidates);
         for (auto &Candidate : CandidateProfileData)
-          CallGraphEdges[Candidate.Value].updateHotness(
-              getHotness(Candidate.Count, PSI));
+          CallGraphEdges[Index.getOrInsertValueInfo(Candidate.Value)]
+              .updateHotness(getHotness(Candidate.Count, PSI));
       }
     }
 
   // Explicit add hot edges to enforce importing for designated GUIDs for
   // sample PGO, to enable the same inlines as the profiled optimized binary.
   for (auto &I : F.getImportGUIDs())
-    CallGraphEdges[I].updateHotness(CalleeInfo::HotnessType::Hot);
+    CallGraphEdges[Index.getOrInsertValueInfo(I)].updateHotness(
+        CalleeInfo::HotnessType::Hot);
 
   bool NonRenamableLocal = isNonRenamableLocal(F);
   bool NotEligibleForImport =
       NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
       // Inliner doesn't handle variadic functions.
       // FIXME: refactor this to use the same code that inliner is using.
       F.isVarArg();
   GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M,
   Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary));
 }
 
 static void
 computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V,
                        DenseSet<GlobalValue::GUID> &CantBePromoted) {
   SetVector<ValueInfo> RefEdges;
   SmallPtrSet<const User *, 8> Visited;
-  findRefEdges(&V, RefEdges, Visited);
+  findRefEdges(Index, &V, RefEdges, Visited);
   bool NonRenamableLocal = isNonRenamableLocal(V);
   GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
                                     /* LiveRoot = */ false);
   auto GVarSummary =
       llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector());
   if (NonRenamableLocal)
     CantBePromoted.insert(V.getGUID());
   Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary));
computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
   AS->setAliasee(AliaseeSummary);
   if (NonRenamableLocal)
     CantBePromoted.insert(A.getGUID());
   Index.addGlobalValueSummary(A.getName(), std::move(AS));
 }
 
 // Set LiveRoot flag on entries matching the given value name.
 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
-  auto SummaryList =
-      Index.findGlobalValueSummaryList(GlobalValue::getGUID(Name));
-  if (SummaryList == Index.end())
-    return;
-  for (auto &Summary : SummaryList->second)
+  if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name)))
+    for (auto &Summary : VI.getSummaryList())
       Summary->setLiveRoot();
 }
 
 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
     const Module &M,
     std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
     ProfileSummaryInfo *PSI) {
   ModuleSummaryIndex Index;
 
ModuleSymbolTable::CollectAsmSymbols(
                 llvm::make_unique<GlobalVarSummary>(GVFlags,
                                                     ArrayRef<ValueInfo>{});
             Index.addGlobalValueSummary(Name, std::move(Summary));
           }
         });
   }
 
   for (auto &GlobalList : Index) {
-    assert(GlobalList.second.size() == 1 &&
+    // Ignore entries for references that are undefined in the current module.
+    if (GlobalList.second.SummaryList.empty())
+      continue;
+
+    assert(GlobalList.second.SummaryList.size() == 1 &&
            "Expected module's index to have one summary per GUID");
-    auto &Summary = GlobalList.second[0];
+    auto &Summary = GlobalList.second.SummaryList[0];
     bool AllRefsCanBeExternallyReferenced =
         llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
-          return !CantBePromoted.count(VI.getValue()->getGUID());
+          return !CantBePromoted.count(VI.getGUID());
         });
     if (!AllRefsCanBeExternallyReferenced) {
       Summary->setNotEligibleToImport();
       continue;
     }
 
     if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
       bool AllCallsCanBeExternallyReferenced = llvm::all_of(
           FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
-            auto GUID = Edge.first.isGUID() ? Edge.first.getGUID()
-                                            : Edge.first.getValue()->getGUID();
-            return !CantBePromoted.count(GUID);
+            return !CantBePromoted.count(Edge.first.getGUID());
           });
       if (!AllCallsCanBeExternallyReferenced)
         Summary->setNotEligibleToImport();
     }
   }
 
   return Index;
 }

llvm/trunk/lib/Bitcode/Reader/BitcodeReader.cpp

class ModuleSummaryIndexBitcodeReader : public BitcodeReaderBase {
 
   /// Indicates whether we have already parsed the VST, used for error checking.
   bool SeenValueSymbolTable = false;
 
   /// Set to the offset of the VST recorded in the MODULE_CODE_VSTOFFSET record.
   /// Used to enable on-demand parsing of the VST.
   uint64_t VSTOffset = 0;
 
-  // Map to save ValueId to GUID association that was recorded in the
+  // Map to save ValueId to ValueInfo association that was recorded in the
   // ValueSymbolTable. It is used after the VST is parsed to convert
   // call graph edges read from the function summary from referencing
-  // callees by their ValueId to using the GUID instead, which is how
+  // callees by their ValueId to using the ValueInfo instead, which is how
   // they are recorded in the summary index being built.
-  // We save a second GUID which is the same as the first one, but ignoring the
-  // linkage, i.e. for value other than local linkage they are identical.
-  DenseMap<unsigned, std::pair<GlobalValue::GUID, GlobalValue::GUID>>
-      ValueIdToCallGraphGUIDMap;
+  // We save a GUID which refers to the same global as the ValueInfo, but
+  // ignoring the linkage, i.e. for values other than local linkage they are
+  // identical.
+  DenseMap<unsigned, std::pair<ValueInfo, GlobalValue::GUID>>
+      ValueIdToValueInfoMap;
 
   /// 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
   /// summary records.
   DenseMap<uint64_t, StringRef> ModuleIdMap;
 
   /// Original source file name recorded in a bitcode record.
Error parseValueSymbolTable(
       DenseMap<unsigned, GlobalValue::LinkageTypes> &ValueIdToLinkageMap);
   std::vector<ValueInfo> makeRefList(ArrayRef<uint64_t> Record);
   std::vector<FunctionSummary::EdgeTy> makeCallList(ArrayRef<uint64_t> Record,
                                                     bool IsOldProfileFormat,
                                                     bool HasProfile);
   Error parseEntireSummary();
   Error parseModuleStringTable();
 
-  std::pair<GlobalValue::GUID, GlobalValue::GUID>
-  getGUIDFromValueId(unsigned ValueId);
+  std::pair<ValueInfo, GlobalValue::GUID>
+  getValueInfoFromValueId(unsigned ValueId);
 
   ModulePathStringTableTy::iterator addThisModulePath();
 };
 
 } // end anonymous namespace
 
 std::error_code llvm::errorToErrorCodeAndEmitErrors(LLVMContext &Ctx,
                                                     Error Err) {
ModuleSummaryIndexBitcodeReader::ModuleSummaryIndexBitcodeReader(
     : BitcodeReaderBase(std::move(Cursor), Strtab), TheIndex(TheIndex),
       ModulePath(ModulePath), ModuleId(ModuleId) {}
 
 ModulePathStringTableTy::iterator
 ModuleSummaryIndexBitcodeReader::addThisModulePath() {
   return TheIndex.addModulePath(ModulePath, ModuleId);
 }
 
-std::pair<GlobalValue::GUID, GlobalValue::GUID>
-ModuleSummaryIndexBitcodeReader::getGUIDFromValueId(unsigned ValueId) {
-  auto VGI = ValueIdToCallGraphGUIDMap.find(ValueId);
-  assert(VGI != ValueIdToCallGraphGUIDMap.end());
-  return VGI->second;
+std::pair<ValueInfo, GlobalValue::GUID>
+ModuleSummaryIndexBitcodeReader::getValueInfoFromValueId(unsigned ValueId) {
+  auto VGI = ValueIdToValueInfoMap[ValueId];
+  assert(VGI.first);
+  return VGI;
 }
 
 void ModuleSummaryIndexBitcodeReader::setValueGUID(
     uint64_t ValueID, StringRef ValueName, GlobalValue::LinkageTypes Linkage,
     StringRef SourceFileName) {
   std::string GlobalId =
       GlobalValue::getGlobalIdentifier(ValueName, Linkage, SourceFileName);
   auto ValueGUID = GlobalValue::getGUID(GlobalId);
   auto OriginalNameID = ValueGUID;
   if (GlobalValue::isLocalLinkage(Linkage))
     OriginalNameID = GlobalValue::getGUID(ValueName);
   if (PrintSummaryGUIDs)
     dbgs() << "GUID " << ValueGUID << "(" << OriginalNameID << ") is "
            << ValueName << "\n";
-  ValueIdToCallGraphGUIDMap[ValueID] =
-      std::make_pair(ValueGUID, OriginalNameID);
+  ValueIdToValueInfoMap[ValueID] =
+      std::make_pair(TheIndex.getOrInsertValueInfo(ValueGUID), OriginalNameID);
 }
 
 // Specialized value symbol table parser used when reading module index
 // blocks where we don't actually create global values. The parsed information
 // is saved in the bitcode reader for use when later parsing summaries.
 Error ModuleSummaryIndexBitcodeReader::parseValueSymbolTable(
     uint64_t Offset,
     DenseMap<unsigned, GlobalValue::LinkageTypes> &ValueIdToLinkageMap) {
case bitc::VST_CODE_FNENTRY: {
       break;
     }
     case bitc::VST_CODE_COMBINED_ENTRY: {
       // VST_CODE_COMBINED_ENTRY: [valueid, refguid]
       unsigned ValueID = Record[0];
       GlobalValue::GUID RefGUID = Record[1];
       // The "original name", which is the second value of the pair will be
       // overriden later by a FS_COMBINED_ORIGINAL_NAME in the combined index.
-      ValueIdToCallGraphGUIDMap[ValueID] = std::make_pair(RefGUID, RefGUID);
+      ValueIdToValueInfoMap[ValueID] =
+          std::make_pair(TheIndex.getOrInsertValueInfo(RefGUID), RefGUID);
       break;
     }
     }
   }
 }
 
 // Parse just the blocks needed for building the index out of the module.
 // At the end of this routine the module Index is populated with a map
Error ModuleSummaryIndexBitcodeReader::parseModule() {
   }
 }
 
 std::vector<ValueInfo>
 ModuleSummaryIndexBitcodeReader::makeRefList(ArrayRef<uint64_t> Record) {
   std::vector<ValueInfo> Ret;
   Ret.reserve(Record.size());
   for (uint64_t RefValueId : Record)
-    Ret.push_back(getGUIDFromValueId(RefValueId).first);
+    Ret.push_back(getValueInfoFromValueId(RefValueId).first);
   return Ret;
 }
 
 std::vector<FunctionSummary::EdgeTy> ModuleSummaryIndexBitcodeReader::makeCallList(
     ArrayRef<uint64_t> Record, bool IsOldProfileFormat, bool HasProfile) {
   std::vector<FunctionSummary::EdgeTy> Ret;
   Ret.reserve(Record.size());
   for (unsigned I = 0, E = Record.size(); I != E; ++I) {
     CalleeInfo::HotnessType Hotness = CalleeInfo::HotnessType::Unknown;
-    GlobalValue::GUID CalleeGUID = getGUIDFromValueId(Record[I]).first;
+    ValueInfo Callee = getValueInfoFromValueId(Record[I]).first;
     if (IsOldProfileFormat) {
       I += 1; // Skip old callsitecount field
       if (HasProfile)
         I += 1; // Skip old profilecount field
     } else if (HasProfile)
       Hotness = static_cast<CalleeInfo::HotnessType>(Record[++I]);
-    Ret.push_back(FunctionSummary::EdgeTy{CalleeGUID, CalleeInfo{Hotness}});
+    Ret.push_back(FunctionSummary::EdgeTy{Callee, CalleeInfo{Hotness}});
   }
   return Ret;
 }
 
 // Eagerly parse the entire summary block. This populates the GlobalValueSummary
 // objects in the index.
 Error ModuleSummaryIndexBitcodeReader::parseEntireSummary() {
   if (Stream.EnterSubBlock(bitc::GLOBALVAL_SUMMARY_BLOCK_ID))
while (true) {
     Record.clear();
     auto BitCode = Stream.readRecord(Entry.ID, Record);
     switch (BitCode) {
     default: // Default behavior: ignore.
       break;
     case bitc::FS_VALUE_GUID: { // [valueid, refguid]
       uint64_t ValueID = Record[0];
       GlobalValue::GUID RefGUID = Record[1];
-      ValueIdToCallGraphGUIDMap[ValueID] = std::make_pair(RefGUID, RefGUID);
+      ValueIdToValueInfoMap[ValueID] =
+          std::make_pair(TheIndex.getOrInsertValueInfo(RefGUID), RefGUID);
       break;
     }
     // FS_PERMODULE: [valueid, flags, instcount, numrefs, numrefs x valueid,
     //                n x (valueid)]
     // FS_PERMODULE_PROFILE: [valueid, flags, instcount, numrefs,
     //                        numrefs x valueid,
     //                        n x (valueid, hotness)]
     case bitc::FS_PERMODULE:
case bitc::FS_PERMODULE_PROFILE: {
           std::move(PendingTypeCheckedLoadVCalls),
           std::move(PendingTypeTestAssumeConstVCalls),
           std::move(PendingTypeCheckedLoadConstVCalls));
       PendingTypeTests.clear();
       PendingTypeTestAssumeVCalls.clear();
       PendingTypeCheckedLoadVCalls.clear();
       PendingTypeTestAssumeConstVCalls.clear();
       PendingTypeCheckedLoadConstVCalls.clear();
-      auto GUID = getGUIDFromValueId(ValueID);
+      auto VIAndOriginalGUID = getValueInfoFromValueId(ValueID);
       FS->setModulePath(addThisModulePath()->first());
-      FS->setOriginalName(GUID.second);
-      TheIndex.addGlobalValueSummary(GUID.first, std::move(FS));
+      FS->setOriginalName(VIAndOriginalGUID.second);
+      TheIndex.addGlobalValueSummary(VIAndOriginalGUID.first, std::move(FS));
       break;
     }
     // FS_ALIAS: [valueid, flags, valueid]
     // Aliases must be emitted (and parsed) after all FS_PERMODULE entries, as
     // they expect all aliasee summaries to be available.
     case bitc::FS_ALIAS: {
       unsigned ValueID = Record[0];
       uint64_t RawFlags = Record[1];
       unsigned AliaseeID = Record[2];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
       auto AS =
           llvm::make_unique<AliasSummary>(Flags, std::vector<ValueInfo>{});
       // The module path string ref set in the summary must be owned by the
       // index's module string table. Since we don't have a module path
       // string table section in the per-module index, we create a single
       // module path string table entry with an empty (0) ID to take
       // ownership.
       AS->setModulePath(addThisModulePath()->first());
 
-      GlobalValue::GUID AliaseeGUID = getGUIDFromValueId(AliaseeID).first;
+      GlobalValue::GUID AliaseeGUID =
+          getValueInfoFromValueId(AliaseeID).first.getGUID();
       auto AliaseeInModule =
           TheIndex.findSummaryInModule(AliaseeGUID, ModulePath);
       if (!AliaseeInModule)
         return error("Alias expects aliasee summary to be parsed");
       AS->setAliasee(AliaseeInModule);
 
-      auto GUID = getGUIDFromValueId(ValueID);
+      auto GUID = getValueInfoFromValueId(ValueID);
       AS->setOriginalName(GUID.second);
       TheIndex.addGlobalValueSummary(GUID.first, std::move(AS));
       break;
     }
     // FS_PERMODULE_GLOBALVAR_INIT_REFS: [valueid, flags, n x valueid]
     case bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS: {
       unsigned ValueID = Record[0];
       uint64_t RawFlags = Record[1];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
       std::vector<ValueInfo> Refs =
           makeRefList(ArrayRef<uint64_t>(Record).slice(2));
       auto FS = llvm::make_unique<GlobalVarSummary>(Flags, std::move(Refs));
       FS->setModulePath(addThisModulePath()->first());
-      auto GUID = getGUIDFromValueId(ValueID);
+      auto GUID = getValueInfoFromValueId(ValueID);
       FS->setOriginalName(GUID.second);
       TheIndex.addGlobalValueSummary(GUID.first, std::move(FS));
       break;
     }
     // FS_COMBINED: [valueid, modid, flags, instcount, numrefs,
     //               numrefs x valueid, n x (valueid)]
     // FS_COMBINED_PROFILE: [valueid, modid, flags, instcount, numrefs,
     //                       numrefs x valueid, n x (valueid, hotness)]
case bitc::FS_COMBINED_PROFILE: {
       assert(Record.size() >= RefListStartIndex + NumRefs &&
              "Record size inconsistent with number of references");
       std::vector<ValueInfo> Refs = makeRefList(
           ArrayRef<uint64_t>(Record).slice(RefListStartIndex, NumRefs));
       bool HasProfile = (BitCode == bitc::FS_COMBINED_PROFILE);
       std::vector<FunctionSummary::EdgeTy> Edges = makeCallList(
           ArrayRef<uint64_t>(Record).slice(CallGraphEdgeStartIndex),
           IsOldProfileFormat, HasProfile);
-      GlobalValue::GUID GUID = getGUIDFromValueId(ValueID).first;
+      ValueInfo VI = getValueInfoFromValueId(ValueID).first;
       auto FS = llvm::make_unique<FunctionSummary>(
           Flags, InstCount, std::move(Refs), std::move(Edges),
           std::move(PendingTypeTests), std::move(PendingTypeTestAssumeVCalls),
           std::move(PendingTypeCheckedLoadVCalls),
           std::move(PendingTypeTestAssumeConstVCalls),
           std::move(PendingTypeCheckedLoadConstVCalls));
       PendingTypeTests.clear();
       PendingTypeTestAssumeVCalls.clear();
       PendingTypeCheckedLoadVCalls.clear();
       PendingTypeTestAssumeConstVCalls.clear();
       PendingTypeCheckedLoadConstVCalls.clear();
       LastSeenSummary = FS.get();
-      LastSeenGUID = GUID;
+      LastSeenGUID = VI.getGUID();
       FS->setModulePath(ModuleIdMap[ModuleId]);
-      TheIndex.addGlobalValueSummary(GUID, std::move(FS));
+      TheIndex.addGlobalValueSummary(VI, std::move(FS));
       break;
     }
     // FS_COMBINED_ALIAS: [valueid, modid, flags, valueid]
     // Aliases must be emitted (and parsed) after all FS_COMBINED entries, as
     // they expect all aliasee summaries to be available.
     case bitc::FS_COMBINED_ALIAS: {
       unsigned ValueID = Record[0];
       uint64_t ModuleId = Record[1];
       uint64_t RawFlags = Record[2];
       unsigned AliaseeValueId = Record[3];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
       auto AS = llvm::make_unique<AliasSummary>(Flags, std::vector<ValueInfo>{});
       LastSeenSummary = AS.get();
       AS->setModulePath(ModuleIdMap[ModuleId]);
 
-      auto AliaseeGUID = getGUIDFromValueId(AliaseeValueId).first;
+      auto AliaseeGUID =
+          getValueInfoFromValueId(AliaseeValueId).first.getGUID();
       auto AliaseeInModule =
           TheIndex.findSummaryInModule(AliaseeGUID, AS->modulePath());
       if (!AliaseeInModule)
         return error("Alias expects aliasee summary to be parsed");
       AS->setAliasee(AliaseeInModule);
 
-      GlobalValue::GUID GUID = getGUIDFromValueId(ValueID).first;
-      LastSeenGUID = GUID;
-      TheIndex.addGlobalValueSummary(GUID, std::move(AS));
+      ValueInfo VI = getValueInfoFromValueId(ValueID).first;
+      LastSeenGUID = VI.getGUID();
+      TheIndex.addGlobalValueSummary(VI, std::move(AS));
       break;
     }
     // FS_COMBINED_GLOBALVAR_INIT_REFS: [valueid, modid, flags, n x valueid]
     case bitc::FS_COMBINED_GLOBALVAR_INIT_REFS: {
       unsigned ValueID = Record[0];
       uint64_t ModuleId = Record[1];
       uint64_t RawFlags = Record[2];
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
       std::vector<ValueInfo> Refs =
           makeRefList(ArrayRef<uint64_t>(Record).slice(3));
       auto FS = llvm::make_unique<GlobalVarSummary>(Flags, std::move(Refs));
       LastSeenSummary = FS.get();
       FS->setModulePath(ModuleIdMap[ModuleId]);
-      GlobalValue::GUID GUID = getGUIDFromValueId(ValueID).first;
-      LastSeenGUID = GUID;
-      TheIndex.addGlobalValueSummary(GUID, std::move(FS));
+      ValueInfo VI = getValueInfoFromValueId(ValueID).first;
+      LastSeenGUID = VI.getGUID();
+      TheIndex.addGlobalValueSummary(VI, std::move(FS));
       break;
     }
     // FS_COMBINED_ORIGINAL_NAME: [original_name]
     case bitc::FS_COMBINED_ORIGINAL_NAME: {
       uint64_t OriginalName = Record[0];
       if (!LastSeenSummary)
         return error("Name attachment that does not follow a combined record");
       LastSeenSummary->setOriginalName(OriginalName);

llvm/trunk/lib/Bitcode/Writer/BitcodeWriter.cpp

ModuleBitcodeWriter(const Module *M, SmallVectorImpl<char> &Buffer,
     // (which would have been assigned an ID by the ValueEnumerator).
     // The starting ValueId is just after the number of values in the
     // ValueEnumerator, so that they can be emitted in the VST.
     GlobalValueId = VE.getValues().size();
     if (!Index)
       return;
     for (const auto &GUIDSummaryLists : *Index)
       // Examine all summaries for this GUID.
-      for (auto &Summary : GUIDSummaryLists.second)
+      for (auto &Summary : GUIDSummaryLists.second.SummaryList)
         if (auto FS = dyn_cast<FunctionSummary>(Summary.get()))
           // For each call in the function summary, see if the call
           // is to a GUID (which means it is for an indirect call,
           // otherwise we would have a Value for it). If so, synthesize
           // a value id.
           for (auto &CallEdge : FS->calls())
-            if (CallEdge.first.isGUID())
+            if (!CallEdge.first.getValue())
               assignValueId(CallEdge.first.getGUID());
   }
 
   /// Emit the current module to the bitstream.
   void write();
 
 private:
   uint64_t bitcodeStartBit() { return BitcodeStartBit; }
unsigned getValueId(GlobalValue::GUID ValGUID) {
     // Expect that any GUID value had a value Id assigned by an
     // earlier call to assignValueId.
     assert(VMI != GUIDToValueIdMap.end() &&
            "GUID does not have assigned value Id");
     return VMI->second;
   }
   // Helper to get the valueId for the type of value recorded in VI.
   unsigned getValueId(ValueInfo VI) {
-    if (VI.isGUID())
+    if (!VI.getValue())
       return getValueId(VI.getGUID());
     return VE.getValueID(VI.getValue());
   }
   std::map<GlobalValue::GUID, unsigned> &valueIds() { return GUIDToValueIdMap; }
 };
 
 /// Class to manage the bitcode writing for a combined index.
 class IndexBitcodeWriter : public BitcodeWriterBase {
public:
   /// entire index or just those in a provided ModuleToSummariesForIndex map.
   void forEachSummary(std::function<void(GVInfo)> Callback) {
     if (ModuleToSummariesForIndex) {
       for (auto &M : *ModuleToSummariesForIndex)
         for (auto &Summary : M.second)
           Callback(Summary);
     } else {
       for (auto &Summaries : Index)
-        for (auto &Summary : Summaries.second)
+        for (auto &Summary : Summaries.second.SummaryList)
           Callback({Summaries.first, Summary.get()});
     }
   }
 
   /// Main entry point for writing a combined index to bitcode.
   void write();
 
 private:
void ModuleBitcodeWriter::writePerModuleFunctionSummaryRecord(
   NameVals.clear();
 }
 
 // Collect the global value references in the given variable's initializer,
 // and emit them in a summary record.
 void ModuleBitcodeWriter::writeModuleLevelReferences(
     const GlobalVariable &V, SmallVector<uint64_t, 64> &NameVals,
     unsigned FSModRefsAbbrev) {
-  auto Summaries =
-      Index->findGlobalValueSummaryList(GlobalValue::getGUID(V.getName()));
-  if (Summaries == Index->end()) {
+  auto VI = Index->getValueInfo(GlobalValue::getGUID(V.getName()));
+  if (!VI || VI.getSummaryList().empty()) {
     // Only declarations should not have a summary (a declaration might however
     // have a summary if the def was in module level asm).
     assert(V.isDeclaration());
     return;
   }
-  auto *Summary = Summaries->second.front().get();
+  auto *Summary = VI.getSummaryList()[0].get();
   NameVals.push_back(VE.getValueID(&V));
   GlobalVarSummary *VS = cast<GlobalVarSummary>(Summary);
   NameVals.push_back(getEncodedGVSummaryFlags(VS->flags()));
 
   unsigned SizeBeforeRefs = NameVals.size();
   for (auto &RI : VS->refs())
     NameVals.push_back(VE.getValueID(RI.getValue()));
   // Sort the refs for determinism output, the vector returned by FS->refs() has
void ModuleBitcodeWriter::writePerModuleGlobalValueSummary() {
   // Iterate over the list of functions instead of the Index to
   // ensure the ordering is stable.
   for (const Function &F : M) {
     // Summary emission does not support anonymous functions, they have to
     // renamed using the anonymous function renaming pass.
     if (!F.hasName())
       report_fatal_error("Unexpected anonymous function when writing summary");
 
-    auto Summaries =
-        Index->findGlobalValueSummaryList(GlobalValue::getGUID(F.getName()));
-    if (Summaries == Index->end()) {
+    ValueInfo VI = Index->getValueInfo(GlobalValue::getGUID(F.getName()));
+    if (!VI || VI.getSummaryList().empty()) {
       // Only declarations should not have a summary (a declaration might
       // however have a summary if the def was in module level asm).
       assert(F.isDeclaration());
       continue;
     }
-    auto *Summary = Summaries->second.front().get();
+    auto *Summary = VI.getSummaryList()[0].get();
     writePerModuleFunctionSummaryRecord(NameVals, Summary, VE.getValueID(&F),
                                         FSCallsAbbrev, FSCallsProfileAbbrev, F);
   }
 
   // Capture references from GlobalVariable initializers, which are outside
   // of a function scope.
   for (const GlobalVariable &G : M.globals())
     writeModuleLevelReferences(G, NameVals, FSModRefsAbbrev);

llvm/trunk/lib/IR/ModuleSummaryIndex.cpp

 using namespace llvm;
 
 // Collect for the given module the list of function it defines
 // (GUID -> Summary).
 void ModuleSummaryIndex::collectDefinedFunctionsForModule(
     StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
   for (auto &GlobalList : *this) {
     auto GUID = GlobalList.first;
-    for (auto &GlobSummary : GlobalList.second) {
+    for (auto &GlobSummary : GlobalList.second.SummaryList) {
       auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get());
       if (!Summary)
         // Ignore global variable, focus on functions
         continue;
       // Ignore summaries from other modules.
       if (Summary->modulePath() != ModulePath)
         continue;
       GVSummaryMap[GUID] = Summary;
     }
   }
 }
 
 // Collect for each module the list of function it defines (GUID -> Summary).
 void ModuleSummaryIndex::collectDefinedGVSummariesPerModule(
     StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const {
   for (auto &GlobalList : *this) {
     auto GUID = GlobalList.first;
-    for (auto &Summary : GlobalList.second) {
+    for (auto &Summary : GlobalList.second.SummaryList) {
       ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get();
     }
   }
 }
 
 GlobalValueSummary *
 ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID,
                                           bool PerModuleIndex) const {
-  auto SummaryList = findGlobalValueSummaryList(ValueGUID);
-  assert(SummaryList != end() && "GlobalValue not found in index");
-  assert((!PerModuleIndex || SummaryList->second.size() == 1) &&
+  auto VI = getValueInfo(ValueGUID);
+  assert(VI && "GlobalValue not found in index");
+  assert((!PerModuleIndex || VI.getSummaryList().size() == 1) &&
          "Expected a single entry per global value in per-module index");
-  auto &Summary = SummaryList->second[0];
+  auto &Summary = VI.getSummaryList()[0];
   return Summary.get();
 }

llvm/trunk/lib/LTO/LTO.cpp

function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
         isPrevailing,
     function_ref<void(StringRef, GlobalValue::GUID, GlobalValue::LinkageTypes)>
         recordNewLinkage) {
   // We won't optimize the globals that are referenced by an alias for now
   // Ideally we should turn the alias into a global and duplicate the definition
   // when needed.
   DenseSet<GlobalValueSummary *> GlobalInvolvedWithAlias;
   for (auto &I : Index)
-    for (auto &S : I.second)
+    for (auto &S : I.second.SummaryList)
       if (auto AS = dyn_cast<AliasSummary>(S.get()))
         GlobalInvolvedWithAlias.insert(&AS->getAliasee());
 
   for (auto &I : Index)
-    thinLTOResolveWeakForLinkerGUID(I.second, I.first, GlobalInvolvedWithAlias,
-                                    isPrevailing, recordNewLinkage);
+    thinLTOResolveWeakForLinkerGUID(I.second.SummaryList, I.first,
+                                    GlobalInvolvedWithAlias, isPrevailing,
+                                    recordNewLinkage);
 }
 
 static void thinLTOInternalizeAndPromoteGUID(
     GlobalValueSummaryList &GVSummaryList, GlobalValue::GUID GUID,
     function_ref<bool(StringRef, GlobalValue::GUID)> isExported) {
   for (auto &S : GVSummaryList) {
     if (isExported(S->modulePath(), GUID)) {
       if (GlobalValue::isLocalLinkage(S->linkage()))
         S->setLinkage(GlobalValue::ExternalLinkage);
     } else if (!GlobalValue::isLocalLinkage(S->linkage()))
       S->setLinkage(GlobalValue::InternalLinkage);
   }
 }
 
 // Update the linkages in the given \p Index to mark exported values
 // as external and non-exported values as internal.
 void llvm::thinLTOInternalizeAndPromoteInIndex(
     ModuleSummaryIndex &Index,
     function_ref<bool(StringRef, GlobalValue::GUID)> isExported) {
   for (auto &I : Index)
-    thinLTOInternalizeAndPromoteGUID(I.second, I.first, isExported);
+    thinLTOInternalizeAndPromoteGUID(I.second.SummaryList, I.first, isExported);
 }
 
 // Requires a destructor for std::vector<InputModule>.
 InputFile::~InputFile() = default;
 
 Expected<std::unique_ptr<InputFile>> InputFile::create(MemoryBufferRef Object) {
   std::unique_ptr<InputFile> File(new InputFile);
 

llvm/trunk/lib/LTO/ThinLTOCodeGenerator.cpp

 static void computePrevailingCopies(
     const ModuleSummaryIndex &Index,
     DenseMap<GlobalValue::GUID, const GlobalValueSummary *> &PrevailingCopy) {
   auto HasMultipleCopies = [&](const GlobalValueSummaryList &GVSummaryList) {
     return GVSummaryList.size() > 1;
   };
 
   for (auto &I : Index) {
-    if (HasMultipleCopies(I.second))
-      PrevailingCopy[I.first] = getFirstDefinitionForLinker(I.second);
+    if (HasMultipleCopies(I.second.SummaryList))
+      PrevailingCopy[I.first] =
+          getFirstDefinitionForLinker(I.second.SummaryList);
   }
 }
 
 static StringMap<MemoryBufferRef>
 generateModuleMap(const std::vector<ThinLTOBuffer> &Modules) {
   StringMap<MemoryBufferRef> ModuleMap;
   for (auto &ModuleBuffer : Modules) {
     assert(ModuleMap.find(ModuleBuffer.getBufferIdentifier()) ==

llvm/trunk/lib/Transforms/IPO/FunctionImport.cpp

 /// - The smallest: more likely to be inlined.
 /// - The one with the least outgoing edges (already well optimized).
 /// - One from a module already being imported from in order to reduce the
 ///   number of source modules parsed/linked.
 /// - One that has PGO data attached.
 /// - [insert you fancy metric here]
 static const GlobalValueSummary *
 selectCallee(const ModuleSummaryIndex &Index,
-             const GlobalValueSummaryList &CalleeSummaryList,
+             ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
              unsigned Threshold, StringRef CallerModulePath) {
   auto It = llvm::find_if(
       CalleeSummaryList,
       [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {
         auto *GVSummary = SummaryPtr.get();
         if (GlobalValue::isInterposableLinkage(GVSummary->linkage()))
           // There is no point in importing these, we can't inline them
           return false;
auto It = llvm::find_if(
         return true;
       });
   if (It == CalleeSummaryList.end())
     return nullptr;
 
   return cast<GlobalValueSummary>(It->get());
 }
 
-/// Return the summary for the function \p GUID that fits the \p Threshold, or
-/// null if there's no match.
-static const GlobalValueSummary *selectCallee(GlobalValue::GUID GUID,
-                                              unsigned Threshold,
-                                              const ModuleSummaryIndex &Index,
-                                              StringRef CallerModulePath) {
-  auto CalleeSummaryList = Index.findGlobalValueSummaryList(GUID);
-  if (CalleeSummaryList == Index.end())
-    return nullptr; // This function does not have a summary
-  return selectCallee(Index, CalleeSummaryList->second, Threshold,
-                      CallerModulePath);
-}
-
 using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */,
                             GlobalValue::GUID>;
 
 /// Compute the list of functions to import for a given caller. Mark these
 /// imported functions and the symbols they reference in their source module as
 /// exported from their source module.
 static void computeImportForFunction(
     const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
     const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
     SmallVectorImpl<EdgeInfo> &Worklist,
     FunctionImporter::ImportMapTy &ImportList,
     StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
   for (auto &Edge : Summary.calls()) {
-    auto GUID = Edge.first.getGUID();
-    DEBUG(dbgs() << " edge -> " << GUID << " Threshold:" << Threshold << "\n");
+    ValueInfo VI = Edge.first;
+    DEBUG(dbgs() << " edge -> " << VI.getGUID() << " Threshold:" << Threshold
+                 << "\n");
 
-    if (Index.findGlobalValueSummaryList(GUID) == Index.end()) {
+    if (VI.getSummaryList().empty()) {
       // For SamplePGO, the indirect call targets for local functions will
       // have its original name annotated in profile. We try to find the
       // corresponding PGOFuncName as the GUID.
-      GUID = Index.getGUIDFromOriginalID(GUID);
+      auto GUID = Index.getGUIDFromOriginalID(VI.getGUID());
       if (GUID == 0)
         continue;
+      VI = Index.getValueInfo(GUID);
+      if (!VI)
+        continue;
     }
 
-    if (DefinedGVSummaries.count(GUID)) {
+    if (DefinedGVSummaries.count(VI.getGUID())) {
       DEBUG(dbgs() << "ignored! Target already in destination module.\n");
       continue;
     }
 
     auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
       if (Hotness == CalleeInfo::HotnessType::Hot)
         return ImportHotMultiplier;
       if (Hotness == CalleeInfo::HotnessType::Cold)
         return ImportColdMultiplier;
       return 1.0;
     };
 
     const auto NewThreshold =
         Threshold * GetBonusMultiplier(Edge.second.Hotness);
 
-    auto *CalleeSummary =
-        selectCallee(GUID, NewThreshold, Index, Summary.modulePath());
+    auto *CalleeSummary = selectCallee(Index, VI.getSummaryList(), NewThreshold,
+                                       Summary.modulePath());
     if (!CalleeSummary) {
       DEBUG(dbgs() << "ignored! No qualifying callee with summary found.\n");
       continue;
     }
     // "Resolve" the summary, traversing alias,
     const FunctionSummary *ResolvedCalleeSummary;
     if (isa<AliasSummary>(CalleeSummary)) {
       ResolvedCalleeSummary = cast<FunctionSummary>(
auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
         return Threshold * ImportHotInstrFactor;
       return Threshold * ImportInstrFactor;
     };
 
     bool IsHotCallsite = Edge.second.Hotness == CalleeInfo::HotnessType::Hot;
     const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite);
 
     auto ExportModulePath = ResolvedCalleeSummary->modulePath();
-    auto &ProcessedThreshold = ImportList[ExportModulePath][GUID];
+    auto &ProcessedThreshold = ImportList[ExportModulePath][VI.getGUID()];
     /// Since the traversal of the call graph is DFS, we can revisit a function
     /// a second time with a higher threshold. In this case, it is added back to
     /// the worklist with the new threshold.
     if (ProcessedThreshold && ProcessedThreshold >= AdjThreshold) {
       DEBUG(dbgs() << "ignored! Target was already seen with Threshold "
                    << ProcessedThreshold << "\n");
       continue;
     }
     bool PreviouslyImported = ProcessedThreshold != 0;
     // Mark this function as imported in this module, with the current Threshold
     ProcessedThreshold = AdjThreshold;
 
     // Make exports in the source module.
     if (ExportLists) {
       auto &ExportList = (*ExportLists)[ExportModulePath];
-      ExportList.insert(GUID);
+      ExportList.insert(VI.getGUID());
       if (!PreviouslyImported) {
         // This is the first time this function was exported from its source
         // module, so mark all functions and globals it references as exported
         // to the outside if they are defined in the same source module.
         // For efficiency, we unconditionally add all the referenced GUIDs
         // to the ExportList for this module, and will prune out any not
         // defined in the module later in a single pass.
         for (auto &Edge : ResolvedCalleeSummary->calls()) {
           auto CalleeGUID = Edge.first.getGUID();
           ExportList.insert(CalleeGUID);
         }
         for (auto &Ref : ResolvedCalleeSummary->refs()) {
           auto GUID = Ref.getGUID();
           ExportList.insert(GUID);
         }
       }
     }
 
     // Insert the newly imported function to the worklist.
-    Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, GUID);
+    Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, VI.getGUID());
   }
 }
 
 /// Given the list of globals defined in a module, compute the list of imports
 /// as well as the list of "exports", i.e. the list of symbols referenced from
 /// another module (that may require promotion).
 static void ComputeImportForModule(
     const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index,

 DenseSet<GlobalValue::GUID> llvm::computeDeadSymbols(
     const ModuleSummaryIndex &Index,
     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
   if (!ComputeDead)
     return DenseSet<GlobalValue::GUID>();
   if (GUIDPreservedSymbols.empty())
     // Don't do anything when nothing is live, this is friendly with tests.
     return DenseSet<GlobalValue::GUID>();
-  DenseSet<GlobalValue::GUID> LiveSymbols = GUIDPreservedSymbols;
-  SmallVector<GlobalValue::GUID, 128> Worklist;
-  Worklist.reserve(LiveSymbols.size() * 2);
-  for (auto GUID : LiveSymbols) {
-    DEBUG(dbgs() << "Live root: " << GUID << "\n");
-    Worklist.push_back(GUID);
+  DenseSet<ValueInfo> LiveSymbols;
+  SmallVector<ValueInfo, 128> Worklist;
+  Worklist.reserve(GUIDPreservedSymbols.size() * 2);
+  for (auto GUID : GUIDPreservedSymbols) {
+    ValueInfo VI = Index.getValueInfo(GUID);
+    if (!VI)
+      continue;
+    DEBUG(dbgs() << "Live root: " << VI.getGUID() << "\n");
+    LiveSymbols.insert(VI);
+    Worklist.push_back(VI);
   }
   // Add values flagged in the index as live roots to the worklist.
   for (const auto &Entry : Index) {
     bool IsLiveRoot = llvm::any_of(
-        Entry.second,
+        Entry.second.SummaryList,
         [&](const std::unique_ptr<llvm::GlobalValueSummary> &Summary) {
           return Summary->liveRoot();
         });
     if (!IsLiveRoot)
       continue;
     DEBUG(dbgs() << "Live root (summary): " << Entry.first << "\n");
-    Worklist.push_back(Entry.first);
+    Worklist.push_back(ValueInfo(&Entry));
   }
 
   while (!Worklist.empty()) {
-    auto GUID = Worklist.pop_back_val();
-    auto It = Index.findGlobalValueSummaryList(GUID);
-    if (It == Index.end()) {
-      DEBUG(dbgs() << "Not in index: " << GUID << "\n");
-      continue;
-    }
+    auto VI = Worklist.pop_back_val();
 
     // FIXME: we should only make the prevailing copy live here
-    for (auto &Summary : It->second) {
+    for (auto &Summary : VI.getSummaryList()) {
       for (auto Ref : Summary->refs()) {
-        auto RefGUID = Ref.getGUID();
-        if (LiveSymbols.insert(RefGUID).second) {
-          DEBUG(dbgs() << "Marking live (ref): " << RefGUID << "\n");
-          Worklist.push_back(RefGUID);
+        if (LiveSymbols.insert(Ref).second) {
+          DEBUG(dbgs() << "Marking live (ref): " << Ref.getGUID() << "\n");
+          Worklist.push_back(Ref);
         }
       }
       if (auto *FS = dyn_cast<FunctionSummary>(Summary.get())) {
         for (auto Call : FS->calls()) {
-          auto CallGUID = Call.first.getGUID();
-          if (LiveSymbols.insert(CallGUID).second) {
-            DEBUG(dbgs() << "Marking live (call): " << CallGUID << "\n");
-            Worklist.push_back(CallGUID);
+          if (LiveSymbols.insert(Call.first).second) {
+            DEBUG(dbgs() << "Marking live (call): " << Call.first.getGUID()
+                         << "\n");
+            Worklist.push_back(Call.first);
           }
         }
       }
       if (auto *AS = dyn_cast<AliasSummary>(Summary.get())) {
         auto AliaseeGUID = AS->getAliasee().getOriginalName();
-        if (LiveSymbols.insert(AliaseeGUID).second) {
+        ValueInfo AliaseeVI = Index.getValueInfo(AliaseeGUID);
+        if (AliaseeVI && LiveSymbols.insert(AliaseeVI).second) {
           DEBUG(dbgs() << "Marking live (alias): " << AliaseeGUID << "\n");
-          Worklist.push_back(AliaseeGUID);
+          Worklist.push_back(AliaseeVI);
         }
       }
     }
   }
   DenseSet<GlobalValue::GUID> DeadSymbols;
   DeadSymbols.reserve(
       std::min(Index.size(), Index.size() - LiveSymbols.size()));
   for (auto &Entry : Index) {
-    auto GUID = Entry.first;
-    if (!LiveSymbols.count(GUID)) {
-      DEBUG(dbgs() << "Marking dead: " << GUID << "\n");
-      DeadSymbols.insert(GUID);
+    if (!LiveSymbols.count(ValueInfo(&Entry))) {
+      DEBUG(dbgs() << "Marking dead: " << Entry.first << "\n");
+      DeadSymbols.insert(Entry.first);
     }
   }
   DEBUG(dbgs() << LiveSymbols.size() << " symbols Live, and "
                << DeadSymbols.size() << " symbols Dead \n");
   NumDeadSymbols += DeadSymbols.size();
   NumLiveSymbols += LiveSymbols.size();
   return DeadSymbols;
 }
static bool doImportingForModule(Module &M) {
   ComputeCrossModuleImportForModule(M.getModuleIdentifier(), *Index,
                                     ImportList);
 
   // Conservatively mark all internal values as promoted. This interface is
   // only used when doing importing via the function importing pass. The pass
   // is only enabled when testing importing via the 'opt' tool, which does
   // not do the ThinLink that would normally determine what values to promote.
   for (auto &I : *Index) {
-    for (auto &S : I.second) {
+    for (auto &S : I.second.SummaryList) {
       if (GlobalValue::isLocalLinkage(S->linkage()))
         S->setLinkage(GlobalValue::ExternalLinkage);
     }
   }
 
   // Next we need to promote to global scope and rename any local values that
   // are potentially exported to other modules.
   if (renameModuleForThinLTO(M, *Index, nullptr)) {

llvm/trunk/lib/Transforms/IPO/LowerTypeTests.cpp

if (ExportSummary) {
     DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
     for (auto &P : TypeIdInfo) {
       if (auto *TypeId = dyn_cast<MDString>(P.first))
         MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
             TypeId);
     }
 
     for (auto &P : *ExportSummary) {
-      for (auto &S : P.second) {
+      for (auto &S : P.second.SummaryList) {
         auto *FS = dyn_cast<FunctionSummary>(S.get());
         if (!FS)
           continue;
         // FIXME: Only add live functions.
         for (GlobalValue::GUID G : FS->type_tests())
           for (Metadata *MD : MetadataByGUID[G])
             AddTypeIdUse(MD).IsExported = true;
       }

llvm/trunk/lib/Transforms/IPO/WholeProgramDevirt.cpp

if (ExportSummary) {
     DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
     for (auto &P : TypeIdMap) {
       if (auto *TypeId = dyn_cast<MDString>(P.first))
         MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
             TypeId);
     }
 
     for (auto &P : *ExportSummary) {
-      for (auto &S : P.second) {
+      for (auto &S : P.second.SummaryList) {
         auto *FS = dyn_cast<FunctionSummary>(S.get());
         if (!FS)
           continue;
         // FIXME: Only add live functions.
         for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls()) {
           for (Metadata *MD : MetadataByGUID[VF.GUID]) {
             CallSlots[{MD, VF.Offset}].CSInfo.SummaryHasTypeTestAssumeUsers =
                 true;

llvm/trunk/tools/llvm-link/llvm-link.cpp

for (const auto &File : Files) {
     if (!SummaryIndex.empty()) {
       std::unique_ptr<ModuleSummaryIndex> Index =
           ExitOnErr(llvm::getModuleSummaryIndexForFile(SummaryIndex));
 
       // Conservatively mark all internal values as promoted, since this tool
       // does not do the ThinLink that would normally determine what values to
       // promote.
       for (auto &I : *Index) {
-        for (auto &S : I.second) {
+        for (auto &S : I.second.SummaryList) {
           if (GlobalValue::isLocalLinkage(S->linkage()))
             S->setLinkage(GlobalValue::ExternalLinkage);
         }
       }
 
       // Promotion
       if (renameModuleForThinLTO(*M, *Index))
         return true;

llvm/trunk/tools/llvm-lto/llvm-lto.cpp

for (auto &Filename : InputFilenames) {
     std::unique_ptr<ModuleSummaryIndex> Index =
         ExitOnErr(llvm::getModuleSummaryIndexForFile(Filename));
     // Skip files without a module summary.
     if (!Index)
       report_fatal_error(Filename + " does not contain an index");
 
     unsigned Calls = 0, Refs = 0, Functions = 0, Alias = 0, Globals = 0;
     for (auto &Summaries : *Index) {
-      for (auto &Summary : Summaries.second) {
+      for (auto &Summary : Summaries.second.SummaryList) {
         Refs += Summary->refs().size();
         if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
           Functions++;
           Calls += FuncSummary->calls().size();
         } else if (isa<AliasSummary>(Summary.get()))
           Alias++;
         else
           Globals++;