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