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