A RefSCC of the call graph. More...

#include "llvm/Analysis/LazyCallGraph.h"

Public Types
using	iterator = pointee_iterator< SmallVectorImpl< SCC * >::const_iterator >

using	range = iterator_range< iterator >

using	parent_iterator = pointee_iterator< SmallPtrSetImpl< RefSCC * >::const_iterator >

Public Member Functions
iterator	begin () const

iterator	end () const

ssize_t	size () const

SCC &	operator[] (int Idx)

iterator	find (SCC &C) const

bool	isParentOf (const RefSCC &RC) const
	Test if this RefSCC is a parent of RC. More...

bool	isAncestorOf (const RefSCC &RC) const
	Test if this RefSCC is an ancestor of RC. More...

bool	isChildOf (const RefSCC &RC) const
	Test if this RefSCC is a child of RC. More...

bool	isDescendantOf (const RefSCC &RC) const
	Test if this RefSCC is a descendant of RC. More...

std::string	getName () const
	Provide a short name by printing this RefSCC to a std::string. More...

Mutation API
These methods provide the core API for updating the call graph in the presence of (potentially still in-flight) DFS-found RefSCCs and SCCs. Note that these methods sometimes have complex runtimes, so be careful how you call them.
bool	switchInternalEdgeToCall (Node &SourceN, Node &TargetN, function_ref< void(ArrayRef< SCC *> MergedSCCs)> MergeCB={})
	Make an existing internal ref edge into a call edge. More...

void	switchTrivialInternalEdgeToRef (Node &SourceN, Node &TargetN)
	Make an existing internal call edge between separate SCCs into a ref edge. More...

iterator_range< iterator >	switchInternalEdgeToRef (Node &SourceN, Node &TargetN)
	Make an existing internal call edge within a single SCC into a ref edge. More...

void	switchOutgoingEdgeToCall (Node &SourceN, Node &TargetN)
	Make an existing outgoing ref edge into a call edge. More...

void	switchOutgoingEdgeToRef (Node &SourceN, Node &TargetN)
	Make an existing outgoing call edge into a ref edge. More...

void	insertInternalRefEdge (Node &SourceN, Node &TargetN)
	Insert a ref edge from one node in this RefSCC to another in this RefSCC. More...

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. More...

SmallVector< RefSCC *, 1 >	insertIncomingRefEdge (Node &SourceN, Node &TargetN)
	Insert an edge whose source is in a descendant RefSCC and target is in this RefSCC. More...

void	removeOutgoingEdge (Node &SourceN, Node &TargetN)
	Remove an edge whose source is in this RefSCC and target is not. More...

SmallVector< RefSCC *, 1 >	removeInternalRefEdge (Node &SourceN, ArrayRef< Node *> TargetNs)
	Remove a list of ref edges which are entirely within this RefSCC. More...

void	insertTrivialCallEdge (Node &SourceN, Node &TargetN)
	A convenience wrapper around the above to handle trivial cases of inserting a new call edge. More...

void	insertTrivialRefEdge (Node &SourceN, Node &TargetN)
	A convenience wrapper around the above to handle trivial cases of inserting a new ref edge. More...

void	replaceNodeFunction (Node &N, Function &NewF)
	Directly replace a node's function with a new function. More...

Friends
class	LazyCallGraph

class	LazyCallGraph::Node

raw_ostream &	operator<< (raw_ostream &OS, const RefSCC &RC)
	Print a short description useful for debugging or logging. More...

Detailed Description

A RefSCC of the call graph.

This models a Strongly Connected Component of function reference edges in the call graph. As opposed to actual SCCs, these can be used to scope subgraphs of the module which are independent from other subgraphs of the module because they do not reference it in any way. This is also the unit where we do mutation of the graph in order to restrict mutations to those which don't violate this independence.

A RefSCC contains a DAG of actual SCCs. All the nodes within the RefSCC are necessarily within some actual SCC that nests within it. Since a direct call is a reference, there will always be at least one RefSCC around any SCC.

