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