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" 16198892Srdivacky#include "llvm/ADT/DenseMap.h" 17239462Sdim#include "llvm/ADT/STLExtras.h" 18234353Sdim#include "llvm/ADT/SetVector.h" 19239462Sdim#include "llvm/ADT/SmallPtrSet.h" 20193323Sed#include "llvm/ADT/SmallVector.h" 21193323Sed#include "llvm/ADT/Statistic.h" 22263508Sdim#include "llvm/Analysis/ConstantFolding.h" 23239462Sdim#include "llvm/Analysis/InstructionSimplify.h" 24249423Sdim#include "llvm/Analysis/TargetTransformInfo.h" 25239462Sdim#include "llvm/Analysis/ValueTracking.h" 26249423Sdim#include "llvm/IR/Constants.h" 27249423Sdim#include "llvm/IR/DataLayout.h" 28249423Sdim#include "llvm/IR/DerivedTypes.h" 29249423Sdim#include "llvm/IR/GlobalVariable.h" 30249423Sdim#include "llvm/IR/IRBuilder.h" 31249423Sdim#include "llvm/IR/Instructions.h" 32249423Sdim#include "llvm/IR/IntrinsicInst.h" 33249423Sdim#include "llvm/IR/LLVMContext.h" 34249423Sdim#include "llvm/IR/MDBuilder.h" 35249423Sdim#include "llvm/IR/Metadata.h" 36249423Sdim#include "llvm/IR/Module.h" 37249423Sdim#include "llvm/IR/Operator.h" 38249423Sdim#include "llvm/IR/Type.h" 39218893Sdim#include "llvm/Support/CFG.h" 40218893Sdim#include "llvm/Support/CommandLine.h" 41218893Sdim#include "llvm/Support/ConstantRange.h" 42218893Sdim#include "llvm/Support/Debug.h" 43223017Sdim#include "llvm/Support/NoFolder.h" 44263508Sdim#include "llvm/Support/PatternMatch.h" 45218893Sdim#include "llvm/Support/raw_ostream.h" 46239462Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 47193323Sed#include <algorithm> 48249423Sdim#include <map> 49193323Sed#include <set> 50193323Sedusing namespace llvm; 51263508Sdimusing namespace PatternMatch; 52193323Sed 53221345Sdimstatic cl::opt<unsigned> 54221345SdimPHINodeFoldingThreshold("phi-node-folding-threshold", cl::Hidden, cl::init(1), 55221345Sdim cl::desc("Control the amount of phi node folding to perform (default = 1)")); 56221345Sdim 57218893Sdimstatic cl::opt<bool> 58218893SdimDupRet("simplifycfg-dup-ret", cl::Hidden, cl::init(false), 59218893Sdim cl::desc("Duplicate return instructions into unconditional branches")); 60218893Sdim 61243830Sdimstatic cl::opt<bool> 62243830SdimSinkCommon("simplifycfg-sink-common", cl::Hidden, cl::init(true), 63243830Sdim cl::desc("Sink common instructions down to the end block")); 64243830Sdim 65251662Sdimstatic cl::opt<bool> 66251662SdimHoistCondStores("simplifycfg-hoist-cond-stores", cl::Hidden, cl::init(true), 67251662Sdim cl::desc("Hoist conditional stores if an unconditional store preceeds")); 68251662Sdim 69243830SdimSTATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps"); 70243830SdimSTATISTIC(NumLookupTables, "Number of switch instructions turned into lookup tables"); 71243830SdimSTATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block"); 72193323SedSTATISTIC(NumSpeculations, "Number of speculative executed instructions"); 73193323Sed 74203954Srdivackynamespace { 75239462Sdim /// ValueEqualityComparisonCase - Represents a case of a switch. 76239462Sdim struct ValueEqualityComparisonCase { 77239462Sdim ConstantInt *Value; 78239462Sdim BasicBlock *Dest; 79239462Sdim 80239462Sdim ValueEqualityComparisonCase(ConstantInt *Value, BasicBlock *Dest) 81239462Sdim : Value(Value), Dest(Dest) {} 82239462Sdim 83239462Sdim bool operator<(ValueEqualityComparisonCase RHS) const { 84239462Sdim // Comparing pointers is ok as we only rely on the order for uniquing. 85239462Sdim return Value < RHS.Value; 86239462Sdim } 87243830Sdim 88243830Sdim bool operator==(BasicBlock *RHSDest) const { return Dest == RHSDest; } 89239462Sdim }; 90239462Sdim 91203954Srdivackyclass SimplifyCFGOpt { 92249423Sdim const TargetTransformInfo &TTI; 93243830Sdim const DataLayout *const TD; 94203954Srdivacky Value *isValueEqualityComparison(TerminatorInst *TI); 95203954Srdivacky BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI, 96239462Sdim std::vector<ValueEqualityComparisonCase> &Cases); 97203954Srdivacky bool SimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 98223017Sdim BasicBlock *Pred, 99223017Sdim IRBuilder<> &Builder); 100223017Sdim bool FoldValueComparisonIntoPredecessors(TerminatorInst *TI, 101223017Sdim IRBuilder<> &Builder); 102203954Srdivacky 103234353Sdim bool SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder); 104226633Sdim bool SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder); 105218893Sdim bool SimplifyUnreachable(UnreachableInst *UI); 106223017Sdim bool SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder); 107218893Sdim bool SimplifyIndirectBr(IndirectBrInst *IBI); 108223017Sdim bool SimplifyUncondBranch(BranchInst *BI, IRBuilder <> &Builder); 109223017Sdim bool SimplifyCondBranch(BranchInst *BI, IRBuilder <>&Builder); 110218893Sdim 111203954Srdivackypublic: 112249423Sdim SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout *TD) 113249423Sdim : TTI(TTI), TD(TD) {} 114203954Srdivacky bool run(BasicBlock *BB); 115203954Srdivacky}; 116203954Srdivacky} 117203954Srdivacky 118193323Sed/// SafeToMergeTerminators - Return true if it is safe to merge these two 119193323Sed/// terminator instructions together. 120193323Sed/// 121193323Sedstatic bool SafeToMergeTerminators(TerminatorInst *SI1, TerminatorInst *SI2) { 122193323Sed if (SI1 == SI2) return false; // Can't merge with self! 123243830Sdim 124193323Sed // It is not safe to merge these two switch instructions if they have a common 125193323Sed // successor, and if that successor has a PHI node, and if *that* PHI node has 126193323Sed // conflicting incoming values from the two switch blocks. 127193323Sed BasicBlock *SI1BB = SI1->getParent(); 128193323Sed BasicBlock *SI2BB = SI2->getParent(); 129193323Sed SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 130243830Sdim 131193323Sed for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 132193323Sed if (SI1Succs.count(*I)) 133193323Sed for (BasicBlock::iterator BBI = (*I)->begin(); 134193323Sed isa<PHINode>(BBI); ++BBI) { 135193323Sed PHINode *PN = cast<PHINode>(BBI); 136193323Sed if (PN->getIncomingValueForBlock(SI1BB) != 137193323Sed PN->getIncomingValueForBlock(SI2BB)) 138193323Sed return false; 139193323Sed } 140243830Sdim 141193323Sed return true; 142193323Sed} 143193323Sed 144239462Sdim/// isProfitableToFoldUnconditional - Return true if it is safe and profitable 145239462Sdim/// to merge these two terminator instructions together, where SI1 is an 146239462Sdim/// unconditional branch. PhiNodes will store all PHI nodes in common 147239462Sdim/// successors. 148239462Sdim/// 149239462Sdimstatic bool isProfitableToFoldUnconditional(BranchInst *SI1, 150239462Sdim BranchInst *SI2, 151239462Sdim Instruction *Cond, 152239462Sdim SmallVectorImpl<PHINode*> &PhiNodes) { 153239462Sdim if (SI1 == SI2) return false; // Can't merge with self! 154239462Sdim assert(SI1->isUnconditional() && SI2->isConditional()); 155239462Sdim 156239462Sdim // We fold the unconditional branch if we can easily update all PHI nodes in 157243830Sdim // common successors: 158239462Sdim // 1> We have a constant incoming value for the conditional branch; 159239462Sdim // 2> We have "Cond" as the incoming value for the unconditional branch; 160239462Sdim // 3> SI2->getCondition() and Cond have same operands. 161239462Sdim CmpInst *Ci2 = dyn_cast<CmpInst>(SI2->getCondition()); 162239462Sdim if (!Ci2) return false; 163239462Sdim if (!(Cond->getOperand(0) == Ci2->getOperand(0) && 164239462Sdim Cond->getOperand(1) == Ci2->getOperand(1)) && 165239462Sdim !(Cond->getOperand(0) == Ci2->getOperand(1) && 166239462Sdim Cond->getOperand(1) == Ci2->getOperand(0))) 167239462Sdim return false; 168239462Sdim 169239462Sdim BasicBlock *SI1BB = SI1->getParent(); 170239462Sdim BasicBlock *SI2BB = SI2->getParent(); 171239462Sdim SmallPtrSet<BasicBlock*, 16> SI1Succs(succ_begin(SI1BB), succ_end(SI1BB)); 172239462Sdim for (succ_iterator I = succ_begin(SI2BB), E = succ_end(SI2BB); I != E; ++I) 173239462Sdim if (SI1Succs.count(*I)) 174239462Sdim for (BasicBlock::iterator BBI = (*I)->begin(); 175239462Sdim isa<PHINode>(BBI); ++BBI) { 176239462Sdim PHINode *PN = cast<PHINode>(BBI); 177239462Sdim if (PN->getIncomingValueForBlock(SI1BB) != Cond || 178239462Sdim !isa<ConstantInt>(PN->getIncomingValueForBlock(SI2BB))) 179239462Sdim return false; 180239462Sdim PhiNodes.push_back(PN); 181239462Sdim } 182239462Sdim return true; 183239462Sdim} 184239462Sdim 185193323Sed/// AddPredecessorToBlock - Update PHI nodes in Succ to indicate that there will 186193323Sed/// now be entries in it from the 'NewPred' block. The values that will be 187193323Sed/// flowing into the PHI nodes will be the same as those coming in from 188193323Sed/// ExistPred, an existing predecessor of Succ. 189193323Sedstatic void AddPredecessorToBlock(BasicBlock *Succ, BasicBlock *NewPred, 190193323Sed BasicBlock *ExistPred) { 191193323Sed if (!isa<PHINode>(Succ->begin())) return; // Quick exit if nothing to do 192243830Sdim 193193323Sed PHINode *PN; 194193323Sed for (BasicBlock::iterator I = Succ->begin(); 195193323Sed (PN = dyn_cast<PHINode>(I)); ++I) 196193323Sed PN->addIncoming(PN->getIncomingValueForBlock(ExistPred), NewPred); 197193323Sed} 198193323Sed 199263508Sdim/// ComputeSpeculationCost - Compute an abstract "cost" of speculating the 200234353Sdim/// given instruction, which is assumed to be safe to speculate. 1 means 201234353Sdim/// cheap, 2 means less cheap, and UINT_MAX means prohibitively expensive. 202234353Sdimstatic unsigned ComputeSpeculationCost(const User *I) { 203234353Sdim assert(isSafeToSpeculativelyExecute(I) && 204234353Sdim "Instruction is not safe to speculatively execute!"); 205234353Sdim switch (Operator::getOpcode(I)) { 206234353Sdim default: 207234353Sdim // In doubt, be conservative. 208234353Sdim return UINT_MAX; 209234353Sdim case Instruction::GetElementPtr: 210234353Sdim // GEPs are cheap if all indices are constant. 211234353Sdim if (!cast<GEPOperator>(I)->hasAllConstantIndices()) 212234353Sdim return UINT_MAX; 213234353Sdim return 1; 214234353Sdim case Instruction::Load: 215234353Sdim case Instruction::Add: 216234353Sdim case Instruction::Sub: 217234353Sdim case Instruction::And: 218234353Sdim case Instruction::Or: 219234353Sdim case Instruction::Xor: 220234353Sdim case Instruction::Shl: 221234353Sdim case Instruction::LShr: 222234353Sdim case Instruction::AShr: 223234353Sdim case Instruction::ICmp: 224234353Sdim case Instruction::Trunc: 225234353Sdim case Instruction::ZExt: 226234353Sdim case Instruction::SExt: 227234353Sdim return 1; // These are all cheap. 228234353Sdim 229234353Sdim case Instruction::Call: 230234353Sdim case Instruction::Select: 231234353Sdim return 2; 232234353Sdim } 233234353Sdim} 234234353Sdim 235193323Sed/// DominatesMergePoint - If we have a merge point of an "if condition" as 236193323Sed/// accepted above, return true if the specified value dominates the block. We 237193323Sed/// don't handle the true generality of domination here, just a special case 238193323Sed/// which works well enough for us. 239193323Sed/// 240193323Sed/// If AggressiveInsts is non-null, and if V does not dominate BB, we check to 241221345Sdim/// see if V (which must be an instruction) and its recursive operands 242221345Sdim/// that do not dominate BB have a combined cost lower than CostRemaining and 243221345Sdim/// are non-trapping. If both are true, the instruction is inserted into the 244221345Sdim/// set and true is returned. 245221345Sdim/// 246221345Sdim/// The cost for most non-trapping instructions is defined as 1 except for 247221345Sdim/// Select whose cost is 2. 248221345Sdim/// 249221345Sdim/// After this function returns, CostRemaining is decreased by the cost of 250221345Sdim/// V plus its non-dominating operands. If that cost is greater than 251221345Sdim/// CostRemaining, false is returned and CostRemaining is undefined. 252193323Sedstatic bool DominatesMergePoint(Value *V, BasicBlock *BB, 253221345Sdim SmallPtrSet<Instruction*, 4> *AggressiveInsts, 254221345Sdim unsigned &CostRemaining) { 255193323Sed Instruction *I = dyn_cast<Instruction>(V); 256193323Sed if (!I) { 257193323Sed // Non-instructions all dominate instructions, but not all constantexprs 258193323Sed // can be executed unconditionally. 259193323Sed if (ConstantExpr *C = dyn_cast<ConstantExpr>(V)) 260193323Sed if (C->canTrap()) 261193323Sed return false; 262193323Sed return true; 263193323Sed } 264193323Sed BasicBlock *PBB = I->getParent(); 265193323Sed 266193323Sed // We don't want to allow weird loops that might have the "if condition" in 267193323Sed // the bottom of this block. 268193323Sed if (PBB == BB) return false; 269193323Sed 270193323Sed // If this instruction is defined in a block that contains an unconditional 271193323Sed // branch to BB, then it must be in the 'conditional' part of the "if 272218893Sdim // statement". If not, it definitely dominates the region. 273218893Sdim BranchInst *BI = dyn_cast<BranchInst>(PBB->getTerminator()); 274218893Sdim if (BI == 0 || BI->isConditional() || BI->getSuccessor(0) != BB) 275218893Sdim return true; 276198090Srdivacky 277218893Sdim // If we aren't allowing aggressive promotion anymore, then don't consider 278218893Sdim // instructions in the 'if region'. 279218893Sdim if (AggressiveInsts == 0) return false; 280243830Sdim 281221345Sdim // If we have seen this instruction before, don't count it again. 282221345Sdim if (AggressiveInsts->count(I)) return true; 283221345Sdim 284218893Sdim // Okay, it looks like the instruction IS in the "condition". Check to 285218893Sdim // see if it's a cheap instruction to unconditionally compute, and if it 286218893Sdim // only uses stuff defined outside of the condition. If so, hoist it out. 287234353Sdim if (!isSafeToSpeculativelyExecute(I)) 288218893Sdim return false; 289193323Sed 290234353Sdim unsigned Cost = ComputeSpeculationCost(I); 291221345Sdim 292221345Sdim if (Cost > CostRemaining) 293221345Sdim return false; 294221345Sdim 295221345Sdim CostRemaining -= Cost; 296221345Sdim 297221345Sdim // Okay, we can only really hoist these out if their operands do 298221345Sdim // not take us over the cost threshold. 299218893Sdim for (User::op_iterator i = I->op_begin(), e = I->op_end(); i != e; ++i) 300221345Sdim if (!DominatesMergePoint(*i, BB, AggressiveInsts, CostRemaining)) 301218893Sdim return false; 302218893Sdim // Okay, it's safe to do this! Remember this instruction. 303218893Sdim AggressiveInsts->insert(I); 304193323Sed return true; 305193323Sed} 306193323Sed 307203954Srdivacky/// GetConstantInt - Extract ConstantInt from value, looking through IntToPtr 308203954Srdivacky/// and PointerNullValue. Return NULL if value is not a constant int. 309243830Sdimstatic ConstantInt *GetConstantInt(Value *V, const DataLayout *TD) { 310203954Srdivacky // Normal constant int. 311203954Srdivacky ConstantInt *CI = dyn_cast<ConstantInt>(V); 312204642Srdivacky if (CI || !TD || !isa<Constant>(V) || !V->getType()->isPointerTy()) 313203954Srdivacky return CI; 314203954Srdivacky 315203954Srdivacky // This is some kind of pointer constant. Turn it into a pointer-sized 316203954Srdivacky // ConstantInt if possible. 317243830Sdim IntegerType *PtrTy = cast<IntegerType>(TD->getIntPtrType(V->getType())); 318203954Srdivacky 319203954Srdivacky // Null pointer means 0, see SelectionDAGBuilder::getValue(const Value*). 320203954Srdivacky if (isa<ConstantPointerNull>(V)) 321203954Srdivacky return ConstantInt::get(PtrTy, 0); 322203954Srdivacky 323203954Srdivacky // IntToPtr const int. 324203954Srdivacky if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 325203954Srdivacky if (CE->getOpcode() == Instruction::IntToPtr) 326203954Srdivacky if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(0))) { 327203954Srdivacky // The constant is very likely to have the right type already. 328203954Srdivacky if (CI->getType() == PtrTy) 329203954Srdivacky return CI; 330203954Srdivacky else 331203954Srdivacky return cast<ConstantInt> 332203954Srdivacky (ConstantExpr::getIntegerCast(CI, PtrTy, /*isSigned=*/false)); 333203954Srdivacky } 334203954Srdivacky return 0; 335203954Srdivacky} 336203954Srdivacky 337218893Sdim/// GatherConstantCompares - Given a potentially 'or'd or 'and'd together 338218893Sdim/// collection of icmp eq/ne instructions that compare a value against a 339218893Sdim/// constant, return the value being compared, and stick the constant into the 340218893Sdim/// Values vector. 341218893Sdimstatic Value * 342218893SdimGatherConstantCompares(Value *V, std::vector<ConstantInt*> &Vals, Value *&Extra, 343243830Sdim const DataLayout *TD, bool isEQ, unsigned &UsedICmps) { 344218893Sdim Instruction *I = dyn_cast<Instruction>(V); 345218893Sdim if (I == 0) return 0; 346243830Sdim 347218893Sdim // If this is an icmp against a constant, handle this as one of the cases. 348218893Sdim if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) { 349218893Sdim if (ConstantInt *C = GetConstantInt(I->getOperand(1), TD)) { 350263508Sdim Value *RHSVal; 351263508Sdim ConstantInt *RHSC; 352263508Sdim 353218893Sdim if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ:ICmpInst::ICMP_NE)) { 354263508Sdim // (x & ~2^x) == y --> x == y || x == y|2^x 355263508Sdim // This undoes a transformation done by instcombine to fuse 2 compares. 356263508Sdim if (match(ICI->getOperand(0), 357263508Sdim m_And(m_Value(RHSVal), m_ConstantInt(RHSC)))) { 358263508Sdim APInt Not = ~RHSC->getValue(); 359263508Sdim if (Not.isPowerOf2()) { 360263508Sdim Vals.push_back(C); 361263508Sdim Vals.push_back( 362263508Sdim ConstantInt::get(C->getContext(), C->getValue() | Not)); 363263508Sdim UsedICmps++; 364263508Sdim return RHSVal; 365263508Sdim } 366263508Sdim } 367263508Sdim 368218893Sdim UsedICmps++; 369218893Sdim Vals.push_back(C); 370218893Sdim return I->getOperand(0); 371193323Sed } 372243830Sdim 373218893Sdim // If we have "x ult 3" comparison, for example, then we can add 0,1,2 to 374218893Sdim // the set. 375218893Sdim ConstantRange Span = 376218893Sdim ConstantRange::makeICmpRegion(ICI->getPredicate(), C->getValue()); 377243830Sdim 378263508Sdim // Shift the range if the compare is fed by an add. This is the range 379263508Sdim // compare idiom as emitted by instcombine. 380263508Sdim bool hasAdd = 381263508Sdim match(I->getOperand(0), m_Add(m_Value(RHSVal), m_ConstantInt(RHSC))); 382263508Sdim if (hasAdd) 383263508Sdim Span = Span.subtract(RHSC->getValue()); 384263508Sdim 385218893Sdim // If this is an and/!= check then we want to optimize "x ugt 2" into 386218893Sdim // x != 0 && x != 1. 387218893Sdim if (!isEQ) 388218893Sdim Span = Span.inverse(); 389243830Sdim 390218893Sdim // If there are a ton of values, we don't want to make a ginormous switch. 391234353Sdim if (Span.getSetSize().ugt(8) || Span.isEmptySet()) 392218893Sdim return 0; 393243830Sdim 394218893Sdim for (APInt Tmp = Span.getLower(); Tmp != Span.getUpper(); ++Tmp) 395218893Sdim Vals.push_back(ConstantInt::get(V->getContext(), Tmp)); 396218893Sdim UsedICmps++; 397263508Sdim return hasAdd ? RHSVal : I->getOperand(0); 398193323Sed } 399218893Sdim return 0; 400193323Sed } 401243830Sdim 402218893Sdim // Otherwise, we can only handle an | or &, depending on isEQ. 403218893Sdim if (I->getOpcode() != (isEQ ? Instruction::Or : Instruction::And)) 404218893Sdim return 0; 405243830Sdim 406218893Sdim unsigned NumValsBeforeLHS = Vals.size(); 407218893Sdim unsigned UsedICmpsBeforeLHS = UsedICmps; 408218893Sdim if (Value *LHS = GatherConstantCompares(I->getOperand(0), Vals, Extra, TD, 409218893Sdim isEQ, UsedICmps)) { 410218893Sdim unsigned NumVals = Vals.size(); 411218893Sdim unsigned UsedICmpsBeforeRHS = UsedICmps; 412218893Sdim if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, 413218893Sdim isEQ, UsedICmps)) { 414218893Sdim if (LHS == RHS) 415218893Sdim return LHS; 416218893Sdim Vals.resize(NumVals); 417218893Sdim UsedICmps = UsedICmpsBeforeRHS; 418218893Sdim } 419193323Sed 420218893Sdim // The RHS of the or/and can't be folded in and we haven't used "Extra" yet, 421218893Sdim // set it and return success. 422218893Sdim if (Extra == 0 || Extra == I->getOperand(1)) { 423218893Sdim Extra = I->getOperand(1); 424218893Sdim return LHS; 425193323Sed } 426243830Sdim 427218893Sdim Vals.resize(NumValsBeforeLHS); 428218893Sdim UsedICmps = UsedICmpsBeforeLHS; 429218893Sdim return 0; 430193323Sed } 431243830Sdim 432218893Sdim // If the LHS can't be folded in, but Extra is available and RHS can, try to 433218893Sdim // use LHS as Extra. 434218893Sdim if (Extra == 0 || Extra == I->getOperand(0)) { 435218893Sdim Value *OldExtra = Extra; 436218893Sdim Extra = I->getOperand(0); 437218893Sdim if (Value *RHS = GatherConstantCompares(I->getOperand(1), Vals, Extra, TD, 438218893Sdim isEQ, UsedICmps)) 439218893Sdim return RHS; 440218893Sdim assert(Vals.size() == NumValsBeforeLHS); 441218893Sdim Extra = OldExtra; 442218893Sdim } 443243830Sdim 444193323Sed return 0; 445193323Sed} 446234353Sdim 447193323Sedstatic void EraseTerminatorInstAndDCECond(TerminatorInst *TI) { 448234353Sdim Instruction *Cond = 0; 449193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 450193323Sed Cond = dyn_cast<Instruction>(SI->getCondition()); 451193323Sed } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 452193323Sed if (BI->isConditional()) 453193323Sed Cond = dyn_cast<Instruction>(BI->getCondition()); 454218893Sdim } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(TI)) { 455218893Sdim Cond = dyn_cast<Instruction>(IBI->getAddress()); 456193323Sed } 457193323Sed 458193323Sed TI->eraseFromParent(); 459193323Sed if (Cond) RecursivelyDeleteTriviallyDeadInstructions(Cond); 460193323Sed} 461193323Sed 462193323Sed/// isValueEqualityComparison - Return true if the specified terminator checks 463193323Sed/// to see if a value is equal to constant integer value. 464203954SrdivackyValue *SimplifyCFGOpt::isValueEqualityComparison(TerminatorInst *TI) { 465203954Srdivacky Value *CV = 0; 466193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 467193323Sed // Do not permit merging of large switch instructions into their 468193323Sed // predecessors unless there is only one predecessor. 469203954Srdivacky if (SI->getNumSuccessors()*std::distance(pred_begin(SI->getParent()), 470203954Srdivacky pred_end(SI->getParent())) <= 128) 471203954Srdivacky CV = SI->getCondition(); 472203954Srdivacky } else if (BranchInst *BI = dyn_cast<BranchInst>(TI)) 473193323Sed if (BI->isConditional() && BI->getCondition()->hasOneUse()) 474193323Sed if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) 475263508Sdim if (ICI->isEquality() && GetConstantInt(ICI->getOperand(1), TD)) 476203954Srdivacky CV = ICI->getOperand(0); 477203954Srdivacky 478203954Srdivacky // Unwrap any lossless ptrtoint cast. 479263508Sdim if (TD && CV) { 480263508Sdim if (PtrToIntInst *PTII = dyn_cast<PtrToIntInst>(CV)) { 481263508Sdim Value *Ptr = PTII->getPointerOperand(); 482263508Sdim if (PTII->getType() == TD->getIntPtrType(Ptr->getType())) 483263508Sdim CV = Ptr; 484263508Sdim } 485263508Sdim } 486203954Srdivacky return CV; 487193323Sed} 488193323Sed 489193323Sed/// GetValueEqualityComparisonCases - Given a value comparison instruction, 490193323Sed/// decode all of the 'cases' that it represents and return the 'default' block. 491203954SrdivackyBasicBlock *SimplifyCFGOpt:: 492193323SedGetValueEqualityComparisonCases(TerminatorInst *TI, 493239462Sdim std::vector<ValueEqualityComparisonCase> 494239462Sdim &Cases) { 495193323Sed if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 496193323Sed Cases.reserve(SI->getNumCases()); 497234353Sdim for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) 498239462Sdim Cases.push_back(ValueEqualityComparisonCase(i.getCaseValue(), 499239462Sdim i.getCaseSuccessor())); 500193323Sed return SI->getDefaultDest(); 501193323Sed } 502193323Sed 503193323Sed BranchInst *BI = cast<BranchInst>(TI); 504193323Sed ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 505239462Sdim BasicBlock *Succ = BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_NE); 506239462Sdim Cases.push_back(ValueEqualityComparisonCase(GetConstantInt(ICI->getOperand(1), 507239462Sdim TD), 508239462Sdim Succ)); 509193323Sed return BI->getSuccessor(ICI->getPredicate() == ICmpInst::ICMP_EQ); 510193323Sed} 511193323Sed 512193323Sed 513193323Sed/// EliminateBlockCases - Given a vector of bb/value pairs, remove any entries 514193323Sed/// in the list that match the specified block. 515193323Sedstatic void EliminateBlockCases(BasicBlock *BB, 516239462Sdim std::vector<ValueEqualityComparisonCase> &Cases) { 517243830Sdim Cases.erase(std::remove(Cases.begin(), Cases.end(), BB), Cases.end()); 518193323Sed} 519193323Sed 520193323Sed/// ValuesOverlap - Return true if there are any keys in C1 that exist in C2 as 521193323Sed/// well. 522193323Sedstatic bool 523239462SdimValuesOverlap(std::vector<ValueEqualityComparisonCase> &C1, 524239462Sdim std::vector<ValueEqualityComparisonCase > &C2) { 525239462Sdim std::vector<ValueEqualityComparisonCase> *V1 = &C1, *V2 = &C2; 526193323Sed 527193323Sed // Make V1 be smaller than V2. 528193323Sed if (V1->size() > V2->size()) 529193323Sed std::swap(V1, V2); 530193323Sed 531193323Sed if (V1->size() == 0) return false; 532193323Sed if (V1->size() == 1) { 533193323Sed // Just scan V2. 534239462Sdim ConstantInt *TheVal = (*V1)[0].Value; 535193323Sed for (unsigned i = 0, e = V2->size(); i != e; ++i) 536239462Sdim if (TheVal == (*V2)[i].Value) 537193323Sed return true; 538193323Sed } 539193323Sed 540193323Sed // Otherwise, just sort both lists and compare element by element. 541218893Sdim array_pod_sort(V1->begin(), V1->end()); 542218893Sdim array_pod_sort(V2->begin(), V2->end()); 543193323Sed unsigned i1 = 0, i2 = 0, e1 = V1->size(), e2 = V2->size(); 544193323Sed while (i1 != e1 && i2 != e2) { 545239462Sdim if ((*V1)[i1].Value == (*V2)[i2].Value) 546193323Sed return true; 547239462Sdim if ((*V1)[i1].Value < (*V2)[i2].Value) 548193323Sed ++i1; 549193323Sed else 550193323Sed ++i2; 551193323Sed } 552193323Sed return false; 553193323Sed} 554193323Sed 555193323Sed/// SimplifyEqualityComparisonWithOnlyPredecessor - If TI is known to be a 556193323Sed/// terminator instruction and its block is known to only have a single 557193323Sed/// predecessor block, check to see if that predecessor is also a value 558193323Sed/// comparison with the same value, and if that comparison determines the 559193323Sed/// outcome of this comparison. If so, simplify TI. This does a very limited 560193323Sed/// form of jump threading. 561203954Srdivackybool SimplifyCFGOpt:: 562203954SrdivackySimplifyEqualityComparisonWithOnlyPredecessor(TerminatorInst *TI, 563223017Sdim BasicBlock *Pred, 564223017Sdim IRBuilder<> &Builder) { 565193323Sed Value *PredVal = isValueEqualityComparison(Pred->getTerminator()); 566193323Sed if (!PredVal) return false; // Not a value comparison in predecessor. 567193323Sed 568193323Sed Value *ThisVal = isValueEqualityComparison(TI); 569193323Sed assert(ThisVal && "This isn't a value comparison!!"); 570193323Sed if (ThisVal != PredVal) return false; // Different predicates. 571193323Sed 572243830Sdim // TODO: Preserve branch weight metadata, similarly to how 573243830Sdim // FoldValueComparisonIntoPredecessors preserves it. 574243830Sdim 575193323Sed // Find out information about when control will move from Pred to TI's block. 576239462Sdim std::vector<ValueEqualityComparisonCase> PredCases; 577193323Sed BasicBlock *PredDef = GetValueEqualityComparisonCases(Pred->getTerminator(), 578193323Sed PredCases); 579193323Sed EliminateBlockCases(PredDef, PredCases); // Remove default from cases. 580193323Sed 581193323Sed // Find information about how control leaves this block. 582239462Sdim std::vector<ValueEqualityComparisonCase> ThisCases; 583193323Sed BasicBlock *ThisDef = GetValueEqualityComparisonCases(TI, ThisCases); 584193323Sed EliminateBlockCases(ThisDef, ThisCases); // Remove default from cases. 585193323Sed 586193323Sed // If TI's block is the default block from Pred's comparison, potentially 587193323Sed // simplify TI based on this knowledge. 588193323Sed if (PredDef == TI->getParent()) { 589193323Sed // If we are here, we know that the value is none of those cases listed in 590193323Sed // PredCases. If there are any cases in ThisCases that are in PredCases, we 591193323Sed // can simplify TI. 592218893Sdim if (!ValuesOverlap(PredCases, ThisCases)) 593218893Sdim return false; 594243830Sdim 595218893Sdim if (isa<BranchInst>(TI)) { 596218893Sdim // Okay, one of the successors of this condbr is dead. Convert it to a 597218893Sdim // uncond br. 598218893Sdim assert(ThisCases.size() == 1 && "Branch can only have one case!"); 599218893Sdim // Insert the new branch. 600223017Sdim Instruction *NI = Builder.CreateBr(ThisDef); 601218893Sdim (void) NI; 602193323Sed 603218893Sdim // Remove PHI node entries for the dead edge. 604239462Sdim ThisCases[0].Dest->removePredecessor(TI->getParent()); 605193323Sed 606218893Sdim DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 607218893Sdim << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 608193323Sed 609218893Sdim EraseTerminatorInstAndDCECond(TI); 610218893Sdim return true; 611218893Sdim } 612243830Sdim 613218893Sdim SwitchInst *SI = cast<SwitchInst>(TI); 614218893Sdim // Okay, TI has cases that are statically dead, prune them away. 615218893Sdim SmallPtrSet<Constant*, 16> DeadCases; 616218893Sdim for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 617239462Sdim DeadCases.insert(PredCases[i].Value); 618193323Sed 619218893Sdim DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 620218893Sdim << "Through successor TI: " << *TI); 621193323Sed 622243830Sdim // Collect branch weights into a vector. 623243830Sdim SmallVector<uint32_t, 8> Weights; 624243830Sdim MDNode* MD = SI->getMetadata(LLVMContext::MD_prof); 625243830Sdim bool HasWeight = MD && (MD->getNumOperands() == 2 + SI->getNumCases()); 626243830Sdim if (HasWeight) 627243830Sdim for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e; 628243830Sdim ++MD_i) { 629243830Sdim ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(MD_i)); 630243830Sdim assert(CI); 631243830Sdim Weights.push_back(CI->getValue().getZExtValue()); 632243830Sdim } 633234353Sdim for (SwitchInst::CaseIt i = SI->case_end(), e = SI->case_begin(); i != e;) { 634234353Sdim --i; 635234353Sdim if (DeadCases.count(i.getCaseValue())) { 636243830Sdim if (HasWeight) { 637243830Sdim std::swap(Weights[i.getCaseIndex()+1], Weights.back()); 638243830Sdim Weights.pop_back(); 639243830Sdim } 640234353Sdim i.getCaseSuccessor()->removePredecessor(TI->getParent()); 641218893Sdim SI->removeCase(i); 642218893Sdim } 643234353Sdim } 644243830Sdim if (HasWeight && Weights.size() >= 2) 645243830Sdim SI->setMetadata(LLVMContext::MD_prof, 646243830Sdim MDBuilder(SI->getParent()->getContext()). 647243830Sdim createBranchWeights(Weights)); 648193323Sed 649218893Sdim DEBUG(dbgs() << "Leaving: " << *TI << "\n"); 650218893Sdim return true; 651218893Sdim } 652243830Sdim 653218893Sdim // Otherwise, TI's block must correspond to some matched value. Find out 654218893Sdim // which value (or set of values) this is. 655218893Sdim ConstantInt *TIV = 0; 656218893Sdim BasicBlock *TIBB = TI->getParent(); 657218893Sdim for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 658239462Sdim if (PredCases[i].Dest == TIBB) { 659218893Sdim if (TIV != 0) 660218893Sdim return false; // Cannot handle multiple values coming to this block. 661239462Sdim TIV = PredCases[i].Value; 662218893Sdim } 663218893Sdim assert(TIV && "No edge from pred to succ?"); 664193323Sed 665218893Sdim // Okay, we found the one constant that our value can be if we get into TI's 666218893Sdim // BB. Find out which successor will unconditionally be branched to. 667218893Sdim BasicBlock *TheRealDest = 0; 668218893Sdim for (unsigned i = 0, e = ThisCases.size(); i != e; ++i) 669239462Sdim if (ThisCases[i].Value == TIV) { 670239462Sdim TheRealDest = ThisCases[i].Dest; 671218893Sdim break; 672193323Sed } 673193323Sed 674218893Sdim // If not handled by any explicit cases, it is handled by the default case. 675218893Sdim if (TheRealDest == 0) TheRealDest = ThisDef; 676193323Sed 677218893Sdim // Remove PHI node entries for dead edges. 678218893Sdim BasicBlock *CheckEdge = TheRealDest; 679218893Sdim for (succ_iterator SI = succ_begin(TIBB), e = succ_end(TIBB); SI != e; ++SI) 680218893Sdim if (*SI != CheckEdge) 681218893Sdim (*SI)->removePredecessor(TIBB); 682218893Sdim else 683218893Sdim CheckEdge = 0; 684193323Sed 685218893Sdim // Insert the new branch. 686223017Sdim Instruction *NI = Builder.CreateBr(TheRealDest); 687218893Sdim (void) NI; 688193323Sed 689218893Sdim DEBUG(dbgs() << "Threading pred instr: " << *Pred->getTerminator() 690218893Sdim << "Through successor TI: " << *TI << "Leaving: " << *NI << "\n"); 691193323Sed 692218893Sdim EraseTerminatorInstAndDCECond(TI); 693218893Sdim return true; 694193323Sed} 695193323Sed 696193323Sednamespace { 697193323Sed /// ConstantIntOrdering - This class implements a stable ordering of constant 698193323Sed /// integers that does not depend on their address. This is important for 699193323Sed /// applications that sort ConstantInt's to ensure uniqueness. 700193323Sed struct ConstantIntOrdering { 701193323Sed bool operator()(const ConstantInt *LHS, const ConstantInt *RHS) const { 702193323Sed return LHS->getValue().ult(RHS->getValue()); 703193323Sed } 704193323Sed }; 705193323Sed} 706193323Sed 707263508Sdimstatic int ConstantIntSortPredicate(ConstantInt *const *P1, 708263508Sdim ConstantInt *const *P2) { 709263508Sdim const ConstantInt *LHS = *P1; 710263508Sdim const ConstantInt *RHS = *P2; 711218893Sdim if (LHS->getValue().ult(RHS->getValue())) 712218893Sdim return 1; 713218893Sdim if (LHS->getValue() == RHS->getValue()) 714218893Sdim return 0; 715218893Sdim return -1; 716218893Sdim} 717218893Sdim 718243830Sdimstatic inline bool HasBranchWeights(const Instruction* I) { 719243830Sdim MDNode* ProfMD = I->getMetadata(LLVMContext::MD_prof); 720243830Sdim if (ProfMD && ProfMD->getOperand(0)) 721243830Sdim if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0))) 722243830Sdim return MDS->getString().equals("branch_weights"); 723243830Sdim 724243830Sdim return false; 725243830Sdim} 726243830Sdim 727243830Sdim/// Get Weights of a given TerminatorInst, the default weight is at the front 728243830Sdim/// of the vector. If TI is a conditional eq, we need to swap the branch-weight 729243830Sdim/// metadata. 730243830Sdimstatic void GetBranchWeights(TerminatorInst *TI, 731243830Sdim SmallVectorImpl<uint64_t> &Weights) { 732243830Sdim MDNode* MD = TI->getMetadata(LLVMContext::MD_prof); 733243830Sdim assert(MD); 734243830Sdim for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) { 735243830Sdim ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(i)); 736243830Sdim assert(CI); 737243830Sdim Weights.push_back(CI->getValue().getZExtValue()); 738243830Sdim } 739243830Sdim 740243830Sdim // If TI is a conditional eq, the default case is the false case, 741243830Sdim // and the corresponding branch-weight data is at index 2. We swap the 742243830Sdim // default weight to be the first entry. 743243830Sdim if (BranchInst* BI = dyn_cast<BranchInst>(TI)) { 744243830Sdim assert(Weights.size() == 2); 745243830Sdim ICmpInst *ICI = cast<ICmpInst>(BI->getCondition()); 746243830Sdim if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 747243830Sdim std::swap(Weights.front(), Weights.back()); 748243830Sdim } 749243830Sdim} 750243830Sdim 751243830Sdim/// Sees if any of the weights are too big for a uint32_t, and halves all the 752243830Sdim/// weights if any are. 753243830Sdimstatic void FitWeights(MutableArrayRef<uint64_t> Weights) { 754243830Sdim bool Halve = false; 755243830Sdim for (unsigned i = 0; i < Weights.size(); ++i) 756243830Sdim if (Weights[i] > UINT_MAX) { 757243830Sdim Halve = true; 758243830Sdim break; 759243830Sdim } 760243830Sdim 761243830Sdim if (! Halve) 762243830Sdim return; 763243830Sdim 764243830Sdim for (unsigned i = 0; i < Weights.size(); ++i) 765243830Sdim Weights[i] /= 2; 766243830Sdim} 767243830Sdim 768193323Sed/// FoldValueComparisonIntoPredecessors - The specified terminator is a value 769193323Sed/// equality comparison instruction (either a switch or a branch on "X == c"). 770193323Sed/// See if any of the predecessors of the terminator block are value comparisons 771193323Sed/// on the same value. If so, and if safe to do so, fold them together. 772223017Sdimbool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI, 773223017Sdim IRBuilder<> &Builder) { 774193323Sed BasicBlock *BB = TI->getParent(); 775193323Sed Value *CV = isValueEqualityComparison(TI); // CondVal 776193323Sed assert(CV && "Not a comparison?"); 777193323Sed bool Changed = false; 778193323Sed 779193323Sed SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 780193323Sed while (!Preds.empty()) { 781193323Sed BasicBlock *Pred = Preds.pop_back_val(); 782193323Sed 783193323Sed // See if the predecessor is a comparison with the same value. 784193323Sed TerminatorInst *PTI = Pred->getTerminator(); 785193323Sed Value *PCV = isValueEqualityComparison(PTI); // PredCondVal 786193323Sed 787193323Sed if (PCV == CV && SafeToMergeTerminators(TI, PTI)) { 788193323Sed // Figure out which 'cases' to copy from SI to PSI. 789239462Sdim std::vector<ValueEqualityComparisonCase> BBCases; 790193323Sed BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); 791193323Sed 792239462Sdim std::vector<ValueEqualityComparisonCase> PredCases; 793193323Sed BasicBlock *PredDefault = GetValueEqualityComparisonCases(PTI, PredCases); 794193323Sed 795193323Sed // Based on whether the default edge from PTI goes to BB or not, fill in 796193323Sed // PredCases and PredDefault with the new switch cases we would like to 797193323Sed // build. 798193323Sed SmallVector<BasicBlock*, 8> NewSuccessors; 799193323Sed 800243830Sdim // Update the branch weight metadata along the way 801243830Sdim SmallVector<uint64_t, 8> Weights; 802243830Sdim bool PredHasWeights = HasBranchWeights(PTI); 803243830Sdim bool SuccHasWeights = HasBranchWeights(TI); 804243830Sdim 805243830Sdim if (PredHasWeights) { 806243830Sdim GetBranchWeights(PTI, Weights); 807249423Sdim // branch-weight metadata is inconsistent here. 808243830Sdim if (Weights.size() != 1 + PredCases.size()) 809243830Sdim PredHasWeights = SuccHasWeights = false; 810243830Sdim } else if (SuccHasWeights) 811243830Sdim // If there are no predecessor weights but there are successor weights, 812243830Sdim // populate Weights with 1, which will later be scaled to the sum of 813243830Sdim // successor's weights 814243830Sdim Weights.assign(1 + PredCases.size(), 1); 815243830Sdim 816243830Sdim SmallVector<uint64_t, 8> SuccWeights; 817243830Sdim if (SuccHasWeights) { 818243830Sdim GetBranchWeights(TI, SuccWeights); 819249423Sdim // branch-weight metadata is inconsistent here. 820243830Sdim if (SuccWeights.size() != 1 + BBCases.size()) 821243830Sdim PredHasWeights = SuccHasWeights = false; 822243830Sdim } else if (PredHasWeights) 823243830Sdim SuccWeights.assign(1 + BBCases.size(), 1); 824243830Sdim 825193323Sed if (PredDefault == BB) { 826193323Sed // If this is the default destination from PTI, only the edges in TI 827193323Sed // that don't occur in PTI, or that branch to BB will be activated. 828193323Sed std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 829193323Sed for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 830239462Sdim if (PredCases[i].Dest != BB) 831239462Sdim PTIHandled.insert(PredCases[i].Value); 832193323Sed else { 833193323Sed // The default destination is BB, we don't need explicit targets. 834193323Sed std::swap(PredCases[i], PredCases.back()); 835243830Sdim 836243830Sdim if (PredHasWeights || SuccHasWeights) { 837243830Sdim // Increase weight for the default case. 838243830Sdim Weights[0] += Weights[i+1]; 839243830Sdim std::swap(Weights[i+1], Weights.back()); 840243830Sdim Weights.pop_back(); 841243830Sdim } 842243830Sdim 843193323Sed PredCases.pop_back(); 844193323Sed --i; --e; 845193323Sed } 846193323Sed 847193323Sed // Reconstruct the new switch statement we will be building. 848193323Sed if (PredDefault != BBDefault) { 849193323Sed PredDefault->removePredecessor(Pred); 850193323Sed PredDefault = BBDefault; 851193323Sed NewSuccessors.push_back(BBDefault); 852193323Sed } 853243830Sdim 854243830Sdim unsigned CasesFromPred = Weights.size(); 855243830Sdim uint64_t ValidTotalSuccWeight = 0; 856193323Sed for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 857239462Sdim if (!PTIHandled.count(BBCases[i].Value) && 858239462Sdim BBCases[i].Dest != BBDefault) { 859193323Sed PredCases.push_back(BBCases[i]); 860239462Sdim NewSuccessors.push_back(BBCases[i].Dest); 861243830Sdim if (SuccHasWeights || PredHasWeights) { 862243830Sdim // The default weight is at index 0, so weight for the ith case 863243830Sdim // should be at index i+1. Scale the cases from successor by 864243830Sdim // PredDefaultWeight (Weights[0]). 865243830Sdim Weights.push_back(Weights[0] * SuccWeights[i+1]); 866243830Sdim ValidTotalSuccWeight += SuccWeights[i+1]; 867243830Sdim } 868193323Sed } 869193323Sed 870243830Sdim if (SuccHasWeights || PredHasWeights) { 871243830Sdim ValidTotalSuccWeight += SuccWeights[0]; 872243830Sdim // Scale the cases from predecessor by ValidTotalSuccWeight. 873243830Sdim for (unsigned i = 1; i < CasesFromPred; ++i) 874243830Sdim Weights[i] *= ValidTotalSuccWeight; 875243830Sdim // Scale the default weight by SuccDefaultWeight (SuccWeights[0]). 876243830Sdim Weights[0] *= SuccWeights[0]; 877243830Sdim } 878193323Sed } else { 879193323Sed // If this is not the default destination from PSI, only the edges 880193323Sed // in SI that occur in PSI with a destination of BB will be 881193323Sed // activated. 882193323Sed std::set<ConstantInt*, ConstantIntOrdering> PTIHandled; 883243830Sdim std::map<ConstantInt*, uint64_t> WeightsForHandled; 884193323Sed for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 885239462Sdim if (PredCases[i].Dest == BB) { 886239462Sdim PTIHandled.insert(PredCases[i].Value); 887243830Sdim 888243830Sdim if (PredHasWeights || SuccHasWeights) { 889243830Sdim WeightsForHandled[PredCases[i].Value] = Weights[i+1]; 890243830Sdim std::swap(Weights[i+1], Weights.back()); 891243830Sdim Weights.pop_back(); 892243830Sdim } 893243830Sdim 894193323Sed std::swap(PredCases[i], PredCases.back()); 895193323Sed PredCases.pop_back(); 896193323Sed --i; --e; 897193323Sed } 898193323Sed 899193323Sed // Okay, now we know which constants were sent to BB from the 900193323Sed // predecessor. Figure out where they will all go now. 901193323Sed for (unsigned i = 0, e = BBCases.size(); i != e; ++i) 902239462Sdim if (PTIHandled.count(BBCases[i].Value)) { 903193323Sed // If this is one we are capable of getting... 904243830Sdim if (PredHasWeights || SuccHasWeights) 905243830Sdim Weights.push_back(WeightsForHandled[BBCases[i].Value]); 906193323Sed PredCases.push_back(BBCases[i]); 907239462Sdim NewSuccessors.push_back(BBCases[i].Dest); 908239462Sdim PTIHandled.erase(BBCases[i].Value);// This constant is taken care of 909193323Sed } 910193323Sed 911193323Sed // If there are any constants vectored to BB that TI doesn't handle, 912193323Sed // they must go to the default destination of TI. 913243830Sdim for (std::set<ConstantInt*, ConstantIntOrdering>::iterator I = 914193323Sed PTIHandled.begin(), 915193323Sed E = PTIHandled.end(); I != E; ++I) { 916249423Sdim if (PredHasWeights || SuccHasWeights) 917249423Sdim Weights.push_back(WeightsForHandled[*I]); 918239462Sdim PredCases.push_back(ValueEqualityComparisonCase(*I, BBDefault)); 919193323Sed NewSuccessors.push_back(BBDefault); 920193323Sed } 921193323Sed } 922193323Sed 923193323Sed // Okay, at this point, we know which new successor Pred will get. Make 924193323Sed // sure we update the number of entries in the PHI nodes for these 925193323Sed // successors. 926193323Sed for (unsigned i = 0, e = NewSuccessors.size(); i != e; ++i) 927193323Sed AddPredecessorToBlock(NewSuccessors[i], Pred, BB); 928193323Sed 929223017Sdim Builder.SetInsertPoint(PTI); 930203954Srdivacky // Convert pointer to int before we switch. 931204642Srdivacky if (CV->getType()->isPointerTy()) { 932243830Sdim assert(TD && "Cannot switch on pointer without DataLayout"); 933263508Sdim CV = Builder.CreatePtrToInt(CV, TD->getIntPtrType(CV->getType()), 934223017Sdim "magicptr"); 935203954Srdivacky } 936203954Srdivacky 937193323Sed // Now that the successors are updated, create the new Switch instruction. 938223017Sdim SwitchInst *NewSI = Builder.CreateSwitch(CV, PredDefault, 939223017Sdim PredCases.size()); 940223017Sdim NewSI->setDebugLoc(PTI->getDebugLoc()); 941193323Sed for (unsigned i = 0, e = PredCases.size(); i != e; ++i) 942239462Sdim NewSI->addCase(PredCases[i].Value, PredCases[i].Dest); 943193323Sed 944243830Sdim if (PredHasWeights || SuccHasWeights) { 945243830Sdim // Halve the weights if any of them cannot fit in an uint32_t 946243830Sdim FitWeights(Weights); 947243830Sdim 948243830Sdim SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); 949243830Sdim 950243830Sdim NewSI->setMetadata(LLVMContext::MD_prof, 951243830Sdim MDBuilder(BB->getContext()). 952243830Sdim createBranchWeights(MDWeights)); 953243830Sdim } 954243830Sdim 955193323Sed EraseTerminatorInstAndDCECond(PTI); 956193323Sed 957193323Sed // Okay, last check. If BB is still a successor of PSI, then we must 958193323Sed // have an infinite loop case. If so, add an infinitely looping block 959193323Sed // to handle the case to preserve the behavior of the code. 960193323Sed BasicBlock *InfLoopBlock = 0; 961193323Sed for (unsigned i = 0, e = NewSI->getNumSuccessors(); i != e; ++i) 962193323Sed if (NewSI->getSuccessor(i) == BB) { 963193323Sed if (InfLoopBlock == 0) { 964193323Sed // Insert it at the end of the function, because it's either code, 965193323Sed // or it won't matter if it's hot. :) 966198090Srdivacky InfLoopBlock = BasicBlock::Create(BB->getContext(), 967198090Srdivacky "infloop", BB->getParent()); 968193323Sed BranchInst::Create(InfLoopBlock, InfLoopBlock); 969193323Sed } 970193323Sed NewSI->setSuccessor(i, InfLoopBlock); 971193323Sed } 972193323Sed 973193323Sed Changed = true; 974193323Sed } 975193323Sed } 976193323Sed return Changed; 977193323Sed} 978193323Sed 979194612Sed// isSafeToHoistInvoke - If we would need to insert a select that uses the 980194612Sed// value of this invoke (comments in HoistThenElseCodeToIf explain why we 981194612Sed// would need to do this), we can't hoist the invoke, as there is nowhere 982194612Sed// to put the select in this case. 983194612Sedstatic bool isSafeToHoistInvoke(BasicBlock *BB1, BasicBlock *BB2, 984194612Sed Instruction *I1, Instruction *I2) { 985194612Sed for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 986194612Sed PHINode *PN; 987194612Sed for (BasicBlock::iterator BBI = SI->begin(); 988194612Sed (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 989194612Sed Value *BB1V = PN->getIncomingValueForBlock(BB1); 990194612Sed Value *BB2V = PN->getIncomingValueForBlock(BB2); 991194612Sed if (BB1V != BB2V && (BB1V==I1 || BB2V==I2)) { 992194612Sed return false; 993194612Sed } 994194612Sed } 995194612Sed } 996194612Sed return true; 997194612Sed} 998194612Sed 999193323Sed/// HoistThenElseCodeToIf - Given a conditional branch that goes to BB1 and 1000193323Sed/// BB2, hoist any common code in the two blocks up into the branch block. The 1001193323Sed/// caller of this function guarantees that BI's block dominates BB1 and BB2. 1002193323Sedstatic bool HoistThenElseCodeToIf(BranchInst *BI) { 1003193323Sed // This does very trivial matching, with limited scanning, to find identical 1004193323Sed // instructions in the two blocks. In particular, we don't want to get into 1005193323Sed // O(M*N) situations here where M and N are the sizes of BB1 and BB2. As 1006193323Sed // such, we currently just scan for obviously identical instructions in an 1007193323Sed // identical order. 1008193323Sed BasicBlock *BB1 = BI->getSuccessor(0); // The true destination. 1009193323Sed BasicBlock *BB2 = BI->getSuccessor(1); // The false destination 1010193323Sed 1011193323Sed BasicBlock::iterator BB1_Itr = BB1->begin(); 1012193323Sed BasicBlock::iterator BB2_Itr = BB2->begin(); 1013193323Sed 1014193323Sed Instruction *I1 = BB1_Itr++, *I2 = BB2_Itr++; 1015221345Sdim // Skip debug info if it is not identical. 1016221345Sdim DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1); 1017221345Sdim DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2); 1018221345Sdim if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { 1019221345Sdim while (isa<DbgInfoIntrinsic>(I1)) 1020221345Sdim I1 = BB1_Itr++; 1021221345Sdim while (isa<DbgInfoIntrinsic>(I2)) 1022221345Sdim I2 = BB2_Itr++; 1023221345Sdim } 1024221345Sdim if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) || 1025194612Sed (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2))) 1026193323Sed return false; 1027193323Sed 1028193323Sed BasicBlock *BIParent = BI->getParent(); 1029193323Sed 1030263508Sdim bool Changed = false; 1031193323Sed do { 1032193323Sed // If we are hoisting the terminator instruction, don't move one (making a 1033193323Sed // broken BB), instead clone it, and remove BI. 1034193323Sed if (isa<TerminatorInst>(I1)) 1035193323Sed goto HoistTerminator; 1036193323Sed 1037193323Sed // For a normal instruction, we just move one to right before the branch, 1038193323Sed // then replace all uses of the other with the first. Finally, we remove 1039193323Sed // the now redundant second instruction. 1040193323Sed BIParent->getInstList().splice(BI, BB1->getInstList(), I1); 1041193323Sed if (!I2->use_empty()) 1042193323Sed I2->replaceAllUsesWith(I1); 1043198090Srdivacky I1->intersectOptionalDataWith(I2); 1044218893Sdim I2->eraseFromParent(); 1045263508Sdim Changed = true; 1046193323Sed 1047193323Sed I1 = BB1_Itr++; 1048193323Sed I2 = BB2_Itr++; 1049221345Sdim // Skip debug info if it is not identical. 1050221345Sdim DbgInfoIntrinsic *DBI1 = dyn_cast<DbgInfoIntrinsic>(I1); 1051221345Sdim DbgInfoIntrinsic *DBI2 = dyn_cast<DbgInfoIntrinsic>(I2); 1052221345Sdim if (!DBI1 || !DBI2 || !DBI1->isIdenticalToWhenDefined(DBI2)) { 1053221345Sdim while (isa<DbgInfoIntrinsic>(I1)) 1054221345Sdim I1 = BB1_Itr++; 1055221345Sdim while (isa<DbgInfoIntrinsic>(I2)) 1056221345Sdim I2 = BB2_Itr++; 1057221345Sdim } 1058221345Sdim } while (I1->isIdenticalToWhenDefined(I2)); 1059193323Sed 1060193323Sed return true; 1061193323Sed 1062193323SedHoistTerminator: 1063194612Sed // It may not be possible to hoist an invoke. 1064194612Sed if (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) 1065263508Sdim return Changed; 1066194612Sed 1067263508Sdim for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 1068263508Sdim PHINode *PN; 1069263508Sdim for (BasicBlock::iterator BBI = SI->begin(); 1070263508Sdim (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 1071263508Sdim Value *BB1V = PN->getIncomingValueForBlock(BB1); 1072263508Sdim Value *BB2V = PN->getIncomingValueForBlock(BB2); 1073263508Sdim if (BB1V == BB2V) 1074263508Sdim continue; 1075263508Sdim 1076263508Sdim if (isa<ConstantExpr>(BB1V) && !isSafeToSpeculativelyExecute(BB1V)) 1077263508Sdim return Changed; 1078263508Sdim if (isa<ConstantExpr>(BB2V) && !isSafeToSpeculativelyExecute(BB2V)) 1079263508Sdim return Changed; 1080263508Sdim } 1081263508Sdim } 1082263508Sdim 1083193323Sed // Okay, it is safe to hoist the terminator. 1084193323Sed Instruction *NT = I1->clone(); 1085193323Sed BIParent->getInstList().insert(BI, NT); 1086202375Srdivacky if (!NT->getType()->isVoidTy()) { 1087193323Sed I1->replaceAllUsesWith(NT); 1088193323Sed I2->replaceAllUsesWith(NT); 1089193323Sed NT->takeName(I1); 1090193323Sed } 1091193323Sed 1092223017Sdim IRBuilder<true, NoFolder> Builder(NT); 1093193323Sed // Hoisting one of the terminators from our successor is a great thing. 1094193323Sed // Unfortunately, the successors of the if/else blocks may have PHI nodes in 1095193323Sed // them. If they do, all PHI entries for BB1/BB2 must agree for all PHI 1096193323Sed // nodes, so we insert select instruction to compute the final result. 1097193323Sed std::map<std::pair<Value*,Value*>, SelectInst*> InsertedSelects; 1098193323Sed for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) { 1099193323Sed PHINode *PN; 1100193323Sed for (BasicBlock::iterator BBI = SI->begin(); 1101193323Sed (PN = dyn_cast<PHINode>(BBI)); ++BBI) { 1102193323Sed Value *BB1V = PN->getIncomingValueForBlock(BB1); 1103193323Sed Value *BB2V = PN->getIncomingValueForBlock(BB2); 1104218893Sdim if (BB1V == BB2V) continue; 1105243830Sdim 1106218893Sdim // These values do not agree. Insert a select instruction before NT 1107218893Sdim // that determines the right value. 1108218893Sdim SelectInst *&SI = InsertedSelects[std::make_pair(BB1V, BB2V)]; 1109243830Sdim if (SI == 0) 1110223017Sdim SI = cast<SelectInst> 1111223017Sdim (Builder.CreateSelect(BI->getCondition(), BB1V, BB2V, 1112223017Sdim BB1V->getName()+"."+BB2V->getName())); 1113223017Sdim 1114218893Sdim // Make the PHI node use the select for all incoming values for BB1/BB2 1115218893Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 1116218893Sdim if (PN->getIncomingBlock(i) == BB1 || PN->getIncomingBlock(i) == BB2) 1117218893Sdim PN->setIncomingValue(i, SI); 1118193323Sed } 1119193323Sed } 1120193323Sed 1121193323Sed // Update any PHI nodes in our new successors. 1122193323Sed for (succ_iterator SI = succ_begin(BB1), E = succ_end(BB1); SI != E; ++SI) 1123193323Sed AddPredecessorToBlock(*SI, BIParent, BB1); 1124193323Sed 1125193323Sed EraseTerminatorInstAndDCECond(BI); 1126193323Sed return true; 1127193323Sed} 1128193323Sed 1129243830Sdim/// SinkThenElseCodeToEnd - Given an unconditional branch that goes to BBEnd, 1130243830Sdim/// check whether BBEnd has only two predecessors and the other predecessor 1131243830Sdim/// ends with an unconditional branch. If it is true, sink any common code 1132243830Sdim/// in the two predecessors to BBEnd. 1133243830Sdimstatic bool SinkThenElseCodeToEnd(BranchInst *BI1) { 1134243830Sdim assert(BI1->isUnconditional()); 1135243830Sdim BasicBlock *BB1 = BI1->getParent(); 1136243830Sdim BasicBlock *BBEnd = BI1->getSuccessor(0); 1137243830Sdim 1138243830Sdim // Check that BBEnd has two predecessors and the other predecessor ends with 1139243830Sdim // an unconditional branch. 1140243830Sdim pred_iterator PI = pred_begin(BBEnd), PE = pred_end(BBEnd); 1141243830Sdim BasicBlock *Pred0 = *PI++; 1142243830Sdim if (PI == PE) // Only one predecessor. 1143243830Sdim return false; 1144243830Sdim BasicBlock *Pred1 = *PI++; 1145243830Sdim if (PI != PE) // More than two predecessors. 1146243830Sdim return false; 1147243830Sdim BasicBlock *BB2 = (Pred0 == BB1) ? Pred1 : Pred0; 1148243830Sdim BranchInst *BI2 = dyn_cast<BranchInst>(BB2->getTerminator()); 1149243830Sdim if (!BI2 || !BI2->isUnconditional()) 1150243830Sdim return false; 1151243830Sdim 1152243830Sdim // Gather the PHI nodes in BBEnd. 1153243830Sdim std::map<Value*, std::pair<Value*, PHINode*> > MapValueFromBB1ToBB2; 1154243830Sdim Instruction *FirstNonPhiInBBEnd = 0; 1155243830Sdim for (BasicBlock::iterator I = BBEnd->begin(), E = BBEnd->end(); 1156243830Sdim I != E; ++I) { 1157243830Sdim if (PHINode *PN = dyn_cast<PHINode>(I)) { 1158243830Sdim Value *BB1V = PN->getIncomingValueForBlock(BB1); 1159249423Sdim Value *BB2V = PN->getIncomingValueForBlock(BB2); 1160243830Sdim MapValueFromBB1ToBB2[BB1V] = std::make_pair(BB2V, PN); 1161243830Sdim } else { 1162243830Sdim FirstNonPhiInBBEnd = &*I; 1163243830Sdim break; 1164243830Sdim } 1165243830Sdim } 1166243830Sdim if (!FirstNonPhiInBBEnd) 1167243830Sdim return false; 1168243830Sdim 1169249423Sdim 1170243830Sdim // This does very trivial matching, with limited scanning, to find identical 1171243830Sdim // instructions in the two blocks. We scan backward for obviously identical 1172243830Sdim // instructions in an identical order. 1173243830Sdim BasicBlock::InstListType::reverse_iterator RI1 = BB1->getInstList().rbegin(), 1174243830Sdim RE1 = BB1->getInstList().rend(), RI2 = BB2->getInstList().rbegin(), 1175243830Sdim RE2 = BB2->getInstList().rend(); 1176243830Sdim // Skip debug info. 1177243830Sdim while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1; 1178243830Sdim if (RI1 == RE1) 1179243830Sdim return false; 1180243830Sdim while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2; 1181243830Sdim if (RI2 == RE2) 1182243830Sdim return false; 1183243830Sdim // Skip the unconditional branches. 1184243830Sdim ++RI1; 1185243830Sdim ++RI2; 1186243830Sdim 1187243830Sdim bool Changed = false; 1188243830Sdim while (RI1 != RE1 && RI2 != RE2) { 1189243830Sdim // Skip debug info. 1190243830Sdim while (RI1 != RE1 && isa<DbgInfoIntrinsic>(&*RI1)) ++RI1; 1191243830Sdim if (RI1 == RE1) 1192243830Sdim return Changed; 1193243830Sdim while (RI2 != RE2 && isa<DbgInfoIntrinsic>(&*RI2)) ++RI2; 1194243830Sdim if (RI2 == RE2) 1195243830Sdim return Changed; 1196243830Sdim 1197243830Sdim Instruction *I1 = &*RI1, *I2 = &*RI2; 1198243830Sdim // I1 and I2 should have a single use in the same PHI node, and they 1199243830Sdim // perform the same operation. 1200243830Sdim // Cannot move control-flow-involving, volatile loads, vaarg, etc. 1201243830Sdim if (isa<PHINode>(I1) || isa<PHINode>(I2) || 1202243830Sdim isa<TerminatorInst>(I1) || isa<TerminatorInst>(I2) || 1203243830Sdim isa<LandingPadInst>(I1) || isa<LandingPadInst>(I2) || 1204243830Sdim isa<AllocaInst>(I1) || isa<AllocaInst>(I2) || 1205243830Sdim I1->mayHaveSideEffects() || I2->mayHaveSideEffects() || 1206243830Sdim I1->mayReadOrWriteMemory() || I2->mayReadOrWriteMemory() || 1207243830Sdim !I1->hasOneUse() || !I2->hasOneUse() || 1208243830Sdim MapValueFromBB1ToBB2.find(I1) == MapValueFromBB1ToBB2.end() || 1209243830Sdim MapValueFromBB1ToBB2[I1].first != I2) 1210243830Sdim return Changed; 1211243830Sdim 1212243830Sdim // Check whether we should swap the operands of ICmpInst. 1213243830Sdim ICmpInst *ICmp1 = dyn_cast<ICmpInst>(I1), *ICmp2 = dyn_cast<ICmpInst>(I2); 1214243830Sdim bool SwapOpnds = false; 1215243830Sdim if (ICmp1 && ICmp2 && 1216243830Sdim ICmp1->getOperand(0) != ICmp2->getOperand(0) && 1217243830Sdim ICmp1->getOperand(1) != ICmp2->getOperand(1) && 1218243830Sdim (ICmp1->getOperand(0) == ICmp2->getOperand(1) || 1219243830Sdim ICmp1->getOperand(1) == ICmp2->getOperand(0))) { 1220243830Sdim ICmp2->swapOperands(); 1221243830Sdim SwapOpnds = true; 1222243830Sdim } 1223243830Sdim if (!I1->isSameOperationAs(I2)) { 1224243830Sdim if (SwapOpnds) 1225243830Sdim ICmp2->swapOperands(); 1226243830Sdim return Changed; 1227243830Sdim } 1228243830Sdim 1229243830Sdim // The operands should be either the same or they need to be generated 1230243830Sdim // with a PHI node after sinking. We only handle the case where there is 1231243830Sdim // a single pair of different operands. 1232243830Sdim Value *DifferentOp1 = 0, *DifferentOp2 = 0; 1233243830Sdim unsigned Op1Idx = 0; 1234243830Sdim for (unsigned I = 0, E = I1->getNumOperands(); I != E; ++I) { 1235243830Sdim if (I1->getOperand(I) == I2->getOperand(I)) 1236243830Sdim continue; 1237243830Sdim // Early exit if we have more-than one pair of different operands or 1238243830Sdim // the different operand is already in MapValueFromBB1ToBB2. 1239243830Sdim // Early exit if we need a PHI node to replace a constant. 1240243830Sdim if (DifferentOp1 || 1241243830Sdim MapValueFromBB1ToBB2.find(I1->getOperand(I)) != 1242243830Sdim MapValueFromBB1ToBB2.end() || 1243243830Sdim isa<Constant>(I1->getOperand(I)) || 1244243830Sdim isa<Constant>(I2->getOperand(I))) { 1245243830Sdim // If we can't sink the instructions, undo the swapping. 1246243830Sdim if (SwapOpnds) 1247243830Sdim ICmp2->swapOperands(); 1248243830Sdim return Changed; 1249243830Sdim } 1250243830Sdim DifferentOp1 = I1->getOperand(I); 1251243830Sdim Op1Idx = I; 1252243830Sdim DifferentOp2 = I2->getOperand(I); 1253243830Sdim } 1254243830Sdim 1255243830Sdim // We insert the pair of different operands to MapValueFromBB1ToBB2 and 1256243830Sdim // remove (I1, I2) from MapValueFromBB1ToBB2. 1257243830Sdim if (DifferentOp1) { 1258243830Sdim PHINode *NewPN = PHINode::Create(DifferentOp1->getType(), 2, 1259243830Sdim DifferentOp1->getName() + ".sink", 1260243830Sdim BBEnd->begin()); 1261243830Sdim MapValueFromBB1ToBB2[DifferentOp1] = std::make_pair(DifferentOp2, NewPN); 1262243830Sdim // I1 should use NewPN instead of DifferentOp1. 1263243830Sdim I1->setOperand(Op1Idx, NewPN); 1264243830Sdim NewPN->addIncoming(DifferentOp1, BB1); 1265243830Sdim NewPN->addIncoming(DifferentOp2, BB2); 1266243830Sdim DEBUG(dbgs() << "Create PHI node " << *NewPN << "\n";); 1267243830Sdim } 1268243830Sdim PHINode *OldPN = MapValueFromBB1ToBB2[I1].second; 1269243830Sdim MapValueFromBB1ToBB2.erase(I1); 1270243830Sdim 1271243830Sdim DEBUG(dbgs() << "SINK common instructions " << *I1 << "\n";); 1272243830Sdim DEBUG(dbgs() << " " << *I2 << "\n";); 1273243830Sdim // We need to update RE1 and RE2 if we are going to sink the first 1274243830Sdim // instruction in the basic block down. 1275243830Sdim bool UpdateRE1 = (I1 == BB1->begin()), UpdateRE2 = (I2 == BB2->begin()); 1276243830Sdim // Sink the instruction. 1277243830Sdim BBEnd->getInstList().splice(FirstNonPhiInBBEnd, BB1->getInstList(), I1); 1278243830Sdim if (!OldPN->use_empty()) 1279243830Sdim OldPN->replaceAllUsesWith(I1); 1280243830Sdim OldPN->eraseFromParent(); 1281243830Sdim 1282243830Sdim if (!I2->use_empty()) 1283243830Sdim I2->replaceAllUsesWith(I1); 1284243830Sdim I1->intersectOptionalDataWith(I2); 1285243830Sdim I2->eraseFromParent(); 1286243830Sdim 1287243830Sdim if (UpdateRE1) 1288243830Sdim RE1 = BB1->getInstList().rend(); 1289243830Sdim if (UpdateRE2) 1290243830Sdim RE2 = BB2->getInstList().rend(); 1291243830Sdim FirstNonPhiInBBEnd = I1; 1292243830Sdim NumSinkCommons++; 1293243830Sdim Changed = true; 1294243830Sdim } 1295243830Sdim return Changed; 1296243830Sdim} 1297243830Sdim 1298251662Sdim/// \brief Determine if we can hoist sink a sole store instruction out of a 1299251662Sdim/// conditional block. 1300251662Sdim/// 1301251662Sdim/// We are looking for code like the following: 1302251662Sdim/// BrBB: 1303251662Sdim/// store i32 %add, i32* %arrayidx2 1304251662Sdim/// ... // No other stores or function calls (we could be calling a memory 1305251662Sdim/// ... // function). 1306251662Sdim/// %cmp = icmp ult %x, %y 1307251662Sdim/// br i1 %cmp, label %EndBB, label %ThenBB 1308251662Sdim/// ThenBB: 1309251662Sdim/// store i32 %add5, i32* %arrayidx2 1310251662Sdim/// br label EndBB 1311251662Sdim/// EndBB: 1312251662Sdim/// ... 1313251662Sdim/// We are going to transform this into: 1314251662Sdim/// BrBB: 1315251662Sdim/// store i32 %add, i32* %arrayidx2 1316251662Sdim/// ... // 1317251662Sdim/// %cmp = icmp ult %x, %y 1318251662Sdim/// %add.add5 = select i1 %cmp, i32 %add, %add5 1319251662Sdim/// store i32 %add.add5, i32* %arrayidx2 1320251662Sdim/// ... 1321251662Sdim/// 1322251662Sdim/// \return The pointer to the value of the previous store if the store can be 1323251662Sdim/// hoisted into the predecessor block. 0 otherwise. 1324263508Sdimstatic Value *isSafeToSpeculateStore(Instruction *I, BasicBlock *BrBB, 1325263508Sdim BasicBlock *StoreBB, BasicBlock *EndBB) { 1326251662Sdim StoreInst *StoreToHoist = dyn_cast<StoreInst>(I); 1327251662Sdim if (!StoreToHoist) 1328251662Sdim return 0; 1329251662Sdim 1330251662Sdim // Volatile or atomic. 1331251662Sdim if (!StoreToHoist->isSimple()) 1332251662Sdim return 0; 1333251662Sdim 1334251662Sdim Value *StorePtr = StoreToHoist->getPointerOperand(); 1335251662Sdim 1336251662Sdim // Look for a store to the same pointer in BrBB. 1337251662Sdim unsigned MaxNumInstToLookAt = 10; 1338251662Sdim for (BasicBlock::reverse_iterator RI = BrBB->rbegin(), 1339251662Sdim RE = BrBB->rend(); RI != RE && (--MaxNumInstToLookAt); ++RI) { 1340251662Sdim Instruction *CurI = &*RI; 1341251662Sdim 1342251662Sdim // Could be calling an instruction that effects memory like free(). 1343251662Sdim if (CurI->mayHaveSideEffects() && !isa<StoreInst>(CurI)) 1344251662Sdim return 0; 1345251662Sdim 1346251662Sdim StoreInst *SI = dyn_cast<StoreInst>(CurI); 1347251662Sdim // Found the previous store make sure it stores to the same location. 1348251662Sdim if (SI && SI->getPointerOperand() == StorePtr) 1349251662Sdim // Found the previous store, return its value operand. 1350251662Sdim return SI->getValueOperand(); 1351251662Sdim else if (SI) 1352251662Sdim return 0; // Unknown store. 1353251662Sdim } 1354251662Sdim 1355251662Sdim return 0; 1356251662Sdim} 1357251662Sdim 1358249423Sdim/// \brief Speculate a conditional basic block flattening the CFG. 1359234353Sdim/// 1360249423Sdim/// Note that this is a very risky transform currently. Speculating 1361249423Sdim/// instructions like this is most often not desirable. Instead, there is an MI 1362249423Sdim/// pass which can do it with full awareness of the resource constraints. 1363249423Sdim/// However, some cases are "obvious" and we should do directly. An example of 1364249423Sdim/// this is speculating a single, reasonably cheap instruction. 1365249423Sdim/// 1366249423Sdim/// There is only one distinct advantage to flattening the CFG at the IR level: 1367249423Sdim/// it makes very common but simplistic optimizations such as are common in 1368249423Sdim/// instcombine and the DAG combiner more powerful by removing CFG edges and 1369249423Sdim/// modeling their effects with easier to reason about SSA value graphs. 1370249423Sdim/// 1371249423Sdim/// 1372249423Sdim/// An illustration of this transform is turning this IR: 1373249423Sdim/// \code 1374249423Sdim/// BB: 1375249423Sdim/// %cmp = icmp ult %x, %y 1376249423Sdim/// br i1 %cmp, label %EndBB, label %ThenBB 1377249423Sdim/// ThenBB: 1378249423Sdim/// %sub = sub %x, %y 1379234353Sdim/// br label BB2 1380249423Sdim/// EndBB: 1381249423Sdim/// %phi = phi [ %sub, %ThenBB ], [ 0, %EndBB ] 1382249423Sdim/// ... 1383249423Sdim/// \endcode 1384249423Sdim/// 1385249423Sdim/// Into this IR: 1386249423Sdim/// \code 1387249423Sdim/// BB: 1388249423Sdim/// %cmp = icmp ult %x, %y 1389249423Sdim/// %sub = sub %x, %y 1390249423Sdim/// %cond = select i1 %cmp, 0, %sub 1391249423Sdim/// ... 1392249423Sdim/// \endcode 1393249423Sdim/// 1394249423Sdim/// \returns true if the conditional block is removed. 1395249423Sdimstatic bool SpeculativelyExecuteBB(BranchInst *BI, BasicBlock *ThenBB) { 1396249423Sdim // Be conservative for now. FP select instruction can often be expensive. 1397249423Sdim Value *BrCond = BI->getCondition(); 1398249423Sdim if (isa<FCmpInst>(BrCond)) 1399249423Sdim return false; 1400249423Sdim 1401249423Sdim BasicBlock *BB = BI->getParent(); 1402249423Sdim BasicBlock *EndBB = ThenBB->getTerminator()->getSuccessor(0); 1403249423Sdim 1404249423Sdim // If ThenBB is actually on the false edge of the conditional branch, remember 1405249423Sdim // to swap the select operands later. 1406249423Sdim bool Invert = false; 1407249423Sdim if (ThenBB != BI->getSuccessor(0)) { 1408249423Sdim assert(ThenBB == BI->getSuccessor(1) && "No edge from 'if' block?"); 1409249423Sdim Invert = true; 1410249423Sdim } 1411249423Sdim assert(EndBB == BI->getSuccessor(!Invert) && "No edge from to end block"); 1412249423Sdim 1413249423Sdim // Keep a count of how many times instructions are used within CondBB when 1414249423Sdim // they are candidates for sinking into CondBB. Specifically: 1415249423Sdim // - They are defined in BB, and 1416249423Sdim // - They have no side effects, and 1417249423Sdim // - All of their uses are in CondBB. 1418249423Sdim SmallDenseMap<Instruction *, unsigned, 4> SinkCandidateUseCounts; 1419249423Sdim 1420249423Sdim unsigned SpeculationCost = 0; 1421251662Sdim Value *SpeculatedStoreValue = 0; 1422251662Sdim StoreInst *SpeculatedStore = 0; 1423249423Sdim for (BasicBlock::iterator BBI = ThenBB->begin(), 1424249423Sdim BBE = llvm::prior(ThenBB->end()); 1425193323Sed BBI != BBE; ++BBI) { 1426193323Sed Instruction *I = BBI; 1427193323Sed // Skip debug info. 1428249423Sdim if (isa<DbgInfoIntrinsic>(I)) 1429249423Sdim continue; 1430193323Sed 1431249423Sdim // Only speculatively execution a single instruction (not counting the 1432249423Sdim // terminator) for now. 1433249423Sdim ++SpeculationCost; 1434249423Sdim if (SpeculationCost > 1) 1435193323Sed return false; 1436193323Sed 1437234353Sdim // Don't hoist the instruction if it's unsafe or expensive. 1438251662Sdim if (!isSafeToSpeculativelyExecute(I) && 1439251662Sdim !(HoistCondStores && 1440251662Sdim (SpeculatedStoreValue = isSafeToSpeculateStore(I, BB, ThenBB, 1441251662Sdim EndBB)))) 1442234353Sdim return false; 1443251662Sdim if (!SpeculatedStoreValue && 1444251662Sdim ComputeSpeculationCost(I) > PHINodeFoldingThreshold) 1445234353Sdim return false; 1446234353Sdim 1447251662Sdim // Store the store speculation candidate. 1448251662Sdim if (SpeculatedStoreValue) 1449251662Sdim SpeculatedStore = cast<StoreInst>(I); 1450251662Sdim 1451234353Sdim // Do not hoist the instruction if any of its operands are defined but not 1452251662Sdim // used in BB. The transformation will prevent the operand from 1453234353Sdim // being sunk into the use block. 1454249423Sdim for (User::op_iterator i = I->op_begin(), e = I->op_end(); 1455234353Sdim i != e; ++i) { 1456234353Sdim Instruction *OpI = dyn_cast<Instruction>(*i); 1457249423Sdim if (!OpI || OpI->getParent() != BB || 1458249423Sdim OpI->mayHaveSideEffects()) 1459249423Sdim continue; // Not a candidate for sinking. 1460249423Sdim 1461249423Sdim ++SinkCandidateUseCounts[OpI]; 1462234353Sdim } 1463234353Sdim } 1464234353Sdim 1465249423Sdim // Consider any sink candidates which are only used in CondBB as costs for 1466249423Sdim // speculation. Note, while we iterate over a DenseMap here, we are summing 1467249423Sdim // and so iteration order isn't significant. 1468249423Sdim for (SmallDenseMap<Instruction *, unsigned, 4>::iterator I = 1469249423Sdim SinkCandidateUseCounts.begin(), E = SinkCandidateUseCounts.end(); 1470249423Sdim I != E; ++I) 1471249423Sdim if (I->first->getNumUses() == I->second) { 1472249423Sdim ++SpeculationCost; 1473249423Sdim if (SpeculationCost > 1) 1474249423Sdim return false; 1475249423Sdim } 1476193323Sed 1477249423Sdim // Check that the PHI nodes can be converted to selects. 1478249423Sdim bool HaveRewritablePHIs = false; 1479249423Sdim for (BasicBlock::iterator I = EndBB->begin(); 1480234353Sdim PHINode *PN = dyn_cast<PHINode>(I); ++I) { 1481249423Sdim Value *OrigV = PN->getIncomingValueForBlock(BB); 1482249423Sdim Value *ThenV = PN->getIncomingValueForBlock(ThenBB); 1483234353Sdim 1484263508Sdim // FIXME: Try to remove some of the duplication with HoistThenElseCodeToIf. 1485234353Sdim // Skip PHIs which are trivial. 1486249423Sdim if (ThenV == OrigV) 1487234353Sdim continue; 1488234353Sdim 1489249423Sdim HaveRewritablePHIs = true; 1490263508Sdim ConstantExpr *OrigCE = dyn_cast<ConstantExpr>(OrigV); 1491263508Sdim ConstantExpr *ThenCE = dyn_cast<ConstantExpr>(ThenV); 1492263508Sdim if (!OrigCE && !ThenCE) 1493249423Sdim continue; // Known safe and cheap. 1494234353Sdim 1495263508Sdim if ((ThenCE && !isSafeToSpeculativelyExecute(ThenCE)) || 1496263508Sdim (OrigCE && !isSafeToSpeculativelyExecute(OrigCE))) 1497249423Sdim return false; 1498263508Sdim unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE) : 0; 1499263508Sdim unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE) : 0; 1500263508Sdim if (OrigCost + ThenCost > 2 * PHINodeFoldingThreshold) 1501249423Sdim return false; 1502249423Sdim 1503249423Sdim // Account for the cost of an unfolded ConstantExpr which could end up 1504249423Sdim // getting expanded into Instructions. 1505249423Sdim // FIXME: This doesn't account for how many operations are combined in the 1506249423Sdim // constant expression. 1507249423Sdim ++SpeculationCost; 1508249423Sdim if (SpeculationCost > 1) 1509249423Sdim return false; 1510193323Sed } 1511193323Sed 1512234353Sdim // If there are no PHIs to process, bail early. This helps ensure idempotence 1513234353Sdim // as well. 1514251662Sdim if (!HaveRewritablePHIs && !(HoistCondStores && SpeculatedStoreValue)) 1515234353Sdim return false; 1516243830Sdim 1517234353Sdim // If we get here, we can hoist the instruction and if-convert. 1518249423Sdim DEBUG(dbgs() << "SPECULATIVELY EXECUTING BB" << *ThenBB << "\n";); 1519193323Sed 1520251662Sdim // Insert a select of the value of the speculated store. 1521251662Sdim if (SpeculatedStoreValue) { 1522251662Sdim IRBuilder<true, NoFolder> Builder(BI); 1523251662Sdim Value *TrueV = SpeculatedStore->getValueOperand(); 1524251662Sdim Value *FalseV = SpeculatedStoreValue; 1525251662Sdim if (Invert) 1526251662Sdim std::swap(TrueV, FalseV); 1527251662Sdim Value *S = Builder.CreateSelect(BrCond, TrueV, FalseV, TrueV->getName() + 1528251662Sdim "." + FalseV->getName()); 1529251662Sdim SpeculatedStore->setOperand(0, S); 1530251662Sdim } 1531251662Sdim 1532249423Sdim // Hoist the instructions. 1533249423Sdim BB->getInstList().splice(BI, ThenBB->getInstList(), ThenBB->begin(), 1534249423Sdim llvm::prior(ThenBB->end())); 1535193323Sed 1536234353Sdim // Insert selects and rewrite the PHI operands. 1537223017Sdim IRBuilder<true, NoFolder> Builder(BI); 1538249423Sdim for (BasicBlock::iterator I = EndBB->begin(); 1539249423Sdim PHINode *PN = dyn_cast<PHINode>(I); ++I) { 1540249423Sdim unsigned OrigI = PN->getBasicBlockIndex(BB); 1541249423Sdim unsigned ThenI = PN->getBasicBlockIndex(ThenBB); 1542249423Sdim Value *OrigV = PN->getIncomingValue(OrigI); 1543249423Sdim Value *ThenV = PN->getIncomingValue(ThenI); 1544193323Sed 1545249423Sdim // Skip PHIs which are trivial. 1546249423Sdim if (OrigV == ThenV) 1547249423Sdim continue; 1548249423Sdim 1549234353Sdim // Create a select whose true value is the speculatively executed value and 1550249423Sdim // false value is the preexisting value. Swap them if the branch 1551249423Sdim // destinations were inverted. 1552249423Sdim Value *TrueV = ThenV, *FalseV = OrigV; 1553234353Sdim if (Invert) 1554249423Sdim std::swap(TrueV, FalseV); 1555249423Sdim Value *V = Builder.CreateSelect(BrCond, TrueV, FalseV, 1556249423Sdim TrueV->getName() + "." + FalseV->getName()); 1557249423Sdim PN->setIncomingValue(OrigI, V); 1558249423Sdim PN->setIncomingValue(ThenI, V); 1559193323Sed } 1560193323Sed 1561193323Sed ++NumSpeculations; 1562193323Sed return true; 1563193323Sed} 1564193323Sed 1565263508Sdim/// \returns True if this block contains a CallInst with the NoDuplicate 1566263508Sdim/// attribute. 1567263508Sdimstatic bool HasNoDuplicateCall(const BasicBlock *BB) { 1568263508Sdim for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 1569263508Sdim const CallInst *CI = dyn_cast<CallInst>(I); 1570263508Sdim if (!CI) 1571263508Sdim continue; 1572263508Sdim if (CI->cannotDuplicate()) 1573263508Sdim return true; 1574263508Sdim } 1575263508Sdim return false; 1576263508Sdim} 1577263508Sdim 1578193323Sed/// BlockIsSimpleEnoughToThreadThrough - Return true if we can thread a branch 1579193323Sed/// across this block. 1580193323Sedstatic bool BlockIsSimpleEnoughToThreadThrough(BasicBlock *BB) { 1581193323Sed BranchInst *BI = cast<BranchInst>(BB->getTerminator()); 1582193323Sed unsigned Size = 0; 1583243830Sdim 1584193323Sed for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1585193323Sed if (isa<DbgInfoIntrinsic>(BBI)) 1586193323Sed continue; 1587193323Sed if (Size > 10) return false; // Don't clone large BB's. 1588193323Sed ++Size; 1589243830Sdim 1590193323Sed // We can only support instructions that do not define values that are 1591193323Sed // live outside of the current basic block. 1592193323Sed for (Value::use_iterator UI = BBI->use_begin(), E = BBI->use_end(); 1593193323Sed UI != E; ++UI) { 1594193323Sed Instruction *U = cast<Instruction>(*UI); 1595193323Sed if (U->getParent() != BB || isa<PHINode>(U)) return false; 1596193323Sed } 1597243830Sdim 1598193323Sed // Looks ok, continue checking. 1599193323Sed } 1600193323Sed 1601193323Sed return true; 1602193323Sed} 1603193323Sed 1604193323Sed/// FoldCondBranchOnPHI - If we have a conditional branch on a PHI node value 1605193323Sed/// that is defined in the same block as the branch and if any PHI entries are 1606193323Sed/// constants, thread edges corresponding to that entry to be branches to their 1607193323Sed/// ultimate destination. 1608243830Sdimstatic bool FoldCondBranchOnPHI(BranchInst *BI, const DataLayout *TD) { 1609193323Sed BasicBlock *BB = BI->getParent(); 1610193323Sed PHINode *PN = dyn_cast<PHINode>(BI->getCondition()); 1611193323Sed // NOTE: we currently cannot transform this case if the PHI node is used 1612193323Sed // outside of the block. 1613193323Sed if (!PN || PN->getParent() != BB || !PN->hasOneUse()) 1614193323Sed return false; 1615243830Sdim 1616193323Sed // Degenerate case of a single entry PHI. 1617193323Sed if (PN->getNumIncomingValues() == 1) { 1618193323Sed FoldSingleEntryPHINodes(PN->getParent()); 1619243830Sdim return true; 1620193323Sed } 1621193323Sed 1622193323Sed // Now we know that this block has multiple preds and two succs. 1623193323Sed if (!BlockIsSimpleEnoughToThreadThrough(BB)) return false; 1624243830Sdim 1625263508Sdim if (HasNoDuplicateCall(BB)) return false; 1626263508Sdim 1627193323Sed // Okay, this is a simple enough basic block. See if any phi values are 1628193323Sed // constants. 1629193323Sed for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 1630218893Sdim ConstantInt *CB = dyn_cast<ConstantInt>(PN->getIncomingValue(i)); 1631218893Sdim if (CB == 0 || !CB->getType()->isIntegerTy(1)) continue; 1632243830Sdim 1633218893Sdim // Okay, we now know that all edges from PredBB should be revectored to 1634218893Sdim // branch to RealDest. 1635218893Sdim BasicBlock *PredBB = PN->getIncomingBlock(i); 1636218893Sdim BasicBlock *RealDest = BI->getSuccessor(!CB->getZExtValue()); 1637243830Sdim 1638218893Sdim if (RealDest == BB) continue; // Skip self loops. 1639223017Sdim // Skip if the predecessor's terminator is an indirect branch. 1640223017Sdim if (isa<IndirectBrInst>(PredBB->getTerminator())) continue; 1641243830Sdim 1642218893Sdim // The dest block might have PHI nodes, other predecessors and other 1643218893Sdim // difficult cases. Instead of being smart about this, just insert a new 1644218893Sdim // block that jumps to the destination block, effectively splitting 1645218893Sdim // the edge we are about to create. 1646218893Sdim BasicBlock *EdgeBB = BasicBlock::Create(BB->getContext(), 1647218893Sdim RealDest->getName()+".critedge", 1648218893Sdim RealDest->getParent(), RealDest); 1649218893Sdim BranchInst::Create(RealDest, EdgeBB); 1650243830Sdim 1651218893Sdim // Update PHI nodes. 1652218893Sdim AddPredecessorToBlock(RealDest, EdgeBB, BB); 1653218893Sdim 1654218893Sdim // BB may have instructions that are being threaded over. Clone these 1655218893Sdim // instructions into EdgeBB. We know that there will be no uses of the 1656218893Sdim // cloned instructions outside of EdgeBB. 1657218893Sdim BasicBlock::iterator InsertPt = EdgeBB->begin(); 1658218893Sdim DenseMap<Value*, Value*> TranslateMap; // Track translated values. 1659218893Sdim for (BasicBlock::iterator BBI = BB->begin(); &*BBI != BI; ++BBI) { 1660218893Sdim if (PHINode *PN = dyn_cast<PHINode>(BBI)) { 1661218893Sdim TranslateMap[PN] = PN->getIncomingValueForBlock(PredBB); 1662218893Sdim continue; 1663218893Sdim } 1664218893Sdim // Clone the instruction. 1665218893Sdim Instruction *N = BBI->clone(); 1666218893Sdim if (BBI->hasName()) N->setName(BBI->getName()+".c"); 1667243830Sdim 1668218893Sdim // Update operands due to translation. 1669218893Sdim for (User::op_iterator i = N->op_begin(), e = N->op_end(); 1670218893Sdim i != e; ++i) { 1671218893Sdim DenseMap<Value*, Value*>::iterator PI = TranslateMap.find(*i); 1672218893Sdim if (PI != TranslateMap.end()) 1673218893Sdim *i = PI->second; 1674218893Sdim } 1675243830Sdim 1676218893Sdim // Check for trivial simplification. 1677218893Sdim if (Value *V = SimplifyInstruction(N, TD)) { 1678218893Sdim TranslateMap[BBI] = V; 1679218893Sdim delete N; // Instruction folded away, don't need actual inst 1680218893Sdim } else { 1681218893Sdim // Insert the new instruction into its new home. 1682218893Sdim EdgeBB->getInstList().insert(InsertPt, N); 1683218893Sdim if (!BBI->use_empty()) 1684218893Sdim TranslateMap[BBI] = N; 1685193323Sed } 1686218893Sdim } 1687193323Sed 1688218893Sdim // Loop over all of the edges from PredBB to BB, changing them to branch 1689218893Sdim // to EdgeBB instead. 1690218893Sdim TerminatorInst *PredBBTI = PredBB->getTerminator(); 1691218893Sdim for (unsigned i = 0, e = PredBBTI->getNumSuccessors(); i != e; ++i) 1692218893Sdim if (PredBBTI->getSuccessor(i) == BB) { 1693218893Sdim BB->removePredecessor(PredBB); 1694218893Sdim PredBBTI->setSuccessor(i, EdgeBB); 1695193323Sed } 1696223017Sdim 1697218893Sdim // Recurse, simplifying any other constants. 1698218893Sdim return FoldCondBranchOnPHI(BI, TD) | true; 1699193323Sed } 1700193323Sed 1701193323Sed return false; 1702193323Sed} 1703193323Sed 1704193323Sed/// FoldTwoEntryPHINode - Given a BB that starts with the specified two-entry 1705193323Sed/// PHI node, see if we can eliminate it. 1706243830Sdimstatic bool FoldTwoEntryPHINode(PHINode *PN, const DataLayout *TD) { 1707193323Sed // Ok, this is a two entry PHI node. Check to see if this is a simple "if 1708193323Sed // statement", which has a very simple dominance structure. Basically, we 1709193323Sed // are trying to find the condition that is being branched on, which 1710193323Sed // subsequently causes this merge to happen. We really want control 1711193323Sed // dependence information for this check, but simplifycfg can't keep it up 1712193323Sed // to date, and this catches most of the cases we care about anyway. 1713193323Sed BasicBlock *BB = PN->getParent(); 1714193323Sed BasicBlock *IfTrue, *IfFalse; 1715193323Sed Value *IfCond = GetIfCondition(BB, IfTrue, IfFalse); 1716218893Sdim if (!IfCond || 1717218893Sdim // Don't bother if the branch will be constant folded trivially. 1718218893Sdim isa<ConstantInt>(IfCond)) 1719218893Sdim return false; 1720243830Sdim 1721193323Sed // Okay, we found that we can merge this two-entry phi node into a select. 1722193323Sed // Doing so would require us to fold *all* two entry phi nodes in this block. 1723193323Sed // At some point this becomes non-profitable (particularly if the target 1724193323Sed // doesn't support cmov's). Only do this transformation if there are two or 1725193323Sed // fewer PHI nodes in this block. 1726193323Sed unsigned NumPhis = 0; 1727193323Sed for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++NumPhis, ++I) 1728193323Sed if (NumPhis > 2) 1729193323Sed return false; 1730243830Sdim 1731193323Sed // Loop over the PHI's seeing if we can promote them all to select 1732193323Sed // instructions. While we are at it, keep track of the instructions 1733193323Sed // that need to be moved to the dominating block. 1734218893Sdim SmallPtrSet<Instruction*, 4> AggressiveInsts; 1735221345Sdim unsigned MaxCostVal0 = PHINodeFoldingThreshold, 1736221345Sdim MaxCostVal1 = PHINodeFoldingThreshold; 1737243830Sdim 1738218893Sdim for (BasicBlock::iterator II = BB->begin(); isa<PHINode>(II);) { 1739218893Sdim PHINode *PN = cast<PHINode>(II++); 1740218893Sdim if (Value *V = SimplifyInstruction(PN, TD)) { 1741218893Sdim PN->replaceAllUsesWith(V); 1742218893Sdim PN->eraseFromParent(); 1743218893Sdim continue; 1744218893Sdim } 1745243830Sdim 1746221345Sdim if (!DominatesMergePoint(PN->getIncomingValue(0), BB, &AggressiveInsts, 1747221345Sdim MaxCostVal0) || 1748221345Sdim !DominatesMergePoint(PN->getIncomingValue(1), BB, &AggressiveInsts, 1749221345Sdim MaxCostVal1)) 1750193323Sed return false; 1751193323Sed } 1752243830Sdim 1753239462Sdim // If we folded the first phi, PN dangles at this point. Refresh it. If 1754218893Sdim // we ran out of PHIs then we simplified them all. 1755218893Sdim PN = dyn_cast<PHINode>(BB->begin()); 1756218893Sdim if (PN == 0) return true; 1757243830Sdim 1758218893Sdim // Don't fold i1 branches on PHIs which contain binary operators. These can 1759218893Sdim // often be turned into switches and other things. 1760218893Sdim if (PN->getType()->isIntegerTy(1) && 1761218893Sdim (isa<BinaryOperator>(PN->getIncomingValue(0)) || 1762218893Sdim isa<BinaryOperator>(PN->getIncomingValue(1)) || 1763218893Sdim isa<BinaryOperator>(IfCond))) 1764218893Sdim return false; 1765243830Sdim 1766193323Sed // If we all PHI nodes are promotable, check to make sure that all 1767193323Sed // instructions in the predecessor blocks can be promoted as well. If 1768193323Sed // not, we won't be able to get rid of the control flow, so it's not 1769193323Sed // worth promoting to select instructions. 1770218893Sdim BasicBlock *DomBlock = 0; 1771218893Sdim BasicBlock *IfBlock1 = PN->getIncomingBlock(0); 1772218893Sdim BasicBlock *IfBlock2 = PN->getIncomingBlock(1); 1773218893Sdim if (cast<BranchInst>(IfBlock1->getTerminator())->isConditional()) { 1774218893Sdim IfBlock1 = 0; 1775218893Sdim } else { 1776218893Sdim DomBlock = *pred_begin(IfBlock1); 1777218893Sdim for (BasicBlock::iterator I = IfBlock1->begin();!isa<TerminatorInst>(I);++I) 1778193323Sed if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1779193323Sed // This is not an aggressive instruction that we can promote. 1780193323Sed // Because of this, we won't be able to get rid of the control 1781193323Sed // flow, so the xform is not worth it. 1782193323Sed return false; 1783193323Sed } 1784193323Sed } 1785243830Sdim 1786218893Sdim if (cast<BranchInst>(IfBlock2->getTerminator())->isConditional()) { 1787218893Sdim IfBlock2 = 0; 1788218893Sdim } else { 1789218893Sdim DomBlock = *pred_begin(IfBlock2); 1790218893Sdim for (BasicBlock::iterator I = IfBlock2->begin();!isa<TerminatorInst>(I);++I) 1791193323Sed if (!AggressiveInsts.count(I) && !isa<DbgInfoIntrinsic>(I)) { 1792193323Sed // This is not an aggressive instruction that we can promote. 1793193323Sed // Because of this, we won't be able to get rid of the control 1794193323Sed // flow, so the xform is not worth it. 1795193323Sed return false; 1796193323Sed } 1797193323Sed } 1798243830Sdim 1799218893Sdim DEBUG(dbgs() << "FOUND IF CONDITION! " << *IfCond << " T: " 1800218893Sdim << IfTrue->getName() << " F: " << IfFalse->getName() << "\n"); 1801243830Sdim 1802193323Sed // If we can still promote the PHI nodes after this gauntlet of tests, 1803193323Sed // do all of the PHI's now. 1804218893Sdim Instruction *InsertPt = DomBlock->getTerminator(); 1805223017Sdim IRBuilder<true, NoFolder> Builder(InsertPt); 1806243830Sdim 1807193323Sed // Move all 'aggressive' instructions, which are defined in the 1808193323Sed // conditional parts of the if's up to the dominating block. 1809218893Sdim if (IfBlock1) 1810218893Sdim DomBlock->getInstList().splice(InsertPt, 1811218893Sdim IfBlock1->getInstList(), IfBlock1->begin(), 1812193323Sed IfBlock1->getTerminator()); 1813218893Sdim if (IfBlock2) 1814218893Sdim DomBlock->getInstList().splice(InsertPt, 1815218893Sdim IfBlock2->getInstList(), IfBlock2->begin(), 1816193323Sed IfBlock2->getTerminator()); 1817243830Sdim 1818193323Sed while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) { 1819193323Sed // Change the PHI node into a select instruction. 1820218893Sdim Value *TrueVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfFalse); 1821218893Sdim Value *FalseVal = PN->getIncomingValue(PN->getIncomingBlock(0) == IfTrue); 1822243830Sdim 1823243830Sdim SelectInst *NV = 1824223017Sdim cast<SelectInst>(Builder.CreateSelect(IfCond, TrueVal, FalseVal, "")); 1825193323Sed PN->replaceAllUsesWith(NV); 1826193323Sed NV->takeName(PN); 1827218893Sdim PN->eraseFromParent(); 1828193323Sed } 1829243830Sdim 1830218893Sdim // At this point, IfBlock1 and IfBlock2 are both empty, so our if statement 1831218893Sdim // has been flattened. Change DomBlock to jump directly to our new block to 1832218893Sdim // avoid other simplifycfg's kicking in on the diamond. 1833218893Sdim TerminatorInst *OldTI = DomBlock->getTerminator(); 1834223017Sdim Builder.SetInsertPoint(OldTI); 1835223017Sdim Builder.CreateBr(BB); 1836218893Sdim OldTI->eraseFromParent(); 1837193323Sed return true; 1838193323Sed} 1839193323Sed 1840193323Sed/// SimplifyCondBranchToTwoReturns - If we found a conditional branch that goes 1841193323Sed/// to two returning blocks, try to merge them together into one return, 1842193323Sed/// introducing a select if the return values disagree. 1843243830Sdimstatic bool SimplifyCondBranchToTwoReturns(BranchInst *BI, 1844223017Sdim IRBuilder<> &Builder) { 1845193323Sed assert(BI->isConditional() && "Must be a conditional branch"); 1846193323Sed BasicBlock *TrueSucc = BI->getSuccessor(0); 1847193323Sed BasicBlock *FalseSucc = BI->getSuccessor(1); 1848193323Sed ReturnInst *TrueRet = cast<ReturnInst>(TrueSucc->getTerminator()); 1849193323Sed ReturnInst *FalseRet = cast<ReturnInst>(FalseSucc->getTerminator()); 1850243830Sdim 1851193323Sed // Check to ensure both blocks are empty (just a return) or optionally empty 1852193323Sed // with PHI nodes. If there are other instructions, merging would cause extra 1853193323Sed // computation on one path or the other. 1854218893Sdim if (!TrueSucc->getFirstNonPHIOrDbg()->isTerminator()) 1855193323Sed return false; 1856218893Sdim if (!FalseSucc->getFirstNonPHIOrDbg()->isTerminator()) 1857193323Sed return false; 1858193323Sed 1859223017Sdim Builder.SetInsertPoint(BI); 1860193323Sed // Okay, we found a branch that is going to two return nodes. If 1861193323Sed // there is no return value for this function, just change the 1862193323Sed // branch into a return. 1863193323Sed if (FalseRet->getNumOperands() == 0) { 1864193323Sed TrueSucc->removePredecessor(BI->getParent()); 1865193323Sed FalseSucc->removePredecessor(BI->getParent()); 1866223017Sdim Builder.CreateRetVoid(); 1867193323Sed EraseTerminatorInstAndDCECond(BI); 1868193323Sed return true; 1869193323Sed } 1870243830Sdim 1871193323Sed // Otherwise, figure out what the true and false return values are 1872193323Sed // so we can insert a new select instruction. 1873193323Sed Value *TrueValue = TrueRet->getReturnValue(); 1874193323Sed Value *FalseValue = FalseRet->getReturnValue(); 1875243830Sdim 1876193323Sed // Unwrap any PHI nodes in the return blocks. 1877193323Sed if (PHINode *TVPN = dyn_cast_or_null<PHINode>(TrueValue)) 1878193323Sed if (TVPN->getParent() == TrueSucc) 1879193323Sed TrueValue = TVPN->getIncomingValueForBlock(BI->getParent()); 1880193323Sed if (PHINode *FVPN = dyn_cast_or_null<PHINode>(FalseValue)) 1881193323Sed if (FVPN->getParent() == FalseSucc) 1882193323Sed FalseValue = FVPN->getIncomingValueForBlock(BI->getParent()); 1883243830Sdim 1884193323Sed // In order for this transformation to be safe, we must be able to 1885193323Sed // unconditionally execute both operands to the return. This is 1886193323Sed // normally the case, but we could have a potentially-trapping 1887193323Sed // constant expression that prevents this transformation from being 1888193323Sed // safe. 1889193323Sed if (ConstantExpr *TCV = dyn_cast_or_null<ConstantExpr>(TrueValue)) 1890193323Sed if (TCV->canTrap()) 1891193323Sed return false; 1892193323Sed if (ConstantExpr *FCV = dyn_cast_or_null<ConstantExpr>(FalseValue)) 1893193323Sed if (FCV->canTrap()) 1894193323Sed return false; 1895243830Sdim 1896193323Sed // Okay, we collected all the mapped values and checked them for sanity, and 1897193323Sed // defined to really do this transformation. First, update the CFG. 1898193323Sed TrueSucc->removePredecessor(BI->getParent()); 1899193323Sed FalseSucc->removePredecessor(BI->getParent()); 1900243830Sdim 1901193323Sed // Insert select instructions where needed. 1902193323Sed Value *BrCond = BI->getCondition(); 1903193323Sed if (TrueValue) { 1904193323Sed // Insert a select if the results differ. 1905193323Sed if (TrueValue == FalseValue || isa<UndefValue>(FalseValue)) { 1906193323Sed } else if (isa<UndefValue>(TrueValue)) { 1907193323Sed TrueValue = FalseValue; 1908193323Sed } else { 1909223017Sdim TrueValue = Builder.CreateSelect(BrCond, TrueValue, 1910223017Sdim FalseValue, "retval"); 1911193323Sed } 1912193323Sed } 1913193323Sed 1914243830Sdim Value *RI = !TrueValue ? 1915223017Sdim Builder.CreateRetVoid() : Builder.CreateRet(TrueValue); 1916223017Sdim 1917198090Srdivacky (void) RI; 1918243830Sdim 1919202375Srdivacky DEBUG(dbgs() << "\nCHANGING BRANCH TO TWO RETURNS INTO SELECT:" 1920198090Srdivacky << "\n " << *BI << "NewRet = " << *RI 1921198090Srdivacky << "TRUEBLOCK: " << *TrueSucc << "FALSEBLOCK: "<< *FalseSucc); 1922243830Sdim 1923193323Sed EraseTerminatorInstAndDCECond(BI); 1924193323Sed 1925193323Sed return true; 1926193323Sed} 1927193323Sed 1928234353Sdim/// ExtractBranchMetadata - Given a conditional BranchInstruction, retrieve the 1929234353Sdim/// probabilities of the branch taking each edge. Fills in the two APInt 1930234353Sdim/// parameters and return true, or returns false if no or invalid metadata was 1931234353Sdim/// found. 1932234353Sdimstatic bool ExtractBranchMetadata(BranchInst *BI, 1933243830Sdim uint64_t &ProbTrue, uint64_t &ProbFalse) { 1934234353Sdim assert(BI->isConditional() && 1935234353Sdim "Looking for probabilities on unconditional branch?"); 1936234353Sdim MDNode *ProfileData = BI->getMetadata(LLVMContext::MD_prof); 1937234353Sdim if (!ProfileData || ProfileData->getNumOperands() != 3) return false; 1938234353Sdim ConstantInt *CITrue = dyn_cast<ConstantInt>(ProfileData->getOperand(1)); 1939234353Sdim ConstantInt *CIFalse = dyn_cast<ConstantInt>(ProfileData->getOperand(2)); 1940234353Sdim if (!CITrue || !CIFalse) return false; 1941243830Sdim ProbTrue = CITrue->getValue().getZExtValue(); 1942243830Sdim ProbFalse = CIFalse->getValue().getZExtValue(); 1943234353Sdim return true; 1944234353Sdim} 1945234353Sdim 1946239462Sdim/// checkCSEInPredecessor - Return true if the given instruction is available 1947239462Sdim/// in its predecessor block. If yes, the instruction will be removed. 1948239462Sdim/// 1949239462Sdimstatic bool checkCSEInPredecessor(Instruction *Inst, BasicBlock *PB) { 1950239462Sdim if (!isa<BinaryOperator>(Inst) && !isa<CmpInst>(Inst)) 1951239462Sdim return false; 1952239462Sdim for (BasicBlock::iterator I = PB->begin(), E = PB->end(); I != E; I++) { 1953239462Sdim Instruction *PBI = &*I; 1954239462Sdim // Check whether Inst and PBI generate the same value. 1955239462Sdim if (Inst->isIdenticalTo(PBI)) { 1956239462Sdim Inst->replaceAllUsesWith(PBI); 1957239462Sdim Inst->eraseFromParent(); 1958239462Sdim return true; 1959239462Sdim } 1960239462Sdim } 1961239462Sdim return false; 1962239462Sdim} 1963234353Sdim 1964221345Sdim/// FoldBranchToCommonDest - If this basic block is simple enough, and if a 1965221345Sdim/// predecessor branches to us and one of our successors, fold the block into 1966221345Sdim/// the predecessor and use logical operations to pick the right destination. 1967195340Sedbool llvm::FoldBranchToCommonDest(BranchInst *BI) { 1968193323Sed BasicBlock *BB = BI->getParent(); 1969223017Sdim 1970239462Sdim Instruction *Cond = 0; 1971239462Sdim if (BI->isConditional()) 1972239462Sdim Cond = dyn_cast<Instruction>(BI->getCondition()); 1973239462Sdim else { 1974239462Sdim // For unconditional branch, check for a simple CFG pattern, where 1975239462Sdim // BB has a single predecessor and BB's successor is also its predecessor's 1976239462Sdim // successor. If such pattern exisits, check for CSE between BB and its 1977239462Sdim // predecessor. 1978239462Sdim if (BasicBlock *PB = BB->getSinglePredecessor()) 1979239462Sdim if (BranchInst *PBI = dyn_cast<BranchInst>(PB->getTerminator())) 1980239462Sdim if (PBI->isConditional() && 1981239462Sdim (BI->getSuccessor(0) == PBI->getSuccessor(0) || 1982239462Sdim BI->getSuccessor(0) == PBI->getSuccessor(1))) { 1983239462Sdim for (BasicBlock::iterator I = BB->begin(), E = BB->end(); 1984239462Sdim I != E; ) { 1985239462Sdim Instruction *Curr = I++; 1986239462Sdim if (isa<CmpInst>(Curr)) { 1987239462Sdim Cond = Curr; 1988239462Sdim break; 1989239462Sdim } 1990239462Sdim // Quit if we can't remove this instruction. 1991239462Sdim if (!checkCSEInPredecessor(Curr, PB)) 1992239462Sdim return false; 1993239462Sdim } 1994239462Sdim } 1995239462Sdim 1996239462Sdim if (Cond == 0) 1997239462Sdim return false; 1998239462Sdim } 1999243830Sdim 2000210299Sed if (Cond == 0 || (!isa<CmpInst>(Cond) && !isa<BinaryOperator>(Cond)) || 2001210299Sed Cond->getParent() != BB || !Cond->hasOneUse()) 2002210299Sed return false; 2003221345Sdim 2004193323Sed // Only allow this if the condition is a simple instruction that can be 2005193323Sed // executed unconditionally. It must be in the same block as the branch, and 2006193323Sed // must be at the front of the block. 2007193323Sed BasicBlock::iterator FrontIt = BB->front(); 2008221345Sdim 2009193323Sed // Ignore dbg intrinsics. 2010221345Sdim while (isa<DbgInfoIntrinsic>(FrontIt)) ++FrontIt; 2011234353Sdim 2012210299Sed // Allow a single instruction to be hoisted in addition to the compare 2013210299Sed // that feeds the branch. We later ensure that any values that _it_ uses 2014210299Sed // were also live in the predecessor, so that we don't unnecessarily create 2015210299Sed // register pressure or inhibit out-of-order execution. 2016210299Sed Instruction *BonusInst = 0; 2017210299Sed if (&*FrontIt != Cond && 2018210299Sed FrontIt->hasOneUse() && *FrontIt->use_begin() == Cond && 2019234353Sdim isSafeToSpeculativelyExecute(FrontIt)) { 2020210299Sed BonusInst = &*FrontIt; 2021210299Sed ++FrontIt; 2022243830Sdim 2023221345Sdim // Ignore dbg intrinsics. 2024221345Sdim while (isa<DbgInfoIntrinsic>(FrontIt)) ++FrontIt; 2025193323Sed } 2026221345Sdim 2027210299Sed // Only a single bonus inst is allowed. 2028210299Sed if (&*FrontIt != Cond) 2029210299Sed return false; 2030243830Sdim 2031193323Sed // Make sure the instruction after the condition is the cond branch. 2032193323Sed BasicBlock::iterator CondIt = Cond; ++CondIt; 2033221345Sdim 2034193323Sed // Ingore dbg intrinsics. 2035221345Sdim while (isa<DbgInfoIntrinsic>(CondIt)) ++CondIt; 2036243830Sdim 2037221345Sdim if (&*CondIt != BI) 2038193323Sed return false; 2039193323Sed 2040193323Sed // Cond is known to be a compare or binary operator. Check to make sure that 2041193323Sed // neither operand is a potentially-trapping constant expression. 2042193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(0))) 2043193323Sed if (CE->canTrap()) 2044193323Sed return false; 2045193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Cond->getOperand(1))) 2046193323Sed if (CE->canTrap()) 2047193323Sed return false; 2048243830Sdim 2049193323Sed // Finally, don't infinitely unroll conditional loops. 2050193323Sed BasicBlock *TrueDest = BI->getSuccessor(0); 2051239462Sdim BasicBlock *FalseDest = (BI->isConditional()) ? BI->getSuccessor(1) : 0; 2052193323Sed if (TrueDest == BB || FalseDest == BB) 2053193323Sed return false; 2054221345Sdim 2055193323Sed for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 2056193323Sed BasicBlock *PredBlock = *PI; 2057193323Sed BranchInst *PBI = dyn_cast<BranchInst>(PredBlock->getTerminator()); 2058243830Sdim 2059193323Sed // Check that we have two conditional branches. If there is a PHI node in 2060193323Sed // the common successor, verify that the same value flows in from both 2061193323Sed // blocks. 2062239462Sdim SmallVector<PHINode*, 4> PHIs; 2063239462Sdim if (PBI == 0 || PBI->isUnconditional() || 2064243830Sdim (BI->isConditional() && 2065239462Sdim !SafeToMergeTerminators(BI, PBI)) || 2066239462Sdim (!BI->isConditional() && 2067239462Sdim !isProfitableToFoldUnconditional(BI, PBI, Cond, PHIs))) 2068193323Sed continue; 2069243830Sdim 2070221345Sdim // Determine if the two branches share a common destination. 2071243830Sdim Instruction::BinaryOps Opc = Instruction::BinaryOpsEnd; 2072221345Sdim bool InvertPredCond = false; 2073243830Sdim 2074239462Sdim if (BI->isConditional()) { 2075239462Sdim if (PBI->getSuccessor(0) == TrueDest) 2076239462Sdim Opc = Instruction::Or; 2077239462Sdim else if (PBI->getSuccessor(1) == FalseDest) 2078239462Sdim Opc = Instruction::And; 2079239462Sdim else if (PBI->getSuccessor(0) == FalseDest) 2080239462Sdim Opc = Instruction::And, InvertPredCond = true; 2081239462Sdim else if (PBI->getSuccessor(1) == TrueDest) 2082239462Sdim Opc = Instruction::Or, InvertPredCond = true; 2083239462Sdim else 2084239462Sdim continue; 2085239462Sdim } else { 2086239462Sdim if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest) 2087239462Sdim continue; 2088239462Sdim } 2089221345Sdim 2090210299Sed // Ensure that any values used in the bonus instruction are also used 2091210299Sed // by the terminator of the predecessor. This means that those values 2092243830Sdim // must already have been resolved, so we won't be inhibiting the 2093263508Sdim // out-of-order core by speculating them earlier. We also allow 2094263508Sdim // instructions that are used by the terminator's condition because it 2095263508Sdim // exposes more merging opportunities. 2096263508Sdim bool UsedByBranch = (BonusInst && BonusInst->hasOneUse() && 2097263508Sdim *BonusInst->use_begin() == Cond); 2098263508Sdim 2099263508Sdim if (BonusInst && !UsedByBranch) { 2100210299Sed // Collect the values used by the bonus inst 2101210299Sed SmallPtrSet<Value*, 4> UsedValues; 2102210299Sed for (Instruction::op_iterator OI = BonusInst->op_begin(), 2103210299Sed OE = BonusInst->op_end(); OI != OE; ++OI) { 2104234353Sdim Value *V = *OI; 2105263508Sdim if (!isa<Constant>(V) && !isa<Argument>(V)) 2106210299Sed UsedValues.insert(V); 2107210299Sed } 2108210299Sed 2109210299Sed SmallVector<std::pair<Value*, unsigned>, 4> Worklist; 2110210299Sed Worklist.push_back(std::make_pair(PBI->getOperand(0), 0)); 2111243830Sdim 2112210299Sed // Walk up to four levels back up the use-def chain of the predecessor's 2113210299Sed // terminator to see if all those values were used. The choice of four 2114210299Sed // levels is arbitrary, to provide a compile-time-cost bound. 2115210299Sed while (!Worklist.empty()) { 2116210299Sed std::pair<Value*, unsigned> Pair = Worklist.back(); 2117210299Sed Worklist.pop_back(); 2118243830Sdim 2119210299Sed if (Pair.second >= 4) continue; 2120210299Sed UsedValues.erase(Pair.first); 2121210299Sed if (UsedValues.empty()) break; 2122243830Sdim 2123218893Sdim if (Instruction *I = dyn_cast<Instruction>(Pair.first)) { 2124210299Sed for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end(); 2125210299Sed OI != OE; ++OI) 2126210299Sed Worklist.push_back(std::make_pair(OI->get(), Pair.second+1)); 2127243830Sdim } 2128210299Sed } 2129243830Sdim 2130210299Sed if (!UsedValues.empty()) return false; 2131210299Sed } 2132193323Sed 2133202375Srdivacky DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB); 2134243830Sdim IRBuilder<> Builder(PBI); 2135223017Sdim 2136193323Sed // If we need to invert the condition in the pred block to match, do so now. 2137193323Sed if (InvertPredCond) { 2138218893Sdim Value *NewCond = PBI->getCondition(); 2139243830Sdim 2140218893Sdim if (NewCond->hasOneUse() && isa<CmpInst>(NewCond)) { 2141218893Sdim CmpInst *CI = cast<CmpInst>(NewCond); 2142218893Sdim CI->setPredicate(CI->getInversePredicate()); 2143218893Sdim } else { 2144243830Sdim NewCond = Builder.CreateNot(NewCond, 2145223017Sdim PBI->getCondition()->getName()+".not"); 2146218893Sdim } 2147243830Sdim 2148193323Sed PBI->setCondition(NewCond); 2149234353Sdim PBI->swapSuccessors(); 2150193323Sed } 2151243830Sdim 2152210299Sed // If we have a bonus inst, clone it into the predecessor block. 2153210299Sed Instruction *NewBonus = 0; 2154210299Sed if (BonusInst) { 2155210299Sed NewBonus = BonusInst->clone(); 2156210299Sed PredBlock->getInstList().insert(PBI, NewBonus); 2157210299Sed NewBonus->takeName(BonusInst); 2158210299Sed BonusInst->setName(BonusInst->getName()+".old"); 2159210299Sed } 2160243830Sdim 2161193323Sed // Clone Cond into the predecessor basic block, and or/and the 2162193323Sed // two conditions together. 2163193323Sed Instruction *New = Cond->clone(); 2164210299Sed if (BonusInst) New->replaceUsesOfWith(BonusInst, NewBonus); 2165193323Sed PredBlock->getInstList().insert(PBI, New); 2166193323Sed New->takeName(Cond); 2167193323Sed Cond->setName(New->getName()+".old"); 2168243830Sdim 2169239462Sdim if (BI->isConditional()) { 2170243830Sdim Instruction *NewCond = 2171239462Sdim cast<Instruction>(Builder.CreateBinOp(Opc, PBI->getCondition(), 2172223017Sdim New, "or.cond")); 2173239462Sdim PBI->setCondition(NewCond); 2174239462Sdim 2175243830Sdim uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight; 2176243830Sdim bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight, 2177243830Sdim PredFalseWeight); 2178243830Sdim bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight, 2179243830Sdim SuccFalseWeight); 2180243830Sdim SmallVector<uint64_t, 8> NewWeights; 2181243830Sdim 2182239462Sdim if (PBI->getSuccessor(0) == BB) { 2183243830Sdim if (PredHasWeights && SuccHasWeights) { 2184243830Sdim // PBI: br i1 %x, BB, FalseDest 2185243830Sdim // BI: br i1 %y, TrueDest, FalseDest 2186243830Sdim //TrueWeight is TrueWeight for PBI * TrueWeight for BI. 2187243830Sdim NewWeights.push_back(PredTrueWeight * SuccTrueWeight); 2188243830Sdim //FalseWeight is FalseWeight for PBI * TotalWeight for BI + 2189243830Sdim // TrueWeight for PBI * FalseWeight for BI. 2190243830Sdim // We assume that total weights of a BranchInst can fit into 32 bits. 2191243830Sdim // Therefore, we will not have overflow using 64-bit arithmetic. 2192243830Sdim NewWeights.push_back(PredFalseWeight * (SuccFalseWeight + 2193243830Sdim SuccTrueWeight) + PredTrueWeight * SuccFalseWeight); 2194243830Sdim } 2195239462Sdim AddPredecessorToBlock(TrueDest, PredBlock, BB); 2196239462Sdim PBI->setSuccessor(0, TrueDest); 2197239462Sdim } 2198239462Sdim if (PBI->getSuccessor(1) == BB) { 2199243830Sdim if (PredHasWeights && SuccHasWeights) { 2200243830Sdim // PBI: br i1 %x, TrueDest, BB 2201243830Sdim // BI: br i1 %y, TrueDest, FalseDest 2202243830Sdim //TrueWeight is TrueWeight for PBI * TotalWeight for BI + 2203243830Sdim // FalseWeight for PBI * TrueWeight for BI. 2204243830Sdim NewWeights.push_back(PredTrueWeight * (SuccFalseWeight + 2205243830Sdim SuccTrueWeight) + PredFalseWeight * SuccTrueWeight); 2206243830Sdim //FalseWeight is FalseWeight for PBI * FalseWeight for BI. 2207243830Sdim NewWeights.push_back(PredFalseWeight * SuccFalseWeight); 2208243830Sdim } 2209239462Sdim AddPredecessorToBlock(FalseDest, PredBlock, BB); 2210239462Sdim PBI->setSuccessor(1, FalseDest); 2211239462Sdim } 2212243830Sdim if (NewWeights.size() == 2) { 2213243830Sdim // Halve the weights if any of them cannot fit in an uint32_t 2214243830Sdim FitWeights(NewWeights); 2215243830Sdim 2216243830Sdim SmallVector<uint32_t, 8> MDWeights(NewWeights.begin(),NewWeights.end()); 2217243830Sdim PBI->setMetadata(LLVMContext::MD_prof, 2218243830Sdim MDBuilder(BI->getContext()). 2219243830Sdim createBranchWeights(MDWeights)); 2220243830Sdim } else 2221243830Sdim PBI->setMetadata(LLVMContext::MD_prof, NULL); 2222239462Sdim } else { 2223239462Sdim // Update PHI nodes in the common successors. 2224239462Sdim for (unsigned i = 0, e = PHIs.size(); i != e; ++i) { 2225239462Sdim ConstantInt *PBI_C = cast<ConstantInt>( 2226239462Sdim PHIs[i]->getIncomingValueForBlock(PBI->getParent())); 2227239462Sdim assert(PBI_C->getType()->isIntegerTy(1)); 2228239462Sdim Instruction *MergedCond = 0; 2229239462Sdim if (PBI->getSuccessor(0) == TrueDest) { 2230239462Sdim // Create (PBI_Cond and PBI_C) or (!PBI_Cond and BI_Value) 2231239462Sdim // PBI_C is true: PBI_Cond or (!PBI_Cond and BI_Value) 2232239462Sdim // is false: !PBI_Cond and BI_Value 2233239462Sdim Instruction *NotCond = 2234239462Sdim cast<Instruction>(Builder.CreateNot(PBI->getCondition(), 2235239462Sdim "not.cond")); 2236239462Sdim MergedCond = 2237239462Sdim cast<Instruction>(Builder.CreateBinOp(Instruction::And, 2238239462Sdim NotCond, New, 2239239462Sdim "and.cond")); 2240239462Sdim if (PBI_C->isOne()) 2241239462Sdim MergedCond = 2242239462Sdim cast<Instruction>(Builder.CreateBinOp(Instruction::Or, 2243239462Sdim PBI->getCondition(), MergedCond, 2244239462Sdim "or.cond")); 2245239462Sdim } else { 2246239462Sdim // Create (PBI_Cond and BI_Value) or (!PBI_Cond and PBI_C) 2247239462Sdim // PBI_C is true: (PBI_Cond and BI_Value) or (!PBI_Cond) 2248239462Sdim // is false: PBI_Cond and BI_Value 2249243830Sdim MergedCond = 2250239462Sdim cast<Instruction>(Builder.CreateBinOp(Instruction::And, 2251239462Sdim PBI->getCondition(), New, 2252239462Sdim "and.cond")); 2253239462Sdim if (PBI_C->isOne()) { 2254239462Sdim Instruction *NotCond = 2255239462Sdim cast<Instruction>(Builder.CreateNot(PBI->getCondition(), 2256239462Sdim "not.cond")); 2257243830Sdim MergedCond = 2258239462Sdim cast<Instruction>(Builder.CreateBinOp(Instruction::Or, 2259239462Sdim NotCond, MergedCond, 2260239462Sdim "or.cond")); 2261239462Sdim } 2262239462Sdim } 2263239462Sdim // Update PHI Node. 2264239462Sdim PHIs[i]->setIncomingValue(PHIs[i]->getBasicBlockIndex(PBI->getParent()), 2265239462Sdim MergedCond); 2266239462Sdim } 2267239462Sdim // Change PBI from Conditional to Unconditional. 2268239462Sdim BranchInst *New_PBI = BranchInst::Create(TrueDest, PBI); 2269239462Sdim EraseTerminatorInstAndDCECond(PBI); 2270239462Sdim PBI = New_PBI; 2271193323Sed } 2272221345Sdim 2273234353Sdim // TODO: If BB is reachable from all paths through PredBlock, then we 2274234353Sdim // could replace PBI's branch probabilities with BI's. 2275234353Sdim 2276221345Sdim // Copy any debug value intrinsics into the end of PredBlock. 2277221345Sdim for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 2278221345Sdim if (isa<DbgInfoIntrinsic>(*I)) 2279221345Sdim I->clone()->insertBefore(PBI); 2280243830Sdim 2281193323Sed return true; 2282193323Sed } 2283193323Sed return false; 2284193323Sed} 2285193323Sed 2286193323Sed/// SimplifyCondBranchToCondBranch - If we have a conditional branch as a 2287193323Sed/// predecessor of another block, this function tries to simplify it. We know 2288193323Sed/// that PBI and BI are both conditional branches, and BI is in one of the 2289193323Sed/// successor blocks of PBI - PBI branches to BI. 2290193323Sedstatic bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { 2291193323Sed assert(PBI->isConditional() && BI->isConditional()); 2292193323Sed BasicBlock *BB = BI->getParent(); 2293198090Srdivacky 2294193323Sed // If this block ends with a branch instruction, and if there is a 2295243830Sdim // predecessor that ends on a branch of the same condition, make 2296193323Sed // this conditional branch redundant. 2297193323Sed if (PBI->getCondition() == BI->getCondition() && 2298193323Sed PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 2299193323Sed // Okay, the outcome of this conditional branch is statically 2300193323Sed // knowable. If this block had a single pred, handle specially. 2301193323Sed if (BB->getSinglePredecessor()) { 2302193323Sed // Turn this into a branch on constant. 2303193323Sed bool CondIsTrue = PBI->getSuccessor(0) == BB; 2304243830Sdim BI->setCondition(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 2305198090Srdivacky CondIsTrue)); 2306193323Sed return true; // Nuke the branch on constant. 2307193323Sed } 2308243830Sdim 2309193323Sed // Otherwise, if there are multiple predecessors, insert a PHI that merges 2310193323Sed // in the constant and simplify the block result. Subsequent passes of 2311193323Sed // simplifycfg will thread the block. 2312193323Sed if (BlockIsSimpleEnoughToThreadThrough(BB)) { 2313221345Sdim pred_iterator PB = pred_begin(BB), PE = pred_end(BB); 2314198090Srdivacky PHINode *NewPN = PHINode::Create(Type::getInt1Ty(BB->getContext()), 2315221345Sdim std::distance(PB, PE), 2316193323Sed BI->getCondition()->getName() + ".pr", 2317193323Sed BB->begin()); 2318193323Sed // Okay, we're going to insert the PHI node. Since PBI is not the only 2319193323Sed // predecessor, compute the PHI'd conditional value for all of the preds. 2320193323Sed // Any predecessor where the condition is not computable we keep symbolic. 2321221345Sdim for (pred_iterator PI = PB; PI != PE; ++PI) { 2322210299Sed BasicBlock *P = *PI; 2323210299Sed if ((PBI = dyn_cast<BranchInst>(P->getTerminator())) && 2324193323Sed PBI != BI && PBI->isConditional() && 2325193323Sed PBI->getCondition() == BI->getCondition() && 2326193323Sed PBI->getSuccessor(0) != PBI->getSuccessor(1)) { 2327193323Sed bool CondIsTrue = PBI->getSuccessor(0) == BB; 2328243830Sdim NewPN->addIncoming(ConstantInt::get(Type::getInt1Ty(BB->getContext()), 2329210299Sed CondIsTrue), P); 2330193323Sed } else { 2331210299Sed NewPN->addIncoming(BI->getCondition(), P); 2332193323Sed } 2333210299Sed } 2334243830Sdim 2335193323Sed BI->setCondition(NewPN); 2336193323Sed return true; 2337193323Sed } 2338193323Sed } 2339243830Sdim 2340193323Sed // If this is a conditional branch in an empty block, and if any 2341193323Sed // predecessors is a conditional branch to one of our destinations, 2342193323Sed // fold the conditions into logical ops and one cond br. 2343193323Sed BasicBlock::iterator BBI = BB->begin(); 2344193323Sed // Ignore dbg intrinsics. 2345193323Sed while (isa<DbgInfoIntrinsic>(BBI)) 2346193323Sed ++BBI; 2347193323Sed if (&*BBI != BI) 2348193323Sed return false; 2349193323Sed 2350243830Sdim 2351193323Sed if (ConstantExpr *CE = dyn_cast<ConstantExpr>(BI->getCondition())) 2352193323Sed if (CE->canTrap()) 2353193323Sed return false; 2354243830Sdim 2355193323Sed int PBIOp, BIOp; 2356193323Sed if (PBI->getSuccessor(0) == BI->getSuccessor(0)) 2357193323Sed PBIOp = BIOp = 0; 2358193323Sed else if (PBI->getSuccessor(0) == BI->getSuccessor(1)) 2359193323Sed PBIOp = 0, BIOp = 1; 2360193323Sed else if (PBI->getSuccessor(1) == BI->getSuccessor(0)) 2361193323Sed PBIOp = 1, BIOp = 0; 2362193323Sed else if (PBI->getSuccessor(1) == BI->getSuccessor(1)) 2363193323Sed PBIOp = BIOp = 1; 2364193323Sed else 2365193323Sed return false; 2366243830Sdim 2367193323Sed // Check to make sure that the other destination of this branch 2368193323Sed // isn't BB itself. If so, this is an infinite loop that will 2369193323Sed // keep getting unwound. 2370193323Sed if (PBI->getSuccessor(PBIOp) == BB) 2371193323Sed return false; 2372243830Sdim 2373243830Sdim // Do not perform this transformation if it would require 2374193323Sed // insertion of a large number of select instructions. For targets 2375193323Sed // without predication/cmovs, this is a big pessimization. 2376193323Sed BasicBlock *CommonDest = PBI->getSuccessor(PBIOp); 2377243830Sdim 2378193323Sed unsigned NumPhis = 0; 2379193323Sed for (BasicBlock::iterator II = CommonDest->begin(); 2380193323Sed isa<PHINode>(II); ++II, ++NumPhis) 2381193323Sed if (NumPhis > 2) // Disable this xform. 2382193323Sed return false; 2383243830Sdim 2384193323Sed // Finally, if everything is ok, fold the branches to logical ops. 2385193323Sed BasicBlock *OtherDest = BI->getSuccessor(BIOp ^ 1); 2386243830Sdim 2387202375Srdivacky DEBUG(dbgs() << "FOLDING BRs:" << *PBI->getParent() 2388198090Srdivacky << "AND: " << *BI->getParent()); 2389243830Sdim 2390243830Sdim 2391193323Sed // If OtherDest *is* BB, then BB is a basic block with a single conditional 2392193323Sed // branch in it, where one edge (OtherDest) goes back to itself but the other 2393193323Sed // exits. We don't *know* that the program avoids the infinite loop 2394193323Sed // (even though that seems likely). If we do this xform naively, we'll end up 2395193323Sed // recursively unpeeling the loop. Since we know that (after the xform is 2396193323Sed // done) that the block *is* infinite if reached, we just make it an obviously 2397193323Sed // infinite loop with no cond branch. 2398193323Sed if (OtherDest == BB) { 2399193323Sed // Insert it at the end of the function, because it's either code, 2400193323Sed // or it won't matter if it's hot. :) 2401198090Srdivacky BasicBlock *InfLoopBlock = BasicBlock::Create(BB->getContext(), 2402198090Srdivacky "infloop", BB->getParent()); 2403193323Sed BranchInst::Create(InfLoopBlock, InfLoopBlock); 2404193323Sed OtherDest = InfLoopBlock; 2405243830Sdim } 2406243830Sdim 2407202375Srdivacky DEBUG(dbgs() << *PBI->getParent()->getParent()); 2408223017Sdim 2409193323Sed // BI may have other predecessors. Because of this, we leave 2410193323Sed // it alone, but modify PBI. 2411243830Sdim 2412193323Sed // Make sure we get to CommonDest on True&True directions. 2413193323Sed Value *PBICond = PBI->getCondition(); 2414223017Sdim IRBuilder<true, NoFolder> Builder(PBI); 2415193323Sed if (PBIOp) 2416223017Sdim PBICond = Builder.CreateNot(PBICond, PBICond->getName()+".not"); 2417223017Sdim 2418193323Sed Value *BICond = BI->getCondition(); 2419193323Sed if (BIOp) 2420223017Sdim BICond = Builder.CreateNot(BICond, BICond->getName()+".not"); 2421223017Sdim 2422193323Sed // Merge the conditions. 2423223017Sdim Value *Cond = Builder.CreateOr(PBICond, BICond, "brmerge"); 2424243830Sdim 2425193323Sed // Modify PBI to branch on the new condition to the new dests. 2426193323Sed PBI->setCondition(Cond); 2427193323Sed PBI->setSuccessor(0, CommonDest); 2428193323Sed PBI->setSuccessor(1, OtherDest); 2429243830Sdim 2430243830Sdim // Update branch weight for PBI. 2431243830Sdim uint64_t PredTrueWeight, PredFalseWeight, SuccTrueWeight, SuccFalseWeight; 2432243830Sdim bool PredHasWeights = ExtractBranchMetadata(PBI, PredTrueWeight, 2433243830Sdim PredFalseWeight); 2434243830Sdim bool SuccHasWeights = ExtractBranchMetadata(BI, SuccTrueWeight, 2435243830Sdim SuccFalseWeight); 2436243830Sdim if (PredHasWeights && SuccHasWeights) { 2437243830Sdim uint64_t PredCommon = PBIOp ? PredFalseWeight : PredTrueWeight; 2438243830Sdim uint64_t PredOther = PBIOp ?PredTrueWeight : PredFalseWeight; 2439243830Sdim uint64_t SuccCommon = BIOp ? SuccFalseWeight : SuccTrueWeight; 2440243830Sdim uint64_t SuccOther = BIOp ? SuccTrueWeight : SuccFalseWeight; 2441243830Sdim // The weight to CommonDest should be PredCommon * SuccTotal + 2442243830Sdim // PredOther * SuccCommon. 2443243830Sdim // The weight to OtherDest should be PredOther * SuccOther. 2444243830Sdim SmallVector<uint64_t, 2> NewWeights; 2445243830Sdim NewWeights.push_back(PredCommon * (SuccCommon + SuccOther) + 2446243830Sdim PredOther * SuccCommon); 2447243830Sdim NewWeights.push_back(PredOther * SuccOther); 2448243830Sdim // Halve the weights if any of them cannot fit in an uint32_t 2449243830Sdim FitWeights(NewWeights); 2450243830Sdim 2451243830Sdim SmallVector<uint32_t, 2> MDWeights(NewWeights.begin(),NewWeights.end()); 2452243830Sdim PBI->setMetadata(LLVMContext::MD_prof, 2453243830Sdim MDBuilder(BI->getContext()). 2454243830Sdim createBranchWeights(MDWeights)); 2455243830Sdim } 2456243830Sdim 2457193323Sed // OtherDest may have phi nodes. If so, add an entry from PBI's 2458193323Sed // block that are identical to the entries for BI's block. 2459218893Sdim AddPredecessorToBlock(OtherDest, PBI->getParent(), BB); 2460243830Sdim 2461193323Sed // We know that the CommonDest already had an edge from PBI to 2462193323Sed // it. If it has PHIs though, the PHIs may have different 2463193323Sed // entries for BB and PBI's BB. If so, insert a select to make 2464193323Sed // them agree. 2465218893Sdim PHINode *PN; 2466193323Sed for (BasicBlock::iterator II = CommonDest->begin(); 2467193323Sed (PN = dyn_cast<PHINode>(II)); ++II) { 2468193323Sed Value *BIV = PN->getIncomingValueForBlock(BB); 2469193323Sed unsigned PBBIdx = PN->getBasicBlockIndex(PBI->getParent()); 2470193323Sed Value *PBIV = PN->getIncomingValue(PBBIdx); 2471193323Sed if (BIV != PBIV) { 2472193323Sed // Insert a select in PBI to pick the right value. 2473223017Sdim Value *NV = cast<SelectInst> 2474223017Sdim (Builder.CreateSelect(PBICond, PBIV, BIV, PBIV->getName()+".mux")); 2475193323Sed PN->setIncomingValue(PBBIdx, NV); 2476193323Sed } 2477193323Sed } 2478243830Sdim 2479202375Srdivacky DEBUG(dbgs() << "INTO: " << *PBI->getParent()); 2480202375Srdivacky DEBUG(dbgs() << *PBI->getParent()->getParent()); 2481243830Sdim 2482193323Sed // This basic block is probably dead. We know it has at least 2483193323Sed // one fewer predecessor. 2484193323Sed return true; 2485193323Sed} 2486193323Sed 2487218893Sdim// SimplifyTerminatorOnSelect - Simplifies a terminator by replacing it with a 2488218893Sdim// branch to TrueBB if Cond is true or to FalseBB if Cond is false. 2489218893Sdim// Takes care of updating the successors and removing the old terminator. 2490218893Sdim// Also makes sure not to introduce new successors by assuming that edges to 2491218893Sdim// non-successor TrueBBs and FalseBBs aren't reachable. 2492218893Sdimstatic bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond, 2493243830Sdim BasicBlock *TrueBB, BasicBlock *FalseBB, 2494243830Sdim uint32_t TrueWeight, 2495243830Sdim uint32_t FalseWeight){ 2496218893Sdim // Remove any superfluous successor edges from the CFG. 2497218893Sdim // First, figure out which successors to preserve. 2498218893Sdim // If TrueBB and FalseBB are equal, only try to preserve one copy of that 2499218893Sdim // successor. 2500218893Sdim BasicBlock *KeepEdge1 = TrueBB; 2501218893Sdim BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : 0; 2502193323Sed 2503218893Sdim // Then remove the rest. 2504218893Sdim for (unsigned I = 0, E = OldTerm->getNumSuccessors(); I != E; ++I) { 2505218893Sdim BasicBlock *Succ = OldTerm->getSuccessor(I); 2506218893Sdim // Make sure only to keep exactly one copy of each edge. 2507218893Sdim if (Succ == KeepEdge1) 2508218893Sdim KeepEdge1 = 0; 2509218893Sdim else if (Succ == KeepEdge2) 2510218893Sdim KeepEdge2 = 0; 2511218893Sdim else 2512218893Sdim Succ->removePredecessor(OldTerm->getParent()); 2513218893Sdim } 2514193323Sed 2515223017Sdim IRBuilder<> Builder(OldTerm); 2516223017Sdim Builder.SetCurrentDebugLocation(OldTerm->getDebugLoc()); 2517223017Sdim 2518218893Sdim // Insert an appropriate new terminator. 2519218893Sdim if ((KeepEdge1 == 0) && (KeepEdge2 == 0)) { 2520218893Sdim if (TrueBB == FalseBB) 2521218893Sdim // We were only looking for one successor, and it was present. 2522218893Sdim // Create an unconditional branch to it. 2523223017Sdim Builder.CreateBr(TrueBB); 2524243830Sdim else { 2525218893Sdim // We found both of the successors we were looking for. 2526218893Sdim // Create a conditional branch sharing the condition of the select. 2527243830Sdim BranchInst *NewBI = Builder.CreateCondBr(Cond, TrueBB, FalseBB); 2528243830Sdim if (TrueWeight != FalseWeight) 2529243830Sdim NewBI->setMetadata(LLVMContext::MD_prof, 2530243830Sdim MDBuilder(OldTerm->getContext()). 2531243830Sdim createBranchWeights(TrueWeight, FalseWeight)); 2532243830Sdim } 2533218893Sdim } else if (KeepEdge1 && (KeepEdge2 || TrueBB == FalseBB)) { 2534218893Sdim // Neither of the selected blocks were successors, so this 2535218893Sdim // terminator must be unreachable. 2536218893Sdim new UnreachableInst(OldTerm->getContext(), OldTerm); 2537218893Sdim } else { 2538218893Sdim // One of the selected values was a successor, but the other wasn't. 2539218893Sdim // Insert an unconditional branch to the one that was found; 2540218893Sdim // the edge to the one that wasn't must be unreachable. 2541218893Sdim if (KeepEdge1 == 0) 2542218893Sdim // Only TrueBB was found. 2543223017Sdim Builder.CreateBr(TrueBB); 2544218893Sdim else 2545218893Sdim // Only FalseBB was found. 2546223017Sdim Builder.CreateBr(FalseBB); 2547193323Sed } 2548193323Sed 2549218893Sdim EraseTerminatorInstAndDCECond(OldTerm); 2550218893Sdim return true; 2551218893Sdim} 2552193323Sed 2553221345Sdim// SimplifySwitchOnSelect - Replaces 2554221345Sdim// (switch (select cond, X, Y)) on constant X, Y 2555221345Sdim// with a branch - conditional if X and Y lead to distinct BBs, 2556221345Sdim// unconditional otherwise. 2557221345Sdimstatic bool SimplifySwitchOnSelect(SwitchInst *SI, SelectInst *Select) { 2558221345Sdim // Check for constant integer values in the select. 2559221345Sdim ConstantInt *TrueVal = dyn_cast<ConstantInt>(Select->getTrueValue()); 2560221345Sdim ConstantInt *FalseVal = dyn_cast<ConstantInt>(Select->getFalseValue()); 2561221345Sdim if (!TrueVal || !FalseVal) 2562221345Sdim return false; 2563221345Sdim 2564221345Sdim // Find the relevant condition and destinations. 2565221345Sdim Value *Condition = Select->getCondition(); 2566234353Sdim BasicBlock *TrueBB = SI->findCaseValue(TrueVal).getCaseSuccessor(); 2567234353Sdim BasicBlock *FalseBB = SI->findCaseValue(FalseVal).getCaseSuccessor(); 2568221345Sdim 2569243830Sdim // Get weight for TrueBB and FalseBB. 2570243830Sdim uint32_t TrueWeight = 0, FalseWeight = 0; 2571243830Sdim SmallVector<uint64_t, 8> Weights; 2572243830Sdim bool HasWeights = HasBranchWeights(SI); 2573243830Sdim if (HasWeights) { 2574243830Sdim GetBranchWeights(SI, Weights); 2575243830Sdim if (Weights.size() == 1 + SI->getNumCases()) { 2576243830Sdim TrueWeight = (uint32_t)Weights[SI->findCaseValue(TrueVal). 2577243830Sdim getSuccessorIndex()]; 2578243830Sdim FalseWeight = (uint32_t)Weights[SI->findCaseValue(FalseVal). 2579243830Sdim getSuccessorIndex()]; 2580243830Sdim } 2581243830Sdim } 2582243830Sdim 2583221345Sdim // Perform the actual simplification. 2584243830Sdim return SimplifyTerminatorOnSelect(SI, Condition, TrueBB, FalseBB, 2585243830Sdim TrueWeight, FalseWeight); 2586221345Sdim} 2587221345Sdim 2588218893Sdim// SimplifyIndirectBrOnSelect - Replaces 2589218893Sdim// (indirectbr (select cond, blockaddress(@fn, BlockA), 2590218893Sdim// blockaddress(@fn, BlockB))) 2591218893Sdim// with 2592218893Sdim// (br cond, BlockA, BlockB). 2593218893Sdimstatic bool SimplifyIndirectBrOnSelect(IndirectBrInst *IBI, SelectInst *SI) { 2594218893Sdim // Check that both operands of the select are block addresses. 2595218893Sdim BlockAddress *TBA = dyn_cast<BlockAddress>(SI->getTrueValue()); 2596218893Sdim BlockAddress *FBA = dyn_cast<BlockAddress>(SI->getFalseValue()); 2597218893Sdim if (!TBA || !FBA) 2598218893Sdim return false; 2599198892Srdivacky 2600218893Sdim // Extract the actual blocks. 2601218893Sdim BasicBlock *TrueBB = TBA->getBasicBlock(); 2602218893Sdim BasicBlock *FalseBB = FBA->getBasicBlock(); 2603193323Sed 2604218893Sdim // Perform the actual simplification. 2605243830Sdim return SimplifyTerminatorOnSelect(IBI, SI->getCondition(), TrueBB, FalseBB, 2606243830Sdim 0, 0); 2607218893Sdim} 2608193323Sed 2609218893Sdim/// TryToSimplifyUncondBranchWithICmpInIt - This is called when we find an icmp 2610218893Sdim/// instruction (a seteq/setne with a constant) as the only instruction in a 2611218893Sdim/// block that ends with an uncond branch. We are looking for a very specific 2612218893Sdim/// pattern that occurs when "A == 1 || A == 2 || A == 3" gets simplified. In 2613218893Sdim/// this case, we merge the first two "or's of icmp" into a switch, but then the 2614218893Sdim/// default value goes to an uncond block with a seteq in it, we get something 2615218893Sdim/// like: 2616218893Sdim/// 2617218893Sdim/// switch i8 %A, label %DEFAULT [ i8 1, label %end i8 2, label %end ] 2618218893Sdim/// DEFAULT: 2619218893Sdim/// %tmp = icmp eq i8 %A, 92 2620218893Sdim/// br label %end 2621218893Sdim/// end: 2622218893Sdim/// ... = phi i1 [ true, %entry ], [ %tmp, %DEFAULT ], [ true, %entry ] 2623243830Sdim/// 2624218893Sdim/// We prefer to split the edge to 'end' so that there is a true/false entry to 2625218893Sdim/// the PHI, merging the third icmp into the switch. 2626249423Sdimstatic bool TryToSimplifyUncondBranchWithICmpInIt( 2627249423Sdim ICmpInst *ICI, IRBuilder<> &Builder, const TargetTransformInfo &TTI, 2628249423Sdim const DataLayout *TD) { 2629218893Sdim BasicBlock *BB = ICI->getParent(); 2630223017Sdim 2631218893Sdim // If the block has any PHIs in it or the icmp has multiple uses, it is too 2632218893Sdim // complex. 2633218893Sdim if (isa<PHINode>(BB->begin()) || !ICI->hasOneUse()) return false; 2634193323Sed 2635218893Sdim Value *V = ICI->getOperand(0); 2636218893Sdim ConstantInt *Cst = cast<ConstantInt>(ICI->getOperand(1)); 2637243830Sdim 2638218893Sdim // The pattern we're looking for is where our only predecessor is a switch on 2639218893Sdim // 'V' and this block is the default case for the switch. In this case we can 2640218893Sdim // fold the compared value into the switch to simplify things. 2641218893Sdim BasicBlock *Pred = BB->getSinglePredecessor(); 2642218893Sdim if (Pred == 0 || !isa<SwitchInst>(Pred->getTerminator())) return false; 2643243830Sdim 2644218893Sdim SwitchInst *SI = cast<SwitchInst>(Pred->getTerminator()); 2645218893Sdim if (SI->getCondition() != V) 2646218893Sdim return false; 2647243830Sdim 2648218893Sdim // If BB is reachable on a non-default case, then we simply know the value of 2649218893Sdim // V in this block. Substitute it and constant fold the icmp instruction 2650218893Sdim // away. 2651218893Sdim if (SI->getDefaultDest() != BB) { 2652218893Sdim ConstantInt *VVal = SI->findCaseDest(BB); 2653218893Sdim assert(VVal && "Should have a unique destination value"); 2654218893Sdim ICI->setOperand(0, VVal); 2655243830Sdim 2656218893Sdim if (Value *V = SimplifyInstruction(ICI, TD)) { 2657218893Sdim ICI->replaceAllUsesWith(V); 2658218893Sdim ICI->eraseFromParent(); 2659218893Sdim } 2660218893Sdim // BB is now empty, so it is likely to simplify away. 2661249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 2662218893Sdim } 2663243830Sdim 2664218893Sdim // Ok, the block is reachable from the default dest. If the constant we're 2665218893Sdim // comparing exists in one of the other edges, then we can constant fold ICI 2666218893Sdim // and zap it. 2667234353Sdim if (SI->findCaseValue(Cst) != SI->case_default()) { 2668218893Sdim Value *V; 2669218893Sdim if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 2670218893Sdim V = ConstantInt::getFalse(BB->getContext()); 2671218893Sdim else 2672218893Sdim V = ConstantInt::getTrue(BB->getContext()); 2673243830Sdim 2674218893Sdim ICI->replaceAllUsesWith(V); 2675218893Sdim ICI->eraseFromParent(); 2676218893Sdim // BB is now empty, so it is likely to simplify away. 2677249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 2678218893Sdim } 2679243830Sdim 2680218893Sdim // The use of the icmp has to be in the 'end' block, by the only PHI node in 2681218893Sdim // the block. 2682218893Sdim BasicBlock *SuccBlock = BB->getTerminator()->getSuccessor(0); 2683218893Sdim PHINode *PHIUse = dyn_cast<PHINode>(ICI->use_back()); 2684218893Sdim if (PHIUse == 0 || PHIUse != &SuccBlock->front() || 2685218893Sdim isa<PHINode>(++BasicBlock::iterator(PHIUse))) 2686218893Sdim return false; 2687193323Sed 2688218893Sdim // If the icmp is a SETEQ, then the default dest gets false, the new edge gets 2689218893Sdim // true in the PHI. 2690218893Sdim Constant *DefaultCst = ConstantInt::getTrue(BB->getContext()); 2691218893Sdim Constant *NewCst = ConstantInt::getFalse(BB->getContext()); 2692193323Sed 2693218893Sdim if (ICI->getPredicate() == ICmpInst::ICMP_EQ) 2694218893Sdim std::swap(DefaultCst, NewCst); 2695193323Sed 2696218893Sdim // Replace ICI (which is used by the PHI for the default value) with true or 2697218893Sdim // false depending on if it is EQ or NE. 2698218893Sdim ICI->replaceAllUsesWith(DefaultCst); 2699218893Sdim ICI->eraseFromParent(); 2700193323Sed 2701218893Sdim // Okay, the switch goes to this block on a default value. Add an edge from 2702218893Sdim // the switch to the merge point on the compared value. 2703218893Sdim BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "switch.edge", 2704218893Sdim BB->getParent(), BB); 2705243830Sdim SmallVector<uint64_t, 8> Weights; 2706243830Sdim bool HasWeights = HasBranchWeights(SI); 2707243830Sdim if (HasWeights) { 2708243830Sdim GetBranchWeights(SI, Weights); 2709243830Sdim if (Weights.size() == 1 + SI->getNumCases()) { 2710243830Sdim // Split weight for default case to case for "Cst". 2711243830Sdim Weights[0] = (Weights[0]+1) >> 1; 2712243830Sdim Weights.push_back(Weights[0]); 2713243830Sdim 2714243830Sdim SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); 2715243830Sdim SI->setMetadata(LLVMContext::MD_prof, 2716243830Sdim MDBuilder(SI->getContext()). 2717243830Sdim createBranchWeights(MDWeights)); 2718243830Sdim } 2719243830Sdim } 2720218893Sdim SI->addCase(Cst, NewBB); 2721243830Sdim 2722218893Sdim // NewBB branches to the phi block, add the uncond branch and the phi entry. 2723223017Sdim Builder.SetInsertPoint(NewBB); 2724223017Sdim Builder.SetCurrentDebugLocation(SI->getDebugLoc()); 2725223017Sdim Builder.CreateBr(SuccBlock); 2726218893Sdim PHIUse->addIncoming(NewCst, NewBB); 2727218893Sdim return true; 2728218893Sdim} 2729193323Sed 2730218893Sdim/// SimplifyBranchOnICmpChain - The specified branch is a conditional branch. 2731218893Sdim/// Check to see if it is branching on an or/and chain of icmp instructions, and 2732218893Sdim/// fold it into a switch instruction if so. 2733243830Sdimstatic bool SimplifyBranchOnICmpChain(BranchInst *BI, const DataLayout *TD, 2734223017Sdim IRBuilder<> &Builder) { 2735218893Sdim Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()); 2736218893Sdim if (Cond == 0) return false; 2737243830Sdim 2738243830Sdim 2739218893Sdim // Change br (X == 0 | X == 1), T, F into a switch instruction. 2740218893Sdim // If this is a bunch of seteq's or'd together, or if it's a bunch of 2741218893Sdim // 'setne's and'ed together, collect them. 2742218893Sdim Value *CompVal = 0; 2743218893Sdim std::vector<ConstantInt*> Values; 2744218893Sdim bool TrueWhenEqual = true; 2745218893Sdim Value *ExtraCase = 0; 2746218893Sdim unsigned UsedICmps = 0; 2747243830Sdim 2748218893Sdim if (Cond->getOpcode() == Instruction::Or) { 2749218893Sdim CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, true, 2750218893Sdim UsedICmps); 2751218893Sdim } else if (Cond->getOpcode() == Instruction::And) { 2752218893Sdim CompVal = GatherConstantCompares(Cond, Values, ExtraCase, TD, false, 2753218893Sdim UsedICmps); 2754218893Sdim TrueWhenEqual = false; 2755218893Sdim } 2756243830Sdim 2757218893Sdim // If we didn't have a multiply compared value, fail. 2758218893Sdim if (CompVal == 0) return false; 2759193323Sed 2760218893Sdim // Avoid turning single icmps into a switch. 2761218893Sdim if (UsedICmps <= 1) 2762218893Sdim return false; 2763218893Sdim 2764218893Sdim // There might be duplicate constants in the list, which the switch 2765218893Sdim // instruction can't handle, remove them now. 2766218893Sdim array_pod_sort(Values.begin(), Values.end(), ConstantIntSortPredicate); 2767218893Sdim Values.erase(std::unique(Values.begin(), Values.end()), Values.end()); 2768243830Sdim 2769218893Sdim // If Extra was used, we require at least two switch values to do the 2770218893Sdim // transformation. A switch with one value is just an cond branch. 2771218893Sdim if (ExtraCase && Values.size() < 2) return false; 2772243830Sdim 2773243830Sdim // TODO: Preserve branch weight metadata, similarly to how 2774243830Sdim // FoldValueComparisonIntoPredecessors preserves it. 2775243830Sdim 2776218893Sdim // Figure out which block is which destination. 2777218893Sdim BasicBlock *DefaultBB = BI->getSuccessor(1); 2778218893Sdim BasicBlock *EdgeBB = BI->getSuccessor(0); 2779218893Sdim if (!TrueWhenEqual) std::swap(DefaultBB, EdgeBB); 2780243830Sdim 2781218893Sdim BasicBlock *BB = BI->getParent(); 2782243830Sdim 2783218893Sdim DEBUG(dbgs() << "Converting 'icmp' chain with " << Values.size() 2784218893Sdim << " cases into SWITCH. BB is:\n" << *BB); 2785243830Sdim 2786218893Sdim // If there are any extra values that couldn't be folded into the switch 2787218893Sdim // then we evaluate them with an explicit branch first. Split the block 2788218893Sdim // right before the condbr to handle it. 2789218893Sdim if (ExtraCase) { 2790218893Sdim BasicBlock *NewBB = BB->splitBasicBlock(BI, "switch.early.test"); 2791218893Sdim // Remove the uncond branch added to the old block. 2792218893Sdim TerminatorInst *OldTI = BB->getTerminator(); 2793223017Sdim Builder.SetInsertPoint(OldTI); 2794223017Sdim 2795218893Sdim if (TrueWhenEqual) 2796223017Sdim Builder.CreateCondBr(ExtraCase, EdgeBB, NewBB); 2797218893Sdim else 2798223017Sdim Builder.CreateCondBr(ExtraCase, NewBB, EdgeBB); 2799243830Sdim 2800218893Sdim OldTI->eraseFromParent(); 2801243830Sdim 2802218893Sdim // If there are PHI nodes in EdgeBB, then we need to add a new entry to them 2803218893Sdim // for the edge we just added. 2804218893Sdim AddPredecessorToBlock(EdgeBB, BB, NewBB); 2805243830Sdim 2806218893Sdim DEBUG(dbgs() << " ** 'icmp' chain unhandled condition: " << *ExtraCase 2807218893Sdim << "\nEXTRABB = " << *BB); 2808218893Sdim BB = NewBB; 2809218893Sdim } 2810223017Sdim 2811223017Sdim Builder.SetInsertPoint(BI); 2812218893Sdim // Convert pointer to int before we switch. 2813218893Sdim if (CompVal->getType()->isPointerTy()) { 2814243830Sdim assert(TD && "Cannot switch on pointer without DataLayout"); 2815223017Sdim CompVal = Builder.CreatePtrToInt(CompVal, 2816263508Sdim TD->getIntPtrType(CompVal->getType()), 2817223017Sdim "magicptr"); 2818218893Sdim } 2819243830Sdim 2820218893Sdim // Create the new switch instruction now. 2821223017Sdim SwitchInst *New = Builder.CreateSwitch(CompVal, DefaultBB, Values.size()); 2822223017Sdim 2823218893Sdim // Add all of the 'cases' to the switch instruction. 2824218893Sdim for (unsigned i = 0, e = Values.size(); i != e; ++i) 2825218893Sdim New->addCase(Values[i], EdgeBB); 2826243830Sdim 2827218893Sdim // We added edges from PI to the EdgeBB. As such, if there were any 2828218893Sdim // PHI nodes in EdgeBB, they need entries to be added corresponding to 2829218893Sdim // the number of edges added. 2830218893Sdim for (BasicBlock::iterator BBI = EdgeBB->begin(); 2831218893Sdim isa<PHINode>(BBI); ++BBI) { 2832218893Sdim PHINode *PN = cast<PHINode>(BBI); 2833218893Sdim Value *InVal = PN->getIncomingValueForBlock(BB); 2834218893Sdim for (unsigned i = 0, e = Values.size()-1; i != e; ++i) 2835218893Sdim PN->addIncoming(InVal, BB); 2836218893Sdim } 2837243830Sdim 2838218893Sdim // Erase the old branch instruction. 2839218893Sdim EraseTerminatorInstAndDCECond(BI); 2840243830Sdim 2841218893Sdim DEBUG(dbgs() << " ** 'icmp' chain result is:\n" << *BB << '\n'); 2842218893Sdim return true; 2843218893Sdim} 2844218893Sdim 2845226633Sdimbool SimplifyCFGOpt::SimplifyResume(ResumeInst *RI, IRBuilder<> &Builder) { 2846226633Sdim // If this is a trivial landing pad that just continues unwinding the caught 2847226633Sdim // exception then zap the landing pad, turning its invokes into calls. 2848226633Sdim BasicBlock *BB = RI->getParent(); 2849226633Sdim LandingPadInst *LPInst = dyn_cast<LandingPadInst>(BB->getFirstNonPHI()); 2850226633Sdim if (RI->getValue() != LPInst) 2851226633Sdim // Not a landing pad, or the resume is not unwinding the exception that 2852226633Sdim // caused control to branch here. 2853226633Sdim return false; 2854226633Sdim 2855226633Sdim // Check that there are no other instructions except for debug intrinsics. 2856226633Sdim BasicBlock::iterator I = LPInst, E = RI; 2857226633Sdim while (++I != E) 2858226633Sdim if (!isa<DbgInfoIntrinsic>(I)) 2859226633Sdim return false; 2860226633Sdim 2861226633Sdim // Turn all invokes that unwind here into calls and delete the basic block. 2862249423Sdim bool InvokeRequiresTableEntry = false; 2863249423Sdim bool Changed = false; 2864226633Sdim for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;) { 2865226633Sdim InvokeInst *II = cast<InvokeInst>((*PI++)->getTerminator()); 2866249423Sdim 2867249423Sdim if (II->hasFnAttr(Attribute::UWTable)) { 2868249423Sdim // Don't remove an `invoke' instruction if the ABI requires an entry into 2869249423Sdim // the table. 2870249423Sdim InvokeRequiresTableEntry = true; 2871249423Sdim continue; 2872249423Sdim } 2873249423Sdim 2874226633Sdim SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3); 2875249423Sdim 2876226633Sdim // Insert a call instruction before the invoke. 2877226633Sdim CallInst *Call = CallInst::Create(II->getCalledValue(), Args, "", II); 2878226633Sdim Call->takeName(II); 2879226633Sdim Call->setCallingConv(II->getCallingConv()); 2880226633Sdim Call->setAttributes(II->getAttributes()); 2881226633Sdim Call->setDebugLoc(II->getDebugLoc()); 2882226633Sdim 2883226633Sdim // Anything that used the value produced by the invoke instruction now uses 2884226633Sdim // the value produced by the call instruction. Note that we do this even 2885226633Sdim // for void functions and calls with no uses so that the callgraph edge is 2886226633Sdim // updated. 2887226633Sdim II->replaceAllUsesWith(Call); 2888226633Sdim BB->removePredecessor(II->getParent()); 2889226633Sdim 2890226633Sdim // Insert a branch to the normal destination right before the invoke. 2891226633Sdim BranchInst::Create(II->getNormalDest(), II); 2892226633Sdim 2893226633Sdim // Finally, delete the invoke instruction! 2894226633Sdim II->eraseFromParent(); 2895249423Sdim Changed = true; 2896226633Sdim } 2897226633Sdim 2898249423Sdim if (!InvokeRequiresTableEntry) 2899249423Sdim // The landingpad is now unreachable. Zap it. 2900249423Sdim BB->eraseFromParent(); 2901249423Sdim 2902249423Sdim return Changed; 2903226633Sdim} 2904226633Sdim 2905223017Sdimbool SimplifyCFGOpt::SimplifyReturn(ReturnInst *RI, IRBuilder<> &Builder) { 2906218893Sdim BasicBlock *BB = RI->getParent(); 2907218893Sdim if (!BB->getFirstNonPHIOrDbg()->isTerminator()) return false; 2908243830Sdim 2909218893Sdim // Find predecessors that end with branches. 2910218893Sdim SmallVector<BasicBlock*, 8> UncondBranchPreds; 2911218893Sdim SmallVector<BranchInst*, 8> CondBranchPreds; 2912218893Sdim for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 2913218893Sdim BasicBlock *P = *PI; 2914218893Sdim TerminatorInst *PTI = P->getTerminator(); 2915218893Sdim if (BranchInst *BI = dyn_cast<BranchInst>(PTI)) { 2916218893Sdim if (BI->isUnconditional()) 2917218893Sdim UncondBranchPreds.push_back(P); 2918218893Sdim else 2919218893Sdim CondBranchPreds.push_back(BI); 2920193323Sed } 2921218893Sdim } 2922243830Sdim 2923218893Sdim // If we found some, do the transformation! 2924218893Sdim if (!UncondBranchPreds.empty() && DupRet) { 2925218893Sdim while (!UncondBranchPreds.empty()) { 2926218893Sdim BasicBlock *Pred = UncondBranchPreds.pop_back_val(); 2927218893Sdim DEBUG(dbgs() << "FOLDING: " << *BB 2928218893Sdim << "INTO UNCOND BRANCH PRED: " << *Pred); 2929218893Sdim (void)FoldReturnIntoUncondBranch(RI, BB, Pred); 2930218893Sdim } 2931243830Sdim 2932218893Sdim // If we eliminated all predecessors of the block, delete the block now. 2933218893Sdim if (pred_begin(BB) == pred_end(BB)) 2934193323Sed // We know there are no successors, so just nuke the block. 2935218893Sdim BB->eraseFromParent(); 2936243830Sdim 2937218893Sdim return true; 2938218893Sdim } 2939243830Sdim 2940218893Sdim // Check out all of the conditional branches going to this return 2941218893Sdim // instruction. If any of them just select between returns, change the 2942218893Sdim // branch itself into a select/return pair. 2943218893Sdim while (!CondBranchPreds.empty()) { 2944218893Sdim BranchInst *BI = CondBranchPreds.pop_back_val(); 2945243830Sdim 2946218893Sdim // Check to see if the non-BB successor is also a return block. 2947218893Sdim if (isa<ReturnInst>(BI->getSuccessor(0)->getTerminator()) && 2948218893Sdim isa<ReturnInst>(BI->getSuccessor(1)->getTerminator()) && 2949223017Sdim SimplifyCondBranchToTwoReturns(BI, Builder)) 2950193323Sed return true; 2951218893Sdim } 2952218893Sdim return false; 2953218893Sdim} 2954193323Sed 2955218893Sdimbool SimplifyCFGOpt::SimplifyUnreachable(UnreachableInst *UI) { 2956218893Sdim BasicBlock *BB = UI->getParent(); 2957243830Sdim 2958218893Sdim bool Changed = false; 2959243830Sdim 2960218893Sdim // If there are any instructions immediately before the unreachable that can 2961218893Sdim // be removed, do so. 2962218893Sdim while (UI != BB->begin()) { 2963218893Sdim BasicBlock::iterator BBI = UI; 2964218893Sdim --BBI; 2965226633Sdim // Do not delete instructions that can have side effects which might cause 2966226633Sdim // the unreachable to not be reachable; specifically, calls and volatile 2967226633Sdim // operations may have this effect. 2968218893Sdim if (isa<CallInst>(BBI) && !isa<DbgInfoIntrinsic>(BBI)) break; 2969226633Sdim 2970226633Sdim if (BBI->mayHaveSideEffects()) { 2971226633Sdim if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) { 2972226633Sdim if (SI->isVolatile()) 2973226633Sdim break; 2974226633Sdim } else if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) { 2975226633Sdim if (LI->isVolatile()) 2976226633Sdim break; 2977226633Sdim } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(BBI)) { 2978226633Sdim if (RMWI->isVolatile()) 2979226633Sdim break; 2980226633Sdim } else if (AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(BBI)) { 2981226633Sdim if (CXI->isVolatile()) 2982226633Sdim break; 2983226633Sdim } else if (!isa<FenceInst>(BBI) && !isa<VAArgInst>(BBI) && 2984226633Sdim !isa<LandingPadInst>(BBI)) { 2985218893Sdim break; 2986226633Sdim } 2987226633Sdim // Note that deleting LandingPad's here is in fact okay, although it 2988226633Sdim // involves a bit of subtle reasoning. If this inst is a LandingPad, 2989226633Sdim // all the predecessors of this block will be the unwind edges of Invokes, 2990226633Sdim // and we can therefore guarantee this block will be erased. 2991226633Sdim } 2992226633Sdim 2993221345Sdim // Delete this instruction (any uses are guaranteed to be dead) 2994221345Sdim if (!BBI->use_empty()) 2995221345Sdim BBI->replaceAllUsesWith(UndefValue::get(BBI->getType())); 2996218893Sdim BBI->eraseFromParent(); 2997218893Sdim Changed = true; 2998218893Sdim } 2999243830Sdim 3000218893Sdim // If the unreachable instruction is the first in the block, take a gander 3001218893Sdim // at all of the predecessors of this instruction, and simplify them. 3002218893Sdim if (&BB->front() != UI) return Changed; 3003243830Sdim 3004218893Sdim SmallVector<BasicBlock*, 8> Preds(pred_begin(BB), pred_end(BB)); 3005218893Sdim for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 3006218893Sdim TerminatorInst *TI = Preds[i]->getTerminator(); 3007223017Sdim IRBuilder<> Builder(TI); 3008218893Sdim if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 3009218893Sdim if (BI->isUnconditional()) { 3010218893Sdim if (BI->getSuccessor(0) == BB) { 3011218893Sdim new UnreachableInst(TI->getContext(), TI); 3012218893Sdim TI->eraseFromParent(); 3013218893Sdim Changed = true; 3014218893Sdim } 3015218893Sdim } else { 3016218893Sdim if (BI->getSuccessor(0) == BB) { 3017223017Sdim Builder.CreateBr(BI->getSuccessor(1)); 3018218893Sdim EraseTerminatorInstAndDCECond(BI); 3019218893Sdim } else if (BI->getSuccessor(1) == BB) { 3020223017Sdim Builder.CreateBr(BI->getSuccessor(0)); 3021218893Sdim EraseTerminatorInstAndDCECond(BI); 3022218893Sdim Changed = true; 3023218893Sdim } 3024218893Sdim } 3025218893Sdim } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 3026234353Sdim for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 3027234353Sdim i != e; ++i) 3028234353Sdim if (i.getCaseSuccessor() == BB) { 3029218893Sdim BB->removePredecessor(SI->getParent()); 3030218893Sdim SI->removeCase(i); 3031218893Sdim --i; --e; 3032218893Sdim Changed = true; 3033218893Sdim } 3034218893Sdim // If the default value is unreachable, figure out the most popular 3035218893Sdim // destination and make it the default. 3036234353Sdim if (SI->getDefaultDest() == BB) { 3037221345Sdim std::map<BasicBlock*, std::pair<unsigned, unsigned> > Popularity; 3038234353Sdim for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 3039234353Sdim i != e; ++i) { 3040234353Sdim std::pair<unsigned, unsigned> &entry = 3041234353Sdim Popularity[i.getCaseSuccessor()]; 3042221345Sdim if (entry.first == 0) { 3043221345Sdim entry.first = 1; 3044234353Sdim entry.second = i.getCaseIndex(); 3045221345Sdim } else { 3046221345Sdim entry.first++; 3047221345Sdim } 3048221345Sdim } 3049221345Sdim 3050218893Sdim // Find the most popular block. 3051218893Sdim unsigned MaxPop = 0; 3052221345Sdim unsigned MaxIndex = 0; 3053218893Sdim BasicBlock *MaxBlock = 0; 3054221345Sdim for (std::map<BasicBlock*, std::pair<unsigned, unsigned> >::iterator 3055218893Sdim I = Popularity.begin(), E = Popularity.end(); I != E; ++I) { 3056243830Sdim if (I->second.first > MaxPop || 3057221345Sdim (I->second.first == MaxPop && MaxIndex > I->second.second)) { 3058221345Sdim MaxPop = I->second.first; 3059221345Sdim MaxIndex = I->second.second; 3060218893Sdim MaxBlock = I->first; 3061193323Sed } 3062193323Sed } 3063218893Sdim if (MaxBlock) { 3064218893Sdim // Make this the new default, allowing us to delete any explicit 3065218893Sdim // edges to it. 3066234353Sdim SI->setDefaultDest(MaxBlock); 3067218893Sdim Changed = true; 3068243830Sdim 3069218893Sdim // If MaxBlock has phinodes in it, remove MaxPop-1 entries from 3070218893Sdim // it. 3071218893Sdim if (isa<PHINode>(MaxBlock->begin())) 3072218893Sdim for (unsigned i = 0; i != MaxPop-1; ++i) 3073218893Sdim MaxBlock->removePredecessor(SI->getParent()); 3074243830Sdim 3075234353Sdim for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); 3076234353Sdim i != e; ++i) 3077234353Sdim if (i.getCaseSuccessor() == MaxBlock) { 3078218893Sdim SI->removeCase(i); 3079218893Sdim --i; --e; 3080218893Sdim } 3081218893Sdim } 3082193323Sed } 3083218893Sdim } else if (InvokeInst *II = dyn_cast<InvokeInst>(TI)) { 3084218893Sdim if (II->getUnwindDest() == BB) { 3085218893Sdim // Convert the invoke to a call instruction. This would be a good 3086218893Sdim // place to note that the call does not throw though. 3087223017Sdim BranchInst *BI = Builder.CreateBr(II->getNormalDest()); 3088218893Sdim II->removeFromParent(); // Take out of symbol table 3089243830Sdim 3090218893Sdim // Insert the call now... 3091218893Sdim SmallVector<Value*, 8> Args(II->op_begin(), II->op_end()-3); 3092223017Sdim Builder.SetInsertPoint(BI); 3093223017Sdim CallInst *CI = Builder.CreateCall(II->getCalledValue(), 3094224145Sdim Args, II->getName()); 3095218893Sdim CI->setCallingConv(II->getCallingConv()); 3096218893Sdim CI->setAttributes(II->getAttributes()); 3097218893Sdim // If the invoke produced a value, the call does now instead. 3098218893Sdim II->replaceAllUsesWith(CI); 3099218893Sdim delete II; 3100218893Sdim Changed = true; 3101218893Sdim } 3102218893Sdim } 3103218893Sdim } 3104243830Sdim 3105218893Sdim // If this block is now dead, remove it. 3106218893Sdim if (pred_begin(BB) == pred_end(BB) && 3107218893Sdim BB != &BB->getParent()->getEntryBlock()) { 3108218893Sdim // We know there are no successors, so just nuke the block. 3109218893Sdim BB->eraseFromParent(); 3110218893Sdim return true; 3111218893Sdim } 3112193323Sed 3113218893Sdim return Changed; 3114218893Sdim} 3115193323Sed 3116218893Sdim/// TurnSwitchRangeIntoICmp - Turns a switch with that contains only a 3117218893Sdim/// integer range comparison into a sub, an icmp and a branch. 3118223017Sdimstatic bool TurnSwitchRangeIntoICmp(SwitchInst *SI, IRBuilder<> &Builder) { 3119234353Sdim assert(SI->getNumCases() > 1 && "Degenerate switch?"); 3120193323Sed 3121218893Sdim // Make sure all cases point to the same destination and gather the values. 3122218893Sdim SmallVector<ConstantInt *, 16> Cases; 3123234353Sdim SwitchInst::CaseIt I = SI->case_begin(); 3124234353Sdim Cases.push_back(I.getCaseValue()); 3125234353Sdim SwitchInst::CaseIt PrevI = I++; 3126234353Sdim for (SwitchInst::CaseIt E = SI->case_end(); I != E; PrevI = I++) { 3127234353Sdim if (PrevI.getCaseSuccessor() != I.getCaseSuccessor()) 3128218893Sdim return false; 3129234353Sdim Cases.push_back(I.getCaseValue()); 3130218893Sdim } 3131234353Sdim assert(Cases.size() == SI->getNumCases() && "Not all cases gathered"); 3132193323Sed 3133218893Sdim // Sort the case values, then check if they form a range we can transform. 3134218893Sdim array_pod_sort(Cases.begin(), Cases.end(), ConstantIntSortPredicate); 3135218893Sdim for (unsigned I = 1, E = Cases.size(); I != E; ++I) { 3136218893Sdim if (Cases[I-1]->getValue() != Cases[I]->getValue()+1) 3137218893Sdim return false; 3138218893Sdim } 3139193323Sed 3140218893Sdim Constant *Offset = ConstantExpr::getNeg(Cases.back()); 3141234353Sdim Constant *NumCases = ConstantInt::get(Offset->getType(), SI->getNumCases()); 3142193323Sed 3143218893Sdim Value *Sub = SI->getCondition(); 3144218893Sdim if (!Offset->isNullValue()) 3145223017Sdim Sub = Builder.CreateAdd(Sub, Offset, Sub->getName()+".off"); 3146251662Sdim Value *Cmp; 3147251662Sdim // If NumCases overflowed, then all possible values jump to the successor. 3148251662Sdim if (NumCases->isNullValue() && SI->getNumCases() != 0) 3149251662Sdim Cmp = ConstantInt::getTrue(SI->getContext()); 3150251662Sdim else 3151251662Sdim Cmp = Builder.CreateICmpULT(Sub, NumCases, "switch"); 3152243830Sdim BranchInst *NewBI = Builder.CreateCondBr( 3153234353Sdim Cmp, SI->case_begin().getCaseSuccessor(), SI->getDefaultDest()); 3154193323Sed 3155243830Sdim // Update weight for the newly-created conditional branch. 3156243830Sdim SmallVector<uint64_t, 8> Weights; 3157243830Sdim bool HasWeights = HasBranchWeights(SI); 3158243830Sdim if (HasWeights) { 3159243830Sdim GetBranchWeights(SI, Weights); 3160243830Sdim if (Weights.size() == 1 + SI->getNumCases()) { 3161243830Sdim // Combine all weights for the cases to be the true weight of NewBI. 3162243830Sdim // We assume that the sum of all weights for a Terminator can fit into 32 3163243830Sdim // bits. 3164243830Sdim uint32_t NewTrueWeight = 0; 3165243830Sdim for (unsigned I = 1, E = Weights.size(); I != E; ++I) 3166243830Sdim NewTrueWeight += (uint32_t)Weights[I]; 3167243830Sdim NewBI->setMetadata(LLVMContext::MD_prof, 3168243830Sdim MDBuilder(SI->getContext()). 3169243830Sdim createBranchWeights(NewTrueWeight, 3170243830Sdim (uint32_t)Weights[0])); 3171243830Sdim } 3172243830Sdim } 3173243830Sdim 3174218893Sdim // Prune obsolete incoming values off the successor's PHI nodes. 3175234353Sdim for (BasicBlock::iterator BBI = SI->case_begin().getCaseSuccessor()->begin(); 3176218893Sdim isa<PHINode>(BBI); ++BBI) { 3177234353Sdim for (unsigned I = 0, E = SI->getNumCases()-1; I != E; ++I) 3178218893Sdim cast<PHINode>(BBI)->removeIncomingValue(SI->getParent()); 3179218893Sdim } 3180218893Sdim SI->eraseFromParent(); 3181193323Sed 3182218893Sdim return true; 3183218893Sdim} 3184193323Sed 3185223017Sdim/// EliminateDeadSwitchCases - Compute masked bits for the condition of a switch 3186223017Sdim/// and use it to remove dead cases. 3187223017Sdimstatic bool EliminateDeadSwitchCases(SwitchInst *SI) { 3188223017Sdim Value *Cond = SI->getCondition(); 3189263508Sdim unsigned Bits = Cond->getType()->getIntegerBitWidth(); 3190223017Sdim APInt KnownZero(Bits, 0), KnownOne(Bits, 0); 3191234353Sdim ComputeMaskedBits(Cond, KnownZero, KnownOne); 3192223017Sdim 3193223017Sdim // Gather dead cases. 3194223017Sdim SmallVector<ConstantInt*, 8> DeadCases; 3195234353Sdim for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) { 3196234353Sdim if ((I.getCaseValue()->getValue() & KnownZero) != 0 || 3197234353Sdim (I.getCaseValue()->getValue() & KnownOne) != KnownOne) { 3198234353Sdim DeadCases.push_back(I.getCaseValue()); 3199223017Sdim DEBUG(dbgs() << "SimplifyCFG: switch case '" 3200234353Sdim << I.getCaseValue() << "' is dead.\n"); 3201223017Sdim } 3202223017Sdim } 3203223017Sdim 3204243830Sdim SmallVector<uint64_t, 8> Weights; 3205243830Sdim bool HasWeight = HasBranchWeights(SI); 3206243830Sdim if (HasWeight) { 3207243830Sdim GetBranchWeights(SI, Weights); 3208243830Sdim HasWeight = (Weights.size() == 1 + SI->getNumCases()); 3209243830Sdim } 3210243830Sdim 3211223017Sdim // Remove dead cases from the switch. 3212223017Sdim for (unsigned I = 0, E = DeadCases.size(); I != E; ++I) { 3213234353Sdim SwitchInst::CaseIt Case = SI->findCaseValue(DeadCases[I]); 3214234353Sdim assert(Case != SI->case_default() && 3215234353Sdim "Case was not found. Probably mistake in DeadCases forming."); 3216243830Sdim if (HasWeight) { 3217243830Sdim std::swap(Weights[Case.getCaseIndex()+1], Weights.back()); 3218243830Sdim Weights.pop_back(); 3219243830Sdim } 3220243830Sdim 3221223017Sdim // Prune unused values from PHI nodes. 3222234353Sdim Case.getCaseSuccessor()->removePredecessor(SI->getParent()); 3223223017Sdim SI->removeCase(Case); 3224223017Sdim } 3225243830Sdim if (HasWeight) { 3226243830Sdim SmallVector<uint32_t, 8> MDWeights(Weights.begin(), Weights.end()); 3227243830Sdim SI->setMetadata(LLVMContext::MD_prof, 3228243830Sdim MDBuilder(SI->getParent()->getContext()). 3229243830Sdim createBranchWeights(MDWeights)); 3230243830Sdim } 3231223017Sdim 3232223017Sdim return !DeadCases.empty(); 3233223017Sdim} 3234223017Sdim 3235224145Sdim/// FindPHIForConditionForwarding - If BB would be eligible for simplification 3236224145Sdim/// by TryToSimplifyUncondBranchFromEmptyBlock (i.e. it is empty and terminated 3237224145Sdim/// by an unconditional branch), look at the phi node for BB in the successor 3238224145Sdim/// block and see if the incoming value is equal to CaseValue. If so, return 3239224145Sdim/// the phi node, and set PhiIndex to BB's index in the phi node. 3240224145Sdimstatic PHINode *FindPHIForConditionForwarding(ConstantInt *CaseValue, 3241224145Sdim BasicBlock *BB, 3242224145Sdim int *PhiIndex) { 3243224145Sdim if (BB->getFirstNonPHIOrDbg() != BB->getTerminator()) 3244224145Sdim return NULL; // BB must be empty to be a candidate for simplification. 3245224145Sdim if (!BB->getSinglePredecessor()) 3246224145Sdim return NULL; // BB must be dominated by the switch. 3247224145Sdim 3248224145Sdim BranchInst *Branch = dyn_cast<BranchInst>(BB->getTerminator()); 3249224145Sdim if (!Branch || !Branch->isUnconditional()) 3250224145Sdim return NULL; // Terminator must be unconditional branch. 3251224145Sdim 3252224145Sdim BasicBlock *Succ = Branch->getSuccessor(0); 3253224145Sdim 3254224145Sdim BasicBlock::iterator I = Succ->begin(); 3255224145Sdim while (PHINode *PHI = dyn_cast<PHINode>(I++)) { 3256224145Sdim int Idx = PHI->getBasicBlockIndex(BB); 3257224145Sdim assert(Idx >= 0 && "PHI has no entry for predecessor?"); 3258224145Sdim 3259224145Sdim Value *InValue = PHI->getIncomingValue(Idx); 3260224145Sdim if (InValue != CaseValue) continue; 3261224145Sdim 3262224145Sdim *PhiIndex = Idx; 3263224145Sdim return PHI; 3264224145Sdim } 3265224145Sdim 3266224145Sdim return NULL; 3267224145Sdim} 3268224145Sdim 3269224145Sdim/// ForwardSwitchConditionToPHI - Try to forward the condition of a switch 3270224145Sdim/// instruction to a phi node dominated by the switch, if that would mean that 3271224145Sdim/// some of the destination blocks of the switch can be folded away. 3272224145Sdim/// Returns true if a change is made. 3273224145Sdimstatic bool ForwardSwitchConditionToPHI(SwitchInst *SI) { 3274224145Sdim typedef DenseMap<PHINode*, SmallVector<int,4> > ForwardingNodesMap; 3275224145Sdim ForwardingNodesMap ForwardingNodes; 3276224145Sdim 3277234353Sdim for (SwitchInst::CaseIt I = SI->case_begin(), E = SI->case_end(); I != E; ++I) { 3278234353Sdim ConstantInt *CaseValue = I.getCaseValue(); 3279234353Sdim BasicBlock *CaseDest = I.getCaseSuccessor(); 3280224145Sdim 3281224145Sdim int PhiIndex; 3282224145Sdim PHINode *PHI = FindPHIForConditionForwarding(CaseValue, CaseDest, 3283224145Sdim &PhiIndex); 3284224145Sdim if (!PHI) continue; 3285224145Sdim 3286224145Sdim ForwardingNodes[PHI].push_back(PhiIndex); 3287224145Sdim } 3288224145Sdim 3289224145Sdim bool Changed = false; 3290224145Sdim 3291224145Sdim for (ForwardingNodesMap::iterator I = ForwardingNodes.begin(), 3292224145Sdim E = ForwardingNodes.end(); I != E; ++I) { 3293224145Sdim PHINode *Phi = I->first; 3294263508Sdim SmallVectorImpl<int> &Indexes = I->second; 3295224145Sdim 3296224145Sdim if (Indexes.size() < 2) continue; 3297224145Sdim 3298224145Sdim for (size_t I = 0, E = Indexes.size(); I != E; ++I) 3299224145Sdim Phi->setIncomingValue(Indexes[I], SI->getCondition()); 3300224145Sdim Changed = true; 3301224145Sdim } 3302224145Sdim 3303224145Sdim return Changed; 3304224145Sdim} 3305224145Sdim 3306243830Sdim/// ValidLookupTableConstant - Return true if the backend will be able to handle 3307243830Sdim/// initializing an array of constants like C. 3308243830Sdimstatic bool ValidLookupTableConstant(Constant *C) { 3309243830Sdim if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) 3310243830Sdim return CE->isGEPWithNoNotionalOverIndexing(); 3311243830Sdim 3312243830Sdim return isa<ConstantFP>(C) || 3313243830Sdim isa<ConstantInt>(C) || 3314243830Sdim isa<ConstantPointerNull>(C) || 3315243830Sdim isa<GlobalValue>(C) || 3316243830Sdim isa<UndefValue>(C); 3317243830Sdim} 3318243830Sdim 3319243830Sdim/// LookupConstant - If V is a Constant, return it. Otherwise, try to look up 3320243830Sdim/// its constant value in ConstantPool, returning 0 if it's not there. 3321243830Sdimstatic Constant *LookupConstant(Value *V, 3322243830Sdim const SmallDenseMap<Value*, Constant*>& ConstantPool) { 3323243830Sdim if (Constant *C = dyn_cast<Constant>(V)) 3324243830Sdim return C; 3325243830Sdim return ConstantPool.lookup(V); 3326243830Sdim} 3327243830Sdim 3328243830Sdim/// ConstantFold - Try to fold instruction I into a constant. This works for 3329243830Sdim/// simple instructions such as binary operations where both operands are 3330243830Sdim/// constant or can be replaced by constants from the ConstantPool. Returns the 3331243830Sdim/// resulting constant on success, 0 otherwise. 3332263508Sdimstatic Constant * 3333263508SdimConstantFold(Instruction *I, 3334263508Sdim const SmallDenseMap<Value *, Constant *> &ConstantPool, 3335263508Sdim const DataLayout *DL) { 3336243830Sdim if (SelectInst *Select = dyn_cast<SelectInst>(I)) { 3337243830Sdim Constant *A = LookupConstant(Select->getCondition(), ConstantPool); 3338243830Sdim if (!A) 3339243830Sdim return 0; 3340243830Sdim if (A->isAllOnesValue()) 3341243830Sdim return LookupConstant(Select->getTrueValue(), ConstantPool); 3342243830Sdim if (A->isNullValue()) 3343243830Sdim return LookupConstant(Select->getFalseValue(), ConstantPool); 3344243830Sdim return 0; 3345243830Sdim } 3346243830Sdim 3347263508Sdim SmallVector<Constant *, 4> COps; 3348263508Sdim for (unsigned N = 0, E = I->getNumOperands(); N != E; ++N) { 3349263508Sdim if (Constant *A = LookupConstant(I->getOperand(N), ConstantPool)) 3350263508Sdim COps.push_back(A); 3351263508Sdim else 3352243830Sdim return 0; 3353243830Sdim } 3354243830Sdim 3355263508Sdim if (CmpInst *Cmp = dyn_cast<CmpInst>(I)) 3356263508Sdim return ConstantFoldCompareInstOperands(Cmp->getPredicate(), COps[0], 3357263508Sdim COps[1], DL); 3358263508Sdim 3359263508Sdim return ConstantFoldInstOperands(I->getOpcode(), I->getType(), COps, DL); 3360243830Sdim} 3361243830Sdim 3362243830Sdim/// GetCaseResults - Try to determine the resulting constant values in phi nodes 3363243830Sdim/// at the common destination basic block, *CommonDest, for one of the case 3364243830Sdim/// destionations CaseDest corresponding to value CaseVal (0 for the default 3365243830Sdim/// case), of a switch instruction SI. 3366263508Sdimstatic bool 3367263508SdimGetCaseResults(SwitchInst *SI, 3368263508Sdim ConstantInt *CaseVal, 3369263508Sdim BasicBlock *CaseDest, 3370263508Sdim BasicBlock **CommonDest, 3371263508Sdim SmallVectorImpl<std::pair<PHINode *, Constant *> > &Res, 3372263508Sdim const DataLayout *DL) { 3373243830Sdim // The block from which we enter the common destination. 3374243830Sdim BasicBlock *Pred = SI->getParent(); 3375243830Sdim 3376243830Sdim // If CaseDest is empty except for some side-effect free instructions through 3377243830Sdim // which we can constant-propagate the CaseVal, continue to its successor. 3378243830Sdim SmallDenseMap<Value*, Constant*> ConstantPool; 3379243830Sdim ConstantPool.insert(std::make_pair(SI->getCondition(), CaseVal)); 3380243830Sdim for (BasicBlock::iterator I = CaseDest->begin(), E = CaseDest->end(); I != E; 3381243830Sdim ++I) { 3382243830Sdim if (TerminatorInst *T = dyn_cast<TerminatorInst>(I)) { 3383243830Sdim // If the terminator is a simple branch, continue to the next block. 3384243830Sdim if (T->getNumSuccessors() != 1) 3385243830Sdim return false; 3386243830Sdim Pred = CaseDest; 3387243830Sdim CaseDest = T->getSuccessor(0); 3388243830Sdim } else if (isa<DbgInfoIntrinsic>(I)) { 3389243830Sdim // Skip debug intrinsic. 3390243830Sdim continue; 3391263508Sdim } else if (Constant *C = ConstantFold(I, ConstantPool, DL)) { 3392243830Sdim // Instruction is side-effect free and constant. 3393243830Sdim ConstantPool.insert(std::make_pair(I, C)); 3394243830Sdim } else { 3395243830Sdim break; 3396243830Sdim } 3397243830Sdim } 3398243830Sdim 3399243830Sdim // If we did not have a CommonDest before, use the current one. 3400243830Sdim if (!*CommonDest) 3401243830Sdim *CommonDest = CaseDest; 3402243830Sdim // If the destination isn't the common one, abort. 3403243830Sdim if (CaseDest != *CommonDest) 3404218893Sdim return false; 3405193323Sed 3406243830Sdim // Get the values for this case from phi nodes in the destination block. 3407243830Sdim BasicBlock::iterator I = (*CommonDest)->begin(); 3408243830Sdim while (PHINode *PHI = dyn_cast<PHINode>(I++)) { 3409243830Sdim int Idx = PHI->getBasicBlockIndex(Pred); 3410243830Sdim if (Idx == -1) 3411243830Sdim continue; 3412243830Sdim 3413243830Sdim Constant *ConstVal = LookupConstant(PHI->getIncomingValue(Idx), 3414243830Sdim ConstantPool); 3415243830Sdim if (!ConstVal) 3416243830Sdim return false; 3417243830Sdim 3418243830Sdim // Note: If the constant comes from constant-propagating the case value 3419243830Sdim // through the CaseDest basic block, it will be safe to remove the 3420243830Sdim // instructions in that block. They cannot be used (except in the phi nodes 3421243830Sdim // we visit) outside CaseDest, because that block does not dominate its 3422243830Sdim // successor. If it did, we would not be in this phi node. 3423243830Sdim 3424243830Sdim // Be conservative about which kinds of constants we support. 3425243830Sdim if (!ValidLookupTableConstant(ConstVal)) 3426243830Sdim return false; 3427243830Sdim 3428243830Sdim Res.push_back(std::make_pair(PHI, ConstVal)); 3429243830Sdim } 3430243830Sdim 3431243830Sdim return true; 3432243830Sdim} 3433243830Sdim 3434243830Sdimnamespace { 3435243830Sdim /// SwitchLookupTable - This class represents a lookup table that can be used 3436243830Sdim /// to replace a switch. 3437243830Sdim class SwitchLookupTable { 3438243830Sdim public: 3439243830Sdim /// SwitchLookupTable - Create a lookup table to use as a switch replacement 3440243830Sdim /// with the contents of Values, using DefaultValue to fill any holes in the 3441243830Sdim /// table. 3442243830Sdim SwitchLookupTable(Module &M, 3443243830Sdim uint64_t TableSize, 3444243830Sdim ConstantInt *Offset, 3445263508Sdim const SmallVectorImpl<std::pair<ConstantInt*, Constant*> >& Values, 3446243830Sdim Constant *DefaultValue, 3447243830Sdim const DataLayout *TD); 3448243830Sdim 3449243830Sdim /// BuildLookup - Build instructions with Builder to retrieve the value at 3450243830Sdim /// the position given by Index in the lookup table. 3451243830Sdim Value *BuildLookup(Value *Index, IRBuilder<> &Builder); 3452243830Sdim 3453243830Sdim /// WouldFitInRegister - Return true if a table with TableSize elements of 3454243830Sdim /// type ElementType would fit in a target-legal register. 3455243830Sdim static bool WouldFitInRegister(const DataLayout *TD, 3456243830Sdim uint64_t TableSize, 3457243830Sdim const Type *ElementType); 3458243830Sdim 3459243830Sdim private: 3460243830Sdim // Depending on the contents of the table, it can be represented in 3461243830Sdim // different ways. 3462243830Sdim enum { 3463243830Sdim // For tables where each element contains the same value, we just have to 3464243830Sdim // store that single value and return it for each lookup. 3465243830Sdim SingleValueKind, 3466243830Sdim 3467243830Sdim // For small tables with integer elements, we can pack them into a bitmap 3468243830Sdim // that fits into a target-legal register. Values are retrieved by 3469243830Sdim // shift and mask operations. 3470243830Sdim BitMapKind, 3471243830Sdim 3472243830Sdim // The table is stored as an array of values. Values are retrieved by load 3473243830Sdim // instructions from the table. 3474243830Sdim ArrayKind 3475243830Sdim } Kind; 3476243830Sdim 3477243830Sdim // For SingleValueKind, this is the single value. 3478243830Sdim Constant *SingleValue; 3479243830Sdim 3480243830Sdim // For BitMapKind, this is the bitmap. 3481243830Sdim ConstantInt *BitMap; 3482243830Sdim IntegerType *BitMapElementTy; 3483243830Sdim 3484243830Sdim // For ArrayKind, this is the array. 3485243830Sdim GlobalVariable *Array; 3486243830Sdim }; 3487243830Sdim} 3488243830Sdim 3489243830SdimSwitchLookupTable::SwitchLookupTable(Module &M, 3490243830Sdim uint64_t TableSize, 3491243830Sdim ConstantInt *Offset, 3492263508Sdim const SmallVectorImpl<std::pair<ConstantInt*, Constant*> >& Values, 3493243830Sdim Constant *DefaultValue, 3494249423Sdim const DataLayout *TD) 3495249423Sdim : SingleValue(0), BitMap(0), BitMapElementTy(0), Array(0) { 3496243830Sdim assert(Values.size() && "Can't build lookup table without values!"); 3497243830Sdim assert(TableSize >= Values.size() && "Can't fit values in table!"); 3498243830Sdim 3499243830Sdim // If all values in the table are equal, this is that value. 3500243830Sdim SingleValue = Values.begin()->second; 3501243830Sdim 3502243830Sdim // Build up the table contents. 3503243830Sdim SmallVector<Constant*, 64> TableContents(TableSize); 3504243830Sdim for (size_t I = 0, E = Values.size(); I != E; ++I) { 3505243830Sdim ConstantInt *CaseVal = Values[I].first; 3506243830Sdim Constant *CaseRes = Values[I].second; 3507243830Sdim assert(CaseRes->getType() == DefaultValue->getType()); 3508243830Sdim 3509243830Sdim uint64_t Idx = (CaseVal->getValue() - Offset->getValue()) 3510243830Sdim .getLimitedValue(); 3511243830Sdim TableContents[Idx] = CaseRes; 3512243830Sdim 3513243830Sdim if (CaseRes != SingleValue) 3514243830Sdim SingleValue = 0; 3515243830Sdim } 3516243830Sdim 3517243830Sdim // Fill in any holes in the table with the default result. 3518243830Sdim if (Values.size() < TableSize) { 3519243830Sdim for (uint64_t I = 0; I < TableSize; ++I) { 3520243830Sdim if (!TableContents[I]) 3521243830Sdim TableContents[I] = DefaultValue; 3522243830Sdim } 3523243830Sdim 3524243830Sdim if (DefaultValue != SingleValue) 3525243830Sdim SingleValue = 0; 3526243830Sdim } 3527243830Sdim 3528243830Sdim // If each element in the table contains the same value, we only need to store 3529243830Sdim // that single value. 3530243830Sdim if (SingleValue) { 3531243830Sdim Kind = SingleValueKind; 3532243830Sdim return; 3533243830Sdim } 3534243830Sdim 3535243830Sdim // If the type is integer and the table fits in a register, build a bitmap. 3536243830Sdim if (WouldFitInRegister(TD, TableSize, DefaultValue->getType())) { 3537243830Sdim IntegerType *IT = cast<IntegerType>(DefaultValue->getType()); 3538243830Sdim APInt TableInt(TableSize * IT->getBitWidth(), 0); 3539243830Sdim for (uint64_t I = TableSize; I > 0; --I) { 3540243830Sdim TableInt <<= IT->getBitWidth(); 3541243830Sdim // Insert values into the bitmap. Undef values are set to zero. 3542243830Sdim if (!isa<UndefValue>(TableContents[I - 1])) { 3543243830Sdim ConstantInt *Val = cast<ConstantInt>(TableContents[I - 1]); 3544243830Sdim TableInt |= Val->getValue().zext(TableInt.getBitWidth()); 3545243830Sdim } 3546243830Sdim } 3547243830Sdim BitMap = ConstantInt::get(M.getContext(), TableInt); 3548243830Sdim BitMapElementTy = IT; 3549243830Sdim Kind = BitMapKind; 3550243830Sdim ++NumBitMaps; 3551243830Sdim return; 3552243830Sdim } 3553243830Sdim 3554243830Sdim // Store the table in an array. 3555243830Sdim ArrayType *ArrayTy = ArrayType::get(DefaultValue->getType(), TableSize); 3556243830Sdim Constant *Initializer = ConstantArray::get(ArrayTy, TableContents); 3557243830Sdim 3558243830Sdim Array = new GlobalVariable(M, ArrayTy, /*constant=*/ true, 3559243830Sdim GlobalVariable::PrivateLinkage, 3560243830Sdim Initializer, 3561243830Sdim "switch.table"); 3562243830Sdim Array->setUnnamedAddr(true); 3563243830Sdim Kind = ArrayKind; 3564243830Sdim} 3565243830Sdim 3566243830SdimValue *SwitchLookupTable::BuildLookup(Value *Index, IRBuilder<> &Builder) { 3567243830Sdim switch (Kind) { 3568243830Sdim case SingleValueKind: 3569243830Sdim return SingleValue; 3570243830Sdim case BitMapKind: { 3571243830Sdim // Type of the bitmap (e.g. i59). 3572243830Sdim IntegerType *MapTy = BitMap->getType(); 3573243830Sdim 3574243830Sdim // Cast Index to the same type as the bitmap. 3575243830Sdim // Note: The Index is <= the number of elements in the table, so 3576243830Sdim // truncating it to the width of the bitmask is safe. 3577243830Sdim Value *ShiftAmt = Builder.CreateZExtOrTrunc(Index, MapTy, "switch.cast"); 3578243830Sdim 3579243830Sdim // Multiply the shift amount by the element width. 3580243830Sdim ShiftAmt = Builder.CreateMul(ShiftAmt, 3581243830Sdim ConstantInt::get(MapTy, BitMapElementTy->getBitWidth()), 3582243830Sdim "switch.shiftamt"); 3583243830Sdim 3584243830Sdim // Shift down. 3585243830Sdim Value *DownShifted = Builder.CreateLShr(BitMap, ShiftAmt, 3586243830Sdim "switch.downshift"); 3587243830Sdim // Mask off. 3588243830Sdim return Builder.CreateTrunc(DownShifted, BitMapElementTy, 3589243830Sdim "switch.masked"); 3590243830Sdim } 3591243830Sdim case ArrayKind: { 3592243830Sdim Value *GEPIndices[] = { Builder.getInt32(0), Index }; 3593243830Sdim Value *GEP = Builder.CreateInBoundsGEP(Array, GEPIndices, 3594243830Sdim "switch.gep"); 3595243830Sdim return Builder.CreateLoad(GEP, "switch.load"); 3596243830Sdim } 3597243830Sdim } 3598243830Sdim llvm_unreachable("Unknown lookup table kind!"); 3599243830Sdim} 3600243830Sdim 3601243830Sdimbool SwitchLookupTable::WouldFitInRegister(const DataLayout *TD, 3602243830Sdim uint64_t TableSize, 3603243830Sdim const Type *ElementType) { 3604243830Sdim if (!TD) 3605243830Sdim return false; 3606243830Sdim const IntegerType *IT = dyn_cast<IntegerType>(ElementType); 3607243830Sdim if (!IT) 3608243830Sdim return false; 3609243830Sdim // FIXME: If the type is wider than it needs to be, e.g. i8 but all values 3610243830Sdim // are <= 15, we could try to narrow the type. 3611243830Sdim 3612243830Sdim // Avoid overflow, fitsInLegalInteger uses unsigned int for the width. 3613243830Sdim if (TableSize >= UINT_MAX/IT->getBitWidth()) 3614243830Sdim return false; 3615243830Sdim return TD->fitsInLegalInteger(TableSize * IT->getBitWidth()); 3616243830Sdim} 3617243830Sdim 3618243830Sdim/// ShouldBuildLookupTable - Determine whether a lookup table should be built 3619263508Sdim/// for this switch, based on the number of cases, size of the table and the 3620243830Sdim/// types of the results. 3621243830Sdimstatic bool ShouldBuildLookupTable(SwitchInst *SI, 3622243830Sdim uint64_t TableSize, 3623249423Sdim const TargetTransformInfo &TTI, 3624243830Sdim const DataLayout *TD, 3625243830Sdim const SmallDenseMap<PHINode*, Type*>& ResultTypes) { 3626243830Sdim if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10) 3627243830Sdim return false; // TableSize overflowed, or mul below might overflow. 3628243830Sdim 3629249423Sdim bool AllTablesFitInRegister = true; 3630249423Sdim bool HasIllegalType = false; 3631243830Sdim for (SmallDenseMap<PHINode*, Type*>::const_iterator I = ResultTypes.begin(), 3632243830Sdim E = ResultTypes.end(); I != E; ++I) { 3633249423Sdim Type *Ty = I->second; 3634249423Sdim 3635249423Sdim // Saturate this flag to true. 3636249423Sdim HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty); 3637249423Sdim 3638249423Sdim // Saturate this flag to false. 3639249423Sdim AllTablesFitInRegister = AllTablesFitInRegister && 3640249423Sdim SwitchLookupTable::WouldFitInRegister(TD, TableSize, Ty); 3641249423Sdim 3642249423Sdim // If both flags saturate, we're done. NOTE: This *only* works with 3643249423Sdim // saturating flags, and all flags have to saturate first due to the 3644249423Sdim // non-deterministic behavior of iterating over a dense map. 3645249423Sdim if (HasIllegalType && !AllTablesFitInRegister) 3646249423Sdim break; 3647243830Sdim } 3648249423Sdim 3649249423Sdim // If each table would fit in a register, we should build it anyway. 3650249423Sdim if (AllTablesFitInRegister) 3651249423Sdim return true; 3652249423Sdim 3653249423Sdim // Don't build a table that doesn't fit in-register if it has illegal types. 3654249423Sdim if (HasIllegalType) 3655249423Sdim return false; 3656249423Sdim 3657249423Sdim // The table density should be at least 40%. This is the same criterion as for 3658249423Sdim // jump tables, see SelectionDAGBuilder::handleJTSwitchCase. 3659249423Sdim // FIXME: Find the best cut-off. 3660249423Sdim return SI->getNumCases() * 10 >= TableSize * 4; 3661243830Sdim} 3662243830Sdim 3663243830Sdim/// SwitchToLookupTable - If the switch is only used to initialize one or more 3664243830Sdim/// phi nodes in a common successor block with different constant values, 3665243830Sdim/// replace the switch with lookup tables. 3666243830Sdimstatic bool SwitchToLookupTable(SwitchInst *SI, 3667243830Sdim IRBuilder<> &Builder, 3668249423Sdim const TargetTransformInfo &TTI, 3669249423Sdim const DataLayout* TD) { 3670243830Sdim assert(SI->getNumCases() > 1 && "Degenerate switch?"); 3671243830Sdim 3672243830Sdim // Only build lookup table when we have a target that supports it. 3673249423Sdim if (!TTI.shouldBuildLookupTables()) 3674243830Sdim return false; 3675243830Sdim 3676243830Sdim // FIXME: If the switch is too sparse for a lookup table, perhaps we could 3677243830Sdim // split off a dense part and build a lookup table for that. 3678243830Sdim 3679243830Sdim // FIXME: This creates arrays of GEPs to constant strings, which means each 3680243830Sdim // GEP needs a runtime relocation in PIC code. We should just build one big 3681243830Sdim // string and lookup indices into that. 3682243830Sdim 3683243830Sdim // Ignore the switch if the number of cases is too small. 3684243830Sdim // This is similar to the check when building jump tables in 3685243830Sdim // SelectionDAGBuilder::handleJTSwitchCase. 3686243830Sdim // FIXME: Determine the best cut-off. 3687243830Sdim if (SI->getNumCases() < 4) 3688243830Sdim return false; 3689243830Sdim 3690243830Sdim // Figure out the corresponding result for each case value and phi node in the 3691243830Sdim // common destination, as well as the the min and max case values. 3692243830Sdim assert(SI->case_begin() != SI->case_end()); 3693243830Sdim SwitchInst::CaseIt CI = SI->case_begin(); 3694243830Sdim ConstantInt *MinCaseVal = CI.getCaseValue(); 3695243830Sdim ConstantInt *MaxCaseVal = CI.getCaseValue(); 3696243830Sdim 3697243830Sdim BasicBlock *CommonDest = 0; 3698243830Sdim typedef SmallVector<std::pair<ConstantInt*, Constant*>, 4> ResultListTy; 3699243830Sdim SmallDenseMap<PHINode*, ResultListTy> ResultLists; 3700243830Sdim SmallDenseMap<PHINode*, Constant*> DefaultResults; 3701243830Sdim SmallDenseMap<PHINode*, Type*> ResultTypes; 3702243830Sdim SmallVector<PHINode*, 4> PHIs; 3703243830Sdim 3704243830Sdim for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) { 3705243830Sdim ConstantInt *CaseVal = CI.getCaseValue(); 3706243830Sdim if (CaseVal->getValue().slt(MinCaseVal->getValue())) 3707243830Sdim MinCaseVal = CaseVal; 3708243830Sdim if (CaseVal->getValue().sgt(MaxCaseVal->getValue())) 3709243830Sdim MaxCaseVal = CaseVal; 3710243830Sdim 3711243830Sdim // Resulting value at phi nodes for this case value. 3712243830Sdim typedef SmallVector<std::pair<PHINode*, Constant*>, 4> ResultsTy; 3713243830Sdim ResultsTy Results; 3714243830Sdim if (!GetCaseResults(SI, CaseVal, CI.getCaseSuccessor(), &CommonDest, 3715263508Sdim Results, TD)) 3716243830Sdim return false; 3717243830Sdim 3718243830Sdim // Append the result from this case to the list for each phi. 3719243830Sdim for (ResultsTy::iterator I = Results.begin(), E = Results.end(); I!=E; ++I) { 3720243830Sdim if (!ResultLists.count(I->first)) 3721243830Sdim PHIs.push_back(I->first); 3722243830Sdim ResultLists[I->first].push_back(std::make_pair(CaseVal, I->second)); 3723243830Sdim } 3724243830Sdim } 3725243830Sdim 3726243830Sdim // Get the resulting values for the default case. 3727243830Sdim SmallVector<std::pair<PHINode*, Constant*>, 4> DefaultResultsList; 3728243830Sdim if (!GetCaseResults(SI, 0, SI->getDefaultDest(), &CommonDest, 3729263508Sdim DefaultResultsList, TD)) 3730243830Sdim return false; 3731243830Sdim for (size_t I = 0, E = DefaultResultsList.size(); I != E; ++I) { 3732243830Sdim PHINode *PHI = DefaultResultsList[I].first; 3733243830Sdim Constant *Result = DefaultResultsList[I].second; 3734243830Sdim DefaultResults[PHI] = Result; 3735243830Sdim ResultTypes[PHI] = Result->getType(); 3736243830Sdim } 3737243830Sdim 3738243830Sdim APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue(); 3739243830Sdim uint64_t TableSize = RangeSpread.getLimitedValue() + 1; 3740249423Sdim if (!ShouldBuildLookupTable(SI, TableSize, TTI, TD, ResultTypes)) 3741243830Sdim return false; 3742243830Sdim 3743243830Sdim // Create the BB that does the lookups. 3744243830Sdim Module &Mod = *CommonDest->getParent()->getParent(); 3745243830Sdim BasicBlock *LookupBB = BasicBlock::Create(Mod.getContext(), 3746243830Sdim "switch.lookup", 3747243830Sdim CommonDest->getParent(), 3748243830Sdim CommonDest); 3749243830Sdim 3750263508Sdim // Compute the table index value. 3751243830Sdim Builder.SetInsertPoint(SI); 3752243830Sdim Value *TableIndex = Builder.CreateSub(SI->getCondition(), MinCaseVal, 3753243830Sdim "switch.tableidx"); 3754243830Sdim 3755263508Sdim // Compute the maximum table size representable by the integer type we are 3756263508Sdim // switching upon. 3757263508Sdim unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits(); 3758263508Sdim uint64_t MaxTableSize = CaseSize > 63? UINT64_MAX : 1ULL << CaseSize; 3759263508Sdim assert(MaxTableSize >= TableSize && 3760263508Sdim "It is impossible for a switch to have more entries than the max " 3761263508Sdim "representable value of its input integer type's size."); 3762263508Sdim 3763263508Sdim // If we have a fully covered lookup table, unconditionally branch to the 3764263508Sdim // lookup table BB. Otherwise, check if the condition value is within the case 3765263508Sdim // range. If it is so, branch to the new BB. Otherwise branch to SI's default 3766263508Sdim // destination. 3767263508Sdim const bool GeneratingCoveredLookupTable = MaxTableSize == TableSize; 3768263508Sdim if (GeneratingCoveredLookupTable) { 3769263508Sdim Builder.CreateBr(LookupBB); 3770263508Sdim SI->getDefaultDest()->removePredecessor(SI->getParent()); 3771263508Sdim } else { 3772263508Sdim Value *Cmp = Builder.CreateICmpULT(TableIndex, ConstantInt::get( 3773263508Sdim MinCaseVal->getType(), TableSize)); 3774263508Sdim Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest()); 3775263508Sdim } 3776263508Sdim 3777243830Sdim // Populate the BB that does the lookups. 3778243830Sdim Builder.SetInsertPoint(LookupBB); 3779243830Sdim bool ReturnedEarly = false; 3780243830Sdim for (size_t I = 0, E = PHIs.size(); I != E; ++I) { 3781243830Sdim PHINode *PHI = PHIs[I]; 3782243830Sdim 3783243830Sdim SwitchLookupTable Table(Mod, TableSize, MinCaseVal, ResultLists[PHI], 3784243830Sdim DefaultResults[PHI], TD); 3785243830Sdim 3786243830Sdim Value *Result = Table.BuildLookup(TableIndex, Builder); 3787243830Sdim 3788243830Sdim // If the result is used to return immediately from the function, we want to 3789243830Sdim // do that right here. 3790243830Sdim if (PHI->hasOneUse() && isa<ReturnInst>(*PHI->use_begin()) && 3791243830Sdim *PHI->use_begin() == CommonDest->getFirstNonPHIOrDbg()) { 3792243830Sdim Builder.CreateRet(Result); 3793243830Sdim ReturnedEarly = true; 3794243830Sdim break; 3795243830Sdim } 3796243830Sdim 3797243830Sdim PHI->addIncoming(Result, LookupBB); 3798243830Sdim } 3799243830Sdim 3800243830Sdim if (!ReturnedEarly) 3801243830Sdim Builder.CreateBr(CommonDest); 3802243830Sdim 3803243830Sdim // Remove the switch. 3804263508Sdim for (unsigned i = 0, e = SI->getNumSuccessors(); i < e; ++i) { 3805243830Sdim BasicBlock *Succ = SI->getSuccessor(i); 3806263508Sdim 3807263508Sdim if (Succ == SI->getDefaultDest()) 3808263508Sdim continue; 3809243830Sdim Succ->removePredecessor(SI->getParent()); 3810243830Sdim } 3811243830Sdim SI->eraseFromParent(); 3812243830Sdim 3813243830Sdim ++NumLookupTables; 3814243830Sdim return true; 3815243830Sdim} 3816243830Sdim 3817243830Sdimbool SimplifyCFGOpt::SimplifySwitch(SwitchInst *SI, IRBuilder<> &Builder) { 3818218893Sdim BasicBlock *BB = SI->getParent(); 3819193323Sed 3820243830Sdim if (isValueEqualityComparison(SI)) { 3821243830Sdim // If we only have one predecessor, and if it is a branch on this value, 3822243830Sdim // see if that predecessor totally determines the outcome of this switch. 3823243830Sdim if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 3824243830Sdim if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder)) 3825249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3826221345Sdim 3827243830Sdim Value *Cond = SI->getCondition(); 3828243830Sdim if (SelectInst *Select = dyn_cast<SelectInst>(Cond)) 3829243830Sdim if (SimplifySwitchOnSelect(SI, Select)) 3830249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3831221345Sdim 3832243830Sdim // If the block only contains the switch, see if we can fold the block 3833243830Sdim // away into any preds. 3834243830Sdim BasicBlock::iterator BBI = BB->begin(); 3835243830Sdim // Ignore dbg intrinsics. 3836243830Sdim while (isa<DbgInfoIntrinsic>(BBI)) 3837243830Sdim ++BBI; 3838243830Sdim if (SI == &*BBI) 3839243830Sdim if (FoldValueComparisonIntoPredecessors(SI, Builder)) 3840249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3841243830Sdim } 3842193323Sed 3843218893Sdim // Try to transform the switch into an icmp and a branch. 3844223017Sdim if (TurnSwitchRangeIntoICmp(SI, Builder)) 3845249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3846223017Sdim 3847223017Sdim // Remove unreachable cases. 3848223017Sdim if (EliminateDeadSwitchCases(SI)) 3849249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3850223017Sdim 3851224145Sdim if (ForwardSwitchConditionToPHI(SI)) 3852249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3853224145Sdim 3854249423Sdim if (SwitchToLookupTable(SI, Builder, TTI, TD)) 3855249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3856243830Sdim 3857218893Sdim return false; 3858218893Sdim} 3859193323Sed 3860218893Sdimbool SimplifyCFGOpt::SimplifyIndirectBr(IndirectBrInst *IBI) { 3861218893Sdim BasicBlock *BB = IBI->getParent(); 3862218893Sdim bool Changed = false; 3863243830Sdim 3864218893Sdim // Eliminate redundant destinations. 3865218893Sdim SmallPtrSet<Value *, 8> Succs; 3866218893Sdim for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) { 3867218893Sdim BasicBlock *Dest = IBI->getDestination(i); 3868218893Sdim if (!Dest->hasAddressTaken() || !Succs.insert(Dest)) { 3869218893Sdim Dest->removePredecessor(BB); 3870218893Sdim IBI->removeDestination(i); 3871218893Sdim --i; --e; 3872218893Sdim Changed = true; 3873218893Sdim } 3874243830Sdim } 3875193323Sed 3876218893Sdim if (IBI->getNumDestinations() == 0) { 3877218893Sdim // If the indirectbr has no successors, change it to unreachable. 3878218893Sdim new UnreachableInst(IBI->getContext(), IBI); 3879218893Sdim EraseTerminatorInstAndDCECond(IBI); 3880218893Sdim return true; 3881218893Sdim } 3882243830Sdim 3883218893Sdim if (IBI->getNumDestinations() == 1) { 3884218893Sdim // If the indirectbr has one successor, change it to a direct branch. 3885218893Sdim BranchInst::Create(IBI->getDestination(0), IBI); 3886218893Sdim EraseTerminatorInstAndDCECond(IBI); 3887218893Sdim return true; 3888218893Sdim } 3889243830Sdim 3890218893Sdim if (SelectInst *SI = dyn_cast<SelectInst>(IBI->getAddress())) { 3891218893Sdim if (SimplifyIndirectBrOnSelect(IBI, SI)) 3892249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3893218893Sdim } 3894218893Sdim return Changed; 3895218893Sdim} 3896218893Sdim 3897223017Sdimbool SimplifyCFGOpt::SimplifyUncondBranch(BranchInst *BI, IRBuilder<> &Builder){ 3898218893Sdim BasicBlock *BB = BI->getParent(); 3899243830Sdim 3900243830Sdim if (SinkCommon && SinkThenElseCodeToEnd(BI)) 3901243830Sdim return true; 3902243830Sdim 3903218893Sdim // If the Terminator is the only non-phi instruction, simplify the block. 3904224145Sdim BasicBlock::iterator I = BB->getFirstNonPHIOrDbgOrLifetime(); 3905218893Sdim if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && 3906218893Sdim TryToSimplifyUncondBranchFromEmptyBlock(BB)) 3907218893Sdim return true; 3908243830Sdim 3909218893Sdim // If the only instruction in the block is a seteq/setne comparison 3910218893Sdim // against a constant, try to simplify the block. 3911218893Sdim if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) 3912218893Sdim if (ICI->isEquality() && isa<ConstantInt>(ICI->getOperand(1))) { 3913218893Sdim for (++I; isa<DbgInfoIntrinsic>(I); ++I) 3914218893Sdim ; 3915234353Sdim if (I->isTerminator() && 3916249423Sdim TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, TTI, TD)) 3917193323Sed return true; 3918193323Sed } 3919243830Sdim 3920239462Sdim // If this basic block is ONLY a compare and a branch, and if a predecessor 3921239462Sdim // branches to us and our successor, fold the comparison into the 3922239462Sdim // predecessor and use logical operations to update the incoming value 3923239462Sdim // for PHI nodes in common successor. 3924239462Sdim if (FoldBranchToCommonDest(BI)) 3925249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3926218893Sdim return false; 3927218893Sdim} 3928212904Sdim 3929218893Sdim 3930223017Sdimbool SimplifyCFGOpt::SimplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { 3931218893Sdim BasicBlock *BB = BI->getParent(); 3932243830Sdim 3933218893Sdim // Conditional branch 3934218893Sdim if (isValueEqualityComparison(BI)) { 3935218893Sdim // If we only have one predecessor, and if it is a branch on this value, 3936218893Sdim // see if that predecessor totally determines the outcome of this 3937218893Sdim // switch. 3938218893Sdim if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) 3939223017Sdim if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder)) 3940249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3941243830Sdim 3942218893Sdim // This block must be empty, except for the setcond inst, if it exists. 3943218893Sdim // Ignore dbg intrinsics. 3944218893Sdim BasicBlock::iterator I = BB->begin(); 3945218893Sdim // Ignore dbg intrinsics. 3946218893Sdim while (isa<DbgInfoIntrinsic>(I)) 3947218893Sdim ++I; 3948218893Sdim if (&*I == BI) { 3949223017Sdim if (FoldValueComparisonIntoPredecessors(BI, Builder)) 3950249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3951218893Sdim } else if (&*I == cast<Instruction>(BI->getCondition())){ 3952218893Sdim ++I; 3953218893Sdim // Ignore dbg intrinsics. 3954218893Sdim while (isa<DbgInfoIntrinsic>(I)) 3955218893Sdim ++I; 3956223017Sdim if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder)) 3957249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3958212904Sdim } 3959193323Sed } 3960243830Sdim 3961218893Sdim // Try to turn "br (X == 0 | X == 1), T, F" into a switch instruction. 3962223017Sdim if (SimplifyBranchOnICmpChain(BI, TD, Builder)) 3963193323Sed return true; 3964243830Sdim 3965234353Sdim // If this basic block is ONLY a compare and a branch, and if a predecessor 3966234353Sdim // branches to us and one of our successors, fold the comparison into the 3967234353Sdim // predecessor and use logical operations to pick the right destination. 3968234353Sdim if (FoldBranchToCommonDest(BI)) 3969249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3970243830Sdim 3971218893Sdim // We have a conditional branch to two blocks that are only reachable 3972218893Sdim // from BI. We know that the condbr dominates the two blocks, so see if 3973218893Sdim // there is any identical code in the "then" and "else" blocks. If so, we 3974218893Sdim // can hoist it up to the branching block. 3975218893Sdim if (BI->getSuccessor(0)->getSinglePredecessor() != 0) { 3976218893Sdim if (BI->getSuccessor(1)->getSinglePredecessor() != 0) { 3977218893Sdim if (HoistThenElseCodeToIf(BI)) 3978249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3979218893Sdim } else { 3980218893Sdim // If Successor #1 has multiple preds, we may be able to conditionally 3981218893Sdim // execute Successor #0 if it branches to successor #1. 3982218893Sdim TerminatorInst *Succ0TI = BI->getSuccessor(0)->getTerminator(); 3983218893Sdim if (Succ0TI->getNumSuccessors() == 1 && 3984218893Sdim Succ0TI->getSuccessor(0) == BI->getSuccessor(1)) 3985218893Sdim if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0))) 3986249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3987193323Sed } 3988218893Sdim } else if (BI->getSuccessor(1)->getSinglePredecessor() != 0) { 3989218893Sdim // If Successor #0 has multiple preds, we may be able to conditionally 3990218893Sdim // execute Successor #1 if it branches to successor #0. 3991218893Sdim TerminatorInst *Succ1TI = BI->getSuccessor(1)->getTerminator(); 3992218893Sdim if (Succ1TI->getNumSuccessors() == 1 && 3993218893Sdim Succ1TI->getSuccessor(0) == BI->getSuccessor(0)) 3994218893Sdim if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1))) 3995249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 3996212904Sdim } 3997243830Sdim 3998218893Sdim // If this is a branch on a phi node in the current block, thread control 3999218893Sdim // through this block if any PHI node entries are constants. 4000218893Sdim if (PHINode *PN = dyn_cast<PHINode>(BI->getCondition())) 4001218893Sdim if (PN->getParent() == BI->getParent()) 4002218893Sdim if (FoldCondBranchOnPHI(BI, TD)) 4003249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 4004243830Sdim 4005218893Sdim // Scan predecessor blocks for conditional branches. 4006218893Sdim for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 4007218893Sdim if (BranchInst *PBI = dyn_cast<BranchInst>((*PI)->getTerminator())) 4008218893Sdim if (PBI != BI && PBI->isConditional()) 4009218893Sdim if (SimplifyCondBranchToCondBranch(PBI, BI)) 4010249423Sdim return SimplifyCFG(BB, TTI, TD) | true; 4011193323Sed 4012218893Sdim return false; 4013218893Sdim} 4014193323Sed 4015226633Sdim/// Check if passing a value to an instruction will cause undefined behavior. 4016226633Sdimstatic bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) { 4017226633Sdim Constant *C = dyn_cast<Constant>(V); 4018226633Sdim if (!C) 4019226633Sdim return false; 4020226633Sdim 4021243830Sdim if (I->use_empty()) 4022226633Sdim return false; 4023226633Sdim 4024226633Sdim if (C->isNullValue()) { 4025243830Sdim // Only look at the first use, avoid hurting compile time with long uselists 4026243830Sdim User *Use = *I->use_begin(); 4027226633Sdim 4028226633Sdim // Now make sure that there are no instructions in between that can alter 4029226633Sdim // control flow (eg. calls) 4030226633Sdim for (BasicBlock::iterator i = ++BasicBlock::iterator(I); &*i != Use; ++i) 4031226633Sdim if (i == I->getParent()->end() || i->mayHaveSideEffects()) 4032226633Sdim return false; 4033226633Sdim 4034226633Sdim // Look through GEPs. A load from a GEP derived from NULL is still undefined 4035226633Sdim if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Use)) 4036226633Sdim if (GEP->getPointerOperand() == I) 4037226633Sdim return passingValueIsAlwaysUndefined(V, GEP); 4038226633Sdim 4039226633Sdim // Look through bitcasts. 4040226633Sdim if (BitCastInst *BC = dyn_cast<BitCastInst>(Use)) 4041226633Sdim return passingValueIsAlwaysUndefined(V, BC); 4042226633Sdim 4043226633Sdim // Load from null is undefined. 4044226633Sdim if (LoadInst *LI = dyn_cast<LoadInst>(Use)) 4045249423Sdim if (!LI->isVolatile()) 4046249423Sdim return LI->getPointerAddressSpace() == 0; 4047226633Sdim 4048226633Sdim // Store to null is undefined. 4049226633Sdim if (StoreInst *SI = dyn_cast<StoreInst>(Use)) 4050249423Sdim if (!SI->isVolatile()) 4051249423Sdim return SI->getPointerAddressSpace() == 0 && SI->getPointerOperand() == I; 4052226633Sdim } 4053226633Sdim return false; 4054226633Sdim} 4055226633Sdim 4056226633Sdim/// If BB has an incoming value that will always trigger undefined behavior 4057234353Sdim/// (eg. null pointer dereference), remove the branch leading here. 4058226633Sdimstatic bool removeUndefIntroducingPredecessor(BasicBlock *BB) { 4059226633Sdim for (BasicBlock::iterator i = BB->begin(); 4060226633Sdim PHINode *PHI = dyn_cast<PHINode>(i); ++i) 4061226633Sdim for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) 4062226633Sdim if (passingValueIsAlwaysUndefined(PHI->getIncomingValue(i), PHI)) { 4063226633Sdim TerminatorInst *T = PHI->getIncomingBlock(i)->getTerminator(); 4064226633Sdim IRBuilder<> Builder(T); 4065226633Sdim if (BranchInst *BI = dyn_cast<BranchInst>(T)) { 4066226633Sdim BB->removePredecessor(PHI->getIncomingBlock(i)); 4067226633Sdim // Turn uncoditional branches into unreachables and remove the dead 4068226633Sdim // destination from conditional branches. 4069226633Sdim if (BI->isUnconditional()) 4070226633Sdim Builder.CreateUnreachable(); 4071226633Sdim else 4072226633Sdim Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) : 4073226633Sdim BI->getSuccessor(0)); 4074226633Sdim BI->eraseFromParent(); 4075226633Sdim return true; 4076226633Sdim } 4077226633Sdim // TODO: SwitchInst. 4078226633Sdim } 4079226633Sdim 4080226633Sdim return false; 4081226633Sdim} 4082226633Sdim 4083218893Sdimbool SimplifyCFGOpt::run(BasicBlock *BB) { 4084218893Sdim bool Changed = false; 4085193323Sed 4086218893Sdim assert(BB && BB->getParent() && "Block not embedded in function!"); 4087218893Sdim assert(BB->getTerminator() && "Degenerate basic block encountered!"); 4088193323Sed 4089218893Sdim // Remove basic blocks that have no predecessors (except the entry block)... 4090218893Sdim // or that just have themself as a predecessor. These are unreachable. 4091218893Sdim if ((pred_begin(BB) == pred_end(BB) && 4092218893Sdim BB != &BB->getParent()->getEntryBlock()) || 4093218893Sdim BB->getSinglePredecessor() == BB) { 4094218893Sdim DEBUG(dbgs() << "Removing BB: \n" << *BB); 4095218893Sdim DeleteDeadBlock(BB); 4096218893Sdim return true; 4097218893Sdim } 4098203954Srdivacky 4099218893Sdim // Check to see if we can constant propagate this terminator instruction 4100218893Sdim // away... 4101223017Sdim Changed |= ConstantFoldTerminator(BB, true); 4102193323Sed 4103218893Sdim // Check for and eliminate duplicate PHI nodes in this block. 4104218893Sdim Changed |= EliminateDuplicatePHINodes(BB); 4105193323Sed 4106226633Sdim // Check for and remove branches that will always cause undefined behavior. 4107226633Sdim Changed |= removeUndefIntroducingPredecessor(BB); 4108226633Sdim 4109218893Sdim // Merge basic blocks into their predecessor if there is only one distinct 4110218893Sdim // pred, and if there is only one distinct successor of the predecessor, and 4111218893Sdim // if there are no PHI nodes. 4112218893Sdim // 4113218893Sdim if (MergeBlockIntoPredecessor(BB)) 4114218893Sdim return true; 4115243830Sdim 4116223017Sdim IRBuilder<> Builder(BB); 4117223017Sdim 4118218893Sdim // If there is a trivial two-entry PHI node in this basic block, and we can 4119218893Sdim // eliminate it, do so now. 4120218893Sdim if (PHINode *PN = dyn_cast<PHINode>(BB->begin())) 4121218893Sdim if (PN->getNumIncomingValues() == 2) 4122218893Sdim Changed |= FoldTwoEntryPHINode(PN, TD); 4123193323Sed 4124223017Sdim Builder.SetInsertPoint(BB->getTerminator()); 4125218893Sdim if (BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator())) { 4126218893Sdim if (BI->isUnconditional()) { 4127223017Sdim if (SimplifyUncondBranch(BI, Builder)) return true; 4128218893Sdim } else { 4129223017Sdim if (SimplifyCondBranch(BI, Builder)) return true; 4130218893Sdim } 4131234353Sdim } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 4132234353Sdim if (SimplifyReturn(RI, Builder)) return true; 4133226633Sdim } else if (ResumeInst *RI = dyn_cast<ResumeInst>(BB->getTerminator())) { 4134226633Sdim if (SimplifyResume(RI, Builder)) return true; 4135218893Sdim } else if (SwitchInst *SI = dyn_cast<SwitchInst>(BB->getTerminator())) { 4136223017Sdim if (SimplifySwitch(SI, Builder)) return true; 4137218893Sdim } else if (UnreachableInst *UI = 4138218893Sdim dyn_cast<UnreachableInst>(BB->getTerminator())) { 4139218893Sdim if (SimplifyUnreachable(UI)) return true; 4140218893Sdim } else if (IndirectBrInst *IBI = 4141218893Sdim dyn_cast<IndirectBrInst>(BB->getTerminator())) { 4142218893Sdim if (SimplifyIndirectBr(IBI)) return true; 4143218893Sdim } 4144193323Sed 4145193323Sed return Changed; 4146193323Sed} 4147203954Srdivacky 4148203954Srdivacky/// SimplifyCFG - This function is used to do simplification of a CFG. For 4149203954Srdivacky/// example, it adjusts branches to branches to eliminate the extra hop, it 4150203954Srdivacky/// eliminates unreachable basic blocks, and does other "peephole" optimization 4151203954Srdivacky/// of the CFG. It returns true if a modification was made. 4152203954Srdivacky/// 4153249423Sdimbool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, 4154249423Sdim const DataLayout *TD) { 4155249423Sdim return SimplifyCFGOpt(TTI, TD).run(BB); 4156203954Srdivacky} 4157