Go to the documentation of this file.
34 #ifndef LLVM_ANALYSIS_LAZYCALLGRAPH_H
35 #define LLVM_ANALYSIS_LAZYCALLGRAPH_H
59 template <
class GraphType>
struct GraphTraits;
61 class TargetLibraryInfo;
143 explicit operator bool()
const;
169 void setKind(
Kind K) {
Value.setInt(K); }
194 std::forward_iterator_tag> {
203 while (
I !=
E && !*
I)
210 using iterator_adaptor_base::operator++;
214 }
while (
I !=
E && !*
I);
225 std::forward_iterator_tag> {
232 void advanceToNextEdge() {
233 while (
I !=
E && (!*
I || !
I->isCall()))
246 using iterator_adaptor_base::operator++;
258 assert(EdgeIndexMap.find(&
N) != EdgeIndexMap.end() &&
"No such edge!");
259 auto &
E = Edges[EdgeIndexMap.find(&
N)->second];
260 assert(
E &&
"Dead or null edge!");
265 auto EI = EdgeIndexMap.find(&
N);
266 if (EI == EdgeIndexMap.end())
268 auto &
E = Edges[EI->second];
269 return E ? &
E :
nullptr;
282 for (
auto &
E : Edges)
302 bool removeEdgeInternal(
Node &ChildN);
340 "Both graph and function pointers should be null or non-null.");
368 return populateSlow();
388 EdgeSequence &populateSlow();
395 void replaceFunction(
Function &NewF);
401 return OS <<
N.F->getName();
426 template <
typename NodeRangeT>
427 SCC(
RefSCC &OuterRefSCC, NodeRangeT &&Nodes)
428 : OuterRefSCC(&OuterRefSCC), Nodes(
std::forward<NodeRangeT>(Nodes)) {}
431 OuterRefSCC =
nullptr;
450 OS <<
"..., " << *
C.Nodes.back();
463 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
480 int size()
const {
return Nodes.size(); }
488 bool isParentOf(
const SCC &
C)
const;
496 bool isAncestorOf(
const SCC &
C)
const;
572 OS <<
"..., " << *RC.SCCs.back();
585 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
607 ssize_t
size()
const {
return SCCs.size(); }
612 return SCCs.begin() + SCCIndices.
find(&
C)->second;
873 std::forward_iterator_tag, RefSCC> {
885 incrementUntilNonEmptyRefSCC();
894 if (Index == (
int)
G.PostOrderRefSCCs.size())
898 return G.PostOrderRefSCCs[Index];
902 void incrementUntilNonEmptyRefSCC() {
903 while (RC && RC->
size() == 0)
908 assert(RC &&
"Cannot increment the end iterator!");
909 RC = getRC(*G,
G->RefSCCIndices.find(RC)->second + 1);
914 return G ==
Arg.G && RC ==
Arg.RC;
919 using iterator_facade_base::operator++;
922 incrementUntilNonEmptyRefSCC();
947 if (!EntryEdges.
empty())
948 assert(!PostOrderRefSCCs.empty() &&
949 "Must form RefSCCs before iterating them!");
953 if (!EntryEdges.
empty())
954 assert(!PostOrderRefSCCs.empty() &&
955 "Must form RefSCCs before iterating them!");
957 postorder_ref_scc_iterator::IsAtEndT());
979 return &
C->getOuterRefSCC();
991 return insertInto(
F,
N);
999 return LibFunctions.getArrayRef();
1119 EdgeSequence EntryEdges;
1154 void updateGraphPtrs();
1159 template <
typename... Ts>
SCC *createSCC(Ts &&...
Args) {
1166 template <
typename... Ts> RefSCC *createRefSCC(Ts &&...
Args) {
1167 return new (RefSCCBPA.
Allocate()) RefSCC(std::forward<Ts>(
Args)...);
1181 template <
typename RootsT,
typename GetBeginT,
typename GetEndT,
1182 typename GetNodeT,
typename FormSCCCallbackT>
1183 static void buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1184 GetEndT &&GetEnd, GetNodeT &&GetNode,
1185 FormSCCCallbackT &&FormSCC);
1188 void buildSCCs(RefSCC &RC, node_stack_range Nodes);
1194 int getRefSCCIndex(RefSCC &RC) {
1195 auto IndexIt = RefSCCIndices.
find(&RC);
1196 assert(IndexIt != RefSCCIndices.
end() &&
"RefSCC doesn't have an index!");
1197 assert(PostOrderRefSCCs[IndexIt->second] == &RC &&
1198 "Index does not point back at RC!");
1199 return IndexIt->second;
1206 inline LazyCallGraph::Edge::operator bool()
const {
1207 return Value.getPointer() && !
Value.getPointer()->isDead();
1211 assert(*
this &&
"Queried a null edge!");
1212 return Value.getInt();
1216 assert(*
this &&
"Queried a null edge!");
1217 return getKind() == Call;
1221 assert(*
this &&
"Queried a null edge!");
1222 return *
Value.getPointer();
1226 assert(*
this &&
"Queried a null edge!");
1227 return getNode().getFunction();
1300 #endif // LLVM_ANALYSIS_LAZYCALLGRAPH_H
A set of analyses that are preserved following a run of a transformation pass.
bool operator==(const postorder_ref_scc_iterator &Arg) const
iterator find(SCC &C) const
This is an optimization pass for GlobalISel generic memory operations.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
LazyCallGraph(Module &M, function_ref< TargetLibraryInfo &(Function &)> GetTLI)
Construct a graph for the given module.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
A CRTP mix-in to automatically provide informational APIs needed for passes.
void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK)
Update the call graph after inserting a new edge.
A raw_ostream that writes to an std::string.
Target - Wrapper for Target specific information.
void removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
bool isPopulated() const
Tests whether the node has been populated with edges.
FunctionAnalysisManager FAM
A BumpPtrAllocator that allows only elements of a specific type to be allocated.
bool isDescendantOf(const SCC &C) const
Test if this SCC is a descendant of C.
Function & getFunction() const
CRTP base class for adapting an iterator to a different type.
Node * lookup(const Function &F) const
Lookup a function in the graph which has already been scanned and added.
static ChildIteratorType child_end(NodeRef N)
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
iterator_range< call_iterator > calls()
postorder_ref_scc_iterator postorder_ref_scc_begin()
bool invalidate(Module &, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &)
bool isAncestorOf(const RefSCC &RC) const
Test if this RefSCC is an ancestor of RC.
Edge & operator[](Node &N)
static void clear(coro::Shape &Shape)
Node & getNode() const
Get the call graph node referenced by this edge.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
void insertTrivialCallEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new call edge.
An SCC of the call graph.
LazyCallGraph & operator=(LazyCallGraph &&RHS)
A pass which prints the call graph to a raw_ostream.
postorder_ref_scc_iterator & operator++()
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
EdgeSequence::iterator end()
bool isDead() const
Tests whether this is actually a dead node and no longer valid.
(vector float) vec_cmpeq(*A, *B) C
bool isParentOf(const RefSCC &RC) const
Test if this RefSCC is a parent of RC.
void insertTrivialRefEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new ref edge.
void removeEdge(Function &Source, Function &Target)
Update the call graph after deleting an edge.
A RefSCC of the call graph.
An iterator used for the edges to both entry nodes and child nodes.
This class implements an extremely fast bulk output stream that can only output to a stream.
The edge sequence object.
SCC * lookupSCC(Node &N) const
Lookup a function's SCC in the graph.
API to communicate dependencies between analyses during invalidation.
void insertEdge(Function &Source, Function &Target, Edge::Kind EK)
Update the call graph after inserting a new edge.
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.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
friend class LazyCallGraph
Node & get(Function &F)
Get a graph node for a given function, scanning it to populate the graph data as necessary.
StringRef getName() const
bool switchInternalEdgeToCall(Node &SourceN, Node &TargetN, function_ref< void(ArrayRef< SCC * > MergedSCCs)> MergeCB={})
Make an existing internal ref edge into a call edge.
An efficient, type-erasing, non-owning reference to a callable.
A pass which prints the call graph as a DOT file to a raw_ostream.
std::string getName() const
Provide a short name by printing this SCC to a std::string.
iterator_range< iterator > switchInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge within a single SCC into a ref edge.
bool operator!=(const Node &N) const
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear void clear()
bool isDescendantOf(const RefSCC &RC) const
Test if this RefSCC is a descendant of RC.
void addSplitFunction(Function &OriginalFunction, Function &NewFunction)
Add a new function split/outlined from an existing function.
#define LLVM_EXTERNAL_VISIBILITY
RefSCC * lookupRefSCC(Node &N) const
Lookup a function's RefSCC in the graph.
std::string getName() const
Provide a short name by printing this RefSCC to a std::string.
void removeOutgoingEdge(Node &SourceN, Node &TargetN)
Remove an edge whose source is in this RefSCC and target is not.
LazyCallGraph & getGraph() const
static ChildIteratorType child_begin(NodeRef N)
A special type used by analysis passes to provide an address that identifies that particular analysis...
EdgeSequence::iterator begin()
SmallVector< RefSCC *, 1 > insertIncomingRefEdge(Node &SourceN, Node &TargetN)
Insert an edge whose source is in a descendant RefSCC and target is in this RefSCC.
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
static ChildIteratorType child_end(NodeRef N)
Kind
The kind of edge in the graph.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Function & getFunction() const
Get the function referenced by this edge.
A Module instance is used to store all the information related to an LLVM module.
A post-order depth-first RefSCC iterator over the call graph.
A CRTP mix-in that provides informational APIs needed for analysis passes.
A node in the call graph.
A class used to represent edges in the call graph.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
StringRef - Represent a constant reference to a string, i.e.
SmallVector< RefSCC *, 1 > removeInternalRefEdge(Node &SourceN, ArrayRef< Node * > TargetNs)
Remove a list of ref edges which are entirely within this RefSCC.
LazyCallGraph run(Module &M, ModuleAnalysisManager &AM)
Compute the LazyCallGraph for the module M.
Kind getKind() const
Returns the Kind of the edge.
static NodeRef getEntryNode(NodeRef N)
postorder_ref_scc_iterator postorder_ref_scc_end()
Machine Check Debug Module
void replaceNodeFunction(Node &N, Function &NewF)
Directly replace a node's function with a new function.
call_iterator & operator++()
T * Allocate(size_t num=1)
Allocate space for an array of objects without constructing them.
reference operator*() const
ArrayRef< Function * > getLibFunctions() const
Get the sequence of known and defined library functions.
void addSplitRefRecursiveFunctions(Function &OriginalFunction, ArrayRef< Function * > NewFunctions)
Add new ref-recursive functions split/outlined from an existing function.
friend raw_ostream & operator<<(raw_ostream &OS, const Node &N)
Print the name of this node's function.
friend raw_ostream & operator<<(raw_ostream &OS, const RefSCC &RC)
Print a short description useful for debugging or logging.
bool isCall() const
Test whether the edge represents a direct call to a function.
EdgeSequence & populate()
Populate the edges of this node if necessary.
static NodeRef getEntryNode(NodeRef N)
An analysis pass which computes the call graph for a module.
bool isLibFunction(Function &F) const
Test whether a function is a known and defined library function tracked by the call graph.
Provides information about what library functions are available for the current target.
static ChildIteratorType child_begin(NodeRef N)
void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge between separate SCCs into a ref edge.
SCC & operator[](int Idx)
void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing outgoing call edge into a ref edge.
PointerIntPair - This class implements a pair of a pointer and small integer.
An iterator over specifically call edges.
typename SuperClass::iterator iterator
EdgeSequence & operator*() const
void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN)
Make an existing outgoing ref edge into a call edge.
RefSCC & getOuterRefSCC() const
A range adaptor for a pair of iterators.
iterator_range< postorder_ref_scc_iterator > postorder_ref_sccs()
bool operator==(const Node &N) const
Equality is defined as address equality.
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.
A container for analyses that lazily runs them and caches their results.
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
bool isChildOf(const RefSCC &RC) const
Test if this RefSCC is a child of RC.
EdgeSequence * operator->() const
An iterator type that allows iterating over the pointees via some other iterator.
call_iterator call_begin()
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
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...
LLVM Value Representation.
bool isChildOf(const SCC &C) const
Test if this SCC is a child of C.
Analysis pass providing the TargetLibraryInfo.
void insertInternalRefEdge(Node &SourceN, Node &TargetN)
Insert a ref edge from one node in this RefSCC to another in this RefSCC.
void removeEdge(Node &SourceN, Node &TargetN)
Update the call graph after deleting an edge.
friend raw_ostream & operator<<(raw_ostream &OS, const SCC &C)
Print a short description useful for debugging or logging.