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> 24 25 using namespace llvm; 26 27 ValueSymbolTable *BasicBlock::getValueSymbolTable() { 28 if (Function *F = getParent()) 29 return &F->getValueSymbolTable(); 30 return nullptr; 31 } 32 33 LLVMContext &BasicBlock::getContext() const { 34 return getType()->getContext(); 35 } 36 37 // Explicit instantiation of SymbolTableListTraits since some of the methods 38 // are not in the public header file... 39 template class llvm::SymbolTableListTraits<Instruction>; 40 41 BasicBlock::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 54 void 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->getIterator(), this); 60 else 61 NewParent->getBasicBlockList().push_back(this); 62 } 63 64 BasicBlock::~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 88 void BasicBlock::setParent(Function *parent) { 89 // Set Parent=parent, updating instruction symtab entries as appropriate. 90 InstList.setSymTabObject(&Parent, parent); 91 } 92 93 void BasicBlock::removeFromParent() { 94 getParent()->getBasicBlockList().remove(getIterator()); 95 } 96 97 iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() { 98 return getParent()->getBasicBlockList().erase(getIterator()); 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. 103 void BasicBlock::moveBefore(BasicBlock *MovePos) { 104 MovePos->getParent()->getBasicBlockList().splice( 105 MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator()); 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. 110 void BasicBlock::moveAfter(BasicBlock *MovePos) { 111 MovePos->getParent()->getBasicBlockList().splice( 112 ++MovePos->getIterator(), getParent()->getBasicBlockList(), 113 getIterator()); 114 } 115 116 const Module *BasicBlock::getModule() const { 117 return getParent()->getParent(); 118 } 119 120 Module *BasicBlock::getModule() { 121 return getParent()->getParent(); 122 } 123 124 TerminatorInst *BasicBlock::getTerminator() { 125 if (InstList.empty()) return nullptr; 126 return dyn_cast<TerminatorInst>(&InstList.back()); 127 } 128 129 const TerminatorInst *BasicBlock::getTerminator() const { 130 if (InstList.empty()) return nullptr; 131 return dyn_cast<TerminatorInst>(&InstList.back()); 132 } 133 134 CallInst *BasicBlock::getTerminatingMustTailCall() { 135 if (InstList.empty()) 136 return nullptr; 137 ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back()); 138 if (!RI || RI == &InstList.front()) 139 return nullptr; 140 141 Instruction *Prev = RI->getPrevNode(); 142 if (!Prev) 143 return nullptr; 144 145 if (Value *RV = RI->getReturnValue()) { 146 if (RV != Prev) 147 return nullptr; 148 149 // Look through the optional bitcast. 150 if (auto *BI = dyn_cast<BitCastInst>(Prev)) { 151 RV = BI->getOperand(0); 152 Prev = BI->getPrevNode(); 153 if (!Prev || RV != Prev) 154 return nullptr; 155 } 156 } 157 158 if (auto *CI = dyn_cast<CallInst>(Prev)) { 159 if (CI->isMustTailCall()) 160 return CI; 161 } 162 return nullptr; 163 } 164 165 CallInst *BasicBlock::getTerminatingDeoptimizeCall() { 166 if (InstList.empty()) 167 return nullptr; 168 auto *RI = dyn_cast<ReturnInst>(&InstList.back()); 169 if (!RI || RI == &InstList.front()) 170 return nullptr; 171 172 if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode())) 173 if (Function *F = CI->getCalledFunction()) 174 if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize) 175 return CI; 176 177 return nullptr; 178 } 179 180 Instruction* BasicBlock::getFirstNonPHI() { 181 for (Instruction &I : *this) 182 if (!isa<PHINode>(I)) 183 return &I; 184 return nullptr; 185 } 186 187 Instruction* BasicBlock::getFirstNonPHIOrDbg() { 188 for (Instruction &I : *this) 189 if (!isa<PHINode>(I) && !isa<DbgInfoIntrinsic>(I)) 190 return &I; 191 return nullptr; 192 } 193 194 Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() { 195 for (Instruction &I : *this) { 196 if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I)) 197 continue; 198 199 if (auto *II = dyn_cast<IntrinsicInst>(&I)) 200 if (II->getIntrinsicID() == Intrinsic::lifetime_start || 201 II->getIntrinsicID() == Intrinsic::lifetime_end) 202 continue; 203 204 return &I; 205 } 206 return nullptr; 207 } 208 209 BasicBlock::iterator BasicBlock::getFirstInsertionPt() { 210 Instruction *FirstNonPHI = getFirstNonPHI(); 211 if (!FirstNonPHI) 212 return end(); 213 214 iterator InsertPt = FirstNonPHI->getIterator(); 215 if (InsertPt->isEHPad()) ++InsertPt; 216 return InsertPt; 217 } 218 219 void BasicBlock::dropAllReferences() { 220 for (Instruction &I : *this) 221 I.dropAllReferences(); 222 } 223 224 /// If this basic block has a single predecessor block, 225 /// return the block, otherwise return a null pointer. 226 BasicBlock *BasicBlock::getSinglePredecessor() { 227 pred_iterator PI = pred_begin(this), E = pred_end(this); 228 if (PI == E) return nullptr; // No preds. 229 BasicBlock *ThePred = *PI; 230 ++PI; 231 return (PI == E) ? ThePred : nullptr /*multiple preds*/; 232 } 233 234 /// If this basic block has a unique predecessor block, 235 /// return the block, otherwise return a null pointer. 236 /// Note that unique predecessor doesn't mean single edge, there can be 237 /// multiple edges from the unique predecessor to this block (for example 238 /// a switch statement with multiple cases having the same destination). 239 BasicBlock *BasicBlock::getUniquePredecessor() { 240 pred_iterator PI = pred_begin(this), E = pred_end(this); 241 if (PI == E) return nullptr; // No preds. 242 BasicBlock *PredBB = *PI; 243 ++PI; 244 for (;PI != E; ++PI) { 245 if (*PI != PredBB) 246 return nullptr; 247 // The same predecessor appears multiple times in the predecessor list. 248 // This is OK. 249 } 250 return PredBB; 251 } 252 253 BasicBlock *BasicBlock::getSingleSuccessor() { 254 succ_iterator SI = succ_begin(this), E = succ_end(this); 255 if (SI == E) return nullptr; // no successors 256 BasicBlock *TheSucc = *SI; 257 ++SI; 258 return (SI == E) ? TheSucc : nullptr /* multiple successors */; 259 } 260 261 BasicBlock *BasicBlock::getUniqueSuccessor() { 262 succ_iterator SI = succ_begin(this), E = succ_end(this); 263 if (SI == E) return nullptr; // No successors 264 BasicBlock *SuccBB = *SI; 265 ++SI; 266 for (;SI != E; ++SI) { 267 if (*SI != SuccBB) 268 return nullptr; 269 // The same successor appears multiple times in the successor list. 270 // This is OK. 271 } 272 return SuccBB; 273 } 274 275 /// This method is used to notify a BasicBlock that the 276 /// specified Predecessor of the block is no longer able to reach it. This is 277 /// actually not used to update the Predecessor list, but is actually used to 278 /// update the PHI nodes that reside in the block. Note that this should be 279 /// called while the predecessor still refers to this block. 280 /// 281 void BasicBlock::removePredecessor(BasicBlock *Pred, 282 bool DontDeleteUselessPHIs) { 283 assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs. 284 find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) && 285 "removePredecessor: BB is not a predecessor!"); 286 287 if (InstList.empty()) return; 288 PHINode *APN = dyn_cast<PHINode>(&front()); 289 if (!APN) return; // Quick exit. 290 291 // If there are exactly two predecessors, then we want to nuke the PHI nodes 292 // altogether. However, we cannot do this, if this in this case: 293 // 294 // Loop: 295 // %x = phi [X, Loop] 296 // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1 297 // br Loop ;; %x2 does not dominate all uses 298 // 299 // This is because the PHI node input is actually taken from the predecessor 300 // basic block. The only case this can happen is with a self loop, so we 301 // check for this case explicitly now. 302 // 303 unsigned max_idx = APN->getNumIncomingValues(); 304 assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 305 if (max_idx == 2) { 306 BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred); 307 308 // Disable PHI elimination! 309 if (this == Other) max_idx = 3; 310 } 311 312 // <= Two predecessors BEFORE I remove one? 313 if (max_idx <= 2 && !DontDeleteUselessPHIs) { 314 // Yup, loop through and nuke the PHI nodes 315 while (PHINode *PN = dyn_cast<PHINode>(&front())) { 316 // Remove the predecessor first. 317 PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs); 318 319 // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 320 if (max_idx == 2) { 321 if (PN->getIncomingValue(0) != PN) 322 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 323 else 324 // We are left with an infinite loop with no entries: kill the PHI. 325 PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 326 getInstList().pop_front(); // Remove the PHI node 327 } 328 329 // If the PHI node already only had one entry, it got deleted by 330 // removeIncomingValue. 331 } 332 } else { 333 // Okay, now we know that we need to remove predecessor #pred_idx from all 334 // PHI nodes. Iterate over each PHI node fixing them up 335 PHINode *PN; 336 for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) { 337 ++II; 338 PN->removeIncomingValue(Pred, false); 339 // If all incoming values to the Phi are the same, we can replace the Phi 340 // with that value. 341 Value* PNV = nullptr; 342 if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue())) 343 if (PNV != PN) { 344 PN->replaceAllUsesWith(PNV); 345 PN->eraseFromParent(); 346 } 347 } 348 } 349 } 350 351 bool BasicBlock::canSplitPredecessors() const { 352 const Instruction *FirstNonPHI = getFirstNonPHI(); 353 if (isa<LandingPadInst>(FirstNonPHI)) 354 return true; 355 // This is perhaps a little conservative because constructs like 356 // CleanupBlockInst are pretty easy to split. However, SplitBlockPredecessors 357 // cannot handle such things just yet. 358 if (FirstNonPHI->isEHPad()) 359 return false; 360 return true; 361 } 362 363 /// This splits a basic block into two at the specified 364 /// instruction. Note that all instructions BEFORE the specified iterator stay 365 /// as part of the original basic block, an unconditional branch is added to 366 /// the new BB, and the rest of the instructions in the BB are moved to the new 367 /// BB, including the old terminator. This invalidates the iterator. 368 /// 369 /// Note that this only works on well formed basic blocks (must have a 370 /// terminator), and 'I' must not be the end of instruction list (which would 371 /// cause a degenerate basic block to be formed, having a terminator inside of 372 /// the basic block). 373 /// 374 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) { 375 assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 376 assert(I != InstList.end() && 377 "Trying to get me to create degenerate basic block!"); 378 379 BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(), 380 this->getNextNode()); 381 382 // Save DebugLoc of split point before invalidating iterator. 383 DebugLoc Loc = I->getDebugLoc(); 384 // Move all of the specified instructions from the original basic block into 385 // the new basic block. 386 New->getInstList().splice(New->end(), this->getInstList(), I, end()); 387 388 // Add a branch instruction to the newly formed basic block. 389 BranchInst *BI = BranchInst::Create(New, this); 390 BI->setDebugLoc(Loc); 391 392 // Now we must loop through all of the successors of the New block (which 393 // _were_ the successors of the 'this' block), and update any PHI nodes in 394 // successors. If there were PHI nodes in the successors, then they need to 395 // know that incoming branches will be from New, not from Old. 396 // 397 for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) { 398 // Loop over any phi nodes in the basic block, updating the BB field of 399 // incoming values... 400 BasicBlock *Successor = *I; 401 PHINode *PN; 402 for (BasicBlock::iterator II = Successor->begin(); 403 (PN = dyn_cast<PHINode>(II)); ++II) { 404 int IDX = PN->getBasicBlockIndex(this); 405 while (IDX != -1) { 406 PN->setIncomingBlock((unsigned)IDX, New); 407 IDX = PN->getBasicBlockIndex(this); 408 } 409 } 410 } 411 return New; 412 } 413 414 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) { 415 TerminatorInst *TI = getTerminator(); 416 if (!TI) 417 // Cope with being called on a BasicBlock that doesn't have a terminator 418 // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this. 419 return; 420 for (BasicBlock *Succ : TI->successors()) { 421 // N.B. Succ might not be a complete BasicBlock, so don't assume 422 // that it ends with a non-phi instruction. 423 for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) { 424 PHINode *PN = dyn_cast<PHINode>(II); 425 if (!PN) 426 break; 427 int i; 428 while ((i = PN->getBasicBlockIndex(this)) >= 0) 429 PN->setIncomingBlock(i, New); 430 } 431 } 432 } 433 434 /// Return true if this basic block is a landing pad. I.e., it's 435 /// the destination of the 'unwind' edge of an invoke instruction. 436 bool BasicBlock::isLandingPad() const { 437 return isa<LandingPadInst>(getFirstNonPHI()); 438 } 439 440 /// Return the landingpad instruction associated with the landing pad. 441 LandingPadInst *BasicBlock::getLandingPadInst() { 442 return dyn_cast<LandingPadInst>(getFirstNonPHI()); 443 } 444 const LandingPadInst *BasicBlock::getLandingPadInst() const { 445 return dyn_cast<LandingPadInst>(getFirstNonPHI()); 446 } 447