contrib/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

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