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