contrib/llvm-project/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() const {
 101   std::function<bool(const Instruction &)> Fn = [](const Instruction &I) {
 102     return !isa<DbgInfoIntrinsic>(I);
 103   };
 104   return make_filter_range(*this, Fn);
 105 }
 106
 107 iterator_range<filter_iterator<BasicBlock::iterator,
 108                                std::function<bool(Instruction &)>>>
 109 BasicBlock::instructionsWithoutDebug() {
 110   std::function<bool(Instruction &)> Fn = [](Instruction &I) {
 111     return !isa<DbgInfoIntrinsic>(I);
 112   };
 113   return make_filter_range(*this, Fn);
 114 }
 115
 116 filter_iterator<BasicBlock::const_iterator,
 117                 std::function<bool(const Instruction &)>>::difference_type
 118 BasicBlock::sizeWithoutDebug() const {
 119   return std::distance(instructionsWithoutDebug().begin(),
 120                        instructionsWithoutDebug().end());
 121 }
 122
 123 void BasicBlock::removeFromParent() {
 124   getParent()->getBasicBlockList().remove(getIterator());
 125 }
 126
 127 iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
 128   return getParent()->getBasicBlockList().erase(getIterator());
 129 }
 130
 131 /// Unlink this basic block from its current function and
 132 /// insert it into the function that MovePos lives in, right before MovePos.
 133 void BasicBlock::moveBefore(BasicBlock *MovePos) {
 134   MovePos->getParent()->getBasicBlockList().splice(
 135       MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
 136 }
 137
 138 /// Unlink this basic block from its current function and
 139 /// insert it into the function that MovePos lives in, right after MovePos.
 140 void BasicBlock::moveAfter(BasicBlock *MovePos) {
 141   MovePos->getParent()->getBasicBlockList().splice(
 142       ++MovePos->getIterator(), getParent()->getBasicBlockList(),
 143       getIterator());
 144 }
 145
 146 const Module *BasicBlock::getModule() const {
 147   return getParent()->getParent();
 148 }
 149
 150 const Instruction *BasicBlock::getTerminator() const {
 151   if (InstList.empty() || !InstList.back().isTerminator())
 152     return nullptr;
 153   return &InstList.back();
 154 }
 155
 156 const CallInst *BasicBlock::getTerminatingMustTailCall() const {
 157   if (InstList.empty())
 158     return nullptr;
 159   const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
 160   if (!RI || RI == &InstList.front())
 161     return nullptr;
 162
 163   const Instruction *Prev = RI->getPrevNode();
 164   if (!Prev)
 165     return nullptr;
 166
 167   if (Value *RV = RI->getReturnValue()) {
 168     if (RV != Prev)
 169       return nullptr;
 170
 171     // Look through the optional bitcast.
 172     if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
 173       RV = BI->getOperand(0);
 174       Prev = BI->getPrevNode();
 175       if (!Prev || RV != Prev)
 176         return nullptr;
 177     }
 178   }
 179
 180   if (auto *CI = dyn_cast<CallInst>(Prev)) {
 181     if (CI->isMustTailCall())
 182       return CI;
 183   }
 184   return nullptr;
 185 }
 186
 187 const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
 188   if (InstList.empty())
 189     return nullptr;
 190   auto *RI = dyn_cast<ReturnInst>(&InstList.back());
 191   if (!RI || RI == &InstList.front())
 192     return nullptr;
 193
 194   if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
 195     if (Function *F = CI->getCalledFunction())
 196       if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
 197         return CI;
 198
 199   return nullptr;
 200 }
 201
 202 const CallInst *BasicBlock::getPostdominatingDeoptimizeCall() const {
 203   const BasicBlock* BB = this;
 204   SmallPtrSet<const BasicBlock *, 8> Visited;
 205   Visited.insert(BB);
 206   while (auto *Succ = BB->getUniqueSuccessor()) {
 207     if (!Visited.insert(Succ).second)
 208       return nullptr;
 209     BB = Succ;
 210   }
 211   return BB->getTerminatingDeoptimizeCall();
 212 }
 213
 214 const Instruction* BasicBlock::getFirstNonPHI() const {
 215   for (const Instruction &I : *this)
 216     if (!isa<PHINode>(I))
 217       return &I;
 218   return nullptr;
 219 }
 220
 221 const Instruction* BasicBlock::getFirstNonPHIOrDbg() const {
 222   for (const Instruction &I : *this)
 223     if (!isa<PHINode>(I) && !isa<DbgInfoIntrinsic>(I))
 224       return &I;
 225   return nullptr;
 226 }
 227
 228 const Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() const {
 229   for (const Instruction &I : *this) {
 230     if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
 231       continue;
 232
 233     if (I.isLifetimeStartOrEnd())
 234       continue;
 235
 236     return &I;
 237   }
 238   return nullptr;
 239 }
 240
 241 BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
 242   const Instruction *FirstNonPHI = getFirstNonPHI();
 243   if (!FirstNonPHI)
 244     return end();
 245
 246   const_iterator InsertPt = FirstNonPHI->getIterator();
 247   if (InsertPt->isEHPad()) ++InsertPt;
 248   return InsertPt;
 249 }
 250
 251 void BasicBlock::dropAllReferences() {
 252   for (Instruction &I : *this)
 253     I.dropAllReferences();
 254 }
 255
 256 /// If this basic block has a single predecessor block,
 257 /// return the block, otherwise return a null pointer.
 258 const BasicBlock *BasicBlock::getSinglePredecessor() const {
 259   const_pred_iterator PI = pred_begin(this), E = pred_end(this);
 260   if (PI == E) return nullptr;         // No preds.
 261   const BasicBlock *ThePred = *PI;
 262   ++PI;
 263   return (PI == E) ? ThePred : nullptr /*multiple preds*/;
 264 }
 265
 266 /// If this basic block has a unique predecessor block,
 267 /// return the block, otherwise return a null pointer.
 268 /// Note that unique predecessor doesn't mean single edge, there can be
 269 /// multiple edges from the unique predecessor to this block (for example
 270 /// a switch statement with multiple cases having the same destination).
 271 const BasicBlock *BasicBlock::getUniquePredecessor() const {
 272   const_pred_iterator PI = pred_begin(this), E = pred_end(this);
 273   if (PI == E) return nullptr; // No preds.
 274   const BasicBlock *PredBB = *PI;
 275   ++PI;
 276   for (;PI != E; ++PI) {
 277     if (*PI != PredBB)
 278       return nullptr;
 279     // The same predecessor appears multiple times in the predecessor list.
 280     // This is OK.
 281   }
 282   return PredBB;
 283 }
 284
 285 bool BasicBlock::hasNPredecessors(unsigned N) const {
 286   return hasNItems(pred_begin(this), pred_end(this), N);
 287 }
 288
 289 bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const {
 290   return hasNItemsOrMore(pred_begin(this), pred_end(this), N);
 291 }
 292
 293 const BasicBlock *BasicBlock::getSingleSuccessor() const {
 294   const_succ_iterator SI = succ_begin(this), E = succ_end(this);
 295   if (SI == E) return nullptr; // no successors
 296   const BasicBlock *TheSucc = *SI;
 297   ++SI;
 298   return (SI == E) ? TheSucc : nullptr /* multiple successors */;
 299 }
 300
 301 const BasicBlock *BasicBlock::getUniqueSuccessor() const {
 302   const_succ_iterator SI = succ_begin(this), E = succ_end(this);
 303   if (SI == E) return nullptr; // No successors
 304   const BasicBlock *SuccBB = *SI;
 305   ++SI;
 306   for (;SI != E; ++SI) {
 307     if (*SI != SuccBB)
 308       return nullptr;
 309     // The same successor appears multiple times in the successor list.
 310     // This is OK.
 311   }
 312   return SuccBB;
 313 }
 314
 315 iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
 316   PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(&*begin());
 317   return make_range<phi_iterator>(P, nullptr);
 318 }
 319
 320 /// Update PHI nodes in this BasicBlock before removal of predecessor \p Pred.
 321 /// Note that this function does not actually remove the predecessor.
 322 ///
 323 /// If \p KeepOneInputPHIs is true then don't remove PHIs that are left with
 324 /// zero or one incoming values, and don't simplify PHIs with all incoming
 325 /// values the same.
 326 void BasicBlock::removePredecessor(BasicBlock *Pred,
 327                                    bool KeepOneInputPHIs) {
 328   // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs.
 329   assert((hasNUsesOrMore(16) ||
 330           find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
 331          "Pred is not a predecessor!");
 332
 333   // Return early if there are no PHI nodes to update.
 334   if (!isa<PHINode>(begin()))
 335     return;
 336   unsigned NumPreds = cast<PHINode>(front()).getNumIncomingValues();
 337
 338   // Update all PHI nodes.
 339   for (iterator II = begin(); isa<PHINode>(II);) {
 340     PHINode *PN = cast<PHINode>(II++);
 341     PN->removeIncomingValue(Pred, !KeepOneInputPHIs);
 342     if (!KeepOneInputPHIs) {
 343       // If we have a single predecessor, removeIncomingValue erased the PHI
 344       // node itself.
 345       if (NumPreds > 1) {
 346         if (Value *PNV = PN->hasConstantValue()) {
 347           // Replace the PHI node with its constant value.
 348           PN->replaceAllUsesWith(PNV);
 349           PN->eraseFromParent();
 350         }
 351       }
 352     }
 353   }
 354 }
 355
 356 bool BasicBlock::canSplitPredecessors() const {
 357   const Instruction *FirstNonPHI = getFirstNonPHI();
 358   if (isa<LandingPadInst>(FirstNonPHI))
 359     return true;
 360   // This is perhaps a little conservative because constructs like
 361   // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
 362   // cannot handle such things just yet.
 363   if (FirstNonPHI->isEHPad())
 364     return false;
 365   return true;
 366 }
 367
 368 bool BasicBlock::isLegalToHoistInto() const {
 369   auto *Term = getTerminator();
 370   // No terminator means the block is under construction.
 371   if (!Term)
 372     return true;
 373
 374   // If the block has no successors, there can be no instructions to hoist.
 375   assert(Term->getNumSuccessors() > 0);
 376
 377   // Instructions should not be hoisted across exception handling boundaries.
 378   return !Term->isExceptionalTerminator();
 379 }
 380
 381 /// This splits a basic block into two at the specified
 382 /// instruction.  Note that all instructions BEFORE the specified iterator stay
 383 /// as part of the original basic block, an unconditional branch is added to
 384 /// the new BB, and the rest of the instructions in the BB are moved to the new
 385 /// BB, including the old terminator.  This invalidates the iterator.
 386 ///
 387 /// Note that this only works on well formed basic blocks (must have a
 388 /// terminator), and 'I' must not be the end of instruction list (which would
 389 /// cause a degenerate basic block to be formed, having a terminator inside of
 390 /// the basic block).
 391 ///
 392 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
 393   assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
 394   assert(I != InstList.end() &&
 395          "Trying to get me to create degenerate basic block!");
 396
 397   BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
 398                                        this->getNextNode());
 399
 400   // Save DebugLoc of split point before invalidating iterator.
 401   DebugLoc Loc = I->getDebugLoc();
 402   // Move all of the specified instructions from the original basic block into
 403   // the new basic block.
 404   New->getInstList().splice(New->end(), this->getInstList(), I, end());
 405
 406   // Add a branch instruction to the newly formed basic block.
 407   BranchInst *BI = BranchInst::Create(New, this);
 408   BI->setDebugLoc(Loc);
 409
 410   // Now we must loop through all of the successors of the New block (which
 411   // _were_ the successors of the 'this' block), and update any PHI nodes in
 412   // successors.  If there were PHI nodes in the successors, then they need to
 413   // know that incoming branches will be from New, not from Old (this).
 414   //
 415   New->replaceSuccessorsPhiUsesWith(this, New);
 416   return New;
 417 }
 418
 419 void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) {
 420   // N.B. This might not be a complete BasicBlock, so don't assume
 421   // that it ends with a non-phi instruction.
 422   for (iterator II = begin(), IE = end(); II != IE; ++II) {
 423     PHINode *PN = dyn_cast<PHINode>(II);
 424     if (!PN)
 425       break;
 426     PN->replaceIncomingBlockWith(Old, New);
 427   }
 428 }
 429
 430 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *Old,
 431                                               BasicBlock *New) {
 432   Instruction *TI = getTerminator();
 433   if (!TI)
 434     // Cope with being called on a BasicBlock that doesn't have a terminator
 435     // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
 436     return;
 437   llvm::for_each(successors(TI), [Old, New](BasicBlock *Succ) {
 438     Succ->replacePhiUsesWith(Old, New);
 439   });
 440 }
 441
 442 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
 443   this->replaceSuccessorsPhiUsesWith(this, New);
 444 }
 445
 446 /// Return true if this basic block is a landing pad. I.e., it's
 447 /// the destination of the 'unwind' edge of an invoke instruction.
 448 bool BasicBlock::isLandingPad() const {
 449   return isa<LandingPadInst>(getFirstNonPHI());
 450 }
 451
 452 /// Return the landingpad instruction associated with the landing pad.
 453 const LandingPadInst *BasicBlock::getLandingPadInst() const {
 454   return dyn_cast<LandingPadInst>(getFirstNonPHI());
 455 }
 456
 457 Optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
 458   const Instruction *TI = getTerminator();
 459   if (MDNode *MDIrrLoopHeader =
 460       TI->getMetadata(LLVMContext::MD_irr_loop)) {
 461     MDString *MDName = cast<MDString>(MDIrrLoopHeader->getOperand(0));
 462     if (MDName->getString().equals("loop_header_weight")) {
 463       auto *CI = mdconst::extract<ConstantInt>(MDIrrLoopHeader->getOperand(1));
 464       return Optional<uint64_t>(CI->getValue().getZExtValue());
 465     }
 466   }
 467   return Optional<uint64_t>();
 468 }
 469
 470 BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
 471   while (isa<DbgInfoIntrinsic>(It))
 472     ++It;
 473   return It;
 474 }
 475
 476 void BasicBlock::renumberInstructions() {
 477   unsigned Order = 0;
 478   for (Instruction &I : *this)
 479     I.Order = Order++;
 480
 481   // Set the bit to indicate that the instruction order valid and cached.
 482   BasicBlockBits Bits = getBasicBlockBits();
 483   Bits.InstrOrderValid = true;
 484   setBasicBlockBits(Bits);
 485 }
 486
 487 #ifndef NDEBUG
 488 /// In asserts builds, this checks the numbering. In non-asserts builds, it
 489 /// is defined as a no-op inline function in BasicBlock.h.
 490 void BasicBlock::validateInstrOrdering() const {
 491   if (!isInstrOrderValid())
 492     return;
 493   const Instruction *Prev = nullptr;
 494   for (const Instruction &I : *this) {
 495     assert((!Prev || Prev->comesBefore(&I)) &&
 496            "cached instruction ordering is incorrect");
 497     Prev = &I;
 498   }
 499 }
 500 #endif