include/llvm/IR/BasicBlock.h

   1 //===-- llvm/BasicBlock.h - Represent a basic block in the VM ---*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains the declaration of the BasicBlock class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_IR_BASICBLOCK_H
  15 #define LLVM_IR_BASICBLOCK_H
  16
  17 #include "llvm/ADT/Twine.h"
  18 #include "llvm/ADT/ilist.h"
  19 #include "llvm/IR/Instruction.h"
  20 #include "llvm/IR/SymbolTableListTraits.h"
  21 #include "llvm/Support/CBindingWrapping.h"
  22 #include "llvm/Support/DataTypes.h"
  23
  24 namespace llvm {
  25
  26 class CallInst;
  27 class LandingPadInst;
  28 class TerminatorInst;
  29 class LLVMContext;
  30 class BlockAddress;
  31 class Function;
  32
  33 template <>
  34 struct SymbolTableListSentinelTraits<BasicBlock>
  35     : public ilist_half_embedded_sentinel_traits<BasicBlock> {};
  36
  37 /// \brief LLVM Basic Block Representation
  38 ///
  39 /// This represents a single basic block in LLVM. A basic block is simply a
  40 /// container of instructions that execute sequentially. Basic blocks are Values
  41 /// because they are referenced by instructions such as branches and switch
  42 /// tables. The type of a BasicBlock is "Type::LabelTy" because the basic block
  43 /// represents a label to which a branch can jump.
  44 ///
  45 /// A well formed basic block is formed of a list of non-terminating
  46 /// instructions followed by a single TerminatorInst instruction.
  47 /// TerminatorInst's may not occur in the middle of basic blocks, and must
  48 /// terminate the blocks. The BasicBlock class allows malformed basic blocks to
  49 /// occur because it may be useful in the intermediate stage of constructing or
  50 /// modifying a program. However, the verifier will ensure that basic blocks
  51 /// are "well formed".
  52 class BasicBlock : public Value, // Basic blocks are data objects also
  53                    public ilist_node_with_parent<BasicBlock, Function> {
  54   friend class BlockAddress;
  55 public:
  56   typedef SymbolTableList<Instruction> InstListType;
  57
  58 private:
  59   InstListType InstList;
  60   Function *Parent;
  61
  62   // XXX-update: A flag that checks whether we can eliminate this block.
  63   bool canEliminateBlock;
  64
  65   void setParent(Function *parent);
  66   friend class SymbolTableListTraits<BasicBlock>;
  67
  68   BasicBlock(const BasicBlock &) = delete;
  69   void operator=(const BasicBlock &) = delete;
  70
  71   /// \brief Constructor.
  72   ///
  73   /// If the function parameter is specified, the basic block is automatically
  74   /// inserted at either the end of the function (if InsertBefore is null), or
  75   /// before the specified basic block.
  76   explicit BasicBlock(LLVMContext &C, const Twine &Name = "",
  77                       Function *Parent = nullptr,
  78                       BasicBlock *InsertBefore = nullptr);
  79 public:
  80   // XXX-update:
  81   void disableCanEliminateBlock() {
  82     canEliminateBlock = false;
  83   }
  84
  85   bool getCanEliminateBlock() {
  86     return canEliminateBlock;
  87   }
  88
  89
  90   /// \brief Get the context in which this basic block lives.
  91   LLVMContext &getContext() const;
  92
  93   /// Instruction iterators...
  94   typedef InstListType::iterator iterator;
  95   typedef InstListType::const_iterator const_iterator;
  96   typedef InstListType::reverse_iterator reverse_iterator;
  97   typedef InstListType::const_reverse_iterator const_reverse_iterator;
  98
  99   /// \brief Creates a new BasicBlock.
 100   ///
 101   /// If the Parent parameter is specified, the basic block is automatically
 102   /// inserted at either the end of the function (if InsertBefore is 0), or
 103   /// before the specified basic block.
 104   static BasicBlock *Create(LLVMContext &Context, const Twine &Name = "",
 105                             Function *Parent = nullptr,
 106                             BasicBlock *InsertBefore = nullptr) {
 107     return new BasicBlock(Context, Name, Parent, InsertBefore);
 108   }
 109   ~BasicBlock() override;
 110
 111   /// \brief Return the enclosing method, or null if none.
 112   const Function *getParent() const { return Parent; }
 113         Function *getParent()       { return Parent; }
 114
 115   /// \brief Return the module owning the function this basic block belongs to,
 116   /// or nullptr it the function does not have a module.
 117   ///
 118   /// Note: this is undefined behavior if the block does not have a parent.
 119   const Module *getModule() const;
 120   Module *getModule();
 121
 122   /// \brief Returns the terminator instruction if the block is well formed or
 123   /// null if the block is not well formed.
 124   TerminatorInst *getTerminator();
 125   const TerminatorInst *getTerminator() const;
 126
 127   /// \brief Returns the call instruction marked 'musttail' prior to the
 128   /// terminating return instruction of this basic block, if such a call is
 129   /// present.  Otherwise, returns null.
 130   CallInst *getTerminatingMustTailCall();
 131   const CallInst *getTerminatingMustTailCall() const {
 132     return const_cast<BasicBlock *>(this)->getTerminatingMustTailCall();
 133   }
 134
 135   /// \brief Returns a pointer to the first instruction in this block that is
 136   /// not a PHINode instruction.
 137   ///
 138   /// When adding instructions to the beginning of the basic block, they should
 139   /// be added before the returned value, not before the first instruction,
 140   /// which might be PHI. Returns 0 is there's no non-PHI instruction.
 141   Instruction* getFirstNonPHI();
 142   const Instruction* getFirstNonPHI() const {
 143     return const_cast<BasicBlock*>(this)->getFirstNonPHI();
 144   }
 145
 146   /// \brief Returns a pointer to the first instruction in this block that is not
 147   /// a PHINode or a debug intrinsic.
 148   Instruction* getFirstNonPHIOrDbg();
 149   const Instruction* getFirstNonPHIOrDbg() const {
 150     return const_cast<BasicBlock*>(this)->getFirstNonPHIOrDbg();
 151   }
 152
 153   /// \brief Returns a pointer to the first instruction in this block that is not
 154   /// a PHINode, a debug intrinsic, or a lifetime intrinsic.
 155   Instruction* getFirstNonPHIOrDbgOrLifetime();
 156   const Instruction* getFirstNonPHIOrDbgOrLifetime() const {
 157     return const_cast<BasicBlock*>(this)->getFirstNonPHIOrDbgOrLifetime();
 158   }
 159
 160   /// \brief Returns an iterator to the first instruction in this block that is
 161   /// suitable for inserting a non-PHI instruction.
 162   ///
 163   /// In particular, it skips all PHIs and LandingPad instructions.
 164   iterator getFirstInsertionPt();
 165   const_iterator getFirstInsertionPt() const {
 166     return const_cast<BasicBlock*>(this)->getFirstInsertionPt();
 167   }
 168
 169   /// \brief Unlink 'this' from the containing function, but do not delete it.
 170   void removeFromParent();
 171
 172   /// \brief Unlink 'this' from the containing function and delete it.
 173   ///
 174   // \returns an iterator pointing to the element after the erased one.
 175   SymbolTableList<BasicBlock>::iterator eraseFromParent();
 176
 177   /// \brief Unlink this basic block from its current function and insert it
 178   /// into the function that \p MovePos lives in, right before \p MovePos.
 179   void moveBefore(BasicBlock *MovePos);
 180
 181   /// \brief Unlink this basic block from its current function and insert it
 182   /// right after \p MovePos in the function \p MovePos lives in.
 183   void moveAfter(BasicBlock *MovePos);
 184
 185   /// \brief Insert unlinked basic block into a function.
 186   ///
 187   /// Inserts an unlinked basic block into \c Parent.  If \c InsertBefore is
 188   /// provided, inserts before that basic block, otherwise inserts at the end.
 189   ///
 190   /// \pre \a getParent() is \c nullptr.
 191   void insertInto(Function *Parent, BasicBlock *InsertBefore = nullptr);
 192
 193   /// \brief Return the predecessor of this block if it has a single predecessor
 194   /// block. Otherwise return a null pointer.
 195   BasicBlock *getSinglePredecessor();
 196   const BasicBlock *getSinglePredecessor() const {
 197     return const_cast<BasicBlock*>(this)->getSinglePredecessor();
 198   }
 199
 200   /// \brief Return the predecessor of this block if it has a unique predecessor
 201   /// block. Otherwise return a null pointer.
 202   ///
 203   /// Note that unique predecessor doesn't mean single edge, there can be
 204   /// multiple edges from the unique predecessor to this block (for example a
 205   /// switch statement with multiple cases having the same destination).
 206   BasicBlock *getUniquePredecessor();
 207   const BasicBlock *getUniquePredecessor() const {
 208     return const_cast<BasicBlock*>(this)->getUniquePredecessor();
 209   }
 210
 211   /// \brief Return the successor of this block if it has a single successor.
 212   /// Otherwise return a null pointer.
 213   ///
 214   /// This method is analogous to getSinglePredecessor above.
 215   BasicBlock *getSingleSuccessor();
 216   const BasicBlock *getSingleSuccessor() const {
 217     return const_cast<BasicBlock*>(this)->getSingleSuccessor();
 218   }
 219
 220   /// \brief Return the successor of this block if it has a unique successor.
 221   /// Otherwise return a null pointer.
 222   ///
 223   /// This method is analogous to getUniquePredecessor above.
 224   BasicBlock *getUniqueSuccessor();
 225   const BasicBlock *getUniqueSuccessor() const {
 226     return const_cast<BasicBlock*>(this)->getUniqueSuccessor();
 227   }
 228
 229   //===--------------------------------------------------------------------===//
 230   /// Instruction iterator methods
 231   ///
 232   inline iterator                begin()       { return InstList.begin(); }
 233   inline const_iterator          begin() const { return InstList.begin(); }
 234   inline iterator                end  ()       { return InstList.end();   }
 235   inline const_iterator          end  () const { return InstList.end();   }
 236
 237   inline reverse_iterator        rbegin()       { return InstList.rbegin(); }
 238   inline const_reverse_iterator  rbegin() const { return InstList.rbegin(); }
 239   inline reverse_iterator        rend  ()       { return InstList.rend();   }
 240   inline const_reverse_iterator  rend  () const { return InstList.rend();   }
 241
 242   inline size_t                   size() const { return InstList.size();  }
 243   inline bool                    empty() const { return InstList.empty(); }
 244   inline const Instruction      &front() const { return InstList.front(); }
 245   inline       Instruction      &front()       { return InstList.front(); }
 246   inline const Instruction       &back() const { return InstList.back();  }
 247   inline       Instruction       &back()       { return InstList.back();  }
 248
 249   /// \brief Return the underlying instruction list container.
 250   ///
 251   /// Currently you need to access the underlying instruction list container
 252   /// directly if you want to modify it.
 253   const InstListType &getInstList() const { return InstList; }
 254         InstListType &getInstList()       { return InstList; }
 255
 256   /// \brief Returns a pointer to a member of the instruction list.
 257   static InstListType BasicBlock::*getSublistAccess(Instruction*) {
 258     return &BasicBlock::InstList;
 259   }
 260
 261   /// \brief Returns a pointer to the symbol table if one exists.
 262   ValueSymbolTable *getValueSymbolTable();
 263
 264   /// \brief Methods for support type inquiry through isa, cast, and dyn_cast.
 265   static inline bool classof(const Value *V) {
 266     return V->getValueID() == Value::BasicBlockVal;
 267   }
 268
 269   /// \brief Cause all subinstructions to "let go" of all the references that
 270   /// said subinstructions are maintaining.
 271   ///
 272   /// This allows one to 'delete' a whole class at a time, even though there may
 273   /// be circular references... first all references are dropped, and all use
 274   /// counts go to zero.  Then everything is delete'd for real.  Note that no
 275   /// operations are valid on an object that has "dropped all references",
 276   /// except operator delete.
 277   void dropAllReferences();
 278
 279   /// \brief Notify the BasicBlock that the predecessor \p Pred is no longer
 280   /// able to reach it.
 281   ///
 282   /// This is actually not used to update the Predecessor list, but is actually
 283   /// used to update the PHI nodes that reside in the block.  Note that this
 284   /// should be called while the predecessor still refers to this block.
 285   void removePredecessor(BasicBlock *Pred, bool DontDeleteUselessPHIs = false);
 286
 287   bool canSplitPredecessors() const;
 288
 289   /// \brief Split the basic block into two basic blocks at the specified
 290   /// instruction.
 291   ///
 292   /// Note that all instructions BEFORE the specified iterator stay as part of
 293   /// the original basic block, an unconditional branch is added to the original
 294   /// BB, and the rest of the instructions in the BB are moved to the new BB,
 295   /// including the old terminator.  The newly formed BasicBlock is returned.
 296   /// This function invalidates the specified iterator.
 297   ///
 298   /// Note that this only works on well formed basic blocks (must have a
 299   /// terminator), and 'I' must not be the end of instruction list (which would
 300   /// cause a degenerate basic block to be formed, having a terminator inside of
 301   /// the basic block).
 302   ///
 303   /// Also note that this doesn't preserve any passes. To split blocks while
 304   /// keeping loop information consistent, use the SplitBlock utility function.
 305   BasicBlock *splitBasicBlock(iterator I, const Twine &BBName = "");
 306   BasicBlock *splitBasicBlock(Instruction *I, const Twine &BBName = "") {
 307     return splitBasicBlock(I->getIterator(), BBName);
 308   }
 309
 310   /// \brief Returns true if there are any uses of this basic block other than
 311   /// direct branches, switches, etc. to it.
 312   bool hasAddressTaken() const { return getSubclassDataFromValue() != 0; }
 313
 314   /// \brief Update all phi nodes in this basic block's successors to refer to
 315   /// basic block \p New instead of to it.
 316   void replaceSuccessorsPhiUsesWith(BasicBlock *New);
 317
 318   /// \brief Return true if this basic block is an exception handling block.
 319   bool isEHPad() const { return getFirstNonPHI()->isEHPad(); }
 320
 321   /// \brief Return true if this basic block is a landing pad.
 322   ///
 323   /// Being a ``landing pad'' means that the basic block is the destination of
 324   /// the 'unwind' edge of an invoke instruction.
 325   bool isLandingPad() const;
 326
 327   /// \brief Return the landingpad instruction associated with the landing pad.
 328   LandingPadInst *getLandingPadInst();
 329   const LandingPadInst *getLandingPadInst() const;
 330
 331 private:
 332   /// \brief Increment the internal refcount of the number of BlockAddresses
 333   /// referencing this BasicBlock by \p Amt.
 334   ///
 335   /// This is almost always 0, sometimes one possibly, but almost never 2, and
 336   /// inconceivably 3 or more.
 337   void AdjustBlockAddressRefCount(int Amt) {
 338     setValueSubclassData(getSubclassDataFromValue()+Amt);
 339     assert((int)(signed char)getSubclassDataFromValue() >= 0 &&
 340            "Refcount wrap-around");
 341   }
 342   /// \brief Shadow Value::setValueSubclassData with a private forwarding method
 343   /// so that any future subclasses cannot accidentally use it.
 344   void setValueSubclassData(unsigned short D) {
 345     Value::setValueSubclassData(D);
 346   }
 347 };
 348
 349 // Create wrappers for C Binding types (see CBindingWrapping.h).
 350 DEFINE_SIMPLE_CONVERSION_FUNCTIONS(BasicBlock, LLVMBasicBlockRef)
 351
 352 } // End llvm namespace
 353
 354 #endif