Lines Matching defs:SCC
49 template class AllAnalysesOn<LazyCallGraph::SCC>;
50 template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
51 template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
55 LazyCallGraph::SCC, LazyCallGraph &>;
62 PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
63 CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
73 // The SCC may be refined while we are running passes over it, so set up
75 LazyCallGraph::SCC *C = &InitialC;
89 // Update the SCC if necessary.
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.
105 PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);
106 LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
111 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
117 PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
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
127 // SCC. Therefore, the remaining analysis results in the AnalysisManager are
130 PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
151 SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
155 SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
157 SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
196 "Should always start with an empty SCC worklist");
198 LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
201 // The top of the worklist may *also* be the same SCC we just ran over
202 // (and invalidated for). Keep track of that last SCC we processed due
203 // to SCC update to avoid redundant processing when an SCC is both just
205 LazyCallGraph::SCC *LastUpdatedC = nullptr;
209 for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
213 LazyCallGraph::SCC *C = CWorklist.pop_back_val();
219 LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
223 LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n");
226 // We used to also check if the current SCC is part of the current
239 // the first time we see this SCC.
243 // Each time we visit a new SCC pulled off the worklist,
244 // a transformation of a child SCC may have also modified this parent
246 // cross-SCC preserved set. This preserved set is intersected by any
248 // to marking its SCC as preserved. That lets us track everything that
250 // on a single SCC.
252 // This essentially allows SCC passes to freely invalidate analyses
253 // of any ancestor SCC. If this becomes detrimental to successfully
254 // caching analyses, we could force each SCC pass to manually
262 assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
263 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
271 if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
276 // Update the SCC and RefSCC if necessary.
280 // If we're updating the SCC, also update the FAM inside the proxy's
286 // Intersect with the cross-SCC preserved set to capture any
287 // cross-SCC invalidation.
293 // If the CGSCC pass wasn't able to provide a valid updated SCC,
294 // the current SCC may simply need to be skipped if invalid.
296 PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);
297 LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
302 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
305 // for the (potentially updated) SCC here. Note that any other SCCs
307 // whatever was updating the call graph. This SCC gets invalidated
312 PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
315 // current SCC and/or RefSCC. We need to update our current SCC and
316 // RefSCC pointers to follow these. Also, when the current SCC is
317 // refined, re-run the SCC pass over the newly refined SCC in order
318 // to observe the most precise SCC model available. This inherently
325 << "Re-running SCC passes after a refinement of the "
326 "current SCC: "
330 // invalid SCC and RefSCCs respectively. But we will short circuit
351 // By definition we preserve the call garph, all SCC analyses, and the
353 PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
360 PreservedAnalyses DevirtSCCRepeatedPass::run(LazyCallGraph::SCC &InitialC,
368 // The SCC may be refined while we are running passes over it, so set up
370 LazyCallGraph::SCC *C = &InitialC;
373 // of the SCC.
380 // direct calls for each function in the SCC.
381 auto ScanSCC = [](LazyCallGraph::SCC &C,
410 if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
417 // If the CGSCC pass wasn't able to provide a valid updated SCC, the
418 // current SCC may simply need to be skipped if invalid.
420 PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);
421 LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
429 PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
431 // If the SCC structure has changed, bail immediately and let the outer
436 assert(C->begin() != C->end() && "Cannot have an empty SCC!");
459 // of direct calls for any function in the SCC. This can be fooled by all
489 << MaxIterations << ") on SCC: " << *C << "\n");
494 dbgs() << "Repeating an SCC pass after finding a devirtualization in: "
507 PreservedAnalyses CGSCCToFunctionPassAdaptor::run(LazyCallGraph::SCC &C,
519 // The SCC may get split while we are optimizing functions due to deleting
520 // edges. If this happens, the current SCC can shift, so keep track of
522 LazyCallGraph::SCC *CurrentC = &C;
524 LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C << "\n");
557 // function pass. This may also update the current SCC to point to
558 // a smaller, more refined SCC.
564 "Current SCC not updated to the SCC containing the current node!");
595 // entire SCC layer as well rather than trying to do invalidation ourselves.
611 PA.allAnalysesInSetPreserved<AllAnalysesOn<LazyCallGraph::SCC>>();
621 // for this SCC.
644 // preserve all SCC analyses.
657 // be accessed in an SCC analysis and proxied onward to function passes.
668 FunctionAnalysisManagerCGSCCProxy::run(LazyCallGraph::SCC &C,
690 LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
705 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) {
723 // SCC-level analysis invalidation that triggers deferred invalidation
758 /// When a new SCC is created for the graph we first update the
761 /// that SCC, two forms of updates are required.
763 /// First, a proxy from the SCC to the FunctionAnalysisManager needs to be
764 /// created so that any subsequent invalidation events to the SCC are
767 /// Second, if any of the functions within the SCC have analysis results with
769 /// *wrong* SCC's analysis result. We forcibly invalidate the necessary
771 static void updateNewSCCFunctionAnalyses(LazyCallGraph::SCC &C,
777 // Now walk the functions in this SCC and invalidate any function analysis
778 // results that might have outer dependencies on an SCC analysis.
807 /// The range of new SCCs must be in postorder already. The SCC they were split
811 /// This function returns the SCC containing \p N. This will be either \p C if
812 /// no new SCCs have been split out, or it will be the new SCC containing \p N.
814 static LazyCallGraph::SCC *
816 LazyCallGraph::Node &N, LazyCallGraph::SCC *C,
818 using SCC = LazyCallGraph::SCC;
823 // Add the current SCC to the worklist as its shape has changed.
825 LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist:" << *C
828 SCC *OldC = C;
830 // Update the current SCC. Note that if we have new SCCs, this must actually
831 // change the SCC.
833 "Cannot insert new SCCs without changing current SCC!");
835 assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
838 // them for each SCC that was split off.
844 // We need to propagate an invalidation call to all but the newly current SCC
855 // Ensure the now-current SCC's function analyses are updated.
859 for (SCC &NewC : llvm::reverse(llvm::drop_begin(NewSCCRange))) {
860 assert(C != &NewC && "No need to re-visit the current SCC!");
861 assert(OldC != &NewC && "Already handled the original SCC!");
863 LLVM_DEBUG(dbgs() << "Enqueuing a newly formed SCC:" << NewC << "\n");
869 // Also propagate a normal invalidation to the new SCC as only the current
876 static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass(
877 LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
882 using SCC = LazyCallGraph::SCC;
886 SCC *C = &InitialC;
963 SCC &TargetC = *G.lookupSCC(*RefTarget);
976 SCC &TargetC = *G.lookupSCC(*CallTarget);
1004 SCC &TargetC = *G.lookupSCC(E.getNode());
1022 SCC &TargetC = *G.lookupSCC(*TargetN);
1040 SCC &TargetC = *G.lookupSCC(*RefTarget);
1076 SCC &TargetC = *G.lookupSCC(*CallTarget);
1101 N, *CallTarget, [&](ArrayRef<SCC *> MergedSCCs) {
1102 for (SCC *MergedC : MergedSCCs) {
1103 assert(MergedC != &TargetC && "Cannot merge away the target SCC!");
1109 // Mark that this SCC will no longer be valid.
1125 assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
1128 // analysis manager, we need to create a proxy in the new current SCC as
1133 // Any analyses cached for this SCC are no longer precise as the shape
1141 // If we have actually moved an SCC to be topologically "below" the current
1142 // one due to merging, we will need to revisit the current SCC after
1145 // It is critical that we *do not* revisit the current SCC unless we
1147 // form a cycle where an SCC is split apart, merged, split, merged and so
1150 // Put our current SCC back onto the worklist as we'll visit other SCCs
1153 // optimize the current SCC.
1155 LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist: " << *C
1158 for (SCC &MovedC : llvm::reverse(make_range(RC->begin() + InitialSCCIndex,
1161 LLVM_DEBUG(dbgs() << "Enqueuing a newly earlier in post-order SCC: "
1167 assert(!UR.InvalidatedSCCs.count(C) && "Invalidated the current SCC!");
1168 assert(&C->getOuterRefSCC() == RC && "Current SCC not in current RefSCC!");
1170 // Record the current SCC for higher layers of the CGSCC pass manager now that
1178 LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(
1179 LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
1185 LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForCGSCCPass(
1186 LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,