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