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

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.

Differential Revision: https://reviews.llvm.org/D32471

llvm-svn: 302108

3 files changed, 45 insertions, 56 deletions

diff --git a/llvm/lib/Transforms/IPO/FunctionImport.cpp b/llvm/lib/Transforms/IPO/FunctionImport.cpp
index c7ef2494e3b..7ed07d63c62 100644
--- a/llvm/lib/Transforms/IPO/FunctionImport.cpp
+++ b/llvm/lib/Transforms/IPO/FunctionImport.cpp
@@ -117,7 +117,7 @@ namespace {
 /// - [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,
@@ -168,19 +168,6 @@ selectCallee(const ModuleSummaryIndex &Index,
   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>;
 
@@ -194,19 +181,23 @@ static void computeImportForFunction(
     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;
     }
@@ -222,8 +213,8 @@ static void computeImportForFunction(
     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;
@@ -255,7 +246,7 @@ static void computeImportForFunction(
     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.
@@ -271,7 +262,7 @@ static void computeImportForFunction(
     // 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
@@ -291,7 +282,7 @@ static void computeImportForFunction(
     }
 
     // Insert the newly imported function to the worklist.
-    Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, GUID);
+    Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, VI.getGUID());
   }
 }
 
@@ -431,57 +422,56 @@ DenseSet<GlobalValue::GUID> llvm::computeDeadSymbols(
   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);
         }
       }
     }
@@ -490,10 +480,9 @@ DenseSet<GlobalValue::GUID> llvm::computeDeadSymbols(
   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 "
@@ -825,7 +814,7 @@ static bool doImportingForModule(Module &M) {
   // 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);
     }
diff --git a/llvm/lib/Transforms/IPO/LowerTypeTests.cpp b/llvm/lib/Transforms/IPO/LowerTypeTests.cpp
index 785207efbe5..ca4ee92f971 100644
--- a/llvm/lib/Transforms/IPO/LowerTypeTests.cpp
+++ b/llvm/lib/Transforms/IPO/LowerTypeTests.cpp
@@ -1440,7 +1440,7 @@ bool LowerTypeTestsModule::lower() {
     }
 
     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;
diff --git a/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp b/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp
index cb7d487b68b..aae22c5457b 100644
--- a/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp
+++ b/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp
@@ -1322,7 +1322,7 @@ bool DevirtModule::run() {
     }
 
     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;