1249259Sdim//===-- llvm/BasicBlock.h - Represent a basic block in the VM ---*- C++ -*-===// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim// This file contains the declaration of the BasicBlock class. 11249259Sdim// 12249259Sdim//===----------------------------------------------------------------------===// 13249259Sdim 14249259Sdim#ifndef LLVM_IR_BASICBLOCK_H 15249259Sdim#define LLVM_IR_BASICBLOCK_H 16249259Sdim 17249259Sdim#include "llvm/ADT/Twine.h" 18249259Sdim#include "llvm/ADT/ilist.h" 19249259Sdim#include "llvm/IR/Instruction.h" 20249259Sdim#include "llvm/IR/SymbolTableListTraits.h" 21251662Sdim#include "llvm/Support/CBindingWrapping.h" 22249259Sdim#include "llvm/Support/DataTypes.h" 23249259Sdim 24249259Sdimnamespace llvm { 25249259Sdim 26249259Sdimclass LandingPadInst; 27249259Sdimclass TerminatorInst; 28249259Sdimclass LLVMContext; 29249259Sdimclass BlockAddress; 30249259Sdim 31249259Sdimtemplate<> struct ilist_traits<Instruction> 32249259Sdim : public SymbolTableListTraits<Instruction, BasicBlock> { 33249259Sdim 34249259Sdim /// \brief Return a node that marks the end of a list. 35249259Sdim /// 36249259Sdim /// The sentinel is relative to this instance, so we use a non-static 37249259Sdim /// method. 38249259Sdim Instruction *createSentinel() const { 39249259Sdim // Since i(p)lists always publicly derive from their corresponding traits, 40249259Sdim // placing a data member in this class will augment the i(p)list. But since 41249259Sdim // the NodeTy is expected to be publicly derive from ilist_node<NodeTy>, 42249259Sdim // there is a legal viable downcast from it to NodeTy. We use this trick to 43249259Sdim // superimpose an i(p)list with a "ghostly" NodeTy, which becomes the 44249259Sdim // sentinel. Dereferencing the sentinel is forbidden (save the 45249259Sdim // ilist_node<NodeTy>), so no one will ever notice the superposition. 46249259Sdim return static_cast<Instruction*>(&Sentinel); 47249259Sdim } 48249259Sdim static void destroySentinel(Instruction*) {} 49249259Sdim 50249259Sdim Instruction *provideInitialHead() const { return createSentinel(); } 51249259Sdim Instruction *ensureHead(Instruction*) const { return createSentinel(); } 52249259Sdim static void noteHead(Instruction*, Instruction*) {} 53249259Sdimprivate: 54249259Sdim mutable ilist_half_node<Instruction> Sentinel; 55249259Sdim}; 56249259Sdim 57249259Sdim/// \brief LLVM Basic Block Representation 58249259Sdim/// 59249259Sdim/// This represents a single basic block in LLVM. A basic block is simply a 60249259Sdim/// container of instructions that execute sequentially. Basic blocks are Values 61249259Sdim/// because they are referenced by instructions such as branches and switch 62249259Sdim/// tables. The type of a BasicBlock is "Type::LabelTy" because the basic block 63249259Sdim/// represents a label to which a branch can jump. 64249259Sdim/// 65249259Sdim/// A well formed basic block is formed of a list of non-terminating 66249259Sdim/// instructions followed by a single TerminatorInst instruction. 67249259Sdim/// TerminatorInst's may not occur in the middle of basic blocks, and must 68249259Sdim/// terminate the blocks. The BasicBlock class allows malformed basic blocks to 69249259Sdim/// occur because it may be useful in the intermediate stage of constructing or 70249259Sdim/// modifying a program. However, the verifier will ensure that basic blocks 71249259Sdim/// are "well formed". 72249259Sdimclass BasicBlock : public Value, // Basic blocks are data objects also 73249259Sdim public ilist_node<BasicBlock> { 74249259Sdim friend class BlockAddress; 75249259Sdimpublic: 76249259Sdim typedef iplist<Instruction> InstListType; 77249259Sdimprivate: 78249259Sdim InstListType InstList; 79249259Sdim Function *Parent; 80249259Sdim 81249259Sdim void setParent(Function *parent); 82249259Sdim friend class SymbolTableListTraits<BasicBlock, Function>; 83249259Sdim 84249259Sdim BasicBlock(const BasicBlock &) LLVM_DELETED_FUNCTION; 85249259Sdim void operator=(const BasicBlock &) LLVM_DELETED_FUNCTION; 86249259Sdim 87249259Sdim /// \brief Constructor. 88249259Sdim /// 89249259Sdim /// If the function parameter is specified, the basic block is automatically 90249259Sdim /// inserted at either the end of the function (if InsertBefore is null), or 91249259Sdim /// before the specified basic block. 92249259Sdim explicit BasicBlock(LLVMContext &C, const Twine &Name = "", 93249259Sdim Function *Parent = 0, BasicBlock *InsertBefore = 0); 94249259Sdimpublic: 95249259Sdim /// \brief Get the context in which this basic block lives. 96249259Sdim LLVMContext &getContext() const; 97249259Sdim 98249259Sdim /// Instruction iterators... 99249259Sdim typedef InstListType::iterator iterator; 100249259Sdim typedef InstListType::const_iterator const_iterator; 101249259Sdim typedef InstListType::reverse_iterator reverse_iterator; 102249259Sdim typedef InstListType::const_reverse_iterator const_reverse_iterator; 103249259Sdim 104249259Sdim /// \brief Creates a new BasicBlock. 105249259Sdim /// 106249259Sdim /// If the Parent parameter is specified, the basic block is automatically 107249259Sdim /// inserted at either the end of the function (if InsertBefore is 0), or 108249259Sdim /// before the specified basic block. 109249259Sdim static BasicBlock *Create(LLVMContext &Context, const Twine &Name = "", 110249259Sdim Function *Parent = 0,BasicBlock *InsertBefore = 0) { 111249259Sdim return new BasicBlock(Context, Name, Parent, InsertBefore); 112249259Sdim } 113249259Sdim ~BasicBlock(); 114249259Sdim 115249259Sdim /// \brief Return the enclosing method, or null if none. 116249259Sdim const Function *getParent() const { return Parent; } 117249259Sdim Function *getParent() { return Parent; } 118249259Sdim 119249259Sdim /// \brief Returns the terminator instruction if the block is well formed or 120249259Sdim /// null if the block is not well formed. 121249259Sdim TerminatorInst *getTerminator(); 122249259Sdim const TerminatorInst *getTerminator() const; 123249259Sdim 124249259Sdim /// \brief Returns a pointer to the first instruction in this block that is 125249259Sdim /// not a PHINode instruction. 126249259Sdim /// 127249259Sdim /// When adding instructions to the beginning of the basic block, they should 128249259Sdim /// be added before the returned value, not before the first instruction, 129249259Sdim /// which might be PHI. Returns 0 is there's no non-PHI instruction. 130249259Sdim Instruction* getFirstNonPHI(); 131249259Sdim const Instruction* getFirstNonPHI() const { 132249259Sdim return const_cast<BasicBlock*>(this)->getFirstNonPHI(); 133249259Sdim } 134249259Sdim 135249259Sdim /// \brief Returns a pointer to the first instruction in this block that is not 136249259Sdim /// a PHINode or a debug intrinsic. 137249259Sdim Instruction* getFirstNonPHIOrDbg(); 138249259Sdim const Instruction* getFirstNonPHIOrDbg() const { 139249259Sdim return const_cast<BasicBlock*>(this)->getFirstNonPHIOrDbg(); 140249259Sdim } 141249259Sdim 142249259Sdim /// \brief Returns a pointer to the first instruction in this block that is not 143249259Sdim /// a PHINode, a debug intrinsic, or a lifetime intrinsic. 144249259Sdim Instruction* getFirstNonPHIOrDbgOrLifetime(); 145249259Sdim const Instruction* getFirstNonPHIOrDbgOrLifetime() const { 146249259Sdim return const_cast<BasicBlock*>(this)->getFirstNonPHIOrDbgOrLifetime(); 147249259Sdim } 148249259Sdim 149249259Sdim /// \brief Returns an iterator to the first instruction in this block that is 150249259Sdim /// suitable for inserting a non-PHI instruction. 151249259Sdim /// 152249259Sdim /// In particular, it skips all PHIs and LandingPad instructions. 153249259Sdim iterator getFirstInsertionPt(); 154249259Sdim const_iterator getFirstInsertionPt() const { 155249259Sdim return const_cast<BasicBlock*>(this)->getFirstInsertionPt(); 156249259Sdim } 157249259Sdim 158249259Sdim /// \brief Unlink 'this' from the containing function, but do not delete it. 159249259Sdim void removeFromParent(); 160249259Sdim 161249259Sdim /// \brief Unlink 'this' from the containing function and delete it. 162249259Sdim void eraseFromParent(); 163249259Sdim 164249259Sdim /// \brief Unlink this basic block from its current function and insert it 165249259Sdim /// into the function that \p MovePos lives in, right before \p MovePos. 166249259Sdim void moveBefore(BasicBlock *MovePos); 167249259Sdim 168249259Sdim /// \brief Unlink this basic block from its current function and insert it 169249259Sdim /// right after \p MovePos in the function \p MovePos lives in. 170249259Sdim void moveAfter(BasicBlock *MovePos); 171249259Sdim 172249259Sdim 173249259Sdim /// \brief Return this block if it has a single predecessor block. Otherwise 174249259Sdim /// return a null pointer. 175249259Sdim BasicBlock *getSinglePredecessor(); 176249259Sdim const BasicBlock *getSinglePredecessor() const { 177249259Sdim return const_cast<BasicBlock*>(this)->getSinglePredecessor(); 178249259Sdim } 179249259Sdim 180249259Sdim /// \brief Return this block if it has a unique predecessor block. Otherwise return a null pointer. 181249259Sdim /// 182249259Sdim /// Note that unique predecessor doesn't mean single edge, there can be 183249259Sdim /// multiple edges from the unique predecessor to this block (for example a 184249259Sdim /// switch statement with multiple cases having the same destination). 185249259Sdim BasicBlock *getUniquePredecessor(); 186249259Sdim const BasicBlock *getUniquePredecessor() const { 187249259Sdim return const_cast<BasicBlock*>(this)->getUniquePredecessor(); 188249259Sdim } 189249259Sdim 190249259Sdim //===--------------------------------------------------------------------===// 191249259Sdim /// Instruction iterator methods 192249259Sdim /// 193249259Sdim inline iterator begin() { return InstList.begin(); } 194249259Sdim inline const_iterator begin() const { return InstList.begin(); } 195249259Sdim inline iterator end () { return InstList.end(); } 196249259Sdim inline const_iterator end () const { return InstList.end(); } 197249259Sdim 198249259Sdim inline reverse_iterator rbegin() { return InstList.rbegin(); } 199249259Sdim inline const_reverse_iterator rbegin() const { return InstList.rbegin(); } 200249259Sdim inline reverse_iterator rend () { return InstList.rend(); } 201249259Sdim inline const_reverse_iterator rend () const { return InstList.rend(); } 202249259Sdim 203249259Sdim inline size_t size() const { return InstList.size(); } 204249259Sdim inline bool empty() const { return InstList.empty(); } 205249259Sdim inline const Instruction &front() const { return InstList.front(); } 206249259Sdim inline Instruction &front() { return InstList.front(); } 207249259Sdim inline const Instruction &back() const { return InstList.back(); } 208249259Sdim inline Instruction &back() { return InstList.back(); } 209249259Sdim 210249259Sdim /// \brief Return the underlying instruction list container. 211249259Sdim /// 212249259Sdim /// Currently you need to access the underlying instruction list container 213249259Sdim /// directly if you want to modify it. 214249259Sdim const InstListType &getInstList() const { return InstList; } 215249259Sdim InstListType &getInstList() { return InstList; } 216249259Sdim 217249259Sdim /// \brief Returns a pointer to a member of the instruction list. 218249259Sdim static iplist<Instruction> BasicBlock::*getSublistAccess(Instruction*) { 219249259Sdim return &BasicBlock::InstList; 220249259Sdim } 221249259Sdim 222249259Sdim /// \brief Returns a pointer to the symbol table if one exists. 223249259Sdim ValueSymbolTable *getValueSymbolTable(); 224249259Sdim 225249259Sdim /// \brief Methods for support type inquiry through isa, cast, and dyn_cast. 226249259Sdim static inline bool classof(const Value *V) { 227249259Sdim return V->getValueID() == Value::BasicBlockVal; 228249259Sdim } 229249259Sdim 230249259Sdim /// \brief Cause all subinstructions to "let go" of all the references that 231249259Sdim /// said subinstructions are maintaining. 232249259Sdim /// 233249259Sdim /// This allows one to 'delete' a whole class at a time, even though there may 234249259Sdim /// be circular references... first all references are dropped, and all use 235249259Sdim /// counts go to zero. Then everything is delete'd for real. Note that no 236249259Sdim /// operations are valid on an object that has "dropped all references", 237249259Sdim /// except operator delete. 238249259Sdim void dropAllReferences(); 239249259Sdim 240249259Sdim /// \brief Notify the BasicBlock that the predecessor \p Pred is no longer 241249259Sdim /// able to reach it. 242249259Sdim /// 243249259Sdim /// This is actually not used to update the Predecessor list, but is actually 244249259Sdim /// used to update the PHI nodes that reside in the block. Note that this 245249259Sdim /// should be called while the predecessor still refers to this block. 246249259Sdim void removePredecessor(BasicBlock *Pred, bool DontDeleteUselessPHIs = false); 247249259Sdim 248249259Sdim /// \brief Split the basic block into two basic blocks at the specified 249249259Sdim /// instruction. 250249259Sdim /// 251249259Sdim /// Note that all instructions BEFORE the specified iterator stay as part of 252249259Sdim /// the original basic block, an unconditional branch is added to the original 253249259Sdim /// BB, and the rest of the instructions in the BB are moved to the new BB, 254249259Sdim /// including the old terminator. The newly formed BasicBlock is returned. 255249259Sdim /// This function invalidates the specified iterator. 256249259Sdim /// 257249259Sdim /// Note that this only works on well formed basic blocks (must have a 258249259Sdim /// terminator), and 'I' must not be the end of instruction list (which would 259249259Sdim /// cause a degenerate basic block to be formed, having a terminator inside of 260249259Sdim /// the basic block). 261249259Sdim /// 262249259Sdim /// Also note that this doesn't preserve any passes. To split blocks while 263249259Sdim /// keeping loop information consistent, use the SplitBlock utility function. 264249259Sdim BasicBlock *splitBasicBlock(iterator I, const Twine &BBName = ""); 265249259Sdim 266249259Sdim /// \brief Returns true if there are any uses of this basic block other than 267249259Sdim /// direct branches, switches, etc. to it. 268249259Sdim bool hasAddressTaken() const { return getSubclassDataFromValue() != 0; } 269249259Sdim 270249259Sdim /// \brief Update all phi nodes in this basic block's successors to refer to 271249259Sdim /// basic block \p New instead of to it. 272249259Sdim void replaceSuccessorsPhiUsesWith(BasicBlock *New); 273249259Sdim 274249259Sdim /// \brief Return true if this basic block is a landing pad. 275249259Sdim /// 276249259Sdim /// Being a ``landing pad'' means that the basic block is the destination of 277249259Sdim /// the 'unwind' edge of an invoke instruction. 278249259Sdim bool isLandingPad() const; 279249259Sdim 280249259Sdim /// \brief Return the landingpad instruction associated with the landing pad. 281249259Sdim LandingPadInst *getLandingPadInst(); 282249259Sdim const LandingPadInst *getLandingPadInst() const; 283249259Sdim 284249259Sdimprivate: 285249259Sdim /// \brief Increment the internal refcount of the number of BlockAddresses 286249259Sdim /// referencing this BasicBlock by \p Amt. 287249259Sdim /// 288249259Sdim /// This is almost always 0, sometimes one possibly, but almost never 2, and 289249259Sdim /// inconceivably 3 or more. 290249259Sdim void AdjustBlockAddressRefCount(int Amt) { 291249259Sdim setValueSubclassData(getSubclassDataFromValue()+Amt); 292249259Sdim assert((int)(signed char)getSubclassDataFromValue() >= 0 && 293249259Sdim "Refcount wrap-around"); 294249259Sdim } 295249259Sdim /// \brief Shadow Value::setValueSubclassData with a private forwarding method 296249259Sdim /// so that any future subclasses cannot accidentally use it. 297249259Sdim void setValueSubclassData(unsigned short D) { 298249259Sdim Value::setValueSubclassData(D); 299249259Sdim } 300249259Sdim}; 301249259Sdim 302251662Sdim// Create wrappers for C Binding types (see CBindingWrapping.h). 303251662SdimDEFINE_SIMPLE_CONVERSION_FUNCTIONS(BasicBlock, LLVMBasicBlockRef) 304251662Sdim 305249259Sdim} // End llvm namespace 306249259Sdim 307249259Sdim#endif 308