BasicBlock.cpp revision 2c3e0051c31c3f5b2328b447eadf1cf9c4427442
1//===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===// 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 implements the BasicBlock class for the IR library. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/IR/BasicBlock.h" 15#include "SymbolTableListTraitsImpl.h" 16#include "llvm/ADT/STLExtras.h" 17#include "llvm/IR/CFG.h" 18#include "llvm/IR/Constants.h" 19#include "llvm/IR/Instructions.h" 20#include "llvm/IR/IntrinsicInst.h" 21#include "llvm/IR/LLVMContext.h" 22#include "llvm/IR/Type.h" 23#include <algorithm> 24using namespace llvm; 25 26ValueSymbolTable *BasicBlock::getValueSymbolTable() { 27 if (Function *F = getParent()) 28 return &F->getValueSymbolTable(); 29 return nullptr; 30} 31 32LLVMContext &BasicBlock::getContext() const { 33 return getType()->getContext(); 34} 35 36// Explicit instantiation of SymbolTableListTraits since some of the methods 37// are not in the public header file... 38template class llvm::SymbolTableListTraits<Instruction, BasicBlock>; 39 40 41BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent, 42 BasicBlock *InsertBefore) 43 : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) { 44 45 if (NewParent) 46 insertInto(NewParent, InsertBefore); 47 else 48 assert(!InsertBefore && 49 "Cannot insert block before another block with no function!"); 50 51 setName(Name); 52} 53 54void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) { 55 assert(NewParent && "Expected a parent"); 56 assert(!Parent && "Already has a parent"); 57 58 if (InsertBefore) 59 NewParent->getBasicBlockList().insert(InsertBefore, this); 60 else 61 NewParent->getBasicBlockList().push_back(this); 62} 63 64BasicBlock::~BasicBlock() { 65 // If the address of the block is taken and it is being deleted (e.g. because 66 // it is dead), this means that there is either a dangling constant expr 67 // hanging off the block, or an undefined use of the block (source code 68 // expecting the address of a label to keep the block alive even though there 69 // is no indirect branch). Handle these cases by zapping the BlockAddress 70 // nodes. There are no other possible uses at this point. 71 if (hasAddressTaken()) { 72 assert(!use_empty() && "There should be at least one blockaddress!"); 73 Constant *Replacement = 74 ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1); 75 while (!use_empty()) { 76 BlockAddress *BA = cast<BlockAddress>(user_back()); 77 BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 78 BA->getType())); 79 BA->destroyConstant(); 80 } 81 } 82 83 assert(getParent() == nullptr && "BasicBlock still linked into the program!"); 84 dropAllReferences(); 85 InstList.clear(); 86} 87 88void BasicBlock::setParent(Function *parent) { 89 // Set Parent=parent, updating instruction symtab entries as appropriate. 90 InstList.setSymTabObject(&Parent, parent); 91} 92 93void BasicBlock::removeFromParent() { 94 getParent()->getBasicBlockList().remove(this); 95} 96 97iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() { 98 return getParent()->getBasicBlockList().erase(this); 99} 100 101/// Unlink this basic block from its current function and 102/// insert it into the function that MovePos lives in, right before MovePos. 103void BasicBlock::moveBefore(BasicBlock *MovePos) { 104 MovePos->getParent()->getBasicBlockList().splice(MovePos, 105 getParent()->getBasicBlockList(), this); 106} 107 108/// Unlink this basic block from its current function and 109/// insert it into the function that MovePos lives in, right after MovePos. 110void BasicBlock::moveAfter(BasicBlock *MovePos) { 111 Function::iterator I = MovePos; 112 MovePos->getParent()->getBasicBlockList().splice(++I, 113 getParent()->getBasicBlockList(), this); 114} 115 116const Module *BasicBlock::getModule() const { 117 return getParent()->getParent(); 118} 119 120TerminatorInst *BasicBlock::getTerminator() { 121 if (InstList.empty()) return nullptr; 122 return dyn_cast<TerminatorInst>(&InstList.back()); 123} 124 125const TerminatorInst *BasicBlock::getTerminator() const { 126 if (InstList.empty()) return nullptr; 127 return dyn_cast<TerminatorInst>(&InstList.back()); 128} 129 130CallInst *BasicBlock::getTerminatingMustTailCall() { 131 if (InstList.empty()) 132 return nullptr; 133 ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back()); 134 if (!RI || RI == &InstList.front()) 135 return nullptr; 136 137 Instruction *Prev = RI->getPrevNode(); 138 if (!Prev) 139 return nullptr; 140 141 if (Value *RV = RI->getReturnValue()) { 142 if (RV != Prev) 143 return nullptr; 144 145 // Look through the optional bitcast. 146 if (auto *BI = dyn_cast<BitCastInst>(Prev)) { 147 RV = BI->getOperand(0); 148 Prev = BI->getPrevNode(); 149 if (!Prev || RV != Prev) 150 return nullptr; 151 } 152 } 153 154 if (auto *CI = dyn_cast<CallInst>(Prev)) { 155 if (CI->isMustTailCall()) 156 return CI; 157 } 158 return nullptr; 159} 160 161Instruction* BasicBlock::getFirstNonPHI() { 162 BasicBlock::iterator i = begin(); 163 // All valid basic blocks should have a terminator, 164 // which is not a PHINode. If we have an invalid basic 165 // block we'll get an assertion failure when dereferencing 166 // a past-the-end iterator. 167 while (isa<PHINode>(i)) ++i; 168 return &*i; 169} 170 171Instruction* BasicBlock::getFirstNonPHIOrDbg() { 172 BasicBlock::iterator i = begin(); 173 // All valid basic blocks should have a terminator, 174 // which is not a PHINode. If we have an invalid basic 175 // block we'll get an assertion failure when dereferencing 176 // a past-the-end iterator. 177 while (isa<PHINode>(i) || isa<DbgInfoIntrinsic>(i)) ++i; 178 return &*i; 179} 180 181Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() { 182 // All valid basic blocks should have a terminator, 183 // which is not a PHINode. If we have an invalid basic 184 // block we'll get an assertion failure when dereferencing 185 // a past-the-end iterator. 186 BasicBlock::iterator i = begin(); 187 for (;; ++i) { 188 if (isa<PHINode>(i) || isa<DbgInfoIntrinsic>(i)) 189 continue; 190 191 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(i); 192 if (!II) 193 break; 194 if (II->getIntrinsicID() != Intrinsic::lifetime_start && 195 II->getIntrinsicID() != Intrinsic::lifetime_end) 196 break; 197 } 198 return &*i; 199} 200 201BasicBlock::iterator BasicBlock::getFirstInsertionPt() { 202 iterator InsertPt = getFirstNonPHI(); 203 if (isa<LandingPadInst>(InsertPt)) ++InsertPt; 204 return InsertPt; 205} 206 207void BasicBlock::dropAllReferences() { 208 for(iterator I = begin(), E = end(); I != E; ++I) 209 I->dropAllReferences(); 210} 211 212/// If this basic block has a single predecessor block, 213/// return the block, otherwise return a null pointer. 214BasicBlock *BasicBlock::getSinglePredecessor() { 215 pred_iterator PI = pred_begin(this), E = pred_end(this); 216 if (PI == E) return nullptr; // No preds. 217 BasicBlock *ThePred = *PI; 218 ++PI; 219 return (PI == E) ? ThePred : nullptr /*multiple preds*/; 220} 221 222/// If this basic block has a unique predecessor block, 223/// return the block, otherwise return a null pointer. 224/// Note that unique predecessor doesn't mean single edge, there can be 225/// multiple edges from the unique predecessor to this block (for example 226/// a switch statement with multiple cases having the same destination). 227BasicBlock *BasicBlock::getUniquePredecessor() { 228 pred_iterator PI = pred_begin(this), E = pred_end(this); 229 if (PI == E) return nullptr; // No preds. 230 BasicBlock *PredBB = *PI; 231 ++PI; 232 for (;PI != E; ++PI) { 233 if (*PI != PredBB) 234 return nullptr; 235 // The same predecessor appears multiple times in the predecessor list. 236 // This is OK. 237 } 238 return PredBB; 239} 240 241BasicBlock *BasicBlock::getUniqueSuccessor() { 242 succ_iterator SI = succ_begin(this), E = succ_end(this); 243 if (SI == E) return NULL; // No successors 244 BasicBlock *SuccBB = *SI; 245 ++SI; 246 for (;SI != E; ++SI) { 247 if (*SI != SuccBB) 248 return NULL; 249 // The same successor appears multiple times in the successor list. 250 // This is OK. 251 } 252 return SuccBB; 253} 254 255/// This method is used to notify a BasicBlock that the 256/// specified Predecessor of the block is no longer able to reach it. This is 257/// actually not used to update the Predecessor list, but is actually used to 258/// update the PHI nodes that reside in the block. Note that this should be 259/// called while the predecessor still refers to this block. 260/// 261void BasicBlock::removePredecessor(BasicBlock *Pred, 262 bool DontDeleteUselessPHIs) { 263 assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs. 264 find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) && 265 "removePredecessor: BB is not a predecessor!"); 266 267 if (InstList.empty()) return; 268 PHINode *APN = dyn_cast<PHINode>(&front()); 269 if (!APN) return; // Quick exit. 270 271 // If there are exactly two predecessors, then we want to nuke the PHI nodes 272 // altogether. However, we cannot do this, if this in this case: 273 // 274 // Loop: 275 // %x = phi [X, Loop] 276 // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1 277 // br Loop ;; %x2 does not dominate all uses 278 // 279 // This is because the PHI node input is actually taken from the predecessor 280 // basic block. The only case this can happen is with a self loop, so we 281 // check for this case explicitly now. 282 // 283 unsigned max_idx = APN->getNumIncomingValues(); 284 assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 285 if (max_idx == 2) { 286 BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred); 287 288 // Disable PHI elimination! 289 if (this == Other) max_idx = 3; 290 } 291 292 // <= Two predecessors BEFORE I remove one? 293 if (max_idx <= 2 && !DontDeleteUselessPHIs) { 294 // Yup, loop through and nuke the PHI nodes 295 while (PHINode *PN = dyn_cast<PHINode>(&front())) { 296 // Remove the predecessor first. 297 PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs); 298 299 // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 300 if (max_idx == 2) { 301 if (PN->getIncomingValue(0) != PN) 302 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 303 else 304 // We are left with an infinite loop with no entries: kill the PHI. 305 PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 306 getInstList().pop_front(); // Remove the PHI node 307 } 308 309 // If the PHI node already only had one entry, it got deleted by 310 // removeIncomingValue. 311 } 312 } else { 313 // Okay, now we know that we need to remove predecessor #pred_idx from all 314 // PHI nodes. Iterate over each PHI node fixing them up 315 PHINode *PN; 316 for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) { 317 ++II; 318 PN->removeIncomingValue(Pred, false); 319 // If all incoming values to the Phi are the same, we can replace the Phi 320 // with that value. 321 Value* PNV = nullptr; 322 if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue())) 323 if (PNV != PN) { 324 PN->replaceAllUsesWith(PNV); 325 PN->eraseFromParent(); 326 } 327 } 328 } 329} 330 331 332/// This splits a basic block into two at the specified 333/// instruction. Note that all instructions BEFORE the specified iterator stay 334/// as part of the original basic block, an unconditional branch is added to 335/// the new BB, and the rest of the instructions in the BB are moved to the new 336/// BB, including the old terminator. This invalidates the iterator. 337/// 338/// Note that this only works on well formed basic blocks (must have a 339/// terminator), and 'I' must not be the end of instruction list (which would 340/// cause a degenerate basic block to be formed, having a terminator inside of 341/// the basic block). 342/// 343BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) { 344 assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 345 assert(I != InstList.end() && 346 "Trying to get me to create degenerate basic block!"); 347 348 BasicBlock *InsertBefore = std::next(Function::iterator(this)) 349 .getNodePtrUnchecked(); 350 BasicBlock *New = BasicBlock::Create(getContext(), BBName, 351 getParent(), InsertBefore); 352 353 // Move all of the specified instructions from the original basic block into 354 // the new basic block. 355 New->getInstList().splice(New->end(), this->getInstList(), I, end()); 356 357 // Add a branch instruction to the newly formed basic block. 358 BranchInst::Create(New, this); 359 360 // Now we must loop through all of the successors of the New block (which 361 // _were_ the successors of the 'this' block), and update any PHI nodes in 362 // successors. If there were PHI nodes in the successors, then they need to 363 // know that incoming branches will be from New, not from Old. 364 // 365 for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) { 366 // Loop over any phi nodes in the basic block, updating the BB field of 367 // incoming values... 368 BasicBlock *Successor = *I; 369 PHINode *PN; 370 for (BasicBlock::iterator II = Successor->begin(); 371 (PN = dyn_cast<PHINode>(II)); ++II) { 372 int IDX = PN->getBasicBlockIndex(this); 373 while (IDX != -1) { 374 PN->setIncomingBlock((unsigned)IDX, New); 375 IDX = PN->getBasicBlockIndex(this); 376 } 377 } 378 } 379 return New; 380} 381 382void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) { 383 TerminatorInst *TI = getTerminator(); 384 if (!TI) 385 // Cope with being called on a BasicBlock that doesn't have a terminator 386 // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this. 387 return; 388 for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { 389 BasicBlock *Succ = TI->getSuccessor(i); 390 // N.B. Succ might not be a complete BasicBlock, so don't assume 391 // that it ends with a non-phi instruction. 392 for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) { 393 PHINode *PN = dyn_cast<PHINode>(II); 394 if (!PN) 395 break; 396 int i; 397 while ((i = PN->getBasicBlockIndex(this)) >= 0) 398 PN->setIncomingBlock(i, New); 399 } 400 } 401} 402 403/// Return true if this basic block is a landing pad. I.e., it's 404/// the destination of the 'unwind' edge of an invoke instruction. 405bool BasicBlock::isLandingPad() const { 406 return isa<LandingPadInst>(getFirstNonPHI()); 407} 408 409/// Return the landingpad instruction associated with the landing pad. 410LandingPadInst *BasicBlock::getLandingPadInst() { 411 return dyn_cast<LandingPadInst>(getFirstNonPHI()); 412} 413const LandingPadInst *BasicBlock::getLandingPadInst() const { 414 return dyn_cast<LandingPadInst>(getFirstNonPHI()); 415} 416