SimplifyCFG.cpp revision 37dc938bbe556a9414d063196d367c2f75d07d95
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 14218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner#define DEBUG_TYPE "simplifycfg" 1501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Transforms/Utils/Local.h" 16723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner#include "llvm/Constants.h" 17723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner#include "llvm/Instructions.h" 180d56008f53587531718ec36af82cc24576580b36Chris Lattner#include "llvm/Type.h" 1901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Support/CFG.h" 20551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 2101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <algorithm> 2201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <functional> 23d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner#include <set> 24698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner#include <map> 25f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 26d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 270d56008f53587531718ec36af82cc24576580b36Chris Lattner// PropagatePredecessorsForPHIs - This gets "Succ" ready to have the 280d56008f53587531718ec36af82cc24576580b36Chris Lattner// predecessors from "BB". This is a little tricky because "Succ" has PHI 290d56008f53587531718ec36af82cc24576580b36Chris Lattner// nodes, which need to have extra slots added to them to hold the merge edges 300d56008f53587531718ec36af82cc24576580b36Chris Lattner// from BB's predecessors, and BB itself might have had PHI nodes in it. This 310d56008f53587531718ec36af82cc24576580b36Chris Lattner// function returns true (failure) if the Succ BB already has a predecessor that 320d56008f53587531718ec36af82cc24576580b36Chris Lattner// is a predecessor of BB and incoming PHI arguments would not be discernible. 3301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 3401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// Assumption: Succ is the single successor for BB. 3501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 36a3bbcb5b664c1c851b87392119608901b2e1837cMisha Brukmanstatic bool PropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 3701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 383abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner 393abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner if (!isa<PHINode>(Succ->front())) 403abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner return false; // We can make the transformation, no problem. 4101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 4201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If there is more than one predecessor, and there are PHI nodes in 4301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // the successor, then we need to add incoming edges for the PHI nodes 4401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 4501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 4601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 4701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Check to see if one of the predecessors of BB is already a predecessor of 48e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // Succ. If so, we cannot do the transformation if there are any PHI nodes 49e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // with incompatible values coming in from the two edges! 5001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 51e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); PI != PE; ++PI) 5220aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos if (std::find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) { 53e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // Loop over all of the PHI nodes checking to see if there are 54e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // incompatible values coming in. 552da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 562da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 57e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // Loop up the entries in the PHI node for BB and for *PI if the values 58e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // coming in are non-equal, we cannot merge these two blocks (instead we 59e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // should insert a conditional move or something, then merge the 60e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // blocks). 61e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner int Idx1 = PN->getBasicBlockIndex(BB); 62e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner int Idx2 = PN->getBasicBlockIndex(*PI); 63e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner assert(Idx1 != -1 && Idx2 != -1 && 64e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner "Didn't have entries for my predecessors??"); 65e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner if (PN->getIncomingValue(Idx1) != PN->getIncomingValue(Idx2)) 66e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner return true; // Values are not equal... 67e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner } 68e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner } 6901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 70218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner // Loop over all of the PHI nodes in the successor BB. 712da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 722da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 73bb190ac8dafdcc5e604da3695987d69ee8632195Chris Lattner Value *OldVal = PN->removeIncomingValue(BB, false); 7401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(OldVal && "No entry in PHI for Pred BB!"); 7501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 76218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner // If this incoming value is one of the PHI nodes in BB, the new entries in 77218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner // the PHI node are the entries from the old PHI. 7846a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 7946a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner PHINode *OldValPN = cast<PHINode>(OldVal); 80218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 81218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner PN->addIncoming(OldValPN->getIncomingValue(i), 82218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner OldValPN->getIncomingBlock(i)); 8346a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner } else { 8446a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 8546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner End = BBPreds.end(); PredI != End; ++PredI) { 8646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // Add an incoming value for each of the new incoming values... 8746a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner PN->addIncoming(OldVal, *PredI); 8846a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner } 8901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 9001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 9101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return false; 9201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 9301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 94723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// GetIfCondition - Given a basic block (BB) with two predecessors (and 95723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// presumably PHI nodes in it), check to see if the merge at this block is due 96723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// to an "if condition". If so, return the boolean condition that determines 97723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// which entry into BB will be taken. Also, return by references the block 98723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// that will be entered from if the condition is true, and the block that will 99723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// be entered if the condition is false. 100723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// 101723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// 102723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattnerstatic Value *GetIfCondition(BasicBlock *BB, 103723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 104723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 105723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner "Function can only handle blocks with 2 predecessors!"); 106723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *Pred1 = *pred_begin(BB); 107723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *Pred2 = *++pred_begin(BB); 108723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 109723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // We can only handle branches. Other control flow will be lowered to 110723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // branches if possible anyway. 111723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (!isa<BranchInst>(Pred1->getTerminator()) || 112723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner !isa<BranchInst>(Pred2->getTerminator())) 113723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 114723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 115723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 116723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 117723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Eliminate code duplication by ensuring that Pred1Br is conditional if 118723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // either are. 119723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred2Br->isConditional()) { 120723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If both branches are conditional, we don't have an "if statement". In 121723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // reality, we could transform this case, but since the condition will be 122723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // required anyway, we stand no chance of eliminating it, so the xform is 123723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // probably not profitable. 124723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->isConditional()) 125723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 126723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 127723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner std::swap(Pred1, Pred2); 128723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner std::swap(Pred1Br, Pred2Br); 129723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 130723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 131723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->isConditional()) { 132723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If we found a conditional branch predecessor, make sure that it branches 133723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 134723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->getSuccessor(0) == BB && 135723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Pred1Br->getSuccessor(1) == Pred2) { 136723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred1; 137723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred2; 138723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else if (Pred1Br->getSuccessor(0) == Pred2 && 139723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Pred1Br->getSuccessor(1) == BB) { 140723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred2; 141723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred1; 142723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else { 143723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // We know that one arm of the conditional goes to BB, so the other must 144723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // go somewhere unrelated, and this must not be an "if statement". 145723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 146723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 147723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 148723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // The only thing we have to watch out for here is to make sure that Pred2 149723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // doesn't have incoming edges from other blocks. If it does, the condition 150723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // doesn't dominate BB. 151723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (++pred_begin(Pred2) != pred_end(Pred2)) 152723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 153723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 154723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return Pred1Br->getCondition(); 155723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 156723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 157723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Ok, if we got here, both predecessors end with an unconditional branch to 158723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // BB. Don't panic! If both blocks only have a single (identical) 159723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // predecessor, and THAT is a conditional branch, then we're all ok! 160723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (pred_begin(Pred1) == pred_end(Pred1) || 161723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner ++pred_begin(Pred1) != pred_end(Pred1) || 162723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner pred_begin(Pred2) == pred_end(Pred2) || 163723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner ++pred_begin(Pred2) != pred_end(Pred2) || 164723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner *pred_begin(Pred1) != *pred_begin(Pred2)) 165723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 166723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 167723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Otherwise, if this is a conditional branch, then we can use it! 168723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *CommonPred = *pred_begin(Pred1); 169723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 170723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner assert(BI->isConditional() && "Two successors but not conditional?"); 171723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (BI->getSuccessor(0) == Pred1) { 172723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred1; 173723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred2; 174723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else { 175723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred2; 176723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred1; 177723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 178723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return BI->getCondition(); 179723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 180723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 181723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner} 182723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 183723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 184723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// If we have a merge point of an "if condition" as accepted above, return true 185723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// if the specified value dominates the block. We don't handle the true 186723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// generality of domination here, just a special case which works well enough 187723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// for us. 1889c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// 1899c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 1909c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// see if V (which must be an instruction) is cheap to compute and is 1919c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// non-trapping. If both are true, the instruction is inserted into the set and 1929c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// true is returned. 1939c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattnerstatic bool DominatesMergePoint(Value *V, BasicBlock *BB, 1949c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner std::set<Instruction*> *AggressiveInsts) { 195570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 196570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (!I) return true; // Non-instructions all dominate instructions. 197570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner BasicBlock *PBB = I->getParent(); 198570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 199570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // We don't want to allow wierd loops that might have the "if condition" in 200570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // the bottom of this block. 201570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (PBB == BB) return false; 202570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 203570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // If this instruction is defined in a block that contains an unconditional 204570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // branch to BB, then it must be in the 'conditional' part of the "if 205570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // statement". 206570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator())) 207570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { 2089c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!AggressiveInsts) return false; 209570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Okay, it looks like the instruction IS in the "condition". Check to 210570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // see if its a cheap instruction to unconditionally compute, and if it 211570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // only uses stuff defined outside of the condition. If so, hoist it out. 212570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner switch (I->getOpcode()) { 213570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner default: return false; // Cannot hoist this out safely. 214570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Load: 215570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // We can hoist loads that are non-volatile and obviously cannot trap. 216570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (cast<LoadInst>(I)->isVolatile()) 217570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 218570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (!isa<AllocaInst>(I->getOperand(0)) && 219460f16c6253928519689e882a4dbb7f236f33294Reid Spencer !isa<Constant>(I->getOperand(0))) 220570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 221570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 222570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Finally, we have to check to make sure there are no instructions 223570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // before the load in its basic block, as we are going to hoist the loop 224570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // out to its predecessor. 225570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (PBB->begin() != BasicBlock::iterator(I)) 226570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 227570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner break; 228570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Add: 229570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Sub: 230570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::And: 231570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Or: 232570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Xor: 233570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Shl: 234570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Shr: 235570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner break; // These are all cheap and non-trapping instructions. 236570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner } 237570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 238570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Okay, we can only really hoist these out if their operands are not 239570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // defined in the conditional region. 240570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 2419c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!DominatesMergePoint(I->getOperand(i), BB, 0)) 242570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 2439c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Okay, it's safe to do this! Remember this instruction. 2449c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner AggressiveInsts->insert(I); 245570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner } 246723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 247723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return true; 248723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner} 24901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 2500d56008f53587531718ec36af82cc24576580b36Chris Lattner// GatherConstantSetEQs - Given a potentially 'or'd together collection of seteq 2510d56008f53587531718ec36af82cc24576580b36Chris Lattner// instructions that compare a value against a constant, return the value being 2520d56008f53587531718ec36af82cc24576580b36Chris Lattner// compared, and stick the constant into the Values vector. 2531654cff8e80acdddf5e5f2261595007878924aacChris Lattnerstatic Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values){ 2540d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Instruction *Inst = dyn_cast<Instruction>(V)) 2550d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Inst->getOpcode() == Instruction::SetEQ) { 2561654cff8e80acdddf5e5f2261595007878924aacChris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 2570d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 2580d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 2591654cff8e80acdddf5e5f2261595007878924aacChris Lattner } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 2600d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 2610d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(1); 2620d56008f53587531718ec36af82cc24576580b36Chris Lattner } 2630d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::Or) { 2640d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 2650d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 2660d56008f53587531718ec36af82cc24576580b36Chris Lattner if (LHS == RHS) 2670d56008f53587531718ec36af82cc24576580b36Chris Lattner return LHS; 2680d56008f53587531718ec36af82cc24576580b36Chris Lattner } 2690d56008f53587531718ec36af82cc24576580b36Chris Lattner return 0; 2700d56008f53587531718ec36af82cc24576580b36Chris Lattner} 2710d56008f53587531718ec36af82cc24576580b36Chris Lattner 2720d56008f53587531718ec36af82cc24576580b36Chris Lattner// GatherConstantSetNEs - Given a potentially 'and'd together collection of 2730d56008f53587531718ec36af82cc24576580b36Chris Lattner// setne instructions that compare a value against a constant, return the value 2740d56008f53587531718ec36af82cc24576580b36Chris Lattner// being compared, and stick the constant into the Values vector. 2751654cff8e80acdddf5e5f2261595007878924aacChris Lattnerstatic Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values){ 2760d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Instruction *Inst = dyn_cast<Instruction>(V)) 2770d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Inst->getOpcode() == Instruction::SetNE) { 2781654cff8e80acdddf5e5f2261595007878924aacChris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 2790d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 2800d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 2811654cff8e80acdddf5e5f2261595007878924aacChris Lattner } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 2820d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 2830d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(1); 2840d56008f53587531718ec36af82cc24576580b36Chris Lattner } 2850d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::Cast) { 2860d56008f53587531718ec36af82cc24576580b36Chris Lattner // Cast of X to bool is really a comparison against zero. 2870d56008f53587531718ec36af82cc24576580b36Chris Lattner assert(Inst->getType() == Type::BoolTy && "Can only handle bool values!"); 2881654cff8e80acdddf5e5f2261595007878924aacChris Lattner Values.push_back(ConstantInt::get(Inst->getOperand(0)->getType(), 0)); 2890d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 2900d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::And) { 2910d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 2920d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 2930d56008f53587531718ec36af82cc24576580b36Chris Lattner if (LHS == RHS) 2940d56008f53587531718ec36af82cc24576580b36Chris Lattner return LHS; 2950d56008f53587531718ec36af82cc24576580b36Chris Lattner } 2960d56008f53587531718ec36af82cc24576580b36Chris Lattner return 0; 2970d56008f53587531718ec36af82cc24576580b36Chris Lattner} 2980d56008f53587531718ec36af82cc24576580b36Chris Lattner 2990d56008f53587531718ec36af82cc24576580b36Chris Lattner 3000d56008f53587531718ec36af82cc24576580b36Chris Lattner 3010d56008f53587531718ec36af82cc24576580b36Chris Lattner/// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 3020d56008f53587531718ec36af82cc24576580b36Chris Lattner/// bunch of comparisons of one value against constants, return the value and 3030d56008f53587531718ec36af82cc24576580b36Chris Lattner/// the constants being compared. 3040d56008f53587531718ec36af82cc24576580b36Chris Lattnerstatic bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 3051654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::vector<ConstantInt*> &Values) { 3060d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Cond->getOpcode() == Instruction::Or) { 3070d56008f53587531718ec36af82cc24576580b36Chris Lattner CompVal = GatherConstantSetEQs(Cond, Values); 3080d56008f53587531718ec36af82cc24576580b36Chris Lattner 3090d56008f53587531718ec36af82cc24576580b36Chris Lattner // Return true to indicate that the condition is true if the CompVal is 3100d56008f53587531718ec36af82cc24576580b36Chris Lattner // equal to one of the constants. 3110d56008f53587531718ec36af82cc24576580b36Chris Lattner return true; 3120d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Cond->getOpcode() == Instruction::And) { 3130d56008f53587531718ec36af82cc24576580b36Chris Lattner CompVal = GatherConstantSetNEs(Cond, Values); 3140d56008f53587531718ec36af82cc24576580b36Chris Lattner 3150d56008f53587531718ec36af82cc24576580b36Chris Lattner // Return false to indicate that the condition is false if the CompVal is 3160d56008f53587531718ec36af82cc24576580b36Chris Lattner // equal to one of the constants. 3170d56008f53587531718ec36af82cc24576580b36Chris Lattner return false; 3180d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3190d56008f53587531718ec36af82cc24576580b36Chris Lattner return false; 3200d56008f53587531718ec36af82cc24576580b36Chris Lattner} 3210d56008f53587531718ec36af82cc24576580b36Chris Lattner 3220d56008f53587531718ec36af82cc24576580b36Chris Lattner/// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and 3230d56008f53587531718ec36af82cc24576580b36Chris Lattner/// has no side effects, nuke it. If it uses any instructions that become dead 3240d56008f53587531718ec36af82cc24576580b36Chris Lattner/// because the instruction is now gone, nuke them too. 3250d56008f53587531718ec36af82cc24576580b36Chris Lattnerstatic void ErasePossiblyDeadInstructionTree(Instruction *I) { 3260d56008f53587531718ec36af82cc24576580b36Chris Lattner if (isInstructionTriviallyDead(I)) { 3270d56008f53587531718ec36af82cc24576580b36Chris Lattner std::vector<Value*> Operands(I->op_begin(), I->op_end()); 3280d56008f53587531718ec36af82cc24576580b36Chris Lattner I->getParent()->getInstList().erase(I); 3290d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Operands.size(); i != e; ++i) 3300d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Instruction *OpI = dyn_cast<Instruction>(Operands[i])) 3310d56008f53587531718ec36af82cc24576580b36Chris Lattner ErasePossiblyDeadInstructionTree(OpI); 3320d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3330d56008f53587531718ec36af82cc24576580b36Chris Lattner} 3340d56008f53587531718ec36af82cc24576580b36Chris Lattner 335d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// SafeToMergeTerminators - Return true if it is safe to merge these two 336d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// terminator instructions together. 337d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// 338d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattnerstatic bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 339d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (SI1 == SI2) return false; // Can't merge with self! 340d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner 341d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner // It is not safe to merge these two switch instructions if they have a common 3422636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner // successor, and if that successor has a PHI node, and if *that* PHI node has 343d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner // conflicting incoming values from the two switch blocks. 344d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner BasicBlock *SI1BB = SI1->getParent(); 345d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner BasicBlock *SI2BB = SI2->getParent(); 346d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 347d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner 348d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 349d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (SI1Succs.count(*I)) 350d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner for (BasicBlock::iterator BBI = (*I)->begin(); 3512da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer isa<PHINode>(BBI); ++BBI) { 3522da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(BBI); 353d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (PN->getIncomingValueForBlock(SI1BB) != 354d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner PN->getIncomingValueForBlock(SI2BB)) 355d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner return false; 3562da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer } 357d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner 358d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner return true; 359d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner} 360d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner 361d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 362d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// now be entries in it from the 'NewPred' block. The values that will be 363d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// flowing into the PHI nodes will be the same as those coming in from 3642636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner/// ExistPred, an existing predecessor of Succ. 365d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattnerstatic void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 366d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner BasicBlock *ExistPred) { 367d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 368d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 369d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 370d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner 3712da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 3722da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 373d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner Value *V = PN->getIncomingValueForBlock(ExistPred); 374d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner PN->addIncoming(V, NewPred); 375d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner } 376d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner} 377d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner 378542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// isValueEqualityComparison - Return true if the specified terminator checks to 379542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// see if a value is equal to constant integer value. 380542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic Value *isValueEqualityComparison(TerminatorInst *TI) { 3814bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 3824bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner // Do not permit merging of large switch instructions into their 3834bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner // predecessors unless there is only one predecessor. 3844bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), 3854bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner pred_end(SI->getParent())) > 128) 3864bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner return 0; 3874bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner 388542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SI->getCondition(); 3894bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner } 390542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 391542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (BI->isConditional() && BI->getCondition()->hasOneUse()) 392542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition())) 393542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if ((SCI->getOpcode() == Instruction::SetEQ || 394542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner SCI->getOpcode() == Instruction::SetNE) && 395542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner isa<ConstantInt>(SCI->getOperand(1))) 396542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SCI->getOperand(0); 397542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return 0; 398542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 399542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 400542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// Given a value comparison instruction, decode all of the 'cases' that it 401542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// represents and return the 'default' block. 402542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic BasicBlock * 403542f149f00afaf1125b8f2040cad4fe05ed24c3aChris LattnerGetValueEqualityComparisonCases(TerminatorInst *TI, 404542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, 405542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock*> > &Cases) { 406542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 407542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Cases.reserve(SI->getNumCases()); 408542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 409542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Cases.push_back(std::make_pair(cast<ConstantInt>(SI->getCaseValue(i)), 410542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner SI->getSuccessor(i))); 411542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SI->getDefaultDest(); 412542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 413542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 414542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BranchInst *BI = cast<BranchInst>(TI); 415542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner SetCondInst *SCI = cast<SetCondInst>(BI->getCondition()); 416542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Cases.push_back(std::make_pair(cast<ConstantInt>(SCI->getOperand(1)), 417542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BI->getSuccessor(SCI->getOpcode() == 418542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Instruction::SetNE))); 419542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return BI->getSuccessor(SCI->getOpcode() == Instruction::SetEQ); 420542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 421542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 422542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 423542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// FoldValueComparisonIntoPredecessors - The specified terminator is a value 424542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// equality comparison instruction (either a switch or a branch on "X == c"). 425542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// See if any of the predecessors of the terminator block are value comparisons 426542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// on the same value. If so, and if safe to do so, fold them together. 427542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 428542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *BB = TI->getParent(); 429542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Value *CV = isValueEqualityComparison(TI); // CondVal 430542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner assert(CV && "Not a comparison?"); 431542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner bool Changed = false; 432542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 433542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 434542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner while (!Preds.empty()) { 435542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *Pred = Preds.back(); 436542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Preds.pop_back(); 437542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 438542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // See if the predecessor is a comparison with the same value. 439542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner TerminatorInst *PTI = Pred->getTerminator(); 440542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 441542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 442542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 443542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Figure out which 'cases' to copy from SI to PSI. 444542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 445542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 446542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 447542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 448542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 449542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 450542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Based on whether the default edge from PTI goes to BB or not, fill in 451542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // PredCases and PredDefault with the new switch cases we would like to 452542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // build. 453542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<BasicBlock*> NewSuccessors; 454542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 455542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredDefault == BB) { 456542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is the default destination from PTI, only the edges in TI 457542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // that don't occur in PTI, or that branch to BB will be activated. 458542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::set<ConstantInt*> PTIHandled; 459542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 460542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredCases[i].second != BB) 461542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.insert(PredCases[i].first); 462542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner else { 463542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // The default destination is BB, we don't need explicit targets. 464542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::swap(PredCases[i], PredCases.back()); 465542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.pop_back(); 466542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner --i; --e; 467542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 468542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 469542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Reconstruct the new switch statement we will be building. 470542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredDefault != BBDefault) { 471542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredDefault->removePredecessor(Pred); 472542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredDefault = BBDefault; 473542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBDefault); 474542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 475542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 476542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (!PTIHandled.count(BBCases[i].first) && 477542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BBCases[i].second != BBDefault) { 478542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(BBCases[i]); 479542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBCases[i].second); 480542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 481542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 482542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } else { 483542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is not the default destination from PSI, only the edges 484542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // in SI that occur in PSI with a destination of BB will be 485542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // activated. 486542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::set<ConstantInt*> PTIHandled; 487542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 488542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredCases[i].second == BB) { 489542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.insert(PredCases[i].first); 490542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::swap(PredCases[i], PredCases.back()); 491542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.pop_back(); 492542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner --i; --e; 493542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 494542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 495542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, now we know which constants were sent to BB from the 496542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // predecessor. Figure out where they will all go now. 497542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 498542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PTIHandled.count(BBCases[i].first)) { 499542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is one we are capable of getting... 500542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(BBCases[i]); 501542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBCases[i].second); 502542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.erase(BBCases[i].first);// This constant is taken care of 503542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 504542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 505542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If there are any constants vectored to BB that TI doesn't handle, 506542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // they must go to the default destination of TI. 507542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (std::set<ConstantInt*>::iterator I = PTIHandled.begin(), 508542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner E = PTIHandled.end(); I != E; ++I) { 509542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(std::make_pair(*I, BBDefault)); 510542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBDefault); 511542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 512542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 513542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 514542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, at this point, we know which new successor Pred will get. Make 515542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // sure we update the number of entries in the PHI nodes for these 516542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // successors. 517542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 518542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 519542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 520542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Now that the successors are updated, create the new Switch instruction. 521542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner SwitchInst *NewSI = new SwitchInst(CV, PredDefault, PTI); 522542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 523542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSI->addCase(PredCases[i].first, PredCases[i].second); 524542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Pred->getInstList().erase(PTI); 525542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 526542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, last check. If BB is still a successor of PSI, then we must 527542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // have an infinite loop case. If so, add an infinitely looping block 528542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // to handle the case to preserve the behavior of the code. 529542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *InfLoopBlock = 0; 530542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 531542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (NewSI->getSuccessor(i) == BB) { 532542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (InfLoopBlock == 0) { 533542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Insert it at the end of the loop, because it's either code, 534542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // or it won't matter if it's hot. :) 535542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner InfLoopBlock = new BasicBlock("infloop", BB->getParent()); 536542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner new BranchInst(InfLoopBlock, InfLoopBlock); 537542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 538542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSI->setSuccessor(i, InfLoopBlock); 539542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 540542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 541542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Changed = true; 542542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 543542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 544542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return Changed; 545542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 546542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 54737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// HoistThenElseCodeToIf - Given a conditional branch that codes to BB1 and 54837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// BB2, hoist any common code in the two blocks up into the branch block. The 54937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// caller of this function guarantees that BI's block dominates BB1 and BB2. 55037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattnerstatic bool HoistThenElseCodeToIf(BranchInst *BI) { 55137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // This does very trivial matching, with limited scanning, to find identical 55237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // instructions in the two blocks. In particular, we don't want to get into 55337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 55437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // such, we currently just scan for obviously identical instructions in an 55537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // identical order. 55637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 55737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 55837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 55937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Instruction *I1 = BB1->begin(), *I2 = BB2->begin(); 56037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (I1->getOpcode() != I2->getOpcode() || !I1->isIdenticalTo(I2)) 56137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return false; 56237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 56337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // If we get here, we can hoist at least one instruction. 56437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BIParent = BI->getParent(); 56537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner bool Hoisted = false; 56637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 56737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner do { 56837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // If we are hoisting the terminator instruction, don't move one (making a 56937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // broken BB), instead clone it, and remove BI. 57037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (isa<TerminatorInst>(I1)) 57137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner goto HoistTerminator; 57237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 57337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // For a normal instruction, we just move one to right before the branch, 57437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // then replace all uses of the other with the first. Finally, we remove 57537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // the now redundant second instruction. 57637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 57737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (!I2->use_empty()) 57837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2->replaceAllUsesWith(I1); 57937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BB2->getInstList().erase(I2); 58037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 58137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I1 = BB1->begin(); 58237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2 = BB2->begin(); 58337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Hoisted = true; 58437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } while (I1->getOpcode() == I2->getOpcode() && I1->isIdenticalTo(I2)); 58537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 58637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return true; 58737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 58837dc938bbe556a9414d063196d367c2f75d07d95Chris LattnerHoistTerminator: 58937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Okay, it is safe to hoist the terminator. 59037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Instruction *NT = I1->clone(); 59137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BIParent->getInstList().insert(BI, NT); 59237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (NT->getType() != Type::VoidTy) { 59337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I1->replaceAllUsesWith(NT); 59437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2->replaceAllUsesWith(NT); 59537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner NT->setName(I1->getName()); 59637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 59737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 59837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Hoisting one of the terminators from our successor is a great thing. 59937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Unfortunately, the successors of the if/else blocks may have PHI nodes in 60037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 60137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // nodes, so we insert select instruction to compute the final result. 60237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 60337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 60437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PHINode *PN; 60537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (BasicBlock::iterator BBI = SI->begin(); 60637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PN = dyn_cast<PHINode>(BBI); ++BBI) { 60737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Value *BB1V = PN->getIncomingValueForBlock(BB1); 60837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Value *BB2V = PN->getIncomingValueForBlock(BB2); 60937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (BB1V != BB2V) { 61037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // These values do not agree. Insert a select instruction before NT 61137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // that determines the right value. 61237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 61337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (SI == 0) 61437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner SI = new SelectInst(BI->getCondition(), BB1V, BB2V, 61537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BB1V->getName()+"."+BB2V->getName(), NT); 61637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Make the PHI node use the select for all incoming values for BB1/BB2 61737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 61837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 61937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PN->setIncomingValue(i, SI); 62037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 62137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 62237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 62337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 62437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Update any PHI nodes in our new successors. 62537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 62637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner AddPredecessorToBlock(*SI, BIParent, BB1); 62737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 62837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BI->eraseFromParent(); 62937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return true; 63037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner} 63137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 6321654cff8e80acdddf5e5f2261595007878924aacChris Lattnernamespace { 6331654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// ConstantIntOrdering - This class implements a stable ordering of constant 6341654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// integers that does not depend on their address. This is important for 6351654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// applications that sort ConstantInt's to ensure uniqueness. 6361654cff8e80acdddf5e5f2261595007878924aacChris Lattner struct ConstantIntOrdering { 6371654cff8e80acdddf5e5f2261595007878924aacChris Lattner bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 6381654cff8e80acdddf5e5f2261595007878924aacChris Lattner return LHS->getRawValue() < RHS->getRawValue(); 6391654cff8e80acdddf5e5f2261595007878924aacChris Lattner } 6401654cff8e80acdddf5e5f2261595007878924aacChris Lattner }; 6411654cff8e80acdddf5e5f2261595007878924aacChris Lattner} 6421654cff8e80acdddf5e5f2261595007878924aacChris Lattner 643542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 64401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// SimplifyCFG - This function is used to do simplification of a CFG. For 64501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// example, it adjusts branches to branches to eliminate the extra hop, it 64601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// eliminates unreachable basic blocks, and does other "peephole" optimization 647e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// of the CFG. It returns true if a modification was made. 64801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 64901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// WARNING: The entry node of a function may not be simplified. 65001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 651f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::SimplifyCFG(BasicBlock *BB) { 652dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner bool Changed = false; 65301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner Function *M = BB->getParent(); 65401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 65501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB && BB->getParent() && "Block not embedded in function!"); 65601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB->getTerminator() && "Degenerate basic block encountered!"); 65718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 65801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 65901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove basic blocks that have no predecessors... which are unreachable. 660d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (pred_begin(BB) == pred_end(BB) || 661d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner *pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB)) { 66230b434476796cd4a85c02914687d22f2e5ec95caChris Lattner DEBUG(std::cerr << "Removing BB: \n" << *BB); 66301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 66401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Loop through all of our successors and make sure they know that one 66501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // of their predecessors is going away. 66601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner for_each(succ_begin(BB), succ_end(BB), 66701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner std::bind2nd(std::mem_fun(&BasicBlock::removePredecessor), BB)); 66801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 66901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner while (!BB->empty()) { 67018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Instruction &I = BB->back(); 67101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If this instruction is used, replace uses with an arbitrary 67201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // constant value. Because control flow can't get here, we don't care 67301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // what we replace the value with. Note that since this block is 67401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // unreachable, and all values contained within it must dominate their 67501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // uses, that all uses will eventually be removed. 67618961504fc2b299578dba817900a0696cf3ccc4dChris Lattner if (!I.use_empty()) 67701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Make all users of this instruction reference the constant instead 67818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner I.replaceAllUsesWith(Constant::getNullValue(I.getType())); 67901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 68001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove the instruction from the basic block 68118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BB->getInstList().pop_back(); 68201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 68318961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 68401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 68501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 68601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 687694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // Check to see if we can constant propagate this terminator instruction 688694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // away... 689dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner Changed |= ConstantFoldTerminator(BB); 690694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 69146a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // Check to see if this block has no non-phi instructions and only a single 69246a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // successor. If so, replace references to this basic block with references 69346a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // to the successor. 69401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner succ_iterator SI(succ_begin(BB)); 69501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner if (SI != succ_end(BB) && ++SI == succ_end(BB)) { // One succ? 69646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 69746a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner while (isa<PHINode>(*BBI)) ++BBI; 69846a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner 699bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner BasicBlock *Succ = *succ_begin(BB); // There is exactly one successor. 700bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner if (BBI->isTerminator() && // Terminator is the only non-phi instruction! 701bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner Succ != BB) { // Don't hurt infinite loops! 702bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner // If our successor has PHI nodes, then we need to update them to include 703bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner // entries for BB's predecessors, not for BB itself. Be careful though, 704bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner // if this transformation fails (returns true) then we cannot do this 705bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner // transformation! 706bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner // 707bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner if (!PropagatePredecessorsForPHIs(BB, Succ)) { 708bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner DEBUG(std::cerr << "Killing Trivial BB: \n" << *BB); 709bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner 710bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner if (isa<PHINode>(&BB->front())) { 7113a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner std::vector<BasicBlock*> 7123a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 713bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner 71446a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // Move all PHI nodes in BB to Succ if they are alive, otherwise 71546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // delete them. 71646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 71746a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner if (PN->use_empty()) 718bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner BB->getInstList().erase(BB->begin()); // Nuke instruction. 71946a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner else { 72046a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // The instruction is alive, so this means that Succ must have 72146a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner // *ONLY* had BB as a predecessor, and the PHI node is still valid 7223a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // now. Simply move it into Succ, because we know that BB 7233a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // strictly dominated Succ. 72446a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner BB->getInstList().remove(BB->begin()); 72546a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner Succ->getInstList().push_front(PN); 726bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner 7273a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // We need to add new entries for the PHI node to account for 7283a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // predecessors of Succ that the PHI node does not take into 7293a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // account. At this point, since we know that BB dominated succ, 7303a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // this means that we should any newly added incoming edges should 7313a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // use the PHI node as the value for these edges, because they are 7323a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner // loop back edges. 7333a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 7343a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner if (OldSuccPreds[i] != BB) 7353a43837d859bddfdc24bc0c2d87669a6300c7bfeChris Lattner PN->addIncoming(PN, OldSuccPreds[i]); 73646a5f1f6e4a3be3d53b4e0016b78d108a2353f4cChris Lattner } 737bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner } 738bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner 739bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner // Everything that jumped to BB now goes to Succ. 740bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner std::string OldName = BB->getName(); 741bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner BB->replaceAllUsesWith(Succ); 742bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner BB->eraseFromParent(); // Delete the old basic block. 743bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner 744bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can 745bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner Succ->setName(OldName); 746bfd3e527015f55d144adf44af94028db61dd6269Chris Lattner return true; 74701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 74801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 74901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 75001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 75119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If this is a returning block with only PHI nodes in it, fold the return 75219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // instruction into any unconditional branch predecessors. 753147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // 754147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // If any predecessor is a conditional branch that just selects among 755147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // different return values, fold the replace the branch/return with a select 756147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // and return. 75719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 75819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BasicBlock::iterator BBI = BB->getTerminator(); 75919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BBI == BB->begin() || isa<PHINode>(--BBI)) { 760147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Find predecessors that end with branches. 76119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner std::vector<BasicBlock*> UncondBranchPreds; 762147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner std::vector<BranchInst*> CondBranchPreds; 76319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 76419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner TerminatorInst *PTI = (*PI)->getTerminator(); 76519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 76619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BI->isUnconditional()) 76719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner UncondBranchPreds.push_back(*PI); 768147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner else 769147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner CondBranchPreds.push_back(BI); 77019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 77119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 77219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we found some, do the transformation! 77319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (!UncondBranchPreds.empty()) { 77419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner while (!UncondBranchPreds.empty()) { 77519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BasicBlock *Pred = UncondBranchPreds.back(); 77619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner UncondBranchPreds.pop_back(); 77719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Instruction *UncondBranch = Pred->getTerminator(); 77819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Clone the return and add it to the end of the predecessor. 77919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Instruction *NewRet = RI->clone(); 78019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().push_back(NewRet); 78119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 78219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If the return instruction returns a value, and if the value was a 78319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // PHI node in "BB", propagate the right value into the return. 78419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (NewRet->getNumOperands() == 1) 78519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0))) 78619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (PN->getParent() == BB) 78719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred)); 78819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Update any PHI nodes in the returning block to realize that we no 78919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // longer branch to them. 79019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BB->removePredecessor(Pred); 79119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().erase(UncondBranch); 79219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 79319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 79419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we eliminated all predecessors of the block, delete the block now. 79519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (pred_begin(BB) == pred_end(BB)) 79619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // We know there are no successors, so just nuke the block. 79719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner M->getBasicBlockList().erase(BB); 79819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 79919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner return true; 80019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 801147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 802147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check out all of the conditional branches going to this return 803147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // instruction. If any of them just select between returns, change the 804147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // branch itself into a select/return pair. 805147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner while (!CondBranchPreds.empty()) { 806147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BranchInst *BI = CondBranchPreds.back(); 807147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner CondBranchPreds.pop_back(); 808147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *TrueSucc = BI->getSuccessor(0); 809147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *FalseSucc = BI->getSuccessor(1); 810147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *OtherSucc = TrueSucc == BB ? FalseSucc : TrueSucc; 811147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 812147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check to see if the non-BB successor is also a return block. 813147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (isa<ReturnInst>(OtherSucc->getTerminator())) { 814147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check to see if there are only PHI instructions in this block. 815147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock::iterator OSI = OtherSucc->getTerminator(); 816147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (OSI == OtherSucc->begin() || isa<PHINode>(--OSI)) { 817147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Okay, we found a branch that is going to two return nodes. If 818147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // there is no return value for this function, just change the 819147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // branch into a return. 820147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (RI->getNumOperands() == 0) { 821147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner TrueSucc->removePredecessor(BI->getParent()); 822147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner FalseSucc->removePredecessor(BI->getParent()); 823147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner new ReturnInst(0, BI); 824147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BI->getParent()->getInstList().erase(BI); 825147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner return true; 826147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 827147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 828147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Otherwise, figure out what the true and false return values are 829147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // so we can insert a new select instruction. 830147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner Value *TrueValue = TrueSucc->getTerminator()->getOperand(0); 831147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner Value *FalseValue = FalseSucc->getTerminator()->getOperand(0); 832147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 833147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Unwrap any PHI nodes in the return blocks. 834147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue)) 835147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (TVPN->getParent() == TrueSucc) 836147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 837147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue)) 838147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (FVPN->getParent() == FalseSucc) 839147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 840147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 8417aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner TrueSucc->removePredecessor(BI->getParent()); 8427aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner FalseSucc->removePredecessor(BI->getParent()); 8437aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner 844147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Insert a new select instruction. 8450ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner Value *NewRetVal; 8460ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner Value *BrCond = BI->getCondition(); 8470ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (TrueValue != FalseValue) 8480ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner NewRetVal = new SelectInst(BrCond, TrueValue, 8490ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner FalseValue, "retval", BI); 8500ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner else 8510ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner NewRetVal = TrueValue; 8520ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner 853147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner new ReturnInst(NewRetVal, BI); 854147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BI->getParent()->getInstList().erase(BI); 8550ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (BrCond->use_empty()) 8560ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (Instruction *BrCondI = dyn_cast<Instruction>(BrCond)) 8570ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner BrCondI->getParent()->getInstList().erase(BrCondI); 858147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner return true; 859147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 860147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 861147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 86219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 863e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->begin())) { 864e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Check to see if the first instruction in this block is just an unwind. 865e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // If so, replace any invoke instructions which use this as an exception 866af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner // destination with call instructions, and any unconditional branch 867af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner // predecessor with an unwind. 868e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // 869e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 870e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner while (!Preds.empty()) { 871e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner BasicBlock *Pred = Preds.back(); 872af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) { 873af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner if (BI->isUnconditional()) { 874af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner Pred->getInstList().pop_back(); // nuke uncond branch 875af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner new UnwindInst(Pred); // Use unwind. 876af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner Changed = true; 877af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner } 878af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 879e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner if (II->getUnwindDest() == BB) { 880e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Insert a new branch instruction before the invoke, because this 881e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // is now a fall through... 882e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner BranchInst *BI = new BranchInst(II->getNormalDest(), II); 883e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Pred->getInstList().remove(II); // Take out of symbol table 884e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner 885e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Insert the call now... 886e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 887e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner CallInst *CI = new CallInst(II->getCalledValue(), Args, 888e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner II->getName(), BI); 889e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // If the invoke produced a value, the Call now does instead 890e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner II->replaceAllUsesWith(CI); 891e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner delete II; 892e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Changed = true; 893e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 894e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner 895e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Preds.pop_back(); 896e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 8978e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 8988e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // If this block is now dead, remove it. 8998e509dd5e81e92a466580ab4022994079952cca9Chris Lattner if (pred_begin(BB) == pred_end(BB)) { 9008e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // We know there are no successors, so just nuke the block. 9018e509dd5e81e92a466580ab4022994079952cca9Chris Lattner M->getBasicBlockList().erase(BB); 9028e509dd5e81e92a466580ab4022994079952cca9Chris Lattner return true; 9038e509dd5e81e92a466580ab4022994079952cca9Chris Lattner } 9048e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 905d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->begin())) { 9067acd1ccb8a61217f8c06b5fbdcc9785437bd0989Chris Lattner if (isValueEqualityComparison(SI)) 9077acd1ccb8a61217f8c06b5fbdcc9785437bd0989Chris Lattner if (FoldValueComparisonIntoPredecessors(SI)) 9087acd1ccb8a61217f8c06b5fbdcc9785437bd0989Chris Lattner return SimplifyCFG(BB) || 1; 909542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 91092da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner if (BI->isConditional()) { 911e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (Value *CompVal = isValueEqualityComparison(BI)) { 912e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // This block must be empty, except for the setcond inst, if it exists. 913e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock::iterator I = BB->begin(); 914e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (&*I == BI || 915e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner (&*I == cast<Instruction>(BI->getCondition()) && 916e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner &*++I == BI)) 917e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (FoldValueComparisonIntoPredecessors(BI)) 918e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner return SimplifyCFG(BB) | true; 919e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 920e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 921e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // If this basic block is ONLY a setcc and a branch, and if a predecessor 922e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // branches to us and one of our successors, fold the setcc into the 923e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // predecessor and use logical operations to pick the right destination. 92412fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner BasicBlock *TrueDest = BI->getSuccessor(0); 92512fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner BasicBlock *FalseDest = BI->getSuccessor(1); 926bdcc0b8c55041ff89b59f0ea2cdbc2ac02f26a3dChris Lattner if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(BI->getCondition())) 927e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (Cond->getParent() == BB && &BB->front() == Cond && 92812fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner Cond->getNext() == BI && Cond->hasOneUse() && 92912fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner TrueDest != BB && FalseDest != BB) 930e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI) 931e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 932a1f79fb08b92801d4ab3cb32fe0bd9d12dfb3954Chris Lattner if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) { 9332636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner BasicBlock *PredBlock = *PI; 934e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == FalseDest || 935e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(1) == TrueDest) { 936e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // Invert the predecessors condition test (xor it with true), 937e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // which allows us to write this code once. 938e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Value *NewCond = 939e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BinaryOperator::createNot(PBI->getCondition(), 940e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getCondition()->getName()+".not", PBI); 941e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setCondition(NewCond); 942e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock *OldTrue = PBI->getSuccessor(0); 943e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock *OldFalse = PBI->getSuccessor(1); 944e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(0, OldFalse); 945e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(1, OldTrue); 946e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 947e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 948e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == TrueDest || 949e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(1) == FalseDest) { 9502636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner // Clone Cond into the predecessor basic block, and or/and the 951e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // two conditions together. 952e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction *New = Cond->clone(); 953e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner New->setName(Cond->getName()); 954e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Cond->setName(Cond->getName()+".old"); 9552636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner PredBlock->getInstList().insert(PBI, New); 956e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction::BinaryOps Opcode = 957e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(0) == TrueDest ? 958e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction::Or : Instruction::And; 959e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Value *NewCond = 960e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BinaryOperator::create(Opcode, PBI->getCondition(), 961e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner New, "bothcond", PBI); 962e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setCondition(NewCond); 963e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == BB) { 9642636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner AddPredecessorToBlock(TrueDest, PredBlock, BB); 965e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(0, TrueDest); 966e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 967e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(1) == BB) { 9682636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner AddPredecessorToBlock(FalseDest, PredBlock, BB); 969e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(1, FalseDest); 970e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 971e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner return SimplifyCFG(BB) | 1; 972e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 973e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 974e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 97592da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // If this block ends with a branch instruction, and if there is one 97692da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // predecessor, see if the previous block ended with a branch on the same 97792da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // condition, which makes this conditional branch redundant. 97892da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 97992da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner BasicBlock *OnlyPred = *PI++; 98092da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner for (; PI != PE; ++PI)// Search all predecessors, see if they are all same 98192da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner if (*PI != OnlyPred) { 98292da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner OnlyPred = 0; // There are multiple different predecessors... 98392da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner break; 98492da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner } 98592da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner 98692da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner if (OnlyPred) 98792da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner if (BranchInst *PBI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 98892da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner if (PBI->isConditional() && 98992da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner PBI->getCondition() == BI->getCondition() && 990951fdb9764ea7abd1f409712636cf80a86140d90Chris Lattner (PBI->getSuccessor(0) != BB || PBI->getSuccessor(1) != BB)) { 99192da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // Okay, the outcome of this conditional branch is statically 99292da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // knowable. Delete the outgoing CFG edge that is impossible to 99392da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // execute. 99492da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner bool CondIsTrue = PBI->getSuccessor(0) == BB; 99592da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner BI->getSuccessor(CondIsTrue)->removePredecessor(BB); 99692da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner new BranchInst(BI->getSuccessor(!CondIsTrue), BB); 99792da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner BB->getInstList().erase(BI); 99892da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner return SimplifyCFG(BB) | true; 99992da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner } 1000d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner } 1001698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (isa<UnreachableInst>(BB->getTerminator())) { 1002698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If there are any instructions immediately before the unreachable that can 1003698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // be removed, do so. 1004698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Instruction *Unreachable = BB->getTerminator(); 1005698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner while (Unreachable != BB->begin()) { 1006698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock::iterator BBI = Unreachable; 1007698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --BBI; 1008698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (isa<CallInst>(BBI)) break; 1009698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Delete this instruction 1010698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BB->getInstList().erase(BBI); 1011698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1012698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1013698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1014698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the unreachable instruction is the first in the block, take a gander 1015698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // at all of the predecessors of this instruction, and simplify them. 1016698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (&BB->front() == Unreachable) { 1017698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 1018698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 1019698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TerminatorInst *TI = Preds[i]->getTerminator(); 1020698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1021698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1022698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->isUnconditional()) { 1023698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 1024698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new UnreachableInst(TI); 1025698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TI->eraseFromParent(); 1026698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1027698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1028698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else { 1029698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 1030698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new BranchInst(BI->getSuccessor(1), BI); 1031698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BI->eraseFromParent(); 1032698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (BI->getSuccessor(1) == BB) { 1033698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new BranchInst(BI->getSuccessor(0), BI); 1034698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BI->eraseFromParent(); 1035698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1036698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1037698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1038698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1039698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1040698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == BB) { 1041698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1042698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1043698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1044698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1045698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the default value is unreachable, figure out the most popular 1046698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // destination and make it the default. 1047698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(0) == BB) { 1048698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::map<BasicBlock*, unsigned> Popularity; 1049698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1050698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Popularity[SI->getSuccessor(i)]++; 1051698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1052698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Find the most popular block. 1053698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner unsigned MaxPop = 0; 1054698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock *MaxBlock = 0; 1055698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (std::map<BasicBlock*, unsigned>::iterator 1056698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 1057698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (I->second > MaxPop) { 1058698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxPop = I->second; 1059698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxBlock = I->first; 1060698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1061698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1062698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (MaxBlock) { 1063698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Make this the new default, allowing us to delete any explicit 1064698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // edges to it. 1065698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->setSuccessor(0, MaxBlock); 1066698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1067698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1068698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1069698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == MaxBlock) { 1070698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1071698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1072698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1073698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1074698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1075698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 1076698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (II->getUnwindDest() == BB) { 1077698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Convert the invoke to a call instruction. This would be a good 1078698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // place to note that the call does not throw though. 1079698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BranchInst *BI = new BranchInst(II->getNormalDest(), II); 1080698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->removeFromParent(); // Take out of symbol table 1081698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1082698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Insert the call now... 1083698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 1084698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner CallInst *CI = new CallInst(II->getCalledValue(), Args, 1085698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->getName(), BI); 1086698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the invoke produced a value, the Call does now instead. 1087698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->replaceAllUsesWith(CI); 1088698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner delete II; 1089698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1090698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1091698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1092698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1093698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1094698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If this block is now dead, remove it. 1095698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (pred_begin(BB) == pred_end(BB)) { 1096698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // We know there are no successors, so just nuke the block. 1097698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner M->getBasicBlockList().erase(BB); 1098698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner return true; 1099698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1100698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 110119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 110219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 110301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Merge basic blocks into their predecessor if there is only one distinct 110401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // pred, and if there is only one distinct successor of the predecessor, and 110501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // if there are no PHI nodes. 110601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 11072355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 11082355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BasicBlock *OnlyPred = *PI++; 11092355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 11102355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (*PI != OnlyPred) { 11112355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred = 0; // There are multiple different predecessors... 11122355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner break; 11132355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 111492da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner 11152355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BasicBlock *OnlySucc = 0; 11162355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (OnlyPred && OnlyPred != BB && // Don't break self loops 11172355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 11182355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Check to see if there is only one distinct successor... 11192355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 11202355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlySucc = BB; 11212355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner for (; SI != SE; ++SI) 11222355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (*SI != OnlySucc) { 11232355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlySucc = 0; // There are multiple distinct successors! 112401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner break; 112501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 11262355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 112701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 11282355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (OnlySucc) { 112930b434476796cd4a85c02914687d22f2e5ec95caChris Lattner DEBUG(std::cerr << "Merging: " << *BB << "into: " << *OnlyPred); 11302355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner TerminatorInst *Term = OnlyPred->getTerminator(); 113101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 11322355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Resolve any PHI nodes at the start of the block. They are all 11332355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // guaranteed to have exactly one entry if they exist, unless there are 11342355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // multiple duplicate (but guaranteed to be equal) entries for the 11352355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // incoming edges. This occurs when there are multiple edges from 11362355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // OnlyPred to OnlySucc. 11372355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // 11382355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 11392355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 11402355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BB->getInstList().pop_front(); // Delete the phi node... 11412355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 114291b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner 11432355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Delete the unconditional branch from the predecessor... 11442355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getInstList().pop_back(); 114501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 11462355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Move all definitions in the successor to the predecessor... 11472355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 114818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 11492355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Make all PHI nodes that referred to BB now refer to Pred as their 11502355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // source... 11512355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BB->replaceAllUsesWith(OnlyPred); 115218961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 11532355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner std::string OldName = BB->getName(); 115418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 11552355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Erase basic block from the function... 11562355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner M->getBasicBlockList().erase(BB); 115718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 11582355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Inherit predecessors name if it exists... 11592355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (!OldName.empty() && !OnlyPred->hasName()) 11602355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->setName(OldName); 116101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 11622355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner return true; 116301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 1164723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 116537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Otherwise, if this block only has a single predecessor, and if that block 116637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // is a conditional branch, see if we can hoist any code from this block up 116737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // into our predecessor. 116837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (OnlyPred) 116937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) { 117037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // This is guaranteed to be a condbr at this point. 117137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner assert(BI->isConditional() && "Should have folded bb into pred!"); 117237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Get the other block. 117337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); 117437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PI = pred_begin(OtherBB); 117537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner ++PI; 117637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (PI == pred_end(OtherBB)) { 117737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // We have a conditional branch to two blocks that are only reachable 117837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // from the condbr. We know that the condbr dominates the two blocks, 117937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // so see if there is any identical code in the "then" and "else" 118037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // blocks. If so, we can hoist it up to the branching block. 118137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Changed |= HoistThenElseCodeToIf(BI); 118237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 118337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 118437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 11850d56008f53587531718ec36af82cc24576580b36Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 11860d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 11870d56008f53587531718ec36af82cc24576580b36Chris Lattner // Change br (X == 0 | X == 1), T, F into a switch instruction. 11880d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 11890d56008f53587531718ec36af82cc24576580b36Chris Lattner Instruction *Cond = cast<Instruction>(BI->getCondition()); 11900d56008f53587531718ec36af82cc24576580b36Chris Lattner // If this is a bunch of seteq's or'd together, or if it's a bunch of 11910d56008f53587531718ec36af82cc24576580b36Chris Lattner // 'setne's and'ed together, collect them. 11920d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *CompVal = 0; 11931654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::vector<ConstantInt*> Values; 11940d56008f53587531718ec36af82cc24576580b36Chris Lattner bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 11950d56008f53587531718ec36af82cc24576580b36Chris Lattner if (CompVal && CompVal->getType()->isInteger()) { 11960d56008f53587531718ec36af82cc24576580b36Chris Lattner // There might be duplicate constants in the list, which the switch 11970d56008f53587531718ec36af82cc24576580b36Chris Lattner // instruction can't handle, remove them now. 11981654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 11990d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 12000d56008f53587531718ec36af82cc24576580b36Chris Lattner 12010d56008f53587531718ec36af82cc24576580b36Chris Lattner // Figure out which block is which destination. 12020d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *DefaultBB = BI->getSuccessor(1); 12030d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *EdgeBB = BI->getSuccessor(0); 12040d56008f53587531718ec36af82cc24576580b36Chris Lattner if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 12050d56008f53587531718ec36af82cc24576580b36Chris Lattner 12060d56008f53587531718ec36af82cc24576580b36Chris Lattner // Create the new switch instruction now. 12070d56008f53587531718ec36af82cc24576580b36Chris Lattner SwitchInst *New = new SwitchInst(CompVal, DefaultBB, BI); 12080d56008f53587531718ec36af82cc24576580b36Chris Lattner 12090d56008f53587531718ec36af82cc24576580b36Chris Lattner // Add all of the 'cases' to the switch instruction. 12100d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size(); i != e; ++i) 12110d56008f53587531718ec36af82cc24576580b36Chris Lattner New->addCase(Values[i], EdgeBB); 12120d56008f53587531718ec36af82cc24576580b36Chris Lattner 12130d56008f53587531718ec36af82cc24576580b36Chris Lattner // We added edges from PI to the EdgeBB. As such, if there were any 12140d56008f53587531718ec36af82cc24576580b36Chris Lattner // PHI nodes in EdgeBB, they need entries to be added corresponding to 12150d56008f53587531718ec36af82cc24576580b36Chris Lattner // the number of edges added. 12160d56008f53587531718ec36af82cc24576580b36Chris Lattner for (BasicBlock::iterator BBI = EdgeBB->begin(); 12172da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer isa<PHINode>(BBI); ++BBI) { 12182da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(BBI); 12190d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *InVal = PN->getIncomingValueForBlock(*PI); 12200d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 12210d56008f53587531718ec36af82cc24576580b36Chris Lattner PN->addIncoming(InVal, *PI); 12220d56008f53587531718ec36af82cc24576580b36Chris Lattner } 12230d56008f53587531718ec36af82cc24576580b36Chris Lattner 12240d56008f53587531718ec36af82cc24576580b36Chris Lattner // Erase the old branch instruction. 12250d56008f53587531718ec36af82cc24576580b36Chris Lattner (*PI)->getInstList().erase(BI); 12260d56008f53587531718ec36af82cc24576580b36Chris Lattner 12270d56008f53587531718ec36af82cc24576580b36Chris Lattner // Erase the potentially condition tree that was used to computed the 12280d56008f53587531718ec36af82cc24576580b36Chris Lattner // branch condition. 12290d56008f53587531718ec36af82cc24576580b36Chris Lattner ErasePossiblyDeadInstructionTree(Cond); 12300d56008f53587531718ec36af82cc24576580b36Chris Lattner return true; 12310d56008f53587531718ec36af82cc24576580b36Chris Lattner } 12320d56008f53587531718ec36af82cc24576580b36Chris Lattner } 12330d56008f53587531718ec36af82cc24576580b36Chris Lattner 1234723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If there is a trivial two-entry PHI node in this basic block, and we can 1235723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // eliminate it, do so now. 1236723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 1237723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (PN->getNumIncomingValues() == 2) { 1238723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1239723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // statement", which has a very simple dominance structure. Basically, we 1240723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // are trying to find the condition that is being branched on, which 1241723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // subsequently causes this merge to happen. We really want control 1242723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // dependence information for this check, but simplifycfg can't keep it up 1243723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // to date, and this catches most of the cases we care about anyway. 1244723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // 1245723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *IfTrue, *IfFalse; 1246723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse)) { 1247218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner DEBUG(std::cerr << "FOUND IF CONDITION! " << *IfCond << " T: " 1248218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1249723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 12509c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Loop over the PHI's seeing if we can promote them all to select 12519c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // instructions. While we are at it, keep track of the instructions 12529c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // that need to be moved to the dominating block. 12539c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner std::set<Instruction*> AggressiveInsts; 12549c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner bool CanPromote = true; 12559c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 1256723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock::iterator AfterPHIIt = BB->begin(); 12579c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner while (isa<PHINode>(AfterPHIIt)) { 12589c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner PHINode *PN = cast<PHINode>(AfterPHIIt++); 12599c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) 12609c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 12619c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 12629c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner &AggressiveInsts) || 12639c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner !DominatesMergePoint(PN->getIncomingValue(1), BB, 12649c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner &AggressiveInsts)) { 12659c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote = false; 12669c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner break; 12679c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 12689c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 1269723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 12709c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Did we eliminate all PHI's? 12719c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote |= AfterPHIIt == BB->begin(); 12729c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 12739c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // If we all PHI nodes are promotable, check to make sure that all 12749c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // instructions in the predecessor blocks can be promoted as well. If 12759c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // not, we won't be able to get rid of the control flow, so it's not 12769c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // worth promoting to select instructions. 12774e073a871b208a2c9dfa004b3a93fb26f96daa17Reid Spencer BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 12789c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (CanPromote) { 12799c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner PN = cast<PHINode>(BB->begin()); 12809c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner BasicBlock *Pred = PN->getIncomingBlock(0); 12819c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 12829c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1 = Pred; 12839c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock = *pred_begin(Pred); 12849c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner for (BasicBlock::iterator I = Pred->begin(); 12859c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner !isa<TerminatorInst>(I); ++I) 12869c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!AggressiveInsts.count(I)) { 12879c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // This is not an aggressive instruction that we can promote. 12889c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Because of this, we won't be able to get rid of the control 12899c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // flow, so the xform is not worth it. 12909c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote = false; 12919c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner break; 12929c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 12939c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 12949c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 12959c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner Pred = PN->getIncomingBlock(1); 12969c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (CanPromote && 12979c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 12989c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2 = Pred; 12999c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock = *pred_begin(Pred); 13009c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner for (BasicBlock::iterator I = Pred->begin(); 13019c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner !isa<TerminatorInst>(I); ++I) 13029c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!AggressiveInsts.count(I)) { 13039c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // This is not an aggressive instruction that we can promote. 13049c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Because of this, we won't be able to get rid of the control 13059c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // flow, so the xform is not worth it. 13069c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote = false; 13079c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner break; 13089c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 13099c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 13109c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 13119c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 13129c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // If we can still promote the PHI nodes after this gauntlet of tests, 13139c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // do all of the PHI's now. 13149c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (CanPromote) { 13159c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Move all 'aggressive' instructions, which are defined in the 13169c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // conditional parts of the if's up to the dominating block. 13179c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (IfBlock1) { 13189c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 13199c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1->getInstList(), 13209c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1->begin(), 13219c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1->getTerminator()); 13229c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 13239c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (IfBlock2) { 13249c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 13259c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2->getInstList(), 13269c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2->begin(), 13279c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2->getTerminator()); 13289c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 13299c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 13309c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 13319c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Change the PHI node into a select instruction. 1332723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Value *TrueVal = 1333723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1334723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Value *FalseVal = 1335723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1336723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 1337552112f2f8702f2cba8cb5775bc24c3e02ba265cChris Lattner std::string Name = PN->getName(); PN->setName(""); 1338552112f2f8702f2cba8cb5775bc24c3e02ba265cChris Lattner PN->replaceAllUsesWith(new SelectInst(IfCond, TrueVal, FalseVal, 13399c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner Name, AfterPHIIt)); 1340552112f2f8702f2cba8cb5775bc24c3e02ba265cChris Lattner BB->getInstList().erase(PN); 1341723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 13429c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner Changed = true; 1343723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 1344723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 1345723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 134601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 1347694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner return Changed; 134801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 1349