LLVM API Documentation

BasicBlock.cpp

Go to the documentation of this file.
00001 //===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the BasicBlock class for the VMCore library.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "llvm/BasicBlock.h"
00015 #include "llvm/Constants.h"
00016 #include "llvm/Instructions.h"
00017 #include "llvm/LLVMContext.h"
00018 #include "llvm/Type.h"
00019 #include "llvm/ADT/STLExtras.h"
00020 #include "llvm/Support/CFG.h"
00021 #include "llvm/Support/LeakDetector.h"
00022 #include "SymbolTableListTraitsImpl.h"
00023 #include <algorithm>
00024 using namespace llvm;
00025 
00026 ValueSymbolTable *BasicBlock::getValueSymbolTable() {
00027   if (Function *F = getParent())
00028     return &F->getValueSymbolTable();
00029   return 0;
00030 }
00031 
00032 LLVMContext &BasicBlock::getContext() const {
00033   return getType()->getContext();
00034 }
00035 
00036 // Explicit instantiation of SymbolTableListTraits since some of the methods
00037 // are not in the public header file...
00038 template class SymbolTableListTraits<Instruction, BasicBlock>;
00039 
00040 
00041 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
00042                        BasicBlock *InsertBefore)
00043   : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(0) {
00044 
00045   // Make sure that we get added to a function
00046   LeakDetector::addGarbageObject(this);
00047 
00048   if (InsertBefore) {
00049     assert(NewParent &&
00050            "Cannot insert block before another block with no function!");
00051     NewParent->getBasicBlockList().insert(InsertBefore, this);
00052   } else if (NewParent) {
00053     NewParent->getBasicBlockList().push_back(this);
00054   }
00055   
00056   setName(Name);
00057 }
00058 
00059 
00060 BasicBlock::~BasicBlock() {
00061   assert(getParent() == 0 && "BasicBlock still linked into the program!");
00062   dropAllReferences();
00063   InstList.clear();
00064 }
00065 
00066 void BasicBlock::setParent(Function *parent) {
00067   if (getParent())
00068     LeakDetector::addGarbageObject(this);
00069 
00070   // Set Parent=parent, updating instruction symtab entries as appropriate.
00071   InstList.setSymTabObject(&Parent, parent);
00072 
00073   if (getParent())
00074     LeakDetector::removeGarbageObject(this);
00075 }
00076 
00077 void BasicBlock::removeFromParent() {
00078   getParent()->getBasicBlockList().remove(this);
00079 }
00080 
00081 void BasicBlock::eraseFromParent() {
00082   getParent()->getBasicBlockList().erase(this);
00083 }
00084 
00085 /// moveBefore - Unlink this basic block from its current function and
00086 /// insert it into the function that MovePos lives in, right before MovePos.
00087 void BasicBlock::moveBefore(BasicBlock *MovePos) {
00088   MovePos->getParent()->getBasicBlockList().splice(MovePos,
00089                        getParent()->getBasicBlockList(), this);
00090 }
00091 
00092 /// moveAfter - Unlink this basic block from its current function and
00093 /// insert it into the function that MovePos lives in, right after MovePos.
00094 void BasicBlock::moveAfter(BasicBlock *MovePos) {
00095   Function::iterator I = MovePos;
00096   MovePos->getParent()->getBasicBlockList().splice(++I,
00097                                        getParent()->getBasicBlockList(), this);
00098 }
00099 
00100 
00101 TerminatorInst *BasicBlock::getTerminator() {
00102   if (InstList.empty()) return 0;
00103   return dyn_cast<TerminatorInst>(&InstList.back());
00104 }
00105 
00106 const TerminatorInst *BasicBlock::getTerminator() const {
00107   if (InstList.empty()) return 0;
00108   return dyn_cast<TerminatorInst>(&InstList.back());
00109 }
00110 
00111 Instruction* BasicBlock::getFirstNonPHI() {
00112   BasicBlock::iterator i = begin();
00113   // All valid basic blocks should have a terminator,
00114   // which is not a PHINode. If we have an invalid basic
00115   // block we'll get an assertion failure when dereferencing
00116   // a past-the-end iterator.
00117   while (isa<PHINode>(i)) ++i;
00118   return &*i;
00119 }
00120 
00121 void BasicBlock::dropAllReferences() {
00122   for(iterator I = begin(), E = end(); I != E; ++I)
00123     I->dropAllReferences();
00124 }
00125 
00126 /// getSinglePredecessor - If this basic block has a single predecessor block,
00127 /// return the block, otherwise return a null pointer.
00128 BasicBlock *BasicBlock::getSinglePredecessor() {
00129   pred_iterator PI = pred_begin(this), E = pred_end(this);
00130   if (PI == E) return 0;         // No preds.
00131   BasicBlock *ThePred = *PI;
00132   ++PI;
00133   return (PI == E) ? ThePred : 0 /*multiple preds*/;
00134 }
00135 
00136 /// getUniquePredecessor - If this basic block has a unique predecessor block,
00137 /// return the block, otherwise return a null pointer.
00138 /// Note that unique predecessor doesn't mean single edge, there can be 
00139 /// multiple edges from the unique predecessor to this block (for example 
00140 /// a switch statement with multiple cases having the same destination).
00141 BasicBlock *BasicBlock::getUniquePredecessor() {
00142   pred_iterator PI = pred_begin(this), E = pred_end(this);
00143   if (PI == E) return 0; // No preds.
00144   BasicBlock *PredBB = *PI;
00145   ++PI;
00146   for (;PI != E; ++PI) {
00147     if (*PI != PredBB)
00148       return 0;
00149     // The same predecessor appears multiple times in the predecessor list.
00150     // This is OK.
00151   }
00152   return PredBB;
00153 }
00154 
00155 /// removePredecessor - This method is used to notify a BasicBlock that the
00156 /// specified Predecessor of the block is no longer able to reach it.  This is
00157 /// actually not used to update the Predecessor list, but is actually used to
00158 /// update the PHI nodes that reside in the block.  Note that this should be
00159 /// called while the predecessor still refers to this block.
00160 ///
00161 void BasicBlock::removePredecessor(BasicBlock *Pred,
00162                                    bool DontDeleteUselessPHIs) {
00163   assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
00164           find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
00165          "removePredecessor: BB is not a predecessor!");
00166 
00167   if (InstList.empty()) return;
00168   PHINode *APN = dyn_cast<PHINode>(&front());
00169   if (!APN) return;   // Quick exit.
00170 
00171   // If there are exactly two predecessors, then we want to nuke the PHI nodes
00172   // altogether.  However, we cannot do this, if this in this case:
00173   //
00174   //  Loop:
00175   //    %x = phi [X, Loop]
00176   //    %x2 = add %x, 1         ;; This would become %x2 = add %x2, 1
00177   //    br Loop                 ;; %x2 does not dominate all uses
00178   //
00179   // This is because the PHI node input is actually taken from the predecessor
00180   // basic block.  The only case this can happen is with a self loop, so we
00181   // check for this case explicitly now.
00182   //
00183   unsigned max_idx = APN->getNumIncomingValues();
00184   assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
00185   if (max_idx == 2) {
00186     BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred);
00187 
00188     // Disable PHI elimination!
00189     if (this == Other) max_idx = 3;
00190   }
00191 
00192   // <= Two predecessors BEFORE I remove one?
00193   if (max_idx <= 2 && !DontDeleteUselessPHIs) {
00194     // Yup, loop through and nuke the PHI nodes
00195     while (PHINode *PN = dyn_cast<PHINode>(&front())) {
00196       // Remove the predecessor first.
00197       PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs);
00198 
00199       // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
00200       if (max_idx == 2) {
00201         if (PN->getOperand(0) != PN)
00202           PN->replaceAllUsesWith(PN->getOperand(0));
00203         else
00204           // We are left with an infinite loop with no entries: kill the PHI.
00205           PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
00206         getInstList().pop_front();    // Remove the PHI node
00207       }
00208 
00209       // If the PHI node already only had one entry, it got deleted by
00210       // removeIncomingValue.
00211     }
00212   } else {
00213     // Okay, now we know that we need to remove predecessor #pred_idx from all
00214     // PHI nodes.  Iterate over each PHI node fixing them up
00215     PHINode *PN;
00216     for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
00217       ++II;
00218       PN->removeIncomingValue(Pred, false);
00219       // If all incoming values to the Phi are the same, we can replace the Phi
00220       // with that value.
00221       Value* PNV = 0;
00222       if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue())) {
00223         PN->replaceAllUsesWith(PNV);
00224         PN->eraseFromParent();
00225       }
00226     }
00227   }
00228 }
00229 
00230 
00231 /// splitBasicBlock - This splits a basic block into two at the specified
00232 /// instruction.  Note that all instructions BEFORE the specified iterator stay
00233 /// as part of the original basic block, an unconditional branch is added to
00234 /// the new BB, and the rest of the instructions in the BB are moved to the new
00235 /// BB, including the old terminator.  This invalidates the iterator.
00236 ///
00237 /// Note that this only works on well formed basic blocks (must have a
00238 /// terminator), and 'I' must not be the end of instruction list (which would
00239 /// cause a degenerate basic block to be formed, having a terminator inside of
00240 /// the basic block).
00241 ///
00242 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
00243   assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
00244   assert(I != InstList.end() &&
00245          "Trying to get me to create degenerate basic block!");
00246 
00247   BasicBlock *InsertBefore = next(Function::iterator(this))
00248                                .getNodePtrUnchecked();
00249   BasicBlock *New = BasicBlock::Create(getContext(), BBName,
00250                                        getParent(), InsertBefore);
00251 
00252   // Move all of the specified instructions from the original basic block into
00253   // the new basic block.
00254   New->getInstList().splice(New->end(), this->getInstList(), I, end());
00255 
00256   // Add a branch instruction to the newly formed basic block.
00257   BranchInst::Create(New, this);
00258 
00259   // Now we must loop through all of the successors of the New block (which
00260   // _were_ the successors of the 'this' block), and update any PHI nodes in
00261   // successors.  If there were PHI nodes in the successors, then they need to
00262   // know that incoming branches will be from New, not from Old.
00263   //
00264   for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) {
00265     // Loop over any phi nodes in the basic block, updating the BB field of
00266     // incoming values...
00267     BasicBlock *Successor = *I;
00268     PHINode *PN;
00269     for (BasicBlock::iterator II = Successor->begin();
00270          (PN = dyn_cast<PHINode>(II)); ++II) {
00271       int IDX = PN->getBasicBlockIndex(this);
00272       while (IDX != -1) {
00273         PN->setIncomingBlock((unsigned)IDX, New);
00274         IDX = PN->getBasicBlockIndex(this);
00275       }
00276     }
00277   }
00278   return New;
00279 }