Definition at line 547 of file LazyCallGraph.h.

Member Typedef Documentation

◆ iterator

using llvm::LazyCallGraph::RefSCC::iterator = pointee_iterator<SmallVectorImpl<SCC *>::const_iterator>

Definition at line 614 of file LazyCallGraph.h.

◆ parent_iterator

using llvm::LazyCallGraph::RefSCC::parent_iterator = pointee_iterator<SmallPtrSetImpl<RefSCC *>::const_iterator>

Definition at line 617 of file LazyCallGraph.h.

◆ range

using llvm::LazyCallGraph::RefSCC::range = iterator_range<iterator>

Definition at line 615 of file LazyCallGraph.h.

Member Function Documentation

◆ begin()

iterator llvm::LazyCallGraph::RefSCC::begin ( ) const

inline

Definition at line 619 of file LazyCallGraph.h.

References llvm::SmallVectorTemplateCommon< T >::begin().

◆ end()

iterator llvm::LazyCallGraph::RefSCC::end ( ) const

inline

Definition at line 620 of file LazyCallGraph.h.

References llvm::SmallVectorTemplateCommon< T >::end().

◆ find()

iterator llvm::LazyCallGraph::RefSCC::find ( SCC & C ) const

inline

Definition at line 626 of file LazyCallGraph.h.

References llvm::SmallVectorTemplateCommon< T >::begin(), and llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find().

◆ getName()

std::string llvm::LazyCallGraph::RefSCC::getName ( ) const

inline

Provide a short name by printing this RefSCC to a std::string.

This copes with the fact that we don't have a name per-se for an RefSCC while still making the use of this in debugging and logging useful.

Definition at line 662 of file LazyCallGraph.h.

References llvm::raw_ostream::flush(), and Name.

◆ insertIncomingRefEdge()

SmallVector< LazyCallGraph::RefSCC *, 1 > LazyCallGraph::RefSCC::insertIncomingRefEdge	(	Node &	SourceN,
		Node &	TargetN
	)

Insert an edge whose source is in a descendant RefSCC and target is in this RefSCC.

There must be an existing path from the target to the source in this case.

NB! This is has the potential to be a very expensive function. It inherently forms a cycle in the prior RefSCC DAG and we have to merge RefSCCs to resolve that cycle. But finding all of the RefSCCs which participate in the cycle can in the worst case require traversing every RefSCC in the graph. Every attempt is made to avoid that, but passes must still exercise caution calling this routine repeatedly.

Also note that this can only insert ref edges. In order to insert a call edge, first insert a ref edge and then switch it to a call edge. These are intentionally kept as separate interfaces because each step of the operation invalidates a different set of data structures.

