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/IntrinsicInst.h"
17 #include "llvm/Analysis/InstructionSimplify.h"
18 #include "llvm/Support/PatternMatch.h"
20 using namespace PatternMatch
;
23 /// simplifyValueKnownNonZero - The specific integer value is used in a context
24 /// where it is known to be non-zero. If this allows us to simplify the
25 /// computation, do so and return the new operand, otherwise return null.
26 static Value
*simplifyValueKnownNonZero(Value
*V
, InstCombiner
&IC
) {
27 // If V has multiple uses, then we would have to do more analysis to determine
28 // if this is safe. For example, the use could be in dynamically unreached
30 if (!V
->hasOneUse()) return 0;
32 bool MadeChange
= false;
34 // ((1 << A) >>u B) --> (1 << (A-B))
35 // Because V cannot be zero, we know that B is less than A.
36 Value
*A
= 0, *B
= 0, *PowerOf2
= 0;
37 if (match(V
, m_LShr(m_OneUse(m_Shl(m_Value(PowerOf2
), m_Value(A
))),
39 // The "1" can be any value known to be a power of 2.
40 isPowerOfTwo(PowerOf2
, IC
.getTargetData())) {
41 A
= IC
.Builder
->CreateSub(A
, B
, "tmp");
42 return IC
.Builder
->CreateShl(PowerOf2
, A
);
45 // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
46 // inexact. Similarly for <<.
47 if (BinaryOperator
*I
= dyn_cast
<BinaryOperator
>(V
))
48 if (I
->isLogicalShift() &&
49 isPowerOfTwo(I
->getOperand(0), IC
.getTargetData())) {
50 // We know that this is an exact/nuw shift and that the input is a
51 // non-zero context as well.
52 if (Value
*V2
= simplifyValueKnownNonZero(I
->getOperand(0), IC
)) {
57 if (I
->getOpcode() == Instruction::LShr
&& !I
->isExact()) {
62 if (I
->getOpcode() == Instruction::Shl
&& !I
->hasNoUnsignedWrap()) {
63 I
->setHasNoUnsignedWrap();
68 // TODO: Lots more we could do here:
69 // If V is a phi node, we can call this on each of its operands.
70 // "select cond, X, 0" can simplify to "X".
72 return MadeChange
? V
: 0;
76 /// MultiplyOverflows - True if the multiply can not be expressed in an int
78 static bool MultiplyOverflows(ConstantInt
*C1
, ConstantInt
*C2
, bool sign
) {
79 uint32_t W
= C1
->getBitWidth();
80 APInt LHSExt
= C1
->getValue(), RHSExt
= C2
->getValue();
82 LHSExt
= LHSExt
.sext(W
* 2);
83 RHSExt
= RHSExt
.sext(W
* 2);
85 LHSExt
= LHSExt
.zext(W
* 2);
86 RHSExt
= RHSExt
.zext(W
* 2);
89 APInt MulExt
= LHSExt
* RHSExt
;
92 return MulExt
.ugt(APInt::getLowBitsSet(W
* 2, W
));
94 APInt Min
= APInt::getSignedMinValue(W
).sext(W
* 2);
95 APInt Max
= APInt::getSignedMaxValue(W
).sext(W
* 2);
96 return MulExt
.slt(Min
) || MulExt
.sgt(Max
);
99 Instruction
*InstCombiner::visitMul(BinaryOperator
&I
) {
100 bool Changed
= SimplifyAssociativeOrCommutative(I
);
101 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
103 if (Value
*V
= SimplifyMulInst(Op0
, Op1
, TD
))
104 return ReplaceInstUsesWith(I
, V
);
106 if (Value
*V
= SimplifyUsingDistributiveLaws(I
))
107 return ReplaceInstUsesWith(I
, V
);
109 if (match(Op1
, m_AllOnes())) // X * -1 == 0 - X
110 return BinaryOperator::CreateNeg(Op0
, I
.getName());
112 if (ConstantInt
*CI
= dyn_cast
<ConstantInt
>(Op1
)) {
114 // ((X << C1)*C2) == (X * (C2 << C1))
115 if (BinaryOperator
*SI
= dyn_cast
<BinaryOperator
>(Op0
))
116 if (SI
->getOpcode() == Instruction::Shl
)
117 if (Constant
*ShOp
= dyn_cast
<Constant
>(SI
->getOperand(1)))
118 return BinaryOperator::CreateMul(SI
->getOperand(0),
119 ConstantExpr::getShl(CI
, ShOp
));
121 const APInt
&Val
= CI
->getValue();
122 if (Val
.isPowerOf2()) { // Replace X*(2^C) with X << C
123 Constant
*NewCst
= ConstantInt::get(Op0
->getType(), Val
.logBase2());
124 BinaryOperator
*Shl
= BinaryOperator::CreateShl(Op0
, NewCst
);
125 if (I
.hasNoSignedWrap()) Shl
->setHasNoSignedWrap();
126 if (I
.hasNoUnsignedWrap()) Shl
->setHasNoUnsignedWrap();
130 // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
131 { Value
*X
; ConstantInt
*C1
;
132 if (Op0
->hasOneUse() &&
133 match(Op0
, m_Add(m_Value(X
), m_ConstantInt(C1
)))) {
134 Value
*Add
= Builder
->CreateMul(X
, CI
, "tmp");
135 return BinaryOperator::CreateAdd(Add
, Builder
->CreateMul(C1
, CI
));
139 // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n
140 // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n
141 // The "* (2**n)" thus becomes a potential shifting opportunity.
143 const APInt
& Val
= CI
->getValue();
144 const APInt
&PosVal
= Val
.abs();
145 if (Val
.isNegative() && PosVal
.isPowerOf2()) {
146 Value
*X
= 0, *Y
= 0;
147 if (Op0
->hasOneUse()) {
150 if (match(Op0
, m_Sub(m_Value(Y
), m_Value(X
))))
151 Sub
= Builder
->CreateSub(X
, Y
, "suba");
152 else if (match(Op0
, m_Add(m_Value(Y
), m_ConstantInt(C1
))))
153 Sub
= Builder
->CreateSub(Builder
->CreateNeg(C1
), Y
, "subc");
156 BinaryOperator::CreateMul(Sub
,
157 ConstantInt::get(Y
->getType(), PosVal
));
163 // Simplify mul instructions with a constant RHS.
164 if (isa
<Constant
>(Op1
)) {
165 // Try to fold constant mul into select arguments.
166 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(Op0
))
167 if (Instruction
*R
= FoldOpIntoSelect(I
, SI
))
170 if (isa
<PHINode
>(Op0
))
171 if (Instruction
*NV
= FoldOpIntoPhi(I
))
175 if (Value
*Op0v
= dyn_castNegVal(Op0
)) // -X * -Y = X*Y
176 if (Value
*Op1v
= dyn_castNegVal(Op1
))
177 return BinaryOperator::CreateMul(Op0v
, Op1v
);
179 // (X / Y) * Y = X - (X % Y)
180 // (X / Y) * -Y = (X % Y) - X
183 BinaryOperator
*BO
= dyn_cast
<BinaryOperator
>(Op0
);
185 (BO
->getOpcode() != Instruction::UDiv
&&
186 BO
->getOpcode() != Instruction::SDiv
)) {
188 BO
= dyn_cast
<BinaryOperator
>(Op1
);
190 Value
*Neg
= dyn_castNegVal(Op1C
);
191 if (BO
&& BO
->hasOneUse() &&
192 (BO
->getOperand(1) == Op1C
|| BO
->getOperand(1) == Neg
) &&
193 (BO
->getOpcode() == Instruction::UDiv
||
194 BO
->getOpcode() == Instruction::SDiv
)) {
195 Value
*Op0BO
= BO
->getOperand(0), *Op1BO
= BO
->getOperand(1);
197 // If the division is exact, X % Y is zero, so we end up with X or -X.
198 if (PossiblyExactOperator
*SDiv
= dyn_cast
<PossiblyExactOperator
>(BO
))
199 if (SDiv
->isExact()) {
201 return ReplaceInstUsesWith(I
, Op0BO
);
202 return BinaryOperator::CreateNeg(Op0BO
);
206 if (BO
->getOpcode() == Instruction::UDiv
)
207 Rem
= Builder
->CreateURem(Op0BO
, Op1BO
);
209 Rem
= Builder
->CreateSRem(Op0BO
, Op1BO
);
213 return BinaryOperator::CreateSub(Op0BO
, Rem
);
214 return BinaryOperator::CreateSub(Rem
, Op0BO
);
218 /// i1 mul -> i1 and.
219 if (I
.getType()->isIntegerTy(1))
220 return BinaryOperator::CreateAnd(Op0
, Op1
);
222 // X*(1 << Y) --> X << Y
223 // (1 << Y)*X --> X << Y
226 if (match(Op0
, m_Shl(m_One(), m_Value(Y
))))
227 return BinaryOperator::CreateShl(Op1
, Y
);
228 if (match(Op1
, m_Shl(m_One(), m_Value(Y
))))
229 return BinaryOperator::CreateShl(Op0
, Y
);
232 // If one of the operands of the multiply is a cast from a boolean value, then
233 // we know the bool is either zero or one, so this is a 'masking' multiply.
234 // X * Y (where Y is 0 or 1) -> X & (0-Y)
235 if (!I
.getType()->isVectorTy()) {
236 // -2 is "-1 << 1" so it is all bits set except the low one.
237 APInt
Negative2(I
.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true);
239 Value
*BoolCast
= 0, *OtherOp
= 0;
240 if (MaskedValueIsZero(Op0
, Negative2
))
241 BoolCast
= Op0
, OtherOp
= Op1
;
242 else if (MaskedValueIsZero(Op1
, Negative2
))
243 BoolCast
= Op1
, OtherOp
= Op0
;
246 Value
*V
= Builder
->CreateSub(Constant::getNullValue(I
.getType()),
248 return BinaryOperator::CreateAnd(V
, OtherOp
);
252 return Changed
? &I
: 0;
255 Instruction
*InstCombiner::visitFMul(BinaryOperator
&I
) {
256 bool Changed
= SimplifyAssociativeOrCommutative(I
);
257 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
259 // Simplify mul instructions with a constant RHS...
260 if (Constant
*Op1C
= dyn_cast
<Constant
>(Op1
)) {
261 if (ConstantFP
*Op1F
= dyn_cast
<ConstantFP
>(Op1C
)) {
262 // "In IEEE floating point, x*1 is not equivalent to x for nans. However,
263 // ANSI says we can drop signals, so we can do this anyway." (from GCC)
264 if (Op1F
->isExactlyValue(1.0))
265 return ReplaceInstUsesWith(I
, Op0
); // Eliminate 'fmul double %X, 1.0'
266 } else if (Op1C
->getType()->isVectorTy()) {
267 if (ConstantVector
*Op1V
= dyn_cast
<ConstantVector
>(Op1C
)) {
268 // As above, vector X*splat(1.0) -> X in all defined cases.
269 if (Constant
*Splat
= Op1V
->getSplatValue()) {
270 if (ConstantFP
*F
= dyn_cast
<ConstantFP
>(Splat
))
271 if (F
->isExactlyValue(1.0))
272 return ReplaceInstUsesWith(I
, Op0
);
277 // Try to fold constant mul into select arguments.
278 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(Op0
))
279 if (Instruction
*R
= FoldOpIntoSelect(I
, SI
))
282 if (isa
<PHINode
>(Op0
))
283 if (Instruction
*NV
= FoldOpIntoPhi(I
))
287 if (Value
*Op0v
= dyn_castFNegVal(Op0
)) // -X * -Y = X*Y
288 if (Value
*Op1v
= dyn_castFNegVal(Op1
))
289 return BinaryOperator::CreateFMul(Op0v
, Op1v
);
291 return Changed
? &I
: 0;
294 /// SimplifyDivRemOfSelect - Try to fold a divide or remainder of a select
296 bool InstCombiner::SimplifyDivRemOfSelect(BinaryOperator
&I
) {
297 SelectInst
*SI
= cast
<SelectInst
>(I
.getOperand(1));
299 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
300 int NonNullOperand
= -1;
301 if (Constant
*ST
= dyn_cast
<Constant
>(SI
->getOperand(1)))
302 if (ST
->isNullValue())
304 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
305 if (Constant
*ST
= dyn_cast
<Constant
>(SI
->getOperand(2)))
306 if (ST
->isNullValue())
309 if (NonNullOperand
== -1)
312 Value
*SelectCond
= SI
->getOperand(0);
314 // Change the div/rem to use 'Y' instead of the select.
315 I
.setOperand(1, SI
->getOperand(NonNullOperand
));
317 // Okay, we know we replace the operand of the div/rem with 'Y' with no
318 // problem. However, the select, or the condition of the select may have
319 // multiple uses. Based on our knowledge that the operand must be non-zero,
320 // propagate the known value for the select into other uses of it, and
321 // propagate a known value of the condition into its other users.
323 // If the select and condition only have a single use, don't bother with this,
325 if (SI
->use_empty() && SelectCond
->hasOneUse())
328 // Scan the current block backward, looking for other uses of SI.
329 BasicBlock::iterator BBI
= &I
, BBFront
= I
.getParent()->begin();
331 while (BBI
!= BBFront
) {
333 // If we found a call to a function, we can't assume it will return, so
334 // information from below it cannot be propagated above it.
335 if (isa
<CallInst
>(BBI
) && !isa
<IntrinsicInst
>(BBI
))
338 // Replace uses of the select or its condition with the known values.
339 for (Instruction::op_iterator I
= BBI
->op_begin(), E
= BBI
->op_end();
342 *I
= SI
->getOperand(NonNullOperand
);
344 } else if (*I
== SelectCond
) {
345 *I
= NonNullOperand
== 1 ? ConstantInt::getTrue(BBI
->getContext()) :
346 ConstantInt::getFalse(BBI
->getContext());
351 // If we past the instruction, quit looking for it.
354 if (&*BBI
== SelectCond
)
357 // If we ran out of things to eliminate, break out of the loop.
358 if (SelectCond
== 0 && SI
== 0)
366 /// This function implements the transforms common to both integer division
367 /// instructions (udiv and sdiv). It is called by the visitors to those integer
368 /// division instructions.
369 /// @brief Common integer divide transforms
370 Instruction
*InstCombiner::commonIDivTransforms(BinaryOperator
&I
) {
371 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
373 // The RHS is known non-zero.
374 if (Value
*V
= simplifyValueKnownNonZero(I
.getOperand(1), *this)) {
379 // Handle cases involving: [su]div X, (select Cond, Y, Z)
380 // This does not apply for fdiv.
381 if (isa
<SelectInst
>(Op1
) && SimplifyDivRemOfSelect(I
))
384 if (ConstantInt
*RHS
= dyn_cast
<ConstantInt
>(Op1
)) {
385 // (X / C1) / C2 -> X / (C1*C2)
386 if (Instruction
*LHS
= dyn_cast
<Instruction
>(Op0
))
387 if (Instruction::BinaryOps(LHS
->getOpcode()) == I
.getOpcode())
388 if (ConstantInt
*LHSRHS
= dyn_cast
<ConstantInt
>(LHS
->getOperand(1))) {
389 if (MultiplyOverflows(RHS
, LHSRHS
,
390 I
.getOpcode()==Instruction::SDiv
))
391 return ReplaceInstUsesWith(I
, Constant::getNullValue(I
.getType()));
392 return BinaryOperator::Create(I
.getOpcode(), LHS
->getOperand(0),
393 ConstantExpr::getMul(RHS
, LHSRHS
));
396 if (!RHS
->isZero()) { // avoid X udiv 0
397 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(Op0
))
398 if (Instruction
*R
= FoldOpIntoSelect(I
, SI
))
400 if (isa
<PHINode
>(Op0
))
401 if (Instruction
*NV
= FoldOpIntoPhi(I
))
406 // See if we can fold away this div instruction.
407 if (SimplifyDemandedInstructionBits(I
))
410 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
411 Value
*X
= 0, *Z
= 0;
412 if (match(Op0
, m_Sub(m_Value(X
), m_Value(Z
)))) { // (X - Z) / Y; Y = Op1
413 bool isSigned
= I
.getOpcode() == Instruction::SDiv
;
414 if ((isSigned
&& match(Z
, m_SRem(m_Specific(X
), m_Specific(Op1
)))) ||
415 (!isSigned
&& match(Z
, m_URem(m_Specific(X
), m_Specific(Op1
)))))
416 return BinaryOperator::Create(I
.getOpcode(), X
, Op1
);
422 /// dyn_castZExtVal - Checks if V is a zext or constant that can
423 /// be truncated to Ty without losing bits.
424 static Value
*dyn_castZExtVal(Value
*V
, const Type
*Ty
) {
425 if (ZExtInst
*Z
= dyn_cast
<ZExtInst
>(V
)) {
426 if (Z
->getSrcTy() == Ty
)
427 return Z
->getOperand(0);
428 } else if (ConstantInt
*C
= dyn_cast
<ConstantInt
>(V
)) {
429 if (C
->getValue().getActiveBits() <= cast
<IntegerType
>(Ty
)->getBitWidth())
430 return ConstantExpr::getTrunc(C
, Ty
);
435 Instruction
*InstCombiner::visitUDiv(BinaryOperator
&I
) {
436 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
438 if (Value
*V
= SimplifyUDivInst(Op0
, Op1
, TD
))
439 return ReplaceInstUsesWith(I
, V
);
441 // Handle the integer div common cases
442 if (Instruction
*Common
= commonIDivTransforms(I
))
445 if (ConstantInt
*C
= dyn_cast
<ConstantInt
>(Op1
)) {
446 // X udiv 2^C -> X >> C
447 // Check to see if this is an unsigned division with an exact power of 2,
448 // if so, convert to a right shift.
449 if (C
->getValue().isPowerOf2()) { // 0 not included in isPowerOf2
450 BinaryOperator
*LShr
=
451 BinaryOperator::CreateLShr(Op0
,
452 ConstantInt::get(Op0
->getType(), C
->getValue().logBase2()));
453 if (I
.isExact()) LShr
->setIsExact();
457 // X udiv C, where C >= signbit
458 if (C
->getValue().isNegative()) {
459 Value
*IC
= Builder
->CreateICmpULT(Op0
, C
);
460 return SelectInst::Create(IC
, Constant::getNullValue(I
.getType()),
461 ConstantInt::get(I
.getType(), 1));
465 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
466 { const APInt
*CI
; Value
*N
;
467 if (match(Op1
, m_Shl(m_Power2(CI
), m_Value(N
)))) {
469 N
= Builder
->CreateAdd(N
, ConstantInt::get(I
.getType(), CI
->logBase2()),
472 return BinaryOperator::CreateExactLShr(Op0
, N
);
473 return BinaryOperator::CreateLShr(Op0
, N
);
477 // udiv X, (Select Cond, C1, C2) --> Select Cond, (shr X, C1), (shr X, C2)
478 // where C1&C2 are powers of two.
479 { Value
*Cond
; const APInt
*C1
, *C2
;
480 if (match(Op1
, m_Select(m_Value(Cond
), m_Power2(C1
), m_Power2(C2
)))) {
481 // Construct the "on true" case of the select
482 Value
*TSI
= Builder
->CreateLShr(Op0
, C1
->logBase2(), Op1
->getName()+".t",
485 // Construct the "on false" case of the select
486 Value
*FSI
= Builder
->CreateLShr(Op0
, C2
->logBase2(), Op1
->getName()+".f",
489 // construct the select instruction and return it.
490 return SelectInst::Create(Cond
, TSI
, FSI
);
494 // (zext A) udiv (zext B) --> zext (A udiv B)
495 if (ZExtInst
*ZOp0
= dyn_cast
<ZExtInst
>(Op0
))
496 if (Value
*ZOp1
= dyn_castZExtVal(Op1
, ZOp0
->getSrcTy()))
497 return new ZExtInst(Builder
->CreateUDiv(ZOp0
->getOperand(0), ZOp1
, "div",
504 Instruction
*InstCombiner::visitSDiv(BinaryOperator
&I
) {
505 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
507 if (Value
*V
= SimplifySDivInst(Op0
, Op1
, TD
))
508 return ReplaceInstUsesWith(I
, V
);
510 // Handle the integer div common cases
511 if (Instruction
*Common
= commonIDivTransforms(I
))
514 if (ConstantInt
*RHS
= dyn_cast
<ConstantInt
>(Op1
)) {
516 if (RHS
->isAllOnesValue())
517 return BinaryOperator::CreateNeg(Op0
);
519 // sdiv X, C --> ashr exact X, log2(C)
520 if (I
.isExact() && RHS
->getValue().isNonNegative() &&
521 RHS
->getValue().isPowerOf2()) {
522 Value
*ShAmt
= llvm::ConstantInt::get(RHS
->getType(),
523 RHS
->getValue().exactLogBase2());
524 return BinaryOperator::CreateExactAShr(Op0
, ShAmt
, I
.getName());
527 // -X/C --> X/-C provided the negation doesn't overflow.
528 if (SubOperator
*Sub
= dyn_cast
<SubOperator
>(Op0
))
529 if (match(Sub
->getOperand(0), m_Zero()) && Sub
->hasNoSignedWrap())
530 return BinaryOperator::CreateSDiv(Sub
->getOperand(1),
531 ConstantExpr::getNeg(RHS
));
534 // If the sign bits of both operands are zero (i.e. we can prove they are
535 // unsigned inputs), turn this into a udiv.
536 if (I
.getType()->isIntegerTy()) {
537 APInt
Mask(APInt::getSignBit(I
.getType()->getPrimitiveSizeInBits()));
538 if (MaskedValueIsZero(Op0
, Mask
)) {
539 if (MaskedValueIsZero(Op1
, Mask
)) {
540 // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
541 return BinaryOperator::CreateUDiv(Op0
, Op1
, I
.getName());
544 if (match(Op1
, m_Shl(m_Power2(), m_Value()))) {
545 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
546 // Safe because the only negative value (1 << Y) can take on is
547 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
549 return BinaryOperator::CreateUDiv(Op0
, Op1
, I
.getName());
557 Instruction
*InstCombiner::visitFDiv(BinaryOperator
&I
) {
558 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
560 if (Value
*V
= SimplifyFDivInst(Op0
, Op1
, TD
))
561 return ReplaceInstUsesWith(I
, V
);
563 if (ConstantFP
*Op1C
= dyn_cast
<ConstantFP
>(Op1
)) {
564 const APFloat
&Op1F
= Op1C
->getValueAPF();
566 // If the divisor has an exact multiplicative inverse we can turn the fdiv
567 // into a cheaper fmul.
568 APFloat
Reciprocal(Op1F
.getSemantics());
569 if (Op1F
.getExactInverse(&Reciprocal
)) {
570 ConstantFP
*RFP
= ConstantFP::get(Builder
->getContext(), Reciprocal
);
571 return BinaryOperator::CreateFMul(Op0
, RFP
);
578 /// This function implements the transforms common to both integer remainder
579 /// instructions (urem and srem). It is called by the visitors to those integer
580 /// remainder instructions.
581 /// @brief Common integer remainder transforms
582 Instruction
*InstCombiner::commonIRemTransforms(BinaryOperator
&I
) {
583 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
585 // The RHS is known non-zero.
586 if (Value
*V
= simplifyValueKnownNonZero(I
.getOperand(1), *this)) {
591 // Handle cases involving: rem X, (select Cond, Y, Z)
592 if (isa
<SelectInst
>(Op1
) && SimplifyDivRemOfSelect(I
))
595 if (isa
<ConstantInt
>(Op1
)) {
596 if (Instruction
*Op0I
= dyn_cast
<Instruction
>(Op0
)) {
597 if (SelectInst
*SI
= dyn_cast
<SelectInst
>(Op0I
)) {
598 if (Instruction
*R
= FoldOpIntoSelect(I
, SI
))
600 } else if (isa
<PHINode
>(Op0I
)) {
601 if (Instruction
*NV
= FoldOpIntoPhi(I
))
605 // See if we can fold away this rem instruction.
606 if (SimplifyDemandedInstructionBits(I
))
614 Instruction
*InstCombiner::visitURem(BinaryOperator
&I
) {
615 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
617 if (Value
*V
= SimplifyURemInst(Op0
, Op1
, TD
))
618 return ReplaceInstUsesWith(I
, V
);
620 if (Instruction
*common
= commonIRemTransforms(I
))
623 // X urem C^2 -> X and C-1
625 if (match(Op1
, m_Power2(C
)))
626 return BinaryOperator::CreateAnd(Op0
,
627 ConstantInt::get(I
.getType(), *C
-1));
630 // Turn A % (C << N), where C is 2^k, into A & ((C << N)-1)
631 if (match(Op1
, m_Shl(m_Power2(), m_Value()))) {
632 Constant
*N1
= Constant::getAllOnesValue(I
.getType());
633 Value
*Add
= Builder
->CreateAdd(Op1
, N1
, "tmp");
634 return BinaryOperator::CreateAnd(Op0
, Add
);
637 // urem X, (select Cond, 2^C1, 2^C2) -->
638 // select Cond, (and X, C1-1), (and X, C2-1)
639 // when C1&C2 are powers of two.
640 { Value
*Cond
; const APInt
*C1
, *C2
;
641 if (match(Op1
, m_Select(m_Value(Cond
), m_Power2(C1
), m_Power2(C2
)))) {
642 Value
*TrueAnd
= Builder
->CreateAnd(Op0
, *C1
-1, Op1
->getName()+".t");
643 Value
*FalseAnd
= Builder
->CreateAnd(Op0
, *C2
-1, Op1
->getName()+".f");
644 return SelectInst::Create(Cond
, TrueAnd
, FalseAnd
);
648 // (zext A) urem (zext B) --> zext (A urem B)
649 if (ZExtInst
*ZOp0
= dyn_cast
<ZExtInst
>(Op0
))
650 if (Value
*ZOp1
= dyn_castZExtVal(Op1
, ZOp0
->getSrcTy()))
651 return new ZExtInst(Builder
->CreateURem(ZOp0
->getOperand(0), ZOp1
),
657 Instruction
*InstCombiner::visitSRem(BinaryOperator
&I
) {
658 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
660 if (Value
*V
= SimplifySRemInst(Op0
, Op1
, TD
))
661 return ReplaceInstUsesWith(I
, V
);
663 // Handle the integer rem common cases
664 if (Instruction
*Common
= commonIRemTransforms(I
))
667 if (Value
*RHSNeg
= dyn_castNegVal(Op1
))
668 if (!isa
<Constant
>(RHSNeg
) ||
669 (isa
<ConstantInt
>(RHSNeg
) &&
670 cast
<ConstantInt
>(RHSNeg
)->getValue().isStrictlyPositive())) {
672 Worklist
.AddValue(I
.getOperand(1));
673 I
.setOperand(1, RHSNeg
);
677 // If the sign bits of both operands are zero (i.e. we can prove they are
678 // unsigned inputs), turn this into a urem.
679 if (I
.getType()->isIntegerTy()) {
680 APInt
Mask(APInt::getSignBit(I
.getType()->getPrimitiveSizeInBits()));
681 if (MaskedValueIsZero(Op1
, Mask
) && MaskedValueIsZero(Op0
, Mask
)) {
682 // X srem Y -> X urem Y, iff X and Y don't have sign bit set
683 return BinaryOperator::CreateURem(Op0
, Op1
, I
.getName());
687 // If it's a constant vector, flip any negative values positive.
688 if (ConstantVector
*RHSV
= dyn_cast
<ConstantVector
>(Op1
)) {
689 unsigned VWidth
= RHSV
->getNumOperands();
691 bool hasNegative
= false;
692 for (unsigned i
= 0; !hasNegative
&& i
!= VWidth
; ++i
)
693 if (ConstantInt
*RHS
= dyn_cast
<ConstantInt
>(RHSV
->getOperand(i
)))
694 if (RHS
->getValue().isNegative())
698 std::vector
<Constant
*> Elts(VWidth
);
699 for (unsigned i
= 0; i
!= VWidth
; ++i
) {
700 if (ConstantInt
*RHS
= dyn_cast
<ConstantInt
>(RHSV
->getOperand(i
))) {
701 if (RHS
->getValue().isNegative())
702 Elts
[i
] = cast
<ConstantInt
>(ConstantExpr::getNeg(RHS
));
708 Constant
*NewRHSV
= ConstantVector::get(Elts
);
709 if (NewRHSV
!= RHSV
) {
710 Worklist
.AddValue(I
.getOperand(1));
711 I
.setOperand(1, NewRHSV
);
720 Instruction
*InstCombiner::visitFRem(BinaryOperator
&I
) {
721 Value
*Op0
= I
.getOperand(0), *Op1
= I
.getOperand(1);
723 if (Value
*V
= SimplifyFRemInst(Op0
, Op1
, TD
))
724 return ReplaceInstUsesWith(I
, V
);
726 // Handle cases involving: rem X, (select Cond, Y, Z)
727 if (isa
<SelectInst
>(Op1
) && SimplifyDivRemOfSelect(I
))