SimplifyCFG.cpp revision 203954
1193323Sed//===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// Peephole optimize the CFG. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#define DEBUG_TYPE "simplifycfg" 15193323Sed#include "llvm/Transforms/Utils/Local.h" 16193323Sed#include "llvm/Constants.h" 17193323Sed#include "llvm/Instructions.h" 18193323Sed#include "llvm/IntrinsicInst.h" 19193323Sed#include "llvm/Type.h" 20193323Sed#include "llvm/DerivedTypes.h" 21193323Sed#include "llvm/GlobalVariable.h" 22193323Sed#include "llvm/Support/CFG.h" 23193323Sed#include "llvm/Support/Debug.h" 24198090Srdivacky#include "llvm/Support/raw_ostream.h" 25193323Sed#include "llvm/Analysis/ConstantFolding.h" 26203954Srdivacky#include "llvm/Target/TargetData.h" 27193323Sed#include "llvm/Transforms/Utils/BasicBlockUtils.h" 28198892Srdivacky#include "llvm/ADT/DenseMap.h" 29193323Sed#include "llvm/ADT/SmallVector.h" 30193323Sed#include "llvm/ADT/SmallPtrSet.h" 31193323Sed#include "llvm/ADT/Statistic.h" 32193323Sed#include <algorithm> 33193323Sed#include <functional> 34193323Sed#include <set> 35193323Sed#include <map> 36193323Sedusing namespace llvm; 37193323Sed 38193323SedSTATISTIC(NumSpeculations, "Number of speculative executed instructions"); 39193323Sed 40203954Srdivackynamespace { 41203954Srdivackyclass SimplifyCFGOpt { 42203954Srdivacky const TargetData *const TD; 43203954Srdivacky 44203954Srdivacky ConstantInt *GetConstantInt(Value *V); 45203954Srdivacky Value *GatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values); 46203954Srdivacky Value *GatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values); 47203954Srdivacky bool GatherValueComparisons(Instruction *Cond, Value *&CompVal, 48203954Srdivacky std::vector<ConstantInt*> &Values); 49203954Srdivacky Value *isValueEqualityComparison(TerminatorInst *TI); 50203954Srdivacky BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI, 51203954Srdivacky std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases); 52203954Srdivacky bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 53203954Srdivacky BasicBlock *Pred); 54203954Srdivacky bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI); 55203954Srdivacky 56203954Srdivackypublic: 57203954Srdivacky explicit SimplifyCFGOpt(const TargetData *td) : TD(td) {} 58203954Srdivacky bool run(BasicBlock *BB); 59203954Srdivacky}; 60203954Srdivacky} 61203954Srdivacky 62193323Sed/// SafeToMergeTerminators - Return true if it is safe to merge these two 63193323Sed/// terminator instructions together. 64193323Sed/// 65193323Sedstatic bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 66193323Sed if (SI1 == SI2) return false; // Can't merge with self! 67193323Sed 68193323Sed // It is not safe to merge these two switch instructions if they have a common 69193323Sed // successor, and if that successor has a PHI node, and if *that* PHI node has 70193323Sed // conflicting incoming values from the two switch blocks. 71193323Sed BasicBlock *SI1BB = SI1->getParent(); 72193323Sed BasicBlock *SI2BB = SI2->getParent(); 73193323Sed SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 74193323Sed 75193323Sed for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 76193323Sed if (SI1Succs.count(*I)) 77193323Sed for (BasicBlock::iterator BBI = (*I)->begin(); 78193323Sed isa<PHINode>(BBI); ++BBI) { 79193323Sed PHINode *PN = cast<PHINode>(BBI); 80193323Sed if (PN->getIncomingValueForBlock(SI1BB) != 81193323Sed PN->getIncomingValueForBlock(SI2BB)) 82193323Sed return false; 83193323Sed } 84193323Sed 85193323Sed return true; 86193323Sed} 87193323Sed 88193323Sed/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 89193323Sed/// now be entries in it from the 'NewPred' block. The values that will be 90193323Sed/// flowing into the PHI nodes will be the same as those coming in from 91193323Sed/// ExistPred, an existing predecessor of Succ. 92193323Sedstatic void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 93193323Sed BasicBlock *ExistPred) { 94193323Sed assert(std::find(succ_begin(ExistPred), succ_end(ExistPred), Succ) != 95193323Sed succ_end(ExistPred) && "ExistPred is not a predecessor of Succ!"); 96193323Sed if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 97193323Sed 98193323Sed PHINode *PN; 99193323Sed for (BasicBlock::iterator I = Succ->begin(); 100193323Sed (PN = dyn_cast<PHINode>(I)); ++I) 101193323Sed PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); 102193323Sed} 103193323Sed 104193323Sed 105193323Sed/// GetIfCondition - Given a basic block (BB) with two predecessors (and 106193323Sed/// presumably PHI nodes in it), check to see if the merge at this block is due 107193323Sed/// to an "if condition". If so, return the boolean condition that determines 108193323Sed/// which entry into BB will be taken. Also, return by references the block 109193323Sed/// that will be entered from if the condition is true, and the block that will 110193323Sed/// be entered if the condition is false. 111193323Sed/// 112193323Sed/// 113193323Sedstatic Value *GetIfCondition(BasicBlock *BB, 114193323Sed BasicBlock *&IfTrue, BasicBlock *&IfFalse) { 115193323Sed assert(std::distance(pred_begin(BB), pred_end(BB)) == 2 && 116193323Sed "Function can only handle blocks with 2 predecessors!"); 117193323Sed BasicBlock *Pred1 = *pred_begin(BB); 118193323Sed BasicBlock *Pred2 = *++pred_begin(BB); 119193323Sed 120193323Sed // We can only handle branches. Other control flow will be lowered to 121193323Sed // branches if possible anyway. 122193323Sed if (!isa<BranchInst>(Pred1->getTerminator()) || 123193323Sed !isa<BranchInst>(Pred2->getTerminator())) 124193323Sed return 0; 125193323Sed BranchInst *Pred1Br = cast<BranchInst>(Pred1->getTerminator()); 126193323Sed BranchInst *Pred2Br = cast<BranchInst>(Pred2->getTerminator()); 127193323Sed 128193323Sed // Eliminate code duplication by ensuring that Pred1Br is conditional if 129193323Sed // either are. 130193323Sed if (Pred2Br->isConditional()) { 131193323Sed // If both branches are conditional, we don't have an "if statement". In 132193323Sed // reality, we could transform this case, but since the condition will be 133193323Sed // required anyway, we stand no chance of eliminating it, so the xform is 134193323Sed // probably not profitable. 135193323Sed if (Pred1Br->isConditional()) 136193323Sed return 0; 137193323Sed 138193323Sed std::swap(Pred1, Pred2); 139193323Sed std::swap(Pred1Br, Pred2Br); 140193323Sed } 141193323Sed 142193323Sed if (Pred1Br->isConditional()) { 143193323Sed // If we found a conditional branch predecessor, make sure that it branches 144193323Sed // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 145193323Sed if (Pred1Br->getSuccessor(0) == BB && 146193323Sed Pred1Br->getSuccessor(1) == Pred2) { 147193323Sed IfTrue = Pred1; 148193323Sed IfFalse = Pred2; 149193323Sed } else if (Pred1Br->getSuccessor(0) == Pred2 && 150193323Sed Pred1Br->getSuccessor(1) == BB) { 151193323Sed IfTrue = Pred2; 152193323Sed IfFalse = Pred1; 153193323Sed } else { 154193323Sed // We know that one arm of the conditional goes to BB, so the other must 155193323Sed // go somewhere unrelated, and this must not be an "if statement". 156193323Sed return 0; 157193323Sed } 158193323Sed 159193323Sed // The only thing we have to watch out for here is to make sure that Pred2 160193323Sed // doesn't have incoming edges from other blocks. If it does, the condition 161193323Sed // doesn't dominate BB. 162193323Sed if (++pred_begin(Pred2) != pred_end(Pred2)) 163193323Sed return 0; 164193323Sed 165193323Sed return Pred1Br->getCondition(); 166193323Sed } 167193323Sed 168193323Sed // Ok, if we got here, both predecessors end with an unconditional branch to 169193323Sed // BB. Don't panic! If both blocks only have a single (identical) 170193323Sed // predecessor, and THAT is a conditional branch, then we're all ok! 171193323Sed if (pred_begin(Pred1) == pred_end(Pred1) || 172193323Sed ++pred_begin(Pred1) != pred_end(Pred1) || 173193323Sed pred_begin(Pred2) == pred_end(Pred2) || 174193323Sed ++pred_begin(Pred2) != pred_end(Pred2) || 175193323Sed *pred_begin(Pred1) != *pred_begin(Pred2)) 176193323Sed return 0; 177193323Sed 178193323Sed // Otherwise, if this is a conditional branch, then we can use it! 179193323Sed BasicBlock *CommonPred = *pred_begin(Pred1); 180193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator())) { 181193323Sed assert(BI->isConditional() && "Two successors but not conditional?"); 182193323Sed if (BI->getSuccessor(0) == Pred1) { 183193323Sed IfTrue = Pred1; 184193323Sed IfFalse = Pred2; 185193323Sed } else { 186193323Sed IfTrue = Pred2; 187193323Sed IfFalse = Pred1; 188193323Sed } 189193323Sed return BI->getCondition(); 190193323Sed } 191193323Sed return 0; 192193323Sed} 193193323Sed 194193323Sed/// DominatesMergePoint - If we have a merge point of an "if condition" as 195193323Sed/// accepted above, return true if the specified value dominates the block. We 196193323Sed/// don't handle the true generality of domination here, just a special case 197193323Sed/// which works well enough for us. 198193323Sed/// 199193323Sed/// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 200193323Sed/// see if V (which must be an instruction) is cheap to compute and is 201193323Sed/// non-trapping. If both are true, the instruction is inserted into the set 202193323Sed/// and true is returned. 203193323Sedstatic bool DominatesMergePoint(Value *V, BasicBlock *BB, 204193323Sed std::set<Instruction*> *AggressiveInsts) { 205193323Sed Instruction *I = dyn_cast<Instruction>(V); 206193323Sed if (!I) { 207193323Sed // Non-instructions all dominate instructions, but not all constantexprs 208193323Sed // can be executed unconditionally. 209193323Sed if (ConstantExpr *C = dyn_cast<ConstantExpr>(V)) 210193323Sed if (C->canTrap()) 211193323Sed return false; 212193323Sed return true; 213193323Sed } 214193323Sed BasicBlock *PBB = I->getParent(); 215193323Sed 216193323Sed // We don't want to allow weird loops that might have the "if condition" in 217193323Sed // the bottom of this block. 218193323Sed if (PBB == BB) return false; 219193323Sed 220193323Sed // If this instruction is defined in a block that contains an unconditional 221193323Sed // branch to BB, then it must be in the 'conditional' part of the "if 222193323Sed // statement". 223193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator())) 224193323Sed if (BI->isUnconditional() && BI->getSuccessor(0) == BB) { 225193323Sed if (!AggressiveInsts) return false; 226193323Sed // Okay, it looks like the instruction IS in the "condition". Check to 227193323Sed // see if its a cheap instruction to unconditionally compute, and if it 228193323Sed // only uses stuff defined outside of the condition. If so, hoist it out. 229198090Srdivacky if (!I->isSafeToSpeculativelyExecute()) 230198090Srdivacky return false; 231198090Srdivacky 232193323Sed switch (I->getOpcode()) { 233193323Sed default: return false; // Cannot hoist this out safely. 234193323Sed case Instruction::Load: { 235198090Srdivacky // We have to check to make sure there are no instructions before the 236198090Srdivacky // load in its basic block, as we are going to hoist the loop out to 237198090Srdivacky // its predecessor. 238193323Sed BasicBlock::iterator IP = PBB->begin(); 239193323Sed while (isa<DbgInfoIntrinsic>(IP)) 240193323Sed IP++; 241193323Sed if (IP != BasicBlock::iterator(I)) 242193323Sed return false; 243193323Sed break; 244193323Sed } 245193323Sed case Instruction::Add: 246193323Sed case Instruction::Sub: 247193323Sed case Instruction::And: 248193323Sed case Instruction::Or: 249193323Sed case Instruction::Xor: 250193323Sed case Instruction::Shl: 251193323Sed case Instruction::LShr: 252193323Sed case Instruction::AShr: 253193323Sed case Instruction::ICmp: 254193323Sed break; // These are all cheap and non-trapping instructions. 255193323Sed } 256193323Sed 257193323Sed // Okay, we can only really hoist these out if their operands are not 258193323Sed // defined in the conditional region. 259193323Sed for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) 260193323Sed if (!DominatesMergePoint(*i, BB, 0)) 261193323Sed return false; 262193323Sed // Okay, it's safe to do this! Remember this instruction. 263193323Sed AggressiveInsts->insert(I); 264193323Sed } 265193323Sed 266193323Sed return true; 267193323Sed} 268193323Sed 269203954Srdivacky/// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr 270203954Srdivacky/// and PointerNullValue. Return NULL if value is not a constant int. 271203954SrdivackyConstantInt *SimplifyCFGOpt::GetConstantInt(Value *V) { 272203954Srdivacky // Normal constant int. 273203954Srdivacky ConstantInt *CI = dyn_cast<ConstantInt>(V); 274203954Srdivacky if (CI || !TD || !isa<Constant>(V) || !isa<PointerType>(V->getType())) 275203954Srdivacky return CI; 276203954Srdivacky 277203954Srdivacky // This is some kind of pointer constant. Turn it into a pointer-sized 278203954Srdivacky // ConstantInt if possible. 279203954Srdivacky const IntegerType *PtrTy = TD->getIntPtrType(V->getContext()); 280203954Srdivacky 281203954Srdivacky // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*). 282203954Srdivacky if (isa<ConstantPointerNull>(V)) 283203954Srdivacky return ConstantInt::get(PtrTy, 0); 284203954Srdivacky 285203954Srdivacky // IntToPtr const int. 286203954Srdivacky if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 287203954Srdivacky if (CE->getOpcode() == Instruction::IntToPtr) 288203954Srdivacky if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) { 289203954Srdivacky // The constant is very likely to have the right type already. 290203954Srdivacky if (CI->getType() == PtrTy) 291203954Srdivacky return CI; 292203954Srdivacky else 293203954Srdivacky return cast<ConstantInt> 294203954Srdivacky (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false)); 295203954Srdivacky } 296203954Srdivacky return 0; 297203954Srdivacky} 298203954Srdivacky 299193323Sed/// GatherConstantSetEQs - Given a potentially 'or'd together collection of 300193323Sed/// icmp_eq instructions that compare a value against a constant, return the 301193323Sed/// value being compared, and stick the constant into the Values vector. 302203954SrdivackyValue *SimplifyCFGOpt:: 303203954SrdivackyGatherConstantSetEQs(Value *V, std::vector<ConstantInt*> &Values) { 304193323Sed if (Instruction *Inst = dyn_cast<Instruction>(V)) { 305193323Sed if (Inst->getOpcode() == Instruction::ICmp && 306193323Sed cast<ICmpInst>(Inst)->getPredicate() == ICmpInst::ICMP_EQ) { 307203954Srdivacky if (ConstantInt *C = GetConstantInt(Inst->getOperand(1))) { 308193323Sed Values.push_back(C); 309193323Sed return Inst->getOperand(0); 310203954Srdivacky } else if (ConstantInt *C = GetConstantInt(Inst->getOperand(0))) { 311193323Sed Values.push_back(C); 312193323Sed return Inst->getOperand(1); 313193323Sed } 314193323Sed } else if (Inst->getOpcode() == Instruction::Or) { 315193323Sed if (Value *LHS = GatherConstantSetEQs(Inst->getOperand(0), Values)) 316193323Sed if (Value *RHS = GatherConstantSetEQs(Inst->getOperand(1), Values)) 317193323Sed if (LHS == RHS) 318193323Sed return LHS; 319193323Sed } 320193323Sed } 321193323Sed return 0; 322193323Sed} 323193323Sed 324193323Sed/// GatherConstantSetNEs - Given a potentially 'and'd together collection of 325193323Sed/// setne instructions that compare a value against a constant, return the value 326193323Sed/// being compared, and stick the constant into the Values vector. 327203954SrdivackyValue *SimplifyCFGOpt:: 328203954SrdivackyGatherConstantSetNEs(Value *V, std::vector<ConstantInt*> &Values) { 329193323Sed if (Instruction *Inst = dyn_cast<Instruction>(V)) { 330193323Sed if (Inst->getOpcode() == Instruction::ICmp && 331193323Sed cast<ICmpInst>(Inst)->getPredicate() == ICmpInst::ICMP_NE) { 332203954Srdivacky if (ConstantInt *C = GetConstantInt(Inst->getOperand(1))) { 333193323Sed Values.push_back(C); 334193323Sed return Inst->getOperand(0); 335203954Srdivacky } else if (ConstantInt *C = GetConstantInt(Inst->getOperand(0))) { 336193323Sed Values.push_back(C); 337193323Sed return Inst->getOperand(1); 338193323Sed } 339193323Sed } else if (Inst->getOpcode() == Instruction::And) { 340193323Sed if (Value *LHS = GatherConstantSetNEs(Inst->getOperand(0), Values)) 341193323Sed if (Value *RHS = GatherConstantSetNEs(Inst->getOperand(1), Values)) 342193323Sed if (LHS == RHS) 343193323Sed return LHS; 344193323Sed } 345193323Sed } 346193323Sed return 0; 347193323Sed} 348193323Sed 349193323Sed/// GatherValueComparisons - If the specified Cond is an 'and' or 'or' of a 350193323Sed/// bunch of comparisons of one value against constants, return the value and 351193323Sed/// the constants being compared. 352203954Srdivackybool SimplifyCFGOpt::GatherValueComparisons(Instruction *Cond, Value *&CompVal, 353203954Srdivacky std::vector<ConstantInt*> &Values) { 354193323Sed if (Cond->getOpcode() == Instruction::Or) { 355193323Sed CompVal = GatherConstantSetEQs(Cond, Values); 356193323Sed 357193323Sed // Return true to indicate that the condition is true if the CompVal is 358193323Sed // equal to one of the constants. 359193323Sed return true; 360193323Sed } else if (Cond->getOpcode() == Instruction::And) { 361193323Sed CompVal = GatherConstantSetNEs(Cond, Values); 362193323Sed 363193323Sed // Return false to indicate that the condition is false if the CompVal is 364193323Sed // equal to one of the constants. 365193323Sed return false; 366193323Sed } 367193323Sed return false; 368193323Sed} 369193323Sed 370193323Sedstatic void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { 371193323Sed Instruction* Cond = 0; 372193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 373193323Sed Cond = dyn_cast<Instruction>(SI->getCondition()); 374193323Sed } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 375193323Sed if (BI->isConditional()) 376193323Sed Cond = dyn_cast<Instruction>(BI->getCondition()); 377193323Sed } 378193323Sed 379193323Sed TI->eraseFromParent(); 380193323Sed if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond); 381193323Sed} 382193323Sed 383193323Sed/// isValueEqualityComparison - Return true if the specified terminator checks 384193323Sed/// to see if a value is equal to constant integer value. 385203954SrdivackyValue *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { 386203954Srdivacky Value *CV = 0; 387193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 388193323Sed // Do not permit merging of large switch instructions into their 389193323Sed // predecessors unless there is only one predecessor. 390203954Srdivacky if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()), 391203954Srdivacky pred_end(SI->getParent())) <= 128) 392203954Srdivacky CV = SI->getCondition(); 393203954Srdivacky } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 394193323Sed if (BI->isConditional() && BI->getCondition()->hasOneUse()) 395193323Sed if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) 396193323Sed if ((ICI->getPredicate() == ICmpInst::ICMP_EQ || 397193323Sed ICI->getPredicate() == ICmpInst::ICMP_NE) && 398203954Srdivacky GetConstantInt(ICI->getOperand(1))) 399203954Srdivacky CV = ICI->getOperand(0); 400203954Srdivacky 401203954Srdivacky // Unwrap any lossless ptrtoint cast. 402203954Srdivacky if (TD && CV && CV->getType() == TD->getIntPtrType(CV->getContext())) 403203954Srdivacky if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) 404203954Srdivacky CV = PTII->getOperand(0); 405203954Srdivacky return CV; 406193323Sed} 407193323Sed 408193323Sed/// GetValueEqualityComparisonCases - Given a value comparison instruction, 409193323Sed/// decode all of the 'cases' that it represents and return the 'default' block. 410203954SrdivackyBasicBlock *SimplifyCFGOpt:: 411193323SedGetValueEqualityComparisonCases(TerminatorInst *TI, 412193323Sed std::vector<std::pair<ConstantInt*, 413193323Sed BasicBlock*> > &Cases) { 414193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 415193323Sed Cases.reserve(SI->getNumCases()); 416193323Sed for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 417193323Sed Cases.push_back(std::make_pair(SI->getCaseValue(i), SI->getSuccessor(i))); 418193323Sed return SI->getDefaultDest(); 419193323Sed } 420193323Sed 421193323Sed BranchInst *BI = cast<BranchInst>(TI); 422193323Sed ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 423203954Srdivacky Cases.push_back(std::make_pair(GetConstantInt(ICI->getOperand(1)), 424193323Sed BI->getSuccessor(ICI->getPredicate() == 425193323Sed ICmpInst::ICMP_NE))); 426193323Sed return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); 427193323Sed} 428193323Sed 429193323Sed 430193323Sed/// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries 431193323Sed/// in the list that match the specified block. 432193323Sedstatic void EliminateBlockCases(BasicBlock *BB, 433193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) { 434193323Sed for (unsigned i = 0, e = Cases.size(); i != e; ++i) 435193323Sed if (Cases[i].second == BB) { 436193323Sed Cases.erase(Cases.begin()+i); 437193323Sed --i; --e; 438193323Sed } 439193323Sed} 440193323Sed 441193323Sed/// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 442193323Sed/// well. 443193323Sedstatic bool 444193323SedValuesOverlap(std::vector<std::pair<ConstantInt*, BasicBlock*> > &C1, 445193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > &C2) { 446193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > *V1 = &C1, *V2 = &C2; 447193323Sed 448193323Sed // Make V1 be smaller than V2. 449193323Sed if (V1->size() > V2->size()) 450193323Sed std::swap(V1, V2); 451193323Sed 452193323Sed if (V1->size() == 0) return false; 453193323Sed if (V1->size() == 1) { 454193323Sed // Just scan V2. 455193323Sed ConstantInt *TheVal = (*V1)[0].first; 456193323Sed for (unsigned i = 0, e = V2->size(); i != e; ++i) 457193323Sed if (TheVal == (*V2)[i].first) 458193323Sed return true; 459193323Sed } 460193323Sed 461193323Sed // Otherwise, just sort both lists and compare element by element. 462193323Sed std::sort(V1->begin(), V1->end()); 463193323Sed std::sort(V2->begin(), V2->end()); 464193323Sed unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 465193323Sed while (i1 != e1 && i2 != e2) { 466193323Sed if ((*V1)[i1].first == (*V2)[i2].first) 467193323Sed return true; 468193323Sed if ((*V1)[i1].first < (*V2)[i2].first) 469193323Sed ++i1; 470193323Sed else 471193323Sed ++i2; 472193323Sed } 473193323Sed return false; 474193323Sed} 475193323Sed 476193323Sed/// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 477193323Sed/// terminator instruction and its block is known to only have a single 478193323Sed/// predecessor block, check to see if that predecessor is also a value 479193323Sed/// comparison with the same value, and if that comparison determines the 480193323Sed/// outcome of this comparison. If so, simplify TI. This does a very limited 481193323Sed/// form of jump threading. 482203954Srdivackybool SimplifyCFGOpt:: 483203954SrdivackySimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 484203954Srdivacky BasicBlock *Pred) { 485193323Sed Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 486193323Sed if (!PredVal) return false; // Not a value comparison in predecessor. 487193323Sed 488193323Sed Value *ThisVal = isValueEqualityComparison(TI); 489193323Sed assert(ThisVal && "This isn't a value comparison!!"); 490193323Sed if (ThisVal != PredVal) return false; // Different predicates. 491193323Sed 492193323Sed // Find out information about when control will move from Pred to TI's block. 493193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 494193323Sed BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 495193323Sed PredCases); 496193323Sed EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 497193323Sed 498193323Sed // Find information about how control leaves this block. 499193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases; 500193323Sed BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 501193323Sed EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 502193323Sed 503193323Sed // If TI's block is the default block from Pred's comparison, potentially 504193323Sed // simplify TI based on this knowledge. 505193323Sed if (PredDef == TI->getParent()) { 506193323Sed // If we are here, we know that the value is none of those cases listed in 507193323Sed // PredCases. If there are any cases in ThisCases that are in PredCases, we 508193323Sed // can simplify TI. 509193323Sed if (ValuesOverlap(PredCases, ThisCases)) { 510193323Sed if (isa<BranchInst>(TI)) { 511193323Sed // Okay, one of the successors of this condbr is dead. Convert it to a 512193323Sed // uncond br. 513193323Sed assert(ThisCases.size() == 1 && "Branch can only have one case!"); 514193323Sed // Insert the new branch. 515193323Sed Instruction *NI = BranchInst::Create(ThisDef, TI); 516198090Srdivacky (void) NI; 517193323Sed 518193323Sed // Remove PHI node entries for the dead edge. 519193323Sed ThisCases[0].second->removePredecessor(TI->getParent()); 520193323Sed 521202375Srdivacky DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 522198090Srdivacky << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 523193323Sed 524193323Sed EraseTerminatorInstAndDCECond(TI); 525193323Sed return true; 526193323Sed 527193323Sed } else { 528193323Sed SwitchInst *SI = cast<SwitchInst>(TI); 529193323Sed // Okay, TI has cases that are statically dead, prune them away. 530193323Sed SmallPtrSet<Constant*, 16> DeadCases; 531193323Sed for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 532193323Sed DeadCases.insert(PredCases[i].first); 533193323Sed 534202375Srdivacky DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 535198090Srdivacky << "Through successor TI: " << *TI); 536193323Sed 537193323Sed for (unsigned i = SI->getNumCases()-1; i != 0; --i) 538193323Sed if (DeadCases.count(SI->getCaseValue(i))) { 539193323Sed SI->getSuccessor(i)->removePredecessor(TI->getParent()); 540193323Sed SI->removeCase(i); 541193323Sed } 542193323Sed 543202375Srdivacky DEBUG(dbgs() << "Leaving: " << *TI << "\n"); 544193323Sed return true; 545193323Sed } 546193323Sed } 547193323Sed 548193323Sed } else { 549193323Sed // Otherwise, TI's block must correspond to some matched value. Find out 550193323Sed // which value (or set of values) this is. 551193323Sed ConstantInt *TIV = 0; 552193323Sed BasicBlock *TIBB = TI->getParent(); 553193323Sed for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 554193323Sed if (PredCases[i].second == TIBB) { 555193323Sed if (TIV == 0) 556193323Sed TIV = PredCases[i].first; 557193323Sed else 558193323Sed return false; // Cannot handle multiple values coming to this block. 559193323Sed } 560193323Sed assert(TIV && "No edge from pred to succ?"); 561193323Sed 562193323Sed // Okay, we found the one constant that our value can be if we get into TI's 563193323Sed // BB. Find out which successor will unconditionally be branched to. 564193323Sed BasicBlock *TheRealDest = 0; 565193323Sed for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 566193323Sed if (ThisCases[i].first == TIV) { 567193323Sed TheRealDest = ThisCases[i].second; 568193323Sed break; 569193323Sed } 570193323Sed 571193323Sed // If not handled by any explicit cases, it is handled by the default case. 572193323Sed if (TheRealDest == 0) TheRealDest = ThisDef; 573193323Sed 574193323Sed // Remove PHI node entries for dead edges. 575193323Sed BasicBlock *CheckEdge = TheRealDest; 576193323Sed for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 577193323Sed if (*SI != CheckEdge) 578193323Sed (*SI)->removePredecessor(TIBB); 579193323Sed else 580193323Sed CheckEdge = 0; 581193323Sed 582193323Sed // Insert the new branch. 583193323Sed Instruction *NI = BranchInst::Create(TheRealDest, TI); 584198090Srdivacky (void) NI; 585193323Sed 586202375Srdivacky DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 587198090Srdivacky << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 588193323Sed 589193323Sed EraseTerminatorInstAndDCECond(TI); 590193323Sed return true; 591193323Sed } 592193323Sed return false; 593193323Sed} 594193323Sed 595193323Sednamespace { 596193323Sed /// ConstantIntOrdering - This class implements a stable ordering of constant 597193323Sed /// integers that does not depend on their address. This is important for 598193323Sed /// applications that sort ConstantInt's to ensure uniqueness. 599193323Sed struct ConstantIntOrdering { 600193323Sed bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 601193323Sed return LHS->getValue().ult(RHS->getValue()); 602193323Sed } 603193323Sed }; 604193323Sed} 605193323Sed 606193323Sed/// FoldValueComparisonIntoPredecessors - The specified terminator is a value 607193323Sed/// equality comparison instruction (either a switch or a branch on "X == c"). 608193323Sed/// See if any of the predecessors of the terminator block are value comparisons 609193323Sed/// on the same value. If so, and if safe to do so, fold them together. 610203954Srdivackybool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 611193323Sed BasicBlock *BB = TI->getParent(); 612193323Sed Value *CV = isValueEqualityComparison(TI); // CondVal 613193323Sed assert(CV && "Not a comparison?"); 614193323Sed bool Changed = false; 615193323Sed 616193323Sed SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 617193323Sed while (!Preds.empty()) { 618193323Sed BasicBlock *Pred = Preds.pop_back_val(); 619193323Sed 620193323Sed // See if the predecessor is a comparison with the same value. 621193323Sed TerminatorInst *PTI = Pred->getTerminator(); 622193323Sed Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 623193323Sed 624193323Sed if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 625193323Sed // Figure out which 'cases' to copy from SI to PSI. 626193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 627193323Sed BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 628193323Sed 629193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 630193323Sed BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 631193323Sed 632193323Sed // Based on whether the default edge from PTI goes to BB or not, fill in 633193323Sed // PredCases and PredDefault with the new switch cases we would like to 634193323Sed // build. 635193323Sed SmallVector<BasicBlock*, 8> NewSuccessors; 636193323Sed 637193323Sed if (PredDefault == BB) { 638193323Sed // If this is the default destination from PTI, only the edges in TI 639193323Sed // that don't occur in PTI, or that branch to BB will be activated. 640193323Sed std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 641193323Sed for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 642193323Sed if (PredCases[i].second != BB) 643193323Sed PTIHandled.insert(PredCases[i].first); 644193323Sed else { 645193323Sed // The default destination is BB, we don't need explicit targets. 646193323Sed std::swap(PredCases[i], PredCases.back()); 647193323Sed PredCases.pop_back(); 648193323Sed --i; --e; 649193323Sed } 650193323Sed 651193323Sed // Reconstruct the new switch statement we will be building. 652193323Sed if (PredDefault != BBDefault) { 653193323Sed PredDefault->removePredecessor(Pred); 654193323Sed PredDefault = BBDefault; 655193323Sed NewSuccessors.push_back(BBDefault); 656193323Sed } 657193323Sed for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 658193323Sed if (!PTIHandled.count(BBCases[i].first) && 659193323Sed BBCases[i].second != BBDefault) { 660193323Sed PredCases.push_back(BBCases[i]); 661193323Sed NewSuccessors.push_back(BBCases[i].second); 662193323Sed } 663193323Sed 664193323Sed } else { 665193323Sed // If this is not the default destination from PSI, only the edges 666193323Sed // in SI that occur in PSI with a destination of BB will be 667193323Sed // activated. 668193323Sed std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 669193323Sed for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 670193323Sed if (PredCases[i].second == BB) { 671193323Sed PTIHandled.insert(PredCases[i].first); 672193323Sed std::swap(PredCases[i], PredCases.back()); 673193323Sed PredCases.pop_back(); 674193323Sed --i; --e; 675193323Sed } 676193323Sed 677193323Sed // Okay, now we know which constants were sent to BB from the 678193323Sed // predecessor. Figure out where they will all go now. 679193323Sed for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 680193323Sed if (PTIHandled.count(BBCases[i].first)) { 681193323Sed // If this is one we are capable of getting... 682193323Sed PredCases.push_back(BBCases[i]); 683193323Sed NewSuccessors.push_back(BBCases[i].second); 684193323Sed PTIHandled.erase(BBCases[i].first);// This constant is taken care of 685193323Sed } 686193323Sed 687193323Sed // If there are any constants vectored to BB that TI doesn't handle, 688193323Sed // they must go to the default destination of TI. 689193323Sed for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I = 690193323Sed PTIHandled.begin(), 691193323Sed E = PTIHandled.end(); I != E; ++I) { 692193323Sed PredCases.push_back(std::make_pair(*I, BBDefault)); 693193323Sed NewSuccessors.push_back(BBDefault); 694193323Sed } 695193323Sed } 696193323Sed 697193323Sed // Okay, at this point, we know which new successor Pred will get. Make 698193323Sed // sure we update the number of entries in the PHI nodes for these 699193323Sed // successors. 700193323Sed for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 701193323Sed AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 702193323Sed 703203954Srdivacky // Convert pointer to int before we switch. 704203954Srdivacky if (isa<PointerType>(CV->getType())) { 705203954Srdivacky assert(TD && "Cannot switch on pointer without TargetData"); 706203954Srdivacky CV = new PtrToIntInst(CV, TD->getIntPtrType(CV->getContext()), 707203954Srdivacky "magicptr", PTI); 708203954Srdivacky } 709203954Srdivacky 710193323Sed // Now that the successors are updated, create the new Switch instruction. 711193323Sed SwitchInst *NewSI = SwitchInst::Create(CV, PredDefault, 712193323Sed PredCases.size(), PTI); 713193323Sed for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 714193323Sed NewSI->addCase(PredCases[i].first, PredCases[i].second); 715193323Sed 716193323Sed EraseTerminatorInstAndDCECond(PTI); 717193323Sed 718193323Sed // Okay, last check. If BB is still a successor of PSI, then we must 719193323Sed // have an infinite loop case. If so, add an infinitely looping block 720193323Sed // to handle the case to preserve the behavior of the code. 721193323Sed BasicBlock *InfLoopBlock = 0; 722193323Sed for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 723193323Sed if (NewSI->getSuccessor(i) == BB) { 724193323Sed if (InfLoopBlock == 0) { 725193323Sed // Insert it at the end of the function, because it's either code, 726193323Sed // or it won't matter if it's hot. :) 727198090Srdivacky InfLoopBlock = BasicBlock::Create(BB->getContext(), 728198090Srdivacky "infloop", BB->getParent()); 729193323Sed BranchInst::Create(InfLoopBlock, InfLoopBlock); 730193323Sed } 731193323Sed NewSI->setSuccessor(i, InfLoopBlock); 732193323Sed } 733193323Sed 734193323Sed Changed = true; 735193323Sed } 736193323Sed } 737193323Sed return Changed; 738193323Sed} 739193323Sed 740194612Sed// isSafeToHoistInvoke - If we would need to insert a select that uses the 741194612Sed// value of this invoke (comments in HoistThenElseCodeToIf explain why we 742194612Sed// would need to do this), we can't hoist the invoke, as there is nowhere 743194612Sed// to put the select in this case. 744194612Sedstatic bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, 745194612Sed Instruction *I1, Instruction *I2) { 746194612Sed for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 747194612Sed PHINode *PN; 748194612Sed for (BasicBlock::iterator BBI = SI->begin(); 749194612Sed (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 750194612Sed Value *BB1V = PN->getIncomingValueForBlock(BB1); 751194612Sed Value *BB2V = PN->getIncomingValueForBlock(BB2); 752194612Sed if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) { 753194612Sed return false; 754194612Sed } 755194612Sed } 756194612Sed } 757194612Sed return true; 758194612Sed} 759194612Sed 760193323Sed/// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and 761193323Sed/// BB2, hoist any common code in the two blocks up into the branch block. The 762193323Sed/// caller of this function guarantees that BI's block dominates BB1 and BB2. 763193323Sedstatic bool HoistThenElseCodeToIf(BranchInst *BI) { 764193323Sed // This does very trivial matching, with limited scanning, to find identical 765193323Sed // instructions in the two blocks. In particular, we don't want to get into 766193323Sed // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 767193323Sed // such, we currently just scan for obviously identical instructions in an 768193323Sed // identical order. 769193323Sed BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 770193323Sed BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 771193323Sed 772193323Sed BasicBlock::iterator BB1_Itr = BB1->begin(); 773193323Sed BasicBlock::iterator BB2_Itr = BB2->begin(); 774193323Sed 775193323Sed Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++; 776193323Sed while (isa<DbgInfoIntrinsic>(I1)) 777193323Sed I1 = BB1_Itr++; 778193323Sed while (isa<DbgInfoIntrinsic>(I2)) 779193323Sed I2 = BB2_Itr++; 780194612Sed if (I1->getOpcode() != I2->getOpcode() || isa<PHINode>(I1) || 781198090Srdivacky !I1->isIdenticalToWhenDefined(I2) || 782194612Sed (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))) 783193323Sed return false; 784193323Sed 785193323Sed // If we get here, we can hoist at least one instruction. 786193323Sed BasicBlock *BIParent = BI->getParent(); 787193323Sed 788193323Sed do { 789193323Sed // If we are hoisting the terminator instruction, don't move one (making a 790193323Sed // broken BB), instead clone it, and remove BI. 791193323Sed if (isa<TerminatorInst>(I1)) 792193323Sed goto HoistTerminator; 793193323Sed 794193323Sed // For a normal instruction, we just move one to right before the branch, 795193323Sed // then replace all uses of the other with the first. Finally, we remove 796193323Sed // the now redundant second instruction. 797193323Sed BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 798193323Sed if (!I2->use_empty()) 799193323Sed I2->replaceAllUsesWith(I1); 800198090Srdivacky I1->intersectOptionalDataWith(I2); 801193323Sed BB2->getInstList().erase(I2); 802193323Sed 803193323Sed I1 = BB1_Itr++; 804193323Sed while (isa<DbgInfoIntrinsic>(I1)) 805193323Sed I1 = BB1_Itr++; 806193323Sed I2 = BB2_Itr++; 807193323Sed while (isa<DbgInfoIntrinsic>(I2)) 808193323Sed I2 = BB2_Itr++; 809198090Srdivacky } while (I1->getOpcode() == I2->getOpcode() && 810198090Srdivacky I1->isIdenticalToWhenDefined(I2)); 811193323Sed 812193323Sed return true; 813193323Sed 814193323SedHoistTerminator: 815194612Sed // It may not be possible to hoist an invoke. 816194612Sed if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) 817194612Sed return true; 818194612Sed 819193323Sed // Okay, it is safe to hoist the terminator. 820193323Sed Instruction *NT = I1->clone(); 821193323Sed BIParent->getInstList().insert(BI, NT); 822202375Srdivacky if (!NT->getType()->isVoidTy()) { 823193323Sed I1->replaceAllUsesWith(NT); 824193323Sed I2->replaceAllUsesWith(NT); 825193323Sed NT->takeName(I1); 826193323Sed } 827193323Sed 828193323Sed // Hoisting one of the terminators from our successor is a great thing. 829193323Sed // Unfortunately, the successors of the if/else blocks may have PHI nodes in 830193323Sed // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 831193323Sed // nodes, so we insert select instruction to compute the final result. 832193323Sed std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 833193323Sed for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 834193323Sed PHINode *PN; 835193323Sed for (BasicBlock::iterator BBI = SI->begin(); 836193323Sed (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 837193323Sed Value *BB1V = PN->getIncomingValueForBlock(BB1); 838193323Sed Value *BB2V = PN->getIncomingValueForBlock(BB2); 839193323Sed if (BB1V != BB2V) { 840193323Sed // These values do not agree. Insert a select instruction before NT 841193323Sed // that determines the right value. 842193323Sed SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 843193323Sed if (SI == 0) 844193323Sed SI = SelectInst::Create(BI->getCondition(), BB1V, BB2V, 845193323Sed BB1V->getName()+"."+BB2V->getName(), NT); 846193323Sed // Make the PHI node use the select for all incoming values for BB1/BB2 847193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 848193323Sed if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 849193323Sed PN->setIncomingValue(i, SI); 850193323Sed } 851193323Sed } 852193323Sed } 853193323Sed 854193323Sed // Update any PHI nodes in our new successors. 855193323Sed for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 856193323Sed AddPredecessorToBlock(*SI, BIParent, BB1); 857193323Sed 858193323Sed EraseTerminatorInstAndDCECond(BI); 859193323Sed return true; 860193323Sed} 861193323Sed 862193323Sed/// SpeculativelyExecuteBB - Given a conditional branch that goes to BB1 863193323Sed/// and an BB2 and the only successor of BB1 is BB2, hoist simple code 864193323Sed/// (for now, restricted to a single instruction that's side effect free) from 865193323Sed/// the BB1 into the branch block to speculatively execute it. 866193323Sedstatic bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { 867193323Sed // Only speculatively execution a single instruction (not counting the 868193323Sed // terminator) for now. 869193323Sed Instruction *HInst = NULL; 870193323Sed Instruction *Term = BB1->getTerminator(); 871193323Sed for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end(); 872193323Sed BBI != BBE; ++BBI) { 873193323Sed Instruction *I = BBI; 874193323Sed // Skip debug info. 875193323Sed if (isa<DbgInfoIntrinsic>(I)) continue; 876193323Sed if (I == Term) break; 877193323Sed 878193323Sed if (!HInst) 879193323Sed HInst = I; 880193323Sed else 881193323Sed return false; 882193323Sed } 883193323Sed if (!HInst) 884193323Sed return false; 885193323Sed 886193323Sed // Be conservative for now. FP select instruction can often be expensive. 887193323Sed Value *BrCond = BI->getCondition(); 888193323Sed if (isa<Instruction>(BrCond) && 889193323Sed cast<Instruction>(BrCond)->getOpcode() == Instruction::FCmp) 890193323Sed return false; 891193323Sed 892193323Sed // If BB1 is actually on the false edge of the conditional branch, remember 893193323Sed // to swap the select operands later. 894193323Sed bool Invert = false; 895193323Sed if (BB1 != BI->getSuccessor(0)) { 896193323Sed assert(BB1 == BI->getSuccessor(1) && "No edge from 'if' block?"); 897193323Sed Invert = true; 898193323Sed } 899193323Sed 900193323Sed // Turn 901193323Sed // BB: 902193323Sed // %t1 = icmp 903193323Sed // br i1 %t1, label %BB1, label %BB2 904193323Sed // BB1: 905193323Sed // %t3 = add %t2, c 906193323Sed // br label BB2 907193323Sed // BB2: 908193323Sed // => 909193323Sed // BB: 910193323Sed // %t1 = icmp 911193323Sed // %t4 = add %t2, c 912193323Sed // %t3 = select i1 %t1, %t2, %t3 913193323Sed switch (HInst->getOpcode()) { 914193323Sed default: return false; // Not safe / profitable to hoist. 915193323Sed case Instruction::Add: 916193323Sed case Instruction::Sub: 917193574Sed // Not worth doing for vector ops. 918193574Sed if (isa<VectorType>(HInst->getType())) 919193323Sed return false; 920193323Sed break; 921193323Sed case Instruction::And: 922193323Sed case Instruction::Or: 923193323Sed case Instruction::Xor: 924193323Sed case Instruction::Shl: 925193323Sed case Instruction::LShr: 926193323Sed case Instruction::AShr: 927193323Sed // Don't mess with vector operations. 928193323Sed if (isa<VectorType>(HInst->getType())) 929193323Sed return false; 930193323Sed break; // These are all cheap and non-trapping instructions. 931193323Sed } 932193323Sed 933193323Sed // If the instruction is obviously dead, don't try to predicate it. 934193323Sed if (HInst->use_empty()) { 935193323Sed HInst->eraseFromParent(); 936193323Sed return true; 937193323Sed } 938193323Sed 939193323Sed // Can we speculatively execute the instruction? And what is the value 940193323Sed // if the condition is false? Consider the phi uses, if the incoming value 941193323Sed // from the "if" block are all the same V, then V is the value of the 942193323Sed // select if the condition is false. 943193323Sed BasicBlock *BIParent = BI->getParent(); 944193323Sed SmallVector<PHINode*, 4> PHIUses; 945193323Sed Value *FalseV = NULL; 946193323Sed 947193323Sed BasicBlock *BB2 = BB1->getTerminator()->getSuccessor(0); 948193323Sed for (Value::use_iterator UI = HInst->use_begin(), E = HInst->use_end(); 949193323Sed UI != E; ++UI) { 950193323Sed // Ignore any user that is not a PHI node in BB2. These can only occur in 951193323Sed // unreachable blocks, because they would not be dominated by the instr. 952193323Sed PHINode *PN = dyn_cast<PHINode>(UI); 953193323Sed if (!PN || PN->getParent() != BB2) 954193323Sed return false; 955193323Sed PHIUses.push_back(PN); 956193323Sed 957193323Sed Value *PHIV = PN->getIncomingValueForBlock(BIParent); 958193323Sed if (!FalseV) 959193323Sed FalseV = PHIV; 960193323Sed else if (FalseV != PHIV) 961193323Sed return false; // Inconsistent value when condition is false. 962193323Sed } 963193323Sed 964193323Sed assert(FalseV && "Must have at least one user, and it must be a PHI"); 965193323Sed 966193323Sed // Do not hoist the instruction if any of its operands are defined but not 967193323Sed // used in this BB. The transformation will prevent the operand from 968193323Sed // being sunk into the use block. 969193323Sed for (User::op_iterator i = HInst->op_begin(), e = HInst->op_end(); 970193323Sed i != e; ++i) { 971193323Sed Instruction *OpI = dyn_cast<Instruction>(*i); 972193323Sed if (OpI && OpI->getParent() == BIParent && 973193323Sed !OpI->isUsedInBasicBlock(BIParent)) 974193323Sed return false; 975193323Sed } 976193323Sed 977193323Sed // If we get here, we can hoist the instruction. Try to place it 978193323Sed // before the icmp instruction preceding the conditional branch. 979193323Sed BasicBlock::iterator InsertPos = BI; 980193323Sed if (InsertPos != BIParent->begin()) 981193323Sed --InsertPos; 982193323Sed // Skip debug info between condition and branch. 983193323Sed while (InsertPos != BIParent->begin() && isa<DbgInfoIntrinsic>(InsertPos)) 984193323Sed --InsertPos; 985193323Sed if (InsertPos == BrCond && !isa<PHINode>(BrCond)) { 986193323Sed SmallPtrSet<Instruction *, 4> BB1Insns; 987193323Sed for(BasicBlock::iterator BB1I = BB1->begin(), BB1E = BB1->end(); 988193323Sed BB1I != BB1E; ++BB1I) 989193323Sed BB1Insns.insert(BB1I); 990193323Sed for(Value::use_iterator UI = BrCond->use_begin(), UE = BrCond->use_end(); 991193323Sed UI != UE; ++UI) { 992193323Sed Instruction *Use = cast<Instruction>(*UI); 993193323Sed if (BB1Insns.count(Use)) { 994193323Sed // If BrCond uses the instruction that place it just before 995193323Sed // branch instruction. 996193323Sed InsertPos = BI; 997193323Sed break; 998193323Sed } 999193323Sed } 1000193323Sed } else 1001193323Sed InsertPos = BI; 1002193323Sed BIParent->getInstList().splice(InsertPos, BB1->getInstList(), HInst); 1003193323Sed 1004193323Sed // Create a select whose true value is the speculatively executed value and 1005193323Sed // false value is the previously determined FalseV. 1006193323Sed SelectInst *SI; 1007193323Sed if (Invert) 1008193323Sed SI = SelectInst::Create(BrCond, FalseV, HInst, 1009193323Sed FalseV->getName() + "." + HInst->getName(), BI); 1010193323Sed else 1011193323Sed SI = SelectInst::Create(BrCond, HInst, FalseV, 1012193323Sed HInst->getName() + "." + FalseV->getName(), BI); 1013193323Sed 1014193323Sed // Make the PHI node use the select for all incoming values for "then" and 1015193323Sed // "if" blocks. 1016193323Sed for (unsigned i = 0, e = PHIUses.size(); i != e; ++i) { 1017193323Sed PHINode *PN = PHIUses[i]; 1018193323Sed for (unsigned j = 0, ee = PN->getNumIncomingValues(); j != ee; ++j) 1019193323Sed if (PN->getIncomingBlock(j) == BB1 || 1020193323Sed PN->getIncomingBlock(j) == BIParent) 1021193323Sed PN->setIncomingValue(j, SI); 1022193323Sed } 1023193323Sed 1024193323Sed ++NumSpeculations; 1025193323Sed return true; 1026193323Sed} 1027193323Sed 1028193323Sed/// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch 1029193323Sed/// across this block. 1030193323Sedstatic bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { 1031193323Sed BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 1032193323Sed unsigned Size = 0; 1033193323Sed 1034193323Sed for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1035193323Sed if (isa<DbgInfoIntrinsic>(BBI)) 1036193323Sed continue; 1037193323Sed if (Size > 10) return false; // Don't clone large BB's. 1038193323Sed ++Size; 1039193323Sed 1040193323Sed // We can only support instructions that do not define values that are 1041193323Sed // live outside of the current basic block. 1042193323Sed for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 1043193323Sed UI != E; ++UI) { 1044193323Sed Instruction *U = cast<Instruction>(*UI); 1045193323Sed if (U->getParent() != BB || isa<PHINode>(U)) return false; 1046193323Sed } 1047193323Sed 1048193323Sed // Looks ok, continue checking. 1049193323Sed } 1050193323Sed 1051193323Sed return true; 1052193323Sed} 1053193323Sed 1054193323Sed/// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value 1055193323Sed/// that is defined in the same block as the branch and if any PHI entries are 1056193323Sed/// constants, thread edges corresponding to that entry to be branches to their 1057193323Sed/// ultimate destination. 1058193323Sedstatic bool FoldCondBranchOnPHI(BranchInst *BI) { 1059193323Sed BasicBlock *BB = BI->getParent(); 1060193323Sed PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 1061193323Sed // NOTE: we currently cannot transform this case if the PHI node is used 1062193323Sed // outside of the block. 1063193323Sed if (!PN || PN->getParent() != BB || !PN->hasOneUse()) 1064193323Sed return false; 1065193323Sed 1066193323Sed // Degenerate case of a single entry PHI. 1067193323Sed if (PN->getNumIncomingValues() == 1) { 1068193323Sed FoldSingleEntryPHINodes(PN->getParent()); 1069193323Sed return true; 1070193323Sed } 1071193323Sed 1072193323Sed // Now we know that this block has multiple preds and two succs. 1073193323Sed if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; 1074193323Sed 1075193323Sed // Okay, this is a simple enough basic block. See if any phi values are 1076193323Sed // constants. 1077193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1078193323Sed ConstantInt *CB; 1079193323Sed if ((CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i))) && 1080203954Srdivacky CB->getType()->isIntegerTy(1)) { 1081193323Sed // Okay, we now know that all edges from PredBB should be revectored to 1082193323Sed // branch to RealDest. 1083193323Sed BasicBlock *PredBB = PN->getIncomingBlock(i); 1084193323Sed BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); 1085193323Sed 1086193323Sed if (RealDest == BB) continue; // Skip self loops. 1087193323Sed 1088193323Sed // The dest block might have PHI nodes, other predecessors and other 1089193323Sed // difficult cases. Instead of being smart about this, just insert a new 1090193323Sed // block that jumps to the destination block, effectively splitting 1091193323Sed // the edge we are about to create. 1092198090Srdivacky BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(), 1093198090Srdivacky RealDest->getName()+".critedge", 1094193323Sed RealDest->getParent(), RealDest); 1095193323Sed BranchInst::Create(RealDest, EdgeBB); 1096193323Sed PHINode *PN; 1097193323Sed for (BasicBlock::iterator BBI = RealDest->begin(); 1098193323Sed (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 1099193323Sed Value *V = PN->getIncomingValueForBlock(BB); 1100193323Sed PN->addIncoming(V, EdgeBB); 1101193323Sed } 1102193323Sed 1103193323Sed // BB may have instructions that are being threaded over. Clone these 1104193323Sed // instructions into EdgeBB. We know that there will be no uses of the 1105193323Sed // cloned instructions outside of EdgeBB. 1106193323Sed BasicBlock::iterator InsertPt = EdgeBB->begin(); 1107193323Sed std::map<Value*, Value*> TranslateMap; // Track translated values. 1108193323Sed for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1109193323Sed if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 1110193323Sed TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); 1111193323Sed } else { 1112193323Sed // Clone the instruction. 1113193323Sed Instruction *N = BBI->clone(); 1114193323Sed if (BBI->hasName()) N->setName(BBI->getName()+".c"); 1115193323Sed 1116193323Sed // Update operands due to translation. 1117193323Sed for (User::op_iterator i = N->op_begin(), e = N->op_end(); 1118193323Sed i != e; ++i) { 1119193323Sed std::map<Value*, Value*>::iterator PI = 1120193323Sed TranslateMap.find(*i); 1121193323Sed if (PI != TranslateMap.end()) 1122193323Sed *i = PI->second; 1123193323Sed } 1124193323Sed 1125193323Sed // Check for trivial simplification. 1126199481Srdivacky if (Constant *C = ConstantFoldInstruction(N)) { 1127193323Sed TranslateMap[BBI] = C; 1128193323Sed delete N; // Constant folded away, don't need actual inst 1129193323Sed } else { 1130193323Sed // Insert the new instruction into its new home. 1131193323Sed EdgeBB->getInstList().insert(InsertPt, N); 1132193323Sed if (!BBI->use_empty()) 1133193323Sed TranslateMap[BBI] = N; 1134193323Sed } 1135193323Sed } 1136193323Sed } 1137193323Sed 1138193323Sed // Loop over all of the edges from PredBB to BB, changing them to branch 1139193323Sed // to EdgeBB instead. 1140193323Sed TerminatorInst *PredBBTI = PredBB->getTerminator(); 1141193323Sed for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 1142193323Sed if (PredBBTI->getSuccessor(i) == BB) { 1143193323Sed BB->removePredecessor(PredBB); 1144193323Sed PredBBTI->setSuccessor(i, EdgeBB); 1145193323Sed } 1146193323Sed 1147193323Sed // Recurse, simplifying any other constants. 1148193323Sed return FoldCondBranchOnPHI(BI) | true; 1149193323Sed } 1150193323Sed } 1151193323Sed 1152193323Sed return false; 1153193323Sed} 1154193323Sed 1155193323Sed/// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry 1156193323Sed/// PHI node, see if we can eliminate it. 1157193323Sedstatic bool FoldTwoEntryPHINode(PHINode *PN) { 1158193323Sed // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1159193323Sed // statement", which has a very simple dominance structure. Basically, we 1160193323Sed // are trying to find the condition that is being branched on, which 1161193323Sed // subsequently causes this merge to happen. We really want control 1162193323Sed // dependence information for this check, but simplifycfg can't keep it up 1163193323Sed // to date, and this catches most of the cases we care about anyway. 1164193323Sed // 1165193323Sed BasicBlock *BB = PN->getParent(); 1166193323Sed BasicBlock *IfTrue, *IfFalse; 1167193323Sed Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); 1168193323Sed if (!IfCond) return false; 1169193323Sed 1170193323Sed // Okay, we found that we can merge this two-entry phi node into a select. 1171193323Sed // Doing so would require us to fold *all* two entry phi nodes in this block. 1172193323Sed // At some point this becomes non-profitable (particularly if the target 1173193323Sed // doesn't support cmov's). Only do this transformation if there are two or 1174193323Sed // fewer PHI nodes in this block. 1175193323Sed unsigned NumPhis = 0; 1176193323Sed for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I) 1177193323Sed if (NumPhis > 2) 1178193323Sed return false; 1179193323Sed 1180202375Srdivacky DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond << " T: " 1181198090Srdivacky << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1182193323Sed 1183193323Sed // Loop over the PHI's seeing if we can promote them all to select 1184193323Sed // instructions. While we are at it, keep track of the instructions 1185193323Sed // that need to be moved to the dominating block. 1186193323Sed std::set<Instruction*> AggressiveInsts; 1187193323Sed 1188193323Sed BasicBlock::iterator AfterPHIIt = BB->begin(); 1189193323Sed while (isa<PHINode>(AfterPHIIt)) { 1190193323Sed PHINode *PN = cast<PHINode>(AfterPHIIt++); 1191193323Sed if (PN->getIncomingValue(0) == PN->getIncomingValue(1)) { 1192193323Sed if (PN->getIncomingValue(0) != PN) 1193193323Sed PN->replaceAllUsesWith(PN->getIncomingValue(0)); 1194193323Sed else 1195193323Sed PN->replaceAllUsesWith(UndefValue::get(PN->getType())); 1196193323Sed } else if (!DominatesMergePoint(PN->getIncomingValue(0), BB, 1197193323Sed &AggressiveInsts) || 1198193323Sed !DominatesMergePoint(PN->getIncomingValue(1), BB, 1199193323Sed &AggressiveInsts)) { 1200193323Sed return false; 1201193323Sed } 1202193323Sed } 1203193323Sed 1204193323Sed // If we all PHI nodes are promotable, check to make sure that all 1205193323Sed // instructions in the predecessor blocks can be promoted as well. If 1206193323Sed // not, we won't be able to get rid of the control flow, so it's not 1207193323Sed // worth promoting to select instructions. 1208193323Sed BasicBlock *DomBlock = 0, *IfBlock1 = 0, *IfBlock2 = 0; 1209193323Sed PN = cast<PHINode>(BB->begin()); 1210193323Sed BasicBlock *Pred = PN->getIncomingBlock(0); 1211193323Sed if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1212193323Sed IfBlock1 = Pred; 1213193323Sed DomBlock = *pred_begin(Pred); 1214193323Sed for (BasicBlock::iterator I = Pred->begin(); 1215193323Sed !isa<TerminatorInst>(I); ++I) 1216193323Sed if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1217193323Sed // This is not an aggressive instruction that we can promote. 1218193323Sed // Because of this, we won't be able to get rid of the control 1219193323Sed // flow, so the xform is not worth it. 1220193323Sed return false; 1221193323Sed } 1222193323Sed } 1223193323Sed 1224193323Sed Pred = PN->getIncomingBlock(1); 1225193323Sed if (cast<BranchInst>(Pred->getTerminator())->isUnconditional()) { 1226193323Sed IfBlock2 = Pred; 1227193323Sed DomBlock = *pred_begin(Pred); 1228193323Sed for (BasicBlock::iterator I = Pred->begin(); 1229193323Sed !isa<TerminatorInst>(I); ++I) 1230193323Sed if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1231193323Sed // This is not an aggressive instruction that we can promote. 1232193323Sed // Because of this, we won't be able to get rid of the control 1233193323Sed // flow, so the xform is not worth it. 1234193323Sed return false; 1235193323Sed } 1236193323Sed } 1237193323Sed 1238193323Sed // If we can still promote the PHI nodes after this gauntlet of tests, 1239193323Sed // do all of the PHI's now. 1240193323Sed 1241193323Sed // Move all 'aggressive' instructions, which are defined in the 1242193323Sed // conditional parts of the if's up to the dominating block. 1243193323Sed if (IfBlock1) { 1244193323Sed DomBlock->getInstList().splice(DomBlock->getTerminator(), 1245193323Sed IfBlock1->getInstList(), 1246193323Sed IfBlock1->begin(), 1247193323Sed IfBlock1->getTerminator()); 1248193323Sed } 1249193323Sed if (IfBlock2) { 1250193323Sed DomBlock->getInstList().splice(DomBlock->getTerminator(), 1251193323Sed IfBlock2->getInstList(), 1252193323Sed IfBlock2->begin(), 1253193323Sed IfBlock2->getTerminator()); 1254193323Sed } 1255193323Sed 1256193323Sed while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 1257193323Sed // Change the PHI node into a select instruction. 1258193323Sed Value *TrueVal = 1259193323Sed PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1260193323Sed Value *FalseVal = 1261193323Sed PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1262193323Sed 1263193323Sed Value *NV = SelectInst::Create(IfCond, TrueVal, FalseVal, "", AfterPHIIt); 1264193323Sed PN->replaceAllUsesWith(NV); 1265193323Sed NV->takeName(PN); 1266193323Sed 1267193323Sed BB->getInstList().erase(PN); 1268193323Sed } 1269193323Sed return true; 1270193323Sed} 1271193323Sed 1272193323Sed/// isTerminatorFirstRelevantInsn - Return true if Term is very first 1273193323Sed/// instruction ignoring Phi nodes and dbg intrinsics. 1274193323Sedstatic bool isTerminatorFirstRelevantInsn(BasicBlock *BB, Instruction *Term) { 1275193323Sed BasicBlock::iterator BBI = Term; 1276193323Sed while (BBI != BB->begin()) { 1277193323Sed --BBI; 1278193323Sed if (!isa<DbgInfoIntrinsic>(BBI)) 1279193323Sed break; 1280193323Sed } 1281193323Sed 1282193323Sed if (isa<PHINode>(BBI) || &*BBI == Term || isa<DbgInfoIntrinsic>(BBI)) 1283193323Sed return true; 1284193323Sed return false; 1285193323Sed} 1286193323Sed 1287193323Sed/// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes 1288193323Sed/// to two returning blocks, try to merge them together into one return, 1289193323Sed/// introducing a select if the return values disagree. 1290193323Sedstatic bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { 1291193323Sed assert(BI->isConditional() && "Must be a conditional branch"); 1292193323Sed BasicBlock *TrueSucc = BI->getSuccessor(0); 1293193323Sed BasicBlock *FalseSucc = BI->getSuccessor(1); 1294193323Sed ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator()); 1295193323Sed ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator()); 1296193323Sed 1297193323Sed // Check to ensure both blocks are empty (just a return) or optionally empty 1298193323Sed // with PHI nodes. If there are other instructions, merging would cause extra 1299193323Sed // computation on one path or the other. 1300193323Sed if (!isTerminatorFirstRelevantInsn(TrueSucc, TrueRet)) 1301193323Sed return false; 1302193323Sed if (!isTerminatorFirstRelevantInsn(FalseSucc, FalseRet)) 1303193323Sed return false; 1304193323Sed 1305193323Sed // Okay, we found a branch that is going to two return nodes. If 1306193323Sed // there is no return value for this function, just change the 1307193323Sed // branch into a return. 1308193323Sed if (FalseRet->getNumOperands() == 0) { 1309193323Sed TrueSucc->removePredecessor(BI->getParent()); 1310193323Sed FalseSucc->removePredecessor(BI->getParent()); 1311198090Srdivacky ReturnInst::Create(BI->getContext(), 0, BI); 1312193323Sed EraseTerminatorInstAndDCECond(BI); 1313193323Sed return true; 1314193323Sed } 1315193323Sed 1316193323Sed // Otherwise, figure out what the true and false return values are 1317193323Sed // so we can insert a new select instruction. 1318193323Sed Value *TrueValue = TrueRet->getReturnValue(); 1319193323Sed Value *FalseValue = FalseRet->getReturnValue(); 1320193323Sed 1321193323Sed // Unwrap any PHI nodes in the return blocks. 1322193323Sed if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue)) 1323193323Sed if (TVPN->getParent() == TrueSucc) 1324193323Sed TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1325193323Sed if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue)) 1326193323Sed if (FVPN->getParent() == FalseSucc) 1327193323Sed FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1328193323Sed 1329193323Sed // In order for this transformation to be safe, we must be able to 1330193323Sed // unconditionally execute both operands to the return. This is 1331193323Sed // normally the case, but we could have a potentially-trapping 1332193323Sed // constant expression that prevents this transformation from being 1333193323Sed // safe. 1334193323Sed if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue)) 1335193323Sed if (TCV->canTrap()) 1336193323Sed return false; 1337193323Sed if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue)) 1338193323Sed if (FCV->canTrap()) 1339193323Sed return false; 1340193323Sed 1341193323Sed // Okay, we collected all the mapped values and checked them for sanity, and 1342193323Sed // defined to really do this transformation. First, update the CFG. 1343193323Sed TrueSucc->removePredecessor(BI->getParent()); 1344193323Sed FalseSucc->removePredecessor(BI->getParent()); 1345193323Sed 1346193323Sed // Insert select instructions where needed. 1347193323Sed Value *BrCond = BI->getCondition(); 1348193323Sed if (TrueValue) { 1349193323Sed // Insert a select if the results differ. 1350193323Sed if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) { 1351193323Sed } else if (isa<UndefValue>(TrueValue)) { 1352193323Sed TrueValue = FalseValue; 1353193323Sed } else { 1354193323Sed TrueValue = SelectInst::Create(BrCond, TrueValue, 1355193323Sed FalseValue, "retval", BI); 1356193323Sed } 1357193323Sed } 1358193323Sed 1359193323Sed Value *RI = !TrueValue ? 1360198090Srdivacky ReturnInst::Create(BI->getContext(), BI) : 1361198090Srdivacky ReturnInst::Create(BI->getContext(), TrueValue, BI); 1362198090Srdivacky (void) RI; 1363193323Sed 1364202375Srdivacky DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" 1365198090Srdivacky << "\n " << *BI << "NewRet = " << *RI 1366198090Srdivacky << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc); 1367193323Sed 1368193323Sed EraseTerminatorInstAndDCECond(BI); 1369193323Sed 1370193323Sed return true; 1371193323Sed} 1372193323Sed 1373193323Sed/// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch, 1374193323Sed/// and if a predecessor branches to us and one of our successors, fold the 1375193323Sed/// setcc into the predecessor and use logical operations to pick the right 1376193323Sed/// destination. 1377195340Sedbool llvm::FoldBranchToCommonDest(BranchInst *BI) { 1378193323Sed BasicBlock *BB = BI->getParent(); 1379193323Sed Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); 1380193323Sed if (Cond == 0) return false; 1381193323Sed 1382193323Sed 1383193323Sed // Only allow this if the condition is a simple instruction that can be 1384193323Sed // executed unconditionally. It must be in the same block as the branch, and 1385193323Sed // must be at the front of the block. 1386193323Sed BasicBlock::iterator FrontIt = BB->front(); 1387193323Sed // Ignore dbg intrinsics. 1388193323Sed while(isa<DbgInfoIntrinsic>(FrontIt)) 1389193323Sed ++FrontIt; 1390193323Sed if ((!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) || 1391193323Sed Cond->getParent() != BB || &*FrontIt != Cond || !Cond->hasOneUse()) { 1392193323Sed return false; 1393193323Sed } 1394193323Sed 1395193323Sed // Make sure the instruction after the condition is the cond branch. 1396193323Sed BasicBlock::iterator CondIt = Cond; ++CondIt; 1397193323Sed // Ingore dbg intrinsics. 1398193323Sed while(isa<DbgInfoIntrinsic>(CondIt)) 1399193323Sed ++CondIt; 1400193323Sed if (&*CondIt != BI) { 1401193323Sed assert (!isa<DbgInfoIntrinsic>(CondIt) && "Hey do not forget debug info!"); 1402193323Sed return false; 1403193323Sed } 1404193323Sed 1405193323Sed // Cond is known to be a compare or binary operator. Check to make sure that 1406193323Sed // neither operand is a potentially-trapping constant expression. 1407193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0))) 1408193323Sed if (CE->canTrap()) 1409193323Sed return false; 1410193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1))) 1411193323Sed if (CE->canTrap()) 1412193323Sed return false; 1413193323Sed 1414193323Sed 1415193323Sed // Finally, don't infinitely unroll conditional loops. 1416193323Sed BasicBlock *TrueDest = BI->getSuccessor(0); 1417193323Sed BasicBlock *FalseDest = BI->getSuccessor(1); 1418193323Sed if (TrueDest == BB || FalseDest == BB) 1419193323Sed return false; 1420193323Sed 1421193323Sed for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 1422193323Sed BasicBlock *PredBlock = *PI; 1423193323Sed BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator()); 1424193323Sed 1425193323Sed // Check that we have two conditional branches. If there is a PHI node in 1426193323Sed // the common successor, verify that the same value flows in from both 1427193323Sed // blocks. 1428193323Sed if (PBI == 0 || PBI->isUnconditional() || 1429193323Sed !SafeToMergeTerminators(BI, PBI)) 1430193323Sed continue; 1431193323Sed 1432193323Sed Instruction::BinaryOps Opc; 1433193323Sed bool InvertPredCond = false; 1434193323Sed 1435193323Sed if (PBI->getSuccessor(0) == TrueDest) 1436193323Sed Opc = Instruction::Or; 1437193323Sed else if (PBI->getSuccessor(1) == FalseDest) 1438193323Sed Opc = Instruction::And; 1439193323Sed else if (PBI->getSuccessor(0) == FalseDest) 1440193323Sed Opc = Instruction::And, InvertPredCond = true; 1441193323Sed else if (PBI->getSuccessor(1) == TrueDest) 1442193323Sed Opc = Instruction::Or, InvertPredCond = true; 1443193323Sed else 1444193323Sed continue; 1445193323Sed 1446202375Srdivacky DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB); 1447193323Sed 1448193323Sed // If we need to invert the condition in the pred block to match, do so now. 1449193323Sed if (InvertPredCond) { 1450193323Sed Value *NewCond = 1451193323Sed BinaryOperator::CreateNot(PBI->getCondition(), 1452193323Sed PBI->getCondition()->getName()+".not", PBI); 1453193323Sed PBI->setCondition(NewCond); 1454193323Sed BasicBlock *OldTrue = PBI->getSuccessor(0); 1455193323Sed BasicBlock *OldFalse = PBI->getSuccessor(1); 1456193323Sed PBI->setSuccessor(0, OldFalse); 1457193323Sed PBI->setSuccessor(1, OldTrue); 1458193323Sed } 1459193323Sed 1460193323Sed // Clone Cond into the predecessor basic block, and or/and the 1461193323Sed // two conditions together. 1462193323Sed Instruction *New = Cond->clone(); 1463193323Sed PredBlock->getInstList().insert(PBI, New); 1464193323Sed New->takeName(Cond); 1465193323Sed Cond->setName(New->getName()+".old"); 1466193323Sed 1467193323Sed Value *NewCond = BinaryOperator::Create(Opc, PBI->getCondition(), 1468193323Sed New, "or.cond", PBI); 1469193323Sed PBI->setCondition(NewCond); 1470193323Sed if (PBI->getSuccessor(0) == BB) { 1471193323Sed AddPredecessorToBlock(TrueDest, PredBlock, BB); 1472193323Sed PBI->setSuccessor(0, TrueDest); 1473193323Sed } 1474193323Sed if (PBI->getSuccessor(1) == BB) { 1475193323Sed AddPredecessorToBlock(FalseDest, PredBlock, BB); 1476193323Sed PBI->setSuccessor(1, FalseDest); 1477193323Sed } 1478193323Sed return true; 1479193323Sed } 1480193323Sed return false; 1481193323Sed} 1482193323Sed 1483193323Sed/// SimplifyCondBranchToCondBranch - If we have a conditional branch as a 1484193323Sed/// predecessor of another block, this function tries to simplify it. We know 1485193323Sed/// that PBI and BI are both conditional branches, and BI is in one of the 1486193323Sed/// successor blocks of PBI - PBI branches to BI. 1487193323Sedstatic bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { 1488193323Sed assert(PBI->isConditional() && BI->isConditional()); 1489193323Sed BasicBlock *BB = BI->getParent(); 1490198090Srdivacky 1491193323Sed // If this block ends with a branch instruction, and if there is a 1492193323Sed // predecessor that ends on a branch of the same condition, make 1493193323Sed // this conditional branch redundant. 1494193323Sed if (PBI->getCondition() == BI->getCondition() && 1495193323Sed PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 1496193323Sed // Okay, the outcome of this conditional branch is statically 1497193323Sed // knowable. If this block had a single pred, handle specially. 1498193323Sed if (BB->getSinglePredecessor()) { 1499193323Sed // Turn this into a branch on constant. 1500193323Sed bool CondIsTrue = PBI->getSuccessor(0) == BB; 1501198090Srdivacky BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 1502198090Srdivacky CondIsTrue)); 1503193323Sed return true; // Nuke the branch on constant. 1504193323Sed } 1505193323Sed 1506193323Sed // Otherwise, if there are multiple predecessors, insert a PHI that merges 1507193323Sed // in the constant and simplify the block result. Subsequent passes of 1508193323Sed // simplifycfg will thread the block. 1509193323Sed if (BlockIsSimpleEnoughToThreadThrough(BB)) { 1510198090Srdivacky PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()), 1511193323Sed BI->getCondition()->getName() + ".pr", 1512193323Sed BB->begin()); 1513193323Sed // Okay, we're going to insert the PHI node. Since PBI is not the only 1514193323Sed // predecessor, compute the PHI'd conditional value for all of the preds. 1515193323Sed // Any predecessor where the condition is not computable we keep symbolic. 1516193323Sed for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 1517193323Sed if ((PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) && 1518193323Sed PBI != BI && PBI->isConditional() && 1519193323Sed PBI->getCondition() == BI->getCondition() && 1520193323Sed PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 1521193323Sed bool CondIsTrue = PBI->getSuccessor(0) == BB; 1522198090Srdivacky NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 1523193323Sed CondIsTrue), *PI); 1524193323Sed } else { 1525193323Sed NewPN->addIncoming(BI->getCondition(), *PI); 1526193323Sed } 1527193323Sed 1528193323Sed BI->setCondition(NewPN); 1529193323Sed return true; 1530193323Sed } 1531193323Sed } 1532193323Sed 1533193323Sed // If this is a conditional branch in an empty block, and if any 1534193323Sed // predecessors is a conditional branch to one of our destinations, 1535193323Sed // fold the conditions into logical ops and one cond br. 1536193323Sed BasicBlock::iterator BBI = BB->begin(); 1537193323Sed // Ignore dbg intrinsics. 1538193323Sed while (isa<DbgInfoIntrinsic>(BBI)) 1539193323Sed ++BBI; 1540193323Sed if (&*BBI != BI) 1541193323Sed return false; 1542193323Sed 1543193323Sed 1544193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BI->getCondition())) 1545193323Sed if (CE->canTrap()) 1546193323Sed return false; 1547193323Sed 1548193323Sed int PBIOp, BIOp; 1549193323Sed if (PBI->getSuccessor(0) == BI->getSuccessor(0)) 1550193323Sed PBIOp = BIOp = 0; 1551193323Sed else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) 1552193323Sed PBIOp = 0, BIOp = 1; 1553193323Sed else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) 1554193323Sed PBIOp = 1, BIOp = 0; 1555193323Sed else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) 1556193323Sed PBIOp = BIOp = 1; 1557193323Sed else 1558193323Sed return false; 1559193323Sed 1560193323Sed // Check to make sure that the other destination of this branch 1561193323Sed // isn't BB itself. If so, this is an infinite loop that will 1562193323Sed // keep getting unwound. 1563193323Sed if (PBI->getSuccessor(PBIOp) == BB) 1564193323Sed return false; 1565193323Sed 1566193323Sed // Do not perform this transformation if it would require 1567193323Sed // insertion of a large number of select instructions. For targets 1568193323Sed // without predication/cmovs, this is a big pessimization. 1569193323Sed BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 1570193323Sed 1571193323Sed unsigned NumPhis = 0; 1572193323Sed for (BasicBlock::iterator II = CommonDest->begin(); 1573193323Sed isa<PHINode>(II); ++II, ++NumPhis) 1574193323Sed if (NumPhis > 2) // Disable this xform. 1575193323Sed return false; 1576193323Sed 1577193323Sed // Finally, if everything is ok, fold the branches to logical ops. 1578193323Sed BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); 1579193323Sed 1580202375Srdivacky DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent() 1581198090Srdivacky << "AND: " << *BI->getParent()); 1582193323Sed 1583193323Sed 1584193323Sed // If OtherDest *is* BB, then BB is a basic block with a single conditional 1585193323Sed // branch in it, where one edge (OtherDest) goes back to itself but the other 1586193323Sed // exits. We don't *know* that the program avoids the infinite loop 1587193323Sed // (even though that seems likely). If we do this xform naively, we'll end up 1588193323Sed // recursively unpeeling the loop. Since we know that (after the xform is 1589193323Sed // done) that the block *is* infinite if reached, we just make it an obviously 1590193323Sed // infinite loop with no cond branch. 1591193323Sed if (OtherDest == BB) { 1592193323Sed // Insert it at the end of the function, because it's either code, 1593193323Sed // or it won't matter if it's hot. :) 1594198090Srdivacky BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(), 1595198090Srdivacky "infloop", BB->getParent()); 1596193323Sed BranchInst::Create(InfLoopBlock, InfLoopBlock); 1597193323Sed OtherDest = InfLoopBlock; 1598193323Sed } 1599193323Sed 1600202375Srdivacky DEBUG(dbgs() << *PBI->getParent()->getParent()); 1601193323Sed 1602193323Sed // BI may have other predecessors. Because of this, we leave 1603193323Sed // it alone, but modify PBI. 1604193323Sed 1605193323Sed // Make sure we get to CommonDest on True&True directions. 1606193323Sed Value *PBICond = PBI->getCondition(); 1607193323Sed if (PBIOp) 1608193323Sed PBICond = BinaryOperator::CreateNot(PBICond, 1609193323Sed PBICond->getName()+".not", 1610193323Sed PBI); 1611193323Sed Value *BICond = BI->getCondition(); 1612193323Sed if (BIOp) 1613193323Sed BICond = BinaryOperator::CreateNot(BICond, 1614193323Sed BICond->getName()+".not", 1615193323Sed PBI); 1616193323Sed // Merge the conditions. 1617193323Sed Value *Cond = BinaryOperator::CreateOr(PBICond, BICond, "brmerge", PBI); 1618193323Sed 1619193323Sed // Modify PBI to branch on the new condition to the new dests. 1620193323Sed PBI->setCondition(Cond); 1621193323Sed PBI->setSuccessor(0, CommonDest); 1622193323Sed PBI->setSuccessor(1, OtherDest); 1623193323Sed 1624193323Sed // OtherDest may have phi nodes. If so, add an entry from PBI's 1625193323Sed // block that are identical to the entries for BI's block. 1626193323Sed PHINode *PN; 1627193323Sed for (BasicBlock::iterator II = OtherDest->begin(); 1628193323Sed (PN = dyn_cast<PHINode>(II)); ++II) { 1629193323Sed Value *V = PN->getIncomingValueForBlock(BB); 1630193323Sed PN->addIncoming(V, PBI->getParent()); 1631193323Sed } 1632193323Sed 1633193323Sed // We know that the CommonDest already had an edge from PBI to 1634193323Sed // it. If it has PHIs though, the PHIs may have different 1635193323Sed // entries for BB and PBI's BB. If so, insert a select to make 1636193323Sed // them agree. 1637193323Sed for (BasicBlock::iterator II = CommonDest->begin(); 1638193323Sed (PN = dyn_cast<PHINode>(II)); ++II) { 1639193323Sed Value *BIV = PN->getIncomingValueForBlock(BB); 1640193323Sed unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); 1641193323Sed Value *PBIV = PN->getIncomingValue(PBBIdx); 1642193323Sed if (BIV != PBIV) { 1643193323Sed // Insert a select in PBI to pick the right value. 1644193323Sed Value *NV = SelectInst::Create(PBICond, PBIV, BIV, 1645193323Sed PBIV->getName()+".mux", PBI); 1646193323Sed PN->setIncomingValue(PBBIdx, NV); 1647193323Sed } 1648193323Sed } 1649193323Sed 1650202375Srdivacky DEBUG(dbgs() << "INTO: " << *PBI->getParent()); 1651202375Srdivacky DEBUG(dbgs() << *PBI->getParent()->getParent()); 1652193323Sed 1653193323Sed // This basic block is probably dead. We know it has at least 1654193323Sed // one fewer predecessor. 1655193323Sed return true; 1656193323Sed} 1657193323Sed 1658203954Srdivackybool SimplifyCFGOpt::run(BasicBlock *BB) { 1659193323Sed bool Changed = false; 1660193323Sed Function *M = BB->getParent(); 1661193323Sed 1662193323Sed assert(BB && BB->getParent() && "Block not embedded in function!"); 1663193323Sed assert(BB->getTerminator() && "Degenerate basic block encountered!"); 1664193323Sed assert(&BB->getParent()->getEntryBlock() != BB && 1665193323Sed "Can't Simplify entry block!"); 1666193323Sed 1667193323Sed // Remove basic blocks that have no predecessors... or that just have themself 1668193323Sed // as a predecessor. These are unreachable. 1669193323Sed if (pred_begin(BB) == pred_end(BB) || BB->getSinglePredecessor() == BB) { 1670202375Srdivacky DEBUG(dbgs() << "Removing BB: \n" << *BB); 1671193323Sed DeleteDeadBlock(BB); 1672193323Sed return true; 1673193323Sed } 1674193323Sed 1675193323Sed // Check to see if we can constant propagate this terminator instruction 1676193323Sed // away... 1677193323Sed Changed |= ConstantFoldTerminator(BB); 1678193323Sed 1679198892Srdivacky // Check for and eliminate duplicate PHI nodes in this block. 1680198892Srdivacky Changed |= EliminateDuplicatePHINodes(BB); 1681198892Srdivacky 1682193323Sed // If there is a trivial two-entry PHI node in this basic block, and we can 1683193323Sed // eliminate it, do so now. 1684193323Sed if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 1685193323Sed if (PN->getNumIncomingValues() == 2) 1686193323Sed Changed |= FoldTwoEntryPHINode(PN); 1687193323Sed 1688193323Sed // If this is a returning block with only PHI nodes in it, fold the return 1689193323Sed // instruction into any unconditional branch predecessors. 1690193323Sed // 1691193323Sed // If any predecessor is a conditional branch that just selects among 1692193323Sed // different return values, fold the replace the branch/return with a select 1693193323Sed // and return. 1694193323Sed if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 1695193323Sed if (isTerminatorFirstRelevantInsn(BB, BB->getTerminator())) { 1696193323Sed // Find predecessors that end with branches. 1697193323Sed SmallVector<BasicBlock*, 8> UncondBranchPreds; 1698193323Sed SmallVector<BranchInst*, 8> CondBranchPreds; 1699193323Sed for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 1700193323Sed TerminatorInst *PTI = (*PI)->getTerminator(); 1701193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) { 1702193323Sed if (BI->isUnconditional()) 1703193323Sed UncondBranchPreds.push_back(*PI); 1704193323Sed else 1705193323Sed CondBranchPreds.push_back(BI); 1706193323Sed } 1707193323Sed } 1708193323Sed 1709193323Sed // If we found some, do the transformation! 1710193323Sed if (!UncondBranchPreds.empty()) { 1711193323Sed while (!UncondBranchPreds.empty()) { 1712193323Sed BasicBlock *Pred = UncondBranchPreds.pop_back_val(); 1713202375Srdivacky DEBUG(dbgs() << "FOLDING: " << *BB 1714198090Srdivacky << "INTO UNCOND BRANCH PRED: " << *Pred); 1715193323Sed Instruction *UncondBranch = Pred->getTerminator(); 1716193323Sed // Clone the return and add it to the end of the predecessor. 1717193323Sed Instruction *NewRet = RI->clone(); 1718193323Sed Pred->getInstList().push_back(NewRet); 1719193323Sed 1720193323Sed // If the return instruction returns a value, and if the value was a 1721193323Sed // PHI node in "BB", propagate the right value into the return. 1722193323Sed for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end(); 1723193323Sed i != e; ++i) 1724193323Sed if (PHINode *PN = dyn_cast<PHINode>(*i)) 1725193323Sed if (PN->getParent() == BB) 1726193323Sed *i = PN->getIncomingValueForBlock(Pred); 1727193323Sed 1728193323Sed // Update any PHI nodes in the returning block to realize that we no 1729193323Sed // longer branch to them. 1730193323Sed BB->removePredecessor(Pred); 1731193323Sed Pred->getInstList().erase(UncondBranch); 1732193323Sed } 1733193323Sed 1734193323Sed // If we eliminated all predecessors of the block, delete the block now. 1735193323Sed if (pred_begin(BB) == pred_end(BB)) 1736193323Sed // We know there are no successors, so just nuke the block. 1737193323Sed M->getBasicBlockList().erase(BB); 1738193323Sed 1739193323Sed return true; 1740193323Sed } 1741193323Sed 1742193323Sed // Check out all of the conditional branches going to this return 1743193323Sed // instruction. If any of them just select between returns, change the 1744193323Sed // branch itself into a select/return pair. 1745193323Sed while (!CondBranchPreds.empty()) { 1746193323Sed BranchInst *BI = CondBranchPreds.pop_back_val(); 1747193323Sed 1748193323Sed // Check to see if the non-BB successor is also a return block. 1749193323Sed if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) && 1750193323Sed isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) && 1751193323Sed SimplifyCondBranchToTwoReturns(BI)) 1752193323Sed return true; 1753193323Sed } 1754193323Sed } 1755193323Sed } else if (isa<UnwindInst>(BB->begin())) { 1756193323Sed // Check to see if the first instruction in this block is just an unwind. 1757193323Sed // If so, replace any invoke instructions which use this as an exception 1758198090Srdivacky // destination with call instructions. 1759193323Sed // 1760193323Sed SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 1761193323Sed while (!Preds.empty()) { 1762193323Sed BasicBlock *Pred = Preds.back(); 1763198090Srdivacky if (InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator())) 1764193323Sed if (II->getUnwindDest() == BB) { 1765193323Sed // Insert a new branch instruction before the invoke, because this 1766198090Srdivacky // is now a fall through. 1767193323Sed BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); 1768193323Sed Pred->getInstList().remove(II); // Take out of symbol table 1769193323Sed 1770198090Srdivacky // Insert the call now. 1771193323Sed SmallVector<Value*,8> Args(II->op_begin()+3, II->op_end()); 1772193323Sed CallInst *CI = CallInst::Create(II->getCalledValue(), 1773193323Sed Args.begin(), Args.end(), 1774193323Sed II->getName(), BI); 1775193323Sed CI->setCallingConv(II->getCallingConv()); 1776193323Sed CI->setAttributes(II->getAttributes()); 1777198090Srdivacky // If the invoke produced a value, the Call now does instead. 1778193323Sed II->replaceAllUsesWith(CI); 1779193323Sed delete II; 1780193323Sed Changed = true; 1781193323Sed } 1782193323Sed 1783193323Sed Preds.pop_back(); 1784193323Sed } 1785193323Sed 1786193323Sed // If this block is now dead, remove it. 1787193323Sed if (pred_begin(BB) == pred_end(BB)) { 1788193323Sed // We know there are no successors, so just nuke the block. 1789193323Sed M->getBasicBlockList().erase(BB); 1790193323Sed return true; 1791193323Sed } 1792193323Sed 1793193323Sed } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 1794193323Sed if (isValueEqualityComparison(SI)) { 1795193323Sed // If we only have one predecessor, and if it is a branch on this value, 1796193323Sed // see if that predecessor totally determines the outcome of this switch. 1797193323Sed if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1798193323Sed if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) 1799193323Sed return SimplifyCFG(BB) || 1; 1800193323Sed 1801193323Sed // If the block only contains the switch, see if we can fold the block 1802193323Sed // away into any preds. 1803193323Sed BasicBlock::iterator BBI = BB->begin(); 1804193323Sed // Ignore dbg intrinsics. 1805193323Sed while (isa<DbgInfoIntrinsic>(BBI)) 1806193323Sed ++BBI; 1807193323Sed if (SI == &*BBI) 1808193323Sed if (FoldValueComparisonIntoPredecessors(SI)) 1809193323Sed return SimplifyCFG(BB) || 1; 1810193323Sed } 1811193323Sed } else if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 1812193323Sed if (BI->isUnconditional()) { 1813193323Sed BasicBlock::iterator BBI = BB->getFirstNonPHI(); 1814193323Sed 1815193323Sed // Ignore dbg intrinsics. 1816193323Sed while (isa<DbgInfoIntrinsic>(BBI)) 1817193323Sed ++BBI; 1818199481Srdivacky if (BBI->isTerminator()) // Terminator is the only non-phi instruction! 1819199481Srdivacky if (TryToSimplifyUncondBranchFromEmptyBlock(BB)) 1820193323Sed return true; 1821193323Sed 1822193323Sed } else { // Conditional branch 1823193323Sed if (isValueEqualityComparison(BI)) { 1824193323Sed // If we only have one predecessor, and if it is a branch on this value, 1825193323Sed // see if that predecessor totally determines the outcome of this 1826193323Sed // switch. 1827193323Sed if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 1828193323Sed if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) 1829193323Sed return SimplifyCFG(BB) || 1; 1830193323Sed 1831193323Sed // This block must be empty, except for the setcond inst, if it exists. 1832193323Sed // Ignore dbg intrinsics. 1833193323Sed BasicBlock::iterator I = BB->begin(); 1834193323Sed // Ignore dbg intrinsics. 1835193323Sed while (isa<DbgInfoIntrinsic>(I)) 1836193323Sed ++I; 1837193323Sed if (&*I == BI) { 1838193323Sed if (FoldValueComparisonIntoPredecessors(BI)) 1839193323Sed return SimplifyCFG(BB) | true; 1840193323Sed } else if (&*I == cast<Instruction>(BI->getCondition())){ 1841193323Sed ++I; 1842193323Sed // Ignore dbg intrinsics. 1843193323Sed while (isa<DbgInfoIntrinsic>(I)) 1844193323Sed ++I; 1845193323Sed if(&*I == BI) { 1846193323Sed if (FoldValueComparisonIntoPredecessors(BI)) 1847193323Sed return SimplifyCFG(BB) | true; 1848193323Sed } 1849193323Sed } 1850193323Sed } 1851193323Sed 1852193323Sed // If this is a branch on a phi node in the current block, thread control 1853193323Sed // through this block if any PHI node entries are constants. 1854193323Sed if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 1855193323Sed if (PN->getParent() == BI->getParent()) 1856193323Sed if (FoldCondBranchOnPHI(BI)) 1857193323Sed return SimplifyCFG(BB) | true; 1858193323Sed 1859193323Sed // If this basic block is ONLY a setcc and a branch, and if a predecessor 1860193323Sed // branches to us and one of our successors, fold the setcc into the 1861193323Sed // predecessor and use logical operations to pick the right destination. 1862193323Sed if (FoldBranchToCommonDest(BI)) 1863193323Sed return SimplifyCFG(BB) | 1; 1864193323Sed 1865193323Sed 1866193323Sed // Scan predecessor blocks for conditional branches. 1867193323Sed for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 1868193323Sed if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 1869193323Sed if (PBI != BI && PBI->isConditional()) 1870193323Sed if (SimplifyCondBranchToCondBranch(PBI, BI)) 1871193323Sed return SimplifyCFG(BB) | true; 1872193323Sed } 1873193323Sed } else if (isa<UnreachableInst>(BB->getTerminator())) { 1874193323Sed // If there are any instructions immediately before the unreachable that can 1875193323Sed // be removed, do so. 1876193323Sed Instruction *Unreachable = BB->getTerminator(); 1877193323Sed while (Unreachable != BB->begin()) { 1878193323Sed BasicBlock::iterator BBI = Unreachable; 1879193323Sed --BBI; 1880193323Sed // Do not delete instructions that can have side effects, like calls 1881193323Sed // (which may never return) and volatile loads and stores. 1882193323Sed if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break; 1883193323Sed 1884193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) 1885193323Sed if (SI->isVolatile()) 1886193323Sed break; 1887193323Sed 1888193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) 1889193323Sed if (LI->isVolatile()) 1890193323Sed break; 1891193323Sed 1892193323Sed // Delete this instruction 1893193323Sed BB->getInstList().erase(BBI); 1894193323Sed Changed = true; 1895193323Sed } 1896193323Sed 1897193323Sed // If the unreachable instruction is the first in the block, take a gander 1898193323Sed // at all of the predecessors of this instruction, and simplify them. 1899193323Sed if (&BB->front() == Unreachable) { 1900193323Sed SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 1901193323Sed for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 1902193323Sed TerminatorInst *TI = Preds[i]->getTerminator(); 1903193323Sed 1904193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1905193323Sed if (BI->isUnconditional()) { 1906193323Sed if (BI->getSuccessor(0) == BB) { 1907198090Srdivacky new UnreachableInst(TI->getContext(), TI); 1908193323Sed TI->eraseFromParent(); 1909193323Sed Changed = true; 1910193323Sed } 1911193323Sed } else { 1912193323Sed if (BI->getSuccessor(0) == BB) { 1913193323Sed BranchInst::Create(BI->getSuccessor(1), BI); 1914193323Sed EraseTerminatorInstAndDCECond(BI); 1915193323Sed } else if (BI->getSuccessor(1) == BB) { 1916193323Sed BranchInst::Create(BI->getSuccessor(0), BI); 1917193323Sed EraseTerminatorInstAndDCECond(BI); 1918193323Sed Changed = true; 1919193323Sed } 1920193323Sed } 1921193323Sed } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1922193323Sed for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1923193323Sed if (SI->getSuccessor(i) == BB) { 1924193323Sed BB->removePredecessor(SI->getParent()); 1925193323Sed SI->removeCase(i); 1926193323Sed --i; --e; 1927193323Sed Changed = true; 1928193323Sed } 1929193323Sed // If the default value is unreachable, figure out the most popular 1930193323Sed // destination and make it the default. 1931193323Sed if (SI->getSuccessor(0) == BB) { 1932193323Sed std::map<BasicBlock*, unsigned> Popularity; 1933193323Sed for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1934193323Sed Popularity[SI->getSuccessor(i)]++; 1935193323Sed 1936193323Sed // Find the most popular block. 1937193323Sed unsigned MaxPop = 0; 1938193323Sed BasicBlock *MaxBlock = 0; 1939193323Sed for (std::map<BasicBlock*, unsigned>::iterator 1940193323Sed I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 1941193323Sed if (I->second > MaxPop) { 1942193323Sed MaxPop = I->second; 1943193323Sed MaxBlock = I->first; 1944193323Sed } 1945193323Sed } 1946193323Sed if (MaxBlock) { 1947193323Sed // Make this the new default, allowing us to delete any explicit 1948193323Sed // edges to it. 1949193323Sed SI->setSuccessor(0, MaxBlock); 1950193323Sed Changed = true; 1951193323Sed 1952193323Sed // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 1953193323Sed // it. 1954193323Sed if (isa<PHINode>(MaxBlock->begin())) 1955193323Sed for (unsigned i = 0; i != MaxPop-1; ++i) 1956193323Sed MaxBlock->removePredecessor(SI->getParent()); 1957193323Sed 1958193323Sed for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 1959193323Sed if (SI->getSuccessor(i) == MaxBlock) { 1960193323Sed SI->removeCase(i); 1961193323Sed --i; --e; 1962193323Sed } 1963193323Sed } 1964193323Sed } 1965193323Sed } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 1966193323Sed if (II->getUnwindDest() == BB) { 1967193323Sed // Convert the invoke to a call instruction. This would be a good 1968193323Sed // place to note that the call does not throw though. 1969193323Sed BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); 1970193323Sed II->removeFromParent(); // Take out of symbol table 1971193323Sed 1972193323Sed // Insert the call now... 1973193323Sed SmallVector<Value*, 8> Args(II->op_begin()+3, II->op_end()); 1974193323Sed CallInst *CI = CallInst::Create(II->getCalledValue(), 1975193323Sed Args.begin(), Args.end(), 1976193323Sed II->getName(), BI); 1977193323Sed CI->setCallingConv(II->getCallingConv()); 1978193323Sed CI->setAttributes(II->getAttributes()); 1979193323Sed // If the invoke produced a value, the Call does now instead. 1980193323Sed II->replaceAllUsesWith(CI); 1981193323Sed delete II; 1982193323Sed Changed = true; 1983193323Sed } 1984193323Sed } 1985193323Sed } 1986193323Sed 1987193323Sed // If this block is now dead, remove it. 1988193323Sed if (pred_begin(BB) == pred_end(BB)) { 1989193323Sed // We know there are no successors, so just nuke the block. 1990193323Sed M->getBasicBlockList().erase(BB); 1991193323Sed return true; 1992193323Sed } 1993193323Sed } 1994193323Sed } 1995193323Sed 1996193323Sed // Merge basic blocks into their predecessor if there is only one distinct 1997193323Sed // pred, and if there is only one distinct successor of the predecessor, and 1998193323Sed // if there are no PHI nodes. 1999193323Sed // 2000193323Sed if (MergeBlockIntoPredecessor(BB)) 2001193323Sed return true; 2002193323Sed 2003193323Sed // Otherwise, if this block only has a single predecessor, and if that block 2004193323Sed // is a conditional branch, see if we can hoist any code from this block up 2005193323Sed // into our predecessor. 2006193323Sed pred_iterator PI(pred_begin(BB)), PE(pred_end(BB)); 2007193323Sed BasicBlock *OnlyPred = *PI++; 2008193323Sed for (; PI != PE; ++PI) // Search all predecessors, see if they are all same 2009193323Sed if (*PI != OnlyPred) { 2010193323Sed OnlyPred = 0; // There are multiple different predecessors... 2011193323Sed break; 2012193323Sed } 2013193323Sed 2014193323Sed if (OnlyPred) 2015193323Sed if (BranchInst *BI = dyn_cast<BranchInst>(OnlyPred->getTerminator())) 2016193323Sed if (BI->isConditional()) { 2017193323Sed // Get the other block. 2018193323Sed BasicBlock *OtherBB = BI->getSuccessor(BI->getSuccessor(0) == BB); 2019193323Sed PI = pred_begin(OtherBB); 2020193323Sed ++PI; 2021193323Sed 2022193323Sed if (PI == pred_end(OtherBB)) { 2023193323Sed // We have a conditional branch to two blocks that are only reachable 2024193323Sed // from the condbr. We know that the condbr dominates the two blocks, 2025193323Sed // so see if there is any identical code in the "then" and "else" 2026193323Sed // blocks. If so, we can hoist it up to the branching block. 2027193323Sed Changed |= HoistThenElseCodeToIf(BI); 2028193323Sed } else { 2029193323Sed BasicBlock* OnlySucc = NULL; 2030193323Sed for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); 2031193323Sed SI != SE; ++SI) { 2032193323Sed if (!OnlySucc) 2033193323Sed OnlySucc = *SI; 2034193323Sed else if (*SI != OnlySucc) { 2035193323Sed OnlySucc = 0; // There are multiple distinct successors! 2036193323Sed break; 2037193323Sed } 2038193323Sed } 2039193323Sed 2040193323Sed if (OnlySucc == OtherBB) { 2041193323Sed // If BB's only successor is the other successor of the predecessor, 2042193323Sed // i.e. a triangle, see if we can hoist any code from this block up 2043193323Sed // to the "if" block. 2044193323Sed Changed |= SpeculativelyExecuteBB(BI, BB); 2045193323Sed } 2046193323Sed } 2047193323Sed } 2048193323Sed 2049193323Sed for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 2050193323Sed if (BranchInst *BI = dyn_cast<BranchInst>((*PI)->getTerminator())) 2051193323Sed // Change br (X == 0 | X == 1), T, F into a switch instruction. 2052193323Sed if (BI->isConditional() && isa<Instruction>(BI->getCondition())) { 2053193323Sed Instruction *Cond = cast<Instruction>(BI->getCondition()); 2054193323Sed // If this is a bunch of seteq's or'd together, or if it's a bunch of 2055193323Sed // 'setne's and'ed together, collect them. 2056193323Sed Value *CompVal = 0; 2057193323Sed std::vector<ConstantInt*> Values; 2058193323Sed bool TrueWhenEqual = GatherValueComparisons(Cond, CompVal, Values); 2059203954Srdivacky if (CompVal) { 2060193323Sed // There might be duplicate constants in the list, which the switch 2061193323Sed // instruction can't handle, remove them now. 2062193323Sed std::sort(Values.begin(), Values.end(), ConstantIntOrdering()); 2063193323Sed Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 2064193323Sed 2065193323Sed // Figure out which block is which destination. 2066193323Sed BasicBlock *DefaultBB = BI->getSuccessor(1); 2067193323Sed BasicBlock *EdgeBB = BI->getSuccessor(0); 2068193323Sed if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 2069193323Sed 2070203954Srdivacky // Convert pointer to int before we switch. 2071203954Srdivacky if (isa<PointerType>(CompVal->getType())) { 2072203954Srdivacky assert(TD && "Cannot switch on pointer without TargetData"); 2073203954Srdivacky CompVal = new PtrToIntInst(CompVal, 2074203954Srdivacky TD->getIntPtrType(CompVal->getContext()), 2075203954Srdivacky "magicptr", BI); 2076203954Srdivacky } 2077203954Srdivacky 2078193323Sed // Create the new switch instruction now. 2079193323Sed SwitchInst *New = SwitchInst::Create(CompVal, DefaultBB, 2080193323Sed Values.size(), BI); 2081193323Sed 2082193323Sed // Add all of the 'cases' to the switch instruction. 2083193323Sed for (unsigned i = 0, e = Values.size(); i != e; ++i) 2084193323Sed New->addCase(Values[i], EdgeBB); 2085193323Sed 2086193323Sed // We added edges from PI to the EdgeBB. As such, if there were any 2087193323Sed // PHI nodes in EdgeBB, they need entries to be added corresponding to 2088193323Sed // the number of edges added. 2089193323Sed for (BasicBlock::iterator BBI = EdgeBB->begin(); 2090193323Sed isa<PHINode>(BBI); ++BBI) { 2091193323Sed PHINode *PN = cast<PHINode>(BBI); 2092193323Sed Value *InVal = PN->getIncomingValueForBlock(*PI); 2093193323Sed for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 2094193323Sed PN->addIncoming(InVal, *PI); 2095193323Sed } 2096193323Sed 2097193323Sed // Erase the old branch instruction. 2098193323Sed EraseTerminatorInstAndDCECond(BI); 2099193323Sed return true; 2100193323Sed } 2101193323Sed } 2102193323Sed 2103193323Sed return Changed; 2104193323Sed} 2105203954Srdivacky 2106203954Srdivacky/// SimplifyCFG - This function is used to do simplification of a CFG. For 2107203954Srdivacky/// example, it adjusts branches to branches to eliminate the extra hop, it 2108203954Srdivacky/// eliminates unreachable basic blocks, and does other "peephole" optimization 2109203954Srdivacky/// of the CFG. It returns true if a modification was made. 2110203954Srdivacky/// 2111203954Srdivacky/// WARNING: The entry node of a function may not be simplified. 2112203954Srdivacky/// 2113203954Srdivackybool llvm::SimplifyCFG(BasicBlock *BB, const TargetData *TD) { 2114203954Srdivacky return SimplifyCFGOpt(TD).run(BB); 2115203954Srdivacky} 2116