SimplifyCFG.cpp revision b0bc6c361da9009e8414efde317d9bbff755f6c0
101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 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" 18383d7ed9158576aef5cde872548225a17e3c0155Devang Patel#include "llvm/IntrinsicInst.h" 190d56008f53587531718ec36af82cc24576580b36Chris Lattner#include "llvm/Type.h" 20c10305743c313558405079452138f03124e87581Reid Spencer#include "llvm/DerivedTypes.h" 21f8bc3008214c8327ff987573a111fc0dcefb7d25Dale Johannesen#include "llvm/GlobalVariable.h" 2201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include "llvm/Support/CFG.h" 23551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 24ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 2579066fa6acce02c97c714a5a6e151ed8a249721cChris Lattner#include "llvm/Analysis/ConstantFolding.h" 2658e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen#include "llvm/Target/TargetData.h" 27eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner#include "llvm/Transforms/Utils/BasicBlockUtils.h" 282c63566e406974caa70ee27f35af28112e80f951Dan Gohman#include "llvm/ADT/DenseMap.h" 2993e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner#include "llvm/ADT/SmallVector.h" 30c9951231822215d6aea7a9b50947c18d8d745609Chris Lattner#include "llvm/ADT/SmallPtrSet.h" 31502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng#include "llvm/ADT/Statistic.h" 3201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <algorithm> 3301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner#include <functional> 34d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner#include <set> 35698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner#include <map> 36f7703df4968084c18c248c1feea9961c19a32e6aChris Lattnerusing namespace llvm; 37d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 38502a4f5162498ec420e3cb22f667808d726dd7daEvan ChengSTATISTIC(NumSpeculations, "Number of speculative executed instructions"); 39502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng 4058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesennamespace { 4158e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesenclass SimplifyCFGOpt { 4258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen const TargetData *const TD; 4358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen 4458e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen ConstantInt *GetConstantInt(Value *V); 4558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values); 4658e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values); 4758e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 4858e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen std::vector<ConstantInt*> &Values); 4958e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen Value *isValueEqualityComparison(TerminatorInst *TI); 5058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI, 5158e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases); 5258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 5358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen BasicBlock *Pred); 5458e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI); 5558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen 5658e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesenpublic: 5758e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen explicit SimplifyCFGOpt(const TargetData *td) : TD(td) {} 5858e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen bool run(BasicBlock *BB); 5958e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen}; 6058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen} 6158e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen 622bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// SafeToMergeTerminators - Return true if it is safe to merge these two 632bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// terminator instructions together. 642bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// 652bdcb56146279009f233933a101cb3dd54a951cdChris Lattnerstatic bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 662bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (SI1 == SI2) return false; // Can't merge with self! 672bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 682bdcb56146279009f233933a101cb3dd54a951cdChris Lattner // It is not safe to merge these two switch instructions if they have a common 692bdcb56146279009f233933a101cb3dd54a951cdChris Lattner // successor, and if that successor has a PHI node, and if *that* PHI node has 702bdcb56146279009f233933a101cb3dd54a951cdChris Lattner // conflicting incoming values from the two switch blocks. 712bdcb56146279009f233933a101cb3dd54a951cdChris Lattner BasicBlock *SI1BB = SI1->getParent(); 722bdcb56146279009f233933a101cb3dd54a951cdChris Lattner BasicBlock *SI2BB = SI2->getParent(); 73c9951231822215d6aea7a9b50947c18d8d745609Chris Lattner SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 742bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 752bdcb56146279009f233933a101cb3dd54a951cdChris Lattner for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 762bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (SI1Succs.count(*I)) 772bdcb56146279009f233933a101cb3dd54a951cdChris Lattner for (BasicBlock::iterator BBI = (*I)->begin(); 782bdcb56146279009f233933a101cb3dd54a951cdChris Lattner isa<PHINode>(BBI); ++BBI) { 792bdcb56146279009f233933a101cb3dd54a951cdChris Lattner PHINode *PN = cast<PHINode>(BBI); 802bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (PN->getIncomingValueForBlock(SI1BB) != 812bdcb56146279009f233933a101cb3dd54a951cdChris Lattner PN->getIncomingValueForBlock(SI2BB)) 822bdcb56146279009f233933a101cb3dd54a951cdChris Lattner return false; 832bdcb56146279009f233933a101cb3dd54a951cdChris Lattner } 842bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 852bdcb56146279009f233933a101cb3dd54a951cdChris Lattner return true; 862bdcb56146279009f233933a101cb3dd54a951cdChris Lattner} 872bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 882bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 892bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// now be entries in it from the 'NewPred' block. The values that will be 902bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// flowing into the PHI nodes will be the same as those coming in from 912bdcb56146279009f233933a101cb3dd54a951cdChris Lattner/// ExistPred, an existing predecessor of Succ. 922bdcb56146279009f233933a101cb3dd54a951cdChris Lattnerstatic void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 932bdcb56146279009f233933a101cb3dd54a951cdChris Lattner BasicBlock *ExistPred) { 942bdcb56146279009f233933a101cb3dd54a951cdChris Lattner assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 952bdcb56146279009f233933a101cb3dd54a951cdChris Lattner succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 962bdcb56146279009f233933a101cb3dd54a951cdChris Lattner if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 972bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 98093a4385027235459ab6972b2e2fdc79061773cfChris Lattner PHINode *PN; 99093a4385027235459ab6972b2e2fdc79061773cfChris Lattner for (BasicBlock::iterator I = Succ->begin(); 100093a4385027235459ab6972b2e2fdc79061773cfChris Lattner (PN = dyn_cast<PHINode>(I)); ++I) 101093a4385027235459ab6972b2e2fdc79061773cfChris Lattner PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); 1022bdcb56146279009f233933a101cb3dd54a951cdChris Lattner} 1032bdcb56146279009f233933a101cb3dd54a951cdChris Lattner 1047e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 105723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// GetIfCondition - Given a basic block (BB) with two predecessors (and 106723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// presumably PHI nodes in it), check to see if the merge at this block is due 107723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// to an "if condition". If so, return the boolean condition that determines 108723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// which entry into BB will be taken. Also, return by references the block 109723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// that will be entered from if the condition is true, and the block that will 110723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// be entered if the condition is false. 111fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman/// 112723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner/// 113723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattnerstatic Value *GetIfCondition(BasicBlock *BB, 114723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 115723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 116723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner "Function can only handle blocks with 2 predecessors!"); 117723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *Pred1 = *pred_begin(BB); 118723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *Pred2 = *++pred_begin(BB); 119723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 120723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // We can only handle branches. Other control flow will be lowered to 121723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // branches if possible anyway. 122723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (!isa<BranchInst>(Pred1->getTerminator()) || 123723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner !isa<BranchInst>(Pred2->getTerminator())) 124723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 125723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 126723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 127723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 128723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Eliminate code duplication by ensuring that Pred1Br is conditional if 129723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // either are. 130723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred2Br->isConditional()) { 131723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If both branches are conditional, we don't have an "if statement". In 132723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // reality, we could transform this case, but since the condition will be 133723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // required anyway, we stand no chance of eliminating it, so the xform is 134723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // probably not profitable. 135723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->isConditional()) 136723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 137723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 138723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner std::swap(Pred1, Pred2); 139723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner std::swap(Pred1Br, Pred2Br); 140723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 141723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 142723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->isConditional()) { 143723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // If we found a conditional branch predecessor, make sure that it branches 144723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 145723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (Pred1Br->getSuccessor(0) == BB && 146723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Pred1Br->getSuccessor(1) == Pred2) { 147723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred1; 148723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred2; 149723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else if (Pred1Br->getSuccessor(0) == Pred2 && 150723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner Pred1Br->getSuccessor(1) == BB) { 151723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred2; 152723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred1; 153723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else { 154723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // We know that one arm of the conditional goes to BB, so the other must 155723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // go somewhere unrelated, and this must not be an "if statement". 156723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 157723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 158723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 159723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // The only thing we have to watch out for here is to make sure that Pred2 160723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // doesn't have incoming edges from other blocks. If it does, the condition 161723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // doesn't dominate BB. 162723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (++pred_begin(Pred2) != pred_end(Pred2)) 163723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 164723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 165723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return Pred1Br->getCondition(); 166723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 167723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 168723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Ok, if we got here, both predecessors end with an unconditional branch to 169723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // BB. Don't panic! If both blocks only have a single (identical) 170723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // predecessor, and THAT is a conditional branch, then we're all ok! 171723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (pred_begin(Pred1) == pred_end(Pred1) || 172723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner ++pred_begin(Pred1) != pred_end(Pred1) || 173723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner pred_begin(Pred2) == pred_end(Pred2) || 174723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner ++pred_begin(Pred2) != pred_end(Pred2) || 175723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner *pred_begin(Pred1) != *pred_begin(Pred2)) 176723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 177723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 178723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner // Otherwise, if this is a conditional branch, then we can use it! 179723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner BasicBlock *CommonPred = *pred_begin(Pred1); 180723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 181723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner assert(BI->isConditional() && "Two successors but not conditional?"); 182723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner if (BI->getSuccessor(0) == Pred1) { 183723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred1; 184723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred2; 185723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } else { 186723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfTrue = Pred2; 187723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner IfFalse = Pred1; 188723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 189723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return BI->getCondition(); 190723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner } 191723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return 0; 192723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner} 193723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 1945049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// DominatesMergePoint - If we have a merge point of an "if condition" as 1955049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// accepted above, return true if the specified value dominates the block. We 1965049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// don't handle the true generality of domination here, just a special case 1975049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// which works well enough for us. 1985049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// 1995049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 2005049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// see if V (which must be an instruction) is cheap to compute and is 2015049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// non-trapping. If both are true, the instruction is inserted into the set 2025049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// and true is returned. 2039c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattnerstatic bool DominatesMergePoint(Value *V, BasicBlock *BB, 2049c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner std::set<Instruction*> *AggressiveInsts) { 205570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner Instruction *I = dyn_cast<Instruction>(V); 206b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner if (!I) { 207b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner // Non-instructions all dominate instructions, but not all constantexprs 208b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner // can be executed unconditionally. 209b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner if (ConstantExpr *C = dyn_cast<ConstantExpr>(V)) 210b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner if (C->canTrap()) 211b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner return false; 212b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner return true; 213b74b1816305affe25da32c2f29532df41a23cd55Chris Lattner } 214570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner BasicBlock *PBB = I->getParent(); 215570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 216da895d63377b421dc50117befb2bec80d2973526Chris Lattner // We don't want to allow weird loops that might have the "if condition" in 217570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // the bottom of this block. 218570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (PBB == BB) return false; 219570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner 220570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // If this instruction is defined in a block that contains an unconditional 221570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // branch to BB, then it must be in the 'conditional' part of the "if 222570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // statement". 223570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator())) 224570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { 2259c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner if (!AggressiveInsts) return false; 226570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Okay, it looks like the instruction IS in the "condition". Check to 227570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // see if its a cheap instruction to unconditionally compute, and if it 228570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // only uses stuff defined outside of the condition. If so, hoist it out. 2290b79a7727d68a507837e827803859424cf3d997bEli Friedman if (!I->isSafeToSpeculativelyExecute()) 2300b79a7727d68a507837e827803859424cf3d997bEli Friedman return false; 2310b79a7727d68a507837e827803859424cf3d997bEli Friedman 232570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner switch (I->getOpcode()) { 233570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner default: return false; // Cannot hoist this out safely. 2343a56d146413ee344b10bbcb2b7d8dffaadc9fadeDale Johannesen case Instruction::Load: { 2350b79a7727d68a507837e827803859424cf3d997bEli Friedman // We have to check to make sure there are no instructions before the 2360b79a7727d68a507837e827803859424cf3d997bEli Friedman // load in its basic block, as we are going to hoist the loop out to 2370b79a7727d68a507837e827803859424cf3d997bEli Friedman // its predecessor. 2383a56d146413ee344b10bbcb2b7d8dffaadc9fadeDale Johannesen BasicBlock::iterator IP = PBB->begin(); 2393a56d146413ee344b10bbcb2b7d8dffaadc9fadeDale Johannesen while (isa<DbgInfoIntrinsic>(IP)) 2403a56d146413ee344b10bbcb2b7d8dffaadc9fadeDale Johannesen IP++; 2413a56d146413ee344b10bbcb2b7d8dffaadc9fadeDale Johannesen if (IP != BasicBlock::iterator(I)) 242570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 243570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner break; 2443a56d146413ee344b10bbcb2b7d8dffaadc9fadeDale Johannesen } 245570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Add: 246570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Sub: 247570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::And: 248570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Or: 249570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Xor: 250570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner case Instruction::Shl: 2513822ff5c71478c7c90a50ca57045fb676fcb5005Reid Spencer case Instruction::LShr: 2523822ff5c71478c7c90a50ca57045fb676fcb5005Reid Spencer case Instruction::AShr: 253e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer case Instruction::ICmp: 254570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner break; // These are all cheap and non-trapping instructions. 255570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner } 256fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 257570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // Okay, we can only really hoist these out if their operands are not 258570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner // defined in the conditional region. 259f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) 260f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif if (!DominatesMergePoint(*i, BB, 0)) 261570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner return false; 2629c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner // Okay, it's safe to do this! Remember this instruction. 2639c07866ef861e072395306e9811c329c7fe5bbe8Chris Lattner AggressiveInsts->insert(I); 264570751c2a7d8851bc61e408746a903b0253d2d21Chris Lattner } 265723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner 266723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner return true; 267723c66d4c0aa081ea8fa221617c5097e31333e6cChris Lattner} 26801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 26958e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen/// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr 27058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen/// and PointerNullValue. Return NULL if value is not a constant int. 27158e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund OlesenConstantInt *SimplifyCFGOpt::GetConstantInt(Value *V) { 27258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen // Normal constant int. 27358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen ConstantInt *CI = dyn_cast<ConstantInt>(V); 27458e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (CI || !TD || !isa<Constant>(V) || !isa<PointerType>(V->getType())) 27558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen return CI; 27658e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen 27758e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen // This is some kind of pointer constant. Turn it into a pointer-sized 27858e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen // ConstantInt if possible. 27958e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen const IntegerType *PtrTy = TD->getIntPtrType(V->getContext()); 28058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen 28158e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*). 28258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (isa<ConstantPointerNull>(V)) 28358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen return ConstantInt::get(PtrTy, 0); 28458e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen 28558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen // IntToPtr const int. 28658e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 28758e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (CE->getOpcode() == Instruction::IntToPtr) 28858e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) { 28958e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen // The constant is very likely to have the right type already. 29058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (CI->getType() == PtrTy) 29158e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen return CI; 29258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen else 29358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen return cast<ConstantInt> 29458e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false)); 29558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen } 29658e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen return 0; 29758e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen} 29858e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen 2995049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// GatherConstantSetEQs - Given a potentially 'or'd together collection of 3005049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// icmp_eq instructions that compare a value against a constant, return the 3015049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// value being compared, and stick the constant into the Values vector. 30258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund OlesenValue *SimplifyCFGOpt:: 30358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund OlesenGatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values) { 30407e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov if (Instruction *Inst = dyn_cast<Instruction>(V)) { 305e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if (Inst->getOpcode() == Instruction::ICmp && 306e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer cast<ICmpInst>(Inst)->getPredicate() == ICmpInst::ICMP_EQ) { 30758e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (ConstantInt *C = GetConstantInt(Inst->getOperand(1))) { 3080d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 3090d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 31058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen } else if (ConstantInt *C = GetConstantInt(Inst->getOperand(0))) { 3110d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 3120d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(1); 3130d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3140d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::Or) { 3150d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 3160d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 3170d56008f53587531718ec36af82cc24576580b36Chris Lattner if (LHS == RHS) 3180d56008f53587531718ec36af82cc24576580b36Chris Lattner return LHS; 3190d56008f53587531718ec36af82cc24576580b36Chris Lattner } 32007e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov } 3210d56008f53587531718ec36af82cc24576580b36Chris Lattner return 0; 3220d56008f53587531718ec36af82cc24576580b36Chris Lattner} 3230d56008f53587531718ec36af82cc24576580b36Chris Lattner 3245049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// GatherConstantSetNEs - Given a potentially 'and'd together collection of 3255049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// setne instructions that compare a value against a constant, return the value 3265049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// being compared, and stick the constant into the Values vector. 32758e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund OlesenValue *SimplifyCFGOpt:: 32858e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund OlesenGatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values) { 32907e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov if (Instruction *Inst = dyn_cast<Instruction>(V)) { 330e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if (Inst->getOpcode() == Instruction::ICmp && 331e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer cast<ICmpInst>(Inst)->getPredicate() == ICmpInst::ICMP_NE) { 33258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (ConstantInt *C = GetConstantInt(Inst->getOperand(1))) { 3330d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 3340d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(0); 33558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen } else if (ConstantInt *C = GetConstantInt(Inst->getOperand(0))) { 3360d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.push_back(C); 3370d56008f53587531718ec36af82cc24576580b36Chris Lattner return Inst->getOperand(1); 3380d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3390d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Inst->getOpcode() == Instruction::And) { 3400d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 3410d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 3420d56008f53587531718ec36af82cc24576580b36Chris Lattner if (LHS == RHS) 3430d56008f53587531718ec36af82cc24576580b36Chris Lattner return LHS; 3440d56008f53587531718ec36af82cc24576580b36Chris Lattner } 34507e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov } 3460d56008f53587531718ec36af82cc24576580b36Chris Lattner return 0; 3470d56008f53587531718ec36af82cc24576580b36Chris Lattner} 3480d56008f53587531718ec36af82cc24576580b36Chris Lattner 3490d56008f53587531718ec36af82cc24576580b36Chris Lattner/// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 3500d56008f53587531718ec36af82cc24576580b36Chris Lattner/// bunch of comparisons of one value against constants, return the value and 3510d56008f53587531718ec36af82cc24576580b36Chris Lattner/// the constants being compared. 35258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesenbool SimplifyCFGOpt::GatherValueComparisons(Instruction *Cond, Value *&CompVal, 35358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen std::vector<ConstantInt*> &Values) { 3540d56008f53587531718ec36af82cc24576580b36Chris Lattner if (Cond->getOpcode() == Instruction::Or) { 3550d56008f53587531718ec36af82cc24576580b36Chris Lattner CompVal = GatherConstantSetEQs(Cond, Values); 3560d56008f53587531718ec36af82cc24576580b36Chris Lattner 3570d56008f53587531718ec36af82cc24576580b36Chris Lattner // Return true to indicate that the condition is true if the CompVal is 3580d56008f53587531718ec36af82cc24576580b36Chris Lattner // equal to one of the constants. 3590d56008f53587531718ec36af82cc24576580b36Chris Lattner return true; 3600d56008f53587531718ec36af82cc24576580b36Chris Lattner } else if (Cond->getOpcode() == Instruction::And) { 3610d56008f53587531718ec36af82cc24576580b36Chris Lattner CompVal = GatherConstantSetNEs(Cond, Values); 362fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 3630d56008f53587531718ec36af82cc24576580b36Chris Lattner // Return false to indicate that the condition is false if the CompVal is 3640d56008f53587531718ec36af82cc24576580b36Chris Lattner // equal to one of the constants. 3650d56008f53587531718ec36af82cc24576580b36Chris Lattner return false; 3660d56008f53587531718ec36af82cc24576580b36Chris Lattner } 3670d56008f53587531718ec36af82cc24576580b36Chris Lattner return false; 3680d56008f53587531718ec36af82cc24576580b36Chris Lattner} 3690d56008f53587531718ec36af82cc24576580b36Chris Lattner 370080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedmanstatic void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { 371080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman Instruction* Cond = 0; 372080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 373080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman Cond = dyn_cast<Instruction>(SI->getCondition()); 374080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 375080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman if (BI->isConditional()) 376080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman Cond = dyn_cast<Instruction>(BI->getCondition()); 377080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman } 378080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman 379080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman TI->eraseFromParent(); 380080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond); 381080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman} 382080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman 3839fd4955c6ab9a191dec2d5afd4b2027d4b906f2eChris Lattner/// isValueEqualityComparison - Return true if the specified terminator checks 3849fd4955c6ab9a191dec2d5afd4b2027d4b906f2eChris Lattner/// to see if a value is equal to constant integer value. 38558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund OlesenValue *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { 38658e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen Value *CV = 0; 3874bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 3884bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner // Do not permit merging of large switch instructions into their 3894bebf08d152d84970d250feec72fb734cb8a5316Chris Lattner // predecessors unless there is only one predecessor. 39058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()), 39158e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen pred_end(SI->getParent())) <= 128) 39258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen CV = SI->getCondition(); 39358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 394542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (BI->isConditional() && BI->getCondition()->hasOneUse()) 395e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) 396e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer if ((ICI->getPredicate() == ICmpInst::ICMP_EQ || 397e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer ICI->getPredicate() == ICmpInst::ICMP_NE) && 39858e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen GetConstantInt(ICI->getOperand(1))) 39958e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen CV = ICI->getOperand(0); 40058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen 40158e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen // Unwrap any lossless ptrtoint cast. 40258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (TD && CV && CV->getType() == TD->getIntPtrType(CV->getContext())) 40358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) 40458e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen CV = PTII->getOperand(0); 40558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen return CV; 406542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 407542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 4085049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// GetValueEqualityComparisonCases - Given a value comparison instruction, 4095049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// decode all of the 'cases' that it represents and return the 'default' block. 41058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund OlesenBasicBlock *SimplifyCFGOpt:: 411fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha BrukmanGetValueEqualityComparisonCases(TerminatorInst *TI, 412542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, 413542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock*> > &Cases) { 414542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 415542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Cases.reserve(SI->getNumCases()); 416542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 417be54dcc8a9d14592e324d6e6ae1322782e17f09fChris Lattner Cases.push_back(std::make_pair(SI->getCaseValue(i), SI->getSuccessor(i))); 418542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return SI->getDefaultDest(); 419542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 420542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 421542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BranchInst *BI = cast<BranchInst>(TI); 422e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 42358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen Cases.push_back(std::make_pair(GetConstantInt(ICI->getOperand(1)), 424e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer BI->getSuccessor(ICI->getPredicate() == 425e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer ICmpInst::ICMP_NE))); 426e4d87aa2de6e52952dca73716386db09aad5a8fdReid Spencer return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); 427542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 428542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 429542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 4305049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries 4315049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// in the list that match the specified block. 432fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukmanstatic void EliminateBlockCases(BasicBlock *BB, 433623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) { 434623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = Cases.size(); i != e; ++i) 435623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (Cases[i].second == BB) { 436623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Cases.erase(Cases.begin()+i); 437623369ac5669a3667a94a3cbba342dea78845615Chris Lattner --i; --e; 438623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 439623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 440623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 4415049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 4425049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// well. 443623369ac5669a3667a94a3cbba342dea78845615Chris Lattnerstatic bool 444623369ac5669a3667a94a3cbba342dea78845615Chris LattnerValuesOverlap(std::vector<std::pair<ConstantInt*, BasicBlock*> > &C1, 445623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > &C2) { 446623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > *V1 = &C1, *V2 = &C2; 447623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 448623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Make V1 be smaller than V2. 449623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() > V2->size()) 450623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::swap(V1, V2); 451623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 452623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() == 0) return false; 453623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (V1->size() == 1) { 454623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Just scan V2. 455623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ConstantInt *TheVal = (*V1)[0].first; 456623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = V2->size(); i != e; ++i) 457623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TheVal == (*V2)[i].first) 458623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 459623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 460623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 461623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Otherwise, just sort both lists and compare element by element. 462623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::sort(V1->begin(), V1->end()); 463623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::sort(V2->begin(), V2->end()); 464623369ac5669a3667a94a3cbba342dea78845615Chris Lattner unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 465623369ac5669a3667a94a3cbba342dea78845615Chris Lattner while (i1 != e1 && i2 != e2) { 466623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if ((*V1)[i1].first == (*V2)[i2].first) 467623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 468623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if ((*V1)[i1].first < (*V2)[i2].first) 469623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ++i1; 470623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 471623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ++i2; 472623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 473623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; 474623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 475623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 4765049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 4775049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// terminator instruction and its block is known to only have a single 4785049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// predecessor block, check to see if that predecessor is also a value 4795049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// comparison with the same value, and if that comparison determines the 4805049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// outcome of this comparison. If so, simplify TI. This does a very limited 4815049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// form of jump threading. 48258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesenbool SimplifyCFGOpt:: 48358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund OlesenSimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 48458e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen BasicBlock *Pred) { 485623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 486623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (!PredVal) return false; // Not a value comparison in predecessor. 487623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 488623369ac5669a3667a94a3cbba342dea78845615Chris Lattner Value *ThisVal = isValueEqualityComparison(TI); 489623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(ThisVal && "This isn't a value comparison!!"); 490623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ThisVal != PredVal) return false; // Different predicates. 491623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 492623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Find out information about when control will move from Pred to TI's block. 493623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 494623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 495623369ac5669a3667a94a3cbba342dea78845615Chris Lattner PredCases); 496623369ac5669a3667a94a3cbba342dea78845615Chris Lattner EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 497fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 498623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Find information about how control leaves this block. 499623369ac5669a3667a94a3cbba342dea78845615Chris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases; 500623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 501623369ac5669a3667a94a3cbba342dea78845615Chris Lattner EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 502623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 503623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If TI's block is the default block from Pred's comparison, potentially 504623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // simplify TI based on this knowledge. 505623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (PredDef == TI->getParent()) { 506623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we are here, we know that the value is none of those cases listed in 507623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // PredCases. If there are any cases in ThisCases that are in PredCases, we 508623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // can simplify TI. 509623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ValuesOverlap(PredCases, ThisCases)) { 510080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman if (isa<BranchInst>(TI)) { 511623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, one of the successors of this condbr is dead. Convert it to a 512623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // uncond br. 513623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(ThisCases.size() == 1 && "Branch can only have one case!"); 514623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Insert the new branch. 515051a950000e21935165db56695e35bade668193bGabor Greif Instruction *NI = BranchInst::Create(ThisDef, TI); 516e317bcc74c1f317f913e9b05db385901cfc54d0bDaniel Dunbar (void) NI; 517623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 518623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Remove PHI node entries for the dead edge. 519623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ThisCases[0].second->removePredecessor(TI->getParent()); 520623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 52189d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 522bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 523623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 524080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman EraseTerminatorInstAndDCECond(TI); 525623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 526623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 527623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else { 528623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SwitchInst *SI = cast<SwitchInst>(TI); 529623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, TI has cases that are statically dead, prune them away. 530c9951231822215d6aea7a9b50947c18d8d745609Chris Lattner SmallPtrSet<Constant*, 16> DeadCases; 531623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 532623369ac5669a3667a94a3cbba342dea78845615Chris Lattner DeadCases.insert(PredCases[i].first); 533623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 53489d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 535bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << "Through successor TI: " << *TI); 536623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 537623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = SI->getNumCases()-1; i != 0; --i) 538623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (DeadCases.count(SI->getCaseValue(i))) { 539623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SI->getSuccessor(i)->removePredecessor(TI->getParent()); 540623369ac5669a3667a94a3cbba342dea78845615Chris Lattner SI->removeCase(i); 541623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 542623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 54389d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << "Leaving: " << *TI << "\n"); 544623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 545623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 546623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 547623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 548623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else { 549623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Otherwise, TI's block must correspond to some matched value. Find out 550623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // which value (or set of values) this is. 551623369ac5669a3667a94a3cbba342dea78845615Chris Lattner ConstantInt *TIV = 0; 552623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *TIBB = TI->getParent(); 553623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 55407e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov if (PredCases[i].second == TIBB) { 555623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TIV == 0) 556623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TIV = PredCases[i].first; 557623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 558623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; // Cannot handle multiple values coming to this block. 55907e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov } 560623369ac5669a3667a94a3cbba342dea78845615Chris Lattner assert(TIV && "No edge from pred to succ?"); 561623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 562623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Okay, we found the one constant that our value can be if we get into TI's 563623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // BB. Find out which successor will unconditionally be branched to. 564623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *TheRealDest = 0; 565623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 566623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (ThisCases[i].first == TIV) { 567623369ac5669a3667a94a3cbba342dea78845615Chris Lattner TheRealDest = ThisCases[i].second; 568623369ac5669a3667a94a3cbba342dea78845615Chris Lattner break; 569623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 570623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 571623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If not handled by any explicit cases, it is handled by the default case. 572623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (TheRealDest == 0) TheRealDest = ThisDef; 573623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 574623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Remove PHI node entries for dead edges. 575623369ac5669a3667a94a3cbba342dea78845615Chris Lattner BasicBlock *CheckEdge = TheRealDest; 576623369ac5669a3667a94a3cbba342dea78845615Chris Lattner for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 577623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (*SI != CheckEdge) 578623369ac5669a3667a94a3cbba342dea78845615Chris Lattner (*SI)->removePredecessor(TIBB); 579623369ac5669a3667a94a3cbba342dea78845615Chris Lattner else 580623369ac5669a3667a94a3cbba342dea78845615Chris Lattner CheckEdge = 0; 581623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 582623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // Insert the new branch. 583051a950000e21935165db56695e35bade668193bGabor Greif Instruction *NI = BranchInst::Create(TheRealDest, TI); 584e317bcc74c1f317f913e9b05db385901cfc54d0bDaniel Dunbar (void) NI; 585623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 58689d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 587bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 588623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 589080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman EraseTerminatorInstAndDCECond(TI); 590623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return true; 591623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 592623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return false; 593623369ac5669a3667a94a3cbba342dea78845615Chris Lattner} 594623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 595c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesennamespace { 596c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen /// ConstantIntOrdering - This class implements a stable ordering of constant 597c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen /// integers that does not depend on their address. This is important for 598c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen /// applications that sort ConstantInt's to ensure uniqueness. 599c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen struct ConstantIntOrdering { 600c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 601c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen return LHS->getValue().ult(RHS->getValue()); 602c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen } 603c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen }; 604c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen} 605a9537cf3fcf9fdaac94749db9fbd34912b1f0f08Dale Johannesen 6065049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// FoldValueComparisonIntoPredecessors - The specified terminator is a value 6075049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// equality comparison instruction (either a switch or a branch on "X == c"). 6085049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// See if any of the predecessors of the terminator block are value comparisons 6095049fa6bbc66534fe0cc361808dff80fd2d5cde2Bill Wendling/// on the same value. If so, and if safe to do so, fold them together. 61058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesenbool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 611542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *BB = TI->getParent(); 612542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Value *CV = isValueEqualityComparison(TI); // CondVal 613542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner assert(CV && "Not a comparison?"); 614542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner bool Changed = false; 615542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 6168244243a31d636ce8838a81d4c402274fd391d2bChris Lattner SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 617542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner while (!Preds.empty()) { 618e9d87f49063cb1bd213d8e9c339b9b63393cc2d9Dan Gohman BasicBlock *Pred = Preds.pop_back_val(); 619fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 620542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // See if the predecessor is a comparison with the same value. 621542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner TerminatorInst *PTI = Pred->getTerminator(); 622542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 623542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 624542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 625542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Figure out which 'cases' to copy from SI to PSI. 626542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 627542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 628542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 629542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 630542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 631542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 632542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Based on whether the default edge from PTI goes to BB or not, fill in 633542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // PredCases and PredDefault with the new switch cases we would like to 634542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // build. 6358244243a31d636ce8838a81d4c402274fd391d2bChris Lattner SmallVector<BasicBlock*, 8> NewSuccessors; 636542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 637542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredDefault == BB) { 638542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is the default destination from PTI, only the edges in TI 639542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // that don't occur in PTI, or that branch to BB will be activated. 640c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 641542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 642542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredCases[i].second != BB) 643542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.insert(PredCases[i].first); 644542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner else { 645542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // The default destination is BB, we don't need explicit targets. 646542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::swap(PredCases[i], PredCases.back()); 647542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.pop_back(); 648542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner --i; --e; 649542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 650542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 651542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Reconstruct the new switch statement we will be building. 652542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredDefault != BBDefault) { 653542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredDefault->removePredecessor(Pred); 654542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredDefault = BBDefault; 655542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBDefault); 656542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 657542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 658542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (!PTIHandled.count(BBCases[i].first) && 659542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BBCases[i].second != BBDefault) { 660542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(BBCases[i]); 661542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBCases[i].second); 662542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 663542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 664542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } else { 665542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is not the default destination from PSI, only the edges 666542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // in SI that occur in PSI with a destination of BB will be 667542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // activated. 668c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 669542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 670542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PredCases[i].second == BB) { 671542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.insert(PredCases[i].first); 672542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner std::swap(PredCases[i], PredCases.back()); 673542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.pop_back(); 674542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner --i; --e; 675542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 676542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 677542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, now we know which constants were sent to BB from the 678542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // predecessor. Figure out where they will all go now. 679542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 680542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (PTIHandled.count(BBCases[i].first)) { 681542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If this is one we are capable of getting... 682542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(BBCases[i]); 683542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBCases[i].second); 684542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PTIHandled.erase(BBCases[i].first);// This constant is taken care of 685542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 686542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 687542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // If there are any constants vectored to BB that TI doesn't handle, 688542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // they must go to the default destination of TI. 689c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I = 690c81f5445a7cbe3ba0252aec030082a40e5019eceDale Johannesen PTIHandled.begin(), 691542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner E = PTIHandled.end(); I != E; ++I) { 692542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner PredCases.push_back(std::make_pair(*I, BBDefault)); 693542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSuccessors.push_back(BBDefault); 694542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 695542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 696542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 697542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, at this point, we know which new successor Pred will get. Make 698542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // sure we update the number of entries in the PHI nodes for these 699542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // successors. 700542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 701542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 702542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 70358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen // Convert pointer to int before we switch. 70458e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (isa<PointerType>(CV->getType())) { 70558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen assert(TD && "Cannot switch on pointer without TargetData"); 70658e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen CV = new PtrToIntInst(CV, TD->getIntPtrType(CV->getContext()), 70758e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen "magicptr", PTI); 70858e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen } 70958e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen 710542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Now that the successors are updated, create the new Switch instruction. 711b1dbcd886a4b5597a839f299054b78b33fb2d6dfGabor Greif SwitchInst *NewSI = SwitchInst::Create(CV, PredDefault, 712b1dbcd886a4b5597a839f299054b78b33fb2d6dfGabor Greif PredCases.size(), PTI); 713542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 714542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSI->addCase(PredCases[i].first, PredCases[i].second); 71513b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner 716080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman EraseTerminatorInstAndDCECond(PTI); 71713b2f764c041e15af3d6033826deb9c7e669ca97Chris Lattner 718542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // Okay, last check. If BB is still a successor of PSI, then we must 719542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // have an infinite loop case. If so, add an infinitely looping block 720542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // to handle the case to preserve the behavior of the code. 721542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner BasicBlock *InfLoopBlock = 0; 722542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 723542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (NewSI->getSuccessor(i) == BB) { 724542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner if (InfLoopBlock == 0) { 725093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // Insert it at the end of the function, because it's either code, 726542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner // or it won't matter if it's hot. :) 7271d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson InfLoopBlock = BasicBlock::Create(BB->getContext(), 7281d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "infloop", BB->getParent()); 729051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(InfLoopBlock, InfLoopBlock); 730542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 731542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner NewSI->setSuccessor(i, InfLoopBlock); 732542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 733fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 734542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner Changed = true; 735542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 736542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } 737542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner return Changed; 738542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner} 739542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner 740c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen// isSafeToHoistInvoke - If we would need to insert a select that uses the 741c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen// value of this invoke (comments in HoistThenElseCodeToIf explain why we 742c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen// would need to do this), we can't hoist the invoke, as there is nowhere 743c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen// to put the select in this case. 744c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesenstatic bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, 745c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen Instruction *I1, Instruction *I2) { 746c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 747c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen PHINode *PN; 748c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen for (BasicBlock::iterator BBI = SI->begin(); 749c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 750c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen Value *BB1V = PN->getIncomingValueForBlock(BB1); 751c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen Value *BB2V = PN->getIncomingValueForBlock(BB2); 752c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) { 753c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen return false; 754c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen } 755c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen } 756c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen } 757c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen return true; 758c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen} 759c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen 7606306d07aa8cf71e3c7fed7f295665f53595473ebChris Lattner/// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and 76137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// BB2, hoist any common code in the two blocks up into the branch block. The 76237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner/// caller of this function guarantees that BI's block dominates BB1 and BB2. 76337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattnerstatic bool HoistThenElseCodeToIf(BranchInst *BI) { 76437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // This does very trivial matching, with limited scanning, to find identical 76537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // instructions in the two blocks. In particular, we don't want to get into 76637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 76737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // such, we currently just scan for obviously identical instructions in an 76837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // identical order. 76937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 77037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 77137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 77265085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel BasicBlock::iterator BB1_Itr = BB1->begin(); 77365085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel BasicBlock::iterator BB2_Itr = BB2->begin(); 77465085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel 77565085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++; 77665085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel while (isa<DbgInfoIntrinsic>(I1)) 77765085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel I1 = BB1_Itr++; 77865085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel while (isa<DbgInfoIntrinsic>(I2)) 77965085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel I2 = BB2_Itr++; 780c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen if (I1->getOpcode() != I2->getOpcode() || isa<PHINode>(I1) || 78158cfa3b13752579c86cf85270d49f9ced0942f2fDan Gohman !I1->isIdenticalToWhenDefined(I2) || 782c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))) 78337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return false; 78437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 78537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // If we get here, we can hoist at least one instruction. 78637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BasicBlock *BIParent = BI->getParent(); 78737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 78837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner do { 78937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // If we are hoisting the terminator instruction, don't move one (making a 79037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // broken BB), instead clone it, and remove BI. 79137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (isa<TerminatorInst>(I1)) 79237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner goto HoistTerminator; 793fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 79437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // For a normal instruction, we just move one to right before the branch, 79537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // then replace all uses of the other with the first. Finally, we remove 79637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // the now redundant second instruction. 79737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 79837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (!I2->use_empty()) 79937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2->replaceAllUsesWith(I1); 80058cfa3b13752579c86cf85270d49f9ced0942f2fDan Gohman I1->intersectOptionalDataWith(I2); 80137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BB2->getInstList().erase(I2); 802fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 80365085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel I1 = BB1_Itr++; 80465085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel while (isa<DbgInfoIntrinsic>(I1)) 80565085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel I1 = BB1_Itr++; 80665085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel I2 = BB2_Itr++; 80765085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel while (isa<DbgInfoIntrinsic>(I2)) 80865085cf7b3470b7b087f5fd7b0497879b90b32baDevang Patel I2 = BB2_Itr++; 80958cfa3b13752579c86cf85270d49f9ced0942f2fDan Gohman } while (I1->getOpcode() == I2->getOpcode() && 81058cfa3b13752579c86cf85270d49f9ced0942f2fDan Gohman I1->isIdenticalToWhenDefined(I2)); 81137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 81237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return true; 81337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 81437dc938bbe556a9414d063196d367c2f75d07d95Chris LattnerHoistTerminator: 815c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen // It may not be possible to hoist an invoke. 816c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) 817c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen return true; 818c1f104054dda0b3946abbe3b6859e960b60168f7Dale Johannesen 81937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Okay, it is safe to hoist the terminator. 8206776064d190701c5bae4d5403939eed2e480d1cdNick Lewycky Instruction *NT = I1->clone(); 82137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner BIParent->getInstList().insert(BI, NT); 822f012705c7e4ca8cf90b6b734ce1d5355daca5ba5Benjamin Kramer if (!NT->getType()->isVoidTy()) { 82337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I1->replaceAllUsesWith(NT); 82437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner I2->replaceAllUsesWith(NT); 82586cc42355593dd1689f7d58d56695c451215b02bChris Lattner NT->takeName(I1); 82637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 82737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 82837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Hoisting one of the terminators from our successor is a great thing. 82937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Unfortunately, the successors of the if/else blocks may have PHI nodes in 83037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 83137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // nodes, so we insert select instruction to compute the final result. 83237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 83337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 83437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PHINode *PN; 83537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (BasicBlock::iterator BBI = SI->begin(); 8360f535c6fa8b03491dc110feb65d78922ee29d1fcChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 83737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Value *BB1V = PN->getIncomingValueForBlock(BB1); 83837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner Value *BB2V = PN->getIncomingValueForBlock(BB2); 83937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (BB1V != BB2V) { 84037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // These values do not agree. Insert a select instruction before NT 84137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // that determines the right value. 84237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 84337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (SI == 0) 844051a950000e21935165db56695e35bade668193bGabor Greif SI = SelectInst::Create(BI->getCondition(), BB1V, BB2V, 845051a950000e21935165db56695e35bade668193bGabor Greif BB1V->getName()+"."+BB2V->getName(), NT); 84637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Make the PHI node use the select for all incoming values for BB1/BB2 84737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 84837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 84937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner PN->setIncomingValue(i, SI); 85037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 85137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 85237dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 85337dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 85437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner // Update any PHI nodes in our new successors. 85537dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 85637dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner AddPredecessorToBlock(*SI, BIParent, BB1); 857fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 858080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman EraseTerminatorInstAndDCECond(BI); 85937dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner return true; 86037dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner} 86137dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 8624d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng/// SpeculativelyExecuteBB - Given a conditional branch that goes to BB1 8634d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng/// and an BB2 and the only successor of BB1 is BB2, hoist simple code 8644d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng/// (for now, restricted to a single instruction that's side effect free) from 8654d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng/// the BB1 into the branch block to speculatively execute it. 8664d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Chengstatic bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { 8674d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // Only speculatively execution a single instruction (not counting the 8684d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // terminator) for now. 86906b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel Instruction *HInst = NULL; 87006b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel Instruction *Term = BB1->getTerminator(); 87106b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end(); 87206b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel BBI != BBE; ++BBI) { 87306b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel Instruction *I = BBI; 87406b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel // Skip debug info. 87506b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel if (isa<DbgInfoIntrinsic>(I)) continue; 87606b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel if (I == Term) break; 87706b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel 87806b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel if (!HInst) 87906b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel HInst = I; 88006b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel else 88106b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel return false; 88206b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel } 88306b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel if (!HInst) 88406b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel return false; 8854d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng 886797d95188d00963a835db9ad66dd3c4a54aa2fafEvan Cheng // Be conservative for now. FP select instruction can often be expensive. 887797d95188d00963a835db9ad66dd3c4a54aa2fafEvan Cheng Value *BrCond = BI->getCondition(); 888797d95188d00963a835db9ad66dd3c4a54aa2fafEvan Cheng if (isa<Instruction>(BrCond) && 889797d95188d00963a835db9ad66dd3c4a54aa2fafEvan Cheng cast<Instruction>(BrCond)->getOpcode() == Instruction::FCmp) 890797d95188d00963a835db9ad66dd3c4a54aa2fafEvan Cheng return false; 891797d95188d00963a835db9ad66dd3c4a54aa2fafEvan Cheng 8924d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // If BB1 is actually on the false edge of the conditional branch, remember 8934d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // to swap the select operands later. 8944d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng bool Invert = false; 8954d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng if (BB1 != BI->getSuccessor(0)) { 8964d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng assert(BB1 == BI->getSuccessor(1) && "No edge from 'if' block?"); 8974d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng Invert = true; 8984d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng } 8994d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng 9004d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // Turn 9014d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // BB: 9024d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // %t1 = icmp 9034d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // br i1 %t1, label %BB1, label %BB2 9044d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // BB1: 9054d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // %t3 = add %t2, c 9064d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // br label BB2 9074d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // BB2: 9084d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // => 9094d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // BB: 9104d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // %t1 = icmp 9114d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // %t4 = add %t2, c 9124d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // %t3 = select i1 %t1, %t2, %t3 91306b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel switch (HInst->getOpcode()) { 9144d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng default: return false; // Not safe / profitable to hoist. 9154d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng case Instruction::Add: 9164d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng case Instruction::Sub: 917ae3a0be92e33bc716722aa600983fc1535acb122Dan Gohman // Not worth doing for vector ops. 918ae3a0be92e33bc716722aa600983fc1535acb122Dan Gohman if (isa<VectorType>(HInst->getType())) 9199dd3b610dcb17f88ed52ae03022179bf21e0e132Chris Lattner return false; 9209dd3b610dcb17f88ed52ae03022179bf21e0e132Chris Lattner break; 9214d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng case Instruction::And: 9224d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng case Instruction::Or: 9234d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng case Instruction::Xor: 9244d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng case Instruction::Shl: 9254d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng case Instruction::LShr: 9264d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng case Instruction::AShr: 9279dd3b610dcb17f88ed52ae03022179bf21e0e132Chris Lattner // Don't mess with vector operations. 92806b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel if (isa<VectorType>(HInst->getType())) 929e5334ea518e3dffec4037ede97433eb700fa1d26Evan Cheng return false; 9304d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng break; // These are all cheap and non-trapping instructions. 9314d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng } 9326fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner 9336fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner // If the instruction is obviously dead, don't try to predicate it. 93406b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel if (HInst->use_empty()) { 93506b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel HInst->eraseFromParent(); 9366fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner return true; 9376fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner } 9384d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng 9394d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // Can we speculatively execute the instruction? And what is the value 9404d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // if the condition is false? Consider the phi uses, if the incoming value 9414d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // from the "if" block are all the same V, then V is the value of the 9424d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // select if the condition is false. 9434d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng BasicBlock *BIParent = BI->getParent(); 9444d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng SmallVector<PHINode*, 4> PHIUses; 9454d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng Value *FalseV = NULL; 9466fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner 9476fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner BasicBlock *BB2 = BB1->getTerminator()->getSuccessor(0); 94806b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel for (Value::use_iterator UI = HInst->use_begin(), E = HInst->use_end(); 9494d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng UI != E; ++UI) { 9506fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner // Ignore any user that is not a PHI node in BB2. These can only occur in 9516fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner // unreachable blocks, because they would not be dominated by the instr. 9524d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng PHINode *PN = dyn_cast<PHINode>(UI); 9536fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner if (!PN || PN->getParent() != BB2) 9546fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner return false; 9554d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng PHIUses.push_back(PN); 9566fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner 9574d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng Value *PHIV = PN->getIncomingValueForBlock(BIParent); 9584d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng if (!FalseV) 9594d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng FalseV = PHIV; 9604d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng else if (FalseV != PHIV) 9616fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner return false; // Inconsistent value when condition is false. 9624d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng } 9636fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner 9646fe73bbcf3b6c1ddfd5e70e8b5188f8df439ace6Chris Lattner assert(FalseV && "Must have at least one user, and it must be a PHI"); 9654d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng 966502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng // Do not hoist the instruction if any of its operands are defined but not 967502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng // used in this BB. The transformation will prevent the operand from 968502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng // being sunk into the use block. 96906b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel for (User::op_iterator i = HInst->op_begin(), e = HInst->op_end(); 97006b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel i != e; ++i) { 971502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng Instruction *OpI = dyn_cast<Instruction>(*i); 972502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng if (OpI && OpI->getParent() == BIParent && 973502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng !OpI->isUsedInBasicBlock(BIParent)) 974502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng return false; 975502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng } 976502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng 9773d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel // If we get here, we can hoist the instruction. Try to place it 978990afedb3a4b7d32832d74ad5b5863c19f909e1fDale Johannesen // before the icmp instruction preceding the conditional branch. 9793d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel BasicBlock::iterator InsertPos = BI; 980990afedb3a4b7d32832d74ad5b5863c19f909e1fDale Johannesen if (InsertPos != BIParent->begin()) 981990afedb3a4b7d32832d74ad5b5863c19f909e1fDale Johannesen --InsertPos; 982990afedb3a4b7d32832d74ad5b5863c19f909e1fDale Johannesen // Skip debug info between condition and branch. 983990afedb3a4b7d32832d74ad5b5863c19f909e1fDale Johannesen while (InsertPos != BIParent->begin() && isa<DbgInfoIntrinsic>(InsertPos)) 9843d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel --InsertPos; 98520da1f07dac4d771e55ee5c7f105ccedfa4caaaaDevang Patel if (InsertPos == BrCond && !isa<PHINode>(BrCond)) { 9863d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel SmallPtrSet<Instruction *, 4> BB1Insns; 9873d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel for(BasicBlock::iterator BB1I = BB1->begin(), BB1E = BB1->end(); 9883d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel BB1I != BB1E; ++BB1I) 9893d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel BB1Insns.insert(BB1I); 9903d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel for(Value::use_iterator UI = BrCond->use_begin(), UE = BrCond->use_end(); 9913d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel UI != UE; ++UI) { 9923d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel Instruction *Use = cast<Instruction>(*UI); 9933d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel if (BB1Insns.count(Use)) { 9943d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel // If BrCond uses the instruction that place it just before 9953d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel // branch instruction. 9963d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel InsertPos = BI; 9973d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel break; 9983d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel } 9993d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel } 10003d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel } else 10013d0a9a371c0ce3a46e845a7bf1f1acb7a1cf523eDevang Patel InsertPos = BI; 100206b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel BIParent->getInstList().splice(InsertPos, BB1->getInstList(), HInst); 10034d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng 10044d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // Create a select whose true value is the speculatively executed value and 10054d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // false value is the previously determined FalseV. 10064d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng SelectInst *SI; 10074d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng if (Invert) 100806b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel SI = SelectInst::Create(BrCond, FalseV, HInst, 100906b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel FalseV->getName() + "." + HInst->getName(), BI); 10104d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng else 101106b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel SI = SelectInst::Create(BrCond, HInst, FalseV, 101206b1e67d44a6c13f9e75fbc1ac3c7de2df4776c9Devang Patel HInst->getName() + "." + FalseV->getName(), BI); 10134d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng 10144d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // Make the PHI node use the select for all incoming values for "then" and 10154d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // "if" blocks. 10164d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng for (unsigned i = 0, e = PHIUses.size(); i != e; ++i) { 10174d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng PHINode *PN = PHIUses[i]; 10184d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng for (unsigned j = 0, ee = PN->getNumIncomingValues(); j != ee; ++j) 10194d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng if (PN->getIncomingBlock(j) == BB1 || 10204d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng PN->getIncomingBlock(j) == BIParent) 10214d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng PN->setIncomingValue(j, SI); 10224d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng } 10234d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng 1024502a4f5162498ec420e3cb22f667808d726dd7daEvan Cheng ++NumSpeculations; 10254d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng return true; 10264d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng} 10274d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng 10282e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner/// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch 10292e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner/// across this block. 10302e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattnerstatic bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { 10312e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 1032e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner unsigned Size = 0; 1033e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 10349200c89968e52a590ee0b96092a0a589aa138a6fDevang Patel for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 10358483e54837ede5dd40c5561f15c6a663e2bee87cDale Johannesen if (isa<DbgInfoIntrinsic>(BBI)) 10368483e54837ede5dd40c5561f15c6a663e2bee87cDale Johannesen continue; 1037e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (Size > 10) return false; // Don't clone large BB's. 10388483e54837ede5dd40c5561f15c6a663e2bee87cDale Johannesen ++Size; 10392e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 10408483e54837ede5dd40c5561f15c6a663e2bee87cDale Johannesen // We can only support instructions that do not define values that are 1041e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // live outside of the current basic block. 1042e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 1043e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner UI != E; ++UI) { 1044e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner Instruction *U = cast<Instruction>(*UI); 1045e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (U->getParent() != BB || isa<PHINode>(U)) return false; 1046e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 10472e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 10482e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner // Looks ok, continue checking. 10492e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner } 1050e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 10512e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner return true; 10522e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner} 10532e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner 1054eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value 1055eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// that is defined in the same block as the branch and if any PHI entries are 1056eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// constants, thread edges corresponding to that entry to be branches to their 1057eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner/// ultimate destination. 1058eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattnerstatic bool FoldCondBranchOnPHI(BranchInst *BI) { 1059eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BasicBlock *BB = BI->getParent(); 1060eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 10619c88d9816246d260b37cdc689f313c56aec6941eChris Lattner // NOTE: we currently cannot transform this case if the PHI node is used 10629c88d9816246d260b37cdc689f313c56aec6941eChris Lattner // outside of the block. 10632e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (!PN || PN->getParent() != BB || !PN->hasOneUse()) 10642e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner return false; 1065eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1066eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Degenerate case of a single entry PHI. 1067eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PN->getNumIncomingValues() == 1) { 106829874e0dc6c4e55bc384611273343bb358982cc3Chris Lattner FoldSingleEntryPHINodes(PN->getParent()); 1069eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return true; 1070eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 1071eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1072eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Now we know that this block has multiple preds and two succs. 10732e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; 1074eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1075eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Okay, this is a simple enough basic block. See if any phi values are 1076eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // constants. 10776b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 10786b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng ConstantInt *CB; 10796b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if ((CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i))) && 1080b0bc6c361da9009e8414efde317d9bbff755f6c0Duncan Sands CB->getType()->isIntegerTy(1)) { 1081eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Okay, we now know that all edges from PredBB should be revectored to 1082eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // branch to RealDest. 1083eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BasicBlock *PredBB = PN->getIncomingBlock(i); 1084579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); 1085eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1086e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (RealDest == BB) continue; // Skip self loops. 1087eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1088e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // The dest block might have PHI nodes, other predecessors and other 1089e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // difficult cases. Instead of being smart about this, just insert a new 1090e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // block that jumps to the destination block, effectively splitting 1091e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // the edge we are about to create. 10921d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(), 10931d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson RealDest->getName()+".critedge", 1094051a950000e21935165db56695e35bade668193bGabor Greif RealDest->getParent(), RealDest); 1095051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(RealDest, EdgeBB); 1096e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner PHINode *PN; 1097e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (BasicBlock::iterator BBI = RealDest->begin(); 1098e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 1099e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner Value *V = PN->getIncomingValueForBlock(BB); 1100e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner PN->addIncoming(V, EdgeBB); 1101e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1102e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 1103e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // BB may have instructions that are being threaded over. Clone these 1104e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // instructions into EdgeBB. We know that there will be no uses of the 1105e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // cloned instructions outside of EdgeBB. 1106e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner BasicBlock::iterator InsertPt = EdgeBB->begin(); 1107e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner std::map<Value*, Value*> TranslateMap; // Track translated values. 1108e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1109e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 1110e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); 1111e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } else { 1112e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Clone the instruction. 11136776064d190701c5bae4d5403939eed2e480d1cdNick Lewycky Instruction *N = BBI->clone(); 1114e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (BBI->hasName()) N->setName(BBI->getName()+".c"); 1115e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 1116e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Update operands due to translation. 1117f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif for (User::op_iterator i = N->op_begin(), e = N->op_end(); 1118f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif i != e; ++i) { 1119e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner std::map<Value*, Value*>::iterator PI = 1120f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif TranslateMap.find(*i); 1121e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (PI != TranslateMap.end()) 1122f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif *i = PI->second; 1123e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1124e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 1125e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Check for trivial simplification. 11267b550ccfc5a3346c17e0390a59e2d6d19bc52705Chris Lattner if (Constant *C = ConstantFoldInstruction(N)) { 1127e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner TranslateMap[BBI] = C; 1128e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner delete N; // Constant folded away, don't need actual inst 1129e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } else { 1130e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // Insert the new instruction into its new home. 1131e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner EdgeBB->getInstList().insert(InsertPt, N); 1132e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner if (!BBI->use_empty()) 1133e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner TranslateMap[BBI] = N; 1134e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1135e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1136e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner } 1137e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner 1138eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Loop over all of the edges from PredBB to BB, changing them to branch 1139e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner // to EdgeBB instead. 1140eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner TerminatorInst *PredBBTI = PredBB->getTerminator(); 1141eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 1142eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PredBBTI->getSuccessor(i) == BB) { 1143eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner BB->removePredecessor(PredBB); 1144e9487f0dc8c6d15cb257d5b49fa96ed436d32f5fChris Lattner PredBBTI->setSuccessor(i, EdgeBB); 1145eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 1146eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1147eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // Recurse, simplifying any other constants. 1148eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return FoldCondBranchOnPHI(BI) | true; 1149eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner } 11506b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng } 1151eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1152eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return false; 1153eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner} 1154eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1155f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner/// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry 1156f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner/// PHI node, see if we can eliminate it. 1157f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattnerstatic bool FoldTwoEntryPHINode(PHINode *PN) { 1158f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1159f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // statement", which has a very simple dominance structure. Basically, we 1160f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // are trying to find the condition that is being branched on, which 1161f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // subsequently causes this merge to happen. We really want control 1162f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // dependence information for this check, but simplifycfg can't keep it up 1163f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // to date, and this catches most of the cases we care about anyway. 1164f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // 1165f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *BB = PN->getParent(); 1166f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *IfTrue, *IfFalse; 1167f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); 1168f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (!IfCond) return false; 1169f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1170822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // Okay, we found that we can merge this two-entry phi node into a select. 1171822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // Doing so would require us to fold *all* two entry phi nodes in this block. 1172822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // At some point this becomes non-profitable (particularly if the target 1173822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // doesn't support cmov's). Only do this transformation if there are two or 1174822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner // fewer PHI nodes in this block. 1175822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner unsigned NumPhis = 0; 1176822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I) 1177822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner if (NumPhis > 2) 1178822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner return false; 1179822a87998387a4c52be5162523f09cc8e5e5afb7Chris Lattner 118089d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond << " T: " 1181ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1182f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1183f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Loop over the PHI's seeing if we can promote them all to select 1184f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // instructions. While we are at it, keep track of the instructions 1185f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // that need to be moved to the dominating block. 1186f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner std::set<Instruction*> AggressiveInsts; 1187f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1188f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock::iterator AfterPHIIt = BB->begin(); 1189f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner while (isa<PHINode>(AfterPHIIt)) { 1190f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PHINode *PN = cast<PHINode>(AfterPHIIt++); 1191f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) { 1192f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (PN->getIncomingValue(0) != PN) 1193f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->replaceAllUsesWith(PN->getIncomingValue(0)); 1194f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner else 11959e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 1196f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 1197f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner &AggressiveInsts) || 1198f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner !DominatesMergePoint(PN->getIncomingValue(1), BB, 1199f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner &AggressiveInsts)) { 1200055dc102e97316d423bd068f8b228d27fb93c90aChris Lattner return false; 1201f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1202f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1203f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1204f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // If we all PHI nodes are promotable, check to make sure that all 1205f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // instructions in the predecessor blocks can be promoted as well. If 1206f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // not, we won't be able to get rid of the control flow, so it's not 1207f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // worth promoting to select instructions. 1208f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 1209f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN = cast<PHINode>(BB->begin()); 1210f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BasicBlock *Pred = PN->getIncomingBlock(0); 1211f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1212f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1 = Pred; 1213f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock = *pred_begin(Pred); 1214f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner for (BasicBlock::iterator I = Pred->begin(); 1215f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner !isa<TerminatorInst>(I); ++I) 1216383d7ed9158576aef5cde872548225a17e3c0155Devang Patel if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1217f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // This is not an aggressive instruction that we can promote. 1218f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Because of this, we won't be able to get rid of the control 1219f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // flow, so the xform is not worth it. 1220f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner return false; 1221f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1222f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1223f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1224f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Pred = PN->getIncomingBlock(1); 1225f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1226f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2 = Pred; 1227f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock = *pred_begin(Pred); 1228f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner for (BasicBlock::iterator I = Pred->begin(); 1229f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner !isa<TerminatorInst>(I); ++I) 1230383d7ed9158576aef5cde872548225a17e3c0155Devang Patel if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1231f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // This is not an aggressive instruction that we can promote. 1232f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Because of this, we won't be able to get rid of the control 1233f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // flow, so the xform is not worth it. 1234f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner return false; 1235f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1236f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1237f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1238f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // If we can still promote the PHI nodes after this gauntlet of tests, 1239f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // do all of the PHI's now. 1240f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1241f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Move all 'aggressive' instructions, which are defined in the 1242f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // conditional parts of the if's up to the dominating block. 1243f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (IfBlock1) { 1244f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 1245f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1->getInstList(), 1246f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1->begin(), 1247f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock1->getTerminator()); 1248f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1249f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner if (IfBlock2) { 1250f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner DomBlock->getInstList().splice(DomBlock->getTerminator(), 1251f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2->getInstList(), 1252f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2->begin(), 1253f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner IfBlock2->getTerminator()); 1254f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1255f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1256f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 1257f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner // Change the PHI node into a select instruction. 1258f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Value *TrueVal = 1259f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1260f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner Value *FalseVal = 1261f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1262f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner 1263051a950000e21935165db56695e35bade668193bGabor Greif Value *NV = SelectInst::Create(IfCond, TrueVal, FalseVal, "", AfterPHIIt); 126486cc42355593dd1689f7d58d56695c451215b02bChris Lattner PN->replaceAllUsesWith(NV); 126586cc42355593dd1689f7d58d56695c451215b02bChris Lattner NV->takeName(PN); 126686cc42355593dd1689f7d58d56695c451215b02bChris Lattner 1267f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner BB->getInstList().erase(PN); 1268f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner } 1269f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner return true; 1270f58c1a578e63265abf46c395953fe8aa3f73e37cChris Lattner} 1271eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner 1272998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel/// isTerminatorFirstRelevantInsn - Return true if Term is very first 1273998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel/// instruction ignoring Phi nodes and dbg intrinsics. 1274998cbb0444ecb597e4b46f1950561d92b5395769Devang Patelstatic bool isTerminatorFirstRelevantInsn(BasicBlock *BB, Instruction *Term) { 1275998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel BasicBlock::iterator BBI = Term; 1276998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel while (BBI != BB->begin()) { 1277998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel --BBI; 1278998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel if (!isa<DbgInfoIntrinsic>(BBI)) 1279998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel break; 1280998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel } 12810464a1431b79ed2be54413de239347c56ad84bfaDevang Patel 12820464a1431b79ed2be54413de239347c56ad84bfaDevang Patel if (isa<PHINode>(BBI) || &*BBI == Term || isa<DbgInfoIntrinsic>(BBI)) 1283998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel return true; 1284998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel return false; 1285998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel} 1286998cbb0444ecb597e4b46f1950561d92b5395769Devang Patel 1287c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner/// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes 1288c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner/// to two returning blocks, try to merge them together into one return, 1289c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner/// introducing a select if the return values disagree. 1290c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattnerstatic bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { 1291c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner assert(BI->isConditional() && "Must be a conditional branch"); 1292c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner BasicBlock *TrueSucc = BI->getSuccessor(0); 1293c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner BasicBlock *FalseSucc = BI->getSuccessor(1); 1294c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator()); 1295c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator()); 1296c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner 1297c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner // Check to ensure both blocks are empty (just a return) or optionally empty 1298c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner // with PHI nodes. If there are other instructions, merging would cause extra 1299c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner // computation on one path or the other. 13002cc86a1de1cf598be384836f19d1ef1892fb50fcDevang Patel if (!isTerminatorFirstRelevantInsn(TrueSucc, TrueRet)) 13012cc86a1de1cf598be384836f19d1ef1892fb50fcDevang Patel return false; 13022cc86a1de1cf598be384836f19d1ef1892fb50fcDevang Patel if (!isTerminatorFirstRelevantInsn(FalseSucc, FalseRet)) 13032cc86a1de1cf598be384836f19d1ef1892fb50fcDevang Patel return false; 1304c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner 1305c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner // Okay, we found a branch that is going to two return nodes. If 1306c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner // there is no return value for this function, just change the 1307c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner // branch into a return. 1308c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner if (FalseRet->getNumOperands() == 0) { 1309c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner TrueSucc->removePredecessor(BI->getParent()); 1310c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner FalseSucc->removePredecessor(BI->getParent()); 13111d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst::Create(BI->getContext(), 0, BI); 1312080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman EraseTerminatorInstAndDCECond(BI); 1313c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner return true; 1314c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner } 1315c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner 1316fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman // Otherwise, figure out what the true and false return values are 1317fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman // so we can insert a new select instruction. 1318fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman Value *TrueValue = TrueRet->getReturnValue(); 1319fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman Value *FalseValue = FalseRet->getReturnValue(); 1320fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman 1321fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman // Unwrap any PHI nodes in the return blocks. 1322fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue)) 1323fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (TVPN->getParent() == TrueSucc) 1324fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1325fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue)) 1326fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (FVPN->getParent() == FalseSucc) 1327fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1328fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman 1329fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman // In order for this transformation to be safe, we must be able to 1330fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman // unconditionally execute both operands to the return. This is 1331fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman // normally the case, but we could have a potentially-trapping 1332fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman // constant expression that prevents this transformation from being 1333fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman // safe. 1334fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue)) 1335fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (TCV->canTrap()) 1336fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman return false; 1337fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue)) 1338fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (FCV->canTrap()) 1339fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman return false; 1340c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner 1341c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner // Okay, we collected all the mapped values and checked them for sanity, and 1342c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner // defined to really do this transformation. First, update the CFG. 1343c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner TrueSucc->removePredecessor(BI->getParent()); 1344c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner FalseSucc->removePredecessor(BI->getParent()); 1345c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner 1346c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner // Insert select instructions where needed. 1347c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner Value *BrCond = BI->getCondition(); 1348fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (TrueValue) { 1349c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner // Insert a select if the results differ. 1350fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) { 1351fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman } else if (isa<UndefValue>(TrueValue)) { 1352fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman TrueValue = FalseValue; 1353fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman } else { 1354fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman TrueValue = SelectInst::Create(BrCond, TrueValue, 1355fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman FalseValue, "retval", BI); 1356c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner } 1357c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner } 1358c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner 1359fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman Value *RI = !TrueValue ? 13601d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst::Create(BI->getContext(), BI) : 13611d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst::Create(BI->getContext(), TrueValue, BI); 1362e317bcc74c1f317f913e9b05db385901cfc54d0bDaniel Dunbar (void) RI; 1363c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner 136489d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" 1365bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << "\n " << *BI << "NewRet = " << *RI 1366bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc); 1367c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner 1368080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman EraseTerminatorInstAndDCECond(BI); 1369080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman 1370c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner return true; 1371c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner} 1372c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner 13731347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch, 13741347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner/// and if a predecessor branches to us and one of our successors, fold the 13751347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner/// setcc into the predecessor and use logical operations to pick the right 13761347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner/// destination. 13774b35f83b91a1a313f0730c600e5178aaf7df98d6Dan Gohmanbool llvm::FoldBranchToCommonDest(BranchInst *BI) { 1378093a4385027235459ab6972b2e2fdc79061773cfChris Lattner BasicBlock *BB = BI->getParent(); 13791347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); 13801347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner if (Cond == 0) return false; 13811347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner 1382093a4385027235459ab6972b2e2fdc79061773cfChris Lattner 13831347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner // Only allow this if the condition is a simple instruction that can be 13841347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner // executed unconditionally. It must be in the same block as the branch, and 13851347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner // must be at the front of the block. 1386d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel BasicBlock::iterator FrontIt = BB->front(); 1387d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel // Ignore dbg intrinsics. 1388d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel while(isa<DbgInfoIntrinsic>(FrontIt)) 1389d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel ++FrontIt; 13901347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner if ((!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) || 1391d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel Cond->getParent() != BB || &*FrontIt != Cond || !Cond->hasOneUse()) { 13921347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner return false; 1393d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel } 13946ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner 13951347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner // Make sure the instruction after the condition is the cond branch. 13961347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner BasicBlock::iterator CondIt = Cond; ++CondIt; 1397d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel // Ingore dbg intrinsics. 1398d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel while(isa<DbgInfoIntrinsic>(CondIt)) 1399d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel ++CondIt; 1400d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel if (&*CondIt != BI) { 1401d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel assert (!isa<DbgInfoIntrinsic>(CondIt) && "Hey do not forget debug info!"); 14021347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner return false; 1403d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel } 14046ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner 14056ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner // Cond is known to be a compare or binary operator. Check to make sure that 14066ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner // neither operand is a potentially-trapping constant expression. 14076ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0))) 14086ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner if (CE->canTrap()) 14096ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner return false; 14106ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1))) 14116ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner if (CE->canTrap()) 14126ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner return false; 14136ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner 14141347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner 14151347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner // Finally, don't infinitely unroll conditional loops. 14161347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner BasicBlock *TrueDest = BI->getSuccessor(0); 14171347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner BasicBlock *FalseDest = BI->getSuccessor(1); 14181347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner if (TrueDest == BB || FalseDest == BB) 14191347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner return false; 14201347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner 14211347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 14221347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner BasicBlock *PredBlock = *PI; 14231347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator()); 14246ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner 1425093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // Check that we have two conditional branches. If there is a PHI node in 1426093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // the common successor, verify that the same value flows in from both 1427093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // blocks. 14281347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner if (PBI == 0 || PBI->isUnconditional() || 14291347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner !SafeToMergeTerminators(BI, PBI)) 14301347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner continue; 14311347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner 14323698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner Instruction::BinaryOps Opc; 14333698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner bool InvertPredCond = false; 14343698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner 14353698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner if (PBI->getSuccessor(0) == TrueDest) 14363698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner Opc = Instruction::Or; 14373698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner else if (PBI->getSuccessor(1) == FalseDest) 14383698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner Opc = Instruction::And; 14393698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner else if (PBI->getSuccessor(0) == FalseDest) 14403698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner Opc = Instruction::And, InvertPredCond = true; 14413698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner else if (PBI->getSuccessor(1) == TrueDest) 14423698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner Opc = Instruction::Or, InvertPredCond = true; 14433698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner else 14443698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner continue; 14453698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner 144689d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB); 14476ff645bf0fcfc0c62e9d9126e1243ec8bf10abbcChris Lattner 14483698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner // If we need to invert the condition in the pred block to match, do so now. 14493698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner if (InvertPredCond) { 14501347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner Value *NewCond = 14514ae5126d041768ab9665cf2f11c024becd76c41fDan Gohman BinaryOperator::CreateNot(PBI->getCondition(), 14523698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner PBI->getCondition()->getName()+".not", PBI); 14531347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner PBI->setCondition(NewCond); 14541347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner BasicBlock *OldTrue = PBI->getSuccessor(0); 14551347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner BasicBlock *OldFalse = PBI->getSuccessor(1); 14561347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner PBI->setSuccessor(0, OldFalse); 14571347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner PBI->setSuccessor(1, OldTrue); 14581347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner } 145970087f31f154156bcb494dd0cf3b7d74c0c8b528Chris Lattner 14603698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner // Clone Cond into the predecessor basic block, and or/and the 14613698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner // two conditions together. 14626776064d190701c5bae4d5403939eed2e480d1cdNick Lewycky Instruction *New = Cond->clone(); 14633698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner PredBlock->getInstList().insert(PBI, New); 14643698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner New->takeName(Cond); 14653698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner Cond->setName(New->getName()+".old"); 146670087f31f154156bcb494dd0cf3b7d74c0c8b528Chris Lattner 14673698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner Value *NewCond = BinaryOperator::Create(Opc, PBI->getCondition(), 14683698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner New, "or.cond", PBI); 14693698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner PBI->setCondition(NewCond); 14703698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner if (PBI->getSuccessor(0) == BB) { 14713698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner AddPredecessorToBlock(TrueDest, PredBlock, BB); 14723698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner PBI->setSuccessor(0, TrueDest); 14733698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner } 14743698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner if (PBI->getSuccessor(1) == BB) { 14753698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner AddPredecessorToBlock(FalseDest, PredBlock, BB); 14763698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner PBI->setSuccessor(1, FalseDest); 14771347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner } 14783698909623f994826b6a11fc4ea37e4b425a9589Chris Lattner return true; 14791347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner } 14801347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner return false; 14811347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner} 14821347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner 1483867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner/// SimplifyCondBranchToCondBranch - If we have a conditional branch as a 1484867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner/// predecessor of another block, this function tries to simplify it. We know 1485867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner/// that PBI and BI are both conditional branches, and BI is in one of the 1486867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner/// successor blocks of PBI - PBI branches to BI. 1487867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattnerstatic bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { 1488867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner assert(PBI->isConditional() && BI->isConditional()); 1489867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner BasicBlock *BB = BI->getParent(); 14904ae5126d041768ab9665cf2f11c024becd76c41fDan Gohman 1491867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // If this block ends with a branch instruction, and if there is a 1492867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // predecessor that ends on a branch of the same condition, make 1493867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // this conditional branch redundant. 1494867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner if (PBI->getCondition() == BI->getCondition() && 1495867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 1496867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // Okay, the outcome of this conditional branch is statically 1497867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // knowable. If this block had a single pred, handle specially. 1498867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner if (BB->getSinglePredecessor()) { 1499867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // Turn this into a branch on constant. 1500867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner bool CondIsTrue = PBI->getSuccessor(0) == BB; 15011d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 15021d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson CondIsTrue)); 1503867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner return true; // Nuke the branch on constant. 1504867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner } 1505867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner 1506867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // Otherwise, if there are multiple predecessors, insert a PHI that merges 1507867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // in the constant and simplify the block result. Subsequent passes of 1508867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // simplifycfg will thread the block. 1509867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner if (BlockIsSimpleEnoughToThreadThrough(BB)) { 15101d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()), 1511867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner BI->getCondition()->getName() + ".pr", 1512867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner BB->begin()); 1513eb388af89f15ee3de6f53359473e1a54418a667fChris Lattner // Okay, we're going to insert the PHI node. Since PBI is not the only 1514eb388af89f15ee3de6f53359473e1a54418a667fChris Lattner // predecessor, compute the PHI'd conditional value for all of the preds. 1515eb388af89f15ee3de6f53359473e1a54418a667fChris Lattner // Any predecessor where the condition is not computable we keep symbolic. 1516867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 1517867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner if ((PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) && 1518867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner PBI != BI && PBI->isConditional() && 1519867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner PBI->getCondition() == BI->getCondition() && 1520867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 1521867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner bool CondIsTrue = PBI->getSuccessor(0) == BB; 15221d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 1523867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner CondIsTrue), *PI); 1524867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner } else { 1525867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner NewPN->addIncoming(BI->getCondition(), *PI); 1526867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner } 1527867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner 1528867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner BI->setCondition(NewPN); 1529867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner return true; 1530867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner } 1531867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner } 1532867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner 1533867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // If this is a conditional branch in an empty block, and if any 1534867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // predecessors is a conditional branch to one of our destinations, 1535867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // fold the conditions into logical ops and one cond br. 1536a8d57fe96bb870e4f69c6b522a78936d1495d0d2Zhou Sheng BasicBlock::iterator BBI = BB->begin(); 1537a8d57fe96bb870e4f69c6b522a78936d1495d0d2Zhou Sheng // Ignore dbg intrinsics. 1538a8d57fe96bb870e4f69c6b522a78936d1495d0d2Zhou Sheng while (isa<DbgInfoIntrinsic>(BBI)) 1539a8d57fe96bb870e4f69c6b522a78936d1495d0d2Zhou Sheng ++BBI; 1540a8d57fe96bb870e4f69c6b522a78936d1495d0d2Zhou Sheng if (&*BBI != BI) 1541b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner return false; 154263bf29b5b1c741038d6d502d62721cac0d2760b4Chris Lattner 154363bf29b5b1c741038d6d502d62721cac0d2760b4Chris Lattner 154463bf29b5b1c741038d6d502d62721cac0d2760b4Chris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BI->getCondition())) 154563bf29b5b1c741038d6d502d62721cac0d2760b4Chris Lattner if (CE->canTrap()) 154663bf29b5b1c741038d6d502d62721cac0d2760b4Chris Lattner return false; 1547b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner 1548b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner int PBIOp, BIOp; 1549b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner if (PBI->getSuccessor(0) == BI->getSuccessor(0)) 1550b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PBIOp = BIOp = 0; 1551b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) 1552b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PBIOp = 0, BIOp = 1; 1553b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) 1554b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PBIOp = 1, BIOp = 0; 1555b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) 1556b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PBIOp = BIOp = 1; 1557b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner else 1558b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner return false; 1559867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner 1560b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // Check to make sure that the other destination of this branch 1561b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // isn't BB itself. If so, this is an infinite loop that will 1562b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // keep getting unwound. 1563b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner if (PBI->getSuccessor(PBIOp) == BB) 1564b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner return false; 1565867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner 1566b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // Do not perform this transformation if it would require 1567b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // insertion of a large number of select instructions. For targets 1568b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // without predication/cmovs, this is a big pessimization. 1569b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 1570867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner 1571b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner unsigned NumPhis = 0; 1572b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner for (BasicBlock::iterator II = CommonDest->begin(); 1573b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner isa<PHINode>(II); ++II, ++NumPhis) 1574b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner if (NumPhis > 2) // Disable this xform. 1575b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner return false; 1576867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner 1577b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // Finally, if everything is ok, fold the branches to logical ops. 1578b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); 1579b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner 158089d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent() 1581bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << "AND: " << *BI->getParent()); 1582b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner 1583093a4385027235459ab6972b2e2fdc79061773cfChris Lattner 1584093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // If OtherDest *is* BB, then BB is a basic block with a single conditional 1585093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // branch in it, where one edge (OtherDest) goes back to itself but the other 1586093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // exits. We don't *know* that the program avoids the infinite loop 1587093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // (even though that seems likely). If we do this xform naively, we'll end up 1588093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // recursively unpeeling the loop. Since we know that (after the xform is 1589093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // done) that the block *is* infinite if reached, we just make it an obviously 1590093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // infinite loop with no cond branch. 1591093a4385027235459ab6972b2e2fdc79061773cfChris Lattner if (OtherDest == BB) { 1592093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // Insert it at the end of the function, because it's either code, 1593093a4385027235459ab6972b2e2fdc79061773cfChris Lattner // or it won't matter if it's hot. :) 15941d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(), 15951d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "infloop", BB->getParent()); 1596093a4385027235459ab6972b2e2fdc79061773cfChris Lattner BranchInst::Create(InfLoopBlock, InfLoopBlock); 1597093a4385027235459ab6972b2e2fdc79061773cfChris Lattner OtherDest = InfLoopBlock; 1598093a4385027235459ab6972b2e2fdc79061773cfChris Lattner } 1599093a4385027235459ab6972b2e2fdc79061773cfChris Lattner 160089d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << *PBI->getParent()->getParent()); 1601b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner 1602b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // BI may have other predecessors. Because of this, we leave 1603b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // it alone, but modify PBI. 1604b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner 1605b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // Make sure we get to CommonDest on True&True directions. 1606b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner Value *PBICond = PBI->getCondition(); 1607b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner if (PBIOp) 16084ae5126d041768ab9665cf2f11c024becd76c41fDan Gohman PBICond = BinaryOperator::CreateNot(PBICond, 1609b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PBICond->getName()+".not", 1610b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PBI); 1611b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner Value *BICond = BI->getCondition(); 1612b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner if (BIOp) 16134ae5126d041768ab9665cf2f11c024becd76c41fDan Gohman BICond = BinaryOperator::CreateNot(BICond, 1614b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner BICond->getName()+".not", 1615b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PBI); 1616b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // Merge the conditions. 1617b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner Value *Cond = BinaryOperator::CreateOr(PBICond, BICond, "brmerge", PBI); 1618b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner 1619b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // Modify PBI to branch on the new condition to the new dests. 1620b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PBI->setCondition(Cond); 1621b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PBI->setSuccessor(0, CommonDest); 1622b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PBI->setSuccessor(1, OtherDest); 1623b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner 1624b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // OtherDest may have phi nodes. If so, add an entry from PBI's 1625b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // block that are identical to the entries for BI's block. 1626b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PHINode *PN; 1627b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner for (BasicBlock::iterator II = OtherDest->begin(); 1628b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner (PN = dyn_cast<PHINode>(II)); ++II) { 1629b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner Value *V = PN->getIncomingValueForBlock(BB); 1630b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PN->addIncoming(V, PBI->getParent()); 1631b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner } 1632b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner 1633b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // We know that the CommonDest already had an edge from PBI to 1634b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // it. If it has PHIs though, the PHIs may have different 1635b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // entries for BB and PBI's BB. If so, insert a select to make 1636b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // them agree. 1637b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner for (BasicBlock::iterator II = CommonDest->begin(); 1638b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner (PN = dyn_cast<PHINode>(II)); ++II) { 1639b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner Value *BIV = PN->getIncomingValueForBlock(BB); 1640b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); 1641b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner Value *PBIV = PN->getIncomingValue(PBBIdx); 1642b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner if (BIV != PBIV) { 1643b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // Insert a select in PBI to pick the right value. 1644b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner Value *NV = SelectInst::Create(PBICond, PBIV, BIV, 1645b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PBIV->getName()+".mux", PBI); 1646b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner PN->setIncomingValue(PBBIdx, NV); 1647867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner } 1648867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner } 1649b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner 165089d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << "INTO: " << *PBI->getParent()); 165189d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << *PBI->getParent()->getParent()); 1652b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner 1653b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // This basic block is probably dead. We know it has at least 1654b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner // one fewer predecessor. 1655b824512b8d733ccdfb1b1a2e8a6950605acf1c52Chris Lattner return true; 1656867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner} 1657867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner 165858e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesenbool SimplifyCFGOpt::run(BasicBlock *BB) { 1659dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner bool Changed = false; 166001d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner Function *M = BB->getParent(); 166101d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 166201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB && BB->getParent() && "Block not embedded in function!"); 166301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner assert(BB->getTerminator() && "Degenerate basic block encountered!"); 1664ecb7a77885b174cf4d001a9b48533b3979e7810dDan Gohman assert(&BB->getParent()->getEntryBlock() != BB && 1665ecb7a77885b174cf4d001a9b48533b3979e7810dDan Gohman "Can't Simplify entry block!"); 166601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 16675a5c9a5acd5f90ec3815f4871c66e224902588ceChris Lattner // Remove basic blocks that have no predecessors... or that just have themself 16685a5c9a5acd5f90ec3815f4871c66e224902588ceChris Lattner // as a predecessor. These are unreachable. 16695a5c9a5acd5f90ec3815f4871c66e224902588ceChris Lattner if (pred_begin(BB) == pred_end(BB) || BB->getSinglePredecessor() == BB) { 167089d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << "Removing BB: \n" << *BB); 167171af9b07a58a264064813545889cf6473ce23de6Chris Lattner DeleteDeadBlock(BB); 167201d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner return true; 167301d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner } 167401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner 1675694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // Check to see if we can constant propagate this terminator instruction 1676694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner // away... 1677dc3602bf0d27aac80e08ef8823967850acd05a14Chris Lattner Changed |= ConstantFoldTerminator(BB); 1678694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner 16792c63566e406974caa70ee27f35af28112e80f951Dan Gohman // Check for and eliminate duplicate PHI nodes in this block. 16802c63566e406974caa70ee27f35af28112e80f951Dan Gohman Changed |= EliminateDuplicatePHINodes(BB); 16812c63566e406974caa70ee27f35af28112e80f951Dan Gohman 1682882d87d168374ce790621e9ad4d7304b9dff0d78Dan Gohman // If there is a trivial two-entry PHI node in this basic block, and we can 1683882d87d168374ce790621e9ad4d7304b9dff0d78Dan Gohman // eliminate it, do so now. 1684882d87d168374ce790621e9ad4d7304b9dff0d78Dan Gohman if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 1685882d87d168374ce790621e9ad4d7304b9dff0d78Dan Gohman if (PN->getNumIncomingValues() == 2) 1686882d87d168374ce790621e9ad4d7304b9dff0d78Dan Gohman Changed |= FoldTwoEntryPHINode(PN); 1687882d87d168374ce790621e9ad4d7304b9dff0d78Dan Gohman 168819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If this is a returning block with only PHI nodes in it, fold the return 168919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // instruction into any unconditional branch predecessors. 1690147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // 1691147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // If any predecessor is a conditional branch that just selects among 1692147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // different return values, fold the replace the branch/return with a select 1693147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // and return. 169419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 16952cc86a1de1cf598be384836f19d1ef1892fb50fcDevang Patel if (isTerminatorFirstRelevantInsn(BB, BB->getTerminator())) { 1696147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Find predecessors that end with branches. 16978244243a31d636ce8838a81d4c402274fd391d2bChris Lattner SmallVector<BasicBlock*, 8> UncondBranchPreds; 16988244243a31d636ce8838a81d4c402274fd391d2bChris Lattner SmallVector<BranchInst*, 8> CondBranchPreds; 169919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 170019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner TerminatorInst *PTI = (*PI)->getTerminator(); 170107e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) { 170219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (BI->isUnconditional()) 170319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner UncondBranchPreds.push_back(*PI); 1704147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner else 1705147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner CondBranchPreds.push_back(BI); 170607e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov } 170719831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 1708fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 170919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we found some, do the transformation! 17101c85503e381423f20769582b6ab169bce9cfe2a2Bill Wendling if (!UncondBranchPreds.empty()) { 171119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner while (!UncondBranchPreds.empty()) { 1712e9d87f49063cb1bd213d8e9c339b9b63393cc2d9Dan Gohman BasicBlock *Pred = UncondBranchPreds.pop_back_val(); 171389d6fd36a26fdf068ceea90422dc2897e89700b5David Greene DEBUG(dbgs() << "FOLDING: " << *BB 1714bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner << "INTO UNCOND BRANCH PRED: " << *Pred); 171519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Instruction *UncondBranch = Pred->getTerminator(); 171619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Clone the return and add it to the end of the predecessor. 17176776064d190701c5bae4d5403939eed2e480d1cdNick Lewycky Instruction *NewRet = RI->clone(); 171819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().push_back(NewRet); 171919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 172019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If the return instruction returns a value, and if the value was a 172119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // PHI node in "BB", propagate the right value into the return. 1722f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end(); 1723f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif i != e; ++i) 1724f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif if (PHINode *PN = dyn_cast<PHINode>(*i)) 172519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (PN->getParent() == BB) 1726f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif *i = PN->getIncomingValueForBlock(Pred); 1727ffba5821eee7b7a6139f9dfb06b8d306bf344a9dChris Lattner 172819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // Update any PHI nodes in the returning block to realize that we no 172919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // longer branch to them. 173019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner BB->removePredecessor(Pred); 173119831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner Pred->getInstList().erase(UncondBranch); 173219831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 173319831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 173419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // If we eliminated all predecessors of the block, delete the block now. 173519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner if (pred_begin(BB) == pred_end(BB)) 173619831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner // We know there are no successors, so just nuke the block. 17375622f07a21b799964dc172925b9ebc38191859f6Devang Patel M->getBasicBlockList().erase(BB); 173819831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 173919831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner return true; 174019831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 1741147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1742147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check out all of the conditional branches going to this return 1743147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // instruction. If any of them just select between returns, change the 1744147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // branch itself into a select/return pair. 1745147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner while (!CondBranchPreds.empty()) { 1746e9d87f49063cb1bd213d8e9c339b9b63393cc2d9Dan Gohman BranchInst *BI = CondBranchPreds.pop_back_val(); 1747147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner 1748147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner // Check to see if the non-BB successor is also a return block. 1749c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) && 1750c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) && 1751c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner SimplifyCondBranchToTwoReturns(BI)) 1752c9e495c534b95a72502d1840293e66fa2e2d6882Chris Lattner return true; 1753147af6b75f2e9a71baf46a12cf1312f627f1590bChris Lattner } 175419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 17553ed469ccd7b028a030b550d84b7336d146f5d8faReid Spencer } else if (isa<UnwindInst>(BB->begin())) { 1756e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Check to see if the first instruction in this block is just an unwind. 1757e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // If so, replace any invoke instructions which use this as an exception 175811f15dbb287b5d9aa63913f84ce931569a5ebdf3Chris Lattner // destination with call instructions. 1759e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // 17608244243a31d636ce8838a81d4c402274fd391d2bChris Lattner SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 1761e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner while (!Preds.empty()) { 1762e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner BasicBlock *Pred = Preds.back(); 176311f15dbb287b5d9aa63913f84ce931569a5ebdf3Chris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 1764e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner if (II->getUnwindDest() == BB) { 1765e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner // Insert a new branch instruction before the invoke, because this 176611f15dbb287b5d9aa63913f84ce931569a5ebdf3Chris Lattner // is now a fall through. 1767051a950000e21935165db56695e35bade668193bGabor Greif BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); 1768e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Pred->getInstList().remove(II); // Take out of symbol table 1769fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 177011f15dbb287b5d9aa63913f84ce931569a5ebdf3Chris Lattner // Insert the call now. 177193e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner SmallVector<Value*,8> Args(II->op_begin()+3, II->op_end()); 1772051a950000e21935165db56695e35bade668193bGabor Greif CallInst *CI = CallInst::Create(II->getCalledValue(), 1773f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif Args.begin(), Args.end(), 1774f7ea3638e0f85a9793e7c9f081ed6ddb1ebb832eGabor Greif II->getName(), BI); 177516d0db2da8c274f98db4a89ca7a92f970d464b9aChris Lattner CI->setCallingConv(II->getCallingConv()); 17760598866c052147c31b808391f58434ce3dbfb838Devang Patel CI->setAttributes(II->getAttributes()); 177711f15dbb287b5d9aa63913f84ce931569a5ebdf3Chris Lattner // If the invoke produced a value, the Call now does instead. 1778e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner II->replaceAllUsesWith(CI); 1779e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner delete II; 1780e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Changed = true; 1781e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 1782fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1783e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner Preds.pop_back(); 1784e14ea0804afba2ac5824507571a220d05b0aa21dChris Lattner } 17858e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 17868e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // If this block is now dead, remove it. 17878e509dd5e81e92a466580ab4022994079952cca9Chris Lattner if (pred_begin(BB) == pred_end(BB)) { 17888e509dd5e81e92a466580ab4022994079952cca9Chris Lattner // We know there are no successors, so just nuke the block. 17898e509dd5e81e92a466580ab4022994079952cca9Chris Lattner M->getBasicBlockList().erase(BB); 17908e509dd5e81e92a466580ab4022994079952cca9Chris Lattner return true; 17918e509dd5e81e92a466580ab4022994079952cca9Chris Lattner } 17928e509dd5e81e92a466580ab4022994079952cca9Chris Lattner 1793623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1794623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (isValueEqualityComparison(SI)) { 1795623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we only have one predecessor, and if it is a branch on this value, 1796623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // see if that predecessor totally determines the outcome of this switch. 1797623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1798623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) 1799623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1800623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 1801623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If the block only contains the switch, see if we can fold the block 1802623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // away into any preds. 18039a7c743fc0d45e4f2331c4092d3f29bf18351e6fZhou Sheng BasicBlock::iterator BBI = BB->begin(); 18049a7c743fc0d45e4f2331c4092d3f29bf18351e6fZhou Sheng // Ignore dbg intrinsics. 18059a7c743fc0d45e4f2331c4092d3f29bf18351e6fZhou Sheng while (isa<DbgInfoIntrinsic>(BBI)) 18069a7c743fc0d45e4f2331c4092d3f29bf18351e6fZhou Sheng ++BBI; 18079a7c743fc0d45e4f2331c4092d3f29bf18351e6fZhou Sheng if (SI == &*BBI) 1808623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (FoldValueComparisonIntoPredecessors(SI)) 1809623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1810623369ac5669a3667a94a3cbba342dea78845615Chris Lattner } 1811542f149f00afaf1125b8f2040cad4fe05ed24c3aChris Lattner } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 18127e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner if (BI->isUnconditional()) { 181302dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator BBI = BB->getFirstNonPHI(); 18147e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 1815d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel // Ignore dbg intrinsics. 1816d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel while (isa<DbgInfoIntrinsic>(BBI)) 1817d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel ++BBI; 1818dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (BBI->isTerminator()) // Terminator is the only non-phi instruction! 1819dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) 18201347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner return true; 18217e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner 18227e66348cba4384d07b37ad1c186e67ba6d26babdChris Lattner } else { // Conditional branch 18233ed469ccd7b028a030b550d84b7336d146f5d8faReid Spencer if (isValueEqualityComparison(BI)) { 1824623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // If we only have one predecessor, and if it is a branch on this value, 1825623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // see if that predecessor totally determines the outcome of this 1826623369ac5669a3667a94a3cbba342dea78845615Chris Lattner // switch. 1827623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1828623369ac5669a3667a94a3cbba342dea78845615Chris Lattner if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) 1829623369ac5669a3667a94a3cbba342dea78845615Chris Lattner return SimplifyCFG(BB) || 1; 1830623369ac5669a3667a94a3cbba342dea78845615Chris Lattner 1831e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // This block must be empty, except for the setcond inst, if it exists. 1832556b20ab46520ac53bb689d3c70160bc9d496a3fDevang Patel // Ignore dbg intrinsics. 1833e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner BasicBlock::iterator I = BB->begin(); 1834d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel // Ignore dbg intrinsics. 1835556b20ab46520ac53bb689d3c70160bc9d496a3fDevang Patel while (isa<DbgInfoIntrinsic>(I)) 1836d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel ++I; 1837d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel if (&*I == BI) { 1838e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner if (FoldValueComparisonIntoPredecessors(BI)) 1839e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner return SimplifyCFG(BB) | true; 1840d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel } else if (&*I == cast<Instruction>(BI->getCondition())){ 1841d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel ++I; 1842d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel // Ignore dbg intrinsics. 1843d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel while (isa<DbgInfoIntrinsic>(I)) 1844d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel ++I; 1845d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel if(&*I == BI) { 1846d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel if (FoldValueComparisonIntoPredecessors(BI)) 1847d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel return SimplifyCFG(BB) | true; 1848d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel } 1849d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel } 1850e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner } 1851d0a203d76f4ef77ae1c392e8e73e2f05b676a5f2Devang Patel 1852eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // If this is a branch on a phi node in the current block, thread control 1853eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner // through this block if any PHI node entries are constants. 1854eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 1855eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (PN->getParent() == BI->getParent()) 1856eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner if (FoldCondBranchOnPHI(BI)) 1857eaba3a194c23ecbfc5f3da439d1ef7a08eedf02cChris Lattner return SimplifyCFG(BB) | true; 1858e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 1859e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // If this basic block is ONLY a setcc and a branch, and if a predecessor 1860e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // branches to us and one of our successors, fold the setcc into the 1861e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner // predecessor and use logical operations to pick the right destination. 18621347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner if (FoldBranchToCommonDest(BI)) 18631347e87c7baa78bd442d7017a8d67bd4fe674e01Chris Lattner return SimplifyCFG(BB) | 1; 1864e67fa05036f634a4ec1e0893033c89250eb58954Chris Lattner 1865867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner 1866867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner // Scan predecessor blocks for conditional branches. 18672e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 18682e42e36698d5a34f1952ca3389f1973a6a1166f2Chris Lattner if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1869867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner if (PBI != BI && PBI->isConditional()) 1870867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner if (SimplifyCondBranchToCondBranch(PBI, BI)) 1871867661ac8bd8e202bd4becf9b8e046bf69e150b1Chris Lattner return SimplifyCFG(BB) | true; 1872d52c261cf801331bebda9711acd54c7c5377a6bdChris Lattner } 1873698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (isa<UnreachableInst>(BB->getTerminator())) { 1874698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If there are any instructions immediately before the unreachable that can 1875698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // be removed, do so. 1876698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Instruction *Unreachable = BB->getTerminator(); 1877698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner while (Unreachable != BB->begin()) { 1878698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock::iterator BBI = Unreachable; 1879698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --BBI; 1880f8131c99de2ac66be4307ae24f2db44d12bc9b3fChris Lattner // Do not delete instructions that can have side effects, like calls 1881f8131c99de2ac66be4307ae24f2db44d12bc9b3fChris Lattner // (which may never return) and volatile loads and stores. 188280b8a62fda56179b00fe463ae55d712aa8abefecDale Johannesen if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break; 1883f8131c99de2ac66be4307ae24f2db44d12bc9b3fChris Lattner 1884f8131c99de2ac66be4307ae24f2db44d12bc9b3fChris Lattner if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) 1885f8131c99de2ac66be4307ae24f2db44d12bc9b3fChris Lattner if (SI->isVolatile()) 1886f8131c99de2ac66be4307ae24f2db44d12bc9b3fChris Lattner break; 1887f8131c99de2ac66be4307ae24f2db44d12bc9b3fChris Lattner 1888f8131c99de2ac66be4307ae24f2db44d12bc9b3fChris Lattner if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) 1889f8131c99de2ac66be4307ae24f2db44d12bc9b3fChris Lattner if (LI->isVolatile()) 1890f8131c99de2ac66be4307ae24f2db44d12bc9b3fChris Lattner break; 1891f8131c99de2ac66be4307ae24f2db44d12bc9b3fChris Lattner 1892698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Delete this instruction 1893698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BB->getInstList().erase(BBI); 1894698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1895698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1896698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1897698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the unreachable instruction is the first in the block, take a gander 1898698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // at all of the predecessors of this instruction, and simplify them. 1899698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (&BB->front() == Unreachable) { 19008244243a31d636ce8838a81d4c402274fd391d2bChris Lattner SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 1901698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 1902698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TerminatorInst *TI = Preds[i]->getTerminator(); 1903698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1904698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1905698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->isUnconditional()) { 1906698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 19071d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson new UnreachableInst(TI->getContext(), TI); 1908698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner TI->eraseFromParent(); 1909698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1910698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1911698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else { 1912698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (BI->getSuccessor(0) == BB) { 1913051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(BI->getSuccessor(1), BI); 1914080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman EraseTerminatorInstAndDCECond(BI); 1915698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (BI->getSuccessor(1) == BB) { 1916051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(BI->getSuccessor(0), BI); 1917080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman EraseTerminatorInstAndDCECond(BI); 1918698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1919698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1920698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1921698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1922698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1923698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == BB) { 192442eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner BB->removePredecessor(SI->getParent()); 1925698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1926698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1927698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1928698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1929698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the default value is unreachable, figure out the most popular 1930698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // destination and make it the default. 1931698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(0) == BB) { 1932698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner std::map<BasicBlock*, unsigned> Popularity; 1933698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1934698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Popularity[SI->getSuccessor(i)]++; 1935698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1936698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Find the most popular block. 1937698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner unsigned MaxPop = 0; 1938698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner BasicBlock *MaxBlock = 0; 1939698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (std::map<BasicBlock*, unsigned>::iterator 1940698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 1941698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (I->second > MaxPop) { 1942698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxPop = I->second; 1943698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner MaxBlock = I->first; 1944698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1945698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1946698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (MaxBlock) { 1947698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Make this the new default, allowing us to delete any explicit 1948698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // edges to it. 1949698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->setSuccessor(0, MaxBlock); 1950698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1951698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 195242eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 195342eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner // it. 195442eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner if (isa<PHINode>(MaxBlock->begin())) 195542eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner for (unsigned i = 0; i != MaxPop-1; ++i) 195642eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner MaxBlock->removePredecessor(SI->getParent()); 195742eb7524ef3a994f184924e583871406cf5d1ed6Chris Lattner 1958698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1959698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (SI->getSuccessor(i) == MaxBlock) { 1960698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner SI->removeCase(i); 1961698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner --i; --e; 1962698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1963698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1964698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1965698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 1966698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (II->getUnwindDest() == BB) { 1967698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Convert the invoke to a call instruction. This would be a good 1968698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // place to note that the call does not throw though. 1969051a950000e21935165db56695e35bade668193bGabor Greif BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); 1970698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->removeFromParent(); // Take out of symbol table 1971fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 1972698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // Insert the call now... 197393e985f1b17aef62d58e3198a4604f9f6cfe8d19Chris Lattner SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); 1974051a950000e21935165db56695e35bade668193bGabor Greif CallInst *CI = CallInst::Create(II->getCalledValue(), 1975051a950000e21935165db56695e35bade668193bGabor Greif Args.begin(), Args.end(), 1976051a950000e21935165db56695e35bade668193bGabor Greif II->getName(), BI); 197716d0db2da8c274f98db4a89ca7a92f970d464b9aChris Lattner CI->setCallingConv(II->getCallingConv()); 19780598866c052147c31b808391f58434ce3dbfb838Devang Patel CI->setAttributes(II->getAttributes()); 1979698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If the invoke produced a value, the Call does now instead. 1980698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner II->replaceAllUsesWith(CI); 1981698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner delete II; 1982698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner Changed = true; 1983698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1984698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1985698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1986698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner 1987698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // If this block is now dead, remove it. 1988698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner if (pred_begin(BB) == pred_end(BB)) { 1989698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner // We know there are no successors, so just nuke the block. 1990698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner M->getBasicBlockList().erase(BB); 1991698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner return true; 1992698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 1993698f96f7c81e45292ae4f5d76b8e06c88a88a71fChris Lattner } 199419831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner } 199519831ec8531b0710629c1b0a8c0323e70ae0ef07Chris Lattner 199601d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // Merge basic blocks into their predecessor if there is only one distinct 199701d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // pred, and if there is only one distinct successor of the predecessor, and 199801d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // if there are no PHI nodes. 199901d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner // 2000cfa94198d5a75776a600df8113ac565b25552399Owen Anderson if (MergeBlockIntoPredecessor(BB)) 2001cfa94198d5a75776a600df8113ac565b25552399Owen Anderson return true; 2002cfa94198d5a75776a600df8113ac565b25552399Owen Anderson 2003cfa94198d5a75776a600df8113ac565b25552399Owen Anderson // Otherwise, if this block only has a single predecessor, and if that block 2004cfa94198d5a75776a600df8113ac565b25552399Owen Anderson // is a conditional branch, see if we can hoist any code from this block up 2005cfa94198d5a75776a600df8113ac565b25552399Owen Anderson // into our predecessor. 20062355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 20072355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner BasicBlock *OnlyPred = *PI++; 20082355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 20092355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner if (*PI != OnlyPred) { 20102355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner OnlyPred = 0; // There are multiple different predecessors... 20112355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner break; 20122355f948c59a2b4a78667d6898333524f9b78f27Chris Lattner } 2013cfa94198d5a75776a600df8113ac565b25552399Owen Anderson 201437dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner if (OnlyPred) 20157613437db954abafd1230c961e87872df5721957Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 20167613437db954abafd1230c961e87872df5721957Chris Lattner if (BI->isConditional()) { 20177613437db954abafd1230c961e87872df5721957Chris Lattner // Get the other block. 20187613437db954abafd1230c961e87872df5721957Chris Lattner BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); 20197613437db954abafd1230c961e87872df5721957Chris Lattner PI = pred_begin(OtherBB); 20207613437db954abafd1230c961e87872df5721957Chris Lattner ++PI; 2021cfa94198d5a75776a600df8113ac565b25552399Owen Anderson 20227613437db954abafd1230c961e87872df5721957Chris Lattner if (PI == pred_end(OtherBB)) { 20237613437db954abafd1230c961e87872df5721957Chris Lattner // We have a conditional branch to two blocks that are only reachable 20247613437db954abafd1230c961e87872df5721957Chris Lattner // from the condbr. We know that the condbr dominates the two blocks, 20257613437db954abafd1230c961e87872df5721957Chris Lattner // so see if there is any identical code in the "then" and "else" 20267613437db954abafd1230c961e87872df5721957Chris Lattner // blocks. If so, we can hoist it up to the branching block. 20277613437db954abafd1230c961e87872df5721957Chris Lattner Changed |= HoistThenElseCodeToIf(BI); 20284d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng } else { 2029cfa94198d5a75776a600df8113ac565b25552399Owen Anderson BasicBlock* OnlySucc = NULL; 20304d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 20314d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng SI != SE; ++SI) { 20324d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng if (!OnlySucc) 20334d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng OnlySucc = *SI; 20344d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng else if (*SI != OnlySucc) { 20354d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng OnlySucc = 0; // There are multiple distinct successors! 20364d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng break; 20374d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng } 20384d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng } 20394d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng 20404d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng if (OnlySucc == OtherBB) { 20414d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // If BB's only successor is the other successor of the predecessor, 20424d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // i.e. a triangle, see if we can hoist any code from this block up 20434d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng // to the "if" block. 20444d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng Changed |= SpeculativelyExecuteBB(BI, BB); 20454d09efd7b8fdf9e8a8c89bdb821f4992091a764bEvan Cheng } 20467613437db954abafd1230c961e87872df5721957Chris Lattner } 204737dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner } 204837dc938bbe556a9414d063196d367c2f75d07d95Chris Lattner 20490d56008f53587531718ec36af82cc24576580b36Chris Lattner for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 20500d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 20510d56008f53587531718ec36af82cc24576580b36Chris Lattner // Change br (X == 0 | X == 1), T, F into a switch instruction. 20520d56008f53587531718ec36af82cc24576580b36Chris Lattner if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 20530d56008f53587531718ec36af82cc24576580b36Chris Lattner Instruction *Cond = cast<Instruction>(BI->getCondition()); 20540d56008f53587531718ec36af82cc24576580b36Chris Lattner // If this is a bunch of seteq's or'd together, or if it's a bunch of 20550d56008f53587531718ec36af82cc24576580b36Chris Lattner // 'setne's and'ed together, collect them. 20560d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *CompVal = 0; 20571654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::vector<ConstantInt*> Values; 20580d56008f53587531718ec36af82cc24576580b36Chris Lattner bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 205958e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (CompVal) { 20600d56008f53587531718ec36af82cc24576580b36Chris Lattner // There might be duplicate constants in the list, which the switch 20610d56008f53587531718ec36af82cc24576580b36Chris Lattner // instruction can't handle, remove them now. 20621654cff8e80acdddf5e5f2261595007878924aacChris Lattner std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 20630d56008f53587531718ec36af82cc24576580b36Chris Lattner Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 2064fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 20650d56008f53587531718ec36af82cc24576580b36Chris Lattner // Figure out which block is which destination. 20660d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *DefaultBB = BI->getSuccessor(1); 20670d56008f53587531718ec36af82cc24576580b36Chris Lattner BasicBlock *EdgeBB = BI->getSuccessor(0); 20680d56008f53587531718ec36af82cc24576580b36Chris Lattner if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 2069fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 207058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen // Convert pointer to int before we switch. 207158e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen if (isa<PointerType>(CompVal->getType())) { 207258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen assert(TD && "Cannot switch on pointer without TargetData"); 207358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen CompVal = new PtrToIntInst(CompVal, 207458e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen TD->getIntPtrType(CompVal->getContext()), 207558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen "magicptr", BI); 207658e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen } 207758e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen 20780d56008f53587531718ec36af82cc24576580b36Chris Lattner // Create the new switch instruction now. 2079b1dbcd886a4b5597a839f299054b78b33fb2d6dfGabor Greif SwitchInst *New = SwitchInst::Create(CompVal, DefaultBB, 2080b1dbcd886a4b5597a839f299054b78b33fb2d6dfGabor Greif Values.size(), BI); 2081fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 20820d56008f53587531718ec36af82cc24576580b36Chris Lattner // Add all of the 'cases' to the switch instruction. 20830d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size(); i != e; ++i) 20840d56008f53587531718ec36af82cc24576580b36Chris Lattner New->addCase(Values[i], EdgeBB); 2085fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 20860d56008f53587531718ec36af82cc24576580b36Chris Lattner // We added edges from PI to the EdgeBB. As such, if there were any 20870d56008f53587531718ec36af82cc24576580b36Chris Lattner // PHI nodes in EdgeBB, they need entries to be added corresponding to 20880d56008f53587531718ec36af82cc24576580b36Chris Lattner // the number of edges added. 20890d56008f53587531718ec36af82cc24576580b36Chris Lattner for (BasicBlock::iterator BBI = EdgeBB->begin(); 20902da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer isa<PHINode>(BBI); ++BBI) { 20912da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(BBI); 20920d56008f53587531718ec36af82cc24576580b36Chris Lattner Value *InVal = PN->getIncomingValueForBlock(*PI); 20930d56008f53587531718ec36af82cc24576580b36Chris Lattner for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 20940d56008f53587531718ec36af82cc24576580b36Chris Lattner PN->addIncoming(InVal, *PI); 20950d56008f53587531718ec36af82cc24576580b36Chris Lattner } 20960d56008f53587531718ec36af82cc24576580b36Chris Lattner 20970d56008f53587531718ec36af82cc24576580b36Chris Lattner // Erase the old branch instruction. 2098080efb8cea6255b4f1f373d9cb583d6a6302106bEli Friedman EraseTerminatorInstAndDCECond(BI); 20990d56008f53587531718ec36af82cc24576580b36Chris Lattner return true; 21000d56008f53587531718ec36af82cc24576580b36Chris Lattner } 21010d56008f53587531718ec36af82cc24576580b36Chris Lattner } 21020d56008f53587531718ec36af82cc24576580b36Chris Lattner 2103694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner return Changed; 210401d1ee3a4c4153c80c3c415e4612db6c27e37acbChris Lattner} 210558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen 210658e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen/// SimplifyCFG - This function is used to do simplification of a CFG. For 210758e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen/// example, it adjusts branches to branches to eliminate the extra hop, it 210858e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen/// eliminates unreachable basic blocks, and does other "peephole" optimization 210958e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen/// of the CFG. It returns true if a modification was made. 211058e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen/// 211158e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen/// WARNING: The entry node of a function may not be simplified. 211258e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen/// 211358e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesenbool llvm::SimplifyCFG(BasicBlock *BB, const TargetData *TD) { 211458e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen return SimplifyCFGOpt(TD).run(BB); 211558e9ee85fda5083e2eea987917e8eab6ba31fe5eJakob Stoklund Olesen} 2116