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   // Methods for support type inquiry through isa, cast, and dyn_cast:
 113   static inline bool isa(const BasicBlock *BB) { return true; }
 114   static inline bool isa(const Value *V) {
 115     return V->getValueType() == Value::BasicBlockVal;
 116   }
 117
 118   // hasConstantPoolReferences() - This predicate is true if there is a
 119   // reference to this basic block in the constant pool for this method.  For
 120   // example, if a block is reached through a switch table, that table resides
 121   // in the constant pool, and the basic block is reference from it.
 122   //
 123   bool hasConstantPoolReferences() const;
 124
 125   // dropAllReferences() - This function causes all the subinstructions to "let
 126   // go" of all references that they are maintaining.  This allows one to
 127   // 'delete' a whole class at a time, even though there may be circular
 128   // references... first all references are dropped, and all use counts go to
 129   // zero.  Then everything is delete'd for real.  Note that no operations are
 130   // valid on an object that has "dropped all references", except operator
 131   // delete.
 132   //
 133   void dropAllReferences();
 134
 135   // removePredecessor - This method is used to notify a BasicBlock that the
 136   // specified Predecessor of the block is no longer able to reach it.  This is
 137   // actually not used to update the Predecessor list, but is actually used to
 138   // update the PHI nodes that reside in the block.  Note that this should be
 139   // called while the predecessor still refers to this block.
 140   //
 141   void removePredecessor(BasicBlock *Pred);
 142
 143   // splitBasicBlock - This splits a basic block into two at the specified
 144   // instruction.  Note that all instructions BEFORE the specified iterator stay
 145   // as part of the original basic block, an unconditional branch is added to
 146   // the new BB, and the rest of the instructions in the BB are moved to the new
 147   // BB, including the old terminator.  The newly formed BasicBlock is returned.
 148   // This function invalidates the specified iterator.
 149   //
 150   // Note that this only works on well formed basic blocks (must have a
 151   // terminator), and 'I' must not be the end of instruction list (which would
 152   // cause a degenerate basic block to be formed, having a terminator inside of
 153   // the basic block).
 154   //
 155   BasicBlock *splitBasicBlock(iterator I);
 156
 157
 158   //===--------------------------------------------------------------------===//
 159   // Predecessor and Successor Iterators
 160   //
 161   template <class _Ptr,  class _USE_iterator> // Predecessor Iterator
 162   class PredIterator : public std::bidirectional_iterator<_Ptr, ptrdiff_t> {
 163     _Ptr *BB;
 164     _USE_iterator It;
 165   public:
 166     typedef PredIterator<_Ptr,_USE_iterator> _Self;
 167
 168     inline void advancePastConstPool() {
 169       // TODO: This is bad
 170       // Loop to ignore constant pool references
 171       while (It != BB->use_end() &&
 172              (((*It)->getValueType() != Value::InstructionVal) ||
 173               !(((Instruction*)(*It))->isTerminator())))
 174         ++It;
 175     }
 176
 177     inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) {
 178       advancePastConstPool();
 179     }
 180     inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {}
 181
 182     inline bool operator==(const _Self& x) const { return It == x.It; }
 183     inline bool operator!=(const _Self& x) const { return !operator==(x); }
 184
 185     inline pointer operator*() const {
 186       return cast<Instruction>(*It)->getParent();
 187     }
 188     inline pointer *operator->() const { return &(operator*()); }
 189
 190     inline _Self& operator++() {   // Preincrement
 191       ++It; advancePastConstPool();
 192       return *this;
 193     }
 194
 195     inline _Self operator++(int) { // Postincrement
 196       _Self tmp = *this; ++*this; return tmp;
 197     }
 198
 199     inline _Self& operator--() { --It; return *this; }  // Predecrement
 200     inline _Self operator--(int) { // Postdecrement
 201       _Self tmp = *this; --*this; return tmp;
 202     }
 203   };
 204
 205   inline pred_iterator pred_begin() { return pred_iterator(this); }
 206   inline pred_const_iterator pred_begin() const {
 207     return pred_const_iterator(this);
 208   }
 209   inline pred_iterator pred_end() { return pred_iterator(this, true); }
 210   inline pred_const_iterator pred_end() const {
 211     return pred_const_iterator(this, true);
 212   }
 213
 214   template <class _Term, class _BB>           // Successor Iterator
 215   class SuccIterator : public std::bidirectional_iterator<_BB, ptrdiff_t> {
 216     const _Term Term;
 217     unsigned idx;
 218   public:
 219     typedef SuccIterator<_Term, _BB> _Self;
 220     // TODO: This can be random access iterator, need operator+ and stuff tho
 221
 222     inline SuccIterator(_Term T) : Term(T), idx(0) {         // begin iterator
 223       assert(T && "getTerminator returned null!");
 224     }
 225     inline SuccIterator(_Term T, bool)                       // end iterator
 226       : Term(T), idx(Term->getNumSuccessors()) {
 227       assert(T && "getTerminator returned null!");
 228     }
 229
 230     inline bool operator==(const _Self& x) const { return idx == x.idx; }
 231     inline bool operator!=(const _Self& x) const { return !operator==(x); }
 232
 233     inline pointer operator*() const { return Term->getSuccessor(idx); }
 234     inline pointer operator->() const { return operator*(); }
 235
 236     inline _Self& operator++() { ++idx; return *this; } // Preincrement
 237     inline _Self operator++(int) { // Postincrement
 238       _Self tmp = *this; ++*this; return tmp;
 239     }
 240
 241     inline _Self& operator--() { --idx; return *this; }  // Predecrement
 242     inline _Self operator--(int) { // Postdecrement
 243       _Self tmp = *this; --*this; return tmp;
 244     }
 245   };
 246
 247   inline succ_iterator succ_begin() { return succ_iterator(getTerminator()); }
 248   inline succ_const_iterator succ_begin() const {
 249     return succ_const_iterator(getTerminator());
 250   }
 251   inline succ_iterator succ_end() {return succ_iterator(getTerminator(), true);}
 252   inline succ_const_iterator succ_end() const {
 253     return succ_const_iterator(getTerminator(), true);
 254   }
 255 };
 256
 257
 258 //===--------------------------------------------------------------------===//
 259 // GraphTraits specializations for basic block graphs (CFGs)
 260 //===--------------------------------------------------------------------===//
 261
 262 // Provide specializations of GraphTraits to be able to treat a method as a
 263 // graph of basic blocks...
 264
 265 template <> struct GraphTraits<BasicBlock*> {
 266   typedef BasicBlock NodeType;
 267   typedef BasicBlock::succ_iterator ChildIteratorType;
 268
 269   static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
 270   static inline ChildIteratorType child_begin(NodeType *N) {
 271     return N->succ_begin();
 272   }
 273   static inline ChildIteratorType child_end(NodeType *N) {
 274     return N->succ_end();
 275   }
 276 };
 277
 278 template <> struct GraphTraits<const BasicBlock*> {
 279   typedef const BasicBlock NodeType;
 280   typedef BasicBlock::succ_const_iterator ChildIteratorType;
 281
 282   static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
 283
 284   static inline ChildIteratorType child_begin(NodeType *N) {
 285     return N->succ_begin();
 286   }
 287   static inline ChildIteratorType child_end(NodeType *N) {
 288     return N->succ_end();
 289   }
 290 };
 291
 292 // Provide specializations of GraphTraits to be able to treat a method as a
 293 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 294 // a method is considered to be when traversing the predecessor edges of a BB
 295 // instead of the successor edges.
 296 //
 297 template <> struct GraphTraits<Inverse<BasicBlock*> > {
 298   typedef BasicBlock NodeType;
 299   typedef BasicBlock::pred_iterator ChildIteratorType;
 300   static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
 301   static inline ChildIteratorType child_begin(NodeType *N) {
 302     return N->pred_begin();
 303   }
 304   static inline ChildIteratorType child_end(NodeType *N) {
 305     return N->pred_end();
 306   }
 307 };
 308
 309 template <> struct GraphTraits<Inverse<const BasicBlock*> > {
 310   typedef const BasicBlock NodeType;
 311   typedef BasicBlock::pred_const_iterator ChildIteratorType;
 312   static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
 313     return G.Graph;
 314   }
 315   static inline ChildIteratorType child_begin(NodeType *N) {
 316     return N->pred_begin();
 317   }
 318   static inline ChildIteratorType child_end(NodeType *N) {
 319     return N->pred_end();
 320   }
 321 };
 322
 323
 324 #endif