include/llvm/Transforms/IPO/FunctionImport.h

   1 //===- llvm/Transforms/IPO/FunctionImport.h - ThinLTO importing -*- C++ -*-===//
   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 #ifndef LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H
  10 #define LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H
  11
  12 #include "llvm/ADT/DenseSet.h"
  13 #include "llvm/ADT/StringMap.h"
  14 #include "llvm/ADT/StringRef.h"
  15 #include "llvm/IR/GlobalValue.h"
  16 #include "llvm/IR/ModuleSummaryIndex.h"
  17 #include "llvm/IR/PassManager.h"
  18 #include "llvm/Support/Error.h"
  19 #include <functional>
  20 #include <map>
  21 #include <memory>
  22 #include <string>
  23 #include <system_error>
  24 #include <unordered_set>
  25 #include <utility>
  26
  27 namespace llvm {
  28
  29 class Module;
  30
  31 /// The function importer is automatically importing function from other modules
  32 /// based on the provided summary informations.
  33 class FunctionImporter {
  34 public:
  35   /// Set of functions to import from a source module. Each entry is a set
  36   /// containing all the GUIDs of all functions to import for a source module.
  37   using FunctionsToImportTy = std::unordered_set<GlobalValue::GUID>;
  38
  39   /// The different reasons selectCallee will chose not to import a
  40   /// candidate.
  41   enum ImportFailureReason {
  42     None,
  43     // We can encounter a global variable instead of a function in rare
  44     // situations with SamplePGO. See comments where this failure type is
  45     // set for more details.
  46     GlobalVar,
  47     // Found to be globally dead, so we don't bother importing.
  48     NotLive,
  49     // Instruction count over the current threshold.
  50     TooLarge,
  51     // Don't import something with interposable linkage as we can't inline it
  52     // anyway.
  53     InterposableLinkage,
  54     // Generally we won't end up failing due to this reason, as we expect
  55     // to find at least one summary for the GUID that is global or a local
  56     // in the referenced module for direct calls.
  57     LocalLinkageNotInModule,
  58     // This corresponds to the NotEligibleToImport being set on the summary,
  59     // which can happen in a few different cases (e.g. local that can't be
  60     // renamed or promoted because it is referenced on a llvm*.used variable).
  61     NotEligible,
  62     // This corresponds to NoInline being set on the function summary,
  63     // which will happen if it is known that the inliner will not be able
  64     // to inline the function (e.g. it is marked with a NoInline attribute).
  65     NoInline
  66   };
  67
  68   /// Information optionally tracked for candidates the importer decided
  69   /// not to import. Used for optional stat printing.
  70   struct ImportFailureInfo {
  71     // The ValueInfo corresponding to the candidate. We save an index hash
  72     // table lookup for each GUID by stashing this here.
  73     ValueInfo VI;
  74     // The maximum call edge hotness for all failed imports of this candidate.
  75     CalleeInfo::HotnessType MaxHotness;
  76     // most recent reason for failing to import (doesn't necessarily correspond
  77     // to the attempt with the maximum hotness).
  78     ImportFailureReason Reason;
  79     // The number of times we tried to import candidate but failed.
  80     unsigned Attempts;
  81     ImportFailureInfo(ValueInfo VI, CalleeInfo::HotnessType MaxHotness,
  82                       ImportFailureReason Reason, unsigned Attempts)
  83         : VI(VI), MaxHotness(MaxHotness), Reason(Reason), Attempts(Attempts) {}
  84   };
  85
  86   /// Map of callee GUID considered for import into a given module to a pair
  87   /// consisting of the largest threshold applied when deciding whether to
  88   /// import it and, if we decided to import, a pointer to the summary instance
  89   /// imported. If we decided not to import, the summary will be nullptr.
  90   using ImportThresholdsTy =
  91       DenseMap<GlobalValue::GUID,
  92                std::tuple<unsigned, const GlobalValueSummary *,
  93                           std::unique_ptr<ImportFailureInfo>>>;
  94
  95   /// The map contains an entry for every module to import from, the key being
  96   /// the module identifier to pass to the ModuleLoader. The value is the set of
  97   /// functions to import.
  98   using ImportMapTy = StringMap<FunctionsToImportTy>;
  99
 100   /// The set contains an entry for every global value the module exports.
 101   using ExportSetTy = std::unordered_set<GlobalValue::GUID>;
 102
 103   /// A function of this type is used to load modules referenced by the index.
 104   using ModuleLoaderTy =
 105       std::function<Expected<std::unique_ptr<Module>>(StringRef Identifier)>;
 106
 107   /// Create a Function Importer.
 108   FunctionImporter(const ModuleSummaryIndex &Index, ModuleLoaderTy ModuleLoader)
 109       : Index(Index), ModuleLoader(std::move(ModuleLoader)) {}
 110
 111   /// Import functions in Module \p M based on the supplied import list.
 112   Expected<bool> importFunctions(Module &M, const ImportMapTy &ImportList);
 113
 114 private:
 115   /// The summaries index used to trigger importing.
 116   const ModuleSummaryIndex &Index;
 117
 118   /// Factory function to load a Module for a given identifier
 119   ModuleLoaderTy ModuleLoader;
 120 };
 121
 122 /// The function importing pass
 123 class FunctionImportPass : public PassInfoMixin<FunctionImportPass> {
 124 public:
 125   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 126 };
 127
 128 /// Compute all the imports and exports for every module in the Index.
 129 ///
 130 /// \p ModuleToDefinedGVSummaries contains for each Module a map
 131 /// (GUID -> Summary) for every global defined in the module.
 132 ///
 133 /// \p ImportLists will be populated with an entry for every Module we are
 134 /// importing into. This entry is itself a map that can be passed to
 135 /// FunctionImporter::importFunctions() above (see description there).
 136 ///
 137 /// \p ExportLists contains for each Module the set of globals (GUID) that will
 138 /// be imported by another module, or referenced by such a function. I.e. this
 139 /// is the set of globals that need to be promoted/renamed appropriately.
 140 void ComputeCrossModuleImport(
 141     const ModuleSummaryIndex &Index,
 142     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
 143     StringMap<FunctionImporter::ImportMapTy> &ImportLists,
 144     StringMap<FunctionImporter::ExportSetTy> &ExportLists);
 145
 146 /// Compute all the imports for the given module using the Index.
 147 ///
 148 /// \p ImportList will be populated with a map that can be passed to
 149 /// FunctionImporter::importFunctions() above (see description there).
 150 void ComputeCrossModuleImportForModule(
 151     StringRef ModulePath, const ModuleSummaryIndex &Index,
 152     FunctionImporter::ImportMapTy &ImportList);
 153
 154 /// Mark all external summaries in \p Index for import into the given module.
 155 /// Used for distributed builds using a distributed index.
 156 ///
 157 /// \p ImportList will be populated with a map that can be passed to
 158 /// FunctionImporter::importFunctions() above (see description there).
 159 void ComputeCrossModuleImportForModuleFromIndex(
 160     StringRef ModulePath, const ModuleSummaryIndex &Index,
 161     FunctionImporter::ImportMapTy &ImportList);
 162
 163 /// PrevailingType enum used as a return type of callback passed
 164 /// to computeDeadSymbols. Yes and No values used when status explicitly
 165 /// set by symbols resolution, otherwise status is Unknown.
 166 enum class PrevailingType { Yes, No, Unknown };
 167
 168 /// Compute all the symbols that are "dead": i.e these that can't be reached
 169 /// in the graph from any of the given symbols listed in
 170 /// \p GUIDPreservedSymbols. Non-prevailing symbols are symbols without a
 171 /// prevailing copy anywhere in IR and are normally dead, \p isPrevailing
 172 /// predicate returns status of symbol.
 173 void computeDeadSymbols(
 174     ModuleSummaryIndex &Index,
 175     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
 176     function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing);
 177
 178 /// Compute dead symbols and run constant propagation in combined index
 179 /// after that.
 180 void computeDeadSymbolsWithConstProp(
 181     ModuleSummaryIndex &Index,
 182     const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
 183     function_ref<PrevailingType(GlobalValue::GUID)> isPrevailing,
 184     bool ImportEnabled);
 185
 186 /// Converts value \p GV to declaration, or replaces with a declaration if
 187 /// it is an alias. Returns true if converted, false if replaced.
 188 bool convertToDeclaration(GlobalValue &GV);
 189
 190 /// Compute the set of summaries needed for a ThinLTO backend compilation of
 191 /// \p ModulePath.
 192 //
 193 /// This includes summaries from that module (in case any global summary based
 194 /// optimizations were recorded) and from any definitions in other modules that
 195 /// should be imported.
 196 //
 197 /// \p ModuleToSummariesForIndex will be populated with the needed summaries
 198 /// from each required module path. Use a std::map instead of StringMap to get
 199 /// stable order for bitcode emission.
 200 void gatherImportedSummariesForModule(
 201     StringRef ModulePath,
 202     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
 203     const FunctionImporter::ImportMapTy &ImportList,
 204     std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex);
 205
 206 /// Emit into \p OutputFilename the files module \p ModulePath will import from.
 207 std::error_code EmitImportsFiles(
 208     StringRef ModulePath, StringRef OutputFilename,
 209     const std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex);
 210
 211 /// Resolve prevailing symbol linkages in \p TheModule based on the information
 212 /// recorded in the summaries during global summary-based analysis.
 213 void thinLTOResolvePrevailingInModule(Module &TheModule,
 214                                       const GVSummaryMapTy &DefinedGlobals);
 215
 216 /// Internalize \p TheModule based on the information recorded in the summaries
 217 /// during global summary-based analysis.
 218 void thinLTOInternalizeModule(Module &TheModule,
 219                               const GVSummaryMapTy &DefinedGlobals);
 220
 221 } // end namespace llvm
 222
 223 #endif // LLVM_TRANSFORMS_IPO_FUNCTIONIMPORT_H