LTO.cpp revision 363496 
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
54using namespace llvm;
55using namespace lto;
56using namespace object;
57
58#define DEBUG_TYPE "lto"
59
60static 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.
65cl::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.
72void 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
324static 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.
378void 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
400static 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
408static 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.
438void 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>.
449InputFile::~InputFile() = default;
450
451Expected<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
480StringRef InputFile::getName() const {
481  return Mods[0].getModuleIdentifier();
482}
483
484BitcodeModule &InputFile::getSingleBitcodeModule() {
485  assert(Mods.size() == 1 && "Expect only one bitcode module");
486  return Mods[0];
487}
488
489LTO::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
495LTO::ThinLTOState::ThinLTOState(ThinBackend Backend)
496    : Backend(Backend), CombinedIndex(/*HaveGVs*/ false) {
497  if (!Backend)
498    this->Backend =
499        createInProcessThinBackend(llvm::heavyweight_hardware_concurrency());
500}
501
502LTO::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>.
509LTO::~LTO() = default;
510
511// Add the symbols in the given module to the GlobalResolutions map, and resolve
512// their partitions.
513void 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
566static 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
590Error 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
609Error 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.
660static void
661handleNonPrevailingComdat(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.
683Expected<LTO::RegularLTOState::AddedModule>
684LTO::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
800Error 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.
828Error 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
875unsigned 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.
882Error 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
919Error 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
975Error 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
1039static const char *libcallRoutineNames[] = {
1040#define HANDLE_LIBCALL(code, name) name,
1041#include "llvm/IR/RuntimeLibcalls.def"
1042#undef HANDLE_LIBCALL
1043};
1044
1045ArrayRef<const char*> LTO::getRuntimeLibcallSymbols() {
1046  return makeArrayRef(libcallRoutineNames);
1047}
1048
1049/// This class defines the interface to the ThinLTO backend.
1050class lto::ThinBackendProc {
1051protected:
1052  const Config &Conf;
1053  ModuleSummaryIndex &CombinedIndex;
1054  const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries;
1055
1056public:
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
1072namespace {
1073class 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
1083public:
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
1182ThinBackend 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.
1195std::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
1212namespace {
1213class WriteIndexesThinBackend : public ThinBackendProc {
1214  std::string OldPrefix, NewPrefix;
1215  bool ShouldEmitImportsFiles;
1216  raw_fd_ostream *LinkedObjectsFile;
1217  lto::IndexWriteCallback OnWrite;
1218
1219public:
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
1270ThinBackend 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
1282Error 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
1400Expected<std::unique_ptr<ToolOutputFile>>
1401lto::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
1423Expected<std::unique_ptr<ToolOutputFile>>
1424lto::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}
1439