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" 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 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. 77 static 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. 103 static 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 117 Instruction *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 294 static 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). 329 static 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 345 static 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 /// 357 Value *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 402 Instruction *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 // B * (uitofp i1 C) -> select C, B, 0 560 if (I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) { 561 Value *LHS = Op0, *RHS = Op1; 562 Value *B, *C; 563 if (!match(RHS, m_UIToFP(m_Value(C)))) 564 std::swap(LHS, RHS); 565 566 if (match(RHS, m_UIToFP(m_Value(C))) && C->getType()->isIntegerTy(1)) { 567 B = LHS; 568 Value *Zero = ConstantFP::getNegativeZero(B->getType()); 569 return SelectInst::Create(C, B, Zero); 570 } 571 } 572 573 // A * (1 - uitofp i1 C) -> select C, 0, A 574 if (I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) { 575 Value *LHS = Op0, *RHS = Op1; 576 Value *A, *C; 577 if (!match(RHS, m_FSub(m_FPOne(), m_UIToFP(m_Value(C))))) 578 std::swap(LHS, RHS); 579 580 if (match(RHS, m_FSub(m_FPOne(), m_UIToFP(m_Value(C)))) && 581 C->getType()->isIntegerTy(1)) { 582 A = LHS; 583 Value *Zero = ConstantFP::getNegativeZero(A->getType()); 584 return SelectInst::Create(C, Zero, A); 585 } 586 } 587 588 if (!isa<Constant>(Op1)) 589 std::swap(Opnd0, Opnd1); 590 else 591 break; 592 } 593 594 return Changed ? &I : 0; 595 } 596 597 /// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select 598 /// instruction. 599 bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { 600 SelectInst *SI = cast<SelectInst>(I.getOperand(1)); 601 602 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y 603 int NonNullOperand = -1; 604 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1))) 605 if (ST->isNullValue()) 606 NonNullOperand = 2; 607 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y 608 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2))) 609 if (ST->isNullValue()) 610 NonNullOperand = 1; 611 612 if (NonNullOperand == -1) 613 return false; 614 615 Value *SelectCond = SI->getOperand(0); 616 617 // Change the div/rem to use 'Y' instead of the select. 618 I.setOperand(1, SI->getOperand(NonNullOperand)); 619 620 // Okay, we know we replace the operand of the div/rem with 'Y' with no 621 // problem. However, the select, or the condition of the select may have 622 // multiple uses. Based on our knowledge that the operand must be non-zero, 623 // propagate the known value for the select into other uses of it, and 624 // propagate a known value of the condition into its other users. 625 626 // If the select and condition only have a single use, don't bother with this, 627 // early exit. 628 if (SI->use_empty() && SelectCond->hasOneUse()) 629 return true; 630 631 // Scan the current block backward, looking for other uses of SI. 632 BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin(); 633 634 while (BBI != BBFront) { 635 --BBI; 636 // If we found a call to a function, we can't assume it will return, so 637 // information from below it cannot be propagated above it. 638 if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI)) 639 break; 640 641 // Replace uses of the select or its condition with the known values. 642 for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end(); 643 I != E; ++I) { 644 if (*I == SI) { 645 *I = SI->getOperand(NonNullOperand); 646 Worklist.Add(BBI); 647 } else if (*I == SelectCond) { 648 *I = Builder->getInt1(NonNullOperand == 1); 649 Worklist.Add(BBI); 650 } 651 } 652 653 // If we past the instruction, quit looking for it. 654 if (&*BBI == SI) 655 SI = 0; 656 if (&*BBI == SelectCond) 657 SelectCond = 0; 658 659 // If we ran out of things to eliminate, break out of the loop. 660 if (SelectCond == 0 && SI == 0) 661 break; 662 663 } 664 return true; 665 } 666 667 668 /// This function implements the transforms common to both integer division 669 /// instructions (udiv and sdiv). It is called by the visitors to those integer 670 /// division instructions. 671 /// @brief Common integer divide transforms 672 Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { 673 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 674 675 // The RHS is known non-zero. 676 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 677 I.setOperand(1, V); 678 return &I; 679 } 680 681 // Handle cases involving: [su]div X, (select Cond, Y, Z) 682 // This does not apply for fdiv. 683 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 684 return &I; 685 686 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 687 // (X / C1) / C2 -> X / (C1*C2) 688 if (Instruction *LHS = dyn_cast<Instruction>(Op0)) 689 if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode()) 690 if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) { 691 if (MultiplyOverflows(RHS, LHSRHS, 692 I.getOpcode()==Instruction::SDiv)) 693 return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType())); 694 return BinaryOperator::Create(I.getOpcode(), LHS->getOperand(0), 695 ConstantExpr::getMul(RHS, LHSRHS)); 696 } 697 698 if (!RHS->isZero()) { // avoid X udiv 0 699 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 700 if (Instruction *R = FoldOpIntoSelect(I, SI)) 701 return R; 702 if (isa<PHINode>(Op0)) 703 if (Instruction *NV = FoldOpIntoPhi(I)) 704 return NV; 705 } 706 } 707 708 // See if we can fold away this div instruction. 709 if (SimplifyDemandedInstructionBits(I)) 710 return &I; 711 712 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y 713 Value *X = 0, *Z = 0; 714 if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1 715 bool isSigned = I.getOpcode() == Instruction::SDiv; 716 if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || 717 (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) 718 return BinaryOperator::Create(I.getOpcode(), X, Op1); 719 } 720 721 return 0; 722 } 723 724 /// dyn_castZExtVal - Checks if V is a zext or constant that can 725 /// be truncated to Ty without losing bits. 726 static Value *dyn_castZExtVal(Value *V, Type *Ty) { 727 if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) { 728 if (Z->getSrcTy() == Ty) 729 return Z->getOperand(0); 730 } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) { 731 if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth()) 732 return ConstantExpr::getTrunc(C, Ty); 733 } 734 return 0; 735 } 736 737 namespace { 738 const unsigned MaxDepth = 6; 739 typedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1, 740 const BinaryOperator &I, 741 InstCombiner &IC); 742 743 /// \brief Used to maintain state for visitUDivOperand(). 744 struct UDivFoldAction { 745 FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this 746 ///< operand. This can be zero if this action 747 ///< joins two actions together. 748 749 Value *OperandToFold; ///< Which operand to fold. 750 union { 751 Instruction *FoldResult; ///< The instruction returned when FoldAction is 752 ///< invoked. 753 754 size_t SelectLHSIdx; ///< Stores the LHS action index if this action 755 ///< joins two actions together. 756 }; 757 758 UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand) 759 : FoldAction(FA), OperandToFold(InputOperand), FoldResult(0) {} 760 UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS) 761 : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {} 762 }; 763 } 764 765 // X udiv 2^C -> X >> C 766 static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1, 767 const BinaryOperator &I, InstCombiner &IC) { 768 const APInt &C = cast<Constant>(Op1)->getUniqueInteger(); 769 BinaryOperator *LShr = BinaryOperator::CreateLShr( 770 Op0, ConstantInt::get(Op0->getType(), C.logBase2())); 771 if (I.isExact()) LShr->setIsExact(); 772 return LShr; 773 } 774 775 // X udiv C, where C >= signbit 776 static Instruction *foldUDivNegCst(Value *Op0, Value *Op1, 777 const BinaryOperator &I, InstCombiner &IC) { 778 Value *ICI = IC.Builder->CreateICmpULT(Op0, cast<ConstantInt>(Op1)); 779 780 return SelectInst::Create(ICI, Constant::getNullValue(I.getType()), 781 ConstantInt::get(I.getType(), 1)); 782 } 783 784 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 785 static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I, 786 InstCombiner &IC) { 787 Instruction *ShiftLeft = cast<Instruction>(Op1); 788 if (isa<ZExtInst>(ShiftLeft)) 789 ShiftLeft = cast<Instruction>(ShiftLeft->getOperand(0)); 790 791 const APInt &CI = 792 cast<Constant>(ShiftLeft->getOperand(0))->getUniqueInteger(); 793 Value *N = ShiftLeft->getOperand(1); 794 if (CI != 1) 795 N = IC.Builder->CreateAdd(N, ConstantInt::get(N->getType(), CI.logBase2())); 796 if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1)) 797 N = IC.Builder->CreateZExt(N, Z->getDestTy()); 798 BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N); 799 if (I.isExact()) LShr->setIsExact(); 800 return LShr; 801 } 802 803 // \brief Recursively visits the possible right hand operands of a udiv 804 // instruction, seeing through select instructions, to determine if we can 805 // replace the udiv with something simpler. If we find that an operand is not 806 // able to simplify the udiv, we abort the entire transformation. 807 static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I, 808 SmallVectorImpl<UDivFoldAction> &Actions, 809 unsigned Depth = 0) { 810 // Check to see if this is an unsigned division with an exact power of 2, 811 // if so, convert to a right shift. 812 if (match(Op1, m_Power2())) { 813 Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1)); 814 return Actions.size(); 815 } 816 817 if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) 818 // X udiv C, where C >= signbit 819 if (C->getValue().isNegative()) { 820 Actions.push_back(UDivFoldAction(foldUDivNegCst, C)); 821 return Actions.size(); 822 } 823 824 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 825 if (match(Op1, m_Shl(m_Power2(), m_Value())) || 826 match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) { 827 Actions.push_back(UDivFoldAction(foldUDivShl, Op1)); 828 return Actions.size(); 829 } 830 831 // The remaining tests are all recursive, so bail out if we hit the limit. 832 if (Depth++ == MaxDepth) 833 return 0; 834 835 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 836 if (size_t LHSIdx = visitUDivOperand(Op0, SI->getOperand(1), I, Actions)) 837 if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions)) { 838 Actions.push_back(UDivFoldAction((FoldUDivOperandCb)0, Op1, LHSIdx-1)); 839 return Actions.size(); 840 } 841 842 return 0; 843 } 844 845 Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { 846 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 847 848 if (Value *V = SimplifyUDivInst(Op0, Op1, TD)) 849 return ReplaceInstUsesWith(I, V); 850 851 // Handle the integer div common cases 852 if (Instruction *Common = commonIDivTransforms(I)) 853 return Common; 854 855 // (x lshr C1) udiv C2 --> x udiv (C2 << C1) 856 if (ConstantInt *C2 = dyn_cast<ConstantInt>(Op1)) { 857 Value *X; 858 ConstantInt *C1; 859 if (match(Op0, m_LShr(m_Value(X), m_ConstantInt(C1)))) { 860 APInt NC = C2->getValue().shl(C1->getLimitedValue(C1->getBitWidth()-1)); 861 return BinaryOperator::CreateUDiv(X, Builder->getInt(NC)); 862 } 863 } 864 865 // (zext A) udiv (zext B) --> zext (A udiv B) 866 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 867 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 868 return new ZExtInst(Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", 869 I.isExact()), 870 I.getType()); 871 872 // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...)))) 873 SmallVector<UDivFoldAction, 6> UDivActions; 874 if (visitUDivOperand(Op0, Op1, I, UDivActions)) 875 for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) { 876 FoldUDivOperandCb Action = UDivActions[i].FoldAction; 877 Value *ActionOp1 = UDivActions[i].OperandToFold; 878 Instruction *Inst; 879 if (Action) 880 Inst = Action(Op0, ActionOp1, I, *this); 881 else { 882 // This action joins two actions together. The RHS of this action is 883 // simply the last action we processed, we saved the LHS action index in 884 // the joining action. 885 size_t SelectRHSIdx = i - 1; 886 Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult; 887 size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx; 888 Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult; 889 Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(), 890 SelectLHS, SelectRHS); 891 } 892 893 // If this is the last action to process, return it to the InstCombiner. 894 // Otherwise, we insert it before the UDiv and record it so that we may 895 // use it as part of a joining action (i.e., a SelectInst). 896 if (e - i != 1) { 897 Inst->insertBefore(&I); 898 UDivActions[i].FoldResult = Inst; 899 } else 900 return Inst; 901 } 902 903 return 0; 904 } 905 906 Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { 907 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 908 909 if (Value *V = SimplifySDivInst(Op0, Op1, TD)) 910 return ReplaceInstUsesWith(I, V); 911 912 // Handle the integer div common cases 913 if (Instruction *Common = commonIDivTransforms(I)) 914 return Common; 915 916 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 917 // sdiv X, -1 == -X 918 if (RHS->isAllOnesValue()) 919 return BinaryOperator::CreateNeg(Op0); 920 921 // sdiv X, C --> ashr exact X, log2(C) 922 if (I.isExact() && RHS->getValue().isNonNegative() && 923 RHS->getValue().isPowerOf2()) { 924 Value *ShAmt = llvm::ConstantInt::get(RHS->getType(), 925 RHS->getValue().exactLogBase2()); 926 return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName()); 927 } 928 929 // -X/C --> X/-C provided the negation doesn't overflow. 930 if (SubOperator *Sub = dyn_cast<SubOperator>(Op0)) 931 if (match(Sub->getOperand(0), m_Zero()) && Sub->hasNoSignedWrap()) 932 return BinaryOperator::CreateSDiv(Sub->getOperand(1), 933 ConstantExpr::getNeg(RHS)); 934 } 935 936 // If the sign bits of both operands are zero (i.e. we can prove they are 937 // unsigned inputs), turn this into a udiv. 938 if (I.getType()->isIntegerTy()) { 939 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 940 if (MaskedValueIsZero(Op0, Mask)) { 941 if (MaskedValueIsZero(Op1, Mask)) { 942 // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set 943 return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 944 } 945 946 if (match(Op1, m_Shl(m_Power2(), m_Value()))) { 947 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) 948 // Safe because the only negative value (1 << Y) can take on is 949 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have 950 // the sign bit set. 951 return BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 952 } 953 } 954 } 955 956 return 0; 957 } 958 959 /// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special 960 /// FP value and: 961 /// 1) 1/C is exact, or 962 /// 2) reciprocal is allowed. 963 /// If the conversion was successful, the simplified expression "X * 1/C" is 964 /// returned; otherwise, NULL is returned. 965 /// 966 static Instruction *CvtFDivConstToReciprocal(Value *Dividend, 967 ConstantFP *Divisor, 968 bool AllowReciprocal) { 969 const APFloat &FpVal = Divisor->getValueAPF(); 970 APFloat Reciprocal(FpVal.getSemantics()); 971 bool Cvt = FpVal.getExactInverse(&Reciprocal); 972 973 if (!Cvt && AllowReciprocal && FpVal.isFiniteNonZero()) { 974 Reciprocal = APFloat(FpVal.getSemantics(), 1.0f); 975 (void)Reciprocal.divide(FpVal, APFloat::rmNearestTiesToEven); 976 Cvt = !Reciprocal.isDenormal(); 977 } 978 979 if (!Cvt) 980 return 0; 981 982 ConstantFP *R; 983 R = ConstantFP::get(Dividend->getType()->getContext(), Reciprocal); 984 return BinaryOperator::CreateFMul(Dividend, R); 985 } 986 987 Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { 988 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 989 990 if (Value *V = SimplifyFDivInst(Op0, Op1, TD)) 991 return ReplaceInstUsesWith(I, V); 992 993 if (isa<Constant>(Op0)) 994 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 995 if (Instruction *R = FoldOpIntoSelect(I, SI)) 996 return R; 997 998 bool AllowReassociate = I.hasUnsafeAlgebra(); 999 bool AllowReciprocal = I.hasAllowReciprocal(); 1000 1001 if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) { 1002 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 1003 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1004 return R; 1005 1006 if (AllowReassociate) { 1007 ConstantFP *C1 = 0; 1008 ConstantFP *C2 = Op1C; 1009 Value *X; 1010 Instruction *Res = 0; 1011 1012 if (match(Op0, m_FMul(m_Value(X), m_ConstantFP(C1)))) { 1013 // (X*C1)/C2 => X * (C1/C2) 1014 // 1015 Constant *C = ConstantExpr::getFDiv(C1, C2); 1016 const APFloat &F = cast<ConstantFP>(C)->getValueAPF(); 1017 if (F.isNormal()) 1018 Res = BinaryOperator::CreateFMul(X, C); 1019 } else if (match(Op0, m_FDiv(m_Value(X), m_ConstantFP(C1)))) { 1020 // (X/C1)/C2 => X /(C2*C1) [=> X * 1/(C2*C1) if reciprocal is allowed] 1021 // 1022 Constant *C = ConstantExpr::getFMul(C1, C2); 1023 const APFloat &F = cast<ConstantFP>(C)->getValueAPF(); 1024 if (F.isNormal()) { 1025 Res = CvtFDivConstToReciprocal(X, cast<ConstantFP>(C), 1026 AllowReciprocal); 1027 if (!Res) 1028 Res = BinaryOperator::CreateFDiv(X, C); 1029 } 1030 } 1031 1032 if (Res) { 1033 Res->setFastMathFlags(I.getFastMathFlags()); 1034 return Res; 1035 } 1036 } 1037 1038 // X / C => X * 1/C 1039 if (Instruction *T = CvtFDivConstToReciprocal(Op0, Op1C, AllowReciprocal)) 1040 return T; 1041 1042 return 0; 1043 } 1044 1045 if (AllowReassociate && isa<ConstantFP>(Op0)) { 1046 ConstantFP *C1 = cast<ConstantFP>(Op0), *C2; 1047 Constant *Fold = 0; 1048 Value *X; 1049 bool CreateDiv = true; 1050 1051 // C1 / (X*C2) => (C1/C2) / X 1052 if (match(Op1, m_FMul(m_Value(X), m_ConstantFP(C2)))) 1053 Fold = ConstantExpr::getFDiv(C1, C2); 1054 else if (match(Op1, m_FDiv(m_Value(X), m_ConstantFP(C2)))) { 1055 // C1 / (X/C2) => (C1*C2) / X 1056 Fold = ConstantExpr::getFMul(C1, C2); 1057 } else if (match(Op1, m_FDiv(m_ConstantFP(C2), m_Value(X)))) { 1058 // C1 / (C2/X) => (C1/C2) * X 1059 Fold = ConstantExpr::getFDiv(C1, C2); 1060 CreateDiv = false; 1061 } 1062 1063 if (Fold) { 1064 const APFloat &FoldC = cast<ConstantFP>(Fold)->getValueAPF(); 1065 if (FoldC.isNormal()) { 1066 Instruction *R = CreateDiv ? 1067 BinaryOperator::CreateFDiv(Fold, X) : 1068 BinaryOperator::CreateFMul(X, Fold); 1069 R->setFastMathFlags(I.getFastMathFlags()); 1070 return R; 1071 } 1072 } 1073 return 0; 1074 } 1075 1076 if (AllowReassociate) { 1077 Value *X, *Y; 1078 Value *NewInst = 0; 1079 Instruction *SimpR = 0; 1080 1081 if (Op0->hasOneUse() && match(Op0, m_FDiv(m_Value(X), m_Value(Y)))) { 1082 // (X/Y) / Z => X / (Y*Z) 1083 // 1084 if (!isa<ConstantFP>(Y) || !isa<ConstantFP>(Op1)) { 1085 NewInst = Builder->CreateFMul(Y, Op1); 1086 SimpR = BinaryOperator::CreateFDiv(X, NewInst); 1087 } 1088 } else if (Op1->hasOneUse() && match(Op1, m_FDiv(m_Value(X), m_Value(Y)))) { 1089 // Z / (X/Y) => Z*Y / X 1090 // 1091 if (!isa<ConstantFP>(Y) || !isa<ConstantFP>(Op0)) { 1092 NewInst = Builder->CreateFMul(Op0, Y); 1093 SimpR = BinaryOperator::CreateFDiv(NewInst, X); 1094 } 1095 } 1096 1097 if (NewInst) { 1098 if (Instruction *T = dyn_cast<Instruction>(NewInst)) 1099 T->setDebugLoc(I.getDebugLoc()); 1100 SimpR->setFastMathFlags(I.getFastMathFlags()); 1101 return SimpR; 1102 } 1103 } 1104 1105 return 0; 1106 } 1107 1108 /// This function implements the transforms common to both integer remainder 1109 /// instructions (urem and srem). It is called by the visitors to those integer 1110 /// remainder instructions. 1111 /// @brief Common integer remainder transforms 1112 Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) { 1113 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1114 1115 // The RHS is known non-zero. 1116 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) { 1117 I.setOperand(1, V); 1118 return &I; 1119 } 1120 1121 // Handle cases involving: rem X, (select Cond, Y, Z) 1122 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 1123 return &I; 1124 1125 if (isa<ConstantInt>(Op1)) { 1126 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { 1127 if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { 1128 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1129 return R; 1130 } else if (isa<PHINode>(Op0I)) { 1131 if (Instruction *NV = FoldOpIntoPhi(I)) 1132 return NV; 1133 } 1134 1135 // See if we can fold away this rem instruction. 1136 if (SimplifyDemandedInstructionBits(I)) 1137 return &I; 1138 } 1139 } 1140 1141 return 0; 1142 } 1143 1144 Instruction *InstCombiner::visitURem(BinaryOperator &I) { 1145 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1146 1147 if (Value *V = SimplifyURemInst(Op0, Op1, TD)) 1148 return ReplaceInstUsesWith(I, V); 1149 1150 if (Instruction *common = commonIRemTransforms(I)) 1151 return common; 1152 1153 // (zext A) urem (zext B) --> zext (A urem B) 1154 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 1155 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 1156 return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), 1157 I.getType()); 1158 1159 // X urem Y -> X and Y-1, where Y is a power of 2, 1160 if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/true)) { 1161 Constant *N1 = Constant::getAllOnesValue(I.getType()); 1162 Value *Add = Builder->CreateAdd(Op1, N1); 1163 return BinaryOperator::CreateAnd(Op0, Add); 1164 } 1165 1166 // 1 urem X -> zext(X != 1) 1167 if (match(Op0, m_One())) { 1168 Value *Cmp = Builder->CreateICmpNE(Op1, Op0); 1169 Value *Ext = Builder->CreateZExt(Cmp, I.getType()); 1170 return ReplaceInstUsesWith(I, Ext); 1171 } 1172 1173 return 0; 1174 } 1175 1176 Instruction *InstCombiner::visitSRem(BinaryOperator &I) { 1177 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1178 1179 if (Value *V = SimplifySRemInst(Op0, Op1, TD)) 1180 return ReplaceInstUsesWith(I, V); 1181 1182 // Handle the integer rem common cases 1183 if (Instruction *Common = commonIRemTransforms(I)) 1184 return Common; 1185 1186 if (Value *RHSNeg = dyn_castNegVal(Op1)) 1187 if (!isa<Constant>(RHSNeg) || 1188 (isa<ConstantInt>(RHSNeg) && 1189 cast<ConstantInt>(RHSNeg)->getValue().isStrictlyPositive())) { 1190 // X % -Y -> X % Y 1191 Worklist.AddValue(I.getOperand(1)); 1192 I.setOperand(1, RHSNeg); 1193 return &I; 1194 } 1195 1196 // If the sign bits of both operands are zero (i.e. we can prove they are 1197 // unsigned inputs), turn this into a urem. 1198 if (I.getType()->isIntegerTy()) { 1199 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 1200 if (MaskedValueIsZero(Op1, Mask) && MaskedValueIsZero(Op0, Mask)) { 1201 // X srem Y -> X urem Y, iff X and Y don't have sign bit set 1202 return BinaryOperator::CreateURem(Op0, Op1, I.getName()); 1203 } 1204 } 1205 1206 // If it's a constant vector, flip any negative values positive. 1207 if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) { 1208 Constant *C = cast<Constant>(Op1); 1209 unsigned VWidth = C->getType()->getVectorNumElements(); 1210 1211 bool hasNegative = false; 1212 bool hasMissing = false; 1213 for (unsigned i = 0; i != VWidth; ++i) { 1214 Constant *Elt = C->getAggregateElement(i); 1215 if (Elt == 0) { 1216 hasMissing = true; 1217 break; 1218 } 1219 1220 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt)) 1221 if (RHS->isNegative()) 1222 hasNegative = true; 1223 } 1224 1225 if (hasNegative && !hasMissing) { 1226 SmallVector<Constant *, 16> Elts(VWidth); 1227 for (unsigned i = 0; i != VWidth; ++i) { 1228 Elts[i] = C->getAggregateElement(i); // Handle undef, etc. 1229 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) { 1230 if (RHS->isNegative()) 1231 Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); 1232 } 1233 } 1234 1235 Constant *NewRHSV = ConstantVector::get(Elts); 1236 if (NewRHSV != C) { // Don't loop on -MININT 1237 Worklist.AddValue(I.getOperand(1)); 1238 I.setOperand(1, NewRHSV); 1239 return &I; 1240 } 1241 } 1242 } 1243 1244 return 0; 1245 } 1246 1247 Instruction *InstCombiner::visitFRem(BinaryOperator &I) { 1248 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1249 1250 if (Value *V = SimplifyFRemInst(Op0, Op1, TD)) 1251 return ReplaceInstUsesWith(I, V); 1252 1253 // Handle cases involving: rem X, (select Cond, Y, Z) 1254 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 1255 return &I; 1256 1257 return 0; 1258 } 1259