BasicBlock.cpp revision e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0
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/iTerminators.h" 9009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/SymbolTable.h" 10009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/Type.h" 11455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner#include "llvm/Support/CFG.h" 127061dc50b2513731d7b346ab16183cda4a44619fChris Lattner#include "llvm/iPHINode.h" 13b63933975f7d7381bc4310925ce2a7ceb6095a88Vikram S. Adve#include "llvm/CodeGen/MachineInstr.h" 14009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 15009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Instantiate Templates - This ugliness is the price we have to pay 16009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// for having a ValueHolderImpl.h file seperate from ValueHolder.h! :( 17009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 18a3d3c2b64545c00f70453642e5d84b028dfce671Chris Lattnertemplate class ValueHolder<Instruction, BasicBlock, Method>; 19009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 20697954c15da58bd8b186dbafdedd8b06db770201Chris LattnerBasicBlock::BasicBlock(const std::string &name, Method *Parent) 216892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattner : Value(Type::LabelTy, Value::BasicBlockVal, name), InstList(this, 0), 226892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattner machineInstrVec(new MachineCodeForBasicBlock) { 23a3d3c2b64545c00f70453642e5d84b028dfce671Chris Lattner if (Parent) 24a3d3c2b64545c00f70453642e5d84b028dfce671Chris Lattner Parent->getBasicBlocks().push_back(this); 25009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 26009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 27009505452b713ed2e3a8e99c5545a6e721c65495Chris LattnerBasicBlock::~BasicBlock() { 28009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner dropAllReferences(); 29009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner InstList.delete_all(); 30b63933975f7d7381bc4310925ce2a7ceb6095a88Vikram S. Adve delete machineInstrVec; 31009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 32009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 33009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Specialize setName to take care of symbol table majik 34697954c15da58bd8b186dbafdedd8b06db770201Chris Lattnervoid BasicBlock::setName(const std::string &name, SymbolTable *ST) { 35009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Method *P; 366892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattner assert((ST == 0 || (!getParent() || ST == getParent()->getSymbolTable())) && 376892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattner "Invalid symtab argument!"); 38009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if ((P = getParent()) && hasName()) P->getSymbolTable()->remove(this); 39009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Value::setName(name); 40009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (P && hasName()) P->getSymbolTable()->insert(this); 41009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 42009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 43009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnervoid BasicBlock::setParent(Method *parent) { 44009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (getParent() && hasName()) 45009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner getParent()->getSymbolTable()->remove(this); 46009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 47009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner InstList.setParent(parent); 48009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 49009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (getParent() && hasName()) 50009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner getParent()->getSymbolTableSure()->insert(this); 51009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 52009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 53009505452b713ed2e3a8e99c5545a6e721c65495Chris LattnerTerminatorInst *BasicBlock::getTerminator() { 54009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 55009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Instruction *T = InstList.back(); 56b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner if (isa<TerminatorInst>(T)) return cast<TerminatorInst>(T); 57009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return 0; 58009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 59009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 60009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnerconst TerminatorInst *const BasicBlock::getTerminator() const { 61009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 62b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner if (const TerminatorInst *TI = dyn_cast<TerminatorInst>(InstList.back())) 63b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner return TI; 64009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return 0; 65009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 66009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 67009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnervoid BasicBlock::dropAllReferences() { 68009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner for_each(InstList.begin(), InstList.end(), 69009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner std::mem_fun(&Instruction::dropAllReferences)); 70009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 71009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 72e9bb2df410f7a22decad9a883f7139d5857c1520Chris Lattner// hasConstantReferences() - This predicate is true if there is a 73009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// reference to this basic block in the constant pool for this method. For 74009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// example, if a block is reached through a switch table, that table resides 75009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// in the constant pool, and the basic block is reference from it. 76009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 77e9bb2df410f7a22decad9a883f7139d5857c1520Chris Lattnerbool BasicBlock::hasConstantReferences() const { 78009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner for (use_const_iterator I = use_begin(), E = use_end(); I != E; ++I) 79e9bb2df410f7a22decad9a883f7139d5857c1520Chris Lattner if (::isa<Constant>(*I)) 80009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return true; 81009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 82009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return false; 83009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 84009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 85b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// removePredecessor - This method is used to notify a BasicBlock that the 86b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// specified Predecessor of the block is no longer able to reach it. This is 87b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// actually not used to update the Predecessor list, but is actually used to 88b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// update the PHI nodes that reside in the block. Note that this should be 89b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// called while the predecessor still refers to this block. 90b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// 91b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattnervoid BasicBlock::removePredecessor(BasicBlock *Pred) { 92455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner assert(find(pred_begin(this), pred_end(this), Pred) != pred_end(this) && 93b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner "removePredecessor: BB is not a predecessor!"); 94b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner if (!isa<PHINode>(front())) return; // Quick exit. 95b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 96455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner pred_iterator PI(pred_begin(this)), EI(pred_end(this)); 97b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner unsigned max_idx; 98b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 99b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // Loop over the rest of the predecessors until we run out, or until we find 100b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // out that there are more than 2 predecessors. 101b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner for (max_idx = 0; PI != EI && max_idx < 3; ++PI, ++max_idx) /*empty*/; 102b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 103b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If there are exactly two predecessors, then we want to nuke the PHI nodes 104b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // altogether. 105b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 106b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner if (max_idx <= 2) { // <= Two predecessors BEFORE I remove one? 107b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner // Yup, loop through and nuke the PHI nodes 108b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner while (PHINode *PN = dyn_cast<PHINode>(front())) { 109b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner PN->removeIncomingValue(Pred); // Remove the predecessor first... 110b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 111b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner assert(PN->getNumIncomingValues() == max_idx-1 && 112b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner "PHI node shouldn't have this many values!!!"); 113b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 114b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 115b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner if (max_idx == 2) 116b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner PN->replaceAllUsesWith(PN->getOperand(0)); 117b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner delete getInstList().remove(begin()); // Remove the PHI node 118b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 119b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } else { 120b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // Okay, now we know that we need to remove predecessor #pred_idx from all 121b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // PHI nodes. Iterate over each PHI node fixing them up 122b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner iterator II(begin()); 123b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner for (; isa<PHINode>(*II); ++II) 124b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner cast<PHINode>(*II)->removeIncomingValue(Pred); 125b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 126b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner} 127b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 128009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 129009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// splitBasicBlock - This splits a basic block into two at the specified 130009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// instruction. Note that all instructions BEFORE the specified iterator stay 131009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// as part of the original basic block, an unconditional branch is added to 132009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// the new BB, and the rest of the instructions in the BB are moved to the new 133009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// BB, including the old terminator. This invalidates the iterator. 134009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 135009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Note that this only works on well formed basic blocks (must have a 136009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// terminator), and 'I' must not be the end of instruction list (which would 137009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// cause a degenerate basic block to be formed, having a terminator inside of 138009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// the basic block). 139009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 1407fc9fe34390c66ca58646d09a87f7dbaacb6c1f8Chris LattnerBasicBlock *BasicBlock::splitBasicBlock(iterator I) { 141009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 142009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner assert(I != InstList.end() && 143009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner "Trying to get me to create degenerate basic block!"); 144009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 145009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner BasicBlock *New = new BasicBlock("", getParent()); 146009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 147009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // Go from the end of the basic block through to the iterator pointer, moving 148009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // to the new basic block... 149009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Instruction *Inst = 0; 150009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner do { 1517fc9fe34390c66ca58646d09a87f7dbaacb6c1f8Chris Lattner iterator EndIt = end(); 152009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Inst = InstList.remove(--EndIt); // Remove from end 153009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner New->InstList.push_front(Inst); // Add to front 154009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner } while (Inst != *I); // Loop until we move the specified instruction. 155009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 156009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // Add a branch instruction to the newly formed basic block. 157009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner InstList.push_back(new BranchInst(New)); 158e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner 159e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // Now we must loop through all of the successors of the New block (which 160e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // _were_ the successors of the 'this' block), and update any PHI nodes in 161e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // successors. If there were PHI nodes in the successors, then they need to 162e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // know that incoming branches will be from New, not from Old. 163e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // 164e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner for (BasicBlock::succ_iterator I = succ_begin(New), E = succ_end(New); 165e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner I != E; ++I) { 166e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // Loop over any phi nodes in the basic block, updating the BB field of 167e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // incoming values... 168e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner BasicBlock *Successor = *I; 169e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner for (BasicBlock::iterator II = Successor->begin(); 170e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner PHINode *PN = dyn_cast<PHINode>(*II); ++II) { 171e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner int IDX = PN->getBasicBlockIndex(this); 172e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner while (IDX != -1) { 173e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner PN->setIncomingBlock((unsigned)IDX, New); 174e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner IDX = PN->getBasicBlockIndex(this); 175e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 176e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 177e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 178009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return New; 179009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 180