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