BasicBlock.cpp revision 28962f353b16f34571b3ed3127f7e17e1c0a76f2
1d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner//===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 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. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 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" 153464547968b58dda0acbf6e0e192f03f66652848Chris Lattner#include "llvm/Constants.h" 1644336292fcd9f3f99cbfc2c3366bea0cf95bb675Misha Brukman#include "llvm/Instructions.h" 17009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner#include "llvm/Type.h" 18455889aa79e3463a4b0f2161e3d9d72a683268b6Chris Lattner#include "llvm/Support/CFG.h" 19551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/LeakDetector.h" 207e70829632f82de15db187845666aaca6e04b792Chris Lattner#include "SymbolTableListTraitsImpl.h" 217e70829632f82de15db187845666aaca6e04b792Chris Lattner#include <algorithm> 22108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattnerusing namespace llvm; 23108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner 24108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattnernamespace { 25108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner /// DummyInst - An instance of this class is used to mark the end of the 26108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner /// instruction list. This is not a real instruction. 27108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner struct DummyInst : public Instruction { 2896d83f63cdbb33c075901b1b84eb07622d86386fChris Lattner DummyInst() : Instruction(Type::VoidTy, OtherOpsEnd, 0, 0) { 29108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner // This should not be garbage monitored. 30108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner LeakDetector::removeGarbageObject(this); 31108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner } 32009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 33108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner virtual Instruction *clone() const { 34108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner assert(0 && "Cannot clone EOL");abort(); 35108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner return 0; 36108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner } 37108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner virtual const char *getOpcodeName() const { return "*end-of-list-inst*"; } 387e70829632f82de15db187845666aaca6e04b792Chris Lattner 39108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner // Methods for support type inquiry through isa, cast, and dyn_cast... 40108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner static inline bool classof(const DummyInst *) { return true; } 41108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner static inline bool classof(const Instruction *I) { 42108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner return I->getOpcode() == OtherOpsEnd; 43108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner } 44108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner static inline bool classof(const Value *V) { 45108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner return isa<Instruction>(V) && classof(cast<Instruction>(V)); 46108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner } 47108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner }; 48108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner} 497e70829632f82de15db187845666aaca6e04b792Chris Lattner 50bca81448ac8e19c588c9a4ad16fc70732b76327cChris LattnerInstruction *ilist_traits<Instruction>::createSentinel() { 517e70829632f82de15db187845666aaca6e04b792Chris Lattner return new DummyInst(); 527e70829632f82de15db187845666aaca6e04b792Chris Lattner} 537e70829632f82de15db187845666aaca6e04b792Chris Lattneriplist<Instruction> &ilist_traits<Instruction>::getList(BasicBlock *BB) { 547e70829632f82de15db187845666aaca6e04b792Chris Lattner return BB->getInstList(); 557e70829632f82de15db187845666aaca6e04b792Chris Lattner} 567e70829632f82de15db187845666aaca6e04b792Chris Lattner 577e70829632f82de15db187845666aaca6e04b792Chris Lattner// Explicit instantiation of SymbolTableListTraits since some of the methods 587e70829632f82de15db187845666aaca6e04b792Chris Lattner// are not in the public header file... 59e860e0d69c9c155704cd3c4b2533410a8c782d9eChris Lattnertemplate class SymbolTableListTraits<Instruction, BasicBlock, Function>; 607e70829632f82de15db187845666aaca6e04b792Chris Lattner 61009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 624f05611ed948ed1fb3e861d178aae18bd025ce1cChris LattnerBasicBlock::BasicBlock(const std::string &Name, Function *Parent, 634f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner BasicBlock *InsertBefore) 640a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner : Value(Type::LabelTy, Value::BasicBlockVal, Name) { 650a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner // Initialize the instlist... 660a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner InstList.setItemParent(this); 670a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 680a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner // Make sure that we get added to a function 690a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner LeakDetector::addGarbageObject(this); 700a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 710a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner if (InsertBefore) { 724f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner assert(Parent && 734f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner "Cannot insert block before another block with no function!"); 744f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner Parent->getBasicBlockList().insert(InsertBefore, this); 754f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner } else if (Parent) { 764f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner Parent->getBasicBlockList().push_back(this); 770a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner } 780a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner} 790a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 800a1a874d1f4659f02c0d4fdd6be69f1188bd0625Chris Lattner 81009505452b713ed2e3a8e99c5545a6e721c65495Chris LattnerBasicBlock::~BasicBlock() { 82ea51deb18a60d37e546909af4aa95ca6f2c5d56fMisha Brukman assert(getParent() == 0 && "BasicBlock still linked into the program!"); 83009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner dropAllReferences(); 847e70829632f82de15db187845666aaca6e04b792Chris Lattner InstList.clear(); 85009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 86009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 87bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattnervoid BasicBlock::setParent(Function *parent) { 88d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner if (getParent()) 89d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner LeakDetector::addGarbageObject(this); 90d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner 91bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner InstList.setParent(parent); 92d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner 93d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner if (getParent()) 94d1e693f2a3883dacf213aa2b477540c57b53b714Chris Lattner LeakDetector::removeGarbageObject(this); 95bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner} 96bded132d00ed626a6541b67ad101ef0fd47d3491Chris Lattner 974b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattnervoid BasicBlock::removeFromParent() { 984b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner getParent()->getBasicBlockList().remove(this); 994b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner} 1004b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner 1014b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattnervoid BasicBlock::eraseFromParent() { 1024b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner getParent()->getBasicBlockList().erase(this); 1034b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner} 1044b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner 1056a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattner/// moveBefore - Unlink this instruction from its current function and 1066a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattner/// insert it into the function that MovePos lives in, right before 1076a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattner/// MovePos. 1086a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattnervoid BasicBlock::moveBefore(BasicBlock *MovePos) { 1096a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattner MovePos->getParent()->getBasicBlockList().splice(MovePos, 1106a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattner getParent()->getBasicBlockList(), this); 1116a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattner} 1126a13aed525f586fc8f475ce17ce7f6cf77ddd2f4Chris Lattner 1134b83380f330b1c77bb9b4ad8f63bdcf1a596afd6Chris Lattner 114009505452b713ed2e3a8e99c5545a6e721c65495Chris LattnerTerminatorInst *BasicBlock::getTerminator() { 115009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 1167e70829632f82de15db187845666aaca6e04b792Chris Lattner return dyn_cast<TerminatorInst>(&InstList.back()); 117009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 118009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 119009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnerconst TerminatorInst *const BasicBlock::getTerminator() const { 120009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner if (InstList.empty()) return 0; 1217e70829632f82de15db187845666aaca6e04b792Chris Lattner return dyn_cast<TerminatorInst>(&InstList.back()); 122009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 123009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 124dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir PrusInstruction* BasicBlock::getFirstNonPHI() 125dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir Prus{ 12628962f353b16f34571b3ed3127f7e17e1c0a76f2Vladimir Prus BasicBlock::iterator i = begin(); 127dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir Prus // All valid basic blocks should have a terminator, 128dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir Prus // which is not a PHINode. If we have invalid basic 129dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir Prus // block we'll get assert when dereferencing past-the-end 130dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir Prus // iterator. 131dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir Prus while (isa<PHINode>(i)) ++i; 132dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir Prus return &*i; 133dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir Prus} 134dd49dbfe44098eb53b1ac29f017e422147572bbbVladimir Prus 135009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattnervoid BasicBlock::dropAllReferences() { 1367e70829632f82de15db187845666aaca6e04b792Chris Lattner for(iterator I = begin(), E = end(); I != E; ++I) 1377e70829632f82de15db187845666aaca6e04b792Chris Lattner I->dropAllReferences(); 138009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 139009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 140ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner/// getSinglePredecessor - If this basic block has a single predecessor block, 141ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner/// return the block, otherwise return a null pointer. 142ad993cbb77b26b36cee938686b3377c0d92abd5eChris LattnerBasicBlock *BasicBlock::getSinglePredecessor() { 143ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner pred_iterator PI = pred_begin(this), E = pred_end(this); 144ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner if (PI == E) return 0; // No preds. 145ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner BasicBlock *ThePred = *PI; 146ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner ++PI; 147ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner return (PI == E) ? ThePred : 0 /*multiple preds*/; 148ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner} 149ad993cbb77b26b36cee938686b3377c0d92abd5eChris Lattner 150566f600779d8c28a81bb08951ec1962fe34322abChris Lattner/// removePredecessor - This method is used to notify a BasicBlock that the 151566f600779d8c28a81bb08951ec1962fe34322abChris Lattner/// specified Predecessor of the block is no longer able to reach it. This is 152fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// actually not used to update the Predecessor list, but is actually used to 153566f600779d8c28a81bb08951ec1962fe34322abChris Lattner/// update the PHI nodes that reside in the block. Note that this should be 154566f600779d8c28a81bb08951ec1962fe34322abChris Lattner/// called while the predecessor still refers to this block. 155566f600779d8c28a81bb08951ec1962fe34322abChris Lattner/// 1563464547968b58dda0acbf6e0e192f03f66652848Chris Lattnervoid BasicBlock::removePredecessor(BasicBlock *Pred, 1573464547968b58dda0acbf6e0e192f03f66652848Chris Lattner bool DontDeleteUselessPHIs) { 1581f21ef1511ce003fc177121b980e783b83992f82Chris Lattner assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs. 15935f0aecdb012ba150953f6f3a98862be9c72d265Chris Lattner find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) && 1609d80930e950214d026afd3a3d18cda32629efdb9Jeff Cohen "removePredecessor: BB is not a predecessor!"); 16135f0aecdb012ba150953f6f3a98862be9c72d265Chris Lattner 162f23586c7efe615d061c00c24cf62f03f7962776fChris Lattner if (InstList.empty()) return; 163a9e7781b3b8e457946491529816feab73c66d774Chris Lattner PHINode *APN = dyn_cast<PHINode>(&front()); 164a9e7781b3b8e457946491529816feab73c66d774Chris Lattner if (!APN) return; // Quick exit. 165b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 166b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If there are exactly two predecessors, then we want to nuke the PHI nodes 167a9e7781b3b8e457946491529816feab73c66d774Chris Lattner // altogether. However, we cannot do this, if this in this case: 16887a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // 16987a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // Loop: 17087a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // %x = phi [X, Loop] 17187a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1 17287a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // br Loop ;; %x2 does not dominate all uses 17387a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // 17487a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // This is because the PHI node input is actually taken from the predecessor 175fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // basic block. The only case this can happen is with a self loop, so we 17687a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // check for this case explicitly now. 177fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // 178a9e7781b3b8e457946491529816feab73c66d774Chris Lattner unsigned max_idx = APN->getNumIncomingValues(); 179b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); 18087a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner if (max_idx == 2) { 181a9e7781b3b8e457946491529816feab73c66d774Chris Lattner BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred); 18287a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner 18387a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner // Disable PHI elimination! 18487a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner if (this == Other) max_idx = 3; 18587a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner } 18687a09b10f8e03182e9edcb6e9ee8386f4a5d8daeChris Lattner 1873464547968b58dda0acbf6e0e192f03f66652848Chris Lattner // <= Two predecessors BEFORE I remove one? 1883464547968b58dda0acbf6e0e192f03f66652848Chris Lattner if (max_idx <= 2 && !DontDeleteUselessPHIs) { 189b00c582b6d40e6b9ff2d1ed4f5eaf7930e792aceChris Lattner // Yup, loop through and nuke the PHI nodes 1907e70829632f82de15db187845666aaca6e04b792Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&front())) { 1913464547968b58dda0acbf6e0e192f03f66652848Chris Lattner // Remove the predecessor first. 1923464547968b58dda0acbf6e0e192f03f66652848Chris Lattner PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs); 193b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 194b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // If the PHI _HAD_ two uses, replace PHI node with its now *single* value 195dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner if (max_idx == 2) { 19602a78cf7eacf97f2c9584e29d02f77612aead35fChris Lattner if (PN->getOperand(0) != PN) 19702a78cf7eacf97f2c9584e29d02f77612aead35fChris Lattner PN->replaceAllUsesWith(PN->getOperand(0)); 19802a78cf7eacf97f2c9584e29d02f77612aead35fChris Lattner else 19902a78cf7eacf97f2c9584e29d02f77612aead35fChris Lattner // We are left with an infinite loop with no entries: kill the PHI. 2003464547968b58dda0acbf6e0e192f03f66652848Chris Lattner PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 201dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner getInstList().pop_front(); // Remove the PHI node 202dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner } 203dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner 204dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner // If the PHI node already only had one entry, it got deleted by 205dee430d26e14a3d7c8d86688d49ac8b116aa044fChris Lattner // removeIncomingValue. 206b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 207b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } else { 208b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // Okay, now we know that we need to remove predecessor #pred_idx from all 209b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner // PHI nodes. Iterate over each PHI node fixing them up 210f878218c972dc570eb50e739c2ee2b9dd75ee5ddChris Lattner PHINode *PN; 21180f4d88a97e1b925c2ea67f932dd9c3ce1df1f8dChris Lattner for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) { 21280f4d88a97e1b925c2ea67f932dd9c3ce1df1f8dChris Lattner ++II; 2133464547968b58dda0acbf6e0e192f03f66652848Chris Lattner PN->removeIncomingValue(Pred, false); 214a83ba0f5c934e2cdbb5724cab365ecc0b5aae6c6Nate Begeman // If all incoming values to the Phi are the same, we can replace the Phi 215a83ba0f5c934e2cdbb5724cab365ecc0b5aae6c6Nate Begeman // with that value. 2161325b42a7dc38e99e1aa3531395d1678b31d3c55Chris Lattner if (Value *PNV = PN->hasConstantValue()) { 2171325b42a7dc38e99e1aa3531395d1678b31d3c55Chris Lattner PN->replaceAllUsesWith(PNV); 2181325b42a7dc38e99e1aa3531395d1678b31d3c55Chris Lattner PN->eraseFromParent(); 2191325b42a7dc38e99e1aa3531395d1678b31d3c55Chris Lattner } 220a83ba0f5c934e2cdbb5724cab365ecc0b5aae6c6Nate Begeman } 221b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner } 222b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner} 223b47af25099cac5c59795d6f1eb3b7cf9f962b32fChris Lattner 224009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 2250f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// splitBasicBlock - This splits a basic block into two at the specified 2260f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// instruction. Note that all instructions BEFORE the specified iterator stay 227fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// as part of the original basic block, an unconditional branch is added to 2280f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// the new BB, and the rest of the instructions in the BB are moved to the new 2290f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// BB, including the old terminator. This invalidates the iterator. 2300f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// 231fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// Note that this only works on well formed basic blocks (must have a 2320f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// terminator), and 'I' must not be the end of instruction list (which would 2330f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// cause a degenerate basic block to be formed, having a terminator inside of 234fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// the basic block). 2350f67dd6237eb7227aa58e9b77cd95f354989b891Chris Lattner/// 2364bd4aa5e3c41c0fc803e960252bb6fe75b804b1dChris LattnerBasicBlock *BasicBlock::splitBasicBlock(iterator I, const std::string &BBName) { 237009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!"); 238fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman assert(I != InstList.end() && 2399d80930e950214d026afd3a3d18cda32629efdb9Jeff Cohen "Trying to get me to create degenerate basic block!"); 240009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 2414f05611ed948ed1fb3e861d178aae18bd025ce1cChris Lattner BasicBlock *New = new BasicBlock(BBName, getParent(), getNext()); 242009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 243f2c3106866137b0c06e99f453a83d9558c0c6934Chris Lattner // Move all of the specified instructions from the original basic block into 244f2c3106866137b0c06e99f453a83d9558c0c6934Chris Lattner // the new basic block. 245f2c3106866137b0c06e99f453a83d9558c0c6934Chris Lattner New->getInstList().splice(New->end(), this->getInstList(), I, end()); 246009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner 247009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner // Add a branch instruction to the newly formed basic block. 248108e4ab159b59a616b0868e396dc7ddc1fb48616Chris Lattner new BranchInst(New, this); 249e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner 250e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // Now we must loop through all of the successors of the New block (which 251e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // _were_ the successors of the 'this' block), and update any PHI nodes in 252e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // successors. If there were PHI nodes in the successors, then they need to 253e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // know that incoming branches will be from New, not from Old. 254e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // 2551c9ab515de41707c8e04a51694a50479068e891dChris Lattner for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) { 256e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // Loop over any phi nodes in the basic block, updating the BB field of 257e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner // incoming values... 258e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner BasicBlock *Successor = *I; 259f878218c972dc570eb50e739c2ee2b9dd75ee5ddChris Lattner PHINode *PN; 260e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner for (BasicBlock::iterator II = Successor->begin(); 2619bf2a926cbdf05c5b412ec35e72908a08a4cf34bChris Lattner (PN = dyn_cast<PHINode>(II)); ++II) { 262e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner int IDX = PN->getBasicBlockIndex(this); 263e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner while (IDX != -1) { 264e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner PN->setIncomingBlock((unsigned)IDX, New); 265e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner IDX = PN->getBasicBlockIndex(this); 266e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 267e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 268e8e320d2faa997605c76a7c3ab9e9b4fb578e8c0Chris Lattner } 269009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner return New; 270009505452b713ed2e3a8e99c5545a6e721c65495Chris Lattner} 271