BasicBlock.cpp revision b63933975f7d7381bc4310925ce2a7ceb6095a88
1//===-- BasicBlock.cpp - Implement BasicBlock related functions --*- C++ -*--=// 2// 3// This file implements the Method class for the VMCore library. 4// 5//===----------------------------------------------------------------------===// 6 7#include "llvm/ValueHolderImpl.h" 8#include "llvm/BasicBlock.h" 9#include "llvm/iTerminators.h" 10#include "llvm/Module.h" 11#include "llvm/Method.h" 12#include "llvm/SymbolTable.h" 13#include "llvm/Type.h" 14#include "llvm/CFG.h" 15#include "llvm/iOther.h" 16#include "llvm/CodeGen/MachineInstr.h" 17 18// Instantiate Templates - This ugliness is the price we have to pay 19// for having a ValueHolderImpl.h file seperate from ValueHolder.h! :( 20// 21template class ValueHolder<Instruction, BasicBlock, Method>; 22 23BasicBlock::BasicBlock(const string &name, Method *Parent) 24 : Value(Type::LabelTy, Value::BasicBlockVal, name), 25 InstList(this, 0), 26 machineInstrVec(new MachineCodeForBasicBlock) 27{ 28 if (Parent) 29 Parent->getBasicBlocks().push_back(this); 30} 31 32BasicBlock::~BasicBlock() { 33 dropAllReferences(); 34 InstList.delete_all(); 35 delete machineInstrVec; 36} 37 38// Specialize setName to take care of symbol table majik 39void BasicBlock::setName(const string &name) { 40 Method *P; 41 if ((P = getParent()) && hasName()) P->getSymbolTable()->remove(this); 42 Value::setName(name); 43 if (P && hasName()) P->getSymbolTable()->insert(this); 44} 45 46void BasicBlock::setParent(Method *parent) { 47 if (getParent() && hasName()) 48 getParent()->getSymbolTable()->remove(this); 49 50 InstList.setParent(parent); 51 52 if (getParent() && hasName()) 53 getParent()->getSymbolTableSure()->insert(this); 54} 55 56TerminatorInst *BasicBlock::getTerminator() { 57 if (InstList.empty()) return 0; 58 Instruction *T = InstList.back(); 59 if (T->isTerminator()) return (TerminatorInst*)T; 60 return 0; 61} 62 63const TerminatorInst *const BasicBlock::getTerminator() const { 64 if (InstList.empty()) return 0; 65 const Instruction *T = InstList.back(); 66 if (T->isTerminator()) return (TerminatorInst*)T; 67 return 0; 68} 69 70void BasicBlock::dropAllReferences() { 71 for_each(InstList.begin(), InstList.end(), 72 std::mem_fun(&Instruction::dropAllReferences)); 73} 74 75// hasConstantPoolReferences() - This predicate is true if there is a 76// reference to this basic block in the constant pool for this method. For 77// example, if a block is reached through a switch table, that table resides 78// in the constant pool, and the basic block is reference from it. 79// 80bool BasicBlock::hasConstantPoolReferences() const { 81 for (use_const_iterator I = use_begin(), E = use_end(); I != E; ++I) 82 if ((*I)->isConstant()) 83 return true; 84 85 return false; 86} 87 88// removePredecessor - This method is used to notify a BasicBlock that the 89// specified Predecessor of the block is no longer able to reach it. This is 90// actually not used to update the Predecessor list, but is actually used to 91// update the PHI nodes that reside in the block. Note that this should be 92// called while the predecessor still refers to this block. 93// 94void BasicBlock::removePredecessor(BasicBlock *Pred) { 95 using cfg::pred_begin; using cfg::pred_end; using cfg::pred_iterator; 96 assert(find(pred_begin(this), pred_end(this), Pred) != pred_end(this) && 97 "removePredecessor: BB is not a predecessor!"); 98 if (!front()->isPHINode()) return; // Quick exit. 99 100 pred_iterator PI(pred_begin(this)), EI(pred_end(this)); 101 unsigned max_idx; 102 103 // Loop over the rest of the predecessors until we run out, or until we find 104 // out that there are more than 2 predecessors. 105 for (max_idx = 0; PI != EI && max_idx < 3; ++PI, ++max_idx) /*empty*/; 106 107 // If there are exactly two predecessors, then we want to nuke the PHI nodes 108 // altogether. 109 assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 110 if (max_idx <= 2) { // <= Two predecessors BEFORE I remove one? 111 while (front()->isPHINode()) { // Yup, loop through and nuke the PHI nodes 112 PHINode *PN = (PHINode*)front(); 113 PN->removeIncomingValue(Pred); // Remove the predecessor first... 114 115 assert(PN->getNumIncomingValues() == max_idx-1 && 116 "PHI node shouldn't have this many values!!!"); 117 118 // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 119 if (max_idx == 2) 120 PN->replaceAllUsesWith(PN->getOperand(0)); 121 delete getInstList().remove(begin()); // Remove the PHI node 122 } 123 } else { 124 // Okay, now we know that we need to remove predecessor #pred_idx from all 125 // PHI nodes. Iterate over each PHI node fixing them up 126 iterator II(begin()); 127 for (; (*II)->isPHINode(); ++II) { 128 PHINode *PN = (PHINode*)*II; 129 PN->removeIncomingValue(Pred); 130 } 131 } 132} 133 134 135// splitBasicBlock - This splits a basic block into two at the specified 136// instruction. Note that all instructions BEFORE the specified iterator stay 137// as part of the original basic block, an unconditional branch is added to 138// the new BB, and the rest of the instructions in the BB are moved to the new 139// BB, including the old terminator. This invalidates the iterator. 140// 141// Note that this only works on well formed basic blocks (must have a 142// terminator), and 'I' must not be the end of instruction list (which would 143// cause a degenerate basic block to be formed, having a terminator inside of 144// the basic block). 145// 146BasicBlock *BasicBlock::splitBasicBlock(iterator I) { 147 assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 148 assert(I != InstList.end() && 149 "Trying to get me to create degenerate basic block!"); 150 151 BasicBlock *New = new BasicBlock("", getParent()); 152 153 // Go from the end of the basic block through to the iterator pointer, moving 154 // to the new basic block... 155 Instruction *Inst = 0; 156 do { 157 iterator EndIt = end(); 158 Inst = InstList.remove(--EndIt); // Remove from end 159 New->InstList.push_front(Inst); // Add to front 160 } while (Inst != *I); // Loop until we move the specified instruction. 161 162 // Add a branch instruction to the newly formed basic block. 163 InstList.push_back(new BranchInst(New)); 164 return New; 165} 166