SimplifyCFG.cpp revision eaba3a194c23ecbfc5f3da439d1ef7a08eedf02c
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 893eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value 894eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// that is defined in the same block as the branch and if any PHI entries are 895eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// constants, thread edges corresponding to that entry to be branches to their 896eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// ultimate destination. 897eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattnerstatic bool FoldCondBranchOnPHI(BranchInst *BI) { 898eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BasicBlock *BB = BI->getParent(); 899eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 900eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (!PN || PN->getParent() != BB) return false; 901eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 902eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Degenerate case of a single entry PHI. 903eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PN->getNumIncomingValues() == 1) { 904eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PN->getIncomingValue(0) != PN) 905eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 906eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner else 907eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 908eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PN->eraseFromParent(); 909eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return true; 910eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 911eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 912eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Now we know that this block has multiple preds and two succs. 913eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 914eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // If this basic block contains anything other than the PHI and branch, bail 915eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // out. FIXME: improve this in the future. 916eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BasicBlock::iterator BBI = BB->begin(); 917eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (&*BBI != PN || &*++BBI != BI) 918eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return false; 919eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 920eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Okay, this is a simple enough basic block. See if any phi values are 921eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // constants. 922eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 923eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (ConstantBool *CB = dyn_cast<ConstantBool>(PN->getIncomingValue(i))) { 924eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Okay, we now know that all edges from PredBB should be revectored to 925eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // branch to RealDest. 926eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BasicBlock *PredBB = PN->getIncomingBlock(i); 927eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BasicBlock *RealDest = BI->getSuccessor(!CB->getValue()); 928eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 929eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // If there are PHI nodes in the destination block, we have to add an 930eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // entry for PredBB. Instead of being smart about this, just split the 931eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // critical edge, which will eliminate the PHI-ness. 932eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (isa<PHINode>(RealDest->begin())) { 933eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner SplitCriticalEdge(BI, !CB->getValue()); 934eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner RealDest = BI->getSuccessor(!CB->getValue()); 935eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 936eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner assert(!isa<PHINode>(RealDest->begin()) && "Crit edge split failure!"); 937eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 938eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Loop over all of the edges from PredBB to BB, changing them to branch 939eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // to RealDest instead. 940eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner TerminatorInst *PredBBTI = PredBB->getTerminator(); 941eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 942eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PredBBTI->getSuccessor(i) == BB) { 943eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BB->removePredecessor(PredBB); 944eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PredBBTI->setSuccessor(i, RealDest); 945eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 946eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 947eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner std::cerr << *BB; 948eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 949eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Recurse, simplifying any other constants. 950eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return FoldCondBranchOnPHI(BI) | true; 951eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 952eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 953eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return false; 954eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner} 955eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 956eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 9571654cff8e80acdddf5e5f2261595007878924aacChris Lattnernamespace { 9581654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// ConstantIntOrdering - This class implements a stable ordering of constant 9591654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// integers that does not depend on their address. This is important for 9601654cff8e80acdddf5e5f2261595007878924aacChris Lattner /// applications that sort ConstantInt's to ensure uniqueness. 9611654cff8e80acdddf5e5f2261595007878924aacChris Lattner struct ConstantIntOrdering { 9621654cff8e80acdddf5e5f2261595007878924aacChris Lattner bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 9631654cff8e80acdddf5e5f2261595007878924aacChris Lattner return LHS->getRawValue() < RHS->getRawValue(); 9641654cff8e80acdddf5e5f2261595007878924aacChris Lattner } 9651654cff8e80acdddf5e5f2261595007878924aacChris Lattner }; 9661654cff8e80acdddf5e5f2261595007878924aacChris Lattner} 9671654cff8e80acdddf5e5f2261595007878924aacChris Lattner 96801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// SimplifyCFG - This function is used to do simplification of a CFG. For 96901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// example, it adjusts branches to branches to eliminate the extra hop, it 97001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// eliminates unreachable basic blocks, and does other "peephole" optimization 971e2ca540e7c29703c3b943a96fed7e383c7bd35c0Chris Lattner// of the CFG. It returns true if a modification was made. 97201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 97301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// WARNING: The entry node of a function may not be simplified. 97401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner// 975f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerbool llvm::SimplifyCFG(BasicBlock *BB) { 976dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner bool Changed = false; 97701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner Function *M = BB->getParent(); 97801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 97901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB && BB->getParent() && "Block not embedded in function!"); 98001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB->getTerminator() && "Degenerate basic block encountered!"); 98118961504fc2b299578dba817900a0696cf3ccc4dChris Lattner assert(&BB->getParent()->front() != BB && "Can't Simplify entry block!"); 98201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 98301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove basic blocks that have no predecessors... which are unreachable. 984d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner if (pred_begin(BB) == pred_end(BB) || 985d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner *pred_begin(BB) == BB && ++pred_begin(BB) == pred_end(BB)) { 98630b434476796cd4a85c02914687d22f2e5ec95caChris Lattner DEBUG(std::cerr << "Removing BB: \n" << *BB); 98701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 98801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Loop through all of our successors and make sure they know that one 98901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // of their predecessors is going away. 990151c80be8180a7a0aa1594848699aa6b678b3998Chris Lattner for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) 991151c80be8180a7a0aa1594848699aa6b678b3998Chris Lattner SI->removePredecessor(BB); 99201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 99301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner while (!BB->empty()) { 99418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner Instruction &I = BB->back(); 99501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // If this instruction is used, replace uses with an arbitrary 996f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner // value. Because control flow can't get here, we don't care 997fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // what we replace the value with. Note that since this block is 99801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // unreachable, and all values contained within it must dominate their 99901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // uses, that all uses will eventually be removed. 1000fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman if (!I.use_empty()) 1001f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner // Make all users of this instruction use undef instead 1002f5e982daa8a83b4fcadccdf67b18889cfdcdf77dChris Lattner I.replaceAllUsesWith(UndefValue::get(I.getType())); 1003fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 100401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Remove the instruction from the basic block 100518961504fc2b299578dba817900a0696cf3ccc4dChris Lattner BB->getInstList().pop_back(); 100601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 100718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner M->getBasicBlockList().erase(BB); 100801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 100901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 101001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 1011694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // Check to see if we can constant propagate this terminator instruction 1012694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // away... 1013dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner Changed |= ConstantFoldTerminator(BB); 1014694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 101519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If this is a returning block with only PHI nodes in it, fold the return 101619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // instruction into any unconditional branch predecessors. 1017147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // 1018147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // If any predecessor is a conditional branch that just selects among 1019147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // different return values, fold the replace the branch/return with a select 1020147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // and return. 102119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 102219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BasicBlock::iterator BBI = BB->getTerminator(); 102319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BBI == BB->begin() || isa<PHINode>(--BBI)) { 1024147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Find predecessors that end with branches. 102519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner std::vector<BasicBlock*> UncondBranchPreds; 1026147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner std::vector<BranchInst*> CondBranchPreds; 102719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 102819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner TerminatorInst *PTI = (*PI)->getTerminator(); 102919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) 103019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BI->isUnconditional()) 103119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner UncondBranchPreds.push_back(*PI); 1032147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner else 1033147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner CondBranchPreds.push_back(BI); 103419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 1035fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 103619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we found some, do the transformation! 103719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (!UncondBranchPreds.empty()) { 103819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner while (!UncondBranchPreds.empty()) { 103919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BasicBlock *Pred = UncondBranchPreds.back(); 104019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner UncondBranchPreds.pop_back(); 104119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Instruction *UncondBranch = Pred->getTerminator(); 104219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Clone the return and add it to the end of the predecessor. 104319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Instruction *NewRet = RI->clone(); 104419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().push_back(NewRet); 104519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 104619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If the return instruction returns a value, and if the value was a 104719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // PHI node in "BB", propagate the right value into the return. 104819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (NewRet->getNumOperands() == 1) 104919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(NewRet->getOperand(0))) 105019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (PN->getParent() == BB) 105119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner NewRet->setOperand(0, PN->getIncomingValueForBlock(Pred)); 105219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Update any PHI nodes in the returning block to realize that we no 105319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // longer branch to them. 105419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BB->removePredecessor(Pred); 105519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().erase(UncondBranch); 105619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 105719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 105819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we eliminated all predecessors of the block, delete the block now. 105919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (pred_begin(BB) == pred_end(BB)) 106019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // We know there are no successors, so just nuke the block. 106119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner M->getBasicBlockList().erase(BB); 106219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 106319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner return true; 106419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 1065147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1066147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check out all of the conditional branches going to this return 1067147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // instruction. If any of them just select between returns, change the 1068147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // branch itself into a select/return pair. 1069147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner while (!CondBranchPreds.empty()) { 1070147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BranchInst *BI = CondBranchPreds.back(); 1071147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner CondBranchPreds.pop_back(); 1072147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *TrueSucc = BI->getSuccessor(0); 1073147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *FalseSucc = BI->getSuccessor(1); 1074147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock *OtherSucc = TrueSucc == BB ? FalseSucc : TrueSucc; 1075147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1076147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check to see if the non-BB successor is also a return block. 1077147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (isa<ReturnInst>(OtherSucc->getTerminator())) { 1078147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check to see if there are only PHI instructions in this block. 1079147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BasicBlock::iterator OSI = OtherSucc->getTerminator(); 1080147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (OSI == OtherSucc->begin() || isa<PHINode>(--OSI)) { 1081147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Okay, we found a branch that is going to two return nodes. If 1082147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // there is no return value for this function, just change the 1083147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // branch into a return. 1084147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (RI->getNumOperands() == 0) { 1085147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner TrueSucc->removePredecessor(BI->getParent()); 1086147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner FalseSucc->removePredecessor(BI->getParent()); 1087147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner new ReturnInst(0, BI); 1088147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BI->getParent()->getInstList().erase(BI); 1089147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner return true; 1090147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1091147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1092147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Otherwise, figure out what the true and false return values are 1093147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // so we can insert a new select instruction. 1094147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner Value *TrueValue = TrueSucc->getTerminator()->getOperand(0); 1095147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner Value *FalseValue = FalseSucc->getTerminator()->getOperand(0); 1096147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1097147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Unwrap any PHI nodes in the return blocks. 1098147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (PHINode *TVPN = dyn_cast<PHINode>(TrueValue)) 1099147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (TVPN->getParent() == TrueSucc) 1100147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1101147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (PHINode *FVPN = dyn_cast<PHINode>(FalseValue)) 1102147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner if (FVPN->getParent() == FalseSucc) 1103147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1104147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 11057aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner TrueSucc->removePredecessor(BI->getParent()); 11067aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner FalseSucc->removePredecessor(BI->getParent()); 11077aa773bc07fd6125c0e4a965760fa06c5679cc8dChris Lattner 1108147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Insert a new select instruction. 11090ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner Value *NewRetVal; 11100ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner Value *BrCond = BI->getCondition(); 11110ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (TrueValue != FalseValue) 11120ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner NewRetVal = new SelectInst(BrCond, TrueValue, 11130ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner FalseValue, "retval", BI); 11140ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner else 11150ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner NewRetVal = TrueValue; 11160ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner 1117147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner new ReturnInst(NewRetVal, BI); 1118147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner BI->getParent()->getInstList().erase(BI); 11190ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (BrCond->use_empty()) 11200ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner if (Instruction *BrCondI = dyn_cast<Instruction>(BrCond)) 11210ed7f42c1b6e6dab8b531d7f2fa45ed2fe310849Chris Lattner BrCondI->getParent()->getInstList().erase(BrCondI); 1122147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner return true; 1123147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1124147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 1125147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 112619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 1127e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->begin())) { 1128e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Check to see if the first instruction in this block is just an unwind. 1129e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // If so, replace any invoke instructions which use this as an exception 1130af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner // destination with call instructions, and any unconditional branch 1131af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner // predecessor with an unwind. 1132e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // 1133e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 1134e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner while (!Preds.empty()) { 1135e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner BasicBlock *Pred = Preds.back(); 1136af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) { 1137af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner if (BI->isUnconditional()) { 1138af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner Pred->getInstList().pop_back(); // nuke uncond branch 1139af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner new UnwindInst(Pred); // Use unwind. 1140af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner Changed = true; 1141af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner } 1142af17b1df84c31cb4f9a09213db9aa3c1e8b910eaChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 1143e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner if (II->getUnwindDest() == BB) { 1144e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Insert a new branch instruction before the invoke, because this 1145e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // is now a fall through... 1146e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner BranchInst *BI = new BranchInst(II->getNormalDest(), II); 1147e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Pred->getInstList().remove(II); // Take out of symbol table 1148fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1149e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Insert the call now... 1150e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 1151e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner CallInst *CI = new CallInst(II->getCalledValue(), Args, 1152e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner II->getName(), BI); 115316d0db2da8c274f98db4a89ca7a92f970d464b9aChris Lattner CI->setCallingConv(II->getCallingConv()); 1154e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // If the invoke produced a value, the Call now does instead 1155e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner II->replaceAllUsesWith(CI); 1156e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner delete II; 1157e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Changed = true; 1158e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 1159fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1160e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Preds.pop_back(); 1161e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 11628e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 11638e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // If this block is now dead, remove it. 11648e509dd5e81e92a466580ab4022994079952cca9Chris Lattner if (pred_begin(BB) == pred_end(BB)) { 11658e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // We know there are no successors, so just nuke the block. 11668e509dd5e81e92a466580ab4022994079952cca9Chris Lattner M->getBasicBlockList().erase(BB); 11678e509dd5e81e92a466580ab4022994079952cca9Chris Lattner return true; 11688e509dd5e81e92a466580ab4022994079952cca9Chris Lattner } 11698e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 1170623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1171623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (isValueEqualityComparison(SI)) { 1172623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we only have one predecessor, and if it is a branch on this value, 1173623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // see if that predecessor totally determines the outcome of this switch. 1174623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1175623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) 1176623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1177623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 1178623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If the block only contains the switch, see if we can fold the block 1179623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // away into any preds. 1180623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SI == &BB->front()) 1181623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (FoldValueComparisonIntoPredecessors(SI)) 1182623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1183623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 1184542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 11857e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (BI->isUnconditional()) { 11867e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BasicBlock::iterator BBI = BB->begin(); // Skip over phi nodes... 11877e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner while (isa<PHINode>(*BBI)) ++BBI; 11887e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 11897e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner BasicBlock *Succ = BI->getSuccessor(0); 11907e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (BBI->isTerminator() && // Terminator is the only non-phi instruction! 11917e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner Succ != BB) // Don't hurt infinite loops! 11927e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (TryToSimplifyUncondBranchFromEmptyBlock(BB, Succ)) 11937e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner return 1; 11947e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 11957e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } else { // Conditional branch 1196e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (Value *CompVal = isValueEqualityComparison(BI)) { 1197623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we only have one predecessor, and if it is a branch on this value, 1198623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // see if that predecessor totally determines the outcome of this 1199623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // switch. 1200623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1201623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) 1202623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1203623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 1204e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // This block must be empty, except for the setcond inst, if it exists. 1205e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock::iterator I = BB->begin(); 1206e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (&*I == BI || 1207e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner (&*I == cast<Instruction>(BI->getCondition()) && 1208e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner &*++I == BI)) 1209e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (FoldValueComparisonIntoPredecessors(BI)) 1210e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner return SimplifyCFG(BB) | true; 1211e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1212eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1213eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // If this is a branch on a phi node in the current block, thread control 1214eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // through this block if any PHI node entries are constants. 1215eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 1216eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PN->getParent() == BI->getParent()) 1217eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (FoldCondBranchOnPHI(BI)) 1218eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return SimplifyCFG(BB) | true; 1219eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1220e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 1221e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // If this basic block is ONLY a setcc and a branch, and if a predecessor 1222e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // branches to us and one of our successors, fold the setcc into the 1223e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // predecessor and use logical operations to pick the right destination. 122412fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner BasicBlock *TrueDest = BI->getSuccessor(0); 122512fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner BasicBlock *FalseDest = BI->getSuccessor(1); 1226bdcc0b8c55041ff89b59f0ea2cdbc2ac02f26a3dChris Lattner if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(BI->getCondition())) 1227e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (Cond->getParent() == BB && &BB->front() == Cond && 122812fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner Cond->getNext() == BI && Cond->hasOneUse() && 122912fe2b1b82fe825d023f40a98931381e84fbc9d3Chris Lattner TrueDest != BB && FalseDest != BB) 1230e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI!=E; ++PI) 1231e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1232a1f79fb08b92801d4ab3cb32fe0bd9d12dfb3954Chris Lattner if (PBI->isConditional() && SafeToMergeTerminators(BI, PBI)) { 12332636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner BasicBlock *PredBlock = *PI; 1234e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == FalseDest || 1235e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(1) == TrueDest) { 1236e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // Invert the predecessors condition test (xor it with true), 1237e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // which allows us to write this code once. 1238e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Value *NewCond = 1239e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BinaryOperator::createNot(PBI->getCondition(), 1240e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getCondition()->getName()+".not", PBI); 1241e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setCondition(NewCond); 1242e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock *OldTrue = PBI->getSuccessor(0); 1243e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock *OldFalse = PBI->getSuccessor(1); 1244e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(0, OldFalse); 1245e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(1, OldTrue); 1246e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1247e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 1248e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == TrueDest || 1249e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(1) == FalseDest) { 12502636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner // Clone Cond into the predecessor basic block, and or/and the 1251e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // two conditions together. 1252e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction *New = Cond->clone(); 1253e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner New->setName(Cond->getName()); 1254e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Cond->setName(Cond->getName()+".old"); 12552636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner PredBlock->getInstList().insert(PBI, New); 1256e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction::BinaryOps Opcode = 1257e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->getSuccessor(0) == TrueDest ? 1258e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner Instruction::Or : Instruction::And; 1259fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman Value *NewCond = 1260e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BinaryOperator::create(Opcode, PBI->getCondition(), 1261e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner New, "bothcond", PBI); 1262e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setCondition(NewCond); 1263e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(0) == BB) { 12642636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner AddPredecessorToBlock(TrueDest, PredBlock, BB); 1265e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(0, TrueDest); 1266e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1267e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (PBI->getSuccessor(1) == BB) { 12682636c1be17c384993c25e9fe1e61a76cee157aa1Chris Lattner AddPredecessorToBlock(FalseDest, PredBlock, BB); 1269e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner PBI->setSuccessor(1, FalseDest); 1270e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1271e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner return SimplifyCFG(BB) | 1; 1272e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1273e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1274e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 127592da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // If this block ends with a branch instruction, and if there is one 127692da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // predecessor, see if the previous block ended with a branch on the same 127792da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // condition, which makes this conditional branch redundant. 12787e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 127992da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner if (BranchInst *PBI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 128092da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner if (PBI->isConditional() && 128192da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner PBI->getCondition() == BI->getCondition() && 1282951fdb9764ea7abd1f409712636cf80a86140d90Chris Lattner (PBI->getSuccessor(0) != BB || PBI->getSuccessor(1) != BB)) { 128392da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // Okay, the outcome of this conditional branch is statically 128492da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // knowable. Delete the outgoing CFG edge that is impossible to 128592da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner // execute. 128692da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner bool CondIsTrue = PBI->getSuccessor(0) == BB; 128792da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner BI->getSuccessor(CondIsTrue)->removePredecessor(BB); 128892da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner new BranchInst(BI->getSuccessor(!CondIsTrue), BB); 128992da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner BB->getInstList().erase(BI); 129092da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner return SimplifyCFG(BB) | true; 129192da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner } 1292d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner } 1293698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (isa<UnreachableInst>(BB->getTerminator())) { 1294698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If there are any instructions immediately before the unreachable that can 1295698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // be removed, do so. 1296698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Instruction *Unreachable = BB->getTerminator(); 1297698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner while (Unreachable != BB->begin()) { 1298698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock::iterator BBI = Unreachable; 1299698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --BBI; 1300698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (isa<CallInst>(BBI)) break; 1301698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Delete this instruction 1302698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BB->getInstList().erase(BBI); 1303698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1304698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1305698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1306698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the unreachable instruction is the first in the block, take a gander 1307698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // at all of the predecessors of this instruction, and simplify them. 1308698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (&BB->front() == Unreachable) { 1309698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::vector<BasicBlock*> Preds(pred_begin(BB), pred_end(BB)); 1310698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 1311698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TerminatorInst *TI = Preds[i]->getTerminator(); 1312698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1313698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1314698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->isUnconditional()) { 1315698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 1316698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new UnreachableInst(TI); 1317698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TI->eraseFromParent(); 1318698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1319698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1320698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else { 1321698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 1322698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new BranchInst(BI->getSuccessor(1), BI); 1323698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BI->eraseFromParent(); 1324698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (BI->getSuccessor(1) == BB) { 1325698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner new BranchInst(BI->getSuccessor(0), BI); 1326698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BI->eraseFromParent(); 1327698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1328698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1329698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1330698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1331698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1332698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == BB) { 133342eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner BB->removePredecessor(SI->getParent()); 1334698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1335698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1336698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1337698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1338698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the default value is unreachable, figure out the most popular 1339698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // destination and make it the default. 1340698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(0) == BB) { 1341698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::map<BasicBlock*, unsigned> Popularity; 1342698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1343698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Popularity[SI->getSuccessor(i)]++; 1344698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1345698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Find the most popular block. 1346698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner unsigned MaxPop = 0; 1347698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock *MaxBlock = 0; 1348698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (std::map<BasicBlock*, unsigned>::iterator 1349698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 1350698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (I->second > MaxPop) { 1351698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxPop = I->second; 1352698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxBlock = I->first; 1353698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1354698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1355698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (MaxBlock) { 1356698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Make this the new default, allowing us to delete any explicit 1357698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // edges to it. 1358698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->setSuccessor(0, MaxBlock); 1359698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1360698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 136142eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 136242eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner // it. 136342eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner if (isa<PHINode>(MaxBlock->begin())) 136442eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner for (unsigned i = 0; i != MaxPop-1; ++i) 136542eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner MaxBlock->removePredecessor(SI->getParent()); 136642eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner 1367698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1368698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == MaxBlock) { 1369698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1370698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1371698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1372698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1373698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1374698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 1375698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (II->getUnwindDest() == BB) { 1376698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Convert the invoke to a call instruction. This would be a good 1377698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // place to note that the call does not throw though. 1378698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BranchInst *BI = new BranchInst(II->getNormalDest(), II); 1379698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->removeFromParent(); // Take out of symbol table 1380fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1381698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Insert the call now... 1382698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::vector<Value*> Args(II->op_begin()+3, II->op_end()); 1383698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner CallInst *CI = new CallInst(II->getCalledValue(), Args, 1384698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->getName(), BI); 138516d0db2da8c274f98db4a89ca7a92f970d464b9aChris Lattner CI->setCallingConv(II->getCallingConv()); 1386698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the invoke produced a value, the Call does now instead. 1387698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->replaceAllUsesWith(CI); 1388698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner delete II; 1389698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1390698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1391698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1392698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1393698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1394698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If this block is now dead, remove it. 1395698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (pred_begin(BB) == pred_end(BB)) { 1396698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // We know there are no successors, so just nuke the block. 1397698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner M->getBasicBlockList().erase(BB); 1398698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner return true; 1399698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1400698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 140119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 140219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 140301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Merge basic blocks into their predecessor if there is only one distinct 140401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // pred, and if there is only one distinct successor of the predecessor, and 140501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // if there are no PHI nodes. 140601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 14072355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 14082355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BasicBlock *OnlyPred = *PI++; 14092355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 14102355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (*PI != OnlyPred) { 14112355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred = 0; // There are multiple different predecessors... 14122355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner break; 14132355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 141492da2c2053feda379726f34b227ca6ac3bcdaab4Chris Lattner 14152355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BasicBlock *OnlySucc = 0; 14162355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (OnlyPred && OnlyPred != BB && // Don't break self loops 14172355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getTerminator()->getOpcode() != Instruction::Invoke) { 14182355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Check to see if there is only one distinct successor... 14192355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner succ_iterator SI(succ_begin(OnlyPred)), SE(succ_end(OnlyPred)); 14202355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlySucc = BB; 14212355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner for (; SI != SE; ++SI) 14222355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (*SI != OnlySucc) { 14232355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlySucc = 0; // There are multiple distinct successors! 142401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner break; 142501d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 14262355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 142701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 14282355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (OnlySucc) { 142930b434476796cd4a85c02914687d22f2e5ec95caChris Lattner DEBUG(std::cerr << "Merging: " << *BB << "into: " << *OnlyPred); 14302355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner TerminatorInst *Term = OnlyPred->getTerminator(); 143101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 14322355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Resolve any PHI nodes at the start of the block. They are all 14332355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // guaranteed to have exactly one entry if they exist, unless there are 14342355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // multiple duplicate (but guaranteed to be equal) entries for the 14352355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // incoming edges. This occurs when there are multiple edges from 14362355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // OnlyPred to OnlySucc. 14372355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // 14382355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) { 14392355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 14402355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BB->getInstList().pop_front(); // Delete the phi node... 14412355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 144291b65c0b42b3d5dece246bdb366441d6f5593396Chris Lattner 14432355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Delete the unconditional branch from the predecessor... 14442355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getInstList().pop_back(); 1445fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 14462355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Move all definitions in the successor to the predecessor... 14472355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList()); 1448fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 14492355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Make all PHI nodes that referred to BB now refer to Pred as their 14502355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // source... 14512355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BB->replaceAllUsesWith(OnlyPred); 145218961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 14532355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner std::string OldName = BB->getName(); 145418961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 1455fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // Erase basic block from the function... 14562355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner M->getBasicBlockList().erase(BB); 145718961504fc2b299578dba817900a0696cf3ccc4dChris Lattner 14582355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner // Inherit predecessors name if it exists... 14592355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (!OldName.empty() && !OnlyPred->hasName()) 14602355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred->setName(OldName); 1461fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 14622355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner return true; 146301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 1464723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 146537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Otherwise, if this block only has a single predecessor, and if that block 146637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // is a conditional branch, see if we can hoist any code from this block up 146737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // into our predecessor. 146837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (OnlyPred) 14697613437db954abafd1230c961e87872df5721957Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 14707613437db954abafd1230c961e87872df5721957Chris Lattner if (BI->isConditional()) { 14717613437db954abafd1230c961e87872df5721957Chris Lattner // Get the other block. 14727613437db954abafd1230c961e87872df5721957Chris Lattner BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); 14737613437db954abafd1230c961e87872df5721957Chris Lattner PI = pred_begin(OtherBB); 14747613437db954abafd1230c961e87872df5721957Chris Lattner ++PI; 14757613437db954abafd1230c961e87872df5721957Chris Lattner if (PI == pred_end(OtherBB)) { 14767613437db954abafd1230c961e87872df5721957Chris Lattner // We have a conditional branch to two blocks that are only reachable 14777613437db954abafd1230c961e87872df5721957Chris Lattner // from the condbr. We know that the condbr dominates the two blocks, 14787613437db954abafd1230c961e87872df5721957Chris Lattner // so see if there is any identical code in the "then" and "else" 14797613437db954abafd1230c961e87872df5721957Chris Lattner // blocks. If so, we can hoist it up to the branching block. 14807613437db954abafd1230c961e87872df5721957Chris Lattner Changed |= HoistThenElseCodeToIf(BI); 14817613437db954abafd1230c961e87872df5721957Chris Lattner } 148237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 148337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 14840d56008f53587531718ec36af82cc24576580b36Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 14850d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 14860d56008f53587531718ec36af82cc24576580b36Chris Lattner // Change br (X == 0 | X == 1), T, F into a switch instruction. 14870d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 14880d56008f53587531718ec36af82cc24576580b36Chris Lattner Instruction *Cond = cast<Instruction>(BI->getCondition()); 14890d56008f53587531718ec36af82cc24576580b36Chris Lattner // If this is a bunch of seteq's or'd together, or if it's a bunch of 14900d56008f53587531718ec36af82cc24576580b36Chris Lattner // 'setne's and'ed together, collect them. 14910d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *CompVal = 0; 14921654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::vector<ConstantInt*> Values; 14930d56008f53587531718ec36af82cc24576580b36Chris Lattner bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 14940d56008f53587531718ec36af82cc24576580b36Chris Lattner if (CompVal && CompVal->getType()->isInteger()) { 14950d56008f53587531718ec36af82cc24576580b36Chris Lattner // There might be duplicate constants in the list, which the switch 14960d56008f53587531718ec36af82cc24576580b36Chris Lattner // instruction can't handle, remove them now. 14971654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 14980d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 1499fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 15000d56008f53587531718ec36af82cc24576580b36Chris Lattner // Figure out which block is which destination. 15010d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *DefaultBB = BI->getSuccessor(1); 15020d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *EdgeBB = BI->getSuccessor(0); 15030d56008f53587531718ec36af82cc24576580b36Chris Lattner if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 1504fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 15050d56008f53587531718ec36af82cc24576580b36Chris Lattner // Create the new switch instruction now. 1506378805969ea928b91aa321746031a8f51667a783Chris Lattner SwitchInst *New = new SwitchInst(CompVal, DefaultBB,Values.size(),BI); 1507fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 15080d56008f53587531718ec36af82cc24576580b36Chris Lattner // Add all of the 'cases' to the switch instruction. 15090d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size(); i != e; ++i) 15100d56008f53587531718ec36af82cc24576580b36Chris Lattner New->addCase(Values[i], EdgeBB); 1511fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 15120d56008f53587531718ec36af82cc24576580b36Chris Lattner // We added edges from PI to the EdgeBB. As such, if there were any 15130d56008f53587531718ec36af82cc24576580b36Chris Lattner // PHI nodes in EdgeBB, they need entries to be added corresponding to 15140d56008f53587531718ec36af82cc24576580b36Chris Lattner // the number of edges added. 15150d56008f53587531718ec36af82cc24576580b36Chris Lattner for (BasicBlock::iterator BBI = EdgeBB->begin(); 15162da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer isa<PHINode>(BBI); ++BBI) { 15172da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(BBI); 15180d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *InVal = PN->getIncomingValueForBlock(*PI); 15190d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 15200d56008f53587531718ec36af82cc24576580b36Chris Lattner PN->addIncoming(InVal, *PI); 15210d56008f53587531718ec36af82cc24576580b36Chris Lattner } 15220d56008f53587531718ec36af82cc24576580b36Chris Lattner 15230d56008f53587531718ec36af82cc24576580b36Chris Lattner // Erase the old branch instruction. 15240d56008f53587531718ec36af82cc24576580b36Chris Lattner (*PI)->getInstList().erase(BI); 15250d56008f53587531718ec36af82cc24576580b36Chris Lattner 15260d56008f53587531718ec36af82cc24576580b36Chris Lattner // Erase the potentially condition tree that was used to computed the 15270d56008f53587531718ec36af82cc24576580b36Chris Lattner // branch condition. 15280d56008f53587531718ec36af82cc24576580b36Chris Lattner ErasePossiblyDeadInstructionTree(Cond); 15290d56008f53587531718ec36af82cc24576580b36Chris Lattner return true; 15300d56008f53587531718ec36af82cc24576580b36Chris Lattner } 15310d56008f53587531718ec36af82cc24576580b36Chris Lattner } 15320d56008f53587531718ec36af82cc24576580b36Chris Lattner 1533723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If there is a trivial two-entry PHI node in this basic block, and we can 1534723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // eliminate it, do so now. 1535723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 1536723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (PN->getNumIncomingValues() == 2) { 1537723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1538723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // statement", which has a very simple dominance structure. Basically, we 1539723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // are trying to find the condition that is being branched on, which 1540723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // subsequently causes this merge to happen. We really want control 1541723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // dependence information for this check, but simplifycfg can't keep it up 1542723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // to date, and this catches most of the cases we care about anyway. 1543723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // 1544723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *IfTrue, *IfFalse; 1545723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse)) { 1546218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner DEBUG(std::cerr << "FOUND IF CONDITION! " << *IfCond << " T: " 1547218a8223e62c41ae6318e28e8f4c672fcfbb5082Chris Lattner << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1548723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 15499c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Loop over the PHI's seeing if we can promote them all to select 15509c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // instructions. While we are at it, keep track of the instructions 15519c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // that need to be moved to the dominating block. 15529c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner std::set<Instruction*> AggressiveInsts; 15539c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner bool CanPromote = true; 15549c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 1555723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock::iterator AfterPHIIt = BB->begin(); 15569c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner while (isa<PHINode>(AfterPHIIt)) { 15579c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner PHINode *PN = cast<PHINode>(AfterPHIIt++); 15580289929c6212229980c9057853860ccfd3f81678Chris Lattner if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) { 15590289929c6212229980c9057853860ccfd3f81678Chris Lattner if (PN->getIncomingValue(0) != PN) 15600289929c6212229980c9057853860ccfd3f81678Chris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 15610289929c6212229980c9057853860ccfd3f81678Chris Lattner else 15620289929c6212229980c9057853860ccfd3f81678Chris Lattner PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 15630289929c6212229980c9057853860ccfd3f81678Chris Lattner } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 15640289929c6212229980c9057853860ccfd3f81678Chris Lattner &AggressiveInsts) || 15650289929c6212229980c9057853860ccfd3f81678Chris Lattner !DominatesMergePoint(PN->getIncomingValue(1), BB, 15660289929c6212229980c9057853860ccfd3f81678Chris Lattner &AggressiveInsts)) { 15679c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote = false; 15689c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner break; 15699c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 15709c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 1571723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 15729c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Did we eliminate all PHI's? 15739c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote |= AfterPHIIt == BB->begin(); 15749c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 15759c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // If we all PHI nodes are promotable, check to make sure that all 15769c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // instructions in the predecessor blocks can be promoted as well. If 15779c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // not, we won't be able to get rid of the control flow, so it's not 15789c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // worth promoting to select instructions. 15794e073a871b208a2c9dfa004b3a93fb26f96daa17Reid Spencer BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 15809c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (CanPromote) { 15819c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner PN = cast<PHINode>(BB->begin()); 15829c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner BasicBlock *Pred = PN->getIncomingBlock(0); 15839c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 15849c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1 = Pred; 15859c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock = *pred_begin(Pred); 15869c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner for (BasicBlock::iterator I = Pred->begin(); 15879c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner !isa<TerminatorInst>(I); ++I) 15889c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!AggressiveInsts.count(I)) { 15899c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // This is not an aggressive instruction that we can promote. 15909c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Because of this, we won't be able to get rid of the control 15919c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // flow, so the xform is not worth it. 15929c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote = false; 15939c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner break; 15949c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 15959c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 15969c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 15979c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner Pred = PN->getIncomingBlock(1); 1598fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman if (CanPromote && 15999c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 16009c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2 = Pred; 16019c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock = *pred_begin(Pred); 16029c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner for (BasicBlock::iterator I = Pred->begin(); 16039c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner !isa<TerminatorInst>(I); ++I) 16049c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!AggressiveInsts.count(I)) { 16059c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // This is not an aggressive instruction that we can promote. 16069c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Because of this, we won't be able to get rid of the control 16079c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // flow, so the xform is not worth it. 16089c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner CanPromote = false; 16099c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner break; 16109c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 16119c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 16129c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 16139c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 16149c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // If we can still promote the PHI nodes after this gauntlet of tests, 16159c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // do all of the PHI's now. 16169c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (CanPromote) { 16179c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Move all 'aggressive' instructions, which are defined in the 16189c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // conditional parts of the if's up to the dominating block. 16199c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (IfBlock1) { 16209c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 16219c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1->getInstList(), 16229c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1->begin(), 16239c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock1->getTerminator()); 16249c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 16259c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (IfBlock2) { 16269c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 16279c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2->getInstList(), 16289c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2->begin(), 16299c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner IfBlock2->getTerminator()); 16309c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner } 16319c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner 16329c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 16339c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Change the PHI node into a select instruction. 1634723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Value *TrueVal = 1635723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1636723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Value *FalseVal = 1637723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1638723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 1639552112f2f8702f2cba8cb5775bc24c3e02ba265cChris Lattner std::string Name = PN->getName(); PN->setName(""); 1640552112f2f8702f2cba8cb5775bc24c3e02ba265cChris Lattner PN->replaceAllUsesWith(new SelectInst(IfCond, TrueVal, FalseVal, 16419c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner Name, AfterPHIIt)); 1642552112f2f8702f2cba8cb5775bc24c3e02ba265cChris Lattner BB->getInstList().erase(PN); 1643723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 16449c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner Changed = true; 1645723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 1646723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 1647723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 1648fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1649694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner return Changed; 165001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 1651