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