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