include/llvm/CFG.h

   1 //===-- llvm/CFG.h - CFG definitions and useful classes ----------*- C++ -*--=//
   2 //
   3 // This file contains the class definitions useful for operating on the control
   4 // flow graph.
   5 //
   6 // Currently it contains functionality for these three applications:
   7 //
   8 //  1. Iterate over the predecessors of a basic block:
   9 //     pred_iterator, pred_const_iterator, pred_begin, pred_end
  10 //  2. Iterate over the successors of a basic block:
  11 //     succ_iterator, succ_const_iterator, succ_begin, succ_end
  12 //  3. Iterate over the basic blocks of a method in depth first ordering or
  13 //     reverse depth first order.  df_iterator, df_const_iterator,
  14 //     df_begin, df_end.  df_begin takes an arg to specify reverse or not.
  15 //  4. Iterator over the basic blocks of a method in post order.
  16 //  5. Iterator over a method in reverse post order.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #ifndef LLVM_CFG_H
  21 #define LLVM_CFG_H
  22
  23 #include "llvm/CFGdecls.h"      // See this file for concise interface info
  24 #include "llvm/BasicBlock.h"
  25 #include "llvm/InstrTypes.h"
  26 #include "llvm/Type.h"
  27 #include <iterator>
  28
  29 namespace cfg {
  30
  31 //===----------------------------------------------------------------------===//
  32 //                                Implementation
  33 //===----------------------------------------------------------------------===//
  34
  35 //===----------------------------------------------------------------------===//
  36 // Basic Block Predecessor Iterator
  37 //
  38
  39 template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
  40 class PredIterator : public std::bidirectional_iterator<_Ptr, ptrdiff_t> {
  41   _Ptr *BB;
  42   _USE_iterator It;
  43 public:
  44   typedef PredIterator<_Ptr,_USE_iterator> _Self;
  45
  46   inline void advancePastConstPool() {
  47     // TODO: This is bad
  48     // Loop to ignore constant pool references
  49     while (It != BB->use_end() &&
  50            ((!(*It)->isInstruction()) ||
  51             !(((Instruction*)(*It))->isTerminator())))
  52       ++It;
  53   }
  54
  55   inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) {
  56     advancePastConstPool();
  57   }
  58   inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {}
  59
  60   inline bool operator==(const _Self& x) const { return It == x.It; }
  61   inline bool operator!=(const _Self& x) const { return !operator==(x); }
  62
  63   inline pointer operator*() const {
  64     return (*It)->castInstructionAsserting()->getParent();
  65   }
  66   inline pointer *operator->() const { return &(operator*()); }
  67
  68   inline _Self& operator++() {   // Preincrement
  69     ++It; advancePastConstPool();
  70     return *this;
  71   }
  72
  73   inline _Self operator++(int) { // Postincrement
  74     _Self tmp = *this; ++*this; return tmp;
  75   }
  76
  77   inline _Self& operator--() { --It; return *this; }  // Predecrement
  78   inline _Self operator--(int) { // Postdecrement
  79     _Self tmp = *this; --*this; return tmp;
  80   }
  81 };
  82
  83 inline pred_iterator       pred_begin(      BasicBlock *BB) {
  84   return pred_iterator(BB);
  85 }
  86 inline pred_const_iterator pred_begin(const BasicBlock *BB) {
  87   return pred_const_iterator(BB);
  88 }
  89 inline pred_iterator       pred_end(      BasicBlock *BB) {
  90   return pred_iterator(BB,true);
  91 }
  92 inline pred_const_iterator pred_end(const BasicBlock *BB) {
  93   return pred_const_iterator(BB,true);
  94 }
  95
  96
  97 //===----------------------------------------------------------------------===//
  98 // Basic Block Successor Iterator
  99 //
 100
 101 template <class _Term, class _BB>           // Successor Iterator
 102 class SuccIterator : public std::bidirectional_iterator<_BB, ptrdiff_t> {
 103   const _Term Term;
 104   unsigned idx;
 105 public:
 106   typedef SuccIterator<_Term, _BB> _Self;
 107   // TODO: This can be random access iterator, need operator+ and stuff tho
 108
 109   inline SuccIterator(_Term T) : Term(T), idx(0) {         // begin iterator
 110     assert(T && "getTerminator returned null!");
 111   }
 112   inline SuccIterator(_Term T, bool)                       // end iterator
 113     : Term(T), idx(Term->getNumSuccessors()) {
 114     assert(T && "getTerminator returned null!");
 115   }
 116
 117   inline bool operator==(const _Self& x) const { return idx == x.idx; }
 118   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 119
 120   inline pointer operator*() const { return Term->getSuccessor(idx); }
 121   inline pointer operator->() const { return operator*(); }
 122
 123   inline _Self& operator++() { ++idx; return *this; } // Preincrement
 124   inline _Self operator++(int) { // Postincrement
 125     _Self tmp = *this; ++*this; return tmp;
 126   }
 127
 128   inline _Self& operator--() { --idx; return *this; }  // Predecrement
 129   inline _Self operator--(int) { // Postdecrement
 130     _Self tmp = *this; --*this; return tmp;
 131   }
 132 };
 133
 134 inline succ_iterator       succ_begin(      BasicBlock *BB) {
 135   return succ_iterator(BB->getTerminator());
 136 }
 137 inline succ_const_iterator succ_begin(const BasicBlock *BB) {
 138   return succ_const_iterator(BB->getTerminator());
 139 }
 140 inline succ_iterator       succ_end(      BasicBlock *BB) {
 141   return succ_iterator(BB->getTerminator(),true);
 142 }
 143 inline succ_const_iterator succ_end(const BasicBlock *BB) {
 144   return succ_const_iterator(BB->getTerminator(),true);
 145 }
 146
 147 }    // End namespace cfg
 148
 149 #endif