14ed960061a1aa85bef288f06cb33c5c5b8706860Duncan Sands//===---- ADT/SCCIterator.h - Strongly Connected Comp. Iter. ----*- C++ -*-===// 29769ab22265b313171d201b5928688524a01bd87Misha Brukman// 3b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// The LLVM Compiler Infrastructure 4b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 79769ab22265b313171d201b5928688524a01bd87Misha Brukman// 8b2109ce97881269a610fa4afbcbca350e975174dJohn Criswell//===----------------------------------------------------------------------===// 936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \file 1036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 1136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// This builds on the llvm/ADT/GraphTraits.h file to find the strongly 1236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// connected components (SCCs) of a graph in O(N+E) time using Tarjan's DFS 1336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// algorithm. 1436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 1536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// The SCC iterator has the important property that if a node in SCC S1 has an 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// edge to a node in SCC S2, then it visits S1 *after* S2. 1736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// To visit S1 *before* S2, use the scc_iterator on the Inverse graph. (NOTE: 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// This requires some simple wrappers and is not supported yet.) 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 215fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve//===----------------------------------------------------------------------===// 225fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 23551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#ifndef LLVM_ADT_SCCITERATOR_H 24551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#define LLVM_ADT_SCCITERATOR_H 255fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 26270fc1077b07d7de1adbc3016d566d1757273b63Chris Lattner#include "llvm/ADT/DenseMap.h" 27255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/ADT/GraphTraits.h" 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/ADT/iterator.h" 29a2769a33c94f021a609a462b28ebea069eba6f74Misha Brukman#include <vector> 305fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 31d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 32d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Enumerate the SCCs of a directed graph in reverse topological order 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// of the SCC DAG. 35ff8fc078906da46b00aa102d724590b1b96e5526Chris Lattner/// 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// This is implemented using Tarjan's DFS algorithm using an internal stack to 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// build up a vector of nodes in a particular SCC. Note that it is a forward 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// iterator and thus you cannot backtrack or re-visit nodes. 39dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate <class GraphT, class GT = GraphTraits<GraphT>> 4055b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattnerclass scc_iterator 41dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : public iterator_facade_base< 42dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines scc_iterator<GraphT, GT>, std::forward_iterator_tag, 43dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const std::vector<typename GT::NodeType *>, ptrdiff_t> { 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef typename GT::NodeType NodeType; 455fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve typedef typename GT::ChildIteratorType ChildItTy; 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines typedef std::vector<NodeType *> SccTy; 47dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typedef typename scc_iterator::reference reference; 485fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 49dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// Element of VisitStack during DFS. 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines struct StackElement { 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NodeType *Node; ///< The current node pointer. 5236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ChildItTy NextChild; ///< The next child, modified inplace during DFS. 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned MinVisited; ///< Minimum uplink value of all children of Node. 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines StackElement(NodeType *Node, const ChildItTy &Child, unsigned Min) 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : Node(Node), NextChild(Child), MinVisited(Min) {} 5736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool operator==(const StackElement &Other) const { 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Node == Other.Node && 6036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NextChild == Other.NextChild && 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MinVisited == Other.MinVisited; 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines }; 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// The visit counters used to detect when a complete SCC is on the stack. 66dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// visitNum is the global counter. 67dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// 68dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// nodeVisitNumbers are per-node visit numbers, also used as DFS flags. 6922ab2a16e5477d96d579c04a9798a6cddd277434Chris Lattner unsigned visitNum; 70270fc1077b07d7de1adbc3016d566d1757273b63Chris Lattner DenseMap<NodeType *, unsigned> nodeVisitNumbers; 715fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 72dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// Stack holding nodes of the SCC. 7322ab2a16e5477d96d579c04a9798a6cddd277434Chris Lattner std::vector<NodeType *> SCCNodeStack; 745fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// The current SCC, retrieved using operator*(). 765fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve SccTy CurrentSCC; 775fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 78dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// DFS stack, Used to maintain the ordering. The top contains the current 79dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// node, the next child to visit, and the minimum uplink value of all child 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::vector<StackElement> VisitStack; 815fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 82dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// A single "visit" within the non-recursive DFS traversal. 83dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void DFSVisitOne(NodeType *N); 845fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// The stack-based DFS traversal; defined below. 86dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void DFSVisitChildren(); 875fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 88dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// Compute the next SCC using the DFS traversal. 89dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void GetNextSCC(); 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 91dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines scc_iterator(NodeType *entryN) : visitNum(0) { 925fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve DFSVisitOne(entryN); 935fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve GetNextSCC(); 945fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve } 955fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 96dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// End is when the DFS stack is empty. 97dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines scc_iterator() {} 985fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 9936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinespublic: 100dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static scc_iterator begin(const GraphT &G) { 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return scc_iterator(GT::getEntryNode(G)); 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 103dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static scc_iterator end(const GraphT &) { return scc_iterator(); } 1045fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Direct loop termination test which is more efficient than 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// comparison with \c end(). 107dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool isAtEnd() const { 1081818275956b339de89ac57d90d37a88c3566048eVikram S. Adve assert(!CurrentSCC.empty() || VisitStack.empty()); 1091818275956b339de89ac57d90d37a88c3566048eVikram S. Adve return CurrentSCC.empty(); 1105fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve } 1115fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 112dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool operator==(const scc_iterator &x) const { 1131818275956b339de89ac57d90d37a88c3566048eVikram S. Adve return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC; 1145fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve } 1155fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines scc_iterator &operator++() { 1175fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve GetNextSCC(); 1189769ab22265b313171d201b5928688524a01bd87Misha Brukman return *this; 1195fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve } 1205fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 121dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines reference operator*() const { 122b55cae23cb9bd6661093e8c2822be4fd721587e1Chris Lattner assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); 123b55cae23cb9bd6661093e8c2822be4fd721587e1Chris Lattner return CurrentSCC; 1245fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve } 12594d1092c6a385ff077fb28773d9ba3ad15cb9a8dChris Lattner 12636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// \brief Test if the current SCC has a loop. 12736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// 12836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// If the SCC has more than one node, this is trivially true. If not, it may 12936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// still contain a loop if the node has an edge back to itself. 130dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool hasLoop() const; 131dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 132dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// This informs the \c scc_iterator that the specified \c Old node 133dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines /// has been deleted, and \c New is to be used in its place. 134dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void ReplaceNode(NodeType *Old, NodeType *New) { 135dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?"); 136dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines nodeVisitNumbers[New] = nodeVisitNumbers[Old]; 137dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines nodeVisitNumbers.erase(Old); 138dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 139dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines}; 140dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 141dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate <class GraphT, class GT> 142dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid scc_iterator<GraphT, GT>::DFSVisitOne(NodeType *N) { 143dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++visitNum; 144dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines nodeVisitNumbers[N] = visitNum; 145dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SCCNodeStack.push_back(N); 146dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum)); 147dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#if 0 // Enable if needed when debugging. 148dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << "TarjanSCC: Node " << N << 149dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " : visitNum = " << visitNum << "\n"; 150dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#endif 151dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 152dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 153dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate <class GraphT, class GT> 154dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid scc_iterator<GraphT, GT>::DFSVisitChildren() { 155dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(!VisitStack.empty()); 156dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) { 157dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // TOS has at least one more child so continue DFS 158dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NodeType *childN = *VisitStack.back().NextChild++; 159dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typename DenseMap<NodeType *, unsigned>::iterator Visited = 160dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines nodeVisitNumbers.find(childN); 161dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Visited == nodeVisitNumbers.end()) { 162dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // this node has never been seen. 163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DFSVisitOne(childN); 164dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 165dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 166dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 167dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines unsigned childNum = Visited->second; 168dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (VisitStack.back().MinVisited > childNum) 169dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines VisitStack.back().MinVisited = childNum; 170dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 171dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 172dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 173dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() { 174dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CurrentSCC.clear(); // Prepare to compute the next SCC 175dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines while (!VisitStack.empty()) { 176dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DFSVisitChildren(); 177dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 178dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Pop the leaf on top of the VisitStack. 179dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NodeType *visitingN = VisitStack.back().Node; 180dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines unsigned minVisitNum = VisitStack.back().MinVisited; 181dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(VisitStack.back().NextChild == GT::child_end(visitingN)); 182dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines VisitStack.pop_back(); 183dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 184dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Propagate MinVisitNum to parent so we can detect the SCC starting node. 185dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!VisitStack.empty() && VisitStack.back().MinVisited > minVisitNum) 186dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines VisitStack.back().MinVisited = minVisitNum; 187dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 188dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#if 0 // Enable if needed when debugging. 189dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << "TarjanSCC: Popped node " << visitingN << 190dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines " : minVisitNum = " << minVisitNum << "; Node visit num = " << 191dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines nodeVisitNumbers[visitingN] << "\n"; 192dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#endif 193dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 194dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (minVisitNum != nodeVisitNumbers[visitingN]) 195dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 196dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 197dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // A full SCC is on the SCCNodeStack! It includes all nodes below 198dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // visitingN on the stack. Copy those nodes to CurrentSCC, 199dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // reset their minVisit values, and return (this suspends 200dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // the DFS traversal till the next ++). 201dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines do { 202dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines CurrentSCC.push_back(SCCNodeStack.back()); 203dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SCCNodeStack.pop_back(); 204dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines nodeVisitNumbers[CurrentSCC.back()] = ~0U; 205dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } while (CurrentSCC.back() != visitingN); 206dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 207dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 208dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 209dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 210dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate <class GraphT, class GT> 211dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool scc_iterator<GraphT, GT>::hasLoop() const { 21294d1092c6a385ff077fb28773d9ba3ad15cb9a8dChris Lattner assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); 21336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (CurrentSCC.size() > 1) 21436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 21594d1092c6a385ff077fb28773d9ba3ad15cb9a8dChris Lattner NodeType *N = CurrentSCC.front(); 21636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE; 21736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++CI) 21894d1092c6a385ff077fb28773d9ba3ad15cb9a8dChris Lattner if (*CI == N) 21994d1092c6a385ff077fb28773d9ba3ad15cb9a8dChris Lattner return true; 22094d1092c6a385ff077fb28773d9ba3ad15cb9a8dChris Lattner return false; 22194d1092c6a385ff077fb28773d9ba3ad15cb9a8dChris Lattner } 222b08904093ab97b0c0ef84f5834b4834c188cb44dDuncan Sands 22336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Construct the begin iterator for a deduced graph type T. 22436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate <class T> scc_iterator<T> scc_begin(const T &G) { 22555b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner return scc_iterator<T>::begin(G); 2265fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve} 2275fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 22836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Construct the end iterator for a deduced graph type T. 22936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate <class T> scc_iterator<T> scc_end(const T &G) { 23055b2eb3ef828819a623444ce966e70ad86ad6da4Chris Lattner return scc_iterator<T>::end(G); 231169f8b838b3f3be75d605251ba3bdcc0ad09d795Chris Lattner} 2325fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve 23336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Construct the begin iterator for a deduced graph type T's Inverse<T>. 23436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate <class T> scc_iterator<Inverse<T> > scc_begin(const Inverse<T> &G) { 2358b146240a2883fdbf0a7ad856df84a56c6f0d3d1Chris Lattner return scc_iterator<Inverse<T> >::begin(G); 2364a20c7a0a9ffa2b60668b1b8c39e550531dbcbb1Duncan Sands} 2374a20c7a0a9ffa2b60668b1b8c39e550531dbcbb1Duncan Sands 23836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// \brief Construct the end iterator for a deduced graph type T's Inverse<T>. 23936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestemplate <class T> scc_iterator<Inverse<T> > scc_end(const Inverse<T> &G) { 2408b146240a2883fdbf0a7ad856df84a56c6f0d3d1Chris Lattner return scc_iterator<Inverse<T> >::end(G); 2414a20c7a0a9ffa2b60668b1b8c39e550531dbcbb1Duncan Sands} 2424a20c7a0a9ffa2b60668b1b8c39e550531dbcbb1Duncan Sands 243d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 244d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2455fe9171b38404bdb2296b849182769083c9d07b3Vikram S. Adve#endif 246