This returns all the RefSCCs which were merged into the this RefSCC (the target's). This allows callers to invalidate any cached information.

FIXME: We could possibly optimize this quite a bit for cases where the caller and callee are very nearby in the graph. See comments in the implementation for details, but that use case might impact users.

Definition at line 952 of file LazyCallGraph.cpp.

References llvm::SmallVectorImpl< T >::append(), assert(), llvm::iterator_range< IteratorT >::begin(), C, E, llvm::SmallVectorBase::empty(), llvm::iterator_range< IteratorT >::end(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::LazyCallGraph::lookupRefSCC(), llvm::make_range(), llvm::make_scope_exit(), N, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::LazyCallGraph::Edge::Ref, updatePostorderSequenceForEdgeInsertion(), and llvm::verify().

◆ insertInternalRefEdge()

void LazyCallGraph::RefSCC::insertInternalRefEdge	(	Node &	SourceN,
		Node &	TargetN
	)

Insert a ref edge from one node in this RefSCC to another in this RefSCC.

This is always a trivial operation as it doesn't change any part of the graph structure besides connecting the two nodes.

Note that we don't support directly inserting internal call edges because that could change the graph structure and requires returning information about what became invalid. As a consequence, the pattern should be to first insert the necessary ref edge, and then to switch it to a call edge if needed and handle any invalidation that results. See the switchInternalEdgeToCall routine for details.

Definition at line 918 of file LazyCallGraph.cpp.

References assert(), llvm::LazyCallGraph::lookupRefSCC(), llvm::LazyCallGraph::Edge::Ref, and llvm::verify().

◆ insertOutgoingEdge()

void LazyCallGraph::RefSCC::insertOutgoingEdge	(	Node &	SourceN,
		Node &	TargetN,
		Edge::Kind	EK
	)

Insert an edge whose parent is in this RefSCC and child is in some child RefSCC.

There must be an existing path from the SourceN to the TargetN. This operation is inexpensive and does not change the set of SCCs and RefSCCs in the graph.

Definition at line 931 of file LazyCallGraph.cpp.

References assert(), isDescendantOf(), llvm::LazyCallGraph::lookupRefSCC(), and llvm::verify().

◆ insertTrivialCallEdge()

void LazyCallGraph::RefSCC::insertTrivialCallEdge	(	Node &	SourceN,
		Node &	TargetN
	)

A convenience wrapper around the above to handle trivial cases of inserting a new call edge.

This is trivial whenever the target is in the same SCC as the source or the edge is an outgoing edge to some descendant SCC. In these cases there is no change to the cyclic structure of SCCs or RefSCCs.

To further make calling this convenient, it also handles inserting already existing edges.

Definition at line 1368 of file LazyCallGraph.cpp.

References assert(), llvm::LazyCallGraph::Edge::Call, E, llvm::SmallVectorImpl< T >::emplace_back(), llvm::LazyCallGraph::Edge::isCall(), llvm::LazyCallGraph::lookupSCC(), llvm::make_scope_exit(), llvm::SmallVectorBase::size(), and llvm::verify().

◆ insertTrivialRefEdge()

void LazyCallGraph::RefSCC::insertTrivialRefEdge	(	Node &	SourceN,
		Node &	TargetN
	)

A convenience wrapper around the above to handle trivial cases of inserting a new ref edge.

This is trivial whenever the target is in the same RefSCC as the source or the edge is an outgoing edge to some descendant RefSCC. In these cases there is no change to the cyclic structure of the RefSCCs.

To further make calling this convenient, it also handles inserting already existing edges.

Definition at line 1403 of file LazyCallGraph.cpp.

References assert(), llvm::SmallVectorImpl< T >::emplace_back(), llvm::LazyCallGraph::lookupRefSCC(), llvm::make_scope_exit(), llvm::LazyCallGraph::Edge::Ref, llvm::SmallVectorBase::size(), and llvm::verify().

◆ isAncestorOf()

bool LazyCallGraph::RefSCC::isAncestorOf ( const RefSCC & RC ) const

Test if this RefSCC is an ancestor of RC.

CAUTION: This method walks the directed graph of edges as far as necessary to find a possible path to the argument. In the worst case this may walk the entire graph and can be extremely expensive.

Definition at line 352 of file LazyCallGraph.cpp.

References C, E, llvm::SmallVectorBase::empty(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::LazyCallGraph::lookupRefSCC(), N, llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T >::push_back().

Referenced by isDescendantOf().

◆ isChildOf()

bool llvm::LazyCallGraph::RefSCC::isChildOf ( const RefSCC & RC ) const

inline

Test if this RefSCC is a child of RC.

CAUTION: This method walks every edge in the argument RefSCC, it can be very expensive.

Definition at line 647 of file LazyCallGraph.h.

References isParentOf().

◆ isDescendantOf()

bool llvm::LazyCallGraph::RefSCC::isDescendantOf ( const RefSCC & RC ) const

inline

Test if this RefSCC is a descendant of RC.

CAUTION: This method walks the directed graph of edges as far as necessary to find a possible path from the argument. In the worst case this may walk the entire graph and can be extremely expensive.

Definition at line 654 of file LazyCallGraph.h.

References isAncestorOf().

Referenced by insertOutgoingEdge(), switchOutgoingEdgeToCall(), and switchOutgoingEdgeToRef().

◆ isParentOf()

bool LazyCallGraph::RefSCC::isParentOf ( const RefSCC & RC ) const

Test if this RefSCC is a parent of RC.

CAUTION: This method walks every edge in the RefSCC, it can be very expensive.

Definition at line 338 of file LazyCallGraph.cpp.

References C, E, llvm::LazyCallGraph::lookupRefSCC(), and N.

Referenced by isChildOf().

◆ operator[]()

SCC& llvm::LazyCallGraph::RefSCC::operator[] ( int Idx )

inline

Definition at line 624 of file LazyCallGraph.h.

◆ removeInternalRefEdge()

SmallVector< LazyCallGraph::RefSCC *, 1 > LazyCallGraph::RefSCC::removeInternalRefEdge	(	Node &	SourceN,
		ArrayRef< Node *>	TargetNs
	)

Remove a list of ref edges which are entirely within this RefSCC.

Both the SourceN and all of the TargetNs must be within this RefSCC. Removing these edges may break cycles that form this RefSCC and thus this operation may change the RefSCC graph significantly. In particular, this operation will re-form new RefSCCs based on the remaining connectivity of the graph. The following invariants are guaranteed to hold after calling this method:

1) If a ref-cycle remains after removal, it leaves this RefSCC intact and in the graph. No new RefSCCs are built. 2) Otherwise, this RefSCC will be dead after this call and no longer in the graph or the postorder traversal of the call graph. Any iterator pointing at this RefSCC will become invalid. 3) All newly formed RefSCCs will be returned and the order of the RefSCCs returned will be a valid postorder traversal of the new RefSCCs. 4) No RefSCC other than this RefSCC has its member set changed (this is inherent in the definition of removing such an edge).

