ThinLTO: use the callgraph from the combined index to drive the FunctionImporter

[mehdi_amini]

Summary

Now that the summary contains the full reference/call graph, we can
replace the existing function importer that loads and inspect the IR
to iteratively walk the call graph by a traversal based purely on the
summary information. Decouple the actual importing decision from any
IR manipulation.

[tejohnson]

Thanks! A few comments/questions below.

include/llvm/Transforms/IPO/FunctionImport.h

50

Need a description of what is in each ImportList entry. Realize this could be deduced by reading ahead to the next comment, but would be good to include here too.

60

s/enty/entry/

61

Outer StringMap has an entry for every Module we are importing to, with an entry for each Module we are importing from, right? Maybe make that clearer by changing the first sentence above to "ImportLists will be populated with an entry for every Module we are importing into."

Might be clearer if you use typedefs for each map.

lib/LTO/ThinLTOCodeGenerator.cpp

374

Initialize these two maps with the module count as done in ThinLTOCodeGenerator::crossModuleImport

lib/Transforms/IPO/FunctionImport.cpp

69

• Prioritize copies from a module already being imported from (reduces # source modules parsed/linked)
• Prioritize any that has profile data, although we don't have that info here (not sure how COMDAT profile matching works on llvm, I know on gcc only the selected or any inlined/selected copies would get profile data, may be different on llvm due to single profile database?)

74

I think this can be an assert? We should have a summary for every GlobalValueInfo in the combined map, and presumably it should be a FunctionSummary type since we got here via the GUID of a call graph edge.

111

Give more meaningful message here? Maybe just as simple as "ignored! No qualifying callee with summary found."

127–128

This should be an assert as selectCallee already checked this condition.

156

This only adds the called functions, I think you need to do the same for the refs().

166

Can this be an assert?

168

Extraneous ";"?

260

Comment about ignoring global variables (which should be the only reason this is null?).

262

Isn't this the number of modules being exported from in total? I.e. the size of this will monotonically increase as we invoke ComputeImportForModule across all the modules. Message is confusing - this isn't the number of exports from this module.

263

Use GUID instead of GlobalList.first for consistency/clarity.

302

GlobalsToImport here and in map name since it covers gvars now too.

313

Use your new getGUID() here and in alias handling below too. Also, needs merge as the existing static getGUID() has moved to GlobalValue from Function.

318

Add comment about why this is done?

364

This patch seems to undo the renaming done in r263513.

416

Another renaming that was undone by patch (bad merge?)

443

Note the export lists are not useful at this point since in this case we are already in the back end and we can't communicate this info to the source module which is presumably being compiled in a separate thread or backend process (in the distributed build case). Probably needs a comment about needing to be conservative when function importing being done in the backend and assume for now that all symbols may be exported. To get better about this in the distributed build case we will need to compute this info in the plugin and save it somewhere (in the index?) for consumption by the backends. For the single machine case where gold is the linker it will have to be reworked similar to what you have done in LTOCodeGenerator to do the importing computation ahead of time.

test/Transforms/FunctionImport/adjustable_threshold.ll

7

Why these changes of using .bc instead of .ll? Is it needed or at least independent and can be committed separately?

[mehdi_amini]

Thanks, I'll fix all of these comments, a few answers in the meantime.

lib/LTO/ThinLTOCodeGenerator.cpp

374

Yes! I was waiting for my changes on the StringMap to be checked in (committed yesterday).

lib/Transforms/IPO/FunctionImport.cpp

364

Probably an issue when rebasing on top of your changes.

443

You can call ComputeCrossModuleImport and get the same answer in every backend jobs.
By moving this code a few lines above before the renameModuleforThinLTO we'll be able to use the export list to limit the renaming in the source module.

test/Transforms/FunctionImport/adjustable_threshold.ll

7

It is needed: the summary will contains the module path as a string pointing to the .bc.
The importer will not be able to walk the graph because if won't find the modules in the index.

[davidxl]

lib/Transforms/IPO/FunctionImport.cpp

67

Why not passing a reference of the Edge to 'selectCallee'. We will need to look at profile data in the future.

69

In LLVM, comdat function's profile counters will also be put into comdat, so there should be no need to differentiate based on profile availability.

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

67

I think the profile info will not impact *which* callee you select right? What do you expect to do with this information at this level?

[davidxl]

lib/Transforms/IPO/FunctionImport.cpp

67

It will impact importing strategy. For instance increased threshold for hot callsites and reduced threshold for extreme cold ones. The summary Edge can also contain other nice bits (such as has constant argument etc) which will help importing more precisely.

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

69

Good news!

443

As discussed on IRC, this will work for the time being (assuming all invocations use the same thresholds etc). Longer term, compute this info in the plugin (and serialize out for distributed build backends).

[mehdi_amini]

lib/Transforms/IPO/FunctionImport.cpp

67

I agree, it is not clear to me that exposing the "Edge" here is the right abstraction (one could modifying the Threshold at call site to include a PGO bias for instance, even if it is probably not the right thing either).

I think that I can safely leave this for the larger refactoring work that will follow when we will rework the cost model for importing.

[davidxl]

lib/Transforms/IPO/FunctionImport.cpp

67

Sounds fine to me.

[mehdi_amini]

Address Teresa's comments

[mehdi_amini]

Update one comment

[mehdi_amini]

include/llvm/Transforms/IPO/FunctionImport.h

61

Typedef solve it all :)

I'll probably commit a subsequent cleanup to make GUID a typedef as well.

lib/Transforms/IPO/FunctionImport.cpp

67

Great, thanks David!

69

Updated the comment.

74

I think this was originally an assert and I figured later it was a legit case. Can't remember, will turn back into an assert for now.

156

This was intentional, comment added.

318

I have no idea, I remember copying it from what I was tracking in the ModuleLinker/IRMover. But can't retrieve it now, we want to import an alias to a global variable, should we import the global as well if it is link once?

[mehdi_amini]

Fix typedefs

[tejohnson]

include/llvm/Transforms/IPO/FunctionImport.h

