[ThinLTO] Only compute imports for current module in FunctionImport pass

[tejohnson]

Summary

The function import pass was computing all the imports for all the
modules in the index, and only using the imports for the current module.
Change this to instead compute only for the given module. This means
that the exports list can't be populated, but they weren't being used
anyway.

Note that if we want to use the export lists to control linkage changes,
it would be better to compute them a single time in the thin link step
and mark any required changes in the index.

[mehdi_amini]

About your note: ComputeCrossModuleImport() *is* the API I am calling in the Thin-link step.

The export list is gonna be needed to drive a "smart" promotion/renaming, so I expect it to be needed at the same stage you need the import list.
What will be the need for this?

lib/Transforms/IPO/FunctionImport.cpp

313 ↗

(On Diff #53183)

Should be refactored with ModuleSummaryIndex::collectDefinedFunctionsPerModule() after D18908, the code looks close.

[tejohnson]

In D18945#396592, @joker.eph wrote:

About your note: ComputeCrossModuleImport() *is* the API I am calling in the Thin-link step.

Right, I haven't changed that callsite and that module will also be called from the gold-plugin.

The export list is gonna be needed to drive a "smart" promotion/renaming, so I expect it to be needed at the same stage you need the import list.
What will be the need for this?

The callsite in the function importer (see the last change in this file) uses the new interface. It doesn't need to recompute all imports for all modules. Should reduce compile time in the back ends that use this pass.

[tejohnson]

In D18945#396599, @tejohnson wrote:

In D18945#396592, @joker.eph wrote:

About your note: ComputeCrossModuleImport() *is* the API I am calling in the Thin-link step.

Right, I haven't changed that callsite and that module will also be called from the gold-plugin.

Just to clarify, it can be called from the gold plugin to compute the imports and exports to:

• guide importing (when the backend threads are launched from gold, similar to what you are doing in the libLTO case
• to optimize linkage (potentially marking changes in the index for the distributed backend case)
• to determine how to stage bitcode input files onto distributed build machines.

The export list is gonna be needed to drive a "smart" promotion/renaming, so I expect it to be needed at the same stage you need the import list.
What will be the need for this?

The callsite in the function importer (see the last change in this file) uses the new interface. It doesn't need to recompute all imports for all modules. Should reduce compile time in the back ends that use this pass.

This is particularly for the distributed build case where the importing is done in the back end processes.

[mehdi_amini]

This is particularly for the distributed build case where the importing is done in the back end processes.

This is the part I'm not convinced yet, because of the part where I wrote "The export list is gonna be needed to drive a "smart" promotion/renaming, so I expect it to be needed at the same stage you need the import list."

[tejohnson]

In D18945#396617, @joker.eph wrote:

This is particularly for the distributed build case where the importing is done in the back end processes.

This is the part I'm not convinced yet, because of the part where I wrote "The export list is gonna be needed to drive a "smart" promotion/renaming, so I expect it to be needed at the same stage you need the import list."

Note you can still do this from libLTO where you are calling ComputeCrossModuleImport and renameModuleForThinLTO directly (a single time per link).

For the distributed back end case, I want to avoid doing redundant work in thousands of back ends, which it currently is doing unnecessarily. As mentioned, the smart promotion could be done by invoking the full ComputeCrossModuleImport in the thin link step and marking the updated linkages in the index for the backends to adjust.

[tejohnson]

In D18945#396618, @tejohnson wrote:

Note you can still do this from libLTO where you are calling ComputeCrossModuleImport and renameModuleForThinLTO directly (a single time per link).

(the once per link is obviously meant for the former, not the per-module renameModuleForThinLTO...)

[mehdi_amini]

I suspect the most efficient implementation for a distributed is that the ThinLink would provide for each file:

• the list of imports (module id + list of functions)
• the list of export

This is exactly what you need to send to the backend, not the index itself.

[tejohnson]

In D18945#396620, @joker.eph wrote:

I suspect the most efficient implementation for a distributed is that the ThinLink would provide for each file:

• the list of imports (module id + list of functions)
• the list of export

This is exactly what you need to send to the backend, not the index itself.

In some ways, but I'd like to enable more flexibility in the backends (locals have to be handled suitably conservatively if we promote based on the link time decisions).

If we eventually decide to go that route, passing this info from the link step to the backends requires additional/new plumbing (maybe write out a subset of the index with just the desired imports, e.g.). In that case, the invocation of ComputeCrossModuleImportForModule here goes away completely in that model, and I don't see a need to compute the lists for all modules redundantly until then.

lib/Transforms/IPO/FunctionImport.cpp

313 ↗

(On Diff #53183)

Meaning refactor this out into a ModuleSummaryIndex method as you did with the version of this loop from ComputeCrossModuleImport()? Sure, I can do that. Note this version is different than the one from ComputeCrossModuleImport (which D18908 pulls out into collectDefinedFunctionsPerModule) in that it is looking for a specific module path, and is only building a std::map, not StringMap<std::map>.

[tejohnson]

Refactor function info map build into collectDefinedFunctionsForModule
method on the ModuleSummaryIndex, similar to the refactoring done in
D18908 for the full-index case.

To give an idea of the impact of this change: I have a large application
containing 13719 source modules, and a 114M module summary index with
2283915 function summaries and 1166281 globalvar init summaries.
For a single source module's ThinLTO distributed backend compile step,
the Function Importing pass time before this change was 46.7s, and after
this change was only 0.3s. And that ~46s cost was being paid by all
13719 source modules!

[mehdi_amini]

LGTM.

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

public:
   }
 
   /// Remove entries in the GlobalValueMap that have empty summaries due to the
   /// eager nature of map entry creation during VST parsing. These would
   /// also be suppressed during combined index generation in mergeFrom(),
   /// but if there was only one module or this was the first module we might
   /// not invoke mergeFrom.
   void removeEmptySummaryEntries();
+
+  /// Collect for the given module the list of function it defines
+  /// (GUID -> Summary).
+  void collectDefinedFunctionsForModule(
+      StringRef ModulePath,
+      std::map<GlobalValue::GUID, FunctionSummary *> &FunctionInfoMap) const;
 };
 
 } // End llvm namespace
 
 #endif

