X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSCCIterator.h;h=48436c667474c8342e24b33f2ad809dfb82bfaef;hb=5d37976090df34f003e5128e39593b763be0ca71;hp=2ea780ca92dc2ffe84a9fd897228aec8a2921100;hpb=de0579d94640fa4f32aaa618e954f9504db6da4d;p=oota-llvm.git diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h index 2ea780ca92d..48436c66747 100644 --- a/include/llvm/ADT/SCCIterator.h +++ b/include/llvm/ADT/SCCIterator.h @@ -1,30 +1,29 @@ -//===-- Support/SCCIterator.h - SCC iterator --------------------*- C++ -*-===// -// +//===---- ADT/SCCIterator.h - Strongly Connected Comp. Iter. ----*- C++ -*-===// +// // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// //===----------------------------------------------------------------------===// // -// This builds on the Support/GraphTraits.h file to find the strongly connected +// 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_SCCITERATOR_H -#define SUPPORT_SCCITERATOR_H +#ifndef LLVM_ADT_SCCITERATOR_H +#define LLVM_ADT_SCCITERATOR_H -#include "Support/GraphTraits.h" -#include "Support/iterator" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/DenseMap.h" #include -#include namespace llvm { @@ -35,11 +34,13 @@ namespace llvm { /// template > class scc_iterator - : public forward_iterator, ptrdiff_t> { + : public std::iterator, ptrdiff_t> { typedef typename GT::NodeType NodeType; typedef typename GT::ChildIteratorType ChildItTy; typedef std::vector SccTy; - typedef forward_iterator super; + typedef std::iterator, ptrdiff_t> super; typedef typename super::reference reference; typedef typename super::pointer pointer; @@ -47,7 +48,7 @@ class scc_iterator // visitNum is the global counter. // nodeVisitNumbers are per-node visit numbers, also used as DFS flags. unsigned visitNum; - std::map nodeVisitNumbers; + DenseMap nodeVisitNumbers; // SCCNodeStack - Stack holding nodes of the SCC. std::vector SCCNodeStack; @@ -59,20 +60,20 @@ class scc_iterator // First element is basic block pointer, second is the 'next child' to visit 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::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_back(N); MinVisitNumStack.push_back(visitNum); VisitStack.push_back(std::make_pair(N, GT::child_begin(N))); - //DEBUG(std::cerr << "TarjanSCC: Node " << N << - // " : visitNum = " << visitNum << "\n"); + //dbgs() << "TarjanSCC: Node " << N << + // " : visitNum = " << visitNum << "\n"; } // The stack-based DFS traversal; defined below. @@ -82,13 +83,14 @@ class scc_iterator // 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 + // this node has never been seen. DFSVisitOne(childN); - } else { - unsigned childNum = nodeVisitNumbers[childN]; - if (MinVisitNumStack.back() > childNum) - MinVisitNumStack.back() = childNum; + continue; } + + unsigned childNum = nodeVisitNumbers[childN]; + if (MinVisitNumStack.back() > childNum) + MinVisitNumStack.back() = childNum; } } @@ -99,29 +101,30 @@ class scc_iterator while (!VisitStack.empty()) { DFSVisitChildren(); assert(VisitStack.back().second ==GT::child_end(VisitStack.back().first)); - NodeType* visitingN = 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 << + //dbgs() << "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; - } + // 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; } } @@ -135,16 +138,16 @@ public: 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 { + // 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 { + inline bool operator==(const _Self& x) const { return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC; } inline bool operator!=(const _Self& x) const { return !operator==(x); } @@ -152,18 +155,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; } @@ -180,20 +183,38 @@ public: 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 SCC iterator. template -scc_iterator scc_begin(T G) { +scc_iterator scc_begin(const T &G) { return scc_iterator::begin(G); } template -scc_iterator scc_end(T G) { +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