include/llvm/LTO/LTO.h

   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/ADT/StringSet.h"
  21 #include "llvm/IR/DiagnosticInfo.h"
  22 #include "llvm/IR/ModuleSummaryIndex.h"
  23 #include "llvm/IR/RemarkStreamer.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"
  28 #include "llvm/Support/ToolOutputFile.h"
  29 #include "llvm/Support/thread.h"
  30 #include "llvm/Target/TargetOptions.h"
  31 #include "llvm/Transforms/IPO/FunctionImport.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 linkage for prevailing symbols in the \p Index. Linkage changes
  44 /// recorded in the index and the ThinLTO backends must apply the changes to
  45 /// the module via thinLTOResolvePrevailingInModule.
  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).
  49 void thinLTOResolvePrevailingInIndex(
  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     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols);
  56
  57 /// Update the linkages in the given \p Index to mark exported values
  58 /// as external and non-exported values as internal. The ThinLTO backends
  59 /// must apply the changes to the Module via thinLTOInternalizeModule.
  60 void thinLTOInternalizeAndPromoteInIndex(
  61     ModuleSummaryIndex &Index,
  62     function_ref<bool(StringRef, GlobalValue::GUID)> isExported,
  63     function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>
  64         isPrevailing);
  65
  66 /// Computes a unique hash for the Module considering the current list of
  67 /// export/import and other global analysis results.
  68 /// The hash is produced in \p Key.
  69 void computeLTOCacheKey(
  70     SmallString<40> &Key, const lto::Config &Conf,
  71     const ModuleSummaryIndex &Index, StringRef ModuleID,
  72     const FunctionImporter::ImportMapTy &ImportList,
  73     const FunctionImporter::ExportSetTy &ExportList,
  74     const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
  75     const GVSummaryMapTy &DefinedGlobals,
  76     const std::set<GlobalValue::GUID> &CfiFunctionDefs = {},
  77     const std::set<GlobalValue::GUID> &CfiFunctionDecls = {});
  78
  79 namespace lto {
  80
  81 /// Given the original \p Path to an output file, replace any path
  82 /// prefix matching \p OldPrefix with \p NewPrefix. Also, create the
  83 /// resulting directory if it does not yet exist.
  84 std::string getThinLTOOutputFile(const std::string &Path,
  85                                  const std::string &OldPrefix,
  86                                  const std::string &NewPrefix);
  87
  88 /// Setup optimization remarks.
  89 Expected<std::unique_ptr<ToolOutputFile>>
  90 setupOptimizationRemarks(LLVMContext &Context, StringRef RemarksFilename,
  91                          StringRef RemarksPasses, StringRef RemarksFormat,
  92                          bool RemarksWithHotness, int Count = -1);
  93
  94 /// Setups the output file for saving statistics.
  95 Expected<std::unique_ptr<ToolOutputFile>>
  96 setupStatsFile(StringRef StatsFilename);
  97
  98 class LTO;
  99 struct SymbolResolution;
 100 class 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.
 104 class InputFile {
 105 public:
 106   class Symbol;
 107
 108 private:
 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
 124 public:
 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
 180 private:
 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.
 192 class NativeObjectStream {
 193 public:
 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.
 203 using 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);
 218 using 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.
 224 using ThinBackend = std::function<std::unique_ptr<ThinBackendProc>(
 225     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 ThinBackend createInProcessThinBackend(unsigned ParallelismLevel);
 231
 232 /// This ThinBackend writes individual module indexes to files, instead of
 233 /// running the individual backend jobs. This backend is for distributed builds
 234 /// where separate processes will invoke the real backends.
 235 ///
 236 /// To find the path to write the index to, the backend checks if the path has a
 237 /// prefix of OldPrefix; if so, it replaces that prefix with NewPrefix. It then
 238 /// appends ".thinlto.bc" and writes the index to that path. If
 239 /// ShouldEmitImportsFiles is true it also writes a list of imported files to a
 240 /// similar path with ".imports" appended instead.
 241 /// LinkedObjectsFile is an output stream to write the list of object files for
 242 /// the final ThinLTO linking. Can be nullptr.
 243 /// OnWrite is callback which receives module identifier and notifies LTO user
 244 /// that index file for the module (and optionally imports file) was created.
 245 using IndexWriteCallback = std::function<void(const std::string &)>;
 246 ThinBackend createWriteIndexesThinBackend(std::string OldPrefix,
 247                                           std::string NewPrefix,
 248                                           bool ShouldEmitImportsFiles,
 249                                           raw_fd_ostream *LinkedObjectsFile,
 250                                           IndexWriteCallback OnWrite);
 251
 252 /// This class implements a resolution-based interface to LLVM's LTO
 253 /// functionality. It supports regular LTO, parallel LTO code generation and
 254 /// ThinLTO. You can use it from a linker in the following way:
 255 /// - Set hooks and code generation options (see lto::Config struct defined in
 256 ///   Config.h), and use the lto::Config object to create an lto::LTO object.
 257 /// - Create lto::InputFile objects using lto::InputFile::create(), then use
 258 ///   the symbols() function to enumerate its symbols and compute a resolution
 259 ///   for each symbol (see SymbolResolution below).
 260 /// - After the linker has visited each input file (and each regular object
 261 ///   file) and computed a resolution for each symbol, take each lto::InputFile
 262 ///   and pass it and an array of symbol resolutions to the add() function.
 263 /// - Call the getMaxTasks() function to get an upper bound on the number of
 264 ///   native object files that LTO may add to the link.
 265 /// - Call the run() function. This function will use the supplied AddStream
 266 ///   and Cache functions to add up to getMaxTasks() native object files to
 267 ///   the link.
 268 class LTO {
 269   friend InputFile;
 270
 271 public:
 272   /// Create an LTO object. A default constructed LTO object has a reasonable
 273   /// production configuration, but you can customize it by passing arguments to
 274   /// this constructor.
 275   /// FIXME: We do currently require the DiagHandler field to be set in Conf.
 276   /// Until that is fixed, a Config argument is required.
 277   LTO(Config Conf, ThinBackend Backend = nullptr,
 278       unsigned ParallelCodeGenParallelismLevel = 1);
 279   ~LTO();
 280
 281   /// Add an input file to the LTO link, using the provided symbol resolutions.
 282   /// The symbol resolutions must appear in the enumeration order given by
 283   /// InputFile::symbols().
 284   Error add(std::unique_ptr<InputFile> Obj, ArrayRef<SymbolResolution> Res);
 285
 286   /// Returns an upper bound on the number of tasks that the client may expect.
 287   /// This may only be called after all IR object files have been added. For a
 288   /// full description of tasks see LTOBackend.h.
 289   unsigned getMaxTasks() const;
 290
 291   /// Runs the LTO pipeline. This function calls the supplied AddStream
 292   /// function to add native object files to the link.
 293   ///
 294   /// The Cache parameter is optional. If supplied, it will be used to cache
 295   /// native object files and add them to the link.
 296   ///
 297   /// The client will receive at most one callback (via either AddStream or
 298   /// Cache) for each task identifier.
 299   Error run(AddStreamFn AddStream, NativeObjectCache Cache = nullptr);
 300
 301   /// Static method that returns a list of libcall symbols that can be generated
 302   /// by LTO but might not be visible from bitcode symbol table.
 303   static ArrayRef<const char*> getRuntimeLibcallSymbols();
 304
 305 private:
 306   Config Conf;
 307
 308   struct RegularLTOState {
 309     RegularLTOState(unsigned ParallelCodeGenParallelismLevel, Config &Conf);
 310     struct CommonResolution {
 311       uint64_t Size = 0;
 312       MaybeAlign Align;
 313       /// Record if at least one instance of the common was marked as prevailing
 314       bool Prevailing = false;
 315     };
 316     std::map<std::string, CommonResolution> Commons;
 317
 318     unsigned ParallelCodeGenParallelismLevel;
 319     LTOLLVMContext Ctx;
 320     std::unique_ptr<Module> CombinedModule;
 321     std::unique_ptr<IRMover> Mover;
 322
 323     // This stores the information about a regular LTO module that we have added
 324     // to the link. It will either be linked immediately (for modules without
 325     // summaries) or after summary-based dead stripping (for modules with
 326     // summaries).
 327     struct AddedModule {
 328       std::unique_ptr<Module> M;
 329       std::vector<GlobalValue *> Keep;
 330     };
 331     std::vector<AddedModule> ModsWithSummaries;
 332   } RegularLTO;
 333
 334   struct ThinLTOState {
 335     ThinLTOState(ThinBackend Backend);
 336
 337     ThinBackend Backend;
 338     ModuleSummaryIndex CombinedIndex;
 339     MapVector<StringRef, BitcodeModule> ModuleMap;
 340     DenseMap<GlobalValue::GUID, StringRef> PrevailingModuleForGUID;
 341   } ThinLTO;
 342
 343   // The global resolution for a particular (mangled) symbol name. This is in
 344   // particular necessary to track whether each symbol can be internalized.
 345   // Because any input file may introduce a new cross-partition reference, we
 346   // cannot make any final internalization decisions until all input files have
 347   // been added and the client has called run(). During run() we apply
 348   // internalization decisions either directly to the module (for regular LTO)
 349   // or to the combined index (for ThinLTO).
 350   struct GlobalResolution {
 351     /// The unmangled name of the global.
 352     std::string IRName;
 353
 354     /// Keep track if the symbol is visible outside of a module with a summary
 355     /// (i.e. in either a regular object or a regular LTO module without a
 356     /// summary).
 357     bool VisibleOutsideSummary = false;
 358
 359     bool UnnamedAddr = true;
 360
 361     /// True if module contains the prevailing definition.
 362     bool Prevailing = false;
 363
 364     /// Returns true if module contains the prevailing definition and symbol is
 365     /// an IR symbol. For example when module-level inline asm block is used,
 366     /// symbol can be prevailing in module but have no IR name.
 367     bool isPrevailingIRSymbol() const { return Prevailing && !IRName.empty(); }
 368
 369     /// This field keeps track of the partition number of this global. The
 370     /// regular LTO object is partition 0, while each ThinLTO object has its own
 371     /// partition number from 1 onwards.
 372     ///
 373     /// Any global that is defined or used by more than one partition, or that
 374     /// is referenced externally, may not be internalized.
 375     ///
 376     /// Partitions generally have a one-to-one correspondence with tasks, except
 377     /// that we use partition 0 for all parallel LTO code generation partitions.
 378     /// Any partitioning of the combined LTO object is done internally by the
 379     /// LTO backend.
 380     unsigned Partition = Unknown;
 381
 382     /// Special partition numbers.
 383     enum : unsigned {
 384       /// A partition number has not yet been assigned to this global.
 385       Unknown = -1u,
 386
 387       /// This global is either used by more than one partition or has an
 388       /// external reference, and therefore cannot be internalized.
 389       External = -2u,
 390
 391       /// The RegularLTO partition
 392       RegularLTO = 0,
 393     };
 394   };
 395
 396   // Global mapping from mangled symbol names to resolutions.
 397   StringMap<GlobalResolution> GlobalResolutions;
 398
 399   void addModuleToGlobalRes(ArrayRef<InputFile::Symbol> Syms,
 400                             ArrayRef<SymbolResolution> Res, unsigned Partition,
 401                             bool InSummary);
 402
 403   // These functions take a range of symbol resolutions [ResI, ResE) and consume
 404   // the resolutions used by a single input module by incrementing ResI. After
 405   // these functions return, [ResI, ResE) will refer to the resolution range for
 406   // the remaining modules in the InputFile.
 407   Error addModule(InputFile &Input, unsigned ModI,
 408                   const SymbolResolution *&ResI, const SymbolResolution *ResE);
 409
 410   Expected<RegularLTOState::AddedModule>
 411   addRegularLTO(BitcodeModule BM, ArrayRef<InputFile::Symbol> Syms,
 412                 const SymbolResolution *&ResI, const SymbolResolution *ResE);
 413   Error linkRegularLTO(RegularLTOState::AddedModule Mod,
 414                        bool LivenessFromIndex);
 415
 416   Error addThinLTO(BitcodeModule BM, ArrayRef<InputFile::Symbol> Syms,
 417                    const SymbolResolution *&ResI, const SymbolResolution *ResE);
 418
 419   Error runRegularLTO(AddStreamFn AddStream);
 420   Error runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache,
 421                    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols);
 422
 423   Error checkPartiallySplit();
 424
 425   mutable bool CalledGetMaxTasks = false;
 426
 427   // Use Optional to distinguish false from not yet initialized.
 428   Optional<bool> EnableSplitLTOUnit;
 429 };
 430
 431 /// The resolution for a symbol. The linker must provide a SymbolResolution for
 432 /// each global symbol based on its internal resolution of that symbol.
 433 struct SymbolResolution {
 434   SymbolResolution()
 435       : Prevailing(0), FinalDefinitionInLinkageUnit(0), VisibleToRegularObj(0),
 436         LinkerRedefined(0) {}
 437
 438   /// The linker has chosen this definition of the symbol.
 439   unsigned Prevailing : 1;
 440
 441   /// The definition of this symbol is unpreemptable at runtime and is known to
 442   /// be in this linkage unit.
 443   unsigned FinalDefinitionInLinkageUnit : 1;
 444
 445   /// The definition of this symbol is visible outside of the LTO unit.
 446   unsigned VisibleToRegularObj : 1;
 447
 448   /// Linker redefined version of the symbol which appeared in -wrap or -defsym
 449   /// linker option.
 450   unsigned LinkerRedefined : 1;
 451 };
 452
 453 } // namespace lto
 454 } // namespace llvm
 455
 456 #endif