1.7.6.1Copyright © 2003-2014 University of Illinois at Urbana-Champaign. All Rights Reserved.
LLVM API Documentation
An SCC of the call graph. More...
#include <LazyCallGraph.h>
Public Types | |
| typedef SmallVectorImpl< Node * > ::const_iterator | iterator |
| typedef pointee_iterator < SmallPtrSet< SCC *, 1 > ::const_iterator > | parent_iterator |
Public Member Functions | |
| iterator | begin () const |
| iterator | end () const |
| parent_iterator | parent_begin () const |
| parent_iterator | parent_end () const |
| iterator_range< parent_iterator > | parents () const |
| bool | isParentOf (const SCC &C) const |
| Test if this SCC is a parent of C. | |
| bool | isAncestorOf (const SCC &C) const |
| Test if this SCC is an ancestor of C. | |
| bool | isChildOf (const SCC &C) const |
| Test if this SCC is a child of C. | |
| bool | isDescendantOf (const SCC &C) const |
| Test if this SCC is a descendant of C. | |
Mutation API | |
These methods provide the core API for updating the call graph in the presence of a (potentially still in-flight) DFS-found SCCs. Note that these methods sometimes have complex runtimes, so be careful how you call them. | |
| void | insertIntraSCCEdge (Node &CallerN, Node &CalleeN) |
| Insert an edge from one node in this SCC to another in this SCC. | |
| void | insertOutgoingEdge (Node &CallerN, Node &CalleeN) |
| Insert an edge whose tail is in this SCC and head is in some child SCC. | |
| SmallVector< SCC *, 1 > | insertIncomingEdge (Node &CallerN, Node &CalleeN) |
| Insert an edge whose tail is in a descendant SCC and head is in this SCC. | |
| void | removeInterSCCEdge (Node &CallerN, Node &CalleeN) |
| Remove an edge whose source is in this SCC and target is *not*. | |
| SmallVector< SCC *, 1 > | removeIntraSCCEdge (Node &CallerN, Node &CalleeN) |
| Remove an edge which is entirely within this SCC. | |
Friends | |
| class | LazyCallGraph |
| class | LazyCallGraph::Node |
An SCC of the call graph.
This represents a Strongly Connected Component of the call graph as a collection of call graph nodes. While the order of nodes in the SCC is stable, it is not any particular order.
Definition at line 210 of file LazyCallGraph.h.
| typedef SmallVectorImpl<Node *>::const_iterator llvm::LazyCallGraph::SCC::iterator |
Definition at line 228 of file LazyCallGraph.h.
| typedef pointee_iterator<SmallPtrSet<SCC *, 1>::const_iterator> llvm::LazyCallGraph::SCC::parent_iterator |
Definition at line 229 of file LazyCallGraph.h.
| iterator llvm::LazyCallGraph::SCC::begin | ( | ) | const [inline] |
Definition at line 231 of file LazyCallGraph.h.
References llvm::SmallVectorTemplateCommon< T, typename >::begin().
Referenced by printSCC().
| iterator llvm::LazyCallGraph::SCC::end | ( | ) | const [inline] |
Definition at line 232 of file LazyCallGraph.h.
References llvm::SmallVectorTemplateCommon< T, typename >::end().
Referenced by printSCC().
| SmallVector< LazyCallGraph::SCC *, 1 > LazyCallGraph::SCC::insertIncomingEdge | ( | Node & | CallerN, |
| Node & | CalleeN | ||
| ) |
Insert an edge whose tail is in a descendant SCC and head is in this SCC.
There must be an existing path from the callee to the caller in this case. NB! This is has the potential to be a very expensive function. It inherently forms a cycle in the prior SCC DAG and we have to merge SCCs to resolve that cycle. But finding all of the SCCs which participate in the cycle can in the worst case require traversing every SCC in the graph. Every attempt is made to avoid that, but passes must still exercise caution calling this routine repeatedly.
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 206 of file LazyCallGraph.cpp.
References llvm::CallingConv::C, llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::clear(), llvm::SmallPtrSetImplBase::clear(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::SmallVectorBase::empty(), llvm::SmallPtrSetImpl< PtrType >::erase(), I, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::lookup(), parent_begin(), parent_end(), llvm::SmallVectorImpl< T >::pop_back_val(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), and llvm::SmallVectorTemplateCommon< T >::size().
| void LazyCallGraph::SCC::insertIntraSCCEdge | ( | Node & | CallerN, |
| Node & | CalleeN | ||
| ) |
Insert an edge from one node in this SCC to another in this SCC.
By the definition of an SCC, this does not change the nature or make-up of any SCCs.
Definition at line 180 of file LazyCallGraph.cpp.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::lookup().
| void LazyCallGraph::SCC::insertOutgoingEdge | ( | Node & | CallerN, |
| Node & | CalleeN | ||
| ) |
Insert an edge whose tail is in this SCC and head is in some child SCC.
There must be an existing path from the caller to the callee. This operation is inexpensive and does not change the set of SCCs in the graph.
Definition at line 190 of file LazyCallGraph.cpp.
References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::lookup().
| bool llvm::LazyCallGraph::SCC::isAncestorOf | ( | const SCC & | C | ) | const [inline] |
Test if this SCC is an ancestor of C.
Definition at line 245 of file LazyCallGraph.h.
References isDescendantOf().
| bool llvm::LazyCallGraph::SCC::isChildOf | ( | const SCC & | C | ) | const [inline] |
Test if this SCC is a child of C.
Definition at line 248 of file LazyCallGraph.h.
References llvm::SmallPtrSetImpl< PtrType >::count().
Referenced by isDescendantOf(), and isParentOf().
| bool LazyCallGraph::SCC::isDescendantOf | ( | const SCC & | C | ) | const |
Test if this SCC is a descendant of C.
Definition at line 165 of file LazyCallGraph.cpp.
References llvm::SmallVectorBase::empty(), isChildOf(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back().
Referenced by isAncestorOf().
| bool llvm::LazyCallGraph::SCC::isParentOf | ( | const SCC & | C | ) | const [inline] |
Test if this SCC is a parent of C.
Definition at line 242 of file LazyCallGraph.h.
References isChildOf().
| parent_iterator llvm::LazyCallGraph::SCC::parent_begin | ( | ) | const [inline] |
Definition at line 234 of file LazyCallGraph.h.
References llvm::SmallPtrSetImpl< PtrType >::begin().
Referenced by insertIncomingEdge(), and parents().
| parent_iterator llvm::LazyCallGraph::SCC::parent_end | ( | ) | const [inline] |
Definition at line 235 of file LazyCallGraph.h.
References llvm::SmallPtrSetImpl< PtrType >::end().
Referenced by insertIncomingEdge(), and parents().
| iterator_range<parent_iterator> llvm::LazyCallGraph::SCC::parents | ( | ) | const [inline] |
Definition at line 237 of file LazyCallGraph.h.
References parent_begin(), and parent_end().
| void LazyCallGraph::SCC::removeInterSCCEdge | ( | Node & | CallerN, |
| Node & | CalleeN | ||
| ) |
Remove an edge whose source is in this SCC and target is *not*.
This removes an inter-SCC edge. All inter-SCC edges originating from this SCC have been fully explored by any in-flight DFS SCC formation, so this is always safe to call once you have the source SCC.
This operation does not change the set of SCCs or the members of the SCCs 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 324 of file LazyCallGraph.cpp.
References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::dbgs(), DEBUG, llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::LazyCallGraph::Node::getFunction(), llvm::Value::getName(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::lookup(), and llvm::SmallVectorTemplateBase< T, isPodLike >::push_back().
| SmallVector< LazyCallGraph::SCC *, 1 > LazyCallGraph::SCC::removeIntraSCCEdge | ( | Node & | CallerN, |
| Node & | CalleeN | ||
| ) |
Remove an edge which is entirely within this SCC.
Both the Caller and the Callee must be within this SCC. Removing such an edge make break cycles that form this SCC and thus this operation may change the SCC graph significantly. In particular, this operation will re-form new SCCs based on the remaining connectivity of the graph. The following invariants are guaranteed to hold after calling this method:
1) This SCC is still an SCC in the graph. 2) This SCC will be the parent of any new SCCs. Thus, this SCC is preserved as the root of any new SCC directed graph formed. 3) No SCC other than this SCC has its member set changed (this is inherent in the definition of removing such an edge). 4) All of the parent links of the SCC graph will be updated to reflect the new SCC structure. 5) All SCCs formed out of this SCC, excluding this SCC, will be returned in a vector. 6) The order of the SCCs in the vector will be a valid postorder traversal of the new SCCs.
These invariants are very important to ensure that we can build optimization pipeliens on top of the CGSCC pass manager which intelligently update the SCC graph without invalidating other parts of the SCC graph.
The runtime complexity of this method is, in the worst case, O(V+E) where V is the number of nodes in this SCC and E is the number of edges leaving the nodes in this SCC. Note that E includes both edges within this SCC and edges from this SCC to child SCCs. 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 457 of file LazyCallGraph.cpp.
References llvm::SmallVectorTemplateCommon< T, typename >::begin(), llvm::CallingConv::C, llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::erase(), llvm::SmallVectorImpl< T >::erase(), llvm::LazyCallGraph::Node::getFunction(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT >::lookup(), llvm::LibFunc::remove, and llvm::SmallVectorImpl< T >::swap().
friend class LazyCallGraph [friend] |
Definition at line 211 of file LazyCallGraph.h.
friend class LazyCallGraph::Node [friend] |
Definition at line 212 of file LazyCallGraph.h.
Generated on Thu Sep 18 2014 04:05:24 for LLVM by
1.7.6.1
Copyright © 2003-2014 University of Illinois at Urbana-Champaign.
All Rights Reserved.