1 //===- InstCombineMulDivRem.cpp -------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv, 11 // srem, urem, frem. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "InstCombine.h" 16 #include "llvm/IntrinsicInst.h" 17 #include "llvm/Analysis/InstructionSimplify.h" 18 #include "llvm/Support/PatternMatch.h" 19 using namespace llvm; 20 using namespace PatternMatch; 21 22 23 /// simplifyValueKnownNonZero - The specific integer value is used in a context 24 /// where it is known to be non-zero. If this allows us to simplify the 25 /// computation, do so and return the new operand, otherwise return null. 26 static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC) { 27 // If V has multiple uses, then we would have to do more analysis to determine 28 // if this is safe. For example, the use could be in dynamically unreached 29 // code. 30 if (!V->hasOneUse()) return 0; 31 32 bool MadeChange = false; 33 34 // ((1 << A) >>u B) --> (1 << (A-B)) 35 // Because V cannot be zero, we know that B is less than A. 36 Value *A = 0, *B = 0, *PowerOf2 = 0; 37 if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(PowerOf2), m_Value(A))), 38 m_Value(B))) && 39 // The "1" can be any value known to be a power of 2. 40 isPowerOfTwo(PowerOf2, IC.getTargetData())) { 41 A = IC.Builder->CreateSub(A, B); 42 return IC.Builder->CreateShl(PowerOf2, A); 43 } 44 45 // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it 46 // inexact. Similarly for <<. 47 if (BinaryOperator *I = dyn_cast<BinaryOperator>(V)) 48 if (I->isLogicalShift() && 49 isPowerOfTwo(I->getOperand(0), IC.getTargetData())) { 50 // We know that this is an exact/nuw shift and that the input is a 51 // non-zero context as well. 52 if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC)) { 53 I->setOperand(0, V2); 54 MadeChange = true; 55 } 56 57 if (I->getOpcode() == Instruction::LShr && !I->isExact()) { 58 I->setIsExact(); 59 MadeChange = true; 60 } 61 62 if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) { 63 I->setHasNoUnsignedWrap(); 64 MadeChange = true; 65 } 66 } 67 68 // TODO: Lots more we could do here: 69 // If V is a phi node, we can call this on each of its operands. 70 // "select cond, X, 0" can simplify to "X". 71 72 return MadeChange ? V : 0; 73 } 74 75 76 /// MultiplyOverflows - True if the multiply can not be expressed in an int 77 /// this size. 78 static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) { 79 uint32_t W = C1->getBitWidth(); 80 APInt LHSExt = C1->getValue(), RHSExt = C2->getValue(); 81 if (sign) { 82 LHSExt = LHSExt.sext(W * 2); 83 RHSExt = RHSExt.sext(W * 2); 84 } else { 85 LHSExt = LHSExt.zext(W * 2); 86 RHSExt = RHSExt.zext(W * 2); 87 } 88 89 APInt MulExt = LHSExt * RHSExt; 90 91 if (!sign) 92 return MulExt.ugt(APInt::getLowBitsSet(W * 2, W)); 93 94 APInt Min = APInt::getSignedMinValue(W).sext(W * 2); 95 APInt Max = APInt::getSignedMaxValue(W).sext(W * 2); 96 return MulExt.slt(Min) || MulExt.sgt(Max); 97 } 98 99 Instruction *InstCombiner::visitMul(BinaryOperator &I) { 100 bool Changed = SimplifyAssociativeOrCommutative(I); 101 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 102 103 if (Value *V = SimplifyMulInst(Op0, Op1, TD)) 104 return ReplaceInstUsesWith(I, V); 105 106 if (Value *V = SimplifyUsingDistributiveLaws(I)) 107 return ReplaceInstUsesWith(I, V); 108 109 if (match(Op1, m_AllOnes())) // X * -1 == 0 - X 110 return BinaryOperator::CreateNeg(Op0, I.getName()); 111 112 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 113 114 // ((X << C1)*C2) == (X * (C2 << C1)) 115 if (BinaryOperator *SI = dyn_cast<BinaryOperator>(Op0)) 116 if (SI->getOpcode() == Instruction::Shl) 117 if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1))) 118 return BinaryOperator::CreateMul(SI->getOperand(0), 119 ConstantExpr::getShl(CI, ShOp)); 120 121 const APInt &Val = CI->getValue(); 122 if (Val.isPowerOf2()) { // Replace X*(2^C) with X << C 123 Constant *NewCst = ConstantInt::get(Op0->getType(), Val.logBase2()); 124 BinaryOperator *Shl = BinaryOperator::CreateShl(Op0, NewCst); 125 if (I.hasNoSignedWrap()) Shl->setHasNoSignedWrap(); 126 if (I.hasNoUnsignedWrap()) Shl->setHasNoUnsignedWrap(); 127 return Shl; 128 } 129 130 // Canonicalize (X+C1)*CI -> X*CI+C1*CI. 131 { Value *X; ConstantInt *C1; 132 if (Op0->hasOneUse() && 133 match(Op0, m_Add(m_Value(X), m_ConstantInt(C1)))) { 134 Value *Add = Builder->CreateMul(X, CI); 135 return BinaryOperator::CreateAdd(Add, Builder->CreateMul(C1, CI)); 136 } 137 } 138 139 // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n 140 // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n 141 // The "* (2**n)" thus becomes a potential shifting opportunity. 142 { 143 const APInt & Val = CI->getValue(); 144 const APInt &PosVal = Val.abs(); 145 if (Val.isNegative() && PosVal.isPowerOf2()) { 146 Value *X = 0, *Y = 0; 147 if (Op0->hasOneUse()) { 148 ConstantInt *C1; 149 Value *Sub = 0; 150 if (match(Op0, m_Sub(m_Value(Y), m_Value(X)))) 151 Sub = Builder->CreateSub(X, Y, "suba"); 152 else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1)))) 153 Sub = Builder->CreateSub(Builder->CreateNeg(C1), Y, "subc"); 154 if (Sub) 155 return 156 BinaryOperator::CreateMul(Sub, 157 ConstantInt::get(Y->getType(), PosVal)); 158 } 159 } 160 } 161 } 162 163 // Simplify mul instructions with a constant RHS. 164 if (isa<Constant>(Op1)) { 165 // Try to fold constant mul into select arguments. 166 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 167 if (Instruction *R = FoldOpIntoSelect(I, SI)) 168 return R; 169 170 if (isa<PHINode>(Op0)) 171 if (Instruction *NV = FoldOpIntoPhi(I)) 172 return NV; 173 } 174 175 if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y 176 if (Value *Op1v = dyn_castNegVal(Op1)) 177 return BinaryOperator::CreateMul(Op0v, Op1v); 178 179 // (X / Y) * Y = X - (X % Y) 180 // (X / Y) * -Y = (X % Y) - X 181 { 182 Value *Op1C = Op1; 183 BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0); 184 if (!BO || 185 (BO->getOpcode() != Instruction::UDiv && 186 BO->getOpcode() != Instruction::SDiv)) { 187 Op1C = Op0; 188 BO = dyn_cast<BinaryOperator>(Op1); 189 } 190 Value *Neg = dyn_castNegVal(Op1C); 191 if (BO && BO->hasOneUse() && 192 (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) && 193 (BO->getOpcode() == Instruction::UDiv || 194 BO->getOpcode() == Instruction::SDiv)) { 195 Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1); 196 197 // If the division is exact, X % Y is zero, so we end up with X or -X. 198 if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO)) 199 if (SDiv->isExact()) { 200 if (Op1BO == Op1C) 201 return ReplaceInstUsesWith(I, Op0BO); 202 return BinaryOperator::CreateNeg(Op0BO); 203 } 204 205 Value *Rem; 206 if (BO->getOpcode() == Instruction::UDiv) 207 Rem = Builder->CreateURem(Op0BO, Op1BO); 208 else 209 Rem = Builder->CreateSRem(Op0BO, Op1BO); 210 Rem->takeName(BO); 211 212 if (Op1BO == Op1C) 213 return BinaryOperator::CreateSub(Op0BO, Rem); 214 return BinaryOperator::CreateSub(Rem, Op0BO); 215 } 216 } 217 218 /// i1 mul -> i1 and. 219 if (I.getType()->isIntegerTy(1)) 220 return BinaryOperator::CreateAnd(Op0, Op1); 221 222 // X*(1 << Y) --> X << Y 223 // (1 << Y)*X --> X << Y 224 { 225 Value *Y; 226 if (match(Op0, m_Shl(m_One(), m_Value(Y)))) 227 return BinaryOperator::CreateShl(Op1, Y); 228 if (match(Op1, m_Shl(m_One(), m_Value(Y)))) 229 return BinaryOperator::CreateShl(Op0, Y); 230 } 231 232 // If one of the operands of the multiply is a cast from a boolean value, then 233 // we know the bool is either zero or one, so this is a 'masking' multiply. 234 // X * Y (where Y is 0 or 1) -> X & (0-Y) 235 if (!I.getType()->isVectorTy()) { 236 // -2 is "-1 << 1" so it is all bits set except the low one. 237 APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true); 238 239 Value *BoolCast = 0, *OtherOp = 0; 240 if (MaskedValueIsZero(Op0, Negative2)) 241 BoolCast = Op0, OtherOp = Op1; 242 else if (MaskedValueIsZero(Op1, Negative2)) 243 BoolCast = Op1, OtherOp = Op0; 244 245 if (BoolCast) { 246 Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()), 247 BoolCast); 248 return BinaryOperator::CreateAnd(V, OtherOp); 249 } 250 } 251 252 return Changed ? &I : 0; 253 } 254 255 Instruction *InstCombiner::visitFMul(BinaryOperator &I) { 256 bool Changed = SimplifyAssociativeOrCommutative(I); 257 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 258 259 // Simplify mul instructions with a constant RHS. 260 if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 261 if (ConstantFP *Op1F = dyn_cast<ConstantFP>(Op1C)) { 262 // "In IEEE floating point, x*1 is not equivalent to x for nans. However, 263 // ANSI says we can drop signals, so we can do this anyway." (from GCC) 264 if (Op1F->isExactlyValue(1.0)) 265 return ReplaceInstUsesWith(I, Op0); // Eliminate 'fmul double %X, 1.0' 266 } else if (ConstantDataVector *Op1V = dyn_cast<ConstantDataVector>(Op1C)) { 267 // As above, vector X*splat(1.0) -> X in all defined cases. 268 if (ConstantFP *F = dyn_cast_or_null<ConstantFP>(Op1V->getSplatValue())) 269 if (F->isExactlyValue(1.0)) 270 return ReplaceInstUsesWith(I, Op0); 271 } 272 273 // Try to fold constant mul into select arguments. 274 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 275 if (Instruction *R = FoldOpIntoSelect(I, SI)) 276 return R; 277 278 if (isa<PHINode>(Op0)) 279 if (Instruction *NV = FoldOpIntoPhi(I)) 280 return NV; 281 } 282 283 if (Value *Op0v = dyn_castFNegVal(Op0)) // -X * -Y = X*Y 284 if (Value *Op1v = dyn_castFNegVal(Op1)) 285 return BinaryOperator::CreateFMul(Op0v, Op1v); 286 287 return Changed ? &I : 0; 288 } 289 290 /// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select 291 /// instruction. 292 bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { 293 SelectInst *SI = cast<SelectInst>(I.getOperand(1)); 294 295 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y 296 int NonNullOperand = -1; 297 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1))) 298 if (ST->isNullValue()) 299 NonNullOperand = 2; 300 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y 301 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2))) 302 if (ST->isNullValue()) 303 NonNullOperand = 1; 304 305 if (NonNullOperand == -1) 306 return false; 307 308 Value *SelectCond = SI->getOperand(0); 309 310 // Change the div/rem to use 'Y' instead of the select. 311 I.setOperand(1, SI->getOperand(NonNullOperand)); 312 313 // Okay, we know we replace the operand of the div/rem with 'Y' with no 314 // problem. However, the select, or the condition of the select may have 315 // multiple uses. Based on our knowledge that the operand must be non-zero, 316 // propagate the known value for the select into other uses of it, and 317 // propagate a known value of the condition into its other users. 318 319 // If the select and condition only have a single use, don't bother with this, 320 // early exit. 321 if (SI->use_empty() && SelectCond->hasOneUse()) 322 return true; 323 324 // Scan the current block backward, looking for other uses of SI. 325 BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin(); 326 327 while (BBI != BBFront) { 328 --BBI; 329 // If we found a call to a function, we can't assume it will return, so 330 // information from below it cannot be propagated above it. 331 if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI)) 332 break; 333 334 // Replace uses of the select or its condition with the known values. 335 for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end(); 336 I != E; ++I) { 337 if (*I == SI) { 338 *I = SI->getOperand(NonNullOperand); 339 Worklist.Add(BBI); 340 } else if (*I == SelectCond) { 341 *I = NonNullOperand == 1 ? ConstantInt::getTrue(BBI->getContext()) : 342 ConstantInt::getFalse(BBI->getContext()); 343 Worklist.Add(BBI); 344 } 345 } 346 347 // If we past the instruction, quit looking for it. 348 if (&*BBI == SI) 349 SI = 0; 350 if (&*BBI == SelectCond) 351 SelectCond = 0; 352 353 // If we ran out of things to eliminate, break out of the loop. 354 if (SelectCond == 0 && SI == 0) 355 break; 356 357 } 358 return true; 359 } 360 361 362 /// This function implements the transforms common to both integer division 363 /// instructions (udiv and sdiv). It is called by the visitors to those integer 364 /// division instructions. 365 /// @brief Common integer divide transforms 366 Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { 367 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 368 369 // The RHS is known non-zero. 370 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 371 I.setOperand(1, V); 372 return &I; 373 } 374 375 // Handle cases involving: [su]div X, (select Cond, Y, Z) 376 // This does not apply for fdiv. 377 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 378 return &I; 379 380 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 381 // (X / C1) / C2 -> X / (C1*C2) 382 if (Instruction *LHS = dyn_cast<Instruction>(Op0)) 383 if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode()) 384 if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) { 385 if (MultiplyOverflows(RHS, LHSRHS, 386 I.getOpcode()==Instruction::SDiv)) 387 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 388 return BinaryOperator::Create(I.getOpcode(), LHS->getOperand(0), 389 ConstantExpr::getMul(RHS, LHSRHS)); 390 } 391 392 if (!RHS->isZero()) { // avoid X udiv 0 393 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 394 if (Instruction *R = FoldOpIntoSelect(I, SI)) 395 return R; 396 if (isa<PHINode>(Op0)) 397 if (Instruction *NV = FoldOpIntoPhi(I)) 398 return NV; 399 } 400 } 401 402 // See if we can fold away this div instruction. 403 if (SimplifyDemandedInstructionBits(I)) 404 return &I; 405 406 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y 407 Value *X = 0, *Z = 0; 408 if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1 409 bool isSigned = I.getOpcode() == Instruction::SDiv; 410 if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || 411 (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) 412 return BinaryOperator::Create(I.getOpcode(), X, Op1); 413 } 414 415 return 0; 416 } 417 418 /// dyn_castZExtVal - Checks if V is a zext or constant that can 419 /// be truncated to Ty without losing bits. 420 static Value *dyn_castZExtVal(Value *V, Type *Ty) { 421 if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) { 422 if (Z->getSrcTy() == Ty) 423 return Z->getOperand(0); 424 } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) { 425 if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth()) 426 return ConstantExpr::getTrunc(C, Ty); 427 } 428 return 0; 429 } 430 431 Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { 432 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 433 434 if (Value *V = SimplifyUDivInst(Op0, Op1, TD)) 435 return ReplaceInstUsesWith(I, V); 436 437 // Handle the integer div common cases 438 if (Instruction *Common = commonIDivTransforms(I)) 439 return Common; 440 441 { 442 // X udiv 2^C -> X >> C 443 // Check to see if this is an unsigned division with an exact power of 2, 444 // if so, convert to a right shift. 445 const APInt *C; 446 if (match(Op1, m_Power2(C))) { 447 BinaryOperator *LShr = 448 BinaryOperator::CreateLShr(Op0, 449 ConstantInt::get(Op0->getType(), 450 C->logBase2())); 451 if (I.isExact()) LShr->setIsExact(); 452 return LShr; 453 } 454 } 455 456 if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) { 457 // X udiv C, where C >= signbit 458 if (C->getValue().isNegative()) { 459 Value *IC = Builder->CreateICmpULT(Op0, C); 460 return SelectInst::Create(IC, Constant::getNullValue(I.getType()), 461 ConstantInt::get(I.getType(), 1)); 462 } 463 } 464 465 // (x lshr C1) udiv C2 --> x udiv (C2 << C1) 466 if (ConstantInt *C2 = dyn_cast<ConstantInt>(Op1)) { 467 Value *X; 468 ConstantInt *C1; 469 if (match(Op0, m_LShr(m_Value(X), m_ConstantInt(C1)))) { 470 APInt NC = C2->getValue().shl(C1->getLimitedValue(C1->getBitWidth()-1)); 471 return BinaryOperator::CreateUDiv(X, Builder->getInt(NC)); 472 } 473 } 474 475 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 476 { const APInt *CI; Value *N; 477 if (match(Op1, m_Shl(m_Power2(CI), m_Value(N))) || 478 match(Op1, m_ZExt(m_Shl(m_Power2(CI), m_Value(N))))) { 479 if (*CI != 1) 480 N = Builder->CreateAdd(N, ConstantInt::get(I.getType(),CI->logBase2())); 481 if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1)) 482 N = Builder->CreateZExt(N, Z->getDestTy()); 483 if (I.isExact()) 484 return BinaryOperator::CreateExactLShr(Op0, N); 485 return BinaryOperator::CreateLShr(Op0, N); 486 } 487 } 488 489 // udiv X, (Select Cond, C1, C2) --> Select Cond, (shr X, C1), (shr X, C2) 490 // where C1&C2 are powers of two. 491 { Value *Cond; const APInt *C1, *C2; 492 if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) { 493 // Construct the "on true" case of the select 494 Value *TSI = Builder->CreateLShr(Op0, C1->logBase2(), Op1->getName()+".t", 495 I.isExact()); 496 497 // Construct the "on false" case of the select 498 Value *FSI = Builder->CreateLShr(Op0, C2->logBase2(), Op1->getName()+".f", 499 I.isExact()); 500 501 // construct the select instruction and return it. 502 return SelectInst::Create(Cond, TSI, FSI); 503 } 504 } 505 506 // (zext A) udiv (zext B) --> zext (A udiv B) 507 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 508 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 509 return new ZExtInst(Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", 510 I.isExact()), 511 I.getType()); 512 513 return 0; 514 } 515 516 Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { 517 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 518 519 if (Value *V = SimplifySDivInst(Op0, Op1, TD)) 520 return ReplaceInstUsesWith(I, V); 521 522 // Handle the integer div common cases 523 if (Instruction *Common = commonIDivTransforms(I)) 524 return Common; 525 526 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 527 // sdiv X, -1 == -X 528 if (RHS->isAllOnesValue()) 529 return BinaryOperator::CreateNeg(Op0); 530 531 // sdiv X, C --> ashr exact X, log2(C) 532 if (I.isExact() && RHS->getValue().isNonNegative() && 533 RHS->getValue().isPowerOf2()) { 534 Value *ShAmt = llvm::ConstantInt::get(RHS->getType(), 535 RHS->getValue().exactLogBase2()); 536 return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName()); 537 } 538 539 // -X/C --> X/-C provided the negation doesn't overflow. 540 if (SubOperator *Sub = dyn_cast<SubOperator>(Op0)) 541 if (match(Sub->getOperand(0), m_Zero()) && Sub->hasNoSignedWrap()) 542 return BinaryOperator::CreateSDiv(Sub->getOperand(1), 543 ConstantExpr::getNeg(RHS)); 544 } 545 546 // If the sign bits of both operands are zero (i.e. we can prove they are 547 // unsigned inputs), turn this into a udiv. 548 if (I.getType()->isIntegerTy()) { 549 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 550 if (MaskedValueIsZero(Op0, Mask)) { 551 if (MaskedValueIsZero(Op1, Mask)) { 552 // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set 553 return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 554 } 555 556 if (match(Op1, m_Shl(m_Power2(), m_Value()))) { 557 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) 558 // Safe because the only negative value (1 << Y) can take on is 559 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have 560 // the sign bit set. 561 return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 562 } 563 } 564 } 565 566 return 0; 567 } 568 569 Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { 570 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 571 572 if (Value *V = SimplifyFDivInst(Op0, Op1, TD)) 573 return ReplaceInstUsesWith(I, V); 574 575 if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) { 576 const APFloat &Op1F = Op1C->getValueAPF(); 577 578 // If the divisor has an exact multiplicative inverse we can turn the fdiv 579 // into a cheaper fmul. 580 APFloat Reciprocal(Op1F.getSemantics()); 581 if (Op1F.getExactInverse(&Reciprocal)) { 582 ConstantFP *RFP = ConstantFP::get(Builder->getContext(), Reciprocal); 583 return BinaryOperator::CreateFMul(Op0, RFP); 584 } 585 } 586 587 return 0; 588 } 589 590 /// This function implements the transforms common to both integer remainder 591 /// instructions (urem and srem). It is called by the visitors to those integer 592 /// remainder instructions. 593 /// @brief Common integer remainder transforms 594 Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) { 595 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 596 597 // The RHS is known non-zero. 598 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 599 I.setOperand(1, V); 600 return &I; 601 } 602 603 // Handle cases involving: rem X, (select Cond, Y, Z) 604 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 605 return &I; 606 607 if (isa<ConstantInt>(Op1)) { 608 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { 609 if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { 610 if (Instruction *R = FoldOpIntoSelect(I, SI)) 611 return R; 612 } else if (isa<PHINode>(Op0I)) { 613 if (Instruction *NV = FoldOpIntoPhi(I)) 614 return NV; 615 } 616 617 // See if we can fold away this rem instruction. 618 if (SimplifyDemandedInstructionBits(I)) 619 return &I; 620 } 621 } 622 623 return 0; 624 } 625 626 Instruction *InstCombiner::visitURem(BinaryOperator &I) { 627 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 628 629 if (Value *V = SimplifyURemInst(Op0, Op1, TD)) 630 return ReplaceInstUsesWith(I, V); 631 632 if (Instruction *common = commonIRemTransforms(I)) 633 return common; 634 635 // X urem C^2 -> X and C-1 636 { const APInt *C; 637 if (match(Op1, m_Power2(C))) 638 return BinaryOperator::CreateAnd(Op0, 639 ConstantInt::get(I.getType(), *C-1)); 640 } 641 642 // Turn A % (C << N), where C is 2^k, into A & ((C << N)-1) 643 if (match(Op1, m_Shl(m_Power2(), m_Value()))) { 644 Constant *N1 = Constant::getAllOnesValue(I.getType()); 645 Value *Add = Builder->CreateAdd(Op1, N1); 646 return BinaryOperator::CreateAnd(Op0, Add); 647 } 648 649 // urem X, (select Cond, 2^C1, 2^C2) --> 650 // select Cond, (and X, C1-1), (and X, C2-1) 651 // when C1&C2 are powers of two. 652 { Value *Cond; const APInt *C1, *C2; 653 if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) { 654 Value *TrueAnd = Builder->CreateAnd(Op0, *C1-1, Op1->getName()+".t"); 655 Value *FalseAnd = Builder->CreateAnd(Op0, *C2-1, Op1->getName()+".f"); 656 return SelectInst::Create(Cond, TrueAnd, FalseAnd); 657 } 658 } 659 660 // (zext A) urem (zext B) --> zext (A urem B) 661 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 662 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 663 return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), 664 I.getType()); 665 666 return 0; 667 } 668 669 Instruction *InstCombiner::visitSRem(BinaryOperator &I) { 670 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 671 672 if (Value *V = SimplifySRemInst(Op0, Op1, TD)) 673 return ReplaceInstUsesWith(I, V); 674 675 // Handle the integer rem common cases 676 if (Instruction *Common = commonIRemTransforms(I)) 677 return Common; 678 679 if (Value *RHSNeg = dyn_castNegVal(Op1)) 680 if (!isa<Constant>(RHSNeg) || 681 (isa<ConstantInt>(RHSNeg) && 682 cast<ConstantInt>(RHSNeg)->getValue().isStrictlyPositive())) { 683 // X % -Y -> X % Y 684 Worklist.AddValue(I.getOperand(1)); 685 I.setOperand(1, RHSNeg); 686 return &I; 687 } 688 689 // If the sign bits of both operands are zero (i.e. we can prove they are 690 // unsigned inputs), turn this into a urem. 691 if (I.getType()->isIntegerTy()) { 692 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 693 if (MaskedValueIsZero(Op1, Mask) && MaskedValueIsZero(Op0, Mask)) { 694 // X srem Y -> X urem Y, iff X and Y don't have sign bit set 695 return BinaryOperator::CreateURem(Op0, Op1, I.getName()); 696 } 697 } 698 699 // If it's a constant vector, flip any negative values positive. 700 if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) { 701 Constant *C = cast<Constant>(Op1); 702 unsigned VWidth = C->getType()->getVectorNumElements(); 703 704 bool hasNegative = false; 705 bool hasMissing = false; 706 for (unsigned i = 0; i != VWidth; ++i) { 707 Constant *Elt = C->getAggregateElement(i); 708 if (Elt == 0) { 709 hasMissing = true; 710 break; 711 } 712 713 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt)) 714 if (RHS->isNegative()) 715 hasNegative = true; 716 } 717 718 if (hasNegative && !hasMissing) { 719 SmallVector<Constant *, 16> Elts(VWidth); 720 for (unsigned i = 0; i != VWidth; ++i) { 721 Elts[i] = C->getAggregateElement(i); // Handle undef, etc. 722 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) { 723 if (RHS->isNegative()) 724 Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); 725 } 726 } 727 728 Constant *NewRHSV = ConstantVector::get(Elts); 729 if (NewRHSV != C) { // Don't loop on -MININT 730 Worklist.AddValue(I.getOperand(1)); 731 I.setOperand(1, NewRHSV); 732 return &I; 733 } 734 } 735 } 736 737 return 0; 738 } 739 740 Instruction *InstCombiner::visitFRem(BinaryOperator &I) { 741 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 742 743 if (Value *V = SimplifyFRemInst(Op0, Op1, TD)) 744 return ReplaceInstUsesWith(I, V); 745 746 // Handle cases involving: rem X, (select Cond, Y, Z) 747 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 748 return &I; 749 750 return 0; 751 } 752