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

   1 //===- FunctionImport.cpp - ThinLTO Summary-based Function Import ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements Function import based on summaries.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Transforms/IPO/FunctionImport.h"
  15 #include "llvm/ADT/ArrayRef.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/ADT/SetVector.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/ADT/StringMap.h"
  21 #include "llvm/ADT/StringSet.h"
  22 #include "llvm/ADT/StringRef.h"
  23 #include "llvm/Bitcode/BitcodeReader.h"
  24 #include "llvm/IR/AutoUpgrade.h"
  25 #include "llvm/IR/Constants.h"
  26 #include "llvm/IR/Function.h"
  27 #include "llvm/IR/GlobalAlias.h"
  28 #include "llvm/IR/GlobalObject.h"
  29 #include "llvm/IR/GlobalValue.h"
  30 #include "llvm/IR/GlobalVariable.h"
  31 #include "llvm/IR/Metadata.h"
  32 #include "llvm/IR/Module.h"
  33 #include "llvm/IR/ModuleSummaryIndex.h"
  34 #include "llvm/IRReader/IRReader.h"
  35 #include "llvm/Linker/IRMover.h"
  36 #include "llvm/Object/ModuleSymbolTable.h"
  37 #include "llvm/Object/SymbolicFile.h"
  38 #include "llvm/Pass.h"
  39 #include "llvm/Support/Casting.h"
  40 #include "llvm/Support/CommandLine.h"
  41 #include "llvm/Support/Debug.h"
  42 #include "llvm/Support/Error.h"
  43 #include "llvm/Support/ErrorHandling.h"
  44 #include "llvm/Support/FileSystem.h"
  45 #include "llvm/Support/SourceMgr.h"
  46 #include "llvm/Support/raw_ostream.h"
  47 #include "llvm/Transforms/IPO/Internalize.h"
  48 #include "llvm/Transforms/Utils/Cloning.h"
  49 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
  50 #include "llvm/Transforms/Utils/ValueMapper.h"
  51 #include <cassert>
  52 #include <memory>
  53 #include <set>
  54 #include <string>
  55 #include <system_error>
  56 #include <tuple>
  57 #include <utility>
  58
  59 using namespace llvm;
  60
  61 #define DEBUG_TYPE "function-import"
  62
  63 STATISTIC(NumImportedFunctions, "Number of functions imported");
  64 STATISTIC(NumImportedModules, "Number of modules imported from");
  65 STATISTIC(NumDeadSymbols, "Number of dead stripped symbols in index");
  66 STATISTIC(NumLiveSymbols, "Number of live symbols in index");
  67
  68 /// Limit on instruction count of imported functions.
  69 static cl::opt<unsigned> ImportInstrLimit(
  70     "import-instr-limit", cl::init(100), cl::Hidden, cl::value_desc("N"),
  71     cl::desc("Only import functions with less than N instructions"));
  72
  73 static cl::opt<float>
  74     ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7),
  75                       cl::Hidden, cl::value_desc("x"),
  76                       cl::desc("As we import functions, multiply the "
  77                                "`import-instr-limit` threshold by this factor "
  78                                "before processing newly imported functions"));
  79
  80 static cl::opt<float> ImportHotInstrFactor(
  81     "import-hot-evolution-factor", cl::init(1.0), cl::Hidden,
  82     cl::value_desc("x"),
  83     cl::desc("As we import functions called from hot callsite, multiply the "
  84              "`import-instr-limit` threshold by this factor "
  85              "before processing newly imported functions"));
  86
  87 static cl::opt<float> ImportHotMultiplier(
  88     "import-hot-multiplier", cl::init(10.0), cl::Hidden, cl::value_desc("x"),
  89     cl::desc("Multiply the `import-instr-limit` threshold for hot callsites"));
  90
  91 static cl::opt<float> ImportCriticalMultiplier(
  92     "import-critical-multiplier", cl::init(100.0), cl::Hidden,
  93     cl::value_desc("x"),
  94     cl::desc(
  95         "Multiply the `import-instr-limit` threshold for critical callsites"));
  96
  97 // FIXME: This multiplier was not really tuned up.
  98 static cl::opt<float> ImportColdMultiplier(
  99     "import-cold-multiplier", cl::init(0), cl::Hidden, cl::value_desc("N"),
 100     cl::desc("Multiply the `import-instr-limit` threshold for cold callsites"));
 101
 102 static cl::opt<bool> PrintImports("print-imports", cl::init(false), cl::Hidden,
 103                                   cl::desc("Print imported functions"));
 104
 105 static cl::opt<bool> ComputeDead("compute-dead", cl::init(true), cl::Hidden,
 106                                  cl::desc("Compute dead symbols"));
 107
 108 static cl::opt<bool> EnableImportMetadata(
 109     "enable-import-metadata", cl::init(
 110 #if !defined(NDEBUG)
 111                                   true /*Enabled with asserts.*/
 112 #else
 113                                   false
 114 #endif
 115                                   ),
 116     cl::Hidden, cl::desc("Enable import metadata like 'thinlto_src_module'"));
 117
 118 /// Summary file to use for function importing when using -function-import from
 119 /// the command line.
 120 static cl::opt<std::string>
 121     SummaryFile("summary-file",
 122                 cl::desc("The summary file to use for function importing."));
 123
 124 /// Used when testing importing from distributed indexes via opt
 125 // -function-import.
 126 static cl::opt<bool>
 127     ImportAllIndex("import-all-index",
 128                    cl::desc("Import all external functions in index."));
 129
 130 // Load lazily a module from \p FileName in \p Context.
 131 static std::unique_ptr<Module> loadFile(const std::string &FileName,
 132                                         LLVMContext &Context) {
 133   SMDiagnostic Err;
 134   DEBUG(dbgs() << "Loading '" << FileName << "'\n");
 135   // Metadata isn't loaded until functions are imported, to minimize
 136   // the memory overhead.
 137   std::unique_ptr<Module> Result =
 138       getLazyIRFileModule(FileName, Err, Context,
 139                           /* ShouldLazyLoadMetadata = */ true);
 140   if (!Result) {
 141     Err.print("function-import", errs());
 142     report_fatal_error("Abort");
 143   }
 144
 145   return Result;
 146 }
 147
 148 /// Given a list of possible callee implementation for a call site, select one
 149 /// that fits the \p Threshold.
 150 ///
 151 /// FIXME: select "best" instead of first that fits. But what is "best"?
 152 /// - The smallest: more likely to be inlined.
 153 /// - The one with the least outgoing edges (already well optimized).
 154 /// - One from a module already being imported from in order to reduce the
 155 ///   number of source modules parsed/linked.
 156 /// - One that has PGO data attached.
 157 /// - [insert you fancy metric here]
 158 static const GlobalValueSummary *
 159 selectCallee(const ModuleSummaryIndex &Index,
 160              ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
 161              unsigned Threshold, StringRef CallerModulePath) {
 162   auto It = llvm::find_if(
 163       CalleeSummaryList,
 164       [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {
 165         auto *GVSummary = SummaryPtr.get();
 166         // For SamplePGO, in computeImportForFunction the OriginalId
 167         // may have been used to locate the callee summary list (See
 168         // comment there).
 169         // The mapping from OriginalId to GUID may return a GUID
 170         // that corresponds to a static variable. Filter it out here.
 171         // This can happen when
 172         // 1) There is a call to a library function which is not defined
 173         // in the index.
 174         // 2) There is a static variable with the  OriginalGUID identical
 175         // to the GUID of the library function in 1);
 176         // When this happens, the logic for SamplePGO kicks in and
 177         // the static variable in 2) will be found, which needs to be
 178         // filtered out.
 179         if (GVSummary->getSummaryKind() == GlobalValueSummary::GlobalVarKind)
 180           return false;
 181         if (GlobalValue::isInterposableLinkage(GVSummary->linkage()))
 182           // There is no point in importing these, we can't inline them
 183           return false;
 184
 185         auto *Summary = cast<FunctionSummary>(GVSummary->getBaseObject());
 186
 187         // If this is a local function, make sure we import the copy
 188         // in the caller's module. The only time a local function can
 189         // share an entry in the index is if there is a local with the same name
 190         // in another module that had the same source file name (in a different
 191         // directory), where each was compiled in their own directory so there
 192         // was not distinguishing path.
 193         // However, do the import from another module if there is only one
 194         // entry in the list - in that case this must be a reference due
 195         // to indirect call profile data, since a function pointer can point to
 196         // a local in another module.
 197         if (GlobalValue::isLocalLinkage(Summary->linkage()) &&
 198             CalleeSummaryList.size() > 1 &&
 199             Summary->modulePath() != CallerModulePath)
 200           return false;
 201
 202         if (Summary->instCount() > Threshold)
 203           return false;
 204
 205         if (Summary->notEligibleToImport())
 206           return false;
 207
 208         return true;
 209       });
 210   if (It == CalleeSummaryList.end())
 211     return nullptr;
 212
 213   return cast<GlobalValueSummary>(It->get());
 214 }
 215
 216 namespace {
 217
 218 using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */,
 219                             GlobalValue::GUID>;
 220
 221 } // anonymous namespace
 222
 223 static ValueInfo
 224 updateValueInfoForIndirectCalls(const ModuleSummaryIndex &Index, ValueInfo VI) {
 225   if (!VI.getSummaryList().empty())
 226     return VI;
 227   // For SamplePGO, the indirect call targets for local functions will
 228   // have its original name annotated in profile. We try to find the
 229   // corresponding PGOFuncName as the GUID.
 230   // FIXME: Consider updating the edges in the graph after building
 231   // it, rather than needing to perform this mapping on each walk.
 232   auto GUID = Index.getGUIDFromOriginalID(VI.getGUID());
 233   if (GUID == 0)
 234     return nullptr;
 235   return Index.getValueInfo(GUID);
 236 }
 237
 238 /// Compute the list of functions to import for a given caller. Mark these
 239 /// imported functions and the symbols they reference in their source module as
 240 /// exported from their source module.
 241 static void computeImportForFunction(
 242     const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
 243     const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
 244     SmallVectorImpl<EdgeInfo> &Worklist,
 245     FunctionImporter::ImportMapTy &ImportList,
 246     StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
 247   for (auto &Edge : Summary.calls()) {
 248     ValueInfo VI = Edge.first;
 249     DEBUG(dbgs() << " edge -> " << VI.getGUID() << " Threshold:" << Threshold
 250                  << "\n");
 251
 252     VI = updateValueInfoForIndirectCalls(Index, VI);
 253     if (!VI)
 254       continue;
 255
 256     if (DefinedGVSummaries.count(VI.getGUID())) {
 257       DEBUG(dbgs() << "ignored! Target already in destination module.\n");
 258       continue;
 259     }
 260
 261     auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
 262       if (Hotness == CalleeInfo::HotnessType::Hot)
 263         return ImportHotMultiplier;
 264       if (Hotness == CalleeInfo::HotnessType::Cold)
 265         return ImportColdMultiplier;
 266       if (Hotness == CalleeInfo::HotnessType::Critical)
 267         return ImportCriticalMultiplier;
 268       return 1.0;
 269     };
 270
 271     const auto NewThreshold =
 272         Threshold * GetBonusMultiplier(Edge.second.Hotness);
 273
 274     auto *CalleeSummary = selectCallee(Index, VI.getSummaryList(), NewThreshold,
 275                                        Summary.modulePath());
 276     if (!CalleeSummary) {
 277       DEBUG(dbgs() << "ignored! No qualifying callee with summary found.\n");
 278       continue;
 279     }
 280
 281     // "Resolve" the summary
 282     const auto *ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary->getBaseObject());
 283
 284     assert(ResolvedCalleeSummary->instCount() <= NewThreshold &&
 285            "selectCallee() didn't honor the threshold");
 286
 287     auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
 288       // Adjust the threshold for next level of imported functions.
 289       // The threshold is different for hot callsites because we can then
 290       // inline chains of hot calls.
 291       if (IsHotCallsite)
 292         return Threshold * ImportHotInstrFactor;
 293       return Threshold * ImportInstrFactor;
 294     };
 295
 296     bool IsHotCallsite = Edge.second.Hotness == CalleeInfo::HotnessType::Hot;
 297     const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite);
 298
 299     auto ExportModulePath = ResolvedCalleeSummary->modulePath();
 300     auto &ProcessedThreshold = ImportList[ExportModulePath][VI.getGUID()];
 301     /// Since the traversal of the call graph is DFS, we can revisit a function
 302     /// a second time with a higher threshold. In this case, it is added back to
 303     /// the worklist with the new threshold.
 304     if (ProcessedThreshold && ProcessedThreshold >= AdjThreshold) {
 305       DEBUG(dbgs() << "ignored! Target was already seen with Threshold "
 306                    << ProcessedThreshold << "\n");
 307       continue;
 308     }
 309     bool PreviouslyImported = ProcessedThreshold != 0;
 310     // Mark this function as imported in this module, with the current Threshold
 311     ProcessedThreshold = AdjThreshold;
 312
 313     // Make exports in the source module.
 314     if (ExportLists) {
 315       auto &ExportList = (*ExportLists)[ExportModulePath];
 316       ExportList.insert(VI.getGUID());
 317       if (!PreviouslyImported) {
 318         // This is the first time this function was exported from its source
 319         // module, so mark all functions and globals it references as exported
 320         // to the outside if they are defined in the same source module.
 321         // For efficiency, we unconditionally add all the referenced GUIDs
 322         // to the ExportList for this module, and will prune out any not
 323         // defined in the module later in a single pass.
 324         for (auto &Edge : ResolvedCalleeSummary->calls()) {
 325           auto CalleeGUID = Edge.first.getGUID();
 326           ExportList.insert(CalleeGUID);
 327         }
 328         for (auto &Ref : ResolvedCalleeSummary->refs()) {
 329           auto GUID = Ref.getGUID();
 330           ExportList.insert(GUID);
 331         }
 332       }
 333     }
 334
 335     // Insert the newly imported function to the worklist.
 336     Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, VI.getGUID());
 337   }
 338 }
 339
 340 /// Given the list of globals defined in a module, compute the list of imports
 341 /// as well as the list of "exports", i.e. the list of symbols referenced from
 342 /// another module (that may require promotion).
 343 static void ComputeImportForModule(
 344     const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index,
 345     FunctionImporter::ImportMapTy &ImportList,
 346     StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
 347   // Worklist contains the list of function imported in this module, for which
 348   // we will analyse the callees and may import further down the callgraph.
 349   SmallVector<EdgeInfo, 128> Worklist;
 350
 351   // Populate the worklist with the import for the functions in the current
 352   // module
 353   for (auto &GVSummary : DefinedGVSummaries) {
 354     if (!Index.isGlobalValueLive(GVSummary.second)) {
 355       DEBUG(dbgs() << "Ignores Dead GUID: " << GVSummary.first << "\n");
 356       continue;
 357     }
 358     auto *FuncSummary =
 359         dyn_cast<FunctionSummary>(GVSummary.second->getBaseObject());
 360     if (!FuncSummary)
 361       // Skip import for global variables
 362       continue;
 363     DEBUG(dbgs() << "Initialize import for " << GVSummary.first << "\n");
 364     computeImportForFunction(*FuncSummary, Index, ImportInstrLimit,
 365                              DefinedGVSummaries, Worklist, ImportList,
 366                              ExportLists);
 367   }
 368
 369   // Process the newly imported functions and add callees to the worklist.
 370   while (!Worklist.empty()) {
 371     auto FuncInfo = Worklist.pop_back_val();
 372     auto *Summary = std::get<0>(FuncInfo);
 373     auto Threshold = std::get<1>(FuncInfo);
 374     auto GUID = std::get<2>(FuncInfo);
 375
 376     // Check if we later added this summary with a higher threshold.
 377     // If so, skip this entry.
 378     auto ExportModulePath = Summary->modulePath();
 379     auto &LatestProcessedThreshold = ImportList[ExportModulePath][GUID];
 380     if (LatestProcessedThreshold > Threshold)
 381       continue;
 382
 383     computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries,
 384                              Worklist, ImportList, ExportLists);
 385   }
 386 }
 387
 388 /// Compute all the import and export for every module using the Index.
 389 void llvm::ComputeCrossModuleImport(
 390     const ModuleSummaryIndex &Index,
 391     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
 392     StringMap<FunctionImporter::ImportMapTy> &ImportLists,
 393     StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
 394   // For each module that has function defined, compute the import/export lists.
 395   for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
 396     auto &ImportList = ImportLists[DefinedGVSummaries.first()];
 397     DEBUG(dbgs() << "Computing import for Module '"
 398                  << DefinedGVSummaries.first() << "'\n");
 399     ComputeImportForModule(DefinedGVSummaries.second, Index, ImportList,
 400                            &ExportLists);
 401   }
 402
 403   // When computing imports we added all GUIDs referenced by anything
 404   // imported from the module to its ExportList. Now we prune each ExportList
 405   // of any not defined in that module. This is more efficient than checking
 406   // while computing imports because some of the summary lists may be long
 407   // due to linkonce (comdat) copies.
 408   for (auto &ELI : ExportLists) {
 409     const auto &DefinedGVSummaries =
 410         ModuleToDefinedGVSummaries.lookup(ELI.first());
 411     for (auto EI = ELI.second.begin(); EI != ELI.second.end();) {
 412       if (!DefinedGVSummaries.count(*EI))
 413         EI = ELI.second.erase(EI);
 414       else
 415         ++EI;
 416     }
 417   }
 418
 419 #ifndef NDEBUG
 420   DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size()
 421                << " modules:\n");
 422   for (auto &ModuleImports : ImportLists) {
 423     auto ModName = ModuleImports.first();
 424     auto &Exports = ExportLists[ModName];
 425     DEBUG(dbgs() << "* Module " << ModName << " exports " << Exports.size()
 426                  << " functions. Imports from " << ModuleImports.second.size()
 427                  << " modules.\n");
 428     for (auto &Src : ModuleImports.second) {
 429       auto SrcModName = Src.first();
 430       DEBUG(dbgs() << " - " << Src.second.size() << " functions imported from "
 431                    << SrcModName << "\n");
 432     }
 433   }
 434 #endif
 435 }
 436
 437 #ifndef NDEBUG
 438 static void dumpImportListForModule(StringRef ModulePath,
 439                                     FunctionImporter::ImportMapTy &ImportList) {
 440   DEBUG(dbgs() << "* Module " << ModulePath << " imports from "
 441                << ImportList.size() << " modules.\n");
 442   for (auto &Src : ImportList) {
 443     auto SrcModName = Src.first();
 444     DEBUG(dbgs() << " - " << Src.second.size() << " functions imported from "
 445                  << SrcModName << "\n");
 446   }
 447 }
 448 #endif
 449
 450 /// Compute all the imports for the given module in the Index.
 451 void llvm::ComputeCrossModuleImportForModule(
 452     StringRef ModulePath, const ModuleSummaryIndex &Index,
 453     FunctionImporter::ImportMapTy &ImportList) {
 454   // Collect the list of functions this module defines.
 455   // GUID -> Summary
 456   GVSummaryMapTy FunctionSummaryMap;
 457   Index.collectDefinedFunctionsForModule(ModulePath, FunctionSummaryMap);
 458
 459   // Compute the import list for this module.
 460   DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n");
 461   ComputeImportForModule(FunctionSummaryMap, Index, ImportList);
 462
 463 #ifndef NDEBUG
 464   dumpImportListForModule(ModulePath, ImportList);
 465 #endif
 466 }
 467
 468 // Mark all external summaries in Index for import into the given module.
 469 // Used for distributed builds using a distributed index.
 470 void llvm::ComputeCrossModuleImportForModuleFromIndex(
 471     StringRef ModulePath, const ModuleSummaryIndex &Index,
 472     FunctionImporter::ImportMapTy &ImportList) {
 473   for (auto &GlobalList : Index) {
 474     // Ignore entries for undefined references.
 475     if (GlobalList.second.SummaryList.empty())
 476       continue;
 477
 478     auto GUID = GlobalList.first;
 479     assert(GlobalList.second.SummaryList.size() == 1 &&
 480            "Expected individual combined index to have one summary per GUID");
 481     auto &Summary = GlobalList.second.SummaryList[0];
 482     // Skip the summaries for the importing module. These are included to
 483     // e.g. record required linkage changes.
 484     if (Summary->modulePath() == ModulePath)
 485       continue;
 486     // Doesn't matter what value we plug in to the map, just needs an entry
 487     // to provoke importing by thinBackend.
 488     ImportList[Summary->modulePath()][GUID] = 1;
 489   }
 490 #ifndef NDEBUG
 491   dumpImportListForModule(ModulePath, ImportList);
 492 #endif
 493 }
 494
 495 void llvm::computeDeadSymbols(
 496     ModuleSummaryIndex &Index,
 497     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
 498   assert(!Index.withGlobalValueDeadStripping());
 499   if (!ComputeDead)
 500     return;
 501   if (GUIDPreservedSymbols.empty())
 502     // Don't do anything when nothing is live, this is friendly with tests.
 503     return;
 504   unsigned LiveSymbols = 0;
 505   SmallVector<ValueInfo, 128> Worklist;
 506   Worklist.reserve(GUIDPreservedSymbols.size() * 2);
 507   for (auto GUID : GUIDPreservedSymbols) {
 508     ValueInfo VI = Index.getValueInfo(GUID);
 509     if (!VI)
 510       continue;
 511     for (auto &S : VI.getSummaryList())
 512       S->setLive(true);
 513   }
 514
 515   // Add values flagged in the index as live roots to the worklist.
 516   for (const auto &Entry : Index)
 517     for (auto &S : Entry.second.SummaryList)
 518       if (S->isLive()) {
 519         DEBUG(dbgs() << "Live root: " << Entry.first << "\n");
 520         Worklist.push_back(ValueInfo(&Entry));
 521         ++LiveSymbols;
 522         break;
 523       }
 524
 525   // Make value live and add it to the worklist if it was not live before.
 526   // FIXME: we should only make the prevailing copy live here
 527   auto visit = [&](ValueInfo VI) {
 528     // FIXME: If we knew which edges were created for indirect call profiles,
 529     // we could skip them here. Any that are live should be reached via
 530     // other edges, e.g. reference edges. Otherwise, using a profile collected
 531     // on a slightly different binary might provoke preserving, importing
 532     // and ultimately promoting calls to functions not linked into this
 533     // binary, which increases the binary size unnecessarily. Note that
 534     // if this code changes, the importer needs to change so that edges
 535     // to functions marked dead are skipped.
 536     VI = updateValueInfoForIndirectCalls(Index, VI);
 537     if (!VI)
 538       return;
 539     for (auto &S : VI.getSummaryList())
 540       if (S->isLive())
 541         return;
 542     for (auto &S : VI.getSummaryList())
 543       S->setLive(true);
 544     ++LiveSymbols;
 545     Worklist.push_back(VI);
 546   };
 547
 548   while (!Worklist.empty()) {
 549     auto VI = Worklist.pop_back_val();
 550     for (auto &Summary : VI.getSummaryList()) {
 551       GlobalValueSummary *Base = Summary->getBaseObject();
 552       for (auto Ref : Base->refs())
 553         visit(Ref);
 554       if (auto *FS = dyn_cast<FunctionSummary>(Base))
 555         for (auto Call : FS->calls())
 556           visit(Call.first);
 557     }
 558   }
 559   Index.setWithGlobalValueDeadStripping();
 560
 561   unsigned DeadSymbols = Index.size() - LiveSymbols;
 562   DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols
 563                << " symbols Dead \n");
 564   NumDeadSymbols += DeadSymbols;
 565   NumLiveSymbols += LiveSymbols;
 566 }
 567
 568 /// Compute the set of summaries needed for a ThinLTO backend compilation of
 569 /// \p ModulePath.
 570 void llvm::gatherImportedSummariesForModule(
 571     StringRef ModulePath,
 572     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
 573     const FunctionImporter::ImportMapTy &ImportList,
 574     std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
 575   // Include all summaries from the importing module.
 576   ModuleToSummariesForIndex[ModulePath] =
 577       ModuleToDefinedGVSummaries.lookup(ModulePath);
 578   // Include summaries for imports.
 579   for (auto &ILI : ImportList) {
 580     auto &SummariesForIndex = ModuleToSummariesForIndex[ILI.first()];
 581     const auto &DefinedGVSummaries =
 582         ModuleToDefinedGVSummaries.lookup(ILI.first());
 583     for (auto &GI : ILI.second) {
 584       const auto &DS = DefinedGVSummaries.find(GI.first);
 585       assert(DS != DefinedGVSummaries.end() &&
 586              "Expected a defined summary for imported global value");
 587       SummariesForIndex[GI.first] = DS->second;
 588     }
 589   }
 590 }
 591
 592 /// Emit the files \p ModulePath will import from into \p OutputFilename.
 593 std::error_code
 594 llvm::EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename,
 595                        const FunctionImporter::ImportMapTy &ModuleImports) {
 596   std::error_code EC;
 597   raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::F_None);
 598   if (EC)
 599     return EC;
 600   for (auto &ILI : ModuleImports)
 601     ImportsOS << ILI.first() << "\n";
 602   return std::error_code();
 603 }
 604
 605 /// Fixup WeakForLinker linkages in \p TheModule based on summary analysis.
 606 void llvm::thinLTOResolveWeakForLinkerModule(
 607     Module &TheModule, const GVSummaryMapTy &DefinedGlobals) {
 608   auto ConvertToDeclaration = [](GlobalValue &GV) {
 609     DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName() << "\n");
 610     if (Function *F = dyn_cast<Function>(&GV)) {
 611       F->deleteBody();
 612       F->clearMetadata();
 613     } else if (GlobalVariable *V = dyn_cast<GlobalVariable>(&GV)) {
 614       V->setInitializer(nullptr);
 615       V->setLinkage(GlobalValue::ExternalLinkage);
 616       V->clearMetadata();
 617     } else
 618       // For now we don't resolve or drop aliases. Once we do we'll
 619       // need to add support here for creating either a function or
 620       // variable declaration, and return the new GlobalValue* for
 621       // the caller to use.
 622       llvm_unreachable("Expected function or variable");
 623   };
 624
 625   auto updateLinkage = [&](GlobalValue &GV) {
 626     // See if the global summary analysis computed a new resolved linkage.
 627     const auto &GS = DefinedGlobals.find(GV.getGUID());
 628     if (GS == DefinedGlobals.end())
 629       return;
 630     auto NewLinkage = GS->second->linkage();
 631     if (NewLinkage == GV.getLinkage())
 632       return;
 633
 634     // Switch the linkage to weakany if asked for, e.g. we do this for
 635     // linker redefined symbols (via --wrap or --defsym).
 636     // We record that the visibility should be changed here in `addThinLTO`
 637     // as we need access to the resolution vectors for each input file in
 638     // order to find which symbols have been redefined.
 639     // We may consider reorganizing this code and moving the linkage recording
 640     // somewhere else, e.g. in thinLTOResolveWeakForLinkerInIndex.
 641     if (NewLinkage == GlobalValue::WeakAnyLinkage) {
 642       GV.setLinkage(NewLinkage);
 643       return;
 644     }
 645
 646     if (!GlobalValue::isWeakForLinker(GV.getLinkage()))
 647       return;
 648     // Check for a non-prevailing def that has interposable linkage
 649     // (e.g. non-odr weak or linkonce). In that case we can't simply
 650     // convert to available_externally, since it would lose the
 651     // interposable property and possibly get inlined. Simply drop
 652     // the definition in that case.
 653     if (GlobalValue::isAvailableExternallyLinkage(NewLinkage) &&
 654         GlobalValue::isInterposableLinkage(GV.getLinkage()))
 655       ConvertToDeclaration(GV);
 656     else {
 657       DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName() << "` from "
 658                    << GV.getLinkage() << " to " << NewLinkage << "\n");
 659       GV.setLinkage(NewLinkage);
 660     }
 661     // Remove declarations from comdats, including available_externally
 662     // as this is a declaration for the linker, and will be dropped eventually.
 663     // It is illegal for comdats to contain declarations.
 664     auto *GO = dyn_cast_or_null<GlobalObject>(&GV);
 665     if (GO && GO->isDeclarationForLinker() && GO->hasComdat())
 666       GO->setComdat(nullptr);
 667   };
 668
 669   // Process functions and global now
 670   for (auto &GV : TheModule)
 671     updateLinkage(GV);
 672   for (auto &GV : TheModule.globals())
 673     updateLinkage(GV);
 674   for (auto &GV : TheModule.aliases())
 675     updateLinkage(GV);
 676 }
 677
 678 /// Run internalization on \p TheModule based on symmary analysis.
 679 void llvm::thinLTOInternalizeModule(Module &TheModule,
 680                                     const GVSummaryMapTy &DefinedGlobals) {
 681   // Declare a callback for the internalize pass that will ask for every
 682   // candidate GlobalValue if it can be internalized or not.
 683   auto MustPreserveGV = [&](const GlobalValue &GV) -> bool {
 684     // Lookup the linkage recorded in the summaries during global analysis.
 685     auto GS = DefinedGlobals.find(GV.getGUID());
 686     if (GS == DefinedGlobals.end()) {
 687       // Must have been promoted (possibly conservatively). Find original
 688       // name so that we can access the correct summary and see if it can
 689       // be internalized again.
 690       // FIXME: Eventually we should control promotion instead of promoting
 691       // and internalizing again.
 692       StringRef OrigName =
 693           ModuleSummaryIndex::getOriginalNameBeforePromote(GV.getName());
 694       std::string OrigId = GlobalValue::getGlobalIdentifier(
 695           OrigName, GlobalValue::InternalLinkage,
 696           TheModule.getSourceFileName());
 697       GS = DefinedGlobals.find(GlobalValue::getGUID(OrigId));
 698       if (GS == DefinedGlobals.end()) {
 699         // Also check the original non-promoted non-globalized name. In some
 700         // cases a preempted weak value is linked in as a local copy because
 701         // it is referenced by an alias (IRLinker::linkGlobalValueProto).
 702         // In that case, since it was originally not a local value, it was
 703         // recorded in the index using the original name.
 704         // FIXME: This may not be needed once PR27866 is fixed.
 705         GS = DefinedGlobals.find(GlobalValue::getGUID(OrigName));
 706         assert(GS != DefinedGlobals.end());
 707       }
 708     }
 709     return !GlobalValue::isLocalLinkage(GS->second->linkage());
 710   };
 711
 712   // FIXME: See if we can just internalize directly here via linkage changes
 713   // based on the index, rather than invoking internalizeModule.
 714   internalizeModule(TheModule, MustPreserveGV);
 715 }
 716
 717 /// Make alias a clone of its aliasee.
 718 static Function *replaceAliasWithAliasee(Module *SrcModule, GlobalAlias *GA) {
 719   Function *Fn = cast<Function>(GA->getBaseObject());
 720
 721   ValueToValueMapTy VMap;
 722   Function *NewFn = CloneFunction(Fn, VMap);
 723   // Clone should use the original alias's linkage and name, and we ensure
 724   // all uses of alias instead use the new clone (casted if necessary).
 725   NewFn->setLinkage(GA->getLinkage());
 726   GA->replaceAllUsesWith(ConstantExpr::getBitCast(NewFn, GA->getType()));
 727   NewFn->takeName(GA);
 728   return NewFn;
 729 }
 730
 731 // Automatically import functions in Module \p DestModule based on the summaries
 732 // index.
 733 Expected<bool> FunctionImporter::importFunctions(
 734     Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) {
 735   DEBUG(dbgs() << "Starting import for Module "
 736                << DestModule.getModuleIdentifier() << "\n");
 737   unsigned ImportedCount = 0;
 738
 739   IRMover Mover(DestModule);
 740   // Do the actual import of functions now, one Module at a time
 741   std::set<StringRef> ModuleNameOrderedList;
 742   for (auto &FunctionsToImportPerModule : ImportList) {
 743     ModuleNameOrderedList.insert(FunctionsToImportPerModule.first());
 744   }
 745   for (auto &Name : ModuleNameOrderedList) {
 746     // Get the module for the import
 747     const auto &FunctionsToImportPerModule = ImportList.find(Name);
 748     assert(FunctionsToImportPerModule != ImportList.end());
 749     Expected<std::unique_ptr<Module>> SrcModuleOrErr = ModuleLoader(Name);
 750     if (!SrcModuleOrErr)
 751       return SrcModuleOrErr.takeError();
 752     std::unique_ptr<Module> SrcModule = std::move(*SrcModuleOrErr);
 753     assert(&DestModule.getContext() == &SrcModule->getContext() &&
 754            "Context mismatch");
 755
 756     // If modules were created with lazy metadata loading, materialize it
 757     // now, before linking it (otherwise this will be a noop).
 758     if (Error Err = SrcModule->materializeMetadata())
 759       return std::move(Err);
 760
 761     auto &ImportGUIDs = FunctionsToImportPerModule->second;
 762     // Find the globals to import
 763     SetVector<GlobalValue *> GlobalsToImport;
 764     for (Function &F : *SrcModule) {
 765       if (!F.hasName())
 766         continue;
 767       auto GUID = F.getGUID();
 768       auto Import = ImportGUIDs.count(GUID);
 769       DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing function " << GUID
 770                    << " " << F.getName() << " from "
 771                    << SrcModule->getSourceFileName() << "\n");
 772       if (Import) {
 773         if (Error Err = F.materialize())
 774           return std::move(Err);
 775         if (EnableImportMetadata) {
 776           // Add 'thinlto_src_module' metadata for statistics and debugging.
 777           F.setMetadata(
 778               "thinlto_src_module",
 779               MDNode::get(DestModule.getContext(),
 780                           {MDString::get(DestModule.getContext(),
 781                                          SrcModule->getSourceFileName())}));
 782         }
 783         GlobalsToImport.insert(&F);
 784       }
 785     }
 786     for (GlobalVariable &GV : SrcModule->globals()) {
 787       if (!GV.hasName())
 788         continue;
 789       auto GUID = GV.getGUID();
 790       auto Import = ImportGUIDs.count(GUID);
 791       DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing global " << GUID
 792                    << " " << GV.getName() << " from "
 793                    << SrcModule->getSourceFileName() << "\n");
 794       if (Import) {
 795         if (Error Err = GV.materialize())
 796           return std::move(Err);
 797         GlobalsToImport.insert(&GV);
 798       }
 799     }
 800     for (GlobalAlias &GA : SrcModule->aliases()) {
 801       if (!GA.hasName())
 802         continue;
 803       auto GUID = GA.getGUID();
 804       auto Import = ImportGUIDs.count(GUID);
 805       DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing alias " << GUID
 806                    << " " << GA.getName() << " from "
 807                    << SrcModule->getSourceFileName() << "\n");
 808       if (Import) {
 809         if (Error Err = GA.materialize())
 810           return std::move(Err);
 811         // Import alias as a copy of its aliasee.
 812         GlobalObject *Base = GA.getBaseObject();
 813         if (Error Err = Base->materialize())
 814           return std::move(Err);
 815         auto *Fn = replaceAliasWithAliasee(SrcModule.get(), &GA);
 816         DEBUG(dbgs() << "Is importing aliasee fn " << Base->getGUID()
 817               << " " << Base->getName() << " from "
 818               << SrcModule->getSourceFileName() << "\n");
 819         if (EnableImportMetadata) {
 820           // Add 'thinlto_src_module' metadata for statistics and debugging.
 821           Fn->setMetadata(
 822               "thinlto_src_module",
 823               MDNode::get(DestModule.getContext(),
 824                           {MDString::get(DestModule.getContext(),
 825                                          SrcModule->getSourceFileName())}));
 826         }
 827         GlobalsToImport.insert(Fn);
 828       }
 829     }
 830
 831     // Upgrade debug info after we're done materializing all the globals and we
 832     // have loaded all the required metadata!
 833     UpgradeDebugInfo(*SrcModule);
 834
 835     // Link in the specified functions.
 836     if (renameModuleForThinLTO(*SrcModule, Index, &GlobalsToImport))
 837       return true;
 838
 839     if (PrintImports) {
 840       for (const auto *GV : GlobalsToImport)
 841         dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName()
 842                << " from " << SrcModule->getSourceFileName() << "\n";
 843     }
 844
 845     if (Mover.move(std::move(SrcModule), GlobalsToImport.getArrayRef(),
 846                    [](GlobalValue &, IRMover::ValueAdder) {},
 847                    /*IsPerformingImport=*/true))
 848       report_fatal_error("Function Import: link error");
 849
 850     ImportedCount += GlobalsToImport.size();
 851     NumImportedModules++;
 852   }
 853
 854   NumImportedFunctions += ImportedCount;
 855
 856   DEBUG(dbgs() << "Imported " << ImportedCount << " functions for Module "
 857                << DestModule.getModuleIdentifier() << "\n");
 858   return ImportedCount;
 859 }
 860
 861 static bool doImportingForModule(Module &M) {
 862   if (SummaryFile.empty())
 863     report_fatal_error("error: -function-import requires -summary-file\n");
 864   Expected<std::unique_ptr<ModuleSummaryIndex>> IndexPtrOrErr =
 865       getModuleSummaryIndexForFile(SummaryFile);
 866   if (!IndexPtrOrErr) {
 867     logAllUnhandledErrors(IndexPtrOrErr.takeError(), errs(),
 868                           "Error loading file '" + SummaryFile + "': ");
 869     return false;
 870   }
 871   std::unique_ptr<ModuleSummaryIndex> Index = std::move(*IndexPtrOrErr);
 872
 873   // First step is collecting the import list.
 874   FunctionImporter::ImportMapTy ImportList;
 875   // If requested, simply import all functions in the index. This is used
 876   // when testing distributed backend handling via the opt tool, when
 877   // we have distributed indexes containing exactly the summaries to import.
 878   if (ImportAllIndex)
 879     ComputeCrossModuleImportForModuleFromIndex(M.getModuleIdentifier(), *Index,
 880                                                ImportList);
 881   else
 882     ComputeCrossModuleImportForModule(M.getModuleIdentifier(), *Index,
 883                                       ImportList);
 884
 885   // Conservatively mark all internal values as promoted. This interface is
 886   // only used when doing importing via the function importing pass. The pass
 887   // is only enabled when testing importing via the 'opt' tool, which does
 888   // not do the ThinLink that would normally determine what values to promote.
 889   for (auto &I : *Index) {
 890     for (auto &S : I.second.SummaryList) {
 891       if (GlobalValue::isLocalLinkage(S->linkage()))
 892         S->setLinkage(GlobalValue::ExternalLinkage);
 893     }
 894   }
 895
 896   // Next we need to promote to global scope and rename any local values that
 897   // are potentially exported to other modules.
 898   if (renameModuleForThinLTO(M, *Index, nullptr)) {
 899     errs() << "Error renaming module\n";
 900     return false;
 901   }
 902
 903   // Perform the import now.
 904   auto ModuleLoader = [&M](StringRef Identifier) {
 905     return loadFile(Identifier, M.getContext());
 906   };
 907   FunctionImporter Importer(*Index, ModuleLoader);
 908   Expected<bool> Result = Importer.importFunctions(M, ImportList);
 909
 910   // FIXME: Probably need to propagate Errors through the pass manager.
 911   if (!Result) {
 912     logAllUnhandledErrors(Result.takeError(), errs(),
 913                           "Error importing module: ");
 914     return false;
 915   }
 916
 917   return *Result;
 918 }
 919
 920 namespace {
 921
 922 /// Pass that performs cross-module function import provided a summary file.
 923 class FunctionImportLegacyPass : public ModulePass {
 924 public:
 925   /// Pass identification, replacement for typeid
 926   static char ID;
 927
 928   explicit FunctionImportLegacyPass() : ModulePass(ID) {}
 929
 930   /// Specify pass name for debug output
 931   StringRef getPassName() const override { return "Function Importing"; }
 932
 933   bool runOnModule(Module &M) override {
 934     if (skipModule(M))
 935       return false;
 936
 937     return doImportingForModule(M);
 938   }
 939 };
 940
 941 } // end anonymous namespace
 942
 943 PreservedAnalyses FunctionImportPass::run(Module &M,
 944                                           ModuleAnalysisManager &AM) {
 945   if (!doImportingForModule(M))
 946     return PreservedAnalyses::all();
 947
 948   return PreservedAnalyses::none();
 949 }
 950
 951 char FunctionImportLegacyPass::ID = 0;
 952 INITIALIZE_PASS(FunctionImportLegacyPass, "function-import",
 953                 "Summary Based Function Import", false, false)
 954
 955 namespace llvm {
 956
 957 Pass *createFunctionImportPass() {
 958   return new FunctionImportLegacyPass();
 959 }
 960
 961 } // end namespace llvm