Revert "[ThinLTO] Ensure we always select the same function copy to import"

This reverts commits r337050 and r337059. Caused failure in
reverse-iteration bot that needs more investigation.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@337081 91177308-0d34-0410-b5e6-96231b3b80d8

7 files changed, 77 insertions, 194 deletions

diff --git a/include/llvm/Transforms/IPO/FunctionImport.h b/include/llvm/Transforms/IPO/FunctionImport.h
index 120a34e1593..369a12e5e90 100644
--- a/include/llvm/Transforms/IPO/FunctionImport.h
+++ b/include/llvm/Transforms/IPO/FunctionImport.h
@@ -33,17 +33,11 @@ class Module;
 /// based on the provided summary informations.
 class FunctionImporter {
 public:
-  /// Set of functions to import from a source module. Each entry is a set
-  /// containing all the GUIDs of all functions to import for a source module.
-  using FunctionsToImportTy = std::unordered_set<GlobalValue::GUID>;
-
-  /// Map of callee GUID considered for import into a given module to a pair
-  /// consisting of the largest threshold applied when deciding whether to
-  /// import it and, if we decided to import, a pointer to the summary instance
-  /// imported. If we decided not to import, the summary will be nullptr.
-  using ImportThresholdsTy =
-      DenseMap<GlobalValue::GUID,
-               std::pair<unsigned, const GlobalValueSummary *>>;
+  /// Set of functions to import from a source module. Each entry is a map
+  /// containing all the functions to import for a source module.
+  /// The keys is the GUID identifying a function to import, and the value
+  /// is the threshold applied when deciding to import it.
+  using FunctionsToImportTy = std::map<GlobalValue::GUID, unsigned>;
 
   /// The map contains an entry for every module to import from, the key being
   /// the module identifier to pass to the ModuleLoader. The value is the set of
diff --git a/lib/LTO/LTO.cpp b/lib/LTO/LTO.cpp
index 3ce23152d0c..34cca32e06e 100644
--- a/lib/LTO/LTO.cpp
+++ b/lib/LTO/LTO.cpp
@@ -156,7 +156,7 @@ static void computeCacheKey(
 
     AddUint64(Entry.second.size());
     for (auto &Fn : Entry.second)
-      AddUint64(Fn);
+      AddUint64(Fn.first);
   }
 
   // Include the hash for the resolved ODR.
@@ -221,7 +221,7 @@ static void computeCacheKey(
   // so we need to collect their used resolutions as well.
   for (auto &ImpM : ImportList)
     for (auto &ImpF : ImpM.second)
-      AddUsedThings(Index.findSummaryInModule(ImpF, ImpM.first()));
+      AddUsedThings(Index.findSummaryInModule(ImpF.first, ImpM.first()));
 
   auto AddTypeIdSummary = [&](StringRef TId, const TypeIdSummary &S) {
     AddString(TId);
diff --git a/lib/Transforms/IPO/FunctionImport.cpp b/lib/Transforms/IPO/FunctionImport.cpp
index 15808a07389..c2907937e70 100644
--- a/lib/Transforms/IPO/FunctionImport.cpp
+++ b/lib/Transforms/IPO/FunctionImport.cpp
@@ -262,7 +262,7 @@ static void computeImportForReferencedGlobals(
           !RefSummary->modulePath().empty() &&
           !GlobalValue::isInterposableLinkage(RefSummary->linkage()) &&
           RefSummary->refs().empty()) {
-        ImportList[RefSummary->modulePath()].insert(VI.getGUID());
+        ImportList[RefSummary->modulePath()][VI.getGUID()] = 1;
         if (ExportLists)
           (*ExportLists)[RefSummary->modulePath()].insert(VI.getGUID());
         break;
@@ -278,8 +278,7 @@ static void computeImportForFunction(
     const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
     SmallVectorImpl<EdgeInfo> &Worklist,
     FunctionImporter::ImportMapTy &ImportList,
-    StringMap<FunctionImporter::ExportSetTy> *ExportLists,
-    FunctionImporter::ImportThresholdsTy &ImportThresholds) {
+    StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
   computeImportForReferencedGlobals(Summary, DefinedGVSummaries, ImportList,
                                     ExportLists);
   static int ImportCount = 0;
@@ -316,85 +315,19 @@ static void computeImportForFunction(
     const auto NewThreshold =
         Threshold * GetBonusMultiplier(Edge.second.getHotness());
 
-    auto IT = ImportThresholds.insert(
-        std::make_pair(VI.getGUID(), std::make_pair(NewThreshold, nullptr)));
-    bool PreviouslyVisited = !IT.second;
-    auto &ProcessedThreshold = IT.first->second.first;
-    auto &CalleeSummary = IT.first->second.second;
-
-    const FunctionSummary *ResolvedCalleeSummary = nullptr;
-    if (CalleeSummary) {
-      assert(PreviouslyVisited);
-      // 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 (so that its own callee chains
-      // can be considered with the higher threshold).
-      if (NewThreshold <= ProcessedThreshold) {
-        LLVM_DEBUG(
-            dbgs() << "ignored! Target was already imported with Threshold "
-                   << ProcessedThreshold << "\n");
-        continue;
-      }
-      // Update with new larger threshold.
-      ProcessedThreshold = NewThreshold;
-      ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
-    } else {
-      // If we already rejected importing a callee at the same or higher
-      // threshold, don't waste time calling selectCallee.
-      if (PreviouslyVisited && NewThreshold <= ProcessedThreshold) {
-        LLVM_DEBUG(
-            dbgs() << "ignored! Target was already rejected with Threshold "
-            << ProcessedThreshold << "\n");
-        continue;
-      }
+    auto *CalleeSummary = selectCallee(Index, VI.getSummaryList(), NewThreshold,
+                                       Summary.modulePath());
+    if (!CalleeSummary) {
+      LLVM_DEBUG(
+          dbgs() << "ignored! No qualifying callee with summary found.\n");
+      continue;
+    }
 
-      CalleeSummary = selectCallee(Index, VI.getSummaryList(), NewThreshold,
-                                   Summary.modulePath());
-      if (!CalleeSummary) {
-        // Update with new larger threshold if this was a retry (otherwise
-        // we would have already inserted with NewThreshold above).
-        if (PreviouslyVisited)
-          ProcessedThreshold = NewThreshold;
-        LLVM_DEBUG(
-            dbgs() << "ignored! No qualifying callee with summary found.\n");
-        continue;
-      }
+    // "Resolve" the summary
+    const auto *ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary->getBaseObject());
 
-      // "Resolve" the summary
-      CalleeSummary = CalleeSummary->getBaseObject();
-      ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
-
-      assert(ResolvedCalleeSummary->instCount() <= NewThreshold &&
-             "selectCallee() didn't honor the threshold");
-
-      auto ExportModulePath = ResolvedCalleeSummary->modulePath();
-      auto ILI = ImportList[ExportModulePath].insert(VI.getGUID());
-      // We previously decided to import this GUID definition if it was already
-      // inserted in the set of imports from the exporting module.
-      bool PreviouslyImported = !ILI.second;
-
-      // Make exports in the source module.
-      if (ExportLists) {
-        auto &ExportList = (*ExportLists)[ExportModulePath];
-        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);
-          }
-        }
-      }
-    }
+    assert(ResolvedCalleeSummary->instCount() <= NewThreshold &&
+           "selectCallee() didn't honor the threshold");
 
     auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
       // Adjust the threshold for next level of imported functions.
@@ -409,8 +342,44 @@ static void computeImportForFunction(
         Edge.second.getHotness() == CalleeInfo::HotnessType::Hot;
     const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite);
 
+    auto ExportModulePath = ResolvedCalleeSummary->modulePath();
+    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) {
+      LLVM_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;
+
     ImportCount++;
 
+    // Make exports in the source module.
+    if (ExportLists) {
+      auto &ExportList = (*ExportLists)[ExportModulePath];
+      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, VI.getGUID());
   }
@@ -426,7 +395,6 @@ static void ComputeImportForModule(
   // Worklist contains the list of function imported in this module, for which
   // we will analyse the callees and may import further down the callgraph.
   SmallVector<EdgeInfo, 128> Worklist;
-  FunctionImporter::ImportThresholdsTy ImportThresholds;
 
   // Populate the worklist with the import for the functions in the current
   // module
@@ -448,7 +416,7 @@ static void ComputeImportForModule(
     LLVM_DEBUG(dbgs() << "Initialize import for " << VI << "\n");
     computeImportForFunction(*FuncSummary, Index, ImportInstrLimit,
                              DefinedGVSummaries, Worklist, ImportList,
-                             ExportLists, ImportThresholds);
+                             ExportLists);
   }
 
   // Process the newly imported functions and add callees to the worklist.
@@ -456,10 +424,17 @@ static void ComputeImportForModule(
     auto FuncInfo = Worklist.pop_back_val();
     auto *Summary = std::get<0>(FuncInfo);
     auto Threshold = std::get<1>(FuncInfo);
+    auto GUID = std::get<2>(FuncInfo);
+
+    // Check if we later added this summary with a higher threshold.
+    // If so, skip this entry.
+    auto ExportModulePath = Summary->modulePath();
+    auto &LatestProcessedThreshold = ImportList[ExportModulePath][GUID];
+    if (LatestProcessedThreshold > Threshold)
+      continue;
 
     computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries,
-                             Worklist, ImportList, ExportLists,
-                             ImportThresholds);
+                             Worklist, ImportList, ExportLists);
   }
 }
 
