1 | //===- Inliner.cpp - Code common to all inliners --------------------------===// |
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 | // This file implements the mechanics required to implement inlining without |
10 | // missing any calls and updating the call graph. The decisions of which calls |
11 | // are profitable to inline are implemented elsewhere. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #include "llvm/Transforms/IPO/Inliner.h" |
16 | #include "llvm/ADT/PriorityWorklist.h" |
17 | #include "llvm/ADT/STLExtras.h" |
18 | #include "llvm/ADT/ScopeExit.h" |
19 | #include "llvm/ADT/SetVector.h" |
20 | #include "llvm/ADT/SmallPtrSet.h" |
21 | #include "llvm/ADT/SmallVector.h" |
22 | #include "llvm/ADT/Statistic.h" |
23 | #include "llvm/ADT/StringExtras.h" |
24 | #include "llvm/ADT/StringRef.h" |
25 | #include "llvm/Analysis/AssumptionCache.h" |
26 | #include "llvm/Analysis/BasicAliasAnalysis.h" |
27 | #include "llvm/Analysis/BlockFrequencyInfo.h" |
28 | #include "llvm/Analysis/CGSCCPassManager.h" |
29 | #include "llvm/Analysis/InlineAdvisor.h" |
30 | #include "llvm/Analysis/InlineCost.h" |
31 | #include "llvm/Analysis/LazyCallGraph.h" |
32 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" |
33 | #include "llvm/Analysis/ProfileSummaryInfo.h" |
34 | #include "llvm/Analysis/ReplayInlineAdvisor.h" |
35 | #include "llvm/Analysis/TargetLibraryInfo.h" |
36 | #include "llvm/Analysis/Utils/ImportedFunctionsInliningStatistics.h" |
37 | #include "llvm/IR/Attributes.h" |
38 | #include "llvm/IR/BasicBlock.h" |
39 | #include "llvm/IR/DebugLoc.h" |
40 | #include "llvm/IR/DerivedTypes.h" |
41 | #include "llvm/IR/DiagnosticInfo.h" |
42 | #include "llvm/IR/Function.h" |
43 | #include "llvm/IR/InstIterator.h" |
44 | #include "llvm/IR/Instruction.h" |
45 | #include "llvm/IR/Instructions.h" |
46 | #include "llvm/IR/IntrinsicInst.h" |
47 | #include "llvm/IR/Metadata.h" |
48 | #include "llvm/IR/Module.h" |
49 | #include "llvm/IR/PassManager.h" |
50 | #include "llvm/IR/User.h" |
51 | #include "llvm/IR/Value.h" |
52 | #include "llvm/Pass.h" |
53 | #include "llvm/Support/Casting.h" |
54 | #include "llvm/Support/CommandLine.h" |
55 | #include "llvm/Support/Debug.h" |
56 | #include "llvm/Support/raw_ostream.h" |
57 | #include "llvm/Transforms/Utils/CallPromotionUtils.h" |
58 | #include "llvm/Transforms/Utils/Cloning.h" |
59 | #include "llvm/Transforms/Utils/Local.h" |
60 | #include "llvm/Transforms/Utils/ModuleUtils.h" |
61 | #include <algorithm> |
62 | #include <cassert> |
63 | #include <functional> |
64 | #include <utility> |
65 | |
66 | using namespace llvm; |
67 | |
68 | #define DEBUG_TYPE "inline" |
69 | |
70 | STATISTIC(NumInlined, "Number of functions inlined" ); |
71 | STATISTIC(NumDeleted, "Number of functions deleted because all callers found" ); |
72 | |
73 | static cl::opt<int> IntraSCCCostMultiplier( |
74 | "intra-scc-cost-multiplier" , cl::init(Val: 2), cl::Hidden, |
75 | cl::desc( |
76 | "Cost multiplier to multiply onto inlined call sites where the " |
77 | "new call was previously an intra-SCC call (not relevant when the " |
78 | "original call was already intra-SCC). This can accumulate over " |
79 | "multiple inlinings (e.g. if a call site already had a cost " |
80 | "multiplier and one of its inlined calls was also subject to " |
81 | "this, the inlined call would have the original multiplier " |
82 | "multiplied by intra-scc-cost-multiplier). This is to prevent tons of " |
83 | "inlining through a child SCC which can cause terrible compile times" )); |
84 | |
85 | /// A flag for test, so we can print the content of the advisor when running it |
86 | /// as part of the default (e.g. -O3) pipeline. |
87 | static cl::opt<bool> KeepAdvisorForPrinting("keep-inline-advisor-for-printing" , |
88 | cl::init(Val: false), cl::Hidden); |
89 | |
90 | /// Allows printing the contents of the advisor after each SCC inliner pass. |
91 | static cl::opt<bool> |
92 | EnablePostSCCAdvisorPrinting("enable-scc-inline-advisor-printing" , |
93 | cl::init(Val: false), cl::Hidden); |
94 | |
95 | |
96 | static cl::opt<std::string> CGSCCInlineReplayFile( |
97 | "cgscc-inline-replay" , cl::init(Val: "" ), cl::value_desc("filename" ), |
98 | cl::desc( |
99 | "Optimization remarks file containing inline remarks to be replayed " |
100 | "by cgscc inlining." ), |
101 | cl::Hidden); |
102 | |
103 | static cl::opt<ReplayInlinerSettings::Scope> CGSCCInlineReplayScope( |
104 | "cgscc-inline-replay-scope" , |
105 | cl::init(Val: ReplayInlinerSettings::Scope::Function), |
106 | cl::values(clEnumValN(ReplayInlinerSettings::Scope::Function, "Function" , |
107 | "Replay on functions that have remarks associated " |
108 | "with them (default)" ), |
109 | clEnumValN(ReplayInlinerSettings::Scope::Module, "Module" , |
110 | "Replay on the entire module" )), |
111 | cl::desc("Whether inline replay should be applied to the entire " |
112 | "Module or just the Functions (default) that are present as " |
113 | "callers in remarks during cgscc inlining." ), |
114 | cl::Hidden); |
115 | |
116 | static cl::opt<ReplayInlinerSettings::Fallback> CGSCCInlineReplayFallback( |
117 | "cgscc-inline-replay-fallback" , |
118 | cl::init(Val: ReplayInlinerSettings::Fallback::Original), |
119 | cl::values( |
120 | clEnumValN( |
121 | ReplayInlinerSettings::Fallback::Original, "Original" , |
122 | "All decisions not in replay send to original advisor (default)" ), |
123 | clEnumValN(ReplayInlinerSettings::Fallback::AlwaysInline, |
124 | "AlwaysInline" , "All decisions not in replay are inlined" ), |
125 | clEnumValN(ReplayInlinerSettings::Fallback::NeverInline, "NeverInline" , |
126 | "All decisions not in replay are not inlined" )), |
127 | cl::desc( |
128 | "How cgscc inline replay treats sites that don't come from the replay. " |
129 | "Original: defers to original advisor, AlwaysInline: inline all sites " |
130 | "not in replay, NeverInline: inline no sites not in replay" ), |
131 | cl::Hidden); |
132 | |
133 | static cl::opt<CallSiteFormat::Format> CGSCCInlineReplayFormat( |
134 | "cgscc-inline-replay-format" , |
135 | cl::init(Val: CallSiteFormat::Format::LineColumnDiscriminator), |
136 | cl::values( |
137 | clEnumValN(CallSiteFormat::Format::Line, "Line" , "<Line Number>" ), |
138 | clEnumValN(CallSiteFormat::Format::LineColumn, "LineColumn" , |
139 | "<Line Number>:<Column Number>" ), |
140 | clEnumValN(CallSiteFormat::Format::LineDiscriminator, |
141 | "LineDiscriminator" , "<Line Number>.<Discriminator>" ), |
142 | clEnumValN(CallSiteFormat::Format::LineColumnDiscriminator, |
143 | "LineColumnDiscriminator" , |
144 | "<Line Number>:<Column Number>.<Discriminator> (default)" )), |
145 | cl::desc("How cgscc inline replay file is formatted" ), cl::Hidden); |
146 | |
147 | /// Return true if the specified inline history ID |
148 | /// indicates an inline history that includes the specified function. |
149 | static bool inlineHistoryIncludes( |
150 | Function *F, int InlineHistoryID, |
151 | const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) { |
152 | while (InlineHistoryID != -1) { |
153 | assert(unsigned(InlineHistoryID) < InlineHistory.size() && |
154 | "Invalid inline history ID" ); |
155 | if (InlineHistory[InlineHistoryID].first == F) |
156 | return true; |
157 | InlineHistoryID = InlineHistory[InlineHistoryID].second; |
158 | } |
159 | return false; |
160 | } |
161 | |
162 | InlineAdvisor & |
163 | InlinerPass::getAdvisor(const ModuleAnalysisManagerCGSCCProxy::Result &MAM, |
164 | FunctionAnalysisManager &FAM, Module &M) { |
165 | if (OwnedAdvisor) |
166 | return *OwnedAdvisor; |
167 | |
168 | auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(IR&: M); |
169 | if (!IAA) { |
170 | // It should still be possible to run the inliner as a stand-alone SCC pass, |
171 | // for test scenarios. In that case, we default to the |
172 | // DefaultInlineAdvisor, which doesn't need to keep state between SCC pass |
173 | // runs. It also uses just the default InlineParams. |
174 | // In this case, we need to use the provided FAM, which is valid for the |
175 | // duration of the inliner pass, and thus the lifetime of the owned advisor. |
176 | // The one we would get from the MAM can be invalidated as a result of the |
177 | // inliner's activity. |
178 | OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>( |
179 | args&: M, args&: FAM, args: getInlineParams(), |
180 | args: InlineContext{.LTOPhase: LTOPhase, .Pass: InlinePass::CGSCCInliner}); |
181 | |
182 | if (!CGSCCInlineReplayFile.empty()) |
183 | OwnedAdvisor = getReplayInlineAdvisor( |
184 | M, FAM, Context&: M.getContext(), OriginalAdvisor: std::move(OwnedAdvisor), |
185 | ReplaySettings: ReplayInlinerSettings{.ReplayFile: CGSCCInlineReplayFile, |
186 | .ReplayScope: CGSCCInlineReplayScope, |
187 | .ReplayFallback: CGSCCInlineReplayFallback, |
188 | .ReplayFormat: {.OutputFormat: CGSCCInlineReplayFormat}}, |
189 | /*EmitRemarks=*/true, |
190 | IC: InlineContext{.LTOPhase: LTOPhase, .Pass: InlinePass::ReplayCGSCCInliner}); |
191 | |
192 | return *OwnedAdvisor; |
193 | } |
194 | assert(IAA->getAdvisor() && |
195 | "Expected a present InlineAdvisorAnalysis also have an " |
196 | "InlineAdvisor initialized" ); |
197 | return *IAA->getAdvisor(); |
198 | } |
199 | |
200 | PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC, |
201 | CGSCCAnalysisManager &AM, LazyCallGraph &CG, |
202 | CGSCCUpdateResult &UR) { |
203 | const auto &MAMProxy = |
204 | AM.getResult<ModuleAnalysisManagerCGSCCProxy>(IR&: InitialC, ExtraArgs&: CG); |
205 | bool Changed = false; |
206 | |
207 | assert(InitialC.size() > 0 && "Cannot handle an empty SCC!" ); |
208 | Module &M = *InitialC.begin()->getFunction().getParent(); |
209 | ProfileSummaryInfo *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(IR&: M); |
210 | |
211 | FunctionAnalysisManager &FAM = |
212 | AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: InitialC, ExtraArgs&: CG) |
213 | .getManager(); |
214 | |
215 | InlineAdvisor &Advisor = getAdvisor(MAM: MAMProxy, FAM, M); |
216 | Advisor.onPassEntry(SCC: &InitialC); |
217 | |
218 | auto AdvisorOnExit = make_scope_exit(F: [&] { Advisor.onPassExit(SCC: &InitialC); }); |
219 | |
220 | // We use a single common worklist for calls across the entire SCC. We |
221 | // process these in-order and append new calls introduced during inlining to |
222 | // the end. The PriorityInlineOrder is optional here, in which the smaller |
223 | // callee would have a higher priority to inline. |
224 | // |
225 | // Note that this particular order of processing is actually critical to |
226 | // avoid very bad behaviors. Consider *highly connected* call graphs where |
227 | // each function contains a small amount of code and a couple of calls to |
228 | // other functions. Because the LLVM inliner is fundamentally a bottom-up |
229 | // inliner, it can handle gracefully the fact that these all appear to be |
230 | // reasonable inlining candidates as it will flatten things until they become |
231 | // too big to inline, and then move on and flatten another batch. |
232 | // |
233 | // However, when processing call edges *within* an SCC we cannot rely on this |
234 | // bottom-up behavior. As a consequence, with heavily connected *SCCs* of |
235 | // functions we can end up incrementally inlining N calls into each of |
236 | // N functions because each incremental inlining decision looks good and we |
237 | // don't have a topological ordering to prevent explosions. |
238 | // |
239 | // To compensate for this, we don't process transitive edges made immediate |
240 | // by inlining until we've done one pass of inlining across the entire SCC. |
241 | // Large, highly connected SCCs still lead to some amount of code bloat in |
242 | // this model, but it is uniformly spread across all the functions in the SCC |
243 | // and eventually they all become too large to inline, rather than |
244 | // incrementally maknig a single function grow in a super linear fashion. |
245 | SmallVector<std::pair<CallBase *, int>, 16> Calls; |
246 | |
247 | // Populate the initial list of calls in this SCC. |
248 | for (auto &N : InitialC) { |
249 | auto &ORE = |
250 | FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: N.getFunction()); |
251 | // We want to generally process call sites top-down in order for |
252 | // simplifications stemming from replacing the call with the returned value |
253 | // after inlining to be visible to subsequent inlining decisions. |
254 | // FIXME: Using instructions sequence is a really bad way to do this. |
255 | // Instead we should do an actual RPO walk of the function body. |
256 | for (Instruction &I : instructions(F&: N.getFunction())) |
257 | if (auto *CB = dyn_cast<CallBase>(Val: &I)) |
258 | if (Function *Callee = CB->getCalledFunction()) { |
259 | if (!Callee->isDeclaration()) |
260 | Calls.push_back(Elt: {CB, -1}); |
261 | else if (!isa<IntrinsicInst>(Val: I)) { |
262 | using namespace ore; |
263 | setInlineRemark(CB&: *CB, Message: "unavailable definition" ); |
264 | ORE.emit(RemarkBuilder: [&]() { |
265 | return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition" , &I) |
266 | << NV("Callee" , Callee) << " will not be inlined into " |
267 | << NV("Caller" , CB->getCaller()) |
268 | << " because its definition is unavailable" |
269 | << setIsVerbose(); |
270 | }); |
271 | } |
272 | } |
273 | } |
274 | if (Calls.empty()) |
275 | return PreservedAnalyses::all(); |
276 | |
277 | // Capture updatable variable for the current SCC. |
278 | auto *C = &InitialC; |
279 | |
280 | // When inlining a callee produces new call sites, we want to keep track of |
281 | // the fact that they were inlined from the callee. This allows us to avoid |
282 | // infinite inlining in some obscure cases. To represent this, we use an |
283 | // index into the InlineHistory vector. |
284 | SmallVector<std::pair<Function *, int>, 16> InlineHistory; |
285 | |
286 | // Track a set vector of inlined callees so that we can augment the caller |
287 | // with all of their edges in the call graph before pruning out the ones that |
288 | // got simplified away. |
289 | SmallSetVector<Function *, 4> InlinedCallees; |
290 | |
291 | // Track the dead functions to delete once finished with inlining calls. We |
292 | // defer deleting these to make it easier to handle the call graph updates. |
293 | SmallVector<Function *, 4> DeadFunctions; |
294 | |
295 | // Track potentially dead non-local functions with comdats to see if they can |
296 | // be deleted as a batch after inlining. |
297 | SmallVector<Function *, 4> DeadFunctionsInComdats; |
298 | |
299 | // Loop forward over all of the calls. Note that we cannot cache the size as |
300 | // inlining can introduce new calls that need to be processed. |
301 | for (int I = 0; I < (int)Calls.size(); ++I) { |
302 | // We expect the calls to typically be batched with sequences of calls that |
303 | // have the same caller, so we first set up some shared infrastructure for |
304 | // this caller. We also do any pruning we can at this layer on the caller |
305 | // alone. |
306 | Function &F = *Calls[I].first->getCaller(); |
307 | LazyCallGraph::Node &N = *CG.lookup(F); |
308 | if (CG.lookupSCC(N) != C) |
309 | continue; |
310 | |
311 | LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n" |
312 | << " Function size: " << F.getInstructionCount() |
313 | << "\n" ); |
314 | |
315 | auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & { |
316 | return FAM.getResult<AssumptionAnalysis>(IR&: F); |
317 | }; |
318 | |
319 | // Now process as many calls as we have within this caller in the sequence. |
320 | // We bail out as soon as the caller has to change so we can update the |
321 | // call graph and prepare the context of that new caller. |
322 | bool DidInline = false; |
323 | for (; I < (int)Calls.size() && Calls[I].first->getCaller() == &F; ++I) { |
324 | auto &P = Calls[I]; |
325 | CallBase *CB = P.first; |
326 | const int InlineHistoryID = P.second; |
327 | Function &Callee = *CB->getCalledFunction(); |
328 | |
329 | if (InlineHistoryID != -1 && |
330 | inlineHistoryIncludes(F: &Callee, InlineHistoryID, InlineHistory)) { |
331 | LLVM_DEBUG(dbgs() << "Skipping inlining due to history: " << F.getName() |
332 | << " -> " << Callee.getName() << "\n" ); |
333 | setInlineRemark(CB&: *CB, Message: "recursive" ); |
334 | // Set noinline so that we don't forget this decision across CGSCC |
335 | // iterations. |
336 | CB->setIsNoInline(); |
337 | continue; |
338 | } |
339 | |
340 | // Check if this inlining may repeat breaking an SCC apart that has |
341 | // already been split once before. In that case, inlining here may |
342 | // trigger infinite inlining, much like is prevented within the inliner |
343 | // itself by the InlineHistory above, but spread across CGSCC iterations |
344 | // and thus hidden from the full inline history. |
345 | LazyCallGraph::SCC *CalleeSCC = CG.lookupSCC(N&: *CG.lookup(F: Callee)); |
346 | if (CalleeSCC == C && UR.InlinedInternalEdges.count(V: {&N, C})) { |
347 | LLVM_DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node " |
348 | "previously split out of this SCC by inlining: " |
349 | << F.getName() << " -> " << Callee.getName() << "\n" ); |
350 | setInlineRemark(CB&: *CB, Message: "recursive SCC split" ); |
351 | continue; |
352 | } |
353 | |
354 | std::unique_ptr<InlineAdvice> Advice = |
355 | Advisor.getAdvice(CB&: *CB, MandatoryOnly: OnlyMandatory); |
356 | |
357 | // Check whether we want to inline this callsite. |
358 | if (!Advice) |
359 | continue; |
360 | |
361 | if (!Advice->isInliningRecommended()) { |
362 | Advice->recordUnattemptedInlining(); |
363 | continue; |
364 | } |
365 | |
366 | int CBCostMult = |
367 | getStringFnAttrAsInt( |
368 | CB&: *CB, AttrKind: InlineConstants::FunctionInlineCostMultiplierAttributeName) |
369 | .value_or(u: 1); |
370 | |
371 | // Setup the data structure used to plumb customization into the |
372 | // `InlineFunction` routine. |
373 | InlineFunctionInfo IFI( |
374 | GetAssumptionCache, PSI, |
375 | &FAM.getResult<BlockFrequencyAnalysis>(IR&: *(CB->getCaller())), |
376 | &FAM.getResult<BlockFrequencyAnalysis>(IR&: Callee)); |
377 | |
378 | InlineResult IR = |
379 | InlineFunction(CB&: *CB, IFI, /*MergeAttributes=*/true, |
380 | CalleeAAR: &FAM.getResult<AAManager>(IR&: *CB->getCaller())); |
381 | if (!IR.isSuccess()) { |
382 | Advice->recordUnsuccessfulInlining(Result: IR); |
383 | continue; |
384 | } |
385 | |
386 | DidInline = true; |
387 | InlinedCallees.insert(X: &Callee); |
388 | ++NumInlined; |
389 | |
390 | LLVM_DEBUG(dbgs() << " Size after inlining: " |
391 | << F.getInstructionCount() << "\n" ); |
392 | |
393 | // Add any new callsites to defined functions to the worklist. |
394 | if (!IFI.InlinedCallSites.empty()) { |
395 | int NewHistoryID = InlineHistory.size(); |
396 | InlineHistory.push_back(Elt: {&Callee, InlineHistoryID}); |
397 | |
398 | for (CallBase *ICB : reverse(C&: IFI.InlinedCallSites)) { |
399 | Function *NewCallee = ICB->getCalledFunction(); |
400 | assert(!(NewCallee && NewCallee->isIntrinsic()) && |
401 | "Intrinsic calls should not be tracked." ); |
402 | if (!NewCallee) { |
403 | // Try to promote an indirect (virtual) call without waiting for |
404 | // the post-inline cleanup and the next DevirtSCCRepeatedPass |
405 | // iteration because the next iteration may not happen and we may |
406 | // miss inlining it. |
407 | if (tryPromoteCall(CB&: *ICB)) |
408 | NewCallee = ICB->getCalledFunction(); |
409 | } |
410 | if (NewCallee) { |
411 | if (!NewCallee->isDeclaration()) { |
412 | Calls.push_back(Elt: {ICB, NewHistoryID}); |
413 | // Continually inlining through an SCC can result in huge compile |
414 | // times and bloated code since we arbitrarily stop at some point |
415 | // when the inliner decides it's not profitable to inline anymore. |
416 | // We attempt to mitigate this by making these calls exponentially |
417 | // more expensive. |
418 | // This doesn't apply to calls in the same SCC since if we do |
419 | // inline through the SCC the function will end up being |
420 | // self-recursive which the inliner bails out on, and inlining |
421 | // within an SCC is necessary for performance. |
422 | if (CalleeSCC != C && |
423 | CalleeSCC == CG.lookupSCC(N&: CG.get(F&: *NewCallee))) { |
424 | Attribute NewCBCostMult = Attribute::get( |
425 | Context&: M.getContext(), |
426 | Kind: InlineConstants::FunctionInlineCostMultiplierAttributeName, |
427 | Val: itostr(X: CBCostMult * IntraSCCCostMultiplier)); |
428 | ICB->addFnAttr(Attr: NewCBCostMult); |
429 | } |
430 | } |
431 | } |
432 | } |
433 | } |
434 | |
435 | // For local functions or discardable functions without comdats, check |
436 | // whether this makes the callee trivially dead. In that case, we can drop |
437 | // the body of the function eagerly which may reduce the number of callers |
438 | // of other functions to one, changing inline cost thresholds. Non-local |
439 | // discardable functions with comdats are checked later on. |
440 | bool CalleeWasDeleted = false; |
441 | if (Callee.isDiscardableIfUnused() && Callee.hasZeroLiveUses() && |
442 | !CG.isLibFunction(F&: Callee)) { |
443 | if (Callee.hasLocalLinkage() || !Callee.hasComdat()) { |
444 | Calls.erase( |
445 | CS: std::remove_if(first: Calls.begin() + I + 1, last: Calls.end(), |
446 | pred: [&](const std::pair<CallBase *, int> &Call) { |
447 | return Call.first->getCaller() == &Callee; |
448 | }), |
449 | CE: Calls.end()); |
450 | |
451 | // Clear the body and queue the function itself for deletion when we |
452 | // finish inlining and call graph updates. |
453 | // Note that after this point, it is an error to do anything other |
454 | // than use the callee's address or delete it. |
455 | Callee.dropAllReferences(); |
456 | assert(!is_contained(DeadFunctions, &Callee) && |
457 | "Cannot put cause a function to become dead twice!" ); |
458 | DeadFunctions.push_back(Elt: &Callee); |
459 | CalleeWasDeleted = true; |
460 | } else { |
461 | DeadFunctionsInComdats.push_back(Elt: &Callee); |
462 | } |
463 | } |
464 | if (CalleeWasDeleted) |
465 | Advice->recordInliningWithCalleeDeleted(); |
466 | else |
467 | Advice->recordInlining(); |
468 | } |
469 | |
470 | // Back the call index up by one to put us in a good position to go around |
471 | // the outer loop. |
472 | --I; |
473 | |
474 | if (!DidInline) |
475 | continue; |
476 | Changed = true; |
477 | |
478 | // At this point, since we have made changes we have at least removed |
479 | // a call instruction. However, in the process we do some incremental |
480 | // simplification of the surrounding code. This simplification can |
481 | // essentially do all of the same things as a function pass and we can |
482 | // re-use the exact same logic for updating the call graph to reflect the |
483 | // change. |
484 | |
485 | // Inside the update, we also update the FunctionAnalysisManager in the |
486 | // proxy for this particular SCC. We do this as the SCC may have changed and |
487 | // as we're going to mutate this particular function we want to make sure |
488 | // the proxy is in place to forward any invalidation events. |
489 | LazyCallGraph::SCC *OldC = C; |
490 | C = &updateCGAndAnalysisManagerForCGSCCPass(G&: CG, C&: *C, N, AM, UR, FAM); |
491 | LLVM_DEBUG(dbgs() << "Updated inlining SCC: " << *C << "\n" ); |
492 | |
493 | // If this causes an SCC to split apart into multiple smaller SCCs, there |
494 | // is a subtle risk we need to prepare for. Other transformations may |
495 | // expose an "infinite inlining" opportunity later, and because of the SCC |
496 | // mutation, we will revisit this function and potentially re-inline. If we |
497 | // do, and that re-inlining also has the potentially to mutate the SCC |
498 | // structure, the infinite inlining problem can manifest through infinite |
499 | // SCC splits and merges. To avoid this, we capture the originating caller |
500 | // node and the SCC containing the call edge. This is a slight over |
501 | // approximation of the possible inlining decisions that must be avoided, |
502 | // but is relatively efficient to store. We use C != OldC to know when |
503 | // a new SCC is generated and the original SCC may be generated via merge |
504 | // in later iterations. |
505 | // |
506 | // It is also possible that even if no new SCC is generated |
507 | // (i.e., C == OldC), the original SCC could be split and then merged |
508 | // into the same one as itself. and the original SCC will be added into |
509 | // UR.CWorklist again, we want to catch such cases too. |
510 | // |
511 | // FIXME: This seems like a very heavyweight way of retaining the inline |
512 | // history, we should look for a more efficient way of tracking it. |
513 | if ((C != OldC || UR.CWorklist.count(key: OldC)) && |
514 | llvm::any_of(Range&: InlinedCallees, P: [&](Function *Callee) { |
515 | return CG.lookupSCC(N&: *CG.lookup(F: *Callee)) == OldC; |
516 | })) { |
517 | LLVM_DEBUG(dbgs() << "Inlined an internal call edge and split an SCC, " |
518 | "retaining this to avoid infinite inlining.\n" ); |
519 | UR.InlinedInternalEdges.insert(V: {&N, OldC}); |
520 | } |
521 | InlinedCallees.clear(); |
522 | |
523 | // Invalidate analyses for this function now so that we don't have to |
524 | // invalidate analyses for all functions in this SCC later. |
525 | FAM.invalidate(IR&: F, PA: PreservedAnalyses::none()); |
526 | } |
527 | |
528 | // We must ensure that we only delete functions with comdats if every function |
529 | // in the comdat is going to be deleted. |
530 | if (!DeadFunctionsInComdats.empty()) { |
531 | filterDeadComdatFunctions(DeadComdatFunctions&: DeadFunctionsInComdats); |
532 | for (auto *Callee : DeadFunctionsInComdats) |
533 | Callee->dropAllReferences(); |
534 | DeadFunctions.append(RHS: DeadFunctionsInComdats); |
535 | } |
536 | |
537 | // Now that we've finished inlining all of the calls across this SCC, delete |
538 | // all of the trivially dead functions, updating the call graph and the CGSCC |
539 | // pass manager in the process. |
540 | // |
541 | // Note that this walks a pointer set which has non-deterministic order but |
542 | // that is OK as all we do is delete things and add pointers to unordered |
543 | // sets. |
544 | for (Function *DeadF : DeadFunctions) { |
545 | // Get the necessary information out of the call graph and nuke the |
546 | // function there. Also, clear out any cached analyses. |
547 | auto &DeadC = *CG.lookupSCC(N&: *CG.lookup(F: *DeadF)); |
548 | FAM.clear(IR&: *DeadF, Name: DeadF->getName()); |
549 | AM.clear(IR&: DeadC, Name: DeadC.getName()); |
550 | auto &DeadRC = DeadC.getOuterRefSCC(); |
551 | CG.removeDeadFunction(F&: *DeadF); |
552 | |
553 | // Mark the relevant parts of the call graph as invalid so we don't visit |
554 | // them. |
555 | UR.InvalidatedSCCs.insert(Ptr: &DeadC); |
556 | UR.InvalidatedRefSCCs.insert(Ptr: &DeadRC); |
557 | |
558 | // If the updated SCC was the one containing the deleted function, clear it. |
559 | if (&DeadC == UR.UpdatedC) |
560 | UR.UpdatedC = nullptr; |
561 | |
562 | // And delete the actual function from the module. |
563 | M.getFunctionList().erase(IT: DeadF); |
564 | |
565 | ++NumDeleted; |
566 | } |
567 | |
568 | if (!Changed) |
569 | return PreservedAnalyses::all(); |
570 | |
571 | PreservedAnalyses PA; |
572 | // Even if we change the IR, we update the core CGSCC data structures and so |
573 | // can preserve the proxy to the function analysis manager. |
574 | PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); |
575 | // We have already invalidated all analyses on modified functions. |
576 | PA.preserveSet<AllAnalysesOn<Function>>(); |
577 | return PA; |
578 | } |
579 | |
580 | ModuleInlinerWrapperPass::ModuleInlinerWrapperPass(InlineParams Params, |
581 | bool MandatoryFirst, |
582 | InlineContext IC, |
583 | InliningAdvisorMode Mode, |
584 | unsigned MaxDevirtIterations) |
585 | : Params(Params), IC(IC), Mode(Mode), |
586 | MaxDevirtIterations(MaxDevirtIterations) { |
587 | // Run the inliner first. The theory is that we are walking bottom-up and so |
588 | // the callees have already been fully optimized, and we want to inline them |
589 | // into the callers so that our optimizations can reflect that. |
590 | // For PreLinkThinLTO pass, we disable hot-caller heuristic for sample PGO |
591 | // because it makes profile annotation in the backend inaccurate. |
592 | if (MandatoryFirst) { |
593 | PM.addPass(Pass: InlinerPass(/*OnlyMandatory*/ true)); |
594 | if (EnablePostSCCAdvisorPrinting) |
595 | PM.addPass(Pass: InlineAdvisorAnalysisPrinterPass(dbgs())); |
596 | } |
597 | PM.addPass(Pass: InlinerPass()); |
598 | if (EnablePostSCCAdvisorPrinting) |
599 | PM.addPass(Pass: InlineAdvisorAnalysisPrinterPass(dbgs())); |
600 | } |
601 | |
602 | PreservedAnalyses ModuleInlinerWrapperPass::run(Module &M, |
603 | ModuleAnalysisManager &MAM) { |
604 | auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(IR&: M); |
605 | if (!IAA.tryCreate(Params, Mode, |
606 | ReplaySettings: {.ReplayFile: CGSCCInlineReplayFile, |
607 | .ReplayScope: CGSCCInlineReplayScope, |
608 | .ReplayFallback: CGSCCInlineReplayFallback, |
609 | .ReplayFormat: {.OutputFormat: CGSCCInlineReplayFormat}}, |
610 | IC)) { |
611 | M.getContext().emitError( |
612 | ErrorStr: "Could not setup Inlining Advisor for the requested " |
613 | "mode and/or options" ); |
614 | return PreservedAnalyses::all(); |
615 | } |
616 | |
617 | // We wrap the CGSCC pipeline in a devirtualization repeater. This will try |
618 | // to detect when we devirtualize indirect calls and iterate the SCC passes |
619 | // in that case to try and catch knock-on inlining or function attrs |
620 | // opportunities. Then we add it to the module pipeline by walking the SCCs |
621 | // in postorder (or bottom-up). |
622 | // If MaxDevirtIterations is 0, we just don't use the devirtualization |
623 | // wrapper. |
624 | if (MaxDevirtIterations == 0) |
625 | MPM.addPass(Pass: createModuleToPostOrderCGSCCPassAdaptor(Pass: std::move(PM))); |
626 | else |
627 | MPM.addPass(Pass: createModuleToPostOrderCGSCCPassAdaptor( |
628 | Pass: createDevirtSCCRepeatedPass(Pass: std::move(PM), MaxIterations: MaxDevirtIterations))); |
629 | |
630 | MPM.addPass(Pass: std::move(AfterCGMPM)); |
631 | MPM.run(IR&: M, AM&: MAM); |
632 | |
633 | // Discard the InlineAdvisor, a subsequent inlining session should construct |
634 | // its own. |
635 | auto PA = PreservedAnalyses::all(); |
636 | if (!KeepAdvisorForPrinting) |
637 | PA.abandon<InlineAdvisorAnalysis>(); |
638 | return PA; |
639 | } |
640 | |
641 | void InlinerPass::printPipeline( |
642 | raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { |
643 | static_cast<PassInfoMixin<InlinerPass> *>(this)->printPipeline( |
644 | OS, MapClassName2PassName); |
645 | if (OnlyMandatory) |
646 | OS << "<only-mandatory>" ; |
647 | } |
648 | |
649 | void ModuleInlinerWrapperPass::printPipeline( |
650 | raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { |
651 | // Print some info about passes added to the wrapper. This is however |
652 | // incomplete as InlineAdvisorAnalysis part isn't included (which also depends |
653 | // on Params and Mode). |
654 | if (!MPM.isEmpty()) { |
655 | MPM.printPipeline(OS, MapClassName2PassName); |
656 | OS << ','; |
657 | } |
658 | OS << "cgscc(" ; |
659 | if (MaxDevirtIterations != 0) |
660 | OS << "devirt<" << MaxDevirtIterations << ">(" ; |
661 | PM.printPipeline(OS, MapClassName2PassName); |
662 | if (MaxDevirtIterations != 0) |
663 | OS << ')'; |
664 | OS << ')'; |
665 | } |
666 | |