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/IntrinsicInst.h"
  17 #include "llvm/Analysis/InstructionSimplify.h"
  18 #include "llvm/Support/PatternMatch.h"
  19 using namespace llvm;
  20 using namespace PatternMatch;
  21
  22
  23 /// simplifyValueKnownNonZero - The specific integer value is used in a context
  24 /// where it is known to be non-zero.  If this allows us to simplify the
  25 /// computation, do so and return the new operand, otherwise return null.
  26 static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC) {
  27   // If V has multiple uses, then we would have to do more analysis to determine
  28   // if this is safe.  For example, the use could be in dynamically unreached
  29   // code.
  30   if (!V->hasOneUse()) return 0;
  31
  32   // ((1 << A) >>u B) --> (1 << (A-B))
  33   // Because V cannot be zero, we know that B is less than A.
  34   Value *A = 0, *B = 0, *PowerOf2 = 0;
  35   if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(PowerOf2), m_Value(A))),
  36                       m_Value(B))) &&
  37       // The "1" can be any value known to be a power of 2.
  38       isPowerOfTwo(PowerOf2, IC.getTargetData())) {
  39     A = IC.Builder->CreateSub(A, B, "tmp");
  40     return IC.Builder->CreateShl(PowerOf2, A);
  41   }
  42
  43   // TODO: Lots more we could do here:
  44   //    "1 >> X" could get an "isexact" bit.
  45   //    If V is a phi node, we can call this on each of its operands.
  46   //    "select cond, X, 0" can simplify to "X".
  47
  48   return 0;
  49 }
  50
  51
  52 /// MultiplyOverflows - True if the multiply can not be expressed in an int
  53 /// this size.
  54 static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) {
  55   uint32_t W = C1->getBitWidth();
  56   APInt LHSExt = C1->getValue(), RHSExt = C2->getValue();
  57   if (sign) {
  58     LHSExt = LHSExt.sext(W * 2);
  59     RHSExt = RHSExt.sext(W * 2);
  60   } else {
  61     LHSExt = LHSExt.zext(W * 2);
  62     RHSExt = RHSExt.zext(W * 2);
  63   }
  64
  65   APInt MulExt = LHSExt * RHSExt;
  66
  67   if (!sign)
  68     return MulExt.ugt(APInt::getLowBitsSet(W * 2, W));
  69
  70   APInt Min = APInt::getSignedMinValue(W).sext(W * 2);
  71   APInt Max = APInt::getSignedMaxValue(W).sext(W * 2);
  72   return MulExt.slt(Min) || MulExt.sgt(Max);
  73 }
  74
  75 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
  76   bool Changed = SimplifyAssociativeOrCommutative(I);
  77   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
  78
  79   if (Value *V = SimplifyMulInst(Op0, Op1, TD))
  80     return ReplaceInstUsesWith(I, V);
  81
  82   if (Value *V = SimplifyUsingDistributiveLaws(I))
  83     return ReplaceInstUsesWith(I, V);
  84
  85   if (match(Op1, m_AllOnes()))  // X * -1 == 0 - X
  86     return BinaryOperator::CreateNeg(Op0, I.getName());
  87
  88   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
  89
  90     // ((X << C1)*C2) == (X * (C2 << C1))
  91     if (BinaryOperator *SI = dyn_cast<BinaryOperator>(Op0))
  92       if (SI->getOpcode() == Instruction::Shl)
  93         if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1)))
  94           return BinaryOperator::CreateMul(SI->getOperand(0),
  95                                            ConstantExpr::getShl(CI, ShOp));
  96
  97     const APInt &Val = CI->getValue();
  98     if (Val.isPowerOf2()) {          // Replace X*(2^C) with X << C
  99       Constant *NewCst = ConstantInt::get(Op0->getType(), Val.logBase2());
 100       BinaryOperator *Shl = BinaryOperator::CreateShl(Op0, NewCst);
 101       if (I.hasNoSignedWrap()) Shl->setHasNoSignedWrap();
 102       if (I.hasNoUnsignedWrap()) Shl->setHasNoUnsignedWrap();
 103       return Shl;
 104     }
 105
 106     // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
 107     { Value *X; ConstantInt *C1;
 108       if (Op0->hasOneUse() &&
 109           match(Op0, m_Add(m_Value(X), m_ConstantInt(C1)))) {
 110         Value *Add = Builder->CreateMul(X, CI, "tmp");
 111         return BinaryOperator::CreateAdd(Add, Builder->CreateMul(C1, CI));
 112       }
 113     }
 114   }
 115
 116   // Simplify mul instructions with a constant RHS.
 117   if (isa<Constant>(Op1)) {
 118     // Try to fold constant mul into select arguments.
 119     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
 120       if (Instruction *R = FoldOpIntoSelect(I, SI))
 121         return R;
 122
 123     if (isa<PHINode>(Op0))
 124       if (Instruction *NV = FoldOpIntoPhi(I))
 125         return NV;
 126   }
 127
 128   if (Value *Op0v = dyn_castNegVal(Op0))     // -X * -Y = X*Y
 129     if (Value *Op1v = dyn_castNegVal(Op1))
 130       return BinaryOperator::CreateMul(Op0v, Op1v);
 131
 132   // (X / Y) *  Y = X - (X % Y)
 133   // (X / Y) * -Y = (X % Y) - X
 134   {
 135     Value *Op1C = Op1;
 136     BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0);
 137     if (!BO ||
 138         (BO->getOpcode() != Instruction::UDiv &&
 139          BO->getOpcode() != Instruction::SDiv)) {
 140       Op1C = Op0;
 141       BO = dyn_cast<BinaryOperator>(Op1);
 142     }
 143     Value *Neg = dyn_castNegVal(Op1C);
 144     if (BO && BO->hasOneUse() &&
 145         (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) &&
 146         (BO->getOpcode() == Instruction::UDiv ||
 147          BO->getOpcode() == Instruction::SDiv)) {
 148       Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1);
 149
 150       // If the division is exact, X % Y is zero, so we end up with X or -X.
 151       if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO))
 152         if (SDiv->isExact()) {
 153           if (Op1BO == Op1C)
 154             return ReplaceInstUsesWith(I, Op0BO);
 155           return BinaryOperator::CreateNeg(Op0BO);
 156         }
 157
 158       Value *Rem;
 159       if (BO->getOpcode() == Instruction::UDiv)
 160         Rem = Builder->CreateURem(Op0BO, Op1BO);
 161       else
 162         Rem = Builder->CreateSRem(Op0BO, Op1BO);
 163       Rem->takeName(BO);
 164
 165       if (Op1BO == Op1C)
 166         return BinaryOperator::CreateSub(Op0BO, Rem);
 167       return BinaryOperator::CreateSub(Rem, Op0BO);
 168     }
 169   }
 170
 171   /// i1 mul -> i1 and.
 172   if (I.getType()->isIntegerTy(1))
 173     return BinaryOperator::CreateAnd(Op0, Op1);
 174
 175   // X*(1 << Y) --> X << Y
 176   // (1 << Y)*X --> X << Y
 177   {
 178     Value *Y;
 179     if (match(Op0, m_Shl(m_One(), m_Value(Y))))
 180       return BinaryOperator::CreateShl(Op1, Y);
 181     if (match(Op1, m_Shl(m_One(), m_Value(Y))))
 182       return BinaryOperator::CreateShl(Op0, Y);
 183   }
 184
 185   // If one of the operands of the multiply is a cast from a boolean value, then
 186   // we know the bool is either zero or one, so this is a 'masking' multiply.
 187   //   X * Y (where Y is 0 or 1) -> X & (0-Y)
 188   if (!I.getType()->isVectorTy()) {
 189     // -2 is "-1 << 1" so it is all bits set except the low one.
 190     APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true);
 191
 192     Value *BoolCast = 0, *OtherOp = 0;
 193     if (MaskedValueIsZero(Op0, Negative2))
 194       BoolCast = Op0, OtherOp = Op1;
 195     else if (MaskedValueIsZero(Op1, Negative2))
 196       BoolCast = Op1, OtherOp = Op0;
 197
 198     if (BoolCast) {
 199       Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()),
 200                                     BoolCast, "tmp");
 201       return BinaryOperator::CreateAnd(V, OtherOp);
 202     }
 203   }
 204
 205   return Changed ? &I : 0;
 206 }
 207
 208 Instruction *InstCombiner::visitFMul(BinaryOperator &I) {
 209   bool Changed = SimplifyAssociativeOrCommutative(I);
 210   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 211
 212   // Simplify mul instructions with a constant RHS...
 213   if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
 214     if (ConstantFP *Op1F = dyn_cast<ConstantFP>(Op1C)) {
 215       // "In IEEE floating point, x*1 is not equivalent to x for nans.  However,
 216       // ANSI says we can drop signals, so we can do this anyway." (from GCC)
 217       if (Op1F->isExactlyValue(1.0))
 218         return ReplaceInstUsesWith(I, Op0);  // Eliminate 'fmul double %X, 1.0'
 219     } else if (Op1C->getType()->isVectorTy()) {
 220       if (ConstantVector *Op1V = dyn_cast<ConstantVector>(Op1C)) {
 221         // As above, vector X*splat(1.0) -> X in all defined cases.
 222         if (Constant *Splat = Op1V->getSplatValue()) {
 223           if (ConstantFP *F = dyn_cast<ConstantFP>(Splat))
 224             if (F->isExactlyValue(1.0))
 225               return ReplaceInstUsesWith(I, Op0);
 226         }
 227       }
 228     }
 229
 230     // Try to fold constant mul into select arguments.
 231     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
 232       if (Instruction *R = FoldOpIntoSelect(I, SI))
 233         return R;
 234
 235     if (isa<PHINode>(Op0))
 236       if (Instruction *NV = FoldOpIntoPhi(I))
 237         return NV;
 238   }
 239
 240   if (Value *Op0v = dyn_castFNegVal(Op0))     // -X * -Y = X*Y
 241     if (Value *Op1v = dyn_castFNegVal(Op1))
 242       return BinaryOperator::CreateFMul(Op0v, Op1v);
 243
 244   return Changed ? &I : 0;
 245 }
 246
 247 /// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select
 248 /// instruction.
 249 bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) {
 250   SelectInst *SI = cast<SelectInst>(I.getOperand(1));
 251
 252   // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
 253   int NonNullOperand = -1;
 254   if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1)))
 255     if (ST->isNullValue())
 256       NonNullOperand = 2;
 257   // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
 258   if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2)))
 259     if (ST->isNullValue())
 260       NonNullOperand = 1;
 261
 262   if (NonNullOperand == -1)
 263     return false;
 264
 265   Value *SelectCond = SI->getOperand(0);
 266
 267   // Change the div/rem to use 'Y' instead of the select.
 268   I.setOperand(1, SI->getOperand(NonNullOperand));
 269
 270   // Okay, we know we replace the operand of the div/rem with 'Y' with no
 271   // problem.  However, the select, or the condition of the select may have
 272   // multiple uses.  Based on our knowledge that the operand must be non-zero,
 273   // propagate the known value for the select into other uses of it, and
 274   // propagate a known value of the condition into its other users.
 275
 276   // If the select and condition only have a single use, don't bother with this,
 277   // early exit.
 278   if (SI->use_empty() && SelectCond->hasOneUse())
 279     return true;
 280
 281   // Scan the current block backward, looking for other uses of SI.
 282   BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin();
 283
 284   while (BBI != BBFront) {
 285     --BBI;
 286     // If we found a call to a function, we can't assume it will return, so
 287     // information from below it cannot be propagated above it.
 288     if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI))
 289       break;
 290
 291     // Replace uses of the select or its condition with the known values.
 292     for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end();
 293          I != E; ++I) {
 294       if (*I == SI) {
 295         *I = SI->getOperand(NonNullOperand);
 296         Worklist.Add(BBI);
 297       } else if (*I == SelectCond) {
 298         *I = NonNullOperand == 1 ? ConstantInt::getTrue(BBI->getContext()) :
 299                                    ConstantInt::getFalse(BBI->getContext());
 300         Worklist.Add(BBI);
 301       }
 302     }
 303
 304     // If we past the instruction, quit looking for it.
 305     if (&*BBI == SI)
 306       SI = 0;
 307     if (&*BBI == SelectCond)
 308       SelectCond = 0;
 309
 310     // If we ran out of things to eliminate, break out of the loop.
 311     if (SelectCond == 0 && SI == 0)
 312       break;
 313
 314   }
 315   return true;
 316 }
 317
 318
 319 /// This function implements the transforms common to both integer division
 320 /// instructions (udiv and sdiv). It is called by the visitors to those integer
 321 /// division instructions.
 322 /// @brief Common integer divide transforms
 323 Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
 324   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 325
 326   // The RHS is known non-zero.
 327   if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) {
 328     I.setOperand(1, V);
 329     return &I;
 330   }
 331
 332   // Handle cases involving: [su]div X, (select Cond, Y, Z)
 333   // This does not apply for fdiv.
 334   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
 335     return &I;
 336
 337   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
 338     // (X / C1) / C2  -> X / (C1*C2)
 339     if (Instruction *LHS = dyn_cast<Instruction>(Op0))
 340       if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode())
 341         if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) {
 342           if (MultiplyOverflows(RHS, LHSRHS,
 343                                 I.getOpcode()==Instruction::SDiv))
 344             return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 345           return BinaryOperator::Create(I.getOpcode(), LHS->getOperand(0),
 346                                         ConstantExpr::getMul(RHS, LHSRHS));
 347         }
 348
 349     if (!RHS->isZero()) { // avoid X udiv 0
 350       if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
 351         if (Instruction *R = FoldOpIntoSelect(I, SI))
 352           return R;
 353       if (isa<PHINode>(Op0))
 354         if (Instruction *NV = FoldOpIntoPhi(I))
 355           return NV;
 356     }
 357   }
 358
 359   // See if we can fold away this div instruction.
 360   if (SimplifyDemandedInstructionBits(I))
 361     return &I;
 362
 363   // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
 364   Value *X = 0, *Z = 0;
 365   if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1
 366     bool isSigned = I.getOpcode() == Instruction::SDiv;
 367     if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
 368         (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
 369       return BinaryOperator::Create(I.getOpcode(), X, Op1);
 370   }
 371
 372   return 0;
 373 }
 374
 375 /// dyn_castZExtVal - Checks if V is a zext or constant that can
 376 /// be truncated to Ty without losing bits.
 377 static Value *dyn_castZExtVal(Value *V, const Type *Ty) {
 378   if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) {
 379     if (Z->getSrcTy() == Ty)
 380       return Z->getOperand(0);
 381   } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) {
 382     if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth())
 383       return ConstantExpr::getTrunc(C, Ty);
 384   }
 385   return 0;
 386 }
 387
 388 Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
 389   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 390
 391   if (Value *V = SimplifyUDivInst(Op0, Op1, TD))
 392     return ReplaceInstUsesWith(I, V);
 393
 394   // Handle the integer div common cases
 395   if (Instruction *Common = commonIDivTransforms(I))
 396     return Common;
 397
 398   if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) {
 399     // X udiv 2^C -> X >> C
 400     // Check to see if this is an unsigned division with an exact power of 2,
 401     // if so, convert to a right shift.
 402     if (C->getValue().isPowerOf2()) { // 0 not included in isPowerOf2
 403       BinaryOperator *LShr =
 404         BinaryOperator::CreateLShr(Op0,
 405             ConstantInt::get(Op0->getType(), C->getValue().logBase2()));
 406       if (I.isExact()) LShr->setIsExact();
 407       return LShr;
 408     }
 409
 410     // X udiv C, where C >= signbit
 411     if (C->getValue().isNegative()) {
 412       Value *IC = Builder->CreateICmpULT(Op0, C);
 413       return SelectInst::Create(IC, Constant::getNullValue(I.getType()),
 414                                 ConstantInt::get(I.getType(), 1));
 415     }
 416   }
 417
 418   // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
 419   { const APInt *CI; Value *N;
 420     if (match(Op1, m_Shl(m_Power2(CI), m_Value(N)))) {
 421       if (*CI != 1)
 422         N = Builder->CreateAdd(N, ConstantInt::get(I.getType(), CI->logBase2()),
 423                                "tmp");
 424       if (I.isExact())
 425         return BinaryOperator::CreateExactLShr(Op0, N);
 426       return BinaryOperator::CreateLShr(Op0, N);
 427     }
 428   }
 429
 430   // udiv X, (Select Cond, C1, C2) --> Select Cond, (shr X, C1), (shr X, C2)
 431   // where C1&C2 are powers of two.
 432   { Value *Cond; const APInt *C1, *C2;
 433     if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) {
 434       // Construct the "on true" case of the select
 435       Value *TSI = Builder->CreateLShr(Op0, C1->logBase2(), Op1->getName()+".t",
 436                                        I.isExact());
 437
 438       // Construct the "on false" case of the select
 439       Value *FSI = Builder->CreateLShr(Op0, C2->logBase2(), Op1->getName()+".f",
 440                                        I.isExact());
 441
 442       // construct the select instruction and return it.
 443       return SelectInst::Create(Cond, TSI, FSI);
 444     }
 445   }
 446
 447   // (zext A) udiv (zext B) --> zext (A udiv B)
 448   if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0))
 449     if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy()))
 450       return new ZExtInst(Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div",
 451                                               I.isExact()),
 452                           I.getType());
 453
 454   return 0;
 455 }
 456
 457 Instruction *InstCombiner::visitSDiv(BinaryOperator &I) {
 458   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 459
 460   if (Value *V = SimplifySDivInst(Op0, Op1, TD))
 461     return ReplaceInstUsesWith(I, V);
 462
 463   // Handle the integer div common cases
 464   if (Instruction *Common = commonIDivTransforms(I))
 465     return Common;
 466
 467   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
 468     // sdiv X, -1 == -X
 469     if (RHS->isAllOnesValue())
 470       return BinaryOperator::CreateNeg(Op0);
 471
 472     // sdiv X, C  -->  ashr exact X, log2(C)
 473     if (I.isExact() && RHS->getValue().isNonNegative() &&
 474         RHS->getValue().isPowerOf2()) {
 475       Value *ShAmt = llvm::ConstantInt::get(RHS->getType(),
 476                                             RHS->getValue().exactLogBase2());
 477       return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName());
 478     }
 479
 480     // -X/C  -->  X/-C  provided the negation doesn't overflow.
 481     if (SubOperator *Sub = dyn_cast<SubOperator>(Op0))
 482       if (match(Sub->getOperand(0), m_Zero()) && Sub->hasNoSignedWrap())
 483         return BinaryOperator::CreateSDiv(Sub->getOperand(1),
 484                                           ConstantExpr::getNeg(RHS));
 485   }
 486
 487   // If the sign bits of both operands are zero (i.e. we can prove they are
 488   // unsigned inputs), turn this into a udiv.
 489   if (I.getType()->isIntegerTy()) {
 490     APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits()));
 491     if (MaskedValueIsZero(Op0, Mask)) {
 492       if (MaskedValueIsZero(Op1, Mask)) {
 493         // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
 494         return BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
 495       }
 496
 497       if (match(Op1, m_Shl(m_Power2(), m_Value()))) {
 498         // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
 499         // Safe because the only negative value (1 << Y) can take on is
 500         // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
 501         // the sign bit set.
 502         return BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
 503       }
 504     }
 505   }
 506
 507   return 0;
 508 }
 509
 510 Instruction *InstCombiner::visitFDiv(BinaryOperator &I) {
 511   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 512
 513   if (Value *V = SimplifyFDivInst(Op0, Op1, TD))
 514     return ReplaceInstUsesWith(I, V);
 515
 516   if (ConstantFP *Op1C = dyn_cast<ConstantFP>(Op1)) {
 517     const APFloat &Op1F = Op1C->getValueAPF();
 518
 519     // If the divisor has an exact multiplicative inverse we can turn the fdiv
 520     // into a cheaper fmul.
 521     APFloat Reciprocal(Op1F.getSemantics());
 522     if (Op1F.getExactInverse(&Reciprocal)) {
 523       ConstantFP *RFP = ConstantFP::get(Builder->getContext(), Reciprocal);
 524       return BinaryOperator::CreateFMul(Op0, RFP);
 525     }
 526   }
 527
 528   return 0;
 529 }
 530
 531 /// This function implements the transforms common to both integer remainder
 532 /// instructions (urem and srem). It is called by the visitors to those integer
 533 /// remainder instructions.
 534 /// @brief Common integer remainder transforms
 535 Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) {
 536   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 537
 538   // The RHS is known non-zero.
 539   if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) {
 540     I.setOperand(1, V);
 541     return &I;
 542   }
 543
 544   // Handle cases involving: rem X, (select Cond, Y, Z)
 545   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
 546     return &I;
 547
 548   if (isa<ConstantInt>(Op1)) {
 549     if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
 550       if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
 551         if (Instruction *R = FoldOpIntoSelect(I, SI))
 552           return R;
 553       } else if (isa<PHINode>(Op0I)) {
 554         if (Instruction *NV = FoldOpIntoPhi(I))
 555           return NV;
 556       }
 557
 558       // See if we can fold away this rem instruction.
 559       if (SimplifyDemandedInstructionBits(I))
 560         return &I;
 561     }
 562   }
 563
 564   return 0;
 565 }
 566
 567 Instruction *InstCombiner::visitURem(BinaryOperator &I) {
 568   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 569
 570   if (Value *V = SimplifyURemInst(Op0, Op1, TD))
 571     return ReplaceInstUsesWith(I, V);
 572
 573   if (Instruction *common = commonIRemTransforms(I))
 574     return common;
 575
 576   // X urem C^2 -> X and C-1
 577   { const APInt *C;
 578     if (match(Op1, m_Power2(C)))
 579       return BinaryOperator::CreateAnd(Op0,
 580                                        ConstantInt::get(I.getType(), *C-1));
 581   }
 582
 583   // Turn A % (C << N), where C is 2^k, into A & ((C << N)-1)
 584   if (match(Op1, m_Shl(m_Power2(), m_Value()))) {
 585     Constant *N1 = Constant::getAllOnesValue(I.getType());
 586     Value *Add = Builder->CreateAdd(Op1, N1, "tmp");
 587     return BinaryOperator::CreateAnd(Op0, Add);
 588   }
 589
 590   // urem X, (select Cond, 2^C1, 2^C2) -->
 591   //    select Cond, (and X, C1-1), (and X, C2-1)
 592   // when C1&C2 are powers of two.
 593   { Value *Cond; const APInt *C1, *C2;
 594     if (match(Op1, m_Select(m_Value(Cond), m_Power2(C1), m_Power2(C2)))) {
 595       Value *TrueAnd = Builder->CreateAnd(Op0, *C1-1, Op1->getName()+".t");
 596       Value *FalseAnd = Builder->CreateAnd(Op0, *C2-1, Op1->getName()+".f");
 597       return SelectInst::Create(Cond, TrueAnd, FalseAnd);
 598     }
 599   }
 600
 601   // (zext A) urem (zext B) --> zext (A urem B)
 602   if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0))
 603     if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy()))
 604       return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1),
 605                           I.getType());
 606
 607   return 0;
 608 }
 609
 610 Instruction *InstCombiner::visitSRem(BinaryOperator &I) {
 611   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 612
 613   if (Value *V = SimplifySRemInst(Op0, Op1, TD))
 614     return ReplaceInstUsesWith(I, V);
 615
 616   // Handle the integer rem common cases
 617   if (Instruction *Common = commonIRemTransforms(I))
 618     return Common;
 619
 620   if (Value *RHSNeg = dyn_castNegVal(Op1))
 621     if (!isa<Constant>(RHSNeg) ||
 622         (isa<ConstantInt>(RHSNeg) &&
 623          cast<ConstantInt>(RHSNeg)->getValue().isStrictlyPositive())) {
 624       // X % -Y -> X % Y
 625       Worklist.AddValue(I.getOperand(1));
 626       I.setOperand(1, RHSNeg);
 627       return &I;
 628     }
 629
 630   // If the sign bits of both operands are zero (i.e. we can prove they are
 631   // unsigned inputs), turn this into a urem.
 632   if (I.getType()->isIntegerTy()) {
 633     APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits()));
 634     if (MaskedValueIsZero(Op1, Mask) && MaskedValueIsZero(Op0, Mask)) {
 635       // X srem Y -> X urem Y, iff X and Y don't have sign bit set
 636       return BinaryOperator::CreateURem(Op0, Op1, I.getName());
 637     }
 638   }
 639
 640   // If it's a constant vector, flip any negative values positive.
 641   if (ConstantVector *RHSV = dyn_cast<ConstantVector>(Op1)) {
 642     unsigned VWidth = RHSV->getNumOperands();
 643
 644     bool hasNegative = false;
 645     for (unsigned i = 0; !hasNegative && i != VWidth; ++i)
 646       if (ConstantInt *RHS = dyn_cast<ConstantInt>(RHSV->getOperand(i)))
 647         if (RHS->getValue().isNegative())
 648           hasNegative = true;
 649
 650     if (hasNegative) {
 651       std::vector<Constant *> Elts(VWidth);
 652       for (unsigned i = 0; i != VWidth; ++i) {
 653         if (ConstantInt *RHS = dyn_cast<ConstantInt>(RHSV->getOperand(i))) {
 654           if (RHS->getValue().isNegative())
 655             Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
 656           else
 657             Elts[i] = RHS;
 658         }
 659       }
 660
 661       Constant *NewRHSV = ConstantVector::get(Elts);
 662       if (NewRHSV != RHSV) {
 663         Worklist.AddValue(I.getOperand(1));
 664         I.setOperand(1, NewRHSV);
 665         return &I;
 666       }
 667     }
 668   }
 669
 670   return 0;
 671 }
 672
 673 Instruction *InstCombiner::visitFRem(BinaryOperator &I) {
 674   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 675
 676   if (Value *V = SimplifyFRemInst(Op0, Op1, TD))
 677     return ReplaceInstUsesWith(I, V);
 678
 679   // Handle cases involving: rem X, (select Cond, Y, Z)
 680   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
 681     return &I;
 682
 683   return 0;
 684 }