These invariants are very important to ensure that we can build optimization pipelines on top of the CGSCC pass manager which intelligently update the RefSCC graph without invalidating other parts of the RefSCC graph.

Note that we provide no routine to remove a call edge. Instead, you must first switch it to a ref edge using switchInternalEdgeToRef. This split API is intentional as each of these two steps can invalidate a different aspect of the graph structure and needs to have the invalidation handled independently.

The runtime complexity of this method is, in the worst case, O(V+E) where V is the number of nodes in this RefSCC and E is the number of edges leaving the nodes in this RefSCC. Note that E includes both edges within this RefSCC and edges from this RefSCC to child RefSCCs. Some effort has been made to minimize the overhead of common cases such as self-edges and edge removals which result in a spanning tree with no more cycles.

Definition at line 1115 of file LazyCallGraph.cpp.

References llvm::all_of(), llvm::SmallVectorImpl< T >::append(), assert(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::LazyCallGraph::EdgeSequence::begin(), C, E, llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::LazyCallGraph::EdgeSequence::end(), llvm::SmallVectorImpl< T >::erase(), llvm::find_if(), I, llvm::LazyCallGraph::lookupRefSCC(), llvm::LazyCallGraph::lookupSCC(), llvm::make_range(), llvm::make_scope_exit(), N, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::reverse(), llvm::SmallVectorBase::size(), llvm::size(), and llvm::verify().

◆ removeOutgoingEdge()

void LazyCallGraph::RefSCC::removeOutgoingEdge	(	Node &	SourceN,
		Node &	TargetN
	)

Remove an edge whose source is in this RefSCC and target is not.

This removes an inter-RefSCC edge. All inter-RefSCC edges originating from this SCC have been fully explored by any in-flight DFS graph formation, so this is always safe to call once you have the source RefSCC.

This operation does not change the cyclic structure of the graph and so is very inexpensive. It may change the connectivity graph of the SCCs though, so be careful calling this while iterating over them.

Definition at line 1095 of file LazyCallGraph.cpp.

References assert(), llvm::LazyCallGraph::lookupRefSCC(), llvm::make_scope_exit(), and llvm::verify().

◆ replaceNodeFunction()

void LazyCallGraph::RefSCC::replaceNodeFunction	(	Node &	N,
		Function &	NewF
	)

Directly replace a node's function with a new function.

This should be used when moving the body and users of a function to a new formal function object but not otherwise changing the call graph structure in any way.

It requires that the old function in the provided node have zero uses and the new function must have calls and references to it establishing an equivalent graph.

Definition at line 1432 of file LazyCallGraph.cpp.

References assert(), llvm::LazyCallGraph::Node::getFunction(), llvm::LazyCallGraph::lookupRefSCC(), llvm::make_scope_exit(), N, llvm::Value::use_empty(), and llvm::verify().

◆ size()

ssize_t llvm::LazyCallGraph::RefSCC::size ( ) const

inline

Definition at line 622 of file LazyCallGraph.h.

References llvm::SmallVectorBase::size().

Referenced by llvm::LazyCallGraph::removeDeadFunction().

◆ switchInternalEdgeToCall()

bool LazyCallGraph::RefSCC::switchInternalEdgeToCall	(	Node &	SourceN,
		Node &	TargetN,
		function_ref< void(ArrayRef< SCC *> MergedSCCs)>	MergeCB = `{}`
	)

Make an existing internal ref edge into a call edge.

This may form a larger cycle and thus collapse SCCs into TargetN's SCC. If that happens, the optional callback MergedCB will be invoked (if provided) on the SCCs being merged away prior to actually performing the merge. Note that this will never include the target SCC as that will be the SCC functions are merged into to resolve the cycle. Once this function returns, these merged SCCs are not in a valid state but the pointers will remain valid until destruction of the parent graph instance for the purpose of clearing cached information. This function also returns 'true' if a cycle was formed and some SCCs merged away as a convenience.

After this operation, both SourceN's SCC and TargetN's SCC may move position within this RefSCC's postorder list. Any SCCs merged are merged into the TargetN's SCC in order to preserve reachability analyses which took place on that SCC.

Definition at line 516 of file LazyCallGraph.cpp.

References assert(), C, llvm::LazyCallGraph::Edge::Call, E, llvm::SmallVectorBase::empty(), llvm::empty(), llvm::LazyCallGraph::SCC::getOuterRefSCC(), llvm::LazyCallGraph::lookupSCC(), llvm::make_range(), llvm::make_scope_exit(), llvm::makeArrayRef(), N, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), updatePostorderSequenceForEdgeInsertion(), and llvm::verify().

