include/llvm/Support/CFG.h

   1 //===-- llvm/Support/CFG.h - Process LLVM structures as graphs ---*- C++ -*--=//
   2 //
   3 // This file defines specializations of GraphTraits that allow Function and
   4 // BasicBlock graphs to be treated as proper graphs for generic algorithms.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #ifndef LLVM_CFG_H
   9 #define LLVM_CFG_H
  10
  11 #include "Support/GraphTraits.h"
  12 #include "llvm/Function.h"
  13 #include "llvm/InstrTypes.h"
  14 #include "Support/iterator"
  15
  16 //===--------------------------------------------------------------------===//
  17 // BasicBlock pred_iterator definition
  18 //===--------------------------------------------------------------------===//
  19
  20 template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
  21 class PredIterator : public bidirectional_iterator<_Ptr, ptrdiff_t> {
  22   typedef bidirectional_iterator<_Ptr, ptrdiff_t> super;
  23   _Ptr *BB;
  24   _USE_iterator It;
  25 public:
  26   typedef PredIterator<_Ptr,_USE_iterator> _Self;
  27   typedef typename super::pointer pointer;
  28
  29   inline void advancePastConstants() {
  30     // Loop to ignore non terminator uses (for example PHI nodes)...
  31     while (It != BB->use_end() && !isa<TerminatorInst>(*It))
  32       ++It;
  33   }
  34
  35   inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) {
  36     advancePastConstants();
  37   }
  38   inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {}
  39
  40   inline bool operator==(const _Self& x) const { return It == x.It; }
  41   inline bool operator!=(const _Self& x) const { return !operator==(x); }
  42
  43   inline pointer operator*() const {
  44     assert(It != BB->use_end() && "pred_iterator out of range!");
  45     return cast<TerminatorInst>(*It)->getParent();
  46   }
  47   inline pointer *operator->() const { return &(operator*()); }
  48
  49   inline _Self& operator++() {   // Preincrement
  50     assert(It != BB->use_end() && "pred_iterator out of range!");
  51     ++It; advancePastConstants();
  52     return *this;
  53   }
  54
  55   inline _Self operator++(int) { // Postincrement
  56     _Self tmp = *this; ++*this; return tmp;
  57   }
  58
  59   inline _Self& operator--() { --It; return *this; }  // Predecrement
  60   inline _Self operator--(int) { // Postdecrement
  61     _Self tmp = *this; --*this; return tmp;
  62   }
  63 };
  64
  65 typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator;
  66 typedef PredIterator<const BasicBlock,
  67                      Value::use_const_iterator> pred_const_iterator;
  68
  69 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
  70 inline pred_const_iterator pred_begin(const BasicBlock *BB) {
  71   return pred_const_iterator(BB);
  72 }
  73 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
  74 inline pred_const_iterator pred_end(const BasicBlock *BB) {
  75   return pred_const_iterator(BB, true);
  76 }
  77
  78
  79
  80 //===--------------------------------------------------------------------===//
  81 // BasicBlock succ_iterator definition
  82 //===--------------------------------------------------------------------===//
  83
  84 template <class _Term, class _BB>           // Successor Iterator
  85 class SuccIterator : public bidirectional_iterator<_BB, ptrdiff_t> {
  86   const _Term Term;
  87   unsigned idx;
  88   typedef bidirectional_iterator<_BB, ptrdiff_t> super;
  89 public:
  90   typedef SuccIterator<_Term, _BB> _Self;
  91   typedef typename super::pointer pointer;
  92   // TODO: This can be random access iterator, need operator+ and stuff tho
  93
  94   inline SuccIterator(_Term T) : Term(T), idx(0) {         // begin iterator
  95     assert(T && "getTerminator returned null!");
  96   }
  97   inline SuccIterator(_Term T, bool)                       // end iterator
  98     : Term(T), idx(Term->getNumSuccessors()) {
  99     assert(T && "getTerminator returned null!");
 100   }
 101
 102   inline const _Self &operator=(const _Self &I) {
 103     assert(Term == I.Term &&"Cannot assign iterators to two different blocks!");
 104     idx = I.idx;
 105     return *this;
 106   }
 107
 108   inline bool operator==(const _Self& x) const { return idx == x.idx; }
 109   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 110
 111   inline pointer operator*() const { return Term->getSuccessor(idx); }
 112   inline pointer operator->() const { return operator*(); }
 113
 114   inline _Self& operator++() { ++idx; return *this; } // Preincrement
 115   inline _Self operator++(int) { // Postincrement
 116     _Self tmp = *this; ++*this; return tmp;
 117   }
 118
 119   inline _Self& operator--() { --idx; return *this; }  // Predecrement
 120   inline _Self operator--(int) { // Postdecrement
 121     _Self tmp = *this; --*this; return tmp;
 122   }
 123 };
 124
 125 typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator;
 126 typedef SuccIterator<const TerminatorInst*,
 127                      const BasicBlock> succ_const_iterator;
 128
 129 inline succ_iterator succ_begin(BasicBlock *BB) {
 130   return succ_iterator(BB->getTerminator());
 131 }
 132 inline succ_const_iterator succ_begin(const BasicBlock *BB) {
 133   return succ_const_iterator(BB->getTerminator());
 134 }
 135 inline succ_iterator succ_end(BasicBlock *BB) {
 136   return succ_iterator(BB->getTerminator(), true);
 137 }
 138 inline succ_const_iterator succ_end(const BasicBlock *BB) {
 139   return succ_const_iterator(BB->getTerminator(), true);
 140 }
 141
 142
 143
 144 //===--------------------------------------------------------------------===//
 145 // GraphTraits specializations for basic block graphs (CFGs)
 146 //===--------------------------------------------------------------------===//
 147
 148 // Provide specializations of GraphTraits to be able to treat a function as a
 149 // graph of basic blocks...
 150
 151 template <> struct GraphTraits<BasicBlock*> {
 152   typedef BasicBlock NodeType;
 153   typedef succ_iterator ChildIteratorType;
 154
 155   static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
 156   static inline ChildIteratorType child_begin(NodeType *N) {
 157     return succ_begin(N);
 158   }
 159   static inline ChildIteratorType child_end(NodeType *N) {
 160     return succ_end(N);
 161   }
 162 };
 163
 164 template <> struct GraphTraits<const BasicBlock*> {
 165   typedef const BasicBlock NodeType;
 166   typedef succ_const_iterator ChildIteratorType;
 167
 168   static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
 169
 170   static inline ChildIteratorType child_begin(NodeType *N) {
 171     return succ_begin(N);
 172   }
 173   static inline ChildIteratorType child_end(NodeType *N) {
 174     return succ_end(N);
 175   }
 176 };
 177
 178 // Provide specializations of GraphTraits to be able to treat a function as a
 179 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 180 // a function is considered to be when traversing the predecessor edges of a BB
 181 // instead of the successor edges.
 182 //
 183 template <> struct GraphTraits<Inverse<BasicBlock*> > {
 184   typedef BasicBlock NodeType;
 185   typedef pred_iterator ChildIteratorType;
 186   static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
 187   static inline ChildIteratorType child_begin(NodeType *N) {
 188     return pred_begin(N);
 189   }
 190   static inline ChildIteratorType child_end(NodeType *N) {
 191     return pred_end(N);
 192   }
 193 };
 194
 195 template <> struct GraphTraits<Inverse<const BasicBlock*> > {
 196   typedef const BasicBlock NodeType;
 197   typedef pred_const_iterator ChildIteratorType;
 198   static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
 199     return G.Graph;
 200   }
 201   static inline ChildIteratorType child_begin(NodeType *N) {
 202     return pred_begin(N);
 203   }
 204   static inline ChildIteratorType child_end(NodeType *N) {
 205     return pred_end(N);
 206   }
 207 };
 208
 209
 210
 211 //===--------------------------------------------------------------------===//
 212 // GraphTraits specializations for function basic block graphs (CFGs)
 213 //===--------------------------------------------------------------------===//
 214
 215 // Provide specializations of GraphTraits to be able to treat a function as a
 216 // graph of basic blocks... these are the same as the basic block iterators,
 217 // except that the root node is implicitly the first node of the function.
 218 //
 219 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
 220   static NodeType *getEntryNode(Function *F) { return &F->getEntryNode(); }
 221
 222   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 223   typedef Function::iterator nodes_iterator;
 224   static nodes_iterator nodes_begin(Function *F) { return F->begin(); }
 225   static nodes_iterator nodes_end  (Function *F) { return F->end(); }
 226 };
 227 template <> struct GraphTraits<const Function*> :
 228   public GraphTraits<const BasicBlock*> {
 229   static NodeType *getEntryNode(const Function *F) { return &F->getEntryNode();}
 230
 231   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 232   typedef Function::const_iterator nodes_iterator;
 233   static nodes_iterator nodes_begin(const Function *F) { return F->begin(); }
 234   static nodes_iterator nodes_end  (const Function *F) { return F->end(); }
 235 };
 236
 237
 238 // Provide specializations of GraphTraits to be able to treat a function as a
 239 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 240 // a function is considered to be when traversing the predecessor edges of a BB
 241 // instead of the successor edges.
 242 //
 243 template <> struct GraphTraits<Inverse<Function*> > :
 244   public GraphTraits<Inverse<BasicBlock*> > {
 245   static NodeType *getEntryNode(Inverse<Function*> G) {
 246     return &G.Graph->getEntryNode();
 247   }
 248 };
 249 template <> struct GraphTraits<Inverse<const Function*> > :
 250   public GraphTraits<Inverse<const BasicBlock*> > {
 251   static NodeType *getEntryNode(Inverse<const Function *> G) {
 252     return &G.Graph->getEntryNode();
 253   }
 254 };
 255
 256 #endif