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