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