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