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