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 on div instructions that work
 308 /// regardless of the kind of div instruction it is (udiv, sdiv, or fdiv). It is
 309 /// used by the visitors to those instructions.
 310 /// @brief Transforms common to all three div instructions
 311 Instruction *InstCombiner::commonDivTransforms(BinaryOperator &I) {
 312   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 313
 314   // undef / X -> 0        for integer.
 315   // undef / X -> undef    for FP (the undef could be a snan).
 316   if (isa<UndefValue>(Op0)) {
 317     if (Op0->getType()->isFPOrFPVectorTy())
 318       return ReplaceInstUsesWith(I, Op0);
 319     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 320   }
 321
 322   // X / undef -> undef
 323   if (isa<UndefValue>(Op1))
 324     return ReplaceInstUsesWith(I, Op1);
 325
 326   return 0;
 327 }
 328
 329 /// This function implements the transforms common to both integer division
 330 /// instructions (udiv and sdiv). It is called by the visitors to those integer
 331 /// division instructions.
 332 /// @brief Common integer divide transforms
 333 Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
 334   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 335
 336   // (sdiv X, X) --> 1     (udiv X, X) --> 1
 337   if (Op0 == Op1) {
 338     if (const VectorType *Ty = dyn_cast<VectorType>(I.getType())) {
 339       Constant *CI = ConstantInt::get(Ty->getElementType(), 1);
 340       std::vector<Constant*> Elts(Ty->getNumElements(), CI);
 341       return ReplaceInstUsesWith(I, ConstantVector::get(Elts));
 342     }
 343
 344     Constant *CI = ConstantInt::get(I.getType(), 1);
 345     return ReplaceInstUsesWith(I, CI);
 346   }
 347
 348   if (Instruction *Common = commonDivTransforms(I))
 349     return Common;
 350
 351   // Handle cases involving: [su]div X, (select Cond, Y, Z)
 352   // This does not apply for fdiv.
 353   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
 354     return &I;
 355
 356   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
 357     // div X, 1 == X
 358     if (RHS->equalsInt(1))
 359       return ReplaceInstUsesWith(I, Op0);
 360
 361     // (X / C1) / C2  -> X / (C1*C2)
 362     if (Instruction *LHS = dyn_cast<Instruction>(Op0))
 363       if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode())
 364         if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) {
 365           if (MultiplyOverflows(RHS, LHSRHS,
 366                                 I.getOpcode()==Instruction::SDiv))
 367             return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 368           else
 369             return BinaryOperator::Create(I.getOpcode(), LHS->getOperand(0),
 370                                       ConstantExpr::getMul(RHS, LHSRHS));
 371         }
 372
 373     if (!RHS->isZero()) { // avoid X udiv 0
 374       if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
 375         if (Instruction *R = FoldOpIntoSelect(I, SI))
 376           return R;
 377       if (isa<PHINode>(Op0))
 378         if (Instruction *NV = FoldOpIntoPhi(I))
 379           return NV;
 380     }
 381   }
 382
 383   // 0 / X == 0, we don't need to preserve faults!
 384   if (ConstantInt *LHS = dyn_cast<ConstantInt>(Op0))
 385     if (LHS->equalsInt(0))
 386       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 387
 388   // It can't be division by zero, hence it must be division by one.
 389   if (I.getType()->isIntegerTy(1))
 390     return ReplaceInstUsesWith(I, Op0);
 391
 392   if (ConstantVector *Op1V = dyn_cast<ConstantVector>(Op1)) {
 393     if (ConstantInt *X = cast_or_null<ConstantInt>(Op1V->getSplatValue()))
 394       // div X, 1 == X
 395       if (X->isOne())
 396         return ReplaceInstUsesWith(I, Op0);
 397   }
 398
 399   return 0;
 400 }
 401
 402 Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
 403   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 404
 405   // Handle the integer div common cases
 406   if (Instruction *Common = commonIDivTransforms(I))
 407     return Common;
 408
 409   if (ConstantInt *C = dyn_cast<ConstantInt>(Op1)) {
 410     // X udiv 2^C -> X >> C
 411     // Check to see if this is an unsigned division with an exact power of 2,
 412     // if so, convert to a right shift.
 413     if (C->getValue().isPowerOf2())  // 0 not included in isPowerOf2
 414       return BinaryOperator::CreateLShr(Op0,
 415             ConstantInt::get(Op0->getType(), C->getValue().logBase2()));
 416
 417     // X udiv C, where C >= signbit
 418     if (C->getValue().isNegative()) {
 419       Value *IC = Builder->CreateICmpULT( Op0, C);
 420       return SelectInst::Create(IC, Constant::getNullValue(I.getType()),
 421                                 ConstantInt::get(I.getType(), 1));
 422     }
 423   }
 424
 425   // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
 426   if (BinaryOperator *RHSI = dyn_cast<BinaryOperator>(I.getOperand(1))) {
 427     if (RHSI->getOpcode() == Instruction::Shl &&
 428         isa<ConstantInt>(RHSI->getOperand(0))) {
 429       const APInt& C1 = cast<ConstantInt>(RHSI->getOperand(0))->getValue();
 430       if (C1.isPowerOf2()) {
 431         Value *N = RHSI->getOperand(1);
 432         const Type *NTy = N->getType();
 433         if (uint32_t C2 = C1.logBase2())
 434           N = Builder->CreateAdd(N, ConstantInt::get(NTy, C2), "tmp");
 435         return BinaryOperator::CreateLShr(Op0, N);
 436       }
 437     }
 438   }
 439
 440   // udiv X, (Select Cond, C1, C2) --> Select Cond, (shr X, C1), (shr X, C2)
 441   // where C1&C2 are powers of two.
 442   if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
 443     if (ConstantInt *STO = dyn_cast<ConstantInt>(SI->getOperand(1)))
 444       if (ConstantInt *SFO = dyn_cast<ConstantInt>(SI->getOperand(2)))  {
 445         const APInt &TVA = STO->getValue(), &FVA = SFO->getValue();
 446         if (TVA.isPowerOf2() && FVA.isPowerOf2()) {
 447           // Compute the shift amounts
 448           uint32_t TSA = TVA.logBase2(), FSA = FVA.logBase2();
 449           // Construct the "on true" case of the select
 450           Constant *TC = ConstantInt::get(Op0->getType(), TSA);
 451           Value *TSI = Builder->CreateLShr(Op0, TC, SI->getName()+".t");
 452
 453           // Construct the "on false" case of the select
 454           Constant *FC = ConstantInt::get(Op0->getType(), FSA);
 455           Value *FSI = Builder->CreateLShr(Op0, FC, SI->getName()+".f");
 456
 457           // construct the select instruction and return it.
 458           return SelectInst::Create(SI->getOperand(0), TSI, FSI, SI->getName());
 459         }
 460       }
 461   return 0;
 462 }
 463
 464 Instruction *InstCombiner::visitSDiv(BinaryOperator &I) {
 465   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 466
 467   // Handle the integer div common cases
 468   if (Instruction *Common = commonIDivTransforms(I))
 469     return Common;
 470
 471   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
 472     // sdiv X, -1 == -X
 473     if (RHS->isAllOnesValue())
 474       return BinaryOperator::CreateNeg(Op0);
 475
 476     // sdiv X, C  -->  ashr X, log2(C)
 477     if (cast<SDivOperator>(&I)->isExact() &&
 478         RHS->getValue().isNonNegative() &&
 479         RHS->getValue().isPowerOf2()) {
 480       Value *ShAmt = llvm::ConstantInt::get(RHS->getType(),
 481                                             RHS->getValue().exactLogBase2());
 482       return BinaryOperator::CreateAShr(Op0, ShAmt, I.getName());
 483     }
 484
 485     // -X/C  -->  X/-C  provided the negation doesn't overflow.
 486     if (SubOperator *Sub = dyn_cast<SubOperator>(Op0))
 487       if (isa<Constant>(Sub->getOperand(0)) &&
 488           cast<Constant>(Sub->getOperand(0))->isNullValue() &&
 489           Sub->hasNoSignedWrap())
 490         return BinaryOperator::CreateSDiv(Sub->getOperand(1),
 491                                           ConstantExpr::getNeg(RHS));
 492   }
 493
 494   // If the sign bits of both operands are zero (i.e. we can prove they are
 495   // unsigned inputs), turn this into a udiv.
 496   if (I.getType()->isIntegerTy()) {
 497     APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits()));
 498     if (MaskedValueIsZero(Op0, Mask)) {
 499       if (MaskedValueIsZero(Op1, Mask)) {
 500         // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
 501         return BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
 502       }
 503       ConstantInt *ShiftedInt;
 504       if (match(Op1, m_Shl(m_ConstantInt(ShiftedInt), m_Value())) &&
 505           ShiftedInt->getValue().isPowerOf2()) {
 506         // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
 507         // Safe because the only negative value (1 << Y) can take on is
 508         // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
 509         // the sign bit set.
 510         return BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
 511       }
 512     }
 513   }
 514
 515   return 0;
 516 }
 517
 518 Instruction *InstCombiner::visitFDiv(BinaryOperator &I) {
 519   return commonDivTransforms(I);
 520 }
 521
 522 /// This function implements the transforms on rem instructions that work
 523 /// regardless of the kind of rem instruction it is (urem, srem, or frem). It
 524 /// is used by the visitors to those instructions.
 525 /// @brief Transforms common to all three rem instructions
 526 Instruction *InstCombiner::commonRemTransforms(BinaryOperator &I) {
 527   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 528
 529   if (isa<UndefValue>(Op0)) {             // undef % X -> 0
 530     if (I.getType()->isFPOrFPVectorTy())
 531       return ReplaceInstUsesWith(I, Op0);  // X % undef -> undef (could be SNaN)
 532     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 533   }
 534   if (isa<UndefValue>(Op1))
 535     return ReplaceInstUsesWith(I, Op1);  // X % undef -> undef
 536
 537   // Handle cases involving: rem X, (select Cond, Y, Z)
 538   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
 539     return &I;
 540
 541   return 0;
 542 }
 543
 544 /// This function implements the transforms common to both integer remainder
 545 /// instructions (urem and srem). It is called by the visitors to those integer
 546 /// remainder instructions.
 547 /// @brief Common integer remainder transforms
 548 Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) {
 549   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 550
 551   if (Instruction *common = commonRemTransforms(I))
 552     return common;
 553
 554   // X % X == 0
 555   if (Op0 == Op1)
 556     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 557
 558   // 0 % X == 0 for integer, we don't need to preserve faults!
 559   if (Constant *LHS = dyn_cast<Constant>(Op0))
 560     if (LHS->isNullValue())
 561       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 562
 563   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
 564     // X % 0 == undef, we don't need to preserve faults!
 565     if (RHS->equalsInt(0))
 566       return ReplaceInstUsesWith(I, UndefValue::get(I.getType()));
 567
 568     if (RHS->equalsInt(1))  // X % 1 == 0
 569       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 570
 571     if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
 572       if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
 573         if (Instruction *R = FoldOpIntoSelect(I, SI))
 574           return R;
 575       } else if (isa<PHINode>(Op0I)) {
 576         if (Instruction *NV = FoldOpIntoPhi(I))
 577           return NV;
 578       }
 579
 580       // See if we can fold away this rem instruction.
 581       if (SimplifyDemandedInstructionBits(I))
 582         return &I;
 583     }
 584   }
 585
 586   return 0;
 587 }
 588
 589 Instruction *InstCombiner::visitURem(BinaryOperator &I) {
 590   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 591
 592   if (Instruction *common = commonIRemTransforms(I))
 593     return common;
 594
 595   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
 596     // X urem C^2 -> X and C
 597     // Check to see if this is an unsigned remainder with an exact power of 2,
 598     // if so, convert to a bitwise and.
 599     if (ConstantInt *C = dyn_cast<ConstantInt>(RHS))
 600       if (C->getValue().isPowerOf2())
 601         return BinaryOperator::CreateAnd(Op0, SubOne(C));
 602   }
 603
 604   if (Instruction *RHSI = dyn_cast<Instruction>(I.getOperand(1))) {
 605     // Turn A % (C << N), where C is 2^k, into A & ((C << N)-1)
 606     if (RHSI->getOpcode() == Instruction::Shl &&
 607         isa<ConstantInt>(RHSI->getOperand(0))) {
 608       if (cast<ConstantInt>(RHSI->getOperand(0))->getValue().isPowerOf2()) {
 609         Constant *N1 = Constant::getAllOnesValue(I.getType());
 610         Value *Add = Builder->CreateAdd(RHSI, N1, "tmp");
 611         return BinaryOperator::CreateAnd(Op0, Add);
 612       }
 613     }
 614   }
 615
 616   // urem X, (select Cond, 2^C1, 2^C2) --> select Cond, (and X, C1), (and X, C2)
 617   // where C1&C2 are powers of two.
 618   if (SelectInst *SI = dyn_cast<SelectInst>(Op1)) {
 619     if (ConstantInt *STO = dyn_cast<ConstantInt>(SI->getOperand(1)))
 620       if (ConstantInt *SFO = dyn_cast<ConstantInt>(SI->getOperand(2))) {
 621         // STO == 0 and SFO == 0 handled above.
 622         if ((STO->getValue().isPowerOf2()) &&
 623             (SFO->getValue().isPowerOf2())) {
 624           Value *TrueAnd = Builder->CreateAnd(Op0, SubOne(STO),
 625                                               SI->getName()+".t");
 626           Value *FalseAnd = Builder->CreateAnd(Op0, SubOne(SFO),
 627                                                SI->getName()+".f");
 628           return SelectInst::Create(SI->getOperand(0), TrueAnd, FalseAnd);
 629         }
 630       }
 631   }
 632
 633   return 0;
 634 }
 635
 636 Instruction *InstCombiner::visitSRem(BinaryOperator &I) {
 637   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 638
 639   // Handle the integer rem common cases
 640   if (Instruction *Common = commonIRemTransforms(I))
 641     return Common;
 642
 643   if (Value *RHSNeg = dyn_castNegVal(Op1))
 644     if (!isa<Constant>(RHSNeg) ||
 645         (isa<ConstantInt>(RHSNeg) &&
 646          cast<ConstantInt>(RHSNeg)->getValue().isStrictlyPositive())) {
 647       // X % -Y -> X % Y
 648       Worklist.AddValue(I.getOperand(1));
 649       I.setOperand(1, RHSNeg);
 650       return &I;
 651     }
 652
 653   // If the sign bits of both operands are zero (i.e. we can prove they are
 654   // unsigned inputs), turn this into a urem.
 655   if (I.getType()->isIntegerTy()) {
 656     APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits()));
 657     if (MaskedValueIsZero(Op1, Mask) && MaskedValueIsZero(Op0, Mask)) {
 658       // X srem Y -> X urem Y, iff X and Y don't have sign bit set
 659       return BinaryOperator::CreateURem(Op0, Op1, I.getName());
 660     }
 661   }
 662
 663   // If it's a constant vector, flip any negative values positive.
 664   if (ConstantVector *RHSV = dyn_cast<ConstantVector>(Op1)) {
 665     unsigned VWidth = RHSV->getNumOperands();
 666
 667     bool hasNegative = false;
 668     for (unsigned i = 0; !hasNegative && i != VWidth; ++i)
 669       if (ConstantInt *RHS = dyn_cast<ConstantInt>(RHSV->getOperand(i)))
 670         if (RHS->getValue().isNegative())
 671           hasNegative = true;
 672
 673     if (hasNegative) {
 674       std::vector<Constant *> Elts(VWidth);
 675       for (unsigned i = 0; i != VWidth; ++i) {
 676         if (ConstantInt *RHS = dyn_cast<ConstantInt>(RHSV->getOperand(i))) {
 677           if (RHS->getValue().isNegative())
 678             Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
 679           else
 680             Elts[i] = RHS;
 681         }
 682       }
 683
 684       Constant *NewRHSV = ConstantVector::get(Elts);
 685       if (NewRHSV != RHSV) {
 686         Worklist.AddValue(I.getOperand(1));
 687         I.setOperand(1, NewRHSV);
 688         return &I;
 689       }
 690     }
 691   }
 692
 693   return 0;
 694 }
 695
 696 Instruction *InstCombiner::visitFRem(BinaryOperator &I) {
 697   return commonRemTransforms(I);
 698 }
 699