1//===-LTO.h - 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 declares functions and classes used to support LTO. It is intended
10// to be used both by LTO classes as well as by clients (gold-plugin) that
11// don't utilize the LTO code generator interfaces.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_LTO_LTO_H
16#define LLVM_LTO_LTO_H
17
18#include "llvm/ADT/MapVector.h"
19#include "llvm/ADT/StringMap.h"
20#include "llvm/Bitcode/BitcodeReader.h"
21#include "llvm/IR/ModuleSummaryIndex.h"
22#include "llvm/LTO/Config.h"
23#include "llvm/Object/IRSymtab.h"
24#include "llvm/Support/Error.h"
25#include "llvm/Support/thread.h"
26#include "llvm/Transforms/IPO/FunctionImport.h"
27
28namespace llvm {
29
30class Error;
31class IRMover;
32class LLVMContext;
33class MemoryBufferRef;
34class Module;
35class raw_pwrite_stream;
36class Target;
37class ToolOutputFile;
38
39/// Resolve linkage for prevailing symbols in the \p Index. Linkage changes
40/// recorded in the index and the ThinLTO backends must apply the changes to
41/// the module via thinLTOResolvePrevailingInModule.
42///
43/// This is done for correctness (if value exported, ensure we always
44/// emit a copy), and compile-time optimization (allow drop of duplicates).
45void thinLTOResolvePrevailingInIndex(
46 const lto::Config &C, ModuleSummaryIndex &Index,
47 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
48 isPrevailing,
49 function_ref<void(StringRef, GlobalValue::GUID, GlobalValue::LinkageTypes)>
50 recordNewLinkage,
51 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols);
52
53/// Update the linkages in the given \p Index to mark exported values
54/// as external and non-exported values as internal. The ThinLTO backends
55/// must apply the changes to the Module via thinLTOInternalizeModule.
56void thinLTOInternalizeAndPromoteInIndex(
57 ModuleSummaryIndex &Index,
58 function_ref<bool(StringRef, ValueInfo)> isExported,
59 function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
60 isPrevailing);
61
62/// Computes a unique hash for the Module considering the current list of
63/// export/import and other global analysis results.
64/// The hash is produced in \p Key.
65void computeLTOCacheKey(
66 SmallString<40> &Key, const lto::Config &Conf,
67 const ModuleSummaryIndex &Index, StringRef ModuleID,
68 const FunctionImporter::ImportMapTy &ImportList,
69 const FunctionImporter::ExportSetTy &ExportList,
70 const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
71 const GVSummaryMapTy &DefinedGlobals,
72 const std::set<GlobalValue::GUID> &CfiFunctionDefs = {},
73 const std::set<GlobalValue::GUID> &CfiFunctionDecls = {});
74
75namespace lto {
76
77/// Given the original \p Path to an output file, replace any path
78/// prefix matching \p OldPrefix with \p NewPrefix. Also, create the
79/// resulting directory if it does not yet exist.
80std::string getThinLTOOutputFile(const std::string &Path,
81 const std::string &OldPrefix,
82 const std::string &NewPrefix);
83
84/// Setup optimization remarks.
85Expected<std::unique_ptr<ToolOutputFile>> setupLLVMOptimizationRemarks(
86 LLVMContext &Context, StringRef RemarksFilename, StringRef RemarksPasses,
87 StringRef RemarksFormat, bool RemarksWithHotness,
88 Optional<uint64_t> RemarksHotnessThreshold = 0, int Count = -1);
89
90/// Setups the output file for saving statistics.
91Expected<std::unique_ptr<ToolOutputFile>>
92setupStatsFile(StringRef StatsFilename);
93
94/// Produces a container ordering for optimal multi-threaded processing. Returns
95/// ordered indices to elements in the input array.
96std::vector<int> generateModulesOrdering(ArrayRef<BitcodeModule *> R);
97
98class LTO;
99struct SymbolResolution;
100class ThinBackendProc;
101
102/// An input file. This is a symbol table wrapper that only exposes the
103/// information that an LTO client should need in order to do symbol resolution.
104class InputFile {
105public:
106 class Symbol;
107
108private:
109 // FIXME: Remove LTO class friendship once we have bitcode symbol tables.
110 friend LTO;
111 InputFile() = default;
112
113 std::vector<BitcodeModule> Mods;
114 SmallVector<char, 0> Strtab;
115 std::vector<Symbol> Symbols;
116
117 // [begin, end) for each module
118 std::vector<std::pair<size_t, size_t>> ModuleSymIndices;
119
120 StringRef TargetTriple, SourceFileName, COFFLinkerOpts;
121 std::vector<StringRef> DependentLibraries;
122 std::vector<StringRef> ComdatTable;
123
124public:
125 ~InputFile();
126
127 /// Create an InputFile.
128 static Expected<std::unique_ptr<InputFile>> create(MemoryBufferRef Object);
129
130 /// The purpose of this class is to only expose the symbol information that an
131 /// LTO client should need in order to do symbol resolution.
132 class Symbol : irsymtab::Symbol {
133 friend LTO;
134
135 public:
136 Symbol(const irsymtab::Symbol &S) : irsymtab::Symbol(S) {}
137
138 using irsymtab::Symbol::isUndefined;
139 using irsymtab::Symbol::isCommon;
140 using irsymtab::Symbol::isWeak;
141 using irsymtab::Symbol::isIndirect;
142 using irsymtab::Symbol::getName;
143 using irsymtab::Symbol::getIRName;
144 using irsymtab::Symbol::getVisibility;
145 using irsymtab::Symbol::canBeOmittedFromSymbolTable;
146 using irsymtab::Symbol::isTLS;
147 using irsymtab::Symbol::getComdatIndex;
148 using irsymtab::Symbol::getCommonSize;
149 using irsymtab::Symbol::getCommonAlignment;
150 using irsymtab::Symbol::getCOFFWeakExternalFallback;
151 using irsymtab::Symbol::getSectionName;
152 using irsymtab::Symbol::isExecutable;
153 using irsymtab::Symbol::isUsed;
154 };
155
156 /// A range over the symbols in this InputFile.
157 ArrayRef<Symbol> symbols() const { return Symbols; }
158
159 /// Returns linker options specified in the input file.
160 StringRef getCOFFLinkerOpts() const { return COFFLinkerOpts; }
161
162 /// Returns dependent library specifiers from the input file.
163 ArrayRef<StringRef> getDependentLibraries() const { return DependentLibraries; }
164
165 /// Returns the path to the InputFile.
166 StringRef getName() const;
167
168 /// Returns the input file's target triple.
169 StringRef getTargetTriple() const { return TargetTriple; }
170
171 /// Returns the source file path specified at compile time.
172 StringRef getSourceFileName() const { return SourceFileName; }
173
174 // Returns a table with all the comdats used by this file.
175 ArrayRef<StringRef> getComdatTable() const { return ComdatTable; }
176
177 // Returns the only BitcodeModule from InputFile.
178 BitcodeModule &getSingleBitcodeModule();
179
180private:
181 ArrayRef<Symbol> module_symbols(unsigned I) const {
182 const auto &Indices = ModuleSymIndices[I];
183 return {Symbols.data() + Indices.first, Symbols.data() + Indices.second};
184 }
185};
186
187/// This class wraps an output stream for a native object. Most clients should
188/// just be able to return an instance of this base class from the stream
189/// callback, but if a client needs to perform some action after the stream is
190/// written to, that can be done by deriving from this class and overriding the
191/// destructor.
192class NativeObjectStream {
193public:
194 NativeObjectStream(std::unique_ptr<raw_pwrite_stream> OS) : OS(std::move(OS)) {}
195 std::unique_ptr<raw_pwrite_stream> OS;
196 virtual ~NativeObjectStream() = default;
197};
198
199/// This type defines the callback to add a native object that is generated on
200/// the fly.
201///
202/// Stream callbacks must be thread safe.
203using AddStreamFn =
204 std::function<std::unique_ptr<NativeObjectStream>(unsigned Task)>;
205
206/// This is the type of a native object cache. To request an item from the
207/// cache, pass a unique string as the Key. For hits, the cached file will be
208/// added to the link and this function will return AddStreamFn(). For misses,
209/// the cache will return a stream callback which must be called at most once to
210/// produce content for the stream. The native object stream produced by the
211/// stream callback will add the file to the link after the stream is written
212/// to.
213///
214/// Clients generally look like this:
215///
216/// if (AddStreamFn AddStream = Cache(Task, Key))
217/// ProduceContent(AddStream);
218using NativeObjectCache =
219 std::function<AddStreamFn(unsigned Task, StringRef Key)>;
220
221/// A ThinBackend defines what happens after the thin-link phase during ThinLTO.
222/// The details of this type definition aren't important; clients can only
223/// create a ThinBackend using one of the create*ThinBackend() functions below.
224using ThinBackend = std::function<std::unique_ptr<ThinBackendProc>(
225 const Config &C, ModuleSummaryIndex &CombinedIndex,
226 StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
227 AddStreamFn AddStream, NativeObjectCache Cache)>;
228
229/// This ThinBackend runs the individual backend jobs in-process.
230/// The default value means to use one job per hardware core (not hyper-thread).
231ThinBackend createInProcessThinBackend(ThreadPoolStrategy Parallelism);
232
233/// This ThinBackend writes individual module indexes to files, instead of
234/// running the individual backend jobs. This backend is for distributed builds
235/// where separate processes will invoke the real backends.
236///
237/// To find the path to write the index to, the backend checks if the path has a
238/// prefix of OldPrefix; if so, it replaces that prefix with NewPrefix. It then
239/// appends ".thinlto.bc" and writes the index to that path. If
240/// ShouldEmitImportsFiles is true it also writes a list of imported files to a
241/// similar path with ".imports" appended instead.
242/// LinkedObjectsFile is an output stream to write the list of object files for
243/// the final ThinLTO linking. Can be nullptr.
244/// OnWrite is callback which receives module identifier and notifies LTO user
245/// that index file for the module (and optionally imports file) was created.
246using IndexWriteCallback = std::function<void(const std::string &)>;
247ThinBackend createWriteIndexesThinBackend(std::string OldPrefix,
248 std::string NewPrefix,
249 bool ShouldEmitImportsFiles,
250 raw_fd_ostream *LinkedObjectsFile,
251 IndexWriteCallback OnWrite);
252
253/// This class implements a resolution-based interface to LLVM's LTO
254/// functionality. It supports regular LTO, parallel LTO code generation and
255/// ThinLTO. You can use it from a linker in the following way:
256/// - Set hooks and code generation options (see lto::Config struct defined in
257/// Config.h), and use the lto::Config object to create an lto::LTO object.
258/// - Create lto::InputFile objects using lto::InputFile::create(), then use
259/// the symbols() function to enumerate its symbols and compute a resolution
260/// for each symbol (see SymbolResolution below).
261/// - After the linker has visited each input file (and each regular object
262/// file) and computed a resolution for each symbol, take each lto::InputFile
263/// and pass it and an array of symbol resolutions to the add() function.
264/// - Call the getMaxTasks() function to get an upper bound on the number of
265/// native object files that LTO may add to the link.
266/// - Call the run() function. This function will use the supplied AddStream
267/// and Cache functions to add up to getMaxTasks() native object files to
268/// the link.
269class LTO {
270 friend InputFile;
271
272public:
273 /// Create an LTO object. A default constructed LTO object has a reasonable
274 /// production configuration, but you can customize it by passing arguments to
275 /// this constructor.
276 /// FIXME: We do currently require the DiagHandler field to be set in Conf.
277 /// Until that is fixed, a Config argument is required.
278 LTO(Config Conf, ThinBackend Backend = nullptr,
279 unsigned ParallelCodeGenParallelismLevel = 1);
280 ~LTO();
281
282 /// Add an input file to the LTO link, using the provided symbol resolutions.
283 /// The symbol resolutions must appear in the enumeration order given by
284 /// InputFile::symbols().
285 Error add(std::unique_ptr<InputFile> Obj, ArrayRef<SymbolResolution> Res);
286
287 /// Returns an upper bound on the number of tasks that the client may expect.
288 /// This may only be called after all IR object files have been added. For a
289 /// full description of tasks see LTOBackend.h.
290 unsigned getMaxTasks() const;
291
292 /// Runs the LTO pipeline. This function calls the supplied AddStream
293 /// function to add native object files to the link.
294 ///
295 /// The Cache parameter is optional. If supplied, it will be used to cache
296 /// native object files and add them to the link.
297 ///
298 /// The client will receive at most one callback (via either AddStream or
299 /// Cache) for each task identifier.
300 Error run(AddStreamFn AddStream, NativeObjectCache Cache = nullptr);
301
302 /// Static method that returns a list of libcall symbols that can be generated
303 /// by LTO but might not be visible from bitcode symbol table.
304 static ArrayRef<const char*> getRuntimeLibcallSymbols();
305
306private:
307 Config Conf;
308
309 struct RegularLTOState {
310 RegularLTOState(unsigned ParallelCodeGenParallelismLevel,
311 const Config &Conf);
312 struct CommonResolution {
313 uint64_t Size = 0;
314 MaybeAlign Align;
315 /// Record if at least one instance of the common was marked as prevailing
316 bool Prevailing = false;
317 };
318 std::map<std::string, CommonResolution> Commons;
319
320 unsigned ParallelCodeGenParallelismLevel;
321 LTOLLVMContext Ctx;
322 std::unique_ptr<Module> CombinedModule;
323 std::unique_ptr<IRMover> Mover;
324
325 // This stores the information about a regular LTO module that we have added
326 // to the link. It will either be linked immediately (for modules without
327 // summaries) or after summary-based dead stripping (for modules with
328 // summaries).
329 struct AddedModule {
330 std::unique_ptr<Module> M;
331 std::vector<GlobalValue *> Keep;
332 };
333 std::vector<AddedModule> ModsWithSummaries;
334 bool EmptyCombinedModule = true;
335 } RegularLTO;
336
337 using ModuleMapType = MapVector<StringRef, BitcodeModule>;
338
339 struct ThinLTOState {
340 ThinLTOState(ThinBackend Backend);
341
342 ThinBackend Backend;
343 ModuleSummaryIndex CombinedIndex;
344 // The full set of bitcode modules in input order.
345 ModuleMapType ModuleMap;
346 // The bitcode modules to compile, if specified by the LTO Config.
347 Optional<ModuleMapType> ModulesToCompile;
348 DenseMap<GlobalValue::GUID, StringRef> PrevailingModuleForGUID;
349 } ThinLTO;
350
351 // The global resolution for a particular (mangled) symbol name. This is in
352 // particular necessary to track whether each symbol can be internalized.
353 // Because any input file may introduce a new cross-partition reference, we
354 // cannot make any final internalization decisions until all input files have
355 // been added and the client has called run(). During run() we apply
356 // internalization decisions either directly to the module (for regular LTO)
357 // or to the combined index (for ThinLTO).
358 struct GlobalResolution {
359 /// The unmangled name of the global.
360 std::string IRName;
361
362 /// Keep track if the symbol is visible outside of a module with a summary
363 /// (i.e. in either a regular object or a regular LTO module without a
364 /// summary).
365 bool VisibleOutsideSummary = false;
366
367 /// The symbol was exported dynamically, and therefore could be referenced
368 /// by a shared library not visible to the linker.
369 bool ExportDynamic = false;
370
371 bool UnnamedAddr = true;
372
373 /// True if module contains the prevailing definition.
374 bool Prevailing = false;
375
376 /// Returns true if module contains the prevailing definition and symbol is
377 /// an IR symbol. For example when module-level inline asm block is used,
378 /// symbol can be prevailing in module but have no IR name.
379 bool isPrevailingIRSymbol() const { return Prevailing && !IRName.empty(); }
380
381 /// This field keeps track of the partition number of this global. The
382 /// regular LTO object is partition 0, while each ThinLTO object has its own
383 /// partition number from 1 onwards.
384 ///
385 /// Any global that is defined or used by more than one partition, or that
386 /// is referenced externally, may not be internalized.
387 ///
388 /// Partitions generally have a one-to-one correspondence with tasks, except
389 /// that we use partition 0 for all parallel LTO code generation partitions.
390 /// Any partitioning of the combined LTO object is done internally by the
391 /// LTO backend.
392 unsigned Partition = Unknown;
393
394 /// Special partition numbers.
395 enum : unsigned {
396 /// A partition number has not yet been assigned to this global.
397 Unknown = -1u,
398
399 /// This global is either used by more than one partition or has an
400 /// external reference, and therefore cannot be internalized.
401 External = -2u,
402
403 /// The RegularLTO partition
404 RegularLTO = 0,
405 };
406 };
407
408 // Global mapping from mangled symbol names to resolutions.
409 StringMap<GlobalResolution> GlobalResolutions;
410
411 void addModuleToGlobalRes(ArrayRef<InputFile::Symbol> Syms,
412 ArrayRef<SymbolResolution> Res, unsigned Partition,
413 bool InSummary);
414
415 // These functions take a range of symbol resolutions [ResI, ResE) and consume
416 // the resolutions used by a single input module by incrementing ResI. After
417 // these functions return, [ResI, ResE) will refer to the resolution range for
418 // the remaining modules in the InputFile.
419 Error addModule(InputFile &Input, unsigned ModI,
420 const SymbolResolution *&ResI, const SymbolResolution *ResE);
421
422 Expected<RegularLTOState::AddedModule>
423 addRegularLTO(BitcodeModule BM, ArrayRef<InputFile::Symbol> Syms,
424 const SymbolResolution *&ResI, const SymbolResolution *ResE);
425 Error linkRegularLTO(RegularLTOState::AddedModule Mod,
426 bool LivenessFromIndex);
427
428 Error addThinLTO(BitcodeModule BM, ArrayRef<InputFile::Symbol> Syms,
429 const SymbolResolution *&ResI, const SymbolResolution *ResE);
430
431 Error runRegularLTO(AddStreamFn AddStream);
432 Error runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache,
433 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols);
434
435 Error checkPartiallySplit();
436
437 mutable bool CalledGetMaxTasks = false;
438
439 // Use Optional to distinguish false from not yet initialized.
440 Optional<bool> EnableSplitLTOUnit;
441
442 // Identify symbols exported dynamically, and that therefore could be
443 // referenced by a shared library not visible to the linker.
444 DenseSet<GlobalValue::GUID> DynamicExportSymbols;
445};
446
447/// The resolution for a symbol. The linker must provide a SymbolResolution for
448/// each global symbol based on its internal resolution of that symbol.
449struct SymbolResolution {
450 SymbolResolution()
451 : Prevailing(0), FinalDefinitionInLinkageUnit(0), VisibleToRegularObj(0),
452 ExportDynamic(0), LinkerRedefined(0) {}
453
454 /// The linker has chosen this definition of the symbol.
455 unsigned Prevailing : 1;
456
457 /// The definition of this symbol is unpreemptable at runtime and is known to
458 /// be in this linkage unit.
459 unsigned FinalDefinitionInLinkageUnit : 1;
460
461 /// The definition of this symbol is visible outside of the LTO unit.
462 unsigned VisibleToRegularObj : 1;
463
464 /// The symbol was exported dynamically, and therefore could be referenced
465 /// by a shared library not visible to the linker.
466 unsigned ExportDynamic : 1;
467
468 /// Linker redefined version of the symbol which appeared in -wrap or -defsym
469 /// linker option.
470 unsigned LinkerRedefined : 1;
471};
472
473} // namespace lto
474} // namespace llvm
475
476#endif
477