InstCombineMulDivRem.cpp revision 3200c4b53ca742bd0103454250ca89fec2776211
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" 19using namespace llvm; 20using 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. 26static 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, "tmp"); 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. 78static 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 99Instruction *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, "tmp"); 135 return BinaryOperator::CreateAdd(Add, Builder->CreateMul(C1, CI)); 136 } 137 } 138 139 // (1 - X) * (-2) -> (x - 1) * 2, for all positive nonzero powers of 2 140 // The "* 2" thus becomes a potential shifting opportunity. 141 { 142 const APInt & Val = CI->getValue(); 143 const APInt &PosVal = Val.abs(); 144 if (Val.isNegative() && PosVal.isPowerOf2()) { 145 Value *X = 0; 146 if (match(Op0, m_Sub(m_One(), m_Value(X)))) { 147 // ConstantInt::get(Op0->getType(), 2); 148 Value *Sub = Builder->CreateSub(X, ConstantInt::get(X->getType(), 1), 149 "dec1"); 150 return BinaryOperator::CreateMul(Sub, ConstantInt::get(X->getType(), 151 PosVal)); 152 } 153 } 154 } 155 } 156 157 // Simplify mul instructions with a constant RHS. 158 if (isa<Constant>(Op1)) { 159 // Try to fold constant mul into select arguments. 160 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 161 if (Instruction *R = FoldOpIntoSelect(I, SI)) 162 return R; 163 164 if (isa<PHINode>(Op0)) 165 if (Instruction *NV = FoldOpIntoPhi(I)) 166 return NV; 167 } 168 169 if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y 170 if (Value *Op1v = dyn_castNegVal(Op1)) 171 return BinaryOperator::CreateMul(Op0v, Op1v); 172 173 // (X / Y) * Y = X - (X % Y) 174 // (X / Y) * -Y = (X % Y) - X 175 { 176 Value *Op1C = Op1; 177 BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0); 178 if (!BO || 179 (BO->getOpcode() != Instruction::UDiv && 180 BO->getOpcode() != Instruction::SDiv)) { 181 Op1C = Op0; 182 BO = dyn_cast<BinaryOperator>(Op1); 183 } 184 Value *Neg = dyn_castNegVal(Op1C); 185 if (BO && BO->hasOneUse() && 186 (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) && 187 (BO->getOpcode() == Instruction::UDiv || 188 BO->getOpcode() == Instruction::SDiv)) { 189 Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1); 190 191 // If the division is exact, X % Y is zero, so we end up with X or -X. 192 if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO)) 193 if (SDiv->isExact()) { 194 if (Op1BO == Op1C) 195 return ReplaceInstUsesWith(I, Op0BO); 196 return BinaryOperator::CreateNeg(Op0BO); 197 } 198 199 Value *Rem; 200 if (BO->getOpcode() == Instruction::UDiv) 201 Rem = Builder->CreateURem(Op0BO, Op1BO); 202 else 203 Rem = Builder->CreateSRem(Op0BO, Op1BO); 204 Rem->takeName(BO); 205 206 if (Op1BO == Op1C) 207 return BinaryOperator::CreateSub(Op0BO, Rem); 208 return BinaryOperator::CreateSub(Rem, Op0BO); 209 } 210 } 211 212 /// i1 mul -> i1 and. 213 if (I.getType()->isIntegerTy(1)) 214 return BinaryOperator::CreateAnd(Op0, Op1); 215 216 // X*(1 << Y) --> X << Y 217 // (1 << Y)*X --> X << Y 218 { 219 Value *Y; 220 if (match(Op0, m_Shl(m_One(), m_Value(Y)))) 221 return BinaryOperator::CreateShl(Op1, Y); 222 if (match(Op1, m_Shl(m_One(), m_Value(Y)))) 223 return BinaryOperator::CreateShl(Op0, Y); 224 } 225 226 // If one of the operands of the multiply is a cast from a boolean value, then 227 // we know the bool is either zero or one, so this is a 'masking' multiply. 228 // X * Y (where Y is 0 or 1) -> X & (0-Y) 229 if (!I.getType()->isVectorTy()) { 230 // -2 is "-1 << 1" so it is all bits set except the low one. 231 APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true); 232 233 Value *BoolCast = 0, *OtherOp = 0; 234 if (MaskedValueIsZero(Op0, Negative2)) 235 BoolCast = Op0, OtherOp = Op1; 236 else if (MaskedValueIsZero(Op1, Negative2)) 237 BoolCast = Op1, OtherOp = Op0; 238 239 if (BoolCast) { 240 Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()), 241 BoolCast, "tmp"); 242 return BinaryOperator::CreateAnd(V, OtherOp); 243 } 244 } 245 246 return Changed ? &I : 0; 247} 248 249Instruction *InstCombiner::visitFMul(BinaryOperator &I) { 250 bool Changed = SimplifyAssociativeOrCommutative(I); 251 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 252 253 // Simplify mul instructions with a constant RHS... 254 if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 255 if (ConstantFP *Op1F = dyn_cast<ConstantFP>(Op1C)) { 256 // "In IEEE floating point, x*1 is not equivalent to x for nans. However, 257 // ANSI says we can drop signals, so we can do this anyway." (from GCC) 258 if (Op1F->isExactlyValue(1.0)) 259 return ReplaceInstUsesWith(I, Op0); // Eliminate 'fmul double %X, 1.0' 260 } else if (Op1C->getType()->isVectorTy()) { 261 if (ConstantVector *Op1V = dyn_cast<ConstantVector>(Op1C)) { 262 // As above, vector X*splat(1.0) -> X in all defined cases. 263 if (Constant *Splat = Op1V->getSplatValue()) { 264 if (ConstantFP *F = dyn_cast<ConstantFP>(Splat)) 265 if (F->isExactlyValue(1.0)) 266 return ReplaceInstUsesWith(I, Op0); 267 } 268 } 269 } 270 271 // Try to fold constant mul into select arguments. 272 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 273 if (Instruction *R = FoldOpIntoSelect(I, SI)) 274 return R; 275 276 if (isa<PHINode>(Op0)) 277 if (Instruction *NV = FoldOpIntoPhi(I)) 278 return NV; 279 } 280 281 if (Value *Op0v = dyn_castFNegVal(Op0)) // -X * -Y = X*Y 282 if (Value *Op1v = dyn_castFNegVal(Op1)) 283 return BinaryOperator::CreateFMul(Op0v, Op1v); 284 285 return Changed ? &I : 0; 286} 287 288/// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select 289/// instruction. 290bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { 291 SelectInst *SI = cast<SelectInst>(I.getOperand(1)); 292 293 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y 294 int NonNullOperand = -1; 295 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1))) 296 if (ST->isNullValue()) 297 NonNullOperand = 2; 298 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y 299 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2))) 300 if (ST->isNullValue()) 301 NonNullOperand = 1; 302 303 if (NonNullOperand == -1) 304 return false; 305 306 Value *SelectCond = SI->getOperand(0); 307 308 // Change the div/rem to use 'Y' instead of the select. 309 I.setOperand(1, SI->getOperand(NonNullOperand)); 310 311 // Okay, we know we replace the operand of the div/rem with 'Y' with no 312 // problem. However, the select, or the condition of the select may have 313 // multiple uses. Based on our knowledge that the operand must be non-zero, 314 // propagate the known value for the select into other uses of it, and 315 // propagate a known value of the condition into its other users. 316 317 // If the select and condition only have a single use, don't bother with this, 318 // early exit. 319 if (SI->use_empty() && SelectCond->hasOneUse()) 320 return true; 321 322 // Scan the current block backward, looking for other uses of SI. 323 BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin(); 324 325 while (BBI != BBFront) { 326 --BBI; 327 // If we found a call to a function, we can't assume it will return, so 328 // information from below it cannot be propagated above it. 329 if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI)) 330 break; 331 332 // Replace uses of the select or its condition with the known values. 333 for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end(); 334 I != E; ++I) { 335 if (*I == SI) { 336 *I = SI->getOperand(NonNullOperand); 337 Worklist.Add(BBI); 338 } else if (*I == SelectCond) { 339 *I = NonNullOperand == 1 ? ConstantInt::getTrue(BBI->getContext()) : 340 ConstantInt::getFalse(BBI->getContext()); 341 Worklist.Add(BBI); 342 } 343 } 344 345 // If we past the instruction, quit looking for it. 346 if (&*BBI == SI) 347 SI = 0; 348 if (&*BBI == SelectCond) 349 SelectCond = 0; 350 351 // If we ran out of things to eliminate, break out of the loop. 352 if (SelectCond == 0 && SI == 0) 353 break; 354 355 } 356 return true; 357} 358 359 360/// This function implements the transforms common to both integer division 361/// instructions (udiv and sdiv). It is called by the visitors to those integer 362/// division instructions. 363/// @brief Common integer divide transforms 364Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { 365 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 366 367 // The RHS is known non-zero. 368 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 369 I.setOperand(1, V); 370 return &I; 371 } 372 373 // Handle cases involving: [su]div X, (select Cond, Y, Z) 374 // This does not apply for fdiv. 375 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 376 return &I; 377 378 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 379 // (X / C1) / C2 -> X / (C1*C2) 380 if (Instruction *LHS = dyn_cast<Instruction>(Op0)) 381 if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode()) 382 if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) { 383 if (MultiplyOverflows(RHS, LHSRHS, 384 I.getOpcode()==Instruction::SDiv)) 385 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 386 return BinaryOperator::Create(I.getOpcode(), LHS->getOperand(0), 387 ConstantExpr::getMul(RHS, LHSRHS)); 388 } 389 390 if (!RHS->isZero()) { // avoid X udiv 0 391 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 392 if (Instruction *R = FoldOpIntoSelect(I, SI)) 393 return R; 394 if (isa<PHINode>(Op0)) 395 if (Instruction *NV = FoldOpIntoPhi(I)) 396 return NV; 397 } 398 } 399 400 // See if we can fold away this div instruction. 401 if (SimplifyDemandedInstructionBits(I)) 402 return &I; 403 404 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y 405 Value *X = 0, *Z = 0; 406 if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1 407 bool isSigned = I.getOpcode() == Instruction::SDiv; 408 if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || 409 (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) 410 return BinaryOperator::Create(I.getOpcode(), X, Op1); 411 } 412 413 return 0; 414} 415 416/// dyn_castZExtVal - Checks if V is a zext or constant that can 417/// be truncated to Ty without losing bits. 418static Value *dyn_castZExtVal(Value *V, const Type *Ty) { 419 if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) { 420 if (Z->getSrcTy() == Ty) 421 return Z->getOperand(0); 422 } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) { 423 if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth()) 424 return ConstantExpr::getTrunc(C, Ty); 425 } 426 return 0; 427} 428 429Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { 430 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 431 432 if (Value *V = SimplifyUDivInst(Op0, Op1, TD)) 433 return ReplaceInstUsesWith(I, V); 434 435 // Handle the integer div common cases 436 if (Instruction *Common = commonIDivTransforms(I)) 437 return Common; 438 439 if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) { 440 // X udiv 2^C -> X >> C 441 // Check to see if this is an unsigned division with an exact power of 2, 442 // if so, convert to a right shift. 443 if (C->getValue().isPowerOf2()) { // 0 not included in isPowerOf2 444 BinaryOperator *LShr = 445 BinaryOperator::CreateLShr(Op0, 446 ConstantInt::get(Op0->getType(), C->getValue().logBase2())); 447 if (I.isExact()) LShr->setIsExact(); 448 return LShr; 449 } 450 451 // X udiv C, where C >= signbit 452 if (C->getValue().isNegative()) { 453 Value *IC = Builder->CreateICmpULT(Op0, C); 454 return SelectInst::Create(IC, Constant::getNullValue(I.getType()), 455 ConstantInt::get(I.getType(), 1)); 456 } 457 } 458 459 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 460 { const APInt *CI; Value *N; 461 if (match(Op1, m_Shl(m_Power2(CI), m_Value(N)))) { 462 if (*CI != 1) 463 N = Builder->CreateAdd(N, ConstantInt::get(I.getType(), CI->logBase2()), 464 "tmp"); 465 if (I.isExact()) 466 return BinaryOperator::CreateExactLShr(Op0, N); 467 return BinaryOperator::CreateLShr(Op0, N); 468 } 469 } 470 471 // udiv X, (Select Cond, C1, C2) --> Select Cond, (shr X, C1), (shr X, C2) 472 // where C1&C2 are powers of two. 473 { Value *Cond; const APInt *C1, *C2; 474 if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) { 475 // Construct the "on true" case of the select 476 Value *TSI = Builder->CreateLShr(Op0, C1->logBase2(), Op1->getName()+".t", 477 I.isExact()); 478 479 // Construct the "on false" case of the select 480 Value *FSI = Builder->CreateLShr(Op0, C2->logBase2(), Op1->getName()+".f", 481 I.isExact()); 482 483 // construct the select instruction and return it. 484 return SelectInst::Create(Cond, TSI, FSI); 485 } 486 } 487 488 // (zext A) udiv (zext B) --> zext (A udiv B) 489 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 490 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 491 return new ZExtInst(Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", 492 I.isExact()), 493 I.getType()); 494 495 return 0; 496} 497 498Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { 499 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 500 501 if (Value *V = SimplifySDivInst(Op0, Op1, TD)) 502 return ReplaceInstUsesWith(I, V); 503 504 // Handle the integer div common cases 505 if (Instruction *Common = commonIDivTransforms(I)) 506 return Common; 507 508 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 509 // sdiv X, -1 == -X 510 if (RHS->isAllOnesValue()) 511 return BinaryOperator::CreateNeg(Op0); 512 513 // sdiv X, C --> ashr exact X, log2(C) 514 if (I.isExact() && RHS->getValue().isNonNegative() && 515 RHS->getValue().isPowerOf2()) { 516 Value *ShAmt = llvm::ConstantInt::get(RHS->getType(), 517 RHS->getValue().exactLogBase2()); 518 return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName()); 519 } 520 521 // -X/C --> X/-C provided the negation doesn't overflow. 522 if (SubOperator *Sub = dyn_cast<SubOperator>(Op0)) 523 if (match(Sub->getOperand(0), m_Zero()) && Sub->hasNoSignedWrap()) 524 return BinaryOperator::CreateSDiv(Sub->getOperand(1), 525 ConstantExpr::getNeg(RHS)); 526 } 527 528 // If the sign bits of both operands are zero (i.e. we can prove they are 529 // unsigned inputs), turn this into a udiv. 530 if (I.getType()->isIntegerTy()) { 531 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 532 if (MaskedValueIsZero(Op0, Mask)) { 533 if (MaskedValueIsZero(Op1, Mask)) { 534 // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set 535 return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 536 } 537 538 if (match(Op1, m_Shl(m_Power2(), m_Value()))) { 539 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) 540 // Safe because the only negative value (1 << Y) can take on is 541 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have 542 // the sign bit set. 543 return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 544 } 545 } 546 } 547 548 return 0; 549} 550 551Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { 552 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 553 554 if (Value *V = SimplifyFDivInst(Op0, Op1, TD)) 555 return ReplaceInstUsesWith(I, V); 556 557 if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) { 558 const APFloat &Op1F = Op1C->getValueAPF(); 559 560 // If the divisor has an exact multiplicative inverse we can turn the fdiv 561 // into a cheaper fmul. 562 APFloat Reciprocal(Op1F.getSemantics()); 563 if (Op1F.getExactInverse(&Reciprocal)) { 564 ConstantFP *RFP = ConstantFP::get(Builder->getContext(), Reciprocal); 565 return BinaryOperator::CreateFMul(Op0, RFP); 566 } 567 } 568 569 return 0; 570} 571 572/// This function implements the transforms common to both integer remainder 573/// instructions (urem and srem). It is called by the visitors to those integer 574/// remainder instructions. 575/// @brief Common integer remainder transforms 576Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) { 577 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 578 579 // The RHS is known non-zero. 580 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 581 I.setOperand(1, V); 582 return &I; 583 } 584 585 // Handle cases involving: rem X, (select Cond, Y, Z) 586 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 587 return &I; 588 589 if (isa<ConstantInt>(Op1)) { 590 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { 591 if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { 592 if (Instruction *R = FoldOpIntoSelect(I, SI)) 593 return R; 594 } else if (isa<PHINode>(Op0I)) { 595 if (Instruction *NV = FoldOpIntoPhi(I)) 596 return NV; 597 } 598 599 // See if we can fold away this rem instruction. 600 if (SimplifyDemandedInstructionBits(I)) 601 return &I; 602 } 603 } 604 605 return 0; 606} 607 608Instruction *InstCombiner::visitURem(BinaryOperator &I) { 609 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 610 611 if (Value *V = SimplifyURemInst(Op0, Op1, TD)) 612 return ReplaceInstUsesWith(I, V); 613 614 if (Instruction *common = commonIRemTransforms(I)) 615 return common; 616 617 // X urem C^2 -> X and C-1 618 { const APInt *C; 619 if (match(Op1, m_Power2(C))) 620 return BinaryOperator::CreateAnd(Op0, 621 ConstantInt::get(I.getType(), *C-1)); 622 } 623 624 // Turn A % (C << N), where C is 2^k, into A & ((C << N)-1) 625 if (match(Op1, m_Shl(m_Power2(), m_Value()))) { 626 Constant *N1 = Constant::getAllOnesValue(I.getType()); 627 Value *Add = Builder->CreateAdd(Op1, N1, "tmp"); 628 return BinaryOperator::CreateAnd(Op0, Add); 629 } 630 631 // urem X, (select Cond, 2^C1, 2^C2) --> 632 // select Cond, (and X, C1-1), (and X, C2-1) 633 // when C1&C2 are powers of two. 634 { Value *Cond; const APInt *C1, *C2; 635 if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) { 636 Value *TrueAnd = Builder->CreateAnd(Op0, *C1-1, Op1->getName()+".t"); 637 Value *FalseAnd = Builder->CreateAnd(Op0, *C2-1, Op1->getName()+".f"); 638 return SelectInst::Create(Cond, TrueAnd, FalseAnd); 639 } 640 } 641 642 // (zext A) urem (zext B) --> zext (A urem B) 643 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 644 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 645 return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), 646 I.getType()); 647 648 return 0; 649} 650 651Instruction *InstCombiner::visitSRem(BinaryOperator &I) { 652 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 653 654 if (Value *V = SimplifySRemInst(Op0, Op1, TD)) 655 return ReplaceInstUsesWith(I, V); 656 657 // Handle the integer rem common cases 658 if (Instruction *Common = commonIRemTransforms(I)) 659 return Common; 660 661 if (Value *RHSNeg = dyn_castNegVal(Op1)) 662 if (!isa<Constant>(RHSNeg) || 663 (isa<ConstantInt>(RHSNeg) && 664 cast<ConstantInt>(RHSNeg)->getValue().isStrictlyPositive())) { 665 // X % -Y -> X % Y 666 Worklist.AddValue(I.getOperand(1)); 667 I.setOperand(1, RHSNeg); 668 return &I; 669 } 670 671 // If the sign bits of both operands are zero (i.e. we can prove they are 672 // unsigned inputs), turn this into a urem. 673 if (I.getType()->isIntegerTy()) { 674 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 675 if (MaskedValueIsZero(Op1, Mask) && MaskedValueIsZero(Op0, Mask)) { 676 // X srem Y -> X urem Y, iff X and Y don't have sign bit set 677 return BinaryOperator::CreateURem(Op0, Op1, I.getName()); 678 } 679 } 680 681 // If it's a constant vector, flip any negative values positive. 682 if (ConstantVector *RHSV = dyn_cast<ConstantVector>(Op1)) { 683 unsigned VWidth = RHSV->getNumOperands(); 684 685 bool hasNegative = false; 686 for (unsigned i = 0; !hasNegative && i != VWidth; ++i) 687 if (ConstantInt *RHS = dyn_cast<ConstantInt>(RHSV->getOperand(i))) 688 if (RHS->getValue().isNegative()) 689 hasNegative = true; 690 691 if (hasNegative) { 692 std::vector<Constant *> Elts(VWidth); 693 for (unsigned i = 0; i != VWidth; ++i) { 694 if (ConstantInt *RHS = dyn_cast<ConstantInt>(RHSV->getOperand(i))) { 695 if (RHS->getValue().isNegative()) 696 Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); 697 else 698 Elts[i] = RHS; 699 } 700 } 701 702 Constant *NewRHSV = ConstantVector::get(Elts); 703 if (NewRHSV != RHSV) { 704 Worklist.AddValue(I.getOperand(1)); 705 I.setOperand(1, NewRHSV); 706 return &I; 707 } 708 } 709 } 710 711 return 0; 712} 713 714Instruction *InstCombiner::visitFRem(BinaryOperator &I) { 715 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 716 717 if (Value *V = SimplifyFRemInst(Op0, Op1, TD)) 718 return ReplaceInstUsesWith(I, V); 719 720 // Handle cases involving: rem X, (select Cond, Y, Z) 721 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 722 return &I; 723 724 return 0; 725} 726