1 //===- InstCombineMulDivRem.cpp -------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv,
13 //===----------------------------------------------------------------------===//
15 #include "InstCombine.h"
16 #include "llvm/Analysis/InstructionSimplify.h"
17 #include "llvm/IR/IntrinsicInst.h"
18 #include "llvm/IR/PatternMatch.h"
20 using namespace PatternMatch
;
22 #define DEBUG_TYPE "instcombine"
25 /// simplifyValueKnownNonZero - The specific integer value is used in a context
26 /// where it is known to be non-zero. If this allows us to simplify the
27 /// computation, do so and return the new operand, otherwise return null.
28 static Value
*simplifyValueKnownNonZero(Value
*V
, InstCombiner
&IC
,
30 // If V has multiple uses, then we would have to do more analysis to determine
31 // if this is safe. For example, the use could be in dynamically unreached
33 if (!V
->hasOneUse()) return nullptr;
35 bool MadeChange
= false;
37 // ((1 << A) >>u B) --> (1 << (A-B))
38 // Because V cannot be zero, we know that B is less than A.
39 Value
*A
= nullptr, *B
= nullptr, *One
= nullptr;
40 if (match(V
, m_LShr(m_OneUse(m_Shl(m_Value(One
), m_Value(A
))), m_Value(B
))) &&
41 match(One
, m_One())) {
42 A
= IC
.Builder
->CreateSub(A
, B
);
43 return IC
.Builder
->CreateShl(One
, A
);
46 // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
47 // inexact. Similarly for <<.
48 if (BinaryOperator
*I
= dyn_cast
<BinaryOperator
>(V
))
49 if (I
->isLogicalShift() &&
50 isKnownToBeAPowerOfTwo(I
->getOperand(0), false, 0,
51 IC
.getAssumptionCache(), CxtI
,
52 IC
.getDominatorTree())) {
53 // We know that this is an exact/nuw shift and that the input is a
54 // non-zero context as well.
55 if (Value
*V2
= simplifyValueKnownNonZero(I
->getOperand(0), IC
, CxtI
)) {
60 if (I
->getOpcode() == Instruction::LShr
&& !I
->isExact()) {
65 if (I
->getOpcode() == Instruction::Shl
&& !I
->hasNoUnsignedWrap()) {
66 I
->setHasNoUnsignedWrap();
71 // TODO: Lots more we could do here:
72 // If V is a phi node, we can call this on each of its operands.
73 // "select cond, X, 0" can simplify to "X".
75 return MadeChange
? V
: nullptr;
79 /// MultiplyOverflows - True if the multiply can not be expressed in an int
81 static bool MultiplyOverflows(const APInt
&C1
, const APInt
&C2
, APInt
&Product
,
85 Product
= C1
.smul_ov(C2
, Overflow
);
87 Product
= C1
.umul_ov(C2
, Overflow
);
92 /// \brief True if C2 is a multiple of C1. Quotient contains C2/C1.
93 static bool IsMultiple(const APInt
&C1
, const APInt
&C2
, APInt
&Quotient
,
95 assert(C1
.getBitWidth() == C2
.getBitWidth() &&
96 "Inconsistent width of constants!");
98 APInt
Remainder(C1
.getBitWidth(), /*Val=*/0ULL, IsSigned
);
100 APInt::sdivrem(C1
, C2
, Quotient
, Remainder
);
102 APInt::udivrem(C1
, C2
, Quotient
, Remainder
);
104 return Remainder
.isMinValue();
107 /// \brief A helper routine of InstCombiner::visitMul().
109 /// If C is a vector of known powers of 2, then this function returns
110 /// a new vector obtained from C replacing each element with its logBase2.
111 /// Return a null pointer otherwise.
112 static Constant
*getLogBase2Vector(ConstantDataVector
*CV
) {
114 SmallVector
<Constant
*, 4> Elts
;
116 for (unsigned I
= 0, E
= CV
->getNumElements(); I
!= E
; ++I
) {
117 Constant
*Elt
= CV
->getElementAsConstant(I
);
118 if (!match(Elt
, m_APInt(IVal
)) || !IVal
->isPowerOf2())
120 Elts
.push_back(ConstantInt::get(Elt
->getType(), IVal
->logBase2()));
123 return ConstantVector::get(Elts
);
126 /// \brief Return true if we can prove that:
127 /// (mul LHS, RHS) === (mul nsw LHS, RHS)
128 bool InstCombiner::WillNotOverflowSignedMul(Value
*LHS
, Value
*RHS
,
130 // Multiplying n * m significant bits yields a result of n + m significant
131 // bits. If the total number of significant bits does not exceed the
132 // result bit width (minus 1), there is no overflow.
133 // This means if we have enough leading sign bits in the operands
134 // we can guarantee that the result does not overflow.
135 // Ref: "Hacker's Delight" by Henry Warren
136 unsigned BitWidth
= LHS
->getType()->getScalarSizeInBits();
138 // Note that underestimating the number of sign bits gives a more
139 // conservative answer.
140 unsigned SignBits
= ComputeNumSignBits(LHS
, 0, CxtI
) +
141 ComputeNumSignBits(RHS
, 0, CxtI
);
143 // First handle the easy case: if we have enough sign bits there's
144 // definitely no overflow.
145 if (SignBits
> BitWidth
+ 1)
148 // There are two ambiguous cases where there can be no overflow:
149 // SignBits == BitWidth + 1 and
150 // SignBits == BitWidth
151 // The second case is difficult to check, therefore we only handle the
153 if (SignBits
== BitWidth
+ 1) {
154 // It overflows only when both arguments are negative and the true
155 // product is exactly the minimum negative number.
156 // E.g. mul i16 with 17 sign bits: 0xff00 * 0xff80 = 0x8000
157 // For simplicity we just check if at least one side is not negative.
158 bool LHSNonNegative
, LHSNegative
;
159 bool RHSNonNegative
, RHSNegative
;
160 ComputeSignBit(LHS
, LHSNonNegative
, LHSNegative
, /*Depth=*/0, CxtI
);
161 ComputeSignBit(RHS
, RHSNonNegative
, RHSNegative
, /*Depth=*/0, CxtI
);
162 if (LHSNonNegative
|| RHSNonNegative
)
168 Instruction
*InstCombiner::visitMul(BinaryOperator
&I
) {
169 bool Changed
= SimplifyAssociativeOrCommutative(I
);
170 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
172 if (Value
*V
= SimplifyVectorOp(I
))
173 return ReplaceInstUsesWith(I
, V
);
175 if (Value
*V
= SimplifyMulInst(Op0
, Op1
, DL
, TLI
, DT
, AC
))
176 return ReplaceInstUsesWith(I
, V
);
178 if (Value
*V
= SimplifyUsingDistributiveLaws(I
))
179 return ReplaceInstUsesWith(I
, V
);
182 if (match(Op1
, m_AllOnes())) {
183 BinaryOperator
*BO
= BinaryOperator::CreateNeg(Op0
, I
.getName());
184 if (I
.hasNoSignedWrap())
185 BO
->setHasNoSignedWrap();
189 // Also allow combining multiply instructions on vectors.
194 if (match(&I
, m_Mul(m_Shl(m_Value(NewOp
), m_Constant(C2
)),
196 match(C1
, m_APInt(IVal
))) {
197 // ((X << C2)*C1) == (X * (C1 << C2))
198 Constant
*Shl
= ConstantExpr::getShl(C1
, C2
);
199 BinaryOperator
*Mul
= cast
<BinaryOperator
>(I
.getOperand(0));
200 BinaryOperator
*BO
= BinaryOperator::CreateMul(NewOp
, Shl
);
201 if (I
.hasNoUnsignedWrap() && Mul
->hasNoUnsignedWrap())
202 BO
->setHasNoUnsignedWrap();
203 if (I
.hasNoSignedWrap() && Mul
->hasNoSignedWrap() &&
204 Shl
->isNotMinSignedValue())
205 BO
->setHasNoSignedWrap();
209 if (match(&I
, m_Mul(m_Value(NewOp
), m_Constant(C1
)))) {
210 Constant
*NewCst
= nullptr;
211 if (match(C1
, m_APInt(IVal
)) && IVal
->isPowerOf2())
212 // Replace X*(2^C) with X << C, where C is either a scalar or a splat.
213 NewCst
= ConstantInt::get(NewOp
->getType(), IVal
->logBase2());
214 else if (ConstantDataVector
*CV
= dyn_cast
<ConstantDataVector
>(C1
))
215 // Replace X*(2^C) with X << C, where C is a vector of known
216 // constant powers of 2.
217 NewCst
= getLogBase2Vector(CV
);
220 BinaryOperator
*Shl
= BinaryOperator::CreateShl(NewOp
, NewCst
);
222 if (I
.hasNoUnsignedWrap())
223 Shl
->setHasNoUnsignedWrap();
224 if (I
.hasNoSignedWrap() && NewCst
->isNotMinSignedValue())
225 Shl
->setHasNoSignedWrap();
232 if (ConstantInt
*CI
= dyn_cast
<ConstantInt
>(Op1
)) {
233 // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n
234 // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n
235 // The "* (2**n)" thus becomes a potential shifting opportunity.
237 const APInt
& Val
= CI
->getValue();
238 const APInt
&PosVal
= Val
.abs();
239 if (Val
.isNegative() && PosVal
.isPowerOf2()) {
240 Value
*X
= nullptr, *Y
= nullptr;
241 if (Op0
->hasOneUse()) {
243 Value
*Sub
= nullptr;
244 if (match(Op0
, m_Sub(m_Value(Y
), m_Value(X
))))
245 Sub
= Builder
->CreateSub(X
, Y
, "suba");
246 else if (match(Op0
, m_Add(m_Value(Y
), m_ConstantInt(C1
))))
247 Sub
= Builder
->CreateSub(Builder
->CreateNeg(C1
), Y
, "subc");
250 BinaryOperator::CreateMul(Sub
,
251 ConstantInt::get(Y
->getType(), PosVal
));
257 // Simplify mul instructions with a constant RHS.
258 if (isa
<Constant
>(Op1
)) {
259 // Try to fold constant mul into select arguments.
260 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(Op0
))
261 if (Instruction
*R
= FoldOpIntoSelect(I
, SI
))
264 if (isa
<PHINode
>(Op0
))
265 if (Instruction
*NV
= FoldOpIntoPhi(I
))
268 // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
272 if (match(Op0
, m_OneUse(m_Add(m_Value(X
), m_Constant(C1
))))) {
273 Value
*Mul
= Builder
->CreateMul(C1
, Op1
);
274 // Only go forward with the transform if C1*CI simplifies to a tidier
276 if (!match(Mul
, m_Mul(m_Value(), m_Value())))
277 return BinaryOperator::CreateAdd(Builder
->CreateMul(X
, Op1
), Mul
);
282 if (Value
*Op0v
= dyn_castNegVal(Op0
)) { // -X * -Y = X*Y
283 if (Value
*Op1v
= dyn_castNegVal(Op1
)) {
284 BinaryOperator
*BO
= BinaryOperator::CreateMul(Op0v
, Op1v
);
285 if (I
.hasNoSignedWrap() &&
286 match(Op0
, m_NSWSub(m_Value(), m_Value())) &&
287 match(Op1
, m_NSWSub(m_Value(), m_Value())))
288 BO
->setHasNoSignedWrap();
293 // (X / Y) * Y = X - (X % Y)
294 // (X / Y) * -Y = (X % Y) - X
297 BinaryOperator
*BO
= dyn_cast
<BinaryOperator
>(Op0
);
299 (BO
->getOpcode() != Instruction::UDiv
&&
300 BO
->getOpcode() != Instruction::SDiv
)) {
302 BO
= dyn_cast
<BinaryOperator
>(Op1
);
304 Value
*Neg
= dyn_castNegVal(Op1C
);
305 if (BO
&& BO
->hasOneUse() &&
306 (BO
->getOperand(1) == Op1C
|| BO
->getOperand(1) == Neg
) &&
307 (BO
->getOpcode() == Instruction::UDiv
||
308 BO
->getOpcode() == Instruction::SDiv
)) {
309 Value
*Op0BO
= BO
->getOperand(0), *Op1BO
= BO
->getOperand(1);
311 // If the division is exact, X % Y is zero, so we end up with X or -X.
312 if (PossiblyExactOperator
*SDiv
= dyn_cast
<PossiblyExactOperator
>(BO
))
313 if (SDiv
->isExact()) {
315 return ReplaceInstUsesWith(I
, Op0BO
);
316 return BinaryOperator::CreateNeg(Op0BO
);
320 if (BO
->getOpcode() == Instruction::UDiv
)
321 Rem
= Builder
->CreateURem(Op0BO
, Op1BO
);
323 Rem
= Builder
->CreateSRem(Op0BO
, Op1BO
);
327 return BinaryOperator::CreateSub(Op0BO
, Rem
);
328 return BinaryOperator::CreateSub(Rem
, Op0BO
);
332 /// i1 mul -> i1 and.
333 if (I
.getType()->getScalarType()->isIntegerTy(1))
334 return BinaryOperator::CreateAnd(Op0
, Op1
);
336 // X*(1 << Y) --> X << Y
337 // (1 << Y)*X --> X << Y
340 BinaryOperator
*BO
= nullptr;
342 if (match(Op0
, m_Shl(m_One(), m_Value(Y
)))) {
343 BO
= BinaryOperator::CreateShl(Op1
, Y
);
344 ShlNSW
= cast
<ShlOperator
>(Op0
)->hasNoSignedWrap();
345 } else if (match(Op1
, m_Shl(m_One(), m_Value(Y
)))) {
346 BO
= BinaryOperator::CreateShl(Op0
, Y
);
347 ShlNSW
= cast
<ShlOperator
>(Op1
)->hasNoSignedWrap();
350 if (I
.hasNoUnsignedWrap())
351 BO
->setHasNoUnsignedWrap();
352 if (I
.hasNoSignedWrap() && ShlNSW
)
353 BO
->setHasNoSignedWrap();
358 // If one of the operands of the multiply is a cast from a boolean value, then
359 // we know the bool is either zero or one, so this is a 'masking' multiply.
360 // X * Y (where Y is 0 or 1) -> X & (0-Y)
361 if (!I
.getType()->isVectorTy()) {
362 // -2 is "-1 << 1" so it is all bits set except the low one.
363 APInt
Negative2(I
.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true);
365 Value
*BoolCast
= nullptr, *OtherOp
= nullptr;
366 if (MaskedValueIsZero(Op0
, Negative2
, 0, &I
))
367 BoolCast
= Op0
, OtherOp
= Op1
;
368 else if (MaskedValueIsZero(Op1
, Negative2
, 0, &I
))
369 BoolCast
= Op1
, OtherOp
= Op0
;
372 Value
*V
= Builder
->CreateSub(Constant::getNullValue(I
.getType()),
374 return BinaryOperator::CreateAnd(V
, OtherOp
);
378 if (!I
.hasNoSignedWrap() && WillNotOverflowSignedMul(Op0
, Op1
, &I
)) {
380 I
.setHasNoSignedWrap(true);
383 if (!I
.hasNoUnsignedWrap() &&
384 computeOverflowForUnsignedMul(Op0
, Op1
, &I
) ==
385 OverflowResult::NeverOverflows
) {
387 I
.setHasNoUnsignedWrap(true);
390 return Changed
? &I
: nullptr;
393 /// Detect pattern log2(Y * 0.5) with corresponding fast math flags.
394 static void detectLog2OfHalf(Value
*&Op
, Value
*&Y
, IntrinsicInst
*&Log2
) {
395 if (!Op
->hasOneUse())
398 IntrinsicInst
*II
= dyn_cast
<IntrinsicInst
>(Op
);
401 if (II
->getIntrinsicID() != Intrinsic::log2
|| !II
->hasUnsafeAlgebra())
405 Value
*OpLog2Of
= II
->getArgOperand(0);
406 if (!OpLog2Of
->hasOneUse())
409 Instruction
*I
= dyn_cast
<Instruction
>(OpLog2Of
);
412 if (I
->getOpcode() != Instruction::FMul
|| !I
->hasUnsafeAlgebra())
415 if (match(I
->getOperand(0), m_SpecificFP(0.5)))
416 Y
= I
->getOperand(1);
417 else if (match(I
->getOperand(1), m_SpecificFP(0.5)))
418 Y
= I
->getOperand(0);
421 static bool isFiniteNonZeroFp(Constant
*C
) {
422 if (C
->getType()->isVectorTy()) {
423 for (unsigned I
= 0, E
= C
->getType()->getVectorNumElements(); I
!= E
;
425 ConstantFP
*CFP
= dyn_cast
<ConstantFP
>(C
->getAggregateElement(I
));
426 if (!CFP
|| !CFP
->getValueAPF().isFiniteNonZero())
432 return isa
<ConstantFP
>(C
) &&
433 cast
<ConstantFP
>(C
)->getValueAPF().isFiniteNonZero();
436 static bool isNormalFp(Constant
*C
) {
437 if (C
->getType()->isVectorTy()) {
438 for (unsigned I
= 0, E
= C
->getType()->getVectorNumElements(); I
!= E
;
440 ConstantFP
*CFP
= dyn_cast
<ConstantFP
>(C
->getAggregateElement(I
));
441 if (!CFP
|| !CFP
->getValueAPF().isNormal())
447 return isa
<ConstantFP
>(C
) && cast
<ConstantFP
>(C
)->getValueAPF().isNormal();
450 /// Helper function of InstCombiner::visitFMul(BinaryOperator(). It returns
451 /// true iff the given value is FMul or FDiv with one and only one operand
452 /// being a normal constant (i.e. not Zero/NaN/Infinity).
453 static bool isFMulOrFDivWithConstant(Value
*V
) {
454 Instruction
*I
= dyn_cast
<Instruction
>(V
);
455 if (!I
|| (I
->getOpcode() != Instruction::FMul
&&
456 I
->getOpcode() != Instruction::FDiv
))
459 Constant
*C0
= dyn_cast
<Constant
>(I
->getOperand(0));
460 Constant
*C1
= dyn_cast
<Constant
>(I
->getOperand(1));
465 return (C0
&& isFiniteNonZeroFp(C0
)) || (C1
&& isFiniteNonZeroFp(C1
));
468 /// foldFMulConst() is a helper routine of InstCombiner::visitFMul().
469 /// The input \p FMulOrDiv is a FMul/FDiv with one and only one operand
470 /// being a constant (i.e. isFMulOrFDivWithConstant(FMulOrDiv) == true).
471 /// This function is to simplify "FMulOrDiv * C" and returns the
472 /// resulting expression. Note that this function could return NULL in
473 /// case the constants cannot be folded into a normal floating-point.
475 Value
*InstCombiner::foldFMulConst(Instruction
*FMulOrDiv
, Constant
*C
,
476 Instruction
*InsertBefore
) {
477 assert(isFMulOrFDivWithConstant(FMulOrDiv
) && "V is invalid");
479 Value
*Opnd0
= FMulOrDiv
->getOperand(0);
480 Value
*Opnd1
= FMulOrDiv
->getOperand(1);
482 Constant
*C0
= dyn_cast
<Constant
>(Opnd0
);
483 Constant
*C1
= dyn_cast
<Constant
>(Opnd1
);
485 BinaryOperator
*R
= nullptr;
487 // (X * C0) * C => X * (C0*C)
488 if (FMulOrDiv
->getOpcode() == Instruction::FMul
) {
489 Constant
*F
= ConstantExpr::getFMul(C1
? C1
: C0
, C
);
491 R
= BinaryOperator::CreateFMul(C1
? Opnd0
: Opnd1
, F
);
494 // (C0 / X) * C => (C0 * C) / X
495 if (FMulOrDiv
->hasOneUse()) {
496 // It would otherwise introduce another div.
497 Constant
*F
= ConstantExpr::getFMul(C0
, C
);
499 R
= BinaryOperator::CreateFDiv(F
, Opnd1
);
502 // (X / C1) * C => X * (C/C1) if C/C1 is not a denormal
503 Constant
*F
= ConstantExpr::getFDiv(C
, C1
);
505 R
= BinaryOperator::CreateFMul(Opnd0
, F
);
507 // (X / C1) * C => X / (C1/C)
508 Constant
*F
= ConstantExpr::getFDiv(C1
, C
);
510 R
= BinaryOperator::CreateFDiv(Opnd0
, F
);
516 R
->setHasUnsafeAlgebra(true);
517 InsertNewInstWith(R
, *InsertBefore
);
523 Instruction
*InstCombiner::visitFMul(BinaryOperator
&I
) {
524 bool Changed
= SimplifyAssociativeOrCommutative(I
);
525 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
527 if (Value
*V
= SimplifyVectorOp(I
))
528 return ReplaceInstUsesWith(I
, V
);
530 if (isa
<Constant
>(Op0
))
534 SimplifyFMulInst(Op0
, Op1
, I
.getFastMathFlags(), DL
, TLI
, DT
, AC
))
535 return ReplaceInstUsesWith(I
, V
);
537 bool AllowReassociate
= I
.hasUnsafeAlgebra();
539 // Simplify mul instructions with a constant RHS.
540 if (isa
<Constant
>(Op1
)) {
541 // Try to fold constant mul into select arguments.
542 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(Op0
))
543 if (Instruction
*R
= FoldOpIntoSelect(I
, SI
))
546 if (isa
<PHINode
>(Op0
))
547 if (Instruction
*NV
= FoldOpIntoPhi(I
))
550 // (fmul X, -1.0) --> (fsub -0.0, X)
551 if (match(Op1
, m_SpecificFP(-1.0))) {
552 Constant
*NegZero
= ConstantFP::getNegativeZero(Op1
->getType());
553 Instruction
*RI
= BinaryOperator::CreateFSub(NegZero
, Op0
);
554 RI
->copyFastMathFlags(&I
);
558 Constant
*C
= cast
<Constant
>(Op1
);
559 if (AllowReassociate
&& isFiniteNonZeroFp(C
)) {
560 // Let MDC denote an expression in one of these forms:
561 // X * C, C/X, X/C, where C is a constant.
563 // Try to simplify "MDC * Constant"
564 if (isFMulOrFDivWithConstant(Op0
))
565 if (Value
*V
= foldFMulConst(cast
<Instruction
>(Op0
), C
, &I
))
566 return ReplaceInstUsesWith(I
, V
);
568 // (MDC +/- C1) * C => (MDC * C) +/- (C1 * C)
569 Instruction
*FAddSub
= dyn_cast
<Instruction
>(Op0
);
571 (FAddSub
->getOpcode() == Instruction::FAdd
||
572 FAddSub
->getOpcode() == Instruction::FSub
)) {
573 Value
*Opnd0
= FAddSub
->getOperand(0);
574 Value
*Opnd1
= FAddSub
->getOperand(1);
575 Constant
*C0
= dyn_cast
<Constant
>(Opnd0
);
576 Constant
*C1
= dyn_cast
<Constant
>(Opnd1
);
580 std::swap(Opnd0
, Opnd1
);
584 if (C1
&& isFiniteNonZeroFp(C1
) && isFMulOrFDivWithConstant(Opnd0
)) {
585 Value
*M1
= ConstantExpr::getFMul(C1
, C
);
586 Value
*M0
= isNormalFp(cast
<Constant
>(M1
)) ?
587 foldFMulConst(cast
<Instruction
>(Opnd0
), C
, &I
) :
590 if (Swap
&& FAddSub
->getOpcode() == Instruction::FSub
)
593 Instruction
*RI
= (FAddSub
->getOpcode() == Instruction::FAdd
)
594 ? BinaryOperator::CreateFAdd(M0
, M1
)
595 : BinaryOperator::CreateFSub(M0
, M1
);
596 RI
->copyFastMathFlags(&I
);
604 // sqrt(X) * sqrt(X) -> X
605 if (AllowReassociate
&& (Op0
== Op1
))
606 if (IntrinsicInst
*II
= dyn_cast
<IntrinsicInst
>(Op0
))
607 if (II
->getIntrinsicID() == Intrinsic::sqrt
)
608 return ReplaceInstUsesWith(I
, II
->getOperand(0));
610 // Under unsafe algebra do:
611 // X * log2(0.5*Y) = X*log2(Y) - X
612 if (AllowReassociate
) {
613 Value
*OpX
= nullptr;
614 Value
*OpY
= nullptr;
616 detectLog2OfHalf(Op0
, OpY
, Log2
);
620 detectLog2OfHalf(Op1
, OpY
, Log2
);
625 // if pattern detected emit alternate sequence
627 BuilderTy::FastMathFlagGuard
Guard(*Builder
);
628 Builder
->SetFastMathFlags(Log2
->getFastMathFlags());
629 Log2
->setArgOperand(0, OpY
);
630 Value
*FMulVal
= Builder
->CreateFMul(OpX
, Log2
);
631 Value
*FSub
= Builder
->CreateFSub(FMulVal
, OpX
);
633 return ReplaceInstUsesWith(I
, FSub
);
637 // Handle symmetric situation in a 2-iteration loop
640 for (int i
= 0; i
< 2; i
++) {
641 bool IgnoreZeroSign
= I
.hasNoSignedZeros();
642 if (BinaryOperator::isFNeg(Opnd0
, IgnoreZeroSign
)) {
643 BuilderTy::FastMathFlagGuard
Guard(*Builder
);
644 Builder
->SetFastMathFlags(I
.getFastMathFlags());
646 Value
*N0
= dyn_castFNegVal(Opnd0
, IgnoreZeroSign
);
647 Value
*N1
= dyn_castFNegVal(Opnd1
, IgnoreZeroSign
);
651 Value
*FMul
= Builder
->CreateFMul(N0
, N1
);
653 return ReplaceInstUsesWith(I
, FMul
);
656 if (Opnd0
->hasOneUse()) {
657 // -X * Y => -(X*Y) (Promote negation as high as possible)
658 Value
*T
= Builder
->CreateFMul(N0
, Opnd1
);
659 Value
*Neg
= Builder
->CreateFNeg(T
);
661 return ReplaceInstUsesWith(I
, Neg
);
665 // (X*Y) * X => (X*X) * Y where Y != X
666 // The purpose is two-fold:
667 // 1) to form a power expression (of X).
668 // 2) potentially shorten the critical path: After transformation, the
669 // latency of the instruction Y is amortized by the expression of X*X,
670 // and therefore Y is in a "less critical" position compared to what it
671 // was before the transformation.
673 if (AllowReassociate
) {
674 Value
*Opnd0_0
, *Opnd0_1
;
675 if (Opnd0
->hasOneUse() &&
676 match(Opnd0
, m_FMul(m_Value(Opnd0_0
), m_Value(Opnd0_1
)))) {
678 if (Opnd0_0
== Opnd1
&& Opnd0_1
!= Opnd1
)
680 else if (Opnd0_1
== Opnd1
&& Opnd0_0
!= Opnd1
)
684 BuilderTy::FastMathFlagGuard
Guard(*Builder
);
685 Builder
->SetFastMathFlags(I
.getFastMathFlags());
686 Value
*T
= Builder
->CreateFMul(Opnd1
, Opnd1
);
688 Value
*R
= Builder
->CreateFMul(T
, Y
);
690 return ReplaceInstUsesWith(I
, R
);
695 if (!isa
<Constant
>(Op1
))
696 std::swap(Opnd0
, Opnd1
);
701 return Changed
? &I
: nullptr;
704 /// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select
706 bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator
&I
) {
707 SelectInst
*SI
= cast
<SelectInst
>(I
.getOperand(1));
709 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
710 int NonNullOperand
= -1;
711 if (Constant
*ST
= dyn_cast
<Constant
>(SI
->getOperand(1)))
712 if (ST
->isNullValue())
714 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
715 if (Constant
*ST
= dyn_cast
<Constant
>(SI
->getOperand(2)))
716 if (ST
->isNullValue())
719 if (NonNullOperand
== -1)
722 Value
*SelectCond
= SI
->getOperand(0);
724 // Change the div/rem to use 'Y' instead of the select.
725 I
.setOperand(1, SI
->getOperand(NonNullOperand
));
727 // Okay, we know we replace the operand of the div/rem with 'Y' with no
728 // problem. However, the select, or the condition of the select may have
729 // multiple uses. Based on our knowledge that the operand must be non-zero,
730 // propagate the known value for the select into other uses of it, and
731 // propagate a known value of the condition into its other users.
733 // If the select and condition only have a single use, don't bother with this,
735 if (SI
->use_empty() && SelectCond
->hasOneUse())
738 // Scan the current block backward, looking for other uses of SI.
739 BasicBlock::iterator BBI
= &I
, BBFront
= I
.getParent()->begin();
741 while (BBI
!= BBFront
) {
743 // If we found a call to a function, we can't assume it will return, so
744 // information from below it cannot be propagated above it.
745 if (isa
<CallInst
>(BBI
) && !isa
<IntrinsicInst
>(BBI
))
748 // Replace uses of the select or its condition with the known values.
749 for (Instruction::op_iterator I
= BBI
->op_begin(), E
= BBI
->op_end();
752 *I
= SI
->getOperand(NonNullOperand
);
754 } else if (*I
== SelectCond
) {
755 *I
= Builder
->getInt1(NonNullOperand
== 1);
760 // If we past the instruction, quit looking for it.
763 if (&*BBI
== SelectCond
)
764 SelectCond
= nullptr;
766 // If we ran out of things to eliminate, break out of the loop.
767 if (!SelectCond
&& !SI
)
775 /// This function implements the transforms common to both integer division
776 /// instructions (udiv and sdiv). It is called by the visitors to those integer
777 /// division instructions.
778 /// @brief Common integer divide transforms
779 Instruction
*InstCombiner::commonIDivTransforms(BinaryOperator
&I
) {
780 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
782 // The RHS is known non-zero.
783 if (Value
*V
= simplifyValueKnownNonZero(I
.getOperand(1), *this, &I
)) {
788 // Handle cases involving: [su]div X, (select Cond, Y, Z)
789 // This does not apply for fdiv.
790 if (isa
<SelectInst
>(Op1
) && SimplifyDivRemOfSelect(I
))
793 if (Instruction
*LHS
= dyn_cast
<Instruction
>(Op0
)) {
795 if (match(Op1
, m_APInt(C2
))) {
798 bool IsSigned
= I
.getOpcode() == Instruction::SDiv
;
800 // (X / C1) / C2 -> X / (C1*C2)
801 if ((IsSigned
&& match(LHS
, m_SDiv(m_Value(X
), m_APInt(C1
)))) ||
802 (!IsSigned
&& match(LHS
, m_UDiv(m_Value(X
), m_APInt(C1
))))) {
803 APInt
Product(C1
->getBitWidth(), /*Val=*/0ULL, IsSigned
);
804 if (!MultiplyOverflows(*C1
, *C2
, Product
, IsSigned
))
805 return BinaryOperator::Create(I
.getOpcode(), X
,
806 ConstantInt::get(I
.getType(), Product
));
809 if ((IsSigned
&& match(LHS
, m_NSWMul(m_Value(X
), m_APInt(C1
)))) ||
810 (!IsSigned
&& match(LHS
, m_NUWMul(m_Value(X
), m_APInt(C1
))))) {
811 APInt
Quotient(C1
->getBitWidth(), /*Val=*/0ULL, IsSigned
);
813 // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
814 if (IsMultiple(*C2
, *C1
, Quotient
, IsSigned
)) {
815 BinaryOperator
*BO
= BinaryOperator::Create(
816 I
.getOpcode(), X
, ConstantInt::get(X
->getType(), Quotient
));
817 BO
->setIsExact(I
.isExact());
821 // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
822 if (IsMultiple(*C1
, *C2
, Quotient
, IsSigned
)) {
823 BinaryOperator
*BO
= BinaryOperator::Create(
824 Instruction::Mul
, X
, ConstantInt::get(X
->getType(), Quotient
));
825 BO
->setHasNoUnsignedWrap(
827 cast
<OverflowingBinaryOperator
>(LHS
)->hasNoUnsignedWrap());
828 BO
->setHasNoSignedWrap(
829 cast
<OverflowingBinaryOperator
>(LHS
)->hasNoSignedWrap());
834 if ((IsSigned
&& match(LHS
, m_NSWShl(m_Value(X
), m_APInt(C1
))) &&
835 *C1
!= C1
->getBitWidth() - 1) ||
836 (!IsSigned
&& match(LHS
, m_NUWShl(m_Value(X
), m_APInt(C1
))))) {
837 APInt
Quotient(C1
->getBitWidth(), /*Val=*/0ULL, IsSigned
);
838 APInt C1Shifted
= APInt::getOneBitSet(
839 C1
->getBitWidth(), static_cast<unsigned>(C1
->getLimitedValue()));
841 // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of C1.
842 if (IsMultiple(*C2
, C1Shifted
, Quotient
, IsSigned
)) {
843 BinaryOperator
*BO
= BinaryOperator::Create(
844 I
.getOpcode(), X
, ConstantInt::get(X
->getType(), Quotient
));
845 BO
->setIsExact(I
.isExact());
849 // (X << C1) / C2 -> X * (C2 >> C1) if C1 is a multiple of C2.
850 if (IsMultiple(C1Shifted
, *C2
, Quotient
, IsSigned
)) {
851 BinaryOperator
*BO
= BinaryOperator::Create(
852 Instruction::Mul
, X
, ConstantInt::get(X
->getType(), Quotient
));
853 BO
->setHasNoUnsignedWrap(
855 cast
<OverflowingBinaryOperator
>(LHS
)->hasNoUnsignedWrap());
856 BO
->setHasNoSignedWrap(
857 cast
<OverflowingBinaryOperator
>(LHS
)->hasNoSignedWrap());
862 if (*C2
!= 0) { // avoid X udiv 0
863 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(Op0
))
864 if (Instruction
*R
= FoldOpIntoSelect(I
, SI
))
866 if (isa
<PHINode
>(Op0
))
867 if (Instruction
*NV
= FoldOpIntoPhi(I
))
873 if (ConstantInt
*One
= dyn_cast
<ConstantInt
>(Op0
)) {
874 if (One
->isOne() && !I
.getType()->isIntegerTy(1)) {
875 bool isSigned
= I
.getOpcode() == Instruction::SDiv
;
877 // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the
878 // result is one, if Op1 is -1 then the result is minus one, otherwise
880 Value
*Inc
= Builder
->CreateAdd(Op1
, One
);
881 Value
*Cmp
= Builder
->CreateICmpULT(
882 Inc
, ConstantInt::get(I
.getType(), 3));
883 return SelectInst::Create(Cmp
, Op1
, ConstantInt::get(I
.getType(), 0));
885 // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
886 // result is one, otherwise it's zero.
887 return new ZExtInst(Builder
->CreateICmpEQ(Op1
, One
), I
.getType());
892 // See if we can fold away this div instruction.
893 if (SimplifyDemandedInstructionBits(I
))
896 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
897 Value
*X
= nullptr, *Z
= nullptr;
898 if (match(Op0
, m_Sub(m_Value(X
), m_Value(Z
)))) { // (X - Z) / Y; Y = Op1
899 bool isSigned
= I
.getOpcode() == Instruction::SDiv
;
900 if ((isSigned
&& match(Z
, m_SRem(m_Specific(X
), m_Specific(Op1
)))) ||
901 (!isSigned
&& match(Z
, m_URem(m_Specific(X
), m_Specific(Op1
)))))
902 return BinaryOperator::Create(I
.getOpcode(), X
, Op1
);
908 /// dyn_castZExtVal - Checks if V is a zext or constant that can
909 /// be truncated to Ty without losing bits.
910 static Value
*dyn_castZExtVal(Value
*V
, Type
*Ty
) {
911 if (ZExtInst
*Z
= dyn_cast
<ZExtInst
>(V
)) {
912 if (Z
->getSrcTy() == Ty
)
913 return Z
->getOperand(0);
914 } else if (ConstantInt
*C
= dyn_cast
<ConstantInt
>(V
)) {
915 if (C
->getValue().getActiveBits() <= cast
<IntegerType
>(Ty
)->getBitWidth())
916 return ConstantExpr::getTrunc(C
, Ty
);
922 const unsigned MaxDepth
= 6;
923 typedef Instruction
*(*FoldUDivOperandCb
)(Value
*Op0
, Value
*Op1
,
924 const BinaryOperator
&I
,
927 /// \brief Used to maintain state for visitUDivOperand().
928 struct UDivFoldAction
{
929 FoldUDivOperandCb FoldAction
; ///< Informs visitUDiv() how to fold this
930 ///< operand. This can be zero if this action
931 ///< joins two actions together.
933 Value
*OperandToFold
; ///< Which operand to fold.
935 Instruction
*FoldResult
; ///< The instruction returned when FoldAction is
938 size_t SelectLHSIdx
; ///< Stores the LHS action index if this action
939 ///< joins two actions together.
942 UDivFoldAction(FoldUDivOperandCb FA
, Value
*InputOperand
)
943 : FoldAction(FA
), OperandToFold(InputOperand
), FoldResult(nullptr) {}
944 UDivFoldAction(FoldUDivOperandCb FA
, Value
*InputOperand
, size_t SLHS
)
945 : FoldAction(FA
), OperandToFold(InputOperand
), SelectLHSIdx(SLHS
) {}
949 // X udiv 2^C -> X >> C
950 static Instruction
*foldUDivPow2Cst(Value
*Op0
, Value
*Op1
,
951 const BinaryOperator
&I
, InstCombiner
&IC
) {
952 const APInt
&C
= cast
<Constant
>(Op1
)->getUniqueInteger();
953 BinaryOperator
*LShr
= BinaryOperator::CreateLShr(
954 Op0
, ConstantInt::get(Op0
->getType(), C
.logBase2()));
960 // X udiv C, where C >= signbit
961 static Instruction
*foldUDivNegCst(Value
*Op0
, Value
*Op1
,
962 const BinaryOperator
&I
, InstCombiner
&IC
) {
963 Value
*ICI
= IC
.Builder
->CreateICmpULT(Op0
, cast
<ConstantInt
>(Op1
));
965 return SelectInst::Create(ICI
, Constant::getNullValue(I
.getType()),
966 ConstantInt::get(I
.getType(), 1));
969 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
970 static Instruction
*foldUDivShl(Value
*Op0
, Value
*Op1
, const BinaryOperator
&I
,
972 Instruction
*ShiftLeft
= cast
<Instruction
>(Op1
);
973 if (isa
<ZExtInst
>(ShiftLeft
))
974 ShiftLeft
= cast
<Instruction
>(ShiftLeft
->getOperand(0));
977 cast
<Constant
>(ShiftLeft
->getOperand(0))->getUniqueInteger();
978 Value
*N
= ShiftLeft
->getOperand(1);
980 N
= IC
.Builder
->CreateAdd(N
, ConstantInt::get(N
->getType(), CI
.logBase2()));
981 if (ZExtInst
*Z
= dyn_cast
<ZExtInst
>(Op1
))
982 N
= IC
.Builder
->CreateZExt(N
, Z
->getDestTy());
983 BinaryOperator
*LShr
= BinaryOperator::CreateLShr(Op0
, N
);
989 // \brief Recursively visits the possible right hand operands of a udiv
990 // instruction, seeing through select instructions, to determine if we can
991 // replace the udiv with something simpler. If we find that an operand is not
992 // able to simplify the udiv, we abort the entire transformation.
993 static size_t visitUDivOperand(Value
*Op0
, Value
*Op1
, const BinaryOperator
&I
,
994 SmallVectorImpl
<UDivFoldAction
> &Actions
,
995 unsigned Depth
= 0) {
996 // Check to see if this is an unsigned division with an exact power of 2,
997 // if so, convert to a right shift.
998 if (match(Op1
, m_Power2())) {
999 Actions
.push_back(UDivFoldAction(foldUDivPow2Cst
, Op1
));
1000 return Actions
.size();
1003 if (ConstantInt
*C
= dyn_cast
<ConstantInt
>(Op1
))
1004 // X udiv C, where C >= signbit
1005 if (C
->getValue().isNegative()) {
1006 Actions
.push_back(UDivFoldAction(foldUDivNegCst
, C
));
1007 return Actions
.size();
1010 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
1011 if (match(Op1
, m_Shl(m_Power2(), m_Value())) ||
1012 match(Op1
, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
1013 Actions
.push_back(UDivFoldAction(foldUDivShl
, Op1
));
1014 return Actions
.size();
1017 // The remaining tests are all recursive, so bail out if we hit the limit.
1018 if (Depth
++ == MaxDepth
)
1021 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(Op1
))
1023 visitUDivOperand(Op0
, SI
->getOperand(1), I
, Actions
, Depth
))
1024 if (visitUDivOperand(Op0
, SI
->getOperand(2), I
, Actions
, Depth
)) {
1025 Actions
.push_back(UDivFoldAction(nullptr, Op1
, LHSIdx
- 1));
1026 return Actions
.size();
1032 Instruction
*InstCombiner::visitUDiv(BinaryOperator
&I
) {
1033 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
1035 if (Value
*V
= SimplifyVectorOp(I
))
1036 return ReplaceInstUsesWith(I
, V
);
1038 if (Value
*V
= SimplifyUDivInst(Op0
, Op1
, DL
, TLI
, DT
, AC
))
1039 return ReplaceInstUsesWith(I
, V
);
1041 // Handle the integer div common cases
1042 if (Instruction
*Common
= commonIDivTransforms(I
))
1045 // (x lshr C1) udiv C2 --> x udiv (C2 << C1)
1048 const APInt
*C1
, *C2
;
1049 if (match(Op0
, m_LShr(m_Value(X
), m_APInt(C1
))) &&
1050 match(Op1
, m_APInt(C2
))) {
1052 APInt C2ShlC1
= C2
->ushl_ov(*C1
, Overflow
);
1054 bool IsExact
= I
.isExact() && match(Op0
, m_Exact(m_Value()));
1055 BinaryOperator
*BO
= BinaryOperator::CreateUDiv(
1056 X
, ConstantInt::get(X
->getType(), C2ShlC1
));
1064 // (zext A) udiv (zext B) --> zext (A udiv B)
1065 if (ZExtInst
*ZOp0
= dyn_cast
<ZExtInst
>(Op0
))
1066 if (Value
*ZOp1
= dyn_castZExtVal(Op1
, ZOp0
->getSrcTy()))
1067 return new ZExtInst(
1068 Builder
->CreateUDiv(ZOp0
->getOperand(0), ZOp1
, "div", I
.isExact()),
1071 // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
1072 SmallVector
<UDivFoldAction
, 6> UDivActions
;
1073 if (visitUDivOperand(Op0
, Op1
, I
, UDivActions
))
1074 for (unsigned i
= 0, e
= UDivActions
.size(); i
!= e
; ++i
) {
1075 FoldUDivOperandCb Action
= UDivActions
[i
].FoldAction
;
1076 Value
*ActionOp1
= UDivActions
[i
].OperandToFold
;
1079 Inst
= Action(Op0
, ActionOp1
, I
, *this);
1081 // This action joins two actions together. The RHS of this action is
1082 // simply the last action we processed, we saved the LHS action index in
1083 // the joining action.
1084 size_t SelectRHSIdx
= i
- 1;
1085 Value
*SelectRHS
= UDivActions
[SelectRHSIdx
].FoldResult
;
1086 size_t SelectLHSIdx
= UDivActions
[i
].SelectLHSIdx
;
1087 Value
*SelectLHS
= UDivActions
[SelectLHSIdx
].FoldResult
;
1088 Inst
= SelectInst::Create(cast
<SelectInst
>(ActionOp1
)->getCondition(),
1089 SelectLHS
, SelectRHS
);
1092 // If this is the last action to process, return it to the InstCombiner.
1093 // Otherwise, we insert it before the UDiv and record it so that we may
1094 // use it as part of a joining action (i.e., a SelectInst).
1096 Inst
->insertBefore(&I
);
1097 UDivActions
[i
].FoldResult
= Inst
;
1105 Instruction
*InstCombiner::visitSDiv(BinaryOperator
&I
) {
1106 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
1108 if (Value
*V
= SimplifyVectorOp(I
))
1109 return ReplaceInstUsesWith(I
, V
);
1111 if (Value
*V
= SimplifySDivInst(Op0
, Op1
, DL
, TLI
, DT
, AC
))
1112 return ReplaceInstUsesWith(I
, V
);
1114 // Handle the integer div common cases
1115 if (Instruction
*Common
= commonIDivTransforms(I
))
1119 if (match(Op1
, m_AllOnes()))
1120 return BinaryOperator::CreateNeg(Op0
);
1122 if (ConstantInt
*RHS
= dyn_cast
<ConstantInt
>(Op1
)) {
1123 // sdiv X, C --> ashr exact X, log2(C)
1124 if (I
.isExact() && RHS
->getValue().isNonNegative() &&
1125 RHS
->getValue().isPowerOf2()) {
1126 Value
*ShAmt
= llvm::ConstantInt::get(RHS
->getType(),
1127 RHS
->getValue().exactLogBase2());
1128 return BinaryOperator::CreateExactAShr(Op0
, ShAmt
, I
.getName());
1132 if (Constant
*RHS
= dyn_cast
<Constant
>(Op1
)) {
1133 // X/INT_MIN -> X == INT_MIN
1134 if (RHS
->isMinSignedValue())
1135 return new ZExtInst(Builder
->CreateICmpEQ(Op0
, Op1
), I
.getType());
1137 // -X/C --> X/-C provided the negation doesn't overflow.
1139 if (match(Op0
, m_NSWSub(m_Zero(), m_Value(X
)))) {
1140 auto *BO
= BinaryOperator::CreateSDiv(X
, ConstantExpr::getNeg(RHS
));
1141 BO
->setIsExact(I
.isExact());
1146 // If the sign bits of both operands are zero (i.e. we can prove they are
1147 // unsigned inputs), turn this into a udiv.
1148 if (I
.getType()->isIntegerTy()) {
1149 APInt
Mask(APInt::getSignBit(I
.getType()->getPrimitiveSizeInBits()));
1150 if (MaskedValueIsZero(Op0
, Mask
, 0, &I
)) {
1151 if (MaskedValueIsZero(Op1
, Mask
, 0, &I
)) {
1152 // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
1153 auto *BO
= BinaryOperator::CreateUDiv(Op0
, Op1
, I
.getName());
1154 BO
->setIsExact(I
.isExact());
1158 if (isKnownToBeAPowerOfTwo(Op1
, /*OrZero*/ true, 0, AC
, &I
, DT
)) {
1159 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1160 // Safe because the only negative value (1 << Y) can take on is
1161 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1162 // the sign bit set.
1163 auto *BO
= BinaryOperator::CreateUDiv(Op0
, Op1
, I
.getName());
1164 BO
->setIsExact(I
.isExact());
1173 /// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special
1175 /// 1) 1/C is exact, or
1176 /// 2) reciprocal is allowed.
1177 /// If the conversion was successful, the simplified expression "X * 1/C" is
1178 /// returned; otherwise, NULL is returned.
1180 static Instruction
*CvtFDivConstToReciprocal(Value
*Dividend
, Constant
*Divisor
,
1181 bool AllowReciprocal
) {
1182 if (!isa
<ConstantFP
>(Divisor
)) // TODO: handle vectors.
1185 const APFloat
&FpVal
= cast
<ConstantFP
>(Divisor
)->getValueAPF();
1186 APFloat
Reciprocal(FpVal
.getSemantics());
1187 bool Cvt
= FpVal
.getExactInverse(&Reciprocal
);
1189 if (!Cvt
&& AllowReciprocal
&& FpVal
.isFiniteNonZero()) {
1190 Reciprocal
= APFloat(FpVal
.getSemantics(), 1.0f
);
1191 (void)Reciprocal
.divide(FpVal
, APFloat::rmNearestTiesToEven
);
1192 Cvt
= !Reciprocal
.isDenormal();
1199 R
= ConstantFP::get(Dividend
->getType()->getContext(), Reciprocal
);
1200 return BinaryOperator::CreateFMul(Dividend
, R
);
1203 Instruction
*InstCombiner::visitFDiv(BinaryOperator
&I
) {
1204 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
1206 if (Value
*V
= SimplifyVectorOp(I
))
1207 return ReplaceInstUsesWith(I
, V
);
1209 if (Value
*V
= SimplifyFDivInst(Op0
, Op1
, DL
, TLI
, DT
, AC
))
1210 return ReplaceInstUsesWith(I
, V
);
1212 if (isa
<Constant
>(Op0
))
1213 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(Op1
))
1214 if (Instruction
*R
= FoldOpIntoSelect(I
, SI
))
1217 bool AllowReassociate
= I
.hasUnsafeAlgebra();
1218 bool AllowReciprocal
= I
.hasAllowReciprocal();
1220 if (Constant
*Op1C
= dyn_cast
<Constant
>(Op1
)) {
1221 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(Op0
))
1222 if (Instruction
*R
= FoldOpIntoSelect(I
, SI
))
1225 if (AllowReassociate
) {
1226 Constant
*C1
= nullptr;
1227 Constant
*C2
= Op1C
;
1229 Instruction
*Res
= nullptr;
1231 if (match(Op0
, m_FMul(m_Value(X
), m_Constant(C1
)))) {
1232 // (X*C1)/C2 => X * (C1/C2)
1234 Constant
*C
= ConstantExpr::getFDiv(C1
, C2
);
1236 Res
= BinaryOperator::CreateFMul(X
, C
);
1237 } else if (match(Op0
, m_FDiv(m_Value(X
), m_Constant(C1
)))) {
1238 // (X/C1)/C2 => X /(C2*C1) [=> X * 1/(C2*C1) if reciprocal is allowed]
1240 Constant
*C
= ConstantExpr::getFMul(C1
, C2
);
1241 if (isNormalFp(C
)) {
1242 Res
= CvtFDivConstToReciprocal(X
, C
, AllowReciprocal
);
1244 Res
= BinaryOperator::CreateFDiv(X
, C
);
1249 Res
->setFastMathFlags(I
.getFastMathFlags());
1255 if (Instruction
*T
= CvtFDivConstToReciprocal(Op0
, Op1C
, AllowReciprocal
)) {
1256 T
->copyFastMathFlags(&I
);
1263 if (AllowReassociate
&& isa
<Constant
>(Op0
)) {
1264 Constant
*C1
= cast
<Constant
>(Op0
), *C2
;
1265 Constant
*Fold
= nullptr;
1267 bool CreateDiv
= true;
1269 // C1 / (X*C2) => (C1/C2) / X
1270 if (match(Op1
, m_FMul(m_Value(X
), m_Constant(C2
))))
1271 Fold
= ConstantExpr::getFDiv(C1
, C2
);
1272 else if (match(Op1
, m_FDiv(m_Value(X
), m_Constant(C2
)))) {
1273 // C1 / (X/C2) => (C1*C2) / X
1274 Fold
= ConstantExpr::getFMul(C1
, C2
);
1275 } else if (match(Op1
, m_FDiv(m_Constant(C2
), m_Value(X
)))) {
1276 // C1 / (C2/X) => (C1/C2) * X
1277 Fold
= ConstantExpr::getFDiv(C1
, C2
);
1281 if (Fold
&& isNormalFp(Fold
)) {
1282 Instruction
*R
= CreateDiv
? BinaryOperator::CreateFDiv(Fold
, X
)
1283 : BinaryOperator::CreateFMul(X
, Fold
);
1284 R
->setFastMathFlags(I
.getFastMathFlags());
1290 if (AllowReassociate
) {
1292 Value
*NewInst
= nullptr;
1293 Instruction
*SimpR
= nullptr;
1295 if (Op0
->hasOneUse() && match(Op0
, m_FDiv(m_Value(X
), m_Value(Y
)))) {
1296 // (X/Y) / Z => X / (Y*Z)
1298 if (!isa
<Constant
>(Y
) || !isa
<Constant
>(Op1
)) {
1299 NewInst
= Builder
->CreateFMul(Y
, Op1
);
1300 if (Instruction
*RI
= dyn_cast
<Instruction
>(NewInst
)) {
1301 FastMathFlags Flags
= I
.getFastMathFlags();
1302 Flags
&= cast
<Instruction
>(Op0
)->getFastMathFlags();
1303 RI
->setFastMathFlags(Flags
);
1305 SimpR
= BinaryOperator::CreateFDiv(X
, NewInst
);
1307 } else if (Op1
->hasOneUse() && match(Op1
, m_FDiv(m_Value(X
), m_Value(Y
)))) {
1308 // Z / (X/Y) => Z*Y / X
1310 if (!isa
<Constant
>(Y
) || !isa
<Constant
>(Op0
)) {
1311 NewInst
= Builder
->CreateFMul(Op0
, Y
);
1312 if (Instruction
*RI
= dyn_cast
<Instruction
>(NewInst
)) {
1313 FastMathFlags Flags
= I
.getFastMathFlags();
1314 Flags
&= cast
<Instruction
>(Op1
)->getFastMathFlags();
1315 RI
->setFastMathFlags(Flags
);
1317 SimpR
= BinaryOperator::CreateFDiv(NewInst
, X
);
1322 if (Instruction
*T
= dyn_cast
<Instruction
>(NewInst
))
1323 T
->setDebugLoc(I
.getDebugLoc());
1324 SimpR
->setFastMathFlags(I
.getFastMathFlags());
1332 /// This function implements the transforms common to both integer remainder
1333 /// instructions (urem and srem). It is called by the visitors to those integer
1334 /// remainder instructions.
1335 /// @brief Common integer remainder transforms
1336 Instruction
*InstCombiner::commonIRemTransforms(BinaryOperator
&I
) {
1337 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
1339 // The RHS is known non-zero.
1340 if (Value
*V
= simplifyValueKnownNonZero(I
.getOperand(1), *this, &I
)) {
1345 // Handle cases involving: rem X, (select Cond, Y, Z)
1346 if (isa
<SelectInst
>(Op1
) && SimplifyDivRemOfSelect(I
))
1349 if (isa
<Constant
>(Op1
)) {
1350 if (Instruction
*Op0I
= dyn_cast
<Instruction
>(Op0
)) {
1351 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(Op0I
)) {
1352 if (Instruction
*R
= FoldOpIntoSelect(I
, SI
))
1354 } else if (isa
<PHINode
>(Op0I
)) {
1355 if (Instruction
*NV
= FoldOpIntoPhi(I
))
1359 // See if we can fold away this rem instruction.
1360 if (SimplifyDemandedInstructionBits(I
))
1368 Instruction
*InstCombiner::visitURem(BinaryOperator
&I
) {
1369 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
1371 if (Value
*V
= SimplifyVectorOp(I
))
1372 return ReplaceInstUsesWith(I
, V
);
1374 if (Value
*V
= SimplifyURemInst(Op0
, Op1
, DL
, TLI
, DT
, AC
))
1375 return ReplaceInstUsesWith(I
, V
);
1377 if (Instruction
*common
= commonIRemTransforms(I
))
1380 // (zext A) urem (zext B) --> zext (A urem B)
1381 if (ZExtInst
*ZOp0
= dyn_cast
<ZExtInst
>(Op0
))
1382 if (Value
*ZOp1
= dyn_castZExtVal(Op1
, ZOp0
->getSrcTy()))
1383 return new ZExtInst(Builder
->CreateURem(ZOp0
->getOperand(0), ZOp1
),
1386 // X urem Y -> X and Y-1, where Y is a power of 2,
1387 if (isKnownToBeAPowerOfTwo(Op1
, /*OrZero*/ true, 0, AC
, &I
, DT
)) {
1388 Constant
*N1
= Constant::getAllOnesValue(I
.getType());
1389 Value
*Add
= Builder
->CreateAdd(Op1
, N1
);
1390 return BinaryOperator::CreateAnd(Op0
, Add
);
1393 // 1 urem X -> zext(X != 1)
1394 if (match(Op0
, m_One())) {
1395 Value
*Cmp
= Builder
->CreateICmpNE(Op1
, Op0
);
1396 Value
*Ext
= Builder
->CreateZExt(Cmp
, I
.getType());
1397 return ReplaceInstUsesWith(I
, Ext
);
1403 Instruction
*InstCombiner::visitSRem(BinaryOperator
&I
) {
1404 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
1406 if (Value
*V
= SimplifyVectorOp(I
))
1407 return ReplaceInstUsesWith(I
, V
);
1409 if (Value
*V
= SimplifySRemInst(Op0
, Op1
, DL
, TLI
, DT
, AC
))
1410 return ReplaceInstUsesWith(I
, V
);
1412 // Handle the integer rem common cases
1413 if (Instruction
*Common
= commonIRemTransforms(I
))
1419 if (match(Op1
, m_APInt(Y
)) && Y
->isNegative() && !Y
->isMinSignedValue()) {
1420 Worklist
.AddValue(I
.getOperand(1));
1421 I
.setOperand(1, ConstantInt::get(I
.getType(), -*Y
));
1426 // If the sign bits of both operands are zero (i.e. we can prove they are
1427 // unsigned inputs), turn this into a urem.
1428 if (I
.getType()->isIntegerTy()) {
1429 APInt
Mask(APInt::getSignBit(I
.getType()->getPrimitiveSizeInBits()));
1430 if (MaskedValueIsZero(Op1
, Mask
, 0, &I
) &&
1431 MaskedValueIsZero(Op0
, Mask
, 0, &I
)) {
1432 // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1433 return BinaryOperator::CreateURem(Op0
, Op1
, I
.getName());
1437 // If it's a constant vector, flip any negative values positive.
1438 if (isa
<ConstantVector
>(Op1
) || isa
<ConstantDataVector
>(Op1
)) {
1439 Constant
*C
= cast
<Constant
>(Op1
);
1440 unsigned VWidth
= C
->getType()->getVectorNumElements();
1442 bool hasNegative
= false;
1443 bool hasMissing
= false;
1444 for (unsigned i
= 0; i
!= VWidth
; ++i
) {
1445 Constant
*Elt
= C
->getAggregateElement(i
);
1451 if (ConstantInt
*RHS
= dyn_cast
<ConstantInt
>(Elt
))
1452 if (RHS
->isNegative())
1456 if (hasNegative
&& !hasMissing
) {
1457 SmallVector
<Constant
*, 16> Elts(VWidth
);
1458 for (unsigned i
= 0; i
!= VWidth
; ++i
) {
1459 Elts
[i
] = C
->getAggregateElement(i
); // Handle undef, etc.
1460 if (ConstantInt
*RHS
= dyn_cast
<ConstantInt
>(Elts
[i
])) {
1461 if (RHS
->isNegative())
1462 Elts
[i
] = cast
<ConstantInt
>(ConstantExpr::getNeg(RHS
));
1466 Constant
*NewRHSV
= ConstantVector::get(Elts
);
1467 if (NewRHSV
!= C
) { // Don't loop on -MININT
1468 Worklist
.AddValue(I
.getOperand(1));
1469 I
.setOperand(1, NewRHSV
);
1478 Instruction
*InstCombiner::visitFRem(BinaryOperator
&I
) {
1479 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
1481 if (Value
*V
= SimplifyVectorOp(I
))
1482 return ReplaceInstUsesWith(I
, V
);
1484 if (Value
*V
= SimplifyFRemInst(Op0
, Op1
, DL
, TLI
, DT
, AC
))
1485 return ReplaceInstUsesWith(I
, V
);
1487 // Handle cases involving: rem X, (select Cond, Y, Z)
1488 if (isa
<SelectInst
>(Op1
) && SimplifyDivRemOfSelect(I
))