34#define DEBUG_TYPE "cgscc"
42 "abort-on-max-devirt-iterations-reached",
43 cl::desc(
"Abort when the max iterations for devirtualization CGSCC repeat "
95 ResultFAMCP->updateFAM(
FAM);
100 PA.intersect(PassPA);
106 LLVM_DEBUG(
dbgs() <<
"Skipping invalidated root or island SCC!\n");
111 assert(
C->begin() !=
C->end() &&
"Cannot have an empty SCC!");
159 InlinedInternalEdges;
162 RCWorklist, CWorklist, InvalidRefSCCSet,
164 InlinedInternalEdges, {}};
175 "Should always start with an empty RefSCC worklist");
191 if (InvalidRefSCCSet.
count(RC)) {
197 "Should always start with an empty SCC worklist");
199 LLVM_DEBUG(
dbgs() <<
"Running an SCC pass across the RefSCC: " << *RC
219 if (InvalidSCCSet.
count(
C)) {
223 if (LastUpdatedC ==
C) {
263 assert(!InvalidSCCSet.
count(
C) &&
"Processing an invalid SCC!");
264 assert(
C->begin() !=
C->end() &&
"Cannot have an empty SCC!");
292 PA.intersect(PassPA);
298 LLVM_DEBUG(
dbgs() <<
"Skipping invalidated root or island SCC!\n");
303 assert(
C->begin() !=
C->end() &&
"Cannot have an empty SCC!");
326 <<
"Re-running SCC passes after a refinement of the "
334 }
while (!CWorklist.
empty());
339 InlinedInternalEdges.
clear();
340 }
while (!RCWorklist.
empty());
375 assert(CallHandles.empty() &&
"Must start with a clear set of handles.");
378 CallCount CountLocal = {0, 0};
381 CallCounts.
insert(std::make_pair(&
N.getFunction(), CountLocal))
384 if (
auto *CB = dyn_cast<CallBase>(&
I)) {
385 if (CB->getCalledFunction()) {
401 for (
int Iteration = 0;; ++Iteration) {
413 LLVM_DEBUG(
dbgs() <<
"Skipping invalidated root or island SCC!\n");
428 assert(
C->begin() !=
C->end() &&
"Cannot have an empty SCC!");
433 if (CallBase *CB = dyn_cast<CallBase>(P.second)) {
434 if (CB->getCalledFunction()) {
435 LLVM_DEBUG(dbgs() <<
"Found devirtualized call: " << *CB <<
"\n");
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) {
475 if (Iteration >= MaxIterations) {
479 dbgs() <<
"Found another devirtualization after hitting the max "
480 "number of repetitions ("
481 << MaxIterations <<
") on SCC: " << *
C <<
"\n");
486 dbgs() <<
"Repeating an SCC pass after finding a devirtualization in: "
490 CallCounts = std::move(NewCallCounts);
516 LLVM_DEBUG(
dbgs() <<
"Running function passes across an SCC: " <<
C <<
"\n");
556 "Current SCC not updated to the SCC containing the current node!");
573bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(
602 bool AreSCCAnalysesPreserved =
607 for (
auto &RC :
G->postorder_ref_sccs())
609 std::optional<PreservedAnalyses> InnerPA;
614 if (
auto *OuterProxy =
616 for (
const auto &OuterInvalidationPair :
617 OuterProxy->getOuterInvalidations()) {
618 AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
619 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
623 for (
AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
624 InnerPA->
abandon(InnerAnalysisID);
631 InnerAM->invalidate(
C, *InnerPA);
637 if (!AreSCCAnalysesPreserved)
638 InnerAM->invalidate(
C, PA);
667 Module &M = *
C.begin()->getFunction().getParent();
671 "The CGSCC pass manager requires that the FAM module proxy is run "
672 "on the module prior to entering the CGSCC walk");
705 bool AreFunctionAnalysesPreserved =
712 std::optional<PreservedAnalyses> FunctionPA;
717 if (
auto *OuterProxy =
719 for (
const auto &OuterInvalidationPair :
720 OuterProxy->getOuterInvalidations()) {
721 AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
722 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
726 for (
AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
727 FunctionPA->
abandon(InnerAnalysisID);
740 if (!AreFunctionAnalysesPreserved)
783 for (
const auto &OuterInvalidationPair :
784 OuterProxy->getOuterInvalidations()) {
785 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
786 for (
AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
787 PA.abandon(InnerAnalysisID);
805template <
typename SCCRangeT>
812 if (NewSCCRange.empty())
817 LLVM_DEBUG(
dbgs() <<
"Enqueuing the existing SCC in the worklist:" << *
C
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!");
834 FAM = &FAMProxy->getManager();
843 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
852 assert(
C != &NewC &&
"No need to re-visit the current SCC!");
853 assert(OldC != &NewC &&
"Already handled the original SCC!");
855 LLVM_DEBUG(
dbgs() <<
"Enqueuing a newly formed SCC:" << NewC <<
"\n");
879 RefSCC *RC = &InitialRC;
896 if (
auto *CB = dyn_cast<CallBase>(&
I)) {
901 "Visited function should already have an associated node");
902 Edge *
E =
N->lookup(*CalleeN);
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;
909 assert(Inserted &&
"We should never visit a function twice.");
911 NewCallEdges.
insert(CalleeN);
912 else if (!
E->isCall())
913 PromotedRefTargets.
insert(CalleeN);
921 else if (!Entry->second)
929 for (
Value *Op :
I.operand_values())
930 if (
auto *OpC = dyn_cast<Constant>(Op))
931 if (Visited.
insert(OpC).second)
934 auto VisitRef = [&](
Function &Referee) {
935 Node *RefereeN =
G.lookup(Referee);
937 "Visited function should already have an associated node");
938 Edge *
E =
N->lookup(*RefereeN);
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;
945 assert(Inserted &&
"We should never visit a function twice.");
947 NewRefEdges.
insert(RefereeN);
948 else if (
E->isCall())
949 DemotedCallTargets.
insert(RefereeN);
954 for (
Node *RefTarget : NewRefEdges) {
955 SCC &TargetC = *
G.lookupSCC(*RefTarget);
956 RefSCC &TargetRC = TargetC.getOuterRefSCC();
959#ifdef EXPENSIVE_CHECKS
960 assert((RC == &TargetRC ||
961 RC->isAncestorOf(TargetRC)) &&
"New ref edge is not trivial!");
963 RC->insertTrivialRefEdge(
N, *RefTarget);
967 for (
Node *CallTarget : NewCallEdges) {
968 SCC &TargetC = *
G.lookupSCC(*CallTarget);
969 RefSCC &TargetRC = TargetC.getOuterRefSCC();
972#ifdef EXPENSIVE_CHECKS
973 assert((RC == &TargetRC ||
974 RC->isAncestorOf(TargetRC)) &&
"New call edge is not trivial!");
978 RC->insertTrivialRefEdge(
N, *CallTarget);
982 for (
auto *LibFn :
G.getLibFunctions())
985 if (!Visited.
count(LibFn))
993 if (RetainedEdges.
count(&
E.getNode()))
996 SCC &TargetC = *
G.lookupSCC(
E.getNode());
997 RefSCC &TargetRC = TargetC.getOuterRefSCC();
998 if (&TargetRC == RC &&
E.isCall()) {
1001 RC->switchTrivialInternalEdgeToRef(
N,
E.getNode());
1014 SCC &TargetC = *
G.lookupSCC(*TargetN);
1015 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1019 if (&TargetRC == RC)
1023 << *TargetN <<
"'\n");
1024 RC->removeOutgoingEdge(
N, *TargetN);
1029 auto NewRefSCCs = RC->removeInternalRefEdge(
N, DeadTargets);
1030 if (!NewRefSCCs.empty()) {
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!");
1047 assert(NewRefSCCs.front() == RC &&
1048 "New current RefSCC not first in the returned list!");
1050 assert(NewRC != RC &&
"Should not encounter the current RefSCC further "
1051 "in the postorder list of new RefSCCs.");
1053 LLVM_DEBUG(
dbgs() <<
"Enqueuing a new RefSCC in the update worklist: "
1061 for (
Node *RefTarget : DemotedCallTargets) {
1062 SCC &TargetC = *
G.lookupSCC(*RefTarget);
1063 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1067 if (&TargetRC != RC) {
1068#ifdef EXPENSIVE_CHECKS
1069 assert(RC->isAncestorOf(TargetRC) &&
1070 "Cannot potentially form RefSCC cycles here!");
1072 RC->switchOutgoingEdgeToRef(
N, *RefTarget);
1073 LLVM_DEBUG(
dbgs() <<
"Switch outgoing call edge to a ref edge from '" <<
N
1074 <<
"' to '" << *RefTarget <<
"'\n");
1080 if (
C != &TargetC) {
1082 RC->switchTrivialInternalEdgeToRef(
N, *RefTarget);
1093 for (
Node *
E : NewCallEdges)
1097 for (
Node *CallTarget : PromotedRefTargets) {
1098 SCC &TargetC = *
G.lookupSCC(*CallTarget);
1099 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1103 if (&TargetRC != RC) {
1104#ifdef EXPENSIVE_CHECKS
1105 assert(RC->isAncestorOf(TargetRC) &&
1106 "Cannot potentially form RefSCC cycles here!");
1108 RC->switchOutgoingEdgeToCall(
N, *CallTarget);
1109 LLVM_DEBUG(
dbgs() <<
"Switch outgoing ref edge to a call edge from '" <<
N
1110 <<
"' to '" << *CallTarget <<
"'\n");
1113 LLVM_DEBUG(
dbgs() <<
"Switch an internal ref edge to a call edge from '"
1114 <<
N <<
"' to '" << *CallTarget <<
"'\n");
1120 bool HasFunctionAnalysisProxy =
false;
1121 auto InitialSCCIndex = RC->find(*
C) - RC->begin();
1122 bool FormedCycle = RC->switchInternalEdgeToCall(
1124 for (SCC *MergedC : MergedSCCs) {
1125 assert(MergedC != &TargetC &&
"Cannot merge away the target SCC!");
1127 HasFunctionAnalysisProxy |=
1129 *MergedC) !=
nullptr;
1137 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1147 assert(
G.lookupSCC(
N) ==
C &&
"Failed to update current SCC!");
1152 if (HasFunctionAnalysisProxy)
1158 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1162 auto NewSCCIndex = RC->find(*
C) - RC->begin();
1171 if (InitialSCCIndex < NewSCCIndex) {
1177 LLVM_DEBUG(
dbgs() <<
"Enqueuing the existing SCC in the worklist: " << *
C
1181 RC->begin() + NewSCCIndex))) {
1183 LLVM_DEBUG(
dbgs() <<
"Enqueuing a newly earlier in post-order SCC: "
1191 assert(&
C->getOuterRefSCC() == RC &&
"Current SCC not in current RefSCC!");
amdgpu Simplify well known AMD library false FunctionCallee Callee
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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.
Implements a lazy call graph analysis and related passes for the new pass manager.
print must be executed print the must be executed context for all instructions
CGSCCAnalysisManager CGAM
FunctionAnalysisManager FAM
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 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.
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...
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.
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...
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
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...
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...
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.