1551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer//===- llvm/ADT/PostOrderIterator.h - PostOrder 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 a generic graph 117461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// post order iterator. This should work over any graph type that has a 127461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// GraphTraits specialization. 137461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 147461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner//===----------------------------------------------------------------------===// 157461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 16551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#ifndef LLVM_ADT_POSTORDERITERATOR_H 17551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#define LLVM_ADT_POSTORDERITERATOR_H 187461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 19551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/GraphTraits.h" 20be24f1b7fb093380f9bac489f4b70a7e133be7b5Owen Anderson#include "llvm/ADT/SmallPtrSet.h" 217461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner#include <set> 22410354fe0c052141dadeca939395743f8dd58e38Chris Lattner#include <vector> 237461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 24d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 25d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 263a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<class SetType, bool External> // Non-external set 273a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanclass po_iterator_storage { 283a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanpublic: 293a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman SetType Visited; 303a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman}; 313a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 325207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick/// DFSetTraits - Allow the SetType used to record depth-first search results to 335207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick/// optionally record node postorder. 345207936a24ab9e0bfaa10e798625df65143e3716Andrew Tricktemplate<class SetType> 355207936a24ab9e0bfaa10e798625df65143e3716Andrew Trickstruct DFSetTraits { 365207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick static void finishPostorder( 375207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick typename SetType::iterator::value_type, SetType &) {} 385207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick}; 395207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick 403a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<class SetType> 413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanclass po_iterator_storage<SetType, true> { 423a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanpublic: 433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman po_iterator_storage(SetType &VSet) : Visited(VSet) {} 443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman po_iterator_storage(const po_iterator_storage &S) : Visited(S.Visited) {} 453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman SetType &Visited; 463a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman}; 473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 483a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<class GraphT, 49be24f1b7fb093380f9bac489f4b70a7e133be7b5Owen Anderson class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>, 50be24f1b7fb093380f9bac489f4b70a7e133be7b5Owen Anderson bool ExtStorage = false, 51be24f1b7fb093380f9bac489f4b70a7e133be7b5Owen Anderson class GT = GraphTraits<GraphT> > 527362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greifclass po_iterator : public std::iterator<std::forward_iterator_tag, 537362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif typename GT::NodeType, ptrdiff_t>, 543a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman public po_iterator_storage<SetType, ExtStorage> { 557362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif typedef std::iterator<std::forward_iterator_tag, 567362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif typename GT::NodeType, ptrdiff_t> super; 577461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner typedef typename GT::NodeType NodeType; 587461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner typedef typename GT::ChildIteratorType ChildItTy; 593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 607461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // VisitStack - Used to maintain the ordering. Top = current block 617461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // First element is basic block pointer, second is the 'next child' to visit 622dac4c1b519feaf1ef63514f07fa16aa5dc7d89aDuncan Sands std::vector<std::pair<NodeType *, ChildItTy> > VisitStack; 637461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 647461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner void traverseChild() { 65a0994b1a13ef3437f5442b9fec1750b150da175aDuncan Sands while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) { 66a0994b1a13ef3437f5442b9fec1750b150da175aDuncan Sands NodeType *BB = *VisitStack.back().second++; 67697ffd61a47af38ac932628e942d75952f901fcdDan Gohman if (this->Visited.insert(BB)) { // If the block is not visited... 68a0994b1a13ef3437f5442b9fec1750b150da175aDuncan Sands VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); 697461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 707461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 717461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 727461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 737461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline po_iterator(NodeType *BB) { 74767a033a5cc6a8003d72a7a243cb60d9bae674d3Chris Lattner this->Visited.insert(BB); 75a0994b1a13ef3437f5442b9fec1750b150da175aDuncan Sands VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); 767461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner traverseChild(); 777461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 783a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline po_iterator() {} // End is when stack is empty. 793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline po_iterator(NodeType *BB, SetType &S) : 81151f369c539d77c50f1c4eeb79659666a620d679Chris Lattner po_iterator_storage<SetType, ExtStorage>(S) { 82697ffd61a47af38ac932628e942d75952f901fcdDan Gohman if (this->Visited.insert(BB)) { 83a0994b1a13ef3437f5442b9fec1750b150da175aDuncan Sands VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB))); 843a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman traverseChild(); 853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 873a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman inline po_iterator(SetType &S) : 89151f369c539d77c50f1c4eeb79659666a620d679Chris Lattner po_iterator_storage<SetType, ExtStorage>(S) { 903a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } // End is when stack is empty. 917461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerpublic: 92d091d85c15d56adca38f3522ff4ac0997141e326Chris Lattner typedef typename super::pointer pointer; 933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman typedef po_iterator<GraphT, SetType, ExtStorage, GT> _Self; 947461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 957461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // Provide static "constructors"... 967461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner static inline _Self begin(GraphT G) { return _Self(GT::getEntryNode(G)); } 977461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner static inline _Self end (GraphT G) { return _Self(); } 987461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 993a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman static inline _Self begin(GraphT G, SetType &S) { 1003a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return _Self(GT::getEntryNode(G), S); 1013a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman } 1023a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman static inline _Self end (GraphT G, SetType &S) { return _Self(S); } 1033a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1049769ab22265b313171d201b5928688524a01bd87Misha Brukman inline bool operator==(const _Self& x) const { 1057461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner return VisitStack == x.VisitStack; 1067461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 1077461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline bool operator!=(const _Self& x) const { return !operator==(x); } 1087461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1099769ab22265b313171d201b5928688524a01bd87Misha Brukman inline pointer operator*() const { 110a0994b1a13ef3437f5442b9fec1750b150da175aDuncan Sands return VisitStack.back().first; 1117461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 1127461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1137461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // This is a nonstandard operator-> that dereferences the pointer an extra 1147461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // time... so that you can actually call methods ON the BasicBlock, because 1157461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // the contained type is a pointer. This allows BBIt->getTerminator() f.e. 1167461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // 1177461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline NodeType *operator->() const { return operator*(); } 1187461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1197461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline _Self& operator++() { // Preincrement 1205207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick DFSetTraits<SetType>::finishPostorder(VisitStack.back().first, 1215207936a24ab9e0bfaa10e798625df65143e3716Andrew Trick this->Visited); 122a0994b1a13ef3437f5442b9fec1750b150da175aDuncan Sands VisitStack.pop_back(); 1237461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner if (!VisitStack.empty()) 1247461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner traverseChild(); 1259769ab22265b313171d201b5928688524a01bd87Misha Brukman return *this; 1267461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 1277461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1287461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline _Self operator++(int) { // Postincrement 1299769ab22265b313171d201b5928688524a01bd87Misha Brukman _Self tmp = *this; ++*this; return tmp; 1307461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 1317461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 1327461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1337461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Provide global constructors that automatically figure out correct types... 1347461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 1357461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 1367461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerpo_iterator<T> po_begin(T G) { return po_iterator<T>::begin(G); } 1377461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 1387461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerpo_iterator<T> po_end (T G) { return po_iterator<T>::end(G); } 1397461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1403a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman// Provide global definitions of external postorder iterators... 1413a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<class T, class SetType=std::set<typename GraphTraits<T>::NodeType*> > 1423a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanstruct po_ext_iterator : public po_iterator<T, SetType, true> { 1433a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman po_ext_iterator(const po_iterator<T, SetType, true> &V) : 1443a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman po_iterator<T, SetType, true>(V) {} 1453a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman}; 1463a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1473a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<class T, class SetType> 1483a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanpo_ext_iterator<T, SetType> po_ext_begin(T G, SetType &S) { 1493a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return po_ext_iterator<T, SetType>::begin(G, S); 1503a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman} 1513a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1523a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate<class T, class SetType> 1533a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanpo_ext_iterator<T, SetType> po_ext_end(T G, SetType &S) { 1543a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return po_ext_iterator<T, SetType>::end(G, S); 1553a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman} 156767a033a5cc6a8003d72a7a243cb60d9bae674d3Chris Lattner 1577461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Provide global definitions of inverse post order iterators... 1583a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate <class T, 1593a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman class SetType = std::set<typename GraphTraits<T>::NodeType*>, 1603a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman bool External = false> 1613a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanstruct ipo_iterator : public po_iterator<Inverse<T>, SetType, External > { 1623a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) : 1633a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman po_iterator<Inverse<T>, SetType, External> (V) {} 1647461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 1657461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1667461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 1677461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattneripo_iterator<T> ipo_begin(T G, bool Reverse = false) { 1687461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner return ipo_iterator<T>::begin(G, Reverse); 1697461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner} 1707461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1717461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 1727461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattneripo_iterator<T> ipo_end(T G){ 1737461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner return ipo_iterator<T>::end(G); 1747461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner} 1757461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1763a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman//Provide global definitions of external inverse postorder iterators... 177a2769a33c94f021a609a462b28ebea069eba6f74Misha Brukmantemplate <class T, 178a2769a33c94f021a609a462b28ebea069eba6f74Misha Brukman class SetType = std::set<typename GraphTraits<T>::NodeType*> > 1793a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanstruct ipo_ext_iterator : public ipo_iterator<T, SetType, true> { 1803a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman ipo_ext_iterator(const ipo_iterator<T, SetType, true> &V) : 1813a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman ipo_iterator<T, SetType, true>(&V) {} 1823a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman ipo_ext_iterator(const po_iterator<Inverse<T>, SetType, true> &V) : 1833a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman ipo_iterator<T, SetType, true>(&V) {} 1843a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman}; 1853a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1863a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate <class T, class SetType> 1873a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanipo_ext_iterator<T, SetType> ipo_ext_begin(T G, SetType &S) { 1883a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return ipo_ext_iterator<T, SetType>::begin(G, S); 1893a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman} 1903a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman 1913a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmantemplate <class T, class SetType> 1923a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukmanipo_ext_iterator<T, SetType> ipo_ext_end(T G, SetType &S) { 1933a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman return ipo_ext_iterator<T, SetType>::end(G, S); 1943a54b3dc87a581c203b18050b4f787b4ca28a12cMisha Brukman} 1957461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1967461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner//===--------------------------------------------------------------------===// 1977461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Reverse Post Order CFG iterator code 1987461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner//===--------------------------------------------------------------------===// 1999769ab22265b313171d201b5928688524a01bd87Misha Brukman// 2007461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// This is used to visit basic blocks in a method in reverse post order. This 2017461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// class is awkward to use because I don't know a good incremental algorithm to 2029769ab22265b313171d201b5928688524a01bd87Misha Brukman// computer RPO from a graph. Because of this, the construction of the 2037461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// ReversePostOrderTraversal object is expensive (it must walk the entire graph 2047461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// with a postorder iterator to build the data structures). The moral of this 2055560c9d49ccae132cabf1155f18aa0480dce3edaMisha Brukman// story is: Don't create more ReversePostOrderTraversal classes than necessary. 2067461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 2077461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// This class should be used like this: 2087461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// { 2096f2ec7f59daa76df2bd98c4dda3d46cd20c66d37Chris Lattner// ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create 21004bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner// for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) { 2117461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// ... 2127461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// } 21304bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner// for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) { 2147461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// ... 2157461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// } 2167461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// } 2177461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 2187461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 21904bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattnertemplate<class GraphT, class GT = GraphTraits<GraphT> > 2207461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerclass ReversePostOrderTraversal { 22104bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner typedef typename GT::NodeType NodeType; 22204bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner std::vector<NodeType*> Blocks; // Block list in normal PO order 22304bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner inline void Initialize(NodeType *BB) { 2247461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner copy(po_begin(BB), po_end(BB), back_inserter(Blocks)); 2257461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 2267461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerpublic: 227de32fedb8c6ec95258dd9e3c104f0e7e49f283cdChris Lattner typedef typename std::vector<NodeType*>::reverse_iterator rpo_iterator; 22804bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner 22904bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner inline ReversePostOrderTraversal(GraphT G) { 23004bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner Initialize(GT::getEntryNode(G)); 2317461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 2327461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 2337461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // Because we want a reverse post order, use reverse iterators from the vector 2347461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline rpo_iterator begin() { return Blocks.rbegin(); } 2357461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline rpo_iterator end() { return Blocks.rend(); } 2367461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 2377461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 238d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 239d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 2407461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner#endif 241