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