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;
168 InlinedInternalEdges,
181 "Should always start with an empty RefSCC worklist");
197 if (InvalidRefSCCSet.
count(RC)) {
203 "Should always start with an empty SCC worklist");
205 LLVM_DEBUG(
dbgs() <<
"Running an SCC pass across the RefSCC: " << *RC
225 if (InvalidSCCSet.
count(
C)) {
229 if (LastUpdatedC ==
C) {
269 assert(!InvalidSCCSet.
count(
C) &&
"Processing an invalid SCC!");
270 assert(
C->begin() !=
C->end() &&
"Cannot have an empty SCC!");
298 PA.intersect(PassPA);
304 LLVM_DEBUG(
dbgs() <<
"Skipping invalidated root or island SCC!\n");
309 assert(
C->begin() !=
C->end() &&
"Cannot have an empty SCC!");
332 <<
"Re-running SCC passes after a refinement of the "
340 }
while (!CWorklist.
empty());
345 InlinedInternalEdges.
clear();
346 }
while (!RCWorklist.
empty());
350 for (
Function *DeadF : DeadFunctions)
351 DeadF->eraseFromParent();
353#if defined(EXPENSIVE_CHECKS)
390 assert(CallHandles.empty() &&
"Must start with a clear set of handles.");
393 CallCount CountLocal = {0, 0};
396 CallCounts.
insert(std::make_pair(&
N.getFunction(), CountLocal))
399 if (
auto *CB = dyn_cast<CallBase>(&
I)) {
400 if (CB->getCalledFunction()) {
416 for (
int Iteration = 0;; ++Iteration) {
428 LLVM_DEBUG(
dbgs() <<
"Skipping invalidated root or island SCC!\n");
443 assert(
C->begin() !=
C->end() &&
"Cannot have an empty SCC!");
448 if (CallBase *CB = dyn_cast<CallBase>(P.second)) {
449 if (CB->getCalledFunction()) {
450 LLVM_DEBUG(dbgs() <<
"Found devirtualized call: " << *CB <<
"\n");
472 for (
auto &Pair : NewCallCounts) {
473 auto &CallCountNew = Pair.second;
474 auto CountIt = CallCounts.find(Pair.first);
475 if (CountIt != CallCounts.end()) {
476 const auto &CallCountOld = CountIt->second;
477 if (CallCountOld.Indirect > CallCountNew.Indirect &&
478 CallCountOld.Direct < CallCountNew.Direct) {
490 if (Iteration >= MaxIterations) {
494 dbgs() <<
"Found another devirtualization after hitting the max "
495 "number of repetitions ("
496 << MaxIterations <<
") on SCC: " << *
C <<
"\n");
501 dbgs() <<
"Repeating an SCC pass after finding a devirtualization in: "
505 CallCounts = std::move(NewCallCounts);
531 LLVM_DEBUG(
dbgs() <<
"Running function passes across an SCC: " <<
C <<
"\n");
571 "Current SCC not updated to the SCC containing the current node!");
588bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(
617 bool AreSCCAnalysesPreserved =
622 for (
auto &RC :
G->postorder_ref_sccs())
624 std::optional<PreservedAnalyses> InnerPA;
629 if (
auto *OuterProxy =
631 for (
const auto &OuterInvalidationPair :
632 OuterProxy->getOuterInvalidations()) {
633 AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
634 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
638 for (
AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
639 InnerPA->
abandon(InnerAnalysisID);
646 InnerAM->invalidate(
C, *InnerPA);
652 if (!AreSCCAnalysesPreserved)
653 InnerAM->invalidate(
C, PA);
682 Module &M = *
C.begin()->getFunction().getParent();
686 "The CGSCC pass manager requires that the FAM module proxy is run "
687 "on the module prior to entering the CGSCC walk");
720 bool AreFunctionAnalysesPreserved =
727 std::optional<PreservedAnalyses> FunctionPA;
732 if (
auto *OuterProxy =
734 for (
const auto &OuterInvalidationPair :
735 OuterProxy->getOuterInvalidations()) {
736 AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
737 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
741 for (
AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
742 FunctionPA->
abandon(InnerAnalysisID);
755 if (!AreFunctionAnalysesPreserved)
798 for (
const auto &OuterInvalidationPair :
799 OuterProxy->getOuterInvalidations()) {
800 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
801 for (
AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
802 PA.abandon(InnerAnalysisID);
820template <
typename SCCRangeT>
827 if (NewSCCRange.empty())
832 LLVM_DEBUG(
dbgs() <<
"Enqueuing the existing SCC in the worklist:" << *
C
839 assert(
C != &*NewSCCRange.begin() &&
840 "Cannot insert new SCCs without changing current SCC!");
841 C = &*NewSCCRange.begin();
842 assert(
G.lookupSCC(
N) ==
C &&
"Failed to update current SCC!");
849 FAM = &FAMProxy->getManager();
858 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
867 assert(
C != &NewC &&
"No need to re-visit the current SCC!");
868 assert(OldC != &NewC &&
"Already handled the original SCC!");
870 LLVM_DEBUG(
dbgs() <<
"Enqueuing a newly formed SCC:" << NewC <<
"\n");
894 RefSCC *RC = &InitialRC;
911 if (
auto *CB = dyn_cast<CallBase>(&
I)) {
912 if (
Function *Callee = CB->getCalledFunction()) {
913 if (Visited.
insert(Callee).second && !Callee->isDeclaration()) {
914 Node *CalleeN =
G.lookup(*Callee);
916 "Visited function should already have an associated node");
917 Edge *E =
N->lookup(*CalleeN);
919 "No function transformations should introduce *new* "
920 "call edges! Any new calls should be modeled as "
921 "promoted existing ref edges!");
922 bool Inserted = RetainedEdges.
insert(CalleeN).second;
924 assert(Inserted &&
"We should never visit a function twice.");
926 NewCallEdges.
insert(CalleeN);
927 else if (!E->isCall())
928 PromotedRefTargets.
insert(CalleeN);
936 else if (!Entry->second)
944 for (
Value *
Op :
I.operand_values())
945 if (
auto *OpC = dyn_cast<Constant>(
Op))
946 if (Visited.
insert(OpC).second)
949 auto VisitRef = [&](
Function &Referee) {
950 Node *RefereeN =
G.lookup(Referee);
952 "Visited function should already have an associated node");
953 Edge *E =
N->lookup(*RefereeN);
955 "No function transformations should introduce *new* ref "
956 "edges! Any new ref edges would require IPO which "
957 "function passes aren't allowed to do!");
958 bool Inserted = RetainedEdges.
insert(RefereeN).second;
960 assert(Inserted &&
"We should never visit a function twice.");
962 NewRefEdges.
insert(RefereeN);
963 else if (E->isCall())
964 DemotedCallTargets.
insert(RefereeN);
969 for (
Node *RefTarget : NewRefEdges) {
970 SCC &TargetC = *
G.lookupSCC(*RefTarget);
971 RefSCC &TargetRC = TargetC.getOuterRefSCC();
974#ifdef EXPENSIVE_CHECKS
975 assert((RC == &TargetRC ||
976 RC->isAncestorOf(TargetRC)) &&
"New ref edge is not trivial!");
978 RC->insertTrivialRefEdge(
N, *RefTarget);
982 for (
Node *CallTarget : NewCallEdges) {
983 SCC &TargetC = *
G.lookupSCC(*CallTarget);
984 RefSCC &TargetRC = TargetC.getOuterRefSCC();
987#ifdef EXPENSIVE_CHECKS
988 assert((RC == &TargetRC ||
989 RC->isAncestorOf(TargetRC)) &&
"New call edge is not trivial!");
993 RC->insertTrivialRefEdge(
N, *CallTarget);
997 for (
auto *LibFn :
G.getLibFunctions())
1000 if (!Visited.
count(LibFn))
1007 for (Edge &E : *
N) {
1008 if (RetainedEdges.
count(&E.getNode()))
1011 SCC &TargetC = *
G.lookupSCC(E.getNode());
1012 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1013 if (&TargetRC == RC && E.isCall()) {
1014 if (
C != &TargetC) {
1016 RC->switchTrivialInternalEdgeToRef(
N, E.getNode());
1029 SCC &TargetC = *
G.lookupSCC(*TargetN);
1030 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1034 if (&TargetRC == RC)
1038 << *TargetN <<
"'\n");
1039 RC->removeOutgoingEdge(
N, *TargetN);
1046 for (
Node *RefTarget : DemotedCallTargets) {
1047 SCC &TargetC = *
G.lookupSCC(*RefTarget);
1048 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1052 if (&TargetRC != RC) {
1053#ifdef EXPENSIVE_CHECKS
1054 assert(RC->isAncestorOf(TargetRC) &&
1055 "Cannot potentially form RefSCC cycles here!");
1057 RC->switchOutgoingEdgeToRef(
N, *RefTarget);
1058 LLVM_DEBUG(
dbgs() <<
"Switch outgoing call edge to a ref edge from '" <<
N
1059 <<
"' to '" << *RefTarget <<
"'\n");
1065 if (
C != &TargetC) {
1067 RC->switchTrivialInternalEdgeToRef(
N, *RefTarget);
1078 for (
Node *E : NewCallEdges)
1079 PromotedRefTargets.
insert(E);
1082 for (
Node *CallTarget : PromotedRefTargets) {
1083 SCC &TargetC = *
G.lookupSCC(*CallTarget);
1084 RefSCC &TargetRC = TargetC.getOuterRefSCC();
1088 if (&TargetRC != RC) {
1089#ifdef EXPENSIVE_CHECKS
1090 assert(RC->isAncestorOf(TargetRC) &&
1091 "Cannot potentially form RefSCC cycles here!");
1093 RC->switchOutgoingEdgeToCall(
N, *CallTarget);
1094 LLVM_DEBUG(
dbgs() <<
"Switch outgoing ref edge to a call edge from '" <<
N
1095 <<
"' to '" << *CallTarget <<
"'\n");
1098 LLVM_DEBUG(
dbgs() <<
"Switch an internal ref edge to a call edge from '"
1099 <<
N <<
"' to '" << *CallTarget <<
"'\n");
1105 bool HasFunctionAnalysisProxy =
false;
1106 auto InitialSCCIndex = RC->find(*
C) - RC->begin();
1107 bool FormedCycle = RC->switchInternalEdgeToCall(
1109 for (SCC *MergedC : MergedSCCs) {
1110 assert(MergedC != &TargetC &&
"Cannot merge away the target SCC!");
1112 HasFunctionAnalysisProxy |=
1114 *MergedC) !=
nullptr;
1122 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1132 assert(
G.lookupSCC(
N) ==
C &&
"Failed to update current SCC!");
1137 if (HasFunctionAnalysisProxy)
1143 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1147 auto NewSCCIndex = RC->find(*
C) - RC->begin();
1156 if (InitialSCCIndex < NewSCCIndex) {
1162 LLVM_DEBUG(
dbgs() <<
"Enqueuing the existing SCC in the worklist: " << *
C
1166 RC->begin() + NewSCCIndex))) {
1168 LLVM_DEBUG(
dbgs() <<
"Enqueuing a newly earlier in post-order SCC: "
1176 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.
Implements a lazy call graph analysis and related passes for the new pass manager.
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.
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.
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.