1 | //===- CGSCCPassManager.cpp - Managing & running CGSCC passes -------------===// |
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 | #include "llvm/Analysis/CGSCCPassManager.h" |
10 | #include "llvm/ADT/ArrayRef.h" |
11 | #include "llvm/ADT/PriorityWorklist.h" |
12 | #include "llvm/ADT/STLExtras.h" |
13 | #include "llvm/ADT/SetVector.h" |
14 | #include "llvm/ADT/SmallPtrSet.h" |
15 | #include "llvm/ADT/SmallVector.h" |
16 | #include "llvm/ADT/iterator_range.h" |
17 | #include "llvm/Analysis/LazyCallGraph.h" |
18 | #include "llvm/IR/Constant.h" |
19 | #include "llvm/IR/InstIterator.h" |
20 | #include "llvm/IR/Instruction.h" |
21 | #include "llvm/IR/PassManager.h" |
22 | #include "llvm/IR/PassManagerImpl.h" |
23 | #include "llvm/IR/ValueHandle.h" |
24 | #include "llvm/Support/Casting.h" |
25 | #include "llvm/Support/CommandLine.h" |
26 | #include "llvm/Support/Debug.h" |
27 | #include "llvm/Support/ErrorHandling.h" |
28 | #include "llvm/Support/TimeProfiler.h" |
29 | #include "llvm/Support/raw_ostream.h" |
30 | #include <cassert> |
31 | #include <iterator> |
32 | #include <optional> |
33 | |
34 | #define DEBUG_TYPE "cgscc" |
35 | |
36 | using namespace llvm; |
37 | |
38 | // Explicit template instantiations and specialization definitions for core |
39 | // template typedefs. |
40 | namespace llvm { |
41 | static cl::opt<bool> AbortOnMaxDevirtIterationsReached( |
42 | "abort-on-max-devirt-iterations-reached" , |
43 | cl::desc("Abort when the max iterations for devirtualization CGSCC repeat " |
44 | "pass is reached" )); |
45 | |
46 | AnalysisKey ShouldNotRunFunctionPassesAnalysis::Key; |
47 | |
48 | // Explicit instantiations for the core proxy templates. |
49 | template class AllAnalysesOn<LazyCallGraph::SCC>; |
50 | template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>; |
51 | template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, |
52 | LazyCallGraph &, CGSCCUpdateResult &>; |
53 | template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>; |
54 | template class OuterAnalysisManagerProxy<ModuleAnalysisManager, |
55 | LazyCallGraph::SCC, LazyCallGraph &>; |
56 | template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>; |
57 | |
58 | /// Explicitly specialize the pass manager run method to handle call graph |
59 | /// updates. |
60 | template <> |
61 | PreservedAnalyses |
62 | PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &, |
63 | CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC, |
64 | CGSCCAnalysisManager &AM, |
65 | LazyCallGraph &G, CGSCCUpdateResult &UR) { |
66 | // Request PassInstrumentation from analysis manager, will use it to run |
67 | // instrumenting callbacks for the passes later. |
68 | PassInstrumentation PI = |
69 | AM.getResult<PassInstrumentationAnalysis>(IR&: InitialC, ExtraArgs&: G); |
70 | |
71 | PreservedAnalyses PA = PreservedAnalyses::all(); |
72 | |
73 | // The SCC may be refined while we are running passes over it, so set up |
74 | // a pointer that we can update. |
75 | LazyCallGraph::SCC *C = &InitialC; |
76 | |
77 | // Get Function analysis manager from its proxy. |
78 | FunctionAnalysisManager &FAM = |
79 | AM.getCachedResult<FunctionAnalysisManagerCGSCCProxy>(IR&: *C)->getManager(); |
80 | |
81 | for (auto &Pass : Passes) { |
82 | // Check the PassInstrumentation's BeforePass callbacks before running the |
83 | // pass, skip its execution completely if asked to (callback returns false). |
84 | if (!PI.runBeforePass(Pass: *Pass, IR: *C)) |
85 | continue; |
86 | |
87 | PreservedAnalyses PassPA = Pass->run(IR&: *C, AM, ExtraArgs&: G, ExtraArgs&: UR); |
88 | |
89 | // Update the SCC if necessary. |
90 | C = UR.UpdatedC ? UR.UpdatedC : C; |
91 | if (UR.UpdatedC) { |
92 | // If C is updated, also create a proxy and update FAM inside the result. |
93 | auto *ResultFAMCP = |
94 | &AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: *C, ExtraArgs&: G); |
95 | ResultFAMCP->updateFAM(FAM); |
96 | } |
97 | |
98 | // Intersect the final preserved analyses to compute the aggregate |
99 | // preserved set for this pass manager. |
100 | PA.intersect(Arg: PassPA); |
101 | |
102 | // If the CGSCC pass wasn't able to provide a valid updated SCC, the |
103 | // current SCC may simply need to be skipped if invalid. |
104 | if (UR.InvalidatedSCCs.count(Ptr: C)) { |
105 | PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass: *Pass, PA: PassPA); |
106 | LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n" ); |
107 | break; |
108 | } |
109 | |
110 | // Check that we didn't miss any update scenario. |
111 | assert(C->begin() != C->end() && "Cannot have an empty SCC!" ); |
112 | |
113 | // Update the analysis manager as each pass runs and potentially |
114 | // invalidates analyses. |
115 | AM.invalidate(IR&: *C, PA: PassPA); |
116 | |
117 | PI.runAfterPass<LazyCallGraph::SCC>(Pass: *Pass, IR: *C, PA: PassPA); |
118 | } |
119 | |
120 | // Before we mark all of *this* SCC's analyses as preserved below, intersect |
121 | // this with the cross-SCC preserved analysis set. This is used to allow |
122 | // CGSCC passes to mutate ancestor SCCs and still trigger proper invalidation |
123 | // for them. |
124 | UR.CrossSCCPA.intersect(Arg: PA); |
125 | |
126 | // Invalidation was handled after each pass in the above loop for the current |
127 | // SCC. Therefore, the remaining analysis results in the AnalysisManager are |
128 | // preserved. We mark this with a set so that we don't need to inspect each |
129 | // one individually. |
130 | PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>(); |
131 | |
132 | return PA; |
133 | } |
134 | |
135 | PreservedAnalyses |
136 | ModuleToPostOrderCGSCCPassAdaptor::run(Module &M, ModuleAnalysisManager &AM) { |
137 | // Setup the CGSCC analysis manager from its proxy. |
138 | CGSCCAnalysisManager &CGAM = |
139 | AM.getResult<CGSCCAnalysisManagerModuleProxy>(IR&: M).getManager(); |
140 | |
141 | // Get the call graph for this module. |
142 | LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(IR&: M); |
143 | |
144 | // Get Function analysis manager from its proxy. |
145 | FunctionAnalysisManager &FAM = |
146 | AM.getCachedResult<FunctionAnalysisManagerModuleProxy>(IR&: M)->getManager(); |
147 | |
148 | // We keep worklists to allow us to push more work onto the pass manager as |
149 | // the passes are run. |
150 | SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist; |
151 | SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist; |
152 | |
153 | // Keep sets for invalidated SCCs and RefSCCs that should be skipped when |
154 | // iterating off the worklists. |
155 | SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet; |
156 | SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet; |
157 | |
158 | SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4> |
159 | InlinedInternalEdges; |
160 | |
161 | CGSCCUpdateResult UR = { |
162 | .RCWorklist: RCWorklist, .CWorklist: CWorklist, .InvalidatedRefSCCs: InvalidRefSCCSet, |
163 | .InvalidatedSCCs: InvalidSCCSet, .UpdatedC: nullptr, .CrossSCCPA: PreservedAnalyses::all(), |
164 | .InlinedInternalEdges: InlinedInternalEdges, .IndirectVHs: {}}; |
165 | |
166 | // Request PassInstrumentation from analysis manager, will use it to run |
167 | // instrumenting callbacks for the passes later. |
168 | PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(IR&: M); |
169 | |
170 | PreservedAnalyses PA = PreservedAnalyses::all(); |
171 | CG.buildRefSCCs(); |
172 | for (LazyCallGraph::RefSCC &RC : |
173 | llvm::make_early_inc_range(Range: CG.postorder_ref_sccs())) { |
174 | assert(RCWorklist.empty() && |
175 | "Should always start with an empty RefSCC worklist" ); |
176 | // The postorder_ref_sccs range we are walking is lazily constructed, so |
177 | // we only push the first one onto the worklist. The worklist allows us |
178 | // to capture *new* RefSCCs created during transformations. |
179 | // |
180 | // We really want to form RefSCCs lazily because that makes them cheaper |
181 | // to update as the program is simplified and allows us to have greater |
182 | // cache locality as forming a RefSCC touches all the parts of all the |
183 | // functions within that RefSCC. |
184 | // |
185 | // We also eagerly increment the iterator to the next position because |
186 | // the CGSCC passes below may delete the current RefSCC. |
187 | RCWorklist.insert(X: &RC); |
188 | |
189 | do { |
190 | LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val(); |
191 | if (InvalidRefSCCSet.count(Ptr: RC)) { |
192 | LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n" ); |
193 | continue; |
194 | } |
195 | |
196 | assert(CWorklist.empty() && |
197 | "Should always start with an empty SCC worklist" ); |
198 | |
199 | LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC |
200 | << "\n" ); |
201 | |
202 | // The top of the worklist may *also* be the same SCC we just ran over |
203 | // (and invalidated for). Keep track of that last SCC we processed due |
204 | // to SCC update to avoid redundant processing when an SCC is both just |
205 | // updated itself and at the top of the worklist. |
206 | LazyCallGraph::SCC *LastUpdatedC = nullptr; |
207 | |
208 | // Push the initial SCCs in reverse post-order as we'll pop off the |
209 | // back and so see this in post-order. |
210 | for (LazyCallGraph::SCC &C : llvm::reverse(C&: *RC)) |
211 | CWorklist.insert(X: &C); |
212 | |
213 | do { |
214 | LazyCallGraph::SCC *C = CWorklist.pop_back_val(); |
215 | // Due to call graph mutations, we may have invalid SCCs or SCCs from |
216 | // other RefSCCs in the worklist. The invalid ones are dead and the |
217 | // other RefSCCs should be queued above, so we just need to skip both |
218 | // scenarios here. |
219 | if (InvalidSCCSet.count(Ptr: C)) { |
220 | LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n" ); |
221 | continue; |
222 | } |
223 | if (LastUpdatedC == C) { |
224 | LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n" ); |
225 | continue; |
226 | } |
227 | // We used to also check if the current SCC is part of the current |
228 | // RefSCC and bail if it wasn't, since it should be in RCWorklist. |
229 | // However, this can cause compile time explosions in some cases on |
230 | // modules with a huge RefSCC. If a non-trivial amount of SCCs in the |
231 | // huge RefSCC can become their own child RefSCC, we create one child |
232 | // RefSCC, bail on the current RefSCC, visit the child RefSCC, revisit |
233 | // the huge RefSCC, and repeat. By visiting all SCCs in the original |
234 | // RefSCC we create all the child RefSCCs in one pass of the RefSCC, |
235 | // rather one pass of the RefSCC creating one child RefSCC at a time. |
236 | |
237 | // Ensure we can proxy analysis updates from the CGSCC analysis manager |
238 | // into the Function analysis manager by getting a proxy here. |
239 | // This also needs to update the FunctionAnalysisManager, as this may be |
240 | // the first time we see this SCC. |
241 | CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: *C, ExtraArgs&: CG).updateFAM( |
242 | FAM); |
243 | |
244 | // Each time we visit a new SCC pulled off the worklist, |
245 | // a transformation of a child SCC may have also modified this parent |
246 | // and invalidated analyses. So we invalidate using the update record's |
247 | // cross-SCC preserved set. This preserved set is intersected by any |
248 | // CGSCC pass that handles invalidation (primarily pass managers) prior |
249 | // to marking its SCC as preserved. That lets us track everything that |
250 | // might need invalidation across SCCs without excessive invalidations |
251 | // on a single SCC. |
252 | // |
253 | // This essentially allows SCC passes to freely invalidate analyses |
254 | // of any ancestor SCC. If this becomes detrimental to successfully |
255 | // caching analyses, we could force each SCC pass to manually |
256 | // invalidate the analyses for any SCCs other than themselves which |
257 | // are mutated. However, that seems to lose the robustness of the |
258 | // pass-manager driven invalidation scheme. |
259 | CGAM.invalidate(IR&: *C, PA: UR.CrossSCCPA); |
260 | |
261 | do { |
262 | // Check that we didn't miss any update scenario. |
263 | assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!" ); |
264 | assert(C->begin() != C->end() && "Cannot have an empty SCC!" ); |
265 | |
266 | LastUpdatedC = UR.UpdatedC; |
267 | UR.UpdatedC = nullptr; |
268 | |
269 | // Check the PassInstrumentation's BeforePass callbacks before |
270 | // running the pass, skip its execution completely if asked to |
271 | // (callback returns false). |
272 | if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass: *Pass, IR: *C)) |
273 | continue; |
274 | |
275 | PreservedAnalyses PassPA = Pass->run(IR&: *C, AM&: CGAM, ExtraArgs&: CG, ExtraArgs&: UR); |
276 | |
277 | // Update the SCC and RefSCC if necessary. |
278 | C = UR.UpdatedC ? UR.UpdatedC : C; |
279 | |
280 | if (UR.UpdatedC) { |
281 | // If we're updating the SCC, also update the FAM inside the proxy's |
282 | // result. |
283 | CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: *C, ExtraArgs&: CG).updateFAM( |
284 | FAM); |
285 | } |
286 | |
287 | // Intersect with the cross-SCC preserved set to capture any |
288 | // cross-SCC invalidation. |
289 | UR.CrossSCCPA.intersect(Arg: PassPA); |
290 | // Intersect the preserved set so that invalidation of module |
291 | // analyses will eventually occur when the module pass completes. |
292 | PA.intersect(Arg: PassPA); |
293 | |
294 | // If the CGSCC pass wasn't able to provide a valid updated SCC, |
295 | // the current SCC may simply need to be skipped if invalid. |
296 | if (UR.InvalidatedSCCs.count(Ptr: C)) { |
297 | PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass: *Pass, PA: PassPA); |
298 | LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n" ); |
299 | break; |
300 | } |
301 | |
302 | // Check that we didn't miss any update scenario. |
303 | assert(C->begin() != C->end() && "Cannot have an empty SCC!" ); |
304 | |
305 | // We handle invalidating the CGSCC analysis manager's information |
306 | // for the (potentially updated) SCC here. Note that any other SCCs |
307 | // whose structure has changed should have been invalidated by |
308 | // whatever was updating the call graph. This SCC gets invalidated |
309 | // late as it contains the nodes that were actively being |
310 | // processed. |
311 | CGAM.invalidate(IR&: *C, PA: PassPA); |
312 | |
313 | PI.runAfterPass<LazyCallGraph::SCC>(Pass: *Pass, IR: *C, PA: PassPA); |
314 | |
315 | // The pass may have restructured the call graph and refined the |
316 | // current SCC and/or RefSCC. We need to update our current SCC and |
317 | // RefSCC pointers to follow these. Also, when the current SCC is |
318 | // refined, re-run the SCC pass over the newly refined SCC in order |
319 | // to observe the most precise SCC model available. This inherently |
320 | // cannot cycle excessively as it only happens when we split SCCs |
321 | // apart, at most converging on a DAG of single nodes. |
322 | // FIXME: If we ever start having RefSCC passes, we'll want to |
323 | // iterate there too. |
324 | if (UR.UpdatedC) |
325 | LLVM_DEBUG(dbgs() |
326 | << "Re-running SCC passes after a refinement of the " |
327 | "current SCC: " |
328 | << *UR.UpdatedC << "\n" ); |
329 | |
330 | // Note that both `C` and `RC` may at this point refer to deleted, |
331 | // invalid SCC and RefSCCs respectively. But we will short circuit |
332 | // the processing when we check them in the loop above. |
333 | } while (UR.UpdatedC); |
334 | } while (!CWorklist.empty()); |
335 | |
336 | // We only need to keep internal inlined edge information within |
337 | // a RefSCC, clear it to save on space and let the next time we visit |
338 | // any of these functions have a fresh start. |
339 | InlinedInternalEdges.clear(); |
340 | } while (!RCWorklist.empty()); |
341 | } |
342 | |
343 | // By definition we preserve the call garph, all SCC analyses, and the |
344 | // analysis proxies by handling them above and in any nested pass managers. |
345 | PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>(); |
346 | PA.preserve<LazyCallGraphAnalysis>(); |
347 | PA.preserve<CGSCCAnalysisManagerModuleProxy>(); |
348 | PA.preserve<FunctionAnalysisManagerModuleProxy>(); |
349 | return PA; |
350 | } |
351 | |
352 | PreservedAnalyses DevirtSCCRepeatedPass::run(LazyCallGraph::SCC &InitialC, |
353 | CGSCCAnalysisManager &AM, |
354 | LazyCallGraph &CG, |
355 | CGSCCUpdateResult &UR) { |
356 | PreservedAnalyses PA = PreservedAnalyses::all(); |
357 | PassInstrumentation PI = |
358 | AM.getResult<PassInstrumentationAnalysis>(IR&: InitialC, ExtraArgs&: CG); |
359 | |
360 | // The SCC may be refined while we are running passes over it, so set up |
361 | // a pointer that we can update. |
362 | LazyCallGraph::SCC *C = &InitialC; |
363 | |
364 | // Struct to track the counts of direct and indirect calls in each function |
365 | // of the SCC. |
366 | struct CallCount { |
367 | int Direct; |
368 | int Indirect; |
369 | }; |
370 | |
371 | // Put value handles on all of the indirect calls and return the number of |
372 | // direct calls for each function in the SCC. |
373 | auto ScanSCC = [](LazyCallGraph::SCC &C, |
374 | SmallMapVector<Value *, WeakTrackingVH, 16> &CallHandles) { |
375 | assert(CallHandles.empty() && "Must start with a clear set of handles." ); |
376 | |
377 | SmallDenseMap<Function *, CallCount> CallCounts; |
378 | CallCount CountLocal = {.Direct: 0, .Indirect: 0}; |
379 | for (LazyCallGraph::Node &N : C) { |
380 | CallCount &Count = |
381 | CallCounts.insert(KV: std::make_pair(x: &N.getFunction(), y&: CountLocal)) |
382 | .first->second; |
383 | for (Instruction &I : instructions(F&: N.getFunction())) |
384 | if (auto *CB = dyn_cast<CallBase>(Val: &I)) { |
385 | if (CB->getCalledFunction()) { |
386 | ++Count.Direct; |
387 | } else { |
388 | ++Count.Indirect; |
389 | CallHandles.insert(KV: {CB, WeakTrackingVH(CB)}); |
390 | } |
391 | } |
392 | } |
393 | |
394 | return CallCounts; |
395 | }; |
396 | |
397 | UR.IndirectVHs.clear(); |
398 | // Populate the initial call handles and get the initial call counts. |
399 | auto CallCounts = ScanSCC(*C, UR.IndirectVHs); |
400 | |
401 | for (int Iteration = 0;; ++Iteration) { |
402 | if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass: *Pass, IR: *C)) |
403 | continue; |
404 | |
405 | PreservedAnalyses PassPA = Pass->run(IR&: *C, AM, ExtraArgs&: CG, ExtraArgs&: UR); |
406 | |
407 | PA.intersect(Arg: PassPA); |
408 | |
409 | // If the CGSCC pass wasn't able to provide a valid updated SCC, the |
410 | // current SCC may simply need to be skipped if invalid. |
411 | if (UR.InvalidatedSCCs.count(Ptr: C)) { |
412 | PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass: *Pass, PA: PassPA); |
413 | LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n" ); |
414 | break; |
415 | } |
416 | |
417 | // Update the analysis manager with each run and intersect the total set |
418 | // of preserved analyses so we're ready to iterate. |
419 | AM.invalidate(IR&: *C, PA: PassPA); |
420 | |
421 | PI.runAfterPass<LazyCallGraph::SCC>(Pass: *Pass, IR: *C, PA: PassPA); |
422 | |
423 | // If the SCC structure has changed, bail immediately and let the outer |
424 | // CGSCC layer handle any iteration to reflect the refined structure. |
425 | if (UR.UpdatedC && UR.UpdatedC != C) |
426 | break; |
427 | |
428 | assert(C->begin() != C->end() && "Cannot have an empty SCC!" ); |
429 | |
430 | // Check whether any of the handles were devirtualized. |
431 | bool Devirt = llvm::any_of(Range&: UR.IndirectVHs, P: [](auto &P) -> bool { |
432 | if (P.second) { |
433 | if (CallBase *CB = dyn_cast<CallBase>(P.second)) { |
434 | if (CB->getCalledFunction()) { |
435 | LLVM_DEBUG(dbgs() << "Found devirtualized call: " << *CB << "\n" ); |
436 | return true; |
437 | } |
438 | } |
439 | } |
440 | return false; |
441 | }); |
442 | |
443 | // Rescan to build up a new set of handles and count how many direct |
444 | // calls remain. If we decide to iterate, this also sets up the input to |
445 | // the next iteration. |
446 | UR.IndirectVHs.clear(); |
447 | auto NewCallCounts = ScanSCC(*C, UR.IndirectVHs); |
448 | |
449 | // If we haven't found an explicit devirtualization already see if we |
450 | // have decreased the number of indirect calls and increased the number |
451 | // of direct calls for any function in the SCC. This can be fooled by all |
452 | // manner of transformations such as DCE and other things, but seems to |
453 | // work well in practice. |
454 | if (!Devirt) |
455 | // Iterate over the keys in NewCallCounts, if Function also exists in |
456 | // CallCounts, make the check below. |
457 | for (auto &Pair : NewCallCounts) { |
458 | auto &CallCountNew = Pair.second; |
459 | auto CountIt = CallCounts.find(Val: Pair.first); |
460 | if (CountIt != CallCounts.end()) { |
461 | const auto &CallCountOld = CountIt->second; |
462 | if (CallCountOld.Indirect > CallCountNew.Indirect && |
463 | CallCountOld.Direct < CallCountNew.Direct) { |
464 | Devirt = true; |
465 | break; |
466 | } |
467 | } |
468 | } |
469 | |
470 | if (!Devirt) { |
471 | break; |
472 | } |
473 | |
474 | // Otherwise, if we've already hit our max, we're done. |
475 | if (Iteration >= MaxIterations) { |
476 | if (AbortOnMaxDevirtIterationsReached) |
477 | report_fatal_error(reason: "Max devirtualization iterations reached" ); |
478 | LLVM_DEBUG( |
479 | dbgs() << "Found another devirtualization after hitting the max " |
480 | "number of repetitions (" |
481 | << MaxIterations << ") on SCC: " << *C << "\n" ); |
482 | break; |
483 | } |
484 | |
485 | LLVM_DEBUG( |
486 | dbgs() << "Repeating an SCC pass after finding a devirtualization in: " |
487 | << *C << "\n" ); |
488 | |
489 | // Move over the new call counts in preparation for iterating. |
490 | CallCounts = std::move(NewCallCounts); |
491 | } |
492 | |
493 | // Note that we don't add any preserved entries here unlike a more normal |
494 | // "pass manager" because we only handle invalidation *between* iterations, |
495 | // not after the last iteration. |
496 | return PA; |
497 | } |
498 | |
499 | PreservedAnalyses CGSCCToFunctionPassAdaptor::run(LazyCallGraph::SCC &C, |
500 | CGSCCAnalysisManager &AM, |
501 | LazyCallGraph &CG, |
502 | CGSCCUpdateResult &UR) { |
503 | // Setup the function analysis manager from its proxy. |
504 | FunctionAnalysisManager &FAM = |
505 | AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: CG).getManager(); |
506 | |
507 | SmallVector<LazyCallGraph::Node *, 4> Nodes; |
508 | for (LazyCallGraph::Node &N : C) |
509 | Nodes.push_back(Elt: &N); |
510 | |
511 | // The SCC may get split while we are optimizing functions due to deleting |
512 | // edges. If this happens, the current SCC can shift, so keep track of |
513 | // a pointer we can overwrite. |
514 | LazyCallGraph::SCC *CurrentC = &C; |
515 | |
516 | LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C << "\n" ); |
517 | |
518 | PreservedAnalyses PA = PreservedAnalyses::all(); |
519 | for (LazyCallGraph::Node *N : Nodes) { |
520 | // Skip nodes from other SCCs. These may have been split out during |
521 | // processing. We'll eventually visit those SCCs and pick up the nodes |
522 | // there. |
523 | if (CG.lookupSCC(N&: *N) != CurrentC) |
524 | continue; |
525 | |
526 | Function &F = N->getFunction(); |
527 | |
528 | if (NoRerun && FAM.getCachedResult<ShouldNotRunFunctionPassesAnalysis>(IR&: F)) |
529 | continue; |
530 | |
531 | PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(IR&: F); |
532 | if (!PI.runBeforePass<Function>(Pass: *Pass, IR: F)) |
533 | continue; |
534 | |
535 | PreservedAnalyses PassPA = Pass->run(IR&: F, AM&: FAM); |
536 | |
537 | // We know that the function pass couldn't have invalidated any other |
538 | // function's analyses (that's the contract of a function pass), so |
539 | // directly handle the function analysis manager's invalidation here. |
540 | FAM.invalidate(IR&: F, PA: EagerlyInvalidate ? PreservedAnalyses::none() : PassPA); |
541 | |
542 | PI.runAfterPass<Function>(Pass: *Pass, IR: F, PA: PassPA); |
543 | |
544 | // Then intersect the preserved set so that invalidation of module |
545 | // analyses will eventually occur when the module pass completes. |
546 | PA.intersect(Arg: std::move(PassPA)); |
547 | |
548 | // If the call graph hasn't been preserved, update it based on this |
549 | // function pass. This may also update the current SCC to point to |
550 | // a smaller, more refined SCC. |
551 | auto PAC = PA.getChecker<LazyCallGraphAnalysis>(); |
552 | if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) { |
553 | CurrentC = &updateCGAndAnalysisManagerForFunctionPass(G&: CG, C&: *CurrentC, N&: *N, |
554 | AM, UR, FAM); |
555 | assert(CG.lookupSCC(*N) == CurrentC && |
556 | "Current SCC not updated to the SCC containing the current node!" ); |
557 | } |
558 | } |
559 | |
560 | // By definition we preserve the proxy. And we preserve all analyses on |
561 | // Functions. This precludes *any* invalidation of function analyses by the |
562 | // proxy, but that's OK because we've taken care to invalidate analyses in |
563 | // the function analysis manager incrementally above. |
564 | PA.preserveSet<AllAnalysesOn<Function>>(); |
565 | PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); |
566 | |
567 | // We've also ensured that we updated the call graph along the way. |
568 | PA.preserve<LazyCallGraphAnalysis>(); |
569 | |
570 | return PA; |
571 | } |
572 | |
573 | bool CGSCCAnalysisManagerModuleProxy::Result::invalidate( |
574 | Module &M, const PreservedAnalyses &PA, |
575 | ModuleAnalysisManager::Invalidator &Inv) { |
576 | // If literally everything is preserved, we're done. |
577 | if (PA.areAllPreserved()) |
578 | return false; // This is still a valid proxy. |
579 | |
580 | // If this proxy or the call graph is going to be invalidated, we also need |
581 | // to clear all the keys coming from that analysis. |
582 | // |
583 | // We also directly invalidate the FAM's module proxy if necessary, and if |
584 | // that proxy isn't preserved we can't preserve this proxy either. We rely on |
585 | // it to handle module -> function analysis invalidation in the face of |
586 | // structural changes and so if it's unavailable we conservatively clear the |
587 | // entire SCC layer as well rather than trying to do invalidation ourselves. |
588 | auto PAC = PA.getChecker<CGSCCAnalysisManagerModuleProxy>(); |
589 | if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>()) || |
590 | Inv.invalidate<LazyCallGraphAnalysis>(IR&: M, PA) || |
591 | Inv.invalidate<FunctionAnalysisManagerModuleProxy>(IR&: M, PA)) { |
592 | InnerAM->clear(); |
593 | |
594 | // And the proxy itself should be marked as invalid so that we can observe |
595 | // the new call graph. This isn't strictly necessary because we cheat |
596 | // above, but is still useful. |
597 | return true; |
598 | } |
599 | |
600 | // Directly check if the relevant set is preserved so we can short circuit |
601 | // invalidating SCCs below. |
602 | bool AreSCCAnalysesPreserved = |
603 | PA.allAnalysesInSetPreserved<AllAnalysesOn<LazyCallGraph::SCC>>(); |
604 | |
605 | // Ok, we have a graph, so we can propagate the invalidation down into it. |
606 | G->buildRefSCCs(); |
607 | for (auto &RC : G->postorder_ref_sccs()) |
608 | for (auto &C : RC) { |
609 | std::optional<PreservedAnalyses> InnerPA; |
610 | |
611 | // Check to see whether the preserved set needs to be adjusted based on |
612 | // module-level analysis invalidation triggering deferred invalidation |
613 | // for this SCC. |
614 | if (auto *OuterProxy = |
615 | InnerAM->getCachedResult<ModuleAnalysisManagerCGSCCProxy>(IR&: C)) |
616 | for (const auto &OuterInvalidationPair : |
617 | OuterProxy->getOuterInvalidations()) { |
618 | AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first; |
619 | const auto &InnerAnalysisIDs = OuterInvalidationPair.second; |
620 | if (Inv.invalidate(ID: OuterAnalysisID, IR&: M, PA)) { |
621 | if (!InnerPA) |
622 | InnerPA = PA; |
623 | for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs) |
624 | InnerPA->abandon(ID: InnerAnalysisID); |
625 | } |
626 | } |
627 | |
628 | // Check if we needed a custom PA set. If so we'll need to run the inner |
629 | // invalidation. |
630 | if (InnerPA) { |
631 | InnerAM->invalidate(IR&: C, PA: *InnerPA); |
632 | continue; |
633 | } |
634 | |
635 | // Otherwise we only need to do invalidation if the original PA set didn't |
636 | // preserve all SCC analyses. |
637 | if (!AreSCCAnalysesPreserved) |
638 | InnerAM->invalidate(IR&: C, PA); |
639 | } |
640 | |
641 | // Return false to indicate that this result is still a valid proxy. |
642 | return false; |
643 | } |
644 | |
645 | template <> |
646 | CGSCCAnalysisManagerModuleProxy::Result |
647 | CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM) { |
648 | // Force the Function analysis manager to also be available so that it can |
649 | // be accessed in an SCC analysis and proxied onward to function passes. |
650 | // FIXME: It is pretty awkward to just drop the result here and assert that |
651 | // we can find it again later. |
652 | (void)AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M); |
653 | |
654 | return Result(*InnerAM, AM.getResult<LazyCallGraphAnalysis>(IR&: M)); |
655 | } |
656 | |
657 | AnalysisKey FunctionAnalysisManagerCGSCCProxy::Key; |
658 | |
659 | FunctionAnalysisManagerCGSCCProxy::Result |
660 | FunctionAnalysisManagerCGSCCProxy::run(LazyCallGraph::SCC &C, |
661 | CGSCCAnalysisManager &AM, |
662 | LazyCallGraph &CG) { |
663 | // Note: unconditionally getting checking that the proxy exists may get it at |
664 | // this point. There are cases when this is being run unnecessarily, but |
665 | // it is cheap and having the assertion in place is more valuable. |
666 | auto &MAMProxy = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: CG); |
667 | Module &M = *C.begin()->getFunction().getParent(); |
668 | bool ProxyExists = |
669 | MAMProxy.cachedResultExists<FunctionAnalysisManagerModuleProxy>(IR&: M); |
670 | assert(ProxyExists && |
671 | "The CGSCC pass manager requires that the FAM module proxy is run " |
672 | "on the module prior to entering the CGSCC walk" ); |
673 | (void)ProxyExists; |
674 | |
675 | // We just return an empty result. The caller will use the updateFAM interface |
676 | // to correctly register the relevant FunctionAnalysisManager based on the |
677 | // context in which this proxy is run. |
678 | return Result(); |
679 | } |
680 | |
681 | bool FunctionAnalysisManagerCGSCCProxy::Result::invalidate( |
682 | LazyCallGraph::SCC &C, const PreservedAnalyses &PA, |
683 | CGSCCAnalysisManager::Invalidator &Inv) { |
684 | // If literally everything is preserved, we're done. |
685 | if (PA.areAllPreserved()) |
686 | return false; // This is still a valid proxy. |
687 | |
688 | // All updates to preserve valid results are done below, so we don't need to |
689 | // invalidate this proxy. |
690 | // |
691 | // Note that in order to preserve this proxy, a module pass must ensure that |
692 | // the FAM has been completely updated to handle the deletion of functions. |
693 | // Specifically, any FAM-cached results for those functions need to have been |
694 | // forcibly cleared. When preserved, this proxy will only invalidate results |
695 | // cached on functions *still in the module* at the end of the module pass. |
696 | auto PAC = PA.getChecker<FunctionAnalysisManagerCGSCCProxy>(); |
697 | if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) { |
698 | for (LazyCallGraph::Node &N : C) |
699 | FAM->invalidate(IR&: N.getFunction(), PA); |
700 | |
701 | return false; |
702 | } |
703 | |
704 | // Directly check if the relevant set is preserved. |
705 | bool AreFunctionAnalysesPreserved = |
706 | PA.allAnalysesInSetPreserved<AllAnalysesOn<Function>>(); |
707 | |
708 | // Now walk all the functions to see if any inner analysis invalidation is |
709 | // necessary. |
710 | for (LazyCallGraph::Node &N : C) { |
711 | Function &F = N.getFunction(); |
712 | std::optional<PreservedAnalyses> FunctionPA; |
713 | |
714 | // Check to see whether the preserved set needs to be pruned based on |
715 | // SCC-level analysis invalidation that triggers deferred invalidation |
716 | // registered with the outer analysis manager proxy for this function. |
717 | if (auto *OuterProxy = |
718 | FAM->getCachedResult<CGSCCAnalysisManagerFunctionProxy>(IR&: F)) |
719 | for (const auto &OuterInvalidationPair : |
720 | OuterProxy->getOuterInvalidations()) { |
721 | AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first; |
722 | const auto &InnerAnalysisIDs = OuterInvalidationPair.second; |
723 | if (Inv.invalidate(ID: OuterAnalysisID, IR&: C, PA)) { |
724 | if (!FunctionPA) |
725 | FunctionPA = PA; |
726 | for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs) |
727 | FunctionPA->abandon(ID: InnerAnalysisID); |
728 | } |
729 | } |
730 | |
731 | // Check if we needed a custom PA set, and if so we'll need to run the |
732 | // inner invalidation. |
733 | if (FunctionPA) { |
734 | FAM->invalidate(IR&: F, PA: *FunctionPA); |
735 | continue; |
736 | } |
737 | |
738 | // Otherwise we only need to do invalidation if the original PA set didn't |
739 | // preserve all function analyses. |
740 | if (!AreFunctionAnalysesPreserved) |
741 | FAM->invalidate(IR&: F, PA); |
742 | } |
743 | |
744 | // Return false to indicate that this result is still a valid proxy. |
745 | return false; |
746 | } |
747 | |
748 | } // end namespace llvm |
749 | |
750 | /// When a new SCC is created for the graph we first update the |
751 | /// FunctionAnalysisManager in the Proxy's result. |
752 | /// As there might be function analysis results cached for the functions now in |
753 | /// that SCC, two forms of updates are required. |
754 | /// |
755 | /// First, a proxy from the SCC to the FunctionAnalysisManager needs to be |
756 | /// created so that any subsequent invalidation events to the SCC are |
757 | /// propagated to the function analysis results cached for functions within it. |
758 | /// |
759 | /// Second, if any of the functions within the SCC have analysis results with |
760 | /// outer analysis dependencies, then those dependencies would point to the |
761 | /// *wrong* SCC's analysis result. We forcibly invalidate the necessary |
762 | /// function analyses so that they don't retain stale handles. |
763 | static void updateNewSCCFunctionAnalyses(LazyCallGraph::SCC &C, |
764 | LazyCallGraph &G, |
765 | CGSCCAnalysisManager &AM, |
766 | FunctionAnalysisManager &FAM) { |
767 | AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: G).updateFAM(FAM); |
768 | |
769 | // Now walk the functions in this SCC and invalidate any function analysis |
770 | // results that might have outer dependencies on an SCC analysis. |
771 | for (LazyCallGraph::Node &N : C) { |
772 | Function &F = N.getFunction(); |
773 | |
774 | auto *OuterProxy = |
775 | FAM.getCachedResult<CGSCCAnalysisManagerFunctionProxy>(IR&: F); |
776 | if (!OuterProxy) |
777 | // No outer analyses were queried, nothing to do. |
778 | continue; |
779 | |
780 | // Forcibly abandon all the inner analyses with dependencies, but |
781 | // invalidate nothing else. |
782 | auto PA = PreservedAnalyses::all(); |
783 | for (const auto &OuterInvalidationPair : |
784 | OuterProxy->getOuterInvalidations()) { |
785 | const auto &InnerAnalysisIDs = OuterInvalidationPair.second; |
786 | for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs) |
787 | PA.abandon(ID: InnerAnalysisID); |
788 | } |
789 | |
790 | // Now invalidate anything we found. |
791 | FAM.invalidate(IR&: F, PA); |
792 | } |
793 | } |
794 | |
795 | /// Helper function to update both the \c CGSCCAnalysisManager \p AM and the \c |
796 | /// CGSCCPassManager's \c CGSCCUpdateResult \p UR based on a range of newly |
797 | /// added SCCs. |
798 | /// |
799 | /// The range of new SCCs must be in postorder already. The SCC they were split |
800 | /// out of must be provided as \p C. The current node being mutated and |
801 | /// triggering updates must be passed as \p N. |
802 | /// |
803 | /// This function returns the SCC containing \p N. This will be either \p C if |
804 | /// no new SCCs have been split out, or it will be the new SCC containing \p N. |
805 | template <typename SCCRangeT> |
806 | static LazyCallGraph::SCC * |
807 | incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G, |
808 | LazyCallGraph::Node &N, LazyCallGraph::SCC *C, |
809 | CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) { |
810 | using SCC = LazyCallGraph::SCC; |
811 | |
812 | if (NewSCCRange.empty()) |
813 | return C; |
814 | |
815 | // Add the current SCC to the worklist as its shape has changed. |
816 | UR.CWorklist.insert(X: C); |
817 | LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist:" << *C |
818 | << "\n" ); |
819 | |
820 | SCC *OldC = C; |
821 | |
822 | // Update the current SCC. Note that if we have new SCCs, this must actually |
823 | // change the SCC. |
824 | assert(C != &*NewSCCRange.begin() && |
825 | "Cannot insert new SCCs without changing current SCC!" ); |
826 | C = &*NewSCCRange.begin(); |
827 | assert(G.lookupSCC(N) == C && "Failed to update current SCC!" ); |
828 | |
829 | // If we had a cached FAM proxy originally, we will want to create more of |
830 | // them for each SCC that was split off. |
831 | FunctionAnalysisManager *FAM = nullptr; |
832 | if (auto *FAMProxy = |
833 | AM.getCachedResult<FunctionAnalysisManagerCGSCCProxy>(IR&: *OldC)) |
834 | FAM = &FAMProxy->getManager(); |
835 | |
836 | // We need to propagate an invalidation call to all but the newly current SCC |
837 | // because the outer pass manager won't do that for us after splitting them. |
838 | // FIXME: We should accept a PreservedAnalysis from the CG updater so that if |
839 | // there are preserved analysis we can avoid invalidating them here for |
840 | // split-off SCCs. |
841 | // We know however that this will preserve any FAM proxy so go ahead and mark |
842 | // that. |
843 | auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>(); |
844 | PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); |
845 | AM.invalidate(IR&: *OldC, PA); |
846 | |
847 | // Ensure the now-current SCC's function analyses are updated. |
848 | if (FAM) |
849 | updateNewSCCFunctionAnalyses(C&: *C, G, AM, FAM&: *FAM); |
850 | |
851 | for (SCC &NewC : llvm::reverse(llvm::drop_begin(NewSCCRange))) { |
852 | assert(C != &NewC && "No need to re-visit the current SCC!" ); |
853 | assert(OldC != &NewC && "Already handled the original SCC!" ); |
854 | UR.CWorklist.insert(X: &NewC); |
855 | LLVM_DEBUG(dbgs() << "Enqueuing a newly formed SCC:" << NewC << "\n" ); |
856 | |
857 | // Ensure new SCCs' function analyses are updated. |
858 | if (FAM) |
859 | updateNewSCCFunctionAnalyses(C&: NewC, G, AM, FAM&: *FAM); |
860 | |
861 | // Also propagate a normal invalidation to the new SCC as only the current |
862 | // will get one from the pass manager infrastructure. |
863 | AM.invalidate(IR&: NewC, PA); |
864 | } |
865 | return C; |
866 | } |
867 | |
868 | static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass( |
869 | LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N, |
870 | CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, |
871 | FunctionAnalysisManager &FAM, bool FunctionPass) { |
872 | using Node = LazyCallGraph::Node; |
873 | using Edge = LazyCallGraph::Edge; |
874 | using SCC = LazyCallGraph::SCC; |
875 | using RefSCC = LazyCallGraph::RefSCC; |
876 | |
877 | RefSCC &InitialRC = InitialC.getOuterRefSCC(); |
878 | SCC *C = &InitialC; |
879 | RefSCC *RC = &InitialRC; |
880 | Function &F = N.getFunction(); |
881 | |
882 | // Walk the function body and build up the set of retained, promoted, and |
883 | // demoted edges. |
884 | SmallVector<Constant *, 16> Worklist; |
885 | SmallPtrSet<Constant *, 16> Visited; |
886 | SmallPtrSet<Node *, 16> RetainedEdges; |
887 | SmallSetVector<Node *, 4> PromotedRefTargets; |
888 | SmallSetVector<Node *, 4> DemotedCallTargets; |
889 | SmallSetVector<Node *, 4> NewCallEdges; |
890 | SmallSetVector<Node *, 4> NewRefEdges; |
891 | |
892 | // First walk the function and handle all called functions. We do this first |
893 | // because if there is a single call edge, whether there are ref edges is |
894 | // irrelevant. |
895 | for (Instruction &I : instructions(F)) { |
896 | if (auto *CB = dyn_cast<CallBase>(Val: &I)) { |
897 | if (Function *Callee = CB->getCalledFunction()) { |
898 | if (Visited.insert(Ptr: Callee).second && !Callee->isDeclaration()) { |
899 | Node *CalleeN = G.lookup(F: *Callee); |
900 | assert(CalleeN && |
901 | "Visited function should already have an associated node" ); |
902 | Edge *E = N->lookup(N&: *CalleeN); |
903 | assert((E || !FunctionPass) && |
904 | "No function transformations should introduce *new* " |
905 | "call edges! Any new calls should be modeled as " |
906 | "promoted existing ref edges!" ); |
907 | bool Inserted = RetainedEdges.insert(Ptr: CalleeN).second; |
908 | (void)Inserted; |
909 | assert(Inserted && "We should never visit a function twice." ); |
910 | if (!E) |
911 | NewCallEdges.insert(X: CalleeN); |
912 | else if (!E->isCall()) |
913 | PromotedRefTargets.insert(X: CalleeN); |
914 | } |
915 | } else { |
916 | // We can miss devirtualization if an indirect call is created then |
917 | // promoted before updateCGAndAnalysisManagerForPass runs. |
918 | auto *Entry = UR.IndirectVHs.find(Key: CB); |
919 | if (Entry == UR.IndirectVHs.end()) |
920 | UR.IndirectVHs.insert(KV: {CB, WeakTrackingVH(CB)}); |
921 | else if (!Entry->second) |
922 | Entry->second = WeakTrackingVH(CB); |
923 | } |
924 | } |
925 | } |
926 | |
927 | // Now walk all references. |
928 | for (Instruction &I : instructions(F)) |
929 | for (Value *Op : I.operand_values()) |
930 | if (auto *OpC = dyn_cast<Constant>(Val: Op)) |
931 | if (Visited.insert(Ptr: OpC).second) |
932 | Worklist.push_back(Elt: OpC); |
933 | |
934 | auto VisitRef = [&](Function &Referee) { |
935 | Node *RefereeN = G.lookup(F: Referee); |
936 | assert(RefereeN && |
937 | "Visited function should already have an associated node" ); |
938 | Edge *E = N->lookup(N&: *RefereeN); |
939 | assert((E || !FunctionPass) && |
940 | "No function transformations should introduce *new* ref " |
941 | "edges! Any new ref edges would require IPO which " |
942 | "function passes aren't allowed to do!" ); |
943 | bool Inserted = RetainedEdges.insert(Ptr: RefereeN).second; |
944 | (void)Inserted; |
945 | assert(Inserted && "We should never visit a function twice." ); |
946 | if (!E) |
947 | NewRefEdges.insert(X: RefereeN); |
948 | else if (E->isCall()) |
949 | DemotedCallTargets.insert(X: RefereeN); |
950 | }; |
951 | LazyCallGraph::visitReferences(Worklist, Visited, Callback: VisitRef); |
952 | |
953 | // Handle new ref edges. |
954 | for (Node *RefTarget : NewRefEdges) { |
955 | SCC &TargetC = *G.lookupSCC(N&: *RefTarget); |
956 | RefSCC &TargetRC = TargetC.getOuterRefSCC(); |
957 | (void)TargetRC; |
958 | // TODO: This only allows trivial edges to be added for now. |
959 | #ifdef EXPENSIVE_CHECKS |
960 | assert((RC == &TargetRC || |
961 | RC->isAncestorOf(TargetRC)) && "New ref edge is not trivial!" ); |
962 | #endif |
963 | RC->insertTrivialRefEdge(SourceN&: N, TargetN&: *RefTarget); |
964 | } |
965 | |
966 | // Handle new call edges. |
967 | for (Node *CallTarget : NewCallEdges) { |
968 | SCC &TargetC = *G.lookupSCC(N&: *CallTarget); |
969 | RefSCC &TargetRC = TargetC.getOuterRefSCC(); |
970 | (void)TargetRC; |
971 | // TODO: This only allows trivial edges to be added for now. |
972 | #ifdef EXPENSIVE_CHECKS |
973 | assert((RC == &TargetRC || |
974 | RC->isAncestorOf(TargetRC)) && "New call edge is not trivial!" ); |
975 | #endif |
976 | // Add a trivial ref edge to be promoted later on alongside |
977 | // PromotedRefTargets. |
978 | RC->insertTrivialRefEdge(SourceN&: N, TargetN&: *CallTarget); |
979 | } |
980 | |
981 | // Include synthetic reference edges to known, defined lib functions. |
982 | for (auto *LibFn : G.getLibFunctions()) |
983 | // While the list of lib functions doesn't have repeats, don't re-visit |
984 | // anything handled above. |
985 | if (!Visited.count(Ptr: LibFn)) |
986 | VisitRef(*LibFn); |
987 | |
988 | // First remove all of the edges that are no longer present in this function. |
989 | // The first step makes these edges uniformly ref edges and accumulates them |
990 | // into a separate data structure so removal doesn't invalidate anything. |
991 | SmallVector<Node *, 4> DeadTargets; |
992 | for (Edge &E : *N) { |
993 | if (RetainedEdges.count(Ptr: &E.getNode())) |
994 | continue; |
995 | |
996 | SCC &TargetC = *G.lookupSCC(N&: E.getNode()); |
997 | RefSCC &TargetRC = TargetC.getOuterRefSCC(); |
998 | if (&TargetRC == RC && E.isCall()) { |
999 | if (C != &TargetC) { |
1000 | // For separate SCCs this is trivial. |
1001 | RC->switchTrivialInternalEdgeToRef(SourceN&: N, TargetN&: E.getNode()); |
1002 | } else { |
1003 | // Now update the call graph. |
1004 | C = incorporateNewSCCRange(NewSCCRange: RC->switchInternalEdgeToRef(SourceN&: N, TargetN&: E.getNode()), |
1005 | G, N, C, AM, UR); |
1006 | } |
1007 | } |
1008 | |
1009 | // Now that this is ready for actual removal, put it into our list. |
1010 | DeadTargets.push_back(Elt: &E.getNode()); |
1011 | } |
1012 | // Remove the easy cases quickly and actually pull them out of our list. |
1013 | llvm::erase_if(C&: DeadTargets, P: [&](Node *TargetN) { |
1014 | SCC &TargetC = *G.lookupSCC(N&: *TargetN); |
1015 | RefSCC &TargetRC = TargetC.getOuterRefSCC(); |
1016 | |
1017 | // We can't trivially remove internal targets, so skip |
1018 | // those. |
1019 | if (&TargetRC == RC) |
1020 | return false; |
1021 | |
1022 | LLVM_DEBUG(dbgs() << "Deleting outgoing edge from '" << N << "' to '" |
1023 | << *TargetN << "'\n" ); |
1024 | RC->removeOutgoingEdge(SourceN&: N, TargetN&: *TargetN); |
1025 | return true; |
1026 | }); |
1027 | |
1028 | // Now do a batch removal of the internal ref edges left. |
1029 | auto NewRefSCCs = RC->removeInternalRefEdge(SourceN&: N, TargetNs: DeadTargets); |
1030 | if (!NewRefSCCs.empty()) { |
1031 | // The old RefSCC is dead, mark it as such. |
1032 | UR.InvalidatedRefSCCs.insert(Ptr: RC); |
1033 | |
1034 | // Note that we don't bother to invalidate analyses as ref-edge |
1035 | // connectivity is not really observable in any way and is intended |
1036 | // exclusively to be used for ordering of transforms rather than for |
1037 | // analysis conclusions. |
1038 | |
1039 | // Update RC to the "bottom". |
1040 | assert(G.lookupSCC(N) == C && "Changed the SCC when splitting RefSCCs!" ); |
1041 | RC = &C->getOuterRefSCC(); |
1042 | assert(G.lookupRefSCC(N) == RC && "Failed to update current RefSCC!" ); |
1043 | |
1044 | // The RC worklist is in reverse postorder, so we enqueue the new ones in |
1045 | // RPO except for the one which contains the source node as that is the |
1046 | // "bottom" we will continue processing in the bottom-up walk. |
1047 | assert(NewRefSCCs.front() == RC && |
1048 | "New current RefSCC not first in the returned list!" ); |
1049 | for (RefSCC *NewRC : llvm::reverse(C: llvm::drop_begin(RangeOrContainer&: NewRefSCCs))) { |
1050 | assert(NewRC != RC && "Should not encounter the current RefSCC further " |
1051 | "in the postorder list of new RefSCCs." ); |
1052 | UR.RCWorklist.insert(X: NewRC); |
1053 | LLVM_DEBUG(dbgs() << "Enqueuing a new RefSCC in the update worklist: " |
1054 | << *NewRC << "\n" ); |
1055 | } |
1056 | } |
1057 | |
1058 | // Next demote all the call edges that are now ref edges. This helps make |
1059 | // the SCCs small which should minimize the work below as we don't want to |
1060 | // form cycles that this would break. |
1061 | for (Node *RefTarget : DemotedCallTargets) { |
1062 | SCC &TargetC = *G.lookupSCC(N&: *RefTarget); |
1063 | RefSCC &TargetRC = TargetC.getOuterRefSCC(); |
1064 | |
1065 | // The easy case is when the target RefSCC is not this RefSCC. This is |
1066 | // only supported when the target RefSCC is a child of this RefSCC. |
1067 | if (&TargetRC != RC) { |
1068 | #ifdef EXPENSIVE_CHECKS |
1069 | assert(RC->isAncestorOf(TargetRC) && |
1070 | "Cannot potentially form RefSCC cycles here!" ); |
1071 | #endif |
1072 | RC->switchOutgoingEdgeToRef(SourceN&: N, TargetN&: *RefTarget); |
1073 | LLVM_DEBUG(dbgs() << "Switch outgoing call edge to a ref edge from '" << N |
1074 | << "' to '" << *RefTarget << "'\n" ); |
1075 | continue; |
1076 | } |
1077 | |
1078 | // We are switching an internal call edge to a ref edge. This may split up |
1079 | // some SCCs. |
1080 | if (C != &TargetC) { |
1081 | // For separate SCCs this is trivial. |
1082 | RC->switchTrivialInternalEdgeToRef(SourceN&: N, TargetN&: *RefTarget); |
1083 | continue; |
1084 | } |
1085 | |
1086 | // Now update the call graph. |
1087 | C = incorporateNewSCCRange(NewSCCRange: RC->switchInternalEdgeToRef(SourceN&: N, TargetN&: *RefTarget), G, N, |
1088 | C, AM, UR); |
1089 | } |
1090 | |
1091 | // We added a ref edge earlier for new call edges, promote those to call edges |
1092 | // alongside PromotedRefTargets. |
1093 | for (Node *E : NewCallEdges) |
1094 | PromotedRefTargets.insert(X: E); |
1095 | |
1096 | // Now promote ref edges into call edges. |
1097 | for (Node *CallTarget : PromotedRefTargets) { |
1098 | SCC &TargetC = *G.lookupSCC(N&: *CallTarget); |
1099 | RefSCC &TargetRC = TargetC.getOuterRefSCC(); |
1100 | |
1101 | // The easy case is when the target RefSCC is not this RefSCC. This is |
1102 | // only supported when the target RefSCC is a child of this RefSCC. |
1103 | if (&TargetRC != RC) { |
1104 | #ifdef EXPENSIVE_CHECKS |
1105 | assert(RC->isAncestorOf(TargetRC) && |
1106 | "Cannot potentially form RefSCC cycles here!" ); |
1107 | #endif |
1108 | RC->switchOutgoingEdgeToCall(SourceN&: N, TargetN&: *CallTarget); |
1109 | LLVM_DEBUG(dbgs() << "Switch outgoing ref edge to a call edge from '" << N |
1110 | << "' to '" << *CallTarget << "'\n" ); |
1111 | continue; |
1112 | } |
1113 | LLVM_DEBUG(dbgs() << "Switch an internal ref edge to a call edge from '" |
1114 | << N << "' to '" << *CallTarget << "'\n" ); |
1115 | |
1116 | // Otherwise we are switching an internal ref edge to a call edge. This |
1117 | // may merge away some SCCs, and we add those to the UpdateResult. We also |
1118 | // need to make sure to update the worklist in the event SCCs have moved |
1119 | // before the current one in the post-order sequence |
1120 | bool HasFunctionAnalysisProxy = false; |
1121 | auto InitialSCCIndex = RC->find(C&: *C) - RC->begin(); |
1122 | bool FormedCycle = RC->switchInternalEdgeToCall( |
1123 | SourceN&: N, TargetN&: *CallTarget, MergeCB: [&](ArrayRef<SCC *> MergedSCCs) { |
1124 | for (SCC *MergedC : MergedSCCs) { |
1125 | assert(MergedC != &TargetC && "Cannot merge away the target SCC!" ); |
1126 | |
1127 | HasFunctionAnalysisProxy |= |
1128 | AM.getCachedResult<FunctionAnalysisManagerCGSCCProxy>( |
1129 | IR&: *MergedC) != nullptr; |
1130 | |
1131 | // Mark that this SCC will no longer be valid. |
1132 | UR.InvalidatedSCCs.insert(Ptr: MergedC); |
1133 | |
1134 | // FIXME: We should really do a 'clear' here to forcibly release |
1135 | // memory, but we don't have a good way of doing that and |
1136 | // preserving the function analyses. |
1137 | auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>(); |
1138 | PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); |
1139 | AM.invalidate(IR&: *MergedC, PA); |
1140 | } |
1141 | }); |
1142 | |
1143 | // If we formed a cycle by creating this call, we need to update more data |
1144 | // structures. |
1145 | if (FormedCycle) { |
1146 | C = &TargetC; |
1147 | assert(G.lookupSCC(N) == C && "Failed to update current SCC!" ); |
1148 | |
1149 | // If one of the invalidated SCCs had a cached proxy to a function |
1150 | // analysis manager, we need to create a proxy in the new current SCC as |
1151 | // the invalidated SCCs had their functions moved. |
1152 | if (HasFunctionAnalysisProxy) |
1153 | AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: *C, ExtraArgs&: G).updateFAM(FAM); |
1154 | |
1155 | // Any analyses cached for this SCC are no longer precise as the shape |
1156 | // has changed by introducing this cycle. However, we have taken care to |
1157 | // update the proxies so it remains valide. |
1158 | auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>(); |
1159 | PA.preserve<FunctionAnalysisManagerCGSCCProxy>(); |
1160 | AM.invalidate(IR&: *C, PA); |
1161 | } |
1162 | auto NewSCCIndex = RC->find(C&: *C) - RC->begin(); |
1163 | // If we have actually moved an SCC to be topologically "below" the current |
1164 | // one due to merging, we will need to revisit the current SCC after |
1165 | // visiting those moved SCCs. |
1166 | // |
1167 | // It is critical that we *do not* revisit the current SCC unless we |
1168 | // actually move SCCs in the process of merging because otherwise we may |
1169 | // form a cycle where an SCC is split apart, merged, split, merged and so |
1170 | // on infinitely. |
1171 | if (InitialSCCIndex < NewSCCIndex) { |
1172 | // Put our current SCC back onto the worklist as we'll visit other SCCs |
1173 | // that are now definitively ordered prior to the current one in the |
1174 | // post-order sequence, and may end up observing more precise context to |
1175 | // optimize the current SCC. |
1176 | UR.CWorklist.insert(X: C); |
1177 | LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist: " << *C |
1178 | << "\n" ); |
1179 | // Enqueue in reverse order as we pop off the back of the worklist. |
1180 | for (SCC &MovedC : llvm::reverse(C: make_range(x: RC->begin() + InitialSCCIndex, |
1181 | y: RC->begin() + NewSCCIndex))) { |
1182 | UR.CWorklist.insert(X: &MovedC); |
1183 | LLVM_DEBUG(dbgs() << "Enqueuing a newly earlier in post-order SCC: " |
1184 | << MovedC << "\n" ); |
1185 | } |
1186 | } |
1187 | } |
1188 | |
1189 | assert(!UR.InvalidatedSCCs.count(C) && "Invalidated the current SCC!" ); |
1190 | assert(!UR.InvalidatedRefSCCs.count(RC) && "Invalidated the current RefSCC!" ); |
1191 | assert(&C->getOuterRefSCC() == RC && "Current SCC not in current RefSCC!" ); |
1192 | |
1193 | // Record the current SCC for higher layers of the CGSCC pass manager now that |
1194 | // all the updates have been applied. |
1195 | if (C != &InitialC) |
1196 | UR.UpdatedC = C; |
1197 | |
1198 | return *C; |
1199 | } |
1200 | |
1201 | LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass( |
1202 | LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N, |
1203 | CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, |
1204 | FunctionAnalysisManager &FAM) { |
1205 | return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM, |
1206 | /* FunctionPass */ true); |
1207 | } |
1208 | LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForCGSCCPass( |
1209 | LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N, |
1210 | CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, |
1211 | FunctionAnalysisManager &FAM) { |
1212 | return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM, |
1213 | /* FunctionPass */ false); |
1214 | } |
1215 | |