lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

   1 //===- InstCombineMulDivRem.cpp -------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv,
  10 // srem, urem, frem.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "InstCombineInternal.h"
  15 #include "llvm/ADT/APFloat.h"
  16 #include "llvm/ADT/APInt.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/Analysis/InstructionSimplify.h"
  19 #include "llvm/IR/BasicBlock.h"
  20 #include "llvm/IR/Constant.h"
  21 #include "llvm/IR/Constants.h"
  22 #include "llvm/IR/InstrTypes.h"
  23 #include "llvm/IR/Instruction.h"
  24 #include "llvm/IR/Instructions.h"
  25 #include "llvm/IR/IntrinsicInst.h"
  26 #include "llvm/IR/Intrinsics.h"
  27 #include "llvm/IR/Operator.h"
  28 #include "llvm/IR/PatternMatch.h"
  29 #include "llvm/IR/Type.h"
  30 #include "llvm/IR/Value.h"
  31 #include "llvm/Support/Casting.h"
  32 #include "llvm/Support/ErrorHandling.h"
  33 #include "llvm/Support/KnownBits.h"
  34 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
  35 #include "llvm/Transforms/Utils/BuildLibCalls.h"
  36 #include <cassert>
  37 #include <cstddef>
  38 #include <cstdint>
  39 #include <utility>
  40
  41 using namespace llvm;
  42 using namespace PatternMatch;
  43
  44 #define DEBUG_TYPE "instcombine"
  45
  46 /// The specific integer value is used in a context where it is known to be
  47 /// non-zero.  If this allows us to simplify the computation, do so and return
  48 /// the new operand, otherwise return null.
  49 static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC,
  50                                         Instruction &CxtI) {
  51   // If V has multiple uses, then we would have to do more analysis to determine
  52   // if this is safe.  For example, the use could be in dynamically unreached
  53   // code.
  54   if (!V->hasOneUse()) return nullptr;
  55
  56   bool MadeChange = false;
  57
  58   // ((1 << A) >>u B) --> (1 << (A-B))
  59   // Because V cannot be zero, we know that B is less than A.
  60   Value *A = nullptr, *B = nullptr, *One = nullptr;
  61   if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) &&
  62       match(One, m_One())) {
  63     A = IC.Builder.CreateSub(A, B);
  64     return IC.Builder.CreateShl(One, A);
  65   }
  66
  67   // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
  68   // inexact.  Similarly for <<.
  69   BinaryOperator *I = dyn_cast<BinaryOperator>(V);
  70   if (I && I->isLogicalShift() &&
  71       IC.isKnownToBeAPowerOfTwo(I->getOperand(0), false, 0, &CxtI)) {
  72     // We know that this is an exact/nuw shift and that the input is a
  73     // non-zero context as well.
  74     if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) {
  75       I->setOperand(0, V2);
  76       MadeChange = true;
  77     }
  78
  79     if (I->getOpcode() == Instruction::LShr && !I->isExact()) {
  80       I->setIsExact();
  81       MadeChange = true;
  82     }
  83
  84     if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) {
  85       I->setHasNoUnsignedWrap();
  86       MadeChange = true;
  87     }
  88   }
  89
  90   // TODO: Lots more we could do here:
  91   //    If V is a phi node, we can call this on each of its operands.
  92   //    "select cond, X, 0" can simplify to "X".
  93
  94   return MadeChange ? V : nullptr;
  95 }
  96
  97 /// A helper routine of InstCombiner::visitMul().
  98 ///
  99 /// If C is a scalar/vector of known powers of 2, then this function returns
 100 /// a new scalar/vector obtained from logBase2 of C.
 101 /// Return a null pointer otherwise.
 102 static Constant *getLogBase2(Type *Ty, Constant *C) {
 103   const APInt *IVal;
 104   if (match(C, m_APInt(IVal)) && IVal->isPowerOf2())
 105     return ConstantInt::get(Ty, IVal->logBase2());
 106
 107   if (!Ty->isVectorTy())
 108     return nullptr;
 109
 110   SmallVector<Constant *, 4> Elts;
 111   for (unsigned I = 0, E = Ty->getVectorNumElements(); I != E; ++I) {
 112     Constant *Elt = C->getAggregateElement(I);
 113     if (!Elt)
 114       return nullptr;
 115     if (isa<UndefValue>(Elt)) {
 116       Elts.push_back(UndefValue::get(Ty->getScalarType()));
 117       continue;
 118     }
 119     if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2())
 120       return nullptr;
 121     Elts.push_back(ConstantInt::get(Ty->getScalarType(), IVal->logBase2()));
 122   }
 123
 124   return ConstantVector::get(Elts);
 125 }
 126
 127 // TODO: This is a specific form of a much more general pattern.
 128 //       We could detect a select with any binop identity constant, or we
 129 //       could use SimplifyBinOp to see if either arm of the select reduces.
 130 //       But that needs to be done carefully and/or while removing potential
 131 //       reverse canonicalizations as in InstCombiner::foldSelectIntoOp().
 132 static Value *foldMulSelectToNegate(BinaryOperator &I,
 133                                     InstCombiner::BuilderTy &Builder) {
 134   Value *Cond, *OtherOp;
 135
 136   // mul (select Cond, 1, -1), OtherOp --> select Cond, OtherOp, -OtherOp
 137   // mul OtherOp, (select Cond, 1, -1) --> select Cond, OtherOp, -OtherOp
 138   if (match(&I, m_c_Mul(m_OneUse(m_Select(m_Value(Cond), m_One(), m_AllOnes())),
 139                         m_Value(OtherOp))))
 140     return Builder.CreateSelect(Cond, OtherOp, Builder.CreateNeg(OtherOp));
 141
 142   // mul (select Cond, -1, 1), OtherOp --> select Cond, -OtherOp, OtherOp
 143   // mul OtherOp, (select Cond, -1, 1) --> select Cond, -OtherOp, OtherOp
 144   if (match(&I, m_c_Mul(m_OneUse(m_Select(m_Value(Cond), m_AllOnes(), m_One())),
 145                         m_Value(OtherOp))))
 146     return Builder.CreateSelect(Cond, Builder.CreateNeg(OtherOp), OtherOp);
 147
 148   // fmul (select Cond, 1.0, -1.0), OtherOp --> select Cond, OtherOp, -OtherOp
 149   // fmul OtherOp, (select Cond, 1.0, -1.0) --> select Cond, OtherOp, -OtherOp
 150   if (match(&I, m_c_FMul(m_OneUse(m_Select(m_Value(Cond), m_SpecificFP(1.0),
 151                                            m_SpecificFP(-1.0))),
 152                          m_Value(OtherOp)))) {
 153     IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
 154     Builder.setFastMathFlags(I.getFastMathFlags());
 155     return Builder.CreateSelect(Cond, OtherOp, Builder.CreateFNeg(OtherOp));
 156   }
 157
 158   // fmul (select Cond, -1.0, 1.0), OtherOp --> select Cond, -OtherOp, OtherOp
 159   // fmul OtherOp, (select Cond, -1.0, 1.0) --> select Cond, -OtherOp, OtherOp
 160   if (match(&I, m_c_FMul(m_OneUse(m_Select(m_Value(Cond), m_SpecificFP(-1.0),
 161                                            m_SpecificFP(1.0))),
 162                          m_Value(OtherOp)))) {
 163     IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
 164     Builder.setFastMathFlags(I.getFastMathFlags());
 165     return Builder.CreateSelect(Cond, Builder.CreateFNeg(OtherOp), OtherOp);
 166   }
 167
 168   return nullptr;
 169 }
 170
 171 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
 172   if (Value *V = SimplifyMulInst(I.getOperand(0), I.getOperand(1),
 173                                  SQ.getWithInstruction(&I)))
 174     return replaceInstUsesWith(I, V);
 175
 176   if (SimplifyAssociativeOrCommutative(I))
 177     return &I;
 178
 179   if (Instruction *X = foldVectorBinop(I))
 180     return X;
 181
 182   if (Value *V = SimplifyUsingDistributiveLaws(I))
 183     return replaceInstUsesWith(I, V);
 184
 185   // X * -1 == 0 - X
 186   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 187   if (match(Op1, m_AllOnes())) {
 188     BinaryOperator *BO = BinaryOperator::CreateNeg(Op0, I.getName());
 189     if (I.hasNoSignedWrap())
 190       BO->setHasNoSignedWrap();
 191     return BO;
 192   }
 193
 194   // Also allow combining multiply instructions on vectors.
 195   {
 196     Value *NewOp;
 197     Constant *C1, *C2;
 198     const APInt *IVal;
 199     if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
 200                         m_Constant(C1))) &&
 201         match(C1, m_APInt(IVal))) {
 202       // ((X << C2)*C1) == (X * (C1 << C2))
 203       Constant *Shl = ConstantExpr::getShl(C1, C2);
 204       BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0));
 205       BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl);
 206       if (I.hasNoUnsignedWrap() && Mul->hasNoUnsignedWrap())
 207         BO->setHasNoUnsignedWrap();
 208       if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap() &&
 209           Shl->isNotMinSignedValue())
 210         BO->setHasNoSignedWrap();
 211       return BO;
 212     }
 213
 214     if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
 215       // Replace X*(2^C) with X << C, where C is either a scalar or a vector.
 216       if (Constant *NewCst = getLogBase2(NewOp->getType(), C1)) {
 217         BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
 218
 219         if (I.hasNoUnsignedWrap())
 220           Shl->setHasNoUnsignedWrap();
 221         if (I.hasNoSignedWrap()) {
 222           const APInt *V;
 223           if (match(NewCst, m_APInt(V)) && *V != V->getBitWidth() - 1)
 224             Shl->setHasNoSignedWrap();
 225         }
 226
 227         return Shl;
 228       }
 229     }
 230   }
 231
 232   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 233     // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n
 234     // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n
 235     // The "* (2**n)" thus becomes a potential shifting opportunity.
 236     {
 237       const APInt &   Val = CI->getValue();
 238       const APInt &PosVal = Val.abs();
 239       if (Val.isNegative() && PosVal.isPowerOf2()) {
 240         Value *X = nullptr, *Y = nullptr;
 241         if (Op0->hasOneUse()) {
 242           ConstantInt *C1;
 243           Value *Sub = nullptr;
 244           if (match(Op0, m_Sub(m_Value(Y), m_Value(X))))
 245             Sub = Builder.CreateSub(X, Y, "suba");
 246           else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1))))
 247             Sub = Builder.CreateSub(Builder.CreateNeg(C1), Y, "subc");
 248           if (Sub)
 249             return
 250               BinaryOperator::CreateMul(Sub,
 251                                         ConstantInt::get(Y->getType(), PosVal));
 252         }
 253       }
 254     }
 255   }
 256
 257   if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
 258     return FoldedMul;
 259
 260   if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
 261     return replaceInstUsesWith(I, FoldedMul);
 262
 263   // Simplify mul instructions with a constant RHS.
 264   if (isa<Constant>(Op1)) {
 265     // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
 266     Value *X;
 267     Constant *C1;
 268     if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) {
 269       Value *Mul = Builder.CreateMul(C1, Op1);
 270       // Only go forward with the transform if C1*CI simplifies to a tidier
 271       // constant.
 272       if (!match(Mul, m_Mul(m_Value(), m_Value())))
 273         return BinaryOperator::CreateAdd(Builder.CreateMul(X, Op1), Mul);
 274     }
 275   }
 276
 277   // -X * C --> X * -C
 278   Value *X, *Y;
 279   Constant *Op1C;
 280   if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Constant(Op1C)))
 281     return BinaryOperator::CreateMul(X, ConstantExpr::getNeg(Op1C));
 282
 283   // -X * -Y --> X * Y
 284   if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Neg(m_Value(Y)))) {
 285     auto *NewMul = BinaryOperator::CreateMul(X, Y);
 286     if (I.hasNoSignedWrap() &&
 287         cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap() &&
 288         cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap())
 289       NewMul->setHasNoSignedWrap();
 290     return NewMul;
 291   }
 292
 293   // -X * Y --> -(X * Y)
 294   // X * -Y --> -(X * Y)
 295   if (match(&I, m_c_Mul(m_OneUse(m_Neg(m_Value(X))), m_Value(Y))))
 296     return BinaryOperator::CreateNeg(Builder.CreateMul(X, Y));
 297
 298   // (X / Y) *  Y = X - (X % Y)
 299   // (X / Y) * -Y = (X % Y) - X
 300   {
 301     Value *Y = Op1;
 302     BinaryOperator *Div = dyn_cast<BinaryOperator>(Op0);
 303     if (!Div || (Div->getOpcode() != Instruction::UDiv &&
 304                  Div->getOpcode() != Instruction::SDiv)) {
 305       Y = Op0;
 306       Div = dyn_cast<BinaryOperator>(Op1);
 307     }
 308     Value *Neg = dyn_castNegVal(Y);
 309     if (Div && Div->hasOneUse() &&
 310         (Div->getOperand(1) == Y || Div->getOperand(1) == Neg) &&
 311         (Div->getOpcode() == Instruction::UDiv ||
 312          Div->getOpcode() == Instruction::SDiv)) {
 313       Value *X = Div->getOperand(0), *DivOp1 = Div->getOperand(1);
 314
 315       // If the division is exact, X % Y is zero, so we end up with X or -X.
 316       if (Div->isExact()) {
 317         if (DivOp1 == Y)
 318           return replaceInstUsesWith(I, X);
 319         return BinaryOperator::CreateNeg(X);
 320       }
 321
 322       auto RemOpc = Div->getOpcode() == Instruction::UDiv ? Instruction::URem
 323                                                           : Instruction::SRem;
 324       Value *Rem = Builder.CreateBinOp(RemOpc, X, DivOp1);
 325       if (DivOp1 == Y)
 326         return BinaryOperator::CreateSub(X, Rem);
 327       return BinaryOperator::CreateSub(Rem, X);
 328     }
 329   }
 330
 331   /// i1 mul -> i1 and.
 332   if (I.getType()->isIntOrIntVectorTy(1))
 333     return BinaryOperator::CreateAnd(Op0, Op1);
 334
 335   // X*(1 << Y) --> X << Y
 336   // (1 << Y)*X --> X << Y
 337   {
 338     Value *Y;
 339     BinaryOperator *BO = nullptr;
 340     bool ShlNSW = false;
 341     if (match(Op0, m_Shl(m_One(), m_Value(Y)))) {
 342       BO = BinaryOperator::CreateShl(Op1, Y);
 343       ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap();
 344     } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) {
 345       BO = BinaryOperator::CreateShl(Op0, Y);
 346       ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap();
 347     }
 348     if (BO) {
 349       if (I.hasNoUnsignedWrap())
 350         BO->setHasNoUnsignedWrap();
 351       if (I.hasNoSignedWrap() && ShlNSW)
 352         BO->setHasNoSignedWrap();
 353       return BO;
 354     }
 355   }
 356
 357   // (bool X) * Y --> X ? Y : 0
 358   // Y * (bool X) --> X ? Y : 0
 359   if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
 360     return SelectInst::Create(X, Op1, ConstantInt::get(I.getType(), 0));
 361   if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
 362     return SelectInst::Create(X, Op0, ConstantInt::get(I.getType(), 0));
 363
 364   // (lshr X, 31) * Y --> (ashr X, 31) & Y
 365   // Y * (lshr X, 31) --> (ashr X, 31) & Y
 366   // TODO: We are not checking one-use because the elimination of the multiply
 367   //       is better for analysis?
 368   // TODO: Should we canonicalize to '(X < 0) ? Y : 0' instead? That would be
 369   //       more similar to what we're doing above.
 370   const APInt *C;
 371   if (match(Op0, m_LShr(m_Value(X), m_APInt(C))) && *C == C->getBitWidth() - 1)
 372     return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op1);
 373   if (match(Op1, m_LShr(m_Value(X), m_APInt(C))) && *C == C->getBitWidth() - 1)
 374     return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op0);
 375
 376   if (Instruction *Ext = narrowMathIfNoOverflow(I))
 377     return Ext;
 378
 379   bool Changed = false;
 380   if (!I.hasNoSignedWrap() && willNotOverflowSignedMul(Op0, Op1, I)) {
 381     Changed = true;
 382     I.setHasNoSignedWrap(true);
 383   }
 384
 385   if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedMul(Op0, Op1, I)) {
 386     Changed = true;
 387     I.setHasNoUnsignedWrap(true);
 388   }
 389
 390   return Changed ? &I : nullptr;
 391 }
 392
 393 Instruction *InstCombiner::visitFMul(BinaryOperator &I) {
 394   if (Value *V = SimplifyFMulInst(I.getOperand(0), I.getOperand(1),
 395                                   I.getFastMathFlags(),
 396                                   SQ.getWithInstruction(&I)))
 397     return replaceInstUsesWith(I, V);
 398
 399   if (SimplifyAssociativeOrCommutative(I))
 400     return &I;
 401
 402   if (Instruction *X = foldVectorBinop(I))
 403     return X;
 404
 405   if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
 406     return FoldedMul;
 407
 408   if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
 409     return replaceInstUsesWith(I, FoldedMul);
 410
 411   // X * -1.0 --> -X
 412   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 413   if (match(Op1, m_SpecificFP(-1.0)))
 414     return BinaryOperator::CreateFNegFMF(Op0, &I);
 415
 416   // -X * -Y --> X * Y
 417   Value *X, *Y;
 418   if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y))))
 419     return BinaryOperator::CreateFMulFMF(X, Y, &I);
 420
 421   // -X * C --> X * -C
 422   Constant *C;
 423   if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_Constant(C)))
 424     return BinaryOperator::CreateFMulFMF(X, ConstantExpr::getFNeg(C), &I);
 425
 426   // fabs(X) * fabs(X) -> X * X
 427   if (Op0 == Op1 && match(Op0, m_Intrinsic<Intrinsic::fabs>(m_Value(X))))
 428     return BinaryOperator::CreateFMulFMF(X, X, &I);
 429
 430   // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E)
 431   if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
 432     return replaceInstUsesWith(I, V);
 433
 434   if (I.hasAllowReassoc()) {
 435     // Reassociate constant RHS with another constant to form constant
 436     // expression.
 437     if (match(Op1, m_Constant(C)) && C->isFiniteNonZeroFP()) {
 438       Constant *C1;
 439       if (match(Op0, m_OneUse(m_FDiv(m_Constant(C1), m_Value(X))))) {
 440         // (C1 / X) * C --> (C * C1) / X
 441         Constant *CC1 = ConstantExpr::getFMul(C, C1);
 442         if (CC1->isNormalFP())
 443           return BinaryOperator::CreateFDivFMF(CC1, X, &I);
 444       }
 445       if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
 446         // (X / C1) * C --> X * (C / C1)
 447         Constant *CDivC1 = ConstantExpr::getFDiv(C, C1);
 448         if (CDivC1->isNormalFP())
 449           return BinaryOperator::CreateFMulFMF(X, CDivC1, &I);
 450
 451         // If the constant was a denormal, try reassociating differently.
 452         // (X / C1) * C --> X / (C1 / C)
 453         Constant *C1DivC = ConstantExpr::getFDiv(C1, C);
 454         if (Op0->hasOneUse() && C1DivC->isNormalFP())
 455           return BinaryOperator::CreateFDivFMF(X, C1DivC, &I);
 456       }
 457
 458       // We do not need to match 'fadd C, X' and 'fsub X, C' because they are
 459       // canonicalized to 'fadd X, C'. Distributing the multiply may allow
 460       // further folds and (X * C) + C2 is 'fma'.
 461       if (match(Op0, m_OneUse(m_FAdd(m_Value(X), m_Constant(C1))))) {
 462         // (X + C1) * C --> (X * C) + (C * C1)
 463         Constant *CC1 = ConstantExpr::getFMul(C, C1);
 464         Value *XC = Builder.CreateFMulFMF(X, C, &I);
 465         return BinaryOperator::CreateFAddFMF(XC, CC1, &I);
 466       }
 467       if (match(Op0, m_OneUse(m_FSub(m_Constant(C1), m_Value(X))))) {
 468         // (C1 - X) * C --> (C * C1) - (X * C)
 469         Constant *CC1 = ConstantExpr::getFMul(C, C1);
 470         Value *XC = Builder.CreateFMulFMF(X, C, &I);
 471         return BinaryOperator::CreateFSubFMF(CC1, XC, &I);
 472       }
 473     }
 474
 475     Value *Z;
 476     if (match(&I, m_c_FMul(m_OneUse(m_FDiv(m_Value(X), m_Value(Y))),
 477                            m_Value(Z)))) {
 478       // Sink division: (X / Y) * Z --> (X * Z) / Y
 479       Value *NewFMul = Builder.CreateFMulFMF(X, Z, &I);
 480       return BinaryOperator::CreateFDivFMF(NewFMul, Y, &I);
 481     }
 482
 483     // sqrt(X) * sqrt(Y) -> sqrt(X * Y)
 484     // nnan disallows the possibility of returning a number if both operands are
 485     // negative (in that case, we should return NaN).
 486     if (I.hasNoNaNs() &&
 487         match(Op0, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(X)))) &&
 488         match(Op1, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) {
 489       Value *XY = Builder.CreateFMulFMF(X, Y, &I);
 490       Value *Sqrt = Builder.CreateUnaryIntrinsic(Intrinsic::sqrt, XY, &I);
 491       return replaceInstUsesWith(I, Sqrt);
 492     }
 493
 494     // Like the similar transform in instsimplify, this requires 'nsz' because
 495     // sqrt(-0.0) = -0.0, and -0.0 * -0.0 does not simplify to -0.0.
 496     if (I.hasNoNaNs() && I.hasNoSignedZeros() && Op0 == Op1 &&
 497         Op0->hasNUses(2)) {
 498       // Peek through fdiv to find squaring of square root:
 499       // (X / sqrt(Y)) * (X / sqrt(Y)) --> (X * X) / Y
 500       if (match(Op0, m_FDiv(m_Value(X),
 501                             m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) {
 502         Value *XX = Builder.CreateFMulFMF(X, X, &I);
 503         return BinaryOperator::CreateFDivFMF(XX, Y, &I);
 504       }
 505       // (sqrt(Y) / X) * (sqrt(Y) / X) --> Y / (X * X)
 506       if (match(Op0, m_FDiv(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y)),
 507                             m_Value(X)))) {
 508         Value *XX = Builder.CreateFMulFMF(X, X, &I);
 509         return BinaryOperator::CreateFDivFMF(Y, XX, &I);
 510       }
 511     }
 512
 513     // exp(X) * exp(Y) -> exp(X + Y)
 514     // Match as long as at least one of exp has only one use.
 515     if (match(Op0, m_Intrinsic<Intrinsic::exp>(m_Value(X))) &&
 516         match(Op1, m_Intrinsic<Intrinsic::exp>(m_Value(Y))) &&
 517         (Op0->hasOneUse() || Op1->hasOneUse())) {
 518       Value *XY = Builder.CreateFAddFMF(X, Y, &I);
 519       Value *Exp = Builder.CreateUnaryIntrinsic(Intrinsic::exp, XY, &I);
 520       return replaceInstUsesWith(I, Exp);
 521     }
 522
 523     // exp2(X) * exp2(Y) -> exp2(X + Y)
 524     // Match as long as at least one of exp2 has only one use.
 525     if (match(Op0, m_Intrinsic<Intrinsic::exp2>(m_Value(X))) &&
 526         match(Op1, m_Intrinsic<Intrinsic::exp2>(m_Value(Y))) &&
 527         (Op0->hasOneUse() || Op1->hasOneUse())) {
 528       Value *XY = Builder.CreateFAddFMF(X, Y, &I);
 529       Value *Exp2 = Builder.CreateUnaryIntrinsic(Intrinsic::exp2, XY, &I);
 530       return replaceInstUsesWith(I, Exp2);
 531     }
 532
 533     // (X*Y) * X => (X*X) * Y where Y != X
 534     //  The purpose is two-fold:
 535     //   1) to form a power expression (of X).
 536     //   2) potentially shorten the critical path: After transformation, the
 537     //  latency of the instruction Y is amortized by the expression of X*X,
 538     //  and therefore Y is in a "less critical" position compared to what it
 539     //  was before the transformation.
 540     if (match(Op0, m_OneUse(m_c_FMul(m_Specific(Op1), m_Value(Y)))) &&
 541         Op1 != Y) {
 542       Value *XX = Builder.CreateFMulFMF(Op1, Op1, &I);
 543       return BinaryOperator::CreateFMulFMF(XX, Y, &I);
 544     }
 545     if (match(Op1, m_OneUse(m_c_FMul(m_Specific(Op0), m_Value(Y)))) &&
 546         Op0 != Y) {
 547       Value *XX = Builder.CreateFMulFMF(Op0, Op0, &I);
 548       return BinaryOperator::CreateFMulFMF(XX, Y, &I);
 549     }
 550   }
 551
 552   // log2(X * 0.5) * Y = log2(X) * Y - Y
 553   if (I.isFast()) {
 554     IntrinsicInst *Log2 = nullptr;
 555     if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::log2>(
 556             m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
 557       Log2 = cast<IntrinsicInst>(Op0);
 558       Y = Op1;
 559     }
 560     if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::log2>(
 561             m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
 562       Log2 = cast<IntrinsicInst>(Op1);
 563       Y = Op0;
 564     }
 565     if (Log2) {
 566       Log2->setArgOperand(0, X);
 567       Log2->copyFastMathFlags(&I);
 568       Value *LogXTimesY = Builder.CreateFMulFMF(Log2, Y, &I);
 569       return BinaryOperator::CreateFSubFMF(LogXTimesY, Y, &I);
 570     }
 571   }
 572
 573   return nullptr;
 574 }
 575
 576 /// Fold a divide or remainder with a select instruction divisor when one of the
 577 /// select operands is zero. In that case, we can use the other select operand
 578 /// because div/rem by zero is undefined.
 579 bool InstCombiner::simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I) {
 580   SelectInst *SI = dyn_cast<SelectInst>(I.getOperand(1));
 581   if (!SI)
 582     return false;
 583
 584   int NonNullOperand;
 585   if (match(SI->getTrueValue(), m_Zero()))
 586     // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
 587     NonNullOperand = 2;
 588   else if (match(SI->getFalseValue(), m_Zero()))
 589     // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
 590     NonNullOperand = 1;
 591   else
 592     return false;
 593
 594   // Change the div/rem to use 'Y' instead of the select.
 595   I.setOperand(1, SI->getOperand(NonNullOperand));
 596
 597   // Okay, we know we replace the operand of the div/rem with 'Y' with no
 598   // problem.  However, the select, or the condition of the select may have
 599   // multiple uses.  Based on our knowledge that the operand must be non-zero,
 600   // propagate the known value for the select into other uses of it, and
 601   // propagate a known value of the condition into its other users.
 602
 603   // If the select and condition only have a single use, don't bother with this,
 604   // early exit.
 605   Value *SelectCond = SI->getCondition();
 606   if (SI->use_empty() && SelectCond->hasOneUse())
 607     return true;
 608
 609   // Scan the current block backward, looking for other uses of SI.
 610   BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin();
 611   Type *CondTy = SelectCond->getType();
 612   while (BBI != BBFront) {
 613     --BBI;
 614     // If we found an instruction that we can't assume will return, so
 615     // information from below it cannot be propagated above it.
 616     if (!isGuaranteedToTransferExecutionToSuccessor(&*BBI))
 617       break;
 618
 619     // Replace uses of the select or its condition with the known values.
 620     for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end();
 621          I != E; ++I) {
 622       if (*I == SI) {
 623         *I = SI->getOperand(NonNullOperand);
 624         Worklist.Add(&*BBI);
 625       } else if (*I == SelectCond) {
 626         *I = NonNullOperand == 1 ? ConstantInt::getTrue(CondTy)
 627                                  : ConstantInt::getFalse(CondTy);
 628         Worklist.Add(&*BBI);
 629       }
 630     }
 631
 632     // If we past the instruction, quit looking for it.
 633     if (&*BBI == SI)
 634       SI = nullptr;
 635     if (&*BBI == SelectCond)
 636       SelectCond = nullptr;
 637
 638     // If we ran out of things to eliminate, break out of the loop.
 639     if (!SelectCond && !SI)
 640       break;
 641
 642   }
 643   return true;
 644 }
 645
 646 /// True if the multiply can not be expressed in an int this size.
 647 static bool multiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
 648                               bool IsSigned) {
 649   bool Overflow;
 650   Product = IsSigned ? C1.smul_ov(C2, Overflow) : C1.umul_ov(C2, Overflow);
 651   return Overflow;
 652 }
 653
 654 /// True if C1 is a multiple of C2. Quotient contains C1/C2.
 655 static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
 656                        bool IsSigned) {
 657   assert(C1.getBitWidth() == C2.getBitWidth() && "Constant widths not equal");
 658
 659   // Bail if we will divide by zero.
 660   if (C2.isNullValue())
 661     return false;
 662
 663   // Bail if we would divide INT_MIN by -1.
 664   if (IsSigned && C1.isMinSignedValue() && C2.isAllOnesValue())
 665     return false;
 666
 667   APInt Remainder(C1.getBitWidth(), /*val=*/0ULL, IsSigned);
 668   if (IsSigned)
 669     APInt::sdivrem(C1, C2, Quotient, Remainder);
 670   else
 671     APInt::udivrem(C1, C2, Quotient, Remainder);
 672
 673   return Remainder.isMinValue();
 674 }
 675
 676 /// This function implements the transforms common to both integer division
 677 /// instructions (udiv and sdiv). It is called by the visitors to those integer
 678 /// division instructions.
 679 /// Common integer divide transforms
 680 Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
 681   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 682   bool IsSigned = I.getOpcode() == Instruction::SDiv;
 683   Type *Ty = I.getType();
 684
 685   // The RHS is known non-zero.
 686   if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
 687     I.setOperand(1, V);
 688     return &I;
 689   }
 690
 691   // Handle cases involving: [su]div X, (select Cond, Y, Z)
 692   // This does not apply for fdiv.
 693   if (simplifyDivRemOfSelectWithZeroOp(I))
 694     return &I;
 695
 696   const APInt *C2;
 697   if (match(Op1, m_APInt(C2))) {
 698     Value *X;
 699     const APInt *C1;
 700
 701     // (X / C1) / C2  -> X / (C1*C2)
 702     if ((IsSigned && match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))) ||
 703         (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_APInt(C1))))) {
 704       APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
 705       if (!multiplyOverflows(*C1, *C2, Product, IsSigned))
 706         return BinaryOperator::Create(I.getOpcode(), X,
 707                                       ConstantInt::get(Ty, Product));
 708     }
 709
 710     if ((IsSigned && match(Op0, m_NSWMul(m_Value(X), m_APInt(C1)))) ||
 711         (!IsSigned && match(Op0, m_NUWMul(m_Value(X), m_APInt(C1))))) {
 712       APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
 713
 714       // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
 715       if (isMultiple(*C2, *C1, Quotient, IsSigned)) {
 716         auto *NewDiv = BinaryOperator::Create(I.getOpcode(), X,
 717                                               ConstantInt::get(Ty, Quotient));
 718         NewDiv->setIsExact(I.isExact());
 719         return NewDiv;
 720       }
 721
 722       // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
 723       if (isMultiple(*C1, *C2, Quotient, IsSigned)) {
 724         auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
 725                                            ConstantInt::get(Ty, Quotient));
 726         auto *OBO = cast<OverflowingBinaryOperator>(Op0);
 727         Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
 728         Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
 729         return Mul;
 730       }
 731     }
 732
 733     if ((IsSigned && match(Op0, m_NSWShl(m_Value(X), m_APInt(C1))) &&
 734          *C1 != C1->getBitWidth() - 1) ||
 735         (!IsSigned && match(Op0, m_NUWShl(m_Value(X), m_APInt(C1))))) {
 736       APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
 737       APInt C1Shifted = APInt::getOneBitSet(
 738           C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue()));
 739
 740       // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of 1 << C1.
 741       if (isMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
 742         auto *BO = BinaryOperator::Create(I.getOpcode(), X,
 743                                           ConstantInt::get(Ty, Quotient));
 744         BO->setIsExact(I.isExact());
 745         return BO;
 746       }
 747
 748       // (X << C1) / C2 -> X * ((1 << C1) / C2) if 1 << C1 is a multiple of C2.
 749       if (isMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
 750         auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
 751                                            ConstantInt::get(Ty, Quotient));
 752         auto *OBO = cast<OverflowingBinaryOperator>(Op0);
 753         Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
 754         Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
 755         return Mul;
 756       }
 757     }
 758
 759     if (!C2->isNullValue()) // avoid X udiv 0
 760       if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I))
 761         return FoldedDiv;
 762   }
 763
 764   if (match(Op0, m_One())) {
 765     assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?");
 766     if (IsSigned) {
 767       // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the
 768       // result is one, if Op1 is -1 then the result is minus one, otherwise
 769       // it's zero.
 770       Value *Inc = Builder.CreateAdd(Op1, Op0);
 771       Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(Ty, 3));
 772       return SelectInst::Create(Cmp, Op1, ConstantInt::get(Ty, 0));
 773     } else {
 774       // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
 775       // result is one, otherwise it's zero.
 776       return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), Ty);
 777     }
 778   }
 779
 780   // See if we can fold away this div instruction.
 781   if (SimplifyDemandedInstructionBits(I))
 782     return &I;
 783
 784   // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
 785   Value *X, *Z;
 786   if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) // (X - Z) / Y; Y = Op1
 787     if ((IsSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
 788         (!IsSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
 789       return BinaryOperator::Create(I.getOpcode(), X, Op1);
 790
 791   // (X << Y) / X -> 1 << Y
 792   Value *Y;
 793   if (IsSigned && match(Op0, m_NSWShl(m_Specific(Op1), m_Value(Y))))
 794     return BinaryOperator::CreateNSWShl(ConstantInt::get(Ty, 1), Y);
 795   if (!IsSigned && match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y))))
 796     return BinaryOperator::CreateNUWShl(ConstantInt::get(Ty, 1), Y);
 797
 798   // X / (X * Y) -> 1 / Y if the multiplication does not overflow.
 799   if (match(Op1, m_c_Mul(m_Specific(Op0), m_Value(Y)))) {
 800     bool HasNSW = cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap();
 801     bool HasNUW = cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap();
 802     if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) {
 803       I.setOperand(0, ConstantInt::get(Ty, 1));
 804       I.setOperand(1, Y);
 805       return &I;
 806     }
 807   }
 808
 809   return nullptr;
 810 }
 811
 812 static const unsigned MaxDepth = 6;
 813
 814 namespace {
 815
 816 using FoldUDivOperandCb = Instruction *(*)(Value *Op0, Value *Op1,
 817                                            const BinaryOperator &I,
 818                                            InstCombiner &IC);
 819
 820 /// Used to maintain state for visitUDivOperand().
 821 struct UDivFoldAction {
 822   /// Informs visitUDiv() how to fold this operand.  This can be zero if this
 823   /// action joins two actions together.
 824   FoldUDivOperandCb FoldAction;
 825
 826   /// Which operand to fold.
 827   Value *OperandToFold;
 828
 829   union {
 830     /// The instruction returned when FoldAction is invoked.
 831     Instruction *FoldResult;
 832
 833     /// Stores the LHS action index if this action joins two actions together.
 834     size_t SelectLHSIdx;
 835   };
 836
 837   UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
 838       : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
 839   UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
 840       : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
 841 };
 842
 843 } // end anonymous namespace
 844
 845 // X udiv 2^C -> X >> C
 846 static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1,
 847                                     const BinaryOperator &I, InstCombiner &IC) {
 848   Constant *C1 = getLogBase2(Op0->getType(), cast<Constant>(Op1));
 849   if (!C1)
 850     llvm_unreachable("Failed to constant fold udiv -> logbase2");
 851   BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, C1);
 852   if (I.isExact())
 853     LShr->setIsExact();
 854   return LShr;
 855 }
 856
 857 // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
 858 // X udiv (zext (C1 << N)), where C1 is "1<<C2"  -->  X >> (N+C2)
 859 static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
 860                                 InstCombiner &IC) {
 861   Value *ShiftLeft;
 862   if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
 863     ShiftLeft = Op1;
 864
 865   Constant *CI;
 866   Value *N;
 867   if (!match(ShiftLeft, m_Shl(m_Constant(CI), m_Value(N))))
 868     llvm_unreachable("match should never fail here!");
 869   Constant *Log2Base = getLogBase2(N->getType(), CI);
 870   if (!Log2Base)
 871     llvm_unreachable("getLogBase2 should never fail here!");
 872   N = IC.Builder.CreateAdd(N, Log2Base);
 873   if (Op1 != ShiftLeft)
 874     N = IC.Builder.CreateZExt(N, Op1->getType());
 875   BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
 876   if (I.isExact())
 877     LShr->setIsExact();
 878   return LShr;
 879 }
 880
 881 // Recursively visits the possible right hand operands of a udiv
 882 // instruction, seeing through select instructions, to determine if we can
 883 // replace the udiv with something simpler.  If we find that an operand is not
 884 // able to simplify the udiv, we abort the entire transformation.
 885 static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
 886                                SmallVectorImpl<UDivFoldAction> &Actions,
 887                                unsigned Depth = 0) {
 888   // Check to see if this is an unsigned division with an exact power of 2,
 889   // if so, convert to a right shift.
 890   if (match(Op1, m_Power2())) {
 891     Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1));
 892     return Actions.size();
 893   }
 894
 895   // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
 896   if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
 897       match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
 898     Actions.push_back(UDivFoldAction(foldUDivShl, Op1));
 899     return Actions.size();
 900   }
 901
 902   // The remaining tests are all recursive, so bail out if we hit the limit.
 903   if (Depth++ == MaxDepth)
 904     return 0;
 905
 906   if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
 907     if (size_t LHSIdx =
 908             visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth))
 909       if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) {
 910         Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1));
 911         return Actions.size();
 912       }
 913
 914   return 0;
 915 }
 916
 917 /// If we have zero-extended operands of an unsigned div or rem, we may be able
 918 /// to narrow the operation (sink the zext below the math).
 919 static Instruction *narrowUDivURem(BinaryOperator &I,
 920                                    InstCombiner::BuilderTy &Builder) {
 921   Instruction::BinaryOps Opcode = I.getOpcode();
 922   Value *N = I.getOperand(0);
 923   Value *D = I.getOperand(1);
 924   Type *Ty = I.getType();
 925   Value *X, *Y;
 926   if (match(N, m_ZExt(m_Value(X))) && match(D, m_ZExt(m_Value(Y))) &&
 927       X->getType() == Y->getType() && (N->hasOneUse() || D->hasOneUse())) {
 928     // udiv (zext X), (zext Y) --> zext (udiv X, Y)
 929     // urem (zext X), (zext Y) --> zext (urem X, Y)
 930     Value *NarrowOp = Builder.CreateBinOp(Opcode, X, Y);
 931     return new ZExtInst(NarrowOp, Ty);
 932   }
 933
 934   Constant *C;
 935   if ((match(N, m_OneUse(m_ZExt(m_Value(X)))) && match(D, m_Constant(C))) ||
 936       (match(D, m_OneUse(m_ZExt(m_Value(X)))) && match(N, m_Constant(C)))) {
 937     // If the constant is the same in the smaller type, use the narrow version.
 938     Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
 939     if (ConstantExpr::getZExt(TruncC, Ty) != C)
 940       return nullptr;
 941
 942     // udiv (zext X), C --> zext (udiv X, C')
 943     // urem (zext X), C --> zext (urem X, C')
 944     // udiv C, (zext X) --> zext (udiv C', X)
 945     // urem C, (zext X) --> zext (urem C', X)
 946     Value *NarrowOp = isa<Constant>(D) ? Builder.CreateBinOp(Opcode, X, TruncC)
 947                                        : Builder.CreateBinOp(Opcode, TruncC, X);
 948     return new ZExtInst(NarrowOp, Ty);
 949   }
 950
 951   return nullptr;
 952 }
 953
 954 Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
 955   if (Value *V = SimplifyUDivInst(I.getOperand(0), I.getOperand(1),
 956                                   SQ.getWithInstruction(&I)))
 957     return replaceInstUsesWith(I, V);
 958
 959   if (Instruction *X = foldVectorBinop(I))
 960     return X;
 961
 962   // Handle the integer div common cases
 963   if (Instruction *Common = commonIDivTransforms(I))
 964     return Common;
 965
 966   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 967   Value *X;
 968   const APInt *C1, *C2;
 969   if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && match(Op1, m_APInt(C2))) {
 970     // (X lshr C1) udiv C2 --> X udiv (C2 << C1)
 971     bool Overflow;
 972     APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
 973     if (!Overflow) {
 974       bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value()));
 975       BinaryOperator *BO = BinaryOperator::CreateUDiv(
 976           X, ConstantInt::get(X->getType(), C2ShlC1));
 977       if (IsExact)
 978         BO->setIsExact();
 979       return BO;
 980     }
 981   }
 982
 983   // Op0 / C where C is large (negative) --> zext (Op0 >= C)
 984   // TODO: Could use isKnownNegative() to handle non-constant values.
 985   Type *Ty = I.getType();
 986   if (match(Op1, m_Negative())) {
 987     Value *Cmp = Builder.CreateICmpUGE(Op0, Op1);
 988     return CastInst::CreateZExtOrBitCast(Cmp, Ty);
 989   }
 990   // Op0 / (sext i1 X) --> zext (Op0 == -1) (if X is 0, the div is undefined)
 991   if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
 992     Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
 993     return CastInst::CreateZExtOrBitCast(Cmp, Ty);
 994   }
 995
 996   if (Instruction *NarrowDiv = narrowUDivURem(I, Builder))
 997     return NarrowDiv;
 998
 999   // If the udiv operands are non-overflowing multiplies with a common operand,
