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/StringRef.h"
  22 #include "llvm/ADT/StringSet.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(NumImportedFunctionsThinLink,
  64           "Number of functions thin link decided to import");
  65 STATISTIC(NumImportedHotFunctionsThinLink,
  66           "Number of hot functions thin link decided to import");
  67 STATISTIC(NumImportedCriticalFunctionsThinLink,
  68           "Number of critical functions thin link decided to import");
  69 STATISTIC(NumImportedGlobalVarsThinLink,
  70           "Number of global variables thin link decided to import");
  71 STATISTIC(NumImportedFunctions, "Number of functions imported in backend");
  72 STATISTIC(NumImportedGlobalVars,
  73           "Number of global variables imported in backend");
  74 STATISTIC(NumImportedModules, "Number of modules imported from");
  75 STATISTIC(NumDeadSymbols, "Number of dead stripped symbols in index");
  76 STATISTIC(NumLiveSymbols, "Number of live symbols in index");
  77
  78 /// Limit on instruction count of imported functions.
  79 static cl::opt<unsigned> ImportInstrLimit(
  80     "import-instr-limit", cl::init(100), cl::Hidden, cl::value_desc("N"),
  81     cl::desc("Only import functions with less than N instructions"));
  82
  83 static cl::opt<int> ImportCutoff(
  84     "import-cutoff", cl::init(-1), cl::Hidden, cl::value_desc("N"),
  85     cl::desc("Only import first N functions if N>=0 (default -1)"));
  86
  87 static cl::opt<float>
  88     ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7),
  89                       cl::Hidden, cl::value_desc("x"),
  90                       cl::desc("As we import functions, multiply the "
  91                                "`import-instr-limit` threshold by this factor "
  92                                "before processing newly imported functions"));
  93
  94 static cl::opt<float> ImportHotInstrFactor(
  95     "import-hot-evolution-factor", cl::init(1.0), cl::Hidden,
  96     cl::value_desc("x"),
  97     cl::desc("As we import functions called from hot callsite, multiply the "
  98              "`import-instr-limit` threshold by this factor "
  99              "before processing newly imported functions"));
 100
 101 static cl::opt<float> ImportHotMultiplier(
 102     "import-hot-multiplier", cl::init(10.0), cl::Hidden, cl::value_desc("x"),
 103     cl::desc("Multiply the `import-instr-limit` threshold for hot callsites"));
 104
 105 static cl::opt<float> ImportCriticalMultiplier(
 106     "import-critical-multiplier", cl::init(100.0), cl::Hidden,
 107     cl::value_desc("x"),
 108     cl::desc(
 109         "Multiply the `import-instr-limit` threshold for critical callsites"));
 110
 111 // FIXME: This multiplier was not really tuned up.
 112 static cl::opt<float> ImportColdMultiplier(
 113     "import-cold-multiplier", cl::init(0), cl::Hidden, cl::value_desc("N"),
 114     cl::desc("Multiply the `import-instr-limit` threshold for cold callsites"));
 115
 116 static cl::opt<bool> PrintImports("print-imports", cl::init(false), cl::Hidden,
 117                                   cl::desc("Print imported functions"));
 118
 119 static cl::opt<bool> PrintImportFailures(
 120     "print-import-failures", cl::init(false), cl::Hidden,
 121     cl::desc("Print information for functions rejected for importing"));
 122
 123 static cl::opt<bool> ComputeDead("compute-dead", cl::init(true), cl::Hidden,
 124                                  cl::desc("Compute dead symbols"));
 125
 126 static cl::opt<bool> EnableImportMetadata(
 127     "enable-import-metadata", cl::init(
 128 #if !defined(NDEBUG)
 129                                   true /*Enabled with asserts.*/
 130 #else
 131                                   false
 132 #endif
 133                                   ),
 134     cl::Hidden, cl::desc("Enable import metadata like 'thinlto_src_module'"));
 135
 136 /// Summary file to use for function importing when using -function-import from
 137 /// the command line.
 138 static cl::opt<std::string>
 139     SummaryFile("summary-file",
 140                 cl::desc("The summary file to use for function importing."));
 141
 142 /// Used when testing importing from distributed indexes via opt
 143 // -function-import.
 144 static cl::opt<bool>
 145     ImportAllIndex("import-all-index",
 146                    cl::desc("Import all external functions in index."));
 147
 148 // Load lazily a module from \p FileName in \p Context.
 149 static std::unique_ptr<Module> loadFile(const std::string &FileName,
 150                                         LLVMContext &Context) {
 151   SMDiagnostic Err;
 152   LLVM_DEBUG(dbgs() << "Loading '" << FileName << "'\n");
 153   // Metadata isn't loaded until functions are imported, to minimize
 154   // the memory overhead.
 155   std::unique_ptr<Module> Result =
 156       getLazyIRFileModule(FileName, Err, Context,
 157                           /* ShouldLazyLoadMetadata = */ true);
 158   if (!Result) {
 159     Err.print("function-import", errs());
 160     report_fatal_error("Abort");
 161   }
 162
 163   return Result;
 164 }
 165
 166 /// Given a list of possible callee implementation for a call site, select one
 167 /// that fits the \p Threshold.
 168 ///
 169 /// FIXME: select "best" instead of first that fits. But what is "best"?
 170 /// - The smallest: more likely to be inlined.
 171 /// - The one with the least outgoing edges (already well optimized).
 172 /// - One from a module already being imported from in order to reduce the
 173 ///   number of source modules parsed/linked.
 174 /// - One that has PGO data attached.
 175 /// - [insert you fancy metric here]
 176 static const GlobalValueSummary *
 177 selectCallee(const ModuleSummaryIndex &Index,
 178              ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList,
 179              unsigned Threshold, StringRef CallerModulePath,
 180              FunctionImporter::ImportFailureReason &Reason,
 181              GlobalValue::GUID GUID) {
 182   Reason = FunctionImporter::ImportFailureReason::None;
 183   auto It = llvm::find_if(
 184       CalleeSummaryList,
 185       [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) {
 186         auto *GVSummary = SummaryPtr.get();
 187         if (!Index.isGlobalValueLive(GVSummary)) {
 188           Reason = FunctionImporter::ImportFailureReason::NotLive;
 189           return false;
 190         }
 191
 192         // For SamplePGO, in computeImportForFunction the OriginalId
 193         // may have been used to locate the callee summary list (See
 194         // comment there).
 195         // The mapping from OriginalId to GUID may return a GUID
 196         // that corresponds to a static variable. Filter it out here.
 197         // This can happen when
 198         // 1) There is a call to a library function which is not defined
 199         // in the index.
 200         // 2) There is a static variable with the  OriginalGUID identical
 201         // to the GUID of the library function in 1);
 202         // When this happens, the logic for SamplePGO kicks in and
 203         // the static variable in 2) will be found, which needs to be
 204         // filtered out.
 205         if (GVSummary->getSummaryKind() == GlobalValueSummary::GlobalVarKind) {
 206           Reason = FunctionImporter::ImportFailureReason::GlobalVar;
 207           return false;
 208         }
 209         if (GlobalValue::isInterposableLinkage(GVSummary->linkage())) {
 210           Reason = FunctionImporter::ImportFailureReason::InterposableLinkage;
 211           // There is no point in importing these, we can't inline them
 212           return false;
 213         }
 214
 215         auto *Summary = cast<FunctionSummary>(GVSummary->getBaseObject());
 216
 217         // If this is a local function, make sure we import the copy
 218         // in the caller's module. The only time a local function can
 219         // share an entry in the index is if there is a local with the same name
 220         // in another module that had the same source file name (in a different
 221         // directory), where each was compiled in their own directory so there
 222         // was not distinguishing path.
 223         // However, do the import from another module if there is only one
 224         // entry in the list - in that case this must be a reference due
 225         // to indirect call profile data, since a function pointer can point to
 226         // a local in another module.
 227         if (GlobalValue::isLocalLinkage(Summary->linkage()) &&
 228             CalleeSummaryList.size() > 1 &&
 229             Summary->modulePath() != CallerModulePath) {
 230           Reason =
 231               FunctionImporter::ImportFailureReason::LocalLinkageNotInModule;
 232           return false;
 233         }
 234
 235         if (Summary->instCount() > Threshold) {
 236           Reason = FunctionImporter::ImportFailureReason::TooLarge;
 237           return false;
 238         }
 239
 240         // Skip if it isn't legal to import (e.g. may reference unpromotable
 241         // locals).
 242         if (Summary->notEligibleToImport()) {
 243           Reason = FunctionImporter::ImportFailureReason::NotEligible;
 244           return false;
 245         }
 246
 247         // Don't bother importing if we can't inline it anyway.
 248         if (Summary->fflags().NoInline) {
 249           Reason = FunctionImporter::ImportFailureReason::NoInline;
 250           return false;
 251         }
 252
 253         return true;
 254       });
 255   if (It == CalleeSummaryList.end())
 256     return nullptr;
 257
 258   return cast<GlobalValueSummary>(It->get());
 259 }
 260
 261 namespace {
 262
 263 using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */,
 264                             GlobalValue::GUID>;
 265
 266 } // anonymous namespace
 267
 268 static ValueInfo
 269 updateValueInfoForIndirectCalls(const ModuleSummaryIndex &Index, ValueInfo VI) {
 270   if (!VI.getSummaryList().empty())
 271     return VI;
 272   // For SamplePGO, the indirect call targets for local functions will
 273   // have its original name annotated in profile. We try to find the
 274   // corresponding PGOFuncName as the GUID.
 275   // FIXME: Consider updating the edges in the graph after building
 276   // it, rather than needing to perform this mapping on each walk.
 277   auto GUID = Index.getGUIDFromOriginalID(VI.getGUID());
 278   if (GUID == 0)
 279     return ValueInfo();
 280   return Index.getValueInfo(GUID);
 281 }
 282
 283 static void computeImportForReferencedGlobals(
 284     const FunctionSummary &Summary, const GVSummaryMapTy &DefinedGVSummaries,
 285     FunctionImporter::ImportMapTy &ImportList,
 286     StringMap<FunctionImporter::ExportSetTy> *ExportLists) {
 287   for (auto &VI : Summary.refs()) {
 288     if (DefinedGVSummaries.count(VI.getGUID())) {
 289       LLVM_DEBUG(
 290           dbgs() << "Ref ignored! Target already in destination module.\n");
 291       continue;
 292     }
 293
 294     LLVM_DEBUG(dbgs() << " ref -> " << VI << "\n");
 295
 296     // If this is a local variable, make sure we import the copy
 297     // in the caller's module. The only time a local variable can
 298     // share an entry in the index is if there is a local with the same name
 299     // in another module that had the same source file name (in a different
 300     // directory), where each was compiled in their own directory so there
 301     // was not distinguishing path.
 302     auto LocalNotInModule = [&](const GlobalValueSummary *RefSummary) -> bool {
 303       return GlobalValue::isLocalLinkage(RefSummary->linkage()) &&
 304              RefSummary->modulePath() != Summary.modulePath();
 305     };
 306
 307     for (auto &RefSummary : VI.getSummaryList())
 308       if (isa<GlobalVarSummary>(RefSummary.get()) &&
 309           canImportGlobalVar(RefSummary.get()) &&
 310           !LocalNotInModule(RefSummary.get())) {
 311         auto ILI = ImportList[RefSummary->modulePath()].insert(VI.getGUID());
 312         // Only update stat if we haven't already imported this variable.
 313         if (ILI.second)
 314           NumImportedGlobalVarsThinLink++;
 315         if (ExportLists)
 316           (*ExportLists)[RefSummary->modulePath()].insert(VI.getGUID());
 317         break;
 318       }
 319   }
 320 }
 321
 322 static const char *
 323 getFailureName(FunctionImporter::ImportFailureReason Reason) {
 324   switch (Reason) {
 325   case FunctionImporter::ImportFailureReason::None:
 326     return "None";
 327   case FunctionImporter::ImportFailureReason::GlobalVar:
 328     return "GlobalVar";
 329   case FunctionImporter::ImportFailureReason::NotLive:
 330     return "NotLive";
 331   case FunctionImporter::ImportFailureReason::TooLarge:
 332     return "TooLarge";
 333   case FunctionImporter::ImportFailureReason::InterposableLinkage:
 334     return "InterposableLinkage";
 335   case FunctionImporter::ImportFailureReason::LocalLinkageNotInModule:
 336     return "LocalLinkageNotInModule";
 337   case FunctionImporter::ImportFailureReason::NotEligible:
 338     return "NotEligible";
 339   case FunctionImporter::ImportFailureReason::NoInline:
 340     return "NoInline";
 341   }
 342   llvm_unreachable("invalid reason");
 343 }
 344
 345 /// Compute the list of functions to import for a given caller. Mark these
 346 /// imported functions and the symbols they reference in their source module as
 347 /// exported from their source module.
 348 static void computeImportForFunction(
 349     const FunctionSummary &Summary, const ModuleSummaryIndex &Index,
 350     const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries,
 351     SmallVectorImpl<EdgeInfo> &Worklist,
 352     FunctionImporter::ImportMapTy &ImportList,
 353     StringMap<FunctionImporter::ExportSetTy> *ExportLists,
 354     FunctionImporter::ImportThresholdsTy &ImportThresholds) {
 355   computeImportForReferencedGlobals(Summary, DefinedGVSummaries, ImportList,
 356                                     ExportLists);
 357   static int ImportCount = 0;
 358   for (auto &Edge : Summary.calls()) {
 359     ValueInfo VI = Edge.first;
 360     LLVM_DEBUG(dbgs() << " edge -> " << VI << " Threshold:" << Threshold
 361                       << "\n");
 362
 363     if (ImportCutoff >= 0 && ImportCount >= ImportCutoff) {
 364       LLVM_DEBUG(dbgs() << "ignored! import-cutoff value of " << ImportCutoff
 365                         << " reached.\n");
 366       continue;
 367     }
 368
 369     VI = updateValueInfoForIndirectCalls(Index, VI);
 370     if (!VI)
 371       continue;
 372
 373     if (DefinedGVSummaries.count(VI.getGUID())) {
 374       LLVM_DEBUG(dbgs() << "ignored! Target already in destination module.\n");
 375       continue;
 376     }
 377
 378     auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float {
 379       if (Hotness == CalleeInfo::HotnessType::Hot)
 380         return ImportHotMultiplier;
 381       if (Hotness == CalleeInfo::HotnessType::Cold)
 382         return ImportColdMultiplier;
 383       if (Hotness == CalleeInfo::HotnessType::Critical)
 384         return ImportCriticalMultiplier;
 385       return 1.0;
 386     };
 387
 388     const auto NewThreshold =
 389         Threshold * GetBonusMultiplier(Edge.second.getHotness());
 390
 391     auto IT = ImportThresholds.insert(std::make_pair(
 392         VI.getGUID(), std::make_tuple(NewThreshold, nullptr, nullptr)));
 393     bool PreviouslyVisited = !IT.second;
 394     auto &ProcessedThreshold = std::get<0>(IT.first->second);
 395     auto &CalleeSummary = std::get<1>(IT.first->second);
 396     auto &FailureInfo = std::get<2>(IT.first->second);
 397
 398     bool IsHotCallsite =
 399         Edge.second.getHotness() == CalleeInfo::HotnessType::Hot;
 400     bool IsCriticalCallsite =
 401         Edge.second.getHotness() == CalleeInfo::HotnessType::Critical;
 402
 403     const FunctionSummary *ResolvedCalleeSummary = nullptr;
 404     if (CalleeSummary) {
 405       assert(PreviouslyVisited);
 406       // Since the traversal of the call graph is DFS, we can revisit a function
 407       // a second time with a higher threshold. In this case, it is added back
 408       // to the worklist with the new threshold (so that its own callee chains
 409       // can be considered with the higher threshold).
 410       if (NewThreshold <= ProcessedThreshold) {
 411         LLVM_DEBUG(
 412             dbgs() << "ignored! Target was already imported with Threshold "
 413                    << ProcessedThreshold << "\n");
 414         continue;
 415       }
 416       // Update with new larger threshold.
 417       ProcessedThreshold = NewThreshold;
 418       ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
 419     } else {
 420       // If we already rejected importing a callee at the same or higher
 421       // threshold, don't waste time calling selectCallee.
 422       if (PreviouslyVisited && NewThreshold <= ProcessedThreshold) {
 423         LLVM_DEBUG(
 424             dbgs() << "ignored! Target was already rejected with Threshold "
 425             << ProcessedThreshold << "\n");
 426         if (PrintImportFailures) {
 427           assert(FailureInfo &&
 428                  "Expected FailureInfo for previously rejected candidate");
 429           FailureInfo->Attempts++;
 430         }
 431         continue;
 432       }
 433
 434       FunctionImporter::ImportFailureReason Reason;
 435       CalleeSummary = selectCallee(Index, VI.getSummaryList(), NewThreshold,
 436                                    Summary.modulePath(), Reason, VI.getGUID());
 437       if (!CalleeSummary) {
 438         // Update with new larger threshold if this was a retry (otherwise
 439         // we would have already inserted with NewThreshold above). Also
 440         // update failure info if requested.
 441         if (PreviouslyVisited) {
 442           ProcessedThreshold = NewThreshold;
 443           if (PrintImportFailures) {
 444             assert(FailureInfo &&
 445                    "Expected FailureInfo for previously rejected candidate");
 446             FailureInfo->Reason = Reason;
 447             FailureInfo->Attempts++;
 448             FailureInfo->MaxHotness =
 449                 std::max(FailureInfo->MaxHotness, Edge.second.getHotness());
 450           }
 451         } else if (PrintImportFailures) {
 452           assert(!FailureInfo &&
 453                  "Expected no FailureInfo for newly rejected candidate");
 454           FailureInfo = llvm::make_unique<FunctionImporter::ImportFailureInfo>(
 455               VI, Edge.second.getHotness(), Reason, 1);
 456         }
 457         LLVM_DEBUG(
 458             dbgs() << "ignored! No qualifying callee with summary found.\n");
 459         continue;
 460       }
 461
 462       // "Resolve" the summary
 463       CalleeSummary = CalleeSummary->getBaseObject();
 464       ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary);
 465
 466       assert(ResolvedCalleeSummary->instCount() <= NewThreshold &&
 467              "selectCallee() didn't honor the threshold");
 468
 469       auto ExportModulePath = ResolvedCalleeSummary->modulePath();
 470       auto ILI = ImportList[ExportModulePath].insert(VI.getGUID());
 471       // We previously decided to import this GUID definition if it was already
 472       // inserted in the set of imports from the exporting module.
 473       bool PreviouslyImported = !ILI.second;
 474       if (!PreviouslyImported) {
 475         NumImportedFunctionsThinLink++;
 476         if (IsHotCallsite)
 477           NumImportedHotFunctionsThinLink++;
 478         if (IsCriticalCallsite)
 479           NumImportedCriticalFunctionsThinLink++;
 480       }
 481
 482       // Make exports in the source module.
 483       if (ExportLists) {
 484         auto &ExportList = (*ExportLists)[ExportModulePath];
 485         ExportList.insert(VI.getGUID());
 486         if (!PreviouslyImported) {
 487           // This is the first time this function was exported from its source
 488           // module, so mark all functions and globals it references as exported
 489           // to the outside if they are defined in the same source module.
 490           // For efficiency, we unconditionally add all the referenced GUIDs
 491           // to the ExportList for this module, and will prune out any not
 492           // defined in the module later in a single pass.
 493           for (auto &Edge : ResolvedCalleeSummary->calls()) {
 494             auto CalleeGUID = Edge.first.getGUID();
 495             ExportList.insert(CalleeGUID);
 496           }
 497           for (auto &Ref : ResolvedCalleeSummary->refs()) {
 498             auto GUID = Ref.getGUID();
 499             ExportList.insert(GUID);
 500           }
 501         }
 502       }
 503     }
 504
 505     auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
 506       // Adjust the threshold for next level of imported functions.
 507       // The threshold is different for hot callsites because we can then
 508       // inline chains of hot calls.
 509       if (IsHotCallsite)
 510         return Threshold * ImportHotInstrFactor;
 511       return Threshold * ImportInstrFactor;
 512     };
 513
 514     const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite);
 515
 516     ImportCount++;
 517
 518     // Insert the newly imported function to the worklist.
 519     Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, VI.getGUID());
 520   }
 521 }
 522
 523 /// Given the list of globals defined in a module, compute the list of imports
 524 /// as well as the list of "exports", i.e. the list of symbols referenced from
 525 /// another module (that may require promotion).
 526 static void ComputeImportForModule(
 527     const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index,
 528     StringRef ModName, FunctionImporter::ImportMapTy &ImportList,
 529     StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) {
 530   // Worklist contains the list of function imported in this module, for which
 531   // we will analyse the callees and may import further down the callgraph.
 532   SmallVector<EdgeInfo, 128> Worklist;
 533   FunctionImporter::ImportThresholdsTy ImportThresholds;
 534
 535   // Populate the worklist with the import for the functions in the current
 536   // module
 537   for (auto &GVSummary : DefinedGVSummaries) {
 538 #ifndef NDEBUG
 539     // FIXME: Change the GVSummaryMapTy to hold ValueInfo instead of GUID
 540     // so this map look up (and possibly others) can be avoided.
 541     auto VI = Index.getValueInfo(GVSummary.first);
 542 #endif
 543     if (!Index.isGlobalValueLive(GVSummary.second)) {
 544       LLVM_DEBUG(dbgs() << "Ignores Dead GUID: " << VI << "\n");
 545       continue;
 546     }
 547     auto *FuncSummary =
 548         dyn_cast<FunctionSummary>(GVSummary.second->getBaseObject());
 549     if (!FuncSummary)
 550       // Skip import for global variables
 551       continue;
 552     LLVM_DEBUG(dbgs() << "Initialize import for " << VI << "\n");
 553     computeImportForFunction(*FuncSummary, Index, ImportInstrLimit,
 554                              DefinedGVSummaries, Worklist, ImportList,
 555                              ExportLists, ImportThresholds);
 556   }
 557
 558   // Process the newly imported functions and add callees to the worklist.
 559   while (!Worklist.empty()) {
 560     auto FuncInfo = Worklist.pop_back_val();
 561     auto *Summary = std::get<0>(FuncInfo);
 562     auto Threshold = std::get<1>(FuncInfo);
 563
 564     computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries,
 565                              Worklist, ImportList, ExportLists,
 566                              ImportThresholds);
 567   }
 568
 569   // Print stats about functions considered but rejected for importing
 570   // when requested.
 571   if (PrintImportFailures) {
 572     dbgs() << "Missed imports into module " << ModName << "\n";
 573     for (auto &I : ImportThresholds) {
 574       auto &ProcessedThreshold = std::get<0>(I.second);
 575       auto &CalleeSummary = std::get<1>(I.second);
 576       auto &FailureInfo = std::get<2>(I.second);
 577       if (CalleeSummary)
 578         continue; // We are going to import.
 579       assert(FailureInfo);
 580       FunctionSummary *FS = nullptr;
 581       if (!FailureInfo->VI.getSummaryList().empty())
 582         FS = dyn_cast<FunctionSummary>(
 583             FailureInfo->VI.getSummaryList()[0]->getBaseObject());
 584       dbgs() << FailureInfo->VI
 585              << ": Reason = " << getFailureName(FailureInfo->Reason)
 586              << ", Threshold = " << ProcessedThreshold
 587              << ", Size = " << (FS ? (int)FS->instCount() : -1)
 588              << ", MaxHotness = " << getHotnessName(FailureInfo->MaxHotness)
 589              << ", Attempts = " << FailureInfo->Attempts << "\n";
 590     }
 591   }
 592 }
 593
 594 #ifndef NDEBUG
 595 static bool isGlobalVarSummary(const ModuleSummaryIndex &Index,
 596                                GlobalValue::GUID G) {
 597   if (const auto &VI = Index.getValueInfo(G)) {
 598     auto SL = VI.getSummaryList();
 599     if (!SL.empty())
 600       return SL[0]->getSummaryKind() == GlobalValueSummary::GlobalVarKind;
 601   }
 602   return false;
 603 }
 604
 605 static GlobalValue::GUID getGUID(GlobalValue::GUID G) { return G; }
 606
 607 template <class T>
 608 static unsigned numGlobalVarSummaries(const ModuleSummaryIndex &Index,
 609                                       T &Cont) {
 610   unsigned NumGVS = 0;
 611   for (auto &V : Cont)
 612     if (isGlobalVarSummary(Index, getGUID(V)))
 613       ++NumGVS;
 614   return NumGVS;
 615 }
 616 #endif
 617
 618 /// Compute all the import and export for every module using the Index.
 619 void llvm::ComputeCrossModuleImport(
 620     const ModuleSummaryIndex &Index,
 621     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
 622     StringMap<FunctionImporter::ImportMapTy> &ImportLists,
 623     StringMap<FunctionImporter::ExportSetTy> &ExportLists) {
 624   // For each module that has function defined, compute the import/export lists.
 625   for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
 626     auto &ImportList = ImportLists[DefinedGVSummaries.first()];
 627     LLVM_DEBUG(dbgs() << "Computing import for Module '"
 628                       << DefinedGVSummaries.first() << "'\n");
 629     ComputeImportForModule(DefinedGVSummaries.second, Index,
 630                            DefinedGVSummaries.first(), ImportList,
 631                            &ExportLists);
 632   }
 633
 634   // When computing imports we added all GUIDs referenced by anything
 635   // imported from the module to its ExportList. Now we prune each ExportList
 636   // of any not defined in that module. This is more efficient than checking
 637   // while computing imports because some of the summary lists may be long
 638   // due to linkonce (comdat) copies.
 639   for (auto &ELI : ExportLists) {
 640     const auto &DefinedGVSummaries =
 641         ModuleToDefinedGVSummaries.lookup(ELI.first());
 642     for (auto EI = ELI.second.begin(); EI != ELI.second.end();) {
 643       if (!DefinedGVSummaries.count(*EI))
 644         EI = ELI.second.erase(EI);
 645       else
 646         ++EI;
 647     }
 648   }
 649
 650 #ifndef NDEBUG
 651   LLVM_DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size()
 652                     << " modules:\n");
 653   for (auto &ModuleImports : ImportLists) {
 654     auto ModName = ModuleImports.first();
 655     auto &Exports = ExportLists[ModName];
 656     unsigned NumGVS = numGlobalVarSummaries(Index, Exports);
 657     LLVM_DEBUG(dbgs() << "* Module " << ModName << " exports "
 658                       << Exports.size() - NumGVS << " functions and " << NumGVS
 659                       << " vars. Imports from " << ModuleImports.second.size()
 660                       << " modules.\n");
 661     for (auto &Src : ModuleImports.second) {
 662       auto SrcModName = Src.first();
 663       unsigned NumGVSPerMod = numGlobalVarSummaries(Index, Src.second);
 664       LLVM_DEBUG(dbgs() << " - " << Src.second.size() - NumGVSPerMod
 665                         << " functions imported from " << SrcModName << "\n");
 666       LLVM_DEBUG(dbgs() << " - " << NumGVSPerMod
 667                         << " global vars imported from " << SrcModName << "\n");
 668     }
 669   }
 670 #endif
 671 }
 672
 673 #ifndef NDEBUG
 674 static void dumpImportListForModule(const ModuleSummaryIndex &Index,
 675                                     StringRef ModulePath,
 676                                     FunctionImporter::ImportMapTy &ImportList) {
 677   LLVM_DEBUG(dbgs() << "* Module " << ModulePath << " imports from "
 678                     << ImportList.size() << " modules.\n");
 679   for (auto &Src : ImportList) {
 680     auto SrcModName = Src.first();
 681     unsigned NumGVSPerMod = numGlobalVarSummaries(Index, Src.second);
 682     LLVM_DEBUG(dbgs() << " - " << Src.second.size() - NumGVSPerMod
 683                       << " functions imported from " << SrcModName << "\n");
 684     LLVM_DEBUG(dbgs() << " - " << NumGVSPerMod << " vars imported from "
 685                       << SrcModName << "\n");
 686   }
 687 }
 688 #endif
 689
 690 /// Compute all the imports for the given module in the Index.
 691 void llvm::ComputeCrossModuleImportForModule(
 692     StringRef ModulePath, const ModuleSummaryIndex &Index,
 693     FunctionImporter::ImportMapTy &ImportList) {
 694   // Collect the list of functions this module defines.
 695   // GUID -> Summary
 696   GVSummaryMapTy FunctionSummaryMap;
 697   Index.collectDefinedFunctionsForModule(ModulePath, FunctionSummaryMap);
 698
 699   // Compute the import list for this module.
 700   LLVM_DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n");
 701   ComputeImportForModule(FunctionSummaryMap, Index, ModulePath, ImportList);
 702
 703 #ifndef NDEBUG
 704   dumpImportListForModule(Index, ModulePath, ImportList);
 705 #endif
 706 }
 707
 708 // Mark all external summaries in Index for import into the given module.
 709 // Used for distributed builds using a distributed index.
 710 void llvm::ComputeCrossModuleImportForModuleFromIndex(
 711     StringRef ModulePath, const ModuleSummaryIndex &Index,
 712     FunctionImporter::ImportMapTy &ImportList) {
 713   for (auto &GlobalList : Index) {
 714     // Ignore entries for undefined references.
 715     if (GlobalList.second.SummaryList.empty())
 716       continue;
 717
 718     auto GUID = GlobalList.first;
 719     assert(GlobalList.second.SummaryList.size() == 1 &&
 720            "Expected individual combined index to have one summary per GUID");
 721     auto &Summary = GlobalList.second.SummaryList[0];
 722     // Skip the summaries for the importing module. These are included to
 723     // e.g. record required linkage changes.
 724     if (Summary->modulePath() == ModulePath)
 725       continue;
 726     // Add an entry to provoke importing by thinBackend.
 727     ImportList[Summary->modulePath()].insert(GUID);
 728   }
 729 #ifndef NDEBUG
 730   dumpImportListForModule(Index, ModulePath, ImportList);
 731 #endif
 732 }
 733
 734 void llvm::computeDeadSymbols(
 735     ModuleSummaryIndex &Index,
 736     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
 737     function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing) {
 738   assert(!Index.withGlobalValueDeadStripping());
 739   if (!ComputeDead)
 740     return;
 741   if (GUIDPreservedSymbols.empty())
 742     // Don't do anything when nothing is live, this is friendly with tests.
 743     return;
 744   unsigned LiveSymbols = 0;
 745   SmallVector<ValueInfo, 128> Worklist;
 746   Worklist.reserve(GUIDPreservedSymbols.size() * 2);
 747   for (auto GUID : GUIDPreservedSymbols) {
 748     ValueInfo VI = Index.getValueInfo(GUID);
 749     if (!VI)
 750       continue;
 751     for (auto &S : VI.getSummaryList())
 752       S->setLive(true);
 753   }
 754
 755   // Add values flagged in the index as live roots to the worklist.
 756   for (const auto &Entry : Index) {
 757     auto VI = Index.getValueInfo(Entry);
 758     for (auto &S : Entry.second.SummaryList)
 759       if (S->isLive()) {
 760         LLVM_DEBUG(dbgs() << "Live root: " << VI << "\n");
 761         Worklist.push_back(VI);
 762         ++LiveSymbols;
 763         break;
 764       }
 765   }
 766
 767   // Make value live and add it to the worklist if it was not live before.
 768   auto visit = [&](ValueInfo VI) {
 769     // FIXME: If we knew which edges were created for indirect call profiles,
 770     // we could skip them here. Any that are live should be reached via
 771     // other edges, e.g. reference edges. Otherwise, using a profile collected
 772     // on a slightly different binary might provoke preserving, importing
 773     // and ultimately promoting calls to functions not linked into this
 774     // binary, which increases the binary size unnecessarily. Note that
 775     // if this code changes, the importer needs to change so that edges
 776     // to functions marked dead are skipped.
 777     VI = updateValueInfoForIndirectCalls(Index, VI);
 778     if (!VI)
 779       return;
 780
 781     // We need to make sure all variants of the symbol are scanned, alias can
 782     // make one (but not all) alive.
 783     if (llvm::all_of(VI.getSummaryList(),
 784                      [](const std::unique_ptr<llvm::GlobalValueSummary> &S) {
 785                        return S->isLive();
 786                      }))
 787       return;
 788
 789     // We only keep live symbols that are known to be non-prevailing if any are
 790     // available_externally, linkonceodr, weakodr. Those symbols are discarded
 791     // later in the EliminateAvailableExternally pass and setting them to
 792     // not-live could break downstreams users of liveness information (PR36483)
 793     // or limit optimization opportunities.
 794     if (isPrevailing(VI.getGUID()) == PrevailingType::No) {
 795       bool KeepAliveLinkage = false;
 796       bool Interposable = false;
 797       for (auto &S : VI.getSummaryList()) {
 798         if (S->linkage() == GlobalValue::AvailableExternallyLinkage ||
 799             S->linkage() == GlobalValue::WeakODRLinkage ||
 800             S->linkage() == GlobalValue::LinkOnceODRLinkage)
 801           KeepAliveLinkage = true;
 802         else if (GlobalValue::isInterposableLinkage(S->linkage()))
 803           Interposable = true;
 804       }
 805
 806       if (!KeepAliveLinkage)
 807         return;
 808
 809       if (Interposable)
 810         report_fatal_error(
 811           "Interposable and available_externally/linkonce_odr/weak_odr symbol");
 812     }
 813
 814     for (auto &S : VI.getSummaryList())
 815       S->setLive(true);
 816     ++LiveSymbols;
 817     Worklist.push_back(VI);
 818   };
 819
 820   while (!Worklist.empty()) {
 821     auto VI = Worklist.pop_back_val();
 822     for (auto &Summary : VI.getSummaryList()) {
 823       GlobalValueSummary *Base = Summary->getBaseObject();
 824       // Set base value live in case it is an alias.
 825       Base->setLive(true);
 826       for (auto Ref : Base->refs())
 827         visit(Ref);
 828       if (auto *FS = dyn_cast<FunctionSummary>(Base))
 829         for (auto Call : FS->calls())
 830           visit(Call.first);
 831     }
 832   }
 833   Index.setWithGlobalValueDeadStripping();
 834
 835   unsigned DeadSymbols = Index.size() - LiveSymbols;
 836   LLVM_DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols
 837                     << " symbols Dead \n");
 838   NumDeadSymbols += DeadSymbols;
 839   NumLiveSymbols += LiveSymbols;
 840 }
 841
 842 // Compute dead symbols and propagate constants in combined index.
 843 void llvm::computeDeadSymbolsWithConstProp(
 844     ModuleSummaryIndex &Index,
 845     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
 846     function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing,
 847     bool ImportEnabled) {
 848   computeDeadSymbols(Index, GUIDPreservedSymbols, isPrevailing);
 849   if (ImportEnabled) {
 850     Index.propagateConstants(GUIDPreservedSymbols);
 851   } else {
 852     // If import is disabled we should drop read-only attribute
 853     // from all summaries to prevent internalization.
 854     for (auto &P : Index)
 855       for (auto &S : P.second.SummaryList)
 856         if (auto *GVS = dyn_cast<GlobalVarSummary>(S.get()))
 857           GVS->setReadOnly(false);
 858   }
 859 }
 860
 861 /// Compute the set of summaries needed for a ThinLTO backend compilation of
 862 /// \p ModulePath.
 863 void llvm::gatherImportedSummariesForModule(
 864     StringRef ModulePath,
 865     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
 866     const FunctionImporter::ImportMapTy &ImportList,
 867     std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
 868   // Include all summaries from the importing module.
 869   ModuleToSummariesForIndex[ModulePath] =
 870       ModuleToDefinedGVSummaries.lookup(ModulePath);
 871   // Include summaries for imports.
 872   for (auto &ILI : ImportList) {
 873     auto &SummariesForIndex = ModuleToSummariesForIndex[ILI.first()];
 874     const auto &DefinedGVSummaries =
 875         ModuleToDefinedGVSummaries.lookup(ILI.first());
 876     for (auto &GI : ILI.second) {
 877       const auto &DS = DefinedGVSummaries.find(GI);
 878       assert(DS != DefinedGVSummaries.end() &&
 879              "Expected a defined summary for imported global value");
 880       SummariesForIndex[GI] = DS->second;
 881     }
 882   }
 883 }
 884
 885 /// Emit the files \p ModulePath will import from into \p OutputFilename.
 886 std::error_code llvm::EmitImportsFiles(
 887     StringRef ModulePath, StringRef OutputFilename,
 888     const std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
 889   std::error_code EC;
 890   raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::F_None);
 891   if (EC)
 892     return EC;
 893   for (auto &ILI : ModuleToSummariesForIndex)
 894     // The ModuleToSummariesForIndex map includes an entry for the current
 895     // Module (needed for writing out the index files). We don't want to
 896     // include it in the imports file, however, so filter it out.
 897     if (ILI.first != ModulePath)
 898       ImportsOS << ILI.first << "\n";
 899   return std::error_code();
 900 }
 901
 902 bool llvm::convertToDeclaration(GlobalValue &GV) {
 903   LLVM_DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName()
 904                     << "\n");
 905   if (Function *F = dyn_cast<Function>(&GV)) {
 906     F->deleteBody();
 907     F->clearMetadata();
 908     F->setComdat(nullptr);
 909   } else if (GlobalVariable *V = dyn_cast<GlobalVariable>(&GV)) {
 910     V->setInitializer(nullptr);
 911     V->setLinkage(GlobalValue::ExternalLinkage);
 912     V->clearMetadata();
 913     V->setComdat(nullptr);
 914   } else {
 915     GlobalValue *NewGV;
 916     if (GV.getValueType()->isFunctionTy())
 917       NewGV =
 918           Function::Create(cast<FunctionType>(GV.getValueType()),
 919                            GlobalValue::ExternalLinkage, GV.getAddressSpace(),
 920                            "", GV.getParent());
 921     else
 922       NewGV =
 923           new GlobalVariable(*GV.getParent(), GV.getValueType(),
 924                              /*isConstant*/ false, GlobalValue::ExternalLinkage,
 925                              /*init*/ nullptr, "",
 926                              /*insertbefore*/ nullptr, GV.getThreadLocalMode(),
 927                              GV.getType()->getAddressSpace());
 928     NewGV->takeName(&GV);
 929     GV.replaceAllUsesWith(NewGV);
 930     return false;
 931   }
 932   return true;
 933 }
 934
 935 /// Fixup prevailing symbol linkages in \p TheModule based on summary analysis.
 936 void llvm::thinLTOResolvePrevailingInModule(
 937     Module &TheModule, const GVSummaryMapTy &DefinedGlobals) {
 938   auto updateLinkage = [&](GlobalValue &GV) {
 939     // See if the global summary analysis computed a new resolved linkage.
 940     const auto &GS = DefinedGlobals.find(GV.getGUID());
 941     if (GS == DefinedGlobals.end())
 942       return;
 943     auto NewLinkage = GS->second->linkage();
 944     if (NewLinkage == GV.getLinkage())
 945       return;
 946
 947     // Switch the linkage to weakany if asked for, e.g. we do this for
 948     // linker redefined symbols (via --wrap or --defsym).
 949     // We record that the visibility should be changed here in `addThinLTO`
 950     // as we need access to the resolution vectors for each input file in
 951     // order to find which symbols have been redefined.
 952     // We may consider reorganizing this code and moving the linkage recording
 953     // somewhere else, e.g. in thinLTOResolvePrevailingInIndex.
 954     if (NewLinkage == GlobalValue::WeakAnyLinkage) {
 955       GV.setLinkage(NewLinkage);
 956       return;
 957     }
 958
 959     if (GlobalValue::isLocalLinkage(GV.getLinkage()) ||
 960         // In case it was dead and already converted to declaration.
 961         GV.isDeclaration())
 962       return;
 963     // Check for a non-prevailing def that has interposable linkage
 964     // (e.g. non-odr weak or linkonce). In that case we can't simply
 965     // convert to available_externally, since it would lose the
 966     // interposable property and possibly get inlined. Simply drop
 967     // the definition in that case.
 968     if (GlobalValue::isAvailableExternallyLinkage(NewLinkage) &&
 969         GlobalValue::isInterposableLinkage(GV.getLinkage())) {
 970       if (!convertToDeclaration(GV))
 971         // FIXME: Change this to collect replaced GVs and later erase
 972         // them from the parent module once thinLTOResolvePrevailingGUID is
 973         // changed to enable this for aliases.
 974         llvm_unreachable("Expected GV to be converted");
 975     } else {
 976       // If the original symbols has global unnamed addr and linkonce_odr linkage,
 977       // it should be an auto hide symbol. Add hidden visibility to the symbol to
 978       // preserve the property.
 979       if (GV.hasLinkOnceODRLinkage() && GV.hasGlobalUnnamedAddr() &&
 980           NewLinkage == GlobalValue::WeakODRLinkage)
 981         GV.setVisibility(GlobalValue::HiddenVisibility);
 982
 983       LLVM_DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName()
 984                         << "` from " << GV.getLinkage() << " to " << NewLinkage
 985                         << "\n");
 986       GV.setLinkage(NewLinkage);
 987     }
 988     // Remove declarations from comdats, including available_externally
 989     // as this is a declaration for the linker, and will be dropped eventually.
 990     // It is illegal for comdats to contain declarations.
 991     auto *GO = dyn_cast_or_null<GlobalObject>(&GV);
 992     if (GO && GO->isDeclarationForLinker() && GO->hasComdat())
 993       GO->setComdat(nullptr);
 994   };
 995
 996   // Process functions and global now
 997   for (auto &GV : TheModule)
 998     updateLinkage(GV);
 999   for (auto &GV : TheModule.globals())
