include/llvm/BasicBlock.h

   1 //===-- llvm/BasicBlock.h - Represent a basic block in the VM ----*- C++ -*--=//
   2 //
   3 // This file contains the declaration of the BasicBlock class, which represents
   4 // a single basic block in the VM.
   5 //
   6 // Note that basic blocks themselves are Def's, because they are referenced
   7 // by instructions like branches and can go in switch tables and stuff...
   8 //
   9 // This may see wierd at first, but it's really pretty cool.  :)
  10 //
  11 //===----------------------------------------------------------------------===//
  12 //
  13 // Note that well formed basic blocks are formed of a list of instructions
  14 // followed by a single TerminatorInst instruction.  TerminatorInst's may not
  15 // occur in the middle of basic blocks, and must terminate the blocks.
  16 //
  17 // This code allows malformed basic blocks to occur, because it may be useful
  18 // in the intermediate stage of analysis or modification of a program.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #ifndef LLVM_BASICBLOCK_H
  23 #define LLVM_BASICBLOCK_H
  24
  25 #include "llvm/Value.h"
  26 #include "llvm/ValueHolder.h"
  27 #include "llvm/Support/GraphTraits.h"
  28 #include "llvm/InstrTypes.h"
  29 #include <iterator>
  30
  31 class Instruction;
  32 class Method;
  33 class TerminatorInst;
  34 class MachineCodeForBasicBlock;
  35
  36 class BasicBlock : public Value {       // Basic blocks are data objects also
  37   template <class _Ptr, class _USE_iterator> class PredIterator;
  38   template <class _Term, class _BB> class SuccIterator;
  39 public:
  40   typedef ValueHolder<Instruction, BasicBlock, Method> InstListType;
  41 private :
  42   InstListType InstList;
  43   MachineCodeForBasicBlock* machineInstrVec;
  44
  45   friend class ValueHolder<BasicBlock,Method,Method>;
  46   void setParent(Method *parent);
  47
  48 public:
  49   // Instruction iterators...
  50   typedef InstListType::iterator iterator;
  51   typedef InstListType::const_iterator const_iterator;
  52   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  53   typedef reverse_iterator<iterator>             reverse_iterator;
  54
  55   // Predecessor and successor iterators...
  56   typedef PredIterator<BasicBlock, Value::use_iterator> pred_iterator;
  57   typedef PredIterator<const BasicBlock,
  58                        Value::use_const_iterator> pred_const_iterator;
  59   typedef SuccIterator<TerminatorInst*, BasicBlock> succ_iterator;
  60   typedef SuccIterator<const TerminatorInst*,
  61                        const BasicBlock> succ_const_iterator;
  62
  63   // Ctor, dtor
  64   BasicBlock(const string &Name = "", Method *Parent = 0);
  65   ~BasicBlock();
  66
  67   // Specialize setName to take care of symbol table majik
  68   virtual void setName(const string &name, SymbolTable *ST = 0);
  69
  70   // getParent - Return the enclosing method, or null if none
  71   const Method *getParent() const { return InstList.getParent(); }
  72         Method *getParent()       { return InstList.getParent(); }
  73
  74   // getTerminator() - If this is a well formed basic block, then this returns
  75   // a pointer to the terminator instruction.  If it is not, then you get a null
  76   // pointer back.
  77   //
  78   TerminatorInst *getTerminator();
  79   const TerminatorInst *const getTerminator() const;
  80
  81   // Machine code accessor...
  82   inline MachineCodeForBasicBlock& getMachineInstrVec() const {
  83     return *machineInstrVec;
  84   }
  85
  86   //===--------------------------------------------------------------------===//
  87   // Instruction iterator methods
  88   //
  89   inline iterator                begin()       { return InstList.begin(); }
  90   inline const_iterator          begin() const { return InstList.begin(); }
  91   inline iterator                end  ()       { return InstList.end();   }
  92   inline const_iterator          end  () const { return InstList.end();   }
  93
  94   inline reverse_iterator       rbegin()       { return InstList.rbegin(); }
  95   inline const_reverse_iterator rbegin() const { return InstList.rbegin(); }
  96   inline reverse_iterator       rend  ()       { return InstList.rend();   }
  97   inline const_reverse_iterator rend  () const { return InstList.rend();   }
  98
  99   inline unsigned                 size() const { return InstList.size(); }
 100   inline bool                    empty() const { return InstList.empty(); }
 101   inline const Instruction      *front() const { return InstList.front(); }
 102   inline       Instruction      *front()       { return InstList.front(); }
 103   inline const Instruction       *back()  const { return InstList.back(); }
 104   inline       Instruction       *back()        { return InstList.back(); }
 105
 106   // getInstList() - Return the underlying instruction list container.  You need
 107   // to access it directly if you want to modify it currently.
 108   //
 109   const InstListType &getInstList() const { return InstList; }
 110         InstListType &getInstList()       { return InstList; }
 111
 112   // hasConstantPoolReferences() - This predicate is true if there is a
 113   // reference to this basic block in the constant pool for this method.  For
 114   // example, if a block is reached through a switch table, that table resides
 115   // in the constant pool, and the basic block is reference from it.
 116   //
 117   bool hasConstantPoolReferences() const;
 118
 119   // dropAllReferences() - This function causes all the subinstructions to "let
 120   // go" of all references that they are maintaining.  This allows one to
 121   // 'delete' a whole class at a time, even though there may be circular
 122   // references... first all references are dropped, and all use counts go to
 123   // zero.  Then everything is delete'd for real.  Note that no operations are
 124   // valid on an object that has "dropped all references", except operator
 125   // delete.
 126   //
 127   void dropAllReferences();
 128
 129   // removePredecessor - This method is used to notify a BasicBlock that the
 130   // specified Predecessor of the block is no longer able to reach it.  This is
 131   // actually not used to update the Predecessor list, but is actually used to
 132   // update the PHI nodes that reside in the block.  Note that this should be
 133   // called while the predecessor still refers to this block.
 134   //
 135   void removePredecessor(BasicBlock *Pred);
 136
 137   // splitBasicBlock - This splits a basic block into two at the specified
 138   // instruction.  Note that all instructions BEFORE the specified iterator stay
 139   // as part of the original basic block, an unconditional branch is added to
 140   // the new BB, and the rest of the instructions in the BB are moved to the new
 141   // BB, including the old terminator.  The newly formed BasicBlock is returned.
 142   // This function invalidates the specified iterator.
 143   //
 144   // Note that this only works on well formed basic blocks (must have a
 145   // terminator), and 'I' must not be the end of instruction list (which would
 146   // cause a degenerate basic block to be formed, having a terminator inside of
 147   // the basic block).
 148   //
 149   BasicBlock *splitBasicBlock(iterator I);
 150
 151
 152   //===--------------------------------------------------------------------===//
 153   // Predecessor and Successor Iterators
 154   //
 155   template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
 156   class PredIterator : public std::bidirectional_iterator<_Ptr, ptrdiff_t> {
 157     _Ptr *BB;
 158     _USE_iterator It;
 159   public:
 160     typedef PredIterator<_Ptr,_USE_iterator> _Self;
 161
 162     inline void advancePastConstPool() {
 163       // TODO: This is bad
 164       // Loop to ignore constant pool references
 165       while (It != BB->use_end() &&
 166              ((!isa<Instruction>(*It)) ||
 167               !(((Instruction*)(*It))->isTerminator())))
 168         ++It;
 169     }
 170
 171     inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) {
 172       advancePastConstPool();
 173     }
 174     inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {}
 175
 176     inline bool operator==(const _Self& x) const { return It == x.It; }
 177     inline bool operator!=(const _Self& x) const { return !operator==(x); }
 178
 179     inline pointer operator*() const {
 180       return cast<Instruction>(*It)->getParent();
 181     }
 182     inline pointer *operator->() const { return &(operator*()); }
 183
 184     inline _Self& operator++() {   // Preincrement
 185       ++It; advancePastConstPool();
 186       return *this;
 187     }
 188
 189     inline _Self operator++(int) { // Postincrement
 190       _Self tmp = *this; ++*this; return tmp;
 191     }
 192
 193     inline _Self& operator--() { --It; return *this; }  // Predecrement
 194     inline _Self operator--(int) { // Postdecrement
 195       _Self tmp = *this; --*this; return tmp;
 196     }
 197   };
 198
 199   inline pred_iterator pred_begin() { return pred_iterator(this); }
 200   inline pred_const_iterator pred_begin() const {
 201     return pred_const_iterator(this);
 202   }
 203   inline pred_iterator pred_end() { return pred_iterator(this, true); }
 204   inline pred_const_iterator pred_end() const {
 205     return pred_const_iterator(this, true);
 206   }
 207
 208   template <class _Term, class _BB>           // Successor Iterator
 209   class SuccIterator : public std::bidirectional_iterator<_BB, ptrdiff_t> {
 210     const _Term Term;
 211     unsigned idx;
 212   public:
 213     typedef SuccIterator<_Term, _BB> _Self;
 214     // TODO: This can be random access iterator, need operator+ and stuff tho
 215
 216     inline SuccIterator(_Term T) : Term(T), idx(0) {         // begin iterator
 217       assert(T && "getTerminator returned null!");
 218     }
 219     inline SuccIterator(_Term T, bool)                       // end iterator
 220       : Term(T), idx(Term->getNumSuccessors()) {
 221       assert(T && "getTerminator returned null!");
 222     }
 223
 224     inline bool operator==(const _Self& x) const { return idx == x.idx; }
 225     inline bool operator!=(const _Self& x) const { return !operator==(x); }
 226
 227     inline pointer operator*() const { return Term->getSuccessor(idx); }
 228     inline pointer operator->() const { return operator*(); }
 229
 230     inline _Self& operator++() { ++idx; return *this; } // Preincrement
 231     inline _Self operator++(int) { // Postincrement
 232       _Self tmp = *this; ++*this; return tmp;
 233     }
 234
 235     inline _Self& operator--() { --idx; return *this; }  // Predecrement
 236     inline _Self operator--(int) { // Postdecrement
 237       _Self tmp = *this; --*this; return tmp;
 238     }
 239   };
 240
 241   inline succ_iterator succ_begin() { return succ_iterator(getTerminator()); }
 242   inline succ_const_iterator succ_begin() const {
 243     return succ_const_iterator(getTerminator());
 244   }
 245   inline succ_iterator succ_end() {return succ_iterator(getTerminator(), true);}
 246   inline succ_const_iterator succ_end() const {
 247     return succ_const_iterator(getTerminator(), true);
 248   }
 249 };
 250
 251
 252 //===--------------------------------------------------------------------===//
 253 // GraphTraits specializations for basic block graphs (CFGs)
 254 //===--------------------------------------------------------------------===//
 255
 256 // Provide specializations of GraphTraits to be able to treat a method as a
 257 // graph of basic blocks...
 258
 259 template <> struct GraphTraits<BasicBlock*> {
 260   typedef BasicBlock NodeType;
 261   typedef BasicBlock::succ_iterator ChildIteratorType;
 262
 263   static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
 264   static inline ChildIteratorType child_begin(NodeType *N) {
 265     return N->succ_begin();
 266   }
 267   static inline ChildIteratorType child_end(NodeType *N) {
 268     return N->succ_end();
 269   }
 270 };
 271
 272 template <> struct GraphTraits<const BasicBlock*> {
 273   typedef const BasicBlock NodeType;
 274   typedef BasicBlock::succ_const_iterator ChildIteratorType;
 275
 276   static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
 277
 278   static inline ChildIteratorType child_begin(NodeType *N) {
 279     return N->succ_begin();
 280   }
 281   static inline ChildIteratorType child_end(NodeType *N) {
 282     return N->succ_end();
 283   }
 284 };
 285
 286 // Provide specializations of GraphTraits to be able to treat a method as a
 287 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 288 // a method is considered to be when traversing the predecessor edges of a BB
 289 // instead of the successor edges.
 290 //
 291 template <> struct GraphTraits<Inverse<BasicBlock*> > {
 292   typedef BasicBlock NodeType;
 293   typedef BasicBlock::pred_iterator ChildIteratorType;
 294   static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
 295   static inline ChildIteratorType child_begin(NodeType *N) {
 296     return N->pred_begin();
 297   }
 298   static inline ChildIteratorType child_end(NodeType *N) {
 299     return N->pred_end();
 300   }
 301 };
 302
 303 template <> struct GraphTraits<Inverse<const BasicBlock*> > {
 304   typedef const BasicBlock NodeType;
 305   typedef BasicBlock::pred_const_iterator ChildIteratorType;
 306   static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
 307     return G.Graph;
 308   }
 309   static inline ChildIteratorType child_begin(NodeType *N) {
 310     return N->pred_begin();
 311   }
 312   static inline ChildIteratorType child_end(NodeType *N) {
 313     return N->pred_end();
 314   }
 315 };
 316
 317
 318 #endif