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