SimplifyCFG.cpp revision 694e37f08a7c09ccc24642532106295cf7b3a1e3
101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 3bb190ac8dafdcc5e604da3695987d69ee8632195Chris Lattner// Peephole optimize the CFG. 401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner//===----------------------------------------------------------------------===// 601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Transforms/Utils/Local.h" 801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Constant.h" 901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/iPHINode.h" 1001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Support/CFG.h" 1101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <algorithm> 1201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <functional> 1301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 14a3bbcb5b664c1c851b87392119608901b2e1837cMisha Brukman// PropagatePredecessors - This gets "Succ" ready to have the predecessors from 1501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// "BB". This is a little tricky because "Succ" has PHI nodes, which need to 1601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// have extra slots added to them to hold the merge edges from BB's 17e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// predecessors, and BB itself might have had PHI nodes in it. This function 18e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// returns true (failure) if the Succ BB already has a predecessor that is a 19e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// predecessor of BB and incoming PHI arguments would not be discernable. 2001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 2101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// Assumption: Succ is the single successor for BB. 2201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 23a3bbcb5b664c1c851b87392119608901b2e1837cMisha Brukmanstatic bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 2401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 253abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner 263abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner if (!isa<PHINode>(Succ->front())) 273abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner return false; // We can make the transformation, no problem. 2801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 2901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If there is more than one predecessor, and there are PHI nodes in 3001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // the successor, then we need to add incoming edges for the PHI nodes 3101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 3201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 3301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 3401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Check to see if one of the predecessors of BB is already a predecessor of 35e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // Succ. If so, we cannot do the transformation if there are any PHI nodes 36e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // with incompatible values coming in from the two edges! 3701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 38e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI) 39e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner if (find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) { 40e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // Loop over all of the PHI nodes checking to see if there are 41e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // incompatible values coming in. 4246a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner for (BasicBlock::iterator I = Succ->begin(); 43e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) { 44e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // Loop up the entries in the PHI node for BB and for *PI if the values 45e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // coming in are non-equal, we cannot merge these two blocks (instead we 46e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // should insert a conditional move or something, then merge the 47e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // blocks). 48e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner int Idx1 = PN->getBasicBlockIndex(BB); 49e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner int Idx2 = PN->getBasicBlockIndex(*PI); 50e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner assert(Idx1 != -1 && Idx2 != -1 && 51e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner "Didn't have entries for my predecessors??"); 52e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2)) 53e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner return true; // Values are not equal... 54e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner } 55e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner } 5601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 5701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Loop over all of the PHI nodes in the successor BB 5801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for (BasicBlock::iterator I = Succ->begin(); 59e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner PHINode *PN = dyn_cast<PHINode>(I); ++I) { 60bb190ac8dafdcc5e604da3695987d69ee8632195Chris Lattner Value *OldVal = PN->removeIncomingValue(BB, false); 6101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(OldVal && "No entry in PHI for Pred BB!"); 6201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 6346a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // If this incoming value is one of the PHI nodes in BB... 6446a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 6546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner PHINode *OldValPN = cast<PHINode>(OldVal); 6646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 6746a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner End = BBPreds.end(); PredI != End; ++PredI) { 6846a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner PN->addIncoming(OldValPN->getIncomingValueForBlock(*PredI), *PredI); 6946a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner } 7046a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner } else { 7146a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 7246a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner End = BBPreds.end(); PredI != End; ++PredI) { 7346a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // Add an incoming value for each of the new incoming values... 7446a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner PN->addIncoming(OldVal, *PredI); 7546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner } 7601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 7701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 7801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return false; 7901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 8001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 8101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 8201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// SimplifyCFG - This function is used to do simplification of a CFG. For 8301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// example, it adjusts branches to branches to eliminate the extra hop, it 8401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// eliminates unreachable basic blocks, and does other "peephole" optimization 85e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// of the CFG. It returns true if a modification was made. 8601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 8701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// WARNING: The entry node of a function may not be simplified. 8801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 8918961504fc2b299578dba817900a0696cf3ccc4dChris Lattnerbool SimplifyCFG(BasicBlock *BB) { 9001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner Function *M = BB->getParent(); 9101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 9201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB && BB->getParent() && "Block not embedded in function!"); 9301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB->getTerminator() && "Degenerate basic block encountered!"); 9418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 9501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 9601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove basic blocks that have no predecessors... which are unreachable. 9701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (pred_begin(BB) == pred_end(BB) && 9801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner !BB->hasConstantReferences()) { 9901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Removing BB: \n" << BB; 10001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 10101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Loop through all of our successors and make sure they know that one 10201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // of their predecessors is going away. 10301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for_each(succ_begin(BB), succ_end(BB), 10401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB)); 10501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 10601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner while (!BB->empty()) { 10718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Instruction &I = BB->back(); 10801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If this instruction is used, replace uses with an arbitrary 10901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // constant value. Because control flow can't get here, we don't care 11001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // what we replace the value with. Note that since this block is 11101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // unreachable, and all values contained within it must dominate their 11201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // uses, that all uses will eventually be removed. 11318961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (!I.use_empty()) 11401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Make all users of this instruction reference the constant instead 11518961504fc2b299578dba817900a0696cf3ccc4dChris Lattner I.replaceAllUsesWith(Constant::getNullValue(I.getType())); 11601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 11701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove the instruction from the basic block 11818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BB->getInstList().pop_back(); 11901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 12018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 12101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 12201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 12301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 124694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // Check to see if we can constant propagate this terminator instruction 125694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // away... 126694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner bool Changed = ConstantFoldTerminator(BB); 127694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 12846a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // Check to see if this block has no non-phi instructions and only a single 12946a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // successor. If so, replace references to this basic block with references 13046a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // to the successor. 13101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner succ_iterator SI(succ_begin(BB)); 13201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ? 13346a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner 13446a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 13546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner while (isa<PHINode>(*BBI)) ++BBI; 13646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner 13746a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner if (BBI->isTerminator()) { // Terminator is the only non-phi instruction! 13801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor 13901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 14001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (Succ != BB) { // Arg, don't hurt infinite loops! 14101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If our successor has PHI nodes, then we need to update them to 14201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // include entries for BB's predecessors, not for BB itself. 14301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Be careful though, if this transformation fails (returns true) then 14401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // we cannot do this transformation! 14501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 146a3bbcb5b664c1c851b87392119608901b2e1837cMisha Brukman if (!PropagatePredecessorsForPHIs(BB, Succ)) { 14701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Killing Trivial BB: \n" << BB; 14818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner std::string OldName = BB->getName(); 14918961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 1503a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner std::vector<BasicBlock*> 1513a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 1523a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner 15346a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // Move all PHI nodes in BB to Succ if they are alive, otherwise 15446a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // delete them. 15546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 15646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner if (PN->use_empty()) 15746a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner BB->getInstList().erase(BB->begin()); // Nuke instruction... 15846a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner else { 15946a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // The instruction is alive, so this means that Succ must have 16046a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // *ONLY* had BB as a predecessor, and the PHI node is still valid 1613a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // now. Simply move it into Succ, because we know that BB 1623a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // strictly dominated Succ. 16346a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner BB->getInstList().remove(BB->begin()); 16446a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner Succ->getInstList().push_front(PN); 1653a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner 1663a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // We need to add new entries for the PHI node to account for 1673a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // predecessors of Succ that the PHI node does not take into 1683a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // account. At this point, since we know that BB dominated succ, 1693a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // this means that we should any newly added incoming edges should 1703a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // use the PHI node as the value for these edges, because they are 1713a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // loop back edges. 1723a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner 1733a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 1743a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner if (OldSuccPreds[i] != BB) 1753a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner PN->addIncoming(PN, OldSuccPreds[i]); 17646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner } 17746a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner 1783a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // Everything that jumped to BB now goes to Succ... 1793a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner BB->replaceAllUsesWith(Succ); 1803a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner 18118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner // Delete the old basic block... 18218961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 18301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 18418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can 18518961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Succ->setName(OldName); 18601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 18701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Function after removal: \n" << M; 18801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 18901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 19001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 19101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 19201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 19301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 19401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Merge basic blocks into their predecessor if there is only one distinct 19501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // pred, and if there is only one distinct successor of the predecessor, and 19601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // if there are no PHI nodes. 19701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 19891b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner if (!BB->hasConstantReferences()) { 19901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 20001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BasicBlock *OnlyPred = *PI++; 20101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 20201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (*PI != OnlyPred) { 20301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner OnlyPred = 0; // There are multiple different predecessors... 20401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner break; 20501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 20601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 20701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BasicBlock *OnlySucc = 0; 208122558b05bb753894adc7d925f69dc9ddfa586faChris Lattner if (OnlyPred && OnlyPred != BB && // Don't break self loops 209122558b05bb753894adc7d925f69dc9ddfa586faChris Lattner OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 21001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Check to see if there is only one distinct successor... 21101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 21201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner OnlySucc = BB; 21301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for (; SI != SE; ++SI) 21401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (*SI != OnlySucc) { 21501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner OnlySucc = 0; // There are multiple distinct successors! 21601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner break; 21701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 21801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 21901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 22001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (OnlySucc) { 22101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner //cerr << "Merging: " << BB << "into: " << OnlyPred; 22201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner TerminatorInst *Term = OnlyPred->getTerminator(); 22301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 22491b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner // Resolve any PHI nodes at the start of the block. They are all 225929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // guaranteed to have exactly one entry if they exist, unless there are 226929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // multiple duplicate (but guaranteed to be equal) entries for the 227929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // incoming edges. This occurs when there are multiple edges from 228929b2c6900e20859f338d808a1a89ffc5b3563bbChris Lattner // OnlyPred to OnlySucc. 22991b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner // 23091b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 23191b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 23291b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner BB->getInstList().pop_front(); // Delete the phi node... 23391b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner } 23491b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner 23501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Delete the unconditional branch from the predecessor... 23618961504fc2b299578dba817900a0696cf3ccc4dChris Lattner OnlyPred->getInstList().pop_back(); 23701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 23801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Move all definitions in the succecessor to the predecessor... 23918961504fc2b299578dba817900a0696cf3ccc4dChris Lattner OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 24018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 24101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Make all PHI nodes that refered to BB now refer to Pred as their 24201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // source... 24301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner BB->replaceAllUsesWith(OnlyPred); 24418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 24518961504fc2b299578dba817900a0696cf3ccc4dChris Lattner std::string OldName = BB->getName(); 24618961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 24718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner // Erase basic block from the function... 24818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 24918961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 25001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Inherit predecessors name if it exists... 25118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (!OldName.empty() && !OnlyPred->hasName()) 25218961504fc2b299578dba817900a0696cf3ccc4dChris Lattner OnlyPred->setName(OldName); 25301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 25401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 25501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 25601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 25701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 258694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner return Changed; 25901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 260