34#ifndef LLVM_ANALYSIS_LAZYCALLGRAPH_H
35#define LLVM_ANALYSIS_LAZYCALLGRAPH_H
58template <
class GraphType>
struct GraphTraits;
139 explicit operator bool()
const;
165 void setKind(
Kind K) {
Value.setInt(K); }
190 std::forward_iterator_tag> {
199 while (
I !=
E && !*
I)
206 using iterator_adaptor_base::operator++;
210 }
while (
I !=
E && !*
I);
221 std::forward_iterator_tag> {
228 void advanceToNextEdge() {
229 while (
I !=
E && (!*
I || !
I->isCall()))
242 using iterator_adaptor_base::operator++;
254 assert(EdgeIndexMap.contains(&
N) &&
"No such edge!");
255 auto &
E = Edges[EdgeIndexMap.find(&
N)->second];
256 assert(
E &&
"Dead or null edge!");
261 auto EI = EdgeIndexMap.find(&
N);
262 if (EI == EdgeIndexMap.end())
264 auto &
E = Edges[EI->second];
265 return E ? &
E :
nullptr;
278 for (
auto &
E : Edges)
298 bool removeEdgeInternal(
Node &ChildN);
336 "Both graph and function pointers should be null or non-null.");
364 return populateSlow();
377 std::optional<EdgeSequence> Edges;
384 EdgeSequence &populateSlow();
391 void replaceFunction(
Function &NewF);
393 void clear() { Edges.reset(); }
397 return OS <<
N.F->getName();
422 template <
typename NodeRangeT>
423 SCC(
RefSCC &OuterRefSCC, NodeRangeT &&Nodes)
424 : OuterRefSCC(&OuterRefSCC), Nodes(
std::forward<NodeRangeT>(Nodes)) {}
427 OuterRefSCC =
nullptr;
446 OS <<
"..., " << *
C.Nodes.back();
459#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
484 bool isParentOf(
const SCC &
C)
const;
492 bool isAncestorOf(
const SCC &
C)
const;
576 OS <<
"..., " << *RC.SCCs.back();
589#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
616 return SCCs.
begin() + SCCIndices.
find(&
C)->second;
877 std::forward_iterator_tag, RefSCC> {
889 incrementUntilNonEmptyRefSCC();
898 if (
Index == (
int)
G.PostOrderRefSCCs.size())
902 return G.PostOrderRefSCCs[
Index];
906 void incrementUntilNonEmptyRefSCC() {
907 while (RC && RC->
size() == 0)
912 assert(RC &&
"Cannot increment the end iterator!");
913 RC = getRC(*G,
G->RefSCCIndices.find(RC)->second + 1);
918 return G == Arg.G && RC == Arg.RC;
923 using iterator_facade_base::operator++;
926 incrementUntilNonEmptyRefSCC();
942#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
956 if (!EntryEdges.
empty())
957 assert(!PostOrderRefSCCs.empty() &&
958 "Must form RefSCCs before iterating them!");
962 if (!EntryEdges.
empty())
963 assert(!PostOrderRefSCCs.empty() &&
964 "Must form RefSCCs before iterating them!");
966 postorder_ref_scc_iterator::IsAtEndT());
988 return &
C->getOuterRefSCC();
1000 return insertInto(
F,
N);
1008 return LibFunctions.getArrayRef();
1128 EdgeSequence EntryEdges;
1163 void updateGraphPtrs();
1168 template <
typename... Ts> SCC *createSCC(Ts &&...Args) {
1169 return new (SCCBPA.
Allocate()) SCC(std::forward<Ts>(Args)...);
1175 template <
typename... Ts> RefSCC *createRefSCC(Ts &&...Args) {
1176 return new (RefSCCBPA.
Allocate()) RefSCC(std::forward<Ts>(Args)...);
1190 template <
typename RootsT,
typename GetBeginT,
typename GetEndT,
1191 typename GetNodeT,
typename FormSCCCallbackT>
1192 static void buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1193 GetEndT &&GetEnd, GetNodeT &&GetNode,
1194 FormSCCCallbackT &&FormSCC);
1197 void buildSCCs(RefSCC &RC, node_stack_range Nodes);
1203 int getRefSCCIndex(RefSCC &RC) {
1204 auto IndexIt = RefSCCIndices.
find(&RC);
1205 assert(IndexIt != RefSCCIndices.
end() &&
"RefSCC doesn't have an index!");
1206 assert(PostOrderRefSCCs[IndexIt->second] == &RC &&
1207 "Index does not point back at RC!");
1208 return IndexIt->second;
1215inline LazyCallGraph::Edge::operator
bool()
const {
1216 return Value.getPointer() && !
Value.getPointer()->isDead();
1220 assert(*
this &&
"Queried a null edge!");
1221 return Value.getInt();
1225 assert(*
this &&
"Queried a null edge!");
1226 return getKind() == Call;
1230 assert(*
this &&
"Queried a null edge!");
1231 return *
Value.getPointer();
1235 assert(*
this &&
"Queried a null edge!");
1236 return getNode().getFunction();
static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_EXTERNAL_VISIBILITY
static void clear(coro::Shape &Shape)
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
Machine Check Debug Module
FunctionAnalysisManager FAM
This header defines various interfaces for pass management in LLVM.
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
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),...
iterator find(const_arg_type_t< KeyT > Val)
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
An analysis pass which computes the call graph for a module.
LazyCallGraph run(Module &M, ModuleAnalysisManager &AM)
Compute the LazyCallGraph for the module M.
A pass which prints the call graph as a DOT file to a raw_ostream.
A pass which prints the call graph to a raw_ostream.
An iterator over specifically call edges.
call_iterator & operator++()
An iterator used for the edges to both entry nodes and child nodes.
The edge sequence object.
Edge & operator[](Node &N)
call_iterator call_begin()
iterator_range< call_iterator > calls()
A class used to represent edges in the call graph.
Function & getFunction() const
Get the function referenced by this edge.
bool isCall() const
Test whether the edge represents a direct call to a function.
Kind
The kind of edge in the graph.
Kind getKind() const
Returns the Kind of the edge.
Node & getNode() const
Get the call graph node referenced by this edge.
A node in the call graph.
LazyCallGraph & getGraph() const
EdgeSequence & populate()
Populate the edges of this node if necessary.
bool isDead() const
Tests whether this is actually a dead node and no longer valid.
bool operator!=(const Node &N) const
bool isPopulated() const
Tests whether the node has been populated with edges.
bool operator==(const Node &N) const
Equality is defined as address equality.
friend raw_ostream & operator<<(raw_ostream &OS, const Node &N)
Print the name of this node's function.
EdgeSequence * operator->() const
StringRef getName() const
EdgeSequence & operator*() const
Function & getFunction() const
A RefSCC of the call graph.
SmallVector< RefSCC *, 1 > insertIncomingRefEdge(Node &SourceN, Node &TargetN)
Insert an edge whose source is in a descendant RefSCC and target is in this RefSCC.
bool switchInternalEdgeToCall(Node &SourceN, Node &TargetN, function_ref< void(ArrayRef< SCC * > MergedSCCs)> MergeCB={})
Make an existing internal ref edge into a call edge.
bool isAncestorOf(const RefSCC &RC) const
Test if this RefSCC is an ancestor of RC.
void insertTrivialRefEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new ref edge.
iterator find(SCC &C) const
SCC & operator[](int Idx)
bool isDescendantOf(const RefSCC &RC) const
Test if this RefSCC is a descendant of RC.
bool isChildOf(const RefSCC &RC) const
Test if this RefSCC is a child of RC.
void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN)
Make an existing outgoing ref edge into a call edge.
void replaceNodeFunction(Node &N, Function &NewF)
Directly replace a node's function with a new function.
void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK)
Insert an edge whose parent is in this RefSCC and child is in some child RefSCC.
SmallVector< RefSCC *, 1 > removeInternalRefEdges(ArrayRef< std::pair< Node *, Node * > > Edges)
Remove a list of ref edges which are entirely within this RefSCC.
iterator_range< iterator > switchInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge within a single SCC into a ref edge.
void insertInternalRefEdge(Node &SourceN, Node &TargetN)
Insert a ref edge from one node in this RefSCC to another in this RefSCC.
void insertTrivialCallEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new call edge.
void removeOutgoingEdge(Node &SourceN, Node &TargetN)
Remove an edge whose source is in this RefSCC and target is not.
std::string getName() const
Provide a short name by printing this RefSCC to a std::string.
void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing outgoing call edge into a ref edge.
friend raw_ostream & operator<<(raw_ostream &OS, const RefSCC &RC)
Print a short description useful for debugging or logging.
void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge between separate SCCs into a ref edge.
bool isParentOf(const RefSCC &RC) const
Test if this RefSCC is a parent of RC.
An SCC of the call graph.
bool isChildOf(const SCC &C) const
Test if this SCC is a child of C.
friend raw_ostream & operator<<(raw_ostream &OS, const SCC &C)
Print a short description useful for debugging or logging.
bool isDescendantOf(const SCC &C) const
Test if this SCC is a descendant of C.
std::string getName() const
Provide a short name by printing this SCC to a std::string.
RefSCC & getOuterRefSCC() const
A post-order depth-first RefSCC iterator over the call graph.
reference operator*() const
friend class LazyCallGraph
postorder_ref_scc_iterator & operator++()
bool operator==(const postorder_ref_scc_iterator &Arg) const
A lazily constructed view of the call graph of a module.
bool isLibFunction(Function &F) const
Test whether a function is a known and defined library function tracked by the call graph.
EdgeSequence::iterator begin()
RefSCC * lookupRefSCC(Node &N) const
Lookup a function's RefSCC in the graph.
void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK)
Update the call graph after inserting a new edge.
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 markDeadFunction(Function &F)
Mark a function as dead to be removed later by removeDeadFunctions().
void addSplitFunction(Function &OriginalFunction, Function &NewFunction)
Add a new function split/outlined from an existing function.
void addSplitRefRecursiveFunctions(Function &OriginalFunction, ArrayRef< Function * > NewFunctions)
Add new ref-recursive functions split/outlined from an existing function.
void removeDeadFunctions(ArrayRef< Function * > DeadFs)
Remove dead functions from the call graph.
postorder_ref_scc_iterator postorder_ref_scc_begin()
ArrayRef< Function * > getLibFunctions() const
Get the sequence of known and defined library functions.
postorder_ref_scc_iterator postorder_ref_scc_end()
void removeEdge(Node &SourceN, Node &TargetN)
Update the call graph after deleting an edge.
void removeEdge(Function &Source, Function &Target)
Update the call graph after deleting an edge.
void insertEdge(Function &Source, Function &Target, Edge::Kind EK)
Update the call graph after inserting a new edge.
Node & get(Function &F)
Get a graph node for a given function, scanning it to populate the graph data as necessary.
SCC * lookupSCC(Node &N) const
Lookup a function's SCC in the graph.
iterator_range< postorder_ref_scc_iterator > postorder_ref_sccs()
LazyCallGraph & operator=(LazyCallGraph &&RHS)
bool invalidate(Module &, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &)
void verify()
Verify that every RefSCC is valid.
EdgeSequence::iterator end()
Node * lookup(const Function &F) const
Lookup a function in the graph which has already been scanned and added.
A Module instance is used to store all the information related to an LLVM module.
PointerIntPair - This class implements a pair of a pointer and small integer.
A set of analyses that are preserved following a run of a transformation pass.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
A SetVector that performs no allocations if smaller than a certain size.
typename SuperClass::iterator iterator
std::reverse_iterator< iterator > reverse_iterator
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
StringRef - Represent a constant reference to a string, i.e.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
Target - Wrapper for Target specific information.
LLVM Value Representation.
An efficient, type-erasing, non-owning reference to a callable.
CRTP base class for adapting an iterator to a different type.
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
A raw_ostream that writes to an std::string.
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.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Implement std::hash so that hash_code can be used in STL containers.
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
static ChildIteratorType child_begin(NodeRef N)
static ChildIteratorType child_end(NodeRef N)
static NodeRef getEntryNode(NodeRef N)
static NodeRef getEntryNode(NodeRef N)
static ChildIteratorType child_end(NodeRef N)
static ChildIteratorType child_begin(NodeRef N)
A CRTP mix-in to automatically provide informational APIs needed for passes.
An iterator type that allows iterating over the pointees via some other iterator.