1000   // then eliminate the common factor:
1001   // (A * B) / (A * X) --> B / X (and commuted variants)
1002   // TODO: The code would be reduced if we had m_c_NUWMul pattern matching.
1003   // TODO: If -reassociation handled this generally, we could remove this.
1004   Value *A, *B;
1005   if (match(Op0, m_NUWMul(m_Value(A), m_Value(B)))) {
1006     if (match(Op1, m_NUWMul(m_Specific(A), m_Value(X))) ||
1007         match(Op1, m_NUWMul(m_Value(X), m_Specific(A))))
1008       return BinaryOperator::CreateUDiv(B, X);
1009     if (match(Op1, m_NUWMul(m_Specific(B), m_Value(X))) ||
1010         match(Op1, m_NUWMul(m_Value(X), m_Specific(B))))
1011       return BinaryOperator::CreateUDiv(A, X);
1012   }
1013
1014   // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
1015   SmallVector<UDivFoldAction, 6> UDivActions;
1016   if (visitUDivOperand(Op0, Op1, I, UDivActions))
1017     for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) {
1018       FoldUDivOperandCb Action = UDivActions[i].FoldAction;
1019       Value *ActionOp1 = UDivActions[i].OperandToFold;
1020       Instruction *Inst;
1021       if (Action)
1022         Inst = Action(Op0, ActionOp1, I, *this);
1023       else {
1024         // This action joins two actions together.  The RHS of this action is
1025         // simply the last action we processed, we saved the LHS action index in
1026         // the joining action.
1027         size_t SelectRHSIdx = i - 1;
1028         Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult;
1029         size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx;
1030         Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult;
1031         Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
1032                                   SelectLHS, SelectRHS);
1033       }
1034
1035       // If this is the last action to process, return it to the InstCombiner.
1036       // Otherwise, we insert it before the UDiv and record it so that we may
1037       // use it as part of a joining action (i.e., a SelectInst).
1038       if (e - i != 1) {
1039         Inst->insertBefore(&I);
1040         UDivActions[i].FoldResult = Inst;
1041       } else
1042         return Inst;
1043     }
1044
1045   return nullptr;
1046 }
1047
1048 Instruction *InstCombiner::visitSDiv(BinaryOperator &I) {
1049   if (Value *V = SimplifySDivInst(I.getOperand(0), I.getOperand(1),
1050                                   SQ.getWithInstruction(&I)))
1051     return replaceInstUsesWith(I, V);
1052
1053   if (Instruction *X = foldVectorBinop(I))
1054     return X;
1055
1056   // Handle the integer div common cases
1057   if (Instruction *Common = commonIDivTransforms(I))
1058     return Common;
1059
1060   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1061   Value *X;
1062   // sdiv Op0, -1 --> -Op0
1063   // sdiv Op0, (sext i1 X) --> -Op0 (because if X is 0, the op is undefined)
1064   if (match(Op1, m_AllOnes()) ||
1065       (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1066     return BinaryOperator::CreateNeg(Op0);
1067
1068   // X / INT_MIN --> X == INT_MIN
1069   if (match(Op1, m_SignMask()))
1070     return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), I.getType());
1071
1072   const APInt *Op1C;
1073   if (match(Op1, m_APInt(Op1C))) {
1074     // sdiv exact X, C  -->  ashr exact X, log2(C)
1075     if (I.isExact() && Op1C->isNonNegative() && Op1C->isPowerOf2()) {
1076       Value *ShAmt = ConstantInt::get(Op1->getType(), Op1C->exactLogBase2());
1077       return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName());
1078     }
1079
1080     // If the dividend is sign-extended and the constant divisor is small enough
1081     // to fit in the source type, shrink the division to the narrower type:
1082     // (sext X) sdiv C --> sext (X sdiv C)
1083     Value *Op0Src;
1084     if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
1085         Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) {
1086
1087       // In the general case, we need to make sure that the dividend is not the
1088       // minimum signed value because dividing that by -1 is UB. But here, we
1089       // know that the -1 divisor case is already handled above.
1090
1091       Constant *NarrowDivisor =
1092           ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
1093       Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
1094       return new SExtInst(NarrowOp, Op0->getType());
1095     }
1096
1097     // -X / C --> X / -C (if the negation doesn't overflow).
1098     // TODO: This could be enhanced to handle arbitrary vector constants by
1099     //       checking if all elements are not the min-signed-val.
1100     if (!Op1C->isMinSignedValue() &&
1101         match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1102       Constant *NegC = ConstantInt::get(I.getType(), -(*Op1C));
1103       Instruction *BO = BinaryOperator::CreateSDiv(X, NegC);
1104       BO->setIsExact(I.isExact());
1105       return BO;
1106     }
1107   }
1108
1109   // -X / Y --> -(X / Y)
1110   Value *Y;
1111   if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1112     return BinaryOperator::CreateNSWNeg(
1113         Builder.CreateSDiv(X, Y, I.getName(), I.isExact()));
1114
1115   // If the sign bits of both operands are zero (i.e. we can prove they are
1116   // unsigned inputs), turn this into a udiv.
1117   APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
1118   if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
1119     if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
1120       // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
1121       auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1122       BO->setIsExact(I.isExact());
1123       return BO;
1124     }
1125
1126     if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1127       // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1128       // Safe because the only negative value (1 << Y) can take on is
1129       // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1130       // the sign bit set.
1131       auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1132       BO->setIsExact(I.isExact());
1133       return BO;
1134     }
1135   }
1136
1137   return nullptr;
1138 }
1139
1140 /// Remove negation and try to convert division into multiplication.
1141 static Instruction *foldFDivConstantDivisor(BinaryOperator &I) {
1142   Constant *C;
1143   if (!match(I.getOperand(1), m_Constant(C)))
1144     return nullptr;
1145
1146   // -X / C --> X / -C
1147   Value *X;
1148   if (match(I.getOperand(0), m_FNeg(m_Value(X))))
1149     return BinaryOperator::CreateFDivFMF(X, ConstantExpr::getFNeg(C), &I);
1150
1151   // If the constant divisor has an exact inverse, this is always safe. If not,
1152   // then we can still create a reciprocal if fast-math-flags allow it and the
1153   // constant is a regular number (not zero, infinite, or denormal).
1154   if (!(C->hasExactInverseFP() || (I.hasAllowReciprocal() && C->isNormalFP())))
1155     return nullptr;
1156
1157   // Disallow denormal constants because we don't know what would happen
1158   // on all targets.
1159   // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1160   // denorms are flushed?
1161   auto *RecipC = ConstantExpr::getFDiv(ConstantFP::get(I.getType(), 1.0), C);
1162   if (!RecipC->isNormalFP())
1163     return nullptr;
1164
1165   // X / C --> X * (1 / C)
1166   return BinaryOperator::CreateFMulFMF(I.getOperand(0), RecipC, &I);
1167 }
1168
1169 /// Remove negation and try to reassociate constant math.
1170 static Instruction *foldFDivConstantDividend(BinaryOperator &I) {
1171   Constant *C;
1172   if (!match(I.getOperand(0), m_Constant(C)))
1173     return nullptr;
1174
1175   // C / -X --> -C / X
1176   Value *X;
1177   if (match(I.getOperand(1), m_FNeg(m_Value(X))))
1178     return BinaryOperator::CreateFDivFMF(ConstantExpr::getFNeg(C), X, &I);
1179
1180   if (!I.hasAllowReassoc() || !I.hasAllowReciprocal())
1181     return nullptr;
1182
1183   // Try to reassociate C / X expressions where X includes another constant.
1184   Constant *C2, *NewC = nullptr;
1185   if (match(I.getOperand(1), m_FMul(m_Value(X), m_Constant(C2)))) {
1186     // C / (X * C2) --> (C / C2) / X
1187     NewC = ConstantExpr::getFDiv(C, C2);
1188   } else if (match(I.getOperand(1), m_FDiv(m_Value(X), m_Constant(C2)))) {
1189     // C / (X / C2) --> (C * C2) / X
1190     NewC = ConstantExpr::getFMul(C, C2);
1191   }
1192   // Disallow denormal constants because we don't know what would happen
1193   // on all targets.
1194   // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1195   // denorms are flushed?
1196   if (!NewC || !NewC->isNormalFP())
1197     return nullptr;
1198
1199   return BinaryOperator::CreateFDivFMF(NewC, X, &I);
1200 }
1201
1202 Instruction *InstCombiner::visitFDiv(BinaryOperator &I) {
1203   if (Value *V = SimplifyFDivInst(I.getOperand(0), I.getOperand(1),
1204                                   I.getFastMathFlags(),
1205                                   SQ.getWithInstruction(&I)))
1206     return replaceInstUsesWith(I, V);
1207
1208   if (Instruction *X = foldVectorBinop(I))
1209     return X;
1210
1211   if (Instruction *R = foldFDivConstantDivisor(I))
1212     return R;
1213
1214   if (Instruction *R = foldFDivConstantDividend(I))
1215     return R;
1216
1217   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1218   if (isa<Constant>(Op0))
1219     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1220       if (Instruction *R = FoldOpIntoSelect(I, SI))
1221         return R;
1222
1223   if (isa<Constant>(Op1))
1224     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1225       if (Instruction *R = FoldOpIntoSelect(I, SI))
1226         return R;
1227
1228   if (I.hasAllowReassoc() && I.hasAllowReciprocal()) {
1229     Value *X, *Y;
1230     if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1231         (!isa<Constant>(Y) || !isa<Constant>(Op1))) {
1232       // (X / Y) / Z => X / (Y * Z)
1233       Value *YZ = Builder.CreateFMulFMF(Y, Op1, &I);
1234       return BinaryOperator::CreateFDivFMF(X, YZ, &I);
1235     }
1236     if (match(Op1, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1237         (!isa<Constant>(Y) || !isa<Constant>(Op0))) {
1238       // Z / (X / Y) => (Y * Z) / X
1239       Value *YZ = Builder.CreateFMulFMF(Y, Op0, &I);
1240       return BinaryOperator::CreateFDivFMF(YZ, X, &I);
1241     }
1242   }
1243
1244   if (I.hasAllowReassoc() && Op0->hasOneUse() && Op1->hasOneUse()) {
1245     // sin(X) / cos(X) -> tan(X)
1246     // cos(X) / sin(X) -> 1/tan(X) (cotangent)
1247     Value *X;
1248     bool IsTan = match(Op0, m_Intrinsic<Intrinsic::sin>(m_Value(X))) &&
1249                  match(Op1, m_Intrinsic<Intrinsic::cos>(m_Specific(X)));
1250     bool IsCot =
1251         !IsTan && match(Op0, m_Intrinsic<Intrinsic::cos>(m_Value(X))) &&
1252                   match(Op1, m_Intrinsic<Intrinsic::sin>(m_Specific(X)));
1253
1254     if ((IsTan || IsCot) &&
1255         hasFloatFn(&TLI, I.getType(), LibFunc_tan, LibFunc_tanf, LibFunc_tanl)) {
1256       IRBuilder<> B(&I);
1257       IRBuilder<>::FastMathFlagGuard FMFGuard(B);
1258       B.setFastMathFlags(I.getFastMathFlags());
1259       AttributeList Attrs =
1260           cast<CallBase>(Op0)->getCalledFunction()->getAttributes();
1261       Value *Res = emitUnaryFloatFnCall(X, &TLI, LibFunc_tan, LibFunc_tanf,
1262                                         LibFunc_tanl, B, Attrs);
1263       if (IsCot)
1264         Res = B.CreateFDiv(ConstantFP::get(I.getType(), 1.0), Res);
1265       return replaceInstUsesWith(I, Res);
1266     }
1267   }
1268
1269   // -X / -Y -> X / Y
1270   Value *X, *Y;
1271   if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y)))) {
1272     I.setOperand(0, X);
1273     I.setOperand(1, Y);
1274     return &I;
1275   }
1276
1277   // X / (X * Y) --> 1.0 / Y
1278   // Reassociate to (X / X -> 1.0) is legal when NaNs are not allowed.
1279   // We can ignore the possibility that X is infinity because INF/INF is NaN.
1280   if (I.hasNoNaNs() && I.hasAllowReassoc() &&
1281       match(Op1, m_c_FMul(m_Specific(Op0), m_Value(Y)))) {
1282     I.setOperand(0, ConstantFP::get(I.getType(), 1.0));
1283     I.setOperand(1, Y);
1284     return &I;
1285   }
1286
1287   // X / fabs(X) -> copysign(1.0, X)
1288   // fabs(X) / X -> copysign(1.0, X)
1289   if (I.hasNoNaNs() && I.hasNoInfs() &&
1290       (match(&I,
1291              m_FDiv(m_Value(X), m_Intrinsic<Intrinsic::fabs>(m_Deferred(X)))) ||
1292        match(&I, m_FDiv(m_Intrinsic<Intrinsic::fabs>(m_Value(X)),
1293                         m_Deferred(X))))) {
1294     Value *V = Builder.CreateBinaryIntrinsic(
1295         Intrinsic::copysign, ConstantFP::get(I.getType(), 1.0), X, &I);
1296     return replaceInstUsesWith(I, V);
1297   }
1298   return nullptr;
1299 }
1300
1301 /// This function implements the transforms common to both integer remainder
1302 /// instructions (urem and srem). It is called by the visitors to those integer
1303 /// remainder instructions.
1304 /// Common integer remainder transforms
1305 Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) {
1306   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1307
1308   // The RHS is known non-zero.
1309   if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
1310     I.setOperand(1, V);
1311     return &I;
1312   }
1313
1314   // Handle cases involving: rem X, (select Cond, Y, Z)
1315   if (simplifyDivRemOfSelectWithZeroOp(I))
1316     return &I;
1317
1318   if (isa<Constant>(Op1)) {
1319     if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1320       if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1321         if (Instruction *R = FoldOpIntoSelect(I, SI))
1322           return R;
1323       } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
1324         const APInt *Op1Int;
1325         if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
1326             (I.getOpcode() == Instruction::URem ||
1327              !Op1Int->isMinSignedValue())) {
1328           // foldOpIntoPhi will speculate instructions to the end of the PHI's
1329           // predecessor blocks, so do this only if we know the srem or urem
1330           // will not fault.
1331           if (Instruction *NV = foldOpIntoPhi(I, PN))
1332             return NV;
1333         }
1334       }
1335
1336       // See if we can fold away this rem instruction.
1337       if (SimplifyDemandedInstructionBits(I))
1338         return &I;
1339     }
1340   }
1341
1342   return nullptr;
1343 }
1344
1345 Instruction *InstCombiner::visitURem(BinaryOperator &I) {
1346   if (Value *V = SimplifyURemInst(I.getOperand(0), I.getOperand(1),
1347                                   SQ.getWithInstruction(&I)))
1348     return replaceInstUsesWith(I, V);
1349
1350   if (Instruction *X = foldVectorBinop(I))
1351     return X;
1352
1353   if (Instruction *common = commonIRemTransforms(I))
1354     return common;
1355
1356   if (Instruction *NarrowRem = narrowUDivURem(I, Builder))
1357     return NarrowRem;
1358
1359   // X urem Y -> X and Y-1, where Y is a power of 2,
1360   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1361   Type *Ty = I.getType();
1362   if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1363     // This may increase instruction count, we don't enforce that Y is a
1364     // constant.
1365     Constant *N1 = Constant::getAllOnesValue(Ty);
1366     Value *Add = Builder.CreateAdd(Op1, N1);
1367     return BinaryOperator::CreateAnd(Op0, Add);
1368   }
1369
1370   // 1 urem X -> zext(X != 1)
1371   if (match(Op0, m_One()))
1372     return CastInst::CreateZExtOrBitCast(Builder.CreateICmpNE(Op1, Op0), Ty);
1373
1374   // X urem C -> X < C ? X : X - C, where C >= signbit.
1375   if (match(Op1, m_Negative())) {
1376     Value *Cmp = Builder.CreateICmpULT(Op0, Op1);
1377     Value *Sub = Builder.CreateSub(Op0, Op1);
1378     return SelectInst::Create(Cmp, Op0, Sub);
1379   }
1380
1381   // If the divisor is a sext of a boolean, then the divisor must be max
1382   // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also
1383   // max unsigned value. In that case, the remainder is 0:
1384   // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0
1385   Value *X;
1386   if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1387     Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1388     return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), Op0);
1389   }
1390
1391   return nullptr;
1392 }
1393
1394 Instruction *InstCombiner::visitSRem(BinaryOperator &I) {
1395   if (Value *V = SimplifySRemInst(I.getOperand(0), I.getOperand(1),
1396                                   SQ.getWithInstruction(&I)))
1397     return replaceInstUsesWith(I, V);
1398
1399   if (Instruction *X = foldVectorBinop(I))
1400     return X;
1401
1402   // Handle the integer rem common cases
1403   if (Instruction *Common = commonIRemTransforms(I))
1404     return Common;
1405
1406   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1407   {
1408     const APInt *Y;
1409     // X % -Y -> X % Y
1410     if (match(Op1, m_Negative(Y)) && !Y->isMinSignedValue()) {
1411       Worklist.AddValue(I.getOperand(1));
1412       I.setOperand(1, ConstantInt::get(I.getType(), -*Y));
1413       return &I;
1414     }
1415   }
1416
1417   // -X srem Y --> -(X srem Y)
1418   Value *X, *Y;
1419   if (match(&I, m_SRem(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1420     return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y));
1421
1422   // If the sign bits of both operands are zero (i.e. we can prove they are
1423   // unsigned inputs), turn this into a urem.
1424   APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
1425   if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1426       MaskedValueIsZero(Op0, Mask, 0, &I)) {
1427     // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1428     return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1429   }
1430
1431   // If it's a constant vector, flip any negative values positive.
1432   if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1433     Constant *C = cast<Constant>(Op1);
1434     unsigned VWidth = C->getType()->getVectorNumElements();
1435
1436     bool hasNegative = false;
1437     bool hasMissing = false;
1438     for (unsigned i = 0; i != VWidth; ++i) {
1439       Constant *Elt = C->getAggregateElement(i);
1440       if (!Elt) {
1441         hasMissing = true;
1442         break;
1443       }
1444
1445       if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1446         if (RHS->isNegative())
1447           hasNegative = true;
1448     }
1449
1450     if (hasNegative && !hasMissing) {
1451       SmallVector<Constant *, 16> Elts(VWidth);
1452       for (unsigned i = 0; i != VWidth; ++i) {
1453         Elts[i] = C->getAggregateElement(i);  // Handle undef, etc.
1454         if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1455           if (RHS->isNegative())
1456             Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1457         }
1458       }
1459
1460       Constant *NewRHSV = ConstantVector::get(Elts);
1461       if (NewRHSV != C) {  // Don't loop on -MININT
1462         Worklist.AddValue(I.getOperand(1));
1463         I.setOperand(1, NewRHSV);
1464         return &I;
1465       }
1466     }
1467   }
1468
1469   return nullptr;
1470 }
1471
1472 Instruction *InstCombiner::visitFRem(BinaryOperator &I) {
1473   if (Value *V = SimplifyFRemInst(I.getOperand(0), I.getOperand(1),
1474                                   I.getFastMathFlags(),
1475                                   SQ.getWithInstruction(&I)))
1476     return replaceInstUsesWith(I, V);
1477
1478   if (Instruction *X = foldVectorBinop(I))
1479     return X;
1480
1481   return nullptr;
1482 }