1 //===- InstCombineMulDivRem.cpp -------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv,
10 // srem, urem, frem.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "InstCombineInternal.h"
15 #include "llvm/ADT/APInt.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/Analysis/InstructionSimplify.h"
18 #include "llvm/Analysis/ValueTracking.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/Constant.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/InstrTypes.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/IntrinsicInst.h"
26 #include "llvm/IR/Intrinsics.h"
27 #include "llvm/IR/Operator.h"
28 #include "llvm/IR/PatternMatch.h"
29 #include "llvm/IR/Type.h"
30 #include "llvm/IR/Value.h"
31 #include "llvm/Support/Casting.h"
32 #include "llvm/Support/ErrorHandling.h"
33 #include "llvm/Transforms/InstCombine/InstCombiner.h"
34 #include "llvm/Transforms/Utils/BuildLibCalls.h"
35 #include <cassert>
36
37 #define DEBUG_TYPE "instcombine"
38 #include "llvm/Transforms/Utils/InstructionWorklist.h"
39
40 using namespace llvm;
41 using namespace PatternMatch;
42
43 /// The specific integer value is used in a context where it is known to be
44 /// non-zero. If this allows us to simplify the computation, do so and return
45 /// the new operand, otherwise return null.
simplifyValueKnownNonZero(Value * V,InstCombinerImpl & IC,Instruction & CxtI)46 static Value *simplifyValueKnownNonZero(Value *V, InstCombinerImpl &IC,
47 Instruction &CxtI) {
48 // If V has multiple uses, then we would have to do more analysis to determine
49 // if this is safe. For example, the use could be in dynamically unreached
50 // code.
51 if (!V->hasOneUse()) return nullptr;
52
53 bool MadeChange = false;
54
55 // ((1 << A) >>u B) --> (1 << (A-B))
56 // Because V cannot be zero, we know that B is less than A.
57 Value *A = nullptr, *B = nullptr, *One = nullptr;
58 if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) &&
59 match(One, m_One())) {
60 A = IC.Builder.CreateSub(A, B);
61 return IC.Builder.CreateShl(One, A);
62 }
63
64 // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
65 // inexact. Similarly for <<.
66 BinaryOperator *I = dyn_cast<BinaryOperator>(V);
67 if (I && I->isLogicalShift() &&
68 IC.isKnownToBeAPowerOfTwo(I->getOperand(0), false, 0, &CxtI)) {
69 // We know that this is an exact/nuw shift and that the input is a
70 // non-zero context as well.
71 if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) {
72 IC.replaceOperand(*I, 0, V2);
73 MadeChange = true;
74 }
75
76 if (I->getOpcode() == Instruction::LShr && !I->isExact()) {
77 I->setIsExact();
78 MadeChange = true;
79 }
80
81 if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) {
82 I->setHasNoUnsignedWrap();
83 MadeChange = true;
84 }
85 }
86
87 // TODO: Lots more we could do here:
88 // If V is a phi node, we can call this on each of its operands.
89 // "select cond, X, 0" can simplify to "X".
90
91 return MadeChange ? V : nullptr;
92 }
93
94 // TODO: This is a specific form of a much more general pattern.
95 // We could detect a select with any binop identity constant, or we
96 // could use SimplifyBinOp to see if either arm of the select reduces.
97 // But that needs to be done carefully and/or while removing potential
98 // reverse canonicalizations as in InstCombiner::foldSelectIntoOp().
foldMulSelectToNegate(BinaryOperator & I,InstCombiner::BuilderTy & Builder)99 static Value *foldMulSelectToNegate(BinaryOperator &I,
100 InstCombiner::BuilderTy &Builder) {
101 Value *Cond, *OtherOp;
102
103 // mul (select Cond, 1, -1), OtherOp --> select Cond, OtherOp, -OtherOp
104 // mul OtherOp, (select Cond, 1, -1) --> select Cond, OtherOp, -OtherOp
105 if (match(&I, m_c_Mul(m_OneUse(m_Select(m_Value(Cond), m_One(), m_AllOnes())),
106 m_Value(OtherOp)))) {
107 bool HasAnyNoWrap = I.hasNoSignedWrap() || I.hasNoUnsignedWrap();
108 Value *Neg = Builder.CreateNeg(OtherOp, "", false, HasAnyNoWrap);
109 return Builder.CreateSelect(Cond, OtherOp, Neg);
110 }
111 // mul (select Cond, -1, 1), OtherOp --> select Cond, -OtherOp, OtherOp
112 // mul OtherOp, (select Cond, -1, 1) --> select Cond, -OtherOp, OtherOp
113 if (match(&I, m_c_Mul(m_OneUse(m_Select(m_Value(Cond), m_AllOnes(), m_One())),
114 m_Value(OtherOp)))) {
115 bool HasAnyNoWrap = I.hasNoSignedWrap() || I.hasNoUnsignedWrap();
116 Value *Neg = Builder.CreateNeg(OtherOp, "", false, HasAnyNoWrap);
117 return Builder.CreateSelect(Cond, Neg, OtherOp);
118 }
119
120 // fmul (select Cond, 1.0, -1.0), OtherOp --> select Cond, OtherOp, -OtherOp
121 // fmul OtherOp, (select Cond, 1.0, -1.0) --> select Cond, OtherOp, -OtherOp
122 if (match(&I, m_c_FMul(m_OneUse(m_Select(m_Value(Cond), m_SpecificFP(1.0),
123 m_SpecificFP(-1.0))),
124 m_Value(OtherOp)))) {
125 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
126 Builder.setFastMathFlags(I.getFastMathFlags());
127 return Builder.CreateSelect(Cond, OtherOp, Builder.CreateFNeg(OtherOp));
128 }
129
130 // fmul (select Cond, -1.0, 1.0), OtherOp --> select Cond, -OtherOp, OtherOp
131 // fmul OtherOp, (select Cond, -1.0, 1.0) --> select Cond, -OtherOp, OtherOp
132 if (match(&I, m_c_FMul(m_OneUse(m_Select(m_Value(Cond), m_SpecificFP(-1.0),
133 m_SpecificFP(1.0))),
134 m_Value(OtherOp)))) {
135 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
136 Builder.setFastMathFlags(I.getFastMathFlags());
137 return Builder.CreateSelect(Cond, Builder.CreateFNeg(OtherOp), OtherOp);
138 }
139
140 return nullptr;
141 }
142
143 /// Reduce integer multiplication patterns that contain a (+/-1 << Z) factor.
144 /// Callers are expected to call this twice to handle commuted patterns.
foldMulShl1(BinaryOperator & Mul,bool CommuteOperands,InstCombiner::BuilderTy & Builder)145 static Value *foldMulShl1(BinaryOperator &Mul, bool CommuteOperands,
146 InstCombiner::BuilderTy &Builder) {
147 Value *X = Mul.getOperand(0), *Y = Mul.getOperand(1);
148 if (CommuteOperands)
149 std::swap(X, Y);
150
151 const bool HasNSW = Mul.hasNoSignedWrap();
152 const bool HasNUW = Mul.hasNoUnsignedWrap();
153
154 // X * (1 << Z) --> X << Z
155 Value *Z;
156 if (match(Y, m_Shl(m_One(), m_Value(Z)))) {
157 bool PropagateNSW = HasNSW && cast<ShlOperator>(Y)->hasNoSignedWrap();
158 return Builder.CreateShl(X, Z, Mul.getName(), HasNUW, PropagateNSW);
159 }
160
161 // Similar to above, but an increment of the shifted value becomes an add:
162 // X * ((1 << Z) + 1) --> (X * (1 << Z)) + X --> (X << Z) + X
163 // This increases uses of X, so it may require a freeze, but that is still
164 // expected to be an improvement because it removes the multiply.
165 BinaryOperator *Shift;
166 if (match(Y, m_OneUse(m_Add(m_BinOp(Shift), m_One()))) &&
167 match(Shift, m_OneUse(m_Shl(m_One(), m_Value(Z))))) {
168 bool PropagateNSW = HasNSW && Shift->hasNoSignedWrap();
169 Value *FrX = Builder.CreateFreeze(X, X->getName() + ".fr");
170 Value *Shl = Builder.CreateShl(FrX, Z, "mulshl", HasNUW, PropagateNSW);
171 return Builder.CreateAdd(Shl, FrX, Mul.getName(), HasNUW, PropagateNSW);
172 }
173
174 // Similar to above, but a decrement of the shifted value is disguised as
175 // 'not' and becomes a sub:
176 // X * (~(-1 << Z)) --> X * ((1 << Z) - 1) --> (X << Z) - X
177 // This increases uses of X, so it may require a freeze, but that is still
178 // expected to be an improvement because it removes the multiply.
179 if (match(Y, m_OneUse(m_Not(m_OneUse(m_Shl(m_AllOnes(), m_Value(Z))))))) {
180 Value *FrX = Builder.CreateFreeze(X, X->getName() + ".fr");
181 Value *Shl = Builder.CreateShl(FrX, Z, "mulshl");
182 return Builder.CreateSub(Shl, FrX, Mul.getName());
183 }
184
185 return nullptr;
186 }
187
visitMul(BinaryOperator & I)188 Instruction *InstCombinerImpl::visitMul(BinaryOperator &I) {
189 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
190 if (Value *V =
191 simplifyMulInst(Op0, Op1, I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
192 SQ.getWithInstruction(&I)))
193 return replaceInstUsesWith(I, V);
194
195 if (SimplifyAssociativeOrCommutative(I))
196 return &I;
197
198 if (Instruction *X = foldVectorBinop(I))
199 return X;
200
201 if (Instruction *Phi = foldBinopWithPhiOperands(I))
202 return Phi;
203
204 if (Value *V = foldUsingDistributiveLaws(I))
205 return replaceInstUsesWith(I, V);
206
207 Type *Ty = I.getType();
208 const unsigned BitWidth = Ty->getScalarSizeInBits();
209 const bool HasNSW = I.hasNoSignedWrap();
210 const bool HasNUW = I.hasNoUnsignedWrap();
211
212 // X * -1 --> 0 - X
213 if (match(Op1, m_AllOnes())) {
214 return HasNSW ? BinaryOperator::CreateNSWNeg(Op0)
215 : BinaryOperator::CreateNeg(Op0);
216 }
217
218 // Also allow combining multiply instructions on vectors.
219 {
220 Value *NewOp;
221 Constant *C1, *C2;
222 const APInt *IVal;
223 if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
224 m_Constant(C1))) &&
225 match(C1, m_APInt(IVal))) {
226 // ((X << C2)*C1) == (X * (C1 << C2))
227 Constant *Shl = ConstantExpr::getShl(C1, C2);
228 BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0));
229 BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl);
230 if (HasNUW && Mul->hasNoUnsignedWrap())
231 BO->setHasNoUnsignedWrap();
232 if (HasNSW && Mul->hasNoSignedWrap() && Shl->isNotMinSignedValue())
233 BO->setHasNoSignedWrap();
234 return BO;
235 }
236
237 if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
238 // Replace X*(2^C) with X << C, where C is either a scalar or a vector.
239 if (Constant *NewCst = ConstantExpr::getExactLogBase2(C1)) {
240 BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
241
242 if (HasNUW)
243 Shl->setHasNoUnsignedWrap();
244 if (HasNSW) {
245 const APInt *V;
246 if (match(NewCst, m_APInt(V)) && *V != V->getBitWidth() - 1)
247 Shl->setHasNoSignedWrap();
248 }
249
250 return Shl;
251 }
252 }
253 }
254
255 if (Op0->hasOneUse() && match(Op1, m_NegatedPower2())) {
256 // Interpret X * (-1<<C) as (-X) * (1<<C) and try to sink the negation.
257 // The "* (1<<C)" thus becomes a potential shifting opportunity.
258 if (Value *NegOp0 = Negator::Negate(/*IsNegation*/ true, Op0, *this))
259 return BinaryOperator::CreateMul(
260 NegOp0, ConstantExpr::getNeg(cast<Constant>(Op1)), I.getName());
261
262 // Try to convert multiply of extended operand to narrow negate and shift
263 // for better analysis.
264 // This is valid if the shift amount (trailing zeros in the multiplier
265 // constant) clears more high bits than the bitwidth difference between
266 // source and destination types:
267 // ({z/s}ext X) * (-1<<C) --> (zext (-X)) << C
268 const APInt *NegPow2C;
269 Value *X;
270 if (match(Op0, m_ZExtOrSExt(m_Value(X))) &&
271 match(Op1, m_APIntAllowUndef(NegPow2C))) {
272 unsigned SrcWidth = X->getType()->getScalarSizeInBits();
273 unsigned ShiftAmt = NegPow2C->countTrailingZeros();
274 if (ShiftAmt >= BitWidth - SrcWidth) {
275 Value *N = Builder.CreateNeg(X, X->getName() + ".neg");
276 Value *Z = Builder.CreateZExt(N, Ty, N->getName() + ".z");
277 return BinaryOperator::CreateShl(Z, ConstantInt::get(Ty, ShiftAmt));
278 }
279 }
280 }
281
282 if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
283 return FoldedMul;
284
285 if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
286 return replaceInstUsesWith(I, FoldedMul);
287
288 // Simplify mul instructions with a constant RHS.
289 Constant *MulC;
290 if (match(Op1, m_ImmConstant(MulC))) {
291 // Canonicalize (X+C1)*MulC -> X*MulC+C1*MulC.
292 // Canonicalize (X|C1)*MulC -> X*MulC+C1*MulC.
293 Value *X;
294 Constant *C1;
295 if ((match(Op0, m_OneUse(m_Add(m_Value(X), m_ImmConstant(C1))))) ||
296 (match(Op0, m_OneUse(m_Or(m_Value(X), m_ImmConstant(C1)))) &&
297 haveNoCommonBitsSet(X, C1, DL, &AC, &I, &DT))) {
298 // C1*MulC simplifies to a tidier constant.
299 Value *NewC = Builder.CreateMul(C1, MulC);
300 auto *BOp0 = cast<BinaryOperator>(Op0);
301 bool Op0NUW =
302 (BOp0->getOpcode() == Instruction::Or || BOp0->hasNoUnsignedWrap());
303 Value *NewMul = Builder.CreateMul(X, MulC);
304 auto *BO = BinaryOperator::CreateAdd(NewMul, NewC);
305 if (HasNUW && Op0NUW) {
306 // If NewMulBO is constant we also can set BO to nuw.
307 if (auto *NewMulBO = dyn_cast<BinaryOperator>(NewMul))
308 NewMulBO->setHasNoUnsignedWrap();
309 BO->setHasNoUnsignedWrap();
310 }
311 return BO;
312 }
313 }
314
315 // abs(X) * abs(X) -> X * X
316 // nabs(X) * nabs(X) -> X * X
317 if (Op0 == Op1) {
318 Value *X, *Y;
319 SelectPatternFlavor SPF = matchSelectPattern(Op0, X, Y).Flavor;
320 if (SPF == SPF_ABS || SPF == SPF_NABS)
321 return BinaryOperator::CreateMul(X, X);
322
323 if (match(Op0, m_Intrinsic<Intrinsic::abs>(m_Value(X))))
324 return BinaryOperator::CreateMul(X, X);
325 }
326
327 // -X * C --> X * -C
328 Value *X, *Y;
329 Constant *Op1C;
330 if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Constant(Op1C)))
331 return BinaryOperator::CreateMul(X, ConstantExpr::getNeg(Op1C));
332
333 // -X * -Y --> X * Y
334 if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Neg(m_Value(Y)))) {
335 auto *NewMul = BinaryOperator::CreateMul(X, Y);
336 if (HasNSW && cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap() &&
337 cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap())
338 NewMul->setHasNoSignedWrap();
339 return NewMul;
340 }
341
342 // -X * Y --> -(X * Y)
343 // X * -Y --> -(X * Y)
344 if (match(&I, m_c_Mul(m_OneUse(m_Neg(m_Value(X))), m_Value(Y))))
345 return BinaryOperator::CreateNeg(Builder.CreateMul(X, Y));
346
347 // (X / Y) * Y = X - (X % Y)
348 // (X / Y) * -Y = (X % Y) - X
349 {
350 Value *Y = Op1;
351 BinaryOperator *Div = dyn_cast<BinaryOperator>(Op0);
352 if (!Div || (Div->getOpcode() != Instruction::UDiv &&
353 Div->getOpcode() != Instruction::SDiv)) {
354 Y = Op0;
355 Div = dyn_cast<BinaryOperator>(Op1);
356 }
357 Value *Neg = dyn_castNegVal(Y);
358 if (Div && Div->hasOneUse() &&
359 (Div->getOperand(1) == Y || Div->getOperand(1) == Neg) &&
360 (Div->getOpcode() == Instruction::UDiv ||
361 Div->getOpcode() == Instruction::SDiv)) {
362 Value *X = Div->getOperand(0), *DivOp1 = Div->getOperand(1);
363
364 // If the division is exact, X % Y is zero, so we end up with X or -X.
365 if (Div->isExact()) {
366 if (DivOp1 == Y)
367 return replaceInstUsesWith(I, X);
368 return BinaryOperator::CreateNeg(X);
369 }
370
371 auto RemOpc = Div->getOpcode() == Instruction::UDiv ? Instruction::URem
372 : Instruction::SRem;
373 // X must be frozen because we are increasing its number of uses.
374 Value *XFreeze = Builder.CreateFreeze(X, X->getName() + ".fr");
375 Value *Rem = Builder.CreateBinOp(RemOpc, XFreeze, DivOp1);
376 if (DivOp1 == Y)
377 return BinaryOperator::CreateSub(XFreeze, Rem);
378 return BinaryOperator::CreateSub(Rem, XFreeze);
379 }
380 }
381
382 // Fold the following two scenarios:
383 // 1) i1 mul -> i1 and.
384 // 2) X * Y --> X & Y, iff X, Y can be only {0,1}.
385 // Note: We could use known bits to generalize this and related patterns with
386 // shifts/truncs
387 if (Ty->isIntOrIntVectorTy(1) ||
388 (match(Op0, m_And(m_Value(), m_One())) &&
389 match(Op1, m_And(m_Value(), m_One()))))
390 return BinaryOperator::CreateAnd(Op0, Op1);
391
392 if (Value *R = foldMulShl1(I, /* CommuteOperands */ false, Builder))
393 return replaceInstUsesWith(I, R);
394 if (Value *R = foldMulShl1(I, /* CommuteOperands */ true, Builder))
395 return replaceInstUsesWith(I, R);
396
397 // (zext bool X) * (zext bool Y) --> zext (and X, Y)
398 // (sext bool X) * (sext bool Y) --> zext (and X, Y)
399 // Note: -1 * -1 == 1 * 1 == 1 (if the extends match, the result is the same)
400 if (((match(Op0, m_ZExt(m_Value(X))) && match(Op1, m_ZExt(m_Value(Y)))) ||
401 (match(Op0, m_SExt(m_Value(X))) && match(Op1, m_SExt(m_Value(Y))))) &&
402 X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType() &&
403 (Op0->hasOneUse() || Op1->hasOneUse() || X == Y)) {
404 Value *And = Builder.CreateAnd(X, Y, "mulbool");
405 return CastInst::Create(Instruction::ZExt, And, Ty);
406 }
407 // (sext bool X) * (zext bool Y) --> sext (and X, Y)
408 // (zext bool X) * (sext bool Y) --> sext (and X, Y)
409 // Note: -1 * 1 == 1 * -1 == -1
410 if (((match(Op0, m_SExt(m_Value(X))) && match(Op1, m_ZExt(m_Value(Y)))) ||
411 (match(Op0, m_ZExt(m_Value(X))) && match(Op1, m_SExt(m_Value(Y))))) &&
412 X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType() &&
413 (Op0->hasOneUse() || Op1->hasOneUse())) {
414 Value *And = Builder.CreateAnd(X, Y, "mulbool");
415 return CastInst::Create(Instruction::SExt, And, Ty);
416 }
417
418 // (zext bool X) * Y --> X ? Y : 0
419 // Y * (zext bool X) --> X ? Y : 0
420 if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
421 return SelectInst::Create(X, Op1, ConstantInt::getNullValue(Ty));
422 if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
423 return SelectInst::Create(X, Op0, ConstantInt::getNullValue(Ty));
424
425 Constant *ImmC;
426 if (match(Op1, m_ImmConstant(ImmC))) {
427 // (sext bool X) * C --> X ? -C : 0
428 if (match(Op0, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
429 Constant *NegC = ConstantExpr::getNeg(ImmC);
430 return SelectInst::Create(X, NegC, ConstantInt::getNullValue(Ty));
431 }
432
433 // (ashr i32 X, 31) * C --> (X < 0) ? -C : 0
434 const APInt *C;
435 if (match(Op0, m_OneUse(m_AShr(m_Value(X), m_APInt(C)))) &&
436 *C == C->getBitWidth() - 1) {
437 Constant *NegC = ConstantExpr::getNeg(ImmC);
438 Value *IsNeg = Builder.CreateIsNeg(X, "isneg");
439 return SelectInst::Create(IsNeg, NegC, ConstantInt::getNullValue(Ty));
440 }
441 }
442
443 // (lshr X, 31) * Y --> (X < 0) ? Y : 0
444 // TODO: We are not checking one-use because the elimination of the multiply
445 // is better for analysis?
446 const APInt *C;
447 if (match(&I, m_c_BinOp(m_LShr(m_Value(X), m_APInt(C)), m_Value(Y))) &&
448 *C == C->getBitWidth() - 1) {
449 Value *IsNeg = Builder.CreateIsNeg(X, "isneg");
450 return SelectInst::Create(IsNeg, Y, ConstantInt::getNullValue(Ty));
451 }
452
453 // (and X, 1) * Y --> (trunc X) ? Y : 0
454 if (match(&I, m_c_BinOp(m_OneUse(m_And(m_Value(X), m_One())), m_Value(Y)))) {
455 Value *Tr = Builder.CreateTrunc(X, CmpInst::makeCmpResultType(Ty));
456 return SelectInst::Create(Tr, Y, ConstantInt::getNullValue(Ty));
457 }
458
459 // ((ashr X, 31) | 1) * X --> abs(X)
460 // X * ((ashr X, 31) | 1) --> abs(X)
461 if (match(&I, m_c_BinOp(m_Or(m_AShr(m_Value(X),
462 m_SpecificIntAllowUndef(BitWidth - 1)),
463 m_One()),
464 m_Deferred(X)))) {
465 Value *Abs = Builder.CreateBinaryIntrinsic(
466 Intrinsic::abs, X, ConstantInt::getBool(I.getContext(), HasNSW));
467 Abs->takeName(&I);
468 return replaceInstUsesWith(I, Abs);
469 }
470
471 if (Instruction *Ext = narrowMathIfNoOverflow(I))
472 return Ext;
473
474 bool Changed = false;
475 if (!HasNSW && willNotOverflowSignedMul(Op0, Op1, I)) {
476 Changed = true;
477 I.setHasNoSignedWrap(true);
478 }
479
480 if (!HasNUW && willNotOverflowUnsignedMul(Op0, Op1, I)) {
481 Changed = true;
482 I.setHasNoUnsignedWrap(true);
483 }
484
485 return Changed ? &I : nullptr;
486 }
487
foldFPSignBitOps(BinaryOperator & I)488 Instruction *InstCombinerImpl::foldFPSignBitOps(BinaryOperator &I) {
489 BinaryOperator::BinaryOps Opcode = I.getOpcode();
490 assert((Opcode == Instruction::FMul || Opcode == Instruction::FDiv) &&
491 "Expected fmul or fdiv");
492
493 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
494 Value *X, *Y;
495
496 // -X * -Y --> X * Y
497 // -X / -Y --> X / Y
498 if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y))))
499 return BinaryOperator::CreateWithCopiedFlags(Opcode, X, Y, &I);
500
501 // fabs(X) * fabs(X) -> X * X
502 // fabs(X) / fabs(X) -> X / X
503 if (Op0 == Op1 && match(Op0, m_FAbs(m_Value(X))))
504 return BinaryOperator::CreateWithCopiedFlags(Opcode, X, X, &I);
505
506 // fabs(X) * fabs(Y) --> fabs(X * Y)
507 // fabs(X) / fabs(Y) --> fabs(X / Y)
508 if (match(Op0, m_FAbs(m_Value(X))) && match(Op1, m_FAbs(m_Value(Y))) &&
509 (Op0->hasOneUse() || Op1->hasOneUse())) {
510 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
511 Builder.setFastMathFlags(I.getFastMathFlags());
512 Value *XY = Builder.CreateBinOp(Opcode, X, Y);
513 Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, XY);
514 Fabs->takeName(&I);
515 return replaceInstUsesWith(I, Fabs);
516 }
517
518 return nullptr;
519 }
520
visitFMul(BinaryOperator & I)521 Instruction *InstCombinerImpl::visitFMul(BinaryOperator &I) {
522 if (Value *V = simplifyFMulInst(I.getOperand(0), I.getOperand(1),
523 I.getFastMathFlags(),
524 SQ.getWithInstruction(&I)))
525 return replaceInstUsesWith(I, V);
526
527 if (SimplifyAssociativeOrCommutative(I))
528 return &I;
529
530 if (Instruction *X = foldVectorBinop(I))
531 return X;
532
533 if (Instruction *Phi = foldBinopWithPhiOperands(I))
534 return Phi;
535
536 if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
537 return FoldedMul;
538
539 if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
540 return replaceInstUsesWith(I, FoldedMul);
541
542 if (Instruction *R = foldFPSignBitOps(I))
543 return R;
544
545 // X * -1.0 --> -X
546 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
547 if (match(Op1, m_SpecificFP(-1.0)))
548 return UnaryOperator::CreateFNegFMF(Op0, &I);
549
550 // With no-nans: X * 0.0 --> copysign(0.0, X)
551 if (I.hasNoNaNs() && match(Op1, m_PosZeroFP())) {
552 CallInst *CopySign = Builder.CreateIntrinsic(Intrinsic::copysign,
553 {I.getType()}, {Op1, Op0}, &I);
554 return replaceInstUsesWith(I, CopySign);
555 }
556
557 // -X * C --> X * -C
558 Value *X, *Y;
559 Constant *C;
560 if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_Constant(C)))
561 if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
562 return BinaryOperator::CreateFMulFMF(X, NegC, &I);
563
564 // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E)
565 if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
566 return replaceInstUsesWith(I, V);
567
568 if (I.hasAllowReassoc()) {
569 // Reassociate constant RHS with another constant to form constant
570 // expression.
571 if (match(Op1, m_Constant(C)) && C->isFiniteNonZeroFP()) {
572 Constant *C1;
573 if (match(Op0, m_OneUse(m_FDiv(m_Constant(C1), m_Value(X))))) {
574 // (C1 / X) * C --> (C * C1) / X
575 Constant *CC1 =
576 ConstantFoldBinaryOpOperands(Instruction::FMul, C, C1, DL);
577 if (CC1 && CC1->isNormalFP())
578 return BinaryOperator::CreateFDivFMF(CC1, X, &I);
579 }
580 if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
581 // (X / C1) * C --> X * (C / C1)
582 Constant *CDivC1 =
583 ConstantFoldBinaryOpOperands(Instruction::FDiv, C, C1, DL);
584 if (CDivC1 && CDivC1->isNormalFP())
585 return BinaryOperator::CreateFMulFMF(X, CDivC1, &I);
586
587 // If the constant was a denormal, try reassociating differently.
588 // (X / C1) * C --> X / (C1 / C)
589 Constant *C1DivC =
590 ConstantFoldBinaryOpOperands(Instruction::FDiv, C1, C, DL);
591 if (C1DivC && Op0->hasOneUse() && C1DivC->isNormalFP())
592 return BinaryOperator::CreateFDivFMF(X, C1DivC, &I);
593 }
594
595 // We do not need to match 'fadd C, X' and 'fsub X, C' because they are
596 // canonicalized to 'fadd X, C'. Distributing the multiply may allow
597 // further folds and (X * C) + C2 is 'fma'.
598 if (match(Op0, m_OneUse(m_FAdd(m_Value(X), m_Constant(C1))))) {
599 // (X + C1) * C --> (X * C) + (C * C1)
600 if (Constant *CC1 = ConstantFoldBinaryOpOperands(
601 Instruction::FMul, C, C1, DL)) {
602 Value *XC = Builder.CreateFMulFMF(X, C, &I);
603 return BinaryOperator::CreateFAddFMF(XC, CC1, &I);
604 }
605 }
606 if (match(Op0, m_OneUse(m_FSub(m_Constant(C1), m_Value(X))))) {
607 // (C1 - X) * C --> (C * C1) - (X * C)
608 if (Constant *CC1 = ConstantFoldBinaryOpOperands(
609 Instruction::FMul, C, C1, DL)) {
610 Value *XC = Builder.CreateFMulFMF(X, C, &I);
611 return BinaryOperator::CreateFSubFMF(CC1, XC, &I);
612 }
613 }
614 }
615
616 Value *Z;
617 if (match(&I, m_c_FMul(m_OneUse(m_FDiv(m_Value(X), m_Value(Y))),
618 m_Value(Z)))) {
619 // Sink division: (X / Y) * Z --> (X * Z) / Y
620 Value *NewFMul = Builder.CreateFMulFMF(X, Z, &I);
621 return BinaryOperator::CreateFDivFMF(NewFMul, Y, &I);
622 }
623
624 // sqrt(X) * sqrt(Y) -> sqrt(X * Y)
625 // nnan disallows the possibility of returning a number if both operands are
626 // negative (in that case, we should return NaN).
627 if (I.hasNoNaNs() && match(Op0, m_OneUse(m_Sqrt(m_Value(X)))) &&
628 match(Op1, m_OneUse(m_Sqrt(m_Value(Y))))) {
629 Value *XY = Builder.CreateFMulFMF(X, Y, &I);
630 Value *Sqrt = Builder.CreateUnaryIntrinsic(Intrinsic::sqrt, XY, &I);
631 return replaceInstUsesWith(I, Sqrt);
632 }
633
634 // The following transforms are done irrespective of the number of uses
635 // for the expression "1.0/sqrt(X)".
636 // 1) 1.0/sqrt(X) * X -> X/sqrt(X)
637 // 2) X * 1.0/sqrt(X) -> X/sqrt(X)
638 // We always expect the backend to reduce X/sqrt(X) to sqrt(X), if it
639 // has the necessary (reassoc) fast-math-flags.
640 if (I.hasNoSignedZeros() &&
641 match(Op0, (m_FDiv(m_SpecificFP(1.0), m_Value(Y)))) &&
642 match(Y, m_Sqrt(m_Value(X))) && Op1 == X)
643 return BinaryOperator::CreateFDivFMF(X, Y, &I);
644 if (I.hasNoSignedZeros() &&
645 match(Op1, (m_FDiv(m_SpecificFP(1.0), m_Value(Y)))) &&
646 match(Y, m_Sqrt(m_Value(X))) && Op0 == X)
647 return BinaryOperator::CreateFDivFMF(X, Y, &I);
648
649 // Like the similar transform in instsimplify, this requires 'nsz' because
650 // sqrt(-0.0) = -0.0, and -0.0 * -0.0 does not simplify to -0.0.
651 if (I.hasNoNaNs() && I.hasNoSignedZeros() && Op0 == Op1 &&
652 Op0->hasNUses(2)) {
653 // Peek through fdiv to find squaring of square root:
654 // (X / sqrt(Y)) * (X / sqrt(Y)) --> (X * X) / Y
655 if (match(Op0, m_FDiv(m_Value(X), m_Sqrt(m_Value(Y))))) {
656 Value *XX = Builder.CreateFMulFMF(X, X, &I);
657 return BinaryOperator::CreateFDivFMF(XX, Y, &I);
658 }
659 // (sqrt(Y) / X) * (sqrt(Y) / X) --> Y / (X * X)
660 if (match(Op0, m_FDiv(m_Sqrt(m_Value(Y)), m_Value(X)))) {
661 Value *XX = Builder.CreateFMulFMF(X, X, &I);
662 return BinaryOperator::CreateFDivFMF(Y, XX, &I);
663 }
664 }
665
666 // pow(X, Y) * X --> pow(X, Y+1)
667 // X * pow(X, Y) --> pow(X, Y+1)
668 if (match(&I, m_c_FMul(m_OneUse(m_Intrinsic<Intrinsic::pow>(m_Value(X),
669 m_Value(Y))),
670 m_Deferred(X)))) {
671 Value *Y1 =
672 Builder.CreateFAddFMF(Y, ConstantFP::get(I.getType(), 1.0), &I);
673 Value *Pow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, X, Y1, &I);
674 return replaceInstUsesWith(I, Pow);
675 }
676
677 if (I.isOnlyUserOfAnyOperand()) {
678 // pow(X, Y) * pow(X, Z) -> pow(X, Y + Z)
679 if (match(Op0, m_Intrinsic<Intrinsic::pow>(m_Value(X), m_Value(Y))) &&
680 match(Op1, m_Intrinsic<Intrinsic::pow>(m_Specific(X), m_Value(Z)))) {
681 auto *YZ = Builder.CreateFAddFMF(Y, Z, &I);
682 auto *NewPow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, X, YZ, &I);
683 return replaceInstUsesWith(I, NewPow);
684 }
685 // pow(X, Y) * pow(Z, Y) -> pow(X * Z, Y)
686 if (match(Op0, m_Intrinsic<Intrinsic::pow>(m_Value(X), m_Value(Y))) &&
687 match(Op1, m_Intrinsic<Intrinsic::pow>(m_Value(Z), m_Specific(Y)))) {
688 auto *XZ = Builder.CreateFMulFMF(X, Z, &I);
689 auto *NewPow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, XZ, Y, &I);
690 return replaceInstUsesWith(I, NewPow);
691 }
692
693 // powi(x, y) * powi(x, z) -> powi(x, y + z)
694 if (match(Op0, m_Intrinsic<Intrinsic::powi>(m_Value(X), m_Value(Y))) &&
695 match(Op1, m_Intrinsic<Intrinsic::powi>(m_Specific(X), m_Value(Z))) &&
696 Y->getType() == Z->getType()) {
697 auto *YZ = Builder.CreateAdd(Y, Z);
698 auto *NewPow = Builder.CreateIntrinsic(
699 Intrinsic::powi, {X->getType(), YZ->getType()}, {X, YZ}, &I);
700 return replaceInstUsesWith(I, NewPow);
701 }
702
703 // exp(X) * exp(Y) -> exp(X + Y)
704 if (match(Op0, m_Intrinsic<Intrinsic::exp>(m_Value(X))) &&
705 match(Op1, m_Intrinsic<Intrinsic::exp>(m_Value(Y)))) {
706 Value *XY = Builder.CreateFAddFMF(X, Y, &I);
707 Value *Exp = Builder.CreateUnaryIntrinsic(Intrinsic::exp, XY, &I);
708 return replaceInstUsesWith(I, Exp);
709 }
710
711 // exp2(X) * exp2(Y) -> exp2(X + Y)
712 if (match(Op0, m_Intrinsic<Intrinsic::exp2>(m_Value(X))) &&
713 match(Op1, m_Intrinsic<Intrinsic::exp2>(m_Value(Y)))) {
714 Value *XY = Builder.CreateFAddFMF(X, Y, &I);
715 Value *Exp2 = Builder.CreateUnaryIntrinsic(Intrinsic::exp2, XY, &I);
716 return replaceInstUsesWith(I, Exp2);
717 }
718 }
719
720 // (X*Y) * X => (X*X) * Y where Y != X
721 // The purpose is two-fold:
722 // 1) to form a power expression (of X).
723 // 2) potentially shorten the critical path: After transformation, the
724 // latency of the instruction Y is amortized by the expression of X*X,
725 // and therefore Y is in a "less critical" position compared to what it
726 // was before the transformation.
727 if (match(Op0, m_OneUse(m_c_FMul(m_Specific(Op1), m_Value(Y)))) &&
728 Op1 != Y) {
729 Value *XX = Builder.CreateFMulFMF(Op1, Op1, &I);
730 return BinaryOperator::CreateFMulFMF(XX, Y, &I);
731 }
732 if (match(Op1, m_OneUse(m_c_FMul(m_Specific(Op0), m_Value(Y)))) &&
733 Op0 != Y) {
734 Value *XX = Builder.CreateFMulFMF(Op0, Op0, &I);
735 return BinaryOperator::CreateFMulFMF(XX, Y, &I);
736 }
737 }
738
739 // log2(X * 0.5) * Y = log2(X) * Y - Y
740 if (I.isFast()) {
741 IntrinsicInst *Log2 = nullptr;
742 if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::log2>(
743 m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
744 Log2 = cast<IntrinsicInst>(Op0);
745 Y = Op1;
746 }
747 if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::log2>(
748 m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
749 Log2 = cast<IntrinsicInst>(Op1);
750 Y = Op0;
751 }
752 if (Log2) {
753 Value *Log2 = Builder.CreateUnaryIntrinsic(Intrinsic::log2, X, &I);
754 Value *LogXTimesY = Builder.CreateFMulFMF(Log2, Y, &I);
755 return BinaryOperator::CreateFSubFMF(LogXTimesY, Y, &I);
756 }
757 }
758
759 // Simplify FMUL recurrences starting with 0.0 to 0.0 if nnan and nsz are set.
760 // Given a phi node with entry value as 0 and it used in fmul operation,
761 // we can replace fmul with 0 safely and eleminate loop operation.
762 PHINode *PN = nullptr;
763 Value *Start = nullptr, *Step = nullptr;
764 if (matchSimpleRecurrence(&I, PN, Start, Step) && I.hasNoNaNs() &&
765 I.hasNoSignedZeros() && match(Start, m_Zero()))
766 return replaceInstUsesWith(I, Start);
767
768 return nullptr;
769 }
770
771 /// Fold a divide or remainder with a select instruction divisor when one of the
772 /// select operands is zero. In that case, we can use the other select operand
773 /// because div/rem by zero is undefined.
simplifyDivRemOfSelectWithZeroOp(BinaryOperator & I)774 bool InstCombinerImpl::simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I) {
775 SelectInst *SI = dyn_cast<SelectInst>(I.getOperand(1));
776 if (!SI)
777 return false;
778
779 int NonNullOperand;
780 if (match(SI->getTrueValue(), m_Zero()))
781 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
782 NonNullOperand = 2;
783 else if (match(SI->getFalseValue(), m_Zero()))
784 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
785 NonNullOperand = 1;
786 else
787 return false;
788
789 // Change the div/rem to use 'Y' instead of the select.
790 replaceOperand(I, 1, SI->getOperand(NonNullOperand));
791
792 // Okay, we know we replace the operand of the div/rem with 'Y' with no
793 // problem. However, the select, or the condition of the select may have
794 // multiple uses. Based on our knowledge that the operand must be non-zero,
795 // propagate the known value for the select into other uses of it, and
796 // propagate a known value of the condition into its other users.
797
798 // If the select and condition only have a single use, don't bother with this,
799 // early exit.
800 Value *SelectCond = SI->getCondition();
801 if (SI->use_empty() && SelectCond->hasOneUse())
802 return true;
803
804 // Scan the current block backward, looking for other uses of SI.
805 BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin();
806 Type *CondTy = SelectCond->getType();
807 while (BBI != BBFront) {
808 --BBI;
809 // If we found an instruction that we can't assume will return, so
810 // information from below it cannot be propagated above it.
811 if (!isGuaranteedToTransferExecutionToSuccessor(&*BBI))
812 break;
813
814 // Replace uses of the select or its condition with the known values.
815 for (Use &Op : BBI->operands()) {
816 if (Op == SI) {
817 replaceUse(Op, SI->getOperand(NonNullOperand));
818 Worklist.push(&*BBI);
819 } else if (Op == SelectCond) {
820 replaceUse(Op, NonNullOperand == 1 ? ConstantInt::getTrue(CondTy)
821 : ConstantInt::getFalse(CondTy));
822 Worklist.push(&*BBI);
823 }
824 }
825
826 // If we past the instruction, quit looking for it.
827 if (&*BBI == SI)
828 SI = nullptr;
829 if (&*BBI == SelectCond)
830 SelectCond = nullptr;
831
832 // If we ran out of things to eliminate, break out of the loop.
833 if (!SelectCond && !SI)
834 break;
835
836 }
837 return true;
838 }
839
840 /// True if the multiply can not be expressed in an int this size.
multiplyOverflows(const APInt & C1,const APInt & C2,APInt & Product,bool IsSigned)841 static bool multiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
842 bool IsSigned) {
843 bool Overflow;
844 Product = IsSigned ? C1.smul_ov(C2, Overflow) : C1.umul_ov(C2, Overflow);
845 return Overflow;
846 }
847
848 /// True if C1 is a multiple of C2. Quotient contains C1/C2.
isMultiple(const APInt & C1,const APInt & C2,APInt & Quotient,bool IsSigned)849 static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
850 bool IsSigned) {
851 assert(C1.getBitWidth() == C2.getBitWidth() && "Constant widths not equal");
852
853 // Bail if we will divide by zero.
854 if (C2.isZero())
855 return false;
856
857 // Bail if we would divide INT_MIN by -1.
858 if (IsSigned && C1.isMinSignedValue() && C2.isAllOnes())
859 return false;
860
861 APInt Remainder(C1.getBitWidth(), /*val=*/0ULL, IsSigned);
862 if (IsSigned)
863 APInt::sdivrem(C1, C2, Quotient, Remainder);
864 else
865 APInt::udivrem(C1, C2, Quotient, Remainder);
866
867 return Remainder.isMinValue();
868 }
869
foldIDivShl(BinaryOperator & I,InstCombiner::BuilderTy & Builder)870 static Instruction *foldIDivShl(BinaryOperator &I,
871 InstCombiner::BuilderTy &Builder) {
872 assert((I.getOpcode() == Instruction::SDiv ||
873 I.getOpcode() == Instruction::UDiv) &&
874 "Expected integer divide");
875
876 bool IsSigned = I.getOpcode() == Instruction::SDiv;
877 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
878 Type *Ty = I.getType();
879
880 Instruction *Ret = nullptr;
881 Value *X, *Y, *Z;
882
883 // With appropriate no-wrap constraints, remove a common factor in the
884 // dividend and divisor that is disguised as a left-shifted value.
885 if (match(Op1, m_Shl(m_Value(X), m_Value(Z))) &&
886 match(Op0, m_c_Mul(m_Specific(X), m_Value(Y)))) {
887 // Both operands must have the matching no-wrap for this kind of division.
888 auto *Mul = cast<OverflowingBinaryOperator>(Op0);
889 auto *Shl = cast<OverflowingBinaryOperator>(Op1);
890 bool HasNUW = Mul->hasNoUnsignedWrap() && Shl->hasNoUnsignedWrap();
891 bool HasNSW = Mul->hasNoSignedWrap() && Shl->hasNoSignedWrap();
892
893 // (X * Y) u/ (X << Z) --> Y u>> Z
894 if (!IsSigned && HasNUW)
895 Ret = BinaryOperator::CreateLShr(Y, Z);
896
897 // (X * Y) s/ (X << Z) --> Y s/ (1 << Z)
898 if (IsSigned && HasNSW && (Op0->hasOneUse() || Op1->hasOneUse())) {
899 Value *Shl = Builder.CreateShl(ConstantInt::get(Ty, 1), Z);
900 Ret = BinaryOperator::CreateSDiv(Y, Shl);
901 }
902 }
903
904 // With appropriate no-wrap constraints, remove a common factor in the
905 // dividend and divisor that is disguised as a left-shift amount.
906 if (match(Op0, m_Shl(m_Value(X), m_Value(Z))) &&
907 match(Op1, m_Shl(m_Value(Y), m_Specific(Z)))) {
908 auto *Shl0 = cast<OverflowingBinaryOperator>(Op0);
909 auto *Shl1 = cast<OverflowingBinaryOperator>(Op1);
910
911 // For unsigned div, we need 'nuw' on both shifts or
912 // 'nsw' on both shifts + 'nuw' on the dividend.
913 // (X << Z) / (Y << Z) --> X / Y
914 if (!IsSigned &&
915 ((Shl0->hasNoUnsignedWrap() && Shl1->hasNoUnsignedWrap()) ||
916 (Shl0->hasNoUnsignedWrap() && Shl0->hasNoSignedWrap() &&
917 Shl1->hasNoSignedWrap())))
918 Ret = BinaryOperator::CreateUDiv(X, Y);
919
920 // For signed div, we need 'nsw' on both shifts + 'nuw' on the divisor.
921 // (X << Z) / (Y << Z) --> X / Y
922 if (IsSigned && Shl0->hasNoSignedWrap() && Shl1->hasNoSignedWrap() &&
923 Shl1->hasNoUnsignedWrap())
924 Ret = BinaryOperator::CreateSDiv(X, Y);
925 }
926
927 if (!Ret)
928 return nullptr;
929
930 Ret->setIsExact(I.isExact());
931 return Ret;
932 }
933
934 /// This function implements the transforms common to both integer division
935 /// instructions (udiv and sdiv). It is called by the visitors to those integer
936 /// division instructions.
937 /// Common integer divide transforms
commonIDivTransforms(BinaryOperator & I)938 Instruction *InstCombinerImpl::commonIDivTransforms(BinaryOperator &I) {
939 if (Instruction *Phi = foldBinopWithPhiOperands(I))
940 return Phi;
941
942 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
943 bool IsSigned = I.getOpcode() == Instruction::SDiv;
944 Type *Ty = I.getType();
945
946 // The RHS is known non-zero.
947 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I))
948 return replaceOperand(I, 1, V);
949
950 // Handle cases involving: [su]div X, (select Cond, Y, Z)
951 // This does not apply for fdiv.
952 if (simplifyDivRemOfSelectWithZeroOp(I))
953 return &I;
954
955 // If the divisor is a select-of-constants, try to constant fold all div ops:
956 // C / (select Cond, TrueC, FalseC) --> select Cond, (C / TrueC), (C / FalseC)
957 // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
958 if (match(Op0, m_ImmConstant()) &&
959 match(Op1, m_Select(m_Value(), m_ImmConstant(), m_ImmConstant()))) {
960 if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1),
961 /*FoldWithMultiUse*/ true))
962 return R;
963 }
964
965 const APInt *C2;
966 if (match(Op1, m_APInt(C2))) {
967 Value *X;
968 const APInt *C1;
969
970 // (X / C1) / C2 -> X / (C1*C2)
971 if ((IsSigned && match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))) ||
972 (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_APInt(C1))))) {
973 APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
974 if (!multiplyOverflows(*C1, *C2, Product, IsSigned))
975 return BinaryOperator::Create(I.getOpcode(), X,
976 ConstantInt::get(Ty, Product));
977 }
978
979 if ((IsSigned && match(Op0, m_NSWMul(m_Value(X), m_APInt(C1)))) ||
980 (!IsSigned && match(Op0, m_NUWMul(m_Value(X), m_APInt(C1))))) {
981 APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
982
983 // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
984 if (isMultiple(*C2, *C1, Quotient, IsSigned)) {
985 auto *NewDiv = BinaryOperator::Create(I.getOpcode(), X,
986 ConstantInt::get(Ty, Quotient));
987 NewDiv->setIsExact(I.isExact());
988 return NewDiv;
989 }
990
991 // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
992 if (isMultiple(*C1, *C2, Quotient, IsSigned)) {
993 auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
994 ConstantInt::get(Ty, Quotient));
995 auto *OBO = cast<OverflowingBinaryOperator>(Op0);
996 Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
997 Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
998 return Mul;
999 }
1000 }
1001
1002 if ((IsSigned && match(Op0, m_NSWShl(m_Value(X), m_APInt(C1))) &&
1003 C1->ult(C1->getBitWidth() - 1)) ||
1004 (!IsSigned && match(Op0, m_NUWShl(m_Value(X), m_APInt(C1))) &&
1005 C1->ult(C1->getBitWidth()))) {
1006 APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
1007 APInt C1Shifted = APInt::getOneBitSet(
1008 C1->getBitWidth(), static_cast<unsigned>(C1->getZExtValue()));
1009
1010 // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of 1 << C1.
1011 if (isMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
1012 auto *BO = BinaryOperator::Create(I.getOpcode(), X,
1013 ConstantInt::get(Ty, Quotient));
1014 BO->setIsExact(I.isExact());
1015 return BO;
1016 }
1017
1018 // (X << C1) / C2 -> X * ((1 << C1) / C2) if 1 << C1 is a multiple of C2.
1019 if (isMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
1020 auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
1021 ConstantInt::get(Ty, Quotient));
1022 auto *OBO = cast<OverflowingBinaryOperator>(Op0);
1023 Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
1024 Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
1025 return Mul;
1026 }
1027 }
1028
1029 if (!C2->isZero()) // avoid X udiv 0
1030 if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I))
1031 return FoldedDiv;
1032 }
1033
1034 if (match(Op0, m_One())) {
1035 assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?");
1036 if (IsSigned) {
1037 // 1 / 0 --> undef ; 1 / 1 --> 1 ; 1 / -1 --> -1 ; 1 / anything else --> 0
1038 // (Op1 + 1) u< 3 ? Op1 : 0
1039 // Op1 must be frozen because we are increasing its number of uses.
1040 Value *F1 = Builder.CreateFreeze(Op1, Op1->getName() + ".fr");
1041 Value *Inc = Builder.CreateAdd(F1, Op0);
1042 Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(Ty, 3));
1043 return SelectInst::Create(Cmp, F1, ConstantInt::get(Ty, 0));
1044 } else {
1045 // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
1046 // result is one, otherwise it's zero.
1047 return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), Ty);
1048 }
1049 }
1050
1051 // See if we can fold away this div instruction.
1052 if (SimplifyDemandedInstructionBits(I))
1053 return &I;
1054
1055 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
1056 Value *X, *Z;
1057 if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) // (X - Z) / Y; Y = Op1
1058 if ((IsSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
1059 (!IsSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
1060 return BinaryOperator::Create(I.getOpcode(), X, Op1);
1061
1062 // (X << Y) / X -> 1 << Y
1063 Value *Y;
1064 if (IsSigned && match(Op0, m_NSWShl(m_Specific(Op1), m_Value(Y))))
1065 return BinaryOperator::CreateNSWShl(ConstantInt::get(Ty, 1), Y);
1066 if (!IsSigned && match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y))))
1067 return BinaryOperator::CreateNUWShl(ConstantInt::get(Ty, 1), Y);
1068
1069 // X / (X * Y) -> 1 / Y if the multiplication does not overflow.
1070 if (match(Op1, m_c_Mul(m_Specific(Op0), m_Value(Y)))) {
1071 bool HasNSW = cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap();
1072 bool HasNUW = cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap();
1073 if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) {
1074 replaceOperand(I, 0, ConstantInt::get(Ty, 1));
1075 replaceOperand(I, 1, Y);
1076 return &I;
1077 }
1078 }
1079
1080 // (X << Z) / (X * Y) -> (1 << Z) / Y
1081 // TODO: Handle sdiv.
1082 if (!IsSigned && Op1->hasOneUse() &&
1083 match(Op0, m_NUWShl(m_Value(X), m_Value(Z))) &&
1084 match(Op1, m_c_Mul(m_Specific(X), m_Value(Y))))
1085 if (cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap()) {
1086 Instruction *NewDiv = BinaryOperator::CreateUDiv(
1087 Builder.CreateShl(ConstantInt::get(Ty, 1), Z, "", /*NUW*/ true), Y);
1088 NewDiv->setIsExact(I.isExact());
1089 return NewDiv;
1090 }
1091
1092 if (Instruction *R = foldIDivShl(I, Builder))
1093 return R;
1094
1095 // With the appropriate no-wrap constraint, remove a multiply by the divisor
1096 // after peeking through another divide:
1097 // ((Op1 * X) / Y) / Op1 --> X / Y
1098 if (match(Op0, m_BinOp(I.getOpcode(), m_c_Mul(m_Specific(Op1), m_Value(X)),
1099 m_Value(Y)))) {
1100 auto *InnerDiv = cast<PossiblyExactOperator>(Op0);
1101 auto *Mul = cast<OverflowingBinaryOperator>(InnerDiv->getOperand(0));
1102 Instruction *NewDiv = nullptr;
1103 if (!IsSigned && Mul->hasNoUnsignedWrap())
1104 NewDiv = BinaryOperator::CreateUDiv(X, Y);
1105 else if (IsSigned && Mul->hasNoSignedWrap())
1106 NewDiv = BinaryOperator::CreateSDiv(X, Y);
1107
1108 // Exact propagates only if both of the original divides are exact.
1109 if (NewDiv) {
1110 NewDiv->setIsExact(I.isExact() && InnerDiv->isExact());
1111 return NewDiv;
1112 }
1113 }
1114
1115 return nullptr;
1116 }
1117
1118 static const unsigned MaxDepth = 6;
1119
1120 // Take the exact integer log2 of the value. If DoFold is true, create the
1121 // actual instructions, otherwise return a non-null dummy value. Return nullptr
1122 // on failure.
takeLog2(IRBuilderBase & Builder,Value * Op,unsigned Depth,bool AssumeNonZero,bool DoFold)1123 static Value *takeLog2(IRBuilderBase &Builder, Value *Op, unsigned Depth,
1124 bool AssumeNonZero, bool DoFold) {
1125 auto IfFold = [DoFold](function_ref<Value *()> Fn) {
1126 if (!DoFold)
1127 return reinterpret_cast<Value *>(-1);
1128 return Fn();
1129 };
1130
1131 // FIXME: assert that Op1 isn't/doesn't contain undef.
1132
1133 // log2(2^C) -> C
1134 if (match(Op, m_Power2()))
1135 return IfFold([&]() {
1136 Constant *C = ConstantExpr::getExactLogBase2(cast<Constant>(Op));
1137 if (!C)
1138 llvm_unreachable("Failed to constant fold udiv -> logbase2");
1139 return C;
1140 });
1141
1142 // The remaining tests are all recursive, so bail out if we hit the limit.
1143 if (Depth++ == MaxDepth)
1144 return nullptr;
1145
1146 // log2(zext X) -> zext log2(X)
1147 // FIXME: Require one use?
1148 Value *X, *Y;
1149 if (match(Op, m_ZExt(m_Value(X))))
1150 if (Value *LogX = takeLog2(Builder, X, Depth, AssumeNonZero, DoFold))
1151 return IfFold([&]() { return Builder.CreateZExt(LogX, Op->getType()); });
1152
1153 // log2(X << Y) -> log2(X) + Y
1154 // FIXME: Require one use unless X is 1?
1155 if (match(Op, m_Shl(m_Value(X), m_Value(Y)))) {
1156 auto *BO = cast<OverflowingBinaryOperator>(Op);
1157 // nuw will be set if the `shl` is trivially non-zero.
1158 if (AssumeNonZero || BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap())
1159 if (Value *LogX = takeLog2(Builder, X, Depth, AssumeNonZero, DoFold))
1160 return IfFold([&]() { return Builder.CreateAdd(LogX, Y); });
1161 }
1162
1163 // log2(Cond ? X : Y) -> Cond ? log2(X) : log2(Y)
1164 // FIXME: missed optimization: if one of the hands of select is/contains
1165 // undef, just directly pick the other one.
1166 // FIXME: can both hands contain undef?
1167 // FIXME: Require one use?
1168 if (SelectInst *SI = dyn_cast<SelectInst>(Op))
1169 if (Value *LogX = takeLog2(Builder, SI->getOperand(1), Depth,
1170 AssumeNonZero, DoFold))
1171 if (Value *LogY = takeLog2(Builder, SI->getOperand(2), Depth,
1172 AssumeNonZero, DoFold))
1173 return IfFold([&]() {
1174 return Builder.CreateSelect(SI->getOperand(0), LogX, LogY);
1175 });
1176
1177 // log2(umin(X, Y)) -> umin(log2(X), log2(Y))
1178 // log2(umax(X, Y)) -> umax(log2(X), log2(Y))
1179 auto *MinMax = dyn_cast<MinMaxIntrinsic>(Op);
1180 if (MinMax && MinMax->hasOneUse() && !MinMax->isSigned()) {
1181 // Use AssumeNonZero as false here. Otherwise we can hit case where
1182 // log2(umax(X, Y)) != umax(log2(X), log2(Y)) (because overflow).
1183 if (Value *LogX = takeLog2(Builder, MinMax->getLHS(), Depth,
1184 /*AssumeNonZero*/ false, DoFold))
1185 if (Value *LogY = takeLog2(Builder, MinMax->getRHS(), Depth,
1186 /*AssumeNonZero*/ false, DoFold))
1187 return IfFold([&]() {
1188 return Builder.CreateBinaryIntrinsic(MinMax->getIntrinsicID(), LogX,
1189 LogY);
1190 });
1191 }
1192
1193 return nullptr;
1194 }
1195
1196 /// If we have zero-extended operands of an unsigned div or rem, we may be able
1197 /// to narrow the operation (sink the zext below the math).
narrowUDivURem(BinaryOperator & I,InstCombiner::BuilderTy & Builder)1198 static Instruction *narrowUDivURem(BinaryOperator &I,
1199 InstCombiner::BuilderTy &Builder) {
1200 Instruction::BinaryOps Opcode = I.getOpcode();
1201 Value *N = I.getOperand(0);
1202 Value *D = I.getOperand(1);
1203 Type *Ty = I.getType();
1204 Value *X, *Y;
1205 if (match(N, m_ZExt(m_Value(X))) && match(D, m_ZExt(m_Value(Y))) &&
1206 X->getType() == Y->getType() && (N->hasOneUse() || D->hasOneUse())) {
1207 // udiv (zext X), (zext Y) --> zext (udiv X, Y)
1208 // urem (zext X), (zext Y) --> zext (urem X, Y)
1209 Value *NarrowOp = Builder.CreateBinOp(Opcode, X, Y);
1210 return new ZExtInst(NarrowOp, Ty);
1211 }
1212
1213 Constant *C;
1214 if (isa<Instruction>(N) && match(N, m_OneUse(m_ZExt(m_Value(X)))) &&
1215 match(D, m_Constant(C))) {
1216 // If the constant is the same in the smaller type, use the narrow version.
1217 Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
1218 if (ConstantExpr::getZExt(TruncC, Ty) != C)
1219 return nullptr;
1220
1221 // udiv (zext X), C --> zext (udiv X, C')
1222 // urem (zext X), C --> zext (urem X, C')
1223 return new ZExtInst(Builder.CreateBinOp(Opcode, X, TruncC), Ty);
1224 }
1225 if (isa<Instruction>(D) && match(D, m_OneUse(m_ZExt(m_Value(X)))) &&
1226 match(N, m_Constant(C))) {
1227 // If the constant is the same in the smaller type, use the narrow version.
1228 Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
1229 if (ConstantExpr::getZExt(TruncC, Ty) != C)
1230 return nullptr;
1231
1232 // udiv C, (zext X) --> zext (udiv C', X)
1233 // urem C, (zext X) --> zext (urem C', X)
1234 return new ZExtInst(Builder.CreateBinOp(Opcode, TruncC, X), Ty);
1235 }
1236
1237 return nullptr;
1238 }
1239
visitUDiv(BinaryOperator & I)1240 Instruction *InstCombinerImpl::visitUDiv(BinaryOperator &I) {
1241 if (Value *V = simplifyUDivInst(I.getOperand(0), I.getOperand(1), I.isExact(),
1242 SQ.getWithInstruction(&I)))
1243 return replaceInstUsesWith(I, V);
1244
1245 if (Instruction *X = foldVectorBinop(I))
1246 return X;
1247
1248 // Handle the integer div common cases
1249 if (Instruction *Common = commonIDivTransforms(I))
1250 return Common;
1251
1252 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1253 Value *X;
1254 const APInt *C1, *C2;
1255 if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && match(Op1, m_APInt(C2))) {
1256 // (X lshr C1) udiv C2 --> X udiv (C2 << C1)
1257 bool Overflow;
1258 APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
1259 if (!Overflow) {
1260 bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value()));
1261 BinaryOperator *BO = BinaryOperator::CreateUDiv(
1262 X, ConstantInt::get(X->getType(), C2ShlC1));
1263 if (IsExact)
1264 BO->setIsExact();
1265 return BO;
1266 }
1267 }
1268
1269 // Op0 / C where C is large (negative) --> zext (Op0 >= C)
1270 // TODO: Could use isKnownNegative() to handle non-constant values.
1271 Type *Ty = I.getType();
1272 if (match(Op1, m_Negative())) {
1273 Value *Cmp = Builder.CreateICmpUGE(Op0, Op1);
1274 return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1275 }
1276 // Op0 / (sext i1 X) --> zext (Op0 == -1) (if X is 0, the div is undefined)
1277 if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1278 Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1279 return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1280 }
1281
1282 if (Instruction *NarrowDiv = narrowUDivURem(I, Builder))
1283 return NarrowDiv;
1284
1285 // If the udiv operands are non-overflowing multiplies with a common operand,
1286 // then eliminate the common factor:
1287 // (A * B) / (A * X) --> B / X (and commuted variants)
1288 // TODO: The code would be reduced if we had m_c_NUWMul pattern matching.
1289 // TODO: If -reassociation handled this generally, we could remove this.
1290 Value *A, *B;
1291 if (match(Op0, m_NUWMul(m_Value(A), m_Value(B)))) {
1292 if (match(Op1, m_NUWMul(m_Specific(A), m_Value(X))) ||
1293 match(Op1, m_NUWMul(m_Value(X), m_Specific(A))))
1294 return BinaryOperator::CreateUDiv(B, X);
1295 if (match(Op1, m_NUWMul(m_Specific(B), m_Value(X))) ||
1296 match(Op1, m_NUWMul(m_Value(X), m_Specific(B))))
1297 return BinaryOperator::CreateUDiv(A, X);
1298 }
1299
1300 // Look through a right-shift to find the common factor:
1301 // ((Op1 *nuw A) >> B) / Op1 --> A >> B
1302 if (match(Op0, m_LShr(m_NUWMul(m_Specific(Op1), m_Value(A)), m_Value(B))) ||
1303 match(Op0, m_LShr(m_NUWMul(m_Value(A), m_Specific(Op1)), m_Value(B)))) {
1304 Instruction *Lshr = BinaryOperator::CreateLShr(A, B);
1305 if (I.isExact() && cast<PossiblyExactOperator>(Op0)->isExact())
1306 Lshr->setIsExact();
1307 return Lshr;
1308 }
1309
1310 // Op1 udiv Op2 -> Op1 lshr log2(Op2), if log2() folds away.
1311 if (takeLog2(Builder, Op1, /*Depth*/ 0, /*AssumeNonZero*/ true,
1312 /*DoFold*/ false)) {
1313 Value *Res = takeLog2(Builder, Op1, /*Depth*/ 0,
1314 /*AssumeNonZero*/ true, /*DoFold*/ true);
1315 return replaceInstUsesWith(
1316 I, Builder.CreateLShr(Op0, Res, I.getName(), I.isExact()));
1317 }
1318
1319 return nullptr;
1320 }
1321
visitSDiv(BinaryOperator & I)1322 Instruction *InstCombinerImpl::visitSDiv(BinaryOperator &I) {
1323 if (Value *V = simplifySDivInst(I.getOperand(0), I.getOperand(1), I.isExact(),
1324 SQ.getWithInstruction(&I)))
1325 return replaceInstUsesWith(I, V);
1326
1327 if (Instruction *X = foldVectorBinop(I))
1328 return X;
1329
1330 // Handle the integer div common cases
1331 if (Instruction *Common = commonIDivTransforms(I))
1332 return Common;
1333
1334 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1335 Type *Ty = I.getType();
1336 Value *X;
1337 // sdiv Op0, -1 --> -Op0
1338 // sdiv Op0, (sext i1 X) --> -Op0 (because if X is 0, the op is undefined)
1339 if (match(Op1, m_AllOnes()) ||
1340 (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1341 return BinaryOperator::CreateNeg(Op0);
1342
1343 // X / INT_MIN --> X == INT_MIN
1344 if (match(Op1, m_SignMask()))
1345 return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), Ty);
1346
1347 if (I.isExact()) {
1348 // sdiv exact X, 1<<C --> ashr exact X, C iff 1<<C is non-negative
1349 if (match(Op1, m_Power2()) && match(Op1, m_NonNegative())) {
1350 Constant *C = ConstantExpr::getExactLogBase2(cast<Constant>(Op1));
1351 return BinaryOperator::CreateExactAShr(Op0, C);
1352 }
1353
1354 // sdiv exact X, (1<<ShAmt) --> ashr exact X, ShAmt (if shl is non-negative)
1355 Value *ShAmt;
1356 if (match(Op1, m_NSWShl(m_One(), m_Value(ShAmt))))
1357 return BinaryOperator::CreateExactAShr(Op0, ShAmt);
1358
1359 // sdiv exact X, -1<<C --> -(ashr exact X, C)
1360 if (match(Op1, m_NegatedPower2())) {
1361 Constant *NegPow2C = ConstantExpr::getNeg(cast<Constant>(Op1));
1362 Constant *C = ConstantExpr::getExactLogBase2(NegPow2C);
1363 Value *Ashr = Builder.CreateAShr(Op0, C, I.getName() + ".neg", true);
1364 return BinaryOperator::CreateNeg(Ashr);
1365 }
1366 }
1367
1368 const APInt *Op1C;
1369 if (match(Op1, m_APInt(Op1C))) {
1370 // If the dividend is sign-extended and the constant divisor is small enough
1371 // to fit in the source type, shrink the division to the narrower type:
1372 // (sext X) sdiv C --> sext (X sdiv C)
1373 Value *Op0Src;
1374 if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
1375 Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) {
1376
1377 // In the general case, we need to make sure that the dividend is not the
1378 // minimum signed value because dividing that by -1 is UB. But here, we
1379 // know that the -1 divisor case is already handled above.
1380
1381 Constant *NarrowDivisor =
1382 ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
1383 Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
1384 return new SExtInst(NarrowOp, Ty);
1385 }
1386
1387 // -X / C --> X / -C (if the negation doesn't overflow).
1388 // TODO: This could be enhanced to handle arbitrary vector constants by
1389 // checking if all elements are not the min-signed-val.
1390 if (!Op1C->isMinSignedValue() &&
1391 match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1392 Constant *NegC = ConstantInt::get(Ty, -(*Op1C));
1393 Instruction *BO = BinaryOperator::CreateSDiv(X, NegC);
1394 BO->setIsExact(I.isExact());
1395 return BO;
1396 }
1397 }
1398
1399 // -X / Y --> -(X / Y)
1400 Value *Y;
1401 if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1402 return BinaryOperator::CreateNSWNeg(
1403 Builder.CreateSDiv(X, Y, I.getName(), I.isExact()));
1404
1405 // abs(X) / X --> X > -1 ? 1 : -1
1406 // X / abs(X) --> X > -1 ? 1 : -1
1407 if (match(&I, m_c_BinOp(
1408 m_OneUse(m_Intrinsic<Intrinsic::abs>(m_Value(X), m_One())),
1409 m_Deferred(X)))) {
1410 Value *Cond = Builder.CreateIsNotNeg(X);
1411 return SelectInst::Create(Cond, ConstantInt::get(Ty, 1),
1412 ConstantInt::getAllOnesValue(Ty));
1413 }
1414
1415 KnownBits KnownDividend = computeKnownBits(Op0, 0, &I);
1416 if (!I.isExact() &&
1417 (match(Op1, m_Power2(Op1C)) || match(Op1, m_NegatedPower2(Op1C))) &&
1418 KnownDividend.countMinTrailingZeros() >= Op1C->countTrailingZeros()) {
1419 I.setIsExact();
1420 return &I;
1421 }
1422
1423 if (KnownDividend.isNonNegative()) {
1424 // If both operands are unsigned, turn this into a udiv.
1425 if (isKnownNonNegative(Op1, DL, 0, &AC, &I, &DT)) {
1426 auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1427 BO->setIsExact(I.isExact());
1428 return BO;
1429 }
1430
1431 if (match(Op1, m_NegatedPower2())) {
1432 // X sdiv (-(1 << C)) -> -(X sdiv (1 << C)) ->
1433 // -> -(X udiv (1 << C)) -> -(X u>> C)
1434 Constant *CNegLog2 = ConstantExpr::getExactLogBase2(
1435 ConstantExpr::getNeg(cast<Constant>(Op1)));
1436 Value *Shr = Builder.CreateLShr(Op0, CNegLog2, I.getName(), I.isExact());
1437 return BinaryOperator::CreateNeg(Shr);
1438 }
1439
1440 if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1441 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1442 // Safe because the only negative value (1 << Y) can take on is
1443 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1444 // the sign bit set.
1445 auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1446 BO->setIsExact(I.isExact());
1447 return BO;
1448 }
1449 }
1450
1451 return nullptr;
1452 }
1453
1454 /// Remove negation and try to convert division into multiplication.
foldFDivConstantDivisor(BinaryOperator & I)1455 Instruction *InstCombinerImpl::foldFDivConstantDivisor(BinaryOperator &I) {
1456 Constant *C;
1457 if (!match(I.getOperand(1), m_Constant(C)))
1458 return nullptr;
1459
1460 // -X / C --> X / -C
1461 Value *X;
1462 const DataLayout &DL = I.getModule()->getDataLayout();
1463 if (match(I.getOperand(0), m_FNeg(m_Value(X))))
1464 if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
1465 return BinaryOperator::CreateFDivFMF(X, NegC, &I);
1466
1467 // nnan X / +0.0 -> copysign(inf, X)
1468 if (I.hasNoNaNs() && match(I.getOperand(1), m_Zero())) {
1469 IRBuilder<> B(&I);
1470 // TODO: nnan nsz X / -0.0 -> copysign(inf, X)
1471 CallInst *CopySign = B.CreateIntrinsic(
1472 Intrinsic::copysign, {C->getType()},
1473 {ConstantFP::getInfinity(I.getType()), I.getOperand(0)}, &I);
1474 CopySign->takeName(&I);
1475 return replaceInstUsesWith(I, CopySign);
1476 }
1477
1478 // If the constant divisor has an exact inverse, this is always safe. If not,
1479 // then we can still create a reciprocal if fast-math-flags allow it and the
1480 // constant is a regular number (not zero, infinite, or denormal).
1481 if (!(C->hasExactInverseFP() || (I.hasAllowReciprocal() && C->isNormalFP())))
1482 return nullptr;
1483
1484 // Disallow denormal constants because we don't know what would happen
1485 // on all targets.
1486 // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1487 // denorms are flushed?
1488 auto *RecipC = ConstantFoldBinaryOpOperands(
1489 Instruction::FDiv, ConstantFP::get(I.getType(), 1.0), C, DL);
1490 if (!RecipC || !RecipC->isNormalFP())
1491 return nullptr;
1492
1493 // X / C --> X * (1 / C)
1494 return BinaryOperator::CreateFMulFMF(I.getOperand(0), RecipC, &I);
1495 }
1496
1497 /// Remove negation and try to reassociate constant math.
foldFDivConstantDividend(BinaryOperator & I)1498 static Instruction *foldFDivConstantDividend(BinaryOperator &I) {
1499 Constant *C;
1500 if (!match(I.getOperand(0), m_Constant(C)))
1501 return nullptr;
1502
1503 // C / -X --> -C / X
1504 Value *X;
1505 const DataLayout &DL = I.getModule()->getDataLayout();
1506 if (match(I.getOperand(1), m_FNeg(m_Value(X))))
1507 if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
1508 return BinaryOperator::CreateFDivFMF(NegC, X, &I);
1509
1510 if (!I.hasAllowReassoc() || !I.hasAllowReciprocal())
1511 return nullptr;
1512
1513 // Try to reassociate C / X expressions where X includes another constant.
1514 Constant *C2, *NewC = nullptr;
1515 if (match(I.getOperand(1), m_FMul(m_Value(X), m_Constant(C2)))) {
1516 // C / (X * C2) --> (C / C2) / X
1517 NewC = ConstantFoldBinaryOpOperands(Instruction::FDiv, C, C2, DL);
1518 } else if (match(I.getOperand(1), m_FDiv(m_Value(X), m_Constant(C2)))) {
1519 // C / (X / C2) --> (C * C2) / X
1520 NewC = ConstantFoldBinaryOpOperands(Instruction::FMul, C, C2, DL);
1521 }
1522 // Disallow denormal constants because we don't know what would happen
1523 // on all targets.
1524 // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1525 // denorms are flushed?
1526 if (!NewC || !NewC->isNormalFP())
1527 return nullptr;
1528
1529 return BinaryOperator::CreateFDivFMF(NewC, X, &I);
1530 }
1531
1532 /// Negate the exponent of pow/exp to fold division-by-pow() into multiply.
foldFDivPowDivisor(BinaryOperator & I,InstCombiner::BuilderTy & Builder)1533 static Instruction *foldFDivPowDivisor(BinaryOperator &I,
1534 InstCombiner::BuilderTy &Builder) {
1535 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1536 auto *II = dyn_cast<IntrinsicInst>(Op1);
1537 if (!II || !II->hasOneUse() || !I.hasAllowReassoc() ||
1538 !I.hasAllowReciprocal())
1539 return nullptr;
1540
1541 // Z / pow(X, Y) --> Z * pow(X, -Y)
1542 // Z / exp{2}(Y) --> Z * exp{2}(-Y)
1543 // In the general case, this creates an extra instruction, but fmul allows
1544 // for better canonicalization and optimization than fdiv.
1545 Intrinsic::ID IID = II->getIntrinsicID();
1546 SmallVector<Value *> Args;
1547 switch (IID) {
1548 case Intrinsic::pow:
1549 Args.push_back(II->getArgOperand(0));
1550 Args.push_back(Builder.CreateFNegFMF(II->getArgOperand(1), &I));
1551 break;
1552 case Intrinsic::powi: {
1553 // Require 'ninf' assuming that makes powi(X, -INT_MIN) acceptable.
1554 // That is, X ** (huge negative number) is 0.0, ~1.0, or INF and so
1555 // dividing by that is INF, ~1.0, or 0.0. Code that uses powi allows
1556 // non-standard results, so this corner case should be acceptable if the
1557 // code rules out INF values.
1558 if (!I.hasNoInfs())
1559 return nullptr;
1560 Args.push_back(II->getArgOperand(0));
1561 Args.push_back(Builder.CreateNeg(II->getArgOperand(1)));
1562 Type *Tys[] = {I.getType(), II->getArgOperand(1)->getType()};
1563 Value *Pow = Builder.CreateIntrinsic(IID, Tys, Args, &I);
1564 return BinaryOperator::CreateFMulFMF(Op0, Pow, &I);
1565 }
1566 case Intrinsic::exp:
1567 case Intrinsic::exp2:
1568 Args.push_back(Builder.CreateFNegFMF(II->getArgOperand(0), &I));
1569 break;
1570 default:
1571 return nullptr;
1572 }
1573 Value *Pow = Builder.CreateIntrinsic(IID, I.getType(), Args, &I);
1574 return BinaryOperator::CreateFMulFMF(Op0, Pow, &I);
1575 }
1576
visitFDiv(BinaryOperator & I)1577 Instruction *InstCombinerImpl::visitFDiv(BinaryOperator &I) {
1578 Module *M = I.getModule();
1579
1580 if (Value *V = simplifyFDivInst(I.getOperand(0), I.getOperand(1),
1581 I.getFastMathFlags(),
1582 SQ.getWithInstruction(&I)))
1583 return replaceInstUsesWith(I, V);
1584
1585 if (Instruction *X = foldVectorBinop(I))
1586 return X;
1587
1588 if (Instruction *Phi = foldBinopWithPhiOperands(I))
1589 return Phi;
1590
1591 if (Instruction *R = foldFDivConstantDivisor(I))
1592 return R;
1593
1594 if (Instruction *R = foldFDivConstantDividend(I))
1595 return R;
1596
1597 if (Instruction *R = foldFPSignBitOps(I))
1598 return R;
1599
1600 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1601 if (isa<Constant>(Op0))
1602 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1603 if (Instruction *R = FoldOpIntoSelect(I, SI))
1604 return R;
1605
1606 if (isa<Constant>(Op1))
1607 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1608 if (Instruction *R = FoldOpIntoSelect(I, SI))
1609 return R;
1610
1611 if (I.hasAllowReassoc() && I.hasAllowReciprocal()) {
1612 Value *X, *Y;
1613 if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1614 (!isa<Constant>(Y) || !isa<Constant>(Op1))) {
1615 // (X / Y) / Z => X / (Y * Z)
1616 Value *YZ = Builder.CreateFMulFMF(Y, Op1, &I);
1617 return BinaryOperator::CreateFDivFMF(X, YZ, &I);
1618 }
1619 if (match(Op1, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1620 (!isa<Constant>(Y) || !isa<Constant>(Op0))) {
1621 // Z / (X / Y) => (Y * Z) / X
1622 Value *YZ = Builder.CreateFMulFMF(Y, Op0, &I);
1623 return BinaryOperator::CreateFDivFMF(YZ, X, &I);
1624 }
1625 // Z / (1.0 / Y) => (Y * Z)
1626 //
1627 // This is a special case of Z / (X / Y) => (Y * Z) / X, with X = 1.0. The
1628 // m_OneUse check is avoided because even in the case of the multiple uses
1629 // for 1.0/Y, the number of instructions remain the same and a division is
1630 // replaced by a multiplication.
1631 if (match(Op1, m_FDiv(m_SpecificFP(1.0), m_Value(Y))))
1632 return BinaryOperator::CreateFMulFMF(Y, Op0, &I);
1633 }
1634
1635 if (I.hasAllowReassoc() && Op0->hasOneUse() && Op1->hasOneUse()) {
1636 // sin(X) / cos(X) -> tan(X)
1637 // cos(X) / sin(X) -> 1/tan(X) (cotangent)
1638 Value *X;
1639 bool IsTan = match(Op0, m_Intrinsic<Intrinsic::sin>(m_Value(X))) &&
1640 match(Op1, m_Intrinsic<Intrinsic::cos>(m_Specific(X)));
1641 bool IsCot =
1642 !IsTan && match(Op0, m_Intrinsic<Intrinsic::cos>(m_Value(X))) &&
1643 match(Op1, m_Intrinsic<Intrinsic::sin>(m_Specific(X)));
1644
1645 if ((IsTan || IsCot) && hasFloatFn(M, &TLI, I.getType(), LibFunc_tan,
1646 LibFunc_tanf, LibFunc_tanl)) {
1647 IRBuilder<> B(&I);
1648 IRBuilder<>::FastMathFlagGuard FMFGuard(B);
1649 B.setFastMathFlags(I.getFastMathFlags());
1650 AttributeList Attrs =
1651 cast<CallBase>(Op0)->getCalledFunction()->getAttributes();
1652 Value *Res = emitUnaryFloatFnCall(X, &TLI, LibFunc_tan, LibFunc_tanf,
1653 LibFunc_tanl, B, Attrs);
1654 if (IsCot)
1655 Res = B.CreateFDiv(ConstantFP::get(I.getType(), 1.0), Res);
1656 return replaceInstUsesWith(I, Res);
1657 }
1658 }
1659
1660 // X / (X * Y) --> 1.0 / Y
1661 // Reassociate to (X / X -> 1.0) is legal when NaNs are not allowed.
1662 // We can ignore the possibility that X is infinity because INF/INF is NaN.
1663 Value *X, *Y;
1664 if (I.hasNoNaNs() && I.hasAllowReassoc() &&
1665 match(Op1, m_c_FMul(m_Specific(Op0), m_Value(Y)))) {
1666 replaceOperand(I, 0, ConstantFP::get(I.getType(), 1.0));
1667 replaceOperand(I, 1, Y);
1668 return &I;
1669 }
1670
1671 // X / fabs(X) -> copysign(1.0, X)
1672 // fabs(X) / X -> copysign(1.0, X)
1673 if (I.hasNoNaNs() && I.hasNoInfs() &&
1674 (match(&I, m_FDiv(m_Value(X), m_FAbs(m_Deferred(X)))) ||
1675 match(&I, m_FDiv(m_FAbs(m_Value(X)), m_Deferred(X))))) {
1676 Value *V = Builder.CreateBinaryIntrinsic(
1677 Intrinsic::copysign, ConstantFP::get(I.getType(), 1.0), X, &I);
1678 return replaceInstUsesWith(I, V);
1679 }
1680
1681 if (Instruction *Mul = foldFDivPowDivisor(I, Builder))
1682 return Mul;
1683
1684 // pow(X, Y) / X --> pow(X, Y-1)
1685 if (I.hasAllowReassoc() &&
1686 match(Op0, m_OneUse(m_Intrinsic<Intrinsic::pow>(m_Specific(Op1),
1687 m_Value(Y))))) {
1688 Value *Y1 =
1689 Builder.CreateFAddFMF(Y, ConstantFP::get(I.getType(), -1.0), &I);
1690 Value *Pow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, Op1, Y1, &I);
1691 return replaceInstUsesWith(I, Pow);
1692 }
1693
1694 return nullptr;
1695 }
1696
1697 /// This function implements the transforms common to both integer remainder
1698 /// instructions (urem and srem). It is called by the visitors to those integer
1699 /// remainder instructions.
1700 /// Common integer remainder transforms
commonIRemTransforms(BinaryOperator & I)1701 Instruction *InstCombinerImpl::commonIRemTransforms(BinaryOperator &I) {
1702 if (Instruction *Phi = foldBinopWithPhiOperands(I))
1703 return Phi;
1704
1705 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1706
1707 // The RHS is known non-zero.
1708 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I))
1709 return replaceOperand(I, 1, V);
1710
1711 // Handle cases involving: rem X, (select Cond, Y, Z)
1712 if (simplifyDivRemOfSelectWithZeroOp(I))
1713 return &I;
1714
1715 // If the divisor is a select-of-constants, try to constant fold all rem ops:
1716 // C % (select Cond, TrueC, FalseC) --> select Cond, (C % TrueC), (C % FalseC)
1717 // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
1718 if (match(Op0, m_ImmConstant()) &&
1719 match(Op1, m_Select(m_Value(), m_ImmConstant(), m_ImmConstant()))) {
1720 if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1),
1721 /*FoldWithMultiUse*/ true))
1722 return R;
1723 }
1724
1725 if (isa<Constant>(Op1)) {
1726 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1727 if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1728 if (Instruction *R = FoldOpIntoSelect(I, SI))
1729 return R;
1730 } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
1731 const APInt *Op1Int;
1732 if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
1733 (I.getOpcode() == Instruction::URem ||
1734 !Op1Int->isMinSignedValue())) {
1735 // foldOpIntoPhi will speculate instructions to the end of the PHI's
1736 // predecessor blocks, so do this only if we know the srem or urem
1737 // will not fault.
1738 if (Instruction *NV = foldOpIntoPhi(I, PN))
1739 return NV;
1740 }
1741 }
1742
1743 // See if we can fold away this rem instruction.
1744 if (SimplifyDemandedInstructionBits(I))
1745 return &I;
1746 }
1747 }
1748
1749 return nullptr;
1750 }
1751
visitURem(BinaryOperator & I)1752 Instruction *InstCombinerImpl::visitURem(BinaryOperator &I) {
1753 if (Value *V = simplifyURemInst(I.getOperand(0), I.getOperand(1),
1754 SQ.getWithInstruction(&I)))
1755 return replaceInstUsesWith(I, V);
1756
1757 if (Instruction *X = foldVectorBinop(I))
1758 return X;
1759
1760 if (Instruction *common = commonIRemTransforms(I))
1761 return common;
1762
1763 if (Instruction *NarrowRem = narrowUDivURem(I, Builder))
1764 return NarrowRem;
1765
1766 // X urem Y -> X and Y-1, where Y is a power of 2,
1767 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1768 Type *Ty = I.getType();
1769 if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1770 // This may increase instruction count, we don't enforce that Y is a
1771 // constant.
1772 Constant *N1 = Constant::getAllOnesValue(Ty);
1773 Value *Add = Builder.CreateAdd(Op1, N1);
1774 return BinaryOperator::CreateAnd(Op0, Add);
1775 }
1776
1777 // 1 urem X -> zext(X != 1)
1778 if (match(Op0, m_One())) {
1779 Value *Cmp = Builder.CreateICmpNE(Op1, ConstantInt::get(Ty, 1));
1780 return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1781 }
1782
1783 // Op0 urem C -> Op0 < C ? Op0 : Op0 - C, where C >= signbit.
1784 // Op0 must be frozen because we are increasing its number of uses.
1785 if (match(Op1, m_Negative())) {
1786 Value *F0 = Builder.CreateFreeze(Op0, Op0->getName() + ".fr");
1787 Value *Cmp = Builder.CreateICmpULT(F0, Op1);
1788 Value *Sub = Builder.CreateSub(F0, Op1);
1789 return SelectInst::Create(Cmp, F0, Sub);
1790 }
1791
1792 // If the divisor is a sext of a boolean, then the divisor must be max
1793 // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also
1794 // max unsigned value. In that case, the remainder is 0:
1795 // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0
1796 Value *X;
1797 if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1798 Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1799 return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), Op0);
1800 }
1801
1802 return nullptr;
1803 }
1804
visitSRem(BinaryOperator & I)1805 Instruction *InstCombinerImpl::visitSRem(BinaryOperator &I) {
1806 if (Value *V = simplifySRemInst(I.getOperand(0), I.getOperand(1),
1807 SQ.getWithInstruction(&I)))
1808 return replaceInstUsesWith(I, V);
1809
1810 if (Instruction *X = foldVectorBinop(I))
1811 return X;
1812
1813 // Handle the integer rem common cases
1814 if (Instruction *Common = commonIRemTransforms(I))
1815 return Common;
1816
1817 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1818 {
1819 const APInt *Y;
1820 // X % -Y -> X % Y
1821 if (match(Op1, m_Negative(Y)) && !Y->isMinSignedValue())
1822 return replaceOperand(I, 1, ConstantInt::get(I.getType(), -*Y));
1823 }
1824
1825 // -X srem Y --> -(X srem Y)
1826 Value *X, *Y;
1827 if (match(&I, m_SRem(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1828 return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y));
1829
1830 // If the sign bits of both operands are zero (i.e. we can prove they are
1831 // unsigned inputs), turn this into a urem.
1832 APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
1833 if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1834 MaskedValueIsZero(Op0, Mask, 0, &I)) {
1835 // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1836 return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1837 }
1838
1839 // If it's a constant vector, flip any negative values positive.
1840 if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1841 Constant *C = cast<Constant>(Op1);
1842 unsigned VWidth = cast<FixedVectorType>(C->getType())->getNumElements();
1843
1844 bool hasNegative = false;
1845 bool hasMissing = false;
1846 for (unsigned i = 0; i != VWidth; ++i) {
1847 Constant *Elt = C->getAggregateElement(i);
1848 if (!Elt) {
1849 hasMissing = true;
1850 break;
1851 }
1852
1853 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1854 if (RHS->isNegative())
1855 hasNegative = true;
1856 }
1857
1858 if (hasNegative && !hasMissing) {
1859 SmallVector<Constant *, 16> Elts(VWidth);
1860 for (unsigned i = 0; i != VWidth; ++i) {
1861 Elts[i] = C->getAggregateElement(i); // Handle undef, etc.
1862 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1863 if (RHS->isNegative())
1864 Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1865 }
1866 }
1867
1868 Constant *NewRHSV = ConstantVector::get(Elts);
1869 if (NewRHSV != C) // Don't loop on -MININT
1870 return replaceOperand(I, 1, NewRHSV);
1871 }
1872 }
1873
1874 return nullptr;
1875 }
1876
visitFRem(BinaryOperator & I)1877 Instruction *InstCombinerImpl::visitFRem(BinaryOperator &I) {
1878 if (Value *V = simplifyFRemInst(I.getOperand(0), I.getOperand(1),
1879 I.getFastMathFlags(),
1880 SQ.getWithInstruction(&I)))
1881 return replaceInstUsesWith(I, V);
1882
1883 if (Instruction *X = foldVectorBinop(I))
1884 return X;
1885
1886 if (Instruction *Phi = foldBinopWithPhiOperands(I))
1887 return Phi;
1888
1889 return nullptr;
1890 }
1891