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