◆ switchInternalEdgeToRef()

iterator_range< LazyCallGraph::RefSCC::iterator > LazyCallGraph::RefSCC::switchInternalEdgeToRef	(	Node &	SourceN,
		Node &	TargetN
	)

Make an existing internal call edge within a single SCC into a ref edge.

Since SourceN and TargetN are part of a single SCC, this SCC may be split up due to breaking a cycle in the call edges that formed it. If that happens, then this routine will insert new SCCs into the postorder list before the SCC of TargetN (previously the SCC of both). This preserves postorder as the TargetN can reach all of the other nodes by definition of previously being in a single SCC formed by the cycle from SourceN to TargetN.

The newly added SCCs are added immediately and contiguously prior to the TargetN SCC and return the range covering the new SCCs in the RefSCC's postorder sequence. You can directly iterate the returned range to observe all of the new SCCs in postorder.

Note that if SourceN and TargetN are in separate SCCs, the simpler routine switchTrivialInternalEdgeToRef should be used instead.

Definition at line 688 of file LazyCallGraph.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::LazyCallGraph::SCC::begin(), llvm::SmallVectorImpl< T >::clear(), E, llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::LazyCallGraph::SCC::end(), llvm::SmallVectorImpl< T >::erase(), llvm::find_if(), I, llvm::LazyCallGraph::lookupRefSCC(), llvm::LazyCallGraph::lookupSCC(), llvm::make_range(), llvm::make_scope_exit(), N, llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorTemplateCommon< T >::rbegin(), llvm::LazyCallGraph::Edge::Ref, llvm::reverse(), Size, llvm::SmallVectorBase::size(), llvm::LazyCallGraph::SCC::size(), llvm::SmallVectorImpl< T >::swap(), and llvm::verify().

