* Move BasicBlock and Method graph stuff to new "llvm/Support/CFG.h" file

* Move Method::inst_* to new "llvm/Support/InstIterator.h" file
* inst_iterator no longer permits resync'ing


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

2 files changed, 230 insertions, 0 deletions

diff --git a/include/llvm/Support/CFG.h b/include/llvm/Support/CFG.h
new file mode 100644
index 0000000000..2cc2109b32
--- /dev/null
+++ b/include/llvm/Support/CFG.h
@@ -0,0 +1,115 @@
+//===-- llvm/Support/CFG.h - Process LLVM structures as graphs ---*- C++ -*--=//
+//
+// This file defines specializations of GraphTraits that allow Methods and
+// BasicBlock graphs to be treated as proper graphs for generic algorithms.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CFG_H
+#define LLVM_CFG_H
+
+#include "Support/GraphTraits.h"
+#include "llvm/Method.h"
+#include "llvm/BasicBlock.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...
+
+template <> struct GraphTraits<BasicBlock*> {
+  typedef BasicBlock NodeType;
+  typedef BasicBlock::succ_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
+  static inline ChildIteratorType child_begin(NodeType *N) { 
+    return N->succ_begin(); 
+  }
+  static inline ChildIteratorType child_end(NodeType *N) { 
+    return N->succ_end(); 
+  }
+};
+
+template <> struct GraphTraits<const BasicBlock*> {
+  typedef const BasicBlock NodeType;
+  typedef BasicBlock::succ_const_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
+
+  static inline ChildIteratorType child_begin(NodeType *N) { 
+    return N->succ_begin(); 
+  }
+  static inline ChildIteratorType child_end(NodeType *N) { 
+    return N->succ_end(); 
+  }
+};
+
+// Provide specializations of GraphTraits to be able to treat a method as a 
+// graph of basic blocks... and to walk it in inverse order.  Inverse order for
+// a method is considered to be when traversing the predecessor edges of a BB
+// instead of the successor edges.
+//
+template <> struct GraphTraits<Inverse<BasicBlock*> > {
+  typedef BasicBlock NodeType;
+  typedef BasicBlock::pred_iterator ChildIteratorType;
+  static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
+  static inline ChildIteratorType child_begin(NodeType *N) { 
+    return N->pred_begin(); 
+  }
+  static inline ChildIteratorType child_end(NodeType *N) { 
+    return N->pred_end(); 
+  }
+};
+
+template <> struct GraphTraits<Inverse<const BasicBlock*> > {
+  typedef const BasicBlock NodeType;
+  typedef BasicBlock::pred_const_iterator ChildIteratorType;
+  static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
+    return G.Graph; 
+  }
+  static inline ChildIteratorType child_begin(NodeType *N) { 
+    return N->pred_begin(); 
+  }
+  static inline ChildIteratorType child_end(NodeType *N) { 
+    return N->pred_end(); 
+  }
+};
+
+
+
+//===--------------------------------------------------------------------===//
+// GraphTraits specializations for method basic block graphs (CFGs)
+//===--------------------------------------------------------------------===//
+
+// Provide specializations of GraphTraits to be able to treat a method as a 
+// graph of basic blocks... these are the same as the basic block iterators,
+// except that the root node is implicitly the first node of the method.
+//
+template <> struct GraphTraits<Method*> : public GraphTraits<BasicBlock*> {
+  static NodeType *getEntryNode(Method *M) { return M->front(); }
+};
+template <> struct GraphTraits<const Method*> :
+  public GraphTraits<const BasicBlock*> {
+  static NodeType *getEntryNode(const Method *M) { return M->front(); }
+};
+
+
+// Provide specializations of GraphTraits to be able to treat a method as a 
+// graph of basic blocks... and to walk it in inverse order.  Inverse order for
+// a method is considered to be when traversing the predecessor edges of a BB
+// instead of the successor edges.
+//
+template <> struct GraphTraits<Inverse<Method*> > :
+  public GraphTraits<Inverse<BasicBlock*> > {
+  static NodeType *getEntryNode(Inverse<Method *> G) { return G.Graph->front();}
+};
+template <> struct GraphTraits<Inverse<const Method*> > :
+  public GraphTraits<Inverse<const BasicBlock*> > {
+  static NodeType *getEntryNode(Inverse<const Method *> G) {
+    return G.Graph->front();
+  }
+};
+
+#endif
diff --git a/include/llvm/Support/InstIterator.h b/include/llvm/Support/InstIterator.h
new file mode 100644
index 0000000000..517e6d26a4
--- /dev/null
+++ b/include/llvm/Support/InstIterator.h
@@ -0,0 +1,115 @@
+//===-- llvm/Support/InstIterator.h - Classes for inst iteration -*- C++ -*--=//
+//
+// This file contains definitions of two iterators for iterating over the
+// instructions in a method.  This is effectively a wrapper around a two level
+// iterator that can probably be genericized later.
+//
+// Note that this iterator gets invalidated any time that basic blocks or
+// instructions are moved around.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_INST_ITERATOR_H
+#define LLVM_INST_ITERATOR_H
+
+#include "llvm/BasicBlock.h"
+#include "llvm/Method.h"
+
+// This class is implements inst_begin() & inst_end() for
+// inst_iterator and const_inst_iterator's.
+//
+template <class _BB_t, class _BB_i_t, class _BI_t, class _II_t>
+class InstIterator {
+  typedef _BB_t   BBty;
+  typedef _BB_i_t BBIty;
+  typedef _BI_t   BIty;
+  typedef _II_t   IIty;
+  _BB_t  &BBs;      // BasicBlocksType
+  _BB_i_t BB;       // BasicBlocksType::iterator
+  _BI_t   BI;       // BasicBlock::iterator
+public:
+  typedef std::bidirectional_iterator_tag iterator_category;
+  typedef IIty                            value_type;
+  typedef unsigned                        difference_type;
+  typedef BIty                            pointer;
+  typedef IIty                            reference;
+  
+  template<class M> InstIterator(M &m) 
+    : BBs(m.getBasicBlocks()), BB(BBs.begin()) {    // begin ctor
+    if (BB != BBs.end()) {
+      BI = (*BB)->begin();
+      advanceToNextBB();
+    }
+  }
+
+  template<class M> InstIterator(M &m, bool) 
+    : BBs(m.getBasicBlocks()), BB(BBs.end()) {    // end ctor
+  }
+
+  // Accessors to get at the underlying iterators...
+  inline BBIty &getBasicBlockIterator()  { return BB; }
+  inline BIty  &getInstructionIterator() { return BI; }
+  
+  inline IIty operator*()  const { return *BI; }
+  inline IIty operator->() const { return operator*(); }
+  
+  inline bool operator==(const InstIterator &y) const { 
+    return BB == y.BB && (BB == BBs.end() || BI == y.BI);
+  }
+  inline bool operator!=(const InstIterator& y) const { 
+    return !operator==(y);
+  }
+
+  InstIterator& operator++() { 
+    ++BI;
+    advanceToNextBB();
+    return *this; 
+  }
+  inline InstIterator operator++(int) { 
+    InstIterator tmp = *this; ++*this; return tmp; 
+  }
+    
+  InstIterator& operator--() { 
+    while (BB == BBs.end() || BI == (*BB)->begin()) {
+      --BB;
+      BI = (*BB)->end();
+    }
+    --BI;
+    return *this; 
+  }
+  inline InstIterator  operator--(int) { 
+    InstIterator tmp = *this; --*this; return tmp; 
+  }
+
+  inline bool atEnd() const { return BB == BBs.end(); }
+
+private:
+  inline void advanceToNextBB() {
+    // The only way that the II could be broken is if it is now pointing to
+    // the end() of the current BasicBlock and there are successor BBs.
+    while (BI == (*BB)->end()) {
+      ++BB;
+      if (BB == BBs.end()) break;
+      BI = (*BB)->begin();
+    }
+  }
+};
+
+
+typedef InstIterator<ValueHolder<BasicBlock, Method, Method>, Method::iterator, 
+                     BasicBlock::iterator, Instruction*> inst_iterator;
+typedef InstIterator<const ValueHolder<BasicBlock, Method, Method>,
+                     Method::const_iterator, 
+                     BasicBlock::const_iterator,
+                     const Instruction*> const_inst_iterator;
+
+inline inst_iterator inst_begin(Method *M) { return inst_iterator(*M); }
+inline inst_iterator inst_end(Method *M)   { return inst_iterator(*M, true); }
+inline const_inst_iterator inst_begin(const Method *M) {
+  return const_inst_iterator(*M);
+}
+inline const_inst_iterator inst_end(const Method *M) {
+  return const_inst_iterator(*M, true);
+}
+
+#endif