28

s/function/functions
s/. each/. Each/

35

Incomplete sentence "The value for"

38–39

s/functions/function/
Actually, this needs to hold global variables that are exported as well, right? Maybe say "for every global value the module exports".

Also, not a map. So maybe ExportSetTy in addition to comment fix?

lib/Transforms/IPO/FunctionImport.cpp

156

True that we don't import globals, but we do export references to them if they are referenced from a function that is imported elsewhere. So presumably those references should be added to the export list as they may need to be promoted/renamed.

319

Oh, I know why. We can't have an alias to an available_externally def, since that is actually a declaration for the linker, and most imported defs are given available_externally linkage (except linkonce which stays the same linkage). This is the same logic as in FunctionImportGlobalProcessing::doImportAsDefinition(). I think there might have been more comments around that at one point but they gotten lost when the code moved around.

[mehdi_amini]

Update for Teresa's comments

[mehdi_amini]

Thanks, good catch here. Updated!

lib/Transforms/IPO/FunctionImport.cpp

156

Oh, good point, my previous answer was totally wrong, I thought we were looking at the "import" list here. When I wrote the original code I intended Summary->edge() to iterate over both calls() and refs(). Fixed!

319

Updated comment

[tejohnson]

LGTM, just a couple nits below. Thanks!

lib/Transforms/IPO/FunctionImport.cpp

110

Nit: unneeded braces

167

Maybe "Mark all functions and globals referenced by this function as exported to the outside if they are defined in the same source module."?

[mehdi_amini]

Update before commit

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

119

This can be removed now.

[mehdi_amini]

Even more cleanup :)

[mehdi_amini]

r264503

include/llvm/Transforms/IPO/FunctionImport.h

 //===- llvm/Transforms/IPO/FunctionImport.h - ThinLTO importing -*- C++ -*-===//
 //
 //                      The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_FUNCTIONIMPORT_H
 #define LLVM_FUNCTIONIMPORT_H
 
 #include "llvm/ADT/StringMap.h"
+
 #include <functional>
+#include <map>
+#include <unordered_set>
 
 namespace llvm {
 class LLVMContext;
 class Module;
 class ModuleSummaryIndex;
 
 /// The function importer is automatically importing function from other modules
 /// based on the provided summary informations.
 class FunctionImporter {
+public:
+  /// List of function to import from a source module. each entry is a map
+  /// containing all the functions to import for a source module.
+  /// The keys indicate the GUID identifying a function to import, and the value
+  /// is the threshold applied when deciding to import it.
+  typedef std::map<uint64_t, unsigned> FunctionsToImportTy;
+
+  /// The map contains an entry for every module to import from, the key being
+  /// the module identifier to pass to the ModuleLoader. The value for
+  typedef StringMap<FunctionsToImportTy> ImportMapTy;
 
-  /// The summaries index used to trigger importing.
-  const ModuleSummaryIndex &Index;
-
-  /// Factory function to load a Module for a given identifier
-  std::function<std::unique_ptr<Module>(StringRef Identifier)> ModuleLoader;
+  /// The map contains an entry for every functions the module exports.
+  typedef std::unordered_set<uint64_t> ExportMapTy;
 
-public:
   /// Create a Function Importer.
   FunctionImporter(
       const ModuleSummaryIndex &Index,
       std::function<std::unique_ptr<Module>(StringRef Identifier)> ModuleLoader)
       : Index(Index), ModuleLoader(ModuleLoader) {}
 
-  /// Import functions in Module \p M based on the summary informations.
-  bool importFunctions(Module &M);
+  /// Import functions in Module \p M based on the supplied import list.
+  bool importFunctions(Module &M, const ImportMapTy &ImportList);
+
+private:
+  /// The summaries index used to trigger importing.
+  const ModuleSummaryIndex &Index;
+
+  /// Factory function to load a Module for a given identifier
+  std::function<std::unique_ptr<Module>(StringRef Identifier)> ModuleLoader;
 };
+
+/// Compute all the imports and exports for every module in the Index.
+///
+/// \p ImportLists will be populated with an entry for every Module we are
+/// importing into. This entry is itself a map that can be passed to
+/// FunctionImporter::importFunctions() above (see description there).
+///
+/// \p ExportLists contains for each Module the set of globals (GUID) that will
+/// be imported by another module, or referenced by such a function. I.e. this
+/// is the set of globals that need to be promoted/renamed appropriately.
+void ComputeCrossModuleImport(
+    const ModuleSummaryIndex &Index,
+    StringMap<FunctionImporter::ImportMapTy> &ImportLists,
+    StringMap<FunctionImporter::ExportMapTy> &ExportLists);
 }
 
 #endif // LLVM_FUNCTIONIMPORT_H

