Index: lib/Transforms/IPO/FunctionImport.cpp =================================================================== --- lib/Transforms/IPO/FunctionImport.cpp +++ lib/Transforms/IPO/FunctionImport.cpp @@ -37,6 +37,13 @@ "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 + ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7), + cl::Hidden, cl::value_desc("x"), + cl::desc("As we import functions, multiply the " + "`import-instr-limit` threshold by this factor " + "before processing newly imported functions")); + // Load lazily a module from \p FileName in \p Context. static std::unique_ptr loadFile(const std::string &FileName, LLVMContext &Context) { @@ -56,6 +63,14 @@ } 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>; + /// Helper to load on demand a Module from file and cache it for subsequent /// queries. It can be used with the FunctionImporter. class ModuleLazyLoaderCache { @@ -93,12 +108,12 @@ } // anonymous namespace /// Walk through the instructions in \p F looking for external -/// calls not already in the \p CalledFunctions set. If any are +/// 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 FunctionInfoIndex &Index, - StringSet<> &CalledFunctions, - SmallVector &Worklist) { +static void findExternalCalls( + const Module &DestModule, Function &F, const FunctionInfoIndex &Index, + VisitedFunctionTrackerTy &VisitedFunctions, unsigned Threshold, + SmallVectorImpl> &Worklist) { // We need to suffix internal function calls imported from other modules, // prepare the suffix ahead of time. std::string Suffix; @@ -130,10 +145,18 @@ auto CalledFunctionGlobalID = Function::getGlobalIdentifier( CalledFunction->getName(), CalledFunction->getLinkage(), CalledFunction->getParent()->getSourceFileName()); - auto It = CalledFunctions.insert(CalledFunctionGlobalID); + + 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, skip. - continue; + // 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); @@ -148,7 +171,7 @@ } } - Worklist.push_back(It.first->getKey()); + Worklist.push_back(std::make_pair(It.first->getKey(), Threshold)); DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Adding callee for : " << ImportedName << " : " << F.getName() << "\n"); @@ -165,17 +188,21 @@ // // \p ModuleToFunctionsToImportMap is filled with the set of Function to import // per Module. -static void GetImportList(Module &DestModule, - SmallVector &Worklist, - StringSet<> &CalledFunctions, - std::map> - &ModuleToFunctionsToImportMap, - const FunctionInfoIndex &Index, - ModuleLazyLoaderCache &ModuleLoaderCache) { +static void +GetImportList(Module &DestModule, + SmallVectorImpl> &Worklist, + VisitedFunctionTrackerTy &VisitedFunctions, + std::map> & + ModuleToFunctionsToImportMap, + const FunctionInfoIndex &Index, + ModuleLazyLoaderCache &ModuleLoaderCache) { while (!Worklist.empty()) { - auto CalledFunctionName = Worklist.pop_back_val(); + StringRef CalledFunctionName; + unsigned Threshold; + std::tie(CalledFunctionName, Threshold) = Worklist.pop_back_val(); DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Process import for " - << CalledFunctionName << "\n"); + << CalledFunctionName << " with Threshold " << Threshold + << "\n"); // Try to get a summary for this function call. auto InfoList = Index.findFunctionInfoList(CalledFunctionName); @@ -199,13 +226,17 @@ llvm_unreachable("Missing summary"); } - if (Summary->instCount() > ImportInstrLimit) { + if (Summary->instCount() > Threshold) { DEBUG(dbgs() << DestModule.getModuleIdentifier() << ": Skip import of " << CalledFunctionName << " with " << Summary->instCount() - << " instructions (limit " << ImportInstrLimit << ")\n"); + << " instructions (limit " << Threshold << ")\n"); continue; } + // 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 " @@ -256,8 +287,11 @@ 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, CalledFunctions, Worklist); + findExternalCalls(DestModule, *F, Index, VisitedFunctions, Threshold, + Worklist); } } @@ -271,13 +305,15 @@ << DestModule.getModuleIdentifier() << "\n"); unsigned ImportedCount = 0; - /// First step is collecting the called external functions. - StringSet<> CalledFunctions; - SmallVector Worklist; + // 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, 64> Worklist; for (auto &F : DestModule) { if (F.isDeclaration() || F.hasFnAttribute(Attribute::OptimizeNone)) continue; - findExternalCalls(DestModule, F, Index, CalledFunctions, Worklist); + findExternalCalls(DestModule, F, Index, VisitedFunctions, ImportInstrLimit, + Worklist); } if (Worklist.empty()) return false; @@ -294,7 +330,7 @@ // Analyze the summaries and get the list of functions to import by // populating ModuleToFunctionsToImportMap ModuleLazyLoaderCache ModuleLoaderCache(ModuleLoader); - GetImportList(DestModule, Worklist, CalledFunctions, + GetImportList(DestModule, Worklist, VisitedFunctions, ModuleToFunctionsToImportMap, Index, ModuleLoaderCache); assert(Worklist.empty() && "Worklist hasn't been flushed in GetImportList"); Index: test/Transforms/FunctionImport/Inputs/adjustable_threshold.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionImport/Inputs/adjustable_threshold.ll @@ -0,0 +1,37 @@ +define void @globalfunc1() { +entry: + call void @trampoline() + ret void +} +; Adds an artificial level in the call graph to reduce the importing threshold +define void @trampoline() { +entry: + call void @largefunction() + ret void +} + +define void @globalfunc2() { +entry: + call void @largefunction() + ret void +} + + +; Size is 5: if two layers below in the call graph the threshold will be 4, +; but if only one layer below the threshold will be 7. +define void @largefunction() { + entry: + call void @staticfunc2() + call void @staticfunc2() + call void @staticfunc2() + call void @staticfunc2() + call void @staticfunc2() + ret void +} + +define internal void @staticfunc2() { +entry: + ret void +} + + Index: test/Transforms/FunctionImport/adjustable_threshold.ll =================================================================== --- /dev/null +++ test/Transforms/FunctionImport/adjustable_threshold.ll @@ -0,0 +1,31 @@ +; Do setup work for all below tests: generate bitcode and combined index +; RUN: llvm-as -function-summary %s -o %t.bc +; RUN: llvm-as -function-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 +; 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 +; INSTLIM-PROGRESSIVE-NOT: call void @staticfunc + + + +declare void @globalfunc1() +declare void @globalfunc2() + +define void @entry() { +entry: +; Call site are processed in reversed order! + +; On the direct call, we reconsider @largefunction with a higher threshold and +; import it + call void @globalfunc2() +; When importing globalfunc1, the threshold was limited and @largefunction was +; not imported. + call void @globalfunc1() + ret void +} +