@@ -476,6 +451,11 @@ static bool isGlobalVarSummary(const ModuleSummaryIndex &Index,
 
 static GlobalValue::GUID getGUID(GlobalValue::GUID G) { return G; }
 
+static GlobalValue::GUID
+getGUID(const std::pair<const GlobalValue::GUID, unsigned> &P) {
+  return P.first;
+}
+
 template <class T>
 static unsigned numGlobalVarSummaries(const ModuleSummaryIndex &Index,
                                       T &Cont) {
@@ -594,8 +574,9 @@ void llvm::ComputeCrossModuleImportForModuleFromIndex(
     // e.g. record required linkage changes.
     if (Summary->modulePath() == ModulePath)
       continue;
-    // Add an entry to provoke importing by thinBackend.
-    ImportList[Summary->modulePath()].insert(GUID);
+    // 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;
   }
 #ifndef NDEBUG
   dumpImportListForModule(Index, ModulePath, ImportList);
@@ -717,10 +698,10 @@ void llvm::gatherImportedSummariesForModule(
     const auto &DefinedGVSummaries =
         ModuleToDefinedGVSummaries.lookup(ILI.first());
     for (auto &GI : ILI.second) {
-      const auto &DS = DefinedGVSummaries.find(GI);
+      const auto &DS = DefinedGVSummaries.find(GI.first);
       assert(DS != DefinedGVSummaries.end() &&
              "Expected a defined summary for imported global value");
-      SummariesForIndex[GI] = DS->second;
+      SummariesForIndex[GI.first] = DS->second;
     }
   }
 }
diff --git a/test/Transforms/FunctionImport/Inputs/funcimport_resolved1.ll b/test/Transforms/FunctionImport/Inputs/funcimport_resolved1.ll
deleted file mode 100644
index 2b2443c96af..00000000000
--- a/test/Transforms/FunctionImport/Inputs/funcimport_resolved1.ll
+++ /dev/null
@@ -1,34 +0,0 @@
-target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-apple-macosx10.11.0"
-
-define void @foo() {
-  call void @linkonceodrfunc()
-  call void @linkonceodrfunc2()
-  ret void
-}
-
-define linkonce_odr void @linkonceodrfunc() {
-  call void @f()
-  call void @f()
-  call void @f()
-  call void @f()
-  call void @f()
-  call void @f()
-  call void @f()
-  ret void
-}
-
-define linkonce_odr void @linkonceodrfunc2() {
-  call void @f()
-  call void @f()
-  call void @f()
-  call void @f()
-  call void @f()
-  call void @f()
-  call void @f()
-  ret void
-}
-
-define internal void @f() {
-  ret void
-}
diff --git a/test/Transforms/FunctionImport/Inputs/funcimport_resolved2.ll b/test/Transforms/FunctionImport/Inputs/funcimport_resolved2.ll
deleted file mode 100644
index 278a7f4553f..00000000000
--- a/test/Transforms/FunctionImport/Inputs/funcimport_resolved2.ll
+++ /dev/null
@@ -1,6 +0,0 @@
-target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-apple-macosx10.11.0"
-
-define linkonce_odr void @linkonceodrfunc() {
-  ret void
-}
diff --git a/test/Transforms/FunctionImport/funcimport_resolved.ll b/test/Transforms/FunctionImport/funcimport_resolved.ll
deleted file mode 100644
index b256a613602..00000000000
--- a/test/Transforms/FunctionImport/funcimport_resolved.ll
+++ /dev/null
@@ -1,52 +0,0 @@
-; Test to ensure that we always select the same copy of a linkonce function
-; when it is encountered with different thresholds. When we encounter the
-; copy in funcimport_resolved1.ll with a higher threshold via the direct call
-; from main(), it will be selected for importing. When we encounter it with a
-; lower threshold by reaching it from the deeper call chain via foo(), it
-; won't be selected for importing. We don't want to select both the copy from
-; funcimport_resolved1.ll and the smaller one from funcimport_resolved2.ll,
-; leaving it up to the backend to figure out which one to actually import.
-; The linkonce_odr may have different instruction counts in practice due to
-; different inlines in the compile step.
-
-; Require asserts so we can use -debug-only
-; REQUIRES: asserts
-
-; REQUIRES: x86-registered-target
-
-; RUN: opt -module-summary %s -o %t.bc
-; RUN: opt -module-summary %p/Inputs/funcimport_resolved1.ll -o %t2.bc
-; RUN: opt -module-summary %p/Inputs/funcimport_resolved2.ll -o %t3.bc
-
-; First do a sanity check that all callees are imported with the default
-; instruction limit
-; RUN: llvm-lto2 run %t.bc %t2.bc %t3.bc -o %t4 -r=%t.bc,_main,pl -r=%t.bc,_linkonceodrfunc,l -r=%t.bc,_foo,l -r=%t2.bc,_foo,pl -r=%t2.bc,_linkonceodrfunc,pl -r=%t2.bc,_linkonceodrfunc2,pl -r=%t3.bc,_linkonceodrfunc,l -thinlto-threads=1 -debug-only=function-import 2>&1 | FileCheck %s --check-prefix=INSTLIMDEFAULT
-; INSTLIMDEFAULT: Is importing function {{.*}} foo from {{.*}}funcimport_resolved1.ll
-; INSTLIMDEFAULT: Is importing function {{.*}} linkonceodrfunc from {{.*}}funcimport_resolved1.ll
-; INSTLIMDEFAULT: Is importing function {{.*}} linkonceodrfunc2 from {{.*}}funcimport_resolved1.ll
-; INSTLIMDEFAULT: Is importing function {{.*}} f from {{.*}}funcimport_resolved1.ll
-; INSTLIMDEFAULT-NOT: Is importing function {{.*}} linkonceodrfunc from {{.*}}funcimport_resolved2.ll
-
-; Now run with the lower threshold that will only allow linkonceodrfunc to be
-; imported from funcimport_resolved1.ll when encountered via the direct call
-; from main(). Ensure we don't also select the copy in funcimport_resolved2.ll
-; when it is encountered via the deeper call chain.
-; RUN: llvm-lto2 run %t.bc %t2.bc %t3.bc -o %t4 -r=%t.bc,_main,pl -r=%t.bc,_linkonceodrfunc,l -r=%t.bc,_foo,l -r=%t2.bc,_foo,pl -r=%t2.bc,_linkonceodrfunc,pl -r=%t2.bc,_linkonceodrfunc2,pl -r=%t3.bc,_linkonceodrfunc,l -thinlto-threads=1 -debug-only=function-import -import-instr-limit=8 2>&1 | FileCheck %s --check-prefix=INSTLIM8
-; INSTLIM8: Is importing function {{.*}} foo from {{.*}}funcimport_resolved1.ll
-; INSTLIM8: Is importing function {{.*}} linkonceodrfunc from {{.*}}funcimport_resolved1.ll
-; INSTLIM8: Not importing function {{.*}} linkonceodrfunc2 from {{.*}}funcimport_resolved1.ll
-; INSTLIM8: Is importing function {{.*}} f from {{.*}}funcimport_resolved1.ll
-; INSTLIM8-NOT: Is importing function {{.*}} linkonceodrfunc from {{.*}}funcimport_resolved2.ll
-
-target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-apple-macosx10.11.0"
-
-define i32 @main() #0 {
-entry:
-  call void (...) @foo()
-  call void (...) @linkonceodrfunc()
-  ret i32 0
-}
-
-declare void @foo(...) #1
-declare void @linkonceodrfunc(...) #1
diff --git a/tools/llvm-link/llvm-link.cpp b/tools/llvm-link/llvm-link.cpp
index b7a888375b3..a50b26da731 100644
--- a/tools/llvm-link/llvm-link.cpp
+++ b/tools/llvm-link/llvm-link.cpp
@@ -262,7 +262,7 @@ static bool importFunctions(const char *argv0, Module &DestModule) {
       errs() << "Importing " << FunctionName << " from " << FileName << "\n";
 
     auto &Entry = ImportList[FileName];
-    Entry.insert(F->getGUID());
+    Entry.insert(std::make_pair(F->getGUID(), /* (Unused) threshold */ 1.0));
   }
   auto CachedModuleLoader = [&](StringRef Identifier) {
     return ModuleLoaderCache.takeModule(Identifier);