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
40using namespace llvm;
41using 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.
46static 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, P: m_LShr(L: m_OneUse(SubPattern: m_Shl(L: m_Value(V&: One), R: m_Value(V&: A))), R: m_Value(V&: B))) &&
59 match(V: One, P: m_One())) {
60 A = IC.Builder.CreateSub(LHS: A, RHS: B);
61 return IC.Builder.CreateShl(LHS: One, RHS: 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>(Val: V);
67 if (I && I->isLogicalShift() &&
68 IC.isKnownToBeAPowerOfTwo(V: I->getOperand(i_nocapture: 0), OrZero: false, Depth: 0, CxtI: &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(V: I->getOperand(i_nocapture: 0), IC, CxtI)) {
72 IC.replaceOperand(I&: *I, OpNum: 0, V: 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().
99static 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(V: &I, P: m_c_Mul(L: m_OneUse(SubPattern: m_Select(C: m_Value(V&: Cond), L: m_One(), R: m_AllOnes())),
106 R: m_Value(V&: OtherOp)))) {
107 bool HasAnyNoWrap = I.hasNoSignedWrap() || I.hasNoUnsignedWrap();
108 Value *Neg = Builder.CreateNeg(V: OtherOp, Name: "", HasNSW: HasAnyNoWrap);
109 return Builder.CreateSelect(C: Cond, True: OtherOp, False: 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(V: &I, P: m_c_Mul(L: m_OneUse(SubPattern: m_Select(C: m_Value(V&: Cond), L: m_AllOnes(), R: m_One())),
114 R: m_Value(V&: OtherOp)))) {
115 bool HasAnyNoWrap = I.hasNoSignedWrap() || I.hasNoUnsignedWrap();
116 Value *Neg = Builder.CreateNeg(V: OtherOp, Name: "", HasNSW: HasAnyNoWrap);
117 return Builder.CreateSelect(C: Cond, True: Neg, False: 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(V: &I, P: m_c_FMul(L: m_OneUse(SubPattern: m_Select(C: m_Value(V&: Cond), L: m_SpecificFP(V: 1.0),
123 R: m_SpecificFP(V: -1.0))),
124 R: m_Value(V&: OtherOp)))) {
125 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
126 Builder.setFastMathFlags(I.getFastMathFlags());
127 return Builder.CreateSelect(C: Cond, True: OtherOp, False: Builder.CreateFNeg(V: 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(V: &I, P: m_c_FMul(L: m_OneUse(SubPattern: m_Select(C: m_Value(V&: Cond), L: m_SpecificFP(V: -1.0),
133 R: m_SpecificFP(V: 1.0))),
134 R: m_Value(V&: OtherOp)))) {
135 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
136 Builder.setFastMathFlags(I.getFastMathFlags());
137 return Builder.CreateSelect(C: Cond, True: Builder.CreateFNeg(V: OtherOp), False: 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.
145static Value *foldMulShl1(BinaryOperator &Mul, bool CommuteOperands,
146 InstCombiner::BuilderTy &Builder) {
147 Value *X = Mul.getOperand(i_nocapture: 0), *Y = Mul.getOperand(i_nocapture: 1);
148 if (CommuteOperands)
149 std::swap(a&: X, b&: 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(V: Y, P: m_Shl(L: m_One(), R: m_Value(V&: Z)))) {
157 bool PropagateNSW = HasNSW && cast<ShlOperator>(Val: Y)->hasNoSignedWrap();
158 return Builder.CreateShl(LHS: X, RHS: Z, Name: Mul.getName(), HasNUW, HasNSW: 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(V: Y, P: m_OneUse(SubPattern: m_Add(L: m_BinOp(I&: Shift), R: m_One()))) &&
167 match(V: Shift, P: m_OneUse(SubPattern: m_Shl(L: m_One(), R: m_Value(V&: Z))))) {
168 bool PropagateNSW = HasNSW && Shift->hasNoSignedWrap();
169 Value *FrX = X;
170 if (!isGuaranteedNotToBeUndef(V: X))
171 FrX = Builder.CreateFreeze(V: X, Name: X->getName() + ".fr");
172 Value *Shl = Builder.CreateShl(LHS: FrX, RHS: Z, Name: "mulshl", HasNUW, HasNSW: PropagateNSW);
173 return Builder.CreateAdd(LHS: Shl, RHS: FrX, Name: Mul.getName(), HasNUW, HasNSW: PropagateNSW);
174 }
175
176 // Similar to above, but a decrement of the shifted value is disguised as
177 // 'not' and becomes a sub:
178 // X * (~(-1 << Z)) --> X * ((1 << Z) - 1) --> (X << Z) - X
179 // This increases uses of X, so it may require a freeze, but that is still
180 // expected to be an improvement because it removes the multiply.
181 if (match(V: Y, P: m_OneUse(SubPattern: m_Not(V: m_OneUse(SubPattern: m_Shl(L: m_AllOnes(), R: m_Value(V&: Z))))))) {
182 Value *FrX = X;
183 if (!isGuaranteedNotToBeUndef(V: X))
184 FrX = Builder.CreateFreeze(V: X, Name: X->getName() + ".fr");
185 Value *Shl = Builder.CreateShl(LHS: FrX, RHS: Z, Name: "mulshl");
186 return Builder.CreateSub(LHS: Shl, RHS: FrX, Name: Mul.getName());
187 }
188
189 return nullptr;
190}
191
192static Value *takeLog2(IRBuilderBase &Builder, Value *Op, unsigned Depth,
193 bool AssumeNonZero, bool DoFold);
194
195Instruction *InstCombinerImpl::visitMul(BinaryOperator &I) {
196 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
197 if (Value *V =
198 simplifyMulInst(LHS: Op0, RHS: Op1, IsNSW: I.hasNoSignedWrap(), IsNUW: I.hasNoUnsignedWrap(),
199 Q: SQ.getWithInstruction(I: &I)))
200 return replaceInstUsesWith(I, V);
201
202 if (SimplifyAssociativeOrCommutative(I))
203 return &I;
204
205 if (Instruction *X = foldVectorBinop(Inst&: I))
206 return X;
207
208 if (Instruction *Phi = foldBinopWithPhiOperands(BO&: I))
209 return Phi;
210
211 if (Value *V = foldUsingDistributiveLaws(I))
212 return replaceInstUsesWith(I, V);
213
214 Type *Ty = I.getType();
215 const unsigned BitWidth = Ty->getScalarSizeInBits();
216 const bool HasNSW = I.hasNoSignedWrap();
217 const bool HasNUW = I.hasNoUnsignedWrap();
218
219 // X * -1 --> 0 - X
220 if (match(V: Op1, P: m_AllOnes())) {
221 return HasNSW ? BinaryOperator::CreateNSWNeg(Op: Op0)
222 : BinaryOperator::CreateNeg(Op: Op0);
223 }
224
225 // Also allow combining multiply instructions on vectors.
226 {
227 Value *NewOp;
228 Constant *C1, *C2;
229 const APInt *IVal;
230 if (match(V: &I, P: m_Mul(L: m_Shl(L: m_Value(V&: NewOp), R: m_ImmConstant(C&: C2)),
231 R: m_ImmConstant(C&: C1))) &&
232 match(V: C1, P: m_APInt(Res&: IVal))) {
233 // ((X << C2)*C1) == (X * (C1 << C2))
234 Constant *Shl =
235 ConstantFoldBinaryOpOperands(Opcode: Instruction::Shl, LHS: C1, RHS: C2, DL);
236 assert(Shl && "Constant folding of immediate constants failed");
237 BinaryOperator *Mul = cast<BinaryOperator>(Val: I.getOperand(i_nocapture: 0));
238 BinaryOperator *BO = BinaryOperator::CreateMul(V1: NewOp, V2: Shl);
239 if (HasNUW && Mul->hasNoUnsignedWrap())
240 BO->setHasNoUnsignedWrap();
241 if (HasNSW && Mul->hasNoSignedWrap() && Shl->isNotMinSignedValue())
242 BO->setHasNoSignedWrap();
243 return BO;
244 }
245
246 if (match(V: &I, P: m_Mul(L: m_Value(V&: NewOp), R: m_Constant(C&: C1)))) {
247 // Replace X*(2^C) with X << C, where C is either a scalar or a vector.
248 if (Constant *NewCst = ConstantExpr::getExactLogBase2(C: C1)) {
249 BinaryOperator *Shl = BinaryOperator::CreateShl(V1: NewOp, V2: NewCst);
250
251 if (HasNUW)
252 Shl->setHasNoUnsignedWrap();
253 if (HasNSW) {
254 const APInt *V;
255 if (match(V: NewCst, P: m_APInt(Res&: V)) && *V != V->getBitWidth() - 1)
256 Shl->setHasNoSignedWrap();
257 }
258
259 return Shl;
260 }
261 }
262 }
263
264 if (Op0->hasOneUse() && match(V: Op1, P: m_NegatedPower2())) {
265 // Interpret X * (-1<<C) as (-X) * (1<<C) and try to sink the negation.
266 // The "* (1<<C)" thus becomes a potential shifting opportunity.
267 if (Value *NegOp0 =
268 Negator::Negate(/*IsNegation*/ LHSIsZero: true, IsNSW: HasNSW, Root: Op0, IC&: *this)) {
269 auto *Op1C = cast<Constant>(Val: Op1);
270 return replaceInstUsesWith(
271 I, V: Builder.CreateMul(LHS: NegOp0, RHS: ConstantExpr::getNeg(C: Op1C), Name: "",
272 /* HasNUW */ false,
273 HasNSW: HasNSW && Op1C->isNotMinSignedValue()));
274 }
275
276 // Try to convert multiply of extended operand to narrow negate and shift
277 // for better analysis.
278 // This is valid if the shift amount (trailing zeros in the multiplier
279 // constant) clears more high bits than the bitwidth difference between
280 // source and destination types:
281 // ({z/s}ext X) * (-1<<C) --> (zext (-X)) << C
282 const APInt *NegPow2C;
283 Value *X;
284 if (match(V: Op0, P: m_ZExtOrSExt(Op: m_Value(V&: X))) &&
285 match(V: Op1, P: m_APIntAllowPoison(Res&: NegPow2C))) {
286 unsigned SrcWidth = X->getType()->getScalarSizeInBits();
287 unsigned ShiftAmt = NegPow2C->countr_zero();
288 if (ShiftAmt >= BitWidth - SrcWidth) {
289 Value *N = Builder.CreateNeg(V: X, Name: X->getName() + ".neg");
290 Value *Z = Builder.CreateZExt(V: N, DestTy: Ty, Name: N->getName() + ".z");
291 return BinaryOperator::CreateShl(V1: Z, V2: ConstantInt::get(Ty, V: ShiftAmt));
292 }
293 }
294 }
295
296 if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
297 return FoldedMul;
298
299 if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
300 return replaceInstUsesWith(I, V: FoldedMul);
301
302 // Simplify mul instructions with a constant RHS.
303 Constant *MulC;
304 if (match(V: Op1, P: m_ImmConstant(C&: MulC))) {
305 // Canonicalize (X+C1)*MulC -> X*MulC+C1*MulC.
306 // Canonicalize (X|C1)*MulC -> X*MulC+C1*MulC.
307 Value *X;
308 Constant *C1;
309 if (match(V: Op0, P: m_OneUse(SubPattern: m_AddLike(L: m_Value(V&: X), R: m_ImmConstant(C&: C1))))) {
310 // C1*MulC simplifies to a tidier constant.
311 Value *NewC = Builder.CreateMul(LHS: C1, RHS: MulC);
312 auto *BOp0 = cast<BinaryOperator>(Val: Op0);
313 bool Op0NUW =
314 (BOp0->getOpcode() == Instruction::Or || BOp0->hasNoUnsignedWrap());
315 Value *NewMul = Builder.CreateMul(LHS: X, RHS: MulC);
316 auto *BO = BinaryOperator::CreateAdd(V1: NewMul, V2: NewC);
317 if (HasNUW && Op0NUW) {
318 // If NewMulBO is constant we also can set BO to nuw.
319 if (auto *NewMulBO = dyn_cast<BinaryOperator>(Val: NewMul))
320 NewMulBO->setHasNoUnsignedWrap();
321 BO->setHasNoUnsignedWrap();
322 }
323 return BO;
324 }
325 }
326
327 // abs(X) * abs(X) -> X * X
328 Value *X;
329 if (Op0 == Op1 && match(V: Op0, P: m_Intrinsic<Intrinsic::abs>(Op0: m_Value(V&: X))))
330 return BinaryOperator::CreateMul(V1: X, V2: X);
331
332 {
333 Value *Y;
334 // abs(X) * abs(Y) -> abs(X * Y)
335 if (I.hasNoSignedWrap() &&
336 match(V: Op0,
337 P: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::abs>(Op0: m_Value(V&: X), Op1: m_One()))) &&
338 match(V: Op1, P: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::abs>(Op0: m_Value(V&: Y), Op1: m_One()))))
339 return replaceInstUsesWith(
340 I, V: Builder.CreateBinaryIntrinsic(ID: Intrinsic::abs,
341 LHS: Builder.CreateNSWMul(LHS: X, RHS: Y),
342 RHS: Builder.getTrue()));
343 }
344
345 // -X * C --> X * -C
346 Value *Y;
347 Constant *Op1C;
348 if (match(V: Op0, P: m_Neg(V: m_Value(V&: X))) && match(V: Op1, P: m_Constant(C&: Op1C)))
349 return BinaryOperator::CreateMul(V1: X, V2: ConstantExpr::getNeg(C: Op1C));
350
351 // -X * -Y --> X * Y
352 if (match(V: Op0, P: m_Neg(V: m_Value(V&: X))) && match(V: Op1, P: m_Neg(V: m_Value(V&: Y)))) {
353 auto *NewMul = BinaryOperator::CreateMul(V1: X, V2: Y);
354 if (HasNSW && cast<OverflowingBinaryOperator>(Val: Op0)->hasNoSignedWrap() &&
355 cast<OverflowingBinaryOperator>(Val: Op1)->hasNoSignedWrap())
356 NewMul->setHasNoSignedWrap();
357 return NewMul;
358 }
359
360 // -X * Y --> -(X * Y)
361 // X * -Y --> -(X * Y)
362 if (match(V: &I, P: m_c_Mul(L: m_OneUse(SubPattern: m_Neg(V: m_Value(V&: X))), R: m_Value(V&: Y))))
363 return BinaryOperator::CreateNeg(Op: Builder.CreateMul(LHS: X, RHS: Y));
364
365 // (-X * Y) * -X --> (X * Y) * X
366 // (-X << Y) * -X --> (X << Y) * X
367 if (match(V: Op1, P: m_Neg(V: m_Value(V&: X)))) {
368 if (Value *NegOp0 = Negator::Negate(LHSIsZero: false, /*IsNSW*/ false, Root: Op0, IC&: *this))
369 return BinaryOperator::CreateMul(V1: NegOp0, V2: X);
370 }
371
372 if (Op0->hasOneUse()) {
373 // (mul (div exact X, C0), C1)
374 // -> (div exact X, C0 / C1)
375 // iff C0 % C1 == 0 and X / (C0 / C1) doesn't create UB.
376 const APInt *C1;
377 auto UDivCheck = [&C1](const APInt &C) { return C.urem(RHS: *C1).isZero(); };
378 auto SDivCheck = [&C1](const APInt &C) {
379 APInt Quot, Rem;
380 APInt::sdivrem(LHS: C, RHS: *C1, Quotient&: Quot, Remainder&: Rem);
381 return Rem.isZero() && !Quot.isAllOnes();
382 };
383 if (match(V: Op1, P: m_APInt(Res&: C1)) &&
384 (match(V: Op0, P: m_Exact(SubPattern: m_UDiv(L: m_Value(V&: X), R: m_CheckedInt(CheckFn: UDivCheck)))) ||
385 match(V: Op0, P: m_Exact(SubPattern: m_SDiv(L: m_Value(V&: X), R: m_CheckedInt(CheckFn: SDivCheck)))))) {
386 auto BOpc = cast<BinaryOperator>(Val: Op0)->getOpcode();
387 return BinaryOperator::CreateExact(
388 Opc: BOpc, V1: X,
389 V2: Builder.CreateBinOp(Opc: BOpc, LHS: cast<BinaryOperator>(Val: Op0)->getOperand(i_nocapture: 1),
390 RHS: Op1));
391 }
392 }
393
394 // (X / Y) * Y = X - (X % Y)
395 // (X / Y) * -Y = (X % Y) - X
396 {
397 Value *Y = Op1;
398 BinaryOperator *Div = dyn_cast<BinaryOperator>(Val: Op0);
399 if (!Div || (Div->getOpcode() != Instruction::UDiv &&
400 Div->getOpcode() != Instruction::SDiv)) {
401 Y = Op0;
402 Div = dyn_cast<BinaryOperator>(Val: Op1);
403 }
404 Value *Neg = dyn_castNegVal(V: Y);
405 if (Div && Div->hasOneUse() &&
406 (Div->getOperand(i_nocapture: 1) == Y || Div->getOperand(i_nocapture: 1) == Neg) &&
407 (Div->getOpcode() == Instruction::UDiv ||
408 Div->getOpcode() == Instruction::SDiv)) {
409 Value *X = Div->getOperand(i_nocapture: 0), *DivOp1 = Div->getOperand(i_nocapture: 1);
410
411 // If the division is exact, X % Y is zero, so we end up with X or -X.
412 if (Div->isExact()) {
413 if (DivOp1 == Y)
414 return replaceInstUsesWith(I, V: X);
415 return BinaryOperator::CreateNeg(Op: X);
416 }
417
418 auto RemOpc = Div->getOpcode() == Instruction::UDiv ? Instruction::URem
419 : Instruction::SRem;
420 // X must be frozen because we are increasing its number of uses.
421 Value *XFreeze = X;
422 if (!isGuaranteedNotToBeUndef(V: X))
423 XFreeze = Builder.CreateFreeze(V: X, Name: X->getName() + ".fr");
424 Value *Rem = Builder.CreateBinOp(Opc: RemOpc, LHS: XFreeze, RHS: DivOp1);
425 if (DivOp1 == Y)
426 return BinaryOperator::CreateSub(V1: XFreeze, V2: Rem);
427 return BinaryOperator::CreateSub(V1: Rem, V2: XFreeze);
428 }
429 }
430
431 // Fold the following two scenarios:
432 // 1) i1 mul -> i1 and.
433 // 2) X * Y --> X & Y, iff X, Y can be only {0,1}.
434 // Note: We could use known bits to generalize this and related patterns with
435 // shifts/truncs
436 if (Ty->isIntOrIntVectorTy(BitWidth: 1) ||
437 (match(V: Op0, P: m_And(L: m_Value(), R: m_One())) &&
438 match(V: Op1, P: m_And(L: m_Value(), R: m_One()))))
439 return BinaryOperator::CreateAnd(V1: Op0, V2: Op1);
440
441 if (Value *R = foldMulShl1(Mul&: I, /* CommuteOperands */ false, Builder))
442 return replaceInstUsesWith(I, V: R);
443 if (Value *R = foldMulShl1(Mul&: I, /* CommuteOperands */ true, Builder))
444 return replaceInstUsesWith(I, V: R);
445
446 // (zext bool X) * (zext bool Y) --> zext (and X, Y)
447 // (sext bool X) * (sext bool Y) --> zext (and X, Y)
448 // Note: -1 * -1 == 1 * 1 == 1 (if the extends match, the result is the same)
449 if (((match(V: Op0, P: m_ZExt(Op: m_Value(V&: X))) && match(V: Op1, P: m_ZExt(Op: m_Value(V&: Y)))) ||
450 (match(V: Op0, P: m_SExt(Op: m_Value(V&: X))) && match(V: Op1, P: m_SExt(Op: m_Value(V&: Y))))) &&
451 X->getType()->isIntOrIntVectorTy(BitWidth: 1) && X->getType() == Y->getType() &&
452 (Op0->hasOneUse() || Op1->hasOneUse() || X == Y)) {
453 Value *And = Builder.CreateAnd(LHS: X, RHS: Y, Name: "mulbool");
454 return CastInst::Create(Instruction::ZExt, S: And, Ty);
455 }
456 // (sext bool X) * (zext bool Y) --> sext (and X, Y)
457 // (zext bool X) * (sext bool Y) --> sext (and X, Y)
458 // Note: -1 * 1 == 1 * -1 == -1
459 if (((match(V: Op0, P: m_SExt(Op: m_Value(V&: X))) && match(V: Op1, P: m_ZExt(Op: m_Value(V&: Y)))) ||
460 (match(V: Op0, P: m_ZExt(Op: m_Value(V&: X))) && match(V: Op1, P: m_SExt(Op: m_Value(V&: Y))))) &&
461 X->getType()->isIntOrIntVectorTy(BitWidth: 1) && X->getType() == Y->getType() &&
462 (Op0->hasOneUse() || Op1->hasOneUse())) {
463 Value *And = Builder.CreateAnd(LHS: X, RHS: Y, Name: "mulbool");
464 return CastInst::Create(Instruction::SExt, S: And, Ty);
465 }
466
467 // (zext bool X) * Y --> X ? Y : 0
468 // Y * (zext bool X) --> X ? Y : 0
469 if (match(V: Op0, P: m_ZExt(Op: m_Value(V&: X))) && X->getType()->isIntOrIntVectorTy(BitWidth: 1))
470 return SelectInst::Create(C: X, S1: Op1, S2: ConstantInt::getNullValue(Ty));
471 if (match(V: Op1, P: m_ZExt(Op: m_Value(V&: X))) && X->getType()->isIntOrIntVectorTy(BitWidth: 1))
472 return SelectInst::Create(C: X, S1: Op0, S2: ConstantInt::getNullValue(Ty));
473
474 // mul (sext X), Y -> select X, -Y, 0
475 // mul Y, (sext X) -> select X, -Y, 0
476 if (match(V: &I, P: m_c_Mul(L: m_OneUse(SubPattern: m_SExt(Op: m_Value(V&: X))), R: m_Value(V&: Y))) &&
477 X->getType()->isIntOrIntVectorTy(BitWidth: 1))
478 return SelectInst::Create(C: X, S1: Builder.CreateNeg(V: Y, Name: "", HasNSW: I.hasNoSignedWrap()),
479 S2: ConstantInt::getNullValue(Ty: Op0->getType()));
480
481 Constant *ImmC;
482 if (match(V: Op1, P: m_ImmConstant(C&: ImmC))) {
483 // (sext bool X) * C --> X ? -C : 0
484 if (match(V: Op0, P: m_SExt(Op: m_Value(V&: X))) && X->getType()->isIntOrIntVectorTy(BitWidth: 1)) {
485 Constant *NegC = ConstantExpr::getNeg(C: ImmC);
486 return SelectInst::Create(C: X, S1: NegC, S2: ConstantInt::getNullValue(Ty));
487 }
488
489 // (ashr i32 X, 31) * C --> (X < 0) ? -C : 0
490 const APInt *C;
491 if (match(V: Op0, P: m_OneUse(SubPattern: m_AShr(L: m_Value(V&: X), R: m_APInt(Res&: C)))) &&
492 *C == C->getBitWidth() - 1) {
493 Constant *NegC = ConstantExpr::getNeg(C: ImmC);
494 Value *IsNeg = Builder.CreateIsNeg(Arg: X, Name: "isneg");
495 return SelectInst::Create(C: IsNeg, S1: NegC, S2: ConstantInt::getNullValue(Ty));
496 }
497 }
498
499 // (lshr X, 31) * Y --> (X < 0) ? Y : 0
500 // TODO: We are not checking one-use because the elimination of the multiply
501 // is better for analysis?
502 const APInt *C;
503 if (match(V: &I, P: m_c_BinOp(L: m_LShr(L: m_Value(V&: X), R: m_APInt(Res&: C)), R: m_Value(V&: Y))) &&
504 *C == C->getBitWidth() - 1) {
505 Value *IsNeg = Builder.CreateIsNeg(Arg: X, Name: "isneg");
506 return SelectInst::Create(C: IsNeg, S1: Y, S2: ConstantInt::getNullValue(Ty));
507 }
508
509 // (and X, 1) * Y --> (trunc X) ? Y : 0
510 if (match(V: &I, P: m_c_BinOp(L: m_OneUse(SubPattern: m_And(L: m_Value(V&: X), R: m_One())), R: m_Value(V&: Y)))) {
511 Value *Tr = Builder.CreateTrunc(V: X, DestTy: CmpInst::makeCmpResultType(opnd_type: Ty));
512 return SelectInst::Create(C: Tr, S1: Y, S2: ConstantInt::getNullValue(Ty));
513 }
514
515 // ((ashr X, 31) | 1) * X --> abs(X)
516 // X * ((ashr X, 31) | 1) --> abs(X)
517 if (match(V: &I, P: m_c_BinOp(L: m_Or(L: m_AShr(L: m_Value(V&: X),
518 R: m_SpecificIntAllowPoison(V: BitWidth - 1)),
519 R: m_One()),
520 R: m_Deferred(V: X)))) {
521 Value *Abs = Builder.CreateBinaryIntrinsic(
522 ID: Intrinsic::abs, LHS: X, RHS: ConstantInt::getBool(Context&: I.getContext(), V: HasNSW));
523 Abs->takeName(V: &I);
524 return replaceInstUsesWith(I, V: Abs);
525 }
526
527 if (Instruction *Ext = narrowMathIfNoOverflow(I))
528 return Ext;
529
530 if (Instruction *Res = foldBinOpOfSelectAndCastOfSelectCondition(I))
531 return Res;
532
533 // (mul Op0 Op1):
534 // if Log2(Op0) folds away ->
535 // (shl Op1, Log2(Op0))
536 // if Log2(Op1) folds away ->
537 // (shl Op0, Log2(Op1))
538 if (takeLog2(Builder, Op: Op0, /*Depth*/ 0, /*AssumeNonZero*/ false,
539 /*DoFold*/ false)) {
540 Value *Res = takeLog2(Builder, Op: Op0, /*Depth*/ 0, /*AssumeNonZero*/ false,
541 /*DoFold*/ true);
542 BinaryOperator *Shl = BinaryOperator::CreateShl(V1: Op1, V2: Res);
543 // We can only propegate nuw flag.
544 Shl->setHasNoUnsignedWrap(HasNUW);
545 return Shl;
546 }
547 if (takeLog2(Builder, Op: Op1, /*Depth*/ 0, /*AssumeNonZero*/ false,
548 /*DoFold*/ false)) {
549 Value *Res = takeLog2(Builder, Op: Op1, /*Depth*/ 0, /*AssumeNonZero*/ false,
550 /*DoFold*/ true);
551 BinaryOperator *Shl = BinaryOperator::CreateShl(V1: Op0, V2: Res);
552 // We can only propegate nuw flag.
553 Shl->setHasNoUnsignedWrap(HasNUW);
554 return Shl;
555 }
556
557 bool Changed = false;
558 if (!HasNSW && willNotOverflowSignedMul(LHS: Op0, RHS: Op1, CxtI: I)) {
559 Changed = true;
560 I.setHasNoSignedWrap(true);
561 }
562
563 if (!HasNUW && willNotOverflowUnsignedMul(LHS: Op0, RHS: Op1, CxtI: I, IsNSW: I.hasNoSignedWrap())) {
564 Changed = true;
565 I.setHasNoUnsignedWrap(true);
566 }
567
568 return Changed ? &I : nullptr;
569}
570
571Instruction *InstCombinerImpl::foldFPSignBitOps(BinaryOperator &I) {
572 BinaryOperator::BinaryOps Opcode = I.getOpcode();
573 assert((Opcode == Instruction::FMul || Opcode == Instruction::FDiv) &&
574 "Expected fmul or fdiv");
575
576 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
577 Value *X, *Y;
578
579 // -X * -Y --> X * Y
580 // -X / -Y --> X / Y
581 if (match(V: Op0, P: m_FNeg(X: m_Value(V&: X))) && match(V: Op1, P: m_FNeg(X: m_Value(V&: Y))))
582 return BinaryOperator::CreateWithCopiedFlags(Opc: Opcode, V1: X, V2: Y, CopyO: &I);
583
584 // fabs(X) * fabs(X) -> X * X
585 // fabs(X) / fabs(X) -> X / X
586 if (Op0 == Op1 && match(V: Op0, P: m_FAbs(Op0: m_Value(V&: X))))
587 return BinaryOperator::CreateWithCopiedFlags(Opc: Opcode, V1: X, V2: X, CopyO: &I);
588
589 // fabs(X) * fabs(Y) --> fabs(X * Y)
590 // fabs(X) / fabs(Y) --> fabs(X / Y)
591 if (match(V: Op0, P: m_FAbs(Op0: m_Value(V&: X))) && match(V: Op1, P: m_FAbs(Op0: m_Value(V&: Y))) &&
592 (Op0->hasOneUse() || Op1->hasOneUse())) {
593 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
594 Builder.setFastMathFlags(I.getFastMathFlags());
595 Value *XY = Builder.CreateBinOp(Opc: Opcode, LHS: X, RHS: Y);
596 Value *Fabs = Builder.CreateUnaryIntrinsic(ID: Intrinsic::fabs, V: XY);
597 Fabs->takeName(V: &I);
598 return replaceInstUsesWith(I, V: Fabs);
599 }
600
601 return nullptr;
602}
603
604Instruction *InstCombinerImpl::foldPowiReassoc(BinaryOperator &I) {
605 auto createPowiExpr = [](BinaryOperator &I, InstCombinerImpl &IC, Value *X,
606 Value *Y, Value *Z) {
607 InstCombiner::BuilderTy &Builder = IC.Builder;
608 Value *YZ = Builder.CreateAdd(LHS: Y, RHS: Z);
609 Instruction *NewPow = Builder.CreateIntrinsic(
610 ID: Intrinsic::powi, Types: {X->getType(), YZ->getType()}, Args: {X, YZ}, FMFSource: &I);
611
612 return NewPow;
613 };
614
615 Value *X, *Y, *Z;
616 unsigned Opcode = I.getOpcode();
617 assert((Opcode == Instruction::FMul || Opcode == Instruction::FDiv) &&
618 "Unexpected opcode");
619
620 // powi(X, Y) * X --> powi(X, Y+1)
621 // X * powi(X, Y) --> powi(X, Y+1)
622 if (match(V: &I, P: m_c_FMul(L: m_OneUse(SubPattern: m_AllowReassoc(SubPattern: m_Intrinsic<Intrinsic::powi>(
623 Op0: m_Value(V&: X), Op1: m_Value(V&: Y)))),
624 R: m_Deferred(V: X)))) {
625 Constant *One = ConstantInt::get(Ty: Y->getType(), V: 1);
626 if (willNotOverflowSignedAdd(LHS: Y, RHS: One, CxtI: I)) {
627 Instruction *NewPow = createPowiExpr(I, *this, X, Y, One);
628 return replaceInstUsesWith(I, V: NewPow);
629 }
630 }
631
632 // powi(x, y) * powi(x, z) -> powi(x, y + z)
633 Value *Op0 = I.getOperand(i_nocapture: 0);
634 Value *Op1 = I.getOperand(i_nocapture: 1);
635 if (Opcode == Instruction::FMul && I.isOnlyUserOfAnyOperand() &&
636 match(V: Op0, P: m_AllowReassoc(
637 SubPattern: m_Intrinsic<Intrinsic::powi>(Op0: m_Value(V&: X), Op1: m_Value(V&: Y)))) &&
638 match(V: Op1, P: m_AllowReassoc(SubPattern: m_Intrinsic<Intrinsic::powi>(Op0: m_Specific(V: X),
639 Op1: m_Value(V&: Z)))) &&
640 Y->getType() == Z->getType()) {
641 Instruction *NewPow = createPowiExpr(I, *this, X, Y, Z);
642 return replaceInstUsesWith(I, V: NewPow);
643 }
644
645 if (Opcode == Instruction::FDiv && I.hasAllowReassoc() && I.hasNoNaNs()) {
646 // powi(X, Y) / X --> powi(X, Y-1)
647 // This is legal when (Y - 1) can't wraparound, in which case reassoc and
648 // nnan are required.
649 // TODO: Multi-use may be also better off creating Powi(x,y-1)
650 if (match(V: Op0, P: m_OneUse(SubPattern: m_AllowReassoc(SubPattern: m_Intrinsic<Intrinsic::powi>(
651 Op0: m_Specific(V: Op1), Op1: m_Value(V&: Y))))) &&
652 willNotOverflowSignedSub(LHS: Y, RHS: ConstantInt::get(Ty: Y->getType(), V: 1), CxtI: I)) {
653 Constant *NegOne = ConstantInt::getAllOnesValue(Ty: Y->getType());
654 Instruction *NewPow = createPowiExpr(I, *this, Op1, Y, NegOne);
655 return replaceInstUsesWith(I, V: NewPow);
656 }
657
658 // powi(X, Y) / (X * Z) --> powi(X, Y-1) / Z
659 // This is legal when (Y - 1) can't wraparound, in which case reassoc and
660 // nnan are required.
661 // TODO: Multi-use may be also better off creating Powi(x,y-1)
662 if (match(V: Op0, P: m_OneUse(SubPattern: m_AllowReassoc(SubPattern: m_Intrinsic<Intrinsic::powi>(
663 Op0: m_Value(V&: X), Op1: m_Value(V&: Y))))) &&
664 match(V: Op1, P: m_AllowReassoc(SubPattern: m_c_FMul(L: m_Specific(V: X), R: m_Value(V&: Z)))) &&
665 willNotOverflowSignedSub(LHS: Y, RHS: ConstantInt::get(Ty: Y->getType(), V: 1), CxtI: I)) {
666 Constant *NegOne = ConstantInt::getAllOnesValue(Ty: Y->getType());
667 auto *NewPow = createPowiExpr(I, *this, X, Y, NegOne);
668 return BinaryOperator::CreateFDivFMF(V1: NewPow, V2: Z, FMFSource: &I);
669 }
670 }
671
672 return nullptr;
673}
674
675Instruction *InstCombinerImpl::foldFMulReassoc(BinaryOperator &I) {
676 Value *Op0 = I.getOperand(i_nocapture: 0);
677 Value *Op1 = I.getOperand(i_nocapture: 1);
678 Value *X, *Y;
679 Constant *C;
680 BinaryOperator *Op0BinOp;
681
682 // Reassociate constant RHS with another constant to form constant
683 // expression.
684 if (match(V: Op1, P: m_Constant(C)) && C->isFiniteNonZeroFP() &&
685 match(V: Op0, P: m_AllowReassoc(SubPattern: m_BinOp(I&: Op0BinOp)))) {
686 // Everything in this scope folds I with Op0, intersecting their FMF.
687 FastMathFlags FMF = I.getFastMathFlags() & Op0BinOp->getFastMathFlags();
688 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
689 Builder.setFastMathFlags(FMF);
690 Constant *C1;
691 if (match(V: Op0, P: m_OneUse(SubPattern: m_FDiv(L: m_Constant(C&: C1), R: m_Value(V&: X))))) {
692 // (C1 / X) * C --> (C * C1) / X
693 Constant *CC1 =
694 ConstantFoldBinaryOpOperands(Opcode: Instruction::FMul, LHS: C, RHS: C1, DL);
695 if (CC1 && CC1->isNormalFP())
696 return BinaryOperator::CreateFDivFMF(V1: CC1, V2: X, FMF);
697 }
698 if (match(V: Op0, P: m_FDiv(L: m_Value(V&: X), R: m_Constant(C&: C1)))) {
699 // FIXME: This seems like it should also be checking for arcp
700 // (X / C1) * C --> X * (C / C1)
701 Constant *CDivC1 =
702 ConstantFoldBinaryOpOperands(Opcode: Instruction::FDiv, LHS: C, RHS: C1, DL);
703 if (CDivC1 && CDivC1->isNormalFP())
704 return BinaryOperator::CreateFMulFMF(V1: X, V2: CDivC1, FMF);
705
706 // If the constant was a denormal, try reassociating differently.
707 // (X / C1) * C --> X / (C1 / C)
708 Constant *C1DivC =
709 ConstantFoldBinaryOpOperands(Opcode: Instruction::FDiv, LHS: C1, RHS: C, DL);
710 if (C1DivC && Op0->hasOneUse() && C1DivC->isNormalFP())
711 return BinaryOperator::CreateFDivFMF(V1: X, V2: C1DivC, FMF);
712 }
713
714 // We do not need to match 'fadd C, X' and 'fsub X, C' because they are
715 // canonicalized to 'fadd X, C'. Distributing the multiply may allow
716 // further folds and (X * C) + C2 is 'fma'.
717 if (match(V: Op0, P: m_OneUse(SubPattern: m_FAdd(L: m_Value(V&: X), R: m_Constant(C&: C1))))) {
718 // (X + C1) * C --> (X * C) + (C * C1)
719 if (Constant *CC1 =
720 ConstantFoldBinaryOpOperands(Opcode: Instruction::FMul, LHS: C, RHS: C1, DL)) {
721 Value *XC = Builder.CreateFMul(L: X, R: C);
722 return BinaryOperator::CreateFAddFMF(V1: XC, V2: CC1, FMF);
723 }
724 }
725 if (match(V: Op0, P: m_OneUse(SubPattern: m_FSub(L: m_Constant(C&: C1), R: m_Value(V&: X))))) {
726 // (C1 - X) * C --> (C * C1) - (X * C)
727 if (Constant *CC1 =
728 ConstantFoldBinaryOpOperands(Opcode: Instruction::FMul, LHS: C, RHS: C1, DL)) {
729 Value *XC = Builder.CreateFMul(L: X, R: C);
730 return BinaryOperator::CreateFSubFMF(V1: CC1, V2: XC, FMF);
731 }
732 }
733 }
734
735 Value *Z;
736 if (match(V: &I,
737 P: m_c_FMul(L: m_AllowReassoc(SubPattern: m_OneUse(SubPattern: m_FDiv(L: m_Value(V&: X), R: m_Value(V&: Y)))),
738 R: m_Value(V&: Z)))) {
739 BinaryOperator *DivOp = cast<BinaryOperator>(Val: ((Z == Op0) ? Op1 : Op0));
740 FastMathFlags FMF = I.getFastMathFlags() & DivOp->getFastMathFlags();
741 if (FMF.allowReassoc()) {
742 // Sink division: (X / Y) * Z --> (X * Z) / Y
743 IRBuilder<>::FastMathFlagGuard FMFGuard(Builder);
744 Builder.setFastMathFlags(FMF);
745 auto *NewFMul = Builder.CreateFMul(L: X, R: Z);
746 return BinaryOperator::CreateFDivFMF(V1: NewFMul, V2: Y, FMF);
747 }
748 }
749
750 // sqrt(X) * sqrt(Y) -> sqrt(X * Y)
751 // nnan disallows the possibility of returning a number if both operands are
752 // negative (in that case, we should return NaN).
753 if (I.hasNoNaNs() && match(V: Op0, P: m_OneUse(SubPattern: m_Sqrt(Op0: m_Value(V&: X)))) &&
754 match(V: Op1, P: m_OneUse(SubPattern: m_Sqrt(Op0: m_Value(V&: Y))))) {
755 Value *XY = Builder.CreateFMulFMF(L: X, R: Y, FMFSource: &I);
756 Value *Sqrt = Builder.CreateUnaryIntrinsic(ID: Intrinsic::sqrt, V: XY, FMFSource: &I);
757 return replaceInstUsesWith(I, V: Sqrt);
758 }
759
760 // The following transforms are done irrespective of the number of uses
761 // for the expression "1.0/sqrt(X)".
762 // 1) 1.0/sqrt(X) * X -> X/sqrt(X)
763 // 2) X * 1.0/sqrt(X) -> X/sqrt(X)
764 // We always expect the backend to reduce X/sqrt(X) to sqrt(X), if it
765 // has the necessary (reassoc) fast-math-flags.
766 if (I.hasNoSignedZeros() &&
767 match(V: Op0, P: (m_FDiv(L: m_SpecificFP(V: 1.0), R: m_Value(V&: Y)))) &&
768 match(V: Y, P: m_Sqrt(Op0: m_Value(V&: X))) && Op1 == X)
769 return BinaryOperator::CreateFDivFMF(V1: X, V2: Y, FMFSource: &I);
770 if (I.hasNoSignedZeros() &&
771 match(V: Op1, P: (m_FDiv(L: m_SpecificFP(V: 1.0), R: m_Value(V&: Y)))) &&
772 match(V: Y, P: m_Sqrt(Op0: m_Value(V&: X))) && Op0 == X)
773 return BinaryOperator::CreateFDivFMF(V1: X, V2: Y, FMFSource: &I);
774
775 // Like the similar transform in instsimplify, this requires 'nsz' because
776 // sqrt(-0.0) = -0.0, and -0.0 * -0.0 does not simplify to -0.0.
777 if (I.hasNoNaNs() && I.hasNoSignedZeros() && Op0 == Op1 && Op0->hasNUses(N: 2)) {
778 // Peek through fdiv to find squaring of square root:
779 // (X / sqrt(Y)) * (X / sqrt(Y)) --> (X * X) / Y
780 if (match(V: Op0, P: m_FDiv(L: m_Value(V&: X), R: m_Sqrt(Op0: m_Value(V&: Y))))) {
781 Value *XX = Builder.CreateFMulFMF(L: X, R: X, FMFSource: &I);
782 return BinaryOperator::CreateFDivFMF(V1: XX, V2: Y, FMFSource: &I);
783 }
784 // (sqrt(Y) / X) * (sqrt(Y) / X) --> Y / (X * X)
785 if (match(V: Op0, P: m_FDiv(L: m_Sqrt(Op0: m_Value(V&: Y)), R: m_Value(V&: X)))) {
786 Value *XX = Builder.CreateFMulFMF(L: X, R: X, FMFSource: &I);
787 return BinaryOperator::CreateFDivFMF(V1: Y, V2: XX, FMFSource: &I);
788 }
789 }
790
791 // pow(X, Y) * X --> pow(X, Y+1)
792 // X * pow(X, Y) --> pow(X, Y+1)
793 if (match(V: &I, P: m_c_FMul(L: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::pow>(Op0: m_Value(V&: X),
794 Op1: m_Value(V&: Y))),
795 R: m_Deferred(V: X)))) {
796 Value *Y1 = Builder.CreateFAddFMF(L: Y, R: ConstantFP::get(Ty: I.getType(), V: 1.0), FMFSource: &I);
797 Value *Pow = Builder.CreateBinaryIntrinsic(ID: Intrinsic::pow, LHS: X, RHS: Y1, FMFSource: &I);
798 return replaceInstUsesWith(I, V: Pow);
799 }
800
801 if (Instruction *FoldedPowi = foldPowiReassoc(I))
802 return FoldedPowi;
803
804 if (I.isOnlyUserOfAnyOperand()) {
805 // pow(X, Y) * pow(X, Z) -> pow(X, Y + Z)
806 if (match(V: Op0, P: m_Intrinsic<Intrinsic::pow>(Op0: m_Value(V&: X), Op1: m_Value(V&: Y))) &&
807 match(V: Op1, P: m_Intrinsic<Intrinsic::pow>(Op0: m_Specific(V: X), Op1: m_Value(V&: Z)))) {
808 auto *YZ = Builder.CreateFAddFMF(L: Y, R: Z, FMFSource: &I);
809 auto *NewPow = Builder.CreateBinaryIntrinsic(ID: Intrinsic::pow, LHS: X, RHS: YZ, FMFSource: &I);
810 return replaceInstUsesWith(I, V: NewPow);
811 }
812 // pow(X, Y) * pow(Z, Y) -> pow(X * Z, Y)
813 if (match(V: Op0, P: m_Intrinsic<Intrinsic::pow>(Op0: m_Value(V&: X), Op1: m_Value(V&: Y))) &&
814 match(V: Op1, P: m_Intrinsic<Intrinsic::pow>(Op0: m_Value(V&: Z), Op1: m_Specific(V: Y)))) {
815 auto *XZ = Builder.CreateFMulFMF(L: X, R: Z, FMFSource: &I);
816 auto *NewPow = Builder.CreateBinaryIntrinsic(ID: Intrinsic::pow, LHS: XZ, RHS: Y, FMFSource: &I);
817 return replaceInstUsesWith(I, V: NewPow);
818 }
819
820 // exp(X) * exp(Y) -> exp(X + Y)
821 if (match(V: Op0, P: m_Intrinsic<Intrinsic::exp>(Op0: m_Value(V&: X))) &&
822 match(V: Op1, P: m_Intrinsic<Intrinsic::exp>(Op0: m_Value(V&: Y)))) {
823 Value *XY = Builder.CreateFAddFMF(L: X, R: Y, FMFSource: &I);
824 Value *Exp = Builder.CreateUnaryIntrinsic(ID: Intrinsic::exp, V: XY, FMFSource: &I);
825 return replaceInstUsesWith(I, V: Exp);
826 }
827
828 // exp2(X) * exp2(Y) -> exp2(X + Y)
829 if (match(V: Op0, P: m_Intrinsic<Intrinsic::exp2>(Op0: m_Value(V&: X))) &&
830 match(V: Op1, P: m_Intrinsic<Intrinsic::exp2>(Op0: m_Value(V&: Y)))) {
831 Value *XY = Builder.CreateFAddFMF(L: X, R: Y, FMFSource: &I);
832 Value *Exp2 = Builder.CreateUnaryIntrinsic(ID: Intrinsic::exp2, V: XY, FMFSource: &I);
833 return replaceInstUsesWith(I, V: Exp2);
834 }
835 }
836
837 // (X*Y) * X => (X*X) * Y where Y != X
838 // The purpose is two-fold:
839 // 1) to form a power expression (of X).
840 // 2) potentially shorten the critical path: After transformation, the
841 // latency of the instruction Y is amortized by the expression of X*X,
842 // and therefore Y is in a "less critical" position compared to what it
843 // was before the transformation.
844 if (match(V: Op0, P: m_OneUse(SubPattern: m_c_FMul(L: m_Specific(V: Op1), R: m_Value(V&: Y)))) && Op1 != Y) {
845 Value *XX = Builder.CreateFMulFMF(L: Op1, R: Op1, FMFSource: &I);
846 return BinaryOperator::CreateFMulFMF(V1: XX, V2: Y, FMFSource: &I);
847 }
848 if (match(V: Op1, P: m_OneUse(SubPattern: m_c_FMul(L: m_Specific(V: Op0), R: m_Value(V&: Y)))) && Op0 != Y) {
849 Value *XX = Builder.CreateFMulFMF(L: Op0, R: Op0, FMFSource: &I);
850 return BinaryOperator::CreateFMulFMF(V1: XX, V2: Y, FMFSource: &I);
851 }
852
853 return nullptr;
854}
855
856Instruction *InstCombinerImpl::visitFMul(BinaryOperator &I) {
857 if (Value *V = simplifyFMulInst(LHS: I.getOperand(i_nocapture: 0), RHS: I.getOperand(i_nocapture: 1),
858 FMF: I.getFastMathFlags(),
859 Q: SQ.getWithInstruction(I: &I)))
860 return replaceInstUsesWith(I, V);
861
862 if (SimplifyAssociativeOrCommutative(I))
863 return &I;
864
865 if (Instruction *X = foldVectorBinop(Inst&: I))
866 return X;
867
868 if (Instruction *Phi = foldBinopWithPhiOperands(BO&: I))
869 return Phi;
870
871 if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
872 return FoldedMul;
873
874 if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
875 return replaceInstUsesWith(I, V: FoldedMul);
876
877 if (Instruction *R = foldFPSignBitOps(I))
878 return R;
879
880 if (Instruction *R = foldFBinOpOfIntCasts(I))
881 return R;
882
883 // X * -1.0 --> -X
884 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
885 if (match(V: Op1, P: m_SpecificFP(V: -1.0)))
886 return UnaryOperator::CreateFNegFMF(Op: Op0, FMFSource: &I);
887
888 // With no-nans/no-infs:
889 // X * 0.0 --> copysign(0.0, X)
890 // X * -0.0 --> copysign(0.0, -X)
891 const APFloat *FPC;
892 if (match(V: Op1, P: m_APFloatAllowPoison(Res&: FPC)) && FPC->isZero() &&
893 ((I.hasNoInfs() &&
894 isKnownNeverNaN(V: Op0, /*Depth=*/0, SQ: SQ.getWithInstruction(I: &I))) ||
895 isKnownNeverNaN(V: &I, /*Depth=*/0, SQ: SQ.getWithInstruction(I: &I)))) {
896 if (FPC->isNegative())
897 Op0 = Builder.CreateFNegFMF(V: Op0, FMFSource: &I);
898 CallInst *CopySign = Builder.CreateIntrinsic(ID: Intrinsic::copysign,
899 Types: {I.getType()}, Args: {Op1, Op0}, FMFSource: &I);
900 return replaceInstUsesWith(I, V: CopySign);
901 }
902
903 // -X * C --> X * -C
904 Value *X, *Y;
905 Constant *C;
906 if (match(V: Op0, P: m_FNeg(X: m_Value(V&: X))) && match(V: Op1, P: m_Constant(C)))
907 if (Constant *NegC = ConstantFoldUnaryOpOperand(Opcode: Instruction::FNeg, Op: C, DL))
908 return BinaryOperator::CreateFMulFMF(V1: X, V2: NegC, FMFSource: &I);
909
910 if (I.hasNoNaNs() && I.hasNoSignedZeros()) {
911 // (uitofp bool X) * Y --> X ? Y : 0
912 // Y * (uitofp bool X) --> X ? Y : 0
913 // Note INF * 0 is NaN.
914 if (match(V: Op0, P: m_UIToFP(Op: m_Value(V&: X))) &&
915 X->getType()->isIntOrIntVectorTy(BitWidth: 1)) {
916 auto *SI = SelectInst::Create(C: X, S1: Op1, S2: ConstantFP::get(Ty: I.getType(), V: 0.0));
917 SI->copyFastMathFlags(FMF: I.getFastMathFlags());
918 return SI;
919 }
920 if (match(V: Op1, P: m_UIToFP(Op: m_Value(V&: X))) &&
921 X->getType()->isIntOrIntVectorTy(BitWidth: 1)) {
922 auto *SI = SelectInst::Create(C: X, S1: Op0, S2: ConstantFP::get(Ty: I.getType(), V: 0.0));
923 SI->copyFastMathFlags(FMF: I.getFastMathFlags());
924 return SI;
925 }
926 }
927
928 // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E)
929 if (Value *V = SimplifySelectsFeedingBinaryOp(I, LHS: Op0, RHS: Op1))
930 return replaceInstUsesWith(I, V);
931
932 if (I.hasAllowReassoc())
933 if (Instruction *FoldedMul = foldFMulReassoc(I))
934 return FoldedMul;
935
936 // log2(X * 0.5) * Y = log2(X) * Y - Y
937 if (I.isFast()) {
938 IntrinsicInst *Log2 = nullptr;
939 if (match(V: Op0, P: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::log2>(
940 Op0: m_OneUse(SubPattern: m_FMul(L: m_Value(V&: X), R: m_SpecificFP(V: 0.5))))))) {
941 Log2 = cast<IntrinsicInst>(Val: Op0);
942 Y = Op1;
943 }
944 if (match(V: Op1, P: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::log2>(
945 Op0: m_OneUse(SubPattern: m_FMul(L: m_Value(V&: X), R: m_SpecificFP(V: 0.5))))))) {
946 Log2 = cast<IntrinsicInst>(Val: Op1);
947 Y = Op0;
948 }
949 if (Log2) {
950 Value *Log2 = Builder.CreateUnaryIntrinsic(ID: Intrinsic::log2, V: X, FMFSource: &I);
951 Value *LogXTimesY = Builder.CreateFMulFMF(L: Log2, R: Y, FMFSource: &I);
952 return BinaryOperator::CreateFSubFMF(V1: LogXTimesY, V2: Y, FMFSource: &I);
953 }
954 }
955
956 // Simplify FMUL recurrences starting with 0.0 to 0.0 if nnan and nsz are set.
957 // Given a phi node with entry value as 0 and it used in fmul operation,
958 // we can replace fmul with 0 safely and eleminate loop operation.
959 PHINode *PN = nullptr;
960 Value *Start = nullptr, *Step = nullptr;
961 if (matchSimpleRecurrence(I: &I, P&: PN, Start, Step) && I.hasNoNaNs() &&
962 I.hasNoSignedZeros() && match(V: Start, P: m_Zero()))
963 return replaceInstUsesWith(I, V: Start);
964
965 // minimum(X, Y) * maximum(X, Y) => X * Y.
966 if (match(V: &I,
967 P: m_c_FMul(L: m_Intrinsic<Intrinsic::maximum>(Op0: m_Value(V&: X), Op1: m_Value(V&: Y)),
968 R: m_c_Intrinsic<Intrinsic::minimum>(Op0: m_Deferred(V: X),
969 Op1: m_Deferred(V: Y))))) {
970 BinaryOperator *Result = BinaryOperator::CreateFMulFMF(V1: X, V2: Y, FMFSource: &I);
971 // We cannot preserve ninf if nnan flag is not set.
972 // If X is NaN and Y is Inf then in original program we had NaN * NaN,
973 // while in optimized version NaN * Inf and this is a poison with ninf flag.
974 if (!Result->hasNoNaNs())
975 Result->setHasNoInfs(false);
976 return Result;
977 }
978
979 return nullptr;
980}
981
982/// Fold a divide or remainder with a select instruction divisor when one of the
983/// select operands is zero. In that case, we can use the other select operand
984/// because div/rem by zero is undefined.
985bool InstCombinerImpl::simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I) {
986 SelectInst *SI = dyn_cast<SelectInst>(Val: I.getOperand(i_nocapture: 1));
987 if (!SI)
988 return false;
989
990 int NonNullOperand;
991 if (match(V: SI->getTrueValue(), P: m_Zero()))
992 // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
993 NonNullOperand = 2;
994 else if (match(V: SI->getFalseValue(), P: m_Zero()))
995 // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
996 NonNullOperand = 1;
997 else
998 return false;
999
1000 // Change the div/rem to use 'Y' instead of the select.
1001 replaceOperand(I, OpNum: 1, V: SI->getOperand(i_nocapture: NonNullOperand));
1002
1003 // Okay, we know we replace the operand of the div/rem with 'Y' with no
1004 // problem. However, the select, or the condition of the select may have
1005 // multiple uses. Based on our knowledge that the operand must be non-zero,
1006 // propagate the known value for the select into other uses of it, and
1007 // propagate a known value of the condition into its other users.
1008
1009 // If the select and condition only have a single use, don't bother with this,
1010 // early exit.
1011 Value *SelectCond = SI->getCondition();
1012 if (SI->use_empty() && SelectCond->hasOneUse())
1013 return true;
1014
1015 // Scan the current block backward, looking for other uses of SI.
1016 BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin();
1017 Type *CondTy = SelectCond->getType();
1018 while (BBI != BBFront) {
1019 --BBI;
1020 // If we found an instruction that we can't assume will return, so
1021 // information from below it cannot be propagated above it.
1022 if (!isGuaranteedToTransferExecutionToSuccessor(I: &*BBI))
1023 break;
1024
1025 // Replace uses of the select or its condition with the known values.
1026 for (Use &Op : BBI->operands()) {
1027 if (Op == SI) {
1028 replaceUse(U&: Op, NewValue: SI->getOperand(i_nocapture: NonNullOperand));
1029 Worklist.push(I: &*BBI);
1030 } else if (Op == SelectCond) {
1031 replaceUse(U&: Op, NewValue: NonNullOperand == 1 ? ConstantInt::getTrue(Ty: CondTy)
1032 : ConstantInt::getFalse(Ty: CondTy));
1033 Worklist.push(I: &*BBI);
1034 }
1035 }
1036
1037 // If we past the instruction, quit looking for it.
1038 if (&*BBI == SI)
1039 SI = nullptr;
1040 if (&*BBI == SelectCond)
1041 SelectCond = nullptr;
1042
1043 // If we ran out of things to eliminate, break out of the loop.
1044 if (!SelectCond && !SI)
1045 break;
1046
1047 }
1048 return true;
1049}
1050
1051/// True if the multiply can not be expressed in an int this size.
1052static bool multiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
1053 bool IsSigned) {
1054 bool Overflow;
1055 Product = IsSigned ? C1.smul_ov(RHS: C2, Overflow) : C1.umul_ov(RHS: C2, Overflow);
1056 return Overflow;
1057}
1058
1059/// True if C1 is a multiple of C2. Quotient contains C1/C2.
1060static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
1061 bool IsSigned) {
1062 assert(C1.getBitWidth() == C2.getBitWidth() && "Constant widths not equal");
1063
1064 // Bail if we will divide by zero.
1065 if (C2.isZero())
1066 return false;
1067
1068 // Bail if we would divide INT_MIN by -1.
1069 if (IsSigned && C1.isMinSignedValue() && C2.isAllOnes())
1070 return false;
1071
1072 APInt Remainder(C1.getBitWidth(), /*val=*/0ULL, IsSigned);
1073 if (IsSigned)
1074 APInt::sdivrem(LHS: C1, RHS: C2, Quotient, Remainder);
1075 else
1076 APInt::udivrem(LHS: C1, RHS: C2, Quotient, Remainder);
1077
1078 return Remainder.isMinValue();
1079}
1080
1081static Value *foldIDivShl(BinaryOperator &I, InstCombiner::BuilderTy &Builder) {
1082 assert((I.getOpcode() == Instruction::SDiv ||
1083 I.getOpcode() == Instruction::UDiv) &&
1084 "Expected integer divide");
1085
1086 bool IsSigned = I.getOpcode() == Instruction::SDiv;
1087 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
1088 Type *Ty = I.getType();
1089
1090 Value *X, *Y, *Z;
1091
1092 // With appropriate no-wrap constraints, remove a common factor in the
1093 // dividend and divisor that is disguised as a left-shifted value.
1094 if (match(V: Op1, P: m_Shl(L: m_Value(V&: X), R: m_Value(V&: Z))) &&
1095 match(V: Op0, P: m_c_Mul(L: m_Specific(V: X), R: m_Value(V&: Y)))) {
1096 // Both operands must have the matching no-wrap for this kind of division.
1097 auto *Mul = cast<OverflowingBinaryOperator>(Val: Op0);
1098 auto *Shl = cast<OverflowingBinaryOperator>(Val: Op1);
1099 bool HasNUW = Mul->hasNoUnsignedWrap() && Shl->hasNoUnsignedWrap();
1100 bool HasNSW = Mul->hasNoSignedWrap() && Shl->hasNoSignedWrap();
1101
1102 // (X * Y) u/ (X << Z) --> Y u>> Z
1103 if (!IsSigned && HasNUW)
1104 return Builder.CreateLShr(LHS: Y, RHS: Z, Name: "", isExact: I.isExact());
1105
1106 // (X * Y) s/ (X << Z) --> Y s/ (1 << Z)
1107 if (IsSigned && HasNSW && (Op0->hasOneUse() || Op1->hasOneUse())) {
1108 Value *Shl = Builder.CreateShl(LHS: ConstantInt::get(Ty, V: 1), RHS: Z);
1109 return Builder.CreateSDiv(LHS: Y, RHS: Shl, Name: "", isExact: I.isExact());
1110 }
1111 }
1112
1113 // With appropriate no-wrap constraints, remove a common factor in the
1114 // dividend and divisor that is disguised as a left-shift amount.
1115 if (match(V: Op0, P: m_Shl(L: m_Value(V&: X), R: m_Value(V&: Z))) &&
1116 match(V: Op1, P: m_Shl(L: m_Value(V&: Y), R: m_Specific(V: Z)))) {
1117 auto *Shl0 = cast<OverflowingBinaryOperator>(Val: Op0);
1118 auto *Shl1 = cast<OverflowingBinaryOperator>(Val: Op1);
1119
1120 // For unsigned div, we need 'nuw' on both shifts or
1121 // 'nsw' on both shifts + 'nuw' on the dividend.
1122 // (X << Z) / (Y << Z) --> X / Y
1123 if (!IsSigned &&
1124 ((Shl0->hasNoUnsignedWrap() && Shl1->hasNoUnsignedWrap()) ||
1125 (Shl0->hasNoUnsignedWrap() && Shl0->hasNoSignedWrap() &&
1126 Shl1->hasNoSignedWrap())))
1127 return Builder.CreateUDiv(LHS: X, RHS: Y, Name: "", isExact: I.isExact());
1128
1129 // For signed div, we need 'nsw' on both shifts + 'nuw' on the divisor.
1130 // (X << Z) / (Y << Z) --> X / Y
1131 if (IsSigned && Shl0->hasNoSignedWrap() && Shl1->hasNoSignedWrap() &&
1132 Shl1->hasNoUnsignedWrap())
1133 return Builder.CreateSDiv(LHS: X, RHS: Y, Name: "", isExact: I.isExact());
1134 }
1135
1136 // If X << Y and X << Z does not overflow, then:
1137 // (X << Y) / (X << Z) -> (1 << Y) / (1 << Z) -> 1 << Y >> Z
1138 if (match(V: Op0, P: m_Shl(L: m_Value(V&: X), R: m_Value(V&: Y))) &&
1139 match(V: Op1, P: m_Shl(L: m_Specific(V: X), R: m_Value(V&: Z)))) {
1140 auto *Shl0 = cast<OverflowingBinaryOperator>(Val: Op0);
1141 auto *Shl1 = cast<OverflowingBinaryOperator>(Val: Op1);
1142
1143 if (IsSigned ? (Shl0->hasNoSignedWrap() && Shl1->hasNoSignedWrap())
1144 : (Shl0->hasNoUnsignedWrap() && Shl1->hasNoUnsignedWrap())) {
1145 Constant *One = ConstantInt::get(Ty: X->getType(), V: 1);
1146 // Only preserve the nsw flag if dividend has nsw
1147 // or divisor has nsw and operator is sdiv.
1148 Value *Dividend = Builder.CreateShl(
1149 LHS: One, RHS: Y, Name: "shl.dividend",
1150 /*HasNUW*/ true,
1151 /*HasNSW*/
1152 IsSigned ? (Shl0->hasNoUnsignedWrap() || Shl1->hasNoUnsignedWrap())
1153 : Shl0->hasNoSignedWrap());
1154 return Builder.CreateLShr(LHS: Dividend, RHS: Z, Name: "", isExact: I.isExact());
1155 }
1156 }
1157
1158 return nullptr;
1159}
1160
1161/// This function implements the transforms common to both integer division
1162/// instructions (udiv and sdiv). It is called by the visitors to those integer
1163/// division instructions.
1164/// Common integer divide transforms
1165Instruction *InstCombinerImpl::commonIDivTransforms(BinaryOperator &I) {
1166 if (Instruction *Phi = foldBinopWithPhiOperands(BO&: I))
1167 return Phi;
1168
1169 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
1170 bool IsSigned = I.getOpcode() == Instruction::SDiv;
1171 Type *Ty = I.getType();
1172
1173 // The RHS is known non-zero.
1174 if (Value *V = simplifyValueKnownNonZero(V: I.getOperand(i_nocapture: 1), IC&: *this, CxtI&: I))
1175 return replaceOperand(I, OpNum: 1, V);
1176
1177 // Handle cases involving: [su]div X, (select Cond, Y, Z)
1178 // This does not apply for fdiv.
1179 if (simplifyDivRemOfSelectWithZeroOp(I))
1180 return &I;
1181
1182 // If the divisor is a select-of-constants, try to constant fold all div ops:
1183 // C / (select Cond, TrueC, FalseC) --> select Cond, (C / TrueC), (C / FalseC)
1184 // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
1185 if (match(V: Op0, P: m_ImmConstant()) &&
1186 match(V: Op1, P: m_Select(C: m_Value(), L: m_ImmConstant(), R: m_ImmConstant()))) {
1187 if (Instruction *R = FoldOpIntoSelect(Op&: I, SI: cast<SelectInst>(Val: Op1),
1188 /*FoldWithMultiUse*/ true))
1189 return R;
1190 }
1191
1192 const APInt *C2;
1193 if (match(V: Op1, P: m_APInt(Res&: C2))) {
1194 Value *X;
1195 const APInt *C1;
1196
1197 // (X / C1) / C2 -> X / (C1*C2)
1198 if ((IsSigned && match(V: Op0, P: m_SDiv(L: m_Value(V&: X), R: m_APInt(Res&: C1)))) ||
1199 (!IsSigned && match(V: Op0, P: m_UDiv(L: m_Value(V&: X), R: m_APInt(Res&: C1))))) {
1200 APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
1201 if (!multiplyOverflows(C1: *C1, C2: *C2, Product, IsSigned))
1202 return BinaryOperator::Create(Op: I.getOpcode(), S1: X,
1203 S2: ConstantInt::get(Ty, V: Product));
1204 }
1205
1206 APInt Quotient(C2->getBitWidth(), /*val=*/0ULL, IsSigned);
1207 if ((IsSigned && match(V: Op0, P: m_NSWMul(L: m_Value(V&: X), R: m_APInt(Res&: C1)))) ||
1208 (!IsSigned && match(V: Op0, P: m_NUWMul(L: m_Value(V&: X), R: m_APInt(Res&: C1))))) {
1209
1210 // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
1211 if (isMultiple(C1: *C2, C2: *C1, Quotient, IsSigned)) {
1212 auto *NewDiv = BinaryOperator::Create(Op: I.getOpcode(), S1: X,
1213 S2: ConstantInt::get(Ty, V: Quotient));
1214 NewDiv->setIsExact(I.isExact());
1215 return NewDiv;
1216 }
1217
1218 // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
1219 if (isMultiple(C1: *C1, C2: *C2, Quotient, IsSigned)) {
1220 auto *Mul = BinaryOperator::Create(Op: Instruction::Mul, S1: X,
1221 S2: ConstantInt::get(Ty, V: Quotient));
1222 auto *OBO = cast<OverflowingBinaryOperator>(Val: Op0);
1223 Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
1224 Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
1225 return Mul;
1226 }
1227 }
1228
1229 if ((IsSigned && match(V: Op0, P: m_NSWShl(L: m_Value(V&: X), R: m_APInt(Res&: C1))) &&
1230 C1->ult(RHS: C1->getBitWidth() - 1)) ||
1231 (!IsSigned && match(V: Op0, P: m_NUWShl(L: m_Value(V&: X), R: m_APInt(Res&: C1))) &&
1232 C1->ult(RHS: C1->getBitWidth()))) {
1233 APInt C1Shifted = APInt::getOneBitSet(
1234 numBits: C1->getBitWidth(), BitNo: static_cast<unsigned>(C1->getZExtValue()));
1235
1236 // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of 1 << C1.
1237 if (isMultiple(C1: *C2, C2: C1Shifted, Quotient, IsSigned)) {
1238 auto *BO = BinaryOperator::Create(Op: I.getOpcode(), S1: X,
1239 S2: ConstantInt::get(Ty, V: Quotient));
1240 BO->setIsExact(I.isExact());
1241 return BO;
1242 }
1243
1244 // (X << C1) / C2 -> X * ((1 << C1) / C2) if 1 << C1 is a multiple of C2.
1245 if (isMultiple(C1: C1Shifted, C2: *C2, Quotient, IsSigned)) {
1246 auto *Mul = BinaryOperator::Create(Op: Instruction::Mul, S1: X,
1247 S2: ConstantInt::get(Ty, V: Quotient));
1248 auto *OBO = cast<OverflowingBinaryOperator>(Val: Op0);
1249 Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
1250 Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
1251 return Mul;
1252 }
1253 }
1254
1255 // Distribute div over add to eliminate a matching div/mul pair:
1256 // ((X * C2) + C1) / C2 --> X + C1/C2
1257 // We need a multiple of the divisor for a signed add constant, but
1258 // unsigned is fine with any constant pair.
1259 if (IsSigned &&
1260 match(V: Op0, P: m_NSWAddLike(L: m_NSWMul(L: m_Value(V&: X), R: m_SpecificInt(V: *C2)),
1261 R: m_APInt(Res&: C1))) &&
1262 isMultiple(C1: *C1, C2: *C2, Quotient, IsSigned)) {
1263 return BinaryOperator::CreateNSWAdd(V1: X, V2: ConstantInt::get(Ty, V: Quotient));
1264 }
1265 if (!IsSigned &&
1266 match(V: Op0, P: m_NUWAddLike(L: m_NUWMul(L: m_Value(V&: X), R: m_SpecificInt(V: *C2)),
1267 R: m_APInt(Res&: C1)))) {
1268 return BinaryOperator::CreateNUWAdd(V1: X,
1269 V2: ConstantInt::get(Ty, V: C1->udiv(RHS: *C2)));
1270 }
1271
1272 if (!C2->isZero()) // avoid X udiv 0
1273 if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I))
1274 return FoldedDiv;
1275 }
1276
1277 if (match(V: Op0, P: m_One())) {
1278 assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?");
1279 if (IsSigned) {
1280 // 1 / 0 --> undef ; 1 / 1 --> 1 ; 1 / -1 --> -1 ; 1 / anything else --> 0
1281 // (Op1 + 1) u< 3 ? Op1 : 0
1282 // Op1 must be frozen because we are increasing its number of uses.
1283 Value *F1 = Op1;
1284 if (!isGuaranteedNotToBeUndef(V: Op1))
1285 F1 = Builder.CreateFreeze(V: Op1, Name: Op1->getName() + ".fr");
1286 Value *Inc = Builder.CreateAdd(LHS: F1, RHS: Op0);
1287 Value *Cmp = Builder.CreateICmpULT(LHS: Inc, RHS: ConstantInt::get(Ty, V: 3));
1288 return SelectInst::Create(C: Cmp, S1: F1, S2: ConstantInt::get(Ty, V: 0));
1289 } else {
1290 // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
1291 // result is one, otherwise it's zero.
1292 return new ZExtInst(Builder.CreateICmpEQ(LHS: Op1, RHS: Op0), Ty);
1293 }
1294 }
1295
1296 // See if we can fold away this div instruction.
1297 if (SimplifyDemandedInstructionBits(Inst&: I))
1298 return &I;
1299
1300 // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
1301 Value *X, *Z;
1302 if (match(V: Op0, P: m_Sub(L: m_Value(V&: X), R: m_Value(V&: Z)))) // (X - Z) / Y; Y = Op1
1303 if ((IsSigned && match(V: Z, P: m_SRem(L: m_Specific(V: X), R: m_Specific(V: Op1)))) ||
1304 (!IsSigned && match(V: Z, P: m_URem(L: m_Specific(V: X), R: m_Specific(V: Op1)))))
1305 return BinaryOperator::Create(Op: I.getOpcode(), S1: X, S2: Op1);
1306
1307 // (X << Y) / X -> 1 << Y
1308 Value *Y;
1309 if (IsSigned && match(V: Op0, P: m_NSWShl(L: m_Specific(V: Op1), R: m_Value(V&: Y))))
1310 return BinaryOperator::CreateNSWShl(V1: ConstantInt::get(Ty, V: 1), V2: Y);
1311 if (!IsSigned && match(V: Op0, P: m_NUWShl(L: m_Specific(V: Op1), R: m_Value(V&: Y))))
1312 return BinaryOperator::CreateNUWShl(V1: ConstantInt::get(Ty, V: 1), V2: Y);
1313
1314 // X / (X * Y) -> 1 / Y if the multiplication does not overflow.
1315 if (match(V: Op1, P: m_c_Mul(L: m_Specific(V: Op0), R: m_Value(V&: Y)))) {
1316 bool HasNSW = cast<OverflowingBinaryOperator>(Val: Op1)->hasNoSignedWrap();
1317 bool HasNUW = cast<OverflowingBinaryOperator>(Val: Op1)->hasNoUnsignedWrap();
1318 if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) {
1319 replaceOperand(I, OpNum: 0, V: ConstantInt::get(Ty, V: 1));
1320 replaceOperand(I, OpNum: 1, V: Y);
1321 return &I;
1322 }
1323 }
1324
1325 // (X << Z) / (X * Y) -> (1 << Z) / Y
1326 // TODO: Handle sdiv.
1327 if (!IsSigned && Op1->hasOneUse() &&
1328 match(V: Op0, P: m_NUWShl(L: m_Value(V&: X), R: m_Value(V&: Z))) &&
1329 match(V: Op1, P: m_c_Mul(L: m_Specific(V: X), R: m_Value(V&: Y))))
1330 if (cast<OverflowingBinaryOperator>(Val: Op1)->hasNoUnsignedWrap()) {
1331 Instruction *NewDiv = BinaryOperator::CreateUDiv(
1332 V1: Builder.CreateShl(LHS: ConstantInt::get(Ty, V: 1), RHS: Z, Name: "", /*NUW*/ HasNUW: true), V2: Y);
1333 NewDiv->setIsExact(I.isExact());
1334 return NewDiv;
1335 }
1336
1337 if (Value *R = foldIDivShl(I, Builder))
1338 return replaceInstUsesWith(I, V: R);
1339
1340 // With the appropriate no-wrap constraint, remove a multiply by the divisor
1341 // after peeking through another divide:
1342 // ((Op1 * X) / Y) / Op1 --> X / Y
1343 if (match(V: Op0, P: m_BinOp(Opcode: I.getOpcode(), L: m_c_Mul(L: m_Specific(V: Op1), R: m_Value(V&: X)),
1344 R: m_Value(V&: Y)))) {
1345 auto *InnerDiv = cast<PossiblyExactOperator>(Val: Op0);
1346 auto *Mul = cast<OverflowingBinaryOperator>(Val: InnerDiv->getOperand(i_nocapture: 0));
1347 Instruction *NewDiv = nullptr;
1348 if (!IsSigned && Mul->hasNoUnsignedWrap())
1349 NewDiv = BinaryOperator::CreateUDiv(V1: X, V2: Y);
1350 else if (IsSigned && Mul->hasNoSignedWrap())
1351 NewDiv = BinaryOperator::CreateSDiv(V1: X, V2: Y);
1352
1353 // Exact propagates only if both of the original divides are exact.
1354 if (NewDiv) {
1355 NewDiv->setIsExact(I.isExact() && InnerDiv->isExact());
1356 return NewDiv;
1357 }
1358 }
1359
1360 // (X * Y) / (X * Z) --> Y / Z (and commuted variants)
1361 if (match(V: Op0, P: m_Mul(L: m_Value(V&: X), R: m_Value(V&: Y)))) {
1362 auto OB0HasNSW = cast<OverflowingBinaryOperator>(Val: Op0)->hasNoSignedWrap();
1363 auto OB0HasNUW = cast<OverflowingBinaryOperator>(Val: Op0)->hasNoUnsignedWrap();
1364
1365 auto CreateDivOrNull = [&](Value *A, Value *B) -> Instruction * {
1366 auto OB1HasNSW = cast<OverflowingBinaryOperator>(Val: Op1)->hasNoSignedWrap();
1367 auto OB1HasNUW =
1368 cast<OverflowingBinaryOperator>(Val: Op1)->hasNoUnsignedWrap();
1369 const APInt *C1, *C2;
1370 if (IsSigned && OB0HasNSW) {
1371 if (OB1HasNSW && match(V: B, P: m_APInt(Res&: C1)) && !C1->isAllOnes())
1372 return BinaryOperator::CreateSDiv(V1: A, V2: B);
1373 }
1374 if (!IsSigned && OB0HasNUW) {
1375 if (OB1HasNUW)
1376 return BinaryOperator::CreateUDiv(V1: A, V2: B);
1377 if (match(V: A, P: m_APInt(Res&: C1)) && match(V: B, P: m_APInt(Res&: C2)) && C2->ule(RHS: *C1))
1378 return BinaryOperator::CreateUDiv(V1: A, V2: B);
1379 }
1380 return nullptr;
1381 };
1382
1383 if (match(V: Op1, P: m_c_Mul(L: m_Specific(V: X), R: m_Value(V&: Z)))) {
1384 if (auto *Val = CreateDivOrNull(Y, Z))
1385 return Val;
1386 }
1387 if (match(V: Op1, P: m_c_Mul(L: m_Specific(V: Y), R: m_Value(V&: Z)))) {
1388 if (auto *Val = CreateDivOrNull(X, Z))
1389 return Val;
1390 }
1391 }
1392 return nullptr;
1393}
1394
1395static const unsigned MaxDepth = 6;
1396
1397// Take the exact integer log2 of the value. If DoFold is true, create the
1398// actual instructions, otherwise return a non-null dummy value. Return nullptr
1399// on failure.
1400static Value *takeLog2(IRBuilderBase &Builder, Value *Op, unsigned Depth,
1401 bool AssumeNonZero, bool DoFold) {
1402 auto IfFold = [DoFold](function_ref<Value *()> Fn) {
1403 if (!DoFold)
1404 return reinterpret_cast<Value *>(-1);
1405 return Fn();
1406 };
1407
1408 // FIXME: assert that Op1 isn't/doesn't contain undef.
1409
1410 // log2(2^C) -> C
1411 if (match(V: Op, P: m_Power2()))
1412 return IfFold([&]() {
1413 Constant *C = ConstantExpr::getExactLogBase2(C: cast<Constant>(Val: Op));
1414 if (!C)
1415 llvm_unreachable("Failed to constant fold udiv -> logbase2");
1416 return C;
1417 });
1418
1419 // The remaining tests are all recursive, so bail out if we hit the limit.
1420 if (Depth++ == MaxDepth)
1421 return nullptr;
1422
1423 // log2(zext X) -> zext log2(X)
1424 // FIXME: Require one use?
1425 Value *X, *Y;
1426 if (match(V: Op, P: m_ZExt(Op: m_Value(V&: X))))
1427 if (Value *LogX = takeLog2(Builder, Op: X, Depth, AssumeNonZero, DoFold))
1428 return IfFold([&]() { return Builder.CreateZExt(V: LogX, DestTy: Op->getType()); });
1429
1430 // log2(X << Y) -> log2(X) + Y
1431 // FIXME: Require one use unless X is 1?
1432 if (match(V: Op, P: m_Shl(L: m_Value(V&: X), R: m_Value(V&: Y)))) {
1433 auto *BO = cast<OverflowingBinaryOperator>(Val: Op);
1434 // nuw will be set if the `shl` is trivially non-zero.
1435 if (AssumeNonZero || BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap())
1436 if (Value *LogX = takeLog2(Builder, Op: X, Depth, AssumeNonZero, DoFold))
1437 return IfFold([&]() { return Builder.CreateAdd(LHS: LogX, RHS: Y); });
1438 }
1439
1440 // log2(Cond ? X : Y) -> Cond ? log2(X) : log2(Y)
1441 // FIXME: Require one use?
1442 if (SelectInst *SI = dyn_cast<SelectInst>(Val: Op))
1443 if (Value *LogX = takeLog2(Builder, Op: SI->getOperand(i_nocapture: 1), Depth,
1444 AssumeNonZero, DoFold))
1445 if (Value *LogY = takeLog2(Builder, Op: SI->getOperand(i_nocapture: 2), Depth,
1446 AssumeNonZero, DoFold))
1447 return IfFold([&]() {
1448 return Builder.CreateSelect(C: SI->getOperand(i_nocapture: 0), True: LogX, False: LogY);
1449 });
1450
1451 // log2(umin(X, Y)) -> umin(log2(X), log2(Y))
1452 // log2(umax(X, Y)) -> umax(log2(X), log2(Y))
1453 auto *MinMax = dyn_cast<MinMaxIntrinsic>(Val: Op);
1454 if (MinMax && MinMax->hasOneUse() && !MinMax->isSigned()) {
1455 // Use AssumeNonZero as false here. Otherwise we can hit case where
1456 // log2(umax(X, Y)) != umax(log2(X), log2(Y)) (because overflow).
1457 if (Value *LogX = takeLog2(Builder, Op: MinMax->getLHS(), Depth,
1458 /*AssumeNonZero*/ false, DoFold))
1459 if (Value *LogY = takeLog2(Builder, Op: MinMax->getRHS(), Depth,
1460 /*AssumeNonZero*/ false, DoFold))
1461 return IfFold([&]() {
1462 return Builder.CreateBinaryIntrinsic(ID: MinMax->getIntrinsicID(), LHS: LogX,
1463 RHS: LogY);
1464 });
1465 }
1466
1467 return nullptr;
1468}
1469
1470/// If we have zero-extended operands of an unsigned div or rem, we may be able
1471/// to narrow the operation (sink the zext below the math).
1472static Instruction *narrowUDivURem(BinaryOperator &I,
1473 InstCombinerImpl &IC) {
1474 Instruction::BinaryOps Opcode = I.getOpcode();
1475 Value *N = I.getOperand(i_nocapture: 0);
1476 Value *D = I.getOperand(i_nocapture: 1);
1477 Type *Ty = I.getType();
1478 Value *X, *Y;
1479 if (match(V: N, P: m_ZExt(Op: m_Value(V&: X))) && match(V: D, P: m_ZExt(Op: m_Value(V&: Y))) &&
1480 X->getType() == Y->getType() && (N->hasOneUse() || D->hasOneUse())) {
1481 // udiv (zext X), (zext Y) --> zext (udiv X, Y)
1482 // urem (zext X), (zext Y) --> zext (urem X, Y)
1483 Value *NarrowOp = IC.Builder.CreateBinOp(Opc: Opcode, LHS: X, RHS: Y);
1484 return new ZExtInst(NarrowOp, Ty);
1485 }
1486
1487 Constant *C;
1488 if (isa<Instruction>(Val: N) && match(V: N, P: m_OneUse(SubPattern: m_ZExt(Op: m_Value(V&: X)))) &&
1489 match(V: D, P: m_Constant(C))) {
1490 // If the constant is the same in the smaller type, use the narrow version.
1491 Constant *TruncC = IC.getLosslessUnsignedTrunc(C, TruncTy: X->getType());
1492 if (!TruncC)
1493 return nullptr;
1494
1495 // udiv (zext X), C --> zext (udiv X, C')
1496 // urem (zext X), C --> zext (urem X, C')
1497 return new ZExtInst(IC.Builder.CreateBinOp(Opc: Opcode, LHS: X, RHS: TruncC), Ty);
1498 }
1499 if (isa<Instruction>(Val: D) && match(V: D, P: m_OneUse(SubPattern: m_ZExt(Op: m_Value(V&: X)))) &&
1500 match(V: N, P: m_Constant(C))) {
1501 // If the constant is the same in the smaller type, use the narrow version.
1502 Constant *TruncC = IC.getLosslessUnsignedTrunc(C, TruncTy: X->getType());
1503 if (!TruncC)
1504 return nullptr;
1505
1506 // udiv C, (zext X) --> zext (udiv C', X)
1507 // urem C, (zext X) --> zext (urem C', X)
1508 return new ZExtInst(IC.Builder.CreateBinOp(Opc: Opcode, LHS: TruncC, RHS: X), Ty);
1509 }
1510
1511 return nullptr;
1512}
1513
1514Instruction *InstCombinerImpl::visitUDiv(BinaryOperator &I) {
1515 if (Value *V = simplifyUDivInst(LHS: I.getOperand(i_nocapture: 0), RHS: I.getOperand(i_nocapture: 1), IsExact: I.isExact(),
1516 Q: SQ.getWithInstruction(I: &I)))
1517 return replaceInstUsesWith(I, V);
1518
1519 if (Instruction *X = foldVectorBinop(Inst&: I))
1520 return X;
1521
1522 // Handle the integer div common cases
1523 if (Instruction *Common = commonIDivTransforms(I))
1524 return Common;
1525
1526 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
1527 Value *X;
1528 const APInt *C1, *C2;
1529 if (match(V: Op0, P: m_LShr(L: m_Value(V&: X), R: m_APInt(Res&: C1))) && match(V: Op1, P: m_APInt(Res&: C2))) {
1530 // (X lshr C1) udiv C2 --> X udiv (C2 << C1)
1531 bool Overflow;
1532 APInt C2ShlC1 = C2->ushl_ov(Amt: *C1, Overflow);
1533 if (!Overflow) {
1534 bool IsExact = I.isExact() && match(V: Op0, P: m_Exact(SubPattern: m_Value()));
1535 BinaryOperator *BO = BinaryOperator::CreateUDiv(
1536 V1: X, V2: ConstantInt::get(Ty: X->getType(), V: C2ShlC1));
1537 if (IsExact)
1538 BO->setIsExact();
1539 return BO;
1540 }
1541 }
1542
1543 // Op0 / C where C is large (negative) --> zext (Op0 >= C)
1544 // TODO: Could use isKnownNegative() to handle non-constant values.
1545 Type *Ty = I.getType();
1546 if (match(V: Op1, P: m_Negative())) {
1547 Value *Cmp = Builder.CreateICmpUGE(LHS: Op0, RHS: Op1);
1548 return CastInst::CreateZExtOrBitCast(S: Cmp, Ty);
1549 }
1550 // Op0 / (sext i1 X) --> zext (Op0 == -1) (if X is 0, the div is undefined)
1551 if (match(V: Op1, P: m_SExt(Op: m_Value(V&: X))) && X->getType()->isIntOrIntVectorTy(BitWidth: 1)) {
1552 Value *Cmp = Builder.CreateICmpEQ(LHS: Op0, RHS: ConstantInt::getAllOnesValue(Ty));
1553 return CastInst::CreateZExtOrBitCast(S: Cmp, Ty);
1554 }
1555
1556 if (Instruction *NarrowDiv = narrowUDivURem(I, IC&: *this))
1557 return NarrowDiv;
1558
1559 Value *A, *B;
1560
1561 // Look through a right-shift to find the common factor:
1562 // ((Op1 *nuw A) >> B) / Op1 --> A >> B
1563 if (match(V: Op0, P: m_LShr(L: m_NUWMul(L: m_Specific(V: Op1), R: m_Value(V&: A)), R: m_Value(V&: B))) ||
1564 match(V: Op0, P: m_LShr(L: m_NUWMul(L: m_Value(V&: A), R: m_Specific(V: Op1)), R: m_Value(V&: B)))) {
1565 Instruction *Lshr = BinaryOperator::CreateLShr(V1: A, V2: B);
1566 if (I.isExact() && cast<PossiblyExactOperator>(Val: Op0)->isExact())
1567 Lshr->setIsExact();
1568 return Lshr;
1569 }
1570
1571 // Op1 udiv Op2 -> Op1 lshr log2(Op2), if log2() folds away.
1572 if (takeLog2(Builder, Op: Op1, /*Depth*/ 0, /*AssumeNonZero*/ true,
1573 /*DoFold*/ false)) {
1574 Value *Res = takeLog2(Builder, Op: Op1, /*Depth*/ 0,
1575 /*AssumeNonZero*/ true, /*DoFold*/ true);
1576 return replaceInstUsesWith(
1577 I, V: Builder.CreateLShr(LHS: Op0, RHS: Res, Name: I.getName(), isExact: I.isExact()));
1578 }
1579
1580 return nullptr;
1581}
1582
1583Instruction *InstCombinerImpl::visitSDiv(BinaryOperator &I) {
1584 if (Value *V = simplifySDivInst(LHS: I.getOperand(i_nocapture: 0), RHS: I.getOperand(i_nocapture: 1), IsExact: I.isExact(),
1585 Q: SQ.getWithInstruction(I: &I)))
1586 return replaceInstUsesWith(I, V);
1587
1588 if (Instruction *X = foldVectorBinop(Inst&: I))
1589 return X;
1590
1591 // Handle the integer div common cases
1592 if (Instruction *Common = commonIDivTransforms(I))
1593 return Common;
1594
1595 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
1596 Type *Ty = I.getType();
1597 Value *X;
1598 // sdiv Op0, -1 --> -Op0
1599 // sdiv Op0, (sext i1 X) --> -Op0 (because if X is 0, the op is undefined)
1600 if (match(V: Op1, P: m_AllOnes()) ||
1601 (match(V: Op1, P: m_SExt(Op: m_Value(V&: X))) && X->getType()->isIntOrIntVectorTy(BitWidth: 1)))
1602 return BinaryOperator::CreateNSWNeg(Op: Op0);
1603
1604 // X / INT_MIN --> X == INT_MIN
1605 if (match(V: Op1, P: m_SignMask()))
1606 return new ZExtInst(Builder.CreateICmpEQ(LHS: Op0, RHS: Op1), Ty);
1607
1608 if (I.isExact()) {
1609 // sdiv exact X, 1<<C --> ashr exact X, C iff 1<<C is non-negative
1610 if (match(V: Op1, P: m_Power2()) && match(V: Op1, P: m_NonNegative())) {
1611 Constant *C = ConstantExpr::getExactLogBase2(C: cast<Constant>(Val: Op1));
1612 return BinaryOperator::CreateExactAShr(V1: Op0, V2: C);
1613 }
1614
1615 // sdiv exact X, (1<<ShAmt) --> ashr exact X, ShAmt (if shl is non-negative)
1616 Value *ShAmt;
1617 if (match(V: Op1, P: m_NSWShl(L: m_One(), R: m_Value(V&: ShAmt))))
1618 return BinaryOperator::CreateExactAShr(V1: Op0, V2: ShAmt);
1619
1620 // sdiv exact X, -1<<C --> -(ashr exact X, C)
1621 if (match(V: Op1, P: m_NegatedPower2())) {
1622 Constant *NegPow2C = ConstantExpr::getNeg(C: cast<Constant>(Val: Op1));
1623 Constant *C = ConstantExpr::getExactLogBase2(C: NegPow2C);
1624 Value *Ashr = Builder.CreateAShr(LHS: Op0, RHS: C, Name: I.getName() + ".neg", isExact: true);
1625 return BinaryOperator::CreateNSWNeg(Op: Ashr);
1626 }
1627 }
1628
1629 const APInt *Op1C;
1630 if (match(V: Op1, P: m_APInt(Res&: Op1C))) {
1631 // If the dividend is sign-extended and the constant divisor is small enough
1632 // to fit in the source type, shrink the division to the narrower type:
1633 // (sext X) sdiv C --> sext (X sdiv C)
1634 Value *Op0Src;
1635 if (match(V: Op0, P: m_OneUse(SubPattern: m_SExt(Op: m_Value(V&: Op0Src)))) &&
1636 Op0Src->getType()->getScalarSizeInBits() >=
1637 Op1C->getSignificantBits()) {
1638
1639 // In the general case, we need to make sure that the dividend is not the
1640 // minimum signed value because dividing that by -1 is UB. But here, we
1641 // know that the -1 divisor case is already handled above.
1642
1643 Constant *NarrowDivisor =
1644 ConstantExpr::getTrunc(C: cast<Constant>(Val: Op1), Ty: Op0Src->getType());
1645 Value *NarrowOp = Builder.CreateSDiv(LHS: Op0Src, RHS: NarrowDivisor);
1646 return new SExtInst(NarrowOp, Ty);
1647 }
1648
1649 // -X / C --> X / -C (if the negation doesn't overflow).
1650 // TODO: This could be enhanced to handle arbitrary vector constants by
1651 // checking if all elements are not the min-signed-val.
1652 if (!Op1C->isMinSignedValue() && match(V: Op0, P: m_NSWNeg(V: m_Value(V&: X)))) {
1653 Constant *NegC = ConstantInt::get(Ty, V: -(*Op1C));
1654 Instruction *BO = BinaryOperator::CreateSDiv(V1: X, V2: NegC);
1655 BO->setIsExact(I.isExact());
1656 return BO;
1657 }
1658 }
1659
1660 // -X / Y --> -(X / Y)
1661 Value *Y;
1662 if (match(V: &I, P: m_SDiv(L: m_OneUse(SubPattern: m_NSWNeg(V: m_Value(V&: X))), R: m_Value(V&: Y))))
1663 return BinaryOperator::CreateNSWNeg(
1664 Op: Builder.CreateSDiv(LHS: X, RHS: Y, Name: I.getName(), isExact: I.isExact()));
1665
1666 // abs(X) / X --> X > -1 ? 1 : -1
1667 // X / abs(X) --> X > -1 ? 1 : -1
1668 if (match(V: &I, P: m_c_BinOp(
1669 L: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::abs>(Op0: m_Value(V&: X), Op1: m_One())),
1670 R: m_Deferred(V: X)))) {
1671 Value *Cond = Builder.CreateIsNotNeg(Arg: X);
1672 return SelectInst::Create(C: Cond, S1: ConstantInt::get(Ty, V: 1),
1673 S2: ConstantInt::getAllOnesValue(Ty));
1674 }
1675
1676 KnownBits KnownDividend = computeKnownBits(V: Op0, Depth: 0, CxtI: &I);
1677 if (!I.isExact() &&
1678 (match(V: Op1, P: m_Power2(V&: Op1C)) || match(V: Op1, P: m_NegatedPower2(V&: Op1C))) &&
1679 KnownDividend.countMinTrailingZeros() >= Op1C->countr_zero()) {
1680 I.setIsExact();
1681 return &I;
1682 }
1683
1684 if (KnownDividend.isNonNegative()) {
1685 // If both operands are unsigned, turn this into a udiv.
1686 if (isKnownNonNegative(V: Op1, SQ: SQ.getWithInstruction(I: &I))) {
1687 auto *BO = BinaryOperator::CreateUDiv(V1: Op0, V2: Op1, Name: I.getName());
1688 BO->setIsExact(I.isExact());
1689 return BO;
1690 }
1691
1692 if (match(V: Op1, P: m_NegatedPower2())) {
1693 // X sdiv (-(1 << C)) -> -(X sdiv (1 << C)) ->
1694 // -> -(X udiv (1 << C)) -> -(X u>> C)
1695 Constant *CNegLog2 = ConstantExpr::getExactLogBase2(
1696 C: ConstantExpr::getNeg(C: cast<Constant>(Val: Op1)));
1697 Value *Shr = Builder.CreateLShr(LHS: Op0, RHS: CNegLog2, Name: I.getName(), isExact: I.isExact());
1698 return BinaryOperator::CreateNeg(Op: Shr);
1699 }
1700
1701 if (isKnownToBeAPowerOfTwo(V: Op1, /*OrZero*/ true, Depth: 0, CxtI: &I)) {
1702 // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1703 // Safe because the only negative value (1 << Y) can take on is
1704 // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1705 // the sign bit set.
1706 auto *BO = BinaryOperator::CreateUDiv(V1: Op0, V2: Op1, Name: I.getName());
1707 BO->setIsExact(I.isExact());
1708 return BO;
1709 }
1710 }
1711
1712 // -X / X --> X == INT_MIN ? 1 : -1
1713 if (isKnownNegation(X: Op0, Y: Op1)) {
1714 APInt MinVal = APInt::getSignedMinValue(numBits: Ty->getScalarSizeInBits());
1715 Value *Cond = Builder.CreateICmpEQ(LHS: Op0, RHS: ConstantInt::get(Ty, V: MinVal));
1716 return SelectInst::Create(C: Cond, S1: ConstantInt::get(Ty, V: 1),
1717 S2: ConstantInt::getAllOnesValue(Ty));
1718 }
1719 return nullptr;
1720}
1721
1722/// Remove negation and try to convert division into multiplication.
1723Instruction *InstCombinerImpl::foldFDivConstantDivisor(BinaryOperator &I) {
1724 Constant *C;
1725 if (!match(V: I.getOperand(i_nocapture: 1), P: m_Constant(C)))
1726 return nullptr;
1727
1728 // -X / C --> X / -C
1729 Value *X;
1730 const DataLayout &DL = I.getDataLayout();
1731 if (match(V: I.getOperand(i_nocapture: 0), P: m_FNeg(X: m_Value(V&: X))))
1732 if (Constant *NegC = ConstantFoldUnaryOpOperand(Opcode: Instruction::FNeg, Op: C, DL))
1733 return BinaryOperator::CreateFDivFMF(V1: X, V2: NegC, FMFSource: &I);
1734
1735 // nnan X / +0.0 -> copysign(inf, X)
1736 // nnan nsz X / -0.0 -> copysign(inf, X)
1737 if (I.hasNoNaNs() &&
1738 (match(V: I.getOperand(i_nocapture: 1), P: m_PosZeroFP()) ||
1739 (I.hasNoSignedZeros() && match(V: I.getOperand(i_nocapture: 1), P: m_AnyZeroFP())))) {
1740 IRBuilder<> B(&I);
1741 CallInst *CopySign = B.CreateIntrinsic(
1742 ID: Intrinsic::copysign, Types: {C->getType()},
1743 Args: {ConstantFP::getInfinity(Ty: I.getType()), I.getOperand(i_nocapture: 0)}, FMFSource: &I);
1744 CopySign->takeName(V: &I);
1745 return replaceInstUsesWith(I, V: CopySign);
1746 }
1747
1748 // If the constant divisor has an exact inverse, this is always safe. If not,
1749 // then we can still create a reciprocal if fast-math-flags allow it and the
1750 // constant is a regular number (not zero, infinite, or denormal).
1751 if (!(C->hasExactInverseFP() || (I.hasAllowReciprocal() && C->isNormalFP())))
1752 return nullptr;
1753
1754 // Disallow denormal constants because we don't know what would happen
1755 // on all targets.
1756 // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1757 // denorms are flushed?
1758 auto *RecipC = ConstantFoldBinaryOpOperands(
1759 Opcode: Instruction::FDiv, LHS: ConstantFP::get(Ty: I.getType(), V: 1.0), RHS: C, DL);
1760 if (!RecipC || !RecipC->isNormalFP())
1761 return nullptr;
1762
1763 // X / C --> X * (1 / C)
1764 return BinaryOperator::CreateFMulFMF(V1: I.getOperand(i_nocapture: 0), V2: RecipC, FMFSource: &I);
1765}
1766
1767/// Remove negation and try to reassociate constant math.
1768static Instruction *foldFDivConstantDividend(BinaryOperator &I) {
1769 Constant *C;
1770 if (!match(V: I.getOperand(i_nocapture: 0), P: m_Constant(C)))
1771 return nullptr;
1772
1773 // C / -X --> -C / X
1774 Value *X;
1775 const DataLayout &DL = I.getDataLayout();
1776 if (match(V: I.getOperand(i_nocapture: 1), P: m_FNeg(X: m_Value(V&: X))))
1777 if (Constant *NegC = ConstantFoldUnaryOpOperand(Opcode: Instruction::FNeg, Op: C, DL))
1778 return BinaryOperator::CreateFDivFMF(V1: NegC, V2: X, FMFSource: &I);
1779
1780 if (!I.hasAllowReassoc() || !I.hasAllowReciprocal())
1781 return nullptr;
1782
1783 // Try to reassociate C / X expressions where X includes another constant.
1784 Constant *C2, *NewC = nullptr;
1785 if (match(V: I.getOperand(i_nocapture: 1), P: m_FMul(L: m_Value(V&: X), R: m_Constant(C&: C2)))) {
1786 // C / (X * C2) --> (C / C2) / X
1787 NewC = ConstantFoldBinaryOpOperands(Opcode: Instruction::FDiv, LHS: C, RHS: C2, DL);
1788 } else if (match(V: I.getOperand(i_nocapture: 1), P: m_FDiv(L: m_Value(V&: X), R: m_Constant(C&: C2)))) {
1789 // C / (X / C2) --> (C * C2) / X
1790 NewC = ConstantFoldBinaryOpOperands(Opcode: Instruction::FMul, LHS: C, RHS: C2, DL);
1791 }
1792 // Disallow denormal constants because we don't know what would happen
1793 // on all targets.
1794 // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1795 // denorms are flushed?
1796 if (!NewC || !NewC->isNormalFP())
1797 return nullptr;
1798
1799 return BinaryOperator::CreateFDivFMF(V1: NewC, V2: X, FMFSource: &I);
1800}
1801
1802/// Negate the exponent of pow/exp to fold division-by-pow() into multiply.
1803static Instruction *foldFDivPowDivisor(BinaryOperator &I,
1804 InstCombiner::BuilderTy &Builder) {
1805 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
1806 auto *II = dyn_cast<IntrinsicInst>(Val: Op1);
1807 if (!II || !II->hasOneUse() || !I.hasAllowReassoc() ||
1808 !I.hasAllowReciprocal())
1809 return nullptr;
1810
1811 // Z / pow(X, Y) --> Z * pow(X, -Y)
1812 // Z / exp{2}(Y) --> Z * exp{2}(-Y)
1813 // In the general case, this creates an extra instruction, but fmul allows
1814 // for better canonicalization and optimization than fdiv.
1815 Intrinsic::ID IID = II->getIntrinsicID();
1816 SmallVector<Value *> Args;
1817 switch (IID) {
1818 case Intrinsic::pow:
1819 Args.push_back(Elt: II->getArgOperand(i: 0));
1820 Args.push_back(Elt: Builder.CreateFNegFMF(V: II->getArgOperand(i: 1), FMFSource: &I));
1821 break;
1822 case Intrinsic::powi: {
1823 // Require 'ninf' assuming that makes powi(X, -INT_MIN) acceptable.
1824 // That is, X ** (huge negative number) is 0.0, ~1.0, or INF and so
1825 // dividing by that is INF, ~1.0, or 0.0. Code that uses powi allows
1826 // non-standard results, so this corner case should be acceptable if the
1827 // code rules out INF values.
1828 if (!I.hasNoInfs())
1829 return nullptr;
1830 Args.push_back(Elt: II->getArgOperand(i: 0));
1831 Args.push_back(Elt: Builder.CreateNeg(V: II->getArgOperand(i: 1)));
1832 Type *Tys[] = {I.getType(), II->getArgOperand(i: 1)->getType()};
1833 Value *Pow = Builder.CreateIntrinsic(ID: IID, Types: Tys, Args, FMFSource: &I);
1834 return BinaryOperator::CreateFMulFMF(V1: Op0, V2: Pow, FMFSource: &I);
1835 }
1836 case Intrinsic::exp:
1837 case Intrinsic::exp2:
1838 Args.push_back(Elt: Builder.CreateFNegFMF(V: II->getArgOperand(i: 0), FMFSource: &I));
1839 break;
1840 default:
1841 return nullptr;
1842 }
1843 Value *Pow = Builder.CreateIntrinsic(ID: IID, Types: I.getType(), Args, FMFSource: &I);
1844 return BinaryOperator::CreateFMulFMF(V1: Op0, V2: Pow, FMFSource: &I);
1845}
1846
1847/// Convert div to mul if we have an sqrt divisor iff sqrt's operand is a fdiv
1848/// instruction.
1849static Instruction *foldFDivSqrtDivisor(BinaryOperator &I,
1850 InstCombiner::BuilderTy &Builder) {
1851 // X / sqrt(Y / Z) --> X * sqrt(Z / Y)
1852 if (!I.hasAllowReassoc() || !I.hasAllowReciprocal())
1853 return nullptr;
1854 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
1855 auto *II = dyn_cast<IntrinsicInst>(Val: Op1);
1856 if (!II || II->getIntrinsicID() != Intrinsic::sqrt || !II->hasOneUse() ||
1857 !II->hasAllowReassoc() || !II->hasAllowReciprocal())
1858 return nullptr;
1859
1860 Value *Y, *Z;
1861 auto *DivOp = dyn_cast<Instruction>(Val: II->getOperand(i_nocapture: 0));
1862 if (!DivOp)
1863 return nullptr;
1864 if (!match(V: DivOp, P: m_FDiv(L: m_Value(V&: Y), R: m_Value(V&: Z))))
1865 return nullptr;
1866 if (!DivOp->hasAllowReassoc() || !I.hasAllowReciprocal() ||
1867 !DivOp->hasOneUse())
1868 return nullptr;
1869 Value *SwapDiv = Builder.CreateFDivFMF(L: Z, R: Y, FMFSource: DivOp);
1870 Value *NewSqrt =
1871 Builder.CreateUnaryIntrinsic(ID: II->getIntrinsicID(), V: SwapDiv, FMFSource: II);
1872 return BinaryOperator::CreateFMulFMF(V1: Op0, V2: NewSqrt, FMFSource: &I);
1873}
1874
1875Instruction *InstCombinerImpl::visitFDiv(BinaryOperator &I) {
1876 Module *M = I.getModule();
1877
1878 if (Value *V = simplifyFDivInst(LHS: I.getOperand(i_nocapture: 0), RHS: I.getOperand(i_nocapture: 1),
1879 FMF: I.getFastMathFlags(),
1880 Q: SQ.getWithInstruction(I: &I)))
1881 return replaceInstUsesWith(I, V);
1882
1883 if (Instruction *X = foldVectorBinop(Inst&: I))
1884 return X;
1885
1886 if (Instruction *Phi = foldBinopWithPhiOperands(BO&: I))
1887 return Phi;
1888
1889 if (Instruction *R = foldFDivConstantDivisor(I))
1890 return R;
1891
1892 if (Instruction *R = foldFDivConstantDividend(I))
1893 return R;
1894
1895 if (Instruction *R = foldFPSignBitOps(I))
1896 return R;
1897
1898 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
1899 if (isa<Constant>(Val: Op0))
1900 if (SelectInst *SI = dyn_cast<SelectInst>(Val: Op1))
1901 if (Instruction *R = FoldOpIntoSelect(Op&: I, SI))
1902 return R;
1903
1904 if (isa<Constant>(Val: Op1))
1905 if (SelectInst *SI = dyn_cast<SelectInst>(Val: Op0))
1906 if (Instruction *R = FoldOpIntoSelect(Op&: I, SI))
1907 return R;
1908
1909 if (I.hasAllowReassoc() && I.hasAllowReciprocal()) {
1910 Value *X, *Y;
1911 if (match(V: Op0, P: m_OneUse(SubPattern: m_FDiv(L: m_Value(V&: X), R: m_Value(V&: Y)))) &&
1912 (!isa<Constant>(Val: Y) || !isa<Constant>(Val: Op1))) {
1913 // (X / Y) / Z => X / (Y * Z)
1914 Value *YZ = Builder.CreateFMulFMF(L: Y, R: Op1, FMFSource: &I);
1915 return BinaryOperator::CreateFDivFMF(V1: X, V2: YZ, FMFSource: &I);
1916 }
1917 if (match(V: Op1, P: m_OneUse(SubPattern: m_FDiv(L: m_Value(V&: X), R: m_Value(V&: Y)))) &&
1918 (!isa<Constant>(Val: Y) || !isa<Constant>(Val: Op0))) {
1919 // Z / (X / Y) => (Y * Z) / X
1920 Value *YZ = Builder.CreateFMulFMF(L: Y, R: Op0, FMFSource: &I);
1921 return BinaryOperator::CreateFDivFMF(V1: YZ, V2: X, FMFSource: &I);
1922 }
1923 // Z / (1.0 / Y) => (Y * Z)
1924 //
1925 // This is a special case of Z / (X / Y) => (Y * Z) / X, with X = 1.0. The
1926 // m_OneUse check is avoided because even in the case of the multiple uses
1927 // for 1.0/Y, the number of instructions remain the same and a division is
1928 // replaced by a multiplication.
1929 if (match(V: Op1, P: m_FDiv(L: m_SpecificFP(V: 1.0), R: m_Value(V&: Y))))
1930 return BinaryOperator::CreateFMulFMF(V1: Y, V2: Op0, FMFSource: &I);
1931 }
1932
1933 if (I.hasAllowReassoc() && Op0->hasOneUse() && Op1->hasOneUse()) {
1934 // sin(X) / cos(X) -> tan(X)
1935 // cos(X) / sin(X) -> 1/tan(X) (cotangent)
1936 Value *X;
1937 bool IsTan = match(V: Op0, P: m_Intrinsic<Intrinsic::sin>(Op0: m_Value(V&: X))) &&
1938 match(V: Op1, P: m_Intrinsic<Intrinsic::cos>(Op0: m_Specific(V: X)));
1939 bool IsCot =
1940 !IsTan && match(V: Op0, P: m_Intrinsic<Intrinsic::cos>(Op0: m_Value(V&: X))) &&
1941 match(V: Op1, P: m_Intrinsic<Intrinsic::sin>(Op0: m_Specific(V: X)));
1942
1943 if ((IsTan || IsCot) && hasFloatFn(M, TLI: &TLI, Ty: I.getType(), DoubleFn: LibFunc_tan,
1944 FloatFn: LibFunc_tanf, LongDoubleFn: LibFunc_tanl)) {
1945 IRBuilder<> B(&I);
1946 IRBuilder<>::FastMathFlagGuard FMFGuard(B);
1947 B.setFastMathFlags(I.getFastMathFlags());
1948 AttributeList Attrs =
1949 cast<CallBase>(Val: Op0)->getCalledFunction()->getAttributes();
1950 Value *Res = emitUnaryFloatFnCall(Op: X, TLI: &TLI, DoubleFn: LibFunc_tan, FloatFn: LibFunc_tanf,
1951 LongDoubleFn: LibFunc_tanl, B, Attrs);
1952 if (IsCot)
1953 Res = B.CreateFDiv(L: ConstantFP::get(Ty: I.getType(), V: 1.0), R: Res);
1954 return replaceInstUsesWith(I, V: Res);
1955 }
1956 }
1957
1958 // X / (X * Y) --> 1.0 / Y
1959 // Reassociate to (X / X -> 1.0) is legal when NaNs are not allowed.
1960 // We can ignore the possibility that X is infinity because INF/INF is NaN.
1961 Value *X, *Y;
1962 if (I.hasNoNaNs() && I.hasAllowReassoc() &&
1963 match(V: Op1, P: m_c_FMul(L: m_Specific(V: Op0), R: m_Value(V&: Y)))) {
1964 replaceOperand(I, OpNum: 0, V: ConstantFP::get(Ty: I.getType(), V: 1.0));
1965 replaceOperand(I, OpNum: 1, V: Y);
1966 return &I;
1967 }
1968
1969 // X / fabs(X) -> copysign(1.0, X)
1970 // fabs(X) / X -> copysign(1.0, X)
1971 if (I.hasNoNaNs() && I.hasNoInfs() &&
1972 (match(V: &I, P: m_FDiv(L: m_Value(V&: X), R: m_FAbs(Op0: m_Deferred(V: X)))) ||
1973 match(V: &I, P: m_FDiv(L: m_FAbs(Op0: m_Value(V&: X)), R: m_Deferred(V: X))))) {
1974 Value *V = Builder.CreateBinaryIntrinsic(
1975 ID: Intrinsic::copysign, LHS: ConstantFP::get(Ty: I.getType(), V: 1.0), RHS: X, FMFSource: &I);
1976 return replaceInstUsesWith(I, V);
1977 }
1978
1979 if (Instruction *Mul = foldFDivPowDivisor(I, Builder))
1980 return Mul;
1981
1982 if (Instruction *Mul = foldFDivSqrtDivisor(I, Builder))
1983 return Mul;
1984
1985 // pow(X, Y) / X --> pow(X, Y-1)
1986 if (I.hasAllowReassoc() &&
1987 match(V: Op0, P: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::pow>(Op0: m_Specific(V: Op1),
1988 Op1: m_Value(V&: Y))))) {
1989 Value *Y1 =
1990 Builder.CreateFAddFMF(L: Y, R: ConstantFP::get(Ty: I.getType(), V: -1.0), FMFSource: &I);
1991 Value *Pow = Builder.CreateBinaryIntrinsic(ID: Intrinsic::pow, LHS: Op1, RHS: Y1, FMFSource: &I);
1992 return replaceInstUsesWith(I, V: Pow);
1993 }
1994
1995 if (Instruction *FoldedPowi = foldPowiReassoc(I))
1996 return FoldedPowi;
1997
1998 return nullptr;
1999}
2000
2001// Variety of transform for:
2002// (urem/srem (mul X, Y), (mul X, Z))
2003// (urem/srem (shl X, Y), (shl X, Z))
2004// (urem/srem (shl Y, X), (shl Z, X))
2005// NB: The shift cases are really just extensions of the mul case. We treat
2006// shift as Val * (1 << Amt).
2007static Instruction *simplifyIRemMulShl(BinaryOperator &I,
2008 InstCombinerImpl &IC) {
2009 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1), *X = nullptr;
2010 APInt Y, Z;
2011 bool ShiftByX = false;
2012
2013 // If V is not nullptr, it will be matched using m_Specific.
2014 auto MatchShiftOrMulXC = [](Value *Op, Value *&V, APInt &C) -> bool {
2015 const APInt *Tmp = nullptr;
2016 if ((!V && match(V: Op, P: m_Mul(L: m_Value(V), R: m_APInt(Res&: Tmp)))) ||
2017 (V && match(V: Op, P: m_Mul(L: m_Specific(V), R: m_APInt(Res&: Tmp)))))
2018 C = *Tmp;
2019 else if ((!V && match(V: Op, P: m_Shl(L: m_Value(V), R: m_APInt(Res&: Tmp)))) ||
2020 (V && match(V: Op, P: m_Shl(L: m_Specific(V), R: m_APInt(Res&: Tmp)))))
2021 C = APInt(Tmp->getBitWidth(), 1) << *Tmp;
2022 if (Tmp != nullptr)
2023 return true;
2024
2025 // Reset `V` so we don't start with specific value on next match attempt.
2026 V = nullptr;
2027 return false;
2028 };
2029
2030 auto MatchShiftCX = [](Value *Op, APInt &C, Value *&V) -> bool {
2031 const APInt *Tmp = nullptr;
2032 if ((!V && match(V: Op, P: m_Shl(L: m_APInt(Res&: Tmp), R: m_Value(V)))) ||
2033 (V && match(V: Op, P: m_Shl(L: m_APInt(Res&: Tmp), R: m_Specific(V))))) {
2034 C = *Tmp;
2035 return true;
2036 }
2037
2038 // Reset `V` so we don't start with specific value on next match attempt.
2039 V = nullptr;
2040 return false;
2041 };
2042
2043 if (MatchShiftOrMulXC(Op0, X, Y) && MatchShiftOrMulXC(Op1, X, Z)) {
2044 // pass
2045 } else if (MatchShiftCX(Op0, Y, X) && MatchShiftCX(Op1, Z, X)) {
2046 ShiftByX = true;
2047 } else {
2048 return nullptr;
2049 }
2050
2051 bool IsSRem = I.getOpcode() == Instruction::SRem;
2052
2053 OverflowingBinaryOperator *BO0 = cast<OverflowingBinaryOperator>(Val: Op0);
2054 // TODO: We may be able to deduce more about nsw/nuw of BO0/BO1 based on Y >=
2055 // Z or Z >= Y.
2056 bool BO0HasNSW = BO0->hasNoSignedWrap();
2057 bool BO0HasNUW = BO0->hasNoUnsignedWrap();
2058 bool BO0NoWrap = IsSRem ? BO0HasNSW : BO0HasNUW;
2059
2060 APInt RemYZ = IsSRem ? Y.srem(RHS: Z) : Y.urem(RHS: Z);
2061 // (rem (mul nuw/nsw X, Y), (mul X, Z))
2062 // if (rem Y, Z) == 0
2063 // -> 0
2064 if (RemYZ.isZero() && BO0NoWrap)
2065 return IC.replaceInstUsesWith(I, V: ConstantInt::getNullValue(Ty: I.getType()));
2066
2067 // Helper function to emit either (RemSimplificationC << X) or
2068 // (RemSimplificationC * X) depending on whether we matched Op0/Op1 as
2069 // (shl V, X) or (mul V, X) respectively.
2070 auto CreateMulOrShift =
2071 [&](const APInt &RemSimplificationC) -> BinaryOperator * {
2072 Value *RemSimplification =
2073 ConstantInt::get(Ty: I.getType(), V: RemSimplificationC);
2074 return ShiftByX ? BinaryOperator::CreateShl(V1: RemSimplification, V2: X)
2075 : BinaryOperator::CreateMul(V1: X, V2: RemSimplification);
2076 };
2077
2078 OverflowingBinaryOperator *BO1 = cast<OverflowingBinaryOperator>(Val: Op1);
2079 bool BO1HasNSW = BO1->hasNoSignedWrap();
2080 bool BO1HasNUW = BO1->hasNoUnsignedWrap();
2081 bool BO1NoWrap = IsSRem ? BO1HasNSW : BO1HasNUW;
2082 // (rem (mul X, Y), (mul nuw/nsw X, Z))
2083 // if (rem Y, Z) == Y
2084 // -> (mul nuw/nsw X, Y)
2085 if (RemYZ == Y && BO1NoWrap) {
2086 BinaryOperator *BO = CreateMulOrShift(Y);
2087 // Copy any overflow flags from Op0.
2088 BO->setHasNoSignedWrap(IsSRem || BO0HasNSW);
2089 BO->setHasNoUnsignedWrap(!IsSRem || BO0HasNUW);
2090 return BO;
2091 }
2092
2093 // (rem (mul nuw/nsw X, Y), (mul {nsw} X, Z))
2094 // if Y >= Z
2095 // -> (mul {nuw} nsw X, (rem Y, Z))
2096 if (Y.uge(RHS: Z) && (IsSRem ? (BO0HasNSW && BO1HasNSW) : BO0HasNUW)) {
2097 BinaryOperator *BO = CreateMulOrShift(RemYZ);
2098 BO->setHasNoSignedWrap();
2099 BO->setHasNoUnsignedWrap(BO0HasNUW);
2100 return BO;
2101 }
2102
2103 return nullptr;
2104}
2105
2106/// This function implements the transforms common to both integer remainder
2107/// instructions (urem and srem). It is called by the visitors to those integer
2108/// remainder instructions.
2109/// Common integer remainder transforms
2110Instruction *InstCombinerImpl::commonIRemTransforms(BinaryOperator &I) {
2111 if (Instruction *Phi = foldBinopWithPhiOperands(BO&: I))
2112 return Phi;
2113
2114 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
2115
2116 // The RHS is known non-zero.
2117 if (Value *V = simplifyValueKnownNonZero(V: I.getOperand(i_nocapture: 1), IC&: *this, CxtI&: I))
2118 return replaceOperand(I, OpNum: 1, V);
2119
2120 // Handle cases involving: rem X, (select Cond, Y, Z)
2121 if (simplifyDivRemOfSelectWithZeroOp(I))
2122 return &I;
2123
2124 // If the divisor is a select-of-constants, try to constant fold all rem ops:
2125 // C % (select Cond, TrueC, FalseC) --> select Cond, (C % TrueC), (C % FalseC)
2126 // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
2127 if (match(V: Op0, P: m_ImmConstant()) &&
2128 match(V: Op1, P: m_Select(C: m_Value(), L: m_ImmConstant(), R: m_ImmConstant()))) {
2129 if (Instruction *R = FoldOpIntoSelect(Op&: I, SI: cast<SelectInst>(Val: Op1),
2130 /*FoldWithMultiUse*/ true))
2131 return R;
2132 }
2133
2134 if (isa<Constant>(Val: Op1)) {
2135 if (Instruction *Op0I = dyn_cast<Instruction>(Val: Op0)) {
2136 if (SelectInst *SI = dyn_cast<SelectInst>(Val: Op0I)) {
2137 if (Instruction *R = FoldOpIntoSelect(Op&: I, SI))
2138 return R;
2139 } else if (auto *PN = dyn_cast<PHINode>(Val: Op0I)) {
2140 const APInt *Op1Int;
2141 if (match(V: Op1, P: m_APInt(Res&: Op1Int)) && !Op1Int->isMinValue() &&
2142 (I.getOpcode() == Instruction::URem ||
2143 !Op1Int->isMinSignedValue())) {
2144 // foldOpIntoPhi will speculate instructions to the end of the PHI's
2145 // predecessor blocks, so do this only if we know the srem or urem
2146 // will not fault.
2147 if (Instruction *NV = foldOpIntoPhi(I, PN))
2148 return NV;
2149 }
2150 }
2151
2152 // See if we can fold away this rem instruction.
2153 if (SimplifyDemandedInstructionBits(Inst&: I))
2154 return &I;
2155 }
2156 }
2157
2158 if (Instruction *R = simplifyIRemMulShl(I, IC&: *this))
2159 return R;
2160
2161 return nullptr;
2162}
2163
2164Instruction *InstCombinerImpl::visitURem(BinaryOperator &I) {
2165 if (Value *V = simplifyURemInst(LHS: I.getOperand(i_nocapture: 0), RHS: I.getOperand(i_nocapture: 1),
2166 Q: SQ.getWithInstruction(I: &I)))
2167 return replaceInstUsesWith(I, V);
2168
2169 if (Instruction *X = foldVectorBinop(Inst&: I))
2170 return X;
2171
2172 if (Instruction *common = commonIRemTransforms(I))
2173 return common;
2174
2175 if (Instruction *NarrowRem = narrowUDivURem(I, IC&: *this))
2176 return NarrowRem;
2177
2178 // X urem Y -> X and Y-1, where Y is a power of 2,
2179 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
2180 Type *Ty = I.getType();
2181 if (isKnownToBeAPowerOfTwo(V: Op1, /*OrZero*/ true, Depth: 0, CxtI: &I)) {
2182 // This may increase instruction count, we don't enforce that Y is a
2183 // constant.
2184 Constant *N1 = Constant::getAllOnesValue(Ty);
2185 Value *Add = Builder.CreateAdd(LHS: Op1, RHS: N1);
2186 return BinaryOperator::CreateAnd(V1: Op0, V2: Add);
2187 }
2188
2189 // 1 urem X -> zext(X != 1)
2190 if (match(V: Op0, P: m_One())) {
2191 Value *Cmp = Builder.CreateICmpNE(LHS: Op1, RHS: ConstantInt::get(Ty, V: 1));
2192 return CastInst::CreateZExtOrBitCast(S: Cmp, Ty);
2193 }
2194
2195 // Op0 urem C -> Op0 < C ? Op0 : Op0 - C, where C >= signbit.
2196 // Op0 must be frozen because we are increasing its number of uses.
2197 if (match(V: Op1, P: m_Negative())) {
2198 Value *F0 = Op0;
2199 if (!isGuaranteedNotToBeUndef(V: Op0))
2200 F0 = Builder.CreateFreeze(V: Op0, Name: Op0->getName() + ".fr");
2201 Value *Cmp = Builder.CreateICmpULT(LHS: F0, RHS: Op1);
2202 Value *Sub = Builder.CreateSub(LHS: F0, RHS: Op1);
2203 return SelectInst::Create(C: Cmp, S1: F0, S2: Sub);
2204 }
2205
2206 // If the divisor is a sext of a boolean, then the divisor must be max
2207 // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also
2208 // max unsigned value. In that case, the remainder is 0:
2209 // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0
2210 Value *X;
2211 if (match(V: Op1, P: m_SExt(Op: m_Value(V&: X))) && X->getType()->isIntOrIntVectorTy(BitWidth: 1)) {
2212 Value *FrozenOp0 = Op0;
2213 if (!isGuaranteedNotToBeUndef(V: Op0))
2214 FrozenOp0 = Builder.CreateFreeze(V: Op0, Name: Op0->getName() + ".frozen");
2215 Value *Cmp =
2216 Builder.CreateICmpEQ(LHS: FrozenOp0, RHS: ConstantInt::getAllOnesValue(Ty));
2217 return SelectInst::Create(C: Cmp, S1: ConstantInt::getNullValue(Ty), S2: FrozenOp0);
2218 }
2219
2220 // For "(X + 1) % Op1" and if (X u< Op1) => (X + 1) == Op1 ? 0 : X + 1 .
2221 if (match(V: Op0, P: m_Add(L: m_Value(V&: X), R: m_One()))) {
2222 Value *Val =
2223 simplifyICmpInst(Predicate: ICmpInst::ICMP_ULT, LHS: X, RHS: Op1, Q: SQ.getWithInstruction(I: &I));
2224 if (Val && match(V: Val, P: m_One())) {
2225 Value *FrozenOp0 = Op0;
2226 if (!isGuaranteedNotToBeUndef(V: Op0))
2227 FrozenOp0 = Builder.CreateFreeze(V: Op0, Name: Op0->getName() + ".frozen");
2228 Value *Cmp = Builder.CreateICmpEQ(LHS: FrozenOp0, RHS: Op1);
2229 return SelectInst::Create(C: Cmp, S1: ConstantInt::getNullValue(Ty), S2: FrozenOp0);
2230 }
2231 }
2232
2233 return nullptr;
2234}
2235
2236Instruction *InstCombinerImpl::visitSRem(BinaryOperator &I) {
2237 if (Value *V = simplifySRemInst(LHS: I.getOperand(i_nocapture: 0), RHS: I.getOperand(i_nocapture: 1),
2238 Q: SQ.getWithInstruction(I: &I)))
2239 return replaceInstUsesWith(I, V);
2240
2241 if (Instruction *X = foldVectorBinop(Inst&: I))
2242 return X;
2243
2244 // Handle the integer rem common cases
2245 if (Instruction *Common = commonIRemTransforms(I))
2246 return Common;
2247
2248 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
2249 {
2250 const APInt *Y;
2251 // X % -Y -> X % Y
2252 if (match(V: Op1, P: m_Negative(V&: Y)) && !Y->isMinSignedValue())
2253 return replaceOperand(I, OpNum: 1, V: ConstantInt::get(Ty: I.getType(), V: -*Y));
2254 }
2255
2256 // -X srem Y --> -(X srem Y)
2257 Value *X, *Y;
2258 if (match(V: &I, P: m_SRem(L: m_OneUse(SubPattern: m_NSWNeg(V: m_Value(V&: X))), R: m_Value(V&: Y))))
2259 return BinaryOperator::CreateNSWNeg(Op: Builder.CreateSRem(LHS: X, RHS: Y));
2260
2261 // If the sign bits of both operands are zero (i.e. we can prove they are
2262 // unsigned inputs), turn this into a urem.
2263 APInt Mask(APInt::getSignMask(BitWidth: I.getType()->getScalarSizeInBits()));
2264 if (MaskedValueIsZero(V: Op1, Mask, Depth: 0, CxtI: &I) &&
2265 MaskedValueIsZero(V: Op0, Mask, Depth: 0, CxtI: &I)) {
2266 // X srem Y -> X urem Y, iff X and Y don't have sign bit set
2267 return BinaryOperator::CreateURem(V1: Op0, V2: Op1, Name: I.getName());
2268 }
2269
2270 // If it's a constant vector, flip any negative values positive.
2271 if (isa<ConstantVector>(Val: Op1) || isa<ConstantDataVector>(Val: Op1)) {
2272 Constant *C = cast<Constant>(Val: Op1);
2273 unsigned VWidth = cast<FixedVectorType>(Val: C->getType())->getNumElements();
2274
2275 bool hasNegative = false;
2276 bool hasMissing = false;
2277 for (unsigned i = 0; i != VWidth; ++i) {
2278 Constant *Elt = C->getAggregateElement(Elt: i);
2279 if (!Elt) {
2280 hasMissing = true;
2281 break;
2282 }
2283
2284 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Val: Elt))
2285 if (RHS->isNegative())
2286 hasNegative = true;
2287 }
2288
2289 if (hasNegative && !hasMissing) {
2290 SmallVector<Constant *, 16> Elts(VWidth);
2291 for (unsigned i = 0; i != VWidth; ++i) {
2292 Elts[i] = C->getAggregateElement(Elt: i); // Handle undef, etc.
2293 if (ConstantInt *RHS = dyn_cast<ConstantInt>(Val: Elts[i])) {
2294 if (RHS->isNegative())
2295 Elts[i] = cast<ConstantInt>(Val: ConstantExpr::getNeg(C: RHS));
2296 }
2297 }
2298
2299 Constant *NewRHSV = ConstantVector::get(V: Elts);
2300 if (NewRHSV != C) // Don't loop on -MININT
2301 return replaceOperand(I, OpNum: 1, V: NewRHSV);
2302 }
2303 }
2304
2305 return nullptr;
2306}
2307
2308Instruction *InstCombinerImpl::visitFRem(BinaryOperator &I) {
2309 if (Value *V = simplifyFRemInst(LHS: I.getOperand(i_nocapture: 0), RHS: I.getOperand(i_nocapture: 1),
2310 FMF: I.getFastMathFlags(),
2311 Q: SQ.getWithInstruction(I: &I)))
2312 return replaceInstUsesWith(I, V);
2313
2314 if (Instruction *X = foldVectorBinop(Inst&: I))
2315 return X;
2316
2317 if (Instruction *Phi = foldBinopWithPhiOperands(BO&: I))
2318 return Phi;
2319
2320 return nullptr;
2321}
2322