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