Move contents to the cfg namespace.

Implement post order and reverse post order iterators


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

1 files changed, 189 insertions, 16 deletions

diff --git a/include/llvm/CFG.h b/include/llvm/CFG.h
index b460992..3195607 100644
--- a/include/llvm/CFG.h
+++ b/include/llvm/CFG.h
@@ -28,6 +28,8 @@
 //                                Interface
 //===----------------------------------------------------------------------===//
 
+namespace cfg {
+
 //===--------------------------------------------------------------------===//
 // Predecessor iterator code
 //===--------------------------------------------------------------------===//
@@ -69,7 +71,7 @@ inline succ_const_iterator succ_end  (const BasicBlock *BB);
 
 
 //===--------------------------------------------------------------------===//
-// Depth First CFG iterator code
+// <Reverse> Depth First CFG iterator code
 //===--------------------------------------------------------------------===//
 // 
 // This is used to visit basic blocks in a method in either depth first, or 
@@ -95,6 +97,74 @@ inline df_iterator       df_end  (      BasicBlock *BB);
 inline df_const_iterator df_end  (const BasicBlock *BB);
 
 
+//===--------------------------------------------------------------------===//
+// Post Order CFG iterator code
+//===--------------------------------------------------------------------===//
+// 
+// This is used to visit basic blocks in a method in standard post order.
+//
+
+// Forward declare iterator class template...
+template<class BBType, class SuccItTy> class POIterator;
+
+typedef POIterator<BasicBlock, succ_iterator> po_iterator;
+typedef POIterator<const BasicBlock, 
+		   succ_const_iterator> po_const_iterator;
+
+inline po_iterator       po_begin(      Method *BB);
+inline po_const_iterator po_begin(const Method *BB);
+inline po_iterator       po_end  (      Method *BB);
+inline po_const_iterator po_end  (const Method *BB);
+
+inline po_iterator       po_begin(      BasicBlock *BB);
+inline po_const_iterator po_begin(const BasicBlock *BB);
+inline po_iterator       po_end  (      BasicBlock *BB);
+inline po_const_iterator po_end  (const BasicBlock *BB);
+
+
+//===--------------------------------------------------------------------===//
+// 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*>::const_iterator> 
+// rpo_const_iterator;
+typedef reverse_iterator<vector<BasicBlock*>::iterator> rpo_iterator;
+
+class ReversePostOrderTraversal {
+  vector<BasicBlock*> Blocks;       // Block list in normal PO order
+  void Initialize(BasicBlock *BB);  // Implemented down below
+public:
+  inline ReversePostOrderTraversal(Method *M) {
+    Initialize(M->getBasicBlocks().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(); }
+};
+
 
 //===----------------------------------------------------------------------===//
 //                                Implementation
@@ -224,11 +294,29 @@ class DFIterator {            // BasicBlock Depth First Iterator
   // First element is basic block pointer, second is the 'next child' to visit
   stack<pair<BBType *, SuccItTy> > VisitStack;
   const bool Reverse;         // Iterate over children before self?
+private:
+  void reverseEnterNode() {
+    pair<BBType *, SuccItTy> &Top = VisitStack.top();
+    BBType *BB    = Top.first;
+    SuccItTy &It  = Top.second;
+    for (; It != succ_end(BB); ++It) {
+      BBType *Child = *It;
+      if (!Visited.count(Child)) {
+	Visited.insert(Child);
+	VisitStack.push(make_pair(Child, succ_begin(Child)));
+	reverseEnterNode();
+	return;
+      }
+    }
+  }
 public:
   typedef DFIterator<BBType, SuccItTy> _Self;
 
   typedef forward_iterator_tag iterator_category;
   typedef BBType *pointer;
+  typedef BBType &reference;
+  typedef void difference_type;
+  typedef BBType *value_type;
 
   inline DFIterator(BBType *BB, bool reverse) : Reverse(reverse) {
     Visited.insert(BB);
@@ -252,21 +340,6 @@ public:
   //
   inline BBType *operator->() const { return operator*(); }
 
-  void reverseEnterNode() {
-    pair<BBType *, SuccItTy> &Top = VisitStack.top();
-    BBType *BB    = Top.first;
-    SuccItTy &It  = Top.second;
-    for (; It != succ_end(BB); ++It) {
-      BBType *Child = *It;
-      if (!Visited.count(Child)) {
-	Visited.insert(Child);
-	VisitStack.push(make_pair(Child, succ_begin(Child)));
-	reverseEnterNode();
-	return;
-      }
-    }
-  }
-
   inline _Self& operator++() {   // Preincrement
     if (Reverse) {               // Reverse Depth First Iterator
       if (VisitStack.top().second == succ_end(VisitStack.top().first))
@@ -329,4 +402,104 @@ inline df_const_iterator df_end(const BasicBlock*) {
   return df_const_iterator();
 }
 
+
+//===----------------------------------------------------------------------===//
+// Post Order CFG iterator code
+//
+
+template<class BBType, class SuccItTy> 
+class POIterator {
+  set<BBType *>   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<BBType *, SuccItTy> > VisitStack;
+
+  void traverseChild() {
+    while (VisitStack.top().second != succ_end(VisitStack.top().first)) {
+      BBType *BB = *VisitStack.top().second++;
+      if (!Visited.count(BB)) {  // If the block is not visited...
+	Visited.insert(BB);
+	VisitStack.push(make_pair(BB, succ_begin(BB)));
+      }
+    }
+  }
+public:
+  typedef POIterator<BBType, SuccItTy> _Self;
+
+  typedef forward_iterator_tag iterator_category;
+  typedef BBType *pointer;
+  typedef BBType &reference;
+  typedef void difference_type;
+  typedef BBType *value_type;
+
+  inline POIterator(BBType *BB) {
+    Visited.insert(BB);
+    VisitStack.push(make_pair(BB, succ_begin(BB)));
+    traverseChild();
+  }
+  inline POIterator() { /* End is when stack is empty */ }
+
+  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 BBType *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; 
+  }
+};
+
+inline po_iterator       po_begin(      Method *M) {
+  return po_iterator(M->getBasicBlocks().front());
+}
+inline po_const_iterator po_begin(const Method *M) {
+  return po_const_iterator(M->getBasicBlocks().front());
+}
+inline po_iterator       po_end  (      Method *M) {
+  return po_iterator();
+}
+inline po_const_iterator po_end  (const Method *M) {
+  return po_const_iterator();
+}
+
+inline po_iterator       po_begin(      BasicBlock *BB) {
+  return po_iterator(BB);
+}
+inline po_const_iterator po_begin(const BasicBlock *BB) {
+  return po_const_iterator(BB);
+}
+inline po_iterator       po_end  (      BasicBlock *BB) {
+  return po_iterator();
+}
+inline po_const_iterator po_end  (const BasicBlock *BB) {
+  return po_const_iterator();
+}
+
+
+//===----------------------------------------------------------------------===//
+// Reverse Post Order CFG iterator code
+//
+void ReversePostOrderTraversal::Initialize(BasicBlock *BB) {
+  copy(po_begin(BB), po_end(BB), back_inserter(Blocks));
+}
+
+}    // End namespace cfg
+
 #endif