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

Generated by: LCOV version 1.13