1f4a2713aSLionel Sambuc //===- InstCombineMulDivRem.cpp -------------------------------------------===//
2f4a2713aSLionel Sambuc //
3f4a2713aSLionel Sambuc // The LLVM Compiler Infrastructure
4f4a2713aSLionel Sambuc //
5f4a2713aSLionel Sambuc // This file is distributed under the University of Illinois Open Source
6f4a2713aSLionel Sambuc // License. See LICENSE.TXT for details.
7f4a2713aSLionel Sambuc //
8f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
9f4a2713aSLionel Sambuc //
10f4a2713aSLionel Sambuc // This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv,
11f4a2713aSLionel Sambuc // srem, urem, frem.
12f4a2713aSLionel Sambuc //
13f4a2713aSLionel Sambuc //===----------------------------------------------------------------------===//
14f4a2713aSLionel Sambuc
15f4a2713aSLionel Sambuc #include "InstCombine.h"
16f4a2713aSLionel Sambuc #include "llvm/Analysis/InstructionSimplify.h"
17f4a2713aSLionel Sambuc #include "llvm/IR/IntrinsicInst.h"
18*0a6a1f1dSLionel Sambuc #include "llvm/IR/PatternMatch.h"
19f4a2713aSLionel Sambuc using namespace llvm;
20f4a2713aSLionel Sambuc using namespace PatternMatch;
21f4a2713aSLionel Sambuc
22*0a6a1f1dSLionel Sambuc #define DEBUG_TYPE "instcombine"
23*0a6a1f1dSLionel Sambuc
24f4a2713aSLionel Sambuc
25f4a2713aSLionel Sambuc /// simplifyValueKnownNonZero - The specific integer value is used in a context
26f4a2713aSLionel Sambuc /// where it is known to be non-zero. If this allows us to simplify the
27f4a2713aSLionel Sambuc /// computation, do so and return the new operand, otherwise return null.
simplifyValueKnownNonZero(Value * V,InstCombiner & IC,Instruction * CxtI)28*0a6a1f1dSLionel Sambuc static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC,
29*0a6a1f1dSLionel Sambuc Instruction *CxtI) {
30f4a2713aSLionel Sambuc // If V has multiple uses, then we would have to do more analysis to determine
31f4a2713aSLionel Sambuc // if this is safe. For example, the use could be in dynamically unreached
32f4a2713aSLionel Sambuc // code.
33*0a6a1f1dSLionel Sambuc if (!V->hasOneUse()) return nullptr;
34f4a2713aSLionel Sambuc
35f4a2713aSLionel Sambuc bool MadeChange = false;
36f4a2713aSLionel Sambuc
37f4a2713aSLionel Sambuc // ((1 << A) >>u B) --> (1 << (A-B))
38f4a2713aSLionel Sambuc // Because V cannot be zero, we know that B is less than A.
39*0a6a1f1dSLionel Sambuc Value *A = nullptr, *B = nullptr, *One = nullptr;
40*0a6a1f1dSLionel Sambuc if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) &&
41*0a6a1f1dSLionel Sambuc match(One, m_One())) {
42f4a2713aSLionel Sambuc A = IC.Builder->CreateSub(A, B);
43*0a6a1f1dSLionel Sambuc return IC.Builder->CreateShl(One, A);
44f4a2713aSLionel Sambuc }
45f4a2713aSLionel Sambuc
46f4a2713aSLionel Sambuc // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
47f4a2713aSLionel Sambuc // inexact. Similarly for <<.
48f4a2713aSLionel Sambuc if (BinaryOperator *I = dyn_cast<BinaryOperator>(V))
49*0a6a1f1dSLionel Sambuc if (I->isLogicalShift() &&
50*0a6a1f1dSLionel Sambuc isKnownToBeAPowerOfTwo(I->getOperand(0), false, 0,
51*0a6a1f1dSLionel Sambuc IC.getAssumptionCache(), CxtI,
52*0a6a1f1dSLionel Sambuc IC.getDominatorTree())) {
53f4a2713aSLionel Sambuc // We know that this is an exact/nuw shift and that the input is a
54f4a2713aSLionel Sambuc // non-zero context as well.
55*0a6a1f1dSLionel Sambuc if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) {
56f4a2713aSLionel Sambuc I->setOperand(0, V2);
57f4a2713aSLionel Sambuc MadeChange = true;
58f4a2713aSLionel Sambuc }
59f4a2713aSLionel Sambuc
60f4a2713aSLionel Sambuc if (I->getOpcode() == Instruction::LShr && !I->isExact()) {
61f4a2713aSLionel Sambuc I->setIsExact();
62f4a2713aSLionel Sambuc MadeChange = true;
63f4a2713aSLionel Sambuc }
64f4a2713aSLionel Sambuc
65f4a2713aSLionel Sambuc if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) {
66f4a2713aSLionel Sambuc I->setHasNoUnsignedWrap();
67f4a2713aSLionel Sambuc MadeChange = true;
68f4a2713aSLionel Sambuc }
69f4a2713aSLionel Sambuc }
70f4a2713aSLionel Sambuc
71f4a2713aSLionel Sambuc // TODO: Lots more we could do here:
72f4a2713aSLionel Sambuc // If V is a phi node, we can call this on each of its operands.
73f4a2713aSLionel Sambuc // "select cond, X, 0" can simplify to "X".
74f4a2713aSLionel Sambuc
75*0a6a1f1dSLionel Sambuc return MadeChange ? V : nullptr;
76f4a2713aSLionel Sambuc }
77f4a2713aSLionel Sambuc
78f4a2713aSLionel Sambuc
79f4a2713aSLionel Sambuc /// MultiplyOverflows - True if the multiply can not be expressed in an int
80f4a2713aSLionel Sambuc /// this size.
MultiplyOverflows(const APInt & C1,const APInt & C2,APInt & Product,bool IsSigned)81*0a6a1f1dSLionel Sambuc static bool MultiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
82*0a6a1f1dSLionel Sambuc bool IsSigned) {
83*0a6a1f1dSLionel Sambuc bool Overflow;
84*0a6a1f1dSLionel Sambuc if (IsSigned)
85*0a6a1f1dSLionel Sambuc Product = C1.smul_ov(C2, Overflow);
86*0a6a1f1dSLionel Sambuc else
87*0a6a1f1dSLionel Sambuc Product = C1.umul_ov(C2, Overflow);
88*0a6a1f1dSLionel Sambuc
89*0a6a1f1dSLionel Sambuc return Overflow;
90f4a2713aSLionel Sambuc }
91f4a2713aSLionel Sambuc
92*0a6a1f1dSLionel Sambuc /// \brief True if C2 is a multiple of C1. Quotient contains C2/C1.
IsMultiple(const APInt & C1,const APInt & C2,APInt & Quotient,bool IsSigned)93*0a6a1f1dSLionel Sambuc static bool IsMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
94*0a6a1f1dSLionel Sambuc bool IsSigned) {
95*0a6a1f1dSLionel Sambuc assert(C1.getBitWidth() == C2.getBitWidth() &&
96*0a6a1f1dSLionel Sambuc "Inconsistent width of constants!");
97f4a2713aSLionel Sambuc
98*0a6a1f1dSLionel Sambuc APInt Remainder(C1.getBitWidth(), /*Val=*/0ULL, IsSigned);
99*0a6a1f1dSLionel Sambuc if (IsSigned)
100*0a6a1f1dSLionel Sambuc APInt::sdivrem(C1, C2, Quotient, Remainder);
101*0a6a1f1dSLionel Sambuc else
102*0a6a1f1dSLionel Sambuc APInt::udivrem(C1, C2, Quotient, Remainder);
103f4a2713aSLionel Sambuc
104*0a6a1f1dSLionel Sambuc return Remainder.isMinValue();
105f4a2713aSLionel Sambuc }
106f4a2713aSLionel Sambuc
107f4a2713aSLionel Sambuc /// \brief A helper routine of InstCombiner::visitMul().
108f4a2713aSLionel Sambuc ///
109f4a2713aSLionel Sambuc /// If C is a vector of known powers of 2, then this function returns
110f4a2713aSLionel Sambuc /// a new vector obtained from C replacing each element with its logBase2.
111f4a2713aSLionel Sambuc /// Return a null pointer otherwise.
getLogBase2Vector(ConstantDataVector * CV)112f4a2713aSLionel Sambuc static Constant *getLogBase2Vector(ConstantDataVector *CV) {
113f4a2713aSLionel Sambuc const APInt *IVal;
114f4a2713aSLionel Sambuc SmallVector<Constant *, 4> Elts;
115f4a2713aSLionel Sambuc
116f4a2713aSLionel Sambuc for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) {
117f4a2713aSLionel Sambuc Constant *Elt = CV->getElementAsConstant(I);
118f4a2713aSLionel Sambuc if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2())
119*0a6a1f1dSLionel Sambuc return nullptr;
120f4a2713aSLionel Sambuc Elts.push_back(ConstantInt::get(Elt->getType(), IVal->logBase2()));
121f4a2713aSLionel Sambuc }
122f4a2713aSLionel Sambuc
123f4a2713aSLionel Sambuc return ConstantVector::get(Elts);
124f4a2713aSLionel Sambuc }
125f4a2713aSLionel Sambuc
126*0a6a1f1dSLionel Sambuc /// \brief Return true if we can prove that:
127*0a6a1f1dSLionel Sambuc /// (mul LHS, RHS) === (mul nsw LHS, RHS)
WillNotOverflowSignedMul(Value * LHS,Value * RHS,Instruction * CxtI)128*0a6a1f1dSLionel Sambuc bool InstCombiner::WillNotOverflowSignedMul(Value *LHS, Value *RHS,
129*0a6a1f1dSLionel Sambuc Instruction *CxtI) {
130*0a6a1f1dSLionel Sambuc // Multiplying n * m significant bits yields a result of n + m significant
131*0a6a1f1dSLionel Sambuc // bits. If the total number of significant bits does not exceed the
132*0a6a1f1dSLionel Sambuc // result bit width (minus 1), there is no overflow.
133*0a6a1f1dSLionel Sambuc // This means if we have enough leading sign bits in the operands
134*0a6a1f1dSLionel Sambuc // we can guarantee that the result does not overflow.
135*0a6a1f1dSLionel Sambuc // Ref: "Hacker's Delight" by Henry Warren
136*0a6a1f1dSLionel Sambuc unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
137*0a6a1f1dSLionel Sambuc
138*0a6a1f1dSLionel Sambuc // Note that underestimating the number of sign bits gives a more
139*0a6a1f1dSLionel Sambuc // conservative answer.
140*0a6a1f1dSLionel Sambuc unsigned SignBits = ComputeNumSignBits(LHS, 0, CxtI) +
141*0a6a1f1dSLionel Sambuc ComputeNumSignBits(RHS, 0, CxtI);
142*0a6a1f1dSLionel Sambuc
143*0a6a1f1dSLionel Sambuc // First handle the easy case: if we have enough sign bits there's
144*0a6a1f1dSLionel Sambuc // definitely no overflow.
145*0a6a1f1dSLionel Sambuc if (SignBits > BitWidth + 1)
146*0a6a1f1dSLionel Sambuc return true;
147*0a6a1f1dSLionel Sambuc
148*0a6a1f1dSLionel Sambuc // There are two ambiguous cases where there can be no overflow:
149*0a6a1f1dSLionel Sambuc // SignBits == BitWidth + 1 and
150*0a6a1f1dSLionel Sambuc // SignBits == BitWidth
151*0a6a1f1dSLionel Sambuc // The second case is difficult to check, therefore we only handle the
152*0a6a1f1dSLionel Sambuc // first case.
153*0a6a1f1dSLionel Sambuc if (SignBits == BitWidth + 1) {
154*0a6a1f1dSLionel Sambuc // It overflows only when both arguments are negative and the true
155*0a6a1f1dSLionel Sambuc // product is exactly the minimum negative number.
156*0a6a1f1dSLionel Sambuc // E.g. mul i16 with 17 sign bits: 0xff00 * 0xff80 = 0x8000
157*0a6a1f1dSLionel Sambuc // For simplicity we just check if at least one side is not negative.
158*0a6a1f1dSLionel Sambuc bool LHSNonNegative, LHSNegative;
159*0a6a1f1dSLionel Sambuc bool RHSNonNegative, RHSNegative;
160*0a6a1f1dSLionel Sambuc ComputeSignBit(LHS, LHSNonNegative, LHSNegative, /*Depth=*/0, CxtI);
161*0a6a1f1dSLionel Sambuc ComputeSignBit(RHS, RHSNonNegative, RHSNegative, /*Depth=*/0, CxtI);
162*0a6a1f1dSLionel Sambuc if (LHSNonNegative || RHSNonNegative)
163*0a6a1f1dSLionel Sambuc return true;
164*0a6a1f1dSLionel Sambuc }
165*0a6a1f1dSLionel Sambuc return false;
166*0a6a1f1dSLionel Sambuc }
167*0a6a1f1dSLionel Sambuc
visitMul(BinaryOperator & I)168f4a2713aSLionel Sambuc Instruction *InstCombiner::visitMul(BinaryOperator &I) {
169f4a2713aSLionel Sambuc bool Changed = SimplifyAssociativeOrCommutative(I);
170f4a2713aSLionel Sambuc Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
171f4a2713aSLionel Sambuc
172*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyVectorOp(I))
173*0a6a1f1dSLionel Sambuc return ReplaceInstUsesWith(I, V);
174*0a6a1f1dSLionel Sambuc
175*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyMulInst(Op0, Op1, DL, TLI, DT, AC))
176f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, V);
177f4a2713aSLionel Sambuc
178f4a2713aSLionel Sambuc if (Value *V = SimplifyUsingDistributiveLaws(I))
179f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, V);
180f4a2713aSLionel Sambuc
181*0a6a1f1dSLionel Sambuc // X * -1 == 0 - X
182*0a6a1f1dSLionel Sambuc if (match(Op1, m_AllOnes())) {
183*0a6a1f1dSLionel Sambuc BinaryOperator *BO = BinaryOperator::CreateNeg(Op0, I.getName());
184*0a6a1f1dSLionel Sambuc if (I.hasNoSignedWrap())
185*0a6a1f1dSLionel Sambuc BO->setHasNoSignedWrap();
186*0a6a1f1dSLionel Sambuc return BO;
187*0a6a1f1dSLionel Sambuc }
188f4a2713aSLionel Sambuc
189f4a2713aSLionel Sambuc // Also allow combining multiply instructions on vectors.
190f4a2713aSLionel Sambuc {
191f4a2713aSLionel Sambuc Value *NewOp;
192f4a2713aSLionel Sambuc Constant *C1, *C2;
193f4a2713aSLionel Sambuc const APInt *IVal;
194f4a2713aSLionel Sambuc if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
195f4a2713aSLionel Sambuc m_Constant(C1))) &&
196*0a6a1f1dSLionel Sambuc match(C1, m_APInt(IVal))) {
197*0a6a1f1dSLionel Sambuc // ((X << C2)*C1) == (X * (C1 << C2))
198*0a6a1f1dSLionel Sambuc Constant *Shl = ConstantExpr::getShl(C1, C2);
199*0a6a1f1dSLionel Sambuc BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0));
200*0a6a1f1dSLionel Sambuc BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl);
201*0a6a1f1dSLionel Sambuc if (I.hasNoUnsignedWrap() && Mul->hasNoUnsignedWrap())
202*0a6a1f1dSLionel Sambuc BO->setHasNoUnsignedWrap();
203*0a6a1f1dSLionel Sambuc if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap() &&
204*0a6a1f1dSLionel Sambuc Shl->isNotMinSignedValue())
205*0a6a1f1dSLionel Sambuc BO->setHasNoSignedWrap();
206*0a6a1f1dSLionel Sambuc return BO;
207*0a6a1f1dSLionel Sambuc }
208f4a2713aSLionel Sambuc
209f4a2713aSLionel Sambuc if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
210*0a6a1f1dSLionel Sambuc Constant *NewCst = nullptr;
211f4a2713aSLionel Sambuc if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2())
212f4a2713aSLionel Sambuc // Replace X*(2^C) with X << C, where C is either a scalar or a splat.
213f4a2713aSLionel Sambuc NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2());
214f4a2713aSLionel Sambuc else if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(C1))
215f4a2713aSLionel Sambuc // Replace X*(2^C) with X << C, where C is a vector of known
216f4a2713aSLionel Sambuc // constant powers of 2.
217f4a2713aSLionel Sambuc NewCst = getLogBase2Vector(CV);
218f4a2713aSLionel Sambuc
219f4a2713aSLionel Sambuc if (NewCst) {
220f4a2713aSLionel Sambuc BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
221*0a6a1f1dSLionel Sambuc
222*0a6a1f1dSLionel Sambuc if (I.hasNoUnsignedWrap())
223*0a6a1f1dSLionel Sambuc Shl->setHasNoUnsignedWrap();
224*0a6a1f1dSLionel Sambuc if (I.hasNoSignedWrap() && NewCst->isNotMinSignedValue())
225*0a6a1f1dSLionel Sambuc Shl->setHasNoSignedWrap();
226*0a6a1f1dSLionel Sambuc
227f4a2713aSLionel Sambuc return Shl;
228f4a2713aSLionel Sambuc }
229f4a2713aSLionel Sambuc }
230f4a2713aSLionel Sambuc }
231f4a2713aSLionel Sambuc
232f4a2713aSLionel Sambuc if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
233f4a2713aSLionel Sambuc // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n
234f4a2713aSLionel Sambuc // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n
235f4a2713aSLionel Sambuc // The "* (2**n)" thus becomes a potential shifting opportunity.
236f4a2713aSLionel Sambuc {
237f4a2713aSLionel Sambuc const APInt & Val = CI->getValue();
238f4a2713aSLionel Sambuc const APInt &PosVal = Val.abs();
239f4a2713aSLionel Sambuc if (Val.isNegative() && PosVal.isPowerOf2()) {
240*0a6a1f1dSLionel Sambuc Value *X = nullptr, *Y = nullptr;
241f4a2713aSLionel Sambuc if (Op0->hasOneUse()) {
242f4a2713aSLionel Sambuc ConstantInt *C1;
243*0a6a1f1dSLionel Sambuc Value *Sub = nullptr;
244f4a2713aSLionel Sambuc if (match(Op0, m_Sub(m_Value(Y), m_Value(X))))
245f4a2713aSLionel Sambuc Sub = Builder->CreateSub(X, Y, "suba");
246f4a2713aSLionel Sambuc else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1))))
247f4a2713aSLionel Sambuc Sub = Builder->CreateSub(Builder->CreateNeg(C1), Y, "subc");
248f4a2713aSLionel Sambuc if (Sub)
249f4a2713aSLionel Sambuc return
250f4a2713aSLionel Sambuc BinaryOperator::CreateMul(Sub,
251f4a2713aSLionel Sambuc ConstantInt::get(Y->getType(), PosVal));
252f4a2713aSLionel Sambuc }
253f4a2713aSLionel Sambuc }
254f4a2713aSLionel Sambuc }
255f4a2713aSLionel Sambuc }
256f4a2713aSLionel Sambuc
257f4a2713aSLionel Sambuc // Simplify mul instructions with a constant RHS.
258f4a2713aSLionel Sambuc if (isa<Constant>(Op1)) {
259f4a2713aSLionel Sambuc // Try to fold constant mul into select arguments.
260f4a2713aSLionel Sambuc if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
261f4a2713aSLionel Sambuc if (Instruction *R = FoldOpIntoSelect(I, SI))
262f4a2713aSLionel Sambuc return R;
263f4a2713aSLionel Sambuc
264f4a2713aSLionel Sambuc if (isa<PHINode>(Op0))
265f4a2713aSLionel Sambuc if (Instruction *NV = FoldOpIntoPhi(I))
266f4a2713aSLionel Sambuc return NV;
267*0a6a1f1dSLionel Sambuc
268*0a6a1f1dSLionel Sambuc // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
269*0a6a1f1dSLionel Sambuc {
270*0a6a1f1dSLionel Sambuc Value *X;
271*0a6a1f1dSLionel Sambuc Constant *C1;
272*0a6a1f1dSLionel Sambuc if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) {
273*0a6a1f1dSLionel Sambuc Value *Mul = Builder->CreateMul(C1, Op1);
274*0a6a1f1dSLionel Sambuc // Only go forward with the transform if C1*CI simplifies to a tidier
275*0a6a1f1dSLionel Sambuc // constant.
276*0a6a1f1dSLionel Sambuc if (!match(Mul, m_Mul(m_Value(), m_Value())))
277*0a6a1f1dSLionel Sambuc return BinaryOperator::CreateAdd(Builder->CreateMul(X, Op1), Mul);
278*0a6a1f1dSLionel Sambuc }
279*0a6a1f1dSLionel Sambuc }
280f4a2713aSLionel Sambuc }
281f4a2713aSLionel Sambuc
282*0a6a1f1dSLionel Sambuc if (Value *Op0v = dyn_castNegVal(Op0)) { // -X * -Y = X*Y
283*0a6a1f1dSLionel Sambuc if (Value *Op1v = dyn_castNegVal(Op1)) {
284*0a6a1f1dSLionel Sambuc BinaryOperator *BO = BinaryOperator::CreateMul(Op0v, Op1v);
285*0a6a1f1dSLionel Sambuc if (I.hasNoSignedWrap() &&
286*0a6a1f1dSLionel Sambuc match(Op0, m_NSWSub(m_Value(), m_Value())) &&
287*0a6a1f1dSLionel Sambuc match(Op1, m_NSWSub(m_Value(), m_Value())))
288*0a6a1f1dSLionel Sambuc BO->setHasNoSignedWrap();
289*0a6a1f1dSLionel Sambuc return BO;
290*0a6a1f1dSLionel Sambuc }
291*0a6a1f1dSLionel Sambuc }
292f4a2713aSLionel Sambuc
293f4a2713aSLionel Sambuc // (X / Y) * Y = X - (X % Y)
294f4a2713aSLionel Sambuc // (X / Y) * -Y = (X % Y) - X
295f4a2713aSLionel Sambuc {
296f4a2713aSLionel Sambuc Value *Op1C = Op1;
297f4a2713aSLionel Sambuc BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0);
298f4a2713aSLionel Sambuc if (!BO ||
299f4a2713aSLionel Sambuc (BO->getOpcode() != Instruction::UDiv &&
300f4a2713aSLionel Sambuc BO->getOpcode() != Instruction::SDiv)) {
301f4a2713aSLionel Sambuc Op1C = Op0;
302f4a2713aSLionel Sambuc BO = dyn_cast<BinaryOperator>(Op1);
303f4a2713aSLionel Sambuc }
304f4a2713aSLionel Sambuc Value *Neg = dyn_castNegVal(Op1C);
305f4a2713aSLionel Sambuc if (BO && BO->hasOneUse() &&
306f4a2713aSLionel Sambuc (BO->getOperand(1) == Op1C || BO->getOperand(1) == Neg) &&
307f4a2713aSLionel Sambuc (BO->getOpcode() == Instruction::UDiv ||
308f4a2713aSLionel Sambuc BO->getOpcode() == Instruction::SDiv)) {
309f4a2713aSLionel Sambuc Value *Op0BO = BO->getOperand(0), *Op1BO = BO->getOperand(1);
310f4a2713aSLionel Sambuc
311f4a2713aSLionel Sambuc // If the division is exact, X % Y is zero, so we end up with X or -X.
312f4a2713aSLionel Sambuc if (PossiblyExactOperator *SDiv = dyn_cast<PossiblyExactOperator>(BO))
313f4a2713aSLionel Sambuc if (SDiv->isExact()) {
314f4a2713aSLionel Sambuc if (Op1BO == Op1C)
315f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, Op0BO);
316f4a2713aSLionel Sambuc return BinaryOperator::CreateNeg(Op0BO);
317f4a2713aSLionel Sambuc }
318f4a2713aSLionel Sambuc
319f4a2713aSLionel Sambuc Value *Rem;
320f4a2713aSLionel Sambuc if (BO->getOpcode() == Instruction::UDiv)
321f4a2713aSLionel Sambuc Rem = Builder->CreateURem(Op0BO, Op1BO);
322f4a2713aSLionel Sambuc else
323f4a2713aSLionel Sambuc Rem = Builder->CreateSRem(Op0BO, Op1BO);
324f4a2713aSLionel Sambuc Rem->takeName(BO);
325f4a2713aSLionel Sambuc
326f4a2713aSLionel Sambuc if (Op1BO == Op1C)
327f4a2713aSLionel Sambuc return BinaryOperator::CreateSub(Op0BO, Rem);
328f4a2713aSLionel Sambuc return BinaryOperator::CreateSub(Rem, Op0BO);
329f4a2713aSLionel Sambuc }
330f4a2713aSLionel Sambuc }
331f4a2713aSLionel Sambuc
332f4a2713aSLionel Sambuc /// i1 mul -> i1 and.
333*0a6a1f1dSLionel Sambuc if (I.getType()->getScalarType()->isIntegerTy(1))
334f4a2713aSLionel Sambuc return BinaryOperator::CreateAnd(Op0, Op1);
335f4a2713aSLionel Sambuc
336f4a2713aSLionel Sambuc // X*(1 << Y) --> X << Y
337f4a2713aSLionel Sambuc // (1 << Y)*X --> X << Y
338f4a2713aSLionel Sambuc {
339f4a2713aSLionel Sambuc Value *Y;
340*0a6a1f1dSLionel Sambuc BinaryOperator *BO = nullptr;
341*0a6a1f1dSLionel Sambuc bool ShlNSW = false;
342*0a6a1f1dSLionel Sambuc if (match(Op0, m_Shl(m_One(), m_Value(Y)))) {
343*0a6a1f1dSLionel Sambuc BO = BinaryOperator::CreateShl(Op1, Y);
344*0a6a1f1dSLionel Sambuc ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap();
345*0a6a1f1dSLionel Sambuc } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) {
346*0a6a1f1dSLionel Sambuc BO = BinaryOperator::CreateShl(Op0, Y);
347*0a6a1f1dSLionel Sambuc ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap();
348*0a6a1f1dSLionel Sambuc }
349*0a6a1f1dSLionel Sambuc if (BO) {
350*0a6a1f1dSLionel Sambuc if (I.hasNoUnsignedWrap())
351*0a6a1f1dSLionel Sambuc BO->setHasNoUnsignedWrap();
352*0a6a1f1dSLionel Sambuc if (I.hasNoSignedWrap() && ShlNSW)
353*0a6a1f1dSLionel Sambuc BO->setHasNoSignedWrap();
354*0a6a1f1dSLionel Sambuc return BO;
355*0a6a1f1dSLionel Sambuc }
356f4a2713aSLionel Sambuc }
357f4a2713aSLionel Sambuc
358f4a2713aSLionel Sambuc // If one of the operands of the multiply is a cast from a boolean value, then
359f4a2713aSLionel Sambuc // we know the bool is either zero or one, so this is a 'masking' multiply.
360f4a2713aSLionel Sambuc // X * Y (where Y is 0 or 1) -> X & (0-Y)
361f4a2713aSLionel Sambuc if (!I.getType()->isVectorTy()) {
362f4a2713aSLionel Sambuc // -2 is "-1 << 1" so it is all bits set except the low one.
363f4a2713aSLionel Sambuc APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true);
364f4a2713aSLionel Sambuc
365*0a6a1f1dSLionel Sambuc Value *BoolCast = nullptr, *OtherOp = nullptr;
366*0a6a1f1dSLionel Sambuc if (MaskedValueIsZero(Op0, Negative2, 0, &I))
367f4a2713aSLionel Sambuc BoolCast = Op0, OtherOp = Op1;
368*0a6a1f1dSLionel Sambuc else if (MaskedValueIsZero(Op1, Negative2, 0, &I))
369f4a2713aSLionel Sambuc BoolCast = Op1, OtherOp = Op0;
370f4a2713aSLionel Sambuc
371f4a2713aSLionel Sambuc if (BoolCast) {
372f4a2713aSLionel Sambuc Value *V = Builder->CreateSub(Constant::getNullValue(I.getType()),
373f4a2713aSLionel Sambuc BoolCast);
374f4a2713aSLionel Sambuc return BinaryOperator::CreateAnd(V, OtherOp);
375f4a2713aSLionel Sambuc }
376f4a2713aSLionel Sambuc }
377f4a2713aSLionel Sambuc
378*0a6a1f1dSLionel Sambuc if (!I.hasNoSignedWrap() && WillNotOverflowSignedMul(Op0, Op1, &I)) {
379*0a6a1f1dSLionel Sambuc Changed = true;
380*0a6a1f1dSLionel Sambuc I.setHasNoSignedWrap(true);
381f4a2713aSLionel Sambuc }
382f4a2713aSLionel Sambuc
383*0a6a1f1dSLionel Sambuc if (!I.hasNoUnsignedWrap() &&
384*0a6a1f1dSLionel Sambuc computeOverflowForUnsignedMul(Op0, Op1, &I) ==
385*0a6a1f1dSLionel Sambuc OverflowResult::NeverOverflows) {
386*0a6a1f1dSLionel Sambuc Changed = true;
387*0a6a1f1dSLionel Sambuc I.setHasNoUnsignedWrap(true);
388*0a6a1f1dSLionel Sambuc }
389f4a2713aSLionel Sambuc
390*0a6a1f1dSLionel Sambuc return Changed ? &I : nullptr;
391*0a6a1f1dSLionel Sambuc }
392*0a6a1f1dSLionel Sambuc
393*0a6a1f1dSLionel Sambuc /// Detect pattern log2(Y * 0.5) with corresponding fast math flags.
detectLog2OfHalf(Value * & Op,Value * & Y,IntrinsicInst * & Log2)394f4a2713aSLionel Sambuc static void detectLog2OfHalf(Value *&Op, Value *&Y, IntrinsicInst *&Log2) {
395f4a2713aSLionel Sambuc if (!Op->hasOneUse())
396f4a2713aSLionel Sambuc return;
397f4a2713aSLionel Sambuc
398f4a2713aSLionel Sambuc IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op);
399f4a2713aSLionel Sambuc if (!II)
400f4a2713aSLionel Sambuc return;
401f4a2713aSLionel Sambuc if (II->getIntrinsicID() != Intrinsic::log2 || !II->hasUnsafeAlgebra())
402f4a2713aSLionel Sambuc return;
403f4a2713aSLionel Sambuc Log2 = II;
404f4a2713aSLionel Sambuc
405f4a2713aSLionel Sambuc Value *OpLog2Of = II->getArgOperand(0);
406f4a2713aSLionel Sambuc if (!OpLog2Of->hasOneUse())
407f4a2713aSLionel Sambuc return;
408f4a2713aSLionel Sambuc
409f4a2713aSLionel Sambuc Instruction *I = dyn_cast<Instruction>(OpLog2Of);
410f4a2713aSLionel Sambuc if (!I)
411f4a2713aSLionel Sambuc return;
412f4a2713aSLionel Sambuc if (I->getOpcode() != Instruction::FMul || !I->hasUnsafeAlgebra())
413f4a2713aSLionel Sambuc return;
414f4a2713aSLionel Sambuc
415*0a6a1f1dSLionel Sambuc if (match(I->getOperand(0), m_SpecificFP(0.5)))
416f4a2713aSLionel Sambuc Y = I->getOperand(1);
417*0a6a1f1dSLionel Sambuc else if (match(I->getOperand(1), m_SpecificFP(0.5)))
418f4a2713aSLionel Sambuc Y = I->getOperand(0);
419f4a2713aSLionel Sambuc }
420f4a2713aSLionel Sambuc
isFiniteNonZeroFp(Constant * C)421*0a6a1f1dSLionel Sambuc static bool isFiniteNonZeroFp(Constant *C) {
422*0a6a1f1dSLionel Sambuc if (C->getType()->isVectorTy()) {
423*0a6a1f1dSLionel Sambuc for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E;
424*0a6a1f1dSLionel Sambuc ++I) {
425*0a6a1f1dSLionel Sambuc ConstantFP *CFP = dyn_cast<ConstantFP>(C->getAggregateElement(I));
426*0a6a1f1dSLionel Sambuc if (!CFP || !CFP->getValueAPF().isFiniteNonZero())
427*0a6a1f1dSLionel Sambuc return false;
428*0a6a1f1dSLionel Sambuc }
429*0a6a1f1dSLionel Sambuc return true;
430*0a6a1f1dSLionel Sambuc }
431*0a6a1f1dSLionel Sambuc
432*0a6a1f1dSLionel Sambuc return isa<ConstantFP>(C) &&
433*0a6a1f1dSLionel Sambuc cast<ConstantFP>(C)->getValueAPF().isFiniteNonZero();
434*0a6a1f1dSLionel Sambuc }
435*0a6a1f1dSLionel Sambuc
isNormalFp(Constant * C)436*0a6a1f1dSLionel Sambuc static bool isNormalFp(Constant *C) {
437*0a6a1f1dSLionel Sambuc if (C->getType()->isVectorTy()) {
438*0a6a1f1dSLionel Sambuc for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E;
439*0a6a1f1dSLionel Sambuc ++I) {
440*0a6a1f1dSLionel Sambuc ConstantFP *CFP = dyn_cast<ConstantFP>(C->getAggregateElement(I));
441*0a6a1f1dSLionel Sambuc if (!CFP || !CFP->getValueAPF().isNormal())
442*0a6a1f1dSLionel Sambuc return false;
443*0a6a1f1dSLionel Sambuc }
444*0a6a1f1dSLionel Sambuc return true;
445*0a6a1f1dSLionel Sambuc }
446*0a6a1f1dSLionel Sambuc
447*0a6a1f1dSLionel Sambuc return isa<ConstantFP>(C) && cast<ConstantFP>(C)->getValueAPF().isNormal();
448*0a6a1f1dSLionel Sambuc }
449*0a6a1f1dSLionel Sambuc
450f4a2713aSLionel Sambuc /// Helper function of InstCombiner::visitFMul(BinaryOperator(). It returns
451f4a2713aSLionel Sambuc /// true iff the given value is FMul or FDiv with one and only one operand
452f4a2713aSLionel Sambuc /// being a normal constant (i.e. not Zero/NaN/Infinity).
isFMulOrFDivWithConstant(Value * V)453f4a2713aSLionel Sambuc static bool isFMulOrFDivWithConstant(Value *V) {
454f4a2713aSLionel Sambuc Instruction *I = dyn_cast<Instruction>(V);
455f4a2713aSLionel Sambuc if (!I || (I->getOpcode() != Instruction::FMul &&
456f4a2713aSLionel Sambuc I->getOpcode() != Instruction::FDiv))
457f4a2713aSLionel Sambuc return false;
458f4a2713aSLionel Sambuc
459*0a6a1f1dSLionel Sambuc Constant *C0 = dyn_cast<Constant>(I->getOperand(0));
460*0a6a1f1dSLionel Sambuc Constant *C1 = dyn_cast<Constant>(I->getOperand(1));
461f4a2713aSLionel Sambuc
462f4a2713aSLionel Sambuc if (C0 && C1)
463f4a2713aSLionel Sambuc return false;
464f4a2713aSLionel Sambuc
465*0a6a1f1dSLionel Sambuc return (C0 && isFiniteNonZeroFp(C0)) || (C1 && isFiniteNonZeroFp(C1));
466f4a2713aSLionel Sambuc }
467f4a2713aSLionel Sambuc
468f4a2713aSLionel Sambuc /// foldFMulConst() is a helper routine of InstCombiner::visitFMul().
469f4a2713aSLionel Sambuc /// The input \p FMulOrDiv is a FMul/FDiv with one and only one operand
470f4a2713aSLionel Sambuc /// being a constant (i.e. isFMulOrFDivWithConstant(FMulOrDiv) == true).
471f4a2713aSLionel Sambuc /// This function is to simplify "FMulOrDiv * C" and returns the
472f4a2713aSLionel Sambuc /// resulting expression. Note that this function could return NULL in
473f4a2713aSLionel Sambuc /// case the constants cannot be folded into a normal floating-point.
474f4a2713aSLionel Sambuc ///
foldFMulConst(Instruction * FMulOrDiv,Constant * C,Instruction * InsertBefore)475*0a6a1f1dSLionel Sambuc Value *InstCombiner::foldFMulConst(Instruction *FMulOrDiv, Constant *C,
476f4a2713aSLionel Sambuc Instruction *InsertBefore) {
477f4a2713aSLionel Sambuc assert(isFMulOrFDivWithConstant(FMulOrDiv) && "V is invalid");
478f4a2713aSLionel Sambuc
479f4a2713aSLionel Sambuc Value *Opnd0 = FMulOrDiv->getOperand(0);
480f4a2713aSLionel Sambuc Value *Opnd1 = FMulOrDiv->getOperand(1);
481f4a2713aSLionel Sambuc
482*0a6a1f1dSLionel Sambuc Constant *C0 = dyn_cast<Constant>(Opnd0);
483*0a6a1f1dSLionel Sambuc Constant *C1 = dyn_cast<Constant>(Opnd1);
484f4a2713aSLionel Sambuc
485*0a6a1f1dSLionel Sambuc BinaryOperator *R = nullptr;
486f4a2713aSLionel Sambuc
487f4a2713aSLionel Sambuc // (X * C0) * C => X * (C0*C)
488f4a2713aSLionel Sambuc if (FMulOrDiv->getOpcode() == Instruction::FMul) {
489f4a2713aSLionel Sambuc Constant *F = ConstantExpr::getFMul(C1 ? C1 : C0, C);
490*0a6a1f1dSLionel Sambuc if (isNormalFp(F))
491f4a2713aSLionel Sambuc R = BinaryOperator::CreateFMul(C1 ? Opnd0 : Opnd1, F);
492f4a2713aSLionel Sambuc } else {
493f4a2713aSLionel Sambuc if (C0) {
494f4a2713aSLionel Sambuc // (C0 / X) * C => (C0 * C) / X
495f4a2713aSLionel Sambuc if (FMulOrDiv->hasOneUse()) {
496f4a2713aSLionel Sambuc // It would otherwise introduce another div.
497*0a6a1f1dSLionel Sambuc Constant *F = ConstantExpr::getFMul(C0, C);
498f4a2713aSLionel Sambuc if (isNormalFp(F))
499f4a2713aSLionel Sambuc R = BinaryOperator::CreateFDiv(F, Opnd1);
500f4a2713aSLionel Sambuc }
501f4a2713aSLionel Sambuc } else {
502f4a2713aSLionel Sambuc // (X / C1) * C => X * (C/C1) if C/C1 is not a denormal
503*0a6a1f1dSLionel Sambuc Constant *F = ConstantExpr::getFDiv(C, C1);
504f4a2713aSLionel Sambuc if (isNormalFp(F)) {
505f4a2713aSLionel Sambuc R = BinaryOperator::CreateFMul(Opnd0, F);
506f4a2713aSLionel Sambuc } else {
507f4a2713aSLionel Sambuc // (X / C1) * C => X / (C1/C)
508f4a2713aSLionel Sambuc Constant *F = ConstantExpr::getFDiv(C1, C);
509*0a6a1f1dSLionel Sambuc if (isNormalFp(F))
510f4a2713aSLionel Sambuc R = BinaryOperator::CreateFDiv(Opnd0, F);
511f4a2713aSLionel Sambuc }
512f4a2713aSLionel Sambuc }
513f4a2713aSLionel Sambuc }
514f4a2713aSLionel Sambuc
515f4a2713aSLionel Sambuc if (R) {
516f4a2713aSLionel Sambuc R->setHasUnsafeAlgebra(true);
517f4a2713aSLionel Sambuc InsertNewInstWith(R, *InsertBefore);
518f4a2713aSLionel Sambuc }
519f4a2713aSLionel Sambuc
520f4a2713aSLionel Sambuc return R;
521f4a2713aSLionel Sambuc }
522f4a2713aSLionel Sambuc
visitFMul(BinaryOperator & I)523f4a2713aSLionel Sambuc Instruction *InstCombiner::visitFMul(BinaryOperator &I) {
524f4a2713aSLionel Sambuc bool Changed = SimplifyAssociativeOrCommutative(I);
525f4a2713aSLionel Sambuc Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
526f4a2713aSLionel Sambuc
527*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyVectorOp(I))
528*0a6a1f1dSLionel Sambuc return ReplaceInstUsesWith(I, V);
529*0a6a1f1dSLionel Sambuc
530f4a2713aSLionel Sambuc if (isa<Constant>(Op0))
531f4a2713aSLionel Sambuc std::swap(Op0, Op1);
532f4a2713aSLionel Sambuc
533*0a6a1f1dSLionel Sambuc if (Value *V =
534*0a6a1f1dSLionel Sambuc SimplifyFMulInst(Op0, Op1, I.getFastMathFlags(), DL, TLI, DT, AC))
535f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, V);
536f4a2713aSLionel Sambuc
537f4a2713aSLionel Sambuc bool AllowReassociate = I.hasUnsafeAlgebra();
538f4a2713aSLionel Sambuc
539f4a2713aSLionel Sambuc // Simplify mul instructions with a constant RHS.
540f4a2713aSLionel Sambuc if (isa<Constant>(Op1)) {
541f4a2713aSLionel Sambuc // Try to fold constant mul into select arguments.
542f4a2713aSLionel Sambuc if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
543f4a2713aSLionel Sambuc if (Instruction *R = FoldOpIntoSelect(I, SI))
544f4a2713aSLionel Sambuc return R;
545f4a2713aSLionel Sambuc
546f4a2713aSLionel Sambuc if (isa<PHINode>(Op0))
547f4a2713aSLionel Sambuc if (Instruction *NV = FoldOpIntoPhi(I))
548f4a2713aSLionel Sambuc return NV;
549f4a2713aSLionel Sambuc
550*0a6a1f1dSLionel Sambuc // (fmul X, -1.0) --> (fsub -0.0, X)
551*0a6a1f1dSLionel Sambuc if (match(Op1, m_SpecificFP(-1.0))) {
552*0a6a1f1dSLionel Sambuc Constant *NegZero = ConstantFP::getNegativeZero(Op1->getType());
553*0a6a1f1dSLionel Sambuc Instruction *RI = BinaryOperator::CreateFSub(NegZero, Op0);
554*0a6a1f1dSLionel Sambuc RI->copyFastMathFlags(&I);
555*0a6a1f1dSLionel Sambuc return RI;
556*0a6a1f1dSLionel Sambuc }
557*0a6a1f1dSLionel Sambuc
558*0a6a1f1dSLionel Sambuc Constant *C = cast<Constant>(Op1);
559*0a6a1f1dSLionel Sambuc if (AllowReassociate && isFiniteNonZeroFp(C)) {
560f4a2713aSLionel Sambuc // Let MDC denote an expression in one of these forms:
561f4a2713aSLionel Sambuc // X * C, C/X, X/C, where C is a constant.
562f4a2713aSLionel Sambuc //
563f4a2713aSLionel Sambuc // Try to simplify "MDC * Constant"
564*0a6a1f1dSLionel Sambuc if (isFMulOrFDivWithConstant(Op0))
565*0a6a1f1dSLionel Sambuc if (Value *V = foldFMulConst(cast<Instruction>(Op0), C, &I))
566f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, V);
567f4a2713aSLionel Sambuc
568f4a2713aSLionel Sambuc // (MDC +/- C1) * C => (MDC * C) +/- (C1 * C)
569f4a2713aSLionel Sambuc Instruction *FAddSub = dyn_cast<Instruction>(Op0);
570f4a2713aSLionel Sambuc if (FAddSub &&
571f4a2713aSLionel Sambuc (FAddSub->getOpcode() == Instruction::FAdd ||
572f4a2713aSLionel Sambuc FAddSub->getOpcode() == Instruction::FSub)) {
573f4a2713aSLionel Sambuc Value *Opnd0 = FAddSub->getOperand(0);
574f4a2713aSLionel Sambuc Value *Opnd1 = FAddSub->getOperand(1);
575*0a6a1f1dSLionel Sambuc Constant *C0 = dyn_cast<Constant>(Opnd0);
576*0a6a1f1dSLionel Sambuc Constant *C1 = dyn_cast<Constant>(Opnd1);
577f4a2713aSLionel Sambuc bool Swap = false;
578f4a2713aSLionel Sambuc if (C0) {
579f4a2713aSLionel Sambuc std::swap(C0, C1);
580f4a2713aSLionel Sambuc std::swap(Opnd0, Opnd1);
581f4a2713aSLionel Sambuc Swap = true;
582f4a2713aSLionel Sambuc }
583f4a2713aSLionel Sambuc
584*0a6a1f1dSLionel Sambuc if (C1 && isFiniteNonZeroFp(C1) && isFMulOrFDivWithConstant(Opnd0)) {
585f4a2713aSLionel Sambuc Value *M1 = ConstantExpr::getFMul(C1, C);
586*0a6a1f1dSLionel Sambuc Value *M0 = isNormalFp(cast<Constant>(M1)) ?
587f4a2713aSLionel Sambuc foldFMulConst(cast<Instruction>(Opnd0), C, &I) :
588*0a6a1f1dSLionel Sambuc nullptr;
589f4a2713aSLionel Sambuc if (M0 && M1) {
590f4a2713aSLionel Sambuc if (Swap && FAddSub->getOpcode() == Instruction::FSub)
591f4a2713aSLionel Sambuc std::swap(M0, M1);
592f4a2713aSLionel Sambuc
593f4a2713aSLionel Sambuc Instruction *RI = (FAddSub->getOpcode() == Instruction::FAdd)
594f4a2713aSLionel Sambuc ? BinaryOperator::CreateFAdd(M0, M1)
595f4a2713aSLionel Sambuc : BinaryOperator::CreateFSub(M0, M1);
596f4a2713aSLionel Sambuc RI->copyFastMathFlags(&I);
597f4a2713aSLionel Sambuc return RI;
598f4a2713aSLionel Sambuc }
599f4a2713aSLionel Sambuc }
600f4a2713aSLionel Sambuc }
601f4a2713aSLionel Sambuc }
602f4a2713aSLionel Sambuc }
603f4a2713aSLionel Sambuc
604*0a6a1f1dSLionel Sambuc // sqrt(X) * sqrt(X) -> X
605*0a6a1f1dSLionel Sambuc if (AllowReassociate && (Op0 == Op1))
606*0a6a1f1dSLionel Sambuc if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0))
607*0a6a1f1dSLionel Sambuc if (II->getIntrinsicID() == Intrinsic::sqrt)
608*0a6a1f1dSLionel Sambuc return ReplaceInstUsesWith(I, II->getOperand(0));
609f4a2713aSLionel Sambuc
610f4a2713aSLionel Sambuc // Under unsafe algebra do:
611f4a2713aSLionel Sambuc // X * log2(0.5*Y) = X*log2(Y) - X
612*0a6a1f1dSLionel Sambuc if (AllowReassociate) {
613*0a6a1f1dSLionel Sambuc Value *OpX = nullptr;
614*0a6a1f1dSLionel Sambuc Value *OpY = nullptr;
615f4a2713aSLionel Sambuc IntrinsicInst *Log2;
616f4a2713aSLionel Sambuc detectLog2OfHalf(Op0, OpY, Log2);
617f4a2713aSLionel Sambuc if (OpY) {
618f4a2713aSLionel Sambuc OpX = Op1;
619f4a2713aSLionel Sambuc } else {
620f4a2713aSLionel Sambuc detectLog2OfHalf(Op1, OpY, Log2);
621f4a2713aSLionel Sambuc if (OpY) {
622f4a2713aSLionel Sambuc OpX = Op0;
623f4a2713aSLionel Sambuc }
624f4a2713aSLionel Sambuc }
625f4a2713aSLionel Sambuc // if pattern detected emit alternate sequence
626f4a2713aSLionel Sambuc if (OpX && OpY) {
627f4a2713aSLionel Sambuc BuilderTy::FastMathFlagGuard Guard(*Builder);
628f4a2713aSLionel Sambuc Builder->SetFastMathFlags(Log2->getFastMathFlags());
629f4a2713aSLionel Sambuc Log2->setArgOperand(0, OpY);
630f4a2713aSLionel Sambuc Value *FMulVal = Builder->CreateFMul(OpX, Log2);
631f4a2713aSLionel Sambuc Value *FSub = Builder->CreateFSub(FMulVal, OpX);
632f4a2713aSLionel Sambuc FSub->takeName(&I);
633f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, FSub);
634f4a2713aSLionel Sambuc }
635f4a2713aSLionel Sambuc }
636f4a2713aSLionel Sambuc
637f4a2713aSLionel Sambuc // Handle symmetric situation in a 2-iteration loop
638f4a2713aSLionel Sambuc Value *Opnd0 = Op0;
639f4a2713aSLionel Sambuc Value *Opnd1 = Op1;
640f4a2713aSLionel Sambuc for (int i = 0; i < 2; i++) {
641f4a2713aSLionel Sambuc bool IgnoreZeroSign = I.hasNoSignedZeros();
642f4a2713aSLionel Sambuc if (BinaryOperator::isFNeg(Opnd0, IgnoreZeroSign)) {
643f4a2713aSLionel Sambuc BuilderTy::FastMathFlagGuard Guard(*Builder);
644f4a2713aSLionel Sambuc Builder->SetFastMathFlags(I.getFastMathFlags());
645f4a2713aSLionel Sambuc
646f4a2713aSLionel Sambuc Value *N0 = dyn_castFNegVal(Opnd0, IgnoreZeroSign);
647f4a2713aSLionel Sambuc Value *N1 = dyn_castFNegVal(Opnd1, IgnoreZeroSign);
648f4a2713aSLionel Sambuc
649f4a2713aSLionel Sambuc // -X * -Y => X*Y
650*0a6a1f1dSLionel Sambuc if (N1) {
651*0a6a1f1dSLionel Sambuc Value *FMul = Builder->CreateFMul(N0, N1);
652*0a6a1f1dSLionel Sambuc FMul->takeName(&I);
653*0a6a1f1dSLionel Sambuc return ReplaceInstUsesWith(I, FMul);
654*0a6a1f1dSLionel Sambuc }
655f4a2713aSLionel Sambuc
656f4a2713aSLionel Sambuc if (Opnd0->hasOneUse()) {
657f4a2713aSLionel Sambuc // -X * Y => -(X*Y) (Promote negation as high as possible)
658f4a2713aSLionel Sambuc Value *T = Builder->CreateFMul(N0, Opnd1);
659f4a2713aSLionel Sambuc Value *Neg = Builder->CreateFNeg(T);
660f4a2713aSLionel Sambuc Neg->takeName(&I);
661f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, Neg);
662f4a2713aSLionel Sambuc }
663f4a2713aSLionel Sambuc }
664f4a2713aSLionel Sambuc
665f4a2713aSLionel Sambuc // (X*Y) * X => (X*X) * Y where Y != X
666f4a2713aSLionel Sambuc // The purpose is two-fold:
667f4a2713aSLionel Sambuc // 1) to form a power expression (of X).
668f4a2713aSLionel Sambuc // 2) potentially shorten the critical path: After transformation, the
669f4a2713aSLionel Sambuc // latency of the instruction Y is amortized by the expression of X*X,
670f4a2713aSLionel Sambuc // and therefore Y is in a "less critical" position compared to what it
671f4a2713aSLionel Sambuc // was before the transformation.
672f4a2713aSLionel Sambuc //
673f4a2713aSLionel Sambuc if (AllowReassociate) {
674f4a2713aSLionel Sambuc Value *Opnd0_0, *Opnd0_1;
675f4a2713aSLionel Sambuc if (Opnd0->hasOneUse() &&
676f4a2713aSLionel Sambuc match(Opnd0, m_FMul(m_Value(Opnd0_0), m_Value(Opnd0_1)))) {
677*0a6a1f1dSLionel Sambuc Value *Y = nullptr;
678f4a2713aSLionel Sambuc if (Opnd0_0 == Opnd1 && Opnd0_1 != Opnd1)
679f4a2713aSLionel Sambuc Y = Opnd0_1;
680f4a2713aSLionel Sambuc else if (Opnd0_1 == Opnd1 && Opnd0_0 != Opnd1)
681f4a2713aSLionel Sambuc Y = Opnd0_0;
682f4a2713aSLionel Sambuc
683f4a2713aSLionel Sambuc if (Y) {
684f4a2713aSLionel Sambuc BuilderTy::FastMathFlagGuard Guard(*Builder);
685f4a2713aSLionel Sambuc Builder->SetFastMathFlags(I.getFastMathFlags());
686f4a2713aSLionel Sambuc Value *T = Builder->CreateFMul(Opnd1, Opnd1);
687f4a2713aSLionel Sambuc
688f4a2713aSLionel Sambuc Value *R = Builder->CreateFMul(T, Y);
689f4a2713aSLionel Sambuc R->takeName(&I);
690f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, R);
691f4a2713aSLionel Sambuc }
692f4a2713aSLionel Sambuc }
693f4a2713aSLionel Sambuc }
694f4a2713aSLionel Sambuc
695f4a2713aSLionel Sambuc if (!isa<Constant>(Op1))
696f4a2713aSLionel Sambuc std::swap(Opnd0, Opnd1);
697f4a2713aSLionel Sambuc else
698f4a2713aSLionel Sambuc break;
699f4a2713aSLionel Sambuc }
700f4a2713aSLionel Sambuc
701*0a6a1f1dSLionel Sambuc return Changed ? &I : nullptr;
702f4a2713aSLionel Sambuc }
703f4a2713aSLionel Sambuc
704f4a2713aSLionel Sambuc /// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select
705f4a2713aSLionel Sambuc /// instruction.
SimplifyDivRemOfSelect(BinaryOperator & I)706f4a2713aSLionel Sambuc bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator &I) {
707f4a2713aSLionel Sambuc SelectInst *SI = cast<SelectInst>(I.getOperand(1));
708f4a2713aSLionel Sambuc
709f4a2713aSLionel Sambuc // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
710f4a2713aSLionel Sambuc int NonNullOperand = -1;
711f4a2713aSLionel Sambuc if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1)))
712f4a2713aSLionel Sambuc if (ST->isNullValue())
713f4a2713aSLionel Sambuc NonNullOperand = 2;
714f4a2713aSLionel Sambuc // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
715f4a2713aSLionel Sambuc if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2)))
716f4a2713aSLionel Sambuc if (ST->isNullValue())
717f4a2713aSLionel Sambuc NonNullOperand = 1;
718f4a2713aSLionel Sambuc
719f4a2713aSLionel Sambuc if (NonNullOperand == -1)
720f4a2713aSLionel Sambuc return false;
721f4a2713aSLionel Sambuc
722f4a2713aSLionel Sambuc Value *SelectCond = SI->getOperand(0);
723f4a2713aSLionel Sambuc
724f4a2713aSLionel Sambuc // Change the div/rem to use 'Y' instead of the select.
725f4a2713aSLionel Sambuc I.setOperand(1, SI->getOperand(NonNullOperand));
726f4a2713aSLionel Sambuc
727f4a2713aSLionel Sambuc // Okay, we know we replace the operand of the div/rem with 'Y' with no
728f4a2713aSLionel Sambuc // problem. However, the select, or the condition of the select may have
729f4a2713aSLionel Sambuc // multiple uses. Based on our knowledge that the operand must be non-zero,
730f4a2713aSLionel Sambuc // propagate the known value for the select into other uses of it, and
731f4a2713aSLionel Sambuc // propagate a known value of the condition into its other users.
732f4a2713aSLionel Sambuc
733f4a2713aSLionel Sambuc // If the select and condition only have a single use, don't bother with this,
734f4a2713aSLionel Sambuc // early exit.
735f4a2713aSLionel Sambuc if (SI->use_empty() && SelectCond->hasOneUse())
736f4a2713aSLionel Sambuc return true;
737f4a2713aSLionel Sambuc
738f4a2713aSLionel Sambuc // Scan the current block backward, looking for other uses of SI.
739f4a2713aSLionel Sambuc BasicBlock::iterator BBI = &I, BBFront = I.getParent()->begin();
740f4a2713aSLionel Sambuc
741f4a2713aSLionel Sambuc while (BBI != BBFront) {
742f4a2713aSLionel Sambuc --BBI;
743f4a2713aSLionel Sambuc // If we found a call to a function, we can't assume it will return, so
744f4a2713aSLionel Sambuc // information from below it cannot be propagated above it.
745f4a2713aSLionel Sambuc if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI))
746f4a2713aSLionel Sambuc break;
747f4a2713aSLionel Sambuc
748f4a2713aSLionel Sambuc // Replace uses of the select or its condition with the known values.
749f4a2713aSLionel Sambuc for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end();
750f4a2713aSLionel Sambuc I != E; ++I) {
751f4a2713aSLionel Sambuc if (*I == SI) {
752f4a2713aSLionel Sambuc *I = SI->getOperand(NonNullOperand);
753f4a2713aSLionel Sambuc Worklist.Add(BBI);
754f4a2713aSLionel Sambuc } else if (*I == SelectCond) {
755f4a2713aSLionel Sambuc *I = Builder->getInt1(NonNullOperand == 1);
756f4a2713aSLionel Sambuc Worklist.Add(BBI);
757f4a2713aSLionel Sambuc }
758f4a2713aSLionel Sambuc }
759f4a2713aSLionel Sambuc
760f4a2713aSLionel Sambuc // If we past the instruction, quit looking for it.
761f4a2713aSLionel Sambuc if (&*BBI == SI)
762*0a6a1f1dSLionel Sambuc SI = nullptr;
763f4a2713aSLionel Sambuc if (&*BBI == SelectCond)
764*0a6a1f1dSLionel Sambuc SelectCond = nullptr;
765f4a2713aSLionel Sambuc
766f4a2713aSLionel Sambuc // If we ran out of things to eliminate, break out of the loop.
767*0a6a1f1dSLionel Sambuc if (!SelectCond && !SI)
768f4a2713aSLionel Sambuc break;
769f4a2713aSLionel Sambuc
770f4a2713aSLionel Sambuc }
771f4a2713aSLionel Sambuc return true;
772f4a2713aSLionel Sambuc }
773f4a2713aSLionel Sambuc
774f4a2713aSLionel Sambuc
775f4a2713aSLionel Sambuc /// This function implements the transforms common to both integer division
776f4a2713aSLionel Sambuc /// instructions (udiv and sdiv). It is called by the visitors to those integer
777f4a2713aSLionel Sambuc /// division instructions.
778f4a2713aSLionel Sambuc /// @brief Common integer divide transforms
commonIDivTransforms(BinaryOperator & I)779f4a2713aSLionel Sambuc Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
780f4a2713aSLionel Sambuc Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
781f4a2713aSLionel Sambuc
782f4a2713aSLionel Sambuc // The RHS is known non-zero.
783*0a6a1f1dSLionel Sambuc if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, &I)) {
784f4a2713aSLionel Sambuc I.setOperand(1, V);
785f4a2713aSLionel Sambuc return &I;
786f4a2713aSLionel Sambuc }
787f4a2713aSLionel Sambuc
788f4a2713aSLionel Sambuc // Handle cases involving: [su]div X, (select Cond, Y, Z)
789f4a2713aSLionel Sambuc // This does not apply for fdiv.
790f4a2713aSLionel Sambuc if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
791f4a2713aSLionel Sambuc return &I;
792f4a2713aSLionel Sambuc
793*0a6a1f1dSLionel Sambuc if (Instruction *LHS = dyn_cast<Instruction>(Op0)) {
794*0a6a1f1dSLionel Sambuc const APInt *C2;
795*0a6a1f1dSLionel Sambuc if (match(Op1, m_APInt(C2))) {
796*0a6a1f1dSLionel Sambuc Value *X;
797*0a6a1f1dSLionel Sambuc const APInt *C1;
798*0a6a1f1dSLionel Sambuc bool IsSigned = I.getOpcode() == Instruction::SDiv;
799*0a6a1f1dSLionel Sambuc
800f4a2713aSLionel Sambuc // (X / C1) / C2 -> X / (C1*C2)
801*0a6a1f1dSLionel Sambuc if ((IsSigned && match(LHS, m_SDiv(m_Value(X), m_APInt(C1)))) ||
802*0a6a1f1dSLionel Sambuc (!IsSigned && match(LHS, m_UDiv(m_Value(X), m_APInt(C1))))) {
803*0a6a1f1dSLionel Sambuc APInt Product(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
804*0a6a1f1dSLionel Sambuc if (!MultiplyOverflows(*C1, *C2, Product, IsSigned))
805*0a6a1f1dSLionel Sambuc return BinaryOperator::Create(I.getOpcode(), X,
806*0a6a1f1dSLionel Sambuc ConstantInt::get(I.getType(), Product));
807f4a2713aSLionel Sambuc }
808f4a2713aSLionel Sambuc
809*0a6a1f1dSLionel Sambuc if ((IsSigned && match(LHS, m_NSWMul(m_Value(X), m_APInt(C1)))) ||
810*0a6a1f1dSLionel Sambuc (!IsSigned && match(LHS, m_NUWMul(m_Value(X), m_APInt(C1))))) {
811*0a6a1f1dSLionel Sambuc APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
812*0a6a1f1dSLionel Sambuc
813*0a6a1f1dSLionel Sambuc // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
814*0a6a1f1dSLionel Sambuc if (IsMultiple(*C2, *C1, Quotient, IsSigned)) {
815*0a6a1f1dSLionel Sambuc BinaryOperator *BO = BinaryOperator::Create(
816*0a6a1f1dSLionel Sambuc I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient));
817*0a6a1f1dSLionel Sambuc BO->setIsExact(I.isExact());
818*0a6a1f1dSLionel Sambuc return BO;
819*0a6a1f1dSLionel Sambuc }
820*0a6a1f1dSLionel Sambuc
821*0a6a1f1dSLionel Sambuc // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
822*0a6a1f1dSLionel Sambuc if (IsMultiple(*C1, *C2, Quotient, IsSigned)) {
823*0a6a1f1dSLionel Sambuc BinaryOperator *BO = BinaryOperator::Create(
824*0a6a1f1dSLionel Sambuc Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient));
825*0a6a1f1dSLionel Sambuc BO->setHasNoUnsignedWrap(
826*0a6a1f1dSLionel Sambuc !IsSigned &&
827*0a6a1f1dSLionel Sambuc cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap());
828*0a6a1f1dSLionel Sambuc BO->setHasNoSignedWrap(
829*0a6a1f1dSLionel Sambuc cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap());
830*0a6a1f1dSLionel Sambuc return BO;
831*0a6a1f1dSLionel Sambuc }
832*0a6a1f1dSLionel Sambuc }
833*0a6a1f1dSLionel Sambuc
834*0a6a1f1dSLionel Sambuc if ((IsSigned && match(LHS, m_NSWShl(m_Value(X), m_APInt(C1))) &&
835*0a6a1f1dSLionel Sambuc *C1 != C1->getBitWidth() - 1) ||
836*0a6a1f1dSLionel Sambuc (!IsSigned && match(LHS, m_NUWShl(m_Value(X), m_APInt(C1))))) {
837*0a6a1f1dSLionel Sambuc APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
838*0a6a1f1dSLionel Sambuc APInt C1Shifted = APInt::getOneBitSet(
839*0a6a1f1dSLionel Sambuc C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue()));
840*0a6a1f1dSLionel Sambuc
841*0a6a1f1dSLionel Sambuc // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of C1.
842*0a6a1f1dSLionel Sambuc if (IsMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
843*0a6a1f1dSLionel Sambuc BinaryOperator *BO = BinaryOperator::Create(
844*0a6a1f1dSLionel Sambuc I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient));
845*0a6a1f1dSLionel Sambuc BO->setIsExact(I.isExact());
846*0a6a1f1dSLionel Sambuc return BO;
847*0a6a1f1dSLionel Sambuc }
848*0a6a1f1dSLionel Sambuc
849*0a6a1f1dSLionel Sambuc // (X << C1) / C2 -> X * (C2 >> C1) if C1 is a multiple of C2.
850*0a6a1f1dSLionel Sambuc if (IsMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
851*0a6a1f1dSLionel Sambuc BinaryOperator *BO = BinaryOperator::Create(
852*0a6a1f1dSLionel Sambuc Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient));
853*0a6a1f1dSLionel Sambuc BO->setHasNoUnsignedWrap(
854*0a6a1f1dSLionel Sambuc !IsSigned &&
855*0a6a1f1dSLionel Sambuc cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap());
856*0a6a1f1dSLionel Sambuc BO->setHasNoSignedWrap(
857*0a6a1f1dSLionel Sambuc cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap());
858*0a6a1f1dSLionel Sambuc return BO;
859*0a6a1f1dSLionel Sambuc }
860*0a6a1f1dSLionel Sambuc }
861*0a6a1f1dSLionel Sambuc
862*0a6a1f1dSLionel Sambuc if (*C2 != 0) { // avoid X udiv 0
863f4a2713aSLionel Sambuc if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
864f4a2713aSLionel Sambuc if (Instruction *R = FoldOpIntoSelect(I, SI))
865f4a2713aSLionel Sambuc return R;
866f4a2713aSLionel Sambuc if (isa<PHINode>(Op0))
867f4a2713aSLionel Sambuc if (Instruction *NV = FoldOpIntoPhi(I))
868f4a2713aSLionel Sambuc return NV;
869f4a2713aSLionel Sambuc }
870f4a2713aSLionel Sambuc }
871*0a6a1f1dSLionel Sambuc }
872*0a6a1f1dSLionel Sambuc
873*0a6a1f1dSLionel Sambuc if (ConstantInt *One = dyn_cast<ConstantInt>(Op0)) {
874*0a6a1f1dSLionel Sambuc if (One->isOne() && !I.getType()->isIntegerTy(1)) {
875*0a6a1f1dSLionel Sambuc bool isSigned = I.getOpcode() == Instruction::SDiv;
876*0a6a1f1dSLionel Sambuc if (isSigned) {
877*0a6a1f1dSLionel Sambuc // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the
878*0a6a1f1dSLionel Sambuc // result is one, if Op1 is -1 then the result is minus one, otherwise
879*0a6a1f1dSLionel Sambuc // it's zero.
880*0a6a1f1dSLionel Sambuc Value *Inc = Builder->CreateAdd(Op1, One);
881*0a6a1f1dSLionel Sambuc Value *Cmp = Builder->CreateICmpULT(
882*0a6a1f1dSLionel Sambuc Inc, ConstantInt::get(I.getType(), 3));
883*0a6a1f1dSLionel Sambuc return SelectInst::Create(Cmp, Op1, ConstantInt::get(I.getType(), 0));
884*0a6a1f1dSLionel Sambuc } else {
885*0a6a1f1dSLionel Sambuc // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
886*0a6a1f1dSLionel Sambuc // result is one, otherwise it's zero.
887*0a6a1f1dSLionel Sambuc return new ZExtInst(Builder->CreateICmpEQ(Op1, One), I.getType());
888*0a6a1f1dSLionel Sambuc }
889*0a6a1f1dSLionel Sambuc }
890*0a6a1f1dSLionel Sambuc }
891f4a2713aSLionel Sambuc
892f4a2713aSLionel Sambuc // See if we can fold away this div instruction.
893f4a2713aSLionel Sambuc if (SimplifyDemandedInstructionBits(I))
894f4a2713aSLionel Sambuc return &I;
895f4a2713aSLionel Sambuc
896f4a2713aSLionel Sambuc // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
897*0a6a1f1dSLionel Sambuc Value *X = nullptr, *Z = nullptr;
898f4a2713aSLionel Sambuc if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1
899f4a2713aSLionel Sambuc bool isSigned = I.getOpcode() == Instruction::SDiv;
900f4a2713aSLionel Sambuc if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
901f4a2713aSLionel Sambuc (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
902f4a2713aSLionel Sambuc return BinaryOperator::Create(I.getOpcode(), X, Op1);
903f4a2713aSLionel Sambuc }
904f4a2713aSLionel Sambuc
905*0a6a1f1dSLionel Sambuc return nullptr;
906f4a2713aSLionel Sambuc }
907f4a2713aSLionel Sambuc
908f4a2713aSLionel Sambuc /// dyn_castZExtVal - Checks if V is a zext or constant that can
909f4a2713aSLionel Sambuc /// be truncated to Ty without losing bits.
dyn_castZExtVal(Value * V,Type * Ty)910f4a2713aSLionel Sambuc static Value *dyn_castZExtVal(Value *V, Type *Ty) {
911f4a2713aSLionel Sambuc if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) {
912f4a2713aSLionel Sambuc if (Z->getSrcTy() == Ty)
913f4a2713aSLionel Sambuc return Z->getOperand(0);
914f4a2713aSLionel Sambuc } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) {
915f4a2713aSLionel Sambuc if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth())
916f4a2713aSLionel Sambuc return ConstantExpr::getTrunc(C, Ty);
917f4a2713aSLionel Sambuc }
918*0a6a1f1dSLionel Sambuc return nullptr;
919f4a2713aSLionel Sambuc }
920f4a2713aSLionel Sambuc
921f4a2713aSLionel Sambuc namespace {
922f4a2713aSLionel Sambuc const unsigned MaxDepth = 6;
923f4a2713aSLionel Sambuc typedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1,
924f4a2713aSLionel Sambuc const BinaryOperator &I,
925f4a2713aSLionel Sambuc InstCombiner &IC);
926f4a2713aSLionel Sambuc
927f4a2713aSLionel Sambuc /// \brief Used to maintain state for visitUDivOperand().
928f4a2713aSLionel Sambuc struct UDivFoldAction {
929f4a2713aSLionel Sambuc FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this
930f4a2713aSLionel Sambuc ///< operand. This can be zero if this action
931f4a2713aSLionel Sambuc ///< joins two actions together.
932f4a2713aSLionel Sambuc
933f4a2713aSLionel Sambuc Value *OperandToFold; ///< Which operand to fold.
934f4a2713aSLionel Sambuc union {
935f4a2713aSLionel Sambuc Instruction *FoldResult; ///< The instruction returned when FoldAction is
936f4a2713aSLionel Sambuc ///< invoked.
937f4a2713aSLionel Sambuc
938f4a2713aSLionel Sambuc size_t SelectLHSIdx; ///< Stores the LHS action index if this action
939f4a2713aSLionel Sambuc ///< joins two actions together.
940f4a2713aSLionel Sambuc };
941f4a2713aSLionel Sambuc
UDivFoldAction__anon63f292330111::UDivFoldAction942f4a2713aSLionel Sambuc UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
943*0a6a1f1dSLionel Sambuc : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
UDivFoldAction__anon63f292330111::UDivFoldAction944f4a2713aSLionel Sambuc UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
945f4a2713aSLionel Sambuc : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
946f4a2713aSLionel Sambuc };
947f4a2713aSLionel Sambuc }
948f4a2713aSLionel Sambuc
949f4a2713aSLionel Sambuc // X udiv 2^C -> X >> C
foldUDivPow2Cst(Value * Op0,Value * Op1,const BinaryOperator & I,InstCombiner & IC)950f4a2713aSLionel Sambuc static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1,
951f4a2713aSLionel Sambuc const BinaryOperator &I, InstCombiner &IC) {
952f4a2713aSLionel Sambuc const APInt &C = cast<Constant>(Op1)->getUniqueInteger();
953f4a2713aSLionel Sambuc BinaryOperator *LShr = BinaryOperator::CreateLShr(
954f4a2713aSLionel Sambuc Op0, ConstantInt::get(Op0->getType(), C.logBase2()));
955*0a6a1f1dSLionel Sambuc if (I.isExact())
956*0a6a1f1dSLionel Sambuc LShr->setIsExact();
957f4a2713aSLionel Sambuc return LShr;
958f4a2713aSLionel Sambuc }
959f4a2713aSLionel Sambuc
960f4a2713aSLionel Sambuc // X udiv C, where C >= signbit
foldUDivNegCst(Value * Op0,Value * Op1,const BinaryOperator & I,InstCombiner & IC)961f4a2713aSLionel Sambuc static Instruction *foldUDivNegCst(Value *Op0, Value *Op1,
962f4a2713aSLionel Sambuc const BinaryOperator &I, InstCombiner &IC) {
963f4a2713aSLionel Sambuc Value *ICI = IC.Builder->CreateICmpULT(Op0, cast<ConstantInt>(Op1));
964f4a2713aSLionel Sambuc
965f4a2713aSLionel Sambuc return SelectInst::Create(ICI, Constant::getNullValue(I.getType()),
966f4a2713aSLionel Sambuc ConstantInt::get(I.getType(), 1));
967f4a2713aSLionel Sambuc }
968f4a2713aSLionel Sambuc
969f4a2713aSLionel Sambuc // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
foldUDivShl(Value * Op0,Value * Op1,const BinaryOperator & I,InstCombiner & IC)970f4a2713aSLionel Sambuc static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
971f4a2713aSLionel Sambuc InstCombiner &IC) {
972f4a2713aSLionel Sambuc Instruction *ShiftLeft = cast<Instruction>(Op1);
973f4a2713aSLionel Sambuc if (isa<ZExtInst>(ShiftLeft))
974f4a2713aSLionel Sambuc ShiftLeft = cast<Instruction>(ShiftLeft->getOperand(0));
975f4a2713aSLionel Sambuc
976f4a2713aSLionel Sambuc const APInt &CI =
977f4a2713aSLionel Sambuc cast<Constant>(ShiftLeft->getOperand(0))->getUniqueInteger();
978f4a2713aSLionel Sambuc Value *N = ShiftLeft->getOperand(1);
979f4a2713aSLionel Sambuc if (CI != 1)
980f4a2713aSLionel Sambuc N = IC.Builder->CreateAdd(N, ConstantInt::get(N->getType(), CI.logBase2()));
981f4a2713aSLionel Sambuc if (ZExtInst *Z = dyn_cast<ZExtInst>(Op1))
982f4a2713aSLionel Sambuc N = IC.Builder->CreateZExt(N, Z->getDestTy());
983f4a2713aSLionel Sambuc BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
984*0a6a1f1dSLionel Sambuc if (I.isExact())
985*0a6a1f1dSLionel Sambuc LShr->setIsExact();
986f4a2713aSLionel Sambuc return LShr;
987f4a2713aSLionel Sambuc }
988f4a2713aSLionel Sambuc
989f4a2713aSLionel Sambuc // \brief Recursively visits the possible right hand operands of a udiv
990f4a2713aSLionel Sambuc // instruction, seeing through select instructions, to determine if we can
991f4a2713aSLionel Sambuc // replace the udiv with something simpler. If we find that an operand is not
992f4a2713aSLionel Sambuc // able to simplify the udiv, we abort the entire transformation.
visitUDivOperand(Value * Op0,Value * Op1,const BinaryOperator & I,SmallVectorImpl<UDivFoldAction> & Actions,unsigned Depth=0)993f4a2713aSLionel Sambuc static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
994f4a2713aSLionel Sambuc SmallVectorImpl<UDivFoldAction> &Actions,
995f4a2713aSLionel Sambuc unsigned Depth = 0) {
996f4a2713aSLionel Sambuc // Check to see if this is an unsigned division with an exact power of 2,
997f4a2713aSLionel Sambuc // if so, convert to a right shift.
998f4a2713aSLionel Sambuc if (match(Op1, m_Power2())) {
999f4a2713aSLionel Sambuc Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1));
1000f4a2713aSLionel Sambuc return Actions.size();
1001f4a2713aSLionel Sambuc }
1002f4a2713aSLionel Sambuc
1003f4a2713aSLionel Sambuc if (ConstantInt *C = dyn_cast<ConstantInt>(Op1))
1004f4a2713aSLionel Sambuc // X udiv C, where C >= signbit
1005f4a2713aSLionel Sambuc if (C->getValue().isNegative()) {
1006f4a2713aSLionel Sambuc Actions.push_back(UDivFoldAction(foldUDivNegCst, C));
1007f4a2713aSLionel Sambuc return Actions.size();
1008f4a2713aSLionel Sambuc }
1009f4a2713aSLionel Sambuc
1010f4a2713aSLionel Sambuc // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
1011f4a2713aSLionel Sambuc if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
1012f4a2713aSLionel Sambuc match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
1013f4a2713aSLionel Sambuc Actions.push_back(UDivFoldAction(foldUDivShl, Op1));
1014f4a2713aSLionel Sambuc return Actions.size();
1015f4a2713aSLionel Sambuc }
1016f4a2713aSLionel Sambuc
1017f4a2713aSLionel Sambuc // The remaining tests are all recursive, so bail out if we hit the limit.
1018f4a2713aSLionel Sambuc if (Depth++ == MaxDepth)
1019f4a2713aSLionel Sambuc return 0;
1020f4a2713aSLionel Sambuc
1021f4a2713aSLionel Sambuc if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1022*0a6a1f1dSLionel Sambuc if (size_t LHSIdx =
1023*0a6a1f1dSLionel Sambuc visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth))
1024*0a6a1f1dSLionel Sambuc if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) {
1025*0a6a1f1dSLionel Sambuc Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1));
1026f4a2713aSLionel Sambuc return Actions.size();
1027f4a2713aSLionel Sambuc }
1028f4a2713aSLionel Sambuc
1029f4a2713aSLionel Sambuc return 0;
1030f4a2713aSLionel Sambuc }
1031f4a2713aSLionel Sambuc
visitUDiv(BinaryOperator & I)1032f4a2713aSLionel Sambuc Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
1033f4a2713aSLionel Sambuc Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1034f4a2713aSLionel Sambuc
1035*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyVectorOp(I))
1036*0a6a1f1dSLionel Sambuc return ReplaceInstUsesWith(I, V);
1037*0a6a1f1dSLionel Sambuc
1038*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyUDivInst(Op0, Op1, DL, TLI, DT, AC))
1039f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, V);
1040f4a2713aSLionel Sambuc
1041f4a2713aSLionel Sambuc // Handle the integer div common cases
1042f4a2713aSLionel Sambuc if (Instruction *Common = commonIDivTransforms(I))
1043f4a2713aSLionel Sambuc return Common;
1044f4a2713aSLionel Sambuc
1045f4a2713aSLionel Sambuc // (x lshr C1) udiv C2 --> x udiv (C2 << C1)
1046*0a6a1f1dSLionel Sambuc {
1047f4a2713aSLionel Sambuc Value *X;
1048*0a6a1f1dSLionel Sambuc const APInt *C1, *C2;
1049*0a6a1f1dSLionel Sambuc if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) &&
1050*0a6a1f1dSLionel Sambuc match(Op1, m_APInt(C2))) {
1051*0a6a1f1dSLionel Sambuc bool Overflow;
1052*0a6a1f1dSLionel Sambuc APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
1053*0a6a1f1dSLionel Sambuc if (!Overflow) {
1054*0a6a1f1dSLionel Sambuc bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value()));
1055*0a6a1f1dSLionel Sambuc BinaryOperator *BO = BinaryOperator::CreateUDiv(
1056*0a6a1f1dSLionel Sambuc X, ConstantInt::get(X->getType(), C2ShlC1));
1057*0a6a1f1dSLionel Sambuc if (IsExact)
1058*0a6a1f1dSLionel Sambuc BO->setIsExact();
1059*0a6a1f1dSLionel Sambuc return BO;
1060*0a6a1f1dSLionel Sambuc }
1061f4a2713aSLionel Sambuc }
1062f4a2713aSLionel Sambuc }
1063f4a2713aSLionel Sambuc
1064f4a2713aSLionel Sambuc // (zext A) udiv (zext B) --> zext (A udiv B)
1065f4a2713aSLionel Sambuc if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0))
1066f4a2713aSLionel Sambuc if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy()))
1067*0a6a1f1dSLionel Sambuc return new ZExtInst(
1068*0a6a1f1dSLionel Sambuc Builder->CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", I.isExact()),
1069f4a2713aSLionel Sambuc I.getType());
1070f4a2713aSLionel Sambuc
1071f4a2713aSLionel Sambuc // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
1072f4a2713aSLionel Sambuc SmallVector<UDivFoldAction, 6> UDivActions;
1073f4a2713aSLionel Sambuc if (visitUDivOperand(Op0, Op1, I, UDivActions))
1074f4a2713aSLionel Sambuc for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) {
1075f4a2713aSLionel Sambuc FoldUDivOperandCb Action = UDivActions[i].FoldAction;
1076f4a2713aSLionel Sambuc Value *ActionOp1 = UDivActions[i].OperandToFold;
1077f4a2713aSLionel Sambuc Instruction *Inst;
1078f4a2713aSLionel Sambuc if (Action)
1079f4a2713aSLionel Sambuc Inst = Action(Op0, ActionOp1, I, *this);
1080f4a2713aSLionel Sambuc else {
1081f4a2713aSLionel Sambuc // This action joins two actions together. The RHS of this action is
1082f4a2713aSLionel Sambuc // simply the last action we processed, we saved the LHS action index in
1083f4a2713aSLionel Sambuc // the joining action.
1084f4a2713aSLionel Sambuc size_t SelectRHSIdx = i - 1;
1085f4a2713aSLionel Sambuc Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult;
1086f4a2713aSLionel Sambuc size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx;
1087f4a2713aSLionel Sambuc Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult;
1088f4a2713aSLionel Sambuc Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
1089f4a2713aSLionel Sambuc SelectLHS, SelectRHS);
1090f4a2713aSLionel Sambuc }
1091f4a2713aSLionel Sambuc
1092f4a2713aSLionel Sambuc // If this is the last action to process, return it to the InstCombiner.
1093f4a2713aSLionel Sambuc // Otherwise, we insert it before the UDiv and record it so that we may
1094f4a2713aSLionel Sambuc // use it as part of a joining action (i.e., a SelectInst).
1095f4a2713aSLionel Sambuc if (e - i != 1) {
1096f4a2713aSLionel Sambuc Inst->insertBefore(&I);
1097f4a2713aSLionel Sambuc UDivActions[i].FoldResult = Inst;
1098f4a2713aSLionel Sambuc } else
1099f4a2713aSLionel Sambuc return Inst;
1100f4a2713aSLionel Sambuc }
1101f4a2713aSLionel Sambuc
1102*0a6a1f1dSLionel Sambuc return nullptr;
1103f4a2713aSLionel Sambuc }
1104f4a2713aSLionel Sambuc
visitSDiv(BinaryOperator & I)1105f4a2713aSLionel Sambuc Instruction *InstCombiner::visitSDiv(BinaryOperator &I) {
1106f4a2713aSLionel Sambuc Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1107f4a2713aSLionel Sambuc
1108*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyVectorOp(I))
1109*0a6a1f1dSLionel Sambuc return ReplaceInstUsesWith(I, V);
1110*0a6a1f1dSLionel Sambuc
1111*0a6a1f1dSLionel Sambuc if (Value *V = SimplifySDivInst(Op0, Op1, DL, TLI, DT, AC))
1112f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, V);
1113f4a2713aSLionel Sambuc
1114f4a2713aSLionel Sambuc // Handle the integer div common cases
1115f4a2713aSLionel Sambuc if (Instruction *Common = commonIDivTransforms(I))
1116f4a2713aSLionel Sambuc return Common;
1117f4a2713aSLionel Sambuc
1118f4a2713aSLionel Sambuc // sdiv X, -1 == -X
1119*0a6a1f1dSLionel Sambuc if (match(Op1, m_AllOnes()))
1120f4a2713aSLionel Sambuc return BinaryOperator::CreateNeg(Op0);
1121f4a2713aSLionel Sambuc
1122*0a6a1f1dSLionel Sambuc if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
1123f4a2713aSLionel Sambuc // sdiv X, C --> ashr exact X, log2(C)
1124f4a2713aSLionel Sambuc if (I.isExact() && RHS->getValue().isNonNegative() &&
1125f4a2713aSLionel Sambuc RHS->getValue().isPowerOf2()) {
1126f4a2713aSLionel Sambuc Value *ShAmt = llvm::ConstantInt::get(RHS->getType(),
1127f4a2713aSLionel Sambuc RHS->getValue().exactLogBase2());
1128f4a2713aSLionel Sambuc return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName());
1129f4a2713aSLionel Sambuc }
1130*0a6a1f1dSLionel Sambuc }
1131*0a6a1f1dSLionel Sambuc
1132*0a6a1f1dSLionel Sambuc if (Constant *RHS = dyn_cast<Constant>(Op1)) {
1133*0a6a1f1dSLionel Sambuc // X/INT_MIN -> X == INT_MIN
1134*0a6a1f1dSLionel Sambuc if (RHS->isMinSignedValue())
1135*0a6a1f1dSLionel Sambuc return new ZExtInst(Builder->CreateICmpEQ(Op0, Op1), I.getType());
1136f4a2713aSLionel Sambuc
1137f4a2713aSLionel Sambuc // -X/C --> X/-C provided the negation doesn't overflow.
1138*0a6a1f1dSLionel Sambuc Value *X;
1139*0a6a1f1dSLionel Sambuc if (match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1140*0a6a1f1dSLionel Sambuc auto *BO = BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(RHS));
1141*0a6a1f1dSLionel Sambuc BO->setIsExact(I.isExact());
1142*0a6a1f1dSLionel Sambuc return BO;
1143*0a6a1f1dSLionel Sambuc }
1144f4a2713aSLionel Sambuc }
1145f4a2713aSLionel Sambuc
1146f4a2713aSLionel Sambuc // If the sign bits of both operands are zero (i.e. we can prove they are
1147f4a2713aSLionel Sambuc // unsigned inputs), turn this into a udiv.
1148f4a2713aSLionel Sambuc if (I.getType()->isIntegerTy()) {
1149f4a2713aSLionel Sambuc APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits()));
1150*0a6a1f1dSLionel Sambuc if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
1151*0a6a1f1dSLionel Sambuc if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
1152f4a2713aSLionel Sambuc // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
1153*0a6a1f1dSLionel Sambuc auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1154*0a6a1f1dSLionel Sambuc BO->setIsExact(I.isExact());
1155*0a6a1f1dSLionel Sambuc return BO;
1156f4a2713aSLionel Sambuc }
1157f4a2713aSLionel Sambuc
1158*0a6a1f1dSLionel Sambuc if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, AC, &I, DT)) {
1159f4a2713aSLionel Sambuc // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1160f4a2713aSLionel Sambuc // Safe because the only negative value (1 << Y) can take on is
1161f4a2713aSLionel Sambuc // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1162f4a2713aSLionel Sambuc // the sign bit set.
1163*0a6a1f1dSLionel Sambuc auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1164*0a6a1f1dSLionel Sambuc BO->setIsExact(I.isExact());
1165*0a6a1f1dSLionel Sambuc return BO;
1166f4a2713aSLionel Sambuc }
1167f4a2713aSLionel Sambuc }
1168f4a2713aSLionel Sambuc }
1169f4a2713aSLionel Sambuc
1170*0a6a1f1dSLionel Sambuc return nullptr;
1171f4a2713aSLionel Sambuc }
1172f4a2713aSLionel Sambuc
1173f4a2713aSLionel Sambuc /// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special
1174f4a2713aSLionel Sambuc /// FP value and:
1175f4a2713aSLionel Sambuc /// 1) 1/C is exact, or
1176f4a2713aSLionel Sambuc /// 2) reciprocal is allowed.
1177f4a2713aSLionel Sambuc /// If the conversion was successful, the simplified expression "X * 1/C" is
1178f4a2713aSLionel Sambuc /// returned; otherwise, NULL is returned.
1179f4a2713aSLionel Sambuc ///
CvtFDivConstToReciprocal(Value * Dividend,Constant * Divisor,bool AllowReciprocal)1180*0a6a1f1dSLionel Sambuc static Instruction *CvtFDivConstToReciprocal(Value *Dividend, Constant *Divisor,
1181f4a2713aSLionel Sambuc bool AllowReciprocal) {
1182*0a6a1f1dSLionel Sambuc if (!isa<ConstantFP>(Divisor)) // TODO: handle vectors.
1183*0a6a1f1dSLionel Sambuc return nullptr;
1184*0a6a1f1dSLionel Sambuc
1185*0a6a1f1dSLionel Sambuc const APFloat &FpVal = cast<ConstantFP>(Divisor)->getValueAPF();
1186f4a2713aSLionel Sambuc APFloat Reciprocal(FpVal.getSemantics());
1187f4a2713aSLionel Sambuc bool Cvt = FpVal.getExactInverse(&Reciprocal);
1188f4a2713aSLionel Sambuc
1189f4a2713aSLionel Sambuc if (!Cvt && AllowReciprocal && FpVal.isFiniteNonZero()) {
1190f4a2713aSLionel Sambuc Reciprocal = APFloat(FpVal.getSemantics(), 1.0f);
1191f4a2713aSLionel Sambuc (void)Reciprocal.divide(FpVal, APFloat::rmNearestTiesToEven);
1192f4a2713aSLionel Sambuc Cvt = !Reciprocal.isDenormal();
1193f4a2713aSLionel Sambuc }
1194f4a2713aSLionel Sambuc
1195f4a2713aSLionel Sambuc if (!Cvt)
1196*0a6a1f1dSLionel Sambuc return nullptr;
1197f4a2713aSLionel Sambuc
1198f4a2713aSLionel Sambuc ConstantFP *R;
1199f4a2713aSLionel Sambuc R = ConstantFP::get(Dividend->getType()->getContext(), Reciprocal);
1200f4a2713aSLionel Sambuc return BinaryOperator::CreateFMul(Dividend, R);
1201f4a2713aSLionel Sambuc }
1202f4a2713aSLionel Sambuc
visitFDiv(BinaryOperator & I)1203f4a2713aSLionel Sambuc Instruction *InstCombiner::visitFDiv(BinaryOperator &I) {
1204f4a2713aSLionel Sambuc Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1205f4a2713aSLionel Sambuc
1206*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyVectorOp(I))
1207*0a6a1f1dSLionel Sambuc return ReplaceInstUsesWith(I, V);
1208*0a6a1f1dSLionel Sambuc
1209*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyFDivInst(Op0, Op1, DL, TLI, DT, AC))
1210f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, V);
1211f4a2713aSLionel Sambuc
1212f4a2713aSLionel Sambuc if (isa<Constant>(Op0))
1213f4a2713aSLionel Sambuc if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1214f4a2713aSLionel Sambuc if (Instruction *R = FoldOpIntoSelect(I, SI))
1215f4a2713aSLionel Sambuc return R;
1216f4a2713aSLionel Sambuc
1217f4a2713aSLionel Sambuc bool AllowReassociate = I.hasUnsafeAlgebra();
1218f4a2713aSLionel Sambuc bool AllowReciprocal = I.hasAllowReciprocal();
1219f4a2713aSLionel Sambuc
1220*0a6a1f1dSLionel Sambuc if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
1221f4a2713aSLionel Sambuc if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1222f4a2713aSLionel Sambuc if (Instruction *R = FoldOpIntoSelect(I, SI))
1223f4a2713aSLionel Sambuc return R;
1224f4a2713aSLionel Sambuc
1225f4a2713aSLionel Sambuc if (AllowReassociate) {
1226*0a6a1f1dSLionel Sambuc Constant *C1 = nullptr;
1227*0a6a1f1dSLionel Sambuc Constant *C2 = Op1C;
1228f4a2713aSLionel Sambuc Value *X;
1229*0a6a1f1dSLionel Sambuc Instruction *Res = nullptr;
1230f4a2713aSLionel Sambuc
1231*0a6a1f1dSLionel Sambuc if (match(Op0, m_FMul(m_Value(X), m_Constant(C1)))) {
1232f4a2713aSLionel Sambuc // (X*C1)/C2 => X * (C1/C2)
1233f4a2713aSLionel Sambuc //
1234f4a2713aSLionel Sambuc Constant *C = ConstantExpr::getFDiv(C1, C2);
1235*0a6a1f1dSLionel Sambuc if (isNormalFp(C))
1236f4a2713aSLionel Sambuc Res = BinaryOperator::CreateFMul(X, C);
1237*0a6a1f1dSLionel Sambuc } else if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
1238f4a2713aSLionel Sambuc // (X/C1)/C2 => X /(C2*C1) [=> X * 1/(C2*C1) if reciprocal is allowed]
1239f4a2713aSLionel Sambuc //
1240f4a2713aSLionel Sambuc Constant *C = ConstantExpr::getFMul(C1, C2);
1241*0a6a1f1dSLionel Sambuc if (isNormalFp(C)) {
1242*0a6a1f1dSLionel Sambuc Res = CvtFDivConstToReciprocal(X, C, AllowReciprocal);
1243f4a2713aSLionel Sambuc if (!Res)
1244f4a2713aSLionel Sambuc Res = BinaryOperator::CreateFDiv(X, C);
1245f4a2713aSLionel Sambuc }
1246f4a2713aSLionel Sambuc }
1247f4a2713aSLionel Sambuc
1248f4a2713aSLionel Sambuc if (Res) {
1249f4a2713aSLionel Sambuc Res->setFastMathFlags(I.getFastMathFlags());
1250f4a2713aSLionel Sambuc return Res;
1251f4a2713aSLionel Sambuc }
1252f4a2713aSLionel Sambuc }
1253f4a2713aSLionel Sambuc
1254f4a2713aSLionel Sambuc // X / C => X * 1/C
1255*0a6a1f1dSLionel Sambuc if (Instruction *T = CvtFDivConstToReciprocal(Op0, Op1C, AllowReciprocal)) {
1256*0a6a1f1dSLionel Sambuc T->copyFastMathFlags(&I);
1257f4a2713aSLionel Sambuc return T;
1258f4a2713aSLionel Sambuc }
1259f4a2713aSLionel Sambuc
1260*0a6a1f1dSLionel Sambuc return nullptr;
1261*0a6a1f1dSLionel Sambuc }
1262*0a6a1f1dSLionel Sambuc
1263*0a6a1f1dSLionel Sambuc if (AllowReassociate && isa<Constant>(Op0)) {
1264*0a6a1f1dSLionel Sambuc Constant *C1 = cast<Constant>(Op0), *C2;
1265*0a6a1f1dSLionel Sambuc Constant *Fold = nullptr;
1266f4a2713aSLionel Sambuc Value *X;
1267f4a2713aSLionel Sambuc bool CreateDiv = true;
1268f4a2713aSLionel Sambuc
1269f4a2713aSLionel Sambuc // C1 / (X*C2) => (C1/C2) / X
1270*0a6a1f1dSLionel Sambuc if (match(Op1, m_FMul(m_Value(X), m_Constant(C2))))
1271f4a2713aSLionel Sambuc Fold = ConstantExpr::getFDiv(C1, C2);
1272*0a6a1f1dSLionel Sambuc else if (match(Op1, m_FDiv(m_Value(X), m_Constant(C2)))) {
1273f4a2713aSLionel Sambuc // C1 / (X/C2) => (C1*C2) / X
1274f4a2713aSLionel Sambuc Fold = ConstantExpr::getFMul(C1, C2);
1275*0a6a1f1dSLionel Sambuc } else if (match(Op1, m_FDiv(m_Constant(C2), m_Value(X)))) {
1276f4a2713aSLionel Sambuc // C1 / (C2/X) => (C1/C2) * X
1277f4a2713aSLionel Sambuc Fold = ConstantExpr::getFDiv(C1, C2);
1278f4a2713aSLionel Sambuc CreateDiv = false;
1279f4a2713aSLionel Sambuc }
1280f4a2713aSLionel Sambuc
1281*0a6a1f1dSLionel Sambuc if (Fold && isNormalFp(Fold)) {
1282*0a6a1f1dSLionel Sambuc Instruction *R = CreateDiv ? BinaryOperator::CreateFDiv(Fold, X)
1283*0a6a1f1dSLionel Sambuc : BinaryOperator::CreateFMul(X, Fold);
1284f4a2713aSLionel Sambuc R->setFastMathFlags(I.getFastMathFlags());
1285f4a2713aSLionel Sambuc return R;
1286f4a2713aSLionel Sambuc }
1287*0a6a1f1dSLionel Sambuc return nullptr;
1288f4a2713aSLionel Sambuc }
1289f4a2713aSLionel Sambuc
1290f4a2713aSLionel Sambuc if (AllowReassociate) {
1291f4a2713aSLionel Sambuc Value *X, *Y;
1292*0a6a1f1dSLionel Sambuc Value *NewInst = nullptr;
1293*0a6a1f1dSLionel Sambuc Instruction *SimpR = nullptr;
1294f4a2713aSLionel Sambuc
1295f4a2713aSLionel Sambuc if (Op0->hasOneUse() && match(Op0, m_FDiv(m_Value(X), m_Value(Y)))) {
1296f4a2713aSLionel Sambuc // (X/Y) / Z => X / (Y*Z)
1297f4a2713aSLionel Sambuc //
1298*0a6a1f1dSLionel Sambuc if (!isa<Constant>(Y) || !isa<Constant>(Op1)) {
1299f4a2713aSLionel Sambuc NewInst = Builder->CreateFMul(Y, Op1);
1300*0a6a1f1dSLionel Sambuc if (Instruction *RI = dyn_cast<Instruction>(NewInst)) {
1301*0a6a1f1dSLionel Sambuc FastMathFlags Flags = I.getFastMathFlags();
1302*0a6a1f1dSLionel Sambuc Flags &= cast<Instruction>(Op0)->getFastMathFlags();
1303*0a6a1f1dSLionel Sambuc RI->setFastMathFlags(Flags);
1304*0a6a1f1dSLionel Sambuc }
1305f4a2713aSLionel Sambuc SimpR = BinaryOperator::CreateFDiv(X, NewInst);
1306f4a2713aSLionel Sambuc }
1307f4a2713aSLionel Sambuc } else if (Op1->hasOneUse() && match(Op1, m_FDiv(m_Value(X), m_Value(Y)))) {
1308f4a2713aSLionel Sambuc // Z / (X/Y) => Z*Y / X
1309f4a2713aSLionel Sambuc //
1310*0a6a1f1dSLionel Sambuc if (!isa<Constant>(Y) || !isa<Constant>(Op0)) {
1311f4a2713aSLionel Sambuc NewInst = Builder->CreateFMul(Op0, Y);
1312*0a6a1f1dSLionel Sambuc if (Instruction *RI = dyn_cast<Instruction>(NewInst)) {
1313*0a6a1f1dSLionel Sambuc FastMathFlags Flags = I.getFastMathFlags();
1314*0a6a1f1dSLionel Sambuc Flags &= cast<Instruction>(Op1)->getFastMathFlags();
1315*0a6a1f1dSLionel Sambuc RI->setFastMathFlags(Flags);
1316*0a6a1f1dSLionel Sambuc }
1317f4a2713aSLionel Sambuc SimpR = BinaryOperator::CreateFDiv(NewInst, X);
1318f4a2713aSLionel Sambuc }
1319f4a2713aSLionel Sambuc }
1320f4a2713aSLionel Sambuc
1321f4a2713aSLionel Sambuc if (NewInst) {
1322f4a2713aSLionel Sambuc if (Instruction *T = dyn_cast<Instruction>(NewInst))
1323f4a2713aSLionel Sambuc T->setDebugLoc(I.getDebugLoc());
1324f4a2713aSLionel Sambuc SimpR->setFastMathFlags(I.getFastMathFlags());
1325f4a2713aSLionel Sambuc return SimpR;
1326f4a2713aSLionel Sambuc }
1327f4a2713aSLionel Sambuc }
1328f4a2713aSLionel Sambuc
1329*0a6a1f1dSLionel Sambuc return nullptr;
1330f4a2713aSLionel Sambuc }
1331f4a2713aSLionel Sambuc
1332f4a2713aSLionel Sambuc /// This function implements the transforms common to both integer remainder
1333f4a2713aSLionel Sambuc /// instructions (urem and srem). It is called by the visitors to those integer
1334f4a2713aSLionel Sambuc /// remainder instructions.
1335f4a2713aSLionel Sambuc /// @brief Common integer remainder transforms
commonIRemTransforms(BinaryOperator & I)1336f4a2713aSLionel Sambuc Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) {
1337f4a2713aSLionel Sambuc Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1338f4a2713aSLionel Sambuc
1339f4a2713aSLionel Sambuc // The RHS is known non-zero.
1340*0a6a1f1dSLionel Sambuc if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, &I)) {
1341f4a2713aSLionel Sambuc I.setOperand(1, V);
1342f4a2713aSLionel Sambuc return &I;
1343f4a2713aSLionel Sambuc }
1344f4a2713aSLionel Sambuc
1345f4a2713aSLionel Sambuc // Handle cases involving: rem X, (select Cond, Y, Z)
1346f4a2713aSLionel Sambuc if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
1347f4a2713aSLionel Sambuc return &I;
1348f4a2713aSLionel Sambuc
1349*0a6a1f1dSLionel Sambuc if (isa<Constant>(Op1)) {
1350f4a2713aSLionel Sambuc if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1351f4a2713aSLionel Sambuc if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1352f4a2713aSLionel Sambuc if (Instruction *R = FoldOpIntoSelect(I, SI))
1353f4a2713aSLionel Sambuc return R;
1354f4a2713aSLionel Sambuc } else if (isa<PHINode>(Op0I)) {
1355f4a2713aSLionel Sambuc if (Instruction *NV = FoldOpIntoPhi(I))
1356f4a2713aSLionel Sambuc return NV;
1357f4a2713aSLionel Sambuc }
1358f4a2713aSLionel Sambuc
1359f4a2713aSLionel Sambuc // See if we can fold away this rem instruction.
1360f4a2713aSLionel Sambuc if (SimplifyDemandedInstructionBits(I))
1361f4a2713aSLionel Sambuc return &I;
1362f4a2713aSLionel Sambuc }
1363f4a2713aSLionel Sambuc }
1364f4a2713aSLionel Sambuc
1365*0a6a1f1dSLionel Sambuc return nullptr;
1366f4a2713aSLionel Sambuc }
1367f4a2713aSLionel Sambuc
visitURem(BinaryOperator & I)1368f4a2713aSLionel Sambuc Instruction *InstCombiner::visitURem(BinaryOperator &I) {
1369f4a2713aSLionel Sambuc Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1370f4a2713aSLionel Sambuc
1371*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyVectorOp(I))
1372*0a6a1f1dSLionel Sambuc return ReplaceInstUsesWith(I, V);
1373*0a6a1f1dSLionel Sambuc
1374*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyURemInst(Op0, Op1, DL, TLI, DT, AC))
1375f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, V);
1376f4a2713aSLionel Sambuc
1377f4a2713aSLionel Sambuc if (Instruction *common = commonIRemTransforms(I))
1378f4a2713aSLionel Sambuc return common;
1379f4a2713aSLionel Sambuc
1380f4a2713aSLionel Sambuc // (zext A) urem (zext B) --> zext (A urem B)
1381f4a2713aSLionel Sambuc if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0))
1382f4a2713aSLionel Sambuc if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy()))
1383f4a2713aSLionel Sambuc return new ZExtInst(Builder->CreateURem(ZOp0->getOperand(0), ZOp1),
1384f4a2713aSLionel Sambuc I.getType());
1385f4a2713aSLionel Sambuc
1386f4a2713aSLionel Sambuc // X urem Y -> X and Y-1, where Y is a power of 2,
1387*0a6a1f1dSLionel Sambuc if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, AC, &I, DT)) {
1388f4a2713aSLionel Sambuc Constant *N1 = Constant::getAllOnesValue(I.getType());
1389f4a2713aSLionel Sambuc Value *Add = Builder->CreateAdd(Op1, N1);
1390f4a2713aSLionel Sambuc return BinaryOperator::CreateAnd(Op0, Add);
1391f4a2713aSLionel Sambuc }
1392f4a2713aSLionel Sambuc
1393f4a2713aSLionel Sambuc // 1 urem X -> zext(X != 1)
1394f4a2713aSLionel Sambuc if (match(Op0, m_One())) {
1395f4a2713aSLionel Sambuc Value *Cmp = Builder->CreateICmpNE(Op1, Op0);
1396f4a2713aSLionel Sambuc Value *Ext = Builder->CreateZExt(Cmp, I.getType());
1397f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, Ext);
1398f4a2713aSLionel Sambuc }
1399f4a2713aSLionel Sambuc
1400*0a6a1f1dSLionel Sambuc return nullptr;
1401f4a2713aSLionel Sambuc }
1402f4a2713aSLionel Sambuc
visitSRem(BinaryOperator & I)1403f4a2713aSLionel Sambuc Instruction *InstCombiner::visitSRem(BinaryOperator &I) {
1404f4a2713aSLionel Sambuc Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1405f4a2713aSLionel Sambuc
1406*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyVectorOp(I))
1407*0a6a1f1dSLionel Sambuc return ReplaceInstUsesWith(I, V);
1408*0a6a1f1dSLionel Sambuc
1409*0a6a1f1dSLionel Sambuc if (Value *V = SimplifySRemInst(Op0, Op1, DL, TLI, DT, AC))
1410f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, V);
1411f4a2713aSLionel Sambuc
1412f4a2713aSLionel Sambuc // Handle the integer rem common cases
1413f4a2713aSLionel Sambuc if (Instruction *Common = commonIRemTransforms(I))
1414f4a2713aSLionel Sambuc return Common;
1415f4a2713aSLionel Sambuc
1416*0a6a1f1dSLionel Sambuc {
1417*0a6a1f1dSLionel Sambuc const APInt *Y;
1418f4a2713aSLionel Sambuc // X % -Y -> X % Y
1419*0a6a1f1dSLionel Sambuc if (match(Op1, m_APInt(Y)) && Y->isNegative() && !Y->isMinSignedValue()) {
1420f4a2713aSLionel Sambuc Worklist.AddValue(I.getOperand(1));
1421*0a6a1f1dSLionel Sambuc I.setOperand(1, ConstantInt::get(I.getType(), -*Y));
1422f4a2713aSLionel Sambuc return &I;
1423f4a2713aSLionel Sambuc }
1424*0a6a1f1dSLionel Sambuc }
1425f4a2713aSLionel Sambuc
1426f4a2713aSLionel Sambuc // If the sign bits of both operands are zero (i.e. we can prove they are
1427f4a2713aSLionel Sambuc // unsigned inputs), turn this into a urem.
1428f4a2713aSLionel Sambuc if (I.getType()->isIntegerTy()) {
1429f4a2713aSLionel Sambuc APInt Mask(APInt::getSignBit(I.getType()->getPrimitiveSizeInBits()));
1430*0a6a1f1dSLionel Sambuc if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1431*0a6a1f1dSLionel Sambuc MaskedValueIsZero(Op0, Mask, 0, &I)) {
1432f4a2713aSLionel Sambuc // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1433f4a2713aSLionel Sambuc return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1434f4a2713aSLionel Sambuc }
1435f4a2713aSLionel Sambuc }
1436f4a2713aSLionel Sambuc
1437f4a2713aSLionel Sambuc // If it's a constant vector, flip any negative values positive.
1438f4a2713aSLionel Sambuc if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1439f4a2713aSLionel Sambuc Constant *C = cast<Constant>(Op1);
1440f4a2713aSLionel Sambuc unsigned VWidth = C->getType()->getVectorNumElements();
1441f4a2713aSLionel Sambuc
1442f4a2713aSLionel Sambuc bool hasNegative = false;
1443f4a2713aSLionel Sambuc bool hasMissing = false;
1444f4a2713aSLionel Sambuc for (unsigned i = 0; i != VWidth; ++i) {
1445f4a2713aSLionel Sambuc Constant *Elt = C->getAggregateElement(i);
1446*0a6a1f1dSLionel Sambuc if (!Elt) {
1447f4a2713aSLionel Sambuc hasMissing = true;
1448f4a2713aSLionel Sambuc break;
1449f4a2713aSLionel Sambuc }
1450f4a2713aSLionel Sambuc
1451f4a2713aSLionel Sambuc if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1452f4a2713aSLionel Sambuc if (RHS->isNegative())
1453f4a2713aSLionel Sambuc hasNegative = true;
1454f4a2713aSLionel Sambuc }
1455f4a2713aSLionel Sambuc
1456f4a2713aSLionel Sambuc if (hasNegative && !hasMissing) {
1457f4a2713aSLionel Sambuc SmallVector<Constant *, 16> Elts(VWidth);
1458f4a2713aSLionel Sambuc for (unsigned i = 0; i != VWidth; ++i) {
1459f4a2713aSLionel Sambuc Elts[i] = C->getAggregateElement(i); // Handle undef, etc.
1460f4a2713aSLionel Sambuc if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1461f4a2713aSLionel Sambuc if (RHS->isNegative())
1462f4a2713aSLionel Sambuc Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1463f4a2713aSLionel Sambuc }
1464f4a2713aSLionel Sambuc }
1465f4a2713aSLionel Sambuc
1466f4a2713aSLionel Sambuc Constant *NewRHSV = ConstantVector::get(Elts);
1467f4a2713aSLionel Sambuc if (NewRHSV != C) { // Don't loop on -MININT
1468f4a2713aSLionel Sambuc Worklist.AddValue(I.getOperand(1));
1469f4a2713aSLionel Sambuc I.setOperand(1, NewRHSV);
1470f4a2713aSLionel Sambuc return &I;
1471f4a2713aSLionel Sambuc }
1472f4a2713aSLionel Sambuc }
1473f4a2713aSLionel Sambuc }
1474f4a2713aSLionel Sambuc
1475*0a6a1f1dSLionel Sambuc return nullptr;
1476f4a2713aSLionel Sambuc }
1477f4a2713aSLionel Sambuc
visitFRem(BinaryOperator & I)1478f4a2713aSLionel Sambuc Instruction *InstCombiner::visitFRem(BinaryOperator &I) {
1479f4a2713aSLionel Sambuc Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1480f4a2713aSLionel Sambuc
1481*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyVectorOp(I))
1482*0a6a1f1dSLionel Sambuc return ReplaceInstUsesWith(I, V);
1483*0a6a1f1dSLionel Sambuc
1484*0a6a1f1dSLionel Sambuc if (Value *V = SimplifyFRemInst(Op0, Op1, DL, TLI, DT, AC))
1485f4a2713aSLionel Sambuc return ReplaceInstUsesWith(I, V);
1486f4a2713aSLionel Sambuc
1487f4a2713aSLionel Sambuc // Handle cases involving: rem X, (select Cond, Y, Z)
1488f4a2713aSLionel Sambuc if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
1489f4a2713aSLionel Sambuc return &I;
1490f4a2713aSLionel Sambuc
1491*0a6a1f1dSLionel Sambuc return nullptr;
1492f4a2713aSLionel Sambuc }
1493