X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSCCIterator.h;h=e28f4caa5d76993668b45eacb9fc8de76e8ad839;hb=d6a2aab53e3c4fcd53399cfa6f66d62913e53663;hp=753dd55343c1b6812fd5d47900bfae7f73349275;hpb=94d1092c6a385ff077fb28773d9ba3ad15cb9a8d;p=oota-llvm.git diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h index 753dd55343c..e28f4caa5d7 100644 --- a/include/llvm/ADT/SCCIterator.h +++ b/include/llvm/ADT/SCCIterator.h @@ -1,55 +1,47 @@ -//===-- Support/TarjanSCCIterator.h - Tarjan SCC iterator -------*- C++ -*-===// +//===-- Support/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 SUPPORT_TARJANSCCITERATOR_H -#define SUPPORT_TARJANSCCITERATOR_H +#ifndef LLVM_ADT_SCCITERATOR_H +#define LLVM_ADT_SCCITERATOR_H -#include "Support/GraphTraits.h" -#include "Support/iterator" -#include +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/iterator.h" #include +#include -//-------------------------------------------------------------------------- -// class SCC - A simple representation of an SCC in a generic Graph. -//-------------------------------------------------------------------------- +namespace llvm { +//===----------------------------------------------------------------------===// +/// +/// 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 forward_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; -}; - -//-------------------------------------------------------------------------- -// class TarjanSCC_iterator: Enumerate the SCCs of a directed graph, in -// reverse topological order of the SCC DAG. -//-------------------------------------------------------------------------- - -template > -class TarjanSCC_iterator : public forward_iterator, ptrdiff_t> { - typedef SCC SccTy; + typedef std::vector SccTy; typedef forward_iterator 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. @@ -78,74 +70,69 @@ class TarjanSCC_iterator : public forward_iterator, ptrdiff_t> { nodeVisitNumbers[N] = visitNum; SCCNodeStack.push_back(N); MinVisitNumStack.push_back(visitNum); - VisitStack.push_back(make_pair(N, GT::child_begin(N))); - //DEBUG(std::cerr << "TarjanSCC: Node " << N << - // " : visitNum = " << visitNum << "\n"); + VisitStack.push_back(std::make_pair(N, GT::child_begin(N))); + //DOUT << "TarjanSCC: Node " << N << + // " : visitNum = " << visitNum << "\n"; } // 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.find(childN) == nodeVisitNumbers.end()) - { // this node has never been seen - DFSVisitOne(childN); - } - else - { - unsigned childNum = nodeVisitNumbers[childN]; - if (MinVisitNumStack.back() > childNum) - MinVisitNumStack.back() = 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); + } else { + 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.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; - - //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.back()); - SCCNodeStack.pop_back(); - nodeVisitNumbers[CurrentSCC.back()] = ~0UL; - } while (CurrentSCC.back() != visitingN); - 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; + + //DOUT << "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.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)); } @@ -157,7 +144,7 @@ public: return CurrentSCC.empty(); } - inline bool operator==(const _Self& x) const { + inline bool operator==(const _Self& x) const { return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC; } inline bool operator!=(const _Self& x) const { return !operator==(x); } @@ -165,18 +152,18 @@ public: // 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 reference to the current SCC - inline const SccTy &operator*() const { + inline const SccTy &operator*() const { assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); return CurrentSCC; } - inline SccTy &operator*() { + inline SccTy &operator*() { assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); return CurrentSCC; } @@ -196,15 +183,17 @@ public: }; -// Global constructor for the Tarjan SCC iterator. +// Global constructor for the SCC iterator. template -TarjanSCC_iterator tarj_begin(T G) { - return TarjanSCC_iterator::begin(G); +scc_iterator scc_begin(T G) { + return scc_iterator::begin(G); } template -TarjanSCC_iterator tarj_end(T G) { - return TarjanSCC_iterator::end(G); +scc_iterator scc_end(T G) { + return scc_iterator::end(G); } +} // End llvm namespace + #endif