InstCombineMulDivRem.cpp revision 224145
1202375Srdivacky//===- InstCombineMulDivRem.cpp -------------------------------------------===// 2202375Srdivacky// 3202375Srdivacky// The LLVM Compiler Infrastructure 4202375Srdivacky// 5202375Srdivacky// This file is distributed under the University of Illinois Open Source 6202375Srdivacky// License. See LICENSE.TXT for details. 7202375Srdivacky// 8202375Srdivacky//===----------------------------------------------------------------------===// 9202375Srdivacky// 10202375Srdivacky// This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv, 11202375Srdivacky// srem, urem, frem. 12202375Srdivacky// 13202375Srdivacky//===----------------------------------------------------------------------===// 14202375Srdivacky 15202375Srdivacky#include "InstCombine.h" 16202375Srdivacky#include "llvm/IntrinsicInst.h" 17218893Sdim#include "llvm/Analysis/InstructionSimplify.h" 18202375Srdivacky#include "llvm/Support/PatternMatch.h" 19202375Srdivackyusing namespace llvm; 20202375Srdivackyusing namespace PatternMatch; 21202375Srdivacky 22223017Sdim 23223017Sdim/// simplifyValueKnownNonZero - The specific integer value is used in a context 24223017Sdim/// where it is known to be non-zero. If this allows us to simplify the 25223017Sdim/// computation, do so and return the new operand, otherwise return null. 26223017Sdimstatic Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC) { 27223017Sdim // If V has multiple uses, then we would have to do more analysis to determine 28223017Sdim // if this is safe. For example, the use could be in dynamically unreached 29223017Sdim // code. 30223017Sdim if (!V->hasOneUse()) return 0; 31223017Sdim 32223017Sdim bool MadeChange = false; 33223017Sdim 34223017Sdim // ((1 << A) >>u B) --> (1 << (A-B)) 35223017Sdim // Because V cannot be zero, we know that B is less than A. 36223017Sdim Value *A = 0, *B = 0, *PowerOf2 = 0; 37223017Sdim if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(PowerOf2), m_Value(A))), 38223017Sdim m_Value(B))) && 39223017Sdim // The "1" can be any value known to be a power of 2. 40223017Sdim isPowerOfTwo(PowerOf2, IC.getTargetData())) { 41223017Sdim A = IC.Builder->CreateSub(A, B, "tmp"); 42223017Sdim return IC.Builder->CreateShl(PowerOf2, A); 43223017Sdim } 44223017Sdim 45223017Sdim // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it 46223017Sdim // inexact. Similarly for <<. 47223017Sdim if (BinaryOperator *I = dyn_cast<BinaryOperator>(V)) 48223017Sdim if (I->isLogicalShift() && 49223017Sdim isPowerOfTwo(I->getOperand(0), IC.getTargetData())) { 50223017Sdim // We know that this is an exact/nuw shift and that the input is a 51223017Sdim // non-zero context as well. 52223017Sdim if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC)) { 53223017Sdim I->setOperand(0, V2); 54223017Sdim MadeChange = true; 55223017Sdim } 56223017Sdim 57223017Sdim if (I->getOpcode() == Instruction::LShr && !I->isExact()) { 58223017Sdim I->setIsExact(); 59223017Sdim MadeChange = true; 60223017Sdim } 61223017Sdim 62223017Sdim if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) { 63223017Sdim I->setHasNoUnsignedWrap(); 64223017Sdim MadeChange = true; 65223017Sdim } 66223017Sdim } 67223017Sdim 68223017Sdim // TODO: Lots more we could do here: 69223017Sdim // If V is a phi node, we can call this on each of its operands. 70223017Sdim // "select cond, X, 0" can simplify to "X". 71223017Sdim 72223017Sdim return MadeChange ? V : 0; 73223017Sdim} 74223017Sdim 75223017Sdim 76202375Srdivacky/// MultiplyOverflows - True if the multiply can not be expressed in an int 77202375Srdivacky/// this size. 78202375Srdivackystatic bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) { 79202375Srdivacky uint32_t W = C1->getBitWidth(); 80202375Srdivacky APInt LHSExt = C1->getValue(), RHSExt = C2->getValue(); 81202375Srdivacky if (sign) { 82218893Sdim LHSExt = LHSExt.sext(W * 2); 83218893Sdim RHSExt = RHSExt.sext(W * 2); 84202375Srdivacky } else { 85218893Sdim LHSExt = LHSExt.zext(W * 2); 86218893Sdim RHSExt = RHSExt.zext(W * 2); 87202375Srdivacky } 88202375Srdivacky 89202375Srdivacky APInt MulExt = LHSExt * RHSExt; 90202375Srdivacky 91202375Srdivacky if (!sign) 92202375Srdivacky return MulExt.ugt(APInt::getLowBitsSet(W * 2, W)); 93202375Srdivacky 94202375Srdivacky APInt Min = APInt::getSignedMinValue(W).sext(W * 2); 95202375Srdivacky APInt Max = APInt::getSignedMaxValue(W).sext(W * 2); 96202375Srdivacky return MulExt.slt(Min) || MulExt.sgt(Max); 97202375Srdivacky} 98202375Srdivacky 99202375SrdivackyInstruction *InstCombiner::visitMul(BinaryOperator &I) { 100218893Sdim bool Changed = SimplifyAssociativeOrCommutative(I); 101202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 102202375Srdivacky 103218893Sdim if (Value *V = SimplifyMulInst(Op0, Op1, TD)) 104218893Sdim return ReplaceInstUsesWith(I, V); 105202375Srdivacky 106218893Sdim if (Value *V = SimplifyUsingDistributiveLaws(I)) 107218893Sdim return ReplaceInstUsesWith(I, V); 108202375Srdivacky 109218893Sdim if (match(Op1, m_AllOnes())) // X * -1 == 0 - X 110218893Sdim return BinaryOperator::CreateNeg(Op0, I.getName()); 111218893Sdim 112218893Sdim if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 113218893Sdim 114218893Sdim // ((X << C1)*C2) == (X * (C2 << C1)) 115218893Sdim if (BinaryOperator *SI = dyn_cast<BinaryOperator>(Op0)) 116218893Sdim if (SI->getOpcode() == Instruction::Shl) 117218893Sdim if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1))) 118218893Sdim return BinaryOperator::CreateMul(SI->getOperand(0), 119218893Sdim ConstantExpr::getShl(CI, ShOp)); 120218893Sdim 121218893Sdim const APInt &Val = CI->getValue(); 122218893Sdim if (Val.isPowerOf2()) { // Replace X*(2^C) with X << C 123218893Sdim Constant *NewCst = ConstantInt::get(Op0->getType(), Val.logBase2()); 124218893Sdim BinaryOperator *Shl = BinaryOperator::CreateShl(Op0, NewCst); 125218893Sdim if (I.hasNoSignedWrap()) Shl->setHasNoSignedWrap(); 126218893Sdim if (I.hasNoUnsignedWrap()) Shl->setHasNoUnsignedWrap(); 127218893Sdim return Shl; 128202375Srdivacky } 129202375Srdivacky 130218893Sdim // Canonicalize (X+C1)*CI -> X*CI+C1*CI. 131218893Sdim { Value *X; ConstantInt *C1; 132218893Sdim if (Op0->hasOneUse() && 133218893Sdim match(Op0, m_Add(m_Value(X), m_ConstantInt(C1)))) { 134218893Sdim Value *Add = Builder->CreateMul(X, CI, "tmp"); 135218893Sdim return BinaryOperator::CreateAdd(Add, Builder->CreateMul(C1, CI)); 136202375Srdivacky } 137218893Sdim } 138223017Sdim 139223017Sdim // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n 140223017Sdim // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n 141223017Sdim // The "* (2**n)" thus becomes a potential shifting opportunity. 142223017Sdim { 143223017Sdim const APInt & Val = CI->getValue(); 144223017Sdim const APInt &PosVal = Val.abs(); 145223017Sdim if (Val.isNegative() && PosVal.isPowerOf2()) { 146223017Sdim Value *X = 0, *Y = 0; 147223017Sdim if (Op0->hasOneUse()) { 148223017Sdim ConstantInt *C1; 149223017Sdim Value *Sub = 0; 150223017Sdim if (match(Op0, m_Sub(m_Value(Y), m_Value(X)))) 151223017Sdim Sub = Builder->CreateSub(X, Y, "suba"); 152223017Sdim else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1)))) 153223017Sdim Sub = Builder->CreateSub(Builder->CreateNeg(C1), Y, "subc"); 154223017Sdim if (Sub) 155223017Sdim return 156223017Sdim BinaryOperator::CreateMul(Sub, 157223017Sdim ConstantInt::get(Y->getType(), PosVal)); 158223017Sdim } 159223017Sdim } 160223017Sdim } 161218893Sdim } 162218893Sdim 163218893Sdim // Simplify mul instructions with a constant RHS. 164218893Sdim if (isa<Constant>(Op1)) { 165202375Srdivacky // Try to fold constant mul into select arguments. 166202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 167202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 168202375Srdivacky return R; 169202375Srdivacky 170202375Srdivacky if (isa<PHINode>(Op0)) 171202375Srdivacky if (Instruction *NV = FoldOpIntoPhi(I)) 172202375Srdivacky return NV; 173202375Srdivacky } 174202375Srdivacky 175202375Srdivacky if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y 176202375Srdivacky if (Value *Op1v = dyn_castNegVal(Op1)) 177202375Srdivacky return BinaryOperator::CreateMul(Op0v, Op1v); 178202375Srdivacky 179202375Srdivacky // (X / Y) * Y = X - (X % Y) 180202375Srdivacky // (X / Y) * -Y = (X % Y) - X 181202375Srdivacky { 182202375Srdivacky Value *Op1C = Op1; 183202375Srdivacky BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0); 184202375Srdivacky if (!BO || 185202375Srdivacky (BO->getOpcode() != Instruction::UDiv && 186202375Srdivacky BO->getOpcode() != Instruction::SDiv)) { 187202375Srdivacky Op1C = Op0; 188202375Srdivacky BO = dyn_cast<BinaryOperator>(Op1); 189202375Srdivacky } 190202375Srdivacky Value *Neg = dyn_castNegVal(Op1C); 191202375Srdivacky if (BO && BO->hasOneUse() && 192202375Srdivacky (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) && 193202375Srdivacky (BO->getOpcode() == Instruction::UDiv || 194202375Srdivacky BO->getOpcode() == Instruction::SDiv)) { 195202375Srdivacky Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1); 196202375Srdivacky 197218893Sdim // If the division is exact, X % Y is zero, so we end up with X or -X. 198218893Sdim if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO)) 199202375Srdivacky if (SDiv->isExact()) { 200202375Srdivacky if (Op1BO == Op1C) 201202375Srdivacky return ReplaceInstUsesWith(I, Op0BO); 202202375Srdivacky return BinaryOperator::CreateNeg(Op0BO); 203202375Srdivacky } 204202375Srdivacky 205202375Srdivacky Value *Rem; 206202375Srdivacky if (BO->getOpcode() == Instruction::UDiv) 207202375Srdivacky Rem = Builder->CreateURem(Op0BO, Op1BO); 208202375Srdivacky else 209202375Srdivacky Rem = Builder->CreateSRem(Op0BO, Op1BO); 210202375Srdivacky Rem->takeName(BO); 211202375Srdivacky 212202375Srdivacky if (Op1BO == Op1C) 213202375Srdivacky return BinaryOperator::CreateSub(Op0BO, Rem); 214202375Srdivacky return BinaryOperator::CreateSub(Rem, Op0BO); 215202375Srdivacky } 216202375Srdivacky } 217202375Srdivacky 218202375Srdivacky /// i1 mul -> i1 and. 219203954Srdivacky if (I.getType()->isIntegerTy(1)) 220202375Srdivacky return BinaryOperator::CreateAnd(Op0, Op1); 221202375Srdivacky 222202375Srdivacky // X*(1 << Y) --> X << Y 223202375Srdivacky // (1 << Y)*X --> X << Y 224202375Srdivacky { 225202375Srdivacky Value *Y; 226202375Srdivacky if (match(Op0, m_Shl(m_One(), m_Value(Y)))) 227202375Srdivacky return BinaryOperator::CreateShl(Op1, Y); 228202375Srdivacky if (match(Op1, m_Shl(m_One(), m_Value(Y)))) 229202375Srdivacky return BinaryOperator::CreateShl(Op0, Y); 230202375Srdivacky } 231202375Srdivacky 232202375Srdivacky // If one of the operands of the multiply is a cast from a boolean value, then 233202375Srdivacky // we know the bool is either zero or one, so this is a 'masking' multiply. 234202375Srdivacky // X * Y (where Y is 0 or 1) -> X & (0-Y) 235204642Srdivacky if (!I.getType()->isVectorTy()) { 236202375Srdivacky // -2 is "-1 << 1" so it is all bits set except the low one. 237202375Srdivacky APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true); 238202375Srdivacky 239202375Srdivacky Value *BoolCast = 0, *OtherOp = 0; 240202375Srdivacky if (MaskedValueIsZero(Op0, Negative2)) 241202375Srdivacky BoolCast = Op0, OtherOp = Op1; 242202375Srdivacky else if (MaskedValueIsZero(Op1, Negative2)) 243202375Srdivacky BoolCast = Op1, OtherOp = Op0; 244202375Srdivacky 245202375Srdivacky if (BoolCast) { 246202375Srdivacky Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()), 247202375Srdivacky BoolCast, "tmp"); 248202375Srdivacky return BinaryOperator::CreateAnd(V, OtherOp); 249202375Srdivacky } 250202375Srdivacky } 251202375Srdivacky 252202375Srdivacky return Changed ? &I : 0; 253202375Srdivacky} 254202375Srdivacky 255202375SrdivackyInstruction *InstCombiner::visitFMul(BinaryOperator &I) { 256218893Sdim bool Changed = SimplifyAssociativeOrCommutative(I); 257202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 258202375Srdivacky 259202375Srdivacky // Simplify mul instructions with a constant RHS... 260202375Srdivacky if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 261202375Srdivacky if (ConstantFP *Op1F = dyn_cast<ConstantFP>(Op1C)) { 262202375Srdivacky // "In IEEE floating point, x*1 is not equivalent to x for nans. However, 263202375Srdivacky // ANSI says we can drop signals, so we can do this anyway." (from GCC) 264202375Srdivacky if (Op1F->isExactlyValue(1.0)) 265204642Srdivacky return ReplaceInstUsesWith(I, Op0); // Eliminate 'fmul double %X, 1.0' 266204642Srdivacky } else if (Op1C->getType()->isVectorTy()) { 267202375Srdivacky if (ConstantVector *Op1V = dyn_cast<ConstantVector>(Op1C)) { 268202375Srdivacky // As above, vector X*splat(1.0) -> X in all defined cases. 269202375Srdivacky if (Constant *Splat = Op1V->getSplatValue()) { 270202375Srdivacky if (ConstantFP *F = dyn_cast<ConstantFP>(Splat)) 271202375Srdivacky if (F->isExactlyValue(1.0)) 272202375Srdivacky return ReplaceInstUsesWith(I, Op0); 273202375Srdivacky } 274202375Srdivacky } 275202375Srdivacky } 276202375Srdivacky 277202375Srdivacky // Try to fold constant mul into select arguments. 278202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 279202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 280202375Srdivacky return R; 281202375Srdivacky 282202375Srdivacky if (isa<PHINode>(Op0)) 283202375Srdivacky if (Instruction *NV = FoldOpIntoPhi(I)) 284202375Srdivacky return NV; 285202375Srdivacky } 286202375Srdivacky 287202375Srdivacky if (Value *Op0v = dyn_castFNegVal(Op0)) // -X * -Y = X*Y 288202375Srdivacky if (Value *Op1v = dyn_castFNegVal(Op1)) 289202375Srdivacky return BinaryOperator::CreateFMul(Op0v, Op1v); 290202375Srdivacky 291202375Srdivacky return Changed ? &I : 0; 292202375Srdivacky} 293202375Srdivacky 294202375Srdivacky/// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select 295202375Srdivacky/// instruction. 296202375Srdivackybool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { 297202375Srdivacky SelectInst *SI = cast<SelectInst>(I.getOperand(1)); 298202375Srdivacky 299202375Srdivacky // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y 300202375Srdivacky int NonNullOperand = -1; 301202375Srdivacky if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1))) 302202375Srdivacky if (ST->isNullValue()) 303202375Srdivacky NonNullOperand = 2; 304202375Srdivacky // div/rem X, (Cond ? Y : 0) -> div/rem X, Y 305202375Srdivacky if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2))) 306202375Srdivacky if (ST->isNullValue()) 307202375Srdivacky NonNullOperand = 1; 308202375Srdivacky 309202375Srdivacky if (NonNullOperand == -1) 310202375Srdivacky return false; 311202375Srdivacky 312202375Srdivacky Value *SelectCond = SI->getOperand(0); 313202375Srdivacky 314202375Srdivacky // Change the div/rem to use 'Y' instead of the select. 315202375Srdivacky I.setOperand(1, SI->getOperand(NonNullOperand)); 316202375Srdivacky 317202375Srdivacky // Okay, we know we replace the operand of the div/rem with 'Y' with no 318202375Srdivacky // problem. However, the select, or the condition of the select may have 319202375Srdivacky // multiple uses. Based on our knowledge that the operand must be non-zero, 320202375Srdivacky // propagate the known value for the select into other uses of it, and 321202375Srdivacky // propagate a known value of the condition into its other users. 322202375Srdivacky 323202375Srdivacky // If the select and condition only have a single use, don't bother with this, 324202375Srdivacky // early exit. 325202375Srdivacky if (SI->use_empty() && SelectCond->hasOneUse()) 326202375Srdivacky return true; 327202375Srdivacky 328202375Srdivacky // Scan the current block backward, looking for other uses of SI. 329202375Srdivacky BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin(); 330202375Srdivacky 331202375Srdivacky while (BBI != BBFront) { 332202375Srdivacky --BBI; 333202375Srdivacky // If we found a call to a function, we can't assume it will return, so 334202375Srdivacky // information from below it cannot be propagated above it. 335202375Srdivacky if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI)) 336202375Srdivacky break; 337202375Srdivacky 338202375Srdivacky // Replace uses of the select or its condition with the known values. 339202375Srdivacky for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end(); 340202375Srdivacky I != E; ++I) { 341202375Srdivacky if (*I == SI) { 342202375Srdivacky *I = SI->getOperand(NonNullOperand); 343202375Srdivacky Worklist.Add(BBI); 344202375Srdivacky } else if (*I == SelectCond) { 345202375Srdivacky *I = NonNullOperand == 1 ? ConstantInt::getTrue(BBI->getContext()) : 346202375Srdivacky ConstantInt::getFalse(BBI->getContext()); 347202375Srdivacky Worklist.Add(BBI); 348202375Srdivacky } 349202375Srdivacky } 350202375Srdivacky 351202375Srdivacky // If we past the instruction, quit looking for it. 352202375Srdivacky if (&*BBI == SI) 353202375Srdivacky SI = 0; 354202375Srdivacky if (&*BBI == SelectCond) 355202375Srdivacky SelectCond = 0; 356202375Srdivacky 357202375Srdivacky // If we ran out of things to eliminate, break out of the loop. 358202375Srdivacky if (SelectCond == 0 && SI == 0) 359202375Srdivacky break; 360202375Srdivacky 361202375Srdivacky } 362202375Srdivacky return true; 363202375Srdivacky} 364202375Srdivacky 365202375Srdivacky 366202375Srdivacky/// This function implements the transforms common to both integer division 367202375Srdivacky/// instructions (udiv and sdiv). It is called by the visitors to those integer 368202375Srdivacky/// division instructions. 369202375Srdivacky/// @brief Common integer divide transforms 370202375SrdivackyInstruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { 371202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 372202375Srdivacky 373223017Sdim // The RHS is known non-zero. 374223017Sdim if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 375223017Sdim I.setOperand(1, V); 376223017Sdim return &I; 377223017Sdim } 378223017Sdim 379202375Srdivacky // Handle cases involving: [su]div X, (select Cond, Y, Z) 380202375Srdivacky // This does not apply for fdiv. 381202375Srdivacky if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 382202375Srdivacky return &I; 383202375Srdivacky 384202375Srdivacky if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 385202375Srdivacky // (X / C1) / C2 -> X / (C1*C2) 386202375Srdivacky if (Instruction *LHS = dyn_cast<Instruction>(Op0)) 387202375Srdivacky if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode()) 388202375Srdivacky if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) { 389202375Srdivacky if (MultiplyOverflows(RHS, LHSRHS, 390202375Srdivacky I.getOpcode()==Instruction::SDiv)) 391202375Srdivacky return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 392218893Sdim return BinaryOperator::Create(I.getOpcode(), LHS->getOperand(0), 393218893Sdim ConstantExpr::getMul(RHS, LHSRHS)); 394202375Srdivacky } 395202375Srdivacky 396202375Srdivacky if (!RHS->isZero()) { // avoid X udiv 0 397202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 398202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 399202375Srdivacky return R; 400202375Srdivacky if (isa<PHINode>(Op0)) 401202375Srdivacky if (Instruction *NV = FoldOpIntoPhi(I)) 402202375Srdivacky return NV; 403202375Srdivacky } 404202375Srdivacky } 405202375Srdivacky 406221345Sdim // See if we can fold away this div instruction. 407221345Sdim if (SimplifyDemandedInstructionBits(I)) 408221345Sdim return &I; 409221345Sdim 410218893Sdim // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y 411218893Sdim Value *X = 0, *Z = 0; 412218893Sdim if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1 413218893Sdim bool isSigned = I.getOpcode() == Instruction::SDiv; 414218893Sdim if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || 415218893Sdim (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) 416218893Sdim return BinaryOperator::Create(I.getOpcode(), X, Op1); 417202375Srdivacky } 418202375Srdivacky 419202375Srdivacky return 0; 420202375Srdivacky} 421202375Srdivacky 422221345Sdim/// dyn_castZExtVal - Checks if V is a zext or constant that can 423221345Sdim/// be truncated to Ty without losing bits. 424221345Sdimstatic Value *dyn_castZExtVal(Value *V, const Type *Ty) { 425221345Sdim if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) { 426221345Sdim if (Z->getSrcTy() == Ty) 427221345Sdim return Z->getOperand(0); 428221345Sdim } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) { 429221345Sdim if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth()) 430221345Sdim return ConstantExpr::getTrunc(C, Ty); 431221345Sdim } 432221345Sdim return 0; 433221345Sdim} 434221345Sdim 435202375SrdivackyInstruction *InstCombiner::visitUDiv(BinaryOperator &I) { 436202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 437202375Srdivacky 438218893Sdim if (Value *V = SimplifyUDivInst(Op0, Op1, TD)) 439218893Sdim return ReplaceInstUsesWith(I, V); 440218893Sdim 441202375Srdivacky // Handle the integer div common cases 442202375Srdivacky if (Instruction *Common = commonIDivTransforms(I)) 443202375Srdivacky return Common; 444202375Srdivacky 445202375Srdivacky if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) { 446202878Srdivacky // X udiv 2^C -> X >> C 447202375Srdivacky // Check to see if this is an unsigned division with an exact power of 2, 448202375Srdivacky // if so, convert to a right shift. 449218893Sdim if (C->getValue().isPowerOf2()) { // 0 not included in isPowerOf2 450218893Sdim BinaryOperator *LShr = 451218893Sdim BinaryOperator::CreateLShr(Op0, 452202375Srdivacky ConstantInt::get(Op0->getType(), C->getValue().logBase2())); 453218893Sdim if (I.isExact()) LShr->setIsExact(); 454218893Sdim return LShr; 455218893Sdim } 456202375Srdivacky 457202375Srdivacky // X udiv C, where C >= signbit 458202375Srdivacky if (C->getValue().isNegative()) { 459218893Sdim Value *IC = Builder->CreateICmpULT(Op0, C); 460202375Srdivacky return SelectInst::Create(IC, Constant::getNullValue(I.getType()), 461202375Srdivacky ConstantInt::get(I.getType(), 1)); 462202375Srdivacky } 463202375Srdivacky } 464202375Srdivacky 465202375Srdivacky // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 466218893Sdim { const APInt *CI; Value *N; 467218893Sdim if (match(Op1, m_Shl(m_Power2(CI), m_Value(N)))) { 468218893Sdim if (*CI != 1) 469218893Sdim N = Builder->CreateAdd(N, ConstantInt::get(I.getType(), CI->logBase2()), 470218893Sdim "tmp"); 471218893Sdim if (I.isExact()) 472218893Sdim return BinaryOperator::CreateExactLShr(Op0, N); 473218893Sdim return BinaryOperator::CreateLShr(Op0, N); 474202375Srdivacky } 475202375Srdivacky } 476202375Srdivacky 477202375Srdivacky // udiv X, (Select Cond, C1, C2) --> Select Cond, (shr X, C1), (shr X, C2) 478202375Srdivacky // where C1&C2 are powers of two. 479218893Sdim { Value *Cond; const APInt *C1, *C2; 480218893Sdim if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) { 481218893Sdim // Construct the "on true" case of the select 482218893Sdim Value *TSI = Builder->CreateLShr(Op0, C1->logBase2(), Op1->getName()+".t", 483218893Sdim I.isExact()); 484202375Srdivacky 485218893Sdim // Construct the "on false" case of the select 486218893Sdim Value *FSI = Builder->CreateLShr(Op0, C2->logBase2(), Op1->getName()+".f", 487218893Sdim I.isExact()); 488218893Sdim 489218893Sdim // construct the select instruction and return it. 490218893Sdim return SelectInst::Create(Cond, TSI, FSI); 491218893Sdim } 492218893Sdim } 493221345Sdim 494221345Sdim // (zext A) udiv (zext B) --> zext (A udiv B) 495221345Sdim if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 496221345Sdim if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 497221345Sdim return new ZExtInst(Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", 498221345Sdim I.isExact()), 499221345Sdim I.getType()); 500221345Sdim 501202375Srdivacky return 0; 502202375Srdivacky} 503202375Srdivacky 504202375SrdivackyInstruction *InstCombiner::visitSDiv(BinaryOperator &I) { 505202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 506202375Srdivacky 507218893Sdim if (Value *V = SimplifySDivInst(Op0, Op1, TD)) 508218893Sdim return ReplaceInstUsesWith(I, V); 509218893Sdim 510202375Srdivacky // Handle the integer div common cases 511202375Srdivacky if (Instruction *Common = commonIDivTransforms(I)) 512202375Srdivacky return Common; 513202375Srdivacky 514202375Srdivacky if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 515202375Srdivacky // sdiv X, -1 == -X 516202375Srdivacky if (RHS->isAllOnesValue()) 517202375Srdivacky return BinaryOperator::CreateNeg(Op0); 518202375Srdivacky 519218893Sdim // sdiv X, C --> ashr exact X, log2(C) 520218893Sdim if (I.isExact() && RHS->getValue().isNonNegative() && 521202375Srdivacky RHS->getValue().isPowerOf2()) { 522202375Srdivacky Value *ShAmt = llvm::ConstantInt::get(RHS->getType(), 523202375Srdivacky RHS->getValue().exactLogBase2()); 524218893Sdim return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName()); 525202375Srdivacky } 526202375Srdivacky 527202375Srdivacky // -X/C --> X/-C provided the negation doesn't overflow. 528202375Srdivacky if (SubOperator *Sub = dyn_cast<SubOperator>(Op0)) 529218893Sdim if (match(Sub->getOperand(0), m_Zero()) && Sub->hasNoSignedWrap()) 530202375Srdivacky return BinaryOperator::CreateSDiv(Sub->getOperand(1), 531202375Srdivacky ConstantExpr::getNeg(RHS)); 532202375Srdivacky } 533202375Srdivacky 534202375Srdivacky // If the sign bits of both operands are zero (i.e. we can prove they are 535202375Srdivacky // unsigned inputs), turn this into a udiv. 536203954Srdivacky if (I.getType()->isIntegerTy()) { 537202375Srdivacky APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 538202375Srdivacky if (MaskedValueIsZero(Op0, Mask)) { 539202375Srdivacky if (MaskedValueIsZero(Op1, Mask)) { 540202375Srdivacky // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set 541202375Srdivacky return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 542202375Srdivacky } 543218893Sdim 544218893Sdim if (match(Op1, m_Shl(m_Power2(), m_Value()))) { 545202375Srdivacky // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) 546202375Srdivacky // Safe because the only negative value (1 << Y) can take on is 547202375Srdivacky // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have 548202375Srdivacky // the sign bit set. 549202375Srdivacky return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 550202375Srdivacky } 551202375Srdivacky } 552202375Srdivacky } 553202375Srdivacky 554202375Srdivacky return 0; 555202375Srdivacky} 556202375Srdivacky 557202375SrdivackyInstruction *InstCombiner::visitFDiv(BinaryOperator &I) { 558218893Sdim Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 559218893Sdim 560218893Sdim if (Value *V = SimplifyFDivInst(Op0, Op1, TD)) 561218893Sdim return ReplaceInstUsesWith(I, V); 562218893Sdim 563221345Sdim if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) { 564221345Sdim const APFloat &Op1F = Op1C->getValueAPF(); 565202375Srdivacky 566221345Sdim // If the divisor has an exact multiplicative inverse we can turn the fdiv 567221345Sdim // into a cheaper fmul. 568221345Sdim APFloat Reciprocal(Op1F.getSemantics()); 569221345Sdim if (Op1F.getExactInverse(&Reciprocal)) { 570221345Sdim ConstantFP *RFP = ConstantFP::get(Builder->getContext(), Reciprocal); 571221345Sdim return BinaryOperator::CreateFMul(Op0, RFP); 572221345Sdim } 573202375Srdivacky } 574202375Srdivacky 575202375Srdivacky return 0; 576202375Srdivacky} 577202375Srdivacky 578202375Srdivacky/// This function implements the transforms common to both integer remainder 579202375Srdivacky/// instructions (urem and srem). It is called by the visitors to those integer 580202375Srdivacky/// remainder instructions. 581202375Srdivacky/// @brief Common integer remainder transforms 582202375SrdivackyInstruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) { 583202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 584202375Srdivacky 585223017Sdim // The RHS is known non-zero. 586223017Sdim if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 587223017Sdim I.setOperand(1, V); 588223017Sdim return &I; 589223017Sdim } 590223017Sdim 591221345Sdim // Handle cases involving: rem X, (select Cond, Y, Z) 592221345Sdim if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 593221345Sdim return &I; 594202375Srdivacky 595223017Sdim if (isa<ConstantInt>(Op1)) { 596202375Srdivacky if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { 597202375Srdivacky if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { 598202375Srdivacky if (Instruction *R = FoldOpIntoSelect(I, SI)) 599202375Srdivacky return R; 600202375Srdivacky } else if (isa<PHINode>(Op0I)) { 601202375Srdivacky if (Instruction *NV = FoldOpIntoPhi(I)) 602202375Srdivacky return NV; 603202375Srdivacky } 604202375Srdivacky 605202375Srdivacky // See if we can fold away this rem instruction. 606202375Srdivacky if (SimplifyDemandedInstructionBits(I)) 607202375Srdivacky return &I; 608202375Srdivacky } 609202375Srdivacky } 610202375Srdivacky 611202375Srdivacky return 0; 612202375Srdivacky} 613202375Srdivacky 614202375SrdivackyInstruction *InstCombiner::visitURem(BinaryOperator &I) { 615202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 616202375Srdivacky 617221345Sdim if (Value *V = SimplifyURemInst(Op0, Op1, TD)) 618221345Sdim return ReplaceInstUsesWith(I, V); 619221345Sdim 620202375Srdivacky if (Instruction *common = commonIRemTransforms(I)) 621202375Srdivacky return common; 622202375Srdivacky 623218893Sdim // X urem C^2 -> X and C-1 624218893Sdim { const APInt *C; 625218893Sdim if (match(Op1, m_Power2(C))) 626218893Sdim return BinaryOperator::CreateAnd(Op0, 627218893Sdim ConstantInt::get(I.getType(), *C-1)); 628202375Srdivacky } 629202375Srdivacky 630218893Sdim // Turn A % (C << N), where C is 2^k, into A & ((C << N)-1) 631218893Sdim if (match(Op1, m_Shl(m_Power2(), m_Value()))) { 632218893Sdim Constant *N1 = Constant::getAllOnesValue(I.getType()); 633218893Sdim Value *Add = Builder->CreateAdd(Op1, N1, "tmp"); 634218893Sdim return BinaryOperator::CreateAnd(Op0, Add); 635202375Srdivacky } 636202375Srdivacky 637218893Sdim // urem X, (select Cond, 2^C1, 2^C2) --> 638218893Sdim // select Cond, (and X, C1-1), (and X, C2-1) 639218893Sdim // when C1&C2 are powers of two. 640218893Sdim { Value *Cond; const APInt *C1, *C2; 641218893Sdim if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) { 642218893Sdim Value *TrueAnd = Builder->CreateAnd(Op0, *C1-1, Op1->getName()+".t"); 643218893Sdim Value *FalseAnd = Builder->CreateAnd(Op0, *C2-1, Op1->getName()+".f"); 644218893Sdim return SelectInst::Create(Cond, TrueAnd, FalseAnd); 645218893Sdim } 646202375Srdivacky } 647221345Sdim 648221345Sdim // (zext A) urem (zext B) --> zext (A urem B) 649221345Sdim if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 650221345Sdim if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 651221345Sdim return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), 652221345Sdim I.getType()); 653221345Sdim 654202375Srdivacky return 0; 655202375Srdivacky} 656202375Srdivacky 657202375SrdivackyInstruction *InstCombiner::visitSRem(BinaryOperator &I) { 658202375Srdivacky Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 659202375Srdivacky 660221345Sdim if (Value *V = SimplifySRemInst(Op0, Op1, TD)) 661221345Sdim return ReplaceInstUsesWith(I, V); 662221345Sdim 663202375Srdivacky // Handle the integer rem common cases 664202375Srdivacky if (Instruction *Common = commonIRemTransforms(I)) 665202375Srdivacky return Common; 666202375Srdivacky 667202375Srdivacky if (Value *RHSNeg = dyn_castNegVal(Op1)) 668202375Srdivacky if (!isa<Constant>(RHSNeg) || 669202375Srdivacky (isa<ConstantInt>(RHSNeg) && 670202375Srdivacky cast<ConstantInt>(RHSNeg)->getValue().isStrictlyPositive())) { 671202375Srdivacky // X % -Y -> X % Y 672202375Srdivacky Worklist.AddValue(I.getOperand(1)); 673202375Srdivacky I.setOperand(1, RHSNeg); 674202375Srdivacky return &I; 675202375Srdivacky } 676202375Srdivacky 677202375Srdivacky // If the sign bits of both operands are zero (i.e. we can prove they are 678202375Srdivacky // unsigned inputs), turn this into a urem. 679203954Srdivacky if (I.getType()->isIntegerTy()) { 680202375Srdivacky APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 681202375Srdivacky if (MaskedValueIsZero(Op1, Mask) && MaskedValueIsZero(Op0, Mask)) { 682202375Srdivacky // X srem Y -> X urem Y, iff X and Y don't have sign bit set 683202375Srdivacky return BinaryOperator::CreateURem(Op0, Op1, I.getName()); 684202375Srdivacky } 685202375Srdivacky } 686202375Srdivacky 687202375Srdivacky // If it's a constant vector, flip any negative values positive. 688202375Srdivacky if (ConstantVector *RHSV = dyn_cast<ConstantVector>(Op1)) { 689202375Srdivacky unsigned VWidth = RHSV->getNumOperands(); 690202375Srdivacky 691202375Srdivacky bool hasNegative = false; 692202375Srdivacky for (unsigned i = 0; !hasNegative && i != VWidth; ++i) 693202375Srdivacky if (ConstantInt *RHS = dyn_cast<ConstantInt>(RHSV->getOperand(i))) 694224145Sdim if (RHS->isNegative()) 695202375Srdivacky hasNegative = true; 696202375Srdivacky 697202375Srdivacky if (hasNegative) { 698202375Srdivacky std::vector<Constant *> Elts(VWidth); 699202375Srdivacky for (unsigned i = 0; i != VWidth; ++i) { 700202375Srdivacky if (ConstantInt *RHS = dyn_cast<ConstantInt>(RHSV->getOperand(i))) { 701224145Sdim if (RHS->isNegative()) 702202375Srdivacky Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); 703202375Srdivacky else 704202375Srdivacky Elts[i] = RHS; 705202375Srdivacky } 706202375Srdivacky } 707202375Srdivacky 708202375Srdivacky Constant *NewRHSV = ConstantVector::get(Elts); 709202375Srdivacky if (NewRHSV != RHSV) { 710202375Srdivacky Worklist.AddValue(I.getOperand(1)); 711202375Srdivacky I.setOperand(1, NewRHSV); 712202375Srdivacky return &I; 713202375Srdivacky } 714202375Srdivacky } 715202375Srdivacky } 716202375Srdivacky 717202375Srdivacky return 0; 718202375Srdivacky} 719202375Srdivacky 720202375SrdivackyInstruction *InstCombiner::visitFRem(BinaryOperator &I) { 721221345Sdim Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 722221345Sdim 723221345Sdim if (Value *V = SimplifyFRemInst(Op0, Op1, TD)) 724221345Sdim return ReplaceInstUsesWith(I, V); 725221345Sdim 726221345Sdim // Handle cases involving: rem X, (select Cond, Y, Z) 727221345Sdim if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 728221345Sdim return &I; 729221345Sdim 730221345Sdim return 0; 731202375Srdivacky} 732