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