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