LLVM  16.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"
16 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/Constant.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/InstrTypes.h"
23 #include "llvm/IR/Instruction.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/IntrinsicInst.h"
26 #include "llvm/IR/Intrinsics.h"
27 #include "llvm/IR/Operator.h"
28 #include "llvm/IR/PatternMatch.h"
29 #include "llvm/IR/Type.h"
30 #include "llvm/IR/Value.h"
31 #include "llvm/Support/Casting.h"
35 #include <cassert>
36 
37 #define DEBUG_TYPE "instcombine"
39 
40 using namespace llvm;
41 using 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().
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, "", false, 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, "", false, 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)))) {
126  Builder.setFastMathFlags(I.getFastMathFlags());
127  return Builder.CreateSelect(Cond, OtherOp, Builder.CreateFNeg(OtherOp));
128  }
129 
130  // fmul (select Cond, -1.0, 1.0), OtherOp --> select Cond, -OtherOp, OtherOp
131  // fmul OtherOp, (select Cond, -1.0, 1.0) --> select Cond, -OtherOp, OtherOp
133  m_SpecificFP(1.0))),
134  m_Value(OtherOp)))) {
136  Builder.setFastMathFlags(I.getFastMathFlags());
137  return Builder.CreateSelect(Cond, Builder.CreateFNeg(OtherOp), OtherOp);
138  }
139 
140  return nullptr;
141 }
142 
143 /// Reduce integer multiplication patterns that contain a (+/-1 << Z) factor.
144 /// Callers are expected to call this twice to handle commuted patterns.
145 static Value *foldMulShl1(BinaryOperator &Mul, bool CommuteOperands,
147  Value *X = Mul.getOperand(0), *Y = Mul.getOperand(1);
148  if (CommuteOperands)
149  std::swap(X, Y);
150 
151  const bool HasNSW = Mul.hasNoSignedWrap();
152  const bool HasNUW = Mul.hasNoUnsignedWrap();
153 
154  // X * (1 << Z) --> X << Z
155  Value *Z;
156  if (match(Y, m_Shl(m_One(), m_Value(Z)))) {
157  bool PropagateNSW = HasNSW && cast<ShlOperator>(Y)->hasNoSignedWrap();
158  return Builder.CreateShl(X, Z, Mul.getName(), HasNUW, PropagateNSW);
159  }
160 
161  // Similar to above, but an increment of the shifted value becomes an add:
162  // X * ((1 << Z) + 1) --> (X * (1 << Z)) + X --> (X << Z) + X
163  // This increases uses of X, so it may require a freeze, but that is still
164  // expected to be an improvement because it removes the multiply.
166  if (match(Y, m_OneUse(m_Add(m_BinOp(Shift), m_One()))) &&
167  match(Shift, m_OneUse(m_Shl(m_One(), m_Value(Z))))) {
168  bool PropagateNSW = HasNSW && Shift->hasNoSignedWrap();
169  Value *FrX = Builder.CreateFreeze(X, X->getName() + ".fr");
170  Value *Shl = Builder.CreateShl(FrX, Z, "mulshl", HasNUW, PropagateNSW);
171  return Builder.CreateAdd(Shl, FrX, Mul.getName(), HasNUW, PropagateNSW);
172  }
173 
174  // Similar to above, but a decrement of the shifted value is disguised as
175  // 'not' and becomes a sub:
176  // X * (~(-1 << Z)) --> X * ((1 << Z) - 1) --> (X << Z) - X
177  // This increases uses of X, so it may require a freeze, but that is still
178  // expected to be an improvement because it removes the multiply.
180  Value *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 
189  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
190  if (Value *V = simplifyMulInst(Op0, Op1, SQ.getWithInstruction(&I)))
191  return replaceInstUsesWith(I, V);
192 
193  if (SimplifyAssociativeOrCommutative(I))
194  return &I;
195 
196  if (Instruction *X = foldVectorBinop(I))
197  return X;
198 
199  if (Instruction *Phi = foldBinopWithPhiOperands(I))
200  return Phi;
201 
202  if (Value *V = foldUsingDistributiveLaws(I))
203  return replaceInstUsesWith(I, V);
204 
205  Type *Ty = I.getType();
206  const unsigned BitWidth = Ty->getScalarSizeInBits();
207  const bool HasNSW = I.hasNoSignedWrap();
208  const bool HasNUW = I.hasNoUnsignedWrap();
209 
210  // X * -1 --> 0 - X
211  if (match(Op1, m_AllOnes())) {
212  return HasNSW ? BinaryOperator::CreateNSWNeg(Op0)
214  }
215 
216  // Also allow combining multiply instructions on vectors.
217  {
218  Value *NewOp;
219  Constant *C1, *C2;
220  const APInt *IVal;
221  if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
222  m_Constant(C1))) &&
223  match(C1, m_APInt(IVal))) {
224  // ((X << C2)*C1) == (X * (C1 << C2))
225  Constant *Shl = ConstantExpr::getShl(C1, C2);
226  BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0));
227  BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl);
228  if (HasNUW && Mul->hasNoUnsignedWrap())
229  BO->setHasNoUnsignedWrap();
230  if (HasNSW && Mul->hasNoSignedWrap() && Shl->isNotMinSignedValue())
231  BO->setHasNoSignedWrap();
232  return BO;
233  }
234 
235  if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
236  // Replace X*(2^C) with X << C, where C is either a scalar or a vector.
237  if (Constant *NewCst = ConstantExpr::getExactLogBase2(C1)) {
238  BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
239 
240  if (HasNUW)
241  Shl->setHasNoUnsignedWrap();
242  if (HasNSW) {
243  const APInt *V;
244  if (match(NewCst, m_APInt(V)) && *V != V->getBitWidth() - 1)
245  Shl->setHasNoSignedWrap();
246  }
247 
248  return Shl;
249  }
250  }
251  }
252 
253  if (Op0->hasOneUse() && match(Op1, m_NegatedPower2())) {
254  // Interpret X * (-1<<C) as (-X) * (1<<C) and try to sink the negation.
255  // The "* (1<<C)" thus becomes a potential shifting opportunity.
256  if (Value *NegOp0 = Negator::Negate(/*IsNegation*/ true, Op0, *this))
258  NegOp0, ConstantExpr::getNeg(cast<Constant>(Op1)), I.getName());
259 
260  // Try to convert multiply of extended operand to narrow negate and shift
261  // for better analysis.
262  // This is valid if the shift amount (trailing zeros in the multiplier
263  // constant) clears more high bits than the bitwidth difference between
264  // source and destination types:
265  // ({z/s}ext X) * (-1<<C) --> (zext (-X)) << C
266  const APInt *NegPow2C;
267  Value *X;
268  if (match(Op0, m_ZExtOrSExt(m_Value(X))) &&
269  match(Op1, m_APIntAllowUndef(NegPow2C))) {
270  unsigned SrcWidth = X->getType()->getScalarSizeInBits();
271  unsigned ShiftAmt = NegPow2C->countTrailingZeros();
272  if (ShiftAmt >= BitWidth - SrcWidth) {
273  Value *N = Builder.CreateNeg(X, X->getName() + ".neg");
274  Value *Z = Builder.CreateZExt(N, Ty, N->getName() + ".z");
275  return BinaryOperator::CreateShl(Z, ConstantInt::get(Ty, ShiftAmt));
276  }
277  }
278  }
279 
280  if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
281  return FoldedMul;
282 
283  if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
284  return replaceInstUsesWith(I, FoldedMul);
285 
286  // Simplify mul instructions with a constant RHS.
287  Constant *MulC;
288  if (match(Op1, m_ImmConstant(MulC))) {
289  // Canonicalize (X+C1)*MulC -> X*MulC+C1*MulC.
290  // Canonicalize (X|C1)*MulC -> X*MulC+C1*MulC.
291  Value *X;
292  Constant *C1;
293  if ((match(Op0, m_OneUse(m_Add(m_Value(X), m_ImmConstant(C1))))) ||
294  (match(Op0, m_OneUse(m_Or(m_Value(X), m_ImmConstant(C1)))) &&
295  haveNoCommonBitsSet(X, C1, DL, &AC, &I, &DT))) {
296  // C1*MulC simplifies to a tidier constant.
297  Value *NewC = Builder.CreateMul(C1, MulC);
298  auto *BOp0 = cast<BinaryOperator>(Op0);
299  bool Op0NUW =
300  (BOp0->getOpcode() == Instruction::Or || BOp0->hasNoUnsignedWrap());
301  Value *NewMul = Builder.CreateMul(X, MulC);
302  auto *BO = BinaryOperator::CreateAdd(NewMul, NewC);
303  if (HasNUW && Op0NUW) {
304  // If NewMulBO is constant we also can set BO to nuw.
305  if (auto *NewMulBO = dyn_cast<BinaryOperator>(NewMul))
306  NewMulBO->setHasNoUnsignedWrap();
307  BO->setHasNoUnsignedWrap();
308  }
309  return BO;
310  }
311  }
312 
313  // abs(X) * abs(X) -> X * X
314  // nabs(X) * nabs(X) -> X * X
315  if (Op0 == Op1) {
316  Value *X, *Y;
318  if (SPF == SPF_ABS || SPF == SPF_NABS)
319  return BinaryOperator::CreateMul(X, X);
320 
321  if (match(Op0, m_Intrinsic<Intrinsic::abs>(m_Value(X))))
322  return BinaryOperator::CreateMul(X, X);
323  }
324 
325  // -X * C --> X * -C
326  Value *X, *Y;
327  Constant *Op1C;
328  if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Constant(Op1C)))
330 
331  // -X * -Y --> X * Y
332  if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Neg(m_Value(Y)))) {
333  auto *NewMul = BinaryOperator::CreateMul(X, Y);
334  if (HasNSW && cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap() &&
335  cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap())
336  NewMul->setHasNoSignedWrap();
337  return NewMul;
338  }
339 
340  // -X * Y --> -(X * Y)
341  // X * -Y --> -(X * Y)
342  if (match(&I, m_c_Mul(m_OneUse(m_Neg(m_Value(X))), m_Value(Y))))
343  return BinaryOperator::CreateNeg(Builder.CreateMul(X, Y));
344 
345  // (X / Y) * Y = X - (X % Y)
346  // (X / Y) * -Y = (X % Y) - X
347  {
348  Value *Y = Op1;
349  BinaryOperator *Div = dyn_cast<BinaryOperator>(Op0);
350  if (!Div || (Div->getOpcode() != Instruction::UDiv &&
351  Div->getOpcode() != Instruction::SDiv)) {
352  Y = Op0;
353  Div = dyn_cast<BinaryOperator>(Op1);
354  }
355  Value *Neg = dyn_castNegVal(Y);
356  if (Div && Div->hasOneUse() &&
357  (Div->getOperand(1) == Y || Div->getOperand(1) == Neg) &&
358  (Div->getOpcode() == Instruction::UDiv ||
359  Div->getOpcode() == Instruction::SDiv)) {
360  Value *X = Div->getOperand(0), *DivOp1 = Div->getOperand(1);
361 
362  // If the division is exact, X % Y is zero, so we end up with X or -X.
363  if (Div->isExact()) {
364  if (DivOp1 == Y)
365  return replaceInstUsesWith(I, X);
367  }
368 
369  auto RemOpc = Div->getOpcode() == Instruction::UDiv ? Instruction::URem
370  : Instruction::SRem;
371  // X must be frozen because we are increasing its number of uses.
372  Value *XFreeze = Builder.CreateFreeze(X, X->getName() + ".fr");
373  Value *Rem = Builder.CreateBinOp(RemOpc, XFreeze, DivOp1);
374  if (DivOp1 == Y)
375  return BinaryOperator::CreateSub(XFreeze, Rem);
376  return BinaryOperator::CreateSub(Rem, XFreeze);
377  }
378  }
379 
380  // Fold the following two scenarios:
381  // 1) i1 mul -> i1 and.
382  // 2) X * Y --> X & Y, iff X, Y can be only {0,1}.
383  // Note: We could use known bits to generalize this and related patterns with
384  // shifts/truncs
385  if (Ty->isIntOrIntVectorTy(1) ||
386  (match(Op0, m_And(m_Value(), m_One())) &&
387  match(Op1, m_And(m_Value(), m_One()))))
388  return BinaryOperator::CreateAnd(Op0, Op1);
389 
390  if (Value *R = foldMulShl1(I, /* CommuteOperands */ false, Builder))
391  return replaceInstUsesWith(I, R);
392  if (Value *R = foldMulShl1(I, /* CommuteOperands */ true, Builder))
393  return replaceInstUsesWith(I, R);
394 
395  // (zext bool X) * (zext bool Y) --> zext (and X, Y)
396  // (sext bool X) * (sext bool Y) --> zext (and X, Y)
397  // Note: -1 * -1 == 1 * 1 == 1 (if the extends match, the result is the same)
398  if (((match(Op0, m_ZExt(m_Value(X))) && match(Op1, m_ZExt(m_Value(Y)))) ||
399  (match(Op0, m_SExt(m_Value(X))) && match(Op1, m_SExt(m_Value(Y))))) &&
400  X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType() &&
401  (Op0->hasOneUse() || Op1->hasOneUse() || X == Y)) {
402  Value *And = Builder.CreateAnd(X, Y, "mulbool");
403  return CastInst::Create(Instruction::ZExt, And, Ty);
404  }
405  // (sext bool X) * (zext bool Y) --> sext (and X, Y)
406  // (zext bool X) * (sext bool Y) --> sext (and X, Y)
407  // Note: -1 * 1 == 1 * -1 == -1
408  if (((match(Op0, m_SExt(m_Value(X))) && match(Op1, m_ZExt(m_Value(Y)))) ||
409  (match(Op0, m_ZExt(m_Value(X))) && match(Op1, m_SExt(m_Value(Y))))) &&
410  X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType() &&
411  (Op0->hasOneUse() || Op1->hasOneUse())) {
412  Value *And = Builder.CreateAnd(X, Y, "mulbool");
413  return CastInst::Create(Instruction::SExt, And, Ty);
414  }
415 
416  // (zext bool X) * Y --> X ? Y : 0
417  // Y * (zext bool X) --> X ? Y : 0
418  if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
420  if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
422 
423  Constant *ImmC;
424  if (match(Op1, m_ImmConstant(ImmC))) {
425  // (sext bool X) * C --> X ? -C : 0
426  if (match(Op0, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
427  Constant *NegC = ConstantExpr::getNeg(ImmC);
429  }
430 
431  // (ashr i32 X, 31) * C --> (X < 0) ? -C : 0
432  const APInt *C;
433  if (match(Op0, m_OneUse(m_AShr(m_Value(X), m_APInt(C)))) &&
434  *C == C->getBitWidth() - 1) {
435  Constant *NegC = ConstantExpr::getNeg(ImmC);
436  Value *IsNeg = Builder.CreateIsNeg(X, "isneg");
437  return SelectInst::Create(IsNeg, NegC, ConstantInt::getNullValue(Ty));
438  }
439  }
440 
441  // (lshr X, 31) * Y --> (X < 0) ? Y : 0
442  // TODO: We are not checking one-use because the elimination of the multiply
443  // is better for analysis?
444  const APInt *C;
445  if (match(&I, m_c_BinOp(m_LShr(m_Value(X), m_APInt(C)), m_Value(Y))) &&
446  *C == C->getBitWidth() - 1) {
447  Value *IsNeg = Builder.CreateIsNeg(X, "isneg");
448  return SelectInst::Create(IsNeg, Y, ConstantInt::getNullValue(Ty));
449  }
450 
451  // (and X, 1) * Y --> (trunc X) ? Y : 0
452  if (match(&I, m_c_BinOp(m_OneUse(m_And(m_Value(X), m_One())), m_Value(Y)))) {
453  Value *Tr = Builder.CreateTrunc(X, CmpInst::makeCmpResultType(Ty));
455  }
456 
457  // ((ashr X, 31) | 1) * X --> abs(X)
458  // X * ((ashr X, 31) | 1) --> abs(X)
461  m_One()),
462  m_Deferred(X)))) {
463  Value *Abs = Builder.CreateBinaryIntrinsic(
464  Intrinsic::abs, X, ConstantInt::getBool(I.getContext(), HasNSW));
465  Abs->takeName(&I);
466  return replaceInstUsesWith(I, Abs);
467  }
468 
469  if (Instruction *Ext = narrowMathIfNoOverflow(I))
470  return Ext;
471 
472  bool Changed = false;
473  if (!HasNSW && willNotOverflowSignedMul(Op0, Op1, I)) {
474  Changed = true;
475  I.setHasNoSignedWrap(true);
476  }
477 
478  if (!HasNUW && willNotOverflowUnsignedMul(Op0, Op1, I)) {
479  Changed = true;
480  I.setHasNoUnsignedWrap(true);
481  }
482 
483  return Changed ? &I : nullptr;
484 }
485 
486 Instruction *InstCombinerImpl::foldFPSignBitOps(BinaryOperator &I) {
487  BinaryOperator::BinaryOps Opcode = I.getOpcode();
488  assert((Opcode == Instruction::FMul || Opcode == Instruction::FDiv) &&
489  "Expected fmul or fdiv");
490 
491  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
492  Value *X, *Y;
493 
494  // -X * -Y --> X * Y
495  // -X / -Y --> X / Y
496  if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y))))
497  return BinaryOperator::CreateWithCopiedFlags(Opcode, X, Y, &I);
498 
499  // fabs(X) * fabs(X) -> X * X
500  // fabs(X) / fabs(X) -> X / X
501  if (Op0 == Op1 && match(Op0, m_FAbs(m_Value(X))))
502  return BinaryOperator::CreateWithCopiedFlags(Opcode, X, X, &I);
503 
504  // fabs(X) * fabs(Y) --> fabs(X * Y)
505  // fabs(X) / fabs(Y) --> fabs(X / Y)
506  if (match(Op0, m_FAbs(m_Value(X))) && match(Op1, m_FAbs(m_Value(Y))) &&
507  (Op0->hasOneUse() || Op1->hasOneUse())) {
509  Builder.setFastMathFlags(I.getFastMathFlags());
510  Value *XY = Builder.CreateBinOp(Opcode, X, Y);
511  Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, XY);
512  Fabs->takeName(&I);
513  return replaceInstUsesWith(I, Fabs);
514  }
515 
516  return nullptr;
517 }
518 
520  if (Value *V = simplifyFMulInst(I.getOperand(0), I.getOperand(1),
521  I.getFastMathFlags(),
522  SQ.getWithInstruction(&I)))
523  return replaceInstUsesWith(I, V);
524 
525  if (SimplifyAssociativeOrCommutative(I))
526  return &I;
527 
528  if (Instruction *X = foldVectorBinop(I))
529  return X;
530 
531  if (Instruction *Phi = foldBinopWithPhiOperands(I))
532  return Phi;
533 
534  if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
535  return FoldedMul;
536 
537  if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
538  return replaceInstUsesWith(I, FoldedMul);
539 
540  if (Instruction *R = foldFPSignBitOps(I))
541  return R;
542 
543  // X * -1.0 --> -X
544  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
545  if (match(Op1, m_SpecificFP(-1.0)))
546  return UnaryOperator::CreateFNegFMF(Op0, &I);
547 
548  // With no-nans: X * 0.0 --> copysign(0.0, X)
549  if (I.hasNoNaNs() && match(Op1, m_PosZeroFP())) {
550  CallInst *CopySign = Builder.CreateIntrinsic(Intrinsic::copysign,
551  {I.getType()}, {Op1, Op0}, &I);
552  return replaceInstUsesWith(I, CopySign);
553  }
554 
555  // -X * C --> X * -C
556  Value *X, *Y;
557  Constant *C;
558  if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_Constant(C)))
559  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
560  return BinaryOperator::CreateFMulFMF(X, NegC, &I);
561 
562  // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E)
563  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
564  return replaceInstUsesWith(I, V);
565 
566  if (I.hasAllowReassoc()) {
567  // Reassociate constant RHS with another constant to form constant
568  // expression.
569  if (match(Op1, m_Constant(C)) && C->isFiniteNonZeroFP()) {
570  Constant *C1;
571  if (match(Op0, m_OneUse(m_FDiv(m_Constant(C1), m_Value(X))))) {
572  // (C1 / X) * C --> (C * C1) / X
573  Constant *CC1 =
574  ConstantFoldBinaryOpOperands(Instruction::FMul, C, C1, DL);
575  if (CC1 && CC1->isNormalFP())
576  return BinaryOperator::CreateFDivFMF(CC1, X, &I);
577  }
578  if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
579  // (X / C1) * C --> X * (C / C1)
580  Constant *CDivC1 =
581  ConstantFoldBinaryOpOperands(Instruction::FDiv, C, C1, DL);
582  if (CDivC1 && CDivC1->isNormalFP())
583  return BinaryOperator::CreateFMulFMF(X, CDivC1, &I);
584 
585  // If the constant was a denormal, try reassociating differently.
586  // (X / C1) * C --> X / (C1 / C)
587  Constant *C1DivC =
588  ConstantFoldBinaryOpOperands(Instruction::FDiv, C1, C, DL);
589  if (C1DivC && Op0->hasOneUse() && C1DivC->isNormalFP())
590  return BinaryOperator::CreateFDivFMF(X, C1DivC, &I);
591  }
592 
593  // We do not need to match 'fadd C, X' and 'fsub X, C' because they are
594  // canonicalized to 'fadd X, C'. Distributing the multiply may allow
595  // further folds and (X * C) + C2 is 'fma'.
596  if (match(Op0, m_OneUse(m_FAdd(m_Value(X), m_Constant(C1))))) {
597  // (X + C1) * C --> (X * C) + (C * C1)
599  Instruction::FMul, C, C1, DL)) {
600  Value *XC = Builder.CreateFMulFMF(X, C, &I);
601  return BinaryOperator::CreateFAddFMF(XC, CC1, &I);
602  }
603  }
604  if (match(Op0, m_OneUse(m_FSub(m_Constant(C1), m_Value(X))))) {
605  // (C1 - X) * C --> (C * C1) - (X * C)
607  Instruction::FMul, C, C1, DL)) {
608  Value *XC = Builder.CreateFMulFMF(X, C, &I);
609  return BinaryOperator::CreateFSubFMF(CC1, XC, &I);
610  }
611  }
612  }
613 
614  Value *Z;
616  m_Value(Z)))) {
617  // Sink division: (X / Y) * Z --> (X * Z) / Y
618  Value *NewFMul = Builder.CreateFMulFMF(X, Z, &I);
619  return BinaryOperator::CreateFDivFMF(NewFMul, Y, &I);
620  }
621 
622  // sqrt(X) * sqrt(Y) -> sqrt(X * Y)
623  // nnan disallows the possibility of returning a number if both operands are
624  // negative (in that case, we should return NaN).
625  if (I.hasNoNaNs() && match(Op0, m_OneUse(m_Sqrt(m_Value(X)))) &&
626  match(Op1, m_OneUse(m_Sqrt(m_Value(Y))))) {
627  Value *XY = Builder.CreateFMulFMF(X, Y, &I);
628  Value *Sqrt = Builder.CreateUnaryIntrinsic(Intrinsic::sqrt, XY, &I);
629  return replaceInstUsesWith(I, Sqrt);
630  }
631 
632  // The following transforms are done irrespective of the number of uses
633  // for the expression "1.0/sqrt(X)".
634  // 1) 1.0/sqrt(X) * X -> X/sqrt(X)
635  // 2) X * 1.0/sqrt(X) -> X/sqrt(X)
636  // We always expect the backend to reduce X/sqrt(X) to sqrt(X), if it
637  // has the necessary (reassoc) fast-math-flags.
638  if (I.hasNoSignedZeros() &&
639  match(Op0, (m_FDiv(m_SpecificFP(1.0), m_Value(Y)))) &&
640  match(Y, m_Sqrt(m_Value(X))) && Op1 == X)
641  return BinaryOperator::CreateFDivFMF(X, Y, &I);
642  if (I.hasNoSignedZeros() &&
643  match(Op1, (m_FDiv(m_SpecificFP(1.0), m_Value(Y)))) &&
644  match(Y, m_Sqrt(m_Value(X))) && Op0 == X)
645  return BinaryOperator::CreateFDivFMF(X, Y, &I);
646 
647  // Like the similar transform in instsimplify, this requires 'nsz' because
648  // sqrt(-0.0) = -0.0, and -0.0 * -0.0 does not simplify to -0.0.
649  if (I.hasNoNaNs() && I.hasNoSignedZeros() && Op0 == Op1 &&
650  Op0->hasNUses(2)) {
651  // Peek through fdiv to find squaring of square root:
652  // (X / sqrt(Y)) * (X / sqrt(Y)) --> (X * X) / Y
653  if (match(Op0, m_FDiv(m_Value(X), m_Sqrt(m_Value(Y))))) {
654  Value *XX = Builder.CreateFMulFMF(X, X, &I);
655  return BinaryOperator::CreateFDivFMF(XX, Y, &I);
656  }
657  // (sqrt(Y) / X) * (sqrt(Y) / X) --> Y / (X * X)
658  if (match(Op0, m_FDiv(m_Sqrt(m_Value(Y)), m_Value(X)))) {
659  Value *XX = Builder.CreateFMulFMF(X, X, &I);
660  return BinaryOperator::CreateFDivFMF(Y, XX, &I);
661  }
662  }
663 
664  if (I.isOnlyUserOfAnyOperand()) {
665  // pow(x, y) * pow(x, z) -> pow(x, y + z)
666  if (match(Op0, m_Intrinsic<Intrinsic::pow>(m_Value(X), m_Value(Y))) &&
667  match(Op1, m_Intrinsic<Intrinsic::pow>(m_Specific(X), m_Value(Z)))) {
668  auto *YZ = Builder.CreateFAddFMF(Y, Z, &I);
669  auto *NewPow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, X, YZ, &I);
670  return replaceInstUsesWith(I, NewPow);
671  }
672 
673  // powi(x, y) * powi(x, z) -> powi(x, y + z)
674  if (match(Op0, m_Intrinsic<Intrinsic::powi>(m_Value(X), m_Value(Y))) &&
675  match(Op1, m_Intrinsic<Intrinsic::powi>(m_Specific(X), m_Value(Z))) &&
676  Y->getType() == Z->getType()) {
677  auto *YZ = Builder.CreateAdd(Y, Z);
678  auto *NewPow = Builder.CreateIntrinsic(
679  Intrinsic::powi, {X->getType(), YZ->getType()}, {X, YZ}, &I);
680  return replaceInstUsesWith(I, NewPow);
681  }
682 
683  // exp(X) * exp(Y) -> exp(X + Y)
684  if (match(Op0, m_Intrinsic<Intrinsic::exp>(m_Value(X))) &&
685  match(Op1, m_Intrinsic<Intrinsic::exp>(m_Value(Y)))) {
686  Value *XY = Builder.CreateFAddFMF(X, Y, &I);
687  Value *Exp = Builder.CreateUnaryIntrinsic(Intrinsic::exp, XY, &I);
688  return replaceInstUsesWith(I, Exp);
689  }
690 
691  // exp2(X) * exp2(Y) -> exp2(X + Y)
692  if (match(Op0, m_Intrinsic<Intrinsic::exp2>(m_Value(X))) &&
693  match(Op1, m_Intrinsic<Intrinsic::exp2>(m_Value(Y)))) {
694  Value *XY = Builder.CreateFAddFMF(X, Y, &I);
695  Value *Exp2 = Builder.CreateUnaryIntrinsic(Intrinsic::exp2, XY, &I);
696  return replaceInstUsesWith(I, Exp2);
697  }
698  }
699 
700  // (X*Y) * X => (X*X) * Y where Y != X
701  // The purpose is two-fold:
702  // 1) to form a power expression (of X).
703  // 2) potentially shorten the critical path: After transformation, the
704  // latency of the instruction Y is amortized by the expression of X*X,
705  // and therefore Y is in a "less critical" position compared to what it
706  // was before the transformation.
707  if (match(Op0, m_OneUse(m_c_FMul(m_Specific(Op1), m_Value(Y)))) &&
708  Op1 != Y) {
709  Value *XX = Builder.CreateFMulFMF(Op1, Op1, &I);
710  return BinaryOperator::CreateFMulFMF(XX, Y, &I);
711  }
712  if (match(Op1, m_OneUse(m_c_FMul(m_Specific(Op0), m_Value(Y)))) &&
713  Op0 != Y) {
714  Value *XX = Builder.CreateFMulFMF(Op0, Op0, &I);
715  return BinaryOperator::CreateFMulFMF(XX, Y, &I);
716  }
717  }
718 
719  // log2(X * 0.5) * Y = log2(X) * Y - Y
720  if (I.isFast()) {
721  IntrinsicInst *Log2 = nullptr;
722  if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::log2>(
723  m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
724  Log2 = cast<IntrinsicInst>(Op0);
725  Y = Op1;
726  }
727  if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::log2>(
728  m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
729  Log2 = cast<IntrinsicInst>(Op1);
730  Y = Op0;
731  }
732  if (Log2) {
733  Value *Log2 = Builder.CreateUnaryIntrinsic(Intrinsic::log2, X, &I);
734  Value *LogXTimesY = Builder.CreateFMulFMF(Log2, Y, &I);
735  return BinaryOperator::CreateFSubFMF(LogXTimesY, Y, &I);
736  }
737  }
738 
739  // Simplify FMUL recurrences starting with 0.0 to 0.0 if nnan and nsz are set.
740  // Given a phi node with entry value as 0 and it used in fmul operation,
741  // we can replace fmul with 0 safely and eleminate loop operation.
742  PHINode *PN = nullptr;
743  Value *Start = nullptr, *Step = nullptr;
744  if (matchSimpleRecurrence(&I, PN, Start, Step) && I.hasNoNaNs() &&
745  I.hasNoSignedZeros() && match(Start, m_Zero()))
746  return replaceInstUsesWith(I, Start);
747 
748  return nullptr;
749 }
750 
751 /// Fold a divide or remainder with a select instruction divisor when one of the
752 /// select operands is zero. In that case, we can use the other select operand
753 /// because div/rem by zero is undefined.
755  SelectInst *SI = dyn_cast<SelectInst>(I.getOperand(1));
756  if (!SI)
757  return false;
758 
759  int NonNullOperand;
760  if (match(SI->getTrueValue(), m_Zero()))
761  // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
762  NonNullOperand = 2;
763  else if (match(SI->getFalseValue(), m_Zero()))
764  // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
765  NonNullOperand = 1;
766  else
767  return false;
768 
769  // Change the div/rem to use 'Y' instead of the select.
770  replaceOperand(I, 1, SI->getOperand(NonNullOperand));
771 
772  // Okay, we know we replace the operand of the div/rem with 'Y' with no
773  // problem. However, the select, or the condition of the select may have
774  // multiple uses. Based on our knowledge that the operand must be non-zero,
775  // propagate the known value for the select into other uses of it, and
776  // propagate a known value of the condition into its other users.
777 
778  // If the select and condition only have a single use, don't bother with this,
779  // early exit.
780  Value *SelectCond = SI->getCondition();
781  if (SI->use_empty() && SelectCond->hasOneUse())
782  return true;
783 
784  // Scan the current block backward, looking for other uses of SI.
785  BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin();
786  Type *CondTy = SelectCond->getType();
787  while (BBI != BBFront) {
788  --BBI;
789  // If we found an instruction that we can't assume will return, so
790  // information from below it cannot be propagated above it.
792  break;
793 
794  // Replace uses of the select or its condition with the known values.
795  for (Use &Op : BBI->operands()) {
796  if (Op == SI) {
797  replaceUse(Op, SI->getOperand(NonNullOperand));
798  Worklist.push(&*BBI);
799  } else if (Op == SelectCond) {
800  replaceUse(Op, NonNullOperand == 1 ? ConstantInt::getTrue(CondTy)
801  : ConstantInt::getFalse(CondTy));
802  Worklist.push(&*BBI);
803  }
804  }
805 
806  // If we past the instruction, quit looking for it.
807  if (&*BBI == SI)
808  SI = nullptr;
809  if (&*BBI == SelectCond)
810  SelectCond = nullptr;
811 
812  // If we ran out of things to eliminate, break out of the loop.
813  if (!SelectCond && !SI)
814  break;
815 
816  }
817  return true;
818 }
819 
820 /// True if the multiply can not be expressed in an int this size.
821 static bool multiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
822  bool IsSigned) {
823  bool Overflow;
824  Product = IsSigned ? C1.smul_ov(C2, Overflow) : C1.umul_ov(C2, Overflow);
825  return Overflow;
826 }
827 
828 /// True if C1 is a multiple of C2. Quotient contains C1/C2.
829 static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
830  bool IsSigned) {
831  assert(C1.getBitWidth() == C2.getBitWidth() && "Constant widths not equal");
832 
833  // Bail if we will divide by zero.
834  if (C2.isZero())
835  return false;
836 
837  // Bail if we would divide INT_MIN by -1.
838  if (IsSigned && C1.isMinSignedValue() && C2.isAllOnes())
839  return false;
840 
841  APInt Remainder(C1.getBitWidth(), /*val=*/0ULL, IsSigned);
842  if (IsSigned)
843  APInt::sdivrem(C1, C2, Quotient, Remainder);
844  else
845  APInt::udivrem(C1, C2, Quotient, Remainder);
846 
847  return Remainder.isMinValue();
848 }
849 
852  assert((I.getOpcode() == Instruction::SDiv ||
853  I.getOpcode() == Instruction::UDiv) &&
854  "Expected integer divide");
855 
856  bool IsSigned = I.getOpcode() == Instruction::SDiv;
857  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
858  Type *Ty = I.getType();
859 
860  Instruction *Ret = nullptr;
861  Value *X, *Y, *Z;
862 
863  // With appropriate no-wrap constraints, remove a common factor in the
864  // dividend and divisor that is disguised as a left-shifted value.
865  if (match(Op1, m_Shl(m_Value(X), m_Value(Z))) &&
866  match(Op0, m_c_Mul(m_Specific(X), m_Value(Y)))) {
867  // Both operands must have the matching no-wrap for this kind of division.
868  auto *Mul = cast<OverflowingBinaryOperator>(Op0);
869  auto *Shl = cast<OverflowingBinaryOperator>(Op1);
870  bool HasNUW = Mul->hasNoUnsignedWrap() && Shl->hasNoUnsignedWrap();
871  bool HasNSW = Mul->hasNoSignedWrap() && Shl->hasNoSignedWrap();
872 
873  // (X * Y) u/ (X << Z) --> Y u>> Z
874  if (!IsSigned && HasNUW)
875  Ret = BinaryOperator::CreateLShr(Y, Z);
876 
877  // (X * Y) s/ (X << Z) --> Y s/ (1 << Z)
878  if (IsSigned && HasNSW && (Op0->hasOneUse() || Op1->hasOneUse())) {
879  Value *Shl = Builder.CreateShl(ConstantInt::get(Ty, 1), Z);
880  Ret = BinaryOperator::CreateSDiv(Y, Shl);
881  }
882  }
883 
884  // With appropriate no-wrap constraints, remove a common factor in the
885  // dividend and divisor that is disguised as a left-shift amount.
886  if (match(Op0, m_Shl(m_Value(X), m_Value(Z))) &&
887  match(Op1, m_Shl(m_Value(Y), m_Specific(Z)))) {
888  auto *Shl0 = cast<OverflowingBinaryOperator>(Op0);
889  auto *Shl1 = cast<OverflowingBinaryOperator>(Op1);
890 
891  // For unsigned div, we need 'nuw' on both shifts.
892  // (X << Z) / (Y << Z) --> X / Y
893  if (!IsSigned && Shl0->hasNoUnsignedWrap() && Shl1->hasNoUnsignedWrap())
894  Ret = BinaryOperator::CreateUDiv(X, Y);
895 
896  // For signed div, we need 'nsw' on both shifts + 'nuw' on the divisor.
897  // (X << Z) / (Y << Z) --> X / Y
898  if (IsSigned && Shl0->hasNoSignedWrap() && Shl1->hasNoSignedWrap() &&
899  Shl1->hasNoUnsignedWrap())
900  Ret = BinaryOperator::CreateSDiv(X, Y);
901  }
902 
903  if (!Ret)
904  return nullptr;
905 
906  Ret->setIsExact(I.isExact());
907  return Ret;
908 }
909 
910 /// This function implements the transforms common to both integer division
911 /// instructions (udiv and sdiv). It is called by the visitors to those integer
912 /// division instructions.
913 /// Common integer divide transforms
915  if (Instruction *Phi = foldBinopWithPhiOperands(I))
916  return Phi;
917 
918  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
919  bool IsSigned = I.getOpcode() == Instruction::SDiv;
920  Type *Ty = I.getType();
921 
922  // The RHS is known non-zero.
923  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I))
924  return replaceOperand(I, 1, V);
925 
926  // Handle cases involving: [su]div X, (select Cond, Y, Z)
927  // This does not apply for fdiv.
928  if (simplifyDivRemOfSelectWithZeroOp(I))
929  return &I;
930 
931  // If the divisor is a select-of-constants, try to constant fold all div ops:
932  // C / (select Cond, TrueC, FalseC) --> select Cond, (C / TrueC), (C / FalseC)
933  // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
934  if (match(Op0, m_ImmConstant()) &&
936  if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1),
937  /*FoldWithMultiUse*/ true))
938  return R;
939  }
940 
941  const APInt *C2;
942  if (match(Op1, m_APInt(C2))) {
943  Value *X;
944  const APInt *C1;
945 
946  // (X / C1) / C2 -> X / (C1*C2)
947  if ((IsSigned && match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))) ||
948  (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_APInt(C1))))) {
949  APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
950  if (!multiplyOverflows(*C1, *C2, Product, IsSigned))
951  return BinaryOperator::Create(I.getOpcode(), X,
952  ConstantInt::get(Ty, Product));
953  }
954 
955  if ((IsSigned && match(Op0, m_NSWMul(m_Value(X), m_APInt(C1)))) ||
956  (!IsSigned && match(Op0, m_NUWMul(m_Value(X), m_APInt(C1))))) {
957  APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
958 
959  // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
960  if (isMultiple(*C2, *C1, Quotient, IsSigned)) {
961  auto *NewDiv = BinaryOperator::Create(I.getOpcode(), X,
962  ConstantInt::get(Ty, Quotient));
963  NewDiv->setIsExact(I.isExact());
964  return NewDiv;
965  }
966 
967  // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
968  if (isMultiple(*C1, *C2, Quotient, IsSigned)) {
970  ConstantInt::get(Ty, Quotient));
971  auto *OBO = cast<OverflowingBinaryOperator>(Op0);
972  Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
973  Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
974  return Mul;
975  }
976  }
977 
978  if ((IsSigned && match(Op0, m_NSWShl(m_Value(X), m_APInt(C1))) &&
979  C1->ult(C1->getBitWidth() - 1)) ||
980  (!IsSigned && match(Op0, m_NUWShl(m_Value(X), m_APInt(C1))) &&
981  C1->ult(C1->getBitWidth()))) {
982  APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
983  APInt C1Shifted = APInt::getOneBitSet(
984  C1->getBitWidth(), static_cast<unsigned>(C1->getZExtValue()));
985 
986  // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of 1 << C1.
987  if (isMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
988  auto *BO = BinaryOperator::Create(I.getOpcode(), X,
989  ConstantInt::get(Ty, Quotient));
990  BO->setIsExact(I.isExact());
991  return BO;
992  }
993 
994  // (X << C1) / C2 -> X * ((1 << C1) / C2) if 1 << C1 is a multiple of C2.
995  if (isMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
997  ConstantInt::get(Ty, Quotient));
998  auto *OBO = cast<OverflowingBinaryOperator>(Op0);
999  Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
1000  Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
1001  return Mul;
1002  }
1003  }
1004 
1005  if (!C2->isZero()) // avoid X udiv 0
1006  if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I))
1007  return FoldedDiv;
1008  }
1009 
1010  if (match(Op0, m_One())) {
1011  assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?");
1012  if (IsSigned) {
1013  // 1 / 0 --> undef ; 1 / 1 --> 1 ; 1 / -1 --> -1 ; 1 / anything else --> 0
1014  // (Op1 + 1) u< 3 ? Op1 : 0
1015  // Op1 must be frozen because we are increasing its number of uses.
1016  Value *F1 = Builder.CreateFreeze(Op1, Op1->getName() + ".fr");
1017  Value *Inc = Builder.CreateAdd(F1, Op0);
1018  Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(Ty, 3));
1019  return SelectInst::Create(Cmp, F1, ConstantInt::get(Ty, 0));
1020  } else {
1021  // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
1022  // result is one, otherwise it's zero.
1023  return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), Ty);
1024  }
1025  }
1026 
1027  // See if we can fold away this div instruction.
1028  if (SimplifyDemandedInstructionBits(I))
1029  return &I;
1030 
1031  // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
1032  Value *X, *Z;
1033  if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) // (X - Z) / Y; Y = Op1
1034  if ((IsSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
1035  (!IsSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
1036  return BinaryOperator::Create(I.getOpcode(), X, Op1);
1037 
1038  // (X << Y) / X -> 1 << Y
1039  Value *Y;
1040  if (IsSigned && match(Op0, m_NSWShl(m_Specific(Op1), m_Value(Y))))
1041  return BinaryOperator::CreateNSWShl(ConstantInt::get(Ty, 1), Y);
1042  if (!IsSigned && match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y))))
1043  return BinaryOperator::CreateNUWShl(ConstantInt::get(Ty, 1), Y);
1044 
1045  // X / (X * Y) -> 1 / Y if the multiplication does not overflow.
1046  if (match(Op1, m_c_Mul(m_Specific(Op0), m_Value(Y)))) {
1047  bool HasNSW = cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap();
1048  bool HasNUW = cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap();
1049  if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) {
1050  replaceOperand(I, 0, ConstantInt::get(Ty, 1));
1051  replaceOperand(I, 1, Y);
1052  return &I;
1053  }
1054  }
1055 
1056  if (Instruction *R = foldIDivShl(I, Builder))
1057  return R;
1058 
1059  // With the appropriate no-wrap constraint, remove a multiply by the divisor
1060  // after peeking through another divide:
1061  // ((Op1 * X) / Y) / Op1 --> X / Y
1062  if (match(Op0, m_BinOp(I.getOpcode(), m_c_Mul(m_Specific(Op1), m_Value(X)),
1063  m_Value(Y)))) {
1064  auto *InnerDiv = cast<PossiblyExactOperator>(Op0);
1065  auto *Mul = cast<OverflowingBinaryOperator>(InnerDiv->getOperand(0));
1066  Instruction *NewDiv = nullptr;
1067  if (!IsSigned && Mul->hasNoUnsignedWrap())
1068  NewDiv = BinaryOperator::CreateUDiv(X, Y);
1069  else if (IsSigned && Mul->hasNoSignedWrap())
1070  NewDiv = BinaryOperator::CreateSDiv(X, Y);
1071 
1072  // Exact propagates only if both of the original divides are exact.
1073  if (NewDiv) {
1074  NewDiv->setIsExact(I.isExact() && InnerDiv->isExact());
1075  return NewDiv;
1076  }
1077  }
1078 
1079  return nullptr;
1080 }
1081 
1082 static const unsigned MaxDepth = 6;
1083 
1084 // Take the exact integer log2 of the value. If DoFold is true, create the
1085 // actual instructions, otherwise return a non-null dummy value. Return nullptr
1086 // on failure.
1088  bool DoFold) {
1089  auto IfFold = [DoFold](function_ref<Value *()> Fn) {
1090  if (!DoFold)
1091  return reinterpret_cast<Value *>(-1);
1092  return Fn();
1093  };
1094 
1095  // FIXME: assert that Op1 isn't/doesn't contain undef.
1096 
1097  // log2(2^C) -> C
1098  if (match(Op, m_Power2()))
1099  return IfFold([&]() {
1100  Constant *C = ConstantExpr::getExactLogBase2(cast<Constant>(Op));
1101  if (!C)
1102  llvm_unreachable("Failed to constant fold udiv -> logbase2");
1103  return C;
1104  });
1105 
1106  // The remaining tests are all recursive, so bail out if we hit the limit.
1107  if (Depth++ == MaxDepth)
1108  return nullptr;
1109 
1110  // log2(zext X) -> zext log2(X)
1111  // FIXME: Require one use?
1112  Value *X, *Y;
1113  if (match(Op, m_ZExt(m_Value(X))))
1114  if (Value *LogX = takeLog2(Builder, X, Depth, DoFold))
1115  return IfFold([&]() { return Builder.CreateZExt(LogX, Op->getType()); });
1116 
1117  // log2(X << Y) -> log2(X) + Y
1118  // FIXME: Require one use unless X is 1?
1119  if (match(Op, m_Shl(m_Value(X), m_Value(Y))))
1120  if (Value *LogX = takeLog2(Builder, X, Depth, DoFold))
1121  return IfFold([&]() { return Builder.CreateAdd(LogX, Y); });
1122 
1123  // log2(Cond ? X : Y) -> Cond ? log2(X) : log2(Y)
1124  // FIXME: missed optimization: if one of the hands of select is/contains
1125  // undef, just directly pick the other one.
1126  // FIXME: can both hands contain undef?
1127  // FIXME: Require one use?
1128  if (SelectInst *SI = dyn_cast<SelectInst>(Op))
1129  if (Value *LogX = takeLog2(Builder, SI->getOperand(1), Depth, DoFold))
1130  if (Value *LogY = takeLog2(Builder, SI->getOperand(2), Depth, DoFold))
1131  return IfFold([&]() {
1132  return Builder.CreateSelect(SI->getOperand(0), LogX, LogY);
1133  });
1134 
1135  // log2(umin(X, Y)) -> umin(log2(X), log2(Y))
1136  // log2(umax(X, Y)) -> umax(log2(X), log2(Y))
1137  auto *MinMax = dyn_cast<MinMaxIntrinsic>(Op);
1138  if (MinMax && MinMax->hasOneUse() && !MinMax->isSigned())
1139  if (Value *LogX = takeLog2(Builder, MinMax->getLHS(), Depth, DoFold))
1140  if (Value *LogY = takeLog2(Builder, MinMax->getRHS(), Depth, DoFold))
1141  return IfFold([&]() {
1142  return Builder.CreateBinaryIntrinsic(
1143  MinMax->getIntrinsicID(), LogX, LogY);
1144  });
1145 
1146  return nullptr;
1147 }
1148 
1149 /// If we have zero-extended operands of an unsigned div or rem, we may be able
1150 /// to narrow the operation (sink the zext below the math).
1153  Instruction::BinaryOps Opcode = I.getOpcode();
1154  Value *N = I.getOperand(0);
1155  Value *D = I.getOperand(1);
1156  Type *Ty = I.getType();
1157  Value *X, *Y;
1158  if (match(N, m_ZExt(m_Value(X))) && match(D, m_ZExt(m_Value(Y))) &&
1159  X->getType() == Y->getType() && (N->hasOneUse() || D->hasOneUse())) {
1160  // udiv (zext X), (zext Y) --> zext (udiv X, Y)
1161  // urem (zext X), (zext Y) --> zext (urem X, Y)
1162  Value *NarrowOp = Builder.CreateBinOp(Opcode, X, Y);
1163  return new ZExtInst(NarrowOp, Ty);
1164  }
1165 
1166  Constant *C;
1167  if (isa<Instruction>(N) && match(N, m_OneUse(m_ZExt(m_Value(X)))) &&
1168  match(D, m_Constant(C))) {
1169  // If the constant is the same in the smaller type, use the narrow version.
1170  Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
1171  if (ConstantExpr::getZExt(TruncC, Ty) != C)
1172  return nullptr;
1173 
1174  // udiv (zext X), C --> zext (udiv X, C')
1175  // urem (zext X), C --> zext (urem X, C')
1176  return new ZExtInst(Builder.CreateBinOp(Opcode, X, TruncC), Ty);
1177  }
1178  if (isa<Instruction>(D) && match(D, m_OneUse(m_ZExt(m_Value(X)))) &&
1179  match(N, m_Constant(C))) {
1180  // If the constant is the same in the smaller type, use the narrow version.
1181  Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
1182  if (ConstantExpr::getZExt(TruncC, Ty) != C)
1183  return nullptr;
1184 
1185  // udiv C, (zext X) --> zext (udiv C', X)
1186  // urem C, (zext X) --> zext (urem C', X)
1187  return new ZExtInst(Builder.CreateBinOp(Opcode, TruncC, X), Ty);
1188  }
1189 
1190  return nullptr;
1191 }
1192 
1194  if (Value *V = simplifyUDivInst(I.getOperand(0), I.getOperand(1),
1195  SQ.getWithInstruction(&I)))
1196  return replaceInstUsesWith(I, V);
1197 
1198  if (Instruction *X = foldVectorBinop(I))
1199  return X;
1200 
1201  // Handle the integer div common cases
1202  if (Instruction *Common = commonIDivTransforms(I))
1203  return Common;
1204 
1205  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1206  Value *X;
1207  const APInt *C1, *C2;
1208  if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && match(Op1, m_APInt(C2))) {
1209  // (X lshr C1) udiv C2 --> X udiv (C2 << C1)
1210  bool Overflow;
1211  APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
1212  if (!Overflow) {
1213  bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value()));
1214  BinaryOperator *BO = BinaryOperator::CreateUDiv(
1215  X, ConstantInt::get(X->getType(), C2ShlC1));
1216  if (IsExact)
1217  BO->setIsExact();
1218  return BO;
1219  }
1220  }
1221 
1222  // Op0 / C where C is large (negative) --> zext (Op0 >= C)
1223  // TODO: Could use isKnownNegative() to handle non-constant values.
1224  Type *Ty = I.getType();
1225  if (match(Op1, m_Negative())) {
1226  Value *Cmp = Builder.CreateICmpUGE(Op0, Op1);
1227  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1228  }
1229  // Op0 / (sext i1 X) --> zext (Op0 == -1) (if X is 0, the div is undefined)
1230  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1231  Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1232  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1233  }
1234 
1235  if (Instruction *NarrowDiv = narrowUDivURem(I, Builder))
1236  return NarrowDiv;
1237 
1238  // If the udiv operands are non-overflowing multiplies with a common operand,
1239  // then eliminate the common factor:
1240  // (A * B) / (A * X) --> B / X (and commuted variants)
1241  // TODO: The code would be reduced if we had m_c_NUWMul pattern matching.
1242  // TODO: If -reassociation handled this generally, we could remove this.
1243  Value *A, *B;
1244  if (match(Op0, m_NUWMul(m_Value(A), m_Value(B)))) {
1245  if (match(Op1, m_NUWMul(m_Specific(A), m_Value(X))) ||
1246  match(Op1, m_NUWMul(m_Value(X), m_Specific(A))))
1247  return BinaryOperator::CreateUDiv(B, X);
1248  if (match(Op1, m_NUWMul(m_Specific(B), m_Value(X))) ||
1249  match(Op1, m_NUWMul(m_Value(X), m_Specific(B))))
1250  return BinaryOperator::CreateUDiv(A, X);
1251  }
1252 
1253  // Look through a right-shift to find the common factor:
1254  // ((Op1 *nuw A) >> B) / Op1 --> A >> B
1255  if (match(Op0, m_LShr(m_NUWMul(m_Specific(Op1), m_Value(A)), m_Value(B))) ||
1256  match(Op0, m_LShr(m_NUWMul(m_Value(A), m_Specific(Op1)), m_Value(B)))) {
1257  Instruction *Lshr = BinaryOperator::CreateLShr(A, B);
1258  if (I.isExact() && cast<PossiblyExactOperator>(Op0)->isExact())
1259  Lshr->setIsExact();
1260  return Lshr;
1261  }
1262 
1263  // Op1 udiv Op2 -> Op1 lshr log2(Op2), if log2() folds away.
1264  if (takeLog2(Builder, Op1, /*Depth*/0, /*DoFold*/false)) {
1265  Value *Res = takeLog2(Builder, Op1, /*Depth*/0, /*DoFold*/true);
1266  return replaceInstUsesWith(
1267  I, Builder.CreateLShr(Op0, Res, I.getName(), I.isExact()));
1268  }
1269 
1270  return nullptr;
1271 }
1272 
1274  if (Value *V = simplifySDivInst(I.getOperand(0), I.getOperand(1),
1275  SQ.getWithInstruction(&I)))
1276  return replaceInstUsesWith(I, V);
1277 
1278  if (Instruction *X = foldVectorBinop(I))
1279  return X;
1280 
1281  // Handle the integer div common cases
1282  if (Instruction *Common = commonIDivTransforms(I))
1283  return Common;
1284 
1285  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1286  Type *Ty = I.getType();
1287  Value *X;
1288  // sdiv Op0, -1 --> -Op0
1289  // sdiv Op0, (sext i1 X) --> -Op0 (because if X is 0, the op is undefined)
1290  if (match(Op1, m_AllOnes()) ||
1291  (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1292  return BinaryOperator::CreateNeg(Op0);
1293 
1294  // X / INT_MIN --> X == INT_MIN
1295  if (match(Op1, m_SignMask()))
1296  return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), Ty);
1297 
1298  if (I.isExact()) {
1299  // sdiv exact X, 1<<C --> ashr exact X, C iff 1<<C is non-negative
1300  if (match(Op1, m_Power2()) && match(Op1, m_NonNegative())) {
1301  Constant *C = ConstantExpr::getExactLogBase2(cast<Constant>(Op1));
1302  return BinaryOperator::CreateExactAShr(Op0, C);
1303  }
1304 
1305  // sdiv exact X, (1<<ShAmt) --> ashr exact X, ShAmt (if shl is non-negative)
1306  Value *ShAmt;
1307  if (match(Op1, m_NSWShl(m_One(), m_Value(ShAmt))))
1308  return BinaryOperator::CreateExactAShr(Op0, ShAmt);
1309 
1310  // sdiv exact X, -1<<C --> -(ashr exact X, C)
1311  if (match(Op1, m_NegatedPower2())) {
1312  Constant *NegPow2C = ConstantExpr::getNeg(cast<Constant>(Op1));
1314  Value *Ashr = Builder.CreateAShr(Op0, C, I.getName() + ".neg", true);
1315  return BinaryOperator::CreateNeg(Ashr);
1316  }
1317  }
1318 
1319  const APInt *Op1C;
1320  if (match(Op1, m_APInt(Op1C))) {
1321  // If the dividend is sign-extended and the constant divisor is small enough
1322  // to fit in the source type, shrink the division to the narrower type:
1323  // (sext X) sdiv C --> sext (X sdiv C)
1324  Value *Op0Src;
1325  if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
1326  Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) {
1327 
1328  // In the general case, we need to make sure that the dividend is not the
1329  // minimum signed value because dividing that by -1 is UB. But here, we
1330  // know that the -1 divisor case is already handled above.
1331 
1332  Constant *NarrowDivisor =
1333  ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
1334  Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
1335  return new SExtInst(NarrowOp, Ty);
1336  }
1337 
1338  // -X / C --> X / -C (if the negation doesn't overflow).
1339  // TODO: This could be enhanced to handle arbitrary vector constants by
1340  // checking if all elements are not the min-signed-val.
1341  if (!Op1C->isMinSignedValue() &&
1342  match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1343  Constant *NegC = ConstantInt::get(Ty, -(*Op1C));
1344  Instruction *BO = BinaryOperator::CreateSDiv(X, NegC);
1345  BO->setIsExact(I.isExact());
1346  return BO;
1347  }
1348  }
1349 
1350  // -X / Y --> -(X / Y)
1351  Value *Y;
1352  if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1354  Builder.CreateSDiv(X, Y, I.getName(), I.isExact()));
1355 
1356  // abs(X) / X --> X > -1 ? 1 : -1
1357  // X / abs(X) --> X > -1 ? 1 : -1
1358  if (match(&I, m_c_BinOp(
1359  m_OneUse(m_Intrinsic<Intrinsic::abs>(m_Value(X), m_One())),
1360  m_Deferred(X)))) {
1361  Value *Cond = Builder.CreateIsNotNeg(X);
1362  return SelectInst::Create(Cond, ConstantInt::get(Ty, 1),
1364  }
1365 
1366  KnownBits KnownDividend = computeKnownBits(Op0, 0, &I);
1367  if (!I.isExact() &&
1368  (match(Op1, m_Power2(Op1C)) || match(Op1, m_NegatedPower2(Op1C))) &&
1369  KnownDividend.countMinTrailingZeros() >= Op1C->countTrailingZeros()) {
1370  I.setIsExact();
1371  return &I;
1372  }
1373 
1374  if (KnownDividend.isNonNegative()) {
1375  // If both operands are unsigned, turn this into a udiv.
1376  if (isKnownNonNegative(Op1, DL, 0, &AC, &I, &DT)) {
1377  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1378  BO->setIsExact(I.isExact());
1379  return BO;
1380  }
1381 
1382  if (match(Op1, m_NegatedPower2())) {
1383  // X sdiv (-(1 << C)) -> -(X sdiv (1 << C)) ->
1384  // -> -(X udiv (1 << C)) -> -(X u>> C)
1386  ConstantExpr::getNeg(cast<Constant>(Op1)));
1387  Value *Shr = Builder.CreateLShr(Op0, CNegLog2, I.getName(), I.isExact());
1388  return BinaryOperator::CreateNeg(Shr);
1389  }
1390 
1391  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1392  // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1393  // Safe because the only negative value (1 << Y) can take on is
1394  // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1395  // the sign bit set.
1396  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1397  BO->setIsExact(I.isExact());
1398  return BO;
1399  }
1400  }
1401 
1402  return nullptr;
1403 }
1404 
1405 /// Remove negation and try to convert division into multiplication.
1406 Instruction *InstCombinerImpl::foldFDivConstantDivisor(BinaryOperator &I) {
1407  Constant *C;
1408  if (!match(I.getOperand(1), m_Constant(C)))
1409  return nullptr;
1410 
1411  // -X / C --> X / -C
1412  Value *X;
1413  const DataLayout &DL = I.getModule()->getDataLayout();
1414  if (match(I.getOperand(0), m_FNeg(m_Value(X))))
1415  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
1416  return BinaryOperator::CreateFDivFMF(X, NegC, &I);
1417 
1418  // nnan X / +0.0 -> copysign(inf, X)
1419  if (I.hasNoNaNs() && match(I.getOperand(1), m_Zero())) {
1420  IRBuilder<> B(&I);
1421  // TODO: nnan nsz X / -0.0 -> copysign(inf, X)
1422  CallInst *CopySign = B.CreateIntrinsic(
1423  Intrinsic::copysign, {C->getType()},
1424  {ConstantFP::getInfinity(I.getType()), I.getOperand(0)}, &I);
1425  CopySign->takeName(&I);
1426  return replaceInstUsesWith(I, CopySign);
1427  }
1428 
1429  // If the constant divisor has an exact inverse, this is always safe. If not,
1430  // then we can still create a reciprocal if fast-math-flags allow it and the
1431  // constant is a regular number (not zero, infinite, or denormal).
1432  if (!(C->hasExactInverseFP() || (I.hasAllowReciprocal() && C->isNormalFP())))
1433  return nullptr;
1434 
1435  // Disallow denormal constants because we don't know what would happen
1436  // on all targets.
1437  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1438  // denorms are flushed?
1439  auto *RecipC = ConstantFoldBinaryOpOperands(
1440  Instruction::FDiv, ConstantFP::get(I.getType(), 1.0), C, DL);
1441  if (!RecipC || !RecipC->isNormalFP())
1442  return nullptr;
1443 
1444  // X / C --> X * (1 / C)
1445  return BinaryOperator::CreateFMulFMF(I.getOperand(0), RecipC, &I);
1446 }
1447 
1448 /// Remove negation and try to reassociate constant math.
1450  Constant *C;
1451  if (!match(I.getOperand(0), m_Constant(C)))
1452  return nullptr;
1453 
1454  // C / -X --> -C / X
1455  Value *X;
1456  const DataLayout &DL = I.getModule()->getDataLayout();
1457  if (match(I.getOperand(1), m_FNeg(m_Value(X))))
1458  if (Constant *NegC = ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL))
1459  return BinaryOperator::CreateFDivFMF(NegC, X, &I);
1460 
1461  if (!I.hasAllowReassoc() || !I.hasAllowReciprocal())
1462  return nullptr;
1463 
1464  // Try to reassociate C / X expressions where X includes another constant.
1465  Constant *C2, *NewC = nullptr;
1466  if (match(I.getOperand(1), m_FMul(m_Value(X), m_Constant(C2)))) {
1467  // C / (X * C2) --> (C / C2) / X
1468  NewC = ConstantFoldBinaryOpOperands(Instruction::FDiv, C, C2, DL);
1469  } else if (match(I.getOperand(1), m_FDiv(m_Value(X), m_Constant(C2)))) {
1470  // C / (X / C2) --> (C * C2) / X
1471  NewC = ConstantFoldBinaryOpOperands(Instruction::FMul, C, C2, DL);
1472  }
1473  // Disallow denormal constants because we don't know what would happen
1474  // on all targets.
1475  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1476  // denorms are flushed?
1477  if (!NewC || !NewC->isNormalFP())
1478  return nullptr;
1479 
1480  return BinaryOperator::CreateFDivFMF(NewC, X, &I);
1481 }
1482 
1483 /// Negate the exponent of pow/exp to fold division-by-pow() into multiply.
1486  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1487  auto *II = dyn_cast<IntrinsicInst>(Op1);
1488  if (!II || !II->hasOneUse() || !I.hasAllowReassoc() ||
1489  !I.hasAllowReciprocal())
1490  return nullptr;
1491 
1492  // Z / pow(X, Y) --> Z * pow(X, -Y)
1493  // Z / exp{2}(Y) --> Z * exp{2}(-Y)
1494  // In the general case, this creates an extra instruction, but fmul allows
1495  // for better canonicalization and optimization than fdiv.
1496  Intrinsic::ID IID = II->getIntrinsicID();
1498  switch (IID) {
1499  case Intrinsic::pow:
1500  Args.push_back(II->getArgOperand(0));
1501  Args.push_back(Builder.CreateFNegFMF(II->getArgOperand(1), &I));
1502  break;
1503  case Intrinsic::powi: {
1504  // Require 'ninf' assuming that makes powi(X, -INT_MIN) acceptable.
1505  // That is, X ** (huge negative number) is 0.0, ~1.0, or INF and so
1506  // dividing by that is INF, ~1.0, or 0.0. Code that uses powi allows
1507  // non-standard results, so this corner case should be acceptable if the
1508  // code rules out INF values.
1509  if (!I.hasNoInfs())
1510  return nullptr;
1511  Args.push_back(II->getArgOperand(0));
1512  Args.push_back(Builder.CreateNeg(II->getArgOperand(1)));
1513  Type *Tys[] = {I.getType(), II->getArgOperand(1)->getType()};
1514  Value *Pow = Builder.CreateIntrinsic(IID, Tys, Args, &I);
1515  return BinaryOperator::CreateFMulFMF(Op0, Pow, &I);
1516  }
1517  case Intrinsic::exp:
1518  case Intrinsic::exp2:
1519  Args.push_back(Builder.CreateFNegFMF(II->getArgOperand(0), &I));
1520  break;
1521  default:
1522  return nullptr;
1523  }
1524  Value *Pow = Builder.CreateIntrinsic(IID, I.getType(), Args, &I);
1525  return BinaryOperator::CreateFMulFMF(Op0, Pow, &I);
1526 }
1527 
1529  Module *M = I.getModule();
1530 
1531  if (Value *V = simplifyFDivInst(I.getOperand(0), I.getOperand(1),
1532  I.getFastMathFlags(),
1533  SQ.getWithInstruction(&I)))
1534  return replaceInstUsesWith(I, V);
1535 
1536  if (Instruction *X = foldVectorBinop(I))
1537  return X;
1538 
1539  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1540  return Phi;
1541 
1542  if (Instruction *R = foldFDivConstantDivisor(I))
1543  return R;
1544 
1546  return R;
1547 
1548  if (Instruction *R = foldFPSignBitOps(I))
1549  return R;
1550 
1551  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1552  if (isa<Constant>(Op0))
1553  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1554  if (Instruction *R = FoldOpIntoSelect(I, SI))
1555  return R;
1556 
1557  if (isa<Constant>(Op1))
1558  if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1559  if (Instruction *R = FoldOpIntoSelect(I, SI))
1560  return R;
1561 
1562  if (I.hasAllowReassoc() && I.hasAllowReciprocal()) {
1563  Value *X, *Y;
1564  if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1565  (!isa<Constant>(Y) || !isa<Constant>(Op1))) {
1566  // (X / Y) / Z => X / (Y * Z)
1567  Value *YZ = Builder.CreateFMulFMF(Y, Op1, &I);
1568  return BinaryOperator::CreateFDivFMF(X, YZ, &I);
1569  }
1570  if (match(Op1, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1571  (!isa<Constant>(Y) || !isa<Constant>(Op0))) {
1572  // Z / (X / Y) => (Y * Z) / X
1573  Value *YZ = Builder.CreateFMulFMF(Y, Op0, &I);
1574  return BinaryOperator::CreateFDivFMF(YZ, X, &I);
1575  }
1576  // Z / (1.0 / Y) => (Y * Z)
1577  //
1578  // This is a special case of Z / (X / Y) => (Y * Z) / X, with X = 1.0. The
1579  // m_OneUse check is avoided because even in the case of the multiple uses
1580  // for 1.0/Y, the number of instructions remain the same and a division is
1581  // replaced by a multiplication.
1582  if (match(Op1, m_FDiv(m_SpecificFP(1.0), m_Value(Y))))
1583  return BinaryOperator::CreateFMulFMF(Y, Op0, &I);
1584  }
1585 
1586  if (I.hasAllowReassoc() && Op0->hasOneUse() && Op1->hasOneUse()) {
1587  // sin(X) / cos(X) -> tan(X)
1588  // cos(X) / sin(X) -> 1/tan(X) (cotangent)
1589  Value *X;
1590  bool IsTan = match(Op0, m_Intrinsic<Intrinsic::sin>(m_Value(X))) &&
1591  match(Op1, m_Intrinsic<Intrinsic::cos>(m_Specific(X)));
1592  bool IsCot =
1593  !IsTan && match(Op0, m_Intrinsic<Intrinsic::cos>(m_Value(X))) &&
1594  match(Op1, m_Intrinsic<Intrinsic::sin>(m_Specific(X)));
1595 
1596  if ((IsTan || IsCot) && hasFloatFn(M, &TLI, I.getType(), LibFunc_tan,
1597  LibFunc_tanf, LibFunc_tanl)) {
1598  IRBuilder<> B(&I);
1600  B.setFastMathFlags(I.getFastMathFlags());
1602  cast<CallBase>(Op0)->getCalledFunction()->getAttributes();
1603  Value *Res = emitUnaryFloatFnCall(X, &TLI, LibFunc_tan, LibFunc_tanf,
1604  LibFunc_tanl, B, Attrs);
1605  if (IsCot)
1606  Res = B.CreateFDiv(ConstantFP::get(I.getType(), 1.0), Res);
1607  return replaceInstUsesWith(I, Res);
1608  }
1609  }
1610 
1611  // X / (X * Y) --> 1.0 / Y
1612  // Reassociate to (X / X -> 1.0) is legal when NaNs are not allowed.
1613  // We can ignore the possibility that X is infinity because INF/INF is NaN.
1614  Value *X, *Y;
1615  if (I.hasNoNaNs() && I.hasAllowReassoc() &&
1616  match(Op1, m_c_FMul(m_Specific(Op0), m_Value(Y)))) {
1617  replaceOperand(I, 0, ConstantFP::get(I.getType(), 1.0));
1618  replaceOperand(I, 1, Y);
1619  return &I;
1620  }
1621 
1622  // X / fabs(X) -> copysign(1.0, X)
1623  // fabs(X) / X -> copysign(1.0, X)
1624  if (I.hasNoNaNs() && I.hasNoInfs() &&
1625  (match(&I, m_FDiv(m_Value(X), m_FAbs(m_Deferred(X)))) ||
1626  match(&I, m_FDiv(m_FAbs(m_Value(X)), m_Deferred(X))))) {
1627  Value *V = Builder.CreateBinaryIntrinsic(
1628  Intrinsic::copysign, ConstantFP::get(I.getType(), 1.0), X, &I);
1629  return replaceInstUsesWith(I, V);
1630  }
1631 
1633  return Mul;
1634 
1635  return nullptr;
1636 }
1637 
1638 /// This function implements the transforms common to both integer remainder
1639 /// instructions (urem and srem). It is called by the visitors to those integer
1640 /// remainder instructions.
1641 /// Common integer remainder transforms
1643  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1644  return Phi;
1645 
1646  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1647 
1648  // The RHS is known non-zero.
1649  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I))
1650  return replaceOperand(I, 1, V);
1651 
1652  // Handle cases involving: rem X, (select Cond, Y, Z)
1653  if (simplifyDivRemOfSelectWithZeroOp(I))
1654  return &I;
1655 
1656  // If the divisor is a select-of-constants, try to constant fold all rem ops:
1657  // C % (select Cond, TrueC, FalseC) --> select Cond, (C % TrueC), (C % FalseC)
1658  // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
1659  if (match(Op0, m_ImmConstant()) &&
1661  if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1),
1662  /*FoldWithMultiUse*/ true))
1663  return R;
1664  }
1665 
1666  if (isa<Constant>(Op1)) {
1667  if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1668  if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1669  if (Instruction *R = FoldOpIntoSelect(I, SI))
1670  return R;
1671  } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
1672  const APInt *Op1Int;
1673  if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
1674  (I.getOpcode() == Instruction::URem ||
1675  !Op1Int->isMinSignedValue())) {
1676  // foldOpIntoPhi will speculate instructions to the end of the PHI's
1677  // predecessor blocks, so do this only if we know the srem or urem
1678  // will not fault.
1679  if (Instruction *NV = foldOpIntoPhi(I, PN))
1680  return NV;
1681  }
1682  }
1683 
1684  // See if we can fold away this rem instruction.
1685  if (SimplifyDemandedInstructionBits(I))
1686  return &I;
1687  }
1688  }
1689 
1690  return nullptr;
1691 }
1692 
1694  if (Value *V = simplifyURemInst(I.getOperand(0), I.getOperand(1),
1695  SQ.getWithInstruction(&I)))
1696  return replaceInstUsesWith(I, V);
1697 
1698  if (Instruction *X = foldVectorBinop(I))
1699  return X;
1700 
1701  if (Instruction *common = commonIRemTransforms(I))
1702  return common;
1703 
1704  if (Instruction *NarrowRem = narrowUDivURem(I, Builder))
1705  return NarrowRem;
1706 
1707  // X urem Y -> X and Y-1, where Y is a power of 2,
1708  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1709  Type *Ty = I.getType();
1710  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1711  // This may increase instruction count, we don't enforce that Y is a
1712  // constant.
1714  Value *Add = Builder.CreateAdd(Op1, N1);
1715  return BinaryOperator::CreateAnd(Op0, Add);
1716  }
1717 
1718  // 1 urem X -> zext(X != 1)
1719  if (match(Op0, m_One())) {
1720  Value *Cmp = Builder.CreateICmpNE(Op1, ConstantInt::get(Ty, 1));
1721  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1722  }
1723 
1724  // Op0 urem C -> Op0 < C ? Op0 : Op0 - C, where C >= signbit.
1725  // Op0 must be frozen because we are increasing its number of uses.
1726  if (match(Op1, m_Negative())) {
1727  Value *F0 = Builder.CreateFreeze(Op0, Op0->getName() + ".fr");
1728  Value *Cmp = Builder.CreateICmpULT(F0, Op1);
1729  Value *Sub = Builder.CreateSub(F0, Op1);
1730  return SelectInst::Create(Cmp, F0, Sub);
1731  }
1732 
1733  // If the divisor is a sext of a boolean, then the divisor must be max
1734  // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also
1735  // max unsigned value. In that case, the remainder is 0:
1736  // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0
1737  Value *X;
1738  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1739  Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1740  return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), Op0);
1741  }
1742 
1743  return nullptr;
1744 }
1745 
1747  if (Value *V = simplifySRemInst(I.getOperand(0), I.getOperand(1),
1748  SQ.getWithInstruction(&I)))
1749  return replaceInstUsesWith(I, V);
1750 
1751  if (Instruction *X = foldVectorBinop(I))
1752  return X;
1753 
1754  // Handle the integer rem common cases
1755  if (Instruction *Common = commonIRemTransforms(I))
1756  return Common;
1757 
1758  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1759  {
1760  const APInt *Y;
1761  // X % -Y -> X % Y
1762  if (match(Op1, m_Negative(Y)) && !Y->isMinSignedValue())
1763  return replaceOperand(I, 1, ConstantInt::get(I.getType(), -*Y));
1764  }
1765 
1766  // -X srem Y --> -(X srem Y)
1767  Value *X, *Y;
1768  if (match(&I, m_SRem(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1769  return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y));
1770 
1771  // If the sign bits of both operands are zero (i.e. we can prove they are
1772  // unsigned inputs), turn this into a urem.
1773  APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
1774  if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1775  MaskedValueIsZero(Op0, Mask, 0, &I)) {
1776  // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1777  return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1778  }
1779 
1780  // If it's a constant vector, flip any negative values positive.
1781  if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1782  Constant *C = cast<Constant>(Op1);
1783  unsigned VWidth = cast<FixedVectorType>(C->getType())->getNumElements();
1784 
1785  bool hasNegative = false;
1786  bool hasMissing = false;
1787  for (unsigned i = 0; i != VWidth; ++i) {
1788  Constant *Elt = C->getAggregateElement(i);
1789  if (!Elt) {
1790  hasMissing = true;
1791  break;
1792  }
1793 
1794  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1795  if (RHS->isNegative())
1796  hasNegative = true;
1797  }
1798 
1799  if (hasNegative && !hasMissing) {
1800  SmallVector<Constant *, 16> Elts(VWidth);
1801  for (unsigned i = 0; i != VWidth; ++i) {
1802  Elts[i] = C->getAggregateElement(i); // Handle undef, etc.
1803  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1804  if (RHS->isNegative())
1805  Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1806  }
1807  }
1808 
1809  Constant *NewRHSV = ConstantVector::get(Elts);
1810  if (NewRHSV != C) // Don't loop on -MININT
1811  return replaceOperand(I, 1, NewRHSV);
1812  }
1813  }
1814 
1815  return nullptr;
1816 }
1817 
1819  if (Value *V = simplifyFRemInst(I.getOperand(0), I.getOperand(1),
1820  I.getFastMathFlags(),
1821  SQ.getWithInstruction(&I)))
1822  return replaceInstUsesWith(I, V);
1823 
1824  if (Instruction *X = foldVectorBinop(I))
1825  return X;
1826 
1827  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1828  return Phi;
1829 
1830  return nullptr;
1831 }
i
i
Definition: README.txt:29
llvm::simplifyFMulInst
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.
Definition: InstructionSimplify.cpp:5472
llvm::InstCombinerImpl::isKnownToBeAPowerOfTwo
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
Definition: InstCombineInternal.h:483
Attrs
Function Attrs
Definition: README_ALTIVEC.txt:215
llvm::PatternMatch::m_NonNegative
cst_pred_ty< is_nonnegative > m_NonNegative()
Match an integer or vector of non-negative values.
Definition: PatternMatch.h:485
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::Constant::isNormalFP
bool isNormalFP() const
Return true if this is a normal (as opposed to denormal, infinity, nan, or zero) floating-point scala...
Definition: Constants.cpp:221
llvm::haveNoCommonBitsSet
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if LHS and RHS have no common bits set.
Definition: ValueTracking.cpp:242
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::APInt::udivrem
static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Dual division/remainder interface.
Definition: APInt.cpp:1756
llvm::isKnownNonNegative
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
Definition: ValueTracking.cpp:322
llvm::ConstantFoldUnaryOpOperand
Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
Definition: ConstantFolding.cpp:1332
llvm::MaskedValueIsZero
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if 'V & Mask' is known to be zero.
Definition: ValueTracking.cpp:366
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
InstCombiner.h
llvm::PatternMatch::m_SpecificFP
specific_fpval m_SpecificFP(double V)
Match a specific floating point value or vector with all elements equal to the value.
Definition: PatternMatch.h:815
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
IntrinsicInst.h
llvm::PatternMatch::m_NegatedPower2
cst_pred_ty< is_negated_power2 > m_NegatedPower2()
Match a integer or vector negated power-of-2.
Definition: PatternMatch.h:552
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2092
llvm::BinaryOperator::CreateWithCopiedFlags
static BinaryOperator * CreateWithCopiedFlags(BinaryOps Opc, Value *V1, Value *V2, Instruction *CopyO, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: InstrTypes.h:249
llvm::SelectPatternResult::Flavor
SelectPatternFlavor Flavor
Definition: ValueTracking.h:711
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1117
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
llvm::APInt::getMinSignedBits
unsigned getMinSignedBits() const
NOTE: This is soft-deprecated. Please use getSignificantBits() instead.
Definition: APInt.h:1479
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
llvm::InstCombiner::Builder
BuilderTy & Builder
Definition: InstCombiner.h:58
llvm::emitUnaryFloatFnCall
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.
Definition: BuildLibCalls.cpp:1709
llvm::BinaryOperator::CreateFDivFMF
static BinaryOperator * CreateFDivFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:272
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
llvm::matchSimpleRecurrence
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,...
Definition: ValueTracking.cpp:6535
ErrorHandling.h
llvm::CmpInst::makeCmpResultType
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1044
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::InstCombinerImpl::visitSRem
Instruction * visitSRem(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1746
llvm::CastInst::Create
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
Definition: Instructions.cpp:3340
llvm::InstCombinerImpl::visitFDiv
Instruction * visitFDiv(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1528
ValueTracking.h
llvm::ConstantFP::getInfinity
static Constant * getInfinity(Type *Ty, bool Negative=false)
Definition: Constants.cpp:1033
APInt.h
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::PatternMatch::m_NUWShl
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1213
Shift
bool Shift
Definition: README.txt:468
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1431
foldMulShl1
static Value * foldMulShl1(BinaryOperator &Mul, bool CommuteOperands, InstCombiner::BuilderTy &Builder)
Reduce integer multiplication patterns that contain a (+/-1 << Z) factor.
Definition: InstCombineMulDivRem.cpp:145
llvm::AttributeList
Definition: Attributes.h:430
llvm::Instruction::setHasNoUnsignedWrap
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:153
llvm::simplifySDivInst
Value * simplifySDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an SDiv, fold the result or return null.
Definition: InstructionSimplify.cpp:1241
llvm::PatternMatch::m_BinOp
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::PatternMatch::m_AShr
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1123
Operator.h
llvm::ConstantExpr::getExactLogBase2
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:2685
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::matchSelectPattern
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
Definition: ValueTracking.cpp:6397
llvm::BinaryOperator::CreateNeg
NUW NUW NUW NUW Exact static Exact BinaryOperator * CreateNeg(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Helper functions to construct and inspect unary operations (NEG and NOT) via binary operators SUB and...
Definition: Instructions.cpp:2952
llvm::PatternMatch::m_Not
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
Definition: PatternMatch.h:2289
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:687
llvm::Instruction::setIsExact
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:161
llvm::APInt::isMinValue
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:402
isMultiple
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.
Definition: InstCombineMulDivRem.cpp:829
llvm::PatternMatch::m_Deferred
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:790
llvm::PatternMatch::m_FDiv
BinaryOp_match< LHS, RHS, Instruction::FDiv > m_FDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1069
llvm::PatternMatch::m_FAdd
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:985
llvm::PatternMatch::m_FSub
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:997
llvm::KnownBits::countMinTrailingZeros
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
Definition: KnownBits.h:233
llvm::PatternMatch::m_OneUse
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
Instruction.h
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:278
simplifyValueKnownNonZero
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.
Definition: InstCombineMulDivRem.cpp:46
llvm::SPF_NABS
@ SPF_NABS
Absolute value.
Definition: ValueTracking.h:696
llvm::PatternMatch::m_c_BinOp
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
Definition: PatternMatch.h:2215
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::KnownBits::isNonNegative
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
foldMulSelectToNegate
static Value * foldMulSelectToNegate(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineMulDivRem.cpp:99
llvm::InstCombinerImpl::commonIRemTransforms
Instruction * commonIRemTransforms(BinaryOperator &I)
This function implements the transforms common to both integer remainder instructions (urem and srem)...
Definition: InstCombineMulDivRem.cpp:1642
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1767
llvm::RecurKind::And
@ And
Bitwise or logical AND of integers.
InstCombineInternal.h
llvm::PatternMatch::m_Select
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
Definition: PatternMatch.h:1462
llvm::PatternMatch::m_ZExtOrSExt
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, CastClass_match< OpTy, Instruction::SExt > > m_ZExtOrSExt(const OpTy &Op)
Definition: PatternMatch.h:1648
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::APInt::isZero
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:359
llvm::Instruction::setHasNoSignedWrap
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:157
llvm::ConstantFoldBinaryOpOperands
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
Definition: ConstantFolding.cpp:1339
llvm::PatternMatch::m_Exact
Exact_match< T > m_Exact(const T &SubPattern)
Definition: PatternMatch.h:1351
llvm::PatternMatch::m_SpecificIntAllowUndef
specific_intval< true > m_SpecificIntAllowUndef(APInt V)
Definition: PatternMatch.h:862
llvm::simplifySRemInst
Value * simplifySRemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an SRem, fold the result or return null.
Definition: InstructionSimplify.cpp:1273
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
InstrTypes.h
llvm::Log2
unsigned Log2(Align A)
Returns the log2 of the alignment.
Definition: Alignment.h:209
llvm::simplifyFDivInst
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.
Definition: InstructionSimplify.cpp:5539
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::PatternMatch::m_PosZeroFP
cstfp_pred_ty< is_pos_zero_fp > m_PosZeroFP()
Match a floating-point positive zero.
Definition: PatternMatch.h:673
InstructionWorklist.h
SI
@ SI
Definition: SIInstrInfo.cpp:7882
llvm::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1629
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::PatternMatch::m_FNeg
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
Definition: PatternMatch.h:1033
llvm::Constant::getAllOnesValue
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:395
llvm::PatternMatch::m_SDiv
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1063
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:392
llvm::simplifyFRemInst
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.
Definition: InstructionSimplify.cpp:5577
llvm::Instruction
Definition: Instruction.h:42
llvm::PatternMatch::m_NSWMul
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1172
llvm::Type::getScalarSizeInBits
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition: Type.cpp:189
llvm::APInt::isAllOnes
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:347
foldIDivShl
static Instruction * foldIDivShl(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineMulDivRem.cpp:850
llvm::InstCombinerImpl
Definition: InstCombineInternal.h:61
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:879
llvm::PatternMatch::m_NSWSub
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1164
llvm::PatternMatch::m_URem
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1075
PatternMatch.h
llvm::APInt::countTrailingZeros
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1563
llvm::PatternMatch::m_APIntAllowUndef
apint_match m_APIntAllowUndef(const APInt *&Res)
Match APInt while allowing undefs in splat vector constants.
Definition: PatternMatch.h:284
Type.h
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::PatternMatch::m_One
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:517
llvm::Function::getAttributes
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:314
llvm::PatternMatch::m_Power2
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:544
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::APInt::getOneBitSet
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:222
llvm::ConstantExpr::getTrunc
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2064
BasicBlock.h
llvm::simplifyUDivInst
Value * simplifyUDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a UDiv, fold the result or return null.
Definition: InstructionSimplify.cpp:1252
llvm::PatternMatch::m_Zero
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:537
llvm::MipsISD::Ext
@ Ext
Definition: MipsISelLowering.h:159
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::hasNoSignedWrap
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
Definition: Instruction.cpp:169
llvm::UnaryOperator::CreateFNegFMF
static UnaryOperator * CreateFNegFMF(Value *Op, Instruction *FMFSource, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: InstrTypes.h:164
llvm::BinaryOperator::CreateFMulFMF
static BinaryOperator * CreateFMulFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:267
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::Instruction::hasNoUnsignedWrap
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
Definition: Instruction.cpp:165
llvm::APInt::sdivrem
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition: APInt.cpp:1888
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1099
llvm::PatternMatch::m_AllOnes
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:453
llvm::hasFloatFn
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.
Definition: BuildLibCalls.cpp:1377
llvm::PatternMatch::m_ImmConstant
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:751
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::SystemZISD::XC
@ XC
Definition: SystemZISelLowering.h:123
llvm::ConstantExpr::getShl
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2668
llvm::InstCombinerImpl::commonIDivTransforms
Instruction * commonIDivTransforms(BinaryOperator &I)
This function implements the transforms common to both integer division instructions (udiv and sdiv).
Definition: InstCombineMulDivRem.cpp:914
llvm::PatternMatch::m_FAbs
m_Intrinsic_Ty< Opnd0 >::Ty m_FAbs(const Opnd0 &Op0)
Definition: PatternMatch.h:2171
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1093
llvm::PatternMatch::m_SRem
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1081
llvm::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Definition: ValueTracking.cpp:197
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PatternMatch::m_Sub
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:991
llvm::SPF_ABS
@ SPF_ABS
Floating point maxnum.
Definition: ValueTracking.h:695
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1736
llvm::PatternMatch::m_Negative
cst_pred_ty< is_negative > m_Negative()
Match an integer or vector of negative values.
Definition: PatternMatch.h:475
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::PatternMatch::m_Constant
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:144
llvm::InstCombinerImpl::simplifyDivRemOfSelectWithZeroOp
bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I)
Fold a divide or remainder with a select instruction divisor when one of the select operands is zero.
Definition: InstCombineMulDivRem.cpp:754
llvm::InstCombinerImpl::visitSDiv
Instruction * visitSDiv(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1273
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4849
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
foldFDivConstantDividend
static Instruction * foldFDivConstantDividend(BinaryOperator &I)
Remove negation and try to reassociate constant math.
Definition: InstCombineMulDivRem.cpp:1449
llvm::PatternMatch::m_SExt
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:1623
llvm::PatternMatch::m_NUWMul
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1205
llvm::BinaryOperator
Definition: InstrTypes.h:188
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:138
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Constant::getAggregateElement
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:410
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::MinMax
Definition: AssumeBundleQueries.h:71
llvm::IRBuilderBase
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:93
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::InstCombinerImpl::visitFMul
Instruction * visitFMul(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:519
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1348
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4888
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:834
MaxDepth
static const unsigned MaxDepth
Definition: InstCombineMulDivRem.cpp:1082
llvm::InstCombinerImpl::visitURem
Instruction * visitURem(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1693
llvm::simplifyMulInst
Value * simplifyMulInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a Mul, fold the result or return null.
Definition: InstructionSimplify.cpp:982
Constant.h
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:827
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
llvm::KnownBits
Definition: KnownBits.h:23
llvm::PatternMatch::m_UDiv
BinaryOp_match< LHS, RHS, Instruction::UDiv > m_UDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1057
llvm::APInt::isMinSignedValue
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:408
llvm::BinaryOperator::CreateFAddFMF
static BinaryOperator * CreateFAddFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:257
llvm::InstCombinerImpl::visitFRem
Instruction * visitFRem(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1818
llvm::PatternMatch::m_Sqrt
m_Intrinsic_Ty< Opnd0 >::Ty m_Sqrt(const Opnd0 &Op0)
Definition: PatternMatch.h:2205
llvm::ConstantExpr::getNeg
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2617
llvm::InstCombinerImpl::visitMul
Instruction * visitMul(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:188
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::Negator::Negate
static Value * Negate(bool LHSIsZero, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
Definition: InstCombineNegator.cpp:530
llvm::ConstantInt::getBool
static ConstantInt * getBool(LLVMContext &Context, bool V)
Definition: Constants.cpp:841
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:216
llvm::ConstantFP::get
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:926
llvm::isGuaranteedToTransferExecutionToSuccessor
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
Definition: ValueTracking.cpp:5471
Casting.h
llvm::PatternMatch::m_SignMask
cst_pred_ty< is_sign_mask > m_SignMask()
Match an integer or vector with only the sign bit(s) set.
Definition: PatternMatch.h:576
llvm::Value::hasNUses
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
Definition: Value.cpp:148
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::BinaryOperator::CreateNSWNeg
static BinaryOperator * CreateNSWNeg(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: Instructions.cpp:2968
llvm::PatternMatch::m_NSWShl
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1180
llvm::ARCCC::Z
@ Z
Definition: ARCInfo.h:41
foldFDivPowDivisor
static Instruction * foldFDivPowDivisor(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Negate the exponent of pow/exp to fold division-by-pow() into multiply.
Definition: InstCombineMulDivRem.cpp:1484
powi
This is blocked on not handling X *X *X powi(X, 3)(see note above). The issue is that we end up getting t
llvm::log2
static double log2(double V)
Definition: AMDGPULibCalls.cpp:794
llvm::PatternMatch::m_c_Mul
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.
Definition: PatternMatch.h:2244
takeLog2
static Value * takeLog2(IRBuilderBase &Builder, Value *Op, unsigned Depth, bool DoFold)
Definition: InstCombineMulDivRem.cpp:1087
hasNoSignedWrap
static bool hasNoSignedWrap(BinaryOperator &I)
Definition: InstructionCombining.cpp:306
multiplyOverflows
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.
Definition: InstCombineMulDivRem.cpp:821
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
llvm::InstCombinerImpl::replaceOperand
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
Definition: InstCombineInternal.h:429
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:788
llvm::APInt::getSignMask
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:209
llvm::PatternMatch::m_c_FMul
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.
Definition: PatternMatch.h:2364
Instructions.h
SmallVector.h
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:772
CreateMul
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:253
N
#define N
llvm::IRBuilderBase::CreateShl
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1322
InstructionSimplify.h
llvm::PHINode
Definition: Instructions.h:2698
llvm::Constant::isNotMinSignedValue
bool isNotMinSignedValue() const
Return true if the value is not the smallest signed value, or, for vectors, does not contain smallest...
Definition: Constants.cpp:172
llvm::PatternMatch::m_Neg
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
Definition: PatternMatch.h:2273
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1473
llvm::isKnownToBeAPowerOfTwo
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to have exactly one bit set when defined.
Definition: ValueTracking.cpp:302
llvm::IRBuilderBase::CreateSub
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1250
CreateAdd
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:241
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:381
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:394
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::CastInst::CreateZExtOrBitCast
static CastInst * CreateZExtOrBitCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a ZExt or BitCast cast instruction.
Definition: Instructions.cpp:3384
llvm::simplifyURemInst
Value * simplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a URem, fold the result or return null.
Definition: InstructionSimplify.cpp:1284
llvm::BinaryOperator::Create
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
Definition: Instructions.cpp:2936
llvm::PatternMatch::m_FMul
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1051
Value.h
llvm::abs
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1297
llvm::Instruction::isExact
bool isExact() const LLVM_READONLY
Determine whether the exact flag is set.
Definition: Instruction.cpp:225
BuildLibCalls.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::PatternMatch::m_Shl
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1111
llvm::APInt::ushl_ov
APInt ushl_ov(const APInt &Amt, bool &Overflow) const
Definition: APInt.cpp:1999
llvm::InstCombinerImpl::visitUDiv
Instruction * visitUDiv(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1193
narrowUDivURem
static Instruction * narrowUDivURem(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
If we have zero-extended operands of an unsigned div or rem, we may be able to narrow the operation (...
Definition: InstCombineMulDivRem.cpp:1151
llvm::BinaryOperator::CreateFSubFMF
static BinaryOperator * CreateFSubFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:262
llvm::PatternMatch::m_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1045
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:39