lib/LTO/ThinLTOCodeGenerator.cpp

 
 static void promoteModule(Module &TheModule, const ModuleSummaryIndex &Index) {
   if (renameModuleForThinLTO(TheModule, Index))
     report_fatal_error("renameModuleForThinLTO failed");
 }
 
 static void crossImportIntoModule(Module &TheModule,
                                   const ModuleSummaryIndex &Index,
-                                  StringMap<MemoryBufferRef> &ModuleMap) {
+                                  StringMap<MemoryBufferRef> &ModuleMap,
+                                  const ImportMapTy &ImportList) {
   ModuleLoader Loader(TheModule.getContext(), ModuleMap);
   FunctionImporter Importer(Index, Loader);
-  Importer.importFunctions(TheModule);
+  Importer.importFunctions(TheModule, ImportList);
 }
 
 static void optimizeModule(Module &TheModule, TargetMachine &TM) {
   // Populate the PassManager
   PassManagerBuilder PMB;
   PMB.LibraryInfo = new TargetLibraryInfoImpl(TM.getTargetTriple());
   PMB.Inliner = createFunctionInliningPass();
   // FIXME: should get it from the bitcode?
// CodeGen
     PM.run(TheModule);
   }
   return make_unique<ObjectMemoryBuffer>(std::move(OutputBuffer));
 }
 
 static std::unique_ptr<MemoryBuffer>
 ProcessThinLTOModule(Module &TheModule, const ModuleSummaryIndex &Index,
                      StringMap<MemoryBufferRef> &ModuleMap, TargetMachine &TM,
+                     const ImportMapTy &ImportList,
                      ThinLTOCodeGenerator::CachingOptions CacheOptions,
                      StringRef SaveTempsDir, unsigned count) {
 
   // Save temps: after IPO.
   saveTempBitcode(TheModule, SaveTempsDir, count, ".1.IPO.bc");
 
   // "Benchmark"-like optimization: single-source case
   bool SingleModule = (ModuleMap.size() == 1);
 
   if (!SingleModule) {
     promoteModule(TheModule, Index);
 
     // Save temps: after promotion.
     saveTempBitcode(TheModule, SaveTempsDir, count, ".2.promoted.bc");
 
-    crossImportIntoModule(TheModule, Index, ModuleMap);
+    crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
 
     // Save temps: after cross-module import.
     saveTempBitcode(TheModule, SaveTempsDir, count, ".3.imported.bc");
   }
 
   optimizeModule(TheModule, TM);
 
   saveTempBitcode(TheModule, SaveTempsDir, count, ".3.opt.bc");

 }
 
 /**
  * Perform cross-module importing for the module identified by ModuleIdentifier.
  */
 void ThinLTOCodeGenerator::crossModuleImport(Module &TheModule,
                                              ModuleSummaryIndex &Index) {
   auto ModuleMap = generateModuleMap(Modules);
-  crossImportIntoModule(TheModule, Index, ModuleMap);
+
+  // Generate import/export list
+  auto ModuleCount = Index.modulePaths().size();
+  StringMap<ImportMapTy> ImportLists(ModuleCount);
+  StringMap<ExportMapTy> ExportLists(ModuleCount);
+  ComputeCrossModuleImport(Index, ImportLists, ExportLists);
+  auto &ImportList = ImportLists[TheModule.getModuleIdentifier()];
+
+  crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
 }
 
 /**
  * Perform post-importing ThinLTO optimizations.
  */
 void ThinLTOCodeGenerator::optimize(Module &TheModule) {
   initTMBuilder(TMBuilder, Triple(TheModule.getTargetTriple()));
   optimizeModule(TheModule, *TMBuilder.create());
void ThinLTOCodeGenerator::run() {
   }
 
   // Prepare the resulting object vector
   assert(ProducedBinaries.empty() && "The generator should not be reused");
   ProducedBinaries.resize(Modules.size());
 
   // Prepare the module map.
   auto ModuleMap = generateModuleMap(Modules);
+  auto ModuleCount = Modules.size();
+
+  // Collect the import/export lists for all modules from the call-graph in the
+  // combined index.
+  StringMap<ImportMapTy> ImportLists(ModuleCount);
+  StringMap<ExportMapTy> ExportLists(ModuleCount);
+  ComputeCrossModuleImport(*Index, ImportLists, ExportLists);
 
   // Parallel optimizer + codegen
   {
     ThreadPool Pool(ThreadCount);
     int count = 0;
     for (auto &ModuleBuffer : Modules) {
       Pool.async([&](int count) {
         LLVMContext Context;
         Context.setDiscardValueNames(LTODiscardValueNames);
 
         // Parse module now
         auto TheModule = loadModuleFromBuffer(ModuleBuffer, Context, false);
 
         // Save temps: original file.
         if (!SaveTempsDir.empty()) {
           saveTempBitcode(*TheModule, SaveTempsDir, count, ".0.original.bc");
         }
 
+        auto &ImportList = ImportLists[TheModule->getModuleIdentifier()];
         ProducedBinaries[count] = ProcessThinLTOModule(
-            *TheModule, *Index, ModuleMap, *TMBuilder.create(), CacheOptions,
-            SaveTempsDir, count);
+            *TheModule, *Index, ModuleMap, *TMBuilder.create(), ImportList,
+            CacheOptions, SaveTempsDir, count);
       }, count);
       count++;
     }
   }
 
   // If statistics were requested, print them out now.
   if (llvm::AreStatisticsEnabled())
     llvm::PrintStatistics();
 }

lib/Transforms/IPO/FunctionImport.cpp

 //===- FunctionImport.cpp - ThinLTO Summary-based Function Import ---------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements Function import based on summaries.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/FunctionImport.h"
 
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/IR/AutoUpgrade.h"
 #include "llvm/IR/DiagnosticPrinter.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IRReader/IRReader.h"
 #include "llvm/Linker/Linker.h"
 #include "llvm/Object/ModuleSummaryIndexObjectFile.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
 
-#include <map>
+#define DEBUG_TYPE "function-import"
 
 using namespace llvm;
 
-#define DEBUG_TYPE "function-import"
-
 /// Limit on instruction count of imported functions.
 static cl::opt<unsigned> ImportInstrLimit(
     "import-instr-limit", cl::init(100), cl::Hidden, cl::value_desc("N"),
     cl::desc("Only import functions with less than N instructions"));
 
 static cl::opt<float>
     ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7),
                       cl::Hidden, cl::value_desc("x"),
