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