include/llvm/LTO/LTO.h

   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/CodeGen/Analysis.h"
  23 #include "llvm/IR/DiagnosticInfo.h"
  24 #include "llvm/IR/ModuleSummaryIndex.h"
  25 #include "llvm/LTO/Config.h"
  26 #include "llvm/Linker/IRMover.h"
  27 #include "llvm/Object/IRObjectFile.h"
  28 #include "llvm/Support/Error.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 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).
  49 void thinLTOResolveWeakForLinkerInIndex(
  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.
  59 void thinLTOInternalizeAndPromoteInIndex(
  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 class LTO;
  73 struct SymbolResolution;
  74 class ThinBackendProc;
  75
  76 /// An input file. This is a wrapper for ModuleSymbolTable that exposes only the
  77 /// information that an LTO client should need in order to do symbol resolution.
  78 class InputFile {
  79   // FIXME: Remove LTO class friendship once we have bitcode symbol tables.
  80   friend LTO;
  81   InputFile() = default;
  82
  83   // FIXME: Remove the LLVMContext once we have bitcode symbol tables.
  84   LLVMContext Ctx;
  85   struct InputModule;
  86   std::vector<InputModule> Mods;
  87   ModuleSymbolTable SymTab;
  88
  89   std::vector<StringRef> Comdats;
  90   DenseMap<const Comdat *, unsigned> ComdatMap;
  91
  92 public:
  93   ~InputFile();
  94
  95   /// Create an InputFile.
  96   static Expected<std::unique_ptr<InputFile>> create(MemoryBufferRef Object);
  97
  98   class symbol_iterator;
  99
 100   /// This is a wrapper for ArrayRef<ModuleSymbolTable::Symbol>::iterator that
 101   /// exposes only the information that an LTO client should need in order to do
 102   /// symbol resolution.
 103   ///
 104   /// This object is ephemeral; it is only valid as long as an iterator obtained
 105   /// from symbols() refers to it.
 106   class Symbol {
 107     friend symbol_iterator;
 108     friend LTO;
 109
 110     ArrayRef<ModuleSymbolTable::Symbol>::iterator I;
 111     const ModuleSymbolTable &SymTab;
 112     const InputFile *File;
 113     uint32_t Flags;
 114     SmallString<64> Name;
 115
 116     bool shouldSkip() {
 117       return !(Flags & object::BasicSymbolRef::SF_Global) ||
 118              (Flags & object::BasicSymbolRef::SF_FormatSpecific);
 119     }
 120
 121     void skip() {
 122       ArrayRef<ModuleSymbolTable::Symbol>::iterator E = SymTab.symbols().end();
 123       while (I != E) {
 124         Flags = SymTab.getSymbolFlags(*I);
 125         if (!shouldSkip())
 126           break;
 127         ++I;
 128       }
 129       if (I == E)
 130         return;
 131
 132       Name.clear();
 133       {
 134         raw_svector_ostream OS(Name);
 135         SymTab.printSymbolName(OS, *I);
 136       }
 137     }
 138
 139     bool isGV() const { return I->is<GlobalValue *>(); }
 140     GlobalValue *getGV() const { return I->get<GlobalValue *>(); }
 141
 142   public:
 143     Symbol(ArrayRef<ModuleSymbolTable::Symbol>::iterator I,
 144            const ModuleSymbolTable &SymTab, const InputFile *File)
 145         : I(I), SymTab(SymTab), File(File) {
 146       skip();
 147     }
 148
 149     /// For COFF weak externals, returns the name of the symbol that is used
 150     /// as a fallback if the weak external remains undefined.
 151     std::string getCOFFWeakExternalFallback() const {
 152       assert((Flags & object::BasicSymbolRef::SF_Weak) &&
 153              (Flags & object::BasicSymbolRef::SF_Indirect) &&
 154              "symbol is not a weak external");
 155       std::string Name;
 156       raw_string_ostream OS(Name);
 157       SymTab.printSymbolName(
 158           OS,
 159           cast<GlobalValue>(
 160               cast<GlobalAlias>(getGV())->getAliasee()->stripPointerCasts()));
 161       OS.flush();
 162       return Name;
 163     }
 164
 165     /// Returns the mangled name of the global.
 166     StringRef getName() const { return Name; }
 167
 168     uint32_t getFlags() const { return Flags; }
 169     GlobalValue::VisibilityTypes getVisibility() const {
 170       if (isGV())
 171         return getGV()->getVisibility();
 172       return GlobalValue::DefaultVisibility;
 173     }
 174     bool canBeOmittedFromSymbolTable() const {
 175       return isGV() && llvm::canBeOmittedFromSymbolTable(getGV());
 176     }
 177     bool isTLS() const {
 178       // FIXME: Expose a thread-local flag for module asm symbols.
 179       return isGV() && getGV()->isThreadLocal();
 180     }
 181
 182     // Returns the index of the comdat this symbol is in or -1 if the symbol
 183     // is not in a comdat.
 184     // FIXME: We have to return Expected<int> because aliases point to an
 185     // arbitrary ConstantExpr and that might not actually be a constant. That
 186     // means we might not be able to find what an alias is aliased to and
 187     // so find its comdat.
 188     Expected<int> getComdatIndex() const;
 189
 190     uint64_t getCommonSize() const {
 191       assert(Flags & object::BasicSymbolRef::SF_Common);
 192       if (!isGV())
 193         return 0;
 194       return getGV()->getParent()->getDataLayout().getTypeAllocSize(
 195           getGV()->getType()->getElementType());
 196     }
 197     unsigned getCommonAlignment() const {
 198       assert(Flags & object::BasicSymbolRef::SF_Common);
 199       if (!isGV())
 200         return 0;
 201       return getGV()->getAlignment();
 202     }
 203   };
 204
 205   class symbol_iterator {
 206     Symbol Sym;
 207
 208   public:
 209     symbol_iterator(ArrayRef<ModuleSymbolTable::Symbol>::iterator I,
 210                     const ModuleSymbolTable &SymTab, const InputFile *File)
 211         : Sym(I, SymTab, File) {}
 212
 213     symbol_iterator &operator++() {
 214       ++Sym.I;
 215       Sym.skip();
 216       return *this;
 217     }
 218
 219     symbol_iterator operator++(int) {
 220       symbol_iterator I = *this;
 221       ++*this;
 222       return I;
 223     }
 224
 225     const Symbol &operator*() const { return Sym; }
 226     const Symbol *operator->() const { return &Sym; }
 227
 228     bool operator!=(const symbol_iterator &Other) const {
 229       return Sym.I != Other.Sym.I;
 230     }
 231   };
 232
 233   /// A range over the symbols in this InputFile.
 234   iterator_range<symbol_iterator> symbols() {
 235     return llvm::make_range(
 236         symbol_iterator(SymTab.symbols().begin(), SymTab, this),
 237         symbol_iterator(SymTab.symbols().end(), SymTab, this));
 238   }
 239
 240   /// Returns linker options specified in the input file.
 241   Expected<std::string> getLinkerOpts();
 242
 243   /// Returns the path to the InputFile.
 244   StringRef getName() const;
 245
 246   /// Returns the source file path specified at compile time.
 247   StringRef getSourceFileName() const;
 248
 249   // Returns a table with all the comdats used by this file.
 250   ArrayRef<StringRef> getComdatTable() const { return Comdats; }
 251
 252 private:
 253   iterator_range<symbol_iterator> module_symbols(InputModule &IM);
 254 };
 255
 256 /// This class wraps an output stream for a native object. Most clients should
 257 /// just be able to return an instance of this base class from the stream
 258 /// callback, but if a client needs to perform some action after the stream is
 259 /// written to, that can be done by deriving from this class and overriding the
 260 /// destructor.
 261 class NativeObjectStream {
 262 public:
 263   NativeObjectStream(std::unique_ptr<raw_pwrite_stream> OS) : OS(std::move(OS)) {}
 264   std::unique_ptr<raw_pwrite_stream> OS;
 265   virtual ~NativeObjectStream() = default;
 266 };
 267
 268 /// This type defines the callback to add a native object that is generated on
 269 /// the fly.
 270 ///
 271 /// Stream callbacks must be thread safe.
 272 typedef std::function<std::unique_ptr<NativeObjectStream>(unsigned Task)>
 273     AddStreamFn;
 274
 275 /// This is the type of a native object cache. To request an item from the
 276 /// cache, pass a unique string as the Key. For hits, the cached file will be
 277 /// added to the link and this function will return AddStreamFn(). For misses,
 278 /// the cache will return a stream callback which must be called at most once to
 279 /// produce content for the stream. The native object stream produced by the
 280 /// stream callback will add the file to the link after the stream is written
 281 /// to.
 282 ///
 283 /// Clients generally look like this:
 284 ///
 285 /// if (AddStreamFn AddStream = Cache(Task, Key))
 286 ///   ProduceContent(AddStream);
 287 typedef std::function<AddStreamFn(unsigned Task, StringRef Key)>
 288     NativeObjectCache;
 289
 290 /// A ThinBackend defines what happens after the thin-link phase during ThinLTO.
 291 /// The details of this type definition aren't important; clients can only
 292 /// create a ThinBackend using one of the create*ThinBackend() functions below.
 293 typedef std::function<std::unique_ptr<ThinBackendProc>(
 294     Config &C, ModuleSummaryIndex &CombinedIndex,
 295     StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
 296     AddStreamFn AddStream, NativeObjectCache Cache)>
 297     ThinBackend;
 298
 299 /// This ThinBackend runs the individual backend jobs in-process.
 300 ThinBackend createInProcessThinBackend(unsigned ParallelismLevel);
 301
 302 /// This ThinBackend writes individual module indexes to files, instead of
 303 /// running the individual backend jobs. This backend is for distributed builds
 304 /// where separate processes will invoke the real backends.
 305 ///
 306 /// To find the path to write the index to, the backend checks if the path has a
 307 /// prefix of OldPrefix; if so, it replaces that prefix with NewPrefix. It then
 308 /// appends ".thinlto.bc" and writes the index to that path. If
 309 /// ShouldEmitImportsFiles is true it also writes a list of imported files to a
 310 /// similar path with ".imports" appended instead.
 311 ThinBackend createWriteIndexesThinBackend(std::string OldPrefix,
 312                                           std::string NewPrefix,
 313                                           bool ShouldEmitImportsFiles,
 314                                           std::string LinkedObjectsFile);
 315
 316 /// This class implements a resolution-based interface to LLVM's LTO
 317 /// functionality. It supports regular LTO, parallel LTO code generation and
 318 /// ThinLTO. You can use it from a linker in the following way:
 319 /// - Set hooks and code generation options (see lto::Config struct defined in
 320 ///   Config.h), and use the lto::Config object to create an lto::LTO object.
 321 /// - Create lto::InputFile objects using lto::InputFile::create(), then use
 322 ///   the symbols() function to enumerate its symbols and compute a resolution
 323 ///   for each symbol (see SymbolResolution below).
 324 /// - After the linker has visited each input file (and each regular object
 325 ///   file) and computed a resolution for each symbol, take each lto::InputFile
 326 ///   and pass it and an array of symbol resolutions to the add() function.
 327 /// - Call the getMaxTasks() function to get an upper bound on the number of
 328 ///   native object files that LTO may add to the link.
 329 /// - Call the run() function. This function will use the supplied AddStream
 330 ///   and Cache functions to add up to getMaxTasks() native object files to
 331 ///   the link.
 332 class LTO {
 333   friend InputFile;
 334
 335 public:
 336   /// Create an LTO object. A default constructed LTO object has a reasonable
 337   /// production configuration, but you can customize it by passing arguments to
 338   /// this constructor.
 339   /// FIXME: We do currently require the DiagHandler field to be set in Conf.
 340   /// Until that is fixed, a Config argument is required.
 341   LTO(Config Conf, ThinBackend Backend = nullptr,
 342       unsigned ParallelCodeGenParallelismLevel = 1);
 343   ~LTO();
 344
 345   /// Add an input file to the LTO link, using the provided symbol resolutions.
 346   /// The symbol resolutions must appear in the enumeration order given by
 347   /// InputFile::symbols().
 348   Error add(std::unique_ptr<InputFile> Obj, ArrayRef<SymbolResolution> Res);
 349
 350   /// Returns an upper bound on the number of tasks that the client may expect.
 351   /// This may only be called after all IR object files have been added. For a
 352   /// full description of tasks see LTOBackend.h.
 353   unsigned getMaxTasks() const;
 354
 355   /// Runs the LTO pipeline. This function calls the supplied AddStream
 356   /// function to add native object files to the link.
 357   ///
 358   /// The Cache parameter is optional. If supplied, it will be used to cache
 359   /// native object files and add them to the link.
 360   ///
 361   /// The client will receive at most one callback (via either AddStream or
 362   /// Cache) for each task identifier.
 363   Error run(AddStreamFn AddStream, NativeObjectCache Cache = nullptr);
 364
 365 private:
 366   Config Conf;
 367
 368   struct RegularLTOState {
 369     RegularLTOState(unsigned ParallelCodeGenParallelismLevel, Config &Conf);
 370     struct CommonResolution {
 371       uint64_t Size = 0;
 372       unsigned Align = 0;
 373       /// Record if at least one instance of the common was marked as prevailing
 374       bool Prevailing = false;
 375     };
 376     std::map<std::string, CommonResolution> Commons;
 377
 378     unsigned ParallelCodeGenParallelismLevel;
 379     LTOLLVMContext Ctx;
 380     bool HasModule = false;
 381     std::unique_ptr<Module> CombinedModule;
 382     std::unique_ptr<IRMover> Mover;
 383   } RegularLTO;
 384
 385   struct ThinLTOState {
 386     ThinLTOState(ThinBackend Backend);
 387
 388     ThinBackend Backend;
 389     ModuleSummaryIndex CombinedIndex;
 390     MapVector<StringRef, BitcodeModule> ModuleMap;
 391     DenseMap<GlobalValue::GUID, StringRef> PrevailingModuleForGUID;
 392   } ThinLTO;
 393
 394   // The global resolution for a particular (mangled) symbol name. This is in
 395   // particular necessary to track whether each symbol can be internalized.
 396   // Because any input file may introduce a new cross-partition reference, we
 397   // cannot make any final internalization decisions until all input files have
 398   // been added and the client has called run(). During run() we apply
 399   // internalization decisions either directly to the module (for regular LTO)
 400   // or to the combined index (for ThinLTO).
 401   struct GlobalResolution {
 402     /// The unmangled name of the global.
 403     std::string IRName;
 404
 405     /// Keep track if the symbol is visible outside of ThinLTO (i.e. in
 406     /// either a regular object or the regular LTO partition).
 407     bool VisibleOutsideThinLTO = false;
 408
 409     bool UnnamedAddr = true;
 410
 411     /// This field keeps track of the partition number of this global. The
 412     /// regular LTO object is partition 0, while each ThinLTO object has its own
 413     /// partition number from 1 onwards.
 414     ///
 415     /// Any global that is defined or used by more than one partition, or that
 416     /// is referenced externally, may not be internalized.
 417     ///
 418     /// Partitions generally have a one-to-one correspondence with tasks, except
 419     /// that we use partition 0 for all parallel LTO code generation partitions.
 420     /// Any partitioning of the combined LTO object is done internally by the
 421     /// LTO backend.
 422     unsigned Partition = Unknown;
 423
 424     /// Special partition numbers.
 425     enum : unsigned {
 426       /// A partition number has not yet been assigned to this global.
 427       Unknown = -1u,
 428
 429       /// This global is either used by more than one partition or has an
 430       /// external reference, and therefore cannot be internalized.
 431       External = -2u,
 432
 433       /// The RegularLTO partition
 434       RegularLTO = 0,
 435     };
 436   };
 437
 438   // Global mapping from mangled symbol names to resolutions.
 439   StringMap<GlobalResolution> GlobalResolutions;
 440
 441   void addSymbolToGlobalRes(SmallPtrSet<GlobalValue *, 8> &Used,
 442                             const InputFile::Symbol &Sym, SymbolResolution Res,
 443                             unsigned Partition);
 444
 445   // These functions take a range of symbol resolutions [ResI, ResE) and consume
 446   // the resolutions used by a single input module by incrementing ResI. After
 447   // these functions return, [ResI, ResE) will refer to the resolution range for
 448   // the remaining modules in the InputFile.
 449   Error addModule(InputFile &Input, InputFile::InputModule &IM,
 450                   const SymbolResolution *&ResI, const SymbolResolution *ResE);
 451   Error addRegularLTO(BitcodeModule BM, const SymbolResolution *&ResI,
 452                       const SymbolResolution *ResE);
 453   Error addThinLTO(BitcodeModule BM, Module &M,
 454                    iterator_range<InputFile::symbol_iterator> Syms,
 455                    const SymbolResolution *&ResI, const SymbolResolution *ResE);
 456
 457   Error runRegularLTO(AddStreamFn AddStream);
 458   Error runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache,
 459                    bool HasRegularLTO);
 460
 461   mutable bool CalledGetMaxTasks = false;
 462 };
 463
 464 /// The resolution for a symbol. The linker must provide a SymbolResolution for
 465 /// each global symbol based on its internal resolution of that symbol.
 466 struct SymbolResolution {
 467   SymbolResolution()
 468       : Prevailing(0), FinalDefinitionInLinkageUnit(0), VisibleToRegularObj(0) {
 469   }
 470   /// The linker has chosen this definition of the symbol.
 471   unsigned Prevailing : 1;
 472
 473   /// The definition of this symbol is unpreemptable at runtime and is known to
 474   /// be in this linkage unit.
 475   unsigned FinalDefinitionInLinkageUnit : 1;
 476
 477   /// The definition of this symbol is visible outside of the LTO unit.
 478   unsigned VisibleToRegularObj : 1;
 479 };
 480
 481 } // namespace lto
 482 } // namespace llvm
 483
 484 #endif