LLVM API Documentation

InstCombineMulDivRem.cpp
Go to the documentation of this file.
00001 //===- InstCombineMulDivRem.cpp -------------------------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv,
00011 // srem, urem, frem.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "InstCombine.h"
00016 #include "llvm/Analysis/InstructionSimplify.h"
00017 #include "llvm/IR/IntrinsicInst.h"
00018 #include "llvm/IR/PatternMatch.h"
00019 using namespace llvm;
00020 using namespace PatternMatch;
00021 
00022 
00023 /// simplifyValueKnownNonZero - The specific integer value is used in a context
00024 /// where it is known to be non-zero.  If this allows us to simplify the
00025 /// computation, do so and return the new operand, otherwise return null.
00026 static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC) {
00027   // If V has multiple uses, then we would have to do more analysis to determine
00028   // if this is safe.  For example, the use could be in dynamically unreached
00029   // code.
00030   if (!V->hasOneUse()) return 0;
00031 
00032   bool MadeChange = false;
00033 
00034   // ((1 << A) >>u B) --> (1 << (A-B))
00035   // Because V cannot be zero, we know that B is less than A.
00036   Value *A = 0, *B = 0, *PowerOf2 = 0;
00037   if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(PowerOf2), m_Value(A))),
00038                       m_Value(B))) &&
00039       // The "1" can be any value known to be a power of 2.
00040       isKnownToBeAPowerOfTwo(PowerOf2)) {
00041     A = IC.Builder->CreateSub(A, B);
00042     return IC.Builder->CreateShl(PowerOf2, A);
00043   }
00044 
00045   // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
00046   // inexact.  Similarly for <<.
00047   if (BinaryOperator *I = dyn_cast<BinaryOperator>(V))
00048     if (I->isLogicalShift() && isKnownToBeAPowerOfTwo(I->getOperand(0))) {
00049       // We know that this is an exact/nuw shift and that the input is a
00050       // non-zero context as well.
00051       if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC)) {
00052         I->setOperand(0, V2);
00053         MadeChange = true;
00054       }
00055 
00056       if (I->getOpcode() == Instruction::LShr && !I->isExact()) {
00057         I->setIsExact();
00058         MadeChange = true;
00059       }
00060 
00061       if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) {
00062         I->setHasNoUnsignedWrap();
00063         MadeChange = true;
00064       }
00065     }
00066 
00067   // TODO: Lots more we could do here:
00068   //    If V is a phi node, we can call this on each of its operands.
00069   //    "select cond, X, 0" can simplify to "X".
00070 
00071   return MadeChange ? V : 0;
00072 }
00073 
00074 
00075 /// MultiplyOverflows - True if the multiply can not be expressed in an int
00076 /// this size.
00077 static bool MultiplyOverflows(ConstantInt *C1, ConstantInt *C2, bool sign) {
00078   uint32_t W = C1->getBitWidth();
00079   APInt LHSExt = C1->getValue(), RHSExt = C2->getValue();
00080   if (sign) {
00081     LHSExt = LHSExt.sext(W * 2);
00082     RHSExt = RHSExt.sext(W * 2);
00083   } else {
00084     LHSExt = LHSExt.zext(W * 2);
00085     RHSExt = RHSExt.zext(W * 2);
00086   }
00087 
00088   APInt MulExt = LHSExt * RHSExt;
00089 
00090   if (!sign)
00091     return MulExt.ugt(APInt::getLowBitsSet(W * 2, W));
00092 
00093   APInt Min = APInt::getSignedMinValue(W).sext(W * 2);
00094   APInt Max = APInt::getSignedMaxValue(W).sext(W * 2);
00095   return MulExt.slt(Min) || MulExt.sgt(Max);
00096 }
00097 
00098 /// \brief A helper routine of InstCombiner::visitMul().
00099 ///
00100 /// If C is a vector of known powers of 2, then this function returns
00101 /// a new vector obtained from C replacing each element with its logBase2.
00102 /// Return a null pointer otherwise.
00103 static Constant *getLogBase2Vector(ConstantDataVector *CV) {
00104   const APInt *IVal;
00105   SmallVector<Constant *, 4> Elts;
00106 
00107   for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) {
00108     Constant *Elt = CV->getElementAsConstant(I);
00109     if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2())
00110       return 0;
00111     Elts.push_back(ConstantInt::get(Elt->getType(), IVal->logBase2()));
00112   }
00113 
00114   return ConstantVector::get(Elts);
00115 }
00116 
00117 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
00118   bool Changed = SimplifyAssociativeOrCommutative(I);
00119   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
00120 
00121   if (Value *V = SimplifyMulInst(Op0, Op1, DL))
00122     return ReplaceInstUsesWith(I, V);
00123 
00124   if (Value *V = SimplifyUsingDistributiveLaws(I))
00125     return ReplaceInstUsesWith(I, V);
00126 
00127   if (match(Op1, m_AllOnes()))  // X * -1 == 0 - X
00128     return BinaryOperator::CreateNeg(Op0, I.getName());
00129 
00130   // Also allow combining multiply instructions on vectors.
00131   {
00132     Value *NewOp;
00133     Constant *C1, *C2;
00134     const APInt *IVal;
00135     if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
00136                         m_Constant(C1))) &&
00137         match(C1, m_APInt(IVal)))
00138       // ((X << C1)*C2) == (X * (C2 << C1))
00139       return BinaryOperator::CreateMul(NewOp, ConstantExpr::getShl(C1, C2));
00140 
00141     if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
00142       Constant *NewCst = 0;
00143       if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2())
00144         // Replace X*(2^C) with X << C, where C is either a scalar or a splat.
00145         NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2());
00146       else if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(C1))
00147         // Replace X*(2^C) with X << C, where C is a vector of known
00148         // constant powers of 2.
00149         NewCst = getLogBase2Vector(CV);
00150 
00151       if (NewCst) {
00152         BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
00153         if (I.hasNoSignedWrap()) Shl->setHasNoSignedWrap();
00154         if (I.hasNoUnsignedWrap()) Shl->setHasNoUnsignedWrap();
00155         return Shl;
00156       }
00157     }
00158   }
00159 
00160   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
00161     // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n
00162     // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n
00163     // The "* (2**n)" thus becomes a potential shifting opportunity.
00164     {
00165       const APInt &   Val = CI->getValue();
00166       const APInt &PosVal = Val.abs();
00167       if (Val.isNegative() && PosVal.isPowerOf2()) {
00168         Value *X = 0, *Y = 0;
00169         if (Op0->hasOneUse()) {
00170           ConstantInt *C1;
00171           Value *Sub = 0;
00172           if (match(Op0, m_Sub(m_Value(Y), m_Value(X))))
00173             Sub = Builder->CreateSub(X, Y, "suba");
00174           else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1))))
00175             Sub = Builder->CreateSub(Builder->CreateNeg(C1), Y, "subc");
00176           if (Sub)
00177             return
00178               BinaryOperator::CreateMul(Sub,
00179                                         ConstantInt::get(Y->getType(), PosVal));
00180         }
00181       }
00182     }
00183   }
00184 
00185   // Simplify mul instructions with a constant RHS.
00186   if (isa<Constant>(Op1)) {
00187     // Try to fold constant mul into select arguments.
00188     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
00189       if (Instruction *R = FoldOpIntoSelect(I, SI))
00190         return R;
00191 
00192     if (isa<PHINode>(Op0))
00193       if (Instruction *NV = FoldOpIntoPhi(I))
00194         return NV;
00195 
00196     // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
00197     {
00198       Value *X;
00199       Constant *C1;
00200       if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) {
00201         Value *Add = Builder->CreateMul(X, Op1);
00202         return BinaryOperator::CreateAdd(Add, Builder->CreateMul(C1, Op1));
00203       }
00204     }
00205   }
00206 
00207   if (Value *Op0v = dyn_castNegVal(Op0))     // -X * -Y = X*Y
00208     if (Value *Op1v = dyn_castNegVal(Op1))
00209       return BinaryOperator::CreateMul(Op0v, Op1v);
00210 
00211   // (X / Y) *  Y = X - (X % Y)
00212   // (X / Y) * -Y = (X % Y) - X
00213   {
00214     Value *Op1C = Op1;
00215     BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0);
00216     if (!BO ||
00217         (BO->getOpcode() != Instruction::UDiv &&
00218          BO->getOpcode() != Instruction::SDiv)) {
00219       Op1C = Op0;
00220       BO = dyn_cast<BinaryOperator>(Op1);
00221     }
00222     Value *Neg = dyn_castNegVal(Op1C);
00223     if (BO && BO->hasOneUse() &&
00224         (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) &&
00225         (BO->getOpcode() == Instruction::UDiv ||
00226          BO->getOpcode() == Instruction::SDiv)) {
00227       Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1);
00228 
00229       // If the division is exact, X % Y is zero, so we end up with X or -X.
00230       if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO))
00231         if (SDiv->isExact()) {
00232           if (Op1BO == Op1C)
00233             return ReplaceInstUsesWith(I, Op0BO);
00234           return BinaryOperator::CreateNeg(Op0BO);
00235         }
00236 
00237       Value *Rem;
00238       if (BO->getOpcode() == Instruction::UDiv)
00239         Rem = Builder->CreateURem(Op0BO, Op1BO);
00240       else
00241         Rem = Builder->CreateSRem(Op0BO, Op1BO);
00242       Rem->takeName(BO);
00243 
00244       if (Op1BO == Op1C)
00245         return BinaryOperator::CreateSub(Op0BO, Rem);
00246       return BinaryOperator::CreateSub(Rem, Op0BO);
00247     }
00248   }
00249 
00250   /// i1 mul -> i1 and.
00251   if (I.getType()->getScalarType()->isIntegerTy(1))
00252     return BinaryOperator::CreateAnd(Op0, Op1);
00253 
00254   // X*(1 << Y) --> X << Y
00255   // (1 << Y)*X --> X << Y
00256   {
00257     Value *Y;
00258     if (match(Op0, m_Shl(m_One(), m_Value(Y))))
00259       return BinaryOperator::CreateShl(Op1, Y);
00260     if (match(Op1, m_Shl(m_One(), m_Value(Y))))
00261       return BinaryOperator::CreateShl(Op0, Y);
00262   }
00263 
00264   // If one of the operands of the multiply is a cast from a boolean value, then
00265   // we know the bool is either zero or one, so this is a 'masking' multiply.
00266   //   X * Y (where Y is 0 or 1) -> X & (0-Y)
00267   if (!I.getType()->isVectorTy()) {
00268     // -2 is "-1 << 1" so it is all bits set except the low one.
00269     APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true);
00270 
00271     Value *BoolCast = 0, *OtherOp = 0;
00272     if (MaskedValueIsZero(Op0, Negative2))
00273       BoolCast = Op0, OtherOp = Op1;
00274     else if (MaskedValueIsZero(Op1, Negative2))
00275       BoolCast = Op1, OtherOp = Op0;
00276 
00277     if (BoolCast) {
00278       Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()),
00279                                     BoolCast);
00280       return BinaryOperator::CreateAnd(V, OtherOp);
00281     }
00282   }
00283 
00284   return Changed ? &I : 0;
00285 }
00286 
00287 //
00288 // Detect pattern:
00289 //
00290 // log2(Y*0.5)
00291 //
00292 // And check for corresponding fast math flags
00293 //
00294 
00295 static void detectLog2OfHalf(Value *&Op, Value *&Y, IntrinsicInst *&Log2) {
00296 
00297    if (!Op->hasOneUse())
00298      return;
00299 
00300    IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op);
00301    if (!II)
00302      return;
00303    if (II->getIntrinsicID() != Intrinsic::log2 || !II->hasUnsafeAlgebra())
00304      return;
00305    Log2 = II;
00306 
00307    Value *OpLog2Of = II->getArgOperand(0);
00308    if (!OpLog2Of->hasOneUse())
00309      return;
00310 
00311    Instruction *I = dyn_cast<Instruction>(OpLog2Of);
00312    if (!I)
00313      return;
00314    if (I->getOpcode() != Instruction::FMul || !I->hasUnsafeAlgebra())
00315      return;
00316 
00317    if (match(I->getOperand(0), m_SpecificFP(0.5)))
00318      Y = I->getOperand(1);
00319    else if (match(I->getOperand(1), m_SpecificFP(0.5)))
00320      Y = I->getOperand(0);
00321 }
00322 
00323 static bool isFiniteNonZeroFp(Constant *C) {
00324   if (C->getType()->isVectorTy()) {
00325     for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E;
00326          ++I) {
00327       ConstantFP *CFP = dyn_cast<ConstantFP>(C->getAggregateElement(I));
00328       if (!CFP || !CFP->getValueAPF().isFiniteNonZero())
00329         return false;
00330     }
00331     return true;
00332   }
00333 
00334   return isa<ConstantFP>(C) &&
00335          cast<ConstantFP>(C)->getValueAPF().isFiniteNonZero();
00336 }
00337 
00338 static bool isNormalFp(Constant *C) {
00339   if (C->getType()->isVectorTy()) {
00340     for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E;
00341          ++I) {
00342       ConstantFP *CFP = dyn_cast<ConstantFP>(C->getAggregateElement(I));
00343       if (!CFP || !CFP->getValueAPF().isNormal())
00344         return false;
00345     }
00346     return true;
00347   }
00348 
00349   return isa<ConstantFP>(C) && cast<ConstantFP>(C)->getValueAPF().isNormal();
00350 }
00351 
00352 /// Helper function of InstCombiner::visitFMul(BinaryOperator(). It returns
00353 /// true iff the given value is FMul or FDiv with one and only one operand
00354 /// being a normal constant (i.e. not Zero/NaN/Infinity).
00355 static bool isFMulOrFDivWithConstant(Value *V) {
00356   Instruction *I = dyn_cast<Instruction>(V);
00357   if (!I || (I->getOpcode() != Instruction::FMul &&
00358              I->getOpcode() != Instruction::FDiv))
00359     return false;
00360 
00361   Constant *C0 = dyn_cast<Constant>(I->getOperand(0));
00362   Constant *C1 = dyn_cast<Constant>(I->getOperand(1));
00363 
00364   if (C0 && C1)
00365     return false;
00366 
00367   return (C0 && isFiniteNonZeroFp(C0)) || (C1 && isFiniteNonZeroFp(C1));
00368 }
00369 
00370 /// foldFMulConst() is a helper routine of InstCombiner::visitFMul().
00371 /// The input \p FMulOrDiv is a FMul/FDiv with one and only one operand
00372 /// being a constant (i.e. isFMulOrFDivWithConstant(FMulOrDiv) == true).
00373 /// This function is to simplify "FMulOrDiv * C" and returns the
00374 /// resulting expression. Note that this function could return NULL in
00375 /// case the constants cannot be folded into a normal floating-point.
00376 ///
00377 Value *InstCombiner::foldFMulConst(Instruction *FMulOrDiv, Constant *C,
00378                                    Instruction *InsertBefore) {
00379   assert(isFMulOrFDivWithConstant(FMulOrDiv) && "V is invalid");
00380 
00381   Value *Opnd0 = FMulOrDiv->getOperand(0);
00382   Value *Opnd1 = FMulOrDiv->getOperand(1);
00383 
00384   Constant *C0 = dyn_cast<Constant>(Opnd0);
00385   Constant *C1 = dyn_cast<Constant>(Opnd1);
00386 
00387   BinaryOperator *R = 0;
00388 
00389   // (X * C0) * C => X * (C0*C)
00390   if (FMulOrDiv->getOpcode() == Instruction::FMul) {
00391     Constant *F = ConstantExpr::getFMul(C1 ? C1 : C0, C);
00392     if (isNormalFp(F))
00393       R = BinaryOperator::CreateFMul(C1 ? Opnd0 : Opnd1, F);
00394   } else {
00395     if (C0) {
00396       // (C0 / X) * C => (C0 * C) / X
00397       if (FMulOrDiv->hasOneUse()) {
00398         // It would otherwise introduce another div.
00399         Constant *F = ConstantExpr::getFMul(C0, C);
00400         if (isNormalFp(F))
00401           R = BinaryOperator::CreateFDiv(F, Opnd1);
00402       }
00403     } else {
00404       // (X / C1) * C => X * (C/C1) if C/C1 is not a denormal
00405       Constant *F = ConstantExpr::getFDiv(C, C1);
00406       if (isNormalFp(F)) {
00407         R = BinaryOperator::CreateFMul(Opnd0, F);
00408       } else {
00409         // (X / C1) * C => X / (C1/C)
00410         Constant *F = ConstantExpr::getFDiv(C1, C);
00411         if (isNormalFp(F))
00412           R = BinaryOperator::CreateFDiv(Opnd0, F);
00413       }
00414     }
00415   }
00416 
00417   if (R) {
00418     R->setHasUnsafeAlgebra(true);
00419     InsertNewInstWith(R, *InsertBefore);
00420   }
00421 
00422   return R;
00423 }
00424 
00425 Instruction *InstCombiner::visitFMul(BinaryOperator &I) {
00426   bool Changed = SimplifyAssociativeOrCommutative(I);
00427   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
00428 
00429   if (isa<Constant>(Op0))
00430     std::swap(Op0, Op1);
00431 
00432   if (Value *V = SimplifyFMulInst(Op0, Op1, I.getFastMathFlags(), DL))
00433     return ReplaceInstUsesWith(I, V);
00434 
00435   bool AllowReassociate = I.hasUnsafeAlgebra();
00436 
00437   // Simplify mul instructions with a constant RHS.
00438   if (isa<Constant>(Op1)) {
00439     // Try to fold constant mul into select arguments.
00440     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
00441       if (Instruction *R = FoldOpIntoSelect(I, SI))
00442         return R;
00443 
00444     if (isa<PHINode>(Op0))
00445       if (Instruction *NV = FoldOpIntoPhi(I))
00446         return NV;
00447 
00448     // (fmul X, -1.0) --> (fsub -0.0, X)
00449     if (match(Op1, m_SpecificFP(-1.0))) {
00450       Constant *NegZero = ConstantFP::getNegativeZero(Op1->getType());
00451       Instruction *RI = BinaryOperator::CreateFSub(NegZero, Op0);
00452       RI->copyFastMathFlags(&I);
00453       return RI;
00454     }
00455 
00456     Constant *C = cast<Constant>(Op1);
00457     if (AllowReassociate && isFiniteNonZeroFp(C)) {
00458       // Let MDC denote an expression in one of these forms:
00459       // X * C, C/X, X/C, where C is a constant.
00460       //
00461       // Try to simplify "MDC * Constant"
00462       if (isFMulOrFDivWithConstant(Op0))
00463         if (Value *V = foldFMulConst(cast<Instruction>(Op0), C, &I))
00464           return ReplaceInstUsesWith(I, V);
00465 
00466       // (MDC +/- C1) * C => (MDC * C) +/- (C1 * C)
00467       Instruction *FAddSub = dyn_cast<Instruction>(Op0);
00468       if (FAddSub &&
00469           (FAddSub->getOpcode() == Instruction::FAdd ||
00470            FAddSub->getOpcode() == Instruction::FSub)) {
00471         Value *Opnd0 = FAddSub->getOperand(0);
00472         Value *Opnd1 = FAddSub->getOperand(1);
00473         Constant *C0 = dyn_cast<Constant>(Opnd0);
00474         Constant *C1 = dyn_cast<Constant>(Opnd1);
00475         bool Swap = false;
00476         if (C0) {
00477           std::swap(C0, C1);
00478           std::swap(Opnd0, Opnd1);
00479           Swap = true;
00480         }
00481 
00482         if (C1 && isFiniteNonZeroFp(C1) && isFMulOrFDivWithConstant(Opnd0)) {
00483           Value *M1 = ConstantExpr::getFMul(C1, C);
00484           Value *M0 = isNormalFp(cast<Constant>(M1)) ?
00485                       foldFMulConst(cast<Instruction>(Opnd0), C, &I) :
00486                       0;
00487           if (M0 && M1) {
00488             if (Swap && FAddSub->getOpcode() == Instruction::FSub)
00489               std::swap(M0, M1);
00490 
00491             Instruction *RI = (FAddSub->getOpcode() == Instruction::FAdd)
00492                                   ? BinaryOperator::CreateFAdd(M0, M1)
00493                                   : BinaryOperator::CreateFSub(M0, M1);
00494             RI->copyFastMathFlags(&I);
00495             return RI;
00496           }
00497         }
00498       }
00499     }
00500   }
00501 
00502 
00503   // Under unsafe algebra do:
00504   // X * log2(0.5*Y) = X*log2(Y) - X
00505   if (I.hasUnsafeAlgebra()) {
00506     Value *OpX = NULL;
00507     Value *OpY = NULL;
00508     IntrinsicInst *Log2;
00509     detectLog2OfHalf(Op0, OpY, Log2);
00510     if (OpY) {
00511       OpX = Op1;
00512     } else {
00513       detectLog2OfHalf(Op1, OpY, Log2);
00514       if (OpY) {
00515         OpX = Op0;
00516       }
00517     }
00518     // if pattern detected emit alternate sequence
00519     if (OpX && OpY) {
00520       BuilderTy::FastMathFlagGuard Guard(*Builder);
00521       Builder->SetFastMathFlags(Log2->getFastMathFlags());
00522       Log2->setArgOperand(0, OpY);
00523       Value *FMulVal = Builder->CreateFMul(OpX, Log2);
00524       Value *FSub = Builder->CreateFSub(FMulVal, OpX);
00525       FSub->takeName(&I);
00526       return ReplaceInstUsesWith(I, FSub);
00527     }
00528   }
00529 
00530   // Handle symmetric situation in a 2-iteration loop
00531   Value *Opnd0 = Op0;
00532   Value *Opnd1 = Op1;
00533   for (int i = 0; i < 2; i++) {
00534     bool IgnoreZeroSign = I.hasNoSignedZeros();
00535     if (BinaryOperator::isFNeg(Opnd0, IgnoreZeroSign)) {
00536       BuilderTy::FastMathFlagGuard Guard(*Builder);
00537       Builder->SetFastMathFlags(I.getFastMathFlags());
00538 
00539       Value *N0 = dyn_castFNegVal(Opnd0, IgnoreZeroSign);
00540       Value *N1 = dyn_castFNegVal(Opnd1, IgnoreZeroSign);
00541 
00542       // -X * -Y => X*Y
00543       if (N1) {
00544         Value *FMul = Builder->CreateFMul(N0, N1);
00545         FMul->takeName(&I);
00546         return ReplaceInstUsesWith(I, FMul);
00547       }
00548 
00549       if (Opnd0->hasOneUse()) {
00550         // -X * Y => -(X*Y) (Promote negation as high as possible)
00551         Value *T = Builder->CreateFMul(N0, Opnd1);
00552         Value *Neg = Builder->CreateFNeg(T);
00553         Neg->takeName(&I);
00554         return ReplaceInstUsesWith(I, Neg);
00555       }
00556     }
00557 
00558     // (X*Y) * X => (X*X) * Y where Y != X
00559     //  The purpose is two-fold:
00560     //   1) to form a power expression (of X).
00561     //   2) potentially shorten the critical path: After transformation, the
00562     //  latency of the instruction Y is amortized by the expression of X*X,
00563     //  and therefore Y is in a "less critical" position compared to what it
00564     //  was before the transformation.
00565     //
00566     if (AllowReassociate) {
00567       Value *Opnd0_0, *Opnd0_1;
00568       if (Opnd0->hasOneUse() &&
00569           match(Opnd0, m_FMul(m_Value(Opnd0_0), m_Value(Opnd0_1)))) {
00570         Value *Y = 0;
00571         if (Opnd0_0 == Opnd1 && Opnd0_1 != Opnd1)
00572           Y = Opnd0_1;
00573         else if (Opnd0_1 == Opnd1 && Opnd0_0 != Opnd1)
00574           Y = Opnd0_0;
00575 
00576         if (Y) {
00577           BuilderTy::FastMathFlagGuard Guard(*Builder);
00578           Builder->SetFastMathFlags(I.getFastMathFlags());
00579           Value *T = Builder->CreateFMul(Opnd1, Opnd1);
00580 
00581           Value *R = Builder->CreateFMul(T, Y);
00582           R->takeName(&I);
00583           return ReplaceInstUsesWith(I, R);
00584         }
00585       }
00586     }
00587 
00588     // B * (uitofp i1 C) -> select C, B, 0
00589     if (I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) {
00590       Value *LHS = Op0, *RHS = Op1;
00591       Value *B, *C;
00592       if (!match(RHS, m_UIToFP(m_Value(C))))
00593         std::swap(LHS, RHS);
00594 
00595       if (match(RHS, m_UIToFP(m_Value(C))) &&
00596           C->getType()->getScalarType()->isIntegerTy(1)) {
00597         B = LHS;
00598         Value *Zero = ConstantFP::getNegativeZero(B->getType());
00599         return SelectInst::Create(C, B, Zero);
00600       }
00601     }
00602 
00603     // A * (1 - uitofp i1 C) -> select C, 0, A
00604     if (I.hasNoNaNs() && I.hasNoInfs() && I.hasNoSignedZeros()) {
00605       Value *LHS = Op0, *RHS = Op1;
00606       Value *A, *C;
00607       if (!match(RHS, m_FSub(m_FPOne(), m_UIToFP(m_Value(C)))))
00608         std::swap(LHS, RHS);
00609 
00610       if (match(RHS, m_FSub(m_FPOne(), m_UIToFP(m_Value(C)))) &&
00611           C->getType()->getScalarType()->isIntegerTy(1)) {
00612         A = LHS;
00613         Value *Zero = ConstantFP::getNegativeZero(A->getType());
00614         return SelectInst::Create(C, Zero, A);
00615       }
00616     }
00617 
00618     if (!isa<Constant>(Op1))
00619       std::swap(Opnd0, Opnd1);
00620     else
00621       break;
00622   }
00623 
00624   return Changed ? &I : 0;
00625 }
00626 
00627 /// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select
00628 /// instruction.
00629 bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) {
00630   SelectInst *SI = cast<SelectInst>(I.getOperand(1));
00631 
00632   // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
00633   int NonNullOperand = -1;
00634   if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1)))
00635     if (ST->isNullValue())
00636       NonNullOperand = 2;
00637   // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
00638   if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2)))
00639     if (ST->isNullValue())
00640       NonNullOperand = 1;
00641 
00642   if (NonNullOperand == -1)
00643     return false;
00644 
00645   Value *SelectCond = SI->getOperand(0);
00646 
00647   // Change the div/rem to use 'Y' instead of the select.
00648   I.setOperand(1, SI->getOperand(NonNullOperand));
00649 
00650   // Okay, we know we replace the operand of the div/rem with 'Y' with no
00651   // problem.  However, the select, or the condition of the select may have
00652   // multiple uses.  Based on our knowledge that the operand must be non-zero,
00653   // propagate the known value for the select into other uses of it, and
00654   // propagate a known value of the condition into its other users.
00655 
00656   // If the select and condition only have a single use, don't bother with this,
00657   // early exit.
00658   if (SI->use_empty() && SelectCond->hasOneUse())
00659     return true;
00660 
00661   // Scan the current block backward, looking for other uses of SI.
00662   BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin();
00663 
00664   while (BBI != BBFront) {
00665     --BBI;
00666     // If we found a call to a function, we can't assume it will return, so
00667     // information from below it cannot be propagated above it.
00668     if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI))
00669       break;
00670 
00671     // Replace uses of the select or its condition with the known values.
00672     for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end();
00673          I != E; ++I) {
00674       if (*I == SI) {
00675         *I = SI->getOperand(NonNullOperand);
00676         Worklist.Add(BBI);
00677       } else if (*I == SelectCond) {
00678         *I = Builder->getInt1(NonNullOperand == 1);
00679         Worklist.Add(BBI);
00680       }
00681     }
00682 
00683     // If we past the instruction, quit looking for it.
00684     if (&*BBI == SI)
00685       SI = 0;
00686     if (&*BBI == SelectCond)
00687       SelectCond = 0;
00688 
00689     // If we ran out of things to eliminate, break out of the loop.
00690     if (SelectCond == 0 && SI == 0)
00691       break;
00692 
00693   }
00694   return true;
00695 }
00696 
00697 
00698 /// This function implements the transforms common to both integer division
00699 /// instructions (udiv and sdiv). It is called by the visitors to those integer
00700 /// division instructions.
00701 /// @brief Common integer divide transforms
00702 Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
00703   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
00704 
00705   // The RHS is known non-zero.
00706   if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) {
00707     I.setOperand(1, V);
00708     return &I;
00709   }
00710 
00711   // Handle cases involving: [su]div X, (select Cond, Y, Z)
00712   // This does not apply for fdiv.
00713   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
00714     return &I;
00715 
00716   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
00717     // (X / C1) / C2  -> X / (C1*C2)
00718     if (Instruction *LHS = dyn_cast<Instruction>(Op0))
00719       if (Instruction::BinaryOps(LHS->getOpcode()) == I.getOpcode())
00720         if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) {
00721           if (MultiplyOverflows(RHS, LHSRHS,
00722                                 I.getOpcode()==Instruction::SDiv))
00723             return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
00724           return BinaryOperator::Create(I.getOpcode(), LHS->getOperand(0),
00725                                         ConstantExpr::getMul(RHS, LHSRHS));
00726         }
00727 
00728     if (!RHS->isZero()) { // avoid X udiv 0
00729       if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
00730         if (Instruction *R = FoldOpIntoSelect(I, SI))
00731           return R;
00732       if (isa<PHINode>(Op0))
00733         if (Instruction *NV = FoldOpIntoPhi(I))
00734           return NV;
00735     }
00736   }
00737 
00738   // See if we can fold away this div instruction.
00739   if (SimplifyDemandedInstructionBits(I))
00740     return &I;
00741 
00742   // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
00743   Value *X = 0, *Z = 0;
00744   if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1
00745     bool isSigned = I.getOpcode() == Instruction::SDiv;
00746     if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
00747         (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
00748       return BinaryOperator::Create(I.getOpcode(), X, Op1);
00749   }
00750 
00751   return 0;
00752 }
00753 
00754 /// dyn_castZExtVal - Checks if V is a zext or constant that can
00755 /// be truncated to Ty without losing bits.
00756 static Value *dyn_castZExtVal(Value *V, Type *Ty) {
00757   if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) {
00758     if (Z->getSrcTy() == Ty)
00759       return Z->getOperand(0);
00760   } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) {
00761     if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth())
00762       return ConstantExpr::getTrunc(C, Ty);
00763   }
00764   return 0;
00765 }
00766 
00767 namespace {
00768 const unsigned MaxDepth = 6;
00769 typedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1,
00770                                           const BinaryOperator &I,
00771                                           InstCombiner &IC);
00772 
00773 /// \brief Used to maintain state for visitUDivOperand().
00774 struct UDivFoldAction {
00775   FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this
00776                                 ///< operand.  This can be zero if this action
00777                                 ///< joins two actions together.
00778 
00779   Value *OperandToFold;         ///< Which operand to fold.
00780   union {
00781     Instruction *FoldResult;    ///< The instruction returned when FoldAction is
00782                                 ///< invoked.
00783 
00784     size_t SelectLHSIdx;        ///< Stores the LHS action index if this action
00785                                 ///< joins two actions together.
00786   };
00787 
00788   UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
00789       : FoldAction(FA), OperandToFold(InputOperand), FoldResult(0) {}
00790   UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
00791       : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
00792 };
00793 }
00794 
00795 // X udiv 2^C -> X >> C
00796 static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1,
00797                                     const BinaryOperator &I, InstCombiner &IC) {
00798   const APInt &C = cast<Constant>(Op1)->getUniqueInteger();
00799   BinaryOperator *LShr = BinaryOperator::CreateLShr(
00800       Op0, ConstantInt::get(Op0->getType(), C.logBase2()));
00801   if (I.isExact()) LShr->setIsExact();
00802   return LShr;
00803 }
00804 
00805 // X udiv C, where C >= signbit
00806 static Instruction *foldUDivNegCst(Value *Op0, Value *Op1,
00807                                    const BinaryOperator &I, InstCombiner &IC) {
00808   Value *ICI = IC.Builder->CreateICmpULT(Op0, cast<ConstantInt>(Op1));
00809 
00810   return SelectInst::Create(ICI, Constant::getNullValue(I.getType()),
00811                             ConstantInt::get(I.getType(), 1));
00812 }
00813 
00814 // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
00815 static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
00816                                 InstCombiner &IC) {
00817   Instruction *ShiftLeft = cast<Instruction>(Op1);
00818   if (isa<ZExtInst>(ShiftLeft))
00819     ShiftLeft = cast<Instruction>(ShiftLeft->getOperand(0));
00820 
00821   const APInt &CI =
00822       cast<Constant>(ShiftLeft->getOperand(0))->getUniqueInteger();
00823   Value *N = ShiftLeft->getOperand(1);
00824   if (CI != 1)
00825     N = IC.Builder->CreateAdd(N, ConstantInt::get(N->getType(), CI.logBase2()));
00826   if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1))
00827     N = IC.Builder->CreateZExt(N, Z->getDestTy());
00828   BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
00829   if (I.isExact()) LShr->setIsExact();
00830   return LShr;
00831 }
00832 
00833 // \brief Recursively visits the possible right hand operands of a udiv
00834 // instruction, seeing through select instructions, to determine if we can
00835 // replace the udiv with something simpler.  If we find that an operand is not
00836 // able to simplify the udiv, we abort the entire transformation.
00837 static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
00838                                SmallVectorImpl<UDivFoldAction> &Actions,
00839                                unsigned Depth = 0) {
00840   // Check to see if this is an unsigned division with an exact power of 2,
00841   // if so, convert to a right shift.
00842   if (match(Op1, m_Power2())) {
00843     Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1));
00844     return Actions.size();
00845   }
00846 
00847   if (ConstantInt *C = dyn_cast<ConstantInt>(Op1))
00848     // X udiv C, where C >= signbit
00849     if (C->getValue().isNegative()) {
00850       Actions.push_back(UDivFoldAction(foldUDivNegCst, C));
00851       return Actions.size();
00852     }
00853 
00854   // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
00855   if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
00856       match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
00857     Actions.push_back(UDivFoldAction(foldUDivShl, Op1));
00858     return Actions.size();
00859   }
00860 
00861   // The remaining tests are all recursive, so bail out if we hit the limit.
00862   if (Depth++ == MaxDepth)
00863     return 0;
00864 
00865   if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
00866     if (size_t LHSIdx = visitUDivOperand(Op0, SI->getOperand(1), I, Actions))
00867       if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions)) {
00868         Actions.push_back(UDivFoldAction((FoldUDivOperandCb)0, Op1, LHSIdx-1));
00869         return Actions.size();
00870       }
00871 
00872   return 0;
00873 }
00874 
00875 Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
00876   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
00877 
00878   if (Value *V = SimplifyUDivInst(Op0, Op1, DL))
00879     return ReplaceInstUsesWith(I, V);
00880 
00881   // Handle the integer div common cases
00882   if (Instruction *Common = commonIDivTransforms(I))
00883     return Common;
00884 
00885   // (x lshr C1) udiv C2 --> x udiv (C2 << C1)
00886   if (Constant *C2 = dyn_cast<Constant>(Op1)) {
00887     Value *X;
00888     Constant *C1;
00889     if (match(Op0, m_LShr(m_Value(X), m_Constant(C1))))
00890       return BinaryOperator::CreateUDiv(X, ConstantExpr::getShl(C2, C1));
00891   }
00892 
00893   // (zext A) udiv (zext B) --> zext (A udiv B)
00894   if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0))
00895     if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy()))
00896       return new ZExtInst(Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div",
00897                                               I.isExact()),
00898                           I.getType());
00899 
00900   // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
00901   SmallVector<UDivFoldAction, 6> UDivActions;
00902   if (visitUDivOperand(Op0, Op1, I, UDivActions))
00903     for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) {
00904       FoldUDivOperandCb Action = UDivActions[i].FoldAction;
00905       Value *ActionOp1 = UDivActions[i].OperandToFold;
00906       Instruction *Inst;
00907       if (Action)
00908         Inst = Action(Op0, ActionOp1, I, *this);
00909       else {
00910         // This action joins two actions together.  The RHS of this action is
00911         // simply the last action we processed, we saved the LHS action index in
00912         // the joining action.
00913         size_t SelectRHSIdx = i - 1;
00914         Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult;
00915         size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx;
00916         Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult;
00917         Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
00918                                   SelectLHS, SelectRHS);
00919       }
00920 
00921       // If this is the last action to process, return it to the InstCombiner.
00922       // Otherwise, we insert it before the UDiv and record it so that we may
00923       // use it as part of a joining action (i.e., a SelectInst).
00924       if (e - i != 1) {
00925         Inst->insertBefore(&I);
00926         UDivActions[i].FoldResult = Inst;
00927       } else
00928         return Inst;
00929     }
00930 
00931   return 0;
00932 }
00933 
00934 Instruction *InstCombiner::visitSDiv(BinaryOperator &I) {
00935   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
00936 
00937   if (Value *V = SimplifySDivInst(Op0, Op1, DL))
00938     return ReplaceInstUsesWith(I, V);
00939 
00940   // Handle the integer div common cases
00941   if (Instruction *Common = commonIDivTransforms(I))
00942     return Common;
00943 
00944   // sdiv X, -1 == -X
00945   if (match(Op1, m_AllOnes()))
00946     return BinaryOperator::CreateNeg(Op0);
00947 
00948   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
00949     // sdiv X, C  -->  ashr exact X, log2(C)
00950     if (I.isExact() && RHS->getValue().isNonNegative() &&
00951         RHS->getValue().isPowerOf2()) {
00952       Value *ShAmt = llvm::ConstantInt::get(RHS->getType(),
00953                                             RHS->getValue().exactLogBase2());
00954       return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName());
00955     }
00956   }
00957 
00958   if (Constant *RHS = dyn_cast<Constant>(Op1)) {
00959     // -X/C  -->  X/-C  provided the negation doesn't overflow.
00960     if (SubOperator *Sub = dyn_cast<SubOperator>(Op0))
00961       if (match(Sub->getOperand(0), m_Zero()) && Sub->hasNoSignedWrap())
00962         return BinaryOperator::CreateSDiv(Sub->getOperand(1),
00963                                           ConstantExpr::getNeg(RHS));
00964   }
00965 
00966   // If the sign bits of both operands are zero (i.e. we can prove they are
00967   // unsigned inputs), turn this into a udiv.
00968   if (I.getType()->isIntegerTy()) {
00969     APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits()));
00970     if (MaskedValueIsZero(Op0, Mask)) {
00971       if (MaskedValueIsZero(Op1, Mask)) {
00972         // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
00973         return BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
00974       }
00975 
00976       if (match(Op1, m_Shl(m_Power2(), m_Value()))) {
00977         // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
00978         // Safe because the only negative value (1 << Y) can take on is
00979         // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
00980         // the sign bit set.
00981         return BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
00982       }
00983     }
00984   }
00985 
00986   return 0;
00987 }
00988 
00989 /// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special
00990 /// FP value and:
00991 ///    1) 1/C is exact, or
00992 ///    2) reciprocal is allowed.
00993 /// If the conversion was successful, the simplified expression "X * 1/C" is
00994 /// returned; otherwise, NULL is returned.
00995 ///
00996 static Instruction *CvtFDivConstToReciprocal(Value *Dividend,
00997                                              Constant *Divisor,
00998                                              bool AllowReciprocal) {
00999   if (!isa<ConstantFP>(Divisor)) // TODO: handle vectors.
01000     return 0;
01001 
01002   const APFloat &FpVal = cast<ConstantFP>(Divisor)->getValueAPF();
01003   APFloat Reciprocal(FpVal.getSemantics());
01004   bool Cvt = FpVal.getExactInverse(&Reciprocal);
01005 
01006   if (!Cvt && AllowReciprocal && FpVal.isFiniteNonZero()) {
01007     Reciprocal = APFloat(FpVal.getSemantics(), 1.0f);
01008     (void)Reciprocal.divide(FpVal, APFloat::rmNearestTiesToEven);
01009     Cvt = !Reciprocal.isDenormal();
01010   }
01011 
01012   if (!Cvt)
01013     return 0;
01014 
01015   ConstantFP *R;
01016   R = ConstantFP::get(Dividend->getType()->getContext(), Reciprocal);
01017   return BinaryOperator::CreateFMul(Dividend, R);
01018 }
01019 
01020 Instruction *InstCombiner::visitFDiv(BinaryOperator &I) {
01021   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
01022 
01023   if (Value *V = SimplifyFDivInst(Op0, Op1, DL))
01024     return ReplaceInstUsesWith(I, V);
01025 
01026   if (isa<Constant>(Op0))
01027     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
01028       if (Instruction *R = FoldOpIntoSelect(I, SI))
01029         return R;
01030 
01031   bool AllowReassociate = I.hasUnsafeAlgebra();
01032   bool AllowReciprocal = I.hasAllowReciprocal();
01033 
01034   if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
01035     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
01036       if (Instruction *R = FoldOpIntoSelect(I, SI))
01037         return R;
01038 
01039     if (AllowReassociate) {
01040       Constant *C1 = 0;
01041       Constant *C2 = Op1C;
01042       Value *X;
01043       Instruction *Res = 0;
01044 
01045       if (match(Op0, m_FMul(m_Value(X), m_Constant(C1)))) {
01046         // (X*C1)/C2 => X * (C1/C2)
01047         //
01048         Constant *C = ConstantExpr::getFDiv(C1, C2);
01049         if (isNormalFp(C))
01050           Res = BinaryOperator::CreateFMul(X, C);
01051       } else if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
01052         // (X/C1)/C2 => X /(C2*C1) [=> X * 1/(C2*C1) if reciprocal is allowed]
01053         //
01054         Constant *C = ConstantExpr::getFMul(C1, C2);
01055         if (isNormalFp(C)) {
01056           Res = CvtFDivConstToReciprocal(X, C, AllowReciprocal);
01057           if (!Res)
01058             Res = BinaryOperator::CreateFDiv(X, C);
01059         }
01060       }
01061 
01062       if (Res) {
01063         Res->setFastMathFlags(I.getFastMathFlags());
01064         return Res;
01065       }
01066     }
01067 
01068     // X / C => X * 1/C
01069     if (Instruction *T = CvtFDivConstToReciprocal(Op0, Op1C, AllowReciprocal)) {
01070       T->copyFastMathFlags(&I);
01071       return T;
01072     }
01073 
01074     return 0;
01075   }
01076 
01077   if (AllowReassociate && isa<Constant>(Op0)) {
01078     Constant *C1 = cast<Constant>(Op0), *C2;
01079     Constant *Fold = 0;
01080     Value *X;
01081     bool CreateDiv = true;
01082 
01083     // C1 / (X*C2) => (C1/C2) / X
01084     if (match(Op1, m_FMul(m_Value(X), m_Constant(C2))))
01085       Fold = ConstantExpr::getFDiv(C1, C2);
01086     else if (match(Op1, m_FDiv(m_Value(X), m_Constant(C2)))) {
01087       // C1 / (X/C2) => (C1*C2) / X
01088       Fold = ConstantExpr::getFMul(C1, C2);
01089     } else if (match(Op1, m_FDiv(m_Constant(C2), m_Value(X)))) {
01090       // C1 / (C2/X) => (C1/C2) * X
01091       Fold = ConstantExpr::getFDiv(C1, C2);
01092       CreateDiv = false;
01093     }
01094 
01095     if (Fold && isNormalFp(Fold)) {
01096       Instruction *R = CreateDiv ? BinaryOperator::CreateFDiv(Fold, X)
01097                                  : BinaryOperator::CreateFMul(X, Fold);
01098       R->setFastMathFlags(I.getFastMathFlags());
01099       return R;
01100     }
01101     return 0;
01102   }
01103 
01104   if (AllowReassociate) {
01105     Value *X, *Y;
01106     Value *NewInst = 0;
01107     Instruction *SimpR = 0;
01108 
01109     if (Op0->hasOneUse() && match(Op0, m_FDiv(m_Value(X), m_Value(Y)))) {
01110       // (X/Y) / Z => X / (Y*Z)
01111       //
01112       if (!isa<Constant>(Y) || !isa<Constant>(Op1)) {
01113         NewInst = Builder->CreateFMul(Y, Op1);
01114         if (Instruction *RI = dyn_cast<Instruction>(NewInst)) {
01115           FastMathFlags Flags = I.getFastMathFlags();
01116           Flags &= cast<Instruction>(Op0)->getFastMathFlags();
01117           RI->setFastMathFlags(Flags);
01118         }
01119         SimpR = BinaryOperator::CreateFDiv(X, NewInst);
01120       }
01121     } else if (Op1->hasOneUse() && match(Op1, m_FDiv(m_Value(X), m_Value(Y)))) {
01122       // Z / (X/Y) => Z*Y / X
01123       //
01124       if (!isa<Constant>(Y) || !isa<Constant>(Op0)) {
01125         NewInst = Builder->CreateFMul(Op0, Y);
01126         if (Instruction *RI = dyn_cast<Instruction>(NewInst)) {
01127           FastMathFlags Flags = I.getFastMathFlags();
01128           Flags &= cast<Instruction>(Op1)->getFastMathFlags();
01129           RI->setFastMathFlags(Flags);
01130         }
01131         SimpR = BinaryOperator::CreateFDiv(NewInst, X);
01132       }
01133     }
01134 
01135     if (NewInst) {
01136       if (Instruction *T = dyn_cast<Instruction>(NewInst))
01137         T->setDebugLoc(I.getDebugLoc());
01138       SimpR->setFastMathFlags(I.getFastMathFlags());
01139       return SimpR;
01140     }
01141   }
01142 
01143   return 0;
01144 }
01145 
01146 /// This function implements the transforms common to both integer remainder
01147 /// instructions (urem and srem). It is called by the visitors to those integer
01148 /// remainder instructions.
01149 /// @brief Common integer remainder transforms
01150 Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) {
01151   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
01152 
01153   // The RHS is known non-zero.
01154   if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this)) {
01155     I.setOperand(1, V);
01156     return &I;
01157   }
01158 
01159   // Handle cases involving: rem X, (select Cond, Y, Z)
01160   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
01161     return &I;
01162 
01163   if (isa<Constant>(Op1)) {
01164     if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
01165       if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
01166         if (Instruction *R = FoldOpIntoSelect(I, SI))
01167           return R;
01168       } else if (isa<PHINode>(Op0I)) {
01169         if (Instruction *NV = FoldOpIntoPhi(I))
01170           return NV;
01171       }
01172 
01173       // See if we can fold away this rem instruction.
01174       if (SimplifyDemandedInstructionBits(I))
01175         return &I;
01176     }
01177   }
01178 
01179   return 0;
01180 }
01181 
01182 Instruction *InstCombiner::visitURem(BinaryOperator &I) {
01183   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
01184 
01185   if (Value *V = SimplifyURemInst(Op0, Op1, DL))
01186     return ReplaceInstUsesWith(I, V);
01187 
01188   if (Instruction *common = commonIRemTransforms(I))
01189     return common;
01190 
01191   // (zext A) urem (zext B) --> zext (A urem B)
01192   if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0))
01193     if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy()))
01194       return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1),
01195                           I.getType());
01196 
01197   // X urem Y -> X and Y-1, where Y is a power of 2,
01198   if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/true)) {
01199     Constant *N1 = Constant::getAllOnesValue(I.getType());
01200     Value *Add = Builder->CreateAdd(Op1, N1);
01201     return BinaryOperator::CreateAnd(Op0, Add);
01202   }
01203 
01204   // 1 urem X -> zext(X != 1)
01205   if (match(Op0, m_One())) {
01206     Value *Cmp = Builder->CreateICmpNE(Op1, Op0);
01207     Value *Ext = Builder->CreateZExt(Cmp, I.getType());
01208     return ReplaceInstUsesWith(I, Ext);
01209   }
01210 
01211   return 0;
01212 }
01213 
01214 Instruction *InstCombiner::visitSRem(BinaryOperator &I) {
01215   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
01216 
01217   if (Value *V = SimplifySRemInst(Op0, Op1, DL))
01218     return ReplaceInstUsesWith(I, V);
01219 
01220   // Handle the integer rem common cases
01221   if (Instruction *Common = commonIRemTransforms(I))
01222     return Common;
01223 
01224   if (Value *RHSNeg = dyn_castNegVal(Op1))
01225     if (!isa<Constant>(RHSNeg) ||
01226         (isa<ConstantInt>(RHSNeg) &&
01227          cast<ConstantInt>(RHSNeg)->getValue().isStrictlyPositive())) {
01228       // X % -Y -> X % Y
01229       Worklist.AddValue(I.getOperand(1));
01230       I.setOperand(1, RHSNeg);
01231       return &I;
01232     }
01233 
01234   // If the sign bits of both operands are zero (i.e. we can prove they are
01235   // unsigned inputs), turn this into a urem.
01236   if (I.getType()->isIntegerTy()) {
01237     APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits()));
01238     if (MaskedValueIsZero(Op1, Mask) && MaskedValueIsZero(Op0, Mask)) {
01239       // X srem Y -> X urem Y, iff X and Y don't have sign bit set
01240       return BinaryOperator::CreateURem(Op0, Op1, I.getName());
01241     }
01242   }
01243 
01244   // If it's a constant vector, flip any negative values positive.
01245   if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
01246     Constant *C = cast<Constant>(Op1);
01247     unsigned VWidth = C->getType()->getVectorNumElements();
01248 
01249     bool hasNegative = false;
01250     bool hasMissing = false;
01251     for (unsigned i = 0; i != VWidth; ++i) {
01252       Constant *Elt = C->getAggregateElement(i);
01253       if (Elt == 0) {
01254         hasMissing = true;
01255         break;
01256       }
01257 
01258       if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
01259         if (RHS->isNegative())
01260           hasNegative = true;
01261     }
01262 
01263     if (hasNegative && !hasMissing) {
01264       SmallVector<Constant *, 16> Elts(VWidth);
01265       for (unsigned i = 0; i != VWidth; ++i) {
01266         Elts[i] = C->getAggregateElement(i);  // Handle undef, etc.
01267         if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
01268           if (RHS->isNegative())
01269             Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
01270         }
01271       }
01272 
01273       Constant *NewRHSV = ConstantVector::get(Elts);
01274       if (NewRHSV != C) {  // Don't loop on -MININT
01275         Worklist.AddValue(I.getOperand(1));
01276         I.setOperand(1, NewRHSV);
01277         return &I;
01278       }
01279     }
01280   }
01281 
01282   return 0;
01283 }
01284 
01285 Instruction *InstCombiner::visitFRem(BinaryOperator &I) {
01286   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
01287 
01288   if (Value *V = SimplifyFRemInst(Op0, Op1, DL))
01289     return ReplaceInstUsesWith(I, V);
01290 
01291   // Handle cases involving: rem X, (select Cond, Y, Z)
01292   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
01293     return &I;
01294 
01295   return 0;
01296 }