if (!Result) {
     report_fatal_error("Abort");
   }
 
   return Result;
 }
 
 namespace {
 
-/// Track functions already seen using a map that record the current
-/// Threshold and the importing decision. Since the traversal of the call graph
-/// is DFS, we can revisit a function a second time with a higher threshold. In
-/// this case and if the function was not imported the first time, it is added
-/// back to the worklist with the new threshold
-using VisitedFunctionTrackerTy = StringMap<std::pair<unsigned, bool>>;
-
-/// Helper to load on demand a Module from file and cache it for subsequent
-/// queries. It can be used with the FunctionImporter.
-class ModuleLazyLoaderCache {
-  /// Cache of lazily loaded module for import.
-  StringMap<std::unique_ptr<Module>> ModuleMap;
+/// Given a list of possible callee implementation for a call site, select one
+/// that fits the \p Threshold.
+///
+/// FIXME: select "best" instead of first that fits. But what is "best"?
+/// - 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 FunctionSummary *
+selectCallee(const GlobalValueInfoList &CalleeInfoList, unsigned Threshold) {
+  auto It = llvm::find_if(
+      CalleeInfoList, [&](const std::unique_ptr<GlobalValueInfo> &GlobInfo) {
+        assert(GlobInfo->summary() &&
+               "We should not have a Global Info without summary");
+        auto *Summary = cast<FunctionSummary>(GlobInfo->summary());
 
-  /// Retrieve a Module from the cache or lazily load it on demand.
-  std::function<std::unique_ptr<Module>(StringRef FileName)> createLazyModule;
+        if (GlobalValue::isWeakAnyLinkage(Summary->linkage()))
+          return false;
 
-public:
-  /// Create the loader, Module will be initialized in \p Context.
-  ModuleLazyLoaderCache(std::function<
-      std::unique_ptr<Module>(StringRef FileName)> createLazyModule)
-      : createLazyModule(createLazyModule) {}
-
-  /// Retrieve a Module from the cache or lazily load it on demand.
-  Module &operator()(StringRef FileName);
-
-  std::unique_ptr<Module> takeModule(StringRef FileName) {
-    auto I = ModuleMap.find(FileName);
-    assert(I != ModuleMap.end());
-    std::unique_ptr<Module> Ret = std::move(I->second);
-    ModuleMap.erase(I);
-    return Ret;
-  }
-};
+        if (Summary->instCount() > Threshold)
+          return false;
+
+        return true;
+      });
+  if (It == CalleeInfoList.end())
+    return nullptr;
 
-// Get a Module for \p FileName from the cache, or load it lazily.
-Module &ModuleLazyLoaderCache::operator()(StringRef Identifier) {
-  auto &Module = ModuleMap[Identifier];
-  if (!Module)
-    Module = createLazyModule(Identifier);
-  return *Module;
+  return cast<FunctionSummary>((*It)->summary());
 }
-} // anonymous namespace
 
-/// Walk through the instructions in \p F looking for external
-/// calls not already in the \p VisitedFunctions map. If any are
-/// found they are added to the \p Worklist for importing.
-static void findExternalCalls(
-    const Module &DestModule, Function &F, const ModuleSummaryIndex &Index,
-    VisitedFunctionTrackerTy &VisitedFunctions, unsigned Threshold,
-    SmallVectorImpl<std::pair<StringRef, unsigned>> &Worklist) {
-  // We need to suffix internal function calls imported from other modules,
-  // prepare the suffix ahead of time.
-  std::string Suffix;
-  if (F.getParent() != &DestModule)
-    Suffix =
-        (Twine(".llvm.") +
-         Twine(Index.getModuleId(F.getParent()->getModuleIdentifier()))).str();
-
-  for (auto &BB : F) {
-    for (auto &I : BB) {
-      if (isa<CallInst>(I)) {
-        auto CalledFunction = cast<CallInst>(I).getCalledFunction();
-        // Insert any new external calls that have not already been
-        // added to set/worklist.
-        if (!CalledFunction || !CalledFunction->hasName())
-          continue;
-        // Ignore intrinsics early
-        if (CalledFunction->isIntrinsic()) {
-          assert(CalledFunction->getIntrinsicID() != 0);
-          continue;
-        }
-        auto ImportedName = CalledFunction->getName();
-        auto Renamed = (ImportedName + Suffix).str();
-        // Rename internal functions
-        if (CalledFunction->hasInternalLinkage()) {
-          ImportedName = Renamed;
-        }
-        // Compute the global identifier used in the summary index.
-        auto CalledFunctionGlobalID = GlobalValue::getGlobalIdentifier(
-            CalledFunction->getName(), CalledFunction->getLinkage(),
-            CalledFunction->getParent()->getSourceFileName());
-
-        auto CalledFunctionInfo = std::make_pair(Threshold, false);
-        auto It = VisitedFunctions.insert(
-            std::make_pair(CalledFunctionGlobalID, CalledFunctionInfo));
-        if (!It.second) {
-          // This is a call to a function we already considered, if the function
-          // has been imported the first time, or if the current threshold is
-          // not higher, skip it.
-          auto &FunctionInfo = It.first->second;
-          if (FunctionInfo.second || FunctionInfo.first >= Threshold)
-            continue;
-          It.first->second = CalledFunctionInfo;
-        }
-        // Ignore functions already present in the destination module
-        auto *SrcGV = DestModule.getNamedValue(ImportedName);
-        if (SrcGV) {
-          if (GlobalAlias *SGA = dyn_cast<GlobalAlias>(SrcGV))
-            SrcGV = SGA->getBaseObject();
-          assert(isa<Function>(SrcGV) && "Name collision during import");
-          if (!cast<Function>(SrcGV)->isDeclaration()) {
-            DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Ignoring "
-                         << ImportedName << " already in DestinationModule\n");
-            continue;
-          }
-        }
+/// Return the summary for the function \p GUID that fits the \p Threshold, or
+/// null if there's no match.
+static const FunctionSummary *selectCallee(uint64_t GUID, unsigned Threshold,
+                                           const ModuleSummaryIndex &Index) {
+  auto CalleeInfoList = Index.findGlobalValueInfoList(GUID);
+  if (CalleeInfoList == Index.end()) {
+    return nullptr; // This function does not have a summary
+  }
+  return selectCallee(CalleeInfoList->second, Threshold);
+}
+
+using EdgeInfo = std::pair<const FunctionSummary *, unsigned /* Threshold */>;
+
+/// 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(
+    StringRef ModulePath, const FunctionSummary &Summary,
+    const ModuleSummaryIndex &Index, unsigned Threshold,
+    const std::map<uint64_t, FunctionSummary *> &DefinedFunctions,
+    SmallVectorImpl<EdgeInfo> &Worklist, ImportMapTy &ImportsForModule,
+    StringMap<ExportMapTy> &ExportLists) {
+  for (auto &Edge : Summary.edges()) {
+    auto GUID = Edge.first;
+    DEBUG(dbgs() << " edge -> " << GUID << " Threshold:" << Threshold << "\n");
+
+    if (DefinedFunctions.count(GUID)) {
+      DEBUG(dbgs() << "ignored! Target already in destination module.\n");
+
+    auto *CalleeSummary = selectCallee(GUID, Threshold, Index);
+    if (!CalleeSummary) {
+      DEBUG(dbgs() << "ignored! No qualifying callee with summary found.\n");
+    assert(CalleeSummary->instCount() <= Threshold &&
+           "selectCallee() didn't honor the threshold");
+
+    auto &ProcessedThreshold =
+        ImportsForModule[CalleeSummary->modulePath()][GUID];
+    /// 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 > Threshold) {
+      DEBUG(dbgs() << "ignored! Target was already seen with Threshold "
+                   << ProcessedThreshold << "\n");
+    // Mark this function as imported in this module, with the current Threshold
+    ProcessedThreshold = Threshold;
 
-        Worklist.push_back(std::make_pair(It.first->getKey(), Threshold));
-        DEBUG(dbgs() << DestModule.getModuleIdentifier()
-                     << ": Adding callee for : " << ImportedName << " : "
-                     << F.getName() << "\n");
+    // Make exports
+    auto ExportModulePath = CalleeSummary->modulePath();
+    auto ExportList = ExportLists[ExportModulePath];
+    ExportList.insert(GUID);
+    // Insert every symbol referenced by this function in the source module as
+    // exported from outside as well.
+    for (auto &CalleeEdge : CalleeSummary->edges()) {
+      auto CalleeGUID = CalleeEdge.first;
+      auto CalleeInfoList = Index.findGlobalValueInfoList(CalleeGUID);
+      if (CalleeInfoList == Index.end()) {
+        continue; // This global does not have a summary
+      }
+      auto DefinedInCalleeModule = llvm::find_if(
+          CalleeInfoList->second,
+          [&](const std::unique_ptr<GlobalValueInfo> &GlobInfo) {
+            auto *Summary = GlobInfo->summary();
+            assert(Summary && "Unexpected GlobalValueInfo without summary");
+            if (Summary->modulePath() == ExportModulePath) {
+              return true;
             }
-    }
-  }
+            return false;
+          });
+      if (DefinedInCalleeModule != CalleeInfoList->second.end())
+        ExportList.insert(CalleeGUID);
+    }
+
+    // Insert the newly imported function to the worklist.
+    Worklist.push_back(std::make_pair(CalleeSummary, Threshold));
+
+/// 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(
+    StringRef ModulePath,
+    const std::map<uint64_t, FunctionSummary *> &DefinedFunctions,
+    const ModuleSummaryIndex &Index, ImportMapTy &ImportsForModule,
+    StringMap<ExportMapTy> &ExportLists) {
+  // 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;
+
+  // Populate the worklist with the import for the functions in the current
+  // module
+  for (auto &FuncInfo : DefinedFunctions) {
+    auto *Summary = FuncInfo.second;
+    DEBUG(dbgs() << "Initalize import for " << FuncInfo.first << "\n");
+    computeImportForFunction(ModulePath, *Summary, Index, ImportInstrLimit,
+                             DefinedFunctions, Worklist, ImportsForModule,
+                             ExportLists);
   }
 
-// Helper function: given a worklist and an index, will process all the worklist
-// and decide what to import based on the summary information.
-//
-// Nothing is actually imported, functions are materialized in their source
-// module and analyzed there.
-//
-// \p ModuleToFunctionsToImportMap is filled with the set of Function to import
-// per Module.
-static void
-GetImportList(Module &DestModule,
-              SmallVectorImpl<std::pair<StringRef, unsigned>> &Worklist,
-              VisitedFunctionTrackerTy &VisitedFunctions,
-              std::map<StringRef, DenseSet<const GlobalValue *>>
-                  &ModuleToFunctionsToImportMap,
-              const ModuleSummaryIndex &Index,
-              ModuleLazyLoaderCache &ModuleLoaderCache) {
   while (!Worklist.empty()) {
-    StringRef CalledFunctionName;
-    unsigned Threshold;
-    std::tie(CalledFunctionName, Threshold) = Worklist.pop_back_val();
-    DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Process import for "
-                 << CalledFunctionName << " with Threshold " << Threshold
-                 << "\n");
-
-    // Try to get a summary for this function call.
-    auto InfoList = Index.findGlobalValueInfoList(CalledFunctionName);
-    if (InfoList == Index.end()) {
-      DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": No summary for "
-                   << CalledFunctionName << " Ignoring.\n");
-      continue;
-    }
-    assert(!InfoList->second.empty() && "No summary, error at import?");
+    auto FuncInfo = Worklist.pop_back_val();
+    auto *Summary = FuncInfo.first;
+    auto Threshold = FuncInfo.second;
 
-    // Comdat can have multiple entries, FIXME: what do we do with them?
-    auto &Info = InfoList->second[0];
-    assert(Info && "Nullptr in list, error importing summaries?\n");
-
-    auto *Summary = dyn_cast<FunctionSummary>(Info->summary());
-    if (!Summary) {
-      // FIXME: in case we are lazyloading summaries, we can do it now.
-      DEBUG(dbgs() << DestModule.getModuleIdentifier()
-                   << ": Missing summary for  " << CalledFunctionName
-                   << ", error at import?\n");
-      llvm_unreachable("Missing summary");
-    }
-
-    if (Summary->instCount() > Threshold) {
-      DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Skip import of "
-                   << CalledFunctionName << " with " << Summary->instCount()
-                   << " instructions (limit " << Threshold << ")\n");
-      continue;
-    }
+    // Process the newly imported functions and add callees to the worklist.
+    // Adjust the threshold
+    Threshold = Threshold * ImportInstrFactor;
+
+    computeImportForFunction(ModulePath, *Summary, Index, Threshold,
+                             DefinedFunctions, Worklist, ImportsForModule,
+                             ExportLists);
+  }
 
-    // Mark the function as imported in the VisitedFunctions tracker
-    assert(VisitedFunctions.count(CalledFunctionName));
-    VisitedFunctions[CalledFunctionName].second = true;
-
-    // Get the module path from the summary.
-    auto ModuleIdentifier = Summary->modulePath();
-    DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Importing "
-                 << CalledFunctionName << " from " << ModuleIdentifier << "\n");
-
-    auto &SrcModule = ModuleLoaderCache(ModuleIdentifier);
-
-    // The function that we will import!
-    GlobalValue *SGV = SrcModule.getNamedValue(CalledFunctionName);
-
-    if (!SGV) {
-      // The function is referenced by a global identifier, which has the
-      // source file name prepended for functions that were originally local
-      // in the source module. Strip any prepended name to recover the original
-      // name in the source module.
-      std::pair<StringRef, StringRef> Split = CalledFunctionName.rsplit(':');
-      SGV = SrcModule.getNamedValue(Split.second);
-      assert(SGV && "Can't find function to import in source module");
-    }
-    if (!SGV) {
-      report_fatal_error(Twine("Can't load function '") + CalledFunctionName +
-                         "' in Module '" + SrcModule.getModuleIdentifier() +
-                         "', error in the summary?\n");
-    }
-
-    Function *F = dyn_cast<Function>(SGV);
-    if (!F && isa<GlobalAlias>(SGV)) {
-      auto *SGA = dyn_cast<GlobalAlias>(SGV);
-      F = dyn_cast<Function>(SGA->getBaseObject());
-    }
-    assert(F && "Imported Function is ... not a Function");
-
-    // We cannot import weak_any functions/aliases without possibly affecting
-    // the order they are seen and selected by the linker, changing program
-    // semantics.
-    if (SGV->hasWeakAnyLinkage()) {
-      DEBUG(dbgs() << DestModule.getModuleIdentifier()
-                   << ": Ignoring import request for weak-any "
-                   << (isa<Function>(SGV) ? "function " : "alias ")
-                   << CalledFunctionName << " from "
-                   << SrcModule.getModuleIdentifier() << "\n");
+} // anonymous namespace
+
+/// Compute all the import and export for every module in the Index.
+void llvm::ComputeCrossModuleImport(const ModuleSummaryIndex &Index,
+                                    StringMap<ImportMapTy> &ImportLists,
+                                    StringMap<ExportMapTy> &ExportLists) {
+  auto ModuleCount = Index.modulePaths().size();
+
+  // Collect for each module the list of function it defines.
+  // GUID -> Summary
+  StringMap<std::map<uint64_t, FunctionSummary *>> Module2FunctionInfoMap(
+      ModuleCount);
+
+  for (auto &GlobalList : Index) {
+    auto GUID = GlobalList.first;
+    for (auto &GlobInfo : GlobalList.second) {
+      auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobInfo->summary());
+      if (!Summary)
+        /// Ignore global variable, focus on functions
         continue;
-    }
+      DEBUG(dbgs() << "Adding definition: Module '" << Summary->modulePath()
+                   << "' defines '" << GUID << "'\n");
+      Module2FunctionInfoMap[Summary->modulePath()][GUID] = Summary;
+    }
 
-    // Add the function to the import list
-    auto &Entry = ModuleToFunctionsToImportMap[SrcModule.getModuleIdentifier()];
-    Entry.insert(F);
-
-    // Process the newly imported functions and add callees to the worklist.
-    // Adjust the threshold
-    Threshold = Threshold * ImportInstrFactor;
-    F->materialize();
-    findExternalCalls(DestModule, *F, Index, VisitedFunctions, Threshold,
-                      Worklist);
+  // For each module that has function defined, compute the import/export lists.
+  for (auto &DefinedFunctions : Module2FunctionInfoMap) {
+    auto &ImportsForModule = ImportLists[DefinedFunctions.first()];
+    DEBUG(dbgs() << "Computing import for Module '" << DefinedFunctions.first()
+                 << "'\n");
+    ComputeImportForModule(DefinedFunctions.first(), DefinedFunctions.second,
+                           Index, ImportsForModule, ExportLists);
+  }
+
+#ifndef NDEBUG
+  DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size()
+               << " modules:\n");
+  for (auto &ModuleImports : ImportLists) {
+    auto ModName = ModuleImports.first();
+    auto &Exports = ExportLists[ModName];
+    DEBUG(dbgs() << "* Module " << ModName << " exports " << Exports.size()
+                 << " functions. Imports from " << ModuleImports.second.size()
+                 << " modules.\n");
+    for (auto &Src : ModuleImports.second) {
+      auto SrcModName = Src.first();
+      DEBUG(dbgs() << " - " << Src.second.size() << " functions imported from "
+                   << SrcModName << "\n");
     }
   }
+#endif
+}
 
 // Automatically import functions in Module \p DestModule based on the summaries
 // index.
 //
