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