lib/LTO/ThinLTOCodeGenerator.cpp

   1 //===-ThinLTOCodeGenerator.cpp - LLVM Link Time Optimizer -----------------===//
   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 the Thin Link Time Optimization library. This library is
  11 // intended to be used by linker to optimize code at link time.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/LTO/legacy/ThinLTOCodeGenerator.h"
  16
  17 #ifdef HAVE_LLVM_REVISION
  18 #include "LLVMLTORevision.h"
  19 #endif
  20
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/ADT/StringExtras.h"
  23 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
  24 #include "llvm/Analysis/ProfileSummaryInfo.h"
  25 #include "llvm/Analysis/TargetLibraryInfo.h"
  26 #include "llvm/Analysis/TargetTransformInfo.h"
  27 #include "llvm/Bitcode/BitcodeReader.h"
  28 #include "llvm/Bitcode/BitcodeWriter.h"
  29 #include "llvm/Bitcode/BitcodeWriterPass.h"
  30 #include "llvm/ExecutionEngine/ObjectMemoryBuffer.h"
  31 #include "llvm/IR/DiagnosticPrinter.h"
  32 #include "llvm/IR/LLVMContext.h"
  33 #include "llvm/IR/LegacyPassManager.h"
  34 #include "llvm/IR/Mangler.h"
  35 #include "llvm/IRReader/IRReader.h"
  36 #include "llvm/LTO/LTO.h"
  37 #include "llvm/Linker/Linker.h"
  38 #include "llvm/MC/SubtargetFeature.h"
  39 #include "llvm/Object/IRObjectFile.h"
  40 #include "llvm/Object/ModuleSummaryIndexObjectFile.h"
  41 #include "llvm/Support/CachePruning.h"
  42 #include "llvm/Support/Debug.h"
  43 #include "llvm/Support/Path.h"
  44 #include "llvm/Support/SHA1.h"
  45 #include "llvm/Support/TargetRegistry.h"
  46 #include "llvm/Support/ThreadPool.h"
  47 #include "llvm/Support/Threading.h"
  48 #include "llvm/Target/TargetMachine.h"
  49 #include "llvm/Transforms/IPO.h"
  50 #include "llvm/Transforms/IPO/FunctionImport.h"
  51 #include "llvm/Transforms/IPO/Internalize.h"
  52 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
  53 #include "llvm/Transforms/ObjCARC.h"
  54 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
  55
  56 #include <numeric>
  57
  58 using namespace llvm;
  59
  60 #define DEBUG_TYPE "thinlto"
  61
  62 namespace llvm {
  63 // Flags -discard-value-names, defined in LTOCodeGenerator.cpp
  64 extern cl::opt<bool> LTODiscardValueNames;
  65 }
  66
  67 namespace {
  68
  69 static cl::opt<int>
  70     ThreadCount("threads", cl::init(llvm::heavyweight_hardware_concurrency()));
  71
  72 // Simple helper to save temporary files for debug.
  73 static void saveTempBitcode(const Module &TheModule, StringRef TempDir,
  74                             unsigned count, StringRef Suffix) {
  75   if (TempDir.empty())
  76     return;
  77   // User asked to save temps, let dump the bitcode file after import.
  78   std::string SaveTempPath = (TempDir + llvm::utostr(count) + Suffix).str();
  79   std::error_code EC;
  80   raw_fd_ostream OS(SaveTempPath, EC, sys::fs::F_None);
  81   if (EC)
  82     report_fatal_error(Twine("Failed to open ") + SaveTempPath +
  83                        " to save optimized bitcode\n");
  84   WriteBitcodeToFile(&TheModule, OS, /* ShouldPreserveUseListOrder */ true);
  85 }
  86
  87 static const GlobalValueSummary *
  88 getFirstDefinitionForLinker(const GlobalValueSummaryList &GVSummaryList) {
  89   // If there is any strong definition anywhere, get it.
  90   auto StrongDefForLinker = llvm::find_if(
  91       GVSummaryList, [](const std::unique_ptr<GlobalValueSummary> &Summary) {
  92         auto Linkage = Summary->linkage();
  93         return !GlobalValue::isAvailableExternallyLinkage(Linkage) &&
  94                !GlobalValue::isWeakForLinker(Linkage);
  95       });
  96   if (StrongDefForLinker != GVSummaryList.end())
  97     return StrongDefForLinker->get();
  98   // Get the first *linker visible* definition for this global in the summary
  99   // list.
 100   auto FirstDefForLinker = llvm::find_if(
 101       GVSummaryList, [](const std::unique_ptr<GlobalValueSummary> &Summary) {
 102         auto Linkage = Summary->linkage();
 103         return !GlobalValue::isAvailableExternallyLinkage(Linkage);
 104       });
 105   // Extern templates can be emitted as available_externally.
 106   if (FirstDefForLinker == GVSummaryList.end())
 107     return nullptr;
 108   return FirstDefForLinker->get();
 109 }
 110
 111 // Populate map of GUID to the prevailing copy for any multiply defined
 112 // symbols. Currently assume first copy is prevailing, or any strong
 113 // definition. Can be refined with Linker information in the future.
 114 static void computePrevailingCopies(
 115     const ModuleSummaryIndex &Index,
 116     DenseMap<GlobalValue::GUID, const GlobalValueSummary *> &PrevailingCopy) {
 117   auto HasMultipleCopies = [&](const GlobalValueSummaryList &GVSummaryList) {
 118     return GVSummaryList.size() > 1;
 119   };
 120
 121   for (auto &I : Index) {
 122     if (HasMultipleCopies(I.second))
 123       PrevailingCopy[I.first] = getFirstDefinitionForLinker(I.second);
 124   }
 125 }
 126
 127 static StringMap<MemoryBufferRef>
 128 generateModuleMap(const std::vector<MemoryBufferRef> &Modules) {
 129   StringMap<MemoryBufferRef> ModuleMap;
 130   for (auto &ModuleBuffer : Modules) {
 131     assert(ModuleMap.find(ModuleBuffer.getBufferIdentifier()) ==
 132                ModuleMap.end() &&
 133            "Expect unique Buffer Identifier");
 134     ModuleMap[ModuleBuffer.getBufferIdentifier()] = ModuleBuffer;
 135   }
 136   return ModuleMap;
 137 }
 138
 139 static void promoteModule(Module &TheModule, const ModuleSummaryIndex &Index) {
 140   if (renameModuleForThinLTO(TheModule, Index))
 141     report_fatal_error("renameModuleForThinLTO failed");
 142 }
 143
 144 static void
 145 crossImportIntoModule(Module &TheModule, const ModuleSummaryIndex &Index,
 146                       StringMap<MemoryBufferRef> &ModuleMap,
 147                       const FunctionImporter::ImportMapTy &ImportList) {
 148   ModuleLoader Loader(TheModule.getContext(), ModuleMap);
 149   FunctionImporter Importer(Index, Loader);
 150   if (!Importer.importFunctions(TheModule, ImportList))
 151     report_fatal_error("importFunctions failed");
 152 }
 153
 154 static void optimizeModule(Module &TheModule, TargetMachine &TM) {
 155   // Populate the PassManager
 156   PassManagerBuilder PMB;
 157   PMB.LibraryInfo = new TargetLibraryInfoImpl(TM.getTargetTriple());
 158   PMB.Inliner = createFunctionInliningPass();
 159   // FIXME: should get it from the bitcode?
 160   PMB.OptLevel = 3;
 161   PMB.LoopVectorize = true;
 162   PMB.SLPVectorize = true;
 163   PMB.VerifyInput = true;
 164   PMB.VerifyOutput = false;
 165
 166   legacy::PassManager PM;
 167
 168   // Add the TTI (required to inform the vectorizer about register size for
 169   // instance)
 170   PM.add(createTargetTransformInfoWrapperPass(TM.getTargetIRAnalysis()));
 171
 172   // Add optimizations
 173   PMB.populateThinLTOPassManager(PM);
 174
 175   PM.run(TheModule);
 176 }
 177
 178 // Convert the PreservedSymbols map from "Name" based to "GUID" based.
 179 static DenseSet<GlobalValue::GUID>
 180 computeGUIDPreservedSymbols(const StringSet<> &PreservedSymbols,
 181                             const Triple &TheTriple) {
 182   DenseSet<GlobalValue::GUID> GUIDPreservedSymbols(PreservedSymbols.size());
 183   for (auto &Entry : PreservedSymbols) {
 184     StringRef Name = Entry.first();
 185     if (TheTriple.isOSBinFormatMachO() && Name.size() > 0 && Name[0] == '_')
 186       Name = Name.drop_front();
 187     GUIDPreservedSymbols.insert(GlobalValue::getGUID(Name));
 188   }
 189   return GUIDPreservedSymbols;
 190 }
 191
 192 std::unique_ptr<MemoryBuffer> codegenModule(Module &TheModule,
 193                                             TargetMachine &TM) {
 194   SmallVector<char, 128> OutputBuffer;
 195
 196   // CodeGen
 197   {
 198     raw_svector_ostream OS(OutputBuffer);
 199     legacy::PassManager PM;
 200
 201     // If the bitcode files contain ARC code and were compiled with optimization,
 202     // the ObjCARCContractPass must be run, so do it unconditionally here.
 203     PM.add(createObjCARCContractPass());
 204
 205     // Setup the codegen now.
 206     if (TM.addPassesToEmitFile(PM, OS, TargetMachine::CGFT_ObjectFile,
 207                                /* DisableVerify */ true))
 208       report_fatal_error("Failed to setup codegen");
 209
 210     // Run codegen now. resulting binary is in OutputBuffer.
 211     PM.run(TheModule);
 212   }
 213   return make_unique<ObjectMemoryBuffer>(std::move(OutputBuffer));
 214 }
 215
 216 /// Manage caching for a single Module.
 217 class ModuleCacheEntry {
 218   SmallString<128> EntryPath;
 219
 220 public:
 221   // Create a cache entry. This compute a unique hash for the Module considering
 222   // the current list of export/import, and offer an interface to query to
 223   // access the content in the cache.
 224   ModuleCacheEntry(
 225       StringRef CachePath, const ModuleSummaryIndex &Index, StringRef ModuleID,
 226       const FunctionImporter::ImportMapTy &ImportList,
 227       const FunctionImporter::ExportSetTy &ExportList,
 228       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
 229       const GVSummaryMapTy &DefinedFunctions,
 230       const DenseSet<GlobalValue::GUID> &PreservedSymbols) {
 231     if (CachePath.empty())
 232       return;
 233
 234     if (!Index.modulePaths().count(ModuleID))
 235       // The module does not have an entry, it can't have a hash at all
 236       return;
 237
 238     // Compute the unique hash for this entry
 239     // This is based on the current compiler version, the module itself, the
 240     // export list, the hash for every single module in the import list, the
 241     // list of ResolvedODR for the module, and the list of preserved symbols.
 242
 243     // Include the hash for the current module
 244     auto ModHash = Index.getModuleHash(ModuleID);
 245
 246     if (all_of(ModHash, [](uint32_t V) { return V == 0; }))
 247       // No hash entry, no caching!
 248       return;
 249
 250     SHA1 Hasher;
 251
 252     // Start with the compiler revision
 253     Hasher.update(LLVM_VERSION_STRING);
 254 #ifdef HAVE_LLVM_REVISION
 255     Hasher.update(LLVM_REVISION);
 256 #endif
 257
 258     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
 259     for (auto F : ExportList)
 260       // The export list can impact the internalization, be conservative here
 261       Hasher.update(ArrayRef<uint8_t>((uint8_t *)&F, sizeof(F)));
 262
 263     // Include the hash for every module we import functions from
 264     for (auto &Entry : ImportList) {
 265       auto ModHash = Index.getModuleHash(Entry.first());
 266       Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
 267     }
 268
 269     // Include the hash for the resolved ODR.
 270     for (auto &Entry : ResolvedODR) {
 271       Hasher.update(ArrayRef<uint8_t>((const uint8_t *)&Entry.first,
 272                                       sizeof(GlobalValue::GUID)));
 273       Hasher.update(ArrayRef<uint8_t>((const uint8_t *)&Entry.second,
 274                                       sizeof(GlobalValue::LinkageTypes)));
 275     }
 276
 277     // Include the hash for the preserved symbols.
 278     for (auto &Entry : PreservedSymbols) {
 279       if (DefinedFunctions.count(Entry))
 280         Hasher.update(
 281             ArrayRef<uint8_t>((const uint8_t *)&Entry, sizeof(GlobalValue::GUID)));
 282     }
 283
 284     sys::path::append(EntryPath, CachePath, toHex(Hasher.result()));
 285   }
 286
 287   // Access the path to this entry in the cache.
 288   StringRef getEntryPath() { return EntryPath; }
 289
 290   // Try loading the buffer for this cache entry.
 291   ErrorOr<std::unique_ptr<MemoryBuffer>> tryLoadingBuffer() {
 292     if (EntryPath.empty())
 293       return std::error_code();
 294     return MemoryBuffer::getFile(EntryPath);
 295   }
 296
 297   // Cache the Produced object file
 298   std::unique_ptr<MemoryBuffer>
 299   write(std::unique_ptr<MemoryBuffer> OutputBuffer) {
 300     if (EntryPath.empty())
 301       return OutputBuffer;
 302
 303     // Write to a temporary to avoid race condition
 304     SmallString<128> TempFilename;
 305     int TempFD;
 306     std::error_code EC =
 307         sys::fs::createTemporaryFile("Thin", "tmp.o", TempFD, TempFilename);
 308     if (EC) {
 309       errs() << "Error: " << EC.message() << "\n";
 310       report_fatal_error("ThinLTO: Can't get a temporary file");
 311     }
 312     {
 313       raw_fd_ostream OS(TempFD, /* ShouldClose */ true);
 314       OS << OutputBuffer->getBuffer();
 315     }
 316     // Rename to final destination (hopefully race condition won't matter here)
 317     EC = sys::fs::rename(TempFilename, EntryPath);
 318     if (EC) {
 319       sys::fs::remove(TempFilename);
 320       raw_fd_ostream OS(EntryPath, EC, sys::fs::F_None);
 321       if (EC)
 322         report_fatal_error(Twine("Failed to open ") + EntryPath +
 323                            " to save cached entry\n");
 324       OS << OutputBuffer->getBuffer();
 325     }
 326     auto ReloadedBufferOrErr = MemoryBuffer::getFile(EntryPath);
 327     if (auto EC = ReloadedBufferOrErr.getError()) {
 328       // FIXME diagnose
 329       errs() << "error: can't reload cached file '" << EntryPath
 330              << "': " << EC.message() << "\n";
 331       return OutputBuffer;
 332     }
 333     return std::move(*ReloadedBufferOrErr);
 334   }
 335 };
 336
 337 static std::unique_ptr<MemoryBuffer>
 338 ProcessThinLTOModule(Module &TheModule, ModuleSummaryIndex &Index,
 339                      StringMap<MemoryBufferRef> &ModuleMap, TargetMachine &TM,
 340                      const FunctionImporter::ImportMapTy &ImportList,
 341                      const FunctionImporter::ExportSetTy &ExportList,
 342                      const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
 343                      const GVSummaryMapTy &DefinedGlobals,
 344                      const ThinLTOCodeGenerator::CachingOptions &CacheOptions,
 345                      bool DisableCodeGen, StringRef SaveTempsDir,
 346                      unsigned count) {
 347
 348   // "Benchmark"-like optimization: single-source case
 349   bool SingleModule = (ModuleMap.size() == 1);
 350
 351   if (!SingleModule) {
 352     promoteModule(TheModule, Index);
 353
 354     // Apply summary-based LinkOnce/Weak resolution decisions.
 355     thinLTOResolveWeakForLinkerModule(TheModule, DefinedGlobals);
 356
 357     // Save temps: after promotion.
 358     saveTempBitcode(TheModule, SaveTempsDir, count, ".1.promoted.bc");
 359   }
 360
 361   // Be friendly and don't nuke totally the module when the client didn't
 362   // supply anything to preserve.
 363   if (!ExportList.empty() || !GUIDPreservedSymbols.empty()) {
 364     // Apply summary-based internalization decisions.
 365     thinLTOInternalizeModule(TheModule, DefinedGlobals);
 366   }
 367
 368   // Save internalized bitcode
 369   saveTempBitcode(TheModule, SaveTempsDir, count, ".2.internalized.bc");
 370
 371   if (!SingleModule) {
 372     crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
 373
 374     // Save temps: after cross-module import.
 375     saveTempBitcode(TheModule, SaveTempsDir, count, ".3.imported.bc");
 376   }
 377
 378   optimizeModule(TheModule, TM);
 379
 380   saveTempBitcode(TheModule, SaveTempsDir, count, ".4.opt.bc");
 381
 382   if (DisableCodeGen) {
 383     // Configured to stop before CodeGen, serialize the bitcode and return.
 384     SmallVector<char, 128> OutputBuffer;
 385     {
 386       raw_svector_ostream OS(OutputBuffer);
 387       ProfileSummaryInfo PSI(TheModule);
 388       auto Index = buildModuleSummaryIndex(TheModule, nullptr, nullptr);
 389       WriteBitcodeToFile(&TheModule, OS, true, &Index);
 390     }
 391     return make_unique<ObjectMemoryBuffer>(std::move(OutputBuffer));
 392   }
 393
 394   return codegenModule(TheModule, TM);
 395 }
 396
 397 /// Resolve LinkOnce/Weak symbols. Record resolutions in the \p ResolvedODR map
 398 /// for caching, and in the \p Index for application during the ThinLTO
 399 /// backends. This is needed for correctness for exported symbols (ensure
 400 /// at least one copy kept) and a compile-time optimization (to drop duplicate
 401 /// copies when possible).
 402 static void resolveWeakForLinkerInIndex(
 403     ModuleSummaryIndex &Index,
 404     StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>>
 405         &ResolvedODR) {
 406
 407   DenseMap<GlobalValue::GUID, const GlobalValueSummary *> PrevailingCopy;
 408   computePrevailingCopies(Index, PrevailingCopy);
 409
 410   auto isPrevailing = [&](GlobalValue::GUID GUID, const GlobalValueSummary *S) {
 411     const auto &Prevailing = PrevailingCopy.find(GUID);
 412     // Not in map means that there was only one copy, which must be prevailing.
 413     if (Prevailing == PrevailingCopy.end())
 414       return true;
 415     return Prevailing->second == S;
 416   };
 417
 418   auto recordNewLinkage = [&](StringRef ModuleIdentifier,
 419                               GlobalValue::GUID GUID,
 420                               GlobalValue::LinkageTypes NewLinkage) {
 421     ResolvedODR[ModuleIdentifier][GUID] = NewLinkage;
 422   };
 423
 424   thinLTOResolveWeakForLinkerInIndex(Index, isPrevailing, recordNewLinkage);
 425 }
 426
 427 // Initialize the TargetMachine builder for a given Triple
 428 static void initTMBuilder(TargetMachineBuilder &TMBuilder,
 429                           const Triple &TheTriple) {
 430   // Set a default CPU for Darwin triples (copied from LTOCodeGenerator).
 431   // FIXME this looks pretty terrible...
 432   if (TMBuilder.MCpu.empty() && TheTriple.isOSDarwin()) {
 433     if (TheTriple.getArch() == llvm::Triple::x86_64)
 434       TMBuilder.MCpu = "core2";
 435     else if (TheTriple.getArch() == llvm::Triple::x86)
 436       TMBuilder.MCpu = "yonah";
 437     else if (TheTriple.getArch() == llvm::Triple::aarch64)
 438       TMBuilder.MCpu = "cyclone";
 439   }
 440   TMBuilder.TheTriple = std::move(TheTriple);
 441 }
 442
 443 } // end anonymous namespace
 444
 445 void ThinLTOCodeGenerator::addModule(StringRef Identifier, StringRef Data) {
 446   MemoryBufferRef Buffer(Data, Identifier);
 447   if (Modules.empty()) {
 448     // First module added, so initialize the triple and some options
 449     LLVMContext Context;
 450     StringRef TripleStr;
 451     ErrorOr<std::string> TripleOrErr =
 452         expectedToErrorOrAndEmitErrors(Context, getBitcodeTargetTriple(Buffer));
 453     if (TripleOrErr)
 454       TripleStr = *TripleOrErr;
 455     Triple TheTriple(TripleStr);
 456     initTMBuilder(TMBuilder, Triple(TheTriple));
 457   }
 458 #ifndef NDEBUG
 459   else {
 460     LLVMContext Context;
 461     StringRef TripleStr;
 462     ErrorOr<std::string> TripleOrErr =
 463         expectedToErrorOrAndEmitErrors(Context, getBitcodeTargetTriple(Buffer));
 464     if (TripleOrErr)
 465       TripleStr = *TripleOrErr;
 466     assert(TMBuilder.TheTriple.str() == TripleStr &&
 467            "ThinLTO modules with different triple not supported");
 468   }
 469 #endif
 470   Modules.push_back(Buffer);
 471 }
 472
 473 void ThinLTOCodeGenerator::preserveSymbol(StringRef Name) {
 474   PreservedSymbols.insert(Name);
 475 }
 476
 477 void ThinLTOCodeGenerator::crossReferenceSymbol(StringRef Name) {
 478   // FIXME: At the moment, we don't take advantage of this extra information,
 479   // we're conservatively considering cross-references as preserved.
 480   //  CrossReferencedSymbols.insert(Name);
 481   PreservedSymbols.insert(Name);
 482 }
 483
 484 // TargetMachine factory
 485 std::unique_ptr<TargetMachine> TargetMachineBuilder::create() const {
 486   std::string ErrMsg;
 487   const Target *TheTarget =
 488       TargetRegistry::lookupTarget(TheTriple.str(), ErrMsg);
 489   if (!TheTarget) {
 490     report_fatal_error("Can't load target for this Triple: " + ErrMsg);
 491   }
 492
 493   // Use MAttr as the default set of features.
 494   SubtargetFeatures Features(MAttr);
 495   Features.getDefaultSubtargetFeatures(TheTriple);
 496   std::string FeatureStr = Features.getString();
 497   return std::unique_ptr<TargetMachine>(TheTarget->createTargetMachine(
 498       TheTriple.str(), MCpu, FeatureStr, Options, RelocModel,
 499       CodeModel::Default, CGOptLevel));
 500 }
 501
 502 /**
 503  * Produce the combined summary index from all the bitcode files:
 504  * "thin-link".
 505  */
 506 std::unique_ptr<ModuleSummaryIndex> ThinLTOCodeGenerator::linkCombinedIndex() {
 507   std::unique_ptr<ModuleSummaryIndex> CombinedIndex;
 508   uint64_t NextModuleId = 0;
 509   for (auto &ModuleBuffer : Modules) {
 510     Expected<std::unique_ptr<object::ModuleSummaryIndexObjectFile>> ObjOrErr =
 511         object::ModuleSummaryIndexObjectFile::create(ModuleBuffer);
 512     if (!ObjOrErr) {
 513       // FIXME diagnose
 514       logAllUnhandledErrors(
 515           ObjOrErr.takeError(), errs(),
 516           "error: can't create ModuleSummaryIndexObjectFile for buffer: ");
 517       return nullptr;
 518     }
 519     auto Index = (*ObjOrErr)->takeIndex();
 520     if (CombinedIndex) {
 521       CombinedIndex->mergeFrom(std::move(Index), ++NextModuleId);
 522     } else {
 523       CombinedIndex = std::move(Index);
 524     }
 525   }
 526   return CombinedIndex;
 527 }
 528
 529 /**
 530  * Perform promotion and renaming of exported internal functions.
 531  * Index is updated to reflect linkage changes from weak resolution.
 532  */
 533 void ThinLTOCodeGenerator::promote(Module &TheModule,
 534                                    ModuleSummaryIndex &Index) {
 535   auto ModuleCount = Index.modulePaths().size();
 536   auto ModuleIdentifier = TheModule.getModuleIdentifier();
 537
 538   // Collect for each module the list of function it defines (GUID -> Summary).
 539   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries;
 540   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 541
 542   // Generate import/export list
 543   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
 544   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
 545   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
 546                            ExportLists);
 547
 548   // Resolve LinkOnce/Weak symbols.
 549   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
 550   resolveWeakForLinkerInIndex(Index, ResolvedODR);
 551
 552   thinLTOResolveWeakForLinkerModule(
 553       TheModule, ModuleToDefinedGVSummaries[ModuleIdentifier]);
 554
 555   // Convert the preserved symbols set from string to GUID
 556   auto GUIDPreservedSymbols = computeGUIDPreservedSymbols(
 557       PreservedSymbols, Triple(TheModule.getTargetTriple()));
 558
 559   // Promote the exported values in the index, so that they are promoted
 560   // in the module.
 561   auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) {
 562     const auto &ExportList = ExportLists.find(ModuleIdentifier);
 563     return (ExportList != ExportLists.end() &&
 564             ExportList->second.count(GUID)) ||
 565            GUIDPreservedSymbols.count(GUID);
 566   };
 567   thinLTOInternalizeAndPromoteInIndex(Index, isExported);
 568
 569   promoteModule(TheModule, Index);
 570 }
 571
 572 /**
 573  * Perform cross-module importing for the module identified by ModuleIdentifier.
 574  */
 575 void ThinLTOCodeGenerator::crossModuleImport(Module &TheModule,
 576                                              ModuleSummaryIndex &Index) {
 577   auto ModuleMap = generateModuleMap(Modules);
 578   auto ModuleCount = Index.modulePaths().size();
 579
 580   // Collect for each module the list of function it defines (GUID -> Summary).
 581   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
 582   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 583
 584   // Generate import/export list
 585   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
 586   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
 587   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
 588                            ExportLists);
 589   auto &ImportList = ImportLists[TheModule.getModuleIdentifier()];
 590
 591   crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
 592 }
 593
 594 /**
 595  * Compute the list of summaries needed for importing into module.
 596  */
 597 void ThinLTOCodeGenerator::gatherImportedSummariesForModule(
 598     StringRef ModulePath, ModuleSummaryIndex &Index,
 599     std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
 600   auto ModuleCount = Index.modulePaths().size();
 601
 602   // Collect for each module the list of function it defines (GUID -> Summary).
 603   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
 604   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 605
 606   // Generate import/export list
 607   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
 608   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
 609   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
 610                            ExportLists);
 611
 612   llvm::gatherImportedSummariesForModule(ModulePath, ModuleToDefinedGVSummaries,
 613                                          ImportLists[ModulePath],
 614                                          ModuleToSummariesForIndex);
 615 }
 616
 617 /**
 618  * Emit the list of files needed for importing into module.
 619  */
 620 void ThinLTOCodeGenerator::emitImports(StringRef ModulePath,
 621                                        StringRef OutputName,
 622                                        ModuleSummaryIndex &Index) {
 623   auto ModuleCount = Index.modulePaths().size();
 624
 625   // Collect for each module the list of function it defines (GUID -> Summary).
 626   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
 627   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 628
 629   // Generate import/export list
 630   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
 631   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
 632   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
 633                            ExportLists);
 634
 635   std::error_code EC;
 636   if ((EC = EmitImportsFiles(ModulePath, OutputName, ImportLists[ModulePath])))
 637     report_fatal_error(Twine("Failed to open ") + OutputName +
 638                        " to save imports lists\n");
 639 }
 640
 641 /**
 642  * Perform internalization. Index is updated to reflect linkage changes.
 643  */
 644 void ThinLTOCodeGenerator::internalize(Module &TheModule,
 645                                        ModuleSummaryIndex &Index) {
 646   initTMBuilder(TMBuilder, Triple(TheModule.getTargetTriple()));
 647   auto ModuleCount = Index.modulePaths().size();
 648   auto ModuleIdentifier = TheModule.getModuleIdentifier();
 649
 650   // Convert the preserved symbols set from string to GUID
 651   auto GUIDPreservedSymbols =
 652       computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple);
 653
 654   // Collect for each module the list of function it defines (GUID -> Summary).
 655   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
 656   Index.collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 657
 658   // Generate import/export list
 659   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
 660   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
 661   ComputeCrossModuleImport(Index, ModuleToDefinedGVSummaries, ImportLists,
 662                            ExportLists);
 663   auto &ExportList = ExportLists[ModuleIdentifier];
 664
 665   // Be friendly and don't nuke totally the module when the client didn't
 666   // supply anything to preserve.
 667   if (ExportList.empty() && GUIDPreservedSymbols.empty())
 668     return;
 669
 670   // Internalization
 671   auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) {
 672     const auto &ExportList = ExportLists.find(ModuleIdentifier);
 673     return (ExportList != ExportLists.end() &&
 674             ExportList->second.count(GUID)) ||
 675            GUIDPreservedSymbols.count(GUID);
 676   };
 677   thinLTOInternalizeAndPromoteInIndex(Index, isExported);
 678   thinLTOInternalizeModule(TheModule,
 679                            ModuleToDefinedGVSummaries[ModuleIdentifier]);
 680 }
 681
 682 /**
 683  * Perform post-importing ThinLTO optimizations.
 684  */
 685 void ThinLTOCodeGenerator::optimize(Module &TheModule) {
 686   initTMBuilder(TMBuilder, Triple(TheModule.getTargetTriple()));
 687
 688   // Optimize now
 689   optimizeModule(TheModule, *TMBuilder.create());
 690 }
 691
 692 /**
 693  * Perform ThinLTO CodeGen.
 694  */
 695 std::unique_ptr<MemoryBuffer> ThinLTOCodeGenerator::codegen(Module &TheModule) {
 696   initTMBuilder(TMBuilder, Triple(TheModule.getTargetTriple()));
 697   return codegenModule(TheModule, *TMBuilder.create());
 698 }
 699
 700 // Main entry point for the ThinLTO processing
 701 void ThinLTOCodeGenerator::run() {
 702   if (CodeGenOnly) {
 703     // Perform only parallel codegen and return.
 704     ThreadPool Pool;
 705     assert(ProducedBinaries.empty() && "The generator should not be reused");
 706     ProducedBinaries.resize(Modules.size());
 707     int count = 0;
 708     for (auto &ModuleBuffer : Modules) {
 709       Pool.async([&](int count) {
 710         LLVMContext Context;
 711         Context.setDiscardValueNames(LTODiscardValueNames);
 712
 713         // Parse module now
 714         auto TheModule = loadModuleFromBuffer(ModuleBuffer, Context, false);
 715
 716         // CodeGen
 717         ProducedBinaries[count] = codegen(*TheModule);
 718       }, count++);
 719     }
 720
 721     return;
 722   }
 723
 724   // Sequential linking phase
 725   auto Index = linkCombinedIndex();
 726
 727   // Save temps: index.
 728   if (!SaveTempsDir.empty()) {
 729     auto SaveTempPath = SaveTempsDir + "index.bc";
 730     std::error_code EC;
 731     raw_fd_ostream OS(SaveTempPath, EC, sys::fs::F_None);
 732     if (EC)
 733       report_fatal_error(Twine("Failed to open ") + SaveTempPath +
 734                          " to save optimized bitcode\n");
 735     WriteIndexToFile(*Index, OS);
 736   }
 737
 738   // Prepare the resulting object vector
 739   assert(ProducedBinaries.empty() && "The generator should not be reused");
 740   ProducedBinaries.resize(Modules.size());
 741
 742   // Prepare the module map.
 743   auto ModuleMap = generateModuleMap(Modules);
 744   auto ModuleCount = Modules.size();
 745
 746   // Collect for each module the list of function it defines (GUID -> Summary).
 747   StringMap<GVSummaryMapTy> ModuleToDefinedGVSummaries(ModuleCount);
 748   Index->collectDefinedGVSummariesPerModule(ModuleToDefinedGVSummaries);
 749
 750   // Collect the import/export lists for all modules from the call-graph in the
 751   // combined index.
 752   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
 753   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
 754   ComputeCrossModuleImport(*Index, ModuleToDefinedGVSummaries, ImportLists,
 755                            ExportLists);
 756
 757   // Convert the preserved symbols set from string to GUID, this is needed for
 758   // computing the caching hash and the internalization.
 759   auto GUIDPreservedSymbols =
 760       computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple);
 761
 762   // We use a std::map here to be able to have a defined ordering when
 763   // producing a hash for the cache entry.
 764   // FIXME: we should be able to compute the caching hash for the entry based
 765   // on the index, and nuke this map.
 766   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
 767
 768   // Resolve LinkOnce/Weak symbols, this has to be computed early because it
 769   // impacts the caching.
 770   resolveWeakForLinkerInIndex(*Index, ResolvedODR);
 771
 772   auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) {
 773     const auto &ExportList = ExportLists.find(ModuleIdentifier);
 774     return (ExportList != ExportLists.end() &&
 775             ExportList->second.count(GUID)) ||
 776            GUIDPreservedSymbols.count(GUID);
 777   };
 778
 779   // Use global summary-based analysis to identify symbols that can be
 780   // internalized (because they aren't exported or preserved as per callback).
 781   // Changes are made in the index, consumed in the ThinLTO backends.
 782   thinLTOInternalizeAndPromoteInIndex(*Index, isExported);
 783
 784   // Make sure that every module has an entry in the ExportLists and
 785   // ResolvedODR maps to enable threaded access to these maps below.
 786   for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) {
 787     ExportLists[DefinedGVSummaries.first()];
 788     ResolvedODR[DefinedGVSummaries.first()];
 789   }
 790
 791   // Compute the ordering we will process the inputs: the rough heuristic here
 792   // is to sort them per size so that the largest module get schedule as soon as
 793   // possible. This is purely a compile-time optimization.
 794   std::vector<int> ModulesOrdering;
 795   ModulesOrdering.resize(Modules.size());
 796   std::iota(ModulesOrdering.begin(), ModulesOrdering.end(), 0);
 797   std::sort(ModulesOrdering.begin(), ModulesOrdering.end(),
 798             [&](int LeftIndex, int RightIndex) {
 799               auto LSize = Modules[LeftIndex].getBufferSize();
 800               auto RSize = Modules[RightIndex].getBufferSize();
 801               return LSize > RSize;
 802             });
 803
 804   // Parallel optimizer + codegen
 805   {
 806     ThreadPool Pool(ThreadCount);
 807     for (auto IndexCount : ModulesOrdering) {
 808       auto &ModuleBuffer = Modules[IndexCount];
 809       Pool.async([&](int count) {
 810         auto ModuleIdentifier = ModuleBuffer.getBufferIdentifier();
 811         auto &ExportList = ExportLists[ModuleIdentifier];
 812
 813         auto &DefinedFunctions = ModuleToDefinedGVSummaries[ModuleIdentifier];
 814
 815         // The module may be cached, this helps handling it.
 816         ModuleCacheEntry CacheEntry(CacheOptions.Path, *Index, ModuleIdentifier,
 817                                     ImportLists[ModuleIdentifier], ExportList,
 818                                     ResolvedODR[ModuleIdentifier],
 819                                     DefinedFunctions, GUIDPreservedSymbols);
 820
 821         {
 822           auto ErrOrBuffer = CacheEntry.tryLoadingBuffer();
 823           DEBUG(dbgs() << "Cache " << (ErrOrBuffer ? "hit" : "miss") << " '"
 824                        << CacheEntry.getEntryPath() << "' for buffer " << count
 825                        << " " << ModuleIdentifier << "\n");
 826
 827           if (ErrOrBuffer) {
 828             // Cache Hit!
 829             ProducedBinaries[count] = std::move(ErrOrBuffer.get());
 830             return;
 831           }
 832         }
 833
 834         LLVMContext Context;
 835         Context.setDiscardValueNames(LTODiscardValueNames);
 836         Context.enableDebugTypeODRUniquing();
 837
 838         // Parse module now
 839         auto TheModule = loadModuleFromBuffer(ModuleBuffer, Context, false);
 840
 841         // Save temps: original file.
 842         saveTempBitcode(*TheModule, SaveTempsDir, count, ".0.original.bc");
 843
 844         auto &ImportList = ImportLists[ModuleIdentifier];
 845         // Run the main process now, and generates a binary
 846         auto OutputBuffer = ProcessThinLTOModule(
 847             *TheModule, *Index, ModuleMap, *TMBuilder.create(), ImportList,
 848             ExportList, GUIDPreservedSymbols,
 849             ModuleToDefinedGVSummaries[ModuleIdentifier], CacheOptions,
 850             DisableCodeGen, SaveTempsDir, count);
 851
 852         OutputBuffer = CacheEntry.write(std::move(OutputBuffer));
 853         ProducedBinaries[count] = std::move(OutputBuffer);
 854       }, IndexCount);
 855     }
 856   }
 857
 858   CachePruning(CacheOptions.Path)
 859       .setPruningInterval(std::chrono::seconds(CacheOptions.PruningInterval))
 860       .setEntryExpiration(std::chrono::seconds(CacheOptions.Expiration))
 861       .setMaxSize(CacheOptions.MaxPercentageOfAvailableSpace)
 862       .prune();
 863
 864   // If statistics were requested, print them out now.
 865   if (llvm::AreStatisticsEnabled())
 866     llvm::PrintStatistics();
 867 }