[ThinLTO] Add option for printing import failure reasons

[tejohnson]

Summary

Adds the option for the printing of summary information about functions
considered but rejected for importing during the thin link.

[tejohnson]

Remove extraneous commented line.

[davidxl]

include/llvm/Transforms/IPO/FunctionImport.h

44

Add some comments on the reasons that are not obvious e.g, GlobalVar.

56

Add a comment on MaxHotness.

[tejohnson]

include/llvm/Transforms/IPO/FunctionImport.h

44

Went ahead and documented all.

56

Went ahead and documented all.

[tejohnson]

Address comments

[davidxl]

lgtm

include/llvm/IR/ModuleSummaryIndex.h

void updateRelBlockFreq(uint64_t BlockFreq, uint64_t EntryFreq) {
 
     uint64_t Sum =
         SaturatingAdd<uint64_t>(Temp.toInt<uint64_t>(), RelBlockFreq);
     Sum = std::min(Sum, uint64_t(MaxRelBlockFreq));
     RelBlockFreq = static_cast<uint32_t>(Sum);
   }
 };
 
+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<std::unique_ptr<GlobalValueSummary>>;
 
 struct GlobalValueSummaryInfo {
   union NameOrGV {
     NameOrGV(bool HaveGVs) {
       if (HaveGVs)

include/llvm/Transforms/IPO/FunctionImport.h

 /// The function importer is automatically importing function from other modules
 /// 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>;
 
+  /// 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<GlobalValue::GUID,
-               std::pair<unsigned, const GlobalValueSummary *>>;
+               std::tuple<unsigned, const GlobalValueSummary *,
+                          std::unique_ptr<ImportFailureInfo>>>;
 
   /// 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
   /// functions to import.
   using ImportMapTy = StringMap<FunctionsToImportTy>;
 
   /// The set contains an entry for every global value the module exports.
   using ExportSetTy = std::unordered_set<GlobalValue::GUID>;

lib/IR/AsmWriter.cpp

 // not printed, and other linkage types are expected to be printed with
 // a space after the name.
 static std::string getLinkageNameWithSpace(GlobalValue::LinkageTypes LT) {
   if (LT == GlobalValue::ExternalLinkage)
     return "";
   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();
 
   FunctionSummary::FFlags FFlags = FS->fflags();
   if (FFlags.ReadNone | FFlags.ReadOnly | FFlags.NoRecurse |
       FFlags.ReturnDoesNotAlias) {
     Out << ", funcFlags: (";
     Out << "readNone: " << FFlags.ReadNone;

lib/Transforms/IPO/FunctionImport.cpp

 // FIXME: This multiplier was not really tuned up.
 static cl::opt<float> ImportColdMultiplier(
     "import-cold-multiplier", cl::init(0), cl::Hidden, cl::value_desc("N"),
     cl::desc("Multiply the `import-instr-limit` threshold for cold callsites"));
 
 static cl::opt<bool> PrintImports("print-imports", cl::init(false), cl::Hidden,
                                   cl::desc("Print imported functions"));
 
+static cl::opt<bool> PrintImportFailures(
+    "print-import-failures", cl::init(false), cl::Hidden,
+    cl::desc("Print information for functions rejected for importing"));
+
 static cl::opt<bool> ComputeDead("compute-dead", cl::init(true), cl::Hidden,
                                  cl::desc("Compute dead symbols"));
 
 static cl::opt<bool> EnableImportMetadata(
     "enable-import-metadata", cl::init(
 #if !defined(NDEBUG)
                                   true /*Enabled with asserts.*/
 #else

 /// - 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 GlobalValueSummary *
 selectCallee(const ModuleSummaryIndex &Index,
              ArrayRef<std::unique_ptr<GlobalValueSummary>> 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<GlobalValueSummary> &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
         // comment there).
         // The mapping from OriginalId to GUID may return a GUID
         // that corresponds to a static variable. Filter it out here.
         // This can happen when
         // 1) There is a call to a library function which is not defined
         // in the index.
         // 2) There is a static variable with the  OriginalGUID identical
         // to the GUID of the library function in 1);
         // 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<FunctionSummary>(GVSummary->getBaseObject());
 
         // If this is a local function, make sure we import the copy
         // in the caller's module. The only time a local function can
         // share an entry in the index is if there is a local with the same name
         // in another module that had the same source file name (in a different
         // directory), where each was compiled in their own directory so there
         // was not distinguishing path.
         // However, do the import from another module if there is only one
         // entry in the list - in that case this must be a reference due
         // to indirect call profile data, since a function pointer can point to
         // 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;
       });
   if (It == CalleeSummaryList.end())
     return nullptr;
 
   return cast<GlobalValueSummary>(It->get());
 }
for (auto &RefSummary : VI.getSummaryList())
         ImportList[RefSummary->modulePath()].insert(VI.getGUID());
         if (ExportLists)
           (*ExportLists)[RefSummary->modulePath()].insert(VI.getGUID());
         break;
       }
   }
 }
 
+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.
 static void computeImportForFunction(
     const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
     const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
     SmallVectorImpl<EdgeInfo> &Worklist,
     FunctionImporter::ImportMapTy &ImportList,
auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
       if (Hotness == CalleeInfo::HotnessType::Critical)
         return ImportCriticalMultiplier;
       return 1.0;
     };
 
     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) {
       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");
+        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<FunctionImporter::ImportFailureInfo>(
+              VI, Edge.second.getHotness(), Reason, 1);
+        }
         LLVM_DEBUG(
             dbgs() << "ignored! No qualifying callee with summary found.\n");
         continue;
       }
 
       // "Resolve" the summary
       CalleeSummary = CalleeSummary->getBaseObject();
       ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
