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 "AnalysisOptions.h"
11#include "llvm/ADT/ArrayRef.h"
12#include "llvm/ADT/PriorityWorklist.h"
13#include "llvm/ADT/STLExtras.h"
14#include "llvm/ADT/SetVector.h"
15#include "llvm/ADT/SmallPtrSet.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/ADT/iterator_range.h"
19#include "llvm/Analysis/LazyCallGraph.h"
20#include "llvm/IR/Constant.h"
21#include "llvm/IR/InstIterator.h"
22#include "llvm/IR/Instruction.h"
23#include "llvm/IR/PassManager.h"
24#include "llvm/IR/PassManagerImpl.h"
25#include "llvm/IR/ValueHandle.h"
26#include "llvm/Support/Casting.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 {
43AnalysisKey ShouldNotRunFunctionPassesAnalysis::Key;
44
45// Explicit instantiations for the core proxy templates.
46template class LLVM_EXPORT_TEMPLATE AllAnalysesOn<LazyCallGraph::SCC>;
47template class LLVM_EXPORT_TEMPLATE
48 AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
49template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
50 LazyCallGraph &, CGSCCUpdateResult &>;
51template class LLVM_EXPORT_TEMPLATE
52 InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
53template class LLVM_EXPORT_TEMPLATE OuterAnalysisManagerProxy<
54 ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;
55template class LLVM_EXPORT_TEMPLATE
56 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 LargestCGSCC.updateMax(V: C->size());
88
89 PreservedAnalyses PassPA = Pass->run(IR&: *C, AM, ExtraArgs&: G, ExtraArgs&: UR);
90
91 // Update the SCC if necessary.
92 C = UR.UpdatedC ? UR.UpdatedC : C;
93 if (UR.UpdatedC) {
94 // If C is updated, also create a proxy and update FAM inside the result.
95 auto *ResultFAMCP =
96 &AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: *C, ExtraArgs&: G);
97 ResultFAMCP->updateFAM(FAM);
98 }
99
100 // Intersect the final preserved analyses to compute the aggregate
101 // preserved set for this pass manager.
102 PA.intersect(Arg: PassPA);
103
104 // If the CGSCC pass wasn't able to provide a valid updated SCC, the
105 // current SCC may simply need to be skipped if invalid.
106 if (UR.InvalidatedSCCs.count(Ptr: C)) {
107 PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass: *Pass, PA: PassPA);
108 LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
109 break;
110 }
111
112 // Check that we didn't miss any update scenario.
113 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
114
115 // Update the analysis manager as each pass runs and potentially
116 // invalidates analyses.
117 AM.invalidate(IR&: *C, PA: PassPA);
118
119 PI.runAfterPass<LazyCallGraph::SCC>(Pass: *Pass, IR: *C, PA: PassPA);
120 }
121
122 // Before we mark all of *this* SCC's analyses as preserved below, intersect
123 // this with the cross-SCC preserved analysis set. This is used to allow
124 // CGSCC passes to mutate ancestor SCCs and still trigger proper invalidation
125 // for them.
126 UR.CrossSCCPA.intersect(Arg: PA);
127
128 // Invalidation was handled after each pass in the above loop for the current
129 // SCC. Therefore, the remaining analysis results in the AnalysisManager are
130 // preserved. We mark this with a set so that we don't need to inspect each
131 // one individually.
132 PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
133
134 return PA;
135}
136
137PreservedAnalyses
138ModuleToPostOrderCGSCCPassAdaptor::run(Module &M, ModuleAnalysisManager &AM) {
139 // Setup the CGSCC analysis manager from its proxy.
140 CGSCCAnalysisManager &CGAM =
141 AM.getResult<CGSCCAnalysisManagerModuleProxy>(IR&: M).getManager();
142
143 // Get the call graph for this module.
144 LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(IR&: M);
145
146 // Get Function analysis manager from its proxy.
147 FunctionAnalysisManager &FAM =
148 AM.getCachedResult<FunctionAnalysisManagerModuleProxy>(IR&: M)->getManager();
149
150 // We keep worklists to allow us to push more work onto the pass manager as
151 // the passes are run.
152 SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
153 SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
154
155 // Keep sets for invalidated SCCs that should be skipped when
156 // iterating off the worklists.
157 SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
158
159 SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
160 InlinedInternalEdges;
161
162 SmallVector<Function *, 4> DeadFunctions;
163
164 CGSCCUpdateResult UR = {.CWorklist: CWorklist,
165 .InvalidatedSCCs: InvalidSCCSet,
166 .UpdatedC: nullptr,
167 .CrossSCCPA: PreservedAnalyses::all(),
168 .InlinedInternalEdges: InlinedInternalEdges,
169 .DeadFunctions: DeadFunctions,
170 .IndirectVHs: {}};
171
172 // Request PassInstrumentation from analysis manager, will use it to run
173 // instrumenting callbacks for the passes later.
174 PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(IR&: M);
175
176 PreservedAnalyses PA = PreservedAnalyses::all();
177 CG.buildRefSCCs();
178 for (LazyCallGraph::RefSCC &RC :
179 llvm::make_early_inc_range(Range: CG.postorder_ref_sccs())) {
180 assert(RCWorklist.empty() &&
181 "Should always start with an empty RefSCC worklist");
182 // The postorder_ref_sccs range we are walking is lazily constructed, so
183 // we only push the first one onto the worklist. The worklist allows us
184 // to capture *new* RefSCCs created during transformations.
185 //
186 // We really want to form RefSCCs lazily because that makes them cheaper
187 // to update as the program is simplified and allows us to have greater
188 // cache locality as forming a RefSCC touches all the parts of all the
189 // functions within that RefSCC.
190 //
191 // We also eagerly increment the iterator to the next position because
192 // the CGSCC passes below may delete the current RefSCC.
193 RCWorklist.insert(X: &RC);
194
195 do {
196 LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
197 assert(CWorklist.empty() &&
198 "Should always start with an empty SCC worklist");
199
200 LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
201 << "\n");
202
203 // The top of the worklist may *also* be the same SCC we just ran over
204 // (and invalidated for). Keep track of that last SCC we processed due
205 // to SCC update to avoid redundant processing when an SCC is both just
206 // updated itself and at the top of the worklist.
207 LazyCallGraph::SCC *LastUpdatedC = nullptr;
208
209 // Push the initial SCCs in reverse post-order as we'll pop off the
210 // back and so see this in post-order.
211 for (LazyCallGraph::SCC &C : llvm::reverse(C&: *RC))
212 CWorklist.insert(X: &C);
213
214 do {
215 LazyCallGraph::SCC *C = CWorklist.pop_back_val();
216 // Due to call graph mutations, we may have invalid SCCs or SCCs from
217 // other RefSCCs in the worklist. The invalid ones are dead and the
218 // other RefSCCs should be queued above, so we just need to skip both
219 // scenarios here.
220 if (InvalidSCCSet.count(Ptr: C)) {
221 LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
222 continue;
223 }
224 if (LastUpdatedC == C) {
225 LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n");
226 continue;
227 }
228 // We used to also check if the current SCC is part of the current
229 // RefSCC and bail if it wasn't, since it should be in RCWorklist.
230 // However, this can cause compile time explosions in some cases on
231 // modules with a huge RefSCC. If a non-trivial amount of SCCs in the
232 // huge RefSCC can become their own child RefSCC, we create one child
233 // RefSCC, bail on the current RefSCC, visit the child RefSCC, revisit
234 // the huge RefSCC, and repeat. By visiting all SCCs in the original
235 // RefSCC we create all the child RefSCCs in one pass of the RefSCC,
236 // rather one pass of the RefSCC creating one child RefSCC at a time.
237
238 // Ensure we can proxy analysis updates from the CGSCC analysis manager
239 // into the Function analysis manager by getting a proxy here.
240 // This also needs to update the FunctionAnalysisManager, as this may be
241 // the first time we see this SCC.
242 CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: *C, ExtraArgs&: CG).updateFAM(
243 FAM);
244
245 // Each time we visit a new SCC pulled off the worklist,
246 // a transformation of a child SCC may have also modified this parent
247 // and invalidated analyses. So we invalidate using the update record's
248 // cross-SCC preserved set. This preserved set is intersected by any
249 // CGSCC pass that handles invalidation (primarily pass managers) prior
250 // to marking its SCC as preserved. That lets us track everything that
251 // might need invalidation across SCCs without excessive invalidations
252 // on a single SCC.
253 //
254 // This essentially allows SCC passes to freely invalidate analyses
255 // of any ancestor SCC. If this becomes detrimental to successfully
256 // caching analyses, we could force each SCC pass to manually
257 // invalidate the analyses for any SCCs other than themselves which
258 // are mutated. However, that seems to lose the robustness of the
259 // pass-manager driven invalidation scheme.
260 CGAM.invalidate(IR&: *C, PA: UR.CrossSCCPA);
261
262 do {
263 // Check that we didn't miss any update scenario.
264 assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
265 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
266
267 LastUpdatedC = UR.UpdatedC;
268 UR.UpdatedC = nullptr;
269
270 // Check the PassInstrumentation's BeforePass callbacks before
271 // running the pass, skip its execution completely if asked to
272 // (callback returns false).
273 if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass: *Pass, IR: *C))
274 continue;
275
276 PreservedAnalyses PassPA = Pass->run(IR&: *C, AM&: CGAM, ExtraArgs&: CG, ExtraArgs&: UR);
277
278 // Update the SCC and RefSCC if necessary.
279 C = UR.UpdatedC ? UR.UpdatedC : C;
280
281 if (UR.UpdatedC) {
282 // If we're updating the SCC, also update the FAM inside the proxy's
283 // result.
284 CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: *C, ExtraArgs&: CG).updateFAM(
285 FAM);
286 }
287
288 // Intersect with the cross-SCC preserved set to capture any
289 // cross-SCC invalidation.
290 UR.CrossSCCPA.intersect(Arg: PassPA);
291 // Intersect the preserved set so that invalidation of module
292 // analyses will eventually occur when the module pass completes.
293 PA.intersect(Arg: PassPA);
294
295 // If the CGSCC pass wasn't able to provide a valid updated SCC,
296 // the current SCC may simply need to be skipped if invalid.
297 if (UR.InvalidatedSCCs.count(Ptr: C)) {
298 PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass: *Pass, PA: PassPA);
299 LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
300 break;
301 }
302
303 // Check that we didn't miss any update scenario.
304 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
305
306 // We handle invalidating the CGSCC analysis manager's information
307 // for the (potentially updated) SCC here. Note that any other SCCs
308 // whose structure has changed should have been invalidated by
309 // whatever was updating the call graph. This SCC gets invalidated
310 // late as it contains the nodes that were actively being
311 // processed.
312 CGAM.invalidate(IR&: *C, PA: PassPA);
313
314 PI.runAfterPass<LazyCallGraph::SCC>(Pass: *Pass, IR: *C, PA: PassPA);
315
316 // The pass may have restructured the call graph and refined the
317 // current SCC and/or RefSCC. We need to update our current SCC and
318 // RefSCC pointers to follow these. Also, when the current SCC is
319 // refined, re-run the SCC pass over the newly refined SCC in order
320 // to observe the most precise SCC model available. This inherently
321 // cannot cycle excessively as it only happens when we split SCCs
322 // apart, at most converging on a DAG of single nodes.
323 // FIXME: If we ever start having RefSCC passes, we'll want to
324 // iterate there too.
325 if (UR.UpdatedC)
326 LLVM_DEBUG(dbgs()
327 << "Re-running SCC passes after a refinement of the "
328 "current SCC: "
329 << *UR.UpdatedC << "\n");
330
331 // Note that both `C` and `RC` may at this point refer to deleted,
332 // invalid SCC and RefSCCs respectively. But we will short circuit
333 // the processing when we check them in the loop above.
334 } while (UR.UpdatedC);
335 } while (!CWorklist.empty());
336
337 // We only need to keep internal inlined edge information within
338 // a RefSCC, clear it to save on space and let the next time we visit
339 // any of these functions have a fresh start.
340 InlinedInternalEdges.clear();
341 } while (!RCWorklist.empty());
342 }
343
344 CG.removeDeadFunctions(DeadFs: DeadFunctions);
345 for (Function *DeadF : DeadFunctions)
346 DeadF->eraseFromParent();
347
348#if defined(EXPENSIVE_CHECKS)
349 // Verify that the call graph is still valid.
350 CG.verify();
351#endif
352
353 // By definition we preserve the call garph, all SCC analyses, and the
354 // analysis proxies by handling them above and in any nested pass managers.
355 PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
356 PA.preserve<LazyCallGraphAnalysis>();
357 PA.preserve<CGSCCAnalysisManagerModuleProxy>();
358 PA.preserve<FunctionAnalysisManagerModuleProxy>();
359 return PA;
360}
361
362PreservedAnalyses DevirtSCCRepeatedPass::run(LazyCallGraph::SCC &InitialC,
363 CGSCCAnalysisManager &AM,
364 LazyCallGraph &CG,
365 CGSCCUpdateResult &UR) {
366 PreservedAnalyses PA = PreservedAnalyses::all();
367 PassInstrumentation PI =
368 AM.getResult<PassInstrumentationAnalysis>(IR&: InitialC, ExtraArgs&: CG);
369
370 // The SCC may be refined while we are running passes over it, so set up
371 // a pointer that we can update.
372 LazyCallGraph::SCC *C = &InitialC;
373
374 // Struct to track the counts of direct and indirect calls in each function
375 // of the SCC.
376 struct CallCount {
377 int Direct;
378 int Indirect;
379 };
380
381 // Put value handles on all of the indirect calls and return the number of
382 // direct calls for each function in the SCC.
383 auto ScanSCC = [](LazyCallGraph::SCC &C,
384 SmallMapVector<Value *, WeakTrackingVH, 16> &CallHandles) {
385 assert(CallHandles.empty() && "Must start with a clear set of handles.");
386
387 SmallDenseMap<LazyCallGraph::Node *, CallCount> CallCounts;
388 CallCount CountLocal = {.Direct: 0, .Indirect: 0};
389 for (LazyCallGraph::Node &N : C) {
390 CallCount &Count =
391 CallCounts.insert(KV: std::make_pair(x: &N, y&: CountLocal)).first->second;
392 for (Instruction &I : instructions(F&: N.getFunction()))
393 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
394 if (CB->getCalledFunction()) {
395 ++Count.Direct;
396 } else {
397 ++Count.Indirect;
398 CallHandles.insert(KV: {CB, WeakTrackingVH(CB)});
399 }
400 }
401 }
402
403 return CallCounts;
404 };
405
406 UR.IndirectVHs.clear();
407 // Populate the initial call handles and get the initial call counts.
408 auto CallCounts = ScanSCC(*C, UR.IndirectVHs);
409
410 for (int Iteration = 0;; ++Iteration) {
411 if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass: *Pass, IR: *C))
412 continue;
413
414 PreservedAnalyses PassPA = Pass->run(IR&: *C, AM, ExtraArgs&: CG, ExtraArgs&: UR);
415
416 PA.intersect(Arg: PassPA);
417
418 // If the CGSCC pass wasn't able to provide a valid updated SCC, the
419 // current SCC may simply need to be skipped if invalid.
420 if (UR.InvalidatedSCCs.count(Ptr: C)) {
421 PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass: *Pass, PA: PassPA);
422 LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
423 break;
424 }
425
426 // Update the analysis manager with each run and intersect the total set
427 // of preserved analyses so we're ready to iterate.
428 AM.invalidate(IR&: *C, PA: PassPA);
429
430 PI.runAfterPass<LazyCallGraph::SCC>(Pass: *Pass, IR: *C, PA: PassPA);
431
432 // If the SCC structure has changed, bail immediately and let the outer
433 // CGSCC layer handle any iteration to reflect the refined structure.
434 if (UR.UpdatedC && UR.UpdatedC != C)
435 break;
436
437 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
438
439 // Check whether any of the handles were devirtualized.
440 bool Devirt = llvm::any_of(Range&: UR.IndirectVHs, P: [](auto &P) -> bool {
441 if (P.second) {
442 if (CallBase *CB = dyn_cast<CallBase>(P.second)) {
443 if (CB->getCalledFunction()) {
444 LLVM_DEBUG(dbgs() << "Found devirtualized call: " << *CB << "\n");
445 return true;
446 }
447 }
448 }
449 return false;
450 });
451
452 // Rescan to build up a new set of handles and count how many direct
453 // calls remain. If we decide to iterate, this also sets up the input to
454 // the next iteration.
455 UR.IndirectVHs.clear();
456 auto NewCallCounts = ScanSCC(*C, UR.IndirectVHs);
457
458 // If we haven't found an explicit devirtualization already see if we
459 // have decreased the number of indirect calls and increased the number
460 // of direct calls for any function in the SCC. This can be fooled by all
461 // manner of transformations such as DCE and other things, but seems to
462 // work well in practice.
463 if (!Devirt)
464 // Iterate over the keys in NewCallCounts, if the node also exists in
465 // CallCounts, make the check below.
466 for (auto &Pair : NewCallCounts) {
467 auto &CallCountNew = Pair.second;
468 auto CountIt = CallCounts.find(Val: Pair.first);
469 if (CountIt != CallCounts.end()) {
470 const auto &CallCountOld = CountIt->second;
471 if (CallCountOld.Indirect > CallCountNew.Indirect &&
472 CallCountOld.Direct < CallCountNew.Direct) {
473 Devirt = true;
474 break;
475 }
476 }
477 }
478
479 if (!Devirt) {
480 break;
481 }
482
483 // Otherwise, if we've already hit our max, we're done.
484 if (Iteration >= MaxIterations) {
485 if (getAnalysisOptions(F: C->begin()->getFunction())
486 .abort_on_max_devirt_iterations_reached)
487 report_fatal_error(reason: "Max devirtualization iterations reached");
488 LLVM_DEBUG(
489 dbgs() << "Found another devirtualization after hitting the max "
490 "number of repetitions ("
491 << MaxIterations << ") on SCC: " << *C << "\n");
492 break;
493 }
494
495 LLVM_DEBUG(
496 dbgs() << "Repeating an SCC pass after finding a devirtualization in: "
497 << *C << "\n");
498
499 // Move over the new call counts in preparation for iterating.
500 CallCounts = std::move(NewCallCounts);
501 }
502
503 // Note that we don't add any preserved entries here unlike a more normal
504 // "pass manager" because we only handle invalidation *between* iterations,
505 // not after the last iteration.
506 return PA;
507}
508
509PreservedAnalyses CGSCCToFunctionPassAdaptor::run(LazyCallGraph::SCC &C,
510 CGSCCAnalysisManager &AM,
511 LazyCallGraph &CG,
512 CGSCCUpdateResult &UR) {
513 // Setup the function analysis manager from its proxy.
514 FunctionAnalysisManager &FAM =
515 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: CG).getManager();
516
517 SmallVector<LazyCallGraph::Node *, 4> Nodes(llvm::make_pointer_range(Range&: C));
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 PromotedRefTargets.insert_range(R&: NewCallEdges);
1072
1073 // Now promote ref edges into call edges.
1074 for (Node *CallTarget : PromotedRefTargets) {
1075 SCC &TargetC = *G.lookupSCC(N&: *CallTarget);
1076 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1077
1078 // The easy case is when the target RefSCC is not this RefSCC. This is
1079 // only supported when the target RefSCC is a child of this RefSCC.
1080 if (&TargetRC != RC) {
1081#ifdef EXPENSIVE_CHECKS
1082 assert(RC->isAncestorOf(TargetRC) &&
1083 "Cannot potentially form RefSCC cycles here!");
1084#endif
1085 RC->switchOutgoingEdgeToCall(SourceN&: N, TargetN&: *CallTarget);
1086 LLVM_DEBUG(dbgs() << "Switch outgoing ref edge to a call edge from '" << N
1087 << "' to '" << *CallTarget << "'\n");
1088 continue;
1089 }
1090 LLVM_DEBUG(dbgs() << "Switch an internal ref edge to a call edge from '"
1091 << N << "' to '" << *CallTarget << "'\n");
1092
1093 // Otherwise we are switching an internal ref edge to a call edge. This
1094 // may merge away some SCCs, and we add those to the UpdateResult. We also
1095 // need to make sure to update the worklist in the event SCCs have moved
1096 // before the current one in the post-order sequence
1097 bool HasFunctionAnalysisProxy = false;
1098 auto InitialSCCIndex = RC->find(C&: *C) - RC->begin();
1099 bool FormedCycle = RC->switchInternalEdgeToCall(
1100 SourceN&: N, TargetN&: *CallTarget, MergeCB: [&](ArrayRef<SCC *> MergedSCCs) {
1101 for (SCC *MergedC : MergedSCCs) {
1102 assert(MergedC != &TargetC && "Cannot merge away the target SCC!");
1103
1104 HasFunctionAnalysisProxy |=
1105 AM.getCachedResult<FunctionAnalysisManagerCGSCCProxy>(
1106 IR&: *MergedC) != nullptr;
1107
1108 // Mark that this SCC will no longer be valid.
1109 UR.InvalidatedSCCs.insert(Ptr: MergedC);
1110
1111 // FIXME: We should really do a 'clear' here to forcibly release
1112 // memory, but we don't have a good way of doing that and
1113 // preserving the function analyses.
1114 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1115 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1116 AM.invalidate(IR&: *MergedC, PA);
1117 }
1118 });
1119
1120 // If we formed a cycle by creating this call, we need to update more data
1121 // structures.
1122 if (FormedCycle) {
1123 C = &TargetC;
1124 assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
1125
1126 // If one of the invalidated SCCs had a cached proxy to a function
1127 // analysis manager, we need to create a proxy in the new current SCC as
1128 // the invalidated SCCs had their functions moved.
1129 if (HasFunctionAnalysisProxy)
1130 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: *C, ExtraArgs&: G).updateFAM(FAM);
1131
1132 // Any analyses cached for this SCC are no longer precise as the shape
1133 // has changed by introducing this cycle. However, we have taken care to
1134 // update the proxies so it remains valide.
1135 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1136 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1137 AM.invalidate(IR&: *C, PA);
1138 }
1139 auto NewSCCIndex = RC->find(C&: *C) - RC->begin();
1140 // If we have actually moved an SCC to be topologically "below" the current
1141 // one due to merging, we will need to revisit the current SCC after
1142 // visiting those moved SCCs.
1143 //
1144 // It is critical that we *do not* revisit the current SCC unless we
1145 // actually move SCCs in the process of merging because otherwise we may
1146 // form a cycle where an SCC is split apart, merged, split, merged and so
1147 // on infinitely.
1148 if (InitialSCCIndex < NewSCCIndex) {
1149 // Put our current SCC back onto the worklist as we'll visit other SCCs
1150 // that are now definitively ordered prior to the current one in the
1151 // post-order sequence, and may end up observing more precise context to
1152 // optimize the current SCC.
1153 UR.CWorklist.insert(X: C);
1154 LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist: " << *C
1155 << "\n");
1156 // Enqueue in reverse order as we pop off the back of the worklist.
1157 for (SCC &MovedC : llvm::reverse(C: make_range(x: RC->begin() + InitialSCCIndex,
1158 y: RC->begin() + NewSCCIndex))) {
1159 UR.CWorklist.insert(X: &MovedC);
1160 LLVM_DEBUG(dbgs() << "Enqueuing a newly earlier in post-order SCC: "
1161 << MovedC << "\n");
1162 }
1163 }
1164 }
1165
1166 assert(!UR.InvalidatedSCCs.count(C) && "Invalidated the current SCC!");
1167 assert(&C->getOuterRefSCC() == RC && "Current SCC not in current RefSCC!");
1168
1169 // Record the current SCC for higher layers of the CGSCC pass manager now that
1170 // all the updates have been applied.
1171 if (C != &InitialC)
1172 UR.UpdatedC = C;
1173
1174 return *C;
1175}
1176
1177LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(
1178 LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
1179 CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,
1180 FunctionAnalysisManager &FAM) {
1181 return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM,
1182 /* FunctionPass */ true);
1183}
1184LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForCGSCCPass(
1185 LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
1186 CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,
1187 FunctionAnalysisManager &FAM) {
1188 return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM,
1189 /* FunctionPass */ false);
1190}
1191