BasicBlock.cpp revision 108e4ab159b59a616b0868e396dc7ddc1fb48616
1//===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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/iTerminators.h" 16#include "llvm/Type.h" 17#include "llvm/Support/CFG.h" 18#include "llvm/Constant.h" 19#include "llvm/iPHINode.h" 20#include "llvm/SymbolTable.h" 21#include "Support/LeakDetector.h" 22#include "SymbolTableListTraitsImpl.h" 23#include <algorithm> 24using namespace llvm; 25 26namespace { 27 /// DummyInst - An instance of this class is used to mark the end of the 28 /// instruction list. This is not a real instruction. 29 struct DummyInst : public Instruction { 30 DummyInst() : Instruction(Type::VoidTy, OtherOpsEnd) { 31 // This should not be garbage monitored. 32 LeakDetector::removeGarbageObject(this); 33 } 34 35 virtual Instruction *clone() const { 36 assert(0 && "Cannot clone EOL");abort(); 37 return 0; 38 } 39 virtual const char *getOpcodeName() const { return "*end-of-list-inst*"; } 40 41 // Methods for support type inquiry through isa, cast, and dyn_cast... 42 static inline bool classof(const DummyInst *) { return true; } 43 static inline bool classof(const Instruction *I) { 44 return I->getOpcode() == OtherOpsEnd; 45 } 46 static inline bool classof(const Value *V) { 47 return isa<Instruction>(V) && classof(cast<Instruction>(V)); 48 } 49 }; 50} 51 52Instruction *ilist_traits<Instruction>::createNode() { 53 return new DummyInst(); 54} 55iplist<Instruction> &ilist_traits<Instruction>::getList(BasicBlock *BB) { 56 return BB->getInstList(); 57} 58 59// Explicit instantiation of SymbolTableListTraits since some of the methods 60// are not in the public header file... 61template class SymbolTableListTraits<Instruction, BasicBlock, Function>; 62 63 64// BasicBlock ctor - If the function parameter is specified, the basic block is 65// automatically inserted at the end of the function. 66// 67BasicBlock::BasicBlock(const std::string &name, Function *Parent) 68 : Value(Type::LabelTy, Value::BasicBlockVal, name) { 69 // Initialize the instlist... 70 InstList.setItemParent(this); 71 72 // Make sure that we get added to a function 73 LeakDetector::addGarbageObject(this); 74 75 if (Parent) 76 Parent->getBasicBlockList().push_back(this); 77} 78 79/// BasicBlock ctor - If the InsertBefore parameter is specified, the basic 80/// block is automatically inserted right before the specified block. 81/// 82BasicBlock::BasicBlock(const std::string &Name, BasicBlock *InsertBefore) 83 : Value(Type::LabelTy, Value::BasicBlockVal, Name) { 84 // Initialize the instlist... 85 InstList.setItemParent(this); 86 87 // Make sure that we get added to a function 88 LeakDetector::addGarbageObject(this); 89 90 if (InsertBefore) { 91 assert(InsertBefore->getParent() && 92 "Cannot insert block before another block that is not embedded into" 93 " a function yet!"); 94 InsertBefore->getParent()->getBasicBlockList().insert(InsertBefore, this); 95 } 96} 97 98 99BasicBlock::~BasicBlock() { 100 dropAllReferences(); 101 InstList.clear(); 102} 103 104void BasicBlock::setParent(Function *parent) { 105 if (getParent()) 106 LeakDetector::addGarbageObject(this); 107 108 InstList.setParent(parent); 109 110 if (getParent()) 111 LeakDetector::removeGarbageObject(this); 112} 113 114// Specialize setName to take care of symbol table majik 115void BasicBlock::setName(const std::string &name, SymbolTable *ST) { 116 Function *P; 117 assert((ST == 0 || (!getParent() || ST == &getParent()->getSymbolTable())) && 118 "Invalid symtab argument!"); 119 if ((P = getParent()) && hasName()) P->getSymbolTable().remove(this); 120 Value::setName(name); 121 if (P && hasName()) P->getSymbolTable().insert(this); 122} 123 124TerminatorInst *BasicBlock::getTerminator() { 125 if (InstList.empty()) return 0; 126 return dyn_cast<TerminatorInst>(&InstList.back()); 127} 128 129const TerminatorInst *const BasicBlock::getTerminator() const { 130 if (InstList.empty()) return 0; 131 return dyn_cast<TerminatorInst>(&InstList.back()); 132} 133 134void BasicBlock::dropAllReferences() { 135 for(iterator I = begin(), E = end(); I != E; ++I) 136 I->dropAllReferences(); 137} 138 139// hasConstantReferences() - This predicate is true if there is a 140// reference to this basic block in the constant pool for this method. For 141// example, if a block is reached through a switch table, that table resides 142// in the constant pool, and the basic block is reference from it. 143// 144bool BasicBlock::hasConstantReferences() const { 145 for (use_const_iterator I = use_begin(), E = use_end(); I != E; ++I) 146 if (isa<Constant>((Value*)*I)) 147 return true; 148 149 return false; 150} 151 152// removePredecessor - This method is used to notify a BasicBlock that the 153// specified Predecessor of the block is no longer able to reach it. This is 154// actually not used to update the Predecessor list, but is actually used to 155// update the PHI nodes that reside in the block. Note that this should be 156// called while the predecessor still refers to this block. 157// 158void BasicBlock::removePredecessor(BasicBlock *Pred) { 159 assert(find(pred_begin(this), pred_end(this), Pred) != pred_end(this) && 160 "removePredecessor: BB is not a predecessor!"); 161 if (!isa<PHINode>(front())) return; // Quick exit. 162 163 pred_iterator PI(pred_begin(this)), EI(pred_end(this)); 164 unsigned max_idx; 165 166 // Loop over the rest of the predecessors until we run out, or until we find 167 // out that there are more than 2 predecessors. 168 for (max_idx = 0; PI != EI && max_idx < 3; ++PI, ++max_idx) /*empty*/; 169 170 // If there are exactly two predecessors, then we want to nuke the PHI nodes 171 // altogether. We cannot do this, however if this in this case however: 172 // 173 // Loop: 174 // %x = phi [X, Loop] 175 // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1 176 // br Loop ;; %x2 does not dominate all uses 177 // 178 // This is because the PHI node input is actually taken from the predecessor 179 // basic block. The only case this can happen is with a self loop, so we 180 // check for this case explicitly now. 181 // 182 assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 183 if (max_idx == 2) { 184 PI = pred_begin(this); 185 BasicBlock *Other = *PI == Pred ? *++PI : *PI; 186 187 // Disable PHI elimination! 188 if (this == Other) max_idx = 3; 189 } 190 191 if (max_idx <= 2) { // <= Two predecessors BEFORE I remove one? 192 // Yup, loop through and nuke the PHI nodes 193 while (PHINode *PN = dyn_cast<PHINode>(&front())) { 194 PN->removeIncomingValue(Pred); // Remove the predecessor first... 195 196 // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 197 if (max_idx == 2) { 198 if (PN->getOperand(0) != PN) 199 PN->replaceAllUsesWith(PN->getOperand(0)); 200 else 201 // We are left with an infinite loop with no entries: kill the PHI. 202 PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 203 getInstList().pop_front(); // Remove the PHI node 204 } 205 206 // If the PHI node already only had one entry, it got deleted by 207 // removeIncomingValue. 208 } 209 } else { 210 // Okay, now we know that we need to remove predecessor #pred_idx from all 211 // PHI nodes. Iterate over each PHI node fixing them up 212 for (iterator II = begin(); PHINode *PN = dyn_cast<PHINode>(II); ++II) 213 PN->removeIncomingValue(Pred); 214 } 215} 216 217 218// splitBasicBlock - This splits a basic block into two at the specified 219// instruction. Note that all instructions BEFORE the specified iterator stay 220// as part of the original basic block, an unconditional branch is added to 221// the new BB, and the rest of the instructions in the BB are moved to the new 222// BB, including the old terminator. This invalidates the iterator. 223// 224// Note that this only works on well formed basic blocks (must have a 225// terminator), and 'I' must not be the end of instruction list (which would 226// cause a degenerate basic block to be formed, having a terminator inside of 227// the basic block). 228// 229BasicBlock *BasicBlock::splitBasicBlock(iterator I, const std::string &BBName) { 230 assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 231 assert(I != InstList.end() && 232 "Trying to get me to create degenerate basic block!"); 233 234 BasicBlock *New = new BasicBlock(BBName, getParent()); 235 236 // Go from the end of the basic block through to the iterator pointer, moving 237 // to the new basic block... 238 Instruction *Inst = 0; 239 do { 240 iterator EndIt = end(); 241 Inst = InstList.remove(--EndIt); // Remove from end 242 New->InstList.push_front(Inst); // Add to front 243 } while (Inst != &*I); // Loop until we move the specified instruction. 244 245 // Add a branch instruction to the newly formed basic block. 246 new BranchInst(New, this); 247 248 // Now we must loop through all of the successors of the New block (which 249 // _were_ the successors of the 'this' block), and update any PHI nodes in 250 // successors. If there were PHI nodes in the successors, then they need to 251 // know that incoming branches will be from New, not from Old. 252 // 253 for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) { 254 // Loop over any phi nodes in the basic block, updating the BB field of 255 // incoming values... 256 BasicBlock *Successor = *I; 257 for (BasicBlock::iterator II = Successor->begin(); 258 PHINode *PN = dyn_cast<PHINode>(II); ++II) { 259 int IDX = PN->getBasicBlockIndex(this); 260 while (IDX != -1) { 261 PN->setIncomingBlock((unsigned)IDX, New); 262 IDX = PN->getBasicBlockIndex(this); 263 } 264 } 265 } 266 return New; 267} 268