◆ switchOutgoingEdgeToCall()

void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall	(	Node &	SourceN,
		Node &	TargetN
	)

Make an existing outgoing ref edge into a call edge.

Note that this is trivial as there are no cyclic impacts and there remains a reference edge.

Definition at line 874 of file LazyCallGraph.cpp.

References assert(), llvm::LazyCallGraph::Edge::Call, isDescendantOf(), llvm::LazyCallGraph::lookupRefSCC(), and llvm::verify().

◆ switchOutgoingEdgeToRef()

void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef	(	Node &	SourceN,
		Node &	TargetN
	)

Make an existing outgoing call edge into a ref edge.

This is trivial as there are no cyclic impacts and there remains a reference edge.

Definition at line 896 of file LazyCallGraph.cpp.

References assert(), isDescendantOf(), llvm::LazyCallGraph::lookupRefSCC(), llvm::LazyCallGraph::Edge::Ref, and llvm::verify().

◆ switchTrivialInternalEdgeToRef()

void LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef	(	Node &	SourceN,
		Node &	TargetN
	)

Make an existing internal call edge between separate SCCs into a ref edge.

If SourceN and TargetN in separate SCCs within this RefSCC, changing the call edge between them to a ref edge is a trivial operation that does not require any structural changes to the call graph.

Definition at line 665 of file LazyCallGraph.cpp.

References assert(), llvm::LazyCallGraph::lookupRefSCC(), llvm::LazyCallGraph::lookupSCC(), llvm::make_scope_exit(), llvm::LazyCallGraph::Edge::Ref, and llvm::verify().

Friends And Related Function Documentation

◆ LazyCallGraph

friend class LazyCallGraph

friend

Definition at line 548 of file LazyCallGraph.h.

◆ LazyCallGraph::Node

friend class LazyCallGraph::Node

friend

Definition at line 549 of file LazyCallGraph.h.

◆ operator<<

raw_ostream& operator<<	(	raw_ostream &	OS,
		const RefSCC &	RC
	)

friend

Print a short description useful for debugging or logging.

We print the SCCs wrapped in '[]'s and skipping the middle SCCs if there are a large number.

Definition at line 575 of file LazyCallGraph.h.

The documentation for this class was generated from the following files:

include/llvm/Analysis/LazyCallGraph.h
lib/Analysis/LazyCallGraph.cpp

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ iterator

◆ parent_iterator

◆ range

Member Function Documentation

◆ begin()

◆ end()

◆ find()

◆ getName()

◆ insertIncomingRefEdge()

◆ insertInternalRefEdge()

◆ insertOutgoingEdge()

◆ insertTrivialCallEdge()

◆ insertTrivialRefEdge()

◆ isAncestorOf()

◆ isChildOf()

◆ isDescendantOf()

◆ isParentOf()

◆ operator[]()

◆ removeInternalRefEdge()

◆ removeOutgoingEdge()

◆ replaceNodeFunction()

◆ size()

◆ switchInternalEdgeToCall()

◆ switchInternalEdgeToRef()

◆ switchOutgoingEdgeToCall()

◆ switchOutgoingEdgeToRef()

◆ switchTrivialInternalEdgeToRef()

Friends And Related Function Documentation

◆ LazyCallGraph

◆ LazyCallGraph::Node

◆ operator<<