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