SimplifyCFG.cpp revision 221345
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" 22218893Sdim#include "llvm/Analysis/InstructionSimplify.h" 23203954Srdivacky#include "llvm/Target/TargetData.h" 24193323Sed#include "llvm/Transforms/Utils/BasicBlockUtils.h" 25198892Srdivacky#include "llvm/ADT/DenseMap.h" 26193323Sed#include "llvm/ADT/SmallVector.h" 27193323Sed#include "llvm/ADT/SmallPtrSet.h" 28193323Sed#include "llvm/ADT/Statistic.h" 29218893Sdim#include "llvm/ADT/STLExtras.h" 30218893Sdim#include "llvm/Support/CFG.h" 31218893Sdim#include "llvm/Support/CommandLine.h" 32218893Sdim#include "llvm/Support/ConstantRange.h" 33218893Sdim#include "llvm/Support/Debug.h" 34218893Sdim#include "llvm/Support/raw_ostream.h" 35193323Sed#include <algorithm> 36193323Sed#include <set> 37193323Sed#include <map> 38193323Sedusing namespace llvm; 39193323Sed 40221345Sdimstatic cl::opt<unsigned> 41221345SdimPHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1), 42221345Sdim cl::desc("Control the amount of phi node folding to perform (default = 1)")); 43221345Sdim 44218893Sdimstatic cl::opt<bool> 45218893SdimDupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false), 46218893Sdim cl::desc("Duplicate return instructions into unconditional branches")); 47218893Sdim 48193323SedSTATISTIC(NumSpeculations, "Number of speculative executed instructions"); 49193323Sed 50203954Srdivackynamespace { 51203954Srdivackyclass SimplifyCFGOpt { 52203954Srdivacky const TargetData *const TD; 53203954Srdivacky 54203954Srdivacky Value *isValueEqualityComparison(TerminatorInst *TI); 55203954Srdivacky BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI, 56203954Srdivacky std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases); 57203954Srdivacky bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 58203954Srdivacky BasicBlock *Pred); 59203954Srdivacky bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI); 60203954Srdivacky 61218893Sdim bool SimplifyReturn(ReturnInst *RI); 62218893Sdim bool SimplifyUnwind(UnwindInst *UI); 63218893Sdim bool SimplifyUnreachable(UnreachableInst *UI); 64218893Sdim bool SimplifySwitch(SwitchInst *SI); 65218893Sdim bool SimplifyIndirectBr(IndirectBrInst *IBI); 66218893Sdim bool SimplifyUncondBranch(BranchInst *BI); 67218893Sdim bool SimplifyCondBranch(BranchInst *BI); 68218893Sdim 69203954Srdivackypublic: 70203954Srdivacky explicit SimplifyCFGOpt(const TargetData *td) : TD(td) {} 71203954Srdivacky bool run(BasicBlock *BB); 72203954Srdivacky}; 73203954Srdivacky} 74203954Srdivacky 75193323Sed/// SafeToMergeTerminators - Return true if it is safe to merge these two 76193323Sed/// terminator instructions together. 77193323Sed/// 78193323Sedstatic bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 79193323Sed if (SI1 == SI2) return false; // Can't merge with self! 80193323Sed 81193323Sed // It is not safe to merge these two switch instructions if they have a common 82193323Sed // successor, and if that successor has a PHI node, and if *that* PHI node has 83193323Sed // conflicting incoming values from the two switch blocks. 84193323Sed BasicBlock *SI1BB = SI1->getParent(); 85193323Sed BasicBlock *SI2BB = SI2->getParent(); 86193323Sed SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 87193323Sed 88193323Sed for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 89193323Sed if (SI1Succs.count(*I)) 90193323Sed for (BasicBlock::iterator BBI = (*I)->begin(); 91193323Sed isa<PHINode>(BBI); ++BBI) { 92193323Sed PHINode *PN = cast<PHINode>(BBI); 93193323Sed if (PN->getIncomingValueForBlock(SI1BB) != 94193323Sed PN->getIncomingValueForBlock(SI2BB)) 95193323Sed return false; 96193323Sed } 97193323Sed 98193323Sed return true; 99193323Sed} 100193323Sed 101193323Sed/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 102193323Sed/// now be entries in it from the 'NewPred' block. The values that will be 103193323Sed/// flowing into the PHI nodes will be the same as those coming in from 104193323Sed/// ExistPred, an existing predecessor of Succ. 105193323Sedstatic void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 106193323Sed BasicBlock *ExistPred) { 107193323Sed if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 108193323Sed 109193323Sed PHINode *PN; 110193323Sed for (BasicBlock::iterator I = Succ->begin(); 111193323Sed (PN = dyn_cast<PHINode>(I)); ++I) 112193323Sed PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); 113193323Sed} 114193323Sed 115193323Sed 116218893Sdim/// GetIfCondition - Given a basic block (BB) with two predecessors (and at 117218893Sdim/// least one PHI node in it), check to see if the merge at this block is due 118193323Sed/// to an "if condition". If so, return the boolean condition that determines 119193323Sed/// which entry into BB will be taken. Also, return by references the block 120193323Sed/// that will be entered from if the condition is true, and the block that will 121193323Sed/// be entered if the condition is false. 122193323Sed/// 123218893Sdim/// This does no checking to see if the true/false blocks have large or unsavory 124218893Sdim/// instructions in them. 125218893Sdimstatic Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, 126218893Sdim BasicBlock *&IfFalse) { 127218893Sdim PHINode *SomePHI = cast<PHINode>(BB->begin()); 128218893Sdim assert(SomePHI->getNumIncomingValues() == 2 && 129193323Sed "Function can only handle blocks with 2 predecessors!"); 130218893Sdim BasicBlock *Pred1 = SomePHI->getIncomingBlock(0); 131218893Sdim BasicBlock *Pred2 = SomePHI->getIncomingBlock(1); 132193323Sed 133193323Sed // We can only handle branches. Other control flow will be lowered to 134193323Sed // branches if possible anyway. 135218893Sdim BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator()); 136218893Sdim BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator()); 137218893Sdim if (Pred1Br == 0 || Pred2Br == 0) 138193323Sed return 0; 139193323Sed 140193323Sed // Eliminate code duplication by ensuring that Pred1Br is conditional if 141193323Sed // either are. 142193323Sed if (Pred2Br->isConditional()) { 143193323Sed // If both branches are conditional, we don't have an "if statement". In 144193323Sed // reality, we could transform this case, but since the condition will be 145193323Sed // required anyway, we stand no chance of eliminating it, so the xform is 146193323Sed // probably not profitable. 147193323Sed if (Pred1Br->isConditional()) 148193323Sed return 0; 149193323Sed 150193323Sed std::swap(Pred1, Pred2); 151193323Sed std::swap(Pred1Br, Pred2Br); 152193323Sed } 153193323Sed 154193323Sed if (Pred1Br->isConditional()) { 155218893Sdim // The only thing we have to watch out for here is to make sure that Pred2 156218893Sdim // doesn't have incoming edges from other blocks. If it does, the condition 157218893Sdim // doesn't dominate BB. 158218893Sdim if (Pred2->getSinglePredecessor() == 0) 159218893Sdim return 0; 160218893Sdim 161193323Sed // If we found a conditional branch predecessor, make sure that it branches 162193323Sed // to BB and Pred2Br. If it doesn't, this isn't an "if statement". 163193323Sed if (Pred1Br->getSuccessor(0) == BB && 164193323Sed Pred1Br->getSuccessor(1) == Pred2) { 165193323Sed IfTrue = Pred1; 166193323Sed IfFalse = Pred2; 167193323Sed } else if (Pred1Br->getSuccessor(0) == Pred2 && 168193323Sed Pred1Br->getSuccessor(1) == BB) { 169193323Sed IfTrue = Pred2; 170193323Sed IfFalse = Pred1; 171193323Sed } else { 172193323Sed // We know that one arm of the conditional goes to BB, so the other must 173193323Sed // go somewhere unrelated, and this must not be an "if statement". 174193323Sed return 0; 175193323Sed } 176193323Sed 177193323Sed return Pred1Br->getCondition(); 178193323Sed } 179193323Sed 180193323Sed // Ok, if we got here, both predecessors end with an unconditional branch to 181193323Sed // BB. Don't panic! If both blocks only have a single (identical) 182193323Sed // predecessor, and THAT is a conditional branch, then we're all ok! 183218893Sdim BasicBlock *CommonPred = Pred1->getSinglePredecessor(); 184218893Sdim if (CommonPred == 0 || CommonPred != Pred2->getSinglePredecessor()) 185193323Sed return 0; 186193323Sed 187193323Sed // Otherwise, if this is a conditional branch, then we can use it! 188218893Sdim BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator()); 189218893Sdim if (BI == 0) return 0; 190218893Sdim 191218893Sdim assert(BI->isConditional() && "Two successors but not conditional?"); 192218893Sdim if (BI->getSuccessor(0) == Pred1) { 193218893Sdim IfTrue = Pred1; 194218893Sdim IfFalse = Pred2; 195218893Sdim } else { 196218893Sdim IfTrue = Pred2; 197218893Sdim IfFalse = Pred1; 198193323Sed } 199218893Sdim return BI->getCondition(); 200193323Sed} 201193323Sed 202193323Sed/// DominatesMergePoint - If we have a merge point of an "if condition" as 203193323Sed/// accepted above, return true if the specified value dominates the block. We 204193323Sed/// don't handle the true generality of domination here, just a special case 205193323Sed/// which works well enough for us. 206193323Sed/// 207193323Sed/// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 208221345Sdim/// see if V (which must be an instruction) and its recursive operands 209221345Sdim/// that do not dominate BB have a combined cost lower than CostRemaining and 210221345Sdim/// are non-trapping. If both are true, the instruction is inserted into the 211221345Sdim/// set and true is returned. 212221345Sdim/// 213221345Sdim/// The cost for most non-trapping instructions is defined as 1 except for 214221345Sdim/// Select whose cost is 2. 215221345Sdim/// 216221345Sdim/// After this function returns, CostRemaining is decreased by the cost of 217221345Sdim/// V plus its non-dominating operands. If that cost is greater than 218221345Sdim/// CostRemaining, false is returned and CostRemaining is undefined. 219193323Sedstatic bool DominatesMergePoint(Value *V, BasicBlock *BB, 220221345Sdim SmallPtrSet<Instruction*, 4> *AggressiveInsts, 221221345Sdim unsigned &CostRemaining) { 222193323Sed Instruction *I = dyn_cast<Instruction>(V); 223193323Sed if (!I) { 224193323Sed // Non-instructions all dominate instructions, but not all constantexprs 225193323Sed // can be executed unconditionally. 226193323Sed if (ConstantExpr *C = dyn_cast<ConstantExpr>(V)) 227193323Sed if (C->canTrap()) 228193323Sed return false; 229193323Sed return true; 230193323Sed } 231193323Sed BasicBlock *PBB = I->getParent(); 232193323Sed 233193323Sed // We don't want to allow weird loops that might have the "if condition" in 234193323Sed // the bottom of this block. 235193323Sed if (PBB == BB) return false; 236193323Sed 237193323Sed // If this instruction is defined in a block that contains an unconditional 238193323Sed // branch to BB, then it must be in the 'conditional' part of the "if 239218893Sdim // statement". If not, it definitely dominates the region. 240218893Sdim BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator()); 241218893Sdim if (BI == 0 || BI->isConditional() || BI->getSuccessor(0) != BB) 242218893Sdim return true; 243198090Srdivacky 244218893Sdim // If we aren't allowing aggressive promotion anymore, then don't consider 245218893Sdim // instructions in the 'if region'. 246218893Sdim if (AggressiveInsts == 0) return false; 247218893Sdim 248221345Sdim // If we have seen this instruction before, don't count it again. 249221345Sdim if (AggressiveInsts->count(I)) return true; 250221345Sdim 251218893Sdim // Okay, it looks like the instruction IS in the "condition". Check to 252218893Sdim // see if it's a cheap instruction to unconditionally compute, and if it 253218893Sdim // only uses stuff defined outside of the condition. If so, hoist it out. 254218893Sdim if (!I->isSafeToSpeculativelyExecute()) 255218893Sdim return false; 256193323Sed 257221345Sdim unsigned Cost = 0; 258221345Sdim 259218893Sdim switch (I->getOpcode()) { 260218893Sdim default: return false; // Cannot hoist this out safely. 261218893Sdim case Instruction::Load: 262218893Sdim // We have to check to make sure there are no instructions before the 263218893Sdim // load in its basic block, as we are going to hoist the load out to its 264218893Sdim // predecessor. 265218893Sdim if (PBB->getFirstNonPHIOrDbg() != I) 266218893Sdim return false; 267221345Sdim Cost = 1; 268218893Sdim break; 269219077Sdim case Instruction::GetElementPtr: 270219077Sdim // GEPs are cheap if all indices are constant. 271219077Sdim if (!cast<GetElementPtrInst>(I)->hasAllConstantIndices()) 272219077Sdim return false; 273221345Sdim Cost = 1; 274219077Sdim break; 275218893Sdim case Instruction::Add: 276218893Sdim case Instruction::Sub: 277218893Sdim case Instruction::And: 278218893Sdim case Instruction::Or: 279218893Sdim case Instruction::Xor: 280218893Sdim case Instruction::Shl: 281218893Sdim case Instruction::LShr: 282218893Sdim case Instruction::AShr: 283218893Sdim case Instruction::ICmp: 284221345Sdim case Instruction::Trunc: 285221345Sdim case Instruction::ZExt: 286221345Sdim case Instruction::SExt: 287221345Sdim Cost = 1; 288218893Sdim break; // These are all cheap and non-trapping instructions. 289221345Sdim 290221345Sdim case Instruction::Select: 291221345Sdim Cost = 2; 292221345Sdim break; 293218893Sdim } 294193323Sed 295221345Sdim if (Cost > CostRemaining) 296221345Sdim return false; 297221345Sdim 298221345Sdim CostRemaining -= Cost; 299221345Sdim 300221345Sdim // Okay, we can only really hoist these out if their operands do 301221345Sdim // not take us over the cost threshold. 302218893Sdim for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) 303221345Sdim if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining)) 304218893Sdim return false; 305218893Sdim // Okay, it's safe to do this! Remember this instruction. 306218893Sdim AggressiveInsts->insert(I); 307193323Sed return true; 308193323Sed} 309193323Sed 310203954Srdivacky/// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr 311203954Srdivacky/// and PointerNullValue. Return NULL if value is not a constant int. 312218893Sdimstatic ConstantInt *GetConstantInt(Value *V, const TargetData *TD) { 313203954Srdivacky // Normal constant int. 314203954Srdivacky ConstantInt *CI = dyn_cast<ConstantInt>(V); 315204642Srdivacky if (CI || !TD || !isa<Constant>(V) || !V->getType()->isPointerTy()) 316203954Srdivacky return CI; 317203954Srdivacky 318203954Srdivacky // This is some kind of pointer constant. Turn it into a pointer-sized 319203954Srdivacky // ConstantInt if possible. 320203954Srdivacky const IntegerType *PtrTy = TD->getIntPtrType(V->getContext()); 321203954Srdivacky 322203954Srdivacky // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*). 323203954Srdivacky if (isa<ConstantPointerNull>(V)) 324203954Srdivacky return ConstantInt::get(PtrTy, 0); 325203954Srdivacky 326203954Srdivacky // IntToPtr const int. 327203954Srdivacky if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 328203954Srdivacky if (CE->getOpcode() == Instruction::IntToPtr) 329203954Srdivacky if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) { 330203954Srdivacky // The constant is very likely to have the right type already. 331203954Srdivacky if (CI->getType() == PtrTy) 332203954Srdivacky return CI; 333203954Srdivacky else 334203954Srdivacky return cast<ConstantInt> 335203954Srdivacky (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false)); 336203954Srdivacky } 337203954Srdivacky return 0; 338203954Srdivacky} 339203954Srdivacky 340218893Sdim/// GatherConstantCompares - Given a potentially 'or'd or 'and'd together 341218893Sdim/// collection of icmp eq/ne instructions that compare a value against a 342218893Sdim/// constant, return the value being compared, and stick the constant into the 343218893Sdim/// Values vector. 344218893Sdimstatic Value * 345218893SdimGatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra, 346218893Sdim const TargetData *TD, bool isEQ, unsigned &UsedICmps) { 347218893Sdim Instruction *I = dyn_cast<Instruction>(V); 348218893Sdim if (I == 0) return 0; 349218893Sdim 350218893Sdim // If this is an icmp against a constant, handle this as one of the cases. 351218893Sdim if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) { 352218893Sdim if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) { 353218893Sdim if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) { 354218893Sdim UsedICmps++; 355218893Sdim Vals.push_back(C); 356218893Sdim return I->getOperand(0); 357193323Sed } 358218893Sdim 359218893Sdim // If we have "x ult 3" comparison, for example, then we can add 0,1,2 to 360218893Sdim // the set. 361218893Sdim ConstantRange Span = 362218893Sdim ConstantRange::makeICmpRegion(ICI->getPredicate(), C->getValue()); 363218893Sdim 364218893Sdim // If this is an and/!= check then we want to optimize "x ugt 2" into 365218893Sdim // x != 0 && x != 1. 366218893Sdim if (!isEQ) 367218893Sdim Span = Span.inverse(); 368218893Sdim 369218893Sdim // If there are a ton of values, we don't want to make a ginormous switch. 370218893Sdim if (Span.getSetSize().ugt(8) || Span.isEmptySet() || 371218893Sdim // We don't handle wrapped sets yet. 372218893Sdim Span.isWrappedSet()) 373218893Sdim return 0; 374218893Sdim 375218893Sdim for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp) 376218893Sdim Vals.push_back(ConstantInt::get(V->getContext(), Tmp)); 377218893Sdim UsedICmps++; 378218893Sdim return I->getOperand(0); 379193323Sed } 380218893Sdim return 0; 381193323Sed } 382218893Sdim 383218893Sdim // Otherwise, we can only handle an | or &, depending on isEQ. 384218893Sdim if (I->getOpcode() != (isEQ ? Instruction::Or : Instruction::And)) 385218893Sdim return 0; 386218893Sdim 387218893Sdim unsigned NumValsBeforeLHS = Vals.size(); 388218893Sdim unsigned UsedICmpsBeforeLHS = UsedICmps; 389218893Sdim if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, TD, 390218893Sdim isEQ, UsedICmps)) { 391218893Sdim unsigned NumVals = Vals.size(); 392218893Sdim unsigned UsedICmpsBeforeRHS = UsedICmps; 393218893Sdim if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, 394218893Sdim isEQ, UsedICmps)) { 395218893Sdim if (LHS == RHS) 396218893Sdim return LHS; 397218893Sdim Vals.resize(NumVals); 398218893Sdim UsedICmps = UsedICmpsBeforeRHS; 399218893Sdim } 400193323Sed 401218893Sdim // The RHS of the or/and can't be folded in and we haven't used "Extra" yet, 402218893Sdim // set it and return success. 403218893Sdim if (Extra == 0 || Extra == I->getOperand(1)) { 404218893Sdim Extra = I->getOperand(1); 405218893Sdim return LHS; 406193323Sed } 407218893Sdim 408218893Sdim Vals.resize(NumValsBeforeLHS); 409218893Sdim UsedICmps = UsedICmpsBeforeLHS; 410218893Sdim return 0; 411193323Sed } 412218893Sdim 413218893Sdim // If the LHS can't be folded in, but Extra is available and RHS can, try to 414218893Sdim // use LHS as Extra. 415218893Sdim if (Extra == 0 || Extra == I->getOperand(0)) { 416218893Sdim Value *OldExtra = Extra; 417218893Sdim Extra = I->getOperand(0); 418218893Sdim if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, 419218893Sdim isEQ, UsedICmps)) 420218893Sdim return RHS; 421218893Sdim assert(Vals.size() == NumValsBeforeLHS); 422218893Sdim Extra = OldExtra; 423218893Sdim } 424218893Sdim 425193323Sed return 0; 426193323Sed} 427218893Sdim 428193323Sedstatic void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { 429193323Sed Instruction* Cond = 0; 430193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 431193323Sed Cond = dyn_cast<Instruction>(SI->getCondition()); 432193323Sed } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 433193323Sed if (BI->isConditional()) 434193323Sed Cond = dyn_cast<Instruction>(BI->getCondition()); 435218893Sdim } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) { 436218893Sdim Cond = dyn_cast<Instruction>(IBI->getAddress()); 437193323Sed } 438193323Sed 439193323Sed TI->eraseFromParent(); 440193323Sed if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond); 441193323Sed} 442193323Sed 443193323Sed/// isValueEqualityComparison - Return true if the specified terminator checks 444193323Sed/// to see if a value is equal to constant integer value. 445203954SrdivackyValue *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { 446203954Srdivacky Value *CV = 0; 447193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 448193323Sed // Do not permit merging of large switch instructions into their 449193323Sed // predecessors unless there is only one predecessor. 450203954Srdivacky if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()), 451203954Srdivacky pred_end(SI->getParent())) <= 128) 452203954Srdivacky CV = SI->getCondition(); 453203954Srdivacky } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 454193323Sed if (BI->isConditional() && BI->getCondition()->hasOneUse()) 455193323Sed if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) 456193323Sed if ((ICI->getPredicate() == ICmpInst::ICMP_EQ || 457193323Sed ICI->getPredicate() == ICmpInst::ICMP_NE) && 458218893Sdim GetConstantInt(ICI->getOperand(1), TD)) 459203954Srdivacky CV = ICI->getOperand(0); 460203954Srdivacky 461203954Srdivacky // Unwrap any lossless ptrtoint cast. 462203954Srdivacky if (TD && CV && CV->getType() == TD->getIntPtrType(CV->getContext())) 463203954Srdivacky if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) 464203954Srdivacky CV = PTII->getOperand(0); 465203954Srdivacky return CV; 466193323Sed} 467193323Sed 468193323Sed/// GetValueEqualityComparisonCases - Given a value comparison instruction, 469193323Sed/// decode all of the 'cases' that it represents and return the 'default' block. 470203954SrdivackyBasicBlock *SimplifyCFGOpt:: 471193323SedGetValueEqualityComparisonCases(TerminatorInst *TI, 472193323Sed std::vector<std::pair<ConstantInt*, 473193323Sed BasicBlock*> > &Cases) { 474193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 475193323Sed Cases.reserve(SI->getNumCases()); 476193323Sed for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 477193323Sed Cases.push_back(std::make_pair(SI->getCaseValue(i), SI->getSuccessor(i))); 478193323Sed return SI->getDefaultDest(); 479193323Sed } 480193323Sed 481193323Sed BranchInst *BI = cast<BranchInst>(TI); 482193323Sed ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 483218893Sdim Cases.push_back(std::make_pair(GetConstantInt(ICI->getOperand(1), TD), 484193323Sed BI->getSuccessor(ICI->getPredicate() == 485193323Sed ICmpInst::ICMP_NE))); 486193323Sed return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); 487193323Sed} 488193323Sed 489193323Sed 490193323Sed/// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries 491193323Sed/// in the list that match the specified block. 492193323Sedstatic void EliminateBlockCases(BasicBlock *BB, 493193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > &Cases) { 494193323Sed for (unsigned i = 0, e = Cases.size(); i != e; ++i) 495193323Sed if (Cases[i].second == BB) { 496193323Sed Cases.erase(Cases.begin()+i); 497193323Sed --i; --e; 498193323Sed } 499193323Sed} 500193323Sed 501193323Sed/// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 502193323Sed/// well. 503193323Sedstatic bool 504193323SedValuesOverlap(std::vector<std::pair<ConstantInt*, BasicBlock*> > &C1, 505193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > &C2) { 506193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > *V1 = &C1, *V2 = &C2; 507193323Sed 508193323Sed // Make V1 be smaller than V2. 509193323Sed if (V1->size() > V2->size()) 510193323Sed std::swap(V1, V2); 511193323Sed 512193323Sed if (V1->size() == 0) return false; 513193323Sed if (V1->size() == 1) { 514193323Sed // Just scan V2. 515193323Sed ConstantInt *TheVal = (*V1)[0].first; 516193323Sed for (unsigned i = 0, e = V2->size(); i != e; ++i) 517193323Sed if (TheVal == (*V2)[i].first) 518193323Sed return true; 519193323Sed } 520193323Sed 521193323Sed // Otherwise, just sort both lists and compare element by element. 522218893Sdim array_pod_sort(V1->begin(), V1->end()); 523218893Sdim array_pod_sort(V2->begin(), V2->end()); 524193323Sed unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 525193323Sed while (i1 != e1 && i2 != e2) { 526193323Sed if ((*V1)[i1].first == (*V2)[i2].first) 527193323Sed return true; 528193323Sed if ((*V1)[i1].first < (*V2)[i2].first) 529193323Sed ++i1; 530193323Sed else 531193323Sed ++i2; 532193323Sed } 533193323Sed return false; 534193323Sed} 535193323Sed 536193323Sed/// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 537193323Sed/// terminator instruction and its block is known to only have a single 538193323Sed/// predecessor block, check to see if that predecessor is also a value 539193323Sed/// comparison with the same value, and if that comparison determines the 540193323Sed/// outcome of this comparison. If so, simplify TI. This does a very limited 541193323Sed/// form of jump threading. 542203954Srdivackybool SimplifyCFGOpt:: 543203954SrdivackySimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 544203954Srdivacky BasicBlock *Pred) { 545193323Sed Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 546193323Sed if (!PredVal) return false; // Not a value comparison in predecessor. 547193323Sed 548193323Sed Value *ThisVal = isValueEqualityComparison(TI); 549193323Sed assert(ThisVal && "This isn't a value comparison!!"); 550193323Sed if (ThisVal != PredVal) return false; // Different predicates. 551193323Sed 552193323Sed // Find out information about when control will move from Pred to TI's block. 553193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 554193323Sed BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 555193323Sed PredCases); 556193323Sed EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 557193323Sed 558193323Sed // Find information about how control leaves this block. 559193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > ThisCases; 560193323Sed BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 561193323Sed EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 562193323Sed 563193323Sed // If TI's block is the default block from Pred's comparison, potentially 564193323Sed // simplify TI based on this knowledge. 565193323Sed if (PredDef == TI->getParent()) { 566193323Sed // If we are here, we know that the value is none of those cases listed in 567193323Sed // PredCases. If there are any cases in ThisCases that are in PredCases, we 568193323Sed // can simplify TI. 569218893Sdim if (!ValuesOverlap(PredCases, ThisCases)) 570218893Sdim return false; 571218893Sdim 572218893Sdim if (isa<BranchInst>(TI)) { 573218893Sdim // Okay, one of the successors of this condbr is dead. Convert it to a 574218893Sdim // uncond br. 575218893Sdim assert(ThisCases.size() == 1 && "Branch can only have one case!"); 576218893Sdim // Insert the new branch. 577218893Sdim Instruction *NI = BranchInst::Create(ThisDef, TI); 578218893Sdim (void) NI; 579193323Sed 580218893Sdim // Remove PHI node entries for the dead edge. 581218893Sdim ThisCases[0].second->removePredecessor(TI->getParent()); 582193323Sed 583218893Sdim DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 584218893Sdim << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 585193323Sed 586218893Sdim EraseTerminatorInstAndDCECond(TI); 587218893Sdim return true; 588218893Sdim } 589218893Sdim 590218893Sdim SwitchInst *SI = cast<SwitchInst>(TI); 591218893Sdim // Okay, TI has cases that are statically dead, prune them away. 592218893Sdim SmallPtrSet<Constant*, 16> DeadCases; 593218893Sdim for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 594218893Sdim DeadCases.insert(PredCases[i].first); 595193323Sed 596218893Sdim DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 597218893Sdim << "Through successor TI: " << *TI); 598193323Sed 599218893Sdim for (unsigned i = SI->getNumCases()-1; i != 0; --i) 600218893Sdim if (DeadCases.count(SI->getCaseValue(i))) { 601218893Sdim SI->getSuccessor(i)->removePredecessor(TI->getParent()); 602218893Sdim SI->removeCase(i); 603218893Sdim } 604193323Sed 605218893Sdim DEBUG(dbgs() << "Leaving: " << *TI << "\n"); 606218893Sdim return true; 607218893Sdim } 608218893Sdim 609218893Sdim // Otherwise, TI's block must correspond to some matched value. Find out 610218893Sdim // which value (or set of values) this is. 611218893Sdim ConstantInt *TIV = 0; 612218893Sdim BasicBlock *TIBB = TI->getParent(); 613218893Sdim for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 614218893Sdim if (PredCases[i].second == TIBB) { 615218893Sdim if (TIV != 0) 616218893Sdim return false; // Cannot handle multiple values coming to this block. 617218893Sdim TIV = PredCases[i].first; 618218893Sdim } 619218893Sdim assert(TIV && "No edge from pred to succ?"); 620193323Sed 621218893Sdim // Okay, we found the one constant that our value can be if we get into TI's 622218893Sdim // BB. Find out which successor will unconditionally be branched to. 623218893Sdim BasicBlock *TheRealDest = 0; 624218893Sdim for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 625218893Sdim if (ThisCases[i].first == TIV) { 626218893Sdim TheRealDest = ThisCases[i].second; 627218893Sdim break; 628193323Sed } 629193323Sed 630218893Sdim // If not handled by any explicit cases, it is handled by the default case. 631218893Sdim if (TheRealDest == 0) TheRealDest = ThisDef; 632193323Sed 633218893Sdim // Remove PHI node entries for dead edges. 634218893Sdim BasicBlock *CheckEdge = TheRealDest; 635218893Sdim for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 636218893Sdim if (*SI != CheckEdge) 637218893Sdim (*SI)->removePredecessor(TIBB); 638218893Sdim else 639218893Sdim CheckEdge = 0; 640193323Sed 641218893Sdim // Insert the new branch. 642218893Sdim Instruction *NI = BranchInst::Create(TheRealDest, TI); 643218893Sdim (void) NI; 644193323Sed 645218893Sdim DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 646218893Sdim << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 647193323Sed 648218893Sdim EraseTerminatorInstAndDCECond(TI); 649218893Sdim return true; 650193323Sed} 651193323Sed 652193323Sednamespace { 653193323Sed /// ConstantIntOrdering - This class implements a stable ordering of constant 654193323Sed /// integers that does not depend on their address. This is important for 655193323Sed /// applications that sort ConstantInt's to ensure uniqueness. 656193323Sed struct ConstantIntOrdering { 657193323Sed bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 658193323Sed return LHS->getValue().ult(RHS->getValue()); 659193323Sed } 660193323Sed }; 661193323Sed} 662193323Sed 663218893Sdimstatic int ConstantIntSortPredicate(const void *P1, const void *P2) { 664218893Sdim const ConstantInt *LHS = *(const ConstantInt**)P1; 665218893Sdim const ConstantInt *RHS = *(const ConstantInt**)P2; 666218893Sdim if (LHS->getValue().ult(RHS->getValue())) 667218893Sdim return 1; 668218893Sdim if (LHS->getValue() == RHS->getValue()) 669218893Sdim return 0; 670218893Sdim return -1; 671218893Sdim} 672218893Sdim 673193323Sed/// FoldValueComparisonIntoPredecessors - The specified terminator is a value 674193323Sed/// equality comparison instruction (either a switch or a branch on "X == c"). 675193323Sed/// See if any of the predecessors of the terminator block are value comparisons 676193323Sed/// on the same value. If so, and if safe to do so, fold them together. 677203954Srdivackybool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI) { 678193323Sed BasicBlock *BB = TI->getParent(); 679193323Sed Value *CV = isValueEqualityComparison(TI); // CondVal 680193323Sed assert(CV && "Not a comparison?"); 681193323Sed bool Changed = false; 682193323Sed 683193323Sed SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 684193323Sed while (!Preds.empty()) { 685193323Sed BasicBlock *Pred = Preds.pop_back_val(); 686193323Sed 687193323Sed // See if the predecessor is a comparison with the same value. 688193323Sed TerminatorInst *PTI = Pred->getTerminator(); 689193323Sed Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 690193323Sed 691193323Sed if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 692193323Sed // Figure out which 'cases' to copy from SI to PSI. 693193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > BBCases; 694193323Sed BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 695193323Sed 696193323Sed std::vector<std::pair<ConstantInt*, BasicBlock*> > PredCases; 697193323Sed BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 698193323Sed 699193323Sed // Based on whether the default edge from PTI goes to BB or not, fill in 700193323Sed // PredCases and PredDefault with the new switch cases we would like to 701193323Sed // build. 702193323Sed SmallVector<BasicBlock*, 8> NewSuccessors; 703193323Sed 704193323Sed if (PredDefault == BB) { 705193323Sed // If this is the default destination from PTI, only the edges in TI 706193323Sed // that don't occur in PTI, or that branch to BB will be activated. 707193323Sed std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 708193323Sed for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 709193323Sed if (PredCases[i].second != BB) 710193323Sed PTIHandled.insert(PredCases[i].first); 711193323Sed else { 712193323Sed // The default destination is BB, we don't need explicit targets. 713193323Sed std::swap(PredCases[i], PredCases.back()); 714193323Sed PredCases.pop_back(); 715193323Sed --i; --e; 716193323Sed } 717193323Sed 718193323Sed // Reconstruct the new switch statement we will be building. 719193323Sed if (PredDefault != BBDefault) { 720193323Sed PredDefault->removePredecessor(Pred); 721193323Sed PredDefault = BBDefault; 722193323Sed NewSuccessors.push_back(BBDefault); 723193323Sed } 724193323Sed for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 725193323Sed if (!PTIHandled.count(BBCases[i].first) && 726193323Sed BBCases[i].second != BBDefault) { 727193323Sed PredCases.push_back(BBCases[i]); 728193323Sed NewSuccessors.push_back(BBCases[i].second); 729193323Sed } 730193323Sed 731193323Sed } else { 732193323Sed // If this is not the default destination from PSI, only the edges 733193323Sed // in SI that occur in PSI with a destination of BB will be 734193323Sed // activated. 735193323Sed std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 736193323Sed for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 737193323Sed if (PredCases[i].second == BB) { 738193323Sed PTIHandled.insert(PredCases[i].first); 739193323Sed std::swap(PredCases[i], PredCases.back()); 740193323Sed PredCases.pop_back(); 741193323Sed --i; --e; 742193323Sed } 743193323Sed 744193323Sed // Okay, now we know which constants were sent to BB from the 745193323Sed // predecessor. Figure out where they will all go now. 746193323Sed for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 747193323Sed if (PTIHandled.count(BBCases[i].first)) { 748193323Sed // If this is one we are capable of getting... 749193323Sed PredCases.push_back(BBCases[i]); 750193323Sed NewSuccessors.push_back(BBCases[i].second); 751193323Sed PTIHandled.erase(BBCases[i].first);// This constant is taken care of 752193323Sed } 753193323Sed 754193323Sed // If there are any constants vectored to BB that TI doesn't handle, 755193323Sed // they must go to the default destination of TI. 756193323Sed for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I = 757193323Sed PTIHandled.begin(), 758193323Sed E = PTIHandled.end(); I != E; ++I) { 759193323Sed PredCases.push_back(std::make_pair(*I, BBDefault)); 760193323Sed NewSuccessors.push_back(BBDefault); 761193323Sed } 762193323Sed } 763193323Sed 764193323Sed // Okay, at this point, we know which new successor Pred will get. Make 765193323Sed // sure we update the number of entries in the PHI nodes for these 766193323Sed // successors. 767193323Sed for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 768193323Sed AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 769193323Sed 770203954Srdivacky // Convert pointer to int before we switch. 771204642Srdivacky if (CV->getType()->isPointerTy()) { 772203954Srdivacky assert(TD && "Cannot switch on pointer without TargetData"); 773203954Srdivacky CV = new PtrToIntInst(CV, TD->getIntPtrType(CV->getContext()), 774203954Srdivacky "magicptr", PTI); 775203954Srdivacky } 776203954Srdivacky 777193323Sed // Now that the successors are updated, create the new Switch instruction. 778193323Sed SwitchInst *NewSI = SwitchInst::Create(CV, PredDefault, 779193323Sed PredCases.size(), PTI); 780193323Sed for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 781193323Sed NewSI->addCase(PredCases[i].first, PredCases[i].second); 782193323Sed 783193323Sed EraseTerminatorInstAndDCECond(PTI); 784193323Sed 785193323Sed // Okay, last check. If BB is still a successor of PSI, then we must 786193323Sed // have an infinite loop case. If so, add an infinitely looping block 787193323Sed // to handle the case to preserve the behavior of the code. 788193323Sed BasicBlock *InfLoopBlock = 0; 789193323Sed for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 790193323Sed if (NewSI->getSuccessor(i) == BB) { 791193323Sed if (InfLoopBlock == 0) { 792193323Sed // Insert it at the end of the function, because it's either code, 793193323Sed // or it won't matter if it's hot. :) 794198090Srdivacky InfLoopBlock = BasicBlock::Create(BB->getContext(), 795198090Srdivacky "infloop", BB->getParent()); 796193323Sed BranchInst::Create(InfLoopBlock, InfLoopBlock); 797193323Sed } 798193323Sed NewSI->setSuccessor(i, InfLoopBlock); 799193323Sed } 800193323Sed 801193323Sed Changed = true; 802193323Sed } 803193323Sed } 804193323Sed return Changed; 805193323Sed} 806193323Sed 807194612Sed// isSafeToHoistInvoke - If we would need to insert a select that uses the 808194612Sed// value of this invoke (comments in HoistThenElseCodeToIf explain why we 809194612Sed// would need to do this), we can't hoist the invoke, as there is nowhere 810194612Sed// to put the select in this case. 811194612Sedstatic bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, 812194612Sed Instruction *I1, Instruction *I2) { 813194612Sed for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 814194612Sed PHINode *PN; 815194612Sed for (BasicBlock::iterator BBI = SI->begin(); 816194612Sed (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 817194612Sed Value *BB1V = PN->getIncomingValueForBlock(BB1); 818194612Sed Value *BB2V = PN->getIncomingValueForBlock(BB2); 819194612Sed if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) { 820194612Sed return false; 821194612Sed } 822194612Sed } 823194612Sed } 824194612Sed return true; 825194612Sed} 826194612Sed 827193323Sed/// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and 828193323Sed/// BB2, hoist any common code in the two blocks up into the branch block. The 829193323Sed/// caller of this function guarantees that BI's block dominates BB1 and BB2. 830193323Sedstatic bool HoistThenElseCodeToIf(BranchInst *BI) { 831193323Sed // This does very trivial matching, with limited scanning, to find identical 832193323Sed // instructions in the two blocks. In particular, we don't want to get into 833193323Sed // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 834193323Sed // such, we currently just scan for obviously identical instructions in an 835193323Sed // identical order. 836193323Sed BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 837193323Sed BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 838193323Sed 839193323Sed BasicBlock::iterator BB1_Itr = BB1->begin(); 840193323Sed BasicBlock::iterator BB2_Itr = BB2->begin(); 841193323Sed 842193323Sed Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++; 843221345Sdim // Skip debug info if it is not identical. 844221345Sdim DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1); 845221345Sdim DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2); 846221345Sdim if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { 847221345Sdim while (isa<DbgInfoIntrinsic>(I1)) 848221345Sdim I1 = BB1_Itr++; 849221345Sdim while (isa<DbgInfoIntrinsic>(I2)) 850221345Sdim I2 = BB2_Itr++; 851221345Sdim } 852221345Sdim if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) || 853194612Sed (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))) 854193323Sed return false; 855193323Sed 856193323Sed // If we get here, we can hoist at least one instruction. 857193323Sed BasicBlock *BIParent = BI->getParent(); 858193323Sed 859193323Sed do { 860193323Sed // If we are hoisting the terminator instruction, don't move one (making a 861193323Sed // broken BB), instead clone it, and remove BI. 862193323Sed if (isa<TerminatorInst>(I1)) 863193323Sed goto HoistTerminator; 864193323Sed 865193323Sed // For a normal instruction, we just move one to right before the branch, 866193323Sed // then replace all uses of the other with the first. Finally, we remove 867193323Sed // the now redundant second instruction. 868193323Sed BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 869193323Sed if (!I2->use_empty()) 870193323Sed I2->replaceAllUsesWith(I1); 871198090Srdivacky I1->intersectOptionalDataWith(I2); 872218893Sdim I2->eraseFromParent(); 873193323Sed 874193323Sed I1 = BB1_Itr++; 875193323Sed I2 = BB2_Itr++; 876221345Sdim // Skip debug info if it is not identical. 877221345Sdim DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1); 878221345Sdim DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2); 879221345Sdim if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { 880221345Sdim while (isa<DbgInfoIntrinsic>(I1)) 881221345Sdim I1 = BB1_Itr++; 882221345Sdim while (isa<DbgInfoIntrinsic>(I2)) 883221345Sdim I2 = BB2_Itr++; 884221345Sdim } 885221345Sdim } while (I1->isIdenticalToWhenDefined(I2)); 886193323Sed 887193323Sed return true; 888193323Sed 889193323SedHoistTerminator: 890194612Sed // It may not be possible to hoist an invoke. 891194612Sed if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) 892194612Sed return true; 893194612Sed 894193323Sed // Okay, it is safe to hoist the terminator. 895193323Sed Instruction *NT = I1->clone(); 896193323Sed BIParent->getInstList().insert(BI, NT); 897202375Srdivacky if (!NT->getType()->isVoidTy()) { 898193323Sed I1->replaceAllUsesWith(NT); 899193323Sed I2->replaceAllUsesWith(NT); 900193323Sed NT->takeName(I1); 901193323Sed } 902193323Sed 903193323Sed // Hoisting one of the terminators from our successor is a great thing. 904193323Sed // Unfortunately, the successors of the if/else blocks may have PHI nodes in 905193323Sed // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 906193323Sed // nodes, so we insert select instruction to compute the final result. 907193323Sed std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 908193323Sed for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 909193323Sed PHINode *PN; 910193323Sed for (BasicBlock::iterator BBI = SI->begin(); 911193323Sed (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 912193323Sed Value *BB1V = PN->getIncomingValueForBlock(BB1); 913193323Sed Value *BB2V = PN->getIncomingValueForBlock(BB2); 914218893Sdim if (BB1V == BB2V) continue; 915218893Sdim 916218893Sdim // These values do not agree. Insert a select instruction before NT 917218893Sdim // that determines the right value. 918218893Sdim SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 919218893Sdim if (SI == 0) 920218893Sdim SI = SelectInst::Create(BI->getCondition(), BB1V, BB2V, 921218893Sdim BB1V->getName()+"."+BB2V->getName(), NT); 922218893Sdim // Make the PHI node use the select for all incoming values for BB1/BB2 923218893Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 924218893Sdim if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 925218893Sdim PN->setIncomingValue(i, SI); 926193323Sed } 927193323Sed } 928193323Sed 929193323Sed // Update any PHI nodes in our new successors. 930193323Sed for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 931193323Sed AddPredecessorToBlock(*SI, BIParent, BB1); 932193323Sed 933193323Sed EraseTerminatorInstAndDCECond(BI); 934193323Sed return true; 935193323Sed} 936193323Sed 937193323Sed/// SpeculativelyExecuteBB - Given a conditional branch that goes to BB1 938193323Sed/// and an BB2 and the only successor of BB1 is BB2, hoist simple code 939193323Sed/// (for now, restricted to a single instruction that's side effect free) from 940193323Sed/// the BB1 into the branch block to speculatively execute it. 941193323Sedstatic bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *BB1) { 942193323Sed // Only speculatively execution a single instruction (not counting the 943193323Sed // terminator) for now. 944193323Sed Instruction *HInst = NULL; 945193323Sed Instruction *Term = BB1->getTerminator(); 946193323Sed for (BasicBlock::iterator BBI = BB1->begin(), BBE = BB1->end(); 947193323Sed BBI != BBE; ++BBI) { 948193323Sed Instruction *I = BBI; 949193323Sed // Skip debug info. 950218893Sdim if (isa<DbgInfoIntrinsic>(I)) continue; 951218893Sdim if (I == Term) break; 952193323Sed 953218893Sdim if (HInst) 954193323Sed return false; 955218893Sdim HInst = I; 956193323Sed } 957193323Sed if (!HInst) 958193323Sed return false; 959193323Sed 960193323Sed // Be conservative for now. FP select instruction can often be expensive. 961193323Sed Value *BrCond = BI->getCondition(); 962218893Sdim if (isa<FCmpInst>(BrCond)) 963193323Sed return false; 964193323Sed 965193323Sed // If BB1 is actually on the false edge of the conditional branch, remember 966193323Sed // to swap the select operands later. 967193323Sed bool Invert = false; 968193323Sed if (BB1 != BI->getSuccessor(0)) { 969193323Sed assert(BB1 == BI->getSuccessor(1) && "No edge from 'if' block?"); 970193323Sed Invert = true; 971193323Sed } 972193323Sed 973193323Sed // Turn 974193323Sed // BB: 975193323Sed // %t1 = icmp 976193323Sed // br i1 %t1, label %BB1, label %BB2 977193323Sed // BB1: 978193323Sed // %t3 = add %t2, c 979193323Sed // br label BB2 980193323Sed // BB2: 981193323Sed // => 982193323Sed // BB: 983193323Sed // %t1 = icmp 984193323Sed // %t4 = add %t2, c 985193323Sed // %t3 = select i1 %t1, %t2, %t3 986193323Sed switch (HInst->getOpcode()) { 987193323Sed default: return false; // Not safe / profitable to hoist. 988193323Sed case Instruction::Add: 989193323Sed case Instruction::Sub: 990193574Sed // Not worth doing for vector ops. 991204642Srdivacky if (HInst->getType()->isVectorTy()) 992193323Sed return false; 993193323Sed break; 994193323Sed case Instruction::And: 995193323Sed case Instruction::Or: 996193323Sed case Instruction::Xor: 997193323Sed case Instruction::Shl: 998193323Sed case Instruction::LShr: 999193323Sed case Instruction::AShr: 1000193323Sed // Don't mess with vector operations. 1001204642Srdivacky if (HInst->getType()->isVectorTy()) 1002193323Sed return false; 1003193323Sed break; // These are all cheap and non-trapping instructions. 1004193323Sed } 1005193323Sed 1006193323Sed // If the instruction is obviously dead, don't try to predicate it. 1007193323Sed if (HInst->use_empty()) { 1008193323Sed HInst->eraseFromParent(); 1009193323Sed return true; 1010193323Sed } 1011193323Sed 1012193323Sed // Can we speculatively execute the instruction? And what is the value 1013193323Sed // if the condition is false? Consider the phi uses, if the incoming value 1014193323Sed // from the "if" block are all the same V, then V is the value of the 1015193323Sed // select if the condition is false. 1016193323Sed BasicBlock *BIParent = BI->getParent(); 1017193323Sed SmallVector<PHINode*, 4> PHIUses; 1018193323Sed Value *FalseV = NULL; 1019193323Sed 1020193323Sed BasicBlock *BB2 = BB1->getTerminator()->getSuccessor(0); 1021193323Sed for (Value::use_iterator UI = HInst->use_begin(), E = HInst->use_end(); 1022193323Sed UI != E; ++UI) { 1023193323Sed // Ignore any user that is not a PHI node in BB2. These can only occur in 1024193323Sed // unreachable blocks, because they would not be dominated by the instr. 1025212904Sdim PHINode *PN = dyn_cast<PHINode>(*UI); 1026193323Sed if (!PN || PN->getParent() != BB2) 1027193323Sed return false; 1028193323Sed PHIUses.push_back(PN); 1029193323Sed 1030193323Sed Value *PHIV = PN->getIncomingValueForBlock(BIParent); 1031193323Sed if (!FalseV) 1032193323Sed FalseV = PHIV; 1033193323Sed else if (FalseV != PHIV) 1034193323Sed return false; // Inconsistent value when condition is false. 1035193323Sed } 1036193323Sed 1037193323Sed assert(FalseV && "Must have at least one user, and it must be a PHI"); 1038193323Sed 1039193323Sed // Do not hoist the instruction if any of its operands are defined but not 1040193323Sed // used in this BB. The transformation will prevent the operand from 1041193323Sed // being sunk into the use block. 1042193323Sed for (User::op_iterator i = HInst->op_begin(), e = HInst->op_end(); 1043193323Sed i != e; ++i) { 1044193323Sed Instruction *OpI = dyn_cast<Instruction>(*i); 1045193323Sed if (OpI && OpI->getParent() == BIParent && 1046193323Sed !OpI->isUsedInBasicBlock(BIParent)) 1047193323Sed return false; 1048193323Sed } 1049193323Sed 1050193323Sed // If we get here, we can hoist the instruction. Try to place it 1051193323Sed // before the icmp instruction preceding the conditional branch. 1052193323Sed BasicBlock::iterator InsertPos = BI; 1053193323Sed if (InsertPos != BIParent->begin()) 1054193323Sed --InsertPos; 1055193323Sed // Skip debug info between condition and branch. 1056193323Sed while (InsertPos != BIParent->begin() && isa<DbgInfoIntrinsic>(InsertPos)) 1057193323Sed --InsertPos; 1058193323Sed if (InsertPos == BrCond && !isa<PHINode>(BrCond)) { 1059193323Sed SmallPtrSet<Instruction *, 4> BB1Insns; 1060193323Sed for(BasicBlock::iterator BB1I = BB1->begin(), BB1E = BB1->end(); 1061193323Sed BB1I != BB1E; ++BB1I) 1062193323Sed BB1Insns.insert(BB1I); 1063193323Sed for(Value::use_iterator UI = BrCond->use_begin(), UE = BrCond->use_end(); 1064193323Sed UI != UE; ++UI) { 1065193323Sed Instruction *Use = cast<Instruction>(*UI); 1066218893Sdim if (!BB1Insns.count(Use)) continue; 1067218893Sdim 1068218893Sdim // If BrCond uses the instruction that place it just before 1069218893Sdim // branch instruction. 1070218893Sdim InsertPos = BI; 1071218893Sdim break; 1072193323Sed } 1073193323Sed } else 1074193323Sed InsertPos = BI; 1075193323Sed BIParent->getInstList().splice(InsertPos, BB1->getInstList(), HInst); 1076193323Sed 1077193323Sed // Create a select whose true value is the speculatively executed value and 1078193323Sed // false value is the previously determined FalseV. 1079193323Sed SelectInst *SI; 1080193323Sed if (Invert) 1081193323Sed SI = SelectInst::Create(BrCond, FalseV, HInst, 1082193323Sed FalseV->getName() + "." + HInst->getName(), BI); 1083193323Sed else 1084193323Sed SI = SelectInst::Create(BrCond, HInst, FalseV, 1085193323Sed HInst->getName() + "." + FalseV->getName(), BI); 1086193323Sed 1087193323Sed // Make the PHI node use the select for all incoming values for "then" and 1088193323Sed // "if" blocks. 1089193323Sed for (unsigned i = 0, e = PHIUses.size(); i != e; ++i) { 1090193323Sed PHINode *PN = PHIUses[i]; 1091193323Sed for (unsigned j = 0, ee = PN->getNumIncomingValues(); j != ee; ++j) 1092218893Sdim if (PN->getIncomingBlock(j) == BB1 || PN->getIncomingBlock(j) == BIParent) 1093193323Sed PN->setIncomingValue(j, SI); 1094193323Sed } 1095193323Sed 1096193323Sed ++NumSpeculations; 1097193323Sed return true; 1098193323Sed} 1099193323Sed 1100193323Sed/// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch 1101193323Sed/// across this block. 1102193323Sedstatic bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { 1103193323Sed BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 1104193323Sed unsigned Size = 0; 1105193323Sed 1106193323Sed for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1107193323Sed if (isa<DbgInfoIntrinsic>(BBI)) 1108193323Sed continue; 1109193323Sed if (Size > 10) return false; // Don't clone large BB's. 1110193323Sed ++Size; 1111193323Sed 1112193323Sed // We can only support instructions that do not define values that are 1113193323Sed // live outside of the current basic block. 1114193323Sed for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 1115193323Sed UI != E; ++UI) { 1116193323Sed Instruction *U = cast<Instruction>(*UI); 1117193323Sed if (U->getParent() != BB || isa<PHINode>(U)) return false; 1118193323Sed } 1119193323Sed 1120193323Sed // Looks ok, continue checking. 1121193323Sed } 1122193323Sed 1123193323Sed return true; 1124193323Sed} 1125193323Sed 1126193323Sed/// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value 1127193323Sed/// that is defined in the same block as the branch and if any PHI entries are 1128193323Sed/// constants, thread edges corresponding to that entry to be branches to their 1129193323Sed/// ultimate destination. 1130218893Sdimstatic bool FoldCondBranchOnPHI(BranchInst *BI, const TargetData *TD) { 1131193323Sed BasicBlock *BB = BI->getParent(); 1132193323Sed PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 1133193323Sed // NOTE: we currently cannot transform this case if the PHI node is used 1134193323Sed // outside of the block. 1135193323Sed if (!PN || PN->getParent() != BB || !PN->hasOneUse()) 1136193323Sed return false; 1137193323Sed 1138193323Sed // Degenerate case of a single entry PHI. 1139193323Sed if (PN->getNumIncomingValues() == 1) { 1140193323Sed FoldSingleEntryPHINodes(PN->getParent()); 1141193323Sed return true; 1142193323Sed } 1143193323Sed 1144193323Sed // Now we know that this block has multiple preds and two succs. 1145193323Sed if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; 1146193323Sed 1147193323Sed // Okay, this is a simple enough basic block. See if any phi values are 1148193323Sed // constants. 1149193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1150218893Sdim ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i)); 1151218893Sdim if (CB == 0 || !CB->getType()->isIntegerTy(1)) continue; 1152218893Sdim 1153218893Sdim // Okay, we now know that all edges from PredBB should be revectored to 1154218893Sdim // branch to RealDest. 1155218893Sdim BasicBlock *PredBB = PN->getIncomingBlock(i); 1156218893Sdim BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); 1157218893Sdim 1158218893Sdim if (RealDest == BB) continue; // Skip self loops. 1159218893Sdim 1160218893Sdim // The dest block might have PHI nodes, other predecessors and other 1161218893Sdim // difficult cases. Instead of being smart about this, just insert a new 1162218893Sdim // block that jumps to the destination block, effectively splitting 1163218893Sdim // the edge we are about to create. 1164218893Sdim BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(), 1165218893Sdim RealDest->getName()+".critedge", 1166218893Sdim RealDest->getParent(), RealDest); 1167218893Sdim BranchInst::Create(RealDest, EdgeBB); 1168218893Sdim 1169218893Sdim // Update PHI nodes. 1170218893Sdim AddPredecessorToBlock(RealDest, EdgeBB, BB); 1171218893Sdim 1172218893Sdim // BB may have instructions that are being threaded over. Clone these 1173218893Sdim // instructions into EdgeBB. We know that there will be no uses of the 1174218893Sdim // cloned instructions outside of EdgeBB. 1175218893Sdim BasicBlock::iterator InsertPt = EdgeBB->begin(); 1176218893Sdim DenseMap<Value*, Value*> TranslateMap; // Track translated values. 1177218893Sdim for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1178218893Sdim if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 1179218893Sdim TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); 1180218893Sdim continue; 1181218893Sdim } 1182218893Sdim // Clone the instruction. 1183218893Sdim Instruction *N = BBI->clone(); 1184218893Sdim if (BBI->hasName()) N->setName(BBI->getName()+".c"); 1185193323Sed 1186218893Sdim // Update operands due to translation. 1187218893Sdim for (User::op_iterator i = N->op_begin(), e = N->op_end(); 1188218893Sdim i != e; ++i) { 1189218893Sdim DenseMap<Value*, Value*>::iterator PI = TranslateMap.find(*i); 1190218893Sdim if (PI != TranslateMap.end()) 1191218893Sdim *i = PI->second; 1192218893Sdim } 1193193323Sed 1194218893Sdim // Check for trivial simplification. 1195218893Sdim if (Value *V = SimplifyInstruction(N, TD)) { 1196218893Sdim TranslateMap[BBI] = V; 1197218893Sdim delete N; // Instruction folded away, don't need actual inst 1198218893Sdim } else { 1199218893Sdim // Insert the new instruction into its new home. 1200218893Sdim EdgeBB->getInstList().insert(InsertPt, N); 1201218893Sdim if (!BBI->use_empty()) 1202218893Sdim TranslateMap[BBI] = N; 1203193323Sed } 1204218893Sdim } 1205193323Sed 1206218893Sdim // Loop over all of the edges from PredBB to BB, changing them to branch 1207218893Sdim // to EdgeBB instead. 1208218893Sdim TerminatorInst *PredBBTI = PredBB->getTerminator(); 1209218893Sdim for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 1210218893Sdim if (PredBBTI->getSuccessor(i) == BB) { 1211218893Sdim BB->removePredecessor(PredBB); 1212218893Sdim PredBBTI->setSuccessor(i, EdgeBB); 1213193323Sed } 1214218893Sdim 1215218893Sdim // Recurse, simplifying any other constants. 1216218893Sdim return FoldCondBranchOnPHI(BI, TD) | true; 1217193323Sed } 1218193323Sed 1219193323Sed return false; 1220193323Sed} 1221193323Sed 1222193323Sed/// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry 1223193323Sed/// PHI node, see if we can eliminate it. 1224218893Sdimstatic bool FoldTwoEntryPHINode(PHINode *PN, const TargetData *TD) { 1225193323Sed // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1226193323Sed // statement", which has a very simple dominance structure. Basically, we 1227193323Sed // are trying to find the condition that is being branched on, which 1228193323Sed // subsequently causes this merge to happen. We really want control 1229193323Sed // dependence information for this check, but simplifycfg can't keep it up 1230193323Sed // to date, and this catches most of the cases we care about anyway. 1231193323Sed BasicBlock *BB = PN->getParent(); 1232193323Sed BasicBlock *IfTrue, *IfFalse; 1233193323Sed Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); 1234218893Sdim if (!IfCond || 1235218893Sdim // Don't bother if the branch will be constant folded trivially. 1236218893Sdim isa<ConstantInt>(IfCond)) 1237218893Sdim return false; 1238193323Sed 1239193323Sed // Okay, we found that we can merge this two-entry phi node into a select. 1240193323Sed // Doing so would require us to fold *all* two entry phi nodes in this block. 1241193323Sed // At some point this becomes non-profitable (particularly if the target 1242193323Sed // doesn't support cmov's). Only do this transformation if there are two or 1243193323Sed // fewer PHI nodes in this block. 1244193323Sed unsigned NumPhis = 0; 1245193323Sed for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I) 1246193323Sed if (NumPhis > 2) 1247193323Sed return false; 1248193323Sed 1249193323Sed // Loop over the PHI's seeing if we can promote them all to select 1250193323Sed // instructions. While we are at it, keep track of the instructions 1251193323Sed // that need to be moved to the dominating block. 1252218893Sdim SmallPtrSet<Instruction*, 4> AggressiveInsts; 1253221345Sdim unsigned MaxCostVal0 = PHINodeFoldingThreshold, 1254221345Sdim MaxCostVal1 = PHINodeFoldingThreshold; 1255193323Sed 1256218893Sdim for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) { 1257218893Sdim PHINode *PN = cast<PHINode>(II++); 1258218893Sdim if (Value *V = SimplifyInstruction(PN, TD)) { 1259218893Sdim PN->replaceAllUsesWith(V); 1260218893Sdim PN->eraseFromParent(); 1261218893Sdim continue; 1262218893Sdim } 1263218893Sdim 1264221345Sdim if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts, 1265221345Sdim MaxCostVal0) || 1266221345Sdim !DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts, 1267221345Sdim MaxCostVal1)) 1268193323Sed return false; 1269193323Sed } 1270193323Sed 1271218893Sdim // If we folded the the first phi, PN dangles at this point. Refresh it. If 1272218893Sdim // we ran out of PHIs then we simplified them all. 1273218893Sdim PN = dyn_cast<PHINode>(BB->begin()); 1274218893Sdim if (PN == 0) return true; 1275218893Sdim 1276218893Sdim // Don't fold i1 branches on PHIs which contain binary operators. These can 1277218893Sdim // often be turned into switches and other things. 1278218893Sdim if (PN->getType()->isIntegerTy(1) && 1279218893Sdim (isa<BinaryOperator>(PN->getIncomingValue(0)) || 1280218893Sdim isa<BinaryOperator>(PN->getIncomingValue(1)) || 1281218893Sdim isa<BinaryOperator>(IfCond))) 1282218893Sdim return false; 1283218893Sdim 1284193323Sed // If we all PHI nodes are promotable, check to make sure that all 1285193323Sed // instructions in the predecessor blocks can be promoted as well. If 1286193323Sed // not, we won't be able to get rid of the control flow, so it's not 1287193323Sed // worth promoting to select instructions. 1288218893Sdim BasicBlock *DomBlock = 0; 1289218893Sdim BasicBlock *IfBlock1 = PN->getIncomingBlock(0); 1290218893Sdim BasicBlock *IfBlock2 = PN->getIncomingBlock(1); 1291218893Sdim if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) { 1292218893Sdim IfBlock1 = 0; 1293218893Sdim } else { 1294218893Sdim DomBlock = *pred_begin(IfBlock1); 1295218893Sdim for (BasicBlock::iterator I = IfBlock1->begin();!isa<TerminatorInst>(I);++I) 1296193323Sed if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1297193323Sed // This is not an aggressive instruction that we can promote. 1298193323Sed // Because of this, we won't be able to get rid of the control 1299193323Sed // flow, so the xform is not worth it. 1300193323Sed return false; 1301193323Sed } 1302193323Sed } 1303193323Sed 1304218893Sdim if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) { 1305218893Sdim IfBlock2 = 0; 1306218893Sdim } else { 1307218893Sdim DomBlock = *pred_begin(IfBlock2); 1308218893Sdim for (BasicBlock::iterator I = IfBlock2->begin();!isa<TerminatorInst>(I);++I) 1309193323Sed if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1310193323Sed // This is not an aggressive instruction that we can promote. 1311193323Sed // Because of this, we won't be able to get rid of the control 1312193323Sed // flow, so the xform is not worth it. 1313193323Sed return false; 1314193323Sed } 1315193323Sed } 1316218893Sdim 1317218893Sdim DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond << " T: " 1318218893Sdim << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1319193323Sed 1320193323Sed // If we can still promote the PHI nodes after this gauntlet of tests, 1321193323Sed // do all of the PHI's now. 1322218893Sdim Instruction *InsertPt = DomBlock->getTerminator(); 1323218893Sdim 1324193323Sed // Move all 'aggressive' instructions, which are defined in the 1325193323Sed // conditional parts of the if's up to the dominating block. 1326218893Sdim if (IfBlock1) 1327218893Sdim DomBlock->getInstList().splice(InsertPt, 1328218893Sdim IfBlock1->getInstList(), IfBlock1->begin(), 1329193323Sed IfBlock1->getTerminator()); 1330218893Sdim if (IfBlock2) 1331218893Sdim DomBlock->getInstList().splice(InsertPt, 1332218893Sdim IfBlock2->getInstList(), IfBlock2->begin(), 1333193323Sed IfBlock2->getTerminator()); 1334193323Sed 1335193323Sed while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 1336193323Sed // Change the PHI node into a select instruction. 1337218893Sdim Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1338218893Sdim Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1339193323Sed 1340218893Sdim Value *NV = SelectInst::Create(IfCond, TrueVal, FalseVal, "", InsertPt); 1341193323Sed PN->replaceAllUsesWith(NV); 1342193323Sed NV->takeName(PN); 1343218893Sdim PN->eraseFromParent(); 1344193323Sed } 1345218893Sdim 1346218893Sdim // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement 1347218893Sdim // has been flattened. Change DomBlock to jump directly to our new block to 1348218893Sdim // avoid other simplifycfg's kicking in on the diamond. 1349218893Sdim TerminatorInst *OldTI = DomBlock->getTerminator(); 1350218893Sdim BranchInst::Create(BB, OldTI); 1351218893Sdim OldTI->eraseFromParent(); 1352193323Sed return true; 1353193323Sed} 1354193323Sed 1355193323Sed/// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes 1356193323Sed/// to two returning blocks, try to merge them together into one return, 1357193323Sed/// introducing a select if the return values disagree. 1358193323Sedstatic bool SimplifyCondBranchToTwoReturns(BranchInst *BI) { 1359193323Sed assert(BI->isConditional() && "Must be a conditional branch"); 1360193323Sed BasicBlock *TrueSucc = BI->getSuccessor(0); 1361193323Sed BasicBlock *FalseSucc = BI->getSuccessor(1); 1362193323Sed ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator()); 1363193323Sed ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator()); 1364193323Sed 1365193323Sed // Check to ensure both blocks are empty (just a return) or optionally empty 1366193323Sed // with PHI nodes. If there are other instructions, merging would cause extra 1367193323Sed // computation on one path or the other. 1368218893Sdim if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator()) 1369193323Sed return false; 1370218893Sdim if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator()) 1371193323Sed return false; 1372193323Sed 1373193323Sed // Okay, we found a branch that is going to two return nodes. If 1374193323Sed // there is no return value for this function, just change the 1375193323Sed // branch into a return. 1376193323Sed if (FalseRet->getNumOperands() == 0) { 1377193323Sed TrueSucc->removePredecessor(BI->getParent()); 1378193323Sed FalseSucc->removePredecessor(BI->getParent()); 1379198090Srdivacky ReturnInst::Create(BI->getContext(), 0, BI); 1380193323Sed EraseTerminatorInstAndDCECond(BI); 1381193323Sed return true; 1382193323Sed } 1383193323Sed 1384193323Sed // Otherwise, figure out what the true and false return values are 1385193323Sed // so we can insert a new select instruction. 1386193323Sed Value *TrueValue = TrueRet->getReturnValue(); 1387193323Sed Value *FalseValue = FalseRet->getReturnValue(); 1388193323Sed 1389193323Sed // Unwrap any PHI nodes in the return blocks. 1390193323Sed if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue)) 1391193323Sed if (TVPN->getParent() == TrueSucc) 1392193323Sed TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1393193323Sed if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue)) 1394193323Sed if (FVPN->getParent() == FalseSucc) 1395193323Sed FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1396193323Sed 1397193323Sed // In order for this transformation to be safe, we must be able to 1398193323Sed // unconditionally execute both operands to the return. This is 1399193323Sed // normally the case, but we could have a potentially-trapping 1400193323Sed // constant expression that prevents this transformation from being 1401193323Sed // safe. 1402193323Sed if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue)) 1403193323Sed if (TCV->canTrap()) 1404193323Sed return false; 1405193323Sed if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue)) 1406193323Sed if (FCV->canTrap()) 1407193323Sed return false; 1408193323Sed 1409193323Sed // Okay, we collected all the mapped values and checked them for sanity, and 1410193323Sed // defined to really do this transformation. First, update the CFG. 1411193323Sed TrueSucc->removePredecessor(BI->getParent()); 1412193323Sed FalseSucc->removePredecessor(BI->getParent()); 1413193323Sed 1414193323Sed // Insert select instructions where needed. 1415193323Sed Value *BrCond = BI->getCondition(); 1416193323Sed if (TrueValue) { 1417193323Sed // Insert a select if the results differ. 1418193323Sed if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) { 1419193323Sed } else if (isa<UndefValue>(TrueValue)) { 1420193323Sed TrueValue = FalseValue; 1421193323Sed } else { 1422193323Sed TrueValue = SelectInst::Create(BrCond, TrueValue, 1423193323Sed FalseValue, "retval", BI); 1424193323Sed } 1425193323Sed } 1426193323Sed 1427193323Sed Value *RI = !TrueValue ? 1428198090Srdivacky ReturnInst::Create(BI->getContext(), BI) : 1429198090Srdivacky ReturnInst::Create(BI->getContext(), TrueValue, BI); 1430198090Srdivacky (void) RI; 1431193323Sed 1432202375Srdivacky DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" 1433198090Srdivacky << "\n " << *BI << "NewRet = " << *RI 1434198090Srdivacky << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc); 1435193323Sed 1436193323Sed EraseTerminatorInstAndDCECond(BI); 1437193323Sed 1438193323Sed return true; 1439193323Sed} 1440193323Sed 1441221345Sdim/// FoldBranchToCommonDest - If this basic block is simple enough, and if a 1442221345Sdim/// predecessor branches to us and one of our successors, fold the block into 1443221345Sdim/// the predecessor and use logical operations to pick the right destination. 1444195340Sedbool llvm::FoldBranchToCommonDest(BranchInst *BI) { 1445193323Sed BasicBlock *BB = BI->getParent(); 1446193323Sed Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); 1447210299Sed if (Cond == 0 || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) || 1448210299Sed Cond->getParent() != BB || !Cond->hasOneUse()) 1449210299Sed return false; 1450221345Sdim 1451193323Sed // Only allow this if the condition is a simple instruction that can be 1452193323Sed // executed unconditionally. It must be in the same block as the branch, and 1453193323Sed // must be at the front of the block. 1454193323Sed BasicBlock::iterator FrontIt = BB->front(); 1455221345Sdim 1456193323Sed // Ignore dbg intrinsics. 1457221345Sdim while (isa<DbgInfoIntrinsic>(FrontIt)) ++FrontIt; 1458210299Sed 1459210299Sed // Allow a single instruction to be hoisted in addition to the compare 1460210299Sed // that feeds the branch. We later ensure that any values that _it_ uses 1461210299Sed // were also live in the predecessor, so that we don't unnecessarily create 1462210299Sed // register pressure or inhibit out-of-order execution. 1463210299Sed Instruction *BonusInst = 0; 1464210299Sed if (&*FrontIt != Cond && 1465210299Sed FrontIt->hasOneUse() && *FrontIt->use_begin() == Cond && 1466210299Sed FrontIt->isSafeToSpeculativelyExecute()) { 1467210299Sed BonusInst = &*FrontIt; 1468210299Sed ++FrontIt; 1469221345Sdim 1470221345Sdim // Ignore dbg intrinsics. 1471221345Sdim while (isa<DbgInfoIntrinsic>(FrontIt)) ++FrontIt; 1472193323Sed } 1473221345Sdim 1474210299Sed // Only a single bonus inst is allowed. 1475210299Sed if (&*FrontIt != Cond) 1476210299Sed return false; 1477210299Sed 1478193323Sed // Make sure the instruction after the condition is the cond branch. 1479193323Sed BasicBlock::iterator CondIt = Cond; ++CondIt; 1480221345Sdim 1481193323Sed // Ingore dbg intrinsics. 1482221345Sdim while (isa<DbgInfoIntrinsic>(CondIt)) ++CondIt; 1483221345Sdim 1484221345Sdim if (&*CondIt != BI) 1485193323Sed return false; 1486193323Sed 1487193323Sed // Cond is known to be a compare or binary operator. Check to make sure that 1488193323Sed // neither operand is a potentially-trapping constant expression. 1489193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0))) 1490193323Sed if (CE->canTrap()) 1491193323Sed return false; 1492193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1))) 1493193323Sed if (CE->canTrap()) 1494193323Sed return false; 1495193323Sed 1496193323Sed // Finally, don't infinitely unroll conditional loops. 1497193323Sed BasicBlock *TrueDest = BI->getSuccessor(0); 1498193323Sed BasicBlock *FalseDest = BI->getSuccessor(1); 1499193323Sed if (TrueDest == BB || FalseDest == BB) 1500193323Sed return false; 1501221345Sdim 1502193323Sed for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 1503193323Sed BasicBlock *PredBlock = *PI; 1504193323Sed BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator()); 1505193323Sed 1506193323Sed // Check that we have two conditional branches. If there is a PHI node in 1507193323Sed // the common successor, verify that the same value flows in from both 1508193323Sed // blocks. 1509221345Sdim if (PBI == 0 || PBI->isUnconditional() || !SafeToMergeTerminators(BI, PBI)) 1510193323Sed continue; 1511193323Sed 1512221345Sdim // Determine if the two branches share a common destination. 1513221345Sdim Instruction::BinaryOps Opc; 1514221345Sdim bool InvertPredCond = false; 1515221345Sdim 1516221345Sdim if (PBI->getSuccessor(0) == TrueDest) 1517221345Sdim Opc = Instruction::Or; 1518221345Sdim else if (PBI->getSuccessor(1) == FalseDest) 1519221345Sdim Opc = Instruction::And; 1520221345Sdim else if (PBI->getSuccessor(0) == FalseDest) 1521221345Sdim Opc = Instruction::And, InvertPredCond = true; 1522221345Sdim else if (PBI->getSuccessor(1) == TrueDest) 1523221345Sdim Opc = Instruction::Or, InvertPredCond = true; 1524221345Sdim else 1525221345Sdim continue; 1526221345Sdim 1527210299Sed // Ensure that any values used in the bonus instruction are also used 1528210299Sed // by the terminator of the predecessor. This means that those values 1529210299Sed // must already have been resolved, so we won't be inhibiting the 1530210299Sed // out-of-order core by speculating them earlier. 1531210299Sed if (BonusInst) { 1532210299Sed // Collect the values used by the bonus inst 1533210299Sed SmallPtrSet<Value*, 4> UsedValues; 1534210299Sed for (Instruction::op_iterator OI = BonusInst->op_begin(), 1535210299Sed OE = BonusInst->op_end(); OI != OE; ++OI) { 1536210299Sed Value* V = *OI; 1537210299Sed if (!isa<Constant>(V)) 1538210299Sed UsedValues.insert(V); 1539210299Sed } 1540210299Sed 1541210299Sed SmallVector<std::pair<Value*, unsigned>, 4> Worklist; 1542210299Sed Worklist.push_back(std::make_pair(PBI->getOperand(0), 0)); 1543210299Sed 1544210299Sed // Walk up to four levels back up the use-def chain of the predecessor's 1545210299Sed // terminator to see if all those values were used. The choice of four 1546210299Sed // levels is arbitrary, to provide a compile-time-cost bound. 1547210299Sed while (!Worklist.empty()) { 1548210299Sed std::pair<Value*, unsigned> Pair = Worklist.back(); 1549210299Sed Worklist.pop_back(); 1550210299Sed 1551210299Sed if (Pair.second >= 4) continue; 1552210299Sed UsedValues.erase(Pair.first); 1553210299Sed if (UsedValues.empty()) break; 1554210299Sed 1555218893Sdim if (Instruction *I = dyn_cast<Instruction>(Pair.first)) { 1556210299Sed for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); 1557210299Sed OI != OE; ++OI) 1558210299Sed Worklist.push_back(std::make_pair(OI->get(), Pair.second+1)); 1559210299Sed } 1560210299Sed } 1561210299Sed 1562210299Sed if (!UsedValues.empty()) return false; 1563210299Sed } 1564193323Sed 1565202375Srdivacky DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB); 1566193323Sed 1567193323Sed // If we need to invert the condition in the pred block to match, do so now. 1568193323Sed if (InvertPredCond) { 1569218893Sdim Value *NewCond = PBI->getCondition(); 1570218893Sdim 1571218893Sdim if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) { 1572218893Sdim CmpInst *CI = cast<CmpInst>(NewCond); 1573218893Sdim CI->setPredicate(CI->getInversePredicate()); 1574218893Sdim } else { 1575218893Sdim NewCond = BinaryOperator::CreateNot(NewCond, 1576193323Sed PBI->getCondition()->getName()+".not", PBI); 1577218893Sdim } 1578218893Sdim 1579193323Sed PBI->setCondition(NewCond); 1580193323Sed BasicBlock *OldTrue = PBI->getSuccessor(0); 1581193323Sed BasicBlock *OldFalse = PBI->getSuccessor(1); 1582193323Sed PBI->setSuccessor(0, OldFalse); 1583193323Sed PBI->setSuccessor(1, OldTrue); 1584193323Sed } 1585193323Sed 1586210299Sed // If we have a bonus inst, clone it into the predecessor block. 1587210299Sed Instruction *NewBonus = 0; 1588210299Sed if (BonusInst) { 1589210299Sed NewBonus = BonusInst->clone(); 1590210299Sed PredBlock->getInstList().insert(PBI, NewBonus); 1591210299Sed NewBonus->takeName(BonusInst); 1592210299Sed BonusInst->setName(BonusInst->getName()+".old"); 1593210299Sed } 1594210299Sed 1595193323Sed // Clone Cond into the predecessor basic block, and or/and the 1596193323Sed // two conditions together. 1597193323Sed Instruction *New = Cond->clone(); 1598210299Sed if (BonusInst) New->replaceUsesOfWith(BonusInst, NewBonus); 1599193323Sed PredBlock->getInstList().insert(PBI, New); 1600193323Sed New->takeName(Cond); 1601193323Sed Cond->setName(New->getName()+".old"); 1602193323Sed 1603193323Sed Value *NewCond = BinaryOperator::Create(Opc, PBI->getCondition(), 1604193323Sed New, "or.cond", PBI); 1605193323Sed PBI->setCondition(NewCond); 1606193323Sed if (PBI->getSuccessor(0) == BB) { 1607193323Sed AddPredecessorToBlock(TrueDest, PredBlock, BB); 1608193323Sed PBI->setSuccessor(0, TrueDest); 1609193323Sed } 1610193323Sed if (PBI->getSuccessor(1) == BB) { 1611193323Sed AddPredecessorToBlock(FalseDest, PredBlock, BB); 1612193323Sed PBI->setSuccessor(1, FalseDest); 1613193323Sed } 1614221345Sdim 1615221345Sdim // Copy any debug value intrinsics into the end of PredBlock. 1616221345Sdim for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 1617221345Sdim if (isa<DbgInfoIntrinsic>(*I)) 1618221345Sdim I->clone()->insertBefore(PBI); 1619221345Sdim 1620193323Sed return true; 1621193323Sed } 1622193323Sed return false; 1623193323Sed} 1624193323Sed 1625193323Sed/// SimplifyCondBranchToCondBranch - If we have a conditional branch as a 1626193323Sed/// predecessor of another block, this function tries to simplify it. We know 1627193323Sed/// that PBI and BI are both conditional branches, and BI is in one of the 1628193323Sed/// successor blocks of PBI - PBI branches to BI. 1629193323Sedstatic bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { 1630193323Sed assert(PBI->isConditional() && BI->isConditional()); 1631193323Sed BasicBlock *BB = BI->getParent(); 1632198090Srdivacky 1633193323Sed // If this block ends with a branch instruction, and if there is a 1634193323Sed // predecessor that ends on a branch of the same condition, make 1635193323Sed // this conditional branch redundant. 1636193323Sed if (PBI->getCondition() == BI->getCondition() && 1637193323Sed PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 1638193323Sed // Okay, the outcome of this conditional branch is statically 1639193323Sed // knowable. If this block had a single pred, handle specially. 1640193323Sed if (BB->getSinglePredecessor()) { 1641193323Sed // Turn this into a branch on constant. 1642193323Sed bool CondIsTrue = PBI->getSuccessor(0) == BB; 1643198090Srdivacky BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 1644198090Srdivacky CondIsTrue)); 1645193323Sed return true; // Nuke the branch on constant. 1646193323Sed } 1647193323Sed 1648193323Sed // Otherwise, if there are multiple predecessors, insert a PHI that merges 1649193323Sed // in the constant and simplify the block result. Subsequent passes of 1650193323Sed // simplifycfg will thread the block. 1651193323Sed if (BlockIsSimpleEnoughToThreadThrough(BB)) { 1652221345Sdim pred_iterator PB = pred_begin(BB), PE = pred_end(BB); 1653198090Srdivacky PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()), 1654221345Sdim std::distance(PB, PE), 1655193323Sed BI->getCondition()->getName() + ".pr", 1656193323Sed BB->begin()); 1657193323Sed // Okay, we're going to insert the PHI node. Since PBI is not the only 1658193323Sed // predecessor, compute the PHI'd conditional value for all of the preds. 1659193323Sed // Any predecessor where the condition is not computable we keep symbolic. 1660221345Sdim for (pred_iterator PI = PB; PI != PE; ++PI) { 1661210299Sed BasicBlock *P = *PI; 1662210299Sed if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) && 1663193323Sed PBI != BI && PBI->isConditional() && 1664193323Sed PBI->getCondition() == BI->getCondition() && 1665193323Sed PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 1666193323Sed bool CondIsTrue = PBI->getSuccessor(0) == BB; 1667198090Srdivacky NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 1668210299Sed CondIsTrue), P); 1669193323Sed } else { 1670210299Sed NewPN->addIncoming(BI->getCondition(), P); 1671193323Sed } 1672210299Sed } 1673193323Sed 1674193323Sed BI->setCondition(NewPN); 1675193323Sed return true; 1676193323Sed } 1677193323Sed } 1678193323Sed 1679193323Sed // If this is a conditional branch in an empty block, and if any 1680193323Sed // predecessors is a conditional branch to one of our destinations, 1681193323Sed // fold the conditions into logical ops and one cond br. 1682193323Sed BasicBlock::iterator BBI = BB->begin(); 1683193323Sed // Ignore dbg intrinsics. 1684193323Sed while (isa<DbgInfoIntrinsic>(BBI)) 1685193323Sed ++BBI; 1686193323Sed if (&*BBI != BI) 1687193323Sed return false; 1688193323Sed 1689193323Sed 1690193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BI->getCondition())) 1691193323Sed if (CE->canTrap()) 1692193323Sed return false; 1693193323Sed 1694193323Sed int PBIOp, BIOp; 1695193323Sed if (PBI->getSuccessor(0) == BI->getSuccessor(0)) 1696193323Sed PBIOp = BIOp = 0; 1697193323Sed else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) 1698193323Sed PBIOp = 0, BIOp = 1; 1699193323Sed else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) 1700193323Sed PBIOp = 1, BIOp = 0; 1701193323Sed else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) 1702193323Sed PBIOp = BIOp = 1; 1703193323Sed else 1704193323Sed return false; 1705193323Sed 1706193323Sed // Check to make sure that the other destination of this branch 1707193323Sed // isn't BB itself. If so, this is an infinite loop that will 1708193323Sed // keep getting unwound. 1709193323Sed if (PBI->getSuccessor(PBIOp) == BB) 1710193323Sed return false; 1711193323Sed 1712193323Sed // Do not perform this transformation if it would require 1713193323Sed // insertion of a large number of select instructions. For targets 1714193323Sed // without predication/cmovs, this is a big pessimization. 1715193323Sed BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 1716193323Sed 1717193323Sed unsigned NumPhis = 0; 1718193323Sed for (BasicBlock::iterator II = CommonDest->begin(); 1719193323Sed isa<PHINode>(II); ++II, ++NumPhis) 1720193323Sed if (NumPhis > 2) // Disable this xform. 1721193323Sed return false; 1722193323Sed 1723193323Sed // Finally, if everything is ok, fold the branches to logical ops. 1724193323Sed BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); 1725193323Sed 1726202375Srdivacky DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent() 1727198090Srdivacky << "AND: " << *BI->getParent()); 1728193323Sed 1729193323Sed 1730193323Sed // If OtherDest *is* BB, then BB is a basic block with a single conditional 1731193323Sed // branch in it, where one edge (OtherDest) goes back to itself but the other 1732193323Sed // exits. We don't *know* that the program avoids the infinite loop 1733193323Sed // (even though that seems likely). If we do this xform naively, we'll end up 1734193323Sed // recursively unpeeling the loop. Since we know that (after the xform is 1735193323Sed // done) that the block *is* infinite if reached, we just make it an obviously 1736193323Sed // infinite loop with no cond branch. 1737193323Sed if (OtherDest == BB) { 1738193323Sed // Insert it at the end of the function, because it's either code, 1739193323Sed // or it won't matter if it's hot. :) 1740198090Srdivacky BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(), 1741198090Srdivacky "infloop", BB->getParent()); 1742193323Sed BranchInst::Create(InfLoopBlock, InfLoopBlock); 1743193323Sed OtherDest = InfLoopBlock; 1744193323Sed } 1745193323Sed 1746202375Srdivacky DEBUG(dbgs() << *PBI->getParent()->getParent()); 1747193323Sed 1748193323Sed // BI may have other predecessors. Because of this, we leave 1749193323Sed // it alone, but modify PBI. 1750193323Sed 1751193323Sed // Make sure we get to CommonDest on True&True directions. 1752193323Sed Value *PBICond = PBI->getCondition(); 1753193323Sed if (PBIOp) 1754193323Sed PBICond = BinaryOperator::CreateNot(PBICond, 1755193323Sed PBICond->getName()+".not", 1756193323Sed PBI); 1757193323Sed Value *BICond = BI->getCondition(); 1758193323Sed if (BIOp) 1759193323Sed BICond = BinaryOperator::CreateNot(BICond, 1760193323Sed BICond->getName()+".not", 1761193323Sed PBI); 1762193323Sed // Merge the conditions. 1763193323Sed Value *Cond = BinaryOperator::CreateOr(PBICond, BICond, "brmerge", PBI); 1764193323Sed 1765193323Sed // Modify PBI to branch on the new condition to the new dests. 1766193323Sed PBI->setCondition(Cond); 1767193323Sed PBI->setSuccessor(0, CommonDest); 1768193323Sed PBI->setSuccessor(1, OtherDest); 1769193323Sed 1770193323Sed // OtherDest may have phi nodes. If so, add an entry from PBI's 1771193323Sed // block that are identical to the entries for BI's block. 1772218893Sdim AddPredecessorToBlock(OtherDest, PBI->getParent(), BB); 1773193323Sed 1774193323Sed // We know that the CommonDest already had an edge from PBI to 1775193323Sed // it. If it has PHIs though, the PHIs may have different 1776193323Sed // entries for BB and PBI's BB. If so, insert a select to make 1777193323Sed // them agree. 1778218893Sdim PHINode *PN; 1779193323Sed for (BasicBlock::iterator II = CommonDest->begin(); 1780193323Sed (PN = dyn_cast<PHINode>(II)); ++II) { 1781193323Sed Value *BIV = PN->getIncomingValueForBlock(BB); 1782193323Sed unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); 1783193323Sed Value *PBIV = PN->getIncomingValue(PBBIdx); 1784193323Sed if (BIV != PBIV) { 1785193323Sed // Insert a select in PBI to pick the right value. 1786193323Sed Value *NV = SelectInst::Create(PBICond, PBIV, BIV, 1787193323Sed PBIV->getName()+".mux", PBI); 1788193323Sed PN->setIncomingValue(PBBIdx, NV); 1789193323Sed } 1790193323Sed } 1791193323Sed 1792202375Srdivacky DEBUG(dbgs() << "INTO: " << *PBI->getParent()); 1793202375Srdivacky DEBUG(dbgs() << *PBI->getParent()->getParent()); 1794193323Sed 1795193323Sed // This basic block is probably dead. We know it has at least 1796193323Sed // one fewer predecessor. 1797193323Sed return true; 1798193323Sed} 1799193323Sed 1800218893Sdim// SimplifyTerminatorOnSelect - Simplifies a terminator by replacing it with a 1801218893Sdim// branch to TrueBB if Cond is true or to FalseBB if Cond is false. 1802218893Sdim// Takes care of updating the successors and removing the old terminator. 1803218893Sdim// Also makes sure not to introduce new successors by assuming that edges to 1804218893Sdim// non-successor TrueBBs and FalseBBs aren't reachable. 1805218893Sdimstatic bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, 1806218893Sdim BasicBlock *TrueBB, BasicBlock *FalseBB){ 1807218893Sdim // Remove any superfluous successor edges from the CFG. 1808218893Sdim // First, figure out which successors to preserve. 1809218893Sdim // If TrueBB and FalseBB are equal, only try to preserve one copy of that 1810218893Sdim // successor. 1811218893Sdim BasicBlock *KeepEdge1 = TrueBB; 1812218893Sdim BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : 0; 1813193323Sed 1814218893Sdim // Then remove the rest. 1815218893Sdim for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) { 1816218893Sdim BasicBlock *Succ = OldTerm->getSuccessor(I); 1817218893Sdim // Make sure only to keep exactly one copy of each edge. 1818218893Sdim if (Succ == KeepEdge1) 1819218893Sdim KeepEdge1 = 0; 1820218893Sdim else if (Succ == KeepEdge2) 1821218893Sdim KeepEdge2 = 0; 1822218893Sdim else 1823218893Sdim Succ->removePredecessor(OldTerm->getParent()); 1824218893Sdim } 1825193323Sed 1826218893Sdim // Insert an appropriate new terminator. 1827218893Sdim if ((KeepEdge1 == 0) && (KeepEdge2 == 0)) { 1828218893Sdim if (TrueBB == FalseBB) 1829218893Sdim // We were only looking for one successor, and it was present. 1830218893Sdim // Create an unconditional branch to it. 1831218893Sdim BranchInst::Create(TrueBB, OldTerm); 1832218893Sdim else 1833218893Sdim // We found both of the successors we were looking for. 1834218893Sdim // Create a conditional branch sharing the condition of the select. 1835218893Sdim BranchInst::Create(TrueBB, FalseBB, Cond, OldTerm); 1836218893Sdim } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) { 1837218893Sdim // Neither of the selected blocks were successors, so this 1838218893Sdim // terminator must be unreachable. 1839218893Sdim new UnreachableInst(OldTerm->getContext(), OldTerm); 1840218893Sdim } else { 1841218893Sdim // One of the selected values was a successor, but the other wasn't. 1842218893Sdim // Insert an unconditional branch to the one that was found; 1843218893Sdim // the edge to the one that wasn't must be unreachable. 1844218893Sdim if (KeepEdge1 == 0) 1845218893Sdim // Only TrueBB was found. 1846218893Sdim BranchInst::Create(TrueBB, OldTerm); 1847218893Sdim else 1848218893Sdim // Only FalseBB was found. 1849218893Sdim BranchInst::Create(FalseBB, OldTerm); 1850193323Sed } 1851193323Sed 1852218893Sdim EraseTerminatorInstAndDCECond(OldTerm); 1853218893Sdim return true; 1854218893Sdim} 1855193323Sed 1856221345Sdim// SimplifySwitchOnSelect - Replaces 1857221345Sdim// (switch (select cond, X, Y)) on constant X, Y 1858221345Sdim// with a branch - conditional if X and Y lead to distinct BBs, 1859221345Sdim// unconditional otherwise. 1860221345Sdimstatic bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) { 1861221345Sdim // Check for constant integer values in the select. 1862221345Sdim ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue()); 1863221345Sdim ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue()); 1864221345Sdim if (!TrueVal || !FalseVal) 1865221345Sdim return false; 1866221345Sdim 1867221345Sdim // Find the relevant condition and destinations. 1868221345Sdim Value *Condition = Select->getCondition(); 1869221345Sdim BasicBlock *TrueBB = SI->getSuccessor(SI->findCaseValue(TrueVal)); 1870221345Sdim BasicBlock *FalseBB = SI->getSuccessor(SI->findCaseValue(FalseVal)); 1871221345Sdim 1872221345Sdim // Perform the actual simplification. 1873221345Sdim return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB); 1874221345Sdim} 1875221345Sdim 1876218893Sdim// SimplifyIndirectBrOnSelect - Replaces 1877218893Sdim// (indirectbr (select cond, blockaddress(@fn, BlockA), 1878218893Sdim// blockaddress(@fn, BlockB))) 1879218893Sdim// with 1880218893Sdim// (br cond, BlockA, BlockB). 1881218893Sdimstatic bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { 1882218893Sdim // Check that both operands of the select are block addresses. 1883218893Sdim BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue()); 1884218893Sdim BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue()); 1885218893Sdim if (!TBA || !FBA) 1886218893Sdim return false; 1887198892Srdivacky 1888218893Sdim // Extract the actual blocks. 1889218893Sdim BasicBlock *TrueBB = TBA->getBasicBlock(); 1890218893Sdim BasicBlock *FalseBB = FBA->getBasicBlock(); 1891193323Sed 1892218893Sdim // Perform the actual simplification. 1893218893Sdim return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB); 1894218893Sdim} 1895193323Sed 1896218893Sdim/// TryToSimplifyUncondBranchWithICmpInIt - This is called when we find an icmp 1897218893Sdim/// instruction (a seteq/setne with a constant) as the only instruction in a 1898218893Sdim/// block that ends with an uncond branch. We are looking for a very specific 1899218893Sdim/// pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified. In 1900218893Sdim/// this case, we merge the first two "or's of icmp" into a switch, but then the 1901218893Sdim/// default value goes to an uncond block with a seteq in it, we get something 1902218893Sdim/// like: 1903218893Sdim/// 1904218893Sdim/// switch i8 %A, label %DEFAULT [ i8 1, label %end i8 2, label %end ] 1905218893Sdim/// DEFAULT: 1906218893Sdim/// %tmp = icmp eq i8 %A, 92 1907218893Sdim/// br label %end 1908218893Sdim/// end: 1909218893Sdim/// ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ] 1910218893Sdim/// 1911218893Sdim/// We prefer to split the edge to 'end' so that there is a true/false entry to 1912218893Sdim/// the PHI, merging the third icmp into the switch. 1913218893Sdimstatic bool TryToSimplifyUncondBranchWithICmpInIt(ICmpInst *ICI, 1914218893Sdim const TargetData *TD) { 1915218893Sdim BasicBlock *BB = ICI->getParent(); 1916218893Sdim // If the block has any PHIs in it or the icmp has multiple uses, it is too 1917218893Sdim // complex. 1918218893Sdim if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) return false; 1919193323Sed 1920218893Sdim Value *V = ICI->getOperand(0); 1921218893Sdim ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1)); 1922218893Sdim 1923218893Sdim // The pattern we're looking for is where our only predecessor is a switch on 1924218893Sdim // 'V' and this block is the default case for the switch. In this case we can 1925218893Sdim // fold the compared value into the switch to simplify things. 1926218893Sdim BasicBlock *Pred = BB->getSinglePredecessor(); 1927218893Sdim if (Pred == 0 || !isa<SwitchInst>(Pred->getTerminator())) return false; 1928218893Sdim 1929218893Sdim SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator()); 1930218893Sdim if (SI->getCondition() != V) 1931218893Sdim return false; 1932218893Sdim 1933218893Sdim // If BB is reachable on a non-default case, then we simply know the value of 1934218893Sdim // V in this block. Substitute it and constant fold the icmp instruction 1935218893Sdim // away. 1936218893Sdim if (SI->getDefaultDest() != BB) { 1937218893Sdim ConstantInt *VVal = SI->findCaseDest(BB); 1938218893Sdim assert(VVal && "Should have a unique destination value"); 1939218893Sdim ICI->setOperand(0, VVal); 1940218893Sdim 1941218893Sdim if (Value *V = SimplifyInstruction(ICI, TD)) { 1942218893Sdim ICI->replaceAllUsesWith(V); 1943218893Sdim ICI->eraseFromParent(); 1944218893Sdim } 1945218893Sdim // BB is now empty, so it is likely to simplify away. 1946218893Sdim return SimplifyCFG(BB) | true; 1947218893Sdim } 1948218893Sdim 1949218893Sdim // Ok, the block is reachable from the default dest. If the constant we're 1950218893Sdim // comparing exists in one of the other edges, then we can constant fold ICI 1951218893Sdim // and zap it. 1952218893Sdim if (SI->findCaseValue(Cst) != 0) { 1953218893Sdim Value *V; 1954218893Sdim if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 1955218893Sdim V = ConstantInt::getFalse(BB->getContext()); 1956218893Sdim else 1957218893Sdim V = ConstantInt::getTrue(BB->getContext()); 1958218893Sdim 1959218893Sdim ICI->replaceAllUsesWith(V); 1960218893Sdim ICI->eraseFromParent(); 1961218893Sdim // BB is now empty, so it is likely to simplify away. 1962218893Sdim return SimplifyCFG(BB) | true; 1963218893Sdim } 1964218893Sdim 1965218893Sdim // The use of the icmp has to be in the 'end' block, by the only PHI node in 1966218893Sdim // the block. 1967218893Sdim BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0); 1968218893Sdim PHINode *PHIUse = dyn_cast<PHINode>(ICI->use_back()); 1969218893Sdim if (PHIUse == 0 || PHIUse != &SuccBlock->front() || 1970218893Sdim isa<PHINode>(++BasicBlock::iterator(PHIUse))) 1971218893Sdim return false; 1972193323Sed 1973218893Sdim // If the icmp is a SETEQ, then the default dest gets false, the new edge gets 1974218893Sdim // true in the PHI. 1975218893Sdim Constant *DefaultCst = ConstantInt::getTrue(BB->getContext()); 1976218893Sdim Constant *NewCst = ConstantInt::getFalse(BB->getContext()); 1977193323Sed 1978218893Sdim if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 1979218893Sdim std::swap(DefaultCst, NewCst); 1980193323Sed 1981218893Sdim // Replace ICI (which is used by the PHI for the default value) with true or 1982218893Sdim // false depending on if it is EQ or NE. 1983218893Sdim ICI->replaceAllUsesWith(DefaultCst); 1984218893Sdim ICI->eraseFromParent(); 1985193323Sed 1986218893Sdim // Okay, the switch goes to this block on a default value. Add an edge from 1987218893Sdim // the switch to the merge point on the compared value. 1988218893Sdim BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "switch.edge", 1989218893Sdim BB->getParent(), BB); 1990218893Sdim SI->addCase(Cst, NewBB); 1991218893Sdim 1992218893Sdim // NewBB branches to the phi block, add the uncond branch and the phi entry. 1993218893Sdim BranchInst::Create(SuccBlock, NewBB); 1994218893Sdim PHIUse->addIncoming(NewCst, NewBB); 1995218893Sdim return true; 1996218893Sdim} 1997193323Sed 1998218893Sdim/// SimplifyBranchOnICmpChain - The specified branch is a conditional branch. 1999218893Sdim/// Check to see if it is branching on an or/and chain of icmp instructions, and 2000218893Sdim/// fold it into a switch instruction if so. 2001218893Sdimstatic bool SimplifyBranchOnICmpChain(BranchInst *BI, const TargetData *TD) { 2002218893Sdim Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); 2003218893Sdim if (Cond == 0) return false; 2004218893Sdim 2005218893Sdim 2006218893Sdim // Change br (X == 0 | X == 1), T, F into a switch instruction. 2007218893Sdim // If this is a bunch of seteq's or'd together, or if it's a bunch of 2008218893Sdim // 'setne's and'ed together, collect them. 2009218893Sdim Value *CompVal = 0; 2010218893Sdim std::vector<ConstantInt*> Values; 2011218893Sdim bool TrueWhenEqual = true; 2012218893Sdim Value *ExtraCase = 0; 2013218893Sdim unsigned UsedICmps = 0; 2014218893Sdim 2015218893Sdim if (Cond->getOpcode() == Instruction::Or) { 2016218893Sdim CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true, 2017218893Sdim UsedICmps); 2018218893Sdim } else if (Cond->getOpcode() == Instruction::And) { 2019218893Sdim CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false, 2020218893Sdim UsedICmps); 2021218893Sdim TrueWhenEqual = false; 2022218893Sdim } 2023218893Sdim 2024218893Sdim // If we didn't have a multiply compared value, fail. 2025218893Sdim if (CompVal == 0) return false; 2026193323Sed 2027218893Sdim // Avoid turning single icmps into a switch. 2028218893Sdim if (UsedICmps <= 1) 2029218893Sdim return false; 2030218893Sdim 2031218893Sdim // There might be duplicate constants in the list, which the switch 2032218893Sdim // instruction can't handle, remove them now. 2033218893Sdim array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate); 2034218893Sdim Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 2035218893Sdim 2036218893Sdim // If Extra was used, we require at least two switch values to do the 2037218893Sdim // transformation. A switch with one value is just an cond branch. 2038218893Sdim if (ExtraCase && Values.size() < 2) return false; 2039218893Sdim 2040218893Sdim // Figure out which block is which destination. 2041218893Sdim BasicBlock *DefaultBB = BI->getSuccessor(1); 2042218893Sdim BasicBlock *EdgeBB = BI->getSuccessor(0); 2043218893Sdim if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 2044218893Sdim 2045218893Sdim BasicBlock *BB = BI->getParent(); 2046218893Sdim 2047218893Sdim DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size() 2048218893Sdim << " cases into SWITCH. BB is:\n" << *BB); 2049218893Sdim 2050218893Sdim // If there are any extra values that couldn't be folded into the switch 2051218893Sdim // then we evaluate them with an explicit branch first. Split the block 2052218893Sdim // right before the condbr to handle it. 2053218893Sdim if (ExtraCase) { 2054218893Sdim BasicBlock *NewBB = BB->splitBasicBlock(BI, "switch.early.test"); 2055218893Sdim // Remove the uncond branch added to the old block. 2056218893Sdim TerminatorInst *OldTI = BB->getTerminator(); 2057218893Sdim 2058218893Sdim if (TrueWhenEqual) 2059218893Sdim BranchInst::Create(EdgeBB, NewBB, ExtraCase, OldTI); 2060218893Sdim else 2061218893Sdim BranchInst::Create(NewBB, EdgeBB, ExtraCase, OldTI); 2062218893Sdim 2063218893Sdim OldTI->eraseFromParent(); 2064218893Sdim 2065218893Sdim // If there are PHI nodes in EdgeBB, then we need to add a new entry to them 2066218893Sdim // for the edge we just added. 2067218893Sdim AddPredecessorToBlock(EdgeBB, BB, NewBB); 2068218893Sdim 2069218893Sdim DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase 2070218893Sdim << "\nEXTRABB = " << *BB); 2071218893Sdim BB = NewBB; 2072218893Sdim } 2073218893Sdim 2074218893Sdim // Convert pointer to int before we switch. 2075218893Sdim if (CompVal->getType()->isPointerTy()) { 2076218893Sdim assert(TD && "Cannot switch on pointer without TargetData"); 2077218893Sdim CompVal = new PtrToIntInst(CompVal, 2078218893Sdim TD->getIntPtrType(CompVal->getContext()), 2079218893Sdim "magicptr", BI); 2080218893Sdim } 2081218893Sdim 2082218893Sdim // Create the new switch instruction now. 2083218893Sdim SwitchInst *New = SwitchInst::Create(CompVal, DefaultBB, Values.size(), BI); 2084218893Sdim 2085218893Sdim // Add all of the 'cases' to the switch instruction. 2086218893Sdim for (unsigned i = 0, e = Values.size(); i != e; ++i) 2087218893Sdim New->addCase(Values[i], EdgeBB); 2088218893Sdim 2089218893Sdim // We added edges from PI to the EdgeBB. As such, if there were any 2090218893Sdim // PHI nodes in EdgeBB, they need entries to be added corresponding to 2091218893Sdim // the number of edges added. 2092218893Sdim for (BasicBlock::iterator BBI = EdgeBB->begin(); 2093218893Sdim isa<PHINode>(BBI); ++BBI) { 2094218893Sdim PHINode *PN = cast<PHINode>(BBI); 2095218893Sdim Value *InVal = PN->getIncomingValueForBlock(BB); 2096218893Sdim for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 2097218893Sdim PN->addIncoming(InVal, BB); 2098218893Sdim } 2099218893Sdim 2100218893Sdim // Erase the old branch instruction. 2101218893Sdim EraseTerminatorInstAndDCECond(BI); 2102218893Sdim 2103218893Sdim DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n'); 2104218893Sdim return true; 2105218893Sdim} 2106218893Sdim 2107218893Sdimbool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI) { 2108218893Sdim BasicBlock *BB = RI->getParent(); 2109218893Sdim if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false; 2110218893Sdim 2111218893Sdim // Find predecessors that end with branches. 2112218893Sdim SmallVector<BasicBlock*, 8> UncondBranchPreds; 2113218893Sdim SmallVector<BranchInst*, 8> CondBranchPreds; 2114218893Sdim for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 2115218893Sdim BasicBlock *P = *PI; 2116218893Sdim TerminatorInst *PTI = P->getTerminator(); 2117218893Sdim if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) { 2118218893Sdim if (BI->isUnconditional()) 2119218893Sdim UncondBranchPreds.push_back(P); 2120218893Sdim else 2121218893Sdim CondBranchPreds.push_back(BI); 2122193323Sed } 2123218893Sdim } 2124218893Sdim 2125218893Sdim // If we found some, do the transformation! 2126218893Sdim if (!UncondBranchPreds.empty() && DupRet) { 2127218893Sdim while (!UncondBranchPreds.empty()) { 2128218893Sdim BasicBlock *Pred = UncondBranchPreds.pop_back_val(); 2129218893Sdim DEBUG(dbgs() << "FOLDING: " << *BB 2130218893Sdim << "INTO UNCOND BRANCH PRED: " << *Pred); 2131218893Sdim (void)FoldReturnIntoUncondBranch(RI, BB, Pred); 2132218893Sdim } 2133218893Sdim 2134218893Sdim // If we eliminated all predecessors of the block, delete the block now. 2135218893Sdim if (pred_begin(BB) == pred_end(BB)) 2136193323Sed // We know there are no successors, so just nuke the block. 2137218893Sdim BB->eraseFromParent(); 2138218893Sdim 2139218893Sdim return true; 2140218893Sdim } 2141218893Sdim 2142218893Sdim // Check out all of the conditional branches going to this return 2143218893Sdim // instruction. If any of them just select between returns, change the 2144218893Sdim // branch itself into a select/return pair. 2145218893Sdim while (!CondBranchPreds.empty()) { 2146218893Sdim BranchInst *BI = CondBranchPreds.pop_back_val(); 2147218893Sdim 2148218893Sdim // Check to see if the non-BB successor is also a return block. 2149218893Sdim if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) && 2150218893Sdim isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) && 2151218893Sdim SimplifyCondBranchToTwoReturns(BI)) 2152193323Sed return true; 2153218893Sdim } 2154218893Sdim return false; 2155218893Sdim} 2156193323Sed 2157218893Sdimbool SimplifyCFGOpt::SimplifyUnwind(UnwindInst *UI) { 2158218893Sdim // Check to see if the first instruction in this block is just an unwind. 2159218893Sdim // If so, replace any invoke instructions which use this as an exception 2160218893Sdim // destination with call instructions. 2161218893Sdim BasicBlock *BB = UI->getParent(); 2162218893Sdim if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false; 2163193323Sed 2164218893Sdim bool Changed = false; 2165218893Sdim SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 2166218893Sdim while (!Preds.empty()) { 2167218893Sdim BasicBlock *Pred = Preds.back(); 2168218893Sdim InvokeInst *II = dyn_cast<InvokeInst>(Pred->getTerminator()); 2169218893Sdim if (II && II->getUnwindDest() == BB) { 2170218893Sdim // Insert a new branch instruction before the invoke, because this 2171218893Sdim // is now a fall through. 2172218893Sdim BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); 2173218893Sdim Pred->getInstList().remove(II); // Take out of symbol table 2174218893Sdim 2175218893Sdim // Insert the call now. 2176218893Sdim SmallVector<Value*,8> Args(II->op_begin(), II->op_end()-3); 2177218893Sdim CallInst *CI = CallInst::Create(II->getCalledValue(), 2178218893Sdim Args.begin(), Args.end(), 2179218893Sdim II->getName(), BI); 2180218893Sdim CI->setCallingConv(II->getCallingConv()); 2181218893Sdim CI->setAttributes(II->getAttributes()); 2182218893Sdim // If the invoke produced a value, the Call now does instead. 2183218893Sdim II->replaceAllUsesWith(CI); 2184218893Sdim delete II; 2185218893Sdim Changed = true; 2186193323Sed } 2187218893Sdim 2188218893Sdim Preds.pop_back(); 2189218893Sdim } 2190218893Sdim 2191218893Sdim // If this block is now dead (and isn't the entry block), remove it. 2192218893Sdim if (pred_begin(BB) == pred_end(BB) && 2193218893Sdim BB != &BB->getParent()->getEntryBlock()) { 2194218893Sdim // We know there are no successors, so just nuke the block. 2195218893Sdim BB->eraseFromParent(); 2196218893Sdim return true; 2197218893Sdim } 2198218893Sdim 2199218893Sdim return Changed; 2200218893Sdim} 2201193323Sed 2202218893Sdimbool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { 2203218893Sdim BasicBlock *BB = UI->getParent(); 2204218893Sdim 2205218893Sdim bool Changed = false; 2206218893Sdim 2207218893Sdim // If there are any instructions immediately before the unreachable that can 2208218893Sdim // be removed, do so. 2209218893Sdim while (UI != BB->begin()) { 2210218893Sdim BasicBlock::iterator BBI = UI; 2211218893Sdim --BBI; 2212218893Sdim // Do not delete instructions that can have side effects, like calls 2213218893Sdim // (which may never return) and volatile loads and stores. 2214218893Sdim if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break; 2215218893Sdim 2216218893Sdim if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) 2217218893Sdim if (SI->isVolatile()) 2218218893Sdim break; 2219218893Sdim 2220218893Sdim if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) 2221218893Sdim if (LI->isVolatile()) 2222218893Sdim break; 2223218893Sdim 2224221345Sdim // Delete this instruction (any uses are guaranteed to be dead) 2225221345Sdim if (!BBI->use_empty()) 2226221345Sdim BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 2227218893Sdim BBI->eraseFromParent(); 2228218893Sdim Changed = true; 2229218893Sdim } 2230218893Sdim 2231218893Sdim // If the unreachable instruction is the first in the block, take a gander 2232218893Sdim // at all of the predecessors of this instruction, and simplify them. 2233218893Sdim if (&BB->front() != UI) return Changed; 2234218893Sdim 2235218893Sdim SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 2236218893Sdim for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 2237218893Sdim TerminatorInst *TI = Preds[i]->getTerminator(); 2238218893Sdim 2239218893Sdim if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 2240218893Sdim if (BI->isUnconditional()) { 2241218893Sdim if (BI->getSuccessor(0) == BB) { 2242218893Sdim new UnreachableInst(TI->getContext(), TI); 2243218893Sdim TI->eraseFromParent(); 2244218893Sdim Changed = true; 2245218893Sdim } 2246218893Sdim } else { 2247218893Sdim if (BI->getSuccessor(0) == BB) { 2248218893Sdim BranchInst::Create(BI->getSuccessor(1), BI); 2249218893Sdim EraseTerminatorInstAndDCECond(BI); 2250218893Sdim } else if (BI->getSuccessor(1) == BB) { 2251218893Sdim BranchInst::Create(BI->getSuccessor(0), BI); 2252218893Sdim EraseTerminatorInstAndDCECond(BI); 2253218893Sdim Changed = true; 2254218893Sdim } 2255218893Sdim } 2256218893Sdim } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 2257218893Sdim for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 2258218893Sdim if (SI->getSuccessor(i) == BB) { 2259218893Sdim BB->removePredecessor(SI->getParent()); 2260218893Sdim SI->removeCase(i); 2261218893Sdim --i; --e; 2262218893Sdim Changed = true; 2263218893Sdim } 2264218893Sdim // If the default value is unreachable, figure out the most popular 2265218893Sdim // destination and make it the default. 2266218893Sdim if (SI->getSuccessor(0) == BB) { 2267221345Sdim std::map<BasicBlock*, std::pair<unsigned, unsigned> > Popularity; 2268221345Sdim for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) { 2269221345Sdim std::pair<unsigned, unsigned>& entry = 2270221345Sdim Popularity[SI->getSuccessor(i)]; 2271221345Sdim if (entry.first == 0) { 2272221345Sdim entry.first = 1; 2273221345Sdim entry.second = i; 2274221345Sdim } else { 2275221345Sdim entry.first++; 2276221345Sdim } 2277221345Sdim } 2278221345Sdim 2279218893Sdim // Find the most popular block. 2280218893Sdim unsigned MaxPop = 0; 2281221345Sdim unsigned MaxIndex = 0; 2282218893Sdim BasicBlock *MaxBlock = 0; 2283221345Sdim for (std::map<BasicBlock*, std::pair<unsigned, unsigned> >::iterator 2284218893Sdim I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 2285221345Sdim if (I->second.first > MaxPop || 2286221345Sdim (I->second.first == MaxPop && MaxIndex > I->second.second)) { 2287221345Sdim MaxPop = I->second.first; 2288221345Sdim MaxIndex = I->second.second; 2289218893Sdim MaxBlock = I->first; 2290193323Sed } 2291193323Sed } 2292218893Sdim if (MaxBlock) { 2293218893Sdim // Make this the new default, allowing us to delete any explicit 2294218893Sdim // edges to it. 2295218893Sdim SI->setSuccessor(0, MaxBlock); 2296218893Sdim Changed = true; 2297218893Sdim 2298218893Sdim // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 2299218893Sdim // it. 2300218893Sdim if (isa<PHINode>(MaxBlock->begin())) 2301218893Sdim for (unsigned i = 0; i != MaxPop-1; ++i) 2302218893Sdim MaxBlock->removePredecessor(SI->getParent()); 2303218893Sdim 2304218893Sdim for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) 2305218893Sdim if (SI->getSuccessor(i) == MaxBlock) { 2306218893Sdim SI->removeCase(i); 2307218893Sdim --i; --e; 2308218893Sdim } 2309218893Sdim } 2310193323Sed } 2311218893Sdim } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 2312218893Sdim if (II->getUnwindDest() == BB) { 2313218893Sdim // Convert the invoke to a call instruction. This would be a good 2314218893Sdim // place to note that the call does not throw though. 2315218893Sdim BranchInst *BI = BranchInst::Create(II->getNormalDest(), II); 2316218893Sdim II->removeFromParent(); // Take out of symbol table 2317218893Sdim 2318218893Sdim // Insert the call now... 2319218893Sdim SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3); 2320218893Sdim CallInst *CI = CallInst::Create(II->getCalledValue(), 2321218893Sdim Args.begin(), Args.end(), 2322218893Sdim II->getName(), BI); 2323218893Sdim CI->setCallingConv(II->getCallingConv()); 2324218893Sdim CI->setAttributes(II->getAttributes()); 2325218893Sdim // If the invoke produced a value, the call does now instead. 2326218893Sdim II->replaceAllUsesWith(CI); 2327218893Sdim delete II; 2328218893Sdim Changed = true; 2329218893Sdim } 2330218893Sdim } 2331218893Sdim } 2332218893Sdim 2333218893Sdim // If this block is now dead, remove it. 2334218893Sdim if (pred_begin(BB) == pred_end(BB) && 2335218893Sdim BB != &BB->getParent()->getEntryBlock()) { 2336218893Sdim // We know there are no successors, so just nuke the block. 2337218893Sdim BB->eraseFromParent(); 2338218893Sdim return true; 2339218893Sdim } 2340193323Sed 2341218893Sdim return Changed; 2342218893Sdim} 2343193323Sed 2344218893Sdim/// TurnSwitchRangeIntoICmp - Turns a switch with that contains only a 2345218893Sdim/// integer range comparison into a sub, an icmp and a branch. 2346218893Sdimstatic bool TurnSwitchRangeIntoICmp(SwitchInst *SI) { 2347218893Sdim assert(SI->getNumCases() > 2 && "Degenerate switch?"); 2348193323Sed 2349218893Sdim // Make sure all cases point to the same destination and gather the values. 2350218893Sdim SmallVector<ConstantInt *, 16> Cases; 2351218893Sdim Cases.push_back(SI->getCaseValue(1)); 2352218893Sdim for (unsigned I = 2, E = SI->getNumCases(); I != E; ++I) { 2353218893Sdim if (SI->getSuccessor(I-1) != SI->getSuccessor(I)) 2354218893Sdim return false; 2355218893Sdim Cases.push_back(SI->getCaseValue(I)); 2356218893Sdim } 2357218893Sdim assert(Cases.size() == SI->getNumCases()-1 && "Not all cases gathered"); 2358193323Sed 2359218893Sdim // Sort the case values, then check if they form a range we can transform. 2360218893Sdim array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate); 2361218893Sdim for (unsigned I = 1, E = Cases.size(); I != E; ++I) { 2362218893Sdim if (Cases[I-1]->getValue() != Cases[I]->getValue()+1) 2363218893Sdim return false; 2364218893Sdim } 2365193323Sed 2366218893Sdim Constant *Offset = ConstantExpr::getNeg(Cases.back()); 2367218893Sdim Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases()-1); 2368193323Sed 2369218893Sdim Value *Sub = SI->getCondition(); 2370218893Sdim if (!Offset->isNullValue()) 2371218893Sdim Sub = BinaryOperator::CreateAdd(Sub, Offset, Sub->getName()+".off", SI); 2372218893Sdim Value *Cmp = new ICmpInst(SI, ICmpInst::ICMP_ULT, Sub, NumCases, "switch"); 2373218893Sdim BranchInst::Create(SI->getSuccessor(1), SI->getDefaultDest(), Cmp, SI); 2374193323Sed 2375218893Sdim // Prune obsolete incoming values off the successor's PHI nodes. 2376218893Sdim for (BasicBlock::iterator BBI = SI->getSuccessor(1)->begin(); 2377218893Sdim isa<PHINode>(BBI); ++BBI) { 2378218893Sdim for (unsigned I = 0, E = SI->getNumCases()-2; I != E; ++I) 2379218893Sdim cast<PHINode>(BBI)->removeIncomingValue(SI->getParent()); 2380218893Sdim } 2381218893Sdim SI->eraseFromParent(); 2382193323Sed 2383218893Sdim return true; 2384218893Sdim} 2385193323Sed 2386218893Sdimbool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI) { 2387218893Sdim // If this switch is too complex to want to look at, ignore it. 2388218893Sdim if (!isValueEqualityComparison(SI)) 2389218893Sdim return false; 2390193323Sed 2391218893Sdim BasicBlock *BB = SI->getParent(); 2392193323Sed 2393218893Sdim // If we only have one predecessor, and if it is a branch on this value, 2394218893Sdim // see if that predecessor totally determines the outcome of this switch. 2395218893Sdim if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 2396218893Sdim if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred)) 2397218893Sdim return SimplifyCFG(BB) | true; 2398221345Sdim 2399221345Sdim Value *Cond = SI->getCondition(); 2400221345Sdim if (SelectInst *Select = dyn_cast<SelectInst>(Cond)) 2401221345Sdim if (SimplifySwitchOnSelect(SI, Select)) 2402221345Sdim return SimplifyCFG(BB) | true; 2403221345Sdim 2404218893Sdim // If the block only contains the switch, see if we can fold the block 2405218893Sdim // away into any preds. 2406218893Sdim BasicBlock::iterator BBI = BB->begin(); 2407218893Sdim // Ignore dbg intrinsics. 2408218893Sdim while (isa<DbgInfoIntrinsic>(BBI)) 2409218893Sdim ++BBI; 2410218893Sdim if (SI == &*BBI) 2411218893Sdim if (FoldValueComparisonIntoPredecessors(SI)) 2412218893Sdim return SimplifyCFG(BB) | true; 2413193323Sed 2414218893Sdim // Try to transform the switch into an icmp and a branch. 2415218893Sdim if (TurnSwitchRangeIntoICmp(SI)) 2416218893Sdim return SimplifyCFG(BB) | true; 2417218893Sdim 2418218893Sdim return false; 2419218893Sdim} 2420193323Sed 2421218893Sdimbool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) { 2422218893Sdim BasicBlock *BB = IBI->getParent(); 2423218893Sdim bool Changed = false; 2424218893Sdim 2425218893Sdim // Eliminate redundant destinations. 2426218893Sdim SmallPtrSet<Value *, 8> Succs; 2427218893Sdim for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 2428218893Sdim BasicBlock *Dest = IBI->getDestination(i); 2429218893Sdim if (!Dest->hasAddressTaken() || !Succs.insert(Dest)) { 2430218893Sdim Dest->removePredecessor(BB); 2431218893Sdim IBI->removeDestination(i); 2432218893Sdim --i; --e; 2433218893Sdim Changed = true; 2434218893Sdim } 2435218893Sdim } 2436193323Sed 2437218893Sdim if (IBI->getNumDestinations() == 0) { 2438218893Sdim // If the indirectbr has no successors, change it to unreachable. 2439218893Sdim new UnreachableInst(IBI->getContext(), IBI); 2440218893Sdim EraseTerminatorInstAndDCECond(IBI); 2441218893Sdim return true; 2442218893Sdim } 2443218893Sdim 2444218893Sdim if (IBI->getNumDestinations() == 1) { 2445218893Sdim // If the indirectbr has one successor, change it to a direct branch. 2446218893Sdim BranchInst::Create(IBI->getDestination(0), IBI); 2447218893Sdim EraseTerminatorInstAndDCECond(IBI); 2448218893Sdim return true; 2449218893Sdim } 2450218893Sdim 2451218893Sdim if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) { 2452218893Sdim if (SimplifyIndirectBrOnSelect(IBI, SI)) 2453218893Sdim return SimplifyCFG(BB) | true; 2454218893Sdim } 2455218893Sdim return Changed; 2456218893Sdim} 2457218893Sdim 2458218893Sdimbool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI) { 2459218893Sdim BasicBlock *BB = BI->getParent(); 2460218893Sdim 2461218893Sdim // If the Terminator is the only non-phi instruction, simplify the block. 2462218893Sdim BasicBlock::iterator I = BB->getFirstNonPHIOrDbg(); 2463218893Sdim if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && 2464218893Sdim TryToSimplifyUncondBranchFromEmptyBlock(BB)) 2465218893Sdim return true; 2466218893Sdim 2467218893Sdim // If the only instruction in the block is a seteq/setne comparison 2468218893Sdim // against a constant, try to simplify the block. 2469218893Sdim if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) 2470218893Sdim if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) { 2471218893Sdim for (++I; isa<DbgInfoIntrinsic>(I); ++I) 2472218893Sdim ; 2473218893Sdim if (I->isTerminator() && TryToSimplifyUncondBranchWithICmpInIt(ICI, TD)) 2474193323Sed return true; 2475193323Sed } 2476218893Sdim 2477218893Sdim return false; 2478218893Sdim} 2479212904Sdim 2480218893Sdim 2481218893Sdimbool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI) { 2482218893Sdim BasicBlock *BB = BI->getParent(); 2483218893Sdim 2484218893Sdim // Conditional branch 2485218893Sdim if (isValueEqualityComparison(BI)) { 2486218893Sdim // If we only have one predecessor, and if it is a branch on this value, 2487218893Sdim // see if that predecessor totally determines the outcome of this 2488218893Sdim // switch. 2489218893Sdim if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 2490218893Sdim if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred)) 2491218893Sdim return SimplifyCFG(BB) | true; 2492218893Sdim 2493218893Sdim // This block must be empty, except for the setcond inst, if it exists. 2494218893Sdim // Ignore dbg intrinsics. 2495218893Sdim BasicBlock::iterator I = BB->begin(); 2496218893Sdim // Ignore dbg intrinsics. 2497218893Sdim while (isa<DbgInfoIntrinsic>(I)) 2498218893Sdim ++I; 2499218893Sdim if (&*I == BI) { 2500218893Sdim if (FoldValueComparisonIntoPredecessors(BI)) 2501218893Sdim return SimplifyCFG(BB) | true; 2502218893Sdim } else if (&*I == cast<Instruction>(BI->getCondition())){ 2503218893Sdim ++I; 2504218893Sdim // Ignore dbg intrinsics. 2505218893Sdim while (isa<DbgInfoIntrinsic>(I)) 2506218893Sdim ++I; 2507218893Sdim if (&*I == BI && FoldValueComparisonIntoPredecessors(BI)) 2508218893Sdim return SimplifyCFG(BB) | true; 2509212904Sdim } 2510193323Sed } 2511218893Sdim 2512218893Sdim // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction. 2513218893Sdim if (SimplifyBranchOnICmpChain(BI, TD)) 2514193323Sed return true; 2515218893Sdim 2516218893Sdim // We have a conditional branch to two blocks that are only reachable 2517218893Sdim // from BI. We know that the condbr dominates the two blocks, so see if 2518218893Sdim // there is any identical code in the "then" and "else" blocks. If so, we 2519218893Sdim // can hoist it up to the branching block. 2520218893Sdim if (BI->getSuccessor(0)->getSinglePredecessor() != 0) { 2521218893Sdim if (BI->getSuccessor(1)->getSinglePredecessor() != 0) { 2522218893Sdim if (HoistThenElseCodeToIf(BI)) 2523218893Sdim return SimplifyCFG(BB) | true; 2524218893Sdim } else { 2525218893Sdim // If Successor #1 has multiple preds, we may be able to conditionally 2526218893Sdim // execute Successor #0 if it branches to successor #1. 2527218893Sdim TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator(); 2528218893Sdim if (Succ0TI->getNumSuccessors() == 1 && 2529218893Sdim Succ0TI->getSuccessor(0) == BI->getSuccessor(1)) 2530218893Sdim if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0))) 2531218893Sdim return SimplifyCFG(BB) | true; 2532193323Sed } 2533218893Sdim } else if (BI->getSuccessor(1)->getSinglePredecessor() != 0) { 2534218893Sdim // If Successor #0 has multiple preds, we may be able to conditionally 2535218893Sdim // execute Successor #1 if it branches to successor #0. 2536218893Sdim TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator(); 2537218893Sdim if (Succ1TI->getNumSuccessors() == 1 && 2538218893Sdim Succ1TI->getSuccessor(0) == BI->getSuccessor(0)) 2539218893Sdim if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1))) 2540218893Sdim return SimplifyCFG(BB) | true; 2541212904Sdim } 2542193323Sed 2543218893Sdim // If this is a branch on a phi node in the current block, thread control 2544218893Sdim // through this block if any PHI node entries are constants. 2545218893Sdim if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 2546218893Sdim if (PN->getParent() == BI->getParent()) 2547218893Sdim if (FoldCondBranchOnPHI(BI, TD)) 2548218893Sdim return SimplifyCFG(BB) | true; 2549218893Sdim 2550218893Sdim // If this basic block is ONLY a setcc and a branch, and if a predecessor 2551218893Sdim // branches to us and one of our successors, fold the setcc into the 2552218893Sdim // predecessor and use logical operations to pick the right destination. 2553218893Sdim if (FoldBranchToCommonDest(BI)) 2554218893Sdim return SimplifyCFG(BB) | true; 2555218893Sdim 2556218893Sdim // Scan predecessor blocks for conditional branches. 2557218893Sdim for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 2558218893Sdim if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 2559218893Sdim if (PBI != BI && PBI->isConditional()) 2560218893Sdim if (SimplifyCondBranchToCondBranch(PBI, BI)) 2561218893Sdim return SimplifyCFG(BB) | true; 2562193323Sed 2563218893Sdim return false; 2564218893Sdim} 2565193323Sed 2566218893Sdimbool SimplifyCFGOpt::run(BasicBlock *BB) { 2567218893Sdim bool Changed = false; 2568193323Sed 2569218893Sdim assert(BB && BB->getParent() && "Block not embedded in function!"); 2570218893Sdim assert(BB->getTerminator() && "Degenerate basic block encountered!"); 2571193323Sed 2572218893Sdim // Remove basic blocks that have no predecessors (except the entry block)... 2573218893Sdim // or that just have themself as a predecessor. These are unreachable. 2574218893Sdim if ((pred_begin(BB) == pred_end(BB) && 2575218893Sdim BB != &BB->getParent()->getEntryBlock()) || 2576218893Sdim BB->getSinglePredecessor() == BB) { 2577218893Sdim DEBUG(dbgs() << "Removing BB: \n" << *BB); 2578218893Sdim DeleteDeadBlock(BB); 2579218893Sdim return true; 2580218893Sdim } 2581203954Srdivacky 2582218893Sdim // Check to see if we can constant propagate this terminator instruction 2583218893Sdim // away... 2584218893Sdim Changed |= ConstantFoldTerminator(BB); 2585193323Sed 2586218893Sdim // Check for and eliminate duplicate PHI nodes in this block. 2587218893Sdim Changed |= EliminateDuplicatePHINodes(BB); 2588193323Sed 2589218893Sdim // Merge basic blocks into their predecessor if there is only one distinct 2590218893Sdim // pred, and if there is only one distinct successor of the predecessor, and 2591218893Sdim // if there are no PHI nodes. 2592218893Sdim // 2593218893Sdim if (MergeBlockIntoPredecessor(BB)) 2594218893Sdim return true; 2595218893Sdim 2596218893Sdim // If there is a trivial two-entry PHI node in this basic block, and we can 2597218893Sdim // eliminate it, do so now. 2598218893Sdim if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 2599218893Sdim if (PN->getNumIncomingValues() == 2) 2600218893Sdim Changed |= FoldTwoEntryPHINode(PN, TD); 2601193323Sed 2602218893Sdim if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 2603218893Sdim if (BI->isUnconditional()) { 2604218893Sdim if (SimplifyUncondBranch(BI)) return true; 2605218893Sdim } else { 2606218893Sdim if (SimplifyCondBranch(BI)) return true; 2607218893Sdim } 2608218893Sdim } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 2609218893Sdim if (SimplifyReturn(RI)) return true; 2610218893Sdim } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 2611218893Sdim if (SimplifySwitch(SI)) return true; 2612218893Sdim } else if (UnreachableInst *UI = 2613218893Sdim dyn_cast<UnreachableInst>(BB->getTerminator())) { 2614218893Sdim if (SimplifyUnreachable(UI)) return true; 2615218893Sdim } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) { 2616218893Sdim if (SimplifyUnwind(UI)) return true; 2617218893Sdim } else if (IndirectBrInst *IBI = 2618218893Sdim dyn_cast<IndirectBrInst>(BB->getTerminator())) { 2619218893Sdim if (SimplifyIndirectBr(IBI)) return true; 2620218893Sdim } 2621193323Sed 2622193323Sed return Changed; 2623193323Sed} 2624203954Srdivacky 2625203954Srdivacky/// SimplifyCFG - This function is used to do simplification of a CFG. For 2626203954Srdivacky/// example, it adjusts branches to branches to eliminate the extra hop, it 2627203954Srdivacky/// eliminates unreachable basic blocks, and does other "peephole" optimization 2628203954Srdivacky/// of the CFG. It returns true if a modification was made. 2629203954Srdivacky/// 2630203954Srdivackybool llvm::SimplifyCFG(BasicBlock *BB, const TargetData *TD) { 2631203954Srdivacky return SimplifyCFGOpt(TD).run(BB); 2632203954Srdivacky} 2633