Home | History | Annotate | Download | only in VMCore
      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 VMCore library.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "llvm/BasicBlock.h"
     15 #include "llvm/Constants.h"
     16 #include "llvm/Instructions.h"
     17 #include "llvm/IntrinsicInst.h"
     18 #include "llvm/LLVMContext.h"
     19 #include "llvm/Type.h"
     20 #include "llvm/ADT/STLExtras.h"
     21 #include "llvm/Support/CFG.h"
     22 #include "llvm/Support/LeakDetector.h"
     23 #include "SymbolTableListTraitsImpl.h"
     24 #include <algorithm>
     25 using namespace llvm;
     26 
     27 ValueSymbolTable *BasicBlock::getValueSymbolTable() {
     28   if (Function *F = getParent())
     29     return &F->getValueSymbolTable();
     30   return 0;
     31 }
     32 
     33 LLVMContext &BasicBlock::getContext() const {
     34   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, BasicBlock>;
     40 
     41 
     42 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
     43                        BasicBlock *InsertBefore)
     44   : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(0) {
     45 
     46   // Make sure that we get added to a function
     47   LeakDetector::addGarbageObject(this);
     48 
     49   if (InsertBefore) {
     50     assert(NewParent &&
     51            "Cannot insert block before another block with no function!");
     52     NewParent->getBasicBlockList().insert(InsertBefore, this);
     53   } else if (NewParent) {
     54     NewParent->getBasicBlockList().push_back(this);
     55   }
     56 
     57   setName(Name);
     58 }
     59 
     60 
     61 BasicBlock::~BasicBlock() {
     62   // If the address of the block is taken and it is being deleted (e.g. because
     63   // it is dead), this means that there is either a dangling constant expr
     64   // hanging off the block, or an undefined use of the block (source code
     65   // expecting the address of a label to keep the block alive even though there
     66   // is no indirect branch).  Handle these cases by zapping the BlockAddress
     67   // nodes.  There are no other possible uses at this point.
     68   if (hasAddressTaken()) {
     69     assert(!use_empty() && "There should be at least one blockaddress!");
     70     Constant *Replacement =
     71       ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
     72     while (!use_empty()) {
     73       BlockAddress *BA = cast<BlockAddress>(use_back());
     74       BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
     75                                                        BA->getType()));
     76       BA->destroyConstant();
     77     }
     78   }
     79 
     80   assert(getParent() == 0 && "BasicBlock still linked into the program!");
     81   dropAllReferences();
     82   InstList.clear();
     83 }
     84 
     85 void BasicBlock::setParent(Function *parent) {
     86   if (getParent())
     87     LeakDetector::addGarbageObject(this);
     88 
     89   // Set Parent=parent, updating instruction symtab entries as appropriate.
     90   InstList.setSymTabObject(&Parent, parent);
     91 
     92   if (getParent())
     93     LeakDetector::removeGarbageObject(this);
     94 }
     95 
     96 void BasicBlock::removeFromParent() {
     97   getParent()->getBasicBlockList().remove(this);
     98 }
     99 
    100 void BasicBlock::eraseFromParent() {
    101   getParent()->getBasicBlockList().erase(this);
    102 }
    103 
    104 /// moveBefore - Unlink this basic block from its current function and
    105 /// insert it into the function that MovePos lives in, right before MovePos.
    106 void BasicBlock::moveBefore(BasicBlock *MovePos) {
    107   MovePos->getParent()->getBasicBlockList().splice(MovePos,
    108                        getParent()->getBasicBlockList(), this);
    109 }
    110 
    111 /// moveAfter - Unlink this basic block from its current function and
    112 /// insert it into the function that MovePos lives in, right after MovePos.
    113 void BasicBlock::moveAfter(BasicBlock *MovePos) {
    114   Function::iterator I = MovePos;
    115   MovePos->getParent()->getBasicBlockList().splice(++I,
    116                                        getParent()->getBasicBlockList(), this);
    117 }
    118 
    119 
    120 TerminatorInst *BasicBlock::getTerminator() {
    121   if (InstList.empty()) return 0;
    122   return dyn_cast<TerminatorInst>(&InstList.back());
    123 }
    124 
    125 const TerminatorInst *BasicBlock::getTerminator() const {
    126   if (InstList.empty()) return 0;
    127   return dyn_cast<TerminatorInst>(&InstList.back());
    128 }
    129 
    130 Instruction* BasicBlock::getFirstNonPHI() {
    131   BasicBlock::iterator i = begin();
    132   // All valid basic blocks should have a terminator,
    133   // which is not a PHINode. If we have an invalid basic
    134   // block we'll get an assertion failure when dereferencing
    135   // a past-the-end iterator.
    136   while (isa<PHINode>(i)) ++i;
    137   return &*i;
    138 }
    139 
    140 Instruction* BasicBlock::getFirstNonPHIOrDbg() {
    141   BasicBlock::iterator i = begin();
    142   // All valid basic blocks should have a terminator,
    143   // which is not a PHINode. If we have an invalid basic
    144   // block we'll get an assertion failure when dereferencing
    145   // a past-the-end iterator.
    146   while (isa<PHINode>(i) || isa<DbgInfoIntrinsic>(i)) ++i;
    147   return &*i;
    148 }
    149 
    150 Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() {
    151   // All valid basic blocks should have a terminator,
    152   // which is not a PHINode. If we have an invalid basic
    153   // block we'll get an assertion failure when dereferencing
    154   // a past-the-end iterator.
    155   BasicBlock::iterator i = begin();
    156   for (;; ++i) {
    157     if (isa<PHINode>(i) || isa<DbgInfoIntrinsic>(i))
    158       continue;
    159 
    160     const IntrinsicInst *II = dyn_cast<IntrinsicInst>(i);
    161     if (!II)
    162       break;
    163     if (II->getIntrinsicID() != Intrinsic::lifetime_start &&
    164         II->getIntrinsicID() != Intrinsic::lifetime_end)
    165       break;
    166   }
    167   return &*i;
    168 }
    169 
    170 BasicBlock::iterator BasicBlock::getFirstInsertionPt() {
    171   iterator InsertPt = getFirstNonPHI();
    172   if (isa<LandingPadInst>(InsertPt)) ++InsertPt;
    173   return InsertPt;
    174 }
    175 
    176 void BasicBlock::dropAllReferences() {
    177   for(iterator I = begin(), E = end(); I != E; ++I)
    178     I->dropAllReferences();
    179 }
    180 
    181 /// getSinglePredecessor - If this basic block has a single predecessor block,
    182 /// return the block, otherwise return a null pointer.
    183 BasicBlock *BasicBlock::getSinglePredecessor() {
    184   pred_iterator PI = pred_begin(this), E = pred_end(this);
    185   if (PI == E) return 0;         // No preds.
    186   BasicBlock *ThePred = *PI;
    187   ++PI;
    188   return (PI == E) ? ThePred : 0 /*multiple preds*/;
    189 }
    190 
    191 /// getUniquePredecessor - If this basic block has a unique predecessor block,
    192 /// return the block, otherwise return a null pointer.
    193 /// Note that unique predecessor doesn't mean single edge, there can be
    194 /// multiple edges from the unique predecessor to this block (for example
    195 /// a switch statement with multiple cases having the same destination).
    196 BasicBlock *BasicBlock::getUniquePredecessor() {
    197   pred_iterator PI = pred_begin(this), E = pred_end(this);
    198   if (PI == E) return 0; // No preds.
    199   BasicBlock *PredBB = *PI;
    200   ++PI;
    201   for (;PI != E; ++PI) {
    202     if (*PI != PredBB)
    203       return 0;
    204     // The same predecessor appears multiple times in the predecessor list.
    205     // This is OK.
    206   }
    207   return PredBB;
    208 }
    209 
    210 /// removePredecessor - This method is used to notify a BasicBlock that the
    211 /// specified Predecessor of the block is no longer able to reach it.  This is
    212 /// actually not used to update the Predecessor list, but is actually used to
    213 /// update the PHI nodes that reside in the block.  Note that this should be
    214 /// called while the predecessor still refers to this block.
    215 ///
    216 void BasicBlock::removePredecessor(BasicBlock *Pred,
    217                                    bool DontDeleteUselessPHIs) {
    218   assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
    219           find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
    220          "removePredecessor: BB is not a predecessor!");
    221 
    222   if (InstList.empty()) return;
    223   PHINode *APN = dyn_cast<PHINode>(&front());
    224   if (!APN) return;   // Quick exit.
    225 
    226   // If there are exactly two predecessors, then we want to nuke the PHI nodes
    227   // altogether.  However, we cannot do this, if this in this case:
    228   //
    229   //  Loop:
    230   //    %x = phi [X, Loop]
    231   //    %x2 = add %x, 1         ;; This would become %x2 = add %x2, 1
    232   //    br Loop                 ;; %x2 does not dominate all uses
    233   //
    234   // This is because the PHI node input is actually taken from the predecessor
    235   // basic block.  The only case this can happen is with a self loop, so we
    236   // check for this case explicitly now.
    237   //
    238   unsigned max_idx = APN->getNumIncomingValues();
    239   assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
    240   if (max_idx == 2) {
    241     BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred);
    242 
    243     // Disable PHI elimination!
    244     if (this == Other) max_idx = 3;
    245   }
    246 
    247   // <= Two predecessors BEFORE I remove one?
    248   if (max_idx <= 2 && !DontDeleteUselessPHIs) {
    249     // Yup, loop through and nuke the PHI nodes
    250     while (PHINode *PN = dyn_cast<PHINode>(&front())) {
    251       // Remove the predecessor first.
    252       PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs);
    253 
    254       // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
    255       if (max_idx == 2) {
    256         if (PN->getIncomingValue(0) != PN)
    257           PN->replaceAllUsesWith(PN->getIncomingValue(0));
    258         else
    259           // We are left with an infinite loop with no entries: kill the PHI.
    260           PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
    261         getInstList().pop_front();    // Remove the PHI node
    262       }
    263 
    264       // If the PHI node already only had one entry, it got deleted by
    265       // removeIncomingValue.
    266     }
    267   } else {
    268     // Okay, now we know that we need to remove predecessor #pred_idx from all
    269     // PHI nodes.  Iterate over each PHI node fixing them up
    270     PHINode *PN;
    271     for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
    272       ++II;
    273       PN->removeIncomingValue(Pred, false);
    274       // If all incoming values to the Phi are the same, we can replace the Phi
    275       // with that value.
    276       Value* PNV = 0;
    277       if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue()))
    278         if (PNV != PN) {
    279           PN->replaceAllUsesWith(PNV);
    280           PN->eraseFromParent();
    281         }
    282     }
    283   }
    284 }
    285 
    286 
    287 /// splitBasicBlock - This splits a basic block into two at the specified
    288 /// instruction.  Note that all instructions BEFORE the specified iterator stay
    289 /// as part of the original basic block, an unconditional branch is added to
    290 /// the new BB, and the rest of the instructions in the BB are moved to the new
    291 /// BB, including the old terminator.  This invalidates the iterator.
    292 ///
    293 /// Note that this only works on well formed basic blocks (must have a
    294 /// terminator), and 'I' must not be the end of instruction list (which would
    295 /// cause a degenerate basic block to be formed, having a terminator inside of
    296 /// the basic block).
    297 ///
    298 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
    299   assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
    300   assert(I != InstList.end() &&
    301          "Trying to get me to create degenerate basic block!");
    302 
    303   BasicBlock *InsertBefore = llvm::next(Function::iterator(this))
    304                                .getNodePtrUnchecked();
    305   BasicBlock *New = BasicBlock::Create(getContext(), BBName,
    306                                        getParent(), InsertBefore);
    307 
    308   // Move all of the specified instructions from the original basic block into
    309   // the new basic block.
    310   New->getInstList().splice(New->end(), this->getInstList(), I, end());
    311 
    312   // Add a branch instruction to the newly formed basic block.
    313   BranchInst::Create(New, this);
    314 
    315   // Now we must loop through all of the successors of the New block (which
    316   // _were_ the successors of the 'this' block), and update any PHI nodes in
    317   // successors.  If there were PHI nodes in the successors, then they need to
    318   // know that incoming branches will be from New, not from Old.
    319   //
    320   for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) {
    321     // Loop over any phi nodes in the basic block, updating the BB field of
    322     // incoming values...
    323     BasicBlock *Successor = *I;
    324     PHINode *PN;
    325     for (BasicBlock::iterator II = Successor->begin();
    326          (PN = dyn_cast<PHINode>(II)); ++II) {
    327       int IDX = PN->getBasicBlockIndex(this);
    328       while (IDX != -1) {
    329         PN->setIncomingBlock((unsigned)IDX, New);
    330         IDX = PN->getBasicBlockIndex(this);
    331       }
    332     }
    333   }
    334   return New;
    335 }
    336 
    337 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
    338   TerminatorInst *TI = getTerminator();
    339   if (!TI)
    340     // Cope with being called on a BasicBlock that doesn't have a terminator
    341     // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
    342     return;
    343   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
    344     BasicBlock *Succ = TI->getSuccessor(i);
    345     // N.B. Succ might not be a complete BasicBlock, so don't assume
    346     // that it ends with a non-phi instruction.
    347     for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) {
    348       PHINode *PN = dyn_cast<PHINode>(II);
    349       if (!PN)
    350         break;
    351       int i;
    352       while ((i = PN->getBasicBlockIndex(this)) >= 0)
    353         PN->setIncomingBlock(i, New);
    354     }
    355   }
    356 }
    357 
    358 /// isLandingPad - Return true if this basic block is a landing pad. I.e., it's
    359 /// the destination of the 'unwind' edge of an invoke instruction.
    360 bool BasicBlock::isLandingPad() const {
    361   return isa<LandingPadInst>(getFirstNonPHI());
    362 }
    363 
    364 /// getLandingPadInst() - Return the landingpad instruction associated with
    365 /// the landing pad.
    366 LandingPadInst *BasicBlock::getLandingPadInst() {
    367   return dyn_cast<LandingPadInst>(getFirstNonPHI());
    368 }
    369