BasicBlock.cpp revision 0a1a874d1f4659f02c0d4fdd6be69f1188bd0625
1d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner//===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===// 2009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 3b7653df0853f06112b741be09f1b7ae5a6aa6fdeChris Lattner// This file implements the BasicBlock class for the VMCore library. 4009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 5009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner//===----------------------------------------------------------------------===// 6009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 77e70829632f82de15db187845666aaca6e04b792Chris Lattner#include "llvm/BasicBlock.h" 8009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/iTerminators.h" 9009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/Type.h" 10455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner#include "llvm/Support/CFG.h" 1189d46b0f095cf7f536c6ad40b4541b73d259445fChris Lattner#include "llvm/Constant.h" 127061dc50b2513731d7b346ab16183cda4a44619fChris Lattner#include "llvm/iPHINode.h" 137e70829632f82de15db187845666aaca6e04b792Chris Lattner#include "llvm/SymbolTable.h" 14d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner#include "Support/LeakDetector.h" 157e70829632f82de15db187845666aaca6e04b792Chris Lattner#include "SymbolTableListTraitsImpl.h" 167e70829632f82de15db187845666aaca6e04b792Chris Lattner#include <algorithm> 17009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 187e70829632f82de15db187845666aaca6e04b792Chris Lattner// DummyInst - An instance of this class is used to mark the end of the 197e70829632f82de15db187845666aaca6e04b792Chris Lattner// instruction list. This is not a real instruction. 20009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 217e70829632f82de15db187845666aaca6e04b792Chris Lattnerstruct DummyInst : public Instruction { 22d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner DummyInst() : Instruction(Type::VoidTy, NumOtherOps) { 23d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner // This should not be garbage monitored. 24d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner LeakDetector::removeGarbageObject(this); 25d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner } 267e70829632f82de15db187845666aaca6e04b792Chris Lattner 27b2e80a69514485c36442ea849063313e6db13e09Chris Lattner virtual Instruction *clone() const { 28b2e80a69514485c36442ea849063313e6db13e09Chris Lattner assert(0 && "Cannot clone EOL");abort(); 29b2e80a69514485c36442ea849063313e6db13e09Chris Lattner return 0; 30b2e80a69514485c36442ea849063313e6db13e09Chris Lattner } 317e70829632f82de15db187845666aaca6e04b792Chris Lattner virtual const char *getOpcodeName() const { return "*end-of-list-inst*"; } 327e70829632f82de15db187845666aaca6e04b792Chris Lattner 337e70829632f82de15db187845666aaca6e04b792Chris Lattner // Methods for support type inquiry through isa, cast, and dyn_cast... 347e70829632f82de15db187845666aaca6e04b792Chris Lattner static inline bool classof(const DummyInst *) { return true; } 357e70829632f82de15db187845666aaca6e04b792Chris Lattner static inline bool classof(const Instruction *I) { 367e70829632f82de15db187845666aaca6e04b792Chris Lattner return I->getOpcode() == NumOtherOps; 377e70829632f82de15db187845666aaca6e04b792Chris Lattner } 387e70829632f82de15db187845666aaca6e04b792Chris Lattner static inline bool classof(const Value *V) { 397e70829632f82de15db187845666aaca6e04b792Chris Lattner return isa<Instruction>(V) && classof(cast<Instruction>(V)); 407e70829632f82de15db187845666aaca6e04b792Chris Lattner } 417e70829632f82de15db187845666aaca6e04b792Chris Lattner}; 427e70829632f82de15db187845666aaca6e04b792Chris Lattner 437e70829632f82de15db187845666aaca6e04b792Chris LattnerInstruction *ilist_traits<Instruction>::createNode() { 447e70829632f82de15db187845666aaca6e04b792Chris Lattner return new DummyInst(); 457e70829632f82de15db187845666aaca6e04b792Chris Lattner} 467e70829632f82de15db187845666aaca6e04b792Chris Lattneriplist<Instruction> &ilist_traits<Instruction>::getList(BasicBlock *BB) { 477e70829632f82de15db187845666aaca6e04b792Chris Lattner return BB->getInstList(); 487e70829632f82de15db187845666aaca6e04b792Chris Lattner} 497e70829632f82de15db187845666aaca6e04b792Chris Lattner 507e70829632f82de15db187845666aaca6e04b792Chris Lattner// Explicit instantiation of SymbolTableListTraits since some of the methods 517e70829632f82de15db187845666aaca6e04b792Chris Lattner// are not in the public header file... 527e70829632f82de15db187845666aaca6e04b792Chris Lattnertemplate SymbolTableListTraits<Instruction, BasicBlock, Function>; 537e70829632f82de15db187845666aaca6e04b792Chris Lattner 54009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 55bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner// BasicBlock ctor - If the function parameter is specified, the basic block is 56bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner// automatically inserted at the end of the function. 57bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner// 58b7653df0853f06112b741be09f1b7ae5a6aa6fdeChris LattnerBasicBlock::BasicBlock(const std::string &name, Function *Parent) 5908272fbdb2dd227346789d9d9c4243dffe1ea3a6Vikram S. Adve : Value(Type::LabelTy, Value::BasicBlockVal, name) { 607e70829632f82de15db187845666aaca6e04b792Chris Lattner // Initialize the instlist... 617e70829632f82de15db187845666aaca6e04b792Chris Lattner InstList.setItemParent(this); 627e70829632f82de15db187845666aaca6e04b792Chris Lattner 63d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner // Make sure that we get added to a function 64d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner LeakDetector::addGarbageObject(this); 65d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner 66a3d3c2b64545c00f70453642e5d84b028dfce671Chris Lattner if (Parent) 677e70829632f82de15db187845666aaca6e04b792Chris Lattner Parent->getBasicBlockList().push_back(this); 68009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 69009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 700a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner/// BasicBlock ctor - If the InsertBefore parameter is specified, the basic 710a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner/// block is automatically inserted right before the specified block. 720a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner/// 730a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris LattnerBasicBlock::BasicBlock(const std::string &Name, BasicBlock *InsertBefore) 740a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner : Value(Type::LabelTy, Value::BasicBlockVal, Name) { 750a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner // Initialize the instlist... 760a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner InstList.setItemParent(this); 770a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 780a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner // Make sure that we get added to a function 790a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner LeakDetector::addGarbageObject(this); 800a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 810a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner if (InsertBefore) { 820a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner assert(InsertBefore->getParent() && 830a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner "Cannot insert block before another block that is not embedded into" 840a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner " a function yet!"); 850a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner InsertBefore->getParent()->getBasicBlockList().insert(InsertBefore, this); 860a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner } 870a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner} 880a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 890a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 90009505452b713ed2e3a8e99c5545a6e721c65495Chris LattnerBasicBlock::~BasicBlock() { 91009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner dropAllReferences(); 927e70829632f82de15db187845666aaca6e04b792Chris Lattner InstList.clear(); 93009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 94009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 95bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattnervoid BasicBlock::setParent(Function *parent) { 96d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner if (getParent()) 97d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner LeakDetector::addGarbageObject(this); 98d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner 99bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner InstList.setParent(parent); 100d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner 101d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner if (getParent()) 102d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner LeakDetector::removeGarbageObject(this); 103bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner} 104bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner 105009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Specialize setName to take care of symbol table majik 106697954c15da58bd8b186dbafdedd8b06db770201Chris Lattnervoid BasicBlock::setName(const std::string &name, SymbolTable *ST) { 107b7653df0853f06112b741be09f1b7ae5a6aa6fdeChris Lattner Function *P; 1086892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattner assert((ST == 0 || (!getParent() || ST == getParent()->getSymbolTable())) && 1096892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattner "Invalid symtab argument!"); 110009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if ((P = getParent()) && hasName()) P->getSymbolTable()->remove(this); 111009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Value::setName(name); 112009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (P && hasName()) P->getSymbolTable()->insert(this); 113009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 114009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 115009505452b713ed2e3a8e99c5545a6e721c65495Chris LattnerTerminatorInst *BasicBlock::getTerminator() { 116009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 1177e70829632f82de15db187845666aaca6e04b792Chris Lattner return dyn_cast<TerminatorInst>(&InstList.back()); 118009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 119009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 120009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnerconst TerminatorInst *const BasicBlock::getTerminator() const { 121009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 1227e70829632f82de15db187845666aaca6e04b792Chris Lattner return dyn_cast<TerminatorInst>(&InstList.back()); 123009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 124009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 125009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnervoid BasicBlock::dropAllReferences() { 1267e70829632f82de15db187845666aaca6e04b792Chris Lattner for(iterator I = begin(), E = end(); I != E; ++I) 1277e70829632f82de15db187845666aaca6e04b792Chris Lattner I->dropAllReferences(); 128009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 129009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 130e9bb2df410f7a22decad9a883f7139d5857c1520Chris Lattner// hasConstantReferences() - This predicate is true if there is a 131009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// reference to this basic block in the constant pool for this method. For 132009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// example, if a block is reached through a switch table, that table resides 133009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// in the constant pool, and the basic block is reference from it. 134009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 135e9bb2df410f7a22decad9a883f7139d5857c1520Chris Lattnerbool BasicBlock::hasConstantReferences() const { 136009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner for (use_const_iterator I = use_begin(), E = use_end(); I != E; ++I) 13731bcdb822fe9133b1973de51519d34e5813a6184Chris Lattner if (::isa<Constant>((Value*)*I)) 138009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return true; 139009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 140009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return false; 141009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 142009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 143b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// removePredecessor - This method is used to notify a BasicBlock that the 144b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// specified Predecessor of the block is no longer able to reach it. This is 145b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// actually not used to update the Predecessor list, but is actually used to 146b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// update the PHI nodes that reside in the block. Note that this should be 147b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// called while the predecessor still refers to this block. 148b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// 149b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattnervoid BasicBlock::removePredecessor(BasicBlock *Pred) { 150455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner assert(find(pred_begin(this), pred_end(this), Pred) != pred_end(this) && 151b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner "removePredecessor: BB is not a predecessor!"); 152b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner if (!isa<PHINode>(front())) return; // Quick exit. 153b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 154455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner pred_iterator PI(pred_begin(this)), EI(pred_end(this)); 155b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner unsigned max_idx; 156b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 157b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // Loop over the rest of the predecessors until we run out, or until we find 158b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // out that there are more than 2 predecessors. 159b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner for (max_idx = 0; PI != EI && max_idx < 3; ++PI, ++max_idx) /*empty*/; 160b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 161b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If there are exactly two predecessors, then we want to nuke the PHI nodes 16287a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // altogether. We cannot do this, however if this in this case however: 16387a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // 16487a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // Loop: 16587a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // %x = phi [X, Loop] 16687a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1 16787a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // br Loop ;; %x2 does not dominate all uses 16887a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // 16987a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // This is because the PHI node input is actually taken from the predecessor 17087a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // basic block. The only case this can happen is with a self loop, so we 17187a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // check for this case explicitly now. 17287a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // 173b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 17487a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner if (max_idx == 2) { 17587a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner PI = pred_begin(this); 17687a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner BasicBlock *Other = *PI == Pred ? *++PI : *PI; 17787a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner 17887a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // Disable PHI elimination! 17987a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner if (this == Other) max_idx = 3; 18087a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner } 18187a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner 182b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner if (max_idx <= 2) { // <= Two predecessors BEFORE I remove one? 183b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner // Yup, loop through and nuke the PHI nodes 1847e70829632f82de15db187845666aaca6e04b792Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&front())) { 185b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner PN->removeIncomingValue(Pred); // Remove the predecessor first... 186b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 187b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner assert(PN->getNumIncomingValues() == max_idx-1 && 188b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner "PHI node shouldn't have this many values!!!"); 189b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 190b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 191b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner if (max_idx == 2) 192b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner PN->replaceAllUsesWith(PN->getOperand(0)); 19389d46b0f095cf7f536c6ad40b4541b73d259445fChris Lattner else // Otherwise there are no incoming values/edges, replace with dummy 19489d46b0f095cf7f536c6ad40b4541b73d259445fChris Lattner PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 1957e70829632f82de15db187845666aaca6e04b792Chris Lattner getInstList().pop_front(); // Remove the PHI node 196b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 197b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } else { 198b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // Okay, now we know that we need to remove predecessor #pred_idx from all 199b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // PHI nodes. Iterate over each PHI node fixing them up 2007e70829632f82de15db187845666aaca6e04b792Chris Lattner for (iterator II = begin(); PHINode *PN = dyn_cast<PHINode>(&*II); ++II) 20187a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner PN->removeIncomingValue(Pred); 202b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 203b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner} 204b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 205009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 206009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// splitBasicBlock - This splits a basic block into two at the specified 207009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// instruction. Note that all instructions BEFORE the specified iterator stay 208009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// as part of the original basic block, an unconditional branch is added to 209009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// the new BB, and the rest of the instructions in the BB are moved to the new 210009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// BB, including the old terminator. This invalidates the iterator. 211009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 212009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Note that this only works on well formed basic blocks (must have a 213009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// terminator), and 'I' must not be the end of instruction list (which would 214009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// cause a degenerate basic block to be formed, having a terminator inside of 215009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// the basic block). 216009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 2177fc9fe34390c66ca58646d09a87f7dbaacb6c1f8Chris LattnerBasicBlock *BasicBlock::splitBasicBlock(iterator I) { 218009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 219009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner assert(I != InstList.end() && 220009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner "Trying to get me to create degenerate basic block!"); 221009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 222009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner BasicBlock *New = new BasicBlock("", getParent()); 223009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 224009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // Go from the end of the basic block through to the iterator pointer, moving 225009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // to the new basic block... 226009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Instruction *Inst = 0; 227009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner do { 2287fc9fe34390c66ca58646d09a87f7dbaacb6c1f8Chris Lattner iterator EndIt = end(); 229009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Inst = InstList.remove(--EndIt); // Remove from end 230009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner New->InstList.push_front(Inst); // Add to front 2317e70829632f82de15db187845666aaca6e04b792Chris Lattner } while (Inst != &*I); // Loop until we move the specified instruction. 232009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 233009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // Add a branch instruction to the newly formed basic block. 234009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner InstList.push_back(new BranchInst(New)); 235e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner 236e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // Now we must loop through all of the successors of the New block (which 237e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // _were_ the successors of the 'this' block), and update any PHI nodes in 238e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // successors. If there were PHI nodes in the successors, then they need to 239e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // know that incoming branches will be from New, not from Old. 240e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // 241e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner for (BasicBlock::succ_iterator I = succ_begin(New), E = succ_end(New); 242e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner I != E; ++I) { 243e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // Loop over any phi nodes in the basic block, updating the BB field of 244e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // incoming values... 245e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner BasicBlock *Successor = *I; 246e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner for (BasicBlock::iterator II = Successor->begin(); 2477e70829632f82de15db187845666aaca6e04b792Chris Lattner PHINode *PN = dyn_cast<PHINode>(&*II); ++II) { 248e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner int IDX = PN->getBasicBlockIndex(this); 249e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner while (IDX != -1) { 250e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner PN->setIncomingBlock((unsigned)IDX, New); 251e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner IDX = PN->getBasicBlockIndex(this); 252e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 253e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 254e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 255009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return New; 256009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 257