LLVM API Documentation
00001 //===- llvm/ADT/DepthFirstIterator.h - Depth First iterator -----*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file builds on the ADT/GraphTraits.h file to build generic depth 00011 // first graph iterator. This file exposes the following functions/types: 00012 // 00013 // df_begin/df_end/df_iterator 00014 // * Normal depth-first iteration - visit a node and then all of its children. 00015 // 00016 // idf_begin/idf_end/idf_iterator 00017 // * Depth-first iteration on the 'inverse' graph. 00018 // 00019 // df_ext_begin/df_ext_end/df_ext_iterator 00020 // * Normal depth-first iteration - visit a node and then all of its children. 00021 // This iterator stores the 'visited' set in an external set, which allows 00022 // it to be more efficient, and allows external clients to use the set for 00023 // other purposes. 00024 // 00025 // idf_ext_begin/idf_ext_end/idf_ext_iterator 00026 // * Depth-first iteration on the 'inverse' graph. 00027 // This iterator stores the 'visited' set in an external set, which allows 00028 // it to be more efficient, and allows external clients to use the set for 00029 // other purposes. 00030 // 00031 //===----------------------------------------------------------------------===// 00032 00033 #ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H 00034 #define LLVM_ADT_DEPTHFIRSTITERATOR_H 00035 00036 #include "llvm/ADT/GraphTraits.h" 00037 #include "llvm/ADT/iterator.h" 00038 #include "llvm/ADT/SmallPtrSet.h" 00039 #include "llvm/ADT/PointerIntPair.h" 00040 #include <set> 00041 #include <vector> 00042 00043 namespace llvm { 00044 00045 // df_iterator_storage - A private class which is used to figure out where to 00046 // store the visited set. 00047 template<class SetType, bool External> // Non-external set 00048 class df_iterator_storage { 00049 public: 00050 SetType Visited; 00051 }; 00052 00053 template<class SetType> 00054 class df_iterator_storage<SetType, true> { 00055 public: 00056 df_iterator_storage(SetType &VSet) : Visited(VSet) {} 00057 df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {} 00058 SetType &Visited; 00059 }; 00060 00061 00062 // Generic Depth First Iterator 00063 template<class GraphT, 00064 class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>, 00065 bool ExtStorage = false, class GT = GraphTraits<GraphT> > 00066 class df_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t>, 00067 public df_iterator_storage<SetType, ExtStorage> { 00068 typedef forward_iterator<typename GT::NodeType, ptrdiff_t> super; 00069 00070 typedef typename GT::NodeType NodeType; 00071 typedef typename GT::ChildIteratorType ChildItTy; 00072 typedef PointerIntPair<NodeType*, 1> PointerIntTy; 00073 00074 // VisitStack - Used to maintain the ordering. Top = current block 00075 // First element is node pointer, second is the 'next child' to visit 00076 // if the int in PointerIntTy is 0, the 'next child' to visit is invalid 00077 std::vector<std::pair<PointerIntTy, ChildItTy> > VisitStack; 00078 private: 00079 inline df_iterator(NodeType *Node) { 00080 this->Visited.insert(Node); 00081 VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0), 00082 GT::child_begin(Node))); 00083 } 00084 inline df_iterator() { 00085 // End is when stack is empty 00086 } 00087 inline df_iterator(NodeType *Node, SetType &S) 00088 : df_iterator_storage<SetType, ExtStorage>(S) { 00089 if (!S.count(Node)) { 00090 VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0), 00091 GT::child_begin(Node))); 00092 this->Visited.insert(Node); 00093 } 00094 } 00095 inline df_iterator(SetType &S) 00096 : df_iterator_storage<SetType, ExtStorage>(S) { 00097 // End is when stack is empty 00098 } 00099 00100 inline void toNext() { 00101 do { 00102 std::pair<PointerIntTy, ChildItTy> &Top = VisitStack.back(); 00103 NodeType *Node = Top.first.getPointer(); 00104 ChildItTy &It = Top.second; 00105 if (!Top.first.getInt()) { 00106 // now retrieve the real begin of the children before we dive in 00107 It = GT::child_begin(Node); 00108 Top.first.setInt(1); 00109 } 00110 00111 while (It != GT::child_end(Node)) { 00112 NodeType *Next = *It++; 00113 // Has our next sibling been visited? 00114 if (Next && !this->Visited.count(Next)) { 00115 // No, do it now. 00116 this->Visited.insert(Next); 00117 VisitStack.push_back(std::make_pair(PointerIntTy(Next, 0), 00118 GT::child_begin(Next))); 00119 return; 00120 } 00121 } 00122 00123 // Oops, ran out of successors... go up a level on the stack. 00124 VisitStack.pop_back(); 00125 } while (!VisitStack.empty()); 00126 } 00127 00128 public: 00129 typedef typename super::pointer pointer; 00130 typedef df_iterator<GraphT, SetType, ExtStorage, GT> _Self; 00131 00132 // Provide static begin and end methods as our public "constructors" 00133 static inline _Self begin(const GraphT& G) { 00134 return _Self(GT::getEntryNode(G)); 00135 } 00136 static inline _Self end(const GraphT& G) { return _Self(); } 00137 00138 // Static begin and end methods as our public ctors for external iterators 00139 static inline _Self begin(const GraphT& G, SetType &S) { 00140 return _Self(GT::getEntryNode(G), S); 00141 } 00142 static inline _Self end(const GraphT& G, SetType &S) { return _Self(S); } 00143 00144 inline bool operator==(const _Self& x) const { 00145 return VisitStack.size() == x.VisitStack.size() && 00146 VisitStack == x.VisitStack; 00147 } 00148 inline bool operator!=(const _Self& x) const { return !operator==(x); } 00149 00150 inline pointer operator*() const { 00151 return VisitStack.back().first.getPointer(); 00152 } 00153 00154 // This is a nonstandard operator-> that dereferences the pointer an extra 00155 // time... so that you can actually call methods ON the Node, because 00156 // the contained type is a pointer. This allows BBIt->getTerminator() f.e. 00157 // 00158 inline NodeType *operator->() const { return operator*(); } 00159 00160 inline _Self& operator++() { // Preincrement 00161 toNext(); 00162 return *this; 00163 } 00164 00165 // skips all children of the current node and traverses to next node 00166 // 00167 inline _Self& skipChildren() { 00168 VisitStack.pop_back(); 00169 if (!VisitStack.empty()) 00170 toNext(); 00171 return *this; 00172 } 00173 00174 inline _Self operator++(int) { // Postincrement 00175 _Self tmp = *this; ++*this; return tmp; 00176 } 00177 00178 // nodeVisited - return true if this iterator has already visited the 00179 // specified node. This is public, and will probably be used to iterate over 00180 // nodes that a depth first iteration did not find: ie unreachable nodes. 00181 // 00182 inline bool nodeVisited(NodeType *Node) const { 00183 return this->Visited.count(Node) != 0; 00184 } 00185 }; 00186 00187 00188 // Provide global constructors that automatically figure out correct types... 00189 // 00190 template <class T> 00191 df_iterator<T> df_begin(const T& G) { 00192 return df_iterator<T>::begin(G); 00193 } 00194 00195 template <class T> 00196 df_iterator<T> df_end(const T& G) { 00197 return df_iterator<T>::end(G); 00198 } 00199 00200 // Provide global definitions of external depth first iterators... 00201 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> > 00202 struct df_ext_iterator : public df_iterator<T, SetTy, true> { 00203 df_ext_iterator(const df_iterator<T, SetTy, true> &V) 00204 : df_iterator<T, SetTy, true>(V) {} 00205 }; 00206 00207 template <class T, class SetTy> 00208 df_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) { 00209 return df_ext_iterator<T, SetTy>::begin(G, S); 00210 } 00211 00212 template <class T, class SetTy> 00213 df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) { 00214 return df_ext_iterator<T, SetTy>::end(G, S); 00215 } 00216 00217 00218 // Provide global definitions of inverse depth first iterators... 00219 template <class T, 00220 class SetTy = llvm::SmallPtrSet<typename GraphTraits<T>::NodeType*, 8>, 00221 bool External = false> 00222 struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> { 00223 idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V) 00224 : df_iterator<Inverse<T>, SetTy, External>(V) {} 00225 }; 00226 00227 template <class T> 00228 idf_iterator<T> idf_begin(const T& G) { 00229 return idf_iterator<T>::begin(Inverse<T>(G)); 00230 } 00231 00232 template <class T> 00233 idf_iterator<T> idf_end(const T& G){ 00234 return idf_iterator<T>::end(Inverse<T>(G)); 00235 } 00236 00237 // Provide global definitions of external inverse depth first iterators... 00238 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> > 00239 struct idf_ext_iterator : public idf_iterator<T, SetTy, true> { 00240 idf_ext_iterator(const idf_iterator<T, SetTy, true> &V) 00241 : idf_iterator<T, SetTy, true>(V) {} 00242 idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V) 00243 : idf_iterator<T, SetTy, true>(V) {} 00244 }; 00245 00246 template <class T, class SetTy> 00247 idf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) { 00248 return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S); 00249 } 00250 00251 template <class T, class SetTy> 00252 idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) { 00253 return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S); 00254 } 00255 00256 } // End llvm namespace 00257 00258 #endif