llvm/trunk/include/llvm/Transforms/IPO/FunctionImport.h

 ///
 /// \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::ExportSetTy> &ExportLists);
+
+/// Compute all the imports for the given module using the Index.
+///
+/// \p ImportList will be populated with a map that can be passed to
+/// FunctionImporter::importFunctions() above (see description there).
+void ComputeCrossModuleImportForModule(
+    StringRef ModulePath, const ModuleSummaryIndex &Index,
+    FunctionImporter::ImportMapTy &ImportList);
 }
 
 #endif // LLVM_FUNCTIONIMPORT_H

llvm/trunk/lib/IR/ModuleSummaryIndex.cpp

for (auto MI = begin(), MIE = end(); MI != MIE;) {
     assert(MI->second.size() == 1);
     if (!MI->second[0]->summary())
       MI = GlobalValueMap.erase(MI);
     else
       ++MI;
   }
 }
 
+// Collect for the given module the list of function it defines
+// (GUID -> Summary).
+void ModuleSummaryIndex::collectDefinedFunctionsForModule(
+    StringRef ModulePath,
+    std::map<GlobalValue::GUID, FunctionSummary *> &FunctionInfoMap) const {
+  for (auto &GlobalList : *this) {
+    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;
+      // Ignore summaries from other modules.
+      if (Summary->modulePath() != ModulePath)
+        continue;
+      FunctionInfoMap[GUID] = Summary;
+    }
+  }
+}
+
 GlobalValueInfo *
 ModuleSummaryIndex::getGlobalValueInfo(uint64_t ValueGUID,
                                        bool PerModuleIndex) const {
   auto InfoList = findGlobalValueInfoList(ValueGUID);
   assert(InfoList != end() && "GlobalValue not found in index");
   assert((!PerModuleIndex || InfoList->second.size() == 1) &&
          "Expected a single entry per global value in per-module index");
   auto &Info = InfoList->second[0];
   return Info.get();
 }

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

 /// 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,
     unsigned Threshold,
     const std::map<GlobalValue::GUID, FunctionSummary *> &DefinedFunctions,
     SmallVectorImpl<EdgeInfo> &Worklist,
     FunctionImporter::ImportMapTy &ImportsForModule,
