xref: /freebsd/contrib/llvm-project/llvm/lib/LTO/LTO.cpp (revision 6ba2210ee039f2f12878c217bcf058e9c8b26b29)
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 
57 using namespace llvm;
58 using namespace lto;
59 using namespace object;
60 
61 #define DEBUG_TYPE "lto"
62 
63 static 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.
68 cl::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.
75 void 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 
317 static 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.
371 void 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 
393 static 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 
401 static 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.
431 void 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>.
442 InputFile::~InputFile() = default;
443 
444 Expected<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 
473 StringRef InputFile::getName() const {
474   return Mods[0].getModuleIdentifier();
475 }
476 
477 BitcodeModule &InputFile::getSingleBitcodeModule() {
478   assert(Mods.size() == 1 && "Expect only one bitcode module");
479   return Mods[0];
480 }
481 
482 LTO::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 
488 LTO::ThinLTOState::ThinLTOState(ThinBackend Backend)
489     : Backend(Backend), CombinedIndex(/*HaveGVs*/ false) {
490   if (!Backend)
491     this->Backend =
492         createInProcessThinBackend(llvm::heavyweight_hardware_concurrency());
493 }
494 
495 LTO::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>.
502 LTO::~LTO() = default;
503 
504 // Add the symbols in the given module to the GlobalResolutions map, and resolve
505 // their partitions.
506 void 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 
559 static 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 
583 Error 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 
602 Error 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.
654 static void
655 handleNonPrevailingComdat(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.
677 Expected<LTO::RegularLTOState::AddedModule>
678 LTO::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 
795 Error 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, nullptr);
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.
830 Error 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 
891 unsigned 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.
900 Error 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 
937 Error 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 
982 Error 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       Conf.RemarksHotnessThreshold);
988   if (!DiagFileOrErr)
989     return DiagFileOrErr.takeError();
990 
991   // Finalize linking of regular LTO modules containing summaries now that
992   // we have computed liveness information.
993   for (auto &M : RegularLTO.ModsWithSummaries)
994     if (Error Err = linkRegularLTO(std::move(M),
995                                    /*LivenessFromIndex=*/true))
996       return Err;
997 
998   // Ensure we don't have inconsistently split LTO units with type tests.
999   // FIXME: this checks both LTO and ThinLTO. It happens to work as we take
1000   // this path both cases but eventually this should be split into two and
1001   // do the ThinLTO checks in `runThinLTO`.
1002   if (Error Err = checkPartiallySplit())
1003     return Err;
1004 
1005   // Make sure commons have the right size/alignment: we kept the largest from
1006   // all the prevailing when adding the inputs, and we apply it here.
1007   const DataLayout &DL = RegularLTO.CombinedModule->getDataLayout();
1008   for (auto &I : RegularLTO.Commons) {
1009     if (!I.second.Prevailing)
1010       // Don't do anything if no instance of this common was prevailing.
1011       continue;
1012     GlobalVariable *OldGV = RegularLTO.CombinedModule->getNamedGlobal(I.first);
1013     if (OldGV && DL.getTypeAllocSize(OldGV->getValueType()) == I.second.Size) {
1014       // Don't create a new global if the type is already correct, just make
1015       // sure the alignment is correct.
1016       OldGV->setAlignment(I.second.Align);
1017       continue;
1018     }
1019     ArrayType *Ty =
1020         ArrayType::get(Type::getInt8Ty(RegularLTO.Ctx), I.second.Size);
1021     auto *GV = new GlobalVariable(*RegularLTO.CombinedModule, Ty, false,
1022                                   GlobalValue::CommonLinkage,
1023                                   ConstantAggregateZero::get(Ty), "");
1024     GV->setAlignment(I.second.Align);
1025     if (OldGV) {
1026       OldGV->replaceAllUsesWith(ConstantExpr::getBitCast(GV, OldGV->getType()));
1027       GV->takeName(OldGV);
1028       OldGV->eraseFromParent();
1029     } else {
1030       GV->setName(I.first);
1031     }
1032   }
1033 
1034   // If allowed, upgrade public vcall visibility metadata to linkage unit
1035   // visibility before whole program devirtualization in the optimizer.
1036   updateVCallVisibilityInModule(*RegularLTO.CombinedModule,
1037                                 Conf.HasWholeProgramVisibility);
1038 
1039   if (Conf.PreOptModuleHook &&
1040       !Conf.PreOptModuleHook(0, *RegularLTO.CombinedModule))
1041     return Error::success();
1042 
1043   if (!Conf.CodeGenOnly) {
1044     for (const auto &R : GlobalResolutions) {
1045       if (!R.second.isPrevailingIRSymbol())
1046         continue;
1047       if (R.second.Partition != 0 &&
1048           R.second.Partition != GlobalResolution::External)
1049         continue;
1050 
1051       GlobalValue *GV =
1052           RegularLTO.CombinedModule->getNamedValue(R.second.IRName);
1053       // Ignore symbols defined in other partitions.
1054       // Also skip declarations, which are not allowed to have internal linkage.
1055       if (!GV || GV->hasLocalLinkage() || GV->isDeclaration())
1056         continue;
1057       GV->setUnnamedAddr(R.second.UnnamedAddr ? GlobalValue::UnnamedAddr::Global
1058                                               : GlobalValue::UnnamedAddr::None);
1059       if (EnableLTOInternalization && R.second.Partition == 0)
1060         GV->setLinkage(GlobalValue::InternalLinkage);
1061     }
1062 
1063     RegularLTO.CombinedModule->addModuleFlag(Module::Error, "LTOPostLink", 1);
1064 
1065     if (Conf.PostInternalizeModuleHook &&
1066         !Conf.PostInternalizeModuleHook(0, *RegularLTO.CombinedModule))
1067       return Error::success();
1068   }
1069 
1070   if (!RegularLTO.EmptyCombinedModule || Conf.AlwaysEmitRegularLTOObj) {
1071     if (Error Err = backend(
1072             Conf, AddStream, RegularLTO.ParallelCodeGenParallelismLevel,
1073             std::move(RegularLTO.CombinedModule), ThinLTO.CombinedIndex))
1074       return Err;
1075   }
1076 
1077   return finalizeOptimizationRemarks(std::move(*DiagFileOrErr));
1078 }
1079 
1080 static const char *libcallRoutineNames[] = {
1081 #define HANDLE_LIBCALL(code, name) name,
1082 #include "llvm/IR/RuntimeLibcalls.def"
1083 #undef HANDLE_LIBCALL
1084 };
1085 
1086 ArrayRef<const char*> LTO::getRuntimeLibcallSymbols() {
1087   return makeArrayRef(libcallRoutineNames);
1088 }
1089 
1090 /// This class defines the interface to the ThinLTO backend.
1091 class lto::ThinBackendProc {
1092 protected:
1093   const Config &Conf;
1094   ModuleSummaryIndex &CombinedIndex;
1095   const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries;
1096 
1097 public:
1098   ThinBackendProc(const Config &Conf, ModuleSummaryIndex &CombinedIndex,
1099                   const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries)
1100       : Conf(Conf), CombinedIndex(CombinedIndex),
1101         ModuleToDefinedGVSummaries(ModuleToDefinedGVSummaries) {}
1102 
1103   virtual ~ThinBackendProc() {}
1104   virtual Error start(
1105       unsigned Task, BitcodeModule BM,
1106       const FunctionImporter::ImportMapTy &ImportList,
1107       const FunctionImporter::ExportSetTy &ExportList,
1108       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
1109       MapVector<StringRef, BitcodeModule> &ModuleMap) = 0;
1110   virtual Error wait() = 0;
1111   virtual unsigned getThreadCount() = 0;
1112 };
1113 
1114 namespace {
1115 class InProcessThinBackend : public ThinBackendProc {
1116   ThreadPool BackendThreadPool;
1117   AddStreamFn AddStream;
1118   NativeObjectCache Cache;
1119   std::set<GlobalValue::GUID> CfiFunctionDefs;
1120   std::set<GlobalValue::GUID> CfiFunctionDecls;
1121 
1122   Optional<Error> Err;
1123   std::mutex ErrMu;
1124 
1125 public:
1126   InProcessThinBackend(
1127       const Config &Conf, ModuleSummaryIndex &CombinedIndex,
1128       ThreadPoolStrategy ThinLTOParallelism,
1129       const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
1130       AddStreamFn AddStream, NativeObjectCache Cache)
1131       : ThinBackendProc(Conf, CombinedIndex, ModuleToDefinedGVSummaries),
1132         BackendThreadPool(ThinLTOParallelism), AddStream(std::move(AddStream)),
1133         Cache(std::move(Cache)) {
1134     for (auto &Name : CombinedIndex.cfiFunctionDefs())
1135       CfiFunctionDefs.insert(
1136           GlobalValue::getGUID(GlobalValue::dropLLVMManglingEscape(Name)));
1137     for (auto &Name : CombinedIndex.cfiFunctionDecls())
1138       CfiFunctionDecls.insert(
1139           GlobalValue::getGUID(GlobalValue::dropLLVMManglingEscape(Name)));
1140   }
1141 
1142   Error runThinLTOBackendThread(
1143       AddStreamFn AddStream, NativeObjectCache Cache, unsigned Task,
1144       BitcodeModule BM, ModuleSummaryIndex &CombinedIndex,
1145       const FunctionImporter::ImportMapTy &ImportList,
1146       const FunctionImporter::ExportSetTy &ExportList,
1147       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
1148       const GVSummaryMapTy &DefinedGlobals,
1149       MapVector<StringRef, BitcodeModule> &ModuleMap) {
1150     auto RunThinBackend = [&](AddStreamFn AddStream) {
1151       LTOLLVMContext BackendContext(Conf);
1152       Expected<std::unique_ptr<Module>> MOrErr = BM.parseModule(BackendContext);
1153       if (!MOrErr)
1154         return MOrErr.takeError();
1155 
1156       return thinBackend(Conf, Task, AddStream, **MOrErr, CombinedIndex,
1157                          ImportList, DefinedGlobals, ModuleMap);
1158     };
1159 
1160     auto ModuleID = BM.getModuleIdentifier();
1161 
1162     if (!Cache || !CombinedIndex.modulePaths().count(ModuleID) ||
1163         all_of(CombinedIndex.getModuleHash(ModuleID),
1164                [](uint32_t V) { return V == 0; }))
1165       // Cache disabled or no entry for this module in the combined index or
1166       // no module hash.
1167       return RunThinBackend(AddStream);
1168 
1169     SmallString<40> Key;
1170     // The module may be cached, this helps handling it.
1171     computeLTOCacheKey(Key, Conf, CombinedIndex, ModuleID, ImportList,
1172                        ExportList, ResolvedODR, DefinedGlobals, CfiFunctionDefs,
1173                        CfiFunctionDecls);
1174     if (AddStreamFn CacheAddStream = Cache(Task, Key))
1175       return RunThinBackend(CacheAddStream);
1176 
1177     return Error::success();
1178   }
1179 
1180   Error start(
1181       unsigned Task, BitcodeModule BM,
1182       const FunctionImporter::ImportMapTy &ImportList,
1183       const FunctionImporter::ExportSetTy &ExportList,
1184       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
1185       MapVector<StringRef, BitcodeModule> &ModuleMap) override {
1186     StringRef ModulePath = BM.getModuleIdentifier();
1187     assert(ModuleToDefinedGVSummaries.count(ModulePath));
1188     const GVSummaryMapTy &DefinedGlobals =
1189         ModuleToDefinedGVSummaries.find(ModulePath)->second;
1190     BackendThreadPool.async(
1191         [=](BitcodeModule BM, ModuleSummaryIndex &CombinedIndex,
1192             const FunctionImporter::ImportMapTy &ImportList,
1193             const FunctionImporter::ExportSetTy &ExportList,
1194             const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>
1195                 &ResolvedODR,
1196             const GVSummaryMapTy &DefinedGlobals,
1197             MapVector<StringRef, BitcodeModule> &ModuleMap) {
1198           if (LLVM_ENABLE_THREADS && Conf.TimeTraceEnabled)
1199             timeTraceProfilerInitialize(Conf.TimeTraceGranularity,
1200                                         "thin backend");
1201           Error E = runThinLTOBackendThread(
1202               AddStream, Cache, Task, BM, CombinedIndex, ImportList, ExportList,
1203               ResolvedODR, DefinedGlobals, ModuleMap);
1204           if (E) {
1205             std::unique_lock<std::mutex> L(ErrMu);
1206             if (Err)
1207               Err = joinErrors(std::move(*Err), std::move(E));
1208             else
1209               Err = std::move(E);
1210           }
1211           if (LLVM_ENABLE_THREADS && Conf.TimeTraceEnabled)
1212             timeTraceProfilerFinishThread();
1213         },
1214         BM, std::ref(CombinedIndex), std::ref(ImportList), std::ref(ExportList),
1215         std::ref(ResolvedODR), std::ref(DefinedGlobals), std::ref(ModuleMap));
1216     return Error::success();
1217   }
1218 
1219   Error wait() override {
1220     BackendThreadPool.wait();
1221     if (Err)
1222       return std::move(*Err);
1223     else
1224       return Error::success();
1225   }
1226 
1227   unsigned getThreadCount() override {
1228     return BackendThreadPool.getThreadCount();
1229   }
1230 };
1231 } // end anonymous namespace
1232 
1233 ThinBackend lto::createInProcessThinBackend(ThreadPoolStrategy Parallelism) {
1234   return [=](const Config &Conf, ModuleSummaryIndex &CombinedIndex,
1235              const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
1236              AddStreamFn AddStream, NativeObjectCache Cache) {
1237     return std::make_unique<InProcessThinBackend>(
1238         Conf, CombinedIndex, Parallelism, ModuleToDefinedGVSummaries, AddStream,
1239         Cache);
1240   };
1241 }
1242 
1243 // Given the original \p Path to an output file, replace any path
1244 // prefix matching \p OldPrefix with \p NewPrefix. Also, create the
1245 // resulting directory if it does not yet exist.
1246 std::string lto::getThinLTOOutputFile(const std::string &Path,
1247                                       const std::string &OldPrefix,
1248                                       const std::string &NewPrefix) {
1249   if (OldPrefix.empty() && NewPrefix.empty())
1250     return Path;
1251   SmallString<128> NewPath(Path);
1252   llvm::sys::path::replace_path_prefix(NewPath, OldPrefix, NewPrefix);
1253   StringRef ParentPath = llvm::sys::path::parent_path(NewPath.str());
1254   if (!ParentPath.empty()) {
1255     // Make sure the new directory exists, creating it if necessary.
1256     if (std::error_code EC = llvm::sys::fs::create_directories(ParentPath))
1257       llvm::errs() << "warning: could not create directory '" << ParentPath
1258                    << "': " << EC.message() << '\n';
1259   }
1260   return std::string(NewPath.str());
1261 }
1262 
1263 namespace {
1264 class WriteIndexesThinBackend : public ThinBackendProc {
1265   std::string OldPrefix, NewPrefix;
1266   bool ShouldEmitImportsFiles;
1267   raw_fd_ostream *LinkedObjectsFile;
1268   lto::IndexWriteCallback OnWrite;
1269 
1270 public:
1271   WriteIndexesThinBackend(
1272       const Config &Conf, ModuleSummaryIndex &CombinedIndex,
1273       const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
1274       std::string OldPrefix, std::string NewPrefix, bool ShouldEmitImportsFiles,
1275       raw_fd_ostream *LinkedObjectsFile, lto::IndexWriteCallback OnWrite)
1276       : ThinBackendProc(Conf, CombinedIndex, ModuleToDefinedGVSummaries),
1277         OldPrefix(OldPrefix), NewPrefix(NewPrefix),
1278         ShouldEmitImportsFiles(ShouldEmitImportsFiles),
1279         LinkedObjectsFile(LinkedObjectsFile), OnWrite(OnWrite) {}
1280 
1281   Error start(
1282       unsigned Task, BitcodeModule BM,
1283       const FunctionImporter::ImportMapTy &ImportList,
1284       const FunctionImporter::ExportSetTy &ExportList,
1285       const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
1286       MapVector<StringRef, BitcodeModule> &ModuleMap) override {
1287     StringRef ModulePath = BM.getModuleIdentifier();
1288     std::string NewModulePath =
1289         getThinLTOOutputFile(std::string(ModulePath), OldPrefix, NewPrefix);
1290 
1291     if (LinkedObjectsFile)
1292       *LinkedObjectsFile << NewModulePath << '\n';
1293 
1294     std::map<std::string, GVSummaryMapTy> ModuleToSummariesForIndex;
1295     gatherImportedSummariesForModule(ModulePath, ModuleToDefinedGVSummaries,
1296                                      ImportList, ModuleToSummariesForIndex);
1297 
1298     std::error_code EC;
1299     raw_fd_ostream OS(NewModulePath + ".thinlto.bc", EC,
1300                       sys::fs::OpenFlags::OF_None);
1301     if (EC)
1302       return errorCodeToError(EC);
1303     WriteIndexToFile(CombinedIndex, OS, &ModuleToSummariesForIndex);
1304 
1305     if (ShouldEmitImportsFiles) {
1306       EC = EmitImportsFiles(ModulePath, NewModulePath + ".imports",
1307                             ModuleToSummariesForIndex);
1308       if (EC)
1309         return errorCodeToError(EC);
1310     }
1311 
1312     if (OnWrite)
1313       OnWrite(std::string(ModulePath));
1314     return Error::success();
1315   }
1316 
1317   Error wait() override { return Error::success(); }
1318 
1319   // WriteIndexesThinBackend should always return 1 to prevent module
1320   // re-ordering and avoid non-determinism in the final link.
1321   unsigned getThreadCount() override { return 1; }
1322 };
1323 } // end anonymous namespace
1324 
1325 ThinBackend lto::createWriteIndexesThinBackend(
1326     std::string OldPrefix, std::string NewPrefix, bool ShouldEmitImportsFiles,
1327     raw_fd_ostream *LinkedObjectsFile, IndexWriteCallback OnWrite) {
1328   return [=](const Config &Conf, ModuleSummaryIndex &CombinedIndex,
1329              const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
1330              AddStreamFn AddStream, NativeObjectCache Cache) {
1331     return std::make_unique<WriteIndexesThinBackend>(
1332         Conf, CombinedIndex, ModuleToDefinedGVSummaries, OldPrefix, NewPrefix,
1333         ShouldEmitImportsFiles, LinkedObjectsFile, OnWrite);
1334   };
1335 }
1336 
1337 Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache,
1338                       const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
1339   if (ThinLTO.ModuleMap.empty())
1340     return Error::success();
1341 
1342   if (ThinLTO.ModulesToCompile && ThinLTO.ModulesToCompile->empty()) {
1343     llvm::errs() << "warning: [ThinLTO] No module compiled\n";
1344     return Error::success();
1345   }
1346 
1347   if (Conf.CombinedIndexHook &&
1348       !Conf.CombinedIndexHook(ThinLTO.CombinedIndex, GUIDPreservedSymbols))
1349     return Error::success();
1350 
1351   // Collect for each module the list of function it defines (GUID ->
1352   // Summary).
1353   StringMap<GVSummaryMapTy>
1354       ModuleToDefinedGVSummaries(ThinLTO.ModuleMap.size());
1355   ThinLTO.CombinedIndex.collectDefinedGVSummariesPerModule(
1356       ModuleToDefinedGVSummaries);
1357   // Create entries for any modules that didn't have any GV summaries
1358   // (either they didn't have any GVs to start with, or we suppressed
1359   // generation of the summaries because they e.g. had inline assembly
1360   // uses that couldn't be promoted/renamed on export). This is so
1361   // InProcessThinBackend::start can still launch a backend thread, which
1362   // is passed the map of summaries for the module, without any special
1363   // handling for this case.
1364   for (auto &Mod : ThinLTO.ModuleMap)
1365     if (!ModuleToDefinedGVSummaries.count(Mod.first))
1366       ModuleToDefinedGVSummaries.try_emplace(Mod.first);
1367 
1368   // Synthesize entry counts for functions in the CombinedIndex.
1369   computeSyntheticCounts(ThinLTO.CombinedIndex);
1370 
1371   StringMap<FunctionImporter::ImportMapTy> ImportLists(
1372       ThinLTO.ModuleMap.size());
1373   StringMap<FunctionImporter::ExportSetTy> ExportLists(
1374       ThinLTO.ModuleMap.size());
1375   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
1376 
1377   if (DumpThinCGSCCs)
1378     ThinLTO.CombinedIndex.dumpSCCs(outs());
1379 
1380   std::set<GlobalValue::GUID> ExportedGUIDs;
1381 
1382   // If allowed, upgrade public vcall visibility to linkage unit visibility in
1383   // the summaries before whole program devirtualization below.
1384   updateVCallVisibilityInIndex(ThinLTO.CombinedIndex,
1385                                Conf.HasWholeProgramVisibility);
1386 
1387   // Perform index-based WPD. This will return immediately if there are
1388   // no index entries in the typeIdMetadata map (e.g. if we are instead
1389   // performing IR-based WPD in hybrid regular/thin LTO mode).
1390   std::map<ValueInfo, std::vector<VTableSlotSummary>> LocalWPDTargetsMap;
1391   runWholeProgramDevirtOnIndex(ThinLTO.CombinedIndex, ExportedGUIDs,
1392                                LocalWPDTargetsMap);
1393 
1394   if (Conf.OptLevel > 0)
1395     ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
1396                              ImportLists, ExportLists);
1397 
1398   // Figure out which symbols need to be internalized. This also needs to happen
1399   // at -O0 because summary-based DCE is implemented using internalization, and
1400   // we must apply DCE consistently with the full LTO module in order to avoid
1401   // undefined references during the final link.
1402   for (auto &Res : GlobalResolutions) {
1403     // If the symbol does not have external references or it is not prevailing,
1404     // then not need to mark it as exported from a ThinLTO partition.
1405     if (Res.second.Partition != GlobalResolution::External ||
1406         !Res.second.isPrevailingIRSymbol())
1407       continue;
1408     auto GUID = GlobalValue::getGUID(
1409         GlobalValue::dropLLVMManglingEscape(Res.second.IRName));
1410     // Mark exported unless index-based analysis determined it to be dead.
1411     if (ThinLTO.CombinedIndex.isGUIDLive(GUID))
1412       ExportedGUIDs.insert(GUID);
1413   }
1414 
1415   // Any functions referenced by the jump table in the regular LTO object must
1416   // be exported.
1417   for (auto &Def : ThinLTO.CombinedIndex.cfiFunctionDefs())
1418     ExportedGUIDs.insert(
1419         GlobalValue::getGUID(GlobalValue::dropLLVMManglingEscape(Def)));
1420 
1421   auto isExported = [&](StringRef ModuleIdentifier, ValueInfo VI) {
1422     const auto &ExportList = ExportLists.find(ModuleIdentifier);
1423     return (ExportList != ExportLists.end() && ExportList->second.count(VI)) ||
1424            ExportedGUIDs.count(VI.getGUID());
1425   };
1426 
1427   // Update local devirtualized targets that were exported by cross-module
1428   // importing or by other devirtualizations marked in the ExportedGUIDs set.
1429   updateIndexWPDForExports(ThinLTO.CombinedIndex, isExported,
1430                            LocalWPDTargetsMap);
1431 
1432   auto isPrevailing = [&](GlobalValue::GUID GUID,
1433                           const GlobalValueSummary *S) {
1434     return ThinLTO.PrevailingModuleForGUID[GUID] == S->modulePath();
1435   };
1436   thinLTOInternalizeAndPromoteInIndex(ThinLTO.CombinedIndex, isExported,
1437                                       isPrevailing);
1438 
1439   auto recordNewLinkage = [&](StringRef ModuleIdentifier,
1440                               GlobalValue::GUID GUID,
1441                               GlobalValue::LinkageTypes NewLinkage) {
1442     ResolvedODR[ModuleIdentifier][GUID] = NewLinkage;
1443   };
1444   thinLTOResolvePrevailingInIndex(ThinLTO.CombinedIndex, isPrevailing,
1445                                   recordNewLinkage, GUIDPreservedSymbols);
1446 
1447   generateParamAccessSummary(ThinLTO.CombinedIndex);
1448 
1449   std::unique_ptr<ThinBackendProc> BackendProc =
1450       ThinLTO.Backend(Conf, ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
1451                       AddStream, Cache);
1452 
1453   auto &ModuleMap =
1454       ThinLTO.ModulesToCompile ? *ThinLTO.ModulesToCompile : ThinLTO.ModuleMap;
1455 
1456   auto ProcessOneModule = [&](int I) -> Error {
1457     auto &Mod = *(ModuleMap.begin() + I);
1458     // Tasks 0 through ParallelCodeGenParallelismLevel-1 are reserved for
1459     // combined module and parallel code generation partitions.
1460     return BackendProc->start(RegularLTO.ParallelCodeGenParallelismLevel + I,
1461                               Mod.second, ImportLists[Mod.first],
1462                               ExportLists[Mod.first], ResolvedODR[Mod.first],
1463                               ThinLTO.ModuleMap);
1464   };
1465 
1466   if (BackendProc->getThreadCount() == 1) {
1467     // Process the modules in the order they were provided on the command-line.
1468     // It is important for this codepath to be used for WriteIndexesThinBackend,
1469     // to ensure the emitted LinkedObjectsFile lists ThinLTO objects in the same
1470     // order as the inputs, which otherwise would affect the final link order.
1471     for (int I = 0, E = ModuleMap.size(); I != E; ++I)
1472       if (Error E = ProcessOneModule(I))
1473         return E;
1474   } else {
1475     // When executing in parallel, process largest bitsize modules first to
1476     // improve parallelism, and avoid starving the thread pool near the end.
1477     // This saves about 15 sec on a 36-core machine while link `clang.exe` (out
1478     // of 100 sec).
1479     std::vector<BitcodeModule *> ModulesVec;
1480     ModulesVec.reserve(ModuleMap.size());
1481     for (auto &Mod : ModuleMap)
1482       ModulesVec.push_back(&Mod.second);
1483     for (int I : generateModulesOrdering(ModulesVec))
1484       if (Error E = ProcessOneModule(I))
1485         return E;
1486   }
1487   return BackendProc->wait();
1488 }
1489 
1490 Expected<std::unique_ptr<ToolOutputFile>> lto::setupLLVMOptimizationRemarks(
1491     LLVMContext &Context, StringRef RemarksFilename, StringRef RemarksPasses,
1492     StringRef RemarksFormat, bool RemarksWithHotness,
1493     Optional<uint64_t> RemarksHotnessThreshold, int Count) {
1494   std::string Filename = std::string(RemarksFilename);
1495   // For ThinLTO, file.opt.<format> becomes
1496   // file.opt.<format>.thin.<num>.<format>.
1497   if (!Filename.empty() && Count != -1)
1498     Filename =
1499         (Twine(Filename) + ".thin." + llvm::utostr(Count) + "." + RemarksFormat)
1500             .str();
1501 
1502   auto ResultOrErr = llvm::setupLLVMOptimizationRemarks(
1503       Context, Filename, RemarksPasses, RemarksFormat, RemarksWithHotness,
1504       RemarksHotnessThreshold);
1505   if (Error E = ResultOrErr.takeError())
1506     return std::move(E);
1507 
1508   if (*ResultOrErr)
1509     (*ResultOrErr)->keep();
1510 
1511   return ResultOrErr;
1512 }
1513 
1514 Expected<std::unique_ptr<ToolOutputFile>>
1515 lto::setupStatsFile(StringRef StatsFilename) {
1516   // Setup output file to emit statistics.
1517   if (StatsFilename.empty())
1518     return nullptr;
1519 
1520   llvm::EnableStatistics(false);
1521   std::error_code EC;
1522   auto StatsFile =
1523       std::make_unique<ToolOutputFile>(StatsFilename, EC, sys::fs::OF_None);
1524   if (EC)
1525     return errorCodeToError(EC);
1526 
1527   StatsFile->keep();
1528   return std::move(StatsFile);
1529 }
1530 
1531 // Compute the ordering we will process the inputs: the rough heuristic here
1532 // is to sort them per size so that the largest module get schedule as soon as
1533 // possible. This is purely a compile-time optimization.
1534 std::vector<int> lto::generateModulesOrdering(ArrayRef<BitcodeModule *> R) {
1535   std::vector<int> ModulesOrdering;
1536   ModulesOrdering.resize(R.size());
1537   std::iota(ModulesOrdering.begin(), ModulesOrdering.end(), 0);
1538   llvm::sort(ModulesOrdering, [&](int LeftIndex, int RightIndex) {
1539     auto LSize = R[LeftIndex]->getBuffer().size();
1540     auto RSize = R[RightIndex]->getBuffer().size();
1541     return LSize > RSize;
1542   });
1543   return ModulesOrdering;
1544 }
1545