LCOV - code coverage report
Current view: top level - lib/IR - BasicBlock.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 155 157 98.7 %
Date: 2018-06-17 00:07:59 Functions: 36 36 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     6993874 : ValueSymbolTable *BasicBlock::getValueSymbolTable() {
      28     6993874 :   if (Function *F = getParent())
      29     3297836 :     return F->getValueSymbolTable();
      30             :   return nullptr;
      31             : }
      32             : 
      33     2999814 : LLVMContext &BasicBlock::getContext() const {
      34     2999814 :   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     1328642 : BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
      42     1328642 :                        BasicBlock *InsertBefore)
      43     2657284 :   : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
      44             : 
      45     1328642 :   if (NewParent)
      46      638558 :     insertInto(NewParent, InsertBefore);
      47             :   else
      48             :     assert(!InsertBefore &&
      49             :            "Cannot insert block before another block with no function!");
      50             : 
      51     1328642 :   setName(Name);
      52     1328642 : }
      53             : 
      54      638628 : void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
      55             :   assert(NewParent && "Expected a parent");
      56             :   assert(!Parent && "Already has a parent");
      57             : 
      58      638628 :   if (InsertBefore)
      59       69515 :     NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
      60             :   else
      61      569113 :     NewParent->getBasicBlockList().push_back(this);
      62      638628 : }
      63             : 
      64     2222392 : 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     1111196 :   if (hasAddressTaken()) {
      72             :     assert(!use_empty() && "There should be at least one blockaddress!");
      73             :     Constant *Replacement =
      74         806 :       ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
      75        2418 :     while (!use_empty()) {
      76             :       BlockAddress *BA = cast<BlockAddress>(user_back());
      77         806 :       BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
      78             :                                                        BA->getType()));
      79         806 :       BA->destroyConstant();
      80             :     }
      81             :   }
      82             : 
      83             :   assert(getParent() == nullptr && "BasicBlock still linked into the program!");
      84     1111196 :   dropAllReferences();
      85     1111196 :   InstList.clear();
      86     1111196 : }
      87             : 
      88     2090650 : void BasicBlock::setParent(Function *parent) {
      89             :   // Set Parent=parent, updating instruction symtab entries as appropriate.
      90     2090650 :   InstList.setSymTabObject(&Parent, parent);
      91     2090650 : }
      92             : 
      93             : iterator_range<filter_iterator<BasicBlock::const_iterator,
      94             :                                std::function<bool(const Instruction &)>>>
      95           3 : BasicBlock::instructionsWithoutDebug() const {
      96          15 :   std::function<bool(const Instruction &)> Fn = [](const Instruction &I) {
      97             :     return !isa<DbgInfoIntrinsic>(I);
      98          15 :   };
      99           9 :   return make_filter_range(*this, Fn);
     100             : }
     101             : 
     102             : iterator_range<filter_iterator<BasicBlock::iterator,
     103             :                                std::function<bool(Instruction &)>>>
     104      374408 : BasicBlock::instructionsWithoutDebug() {
     105      723821 :   std::function<bool(Instruction &)> Fn = [](Instruction &I) {
     106             :     return !isa<DbgInfoIntrinsic>(I);
     107      723821 :   };
     108     1123224 :   return make_filter_range(*this, Fn);
     109             : }
     110             : 
     111           1 : void BasicBlock::removeFromParent() {
     112           1 :   getParent()->getBasicBlockList().remove(getIterator());
     113           1 : }
     114             : 
     115      829904 : iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
     116      829904 :   return getParent()->getBasicBlockList().erase(getIterator());
     117             : }
     118             : 
     119             : /// Unlink this basic block from its current function and
     120             : /// insert it into the function that MovePos lives in, right before MovePos.
     121        1727 : void BasicBlock::moveBefore(BasicBlock *MovePos) {
     122        3454 :   MovePos->getParent()->getBasicBlockList().splice(
     123        1727 :       MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
     124        1727 : }
     125             : 
     126             : /// Unlink this basic block from its current function and
     127             : /// insert it into the function that MovePos lives in, right after MovePos.
     128        4797 : void BasicBlock::moveAfter(BasicBlock *MovePos) {
     129        9594 :   MovePos->getParent()->getBasicBlockList().splice(
     130        9594 :       ++MovePos->getIterator(), getParent()->getBasicBlockList(),
     131             :       getIterator());
     132        4797 : }
     133             : 
     134    44336358 : const Module *BasicBlock::getModule() const {
     135    44336358 :   return getParent()->getParent();
     136             : }
     137             : 
     138   130668170 : const TerminatorInst *BasicBlock::getTerminator() const {
     139   130668170 :   if (InstList.empty()) return nullptr;
     140             :   return dyn_cast<TerminatorInst>(&InstList.back());
     141             : }
     142             : 
     143      242534 : const CallInst *BasicBlock::getTerminatingMustTailCall() const {
     144      242534 :   if (InstList.empty())
     145             :     return nullptr;
     146             :   const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
     147       49050 :   if (!RI || RI == &InstList.front())
     148             :     return nullptr;
     149             : 
     150             :   const Instruction *Prev = RI->getPrevNode();
     151       44836 :   if (!Prev)
     152             :     return nullptr;
     153             : 
     154             :   if (Value *RV = RI->getReturnValue()) {
     155       21007 :     if (RV != Prev)
     156             :       return nullptr;
     157             : 
     158             :     // Look through the optional bitcast.
     159             :     if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
     160             :       RV = BI->getOperand(0);
     161             :       Prev = BI->getPrevNode();
     162        1626 :       if (!Prev || RV != Prev)
     163             :         return nullptr;
     164             :     }
     165             :   }
     166             : 
     167             :   if (auto *CI = dyn_cast<CallInst>(Prev)) {
     168       22965 :     if (CI->isMustTailCall())
     169             :       return CI;
     170             :   }
     171             :   return nullptr;
     172             : }
     173             : 
     174      830583 : const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
     175      830583 :   if (InstList.empty())
     176             :     return nullptr;
     177             :   auto *RI = dyn_cast<ReturnInst>(&InstList.back());
     178      813679 :   if (!RI || RI == &InstList.front())
     179             :     return nullptr;
     180             : 
     181             :   if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
     182             :     if (Function *F = CI->getCalledFunction())
     183      151952 :       if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
     184             :         return CI;
     185             : 
     186             :   return nullptr;
     187             : }
     188             : 
     189     2953943 : const Instruction* BasicBlock::getFirstNonPHI() const {
     190     3491005 :   for (const Instruction &I : *this)
     191     3490936 :     if (!isa<PHINode>(I))
     192             :       return &I;
     193             :   return nullptr;
     194             : }
     195             : 
     196     1209623 : const Instruction* BasicBlock::getFirstNonPHIOrDbg() const {
     197     1694056 :   for (const Instruction &I : *this)
     198     1694056 :     if (!isa<PHINode>(I) && !isa<DbgInfoIntrinsic>(I))
     199             :       return &I;
     200             :   return nullptr;
     201             : }
     202             : 
     203          91 : const Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() const {
     204         109 :   for (const Instruction &I : *this) {
     205         127 :     if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
     206          18 :       continue;
     207             : 
     208             :     if (auto *II = dyn_cast<IntrinsicInst>(&I))
     209           0 :       if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
     210             :           II->getIntrinsicID() == Intrinsic::lifetime_end)
     211           0 :         continue;
     212             : 
     213             :     return &I;
     214             :   }
     215             :   return nullptr;
     216             : }
     217             : 
     218      277399 : BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
     219      277399 :   const Instruction *FirstNonPHI = getFirstNonPHI();
     220      277399 :   if (!FirstNonPHI)
     221             :     return end();
     222             : 
     223      277330 :   const_iterator InsertPt = FirstNonPHI->getIterator();
     224             :   if (InsertPt->isEHPad()) ++InsertPt;
     225      277330 :   return InsertPt;
     226             : }
     227             : 
     228     1773942 : void BasicBlock::dropAllReferences() {
     229    10950922 :   for (Instruction &I : *this)
     230     9176980 :     I.dropAllReferences();
     231     1773942 : }
     232             : 
     233             : /// If this basic block has a single predecessor block,
     234             : /// return the block, otherwise return a null pointer.
     235     6933931 : const BasicBlock *BasicBlock::getSinglePredecessor() const {
     236     6933931 :   const_pred_iterator PI = pred_begin(this), E = pred_end(this);
     237     6933931 :   if (PI == E) return nullptr;         // No preds.
     238             :   const BasicBlock *ThePred = *PI;
     239             :   ++PI;
     240     6030134 :   return (PI == E) ? ThePred : nullptr /*multiple preds*/;
     241             : }
     242             : 
     243             : /// If this basic block has a unique predecessor block,
     244             : /// return the block, otherwise return a null pointer.
     245             : /// Note that unique predecessor doesn't mean single edge, there can be
     246             : /// multiple edges from the unique predecessor to this block (for example
     247             : /// a switch statement with multiple cases having the same destination).
     248     2073120 : const BasicBlock *BasicBlock::getUniquePredecessor() const {
     249     2073120 :   const_pred_iterator PI = pred_begin(this), E = pred_end(this);
     250     2073120 :   if (PI == E) return nullptr; // No preds.
     251             :   const BasicBlock *PredBB = *PI;
     252             :   ++PI;
     253     1743805 :   for (;PI != E; ++PI) {
     254      535695 :     if (*PI != PredBB)
     255             :       return nullptr;
     256             :     // The same predecessor appears multiple times in the predecessor list.
     257             :     // This is OK.
     258             :   }
     259             :   return PredBB;
     260             : }
     261             : 
     262      645159 : const BasicBlock *BasicBlock::getSingleSuccessor() const {
     263      645159 :   succ_const_iterator SI = succ_begin(this), E = succ_end(this);
     264      645159 :   if (SI == E) return nullptr; // no successors
     265             :   const BasicBlock *TheSucc = *SI;
     266             :   ++SI;
     267      589362 :   return (SI == E) ? TheSucc : nullptr /* multiple successors */;
     268             : }
     269             : 
     270        2300 : const BasicBlock *BasicBlock::getUniqueSuccessor() const {
     271        2300 :   succ_const_iterator SI = succ_begin(this), E = succ_end(this);
     272        2300 :   if (SI == E) return nullptr; // No successors
     273             :   const BasicBlock *SuccBB = *SI;
     274             :   ++SI;
     275        2299 :   for (;SI != E; ++SI) {
     276          18 :     if (*SI != SuccBB)
     277             :       return nullptr;
     278             :     // The same successor appears multiple times in the successor list.
     279             :     // This is OK.
     280             :   }
     281             :   return SuccBB;
     282             : }
     283             : 
     284     3126457 : iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
     285     3126457 :   PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(&*begin());
     286     3126457 :   return make_range<phi_iterator>(P, nullptr);
     287             : }
     288             : 
     289             : /// This method is used to notify a BasicBlock that the
     290             : /// specified Predecessor of the block is no longer able to reach it.  This is
     291             : /// actually not used to update the Predecessor list, but is actually used to
     292             : /// update the PHI nodes that reside in the block.  Note that this should be
     293             : /// called while the predecessor still refers to this block.
     294             : ///
     295       42537 : void BasicBlock::removePredecessor(BasicBlock *Pred,
     296             :                                    bool DontDeleteUselessPHIs) {
     297             :   assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
     298             :           find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
     299             :          "removePredecessor: BB is not a predecessor!");
     300             : 
     301       42537 :   if (InstList.empty()) return;
     302             :   PHINode *APN = dyn_cast<PHINode>(&front());
     303             :   if (!APN) return;   // Quick exit.
     304             : 
     305             :   // If there are exactly two predecessors, then we want to nuke the PHI nodes
     306             :   // altogether.  However, we cannot do this, if this in this case:
     307             :   //
     308             :   //  Loop:
     309             :   //    %x = phi [X, Loop]
     310             :   //    %x2 = add %x, 1         ;; This would become %x2 = add %x2, 1
     311             :   //    br Loop                 ;; %x2 does not dominate all uses
     312             :   //
     313             :   // This is because the PHI node input is actually taken from the predecessor
     314             :   // basic block.  The only case this can happen is with a self loop, so we
     315             :   // check for this case explicitly now.
     316             :   //
     317             :   unsigned max_idx = APN->getNumIncomingValues();
     318             :   assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
     319        5556 :   if (max_idx == 2) {
     320        3905 :     BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred);
     321             : 
     322             :     // Disable PHI elimination!
     323        3905 :     if (this == Other) max_idx = 3;
     324             :   }
     325             : 
     326             :   // <= Two predecessors BEFORE I remove one?
     327        5556 :   if (max_idx <= 2 && !DontDeleteUselessPHIs) {
     328             :     // Yup, loop through and nuke the PHI nodes
     329             :     while (PHINode *PN = dyn_cast<PHINode>(&front())) {
     330             :       // Remove the predecessor first.
     331        3130 :       PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs);
     332             : 
     333             :       // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
     334        3130 :       if (max_idx == 2) {
     335        3125 :         if (PN->getIncomingValue(0) != PN)
     336        6240 :           PN->replaceAllUsesWith(PN->getIncomingValue(0));
     337             :         else
     338             :           // We are left with an infinite loop with no entries: kill the PHI.
     339           5 :           PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
     340        3125 :         getInstList().pop_front();    // Remove the PHI node
     341             :       }
     342             : 
     343             :       // If the PHI node already only had one entry, it got deleted by
     344             :       // removeIncomingValue.
     345             :     }
     346             :   } else {
     347             :     // Okay, now we know that we need to remove predecessor #pred_idx from all
     348             :     // PHI nodes.  Iterate over each PHI node fixing them up
     349             :     PHINode *PN;
     350             :     for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
     351             :       ++II;
     352        4962 :       PN->removeIncomingValue(Pred, false);
     353             :       // If all incoming values to the Phi are the same, we can replace the Phi
     354             :       // with that value.
     355             :       Value* PNV = nullptr;
     356        4962 :       if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue()))
     357         258 :         if (PNV != PN) {
     358         258 :           PN->replaceAllUsesWith(PNV);
     359         258 :           PN->eraseFromParent();
     360             :         }
     361             :     }
     362             :   }
     363             : }
     364             : 
     365       17538 : bool BasicBlock::canSplitPredecessors() const {
     366       17538 :   const Instruction *FirstNonPHI = getFirstNonPHI();
     367       17538 :   if (isa<LandingPadInst>(FirstNonPHI))
     368             :     return true;
     369             :   // This is perhaps a little conservative because constructs like
     370             :   // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
     371             :   // cannot handle such things just yet.
     372             :   if (FirstNonPHI->isEHPad())
     373             :     return false;
     374             :   return true;
     375             : }
     376             : 
     377      244565 : bool BasicBlock::isLegalToHoistInto() const {
     378      244565 :   auto *Term = getTerminator();
     379             :   // No terminator means the block is under construction.
     380      244565 :   if (!Term)
     381             :     return true;
     382             : 
     383             :   // If the block has no successors, there can be no instructions to hoist.
     384             :   assert(Term->getNumSuccessors() > 0);
     385             : 
     386             :   // Instructions should not be hoisted across exception handling boundaries.
     387      244565 :   return !Term->isExceptional();
     388             : }
     389             : 
     390             : /// This splits a basic block into two at the specified
     391             : /// instruction.  Note that all instructions BEFORE the specified iterator stay
     392             : /// as part of the original basic block, an unconditional branch is added to
     393             : /// the new BB, and the rest of the instructions in the BB are moved to the new
     394             : /// BB, including the old terminator.  This invalidates the iterator.
     395             : ///
     396             : /// Note that this only works on well formed basic blocks (must have a
     397             : /// terminator), and 'I' must not be the end of instruction list (which would
     398             : /// cause a degenerate basic block to be formed, having a terminator inside of
     399             : /// the basic block).
     400             : ///
     401       68989 : BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
     402             :   assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
     403             :   assert(I != InstList.end() &&
     404             :          "Trying to get me to create degenerate basic block!");
     405             : 
     406       68989 :   BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
     407             :                                        this->getNextNode());
     408             : 
     409             :   // Save DebugLoc of split point before invalidating iterator.
     410             :   DebugLoc Loc = I->getDebugLoc();
     411             :   // Move all of the specified instructions from the original basic block into
     412             :   // the new basic block.
     413      137978 :   New->getInstList().splice(New->end(), this->getInstList(), I, end());
     414             : 
     415             :   // Add a branch instruction to the newly formed basic block.
     416             :   BranchInst *BI = BranchInst::Create(New, this);
     417       68989 :   BI->setDebugLoc(Loc);
     418             : 
     419             :   // Now we must loop through all of the successors of the New block (which
     420             :   // _were_ the successors of the 'this' block), and update any PHI nodes in
     421             :   // successors.  If there were PHI nodes in the successors, then they need to
     422             :   // know that incoming branches will be from New, not from Old.
     423             :   //
     424      204976 :   for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) {
     425             :     // Loop over any phi nodes in the basic block, updating the BB field of
     426             :     // incoming values...
     427             :     BasicBlock *Successor = *I;
     428       66998 :     for (auto &PN : Successor->phis()) {
     429       15976 :       int Idx = PN.getBasicBlockIndex(this);
     430       47648 :       while (Idx != -1) {
     431       15836 :         PN.setIncomingBlock((unsigned)Idx, New);
     432       15836 :         Idx = PN.getBasicBlockIndex(this);
     433             :       }
     434             :     }
     435             :   }
     436       68989 :   return New;
     437             : }
     438             : 
     439      282181 : void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
     440             :   TerminatorInst *TI = getTerminator();
     441      282181 :   if (!TI)
     442             :     // Cope with being called on a BasicBlock that doesn't have a terminator
     443             :     // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
     444             :     return;
     445      364840 :   for (BasicBlock *Succ : TI->successors()) {
     446             :     // N.B. Succ might not be a complete BasicBlock, so don't assume
     447             :     // that it ends with a non-phi instruction.
     448      205326 :     for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) {
     449             :       PHINode *PN = dyn_cast<PHINode>(II);
     450             :       if (!PN)
     451             :         break;
     452             :       int i;
     453       38630 :       while ((i = PN->getBasicBlockIndex(this)) >= 0)
     454       12715 :         PN->setIncomingBlock(i, New);
     455             :     }
     456             :   }
     457             : }
     458             : 
     459             : /// Return true if this basic block is a landing pad. I.e., it's
     460             : /// the destination of the 'unwind' edge of an invoke instruction.
     461       47119 : bool BasicBlock::isLandingPad() const {
     462       94238 :   return isa<LandingPadInst>(getFirstNonPHI());
     463             : }
     464             : 
     465             : /// Return the landingpad instruction associated with the landing pad.
     466      404881 : const LandingPadInst *BasicBlock::getLandingPadInst() const {
     467      809762 :   return dyn_cast<LandingPadInst>(getFirstNonPHI());
     468             : }
     469             : 
     470      447195 : Optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
     471      447195 :   const TerminatorInst *TI = getTerminator();
     472      210167 :   if (MDNode *MDIrrLoopHeader =
     473      447195 :       TI->getMetadata(LLVMContext::MD_irr_loop)) {
     474             :     MDString *MDName = cast<MDString>(MDIrrLoopHeader->getOperand(0));
     475          32 :     if (MDName->getString().equals("loop_header_weight")) {
     476             :       auto *CI = mdconst::extract<ConstantInt>(MDIrrLoopHeader->getOperand(1));
     477             :       return Optional<uint64_t>(CI->getValue().getZExtValue());
     478             :     }
     479             :   }
     480             :   return Optional<uint64_t>();
     481             : }

Generated by: LCOV version 1.13