1249259Sdim//===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===// 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 implements the BasicBlock class for the IR library. 11249259Sdim// 12249259Sdim//===----------------------------------------------------------------------===// 13249259Sdim 14249259Sdim#include "llvm/IR/BasicBlock.h" 15249259Sdim#include "SymbolTableListTraitsImpl.h" 16249259Sdim#include "llvm/ADT/STLExtras.h" 17276479Sdim#include "llvm/IR/CFG.h" 18249259Sdim#include "llvm/IR/Constants.h" 19249259Sdim#include "llvm/IR/Instructions.h" 20249259Sdim#include "llvm/IR/IntrinsicInst.h" 21249259Sdim#include "llvm/IR/LLVMContext.h" 22249259Sdim#include "llvm/IR/Type.h" 23249259Sdim#include <algorithm> 24296417Sdim 25249259Sdimusing namespace llvm; 26249259Sdim 27249259SdimValueSymbolTable *BasicBlock::getValueSymbolTable() { 28249259Sdim if (Function *F = getParent()) 29249259Sdim return &F->getValueSymbolTable(); 30276479Sdim return nullptr; 31249259Sdim} 32249259Sdim 33249259SdimLLVMContext &BasicBlock::getContext() const { 34249259Sdim return getType()->getContext(); 35249259Sdim} 36249259Sdim 37249259Sdim// Explicit instantiation of SymbolTableListTraits since some of the methods 38249259Sdim// are not in the public header file... 39296417Sdimtemplate class llvm::SymbolTableListTraits<Instruction>; 40249259Sdim 41249259SdimBasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent, 42249259Sdim BasicBlock *InsertBefore) 43276479Sdim : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) { 44249259Sdim 45280031Sdim if (NewParent) 46280031Sdim insertInto(NewParent, InsertBefore); 47280031Sdim else 48280031Sdim assert(!InsertBefore && 49249259Sdim "Cannot insert block before another block with no function!"); 50249259Sdim 51249259Sdim setName(Name); 52249259Sdim} 53249259Sdim 54280031Sdimvoid BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) { 55280031Sdim assert(NewParent && "Expected a parent"); 56280031Sdim assert(!Parent && "Already has a parent"); 57249259Sdim 58280031Sdim if (InsertBefore) 59296417Sdim NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this); 60280031Sdim else 61280031Sdim NewParent->getBasicBlockList().push_back(this); 62280031Sdim} 63280031Sdim 64249259SdimBasicBlock::~BasicBlock() { 65249259Sdim // If the address of the block is taken and it is being deleted (e.g. because 66249259Sdim // it is dead), this means that there is either a dangling constant expr 67249259Sdim // hanging off the block, or an undefined use of the block (source code 68249259Sdim // expecting the address of a label to keep the block alive even though there 69249259Sdim // is no indirect branch). Handle these cases by zapping the BlockAddress 70249259Sdim // nodes. There are no other possible uses at this point. 71249259Sdim if (hasAddressTaken()) { 72249259Sdim assert(!use_empty() && "There should be at least one blockaddress!"); 73249259Sdim Constant *Replacement = 74249259Sdim ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1); 75249259Sdim while (!use_empty()) { 76276479Sdim BlockAddress *BA = cast<BlockAddress>(user_back()); 77249259Sdim BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 78249259Sdim BA->getType())); 79249259Sdim BA->destroyConstant(); 80249259Sdim } 81249259Sdim } 82249259Sdim 83276479Sdim assert(getParent() == nullptr && "BasicBlock still linked into the program!"); 84249259Sdim dropAllReferences(); 85249259Sdim InstList.clear(); 86249259Sdim} 87249259Sdim 88249259Sdimvoid BasicBlock::setParent(Function *parent) { 89249259Sdim // Set Parent=parent, updating instruction symtab entries as appropriate. 90249259Sdim InstList.setSymTabObject(&Parent, parent); 91249259Sdim} 92249259Sdim 93249259Sdimvoid BasicBlock::removeFromParent() { 94296417Sdim getParent()->getBasicBlockList().remove(getIterator()); 95249259Sdim} 96249259Sdim 97288943Sdimiplist<BasicBlock>::iterator BasicBlock::eraseFromParent() { 98296417Sdim return getParent()->getBasicBlockList().erase(getIterator()); 99249259Sdim} 100249259Sdim 101288943Sdim/// Unlink this basic block from its current function and 102249259Sdim/// insert it into the function that MovePos lives in, right before MovePos. 103249259Sdimvoid BasicBlock::moveBefore(BasicBlock *MovePos) { 104296417Sdim MovePos->getParent()->getBasicBlockList().splice( 105296417Sdim MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator()); 106249259Sdim} 107249259Sdim 108288943Sdim/// Unlink this basic block from its current function and 109249259Sdim/// insert it into the function that MovePos lives in, right after MovePos. 110249259Sdimvoid BasicBlock::moveAfter(BasicBlock *MovePos) { 111296417Sdim MovePos->getParent()->getBasicBlockList().splice( 112296417Sdim ++MovePos->getIterator(), getParent()->getBasicBlockList(), 113296417Sdim getIterator()); 114249259Sdim} 115249259Sdim 116288943Sdimconst Module *BasicBlock::getModule() const { 117288943Sdim return getParent()->getParent(); 118288943Sdim} 119249259Sdim 120288943SdimModule *BasicBlock::getModule() { 121288943Sdim return getParent()->getParent(); 122288943Sdim} 123288943Sdim 124249259SdimTerminatorInst *BasicBlock::getTerminator() { 125276479Sdim if (InstList.empty()) return nullptr; 126249259Sdim return dyn_cast<TerminatorInst>(&InstList.back()); 127249259Sdim} 128249259Sdim 129249259Sdimconst TerminatorInst *BasicBlock::getTerminator() const { 130276479Sdim if (InstList.empty()) return nullptr; 131249259Sdim return dyn_cast<TerminatorInst>(&InstList.back()); 132249259Sdim} 133249259Sdim 134280031SdimCallInst *BasicBlock::getTerminatingMustTailCall() { 135280031Sdim if (InstList.empty()) 136280031Sdim return nullptr; 137280031Sdim ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back()); 138280031Sdim if (!RI || RI == &InstList.front()) 139280031Sdim return nullptr; 140280031Sdim 141280031Sdim Instruction *Prev = RI->getPrevNode(); 142280031Sdim if (!Prev) 143280031Sdim return nullptr; 144280031Sdim 145280031Sdim if (Value *RV = RI->getReturnValue()) { 146280031Sdim if (RV != Prev) 147280031Sdim return nullptr; 148280031Sdim 149280031Sdim // Look through the optional bitcast. 150280031Sdim if (auto *BI = dyn_cast<BitCastInst>(Prev)) { 151280031Sdim RV = BI->getOperand(0); 152280031Sdim Prev = BI->getPrevNode(); 153280031Sdim if (!Prev || RV != Prev) 154280031Sdim return nullptr; 155280031Sdim } 156280031Sdim } 157280031Sdim 158280031Sdim if (auto *CI = dyn_cast<CallInst>(Prev)) { 159280031Sdim if (CI->isMustTailCall()) 160280031Sdim return CI; 161280031Sdim } 162280031Sdim return nullptr; 163280031Sdim} 164280031Sdim 165249259SdimInstruction* BasicBlock::getFirstNonPHI() { 166288943Sdim for (Instruction &I : *this) 167288943Sdim if (!isa<PHINode>(I)) 168288943Sdim return &I; 169288943Sdim return nullptr; 170249259Sdim} 171249259Sdim 172249259SdimInstruction* BasicBlock::getFirstNonPHIOrDbg() { 173288943Sdim for (Instruction &I : *this) 174288943Sdim if (!isa<PHINode>(I) && !isa<DbgInfoIntrinsic>(I)) 175288943Sdim return &I; 176288943Sdim return nullptr; 177249259Sdim} 178249259Sdim 179249259SdimInstruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() { 180288943Sdim for (Instruction &I : *this) { 181288943Sdim if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I)) 182249259Sdim continue; 183249259Sdim 184288943Sdim if (auto *II = dyn_cast<IntrinsicInst>(&I)) 185288943Sdim if (II->getIntrinsicID() == Intrinsic::lifetime_start || 186288943Sdim II->getIntrinsicID() == Intrinsic::lifetime_end) 187288943Sdim continue; 188288943Sdim 189288943Sdim return &I; 190249259Sdim } 191288943Sdim return nullptr; 192249259Sdim} 193249259Sdim 194249259SdimBasicBlock::iterator BasicBlock::getFirstInsertionPt() { 195288943Sdim Instruction *FirstNonPHI = getFirstNonPHI(); 196288943Sdim if (!FirstNonPHI) 197288943Sdim return end(); 198288943Sdim 199296417Sdim iterator InsertPt = FirstNonPHI->getIterator(); 200296417Sdim if (InsertPt->isEHPad()) ++InsertPt; 201249259Sdim return InsertPt; 202249259Sdim} 203249259Sdim 204249259Sdimvoid BasicBlock::dropAllReferences() { 205249259Sdim for(iterator I = begin(), E = end(); I != E; ++I) 206249259Sdim I->dropAllReferences(); 207249259Sdim} 208249259Sdim 209288943Sdim/// If this basic block has a single predecessor block, 210249259Sdim/// return the block, otherwise return a null pointer. 211249259SdimBasicBlock *BasicBlock::getSinglePredecessor() { 212249259Sdim pred_iterator PI = pred_begin(this), E = pred_end(this); 213276479Sdim if (PI == E) return nullptr; // No preds. 214249259Sdim BasicBlock *ThePred = *PI; 215249259Sdim ++PI; 216276479Sdim return (PI == E) ? ThePred : nullptr /*multiple preds*/; 217249259Sdim} 218249259Sdim 219288943Sdim/// If this basic block has a unique predecessor block, 220249259Sdim/// return the block, otherwise return a null pointer. 221249259Sdim/// Note that unique predecessor doesn't mean single edge, there can be 222249259Sdim/// multiple edges from the unique predecessor to this block (for example 223249259Sdim/// a switch statement with multiple cases having the same destination). 224249259SdimBasicBlock *BasicBlock::getUniquePredecessor() { 225249259Sdim pred_iterator PI = pred_begin(this), E = pred_end(this); 226276479Sdim if (PI == E) return nullptr; // No preds. 227249259Sdim BasicBlock *PredBB = *PI; 228249259Sdim ++PI; 229249259Sdim for (;PI != E; ++PI) { 230249259Sdim if (*PI != PredBB) 231276479Sdim return nullptr; 232249259Sdim // The same predecessor appears multiple times in the predecessor list. 233249259Sdim // This is OK. 234249259Sdim } 235249259Sdim return PredBB; 236249259Sdim} 237249259Sdim 238288943SdimBasicBlock *BasicBlock::getSingleSuccessor() { 239288943Sdim succ_iterator SI = succ_begin(this), E = succ_end(this); 240288943Sdim if (SI == E) return nullptr; // no successors 241288943Sdim BasicBlock *TheSucc = *SI; 242288943Sdim ++SI; 243288943Sdim return (SI == E) ? TheSucc : nullptr /* multiple successors */; 244288943Sdim} 245288943Sdim 246288943SdimBasicBlock *BasicBlock::getUniqueSuccessor() { 247288943Sdim succ_iterator SI = succ_begin(this), E = succ_end(this); 248296417Sdim if (SI == E) return nullptr; // No successors 249288943Sdim BasicBlock *SuccBB = *SI; 250288943Sdim ++SI; 251288943Sdim for (;SI != E; ++SI) { 252288943Sdim if (*SI != SuccBB) 253296417Sdim return nullptr; 254288943Sdim // The same successor appears multiple times in the successor list. 255288943Sdim // This is OK. 256288943Sdim } 257288943Sdim return SuccBB; 258288943Sdim} 259288943Sdim 260288943Sdim/// This method is used to notify a BasicBlock that the 261249259Sdim/// specified Predecessor of the block is no longer able to reach it. This is 262249259Sdim/// actually not used to update the Predecessor list, but is actually used to 263249259Sdim/// update the PHI nodes that reside in the block. Note that this should be 264249259Sdim/// called while the predecessor still refers to this block. 265249259Sdim/// 266249259Sdimvoid BasicBlock::removePredecessor(BasicBlock *Pred, 267249259Sdim bool DontDeleteUselessPHIs) { 268249259Sdim assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs. 269249259Sdim find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) && 270249259Sdim "removePredecessor: BB is not a predecessor!"); 271249259Sdim 272249259Sdim if (InstList.empty()) return; 273249259Sdim PHINode *APN = dyn_cast<PHINode>(&front()); 274249259Sdim if (!APN) return; // Quick exit. 275249259Sdim 276249259Sdim // If there are exactly two predecessors, then we want to nuke the PHI nodes 277249259Sdim // altogether. However, we cannot do this, if this in this case: 278249259Sdim // 279249259Sdim // Loop: 280249259Sdim // %x = phi [X, Loop] 281249259Sdim // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1 282249259Sdim // br Loop ;; %x2 does not dominate all uses 283249259Sdim // 284249259Sdim // This is because the PHI node input is actually taken from the predecessor 285249259Sdim // basic block. The only case this can happen is with a self loop, so we 286249259Sdim // check for this case explicitly now. 287249259Sdim // 288249259Sdim unsigned max_idx = APN->getNumIncomingValues(); 289249259Sdim assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 290249259Sdim if (max_idx == 2) { 291249259Sdim BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred); 292249259Sdim 293249259Sdim // Disable PHI elimination! 294249259Sdim if (this == Other) max_idx = 3; 295249259Sdim } 296249259Sdim 297249259Sdim // <= Two predecessors BEFORE I remove one? 298249259Sdim if (max_idx <= 2 && !DontDeleteUselessPHIs) { 299249259Sdim // Yup, loop through and nuke the PHI nodes 300249259Sdim while (PHINode *PN = dyn_cast<PHINode>(&front())) { 301249259Sdim // Remove the predecessor first. 302249259Sdim PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs); 303249259Sdim 304249259Sdim // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 305249259Sdim if (max_idx == 2) { 306249259Sdim if (PN->getIncomingValue(0) != PN) 307249259Sdim PN->replaceAllUsesWith(PN->getIncomingValue(0)); 308249259Sdim else 309249259Sdim // We are left with an infinite loop with no entries: kill the PHI. 310249259Sdim PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 311249259Sdim getInstList().pop_front(); // Remove the PHI node 312249259Sdim } 313249259Sdim 314249259Sdim // If the PHI node already only had one entry, it got deleted by 315249259Sdim // removeIncomingValue. 316249259Sdim } 317249259Sdim } else { 318249259Sdim // Okay, now we know that we need to remove predecessor #pred_idx from all 319249259Sdim // PHI nodes. Iterate over each PHI node fixing them up 320249259Sdim PHINode *PN; 321249259Sdim for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) { 322249259Sdim ++II; 323249259Sdim PN->removeIncomingValue(Pred, false); 324249259Sdim // If all incoming values to the Phi are the same, we can replace the Phi 325249259Sdim // with that value. 326276479Sdim Value* PNV = nullptr; 327249259Sdim if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue())) 328249259Sdim if (PNV != PN) { 329249259Sdim PN->replaceAllUsesWith(PNV); 330249259Sdim PN->eraseFromParent(); 331249259Sdim } 332249259Sdim } 333249259Sdim } 334249259Sdim} 335249259Sdim 336296417Sdimbool BasicBlock::canSplitPredecessors() const { 337296417Sdim const Instruction *FirstNonPHI = getFirstNonPHI(); 338296417Sdim if (isa<LandingPadInst>(FirstNonPHI)) 339296417Sdim return true; 340296417Sdim // This is perhaps a little conservative because constructs like 341296417Sdim // CleanupBlockInst are pretty easy to split. However, SplitBlockPredecessors 342296417Sdim // cannot handle such things just yet. 343296417Sdim if (FirstNonPHI->isEHPad()) 344296417Sdim return false; 345296417Sdim return true; 346296417Sdim} 347249259Sdim 348288943Sdim/// This splits a basic block into two at the specified 349249259Sdim/// instruction. Note that all instructions BEFORE the specified iterator stay 350249259Sdim/// as part of the original basic block, an unconditional branch is added to 351249259Sdim/// the new BB, and the rest of the instructions in the BB are moved to the new 352249259Sdim/// BB, including the old terminator. This invalidates the iterator. 353249259Sdim/// 354249259Sdim/// Note that this only works on well formed basic blocks (must have a 355249259Sdim/// terminator), and 'I' must not be the end of instruction list (which would 356249259Sdim/// cause a degenerate basic block to be formed, having a terminator inside of 357249259Sdim/// the basic block). 358249259Sdim/// 359249259SdimBasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) { 360249259Sdim assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 361249259Sdim assert(I != InstList.end() && 362249259Sdim "Trying to get me to create degenerate basic block!"); 363249259Sdim 364276479Sdim BasicBlock *InsertBefore = std::next(Function::iterator(this)) 365249259Sdim .getNodePtrUnchecked(); 366249259Sdim BasicBlock *New = BasicBlock::Create(getContext(), BBName, 367249259Sdim getParent(), InsertBefore); 368249259Sdim 369288943Sdim // Save DebugLoc of split point before invalidating iterator. 370288943Sdim DebugLoc Loc = I->getDebugLoc(); 371249259Sdim // Move all of the specified instructions from the original basic block into 372249259Sdim // the new basic block. 373249259Sdim New->getInstList().splice(New->end(), this->getInstList(), I, end()); 374249259Sdim 375249259Sdim // Add a branch instruction to the newly formed basic block. 376288943Sdim BranchInst *BI = BranchInst::Create(New, this); 377288943Sdim BI->setDebugLoc(Loc); 378249259Sdim 379249259Sdim // Now we must loop through all of the successors of the New block (which 380249259Sdim // _were_ the successors of the 'this' block), and update any PHI nodes in 381249259Sdim // successors. If there were PHI nodes in the successors, then they need to 382249259Sdim // know that incoming branches will be from New, not from Old. 383249259Sdim // 384249259Sdim for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) { 385249259Sdim // Loop over any phi nodes in the basic block, updating the BB field of 386249259Sdim // incoming values... 387249259Sdim BasicBlock *Successor = *I; 388249259Sdim PHINode *PN; 389249259Sdim for (BasicBlock::iterator II = Successor->begin(); 390249259Sdim (PN = dyn_cast<PHINode>(II)); ++II) { 391249259Sdim int IDX = PN->getBasicBlockIndex(this); 392249259Sdim while (IDX != -1) { 393249259Sdim PN->setIncomingBlock((unsigned)IDX, New); 394249259Sdim IDX = PN->getBasicBlockIndex(this); 395249259Sdim } 396249259Sdim } 397249259Sdim } 398249259Sdim return New; 399249259Sdim} 400249259Sdim 401249259Sdimvoid BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) { 402249259Sdim TerminatorInst *TI = getTerminator(); 403249259Sdim if (!TI) 404249259Sdim // Cope with being called on a BasicBlock that doesn't have a terminator 405249259Sdim // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this. 406249259Sdim return; 407296417Sdim for (BasicBlock *Succ : TI->successors()) { 408249259Sdim // N.B. Succ might not be a complete BasicBlock, so don't assume 409249259Sdim // that it ends with a non-phi instruction. 410249259Sdim for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) { 411249259Sdim PHINode *PN = dyn_cast<PHINode>(II); 412249259Sdim if (!PN) 413249259Sdim break; 414249259Sdim int i; 415249259Sdim while ((i = PN->getBasicBlockIndex(this)) >= 0) 416249259Sdim PN->setIncomingBlock(i, New); 417249259Sdim } 418249259Sdim } 419249259Sdim} 420249259Sdim 421288943Sdim/// Return true if this basic block is a landing pad. I.e., it's 422249259Sdim/// the destination of the 'unwind' edge of an invoke instruction. 423249259Sdimbool BasicBlock::isLandingPad() const { 424249259Sdim return isa<LandingPadInst>(getFirstNonPHI()); 425249259Sdim} 426249259Sdim 427288943Sdim/// Return the landingpad instruction associated with the landing pad. 428249259SdimLandingPadInst *BasicBlock::getLandingPadInst() { 429249259Sdim return dyn_cast<LandingPadInst>(getFirstNonPHI()); 430249259Sdim} 431249259Sdimconst LandingPadInst *BasicBlock::getLandingPadInst() const { 432249259Sdim return dyn_cast<LandingPadInst>(getFirstNonPHI()); 433249259Sdim} 434