-// The current implementation imports every called functions that exists in the
-// summaries index.
-bool FunctionImporter::importFunctions(Module &DestModule) {
+bool FunctionImporter::importFunctions(Module &DestModule,
+                                       const ImportMapTy &ImportList) {
   DEBUG(dbgs() << "Starting import for Module "
                << DestModule.getModuleIdentifier() << "\n");
   unsigned ImportedCount = 0;
 
-  // First step is collecting the called external functions.
-  // We keep the function name as well as the import threshold for its callees.
-  VisitedFunctionTrackerTy VisitedFunctions;
-  SmallVector<std::pair<StringRef, unsigned>, 64> Worklist;
-  for (auto &F : DestModule) {
-    if (F.isDeclaration() || F.hasFnAttribute(Attribute::OptimizeNone))
-      continue;
-    findExternalCalls(DestModule, F, Index, VisitedFunctions, ImportInstrLimit,
-                      Worklist);
-  }
-  if (Worklist.empty())
-    return false;
-
-  /// Second step: for every call to an external function, try to import it.
-
   // Linker that will be used for importing function
   Linker TheLinker(DestModule);
-
-  // Map of Module -> List of Function to import from the Module
-  std::map<StringRef, DenseSet<const GlobalValue *>>
-      ModuleToFunctionsToImportMap;
-
-  // Analyze the summaries and get the list of functions to import by
-  // populating ModuleToFunctionsToImportMap
-  ModuleLazyLoaderCache ModuleLoaderCache(ModuleLoader);
-  GetImportList(DestModule, Worklist, VisitedFunctions,
-                ModuleToFunctionsToImportMap, Index, ModuleLoaderCache);
-  assert(Worklist.empty() && "Worklist hasn't been flushed in GetImportList");
-
   // Do the actual import of functions now, one Module at a time
-  for (auto &FunctionsToImportPerModule : ModuleToFunctionsToImportMap) {
+  std::set<StringRef> ModuleNameOrderedList;
+  for (auto &FunctionsToImportPerModule : ImportList) {
+    ModuleNameOrderedList.insert(FunctionsToImportPerModule.first());
+  }
+  for (auto &Name : ModuleNameOrderedList) {
     // Get the module for the import
-    auto &FunctionsToImport = FunctionsToImportPerModule.second;
-    std::unique_ptr<Module> SrcModule =
-        ModuleLoaderCache.takeModule(FunctionsToImportPerModule.first);
+    const auto &FunctionsToImportPerModule = ImportList.find(Name);
+    assert(FunctionsToImportPerModule != ImportList.end());
+    std::unique_ptr<Module> SrcModule = ModuleLoader(Name);
     assert(&DestModule.getContext() == &SrcModule->getContext() &&
            "Context mismatch");
 
     // If modules were created with lazy metadata loading, materialize it
     // now, before linking it (otherwise this will be a noop).
     SrcModule->materializeMetadata();
     UpgradeDebugInfo(*SrcModule);
 
+    auto &ImportGUIDs = FunctionsToImportPerModule->second;
+    // Find the globals to import
+    DenseSet<const GlobalValue *> GlobalsToImport;
+    for (auto &GV : *SrcModule) {
+      if (GV.hasName() && ImportGUIDs.count(GV.getGUID())) {
+        GV.materialize();
+        GlobalsToImport.insert(&GV);
+      }
+    }
+    for (auto &GV : SrcModule->aliases()) {
+      if (!GV.hasName())
+        continue;
+      auto GUID = GV.getGUID();
+      if (ImportGUIDs.count(GUID)) {
+        GV.materialize();
+        GlobalsToImport.insert(&GV);
+        const GlobalObject *GO = GV.getBaseObject();
+        //        if (!GO->hasLinkOnceODRLinkage())
+        // When the alias is pointing to a linkonceodr, don't import
+        // FIXME: why?
+        //          continue;
+        GlobalsToImport.insert(GO);
+      }
+    }
+    for (auto &GV : SrcModule->globals()) {
+      if (!GV.hasName())
+        continue;
+      auto GUID = Function::getGUID(Function::getGlobalIdentifier(
+          GV.getName(), GV.getLinkage(), SrcModule->getModuleIdentifier()));
+      if (ImportGUIDs.count(GUID)) {
+        GV.materialize();
+        GlobalsToImport.insert(&GV);
+      }
+    }
+
     // Link in the specified functions.
-    if (renameModuleForThinLTO(*SrcModule, Index, &FunctionsToImport))
+    if (renameModuleForThinLTO(*SrcModule, Index, &GlobalsToImport))
       return true;
 
     if (TheLinker.linkInModule(std::move(SrcModule), Linker::Flags::None,
-                               &FunctionsToImport))
+                               &GlobalsToImport))
       report_fatal_error("Function Import: link error");
 
-    ImportedCount += FunctionsToImport.size();
+    ImportedCount += GlobalsToImport.size();
   }
 
   DEBUG(dbgs() << "Imported " << ImportedCount << " functions for Module "
                << DestModule.getModuleIdentifier() << "\n");
   return ImportedCount;
 }
 
 /// Summary file to use for function importing when using -function-import from
 /// the command line.
 static cl::opt<std::string>
     SummaryFile("summary-file",
                 cl::desc("The summary file to use for function importing."));
 
 static void diagnosticHandler(const DiagnosticInfo &DI) {
   raw_ostream &OS = errs();
   DiagnosticPrinterRawOStream DP(OS);
   DI.print(DP);
   OS << '\n';
 }
 
 /// Parse the summary index out of an IR file and return the summary
 /// index object if found, or nullptr if not.
 static std::unique_ptr<ModuleSummaryIndex>
 getModuleSummaryIndexForFile(StringRef Path, std::string &Error,
                              DiagnosticHandlerFunction DiagnosticHandler) {
   std::unique_ptr<MemoryBuffer> Buffer;
   ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOrErr =
       MemoryBuffer::getFile(Path);
   if (std::error_code EC = BufferOrErr.getError()) {
if (SummaryFile.empty() && !Index)
       report_fatal_error("error: -function-import requires -summary-file or "
                          "file from frontend\n");
     std::unique_ptr<ModuleSummaryIndex> IndexPtr;
     if (!SummaryFile.empty()) {
       if (Index)
         report_fatal_error("error: -summary-file and index from frontend\n");
       std::string Error;
       IndexPtr =
           getModuleSummaryIndexForFile(SummaryFile, Error, diagnosticHandler);
       if (!IndexPtr) {
         errs() << "Error loading file '" << SummaryFile << "': " << Error
                << "\n";
         return false;
       }
       Index = IndexPtr.get();
     }
 
-    // First we need to promote to global scope and rename any local values that
+    // First step is collecting the import/export lists
+    // The export list is not used yet, but could limit the amount of renaming
+    // performed in renameModuleForThinLTO()
+    StringMap<ImportMapTy> ImportLists;
+    StringMap<ExportMapTy> ExportLists;
+    ComputeCrossModuleImport(*Index, ImportLists, ExportLists);
+    auto &ImportList = ImportLists[M.getModuleIdentifier()];
+
+    // Next we need to promote to global scope and rename any local values that
     // are potentially exported to other modules.
-    if (renameModuleForThinLTO(M, *Index)) {
+    if (renameModuleForThinLTO(M, *Index, nullptr)) {
       errs() << "Error renaming module\n";
       return false;
     }
 
     // Perform the import now.
     auto ModuleLoader = [&M](StringRef Identifier) {
       return loadFile(Identifier, M.getContext());
     };
     FunctionImporter Importer(*Index, ModuleLoader);
-    return Importer.importFunctions(M);
+    return Importer.importFunctions(M, ImportList);
   }
 };
 } // anonymous namespace
 
 char FunctionImportPass::ID = 0;
 INITIALIZE_PASS_BEGIN(FunctionImportPass, "function-import",
                       "Summary Based Function Import", false, false)
 INITIALIZE_PASS_END(FunctionImportPass, "function-import",
                     "Summary Based Function Import", false, false)
 
 namespace llvm {
 Pass *createFunctionImportPass(const ModuleSummaryIndex *Index = nullptr) {
   return new FunctionImportPass(Index);
 }
 }

