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