contrib/llvm/lib/LTO/LTO.cpp

   1 //===-LTO.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 functions and classes used to support LTO.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/LTO/LTO.h"
  15 #include "llvm/Analysis/TargetLibraryInfo.h"
  16 #include "llvm/Analysis/TargetTransformInfo.h"
  17 #include "llvm/Bitcode/BitcodeReader.h"
  18 #include "llvm/Bitcode/BitcodeWriter.h"
  19 #include "llvm/CodeGen/Analysis.h"
  20 #include "llvm/IR/AutoUpgrade.h"
  21 #include "llvm/IR/DiagnosticPrinter.h"
  22 #include "llvm/IR/LegacyPassManager.h"
  23 #include "llvm/LTO/LTOBackend.h"
  24 #include "llvm/Linker/IRMover.h"
  25 #include "llvm/Object/ModuleSummaryIndexObjectFile.h"
  26 #include "llvm/Support/ManagedStatic.h"
  27 #include "llvm/Support/MemoryBuffer.h"
  28 #include "llvm/Support/Path.h"
  29 #include "llvm/Support/SHA1.h"
  30 #include "llvm/Support/SourceMgr.h"
  31 #include "llvm/Support/TargetRegistry.h"
  32 #include "llvm/Support/ThreadPool.h"
  33 #include "llvm/Support/Threading.h"
  34 #include "llvm/Support/raw_ostream.h"
  35 #include "llvm/Target/TargetMachine.h"
  36 #include "llvm/Target/TargetOptions.h"
  37 #include "llvm/Transforms/IPO.h"
  38 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
  39 #include "llvm/Transforms/Utils/SplitModule.h"
  40
  41 #include <set>
  42
  43 using namespace llvm;
  44 using namespace lto;
  45 using namespace object;
  46
  47 #define DEBUG_TYPE "lto"
  48
  49 // Returns a unique hash for the Module considering the current list of
  50 // export/import and other global analysis results.
  51 // The hash is produced in \p Key.
  52 static void computeCacheKey(
  53     SmallString<40> &Key, const Config &Conf, const ModuleSummaryIndex &Index,
  54     StringRef ModuleID, const FunctionImporter::ImportMapTy &ImportList,
  55     const FunctionImporter::ExportSetTy &ExportList,
  56     const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
  57     const GVSummaryMapTy &DefinedGlobals) {
  58   // Compute the unique hash for this entry.
  59   // This is based on the current compiler version, the module itself, the
  60   // export list, the hash for every single module in the import list, the
  61   // list of ResolvedODR for the module, and the list of preserved symbols.
  62   SHA1 Hasher;
  63
  64   // Start with the compiler revision
  65   Hasher.update(LLVM_VERSION_STRING);
  66 #ifdef HAVE_LLVM_REVISION
  67   Hasher.update(LLVM_REVISION);
  68 #endif
  69
  70   // Include the parts of the LTO configuration that affect code generation.
  71   auto AddString = [&](StringRef Str) {
  72     Hasher.update(Str);
  73     Hasher.update(ArrayRef<uint8_t>{0});
  74   };
  75   auto AddUnsigned = [&](unsigned I) {
  76     uint8_t Data[4];
  77     Data[0] = I;
  78     Data[1] = I >> 8;
  79     Data[2] = I >> 16;
  80     Data[3] = I >> 24;
  81     Hasher.update(ArrayRef<uint8_t>{Data, 4});
  82   };
  83   AddString(Conf.CPU);
  84   // FIXME: Hash more of Options. For now all clients initialize Options from
  85   // command-line flags (which is unsupported in production), but may set
  86   // RelaxELFRelocations. The clang driver can also pass FunctionSections,
  87   // DataSections and DebuggerTuning via command line flags.
  88   AddUnsigned(Conf.Options.RelaxELFRelocations);
  89   AddUnsigned(Conf.Options.FunctionSections);
  90   AddUnsigned(Conf.Options.DataSections);
  91   AddUnsigned((unsigned)Conf.Options.DebuggerTuning);
  92   for (auto &A : Conf.MAttrs)
  93     AddString(A);
  94   AddUnsigned(Conf.RelocModel);
  95   AddUnsigned(Conf.CodeModel);
  96   AddUnsigned(Conf.CGOptLevel);
  97   AddUnsigned(Conf.OptLevel);
  98   AddString(Conf.OptPipeline);
  99   AddString(Conf.AAPipeline);
 100   AddString(Conf.OverrideTriple);
 101   AddString(Conf.DefaultTriple);
 102
 103   // Include the hash for the current module
 104   auto ModHash = Index.getModuleHash(ModuleID);
 105   Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
 106   for (auto F : ExportList)
 107     // The export list can impact the internalization, be conservative here
 108     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&F, sizeof(F)));
 109
 110   // Include the hash for every module we import functions from
 111   for (auto &Entry : ImportList) {
 112     auto ModHash = Index.getModuleHash(Entry.first());
 113     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
 114   }
 115
 116   // Include the hash for the resolved ODR.
 117   for (auto &Entry : ResolvedODR) {
 118     Hasher.update(ArrayRef<uint8_t>((const uint8_t *)&Entry.first,
 119                                     sizeof(GlobalValue::GUID)));
 120     Hasher.update(ArrayRef<uint8_t>((const uint8_t *)&Entry.second,
 121                                     sizeof(GlobalValue::LinkageTypes)));
 122   }
 123
 124   // Include the hash for the linkage type to reflect internalization and weak
 125   // resolution.
 126   for (auto &GS : DefinedGlobals) {
 127     GlobalValue::LinkageTypes Linkage = GS.second->linkage();
 128     Hasher.update(
 129         ArrayRef<uint8_t>((const uint8_t *)&Linkage, sizeof(Linkage)));
 130   }
 131
 132   if (!Conf.SampleProfile.empty()) {
 133     auto FileOrErr = MemoryBuffer::getFile(Conf.SampleProfile);
 134     if (FileOrErr)
 135       Hasher.update(FileOrErr.get()->getBuffer());
 136   }
 137
 138   Key = toHex(Hasher.result());
 139 }
 140
 141 static void thinLTOResolveWeakForLinkerGUID(
 142     GlobalValueSummaryList &GVSummaryList, GlobalValue::GUID GUID,
 143     DenseSet<GlobalValueSummary *> &GlobalInvolvedWithAlias,
 144     function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
 145         isPrevailing,
 146     function_ref<void(StringRef, GlobalValue::GUID, GlobalValue::LinkageTypes)>
 147         recordNewLinkage) {
 148   for (auto &S : GVSummaryList) {
 149     GlobalValue::LinkageTypes OriginalLinkage = S->linkage();
 150     if (!GlobalValue::isWeakForLinker(OriginalLinkage))
 151       continue;
 152     // We need to emit only one of these. The prevailing module will keep it,
 153     // but turned into a weak, while the others will drop it when possible.
 154     // This is both a compile-time optimization and a correctness
 155     // transformation. This is necessary for correctness when we have exported
 156     // a reference - we need to convert the linkonce to weak to
 157     // ensure a copy is kept to satisfy the exported reference.
 158     // FIXME: We may want to split the compile time and correctness
 159     // aspects into separate routines.
 160     if (isPrevailing(GUID, S.get())) {
 161       if (GlobalValue::isLinkOnceLinkage(OriginalLinkage))
 162         S->setLinkage(GlobalValue::getWeakLinkage(
 163             GlobalValue::isLinkOnceODRLinkage(OriginalLinkage)));
 164     }
 165     // Alias and aliasee can't be turned into available_externally.
 166     else if (!isa<AliasSummary>(S.get()) &&
 167              !GlobalInvolvedWithAlias.count(S.get()) &&
 168              (GlobalValue::isLinkOnceODRLinkage(OriginalLinkage) ||
 169               GlobalValue::isWeakODRLinkage(OriginalLinkage)))
 170       S->setLinkage(GlobalValue::AvailableExternallyLinkage);
 171     if (S->linkage() != OriginalLinkage)
 172       recordNewLinkage(S->modulePath(), GUID, S->linkage());
 173   }
 174 }
 175
 176 // Resolve Weak and LinkOnce values in the \p Index.
 177 //
 178 // We'd like to drop these functions if they are no longer referenced in the
 179 // current module. However there is a chance that another module is still
 180 // referencing them because of the import. We make sure we always emit at least
 181 // one copy.
 182 void llvm::thinLTOResolveWeakForLinkerInIndex(
 183     ModuleSummaryIndex &Index,
 184     function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
 185         isPrevailing,
 186     function_ref<void(StringRef, GlobalValue::GUID, GlobalValue::LinkageTypes)>
 187         recordNewLinkage) {
 188   // We won't optimize the globals that are referenced by an alias for now
 189   // Ideally we should turn the alias into a global and duplicate the definition
 190   // when needed.
 191   DenseSet<GlobalValueSummary *> GlobalInvolvedWithAlias;
 192   for (auto &I : Index)
 193     for (auto &S : I.second)
 194       if (auto AS = dyn_cast<AliasSummary>(S.get()))
 195         GlobalInvolvedWithAlias.insert(&AS->getAliasee());
 196
 197   for (auto &I : Index)
 198     thinLTOResolveWeakForLinkerGUID(I.second, I.first, GlobalInvolvedWithAlias,
 199                                     isPrevailing, recordNewLinkage);
 200 }
 201
 202 static void thinLTOInternalizeAndPromoteGUID(
 203     GlobalValueSummaryList &GVSummaryList, GlobalValue::GUID GUID,
 204     function_ref<bool(StringRef, GlobalValue::GUID)> isExported) {
 205   for (auto &S : GVSummaryList) {
 206     if (isExported(S->modulePath(), GUID)) {
 207       if (GlobalValue::isLocalLinkage(S->linkage()))
 208         S->setLinkage(GlobalValue::ExternalLinkage);
 209     } else if (!GlobalValue::isLocalLinkage(S->linkage()))
 210       S->setLinkage(GlobalValue::InternalLinkage);
 211   }
 212 }
 213
 214 // Update the linkages in the given \p Index to mark exported values
 215 // as external and non-exported values as internal.
 216 void llvm::thinLTOInternalizeAndPromoteInIndex(
 217     ModuleSummaryIndex &Index,
 218     function_ref<bool(StringRef, GlobalValue::GUID)> isExported) {
 219   for (auto &I : Index)
 220     thinLTOInternalizeAndPromoteGUID(I.second, I.first, isExported);
 221 }
 222
 223 struct InputFile::InputModule {
 224   BitcodeModule BM;
 225   std::unique_ptr<Module> Mod;
 226
 227   // The range of ModuleSymbolTable entries for this input module.
 228   size_t SymBegin, SymEnd;
 229 };
 230
 231 // Requires a destructor for std::vector<InputModule>.
 232 InputFile::~InputFile() = default;
 233
 234 Expected<std::unique_ptr<InputFile>> InputFile::create(MemoryBufferRef Object) {
 235   std::unique_ptr<InputFile> File(new InputFile);
 236
 237   ErrorOr<MemoryBufferRef> BCOrErr =
 238       IRObjectFile::findBitcodeInMemBuffer(Object);
 239   if (!BCOrErr)
 240     return errorCodeToError(BCOrErr.getError());
 241
 242   Expected<std::vector<BitcodeModule>> BMsOrErr =
 243       getBitcodeModuleList(*BCOrErr);
 244   if (!BMsOrErr)
 245     return BMsOrErr.takeError();
 246
 247   if (BMsOrErr->empty())
 248     return make_error<StringError>("Bitcode file does not contain any modules",
 249                                    inconvertibleErrorCode());
 250
 251   // Create an InputModule for each module in the InputFile, and add it to the
 252   // ModuleSymbolTable.
 253   for (auto BM : *BMsOrErr) {
 254     Expected<std::unique_ptr<Module>> MOrErr =
 255         BM.getLazyModule(File->Ctx, /*ShouldLazyLoadMetadata*/ true,
 256                          /*IsImporting*/ false);
 257     if (!MOrErr)
 258       return MOrErr.takeError();
 259
 260     size_t SymBegin = File->SymTab.symbols().size();
 261     File->SymTab.addModule(MOrErr->get());
 262     size_t SymEnd = File->SymTab.symbols().size();
 263
 264     for (const auto &C : (*MOrErr)->getComdatSymbolTable()) {
 265       auto P = File->ComdatMap.insert(
 266           std::make_pair(&C.second, File->Comdats.size()));
 267       assert(P.second);
 268       (void)P;
 269       File->Comdats.push_back(C.first());
 270     }
 271
 272     File->Mods.push_back({BM, std::move(*MOrErr), SymBegin, SymEnd});
 273   }
 274
 275   return std::move(File);
 276 }
 277
 278 Expected<int> InputFile::Symbol::getComdatIndex() const {
 279   if (!isGV())
 280     return -1;
 281   const GlobalObject *GO = getGV()->getBaseObject();
 282   if (!GO)
 283     return make_error<StringError>("Unable to determine comdat of alias!",
 284                                    inconvertibleErrorCode());
 285   if (const Comdat *C = GO->getComdat()) {
 286     auto I = File->ComdatMap.find(C);
 287     assert(I != File->ComdatMap.end());
 288     return I->second;
 289   }
 290   return -1;
 291 }
 292
 293 StringRef InputFile::getName() const {
 294   return Mods[0].BM.getModuleIdentifier();
 295 }
 296
 297 StringRef InputFile::getSourceFileName() const {
 298   return Mods[0].Mod->getSourceFileName();
 299 }
 300
 301 iterator_range<InputFile::symbol_iterator>
 302 InputFile::module_symbols(InputModule &IM) {
 303   return llvm::make_range(
 304       symbol_iterator(SymTab.symbols().data() + IM.SymBegin, SymTab, this),
 305       symbol_iterator(SymTab.symbols().data() + IM.SymEnd, SymTab, this));
 306 }
 307
 308 LTO::RegularLTOState::RegularLTOState(unsigned ParallelCodeGenParallelismLevel,
 309                                       Config &Conf)
 310     : ParallelCodeGenParallelismLevel(ParallelCodeGenParallelismLevel),
 311       Ctx(Conf) {}
 312
 313 LTO::ThinLTOState::ThinLTOState(ThinBackend Backend) : Backend(Backend) {
 314   if (!Backend)
 315     this->Backend =
 316         createInProcessThinBackend(llvm::heavyweight_hardware_concurrency());
 317 }
 318
 319 LTO::LTO(Config Conf, ThinBackend Backend,
 320          unsigned ParallelCodeGenParallelismLevel)
 321     : Conf(std::move(Conf)),
 322       RegularLTO(ParallelCodeGenParallelismLevel, this->Conf),
 323       ThinLTO(std::move(Backend)) {}
 324
 325 // Requires a destructor for MapVector<BitcodeModule>.
 326 LTO::~LTO() = default;
 327
 328 // Add the given symbol to the GlobalResolutions map, and resolve its partition.
 329 void LTO::addSymbolToGlobalRes(SmallPtrSet<GlobalValue *, 8> &Used,
 330                                const InputFile::Symbol &Sym,
 331                                SymbolResolution Res, unsigned Partition) {
 332   GlobalValue *GV = Sym.isGV() ? Sym.getGV() : nullptr;
 333
 334   auto &GlobalRes = GlobalResolutions[Sym.getName()];
 335   if (GV) {
 336     GlobalRes.UnnamedAddr &= GV->hasGlobalUnnamedAddr();
 337     if (Res.Prevailing)
 338       GlobalRes.IRName = GV->getName();
 339   }
 340   // Set the partition to external if we know it is used elsewhere, e.g.
 341   // it is visible to a regular object, is referenced from llvm.compiler_used,
 342   // or was already recorded as being referenced from a different partition.
 343   if (Res.VisibleToRegularObj || (GV && Used.count(GV)) ||
 344       (GlobalRes.Partition != GlobalResolution::Unknown &&
 345        GlobalRes.Partition != Partition)) {
 346     GlobalRes.Partition = GlobalResolution::External;
 347   } else
 348     // First recorded reference, save the current partition.
 349     GlobalRes.Partition = Partition;
 350
 351   // Flag as visible outside of ThinLTO if visible from a regular object or
 352   // if this is a reference in the regular LTO partition.
 353   GlobalRes.VisibleOutsideThinLTO |=
 354       (Res.VisibleToRegularObj || (Partition == GlobalResolution::RegularLTO));
 355 }
 356
 357 static void writeToResolutionFile(raw_ostream &OS, InputFile *Input,
 358                                   ArrayRef<SymbolResolution> Res) {
 359   StringRef Path = Input->getName();
 360   OS << Path << '\n';
 361   auto ResI = Res.begin();
 362   for (const InputFile::Symbol &Sym : Input->symbols()) {
 363     assert(ResI != Res.end());
 364     SymbolResolution Res = *ResI++;
 365
 366     OS << "-r=" << Path << ',' << Sym.getName() << ',';
 367     if (Res.Prevailing)
 368       OS << 'p';
 369     if (Res.FinalDefinitionInLinkageUnit)
 370       OS << 'l';
 371     if (Res.VisibleToRegularObj)
 372       OS << 'x';
 373     OS << '\n';
 374   }
 375   assert(ResI == Res.end());
 376 }
 377
 378 Error LTO::add(std::unique_ptr<InputFile> Input,
 379                ArrayRef<SymbolResolution> Res) {
 380   assert(!CalledGetMaxTasks);
 381
 382   if (Conf.ResolutionFile)
 383     writeToResolutionFile(*Conf.ResolutionFile, Input.get(), Res);
 384
 385   const SymbolResolution *ResI = Res.begin();
 386   for (InputFile::InputModule &IM : Input->Mods)
 387     if (Error Err = addModule(*Input, IM, ResI, Res.end()))
 388       return Err;
 389
 390   assert(ResI == Res.end());
 391   return Error::success();
 392 }
 393
 394 Error LTO::addModule(InputFile &Input, InputFile::InputModule &IM,
 395                      const SymbolResolution *&ResI,
 396                      const SymbolResolution *ResE) {
 397   // FIXME: move to backend
 398   Module &M = *IM.Mod;
 399
 400   if (M.getDataLayoutStr().empty())
 401     return make_error<StringError>("input module has no datalayout",
 402                                     inconvertibleErrorCode());
 403
 404   if (!Conf.OverrideTriple.empty())
 405     M.setTargetTriple(Conf.OverrideTriple);
 406   else if (M.getTargetTriple().empty())
 407     M.setTargetTriple(Conf.DefaultTriple);
 408
 409   Expected<bool> HasThinLTOSummary = IM.BM.hasSummary();
 410   if (!HasThinLTOSummary)
 411     return HasThinLTOSummary.takeError();
 412
 413   if (*HasThinLTOSummary)
 414     return addThinLTO(IM.BM, M, Input.module_symbols(IM), ResI, ResE);
 415   else
 416     return addRegularLTO(IM.BM, ResI, ResE);
 417 }
 418
 419 // Add a regular LTO object to the link.
 420 Error LTO::addRegularLTO(BitcodeModule BM, const SymbolResolution *&ResI,
 421                          const SymbolResolution *ResE) {
 422   if (!RegularLTO.CombinedModule) {
 423     RegularLTO.CombinedModule =
 424         llvm::make_unique<Module>("ld-temp.o", RegularLTO.Ctx);
 425     RegularLTO.Mover = llvm::make_unique<IRMover>(*RegularLTO.CombinedModule);
 426   }
 427   Expected<std::unique_ptr<Module>> MOrErr =
 428       BM.getLazyModule(RegularLTO.Ctx, /*ShouldLazyLoadMetadata*/ true,
 429                        /*IsImporting*/ false);
 430   if (!MOrErr)
 431     return MOrErr.takeError();
 432
 433   Module &M = **MOrErr;
 434   if (Error Err = M.materializeMetadata())
 435     return Err;
 436   UpgradeDebugInfo(M);
 437
 438   ModuleSymbolTable SymTab;
 439   SymTab.addModule(&M);
 440
 441   SmallPtrSet<GlobalValue *, 8> Used;
 442   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
 443
 444   std::vector<GlobalValue *> Keep;
 445
 446   for (GlobalVariable &GV : M.globals())
 447     if (GV.hasAppendingLinkage())
 448       Keep.push_back(&GV);
 449
 450   for (const InputFile::Symbol &Sym :
 451        make_range(InputFile::symbol_iterator(SymTab.symbols().begin(), SymTab,
 452                                              nullptr),
 453                   InputFile::symbol_iterator(SymTab.symbols().end(), SymTab,
 454                                              nullptr))) {
 455     assert(ResI != ResE);
 456     SymbolResolution Res = *ResI++;
 457     addSymbolToGlobalRes(Used, Sym, Res, 0);
 458
 459     if (Sym.getFlags() & object::BasicSymbolRef::SF_Undefined)
 460       continue;
 461     if (Res.Prevailing && Sym.isGV()) {
 462       GlobalValue *GV = Sym.getGV();
 463       Keep.push_back(GV);
 464       switch (GV->getLinkage()) {
 465       default:
 466         break;
 467       case GlobalValue::LinkOnceAnyLinkage:
 468         GV->setLinkage(GlobalValue::WeakAnyLinkage);
 469         break;
 470       case GlobalValue::LinkOnceODRLinkage:
 471         GV->setLinkage(GlobalValue::WeakODRLinkage);
 472         break;
 473       }
 474     }
 475     // Common resolution: collect the maximum size/alignment over all commons.
 476     // We also record if we see an instance of a common as prevailing, so that
 477     // if none is prevailing we can ignore it later.
 478     if (Sym.getFlags() & object::BasicSymbolRef::SF_Common) {
 479       // FIXME: We should figure out what to do about commons defined by asm.
 480       // For now they aren't reported correctly by ModuleSymbolTable.
 481       auto &CommonRes = RegularLTO.Commons[Sym.getGV()->getName()];
 482       CommonRes.Size = std::max(CommonRes.Size, Sym.getCommonSize());
 483       CommonRes.Align = std::max(CommonRes.Align, Sym.getCommonAlignment());
 484       CommonRes.Prevailing |= Res.Prevailing;
 485     }
 486
 487     // FIXME: use proposed local attribute for FinalDefinitionInLinkageUnit.
 488   }
 489
 490   return RegularLTO.Mover->move(std::move(*MOrErr), Keep,
 491                                 [](GlobalValue &, IRMover::ValueAdder) {},
 492                                 /* LinkModuleInlineAsm */ true,
 493                                 /* IsPerformingImport */ false);
 494 }
 495
 496 // Add a ThinLTO object to the link.
 497 // FIXME: This function should not need to take as many parameters once we have
 498 // a bitcode symbol table.
 499 Error LTO::addThinLTO(BitcodeModule BM, Module &M,
 500                       iterator_range<InputFile::symbol_iterator> Syms,
 501                       const SymbolResolution *&ResI,
 502                       const SymbolResolution *ResE) {
 503   SmallPtrSet<GlobalValue *, 8> Used;
 504   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
 505
 506   Expected<std::unique_ptr<ModuleSummaryIndex>> SummaryOrErr = BM.getSummary();
 507   if (!SummaryOrErr)
 508     return SummaryOrErr.takeError();
 509   ThinLTO.CombinedIndex.mergeFrom(std::move(*SummaryOrErr),
 510                                   ThinLTO.ModuleMap.size());
 511
 512   for (const InputFile::Symbol &Sym : Syms) {
 513     assert(ResI != ResE);
 514     SymbolResolution Res = *ResI++;
 515     addSymbolToGlobalRes(Used, Sym, Res, ThinLTO.ModuleMap.size() + 1);
 516
 517     if (Res.Prevailing && Sym.isGV())
 518       ThinLTO.PrevailingModuleForGUID[Sym.getGV()->getGUID()] =
 519           BM.getModuleIdentifier();
 520   }
 521
 522   if (!ThinLTO.ModuleMap.insert({BM.getModuleIdentifier(), BM}).second)
 523     return make_error<StringError>(
 524         "Expected at most one ThinLTO module per bitcode file",
 525         inconvertibleErrorCode());
 526
 527   return Error::success();
 528 }
 529
 530 unsigned LTO::getMaxTasks() const {
 531   CalledGetMaxTasks = true;
 532   return RegularLTO.ParallelCodeGenParallelismLevel + ThinLTO.ModuleMap.size();
 533 }
 534
 535 Error LTO::run(AddStreamFn AddStream, NativeObjectCache Cache) {
 536   // Save the status of having a regularLTO combined module, as
 537   // this is needed for generating the ThinLTO Task ID, and
 538   // the CombinedModule will be moved at the end of runRegularLTO.
 539   bool HasRegularLTO = RegularLTO.CombinedModule != nullptr;
 540   // Invoke regular LTO if there was a regular LTO module to start with.
 541   if (HasRegularLTO)
 542     if (auto E = runRegularLTO(AddStream))
 543       return E;
 544   return runThinLTO(AddStream, Cache, HasRegularLTO);
 545 }
 546
 547 Error LTO::runRegularLTO(AddStreamFn AddStream) {
 548   // Make sure commons have the right size/alignment: we kept the largest from
 549   // all the prevailing when adding the inputs, and we apply it here.
 550   const DataLayout &DL = RegularLTO.CombinedModule->getDataLayout();
 551   for (auto &I : RegularLTO.Commons) {
 552     if (!I.second.Prevailing)
 553       // Don't do anything if no instance of this common was prevailing.
 554       continue;
 555     GlobalVariable *OldGV = RegularLTO.CombinedModule->getNamedGlobal(I.first);
 556     if (OldGV && DL.getTypeAllocSize(OldGV->getValueType()) == I.second.Size) {
 557       // Don't create a new global if the type is already correct, just make
 558       // sure the alignment is correct.
 559       OldGV->setAlignment(I.second.Align);
 560       continue;
 561     }
 562     ArrayType *Ty =
 563         ArrayType::get(Type::getInt8Ty(RegularLTO.Ctx), I.second.Size);
 564     auto *GV = new GlobalVariable(*RegularLTO.CombinedModule, Ty, false,
 565                                   GlobalValue::CommonLinkage,
 566                                   ConstantAggregateZero::get(Ty), "");
 567     GV->setAlignment(I.second.Align);
 568     if (OldGV) {
 569       OldGV->replaceAllUsesWith(ConstantExpr::getBitCast(GV, OldGV->getType()));
 570       GV->takeName(OldGV);
 571       OldGV->eraseFromParent();
 572     } else {
 573       GV->setName(I.first);
 574     }
 575   }
 576
 577   if (Conf.PreOptModuleHook &&
 578       !Conf.PreOptModuleHook(0, *RegularLTO.CombinedModule))
 579     return Error::success();
 580
 581   if (!Conf.CodeGenOnly) {
 582     for (const auto &R : GlobalResolutions) {
 583       if (R.second.IRName.empty())
 584         continue;
 585       if (R.second.Partition != 0 &&
 586           R.second.Partition != GlobalResolution::External)
 587         continue;
 588
 589       GlobalValue *GV =
 590           RegularLTO.CombinedModule->getNamedValue(R.second.IRName);
 591       // Ignore symbols defined in other partitions.
 592       if (!GV || GV->hasLocalLinkage())
 593         continue;
 594       GV->setUnnamedAddr(R.second.UnnamedAddr ? GlobalValue::UnnamedAddr::Global
 595                                               : GlobalValue::UnnamedAddr::None);
 596       if (R.second.Partition == 0)
 597         GV->setLinkage(GlobalValue::InternalLinkage);
 598     }
 599
 600     if (Conf.PostInternalizeModuleHook &&
 601         !Conf.PostInternalizeModuleHook(0, *RegularLTO.CombinedModule))
 602       return Error::success();
 603   }
 604   return backend(Conf, AddStream, RegularLTO.ParallelCodeGenParallelismLevel,
 605                  std::move(RegularLTO.CombinedModule));
 606 }
 607
 608 /// This class defines the interface to the ThinLTO backend.
 609 class lto::ThinBackendProc {
 610 protected:
 611   Config &Conf;
 612   ModuleSummaryIndex &CombinedIndex;
 613   const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries;
 614
 615 public:
 616   ThinBackendProc(Config &Conf, ModuleSummaryIndex &CombinedIndex,
 617                   const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries)
 618       : Conf(Conf), CombinedIndex(CombinedIndex),
 619         ModuleToDefinedGVSummaries(ModuleToDefinedGVSummaries) {}
 620
 621   virtual ~ThinBackendProc() {}
 622   virtual Error start(
 623       unsigned Task, BitcodeModule BM,
 624       const FunctionImporter::ImportMapTy &ImportList,
 625       const FunctionImporter::ExportSetTy &ExportList,
 626       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
 627       MapVector<StringRef, BitcodeModule> &ModuleMap) = 0;
 628   virtual Error wait() = 0;
 629 };
 630
 631 namespace {
 632 class InProcessThinBackend : public ThinBackendProc {
 633   ThreadPool BackendThreadPool;
 634   AddStreamFn AddStream;
 635   NativeObjectCache Cache;
 636
 637   Optional<Error> Err;
 638   std::mutex ErrMu;
 639
 640 public:
 641   InProcessThinBackend(
 642       Config &Conf, ModuleSummaryIndex &CombinedIndex,
 643       unsigned ThinLTOParallelismLevel,
 644       const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
 645       AddStreamFn AddStream, NativeObjectCache Cache)
 646       : ThinBackendProc(Conf, CombinedIndex, ModuleToDefinedGVSummaries),
 647         BackendThreadPool(ThinLTOParallelismLevel),
 648         AddStream(std::move(AddStream)), Cache(std::move(Cache)) {}
 649
 650   Error runThinLTOBackendThread(
 651       AddStreamFn AddStream, NativeObjectCache Cache, unsigned Task,
 652       BitcodeModule BM, ModuleSummaryIndex &CombinedIndex,
 653       const FunctionImporter::ImportMapTy &ImportList,
 654       const FunctionImporter::ExportSetTy &ExportList,
 655       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
 656       const GVSummaryMapTy &DefinedGlobals,
 657       MapVector<StringRef, BitcodeModule> &ModuleMap) {
 658     auto RunThinBackend = [&](AddStreamFn AddStream) {
 659       LTOLLVMContext BackendContext(Conf);
 660       Expected<std::unique_ptr<Module>> MOrErr = BM.parseModule(BackendContext);
 661       if (!MOrErr)
 662         return MOrErr.takeError();
 663
 664       return thinBackend(Conf, Task, AddStream, **MOrErr, CombinedIndex,
 665                          ImportList, DefinedGlobals, ModuleMap);
 666     };
 667
 668     auto ModuleID = BM.getModuleIdentifier();
 669
 670     if (!Cache || !CombinedIndex.modulePaths().count(ModuleID) ||
 671         all_of(CombinedIndex.getModuleHash(ModuleID),
 672                [](uint32_t V) { return V == 0; }))
 673       // Cache disabled or no entry for this module in the combined index or
 674       // no module hash.
 675       return RunThinBackend(AddStream);
 676
 677     SmallString<40> Key;
 678     // The module may be cached, this helps handling it.
 679     computeCacheKey(Key, Conf, CombinedIndex, ModuleID, ImportList, ExportList,
 680                     ResolvedODR, DefinedGlobals);
 681     if (AddStreamFn CacheAddStream = Cache(Task, Key))
 682       return RunThinBackend(CacheAddStream);
 683
 684     return Error::success();
 685   }
 686
 687   Error start(
 688       unsigned Task, BitcodeModule BM,
 689       const FunctionImporter::ImportMapTy &ImportList,
 690       const FunctionImporter::ExportSetTy &ExportList,
 691       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
 692       MapVector<StringRef, BitcodeModule> &ModuleMap) override {
 693     StringRef ModulePath = BM.getModuleIdentifier();
 694     assert(ModuleToDefinedGVSummaries.count(ModulePath));
 695     const GVSummaryMapTy &DefinedGlobals =
 696         ModuleToDefinedGVSummaries.find(ModulePath)->second;
 697     BackendThreadPool.async(
 698         [=](BitcodeModule BM, ModuleSummaryIndex &CombinedIndex,
 699             const FunctionImporter::ImportMapTy &ImportList,
 700             const FunctionImporter::ExportSetTy &ExportList,
 701             const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>
 702                 &ResolvedODR,
 703             const GVSummaryMapTy &DefinedGlobals,
 704             MapVector<StringRef, BitcodeModule> &ModuleMap) {
 705           Error E = runThinLTOBackendThread(
 706               AddStream, Cache, Task, BM, CombinedIndex, ImportList,
 707               ExportList, ResolvedODR, DefinedGlobals, ModuleMap);
 708           if (E) {
 709             std::unique_lock<std::mutex> L(ErrMu);
 710             if (Err)
 711               Err = joinErrors(std::move(*Err), std::move(E));
 712             else
 713               Err = std::move(E);
 714           }
 715         },
 716         BM, std::ref(CombinedIndex), std::ref(ImportList),
 717         std::ref(ExportList), std::ref(ResolvedODR), std::ref(DefinedGlobals),
 718         std::ref(ModuleMap));
 719     return Error::success();
 720   }
 721
 722   Error wait() override {
 723     BackendThreadPool.wait();
 724     if (Err)
 725       return std::move(*Err);
 726     else
 727       return Error::success();
 728   }
 729 };
 730 } // end anonymous namespace
 731
 732 ThinBackend lto::createInProcessThinBackend(unsigned ParallelismLevel) {
 733   return [=](Config &Conf, ModuleSummaryIndex &CombinedIndex,
 734              const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
 735              AddStreamFn AddStream, NativeObjectCache Cache) {
 736     return llvm::make_unique<InProcessThinBackend>(
 737         Conf, CombinedIndex, ParallelismLevel, ModuleToDefinedGVSummaries,
 738         AddStream, Cache);
 739   };
 740 }
 741
 742 // Given the original \p Path to an output file, replace any path
 743 // prefix matching \p OldPrefix with \p NewPrefix. Also, create the
 744 // resulting directory if it does not yet exist.
 745 std::string lto::getThinLTOOutputFile(const std::string &Path,
 746                                       const std::string &OldPrefix,
 747                                       const std::string &NewPrefix) {
 748   if (OldPrefix.empty() && NewPrefix.empty())
 749     return Path;
 750   SmallString<128> NewPath(Path);
 751   llvm::sys::path::replace_path_prefix(NewPath, OldPrefix, NewPrefix);
 752   StringRef ParentPath = llvm::sys::path::parent_path(NewPath.str());
 753   if (!ParentPath.empty()) {
 754     // Make sure the new directory exists, creating it if necessary.
 755     if (std::error_code EC = llvm::sys::fs::create_directories(ParentPath))
 756       llvm::errs() << "warning: could not create directory '" << ParentPath
 757                    << "': " << EC.message() << '\n';
 758   }
 759   return NewPath.str();
 760 }
 761
 762 namespace {
 763 class WriteIndexesThinBackend : public ThinBackendProc {
 764   std::string OldPrefix, NewPrefix;
 765   bool ShouldEmitImportsFiles;
 766
 767   std::string LinkedObjectsFileName;
 768   std::unique_ptr<llvm::raw_fd_ostream> LinkedObjectsFile;
 769
 770 public:
 771   WriteIndexesThinBackend(
 772       Config &Conf, ModuleSummaryIndex &CombinedIndex,
 773       const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
 774       std::string OldPrefix, std::string NewPrefix, bool ShouldEmitImportsFiles,
 775       std::string LinkedObjectsFileName)
 776       : ThinBackendProc(Conf, CombinedIndex, ModuleToDefinedGVSummaries),
 777         OldPrefix(OldPrefix), NewPrefix(NewPrefix),
 778         ShouldEmitImportsFiles(ShouldEmitImportsFiles),
 779         LinkedObjectsFileName(LinkedObjectsFileName) {}
 780
 781   Error start(
 782       unsigned Task, BitcodeModule BM,
 783       const FunctionImporter::ImportMapTy &ImportList,
 784       const FunctionImporter::ExportSetTy &ExportList,
 785       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
 786       MapVector<StringRef, BitcodeModule> &ModuleMap) override {
 787     StringRef ModulePath = BM.getModuleIdentifier();
 788     std::string NewModulePath =
 789         getThinLTOOutputFile(ModulePath, OldPrefix, NewPrefix);
 790
 791     std::error_code EC;
 792     if (!LinkedObjectsFileName.empty()) {
 793       if (!LinkedObjectsFile) {
 794         LinkedObjectsFile = llvm::make_unique<raw_fd_ostream>(
 795             LinkedObjectsFileName, EC, sys::fs::OpenFlags::F_None);
 796         if (EC)
 797           return errorCodeToError(EC);
 798       }
 799       *LinkedObjectsFile << NewModulePath << '\n';
 800     }
 801
 802     std::map<std::string, GVSummaryMapTy> ModuleToSummariesForIndex;
 803     gatherImportedSummariesForModule(ModulePath, ModuleToDefinedGVSummaries,
 804                                      ImportList, ModuleToSummariesForIndex);
 805
 806     raw_fd_ostream OS(NewModulePath + ".thinlto.bc", EC,
 807                       sys::fs::OpenFlags::F_None);
 808     if (EC)
 809       return errorCodeToError(EC);
 810     WriteIndexToFile(CombinedIndex, OS, &ModuleToSummariesForIndex);
 811
 812     if (ShouldEmitImportsFiles)
 813       return errorCodeToError(
 814           EmitImportsFiles(ModulePath, NewModulePath + ".imports", ImportList));
 815     return Error::success();
 816   }
 817
 818   Error wait() override { return Error::success(); }
 819 };
 820 } // end anonymous namespace
 821
 822 ThinBackend lto::createWriteIndexesThinBackend(std::string OldPrefix,
 823                                                std::string NewPrefix,
 824                                                bool ShouldEmitImportsFiles,
 825                                                std::string LinkedObjectsFile) {
 826   return [=](Config &Conf, ModuleSummaryIndex &CombinedIndex,
 827              const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
 828              AddStreamFn AddStream, NativeObjectCache Cache) {
 829     return llvm::make_unique<WriteIndexesThinBackend>(
 830         Conf, CombinedIndex, ModuleToDefinedGVSummaries, OldPrefix, NewPrefix,
 831         ShouldEmitImportsFiles, LinkedObjectsFile);
 832   };
 833 }
 834
 835 Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache,
 836                       bool HasRegularLTO) {
 837   if (ThinLTO.ModuleMap.empty())
 838     return Error::success();
 839
 840   if (Conf.CombinedIndexHook && !Conf.CombinedIndexHook(ThinLTO.CombinedIndex))
 841     return Error::success();
 842
 843   // Collect for each module the list of function it defines (GUID ->
 844   // Summary).
 845   StringMap<std::map<GlobalValue::GUID, GlobalValueSummary *>>
 846       ModuleToDefinedGVSummaries(ThinLTO.ModuleMap.size());
 847   ThinLTO.CombinedIndex.collectDefinedGVSummariesPerModule(
 848       ModuleToDefinedGVSummaries);
 849   // Create entries for any modules that didn't have any GV summaries
 850   // (either they didn't have any GVs to start with, or we suppressed
 851   // generation of the summaries because they e.g. had inline assembly
 852   // uses that couldn't be promoted/renamed on export). This is so
 853   // InProcessThinBackend::start can still launch a backend thread, which
 854   // is passed the map of summaries for the module, without any special
 855   // handling for this case.
 856   for (auto &Mod : ThinLTO.ModuleMap)
 857     if (!ModuleToDefinedGVSummaries.count(Mod.first))
 858       ModuleToDefinedGVSummaries.try_emplace(Mod.first);
 859
 860   // Compute "dead" symbols, we don't want to import/export these!
 861   DenseSet<GlobalValue::GUID> GUIDPreservedSymbols;
 862   for (auto &Res : GlobalResolutions) {
 863     if (Res.second.VisibleOutsideThinLTO &&
 864         // IRName will be defined if we have seen the prevailing copy of
 865         // this value. If not, no need to preserve any ThinLTO copies.
 866         !Res.second.IRName.empty())
 867       GUIDPreservedSymbols.insert(GlobalValue::getGUID(Res.second.IRName));
 868   }
 869
 870   auto DeadSymbols =
 871       computeDeadSymbols(ThinLTO.CombinedIndex, GUIDPreservedSymbols);
 872
 873   StringMap<FunctionImporter::ImportMapTy> ImportLists(
 874       ThinLTO.ModuleMap.size());
 875   StringMap<FunctionImporter::ExportSetTy> ExportLists(
 876       ThinLTO.ModuleMap.size());
 877   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
 878
 879   if (Conf.OptLevel > 0) {
 880     ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
 881                              ImportLists, ExportLists, &DeadSymbols);
 882
 883     std::set<GlobalValue::GUID> ExportedGUIDs;
 884     for (auto &Res : GlobalResolutions) {
 885       // First check if the symbol was flagged as having external references.
 886       if (Res.second.Partition != GlobalResolution::External)
 887         continue;
 888       // IRName will be defined if we have seen the prevailing copy of
 889       // this value. If not, no need to mark as exported from a ThinLTO
 890       // partition (and we can't get the GUID).
 891       if (Res.second.IRName.empty())
 892         continue;
 893       auto GUID = GlobalValue::getGUID(Res.second.IRName);
 894       // Mark exported unless index-based analysis determined it to be dead.
 895       if (!DeadSymbols.count(GUID))
 896         ExportedGUIDs.insert(GlobalValue::getGUID(Res.second.IRName));
 897     }
 898
 899     auto isPrevailing = [&](GlobalValue::GUID GUID,
 900                             const GlobalValueSummary *S) {
 901       return ThinLTO.PrevailingModuleForGUID[GUID] == S->modulePath();
 902     };
 903     auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) {
 904       const auto &ExportList = ExportLists.find(ModuleIdentifier);
 905       return (ExportList != ExportLists.end() &&
 906               ExportList->second.count(GUID)) ||
 907              ExportedGUIDs.count(GUID);
 908     };
 909     thinLTOInternalizeAndPromoteInIndex(ThinLTO.CombinedIndex, isExported);
 910
 911     auto recordNewLinkage = [&](StringRef ModuleIdentifier,
 912                                 GlobalValue::GUID GUID,
 913                                 GlobalValue::LinkageTypes NewLinkage) {
 914       ResolvedODR[ModuleIdentifier][GUID] = NewLinkage;
 915     };
 916
 917     thinLTOResolveWeakForLinkerInIndex(ThinLTO.CombinedIndex, isPrevailing,
 918                                        recordNewLinkage);
 919   }
 920
 921   std::unique_ptr<ThinBackendProc> BackendProc =
 922       ThinLTO.Backend(Conf, ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
 923                       AddStream, Cache);
 924
 925   // Task numbers start at ParallelCodeGenParallelismLevel if an LTO
 926   // module is present, as tasks 0 through ParallelCodeGenParallelismLevel-1
 927   // are reserved for parallel code generation partitions.
 928   unsigned Task =
 929       HasRegularLTO ? RegularLTO.ParallelCodeGenParallelismLevel : 0;
 930   for (auto &Mod : ThinLTO.ModuleMap) {
 931     if (Error E = BackendProc->start(Task, Mod.second, ImportLists[Mod.first],
 932                                      ExportLists[Mod.first],
 933                                      ResolvedODR[Mod.first], ThinLTO.ModuleMap))
 934       return E;
 935     ++Task;
 936   }
 937
 938   return BackendProc->wait();
 939 }