1000     updateLinkage(GV);
1001   for (auto &GV : TheModule.aliases())
1002     updateLinkage(GV);
1003 }
1004
1005 /// Run internalization on \p TheModule based on symmary analysis.
1006 void llvm::thinLTOInternalizeModule(Module &TheModule,
1007                                     const GVSummaryMapTy &DefinedGlobals) {
1008   // Declare a callback for the internalize pass that will ask for every
1009   // candidate GlobalValue if it can be internalized or not.
1010   auto MustPreserveGV = [&](const GlobalValue &GV) -> bool {
1011     // Lookup the linkage recorded in the summaries during global analysis.
1012     auto GS = DefinedGlobals.find(GV.getGUID());
1013     if (GS == DefinedGlobals.end()) {
1014       // Must have been promoted (possibly conservatively). Find original
1015       // name so that we can access the correct summary and see if it can
1016       // be internalized again.
1017       // FIXME: Eventually we should control promotion instead of promoting
1018       // and internalizing again.
1019       StringRef OrigName =
1020           ModuleSummaryIndex::getOriginalNameBeforePromote(GV.getName());
1021       std::string OrigId = GlobalValue::getGlobalIdentifier(
1022           OrigName, GlobalValue::InternalLinkage,
1023           TheModule.getSourceFileName());
1024       GS = DefinedGlobals.find(GlobalValue::getGUID(OrigId));
1025       if (GS == DefinedGlobals.end()) {
1026         // Also check the original non-promoted non-globalized name. In some
1027         // cases a preempted weak value is linked in as a local copy because
1028         // it is referenced by an alias (IRLinker::linkGlobalValueProto).
1029         // In that case, since it was originally not a local value, it was
1030         // recorded in the index using the original name.
1031         // FIXME: This may not be needed once PR27866 is fixed.
1032         GS = DefinedGlobals.find(GlobalValue::getGUID(OrigName));
1033         assert(GS != DefinedGlobals.end());
1034       }
1035     }
1036     return !GlobalValue::isLocalLinkage(GS->second->linkage());
1037   };
1038
1039   // FIXME: See if we can just internalize directly here via linkage changes
1040   // based on the index, rather than invoking internalizeModule.
1041   internalizeModule(TheModule, MustPreserveGV);
1042 }
1043
1044 /// Make alias a clone of its aliasee.
1045 static Function *replaceAliasWithAliasee(Module *SrcModule, GlobalAlias *GA) {
1046   Function *Fn = cast<Function>(GA->getBaseObject());
1047
1048   ValueToValueMapTy VMap;
1049   Function *NewFn = CloneFunction(Fn, VMap);
1050   // Clone should use the original alias's linkage and name, and we ensure
1051   // all uses of alias instead use the new clone (casted if necessary).
1052   NewFn->setLinkage(GA->getLinkage());
1053   GA->replaceAllUsesWith(ConstantExpr::getBitCast(NewFn, GA->getType()));
1054   NewFn->takeName(GA);
1055   return NewFn;
1056 }
1057
1058 // Internalize values that we marked with specific attribute
1059 // in processGlobalForThinLTO.
1060 static void internalizeImmutableGVs(Module &M) {
1061   for (auto &GV : M.globals())
1062     // Skip GVs which have been converted to declarations
1063     // by dropDeadSymbols.
1064     if (!GV.isDeclaration() && GV.hasAttribute("thinlto-internalize")) {
1065       GV.setLinkage(GlobalValue::InternalLinkage);
1066       GV.setVisibility(GlobalValue::DefaultVisibility);
1067     }
1068 }
1069
1070 // Automatically import functions in Module \p DestModule based on the summaries
1071 // index.
1072 Expected<bool> FunctionImporter::importFunctions(
1073     Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) {
1074   LLVM_DEBUG(dbgs() << "Starting import for Module "
1075                     << DestModule.getModuleIdentifier() << "\n");
1076   unsigned ImportedCount = 0, ImportedGVCount = 0;
1077
1078   IRMover Mover(DestModule);
1079   // Do the actual import of functions now, one Module at a time
1080   std::set<StringRef> ModuleNameOrderedList;
1081   for (auto &FunctionsToImportPerModule : ImportList) {
1082     ModuleNameOrderedList.insert(FunctionsToImportPerModule.first());
1083   }
1084   for (auto &Name : ModuleNameOrderedList) {
1085     // Get the module for the import
1086     const auto &FunctionsToImportPerModule = ImportList.find(Name);
1087     assert(FunctionsToImportPerModule != ImportList.end());
1088     Expected<std::unique_ptr<Module>> SrcModuleOrErr = ModuleLoader(Name);
1089     if (!SrcModuleOrErr)
1090       return SrcModuleOrErr.takeError();
1091     std::unique_ptr<Module> SrcModule = std::move(*SrcModuleOrErr);
1092     assert(&DestModule.getContext() == &SrcModule->getContext() &&
1093            "Context mismatch");
1094
1095     // If modules were created with lazy metadata loading, materialize it
1096     // now, before linking it (otherwise this will be a noop).
1097     if (Error Err = SrcModule->materializeMetadata())
1098       return std::move(Err);
1099
1100     auto &ImportGUIDs = FunctionsToImportPerModule->second;
1101     // Find the globals to import
1102     SetVector<GlobalValue *> GlobalsToImport;
1103     for (Function &F : *SrcModule) {
1104       if (!F.hasName())
1105         continue;
1106       auto GUID = F.getGUID();
1107       auto Import = ImportGUIDs.count(GUID);
1108       LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing function "
1109                         << GUID << " " << F.getName() << " from "
1110                         << SrcModule->getSourceFileName() << "\n");
1111       if (Import) {
1112         if (Error Err = F.materialize())
1113           return std::move(Err);
1114         if (EnableImportMetadata) {
1115           // Add 'thinlto_src_module' metadata for statistics and debugging.
1116           F.setMetadata(
1117               "thinlto_src_module",
1118               MDNode::get(DestModule.getContext(),
1119                           {MDString::get(DestModule.getContext(),
1120                                          SrcModule->getSourceFileName())}));
1121         }
1122         GlobalsToImport.insert(&F);
1123       }
1124     }
1125     for (GlobalVariable &GV : SrcModule->globals()) {
1126       if (!GV.hasName())
1127         continue;
1128       auto GUID = GV.getGUID();
1129       auto Import = ImportGUIDs.count(GUID);
1130       LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing global "
1131                         << GUID << " " << GV.getName() << " from "
1132                         << SrcModule->getSourceFileName() << "\n");
1133       if (Import) {
1134         if (Error Err = GV.materialize())
1135           return std::move(Err);
1136         ImportedGVCount += GlobalsToImport.insert(&GV);
1137       }
1138     }
1139     for (GlobalAlias &GA : SrcModule->aliases()) {
1140       if (!GA.hasName())
1141         continue;
1142       auto GUID = GA.getGUID();
1143       auto Import = ImportGUIDs.count(GUID);
1144       LLVM_DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing alias "
1145                         << GUID << " " << GA.getName() << " from "
1146                         << SrcModule->getSourceFileName() << "\n");
1147       if (Import) {
1148         if (Error Err = GA.materialize())
1149           return std::move(Err);
1150         // Import alias as a copy of its aliasee.
1151         GlobalObject *Base = GA.getBaseObject();
1152         if (Error Err = Base->materialize())
1153           return std::move(Err);
1154         auto *Fn = replaceAliasWithAliasee(SrcModule.get(), &GA);
1155         LLVM_DEBUG(dbgs() << "Is importing aliasee fn " << Base->getGUID()
1156                           << " " << Base->getName() << " from "
1157                           << SrcModule->getSourceFileName() << "\n");
1158         if (EnableImportMetadata) {
1159           // Add 'thinlto_src_module' metadata for statistics and debugging.
1160           Fn->setMetadata(
1161               "thinlto_src_module",
1162               MDNode::get(DestModule.getContext(),
1163                           {MDString::get(DestModule.getContext(),
1164                                          SrcModule->getSourceFileName())}));
1165         }
1166         GlobalsToImport.insert(Fn);
1167       }
1168     }
1169
1170     // Upgrade debug info after we're done materializing all the globals and we
1171     // have loaded all the required metadata!
1172     UpgradeDebugInfo(*SrcModule);
1173
1174     // Link in the specified functions.
1175     if (renameModuleForThinLTO(*SrcModule, Index, &GlobalsToImport))
1176       return true;
1177
1178     if (PrintImports) {
1179       for (const auto *GV : GlobalsToImport)
1180         dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName()
1181                << " from " << SrcModule->getSourceFileName() << "\n";
1182     }
1183
1184     if (Mover.move(std::move(SrcModule), GlobalsToImport.getArrayRef(),
1185                    [](GlobalValue &, IRMover::ValueAdder) {},
1186                    /*IsPerformingImport=*/true))
1187       report_fatal_error("Function Import: link error");
1188
1189     ImportedCount += GlobalsToImport.size();
1190     NumImportedModules++;
1191   }
1192
1193   internalizeImmutableGVs(DestModule);
1194
1195   NumImportedFunctions += (ImportedCount - ImportedGVCount);
1196   NumImportedGlobalVars += ImportedGVCount;
1197
1198   LLVM_DEBUG(dbgs() << "Imported " << ImportedCount - ImportedGVCount
1199                     << " functions for Module "
1200                     << DestModule.getModuleIdentifier() << "\n");
1201   LLVM_DEBUG(dbgs() << "Imported " << ImportedGVCount
1202                     << " global variables for Module "
1203                     << DestModule.getModuleIdentifier() << "\n");
1204   return ImportedCount;
1205 }
1206
1207 static bool doImportingForModule(Module &M) {
1208   if (SummaryFile.empty())
1209     report_fatal_error("error: -function-import requires -summary-file\n");
1210   Expected<std::unique_ptr<ModuleSummaryIndex>> IndexPtrOrErr =
1211       getModuleSummaryIndexForFile(SummaryFile);
1212   if (!IndexPtrOrErr) {
1213     logAllUnhandledErrors(IndexPtrOrErr.takeError(), errs(),
1214                           "Error loading file '" + SummaryFile + "': ");
1215     return false;
1216   }
1217   std::unique_ptr<ModuleSummaryIndex> Index = std::move(*IndexPtrOrErr);
1218
1219   // First step is collecting the import list.
1220   FunctionImporter::ImportMapTy ImportList;
1221   // If requested, simply import all functions in the index. This is used
1222   // when testing distributed backend handling via the opt tool, when
1223   // we have distributed indexes containing exactly the summaries to import.
1224   if (ImportAllIndex)
1225     ComputeCrossModuleImportForModuleFromIndex(M.getModuleIdentifier(), *Index,
1226                                                ImportList);
1227   else
1228     ComputeCrossModuleImportForModule(M.getModuleIdentifier(), *Index,
1229                                       ImportList);
1230
1231   // Conservatively mark all internal values as promoted. This interface is
1232   // only used when doing importing via the function importing pass. The pass
1233   // is only enabled when testing importing via the 'opt' tool, which does
1234   // not do the ThinLink that would normally determine what values to promote.
1235   for (auto &I : *Index) {
1236     for (auto &S : I.second.SummaryList) {
1237       if (GlobalValue::isLocalLinkage(S->linkage()))
1238         S->setLinkage(GlobalValue::ExternalLinkage);
1239     }
1240   }
1241
1242   // Next we need to promote to global scope and rename any local values that
1243   // are potentially exported to other modules.
1244   if (renameModuleForThinLTO(M, *Index, nullptr)) {
1245     errs() << "Error renaming module\n";
1246     return false;
1247   }
1248
1249   // Perform the import now.
1250   auto ModuleLoader = [&M](StringRef Identifier) {
1251     return loadFile(Identifier, M.getContext());
1252   };
1253   FunctionImporter Importer(*Index, ModuleLoader);
1254   Expected<bool> Result = Importer.importFunctions(M, ImportList);
1255
1256   // FIXME: Probably need to propagate Errors through the pass manager.
1257   if (!Result) {
1258     logAllUnhandledErrors(Result.takeError(), errs(),
1259                           "Error importing module: ");
1260     return false;
1261   }
1262
1263   return *Result;
1264 }
1265
1266 namespace {
1267
1268 /// Pass that performs cross-module function import provided a summary file.
1269 class FunctionImportLegacyPass : public ModulePass {
1270 public:
1271   /// Pass identification, replacement for typeid
1272   static char ID;
1273
1274   explicit FunctionImportLegacyPass() : ModulePass(ID) {}
1275
1276   /// Specify pass name for debug output
1277   StringRef getPassName() const override { return "Function Importing"; }
1278
1279   bool runOnModule(Module &M) override {
1280     if (skipModule(M))
1281       return false;
1282
1283     return doImportingForModule(M);
1284   }
1285 };
1286
1287 } // end anonymous namespace
1288
1289 PreservedAnalyses FunctionImportPass::run(Module &M,
1290                                           ModuleAnalysisManager &AM) {
1291   if (!doImportingForModule(M))
1292     return PreservedAnalyses::all();
1293
1294   return PreservedAnalyses::none();
1295 }
1296
1297 char FunctionImportLegacyPass::ID = 0;
1298 INITIALIZE_PASS(FunctionImportLegacyPass, "function-import",
1299                 "Summary Based Function Import", false, false)
1300
1301 namespace llvm {
1302
1303 Pass *createFunctionImportPass() {
1304   return new FunctionImportLegacyPass();
1305 }
1306
1307 } // end namespace llvm