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