test/Transforms/FunctionImport/adjustable_threshold.ll

 ; Do setup work for all below tests: generate bitcode and combined index
 ; RUN: llvm-as -module-summary %s -o %t.bc
 ; RUN: llvm-as -module-summary %p/Inputs/adjustable_threshold.ll -o %t2.bc
 ; RUN: llvm-lto -thinlto -o %t3 %t.bc %t2.bc
 
 ; Test import with default progressive instruction factor
-; RUN: opt -function-import -summary-file %t3.thinlto.bc %s -import-instr-limit=10 -S | FileCheck %s --check-prefix=CHECK --check-prefix=INSTLIM-DEFAULT
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=10 -S | FileCheck %s --check-prefix=CHECK --check-prefix=INSTLIM-DEFAULT
 ; INSTLIM-DEFAULT: call void @staticfunc2.llvm.2()
 
 ; Test import with a reduced progressive instruction factor
-; RUN: opt -function-import -summary-file %t3.thinlto.bc %s -import-instr-limit=10 -import-instr-evolution-factor=0.5 -S | FileCheck %s --check-prefix=CHECK --check-prefix=INSTLIM-PROGRESSIVE
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=10 -import-instr-evolution-factor=0.5 -S | FileCheck %s --check-prefix=CHECK --check-prefix=INSTLIM-PROGRESSIVE
 ; INSTLIM-PROGRESSIVE-NOT: call void @staticfunc
 
 
 
 declare void @globalfunc1()
 declare void @globalfunc2()
 
 define void @entry() {

test/Transforms/FunctionImport/funcimport.ll

 ; Do setup work for all below tests: generate bitcode and combined index
 ; RUN: llvm-as -module-summary %s -o %t.bc
 ; RUN: llvm-as -module-summary %p/Inputs/funcimport.ll -o %t2.bc
 ; RUN: llvm-lto -thinlto -o %t3 %t.bc %t2.bc
 
 ; Do the import now
-; RUN: opt -function-import -summary-file %t3.thinlto.bc %s -S | FileCheck %s --check-prefix=CHECK --check-prefix=INSTLIMDEF
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -S | FileCheck %s --check-prefix=CHECK --check-prefix=INSTLIMDEF
 
 ; Test import with smaller instruction limit
-; RUN: opt -function-import -summary-file %t3.thinlto.bc %s -import-instr-limit=5 -S | FileCheck %s --check-prefix=CHECK --check-prefix=INSTLIM5
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -import-instr-limit=5 -S | FileCheck %s --check-prefix=CHECK --check-prefix=INSTLIM5
 ; INSTLIM5-NOT: @staticfunc.llvm.2
 
 define i32 @main() #0 {
 entry:
   call void (...) @weakalias()
   call void (...) @analias()
   call void (...) @linkoncealias()
   %call = call i32 (...) @referencestatics()

test/Transforms/FunctionImport/funcimport_alias.ll

 ; Do setup work for all below tests: generate bitcode and combined index
 ; RUN: llvm-as -module-summary %s -o %t.bc
 ; RUN: llvm-as -module-summary %p/Inputs/funcimport_alias.ll -o %t2.bc
 ; RUN: llvm-lto -thinlto -o %t3 %t.bc %t2.bc
 
 ; Do the import now. Ensures that the importer handles an external call
 ; from imported callanalias() to a function that is defined already in
 ; the dest module, but as an alias.
-; RUN: opt -function-import -summary-file %t3.thinlto.bc %s -S | FileCheck %s
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -S | FileCheck %s
 
 define i32 @main() #0 {
 entry:
   call void @callanalias()
   ret i32 0
 }
 
 @analias = alias void (), void ()* @globalfunc
 
 define void @globalfunc() #0 {
 entry:
   ret void
 }
 
 declare void @callanalias() #1
 ; CHECK-DAG: define available_externally void @callanalias()

test/Transforms/FunctionImport/funcimport_debug.ll

 ; Do setup work for all below tests: generate bitcode and combined index
 ; RUN: llvm-as -module-summary %s -o %t.bc
 ; RUN: llvm-as -module-summary %p/Inputs/funcimport_debug.ll -o %t2.bc
 ; RUN: llvm-lto -thinlto -o %t3 %t.bc %t2.bc
 
 ; Do the import now and confirm that metadata is linked for imported function.
-; RUN: opt -function-import -summary-file %t3.thinlto.bc %s -S | FileCheck %s
+; RUN: opt -function-import -summary-file %t3.thinlto.bc %t.bc -S | FileCheck %s
 
 ; CHECK: define available_externally void @func()
 
 ; Check that we have exactly two subprograms (that func's subprogram wasn't
 ; linked more than once for example), and that they are connected to
 ; the subprogram list on a compute unit.
 ; CHECK: !{{[0-9]+}} = distinct !DICompileUnit({{.*}} subprograms: ![[SPs1:[0-9]+]]
 ; CHECK: ![[SPs1]] = !{![[MAINSP:[0-9]+]]}