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 32 template<> struct ilist_traits<Instruction> 33 : public SymbolTableListTraits<Instruction, BasicBlock> { 34 35 /// \brief Return a node that marks the end of a list. 36 /// 37 /// The sentinel is relative to this instance, so we use a non-static 38 /// method. 39 Instruction *createSentinel() const { 40 // Since i(p)lists always publicly derive from their corresponding traits, 41 // placing a data member in this class will augment the i(p)list. But since 42 // the NodeTy is expected to be publicly derive from ilist_node<NodeTy>, 43 // there is a legal viable downcast from it to NodeTy. We use this trick to 44 // superimpose an i(p)list with a "ghostly" NodeTy, which becomes the 45 // sentinel. Dereferencing the sentinel is forbidden (save the 46 // ilist_node<NodeTy>), so no one will ever notice the superposition. 47 return static_cast<Instruction*>(&Sentinel); 48 } 49 static void destroySentinel(Instruction*) {} 50 51 Instruction *provideInitialHead() const { return createSentinel(); } 52 Instruction *ensureHead(Instruction*) const { return createSentinel(); } 53 static void noteHead(Instruction*, Instruction*) {} 54 private: 55 mutable ilist_half_node<Instruction> Sentinel; 56 }; 57 58 /// \brief LLVM Basic Block Representation 59 /// 60 /// This represents a single basic block in LLVM. A basic block is simply a 61 /// container of instructions that execute sequentially. Basic blocks are Values 62 /// because they are referenced by instructions such as branches and switch 63 /// tables. The type of a BasicBlock is "Type::LabelTy" because the basic block 64 /// represents a label to which a branch can jump. 65 /// 66 /// A well formed basic block is formed of a list of non-terminating 67 /// instructions followed by a single TerminatorInst instruction. 68 /// TerminatorInst's may not occur in the middle of basic blocks, and must 69 /// terminate the blocks. The BasicBlock class allows malformed basic blocks to 70 /// occur because it may be useful in the intermediate stage of constructing or 71 /// modifying a program. However, the verifier will ensure that basic blocks 72 /// are "well formed". 73 class BasicBlock : public Value, // Basic blocks are data objects also 74 public ilist_node<BasicBlock> { 75 friend class BlockAddress; 76 public: 77 typedef iplist<Instruction> InstListType; 78 private: 79 InstListType InstList; 80 Function *Parent; 81 82 void setParent(Function *parent); 83 friend class SymbolTableListTraits<BasicBlock, Function>; 84 85 BasicBlock(const BasicBlock &) LLVM_DELETED_FUNCTION; 86 void operator=(const BasicBlock &) LLVM_DELETED_FUNCTION; 87 88 /// \brief Constructor. 89 /// 90 /// If the function parameter is specified, the basic block is automatically 91 /// inserted at either the end of the function (if InsertBefore is null), or 92 /// before the specified basic block. 93 explicit BasicBlock(LLVMContext &C, const Twine &Name = "", 94 Function *Parent = nullptr, 95 BasicBlock *InsertBefore = nullptr); 96 public: 97 /// \brief Get the context in which this basic block lives. 98 LLVMContext &getContext() const; 99 100 /// Instruction iterators... 101 typedef InstListType::iterator iterator; 102 typedef InstListType::const_iterator const_iterator; 103 typedef InstListType::reverse_iterator reverse_iterator; 104 typedef InstListType::const_reverse_iterator const_reverse_iterator; 105 106 /// \brief Creates a new BasicBlock. 107 /// 108 /// If the Parent parameter is specified, the basic block is automatically 109 /// inserted at either the end of the function (if InsertBefore is 0), or 110 /// before the specified basic block. 111 static BasicBlock *Create(LLVMContext &Context, const Twine &Name = "", 112 Function *Parent = nullptr, 113 BasicBlock *InsertBefore = nullptr) { 114 return new BasicBlock(Context, Name, Parent, InsertBefore); 115 } 116 ~BasicBlock(); 117 118 /// \brief Return the enclosing method, or null if none. 119 const Function *getParent() const { return Parent; } 120 Function *getParent() { return Parent; } 121 122 const DataLayout *getDataLayout() const; 123 124 /// \brief Returns the terminator instruction if the block is well formed or 125 /// null if the block is not well formed. 126 TerminatorInst *getTerminator(); 127 const TerminatorInst *getTerminator() const; 128 129 /// \brief Returns the call instruction marked 'musttail' prior to the 130 /// terminating return instruction of this basic block, if such a call is 131 /// present. Otherwise, returns null. 132 CallInst *getTerminatingMustTailCall(); 133 const CallInst *getTerminatingMustTailCall() const { 134 return const_cast<BasicBlock *>(this)->getTerminatingMustTailCall(); 135 } 136 137 /// \brief Returns a pointer to the first instruction in this block that is 138 /// not a PHINode instruction. 139 /// 140 /// When adding instructions to the beginning of the basic block, they should 141 /// be added before the returned value, not before the first instruction, 142 /// which might be PHI. Returns 0 is there's no non-PHI instruction. 143 Instruction* getFirstNonPHI(); 144 const Instruction* getFirstNonPHI() const { 145 return const_cast<BasicBlock*>(this)->getFirstNonPHI(); 146 } 147 148 /// \brief Returns a pointer to the first instruction in this block that is not 149 /// a PHINode or a debug intrinsic. 150 Instruction* getFirstNonPHIOrDbg(); 151 const Instruction* getFirstNonPHIOrDbg() const { 152 return const_cast<BasicBlock*>(this)->getFirstNonPHIOrDbg(); 153 } 154 155 /// \brief Returns a pointer to the first instruction in this block that is not 156 /// a PHINode, a debug intrinsic, or a lifetime intrinsic. 157 Instruction* getFirstNonPHIOrDbgOrLifetime(); 158 const Instruction* getFirstNonPHIOrDbgOrLifetime() const { 159 return const_cast<BasicBlock*>(this)->getFirstNonPHIOrDbgOrLifetime(); 160 } 161 162 /// \brief Returns an iterator to the first instruction in this block that is 163 /// suitable for inserting a non-PHI instruction. 164 /// 165 /// In particular, it skips all PHIs and LandingPad instructions. 166 iterator getFirstInsertionPt(); 167 const_iterator getFirstInsertionPt() const { 168 return const_cast<BasicBlock*>(this)->getFirstInsertionPt(); 169 } 170 171 /// \brief Unlink 'this' from the containing function, but do not delete it. 172 void removeFromParent(); 173 174 /// \brief Unlink 'this' from the containing function and delete it. 175 void 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 //===--------------------------------------------------------------------===// 212 /// Instruction iterator methods 213 /// 214 inline iterator begin() { return InstList.begin(); } 215 inline const_iterator begin() const { return InstList.begin(); } 216 inline iterator end () { return InstList.end(); } 217 inline const_iterator end () const { return InstList.end(); } 218 219 inline reverse_iterator rbegin() { return InstList.rbegin(); } 220 inline const_reverse_iterator rbegin() const { return InstList.rbegin(); } 221 inline reverse_iterator rend () { return InstList.rend(); } 222 inline const_reverse_iterator rend () const { return InstList.rend(); } 223 224 inline size_t size() const { return InstList.size(); } 225 inline bool empty() const { return InstList.empty(); } 226 inline const Instruction &front() const { return InstList.front(); } 227 inline Instruction &front() { return InstList.front(); } 228 inline const Instruction &back() const { return InstList.back(); } 229 inline Instruction &back() { return InstList.back(); } 230 231 /// \brief Return the underlying instruction list container. 232 /// 233 /// Currently you need to access the underlying instruction list container 234 /// directly if you want to modify it. 235 const InstListType &getInstList() const { return InstList; } 236 InstListType &getInstList() { return InstList; } 237 238 /// \brief Returns a pointer to a member of the instruction list. 239 static iplist<Instruction> BasicBlock::*getSublistAccess(Instruction*) { 240 return &BasicBlock::InstList; 241 } 242 243 /// \brief Returns a pointer to the symbol table if one exists. 244 ValueSymbolTable *getValueSymbolTable(); 245 246 /// \brief Methods for support type inquiry through isa, cast, and dyn_cast. 247 static inline bool classof(const Value *V) { 248 return V->getValueID() == Value::BasicBlockVal; 249 } 250 251 /// \brief Cause all subinstructions to "let go" of all the references that 252 /// said subinstructions are maintaining. 253 /// 254 /// This allows one to 'delete' a whole class at a time, even though there may 255 /// be circular references... first all references are dropped, and all use 256 /// counts go to zero. Then everything is delete'd for real. Note that no 257 /// operations are valid on an object that has "dropped all references", 258 /// except operator delete. 259 void dropAllReferences(); 260 261 /// \brief Notify the BasicBlock that the predecessor \p Pred is no longer 262 /// able to reach it. 263 /// 264 /// This is actually not used to update the Predecessor list, but is actually 265 /// used to update the PHI nodes that reside in the block. Note that this 266 /// should be called while the predecessor still refers to this block. 267 void removePredecessor(BasicBlock *Pred, bool DontDeleteUselessPHIs = false); 268 269 /// \brief Split the basic block into two basic blocks at the specified 270 /// instruction. 271 /// 272 /// Note that all instructions BEFORE the specified iterator stay as part of 273 /// the original basic block, an unconditional branch is added to the original 274 /// BB, and the rest of the instructions in the BB are moved to the new BB, 275 /// including the old terminator. The newly formed BasicBlock is returned. 276 /// This function invalidates the specified iterator. 277 /// 278 /// Note that this only works on well formed basic blocks (must have a 279 /// terminator), and 'I' must not be the end of instruction list (which would 280 /// cause a degenerate basic block to be formed, having a terminator inside of 281 /// the basic block). 282 /// 283 /// Also note that this doesn't preserve any passes. To split blocks while 284 /// keeping loop information consistent, use the SplitBlock utility function. 285 BasicBlock *splitBasicBlock(iterator I, const Twine &BBName = ""); 286 287 /// \brief Returns true if there are any uses of this basic block other than 288 /// direct branches, switches, etc. to it. 289 bool hasAddressTaken() const { return getSubclassDataFromValue() != 0; } 290 291 /// \brief Update all phi nodes in this basic block's successors to refer to 292 /// basic block \p New instead of to it. 293 void replaceSuccessorsPhiUsesWith(BasicBlock *New); 294 295 /// \brief Return true if this basic block is a landing pad. 296 /// 297 /// Being a ``landing pad'' means that the basic block is the destination of 298 /// the 'unwind' edge of an invoke instruction. 299 bool isLandingPad() const; 300 301 /// \brief Return the landingpad instruction associated with the landing pad. 302 LandingPadInst *getLandingPadInst(); 303 const LandingPadInst *getLandingPadInst() const; 304 305 private: 306 /// \brief Increment the internal refcount of the number of BlockAddresses 307 /// referencing this BasicBlock by \p Amt. 308 /// 309 /// This is almost always 0, sometimes one possibly, but almost never 2, and 310 /// inconceivably 3 or more. 311 void AdjustBlockAddressRefCount(int Amt) { 312 setValueSubclassData(getSubclassDataFromValue()+Amt); 313 assert((int)(signed char)getSubclassDataFromValue() >= 0 && 314 "Refcount wrap-around"); 315 } 316 /// \brief Shadow Value::setValueSubclassData with a private forwarding method 317 /// so that any future subclasses cannot accidentally use it. 318 void setValueSubclassData(unsigned short D) { 319 Value::setValueSubclassData(D); 320 } 321 }; 322 323 // Create wrappers for C Binding types (see CBindingWrapping.h). 324 DEFINE_SIMPLE_CONVERSION_FUNCTIONS(BasicBlock, LLVMBasicBlockRef) 325 326 } // End llvm namespace 327 328 #endif 329