BasicBlock.cpp revision b00c582b6d40e6b9ff2d1ed4f5eaf7930e792ace
1009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner//===-- BasicBlock.cpp - Implement BasicBlock related functions --*- C++ -*--=// 2009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 3009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// This file implements the Method class for the VMCore library. 4009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 5009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner//===----------------------------------------------------------------------===// 6009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 7009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/ValueHolderImpl.h" 8009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/BasicBlock.h" 9009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/iTerminators.h" 10009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/Method.h" 11009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/SymbolTable.h" 12009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/Type.h" 13b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner#include "llvm/iOther.h" 14b63933975f7d7381bc4310925ce2a7ceb6095a88Vikram S. Adve#include "llvm/CodeGen/MachineInstr.h" 15009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 16009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Instantiate Templates - This ugliness is the price we have to pay 17009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// for having a ValueHolderImpl.h file seperate from ValueHolder.h! :( 18009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 19a3d3c2b64545c00f70453642e5d84b028dfce671Chris Lattnertemplate class ValueHolder<Instruction, BasicBlock, Method>; 20009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 21a3d3c2b64545c00f70453642e5d84b028dfce671Chris LattnerBasicBlock::BasicBlock(const string &name, Method *Parent) 226892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattner : Value(Type::LabelTy, Value::BasicBlockVal, name), InstList(this, 0), 236892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattner machineInstrVec(new MachineCodeForBasicBlock) { 24a3d3c2b64545c00f70453642e5d84b028dfce671Chris Lattner if (Parent) 25a3d3c2b64545c00f70453642e5d84b028dfce671Chris Lattner Parent->getBasicBlocks().push_back(this); 26009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 27009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 28009505452b713ed2e3a8e99c5545a6e721c65495Chris LattnerBasicBlock::~BasicBlock() { 29009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner dropAllReferences(); 30009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner InstList.delete_all(); 31b63933975f7d7381bc4310925ce2a7ceb6095a88Vikram S. Adve delete machineInstrVec; 32009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 33009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 34009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Specialize setName to take care of symbol table majik 356892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattnervoid BasicBlock::setName(const string &name, SymbolTable *ST) { 36009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Method *P; 376892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattner assert((ST == 0 || (!getParent() || ST == getParent()->getSymbolTable())) && 386892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattner "Invalid symtab argument!"); 39009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if ((P = getParent()) && hasName()) P->getSymbolTable()->remove(this); 40009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Value::setName(name); 41009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (P && hasName()) P->getSymbolTable()->insert(this); 42009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 43009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 44009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnervoid BasicBlock::setParent(Method *parent) { 45009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (getParent() && hasName()) 46009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner getParent()->getSymbolTable()->remove(this); 47009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 48009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner InstList.setParent(parent); 49009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 50009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (getParent() && hasName()) 51009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner getParent()->getSymbolTableSure()->insert(this); 52009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 53009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 54009505452b713ed2e3a8e99c5545a6e721c65495Chris LattnerTerminatorInst *BasicBlock::getTerminator() { 55009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 56009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Instruction *T = InstList.back(); 57b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner if (isa<TerminatorInst>(T)) return cast<TerminatorInst>(T); 58009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return 0; 59009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 60009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 61009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnerconst TerminatorInst *const BasicBlock::getTerminator() const { 62009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 63b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner if (const TerminatorInst *TI = dyn_cast<TerminatorInst>(InstList.back())) 64b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner return TI; 65009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return 0; 66009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 67009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 68009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnervoid BasicBlock::dropAllReferences() { 69009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner for_each(InstList.begin(), InstList.end(), 70009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner std::mem_fun(&Instruction::dropAllReferences)); 71009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 72009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 73009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// hasConstantPoolReferences() - This predicate is true if there is a 74009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// reference to this basic block in the constant pool for this method. For 75009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// example, if a block is reached through a switch table, that table resides 76009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// in the constant pool, and the basic block is reference from it. 77009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 78009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnerbool BasicBlock::hasConstantPoolReferences() const { 79009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner for (use_const_iterator I = use_begin(), E = use_end(); I != E; ++I) 801d87bcf4909b06dcd86320722653341f08b8b396Chris Lattner if (::isa<ConstPoolVal>(*I)) 81009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return true; 82009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 83009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return false; 84009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 85009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 86b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// removePredecessor - This method is used to notify a BasicBlock that the 87b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// specified Predecessor of the block is no longer able to reach it. This is 88b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// actually not used to update the Predecessor list, but is actually used to 89b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// update the PHI nodes that reside in the block. Note that this should be 90b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// called while the predecessor still refers to this block. 91b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// 92b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattnervoid BasicBlock::removePredecessor(BasicBlock *Pred) { 93f0604b84c7273fc2503454ecaa198eaee5b615bdChris Lattner assert(find(pred_begin(), pred_end(), Pred) != pred_end() && 94b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner "removePredecessor: BB is not a predecessor!"); 95b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner if (!isa<PHINode>(front())) return; // Quick exit. 96b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 97f0604b84c7273fc2503454ecaa198eaee5b615bdChris Lattner pred_iterator PI(pred_begin()), EI(pred_end()); 98b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner unsigned max_idx; 99b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 100b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // Loop over the rest of the predecessors until we run out, or until we find 101b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // out that there are more than 2 predecessors. 102b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner for (max_idx = 0; PI != EI && max_idx < 3; ++PI, ++max_idx) /*empty*/; 103b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 104b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If there are exactly two predecessors, then we want to nuke the PHI nodes 105b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // altogether. 106b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 107b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner if (max_idx <= 2) { // <= Two predecessors BEFORE I remove one? 108b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner // Yup, loop through and nuke the PHI nodes 109b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner while (PHINode *PN = dyn_cast<PHINode>(front())) { 110b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner PN->removeIncomingValue(Pred); // Remove the predecessor first... 111b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 112b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner assert(PN->getNumIncomingValues() == max_idx-1 && 113b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner "PHI node shouldn't have this many values!!!"); 114b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 115b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 116b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner if (max_idx == 2) 117b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner PN->replaceAllUsesWith(PN->getOperand(0)); 118b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner delete getInstList().remove(begin()); // Remove the PHI node 119b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 120b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } else { 121b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // Okay, now we know that we need to remove predecessor #pred_idx from all 122b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // PHI nodes. Iterate over each PHI node fixing them up 123b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner iterator II(begin()); 124b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner for (; isa<PHINode>(*II); ++II) 125b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner cast<PHINode>(*II)->removeIncomingValue(Pred); 126b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 127b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner} 128b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 129009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 130009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// splitBasicBlock - This splits a basic block into two at the specified 131009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// instruction. Note that all instructions BEFORE the specified iterator stay 132009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// as part of the original basic block, an unconditional branch is added to 133009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// the new BB, and the rest of the instructions in the BB are moved to the new 134009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// BB, including the old terminator. This invalidates the iterator. 135009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 136009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Note that this only works on well formed basic blocks (must have a 137009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// terminator), and 'I' must not be the end of instruction list (which would 138009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// cause a degenerate basic block to be formed, having a terminator inside of 139009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// the basic block). 140009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 1417fc9fe34390c66ca58646d09a87f7dbaacb6c1f8Chris LattnerBasicBlock *BasicBlock::splitBasicBlock(iterator I) { 142009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 143009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner assert(I != InstList.end() && 144009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner "Trying to get me to create degenerate basic block!"); 145009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 146009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner BasicBlock *New = new BasicBlock("", getParent()); 147009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 148009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // Go from the end of the basic block through to the iterator pointer, moving 149009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // to the new basic block... 150009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Instruction *Inst = 0; 151009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner do { 1527fc9fe34390c66ca58646d09a87f7dbaacb6c1f8Chris Lattner iterator EndIt = end(); 153009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Inst = InstList.remove(--EndIt); // Remove from end 154009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner New->InstList.push_front(Inst); // Add to front 155009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner } while (Inst != *I); // Loop until we move the specified instruction. 156009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 157009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // Add a branch instruction to the newly formed basic block. 158009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner InstList.push_back(new BranchInst(New)); 159009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return New; 160009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 161