From cee8f9ae67104576b2028125b56e9ba4856a1d66 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Tue, 27 Nov 2001 00:03:19 +0000 Subject: Create a new #include "Support/..." directory structure to move things from "llvm/Support/..." that are not llvm dependant. Move files and fix #includes git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@1400 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/PostOrderIterator.h | 145 +++++++++++++++++++++++++++++++++++ 1 file changed, 145 insertions(+) create mode 100644 include/llvm/ADT/PostOrderIterator.h (limited to 'include/llvm/ADT/PostOrderIterator.h') diff --git a/include/llvm/ADT/PostOrderIterator.h b/include/llvm/ADT/PostOrderIterator.h new file mode 100644 index 0000000..89a9b4d --- /dev/null +++ b/include/llvm/ADT/PostOrderIterator.h @@ -0,0 +1,145 @@ +//===-- Support/PostOrderIterator.h - Generic PostOrder iterator -*- C++ -*--=// +// +// This file builds on the Support/GraphTraits.h file to build a generic graph +// post order iterator. This should work over any graph type that has a +// GraphTraits specialization. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_POSTORDER_ITERATOR_H +#define LLVM_SUPPORT_POSTORDER_ITERATOR_H + +#include "Support/GraphTraits.h" +#include +#include +#include + +template > +class po_iterator : public std::forward_iterator { + typedef typename GT::NodeType NodeType; + typedef typename GT::ChildIteratorType ChildItTy; + + set Visited; // All of the blocks visited so far... + // VisitStack - Used to maintain the ordering. Top = current block + // First element is basic block pointer, second is the 'next child' to visit + stack > VisitStack; + + void traverseChild() { + while (VisitStack.top().second != GT::child_end(VisitStack.top().first)) { + NodeType *BB = *VisitStack.top().second++; + if (!Visited.count(BB)) { // If the block is not visited... + Visited.insert(BB); + VisitStack.push(make_pair(BB, GT::child_begin(BB))); + } + } + } + + inline po_iterator(NodeType *BB) { + Visited.insert(BB); + VisitStack.push(make_pair(BB, GT::child_begin(BB))); + traverseChild(); + } + inline po_iterator() { /* End is when stack is empty */ } +public: + typedef po_iterator _Self; + + // Provide static "constructors"... + static inline _Self begin(GraphT G) { return _Self(GT::getEntryNode(G)); } + static inline _Self end (GraphT G) { return _Self(); } + + inline bool operator==(const _Self& x) const { + return VisitStack == x.VisitStack; + } + inline bool operator!=(const _Self& x) const { return !operator==(x); } + + inline pointer operator*() const { + return VisitStack.top().first; + } + + // This is a nonstandard operator-> that dereferences the pointer an extra + // time... so that you can actually call methods ON the BasicBlock, because + // the contained type is a pointer. This allows BBIt->getTerminator() f.e. + // + inline NodeType *operator->() const { return operator*(); } + + inline _Self& operator++() { // Preincrement + VisitStack.pop(); + if (!VisitStack.empty()) + traverseChild(); + return *this; + } + + inline _Self operator++(int) { // Postincrement + _Self tmp = *this; ++*this; return tmp; + } +}; + +// Provide global constructors that automatically figure out correct types... +// +template +po_iterator po_begin(T G) { return po_iterator::begin(G); } +template +po_iterator po_end (T G) { return po_iterator::end(G); } + +// Provide global definitions of inverse post order iterators... +template +struct ipo_iterator : public po_iterator > { + ipo_iterator(const po_iterator > &V) :po_iterator >(V){} +}; + +template +ipo_iterator ipo_begin(T G, bool Reverse = false) { + return ipo_iterator::begin(G, Reverse); +} + +template +ipo_iterator ipo_end(T G){ + return ipo_iterator::end(G); +} + + +//===--------------------------------------------------------------------===// +// Reverse Post Order CFG iterator code +//===--------------------------------------------------------------------===// +// +// This is used to visit basic blocks in a method in reverse post order. This +// class is awkward to use because I don't know a good incremental algorithm to +// computer RPO from a graph. Because of this, the construction of the +// ReversePostOrderTraversal object is expensive (it must walk the entire graph +// with a postorder iterator to build the data structures). The moral of this +// story is: Don't create more ReversePostOrderTraversal classes than neccesary. +// +// This class should be used like this: +// { +// cfg::ReversePostOrderTraversal RPOT(MethodPtr); // Expensive to create +// for (cfg::rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) { +// ... +// } +// for (cfg::rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) { +// ... +// } +// } +// + +typedef reverse_iterator::iterator> rpo_iterator; +// TODO: FIXME: ReversePostOrderTraversal is not generic! +class ReversePostOrderTraversal { + vector Blocks; // Block list in normal PO order + inline void Initialize(BasicBlock *BB) { + copy(po_begin(BB), po_end(BB), back_inserter(Blocks)); + } +public: + inline ReversePostOrderTraversal(Method *M) { + Initialize(M->front()); + } + inline ReversePostOrderTraversal(BasicBlock *BB) { + Initialize(BB); + } + + // Because we want a reverse post order, use reverse iterators from the vector + inline rpo_iterator begin() { return Blocks.rbegin(); } + inline rpo_iterator end() { return Blocks.rend(); } +}; + +#endif -- cgit v1.1