1551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer//===- llvm/ADT/DepthFirstIterator.h - Depth First iterator -----*- 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//===----------------------------------------------------------------------===// 97461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 10551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer// This file builds on the ADT/GraphTraits.h file to build generic depth 114846f4b87a31797ba0bc6c96862a1128acf16149Chris Lattner// first graph iterator. This file exposes the following functions/types: 124846f4b87a31797ba0bc6c96862a1128acf16149Chris Lattner// 134846f4b87a31797ba0bc6c96862a1128acf16149Chris Lattner// df_begin/df_end/df_iterator 144846f4b87a31797ba0bc6c96862a1128acf16149Chris Lattner// * Normal depth-first iteration - visit a node and then all of its children. 154846f4b87a31797ba0bc6c96862a1128acf16149Chris Lattner// 164846f4b87a31797ba0bc6c96862a1128acf16149Chris Lattner// idf_begin/idf_end/idf_iterator 174846f4b87a31797ba0bc6c96862a1128acf16149Chris Lattner// * Depth-first iteration on the 'inverse' graph. 187461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 199061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// df_ext_begin/df_ext_end/df_ext_iterator 209061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// * Normal depth-first iteration - visit a node and then all of its children. 219061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// This iterator stores the 'visited' set in an external set, which allows 229061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// it to be more efficient, and allows external clients to use the set for 239061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// other purposes. 249061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// 259061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// idf_ext_begin/idf_ext_end/idf_ext_iterator 269061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// * Depth-first iteration on the 'inverse' graph. 279061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// This iterator stores the 'visited' set in an external set, which allows 289061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// it to be more efficient, and allows external clients to use the set for 299061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// other purposes. 309061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// 317461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner//===----------------------------------------------------------------------===// 327461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 33551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H 34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#define LLVM_ADT_DEPTHFIRSTITERATOR_H 357461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/ADT/iterator_range.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/GraphTraits.h" 38f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner#include "llvm/ADT/PointerIntPair.h" 39255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/ADT/SmallPtrSet.h" 407461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner#include <set> 41a2769a33c94f021a609a462b28ebea069eba6f74Misha Brukman#include <vector> 427461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 43d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 44d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 459061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// df_iterator_storage - A private class which is used to figure out where to 469061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// store the visited set. 479061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnertemplate<class SetType, bool External> // Non-external set 489061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnerclass df_iterator_storage { 499061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnerpublic: 509061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner SetType Visited; 519061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner}; 529061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 539061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnertemplate<class SetType> 549061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnerclass df_iterator_storage<SetType, true> { 559061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnerpublic: 569061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner df_iterator_storage(SetType &VSet) : Visited(VSet) {} 579061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {} 589061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner SetType &Visited; 599061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner}; 609061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 619061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 627461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Generic Depth First Iterator 63d3fb6714802d8e44b34980af8772cc3ed398e71aOwen Andersontemplate<class GraphT, 64d3fb6714802d8e44b34980af8772cc3ed398e71aOwen Andersonclass SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>, 659061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner bool ExtStorage = false, class GT = GraphTraits<GraphT> > 66f0891be8bdbeeadb39da5575273b6645755fa383Gabor Greifclass df_iterator : public std::iterator<std::forward_iterator_tag, 67f0891be8bdbeeadb39da5575273b6645755fa383Gabor Greif typename GT::NodeType, ptrdiff_t>, 689061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner public df_iterator_storage<SetType, ExtStorage> { 69f0891be8bdbeeadb39da5575273b6645755fa383Gabor Greif typedef std::iterator<std::forward_iterator_tag, 70f0891be8bdbeeadb39da5575273b6645755fa383Gabor Greif typename GT::NodeType, ptrdiff_t> super; 717f4dd472e35569efefbeffef096c490075e3e824Chris Lattner 727461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner typedef typename GT::NodeType NodeType; 737461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner typedef typename GT::ChildIteratorType ChildItTy; 74f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner typedef PointerIntPair<NodeType*, 1> PointerIntTy; 757461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 767461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // VisitStack - Used to maintain the ordering. Top = current block 777461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // First element is node pointer, second is the 'next child' to visit 78f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner // if the int in PointerIntTy is 0, the 'next child' to visit is invalid 79f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner std::vector<std::pair<PointerIntTy, ChildItTy> > VisitStack; 807461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerprivate: 814846f4b87a31797ba0bc6c96862a1128acf16149Chris Lattner inline df_iterator(NodeType *Node) { 829061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner this->Visited.insert(Node); 83f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0), 84f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner GT::child_begin(Node))); 85f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner } 86f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner inline df_iterator() { 87f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner // End is when stack is empty 887461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 899061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner inline df_iterator(NodeType *Node, SetType &S) 909061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner : df_iterator_storage<SetType, ExtStorage>(S) { 919061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner if (!S.count(Node)) { 92f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0), 93f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner GT::child_begin(Node))); 949061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner this->Visited.insert(Node); 959061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner } 969061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner } 979769ab22265b313171d201b5928688524a01bd87Misha Brukman inline df_iterator(SetType &S) 989061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner : df_iterator_storage<SetType, ExtStorage>(S) { 999061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner // End is when stack is empty 1009061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner } 1019061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 102f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner inline void toNext() { 103f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner do { 104f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner std::pair<PointerIntTy, ChildItTy> &Top = VisitStack.back(); 105f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner NodeType *Node = Top.first.getPointer(); 106f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner ChildItTy &It = Top.second; 107f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner if (!Top.first.getInt()) { 108f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner // now retrieve the real begin of the children before we dive in 109f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner It = GT::child_begin(Node); 110f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner Top.first.setInt(1); 111f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner } 112f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner 113f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner while (It != GT::child_end(Node)) { 114f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner NodeType *Next = *It++; 115f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner // Has our next sibling been visited? 116f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner if (Next && !this->Visited.count(Next)) { 117f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner // No, do it now. 118f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner this->Visited.insert(Next); 119f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner VisitStack.push_back(std::make_pair(PointerIntTy(Next, 0), 120f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner GT::child_begin(Next))); 121f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner return; 122f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner } 123f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner } 124f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner 125f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner // Oops, ran out of successors... go up a level on the stack. 126f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner VisitStack.pop_back(); 127f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner } while (!VisitStack.empty()); 128f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner } 129f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner 1307461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerpublic: 13102a31a5af68aaca1b54c7121f04cb56828ccefc2Chris Lattner typedef typename super::pointer pointer; 1329061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner typedef df_iterator<GraphT, SetType, ExtStorage, GT> _Self; 1337461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1347461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // Provide static begin and end methods as our public "constructors" 135ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikov static inline _Self begin(const GraphT& G) { 1364846f4b87a31797ba0bc6c96862a1128acf16149Chris Lattner return _Self(GT::getEntryNode(G)); 1377461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 138ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikov static inline _Self end(const GraphT& G) { return _Self(); } 1397461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1409061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner // Static begin and end methods as our public ctors for external iterators 141ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikov static inline _Self begin(const GraphT& G, SetType &S) { 1429061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner return _Self(GT::getEntryNode(G), S); 1439061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner } 144ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikov static inline _Self end(const GraphT& G, SetType &S) { return _Self(S); } 1457461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1469769ab22265b313171d201b5928688524a01bd87Misha Brukman inline bool operator==(const _Self& x) const { 147181436f11b740300b7032a7ac1ad848498a1a13eDan Gohman return VisitStack == x.VisitStack; 1487461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 1497461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline bool operator!=(const _Self& x) const { return !operator==(x); } 1507461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1519769ab22265b313171d201b5928688524a01bd87Misha Brukman inline pointer operator*() const { 152f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner return VisitStack.back().first.getPointer(); 1537461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 1547461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1557461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // This is a nonstandard operator-> that dereferences the pointer an extra 1567461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // time... so that you can actually call methods ON the Node, because 1577461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // the contained type is a pointer. This allows BBIt->getTerminator() f.e. 1587461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // 1597461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline NodeType *operator->() const { return operator*(); } 1607461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1617461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline _Self& operator++() { // Preincrement 162f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner toNext(); 163f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner return *this; 164f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner } 1659769ab22265b313171d201b5928688524a01bd87Misha Brukman 166f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner // skips all children of the current node and traverses to next node 167f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner // 168f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner inline _Self& skipChildren() { 169f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner VisitStack.pop_back(); 170f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner if (!VisitStack.empty()) 171f0395160f934eb278aa960de22dada5b297ddd8aChris Lattner toNext(); 1729769ab22265b313171d201b5928688524a01bd87Misha Brukman return *this; 1737461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 1747461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1757461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline _Self operator++(int) { // Postincrement 1769769ab22265b313171d201b5928688524a01bd87Misha Brukman _Self tmp = *this; ++*this; return tmp; 1777461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 1787461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1797461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // nodeVisited - return true if this iterator has already visited the 1807461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // specified node. This is public, and will probably be used to iterate over 1817461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // nodes that a depth first iteration did not find: ie unreachable nodes. 1827461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // 1839769ab22265b313171d201b5928688524a01bd87Misha Brukman inline bool nodeVisited(NodeType *Node) const { 1849061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner return this->Visited.count(Node) != 0; 1857461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 1866709c7bcdacfc3cc07bc0c47d3a3f9b47c699d3aJakob Stoklund Olesen 1876709c7bcdacfc3cc07bc0c47d3a3f9b47c699d3aJakob Stoklund Olesen /// getPathLength - Return the length of the path from the entry node to the 1886709c7bcdacfc3cc07bc0c47d3a3f9b47c699d3aJakob Stoklund Olesen /// current node, counting both nodes. 1896709c7bcdacfc3cc07bc0c47d3a3f9b47c699d3aJakob Stoklund Olesen unsigned getPathLength() const { return VisitStack.size(); } 1906709c7bcdacfc3cc07bc0c47d3a3f9b47c699d3aJakob Stoklund Olesen 191c8e41c591741b3da1077f7000274ad040bef8002Sylvestre Ledru /// getPath - Return the n'th node in the path from the entry node to the 1926709c7bcdacfc3cc07bc0c47d3a3f9b47c699d3aJakob Stoklund Olesen /// current node. 1936709c7bcdacfc3cc07bc0c47d3a3f9b47c699d3aJakob Stoklund Olesen NodeType *getPath(unsigned n) const { 1946709c7bcdacfc3cc07bc0c47d3a3f9b47c699d3aJakob Stoklund Olesen return VisitStack[n].first.getPointer(); 1956709c7bcdacfc3cc07bc0c47d3a3f9b47c699d3aJakob Stoklund Olesen } 1967461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 1977461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1987461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1997461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Provide global constructors that automatically figure out correct types... 2007461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 2017461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 202ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikovdf_iterator<T> df_begin(const T& G) { 2034846f4b87a31797ba0bc6c96862a1128acf16149Chris Lattner return df_iterator<T>::begin(G); 2047461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner} 2057461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 2067461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 207ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikovdf_iterator<T> df_end(const T& G) { 2087461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner return df_iterator<T>::end(G); 2097461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner} 2107461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 211dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// Provide an accessor method to use them in range-based patterns. 212dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate <class T> 213dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesiterator_range<df_iterator<T>> depth_first(const T& G) { 214dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return iterator_range<df_iterator<T>>(df_begin(G), df_end(G)); 215dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 216dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 2179061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// Provide global definitions of external depth first iterators... 2181e79609e304a24e0cad68534ddf3371479d33b86Chris Lattnertemplate <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> > 2199061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnerstruct df_ext_iterator : public df_iterator<T, SetTy, true> { 2209061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner df_ext_iterator(const df_iterator<T, SetTy, true> &V) 2219061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner : df_iterator<T, SetTy, true>(V) {} 2229061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner}; 2239061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 2249061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnertemplate <class T, class SetTy> 225ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikovdf_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) { 2269061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner return df_ext_iterator<T, SetTy>::begin(G, S); 2279061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner} 2289061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 2299061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnertemplate <class T, class SetTy> 230ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikovdf_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) { 2319061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner return df_ext_iterator<T, SetTy>::end(G, S); 2329061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner} 2339061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 2349061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 2357461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Provide global definitions of inverse depth first iterators... 236d3fb6714802d8e44b34980af8772cc3ed398e71aOwen Andersontemplate <class T, 237d3fb6714802d8e44b34980af8772cc3ed398e71aOwen Anderson class SetTy = llvm::SmallPtrSet<typename GraphTraits<T>::NodeType*, 8>, 2389061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner bool External = false> 2399061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnerstruct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> { 2409061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V) 2419061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner : df_iterator<Inverse<T>, SetTy, External>(V) {} 2427461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 2437461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 2447461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 245ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikovidf_iterator<T> idf_begin(const T& G) { 2463ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return idf_iterator<T>::begin(Inverse<T>(G)); 2477461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner} 2487461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 2497461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 250ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikovidf_iterator<T> idf_end(const T& G){ 2513ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return idf_iterator<T>::end(Inverse<T>(G)); 2527461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner} 2537461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 254dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// Provide an accessor method to use them in range-based patterns. 255dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate <class T> 256dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesiterator_range<idf_iterator<T>> inverse_depth_first(const T& G) { 257dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return iterator_range<idf_iterator<T>>(idf_begin(G), idf_end(G)); 258dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 259dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 2609061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner// Provide global definitions of external inverse depth first iterators... 2619061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnertemplate <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> > 2629061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnerstruct idf_ext_iterator : public idf_iterator<T, SetTy, true> { 2639061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner idf_ext_iterator(const idf_iterator<T, SetTy, true> &V) 2649061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner : idf_iterator<T, SetTy, true>(V) {} 2659061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V) 2669061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner : idf_iterator<T, SetTy, true>(V) {} 2679061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner}; 2689061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 2699061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnertemplate <class T, class SetTy> 270ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikovidf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) { 2713ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S); 2729061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner} 2739061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 2749061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattnertemplate <class T, class SetTy> 275ffe9e63c4a11352fd6437588fad516efdb46aa40Anton Korobeynikovidf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) { 2763ee87b6f9da0f63762ffaf0c4fcbc39514a059fbChris Lattner return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S); 2779061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner} 2789061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 279d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 2809061e992d5ee0c59c89ae7812c551bafd680a59cChris Lattner 2817461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner#endif 282