PostOrderIterator.h revision d091d85c15d56adca38f3522ff4ac0997141e326
1cee8f9ae67104576b2028125b56e9ba4856a1d66Chris Lattner//===-- Support/PostOrderIterator.h - Generic PostOrder iterator -*- C++ -*--=// 27461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 37461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// This file builds on the Support/GraphTraits.h file to build a generic graph 47461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// post order iterator. This should work over any graph type that has a 57461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// GraphTraits specialization. 67461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 77461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner//===----------------------------------------------------------------------===// 87461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 9a9f6e4ae0eaea69949755807b7207177f256eaceBrian Gaeke#ifndef SUPPORT_POSTORDERITERATOR_H 10a9f6e4ae0eaea69949755807b7207177f256eaceBrian Gaeke#define SUPPORT_POSTORDERITERATOR_H 117461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 12cee8f9ae67104576b2028125b56e9ba4856a1d66Chris Lattner#include "Support/GraphTraits.h" 134a63b72df95b5c0d4af064cef19377f811ba6060Chris Lattner#include "Support/iterator" 147461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner#include <stack> 157461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner#include <set> 167461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 177461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate<class GraphT, class GT = GraphTraits<GraphT> > 188dc67168ccbd09821ff6d963b26461e9b47028e7Chris Lattnerclass po_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t> { 198dc67168ccbd09821ff6d963b26461e9b47028e7Chris Lattner typedef forward_iterator<typename GT::NodeType, ptrdiff_t> super; 207461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner typedef typename GT::NodeType NodeType; 217461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner typedef typename GT::ChildIteratorType ChildItTy; 227461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 23697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::set<NodeType *> Visited; // All of the blocks visited so far... 247461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // VisitStack - Used to maintain the ordering. Top = current block 257461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // First element is basic block pointer, second is the 'next child' to visit 26697954c15da58bd8b186dbafdedd8b06db770201Chris Lattner std::stack<std::pair<NodeType *, ChildItTy> > VisitStack; 277461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 287461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner void traverseChild() { 297461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner while (VisitStack.top().second != GT::child_end(VisitStack.top().first)) { 307461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner NodeType *BB = *VisitStack.top().second++; 317461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner if (!Visited.count(BB)) { // If the block is not visited... 327461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner Visited.insert(BB); 337461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner VisitStack.push(make_pair(BB, GT::child_begin(BB))); 347461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 357461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 367461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 377461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 387461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline po_iterator(NodeType *BB) { 397461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner Visited.insert(BB); 407461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner VisitStack.push(make_pair(BB, GT::child_begin(BB))); 417461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner traverseChild(); 427461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 437461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline po_iterator() { /* End is when stack is empty */ } 447461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerpublic: 45d091d85c15d56adca38f3522ff4ac0997141e326Chris Lattner typedef typename super::pointer pointer; 467461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner typedef po_iterator<GraphT, GT> _Self; 477461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 487461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // Provide static "constructors"... 497461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner static inline _Self begin(GraphT G) { return _Self(GT::getEntryNode(G)); } 507461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner static inline _Self end (GraphT G) { return _Self(); } 517461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 527461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline bool operator==(const _Self& x) const { 537461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner return VisitStack == x.VisitStack; 547461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 557461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline bool operator!=(const _Self& x) const { return !operator==(x); } 567461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 577461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline pointer operator*() const { 587461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner return VisitStack.top().first; 597461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 607461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 617461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // This is a nonstandard operator-> that dereferences the pointer an extra 627461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // time... so that you can actually call methods ON the BasicBlock, because 637461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // the contained type is a pointer. This allows BBIt->getTerminator() f.e. 647461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // 657461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline NodeType *operator->() const { return operator*(); } 667461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 677461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline _Self& operator++() { // Preincrement 687461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner VisitStack.pop(); 697461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner if (!VisitStack.empty()) 707461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner traverseChild(); 717461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner return *this; 727461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 737461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 747461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline _Self operator++(int) { // Postincrement 757461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner _Self tmp = *this; ++*this; return tmp; 767461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 777461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 787461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 797461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Provide global constructors that automatically figure out correct types... 807461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 817461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 827461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerpo_iterator<T> po_begin(T G) { return po_iterator<T>::begin(G); } 837461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 847461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerpo_iterator<T> po_end (T G) { return po_iterator<T>::end(G); } 857461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 867461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Provide global definitions of inverse post order iterators... 877461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 887461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerstruct ipo_iterator : public po_iterator<Inverse<T> > { 897461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner ipo_iterator(const po_iterator<Inverse<T> > &V) :po_iterator<Inverse<T> >(V){} 907461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 917461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 927461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 937461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattneripo_iterator<T> ipo_begin(T G, bool Reverse = false) { 947461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner return ipo_iterator<T>::begin(G, Reverse); 957461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner} 967461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 977461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnertemplate <class T> 987461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattneripo_iterator<T> ipo_end(T G){ 997461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner return ipo_iterator<T>::end(G); 1007461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner} 1017461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1027461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1037461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner//===--------------------------------------------------------------------===// 1047461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// Reverse Post Order CFG iterator code 1057461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner//===--------------------------------------------------------------------===// 1067461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 1077461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// This is used to visit basic blocks in a method in reverse post order. This 1087461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// class is awkward to use because I don't know a good incremental algorithm to 1097461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// computer RPO from a graph. Because of this, the construction of the 1107461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// ReversePostOrderTraversal object is expensive (it must walk the entire graph 1117461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// with a postorder iterator to build the data structures). The moral of this 1127461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// story is: Don't create more ReversePostOrderTraversal classes than neccesary. 1137461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 1147461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// This class should be used like this: 1157461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// { 1166f2ec7f59daa76df2bd98c4dda3d46cd20c66d37Chris Lattner// ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create 11704bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner// for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) { 1187461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// ... 1197461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// } 12004bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner// for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) { 1217461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// ... 1227461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// } 1237461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// } 1247461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner// 1257461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 12604bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattnertemplate<class GraphT, class GT = GraphTraits<GraphT> > 1277461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerclass ReversePostOrderTraversal { 12804bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner typedef typename GT::NodeType NodeType; 12904bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner std::vector<NodeType*> Blocks; // Block list in normal PO order 13004bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner inline void Initialize(NodeType *BB) { 1317461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner copy(po_begin(BB), po_end(BB), back_inserter(Blocks)); 1327461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 1337461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattnerpublic: 134de32fedb8c6ec95258dd9e3c104f0e7e49f283cdChris Lattner typedef typename std::vector<NodeType*>::reverse_iterator rpo_iterator; 13504bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner 13604bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner inline ReversePostOrderTraversal(GraphT G) { 13704bb837cc0edf2f1908a0ec9b04989598a13cc6aChris Lattner Initialize(GT::getEntryNode(G)); 1387461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner } 1397461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1407461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner // Because we want a reverse post order, use reverse iterators from the vector 1417461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline rpo_iterator begin() { return Blocks.rbegin(); } 1427461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner inline rpo_iterator end() { return Blocks.rend(); } 1437461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner}; 1447461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner 1457461bf5f8e1e9be67f4ce19f35a32a88668934c7Chris Lattner#endif 146