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