SimplifyCFG.cpp revision f7703df4968084c18c248c1feea9961c19a32e6a
101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 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//===----------------------------------------------------------------------===// 901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 10bb190ac8dafdcc5e604da3695987d69ee8632195Chris Lattner// Peephole optimize the CFG. 1101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 1201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner//===----------------------------------------------------------------------===// 1301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 1401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Transforms/Utils/Local.h" 1501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Constant.h" 16dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner#include "llvm/Intrinsics.h" 1701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/iPHINode.h" 18dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner#include "llvm/iTerminators.h" 19dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner#include "llvm/iOther.h" 2001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Support/CFG.h" 2101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <algorithm> 2201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <functional> 23f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 24d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 25a3bbcb5b664c1c851b87392119608901b2e1837cMisha Brukman// PropagatePredecessors - This gets "Succ" ready to have the predecessors from 2601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// "BB". This is a little tricky because "Succ" has PHI nodes, which need to 2701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// have extra slots added to them to hold the merge edges from BB's 28e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// predecessors, and BB itself might have had PHI nodes in it. This function 29e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// returns true (failure) if the Succ BB already has a predecessor that is a 30cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman// predecessor of BB and incoming PHI arguments would not be discernible. 3101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 3201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// Assumption: Succ is the single successor for BB. 3301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 34a3bbcb5b664c1c851b87392119608901b2e1837cMisha Brukmanstatic bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 3501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 363abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner 373abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner if (!isa<PHINode>(Succ->front())) 383abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner return false; // We can make the transformation, no problem. 3901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 4001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If there is more than one predecessor, and there are PHI nodes in 4101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // the successor, then we need to add incoming edges for the PHI nodes 4201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 4301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 4401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 4501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Check to see if one of the predecessors of BB is already a predecessor of 46e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // Succ. If so, we cannot do the transformation if there are any PHI nodes 47e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // with incompatible values coming in from the two edges! 4801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 49e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI) 50e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner if (find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) { 51e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // Loop over all of the PHI nodes checking to see if there are 52e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // incompatible values coming in. 5346a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner for (BasicBlock::iterator I = Succ->begin(); 54e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) { 55e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // Loop up the entries in the PHI node for BB and for *PI if the values 56e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // coming in are non-equal, we cannot merge these two blocks (instead we 57e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // should insert a conditional move or something, then merge the 58e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // blocks). 59e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner int Idx1 = PN->getBasicBlockIndex(BB); 60e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner int Idx2 = PN->getBasicBlockIndex(*PI); 61e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner assert(Idx1 != -1 && Idx2 != -1 && 62e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner "Didn't have entries for my predecessors??"); 63e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2)) 64e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner return true; // Values are not equal... 65e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner } 66e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner } 6701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 6801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Loop over all of the PHI nodes in the successor BB 6901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for (BasicBlock::iterator I = Succ->begin(); 70e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) { 71bb190ac8dafdcc5e604da3695987d69ee8632195Chris Lattner Value *OldVal = PN->removeIncomingValue(BB, false); 7201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(OldVal && "No entry in PHI for Pred BB!"); 7301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 7446a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // If this incoming value is one of the PHI nodes in BB... 7546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 7646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner PHINode *OldValPN = cast<PHINode>(OldVal); 7746a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 7846a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner End = BBPreds.end(); PredI != End; ++PredI) { 7946a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner PN->addIncoming(OldValPN->getIncomingValueForBlock(*PredI), *PredI); 8046a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner } 8146a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner } else { 8246a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 8346a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner End = BBPreds.end(); PredI != End; ++PredI) { 8446a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // Add an incoming value for each of the new incoming values... 8546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner PN->addIncoming(OldVal, *PredI); 8646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner } 8701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 8801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 8901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return false; 9001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 9101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 9201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 9301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// SimplifyCFG - This function is used to do simplification of a CFG. For 9401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// example, it adjusts branches to branches to eliminate the extra hop, it 9501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// eliminates unreachable basic blocks, and does other "peephole" optimization 96e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// of the CFG. It returns true if a modification was made. 9701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 9801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// WARNING: The entry node of a function may not be simplified. 9901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 100f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::SimplifyCFG(BasicBlock *BB) { 101dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner bool Changed = false; 10201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner Function *M = BB->getParent(); 10301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 10401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB && BB->getParent() && "Block not embedded in function!"); 10501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB->getTerminator() && "Degenerate basic block encountered!"); 10618961504fc2b299578dba817900a0696cf3ccc4dChris Lattner assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 10701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 108dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner // Check to see if the first instruction in this block is just an 109dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner // 'llvm.unwind'. If so, replace any invoke instructions which use this as an 110dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner // exception destination with call instructions. 111dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner // 112ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) 113ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner if (BB->begin() == BasicBlock::iterator(UI)) { // Empty block? 114ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 115ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner while (!Preds.empty()) { 116ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner BasicBlock *Pred = Preds.back(); 117ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 118ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner if (II->getExceptionalDest() == BB) { 119ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // Insert a new branch instruction before the invoke, because this 120ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // is now a fall through... 121ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner BranchInst *BI = new BranchInst(II->getNormalDest(), II); 122ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner Pred->getInstList().remove(II); // Take out of symbol table 123ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner 124ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // Insert the call now... 125ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 126ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner CallInst *CI = new CallInst(II->getCalledValue(), Args, 127ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner II->getName(), BI); 128ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner // If the invoke produced a value, the Call now does instead 129ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner II->replaceAllUsesWith(CI); 130ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner delete II; 131ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner Changed = true; 132ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner } 133ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner 134ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner Preds.pop_back(); 135dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner } 136ee5457cbe88b7f691f774de8515d9a94226d1b00Chris Lattner } 137dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner 13801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove basic blocks that have no predecessors... which are unreachable. 13901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (pred_begin(BB) == pred_end(BB) && 14001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner !BB->hasConstantReferences()) { 14101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Removing BB: \n" << BB; 14201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 14301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Loop through all of our successors and make sure they know that one 14401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // of their predecessors is going away. 14501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for_each(succ_begin(BB), succ_end(BB), 14601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB)); 14701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 14801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner while (!BB->empty()) { 14918961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Instruction &I = BB->back(); 15001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If this instruction is used, replace uses with an arbitrary 15101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // constant value. Because control flow can't get here, we don't care 15201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // what we replace the value with. Note that since this block is 15301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // unreachable, and all values contained within it must dominate their 15401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // uses, that all uses will eventually be removed. 15518961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (!I.use_empty()) 15601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Make all users of this instruction reference the constant instead 15718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner I.replaceAllUsesWith(Constant::getNullValue(I.getType())); 15801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 15901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove the instruction from the basic block 16018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BB->getInstList().pop_back(); 16101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 16218961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 16301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 16401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 16501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 166694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // Check to see if we can constant propagate this terminator instruction 167694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // away... 168dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner Changed |= ConstantFoldTerminator(BB); 169694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 17046a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // Check to see if this block has no non-phi instructions and only a single 17146a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // successor. If so, replace references to this basic block with references 17246a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // to the successor. 17301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner succ_iterator SI(succ_begin(BB)); 17401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ? 17546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner 17646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 17746a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner while (isa<PHINode>(*BBI)) ++BBI; 17846a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner 17946a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner if (BBI->isTerminator()) { // Terminator is the only non-phi instruction! 18001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor 18101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 18201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (Succ != BB) { // Arg, don't hurt infinite loops! 18301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If our successor has PHI nodes, then we need to update them to 18401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // include entries for BB's predecessors, not for BB itself. 18501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Be careful though, if this transformation fails (returns true) then 18601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // we cannot do this transformation! 18701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 188a3bbcb5b664c1c851b87392119608901b2e1837cMisha Brukman if (!PropagatePredecessorsForPHIs(BB, Succ)) { 18901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Killing Trivial BB: \n" << BB; 19018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner std::string OldName = BB->getName(); 19118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 1923a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner std::vector<BasicBlock*> 1933a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 1943a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner 19546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // Move all PHI nodes in BB to Succ if they are alive, otherwise 19646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // delete them. 19746a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 19846a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner if (PN->use_empty()) 19946a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner BB->getInstList().erase(BB->begin()); // Nuke instruction... 20046a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner else { 20146a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // The instruction is alive, so this means that Succ must have 20246a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // *ONLY* had BB as a predecessor, and the PHI node is still valid 2033a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // now. Simply move it into Succ, because we know that BB 2043a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // strictly dominated Succ. 20546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner BB->getInstList().remove(BB->begin()); 20646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner Succ->getInstList().push_front(PN); 2073a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner 2083a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // We need to add new entries for the PHI node to account for 2093a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // predecessors of Succ that the PHI node does not take into 2103a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // account. At this point, since we know that BB dominated succ, 2113a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // this means that we should any newly added incoming edges should 2123a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // use the PHI node as the value for these edges, because they are 2133a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // loop back edges. 2143a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner 2153a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 2163a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner if (OldSuccPreds[i] != BB) 2173a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner PN->addIncoming(PN, OldSuccPreds[i]); 21846a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner } 21946a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner 2203a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // Everything that jumped to BB now goes to Succ... 2213a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner BB->replaceAllUsesWith(Succ); 2223a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner 22318961504fc2b299578dba817900a0696cf3ccc4dChris Lattner // Delete the old basic block... 22418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 22501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 22618961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can 22718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Succ->setName(OldName); 22801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 22901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Function after removal: \n" << M; 23001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 23101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 23201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 23301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 23401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 23501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 23601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Merge basic blocks into their predecessor if there is only one distinct 23701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // pred, and if there is only one distinct successor of the predecessor, and 23801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // if there are no PHI nodes. 23901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 24091b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner if (!BB->hasConstantReferences()) { 24101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 24201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BasicBlock *OnlyPred = *PI++; 24301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 24401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (*PI != OnlyPred) { 24501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner OnlyPred = 0; // There are multiple different predecessors... 24601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner break; 24701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 24801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 24901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BasicBlock *OnlySucc = 0; 250122558b05bb753894adc7d925f69dc9ddfa586faChris Lattner if (OnlyPred && OnlyPred != BB && // Don't break self loops 251122558b05bb753894adc7d925f69dc9ddfa586faChris Lattner OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 25201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Check to see if there is only one distinct successor... 25301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 25401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner OnlySucc = BB; 25501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for (; SI != SE; ++SI) 25601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (*SI != OnlySucc) { 25701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner OnlySucc = 0; // There are multiple distinct successors! 25801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner break; 25901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 26001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 26101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 26201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (OnlySucc) { 26301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Merging: " << BB << "into: " << OnlyPred; 26401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner TerminatorInst *Term = OnlyPred->getTerminator(); 26501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 26691b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner // Resolve any PHI nodes at the start of the block. They are all 267929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // guaranteed to have exactly one entry if they exist, unless there are 268929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // multiple duplicate (but guaranteed to be equal) entries for the 269929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // incoming edges. This occurs when there are multiple edges from 270929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // OnlyPred to OnlySucc. 27191b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner // 27291b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 27391b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 27491b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner BB->getInstList().pop_front(); // Delete the phi node... 27591b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner } 27691b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner 27701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Delete the unconditional branch from the predecessor... 27818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner OnlyPred->getInstList().pop_back(); 27901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 280cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Move all definitions in the successor to the predecessor... 28118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 28218961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 283cf00c4ab3ba308d45d98c5ccab87362cf802facbMisha Brukman // Make all PHI nodes that referred to BB now refer to Pred as their 28401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // source... 28501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BB->replaceAllUsesWith(OnlyPred); 28618961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 28718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner std::string OldName = BB->getName(); 28818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 28918961504fc2b299578dba817900a0696cf3ccc4dChris Lattner // Erase basic block from the function... 29018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 29118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 29201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Inherit predecessors name if it exists... 29318961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (!OldName.empty() && !OnlyPred->hasName()) 29418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner OnlyPred->setName(OldName); 29501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 29601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 29701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 29801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 29901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 300694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner return Changed; 30101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 302