-    StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
+    StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
   for (auto &Edge : Summary.calls()) {
     auto GUID = Edge.first.getGUID();
     DEBUG(dbgs() << " edge -> " << GUID << " Threshold:" << Threshold << "\n");
 
     if (DefinedFunctions.count(GUID)) {
       DEBUG(dbgs() << "ignored! Target already in destination module.\n");
       continue;
     }
if (ProcessedThreshold && ProcessedThreshold > Threshold) {
                    << ProcessedThreshold << "\n");
       continue;
     }
     // Mark this function as imported in this module, with the current Threshold
     ProcessedThreshold = Threshold;
 
     // Make exports in the source module.
     auto ExportModulePath = CalleeSummary->modulePath();
-    auto ExportList = ExportLists[ExportModulePath];
+    if (ExportLists) {
+      auto ExportList = (*ExportLists)[ExportModulePath];
       ExportList.insert(GUID);
-    // Mark all functions and globals referenced by this function as exported to
-    // the outside if they are defined in the same source module.
+      // Mark all functions and globals referenced by this function as exported
+      // to the outside if they are defined in the same source module.
       for (auto &Edge : CalleeSummary->calls()) {
         auto CalleeGUID = Edge.first.getGUID();
         if (isGlobalExported(Index, ExportModulePath, CalleeGUID))
           ExportList.insert(CalleeGUID);
       }
       for (auto &Ref : CalleeSummary->refs()) {
         auto GUID = Ref.getGUID();
         if (isGlobalExported(Index, ExportModulePath, GUID))
           ExportList.insert(GUID);
       }
+    }
 
     // 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(
     const std::map<GlobalValue::GUID, FunctionSummary *> &DefinedFunctions,
     const ModuleSummaryIndex &Index,
     FunctionImporter::ImportMapTy &ImportsForModule,
-    StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
+    StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
   // 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;
while (!Worklist.empty()) {
 
     computeImportForFunction(*Summary, Index, Threshold, DefinedFunctions,
                              Worklist, ImportsForModule, ExportLists);
   }
 }
 
 } // anonymous namespace
 
-/// Compute all the import and export for every module in the Index.
+/// Compute all the import and export for every module using the Index.
 void llvm::ComputeCrossModuleImport(
     const ModuleSummaryIndex &Index,
     StringMap<FunctionImporter::ImportMapTy> &ImportLists,
     StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
   auto ModuleCount = Index.modulePaths().size();
 
   // Collect for each module the list of function it defines.
   // GUID -> Summary
void llvm::ComputeCrossModuleImport(
   }
 
   // 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.second, Index, ImportsForModule,
-                           ExportLists);
+                           &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
 }
 
+/// Compute all the imports for the given module in the Index.
+void llvm::ComputeCrossModuleImportForModule(
+    StringRef ModulePath, const ModuleSummaryIndex &Index,
+    FunctionImporter::ImportMapTy &ImportList) {
+
+  // Collect the list of functions this module defines.
+  // GUID -> Summary
+  std::map<GlobalValue::GUID, FunctionSummary *> FunctionInfoMap;
+  Index.collectDefinedFunctionsForModule(ModulePath, FunctionInfoMap);
+
+  // Compute the import list for this module.
+  DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n");
+  ComputeImportForModule(FunctionInfoMap, Index, ImportList);
+
+#ifndef NDEBUG
+  DEBUG(dbgs() << "* Module " << ModulePath << " imports from "
+               << ImportList.size() << " modules.\n");
+  for (auto &Src : ImportList) {
+    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.
 //
 bool FunctionImporter::importFunctions(
     Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) {
   DEBUG(dbgs() << "Starting import for Module "
                << DestModule.getModuleIdentifier() << "\n");
   unsigned ImportedCount = 0;
if (!SummaryFile.empty()) {
       if (!IndexPtr) {
         errs() << "Error loading file '" << SummaryFile << "': " << Error
                << "\n";
         return false;
       }
       Index = IndexPtr.get();
     }
 
-    // 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<FunctionImporter::ImportMapTy> ImportLists;
-    StringMap<FunctionImporter::ExportSetTy> ExportLists;
-    ComputeCrossModuleImport(*Index, ImportLists, ExportLists);
-    auto &ImportList = ImportLists[M.getModuleIdentifier()];
+    // First step is collecting the import list.
+    FunctionImporter::ImportMapTy ImportList;
+    ComputeCrossModuleImportForModule(M.getModuleIdentifier(), *Index,
+                                      ImportList);
 
     // 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)) {
       errs() << "Error renaming module\n";
       return false;
     }