SimplifyCFG.cpp revision 7e66348cba4384d07b37ad1c186e67ba6d26babd
101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 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 { 84fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 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 947e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner/// TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional 957e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner/// branch to Succ, and contains no instructions other than PHI nodes and the 967e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner/// branch. If possible, eliminate BB. 977e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattnerstatic bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, 987e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BasicBlock *Succ) { 997e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // If our successor has PHI nodes, then we need to update them to include 1007e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // entries for BB's predecessors, not for BB itself. Be careful though, 1017e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // if this transformation fails (returns true) then we cannot do this 1027e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // transformation! 1037e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // 1047e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (PropagatePredecessorsForPHIs(BB, Succ)) return false; 1057e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1067e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner DEBUG(std::cerr << "Killing Trivial BB: \n" << *BB); 1077e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1087e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (isa<PHINode>(&BB->front())) { 1097e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner std::vector<BasicBlock*> 1107e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 1117e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1127e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // Move all PHI nodes in BB to Succ if they are alive, otherwise 1137e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // delete them. 1147e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 1157e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (PN->use_empty() /*|| Succ->getSinglePredecessor() == 0*/) { 1167e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // We can only move the PHI node into Succ if BB dominates Succ. 1177e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // Since BB only has a single successor (Succ), the PHI nodes 1187e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // will dominate Succ, unless Succ has multiple predecessors. In 1197e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // this case, the PHIs are either dead, or have references in dead 1207e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // blocks. In either case, we can just remove them. 1217e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (!PN->use_empty()) // Uses in dead block? 1227e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 1237e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner PN->eraseFromParent(); // Nuke instruction. 1247e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } else { 1257e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // The instruction is alive, so this means that Succ must have 1267e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // *ONLY* had BB as a predecessor, and the PHI node is still valid 1277e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // now. Simply move it into Succ, because we know that BB 1287e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // strictly dominated Succ. 1297e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BB->getInstList().remove(BB->begin()); 1307e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner Succ->getInstList().push_front(PN); 1317e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1327e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // We need to add new entries for the PHI node to account for 1337e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // predecessors of Succ that the PHI node does not take into 1347e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // account. At this point, since we know that BB dominated succ, 1357e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // this means that we should any newly added incoming edges should 1367e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // use the PHI node as the value for these edges, because they are 1377e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // loop back edges. 1387e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 1397e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (OldSuccPreds[i] != BB) 1407e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner PN->addIncoming(PN, OldSuccPreds[i]); 1417e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } 1427e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } 1437e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1447e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // Everything that jumped to BB now goes to Succ. 1457e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner std::string OldName = BB->getName(); 1467e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BB->replaceAllUsesWith(Succ); 1477e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BB->eraseFromParent(); // Delete the old basic block. 1487e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1497e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can 1507e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner Succ->setName(OldName); 1517e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner return true; 1527e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner} 1537e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 154723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// GetIfCondition - Given a basic block (BB) with two predecessors (and 155723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// presumably PHI nodes in it), check to see if the merge at this block is due 156723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// to an "if condition". If so, return the boolean condition that determines 157723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// which entry into BB will be taken. Also, return by references the block 158723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// that will be entered from if the condition is true, and the block that will 159723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// be entered if the condition is false. 160fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// 161723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// 162723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattnerstatic Value *GetIfCondition(BasicBlock *BB, 163723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 164723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 165723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner "Function can only handle blocks with 2 predecessors!"); 166723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *Pred1 = *pred_begin(BB); 167723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *Pred2 = *++pred_begin(BB); 168723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 169723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // We can only handle branches. Other control flow will be lowered to 170723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // branches if possible anyway. 171723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (!isa<BranchInst>(Pred1->getTerminator()) || 172723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner !isa<BranchInst>(Pred2->getTerminator())) 173723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 174723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 175723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 176723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 177723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Eliminate code duplication by ensuring that Pred1Br is conditional if 178723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // either are. 179723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred2Br->isConditional()) { 180723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If both branches are conditional, we don't have an "if statement". In 181723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // reality, we could transform this case, but since the condition will be 182723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // required anyway, we stand no chance of eliminating it, so the xform is 183723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // probably not profitable. 184723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->isConditional()) 185723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 186723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 187723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner std::swap(Pred1, Pred2); 188723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner std::swap(Pred1Br, Pred2Br); 189723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 190723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 191723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->isConditional()) { 192723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If we found a conditional branch predecessor, make sure that it branches 193723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 194723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->getSuccessor(0) == BB && 195723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Pred1Br->getSuccessor(1) == Pred2) { 196723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred1; 197723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred2; 198723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else if (Pred1Br->getSuccessor(0) == Pred2 && 199723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Pred1Br->getSuccessor(1) == BB) { 200723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred2; 201723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred1; 202723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else { 203723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // We know that one arm of the conditional goes to BB, so the other must 204723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // go somewhere unrelated, and this must not be an "if statement". 205723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 206723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 207723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 208723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // The only thing we have to watch out for here is to make sure that Pred2 209723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // doesn't have incoming edges from other blocks. If it does, the condition 210723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // doesn't dominate BB. 211723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (++pred_begin(Pred2) != pred_end(Pred2)) 212723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 213723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 214723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return Pred1Br->getCondition(); 215723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 216723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 217723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Ok, if we got here, both predecessors end with an unconditional branch to 218723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // BB. Don't panic! If both blocks only have a single (identical) 219723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // predecessor, and THAT is a conditional branch, then we're all ok! 220723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (pred_begin(Pred1) == pred_end(Pred1) || 221723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner ++pred_begin(Pred1) != pred_end(Pred1) || 222723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner pred_begin(Pred2) == pred_end(Pred2) || 223723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner ++pred_begin(Pred2) != pred_end(Pred2) || 224723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner *pred_begin(Pred1) != *pred_begin(Pred2)) 225723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 226723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 227723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Otherwise, if this is a conditional branch, then we can use it! 228723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *CommonPred = *pred_begin(Pred1); 229723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 230723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner assert(BI->isConditional() && "Two successors but not conditional?"); 231723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (BI->getSuccessor(0) == Pred1) { 232723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred1; 233723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred2; 234723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else { 235723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred2; 236723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred1; 237723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 238723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return BI->getCondition(); 239723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 240723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 241723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner} 242723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 243723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 244723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// If we have a merge point of an "if condition" as accepted above, return true 245723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// if the specified value dominates the block. We don't handle the true 246723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// generality of domination here, just a special case which works well enough 247723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// for us. 2489c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// 2499c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 2509c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// see if V (which must be an instruction) is cheap to compute and is 2519c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// non-trapping. If both are true, the instruction is inserted into the set and 2529c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// true is returned. 2539c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattnerstatic bool DominatesMergePoint(Value *V, BasicBlock *BB, 2549c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner std::set<Instruction*> *AggressiveInsts) { 255570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 256570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (!I) return true; // Non-instructions all dominate instructions. 257570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner BasicBlock *PBB = I->getParent(); 258570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 259da895d63377b421dc50117befb2bec80d2973526Chris Lattner // We don't want to allow weird loops that might have the "if condition" in 260570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // the bottom of this block. 261570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (PBB == BB) return false; 262570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 263570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // If this instruction is defined in a block that contains an unconditional 264570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // branch to BB, then it must be in the 'conditional' part of the "if 265570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // statement". 266570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator())) 267570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { 2689c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!AggressiveInsts) return false; 269570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Okay, it looks like the instruction IS in the "condition". Check to 270570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // see if its a cheap instruction to unconditionally compute, and if it 271570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // only uses stuff defined outside of the condition. If so, hoist it out. 272570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner switch (I->getOpcode()) { 273570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner default: return false; // Cannot hoist this out safely. 274570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Load: 275570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // We can hoist loads that are non-volatile and obviously cannot trap. 276570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (cast<LoadInst>(I)->isVolatile()) 277570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 278570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (!isa<AllocaInst>(I->getOperand(0)) && 279460f16c6253928519689e882a4dbb7f236f33294Reid Spencer !isa<Constant>(I->getOperand(0))) 280570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 281570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 282570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Finally, we have to check to make sure there are no instructions 283570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // before the load in its basic block, as we are going to hoist the loop 284570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // out to its predecessor. 285570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (PBB->begin() != BasicBlock::iterator(I)) 286570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 287570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner break; 288570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Add: 289570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Sub: 290570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::And: 291570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Or: 292570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Xor: 293570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Shl: 294570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Shr: 295bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetEQ: 296bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetNE: 297bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetLT: 298bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetGT: 299bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetLE: 300bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetGE: 301570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner break; // These are all cheap and non-trapping instructions. 302570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner } 303fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 304570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Okay, we can only really hoist these out if their operands are not 305570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // defined in the conditional region. 306570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 3079c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!DominatesMergePoint(I->getOperand(i), BB, 0)) 308570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 3099c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Okay, it's safe to do this! Remember this instruction. 3109c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner AggressiveInsts->insert(I); 311570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner } 312723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 313723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return true; 314723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner} 31501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 3160d56008f53587531718ec36af82cc24576580b36Chris Lattner// GatherConstantSetEQs - Given a potentially 'or'd together collection of seteq 3170d56008f53587531718ec36af82cc24576580b36Chris Lattner// instructions that compare a value against a constant, return the value being 3180d56008f53587531718ec36af82cc24576580b36Chris Lattner// compared, and stick the constant into the Values vector. 3191654cff8e80acdddf5e5f2261595007878924aacChris Lattnerstatic Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values){ 3200d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Instruction *Inst = dyn_cast<Instruction>(V)) 3210d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Inst->getOpcode() == Instruction::SetEQ) { 3221654cff8e80acdddf5e5f2261595007878924aacChris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 3230d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 3240d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 3251654cff8e80acdddf5e5f2261595007878924aacChris Lattner } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 3260d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 3270d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(1); 3280d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3290d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::Or) { 3300d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 3310d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 3320d56008f53587531718ec36af82cc24576580b36Chris Lattner if (LHS == RHS) 3330d56008f53587531718ec36af82cc24576580b36Chris Lattner return LHS; 3340d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3350d56008f53587531718ec36af82cc24576580b36Chris Lattner return 0; 3360d56008f53587531718ec36af82cc24576580b36Chris Lattner} 3370d56008f53587531718ec36af82cc24576580b36Chris Lattner 3380d56008f53587531718ec36af82cc24576580b36Chris Lattner// GatherConstantSetNEs - Given a potentially 'and'd together collection of 3390d56008f53587531718ec36af82cc24576580b36Chris Lattner// setne instructions that compare a value against a constant, return the value 3400d56008f53587531718ec36af82cc24576580b36Chris Lattner// being compared, and stick the constant into the Values vector. 3411654cff8e80acdddf5e5f2261595007878924aacChris Lattnerstatic Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values){ 3420d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Instruction *Inst = dyn_cast<Instruction>(V)) 3430d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Inst->getOpcode() == Instruction::SetNE) { 3441654cff8e80acdddf5e5f2261595007878924aacChris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 3450d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 3460d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 3471654cff8e80acdddf5e5f2261595007878924aacChris Lattner } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 3480d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 3490d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(1); 3500d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3510d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::Cast) { 3520d56008f53587531718ec36af82cc24576580b36Chris Lattner // Cast of X to bool is really a comparison against zero. 3530d56008f53587531718ec36af82cc24576580b36Chris Lattner assert(Inst->getType() == Type::BoolTy && "Can only handle bool values!"); 3541654cff8e80acdddf5e5f2261595007878924aacChris Lattner Values.push_back(ConstantInt::get(Inst->getOperand(0)->getType(), 0)); 3550d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 3560d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::And) { 3570d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 3580d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 3590d56008f53587531718ec36af82cc24576580b36Chris Lattner if (LHS == RHS) 3600d56008f53587531718ec36af82cc24576580b36Chris Lattner return LHS; 3610d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3620d56008f53587531718ec36af82cc24576580b36Chris Lattner return 0; 3630d56008f53587531718ec36af82cc24576580b36Chris Lattner} 3640d56008f53587531718ec36af82cc24576580b36Chris Lattner 3650d56008f53587531718ec36af82cc24576580b36Chris Lattner 3660d56008f53587531718ec36af82cc24576580b36Chris Lattner 3670d56008f53587531718ec36af82cc24576580b36Chris Lattner/// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 3680d56008f53587531718ec36af82cc24576580b36Chris Lattner/// bunch of comparisons of one value against constants, return the value and 3690d56008f53587531718ec36af82cc24576580b36Chris Lattner/// the constants being compared. 3700d56008f53587531718ec36af82cc24576580b36Chris Lattnerstatic bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 3711654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::vector<ConstantInt*> &Values) { 3720d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Cond->getOpcode() == Instruction::Or) { 3730d56008f53587531718ec36af82cc24576580b36Chris Lattner CompVal = GatherConstantSetEQs(Cond, Values); 3740d56008f53587531718ec36af82cc24576580b36Chris Lattner 3750d56008f53587531718ec36af82cc24576580b36Chris Lattner // Return true to indicate that the condition is true if the CompVal is 3760d56008f53587531718ec36af82cc24576580b36Chris Lattner // equal to one of the constants. 3770d56008f53587531718ec36af82cc24576580b36Chris Lattner return true; 3780d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Cond->getOpcode() == Instruction::And) { 3790d56008f53587531718ec36af82cc24576580b36Chris Lattner CompVal = GatherConstantSetNEs(Cond, Values); 380fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 3810d56008f53587531718ec36af82cc24576580b36Chris Lattner // Return false to indicate that the condition is false if the CompVal is 3820d56008f53587531718ec36af82cc24576580b36Chris Lattner // equal to one of the constants. 3830d56008f53587531718ec36af82cc24576580b36Chris Lattner return false; 3840d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3850d56008f53587531718ec36af82cc24576580b36Chris Lattner return false; 3860d56008f53587531718ec36af82cc24576580b36Chris Lattner} 3870d56008f53587531718ec36af82cc24576580b36Chris Lattner 3880d56008f53587531718ec36af82cc24576580b36Chris Lattner/// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and 3890d56008f53587531718ec36af82cc24576580b36Chris Lattner/// has no side effects, nuke it. If it uses any instructions that become dead 3900d56008f53587531718ec36af82cc24576580b36Chris Lattner/// because the instruction is now gone, nuke them too. 3910d56008f53587531718ec36af82cc24576580b36Chris Lattnerstatic void ErasePossiblyDeadInstructionTree(Instruction *I) { 3920d56008f53587531718ec36af82cc24576580b36Chris Lattner if (isInstructionTriviallyDead(I)) { 3930d56008f53587531718ec36af82cc24576580b36Chris Lattner std::vector<Value*> Operands(I->op_begin(), I->op_end()); 3940d56008f53587531718ec36af82cc24576580b36Chris Lattner I->getParent()->getInstList().erase(I); 3950d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Operands.size(); i != e; ++i) 3960d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Instruction *OpI = dyn_cast<Instruction>(Operands[i])) 3970d56008f53587531718ec36af82cc24576580b36Chris Lattner ErasePossiblyDeadInstructionTree(OpI); 3980d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3990d56008f53587531718ec36af82cc24576580b36Chris Lattner} 4000d56008f53587531718ec36af82cc24576580b36Chris Lattner 401d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// SafeToMergeTerminators - Return true if it is safe to merge these two 402d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// terminator instructions together. 403d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// 404d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattnerstatic bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 405d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (SI1 == SI2) return false; // Can't merge with self! 406d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner 407d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner // It is not safe to merge these two switch instructions if they have a common 4082636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner // successor, and if that successor has a PHI node, and if *that* PHI node has 409d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner // conflicting incoming values from the two switch blocks. 410d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner BasicBlock *SI1BB = SI1->getParent(); 411d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner BasicBlock *SI2BB = SI2->getParent(); 412d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 413d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner 414d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 415d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (SI1Succs.count(*I)) 416d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner for (BasicBlock::iterator BBI = (*I)->begin(); 4172da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer isa<PHINode>(BBI); ++BBI) { 4182da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(BBI); 419d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (PN->getIncomingValueForBlock(SI1BB) != 420d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner PN->getIncomingValueForBlock(SI2BB)) 421d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner return false; 4222da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer } 423fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 424d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner return true; 425d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner} 426d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner 427d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 428d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// now be entries in it from the 'NewPred' block. The values that will be 429d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner/// flowing into the PHI nodes will be the same as those coming in from 4302636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner/// ExistPred, an existing predecessor of Succ. 431d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattnerstatic void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 432d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner BasicBlock *ExistPred) { 433d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 434d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 435d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 436d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner 4372da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 4382da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 439d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner Value *V = PN->getIncomingValueForBlock(ExistPred); 440d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner PN->addIncoming(V, NewPred); 441d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner } 442d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner} 443d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner 444542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// isValueEqualityComparison - Return true if the specified terminator checks to 445542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// see if a value is equal to constant integer value. 446542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic Value *isValueEqualityComparison(TerminatorInst *TI) { 4474bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 4484bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner // Do not permit merging of large switch instructions into their 4494bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner // predecessors unless there is only one predecessor. 4504bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), 4514bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner pred_end(SI->getParent())) > 128) 4524bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner return 0; 4534bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner 454542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SI->getCondition(); 4554bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner } 456542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 457542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (BI->isConditional() && BI->getCondition()->hasOneUse()) 458542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition())) 459542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if ((SCI->getOpcode() == Instruction::SetEQ || 460fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman SCI->getOpcode() == Instruction::SetNE) && 461542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner isa<ConstantInt>(SCI->getOperand(1))) 462542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SCI->getOperand(0); 463542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return 0; 464542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 465542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 466542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// Given a value comparison instruction, decode all of the 'cases' that it 467542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// represents and return the 'default' block. 468542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic BasicBlock * 469fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha BrukmanGetValueEqualityComparisonCases(TerminatorInst *TI, 470542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, 471542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock*> > &Cases) { 472542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 473542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Cases.reserve(SI->getNumCases()); 474542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 475be54dcc8a9d14592e324d6e6ae1322782e17f09fChris Lattner Cases.push_back(std::make_pair(SI->getCaseValue(i), SI->getSuccessor(i))); 476542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SI->getDefaultDest(); 477542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 478542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 479542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BranchInst *BI = cast<BranchInst>(TI); 480542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner SetCondInst *SCI = cast<SetCondInst>(BI->getCondition()); 481542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Cases.push_back(std::make_pair(cast<ConstantInt>(SCI->getOperand(1)), 482542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BI->getSuccessor(SCI->getOpcode() == 483542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Instruction::SetNE))); 484542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return BI->getSuccessor(SCI->getOpcode() == Instruction::SetEQ); 485542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 486542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 487542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 488623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// EliminateBlockCases - Given an vector of bb/value pairs, remove any entries 489623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// in the list that match the specified block. 490fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukmanstatic void EliminateBlockCases(BasicBlock *BB, 491623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) { 492623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = Cases.size(); i != e; ++i) 493623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (Cases[i].second == BB) { 494623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Cases.erase(Cases.begin()+i); 495623369ac5669a3667a94a3cbba342dea78845615Chris Lattner --i; --e; 496623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 497623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 498623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 499623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 500623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// well. 501623369ac5669a3667a94a3cbba342dea78845615Chris Lattnerstatic bool 502623369ac5669a3667a94a3cbba342dea78845615Chris LattnerValuesOverlap(std::vector<std::pair<ConstantInt*, BasicBlock*> > &C1, 503623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > &C2) { 504623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > *V1 = &C1, *V2 = &C2; 505623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 506623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Make V1 be smaller than V2. 507623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() > V2->size()) 508623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::swap(V1, V2); 509623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 510623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() == 0) return false; 511623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() == 1) { 512623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Just scan V2. 513623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ConstantInt *TheVal = (*V1)[0].first; 514623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = V2->size(); i != e; ++i) 515623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TheVal == (*V2)[i].first) 516623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 517623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 518623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 519623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Otherwise, just sort both lists and compare element by element. 520623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::sort(V1->begin(), V1->end()); 521623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::sort(V2->begin(), V2->end()); 522623369ac5669a3667a94a3cbba342dea78845615Chris Lattner unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 523623369ac5669a3667a94a3cbba342dea78845615Chris Lattner while (i1 != e1 && i2 != e2) { 524623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if ((*V1)[i1].first == (*V2)[i2].first) 525623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 526623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if ((*V1)[i1].first < (*V2)[i2].first) 527623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ++i1; 528623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 529623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ++i2; 530623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 531623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; 532623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 533623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 534623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 535623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// terminator instruction and its block is known to only have a single 536623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// predecessor block, check to see if that predecessor is also a value 537623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// comparison with the same value, and if that comparison determines the outcome 538623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// of this comparison. If so, simplify TI. This does a very limited form of 539623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// jump threading. 540623369ac5669a3667a94a3cbba342dea78845615Chris Lattnerstatic bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 541623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *Pred) { 542623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 543623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (!PredVal) return false; // Not a value comparison in predecessor. 544623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 545623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Value *ThisVal = isValueEqualityComparison(TI); 546623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(ThisVal && "This isn't a value comparison!!"); 547623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ThisVal != PredVal) return false; // Different predicates. 548623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 549623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Find out information about when control will move from Pred to TI's block. 550623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 551623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 552623369ac5669a3667a94a3cbba342dea78845615Chris Lattner PredCases); 553623369ac5669a3667a94a3cbba342dea78845615Chris Lattner EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 554fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 555623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Find information about how control leaves this block. 556623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases; 557623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 558623369ac5669a3667a94a3cbba342dea78845615Chris Lattner EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 559623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 560623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If TI's block is the default block from Pred's comparison, potentially 561623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // simplify TI based on this knowledge. 562623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (PredDef == TI->getParent()) { 563623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we are here, we know that the value is none of those cases listed in 564623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // PredCases. If there are any cases in ThisCases that are in PredCases, we 565623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // can simplify TI. 566623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ValuesOverlap(PredCases, ThisCases)) { 567623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BranchInst *BTI = dyn_cast<BranchInst>(TI)) { 568623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, one of the successors of this condbr is dead. Convert it to a 569623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // uncond br. 570623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(ThisCases.size() == 1 && "Branch can only have one case!"); 571623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Value *Cond = BTI->getCondition(); 572623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Insert the new branch. 573623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Instruction *NI = new BranchInst(ThisDef, TI); 574623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 575623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Remove PHI node entries for the dead edge. 576623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ThisCases[0].second->removePredecessor(TI->getParent()); 577623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 578623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator() 579623369ac5669a3667a94a3cbba342dea78845615Chris Lattner << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 580623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 581623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TI->eraseFromParent(); // Nuke the old one. 582623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If condition is now dead, nuke it. 583623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (Instruction *CondI = dyn_cast<Instruction>(Cond)) 584623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ErasePossiblyDeadInstructionTree(CondI); 585623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 586623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 587623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else { 588623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SwitchInst *SI = cast<SwitchInst>(TI); 589623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, TI has cases that are statically dead, prune them away. 590623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::set<Constant*> DeadCases; 591623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 592623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DeadCases.insert(PredCases[i].first); 593623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 594623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator() 595623369ac5669a3667a94a3cbba342dea78845615Chris Lattner << "Through successor TI: " << *TI); 596623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 597623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = SI->getNumCases()-1; i != 0; --i) 598623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (DeadCases.count(SI->getCaseValue(i))) { 599623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SI->getSuccessor(i)->removePredecessor(TI->getParent()); 600623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SI->removeCase(i); 601623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 602623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 603623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DEBUG(std::cerr << "Leaving: " << *TI << "\n"); 604623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 605623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 606623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 607623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 608623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else { 609623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Otherwise, TI's block must correspond to some matched value. Find out 610623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // which value (or set of values) this is. 611623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ConstantInt *TIV = 0; 612623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *TIBB = TI->getParent(); 613623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 614623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (PredCases[i].second == TIBB) 615623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TIV == 0) 616623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TIV = PredCases[i].first; 617623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 618623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; // Cannot handle multiple values coming to this block. 619623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(TIV && "No edge from pred to succ?"); 620623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 621623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, we found the one constant that our value can be if we get into TI's 622623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // BB. Find out which successor will unconditionally be branched to. 623623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *TheRealDest = 0; 624623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 625623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ThisCases[i].first == TIV) { 626623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TheRealDest = ThisCases[i].second; 627623369ac5669a3667a94a3cbba342dea78845615Chris Lattner break; 628623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 629623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 630623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If not handled by any explicit cases, it is handled by the default case. 631623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TheRealDest == 0) TheRealDest = ThisDef; 632623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 633623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Remove PHI node entries for dead edges. 634623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *CheckEdge = TheRealDest; 635623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 636623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (*SI != CheckEdge) 637623369ac5669a3667a94a3cbba342dea78845615Chris Lattner (*SI)->removePredecessor(TIBB); 638623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 639623369ac5669a3667a94a3cbba342dea78845615Chris Lattner CheckEdge = 0; 640623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 641623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Insert the new branch. 642623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Instruction *NI = new BranchInst(TheRealDest, TI); 643623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 644623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator() 645623369ac5669a3667a94a3cbba342dea78845615Chris Lattner << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 646623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Instruction *Cond = 0; 647623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 648623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Cond = dyn_cast<Instruction>(BI->getCondition()); 649623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TI->eraseFromParent(); // Nuke the old one. 650623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 651623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (Cond) ErasePossiblyDeadInstructionTree(Cond); 652623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 653623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 654623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; 655623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 656623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 657542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// FoldValueComparisonIntoPredecessors - The specified terminator is a value 658542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// equality comparison instruction (either a switch or a branch on "X == c"). 659542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// See if any of the predecessors of the terminator block are value comparisons 660542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// on the same value. If so, and if safe to do so, fold them together. 661542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 662542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *BB = TI->getParent(); 663542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Value *CV = isValueEqualityComparison(TI); // CondVal 664542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner assert(CV && "Not a comparison?"); 665542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner bool Changed = false; 666542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 667542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 668542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner while (!Preds.empty()) { 669542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *Pred = Preds.back(); 670542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Preds.pop_back(); 671fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 672542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // See if the predecessor is a comparison with the same value. 673542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner TerminatorInst *PTI = Pred->getTerminator(); 674542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 675542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 676542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 677542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Figure out which 'cases' to copy from SI to PSI. 678542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 679542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 680542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 681542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 682542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 683542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 684542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Based on whether the default edge from PTI goes to BB or not, fill in 685542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // PredCases and PredDefault with the new switch cases we would like to 686542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // build. 687542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<BasicBlock*> NewSuccessors; 688542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 689542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredDefault == BB) { 690542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is the default destination from PTI, only the edges in TI 691542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // that don't occur in PTI, or that branch to BB will be activated. 692542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::set<ConstantInt*> PTIHandled; 693542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 694542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredCases[i].second != BB) 695542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.insert(PredCases[i].first); 696542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner else { 697542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // The default destination is BB, we don't need explicit targets. 698542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::swap(PredCases[i], PredCases.back()); 699542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.pop_back(); 700542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner --i; --e; 701542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 702542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 703542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Reconstruct the new switch statement we will be building. 704542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredDefault != BBDefault) { 705542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredDefault->removePredecessor(Pred); 706542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredDefault = BBDefault; 707542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBDefault); 708542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 709542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 710542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (!PTIHandled.count(BBCases[i].first) && 711542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BBCases[i].second != BBDefault) { 712542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(BBCases[i]); 713542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBCases[i].second); 714542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 715542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 716542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } else { 717542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is not the default destination from PSI, only the edges 718542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // in SI that occur in PSI with a destination of BB will be 719542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // activated. 720542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::set<ConstantInt*> PTIHandled; 721542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 722542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredCases[i].second == BB) { 723542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.insert(PredCases[i].first); 724542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::swap(PredCases[i], PredCases.back()); 725542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.pop_back(); 726542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner --i; --e; 727542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 728542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 729542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, now we know which constants were sent to BB from the 730542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // predecessor. Figure out where they will all go now. 731542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 732542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PTIHandled.count(BBCases[i].first)) { 733542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is one we are capable of getting... 734542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(BBCases[i]); 735542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBCases[i].second); 736542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.erase(BBCases[i].first);// This constant is taken care of 737542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 738542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 739542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If there are any constants vectored to BB that TI doesn't handle, 740542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // they must go to the default destination of TI. 741542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (std::set<ConstantInt*>::iterator I = PTIHandled.begin(), 742542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner E = PTIHandled.end(); I != E; ++I) { 743542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(std::make_pair(*I, BBDefault)); 744542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBDefault); 745542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 746542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 747542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 748542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, at this point, we know which new successor Pred will get. Make 749542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // sure we update the number of entries in the PHI nodes for these 750542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // successors. 751542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 752542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 753542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 754542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Now that the successors are updated, create the new Switch instruction. 755378805969ea928b91aa321746031a8f51667a783Chris Lattner SwitchInst *NewSI = new SwitchInst(CV, PredDefault, PredCases.size(),PTI); 756542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 757542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSI->addCase(PredCases[i].first, PredCases[i].second); 75813b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner 75913b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner Instruction *DeadCond = 0; 76013b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 76113b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner // If PTI is a branch, remember the condition. 76213b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner DeadCond = dyn_cast<Instruction>(BI->getCondition()); 763542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Pred->getInstList().erase(PTI); 764542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 76513b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner // If the condition is dead now, remove the instruction tree. 76613b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner if (DeadCond) ErasePossiblyDeadInstructionTree(DeadCond); 76713b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner 768542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, last check. If BB is still a successor of PSI, then we must 769542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // have an infinite loop case. If so, add an infinitely looping block 770542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // to handle the case to preserve the behavior of the code. 771542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *InfLoopBlock = 0; 772542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 773542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (NewSI->getSuccessor(i) == BB) { 774542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (InfLoopBlock == 0) { 775542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Insert it at the end of the loop, because it's either code, 776542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // or it won't matter if it's hot. :) 777542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner InfLoopBlock = new BasicBlock("infloop", BB->getParent()); 778542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner new BranchInst(InfLoopBlock, InfLoopBlock); 779542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 780542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSI->setSuccessor(i, InfLoopBlock); 781542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 782fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 783542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Changed = true; 784542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 785542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 786542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return Changed; 787542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 788542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 78937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// HoistThenElseCodeToIf - Given a conditional branch that codes to BB1 and 79037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// BB2, hoist any common code in the two blocks up into the branch block. The 79137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// caller of this function guarantees that BI's block dominates BB1 and BB2. 79237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattnerstatic bool HoistThenElseCodeToIf(BranchInst *BI) { 79337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // This does very trivial matching, with limited scanning, to find identical 79437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // instructions in the two blocks. In particular, we don't want to get into 79537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 79637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // such, we currently just scan for obviously identical instructions in an 79737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // identical order. 79837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 79937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 80037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 80137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Instruction *I1 = BB1->begin(), *I2 = BB2->begin(); 80237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (I1->getOpcode() != I2->getOpcode() || !I1->isIdenticalTo(I2)) 80337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return false; 80437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 80537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // If we get here, we can hoist at least one instruction. 80637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BIParent = BI->getParent(); 80737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 80837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner do { 80937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // If we are hoisting the terminator instruction, don't move one (making a 81037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // broken BB), instead clone it, and remove BI. 81137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (isa<TerminatorInst>(I1)) 81237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner goto HoistTerminator; 813fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 81437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // For a normal instruction, we just move one to right before the branch, 81537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // then replace all uses of the other with the first. Finally, we remove 81637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // the now redundant second instruction. 81737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 81837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (!I2->use_empty()) 81937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2->replaceAllUsesWith(I1); 82037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BB2->getInstList().erase(I2); 821fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 82237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I1 = BB1->begin(); 82337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2 = BB2->begin(); 82437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } while (I1->getOpcode() == I2->getOpcode() && I1->isIdenticalTo(I2)); 82537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 82637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return true; 82737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 82837dc938bbe556a9414d063196d367c2f75d07d95Chris LattnerHoistTerminator: 82937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Okay, it is safe to hoist the terminator. 83037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Instruction *NT = I1->clone(); 83137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BIParent->getInstList().insert(BI, NT); 83237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (NT->getType() != Type::VoidTy) { 83337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I1->replaceAllUsesWith(NT); 83437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2->replaceAllUsesWith(NT); 83537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner NT->setName(I1->getName()); 83637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 83737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 83837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Hoisting one of the terminators from our successor is a great thing. 83937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Unfortunately, the successors of the if/else blocks may have PHI nodes in 84037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 84137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // nodes, so we insert select instruction to compute the final result. 84237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 84337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 84437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PHINode *PN; 84537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (BasicBlock::iterator BBI = SI->begin(); 8460f535c6fa8b03491dc110feb65d78922ee29d1fcChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 84737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Value *BB1V = PN->getIncomingValueForBlock(BB1); 84837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Value *BB2V = PN->getIncomingValueForBlock(BB2); 84937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (BB1V != BB2V) { 85037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // These values do not agree. Insert a select instruction before NT 85137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // that determines the right value. 85237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 85337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (SI == 0) 85437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner SI = new SelectInst(BI->getCondition(), BB1V, BB2V, 85537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BB1V->getName()+"."+BB2V->getName(), NT); 85637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Make the PHI node use the select for all incoming values for BB1/BB2 85737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 85837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 85937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PN->setIncomingValue(i, SI); 86037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 86137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 86237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 86337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 86437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Update any PHI nodes in our new successors. 86537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 86637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner AddPredecessorToBlock(*SI, BIParent, BB1); 867fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 86837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BI->eraseFromParent(); 86937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return true; 87037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner} 87137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 8721654cff8e80acdddf5e5f2261595007878924aacChris Lattnernamespace { 8731654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// ConstantIntOrdering - This class implements a stable ordering of constant 8741654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// integers that does not depend on their address. This is important for 8751654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// applications that sort ConstantInt's to ensure uniqueness. 8761654cff8e80acdddf5e5f2261595007878924aacChris Lattner struct ConstantIntOrdering { 8771654cff8e80acdddf5e5f2261595007878924aacChris Lattner bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 8781654cff8e80acdddf5e5f2261595007878924aacChris Lattner return LHS->getRawValue() < RHS->getRawValue(); 8791654cff8e80acdddf5e5f2261595007878924aacChris Lattner } 8801654cff8e80acdddf5e5f2261595007878924aacChris Lattner }; 8811654cff8e80acdddf5e5f2261595007878924aacChris Lattner} 8821654cff8e80acdddf5e5f2261595007878924aacChris Lattner 88301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// SimplifyCFG - This function is used to do simplification of a CFG. For 88401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// example, it adjusts branches to branches to eliminate the extra hop, it 88501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// eliminates unreachable basic blocks, and does other "peephole" optimization 886e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// of the CFG. It returns true if a modification was made. 88701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 88801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// WARNING: The entry node of a function may not be simplified. 88901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 890f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::SimplifyCFG(BasicBlock *BB) { 891dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner bool Changed = false; 89201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner Function *M = BB->getParent(); 89301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 89401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB && BB->getParent() && "Block not embedded in function!"); 89501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB->getTerminator() && "Degenerate basic block encountered!"); 89618961504fc2b299578dba817900a0696cf3ccc4dChris Lattner assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 89701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 89801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove basic blocks that have no predecessors... which are unreachable. 899d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (pred_begin(BB) == pred_end(BB) || 900d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner *pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB)) { 90130b434476796cd4a85c02914687d22f2e5ec95caChris Lattner DEBUG(std::cerr << "Removing BB: \n" << *BB); 90201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 90301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Loop through all of our successors and make sure they know that one 90401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // of their predecessors is going away. 905151c80be8180a7a0aa1594848699aa6b678b3998Chris Lattner for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 906151c80be8180a7a0aa1594848699aa6b678b3998Chris Lattner SI->removePredecessor(BB); 90701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 90801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner while (!BB->empty()) { 90918961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Instruction &I = BB->back(); 91001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If this instruction is used, replace uses with an arbitrary 911f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner // value. Because control flow can't get here, we don't care 912fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // what we replace the value with. Note that since this block is 91301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // unreachable, and all values contained within it must dominate their 91401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // uses, that all uses will eventually be removed. 915fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman if (!I.use_empty()) 916f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner // Make all users of this instruction use undef instead 917f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner I.replaceAllUsesWith(UndefValue::get(I.getType())); 918fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 91901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove the instruction from the basic block 92018961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BB->getInstList().pop_back(); 92101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 92218961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 92301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 92401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 92501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 926694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // Check to see if we can constant propagate this terminator instruction 927694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // away... 928dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner Changed |= ConstantFoldTerminator(BB); 929694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 93019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If this is a returning block with only PHI nodes in it, fold the return 93119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // instruction into any unconditional branch predecessors. 932147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // 933147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // If any predecessor is a conditional branch that just selects among 934147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // different return values, fold the replace the branch/return with a select 935147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // and return. 93619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 93719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BasicBlock::iterator BBI = BB->getTerminator(); 93819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BBI == BB->begin() || isa<PHINode>(--BBI)) { 939147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Find predecessors that end with branches. 94019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner std::vector<BasicBlock*> UncondBranchPreds; 941147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner std::vector<BranchInst*> CondBranchPreds; 94219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 94319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner TerminatorInst *PTI = (*PI)->getTerminator(); 94419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 94519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BI->isUnconditional()) 94619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner UncondBranchPreds.push_back(*PI); 947147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner else 948147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner CondBranchPreds.push_back(BI); 94919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 950fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 95119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we found some, do the transformation! 95219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (!UncondBranchPreds.empty()) { 95319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner while (!UncondBranchPreds.empty()) { 95419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BasicBlock *Pred = UncondBranchPreds.back(); 95519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner UncondBranchPreds.pop_back(); 95619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Instruction *UncondBranch = Pred->getTerminator(); 95719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Clone the return and add it to the end of the predecessor. 95819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Instruction *NewRet = RI->clone(); 95919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().push_back(NewRet); 96019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 96119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If the return instruction returns a value, and if the value was a 96219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // PHI node in "BB", propagate the right value into the return. 96319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (NewRet->getNumOperands() == 1) 96419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0))) 96519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (PN->getParent() == BB) 96619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred)); 96719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Update any PHI nodes in the returning block to realize that we no 96819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // longer branch to them. 96919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BB->removePredecessor(Pred); 97019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().erase(UncondBranch); 97119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 97219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 97319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we eliminated all predecessors of the block, delete the block now. 97419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (pred_begin(BB) == pred_end(BB)) 97519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // We know there are no successors, so just nuke the block. 97619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner M->getBasicBlockList().erase(BB); 97719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 97819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner return true; 97919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 980147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 981147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check out all of the conditional branches going to this return 982147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // instruction. If any of them just select between returns, change the 983147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // branch itself into a select/return pair. 984147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner while (!CondBranchPreds.empty()) { 985147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BranchInst *BI = CondBranchPreds.back(); 986147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner CondBranchPreds.pop_back(); 987147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *TrueSucc = BI->getSuccessor(0); 988147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *FalseSucc = BI->getSuccessor(1); 989147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *OtherSucc = TrueSucc == BB ? FalseSucc : TrueSucc; 990147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 991147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check to see if the non-BB successor is also a return block. 992147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (isa<ReturnInst>(OtherSucc->getTerminator())) { 993147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check to see if there are only PHI instructions in this block. 994147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock::iterator OSI = OtherSucc->getTerminator(); 995147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (OSI == OtherSucc->begin() || isa<PHINode>(--OSI)) { 996147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Okay, we found a branch that is going to two return nodes. If 997147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // there is no return value for this function, just change the 998147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // branch into a return. 999147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (RI->getNumOperands() == 0) { 1000147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner TrueSucc->removePredecessor(BI->getParent()); 1001147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner FalseSucc->removePredecessor(BI->getParent()); 1002147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner new ReturnInst(0, BI); 1003147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BI->getParent()->getInstList().erase(BI); 1004147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner return true; 1005147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1006147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1007147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Otherwise, figure out what the true and false return values are 1008147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // so we can insert a new select instruction. 1009147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner Value *TrueValue = TrueSucc->getTerminator()->getOperand(0); 1010147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner Value *FalseValue = FalseSucc->getTerminator()->getOperand(0); 1011147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1012147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Unwrap any PHI nodes in the return blocks. 1013147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue)) 1014147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (TVPN->getParent() == TrueSucc) 1015147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1016147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue)) 1017147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (FVPN->getParent() == FalseSucc) 1018147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1019147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 10207aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner TrueSucc->removePredecessor(BI->getParent()); 10217aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner FalseSucc->removePredecessor(BI->getParent()); 10227aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner 1023147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Insert a new select instruction. 10240ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner Value *NewRetVal; 10250ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner Value *BrCond = BI->getCondition(); 10260ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (TrueValue != FalseValue) 10270ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner NewRetVal = new SelectInst(BrCond, TrueValue, 10280ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner FalseValue, "retval", BI); 10290ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner else 10300ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner NewRetVal = TrueValue; 10310ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner 1032147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner new ReturnInst(NewRetVal, BI); 1033147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BI->getParent()->getInstList().erase(BI); 10340ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (BrCond->use_empty()) 10350ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (Instruction *BrCondI = dyn_cast<Instruction>(BrCond)) 10360ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner BrCondI->getParent()->getInstList().erase(BrCondI); 1037147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner return true; 1038147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1039147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1040147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 104119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 1042e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->begin())) { 1043e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Check to see if the first instruction in this block is just an unwind. 1044e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // If so, replace any invoke instructions which use this as an exception 1045af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner // destination with call instructions, and any unconditional branch 1046af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner // predecessor with an unwind. 1047e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // 1048e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 1049e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner while (!Preds.empty()) { 1050e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner BasicBlock *Pred = Preds.back(); 1051af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) { 1052af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner if (BI->isUnconditional()) { 1053af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner Pred->getInstList().pop_back(); // nuke uncond branch 1054af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner new UnwindInst(Pred); // Use unwind. 1055af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner Changed = true; 1056af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner } 1057af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 1058e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner if (II->getUnwindDest() == BB) { 1059e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Insert a new branch instruction before the invoke, because this 1060e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // is now a fall through... 1061e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner BranchInst *BI = new BranchInst(II->getNormalDest(), II); 1062e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Pred->getInstList().remove(II); // Take out of symbol table 1063fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1064e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Insert the call now... 1065e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 1066e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner CallInst *CI = new CallInst(II->getCalledValue(), Args, 1067e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner II->getName(), BI); 106816d0db2da8c274f98db4a89ca7a92f970d464b9aChris Lattner CI->setCallingConv(II->getCallingConv()); 1069e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // If the invoke produced a value, the Call now does instead 1070e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner II->replaceAllUsesWith(CI); 1071e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner delete II; 1072e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Changed = true; 1073e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 1074fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1075e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Preds.pop_back(); 1076e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 10778e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 10788e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // If this block is now dead, remove it. 10798e509dd5e81e92a466580ab4022994079952cca9Chris Lattner if (pred_begin(BB) == pred_end(BB)) { 10808e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // We know there are no successors, so just nuke the block. 10818e509dd5e81e92a466580ab4022994079952cca9Chris Lattner M->getBasicBlockList().erase(BB); 10828e509dd5e81e92a466580ab4022994079952cca9Chris Lattner return true; 10838e509dd5e81e92a466580ab4022994079952cca9Chris Lattner } 10848e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 1085623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1086623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (isValueEqualityComparison(SI)) { 1087623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we only have one predecessor, and if it is a branch on this value, 1088623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // see if that predecessor totally determines the outcome of this switch. 1089623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1090623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) 1091623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1092623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 1093623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If the block only contains the switch, see if we can fold the block 1094623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // away into any preds. 1095623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SI == &BB->front()) 1096623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (FoldValueComparisonIntoPredecessors(SI)) 1097623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1098623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 1099542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 11007e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (BI->isUnconditional()) { 11017e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 11027e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner while (isa<PHINode>(*BBI)) ++BBI; 11037e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 11047e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BasicBlock *Succ = BI->getSuccessor(0); 11057e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (BBI->isTerminator() && // Terminator is the only non-phi instruction! 11067e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner Succ != BB) // Don't hurt infinite loops! 11077e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ)) 11087e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner return 1; 11097e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 11107e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } else { // Conditional branch 1111e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (Value *CompVal = isValueEqualityComparison(BI)) { 1112623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we only have one predecessor, and if it is a branch on this value, 1113623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // see if that predecessor totally determines the outcome of this 1114623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // switch. 1115623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1116623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) 1117623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1118623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 1119e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // This block must be empty, except for the setcond inst, if it exists. 1120e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock::iterator I = BB->begin(); 1121e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (&*I == BI || 1122e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner (&*I == cast<Instruction>(BI->getCondition()) && 1123e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner &*++I == BI)) 1124e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (FoldValueComparisonIntoPredecessors(BI)) 1125e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner return SimplifyCFG(BB) | true; 1126e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1127e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 1128e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // If this basic block is ONLY a setcc and a branch, and if a predecessor 1129e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // branches to us and one of our successors, fold the setcc into the 1130e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // predecessor and use logical operations to pick the right destination. 113112fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner BasicBlock *TrueDest = BI->getSuccessor(0); 113212fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner BasicBlock *FalseDest = BI->getSuccessor(1); 1133bdcc0b8c55041ff89b59f0ea2cdbc2ac02f26a3dChris Lattner if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(BI->getCondition())) 1134e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (Cond->getParent() == BB && &BB->front() == Cond && 113512fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner Cond->getNext() == BI && Cond->hasOneUse() && 113612fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner TrueDest != BB && FalseDest != BB) 1137e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI) 1138e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1139a1f79fb08b92801d4ab3cb32fe0bd9d12dfb3954Chris Lattner if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) { 11402636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner BasicBlock *PredBlock = *PI; 1141e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == FalseDest || 1142e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(1) == TrueDest) { 1143e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // Invert the predecessors condition test (xor it with true), 1144e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // which allows us to write this code once. 1145e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Value *NewCond = 1146e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BinaryOperator::createNot(PBI->getCondition(), 1147e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getCondition()->getName()+".not", PBI); 1148e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setCondition(NewCond); 1149e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock *OldTrue = PBI->getSuccessor(0); 1150e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock *OldFalse = PBI->getSuccessor(1); 1151e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(0, OldFalse); 1152e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(1, OldTrue); 1153e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1154e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 1155e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == TrueDest || 1156e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(1) == FalseDest) { 11572636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner // Clone Cond into the predecessor basic block, and or/and the 1158e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // two conditions together. 1159e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction *New = Cond->clone(); 1160e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner New->setName(Cond->getName()); 1161e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Cond->setName(Cond->getName()+".old"); 11622636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner PredBlock->getInstList().insert(PBI, New); 1163e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction::BinaryOps Opcode = 1164e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(0) == TrueDest ? 1165e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction::Or : Instruction::And; 1166fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman Value *NewCond = 1167e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BinaryOperator::create(Opcode, PBI->getCondition(), 1168e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner New, "bothcond", PBI); 1169e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setCondition(NewCond); 1170e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == BB) { 11712636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner AddPredecessorToBlock(TrueDest, PredBlock, BB); 1172e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(0, TrueDest); 1173e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1174e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(1) == BB) { 11752636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner AddPredecessorToBlock(FalseDest, PredBlock, BB); 1176e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(1, FalseDest); 1177e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1178e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner return SimplifyCFG(BB) | 1; 1179e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1180e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1181e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 118292da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // If this block ends with a branch instruction, and if there is one 118392da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // predecessor, see if the previous block ended with a branch on the same 118492da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // condition, which makes this conditional branch redundant. 11857e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 118692da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner if (BranchInst *PBI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 118792da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner if (PBI->isConditional() && 118892da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner PBI->getCondition() == BI->getCondition() && 1189951fdb9764ea7abd1f409712636cf80a86140d90Chris Lattner (PBI->getSuccessor(0) != BB || PBI->getSuccessor(1) != BB)) { 119092da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // Okay, the outcome of this conditional branch is statically 119192da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // knowable. Delete the outgoing CFG edge that is impossible to 119292da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // execute. 119392da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner bool CondIsTrue = PBI->getSuccessor(0) == BB; 119492da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner BI->getSuccessor(CondIsTrue)->removePredecessor(BB); 119592da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner new BranchInst(BI->getSuccessor(!CondIsTrue), BB); 119692da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner BB->getInstList().erase(BI); 119792da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner return SimplifyCFG(BB) | true; 119892da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner } 1199d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner } 1200698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (isa<UnreachableInst>(BB->getTerminator())) { 1201698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If there are any instructions immediately before the unreachable that can 1202698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // be removed, do so. 1203698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Instruction *Unreachable = BB->getTerminator(); 1204698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner while (Unreachable != BB->begin()) { 1205698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock::iterator BBI = Unreachable; 1206698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --BBI; 1207698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (isa<CallInst>(BBI)) break; 1208698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Delete this instruction 1209698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BB->getInstList().erase(BBI); 1210698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1211698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1212698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1213698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the unreachable instruction is the first in the block, take a gander 1214698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // at all of the predecessors of this instruction, and simplify them. 1215698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (&BB->front() == Unreachable) { 1216698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 1217698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 1218698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TerminatorInst *TI = Preds[i]->getTerminator(); 1219698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1220698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1221698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->isUnconditional()) { 1222698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 1223698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new UnreachableInst(TI); 1224698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TI->eraseFromParent(); 1225698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1226698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1227698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else { 1228698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 1229698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new BranchInst(BI->getSuccessor(1), BI); 1230698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BI->eraseFromParent(); 1231698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (BI->getSuccessor(1) == BB) { 1232698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new BranchInst(BI->getSuccessor(0), BI); 1233698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BI->eraseFromParent(); 1234698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1235698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1236698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1237698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1238698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1239698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == BB) { 124042eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner BB->removePredecessor(SI->getParent()); 1241698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1242698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1243698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1244698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1245698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the default value is unreachable, figure out the most popular 1246698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // destination and make it the default. 1247698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(0) == BB) { 1248698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::map<BasicBlock*, unsigned> Popularity; 1249698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1250698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Popularity[SI->getSuccessor(i)]++; 1251698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1252698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Find the most popular block. 1253698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner unsigned MaxPop = 0; 1254698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock *MaxBlock = 0; 1255698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (std::map<BasicBlock*, unsigned>::iterator 1256698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 1257698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (I->second > MaxPop) { 1258698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxPop = I->second; 1259698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxBlock = I->first; 1260698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1261698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1262698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (MaxBlock) { 1263698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Make this the new default, allowing us to delete any explicit 1264698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // edges to it. 1265698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->setSuccessor(0, MaxBlock); 1266698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1267698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 126842eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 126942eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner // it. 127042eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner if (isa<PHINode>(MaxBlock->begin())) 127142eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner for (unsigned i = 0; i != MaxPop-1; ++i) 127242eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner MaxBlock->removePredecessor(SI->getParent()); 127342eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner 1274698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1275698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == MaxBlock) { 1276698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1277698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1278698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1279698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1280698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1281698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 1282698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (II->getUnwindDest() == BB) { 1283698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Convert the invoke to a call instruction. This would be a good 1284698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // place to note that the call does not throw though. 1285698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BranchInst *BI = new BranchInst(II->getNormalDest(), II); 1286698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->removeFromParent(); // Take out of symbol table 1287fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1288698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Insert the call now... 1289698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 1290698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner CallInst *CI = new CallInst(II->getCalledValue(), Args, 1291698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->getName(), BI); 129216d0db2da8c274f98db4a89ca7a92f970d464b9aChris Lattner CI->setCallingConv(II->getCallingConv()); 1293698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the invoke produced a value, the Call does now instead. 1294698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->replaceAllUsesWith(CI); 1295698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner delete II; 1296698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1297698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1298698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1299698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1300698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1301698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If this block is now dead, remove it. 1302698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (pred_begin(BB) == pred_end(BB)) { 1303698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // We know there are no successors, so just nuke the block. 1304698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner M->getBasicBlockList().erase(BB); 1305698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner return true; 1306698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1307698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 130819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 130919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 131001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Merge basic blocks into their predecessor if there is only one distinct 131101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // pred, and if there is only one distinct successor of the predecessor, and 131201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // if there are no PHI nodes. 131301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 13142355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 13152355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BasicBlock *OnlyPred = *PI++; 13162355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 13172355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (*PI != OnlyPred) { 13182355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred = 0; // There are multiple different predecessors... 13192355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner break; 13202355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 132192da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner 13222355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BasicBlock *OnlySucc = 0; 13232355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (OnlyPred && OnlyPred != BB && // Don't break self loops 13242355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 13252355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Check to see if there is only one distinct successor... 13262355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 13272355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlySucc = BB; 13282355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner for (; SI != SE; ++SI) 13292355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (*SI != OnlySucc) { 13302355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlySucc = 0; // There are multiple distinct successors! 133101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner break; 133201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 13332355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 133401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 13352355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (OnlySucc) { 133630b434476796cd4a85c02914687d22f2e5ec95caChris Lattner DEBUG(std::cerr << "Merging: " << *BB << "into: " << *OnlyPred); 13372355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner TerminatorInst *Term = OnlyPred->getTerminator(); 133801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 13392355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Resolve any PHI nodes at the start of the block. They are all 13402355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // guaranteed to have exactly one entry if they exist, unless there are 13412355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // multiple duplicate (but guaranteed to be equal) entries for the 13422355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // incoming edges. This occurs when there are multiple edges from 13432355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // OnlyPred to OnlySucc. 13442355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // 13452355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 13462355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 13472355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BB->getInstList().pop_front(); // Delete the phi node... 13482355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 134991b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner 13502355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Delete the unconditional branch from the predecessor... 13512355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getInstList().pop_back(); 1352fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 13532355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Move all definitions in the successor to the predecessor... 13542355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 1355fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 13562355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Make all PHI nodes that referred to BB now refer to Pred as their 13572355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // source... 13582355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BB->replaceAllUsesWith(OnlyPred); 135918961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 13602355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner std::string OldName = BB->getName(); 136118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 1362fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // Erase basic block from the function... 13632355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner M->getBasicBlockList().erase(BB); 136418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 13652355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Inherit predecessors name if it exists... 13662355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (!OldName.empty() && !OnlyPred->hasName()) 13672355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->setName(OldName); 1368fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 13692355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner return true; 137001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 1371723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 137237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Otherwise, if this block only has a single predecessor, and if that block 137337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // is a conditional branch, see if we can hoist any code from this block up 137437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // into our predecessor. 137537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (OnlyPred) 13767613437db954abafd1230c961e87872df5721957Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 13777613437db954abafd1230c961e87872df5721957Chris Lattner if (BI->isConditional()) { 13787613437db954abafd1230c961e87872df5721957Chris Lattner // Get the other block. 13797613437db954abafd1230c961e87872df5721957Chris Lattner BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); 13807613437db954abafd1230c961e87872df5721957Chris Lattner PI = pred_begin(OtherBB); 13817613437db954abafd1230c961e87872df5721957Chris Lattner ++PI; 13827613437db954abafd1230c961e87872df5721957Chris Lattner if (PI == pred_end(OtherBB)) { 13837613437db954abafd1230c961e87872df5721957Chris Lattner // We have a conditional branch to two blocks that are only reachable 13847613437db954abafd1230c961e87872df5721957Chris Lattner // from the condbr. We know that the condbr dominates the two blocks, 13857613437db954abafd1230c961e87872df5721957Chris Lattner // so see if there is any identical code in the "then" and "else" 13867613437db954abafd1230c961e87872df5721957Chris Lattner // blocks. If so, we can hoist it up to the branching block. 13877613437db954abafd1230c961e87872df5721957Chris Lattner Changed |= HoistThenElseCodeToIf(BI); 13887613437db954abafd1230c961e87872df5721957Chris Lattner } 138937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 139037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 13910d56008f53587531718ec36af82cc24576580b36Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 13920d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 13930d56008f53587531718ec36af82cc24576580b36Chris Lattner // Change br (X == 0 | X == 1), T, F into a switch instruction. 13940d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 13950d56008f53587531718ec36af82cc24576580b36Chris Lattner Instruction *Cond = cast<Instruction>(BI->getCondition()); 13960d56008f53587531718ec36af82cc24576580b36Chris Lattner // If this is a bunch of seteq's or'd together, or if it's a bunch of 13970d56008f53587531718ec36af82cc24576580b36Chris Lattner // 'setne's and'ed together, collect them. 13980d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *CompVal = 0; 13991654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::vector<ConstantInt*> Values; 14000d56008f53587531718ec36af82cc24576580b36Chris Lattner bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 14010d56008f53587531718ec36af82cc24576580b36Chris Lattner if (CompVal && CompVal->getType()->isInteger()) { 14020d56008f53587531718ec36af82cc24576580b36Chris Lattner // There might be duplicate constants in the list, which the switch 14030d56008f53587531718ec36af82cc24576580b36Chris Lattner // instruction can't handle, remove them now. 14041654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 14050d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 1406fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 14070d56008f53587531718ec36af82cc24576580b36Chris Lattner // Figure out which block is which destination. 14080d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *DefaultBB = BI->getSuccessor(1); 14090d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *EdgeBB = BI->getSuccessor(0); 14100d56008f53587531718ec36af82cc24576580b36Chris Lattner if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 1411fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 14120d56008f53587531718ec36af82cc24576580b36Chris Lattner // Create the new switch instruction now. 1413378805969ea928b91aa321746031a8f51667a783Chris Lattner SwitchInst *New = new SwitchInst(CompVal, DefaultBB,Values.size(),BI); 1414fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 14150d56008f53587531718ec36af82cc24576580b36Chris Lattner // Add all of the 'cases' to the switch instruction. 14160d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size(); i != e; ++i) 14170d56008f53587531718ec36af82cc24576580b36Chris Lattner New->addCase(Values[i], EdgeBB); 1418fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 14190d56008f53587531718ec36af82cc24576580b36Chris Lattner // We added edges from PI to the EdgeBB. As such, if there were any 14200d56008f53587531718ec36af82cc24576580b36Chris Lattner // PHI nodes in EdgeBB, they need entries to be added corresponding to 14210d56008f53587531718ec36af82cc24576580b36Chris Lattner // the number of edges added. 14220d56008f53587531718ec36af82cc24576580b36Chris Lattner for (BasicBlock::iterator BBI = EdgeBB->begin(); 14232da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer isa<PHINode>(BBI); ++BBI) { 14242da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(BBI); 14250d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *InVal = PN->getIncomingValueForBlock(*PI); 14260d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 14270d56008f53587531718ec36af82cc24576580b36Chris Lattner PN->addIncoming(InVal, *PI); 14280d56008f53587531718ec36af82cc24576580b36Chris Lattner } 14290d56008f53587531718ec36af82cc24576580b36Chris Lattner 14300d56008f53587531718ec36af82cc24576580b36Chris Lattner // Erase the old branch instruction. 14310d56008f53587531718ec36af82cc24576580b36Chris Lattner (*PI)->getInstList().erase(BI); 14320d56008f53587531718ec36af82cc24576580b36Chris Lattner 14330d56008f53587531718ec36af82cc24576580b36Chris Lattner // Erase the potentially condition tree that was used to computed the 14340d56008f53587531718ec36af82cc24576580b36Chris Lattner // branch condition. 14350d56008f53587531718ec36af82cc24576580b36Chris Lattner ErasePossiblyDeadInstructionTree(Cond); 14360d56008f53587531718ec36af82cc24576580b36Chris Lattner return true; 14370d56008f53587531718ec36af82cc24576580b36Chris Lattner } 14380d56008f53587531718ec36af82cc24576580b36Chris Lattner } 14390d56008f53587531718ec36af82cc24576580b36Chris Lattner 1440723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If there is a trivial two-entry PHI node in this basic block, and we can 1441723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // eliminate it, do so now. 1442723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 1443723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (PN->getNumIncomingValues() == 2) { 1444723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1445723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // statement", which has a very simple dominance structure. Basically, we 1446723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // are trying to find the condition that is being branched on, which 1447723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // subsequently causes this merge to happen. We really want control 1448723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // dependence information for this check, but simplifycfg can't keep it up 1449723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // to date, and this catches most of the cases we care about anyway. 1450723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // 1451723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *IfTrue, *IfFalse; 1452723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse)) { 1453218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner DEBUG(std::cerr << "FOUND IF CONDITION! " << *IfCond << " T: " 1454218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1455723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 14569c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Loop over the PHI's seeing if we can promote them all to select 14579c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // instructions. While we are at it, keep track of the instructions 14589c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // that need to be moved to the dominating block. 14599c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner std::set<Instruction*> AggressiveInsts; 14609c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner bool CanPromote = true; 14619c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 1462723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock::iterator AfterPHIIt = BB->begin(); 14639c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner while (isa<PHINode>(AfterPHIIt)) { 14649c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner PHINode *PN = cast<PHINode>(AfterPHIIt++); 14650289929c6212229980c9057853860ccfd3f81678Chris Lattner if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) { 14660289929c6212229980c9057853860ccfd3f81678Chris Lattner if (PN->getIncomingValue(0) != PN) 14670289929c6212229980c9057853860ccfd3f81678Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 14680289929c6212229980c9057853860ccfd3f81678Chris Lattner else 14690289929c6212229980c9057853860ccfd3f81678Chris Lattner PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 14700289929c6212229980c9057853860ccfd3f81678Chris Lattner } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 14710289929c6212229980c9057853860ccfd3f81678Chris Lattner &AggressiveInsts) || 14720289929c6212229980c9057853860ccfd3f81678Chris Lattner !DominatesMergePoint(PN->getIncomingValue(1), BB, 14730289929c6212229980c9057853860ccfd3f81678Chris Lattner &AggressiveInsts)) { 14749c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote = false; 14759c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner break; 14769c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 14779c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 1478723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 14799c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Did we eliminate all PHI's? 14809c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote |= AfterPHIIt == BB->begin(); 14819c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 14829c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // If we all PHI nodes are promotable, check to make sure that all 14839c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // instructions in the predecessor blocks can be promoted as well. If 14849c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // not, we won't be able to get rid of the control flow, so it's not 14859c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // worth promoting to select instructions. 14864e073a871b208a2c9dfa004b3a93fb26f96daa17Reid Spencer BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 14879c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (CanPromote) { 14889c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner PN = cast<PHINode>(BB->begin()); 14899c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner BasicBlock *Pred = PN->getIncomingBlock(0); 14909c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 14919c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1 = Pred; 14929c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock = *pred_begin(Pred); 14939c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner for (BasicBlock::iterator I = Pred->begin(); 14949c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner !isa<TerminatorInst>(I); ++I) 14959c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!AggressiveInsts.count(I)) { 14969c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // This is not an aggressive instruction that we can promote. 14979c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Because of this, we won't be able to get rid of the control 14989c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // flow, so the xform is not worth it. 14999c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote = false; 15009c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner break; 15019c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 15029c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 15039c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 15049c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner Pred = PN->getIncomingBlock(1); 1505fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman if (CanPromote && 15069c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 15079c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2 = Pred; 15089c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock = *pred_begin(Pred); 15099c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner for (BasicBlock::iterator I = Pred->begin(); 15109c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner !isa<TerminatorInst>(I); ++I) 15119c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!AggressiveInsts.count(I)) { 15129c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // This is not an aggressive instruction that we can promote. 15139c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Because of this, we won't be able to get rid of the control 15149c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // flow, so the xform is not worth it. 15159c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote = false; 15169c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner break; 15179c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 15189c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 15199c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 15209c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 15219c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // If we can still promote the PHI nodes after this gauntlet of tests, 15229c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // do all of the PHI's now. 15239c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (CanPromote) { 15249c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Move all 'aggressive' instructions, which are defined in the 15259c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // conditional parts of the if's up to the dominating block. 15269c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (IfBlock1) { 15279c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 15289c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1->getInstList(), 15299c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1->begin(), 15309c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1->getTerminator()); 15319c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 15329c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (IfBlock2) { 15339c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 15349c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2->getInstList(), 15359c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2->begin(), 15369c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2->getTerminator()); 15379c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 15389c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 15399c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 15409c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Change the PHI node into a select instruction. 1541723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Value *TrueVal = 1542723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1543723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Value *FalseVal = 1544723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1545723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 1546552112f2f8702f2cba8cb5775bc24c3e02ba265cChris Lattner std::string Name = PN->getName(); PN->setName(""); 1547552112f2f8702f2cba8cb5775bc24c3e02ba265cChris Lattner PN->replaceAllUsesWith(new SelectInst(IfCond, TrueVal, FalseVal, 15489c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner Name, AfterPHIIt)); 1549552112f2f8702f2cba8cb5775bc24c3e02ba265cChris Lattner BB->getInstList().erase(PN); 1550723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 15519c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner Changed = true; 1552723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 1553723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 1554723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 1555fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1556694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner return Changed; 155701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 1558