Pull iterators out of CFG.h and genericize them with GraphTraits

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@666 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 351 insertions, 0 deletions

diff --git a/include/llvm/Support/DepthFirstIterator.h b/include/llvm/Support/DepthFirstIterator.h
new file mode 100644
index 0000000000..73017067b3
--- /dev/null
+++ b/include/llvm/Support/DepthFirstIterator.h
@@ -0,0 +1,147 @@
+//===- llvm/Support/DepthFirstIterator.h - Depth First iterators -*- C++ -*--=//
+//
+// This file builds on the Support/GraphTraits.h file to build generic depth
+// first graph iterator.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_DEPTH_FIRST_ITERATOR_H
+#define LLVM_SUPPORT_DEPTH_FIRST_ITERATOR_H
+
+#include "llvm/Support/GraphTraits.h"
+#include <iterator>
+#include <stack>
+#include <set>
+
+// Generic Depth First Iterator
+template<class GraphT, class GT = GraphTraits<GraphT> >
+class df_iterator : public std::forward_iterator<typename GT::NodeType,
+                                                 ptrdiff_t> {
+  typedef typename GT::NodeType          NodeType;
+  typedef typename GT::ChildIteratorType ChildItTy;
+
+  set<NodeType *>   Visited;    // All of the blocks visited so far...
+  // VisitStack - Used to maintain the ordering.  Top = current block
+  // First element is node pointer, second is the 'next child' to visit
+  stack<pair<NodeType *, ChildItTy> > VisitStack;
+  const bool Reverse;         // Iterate over children before self?
+private:
+  void reverseEnterNode() {
+    pair<NodeType *, ChildItTy> &Top = VisitStack.top();
+    NodeType *Node = Top.first;
+    ChildItTy &It  = Top.second;
+    for (; It != GT::child_end(Node); ++It) {
+      NodeType *Child = *It;
+      if (!Visited.count(Child)) {
+	Visited.insert(Child);
+	VisitStack.push(make_pair(Child, GT::child_begin(Child)));
+	reverseEnterNode();
+	return;
+      }
+    }
+  }
+
+  inline df_iterator(NodeType *Node, bool reverse) : Reverse(reverse) {
+    Visited.insert(Node);
+    VisitStack.push(make_pair(Node, GT::child_begin(Node)));
+    if (Reverse) reverseEnterNode();
+  }
+  inline df_iterator() { /* End is when stack is empty */ }
+
+public:
+  typedef df_iterator<GraphT, GT> _Self;
+
+  // Provide static begin and end methods as our public "constructors"
+  static inline _Self begin(GraphT G, bool Reverse = false) {
+    return _Self(GT::getEntryNode(G), Reverse);
+  }
+  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 Node, because
+  // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
+  //
+  inline NodeType *operator->() const { return operator*(); }
+
+  inline _Self& operator++() {   // Preincrement
+    if (Reverse) {               // Reverse Depth First Iterator
+      if (VisitStack.top().second == GT::child_end(VisitStack.top().first))
+	VisitStack.pop();
+      if (!VisitStack.empty())
+	reverseEnterNode();
+    } else {                     // Normal Depth First Iterator
+      do {
+	pair<NodeType *, ChildItTy> &Top = VisitStack.top();
+	NodeType *Node = Top.first;
+	ChildItTy &It  = Top.second;
+
+	while (It != GT::child_end(Node)) {
+	  NodeType *Next = *It++;
+	  if (!Visited.count(Next)) {  // Has our next sibling been visited?
+	    // No, do it now.
+	    Visited.insert(Next);
+	    VisitStack.push(make_pair(Next, GT::child_begin(Next)));
+	    return *this;
+	  }
+	}
+	
+	// Oops, ran out of successors... go up a level on the stack.
+	VisitStack.pop();
+      } while (!VisitStack.empty());
+    }
+    return *this; 
+  }
+
+  inline _Self operator++(int) { // Postincrement
+    _Self tmp = *this; ++*this; return tmp; 
+  }
+
+  // nodeVisited - return true if this iterator has already visited the
+  // specified node.  This is public, and will probably be used to iterate over
+  // nodes that a depth first iteration did not find: ie unreachable nodes.
+  //
+  inline bool nodeVisited(NodeType *Node) const { 
+    return Visited.count(Node) != 0;
+  }
+};
+
+
+// Provide global constructors that automatically figure out correct types...
+//
+template <class T>
+df_iterator<T> df_begin(T G, bool Reverse = false) {
+  return df_iterator<T>::begin(G, Reverse);
+}
+
+template <class T>
+df_iterator<T> df_end(T G) {
+  return df_iterator<T>::end(G);
+}
+
+// Provide global definitions of inverse depth first iterators...
+template <class T>
+struct idf_iterator : public df_iterator<Inverse<T> > {
+  idf_iterator(const df_iterator<Inverse<T> > &V) :df_iterator<Inverse<T> >(V){}
+};
+
+template <class T>
+idf_iterator<T> idf_begin(T G, bool Reverse = false) {
+  return idf_iterator<T>::begin(G, Reverse);
+}
+
+template <class T>
+idf_iterator<T> idf_end(T G){
+  return idf_iterator<T>::end(G);
+}
+
+#endif
diff --git a/include/llvm/Support/GraphTraits.h b/include/llvm/Support/GraphTraits.h
new file mode 100644
index 0000000000..479be2caf6
--- /dev/null
+++ b/include/llvm/Support/GraphTraits.h
@@ -0,0 +1,59 @@
+//===-- llvm/Support/GraphTraits.h - Graph traits template -------*- C++ -*--=//
+//
+// This file defines the little GraphTraits<X> template class that should be 
+// specialized by classes that want to be iteratable by generic graph iterators.
+//
+// This file also defines the marker class Inverse that is used to iterate over
+// graphs in a graph defined, inverse ordering...
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_GRAPH_TRAITS_H
+#define LLVM_SUPPORT_GRAPH_TRAITS_H
+
+// GraphTraits - This class should be specialized by different graph types...
+// which is why the default version is empty.
+//
+template<class GraphType>
+struct GraphTraits {
+  // Elements to provide:
+
+  // typedef NodeType          - Type of Node in the graph
+  // typedef ChildIteratorType - Type used to iterate over children in graph
+
+  // static NodeType *getEntryNode(GraphType *)
+  //    Return the entry node of the graph
+
+  // static ChildIteratorType child_begin(NodeType *)
+  // static ChildIteratorType child_end  (NodeType *)
+  //    Return iterators that point to the beginning and ending of the child 
+  //    node list for the specified node.
+  //  
+
+
+  // If anyone tries to use this class without having an appropriate
+  // specialization make an error.  If you get this error, it's because you
+  // need to include the appropriate specialization of GraphTraits<> for your
+  // graph, or you need to define it for a new graph type.
+  //
+  typedef typename GraphType::UnknownGraphTypeError NodeType;
+};
+
+
+// Inverse - This class is used as a little marker class to tell the graph
+// iterator to iterate over the graph in a graph defined "Inverse" ordering.
+// Not all graphs define an inverse ordering, and if they do, it depends on
+// the graph exactly what that is.  Here's an example of usage with the
+// df_iterator:
+//
+// df_iterator<Inverse<Method> > I = idf_begin(M), E = idf_end(M);
+// for (; I != E; ++I) { ... }
+//
+template <class GraphType>
+struct Inverse {
+  GraphType &Graph;
+
+  inline Inverse(GraphType &G) : Graph(G) {}
+};
+
+#endif
diff --git a/include/llvm/Support/PostOrderIterator.h b/include/llvm/Support/PostOrderIterator.h
new file mode 100644
index 0000000000..fa135f8785
--- /dev/null
+++ b/include/llvm/Support/PostOrderIterator.h
@@ -0,0 +1,145 @@
+//===-- llvm/Support/PostOrderIterator.h - Generic PO 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 "llvm/Support/GraphTraits.h"
+#include <iterator>
+#include <stack>
+#include <set>
+
+template<class GraphT, class GT = GraphTraits<GraphT> >
+class po_iterator : public std::forward_iterator<typename GT::NodeType,
+                                                 ptrdiff_t> {
+  typedef typename GT::NodeType          NodeType;
+  typedef typename GT::ChildIteratorType ChildItTy;
+
+  set<NodeType *>   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<pair<NodeType *, ChildItTy> > 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<GraphT, GT> _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 <class T>
+po_iterator<T> po_begin(T G) { return po_iterator<T>::begin(G); }
+template <class T>
+po_iterator<T> po_end  (T G) { return po_iterator<T>::end(G); }
+
+// Provide global definitions of inverse post order iterators...
+template <class T>
+struct ipo_iterator : public po_iterator<Inverse<T> > {
+  ipo_iterator(const po_iterator<Inverse<T> > &V) :po_iterator<Inverse<T> >(V){}
+};
+
+template <class T>
+ipo_iterator<T> ipo_begin(T G, bool Reverse = false) {
+  return ipo_iterator<T>::begin(G, Reverse);
+}
+
+template <class T>
+ipo_iterator<T> ipo_end(T G){
+  return ipo_iterator<T>::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<vector<BasicBlock*>::iterator> rpo_iterator;
+// TODO: FIXME: ReversePostOrderTraversal is not generic!
+class ReversePostOrderTraversal {
+  vector<BasicBlock*> 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