X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSCCIterator.h;h=48436c667474c8342e24b33f2ad809dfb82bfaef;hb=5449a1db40b75586c1daf70a14396295e7b3fe24;hp=e737f7c99072b29429cb2b112734ebd4b93fe0a5;hpb=5fe9171b38404bdb2296b849182769083c9d07b3;p=oota-llvm.git diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h index e737f7c9907..48436c66747 100644 --- a/include/llvm/ADT/SCCIterator.h +++ b/include/llvm/ADT/SCCIterator.h @@ -1,221 +1,220 @@ -//===-- Support/TarjanSCCIterator.h -Generic Tarjan SCC iterator -*- C++ -*--=// +//===---- ADT/SCCIterator.h - Strongly Connected Comp. Iter. ----*- C++ -*-===// // -// This builds on the Support/GraphTraits.h file to find the strongly -// connected components (SCCs) of a graph in O(N+E) time using -// Tarjan's DFS algorithm. +// The LLVM Compiler Infrastructure // -// 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 TarjanSCCIterator on the Inverse graph. +// This file is distributed under the University of Illinois Open Source +// 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.) +// //===----------------------------------------------------------------------===// -#ifndef LLVM_SUPPORT_TARJANSCC_ITERATOR_H -#define LLVM_SUPPORT_TARJANSCC_ITERATOR_H +#ifndef LLVM_ADT_SCCITERATOR_H +#define LLVM_ADT_SCCITERATOR_H -#include "Support/GraphTraits.h" -#include -#include +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/DenseMap.h" #include -#include -#include +namespace llvm { -//-------------------------------------------------------------------------- -// class SCC : A simple representation of an SCC in a generic Graph. -//-------------------------------------------------------------------------- - +//===----------------------------------------------------------------------===// +/// +/// scc_iterator - Enumerate the SCCs of a directed graph, in +/// reverse topological order of the SCC DAG. +/// template > -struct SCC: public std::vector { - - typedef typename GT::NodeType NodeType; +class scc_iterator + : public std::iterator, ptrdiff_t> { + typedef typename GT::NodeType NodeType; typedef typename GT::ChildIteratorType ChildItTy; - - typedef std::vector super; - typedef typename super::iterator iterator; - typedef typename super::const_iterator const_iterator; - typedef typename super::reverse_iterator reverse_iterator; - typedef typename super::const_reverse_iterator const_reverse_iterator; - - // HasLoop() -- Test if this 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 { - if (size() > 1) return true; - NodeType* N = front(); - for (ChildItTy CI=GT::child_begin(N), CE=GT::child_end(N); CI != CE; ++CI) - if (*CI == N) - return true; - return false; - } -}; - -//-------------------------------------------------------------------------- -// class TarjanSCC_iterator: Enumerate the SCCs of a directed graph, in -// reverse topological order of the SCC DAG. -//-------------------------------------------------------------------------- - -const unsigned long MAXLONG = (1 << (8 * sizeof(unsigned long) - 1)); - -namespace { - Statistic<> NumSCCs("NumSCCs", "Number of Strongly Connected Components"); - Statistic<> MaxSCCSize("MaxSCCSize", "Size of largest Strongly Connected Component"); -} - -template > -class TarjanSCC_iterator : public forward_iterator, ptrdiff_t> -{ - typedef SCC SccTy; - typedef forward_iterator super; + typedef std::vector SccTy; + typedef std::iterator, ptrdiff_t> super; typedef typename super::reference reference; typedef typename super::pointer pointer; - typedef typename GT::NodeType NodeType; - typedef typename GT::ChildIteratorType ChildItTy; // 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 long visitNum; - std::map nodeVisitNumbers; + unsigned visitNum; + DenseMap nodeVisitNumbers; // SCCNodeStack - Stack holding nodes of the SCC. - std::stack SCCNodeStack; + std::vector SCCNodeStack; // CurrentSCC - 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::stack > VisitStack; + std::vector > VisitStack; - // MinVistNumStack - Stack holding the "min" values for each node in the DFS. + // 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::stack MinVisitNumStack; + std::vector MinVisitNumStack; // A single "visit" within the non-recursive DFS traversal. - void DFSVisitOne(NodeType* N) { + void DFSVisitOne(NodeType *N) { ++visitNum; // Global counter for the visit order nodeVisitNumbers[N] = visitNum; - SCCNodeStack.push(N); - MinVisitNumStack.push(visitNum); - VisitStack.push(make_pair(N, GT::child_begin(N))); - DEBUG(std::cerr << "TarjanSCC: Node " << N << - " : visitNum = " << visitNum << "\n"); + 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"; } // The stack-based DFS traversal; defined below. void DFSVisitChildren() { assert(!VisitStack.empty()); - while (VisitStack.top().second != GT::child_end(VisitStack.top().first)) - { // TOS has at least one more child so continue DFS - NodeType *childN = *VisitStack.top().second++; - if (nodeVisitNumbers.find(childN) == nodeVisitNumbers.end()) - { // this node has never been seen - DFSVisitOne(childN); - } - else - { - unsigned long childNum = nodeVisitNumbers[childN]; - if (MinVisitNumStack.top() > childNum) - MinVisitNumStack.top() = childNum; - } + 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; + } } // 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.top().second==GT::child_end(VisitStack.top().first)); - NodeType* visitingN = VisitStack.top().first; - unsigned long minVisitNum = MinVisitNumStack.top(); - VisitStack.pop(); - MinVisitNumStack.pop(); - if (! MinVisitNumStack.empty() && MinVisitNumStack.top() > minVisitNum) - MinVisitNumStack.top() = minVisitNum; - - DEBUG(std::cerr << "TarjanSCC: Popped node " << visitingN << - " : minVisitNum = " << minVisitNum << "; Node visit num = " << - nodeVisitNumbers[visitingN] << "\n"); - - if (minVisitNum == nodeVisitNumbers[visitingN]) - { // 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.top()); - SCCNodeStack.pop(); - nodeVisitNumbers[CurrentSCC.back()] = MAXLONG; - } while (CurrentSCC.back() != visitingN); - - ++NumSCCs; - if (CurrentSCC.size() > MaxSCCSize) MaxSCCSize = CurrentSCC.size(); - - return; - } - } + 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; + } } - inline TarjanSCC_iterator(NodeType *entryN) : visitNum(0) { + inline scc_iterator(NodeType *entryN) : visitNum(0) { DFSVisitOne(entryN); GetNextSCC(); } - inline TarjanSCC_iterator() { /* End is when DFS stack is empty */ } + inline scc_iterator() { /* End is when DFS stack is empty */ } public: - typedef TarjanSCC_iterator _Self; + typedef scc_iterator _Self; // Provide static "constructors"... - static inline _Self begin(GraphT& G) { return _Self(GT::getEntryNode(G)); } - static inline _Self end (GraphT& G) { return _Self(); } + static inline _Self begin(const GraphT &G){return _Self(GT::getEntryNode(G));} + static inline _Self end (const GraphT &) { return _Self(); } - // Direct loop termination test (I.fini() is more efficient than I == end()) - inline bool fini() const { - return VisitStack.empty(); + // Direct loop termination test: I.isAtEnd() is more efficient than I == end() + inline bool isAtEnd() const { + assert(!CurrentSCC.empty() || VisitStack.empty()); + return CurrentSCC.empty(); } - inline bool operator==(const _Self& x) const { - return VisitStack == x.VisitStack; + inline bool operator==(const _Self& 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 GetNextSCC(); - return *this; + return *this; } inline _Self operator++(int) { // Postincrement - _Self tmp = *this; ++*this; return tmp; + _Self tmp = *this; ++*this; return tmp; } - // Retrieve a pointer to the current SCC. Returns NULL when done. - inline const SccTy* operator*() const { - assert(!CurrentSCC.empty() || fini()); - return CurrentSCC.empty()? NULL : &CurrentSCC; + // Retrieve a reference to the current SCC + inline const SccTy &operator*() const { + assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); + return CurrentSCC; } - inline SccTy* operator*() { - assert(!CurrentSCC.empty() || fini()); - return CurrentSCC.empty()? NULL : &CurrentSCC; + inline SccTy &operator*() { + 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; + } + + /// ReplaceNode - This informs the scc_iterator that the specified Old node + /// has been deleted, and 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]; + nodeVisitNumbers.erase(Old); } }; -// Global constructor for the Tarjan SCC iterator. Use *I == NULL or I.fini() -// to test termination efficiently, instead of I == the "end" iterator. +// Global constructor for the SCC iterator. template -TarjanSCC_iterator tarj_begin(T G) -{ - return TarjanSCC_iterator::begin(G); +scc_iterator scc_begin(const T &G) { + return scc_iterator::begin(G); } +template +scc_iterator scc_end(const T &G) { + return scc_iterator::end(G); +} -//===----------------------------------------------------------------------===// +template +scc_iterator > scc_begin(const Inverse &G) { + return scc_iterator >::begin(G); +} + +template +scc_iterator > scc_end(const Inverse &G) { + return scc_iterator >::end(G); +} + +} // End llvm namespace #endif