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/InstrTypes.h"
  28 #include "Support/GraphTraits.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 std::reverse_iterator<const_iterator> const_reverse_iterator;
  53   typedef std::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 std::string &Name = "", Method *Parent = 0);
  65   ~BasicBlock();
  66
  67   // Specialize setName to take care of symbol table majik
  68   virtual void setName(const std::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 classof(const BasicBlock *BB) { return true; }
 114   static inline bool classof(const Value *V) {
 115     return V->getValueType() == Value::BasicBlockVal;
 116   }
 117
 118   // hasConstantReferences() - 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 hasConstantReferences() 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 advancePastConstants() {
 169       // TODO: This is bad
 170       // Loop to ignore constant pool references
 171       while (It != BB->use_end() && !isa<TerminatorInst>(*It))
 172         ++It;
 173     }
 174
 175     inline PredIterator(_Ptr *bb) : BB(bb), It(bb->use_begin()) {
 176       advancePastConstants();
 177     }
 178     inline PredIterator(_Ptr *bb, bool) : BB(bb), It(bb->use_end()) {}
 179
 180     inline bool operator==(const _Self& x) const { return It == x.It; }
 181     inline bool operator!=(const _Self& x) const { return !operator==(x); }
 182
 183     inline pointer operator*() const {
 184       return cast<Instruction>(*It)->getParent();
 185     }
 186     inline pointer *operator->() const { return &(operator*()); }
 187
 188     inline _Self& operator++() {   // Preincrement
 189       ++It; advancePastConstants();
 190       return *this;
 191     }
 192
 193     inline _Self operator++(int) { // Postincrement
 194       _Self tmp = *this; ++*this; return tmp;
 195     }
 196
 197     inline _Self& operator--() { --It; return *this; }  // Predecrement
 198     inline _Self operator--(int) { // Postdecrement
 199       _Self tmp = *this; --*this; return tmp;
 200     }
 201   };
 202
 203   inline pred_iterator pred_begin() { return pred_iterator(this); }
 204   inline pred_const_iterator pred_begin() const {
 205     return pred_const_iterator(this);
 206   }
 207   inline pred_iterator pred_end() { return pred_iterator(this, true); }
 208   inline pred_const_iterator pred_end() const {
 209     return pred_const_iterator(this, true);
 210   }
 211
 212   template <class _Term, class _BB>           // Successor Iterator
 213   class SuccIterator : public std::bidirectional_iterator<_BB, ptrdiff_t> {
 214     const _Term Term;
 215     unsigned idx;
 216   public:
 217     typedef SuccIterator<_Term, _BB> _Self;
 218     // TODO: This can be random access iterator, need operator+ and stuff tho
 219
 220     inline SuccIterator(_Term T) : Term(T), idx(0) {         // begin iterator
 221       assert(T && "getTerminator returned null!");
 222     }
 223     inline SuccIterator(_Term T, bool)                       // end iterator
 224       : Term(T), idx(Term->getNumSuccessors()) {
 225       assert(T && "getTerminator returned null!");
 226     }
 227
 228     inline bool operator==(const _Self& x) const { return idx == x.idx; }
 229     inline bool operator!=(const _Self& x) const { return !operator==(x); }
 230
 231     inline pointer operator*() const { return Term->getSuccessor(idx); }
 232     inline pointer operator->() const { return operator*(); }
 233
 234     inline _Self& operator++() { ++idx; return *this; } // Preincrement
 235     inline _Self operator++(int) { // Postincrement
 236       _Self tmp = *this; ++*this; return tmp;
 237     }
 238
 239     inline _Self& operator--() { --idx; return *this; }  // Predecrement
 240     inline _Self operator--(int) { // Postdecrement
 241       _Self tmp = *this; --*this; return tmp;
 242     }
 243   };
 244
 245   inline succ_iterator succ_begin() { return succ_iterator(getTerminator()); }
 246   inline succ_const_iterator succ_begin() const {
 247     return succ_const_iterator(getTerminator());
 248   }
 249   inline succ_iterator succ_end() {return succ_iterator(getTerminator(), true);}
 250   inline succ_const_iterator succ_end() const {
 251     return succ_const_iterator(getTerminator(), true);
 252   }
 253 };
 254
 255
 256 //===--------------------------------------------------------------------===//
 257 // GraphTraits specializations for basic block graphs (CFGs)
 258 //===--------------------------------------------------------------------===//
 259
 260 // Provide specializations of GraphTraits to be able to treat a method as a
 261 // graph of basic blocks...
 262
 263 template <> struct GraphTraits<BasicBlock*> {
 264   typedef BasicBlock NodeType;
 265   typedef BasicBlock::succ_iterator ChildIteratorType;
 266
 267   static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
 268   static inline ChildIteratorType child_begin(NodeType *N) {
 269     return N->succ_begin();
 270   }
 271   static inline ChildIteratorType child_end(NodeType *N) {
 272     return N->succ_end();
 273   }
 274 };
 275
 276 template <> struct GraphTraits<const BasicBlock*> {
 277   typedef const BasicBlock NodeType;
 278   typedef BasicBlock::succ_const_iterator ChildIteratorType;
 279
 280   static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
 281
 282   static inline ChildIteratorType child_begin(NodeType *N) {
 283     return N->succ_begin();
 284   }
 285   static inline ChildIteratorType child_end(NodeType *N) {
 286     return N->succ_end();
 287   }
 288 };
 289
 290 // Provide specializations of GraphTraits to be able to treat a method as a
 291 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 292 // a method is considered to be when traversing the predecessor edges of a BB
 293 // instead of the successor edges.
 294 //
 295 template <> struct GraphTraits<Inverse<BasicBlock*> > {
 296   typedef BasicBlock NodeType;
 297   typedef BasicBlock::pred_iterator ChildIteratorType;
 298   static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
 299   static inline ChildIteratorType child_begin(NodeType *N) {
 300     return N->pred_begin();
 301   }
 302   static inline ChildIteratorType child_end(NodeType *N) {
 303     return N->pred_end();
 304   }
 305 };
 306
 307 template <> struct GraphTraits<Inverse<const BasicBlock*> > {
 308   typedef const BasicBlock NodeType;
 309   typedef BasicBlock::pred_const_iterator ChildIteratorType;
 310   static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
 311     return G.Graph;
 312   }
 313   static inline ChildIteratorType child_begin(NodeType *N) {
 314     return N->pred_begin();
 315   }
 316   static inline ChildIteratorType child_end(NodeType *N) {
 317     return N->pred_end();
 318   }
 319 };
 320
 321
 322 #endif