32#define DEBUG_TYPE "cgscc"
40 "abort-on-max-devirt-iterations-reached",
41 cl::desc(
"Abort when the max iterations for devirtualization CGSCC repeat "
93 ResultFAMCP->updateFAM(
FAM);
104 LLVM_DEBUG(
dbgs() <<
"Skipping invalidated root or island SCC!\n");
109 assert(
C->begin() !=
C->end() &&
"Cannot have an empty SCC!");
156 InlinedInternalEdges;
164 InlinedInternalEdges,
177 "Should always start with an empty RefSCC worklist");
194 "Should always start with an empty SCC worklist");
196 LLVM_DEBUG(
dbgs() <<
"Running an SCC pass across the RefSCC: " << *RC
216 if (InvalidSCCSet.
count(
C)) {
220 if (LastUpdatedC ==
C) {
260 assert(!InvalidSCCSet.
count(
C) &&
"Processing an invalid SCC!");
261 assert(
C->begin() !=
C->end() &&
"Cannot have an empty SCC!");
289 PA.intersect(PassPA);
295 LLVM_DEBUG(
dbgs() <<
"Skipping invalidated root or island SCC!\n");
300 assert(
C->begin() !=
C->end() &&
"Cannot have an empty SCC!");
323 <<
"Re-running SCC passes after a refinement of the "
331 }
while (!CWorklist.
empty());
336 InlinedInternalEdges.
clear();
337 }
while (!RCWorklist.
empty());
341 for (
Function *DeadF : DeadFunctions)
342 DeadF->eraseFromParent();
344#if defined(EXPENSIVE_CHECKS)
381 assert(CallHandles.empty() &&
"Must start with a clear set of handles.");
384 CallCount CountLocal = {0, 0};
387 CallCounts.
insert(std::make_pair(&
N.getFunction(), CountLocal))
390 if (
auto *CB = dyn_cast<CallBase>(&
I)) {
391 if (CB->getCalledFunction()) {
407 for (
int Iteration = 0;; ++Iteration) {
419 LLVM_DEBUG(
dbgs() <<
"Skipping invalidated root or island SCC!\n");
434 assert(
C->begin() !=
C->end() &&
"Cannot have an empty SCC!");
439 if (CallBase *CB = dyn_cast<CallBase>(P.second)) {
440 if (CB->getCalledFunction()) {
441 LLVM_DEBUG(dbgs() <<
"Found devirtualized call: " << *CB <<
"\n");
463 for (
auto &Pair : NewCallCounts) {
464 auto &CallCountNew = Pair.second;
465 auto CountIt = CallCounts.find(Pair.first);
466 if (CountIt != CallCounts.end()) {
467 const auto &CallCountOld = CountIt->second;
468 if (CallCountOld.Indirect > CallCountNew.Indirect &&
469 CallCountOld.Direct < CallCountNew.Direct) {
481 if (Iteration >= MaxIterations) {
485 dbgs() <<
"Found another devirtualization after hitting the max "
486 "number of repetitions ("
487 << MaxIterations <<
") on SCC: " << *
C <<
"\n");
492 dbgs() <<
"Repeating an SCC pass after finding a devirtualization in: "
496 CallCounts = std::move(NewCallCounts);
522 LLVM_DEBUG(
dbgs() <<
"Running function passes across an SCC: " <<
C <<
"\n");
562 "Current SCC not updated to the SCC containing the current node!");
579bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(
608 bool AreSCCAnalysesPreserved =
613 for (
auto &RC :
G->postorder_ref_sccs())
615 std::optional<PreservedAnalyses> InnerPA;
620 if (
auto *OuterProxy =
622 for (
const auto &OuterInvalidationPair :
623 OuterProxy->getOuterInvalidations()) {
624 AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
625 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
629 for (
AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
630 InnerPA->
abandon(InnerAnalysisID);
637 InnerAM->invalidate(
C, *InnerPA);
643 if (!AreSCCAnalysesPreserved)
644 InnerAM->invalidate(
C, PA);
673 Module &M = *
C.begin()->getFunction().getParent();
677 "The CGSCC pass manager requires that the FAM module proxy is run "
678 "on the module prior to entering the CGSCC walk");
711 bool AreFunctionAnalysesPreserved =
718 std::optional<PreservedAnalyses> FunctionPA;
723 if (
auto *OuterProxy =
725 for (
const auto &OuterInvalidationPair :
726 OuterProxy->getOuterInvalidations()) {
727 AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
728 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
732 for (
AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
733 FunctionPA->
abandon(InnerAnalysisID);
746 if (!AreFunctionAnalysesPreserved)
789 for (
const auto &OuterInvalidationPair :
790 OuterProxy->getOuterInvalidations()) {
791 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
792 for (
AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
793 PA.abandon(InnerAnalysisID);
811template <
typename SCCRangeT>
818 if (NewSCCRange.empty())
823 LLVM_DEBUG(
dbgs() <<
"Enqueuing the existing SCC in the worklist:" << *
C
830 assert(
C != &*NewSCCRange.begin() &&
831 "Cannot insert new SCCs without changing current SCC!");
832 C = &*NewSCCRange.begin();
833 assert(
G.lookupSCC(
N) ==
C &&
"Failed to update current SCC!");
840 FAM = &FAMProxy->getManager();
849 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
858 assert(
C != &NewC &&
"No need to re-visit the current SCC!");
859 assert(OldC != &NewC &&
"Already handled the original SCC!");
861 LLVM_DEBUG(
dbgs() <<
"Enqueuing a newly formed SCC:" << NewC <<
"\n");
885 RefSCC *RC = &InitialRC;
902 if (
auto *CB = dyn_cast<CallBase>(&
I)) {
903 if (
Function *Callee = CB->getCalledFunction()) {
904 if (Visited.
insert(Callee).second && !Callee->isDeclaration()) {
905 Node *CalleeN =
G.lookup(*Callee);
907 "Visited function should already have an associated node");
908 Edge *E =
N->lookup(*CalleeN);
910 "No function transformations should introduce *new* "
911 "call edges! Any new calls should be modeled as "
912 "promoted existing ref edges!");
913 bool Inserted = RetainedEdges.
insert(CalleeN).second;
915 assert(Inserted &&
"We should never visit a function twice.");
917 NewCallEdges.
insert(CalleeN);
918 else if (!E->isCall())
919 PromotedRefTargets.
insert(CalleeN);
927 else if (!Entry->second)
935 for (
Value *
Op :
I.operand_values())
936 if (
auto *OpC = dyn_cast<Constant>(
Op))
937 if (Visited.
insert(OpC).second)
940 auto VisitRef = [&](
Function &Referee) {
941 Node *RefereeN =
G.lookup(Referee);
943 "Visited function should already have an associated node");
944 Edge *E =
N->lookup(*RefereeN);
946 "No function transformations should introduce *new* ref "
947 "edges! Any new ref edges would require IPO which "
948 "function passes aren't allowed to do!");
949 bool Inserted = RetainedEdges.
insert(RefereeN).second;
951 assert(Inserted &&
"We should never visit a function twice.");
953 NewRefEdges.
insert(RefereeN);
954 else if (E->isCall())
955 DemotedCallTargets.
insert(RefereeN);
960 for (
Node *RefTarget : NewRefEdges) {
961 SCC &TargetC = *
G.lookupSCC(*RefTarget);
962 RefSCC &TargetRC = TargetC.getOuterRefSCC();
965#ifdef EXPENSIVE_CHECKS
966 assert((RC == &TargetRC ||
967 RC->isAncestorOf(TargetRC)) &&
"New ref edge is not trivial!");
969 RC->insertTrivialRefEdge(
N, *RefTarget);
973 for (
Node *CallTarget : NewCallEdges) {
974 SCC &TargetC = *
G.lookupSCC(*CallTarget);
975 RefSCC &TargetRC = TargetC.getOuterRefSCC();
978#ifdef EXPENSIVE_CHECKS
979 assert((RC == &TargetRC ||
980 RC->isAncestorOf(TargetRC)) &&
"New call edge is not trivial!");
984 RC->insertTrivialRefEdge(
N, *CallTarget);
988 for (
auto *LibFn :
G.getLibFunctions())
991 if (!Visited.
count(LibFn))
999 if (RetainedEdges.
count(&E.getNode()))
1002 SCC &TargetC = *
G.lookupSCC(E.getNode());
1003 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1004 if (&TargetRC == RC && E.isCall()) {
1005 if (
C != &TargetC) {
1007 RC->switchTrivialInternalEdgeToRef(
N, E.getNode());
1020 SCC &TargetC = *
G.lookupSCC(*TargetN);
1021 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1025 if (&TargetRC == RC)
1029 << *TargetN <<
"'\n");
1030 RC->removeOutgoingEdge(
N, *TargetN);
1037 for (
Node *RefTarget : DemotedCallTargets) {
1038 SCC &TargetC = *
G.lookupSCC(*RefTarget);
1039 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1043 if (&TargetRC != RC) {
1044#ifdef EXPENSIVE_CHECKS
1045 assert(RC->isAncestorOf(TargetRC) &&
1046 "Cannot potentially form RefSCC cycles here!");
1048 RC->switchOutgoingEdgeToRef(
N, *RefTarget);
1049 LLVM_DEBUG(
dbgs() <<
"Switch outgoing call edge to a ref edge from '" <<
N
1050 <<
"' to '" << *RefTarget <<
"'\n");
1056 if (
C != &TargetC) {
1058 RC->switchTrivialInternalEdgeToRef(
N, *RefTarget);
1069 for (
Node *E : NewCallEdges)
1070 PromotedRefTargets.
insert(E);
1073 for (
Node *CallTarget : PromotedRefTargets) {
1074 SCC &TargetC = *
G.lookupSCC(*CallTarget);
1075 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1079 if (&TargetRC != RC) {
1080#ifdef EXPENSIVE_CHECKS
1081 assert(RC->isAncestorOf(TargetRC) &&
1082 "Cannot potentially form RefSCC cycles here!");
1084 RC->switchOutgoingEdgeToCall(
N, *CallTarget);
1085 LLVM_DEBUG(
dbgs() <<
"Switch outgoing ref edge to a call edge from '" <<
N
1086 <<
"' to '" << *CallTarget <<
"'\n");
1089 LLVM_DEBUG(
dbgs() <<
"Switch an internal ref edge to a call edge from '"
1090 <<
N <<
"' to '" << *CallTarget <<
"'\n");
1096 bool HasFunctionAnalysisProxy =
false;
1097 auto InitialSCCIndex = RC->find(*
C) - RC->begin();
1098 bool FormedCycle = RC->switchInternalEdgeToCall(
1100 for (SCC *MergedC : MergedSCCs) {
1101 assert(MergedC != &TargetC &&
"Cannot merge away the target SCC!");
1103 HasFunctionAnalysisProxy |=
1105 *MergedC) !=
nullptr;
1113 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1123 assert(
G.lookupSCC(
N) ==
C &&
"Failed to update current SCC!");
1128 if (HasFunctionAnalysisProxy)
1134 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1138 auto NewSCCIndex = RC->find(*
C) - RC->begin();
1147 if (InitialSCCIndex < NewSCCIndex) {
1153 LLVM_DEBUG(
dbgs() <<
"Enqueuing the existing SCC in the worklist: " << *
C
1157 RC->begin() + NewSCCIndex))) {
1159 LLVM_DEBUG(
dbgs() <<
"Enqueuing a newly earlier in post-order SCC: "
1166 assert(&
C->getOuterRefSCC() == RC &&
"Current SCC not in current RefSCC!");
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.
This header defines various interfaces for pass management in LLVM.
Implements a lazy call graph analysis and related passes for the new pass manager.
CGSCCAnalysisManager CGAM
Function const char * Passes
FunctionAnalysisManager FAM
Provides implementations for PassManager and AnalysisManager template methods.
This file provides a priority worklist.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file 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....
API to communicate dependencies between analyses during invalidation.
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
A container for analyses that lazily runs them and caches their results.
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.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
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)
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.
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Result run(IRUnitT &IR, AnalysisManager< IRUnitT, ExtraArgTs... > &AM, ExtraArgTs...)
Run the analysis pass and create our proxy result object.
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.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Pseudo-analysis pass that exposes the PassInstrumentation to pass managers.
This class provides instrumentation entry points for the Pass Manager, doing calls to callbacks regis...
void runAfterPassInvalidated(const PassT &Pass, const PreservedAnalyses &PA) const
AfterPassInvalidated instrumentation point - takes Pass instance that has just been executed.
void runAfterPass(const PassT &Pass, const IRUnitT &IR, const PreservedAnalyses &PA) const
AfterPass instrumentation point - takes Pass instance that has just been executed and constant refere...
bool runBeforePass(const PassT &Pass, const IRUnitT &IR) const
BeforePass instrumentation point - takes Pass instance to be executed and constant reference to IR it...
Manages a sequence of passes over a particular unit of IR.
Pass interface - Implemented by all 'passes'.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
bool areAllPreserved() const
Test whether all analyses are preserved (and none are abandoned).
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
bool allAnalysesInSetPreserved() const
Directly test whether a set of analyses is preserved.
void intersect(const PreservedAnalyses &Arg)
Intersect this set with another in place.
void preserveSet()
Mark an analysis set as preserved.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
void abandon()
Mark an analysis as abandoned.
void preserve()
Mark an analysis as preserved.
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.
Implements a dense probed hash-table based set with some number of buckets stored inline.
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.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
LLVM Value Representation.
Value handle that is nullable, but tries to track the Value.
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.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
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...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
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...
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
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"))
A special type used by analysis passes to provide an address that identifies that particular analysis...
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
SmallMapVector< Value *, WeakTrackingVH, 16 > IndirectVHs
Weak VHs to keep track of indirect calls for the purposes of detecting devirtualization.
SmallPriorityWorklist< LazyCallGraph::SCC *, 1 > & CWorklist
Worklist of the SCCs queued for processing.
SmallPtrSetImpl< LazyCallGraph::SCC * > & InvalidatedSCCs
The set of invalidated SCCs which should be skipped if they are found in CWorklist.
LazyCallGraph::SCC * UpdatedC
If non-null, the updated current SCC being processed.
PreservedAnalyses CrossSCCPA
Preserved analyses across SCCs.
A MapVector that performs no allocations if smaller than a certain size.