SimplifyCFG.cpp revision 93e985f1b17aef62d58e3198a4604f9f6cfe8d19
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" 19c10305743c313558405079452138f03124e87581Reid Spencer#include "llvm/DerivedTypes.h" 2001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Support/CFG.h" 21551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 2279066fa6acce02c97c714a5a6e151ed8a249721cChris Lattner#include "llvm/Analysis/ConstantFolding.h" 23eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 2493e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner#include "llvm/ADT/SmallVector.h" 2501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <algorithm> 2601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <functional> 27d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner#include <set> 28698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner#include <map> 29f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 30d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 312bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// SafeToMergeTerminators - Return true if it is safe to merge these two 322bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// terminator instructions together. 332bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// 342bdcb56146279009f233933a101cb3dd54a951cdChris Lattnerstatic bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 352bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (SI1 == SI2) return false; // Can't merge with self! 362bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 372bdcb56146279009f233933a101cb3dd54a951cdChris Lattner // It is not safe to merge these two switch instructions if they have a common 382bdcb56146279009f233933a101cb3dd54a951cdChris Lattner // successor, and if that successor has a PHI node, and if *that* PHI node has 392bdcb56146279009f233933a101cb3dd54a951cdChris Lattner // conflicting incoming values from the two switch blocks. 402bdcb56146279009f233933a101cb3dd54a951cdChris Lattner BasicBlock *SI1BB = SI1->getParent(); 412bdcb56146279009f233933a101cb3dd54a951cdChris Lattner BasicBlock *SI2BB = SI2->getParent(); 422bdcb56146279009f233933a101cb3dd54a951cdChris Lattner std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 432bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 442bdcb56146279009f233933a101cb3dd54a951cdChris Lattner for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 452bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (SI1Succs.count(*I)) 462bdcb56146279009f233933a101cb3dd54a951cdChris Lattner for (BasicBlock::iterator BBI = (*I)->begin(); 472bdcb56146279009f233933a101cb3dd54a951cdChris Lattner isa<PHINode>(BBI); ++BBI) { 482bdcb56146279009f233933a101cb3dd54a951cdChris Lattner PHINode *PN = cast<PHINode>(BBI); 492bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (PN->getIncomingValueForBlock(SI1BB) != 502bdcb56146279009f233933a101cb3dd54a951cdChris Lattner PN->getIncomingValueForBlock(SI2BB)) 512bdcb56146279009f233933a101cb3dd54a951cdChris Lattner return false; 522bdcb56146279009f233933a101cb3dd54a951cdChris Lattner } 532bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 542bdcb56146279009f233933a101cb3dd54a951cdChris Lattner return true; 552bdcb56146279009f233933a101cb3dd54a951cdChris Lattner} 562bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 572bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 582bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// now be entries in it from the 'NewPred' block. The values that will be 592bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// flowing into the PHI nodes will be the same as those coming in from 602bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// ExistPred, an existing predecessor of Succ. 612bdcb56146279009f233933a101cb3dd54a951cdChris Lattnerstatic void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 622bdcb56146279009f233933a101cb3dd54a951cdChris Lattner BasicBlock *ExistPred) { 632bdcb56146279009f233933a101cb3dd54a951cdChris Lattner assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 642bdcb56146279009f233933a101cb3dd54a951cdChris Lattner succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 652bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 662bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 672bdcb56146279009f233933a101cb3dd54a951cdChris Lattner for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 682bdcb56146279009f233933a101cb3dd54a951cdChris Lattner PHINode *PN = cast<PHINode>(I); 692bdcb56146279009f233933a101cb3dd54a951cdChris Lattner Value *V = PN->getIncomingValueForBlock(ExistPred); 702bdcb56146279009f233933a101cb3dd54a951cdChris Lattner PN->addIncoming(V, NewPred); 712bdcb56146279009f233933a101cb3dd54a951cdChris Lattner } 722bdcb56146279009f233933a101cb3dd54a951cdChris Lattner} 732bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 743b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 753b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner// almost-empty BB ending in an unconditional branch to Succ, into succ. 7601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 7701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// Assumption: Succ is the single successor for BB. 7801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 793b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattnerstatic bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 8001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 813abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner 8201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Check to see if one of the predecessors of BB is already a predecessor of 83e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // Succ. If so, we cannot do the transformation if there are any PHI nodes 84e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // with incompatible values coming in from the two edges! 8501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 86dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner if (isa<PHINode>(Succ->front())) { 87dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner std::set<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 888e75ee212f95861138f813d095d581828ca111cbChris Lattner for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ); 89dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner PI != PE; ++PI) 90dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner if (std::find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) { 91dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // Loop over all of the PHI nodes checking to see if there are 92dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // incompatible values coming in. 93dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 94dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner PHINode *PN = cast<PHINode>(I); 95dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // Loop up the entries in the PHI node for BB and for *PI if the 96dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // values coming in are non-equal, we cannot merge these two blocks 97dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // (instead we should insert a conditional move or something, then 98dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // merge the blocks). 99dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner if (PN->getIncomingValueForBlock(BB) != 100dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner PN->getIncomingValueForBlock(*PI)) 101dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner return false; // Values are not equal... 102dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner } 103dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner } 104dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner } 1051aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner 1061aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner // Finally, if BB has PHI nodes that are used by things other than the PHIs in 1071aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner // Succ and Succ has predecessors that are not Succ and not Pred, we cannot 1081aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner // fold these blocks, as we don't know whether BB dominates Succ or not to 1091aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner // update the PHI nodes correctly. 1101aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner if (!isa<PHINode>(BB->begin()) || Succ->getSinglePredecessor()) return true; 11101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 1121aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner // If the predecessors of Succ are only BB and Succ itself, we can handle this. 1131aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner bool IsSafe = true; 1141aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner for (pred_iterator PI = pred_begin(Succ), E = pred_end(Succ); PI != E; ++PI) 1151aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner if (*PI != Succ && *PI != BB) { 1161aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner IsSafe = false; 1171aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner break; 1181aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner } 1191aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner if (IsSafe) return true; 1201aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner 1218e75ee212f95861138f813d095d581828ca111cbChris Lattner // If the PHI nodes in BB are only used by instructions in Succ, we are ok if 1228e75ee212f95861138f813d095d581828ca111cbChris Lattner // BB and Succ have no common predecessors. 123a0fcc3ee3fb48553bcf12f471bdf24888a93a123Chris Lattner for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I) { 1241aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner PHINode *PN = cast<PHINode>(I); 1251aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E; 1261aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner ++UI) 1278e75ee212f95861138f813d095d581828ca111cbChris Lattner if (cast<Instruction>(*UI)->getParent() != Succ) 1288e75ee212f95861138f813d095d581828ca111cbChris Lattner return false; 1291aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner } 1301aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner 1318e75ee212f95861138f813d095d581828ca111cbChris Lattner // Scan the predecessor sets of BB and Succ, making sure there are no common 1328e75ee212f95861138f813d095d581828ca111cbChris Lattner // predecessors. Common predecessors would cause us to build a phi node with 1338e75ee212f95861138f813d095d581828ca111cbChris Lattner // differing incoming values, which is not legal. 1348e75ee212f95861138f813d095d581828ca111cbChris Lattner std::set<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 1358e75ee212f95861138f813d095d581828ca111cbChris Lattner for (pred_iterator PI = pred_begin(Succ), E = pred_end(Succ); PI != E; ++PI) 1368e75ee212f95861138f813d095d581828ca111cbChris Lattner if (BBPreds.count(*PI)) 1378e75ee212f95861138f813d095d581828ca111cbChris Lattner return false; 1388e75ee212f95861138f813d095d581828ca111cbChris Lattner 1398e75ee212f95861138f813d095d581828ca111cbChris Lattner return true; 14001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 14101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 1427e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner/// TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional 1437e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner/// branch to Succ, and contains no instructions other than PHI nodes and the 1447e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner/// branch. If possible, eliminate BB. 1457e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattnerstatic bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, 1467e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BasicBlock *Succ) { 1477e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // If our successor has PHI nodes, then we need to update them to include 1487e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // entries for BB's predecessors, not for BB itself. Be careful though, 1497e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // if this transformation fails (returns true) then we cannot do this 1507e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // transformation! 1517e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // 1523b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 1537e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1540d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "Killing Trivial BB: \n" << *BB; 1557e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1563b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner if (isa<PHINode>(Succ->begin())) { 1573b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner // If there is more than one pred of succ, and there are PHI nodes in 1583b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner // the successor, then we need to add incoming edges for the PHI nodes 1593b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner // 1603b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 1613b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner 1623b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner // Loop over all of the PHI nodes in the successor of BB. 1633b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 1643b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner PHINode *PN = cast<PHINode>(I); 1653b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner Value *OldVal = PN->removeIncomingValue(BB, false); 1663b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner assert(OldVal && "No entry in PHI for Pred BB!"); 1673b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner 168dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // If this incoming value is one of the PHI nodes in BB, the new entries 169dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // in the PHI node are the entries from the old PHI. 1703b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 1713b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner PHINode *OldValPN = cast<PHINode>(OldVal); 1723b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 1733b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner PN->addIncoming(OldValPN->getIncomingValue(i), 1743b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner OldValPN->getIncomingBlock(i)); 1753b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner } else { 1763b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 1773b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner End = BBPreds.end(); PredI != End; ++PredI) { 1783b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner // Add an incoming value for each of the new incoming values... 1793b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner PN->addIncoming(OldVal, *PredI); 1803b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner } 1813b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner } 1823b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner } 1833b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner } 1843b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner 1857e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (isa<PHINode>(&BB->front())) { 1867e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner std::vector<BasicBlock*> 1877e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 1887e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1897e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // Move all PHI nodes in BB to Succ if they are alive, otherwise 1907e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // delete them. 1917e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 192dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner if (PN->use_empty()) { 193dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // Just remove the dead phi. This happens if Succ's PHIs were the only 194dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // users of the PHI nodes. 195dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner PN->eraseFromParent(); 1967e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } else { 1977e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // The instruction is alive, so this means that Succ must have 1987e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // *ONLY* had BB as a predecessor, and the PHI node is still valid 1997e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // now. Simply move it into Succ, because we know that BB 2007e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // strictly dominated Succ. 201d423b8b6ca3d2d21a8aa07a877d63e5dc45abc70Chris Lattner Succ->getInstList().splice(Succ->begin(), 202d423b8b6ca3d2d21a8aa07a877d63e5dc45abc70Chris Lattner BB->getInstList(), BB->begin()); 2037e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 2047e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // We need to add new entries for the PHI node to account for 2057e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // predecessors of Succ that the PHI node does not take into 2067e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // account. At this point, since we know that BB dominated succ, 2077e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // this means that we should any newly added incoming edges should 2087e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // use the PHI node as the value for these edges, because they are 2097e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // loop back edges. 2107e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 2117e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (OldSuccPreds[i] != BB) 2127e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner PN->addIncoming(PN, OldSuccPreds[i]); 2137e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } 2147e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } 2157e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 2167e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // Everything that jumped to BB now goes to Succ. 2177e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BB->replaceAllUsesWith(Succ); 21886cc42355593dd1689f7d58d56695c451215b02bChris Lattner if (!Succ->hasName()) Succ->takeName(BB); 2197e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BB->eraseFromParent(); // Delete the old basic block. 2207e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner return true; 2217e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner} 2227e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 223723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// GetIfCondition - Given a basic block (BB) with two predecessors (and 224723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// presumably PHI nodes in it), check to see if the merge at this block is due 225723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// to an "if condition". If so, return the boolean condition that determines 226723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// which entry into BB will be taken. Also, return by references the block 227723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// that will be entered from if the condition is true, and the block that will 228723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// be entered if the condition is false. 229fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// 230723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// 231723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattnerstatic Value *GetIfCondition(BasicBlock *BB, 232723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 233723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 234723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner "Function can only handle blocks with 2 predecessors!"); 235723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *Pred1 = *pred_begin(BB); 236723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *Pred2 = *++pred_begin(BB); 237723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 238723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // We can only handle branches. Other control flow will be lowered to 239723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // branches if possible anyway. 240723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (!isa<BranchInst>(Pred1->getTerminator()) || 241723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner !isa<BranchInst>(Pred2->getTerminator())) 242723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 243723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 244723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 245723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 246723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Eliminate code duplication by ensuring that Pred1Br is conditional if 247723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // either are. 248723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred2Br->isConditional()) { 249723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If both branches are conditional, we don't have an "if statement". In 250723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // reality, we could transform this case, but since the condition will be 251723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // required anyway, we stand no chance of eliminating it, so the xform is 252723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // probably not profitable. 253723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->isConditional()) 254723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 255723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 256723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner std::swap(Pred1, Pred2); 257723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner std::swap(Pred1Br, Pred2Br); 258723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 259723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 260723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->isConditional()) { 261723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If we found a conditional branch predecessor, make sure that it branches 262723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 263723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->getSuccessor(0) == BB && 264723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Pred1Br->getSuccessor(1) == Pred2) { 265723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred1; 266723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred2; 267723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else if (Pred1Br->getSuccessor(0) == Pred2 && 268723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Pred1Br->getSuccessor(1) == BB) { 269723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred2; 270723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred1; 271723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else { 272723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // We know that one arm of the conditional goes to BB, so the other must 273723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // go somewhere unrelated, and this must not be an "if statement". 274723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 275723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 276723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 277723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // The only thing we have to watch out for here is to make sure that Pred2 278723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // doesn't have incoming edges from other blocks. If it does, the condition 279723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // doesn't dominate BB. 280723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (++pred_begin(Pred2) != pred_end(Pred2)) 281723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 282723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 283723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return Pred1Br->getCondition(); 284723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 285723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 286723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Ok, if we got here, both predecessors end with an unconditional branch to 287723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // BB. Don't panic! If both blocks only have a single (identical) 288723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // predecessor, and THAT is a conditional branch, then we're all ok! 289723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (pred_begin(Pred1) == pred_end(Pred1) || 290723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner ++pred_begin(Pred1) != pred_end(Pred1) || 291723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner pred_begin(Pred2) == pred_end(Pred2) || 292723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner ++pred_begin(Pred2) != pred_end(Pred2) || 293723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner *pred_begin(Pred1) != *pred_begin(Pred2)) 294723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 295723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 296723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Otherwise, if this is a conditional branch, then we can use it! 297723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *CommonPred = *pred_begin(Pred1); 298723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 299723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner assert(BI->isConditional() && "Two successors but not conditional?"); 300723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (BI->getSuccessor(0) == Pred1) { 301723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred1; 302723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred2; 303723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else { 304723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred2; 305723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred1; 306723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 307723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return BI->getCondition(); 308723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 309723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 310723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner} 311723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 312723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 313723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// If we have a merge point of an "if condition" as accepted above, return true 314723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// if the specified value dominates the block. We don't handle the true 315723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// generality of domination here, just a special case which works well enough 316723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// for us. 3179c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// 3189c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 3199c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// see if V (which must be an instruction) is cheap to compute and is 3209c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// non-trapping. If both are true, the instruction is inserted into the set and 3219c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// true is returned. 3229c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattnerstatic bool DominatesMergePoint(Value *V, BasicBlock *BB, 3239c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner std::set<Instruction*> *AggressiveInsts) { 324570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 325b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner if (!I) { 326b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner // Non-instructions all dominate instructions, but not all constantexprs 327b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner // can be executed unconditionally. 328b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner if (ConstantExpr *C = dyn_cast<ConstantExpr>(V)) 329b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner if (C->canTrap()) 330b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner return false; 331b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner return true; 332b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner } 333570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner BasicBlock *PBB = I->getParent(); 334570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 335da895d63377b421dc50117befb2bec80d2973526Chris Lattner // We don't want to allow weird loops that might have the "if condition" in 336570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // the bottom of this block. 337570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (PBB == BB) return false; 338570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 339570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // If this instruction is defined in a block that contains an unconditional 340570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // branch to BB, then it must be in the 'conditional' part of the "if 341570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // statement". 342570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator())) 343570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { 3449c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!AggressiveInsts) return false; 345570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Okay, it looks like the instruction IS in the "condition". Check to 346570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // see if its a cheap instruction to unconditionally compute, and if it 347570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // only uses stuff defined outside of the condition. If so, hoist it out. 348570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner switch (I->getOpcode()) { 349570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner default: return false; // Cannot hoist this out safely. 350570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Load: 351570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // We can hoist loads that are non-volatile and obviously cannot trap. 352570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (cast<LoadInst>(I)->isVolatile()) 353570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 354570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (!isa<AllocaInst>(I->getOperand(0)) && 355460f16c6253928519689e882a4dbb7f236f33294Reid Spencer !isa<Constant>(I->getOperand(0))) 356570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 357570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 358570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Finally, we have to check to make sure there are no instructions 359570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // before the load in its basic block, as we are going to hoist the loop 360570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // out to its predecessor. 361570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (PBB->begin() != BasicBlock::iterator(I)) 362570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 363570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner break; 364570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Add: 365570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Sub: 366570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::And: 367570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Or: 368570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Xor: 369570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Shl: 3703822ff5c71478c7c90a50ca57045fb676fcb5005Reid Spencer case Instruction::LShr: 3713822ff5c71478c7c90a50ca57045fb676fcb5005Reid Spencer case Instruction::AShr: 372e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer case Instruction::ICmp: 373e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer case Instruction::FCmp: 374570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner break; // These are all cheap and non-trapping instructions. 375570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner } 376fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 377570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Okay, we can only really hoist these out if their operands are not 378570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // defined in the conditional region. 379570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 3809c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!DominatesMergePoint(I->getOperand(i), BB, 0)) 381570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 3829c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Okay, it's safe to do this! Remember this instruction. 3839c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner AggressiveInsts->insert(I); 384570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner } 385723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 386723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return true; 387723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner} 38801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 389e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer// GatherConstantSetEQs - Given a potentially 'or'd together collection of 390e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer// icmp_eq instructions that compare a value against a constant, return the 391e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer// value being compared, and stick the constant into the Values vector. 3921654cff8e80acdddf5e5f2261595007878924aacChris Lattnerstatic Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values){ 3930d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Instruction *Inst = dyn_cast<Instruction>(V)) 394e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if (Inst->getOpcode() == Instruction::ICmp && 395e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer cast<ICmpInst>(Inst)->getPredicate() == ICmpInst::ICMP_EQ) { 3961654cff8e80acdddf5e5f2261595007878924aacChris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 3970d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 3980d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 3991654cff8e80acdddf5e5f2261595007878924aacChris Lattner } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 4000d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 4010d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(1); 4020d56008f53587531718ec36af82cc24576580b36Chris Lattner } 4030d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::Or) { 4040d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 4050d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 4060d56008f53587531718ec36af82cc24576580b36Chris Lattner if (LHS == RHS) 4070d56008f53587531718ec36af82cc24576580b36Chris Lattner return LHS; 4080d56008f53587531718ec36af82cc24576580b36Chris Lattner } 4090d56008f53587531718ec36af82cc24576580b36Chris Lattner return 0; 4100d56008f53587531718ec36af82cc24576580b36Chris Lattner} 4110d56008f53587531718ec36af82cc24576580b36Chris Lattner 4120d56008f53587531718ec36af82cc24576580b36Chris Lattner// GatherConstantSetNEs - Given a potentially 'and'd together collection of 4130d56008f53587531718ec36af82cc24576580b36Chris Lattner// setne instructions that compare a value against a constant, return the value 4140d56008f53587531718ec36af82cc24576580b36Chris Lattner// being compared, and stick the constant into the Values vector. 4151654cff8e80acdddf5e5f2261595007878924aacChris Lattnerstatic Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values){ 4160d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Instruction *Inst = dyn_cast<Instruction>(V)) 417e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if (Inst->getOpcode() == Instruction::ICmp && 418e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer cast<ICmpInst>(Inst)->getPredicate() == ICmpInst::ICMP_NE) { 4191654cff8e80acdddf5e5f2261595007878924aacChris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 4200d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 4210d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 4221654cff8e80acdddf5e5f2261595007878924aacChris Lattner } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 4230d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 4240d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(1); 4250d56008f53587531718ec36af82cc24576580b36Chris Lattner } 4260d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::And) { 4270d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 4280d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 4290d56008f53587531718ec36af82cc24576580b36Chris Lattner if (LHS == RHS) 4300d56008f53587531718ec36af82cc24576580b36Chris Lattner return LHS; 4310d56008f53587531718ec36af82cc24576580b36Chris Lattner } 4320d56008f53587531718ec36af82cc24576580b36Chris Lattner return 0; 4330d56008f53587531718ec36af82cc24576580b36Chris Lattner} 4340d56008f53587531718ec36af82cc24576580b36Chris Lattner 4350d56008f53587531718ec36af82cc24576580b36Chris Lattner 4360d56008f53587531718ec36af82cc24576580b36Chris Lattner 4370d56008f53587531718ec36af82cc24576580b36Chris Lattner/// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 4380d56008f53587531718ec36af82cc24576580b36Chris Lattner/// bunch of comparisons of one value against constants, return the value and 4390d56008f53587531718ec36af82cc24576580b36Chris Lattner/// the constants being compared. 4400d56008f53587531718ec36af82cc24576580b36Chris Lattnerstatic bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 4411654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::vector<ConstantInt*> &Values) { 4420d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Cond->getOpcode() == Instruction::Or) { 4430d56008f53587531718ec36af82cc24576580b36Chris Lattner CompVal = GatherConstantSetEQs(Cond, Values); 4440d56008f53587531718ec36af82cc24576580b36Chris Lattner 4450d56008f53587531718ec36af82cc24576580b36Chris Lattner // Return true to indicate that the condition is true if the CompVal is 4460d56008f53587531718ec36af82cc24576580b36Chris Lattner // equal to one of the constants. 4470d56008f53587531718ec36af82cc24576580b36Chris Lattner return true; 4480d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Cond->getOpcode() == Instruction::And) { 4490d56008f53587531718ec36af82cc24576580b36Chris Lattner CompVal = GatherConstantSetNEs(Cond, Values); 450fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 4510d56008f53587531718ec36af82cc24576580b36Chris Lattner // Return false to indicate that the condition is false if the CompVal is 4520d56008f53587531718ec36af82cc24576580b36Chris Lattner // equal to one of the constants. 4530d56008f53587531718ec36af82cc24576580b36Chris Lattner return false; 4540d56008f53587531718ec36af82cc24576580b36Chris Lattner } 4550d56008f53587531718ec36af82cc24576580b36Chris Lattner return false; 4560d56008f53587531718ec36af82cc24576580b36Chris Lattner} 4570d56008f53587531718ec36af82cc24576580b36Chris Lattner 4580d56008f53587531718ec36af82cc24576580b36Chris Lattner/// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and 4590d56008f53587531718ec36af82cc24576580b36Chris Lattner/// has no side effects, nuke it. If it uses any instructions that become dead 4600d56008f53587531718ec36af82cc24576580b36Chris Lattner/// because the instruction is now gone, nuke them too. 4610d56008f53587531718ec36af82cc24576580b36Chris Lattnerstatic void ErasePossiblyDeadInstructionTree(Instruction *I) { 4628cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner if (!isInstructionTriviallyDead(I)) return; 4638cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner 4648cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner std::vector<Instruction*> InstrsToInspect; 4658cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner InstrsToInspect.push_back(I); 4668cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner 4678cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner while (!InstrsToInspect.empty()) { 4688cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner I = InstrsToInspect.back(); 4698cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner InstrsToInspect.pop_back(); 4708cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner 4718cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner if (!isInstructionTriviallyDead(I)) continue; 4728cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner 4738cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner // If I is in the work list multiple times, remove previous instances. 4748cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner for (unsigned i = 0, e = InstrsToInspect.size(); i != e; ++i) 4758cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner if (InstrsToInspect[i] == I) { 4768cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner InstrsToInspect.erase(InstrsToInspect.begin()+i); 4778cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner --i, --e; 4788cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner } 4798cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner 4808cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner // Add operands of dead instruction to worklist. 4818cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 4828cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i))) 4838cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner InstrsToInspect.push_back(OpI); 4848cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner 4858cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner // Remove dead instruction. 4868cfe6335e40a1190e96e470b35a760a2bad7f650Chris Lattner I->eraseFromParent(); 4870d56008f53587531718ec36af82cc24576580b36Chris Lattner } 4880d56008f53587531718ec36af82cc24576580b36Chris Lattner} 4890d56008f53587531718ec36af82cc24576580b36Chris Lattner 490542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// isValueEqualityComparison - Return true if the specified terminator checks to 491542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// see if a value is equal to constant integer value. 492542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic Value *isValueEqualityComparison(TerminatorInst *TI) { 4934bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 4944bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner // Do not permit merging of large switch instructions into their 4954bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner // predecessors unless there is only one predecessor. 4964bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), 4974bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner pred_end(SI->getParent())) > 128) 4984bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner return 0; 4994bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner 500542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SI->getCondition(); 5014bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner } 502542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 503542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (BI->isConditional() && BI->getCondition()->hasOneUse()) 504e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) 505e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if ((ICI->getPredicate() == ICmpInst::ICMP_EQ || 506e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer ICI->getPredicate() == ICmpInst::ICMP_NE) && 507e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer isa<ConstantInt>(ICI->getOperand(1))) 508e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer return ICI->getOperand(0); 509542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return 0; 510542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 511542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 512542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// Given a value comparison instruction, decode all of the 'cases' that it 513542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// represents and return the 'default' block. 514542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic BasicBlock * 515fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha BrukmanGetValueEqualityComparisonCases(TerminatorInst *TI, 516542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, 517542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock*> > &Cases) { 518542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 519542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Cases.reserve(SI->getNumCases()); 520542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 521be54dcc8a9d14592e324d6e6ae1322782e17f09fChris Lattner Cases.push_back(std::make_pair(SI->getCaseValue(i), SI->getSuccessor(i))); 522542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SI->getDefaultDest(); 523542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 524542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 525542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BranchInst *BI = cast<BranchInst>(TI); 526e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 527e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Cases.push_back(std::make_pair(cast<ConstantInt>(ICI->getOperand(1)), 528e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer BI->getSuccessor(ICI->getPredicate() == 529e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer ICmpInst::ICMP_NE))); 530e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); 531542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 532542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 533542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 534623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// EliminateBlockCases - Given an vector of bb/value pairs, remove any entries 535623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// in the list that match the specified block. 536fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukmanstatic void EliminateBlockCases(BasicBlock *BB, 537623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) { 538623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = Cases.size(); i != e; ++i) 539623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (Cases[i].second == BB) { 540623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Cases.erase(Cases.begin()+i); 541623369ac5669a3667a94a3cbba342dea78845615Chris Lattner --i; --e; 542623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 543623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 544623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 545623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 546623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// well. 547623369ac5669a3667a94a3cbba342dea78845615Chris Lattnerstatic bool 548623369ac5669a3667a94a3cbba342dea78845615Chris LattnerValuesOverlap(std::vector<std::pair<ConstantInt*, BasicBlock*> > &C1, 549623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > &C2) { 550623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > *V1 = &C1, *V2 = &C2; 551623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 552623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Make V1 be smaller than V2. 553623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() > V2->size()) 554623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::swap(V1, V2); 555623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 556623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() == 0) return false; 557623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() == 1) { 558623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Just scan V2. 559623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ConstantInt *TheVal = (*V1)[0].first; 560623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = V2->size(); i != e; ++i) 561623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TheVal == (*V2)[i].first) 562623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 563623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 564623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 565623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Otherwise, just sort both lists and compare element by element. 566623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::sort(V1->begin(), V1->end()); 567623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::sort(V2->begin(), V2->end()); 568623369ac5669a3667a94a3cbba342dea78845615Chris Lattner unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 569623369ac5669a3667a94a3cbba342dea78845615Chris Lattner while (i1 != e1 && i2 != e2) { 570623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if ((*V1)[i1].first == (*V2)[i2].first) 571623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 572623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if ((*V1)[i1].first < (*V2)[i2].first) 573623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ++i1; 574623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 575623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ++i2; 576623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 577623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; 578623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 579623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 580623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 581623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// terminator instruction and its block is known to only have a single 582623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// predecessor block, check to see if that predecessor is also a value 583623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// comparison with the same value, and if that comparison determines the outcome 584623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// of this comparison. If so, simplify TI. This does a very limited form of 585623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// jump threading. 586623369ac5669a3667a94a3cbba342dea78845615Chris Lattnerstatic bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 587623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *Pred) { 588623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 589623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (!PredVal) return false; // Not a value comparison in predecessor. 590623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 591623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Value *ThisVal = isValueEqualityComparison(TI); 592623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(ThisVal && "This isn't a value comparison!!"); 593623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ThisVal != PredVal) return false; // Different predicates. 594623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 595623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Find out information about when control will move from Pred to TI's block. 596623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 597623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 598623369ac5669a3667a94a3cbba342dea78845615Chris Lattner PredCases); 599623369ac5669a3667a94a3cbba342dea78845615Chris Lattner EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 600fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 601623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Find information about how control leaves this block. 602623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases; 603623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 604623369ac5669a3667a94a3cbba342dea78845615Chris Lattner EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 605623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 606623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If TI's block is the default block from Pred's comparison, potentially 607623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // simplify TI based on this knowledge. 608623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (PredDef == TI->getParent()) { 609623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we are here, we know that the value is none of those cases listed in 610623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // PredCases. If there are any cases in ThisCases that are in PredCases, we 611623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // can simplify TI. 612623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ValuesOverlap(PredCases, ThisCases)) { 613623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BranchInst *BTI = dyn_cast<BranchInst>(TI)) { 614623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, one of the successors of this condbr is dead. Convert it to a 615623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // uncond br. 616623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(ThisCases.size() == 1 && "Branch can only have one case!"); 617623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Value *Cond = BTI->getCondition(); 618623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Insert the new branch. 619623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Instruction *NI = new BranchInst(ThisDef, TI); 620623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 621623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Remove PHI node entries for the dead edge. 622623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ThisCases[0].second->removePredecessor(TI->getParent()); 623623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 6240d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "Threading pred instr: " << *Pred->getTerminator() 6250d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"; 626623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 627623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TI->eraseFromParent(); // Nuke the old one. 628623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If condition is now dead, nuke it. 629623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (Instruction *CondI = dyn_cast<Instruction>(Cond)) 630623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ErasePossiblyDeadInstructionTree(CondI); 631623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 632623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 633623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else { 634623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SwitchInst *SI = cast<SwitchInst>(TI); 635623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, TI has cases that are statically dead, prune them away. 636623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::set<Constant*> DeadCases; 637623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 638623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DeadCases.insert(PredCases[i].first); 639623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 6400d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "Threading pred instr: " << *Pred->getTerminator() 6410d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling << "Through successor TI: " << *TI; 642623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 643623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = SI->getNumCases()-1; i != 0; --i) 644623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (DeadCases.count(SI->getCaseValue(i))) { 645623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SI->getSuccessor(i)->removePredecessor(TI->getParent()); 646623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SI->removeCase(i); 647623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 648623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 6490d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "Leaving: " << *TI << "\n"; 650623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 651623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 652623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 653623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 654623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else { 655623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Otherwise, TI's block must correspond to some matched value. Find out 656623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // which value (or set of values) this is. 657623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ConstantInt *TIV = 0; 658623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *TIBB = TI->getParent(); 659623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 660623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (PredCases[i].second == TIBB) 661623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TIV == 0) 662623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TIV = PredCases[i].first; 663623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 664623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; // Cannot handle multiple values coming to this block. 665623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(TIV && "No edge from pred to succ?"); 666623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 667623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, we found the one constant that our value can be if we get into TI's 668623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // BB. Find out which successor will unconditionally be branched to. 669623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *TheRealDest = 0; 670623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 671623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ThisCases[i].first == TIV) { 672623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TheRealDest = ThisCases[i].second; 673623369ac5669a3667a94a3cbba342dea78845615Chris Lattner break; 674623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 675623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 676623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If not handled by any explicit cases, it is handled by the default case. 677623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TheRealDest == 0) TheRealDest = ThisDef; 678623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 679623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Remove PHI node entries for dead edges. 680623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *CheckEdge = TheRealDest; 681623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 682623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (*SI != CheckEdge) 683623369ac5669a3667a94a3cbba342dea78845615Chris Lattner (*SI)->removePredecessor(TIBB); 684623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 685623369ac5669a3667a94a3cbba342dea78845615Chris Lattner CheckEdge = 0; 686623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 687623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Insert the new branch. 688623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Instruction *NI = new BranchInst(TheRealDest, TI); 689623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 6900d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "Threading pred instr: " << *Pred->getTerminator() 6910d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"; 692623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Instruction *Cond = 0; 693623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 694623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Cond = dyn_cast<Instruction>(BI->getCondition()); 695623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TI->eraseFromParent(); // Nuke the old one. 696623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 697623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (Cond) ErasePossiblyDeadInstructionTree(Cond); 698623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 699623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 700623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; 701623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 702623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 703542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// FoldValueComparisonIntoPredecessors - The specified terminator is a value 704542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// equality comparison instruction (either a switch or a branch on "X == c"). 705542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// See if any of the predecessors of the terminator block are value comparisons 706542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// on the same value. If so, and if safe to do so, fold them together. 707542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 708542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *BB = TI->getParent(); 709542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Value *CV = isValueEqualityComparison(TI); // CondVal 710542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner assert(CV && "Not a comparison?"); 711542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner bool Changed = false; 712542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 713542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 714542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner while (!Preds.empty()) { 715542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *Pred = Preds.back(); 716542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Preds.pop_back(); 717fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 718542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // See if the predecessor is a comparison with the same value. 719542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner TerminatorInst *PTI = Pred->getTerminator(); 720542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 721542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 722542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 723542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Figure out which 'cases' to copy from SI to PSI. 724542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 725542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 726542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 727542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 728542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 729542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 730542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Based on whether the default edge from PTI goes to BB or not, fill in 731542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // PredCases and PredDefault with the new switch cases we would like to 732542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // build. 733542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<BasicBlock*> NewSuccessors; 734542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 735542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredDefault == BB) { 736542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is the default destination from PTI, only the edges in TI 737542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // that don't occur in PTI, or that branch to BB will be activated. 738542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::set<ConstantInt*> PTIHandled; 739542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 740542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredCases[i].second != BB) 741542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.insert(PredCases[i].first); 742542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner else { 743542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // The default destination is BB, we don't need explicit targets. 744542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::swap(PredCases[i], PredCases.back()); 745542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.pop_back(); 746542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner --i; --e; 747542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 748542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 749542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Reconstruct the new switch statement we will be building. 750542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredDefault != BBDefault) { 751542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredDefault->removePredecessor(Pred); 752542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredDefault = BBDefault; 753542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBDefault); 754542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 755542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 756542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (!PTIHandled.count(BBCases[i].first) && 757542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BBCases[i].second != BBDefault) { 758542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(BBCases[i]); 759542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBCases[i].second); 760542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 761542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 762542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } else { 763542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is not the default destination from PSI, only the edges 764542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // in SI that occur in PSI with a destination of BB will be 765542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // activated. 766542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::set<ConstantInt*> PTIHandled; 767542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 768542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredCases[i].second == BB) { 769542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.insert(PredCases[i].first); 770542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::swap(PredCases[i], PredCases.back()); 771542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.pop_back(); 772542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner --i; --e; 773542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 774542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 775542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, now we know which constants were sent to BB from the 776542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // predecessor. Figure out where they will all go now. 777542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 778542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PTIHandled.count(BBCases[i].first)) { 779542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is one we are capable of getting... 780542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(BBCases[i]); 781542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBCases[i].second); 782542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.erase(BBCases[i].first);// This constant is taken care of 783542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 784542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 785542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If there are any constants vectored to BB that TI doesn't handle, 786542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // they must go to the default destination of TI. 787542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (std::set<ConstantInt*>::iterator I = PTIHandled.begin(), 788542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner E = PTIHandled.end(); I != E; ++I) { 789542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(std::make_pair(*I, BBDefault)); 790542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBDefault); 791542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 792542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 793542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 794542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, at this point, we know which new successor Pred will get. Make 795542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // sure we update the number of entries in the PHI nodes for these 796542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // successors. 797542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 798542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 799542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 800542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Now that the successors are updated, create the new Switch instruction. 801378805969ea928b91aa321746031a8f51667a783Chris Lattner SwitchInst *NewSI = new SwitchInst(CV, PredDefault, PredCases.size(),PTI); 802542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 803542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSI->addCase(PredCases[i].first, PredCases[i].second); 80413b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner 80513b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner Instruction *DeadCond = 0; 80613b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 80713b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner // If PTI is a branch, remember the condition. 80813b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner DeadCond = dyn_cast<Instruction>(BI->getCondition()); 809542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Pred->getInstList().erase(PTI); 810542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 81113b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner // If the condition is dead now, remove the instruction tree. 81213b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner if (DeadCond) ErasePossiblyDeadInstructionTree(DeadCond); 81313b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner 814542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, last check. If BB is still a successor of PSI, then we must 815542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // have an infinite loop case. If so, add an infinitely looping block 816542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // to handle the case to preserve the behavior of the code. 817542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *InfLoopBlock = 0; 818542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 819542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (NewSI->getSuccessor(i) == BB) { 820542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (InfLoopBlock == 0) { 821542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Insert it at the end of the loop, because it's either code, 822542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // or it won't matter if it's hot. :) 823542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner InfLoopBlock = new BasicBlock("infloop", BB->getParent()); 824542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner new BranchInst(InfLoopBlock, InfLoopBlock); 825542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 826542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSI->setSuccessor(i, InfLoopBlock); 827542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 828fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 829542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Changed = true; 830542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 831542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 832542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return Changed; 833542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 834542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 8356306d07aa8cf71e3c7fed7f295665f53595473ebChris Lattner/// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and 83637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// BB2, hoist any common code in the two blocks up into the branch block. The 83737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// caller of this function guarantees that BI's block dominates BB1 and BB2. 83837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattnerstatic bool HoistThenElseCodeToIf(BranchInst *BI) { 83937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // This does very trivial matching, with limited scanning, to find identical 84037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // instructions in the two blocks. In particular, we don't want to get into 84137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 84237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // such, we currently just scan for obviously identical instructions in an 84337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // identical order. 84437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 84537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 84637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 84737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Instruction *I1 = BB1->begin(), *I2 = BB2->begin(); 848e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if (I1->getOpcode() != I2->getOpcode() || isa<PHINode>(I1) || 849e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer isa<InvokeInst>(I1) || !I1->isIdenticalTo(I2)) 85037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return false; 85137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 85237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // If we get here, we can hoist at least one instruction. 85337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BIParent = BI->getParent(); 85437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 85537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner do { 85637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // If we are hoisting the terminator instruction, don't move one (making a 85737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // broken BB), instead clone it, and remove BI. 85837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (isa<TerminatorInst>(I1)) 85937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner goto HoistTerminator; 860fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 86137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // For a normal instruction, we just move one to right before the branch, 86237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // then replace all uses of the other with the first. Finally, we remove 86337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // the now redundant second instruction. 86437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 86537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (!I2->use_empty()) 86637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2->replaceAllUsesWith(I1); 86737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BB2->getInstList().erase(I2); 868fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 86937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I1 = BB1->begin(); 87037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2 = BB2->begin(); 87137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } while (I1->getOpcode() == I2->getOpcode() && I1->isIdenticalTo(I2)); 87237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 87337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return true; 87437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 87537dc938bbe556a9414d063196d367c2f75d07d95Chris LattnerHoistTerminator: 87637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Okay, it is safe to hoist the terminator. 87737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Instruction *NT = I1->clone(); 87837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BIParent->getInstList().insert(BI, NT); 87937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (NT->getType() != Type::VoidTy) { 88037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I1->replaceAllUsesWith(NT); 88137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2->replaceAllUsesWith(NT); 88286cc42355593dd1689f7d58d56695c451215b02bChris Lattner NT->takeName(I1); 88337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 88437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 88537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Hoisting one of the terminators from our successor is a great thing. 88637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Unfortunately, the successors of the if/else blocks may have PHI nodes in 88737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 88837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // nodes, so we insert select instruction to compute the final result. 88937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 89037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 89137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PHINode *PN; 89237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (BasicBlock::iterator BBI = SI->begin(); 8930f535c6fa8b03491dc110feb65d78922ee29d1fcChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 89437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Value *BB1V = PN->getIncomingValueForBlock(BB1); 89537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Value *BB2V = PN->getIncomingValueForBlock(BB2); 89637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (BB1V != BB2V) { 89737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // These values do not agree. Insert a select instruction before NT 89837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // that determines the right value. 89937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 90037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (SI == 0) 90137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner SI = new SelectInst(BI->getCondition(), BB1V, BB2V, 90237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BB1V->getName()+"."+BB2V->getName(), NT); 90337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Make the PHI node use the select for all incoming values for BB1/BB2 90437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 90537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 90637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PN->setIncomingValue(i, SI); 90737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 90837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 90937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 91037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 91137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Update any PHI nodes in our new successors. 91237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 91337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner AddPredecessorToBlock(*SI, BIParent, BB1); 914fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 91537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BI->eraseFromParent(); 91637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return true; 91737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner} 91837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 9192e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner/// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch 9202e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner/// across this block. 9212e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattnerstatic bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { 9222e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 923e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner unsigned Size = 0; 924e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 9252e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // If this basic block contains anything other than a PHI (which controls the 9262e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // branch) and branch itself, bail out. FIXME: improve this in the future. 927e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI, ++Size) { 928e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (Size > 10) return false; // Don't clone large BB's. 9292e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 930e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // We can only support instructions that are do not define values that are 931e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // live outside of the current basic block. 932e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 933e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner UI != E; ++UI) { 934e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner Instruction *U = cast<Instruction>(*UI); 935e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (U->getParent() != BB || isa<PHINode>(U)) return false; 936e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 9372e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 9382e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // Looks ok, continue checking. 9392e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner } 940e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 9412e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner return true; 9422e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner} 9432e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 944eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value 945eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// that is defined in the same block as the branch and if any PHI entries are 946eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// constants, thread edges corresponding to that entry to be branches to their 947eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// ultimate destination. 948eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattnerstatic bool FoldCondBranchOnPHI(BranchInst *BI) { 949eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BasicBlock *BB = BI->getParent(); 950eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 9519c88d9816246d260b37cdc689f313c56aec6941eChris Lattner // NOTE: we currently cannot transform this case if the PHI node is used 9529c88d9816246d260b37cdc689f313c56aec6941eChris Lattner // outside of the block. 9532e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (!PN || PN->getParent() != BB || !PN->hasOneUse()) 9542e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner return false; 955eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 956eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Degenerate case of a single entry PHI. 957eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PN->getNumIncomingValues() == 1) { 958eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PN->getIncomingValue(0) != PN) 959eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 960eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner else 961eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 962eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PN->eraseFromParent(); 963eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return true; 964eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 965eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 966eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Now we know that this block has multiple preds and two succs. 9672e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; 968eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 969eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Okay, this is a simple enough basic block. See if any phi values are 970eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // constants. 9716b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 9726b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng ConstantInt *CB; 9736b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if ((CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i))) && 9744fe16d607d11e29d742208894909733f5ad01f8fReid Spencer CB->getType() == Type::Int1Ty) { 975eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Okay, we now know that all edges from PredBB should be revectored to 976eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // branch to RealDest. 977eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BasicBlock *PredBB = PN->getIncomingBlock(i); 978579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); 979eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 980e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (RealDest == BB) continue; // Skip self loops. 981eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 982e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // The dest block might have PHI nodes, other predecessors and other 983e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // difficult cases. Instead of being smart about this, just insert a new 984e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // block that jumps to the destination block, effectively splitting 985e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // the edge we are about to create. 986e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner BasicBlock *EdgeBB = new BasicBlock(RealDest->getName()+".critedge", 987e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner RealDest->getParent(), RealDest); 988e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner new BranchInst(RealDest, EdgeBB); 989e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner PHINode *PN; 990e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (BasicBlock::iterator BBI = RealDest->begin(); 991e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 992e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner Value *V = PN->getIncomingValueForBlock(BB); 993e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner PN->addIncoming(V, EdgeBB); 994e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 995e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 996e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // BB may have instructions that are being threaded over. Clone these 997e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // instructions into EdgeBB. We know that there will be no uses of the 998e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // cloned instructions outside of EdgeBB. 999e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner BasicBlock::iterator InsertPt = EdgeBB->begin(); 1000e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner std::map<Value*, Value*> TranslateMap; // Track translated values. 1001e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1002e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 1003e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); 1004e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } else { 1005e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Clone the instruction. 1006e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner Instruction *N = BBI->clone(); 1007e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (BBI->hasName()) N->setName(BBI->getName()+".c"); 1008e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 1009e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Update operands due to translation. 1010e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 1011e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner std::map<Value*, Value*>::iterator PI = 1012e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner TranslateMap.find(N->getOperand(i)); 1013e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (PI != TranslateMap.end()) 1014e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner N->setOperand(i, PI->second); 1015e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1016e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 1017e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Check for trivial simplification. 1018e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (Constant *C = ConstantFoldInstruction(N)) { 1019e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner TranslateMap[BBI] = C; 1020e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner delete N; // Constant folded away, don't need actual inst 1021e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } else { 1022e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Insert the new instruction into its new home. 1023e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner EdgeBB->getInstList().insert(InsertPt, N); 1024e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (!BBI->use_empty()) 1025e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner TranslateMap[BBI] = N; 1026e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1027e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1028e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1029e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 1030eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Loop over all of the edges from PredBB to BB, changing them to branch 1031e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // to EdgeBB instead. 1032eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner TerminatorInst *PredBBTI = PredBB->getTerminator(); 1033eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 1034eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PredBBTI->getSuccessor(i) == BB) { 1035eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BB->removePredecessor(PredBB); 1036e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner PredBBTI->setSuccessor(i, EdgeBB); 1037eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 1038eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1039eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Recurse, simplifying any other constants. 1040eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return FoldCondBranchOnPHI(BI) | true; 1041eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 10426b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng } 1043eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1044eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return false; 1045eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner} 1046eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1047f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner/// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry 1048f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner/// PHI node, see if we can eliminate it. 1049f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattnerstatic bool FoldTwoEntryPHINode(PHINode *PN) { 1050f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1051f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // statement", which has a very simple dominance structure. Basically, we 1052f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // are trying to find the condition that is being branched on, which 1053f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // subsequently causes this merge to happen. We really want control 1054f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // dependence information for this check, but simplifycfg can't keep it up 1055f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // to date, and this catches most of the cases we care about anyway. 1056f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // 1057f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *BB = PN->getParent(); 1058f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *IfTrue, *IfFalse; 1059f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); 1060f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (!IfCond) return false; 1061f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1062822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // Okay, we found that we can merge this two-entry phi node into a select. 1063822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // Doing so would require us to fold *all* two entry phi nodes in this block. 1064822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // At some point this becomes non-profitable (particularly if the target 1065822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // doesn't support cmov's). Only do this transformation if there are two or 1066822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // fewer PHI nodes in this block. 1067822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner unsigned NumPhis = 0; 1068822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I) 1069822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner if (NumPhis > 2) 1070822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner return false; 1071822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner 10720d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "FOUND IF CONDITION! " << *IfCond << " T: " 10730d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"; 1074f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1075f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Loop over the PHI's seeing if we can promote them all to select 1076f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // instructions. While we are at it, keep track of the instructions 1077f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // that need to be moved to the dominating block. 1078f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner std::set<Instruction*> AggressiveInsts; 1079f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1080f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock::iterator AfterPHIIt = BB->begin(); 1081f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner while (isa<PHINode>(AfterPHIIt)) { 1082f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PHINode *PN = cast<PHINode>(AfterPHIIt++); 1083f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) { 1084f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (PN->getIncomingValue(0) != PN) 1085f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 1086f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner else 1087f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 1088f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 1089f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner &AggressiveInsts) || 1090f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner !DominatesMergePoint(PN->getIncomingValue(1), BB, 1091f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner &AggressiveInsts)) { 1092055dc102e97316d423bd068f8b228d27fb93c90aChris Lattner return false; 1093f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1094f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1095f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1096f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // If we all PHI nodes are promotable, check to make sure that all 1097f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // instructions in the predecessor blocks can be promoted as well. If 1098f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // not, we won't be able to get rid of the control flow, so it's not 1099f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // worth promoting to select instructions. 1100f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 1101f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN = cast<PHINode>(BB->begin()); 1102f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *Pred = PN->getIncomingBlock(0); 1103f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1104f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1 = Pred; 1105f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock = *pred_begin(Pred); 1106f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner for (BasicBlock::iterator I = Pred->begin(); 1107f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner !isa<TerminatorInst>(I); ++I) 1108f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (!AggressiveInsts.count(I)) { 1109f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // This is not an aggressive instruction that we can promote. 1110f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Because of this, we won't be able to get rid of the control 1111f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // flow, so the xform is not worth it. 1112f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner return false; 1113f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1114f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1115f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1116f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Pred = PN->getIncomingBlock(1); 1117f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1118f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2 = Pred; 1119f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock = *pred_begin(Pred); 1120f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner for (BasicBlock::iterator I = Pred->begin(); 1121f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner !isa<TerminatorInst>(I); ++I) 1122f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (!AggressiveInsts.count(I)) { 1123f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // This is not an aggressive instruction that we can promote. 1124f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Because of this, we won't be able to get rid of the control 1125f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // flow, so the xform is not worth it. 1126f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner return false; 1127f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1128f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1129f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1130f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // If we can still promote the PHI nodes after this gauntlet of tests, 1131f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // do all of the PHI's now. 1132f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1133f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Move all 'aggressive' instructions, which are defined in the 1134f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // conditional parts of the if's up to the dominating block. 1135f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (IfBlock1) { 1136f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 1137f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1->getInstList(), 1138f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1->begin(), 1139f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1->getTerminator()); 1140f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1141f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (IfBlock2) { 1142f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 1143f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2->getInstList(), 1144f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2->begin(), 1145f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2->getTerminator()); 1146f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1147f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1148f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 1149f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Change the PHI node into a select instruction. 1150f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Value *TrueVal = 1151f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1152f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Value *FalseVal = 1153f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1154f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 115586cc42355593dd1689f7d58d56695c451215b02bChris Lattner Value *NV = new SelectInst(IfCond, TrueVal, FalseVal, "", AfterPHIIt); 115686cc42355593dd1689f7d58d56695c451215b02bChris Lattner PN->replaceAllUsesWith(NV); 115786cc42355593dd1689f7d58d56695c451215b02bChris Lattner NV->takeName(PN); 115886cc42355593dd1689f7d58d56695c451215b02bChris Lattner 1159f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BB->getInstList().erase(PN); 1160f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1161f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner return true; 1162f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner} 1163eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 11641654cff8e80acdddf5e5f2261595007878924aacChris Lattnernamespace { 11651654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// ConstantIntOrdering - This class implements a stable ordering of constant 11661654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// integers that does not depend on their address. This is important for 11671654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// applications that sort ConstantInt's to ensure uniqueness. 11681654cff8e80acdddf5e5f2261595007878924aacChris Lattner struct ConstantIntOrdering { 11691654cff8e80acdddf5e5f2261595007878924aacChris Lattner bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 1170b83eb6447ba155342598f0fabe1f08f5baa9164aReid Spencer return LHS->getZExtValue() < RHS->getZExtValue(); 11711654cff8e80acdddf5e5f2261595007878924aacChris Lattner } 11721654cff8e80acdddf5e5f2261595007878924aacChris Lattner }; 11731654cff8e80acdddf5e5f2261595007878924aacChris Lattner} 11741654cff8e80acdddf5e5f2261595007878924aacChris Lattner 117501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// SimplifyCFG - This function is used to do simplification of a CFG. For 117601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// example, it adjusts branches to branches to eliminate the extra hop, it 117701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// eliminates unreachable basic blocks, and does other "peephole" optimization 1178e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// of the CFG. It returns true if a modification was made. 117901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 118001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// WARNING: The entry node of a function may not be simplified. 118101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 1182f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::SimplifyCFG(BasicBlock *BB) { 1183dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner bool Changed = false; 118401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner Function *M = BB->getParent(); 118501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 118601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB && BB->getParent() && "Block not embedded in function!"); 118701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB->getTerminator() && "Degenerate basic block encountered!"); 118818961504fc2b299578dba817900a0696cf3ccc4dChris Lattner assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 118901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 119001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove basic blocks that have no predecessors... which are unreachable. 1191d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (pred_begin(BB) == pred_end(BB) || 1192d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner *pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB)) { 11930d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "Removing BB: \n" << *BB; 119401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 119501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Loop through all of our successors and make sure they know that one 119601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // of their predecessors is going away. 1197151c80be8180a7a0aa1594848699aa6b678b3998Chris Lattner for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 1198151c80be8180a7a0aa1594848699aa6b678b3998Chris Lattner SI->removePredecessor(BB); 119901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 120001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner while (!BB->empty()) { 120118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Instruction &I = BB->back(); 120201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If this instruction is used, replace uses with an arbitrary 1203f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner // value. Because control flow can't get here, we don't care 1204fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // what we replace the value with. Note that since this block is 120501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // unreachable, and all values contained within it must dominate their 120601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // uses, that all uses will eventually be removed. 1207fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman if (!I.use_empty()) 1208f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner // Make all users of this instruction use undef instead 1209f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner I.replaceAllUsesWith(UndefValue::get(I.getType())); 1210fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 121101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove the instruction from the basic block 121218961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BB->getInstList().pop_back(); 121301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 121418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 121501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 121601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 121701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 1218694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // Check to see if we can constant propagate this terminator instruction 1219694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // away... 1220dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner Changed |= ConstantFoldTerminator(BB); 1221694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 122219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If this is a returning block with only PHI nodes in it, fold the return 122319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // instruction into any unconditional branch predecessors. 1224147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // 1225147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // If any predecessor is a conditional branch that just selects among 1226147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // different return values, fold the replace the branch/return with a select 1227147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // and return. 122819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 122919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BasicBlock::iterator BBI = BB->getTerminator(); 123019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BBI == BB->begin() || isa<PHINode>(--BBI)) { 1231147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Find predecessors that end with branches. 123219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner std::vector<BasicBlock*> UncondBranchPreds; 1233147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner std::vector<BranchInst*> CondBranchPreds; 123419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 123519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner TerminatorInst *PTI = (*PI)->getTerminator(); 123619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 123719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BI->isUnconditional()) 123819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner UncondBranchPreds.push_back(*PI); 1239147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner else 1240147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner CondBranchPreds.push_back(BI); 124119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 1242fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 124319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we found some, do the transformation! 124419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (!UncondBranchPreds.empty()) { 124519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner while (!UncondBranchPreds.empty()) { 124619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BasicBlock *Pred = UncondBranchPreds.back(); 12470d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "FOLDING: " << *BB 12480d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling << "INTO UNCOND BRANCH PRED: " << *Pred; 124919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner UncondBranchPreds.pop_back(); 125019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Instruction *UncondBranch = Pred->getTerminator(); 125119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Clone the return and add it to the end of the predecessor. 125219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Instruction *NewRet = RI->clone(); 125319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().push_back(NewRet); 125419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 125519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If the return instruction returns a value, and if the value was a 125619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // PHI node in "BB", propagate the right value into the return. 125719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (NewRet->getNumOperands() == 1) 125819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0))) 125919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (PN->getParent() == BB) 126019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred)); 126119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Update any PHI nodes in the returning block to realize that we no 126219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // longer branch to them. 126319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BB->removePredecessor(Pred); 126419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().erase(UncondBranch); 126519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 126619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 126719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we eliminated all predecessors of the block, delete the block now. 126819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (pred_begin(BB) == pred_end(BB)) 126919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // We know there are no successors, so just nuke the block. 127019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner M->getBasicBlockList().erase(BB); 127119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 127219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner return true; 127319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 1274147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1275147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check out all of the conditional branches going to this return 1276147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // instruction. If any of them just select between returns, change the 1277147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // branch itself into a select/return pair. 1278147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner while (!CondBranchPreds.empty()) { 1279147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BranchInst *BI = CondBranchPreds.back(); 1280147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner CondBranchPreds.pop_back(); 1281147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *TrueSucc = BI->getSuccessor(0); 1282147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *FalseSucc = BI->getSuccessor(1); 1283147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *OtherSucc = TrueSucc == BB ? FalseSucc : TrueSucc; 1284147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1285147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check to see if the non-BB successor is also a return block. 1286147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (isa<ReturnInst>(OtherSucc->getTerminator())) { 1287147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check to see if there are only PHI instructions in this block. 1288147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock::iterator OSI = OtherSucc->getTerminator(); 1289147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (OSI == OtherSucc->begin() || isa<PHINode>(--OSI)) { 1290147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Okay, we found a branch that is going to two return nodes. If 1291147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // there is no return value for this function, just change the 1292147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // branch into a return. 1293147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (RI->getNumOperands() == 0) { 1294147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner TrueSucc->removePredecessor(BI->getParent()); 1295147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner FalseSucc->removePredecessor(BI->getParent()); 1296147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner new ReturnInst(0, BI); 1297147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BI->getParent()->getInstList().erase(BI); 1298147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner return true; 1299147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1300147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1301147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Otherwise, figure out what the true and false return values are 1302147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // so we can insert a new select instruction. 1303147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner Value *TrueValue = TrueSucc->getTerminator()->getOperand(0); 1304147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner Value *FalseValue = FalseSucc->getTerminator()->getOperand(0); 1305147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1306147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Unwrap any PHI nodes in the return blocks. 1307147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue)) 1308147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (TVPN->getParent() == TrueSucc) 1309147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1310147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue)) 1311147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (FVPN->getParent() == FalseSucc) 1312147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1313147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1314b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner // In order for this transformation to be safe, we must be able to 1315b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner // unconditionally execute both operands to the return. This is 1316b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner // normally the case, but we could have a potentially-trapping 1317b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner // constant expression that prevents this transformation from being 1318b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner // safe. 1319b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner if ((!isa<ConstantExpr>(TrueValue) || 1320b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner !cast<ConstantExpr>(TrueValue)->canTrap()) && 1321b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner (!isa<ConstantExpr>(TrueValue) || 1322b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner !cast<ConstantExpr>(TrueValue)->canTrap())) { 1323b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner TrueSucc->removePredecessor(BI->getParent()); 1324b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner FalseSucc->removePredecessor(BI->getParent()); 1325b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner 1326b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner // Insert a new select instruction. 1327b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner Value *NewRetVal; 1328b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner Value *BrCond = BI->getCondition(); 1329b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner if (TrueValue != FalseValue) 1330b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner NewRetVal = new SelectInst(BrCond, TrueValue, 1331b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner FalseValue, "retval", BI); 1332b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner else 1333b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner NewRetVal = TrueValue; 1334b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner 13350d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" 13360d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling << "\n " << *BI << "Select = " << *NewRetVal 13370d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc; 1338b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner 1339b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner new ReturnInst(NewRetVal, BI); 1340b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner BI->eraseFromParent(); 1341b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner if (Instruction *BrCondI = dyn_cast<Instruction>(BrCond)) 1342b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner if (isInstructionTriviallyDead(BrCondI)) 1343b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner BrCondI->eraseFromParent(); 1344b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner return true; 1345b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner } 1346147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1347147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1348147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 134919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 13503ed469ccd7b028a030b550d84b7336d146f5d8faReid Spencer } else if (isa<UnwindInst>(BB->begin())) { 1351e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Check to see if the first instruction in this block is just an unwind. 1352e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // If so, replace any invoke instructions which use this as an exception 1353af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner // destination with call instructions, and any unconditional branch 1354af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner // predecessor with an unwind. 1355e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // 1356e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 1357e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner while (!Preds.empty()) { 1358e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner BasicBlock *Pred = Preds.back(); 1359af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) { 1360af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner if (BI->isUnconditional()) { 1361af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner Pred->getInstList().pop_back(); // nuke uncond branch 1362af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner new UnwindInst(Pred); // Use unwind. 1363af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner Changed = true; 1364af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner } 1365af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 1366e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner if (II->getUnwindDest() == BB) { 1367e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Insert a new branch instruction before the invoke, because this 1368e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // is now a fall through... 1369e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner BranchInst *BI = new BranchInst(II->getNormalDest(), II); 1370e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Pred->getInstList().remove(II); // Take out of symbol table 1371fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1372e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Insert the call now... 137393e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner SmallVector<Value*,8> Args(II->op_begin()+3, II->op_end()); 137493e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner CallInst *CI = new CallInst(II->getCalledValue(), 137593e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner &Args[0], Args.size(), II->getName(), BI); 137616d0db2da8c274f98db4a89ca7a92f970d464b9aChris Lattner CI->setCallingConv(II->getCallingConv()); 1377e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // If the invoke produced a value, the Call now does instead 1378e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner II->replaceAllUsesWith(CI); 1379e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner delete II; 1380e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Changed = true; 1381e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 1382fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1383e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Preds.pop_back(); 1384e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 13858e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 13868e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // If this block is now dead, remove it. 13878e509dd5e81e92a466580ab4022994079952cca9Chris Lattner if (pred_begin(BB) == pred_end(BB)) { 13888e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // We know there are no successors, so just nuke the block. 13898e509dd5e81e92a466580ab4022994079952cca9Chris Lattner M->getBasicBlockList().erase(BB); 13908e509dd5e81e92a466580ab4022994079952cca9Chris Lattner return true; 13918e509dd5e81e92a466580ab4022994079952cca9Chris Lattner } 13928e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 1393623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1394623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (isValueEqualityComparison(SI)) { 1395623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we only have one predecessor, and if it is a branch on this value, 1396623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // see if that predecessor totally determines the outcome of this switch. 1397623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1398623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) 1399623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1400623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 1401623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If the block only contains the switch, see if we can fold the block 1402623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // away into any preds. 1403623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SI == &BB->front()) 1404623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (FoldValueComparisonIntoPredecessors(SI)) 1405623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1406623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 1407542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 14087e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (BI->isUnconditional()) { 14097e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 14107e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner while (isa<PHINode>(*BBI)) ++BBI; 14117e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 14127e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BasicBlock *Succ = BI->getSuccessor(0); 14137e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (BBI->isTerminator() && // Terminator is the only non-phi instruction! 14147e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner Succ != BB) // Don't hurt infinite loops! 14157e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ)) 14167e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner return 1; 14177e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 14187e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } else { // Conditional branch 14193ed469ccd7b028a030b550d84b7336d146f5d8faReid Spencer if (isValueEqualityComparison(BI)) { 1420623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we only have one predecessor, and if it is a branch on this value, 1421623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // see if that predecessor totally determines the outcome of this 1422623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // switch. 1423623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1424623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) 1425623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1426623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 1427e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // This block must be empty, except for the setcond inst, if it exists. 1428e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock::iterator I = BB->begin(); 1429e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (&*I == BI || 1430e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner (&*I == cast<Instruction>(BI->getCondition()) && 1431e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner &*++I == BI)) 1432e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (FoldValueComparisonIntoPredecessors(BI)) 1433e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner return SimplifyCFG(BB) | true; 1434e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1435eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1436eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // If this is a branch on a phi node in the current block, thread control 1437eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // through this block if any PHI node entries are constants. 1438eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 1439eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PN->getParent() == BI->getParent()) 1440eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (FoldCondBranchOnPHI(BI)) 1441eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return SimplifyCFG(BB) | true; 1442e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 1443e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // If this basic block is ONLY a setcc and a branch, and if a predecessor 1444e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // branches to us and one of our successors, fold the setcc into the 1445e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // predecessor and use logical operations to pick the right destination. 144612fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner BasicBlock *TrueDest = BI->getSuccessor(0); 144712fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner BasicBlock *FalseDest = BI->getSuccessor(1); 1448e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if (Instruction *Cond = dyn_cast<Instruction>(BI->getCondition())) 1449e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if ((isa<CmpInst>(Cond) || isa<BinaryOperator>(Cond)) && 1450e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer Cond->getParent() == BB && &BB->front() == Cond && 145112fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner Cond->getNext() == BI && Cond->hasOneUse() && 145212fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner TrueDest != BB && FalseDest != BB) 1453e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI) 1454e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1455a1f79fb08b92801d4ab3cb32fe0bd9d12dfb3954Chris Lattner if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) { 14562636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner BasicBlock *PredBlock = *PI; 1457e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == FalseDest || 1458e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(1) == TrueDest) { 1459e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // Invert the predecessors condition test (xor it with true), 1460e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // which allows us to write this code once. 1461e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Value *NewCond = 1462e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BinaryOperator::createNot(PBI->getCondition(), 1463e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getCondition()->getName()+".not", PBI); 1464e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setCondition(NewCond); 1465e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock *OldTrue = PBI->getSuccessor(0); 1466e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock *OldFalse = PBI->getSuccessor(1); 1467e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(0, OldFalse); 1468e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(1, OldTrue); 1469e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1470e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 1471299520de7c5358a30dd7786cf9fe9f9a6ce37d94Chris Lattner if ((PBI->getSuccessor(0) == TrueDest && FalseDest != BB) || 1472299520de7c5358a30dd7786cf9fe9f9a6ce37d94Chris Lattner (PBI->getSuccessor(1) == FalseDest && TrueDest != BB)) { 14732636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner // Clone Cond into the predecessor basic block, and or/and the 1474e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // two conditions together. 1475e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction *New = Cond->clone(); 14762636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner PredBlock->getInstList().insert(PBI, New); 147786cc42355593dd1689f7d58d56695c451215b02bChris Lattner New->takeName(Cond); 147886cc42355593dd1689f7d58d56695c451215b02bChris Lattner Cond->setName(New->getName()+".old"); 1479e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction::BinaryOps Opcode = 1480e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(0) == TrueDest ? 1481e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction::Or : Instruction::And; 1482fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman Value *NewCond = 1483e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BinaryOperator::create(Opcode, PBI->getCondition(), 1484e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner New, "bothcond", PBI); 1485e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setCondition(NewCond); 1486e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == BB) { 14872636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner AddPredecessorToBlock(TrueDest, PredBlock, BB); 1488e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(0, TrueDest); 1489e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1490e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(1) == BB) { 14912636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner AddPredecessorToBlock(FalseDest, PredBlock, BB); 1492e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(1, FalseDest); 1493e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1494e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner return SimplifyCFG(BB) | 1; 1495e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1496e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1497e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 1498263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // Scan predessor blocks for conditional branchs. 14992e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 15002e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1501263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner if (PBI != BI && PBI->isConditional()) { 1502263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner 1503263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // If this block ends with a branch instruction, and if there is a 1504579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer // predecessor that ends on a branch of the same condition, make 1505579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer // this conditional branch redundant. 1506263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner if (PBI->getCondition() == BI->getCondition() && 1507263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 1508263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // Okay, the outcome of this conditional branch is statically 1509263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // knowable. If this block had a single pred, handle specially. 1510263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner if (BB->getSinglePredecessor()) { 1511263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // Turn this into a branch on constant. 1512263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner bool CondIsTrue = PBI->getSuccessor(0) == BB; 1513579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer BI->setCondition(ConstantInt::get(Type::Int1Ty, CondIsTrue)); 1514263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner return SimplifyCFG(BB); // Nuke the branch on constant. 1515263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } 1516263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner 1517579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer // Otherwise, if there are multiple predecessors, insert a PHI 1518579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer // that merges in the constant and simplify the block result. 1519263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner if (BlockIsSimpleEnoughToThreadThrough(BB)) { 15204fe16d607d11e29d742208894909733f5ad01f8fReid Spencer PHINode *NewPN = new PHINode(Type::Int1Ty, 1521579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer BI->getCondition()->getName()+".pr", 1522579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer BB->begin()); 1523263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner for (PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 1524263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner if ((PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) && 1525263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBI != BI && PBI->isConditional() && 1526263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBI->getCondition() == BI->getCondition() && 1527263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 1528263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner bool CondIsTrue = PBI->getSuccessor(0) == BB; 1529579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer NewPN->addIncoming(ConstantInt::get(Type::Int1Ty, 1530579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer CondIsTrue), *PI); 1531263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } else { 1532263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner NewPN->addIncoming(BI->getCondition(), *PI); 1533263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } 1534263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner 1535263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner BI->setCondition(NewPN); 1536263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // This will thread the branch. 1537263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner return SimplifyCFG(BB) | true; 1538263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } 15392e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner } 15402e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 1541263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // If this is a conditional branch in an empty block, and if any 1542263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // predecessors is a conditional branch to one of our destinations, 1543263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // fold the conditions into logical ops and one cond br. 1544263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner if (&BB->front() == BI) { 1545263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner int PBIOp, BIOp; 1546263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner if (PBI->getSuccessor(0) == BI->getSuccessor(0)) { 1547263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBIOp = BIOp = 0; 1548263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) { 1549263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBIOp = 0; BIOp = 1; 1550263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) { 1551263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBIOp = 1; BIOp = 0; 1552263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) { 1553263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBIOp = BIOp = 1; 1554263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } else { 1555263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBIOp = BIOp = -1; 1556263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } 15572e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 1558299520de7c5358a30dd7786cf9fe9f9a6ce37d94Chris Lattner // Check to make sure that the other destination of this branch 1559299520de7c5358a30dd7786cf9fe9f9a6ce37d94Chris Lattner // isn't BB itself. If so, this is an infinite loop that will 1560299520de7c5358a30dd7786cf9fe9f9a6ce37d94Chris Lattner // keep getting unwound. 1561299520de7c5358a30dd7786cf9fe9f9a6ce37d94Chris Lattner if (PBIOp != -1 && PBI->getSuccessor(PBIOp) == BB) 1562299520de7c5358a30dd7786cf9fe9f9a6ce37d94Chris Lattner PBIOp = BIOp = -1; 1563822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner 1564822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // Do not perform this transformation if it would require 1565822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // insertion of a large number of select instructions. For targets 1566822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // without predication/cmovs, this is a big pessimization. 1567822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner if (PBIOp != -1) { 1568822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 1569822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner 1570822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner unsigned NumPhis = 0; 1571822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner for (BasicBlock::iterator II = CommonDest->begin(); 1572822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner isa<PHINode>(II); ++II, ++NumPhis) { 1573822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner if (NumPhis > 2) { 1574822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // Disable this xform. 1575822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner PBIOp = -1; 1576822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner break; 1577822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner } 1578822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner } 1579822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner } 15807f2e1dd5d42a4411e5d4c89297952325239b4c2aChris Lattner 1581263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // Finally, if everything is ok, fold the branches to logical ops. 1582263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner if (PBIOp != -1) { 1583263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 1584263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); 1585263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner 15867f2e1dd5d42a4411e5d4c89297952325239b4c2aChris Lattner // If OtherDest *is* BB, then this is a basic block with just 15877f2e1dd5d42a4411e5d4c89297952325239b4c2aChris Lattner // a conditional branch in it, where one edge (OtherDesg) goes 15887f2e1dd5d42a4411e5d4c89297952325239b4c2aChris Lattner // back to the block. We know that the program doesn't get 15897f2e1dd5d42a4411e5d4c89297952325239b4c2aChris Lattner // stuck in the infinite loop, so the condition must be such 15907f2e1dd5d42a4411e5d4c89297952325239b4c2aChris Lattner // that OtherDest isn't branched through. Forward to CommonDest, 15917f2e1dd5d42a4411e5d4c89297952325239b4c2aChris Lattner // and avoid an infinite loop at optimizer time. 15927f2e1dd5d42a4411e5d4c89297952325239b4c2aChris Lattner if (OtherDest == BB) 15937f2e1dd5d42a4411e5d4c89297952325239b4c2aChris Lattner OtherDest = CommonDest; 15947f2e1dd5d42a4411e5d4c89297952325239b4c2aChris Lattner 15950d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "FOLDING BRs:" << *PBI->getParent() 15960d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling << "AND: " << *BI->getParent(); 1597263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner 1598263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // BI may have other predecessors. Because of this, we leave 1599263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // it alone, but modify PBI. 1600263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner 1601263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // Make sure we get to CommonDest on True&True directions. 1602263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner Value *PBICond = PBI->getCondition(); 1603263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner if (PBIOp) 1604263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBICond = BinaryOperator::createNot(PBICond, 1605263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBICond->getName()+".not", 1606263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBI); 1607263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner Value *BICond = BI->getCondition(); 1608263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner if (BIOp) 1609263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner BICond = BinaryOperator::createNot(BICond, 1610263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner BICond->getName()+".not", 1611263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBI); 1612263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // Merge the conditions. 1613263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner Value *Cond = 1614263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner BinaryOperator::createOr(PBICond, BICond, "brmerge", PBI); 1615263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner 1616263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // Modify PBI to branch on the new condition to the new dests. 1617263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBI->setCondition(Cond); 1618263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBI->setSuccessor(0, CommonDest); 1619263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBI->setSuccessor(1, OtherDest); 1620263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner 1621263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // OtherDest may have phi nodes. If so, add an entry from PBI's 1622263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // block that are identical to the entries for BI's block. 1623263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PHINode *PN; 1624263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner for (BasicBlock::iterator II = OtherDest->begin(); 1625263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner (PN = dyn_cast<PHINode>(II)); ++II) { 1626263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner Value *V = PN->getIncomingValueForBlock(BB); 1627263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PN->addIncoming(V, PBI->getParent()); 1628263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } 1629263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner 1630263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // We know that the CommonDest already had an edge from PBI to 1631263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // it. If it has PHIs though, the PHIs may have different 1632263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // entries for BB and PBI's BB. If so, insert a select to make 1633263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // them agree. 1634263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner for (BasicBlock::iterator II = CommonDest->begin(); 1635263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner (PN = dyn_cast<PHINode>(II)); ++II) { 1636263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner Value * BIV = PN->getIncomingValueForBlock(BB); 1637263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); 1638263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner Value *PBIV = PN->getIncomingValue(PBBIdx); 1639263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner if (BIV != PBIV) { 1640263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // Insert a select in PBI to pick the right value. 1641263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner Value *NV = new SelectInst(PBICond, PBIV, BIV, 1642263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PBIV->getName()+".mux", PBI); 1643263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner PN->setIncomingValue(PBBIdx, NV); 1644263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } 1645263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } 1646263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner 16470d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "INTO: " << *PBI->getParent(); 1648263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner 1649263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // This basic block is probably dead. We know it has at least 1650263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner // one fewer predecessor. 1651263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner return SimplifyCFG(BB) | true; 1652263d1e469d849fb9e2087ea9fbd42b4bfcc98c24Chris Lattner } 16532e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner } 165492da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner } 1655d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner } 1656698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (isa<UnreachableInst>(BB->getTerminator())) { 1657698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If there are any instructions immediately before the unreachable that can 1658698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // be removed, do so. 1659698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Instruction *Unreachable = BB->getTerminator(); 1660698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner while (Unreachable != BB->begin()) { 1661698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock::iterator BBI = Unreachable; 1662698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --BBI; 1663698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (isa<CallInst>(BBI)) break; 1664698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Delete this instruction 1665698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BB->getInstList().erase(BBI); 1666698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1667698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1668698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1669698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the unreachable instruction is the first in the block, take a gander 1670698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // at all of the predecessors of this instruction, and simplify them. 1671698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (&BB->front() == Unreachable) { 1672698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 1673698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 1674698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TerminatorInst *TI = Preds[i]->getTerminator(); 1675698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1676698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1677698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->isUnconditional()) { 1678698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 1679698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new UnreachableInst(TI); 1680698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TI->eraseFromParent(); 1681698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1682698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1683698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else { 1684698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 1685698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new BranchInst(BI->getSuccessor(1), BI); 1686698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BI->eraseFromParent(); 1687698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (BI->getSuccessor(1) == BB) { 1688698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new BranchInst(BI->getSuccessor(0), BI); 1689698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BI->eraseFromParent(); 1690698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1691698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1692698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1693698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1694698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1695698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == BB) { 169642eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner BB->removePredecessor(SI->getParent()); 1697698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1698698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1699698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1700698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1701698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the default value is unreachable, figure out the most popular 1702698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // destination and make it the default. 1703698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(0) == BB) { 1704698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::map<BasicBlock*, unsigned> Popularity; 1705698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1706698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Popularity[SI->getSuccessor(i)]++; 1707698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1708698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Find the most popular block. 1709698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner unsigned MaxPop = 0; 1710698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock *MaxBlock = 0; 1711698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (std::map<BasicBlock*, unsigned>::iterator 1712698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 1713698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (I->second > MaxPop) { 1714698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxPop = I->second; 1715698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxBlock = I->first; 1716698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1717698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1718698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (MaxBlock) { 1719698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Make this the new default, allowing us to delete any explicit 1720698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // edges to it. 1721698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->setSuccessor(0, MaxBlock); 1722698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1723698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 172442eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 172542eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner // it. 172642eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner if (isa<PHINode>(MaxBlock->begin())) 172742eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner for (unsigned i = 0; i != MaxPop-1; ++i) 172842eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner MaxBlock->removePredecessor(SI->getParent()); 172942eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner 1730698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1731698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == MaxBlock) { 1732698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1733698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1734698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1735698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1736698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1737698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 1738698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (II->getUnwindDest() == BB) { 1739698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Convert the invoke to a call instruction. This would be a good 1740698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // place to note that the call does not throw though. 1741698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BranchInst *BI = new BranchInst(II->getNormalDest(), II); 1742698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->removeFromParent(); // Take out of symbol table 1743fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1744698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Insert the call now... 174593e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); 174693e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner CallInst *CI = new CallInst(II->getCalledValue(), 174793e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner &Args[0], Args.size(), 1748698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->getName(), BI); 174916d0db2da8c274f98db4a89ca7a92f970d464b9aChris Lattner CI->setCallingConv(II->getCallingConv()); 1750698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the invoke produced a value, the Call does now instead. 1751698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->replaceAllUsesWith(CI); 1752698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner delete II; 1753698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1754698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1755698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1756698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1757698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1758698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If this block is now dead, remove it. 1759698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (pred_begin(BB) == pred_end(BB)) { 1760698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // We know there are no successors, so just nuke the block. 1761698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner M->getBasicBlockList().erase(BB); 1762698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner return true; 1763698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1764698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 176519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 176619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 176701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Merge basic blocks into their predecessor if there is only one distinct 176801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // pred, and if there is only one distinct successor of the predecessor, and 176901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // if there are no PHI nodes. 177001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 17712355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 17722355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BasicBlock *OnlyPred = *PI++; 17732355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 17742355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (*PI != OnlyPred) { 17752355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred = 0; // There are multiple different predecessors... 17762355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner break; 17772355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 177892da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner 17792355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BasicBlock *OnlySucc = 0; 17802355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (OnlyPred && OnlyPred != BB && // Don't break self loops 17812355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 17822355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Check to see if there is only one distinct successor... 17832355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 17842355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlySucc = BB; 17852355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner for (; SI != SE; ++SI) 17862355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (*SI != OnlySucc) { 17872355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlySucc = 0; // There are multiple distinct successors! 178801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner break; 178901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 17902355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 179101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 17922355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (OnlySucc) { 17930d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling DOUT << "Merging: " << *BB << "into: " << *OnlyPred; 179401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 17952355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Resolve any PHI nodes at the start of the block. They are all 17962355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // guaranteed to have exactly one entry if they exist, unless there are 17972355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // multiple duplicate (but guaranteed to be equal) entries for the 17982355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // incoming edges. This occurs when there are multiple edges from 17992355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // OnlyPred to OnlySucc. 18002355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // 18012355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 18022355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 180386cc42355593dd1689f7d58d56695c451215b02bChris Lattner BB->getInstList().pop_front(); // Delete the phi node. 18042355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 180591b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner 180686cc42355593dd1689f7d58d56695c451215b02bChris Lattner // Delete the unconditional branch from the predecessor. 18072355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getInstList().pop_back(); 1808fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 180986cc42355593dd1689f7d58d56695c451215b02bChris Lattner // Move all definitions in the successor to the predecessor. 18102355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 1811fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 18122355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Make all PHI nodes that referred to BB now refer to Pred as their 181386cc42355593dd1689f7d58d56695c451215b02bChris Lattner // source. 18142355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BB->replaceAllUsesWith(OnlyPred); 181518961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 181686cc42355593dd1689f7d58d56695c451215b02bChris Lattner // Inherit predecessors name if it exists. 181786cc42355593dd1689f7d58d56695c451215b02bChris Lattner if (!OnlyPred->hasName()) 181886cc42355593dd1689f7d58d56695c451215b02bChris Lattner OnlyPred->takeName(BB); 181986cc42355593dd1689f7d58d56695c451215b02bChris Lattner 182086cc42355593dd1689f7d58d56695c451215b02bChris Lattner // Erase basic block from the function. 18212355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner M->getBasicBlockList().erase(BB); 182218961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 18232355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner return true; 182401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 1825723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 182637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Otherwise, if this block only has a single predecessor, and if that block 182737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // is a conditional branch, see if we can hoist any code from this block up 182837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // into our predecessor. 182937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (OnlyPred) 18307613437db954abafd1230c961e87872df5721957Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 18317613437db954abafd1230c961e87872df5721957Chris Lattner if (BI->isConditional()) { 18327613437db954abafd1230c961e87872df5721957Chris Lattner // Get the other block. 18337613437db954abafd1230c961e87872df5721957Chris Lattner BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); 18347613437db954abafd1230c961e87872df5721957Chris Lattner PI = pred_begin(OtherBB); 18357613437db954abafd1230c961e87872df5721957Chris Lattner ++PI; 18367613437db954abafd1230c961e87872df5721957Chris Lattner if (PI == pred_end(OtherBB)) { 18377613437db954abafd1230c961e87872df5721957Chris Lattner // We have a conditional branch to two blocks that are only reachable 18387613437db954abafd1230c961e87872df5721957Chris Lattner // from the condbr. We know that the condbr dominates the two blocks, 18397613437db954abafd1230c961e87872df5721957Chris Lattner // so see if there is any identical code in the "then" and "else" 18407613437db954abafd1230c961e87872df5721957Chris Lattner // blocks. If so, we can hoist it up to the branching block. 18417613437db954abafd1230c961e87872df5721957Chris Lattner Changed |= HoistThenElseCodeToIf(BI); 18427613437db954abafd1230c961e87872df5721957Chris Lattner } 184337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 184437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 18450d56008f53587531718ec36af82cc24576580b36Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 18460d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 18470d56008f53587531718ec36af82cc24576580b36Chris Lattner // Change br (X == 0 | X == 1), T, F into a switch instruction. 18480d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 18490d56008f53587531718ec36af82cc24576580b36Chris Lattner Instruction *Cond = cast<Instruction>(BI->getCondition()); 18500d56008f53587531718ec36af82cc24576580b36Chris Lattner // If this is a bunch of seteq's or'd together, or if it's a bunch of 18510d56008f53587531718ec36af82cc24576580b36Chris Lattner // 'setne's and'ed together, collect them. 18520d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *CompVal = 0; 18531654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::vector<ConstantInt*> Values; 18540d56008f53587531718ec36af82cc24576580b36Chris Lattner bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 185542a75517250017a52afb03a0ade03cbd49559fe5Chris Lattner if (CompVal && CompVal->getType()->isInteger()) { 18560d56008f53587531718ec36af82cc24576580b36Chris Lattner // There might be duplicate constants in the list, which the switch 18570d56008f53587531718ec36af82cc24576580b36Chris Lattner // instruction can't handle, remove them now. 18581654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 18590d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 1860fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 18610d56008f53587531718ec36af82cc24576580b36Chris Lattner // Figure out which block is which destination. 18620d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *DefaultBB = BI->getSuccessor(1); 18630d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *EdgeBB = BI->getSuccessor(0); 18640d56008f53587531718ec36af82cc24576580b36Chris Lattner if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 1865fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 18660d56008f53587531718ec36af82cc24576580b36Chris Lattner // Create the new switch instruction now. 1867378805969ea928b91aa321746031a8f51667a783Chris Lattner SwitchInst *New = new SwitchInst(CompVal, DefaultBB,Values.size(),BI); 1868fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 18690d56008f53587531718ec36af82cc24576580b36Chris Lattner // Add all of the 'cases' to the switch instruction. 18700d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size(); i != e; ++i) 18710d56008f53587531718ec36af82cc24576580b36Chris Lattner New->addCase(Values[i], EdgeBB); 1872fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 18730d56008f53587531718ec36af82cc24576580b36Chris Lattner // We added edges from PI to the EdgeBB. As such, if there were any 18740d56008f53587531718ec36af82cc24576580b36Chris Lattner // PHI nodes in EdgeBB, they need entries to be added corresponding to 18750d56008f53587531718ec36af82cc24576580b36Chris Lattner // the number of edges added. 18760d56008f53587531718ec36af82cc24576580b36Chris Lattner for (BasicBlock::iterator BBI = EdgeBB->begin(); 18772da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer isa<PHINode>(BBI); ++BBI) { 18782da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(BBI); 18790d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *InVal = PN->getIncomingValueForBlock(*PI); 18800d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 18810d56008f53587531718ec36af82cc24576580b36Chris Lattner PN->addIncoming(InVal, *PI); 18820d56008f53587531718ec36af82cc24576580b36Chris Lattner } 18830d56008f53587531718ec36af82cc24576580b36Chris Lattner 18840d56008f53587531718ec36af82cc24576580b36Chris Lattner // Erase the old branch instruction. 18850d56008f53587531718ec36af82cc24576580b36Chris Lattner (*PI)->getInstList().erase(BI); 18860d56008f53587531718ec36af82cc24576580b36Chris Lattner 18870d56008f53587531718ec36af82cc24576580b36Chris Lattner // Erase the potentially condition tree that was used to computed the 18880d56008f53587531718ec36af82cc24576580b36Chris Lattner // branch condition. 18890d56008f53587531718ec36af82cc24576580b36Chris Lattner ErasePossiblyDeadInstructionTree(Cond); 18900d56008f53587531718ec36af82cc24576580b36Chris Lattner return true; 18910d56008f53587531718ec36af82cc24576580b36Chris Lattner } 18920d56008f53587531718ec36af82cc24576580b36Chris Lattner } 18930d56008f53587531718ec36af82cc24576580b36Chris Lattner 1894723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If there is a trivial two-entry PHI node in this basic block, and we can 1895723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // eliminate it, do so now. 1896723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 1897f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (PN->getNumIncomingValues() == 2) 1898f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Changed |= FoldTwoEntryPHINode(PN); 1899fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1900694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner return Changed; 190101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 1902