SimplifyCFG.cpp revision 055dc102e97316d423bd068f8b228d27fb93c90a
101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 10bb190ac8dafdcc5e604da3695987d69ee8632195Chris Lattner// Peephole optimize the CFG. 1101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 1201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner//===----------------------------------------------------------------------===// 1301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 14218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner#define DEBUG_TYPE "simplifycfg" 1501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Transforms/Utils/Local.h" 16723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner#include "llvm/Constants.h" 17723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner#include "llvm/Instructions.h" 180d56008f53587531718ec36af82cc24576580b36Chris Lattner#include "llvm/Type.h" 1901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Support/CFG.h" 20551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 21eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 2201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <algorithm> 2301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <functional> 24d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner#include <set> 25698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner#include <map> 26f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 27d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 282bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// SafeToMergeTerminators - Return true if it is safe to merge these two 292bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// terminator instructions together. 302bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// 312bdcb56146279009f233933a101cb3dd54a951cdChris Lattnerstatic bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 322bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (SI1 == SI2) return false; // Can't merge with self! 332bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 342bdcb56146279009f233933a101cb3dd54a951cdChris Lattner // It is not safe to merge these two switch instructions if they have a common 352bdcb56146279009f233933a101cb3dd54a951cdChris Lattner // successor, and if that successor has a PHI node, and if *that* PHI node has 362bdcb56146279009f233933a101cb3dd54a951cdChris Lattner // conflicting incoming values from the two switch blocks. 372bdcb56146279009f233933a101cb3dd54a951cdChris Lattner BasicBlock *SI1BB = SI1->getParent(); 382bdcb56146279009f233933a101cb3dd54a951cdChris Lattner BasicBlock *SI2BB = SI2->getParent(); 392bdcb56146279009f233933a101cb3dd54a951cdChris Lattner std::set<BasicBlock*> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 402bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 412bdcb56146279009f233933a101cb3dd54a951cdChris Lattner for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 422bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (SI1Succs.count(*I)) 432bdcb56146279009f233933a101cb3dd54a951cdChris Lattner for (BasicBlock::iterator BBI = (*I)->begin(); 442bdcb56146279009f233933a101cb3dd54a951cdChris Lattner isa<PHINode>(BBI); ++BBI) { 452bdcb56146279009f233933a101cb3dd54a951cdChris Lattner PHINode *PN = cast<PHINode>(BBI); 462bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (PN->getIncomingValueForBlock(SI1BB) != 472bdcb56146279009f233933a101cb3dd54a951cdChris Lattner PN->getIncomingValueForBlock(SI2BB)) 482bdcb56146279009f233933a101cb3dd54a951cdChris Lattner return false; 492bdcb56146279009f233933a101cb3dd54a951cdChris Lattner } 502bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 512bdcb56146279009f233933a101cb3dd54a951cdChris Lattner return true; 522bdcb56146279009f233933a101cb3dd54a951cdChris Lattner} 532bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 542bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 552bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// now be entries in it from the 'NewPred' block. The values that will be 562bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// flowing into the PHI nodes will be the same as those coming in from 572bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// ExistPred, an existing predecessor of Succ. 582bdcb56146279009f233933a101cb3dd54a951cdChris Lattnerstatic void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 592bdcb56146279009f233933a101cb3dd54a951cdChris Lattner BasicBlock *ExistPred) { 602bdcb56146279009f233933a101cb3dd54a951cdChris Lattner assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 612bdcb56146279009f233933a101cb3dd54a951cdChris Lattner succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 622bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 632bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 642bdcb56146279009f233933a101cb3dd54a951cdChris Lattner for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 652bdcb56146279009f233933a101cb3dd54a951cdChris Lattner PHINode *PN = cast<PHINode>(I); 662bdcb56146279009f233933a101cb3dd54a951cdChris Lattner Value *V = PN->getIncomingValueForBlock(ExistPred); 672bdcb56146279009f233933a101cb3dd54a951cdChris Lattner PN->addIncoming(V, NewPred); 682bdcb56146279009f233933a101cb3dd54a951cdChris Lattner } 692bdcb56146279009f233933a101cb3dd54a951cdChris Lattner} 702bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 713b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an 723b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner// almost-empty BB ending in an unconditional branch to Succ, into succ. 7301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 7401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// Assumption: Succ is the single successor for BB. 7501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 763b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattnerstatic bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) { 7701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!"); 783abb95df01ff2ea5a6a35a1b47351072d4cb4c73Chris Lattner 7901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Check to see if one of the predecessors of BB is already a predecessor of 80e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // Succ. If so, we cannot do the transformation if there are any PHI nodes 81e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner // with incompatible values coming in from the two edges! 8201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 83dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner if (isa<PHINode>(Succ->front())) { 84dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner std::set<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 85dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner for (pred_iterator PI = pred_begin(Succ), PE = pred_end(Succ);\ 86dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner PI != PE; ++PI) 87dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner if (std::find(BBPreds.begin(), BBPreds.end(), *PI) != BBPreds.end()) { 88dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // Loop over all of the PHI nodes checking to see if there are 89dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // incompatible values coming in. 90dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 91dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner PHINode *PN = cast<PHINode>(I); 92dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // Loop up the entries in the PHI node for BB and for *PI if the 93dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // values coming in are non-equal, we cannot merge these two blocks 94dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // (instead we should insert a conditional move or something, then 95dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // merge the blocks). 96dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner if (PN->getIncomingValueForBlock(BB) != 97dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner PN->getIncomingValueForBlock(*PI)) 98dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner return false; // Values are not equal... 99dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner } 100dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner } 101dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner } 1021aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner 1031aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner // Finally, if BB has PHI nodes that are used by things other than the PHIs in 1041aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner // Succ and Succ has predecessors that are not Succ and not Pred, we cannot 1051aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner // fold these blocks, as we don't know whether BB dominates Succ or not to 1061aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner // update the PHI nodes correctly. 1071aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner if (!isa<PHINode>(BB->begin()) || Succ->getSinglePredecessor()) return true; 10801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 1091aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner // If the predecessors of Succ are only BB and Succ itself, we can handle this. 1101aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner bool IsSafe = true; 1111aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner for (pred_iterator PI = pred_begin(Succ), E = pred_end(Succ); PI != E; ++PI) 1121aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner if (*PI != Succ && *PI != BB) { 1131aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner IsSafe = false; 1141aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner break; 1151aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner } 1161aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner if (IsSafe) return true; 1171aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner 1181aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner // If the PHI nodes in BB are only used by instructions in Succ, we are ok. 1191aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner IsSafe = true; 1201aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I) && IsSafe; ++I) { 1211aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner PHINode *PN = cast<PHINode>(I); 1221aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E; 1231aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner ++UI) 1241aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner if (cast<Instruction>(*UI)->getParent() != Succ) { 1251aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner IsSafe = false; 1261aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner break; 1271aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner } 1281aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner } 1291aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner 1301aad921c18edbc17fdc7167b6081ba49c4ea39f9Chris Lattner return IsSafe; 13101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 13201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 1337e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner/// TryToSimplifyUncondBranchFromEmptyBlock - BB contains an unconditional 1347e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner/// branch to Succ, and contains no instructions other than PHI nodes and the 1357e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner/// branch. If possible, eliminate BB. 1367e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattnerstatic bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB, 1377e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BasicBlock *Succ) { 1387e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // If our successor has PHI nodes, then we need to update them to include 1397e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // entries for BB's predecessors, not for BB itself. Be careful though, 1407e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // if this transformation fails (returns true) then we cannot do this 1417e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // transformation! 1427e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // 1433b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; 1447e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1457e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner DEBUG(std::cerr << "Killing Trivial BB: \n" << *BB); 1467e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1473b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner if (isa<PHINode>(Succ->begin())) { 1483b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner // If there is more than one pred of succ, and there are PHI nodes in 1493b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner // the successor, then we need to add incoming edges for the PHI nodes 1503b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner // 1513b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner const std::vector<BasicBlock*> BBPreds(pred_begin(BB), pred_end(BB)); 1523b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner 1533b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner // Loop over all of the PHI nodes in the successor of BB. 1543b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) { 1553b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner PHINode *PN = cast<PHINode>(I); 1563b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner Value *OldVal = PN->removeIncomingValue(BB, false); 1573b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner assert(OldVal && "No entry in PHI for Pred BB!"); 1583b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner 159dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // If this incoming value is one of the PHI nodes in BB, the new entries 160dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // in the PHI node are the entries from the old PHI. 1613b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) { 1623b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner PHINode *OldValPN = cast<PHINode>(OldVal); 1633b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) 1643b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner PN->addIncoming(OldValPN->getIncomingValue(i), 1653b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner OldValPN->getIncomingBlock(i)); 1663b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner } else { 1673b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner for (std::vector<BasicBlock*>::const_iterator PredI = BBPreds.begin(), 1683b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner End = BBPreds.end(); PredI != End; ++PredI) { 1693b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner // Add an incoming value for each of the new incoming values... 1703b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner PN->addIncoming(OldVal, *PredI); 1713b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner } 1723b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner } 1733b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner } 1743b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner } 1753b3efc77972e654c472cee8a3075e74a7d5f0cc8Chris Lattner 1767e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (isa<PHINode>(&BB->front())) { 1777e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner std::vector<BasicBlock*> 1787e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner OldSuccPreds(pred_begin(Succ), pred_end(Succ)); 1797e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1807e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // Move all PHI nodes in BB to Succ if they are alive, otherwise 1817e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // delete them. 1827e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) 183dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner if (PN->use_empty()) { 184dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // Just remove the dead phi. This happens if Succ's PHIs were the only 185dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner // users of the PHI nodes. 186dc88dbeafade56d8866f93ceb7438ea220ae2a9cChris Lattner PN->eraseFromParent(); 1877e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } else { 1887e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // The instruction is alive, so this means that Succ must have 1897e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // *ONLY* had BB as a predecessor, and the PHI node is still valid 1907e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // now. Simply move it into Succ, because we know that BB 1917e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // strictly dominated Succ. 192d423b8b6ca3d2d21a8aa07a877d63e5dc45abc70Chris Lattner Succ->getInstList().splice(Succ->begin(), 193d423b8b6ca3d2d21a8aa07a877d63e5dc45abc70Chris Lattner BB->getInstList(), BB->begin()); 1947e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1957e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // We need to add new entries for the PHI node to account for 1967e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // predecessors of Succ that the PHI node does not take into 1977e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // account. At this point, since we know that BB dominated succ, 1987e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // this means that we should any newly added incoming edges should 1997e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // use the PHI node as the value for these edges, because they are 2007e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // loop back edges. 2017e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner for (unsigned i = 0, e = OldSuccPreds.size(); i != e; ++i) 2027e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (OldSuccPreds[i] != BB) 2037e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner PN->addIncoming(PN, OldSuccPreds[i]); 2047e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } 2057e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } 2067e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 2077e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner // Everything that jumped to BB now goes to Succ. 2087e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner std::string OldName = BB->getName(); 2097e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BB->replaceAllUsesWith(Succ); 2107e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BB->eraseFromParent(); // Delete the old basic block. 2117e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 2127e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (!OldName.empty() && !Succ->hasName()) // Transfer name if we can 2137e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner Succ->setName(OldName); 2147e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner return true; 2157e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner} 2167e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 217723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// GetIfCondition - Given a basic block (BB) with two predecessors (and 218723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// presumably PHI nodes in it), check to see if the merge at this block is due 219723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// to an "if condition". If so, return the boolean condition that determines 220723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// which entry into BB will be taken. Also, return by references the block 221723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// that will be entered from if the condition is true, and the block that will 222723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// be entered if the condition is false. 223fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// 224723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// 225723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattnerstatic Value *GetIfCondition(BasicBlock *BB, 226723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 227723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 228723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner "Function can only handle blocks with 2 predecessors!"); 229723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *Pred1 = *pred_begin(BB); 230723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *Pred2 = *++pred_begin(BB); 231723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 232723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // We can only handle branches. Other control flow will be lowered to 233723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // branches if possible anyway. 234723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (!isa<BranchInst>(Pred1->getTerminator()) || 235723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner !isa<BranchInst>(Pred2->getTerminator())) 236723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 237723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 238723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 239723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 240723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Eliminate code duplication by ensuring that Pred1Br is conditional if 241723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // either are. 242723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred2Br->isConditional()) { 243723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If both branches are conditional, we don't have an "if statement". In 244723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // reality, we could transform this case, but since the condition will be 245723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // required anyway, we stand no chance of eliminating it, so the xform is 246723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // probably not profitable. 247723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->isConditional()) 248723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 249723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 250723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner std::swap(Pred1, Pred2); 251723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner std::swap(Pred1Br, Pred2Br); 252723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 253723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 254723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->isConditional()) { 255723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If we found a conditional branch predecessor, make sure that it branches 256723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 257723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->getSuccessor(0) == BB && 258723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Pred1Br->getSuccessor(1) == Pred2) { 259723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred1; 260723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred2; 261723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else if (Pred1Br->getSuccessor(0) == Pred2 && 262723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Pred1Br->getSuccessor(1) == BB) { 263723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred2; 264723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred1; 265723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else { 266723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // We know that one arm of the conditional goes to BB, so the other must 267723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // go somewhere unrelated, and this must not be an "if statement". 268723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 269723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 270723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 271723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // The only thing we have to watch out for here is to make sure that Pred2 272723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // doesn't have incoming edges from other blocks. If it does, the condition 273723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // doesn't dominate BB. 274723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (++pred_begin(Pred2) != pred_end(Pred2)) 275723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 276723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 277723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return Pred1Br->getCondition(); 278723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 279723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 280723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Ok, if we got here, both predecessors end with an unconditional branch to 281723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // BB. Don't panic! If both blocks only have a single (identical) 282723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // predecessor, and THAT is a conditional branch, then we're all ok! 283723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (pred_begin(Pred1) == pred_end(Pred1) || 284723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner ++pred_begin(Pred1) != pred_end(Pred1) || 285723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner pred_begin(Pred2) == pred_end(Pred2) || 286723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner ++pred_begin(Pred2) != pred_end(Pred2) || 287723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner *pred_begin(Pred1) != *pred_begin(Pred2)) 288723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 289723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 290723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Otherwise, if this is a conditional branch, then we can use it! 291723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *CommonPred = *pred_begin(Pred1); 292723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 293723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner assert(BI->isConditional() && "Two successors but not conditional?"); 294723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (BI->getSuccessor(0) == Pred1) { 295723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred1; 296723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred2; 297723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else { 298723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred2; 299723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred1; 300723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 301723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return BI->getCondition(); 302723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 303723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 304723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner} 305723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 306723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 307723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// If we have a merge point of an "if condition" as accepted above, return true 308723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// if the specified value dominates the block. We don't handle the true 309723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// generality of domination here, just a special case which works well enough 310723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner// for us. 3119c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// 3129c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 3139c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// see if V (which must be an instruction) is cheap to compute and is 3149c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// non-trapping. If both are true, the instruction is inserted into the set and 3159c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner// true is returned. 3169c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattnerstatic bool DominatesMergePoint(Value *V, BasicBlock *BB, 3179c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner std::set<Instruction*> *AggressiveInsts) { 318570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 319570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (!I) return true; // Non-instructions all dominate instructions. 320570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner BasicBlock *PBB = I->getParent(); 321570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 322da895d63377b421dc50117befb2bec80d2973526Chris Lattner // We don't want to allow weird loops that might have the "if condition" in 323570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // the bottom of this block. 324570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (PBB == BB) return false; 325570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 326570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // If this instruction is defined in a block that contains an unconditional 327570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // branch to BB, then it must be in the 'conditional' part of the "if 328570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // statement". 329570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator())) 330570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { 3319c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!AggressiveInsts) return false; 332570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Okay, it looks like the instruction IS in the "condition". Check to 333570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // see if its a cheap instruction to unconditionally compute, and if it 334570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // only uses stuff defined outside of the condition. If so, hoist it out. 335570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner switch (I->getOpcode()) { 336570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner default: return false; // Cannot hoist this out safely. 337570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Load: 338570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // We can hoist loads that are non-volatile and obviously cannot trap. 339570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (cast<LoadInst>(I)->isVolatile()) 340570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 341570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (!isa<AllocaInst>(I->getOperand(0)) && 342460f16c6253928519689e882a4dbb7f236f33294Reid Spencer !isa<Constant>(I->getOperand(0))) 343570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 344570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 345570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Finally, we have to check to make sure there are no instructions 346570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // before the load in its basic block, as we are going to hoist the loop 347570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // out to its predecessor. 348570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (PBB->begin() != BasicBlock::iterator(I)) 349570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 350570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner break; 351570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Add: 352570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Sub: 353570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::And: 354570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Or: 355570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Xor: 356570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Shl: 357570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Shr: 358bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetEQ: 359bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetNE: 360bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetLT: 361bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetGT: 362bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetLE: 363bf5d4fb7d8ee4537955610ef9c48f7009418efc3Chris Lattner case Instruction::SetGE: 364570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner break; // These are all cheap and non-trapping instructions. 365570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner } 366fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 367570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Okay, we can only really hoist these out if their operands are not 368570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // defined in the conditional region. 369570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 3709c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!DominatesMergePoint(I->getOperand(i), BB, 0)) 371570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 3729c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Okay, it's safe to do this! Remember this instruction. 3739c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner AggressiveInsts->insert(I); 374570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner } 375723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 376723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return true; 377723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner} 37801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 3790d56008f53587531718ec36af82cc24576580b36Chris Lattner// GatherConstantSetEQs - Given a potentially 'or'd together collection of seteq 3800d56008f53587531718ec36af82cc24576580b36Chris Lattner// instructions that compare a value against a constant, return the value being 3810d56008f53587531718ec36af82cc24576580b36Chris Lattner// compared, and stick the constant into the Values vector. 3821654cff8e80acdddf5e5f2261595007878924aacChris Lattnerstatic Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values){ 3830d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Instruction *Inst = dyn_cast<Instruction>(V)) 3840d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Inst->getOpcode() == Instruction::SetEQ) { 3851654cff8e80acdddf5e5f2261595007878924aacChris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 3860d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 3870d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 3881654cff8e80acdddf5e5f2261595007878924aacChris Lattner } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 3890d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 3900d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(1); 3910d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3920d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::Or) { 3930d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 3940d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 3950d56008f53587531718ec36af82cc24576580b36Chris Lattner if (LHS == RHS) 3960d56008f53587531718ec36af82cc24576580b36Chris Lattner return LHS; 3970d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3980d56008f53587531718ec36af82cc24576580b36Chris Lattner return 0; 3990d56008f53587531718ec36af82cc24576580b36Chris Lattner} 4000d56008f53587531718ec36af82cc24576580b36Chris Lattner 4010d56008f53587531718ec36af82cc24576580b36Chris Lattner// GatherConstantSetNEs - Given a potentially 'and'd together collection of 4020d56008f53587531718ec36af82cc24576580b36Chris Lattner// setne instructions that compare a value against a constant, return the value 4030d56008f53587531718ec36af82cc24576580b36Chris Lattner// being compared, and stick the constant into the Values vector. 4041654cff8e80acdddf5e5f2261595007878924aacChris Lattnerstatic Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values){ 4050d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Instruction *Inst = dyn_cast<Instruction>(V)) 4060d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Inst->getOpcode() == Instruction::SetNE) { 4071654cff8e80acdddf5e5f2261595007878924aacChris Lattner if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(1))) { 4080d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 4090d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 4101654cff8e80acdddf5e5f2261595007878924aacChris Lattner } else if (ConstantInt *C = dyn_cast<ConstantInt>(Inst->getOperand(0))) { 4110d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 4120d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(1); 4130d56008f53587531718ec36af82cc24576580b36Chris Lattner } 4140d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::Cast) { 4150d56008f53587531718ec36af82cc24576580b36Chris Lattner // Cast of X to bool is really a comparison against zero. 4160d56008f53587531718ec36af82cc24576580b36Chris Lattner assert(Inst->getType() == Type::BoolTy && "Can only handle bool values!"); 4171654cff8e80acdddf5e5f2261595007878924aacChris Lattner Values.push_back(ConstantInt::get(Inst->getOperand(0)->getType(), 0)); 4180d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 4190d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::And) { 4200d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 4210d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 4220d56008f53587531718ec36af82cc24576580b36Chris Lattner if (LHS == RHS) 4230d56008f53587531718ec36af82cc24576580b36Chris Lattner return LHS; 4240d56008f53587531718ec36af82cc24576580b36Chris Lattner } 4250d56008f53587531718ec36af82cc24576580b36Chris Lattner return 0; 4260d56008f53587531718ec36af82cc24576580b36Chris Lattner} 4270d56008f53587531718ec36af82cc24576580b36Chris Lattner 4280d56008f53587531718ec36af82cc24576580b36Chris Lattner 4290d56008f53587531718ec36af82cc24576580b36Chris Lattner 4300d56008f53587531718ec36af82cc24576580b36Chris Lattner/// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 4310d56008f53587531718ec36af82cc24576580b36Chris Lattner/// bunch of comparisons of one value against constants, return the value and 4320d56008f53587531718ec36af82cc24576580b36Chris Lattner/// the constants being compared. 4330d56008f53587531718ec36af82cc24576580b36Chris Lattnerstatic bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 4341654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::vector<ConstantInt*> &Values) { 4350d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Cond->getOpcode() == Instruction::Or) { 4360d56008f53587531718ec36af82cc24576580b36Chris Lattner CompVal = GatherConstantSetEQs(Cond, Values); 4370d56008f53587531718ec36af82cc24576580b36Chris Lattner 4380d56008f53587531718ec36af82cc24576580b36Chris Lattner // Return true to indicate that the condition is true if the CompVal is 4390d56008f53587531718ec36af82cc24576580b36Chris Lattner // equal to one of the constants. 4400d56008f53587531718ec36af82cc24576580b36Chris Lattner return true; 4410d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Cond->getOpcode() == Instruction::And) { 4420d56008f53587531718ec36af82cc24576580b36Chris Lattner CompVal = GatherConstantSetNEs(Cond, Values); 443fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 4440d56008f53587531718ec36af82cc24576580b36Chris Lattner // Return false to indicate that the condition is false if the CompVal is 4450d56008f53587531718ec36af82cc24576580b36Chris Lattner // equal to one of the constants. 4460d56008f53587531718ec36af82cc24576580b36Chris Lattner return false; 4470d56008f53587531718ec36af82cc24576580b36Chris Lattner } 4480d56008f53587531718ec36af82cc24576580b36Chris Lattner return false; 4490d56008f53587531718ec36af82cc24576580b36Chris Lattner} 4500d56008f53587531718ec36af82cc24576580b36Chris Lattner 4510d56008f53587531718ec36af82cc24576580b36Chris Lattner/// ErasePossiblyDeadInstructionTree - If the specified instruction is dead and 4520d56008f53587531718ec36af82cc24576580b36Chris Lattner/// has no side effects, nuke it. If it uses any instructions that become dead 4530d56008f53587531718ec36af82cc24576580b36Chris Lattner/// because the instruction is now gone, nuke them too. 4540d56008f53587531718ec36af82cc24576580b36Chris Lattnerstatic void ErasePossiblyDeadInstructionTree(Instruction *I) { 4550d56008f53587531718ec36af82cc24576580b36Chris Lattner if (isInstructionTriviallyDead(I)) { 4560d56008f53587531718ec36af82cc24576580b36Chris Lattner std::vector<Value*> Operands(I->op_begin(), I->op_end()); 4570d56008f53587531718ec36af82cc24576580b36Chris Lattner I->getParent()->getInstList().erase(I); 4580d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Operands.size(); i != e; ++i) 4590d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Instruction *OpI = dyn_cast<Instruction>(Operands[i])) 4600d56008f53587531718ec36af82cc24576580b36Chris Lattner ErasePossiblyDeadInstructionTree(OpI); 4610d56008f53587531718ec36af82cc24576580b36Chris Lattner } 4620d56008f53587531718ec36af82cc24576580b36Chris Lattner} 4630d56008f53587531718ec36af82cc24576580b36Chris Lattner 464542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// isValueEqualityComparison - Return true if the specified terminator checks to 465542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// see if a value is equal to constant integer value. 466542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic Value *isValueEqualityComparison(TerminatorInst *TI) { 4674bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 4684bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner // Do not permit merging of large switch instructions into their 4694bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner // predecessors unless there is only one predecessor. 4704bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner if (SI->getNumSuccessors() * std::distance(pred_begin(SI->getParent()), 4714bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner pred_end(SI->getParent())) > 128) 4724bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner return 0; 4734bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner 474542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SI->getCondition(); 4754bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner } 476542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 477542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (BI->isConditional() && BI->getCondition()->hasOneUse()) 478542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition())) 479542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if ((SCI->getOpcode() == Instruction::SetEQ || 480fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman SCI->getOpcode() == Instruction::SetNE) && 481542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner isa<ConstantInt>(SCI->getOperand(1))) 482542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SCI->getOperand(0); 483542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return 0; 484542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 485542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 486542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// Given a value comparison instruction, decode all of the 'cases' that it 487542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// represents and return the 'default' block. 488542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic BasicBlock * 489fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha BrukmanGetValueEqualityComparisonCases(TerminatorInst *TI, 490542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, 491542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock*> > &Cases) { 492542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 493542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Cases.reserve(SI->getNumCases()); 494542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 495be54dcc8a9d14592e324d6e6ae1322782e17f09fChris Lattner Cases.push_back(std::make_pair(SI->getCaseValue(i), SI->getSuccessor(i))); 496542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SI->getDefaultDest(); 497542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 498542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 499542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BranchInst *BI = cast<BranchInst>(TI); 500542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner SetCondInst *SCI = cast<SetCondInst>(BI->getCondition()); 501542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Cases.push_back(std::make_pair(cast<ConstantInt>(SCI->getOperand(1)), 502542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BI->getSuccessor(SCI->getOpcode() == 503542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Instruction::SetNE))); 504542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return BI->getSuccessor(SCI->getOpcode() == Instruction::SetEQ); 505542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 506542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 507542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 508623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// EliminateBlockCases - Given an vector of bb/value pairs, remove any entries 509623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// in the list that match the specified block. 510fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukmanstatic void EliminateBlockCases(BasicBlock *BB, 511623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) { 512623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = Cases.size(); i != e; ++i) 513623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (Cases[i].second == BB) { 514623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Cases.erase(Cases.begin()+i); 515623369ac5669a3667a94a3cbba342dea78845615Chris Lattner --i; --e; 516623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 517623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 518623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 519623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 520623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// well. 521623369ac5669a3667a94a3cbba342dea78845615Chris Lattnerstatic bool 522623369ac5669a3667a94a3cbba342dea78845615Chris LattnerValuesOverlap(std::vector<std::pair<ConstantInt*, BasicBlock*> > &C1, 523623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > &C2) { 524623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > *V1 = &C1, *V2 = &C2; 525623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 526623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Make V1 be smaller than V2. 527623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() > V2->size()) 528623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::swap(V1, V2); 529623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 530623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() == 0) return false; 531623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() == 1) { 532623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Just scan V2. 533623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ConstantInt *TheVal = (*V1)[0].first; 534623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = V2->size(); i != e; ++i) 535623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TheVal == (*V2)[i].first) 536623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 537623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 538623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 539623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Otherwise, just sort both lists and compare element by element. 540623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::sort(V1->begin(), V1->end()); 541623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::sort(V2->begin(), V2->end()); 542623369ac5669a3667a94a3cbba342dea78845615Chris Lattner unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 543623369ac5669a3667a94a3cbba342dea78845615Chris Lattner while (i1 != e1 && i2 != e2) { 544623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if ((*V1)[i1].first == (*V2)[i2].first) 545623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 546623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if ((*V1)[i1].first < (*V2)[i2].first) 547623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ++i1; 548623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 549623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ++i2; 550623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 551623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; 552623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 553623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 554623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 555623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// terminator instruction and its block is known to only have a single 556623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// predecessor block, check to see if that predecessor is also a value 557623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// comparison with the same value, and if that comparison determines the outcome 558623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// of this comparison. If so, simplify TI. This does a very limited form of 559623369ac5669a3667a94a3cbba342dea78845615Chris Lattner// jump threading. 560623369ac5669a3667a94a3cbba342dea78845615Chris Lattnerstatic bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 561623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *Pred) { 562623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 563623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (!PredVal) return false; // Not a value comparison in predecessor. 564623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 565623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Value *ThisVal = isValueEqualityComparison(TI); 566623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(ThisVal && "This isn't a value comparison!!"); 567623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ThisVal != PredVal) return false; // Different predicates. 568623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 569623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Find out information about when control will move from Pred to TI's block. 570623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 571623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 572623369ac5669a3667a94a3cbba342dea78845615Chris Lattner PredCases); 573623369ac5669a3667a94a3cbba342dea78845615Chris Lattner EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 574fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 575623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Find information about how control leaves this block. 576623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases; 577623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 578623369ac5669a3667a94a3cbba342dea78845615Chris Lattner EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 579623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 580623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If TI's block is the default block from Pred's comparison, potentially 581623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // simplify TI based on this knowledge. 582623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (PredDef == TI->getParent()) { 583623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we are here, we know that the value is none of those cases listed in 584623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // PredCases. If there are any cases in ThisCases that are in PredCases, we 585623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // can simplify TI. 586623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ValuesOverlap(PredCases, ThisCases)) { 587623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BranchInst *BTI = dyn_cast<BranchInst>(TI)) { 588623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, one of the successors of this condbr is dead. Convert it to a 589623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // uncond br. 590623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(ThisCases.size() == 1 && "Branch can only have one case!"); 591623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Value *Cond = BTI->getCondition(); 592623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Insert the new branch. 593623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Instruction *NI = new BranchInst(ThisDef, TI); 594623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 595623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Remove PHI node entries for the dead edge. 596623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ThisCases[0].second->removePredecessor(TI->getParent()); 597623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 598623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator() 599623369ac5669a3667a94a3cbba342dea78845615Chris Lattner << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 600623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 601623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TI->eraseFromParent(); // Nuke the old one. 602623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If condition is now dead, nuke it. 603623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (Instruction *CondI = dyn_cast<Instruction>(Cond)) 604623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ErasePossiblyDeadInstructionTree(CondI); 605623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 606623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 607623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else { 608623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SwitchInst *SI = cast<SwitchInst>(TI); 609623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, TI has cases that are statically dead, prune them away. 610623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::set<Constant*> DeadCases; 611623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 612623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DeadCases.insert(PredCases[i].first); 613623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 614623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator() 615623369ac5669a3667a94a3cbba342dea78845615Chris Lattner << "Through successor TI: " << *TI); 616623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 617623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = SI->getNumCases()-1; i != 0; --i) 618623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (DeadCases.count(SI->getCaseValue(i))) { 619623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SI->getSuccessor(i)->removePredecessor(TI->getParent()); 620623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SI->removeCase(i); 621623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 622623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 623623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DEBUG(std::cerr << "Leaving: " << *TI << "\n"); 624623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 625623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 626623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 627623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 628623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else { 629623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Otherwise, TI's block must correspond to some matched value. Find out 630623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // which value (or set of values) this is. 631623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ConstantInt *TIV = 0; 632623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *TIBB = TI->getParent(); 633623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 634623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (PredCases[i].second == TIBB) 635623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TIV == 0) 636623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TIV = PredCases[i].first; 637623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 638623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; // Cannot handle multiple values coming to this block. 639623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(TIV && "No edge from pred to succ?"); 640623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 641623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, we found the one constant that our value can be if we get into TI's 642623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // BB. Find out which successor will unconditionally be branched to. 643623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *TheRealDest = 0; 644623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 645623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ThisCases[i].first == TIV) { 646623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TheRealDest = ThisCases[i].second; 647623369ac5669a3667a94a3cbba342dea78845615Chris Lattner break; 648623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 649623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 650623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If not handled by any explicit cases, it is handled by the default case. 651623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TheRealDest == 0) TheRealDest = ThisDef; 652623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 653623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Remove PHI node entries for dead edges. 654623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *CheckEdge = TheRealDest; 655623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 656623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (*SI != CheckEdge) 657623369ac5669a3667a94a3cbba342dea78845615Chris Lattner (*SI)->removePredecessor(TIBB); 658623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 659623369ac5669a3667a94a3cbba342dea78845615Chris Lattner CheckEdge = 0; 660623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 661623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Insert the new branch. 662623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Instruction *NI = new BranchInst(TheRealDest, TI); 663623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 664623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DEBUG(std::cerr << "Threading pred instr: " << *Pred->getTerminator() 665623369ac5669a3667a94a3cbba342dea78845615Chris Lattner << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 666623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Instruction *Cond = 0; 667623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 668623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Cond = dyn_cast<Instruction>(BI->getCondition()); 669623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TI->eraseFromParent(); // Nuke the old one. 670623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 671623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (Cond) ErasePossiblyDeadInstructionTree(Cond); 672623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 673623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 674623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; 675623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 676623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 677542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// FoldValueComparisonIntoPredecessors - The specified terminator is a value 678542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// equality comparison instruction (either a switch or a branch on "X == c"). 679542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// See if any of the predecessors of the terminator block are value comparisons 680542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner// on the same value. If so, and if safe to do so, fold them together. 681542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattnerstatic bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 682542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *BB = TI->getParent(); 683542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Value *CV = isValueEqualityComparison(TI); // CondVal 684542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner assert(CV && "Not a comparison?"); 685542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner bool Changed = false; 686542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 687542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 688542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner while (!Preds.empty()) { 689542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *Pred = Preds.back(); 690542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Preds.pop_back(); 691fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 692542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // See if the predecessor is a comparison with the same value. 693542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner TerminatorInst *PTI = Pred->getTerminator(); 694542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 695542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 696542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 697542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Figure out which 'cases' to copy from SI to PSI. 698542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 699542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 700542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 701542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 702542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 703542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 704542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Based on whether the default edge from PTI goes to BB or not, fill in 705542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // PredCases and PredDefault with the new switch cases we would like to 706542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // build. 707542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<BasicBlock*> NewSuccessors; 708542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 709542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredDefault == BB) { 710542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is the default destination from PTI, only the edges in TI 711542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // that don't occur in PTI, or that branch to BB will be activated. 712542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::set<ConstantInt*> PTIHandled; 713542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 714542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredCases[i].second != BB) 715542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.insert(PredCases[i].first); 716542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner else { 717542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // The default destination is BB, we don't need explicit targets. 718542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::swap(PredCases[i], PredCases.back()); 719542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.pop_back(); 720542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner --i; --e; 721542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 722542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 723542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Reconstruct the new switch statement we will be building. 724542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredDefault != BBDefault) { 725542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredDefault->removePredecessor(Pred); 726542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredDefault = BBDefault; 727542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBDefault); 728542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 729542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 730542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (!PTIHandled.count(BBCases[i].first) && 731542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BBCases[i].second != BBDefault) { 732542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(BBCases[i]); 733542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBCases[i].second); 734542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 735542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 736542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } else { 737542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is not the default destination from PSI, only the edges 738542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // in SI that occur in PSI with a destination of BB will be 739542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // activated. 740542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::set<ConstantInt*> PTIHandled; 741542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 742542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredCases[i].second == BB) { 743542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.insert(PredCases[i].first); 744542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::swap(PredCases[i], PredCases.back()); 745542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.pop_back(); 746542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner --i; --e; 747542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 748542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 749542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, now we know which constants were sent to BB from the 750542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // predecessor. Figure out where they will all go now. 751542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 752542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PTIHandled.count(BBCases[i].first)) { 753542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is one we are capable of getting... 754542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(BBCases[i]); 755542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBCases[i].second); 756542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.erase(BBCases[i].first);// This constant is taken care of 757542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 758542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 759542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If there are any constants vectored to BB that TI doesn't handle, 760542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // they must go to the default destination of TI. 761542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (std::set<ConstantInt*>::iterator I = PTIHandled.begin(), 762542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner E = PTIHandled.end(); I != E; ++I) { 763542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(std::make_pair(*I, BBDefault)); 764542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBDefault); 765542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 766542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 767542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 768542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, at this point, we know which new successor Pred will get. Make 769542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // sure we update the number of entries in the PHI nodes for these 770542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // successors. 771542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 772542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 773542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 774542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Now that the successors are updated, create the new Switch instruction. 775378805969ea928b91aa321746031a8f51667a783Chris Lattner SwitchInst *NewSI = new SwitchInst(CV, PredDefault, PredCases.size(),PTI); 776542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 777542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSI->addCase(PredCases[i].first, PredCases[i].second); 77813b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner 77913b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner Instruction *DeadCond = 0; 78013b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 78113b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner // If PTI is a branch, remember the condition. 78213b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner DeadCond = dyn_cast<Instruction>(BI->getCondition()); 783542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Pred->getInstList().erase(PTI); 784542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 78513b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner // If the condition is dead now, remove the instruction tree. 78613b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner if (DeadCond) ErasePossiblyDeadInstructionTree(DeadCond); 78713b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner 788542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, last check. If BB is still a successor of PSI, then we must 789542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // have an infinite loop case. If so, add an infinitely looping block 790542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // to handle the case to preserve the behavior of the code. 791542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *InfLoopBlock = 0; 792542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 793542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (NewSI->getSuccessor(i) == BB) { 794542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (InfLoopBlock == 0) { 795542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Insert it at the end of the loop, because it's either code, 796542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // or it won't matter if it's hot. :) 797542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner InfLoopBlock = new BasicBlock("infloop", BB->getParent()); 798542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner new BranchInst(InfLoopBlock, InfLoopBlock); 799542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 800542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSI->setSuccessor(i, InfLoopBlock); 801542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 802fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 803542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Changed = true; 804542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 805542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 806542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return Changed; 807542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 808542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 8096306d07aa8cf71e3c7fed7f295665f53595473ebChris Lattner/// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and 81037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// BB2, hoist any common code in the two blocks up into the branch block. The 81137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// caller of this function guarantees that BI's block dominates BB1 and BB2. 81237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattnerstatic bool HoistThenElseCodeToIf(BranchInst *BI) { 81337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // This does very trivial matching, with limited scanning, to find identical 81437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // instructions in the two blocks. In particular, we don't want to get into 81537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 81637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // such, we currently just scan for obviously identical instructions in an 81737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // identical order. 81837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 81937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 82037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 82137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Instruction *I1 = BB1->begin(), *I2 = BB2->begin(); 8226306d07aa8cf71e3c7fed7f295665f53595473ebChris Lattner if (I1->getOpcode() != I2->getOpcode() || !I1->isIdenticalTo(I2) || 8236306d07aa8cf71e3c7fed7f295665f53595473ebChris Lattner isa<PHINode>(I1)) 82437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return false; 82537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 82637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // If we get here, we can hoist at least one instruction. 82737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BIParent = BI->getParent(); 82837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 82937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner do { 83037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // If we are hoisting the terminator instruction, don't move one (making a 83137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // broken BB), instead clone it, and remove BI. 83237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (isa<TerminatorInst>(I1)) 83337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner goto HoistTerminator; 834fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 83537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // For a normal instruction, we just move one to right before the branch, 83637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // then replace all uses of the other with the first. Finally, we remove 83737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // the now redundant second instruction. 83837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 83937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (!I2->use_empty()) 84037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2->replaceAllUsesWith(I1); 84137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BB2->getInstList().erase(I2); 842fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 84337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I1 = BB1->begin(); 84437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2 = BB2->begin(); 84537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } while (I1->getOpcode() == I2->getOpcode() && I1->isIdenticalTo(I2)); 84637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 84737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return true; 84837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 84937dc938bbe556a9414d063196d367c2f75d07d95Chris LattnerHoistTerminator: 85037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Okay, it is safe to hoist the terminator. 85137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Instruction *NT = I1->clone(); 85237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BIParent->getInstList().insert(BI, NT); 85337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (NT->getType() != Type::VoidTy) { 85437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I1->replaceAllUsesWith(NT); 85537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2->replaceAllUsesWith(NT); 85637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner NT->setName(I1->getName()); 85737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 85837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 85937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Hoisting one of the terminators from our successor is a great thing. 86037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Unfortunately, the successors of the if/else blocks may have PHI nodes in 86137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 86237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // nodes, so we insert select instruction to compute the final result. 86337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 86437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 86537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PHINode *PN; 86637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (BasicBlock::iterator BBI = SI->begin(); 8670f535c6fa8b03491dc110feb65d78922ee29d1fcChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 86837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Value *BB1V = PN->getIncomingValueForBlock(BB1); 86937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Value *BB2V = PN->getIncomingValueForBlock(BB2); 87037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (BB1V != BB2V) { 87137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // These values do not agree. Insert a select instruction before NT 87237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // that determines the right value. 87337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 87437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (SI == 0) 87537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner SI = new SelectInst(BI->getCondition(), BB1V, BB2V, 87637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BB1V->getName()+"."+BB2V->getName(), NT); 87737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Make the PHI node use the select for all incoming values for BB1/BB2 87837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 87937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 88037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PN->setIncomingValue(i, SI); 88137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 88237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 88337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 88437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 88537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Update any PHI nodes in our new successors. 88637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 88737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner AddPredecessorToBlock(*SI, BIParent, BB1); 888fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 88937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BI->eraseFromParent(); 89037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return true; 89137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner} 89237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 8932e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner/// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch 8942e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner/// across this block. 8952e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattnerstatic bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { 8962e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 8972e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner Value *Cond = BI->getCondition(); 8982e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 899e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner unsigned Size = 0; 900e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 9012e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // If this basic block contains anything other than a PHI (which controls the 9022e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // branch) and branch itself, bail out. FIXME: improve this in the future. 903e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI, ++Size) { 904e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (Size > 10) return false; // Don't clone large BB's. 9052e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 906e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // We can only support instructions that are do not define values that are 907e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // live outside of the current basic block. 908e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 909e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner UI != E; ++UI) { 910e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner Instruction *U = cast<Instruction>(*UI); 911e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (U->getParent() != BB || isa<PHINode>(U)) return false; 912e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 9132e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 9142e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // Looks ok, continue checking. 9152e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner } 916e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 9172e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner return true; 9182e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner} 9192e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 920eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value 921eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// that is defined in the same block as the branch and if any PHI entries are 922eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// constants, thread edges corresponding to that entry to be branches to their 923eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// ultimate destination. 924eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattnerstatic bool FoldCondBranchOnPHI(BranchInst *BI) { 925eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BasicBlock *BB = BI->getParent(); 926eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 9279c88d9816246d260b37cdc689f313c56aec6941eChris Lattner // NOTE: we currently cannot transform this case if the PHI node is used 9289c88d9816246d260b37cdc689f313c56aec6941eChris Lattner // outside of the block. 9292e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (!PN || PN->getParent() != BB || !PN->hasOneUse()) 9302e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner return false; 931eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 932eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Degenerate case of a single entry PHI. 933eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PN->getNumIncomingValues() == 1) { 934eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PN->getIncomingValue(0) != PN) 935eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 936eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner else 937eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 938eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PN->eraseFromParent(); 939eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return true; 940eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 941eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 942eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Now we know that this block has multiple preds and two succs. 9432e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; 944eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 945eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Okay, this is a simple enough basic block. See if any phi values are 946eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // constants. 947eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 948eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (ConstantBool *CB = dyn_cast<ConstantBool>(PN->getIncomingValue(i))) { 949eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Okay, we now know that all edges from PredBB should be revectored to 950eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // branch to RealDest. 951eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BasicBlock *PredBB = PN->getIncomingBlock(i); 952eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BasicBlock *RealDest = BI->getSuccessor(!CB->getValue()); 953eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 954e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (RealDest == BB) continue; // Skip self loops. 955eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 956e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // The dest block might have PHI nodes, other predecessors and other 957e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // difficult cases. Instead of being smart about this, just insert a new 958e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // block that jumps to the destination block, effectively splitting 959e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // the edge we are about to create. 960e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner BasicBlock *EdgeBB = new BasicBlock(RealDest->getName()+".critedge", 961e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner RealDest->getParent(), RealDest); 962e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner new BranchInst(RealDest, EdgeBB); 963e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner PHINode *PN; 964e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (BasicBlock::iterator BBI = RealDest->begin(); 965e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 966e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner Value *V = PN->getIncomingValueForBlock(BB); 967e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner PN->addIncoming(V, EdgeBB); 968e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 969e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 970e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // BB may have instructions that are being threaded over. Clone these 971e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // instructions into EdgeBB. We know that there will be no uses of the 972e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // cloned instructions outside of EdgeBB. 973e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner BasicBlock::iterator InsertPt = EdgeBB->begin(); 974e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner std::map<Value*, Value*> TranslateMap; // Track translated values. 975e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 976e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 977e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); 978e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } else { 979e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Clone the instruction. 980e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner Instruction *N = BBI->clone(); 981e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (BBI->hasName()) N->setName(BBI->getName()+".c"); 982e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 983e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Update operands due to translation. 984e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 985e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner std::map<Value*, Value*>::iterator PI = 986e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner TranslateMap.find(N->getOperand(i)); 987e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (PI != TranslateMap.end()) 988e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner N->setOperand(i, PI->second); 989e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 990e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 991e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Check for trivial simplification. 992e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (Constant *C = ConstantFoldInstruction(N)) { 993e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner std::cerr << "FOLDED: " << *N; 994e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner TranslateMap[BBI] = C; 995e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner delete N; // Constant folded away, don't need actual inst 996e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } else { 997e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Insert the new instruction into its new home. 998e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner EdgeBB->getInstList().insert(InsertPt, N); 999e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (!BBI->use_empty()) 1000e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner TranslateMap[BBI] = N; 1001e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1002e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1003e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1004e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 1005eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Loop over all of the edges from PredBB to BB, changing them to branch 1006e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // to EdgeBB instead. 1007eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner TerminatorInst *PredBBTI = PredBB->getTerminator(); 1008eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 1009eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PredBBTI->getSuccessor(i) == BB) { 1010eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BB->removePredecessor(PredBB); 1011e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner PredBBTI->setSuccessor(i, EdgeBB); 1012eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 1013eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1014eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Recurse, simplifying any other constants. 1015eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return FoldCondBranchOnPHI(BI) | true; 1016eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 1017eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1018eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return false; 1019eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner} 1020eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1021f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner/// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry 1022f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner/// PHI node, see if we can eliminate it. 1023f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattnerstatic bool FoldTwoEntryPHINode(PHINode *PN) { 1024f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1025f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // statement", which has a very simple dominance structure. Basically, we 1026f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // are trying to find the condition that is being branched on, which 1027f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // subsequently causes this merge to happen. We really want control 1028f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // dependence information for this check, but simplifycfg can't keep it up 1029f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // to date, and this catches most of the cases we care about anyway. 1030f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // 1031f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *BB = PN->getParent(); 1032f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *IfTrue, *IfFalse; 1033f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); 1034f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (!IfCond) return false; 1035f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1036f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DEBUG(std::cerr << "FOUND IF CONDITION! " << *IfCond << " T: " 1037f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1038f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1039f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Loop over the PHI's seeing if we can promote them all to select 1040f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // instructions. While we are at it, keep track of the instructions 1041f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // that need to be moved to the dominating block. 1042f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner std::set<Instruction*> AggressiveInsts; 1043f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1044f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock::iterator AfterPHIIt = BB->begin(); 1045f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner while (isa<PHINode>(AfterPHIIt)) { 1046f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PHINode *PN = cast<PHINode>(AfterPHIIt++); 1047f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) { 1048f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (PN->getIncomingValue(0) != PN) 1049f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 1050f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner else 1051f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 1052f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 1053f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner &AggressiveInsts) || 1054f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner !DominatesMergePoint(PN->getIncomingValue(1), BB, 1055f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner &AggressiveInsts)) { 1056055dc102e97316d423bd068f8b228d27fb93c90aChris Lattner return false; 1057f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1058f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1059f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1060f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // If we all PHI nodes are promotable, check to make sure that all 1061f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // instructions in the predecessor blocks can be promoted as well. If 1062f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // not, we won't be able to get rid of the control flow, so it's not 1063f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // worth promoting to select instructions. 1064f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 1065f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN = cast<PHINode>(BB->begin()); 1066f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *Pred = PN->getIncomingBlock(0); 1067f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1068f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1 = Pred; 1069f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock = *pred_begin(Pred); 1070f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner for (BasicBlock::iterator I = Pred->begin(); 1071f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner !isa<TerminatorInst>(I); ++I) 1072f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (!AggressiveInsts.count(I)) { 1073f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // This is not an aggressive instruction that we can promote. 1074f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Because of this, we won't be able to get rid of the control 1075f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // flow, so the xform is not worth it. 1076f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner return false; 1077f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1078f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1079f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1080f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Pred = PN->getIncomingBlock(1); 1081f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1082f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2 = Pred; 1083f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock = *pred_begin(Pred); 1084f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner for (BasicBlock::iterator I = Pred->begin(); 1085f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner !isa<TerminatorInst>(I); ++I) 1086f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (!AggressiveInsts.count(I)) { 1087f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // This is not an aggressive instruction that we can promote. 1088f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Because of this, we won't be able to get rid of the control 1089f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // flow, so the xform is not worth it. 1090f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner return false; 1091f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1092f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1093f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1094f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // If we can still promote the PHI nodes after this gauntlet of tests, 1095f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // do all of the PHI's now. 1096f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1097f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Move all 'aggressive' instructions, which are defined in the 1098f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // conditional parts of the if's up to the dominating block. 1099f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (IfBlock1) { 1100f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 1101f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1->getInstList(), 1102f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1->begin(), 1103f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1->getTerminator()); 1104f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1105f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (IfBlock2) { 1106f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 1107f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2->getInstList(), 1108f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2->begin(), 1109f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2->getTerminator()); 1110f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1111f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1112f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 1113f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Change the PHI node into a select instruction. 1114f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Value *TrueVal = 1115f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1116f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Value *FalseVal = 1117f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1118f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1119f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner std::string Name = PN->getName(); PN->setName(""); 1120f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->replaceAllUsesWith(new SelectInst(IfCond, TrueVal, FalseVal, 1121f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Name, AfterPHIIt)); 1122f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BB->getInstList().erase(PN); 1123f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1124f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner return true; 1125f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner} 1126eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 11271654cff8e80acdddf5e5f2261595007878924aacChris Lattnernamespace { 11281654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// ConstantIntOrdering - This class implements a stable ordering of constant 11291654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// integers that does not depend on their address. This is important for 11301654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// applications that sort ConstantInt's to ensure uniqueness. 11311654cff8e80acdddf5e5f2261595007878924aacChris Lattner struct ConstantIntOrdering { 11321654cff8e80acdddf5e5f2261595007878924aacChris Lattner bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 11331654cff8e80acdddf5e5f2261595007878924aacChris Lattner return LHS->getRawValue() < RHS->getRawValue(); 11341654cff8e80acdddf5e5f2261595007878924aacChris Lattner } 11351654cff8e80acdddf5e5f2261595007878924aacChris Lattner }; 11361654cff8e80acdddf5e5f2261595007878924aacChris Lattner} 11371654cff8e80acdddf5e5f2261595007878924aacChris Lattner 113801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// SimplifyCFG - This function is used to do simplification of a CFG. For 113901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// example, it adjusts branches to branches to eliminate the extra hop, it 114001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// eliminates unreachable basic blocks, and does other "peephole" optimization 1141e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// of the CFG. It returns true if a modification was made. 114201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 114301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// WARNING: The entry node of a function may not be simplified. 114401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 1145f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::SimplifyCFG(BasicBlock *BB) { 1146dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner bool Changed = false; 114701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner Function *M = BB->getParent(); 114801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 114901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB && BB->getParent() && "Block not embedded in function!"); 115001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB->getTerminator() && "Degenerate basic block encountered!"); 115118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 115201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 115301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove basic blocks that have no predecessors... which are unreachable. 1154d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (pred_begin(BB) == pred_end(BB) || 1155d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner *pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB)) { 115630b434476796cd4a85c02914687d22f2e5ec95caChris Lattner DEBUG(std::cerr << "Removing BB: \n" << *BB); 115701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 115801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Loop through all of our successors and make sure they know that one 115901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // of their predecessors is going away. 1160151c80be8180a7a0aa1594848699aa6b678b3998Chris Lattner for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 1161151c80be8180a7a0aa1594848699aa6b678b3998Chris Lattner SI->removePredecessor(BB); 116201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 116301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner while (!BB->empty()) { 116418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Instruction &I = BB->back(); 116501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If this instruction is used, replace uses with an arbitrary 1166f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner // value. Because control flow can't get here, we don't care 1167fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // what we replace the value with. Note that since this block is 116801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // unreachable, and all values contained within it must dominate their 116901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // uses, that all uses will eventually be removed. 1170fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman if (!I.use_empty()) 1171f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner // Make all users of this instruction use undef instead 1172f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner I.replaceAllUsesWith(UndefValue::get(I.getType())); 1173fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 117401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove the instruction from the basic block 117518961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BB->getInstList().pop_back(); 117601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 117718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 117801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 117901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 118001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 1181694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // Check to see if we can constant propagate this terminator instruction 1182694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // away... 1183dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner Changed |= ConstantFoldTerminator(BB); 1184694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 118519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If this is a returning block with only PHI nodes in it, fold the return 118619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // instruction into any unconditional branch predecessors. 1187147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // 1188147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // If any predecessor is a conditional branch that just selects among 1189147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // different return values, fold the replace the branch/return with a select 1190147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // and return. 119119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 119219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BasicBlock::iterator BBI = BB->getTerminator(); 119319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BBI == BB->begin() || isa<PHINode>(--BBI)) { 1194147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Find predecessors that end with branches. 119519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner std::vector<BasicBlock*> UncondBranchPreds; 1196147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner std::vector<BranchInst*> CondBranchPreds; 119719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 119819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner TerminatorInst *PTI = (*PI)->getTerminator(); 119919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 120019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BI->isUnconditional()) 120119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner UncondBranchPreds.push_back(*PI); 1202147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner else 1203147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner CondBranchPreds.push_back(BI); 120419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 1205fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 120619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we found some, do the transformation! 120719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (!UncondBranchPreds.empty()) { 120819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner while (!UncondBranchPreds.empty()) { 120919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BasicBlock *Pred = UncondBranchPreds.back(); 121019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner UncondBranchPreds.pop_back(); 121119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Instruction *UncondBranch = Pred->getTerminator(); 121219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Clone the return and add it to the end of the predecessor. 121319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Instruction *NewRet = RI->clone(); 121419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().push_back(NewRet); 121519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 121619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If the return instruction returns a value, and if the value was a 121719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // PHI node in "BB", propagate the right value into the return. 121819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (NewRet->getNumOperands() == 1) 121919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0))) 122019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (PN->getParent() == BB) 122119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred)); 122219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Update any PHI nodes in the returning block to realize that we no 122319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // longer branch to them. 122419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BB->removePredecessor(Pred); 122519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().erase(UncondBranch); 122619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 122719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 122819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we eliminated all predecessors of the block, delete the block now. 122919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (pred_begin(BB) == pred_end(BB)) 123019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // We know there are no successors, so just nuke the block. 123119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner M->getBasicBlockList().erase(BB); 123219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 123319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner return true; 123419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 1235147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1236147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check out all of the conditional branches going to this return 1237147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // instruction. If any of them just select between returns, change the 1238147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // branch itself into a select/return pair. 1239147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner while (!CondBranchPreds.empty()) { 1240147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BranchInst *BI = CondBranchPreds.back(); 1241147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner CondBranchPreds.pop_back(); 1242147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *TrueSucc = BI->getSuccessor(0); 1243147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *FalseSucc = BI->getSuccessor(1); 1244147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *OtherSucc = TrueSucc == BB ? FalseSucc : TrueSucc; 1245147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1246147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check to see if the non-BB successor is also a return block. 1247147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (isa<ReturnInst>(OtherSucc->getTerminator())) { 1248147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check to see if there are only PHI instructions in this block. 1249147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock::iterator OSI = OtherSucc->getTerminator(); 1250147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (OSI == OtherSucc->begin() || isa<PHINode>(--OSI)) { 1251147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Okay, we found a branch that is going to two return nodes. If 1252147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // there is no return value for this function, just change the 1253147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // branch into a return. 1254147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (RI->getNumOperands() == 0) { 1255147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner TrueSucc->removePredecessor(BI->getParent()); 1256147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner FalseSucc->removePredecessor(BI->getParent()); 1257147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner new ReturnInst(0, BI); 1258147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BI->getParent()->getInstList().erase(BI); 1259147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner return true; 1260147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1261147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1262147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Otherwise, figure out what the true and false return values are 1263147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // so we can insert a new select instruction. 1264147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner Value *TrueValue = TrueSucc->getTerminator()->getOperand(0); 1265147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner Value *FalseValue = FalseSucc->getTerminator()->getOperand(0); 1266147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1267147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Unwrap any PHI nodes in the return blocks. 1268147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue)) 1269147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (TVPN->getParent() == TrueSucc) 1270147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1271147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue)) 1272147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (FVPN->getParent() == FalseSucc) 1273147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1274147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 12757aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner TrueSucc->removePredecessor(BI->getParent()); 12767aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner FalseSucc->removePredecessor(BI->getParent()); 12777aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner 1278147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Insert a new select instruction. 12790ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner Value *NewRetVal; 12800ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner Value *BrCond = BI->getCondition(); 12810ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (TrueValue != FalseValue) 12820ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner NewRetVal = new SelectInst(BrCond, TrueValue, 12830ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner FalseValue, "retval", BI); 12840ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner else 12850ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner NewRetVal = TrueValue; 12860ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner 1287147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner new ReturnInst(NewRetVal, BI); 1288147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BI->getParent()->getInstList().erase(BI); 12890ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (BrCond->use_empty()) 12900ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (Instruction *BrCondI = dyn_cast<Instruction>(BrCond)) 12910ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner BrCondI->getParent()->getInstList().erase(BrCondI); 1292147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner return true; 1293147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1294147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1295147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 129619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 1297e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->begin())) { 1298e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Check to see if the first instruction in this block is just an unwind. 1299e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // If so, replace any invoke instructions which use this as an exception 1300af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner // destination with call instructions, and any unconditional branch 1301af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner // predecessor with an unwind. 1302e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // 1303e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 1304e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner while (!Preds.empty()) { 1305e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner BasicBlock *Pred = Preds.back(); 1306af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) { 1307af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner if (BI->isUnconditional()) { 1308af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner Pred->getInstList().pop_back(); // nuke uncond branch 1309af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner new UnwindInst(Pred); // Use unwind. 1310af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner Changed = true; 1311af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner } 1312af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 1313e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner if (II->getUnwindDest() == BB) { 1314e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Insert a new branch instruction before the invoke, because this 1315e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // is now a fall through... 1316e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner BranchInst *BI = new BranchInst(II->getNormalDest(), II); 1317e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Pred->getInstList().remove(II); // Take out of symbol table 1318fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1319e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Insert the call now... 1320e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 1321e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner CallInst *CI = new CallInst(II->getCalledValue(), Args, 1322e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner II->getName(), BI); 132316d0db2da8c274f98db4a89ca7a92f970d464b9aChris Lattner CI->setCallingConv(II->getCallingConv()); 1324e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // If the invoke produced a value, the Call now does instead 1325e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner II->replaceAllUsesWith(CI); 1326e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner delete II; 1327e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Changed = true; 1328e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 1329fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1330e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Preds.pop_back(); 1331e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 13328e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 13338e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // If this block is now dead, remove it. 13348e509dd5e81e92a466580ab4022994079952cca9Chris Lattner if (pred_begin(BB) == pred_end(BB)) { 13358e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // We know there are no successors, so just nuke the block. 13368e509dd5e81e92a466580ab4022994079952cca9Chris Lattner M->getBasicBlockList().erase(BB); 13378e509dd5e81e92a466580ab4022994079952cca9Chris Lattner return true; 13388e509dd5e81e92a466580ab4022994079952cca9Chris Lattner } 13398e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 1340623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1341623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (isValueEqualityComparison(SI)) { 1342623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we only have one predecessor, and if it is a branch on this value, 1343623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // see if that predecessor totally determines the outcome of this switch. 1344623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1345623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) 1346623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1347623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 1348623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If the block only contains the switch, see if we can fold the block 1349623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // away into any preds. 1350623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SI == &BB->front()) 1351623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (FoldValueComparisonIntoPredecessors(SI)) 1352623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1353623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 1354542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 13557e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (BI->isUnconditional()) { 13567e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 13577e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner while (isa<PHINode>(*BBI)) ++BBI; 13587e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 13597e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BasicBlock *Succ = BI->getSuccessor(0); 13607e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (BBI->isTerminator() && // Terminator is the only non-phi instruction! 13617e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner Succ != BB) // Don't hurt infinite loops! 13627e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ)) 13637e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner return 1; 13647e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 13657e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } else { // Conditional branch 1366e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (Value *CompVal = isValueEqualityComparison(BI)) { 1367623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we only have one predecessor, and if it is a branch on this value, 1368623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // see if that predecessor totally determines the outcome of this 1369623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // switch. 1370623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1371623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) 1372623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1373623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 1374e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // This block must be empty, except for the setcond inst, if it exists. 1375e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock::iterator I = BB->begin(); 1376e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (&*I == BI || 1377e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner (&*I == cast<Instruction>(BI->getCondition()) && 1378e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner &*++I == BI)) 1379e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (FoldValueComparisonIntoPredecessors(BI)) 1380e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner return SimplifyCFG(BB) | true; 1381e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1382eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1383eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // If this is a branch on a phi node in the current block, thread control 1384eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // through this block if any PHI node entries are constants. 1385eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 1386eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PN->getParent() == BI->getParent()) 1387eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (FoldCondBranchOnPHI(BI)) 1388eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return SimplifyCFG(BB) | true; 1389eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1390e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 1391e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // If this basic block is ONLY a setcc and a branch, and if a predecessor 1392e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // branches to us and one of our successors, fold the setcc into the 1393e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // predecessor and use logical operations to pick the right destination. 139412fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner BasicBlock *TrueDest = BI->getSuccessor(0); 139512fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner BasicBlock *FalseDest = BI->getSuccessor(1); 1396bdcc0b8c55041ff89b59f0ea2cdbc2ac02f26a3dChris Lattner if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(BI->getCondition())) 1397e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (Cond->getParent() == BB && &BB->front() == Cond && 139812fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner Cond->getNext() == BI && Cond->hasOneUse() && 139912fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner TrueDest != BB && FalseDest != BB) 1400e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI) 1401e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1402a1f79fb08b92801d4ab3cb32fe0bd9d12dfb3954Chris Lattner if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) { 14032636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner BasicBlock *PredBlock = *PI; 1404e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == FalseDest || 1405e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(1) == TrueDest) { 1406e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // Invert the predecessors condition test (xor it with true), 1407e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // which allows us to write this code once. 1408e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Value *NewCond = 1409e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BinaryOperator::createNot(PBI->getCondition(), 1410e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getCondition()->getName()+".not", PBI); 1411e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setCondition(NewCond); 1412e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock *OldTrue = PBI->getSuccessor(0); 1413e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock *OldFalse = PBI->getSuccessor(1); 1414e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(0, OldFalse); 1415e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(1, OldTrue); 1416e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1417e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 1418e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == TrueDest || 1419e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(1) == FalseDest) { 14202636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner // Clone Cond into the predecessor basic block, and or/and the 1421e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // two conditions together. 1422e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction *New = Cond->clone(); 1423e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner New->setName(Cond->getName()); 1424e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Cond->setName(Cond->getName()+".old"); 14252636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner PredBlock->getInstList().insert(PBI, New); 1426e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction::BinaryOps Opcode = 1427e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(0) == TrueDest ? 1428e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction::Or : Instruction::And; 1429fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman Value *NewCond = 1430e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BinaryOperator::create(Opcode, PBI->getCondition(), 1431e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner New, "bothcond", PBI); 1432e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setCondition(NewCond); 1433e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == BB) { 14342636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner AddPredecessorToBlock(TrueDest, PredBlock, BB); 1435e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(0, TrueDest); 1436e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1437e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(1) == BB) { 14382636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner AddPredecessorToBlock(FalseDest, PredBlock, BB); 1439e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(1, FalseDest); 1440e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1441e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner return SimplifyCFG(BB) | 1; 1442e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1443e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1444e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 14452e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // If this block ends with a branch instruction, and if there is a 14462e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // predecessor that ends on a branch of the same condition, make this 14472e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // conditional branch redundant. 14482e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 14492e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 14502e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (PBI != BI && PBI->isConditional() && 145192da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner PBI->getCondition() == BI->getCondition() && 14522e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 145392da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // Okay, the outcome of this conditional branch is statically 14542e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // knowable. If this block had a single pred, handle specially. 14552e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (BB->getSinglePredecessor()) { 14562e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // Turn this into a branch on constant. 14572e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner bool CondIsTrue = PBI->getSuccessor(0) == BB; 14582e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner BI->setCondition(ConstantBool::get(CondIsTrue)); 14592e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner return SimplifyCFG(BB); // Nuke the branch on constant. 14602e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner } 14612e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 14622e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // Otherwise, if there are multiple predecessors, insert a PHI that 14632e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // merges in the constant and simplify the block result. 14642e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (BlockIsSimpleEnoughToThreadThrough(BB)) { 14652e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner PHINode *NewPN = new PHINode(Type::BoolTy, 14662e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner BI->getCondition()->getName()+".pr", 14672e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner BB->begin()); 14682e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner for (PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 14692e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if ((PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) && 14702e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner PBI != BI && PBI->isConditional() && 14712e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner PBI->getCondition() == BI->getCondition() && 14722e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 14732e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner bool CondIsTrue = PBI->getSuccessor(0) == BB; 14742e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner NewPN->addIncoming(ConstantBool::get(CondIsTrue), *PI); 14752e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner } else { 14762e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner NewPN->addIncoming(BI->getCondition(), *PI); 14772e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner } 14782e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 14792e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner BI->setCondition(NewPN); 14802e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // This will thread the branch. 14812e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner return SimplifyCFG(BB) | true; 14822e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner } 148392da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner } 1484d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner } 1485698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (isa<UnreachableInst>(BB->getTerminator())) { 1486698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If there are any instructions immediately before the unreachable that can 1487698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // be removed, do so. 1488698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Instruction *Unreachable = BB->getTerminator(); 1489698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner while (Unreachable != BB->begin()) { 1490698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock::iterator BBI = Unreachable; 1491698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --BBI; 1492698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (isa<CallInst>(BBI)) break; 1493698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Delete this instruction 1494698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BB->getInstList().erase(BBI); 1495698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1496698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1497698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1498698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the unreachable instruction is the first in the block, take a gander 1499698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // at all of the predecessors of this instruction, and simplify them. 1500698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (&BB->front() == Unreachable) { 1501698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 1502698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 1503698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TerminatorInst *TI = Preds[i]->getTerminator(); 1504698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1505698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1506698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->isUnconditional()) { 1507698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 1508698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new UnreachableInst(TI); 1509698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TI->eraseFromParent(); 1510698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1511698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1512698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else { 1513698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 1514698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new BranchInst(BI->getSuccessor(1), BI); 1515698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BI->eraseFromParent(); 1516698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (BI->getSuccessor(1) == BB) { 1517698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new BranchInst(BI->getSuccessor(0), BI); 1518698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BI->eraseFromParent(); 1519698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1520698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1521698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1522698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1523698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1524698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == BB) { 152542eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner BB->removePredecessor(SI->getParent()); 1526698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1527698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1528698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1529698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1530698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the default value is unreachable, figure out the most popular 1531698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // destination and make it the default. 1532698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(0) == BB) { 1533698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::map<BasicBlock*, unsigned> Popularity; 1534698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1535698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Popularity[SI->getSuccessor(i)]++; 1536698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1537698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Find the most popular block. 1538698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner unsigned MaxPop = 0; 1539698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock *MaxBlock = 0; 1540698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (std::map<BasicBlock*, unsigned>::iterator 1541698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 1542698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (I->second > MaxPop) { 1543698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxPop = I->second; 1544698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxBlock = I->first; 1545698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1546698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1547698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (MaxBlock) { 1548698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Make this the new default, allowing us to delete any explicit 1549698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // edges to it. 1550698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->setSuccessor(0, MaxBlock); 1551698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1552698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 155342eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 155442eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner // it. 155542eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner if (isa<PHINode>(MaxBlock->begin())) 155642eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner for (unsigned i = 0; i != MaxPop-1; ++i) 155742eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner MaxBlock->removePredecessor(SI->getParent()); 155842eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner 1559698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1560698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == MaxBlock) { 1561698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1562698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1563698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1564698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1565698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1566698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 1567698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (II->getUnwindDest() == BB) { 1568698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Convert the invoke to a call instruction. This would be a good 1569698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // place to note that the call does not throw though. 1570698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BranchInst *BI = new BranchInst(II->getNormalDest(), II); 1571698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->removeFromParent(); // Take out of symbol table 1572fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1573698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Insert the call now... 1574698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 1575698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner CallInst *CI = new CallInst(II->getCalledValue(), Args, 1576698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->getName(), BI); 157716d0db2da8c274f98db4a89ca7a92f970d464b9aChris Lattner CI->setCallingConv(II->getCallingConv()); 1578698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the invoke produced a value, the Call does now instead. 1579698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->replaceAllUsesWith(CI); 1580698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner delete II; 1581698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1582698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1583698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1584698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1585698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1586698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If this block is now dead, remove it. 1587698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (pred_begin(BB) == pred_end(BB)) { 1588698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // We know there are no successors, so just nuke the block. 1589698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner M->getBasicBlockList().erase(BB); 1590698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner return true; 1591698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1592698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 159319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 159419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 159501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Merge basic blocks into their predecessor if there is only one distinct 159601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // pred, and if there is only one distinct successor of the predecessor, and 159701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // if there are no PHI nodes. 159801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 15992355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 16002355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BasicBlock *OnlyPred = *PI++; 16012355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 16022355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (*PI != OnlyPred) { 16032355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred = 0; // There are multiple different predecessors... 16042355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner break; 16052355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 160692da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner 16072355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BasicBlock *OnlySucc = 0; 16082355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (OnlyPred && OnlyPred != BB && // Don't break self loops 16092355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 16102355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Check to see if there is only one distinct successor... 16112355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 16122355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlySucc = BB; 16132355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner for (; SI != SE; ++SI) 16142355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (*SI != OnlySucc) { 16152355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlySucc = 0; // There are multiple distinct successors! 161601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner break; 161701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 16182355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 161901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 16202355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (OnlySucc) { 162130b434476796cd4a85c02914687d22f2e5ec95caChris Lattner DEBUG(std::cerr << "Merging: " << *BB << "into: " << *OnlyPred); 16222355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner TerminatorInst *Term = OnlyPred->getTerminator(); 162301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 16242355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Resolve any PHI nodes at the start of the block. They are all 16252355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // guaranteed to have exactly one entry if they exist, unless there are 16262355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // multiple duplicate (but guaranteed to be equal) entries for the 16272355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // incoming edges. This occurs when there are multiple edges from 16282355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // OnlyPred to OnlySucc. 16292355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // 16302355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 16312355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 16322355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BB->getInstList().pop_front(); // Delete the phi node... 16332355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 163491b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner 16352355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Delete the unconditional branch from the predecessor... 16362355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getInstList().pop_back(); 1637fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 16382355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Move all definitions in the successor to the predecessor... 16392355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 1640fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 16412355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Make all PHI nodes that referred to BB now refer to Pred as their 16422355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // source... 16432355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BB->replaceAllUsesWith(OnlyPred); 164418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 16452355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner std::string OldName = BB->getName(); 164618961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 1647fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // Erase basic block from the function... 16482355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner M->getBasicBlockList().erase(BB); 164918961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 16502355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Inherit predecessors name if it exists... 16512355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (!OldName.empty() && !OnlyPred->hasName()) 16522355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->setName(OldName); 1653fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 16542355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner return true; 165501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 1656723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 165737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Otherwise, if this block only has a single predecessor, and if that block 165837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // is a conditional branch, see if we can hoist any code from this block up 165937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // into our predecessor. 166037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (OnlyPred) 16617613437db954abafd1230c961e87872df5721957Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 16627613437db954abafd1230c961e87872df5721957Chris Lattner if (BI->isConditional()) { 16637613437db954abafd1230c961e87872df5721957Chris Lattner // Get the other block. 16647613437db954abafd1230c961e87872df5721957Chris Lattner BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); 16657613437db954abafd1230c961e87872df5721957Chris Lattner PI = pred_begin(OtherBB); 16667613437db954abafd1230c961e87872df5721957Chris Lattner ++PI; 16677613437db954abafd1230c961e87872df5721957Chris Lattner if (PI == pred_end(OtherBB)) { 16687613437db954abafd1230c961e87872df5721957Chris Lattner // We have a conditional branch to two blocks that are only reachable 16697613437db954abafd1230c961e87872df5721957Chris Lattner // from the condbr. We know that the condbr dominates the two blocks, 16707613437db954abafd1230c961e87872df5721957Chris Lattner // so see if there is any identical code in the "then" and "else" 16717613437db954abafd1230c961e87872df5721957Chris Lattner // blocks. If so, we can hoist it up to the branching block. 16727613437db954abafd1230c961e87872df5721957Chris Lattner Changed |= HoistThenElseCodeToIf(BI); 16737613437db954abafd1230c961e87872df5721957Chris Lattner } 167437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 167537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 16760d56008f53587531718ec36af82cc24576580b36Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 16770d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 16780d56008f53587531718ec36af82cc24576580b36Chris Lattner // Change br (X == 0 | X == 1), T, F into a switch instruction. 16790d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 16800d56008f53587531718ec36af82cc24576580b36Chris Lattner Instruction *Cond = cast<Instruction>(BI->getCondition()); 16810d56008f53587531718ec36af82cc24576580b36Chris Lattner // If this is a bunch of seteq's or'd together, or if it's a bunch of 16820d56008f53587531718ec36af82cc24576580b36Chris Lattner // 'setne's and'ed together, collect them. 16830d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *CompVal = 0; 16841654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::vector<ConstantInt*> Values; 16850d56008f53587531718ec36af82cc24576580b36Chris Lattner bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 16860d56008f53587531718ec36af82cc24576580b36Chris Lattner if (CompVal && CompVal->getType()->isInteger()) { 16870d56008f53587531718ec36af82cc24576580b36Chris Lattner // There might be duplicate constants in the list, which the switch 16880d56008f53587531718ec36af82cc24576580b36Chris Lattner // instruction can't handle, remove them now. 16891654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 16900d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 1691fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 16920d56008f53587531718ec36af82cc24576580b36Chris Lattner // Figure out which block is which destination. 16930d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *DefaultBB = BI->getSuccessor(1); 16940d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *EdgeBB = BI->getSuccessor(0); 16950d56008f53587531718ec36af82cc24576580b36Chris Lattner if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 1696fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 16970d56008f53587531718ec36af82cc24576580b36Chris Lattner // Create the new switch instruction now. 1698378805969ea928b91aa321746031a8f51667a783Chris Lattner SwitchInst *New = new SwitchInst(CompVal, DefaultBB,Values.size(),BI); 1699fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 17000d56008f53587531718ec36af82cc24576580b36Chris Lattner // Add all of the 'cases' to the switch instruction. 17010d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size(); i != e; ++i) 17020d56008f53587531718ec36af82cc24576580b36Chris Lattner New->addCase(Values[i], EdgeBB); 1703fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 17040d56008f53587531718ec36af82cc24576580b36Chris Lattner // We added edges from PI to the EdgeBB. As such, if there were any 17050d56008f53587531718ec36af82cc24576580b36Chris Lattner // PHI nodes in EdgeBB, they need entries to be added corresponding to 17060d56008f53587531718ec36af82cc24576580b36Chris Lattner // the number of edges added. 17070d56008f53587531718ec36af82cc24576580b36Chris Lattner for (BasicBlock::iterator BBI = EdgeBB->begin(); 17082da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer isa<PHINode>(BBI); ++BBI) { 17092da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(BBI); 17100d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *InVal = PN->getIncomingValueForBlock(*PI); 17110d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 17120d56008f53587531718ec36af82cc24576580b36Chris Lattner PN->addIncoming(InVal, *PI); 17130d56008f53587531718ec36af82cc24576580b36Chris Lattner } 17140d56008f53587531718ec36af82cc24576580b36Chris Lattner 17150d56008f53587531718ec36af82cc24576580b36Chris Lattner // Erase the old branch instruction. 17160d56008f53587531718ec36af82cc24576580b36Chris Lattner (*PI)->getInstList().erase(BI); 17170d56008f53587531718ec36af82cc24576580b36Chris Lattner 17180d56008f53587531718ec36af82cc24576580b36Chris Lattner // Erase the potentially condition tree that was used to computed the 17190d56008f53587531718ec36af82cc24576580b36Chris Lattner // branch condition. 17200d56008f53587531718ec36af82cc24576580b36Chris Lattner ErasePossiblyDeadInstructionTree(Cond); 17210d56008f53587531718ec36af82cc24576580b36Chris Lattner return true; 17220d56008f53587531718ec36af82cc24576580b36Chris Lattner } 17230d56008f53587531718ec36af82cc24576580b36Chris Lattner } 17240d56008f53587531718ec36af82cc24576580b36Chris Lattner 1725723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If there is a trivial two-entry PHI node in this basic block, and we can 1726723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // eliminate it, do so now. 1727723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 1728f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (PN->getNumIncomingValues() == 2) 1729f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Changed |= FoldTwoEntryPHINode(PN); 1730fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1731694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner return Changed; 173201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 1733