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