1 //===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the BasicBlock class for the IR library. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/IR/BasicBlock.h" 14 #include "SymbolTableListTraitsImpl.h" 15 #include "llvm/ADT/STLExtras.h" 16 #include "llvm/ADT/Statistic.h" 17 #include "llvm/IR/CFG.h" 18 #include "llvm/IR/Constants.h" 19 #include "llvm/IR/DebugProgramInstruction.h" 20 #include "llvm/IR/Instructions.h" 21 #include "llvm/IR/IntrinsicInst.h" 22 #include "llvm/IR/LLVMContext.h" 23 #include "llvm/IR/Type.h" 24 #include "llvm/Support/CommandLine.h" 25 26 #include "LLVMContextImpl.h" 27 28 using namespace llvm; 29 30 #define DEBUG_TYPE "ir" 31 STATISTIC(NumInstrRenumberings, "Number of renumberings across all blocks"); 32 33 cl::opt<bool> UseNewDbgInfoFormat( 34 "experimental-debuginfo-iterators", 35 cl::desc("Enable communicating debuginfo positions through iterators, " 36 "eliminating intrinsics. Has no effect if " 37 "--preserve-input-debuginfo-format=true."), 38 cl::init(true)); 39 cl::opt<cl::boolOrDefault> PreserveInputDbgFormat( 40 "preserve-input-debuginfo-format", cl::Hidden, 41 cl::desc("When set to true, IR files will be processed and printed in " 42 "their current debug info format, regardless of default behaviour " 43 "or other flags passed. Has no effect if input IR does not " 44 "contain debug records or intrinsics. Ignored in llvm-link, " 45 "llvm-lto, and llvm-lto2.")); 46 47 bool WriteNewDbgInfoFormatToBitcode /*set default value in cl::init() below*/; 48 cl::opt<bool, true> WriteNewDbgInfoFormatToBitcode2( 49 "write-experimental-debuginfo-iterators-to-bitcode", cl::Hidden, 50 cl::location(WriteNewDbgInfoFormatToBitcode), cl::init(true)); 51 52 DbgMarker *BasicBlock::createMarker(Instruction *I) { 53 assert(IsNewDbgInfoFormat && 54 "Tried to create a marker in a non new debug-info block!"); 55 if (I->DebugMarker) 56 return I->DebugMarker; 57 DbgMarker *Marker = new DbgMarker(); 58 Marker->MarkedInstr = I; 59 I->DebugMarker = Marker; 60 return Marker; 61 } 62 63 DbgMarker *BasicBlock::createMarker(InstListType::iterator It) { 64 assert(IsNewDbgInfoFormat && 65 "Tried to create a marker in a non new debug-info block!"); 66 if (It != end()) 67 return createMarker(&*It); 68 DbgMarker *DM = getTrailingDbgRecords(); 69 if (DM) 70 return DM; 71 DM = new DbgMarker(); 72 setTrailingDbgRecords(DM); 73 return DM; 74 } 75 76 void BasicBlock::convertToNewDbgValues() { 77 IsNewDbgInfoFormat = true; 78 79 // Iterate over all instructions in the instruction list, collecting debug 80 // info intrinsics and converting them to DbgRecords. Once we find a "real" 81 // instruction, attach all those DbgRecords to a DbgMarker in that 82 // instruction. 83 SmallVector<DbgRecord *, 4> DbgVarRecs; 84 for (Instruction &I : make_early_inc_range(InstList)) { 85 assert(!I.DebugMarker && "DebugMarker already set on old-format instrs?"); 86 if (DbgVariableIntrinsic *DVI = dyn_cast<DbgVariableIntrinsic>(&I)) { 87 // Convert this dbg.value to a DbgVariableRecord. 88 DbgVariableRecord *Value = new DbgVariableRecord(DVI); 89 DbgVarRecs.push_back(Value); 90 DVI->eraseFromParent(); 91 continue; 92 } 93 94 if (DbgLabelInst *DLI = dyn_cast<DbgLabelInst>(&I)) { 95 DbgVarRecs.push_back( 96 new DbgLabelRecord(DLI->getLabel(), DLI->getDebugLoc())); 97 DLI->eraseFromParent(); 98 continue; 99 } 100 101 if (DbgVarRecs.empty()) 102 continue; 103 104 // Create a marker to store DbgRecords in. 105 createMarker(&I); 106 DbgMarker *Marker = I.DebugMarker; 107 108 for (DbgRecord *DVR : DbgVarRecs) 109 Marker->insertDbgRecord(DVR, false); 110 111 DbgVarRecs.clear(); 112 } 113 } 114 115 void BasicBlock::convertFromNewDbgValues() { 116 invalidateOrders(); 117 IsNewDbgInfoFormat = false; 118 119 // Iterate over the block, finding instructions annotated with DbgMarkers. 120 // Convert any attached DbgRecords to debug intrinsics and insert ahead of the 121 // instruction. 122 for (auto &Inst : *this) { 123 if (!Inst.DebugMarker) 124 continue; 125 126 DbgMarker &Marker = *Inst.DebugMarker; 127 for (DbgRecord &DR : Marker.getDbgRecordRange()) 128 InstList.insert(Inst.getIterator(), 129 DR.createDebugIntrinsic(getModule(), nullptr)); 130 131 Marker.eraseFromParent(); 132 } 133 134 // Assume no trailing DbgRecords: we could technically create them at the end 135 // of the block, after a terminator, but this would be non-cannonical and 136 // indicates that something else is broken somewhere. 137 assert(!getTrailingDbgRecords()); 138 } 139 140 #ifndef NDEBUG 141 void BasicBlock::dumpDbgValues() const { 142 for (auto &Inst : *this) { 143 if (!Inst.DebugMarker) 144 continue; 145 146 dbgs() << "@ " << Inst.DebugMarker << " "; 147 Inst.DebugMarker->dump(); 148 }; 149 } 150 #endif 151 152 void BasicBlock::setIsNewDbgInfoFormat(bool NewFlag) { 153 if (NewFlag && !IsNewDbgInfoFormat) 154 convertToNewDbgValues(); 155 else if (!NewFlag && IsNewDbgInfoFormat) 156 convertFromNewDbgValues(); 157 } 158 void BasicBlock::setNewDbgInfoFormatFlag(bool NewFlag) { 159 IsNewDbgInfoFormat = NewFlag; 160 } 161 162 ValueSymbolTable *BasicBlock::getValueSymbolTable() { 163 if (Function *F = getParent()) 164 return F->getValueSymbolTable(); 165 return nullptr; 166 } 167 168 LLVMContext &BasicBlock::getContext() const { 169 return getType()->getContext(); 170 } 171 172 template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) { 173 BB->invalidateOrders(); 174 } 175 176 // Explicit instantiation of SymbolTableListTraits since some of the methods 177 // are not in the public header file... 178 template class llvm::SymbolTableListTraits< 179 Instruction, ilist_iterator_bits<true>, ilist_parent<BasicBlock>>; 180 181 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent, 182 BasicBlock *InsertBefore) 183 : Value(Type::getLabelTy(C), Value::BasicBlockVal), 184 IsNewDbgInfoFormat(UseNewDbgInfoFormat), Parent(nullptr) { 185 186 if (NewParent) 187 insertInto(NewParent, InsertBefore); 188 else 189 assert(!InsertBefore && 190 "Cannot insert block before another block with no function!"); 191 192 end().getNodePtr()->setParent(this); 193 setName(Name); 194 if (NewParent) 195 setIsNewDbgInfoFormat(NewParent->IsNewDbgInfoFormat); 196 } 197 198 void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) { 199 assert(NewParent && "Expected a parent"); 200 assert(!Parent && "Already has a parent"); 201 202 if (InsertBefore) 203 NewParent->insert(InsertBefore->getIterator(), this); 204 else 205 NewParent->insert(NewParent->end(), this); 206 207 setIsNewDbgInfoFormat(NewParent->IsNewDbgInfoFormat); 208 } 209 210 BasicBlock::~BasicBlock() { 211 validateInstrOrdering(); 212 213 // If the address of the block is taken and it is being deleted (e.g. because 214 // it is dead), this means that there is either a dangling constant expr 215 // hanging off the block, or an undefined use of the block (source code 216 // expecting the address of a label to keep the block alive even though there 217 // is no indirect branch). Handle these cases by zapping the BlockAddress 218 // nodes. There are no other possible uses at this point. 219 if (hasAddressTaken()) { 220 assert(!use_empty() && "There should be at least one blockaddress!"); 221 Constant *Replacement = 222 ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1); 223 while (!use_empty()) { 224 BlockAddress *BA = cast<BlockAddress>(user_back()); 225 BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement, 226 BA->getType())); 227 BA->destroyConstant(); 228 } 229 } 230 231 assert(getParent() == nullptr && "BasicBlock still linked into the program!"); 232 dropAllReferences(); 233 for (auto &Inst : *this) { 234 if (!Inst.DebugMarker) 235 continue; 236 Inst.DebugMarker->eraseFromParent(); 237 } 238 InstList.clear(); 239 } 240 241 void BasicBlock::setParent(Function *parent) { 242 // Set Parent=parent, updating instruction symtab entries as appropriate. 243 InstList.setSymTabObject(&Parent, parent); 244 } 245 246 iterator_range<filter_iterator<BasicBlock::const_iterator, 247 std::function<bool(const Instruction &)>>> 248 BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) const { 249 std::function<bool(const Instruction &)> Fn = [=](const Instruction &I) { 250 return !isa<DbgInfoIntrinsic>(I) && 251 !(SkipPseudoOp && isa<PseudoProbeInst>(I)); 252 }; 253 return make_filter_range(*this, Fn); 254 } 255 256 iterator_range< 257 filter_iterator<BasicBlock::iterator, std::function<bool(Instruction &)>>> 258 BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) { 259 std::function<bool(Instruction &)> Fn = [=](Instruction &I) { 260 return !isa<DbgInfoIntrinsic>(I) && 261 !(SkipPseudoOp && isa<PseudoProbeInst>(I)); 262 }; 263 return make_filter_range(*this, Fn); 264 } 265 266 filter_iterator<BasicBlock::const_iterator, 267 std::function<bool(const Instruction &)>>::difference_type 268 BasicBlock::sizeWithoutDebug() const { 269 return std::distance(instructionsWithoutDebug().begin(), 270 instructionsWithoutDebug().end()); 271 } 272 273 void BasicBlock::removeFromParent() { 274 getParent()->getBasicBlockList().remove(getIterator()); 275 } 276 277 iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() { 278 return getParent()->getBasicBlockList().erase(getIterator()); 279 } 280 281 void BasicBlock::moveBefore(SymbolTableList<BasicBlock>::iterator MovePos) { 282 getParent()->splice(MovePos, getParent(), getIterator()); 283 } 284 285 void BasicBlock::moveAfter(BasicBlock *MovePos) { 286 MovePos->getParent()->splice(++MovePos->getIterator(), getParent(), 287 getIterator()); 288 } 289 290 const Module *BasicBlock::getModule() const { 291 return getParent()->getParent(); 292 } 293 294 const DataLayout &BasicBlock::getDataLayout() const { 295 return getModule()->getDataLayout(); 296 } 297 298 const CallInst *BasicBlock::getTerminatingMustTailCall() const { 299 if (InstList.empty()) 300 return nullptr; 301 const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back()); 302 if (!RI || RI == &InstList.front()) 303 return nullptr; 304 305 const Instruction *Prev = RI->getPrevNode(); 306 if (!Prev) 307 return nullptr; 308 309 if (Value *RV = RI->getReturnValue()) { 310 if (RV != Prev) 311 return nullptr; 312 313 // Look through the optional bitcast. 314 if (auto *BI = dyn_cast<BitCastInst>(Prev)) { 315 RV = BI->getOperand(0); 316 Prev = BI->getPrevNode(); 317 if (!Prev || RV != Prev) 318 return nullptr; 319 } 320 } 321 322 if (auto *CI = dyn_cast<CallInst>(Prev)) { 323 if (CI->isMustTailCall()) 324 return CI; 325 } 326 return nullptr; 327 } 328 329 const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const { 330 if (InstList.empty()) 331 return nullptr; 332 auto *RI = dyn_cast<ReturnInst>(&InstList.back()); 333 if (!RI || RI == &InstList.front()) 334 return nullptr; 335 336 if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode())) 337 if (Function *F = CI->getCalledFunction()) 338 if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize) 339 return CI; 340 341 return nullptr; 342 } 343 344 const CallInst *BasicBlock::getPostdominatingDeoptimizeCall() const { 345 const BasicBlock* BB = this; 346 SmallPtrSet<const BasicBlock *, 8> Visited; 347 Visited.insert(BB); 348 while (auto *Succ = BB->getUniqueSuccessor()) { 349 if (!Visited.insert(Succ).second) 350 return nullptr; 351 BB = Succ; 352 } 353 return BB->getTerminatingDeoptimizeCall(); 354 } 355 356 const Instruction *BasicBlock::getFirstMayFaultInst() const { 357 if (InstList.empty()) 358 return nullptr; 359 for (const Instruction &I : *this) 360 if (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallBase>(I)) 361 return &I; 362 return nullptr; 363 } 364 365 const Instruction* BasicBlock::getFirstNonPHI() const { 366 for (const Instruction &I : *this) 367 if (!isa<PHINode>(I)) 368 return &I; 369 return nullptr; 370 } 371 372 BasicBlock::const_iterator BasicBlock::getFirstNonPHIIt() const { 373 const Instruction *I = getFirstNonPHI(); 374 if (!I) 375 return end(); 376 BasicBlock::const_iterator It = I->getIterator(); 377 // Set the head-inclusive bit to indicate that this iterator includes 378 // any debug-info at the start of the block. This is a no-op unless the 379 // appropriate CMake flag is set. 380 It.setHeadBit(true); 381 return It; 382 } 383 384 const Instruction *BasicBlock::getFirstNonPHIOrDbg(bool SkipPseudoOp) const { 385 for (const Instruction &I : *this) { 386 if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I)) 387 continue; 388 389 if (SkipPseudoOp && isa<PseudoProbeInst>(I)) 390 continue; 391 392 return &I; 393 } 394 return nullptr; 395 } 396 397 const Instruction * 398 BasicBlock::getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp) const { 399 for (const Instruction &I : *this) { 400 if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I)) 401 continue; 402 403 if (I.isLifetimeStartOrEnd()) 404 continue; 405 406 if (SkipPseudoOp && isa<PseudoProbeInst>(I)) 407 continue; 408 409 return &I; 410 } 411 return nullptr; 412 } 413 414 BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const { 415 const Instruction *FirstNonPHI = getFirstNonPHI(); 416 if (!FirstNonPHI) 417 return end(); 418 419 const_iterator InsertPt = FirstNonPHI->getIterator(); 420 if (InsertPt->isEHPad()) ++InsertPt; 421 // Set the head-inclusive bit to indicate that this iterator includes 422 // any debug-info at the start of the block. This is a no-op unless the 423 // appropriate CMake flag is set. 424 InsertPt.setHeadBit(true); 425 return InsertPt; 426 } 427 428 BasicBlock::const_iterator BasicBlock::getFirstNonPHIOrDbgOrAlloca() const { 429 const Instruction *FirstNonPHI = getFirstNonPHI(); 430 if (!FirstNonPHI) 431 return end(); 432 433 const_iterator InsertPt = FirstNonPHI->getIterator(); 434 if (InsertPt->isEHPad()) 435 ++InsertPt; 436 437 if (isEntryBlock()) { 438 const_iterator End = end(); 439 while (InsertPt != End && 440 (isa<AllocaInst>(*InsertPt) || isa<DbgInfoIntrinsic>(*InsertPt) || 441 isa<PseudoProbeInst>(*InsertPt))) { 442 if (const AllocaInst *AI = dyn_cast<AllocaInst>(&*InsertPt)) { 443 if (!AI->isStaticAlloca()) 444 break; 445 } 446 ++InsertPt; 447 } 448 } 449 return InsertPt; 450 } 451 452 void BasicBlock::dropAllReferences() { 453 for (Instruction &I : *this) 454 I.dropAllReferences(); 455 } 456 457 const BasicBlock *BasicBlock::getSinglePredecessor() const { 458 const_pred_iterator PI = pred_begin(this), E = pred_end(this); 459 if (PI == E) return nullptr; // No preds. 460 const BasicBlock *ThePred = *PI; 461 ++PI; 462 return (PI == E) ? ThePred : nullptr /*multiple preds*/; 463 } 464 465 const BasicBlock *BasicBlock::getUniquePredecessor() const { 466 const_pred_iterator PI = pred_begin(this), E = pred_end(this); 467 if (PI == E) return nullptr; // No preds. 468 const BasicBlock *PredBB = *PI; 469 ++PI; 470 for (;PI != E; ++PI) { 471 if (*PI != PredBB) 472 return nullptr; 473 // The same predecessor appears multiple times in the predecessor list. 474 // This is OK. 475 } 476 return PredBB; 477 } 478 479 bool BasicBlock::hasNPredecessors(unsigned N) const { 480 return hasNItems(pred_begin(this), pred_end(this), N); 481 } 482 483 bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const { 484 return hasNItemsOrMore(pred_begin(this), pred_end(this), N); 485 } 486 487 const BasicBlock *BasicBlock::getSingleSuccessor() const { 488 const_succ_iterator SI = succ_begin(this), E = succ_end(this); 489 if (SI == E) return nullptr; // no successors 490 const BasicBlock *TheSucc = *SI; 491 ++SI; 492 return (SI == E) ? TheSucc : nullptr /* multiple successors */; 493 } 494 495 const BasicBlock *BasicBlock::getUniqueSuccessor() const { 496 const_succ_iterator SI = succ_begin(this), E = succ_end(this); 497 if (SI == E) return nullptr; // No successors 498 const BasicBlock *SuccBB = *SI; 499 ++SI; 500 for (;SI != E; ++SI) { 501 if (*SI != SuccBB) 502 return nullptr; 503 // The same successor appears multiple times in the successor list. 504 // This is OK. 505 } 506 return SuccBB; 507 } 508 509 iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() { 510 PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(&*begin()); 511 return make_range<phi_iterator>(P, nullptr); 512 } 513 514 void BasicBlock::removePredecessor(BasicBlock *Pred, 515 bool KeepOneInputPHIs) { 516 // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs. 517 assert((hasNUsesOrMore(16) || llvm::is_contained(predecessors(this), Pred)) && 518 "Pred is not a predecessor!"); 519 520 // Return early if there are no PHI nodes to update. 521 if (empty() || !isa<PHINode>(begin())) 522 return; 523 524 unsigned NumPreds = cast<PHINode>(front()).getNumIncomingValues(); 525 for (PHINode &Phi : make_early_inc_range(phis())) { 526 Phi.removeIncomingValue(Pred, !KeepOneInputPHIs); 527 if (KeepOneInputPHIs) 528 continue; 529 530 // If we have a single predecessor, removeIncomingValue may have erased the 531 // PHI node itself. 532 if (NumPreds == 1) 533 continue; 534 535 // Try to replace the PHI node with a constant value. 536 if (Value *PhiConstant = Phi.hasConstantValue()) { 537 Phi.replaceAllUsesWith(PhiConstant); 538 Phi.eraseFromParent(); 539 } 540 } 541 } 542 543 bool BasicBlock::canSplitPredecessors() const { 544 const Instruction *FirstNonPHI = getFirstNonPHI(); 545 if (isa<LandingPadInst>(FirstNonPHI)) 546 return true; 547 // This is perhaps a little conservative because constructs like 548 // CleanupBlockInst are pretty easy to split. However, SplitBlockPredecessors 549 // cannot handle such things just yet. 550 if (FirstNonPHI->isEHPad()) 551 return false; 552 return true; 553 } 554 555 bool BasicBlock::isLegalToHoistInto() const { 556 auto *Term = getTerminator(); 557 // No terminator means the block is under construction. 558 if (!Term) 559 return true; 560 561 // If the block has no successors, there can be no instructions to hoist. 562 assert(Term->getNumSuccessors() > 0); 563 564 // Instructions should not be hoisted across special terminators, which may 565 // have side effects or return values. 566 return !Term->isSpecialTerminator(); 567 } 568 569 bool BasicBlock::isEntryBlock() const { 570 const Function *F = getParent(); 571 assert(F && "Block must have a parent function to use this API"); 572 return this == &F->getEntryBlock(); 573 } 574 575 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName, 576 bool Before) { 577 if (Before) 578 return splitBasicBlockBefore(I, BBName); 579 580 assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 581 assert(I != InstList.end() && 582 "Trying to get me to create degenerate basic block!"); 583 584 BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(), 585 this->getNextNode()); 586 587 // Save DebugLoc of split point before invalidating iterator. 588 DebugLoc Loc = I->getStableDebugLoc(); 589 // Move all of the specified instructions from the original basic block into 590 // the new basic block. 591 New->splice(New->end(), this, I, end()); 592 593 // Add a branch instruction to the newly formed basic block. 594 BranchInst *BI = BranchInst::Create(New, this); 595 BI->setDebugLoc(Loc); 596 597 // Now we must loop through all of the successors of the New block (which 598 // _were_ the successors of the 'this' block), and update any PHI nodes in 599 // successors. If there were PHI nodes in the successors, then they need to 600 // know that incoming branches will be from New, not from Old (this). 601 // 602 New->replaceSuccessorsPhiUsesWith(this, New); 603 return New; 604 } 605 606 BasicBlock *BasicBlock::splitBasicBlockBefore(iterator I, const Twine &BBName) { 607 assert(getTerminator() && 608 "Can't use splitBasicBlockBefore on degenerate BB!"); 609 assert(I != InstList.end() && 610 "Trying to get me to create degenerate basic block!"); 611 612 assert((!isa<PHINode>(*I) || getSinglePredecessor()) && 613 "cannot split on multi incoming phis"); 614 615 BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(), this); 616 // Save DebugLoc of split point before invalidating iterator. 617 DebugLoc Loc = I->getDebugLoc(); 618 // Move all of the specified instructions from the original basic block into 619 // the new basic block. 620 New->splice(New->end(), this, begin(), I); 621 622 // Loop through all of the predecessors of the 'this' block (which will be the 623 // predecessors of the New block), replace the specified successor 'this' 624 // block to point at the New block and update any PHI nodes in 'this' block. 625 // If there were PHI nodes in 'this' block, the PHI nodes are updated 626 // to reflect that the incoming branches will be from the New block and not 627 // from predecessors of the 'this' block. 628 // Save predecessors to separate vector before modifying them. 629 SmallVector<BasicBlock *, 4> Predecessors; 630 for (BasicBlock *Pred : predecessors(this)) 631 Predecessors.push_back(Pred); 632 for (BasicBlock *Pred : Predecessors) { 633 Instruction *TI = Pred->getTerminator(); 634 TI->replaceSuccessorWith(this, New); 635 this->replacePhiUsesWith(Pred, New); 636 } 637 // Add a branch instruction from "New" to "this" Block. 638 BranchInst *BI = BranchInst::Create(this, New); 639 BI->setDebugLoc(Loc); 640 641 return New; 642 } 643 644 BasicBlock::iterator BasicBlock::erase(BasicBlock::iterator FromIt, 645 BasicBlock::iterator ToIt) { 646 for (Instruction &I : make_early_inc_range(make_range(FromIt, ToIt))) 647 I.eraseFromParent(); 648 return ToIt; 649 } 650 651 void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) { 652 // N.B. This might not be a complete BasicBlock, so don't assume 653 // that it ends with a non-phi instruction. 654 for (Instruction &I : *this) { 655 PHINode *PN = dyn_cast<PHINode>(&I); 656 if (!PN) 657 break; 658 PN->replaceIncomingBlockWith(Old, New); 659 } 660 } 661 662 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *Old, 663 BasicBlock *New) { 664 Instruction *TI = getTerminator(); 665 if (!TI) 666 // Cope with being called on a BasicBlock that doesn't have a terminator 667 // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this. 668 return; 669 for (BasicBlock *Succ : successors(TI)) 670 Succ->replacePhiUsesWith(Old, New); 671 } 672 673 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) { 674 this->replaceSuccessorsPhiUsesWith(this, New); 675 } 676 677 bool BasicBlock::isLandingPad() const { 678 return isa<LandingPadInst>(getFirstNonPHI()); 679 } 680 681 const LandingPadInst *BasicBlock::getLandingPadInst() const { 682 return dyn_cast<LandingPadInst>(getFirstNonPHI()); 683 } 684 685 std::optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const { 686 const Instruction *TI = getTerminator(); 687 if (MDNode *MDIrrLoopHeader = 688 TI->getMetadata(LLVMContext::MD_irr_loop)) { 689 MDString *MDName = cast<MDString>(MDIrrLoopHeader->getOperand(0)); 690 if (MDName->getString() == "loop_header_weight") { 691 auto *CI = mdconst::extract<ConstantInt>(MDIrrLoopHeader->getOperand(1)); 692 return std::optional<uint64_t>(CI->getValue().getZExtValue()); 693 } 694 } 695 return std::nullopt; 696 } 697 698 BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) { 699 while (isa<DbgInfoIntrinsic>(It)) 700 ++It; 701 return It; 702 } 703 704 void BasicBlock::renumberInstructions() { 705 unsigned Order = 0; 706 for (Instruction &I : *this) 707 I.Order = Order++; 708 709 // Set the bit to indicate that the instruction order valid and cached. 710 BasicBlockBits Bits = getBasicBlockBits(); 711 Bits.InstrOrderValid = true; 712 setBasicBlockBits(Bits); 713 714 NumInstrRenumberings++; 715 } 716 717 void BasicBlock::flushTerminatorDbgRecords() { 718 // If we erase the terminator in a block, any DbgRecords will sink and "fall 719 // off the end", existing after any terminator that gets inserted. With 720 // dbg.value intrinsics we would just insert the terminator at end() and 721 // the dbg.values would come before the terminator. With DbgRecords, we must 722 // do this manually. 723 // To get out of this unfortunate form, whenever we insert a terminator, 724 // check whether there's anything trailing at the end and move those 725 // DbgRecords in front of the terminator. 726 727 // Do nothing if we're not in new debug-info format. 728 if (!IsNewDbgInfoFormat) 729 return; 730 731 // If there's no terminator, there's nothing to do. 732 Instruction *Term = getTerminator(); 733 if (!Term) 734 return; 735 736 // Are there any dangling DbgRecords? 737 DbgMarker *TrailingDbgRecords = getTrailingDbgRecords(); 738 if (!TrailingDbgRecords) 739 return; 740 741 // Transfer DbgRecords from the trailing position onto the terminator. 742 createMarker(Term); 743 Term->DebugMarker->absorbDebugValues(*TrailingDbgRecords, false); 744 TrailingDbgRecords->eraseFromParent(); 745 deleteTrailingDbgRecords(); 746 } 747 748 void BasicBlock::spliceDebugInfoEmptyBlock(BasicBlock::iterator Dest, 749 BasicBlock *Src, 750 BasicBlock::iterator First, 751 BasicBlock::iterator Last) { 752 // Imagine the folowing: 753 // 754 // bb1: 755 // dbg.value(... 756 // ret i32 0 757 // 758 // If an optimisation pass attempts to splice the contents of the block from 759 // BB1->begin() to BB1->getTerminator(), then the dbg.value will be 760 // transferred to the destination. 761 // However, in the "new" DbgRecord format for debug-info, that range is empty: 762 // begin() returns an iterator to the terminator, as there will only be a 763 // single instruction in the block. We must piece together from the bits set 764 // in the iterators whether there was the intention to transfer any debug 765 // info. 766 767 // If we're not in "new" debug-info format, do nothing. 768 if (!IsNewDbgInfoFormat) 769 return; 770 771 assert(First == Last); 772 bool InsertAtHead = Dest.getHeadBit(); 773 bool ReadFromHead = First.getHeadBit(); 774 775 // If the source block is completely empty, including no terminator, then 776 // transfer any trailing DbgRecords that are still hanging around. This can 777 // occur when a block is optimised away and the terminator has been moved 778 // somewhere else. 779 if (Src->empty()) { 780 DbgMarker *SrcTrailingDbgRecords = Src->getTrailingDbgRecords(); 781 if (!SrcTrailingDbgRecords) 782 return; 783 784 Dest->adoptDbgRecords(Src, Src->end(), InsertAtHead); 785 // adoptDbgRecords should have released the trailing DbgRecords. 786 assert(!Src->getTrailingDbgRecords()); 787 return; 788 } 789 790 // There are instructions in this block; if the First iterator was 791 // with begin() / getFirstInsertionPt() then the caller intended debug-info 792 // at the start of the block to be transferred. Return otherwise. 793 if (Src->empty() || First != Src->begin() || !ReadFromHead) 794 return; 795 796 // Is there actually anything to transfer? 797 if (!First->hasDbgRecords()) 798 return; 799 800 createMarker(Dest)->absorbDebugValues(*First->DebugMarker, InsertAtHead); 801 802 return; 803 } 804 805 void BasicBlock::spliceDebugInfo(BasicBlock::iterator Dest, BasicBlock *Src, 806 BasicBlock::iterator First, 807 BasicBlock::iterator Last) { 808 /* Do a quick normalisation before calling the real splice implementation. We 809 might be operating on a degenerate basic block that has no instructions 810 in it, a legitimate transient state. In that case, Dest will be end() and 811 any DbgRecords temporarily stored in the TrailingDbgRecords map in 812 LLVMContext. We might illustrate it thus: 813 814 Dest 815 | 816 this-block: ~~~~~~~~ 817 Src-block: ++++B---B---B---B:::C 818 | | 819 First Last 820 821 However: does the caller expect the "~" DbgRecords to end up before or 822 after the spliced segment? This is communciated in the "Head" bit of Dest, 823 which signals whether the caller called begin() or end() on this block. 824 825 If the head bit is set, then all is well, we leave DbgRecords trailing just 826 like how dbg.value instructions would trail after instructions spliced to 827 the beginning of this block. 828 829 If the head bit isn't set, then try to jam the "~" DbgRecords onto the 830 front of the First instruction, then splice like normal, which joins the 831 "~" DbgRecords with the "+" DbgRecords. However if the "+" DbgRecords are 832 supposed to be left behind in Src, then: 833 * detach the "+" DbgRecords, 834 * move the "~" DbgRecords onto First, 835 * splice like normal, 836 * replace the "+" DbgRecords onto the Last position. 837 Complicated, but gets the job done. */ 838 839 // If we're inserting at end(), and not in front of dangling DbgRecords, then 840 // move the DbgRecords onto "First". They'll then be moved naturally in the 841 // splice process. 842 DbgMarker *MoreDanglingDbgRecords = nullptr; 843 DbgMarker *OurTrailingDbgRecords = getTrailingDbgRecords(); 844 if (Dest == end() && !Dest.getHeadBit() && OurTrailingDbgRecords) { 845 // Are the "+" DbgRecords not supposed to move? If so, detach them 846 // temporarily. 847 if (!First.getHeadBit() && First->hasDbgRecords()) { 848 MoreDanglingDbgRecords = Src->getMarker(First); 849 MoreDanglingDbgRecords->removeFromParent(); 850 } 851 852 if (First->hasDbgRecords()) { 853 // Place them at the front, it would look like this: 854 // Dest 855 // | 856 // this-block: 857 // Src-block: ~~~~~~~~++++B---B---B---B:::C 858 // | | 859 // First Last 860 First->adoptDbgRecords(this, end(), true); 861 } else { 862 // No current marker, create one and absorb in. (FIXME: we can avoid an 863 // allocation in the future). 864 DbgMarker *CurMarker = Src->createMarker(&*First); 865 CurMarker->absorbDebugValues(*OurTrailingDbgRecords, false); 866 OurTrailingDbgRecords->eraseFromParent(); 867 } 868 deleteTrailingDbgRecords(); 869 First.setHeadBit(true); 870 } 871 872 // Call the main debug-info-splicing implementation. 873 spliceDebugInfoImpl(Dest, Src, First, Last); 874 875 // Do we have some "+" DbgRecords hanging around that weren't supposed to 876 // move, and we detached to make things easier? 877 if (!MoreDanglingDbgRecords) 878 return; 879 880 // FIXME: we could avoid an allocation here sometimes. (adoptDbgRecords 881 // requires an iterator). 882 DbgMarker *LastMarker = Src->createMarker(Last); 883 LastMarker->absorbDebugValues(*MoreDanglingDbgRecords, true); 884 MoreDanglingDbgRecords->eraseFromParent(); 885 } 886 887 void BasicBlock::spliceDebugInfoImpl(BasicBlock::iterator Dest, BasicBlock *Src, 888 BasicBlock::iterator First, 889 BasicBlock::iterator Last) { 890 // Find out where to _place_ these dbg.values; if InsertAtHead is specified, 891 // this will be at the start of Dest's debug value range, otherwise this is 892 // just Dest's marker. 893 bool InsertAtHead = Dest.getHeadBit(); 894 bool ReadFromHead = First.getHeadBit(); 895 // Use this flag to signal the abnormal case, where we don't want to copy the 896 // DbgRecords ahead of the "Last" position. 897 bool ReadFromTail = !Last.getTailBit(); 898 bool LastIsEnd = (Last == Src->end()); 899 900 /* 901 Here's an illustration of what we're about to do. We have two blocks, this 902 and Src, and two segments of list. Each instruction is marked by a capital 903 while potential DbgRecord debug-info is marked out by "-" characters and a 904 few other special characters (+:=) where I want to highlight what's going 905 on. 906 907 Dest 908 | 909 this-block: A----A----A ====A----A----A----A---A---A 910 Src-block ++++B---B---B---B:::C 911 | | 912 First Last 913 914 The splice method is going to take all the instructions from First up to 915 (but not including) Last and insert them in _front_ of Dest, forming one 916 long list. All the DbgRecords attached to instructions _between_ First and 917 Last need no maintenence. However, we have to do special things with the 918 DbgRecords marked with the +:= characters. We only have three positions: 919 should the "+" DbgRecords be transferred, and if so to where? Do we move the 920 ":" DbgRecords? Would they go in front of the "=" DbgRecords, or should the 921 "=" DbgRecords go before "+" DbgRecords? 922 923 We're told which way it should be by the bits carried in the iterators. The 924 "Head" bit indicates whether the specified position is supposed to be at the 925 front of the attached DbgRecords (true) or not (false). The Tail bit is true 926 on the other end of a range: is the range intended to include DbgRecords up 927 to the end (false) or not (true). 928 929 FIXME: the tail bit doesn't need to be distinct from the head bit, we could 930 combine them. 931 932 Here are some examples of different configurations: 933 934 Dest.Head = true, First.Head = true, Last.Tail = false 935 936 this-block: A----A----A++++B---B---B---B:::====A----A----A----A---A---A 937 | | 938 First Dest 939 940 Wheras if we didn't want to read from the Src list, 941 942 Dest.Head = true, First.Head = false, Last.Tail = false 943 944 this-block: A----A----AB---B---B---B:::====A----A----A----A---A---A 945 | | 946 First Dest 947 948 Or if we didn't want to insert at the head of Dest: 949 950 Dest.Head = false, First.Head = false, Last.Tail = false 951 952 this-block: A----A----A====B---B---B---B:::A----A----A----A---A---A 953 | | 954 First Dest 955 956 Tests for these various configurations can be found in the unit test file 957 BasicBlockDbgInfoTest.cpp. 958 959 */ 960 961 // Detach the marker at Dest -- this lets us move the "====" DbgRecords 962 // around. 963 DbgMarker *DestMarker = nullptr; 964 if ((DestMarker = getMarker(Dest))) { 965 if (Dest == end()) { 966 assert(DestMarker == getTrailingDbgRecords()); 967 deleteTrailingDbgRecords(); 968 } else { 969 DestMarker->removeFromParent(); 970 } 971 } 972 973 // If we're moving the tail range of DbgRecords (":::"), absorb them into the 974 // front of the DbgRecords at Dest. 975 if (ReadFromTail && Src->getMarker(Last)) { 976 DbgMarker *FromLast = Src->getMarker(Last); 977 if (LastIsEnd) { 978 if (Dest == end()) { 979 // Abosrb the trailing markers from Src. 980 assert(FromLast == Src->getTrailingDbgRecords()); 981 createMarker(Dest)->absorbDebugValues(*FromLast, true); 982 FromLast->eraseFromParent(); 983 Src->deleteTrailingDbgRecords(); 984 } else { 985 // adoptDbgRecords will release any trailers. 986 Dest->adoptDbgRecords(Src, Last, true); 987 } 988 assert(!Src->getTrailingDbgRecords()); 989 } else { 990 // FIXME: can we use adoptDbgRecords here to reduce allocations? 991 DbgMarker *OntoDest = createMarker(Dest); 992 OntoDest->absorbDebugValues(*FromLast, true); 993 } 994 } 995 996 // If we're _not_ reading from the head of First, i.e. the "++++" DbgRecords, 997 // move their markers onto Last. They remain in the Src block. No action 998 // needed. 999 if (!ReadFromHead && First->hasDbgRecords()) { 1000 if (Last != Src->end()) { 1001 Last->adoptDbgRecords(Src, First, true); 1002 } else { 1003 DbgMarker *OntoLast = Src->createMarker(Last); 1004 DbgMarker *FromFirst = Src->createMarker(First); 1005 // Always insert at front of Last. 1006 OntoLast->absorbDebugValues(*FromFirst, true); 1007 } 1008 } 1009 1010 // Finally, do something with the "====" DbgRecords we detached. 1011 if (DestMarker) { 1012 if (InsertAtHead) { 1013 // Insert them at the end of the DbgRecords at Dest. The "::::" DbgRecords 1014 // might be in front of them. 1015 DbgMarker *NewDestMarker = createMarker(Dest); 1016 NewDestMarker->absorbDebugValues(*DestMarker, false); 1017 } else { 1018 // Insert them right at the start of the range we moved, ahead of First 1019 // and the "++++" DbgRecords. 1020 // This also covers the rare circumstance where we insert at end(), and we 1021 // did not generate the iterator with begin() / getFirstInsertionPt(), 1022 // meaning any trailing debug-info at the end of the block would 1023 // "normally" have been pushed in front of "First". We move it there now. 1024 DbgMarker *FirstMarker = createMarker(First); 1025 FirstMarker->absorbDebugValues(*DestMarker, true); 1026 } 1027 DestMarker->eraseFromParent(); 1028 } 1029 } 1030 1031 void BasicBlock::splice(iterator Dest, BasicBlock *Src, iterator First, 1032 iterator Last) { 1033 assert(Src->IsNewDbgInfoFormat == IsNewDbgInfoFormat); 1034 1035 #ifdef EXPENSIVE_CHECKS 1036 // Check that First is before Last. 1037 auto FromBBEnd = Src->end(); 1038 for (auto It = First; It != Last; ++It) 1039 assert(It != FromBBEnd && "FromBeginIt not before FromEndIt!"); 1040 #endif // EXPENSIVE_CHECKS 1041 1042 // Lots of horrible special casing for empty transfers: the dbg.values between 1043 // two positions could be spliced in dbg.value mode. 1044 if (First == Last) { 1045 spliceDebugInfoEmptyBlock(Dest, Src, First, Last); 1046 return; 1047 } 1048 1049 // Handle non-instr debug-info specific juggling. 1050 if (IsNewDbgInfoFormat) 1051 spliceDebugInfo(Dest, Src, First, Last); 1052 1053 // And move the instructions. 1054 getInstList().splice(Dest, Src->getInstList(), First, Last); 1055 1056 flushTerminatorDbgRecords(); 1057 } 1058 1059 void BasicBlock::insertDbgRecordAfter(DbgRecord *DR, Instruction *I) { 1060 assert(IsNewDbgInfoFormat); 1061 assert(I->getParent() == this); 1062 1063 iterator NextIt = std::next(I->getIterator()); 1064 DbgMarker *NextMarker = createMarker(NextIt); 1065 NextMarker->insertDbgRecord(DR, true); 1066 } 1067 1068 void BasicBlock::insertDbgRecordBefore(DbgRecord *DR, 1069 InstListType::iterator Where) { 1070 assert(Where == end() || Where->getParent() == this); 1071 bool InsertAtHead = Where.getHeadBit(); 1072 DbgMarker *M = createMarker(Where); 1073 M->insertDbgRecord(DR, InsertAtHead); 1074 } 1075 1076 DbgMarker *BasicBlock::getNextMarker(Instruction *I) { 1077 return getMarker(std::next(I->getIterator())); 1078 } 1079 1080 DbgMarker *BasicBlock::getMarker(InstListType::iterator It) { 1081 if (It == end()) { 1082 DbgMarker *DM = getTrailingDbgRecords(); 1083 return DM; 1084 } 1085 return It->DebugMarker; 1086 } 1087 1088 void BasicBlock::reinsertInstInDbgRecords( 1089 Instruction *I, std::optional<DbgRecord::self_iterator> Pos) { 1090 // "I" was originally removed from a position where it was 1091 // immediately in front of Pos. Any DbgRecords on that position then "fell 1092 // down" onto Pos. "I" has been re-inserted at the front of that wedge of 1093 // DbgRecords, shuffle them around to represent the original positioning. To 1094 // illustrate: 1095 // 1096 // Instructions: I1---I---I0 1097 // DbgRecords: DDD DDD 1098 // 1099 // Instruction "I" removed, 1100 // 1101 // Instructions: I1------I0 1102 // DbgRecords: DDDDDD 1103 // ^Pos 1104 // 1105 // Instruction "I" re-inserted (now): 1106 // 1107 // Instructions: I1---I------I0 1108 // DbgRecords: DDDDDD 1109 // ^Pos 1110 // 1111 // After this method completes: 1112 // 1113 // Instructions: I1---I---I0 1114 // DbgRecords: DDD DDD 1115 1116 // This happens if there were no DbgRecords on I0. Are there now DbgRecords 1117 // there? 1118 if (!Pos) { 1119 DbgMarker *NextMarker = getNextMarker(I); 1120 if (!NextMarker) 1121 return; 1122 if (NextMarker->StoredDbgRecords.empty()) 1123 return; 1124 // There are DbgMarkers there now -- they fell down from "I". 1125 DbgMarker *ThisMarker = createMarker(I); 1126 ThisMarker->absorbDebugValues(*NextMarker, false); 1127 return; 1128 } 1129 1130 // Is there even a range of DbgRecords to move? 1131 DbgMarker *DM = (*Pos)->getMarker(); 1132 auto Range = make_range(DM->StoredDbgRecords.begin(), (*Pos)); 1133 if (Range.begin() == Range.end()) 1134 return; 1135 1136 // Otherwise: splice. 1137 DbgMarker *ThisMarker = createMarker(I); 1138 assert(ThisMarker->StoredDbgRecords.empty()); 1139 ThisMarker->absorbDebugValues(Range, *DM, true); 1140 } 1141 1142 #ifndef NDEBUG 1143 /// In asserts builds, this checks the numbering. In non-asserts builds, it 1144 /// is defined as a no-op inline function in BasicBlock.h. 1145 void BasicBlock::validateInstrOrdering() const { 1146 if (!isInstrOrderValid()) 1147 return; 1148 const Instruction *Prev = nullptr; 1149 for (const Instruction &I : *this) { 1150 assert((!Prev || Prev->comesBefore(&I)) && 1151 "cached instruction ordering is incorrect"); 1152 Prev = &I; 1153 } 1154 } 1155 #endif 1156 1157 void BasicBlock::setTrailingDbgRecords(DbgMarker *foo) { 1158 getContext().pImpl->setTrailingDbgRecords(this, foo); 1159 } 1160 1161 DbgMarker *BasicBlock::getTrailingDbgRecords() { 1162 return getContext().pImpl->getTrailingDbgRecords(this); 1163 } 1164 1165 void BasicBlock::deleteTrailingDbgRecords() { 1166 getContext().pImpl->deleteTrailingDbgRecords(this); 1167 } 1168