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/APFloat.h"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/Analysis/InstructionSimplify.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/Support/KnownBits.h"
34 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
35 #include "llvm/Transforms/Utils/BuildLibCalls.h"
36 #include <cassert>
37 #include <cstddef>
38 #include <cstdint>
39 #include <utility>
40
41 using namespace llvm;
42 using namespace PatternMatch;
43
44 #define DEBUG_TYPE "instcombine"
45
46 /// The specific integer value is used in a context where it is known to be
47 /// non-zero. If this allows us to simplify the computation, do so and return
48 /// the new operand, otherwise return null.
simplifyValueKnownNonZero(Value * V,InstCombiner & IC,Instruction & CxtI)49 static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC,
50 Instruction &CxtI) {
51 // If V has multiple uses, then we would have to do more analysis to determine
52 // if this is safe. For example, the use could be in dynamically unreached
53 // code.
54 if (!V->hasOneUse()) return nullptr;
55
56 bool MadeChange = false;
57
58 // ((1 << A) >>u B) --> (1 << (A-B))
59 // Because V cannot be zero, we know that B is less than A.
60 Value *A = nullptr, *B = nullptr, *One = nullptr;
61 if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) &&
62 match(One, m_One())) {
63 A = IC.Builder.CreateSub(A, B);
64 return IC.Builder.CreateShl(One, A);
65 }
66
67 // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
68 // inexact. Similarly for <<.
69 BinaryOperator *I = dyn_cast<BinaryOperator>(V);
70 if (I && I->isLogicalShift() &&
71 IC.isKnownToBeAPowerOfTwo(I->getOperand(0), false, 0, &CxtI)) {
72 // We know that this is an exact/nuw shift and that the input is a
73 // non-zero context as well.
74 if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) {
75 I->setOperand(0, V2);
76 MadeChange = true;
77 }
78
79 if (I->getOpcode() == Instruction::LShr && !I->isExact()) {
80 I->setIsExact();
81 MadeChange = true;
82 }
83
84 if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) {
85 I->setHasNoUnsignedWrap();
86 MadeChange = true;
87 }
88 }
89
90 // TODO: Lots more we could do here:
91 // If V is a phi node, we can call this on each of its operands.
92 // "select cond, X, 0" can simplify to "X".
93
94 return MadeChange ? V : nullptr;
95 }
96
97 /// A helper routine of InstCombiner::visitMul().
98 ///
99 /// If C is a scalar/vector of known powers of 2, then this function returns
100 /// a new scalar/vector obtained from logBase2 of C.
101 /// Return a null pointer otherwise.
getLogBase2(Type * Ty,Constant * C)102 static Constant *getLogBase2(Type *Ty, Constant *C) {
103 const APInt *IVal;
104 if (match(C, m_APInt(IVal)) && IVal->isPowerOf2())
105 return ConstantInt::get(Ty, IVal->logBase2());
106
107 if (!Ty->isVectorTy())
108 return nullptr;
109
110 SmallVector<Constant *, 4> Elts;
111 for (unsigned I = 0, E = Ty->getVectorNumElements(); I != E; ++I) {
112 Constant *Elt = C->getAggregateElement(I);
113 if (!Elt)
114 return nullptr;
115 if (isa<UndefValue>(Elt)) {
116 Elts.push_back(UndefValue::get(Ty->getScalarType()));
117 continue;
118 }
119 if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2())
120 return nullptr;
121 Elts.push_back(ConstantInt::get(Ty->getScalarType(), IVal->logBase2()));
122 }
123
124 return ConstantVector::get(Elts);
125 }
126
127 // TODO: This is a specific form of a much more general pattern.
128 // We could detect a select with any binop identity constant, or we
129 // could use SimplifyBinOp to see if either arm of the select reduces.
130 // But that needs to be done carefully and/or while removing potential
131 // reverse canonicalizations as in InstCombiner::foldSelectIntoOp().
foldMulSelectToNegate(BinaryOperator & I,InstCombiner::BuilderTy & Builder)132 static Value *foldMulSelectToNegate(BinaryOperator &I,
133 InstCombiner::BuilderTy &Builder) {
134 Value *Cond, *OtherOp;
135
136 // mul (select Cond, 1, -1), OtherOp --> select Cond, OtherOp, -OtherOp
137 // mul OtherOp, (select Cond, 1, -1) --> select Cond, OtherOp, -OtherOp
138 if (match(&I, m_c_Mul(m_OneUse(m_Select(m_Value(Cond), m_One(), m_AllOnes())),
139 m_Value(OtherOp))))
140 return Builder.CreateSelect(Cond, OtherOp, Builder.CreateNeg(OtherOp));
141
142 // mul (select Cond, -1, 1), OtherOp --> select Cond, -OtherOp, OtherOp
143 // mul OtherOp, (select Cond, -1, 1) --> select Cond, -OtherOp, OtherOp
144 if (match(&I, m_c_Mul(m_OneUse(m_Select(m_Value(Cond), m_AllOnes(), m_One())),
145 m_Value(OtherOp))))
146 return Builder.CreateSelect(Cond, Builder.CreateNeg(OtherOp), OtherOp);
147
148 // fmul (select Cond, 1.0, -1.0), OtherOp --> select Cond, OtherOp, -OtherOp
149 // fmul OtherOp, (select Cond, 1.0, -1.0) --> select Cond, OtherOp, -OtherOp
150 if (match(&I, m_c_FMul(m_OneUse(m_Select(m_Value(Cond), m_SpecificFP(1.0),
151 m_SpecificFP(-1.0))),
152 m_Value(OtherOp)))) {
153 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
154 Builder.setFastMathFlags(I.getFastMathFlags());
155 return Builder.CreateSelect(Cond, OtherOp, Builder.CreateFNeg(OtherOp));
156 }
157
158 // fmul (select Cond, -1.0, 1.0), OtherOp --> select Cond, -OtherOp, OtherOp
159 // fmul OtherOp, (select Cond, -1.0, 1.0) --> select Cond, -OtherOp, OtherOp
160 if (match(&I, m_c_FMul(m_OneUse(m_Select(m_Value(Cond), m_SpecificFP(-1.0),
161 m_SpecificFP(1.0))),
162 m_Value(OtherOp)))) {
163 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
164 Builder.setFastMathFlags(I.getFastMathFlags());
165 return Builder.CreateSelect(Cond, Builder.CreateFNeg(OtherOp), OtherOp);
166 }
167
168 return nullptr;
169 }
170
visitMul(BinaryOperator & I)171 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
172 if (Value *V = SimplifyMulInst(I.getOperand(0), I.getOperand(1),
173 SQ.getWithInstruction(&I)))
174 return replaceInstUsesWith(I, V);
175
176 if (SimplifyAssociativeOrCommutative(I))
177 return &I;
178
179 if (Instruction *X = foldVectorBinop(I))
180 return X;
181
182 if (Value *V = SimplifyUsingDistributiveLaws(I))
183 return replaceInstUsesWith(I, V);
184
185 // X * -1 == 0 - X
186 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
187 if (match(Op1, m_AllOnes())) {
188 BinaryOperator *BO = BinaryOperator::CreateNeg(Op0, I.getName());
189 if (I.hasNoSignedWrap())
190 BO->setHasNoSignedWrap();
191 return BO;
192 }
193
194 // Also allow combining multiply instructions on vectors.
195 {
196 Value *NewOp;
197 Constant *C1, *C2;
198 const APInt *IVal;
199 if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
200 m_Constant(C1))) &&
201 match(C1, m_APInt(IVal))) {
202 // ((X << C2)*C1) == (X * (C1 << C2))
203 Constant *Shl = ConstantExpr::getShl(C1, C2);
204 BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0));
205 BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl);
206 if (I.hasNoUnsignedWrap() && Mul->hasNoUnsignedWrap())
207 BO->setHasNoUnsignedWrap();
208 if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap() &&
209 Shl->isNotMinSignedValue())
210 BO->setHasNoSignedWrap();
211 return BO;
212 }
213
214 if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
215 // Replace X*(2^C) with X << C, where C is either a scalar or a vector.
216 if (Constant *NewCst = getLogBase2(NewOp->getType(), C1)) {
217 BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
218
219 if (I.hasNoUnsignedWrap())
220 Shl->setHasNoUnsignedWrap();
221 if (I.hasNoSignedWrap()) {
222 const APInt *V;
223 if (match(NewCst, m_APInt(V)) && *V != V->getBitWidth() - 1)
224 Shl->setHasNoSignedWrap();
225 }
226
227 return Shl;
228 }
229 }
230 }
231
232 if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
233 // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n
234 // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n
235 // The "* (2**n)" thus becomes a potential shifting opportunity.
236 {
237 const APInt & Val = CI->getValue();
238 const APInt &PosVal = Val.abs();
239 if (Val.isNegative() && PosVal.isPowerOf2()) {
240 Value *X = nullptr, *Y = nullptr;
241 if (Op0->hasOneUse()) {
242 ConstantInt *C1;
243 Value *Sub = nullptr;
244 if (match(Op0, m_Sub(m_Value(Y), m_Value(X))))
245 Sub = Builder.CreateSub(X, Y, "suba");
246 else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1))))
247 Sub = Builder.CreateSub(Builder.CreateNeg(C1), Y, "subc");
248 if (Sub)
249 return
250 BinaryOperator::CreateMul(Sub,
251 ConstantInt::get(Y->getType(), PosVal));
252 }
253 }
254 }
255 }
256
257 if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
258 return FoldedMul;
259
260 if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
261 return replaceInstUsesWith(I, FoldedMul);
262
263 // Simplify mul instructions with a constant RHS.
264 if (isa<Constant>(Op1)) {
265 // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
266 Value *X;
267 Constant *C1;
268 if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) {
269 Value *Mul = Builder.CreateMul(C1, Op1);
270 // Only go forward with the transform if C1*CI simplifies to a tidier
271 // constant.
272 if (!match(Mul, m_Mul(m_Value(), m_Value())))
273 return BinaryOperator::CreateAdd(Builder.CreateMul(X, Op1), Mul);
274 }
275 }
276
277 // -X * C --> X * -C
278 Value *X, *Y;
279 Constant *Op1C;
280 if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Constant(Op1C)))
281 return BinaryOperator::CreateMul(X, ConstantExpr::getNeg(Op1C));
282
283 // -X * -Y --> X * Y
284 if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Neg(m_Value(Y)))) {
285 auto *NewMul = BinaryOperator::CreateMul(X, Y);
286 if (I.hasNoSignedWrap() &&
287 cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap() &&
288 cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap())
289 NewMul->setHasNoSignedWrap();
290 return NewMul;
291 }
292
293 // -X * Y --> -(X * Y)
294 // X * -Y --> -(X * Y)
295 if (match(&I, m_c_Mul(m_OneUse(m_Neg(m_Value(X))), m_Value(Y))))
296 return BinaryOperator::CreateNeg(Builder.CreateMul(X, Y));
297
298 // (X / Y) * Y = X - (X % Y)
299 // (X / Y) * -Y = (X % Y) - X
300 {
301 Value *Y = Op1;
302 BinaryOperator *Div = dyn_cast<BinaryOperator>(Op0);
303 if (!Div || (Div->getOpcode() != Instruction::UDiv &&
304 Div->getOpcode() != Instruction::SDiv)) {
305 Y = Op0;
306 Div = dyn_cast<BinaryOperator>(Op1);
307 }
308 Value *Neg = dyn_castNegVal(Y);
309 if (Div && Div->hasOneUse() &&
310 (Div->getOperand(1) == Y || Div->getOperand(1) == Neg) &&
311 (Div->getOpcode() == Instruction::UDiv ||
312 Div->getOpcode() == Instruction::SDiv)) {
313 Value *X = Div->getOperand(0), *DivOp1 = Div->getOperand(1);
314
315 // If the division is exact, X % Y is zero, so we end up with X or -X.
316 if (Div->isExact()) {
317 if (DivOp1 == Y)
318 return replaceInstUsesWith(I, X);
319 return BinaryOperator::CreateNeg(X);
320 }
321
322 auto RemOpc = Div->getOpcode() == Instruction::UDiv ? Instruction::URem
323 : Instruction::SRem;
324 Value *Rem = Builder.CreateBinOp(RemOpc, X, DivOp1);
325 if (DivOp1 == Y)
326 return BinaryOperator::CreateSub(X, Rem);
327 return BinaryOperator::CreateSub(Rem, X);
328 }
329 }
330
331 /// i1 mul -> i1 and.
332 if (I.getType()->isIntOrIntVectorTy(1))
333 return BinaryOperator::CreateAnd(Op0, Op1);
334
335 // X*(1 << Y) --> X << Y
336 // (1 << Y)*X --> X << Y
337 {
338 Value *Y;
339 BinaryOperator *BO = nullptr;
340 bool ShlNSW = false;
341 if (match(Op0, m_Shl(m_One(), m_Value(Y)))) {
342 BO = BinaryOperator::CreateShl(Op1, Y);
343 ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap();
344 } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) {
345 BO = BinaryOperator::CreateShl(Op0, Y);
346 ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap();
347 }
348 if (BO) {
349 if (I.hasNoUnsignedWrap())
350 BO->setHasNoUnsignedWrap();
351 if (I.hasNoSignedWrap() && ShlNSW)
352 BO->setHasNoSignedWrap();
353 return BO;
354 }
355 }
356
357 // (bool X) * Y --> X ? Y : 0
358 // Y * (bool X) --> X ? Y : 0
359 if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
360 return SelectInst::Create(X, Op1, ConstantInt::get(I.getType(), 0));
361 if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
362 return SelectInst::Create(X, Op0, ConstantInt::get(I.getType(), 0));
363
364 // (lshr X, 31) * Y --> (ashr X, 31) & Y
365 // Y * (lshr X, 31) --> (ashr X, 31) & Y
366 // TODO: We are not checking one-use because the elimination of the multiply
367 // is better for analysis?
368 // TODO: Should we canonicalize to '(X < 0) ? Y : 0' instead? That would be
369 // more similar to what we're doing above.
370 const APInt *C;
371 if (match(Op0, m_LShr(m_Value(X), m_APInt(C))) && *C == C->getBitWidth() - 1)
372 return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op1);
373 if (match(Op1, m_LShr(m_Value(X), m_APInt(C))) && *C == C->getBitWidth() - 1)
374 return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op0);
375
376 if (Instruction *Ext = narrowMathIfNoOverflow(I))
377 return Ext;
378
379 bool Changed = false;
380 if (!I.hasNoSignedWrap() && willNotOverflowSignedMul(Op0, Op1, I)) {
381 Changed = true;
382 I.setHasNoSignedWrap(true);
383 }
384
385 if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedMul(Op0, Op1, I)) {
386 Changed = true;
387 I.setHasNoUnsignedWrap(true);
388 }
389
390 return Changed ? &I : nullptr;
391 }
392
visitFMul(BinaryOperator & I)393 Instruction *InstCombiner::visitFMul(BinaryOperator &I) {
394 if (Value *V = SimplifyFMulInst(I.getOperand(0), I.getOperand(1),
395 I.getFastMathFlags(),
396 SQ.getWithInstruction(&I)))
397 return replaceInstUsesWith(I, V);
398
399 if (SimplifyAssociativeOrCommutative(I))
400 return &I;
401
402 if (Instruction *X = foldVectorBinop(I))
403 return X;
404
405 if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
406 return FoldedMul;
407
408 if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
409 return replaceInstUsesWith(I, FoldedMul);
410
411 // X * -1.0 --> -X
412 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
413 if (match(Op1, m_SpecificFP(-1.0)))
414 return BinaryOperator::CreateFNegFMF(Op0, &I);
415
416 // -X * -Y --> X * Y
417 Value *X, *Y;
418 if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y))))
419 return BinaryOperator::CreateFMulFMF(X, Y, &I);
420
421 // -X * C --> X * -C
422 Constant *C;
423 if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_Constant(C)))
424 return BinaryOperator::CreateFMulFMF(X, ConstantExpr::getFNeg(C), &I);
425
426 // fabs(X) * fabs(X) -> X * X
427 if (Op0 == Op1 && match(Op0, m_Intrinsic<Intrinsic::fabs>(m_Value(X))))
428 return BinaryOperator::CreateFMulFMF(X, X, &I);
429
430 // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E)
431 if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
432 return replaceInstUsesWith(I, V);
433
434 if (I.hasAllowReassoc()) {
435 // Reassociate constant RHS with another constant to form constant
436 // expression.
437 if (match(Op1, m_Constant(C)) && C->isFiniteNonZeroFP()) {
438 Constant *C1;
439 if (match(Op0, m_OneUse(m_FDiv(m_Constant(C1), m_Value(X))))) {
440 // (C1 / X) * C --> (C * C1) / X
441 Constant *CC1 = ConstantExpr::getFMul(C, C1);
442 if (CC1->isNormalFP())
443 return BinaryOperator::CreateFDivFMF(CC1, X, &I);
444 }
445 if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
446 // (X / C1) * C --> X * (C / C1)
447 Constant *CDivC1 = ConstantExpr::getFDiv(C, C1);
448 if (CDivC1->isNormalFP())
449 return BinaryOperator::CreateFMulFMF(X, CDivC1, &I);
450
451 // If the constant was a denormal, try reassociating differently.
452 // (X / C1) * C --> X / (C1 / C)
453 Constant *C1DivC = ConstantExpr::getFDiv(C1, C);
454 if (Op0->hasOneUse() && C1DivC->isNormalFP())
455 return BinaryOperator::CreateFDivFMF(X, C1DivC, &I);
456 }
457
458 // We do not need to match 'fadd C, X' and 'fsub X, C' because they are
459 // canonicalized to 'fadd X, C'. Distributing the multiply may allow
460 // further folds and (X * C) + C2 is 'fma'.
461 if (match(Op0, m_OneUse(m_FAdd(m_Value(X), m_Constant(C1))))) {
462 // (X + C1) * C --> (X * C) + (C * C1)
463 Constant *CC1 = ConstantExpr::getFMul(C, C1);
464 Value *XC = Builder.CreateFMulFMF(X, C, &I);
465 return BinaryOperator::CreateFAddFMF(XC, CC1, &I);
466 }
467 if (match(Op0, m_OneUse(m_FSub(m_Constant(C1), m_Value(X))))) {
468 // (C1 - X) * C --> (C * C1) - (X * C)
469 Constant *CC1 = ConstantExpr::getFMul(C, C1);
470 Value *XC = Builder.CreateFMulFMF(X, C, &I);
471 return BinaryOperator::CreateFSubFMF(CC1, XC, &I);
472 }
473 }
474
475 Value *Z;
476 if (match(&I, m_c_FMul(m_OneUse(m_FDiv(m_Value(X), m_Value(Y))),
477 m_Value(Z)))) {
478 // Sink division: (X / Y) * Z --> (X * Z) / Y
479 Value *NewFMul = Builder.CreateFMulFMF(X, Z, &I);
480 return BinaryOperator::CreateFDivFMF(NewFMul, Y, &I);
481 }
482
483 // sqrt(X) * sqrt(Y) -> sqrt(X * Y)
484 // nnan disallows the possibility of returning a number if both operands are
485 // negative (in that case, we should return NaN).
486 if (I.hasNoNaNs() &&
487 match(Op0, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(X)))) &&
488 match(Op1, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) {
489 Value *XY = Builder.CreateFMulFMF(X, Y, &I);
490 Value *Sqrt = Builder.CreateUnaryIntrinsic(Intrinsic::sqrt, XY, &I);
491 return replaceInstUsesWith(I, Sqrt);
492 }
493
494 // Like the similar transform in instsimplify, this requires 'nsz' because
495 // sqrt(-0.0) = -0.0, and -0.0 * -0.0 does not simplify to -0.0.
496 if (I.hasNoNaNs() && I.hasNoSignedZeros() && Op0 == Op1 &&
497 Op0->hasNUses(2)) {
498 // Peek through fdiv to find squaring of square root:
499 // (X / sqrt(Y)) * (X / sqrt(Y)) --> (X * X) / Y
500 if (match(Op0, m_FDiv(m_Value(X),
501 m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) {
502 Value *XX = Builder.CreateFMulFMF(X, X, &I);
503 return BinaryOperator::CreateFDivFMF(XX, Y, &I);
504 }
505 // (sqrt(Y) / X) * (sqrt(Y) / X) --> Y / (X * X)
506 if (match(Op0, m_FDiv(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y)),
507 m_Value(X)))) {
508 Value *XX = Builder.CreateFMulFMF(X, X, &I);
509 return BinaryOperator::CreateFDivFMF(Y, XX, &I);
510 }
511 }
512
513 // exp(X) * exp(Y) -> exp(X + Y)
514 // Match as long as at least one of exp has only one use.
515 if (match(Op0, m_Intrinsic<Intrinsic::exp>(m_Value(X))) &&
516 match(Op1, m_Intrinsic<Intrinsic::exp>(m_Value(Y))) &&
517 (Op0->hasOneUse() || Op1->hasOneUse())) {
518 Value *XY = Builder.CreateFAddFMF(X, Y, &I);
519 Value *Exp = Builder.CreateUnaryIntrinsic(Intrinsic::exp, XY, &I);
520 return replaceInstUsesWith(I, Exp);
521 }
522
523 // exp2(X) * exp2(Y) -> exp2(X + Y)
524 // Match as long as at least one of exp2 has only one use.
525 if (match(Op0, m_Intrinsic<Intrinsic::exp2>(m_Value(X))) &&
526 match(Op1, m_Intrinsic<Intrinsic::exp2>(m_Value(Y))) &&
527 (Op0->hasOneUse() || Op1->hasOneUse())) {
528 Value *XY = Builder.CreateFAddFMF(X, Y, &I);
529 Value *Exp2 = Builder.CreateUnaryIntrinsic(Intrinsic::exp2, XY, &I);
530 return replaceInstUsesWith(I, Exp2);
531 }
532
533 // (X*Y) * X => (X*X) * Y where Y != X
534 // The purpose is two-fold:
535 // 1) to form a power expression (of X).
536 // 2) potentially shorten the critical path: After transformation, the
537 // latency of the instruction Y is amortized by the expression of X*X,
538 // and therefore Y is in a "less critical" position compared to what it
539 // was before the transformation.
540 if (match(Op0, m_OneUse(m_c_FMul(m_Specific(Op1), m_Value(Y)))) &&
541 Op1 != Y) {
542 Value *XX = Builder.CreateFMulFMF(Op1, Op1, &I);
543 return BinaryOperator::CreateFMulFMF(XX, Y, &I);
544 }
545 if (match(Op1, m_OneUse(m_c_FMul(m_Specific(Op0), m_Value(Y)))) &&
546 Op0 != Y) {
547 Value *XX = Builder.CreateFMulFMF(Op0, Op0, &I);
548 return BinaryOperator::CreateFMulFMF(XX, Y, &I);
549 }
550 }
551
552 // log2(X * 0.5) * Y = log2(X) * Y - Y
553 if (I.isFast()) {
554 IntrinsicInst *Log2 = nullptr;
555 if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::log2>(
556 m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
557 Log2 = cast<IntrinsicInst>(Op0);
558 Y = Op1;
559 }
560 if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::log2>(
561 m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
562 Log2 = cast<IntrinsicInst>(Op1);
563 Y = Op0;
564 }
565 if (Log2) {
566 Log2->setArgOperand(0, X);
567 Log2->copyFastMathFlags(&I);
568 Value *LogXTimesY = Builder.CreateFMulFMF(Log2, Y, &I);
569 return BinaryOperator::CreateFSubFMF(LogXTimesY, Y, &I);
570 }
571 }
572
573 return nullptr;
574 }
575
576 /// Fold a divide or remainder with a select instruction divisor when one of the
577 /// select operands is zero. In that case, we can use the other select operand
578 /// because div/rem by zero is undefined.
simplifyDivRemOfSelectWithZeroOp(BinaryOperator & I)579 bool InstCombiner::simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I) {
580 SelectInst *SI = dyn_cast<SelectInst>(I.getOperand(1));
581 if (!SI)
582 return false;
583
584 int NonNullOperand;
585 if (match(SI->getTrueValue(), m_Zero()))
586 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
587 NonNullOperand = 2;
588 else if (match(SI->getFalseValue(), m_Zero()))
589 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
590 NonNullOperand = 1;
591 else
592 return false;
593
594 // Change the div/rem to use 'Y' instead of the select.
595 I.setOperand(1, SI->getOperand(NonNullOperand));
596
597 // Okay, we know we replace the operand of the div/rem with 'Y' with no
598 // problem. However, the select, or the condition of the select may have
599 // multiple uses. Based on our knowledge that the operand must be non-zero,
600 // propagate the known value for the select into other uses of it, and
601 // propagate a known value of the condition into its other users.
602
603 // If the select and condition only have a single use, don't bother with this,
604 // early exit.
605 Value *SelectCond = SI->getCondition();
606 if (SI->use_empty() && SelectCond->hasOneUse())
607 return true;
608
609 // Scan the current block backward, looking for other uses of SI.
610 BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin();
611 Type *CondTy = SelectCond->getType();
612 while (BBI != BBFront) {
613 --BBI;
614 // If we found an instruction that we can't assume will return, so
615 // information from below it cannot be propagated above it.
616 if (!isGuaranteedToTransferExecutionToSuccessor(&*BBI))
617 break;
618
619 // Replace uses of the select or its condition with the known values.
620 for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end();
621 I != E; ++I) {
622 if (*I == SI) {
623 *I = SI->getOperand(NonNullOperand);
624 Worklist.Add(&*BBI);
625 } else if (*I == SelectCond) {
626 *I = NonNullOperand == 1 ? ConstantInt::getTrue(CondTy)
627 : ConstantInt::getFalse(CondTy);
628 Worklist.Add(&*BBI);
629 }
630 }
631
632 // If we past the instruction, quit looking for it.
633 if (&*BBI == SI)
634 SI = nullptr;
635 if (&*BBI == SelectCond)
636 SelectCond = nullptr;
637
638 // If we ran out of things to eliminate, break out of the loop.
639 if (!SelectCond && !SI)
640 break;
641
642 }
643 return true;
644 }
645
646 /// True if the multiply can not be expressed in an int this size.
multiplyOverflows(const APInt & C1,const APInt & C2,APInt & Product,bool IsSigned)647 static bool multiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
648 bool IsSigned) {
649 bool Overflow;
650 Product = IsSigned ? C1.smul_ov(C2, Overflow) : C1.umul_ov(C2, Overflow);
651 return Overflow;
652 }
653
654 /// True if C1 is a multiple of C2. Quotient contains C1/C2.
isMultiple(const APInt & C1,const APInt & C2,APInt & Quotient,bool IsSigned)655 static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
656 bool IsSigned) {
657 assert(C1.getBitWidth() == C2.getBitWidth() && "Constant widths not equal");
658
659 // Bail if we will divide by zero.
660 if (C2.isNullValue())
661 return false;
662
663 // Bail if we would divide INT_MIN by -1.
664 if (IsSigned && C1.isMinSignedValue() && C2.isAllOnesValue())
665 return false;
666
667 APInt Remainder(C1.getBitWidth(), /*val=*/0ULL, IsSigned);
668 if (IsSigned)
669 APInt::sdivrem(C1, C2, Quotient, Remainder);
670 else
671 APInt::udivrem(C1, C2, Quotient, Remainder);
672
673 return Remainder.isMinValue();
674 }
675
676 /// This function implements the transforms common to both integer division
677 /// instructions (udiv and sdiv). It is called by the visitors to those integer
678 /// division instructions.
679 /// Common integer divide transforms
commonIDivTransforms(BinaryOperator & I)680 Instruction *InstCombiner::commonIDivTransforms(BinaryOperator &I) {
681 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
682 bool IsSigned = I.getOpcode() == Instruction::SDiv;
683 Type *Ty = I.getType();
684
685 // The RHS is known non-zero.
686 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
687 I.setOperand(1, V);
688 return &I;
689 }
690
691 // Handle cases involving: [su]div X, (select Cond, Y, Z)
692 // This does not apply for fdiv.
693 if (simplifyDivRemOfSelectWithZeroOp(I))
694 return &I;
695
696 const APInt *C2;
697 if (match(Op1, m_APInt(C2))) {
698 Value *X;
699 const APInt *C1;
700
701 // (X / C1) / C2 -> X / (C1*C2)
702 if ((IsSigned && match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))) ||
703 (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_APInt(C1))))) {
704 APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
705 if (!multiplyOverflows(*C1, *C2, Product, IsSigned))
706 return BinaryOperator::Create(I.getOpcode(), X,
707 ConstantInt::get(Ty, Product));
708 }
709
710 if ((IsSigned && match(Op0, m_NSWMul(m_Value(X), m_APInt(C1)))) ||
711 (!IsSigned && match(Op0, m_NUWMul(m_Value(X), m_APInt(C1))))) {
712 APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
713
714 // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
715 if (isMultiple(*C2, *C1, Quotient, IsSigned)) {
716 auto *NewDiv = BinaryOperator::Create(I.getOpcode(), X,
717 ConstantInt::get(Ty, Quotient));
718 NewDiv->setIsExact(I.isExact());
719 return NewDiv;
720 }
721
722 // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
723 if (isMultiple(*C1, *C2, Quotient, IsSigned)) {
724 auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
725 ConstantInt::get(Ty, Quotient));
726 auto *OBO = cast<OverflowingBinaryOperator>(Op0);
727 Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
728 Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
729 return Mul;
730 }
731 }
732
733 if ((IsSigned && match(Op0, m_NSWShl(m_Value(X), m_APInt(C1))) &&
734 *C1 != C1->getBitWidth() - 1) ||
735 (!IsSigned && match(Op0, m_NUWShl(m_Value(X), m_APInt(C1))))) {
736 APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
737 APInt C1Shifted = APInt::getOneBitSet(
738 C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue()));
739
740 // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of 1 << C1.
741 if (isMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
742 auto *BO = BinaryOperator::Create(I.getOpcode(), X,
743 ConstantInt::get(Ty, Quotient));
744 BO->setIsExact(I.isExact());
745 return BO;
746 }
747
748 // (X << C1) / C2 -> X * ((1 << C1) / C2) if 1 << C1 is a multiple of C2.
749 if (isMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
750 auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
751 ConstantInt::get(Ty, Quotient));
752 auto *OBO = cast<OverflowingBinaryOperator>(Op0);
753 Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
754 Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
755 return Mul;
756 }
757 }
758
759 if (!C2->isNullValue()) // avoid X udiv 0
760 if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I))
761 return FoldedDiv;
762 }
763
764 if (match(Op0, m_One())) {
765 assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?");
766 if (IsSigned) {
767 // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the
768 // result is one, if Op1 is -1 then the result is minus one, otherwise
769 // it's zero.
770 Value *Inc = Builder.CreateAdd(Op1, Op0);
771 Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(Ty, 3));
772 return SelectInst::Create(Cmp, Op1, ConstantInt::get(Ty, 0));
773 } else {
774 // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
775 // result is one, otherwise it's zero.
776 return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), Ty);
777 }
778 }
779
780 // See if we can fold away this div instruction.
781 if (SimplifyDemandedInstructionBits(I))
782 return &I;
783
784 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
785 Value *X, *Z;
786 if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) // (X - Z) / Y; Y = Op1
787 if ((IsSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
788 (!IsSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
789 return BinaryOperator::Create(I.getOpcode(), X, Op1);
790
791 // (X << Y) / X -> 1 << Y
792 Value *Y;
793 if (IsSigned && match(Op0, m_NSWShl(m_Specific(Op1), m_Value(Y))))
794 return BinaryOperator::CreateNSWShl(ConstantInt::get(Ty, 1), Y);
795 if (!IsSigned && match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y))))
796 return BinaryOperator::CreateNUWShl(ConstantInt::get(Ty, 1), Y);
797
798 // X / (X * Y) -> 1 / Y if the multiplication does not overflow.
799 if (match(Op1, m_c_Mul(m_Specific(Op0), m_Value(Y)))) {
800 bool HasNSW = cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap();
801 bool HasNUW = cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap();
802 if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) {
803 I.setOperand(0, ConstantInt::get(Ty, 1));
804 I.setOperand(1, Y);
805 return &I;
806 }
807 }
808
809 return nullptr;
810 }
811
812 static const unsigned MaxDepth = 6;
813
814 namespace {
815
816 using FoldUDivOperandCb = Instruction *(*)(Value *Op0, Value *Op1,
817 const BinaryOperator &I,
818 InstCombiner &IC);
819
820 /// Used to maintain state for visitUDivOperand().
821 struct UDivFoldAction {
822 /// Informs visitUDiv() how to fold this operand. This can be zero if this
823 /// action joins two actions together.
824 FoldUDivOperandCb FoldAction;
825
826 /// Which operand to fold.
827 Value *OperandToFold;
828
829 union {
830 /// The instruction returned when FoldAction is invoked.
831 Instruction *FoldResult;
832
833 /// Stores the LHS action index if this action joins two actions together.
834 size_t SelectLHSIdx;
835 };
836
UDivFoldAction__anonc4fbac310111::UDivFoldAction837 UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
838 : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
UDivFoldAction__anonc4fbac310111::UDivFoldAction839 UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
840 : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
841 };
842
843 } // end anonymous namespace
844
845 // X udiv 2^C -> X >> C
foldUDivPow2Cst(Value * Op0,Value * Op1,const BinaryOperator & I,InstCombiner & IC)846 static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1,
847 const BinaryOperator &I, InstCombiner &IC) {
848 Constant *C1 = getLogBase2(Op0->getType(), cast<Constant>(Op1));
849 if (!C1)
850 llvm_unreachable("Failed to constant fold udiv -> logbase2");
851 BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, C1);
852 if (I.isExact())
853 LShr->setIsExact();
854 return LShr;
855 }
856
857 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
858 // X udiv (zext (C1 << N)), where C1 is "1<<C2" --> X >> (N+C2)
foldUDivShl(Value * Op0,Value * Op1,const BinaryOperator & I,InstCombiner & IC)859 static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
860 InstCombiner &IC) {
861 Value *ShiftLeft;
862 if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
863 ShiftLeft = Op1;
864
865 Constant *CI;
866 Value *N;
867 if (!match(ShiftLeft, m_Shl(m_Constant(CI), m_Value(N))))
868 llvm_unreachable("match should never fail here!");
869 Constant *Log2Base = getLogBase2(N->getType(), CI);
870 if (!Log2Base)
871 llvm_unreachable("getLogBase2 should never fail here!");
872 N = IC.Builder.CreateAdd(N, Log2Base);
873 if (Op1 != ShiftLeft)
874 N = IC.Builder.CreateZExt(N, Op1->getType());
875 BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
876 if (I.isExact())
877 LShr->setIsExact();
878 return LShr;
879 }
880
881 // Recursively visits the possible right hand operands of a udiv
882 // instruction, seeing through select instructions, to determine if we can
883 // replace the udiv with something simpler. If we find that an operand is not
884 // able to simplify the udiv, we abort the entire transformation.
visitUDivOperand(Value * Op0,Value * Op1,const BinaryOperator & I,SmallVectorImpl<UDivFoldAction> & Actions,unsigned Depth=0)885 static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
886 SmallVectorImpl<UDivFoldAction> &Actions,
887 unsigned Depth = 0) {
888 // Check to see if this is an unsigned division with an exact power of 2,
889 // if so, convert to a right shift.
890 if (match(Op1, m_Power2())) {
891 Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1));
892 return Actions.size();
893 }
894
895 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
896 if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
897 match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
898 Actions.push_back(UDivFoldAction(foldUDivShl, Op1));
899 return Actions.size();
900 }
901
902 // The remaining tests are all recursive, so bail out if we hit the limit.
903 if (Depth++ == MaxDepth)
904 return 0;
905
906 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
907 if (size_t LHSIdx =
908 visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth))
909 if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) {
910 Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1));
911 return Actions.size();
912 }
913
914 return 0;
915 }
916
917 /// If we have zero-extended operands of an unsigned div or rem, we may be able
918 /// to narrow the operation (sink the zext below the math).
narrowUDivURem(BinaryOperator & I,InstCombiner::BuilderTy & Builder)919 static Instruction *narrowUDivURem(BinaryOperator &I,
920 InstCombiner::BuilderTy &Builder) {
921 Instruction::BinaryOps Opcode = I.getOpcode();
922 Value *N = I.getOperand(0);
923 Value *D = I.getOperand(1);
924 Type *Ty = I.getType();
925 Value *X, *Y;
926 if (match(N, m_ZExt(m_Value(X))) && match(D, m_ZExt(m_Value(Y))) &&
927 X->getType() == Y->getType() && (N->hasOneUse() || D->hasOneUse())) {
928 // udiv (zext X), (zext Y) --> zext (udiv X, Y)
929 // urem (zext X), (zext Y) --> zext (urem X, Y)
930 Value *NarrowOp = Builder.CreateBinOp(Opcode, X, Y);
931 return new ZExtInst(NarrowOp, Ty);
932 }
933
934 Constant *C;
935 if ((match(N, m_OneUse(m_ZExt(m_Value(X)))) && match(D, m_Constant(C))) ||
936 (match(D, m_OneUse(m_ZExt(m_Value(X)))) && match(N, m_Constant(C)))) {
937 // If the constant is the same in the smaller type, use the narrow version.
938 Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
939 if (ConstantExpr::getZExt(TruncC, Ty) != C)
940 return nullptr;
941
942 // udiv (zext X), C --> zext (udiv X, C')
943 // urem (zext X), C --> zext (urem X, C')
944 // udiv C, (zext X) --> zext (udiv C', X)
945 // urem C, (zext X) --> zext (urem C', X)
946 Value *NarrowOp = isa<Constant>(D) ? Builder.CreateBinOp(Opcode, X, TruncC)
947 : Builder.CreateBinOp(Opcode, TruncC, X);
948 return new ZExtInst(NarrowOp, Ty);
949 }
950
951 return nullptr;
952 }
953
visitUDiv(BinaryOperator & I)954 Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
955 if (Value *V = SimplifyUDivInst(I.getOperand(0), I.getOperand(1),
956 SQ.getWithInstruction(&I)))
957 return replaceInstUsesWith(I, V);
958
959 if (Instruction *X = foldVectorBinop(I))
960 return X;
961
962 // Handle the integer div common cases
963 if (Instruction *Common = commonIDivTransforms(I))
964 return Common;
965
966 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
967 Value *X;
968 const APInt *C1, *C2;
969 if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && match(Op1, m_APInt(C2))) {
970 // (X lshr C1) udiv C2 --> X udiv (C2 << C1)
971 bool Overflow;
972 APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
973 if (!Overflow) {
974 bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value()));
975 BinaryOperator *BO = BinaryOperator::CreateUDiv(
976 X, ConstantInt::get(X->getType(), C2ShlC1));
977 if (IsExact)
978 BO->setIsExact();
979 return BO;
980 }
981 }
982
983 // Op0 / C where C is large (negative) --> zext (Op0 >= C)
984 // TODO: Could use isKnownNegative() to handle non-constant values.
985 Type *Ty = I.getType();
986 if (match(Op1, m_Negative())) {
987 Value *Cmp = Builder.CreateICmpUGE(Op0, Op1);
988 return CastInst::CreateZExtOrBitCast(Cmp, Ty);
989 }
990 // Op0 / (sext i1 X) --> zext (Op0 == -1) (if X is 0, the div is undefined)
991 if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
992 Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
993 return CastInst::CreateZExtOrBitCast(Cmp, Ty);
994 }
995
996 if (Instruction *NarrowDiv = narrowUDivURem(I, Builder))
997 return NarrowDiv;
998
999 // If the udiv operands are non-overflowing multiplies with a common operand,
1000 // then eliminate the common factor:
1001 // (A * B) / (A * X) --> B / X (and commuted variants)
1002 // TODO: The code would be reduced if we had m_c_NUWMul pattern matching.
1003 // TODO: If -reassociation handled this generally, we could remove this.
1004 Value *A, *B;
1005 if (match(Op0, m_NUWMul(m_Value(A), m_Value(B)))) {
1006 if (match(Op1, m_NUWMul(m_Specific(A), m_Value(X))) ||
1007 match(Op1, m_NUWMul(m_Value(X), m_Specific(A))))
1008 return BinaryOperator::CreateUDiv(B, X);
1009 if (match(Op1, m_NUWMul(m_Specific(B), m_Value(X))) ||
1010 match(Op1, m_NUWMul(m_Value(X), m_Specific(B))))
1011 return BinaryOperator::CreateUDiv(A, X);
1012 }
1013
1014 // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
1015 SmallVector<UDivFoldAction, 6> UDivActions;
1016 if (visitUDivOperand(Op0, Op1, I, UDivActions))
1017 for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) {
1018 FoldUDivOperandCb Action = UDivActions[i].FoldAction;
1019 Value *ActionOp1 = UDivActions[i].OperandToFold;
1020 Instruction *Inst;
1021 if (Action)
1022 Inst = Action(Op0, ActionOp1, I, *this);
1023 else {
1024 // This action joins two actions together. The RHS of this action is
1025 // simply the last action we processed, we saved the LHS action index in
1026 // the joining action.
1027 size_t SelectRHSIdx = i - 1;
1028 Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult;
1029 size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx;
1030 Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult;
1031 Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
1032 SelectLHS, SelectRHS);
1033 }
1034
1035 // If this is the last action to process, return it to the InstCombiner.
1036 // Otherwise, we insert it before the UDiv and record it so that we may
1037 // use it as part of a joining action (i.e., a SelectInst).
1038 if (e - i != 1) {
1039 Inst->insertBefore(&I);
1040 UDivActions[i].FoldResult = Inst;
1041 } else
1042 return Inst;
1043 }
1044
1045 return nullptr;
1046 }
1047
visitSDiv(BinaryOperator & I)1048 Instruction *InstCombiner::visitSDiv(BinaryOperator &I) {
1049 if (Value *V = SimplifySDivInst(I.getOperand(0), I.getOperand(1),
1050 SQ.getWithInstruction(&I)))
1051 return replaceInstUsesWith(I, V);
1052
1053 if (Instruction *X = foldVectorBinop(I))
1054 return X;
1055
1056 // Handle the integer div common cases
1057 if (Instruction *Common = commonIDivTransforms(I))
1058 return Common;
1059
1060 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1061 Value *X;
1062 // sdiv Op0, -1 --> -Op0
1063 // sdiv Op0, (sext i1 X) --> -Op0 (because if X is 0, the op is undefined)
1064 if (match(Op1, m_AllOnes()) ||
1065 (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1066 return BinaryOperator::CreateNeg(Op0);
1067
1068 // X / INT_MIN --> X == INT_MIN
1069 if (match(Op1, m_SignMask()))
1070 return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), I.getType());
1071
1072 const APInt *Op1C;
1073 if (match(Op1, m_APInt(Op1C))) {
1074 // sdiv exact X, C --> ashr exact X, log2(C)
1075 if (I.isExact() && Op1C->isNonNegative() && Op1C->isPowerOf2()) {
1076 Value *ShAmt = ConstantInt::get(Op1->getType(), Op1C->exactLogBase2());
1077 return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName());
1078 }
1079
1080 // If the dividend is sign-extended and the constant divisor is small enough
1081 // to fit in the source type, shrink the division to the narrower type:
1082 // (sext X) sdiv C --> sext (X sdiv C)
1083 Value *Op0Src;
1084 if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
1085 Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) {
1086
1087 // In the general case, we need to make sure that the dividend is not the
1088 // minimum signed value because dividing that by -1 is UB. But here, we
1089 // know that the -1 divisor case is already handled above.
1090
1091 Constant *NarrowDivisor =
1092 ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
1093 Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
1094 return new SExtInst(NarrowOp, Op0->getType());
1095 }
1096
1097 // -X / C --> X / -C (if the negation doesn't overflow).
1098 // TODO: This could be enhanced to handle arbitrary vector constants by
1099 // checking if all elements are not the min-signed-val.
1100 if (!Op1C->isMinSignedValue() &&
1101 match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1102 Constant *NegC = ConstantInt::get(I.getType(), -(*Op1C));
1103 Instruction *BO = BinaryOperator::CreateSDiv(X, NegC);
1104 BO->setIsExact(I.isExact());
1105 return BO;
1106 }
1107 }
1108
1109 // -X / Y --> -(X / Y)
1110 Value *Y;
1111 if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1112 return BinaryOperator::CreateNSWNeg(
1113 Builder.CreateSDiv(X, Y, I.getName(), I.isExact()));
1114
1115 // If the sign bits of both operands are zero (i.e. we can prove they are
1116 // unsigned inputs), turn this into a udiv.
1117 APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
1118 if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
1119 if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
1120 // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
1121 auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1122 BO->setIsExact(I.isExact());
1123 return BO;
1124 }
1125
1126 if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1127 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1128 // Safe because the only negative value (1 << Y) can take on is
1129 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1130 // the sign bit set.
1131 auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1132 BO->setIsExact(I.isExact());
1133 return BO;
1134 }
1135 }
1136
1137 return nullptr;
1138 }
1139
1140 /// Remove negation and try to convert division into multiplication.
foldFDivConstantDivisor(BinaryOperator & I)1141 static Instruction *foldFDivConstantDivisor(BinaryOperator &I) {
1142 Constant *C;
1143 if (!match(I.getOperand(1), m_Constant(C)))
1144 return nullptr;
1145
1146 // -X / C --> X / -C
1147 Value *X;
1148 if (match(I.getOperand(0), m_FNeg(m_Value(X))))
1149 return BinaryOperator::CreateFDivFMF(X, ConstantExpr::getFNeg(C), &I);
1150
1151 // If the constant divisor has an exact inverse, this is always safe. If not,
1152 // then we can still create a reciprocal if fast-math-flags allow it and the
1153 // constant is a regular number (not zero, infinite, or denormal).
1154 if (!(C->hasExactInverseFP() || (I.hasAllowReciprocal() && C->isNormalFP())))
1155 return nullptr;
1156
1157 // Disallow denormal constants because we don't know what would happen
1158 // on all targets.
1159 // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1160 // denorms are flushed?
1161 auto *RecipC = ConstantExpr::getFDiv(ConstantFP::get(I.getType(), 1.0), C);
1162 if (!RecipC->isNormalFP())
1163 return nullptr;
1164
1165 // X / C --> X * (1 / C)
1166 return BinaryOperator::CreateFMulFMF(I.getOperand(0), RecipC, &I);
1167 }
1168
1169 /// Remove negation and try to reassociate constant math.
foldFDivConstantDividend(BinaryOperator & I)1170 static Instruction *foldFDivConstantDividend(BinaryOperator &I) {
1171 Constant *C;
1172 if (!match(I.getOperand(0), m_Constant(C)))
1173 return nullptr;
1174
1175 // C / -X --> -C / X
1176 Value *X;
1177 if (match(I.getOperand(1), m_FNeg(m_Value(X))))
1178 return BinaryOperator::CreateFDivFMF(ConstantExpr::getFNeg(C), X, &I);
1179
1180 if (!I.hasAllowReassoc() || !I.hasAllowReciprocal())
1181 return nullptr;
1182
1183 // Try to reassociate C / X expressions where X includes another constant.
1184 Constant *C2, *NewC = nullptr;
1185 if (match(I.getOperand(1), m_FMul(m_Value(X), m_Constant(C2)))) {
1186 // C / (X * C2) --> (C / C2) / X
1187 NewC = ConstantExpr::getFDiv(C, C2);
1188 } else if (match(I.getOperand(1), m_FDiv(m_Value(X), m_Constant(C2)))) {
1189 // C / (X / C2) --> (C * C2) / X
1190 NewC = ConstantExpr::getFMul(C, C2);
1191 }
1192 // Disallow denormal constants because we don't know what would happen
1193 // on all targets.
1194 // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1195 // denorms are flushed?
1196 if (!NewC || !NewC->isNormalFP())
1197 return nullptr;
1198
1199 return BinaryOperator::CreateFDivFMF(NewC, X, &I);
1200 }
1201
visitFDiv(BinaryOperator & I)1202 Instruction *InstCombiner::visitFDiv(BinaryOperator &I) {
1203 if (Value *V = SimplifyFDivInst(I.getOperand(0), I.getOperand(1),
1204 I.getFastMathFlags(),
1205 SQ.getWithInstruction(&I)))
1206 return replaceInstUsesWith(I, V);
1207
1208 if (Instruction *X = foldVectorBinop(I))
1209 return X;
1210
1211 if (Instruction *R = foldFDivConstantDivisor(I))
1212 return R;
1213
1214 if (Instruction *R = foldFDivConstantDividend(I))
1215 return R;
1216
1217 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1218 if (isa<Constant>(Op0))
1219 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1220 if (Instruction *R = FoldOpIntoSelect(I, SI))
1221 return R;
1222
1223 if (isa<Constant>(Op1))
1224 if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1225 if (Instruction *R = FoldOpIntoSelect(I, SI))
1226 return R;
1227
1228 if (I.hasAllowReassoc() && I.hasAllowReciprocal()) {
1229 Value *X, *Y;
1230 if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1231 (!isa<Constant>(Y) || !isa<Constant>(Op1))) {
1232 // (X / Y) / Z => X / (Y * Z)
1233 Value *YZ = Builder.CreateFMulFMF(Y, Op1, &I);
1234 return BinaryOperator::CreateFDivFMF(X, YZ, &I);
1235 }
1236 if (match(Op1, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1237 (!isa<Constant>(Y) || !isa<Constant>(Op0))) {
1238 // Z / (X / Y) => (Y * Z) / X
1239 Value *YZ = Builder.CreateFMulFMF(Y, Op0, &I);
1240 return BinaryOperator::CreateFDivFMF(YZ, X, &I);
1241 }
1242 // Z / (1.0 / Y) => (Y * Z)
1243 //
1244 // This is a special case of Z / (X / Y) => (Y * Z) / X, with X = 1.0. The
1245 // m_OneUse check is avoided because even in the case of the multiple uses
1246 // for 1.0/Y, the number of instructions remain the same and a division is
1247 // replaced by a multiplication.
1248 if (match(Op1, m_FDiv(m_SpecificFP(1.0), m_Value(Y))))
1249 return BinaryOperator::CreateFMulFMF(Y, Op0, &I);
1250 }
1251
1252 if (I.hasAllowReassoc() && Op0->hasOneUse() && Op1->hasOneUse()) {
1253 // sin(X) / cos(X) -> tan(X)
1254 // cos(X) / sin(X) -> 1/tan(X) (cotangent)
1255 Value *X;
1256 bool IsTan = match(Op0, m_Intrinsic<Intrinsic::sin>(m_Value(X))) &&
1257 match(Op1, m_Intrinsic<Intrinsic::cos>(m_Specific(X)));
1258 bool IsCot =
1259 !IsTan && match(Op0, m_Intrinsic<Intrinsic::cos>(m_Value(X))) &&
1260 match(Op1, m_Intrinsic<Intrinsic::sin>(m_Specific(X)));
1261
1262 if ((IsTan || IsCot) &&
1263 hasFloatFn(&TLI, I.getType(), LibFunc_tan, LibFunc_tanf, LibFunc_tanl)) {
1264 IRBuilder<> B(&I);
1265 IRBuilder<>::FastMathFlagGuard FMFGuard(B);
1266 B.setFastMathFlags(I.getFastMathFlags());
1267 AttributeList Attrs =
1268 cast<CallBase>(Op0)->getCalledFunction()->getAttributes();
1269 Value *Res = emitUnaryFloatFnCall(X, &TLI, LibFunc_tan, LibFunc_tanf,
1270 LibFunc_tanl, B, Attrs);
1271 if (IsCot)
1272 Res = B.CreateFDiv(ConstantFP::get(I.getType(), 1.0), Res);
1273 return replaceInstUsesWith(I, Res);
1274 }
1275 }
1276
1277 // -X / -Y -> X / Y
1278 Value *X, *Y;
1279 if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y)))) {
1280 I.setOperand(0, X);
1281 I.setOperand(1, Y);
1282 return &I;
1283 }
1284
1285 // X / (X * Y) --> 1.0 / Y
1286 // Reassociate to (X / X -> 1.0) is legal when NaNs are not allowed.
1287 // We can ignore the possibility that X is infinity because INF/INF is NaN.
1288 if (I.hasNoNaNs() && I.hasAllowReassoc() &&
1289 match(Op1, m_c_FMul(m_Specific(Op0), m_Value(Y)))) {
1290 I.setOperand(0, ConstantFP::get(I.getType(), 1.0));
1291 I.setOperand(1, Y);
1292 return &I;
1293 }
1294
1295 // X / fabs(X) -> copysign(1.0, X)
1296 // fabs(X) / X -> copysign(1.0, X)
1297 if (I.hasNoNaNs() && I.hasNoInfs() &&
1298 (match(&I,
1299 m_FDiv(m_Value(X), m_Intrinsic<Intrinsic::fabs>(m_Deferred(X)))) ||
1300 match(&I, m_FDiv(m_Intrinsic<Intrinsic::fabs>(m_Value(X)),
1301 m_Deferred(X))))) {
1302 Value *V = Builder.CreateBinaryIntrinsic(
1303 Intrinsic::copysign, ConstantFP::get(I.getType(), 1.0), X, &I);
1304 return replaceInstUsesWith(I, V);
1305 }
1306 return nullptr;
1307 }
1308
1309 /// This function implements the transforms common to both integer remainder
1310 /// instructions (urem and srem). It is called by the visitors to those integer
1311 /// remainder instructions.
1312 /// Common integer remainder transforms
commonIRemTransforms(BinaryOperator & I)1313 Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) {
1314 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1315
1316 // The RHS is known non-zero.
1317 if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
1318 I.setOperand(1, V);
1319 return &I;
1320 }
1321
1322 // Handle cases involving: rem X, (select Cond, Y, Z)
1323 if (simplifyDivRemOfSelectWithZeroOp(I))
1324 return &I;
1325
1326 if (isa<Constant>(Op1)) {
1327 if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1328 if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1329 if (Instruction *R = FoldOpIntoSelect(I, SI))
1330 return R;
1331 } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
1332 const APInt *Op1Int;
1333 if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
1334 (I.getOpcode() == Instruction::URem ||
1335 !Op1Int->isMinSignedValue())) {
1336 // foldOpIntoPhi will speculate instructions to the end of the PHI's
1337 // predecessor blocks, so do this only if we know the srem or urem
1338 // will not fault.
1339 if (Instruction *NV = foldOpIntoPhi(I, PN))
1340 return NV;
1341 }
1342 }
1343
1344 // See if we can fold away this rem instruction.
1345 if (SimplifyDemandedInstructionBits(I))
1346 return &I;
1347 }
1348 }
1349
1350 return nullptr;
1351 }
1352
visitURem(BinaryOperator & I)1353 Instruction *InstCombiner::visitURem(BinaryOperator &I) {
1354 if (Value *V = SimplifyURemInst(I.getOperand(0), I.getOperand(1),
1355 SQ.getWithInstruction(&I)))
1356 return replaceInstUsesWith(I, V);
1357
1358 if (Instruction *X = foldVectorBinop(I))
1359 return X;
1360
1361 if (Instruction *common = commonIRemTransforms(I))
1362 return common;
1363
1364 if (Instruction *NarrowRem = narrowUDivURem(I, Builder))
1365 return NarrowRem;
1366
1367 // X urem Y -> X and Y-1, where Y is a power of 2,
1368 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1369 Type *Ty = I.getType();
1370 if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1371 // This may increase instruction count, we don't enforce that Y is a
1372 // constant.
1373 Constant *N1 = Constant::getAllOnesValue(Ty);
1374 Value *Add = Builder.CreateAdd(Op1, N1);
1375 return BinaryOperator::CreateAnd(Op0, Add);
1376 }
1377
1378 // 1 urem X -> zext(X != 1)
1379 if (match(Op0, m_One())) {
1380 Value *Cmp = Builder.CreateICmpNE(Op1, ConstantInt::get(Ty, 1));
1381 return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1382 }
1383
1384 // X urem C -> X < C ? X : X - C, where C >= signbit.
1385 if (match(Op1, m_Negative())) {
1386 Value *Cmp = Builder.CreateICmpULT(Op0, Op1);
1387 Value *Sub = Builder.CreateSub(Op0, Op1);
1388 return SelectInst::Create(Cmp, Op0, Sub);
1389 }
1390
1391 // If the divisor is a sext of a boolean, then the divisor must be max
1392 // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also
1393 // max unsigned value. In that case, the remainder is 0:
1394 // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0
1395 Value *X;
1396 if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1397 Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1398 return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), Op0);
1399 }
1400
1401 return nullptr;
1402 }
1403
visitSRem(BinaryOperator & I)1404 Instruction *InstCombiner::visitSRem(BinaryOperator &I) {
1405 if (Value *V = SimplifySRemInst(I.getOperand(0), I.getOperand(1),
1406 SQ.getWithInstruction(&I)))
1407 return replaceInstUsesWith(I, V);
1408
1409 if (Instruction *X = foldVectorBinop(I))
1410 return X;
1411
1412 // Handle the integer rem common cases
1413 if (Instruction *Common = commonIRemTransforms(I))
1414 return Common;
1415
1416 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1417 {
1418 const APInt *Y;
1419 // X % -Y -> X % Y
1420 if (match(Op1, m_Negative(Y)) && !Y->isMinSignedValue()) {
1421 Worklist.AddValue(I.getOperand(1));
1422 I.setOperand(1, ConstantInt::get(I.getType(), -*Y));
1423 return &I;
1424 }
1425 }
1426
1427 // -X srem Y --> -(X srem Y)
1428 Value *X, *Y;
1429 if (match(&I, m_SRem(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1430 return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y));
1431
1432 // If the sign bits of both operands are zero (i.e. we can prove they are
1433 // unsigned inputs), turn this into a urem.
1434 APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
1435 if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1436 MaskedValueIsZero(Op0, Mask, 0, &I)) {
1437 // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1438 return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1439 }
1440
1441 // If it's a constant vector, flip any negative values positive.
1442 if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1443 Constant *C = cast<Constant>(Op1);
1444 unsigned VWidth = C->getType()->getVectorNumElements();
1445
1446 bool hasNegative = false;
1447 bool hasMissing = false;
1448 for (unsigned i = 0; i != VWidth; ++i) {
1449 Constant *Elt = C->getAggregateElement(i);
1450 if (!Elt) {
1451 hasMissing = true;
1452 break;
1453 }
1454
1455 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1456 if (RHS->isNegative())
1457 hasNegative = true;
1458 }
1459
1460 if (hasNegative && !hasMissing) {
1461 SmallVector<Constant *, 16> Elts(VWidth);
1462 for (unsigned i = 0; i != VWidth; ++i) {
1463 Elts[i] = C->getAggregateElement(i); // Handle undef, etc.
1464 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1465 if (RHS->isNegative())
1466 Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1467 }
1468 }
1469
1470 Constant *NewRHSV = ConstantVector::get(Elts);
1471 if (NewRHSV != C) { // Don't loop on -MININT
1472 Worklist.AddValue(I.getOperand(1));
1473 I.setOperand(1, NewRHSV);
1474 return &I;
1475 }
1476 }
1477 }
1478
1479 return nullptr;
1480 }
1481
visitFRem(BinaryOperator & I)1482 Instruction *InstCombiner::visitFRem(BinaryOperator &I) {
1483 if (Value *V = SimplifyFRemInst(I.getOperand(0), I.getOperand(1),
1484 I.getFastMathFlags(),
1485 SQ.getWithInstruction(&I)))
1486 return replaceInstUsesWith(I, V);
1487
1488 if (Instruction *X = foldVectorBinop(I))
1489 return X;
1490
1491 return nullptr;
1492 }
1493