/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/IPO/FunctionImport.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- FunctionImport.cpp - ThinLTO Summary-based Function Import ---------===// |
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 implements Function import based on summaries. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "llvm/Transforms/IPO/FunctionImport.h" |
15 | | |
16 | | #include "llvm/ADT/SmallVector.h" |
17 | | #include "llvm/ADT/Statistic.h" |
18 | | #include "llvm/ADT/StringSet.h" |
19 | | #include "llvm/ADT/Triple.h" |
20 | | #include "llvm/Bitcode/BitcodeReader.h" |
21 | | #include "llvm/IR/AutoUpgrade.h" |
22 | | #include "llvm/IR/DiagnosticPrinter.h" |
23 | | #include "llvm/IR/IntrinsicInst.h" |
24 | | #include "llvm/IR/Module.h" |
25 | | #include "llvm/IR/Verifier.h" |
26 | | #include "llvm/IRReader/IRReader.h" |
27 | | #include "llvm/Linker/Linker.h" |
28 | | #include "llvm/Object/IRObjectFile.h" |
29 | | #include "llvm/Support/CommandLine.h" |
30 | | #include "llvm/Support/Debug.h" |
31 | | #include "llvm/Support/SourceMgr.h" |
32 | | #include "llvm/Transforms/IPO/Internalize.h" |
33 | | #include "llvm/Transforms/Utils/FunctionImportUtils.h" |
34 | | |
35 | | #define DEBUG_TYPE "function-import" |
36 | | |
37 | | using namespace llvm; |
38 | | |
39 | | STATISTIC(NumImportedFunctions, "Number of functions imported"); |
40 | | STATISTIC(NumImportedModules, "Number of modules imported from"); |
41 | | STATISTIC(NumDeadSymbols, "Number of dead stripped symbols in index"); |
42 | | STATISTIC(NumLiveSymbols, "Number of live symbols in index"); |
43 | | |
44 | | /// Limit on instruction count of imported functions. |
45 | | static cl::opt<unsigned> ImportInstrLimit( |
46 | | "import-instr-limit", cl::init(100), cl::Hidden, cl::value_desc("N"), |
47 | | cl::desc("Only import functions with less than N instructions")); |
48 | | |
49 | | static cl::opt<float> |
50 | | ImportInstrFactor("import-instr-evolution-factor", cl::init(0.7), |
51 | | cl::Hidden, cl::value_desc("x"), |
52 | | cl::desc("As we import functions, multiply the " |
53 | | "`import-instr-limit` threshold by this factor " |
54 | | "before processing newly imported functions")); |
55 | | |
56 | | static cl::opt<float> ImportHotInstrFactor( |
57 | | "import-hot-evolution-factor", cl::init(1.0), cl::Hidden, |
58 | | cl::value_desc("x"), |
59 | | cl::desc("As we import functions called from hot callsite, multiply the " |
60 | | "`import-instr-limit` threshold by this factor " |
61 | | "before processing newly imported functions")); |
62 | | |
63 | | static cl::opt<float> ImportHotMultiplier( |
64 | | "import-hot-multiplier", cl::init(10.0), cl::Hidden, cl::value_desc("x"), |
65 | | cl::desc("Multiply the `import-instr-limit` threshold for hot callsites")); |
66 | | |
67 | | static cl::opt<float> ImportCriticalMultiplier( |
68 | | "import-critical-multiplier", cl::init(100.0), cl::Hidden, |
69 | | cl::value_desc("x"), |
70 | | cl::desc( |
71 | | "Multiply the `import-instr-limit` threshold for critical callsites")); |
72 | | |
73 | | // FIXME: This multiplier was not really tuned up. |
74 | | static cl::opt<float> ImportColdMultiplier( |
75 | | "import-cold-multiplier", cl::init(0), cl::Hidden, cl::value_desc("N"), |
76 | | cl::desc("Multiply the `import-instr-limit` threshold for cold callsites")); |
77 | | |
78 | | static cl::opt<bool> PrintImports("print-imports", cl::init(false), cl::Hidden, |
79 | | cl::desc("Print imported functions")); |
80 | | |
81 | | static cl::opt<bool> ComputeDead("compute-dead", cl::init(true), cl::Hidden, |
82 | | cl::desc("Compute dead symbols")); |
83 | | |
84 | | static cl::opt<bool> EnableImportMetadata( |
85 | | "enable-import-metadata", cl::init( |
86 | | #if !defined(NDEBUG) |
87 | | true /*Enabled with asserts.*/ |
88 | | #else |
89 | | false |
90 | | #endif |
91 | | ), |
92 | | cl::Hidden, cl::desc("Enable import metadata like 'thinlto_src_module'")); |
93 | | |
94 | | // Load lazily a module from \p FileName in \p Context. |
95 | | static std::unique_ptr<Module> loadFile(const std::string &FileName, |
96 | 18 | LLVMContext &Context) { |
97 | 18 | SMDiagnostic Err; |
98 | 18 | DEBUG(dbgs() << "Loading '" << FileName << "'\n"); |
99 | 18 | // Metadata isn't loaded until functions are imported, to minimize |
100 | 18 | // the memory overhead. |
101 | 18 | std::unique_ptr<Module> Result = |
102 | 18 | getLazyIRFileModule(FileName, Err, Context, |
103 | 18 | /* ShouldLazyLoadMetadata = */ true); |
104 | 18 | if (!Result18 ) { |
105 | 0 | Err.print("function-import", errs()); |
106 | 0 | report_fatal_error("Abort"); |
107 | 0 | } |
108 | 18 | |
109 | 18 | return Result; |
110 | 18 | } |
111 | | |
112 | | namespace { |
113 | | |
114 | | /// Given a list of possible callee implementation for a call site, select one |
115 | | /// that fits the \p Threshold. |
116 | | /// |
117 | | /// FIXME: select "best" instead of first that fits. But what is "best"? |
118 | | /// - The smallest: more likely to be inlined. |
119 | | /// - The one with the least outgoing edges (already well optimized). |
120 | | /// - One from a module already being imported from in order to reduce the |
121 | | /// number of source modules parsed/linked. |
122 | | /// - One that has PGO data attached. |
123 | | /// - [insert you fancy metric here] |
124 | | static const GlobalValueSummary * |
125 | | selectCallee(const ModuleSummaryIndex &Index, |
126 | | ArrayRef<std::unique_ptr<GlobalValueSummary>> CalleeSummaryList, |
127 | 320 | unsigned Threshold, StringRef CallerModulePath) { |
128 | 320 | auto It = llvm::find_if( |
129 | 320 | CalleeSummaryList, |
130 | 323 | [&](const std::unique_ptr<GlobalValueSummary> &SummaryPtr) { |
131 | 323 | auto *GVSummary = SummaryPtr.get(); |
132 | 323 | // For SamplePGO, in computeImportForFunction the OriginalId |
133 | 323 | // may have been used to locate the callee summary list (See |
134 | 323 | // comment there). |
135 | 323 | // The mapping from OriginalId to GUID may return a GUID |
136 | 323 | // that corresponds to a static variable. Filter it out here. |
137 | 323 | // This can happen when |
138 | 323 | // 1) There is a call to a library function which is not defined |
139 | 323 | // in the index. |
140 | 323 | // 2) There is a static variable with the OriginalGUID identical |
141 | 323 | // to the GUID of the library function in 1); |
142 | 323 | // When this happens, the logic for SamplePGO kicks in and |
143 | 323 | // the static variable in 2) will be found, which needs to be |
144 | 323 | // filtered out. |
145 | 323 | if (GVSummary->getSummaryKind() == GlobalValueSummary::GlobalVarKind) |
146 | 2 | return false; |
147 | 321 | if (321 GlobalValue::isInterposableLinkage(GVSummary->linkage())321 ) |
148 | 321 | // There is no point in importing these, we can't inline them |
149 | 33 | return false; |
150 | 288 | if (288 isa<AliasSummary>(GVSummary)288 ) |
151 | 288 | // Aliases can't point to "available_externally". |
152 | 288 | // FIXME: we should import alias as available_externally *function*, |
153 | 288 | // the destination module does not need to know it is an alias. |
154 | 40 | return false; |
155 | 248 | |
156 | 248 | auto *Summary = cast<FunctionSummary>(GVSummary); |
157 | 248 | |
158 | 248 | // If this is a local function, make sure we import the copy |
159 | 248 | // in the caller's module. The only time a local function can |
160 | 248 | // share an entry in the index is if there is a local with the same name |
161 | 248 | // in another module that had the same source file name (in a different |
162 | 248 | // directory), where each was compiled in their own directory so there |
163 | 248 | // was not distinguishing path. |
164 | 248 | // However, do the import from another module if there is only one |
165 | 248 | // entry in the list - in that case this must be a reference due |
166 | 248 | // to indirect call profile data, since a function pointer can point to |
167 | 248 | // a local in another module. |
168 | 248 | if (GlobalValue::isLocalLinkage(Summary->linkage()) && |
169 | 16 | CalleeSummaryList.size() > 1 && |
170 | 6 | Summary->modulePath() != CallerModulePath) |
171 | 3 | return false; |
172 | 245 | |
173 | 245 | if (245 Summary->instCount() > Threshold245 ) |
174 | 51 | return false; |
175 | 194 | |
176 | 194 | if (194 Summary->notEligibleToImport()194 ) |
177 | 10 | return false; |
178 | 184 | |
179 | 184 | return true; |
180 | 184 | }); |
181 | 320 | if (It == CalleeSummaryList.end()) |
182 | 136 | return nullptr; |
183 | 184 | |
184 | 184 | return cast<GlobalValueSummary>(It->get()); |
185 | 184 | } |
186 | | |
187 | | using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */, |
188 | | GlobalValue::GUID>; |
189 | | |
190 | | static ValueInfo |
191 | 572 | updateValueInfoForIndirectCalls(const ModuleSummaryIndex &Index, ValueInfo VI) { |
192 | 572 | if (!VI.getSummaryList().empty()) |
193 | 523 | return VI; |
194 | 49 | // For SamplePGO, the indirect call targets for local functions will |
195 | 49 | // have its original name annotated in profile. We try to find the |
196 | 49 | // corresponding PGOFuncName as the GUID. |
197 | 49 | // FIXME: Consider updating the edges in the graph after building |
198 | 49 | // it, rather than needing to perform this mapping on each walk. |
199 | 49 | auto GUID = Index.getGUIDFromOriginalID(VI.getGUID()); |
200 | 49 | if (GUID == 0) |
201 | 39 | return nullptr; |
202 | 10 | return Index.getValueInfo(GUID); |
203 | 10 | } |
204 | | |
205 | | /// Compute the list of functions to import for a given caller. Mark these |
206 | | /// imported functions and the symbols they reference in their source module as |
207 | | /// exported from their source module. |
208 | | static void computeImportForFunction( |
209 | | const FunctionSummary &Summary, const ModuleSummaryIndex &Index, |
210 | | const unsigned Threshold, const GVSummaryMapTy &DefinedGVSummaries, |
211 | | SmallVectorImpl<EdgeInfo> &Worklist, |
212 | | FunctionImporter::ImportMapTy &ImportList, |
213 | 798 | StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) { |
214 | 400 | for (auto &Edge : Summary.calls()) { |
215 | 400 | ValueInfo VI = Edge.first; |
216 | 400 | DEBUG(dbgs() << " edge -> " << VI.getGUID() << " Threshold:" << Threshold |
217 | 400 | << "\n"); |
218 | 400 | |
219 | 400 | VI = updateValueInfoForIndirectCalls(Index, VI); |
220 | 400 | if (!VI) |
221 | 23 | continue; |
222 | 377 | |
223 | 377 | if (377 DefinedGVSummaries.count(VI.getGUID())377 ) { |
224 | 57 | DEBUG(dbgs() << "ignored! Target already in destination module.\n"); |
225 | 57 | continue; |
226 | 57 | } |
227 | 320 | |
228 | 320 | auto GetBonusMultiplier = [](CalleeInfo::HotnessType Hotness) -> float 320 { |
229 | 320 | if (Hotness == CalleeInfo::HotnessType::Hot) |
230 | 44 | return ImportHotMultiplier; |
231 | 276 | if (276 Hotness == CalleeInfo::HotnessType::Cold276 ) |
232 | 20 | return ImportColdMultiplier; |
233 | 256 | if (256 Hotness == CalleeInfo::HotnessType::Critical256 ) |
234 | 0 | return ImportCriticalMultiplier; |
235 | 256 | return 1.0; |
236 | 256 | }; |
237 | 320 | |
238 | 320 | const auto NewThreshold = |
239 | 320 | Threshold * GetBonusMultiplier(Edge.second.Hotness); |
240 | 320 | |
241 | 320 | auto *CalleeSummary = selectCallee(Index, VI.getSummaryList(), NewThreshold, |
242 | 320 | Summary.modulePath()); |
243 | 320 | if (!CalleeSummary320 ) { |
244 | 136 | DEBUG(dbgs() << "ignored! No qualifying callee with summary found.\n"); |
245 | 136 | continue; |
246 | 136 | } |
247 | 184 | |
248 | 184 | // "Resolve" the summary |
249 | 320 | assert(!isa<AliasSummary>(CalleeSummary) && |
250 | 184 | "Unexpected alias in import list"); |
251 | 184 | const auto *ResolvedCalleeSummary = cast<FunctionSummary>(CalleeSummary); |
252 | 184 | |
253 | 184 | assert(ResolvedCalleeSummary->instCount() <= NewThreshold && |
254 | 184 | "selectCallee() didn't honor the threshold"); |
255 | 184 | |
256 | 184 | auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) { |
257 | 184 | // Adjust the threshold for next level of imported functions. |
258 | 184 | // The threshold is different for hot callsites because we can then |
259 | 184 | // inline chains of hot calls. |
260 | 184 | if (IsHotCallsite) |
261 | 31 | return Threshold * ImportHotInstrFactor; |
262 | 153 | return Threshold * ImportInstrFactor; |
263 | 153 | }; |
264 | 184 | |
265 | 184 | bool IsHotCallsite = Edge.second.Hotness == CalleeInfo::HotnessType::Hot; |
266 | 184 | const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite); |
267 | 184 | |
268 | 184 | auto ExportModulePath = ResolvedCalleeSummary->modulePath(); |
269 | 184 | auto &ProcessedThreshold = ImportList[ExportModulePath][VI.getGUID()]; |
270 | 184 | /// Since the traversal of the call graph is DFS, we can revisit a function |
271 | 184 | /// a second time with a higher threshold. In this case, it is added back to |
272 | 184 | /// the worklist with the new threshold. |
273 | 184 | if (ProcessedThreshold && 184 ProcessedThreshold >= AdjThreshold6 ) { |
274 | 5 | DEBUG(dbgs() << "ignored! Target was already seen with Threshold " |
275 | 5 | << ProcessedThreshold << "\n"); |
276 | 5 | continue; |
277 | 5 | } |
278 | 179 | bool PreviouslyImported = ProcessedThreshold != 0; |
279 | 179 | // Mark this function as imported in this module, with the current Threshold |
280 | 179 | ProcessedThreshold = AdjThreshold; |
281 | 179 | |
282 | 179 | // Make exports in the source module. |
283 | 179 | if (ExportLists179 ) { |
284 | 120 | auto &ExportList = (*ExportLists)[ExportModulePath]; |
285 | 120 | ExportList.insert(VI.getGUID()); |
286 | 120 | if (!PreviouslyImported120 ) { |
287 | 120 | // This is the first time this function was exported from its source |
288 | 120 | // module, so mark all functions and globals it references as exported |
289 | 120 | // to the outside if they are defined in the same source module. |
290 | 120 | // For efficiency, we unconditionally add all the referenced GUIDs |
291 | 120 | // to the ExportList for this module, and will prune out any not |
292 | 120 | // defined in the module later in a single pass. |
293 | 31 | for (auto &Edge : ResolvedCalleeSummary->calls()) { |
294 | 31 | auto CalleeGUID = Edge.first.getGUID(); |
295 | 31 | ExportList.insert(CalleeGUID); |
296 | 31 | } |
297 | 35 | for (auto &Ref : ResolvedCalleeSummary->refs()) { |
298 | 35 | auto GUID = Ref.getGUID(); |
299 | 35 | ExportList.insert(GUID); |
300 | 35 | } |
301 | 120 | } |
302 | 120 | } |
303 | 400 | |
304 | 400 | // Insert the newly imported function to the worklist. |
305 | 400 | Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, VI.getGUID()); |
306 | 400 | } |
307 | 798 | } |
308 | | |
309 | | /// Given the list of globals defined in a module, compute the list of imports |
310 | | /// as well as the list of "exports", i.e. the list of symbols referenced from |
311 | | /// another module (that may require promotion). |
312 | | static void ComputeImportForModule( |
313 | | const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index, |
314 | | FunctionImporter::ImportMapTy &ImportList, |
315 | 276 | StringMap<FunctionImporter::ExportSetTy> *ExportLists = nullptr) { |
316 | 276 | // Worklist contains the list of function imported in this module, for which |
317 | 276 | // we will analyse the callees and may import further down the callgraph. |
318 | 276 | SmallVector<EdgeInfo, 128> Worklist; |
319 | 276 | |
320 | 276 | // Populate the worklist with the import for the functions in the current |
321 | 276 | // module |
322 | 777 | for (auto &GVSummary : DefinedGVSummaries) { |
323 | 777 | if (!Index.isGlobalValueLive(GVSummary.second)777 ) { |
324 | 86 | DEBUG(dbgs() << "Ignores Dead GUID: " << GVSummary.first << "\n"); |
325 | 86 | continue; |
326 | 86 | } |
327 | 691 | auto *FuncSummary = |
328 | 691 | dyn_cast<FunctionSummary>(GVSummary.second->getBaseObject()); |
329 | 691 | if (!FuncSummary) |
330 | 691 | // Skip import for global variables |
331 | 72 | continue; |
332 | 619 | DEBUG619 (dbgs() << "Initialize import for " << GVSummary.first << "\n"); |
333 | 619 | computeImportForFunction(*FuncSummary, Index, ImportInstrLimit, |
334 | 619 | DefinedGVSummaries, Worklist, ImportList, |
335 | 619 | ExportLists); |
336 | 619 | } |
337 | 276 | |
338 | 276 | // Process the newly imported functions and add callees to the worklist. |
339 | 455 | while (!Worklist.empty()455 ) { |
340 | 179 | auto FuncInfo = Worklist.pop_back_val(); |
341 | 179 | auto *Summary = std::get<0>(FuncInfo); |
342 | 179 | auto Threshold = std::get<1>(FuncInfo); |
343 | 179 | auto GUID = std::get<2>(FuncInfo); |
344 | 179 | |
345 | 179 | // Check if we later added this summary with a higher threshold. |
346 | 179 | // If so, skip this entry. |
347 | 179 | auto ExportModulePath = Summary->modulePath(); |
348 | 179 | auto &LatestProcessedThreshold = ImportList[ExportModulePath][GUID]; |
349 | 179 | if (LatestProcessedThreshold > Threshold) |
350 | 0 | continue; |
351 | 179 | |
352 | 179 | computeImportForFunction(*Summary, Index, Threshold, DefinedGVSummaries, |
353 | 179 | Worklist, ImportList, ExportLists); |
354 | 179 | } |
355 | 276 | } |
356 | | |
357 | | } // anonymous namespace |
358 | | |
359 | | /// Compute all the import and export for every module using the Index. |
360 | | void llvm::ComputeCrossModuleImport( |
361 | | const ModuleSummaryIndex &Index, |
362 | | const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries, |
363 | | StringMap<FunctionImporter::ImportMapTy> &ImportLists, |
364 | 142 | StringMap<FunctionImporter::ExportSetTy> &ExportLists) { |
365 | 142 | // For each module that has function defined, compute the import/export lists. |
366 | 255 | for (auto &DefinedGVSummaries : ModuleToDefinedGVSummaries) { |
367 | 255 | auto &ImportList = ImportLists[DefinedGVSummaries.first()]; |
368 | 255 | DEBUG(dbgs() << "Computing import for Module '" |
369 | 255 | << DefinedGVSummaries.first() << "'\n"); |
370 | 255 | ComputeImportForModule(DefinedGVSummaries.second, Index, ImportList, |
371 | 255 | &ExportLists); |
372 | 255 | } |
373 | 142 | |
374 | 142 | // When computing imports we added all GUIDs referenced by anything |
375 | 142 | // imported from the module to its ExportList. Now we prune each ExportList |
376 | 142 | // of any not defined in that module. This is more efficient than checking |
377 | 142 | // while computing imports because some of the summary lists may be long |
378 | 142 | // due to linkonce (comdat) copies. |
379 | 84 | for (auto &ELI : ExportLists) { |
380 | 84 | const auto &DefinedGVSummaries = |
381 | 84 | ModuleToDefinedGVSummaries.lookup(ELI.first()); |
382 | 254 | for (auto EI = ELI.second.begin(); EI != ELI.second.end()254 ;) { |
383 | 170 | if (!DefinedGVSummaries.count(*EI)) |
384 | 12 | EI = ELI.second.erase(EI); |
385 | 170 | else |
386 | 158 | ++EI; |
387 | 170 | } |
388 | 84 | } |
389 | 142 | |
390 | | #ifndef NDEBUG |
391 | | DEBUG(dbgs() << "Import/Export lists for " << ImportLists.size() |
392 | | << " modules:\n"); |
393 | | for (auto &ModuleImports : ImportLists) { |
394 | | auto ModName = ModuleImports.first(); |
395 | | auto &Exports = ExportLists[ModName]; |
396 | | DEBUG(dbgs() << "* Module " << ModName << " exports " << Exports.size() |
397 | | << " functions. Imports from " << ModuleImports.second.size() |
398 | | << " modules.\n"); |
399 | | for (auto &Src : ModuleImports.second) { |
400 | | auto SrcModName = Src.first(); |
401 | | DEBUG(dbgs() << " - " << Src.second.size() << " functions imported from " |
402 | | << SrcModName << "\n"); |
403 | | } |
404 | | } |
405 | | #endif |
406 | | } |
407 | | |
408 | | /// Compute all the imports for the given module in the Index. |
409 | | void llvm::ComputeCrossModuleImportForModule( |
410 | | StringRef ModulePath, const ModuleSummaryIndex &Index, |
411 | 21 | FunctionImporter::ImportMapTy &ImportList) { |
412 | 21 | |
413 | 21 | // Collect the list of functions this module defines. |
414 | 21 | // GUID -> Summary |
415 | 21 | GVSummaryMapTy FunctionSummaryMap; |
416 | 21 | Index.collectDefinedFunctionsForModule(ModulePath, FunctionSummaryMap); |
417 | 21 | |
418 | 21 | // Compute the import list for this module. |
419 | 21 | DEBUG(dbgs() << "Computing import for Module '" << ModulePath << "'\n"); |
420 | 21 | ComputeImportForModule(FunctionSummaryMap, Index, ImportList); |
421 | 21 | |
422 | | #ifndef NDEBUG |
423 | | DEBUG(dbgs() << "* Module " << ModulePath << " imports from " |
424 | | << ImportList.size() << " modules.\n"); |
425 | | for (auto &Src : ImportList) { |
426 | | auto SrcModName = Src.first(); |
427 | | DEBUG(dbgs() << " - " << Src.second.size() << " functions imported from " |
428 | | << SrcModName << "\n"); |
429 | | } |
430 | | #endif |
431 | | } |
432 | | |
433 | | void llvm::computeDeadSymbols( |
434 | | ModuleSummaryIndex &Index, |
435 | 304 | const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) { |
436 | 304 | assert(!Index.withGlobalValueDeadStripping()); |
437 | 304 | if (!ComputeDead) |
438 | 0 | return; |
439 | 304 | if (304 GUIDPreservedSymbols.empty()304 ) |
440 | 304 | // Don't do anything when nothing is live, this is friendly with tests. |
441 | 44 | return; |
442 | 260 | unsigned LiveSymbols = 0; |
443 | 260 | SmallVector<ValueInfo, 128> Worklist; |
444 | 260 | Worklist.reserve(GUIDPreservedSymbols.size() * 2); |
445 | 462 | for (auto GUID : GUIDPreservedSymbols) { |
446 | 462 | ValueInfo VI = Index.getValueInfo(GUID); |
447 | 462 | if (!VI) |
448 | 290 | continue; |
449 | 172 | for (auto &S : VI.getSummaryList()) |
450 | 173 | S->setLive(true); |
451 | 462 | } |
452 | 260 | |
453 | 260 | // Add values flagged in the index as live roots to the worklist. |
454 | 260 | for (const auto &Entry : Index) |
455 | 380 | for (auto &S : Entry.second.SummaryList) |
456 | 363 | if (363 S->isLive()363 ) { |
457 | 181 | DEBUG(dbgs() << "Live root: " << Entry.first << "\n"); |
458 | 380 | Worklist.push_back(ValueInfo(&Entry)); |
459 | 380 | ++LiveSymbols; |
460 | 380 | break; |
461 | 380 | } |
462 | 260 | |
463 | 260 | // Make value live and add it to the worklist if it was not live before. |
464 | 260 | // FIXME: we should only make the prevailing copy live here |
465 | 172 | auto visit = [&](ValueInfo VI) { |
466 | 172 | // FIXME: If we knew which edges were created for indirect call profiles, |
467 | 172 | // we could skip them here. Any that are live should be reached via |
468 | 172 | // other edges, e.g. reference edges. Otherwise, using a profile collected |
469 | 172 | // on a slightly different binary might provoke preserving, importing |
470 | 172 | // and ultimately promoting calls to functions not linked into this |
471 | 172 | // binary, which increases the binary size unnecessarily. Note that |
472 | 172 | // if this code changes, the importer needs to change so that edges |
473 | 172 | // to functions marked dead are skipped. |
474 | 172 | VI = updateValueInfoForIndirectCalls(Index, VI); |
475 | 172 | if (!VI) |
476 | 16 | return; |
477 | 156 | for (auto &S : VI.getSummaryList()) |
478 | 156 | if (156 S->isLive()156 ) |
479 | 60 | return; |
480 | 96 | for (auto &S : VI.getSummaryList()) |
481 | 96 | S->setLive(true); |
482 | 172 | ++LiveSymbols; |
483 | 172 | Worklist.push_back(VI); |
484 | 172 | }; |
485 | 260 | |
486 | 537 | while (!Worklist.empty()537 ) { |
487 | 277 | auto VI = Worklist.pop_back_val(); |
488 | 282 | for (auto &Summary : VI.getSummaryList()) { |
489 | 282 | GlobalValueSummary *Base = Summary->getBaseObject(); |
490 | 282 | for (auto Ref : Base->refs()) |
491 | 39 | visit(Ref); |
492 | 282 | if (auto *FS = dyn_cast<FunctionSummary>(Base)) |
493 | 249 | for (auto Call : FS->calls()) |
494 | 133 | visit(Call.first); |
495 | 282 | } |
496 | 277 | } |
497 | 260 | Index.setWithGlobalValueDeadStripping(); |
498 | 260 | |
499 | 260 | unsigned DeadSymbols = Index.size() - LiveSymbols; |
500 | 260 | DEBUG(dbgs() << LiveSymbols << " symbols Live, and " << DeadSymbols |
501 | 304 | << " symbols Dead \n"); |
502 | 304 | NumDeadSymbols += DeadSymbols; |
503 | 304 | NumLiveSymbols += LiveSymbols; |
504 | 304 | } |
505 | | |
506 | | /// Compute the set of summaries needed for a ThinLTO backend compilation of |
507 | | /// \p ModulePath. |
508 | | void llvm::gatherImportedSummariesForModule( |
509 | | StringRef ModulePath, |
510 | | const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries, |
511 | | const FunctionImporter::ImportMapTy &ImportList, |
512 | 11 | std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) { |
513 | 11 | // Include all summaries from the importing module. |
514 | 11 | ModuleToSummariesForIndex[ModulePath] = |
515 | 11 | ModuleToDefinedGVSummaries.lookup(ModulePath); |
516 | 11 | // Include summaries for imports. |
517 | 4 | for (auto &ILI : ImportList) { |
518 | 4 | auto &SummariesForIndex = ModuleToSummariesForIndex[ILI.first()]; |
519 | 4 | const auto &DefinedGVSummaries = |
520 | 4 | ModuleToDefinedGVSummaries.lookup(ILI.first()); |
521 | 4 | for (auto &GI : ILI.second) { |
522 | 4 | const auto &DS = DefinedGVSummaries.find(GI.first); |
523 | 4 | assert(DS != DefinedGVSummaries.end() && |
524 | 4 | "Expected a defined summary for imported global value"); |
525 | 4 | SummariesForIndex[GI.first] = DS->second; |
526 | 4 | } |
527 | 4 | } |
528 | 11 | } |
529 | | |
530 | | /// Emit the files \p ModulePath will import from into \p OutputFilename. |
531 | | std::error_code |
532 | | llvm::EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename, |
533 | 11 | const FunctionImporter::ImportMapTy &ModuleImports) { |
534 | 11 | std::error_code EC; |
535 | 11 | raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::F_None); |
536 | 11 | if (EC) |
537 | 0 | return EC; |
538 | 11 | for (auto &ILI : ModuleImports) |
539 | 4 | ImportsOS << ILI.first() << "\n"; |
540 | 11 | return std::error_code(); |
541 | 11 | } |
542 | | |
543 | | /// Fixup WeakForLinker linkages in \p TheModule based on summary analysis. |
544 | | void llvm::thinLTOResolveWeakForLinkerModule( |
545 | 175 | Module &TheModule, const GVSummaryMapTy &DefinedGlobals) { |
546 | 2 | auto ConvertToDeclaration = [](GlobalValue &GV) { |
547 | 2 | DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName() << "\n"); |
548 | 2 | if (Function *F2 = dyn_cast<Function>(&GV)) { |
549 | 2 | F->deleteBody(); |
550 | 2 | F->clearMetadata(); |
551 | 2 | } else if (GlobalVariable *0 V0 = dyn_cast<GlobalVariable>(&GV)) { |
552 | 0 | V->setInitializer(nullptr); |
553 | 0 | V->setLinkage(GlobalValue::ExternalLinkage); |
554 | 0 | V->clearMetadata(); |
555 | 0 | } else |
556 | 0 | // For now we don't resolve or drop aliases. Once we do we'll |
557 | 0 | // need to add support here for creating either a function or |
558 | 0 | // variable declaration, and return the new GlobalValue* for |
559 | 0 | // the caller to use. |
560 | 0 | llvm_unreachable("Expected function or variable"); |
561 | 2 | }; |
562 | 175 | |
563 | 591 | auto updateLinkage = [&](GlobalValue &GV) { |
564 | 591 | // See if the global summary analysis computed a new resolved linkage. |
565 | 591 | const auto &GS = DefinedGlobals.find(GV.getGUID()); |
566 | 591 | if (GS == DefinedGlobals.end()) |
567 | 140 | return; |
568 | 451 | auto NewLinkage = GS->second->linkage(); |
569 | 451 | if (NewLinkage == GV.getLinkage()) |
570 | 333 | return; |
571 | 118 | |
572 | 118 | // Switch the linkage to weakany if asked for, e.g. we do this for |
573 | 118 | // linker redefined symbols (via --wrap or --defsym). |
574 | 118 | // We record that the visibility should be changed here in `addThinLTO` |
575 | 118 | // as we need access to the resolution vectors for each input file in |
576 | 118 | // order to find which symbols have been redefined. |
577 | 118 | // We may consider reorganizing this code and moving the linkage recording |
578 | 118 | // somewhere else, e.g. in thinLTOResolveWeakForLinkerInIndex. |
579 | 118 | if (118 NewLinkage == GlobalValue::WeakAnyLinkage118 ) { |
580 | 29 | GV.setLinkage(NewLinkage); |
581 | 29 | return; |
582 | 29 | } |
583 | 89 | |
584 | 89 | if (89 !GlobalValue::isWeakForLinker(GV.getLinkage())89 ) |
585 | 41 | return; |
586 | 48 | // Check for a non-prevailing def that has interposable linkage |
587 | 48 | // (e.g. non-odr weak or linkonce). In that case we can't simply |
588 | 48 | // convert to available_externally, since it would lose the |
589 | 48 | // interposable property and possibly get inlined. Simply drop |
590 | 48 | // the definition in that case. |
591 | 48 | if (48 GlobalValue::isAvailableExternallyLinkage(NewLinkage) && |
592 | 7 | GlobalValue::isInterposableLinkage(GV.getLinkage())) |
593 | 2 | ConvertToDeclaration(GV); |
594 | 46 | else { |
595 | 46 | DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName() << "` from " |
596 | 46 | << GV.getLinkage() << " to " << NewLinkage << "\n"); |
597 | 46 | GV.setLinkage(NewLinkage); |
598 | 46 | } |
599 | 48 | // Remove declarations from comdats, including available_externally |
600 | 48 | // as this is a declaration for the linker, and will be dropped eventually. |
601 | 48 | // It is illegal for comdats to contain declarations. |
602 | 48 | auto *GO = dyn_cast_or_null<GlobalObject>(&GV); |
603 | 48 | if (GO && 48 GO->isDeclarationForLinker()33 && GO->hasComdat()7 ) |
604 | 1 | GO->setComdat(nullptr); |
605 | 591 | }; |
606 | 175 | |
607 | 175 | // Process functions and global now |
608 | 175 | for (auto &GV : TheModule) |
609 | 445 | updateLinkage(GV); |
610 | 175 | for (auto &GV : TheModule.globals()) |
611 | 52 | updateLinkage(GV); |
612 | 175 | for (auto &GV : TheModule.aliases()) |
613 | 98 | updateLinkage(GV); |
614 | 175 | } |
615 | | |
616 | | /// Run internalization on \p TheModule based on symmary analysis. |
617 | | void llvm::thinLTOInternalizeModule(Module &TheModule, |
618 | 164 | const GVSummaryMapTy &DefinedGlobals) { |
619 | 164 | // Parse inline ASM and collect the list of symbols that are not defined in |
620 | 164 | // the current module. |
621 | 164 | StringSet<> AsmUndefinedRefs; |
622 | 164 | ModuleSymbolTable::CollectAsmSymbols( |
623 | 164 | TheModule, |
624 | 20 | [&AsmUndefinedRefs](StringRef Name, object::BasicSymbolRef::Flags Flags) { |
625 | 20 | if (Flags & object::BasicSymbolRef::SF_Undefined) |
626 | 4 | AsmUndefinedRefs.insert(Name); |
627 | 20 | }); |
628 | 164 | |
629 | 164 | // Declare a callback for the internalize pass that will ask for every |
630 | 164 | // candidate GlobalValue if it can be internalized or not. |
631 | 260 | auto MustPreserveGV = [&](const GlobalValue &GV) -> bool { |
632 | 260 | // Can't be internalized if referenced in inline asm. |
633 | 260 | if (AsmUndefinedRefs.count(GV.getName())) |
634 | 0 | return true; |
635 | 260 | |
636 | 260 | // Lookup the linkage recorded in the summaries during global analysis. |
637 | 260 | auto GS = DefinedGlobals.find(GV.getGUID()); |
638 | 260 | if (GS == DefinedGlobals.end()260 ) { |
639 | 7 | // Must have been promoted (possibly conservatively). Find original |
640 | 7 | // name so that we can access the correct summary and see if it can |
641 | 7 | // be internalized again. |
642 | 7 | // FIXME: Eventually we should control promotion instead of promoting |
643 | 7 | // and internalizing again. |
644 | 7 | StringRef OrigName = |
645 | 7 | ModuleSummaryIndex::getOriginalNameBeforePromote(GV.getName()); |
646 | 7 | std::string OrigId = GlobalValue::getGlobalIdentifier( |
647 | 7 | OrigName, GlobalValue::InternalLinkage, |
648 | 7 | TheModule.getSourceFileName()); |
649 | 7 | GS = DefinedGlobals.find(GlobalValue::getGUID(OrigId)); |
650 | 7 | if (GS == DefinedGlobals.end()7 ) { |
651 | 0 | // Also check the original non-promoted non-globalized name. In some |
652 | 0 | // cases a preempted weak value is linked in as a local copy because |
653 | 0 | // it is referenced by an alias (IRLinker::linkGlobalValueProto). |
654 | 0 | // In that case, since it was originally not a local value, it was |
655 | 0 | // recorded in the index using the original name. |
656 | 0 | // FIXME: This may not be needed once PR27866 is fixed. |
657 | 0 | GS = DefinedGlobals.find(GlobalValue::getGUID(OrigName)); |
658 | 0 | assert(GS != DefinedGlobals.end()); |
659 | 0 | } |
660 | 7 | } |
661 | 260 | return !GlobalValue::isLocalLinkage(GS->second->linkage()); |
662 | 260 | }; |
663 | 164 | |
664 | 164 | // FIXME: See if we can just internalize directly here via linkage changes |
665 | 164 | // based on the index, rather than invoking internalizeModule. |
666 | 164 | llvm::internalizeModule(TheModule, MustPreserveGV); |
667 | 164 | } |
668 | | |
669 | | // Automatically import functions in Module \p DestModule based on the summaries |
670 | | // index. |
671 | | // |
672 | | Expected<bool> FunctionImporter::importFunctions( |
673 | 215 | Module &DestModule, const FunctionImporter::ImportMapTy &ImportList) { |
674 | 215 | DEBUG(dbgs() << "Starting import for Module " |
675 | 215 | << DestModule.getModuleIdentifier() << "\n"); |
676 | 215 | unsigned ImportedCount = 0; |
677 | 215 | |
678 | 215 | IRMover Mover(DestModule); |
679 | 215 | // Do the actual import of functions now, one Module at a time |
680 | 215 | std::set<StringRef> ModuleNameOrderedList; |
681 | 99 | for (auto &FunctionsToImportPerModule : ImportList) { |
682 | 99 | ModuleNameOrderedList.insert(FunctionsToImportPerModule.first()); |
683 | 99 | } |
684 | 99 | for (auto &Name : ModuleNameOrderedList) { |
685 | 99 | // Get the module for the import |
686 | 99 | const auto &FunctionsToImportPerModule = ImportList.find(Name); |
687 | 99 | assert(FunctionsToImportPerModule != ImportList.end()); |
688 | 99 | Expected<std::unique_ptr<Module>> SrcModuleOrErr = ModuleLoader(Name); |
689 | 99 | if (!SrcModuleOrErr) |
690 | 0 | return SrcModuleOrErr.takeError(); |
691 | 99 | std::unique_ptr<Module> SrcModule = std::move(*SrcModuleOrErr); |
692 | 99 | assert(&DestModule.getContext() == &SrcModule->getContext() && |
693 | 99 | "Context mismatch"); |
694 | 99 | |
695 | 99 | // If modules were created with lazy metadata loading, materialize it |
696 | 99 | // now, before linking it (otherwise this will be a noop). |
697 | 99 | if (Error Err = SrcModule->materializeMetadata()) |
698 | 0 | return std::move(Err); |
699 | 99 | |
700 | 99 | auto &ImportGUIDs = FunctionsToImportPerModule->second; |
701 | 99 | // Find the globals to import |
702 | 99 | SetVector<GlobalValue *> GlobalsToImport; |
703 | 433 | for (Function &F : *SrcModule) { |
704 | 433 | if (!F.hasName()) |
705 | 0 | continue; |
706 | 433 | auto GUID = F.getGUID(); |
707 | 433 | auto Import = ImportGUIDs.count(GUID); |
708 | 433 | DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing function " << GUID |
709 | 433 | << " " << F.getName() << " from " |
710 | 433 | << SrcModule->getSourceFileName() << "\n"); |
711 | 433 | if (Import433 ) { |
712 | 167 | if (Error Err = F.materialize()) |
713 | 0 | return std::move(Err); |
714 | 167 | if (167 EnableImportMetadata167 ) { |
715 | 0 | // Add 'thinlto_src_module' metadata for statistics and debugging. |
716 | 0 | F.setMetadata( |
717 | 0 | "thinlto_src_module", |
718 | 0 | llvm::MDNode::get( |
719 | 0 | DestModule.getContext(), |
720 | 0 | {llvm::MDString::get(DestModule.getContext(), |
721 | 0 | SrcModule->getSourceFileName())})); |
722 | 0 | } |
723 | 167 | GlobalsToImport.insert(&F); |
724 | 167 | } |
725 | 433 | } |
726 | 99 | for (GlobalVariable &GV : SrcModule->globals()) 99 { |
727 | 100 | if (!GV.hasName()) |
728 | 0 | continue; |
729 | 100 | auto GUID = GV.getGUID(); |
730 | 100 | auto Import = ImportGUIDs.count(GUID); |
731 | 100 | DEBUG(dbgs() << (Import ? "Is" : "Not") << " importing global " << GUID |
732 | 100 | << " " << GV.getName() << " from " |
733 | 100 | << SrcModule->getSourceFileName() << "\n"); |
734 | 100 | if (Import100 ) { |
735 | 0 | if (Error Err = GV.materialize()) |
736 | 0 | return std::move(Err); |
737 | 0 | GlobalsToImport.insert(&GV); |
738 | 0 | } |
739 | 100 | } |
740 | | #ifndef NDEBUG |
741 | | for (GlobalAlias &GA : SrcModule->aliases()) { |
742 | | if (!GA.hasName()) |
743 | | continue; |
744 | | auto GUID = GA.getGUID(); |
745 | | assert(!ImportGUIDs.count(GUID) && "Unexpected alias in import list"); |
746 | | DEBUG(dbgs() << "Not importing alias " << GUID |
747 | | << " " << GA.getName() << " from " |
748 | | << SrcModule->getSourceFileName() << "\n"); |
749 | | } |
750 | | #endif |
751 | | |
752 | 99 | // Upgrade debug info after we're done materializing all the globals and we |
753 | 99 | // have loaded all the required metadata! |
754 | 99 | UpgradeDebugInfo(*SrcModule); |
755 | 99 | |
756 | 99 | // Link in the specified functions. |
757 | 99 | if (renameModuleForThinLTO(*SrcModule, Index, &GlobalsToImport)) |
758 | 0 | return true; |
759 | 99 | |
760 | 99 | if (99 PrintImports99 ) { |
761 | 4 | for (const auto *GV : GlobalsToImport) |
762 | 5 | dbgs() << DestModule.getSourceFileName() << ": Import " << GV->getName() |
763 | 5 | << " from " << SrcModule->getSourceFileName() << "\n"; |
764 | 4 | } |
765 | 99 | |
766 | 99 | if (Mover.move(std::move(SrcModule), GlobalsToImport.getArrayRef(), |
767 | 72 | [](GlobalValue &, IRMover::ValueAdder) {}, |
768 | 99 | /*IsPerformingImport=*/true)) |
769 | 0 | report_fatal_error("Function Import: link error"); |
770 | 99 | |
771 | 99 | ImportedCount += GlobalsToImport.size(); |
772 | 99 | NumImportedModules++; |
773 | 99 | } |
774 | 215 | |
775 | 215 | NumImportedFunctions += ImportedCount; |
776 | 215 | |
777 | 215 | DEBUG(dbgs() << "Imported " << ImportedCount << " functions for Module " |
778 | 215 | << DestModule.getModuleIdentifier() << "\n"); |
779 | 215 | return ImportedCount; |
780 | 215 | } |
781 | | |
782 | | /// Summary file to use for function importing when using -function-import from |
783 | | /// the command line. |
784 | | static cl::opt<std::string> |
785 | | SummaryFile("summary-file", |
786 | | cl::desc("The summary file to use for function importing.")); |
787 | | |
788 | 21 | static bool doImportingForModule(Module &M) { |
789 | 21 | if (SummaryFile.empty()) |
790 | 0 | report_fatal_error("error: -function-import requires -summary-file\n"); |
791 | 21 | Expected<std::unique_ptr<ModuleSummaryIndex>> IndexPtrOrErr = |
792 | 21 | getModuleSummaryIndexForFile(SummaryFile); |
793 | 21 | if (!IndexPtrOrErr21 ) { |
794 | 0 | logAllUnhandledErrors(IndexPtrOrErr.takeError(), errs(), |
795 | 0 | "Error loading file '" + SummaryFile + "': "); |
796 | 0 | return false; |
797 | 0 | } |
798 | 21 | std::unique_ptr<ModuleSummaryIndex> Index = std::move(*IndexPtrOrErr); |
799 | 21 | |
800 | 21 | // First step is collecting the import list. |
801 | 21 | FunctionImporter::ImportMapTy ImportList; |
802 | 21 | ComputeCrossModuleImportForModule(M.getModuleIdentifier(), *Index, |
803 | 21 | ImportList); |
804 | 21 | |
805 | 21 | // Conservatively mark all internal values as promoted. This interface is |
806 | 21 | // only used when doing importing via the function importing pass. The pass |
807 | 21 | // is only enabled when testing importing via the 'opt' tool, which does |
808 | 21 | // not do the ThinLink that would normally determine what values to promote. |
809 | 158 | for (auto &I : *Index) { |
810 | 158 | for (auto &S : I.second.SummaryList) { |
811 | 158 | if (GlobalValue::isLocalLinkage(S->linkage())) |
812 | 5 | S->setLinkage(GlobalValue::ExternalLinkage); |
813 | 158 | } |
814 | 158 | } |
815 | 21 | |
816 | 21 | // Next we need to promote to global scope and rename any local values that |
817 | 21 | // are potentially exported to other modules. |
818 | 21 | if (renameModuleForThinLTO(M, *Index, nullptr)21 ) { |
819 | 0 | errs() << "Error renaming module\n"; |
820 | 0 | return false; |
821 | 0 | } |
822 | 21 | |
823 | 21 | // Perform the import now. |
824 | 21 | auto ModuleLoader = [&M](StringRef Identifier) 21 { |
825 | 18 | return loadFile(Identifier, M.getContext()); |
826 | 18 | }; |
827 | 21 | FunctionImporter Importer(*Index, ModuleLoader); |
828 | 21 | Expected<bool> Result = Importer.importFunctions(M, ImportList); |
829 | 21 | |
830 | 21 | // FIXME: Probably need to propagate Errors through the pass manager. |
831 | 21 | if (!Result21 ) { |
832 | 0 | logAllUnhandledErrors(Result.takeError(), errs(), |
833 | 0 | "Error importing module: "); |
834 | 0 | return false; |
835 | 0 | } |
836 | 21 | |
837 | 21 | return *Result; |
838 | 21 | } |
839 | | |
840 | | namespace { |
841 | | /// Pass that performs cross-module function import provided a summary file. |
842 | | class FunctionImportLegacyPass : public ModulePass { |
843 | | public: |
844 | | /// Pass identification, replacement for typeid |
845 | | static char ID; |
846 | | |
847 | | /// Specify pass name for debug output |
848 | 0 | StringRef getPassName() const override { return "Function Importing"; } |
849 | | |
850 | 21 | explicit FunctionImportLegacyPass() : ModulePass(ID) {} |
851 | | |
852 | 21 | bool runOnModule(Module &M) override { |
853 | 21 | if (skipModule(M)) |
854 | 0 | return false; |
855 | 21 | |
856 | 21 | return doImportingForModule(M); |
857 | 21 | } |
858 | | }; |
859 | | } // anonymous namespace |
860 | | |
861 | | PreservedAnalyses FunctionImportPass::run(Module &M, |
862 | 0 | ModuleAnalysisManager &AM) { |
863 | 0 | if (!doImportingForModule(M)) |
864 | 0 | return PreservedAnalyses::all(); |
865 | 0 |
|
866 | 0 | return PreservedAnalyses::none(); |
867 | 0 | } |
868 | | |
869 | | char FunctionImportLegacyPass::ID = 0; |
870 | | INITIALIZE_PASS(FunctionImportLegacyPass, "function-import", |
871 | | "Summary Based Function Import", false, false) |
872 | | |
873 | | namespace llvm { |
874 | 0 | Pass *createFunctionImportPass() { |
875 | 0 | return new FunctionImportLegacyPass(); |
876 | 0 | } |
877 | | } |