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