BasicBlock.cpp revision 4f05611ed948ed1fb3e861d178aae18bd025ce1c
1d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner//===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 10b7653df0853f06112b741be09f1b7ae5a6aa6fdeChris Lattner// This file implements the BasicBlock class for the VMCore library. 11009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 12009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner//===----------------------------------------------------------------------===// 13009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 147e70829632f82de15db187845666aaca6e04b792Chris Lattner#include "llvm/BasicBlock.h" 15009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/iTerminators.h" 16009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/Type.h" 17455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner#include "llvm/Support/CFG.h" 1889d46b0f095cf7f536c6ad40b4541b73d259445fChris Lattner#include "llvm/Constant.h" 197061dc50b2513731d7b346ab16183cda4a44619fChris Lattner#include "llvm/iPHINode.h" 207e70829632f82de15db187845666aaca6e04b792Chris Lattner#include "llvm/SymbolTable.h" 21d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner#include "Support/LeakDetector.h" 227e70829632f82de15db187845666aaca6e04b792Chris Lattner#include "SymbolTableListTraitsImpl.h" 237e70829632f82de15db187845666aaca6e04b792Chris Lattner#include <algorithm> 24108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattnerusing namespace llvm; 25108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner 26108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattnernamespace { 27108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner /// DummyInst - An instance of this class is used to mark the end of the 28108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner /// instruction list. This is not a real instruction. 29108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner struct DummyInst : public Instruction { 30108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner DummyInst() : Instruction(Type::VoidTy, OtherOpsEnd) { 31108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner // This should not be garbage monitored. 32108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner LeakDetector::removeGarbageObject(this); 33108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner } 34009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 35108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner virtual Instruction *clone() const { 36108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner assert(0 && "Cannot clone EOL");abort(); 37108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner return 0; 38108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner } 39108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner virtual const char *getOpcodeName() const { return "*end-of-list-inst*"; } 407e70829632f82de15db187845666aaca6e04b792Chris Lattner 41108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner // Methods for support type inquiry through isa, cast, and dyn_cast... 42108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner static inline bool classof(const DummyInst *) { return true; } 43108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner static inline bool classof(const Instruction *I) { 44108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner return I->getOpcode() == OtherOpsEnd; 45108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner } 46108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner static inline bool classof(const Value *V) { 47108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner return isa<Instruction>(V) && classof(cast<Instruction>(V)); 48108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner } 49108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner }; 50108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner} 517e70829632f82de15db187845666aaca6e04b792Chris Lattner 527e70829632f82de15db187845666aaca6e04b792Chris LattnerInstruction *ilist_traits<Instruction>::createNode() { 537e70829632f82de15db187845666aaca6e04b792Chris Lattner return new DummyInst(); 547e70829632f82de15db187845666aaca6e04b792Chris Lattner} 557e70829632f82de15db187845666aaca6e04b792Chris Lattneriplist<Instruction> &ilist_traits<Instruction>::getList(BasicBlock *BB) { 567e70829632f82de15db187845666aaca6e04b792Chris Lattner return BB->getInstList(); 577e70829632f82de15db187845666aaca6e04b792Chris Lattner} 587e70829632f82de15db187845666aaca6e04b792Chris Lattner 597e70829632f82de15db187845666aaca6e04b792Chris Lattner// Explicit instantiation of SymbolTableListTraits since some of the methods 607e70829632f82de15db187845666aaca6e04b792Chris Lattner// are not in the public header file... 61e860e0d69c9c155704cd3c4b2533410a8c782d9eChris Lattnertemplate class SymbolTableListTraits<Instruction, BasicBlock, Function>; 627e70829632f82de15db187845666aaca6e04b792Chris Lattner 63009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 644f05611ed948ed1fb3e861d178aae18bd025ce1cChris LattnerBasicBlock::BasicBlock(const std::string &Name, Function *Parent, 654f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner BasicBlock *InsertBefore) 660a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner : Value(Type::LabelTy, Value::BasicBlockVal, Name) { 670a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner // Initialize the instlist... 680a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner InstList.setItemParent(this); 690a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 700a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner // Make sure that we get added to a function 710a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner LeakDetector::addGarbageObject(this); 720a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 730a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner if (InsertBefore) { 744f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner assert(Parent && 754f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner "Cannot insert block before another block with no function!"); 764f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner Parent->getBasicBlockList().insert(InsertBefore, this); 774f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner } else if (Parent) { 784f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner Parent->getBasicBlockList().push_back(this); 790a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner } 800a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner} 810a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 820a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 83009505452b713ed2e3a8e99c5545a6e721c65495Chris LattnerBasicBlock::~BasicBlock() { 84009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner dropAllReferences(); 857e70829632f82de15db187845666aaca6e04b792Chris Lattner InstList.clear(); 86009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 87009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 88bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattnervoid BasicBlock::setParent(Function *parent) { 89d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner if (getParent()) 90d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner LeakDetector::addGarbageObject(this); 91d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner 92bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner InstList.setParent(parent); 93d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner 94d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner if (getParent()) 95d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner LeakDetector::removeGarbageObject(this); 96bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner} 97bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner 98009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Specialize setName to take care of symbol table majik 99697954c15da58bd8b186dbafdedd8b06db770201Chris Lattnervoid BasicBlock::setName(const std::string &name, SymbolTable *ST) { 100b7653df0853f06112b741be09f1b7ae5a6aa6fdeChris Lattner Function *P; 1016e6026b46569b01f8f6d4dcdb6c899c3a9c76b3eChris Lattner assert((ST == 0 || (!getParent() || ST == &getParent()->getSymbolTable())) && 1026892b126e3d3b90f13744cc1a7c83fd7f8d615f2Chris Lattner "Invalid symtab argument!"); 1036e6026b46569b01f8f6d4dcdb6c899c3a9c76b3eChris Lattner if ((P = getParent()) && hasName()) P->getSymbolTable().remove(this); 104009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner Value::setName(name); 1056e6026b46569b01f8f6d4dcdb6c899c3a9c76b3eChris Lattner if (P && hasName()) P->getSymbolTable().insert(this); 106009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 107009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 108009505452b713ed2e3a8e99c5545a6e721c65495Chris LattnerTerminatorInst *BasicBlock::getTerminator() { 109009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 1107e70829632f82de15db187845666aaca6e04b792Chris Lattner return dyn_cast<TerminatorInst>(&InstList.back()); 111009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 112009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 113009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnerconst TerminatorInst *const BasicBlock::getTerminator() const { 114009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 1157e70829632f82de15db187845666aaca6e04b792Chris Lattner return dyn_cast<TerminatorInst>(&InstList.back()); 116009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 117009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 118009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnervoid BasicBlock::dropAllReferences() { 1197e70829632f82de15db187845666aaca6e04b792Chris Lattner for(iterator I = begin(), E = end(); I != E; ++I) 1207e70829632f82de15db187845666aaca6e04b792Chris Lattner I->dropAllReferences(); 121009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 122009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 123e9bb2df410f7a22decad9a883f7139d5857c1520Chris Lattner// hasConstantReferences() - This predicate is true if there is a 124009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// reference to this basic block in the constant pool for this method. For 125009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// example, if a block is reached through a switch table, that table resides 126009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// in the constant pool, and the basic block is reference from it. 127009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 128e9bb2df410f7a22decad9a883f7139d5857c1520Chris Lattnerbool BasicBlock::hasConstantReferences() const { 129009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner for (use_const_iterator I = use_begin(), E = use_end(); I != E; ++I) 130d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke if (isa<Constant>((Value*)*I)) 131009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return true; 132009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 133009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return false; 134009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 135009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 136b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// removePredecessor - This method is used to notify a BasicBlock that the 137b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// specified Predecessor of the block is no longer able to reach it. This is 138b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// actually not used to update the Predecessor list, but is actually used to 139b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// update the PHI nodes that reside in the block. Note that this should be 140b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// called while the predecessor still refers to this block. 141b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner// 142b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattnervoid BasicBlock::removePredecessor(BasicBlock *Pred) { 143455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner assert(find(pred_begin(this), pred_end(this), Pred) != pred_end(this) && 144b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner "removePredecessor: BB is not a predecessor!"); 145b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner if (!isa<PHINode>(front())) return; // Quick exit. 146b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 147455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner pred_iterator PI(pred_begin(this)), EI(pred_end(this)); 148b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner unsigned max_idx; 149b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 150b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // Loop over the rest of the predecessors until we run out, or until we find 151b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // out that there are more than 2 predecessors. 152b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner for (max_idx = 0; PI != EI && max_idx < 3; ++PI, ++max_idx) /*empty*/; 153b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 154b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If there are exactly two predecessors, then we want to nuke the PHI nodes 15587a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // altogether. We cannot do this, however if this in this case however: 15687a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // 15787a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // Loop: 15887a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // %x = phi [X, Loop] 15987a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1 16087a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // br Loop ;; %x2 does not dominate all uses 16187a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // 16287a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // This is because the PHI node input is actually taken from the predecessor 16387a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // basic block. The only case this can happen is with a self loop, so we 16487a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // check for this case explicitly now. 16587a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // 166b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 16787a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner if (max_idx == 2) { 16887a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner PI = pred_begin(this); 16987a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner BasicBlock *Other = *PI == Pred ? *++PI : *PI; 17087a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner 17187a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // Disable PHI elimination! 17287a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner if (this == Other) max_idx = 3; 17387a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner } 17487a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner 175b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner if (max_idx <= 2) { // <= Two predecessors BEFORE I remove one? 176b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner // Yup, loop through and nuke the PHI nodes 1777e70829632f82de15db187845666aaca6e04b792Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&front())) { 178b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner PN->removeIncomingValue(Pred); // Remove the predecessor first... 179b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 180b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 181dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner if (max_idx == 2) { 18202a78cf7eacf97f2c9584e29d02f77612aead35fChris Lattner if (PN->getOperand(0) != PN) 18302a78cf7eacf97f2c9584e29d02f77612aead35fChris Lattner PN->replaceAllUsesWith(PN->getOperand(0)); 18402a78cf7eacf97f2c9584e29d02f77612aead35fChris Lattner else 18502a78cf7eacf97f2c9584e29d02f77612aead35fChris Lattner // We are left with an infinite loop with no entries: kill the PHI. 18602a78cf7eacf97f2c9584e29d02f77612aead35fChris Lattner PN->replaceAllUsesWith(Constant::getNullValue(PN->getType())); 187dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner getInstList().pop_front(); // Remove the PHI node 188dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner } 189dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner 190dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner // If the PHI node already only had one entry, it got deleted by 191dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner // removeIncomingValue. 192b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 193b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } else { 194b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // Okay, now we know that we need to remove predecessor #pred_idx from all 195b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // PHI nodes. Iterate over each PHI node fixing them up 196e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner for (iterator II = begin(); PHINode *PN = dyn_cast<PHINode>(II); ++II) 19787a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner PN->removeIncomingValue(Pred); 198b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 199b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner} 200b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 201009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 202009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// splitBasicBlock - This splits a basic block into two at the specified 203009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// instruction. Note that all instructions BEFORE the specified iterator stay 204009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// as part of the original basic block, an unconditional branch is added to 205009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// the new BB, and the rest of the instructions in the BB are moved to the new 206009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// BB, including the old terminator. This invalidates the iterator. 207009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 208009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// Note that this only works on well formed basic blocks (must have a 209009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// terminator), and 'I' must not be the end of instruction list (which would 210009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// cause a degenerate basic block to be formed, having a terminator inside of 211009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// the basic block). 212009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner// 2134bd4aa5e3c41c0fc803e960252bb6fe75b804b1dChris LattnerBasicBlock *BasicBlock::splitBasicBlock(iterator I, const std::string &BBName) { 214009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 215009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner assert(I != InstList.end() && 216009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner "Trying to get me to create degenerate basic block!"); 217009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 2184f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner BasicBlock *New = new BasicBlock(BBName, getParent(), getNext()); 219009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 220f2c3106866137b0c06e99f453a83d9558c0c6934Chris Lattner // Move all of the specified instructions from the original basic block into 221f2c3106866137b0c06e99f453a83d9558c0c6934Chris Lattner // the new basic block. 222f2c3106866137b0c06e99f453a83d9558c0c6934Chris Lattner New->getInstList().splice(New->end(), this->getInstList(), I, end()); 223009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 224009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // Add a branch instruction to the newly formed basic block. 225108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner new BranchInst(New, this); 226e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner 227e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // Now we must loop through all of the successors of the New block (which 228e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // _were_ the successors of the 'this' block), and update any PHI nodes in 229e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // successors. If there were PHI nodes in the successors, then they need to 230e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // know that incoming branches will be from New, not from Old. 231e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // 2321c9ab515de41707c8e04a51694a50479068e891dChris Lattner for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) { 233e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // Loop over any phi nodes in the basic block, updating the BB field of 234e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // incoming values... 235e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner BasicBlock *Successor = *I; 236e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner for (BasicBlock::iterator II = Successor->begin(); 237e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner PHINode *PN = dyn_cast<PHINode>(II); ++II) { 238e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner int IDX = PN->getBasicBlockIndex(this); 239e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner while (IDX != -1) { 240e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner PN->setIncomingBlock((unsigned)IDX, New); 241e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner IDX = PN->getBasicBlockIndex(this); 242e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 243e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 244e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 245009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return New; 246009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 247