Pull predecessor and successor iterators out of the CFG*.h files, and plop them into

the BasicBlock class where they should be.  pred_begin/pred_end become methods on BasicBlock,
and the cfg namespace isn't used anymore.


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

5 files changed, 128 insertions, 314 deletions

diff --git a/include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h b/include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h
index 0dca0fee99..6283a45aa9 100644
--- a/include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h
+++ b/include/llvm/Analysis/LiveVar/FunctionLiveVarInfo.h
@@ -1,4 +1,4 @@
-/* Title:   MethodLiveVarInfo.h
+/* Title:   MethodLiveVarInfo.h             -*- C++ -*-
    Author:  Ruchira Sasanka
    Date:    Jun 30, 01
    Purpose: 
@@ -73,7 +73,6 @@ static const int DEBUG_LV = 0;
 #include "llvm/BasicBlock.h"
 #include "llvm/Instruction.h"
 #include "llvm/Method.h"
-#include "llvm/CFG.h"
 
 #include "LiveVarMap.h"
 #include "BBLiveVar.h"
diff --git a/include/llvm/BasicBlock.h b/include/llvm/BasicBlock.h
index 50ec4c0fbd..11c76a3647 100644
--- a/include/llvm/BasicBlock.h
+++ b/include/llvm/BasicBlock.h
@@ -22,11 +22,11 @@
 #ifndef LLVM_BASICBLOCK_H
 #define LLVM_BASICBLOCK_H
 
-#include "llvm/Value.h"               // Get the definition of Value
+#include "llvm/Value.h"
 #include "llvm/ValueHolder.h"
 #include "llvm/Support/GraphTraits.h"
-
-#include "llvm/CFGdecls.h"   // TODO FIXME: remove
+#include "llvm/InstrTypes.h"
+#include <iterator>
 
 class Instruction;
 class Method;
@@ -34,6 +34,8 @@ class TerminatorInst;
 class MachineCodeForBasicBlock;
 
 class BasicBlock : public Value {       // Basic blocks are data objects also
+  template <class _Ptr, class _USE_iterator> class PredIterator;
+  template <class _Term, class _BB> class SuccIterator;
 public:
   typedef ValueHolder<Instruction, BasicBlock, Method> InstListType;
 private :
@@ -50,17 +52,22 @@ public:
   typedef reverse_iterator<const_iterator> const_reverse_iterator;
   typedef reverse_iterator<iterator>             reverse_iterator;
 
-  typedef cfg::succ_iterator succ_iterator;   // Include CFG.h to use these
-  typedef cfg::pred_iterator pred_iterator;
-  typedef cfg::succ_const_iterator succ_const_iterator;
-  typedef cfg::pred_const_iterator pred_const_iterator;
+  // Predecessor and successor iterators...
+  typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator;
+  typedef PredIterator<const BasicBlock, 
+                       Value::use_const_iterator> pred_const_iterator;
+  typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator;
+  typedef SuccIterator<const TerminatorInst*, 
+                       const BasicBlock> succ_const_iterator;
 
+  // Ctor, dtor
   BasicBlock(const string &Name = "", Method *Parent = 0);
   ~BasicBlock();
 
   // Specialize setName to take care of symbol table majik
   virtual void setName(const string &name, SymbolTable *ST = 0);
 
+  // getParent - Return the enclosing method, or null if none
   const Method *getParent() const { return InstList.getParent(); }
         Method *getParent()       { return InstList.getParent(); }
 
@@ -70,7 +77,6 @@ public:
   //
   TerminatorInst *getTerminator();
   const TerminatorInst *const getTerminator() const;
-
   
   // Machine code accessor...
   inline MachineCodeForBasicBlock& getMachineInstrVec() const {
@@ -79,6 +85,7 @@ public:
   
   //===--------------------------------------------------------------------===//
   // Instruction iterator methods
+  //
   inline iterator                begin()       { return InstList.begin(); }
   inline const_iterator          begin() const { return InstList.begin(); }
   inline iterator                end  ()       { return InstList.end();   }
@@ -140,9 +147,111 @@ public:
   // the basic block).
   //
   BasicBlock *splitBasicBlock(iterator I);
+
+
+  //===--------------------------------------------------------------------===//
+  // Predecessor and Successor Iterators
+  //
+  template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
+  class PredIterator : public std::bidirectional_iterator<_Ptr, ptrdiff_t> {
+    _Ptr *BB;
+    _USE_iterator It;
+  public:
+    typedef PredIterator<_Ptr,_USE_iterator> _Self;
+  
+    inline void advancePastConstPool() {
+      // TODO: This is bad
+      // Loop to ignore constant pool references
+      while (It != BB->use_end() && 
+             ((!(*It)->isInstruction()) ||
+              !(((Instruction*)(*It))->isTerminator())))
+        ++It;
+    }
+  
+    inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) {
+      advancePastConstPool();
+    }
+    inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {}
+    
+    inline bool operator==(const _Self& x) const { return It == x.It; }
+    inline bool operator!=(const _Self& x) const { return !operator==(x); }
+    
+    inline pointer operator*() const { 
+      return (*It)->castInstructionAsserting()->getParent(); 
+    }
+    inline pointer *operator->() const { return &(operator*()); }
+    
+    inline _Self& operator++() {   // Preincrement
+      ++It; advancePastConstPool();
+      return *this; 
+    }
+    
+    inline _Self operator++(int) { // Postincrement
+      _Self tmp = *this; ++*this; return tmp; 
+    }
+    
+    inline _Self& operator--() { --It; return *this; }  // Predecrement
+    inline _Self operator--(int) { // Postdecrement
+      _Self tmp = *this; --*this; return tmp;
+    }
+  };
+  
+  inline pred_iterator pred_begin() { return pred_iterator(this); }
+  inline pred_const_iterator pred_begin() const {
+    return pred_const_iterator(this);
+  }
+  inline pred_iterator pred_end() { return pred_iterator(this, true); }
+  inline pred_const_iterator pred_end() const {
+    return pred_const_iterator(this, true);
+  }
+
+  template <class _Term, class _BB>           // Successor Iterator
+  class SuccIterator : public std::bidirectional_iterator<_BB, ptrdiff_t> {
+    const _Term Term;
+    unsigned idx;
+  public:
+    typedef SuccIterator<_Term, _BB> _Self;
+    // TODO: This can be random access iterator, need operator+ and stuff tho
+    
+    inline SuccIterator(_Term T) : Term(T), idx(0) {         // begin iterator
+      assert(T && "getTerminator returned null!");
+    }
+    inline SuccIterator(_Term T, bool)                       // end iterator
+      : Term(T), idx(Term->getNumSuccessors()) {
+      assert(T && "getTerminator returned null!");
+    }
+    
+    inline bool operator==(const _Self& x) const { return idx == x.idx; }
+    inline bool operator!=(const _Self& x) const { return !operator==(x); }
+    
+    inline pointer operator*() const { return Term->getSuccessor(idx); }
+    inline pointer operator->() const { return operator*(); }
+    
+    inline _Self& operator++() { ++idx; return *this; } // Preincrement
+    inline _Self operator++(int) { // Postincrement
+      _Self tmp = *this; ++*this; return tmp; 
+    }
+    
+    inline _Self& operator--() { --idx; return *this; }  // Predecrement
+    inline _Self operator--(int) { // Postdecrement
+      _Self tmp = *this; --*this; return tmp;
+    }
+  };
+  
+  inline succ_iterator succ_begin() { return succ_iterator(getTerminator()); }
+  inline succ_const_iterator succ_begin() const {
+    return succ_const_iterator(getTerminator());
+  }
+  inline succ_iterator succ_end() {return succ_iterator(getTerminator(), true);}
+  inline succ_const_iterator succ_end() const {
+    return succ_const_iterator(getTerminator(), true);
+  }
 };
 
-#include "llvm/CFG.h"  // TODO FIXME when succ iterators are in BB.h
+
+//===--------------------------------------------------------------------===//
+// GraphTraits specializations for basic block graphs (CFGs)
+//===--------------------------------------------------------------------===//
 
 // Provide specializations of GraphTraits to be able to treat a method as a 
 // graph of basic blocks...
@@ -153,10 +262,10 @@ template <> struct GraphTraits<BasicBlock*> {
 
   static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
   static inline ChildIteratorType child_begin(NodeType *N) { 
-    return cfg::succ_begin(N); 
+    return N->succ_begin(); 
   }
   static inline ChildIteratorType child_end(NodeType *N) { 
-    return cfg::succ_end(N); 
+    return N->succ_end(); 
   }
 };
 
@@ -167,10 +276,10 @@ template <> struct GraphTraits<const BasicBlock*> {
   static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
 
   static inline ChildIteratorType child_begin(NodeType *N) { 
-    return cfg::succ_begin(N); 
+    return N->succ_begin(); 
   }
   static inline ChildIteratorType child_end(NodeType *N) { 
-    return cfg::succ_end(N); 
+    return N->succ_end(); 
   }
 };
 
@@ -184,10 +293,10 @@ template <> struct GraphTraits<Inverse<BasicBlock*> > {
   typedef BasicBlock::pred_iterator ChildIteratorType;
   static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
   static inline ChildIteratorType child_begin(NodeType *N) { 
-    return cfg::pred_begin(N); 
+    return N->pred_begin(); 
   }
   static inline ChildIteratorType child_end(NodeType *N) { 
-    return cfg::pred_end(N); 
+    return N->pred_end(); 
   }
 };
 
@@ -198,10 +307,10 @@ template <> struct GraphTraits<Inverse<const BasicBlock*> > {
     return G.Graph; 
   }
   static inline ChildIteratorType child_begin(NodeType *N) { 
-    return cfg::pred_begin(N); 
+    return N->pred_begin(); 
   }
   static inline ChildIteratorType child_end(NodeType *N) { 
-    return cfg::pred_end(N); 
+    return N->pred_end(); 
   }
 };
 
diff --git a/include/llvm/CFG.h b/include/llvm/CFG.h
deleted file mode 100644
index ad9cd94932..0000000000
--- a/include/llvm/CFG.h
+++ /dev/null
@@ -1,149 +0,0 @@
-//===-- llvm/CFG.h - CFG definitions and useful classes ----------*- C++ -*--=//
-//
-// This file contains the class definitions useful for operating on the control
-// flow graph.
-//
-// Currently it contains functionality for these three applications:
-//
-//  1. Iterate over the predecessors of a basic block:
-//     pred_iterator, pred_const_iterator, pred_begin, pred_end
-//  2. Iterate over the successors of a basic block:
-//     succ_iterator, succ_const_iterator, succ_begin, succ_end
-//  3. Iterate over the basic blocks of a method in depth first ordering or 
-//     reverse depth first order.  df_iterator, df_const_iterator, 
-//     df_begin, df_end.  df_begin takes an arg to specify reverse or not.
-//  4. Iterator over the basic blocks of a method in post order.
-//  5. Iterator over a method in reverse post order.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CFG_H
-#define LLVM_CFG_H
-
-#include "llvm/CFGdecls.h"      // See this file for concise interface info
-#include "llvm/BasicBlock.h"
-#include "llvm/InstrTypes.h"
-#include "llvm/Type.h"
-#include <iterator>
-
-namespace cfg {
-
-//===----------------------------------------------------------------------===//
-//                                Implementation
-//===----------------------------------------------------------------------===//
-
-//===----------------------------------------------------------------------===//
-// Basic Block Predecessor Iterator
-//
-
-template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
-class PredIterator : public std::bidirectional_iterator<_Ptr, ptrdiff_t> {
-  _Ptr *BB;
-  _USE_iterator It;
-public:
-  typedef PredIterator<_Ptr,_USE_iterator> _Self;
-  
-  inline void advancePastConstPool() {
-    // TODO: This is bad
-    // Loop to ignore constant pool references
-    while (It != BB->use_end() && 
-	   ((!(*It)->isInstruction()) ||
-	    !(((Instruction*)(*It))->isTerminator())))
-      ++It;
-  }
-  
-  inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) {
-    advancePastConstPool();
-  }
-  inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {}
-  
-  inline bool operator==(const _Self& x) const { return It == x.It; }
-  inline bool operator!=(const _Self& x) const { return !operator==(x); }
-  
-  inline pointer operator*() const { 
-    return (*It)->castInstructionAsserting()->getParent(); 
-  }
-  inline pointer *operator->() const { return &(operator*()); }
-  
-  inline _Self& operator++() {   // Preincrement
-    ++It; advancePastConstPool();
-    return *this; 
-  }
-  
-  inline _Self operator++(int) { // Postincrement
-    _Self tmp = *this; ++*this; return tmp; 
-  }
-  
-  inline _Self& operator--() { --It; return *this; }  // Predecrement
-  inline _Self operator--(int) { // Postdecrement
-    _Self tmp = *this; --*this; return tmp;
-  }
-};
-
-inline pred_iterator       pred_begin(      BasicBlock *BB) {
-  return pred_iterator(BB);
-}
-inline pred_const_iterator pred_begin(const BasicBlock *BB) {
-  return pred_const_iterator(BB);
-}
-inline pred_iterator       pred_end(      BasicBlock *BB) {
-  return pred_iterator(BB,true);
-}
-inline pred_const_iterator pred_end(const BasicBlock *BB) {
-  return pred_const_iterator(BB,true);
-}
-
-
-//===----------------------------------------------------------------------===//
-// Basic Block Successor Iterator
-//
-
-template <class _Term, class _BB>           // Successor Iterator
-class SuccIterator : public std::bidirectional_iterator<_BB, ptrdiff_t> {
-  const _Term Term;
-  unsigned idx;
-public:
-  typedef SuccIterator<_Term, _BB> _Self;
-  // TODO: This can be random access iterator, need operator+ and stuff tho
-  
-  inline SuccIterator(_Term T) : Term(T), idx(0) {         // begin iterator
-    assert(T && "getTerminator returned null!");
-  }
-  inline SuccIterator(_Term T, bool)                       // end iterator
-    : Term(T), idx(Term->getNumSuccessors()) {
-    assert(T && "getTerminator returned null!");
-  }
-  
-  inline bool operator==(const _Self& x) const { return idx == x.idx; }
-  inline bool operator!=(const _Self& x) const { return !operator==(x); }
-  
-  inline pointer operator*() const { return Term->getSuccessor(idx); }
-  inline pointer operator->() const { return operator*(); }
-  
-  inline _Self& operator++() { ++idx; return *this; } // Preincrement
-  inline _Self operator++(int) { // Postincrement
-    _Self tmp = *this; ++*this; return tmp; 
-  }
-  
-  inline _Self& operator--() { --idx; return *this; }  // Predecrement
-  inline _Self operator--(int) { // Postdecrement
-    _Self tmp = *this; --*this; return tmp;
-  }
-};
-
-inline succ_iterator       succ_begin(      BasicBlock *BB) {
-  return succ_iterator(BB->getTerminator());
-}
-inline succ_const_iterator succ_begin(const BasicBlock *BB) {
-  return succ_const_iterator(BB->getTerminator());
-}
-inline succ_iterator       succ_end(      BasicBlock *BB) {
-  return succ_iterator(BB->getTerminator(),true);
-}
-inline succ_const_iterator succ_end(const BasicBlock *BB) {
-  return succ_const_iterator(BB->getTerminator(),true);
-}
-
-}    // End namespace cfg
-
-#endif
diff --git a/include/llvm/CFGdecls.h b/include/llvm/CFGdecls.h
deleted file mode 100644
index 4ffe256f5e..0000000000
--- a/include/llvm/CFGdecls.h
+++ /dev/null
@@ -1,144 +0,0 @@
-//===-- llvm/CFGdecls.h - CFG forward declarations ---------------*- C++ -*--=//
-//
-// This file contains forward declarations for CFG functions and data
-// structures.  This is used to reduce compile time dependencies among files.
-// Any users of these functions must include CFG.h to get their full 
-// definitions.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CFG_DECLS_H
-#define LLVM_CFG_DECLS_H
-
-#include "llvm/Value.h"
-class TerminatorInst;
-class BasicBlock;
-class Method;
-
-//===----------------------------------------------------------------------===//
-//                                Interface
-//===----------------------------------------------------------------------===//
-
-namespace cfg {
-
-//===--------------------------------------------------------------------===//
-// Predecessor iterator code
-//===--------------------------------------------------------------------===//
-// 
-// This is used to figure out what basic blocks we could be coming from.
-//
-
-// Forward declare iterator class template...
-template <class _Ptr, class _USE_iterator> class PredIterator;
-
-typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator;
-typedef PredIterator<const BasicBlock, 
-		     Value::use_const_iterator> pred_const_iterator;
-
-inline pred_iterator       pred_begin(      BasicBlock *BB);
-inline pred_const_iterator pred_begin(const BasicBlock *BB);
-inline pred_iterator       pred_end  (      BasicBlock *BB);
-inline pred_const_iterator pred_end  (const BasicBlock *BB);
-
-
-//===--------------------------------------------------------------------===//
-// Successor iterator code
-//===--------------------------------------------------------------------===//
-// 
-// This is used to figure out what basic blocks we could be going to...
-//
-
-// Forward declare iterator class template...
-template <class _Term, class _BB> class SuccIterator;
-
-typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator;
-typedef SuccIterator<const TerminatorInst*, 
-		     const BasicBlock> succ_const_iterator;
-
-inline succ_iterator       succ_begin(      BasicBlock *BB);
-inline succ_const_iterator succ_begin(const BasicBlock *BB);
-inline succ_iterator       succ_end  (      BasicBlock *BB);
-inline succ_const_iterator succ_end  (const BasicBlock *BB);
-
-#if 0
-//===--------------------------------------------------------------------===//
-// <Reverse> Depth First CFG iterator code
-//===--------------------------------------------------------------------===//
-// 
-// This is used to visit basic blocks in a method in either depth first, or 
-// reverse depth first ordering, depending on the value passed to the df_begin
-// method.
-//
-struct      BasicBlockGraph;
-struct ConstBasicBlockGraph;
-struct      InverseBasicBlockGraph;
-struct ConstInverseBasicBlockGraph;
-struct TypeGraph;
-
-// Forward declare iterator class template...
-template<class GraphInfo> class DFIterator;
-
-// Normal Depth First Iterator Definitions (Forward and Reverse)
-typedef DFIterator<     BasicBlockGraph> df_iterator;
-typedef DFIterator<ConstBasicBlockGraph> df_const_iterator;
-
-inline df_iterator       df_begin(      Method *M, bool Reverse = false);
-inline df_const_iterator df_begin(const Method *M, bool Reverse = false);
-inline df_iterator       df_end  (      Method *M);
-inline df_const_iterator df_end  (const Method *M);
-
-inline df_iterator       df_begin(      BasicBlock *BB, bool Reverse = false);
-inline df_const_iterator df_begin(const BasicBlock *BB, bool Reverse = false);
-inline df_iterator       df_end  (      BasicBlock *BB);
-inline df_const_iterator df_end  (const BasicBlock *BB);
-
-
-// Inverse Depth First Iterator Definitions (Forward and Reverse) - Traverse
-// predecessors instead of successors...
-//
-typedef DFIterator<     InverseBasicBlockGraph> idf_iterator;
-typedef DFIterator<ConstInverseBasicBlockGraph> idf_const_iterator;
-
-inline idf_iterator       idf_begin(      BasicBlock *BB, bool Reverse = false);
-inline idf_const_iterator idf_begin(const BasicBlock *BB, bool Reverse = false);
-inline idf_iterator       idf_end  (      BasicBlock *BB);
-inline idf_const_iterator idf_end  (const BasicBlock *BB);
-
-
-// Depth First Iterator Definitions for Types.  This lets you iterator over 
-// (possibly cyclic) type graphs in dfo
-//
-typedef DFIterator<TypeGraph> tdf_iterator;
-
-inline tdf_iterator tdf_begin(const Type *T, bool Reverse = false);
-inline tdf_iterator tdf_end  (const Type *T);
-
-
-//===--------------------------------------------------------------------===//
-// 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 *M);
-inline po_const_iterator po_begin(const Method *M);
-inline po_iterator       po_end  (      Method *M);
-inline po_const_iterator po_end  (const Method *M);
-
-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);
-#endif
-
-}    // End namespace cfg
-
-#endif
diff --git a/include/llvm/CodeGen/FunctionLiveVarInfo.h b/include/llvm/CodeGen/FunctionLiveVarInfo.h
index 0dca0fee99..6283a45aa9 100644
--- a/include/llvm/CodeGen/FunctionLiveVarInfo.h
+++ b/include/llvm/CodeGen/FunctionLiveVarInfo.h
@@ -1,4 +1,4 @@
-/* Title:   MethodLiveVarInfo.h
+/* Title:   MethodLiveVarInfo.h             -*- C++ -*-
    Author:  Ruchira Sasanka
    Date:    Jun 30, 01
    Purpose: 
@@ -73,7 +73,6 @@ static const int DEBUG_LV = 0;
 #include "llvm/BasicBlock.h"
 #include "llvm/Instruction.h"
 #include "llvm/Method.h"
-#include "llvm/CFG.h"
 
 #include "LiveVarMap.h"
 #include "BBLiveVar.h"