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