static void computeImportForFunction(
   }
 }
 
 /// 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 GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index,
-    FunctionImporter::ImportMapTy &ImportList,
+    StringRef ModName, FunctionImporter::ImportMapTy &ImportList,
     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;
   FunctionImporter::ImportThresholdsTy ImportThresholds;
 
   // Populate the worklist with the import for the functions in the current
   // module
while (!Worklist.empty()) {
     auto FuncInfo = Worklist.pop_back_val();
     auto *Summary = std::get<0>(FuncInfo);
     auto Threshold = std::get<1>(FuncInfo);
 
     computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries,
                              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<FunctionSummary>(
+            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
 static bool isGlobalVarSummary(const ModuleSummaryIndex &Index,
                                GlobalValue::GUID G) {
   if (const auto &VI = Index.getValueInfo(G)) {
     auto SL = VI.getSummaryList();
     if (!SL.empty())
void llvm::ComputeCrossModuleImport(
     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
     StringMap<FunctionImporter::ImportMapTy> &ImportLists,
     StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
   // For each module that has function defined, compute the import/export lists.
   for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
     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);
   }
 
   // When computing imports we added all GUIDs referenced by anything
   // imported from the module to its ExportList. Now we prune each ExportList
   // of any not defined in that module. This is more efficient than checking
   // while computing imports because some of the summary lists may be long
   // due to linkonce (comdat) copies.
void llvm::ComputeCrossModuleImportForModule(
     FunctionImporter::ImportMapTy &ImportList) {
   // Collect the list of functions this module defines.
   // GUID -> Summary
   GVSummaryMapTy FunctionSummaryMap;
   Index.collectDefinedFunctionsForModule(ModulePath, FunctionSummaryMap);
 
   // 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);
 #endif
 }
 
 // Mark all external summaries in Index for import into the given module.
 // Used for distributed builds using a distributed index.

test/ThinLTO/X86/funcimport2.ll

 ; Do setup work for all below tests: generate bitcode and combined index
 ; RUN: opt -module-summary %s -o %t1.bc
 ; RUN: opt -module-summary %p/Inputs/funcimport2.ll -o %t2.bc
 
 ; 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
 ; RUN: llvm-lto2 run %t1.bc %t2.bc -o %t.o -save-temps \
 ; RUN:     -O0 \
 ; 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"
 
 define void @foo() #0 {
 entry:
   ret void
 }