lib/LTO/LTO.cpp

   1 //===-LTO.cpp - LLVM Link Time Optimizer ----------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements functions and classes used to support LTO.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/LTO/LTO.h"
  14 #include "llvm/ADT/Statistic.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/Config/llvm-config.h"
  21 #include "llvm/IR/AutoUpgrade.h"
  22 #include "llvm/IR/DiagnosticPrinter.h"
  23 #include "llvm/IR/Intrinsics.h"
  24 #include "llvm/IR/LegacyPassManager.h"
  25 #include "llvm/IR/Mangler.h"
  26 #include "llvm/IR/Metadata.h"
  27 #include "llvm/IR/RemarkStreamer.h"
  28 #include "llvm/LTO/LTOBackend.h"
  29 #include "llvm/LTO/SummaryBasedOptimizations.h"
  30 #include "llvm/Linker/IRMover.h"
  31 #include "llvm/Object/IRObjectFile.h"
  32 #include "llvm/Support/Error.h"
  33 #include "llvm/Support/ManagedStatic.h"
  34 #include "llvm/Support/MemoryBuffer.h"
  35 #include "llvm/Support/Path.h"
  36 #include "llvm/Support/SHA1.h"
  37 #include "llvm/Support/SourceMgr.h"
  38 #include "llvm/Support/TargetRegistry.h"
  39 #include "llvm/Support/ThreadPool.h"
  40 #include "llvm/Support/Threading.h"
  41 #include "llvm/Support/VCSRevision.h"
  42 #include "llvm/Support/raw_ostream.h"
  43 #include "llvm/Target/TargetMachine.h"
  44 #include "llvm/Target/TargetOptions.h"
  45 #include "llvm/Transforms/IPO.h"
  46 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
  47 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
  48 #include "llvm/Transforms/Utils/SplitModule.h"
  49
  50 #include <set>
  51
  52 using namespace llvm;
  53 using namespace lto;
  54 using namespace object;
  55
  56 #define DEBUG_TYPE "lto"
  57
  58 static cl::opt<bool>
  59     DumpThinCGSCCs("dump-thin-cg-sccs", cl::init(false), cl::Hidden,
  60                    cl::desc("Dump the SCCs in the ThinLTO index's callgraph"));
  61
  62 /// Enable global value internalization in LTO.
  63 cl::opt<bool> EnableLTOInternalization(
  64     "enable-lto-internalization", cl::init(true), cl::Hidden,
  65     cl::desc("Enable global value internalization in LTO"));
  66
  67 // Computes a unique hash for the Module considering the current list of
  68 // export/import and other global analysis results.
  69 // The hash is produced in \p Key.
  70 void llvm::computeLTOCacheKey(
  71     SmallString<40> &Key, const Config &Conf, const ModuleSummaryIndex &Index,
  72     StringRef ModuleID, const FunctionImporter::ImportMapTy &ImportList,
  73     const FunctionImporter::ExportSetTy &ExportList,
  74     const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
  75     const GVSummaryMapTy &DefinedGlobals,
  76     const std::set<GlobalValue::GUID> &CfiFunctionDefs,
  77     const std::set<GlobalValue::GUID> &CfiFunctionDecls) {
  78   // Compute the unique hash for this entry.
  79   // This is based on the current compiler version, the module itself, the
  80   // export list, the hash for every single module in the import list, the
  81   // list of ResolvedODR for the module, and the list of preserved symbols.
  82   SHA1 Hasher;
  83
  84   // Start with the compiler revision
  85   Hasher.update(LLVM_VERSION_STRING);
  86 #ifdef LLVM_REVISION
  87   Hasher.update(LLVM_REVISION);
  88 #endif
  89
  90   // Include the parts of the LTO configuration that affect code generation.
  91   auto AddString = [&](StringRef Str) {
  92     Hasher.update(Str);
  93     Hasher.update(ArrayRef<uint8_t>{0});
  94   };
  95   auto AddUnsigned = [&](unsigned I) {
  96     uint8_t Data[4];
  97     Data[0] = I;
  98     Data[1] = I >> 8;
  99     Data[2] = I >> 16;
 100     Data[3] = I >> 24;
 101     Hasher.update(ArrayRef<uint8_t>{Data, 4});
 102   };
 103   auto AddUint64 = [&](uint64_t I) {
 104     uint8_t Data[8];
 105     Data[0] = I;
 106     Data[1] = I >> 8;
 107     Data[2] = I >> 16;
 108     Data[3] = I >> 24;
 109     Data[4] = I >> 32;
 110     Data[5] = I >> 40;
 111     Data[6] = I >> 48;
 112     Data[7] = I >> 56;
 113     Hasher.update(ArrayRef<uint8_t>{Data, 8});
 114   };
 115   AddString(Conf.CPU);
 116   // FIXME: Hash more of Options. For now all clients initialize Options from
 117   // command-line flags (which is unsupported in production), but may set
 118   // RelaxELFRelocations. The clang driver can also pass FunctionSections,
 119   // DataSections and DebuggerTuning via command line flags.
 120   AddUnsigned(Conf.Options.RelaxELFRelocations);
 121   AddUnsigned(Conf.Options.FunctionSections);
 122   AddUnsigned(Conf.Options.DataSections);
 123   AddUnsigned((unsigned)Conf.Options.DebuggerTuning);
 124   for (auto &A : Conf.MAttrs)
 125     AddString(A);
 126   if (Conf.RelocModel)
 127     AddUnsigned(*Conf.RelocModel);
 128   else
 129     AddUnsigned(-1);
 130   if (Conf.CodeModel)
 131     AddUnsigned(*Conf.CodeModel);
 132   else
 133     AddUnsigned(-1);
 134   AddUnsigned(Conf.CGOptLevel);
 135   AddUnsigned(Conf.CGFileType);
 136   AddUnsigned(Conf.OptLevel);
 137   AddUnsigned(Conf.UseNewPM);
 138   AddUnsigned(Conf.Freestanding);
 139   AddString(Conf.OptPipeline);
 140   AddString(Conf.AAPipeline);
 141   AddString(Conf.OverrideTriple);
 142   AddString(Conf.DefaultTriple);
 143   AddString(Conf.DwoDir);
 144
 145   // Include the hash for the current module
 146   auto ModHash = Index.getModuleHash(ModuleID);
 147   Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
 148   for (auto F : ExportList)
 149     // The export list can impact the internalization, be conservative here
 150     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&F, sizeof(F)));
 151
 152   // Include the hash for every module we import functions from. The set of
 153   // imported symbols for each module may affect code generation and is
 154   // sensitive to link order, so include that as well.
 155   for (auto &Entry : ImportList) {
 156     auto ModHash = Index.getModuleHash(Entry.first());
 157     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
 158
 159     AddUint64(Entry.second.size());
 160     for (auto &Fn : Entry.second)
 161       AddUint64(Fn);
 162   }
 163
 164   // Include the hash for the resolved ODR.
 165   for (auto &Entry : ResolvedODR) {
 166     Hasher.update(ArrayRef<uint8_t>((const uint8_t *)&Entry.first,
 167                                     sizeof(GlobalValue::GUID)));
 168     Hasher.update(ArrayRef<uint8_t>((const uint8_t *)&Entry.second,
 169                                     sizeof(GlobalValue::LinkageTypes)));
 170   }
 171
 172   // Members of CfiFunctionDefs and CfiFunctionDecls that are referenced or
 173   // defined in this module.
 174   std::set<GlobalValue::GUID> UsedCfiDefs;
 175   std::set<GlobalValue::GUID> UsedCfiDecls;
 176
 177   // Typeids used in this module.
 178   std::set<GlobalValue::GUID> UsedTypeIds;
 179
 180   auto AddUsedCfiGlobal = [&](GlobalValue::GUID ValueGUID) {
 181     if (CfiFunctionDefs.count(ValueGUID))
 182       UsedCfiDefs.insert(ValueGUID);
 183     if (CfiFunctionDecls.count(ValueGUID))
 184       UsedCfiDecls.insert(ValueGUID);
 185   };
 186
 187   auto AddUsedThings = [&](GlobalValueSummary *GS) {
 188     if (!GS) return;
 189     AddUnsigned(GS->isLive());
 190     AddUnsigned(GS->canAutoHide());
 191     for (const ValueInfo &VI : GS->refs()) {
 192       AddUnsigned(VI.isDSOLocal());
 193       AddUsedCfiGlobal(VI.getGUID());
 194     }
 195     if (auto *GVS = dyn_cast<GlobalVarSummary>(GS))
 196       AddUnsigned(GVS->isReadOnly());
 197     if (auto *FS = dyn_cast<FunctionSummary>(GS)) {
 198       for (auto &TT : FS->type_tests())
 199         UsedTypeIds.insert(TT);
 200       for (auto &TT : FS->type_test_assume_vcalls())
 201         UsedTypeIds.insert(TT.GUID);
 202       for (auto &TT : FS->type_checked_load_vcalls())
 203         UsedTypeIds.insert(TT.GUID);
 204       for (auto &TT : FS->type_test_assume_const_vcalls())
 205         UsedTypeIds.insert(TT.VFunc.GUID);
 206       for (auto &TT : FS->type_checked_load_const_vcalls())
 207         UsedTypeIds.insert(TT.VFunc.GUID);
 208       for (auto &ET : FS->calls()) {
 209         AddUnsigned(ET.first.isDSOLocal());
 210         AddUsedCfiGlobal(ET.first.getGUID());
 211       }
 212     }
 213   };
 214
 215   // Include the hash for the linkage type to reflect internalization and weak
 216   // resolution, and collect any used type identifier resolutions.
 217   for (auto &GS : DefinedGlobals) {
 218     GlobalValue::LinkageTypes Linkage = GS.second->linkage();
 219     Hasher.update(
 220         ArrayRef<uint8_t>((const uint8_t *)&Linkage, sizeof(Linkage)));
 221     AddUsedCfiGlobal(GS.first);
 222     AddUsedThings(GS.second);
 223   }
 224
 225   // Imported functions may introduce new uses of type identifier resolutions,
 226   // so we need to collect their used resolutions as well.
 227   for (auto &ImpM : ImportList)
 228     for (auto &ImpF : ImpM.second) {
 229       GlobalValueSummary *S = Index.findSummaryInModule(ImpF, ImpM.first());
 230       AddUsedThings(S);
 231       // If this is an alias, we also care about any types/etc. that the aliasee
 232       // may reference.
 233       if (auto *AS = dyn_cast_or_null<AliasSummary>(S))
 234         AddUsedThings(AS->getBaseObject());
 235     }
 236
 237   auto AddTypeIdSummary = [&](StringRef TId, const TypeIdSummary &S) {
 238     AddString(TId);
 239
 240     AddUnsigned(S.TTRes.TheKind);
 241     AddUnsigned(S.TTRes.SizeM1BitWidth);
 242
 243     AddUint64(S.TTRes.AlignLog2);
 244     AddUint64(S.TTRes.SizeM1);
 245     AddUint64(S.TTRes.BitMask);
 246     AddUint64(S.TTRes.InlineBits);
 247
 248     AddUint64(S.WPDRes.size());
 249     for (auto &WPD : S.WPDRes) {
 250       AddUnsigned(WPD.first);
 251       AddUnsigned(WPD.second.TheKind);
 252       AddString(WPD.second.SingleImplName);
 253
 254       AddUint64(WPD.second.ResByArg.size());
 255       for (auto &ByArg : WPD.second.ResByArg) {
 256         AddUint64(ByArg.first.size());
 257         for (uint64_t Arg : ByArg.first)
 258           AddUint64(Arg);
 259         AddUnsigned(ByArg.second.TheKind);
 260         AddUint64(ByArg.second.Info);
 261         AddUnsigned(ByArg.second.Byte);
 262         AddUnsigned(ByArg.second.Bit);
 263       }
 264     }
 265   };
 266
 267   // Include the hash for all type identifiers used by this module.
 268   for (GlobalValue::GUID TId : UsedTypeIds) {
 269     auto TidIter = Index.typeIds().equal_range(TId);
 270     for (auto It = TidIter.first; It != TidIter.second; ++It)
 271       AddTypeIdSummary(It->second.first, It->second.second);
 272   }
 273
 274   AddUnsigned(UsedCfiDefs.size());
 275   for (auto &V : UsedCfiDefs)
 276     AddUint64(V);
 277
 278   AddUnsigned(UsedCfiDecls.size());
 279   for (auto &V : UsedCfiDecls)
 280     AddUint64(V);
 281
 282   if (!Conf.SampleProfile.empty()) {
 283     auto FileOrErr = MemoryBuffer::getFile(Conf.SampleProfile);
 284     if (FileOrErr) {
 285       Hasher.update(FileOrErr.get()->getBuffer());
 286
 287       if (!Conf.ProfileRemapping.empty()) {
 288         FileOrErr = MemoryBuffer::getFile(Conf.ProfileRemapping);
 289         if (FileOrErr)
 290           Hasher.update(FileOrErr.get()->getBuffer());
 291       }
 292     }
 293   }
 294
 295   Key = toHex(Hasher.result());
 296 }
 297
 298 static void thinLTOResolvePrevailingGUID(
 299     ValueInfo VI, DenseSet<GlobalValueSummary *> &GlobalInvolvedWithAlias,
 300     function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
 301         isPrevailing,
 302     function_ref<void(StringRef, GlobalValue::GUID, GlobalValue::LinkageTypes)>
 303         recordNewLinkage,
 304     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
 305   for (auto &S : VI.getSummaryList()) {
 306     GlobalValue::LinkageTypes OriginalLinkage = S->linkage();
 307     // Ignore local and appending linkage values since the linker
 308     // doesn't resolve them.
 309     if (GlobalValue::isLocalLinkage(OriginalLinkage) ||
 310         GlobalValue::isAppendingLinkage(S->linkage()))
 311       continue;
 312     // We need to emit only one of these. The prevailing module will keep it,
 313     // but turned into a weak, while the others will drop it when possible.
 314     // This is both a compile-time optimization and a correctness
 315     // transformation. This is necessary for correctness when we have exported
 316     // a reference - we need to convert the linkonce to weak to
 317     // ensure a copy is kept to satisfy the exported reference.
 318     // FIXME: We may want to split the compile time and correctness
 319     // aspects into separate routines.
 320     if (isPrevailing(VI.getGUID(), S.get())) {
 321       if (GlobalValue::isLinkOnceLinkage(OriginalLinkage)) {
 322         S->setLinkage(GlobalValue::getWeakLinkage(
 323             GlobalValue::isLinkOnceODRLinkage(OriginalLinkage)));
 324         // The kept copy is eligible for auto-hiding (hidden visibility) if all
 325         // copies were (i.e. they were all linkonce_odr global unnamed addr).
 326         // If any copy is not (e.g. it was originally weak_odr), then the symbol
 327         // must remain externally available (e.g. a weak_odr from an explicitly
 328         // instantiated template). Additionally, if it is in the
 329         // GUIDPreservedSymbols set, that means that it is visibile outside
 330         // the summary (e.g. in a native object or a bitcode file without
 331         // summary), and in that case we cannot hide it as it isn't possible to
 332         // check all copies.
 333         S->setCanAutoHide(VI.canAutoHide() &&
 334                           !GUIDPreservedSymbols.count(VI.getGUID()));
 335       }
 336     }
 337     // Alias and aliasee can't be turned into available_externally.
 338     else if (!isa<AliasSummary>(S.get()) &&
 339              !GlobalInvolvedWithAlias.count(S.get()))
 340       S->setLinkage(GlobalValue::AvailableExternallyLinkage);
 341     if (S->linkage() != OriginalLinkage)
 342       recordNewLinkage(S->modulePath(), VI.getGUID(), S->linkage());
 343   }
 344 }
 345
 346 /// Resolve linkage for prevailing symbols in the \p Index.
 347 //
 348 // We'd like to drop these functions if they are no longer referenced in the
 349 // current module. However there is a chance that another module is still
 350 // referencing them because of the import. We make sure we always emit at least
 351 // one copy.
 352 void llvm::thinLTOResolvePrevailingInIndex(
 353     ModuleSummaryIndex &Index,
 354     function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
 355         isPrevailing,
 356     function_ref<void(StringRef, GlobalValue::GUID, GlobalValue::LinkageTypes)>
 357         recordNewLinkage,
 358     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
 359   // We won't optimize the globals that are referenced by an alias for now
 360   // Ideally we should turn the alias into a global and duplicate the definition
 361   // when needed.
 362   DenseSet<GlobalValueSummary *> GlobalInvolvedWithAlias;
 363   for (auto &I : Index)
 364     for (auto &S : I.second.SummaryList)
 365       if (auto AS = dyn_cast<AliasSummary>(S.get()))
 366         GlobalInvolvedWithAlias.insert(&AS->getAliasee());
 367
 368   for (auto &I : Index)
 369     thinLTOResolvePrevailingGUID(Index.getValueInfo(I), GlobalInvolvedWithAlias,
 370                                  isPrevailing, recordNewLinkage,
 371                                  GUIDPreservedSymbols);
 372 }
 373
 374 static bool isWeakWriteableObject(GlobalValueSummary *GVS) {
 375   if (auto *VarSummary = dyn_cast<GlobalVarSummary>(GVS->getBaseObject()))
 376     return !VarSummary->isReadOnly() &&
 377            (VarSummary->linkage() == GlobalValue::WeakODRLinkage ||
 378             VarSummary->linkage() == GlobalValue::LinkOnceODRLinkage);
 379   return false;
 380 }
 381
 382 static void thinLTOInternalizeAndPromoteGUID(
 383     GlobalValueSummaryList &GVSummaryList, GlobalValue::GUID GUID,
 384     function_ref<bool(StringRef, GlobalValue::GUID)> isExported) {
 385   for (auto &S : GVSummaryList) {
 386     if (isExported(S->modulePath(), GUID)) {
 387       if (GlobalValue::isLocalLinkage(S->linkage()))
 388         S->setLinkage(GlobalValue::ExternalLinkage);
 389     } else if (EnableLTOInternalization &&
 390                // Ignore local and appending linkage values since the linker
 391                // doesn't resolve them.
 392                !GlobalValue::isLocalLinkage(S->linkage()) &&
 393                S->linkage() != GlobalValue::AppendingLinkage &&
 394                // We can't internalize available_externally globals because this
 395                // can break function pointer equality.
 396                S->linkage() != GlobalValue::AvailableExternallyLinkage &&
 397                // Functions and read-only variables with linkonce_odr and weak_odr
 398                // linkage can be internalized. We can't internalize linkonce_odr
 399                // and weak_odr variables which are modified somewhere in the
 400                // program because reads and writes will become inconsistent.
 401                !isWeakWriteableObject(S.get()))
 402       S->setLinkage(GlobalValue::InternalLinkage);
 403   }
 404 }
 405
 406 // Update the linkages in the given \p Index to mark exported values
 407 // as external and non-exported values as internal.
 408 void llvm::thinLTOInternalizeAndPromoteInIndex(
 409     ModuleSummaryIndex &Index,
 410     function_ref<bool(StringRef, GlobalValue::GUID)> isExported) {
 411   for (auto &I : Index)
 412     thinLTOInternalizeAndPromoteGUID(I.second.SummaryList, I.first, isExported);
 413 }
 414
 415 // Requires a destructor for std::vector<InputModule>.
 416 InputFile::~InputFile() = default;
 417
 418 Expected<std::unique_ptr<InputFile>> InputFile::create(MemoryBufferRef Object) {
 419   std::unique_ptr<InputFile> File(new InputFile);
 420
 421   Expected<IRSymtabFile> FOrErr = readIRSymtab(Object);
 422   if (!FOrErr)
 423     return FOrErr.takeError();
 424
 425   File->TargetTriple = FOrErr->TheReader.getTargetTriple();
 426   File->SourceFileName = FOrErr->TheReader.getSourceFileName();
 427   File->COFFLinkerOpts = FOrErr->TheReader.getCOFFLinkerOpts();
 428   File->ComdatTable = FOrErr->TheReader.getComdatTable();
 429
 430   for (unsigned I = 0; I != FOrErr->Mods.size(); ++I) {
 431     size_t Begin = File->Symbols.size();
 432     for (const irsymtab::Reader::SymbolRef &Sym :
 433          FOrErr->TheReader.module_symbols(I))
 434       // Skip symbols that are irrelevant to LTO. Note that this condition needs
 435       // to match the one in Skip() in LTO::addRegularLTO().
 436       if (Sym.isGlobal() && !Sym.isFormatSpecific())
 437         File->Symbols.push_back(Sym);
 438     File->ModuleSymIndices.push_back({Begin, File->Symbols.size()});
 439   }
 440
 441   File->Mods = FOrErr->Mods;
 442   File->Strtab = std::move(FOrErr->Strtab);
 443   return std::move(File);
 444 }
 445
 446 StringRef InputFile::getName() const {
 447   return Mods[0].getModuleIdentifier();
 448 }
 449
 450 BitcodeModule &InputFile::getSingleBitcodeModule() {
 451   assert(Mods.size() == 1 && "Expect only one bitcode module");
 452   return Mods[0];
 453 }
 454
 455 LTO::RegularLTOState::RegularLTOState(unsigned ParallelCodeGenParallelismLevel,
 456                                       Config &Conf)
 457     : ParallelCodeGenParallelismLevel(ParallelCodeGenParallelismLevel),
 458       Ctx(Conf), CombinedModule(llvm::make_unique<Module>("ld-temp.o", Ctx)),
 459       Mover(llvm::make_unique<IRMover>(*CombinedModule)) {}
 460
 461 LTO::ThinLTOState::ThinLTOState(ThinBackend Backend)
 462     : Backend(Backend), CombinedIndex(/*HaveGVs*/ false) {
 463   if (!Backend)
 464     this->Backend =
 465         createInProcessThinBackend(llvm::heavyweight_hardware_concurrency());
 466 }
 467
 468 LTO::LTO(Config Conf, ThinBackend Backend,
 469          unsigned ParallelCodeGenParallelismLevel)
 470     : Conf(std::move(Conf)),
 471       RegularLTO(ParallelCodeGenParallelismLevel, this->Conf),
 472       ThinLTO(std::move(Backend)) {}
 473
 474 // Requires a destructor for MapVector<BitcodeModule>.
 475 LTO::~LTO() = default;
 476
 477 // Add the symbols in the given module to the GlobalResolutions map, and resolve
 478 // their partitions.
 479 void LTO::addModuleToGlobalRes(ArrayRef<InputFile::Symbol> Syms,
 480                                ArrayRef<SymbolResolution> Res,
 481                                unsigned Partition, bool InSummary) {
 482   auto *ResI = Res.begin();
 483   auto *ResE = Res.end();
 484   (void)ResE;
 485   for (const InputFile::Symbol &Sym : Syms) {
 486     assert(ResI != ResE);
 487     SymbolResolution Res = *ResI++;
 488
 489     StringRef Name = Sym.getName();
 490     Triple TT(RegularLTO.CombinedModule->getTargetTriple());
 491     // Strip the __imp_ prefix from COFF dllimport symbols (similar to the
 492     // way they are handled by lld), otherwise we can end up with two
 493     // global resolutions (one with and one for a copy of the symbol without).
 494     if (TT.isOSBinFormatCOFF() && Name.startswith("__imp_"))
 495       Name = Name.substr(strlen("__imp_"));
 496     auto &GlobalRes = GlobalResolutions[Name];
 497     GlobalRes.UnnamedAddr &= Sym.isUnnamedAddr();
 498     if (Res.Prevailing) {
 499       assert(!GlobalRes.Prevailing &&
 500              "Multiple prevailing defs are not allowed");
 501       GlobalRes.Prevailing = true;
 502       GlobalRes.IRName = Sym.getIRName();
 503     } else if (!GlobalRes.Prevailing && GlobalRes.IRName.empty()) {
 504       // Sometimes it can be two copies of symbol in a module and prevailing
 505       // symbol can have no IR name. That might happen if symbol is defined in
 506       // module level inline asm block. In case we have multiple modules with
 507       // the same symbol we want to use IR name of the prevailing symbol.
 508       // Otherwise, if we haven't seen a prevailing symbol, set the name so that
 509       // we can later use it to check if there is any prevailing copy in IR.
 510       GlobalRes.IRName = Sym.getIRName();
 511     }
 512
 513     // Set the partition to external if we know it is re-defined by the linker
 514     // with -defsym or -wrap options, used elsewhere, e.g. it is visible to a
 515     // regular object, is referenced from llvm.compiler_used, or was already
 516     // recorded as being referenced from a different partition.
 517     if (Res.LinkerRedefined || Res.VisibleToRegularObj || Sym.isUsed() ||
 518         (GlobalRes.Partition != GlobalResolution::Unknown &&
 519          GlobalRes.Partition != Partition)) {
 520       GlobalRes.Partition = GlobalResolution::External;
 521     } else
 522       // First recorded reference, save the current partition.
 523       GlobalRes.Partition = Partition;
 524
 525     // Flag as visible outside of summary if visible from a regular object or
 526     // from a module that does not have a summary.
 527     GlobalRes.VisibleOutsideSummary |=
 528         (Res.VisibleToRegularObj || Sym.isUsed() || !InSummary);
 529   }
 530 }
 531
 532 static void writeToResolutionFile(raw_ostream &OS, InputFile *Input,
 533                                   ArrayRef<SymbolResolution> Res) {
 534   StringRef Path = Input->getName();
 535   OS << Path << '\n';
 536   auto ResI = Res.begin();
 537   for (const InputFile::Symbol &Sym : Input->symbols()) {
 538     assert(ResI != Res.end());
 539     SymbolResolution Res = *ResI++;
 540
 541     OS << "-r=" << Path << ',' << Sym.getName() << ',';
 542     if (Res.Prevailing)
 543       OS << 'p';
 544     if (Res.FinalDefinitionInLinkageUnit)
 545       OS << 'l';
 546     if (Res.VisibleToRegularObj)
 547       OS << 'x';
 548     if (Res.LinkerRedefined)
 549       OS << 'r';
 550     OS << '\n';
 551   }
 552   OS.flush();
 553   assert(ResI == Res.end());
 554 }
 555
 556 Error LTO::add(std::unique_ptr<InputFile> Input,
 557                ArrayRef<SymbolResolution> Res) {
 558   assert(!CalledGetMaxTasks);
 559
 560   if (Conf.ResolutionFile)
 561     writeToResolutionFile(*Conf.ResolutionFile, Input.get(), Res);
 562
 563   if (RegularLTO.CombinedModule->getTargetTriple().empty())
 564     RegularLTO.CombinedModule->setTargetTriple(Input->getTargetTriple());
 565
 566   const SymbolResolution *ResI = Res.begin();
 567   for (unsigned I = 0; I != Input->Mods.size(); ++I)
 568     if (Error Err = addModule(*Input, I, ResI, Res.end()))
 569       return Err;
 570
 571   assert(ResI == Res.end());
 572   return Error::success();
 573 }
 574
 575 Error LTO::addModule(InputFile &Input, unsigned ModI,
 576                      const SymbolResolution *&ResI,
 577                      const SymbolResolution *ResE) {
 578   Expected<BitcodeLTOInfo> LTOInfo = Input.Mods[ModI].getLTOInfo();
 579   if (!LTOInfo)
 580     return LTOInfo.takeError();
 581
 582   if (EnableSplitLTOUnit.hasValue()) {
 583     // If only some modules were split, flag this in the index so that
 584     // we can skip or error on optimizations that need consistently split
 585     // modules (whole program devirt and lower type tests).
 586     if (EnableSplitLTOUnit.getValue() != LTOInfo->EnableSplitLTOUnit)
 587       ThinLTO.CombinedIndex.setPartiallySplitLTOUnits();
 588   } else
 589     EnableSplitLTOUnit = LTOInfo->EnableSplitLTOUnit;
 590
 591   BitcodeModule BM = Input.Mods[ModI];
 592   auto ModSyms = Input.module_symbols(ModI);
 593   addModuleToGlobalRes(ModSyms, {ResI, ResE},
 594                        LTOInfo->IsThinLTO ? ThinLTO.ModuleMap.size() + 1 : 0,
 595                        LTOInfo->HasSummary);
 596
 597   if (LTOInfo->IsThinLTO)
 598     return addThinLTO(BM, ModSyms, ResI, ResE);
 599
 600   Expected<RegularLTOState::AddedModule> ModOrErr =
 601       addRegularLTO(BM, ModSyms, ResI, ResE);
 602   if (!ModOrErr)
 603     return ModOrErr.takeError();
 604
 605   if (!LTOInfo->HasSummary)
 606     return linkRegularLTO(std::move(*ModOrErr), /*LivenessFromIndex=*/false);
 607
 608   // Regular LTO module summaries are added to a dummy module that represents
 609   // the combined regular LTO module.
 610   if (Error Err = BM.readSummary(ThinLTO.CombinedIndex, "", -1ull))
 611     return Err;
 612   RegularLTO.ModsWithSummaries.push_back(std::move(*ModOrErr));
 613   return Error::success();
 614 }
 615
 616 // Checks whether the given global value is in a non-prevailing comdat
 617 // (comdat containing values the linker indicated were not prevailing,
 618 // which we then dropped to available_externally), and if so, removes
 619 // it from the comdat. This is called for all global values to ensure the
 620 // comdat is empty rather than leaving an incomplete comdat. It is needed for
 621 // regular LTO modules, in case we are in a mixed-LTO mode (both regular
 622 // and thin LTO modules) compilation. Since the regular LTO module will be
 623 // linked first in the final native link, we want to make sure the linker
 624 // doesn't select any of these incomplete comdats that would be left
 625 // in the regular LTO module without this cleanup.
 626 static void
 627 handleNonPrevailingComdat(GlobalValue &GV,
 628                           std::set<const Comdat *> &NonPrevailingComdats) {
 629   Comdat *C = GV.getComdat();
 630   if (!C)
 631     return;
 632
 633   if (!NonPrevailingComdats.count(C))
 634     return;
 635
 636   // Additionally need to drop externally visible global values from the comdat
 637   // to available_externally, so that there aren't multiply defined linker
 638   // errors.
 639   if (!GV.hasLocalLinkage())
 640     GV.setLinkage(GlobalValue::AvailableExternallyLinkage);
 641
 642   if (auto GO = dyn_cast<GlobalObject>(&GV))
 643     GO->setComdat(nullptr);
 644 }
 645
 646 // Add a regular LTO object to the link.
 647 // The resulting module needs to be linked into the combined LTO module with
 648 // linkRegularLTO.
 649 Expected<LTO::RegularLTOState::AddedModule>
 650 LTO::addRegularLTO(BitcodeModule BM, ArrayRef<InputFile::Symbol> Syms,
 651                    const SymbolResolution *&ResI,
 652                    const SymbolResolution *ResE) {
 653   RegularLTOState::AddedModule Mod;
 654   Expected<std::unique_ptr<Module>> MOrErr =
 655       BM.getLazyModule(RegularLTO.Ctx, /*ShouldLazyLoadMetadata*/ true,
 656                        /*IsImporting*/ false);
 657   if (!MOrErr)
 658     return MOrErr.takeError();
 659   Module &M = **MOrErr;
 660   Mod.M = std::move(*MOrErr);
 661
 662   if (Error Err = M.materializeMetadata())
 663     return std::move(Err);
 664   UpgradeDebugInfo(M);
 665
 666   ModuleSymbolTable SymTab;
 667   SymTab.addModule(&M);
 668
 669   for (GlobalVariable &GV : M.globals())
 670     if (GV.hasAppendingLinkage())
 671       Mod.Keep.push_back(&GV);
 672
 673   DenseSet<GlobalObject *> AliasedGlobals;
 674   for (auto &GA : M.aliases())
 675     if (GlobalObject *GO = GA.getBaseObject())
 676       AliasedGlobals.insert(GO);
 677
 678   // In this function we need IR GlobalValues matching the symbols in Syms
 679   // (which is not backed by a module), so we need to enumerate them in the same
 680   // order. The symbol enumeration order of a ModuleSymbolTable intentionally
 681   // matches the order of an irsymtab, but when we read the irsymtab in
 682   // InputFile::create we omit some symbols that are irrelevant to LTO. The
 683   // Skip() function skips the same symbols from the module as InputFile does
 684   // from the symbol table.
 685   auto MsymI = SymTab.symbols().begin(), MsymE = SymTab.symbols().end();
 686   auto Skip = [&]() {
 687     while (MsymI != MsymE) {
 688       auto Flags = SymTab.getSymbolFlags(*MsymI);
 689       if ((Flags & object::BasicSymbolRef::SF_Global) &&
 690           !(Flags & object::BasicSymbolRef::SF_FormatSpecific))
 691         return;
 692       ++MsymI;
 693     }
 694   };
 695   Skip();
 696
 697   std::set<const Comdat *> NonPrevailingComdats;
 698   for (const InputFile::Symbol &Sym : Syms) {
 699     assert(ResI != ResE);
 700     SymbolResolution Res = *ResI++;
 701
 702     assert(MsymI != MsymE);
 703     ModuleSymbolTable::Symbol Msym = *MsymI++;
 704     Skip();
 705
 706     if (GlobalValue *GV = Msym.dyn_cast<GlobalValue *>()) {
 707       if (Res.Prevailing) {
 708         if (Sym.isUndefined())
 709           continue;
 710         Mod.Keep.push_back(GV);
 711         // For symbols re-defined with linker -wrap and -defsym options,
 712         // set the linkage to weak to inhibit IPO. The linkage will be
 713         // restored by the linker.
 714         if (Res.LinkerRedefined)
 715           GV->setLinkage(GlobalValue::WeakAnyLinkage);
 716
 717         GlobalValue::LinkageTypes OriginalLinkage = GV->getLinkage();
 718         if (GlobalValue::isLinkOnceLinkage(OriginalLinkage))
 719           GV->setLinkage(GlobalValue::getWeakLinkage(
 720               GlobalValue::isLinkOnceODRLinkage(OriginalLinkage)));
 721       } else if (isa<GlobalObject>(GV) &&
 722                  (GV->hasLinkOnceODRLinkage() || GV->hasWeakODRLinkage() ||
 723                   GV->hasAvailableExternallyLinkage()) &&
 724                  !AliasedGlobals.count(cast<GlobalObject>(GV))) {
 725         // Any of the above three types of linkage indicates that the
 726         // chosen prevailing symbol will have the same semantics as this copy of
 727         // the symbol, so we may be able to link it with available_externally
 728         // linkage. We will decide later whether to do that when we link this
 729         // module (in linkRegularLTO), based on whether it is undefined.
 730         Mod.Keep.push_back(GV);
 731         GV->setLinkage(GlobalValue::AvailableExternallyLinkage);
 732         if (GV->hasComdat())
 733           NonPrevailingComdats.insert(GV->getComdat());
 734         cast<GlobalObject>(GV)->setComdat(nullptr);
 735       }
 736
 737       // Set the 'local' flag based on the linker resolution for this symbol.
 738       if (Res.FinalDefinitionInLinkageUnit) {
 739         GV->setDSOLocal(true);
 740         if (GV->hasDLLImportStorageClass())
 741           GV->setDLLStorageClass(GlobalValue::DLLStorageClassTypes::
 742                                  DefaultStorageClass);
 743       }
 744     }
 745     // Common resolution: collect the maximum size/alignment over all commons.
 746     // We also record if we see an instance of a common as prevailing, so that
 747     // if none is prevailing we can ignore it later.
 748     if (Sym.isCommon()) {
 749       // FIXME: We should figure out what to do about commons defined by asm.
 750       // For now they aren't reported correctly by ModuleSymbolTable.
 751       auto &CommonRes = RegularLTO.Commons[Sym.getIRName()];
 752       CommonRes.Size = std::max(CommonRes.Size, Sym.getCommonSize());
 753       CommonRes.Align = std::max(CommonRes.Align, Sym.getCommonAlignment());
 754       CommonRes.Prevailing |= Res.Prevailing;
 755     }
 756
 757   }
 758   if (!M.getComdatSymbolTable().empty())
 759     for (GlobalValue &GV : M.global_values())
 760       handleNonPrevailingComdat(GV, NonPrevailingComdats);
 761   assert(MsymI == MsymE);
 762   return std::move(Mod);
 763 }
 764
 765 Error LTO::linkRegularLTO(RegularLTOState::AddedModule Mod,
 766                           bool LivenessFromIndex) {
 767   std::vector<GlobalValue *> Keep;
 768   for (GlobalValue *GV : Mod.Keep) {
 769     if (LivenessFromIndex && !ThinLTO.CombinedIndex.isGUIDLive(GV->getGUID()))
 770       continue;
 771
 772     if (!GV->hasAvailableExternallyLinkage()) {
 773       Keep.push_back(GV);
 774       continue;
 775     }
 776
 777     // Only link available_externally definitions if we don't already have a
 778     // definition.
 779     GlobalValue *CombinedGV =
 780         RegularLTO.CombinedModule->getNamedValue(GV->getName());
 781     if (CombinedGV && !CombinedGV->isDeclaration())
 782       continue;
 783
 784     Keep.push_back(GV);
 785   }
 786
 787   return RegularLTO.Mover->move(std::move(Mod.M), Keep,
 788                                 [](GlobalValue &, IRMover::ValueAdder) {},
 789                                 /* IsPerformingImport */ false);
 790 }
 791
 792 // Add a ThinLTO module to the link.
 793 Error LTO::addThinLTO(BitcodeModule BM, ArrayRef<InputFile::Symbol> Syms,
 794                       const SymbolResolution *&ResI,
 795                       const SymbolResolution *ResE) {
 796   if (Error Err =
 797           BM.readSummary(ThinLTO.CombinedIndex, BM.getModuleIdentifier(),
 798                          ThinLTO.ModuleMap.size()))
 799     return Err;
 800
 801   for (const InputFile::Symbol &Sym : Syms) {
 802     assert(ResI != ResE);
 803     SymbolResolution Res = *ResI++;
 804
 805     if (!Sym.getIRName().empty()) {
 806       auto GUID = GlobalValue::getGUID(GlobalValue::getGlobalIdentifier(
 807           Sym.getIRName(), GlobalValue::ExternalLinkage, ""));
 808       if (Res.Prevailing) {
 809         ThinLTO.PrevailingModuleForGUID[GUID] = BM.getModuleIdentifier();
 810
 811         // For linker redefined symbols (via --wrap or --defsym) we want to
 812         // switch the linkage to `weak` to prevent IPOs from happening.
 813         // Find the summary in the module for this very GV and record the new
 814         // linkage so that we can switch it when we import the GV.
 815         if (Res.LinkerRedefined)
 816           if (auto S = ThinLTO.CombinedIndex.findSummaryInModule(
 817                   GUID, BM.getModuleIdentifier()))
 818             S->setLinkage(GlobalValue::WeakAnyLinkage);
 819       }
 820
 821       // If the linker resolved the symbol to a local definition then mark it
 822       // as local in the summary for the module we are adding.
 823       if (Res.FinalDefinitionInLinkageUnit) {
 824         if (auto S = ThinLTO.CombinedIndex.findSummaryInModule(
 825                 GUID, BM.getModuleIdentifier())) {
 826           S->setDSOLocal(true);
 827         }
 828       }
 829     }
 830   }
 831
 832   if (!ThinLTO.ModuleMap.insert({BM.getModuleIdentifier(), BM}).second)
 833     return make_error<StringError>(
 834         "Expected at most one ThinLTO module per bitcode file",
 835         inconvertibleErrorCode());
 836
 837   return Error::success();
 838 }
 839
 840 unsigned LTO::getMaxTasks() const {
 841   CalledGetMaxTasks = true;
 842   return RegularLTO.ParallelCodeGenParallelismLevel + ThinLTO.ModuleMap.size();
 843 }
 844
 845 // If only some of the modules were split, we cannot correctly handle
 846 // code that contains type tests or type checked loads.
 847 Error LTO::checkPartiallySplit() {
 848   if (!ThinLTO.CombinedIndex.partiallySplitLTOUnits())
 849     return Error::success();
 850
 851   Function *TypeTestFunc = RegularLTO.CombinedModule->getFunction(
 852       Intrinsic::getName(Intrinsic::type_test));
 853   Function *TypeCheckedLoadFunc = RegularLTO.CombinedModule->getFunction(
 854       Intrinsic::getName(Intrinsic::type_checked_load));
 855
 856   // First check if there are type tests / type checked loads in the
 857   // merged regular LTO module IR.
 858   if ((TypeTestFunc && !TypeTestFunc->use_empty()) ||
 859       (TypeCheckedLoadFunc && !TypeCheckedLoadFunc->use_empty()))
 860     return make_error<StringError>(
 861         "inconsistent LTO Unit splitting (recompile with -fsplit-lto-unit)",
 862         inconvertibleErrorCode());
 863
 864   // Otherwise check if there are any recorded in the combined summary from the
 865   // ThinLTO modules.
 866   for (auto &P : ThinLTO.CombinedIndex) {
 867     for (auto &S : P.second.SummaryList) {
 868       auto *FS = dyn_cast<FunctionSummary>(S.get());
 869       if (!FS)
 870         continue;
 871       if (!FS->type_test_assume_vcalls().empty() ||
 872           !FS->type_checked_load_vcalls().empty() ||
 873           !FS->type_test_assume_const_vcalls().empty() ||
 874           !FS->type_checked_load_const_vcalls().empty() ||
 875           !FS->type_tests().empty())
 876         return make_error<StringError>(
 877             "inconsistent LTO Unit splitting (recompile with -fsplit-lto-unit)",
 878             inconvertibleErrorCode());
 879     }
 880   }
 881   return Error::success();
 882 }
 883
 884 Error LTO::run(AddStreamFn AddStream, NativeObjectCache Cache) {
 885   // Compute "dead" symbols, we don't want to import/export these!
 886   DenseSet<GlobalValue::GUID> GUIDPreservedSymbols;
 887   DenseMap<GlobalValue::GUID, PrevailingType> GUIDPrevailingResolutions;
 888   for (auto &Res : GlobalResolutions) {
 889     // Normally resolution have IR name of symbol. We can do nothing here
 890     // otherwise. See comments in GlobalResolution struct for more details.
 891     if (Res.second.IRName.empty())
 892       continue;
 893
 894     GlobalValue::GUID GUID = GlobalValue::getGUID(
 895         GlobalValue::dropLLVMManglingEscape(Res.second.IRName));
 896
 897     if (Res.second.VisibleOutsideSummary && Res.second.Prevailing)
 898       GUIDPreservedSymbols.insert(GlobalValue::getGUID(
 899           GlobalValue::dropLLVMManglingEscape(Res.second.IRName)));
 900
 901     GUIDPrevailingResolutions[GUID] =
 902         Res.second.Prevailing ? PrevailingType::Yes : PrevailingType::No;
 903   }
 904
 905   auto isPrevailing = [&](GlobalValue::GUID G) {
 906     auto It = GUIDPrevailingResolutions.find(G);
 907     if (It == GUIDPrevailingResolutions.end())
 908       return PrevailingType::Unknown;
 909     return It->second;
 910   };
 911   computeDeadSymbolsWithConstProp(ThinLTO.CombinedIndex, GUIDPreservedSymbols,
 912                                   isPrevailing, Conf.OptLevel > 0);
 913
 914   // Setup output file to emit statistics.
 915   auto StatsFileOrErr = setupStatsFile(Conf.StatsFile);
 916   if (!StatsFileOrErr)
 917     return StatsFileOrErr.takeError();
 918   std::unique_ptr<ToolOutputFile> StatsFile = std::move(StatsFileOrErr.get());
 919
 920   // Finalize linking of regular LTO modules containing summaries now that
 921   // we have computed liveness information.
 922   for (auto &M : RegularLTO.ModsWithSummaries)
 923     if (Error Err = linkRegularLTO(std::move(M),
 924                                    /*LivenessFromIndex=*/true))
 925       return Err;
 926
 927   // Ensure we don't have inconsistently split LTO units with type tests.
 928   if (Error Err = checkPartiallySplit())
 929     return Err;
 930
 931   Error Result = runRegularLTO(AddStream);
 932   if (!Result)
 933     Result = runThinLTO(AddStream, Cache, GUIDPreservedSymbols);
 934
 935   if (StatsFile)
 936     PrintStatisticsJSON(StatsFile->os());
 937
 938   return Result;
 939 }
 940
 941 Error LTO::runRegularLTO(AddStreamFn AddStream) {
 942   // Make sure commons have the right size/alignment: we kept the largest from
 943   // all the prevailing when adding the inputs, and we apply it here.
 944   const DataLayout &DL = RegularLTO.CombinedModule->getDataLayout();
 945   for (auto &I : RegularLTO.Commons) {
 946     if (!I.second.Prevailing)
 947       // Don't do anything if no instance of this common was prevailing.
 948       continue;
 949     GlobalVariable *OldGV = RegularLTO.CombinedModule->getNamedGlobal(I.first);
 950     if (OldGV && DL.getTypeAllocSize(OldGV->getValueType()) == I.second.Size) {
 951       // Don't create a new global if the type is already correct, just make
 952       // sure the alignment is correct.
 953       OldGV->setAlignment(I.second.Align);
 954       continue;
 955     }
 956     ArrayType *Ty =
 957         ArrayType::get(Type::getInt8Ty(RegularLTO.Ctx), I.second.Size);
 958     auto *GV = new GlobalVariable(*RegularLTO.CombinedModule, Ty, false,
 959                                   GlobalValue::CommonLinkage,
 960                                   ConstantAggregateZero::get(Ty), "");
 961     GV->setAlignment(I.second.Align);
 962     if (OldGV) {
 963       OldGV->replaceAllUsesWith(ConstantExpr::getBitCast(GV, OldGV->getType()));
 964       GV->takeName(OldGV);
 965       OldGV->eraseFromParent();
 966     } else {
 967       GV->setName(I.first);
 968     }
 969   }
 970
 971   if (Conf.PreOptModuleHook &&
 972       !Conf.PreOptModuleHook(0, *RegularLTO.CombinedModule))
 973     return Error::success();
 974
 975   if (!Conf.CodeGenOnly) {
 976     for (const auto &R : GlobalResolutions) {
 977       if (!R.second.isPrevailingIRSymbol())
 978         continue;
 979       if (R.second.Partition != 0 &&
 980           R.second.Partition != GlobalResolution::External)
 981         continue;
 982
 983       GlobalValue *GV =
 984           RegularLTO.CombinedModule->getNamedValue(R.second.IRName);
 985       // Ignore symbols defined in other partitions.
 986       // Also skip declarations, which are not allowed to have internal linkage.
 987       if (!GV || GV->hasLocalLinkage() || GV->isDeclaration())
 988         continue;
 989       GV->setUnnamedAddr(R.second.UnnamedAddr ? GlobalValue::UnnamedAddr::Global
 990                                               : GlobalValue::UnnamedAddr::None);
 991       if (EnableLTOInternalization && R.second.Partition == 0)
 992         GV->setLinkage(GlobalValue::InternalLinkage);
 993     }
 994
 995     if (Conf.PostInternalizeModuleHook &&
 996         !Conf.PostInternalizeModuleHook(0, *RegularLTO.CombinedModule))
 997       return Error::success();
 998   }
 999   return backend(Conf, AddStream, RegularLTO.ParallelCodeGenParallelismLevel,
1000                  std::move(RegularLTO.CombinedModule), ThinLTO.CombinedIndex);
1001 }
1002
1003 /// This class defines the interface to the ThinLTO backend.
1004 class lto::ThinBackendProc {
1005 protected:
1006   Config &Conf;
1007   ModuleSummaryIndex &CombinedIndex;
1008   const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries;
1009
1010 public:
1011   ThinBackendProc(Config &Conf, ModuleSummaryIndex &CombinedIndex,
1012                   const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries)
1013       : Conf(Conf), CombinedIndex(CombinedIndex),
1014         ModuleToDefinedGVSummaries(ModuleToDefinedGVSummaries) {}
1015
1016   virtual ~ThinBackendProc() {}
1017   virtual Error start(
1018       unsigned Task, BitcodeModule BM,
1019       const FunctionImporter::ImportMapTy &ImportList,
1020       const FunctionImporter::ExportSetTy &ExportList,
1021       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
1022       MapVector<StringRef, BitcodeModule> &ModuleMap) = 0;
1023   virtual Error wait() = 0;
1024 };
1025
1026 namespace {
1027 class InProcessThinBackend : public ThinBackendProc {
1028   ThreadPool BackendThreadPool;
1029   AddStreamFn AddStream;
1030   NativeObjectCache Cache;
1031   std::set<GlobalValue::GUID> CfiFunctionDefs;
1032   std::set<GlobalValue::GUID> CfiFunctionDecls;
1033
1034   Optional<Error> Err;
1035   std::mutex ErrMu;
1036
1037 public:
1038   InProcessThinBackend(
1039       Config &Conf, ModuleSummaryIndex &CombinedIndex,
1040       unsigned ThinLTOParallelismLevel,
1041       const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
1042       AddStreamFn AddStream, NativeObjectCache Cache)
1043       : ThinBackendProc(Conf, CombinedIndex, ModuleToDefinedGVSummaries),
1044         BackendThreadPool(ThinLTOParallelismLevel),
1045         AddStream(std::move(AddStream)), Cache(std::move(Cache)) {
1046     for (auto &Name : CombinedIndex.cfiFunctionDefs())
1047       CfiFunctionDefs.insert(
1048           GlobalValue::getGUID(GlobalValue::dropLLVMManglingEscape(Name)));
1049     for (auto &Name : CombinedIndex.cfiFunctionDecls())
1050       CfiFunctionDecls.insert(
1051           GlobalValue::getGUID(GlobalValue::dropLLVMManglingEscape(Name)));
1052   }
1053
1054   Error runThinLTOBackendThread(
1055       AddStreamFn AddStream, NativeObjectCache Cache, unsigned Task,
1056       BitcodeModule BM, ModuleSummaryIndex &CombinedIndex,
1057       const FunctionImporter::ImportMapTy &ImportList,
1058       const FunctionImporter::ExportSetTy &ExportList,
1059       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
1060       const GVSummaryMapTy &DefinedGlobals,
1061       MapVector<StringRef, BitcodeModule> &ModuleMap) {
1062     auto RunThinBackend = [&](AddStreamFn AddStream) {
1063       LTOLLVMContext BackendContext(Conf);
1064       Expected<std::unique_ptr<Module>> MOrErr = BM.parseModule(BackendContext);
1065       if (!MOrErr)
1066         return MOrErr.takeError();
1067
1068       return thinBackend(Conf, Task, AddStream, **MOrErr, CombinedIndex,
1069                          ImportList, DefinedGlobals, ModuleMap);
1070     };
1071
1072     auto ModuleID = BM.getModuleIdentifier();
1073
1074     if (!Cache || !CombinedIndex.modulePaths().count(ModuleID) ||
1075         all_of(CombinedIndex.getModuleHash(ModuleID),
1076                [](uint32_t V) { return V == 0; }))
1077       // Cache disabled or no entry for this module in the combined index or
1078       // no module hash.
1079       return RunThinBackend(AddStream);
1080
1081     SmallString<40> Key;
1082     // The module may be cached, this helps handling it.
1083     computeLTOCacheKey(Key, Conf, CombinedIndex, ModuleID, ImportList,
1084                        ExportList, ResolvedODR, DefinedGlobals, CfiFunctionDefs,
1085                        CfiFunctionDecls);
1086     if (AddStreamFn CacheAddStream = Cache(Task, Key))
1087       return RunThinBackend(CacheAddStream);
1088
1089     return Error::success();
1090   }
1091
1092   Error start(
1093       unsigned Task, BitcodeModule BM,
1094       const FunctionImporter::ImportMapTy &ImportList,
1095       const FunctionImporter::ExportSetTy &ExportList,
1096       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
1097       MapVector<StringRef, BitcodeModule> &ModuleMap) override {
1098     StringRef ModulePath = BM.getModuleIdentifier();
1099     assert(ModuleToDefinedGVSummaries.count(ModulePath));
1100     const GVSummaryMapTy &DefinedGlobals =
1101         ModuleToDefinedGVSummaries.find(ModulePath)->second;
1102     BackendThreadPool.async(
1103         [=](BitcodeModule BM, ModuleSummaryIndex &CombinedIndex,
1104             const FunctionImporter::ImportMapTy &ImportList,
1105             const FunctionImporter::ExportSetTy &ExportList,
1106             const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>
1107                 &ResolvedODR,
1108             const GVSummaryMapTy &DefinedGlobals,
1109             MapVector<StringRef, BitcodeModule> &ModuleMap) {
1110           Error E = runThinLTOBackendThread(
1111               AddStream, Cache, Task, BM, CombinedIndex, ImportList, ExportList,
1112               ResolvedODR, DefinedGlobals, ModuleMap);
1113           if (E) {
1114             std::unique_lock<std::mutex> L(ErrMu);
1115             if (Err)
1116               Err = joinErrors(std::move(*Err), std::move(E));
1117             else
1118               Err = std::move(E);
1119           }
1120         },
1121         BM, std::ref(CombinedIndex), std::ref(ImportList), std::ref(ExportList),
1122         std::ref(ResolvedODR), std::ref(DefinedGlobals), std::ref(ModuleMap));
1123     return Error::success();
1124   }
1125
1126   Error wait() override {
1127     BackendThreadPool.wait();
1128     if (Err)
1129       return std::move(*Err);
1130     else
1131       return Error::success();
1132   }
1133 };
1134 } // end anonymous namespace
1135
1136 ThinBackend lto::createInProcessThinBackend(unsigned ParallelismLevel) {
1137   return [=](Config &Conf, ModuleSummaryIndex &CombinedIndex,
1138              const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
1139              AddStreamFn AddStream, NativeObjectCache Cache) {
1140     return llvm::make_unique<InProcessThinBackend>(
1141         Conf, CombinedIndex, ParallelismLevel, ModuleToDefinedGVSummaries,
1142         AddStream, Cache);
1143   };
1144 }
1145
1146 // Given the original \p Path to an output file, replace any path
1147 // prefix matching \p OldPrefix with \p NewPrefix. Also, create the
1148 // resulting directory if it does not yet exist.
1149 std::string lto::getThinLTOOutputFile(const std::string &Path,
1150                                       const std::string &OldPrefix,
1151                                       const std::string &NewPrefix) {
1152   if (OldPrefix.empty() && NewPrefix.empty())
1153     return Path;
1154   SmallString<128> NewPath(Path);
1155   llvm::sys::path::replace_path_prefix(NewPath, OldPrefix, NewPrefix);
1156   StringRef ParentPath = llvm::sys::path::parent_path(NewPath.str());
1157   if (!ParentPath.empty()) {
1158     // Make sure the new directory exists, creating it if necessary.
1159     if (std::error_code EC = llvm::sys::fs::create_directories(ParentPath))
1160       llvm::errs() << "warning: could not create directory '" << ParentPath
1161                    << "': " << EC.message() << '\n';
1162   }
1163   return NewPath.str();
1164 }
1165
1166 namespace {
1167 class WriteIndexesThinBackend : public ThinBackendProc {
1168   std::string OldPrefix, NewPrefix;
1169   bool ShouldEmitImportsFiles;
1170   raw_fd_ostream *LinkedObjectsFile;
1171   lto::IndexWriteCallback OnWrite;
1172
1173 public:
1174   WriteIndexesThinBackend(
1175       Config &Conf, ModuleSummaryIndex &CombinedIndex,
1176       const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
1177       std::string OldPrefix, std::string NewPrefix, bool ShouldEmitImportsFiles,
1178       raw_fd_ostream *LinkedObjectsFile, lto::IndexWriteCallback OnWrite)
1179       : ThinBackendProc(Conf, CombinedIndex, ModuleToDefinedGVSummaries),
1180         OldPrefix(OldPrefix), NewPrefix(NewPrefix),
1181         ShouldEmitImportsFiles(ShouldEmitImportsFiles),
1182         LinkedObjectsFile(LinkedObjectsFile), OnWrite(OnWrite) {}
1183
1184   Error start(
1185       unsigned Task, BitcodeModule BM,
1186       const FunctionImporter::ImportMapTy &ImportList,
1187       const FunctionImporter::ExportSetTy &ExportList,
1188       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
1189       MapVector<StringRef, BitcodeModule> &ModuleMap) override {
1190     StringRef ModulePath = BM.getModuleIdentifier();
1191     std::string NewModulePath =
1192         getThinLTOOutputFile(ModulePath, OldPrefix, NewPrefix);
1193
1194     if (LinkedObjectsFile)
1195       *LinkedObjectsFile << NewModulePath << '\n';
1196
1197     std::map<std::string, GVSummaryMapTy> ModuleToSummariesForIndex;
1198     gatherImportedSummariesForModule(ModulePath, ModuleToDefinedGVSummaries,
1199                                      ImportList, ModuleToSummariesForIndex);
1200
1201     std::error_code EC;
1202     raw_fd_ostream OS(NewModulePath + ".thinlto.bc", EC,
1203                       sys::fs::OpenFlags::F_None);
1204     if (EC)
1205       return errorCodeToError(EC);
1206     WriteIndexToFile(CombinedIndex, OS, &ModuleToSummariesForIndex);
1207
1208     if (ShouldEmitImportsFiles) {
1209       EC = EmitImportsFiles(ModulePath, NewModulePath + ".imports",
1210                             ModuleToSummariesForIndex);
1211       if (EC)
1212         return errorCodeToError(EC);
1213     }
1214
1215     if (OnWrite)
1216       OnWrite(ModulePath);
1217     return Error::success();
1218   }
1219
1220   Error wait() override { return Error::success(); }
1221 };
1222 } // end anonymous namespace
1223
1224 ThinBackend lto::createWriteIndexesThinBackend(
1225     std::string OldPrefix, std::string NewPrefix, bool ShouldEmitImportsFiles,
1226     raw_fd_ostream *LinkedObjectsFile, IndexWriteCallback OnWrite) {
1227   return [=](Config &Conf, ModuleSummaryIndex &CombinedIndex,
1228              const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
1229              AddStreamFn AddStream, NativeObjectCache Cache) {
1230     return llvm::make_unique<WriteIndexesThinBackend>(
1231         Conf, CombinedIndex, ModuleToDefinedGVSummaries, OldPrefix, NewPrefix,
1232         ShouldEmitImportsFiles, LinkedObjectsFile, OnWrite);
1233   };
1234 }
1235
1236 Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache,
1237                       const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
1238   if (ThinLTO.ModuleMap.empty())
1239     return Error::success();
1240
1241   if (Conf.CombinedIndexHook && !Conf.CombinedIndexHook(ThinLTO.CombinedIndex))
1242     return Error::success();
1243
1244   // Collect for each module the list of function it defines (GUID ->
1245   // Summary).
1246   StringMap<GVSummaryMapTy>
1247       ModuleToDefinedGVSummaries(ThinLTO.ModuleMap.size());
1248   ThinLTO.CombinedIndex.collectDefinedGVSummariesPerModule(
1249       ModuleToDefinedGVSummaries);
1250   // Create entries for any modules that didn't have any GV summaries
1251   // (either they didn't have any GVs to start with, or we suppressed
1252   // generation of the summaries because they e.g. had inline assembly
1253   // uses that couldn't be promoted/renamed on export). This is so
1254   // InProcessThinBackend::start can still launch a backend thread, which
1255   // is passed the map of summaries for the module, without any special
1256   // handling for this case.
1257   for (auto &Mod : ThinLTO.ModuleMap)
1258     if (!ModuleToDefinedGVSummaries.count(Mod.first))
1259       ModuleToDefinedGVSummaries.try_emplace(Mod.first);
1260
1261   // Synthesize entry counts for functions in the CombinedIndex.
1262   computeSyntheticCounts(ThinLTO.CombinedIndex);
1263
1264   StringMap<FunctionImporter::ImportMapTy> ImportLists(
1265       ThinLTO.ModuleMap.size());
1266   StringMap<FunctionImporter::ExportSetTy> ExportLists(
1267       ThinLTO.ModuleMap.size());
1268   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
1269
1270   if (DumpThinCGSCCs)
1271     ThinLTO.CombinedIndex.dumpSCCs(outs());
1272
1273   if (Conf.OptLevel > 0)
1274     ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
1275                              ImportLists, ExportLists);
1276
1277   // Figure out which symbols need to be internalized. This also needs to happen
1278   // at -O0 because summary-based DCE is implemented using internalization, and
1279   // we must apply DCE consistently with the full LTO module in order to avoid
1280   // undefined references during the final link.
1281   std::set<GlobalValue::GUID> ExportedGUIDs;
1282   for (auto &Res : GlobalResolutions) {
1283     // If the symbol does not have external references or it is not prevailing,
1284     // then not need to mark it as exported from a ThinLTO partition.
1285     if (Res.second.Partition != GlobalResolution::External ||
1286         !Res.second.isPrevailingIRSymbol())
1287       continue;
1288     auto GUID = GlobalValue::getGUID(
1289         GlobalValue::dropLLVMManglingEscape(Res.second.IRName));
1290     // Mark exported unless index-based analysis determined it to be dead.
1291     if (ThinLTO.CombinedIndex.isGUIDLive(GUID))
1292       ExportedGUIDs.insert(GUID);
1293   }
1294
1295   // Any functions referenced by the jump table in the regular LTO object must
1296   // be exported.
1297   for (auto &Def : ThinLTO.CombinedIndex.cfiFunctionDefs())
1298     ExportedGUIDs.insert(
1299         GlobalValue::getGUID(GlobalValue::dropLLVMManglingEscape(Def)));
1300
1301   auto isExported = [&](StringRef ModuleIdentifier, GlobalValue::GUID GUID) {
1302     const auto &ExportList = ExportLists.find(ModuleIdentifier);
1303     return (ExportList != ExportLists.end() &&
1304             ExportList->second.count(GUID)) ||
1305            ExportedGUIDs.count(GUID);
1306   };
1307   thinLTOInternalizeAndPromoteInIndex(ThinLTO.CombinedIndex, isExported);
1308
1309   auto isPrevailing = [&](GlobalValue::GUID GUID,
1310                           const GlobalValueSummary *S) {
1311     return ThinLTO.PrevailingModuleForGUID[GUID] == S->modulePath();
1312   };
1313   auto recordNewLinkage = [&](StringRef ModuleIdentifier,
1314                               GlobalValue::GUID GUID,
1315                               GlobalValue::LinkageTypes NewLinkage) {
1316     ResolvedODR[ModuleIdentifier][GUID] = NewLinkage;
1317   };
1318   thinLTOResolvePrevailingInIndex(ThinLTO.CombinedIndex, isPrevailing,
1319                                   recordNewLinkage, GUIDPreservedSymbols);
1320
1321   std::unique_ptr<ThinBackendProc> BackendProc =
1322       ThinLTO.Backend(Conf, ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
1323                       AddStream, Cache);
1324
1325   // Tasks 0 through ParallelCodeGenParallelismLevel-1 are reserved for combined
1326   // module and parallel code generation partitions.
1327   unsigned Task = RegularLTO.ParallelCodeGenParallelismLevel;
1328   for (auto &Mod : ThinLTO.ModuleMap) {
1329     if (Error E = BackendProc->start(Task, Mod.second, ImportLists[Mod.first],
1330                                      ExportLists[Mod.first],
1331                                      ResolvedODR[Mod.first], ThinLTO.ModuleMap))
1332       return E;
1333     ++Task;
1334   }
1335
1336   return BackendProc->wait();
1337 }
1338
1339 Expected<std::unique_ptr<ToolOutputFile>>
1340 lto::setupOptimizationRemarks(LLVMContext &Context,
1341                               StringRef LTORemarksFilename,
1342                               StringRef LTORemarksPasses,
1343                               bool LTOPassRemarksWithHotness, int Count) {
1344   if (LTOPassRemarksWithHotness)
1345     Context.setDiagnosticsHotnessRequested(true);
1346   if (LTORemarksFilename.empty())
1347     return nullptr;
1348
1349   std::string Filename = LTORemarksFilename;
1350   if (Count != -1)
1351     Filename += ".thin." + llvm::utostr(Count) + ".yaml";
1352
1353   std::error_code EC;
1354   auto DiagnosticFile =
1355       llvm::make_unique<ToolOutputFile>(Filename, EC, sys::fs::F_None);
1356   if (EC)
1357     return errorCodeToError(EC);
1358   Context.setRemarkStreamer(
1359       llvm::make_unique<RemarkStreamer>(Filename, DiagnosticFile->os()));
1360
1361   if (!LTORemarksPasses.empty())
1362     if (Error E = Context.getRemarkStreamer()->setFilter(LTORemarksPasses))
1363       return std::move(E);
1364
1365   DiagnosticFile->keep();
1366   return std::move(DiagnosticFile);
1367 }
1368
1369 Expected<std::unique_ptr<ToolOutputFile>>
1370 lto::setupStatsFile(StringRef StatsFilename) {
1371   // Setup output file to emit statistics.
1372   if (StatsFilename.empty())
1373     return nullptr;
1374
1375   llvm::EnableStatistics(false);
1376   std::error_code EC;
1377   auto StatsFile =
1378       llvm::make_unique<ToolOutputFile>(StatsFilename, EC, sys::fs::F_None);
1379   if (EC)
1380     return errorCodeToError(EC);
1381
1382   StatsFile->keep();
1383   return std::move(StatsFile);
1384 }