InstCombineMulDivRem.cpp revision e7006bb04bd881478fe24d6fbb3051ba3f63d746
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/Analysis/InstructionSimplify.h" 17#include "llvm/IR/IntrinsicInst.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 isKnownToBeAPowerOfTwo(PowerOf2)) { 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() && isKnownToBeAPowerOfTwo(I->getOperand(0))) { 49 // We know that this is an exact/nuw shift and that the input is a 50 // non-zero context as well. 51 if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC)) { 52 I->setOperand(0, V2); 53 MadeChange = true; 54 } 55 56 if (I->getOpcode() == Instruction::LShr && !I->isExact()) { 57 I->setIsExact(); 58 MadeChange = true; 59 } 60 61 if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) { 62 I->setHasNoUnsignedWrap(); 63 MadeChange = true; 64 } 65 } 66 67 // TODO: Lots more we could do here: 68 // If V is a phi node, we can call this on each of its operands. 69 // "select cond, X, 0" can simplify to "X". 70 71 return MadeChange ? V : 0; 72} 73 74 75/// MultiplyOverflows - True if the multiply can not be expressed in an int 76/// this size. 77static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) { 78 uint32_t W = C1->getBitWidth(); 79 APInt LHSExt = C1->getValue(), RHSExt = C2->getValue(); 80 if (sign) { 81 LHSExt = LHSExt.sext(W * 2); 82 RHSExt = RHSExt.sext(W * 2); 83 } else { 84 LHSExt = LHSExt.zext(W * 2); 85 RHSExt = RHSExt.zext(W * 2); 86 } 87 88 APInt MulExt = LHSExt * RHSExt; 89 90 if (!sign) 91 return MulExt.ugt(APInt::getLowBitsSet(W * 2, W)); 92 93 APInt Min = APInt::getSignedMinValue(W).sext(W * 2); 94 APInt Max = APInt::getSignedMaxValue(W).sext(W * 2); 95 return MulExt.slt(Min) || MulExt.sgt(Max); 96} 97 98/// \brief A helper routine of InstCombiner::visitMul(). 99/// 100/// If C is a vector of known powers of 2, then this function returns 101/// a new vector obtained from C replacing each element with its logBase2. 102/// Return a null pointer otherwise. 103static Constant *getLogBase2Vector(ConstantDataVector *CV) { 104 const APInt *IVal; 105 SmallVector<Constant *, 4> Elts; 106 107 for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) { 108 Constant *Elt = CV->getElementAsConstant(I); 109 if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2()) 110 return 0; 111 Elts.push_back(ConstantInt::get(Elt->getType(), IVal->logBase2())); 112 } 113 114 return ConstantVector::get(Elts); 115} 116 117Instruction *InstCombiner::visitMul(BinaryOperator &I) { 118 bool Changed = SimplifyAssociativeOrCommutative(I); 119 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 120 121 if (Value *V = SimplifyMulInst(Op0, Op1, TD)) 122 return ReplaceInstUsesWith(I, V); 123 124 if (Value *V = SimplifyUsingDistributiveLaws(I)) 125 return ReplaceInstUsesWith(I, V); 126 127 if (match(Op1, m_AllOnes())) // X * -1 == 0 - X 128 return BinaryOperator::CreateNeg(Op0, I.getName()); 129 130 // Also allow combining multiply instructions on vectors. 131 { 132 Value *NewOp; 133 Constant *C1, *C2; 134 const APInt *IVal; 135 if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)), 136 m_Constant(C1))) && 137 match(C1, m_APInt(IVal))) 138 // ((X << C1)*C2) == (X * (C2 << C1)) 139 return BinaryOperator::CreateMul(NewOp, ConstantExpr::getShl(C1, C2)); 140 141 if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) { 142 Constant *NewCst = 0; 143 if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2()) 144 // Replace X*(2^C) with X << C, where C is either a scalar or a splat. 145 NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2()); 146 else if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(C1)) 147 // Replace X*(2^C) with X << C, where C is a vector of known 148 // constant powers of 2. 149 NewCst = getLogBase2Vector(CV); 150 151 if (NewCst) { 152 BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst); 153 if (I.hasNoSignedWrap()) Shl->setHasNoSignedWrap(); 154 if (I.hasNoUnsignedWrap()) Shl->setHasNoUnsignedWrap(); 155 return Shl; 156 } 157 } 158 } 159 160 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 161 // Canonicalize (X+C1)*CI -> X*CI+C1*CI. 162 { Value *X; ConstantInt *C1; 163 if (Op0->hasOneUse() && 164 match(Op0, m_Add(m_Value(X), m_ConstantInt(C1)))) { 165 Value *Add = Builder->CreateMul(X, CI); 166 return BinaryOperator::CreateAdd(Add, Builder->CreateMul(C1, CI)); 167 } 168 } 169 170 // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n 171 // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n 172 // The "* (2**n)" thus becomes a potential shifting opportunity. 173 { 174 const APInt & Val = CI->getValue(); 175 const APInt &PosVal = Val.abs(); 176 if (Val.isNegative() && PosVal.isPowerOf2()) { 177 Value *X = 0, *Y = 0; 178 if (Op0->hasOneUse()) { 179 ConstantInt *C1; 180 Value *Sub = 0; 181 if (match(Op0, m_Sub(m_Value(Y), m_Value(X)))) 182 Sub = Builder->CreateSub(X, Y, "suba"); 183 else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1)))) 184 Sub = Builder->CreateSub(Builder->CreateNeg(C1), Y, "subc"); 185 if (Sub) 186 return 187 BinaryOperator::CreateMul(Sub, 188 ConstantInt::get(Y->getType(), PosVal)); 189 } 190 } 191 } 192 } 193 194 // Simplify mul instructions with a constant RHS. 195 if (isa<Constant>(Op1)) { 196 // Try to fold constant mul into select arguments. 197 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 198 if (Instruction *R = FoldOpIntoSelect(I, SI)) 199 return R; 200 201 if (isa<PHINode>(Op0)) 202 if (Instruction *NV = FoldOpIntoPhi(I)) 203 return NV; 204 } 205 206 if (Value *Op0v = dyn_castNegVal(Op0)) // -X * -Y = X*Y 207 if (Value *Op1v = dyn_castNegVal(Op1)) 208 return BinaryOperator::CreateMul(Op0v, Op1v); 209 210 // (X / Y) * Y = X - (X % Y) 211 // (X / Y) * -Y = (X % Y) - X 212 { 213 Value *Op1C = Op1; 214 BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0); 215 if (!BO || 216 (BO->getOpcode() != Instruction::UDiv && 217 BO->getOpcode() != Instruction::SDiv)) { 218 Op1C = Op0; 219 BO = dyn_cast<BinaryOperator>(Op1); 220 } 221 Value *Neg = dyn_castNegVal(Op1C); 222 if (BO && BO->hasOneUse() && 223 (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) && 224 (BO->getOpcode() == Instruction::UDiv || 225 BO->getOpcode() == Instruction::SDiv)) { 226 Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1); 227 228 // If the division is exact, X % Y is zero, so we end up with X or -X. 229 if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO)) 230 if (SDiv->isExact()) { 231 if (Op1BO == Op1C) 232 return ReplaceInstUsesWith(I, Op0BO); 233 return BinaryOperator::CreateNeg(Op0BO); 234 } 235 236 Value *Rem; 237 if (BO->getOpcode() == Instruction::UDiv) 238 Rem = Builder->CreateURem(Op0BO, Op1BO); 239 else 240 Rem = Builder->CreateSRem(Op0BO, Op1BO); 241 Rem->takeName(BO); 242 243 if (Op1BO == Op1C) 244 return BinaryOperator::CreateSub(Op0BO, Rem); 245 return BinaryOperator::CreateSub(Rem, Op0BO); 246 } 247 } 248 249 /// i1 mul -> i1 and. 250 if (I.getType()->isIntegerTy(1)) 251 return BinaryOperator::CreateAnd(Op0, Op1); 252 253 // X*(1 << Y) --> X << Y 254 // (1 << Y)*X --> X << Y 255 { 256 Value *Y; 257 if (match(Op0, m_Shl(m_One(), m_Value(Y)))) 258 return BinaryOperator::CreateShl(Op1, Y); 259 if (match(Op1, m_Shl(m_One(), m_Value(Y)))) 260 return BinaryOperator::CreateShl(Op0, Y); 261 } 262 263 // If one of the operands of the multiply is a cast from a boolean value, then 264 // we know the bool is either zero or one, so this is a 'masking' multiply. 265 // X * Y (where Y is 0 or 1) -> X & (0-Y) 266 if (!I.getType()->isVectorTy()) { 267 // -2 is "-1 << 1" so it is all bits set except the low one. 268 APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true); 269 270 Value *BoolCast = 0, *OtherOp = 0; 271 if (MaskedValueIsZero(Op0, Negative2)) 272 BoolCast = Op0, OtherOp = Op1; 273 else if (MaskedValueIsZero(Op1, Negative2)) 274 BoolCast = Op1, OtherOp = Op0; 275 276 if (BoolCast) { 277 Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()), 278 BoolCast); 279 return BinaryOperator::CreateAnd(V, OtherOp); 280 } 281 } 282 283 return Changed ? &I : 0; 284} 285 286// 287// Detect pattern: 288// 289// log2(Y*0.5) 290// 291// And check for corresponding fast math flags 292// 293 294static void detectLog2OfHalf(Value *&Op, Value *&Y, IntrinsicInst *&Log2) { 295 296 if (!Op->hasOneUse()) 297 return; 298 299 IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op); 300 if (!II) 301 return; 302 if (II->getIntrinsicID() != Intrinsic::log2 || !II->hasUnsafeAlgebra()) 303 return; 304 Log2 = II; 305 306 Value *OpLog2Of = II->getArgOperand(0); 307 if (!OpLog2Of->hasOneUse()) 308 return; 309 310 Instruction *I = dyn_cast<Instruction>(OpLog2Of); 311 if (!I) 312 return; 313 if (I->getOpcode() != Instruction::FMul || !I->hasUnsafeAlgebra()) 314 return; 315 316 ConstantFP *CFP = dyn_cast<ConstantFP>(I->getOperand(0)); 317 if (CFP && CFP->isExactlyValue(0.5)) { 318 Y = I->getOperand(1); 319 return; 320 } 321 CFP = dyn_cast<ConstantFP>(I->getOperand(1)); 322 if (CFP && CFP->isExactlyValue(0.5)) 323 Y = I->getOperand(0); 324} 325 326/// Helper function of InstCombiner::visitFMul(BinaryOperator(). It returns 327/// true iff the given value is FMul or FDiv with one and only one operand 328/// being a normal constant (i.e. not Zero/NaN/Infinity). 329static bool isFMulOrFDivWithConstant(Value *V) { 330 Instruction *I = dyn_cast<Instruction>(V); 331 if (!I || (I->getOpcode() != Instruction::FMul && 332 I->getOpcode() != Instruction::FDiv)) 333 return false; 334 335 ConstantFP *C0 = dyn_cast<ConstantFP>(I->getOperand(0)); 336 ConstantFP *C1 = dyn_cast<ConstantFP>(I->getOperand(1)); 337 338 if (C0 && C1) 339 return false; 340 341 return (C0 && C0->getValueAPF().isFiniteNonZero()) || 342 (C1 && C1->getValueAPF().isFiniteNonZero()); 343} 344 345static bool isNormalFp(const ConstantFP *C) { 346 const APFloat &Flt = C->getValueAPF(); 347 return Flt.isNormal(); 348} 349 350/// foldFMulConst() is a helper routine of InstCombiner::visitFMul(). 351/// The input \p FMulOrDiv is a FMul/FDiv with one and only one operand 352/// being a constant (i.e. isFMulOrFDivWithConstant(FMulOrDiv) == true). 353/// This function is to simplify "FMulOrDiv * C" and returns the 354/// resulting expression. Note that this function could return NULL in 355/// case the constants cannot be folded into a normal floating-point. 356/// 357Value *InstCombiner::foldFMulConst(Instruction *FMulOrDiv, ConstantFP *C, 358 Instruction *InsertBefore) { 359 assert(isFMulOrFDivWithConstant(FMulOrDiv) && "V is invalid"); 360 361 Value *Opnd0 = FMulOrDiv->getOperand(0); 362 Value *Opnd1 = FMulOrDiv->getOperand(1); 363 364 ConstantFP *C0 = dyn_cast<ConstantFP>(Opnd0); 365 ConstantFP *C1 = dyn_cast<ConstantFP>(Opnd1); 366 367 BinaryOperator *R = 0; 368 369 // (X * C0) * C => X * (C0*C) 370 if (FMulOrDiv->getOpcode() == Instruction::FMul) { 371 Constant *F = ConstantExpr::getFMul(C1 ? C1 : C0, C); 372 if (isNormalFp(cast<ConstantFP>(F))) 373 R = BinaryOperator::CreateFMul(C1 ? Opnd0 : Opnd1, F); 374 } else { 375 if (C0) { 376 // (C0 / X) * C => (C0 * C) / X 377 ConstantFP *F = cast<ConstantFP>(ConstantExpr::getFMul(C0, C)); 378 if (isNormalFp(F)) 379 R = BinaryOperator::CreateFDiv(F, Opnd1); 380 } else { 381 // (X / C1) * C => X * (C/C1) if C/C1 is not a denormal 382 ConstantFP *F = cast<ConstantFP>(ConstantExpr::getFDiv(C, C1)); 383 if (isNormalFp(F)) { 384 R = BinaryOperator::CreateFMul(Opnd0, F); 385 } else { 386 // (X / C1) * C => X / (C1/C) 387 Constant *F = ConstantExpr::getFDiv(C1, C); 388 if (isNormalFp(cast<ConstantFP>(F))) 389 R = BinaryOperator::CreateFDiv(Opnd0, F); 390 } 391 } 392 } 393 394 if (R) { 395 R->setHasUnsafeAlgebra(true); 396 InsertNewInstWith(R, *InsertBefore); 397 } 398 399 return R; 400} 401 402Instruction *InstCombiner::visitFMul(BinaryOperator &I) { 403 bool Changed = SimplifyAssociativeOrCommutative(I); 404 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 405 406 if (isa<Constant>(Op0)) 407 std::swap(Op0, Op1); 408 409 if (Value *V = SimplifyFMulInst(Op0, Op1, I.getFastMathFlags(), TD)) 410 return ReplaceInstUsesWith(I, V); 411 412 bool AllowReassociate = I.hasUnsafeAlgebra(); 413 414 // Simplify mul instructions with a constant RHS. 415 if (isa<Constant>(Op1)) { 416 // Try to fold constant mul into select arguments. 417 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 418 if (Instruction *R = FoldOpIntoSelect(I, SI)) 419 return R; 420 421 if (isa<PHINode>(Op0)) 422 if (Instruction *NV = FoldOpIntoPhi(I)) 423 return NV; 424 425 ConstantFP *C = dyn_cast<ConstantFP>(Op1); 426 if (C && AllowReassociate && C->getValueAPF().isFiniteNonZero()) { 427 // Let MDC denote an expression in one of these forms: 428 // X * C, C/X, X/C, where C is a constant. 429 // 430 // Try to simplify "MDC * Constant" 431 if (isFMulOrFDivWithConstant(Op0)) { 432 Value *V = foldFMulConst(cast<Instruction>(Op0), C, &I); 433 if (V) 434 return ReplaceInstUsesWith(I, V); 435 } 436 437 // (MDC +/- C1) * C => (MDC * C) +/- (C1 * C) 438 Instruction *FAddSub = dyn_cast<Instruction>(Op0); 439 if (FAddSub && 440 (FAddSub->getOpcode() == Instruction::FAdd || 441 FAddSub->getOpcode() == Instruction::FSub)) { 442 Value *Opnd0 = FAddSub->getOperand(0); 443 Value *Opnd1 = FAddSub->getOperand(1); 444 ConstantFP *C0 = dyn_cast<ConstantFP>(Opnd0); 445 ConstantFP *C1 = dyn_cast<ConstantFP>(Opnd1); 446 bool Swap = false; 447 if (C0) { 448 std::swap(C0, C1); 449 std::swap(Opnd0, Opnd1); 450 Swap = true; 451 } 452 453 if (C1 && C1->getValueAPF().isFiniteNonZero() && 454 isFMulOrFDivWithConstant(Opnd0)) { 455 Value *M1 = ConstantExpr::getFMul(C1, C); 456 Value *M0 = isNormalFp(cast<ConstantFP>(M1)) ? 457 foldFMulConst(cast<Instruction>(Opnd0), C, &I) : 458 0; 459 if (M0 && M1) { 460 if (Swap && FAddSub->getOpcode() == Instruction::FSub) 461 std::swap(M0, M1); 462 463 Value *R = (FAddSub->getOpcode() == Instruction::FAdd) ? 464 BinaryOperator::CreateFAdd(M0, M1) : 465 BinaryOperator::CreateFSub(M0, M1); 466 Instruction *RI = cast<Instruction>(R); 467 RI->copyFastMathFlags(&I); 468 return RI; 469 } 470 } 471 } 472 } 473 } 474 475 476 // Under unsafe algebra do: 477 // X * log2(0.5*Y) = X*log2(Y) - X 478 if (I.hasUnsafeAlgebra()) { 479 Value *OpX = NULL; 480 Value *OpY = NULL; 481 IntrinsicInst *Log2; 482 detectLog2OfHalf(Op0, OpY, Log2); 483 if (OpY) { 484 OpX = Op1; 485 } else { 486 detectLog2OfHalf(Op1, OpY, Log2); 487 if (OpY) { 488 OpX = Op0; 489 } 490 } 491 // if pattern detected emit alternate sequence 492 if (OpX && OpY) { 493 Log2->setArgOperand(0, OpY); 494 Value *FMulVal = Builder->CreateFMul(OpX, Log2); 495 Instruction *FMul = cast<Instruction>(FMulVal); 496 FMul->copyFastMathFlags(Log2); 497 Instruction *FSub = BinaryOperator::CreateFSub(FMulVal, OpX); 498 FSub->copyFastMathFlags(Log2); 499 return FSub; 500 } 501 } 502 503 // Handle symmetric situation in a 2-iteration loop 504 Value *Opnd0 = Op0; 505 Value *Opnd1 = Op1; 506 for (int i = 0; i < 2; i++) { 507 bool IgnoreZeroSign = I.hasNoSignedZeros(); 508 if (BinaryOperator::isFNeg(Opnd0, IgnoreZeroSign)) { 509 Value *N0 = dyn_castFNegVal(Opnd0, IgnoreZeroSign); 510 Value *N1 = dyn_castFNegVal(Opnd1, IgnoreZeroSign); 511 512 // -X * -Y => X*Y 513 if (N1) 514 return BinaryOperator::CreateFMul(N0, N1); 515 516 if (Opnd0->hasOneUse()) { 517 // -X * Y => -(X*Y) (Promote negation as high as possible) 518 Value *T = Builder->CreateFMul(N0, Opnd1); 519 cast<Instruction>(T)->setDebugLoc(I.getDebugLoc()); 520 Instruction *Neg = BinaryOperator::CreateFNeg(T); 521 if (I.getFastMathFlags().any()) { 522 cast<Instruction>(T)->copyFastMathFlags(&I); 523 Neg->copyFastMathFlags(&I); 524 } 525 return Neg; 526 } 527 } 528 529 // (X*Y) * X => (X*X) * Y where Y != X 530 // The purpose is two-fold: 531 // 1) to form a power expression (of X). 532 // 2) potentially shorten the critical path: After transformation, the 533 // latency of the instruction Y is amortized by the expression of X*X, 534 // and therefore Y is in a "less critical" position compared to what it 535 // was before the transformation. 536 // 537 if (AllowReassociate) { 538 Value *Opnd0_0, *Opnd0_1; 539 if (Opnd0->hasOneUse() && 540 match(Opnd0, m_FMul(m_Value(Opnd0_0), m_Value(Opnd0_1)))) { 541 Value *Y = 0; 542 if (Opnd0_0 == Opnd1 && Opnd0_1 != Opnd1) 543 Y = Opnd0_1; 544 else if (Opnd0_1 == Opnd1 && Opnd0_0 != Opnd1) 545 Y = Opnd0_0; 546 547 if (Y) { 548 Instruction *T = cast<Instruction>(Builder->CreateFMul(Opnd1, Opnd1)); 549 T->copyFastMathFlags(&I); 550 T->setDebugLoc(I.getDebugLoc()); 551 552 Instruction *R = BinaryOperator::CreateFMul(T, Y); 553 R->copyFastMathFlags(&I); 554 return R; 555 } 556 } 557 } 558 559 if (!isa<Constant>(Op1)) 560 std::swap(Opnd0, Opnd1); 561 else 562 break; 563 } 564 565 return Changed ? &I : 0; 566} 567 568/// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select 569/// instruction. 570bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { 571 SelectInst *SI = cast<SelectInst>(I.getOperand(1)); 572 573 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y 574 int NonNullOperand = -1; 575 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1))) 576 if (ST->isNullValue()) 577 NonNullOperand = 2; 578 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y 579 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2))) 580 if (ST->isNullValue()) 581 NonNullOperand = 1; 582 583 if (NonNullOperand == -1) 584 return false; 585 586 Value *SelectCond = SI->getOperand(0); 587 588 // Change the div/rem to use 'Y' instead of the select. 589 I.setOperand(1, SI->getOperand(NonNullOperand)); 590 591 // Okay, we know we replace the operand of the div/rem with 'Y' with no 592 // problem. However, the select, or the condition of the select may have 593 // multiple uses. Based on our knowledge that the operand must be non-zero, 594 // propagate the known value for the select into other uses of it, and 595 // propagate a known value of the condition into its other users. 596 597 // If the select and condition only have a single use, don't bother with this, 598 // early exit. 599 if (SI->use_empty() && SelectCond->hasOneUse()) 600 return true; 601 602 // Scan the current block backward, looking for other uses of SI. 603 BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin(); 604 605 while (BBI != BBFront) { 606 --BBI; 607 // If we found a call to a function, we can't assume it will return, so 608 // information from below it cannot be propagated above it. 609 if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI)) 610 break; 611 612 // Replace uses of the select or its condition with the known values. 613 for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end(); 614 I != E; ++I) { 615 if (*I == SI) { 616 *I = SI->getOperand(NonNullOperand); 617 Worklist.Add(BBI); 618 } else if (*I == SelectCond) { 619 *I = Builder->getInt1(NonNullOperand == 1); 620 Worklist.Add(BBI); 621 } 622 } 623 624 // If we past the instruction, quit looking for it. 625 if (&*BBI == SI) 626 SI = 0; 627 if (&*BBI == SelectCond) 628 SelectCond = 0; 629 630 // If we ran out of things to eliminate, break out of the loop. 631 if (SelectCond == 0 && SI == 0) 632 break; 633 634 } 635 return true; 636} 637 638 639/// This function implements the transforms common to both integer division 640/// instructions (udiv and sdiv). It is called by the visitors to those integer 641/// division instructions. 642/// @brief Common integer divide transforms 643Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { 644 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 645 646 // The RHS is known non-zero. 647 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 648 I.setOperand(1, V); 649 return &I; 650 } 651 652 // Handle cases involving: [su]div X, (select Cond, Y, Z) 653 // This does not apply for fdiv. 654 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 655 return &I; 656 657 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 658 // (X / C1) / C2 -> X / (C1*C2) 659 if (Instruction *LHS = dyn_cast<Instruction>(Op0)) 660 if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode()) 661 if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) { 662 if (MultiplyOverflows(RHS, LHSRHS, 663 I.getOpcode()==Instruction::SDiv)) 664 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 665 return BinaryOperator::Create(I.getOpcode(), LHS->getOperand(0), 666 ConstantExpr::getMul(RHS, LHSRHS)); 667 } 668 669 if (!RHS->isZero()) { // avoid X udiv 0 670 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 671 if (Instruction *R = FoldOpIntoSelect(I, SI)) 672 return R; 673 if (isa<PHINode>(Op0)) 674 if (Instruction *NV = FoldOpIntoPhi(I)) 675 return NV; 676 } 677 } 678 679 // See if we can fold away this div instruction. 680 if (SimplifyDemandedInstructionBits(I)) 681 return &I; 682 683 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y 684 Value *X = 0, *Z = 0; 685 if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1 686 bool isSigned = I.getOpcode() == Instruction::SDiv; 687 if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || 688 (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) 689 return BinaryOperator::Create(I.getOpcode(), X, Op1); 690 } 691 692 return 0; 693} 694 695/// dyn_castZExtVal - Checks if V is a zext or constant that can 696/// be truncated to Ty without losing bits. 697static Value *dyn_castZExtVal(Value *V, Type *Ty) { 698 if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) { 699 if (Z->getSrcTy() == Ty) 700 return Z->getOperand(0); 701 } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) { 702 if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth()) 703 return ConstantExpr::getTrunc(C, Ty); 704 } 705 return 0; 706} 707 708namespace { 709const unsigned MaxDepth = 6; 710typedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1, 711 const BinaryOperator &I, 712 InstCombiner &IC); 713 714/// \brief Used to maintain state for visitUDivOperand(). 715struct UDivFoldAction { 716 FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this 717 ///< operand. This can be zero if this action 718 ///< joins two actions together. 719 720 Value *OperandToFold; ///< Which operand to fold. 721 union { 722 Instruction *FoldResult; ///< The instruction returned when FoldAction is 723 ///< invoked. 724 725 size_t SelectLHSIdx; ///< Stores the LHS action index if this action 726 ///< joins two actions together. 727 }; 728 729 UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand) 730 : FoldAction(FA), OperandToFold(InputOperand), FoldResult(0) {} 731 UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS) 732 : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {} 733}; 734} 735 736// X udiv 2^C -> X >> C 737static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1, 738 const BinaryOperator &I, InstCombiner &IC) { 739 const APInt &C = cast<Constant>(Op1)->getUniqueInteger(); 740 BinaryOperator *LShr = BinaryOperator::CreateLShr( 741 Op0, ConstantInt::get(Op0->getType(), C.logBase2())); 742 if (I.isExact()) LShr->setIsExact(); 743 return LShr; 744} 745 746// X udiv C, where C >= signbit 747static Instruction *foldUDivNegCst(Value *Op0, Value *Op1, 748 const BinaryOperator &I, InstCombiner &IC) { 749 Value *ICI = IC.Builder->CreateICmpULT(Op0, cast<ConstantInt>(Op1)); 750 751 return SelectInst::Create(ICI, Constant::getNullValue(I.getType()), 752 ConstantInt::get(I.getType(), 1)); 753} 754 755// X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 756static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I, 757 InstCombiner &IC) { 758 Instruction *ShiftLeft = cast<Instruction>(Op1); 759 if (isa<ZExtInst>(ShiftLeft)) 760 ShiftLeft = cast<Instruction>(ShiftLeft->getOperand(0)); 761 762 const APInt &CI = 763 cast<Constant>(ShiftLeft->getOperand(0))->getUniqueInteger(); 764 Value *N = ShiftLeft->getOperand(1); 765 if (CI != 1) 766 N = IC.Builder->CreateAdd(N, ConstantInt::get(N->getType(), CI.logBase2())); 767 if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1)) 768 N = IC.Builder->CreateZExt(N, Z->getDestTy()); 769 BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N); 770 if (I.isExact()) LShr->setIsExact(); 771 return LShr; 772} 773 774// \brief Recursively visits the possible right hand operands of a udiv 775// instruction, seeing through select instructions, to determine if we can 776// replace the udiv with something simpler. If we find that an operand is not 777// able to simplify the udiv, we abort the entire transformation. 778static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I, 779 SmallVectorImpl<UDivFoldAction> &Actions, 780 unsigned Depth = 0) { 781 // Check to see if this is an unsigned division with an exact power of 2, 782 // if so, convert to a right shift. 783 if (match(Op1, m_Power2())) { 784 Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1)); 785 return Actions.size(); 786 } 787 788 if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) 789 // X udiv C, where C >= signbit 790 if (C->getValue().isNegative()) { 791 Actions.push_back(UDivFoldAction(foldUDivNegCst, C)); 792 return Actions.size(); 793 } 794 795 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 796 if (match(Op1, m_Shl(m_Power2(), m_Value())) || 797 match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) { 798 Actions.push_back(UDivFoldAction(foldUDivShl, Op1)); 799 return Actions.size(); 800 } 801 802 // The remaining tests are all recursive, so bail out if we hit the limit. 803 if (Depth++ == MaxDepth) 804 return 0; 805 806 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 807 if (size_t LHSIdx = visitUDivOperand(Op0, SI->getOperand(1), I, Actions)) 808 if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions)) { 809 Actions.push_back(UDivFoldAction((FoldUDivOperandCb)0, Op1, LHSIdx-1)); 810 return Actions.size(); 811 } 812 813 return 0; 814} 815 816Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { 817 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 818 819 if (Value *V = SimplifyUDivInst(Op0, Op1, TD)) 820 return ReplaceInstUsesWith(I, V); 821 822 // Handle the integer div common cases 823 if (Instruction *Common = commonIDivTransforms(I)) 824 return Common; 825 826 // (x lshr C1) udiv C2 --> x udiv (C2 << C1) 827 if (ConstantInt *C2 = dyn_cast<ConstantInt>(Op1)) { 828 Value *X; 829 ConstantInt *C1; 830 if (match(Op0, m_LShr(m_Value(X), m_ConstantInt(C1)))) { 831 APInt NC = C2->getValue().shl(C1->getLimitedValue(C1->getBitWidth()-1)); 832 return BinaryOperator::CreateUDiv(X, Builder->getInt(NC)); 833 } 834 } 835 836 // (zext A) udiv (zext B) --> zext (A udiv B) 837 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 838 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 839 return new ZExtInst(Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", 840 I.isExact()), 841 I.getType()); 842 843 // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...)))) 844 SmallVector<UDivFoldAction, 6> UDivActions; 845 if (visitUDivOperand(Op0, Op1, I, UDivActions)) 846 for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) { 847 FoldUDivOperandCb Action = UDivActions[i].FoldAction; 848 Value *ActionOp1 = UDivActions[i].OperandToFold; 849 Instruction *Inst; 850 if (Action) 851 Inst = Action(Op0, ActionOp1, I, *this); 852 else { 853 // This action joins two actions together. The RHS of this action is 854 // simply the last action we processed, we saved the LHS action index in 855 // the joining action. 856 size_t SelectRHSIdx = i - 1; 857 Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult; 858 size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx; 859 Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult; 860 Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(), 861 SelectLHS, SelectRHS); 862 } 863 864 // If this is the last action to process, return it to the InstCombiner. 865 // Otherwise, we insert it before the UDiv and record it so that we may 866 // use it as part of a joining action (i.e., a SelectInst). 867 if (e - i != 1) { 868 Inst->insertBefore(&I); 869 UDivActions[i].FoldResult = Inst; 870 } else 871 return Inst; 872 } 873 874 return 0; 875} 876 877Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { 878 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 879 880 if (Value *V = SimplifySDivInst(Op0, Op1, TD)) 881 return ReplaceInstUsesWith(I, V); 882 883 // Handle the integer div common cases 884 if (Instruction *Common = commonIDivTransforms(I)) 885 return Common; 886 887 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 888 // sdiv X, -1 == -X 889 if (RHS->isAllOnesValue()) 890 return BinaryOperator::CreateNeg(Op0); 891 892 // sdiv X, C --> ashr exact X, log2(C) 893 if (I.isExact() && RHS->getValue().isNonNegative() && 894 RHS->getValue().isPowerOf2()) { 895 Value *ShAmt = llvm::ConstantInt::get(RHS->getType(), 896 RHS->getValue().exactLogBase2()); 897 return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName()); 898 } 899 900 // -X/C --> X/-C provided the negation doesn't overflow. 901 if (SubOperator *Sub = dyn_cast<SubOperator>(Op0)) 902 if (match(Sub->getOperand(0), m_Zero()) && Sub->hasNoSignedWrap()) 903 return BinaryOperator::CreateSDiv(Sub->getOperand(1), 904 ConstantExpr::getNeg(RHS)); 905 } 906 907 // If the sign bits of both operands are zero (i.e. we can prove they are 908 // unsigned inputs), turn this into a udiv. 909 if (I.getType()->isIntegerTy()) { 910 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 911 if (MaskedValueIsZero(Op0, Mask)) { 912 if (MaskedValueIsZero(Op1, Mask)) { 913 // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set 914 return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 915 } 916 917 if (match(Op1, m_Shl(m_Power2(), m_Value()))) { 918 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) 919 // Safe because the only negative value (1 << Y) can take on is 920 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have 921 // the sign bit set. 922 return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 923 } 924 } 925 } 926 927 return 0; 928} 929 930/// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special 931/// FP value and: 932/// 1) 1/C is exact, or 933/// 2) reciprocal is allowed. 934/// If the conversion was successful, the simplified expression "X * 1/C" is 935/// returned; otherwise, NULL is returned. 936/// 937static Instruction *CvtFDivConstToReciprocal(Value *Dividend, 938 ConstantFP *Divisor, 939 bool AllowReciprocal) { 940 const APFloat &FpVal = Divisor->getValueAPF(); 941 APFloat Reciprocal(FpVal.getSemantics()); 942 bool Cvt = FpVal.getExactInverse(&Reciprocal); 943 944 if (!Cvt && AllowReciprocal && FpVal.isFiniteNonZero()) { 945 Reciprocal = APFloat(FpVal.getSemantics(), 1.0f); 946 (void)Reciprocal.divide(FpVal, APFloat::rmNearestTiesToEven); 947 Cvt = !Reciprocal.isDenormal(); 948 } 949 950 if (!Cvt) 951 return 0; 952 953 ConstantFP *R; 954 R = ConstantFP::get(Dividend->getType()->getContext(), Reciprocal); 955 return BinaryOperator::CreateFMul(Dividend, R); 956} 957 958Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { 959 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 960 961 if (Value *V = SimplifyFDivInst(Op0, Op1, TD)) 962 return ReplaceInstUsesWith(I, V); 963 964 bool AllowReassociate = I.hasUnsafeAlgebra(); 965 bool AllowReciprocal = I.hasAllowReciprocal(); 966 967 if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) { 968 if (AllowReassociate) { 969 ConstantFP *C1 = 0; 970 ConstantFP *C2 = Op1C; 971 Value *X; 972 Instruction *Res = 0; 973 974 if (match(Op0, m_FMul(m_Value(X), m_ConstantFP(C1)))) { 975 // (X*C1)/C2 => X * (C1/C2) 976 // 977 Constant *C = ConstantExpr::getFDiv(C1, C2); 978 const APFloat &F = cast<ConstantFP>(C)->getValueAPF(); 979 if (F.isNormal()) 980 Res = BinaryOperator::CreateFMul(X, C); 981 } else if (match(Op0, m_FDiv(m_Value(X), m_ConstantFP(C1)))) { 982 // (X/C1)/C2 => X /(C2*C1) [=> X * 1/(C2*C1) if reciprocal is allowed] 983 // 984 Constant *C = ConstantExpr::getFMul(C1, C2); 985 const APFloat &F = cast<ConstantFP>(C)->getValueAPF(); 986 if (F.isNormal()) { 987 Res = CvtFDivConstToReciprocal(X, cast<ConstantFP>(C), 988 AllowReciprocal); 989 if (!Res) 990 Res = BinaryOperator::CreateFDiv(X, C); 991 } 992 } 993 994 if (Res) { 995 Res->setFastMathFlags(I.getFastMathFlags()); 996 return Res; 997 } 998 } 999 1000 // X / C => X * 1/C 1001 if (Instruction *T = CvtFDivConstToReciprocal(Op0, Op1C, AllowReciprocal)) 1002 return T; 1003 1004 return 0; 1005 } 1006 1007 if (AllowReassociate && isa<ConstantFP>(Op0)) { 1008 ConstantFP *C1 = cast<ConstantFP>(Op0), *C2; 1009 Constant *Fold = 0; 1010 Value *X; 1011 bool CreateDiv = true; 1012 1013 // C1 / (X*C2) => (C1/C2) / X 1014 if (match(Op1, m_FMul(m_Value(X), m_ConstantFP(C2)))) 1015 Fold = ConstantExpr::getFDiv(C1, C2); 1016 else if (match(Op1, m_FDiv(m_Value(X), m_ConstantFP(C2)))) { 1017 // C1 / (X/C2) => (C1*C2) / X 1018 Fold = ConstantExpr::getFMul(C1, C2); 1019 } else if (match(Op1, m_FDiv(m_ConstantFP(C2), m_Value(X)))) { 1020 // C1 / (C2/X) => (C1/C2) * X 1021 Fold = ConstantExpr::getFDiv(C1, C2); 1022 CreateDiv = false; 1023 } 1024 1025 if (Fold) { 1026 const APFloat &FoldC = cast<ConstantFP>(Fold)->getValueAPF(); 1027 if (FoldC.isNormal()) { 1028 Instruction *R = CreateDiv ? 1029 BinaryOperator::CreateFDiv(Fold, X) : 1030 BinaryOperator::CreateFMul(X, Fold); 1031 R->setFastMathFlags(I.getFastMathFlags()); 1032 return R; 1033 } 1034 } 1035 return 0; 1036 } 1037 1038 if (AllowReassociate) { 1039 Value *X, *Y; 1040 Value *NewInst = 0; 1041 Instruction *SimpR = 0; 1042 1043 if (Op0->hasOneUse() && match(Op0, m_FDiv(m_Value(X), m_Value(Y)))) { 1044 // (X/Y) / Z => X / (Y*Z) 1045 // 1046 if (!isa<ConstantFP>(Y) || !isa<ConstantFP>(Op1)) { 1047 NewInst = Builder->CreateFMul(Y, Op1); 1048 SimpR = BinaryOperator::CreateFDiv(X, NewInst); 1049 } 1050 } else if (Op1->hasOneUse() && match(Op1, m_FDiv(m_Value(X), m_Value(Y)))) { 1051 // Z / (X/Y) => Z*Y / X 1052 // 1053 if (!isa<ConstantFP>(Y) || !isa<ConstantFP>(Op0)) { 1054 NewInst = Builder->CreateFMul(Op0, Y); 1055 SimpR = BinaryOperator::CreateFDiv(NewInst, X); 1056 } 1057 } 1058 1059 if (NewInst) { 1060 if (Instruction *T = dyn_cast<Instruction>(NewInst)) 1061 T->setDebugLoc(I.getDebugLoc()); 1062 SimpR->setFastMathFlags(I.getFastMathFlags()); 1063 return SimpR; 1064 } 1065 } 1066 1067 return 0; 1068} 1069 1070/// This function implements the transforms common to both integer remainder 1071/// instructions (urem and srem). It is called by the visitors to those integer 1072/// remainder instructions. 1073/// @brief Common integer remainder transforms 1074Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) { 1075 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1076 1077 // The RHS is known non-zero. 1078 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 1079 I.setOperand(1, V); 1080 return &I; 1081 } 1082 1083 // Handle cases involving: rem X, (select Cond, Y, Z) 1084 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 1085 return &I; 1086 1087 if (isa<ConstantInt>(Op1)) { 1088 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { 1089 if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { 1090 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1091 return R; 1092 } else if (isa<PHINode>(Op0I)) { 1093 if (Instruction *NV = FoldOpIntoPhi(I)) 1094 return NV; 1095 } 1096 1097 // See if we can fold away this rem instruction. 1098 if (SimplifyDemandedInstructionBits(I)) 1099 return &I; 1100 } 1101 } 1102 1103 return 0; 1104} 1105 1106Instruction *InstCombiner::visitURem(BinaryOperator &I) { 1107 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1108 1109 if (Value *V = SimplifyURemInst(Op0, Op1, TD)) 1110 return ReplaceInstUsesWith(I, V); 1111 1112 if (Instruction *common = commonIRemTransforms(I)) 1113 return common; 1114 1115 // (zext A) urem (zext B) --> zext (A urem B) 1116 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 1117 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 1118 return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), 1119 I.getType()); 1120 1121 // X urem Y -> X and Y-1, where Y is a power of 2, 1122 if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/true)) { 1123 Constant *N1 = Constant::getAllOnesValue(I.getType()); 1124 Value *Add = Builder->CreateAdd(Op1, N1); 1125 return BinaryOperator::CreateAnd(Op0, Add); 1126 } 1127 1128 return 0; 1129} 1130 1131Instruction *InstCombiner::visitSRem(BinaryOperator &I) { 1132 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1133 1134 if (Value *V = SimplifySRemInst(Op0, Op1, TD)) 1135 return ReplaceInstUsesWith(I, V); 1136 1137 // Handle the integer rem common cases 1138 if (Instruction *Common = commonIRemTransforms(I)) 1139 return Common; 1140 1141 if (Value *RHSNeg = dyn_castNegVal(Op1)) 1142 if (!isa<Constant>(RHSNeg) || 1143 (isa<ConstantInt>(RHSNeg) && 1144 cast<ConstantInt>(RHSNeg)->getValue().isStrictlyPositive())) { 1145 // X % -Y -> X % Y 1146 Worklist.AddValue(I.getOperand(1)); 1147 I.setOperand(1, RHSNeg); 1148 return &I; 1149 } 1150 1151 // If the sign bits of both operands are zero (i.e. we can prove they are 1152 // unsigned inputs), turn this into a urem. 1153 if (I.getType()->isIntegerTy()) { 1154 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 1155 if (MaskedValueIsZero(Op1, Mask) && MaskedValueIsZero(Op0, Mask)) { 1156 // X srem Y -> X urem Y, iff X and Y don't have sign bit set 1157 return BinaryOperator::CreateURem(Op0, Op1, I.getName()); 1158 } 1159 } 1160 1161 // If it's a constant vector, flip any negative values positive. 1162 if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) { 1163 Constant *C = cast<Constant>(Op1); 1164 unsigned VWidth = C->getType()->getVectorNumElements(); 1165 1166 bool hasNegative = false; 1167 bool hasMissing = false; 1168 for (unsigned i = 0; i != VWidth; ++i) { 1169 Constant *Elt = C->getAggregateElement(i); 1170 if (Elt == 0) { 1171 hasMissing = true; 1172 break; 1173 } 1174 1175 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt)) 1176 if (RHS->isNegative()) 1177 hasNegative = true; 1178 } 1179 1180 if (hasNegative && !hasMissing) { 1181 SmallVector<Constant *, 16> Elts(VWidth); 1182 for (unsigned i = 0; i != VWidth; ++i) { 1183 Elts[i] = C->getAggregateElement(i); // Handle undef, etc. 1184 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) { 1185 if (RHS->isNegative()) 1186 Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); 1187 } 1188 } 1189 1190 Constant *NewRHSV = ConstantVector::get(Elts); 1191 if (NewRHSV != C) { // Don't loop on -MININT 1192 Worklist.AddValue(I.getOperand(1)); 1193 I.setOperand(1, NewRHSV); 1194 return &I; 1195 } 1196 } 1197 } 1198 1199 return 0; 1200} 1201 1202Instruction *InstCombiner::visitFRem(BinaryOperator &I) { 1203 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1204 1205 if (Value *V = SimplifyFRemInst(Op0, Op1, TD)) 1206 return ReplaceInstUsesWith(I, V); 1207 1208 // Handle cases involving: rem X, (select Cond, Y, Z) 1209 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 1210 return &I; 1211 1212 return 0; 1213} 1214