LCOV - code coverage report
Current view: top level - lib/IR - BasicBlock.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 172 176 97.7 %
Date: 2017-09-14 15:23:50 Functions: 31 31 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements the BasicBlock class for the IR library.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/IR/BasicBlock.h"
      15             : #include "SymbolTableListTraitsImpl.h"
      16             : #include "llvm/ADT/STLExtras.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             : #include <algorithm>
      24             : 
      25             : using namespace llvm;
      26             : 
      27     5247897 : ValueSymbolTable *BasicBlock::getValueSymbolTable() {
      28     5247897 :   if (Function *F = getParent())
      29     2606090 :     return F->getValueSymbolTable();
      30             :   return nullptr;
      31             : }
      32             : 
      33     2561866 : LLVMContext &BasicBlock::getContext() const {
      34     2561866 :   return getType()->getContext();
      35             : }
      36             : 
      37             : // Explicit instantiation of SymbolTableListTraits since some of the methods
      38             : // are not in the public header file...
      39             : template class llvm::SymbolTableListTraits<Instruction>;
      40             : 
      41      920060 : BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
      42      920060 :                        BasicBlock *InsertBefore)
      43     2760180 :   : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
      44             : 
      45      920060 :   if (NewParent)
      46      467385 :     insertInto(NewParent, InsertBefore);
      47             :   else
      48             :     assert(!InsertBefore &&
      49             :            "Cannot insert block before another block with no function!");
      50             : 
      51      920060 :   setName(Name);
      52      920060 : }
      53             : 
      54      467455 : void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
      55             :   assert(NewParent && "Expected a parent");
      56             :   assert(!Parent && "Already has a parent");
      57             : 
      58      467455 :   if (InsertBefore)
      59      118626 :     NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
      60             :   else
      61      408142 :     NewParent->getBasicBlockList().push_back(this);
      62      467455 : }
      63             : 
      64     2401673 : BasicBlock::~BasicBlock() {
      65             :   // If the address of the block is taken and it is being deleted (e.g. because
      66             :   // it is dead), this means that there is either a dangling constant expr
      67             :   // hanging off the block, or an undefined use of the block (source code
      68             :   // expecting the address of a label to keep the block alive even though there
      69             :   // is no indirect branch).  Handle these cases by zapping the BlockAddress
      70             :   // nodes.  There are no other possible uses at this point.
      71      800557 :   if (hasAddressTaken()) {
      72             :     assert(!use_empty() && "There should be at least one blockaddress!");
      73             :     Constant *Replacement =
      74         617 :       ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
      75        3085 :     while (!use_empty()) {
      76        1851 :       BlockAddress *BA = cast<BlockAddress>(user_back());
      77         617 :       BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
      78             :                                                        BA->getType()));
      79         617 :       BA->destroyConstant();
      80             :     }
      81             :   }
      82             : 
      83             :   assert(getParent() == nullptr && "BasicBlock still linked into the program!");
      84      800557 :   dropAllReferences();
      85     1601115 :   InstList.clear();
      86      800558 : }
      87             : 
      88     1518015 : void BasicBlock::setParent(Function *parent) {
      89             :   // Set Parent=parent, updating instruction symtab entries as appropriate.
      90     1518015 :   InstList.setSymTabObject(&Parent, parent);
      91     1518015 : }
      92             : 
      93           1 : void BasicBlock::removeFromParent() {
      94           3 :   getParent()->getBasicBlockList().remove(getIterator());
      95           1 : }
      96             : 
      97      599892 : iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
      98     1199784 :   return getParent()->getBasicBlockList().erase(getIterator());
      99             : }
     100             : 
     101             : /// Unlink this basic block from its current function and
     102             : /// insert it into the function that MovePos lives in, right before MovePos.
     103        1108 : void BasicBlock::moveBefore(BasicBlock *MovePos) {
     104        5540 :   MovePos->getParent()->getBasicBlockList().splice(
     105        1108 :       MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
     106        1108 : }
     107             : 
     108             : /// Unlink this basic block from its current function and
     109             : /// insert it into the function that MovePos lives in, right after MovePos.
     110        3463 : void BasicBlock::moveAfter(BasicBlock *MovePos) {
     111       13852 :   MovePos->getParent()->getBasicBlockList().splice(
     112       13852 :       ++MovePos->getIterator(), getParent()->getBasicBlockList(),
     113             :       getIterator());
     114        3463 : }
     115             : 
     116    40727832 : const Module *BasicBlock::getModule() const {
     117    40727832 :   return getParent()->getParent();
     118             : }
     119             : 
     120   107387025 : const TerminatorInst *BasicBlock::getTerminator() const {
     121   214774050 :   if (InstList.empty()) return nullptr;
     122   214615190 :   return dyn_cast<TerminatorInst>(&InstList.back());
     123             : }
     124             : 
     125          26 : const CallInst *BasicBlock::getTerminatingMustTailCall() const {
     126          52 :   if (InstList.empty())
     127             :     return nullptr;
     128          78 :   const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
     129          52 :   if (!RI || RI == &InstList.front())
     130             :     return nullptr;
     131             : 
     132          52 :   const Instruction *Prev = RI->getPrevNode();
     133          26 :   if (!Prev)
     134             :     return nullptr;
     135             : 
     136          10 :   if (Value *RV = RI->getReturnValue()) {
     137          10 :     if (RV != Prev)
     138             :       return nullptr;
     139             : 
     140             :     // Look through the optional bitcast.
     141           6 :     if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
     142          12 :       RV = BI->getOperand(0);
     143          12 :       Prev = BI->getPrevNode();
     144           6 :       if (!Prev || RV != Prev)
     145             :         return nullptr;
     146             :     }
     147             :   }
     148             : 
     149          24 :   if (auto *CI = dyn_cast<CallInst>(Prev)) {
     150          24 :     if (CI->isMustTailCall())
     151             :       return CI;
     152             :   }
     153             :   return nullptr;
     154             : }
     155             : 
     156      502244 : const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
     157     1004488 :   if (InstList.empty())
     158             :     return nullptr;
     159     1494141 :   auto *RI = dyn_cast<ReturnInst>(&InstList.back());
     160      979306 :   if (!RI || RI == &InstList.front())
     161             :     return nullptr;
     162             : 
     163     1007996 :   if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
     164       99808 :     if (Function *F = CI->getCalledFunction())
     165       99808 :       if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
     166             :         return CI;
     167             : 
     168             :   return nullptr;
     169             : }
     170             : 
     171     2115336 : const Instruction* BasicBlock::getFirstNonPHI() const {
     172     8927782 :   for (const Instruction &I : *this)
     173     2581774 :     if (!isa<PHINode>(I))
     174             :       return &I;
     175             :   return nullptr;
     176             : }
     177             : 
     178     1119836 : const Instruction* BasicBlock::getFirstNonPHIOrDbg() const {
     179     4846034 :   for (const Instruction &I : *this)
     180     1486526 :     if (!isa<PHINode>(I) && !isa<DbgInfoIntrinsic>(I))
     181             :       return &I;
     182             :   return nullptr;
     183             : }
     184             : 
     185         323 : const Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() const {
     186        2254 :   for (const Instruction &I : *this) {
     187        2247 :     if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
     188         962 :       continue;
     189             : 
     190           0 :     if (auto *II = dyn_cast<IntrinsicInst>(&I))
     191           0 :       if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
     192           0 :           II->getIntrinsicID() == Intrinsic::lifetime_end)
     193           0 :         continue;
     194             : 
     195             :     return &I;
     196             :   }
     197             :   return nullptr;
     198             : }
     199             : 
     200      243357 : BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
     201      243357 :   const Instruction *FirstNonPHI = getFirstNonPHI();
     202      243357 :   if (!FirstNonPHI)
     203             :     return end();
     204             : 
     205      486492 :   const_iterator InsertPt = FirstNonPHI->getIterator();
     206      292411 :   if (InsertPt->isEHPad()) ++InsertPt;
     207      243246 :   return InsertPt;
     208             : }
     209             : 
     210     1258847 : void BasicBlock::dropAllReferences() {
     211    10063442 :   for (Instruction &I : *this)
     212     6286901 :     I.dropAllReferences();
     213     1258847 : }
     214             : 
     215             : /// If this basic block has a single predecessor block,
     216             : /// return the block, otherwise return a null pointer.
     217     6340065 : const BasicBlock *BasicBlock::getSinglePredecessor() const {
     218    12680130 :   const_pred_iterator PI = pred_begin(this), E = pred_end(this);
     219     6340065 :   if (PI == E) return nullptr;         // No preds.
     220     5511692 :   const BasicBlock *ThePred = *PI;
     221     5511692 :   ++PI;
     222     5511692 :   return (PI == E) ? ThePred : nullptr /*multiple preds*/;
     223             : }
     224             : 
     225             : /// If this basic block has a unique predecessor block,
     226             : /// return the block, otherwise return a null pointer.
     227             : /// Note that unique predecessor doesn't mean single edge, there can be
     228             : /// multiple edges from the unique predecessor to this block (for example
     229             : /// a switch statement with multiple cases having the same destination).
     230     1946462 : const BasicBlock *BasicBlock::getUniquePredecessor() const {
     231     3892924 :   const_pred_iterator PI = pred_begin(this), E = pred_end(this);
     232     1946462 :   if (PI == E) return nullptr; // No preds.
     233     1637290 :   const BasicBlock *PredBB = *PI;
     234             :   ++PI;
     235     1638831 :   for (;PI != E; ++PI) {
     236      494809 :     if (*PI != PredBB)
     237             :       return nullptr;
     238             :     // The same predecessor appears multiple times in the predecessor list.
     239             :     // This is OK.
     240             :   }
     241             :   return PredBB;
     242             : }
     243             : 
     244      568397 : const BasicBlock *BasicBlock::getSingleSuccessor() const {
     245      568397 :   succ_const_iterator SI = succ_begin(this), E = succ_end(this);
     246      568397 :   if (SI == E) return nullptr; // no successors
     247     1032542 :   const BasicBlock *TheSucc = *SI;
     248      516271 :   ++SI;
     249      516271 :   return (SI == E) ? TheSucc : nullptr /* multiple successors */;
     250             : }
     251             : 
     252        2171 : const BasicBlock *BasicBlock::getUniqueSuccessor() const {
     253        2171 :   succ_const_iterator SI = succ_begin(this), E = succ_end(this);
     254        2171 :   if (SI == E) return nullptr; // No successors
     255        4336 :   const BasicBlock *SuccBB = *SI;
     256             :   ++SI;
     257        2170 :   for (;SI != E; ++SI) {
     258          16 :     if (*SI != SuccBB)
     259             :       return nullptr;
     260             :     // The same successor appears multiple times in the successor list.
     261             :     // This is OK.
     262             :   }
     263             :   return SuccBB;
     264             : }
     265             : 
     266       61370 : iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
     267      245480 :   return make_range<phi_iterator>(dyn_cast<PHINode>(&front()), nullptr);
     268             : }
     269             : 
     270             : /// This method is used to notify a BasicBlock that the
     271             : /// specified Predecessor of the block is no longer able to reach it.  This is
     272             : /// actually not used to update the Predecessor list, but is actually used to
     273             : /// update the PHI nodes that reside in the block.  Note that this should be
     274             : /// called while the predecessor still refers to this block.
     275             : ///
     276       37705 : void BasicBlock::removePredecessor(BasicBlock *Pred,
     277             :                                    bool DontDeleteUselessPHIs) {
     278             :   assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
     279             :           find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
     280             :          "removePredecessor: BB is not a predecessor!");
     281             : 
     282       75410 :   if (InstList.empty()) return;
     283       42361 :   PHINode *APN = dyn_cast<PHINode>(&front());
     284             :   if (!APN) return;   // Quick exit.
     285             : 
     286             :   // If there are exactly two predecessors, then we want to nuke the PHI nodes
     287             :   // altogether.  However, we cannot do this, if this in this case:
     288             :   //
     289             :   //  Loop:
     290             :   //    %x = phi [X, Loop]
     291             :   //    %x2 = add %x, 1         ;; This would become %x2 = add %x2, 1
     292             :   //    br Loop                 ;; %x2 does not dominate all uses
     293             :   //
     294             :   // This is because the PHI node input is actually taken from the predecessor
     295             :   // basic block.  The only case this can happen is with a self loop, so we
     296             :   // check for this case explicitly now.
     297             :   //
     298        4656 :   unsigned max_idx = APN->getNumIncomingValues();
     299             :   assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
     300        4656 :   if (max_idx == 2) {
     301        6624 :     BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred);
     302             : 
     303             :     // Disable PHI elimination!
     304        3312 :     if (this == Other) max_idx = 3;
     305             :   }
     306             : 
     307             :   // <= Two predecessors BEFORE I remove one?
     308        4656 :   if (max_idx <= 2 && !DontDeleteUselessPHIs) {
     309             :     // Yup, loop through and nuke the PHI nodes
     310        7219 :     while (PHINode *PN = dyn_cast<PHINode>(&front())) {
     311             :       // Remove the predecessor first.
     312        2676 :       PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs);
     313             : 
     314             :       // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
     315        2676 :       if (max_idx == 2) {
     316        2673 :         if (PN->getIncomingValue(0) != PN)
     317        5336 :           PN->replaceAllUsesWith(PN->getIncomingValue(0));
     318             :         else
     319             :           // We are left with an infinite loop with no entries: kill the PHI.
     320           5 :           PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
     321        2673 :         getInstList().pop_front();    // Remove the PHI node
     322             :       }
     323             : 
     324             :       // If the PHI node already only had one entry, it got deleted by
     325             :       // removeIncomingValue.
     326             :     }
     327             :   } else {
     328             :     // Okay, now we know that we need to remove predecessor #pred_idx from all
     329             :     // PHI nodes.  Iterate over each PHI node fixing them up
     330             :     PHINode *PN;
     331        4113 :     for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
     332        4113 :       ++II;
     333        4113 :       PN->removeIncomingValue(Pred, false);
     334             :       // If all incoming values to the Phi are the same, we can replace the Phi
     335             :       // with that value.
     336        4113 :       Value* PNV = nullptr;
     337        4113 :       if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue()))
     338         196 :         if (PNV != PN) {
     339         196 :           PN->replaceAllUsesWith(PNV);
     340         196 :           PN->eraseFromParent();
     341             :         }
     342             :     }
     343             :   }
     344             : }
     345             : 
     346       18850 : bool BasicBlock::canSplitPredecessors() const {
     347       18850 :   const Instruction *FirstNonPHI = getFirstNonPHI();
     348       37700 :   if (isa<LandingPadInst>(FirstNonPHI))
     349             :     return true;
     350             :   // This is perhaps a little conservative because constructs like
     351             :   // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
     352             :   // cannot handle such things just yet.
     353       25340 :   if (FirstNonPHI->isEHPad())
     354             :     return false;
     355             :   return true;
     356             : }
     357             : 
     358      203728 : bool BasicBlock::isLegalToHoistInto() const {
     359      203728 :   auto *Term = getTerminator();
     360             :   // No terminator means the block is under construction.
     361      203728 :   if (!Term)
     362             :     return true;
     363             : 
     364             :   // If the block has no successors, there can be no instructions to hoist.
     365             :   assert(Term->getNumSuccessors() > 0);
     366             : 
     367             :   // Instructions should not be hoisted across exception handling boundaries.
     368      203728 :   return !Term->isExceptional();
     369             : }
     370             : 
     371             : /// This splits a basic block into two at the specified
     372             : /// instruction.  Note that all instructions BEFORE the specified iterator stay
     373             : /// as part of the original basic block, an unconditional branch is added to
     374             : /// the new BB, and the rest of the instructions in the BB are moved to the new
     375             : /// BB, including the old terminator.  This invalidates the iterator.
     376             : ///
     377             : /// Note that this only works on well formed basic blocks (must have a
     378             : /// terminator), and 'I' must not be the end of instruction list (which would
     379             : /// cause a degenerate basic block to be formed, having a terminator inside of
     380             : /// the basic block).
     381             : ///
     382       61426 : BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
     383             :   assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
     384             :   assert(I != InstList.end() &&
     385             :          "Trying to get me to create degenerate basic block!");
     386             : 
     387      122852 :   BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
     388       61426 :                                        this->getNextNode());
     389             : 
     390             :   // Save DebugLoc of split point before invalidating iterator.
     391      184278 :   DebugLoc Loc = I->getDebugLoc();
     392             :   // Move all of the specified instructions from the original basic block into
     393             :   // the new basic block.
     394      245704 :   New->getInstList().splice(New->end(), this->getInstList(), I, end());
     395             : 
     396             :   // Add a branch instruction to the newly formed basic block.
     397       61426 :   BranchInst *BI = BranchInst::Create(New, this);
     398      245704 :   BI->setDebugLoc(Loc);
     399             : 
     400             :   // Now we must loop through all of the successors of the New block (which
     401             :   // _were_ the successors of the 'this' block), and update any PHI nodes in
     402             :   // successors.  If there were PHI nodes in the successors, then they need to
     403             :   // know that incoming branches will be from New, not from Old.
     404             :   //
     405      184072 :   for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) {
     406             :     // Loop over any phi nodes in the basic block, updating the BB field of
     407             :     // incoming values...
     408      122440 :     BasicBlock *Successor = *I;
     409      136909 :     for (auto &PN : Successor->phis()) {
     410       14469 :       int Idx = PN.getBasicBlockIndex(this);
     411       43165 :       while (Idx != -1) {
     412       28696 :         PN.setIncomingBlock((unsigned)Idx, New);
     413       14348 :         Idx = PN.getBasicBlockIndex(this);
     414             :       }
     415             :     }
     416             :   }
     417      122852 :   return New;
     418             : }
     419             : 
     420      212365 : void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
     421      212365 :   TerminatorInst *TI = getTerminator();
     422      212365 :   if (!TI)
     423             :     // Cope with being called on a BasicBlock that doesn't have a terminator
     424             :     // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
     425             :     return;
     426      637322 :   for (BasicBlock *Succ : TI->successors()) {
     427             :     // N.B. Succ might not be a complete BasicBlock, so don't assume
     428             :     // that it ends with a non-phi instruction.
     429      313852 :     for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) {
     430             :       PHINode *PN = dyn_cast<PHINode>(II);
     431             :       if (!PN)
     432             :         break;
     433             :       int i;
     434       30104 :       while ((i = PN->getBasicBlockIndex(this)) >= 0)
     435       10362 :         PN->setIncomingBlock(i, New);
     436             :     }
     437             :   }
     438             : }
     439             : 
     440             : /// Return true if this basic block is a landing pad. I.e., it's
     441             : /// the destination of the 'unwind' edge of an invoke instruction.
     442       35378 : bool BasicBlock::isLandingPad() const {
     443       70756 :   return isa<LandingPadInst>(getFirstNonPHI());
     444             : }
     445             : 
     446             : /// Return the landingpad instruction associated with the landing pad.
     447      262534 : const LandingPadInst *BasicBlock::getLandingPadInst() const {
     448      525068 :   return dyn_cast<LandingPadInst>(getFirstNonPHI());
     449             : }

Generated by: LCOV version 1.13