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