Index: llvm/trunk/include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- llvm/trunk/include/llvm/IR/ModuleSummaryIndex.h +++ llvm/trunk/include/llvm/IR/ModuleSummaryIndex.h @@ -99,6 +99,22 @@ } }; +inline const char *getHotnessName(CalleeInfo::HotnessType HT) { + switch (HT) { + case CalleeInfo::HotnessType::Unknown: + return "unknown"; + case CalleeInfo::HotnessType::Cold: + return "cold"; + case CalleeInfo::HotnessType::None: + return "none"; + case CalleeInfo::HotnessType::Hot: + return "hot"; + case CalleeInfo::HotnessType::Critical: + return "critical"; + } + llvm_unreachable("invalid hotness"); +} + class GlobalValueSummary; using GlobalValueSummaryList = std::vector>; Index: llvm/trunk/include/llvm/Transforms/IPO/FunctionImport.h =================================================================== --- llvm/trunk/include/llvm/Transforms/IPO/FunctionImport.h +++ llvm/trunk/include/llvm/Transforms/IPO/FunctionImport.h @@ -37,13 +37,57 @@ /// containing all the GUIDs of all functions to import for a source module. using FunctionsToImportTy = std::unordered_set; + /// The different reasons selectCallee will chose not to import a + /// candidate. + enum ImportFailureReason { + None, + // We can encounter a global variable instead of a function in rare + // situations with SamplePGO. See comments where this failure type is + // set for more details. + GlobalVar, + // Found to be globally dead, so we don't bother importing. + NotLive, + // Instruction count over the current threshold. + TooLarge, + // Don't import something with interposable linkage as we can't inline it + // anyway. + InterposableLinkage, + // Generally we won't end up failing due to this reason, as we expect + // to find at least one summary for the GUID that is global or a local + // in the referenced module for direct calls. + LocalLinkageNotInModule, + // This corresponse to the NotEligibleToImport being set on the summary, + // which can happen in a few different cases (e.g. local that can't be + // renamed or promoted because it is referenced on a llvm*.used variable). + NotEligible + }; + + /// Information optionally tracked for candidates the importer decided + /// not to import. Used for optional stat printing. + struct ImportFailureInfo { + // The ValueInfo corresponding to the candidate. We save an index hash + // table lookup for each GUID by stashing this here. + ValueInfo VI; + // The maximum call edge hotness for all failed imports of this candidate. + CalleeInfo::HotnessType MaxHotness; + // most recent reason for failing to import (doesn't necessarily correspond + // to the attempt with the maximum hotness). + ImportFailureReason Reason; + // The number of times we tried to import candidate but failed. + unsigned Attempts; + ImportFailureInfo(ValueInfo VI, CalleeInfo::HotnessType MaxHotness, + ImportFailureReason Reason, unsigned Attempts) + : VI(VI), MaxHotness(MaxHotness), Reason(Reason), Attempts(Attempts) {} + }; + /// 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>; + std::tuple>>; /// 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 Index: llvm/trunk/lib/IR/AsmWriter.cpp =================================================================== --- llvm/trunk/lib/IR/AsmWriter.cpp +++ llvm/trunk/lib/IR/AsmWriter.cpp @@ -2850,22 +2850,6 @@ return getLinkageName(LT) + " "; } -static const char *getHotnessName(CalleeInfo::HotnessType HT) { - switch (HT) { - case CalleeInfo::HotnessType::Unknown: - return "unknown"; - case CalleeInfo::HotnessType::Cold: - return "cold"; - case CalleeInfo::HotnessType::None: - return "none"; - case CalleeInfo::HotnessType::Hot: - return "hot"; - case CalleeInfo::HotnessType::Critical: - return "critical"; - } - llvm_unreachable("invalid hotness"); -} - void AssemblyWriter::printFunctionSummary(const FunctionSummary *FS) { Out << ", insts: " << FS->instCount(); Index: llvm/trunk/lib/Transforms/IPO/FunctionImport.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/FunctionImport.cpp +++ llvm/trunk/lib/Transforms/IPO/FunctionImport.cpp @@ -107,6 +107,10 @@ static cl::opt PrintImports("print-imports", cl::init(false), cl::Hidden, cl::desc("Print imported functions")); +static cl::opt PrintImportFailures( + "print-import-failures", cl::init(false), cl::Hidden, + cl::desc("Print information for functions rejected for importing")); + static cl::opt ComputeDead("compute-dead", cl::init(true), cl::Hidden, cl::desc("Compute dead symbols")); @@ -163,13 +167,18 @@ static const GlobalValueSummary * selectCallee(const ModuleSummaryIndex &Index, ArrayRef> CalleeSummaryList, - unsigned Threshold, StringRef CallerModulePath) { + unsigned Threshold, StringRef CallerModulePath, + FunctionImporter::ImportFailureReason &Reason, + GlobalValue::GUID GUID) { + Reason = FunctionImporter::ImportFailureReason::None; auto It = llvm::find_if( CalleeSummaryList, [&](const std::unique_ptr &SummaryPtr) { auto *GVSummary = SummaryPtr.get(); - if (!Index.isGlobalValueLive(GVSummary)) + if (!Index.isGlobalValueLive(GVSummary)) { + Reason = FunctionImporter::ImportFailureReason::NotLive; return false; + } // For SamplePGO, in computeImportForFunction the OriginalId // may have been used to locate the callee summary list (See @@ -184,11 +193,15 @@ // When this happens, the logic for SamplePGO kicks in and // the static variable in 2) will be found, which needs to be // filtered out. - if (GVSummary->getSummaryKind() == GlobalValueSummary::GlobalVarKind) + if (GVSummary->getSummaryKind() == GlobalValueSummary::GlobalVarKind) { + Reason = FunctionImporter::ImportFailureReason::GlobalVar; return false; - if (GlobalValue::isInterposableLinkage(GVSummary->linkage())) + } + if (GlobalValue::isInterposableLinkage(GVSummary->linkage())) { + Reason = FunctionImporter::ImportFailureReason::InterposableLinkage; // There is no point in importing these, we can't inline them return false; + } auto *Summary = cast(GVSummary->getBaseObject()); @@ -204,14 +217,21 @@ // a local in another module. if (GlobalValue::isLocalLinkage(Summary->linkage()) && CalleeSummaryList.size() > 1 && - Summary->modulePath() != CallerModulePath) + Summary->modulePath() != CallerModulePath) { + Reason = + FunctionImporter::ImportFailureReason::LocalLinkageNotInModule; return false; + } - if (Summary->instCount() > Threshold) + if (Summary->instCount() > Threshold) { + Reason = FunctionImporter::ImportFailureReason::TooLarge; return false; + } - if (Summary->notEligibleToImport()) + if (Summary->notEligibleToImport()) { + Reason = FunctionImporter::ImportFailureReason::NotEligible; return false; + } return true; }); @@ -270,6 +290,27 @@ } } +static const char * +getFailureName(FunctionImporter::ImportFailureReason Reason) { + switch (Reason) { + case FunctionImporter::ImportFailureReason::None: + return "None"; + case FunctionImporter::ImportFailureReason::GlobalVar: + return "GlobalVar"; + case FunctionImporter::ImportFailureReason::NotLive: + return "NotLive"; + case FunctionImporter::ImportFailureReason::TooLarge: + return "TooLarge"; + case FunctionImporter::ImportFailureReason::InterposableLinkage: + return "InterposableLinkage"; + case FunctionImporter::ImportFailureReason::LocalLinkageNotInModule: + return "LocalLinkageNotInModule"; + case FunctionImporter::ImportFailureReason::NotEligible: + return "NotEligible"; + } + llvm_unreachable("invalid reason"); +} + /// 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. @@ -316,11 +357,12 @@ const auto NewThreshold = Threshold * GetBonusMultiplier(Edge.second.getHotness()); - auto IT = ImportThresholds.insert( - std::make_pair(VI.getGUID(), std::make_pair(NewThreshold, nullptr))); + auto IT = ImportThresholds.insert(std::make_pair( + VI.getGUID(), std::make_tuple(NewThreshold, nullptr, nullptr))); bool PreviouslyVisited = !IT.second; - auto &ProcessedThreshold = IT.first->second.first; - auto &CalleeSummary = IT.first->second.second; + auto &ProcessedThreshold = std::get<0>(IT.first->second); + auto &CalleeSummary = std::get<1>(IT.first->second); + auto &FailureInfo = std::get<2>(IT.first->second); const FunctionSummary *ResolvedCalleeSummary = nullptr; if (CalleeSummary) { @@ -345,16 +387,37 @@ LLVM_DEBUG( dbgs() << "ignored! Target was already rejected with Threshold " << ProcessedThreshold << "\n"); + if (PrintImportFailures) { + assert(FailureInfo && + "Expected FailureInfo for previously rejected candidate"); + FailureInfo->Attempts++; + } continue; } + FunctionImporter::ImportFailureReason Reason; CalleeSummary = selectCallee(Index, VI.getSummaryList(), NewThreshold, - Summary.modulePath()); + Summary.modulePath(), Reason, VI.getGUID()); if (!CalleeSummary) { // Update with new larger threshold if this was a retry (otherwise - // we would have already inserted with NewThreshold above). - if (PreviouslyVisited) + // we would have already inserted with NewThreshold above). Also + // update failure info if requested. + if (PreviouslyVisited) { ProcessedThreshold = NewThreshold; + if (PrintImportFailures) { + assert(FailureInfo && + "Expected FailureInfo for previously rejected candidate"); + FailureInfo->Reason = Reason; + FailureInfo->Attempts++; + FailureInfo->MaxHotness = + std::max(FailureInfo->MaxHotness, Edge.second.getHotness()); + } + } else if (PrintImportFailures) { + assert(!FailureInfo && + "Expected no FailureInfo for newly rejected candidate"); + FailureInfo = llvm::make_unique( + VI, Edge.second.getHotness(), Reason, 1); + } LLVM_DEBUG( dbgs() << "ignored! No qualifying callee with summary found.\n"); continue; @@ -421,7 +484,7 @@ /// another module (that may require promotion). static void ComputeImportForModule( const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index, - FunctionImporter::ImportMapTy &ImportList, + StringRef ModName, FunctionImporter::ImportMapTy &ImportList, StringMap *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. @@ -461,6 +524,30 @@ Worklist, ImportList, ExportLists, ImportThresholds); } + + // Print stats about functions considered but rejected for importing + // when requested. + if (PrintImportFailures) { + dbgs() << "Missed imports into module " << ModName << "\n"; + for (auto &I : ImportThresholds) { + auto &ProcessedThreshold = std::get<0>(I.second); + auto &CalleeSummary = std::get<1>(I.second); + auto &FailureInfo = std::get<2>(I.second); + if (CalleeSummary) + continue; // We are going to import. + assert(FailureInfo); + FunctionSummary *FS = nullptr; + if (!FailureInfo->VI.getSummaryList().empty()) + FS = dyn_cast( + FailureInfo->VI.getSummaryList()[0]->getBaseObject()); + dbgs() << FailureInfo->VI + << ": Reason = " << getFailureName(FailureInfo->Reason) + << ", Threshold = " << ProcessedThreshold + << ", Size = " << (FS ? (int)FS->instCount() : -1) + << ", MaxHotness = " << getHotnessName(FailureInfo->MaxHotness) + << ", Attempts = " << FailureInfo->Attempts << "\n"; + } + } } #ifndef NDEBUG @@ -498,7 +585,8 @@ auto &ImportList = ImportLists[DefinedGVSummaries.first()]; LLVM_DEBUG(dbgs() << "Computing import for Module '" << DefinedGVSummaries.first() << "'\n"); - ComputeImportForModule(DefinedGVSummaries.second, Index, ImportList, + ComputeImportForModule(DefinedGVSummaries.second, Index, + DefinedGVSummaries.first(), ImportList, &ExportLists); } @@ -569,7 +657,7 @@ // Compute the import list for this module. LLVM_DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n"); - ComputeImportForModule(FunctionSummaryMap, Index, ImportList); + ComputeImportForModule(FunctionSummaryMap, Index, ModulePath, ImportList); #ifndef NDEBUG dumpImportListForModule(Index, ModulePath, ImportList); Index: llvm/trunk/test/ThinLTO/X86/funcimport2.ll =================================================================== --- llvm/trunk/test/ThinLTO/X86/funcimport2.ll +++ llvm/trunk/test/ThinLTO/X86/funcimport2.ll @@ -5,9 +5,23 @@ ; RUN: llvm-lto2 run %t1.bc %t2.bc -o %t.o -save-temps \ ; RUN: -r=%t1.bc,_foo,plx \ ; RUN: -r=%t2.bc,_main,plx \ -; RUN: -r=%t2.bc,_foo,l +; RUN: -r=%t2.bc,_foo,l \ +; RUN: -print-import-failures 2>&1 | FileCheck %s --check-prefix=NOFAILURES ; RUN: llvm-dis %t.o.2.3.import.bc -o - | FileCheck %s ; CHECK: define available_externally dso_local void @foo() +; Don't expect any failure messages from -print-import-failures +; NOFAILURES-NOT: Reason = + +; We shouldn't do any importing with a 0 instruction limit, in which case +; -print-import-failures should print a TooLarge reason. +; RUN: llvm-lto2 run %t1.bc %t2.bc -o %t.o -save-temps \ +; RUN: -r=%t1.bc,_foo,plx \ +; RUN: -r=%t2.bc,_main,plx \ +; RUN: -r=%t2.bc,_foo,l \ +; RUN: -import-instr-limit=0 \ +; RUN: -print-import-failures 2>&1 | FileCheck %s --check-prefix=FAILURES +; RUN: llvm-dis %t.o.2.3.import.bc -o - | FileCheck %s --check-prefix=NOIMPORT +; FAILURES: (foo): Reason = TooLarge, Threshold = 0, Size = 1, MaxHotness = unknown, Attempts = 1 ; We shouldn't do any importing at -O0 ; rm -f %t.o.1.3.import.bc @@ -16,8 +30,8 @@ ; RUN: -r=%t1.bc,_foo,plx \ ; RUN: -r=%t2.bc,_main,plx \ ; RUN: -r=%t2.bc,_foo,l -; RUN: llvm-dis %t.o.2.3.import.bc -o - | FileCheck %s --check-prefix=CHECKO0 -; CHECKO0: declare dso_local void @foo(...) +; RUN: llvm-dis %t.o.2.3.import.bc -o - | FileCheck %s --check-prefix=NOIMPORT +; NOIMPORT: declare dso_local void @foo(...) target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-apple-macosx10.11.0"