llvm/lib/IR/BasicBlock.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-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/Instructions.h"
  20 #include "llvm/IR/IntrinsicInst.h"
  21 #include "llvm/IR/LLVMContext.h"
  22 #include "llvm/IR/Type.h"
  23
  24 using namespace llvm;
  25
  26 #define DEBUG_TYPE "ir"
  27 STATISTIC(NumInstrRenumberings, "Number of renumberings across all blocks");
  28
  29 ValueSymbolTable *BasicBlock::getValueSymbolTable() {
  30   if (Function *F = getParent())
  31     return F->getValueSymbolTable();
  32   return nullptr;
  33 }
  34
  35 LLVMContext &BasicBlock::getContext() const {
  36   return getType()->getContext();
  37 }
  38
  39 template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) {
  40   BB->invalidateOrders();
  41 }
  42
  43 // Explicit instantiation of SymbolTableListTraits since some of the methods
  44 // are not in the public header file...
  45 template class llvm::SymbolTableListTraits<Instruction,
  46                                            ilist_iterator_bits<true>>;
  47
  48 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
  49                        BasicBlock *InsertBefore)
  50   : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
  51
  52   if (NewParent)
  53     insertInto(NewParent, InsertBefore);
  54   else
  55     assert(!InsertBefore &&
  56            "Cannot insert block before another block with no function!");
  57
  58   setName(Name);
  59 }
  60
  61 void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
  62   assert(NewParent && "Expected a parent");
  63   assert(!Parent && "Already has a parent");
  64
  65   if (InsertBefore)
  66     NewParent->insert(InsertBefore->getIterator(), this);
  67   else
  68     NewParent->insert(NewParent->end(), this);
  69 }
  70
  71 BasicBlock::~BasicBlock() {
  72   validateInstrOrdering();
  73
  74   // If the address of the block is taken and it is being deleted (e.g. because
  75   // it is dead), this means that there is either a dangling constant expr
  76   // hanging off the block, or an undefined use of the block (source code
  77   // expecting the address of a label to keep the block alive even though there
  78   // is no indirect branch).  Handle these cases by zapping the BlockAddress
  79   // nodes.  There are no other possible uses at this point.
  80   if (hasAddressTaken()) {
  81     assert(!use_empty() && "There should be at least one blockaddress!");
  82     Constant *Replacement =
  83       ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
  84     while (!use_empty()) {
  85       BlockAddress *BA = cast<BlockAddress>(user_back());
  86       BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
  87                                                        BA->getType()));
  88       BA->destroyConstant();
  89     }
  90   }
  91
  92   assert(getParent() == nullptr && "BasicBlock still linked into the program!");
  93   dropAllReferences();
  94   InstList.clear();
  95 }
  96
  97 void BasicBlock::setParent(Function *parent) {
  98   // Set Parent=parent, updating instruction symtab entries as appropriate.
  99   InstList.setSymTabObject(&Parent, parent);
 100 }
 101
 102 iterator_range<filter_iterator<BasicBlock::const_iterator,
 103                                std::function<bool(const Instruction &)>>>
 104 BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) const {
 105   std::function<bool(const Instruction &)> Fn = [=](const Instruction &I) {
 106     return !isa<DbgInfoIntrinsic>(I) &&
 107            !(SkipPseudoOp && isa<PseudoProbeInst>(I));
 108   };
 109   return make_filter_range(*this, Fn);
 110 }
 111
 112 iterator_range<
 113     filter_iterator<BasicBlock::iterator, std::function<bool(Instruction &)>>>
 114 BasicBlock::instructionsWithoutDebug(bool SkipPseudoOp) {
 115   std::function<bool(Instruction &)> Fn = [=](Instruction &I) {
 116     return !isa<DbgInfoIntrinsic>(I) &&
 117            !(SkipPseudoOp && isa<PseudoProbeInst>(I));
 118   };
 119   return make_filter_range(*this, Fn);
 120 }
 121
 122 filter_iterator<BasicBlock::const_iterator,
 123                 std::function<bool(const Instruction &)>>::difference_type
 124 BasicBlock::sizeWithoutDebug() const {
 125   return std::distance(instructionsWithoutDebug().begin(),
 126                        instructionsWithoutDebug().end());
 127 }
 128
 129 void BasicBlock::removeFromParent() {
 130   getParent()->getBasicBlockList().remove(getIterator());
 131 }
 132
 133 iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
 134   return getParent()->getBasicBlockList().erase(getIterator());
 135 }
 136
 137 void BasicBlock::moveBefore(SymbolTableList<BasicBlock>::iterator MovePos) {
 138   getParent()->splice(MovePos, getParent(), getIterator());
 139 }
 140
 141 void BasicBlock::moveAfter(BasicBlock *MovePos) {
 142   MovePos->getParent()->splice(++MovePos->getIterator(), getParent(),
 143                                getIterator());
 144 }
 145
 146 const Module *BasicBlock::getModule() const {
 147   return getParent()->getParent();
 148 }
 149
 150 const CallInst *BasicBlock::getTerminatingMustTailCall() const {
 151   if (InstList.empty())
 152     return nullptr;
 153   const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
 154   if (!RI || RI == &InstList.front())
 155     return nullptr;
 156
 157   const Instruction *Prev = RI->getPrevNode();
 158   if (!Prev)
 159     return nullptr;
 160
 161   if (Value *RV = RI->getReturnValue()) {
 162     if (RV != Prev)
 163       return nullptr;
 164
 165     // Look through the optional bitcast.
 166     if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
 167       RV = BI->getOperand(0);
 168       Prev = BI->getPrevNode();
 169       if (!Prev || RV != Prev)
 170         return nullptr;
 171     }
 172   }
 173
 174   if (auto *CI = dyn_cast<CallInst>(Prev)) {
 175     if (CI->isMustTailCall())
 176       return CI;
 177   }
 178   return nullptr;
 179 }
 180
 181 const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
 182   if (InstList.empty())
 183     return nullptr;
 184   auto *RI = dyn_cast<ReturnInst>(&InstList.back());
 185   if (!RI || RI == &InstList.front())
 186     return nullptr;
 187
 188   if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
 189     if (Function *F = CI->getCalledFunction())
 190       if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
 191         return CI;
 192
 193   return nullptr;
 194 }
 195
 196 const CallInst *BasicBlock::getPostdominatingDeoptimizeCall() const {
 197   const BasicBlock* BB = this;
 198   SmallPtrSet<const BasicBlock *, 8> Visited;
 199   Visited.insert(BB);
 200   while (auto *Succ = BB->getUniqueSuccessor()) {
 201     if (!Visited.insert(Succ).second)
 202       return nullptr;
 203     BB = Succ;
 204   }
 205   return BB->getTerminatingDeoptimizeCall();
 206 }
 207
 208 const Instruction *BasicBlock::getFirstMayFaultInst() const {
 209   if (InstList.empty())
 210     return nullptr;
 211   for (const Instruction &I : *this)
 212     if (isa<LoadInst>(I) || isa<StoreInst>(I) || isa<CallBase>(I))
 213       return &I;
 214   return nullptr;
 215 }
 216
 217 const Instruction* BasicBlock::getFirstNonPHI() const {
 218   for (const Instruction &I : *this)
 219     if (!isa<PHINode>(I))
 220       return &I;
 221   return nullptr;
 222 }
 223
 224 BasicBlock::const_iterator BasicBlock::getFirstNonPHIIt() const {
 225   const Instruction *I = getFirstNonPHI();
 226   BasicBlock::const_iterator It = I->getIterator();
 227   // Set the head-inclusive bit to indicate that this iterator includes
 228   // any debug-info at the start of the block. This is a no-op unless the
 229   // appropriate CMake flag is set.
 230   It.setHeadBit(true);
 231   return It;
 232 }
 233
 234 const Instruction *BasicBlock::getFirstNonPHIOrDbg(bool SkipPseudoOp) const {
 235   for (const Instruction &I : *this) {
 236     if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
 237       continue;
 238
 239     if (SkipPseudoOp && isa<PseudoProbeInst>(I))
 240       continue;
 241
 242     return &I;
 243   }
 244   return nullptr;
 245 }
 246
 247 const Instruction *
 248 BasicBlock::getFirstNonPHIOrDbgOrLifetime(bool SkipPseudoOp) const {
 249   for (const Instruction &I : *this) {
 250     if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
 251       continue;
 252
 253     if (I.isLifetimeStartOrEnd())
 254       continue;
 255
 256     if (SkipPseudoOp && isa<PseudoProbeInst>(I))
 257       continue;
 258
 259     return &I;
 260   }
 261   return nullptr;
 262 }
 263
 264 BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
 265   const Instruction *FirstNonPHI = getFirstNonPHI();
 266   if (!FirstNonPHI)
 267     return end();
 268
 269   const_iterator InsertPt = FirstNonPHI->getIterator();
 270   if (InsertPt->isEHPad()) ++InsertPt;
 271   // Set the head-inclusive bit to indicate that this iterator includes
 272   // any debug-info at the start of the block. This is a no-op unless the
 273   // appropriate CMake flag is set.
 274   InsertPt.setHeadBit(true);
 275   return InsertPt;
 276 }
 277
 278 BasicBlock::const_iterator BasicBlock::getFirstNonPHIOrDbgOrAlloca() const {
 279   const Instruction *FirstNonPHI = getFirstNonPHI();
 280   if (!FirstNonPHI)
 281     return end();
 282
 283   const_iterator InsertPt = FirstNonPHI->getIterator();
 284   if (InsertPt->isEHPad())
 285     ++InsertPt;
 286
 287   if (isEntryBlock()) {
 288     const_iterator End = end();
 289     while (InsertPt != End &&
 290            (isa<AllocaInst>(*InsertPt) || isa<DbgInfoIntrinsic>(*InsertPt) ||
 291             isa<PseudoProbeInst>(*InsertPt))) {
 292       if (const AllocaInst *AI = dyn_cast<AllocaInst>(&*InsertPt)) {
 293         if (!AI->isStaticAlloca())
 294           break;
 295       }
 296       ++InsertPt;
 297     }
 298   }
 299   return InsertPt;
 300 }
 301
 302 void BasicBlock::dropAllReferences() {
 303   for (Instruction &I : *this)
 304     I.dropAllReferences();
 305 }
 306
 307 const BasicBlock *BasicBlock::getSinglePredecessor() const {
 308   const_pred_iterator PI = pred_begin(this), E = pred_end(this);
 309   if (PI == E) return nullptr;         // No preds.
 310   const BasicBlock *ThePred = *PI;
 311   ++PI;
 312   return (PI == E) ? ThePred : nullptr /*multiple preds*/;
 313 }
 314
 315 const BasicBlock *BasicBlock::getUniquePredecessor() const {
 316   const_pred_iterator PI = pred_begin(this), E = pred_end(this);
 317   if (PI == E) return nullptr; // No preds.
 318   const BasicBlock *PredBB = *PI;
 319   ++PI;
 320   for (;PI != E; ++PI) {
 321     if (*PI != PredBB)
 322       return nullptr;
 323     // The same predecessor appears multiple times in the predecessor list.
 324     // This is OK.
 325   }
 326   return PredBB;
 327 }
 328
 329 bool BasicBlock::hasNPredecessors(unsigned N) const {
 330   return hasNItems(pred_begin(this), pred_end(this), N);
 331 }
 332
 333 bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const {
 334   return hasNItemsOrMore(pred_begin(this), pred_end(this), N);
 335 }
 336
 337 const BasicBlock *BasicBlock::getSingleSuccessor() const {
 338   const_succ_iterator SI = succ_begin(this), E = succ_end(this);
 339   if (SI == E) return nullptr; // no successors
 340   const BasicBlock *TheSucc = *SI;
 341   ++SI;
 342   return (SI == E) ? TheSucc : nullptr /* multiple successors */;
 343 }
 344
 345 const BasicBlock *BasicBlock::getUniqueSuccessor() const {
 346   const_succ_iterator SI = succ_begin(this), E = succ_end(this);
 347   if (SI == E) return nullptr; // No successors
 348   const BasicBlock *SuccBB = *SI;
 349   ++SI;
 350   for (;SI != E; ++SI) {
 351     if (*SI != SuccBB)
 352       return nullptr;
 353     // The same successor appears multiple times in the successor list.
 354     // This is OK.
 355   }
 356   return SuccBB;
 357 }
 358
 359 iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
 360   PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(&*begin());
 361   return make_range<phi_iterator>(P, nullptr);
 362 }
 363
 364 void BasicBlock::removePredecessor(BasicBlock *Pred,
 365                                    bool KeepOneInputPHIs) {
 366   // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
 367   assert((hasNUsesOrMore(16) || llvm::is_contained(predecessors(this), Pred)) &&
 368          "Pred is not a predecessor!");
 369
 370   // Return early if there are no PHI nodes to update.
 371   if (empty() || !isa<PHINode>(begin()))
 372     return;
 373
 374   unsigned NumPreds = cast<PHINode>(front()).getNumIncomingValues();
 375   for (PHINode &Phi : make_early_inc_range(phis())) {
 376     Phi.removeIncomingValue(Pred, !KeepOneInputPHIs);
 377     if (KeepOneInputPHIs)
 378       continue;
 379
 380     // If we have a single predecessor, removeIncomingValue may have erased the
 381     // PHI node itself.
 382     if (NumPreds == 1)
 383       continue;
 384
 385     // Try to replace the PHI node with a constant value.
 386     if (Value *PhiConstant = Phi.hasConstantValue()) {
 387       Phi.replaceAllUsesWith(PhiConstant);
 388       Phi.eraseFromParent();
 389     }
 390   }
 391 }
 392
 393 bool BasicBlock::canSplitPredecessors() const {
 394   const Instruction *FirstNonPHI = getFirstNonPHI();
 395   if (isa<LandingPadInst>(FirstNonPHI))
 396     return true;
 397   // This is perhaps a little conservative because constructs like
 398   // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
 399   // cannot handle such things just yet.
 400   if (FirstNonPHI->isEHPad())
 401     return false;
 402   return true;
 403 }
 404
 405 bool BasicBlock::isLegalToHoistInto() const {
 406   auto *Term = getTerminator();
 407   // No terminator means the block is under construction.
 408   if (!Term)
 409     return true;
 410
 411   // If the block has no successors, there can be no instructions to hoist.
 412   assert(Term->getNumSuccessors() > 0);
 413
 414   // Instructions should not be hoisted across special terminators, which may
 415   // have side effects or return values.
 416   return !Term->isSpecialTerminator();
 417 }
 418
 419 bool BasicBlock::isEntryBlock() const {
 420   const Function *F = getParent();
 421   assert(F && "Block must have a parent function to use this API");
 422   return this == &F->getEntryBlock();
 423 }
 424
 425 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName,
 426                                         bool Before) {
 427   if (Before)
 428     return splitBasicBlockBefore(I, BBName);
 429
 430   assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
 431   assert(I != InstList.end() &&
 432          "Trying to get me to create degenerate basic block!");
 433
 434   BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
 435                                        this->getNextNode());
 436
 437   // Save DebugLoc of split point before invalidating iterator.
 438   DebugLoc Loc = I->getDebugLoc();
 439   // Move all of the specified instructions from the original basic block into
 440   // the new basic block.
 441   New->splice(New->end(), this, I, end());
 442
 443   // Add a branch instruction to the newly formed basic block.
 444   BranchInst *BI = BranchInst::Create(New, this);
 445   BI->setDebugLoc(Loc);
 446
 447   // Now we must loop through all of the successors of the New block (which
 448   // _were_ the successors of the 'this' block), and update any PHI nodes in
 449   // successors.  If there were PHI nodes in the successors, then they need to
 450   // know that incoming branches will be from New, not from Old (this).
 451   //
 452   New->replaceSuccessorsPhiUsesWith(this, New);
 453   return New;
 454 }
 455
 456 BasicBlock *BasicBlock::splitBasicBlockBefore(iterator I, const Twine &BBName) {
 457   assert(getTerminator() &&
 458          "Can't use splitBasicBlockBefore on degenerate BB!");
 459   assert(I != InstList.end() &&
 460          "Trying to get me to create degenerate basic block!");
 461
 462   assert((!isa<PHINode>(*I) || getSinglePredecessor()) &&
 463          "cannot split on multi incoming phis");
 464
 465   BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(), this);
 466   // Save DebugLoc of split point before invalidating iterator.
 467   DebugLoc Loc = I->getDebugLoc();
 468   // Move all of the specified instructions from the original basic block into
 469   // the new basic block.
 470   New->splice(New->end(), this, begin(), I);
 471
 472   // Loop through all of the predecessors of the 'this' block (which will be the
 473   // predecessors of the New block), replace the specified successor 'this'
 474   // block to point at the New block and update any PHI nodes in 'this' block.
 475   // If there were PHI nodes in 'this' block, the PHI nodes are updated
 476   // to reflect that the incoming branches will be from the New block and not
 477   // from predecessors of the 'this' block.
 478   // Save predecessors to separate vector before modifying them.
 479   SmallVector<BasicBlock *, 4> Predecessors;
 480   for (BasicBlock *Pred : predecessors(this))
 481     Predecessors.push_back(Pred);
 482   for (BasicBlock *Pred : Predecessors) {
 483     Instruction *TI = Pred->getTerminator();
 484     TI->replaceSuccessorWith(this, New);
 485     this->replacePhiUsesWith(Pred, New);
 486   }
 487   // Add a branch instruction from  "New" to "this" Block.
 488   BranchInst *BI = BranchInst::Create(this, New);
 489   BI->setDebugLoc(Loc);
 490
 491   return New;
 492 }
 493
 494 void BasicBlock::splice(BasicBlock::iterator ToIt, BasicBlock *FromBB,
 495                         BasicBlock::iterator FromBeginIt,
 496                         BasicBlock::iterator FromEndIt) {
 497 #ifdef EXPENSIVE_CHECKS
 498   // Check that FromBeginIt is befor FromEndIt.
 499   auto FromBBEnd = FromBB->end();
 500   for (auto It = FromBeginIt; It != FromEndIt; ++It)
 501     assert(It != FromBBEnd && "FromBeginIt not before FromEndIt!");
 502 #endif // EXPENSIVE_CHECKS
 503   getInstList().splice(ToIt, FromBB->getInstList(), FromBeginIt, FromEndIt);
 504 }
 505
 506 BasicBlock::iterator BasicBlock::erase(BasicBlock::iterator FromIt,
 507                                        BasicBlock::iterator ToIt) {
 508   return InstList.erase(FromIt, ToIt);
 509 }
 510
 511 void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) {
 512   // N.B. This might not be a complete BasicBlock, so don't assume
 513   // that it ends with a non-phi instruction.
 514   for (Instruction &I : *this) {
 515     PHINode *PN = dyn_cast<PHINode>(&I);
 516     if (!PN)
 517       break;
 518     PN->replaceIncomingBlockWith(Old, New);
 519   }
 520 }
 521
 522 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *Old,
 523                                               BasicBlock *New) {
 524   Instruction *TI = getTerminator();
 525   if (!TI)
 526     // Cope with being called on a BasicBlock that doesn't have a terminator
 527     // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
 528     return;
 529   for (BasicBlock *Succ : successors(TI))
 530     Succ->replacePhiUsesWith(Old, New);
 531 }
 532
 533 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
 534   this->replaceSuccessorsPhiUsesWith(this, New);
 535 }
 536
 537 bool BasicBlock::isLandingPad() const {
 538   return isa<LandingPadInst>(getFirstNonPHI());
 539 }
 540
 541 const LandingPadInst *BasicBlock::getLandingPadInst() const {
 542   return dyn_cast<LandingPadInst>(getFirstNonPHI());
 543 }
 544
 545 std::optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
 546   const Instruction *TI = getTerminator();
 547   if (MDNode *MDIrrLoopHeader =
 548       TI->getMetadata(LLVMContext::MD_irr_loop)) {
 549     MDString *MDName = cast<MDString>(MDIrrLoopHeader->getOperand(0));
 550     if (MDName->getString().equals("loop_header_weight")) {
 551       auto *CI = mdconst::extract<ConstantInt>(MDIrrLoopHeader->getOperand(1));
 552       return std::optional<uint64_t>(CI->getValue().getZExtValue());
 553     }
 554   }
 555   return std::nullopt;
 556 }
 557
 558 BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
 559   while (isa<DbgInfoIntrinsic>(It))
 560     ++It;
 561   return It;
 562 }
 563
 564 void BasicBlock::renumberInstructions() {
 565   unsigned Order = 0;
 566   for (Instruction &I : *this)
 567     I.Order = Order++;
 568
 569   // Set the bit to indicate that the instruction order valid and cached.
 570   BasicBlockBits Bits = getBasicBlockBits();
 571   Bits.InstrOrderValid = true;
 572   setBasicBlockBits(Bits);
 573
 574   NumInstrRenumberings++;
 575 }
 576
 577 #ifndef NDEBUG
 578 /// In asserts builds, this checks the numbering. In non-asserts builds, it
 579 /// is defined as a no-op inline function in BasicBlock.h.
 580 void BasicBlock::validateInstrOrdering() const {
 581   if (!isInstrOrderValid())
 582     return;
 583   const Instruction *Prev = nullptr;
 584   for (const Instruction &I : *this) {
 585     assert((!Prev || Prev->comesBefore(&I)) &&
 586            "cached instruction ordering is incorrect");
 587     Prev = &I;
 588   }
 589 }
 590 #endif