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