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