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 "InstCombineInternal.h" 16 #include "llvm/Analysis/InstructionSimplify.h" 17 #include "llvm/IR/IntrinsicInst.h" 18 #include "llvm/IR/PatternMatch.h" 19 using namespace llvm; 20 using namespace PatternMatch; 21 22 #define DEBUG_TYPE "instcombine" 23 24 25 /// The specific integer value is used in a context where it is known to be 26 /// non-zero. If this allows us to simplify the computation, do so and return 27 /// the new operand, otherwise return null. 28 static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC, 29 Instruction &CxtI) { 30 // If V has multiple uses, then we would have to do more analysis to determine 31 // if this is safe. For example, the use could be in dynamically unreached 32 // code. 33 if (!V->hasOneUse()) return nullptr; 34 35 bool MadeChange = false; 36 37 // ((1 << A) >>u B) --> (1 << (A-B)) 38 // Because V cannot be zero, we know that B is less than A. 39 Value *A = nullptr, *B = nullptr, *One = nullptr; 40 if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) && 41 match(One, m_One())) { 42 A = IC.Builder->CreateSub(A, B); 43 return IC.Builder->CreateShl(One, A); 44 } 45 46 // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it 47 // inexact. Similarly for <<. 48 if (BinaryOperator *I = dyn_cast<BinaryOperator>(V)) 49 if (I->isLogicalShift() && 50 isKnownToBeAPowerOfTwo(I->getOperand(0), IC.getDataLayout(), false, 0, 51 IC.getAssumptionCache(), &CxtI, 52 IC.getDominatorTree())) { 53 // We know that this is an exact/nuw shift and that the input is a 54 // non-zero context as well. 55 if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) { 56 I->setOperand(0, V2); 57 MadeChange = true; 58 } 59 60 if (I->getOpcode() == Instruction::LShr && !I->isExact()) { 61 I->setIsExact(); 62 MadeChange = true; 63 } 64 65 if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) { 66 I->setHasNoUnsignedWrap(); 67 MadeChange = true; 68 } 69 } 70 71 // TODO: Lots more we could do here: 72 // If V is a phi node, we can call this on each of its operands. 73 // "select cond, X, 0" can simplify to "X". 74 75 return MadeChange ? V : nullptr; 76 } 77 78 79 /// True if the multiply can not be expressed in an int this size. 80 static bool MultiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product, 81 bool IsSigned) { 82 bool Overflow; 83 if (IsSigned) 84 Product = C1.smul_ov(C2, Overflow); 85 else 86 Product = C1.umul_ov(C2, Overflow); 87 88 return Overflow; 89 } 90 91 /// \brief True if C2 is a multiple of C1. Quotient contains C2/C1. 92 static bool IsMultiple(const APInt &C1, const APInt &C2, APInt &Quotient, 93 bool IsSigned) { 94 assert(C1.getBitWidth() == C2.getBitWidth() && 95 "Inconsistent width of constants!"); 96 97 // Bail if we will divide by zero. 98 if (C2.isMinValue()) 99 return false; 100 101 // Bail if we would divide INT_MIN by -1. 102 if (IsSigned && C1.isMinSignedValue() && C2.isAllOnesValue()) 103 return false; 104 105 APInt Remainder(C1.getBitWidth(), /*Val=*/0ULL, IsSigned); 106 if (IsSigned) 107 APInt::sdivrem(C1, C2, Quotient, Remainder); 108 else 109 APInt::udivrem(C1, C2, Quotient, Remainder); 110 111 return Remainder.isMinValue(); 112 } 113 114 /// \brief A helper routine of InstCombiner::visitMul(). 115 /// 116 /// If C is a vector of known powers of 2, then this function returns 117 /// a new vector obtained from C replacing each element with its logBase2. 118 /// Return a null pointer otherwise. 119 static Constant *getLogBase2Vector(ConstantDataVector *CV) { 120 const APInt *IVal; 121 SmallVector<Constant *, 4> Elts; 122 123 for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) { 124 Constant *Elt = CV->getElementAsConstant(I); 125 if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2()) 126 return nullptr; 127 Elts.push_back(ConstantInt::get(Elt->getType(), IVal->logBase2())); 128 } 129 130 return ConstantVector::get(Elts); 131 } 132 133 /// \brief Return true if we can prove that: 134 /// (mul LHS, RHS) === (mul nsw LHS, RHS) 135 bool InstCombiner::WillNotOverflowSignedMul(Value *LHS, Value *RHS, 136 Instruction &CxtI) { 137 // Multiplying n * m significant bits yields a result of n + m significant 138 // bits. If the total number of significant bits does not exceed the 139 // result bit width (minus 1), there is no overflow. 140 // This means if we have enough leading sign bits in the operands 141 // we can guarantee that the result does not overflow. 142 // Ref: "Hacker's Delight" by Henry Warren 143 unsigned BitWidth = LHS->getType()->getScalarSizeInBits(); 144 145 // Note that underestimating the number of sign bits gives a more 146 // conservative answer. 147 unsigned SignBits = 148 ComputeNumSignBits(LHS, 0, &CxtI) + ComputeNumSignBits(RHS, 0, &CxtI); 149 150 // First handle the easy case: if we have enough sign bits there's 151 // definitely no overflow. 152 if (SignBits > BitWidth + 1) 153 return true; 154 155 // There are two ambiguous cases where there can be no overflow: 156 // SignBits == BitWidth + 1 and 157 // SignBits == BitWidth 158 // The second case is difficult to check, therefore we only handle the 159 // first case. 160 if (SignBits == BitWidth + 1) { 161 // It overflows only when both arguments are negative and the true 162 // product is exactly the minimum negative number. 163 // E.g. mul i16 with 17 sign bits: 0xff00 * 0xff80 = 0x8000 164 // For simplicity we just check if at least one side is not negative. 165 bool LHSNonNegative, LHSNegative; 166 bool RHSNonNegative, RHSNegative; 167 ComputeSignBit(LHS, LHSNonNegative, LHSNegative, /*Depth=*/0, &CxtI); 168 ComputeSignBit(RHS, RHSNonNegative, RHSNegative, /*Depth=*/0, &CxtI); 169 if (LHSNonNegative || RHSNonNegative) 170 return true; 171 } 172 return false; 173 } 174 175 Instruction *InstCombiner::visitMul(BinaryOperator &I) { 176 bool Changed = SimplifyAssociativeOrCommutative(I); 177 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 178 179 if (Value *V = SimplifyVectorOp(I)) 180 return ReplaceInstUsesWith(I, V); 181 182 if (Value *V = SimplifyMulInst(Op0, Op1, DL, TLI, DT, AC)) 183 return ReplaceInstUsesWith(I, V); 184 185 if (Value *V = SimplifyUsingDistributiveLaws(I)) 186 return ReplaceInstUsesWith(I, V); 187 188 // X * -1 == 0 - X 189 if (match(Op1, m_AllOnes())) { 190 BinaryOperator *BO = BinaryOperator::CreateNeg(Op0, I.getName()); 191 if (I.hasNoSignedWrap()) 192 BO->setHasNoSignedWrap(); 193 return BO; 194 } 195 196 // Also allow combining multiply instructions on vectors. 197 { 198 Value *NewOp; 199 Constant *C1, *C2; 200 const APInt *IVal; 201 if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)), 202 m_Constant(C1))) && 203 match(C1, m_APInt(IVal))) { 204 // ((X << C2)*C1) == (X * (C1 << C2)) 205 Constant *Shl = ConstantExpr::getShl(C1, C2); 206 BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0)); 207 BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl); 208 if (I.hasNoUnsignedWrap() && Mul->hasNoUnsignedWrap()) 209 BO->setHasNoUnsignedWrap(); 210 if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap() && 211 Shl->isNotMinSignedValue()) 212 BO->setHasNoSignedWrap(); 213 return BO; 214 } 215 216 if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) { 217 Constant *NewCst = nullptr; 218 if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2()) 219 // Replace X*(2^C) with X << C, where C is either a scalar or a splat. 220 NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2()); 221 else if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(C1)) 222 // Replace X*(2^C) with X << C, where C is a vector of known 223 // constant powers of 2. 224 NewCst = getLogBase2Vector(CV); 225 226 if (NewCst) { 227 unsigned Width = NewCst->getType()->getPrimitiveSizeInBits(); 228 BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst); 229 230 if (I.hasNoUnsignedWrap()) 231 Shl->setHasNoUnsignedWrap(); 232 if (I.hasNoSignedWrap()) { 233 uint64_t V; 234 if (match(NewCst, m_ConstantInt(V)) && V != Width - 1) 235 Shl->setHasNoSignedWrap(); 236 } 237 238 return Shl; 239 } 240 } 241 } 242 243 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) { 244 // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n 245 // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n 246 // The "* (2**n)" thus becomes a potential shifting opportunity. 247 { 248 const APInt & Val = CI->getValue(); 249 const APInt &PosVal = Val.abs(); 250 if (Val.isNegative() && PosVal.isPowerOf2()) { 251 Value *X = nullptr, *Y = nullptr; 252 if (Op0->hasOneUse()) { 253 ConstantInt *C1; 254 Value *Sub = nullptr; 255 if (match(Op0, m_Sub(m_Value(Y), m_Value(X)))) 256 Sub = Builder->CreateSub(X, Y, "suba"); 257 else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1)))) 258 Sub = Builder->CreateSub(Builder->CreateNeg(C1), Y, "subc"); 259 if (Sub) 260 return 261 BinaryOperator::CreateMul(Sub, 262 ConstantInt::get(Y->getType(), PosVal)); 263 } 264 } 265 } 266 } 267 268 // Simplify mul instructions with a constant RHS. 269 if (isa<Constant>(Op1)) { 270 // Try to fold constant mul into select arguments. 271 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 272 if (Instruction *R = FoldOpIntoSelect(I, SI)) 273 return R; 274 275 if (isa<PHINode>(Op0)) 276 if (Instruction *NV = FoldOpIntoPhi(I)) 277 return NV; 278 279 // Canonicalize (X+C1)*CI -> X*CI+C1*CI. 280 { 281 Value *X; 282 Constant *C1; 283 if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) { 284 Value *Mul = Builder->CreateMul(C1, Op1); 285 // Only go forward with the transform if C1*CI simplifies to a tidier 286 // constant. 287 if (!match(Mul, m_Mul(m_Value(), m_Value()))) 288 return BinaryOperator::CreateAdd(Builder->CreateMul(X, Op1), Mul); 289 } 290 } 291 } 292 293 if (Value *Op0v = dyn_castNegVal(Op0)) { // -X * -Y = X*Y 294 if (Value *Op1v = dyn_castNegVal(Op1)) { 295 BinaryOperator *BO = BinaryOperator::CreateMul(Op0v, Op1v); 296 if (I.hasNoSignedWrap() && 297 match(Op0, m_NSWSub(m_Value(), m_Value())) && 298 match(Op1, m_NSWSub(m_Value(), m_Value()))) 299 BO->setHasNoSignedWrap(); 300 return BO; 301 } 302 } 303 304 // (X / Y) * Y = X - (X % Y) 305 // (X / Y) * -Y = (X % Y) - X 306 { 307 Value *Op1C = Op1; 308 BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0); 309 if (!BO || 310 (BO->getOpcode() != Instruction::UDiv && 311 BO->getOpcode() != Instruction::SDiv)) { 312 Op1C = Op0; 313 BO = dyn_cast<BinaryOperator>(Op1); 314 } 315 Value *Neg = dyn_castNegVal(Op1C); 316 if (BO && BO->hasOneUse() && 317 (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) && 318 (BO->getOpcode() == Instruction::UDiv || 319 BO->getOpcode() == Instruction::SDiv)) { 320 Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1); 321 322 // If the division is exact, X % Y is zero, so we end up with X or -X. 323 if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO)) 324 if (SDiv->isExact()) { 325 if (Op1BO == Op1C) 326 return ReplaceInstUsesWith(I, Op0BO); 327 return BinaryOperator::CreateNeg(Op0BO); 328 } 329 330 Value *Rem; 331 if (BO->getOpcode() == Instruction::UDiv) 332 Rem = Builder->CreateURem(Op0BO, Op1BO); 333 else 334 Rem = Builder->CreateSRem(Op0BO, Op1BO); 335 Rem->takeName(BO); 336 337 if (Op1BO == Op1C) 338 return BinaryOperator::CreateSub(Op0BO, Rem); 339 return BinaryOperator::CreateSub(Rem, Op0BO); 340 } 341 } 342 343 /// i1 mul -> i1 and. 344 if (I.getType()->getScalarType()->isIntegerTy(1)) 345 return BinaryOperator::CreateAnd(Op0, Op1); 346 347 // X*(1 << Y) --> X << Y 348 // (1 << Y)*X --> X << Y 349 { 350 Value *Y; 351 BinaryOperator *BO = nullptr; 352 bool ShlNSW = false; 353 if (match(Op0, m_Shl(m_One(), m_Value(Y)))) { 354 BO = BinaryOperator::CreateShl(Op1, Y); 355 ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap(); 356 } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) { 357 BO = BinaryOperator::CreateShl(Op0, Y); 358 ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap(); 359 } 360 if (BO) { 361 if (I.hasNoUnsignedWrap()) 362 BO->setHasNoUnsignedWrap(); 363 if (I.hasNoSignedWrap() && ShlNSW) 364 BO->setHasNoSignedWrap(); 365 return BO; 366 } 367 } 368 369 // If one of the operands of the multiply is a cast from a boolean value, then 370 // we know the bool is either zero or one, so this is a 'masking' multiply. 371 // X * Y (where Y is 0 or 1) -> X & (0-Y) 372 if (!I.getType()->isVectorTy()) { 373 // -2 is "-1 << 1" so it is all bits set except the low one. 374 APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true); 375 376 Value *BoolCast = nullptr, *OtherOp = nullptr; 377 if (MaskedValueIsZero(Op0, Negative2, 0, &I)) 378 BoolCast = Op0, OtherOp = Op1; 379 else if (MaskedValueIsZero(Op1, Negative2, 0, &I)) 380 BoolCast = Op1, OtherOp = Op0; 381 382 if (BoolCast) { 383 Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()), 384 BoolCast); 385 return BinaryOperator::CreateAnd(V, OtherOp); 386 } 387 } 388 389 if (!I.hasNoSignedWrap() && WillNotOverflowSignedMul(Op0, Op1, I)) { 390 Changed = true; 391 I.setHasNoSignedWrap(true); 392 } 393 394 if (!I.hasNoUnsignedWrap() && 395 computeOverflowForUnsignedMul(Op0, Op1, &I) == 396 OverflowResult::NeverOverflows) { 397 Changed = true; 398 I.setHasNoUnsignedWrap(true); 399 } 400 401 return Changed ? &I : nullptr; 402 } 403 404 /// Detect pattern log2(Y * 0.5) with corresponding fast math flags. 405 static void detectLog2OfHalf(Value *&Op, Value *&Y, IntrinsicInst *&Log2) { 406 if (!Op->hasOneUse()) 407 return; 408 409 IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op); 410 if (!II) 411 return; 412 if (II->getIntrinsicID() != Intrinsic::log2 || !II->hasUnsafeAlgebra()) 413 return; 414 Log2 = II; 415 416 Value *OpLog2Of = II->getArgOperand(0); 417 if (!OpLog2Of->hasOneUse()) 418 return; 419 420 Instruction *I = dyn_cast<Instruction>(OpLog2Of); 421 if (!I) 422 return; 423 if (I->getOpcode() != Instruction::FMul || !I->hasUnsafeAlgebra()) 424 return; 425 426 if (match(I->getOperand(0), m_SpecificFP(0.5))) 427 Y = I->getOperand(1); 428 else if (match(I->getOperand(1), m_SpecificFP(0.5))) 429 Y = I->getOperand(0); 430 } 431 432 static bool isFiniteNonZeroFp(Constant *C) { 433 if (C->getType()->isVectorTy()) { 434 for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; 435 ++I) { 436 ConstantFP *CFP = dyn_cast_or_null<ConstantFP>(C->getAggregateElement(I)); 437 if (!CFP || !CFP->getValueAPF().isFiniteNonZero()) 438 return false; 439 } 440 return true; 441 } 442 443 return isa<ConstantFP>(C) && 444 cast<ConstantFP>(C)->getValueAPF().isFiniteNonZero(); 445 } 446 447 static bool isNormalFp(Constant *C) { 448 if (C->getType()->isVectorTy()) { 449 for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E; 450 ++I) { 451 ConstantFP *CFP = dyn_cast_or_null<ConstantFP>(C->getAggregateElement(I)); 452 if (!CFP || !CFP->getValueAPF().isNormal()) 453 return false; 454 } 455 return true; 456 } 457 458 return isa<ConstantFP>(C) && cast<ConstantFP>(C)->getValueAPF().isNormal(); 459 } 460 461 /// Helper function of InstCombiner::visitFMul(BinaryOperator(). It returns 462 /// true iff the given value is FMul or FDiv with one and only one operand 463 /// being a normal constant (i.e. not Zero/NaN/Infinity). 464 static bool isFMulOrFDivWithConstant(Value *V) { 465 Instruction *I = dyn_cast<Instruction>(V); 466 if (!I || (I->getOpcode() != Instruction::FMul && 467 I->getOpcode() != Instruction::FDiv)) 468 return false; 469 470 Constant *C0 = dyn_cast<Constant>(I->getOperand(0)); 471 Constant *C1 = dyn_cast<Constant>(I->getOperand(1)); 472 473 if (C0 && C1) 474 return false; 475 476 return (C0 && isFiniteNonZeroFp(C0)) || (C1 && isFiniteNonZeroFp(C1)); 477 } 478 479 /// foldFMulConst() is a helper routine of InstCombiner::visitFMul(). 480 /// The input \p FMulOrDiv is a FMul/FDiv with one and only one operand 481 /// being a constant (i.e. isFMulOrFDivWithConstant(FMulOrDiv) == true). 482 /// This function is to simplify "FMulOrDiv * C" and returns the 483 /// resulting expression. Note that this function could return NULL in 484 /// case the constants cannot be folded into a normal floating-point. 485 /// 486 Value *InstCombiner::foldFMulConst(Instruction *FMulOrDiv, Constant *C, 487 Instruction *InsertBefore) { 488 assert(isFMulOrFDivWithConstant(FMulOrDiv) && "V is invalid"); 489 490 Value *Opnd0 = FMulOrDiv->getOperand(0); 491 Value *Opnd1 = FMulOrDiv->getOperand(1); 492 493 Constant *C0 = dyn_cast<Constant>(Opnd0); 494 Constant *C1 = dyn_cast<Constant>(Opnd1); 495 496 BinaryOperator *R = nullptr; 497 498 // (X * C0) * C => X * (C0*C) 499 if (FMulOrDiv->getOpcode() == Instruction::FMul) { 500 Constant *F = ConstantExpr::getFMul(C1 ? C1 : C0, C); 501 if (isNormalFp(F)) 502 R = BinaryOperator::CreateFMul(C1 ? Opnd0 : Opnd1, F); 503 } else { 504 if (C0) { 505 // (C0 / X) * C => (C0 * C) / X 506 if (FMulOrDiv->hasOneUse()) { 507 // It would otherwise introduce another div. 508 Constant *F = ConstantExpr::getFMul(C0, C); 509 if (isNormalFp(F)) 510 R = BinaryOperator::CreateFDiv(F, Opnd1); 511 } 512 } else { 513 // (X / C1) * C => X * (C/C1) if C/C1 is not a denormal 514 Constant *F = ConstantExpr::getFDiv(C, C1); 515 if (isNormalFp(F)) { 516 R = BinaryOperator::CreateFMul(Opnd0, F); 517 } else { 518 // (X / C1) * C => X / (C1/C) 519 Constant *F = ConstantExpr::getFDiv(C1, C); 520 if (isNormalFp(F)) 521 R = BinaryOperator::CreateFDiv(Opnd0, F); 522 } 523 } 524 } 525 526 if (R) { 527 R->setHasUnsafeAlgebra(true); 528 InsertNewInstWith(R, *InsertBefore); 529 } 530 531 return R; 532 } 533 534 Instruction *InstCombiner::visitFMul(BinaryOperator &I) { 535 bool Changed = SimplifyAssociativeOrCommutative(I); 536 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 537 538 if (Value *V = SimplifyVectorOp(I)) 539 return ReplaceInstUsesWith(I, V); 540 541 if (isa<Constant>(Op0)) 542 std::swap(Op0, Op1); 543 544 if (Value *V = 545 SimplifyFMulInst(Op0, Op1, I.getFastMathFlags(), DL, TLI, DT, AC)) 546 return ReplaceInstUsesWith(I, V); 547 548 bool AllowReassociate = I.hasUnsafeAlgebra(); 549 550 // Simplify mul instructions with a constant RHS. 551 if (isa<Constant>(Op1)) { 552 // Try to fold constant mul into select arguments. 553 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 554 if (Instruction *R = FoldOpIntoSelect(I, SI)) 555 return R; 556 557 if (isa<PHINode>(Op0)) 558 if (Instruction *NV = FoldOpIntoPhi(I)) 559 return NV; 560 561 // (fmul X, -1.0) --> (fsub -0.0, X) 562 if (match(Op1, m_SpecificFP(-1.0))) { 563 Constant *NegZero = ConstantFP::getNegativeZero(Op1->getType()); 564 Instruction *RI = BinaryOperator::CreateFSub(NegZero, Op0); 565 RI->copyFastMathFlags(&I); 566 return RI; 567 } 568 569 Constant *C = cast<Constant>(Op1); 570 if (AllowReassociate && isFiniteNonZeroFp(C)) { 571 // Let MDC denote an expression in one of these forms: 572 // X * C, C/X, X/C, where C is a constant. 573 // 574 // Try to simplify "MDC * Constant" 575 if (isFMulOrFDivWithConstant(Op0)) 576 if (Value *V = foldFMulConst(cast<Instruction>(Op0), C, &I)) 577 return ReplaceInstUsesWith(I, V); 578 579 // (MDC +/- C1) * C => (MDC * C) +/- (C1 * C) 580 Instruction *FAddSub = dyn_cast<Instruction>(Op0); 581 if (FAddSub && 582 (FAddSub->getOpcode() == Instruction::FAdd || 583 FAddSub->getOpcode() == Instruction::FSub)) { 584 Value *Opnd0 = FAddSub->getOperand(0); 585 Value *Opnd1 = FAddSub->getOperand(1); 586 Constant *C0 = dyn_cast<Constant>(Opnd0); 587 Constant *C1 = dyn_cast<Constant>(Opnd1); 588 bool Swap = false; 589 if (C0) { 590 std::swap(C0, C1); 591 std::swap(Opnd0, Opnd1); 592 Swap = true; 593 } 594 595 if (C1 && isFiniteNonZeroFp(C1) && isFMulOrFDivWithConstant(Opnd0)) { 596 Value *M1 = ConstantExpr::getFMul(C1, C); 597 Value *M0 = isNormalFp(cast<Constant>(M1)) ? 598 foldFMulConst(cast<Instruction>(Opnd0), C, &I) : 599 nullptr; 600 if (M0 && M1) { 601 if (Swap && FAddSub->getOpcode() == Instruction::FSub) 602 std::swap(M0, M1); 603 604 Instruction *RI = (FAddSub->getOpcode() == Instruction::FAdd) 605 ? BinaryOperator::CreateFAdd(M0, M1) 606 : BinaryOperator::CreateFSub(M0, M1); 607 RI->copyFastMathFlags(&I); 608 return RI; 609 } 610 } 611 } 612 } 613 } 614 615 // sqrt(X) * sqrt(X) -> X 616 if (AllowReassociate && (Op0 == Op1)) 617 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) 618 if (II->getIntrinsicID() == Intrinsic::sqrt) 619 return ReplaceInstUsesWith(I, II->getOperand(0)); 620 621 // Under unsafe algebra do: 622 // X * log2(0.5*Y) = X*log2(Y) - X 623 if (AllowReassociate) { 624 Value *OpX = nullptr; 625 Value *OpY = nullptr; 626 IntrinsicInst *Log2; 627 detectLog2OfHalf(Op0, OpY, Log2); 628 if (OpY) { 629 OpX = Op1; 630 } else { 631 detectLog2OfHalf(Op1, OpY, Log2); 632 if (OpY) { 633 OpX = Op0; 634 } 635 } 636 // if pattern detected emit alternate sequence 637 if (OpX && OpY) { 638 BuilderTy::FastMathFlagGuard Guard(*Builder); 639 Builder->SetFastMathFlags(Log2->getFastMathFlags()); 640 Log2->setArgOperand(0, OpY); 641 Value *FMulVal = Builder->CreateFMul(OpX, Log2); 642 Value *FSub = Builder->CreateFSub(FMulVal, OpX); 643 FSub->takeName(&I); 644 return ReplaceInstUsesWith(I, FSub); 645 } 646 } 647 648 // Handle symmetric situation in a 2-iteration loop 649 Value *Opnd0 = Op0; 650 Value *Opnd1 = Op1; 651 for (int i = 0; i < 2; i++) { 652 bool IgnoreZeroSign = I.hasNoSignedZeros(); 653 if (BinaryOperator::isFNeg(Opnd0, IgnoreZeroSign)) { 654 BuilderTy::FastMathFlagGuard Guard(*Builder); 655 Builder->SetFastMathFlags(I.getFastMathFlags()); 656 657 Value *N0 = dyn_castFNegVal(Opnd0, IgnoreZeroSign); 658 Value *N1 = dyn_castFNegVal(Opnd1, IgnoreZeroSign); 659 660 // -X * -Y => X*Y 661 if (N1) { 662 Value *FMul = Builder->CreateFMul(N0, N1); 663 FMul->takeName(&I); 664 return ReplaceInstUsesWith(I, FMul); 665 } 666 667 if (Opnd0->hasOneUse()) { 668 // -X * Y => -(X*Y) (Promote negation as high as possible) 669 Value *T = Builder->CreateFMul(N0, Opnd1); 670 Value *Neg = Builder->CreateFNeg(T); 671 Neg->takeName(&I); 672 return ReplaceInstUsesWith(I, Neg); 673 } 674 } 675 676 // (X*Y) * X => (X*X) * Y where Y != X 677 // The purpose is two-fold: 678 // 1) to form a power expression (of X). 679 // 2) potentially shorten the critical path: After transformation, the 680 // latency of the instruction Y is amortized by the expression of X*X, 681 // and therefore Y is in a "less critical" position compared to what it 682 // was before the transformation. 683 // 684 if (AllowReassociate) { 685 Value *Opnd0_0, *Opnd0_1; 686 if (Opnd0->hasOneUse() && 687 match(Opnd0, m_FMul(m_Value(Opnd0_0), m_Value(Opnd0_1)))) { 688 Value *Y = nullptr; 689 if (Opnd0_0 == Opnd1 && Opnd0_1 != Opnd1) 690 Y = Opnd0_1; 691 else if (Opnd0_1 == Opnd1 && Opnd0_0 != Opnd1) 692 Y = Opnd0_0; 693 694 if (Y) { 695 BuilderTy::FastMathFlagGuard Guard(*Builder); 696 Builder->SetFastMathFlags(I.getFastMathFlags()); 697 Value *T = Builder->CreateFMul(Opnd1, Opnd1); 698 699 Value *R = Builder->CreateFMul(T, Y); 700 R->takeName(&I); 701 return ReplaceInstUsesWith(I, R); 702 } 703 } 704 } 705 706 if (!isa<Constant>(Op1)) 707 std::swap(Opnd0, Opnd1); 708 else 709 break; 710 } 711 712 return Changed ? &I : nullptr; 713 } 714 715 /// Try to fold a divide or remainder of a select instruction. 716 bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) { 717 SelectInst *SI = cast<SelectInst>(I.getOperand(1)); 718 719 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y 720 int NonNullOperand = -1; 721 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1))) 722 if (ST->isNullValue()) 723 NonNullOperand = 2; 724 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y 725 if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2))) 726 if (ST->isNullValue()) 727 NonNullOperand = 1; 728 729 if (NonNullOperand == -1) 730 return false; 731 732 Value *SelectCond = SI->getOperand(0); 733 734 // Change the div/rem to use 'Y' instead of the select. 735 I.setOperand(1, SI->getOperand(NonNullOperand)); 736 737 // Okay, we know we replace the operand of the div/rem with 'Y' with no 738 // problem. However, the select, or the condition of the select may have 739 // multiple uses. Based on our knowledge that the operand must be non-zero, 740 // propagate the known value for the select into other uses of it, and 741 // propagate a known value of the condition into its other users. 742 743 // If the select and condition only have a single use, don't bother with this, 744 // early exit. 745 if (SI->use_empty() && SelectCond->hasOneUse()) 746 return true; 747 748 // Scan the current block backward, looking for other uses of SI. 749 BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin(); 750 751 while (BBI != BBFront) { 752 --BBI; 753 // If we found a call to a function, we can't assume it will return, so 754 // information from below it cannot be propagated above it. 755 if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI)) 756 break; 757 758 // Replace uses of the select or its condition with the known values. 759 for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end(); 760 I != E; ++I) { 761 if (*I == SI) { 762 *I = SI->getOperand(NonNullOperand); 763 Worklist.Add(&*BBI); 764 } else if (*I == SelectCond) { 765 *I = Builder->getInt1(NonNullOperand == 1); 766 Worklist.Add(&*BBI); 767 } 768 } 769 770 // If we past the instruction, quit looking for it. 771 if (&*BBI == SI) 772 SI = nullptr; 773 if (&*BBI == SelectCond) 774 SelectCond = nullptr; 775 776 // If we ran out of things to eliminate, break out of the loop. 777 if (!SelectCond && !SI) 778 break; 779 780 } 781 return true; 782 } 783 784 785 /// This function implements the transforms common to both integer division 786 /// instructions (udiv and sdiv). It is called by the visitors to those integer 787 /// division instructions. 788 /// @brief Common integer divide transforms 789 Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) { 790 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 791 792 // The RHS is known non-zero. 793 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) { 794 I.setOperand(1, V); 795 return &I; 796 } 797 798 // Handle cases involving: [su]div X, (select Cond, Y, Z) 799 // This does not apply for fdiv. 800 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 801 return &I; 802 803 if (Instruction *LHS = dyn_cast<Instruction>(Op0)) { 804 const APInt *C2; 805 if (match(Op1, m_APInt(C2))) { 806 Value *X; 807 const APInt *C1; 808 bool IsSigned = I.getOpcode() == Instruction::SDiv; 809 810 // (X / C1) / C2 -> X / (C1*C2) 811 if ((IsSigned && match(LHS, m_SDiv(m_Value(X), m_APInt(C1)))) || 812 (!IsSigned && match(LHS, m_UDiv(m_Value(X), m_APInt(C1))))) { 813 APInt Product(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); 814 if (!MultiplyOverflows(*C1, *C2, Product, IsSigned)) 815 return BinaryOperator::Create(I.getOpcode(), X, 816 ConstantInt::get(I.getType(), Product)); 817 } 818 819 if ((IsSigned && match(LHS, m_NSWMul(m_Value(X), m_APInt(C1)))) || 820 (!IsSigned && match(LHS, m_NUWMul(m_Value(X), m_APInt(C1))))) { 821 APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); 822 823 // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1. 824 if (IsMultiple(*C2, *C1, Quotient, IsSigned)) { 825 BinaryOperator *BO = BinaryOperator::Create( 826 I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient)); 827 BO->setIsExact(I.isExact()); 828 return BO; 829 } 830 831 // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2. 832 if (IsMultiple(*C1, *C2, Quotient, IsSigned)) { 833 BinaryOperator *BO = BinaryOperator::Create( 834 Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient)); 835 BO->setHasNoUnsignedWrap( 836 !IsSigned && 837 cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap()); 838 BO->setHasNoSignedWrap( 839 cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap()); 840 return BO; 841 } 842 } 843 844 if ((IsSigned && match(LHS, m_NSWShl(m_Value(X), m_APInt(C1))) && 845 *C1 != C1->getBitWidth() - 1) || 846 (!IsSigned && match(LHS, m_NUWShl(m_Value(X), m_APInt(C1))))) { 847 APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned); 848 APInt C1Shifted = APInt::getOneBitSet( 849 C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue())); 850 851 // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of C1. 852 if (IsMultiple(*C2, C1Shifted, Quotient, IsSigned)) { 853 BinaryOperator *BO = BinaryOperator::Create( 854 I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient)); 855 BO->setIsExact(I.isExact()); 856 return BO; 857 } 858 859 // (X << C1) / C2 -> X * (C2 >> C1) if C1 is a multiple of C2. 860 if (IsMultiple(C1Shifted, *C2, Quotient, IsSigned)) { 861 BinaryOperator *BO = BinaryOperator::Create( 862 Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient)); 863 BO->setHasNoUnsignedWrap( 864 !IsSigned && 865 cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap()); 866 BO->setHasNoSignedWrap( 867 cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap()); 868 return BO; 869 } 870 } 871 872 if (*C2 != 0) { // avoid X udiv 0 873 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 874 if (Instruction *R = FoldOpIntoSelect(I, SI)) 875 return R; 876 if (isa<PHINode>(Op0)) 877 if (Instruction *NV = FoldOpIntoPhi(I)) 878 return NV; 879 } 880 } 881 } 882 883 if (ConstantInt *One = dyn_cast<ConstantInt>(Op0)) { 884 if (One->isOne() && !I.getType()->isIntegerTy(1)) { 885 bool isSigned = I.getOpcode() == Instruction::SDiv; 886 if (isSigned) { 887 // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the 888 // result is one, if Op1 is -1 then the result is minus one, otherwise 889 // it's zero. 890 Value *Inc = Builder->CreateAdd(Op1, One); 891 Value *Cmp = Builder->CreateICmpULT( 892 Inc, ConstantInt::get(I.getType(), 3)); 893 return SelectInst::Create(Cmp, Op1, ConstantInt::get(I.getType(), 0)); 894 } else { 895 // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the 896 // result is one, otherwise it's zero. 897 return new ZExtInst(Builder->CreateICmpEQ(Op1, One), I.getType()); 898 } 899 } 900 } 901 902 // See if we can fold away this div instruction. 903 if (SimplifyDemandedInstructionBits(I)) 904 return &I; 905 906 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y 907 Value *X = nullptr, *Z = nullptr; 908 if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1 909 bool isSigned = I.getOpcode() == Instruction::SDiv; 910 if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) || 911 (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1))))) 912 return BinaryOperator::Create(I.getOpcode(), X, Op1); 913 } 914 915 return nullptr; 916 } 917 918 /// dyn_castZExtVal - Checks if V is a zext or constant that can 919 /// be truncated to Ty without losing bits. 920 static Value *dyn_castZExtVal(Value *V, Type *Ty) { 921 if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) { 922 if (Z->getSrcTy() == Ty) 923 return Z->getOperand(0); 924 } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) { 925 if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth()) 926 return ConstantExpr::getTrunc(C, Ty); 927 } 928 return nullptr; 929 } 930 931 namespace { 932 const unsigned MaxDepth = 6; 933 typedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1, 934 const BinaryOperator &I, 935 InstCombiner &IC); 936 937 /// \brief Used to maintain state for visitUDivOperand(). 938 struct UDivFoldAction { 939 FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this 940 ///< operand. This can be zero if this action 941 ///< joins two actions together. 942 943 Value *OperandToFold; ///< Which operand to fold. 944 union { 945 Instruction *FoldResult; ///< The instruction returned when FoldAction is 946 ///< invoked. 947 948 size_t SelectLHSIdx; ///< Stores the LHS action index if this action 949 ///< joins two actions together. 950 }; 951 952 UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand) 953 : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {} 954 UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS) 955 : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {} 956 }; 957 } 958 959 // X udiv 2^C -> X >> C 960 static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1, 961 const BinaryOperator &I, InstCombiner &IC) { 962 const APInt &C = cast<Constant>(Op1)->getUniqueInteger(); 963 BinaryOperator *LShr = BinaryOperator::CreateLShr( 964 Op0, ConstantInt::get(Op0->getType(), C.logBase2())); 965 if (I.isExact()) 966 LShr->setIsExact(); 967 return LShr; 968 } 969 970 // X udiv C, where C >= signbit 971 static Instruction *foldUDivNegCst(Value *Op0, Value *Op1, 972 const BinaryOperator &I, InstCombiner &IC) { 973 Value *ICI = IC.Builder->CreateICmpULT(Op0, cast<ConstantInt>(Op1)); 974 975 return SelectInst::Create(ICI, Constant::getNullValue(I.getType()), 976 ConstantInt::get(I.getType(), 1)); 977 } 978 979 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 980 static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I, 981 InstCombiner &IC) { 982 Instruction *ShiftLeft = cast<Instruction>(Op1); 983 if (isa<ZExtInst>(ShiftLeft)) 984 ShiftLeft = cast<Instruction>(ShiftLeft->getOperand(0)); 985 986 const APInt &CI = 987 cast<Constant>(ShiftLeft->getOperand(0))->getUniqueInteger(); 988 Value *N = ShiftLeft->getOperand(1); 989 if (CI != 1) 990 N = IC.Builder->CreateAdd(N, ConstantInt::get(N->getType(), CI.logBase2())); 991 if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1)) 992 N = IC.Builder->CreateZExt(N, Z->getDestTy()); 993 BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N); 994 if (I.isExact()) 995 LShr->setIsExact(); 996 return LShr; 997 } 998 999 // \brief Recursively visits the possible right hand operands of a udiv 1000 // instruction, seeing through select instructions, to determine if we can 1001 // replace the udiv with something simpler. If we find that an operand is not 1002 // able to simplify the udiv, we abort the entire transformation. 1003 static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I, 1004 SmallVectorImpl<UDivFoldAction> &Actions, 1005 unsigned Depth = 0) { 1006 // Check to see if this is an unsigned division with an exact power of 2, 1007 // if so, convert to a right shift. 1008 if (match(Op1, m_Power2())) { 1009 Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1)); 1010 return Actions.size(); 1011 } 1012 1013 if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) 1014 // X udiv C, where C >= signbit 1015 if (C->getValue().isNegative()) { 1016 Actions.push_back(UDivFoldAction(foldUDivNegCst, C)); 1017 return Actions.size(); 1018 } 1019 1020 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2) 1021 if (match(Op1, m_Shl(m_Power2(), m_Value())) || 1022 match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) { 1023 Actions.push_back(UDivFoldAction(foldUDivShl, Op1)); 1024 return Actions.size(); 1025 } 1026 1027 // The remaining tests are all recursive, so bail out if we hit the limit. 1028 if (Depth++ == MaxDepth) 1029 return 0; 1030 1031 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1032 if (size_t LHSIdx = 1033 visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth)) 1034 if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) { 1035 Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1)); 1036 return Actions.size(); 1037 } 1038 1039 return 0; 1040 } 1041 1042 Instruction *InstCombiner::visitUDiv(BinaryOperator &I) { 1043 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1044 1045 if (Value *V = SimplifyVectorOp(I)) 1046 return ReplaceInstUsesWith(I, V); 1047 1048 if (Value *V = SimplifyUDivInst(Op0, Op1, DL, TLI, DT, AC)) 1049 return ReplaceInstUsesWith(I, V); 1050 1051 // Handle the integer div common cases 1052 if (Instruction *Common = commonIDivTransforms(I)) 1053 return Common; 1054 1055 // (x lshr C1) udiv C2 --> x udiv (C2 << C1) 1056 { 1057 Value *X; 1058 const APInt *C1, *C2; 1059 if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && 1060 match(Op1, m_APInt(C2))) { 1061 bool Overflow; 1062 APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow); 1063 if (!Overflow) { 1064 bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value())); 1065 BinaryOperator *BO = BinaryOperator::CreateUDiv( 1066 X, ConstantInt::get(X->getType(), C2ShlC1)); 1067 if (IsExact) 1068 BO->setIsExact(); 1069 return BO; 1070 } 1071 } 1072 } 1073 1074 // (zext A) udiv (zext B) --> zext (A udiv B) 1075 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 1076 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 1077 return new ZExtInst( 1078 Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", I.isExact()), 1079 I.getType()); 1080 1081 // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...)))) 1082 SmallVector<UDivFoldAction, 6> UDivActions; 1083 if (visitUDivOperand(Op0, Op1, I, UDivActions)) 1084 for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) { 1085 FoldUDivOperandCb Action = UDivActions[i].FoldAction; 1086 Value *ActionOp1 = UDivActions[i].OperandToFold; 1087 Instruction *Inst; 1088 if (Action) 1089 Inst = Action(Op0, ActionOp1, I, *this); 1090 else { 1091 // This action joins two actions together. The RHS of this action is 1092 // simply the last action we processed, we saved the LHS action index in 1093 // the joining action. 1094 size_t SelectRHSIdx = i - 1; 1095 Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult; 1096 size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx; 1097 Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult; 1098 Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(), 1099 SelectLHS, SelectRHS); 1100 } 1101 1102 // If this is the last action to process, return it to the InstCombiner. 1103 // Otherwise, we insert it before the UDiv and record it so that we may 1104 // use it as part of a joining action (i.e., a SelectInst). 1105 if (e - i != 1) { 1106 Inst->insertBefore(&I); 1107 UDivActions[i].FoldResult = Inst; 1108 } else 1109 return Inst; 1110 } 1111 1112 return nullptr; 1113 } 1114 1115 Instruction *InstCombiner::visitSDiv(BinaryOperator &I) { 1116 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1117 1118 if (Value *V = SimplifyVectorOp(I)) 1119 return ReplaceInstUsesWith(I, V); 1120 1121 if (Value *V = SimplifySDivInst(Op0, Op1, DL, TLI, DT, AC)) 1122 return ReplaceInstUsesWith(I, V); 1123 1124 // Handle the integer div common cases 1125 if (Instruction *Common = commonIDivTransforms(I)) 1126 return Common; 1127 1128 // sdiv X, -1 == -X 1129 if (match(Op1, m_AllOnes())) 1130 return BinaryOperator::CreateNeg(Op0); 1131 1132 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) { 1133 // sdiv X, C --> ashr exact X, log2(C) 1134 if (I.isExact() && RHS->getValue().isNonNegative() && 1135 RHS->getValue().isPowerOf2()) { 1136 Value *ShAmt = llvm::ConstantInt::get(RHS->getType(), 1137 RHS->getValue().exactLogBase2()); 1138 return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName()); 1139 } 1140 } 1141 1142 if (Constant *RHS = dyn_cast<Constant>(Op1)) { 1143 // X/INT_MIN -> X == INT_MIN 1144 if (RHS->isMinSignedValue()) 1145 return new ZExtInst(Builder->CreateICmpEQ(Op0, Op1), I.getType()); 1146 1147 // -X/C --> X/-C provided the negation doesn't overflow. 1148 Value *X; 1149 if (match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) { 1150 auto *BO = BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(RHS)); 1151 BO->setIsExact(I.isExact()); 1152 return BO; 1153 } 1154 } 1155 1156 // If the sign bits of both operands are zero (i.e. we can prove they are 1157 // unsigned inputs), turn this into a udiv. 1158 if (I.getType()->isIntegerTy()) { 1159 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 1160 if (MaskedValueIsZero(Op0, Mask, 0, &I)) { 1161 if (MaskedValueIsZero(Op1, Mask, 0, &I)) { 1162 // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set 1163 auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 1164 BO->setIsExact(I.isExact()); 1165 return BO; 1166 } 1167 1168 if (isKnownToBeAPowerOfTwo(Op1, DL, /*OrZero*/ true, 0, AC, &I, DT)) { 1169 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y) 1170 // Safe because the only negative value (1 << Y) can take on is 1171 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have 1172 // the sign bit set. 1173 auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName()); 1174 BO->setIsExact(I.isExact()); 1175 return BO; 1176 } 1177 } 1178 } 1179 1180 return nullptr; 1181 } 1182 1183 /// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special 1184 /// FP value and: 1185 /// 1) 1/C is exact, or 1186 /// 2) reciprocal is allowed. 1187 /// If the conversion was successful, the simplified expression "X * 1/C" is 1188 /// returned; otherwise, NULL is returned. 1189 /// 1190 static Instruction *CvtFDivConstToReciprocal(Value *Dividend, Constant *Divisor, 1191 bool AllowReciprocal) { 1192 if (!isa<ConstantFP>(Divisor)) // TODO: handle vectors. 1193 return nullptr; 1194 1195 const APFloat &FpVal = cast<ConstantFP>(Divisor)->getValueAPF(); 1196 APFloat Reciprocal(FpVal.getSemantics()); 1197 bool Cvt = FpVal.getExactInverse(&Reciprocal); 1198 1199 if (!Cvt && AllowReciprocal && FpVal.isFiniteNonZero()) { 1200 Reciprocal = APFloat(FpVal.getSemantics(), 1.0f); 1201 (void)Reciprocal.divide(FpVal, APFloat::rmNearestTiesToEven); 1202 Cvt = !Reciprocal.isDenormal(); 1203 } 1204 1205 if (!Cvt) 1206 return nullptr; 1207 1208 ConstantFP *R; 1209 R = ConstantFP::get(Dividend->getType()->getContext(), Reciprocal); 1210 return BinaryOperator::CreateFMul(Dividend, R); 1211 } 1212 1213 Instruction *InstCombiner::visitFDiv(BinaryOperator &I) { 1214 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1215 1216 if (Value *V = SimplifyVectorOp(I)) 1217 return ReplaceInstUsesWith(I, V); 1218 1219 if (Value *V = SimplifyFDivInst(Op0, Op1, I.getFastMathFlags(), 1220 DL, TLI, DT, AC)) 1221 return ReplaceInstUsesWith(I, V); 1222 1223 if (isa<Constant>(Op0)) 1224 if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) 1225 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1226 return R; 1227 1228 bool AllowReassociate = I.hasUnsafeAlgebra(); 1229 bool AllowReciprocal = I.hasAllowReciprocal(); 1230 1231 if (Constant *Op1C = dyn_cast<Constant>(Op1)) { 1232 if (SelectInst *SI = dyn_cast<SelectInst>(Op0)) 1233 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1234 return R; 1235 1236 if (AllowReassociate) { 1237 Constant *C1 = nullptr; 1238 Constant *C2 = Op1C; 1239 Value *X; 1240 Instruction *Res = nullptr; 1241 1242 if (match(Op0, m_FMul(m_Value(X), m_Constant(C1)))) { 1243 // (X*C1)/C2 => X * (C1/C2) 1244 // 1245 Constant *C = ConstantExpr::getFDiv(C1, C2); 1246 if (isNormalFp(C)) 1247 Res = BinaryOperator::CreateFMul(X, C); 1248 } else if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) { 1249 // (X/C1)/C2 => X /(C2*C1) [=> X * 1/(C2*C1) if reciprocal is allowed] 1250 // 1251 Constant *C = ConstantExpr::getFMul(C1, C2); 1252 if (isNormalFp(C)) { 1253 Res = CvtFDivConstToReciprocal(X, C, AllowReciprocal); 1254 if (!Res) 1255 Res = BinaryOperator::CreateFDiv(X, C); 1256 } 1257 } 1258 1259 if (Res) { 1260 Res->setFastMathFlags(I.getFastMathFlags()); 1261 return Res; 1262 } 1263 } 1264 1265 // X / C => X * 1/C 1266 if (Instruction *T = CvtFDivConstToReciprocal(Op0, Op1C, AllowReciprocal)) { 1267 T->copyFastMathFlags(&I); 1268 return T; 1269 } 1270 1271 return nullptr; 1272 } 1273 1274 if (AllowReassociate && isa<Constant>(Op0)) { 1275 Constant *C1 = cast<Constant>(Op0), *C2; 1276 Constant *Fold = nullptr; 1277 Value *X; 1278 bool CreateDiv = true; 1279 1280 // C1 / (X*C2) => (C1/C2) / X 1281 if (match(Op1, m_FMul(m_Value(X), m_Constant(C2)))) 1282 Fold = ConstantExpr::getFDiv(C1, C2); 1283 else if (match(Op1, m_FDiv(m_Value(X), m_Constant(C2)))) { 1284 // C1 / (X/C2) => (C1*C2) / X 1285 Fold = ConstantExpr::getFMul(C1, C2); 1286 } else if (match(Op1, m_FDiv(m_Constant(C2), m_Value(X)))) { 1287 // C1 / (C2/X) => (C1/C2) * X 1288 Fold = ConstantExpr::getFDiv(C1, C2); 1289 CreateDiv = false; 1290 } 1291 1292 if (Fold && isNormalFp(Fold)) { 1293 Instruction *R = CreateDiv ? BinaryOperator::CreateFDiv(Fold, X) 1294 : BinaryOperator::CreateFMul(X, Fold); 1295 R->setFastMathFlags(I.getFastMathFlags()); 1296 return R; 1297 } 1298 return nullptr; 1299 } 1300 1301 if (AllowReassociate) { 1302 Value *X, *Y; 1303 Value *NewInst = nullptr; 1304 Instruction *SimpR = nullptr; 1305 1306 if (Op0->hasOneUse() && match(Op0, m_FDiv(m_Value(X), m_Value(Y)))) { 1307 // (X/Y) / Z => X / (Y*Z) 1308 // 1309 if (!isa<Constant>(Y) || !isa<Constant>(Op1)) { 1310 NewInst = Builder->CreateFMul(Y, Op1); 1311 if (Instruction *RI = dyn_cast<Instruction>(NewInst)) { 1312 FastMathFlags Flags = I.getFastMathFlags(); 1313 Flags &= cast<Instruction>(Op0)->getFastMathFlags(); 1314 RI->setFastMathFlags(Flags); 1315 } 1316 SimpR = BinaryOperator::CreateFDiv(X, NewInst); 1317 } 1318 } else if (Op1->hasOneUse() && match(Op1, m_FDiv(m_Value(X), m_Value(Y)))) { 1319 // Z / (X/Y) => Z*Y / X 1320 // 1321 if (!isa<Constant>(Y) || !isa<Constant>(Op0)) { 1322 NewInst = Builder->CreateFMul(Op0, Y); 1323 if (Instruction *RI = dyn_cast<Instruction>(NewInst)) { 1324 FastMathFlags Flags = I.getFastMathFlags(); 1325 Flags &= cast<Instruction>(Op1)->getFastMathFlags(); 1326 RI->setFastMathFlags(Flags); 1327 } 1328 SimpR = BinaryOperator::CreateFDiv(NewInst, X); 1329 } 1330 } 1331 1332 if (NewInst) { 1333 if (Instruction *T = dyn_cast<Instruction>(NewInst)) 1334 T->setDebugLoc(I.getDebugLoc()); 1335 SimpR->setFastMathFlags(I.getFastMathFlags()); 1336 return SimpR; 1337 } 1338 } 1339 1340 return nullptr; 1341 } 1342 1343 /// This function implements the transforms common to both integer remainder 1344 /// instructions (urem and srem). It is called by the visitors to those integer 1345 /// remainder instructions. 1346 /// @brief Common integer remainder transforms 1347 Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) { 1348 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1349 1350 // The RHS is known non-zero. 1351 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) { 1352 I.setOperand(1, V); 1353 return &I; 1354 } 1355 1356 // Handle cases involving: rem X, (select Cond, Y, Z) 1357 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 1358 return &I; 1359 1360 if (isa<Constant>(Op1)) { 1361 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) { 1362 if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) { 1363 if (Instruction *R = FoldOpIntoSelect(I, SI)) 1364 return R; 1365 } else if (isa<PHINode>(Op0I)) { 1366 if (Instruction *NV = FoldOpIntoPhi(I)) 1367 return NV; 1368 } 1369 1370 // See if we can fold away this rem instruction. 1371 if (SimplifyDemandedInstructionBits(I)) 1372 return &I; 1373 } 1374 } 1375 1376 return nullptr; 1377 } 1378 1379 Instruction *InstCombiner::visitURem(BinaryOperator &I) { 1380 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1381 1382 if (Value *V = SimplifyVectorOp(I)) 1383 return ReplaceInstUsesWith(I, V); 1384 1385 if (Value *V = SimplifyURemInst(Op0, Op1, DL, TLI, DT, AC)) 1386 return ReplaceInstUsesWith(I, V); 1387 1388 if (Instruction *common = commonIRemTransforms(I)) 1389 return common; 1390 1391 // (zext A) urem (zext B) --> zext (A urem B) 1392 if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0)) 1393 if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy())) 1394 return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1), 1395 I.getType()); 1396 1397 // X urem Y -> X and Y-1, where Y is a power of 2, 1398 if (isKnownToBeAPowerOfTwo(Op1, DL, /*OrZero*/ true, 0, AC, &I, DT)) { 1399 Constant *N1 = Constant::getAllOnesValue(I.getType()); 1400 Value *Add = Builder->CreateAdd(Op1, N1); 1401 return BinaryOperator::CreateAnd(Op0, Add); 1402 } 1403 1404 // 1 urem X -> zext(X != 1) 1405 if (match(Op0, m_One())) { 1406 Value *Cmp = Builder->CreateICmpNE(Op1, Op0); 1407 Value *Ext = Builder->CreateZExt(Cmp, I.getType()); 1408 return ReplaceInstUsesWith(I, Ext); 1409 } 1410 1411 return nullptr; 1412 } 1413 1414 Instruction *InstCombiner::visitSRem(BinaryOperator &I) { 1415 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1416 1417 if (Value *V = SimplifyVectorOp(I)) 1418 return ReplaceInstUsesWith(I, V); 1419 1420 if (Value *V = SimplifySRemInst(Op0, Op1, DL, TLI, DT, AC)) 1421 return ReplaceInstUsesWith(I, V); 1422 1423 // Handle the integer rem common cases 1424 if (Instruction *Common = commonIRemTransforms(I)) 1425 return Common; 1426 1427 { 1428 const APInt *Y; 1429 // X % -Y -> X % Y 1430 if (match(Op1, m_APInt(Y)) && Y->isNegative() && !Y->isMinSignedValue()) { 1431 Worklist.AddValue(I.getOperand(1)); 1432 I.setOperand(1, ConstantInt::get(I.getType(), -*Y)); 1433 return &I; 1434 } 1435 } 1436 1437 // If the sign bits of both operands are zero (i.e. we can prove they are 1438 // unsigned inputs), turn this into a urem. 1439 if (I.getType()->isIntegerTy()) { 1440 APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits())); 1441 if (MaskedValueIsZero(Op1, Mask, 0, &I) && 1442 MaskedValueIsZero(Op0, Mask, 0, &I)) { 1443 // X srem Y -> X urem Y, iff X and Y don't have sign bit set 1444 return BinaryOperator::CreateURem(Op0, Op1, I.getName()); 1445 } 1446 } 1447 1448 // If it's a constant vector, flip any negative values positive. 1449 if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) { 1450 Constant *C = cast<Constant>(Op1); 1451 unsigned VWidth = C->getType()->getVectorNumElements(); 1452 1453 bool hasNegative = false; 1454 bool hasMissing = false; 1455 for (unsigned i = 0; i != VWidth; ++i) { 1456 Constant *Elt = C->getAggregateElement(i); 1457 if (!Elt) { 1458 hasMissing = true; 1459 break; 1460 } 1461 1462 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt)) 1463 if (RHS->isNegative()) 1464 hasNegative = true; 1465 } 1466 1467 if (hasNegative && !hasMissing) { 1468 SmallVector<Constant *, 16> Elts(VWidth); 1469 for (unsigned i = 0; i != VWidth; ++i) { 1470 Elts[i] = C->getAggregateElement(i); // Handle undef, etc. 1471 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) { 1472 if (RHS->isNegative()) 1473 Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS)); 1474 } 1475 } 1476 1477 Constant *NewRHSV = ConstantVector::get(Elts); 1478 if (NewRHSV != C) { // Don't loop on -MININT 1479 Worklist.AddValue(I.getOperand(1)); 1480 I.setOperand(1, NewRHSV); 1481 return &I; 1482 } 1483 } 1484 } 1485 1486 return nullptr; 1487 } 1488 1489 Instruction *InstCombiner::visitFRem(BinaryOperator &I) { 1490 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1); 1491 1492 if (Value *V = SimplifyVectorOp(I)) 1493 return ReplaceInstUsesWith(I, V); 1494 1495 if (Value *V = SimplifyFRemInst(Op0, Op1, I.getFastMathFlags(), 1496 DL, TLI, DT, AC)) 1497 return ReplaceInstUsesWith(I, V); 1498 1499 // Handle cases involving: rem X, (select Cond, Y, Z) 1500 if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I)) 1501 return &I; 1502 1503 return nullptr; 1504 } 1505