LLVM  8.0.0svn
LTO.h
Go to the documentation of this file.
1 //===-LTO.h - LLVM Link Time Optimizer ------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file declares functions and classes used to support LTO. It is intended
11 // to be used both by LTO classes as well as by clients (gold-plugin) that
12 // don't utilize the LTO code generator interfaces.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_LTO_LTO_H
17 #define LLVM_LTO_LTO_H
18 
19 #include "llvm/ADT/MapVector.h"
20 #include "llvm/ADT/StringMap.h"
21 #include "llvm/ADT/StringSet.h"
22 #include "llvm/IR/DiagnosticInfo.h"
24 #include "llvm/LTO/Config.h"
25 #include "llvm/Linker/IRMover.h"
26 #include "llvm/Object/IRSymtab.h"
27 #include "llvm/Support/Error.h"
29 #include "llvm/Support/thread.h"
32 
33 namespace llvm {
34 
35 class BitcodeModule;
36 class Error;
37 class LLVMContext;
38 class MemoryBufferRef;
39 class Module;
40 class Target;
41 class raw_pwrite_stream;
42 
43 /// Resolve Weak and LinkOnce values in the \p Index. Linkage changes recorded
44 /// in the index and the ThinLTO backends must apply the changes to the Module
45 /// via thinLTOResolveWeakForLinkerModule.
46 ///
47 /// This is done for correctness (if value exported, ensure we always
48 /// emit a copy), and compile-time optimization (allow drop of duplicates).
50  ModuleSummaryIndex &Index,
51  function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
52  isPrevailing,
53  function_ref<void(StringRef, GlobalValue::GUID, GlobalValue::LinkageTypes)>
54  recordNewLinkage);
55 
56 /// Update the linkages in the given \p Index to mark exported values
57 /// as external and non-exported values as internal. The ThinLTO backends
58 /// must apply the changes to the Module via thinLTOInternalizeModule.
60  ModuleSummaryIndex &Index,
61  function_ref<bool(StringRef, GlobalValue::GUID)> isExported);
62 
63 namespace lto {
64 
65 /// Given the original \p Path to an output file, replace any path
66 /// prefix matching \p OldPrefix with \p NewPrefix. Also, create the
67 /// resulting directory if it does not yet exist.
68 std::string getThinLTOOutputFile(const std::string &Path,
69  const std::string &OldPrefix,
70  const std::string &NewPrefix);
71 
72 /// Setup optimization remarks.
73 Expected<std::unique_ptr<ToolOutputFile>>
75  bool LTOPassRemarksWithHotness, int Count = -1);
76 
77 class LTO;
78 struct SymbolResolution;
79 class ThinBackendProc;
80 
81 /// An input file. This is a symbol table wrapper that only exposes the
82 /// information that an LTO client should need in order to do symbol resolution.
83 class InputFile {
84 public:
85  class Symbol;
86 
87 private:
88  // FIXME: Remove LTO class friendship once we have bitcode symbol tables.
89  friend LTO;
90  InputFile() = default;
91 
92  std::vector<BitcodeModule> Mods;
93  SmallVector<char, 0> Strtab;
94  std::vector<Symbol> Symbols;
95 
96  // [begin, end) for each module
97  std::vector<std::pair<size_t, size_t>> ModuleSymIndices;
98 
99  StringRef TargetTriple, SourceFileName, COFFLinkerOpts;
100  std::vector<StringRef> ComdatTable;
101 
102 public:
103  ~InputFile();
104 
105  /// Create an InputFile.
107 
108  /// The purpose of this class is to only expose the symbol information that an
109  /// LTO client should need in order to do symbol resolution.
111  friend LTO;
112 
113  public:
114  Symbol(const irsymtab::Symbol &S) : irsymtab::Symbol(S) {}
115 
130  };
131 
132  /// A range over the symbols in this InputFile.
133  ArrayRef<Symbol> symbols() const { return Symbols; }
134 
135  /// Returns linker options specified in the input file.
136  StringRef getCOFFLinkerOpts() const { return COFFLinkerOpts; }
137 
138  /// Returns the path to the InputFile.
139  StringRef getName() const;
140 
141  /// Returns the input file's target triple.
142  StringRef getTargetTriple() const { return TargetTriple; }
143 
144  /// Returns the source file path specified at compile time.
145  StringRef getSourceFileName() const { return SourceFileName; }
146 
147  // Returns a table with all the comdats used by this file.
148  ArrayRef<StringRef> getComdatTable() const { return ComdatTable; }
149 
150 private:
151  ArrayRef<Symbol> module_symbols(unsigned I) const {
152  const auto &Indices = ModuleSymIndices[I];
153  return {Symbols.data() + Indices.first, Symbols.data() + Indices.second};
154  }
155 };
156 
157 /// This class wraps an output stream for a native object. Most clients should
158 /// just be able to return an instance of this base class from the stream
159 /// callback, but if a client needs to perform some action after the stream is
160 /// written to, that can be done by deriving from this class and overriding the
161 /// destructor.
163 public:
164  NativeObjectStream(std::unique_ptr<raw_pwrite_stream> OS) : OS(std::move(OS)) {}
165  std::unique_ptr<raw_pwrite_stream> OS;
166  virtual ~NativeObjectStream() = default;
167 };
168 
169 /// This type defines the callback to add a native object that is generated on
170 /// the fly.
171 ///
172 /// Stream callbacks must be thread safe.
173 typedef std::function<std::unique_ptr<NativeObjectStream>(unsigned Task)>
175 
176 /// This is the type of a native object cache. To request an item from the
177 /// cache, pass a unique string as the Key. For hits, the cached file will be
178 /// added to the link and this function will return AddStreamFn(). For misses,
179 /// the cache will return a stream callback which must be called at most once to
180 /// produce content for the stream. The native object stream produced by the
181 /// stream callback will add the file to the link after the stream is written
182 /// to.
183 ///
184 /// Clients generally look like this:
185 ///
186 /// if (AddStreamFn AddStream = Cache(Task, Key))
187 /// ProduceContent(AddStream);
188 typedef std::function<AddStreamFn(unsigned Task, StringRef Key)>
190 
191 /// A ThinBackend defines what happens after the thin-link phase during ThinLTO.
192 /// The details of this type definition aren't important; clients can only
193 /// create a ThinBackend using one of the create*ThinBackend() functions below.
194 typedef std::function<std::unique_ptr<ThinBackendProc>(
195  Config &C, ModuleSummaryIndex &CombinedIndex,
196  StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
197  AddStreamFn AddStream, NativeObjectCache Cache)>
199 
200 /// This ThinBackend runs the individual backend jobs in-process.
201 ThinBackend createInProcessThinBackend(unsigned ParallelismLevel);
202 
203 /// This ThinBackend writes individual module indexes to files, instead of
204 /// running the individual backend jobs. This backend is for distributed builds
205 /// where separate processes will invoke the real backends.
206 ///
207 /// To find the path to write the index to, the backend checks if the path has a
208 /// prefix of OldPrefix; if so, it replaces that prefix with NewPrefix. It then
209 /// appends ".thinlto.bc" and writes the index to that path. If
210 /// ShouldEmitImportsFiles is true it also writes a list of imported files to a
211 /// similar path with ".imports" appended instead.
212 /// LinkedObjectsFile is an output stream to write the list of object files for
213 /// the final ThinLTO linking. Can be nullptr.
214 /// OnWrite is callback which receives module identifier and notifies LTO user
215 /// that index file for the module (and optionally imports file) was created.
216 using IndexWriteCallback = std::function<void(const std::string &)>;
217 ThinBackend createWriteIndexesThinBackend(std::string OldPrefix,
218  std::string NewPrefix,
219  bool ShouldEmitImportsFiles,
220  raw_fd_ostream *LinkedObjectsFile,
221  IndexWriteCallback OnWrite);
222 
223 /// This class implements a resolution-based interface to LLVM's LTO
224 /// functionality. It supports regular LTO, parallel LTO code generation and
225 /// ThinLTO. You can use it from a linker in the following way:
226 /// - Set hooks and code generation options (see lto::Config struct defined in
227 /// Config.h), and use the lto::Config object to create an lto::LTO object.
228 /// - Create lto::InputFile objects using lto::InputFile::create(), then use
229 /// the symbols() function to enumerate its symbols and compute a resolution
230 /// for each symbol (see SymbolResolution below).
231 /// - After the linker has visited each input file (and each regular object
232 /// file) and computed a resolution for each symbol, take each lto::InputFile
233 /// and pass it and an array of symbol resolutions to the add() function.
234 /// - Call the getMaxTasks() function to get an upper bound on the number of
235 /// native object files that LTO may add to the link.
236 /// - Call the run() function. This function will use the supplied AddStream
237 /// and Cache functions to add up to getMaxTasks() native object files to
238 /// the link.
239 class LTO {
240  friend InputFile;
241 
242 public:
243  /// Create an LTO object. A default constructed LTO object has a reasonable
244  /// production configuration, but you can customize it by passing arguments to
245  /// this constructor.
246  /// FIXME: We do currently require the DiagHandler field to be set in Conf.
247  /// Until that is fixed, a Config argument is required.
248  LTO(Config Conf, ThinBackend Backend = nullptr,
249  unsigned ParallelCodeGenParallelismLevel = 1);
250  ~LTO();
251 
252  /// Add an input file to the LTO link, using the provided symbol resolutions.
253  /// The symbol resolutions must appear in the enumeration order given by
254  /// InputFile::symbols().
255  Error add(std::unique_ptr<InputFile> Obj, ArrayRef<SymbolResolution> Res);
256 
257  /// Returns an upper bound on the number of tasks that the client may expect.
258  /// This may only be called after all IR object files have been added. For a
259  /// full description of tasks see LTOBackend.h.
260  unsigned getMaxTasks() const;
261 
262  /// Runs the LTO pipeline. This function calls the supplied AddStream
263  /// function to add native object files to the link.
264  ///
265  /// The Cache parameter is optional. If supplied, it will be used to cache
266  /// native object files and add them to the link.
267  ///
268  /// The client will receive at most one callback (via either AddStream or
269  /// Cache) for each task identifier.
270  Error run(AddStreamFn AddStream, NativeObjectCache Cache = nullptr);
271 
272 private:
273  Config Conf;
274 
275  struct RegularLTOState {
276  RegularLTOState(unsigned ParallelCodeGenParallelismLevel, Config &Conf);
278  uint64_t Size = 0;
279  unsigned Align = 0;
280  /// Record if at least one instance of the common was marked as prevailing
281  bool Prevailing = false;
282  };
283  std::map<std::string, CommonResolution> Commons;
284 
285  unsigned ParallelCodeGenParallelismLevel;
286  LTOLLVMContext Ctx;
287  std::unique_ptr<Module> CombinedModule;
288  std::unique_ptr<IRMover> Mover;
289 
290  // This stores the information about a regular LTO module that we have added
291  // to the link. It will either be linked immediately (for modules without
292  // summaries) or after summary-based dead stripping (for modules with
293  // summaries).
294  struct AddedModule {
295  std::unique_ptr<Module> M;
296  std::vector<GlobalValue *> Keep;
297  };
298  std::vector<AddedModule> ModsWithSummaries;
299  } RegularLTO;
300 
301  struct ThinLTOState {
302  ThinLTOState(ThinBackend Backend);
303 
304  ThinBackend Backend;
305  ModuleSummaryIndex CombinedIndex;
307  DenseMap<GlobalValue::GUID, StringRef> PrevailingModuleForGUID;
308  } ThinLTO;
309 
310  // The global resolution for a particular (mangled) symbol name. This is in
311  // particular necessary to track whether each symbol can be internalized.
312  // Because any input file may introduce a new cross-partition reference, we
313  // cannot make any final internalization decisions until all input files have
314  // been added and the client has called run(). During run() we apply
315  // internalization decisions either directly to the module (for regular LTO)
316  // or to the combined index (for ThinLTO).
317  struct GlobalResolution {
318  /// The unmangled name of the global.
319  std::string IRName;
320 
321  /// Keep track if the symbol is visible outside of a module with a summary
322  /// (i.e. in either a regular object or a regular LTO module without a
323  /// summary).
324  bool VisibleOutsideSummary = false;
325 
326  bool UnnamedAddr = true;
327 
328  /// True if module contains the prevailing definition.
329  bool Prevailing = false;
330 
331  /// Returns true if module contains the prevailing definition and symbol is
332  /// an IR symbol. For example when module-level inline asm block is used,
333  /// symbol can be prevailing in module but have no IR name.
334  bool isPrevailingIRSymbol() const { return Prevailing && !IRName.empty(); }
335 
336  /// This field keeps track of the partition number of this global. The
337  /// regular LTO object is partition 0, while each ThinLTO object has its own
338  /// partition number from 1 onwards.
339  ///
340  /// Any global that is defined or used by more than one partition, or that
341  /// is referenced externally, may not be internalized.
342  ///
343  /// Partitions generally have a one-to-one correspondence with tasks, except
344  /// that we use partition 0 for all parallel LTO code generation partitions.
345  /// Any partitioning of the combined LTO object is done internally by the
346  /// LTO backend.
347  unsigned Partition = Unknown;
348 
349  /// Special partition numbers.
350  enum : unsigned {
351  /// A partition number has not yet been assigned to this global.
352  Unknown = -1u,
353 
354  /// This global is either used by more than one partition or has an
355  /// external reference, and therefore cannot be internalized.
356  External = -2u,
357 
358  /// The RegularLTO partition
359  RegularLTO = 0,
360  };
361  };
362 
363  // Global mapping from mangled symbol names to resolutions.
364  StringMap<GlobalResolution> GlobalResolutions;
365 
366  void addModuleToGlobalRes(ArrayRef<InputFile::Symbol> Syms,
367  ArrayRef<SymbolResolution> Res, unsigned Partition,
368  bool InSummary);
369 
370  // These functions take a range of symbol resolutions [ResI, ResE) and consume
371  // the resolutions used by a single input module by incrementing ResI. After
372  // these functions return, [ResI, ResE) will refer to the resolution range for
373  // the remaining modules in the InputFile.
374  Error addModule(InputFile &Input, unsigned ModI,
375  const SymbolResolution *&ResI, const SymbolResolution *ResE);
376 
378  addRegularLTO(BitcodeModule BM, ArrayRef<InputFile::Symbol> Syms,
379  const SymbolResolution *&ResI, const SymbolResolution *ResE);
380  Error linkRegularLTO(RegularLTOState::AddedModule Mod,
381  bool LivenessFromIndex);
382 
383  Error addThinLTO(BitcodeModule BM, ArrayRef<InputFile::Symbol> Syms,
384  const SymbolResolution *&ResI, const SymbolResolution *ResE);
385 
386  Error runRegularLTO(AddStreamFn AddStream);
387  Error runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache);
388 
389  mutable bool CalledGetMaxTasks = false;
390 };
391 
392 /// The resolution for a symbol. The linker must provide a SymbolResolution for
393 /// each global symbol based on its internal resolution of that symbol.
396  : Prevailing(0), FinalDefinitionInLinkageUnit(0), VisibleToRegularObj(0),
397  LinkerRedefined(0) {}
398 
399  /// The linker has chosen this definition of the symbol.
400  unsigned Prevailing : 1;
401 
402  /// The definition of this symbol is unpreemptable at runtime and is known to
403  /// be in this linkage unit.
405 
406  /// The definition of this symbol is visible outside of the LTO unit.
407  unsigned VisibleToRegularObj : 1;
408 
409  /// Linker redefined version of the symbol which appeared in -wrap or -defsym
410  /// linker option.
411  unsigned LinkerRedefined : 1;
412 };
413 
414 } // namespace lto
415 } // namespace llvm
416 
417 #endif
NativeObjectStream(std::unique_ptr< raw_pwrite_stream > OS)
Definition: LTO.h:164
uint64_t CallInst * C
GlobalValue::VisibilityTypes getVisibility() const
Definition: IRSymtab.h:186
ArrayRef< Symbol > symbols() const
A range over the symbols in this InputFile.
Definition: LTO.h:133
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
StringRef getCOFFWeakExternalFallback() const
COFF-specific: for weak externals, returns the name of the symbol that is used as a fallback if the w...
Definition: IRSymtab.h:218
ArrayRef< StringRef > getComdatTable() const
Definition: LTO.h:148
Expected< std::unique_ptr< ToolOutputFile > > setupOptimizationRemarks(LLVMContext &Context, StringRef LTORemarksFilename, bool LTOPassRemarksWithHotness, int Count=-1)
Setup optimization remarks.
Definition: LTO.cpp:1224
LLVMContext & Context
unsigned Prevailing
The linker has chosen this definition of the symbol.
Definition: LTO.h:400
bool isTLS() const
Definition: IRSymtab.h:195
uint64_t GUID
Declare a type to represent a global unique identifier for a global value.
Definition: GlobalValue.h:493
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Symbol(const irsymtab::Symbol &S)
Definition: LTO.h:114
cl::opt< std::string > LTORemarksFilename("lto-pass-remarks-output", cl::desc("Output filename for pass remarks"), cl::value_desc("filename"))
Contains the information needed by linkers for symbol resolution, as well as by the LTO implementatio...
Definition: IRSymtab.h:87
The purpose of this class is to only expose the symbol information that an LTO client should need in ...
Definition: LTO.h:110
unsigned LinkerRedefined
Linker redefined version of the symbol which appeared in -wrap or -defsym linker option.
Definition: LTO.h:411
bool isExecutable() const
Definition: IRSymtab.h:204
The resolution for a symbol.
Definition: LTO.h:394
This class implements a map that also provides access to all stored values in a deterministic order...
Definition: MapVector.h:38
static Expected< std::unique_ptr< InputFile > > create(MemoryBufferRef Object)
Create an InputFile.
Definition: LTO.cpp:364
std::function< void(const std::string &)> IndexWriteCallback
This ThinBackend writes individual module indexes to files, instead of running the individual backend...
Definition: LTO.h:216
bool canBeOmittedFromSymbolTable() const
Definition: IRSymtab.h:197
ThinBackend createWriteIndexesThinBackend(std::string OldPrefix, std::string NewPrefix, bool ShouldEmitImportsFiles, raw_fd_ostream *LinkedObjectsFile, IndexWriteCallback OnWrite)
Definition: LTO.cpp:1112
std::unique_ptr< raw_pwrite_stream > OS
Definition: LTO.h:165
std::function< std::unique_ptr< NativeObjectStream >unsigned Task)> AddStreamFn
This type defines the callback to add a native object that is generated on the fly.
Definition: LTO.h:174
Definition: BitVector.h:938
Represents a module in a bitcode file.
Definition: BitcodeReader.h:57
StringRef getSourceFileName() const
Returns the source file path specified at compile time.
Definition: LTO.h:145
Tagged union holding either a T or a Error.
Definition: CachePruning.h:23
bool isCommon() const
Definition: IRSymtab.h:192
StringRef getTargetTriple() const
Returns the input file&#39;s target triple.
Definition: LTO.h:142
cl::opt< bool > LTOPassRemarksWithHotness("lto-pass-remarks-with-hotness", cl::desc("With PGO, include profile count in optimization remarks"), cl::Hidden)
bool isUndefined() const
Definition: IRSymtab.h:190
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
An input file.
Definition: LTO.h:83
This class implements a resolution-based interface to LLVM&#39;s LTO functionality.
Definition: LTO.h:239
Class to hold module path string table and global value map, and encapsulate methods for operating on...
StringRef getName() const
Returns the mangled symbol name.
Definition: IRSymtab.h:174
std::unique_ptr< Module > M
Definition: LTO.h:295
std::function< AddStreamFn(unsigned Task, StringRef Key)> NativeObjectCache
This is the type of a native object cache.
Definition: LTO.h:189
uint32_t getCommonAlignment() const
Definition: IRSymtab.h:211
This class wraps an output stream for a native object.
Definition: LTO.h:162
bool isIndirect() const
Definition: IRSymtab.h:193
LTO configuration.
Definition: Config.h:36
This represents a symbol that has been read from a storage::Symbol and possibly a storage::Uncommon...
Definition: IRSymtab.h:162
const T * data() const
Definition: ArrayRef.h:146
StringRef getSectionName() const
Definition: IRSymtab.h:223
std::function< std::unique_ptr< ThinBackendProc > Config &C, ModuleSummaryIndex &CombinedIndex, StringMap< GVSummaryMapTy > &ModuleToDefinedGVSummaries, AddStreamFn AddStream, NativeObjectCache Cache)> ThinBackend
A ThinBackend defines what happens after the thin-link phase during ThinLTO.
Definition: LTO.h:198
int getComdatIndex() const
Returns the index into the comdat table (see Reader::getComdatTable()), or -1 if not a comdat member...
Definition: IRSymtab.h:182
The access may modify the value stored in memory.
StringMap - This is an unconventional map that is specialized for handling keys that are "strings"...
Definition: StringMap.h:220
LinkageTypes
An enumeration for the kinds of linkage for global values.
Definition: GlobalValue.h:48
ThinBackend createInProcessThinBackend(unsigned ParallelismLevel)
This ThinBackend runs the individual backend jobs in-process.
Definition: LTO.cpp:1024
bool isWeak() const
Definition: IRSymtab.h:191
std::vector< GlobalValue * > Keep
Definition: LTO.h:296
A raw_ostream that writes to a file descriptor.
Definition: raw_ostream.h:366
void thinLTOResolveWeakForLinkerInIndex(ModuleSummaryIndex &Index, function_ref< bool(GlobalValue::GUID, const GlobalValueSummary *)> isPrevailing, function_ref< void(StringRef, GlobalValue::GUID, GlobalValue::LinkageTypes)> recordNewLinkage)
Resolve Weak and LinkOnce values in the Index.
Definition: LTO.cpp:319
#define I(x, y, z)
Definition: MD5.cpp:58
uint32_t Size
Definition: Profile.cpp:47
unsigned VisibleToRegularObj
The definition of this symbol is visible outside of the LTO unit.
Definition: LTO.h:407
ModuleSummaryIndex.h This file contains the declarations the classes that hold the module index and s...
StringRef getCOFFLinkerOpts() const
Returns linker options specified in the input file.
Definition: LTO.h:136
Lightweight error class with error context and mandatory checking.
Definition: Error.h:158
uint64_t getCommonSize() const
Definition: IRSymtab.h:206
A derived class of LLVMContext that initializes itself according to a given Config object...
Definition: Config.h:202
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
unsigned FinalDefinitionInLinkageUnit
The definition of this symbol is unpreemptable at runtime and is known to be in this linkage unit...
Definition: LTO.h:404
std::string getThinLTOOutputFile(const std::string &Path, const std::string &OldPrefix, const std::string &NewPrefix)
Given the original Path to an output file, replace any path prefix matching OldPrefix with NewPrefix...
Definition: LTO.cpp:1037
void thinLTOInternalizeAndPromoteInIndex(ModuleSummaryIndex &Index, function_ref< bool(StringRef, GlobalValue::GUID)> isExported)
Update the linkages in the given Index to mark exported values as external and non-exported values as...
Definition: LTO.cpp:354