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