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