diff options
Diffstat (limited to 'include/llvm/ADT/SCCIterator.h')
| -rw-r--r-- | include/llvm/ADT/SCCIterator.h | 311 |
1 files changed, 168 insertions, 143 deletions
diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h index 8ce4fd53bacd..bc74416ac88b 100644 --- a/include/llvm/ADT/SCCIterator.h +++ b/include/llvm/ADT/SCCIterator.h @@ -6,16 +6,18 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected -// components (SCCs) of a graph in O(N+E) time using Tarjan's DFS algorithm. -// -// The SCC iterator has the important property that if a node in SCC S1 has an -// edge to a node in SCC S2, then it visits S1 *after* S2. -// -// To visit S1 *before* S2, use the scc_iterator on the Inverse graph. -// (NOTE: This requires some simple wrappers and is not supported yet.) -// +/// \file +/// +/// This builds on the llvm/ADT/GraphTraits.h file to find the strongly +/// connected components (SCCs) of a graph in O(N+E) time using Tarjan's DFS +/// algorithm. +/// +/// The SCC iterator has the important property that if a node in SCC S1 has an +/// edge to a node in SCC S2, then it visits S1 *after* S2. +/// +/// To visit S1 *before* S2, use the scc_iterator on the Inverse graph. (NOTE: +/// This requires some simple wrappers and is not supported yet.) +/// //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_SCCITERATOR_H @@ -23,169 +25,112 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/iterator.h" #include <vector> namespace llvm { -//===----------------------------------------------------------------------===// -/// -/// scc_iterator - Enumerate the SCCs of a directed graph, in -/// reverse topological order of the SCC DAG. +/// \brief Enumerate the SCCs of a directed graph in reverse topological order +/// of the SCC DAG. /// -template<class GraphT, class GT = GraphTraits<GraphT> > +/// This is implemented using Tarjan's DFS algorithm using an internal stack to +/// build up a vector of nodes in a particular SCC. Note that it is a forward +/// iterator and thus you cannot backtrack or re-visit nodes. +template <class GraphT, class GT = GraphTraits<GraphT>> class scc_iterator - : public std::iterator<std::forward_iterator_tag, - std::vector<typename GT::NodeType>, ptrdiff_t> { - typedef typename GT::NodeType NodeType; + : public iterator_facade_base< + scc_iterator<GraphT, GT>, std::forward_iterator_tag, + const std::vector<typename GT::NodeType *>, ptrdiff_t> { + typedef typename GT::NodeType NodeType; typedef typename GT::ChildIteratorType ChildItTy; - typedef std::vector<NodeType*> SccTy; - typedef std::iterator<std::forward_iterator_tag, - std::vector<typename GT::NodeType>, ptrdiff_t> super; - typedef typename super::reference reference; - typedef typename super::pointer pointer; - - // The visit counters used to detect when a complete SCC is on the stack. - // visitNum is the global counter. - // nodeVisitNumbers are per-node visit numbers, also used as DFS flags. + typedef std::vector<NodeType *> SccTy; + typedef typename scc_iterator::reference reference; + + /// Element of VisitStack during DFS. + struct StackElement { + NodeType *Node; ///< The current node pointer. + ChildItTy NextChild; ///< The next child, modified inplace during DFS. + unsigned MinVisited; ///< Minimum uplink value of all children of Node. + + StackElement(NodeType *Node, const ChildItTy &Child, unsigned Min) + : Node(Node), NextChild(Child), MinVisited(Min) {} + + bool operator==(const StackElement &Other) const { + return Node == Other.Node && + NextChild == Other.NextChild && + MinVisited == Other.MinVisited; + } + }; + + /// The visit counters used to detect when a complete SCC is on the stack. + /// visitNum is the global counter. + /// + /// nodeVisitNumbers are per-node visit numbers, also used as DFS flags. unsigned visitNum; DenseMap<NodeType *, unsigned> nodeVisitNumbers; - // SCCNodeStack - Stack holding nodes of the SCC. + /// Stack holding nodes of the SCC. std::vector<NodeType *> SCCNodeStack; - // CurrentSCC - The current SCC, retrieved using operator*(). + /// The current SCC, retrieved using operator*(). SccTy CurrentSCC; - // VisitStack - Used to maintain the ordering. Top = current block - // First element is basic block pointer, second is the 'next child' to visit - std::vector<std::pair<NodeType *, ChildItTy> > VisitStack; - - // MinVisitNumStack - Stack holding the "min" values for each node in the DFS. - // This is used to track the minimum uplink values for all children of - // the corresponding node on the VisitStack. - std::vector<unsigned> MinVisitNumStack; - - // A single "visit" within the non-recursive DFS traversal. - void DFSVisitOne(NodeType *N) { - ++visitNum; // Global counter for the visit order - nodeVisitNumbers[N] = visitNum; - SCCNodeStack.push_back(N); - MinVisitNumStack.push_back(visitNum); - VisitStack.push_back(std::make_pair(N, GT::child_begin(N))); - //dbgs() << "TarjanSCC: Node " << N << - // " : visitNum = " << visitNum << "\n"; - } + /// DFS stack, Used to maintain the ordering. The top contains the current + /// node, the next child to visit, and the minimum uplink value of all child + std::vector<StackElement> VisitStack; - // The stack-based DFS traversal; defined below. - void DFSVisitChildren() { - assert(!VisitStack.empty()); - while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) { - // TOS has at least one more child so continue DFS - NodeType *childN = *VisitStack.back().second++; - if (!nodeVisitNumbers.count(childN)) { - // this node has never been seen. - DFSVisitOne(childN); - continue; - } - - unsigned childNum = nodeVisitNumbers[childN]; - if (MinVisitNumStack.back() > childNum) - MinVisitNumStack.back() = childNum; - } - } + /// A single "visit" within the non-recursive DFS traversal. + void DFSVisitOne(NodeType *N); - // Compute the next SCC using the DFS traversal. - void GetNextSCC() { - assert(VisitStack.size() == MinVisitNumStack.size()); - CurrentSCC.clear(); // Prepare to compute the next SCC - while (!VisitStack.empty()) { - DFSVisitChildren(); - assert(VisitStack.back().second ==GT::child_end(VisitStack.back().first)); - NodeType *visitingN = VisitStack.back().first; - unsigned minVisitNum = MinVisitNumStack.back(); - VisitStack.pop_back(); - MinVisitNumStack.pop_back(); - if (!MinVisitNumStack.empty() && MinVisitNumStack.back() > minVisitNum) - MinVisitNumStack.back() = minVisitNum; - - //dbgs() << "TarjanSCC: Popped node " << visitingN << - // " : minVisitNum = " << minVisitNum << "; Node visit num = " << - // nodeVisitNumbers[visitingN] << "\n"; - - if (minVisitNum != nodeVisitNumbers[visitingN]) - continue; - - // A full SCC is on the SCCNodeStack! It includes all nodes below - // visitingN on the stack. Copy those nodes to CurrentSCC, - // reset their minVisit values, and return (this suspends - // the DFS traversal till the next ++). - do { - CurrentSCC.push_back(SCCNodeStack.back()); - SCCNodeStack.pop_back(); - nodeVisitNumbers[CurrentSCC.back()] = ~0U; - } while (CurrentSCC.back() != visitingN); - return; - } - } + /// The stack-based DFS traversal; defined below. + void DFSVisitChildren(); + + /// Compute the next SCC using the DFS traversal. + void GetNextSCC(); - inline scc_iterator(NodeType *entryN) : visitNum(0) { + scc_iterator(NodeType *entryN) : visitNum(0) { DFSVisitOne(entryN); GetNextSCC(); } - inline scc_iterator() { /* End is when DFS stack is empty */ } -public: - typedef scc_iterator<GraphT, GT> _Self; + /// End is when the DFS stack is empty. + scc_iterator() {} - // Provide static "constructors"... - static inline _Self begin(const GraphT &G){return _Self(GT::getEntryNode(G));} - static inline _Self end (const GraphT &) { return _Self(); } +public: + static scc_iterator begin(const GraphT &G) { + return scc_iterator(GT::getEntryNode(G)); + } + static scc_iterator end(const GraphT &) { return scc_iterator(); } - // Direct loop termination test: I.isAtEnd() is more efficient than I == end() - inline bool isAtEnd() const { + /// \brief Direct loop termination test which is more efficient than + /// comparison with \c end(). + bool isAtEnd() const { assert(!CurrentSCC.empty() || VisitStack.empty()); return CurrentSCC.empty(); } - inline bool operator==(const _Self& x) const { + bool operator==(const scc_iterator &x) const { return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC; } - inline bool operator!=(const _Self& x) const { return !operator==(x); } - // Iterator traversal: forward iteration only - inline _Self& operator++() { // Preincrement + scc_iterator &operator++() { GetNextSCC(); return *this; } - inline _Self operator++(int) { // Postincrement - _Self tmp = *this; ++*this; return tmp; - } - // Retrieve a reference to the current SCC - inline const SccTy &operator*() const { - assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); - return CurrentSCC; - } - inline SccTy &operator*() { + reference operator*() const { assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); return CurrentSCC; } - // hasLoop() -- Test if the current SCC has a loop. If it has more than one - // node, this is trivially true. If not, it may still contain a loop if the - // node has an edge back to itself. - bool hasLoop() const { - assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); - if (CurrentSCC.size() > 1) return true; - NodeType *N = CurrentSCC.front(); - for (ChildItTy CI = GT::child_begin(N), CE=GT::child_end(N); CI != CE; ++CI) - if (*CI == N) - return true; - return false; - } + /// \brief Test if the current SCC has a loop. + /// + /// If the SCC has more than one node, this is trivially true. If not, it may + /// still contain a loop if the node has an edge back to itself. + bool hasLoop() const; - /// ReplaceNode - This informs the scc_iterator that the specified Old node - /// has been deleted, and New is to be used in its place. + /// This informs the \c scc_iterator that the specified \c Old node + /// has been deleted, and \c New is to be used in its place. void ReplaceNode(NodeType *Old, NodeType *New) { assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?"); nodeVisitNumbers[New] = nodeVisitNumbers[Old]; @@ -193,25 +138,105 @@ public: } }; +template <class GraphT, class GT> +void scc_iterator<GraphT, GT>::DFSVisitOne(NodeType *N) { + ++visitNum; + nodeVisitNumbers[N] = visitNum; + SCCNodeStack.push_back(N); + VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum)); +#if 0 // Enable if needed when debugging. + dbgs() << "TarjanSCC: Node " << N << + " : visitNum = " << visitNum << "\n"; +#endif +} + +template <class GraphT, class GT> +void scc_iterator<GraphT, GT>::DFSVisitChildren() { + assert(!VisitStack.empty()); + while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) { + // TOS has at least one more child so continue DFS + NodeType *childN = *VisitStack.back().NextChild++; + typename DenseMap<NodeType *, unsigned>::iterator Visited = + nodeVisitNumbers.find(childN); + if (Visited == nodeVisitNumbers.end()) { + // this node has never been seen. + DFSVisitOne(childN); + continue; + } + + unsigned childNum = Visited->second; + if (VisitStack.back().MinVisited > childNum) + VisitStack.back().MinVisited = childNum; + } +} + +template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() { + CurrentSCC.clear(); // Prepare to compute the next SCC + while (!VisitStack.empty()) { + DFSVisitChildren(); + + // Pop the leaf on top of the VisitStack. + NodeType *visitingN = VisitStack.back().Node; + unsigned minVisitNum = VisitStack.back().MinVisited; + assert(VisitStack.back().NextChild == GT::child_end(visitingN)); + VisitStack.pop_back(); + + // Propagate MinVisitNum to parent so we can detect the SCC starting node. + if (!VisitStack.empty() && VisitStack.back().MinVisited > minVisitNum) + VisitStack.back().MinVisited = minVisitNum; + +#if 0 // Enable if needed when debugging. + dbgs() << "TarjanSCC: Popped node " << visitingN << + " : minVisitNum = " << minVisitNum << "; Node visit num = " << + nodeVisitNumbers[visitingN] << "\n"; +#endif + + if (minVisitNum != nodeVisitNumbers[visitingN]) + continue; + + // A full SCC is on the SCCNodeStack! It includes all nodes below + // visitingN on the stack. Copy those nodes to CurrentSCC, + // reset their minVisit values, and return (this suspends + // the DFS traversal till the next ++). + do { + CurrentSCC.push_back(SCCNodeStack.back()); + SCCNodeStack.pop_back(); + nodeVisitNumbers[CurrentSCC.back()] = ~0U; + } while (CurrentSCC.back() != visitingN); + return; + } +} + +template <class GraphT, class GT> +bool scc_iterator<GraphT, GT>::hasLoop() const { + assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); + if (CurrentSCC.size() > 1) + return true; + NodeType *N = CurrentSCC.front(); + for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE; + ++CI) + if (*CI == N) + return true; + return false; + } -// Global constructor for the SCC iterator. -template <class T> -scc_iterator<T> scc_begin(const T &G) { +/// \brief Construct the begin iterator for a deduced graph type T. +template <class T> scc_iterator<T> scc_begin(const T &G) { return scc_iterator<T>::begin(G); } -template <class T> -scc_iterator<T> scc_end(const T &G) { +/// \brief Construct the end iterator for a deduced graph type T. +template <class T> scc_iterator<T> scc_end(const T &G) { return scc_iterator<T>::end(G); } -template <class T> -scc_iterator<Inverse<T> > scc_begin(const Inverse<T> &G) { +/// \brief Construct the begin iterator for a deduced graph type T's Inverse<T>. +template <class T> scc_iterator<Inverse<T> > scc_begin(const Inverse<T> &G) { return scc_iterator<Inverse<T> >::begin(G); } -template <class T> -scc_iterator<Inverse<T> > scc_end(const Inverse<T> &G) { +/// \brief Construct the end iterator for a deduced graph type T's Inverse<T>. +template <class T> scc_iterator<Inverse<T> > scc_end(const Inverse<T> &G) { return scc_iterator<Inverse<T> >::end(G); } |