LLVM  15.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"
18 #include "llvm/IR/BasicBlock.h"
19 #include "llvm/IR/Constant.h"
20 #include "llvm/IR/Constants.h"
21 #include "llvm/IR/InstrTypes.h"
22 #include "llvm/IR/Instruction.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/IntrinsicInst.h"
25 #include "llvm/IR/Intrinsics.h"
26 #include "llvm/IR/Operator.h"
27 #include "llvm/IR/PatternMatch.h"
28 #include "llvm/IR/Type.h"
29 #include "llvm/IR/Value.h"
30 #include "llvm/Support/Casting.h"
34 #include <cassert>
35 
36 #define DEBUG_TYPE "instcombine"
38 
39 using namespace llvm;
40 using namespace PatternMatch;
41 
42 /// The specific integer value is used in a context where it is known to be
43 /// non-zero. If this allows us to simplify the computation, do so and return
44 /// the new operand, otherwise return null.
46  Instruction &CxtI) {
47  // If V has multiple uses, then we would have to do more analysis to determine
48  // if this is safe. For example, the use could be in dynamically unreached
49  // code.
50  if (!V->hasOneUse()) return nullptr;
51 
52  bool MadeChange = false;
53 
54  // ((1 << A) >>u B) --> (1 << (A-B))
55  // Because V cannot be zero, we know that B is less than A.
56  Value *A = nullptr, *B = nullptr, *One = nullptr;
57  if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) &&
58  match(One, m_One())) {
59  A = IC.Builder.CreateSub(A, B);
60  return IC.Builder.CreateShl(One, A);
61  }
62 
63  // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
64  // inexact. Similarly for <<.
65  BinaryOperator *I = dyn_cast<BinaryOperator>(V);
66  if (I && I->isLogicalShift() &&
67  IC.isKnownToBeAPowerOfTwo(I->getOperand(0), false, 0, &CxtI)) {
68  // We know that this is an exact/nuw shift and that the input is a
69  // non-zero context as well.
70  if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) {
71  IC.replaceOperand(*I, 0, V2);
72  MadeChange = true;
73  }
74 
75  if (I->getOpcode() == Instruction::LShr && !I->isExact()) {
76  I->setIsExact();
77  MadeChange = true;
78  }
79 
80  if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) {
81  I->setHasNoUnsignedWrap();
82  MadeChange = true;
83  }
84  }
85 
86  // TODO: Lots more we could do here:
87  // If V is a phi node, we can call this on each of its operands.
88  // "select cond, X, 0" can simplify to "X".
89 
90  return MadeChange ? V : nullptr;
91 }
92 
93 // TODO: This is a specific form of a much more general pattern.
94 // We could detect a select with any binop identity constant, or we
95 // could use SimplifyBinOp to see if either arm of the select reduces.
96 // But that needs to be done carefully and/or while removing potential
97 // reverse canonicalizations as in InstCombiner::foldSelectIntoOp().
100  Value *Cond, *OtherOp;
101 
102  // mul (select Cond, 1, -1), OtherOp --> select Cond, OtherOp, -OtherOp
103  // mul OtherOp, (select Cond, 1, -1) --> select Cond, OtherOp, -OtherOp
105  m_Value(OtherOp)))) {
106  bool HasAnyNoWrap = I.hasNoSignedWrap() || I.hasNoUnsignedWrap();
107  Value *Neg = Builder.CreateNeg(OtherOp, "", false, HasAnyNoWrap);
108  return Builder.CreateSelect(Cond, OtherOp, Neg);
109  }
110  // mul (select Cond, -1, 1), OtherOp --> select Cond, -OtherOp, OtherOp
111  // mul OtherOp, (select Cond, -1, 1) --> select Cond, -OtherOp, OtherOp
113  m_Value(OtherOp)))) {
114  bool HasAnyNoWrap = I.hasNoSignedWrap() || I.hasNoUnsignedWrap();
115  Value *Neg = Builder.CreateNeg(OtherOp, "", false, HasAnyNoWrap);
116  return Builder.CreateSelect(Cond, Neg, OtherOp);
117  }
118 
119  // fmul (select Cond, 1.0, -1.0), OtherOp --> select Cond, OtherOp, -OtherOp
120  // fmul OtherOp, (select Cond, 1.0, -1.0) --> select Cond, OtherOp, -OtherOp
122  m_SpecificFP(-1.0))),
123  m_Value(OtherOp)))) {
125  Builder.setFastMathFlags(I.getFastMathFlags());
126  return Builder.CreateSelect(Cond, OtherOp, Builder.CreateFNeg(OtherOp));
127  }
128 
129  // fmul (select Cond, -1.0, 1.0), OtherOp --> select Cond, -OtherOp, OtherOp
130  // fmul OtherOp, (select Cond, -1.0, 1.0) --> select Cond, -OtherOp, OtherOp
132  m_SpecificFP(1.0))),
133  m_Value(OtherOp)))) {
135  Builder.setFastMathFlags(I.getFastMathFlags());
136  return Builder.CreateSelect(Cond, Builder.CreateFNeg(OtherOp), OtherOp);
137  }
138 
139  return nullptr;
140 }
141 
143  if (Value *V = SimplifyMulInst(I.getOperand(0), I.getOperand(1),
144  SQ.getWithInstruction(&I)))
145  return replaceInstUsesWith(I, V);
146 
147  if (SimplifyAssociativeOrCommutative(I))
148  return &I;
149 
150  if (Instruction *X = foldVectorBinop(I))
151  return X;
152 
153  if (Instruction *Phi = foldBinopWithPhiOperands(I))
154  return Phi;
155 
156  if (Value *V = SimplifyUsingDistributiveLaws(I))
157  return replaceInstUsesWith(I, V);
158 
159  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
160  unsigned BitWidth = I.getType()->getScalarSizeInBits();
161 
162  // X * -1 == 0 - X
163  if (match(Op1, m_AllOnes())) {
164  BinaryOperator *BO = BinaryOperator::CreateNeg(Op0, I.getName());
165  if (I.hasNoSignedWrap())
166  BO->setHasNoSignedWrap();
167  return BO;
168  }
169 
170  // Also allow combining multiply instructions on vectors.
171  {
172  Value *NewOp;
173  Constant *C1, *C2;
174  const APInt *IVal;
175  if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
176  m_Constant(C1))) &&
177  match(C1, m_APInt(IVal))) {
178  // ((X << C2)*C1) == (X * (C1 << C2))
179  Constant *Shl = ConstantExpr::getShl(C1, C2);
180  BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0));
181  BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl);
182  if (I.hasNoUnsignedWrap() && Mul->hasNoUnsignedWrap())
183  BO->setHasNoUnsignedWrap();
184  if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap() &&
185  Shl->isNotMinSignedValue())
186  BO->setHasNoSignedWrap();
187  return BO;
188  }
189 
190  if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
191  // Replace X*(2^C) with X << C, where C is either a scalar or a vector.
192  if (Constant *NewCst = ConstantExpr::getExactLogBase2(C1)) {
193  BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
194 
195  if (I.hasNoUnsignedWrap())
196  Shl->setHasNoUnsignedWrap();
197  if (I.hasNoSignedWrap()) {
198  const APInt *V;
199  if (match(NewCst, m_APInt(V)) && *V != V->getBitWidth() - 1)
200  Shl->setHasNoSignedWrap();
201  }
202 
203  return Shl;
204  }
205  }
206  }
207 
208  if (Op0->hasOneUse() && match(Op1, m_NegatedPower2())) {
209  // Interpret X * (-1<<C) as (-X) * (1<<C) and try to sink the negation.
210  // The "* (1<<C)" thus becomes a potential shifting opportunity.
211  if (Value *NegOp0 = Negator::Negate(/*IsNegation*/ true, Op0, *this))
213  NegOp0, ConstantExpr::getNeg(cast<Constant>(Op1)), I.getName());
214  }
215 
216  if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
217  return FoldedMul;
218 
219  if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
220  return replaceInstUsesWith(I, FoldedMul);
221 
222  // Simplify mul instructions with a constant RHS.
223  if (isa<Constant>(Op1)) {
224  // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
225  Value *X;
226  Constant *C1;
227  if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) {
228  Value *Mul = Builder.CreateMul(C1, Op1);
229  // Only go forward with the transform if C1*CI simplifies to a tidier
230  // constant.
231  if (!match(Mul, m_Mul(m_Value(), m_Value())))
232  return BinaryOperator::CreateAdd(Builder.CreateMul(X, Op1), Mul);
233  }
234  }
235 
236  // abs(X) * abs(X) -> X * X
237  // nabs(X) * nabs(X) -> X * X
238  if (Op0 == Op1) {
239  Value *X, *Y;
241  if (SPF == SPF_ABS || SPF == SPF_NABS)
242  return BinaryOperator::CreateMul(X, X);
243 
244  if (match(Op0, m_Intrinsic<Intrinsic::abs>(m_Value(X))))
245  return BinaryOperator::CreateMul(X, X);
246  }
247 
248  // -X * C --> X * -C
249  Value *X, *Y;
250  Constant *Op1C;
251  if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Constant(Op1C)))
253 
254  // -X * -Y --> X * Y
255  if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Neg(m_Value(Y)))) {
256  auto *NewMul = BinaryOperator::CreateMul(X, Y);
257  if (I.hasNoSignedWrap() &&
258  cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap() &&
259  cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap())
260  NewMul->setHasNoSignedWrap();
261  return NewMul;
262  }
263 
264  // -X * Y --> -(X * Y)
265  // X * -Y --> -(X * Y)
266  if (match(&I, m_c_Mul(m_OneUse(m_Neg(m_Value(X))), m_Value(Y))))
267  return BinaryOperator::CreateNeg(Builder.CreateMul(X, Y));
268 
269  // (X / Y) * Y = X - (X % Y)
270  // (X / Y) * -Y = (X % Y) - X
271  {
272  Value *Y = Op1;
273  BinaryOperator *Div = dyn_cast<BinaryOperator>(Op0);
274  if (!Div || (Div->getOpcode() != Instruction::UDiv &&
275  Div->getOpcode() != Instruction::SDiv)) {
276  Y = Op0;
277  Div = dyn_cast<BinaryOperator>(Op1);
278  }
279  Value *Neg = dyn_castNegVal(Y);
280  if (Div && Div->hasOneUse() &&
281  (Div->getOperand(1) == Y || Div->getOperand(1) == Neg) &&
282  (Div->getOpcode() == Instruction::UDiv ||
283  Div->getOpcode() == Instruction::SDiv)) {
284  Value *X = Div->getOperand(0), *DivOp1 = Div->getOperand(1);
285 
286  // If the division is exact, X % Y is zero, so we end up with X or -X.
287  if (Div->isExact()) {
288  if (DivOp1 == Y)
289  return replaceInstUsesWith(I, X);
291  }
292 
293  auto RemOpc = Div->getOpcode() == Instruction::UDiv ? Instruction::URem
294  : Instruction::SRem;
295  // X must be frozen because we are increasing its number of uses.
296  Value *XFreeze = Builder.CreateFreeze(X, X->getName() + ".fr");
297  Value *Rem = Builder.CreateBinOp(RemOpc, XFreeze, DivOp1);
298  if (DivOp1 == Y)
299  return BinaryOperator::CreateSub(XFreeze, Rem);
300  return BinaryOperator::CreateSub(Rem, XFreeze);
301  }
302  }
303 
304  /// i1 mul -> i1 and.
305  if (I.getType()->isIntOrIntVectorTy(1))
306  return BinaryOperator::CreateAnd(Op0, Op1);
307 
308  // X*(1 << Y) --> X << Y
309  // (1 << Y)*X --> X << Y
310  {
311  Value *Y;
312  BinaryOperator *BO = nullptr;
313  bool ShlNSW = false;
314  if (match(Op0, m_Shl(m_One(), m_Value(Y)))) {
315  BO = BinaryOperator::CreateShl(Op1, Y);
316  ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap();
317  } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) {
318  BO = BinaryOperator::CreateShl(Op0, Y);
319  ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap();
320  }
321  if (BO) {
322  if (I.hasNoUnsignedWrap())
323  BO->setHasNoUnsignedWrap();
324  if (I.hasNoSignedWrap() && ShlNSW)
325  BO->setHasNoSignedWrap();
326  return BO;
327  }
328  }
329 
330  // (zext bool X) * (zext bool Y) --> zext (and X, Y)
331  // (sext bool X) * (sext bool Y) --> zext (and X, Y)
332  // Note: -1 * -1 == 1 * 1 == 1 (if the extends match, the result is the same)
333  if (((match(Op0, m_ZExt(m_Value(X))) && match(Op1, m_ZExt(m_Value(Y)))) ||
334  (match(Op0, m_SExt(m_Value(X))) && match(Op1, m_SExt(m_Value(Y))))) &&
335  X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType() &&
336  (Op0->hasOneUse() || Op1->hasOneUse() || X == Y)) {
337  Value *And = Builder.CreateAnd(X, Y, "mulbool");
338  return CastInst::Create(Instruction::ZExt, And, I.getType());
339  }
340  // (sext bool X) * (zext bool Y) --> sext (and X, Y)
341  // (zext bool X) * (sext bool Y) --> sext (and X, Y)
342  // Note: -1 * 1 == 1 * -1 == -1
343  if (((match(Op0, m_SExt(m_Value(X))) && match(Op1, m_ZExt(m_Value(Y)))) ||
344  (match(Op0, m_ZExt(m_Value(X))) && match(Op1, m_SExt(m_Value(Y))))) &&
345  X->getType()->isIntOrIntVectorTy(1) && X->getType() == Y->getType() &&
346  (Op0->hasOneUse() || Op1->hasOneUse())) {
347  Value *And = Builder.CreateAnd(X, Y, "mulbool");
348  return CastInst::Create(Instruction::SExt, And, I.getType());
349  }
350 
351  // (zext bool X) * Y --> X ? Y : 0
352  // Y * (zext bool X) --> X ? Y : 0
353  if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
354  return SelectInst::Create(X, Op1, ConstantInt::get(I.getType(), 0));
355  if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
356  return SelectInst::Create(X, Op0, ConstantInt::get(I.getType(), 0));
357 
358  // (sext bool X) * C --> X ? -C : 0
359  Constant *ImmC;
360  if (match(Op0, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1) &&
361  match(Op1, m_ImmConstant(ImmC))) {
362  Constant *NegC = ConstantExpr::getNeg(ImmC);
363  return SelectInst::Create(X, NegC, ConstantInt::getNullValue(I.getType()));
364  }
365 
366  // (lshr X, 31) * Y --> (ashr X, 31) & Y
367  // Y * (lshr X, 31) --> (ashr X, 31) & Y
368  // TODO: We are not checking one-use because the elimination of the multiply
369  // is better for analysis?
370  // TODO: Should we canonicalize to '(X < 0) ? Y : 0' instead? That would be
371  // more similar to what we're doing above.
372  const APInt *C;
373  if (match(Op0, m_LShr(m_Value(X), m_APInt(C))) && *C == C->getBitWidth() - 1)
374  return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op1);
375  if (match(Op1, m_LShr(m_Value(X), m_APInt(C))) && *C == C->getBitWidth() - 1)
376  return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op0);
377 
378  // ((ashr X, 31) | 1) * X --> abs(X)
379  // X * ((ashr X, 31) | 1) --> abs(X)
382  m_One()),
383  m_Deferred(X)))) {
384  Value *Abs = Builder.CreateBinaryIntrinsic(
385  Intrinsic::abs, X,
386  ConstantInt::getBool(I.getContext(), I.hasNoSignedWrap()));
387  Abs->takeName(&I);
388  return replaceInstUsesWith(I, Abs);
389  }
390 
391  if (Instruction *Ext = narrowMathIfNoOverflow(I))
392  return Ext;
393 
394  bool Changed = false;
395  if (!I.hasNoSignedWrap() && willNotOverflowSignedMul(Op0, Op1, I)) {
396  Changed = true;
397  I.setHasNoSignedWrap(true);
398  }
399 
400  if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedMul(Op0, Op1, I)) {
401  Changed = true;
402  I.setHasNoUnsignedWrap(true);
403  }
404 
405  return Changed ? &I : nullptr;
406 }
407 
408 Instruction *InstCombinerImpl::foldFPSignBitOps(BinaryOperator &I) {
409  BinaryOperator::BinaryOps Opcode = I.getOpcode();
410  assert((Opcode == Instruction::FMul || Opcode == Instruction::FDiv) &&
411  "Expected fmul or fdiv");
412 
413  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
414  Value *X, *Y;
415 
416  // -X * -Y --> X * Y
417  // -X / -Y --> X / Y
418  if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y))))
419  return BinaryOperator::CreateWithCopiedFlags(Opcode, X, Y, &I);
420 
421  // fabs(X) * fabs(X) -> X * X
422  // fabs(X) / fabs(X) -> X / X
423  if (Op0 == Op1 && match(Op0, m_FAbs(m_Value(X))))
424  return BinaryOperator::CreateWithCopiedFlags(Opcode, X, X, &I);
425 
426  // fabs(X) * fabs(Y) --> fabs(X * Y)
427  // fabs(X) / fabs(Y) --> fabs(X / Y)
428  if (match(Op0, m_FAbs(m_Value(X))) && match(Op1, m_FAbs(m_Value(Y))) &&
429  (Op0->hasOneUse() || Op1->hasOneUse())) {
431  Builder.setFastMathFlags(I.getFastMathFlags());
432  Value *XY = Builder.CreateBinOp(Opcode, X, Y);
433  Value *Fabs = Builder.CreateUnaryIntrinsic(Intrinsic::fabs, XY);
434  Fabs->takeName(&I);
435  return replaceInstUsesWith(I, Fabs);
436  }
437 
438  return nullptr;
439 }
440 
442  if (Value *V = SimplifyFMulInst(I.getOperand(0), I.getOperand(1),
443  I.getFastMathFlags(),
444  SQ.getWithInstruction(&I)))
445  return replaceInstUsesWith(I, V);
446 
447  if (SimplifyAssociativeOrCommutative(I))
448  return &I;
449 
450  if (Instruction *X = foldVectorBinop(I))
451  return X;
452 
453  if (Instruction *Phi = foldBinopWithPhiOperands(I))
454  return Phi;
455 
456  if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
457  return FoldedMul;
458 
459  if (Value *FoldedMul = foldMulSelectToNegate(I, Builder))
460  return replaceInstUsesWith(I, FoldedMul);
461 
462  if (Instruction *R = foldFPSignBitOps(I))
463  return R;
464 
465  // X * -1.0 --> -X
466  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
467  if (match(Op1, m_SpecificFP(-1.0)))
468  return UnaryOperator::CreateFNegFMF(Op0, &I);
469 
470  // -X * C --> X * -C
471  Value *X, *Y;
472  Constant *C;
473  if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_Constant(C)))
475 
476  // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E)
477  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
478  return replaceInstUsesWith(I, V);
479 
480  if (I.hasAllowReassoc()) {
481  // Reassociate constant RHS with another constant to form constant
482  // expression.
483  if (match(Op1, m_Constant(C)) && C->isFiniteNonZeroFP()) {
484  Constant *C1;
485  if (match(Op0, m_OneUse(m_FDiv(m_Constant(C1), m_Value(X))))) {
486  // (C1 / X) * C --> (C * C1) / X
488  if (CC1->isNormalFP())
489  return BinaryOperator::CreateFDivFMF(CC1, X, &I);
490  }
491  if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
492  // (X / C1) * C --> X * (C / C1)
493  Constant *CDivC1 = ConstantExpr::getFDiv(C, C1);
494  if (CDivC1->isNormalFP())
495  return BinaryOperator::CreateFMulFMF(X, CDivC1, &I);
496 
497  // If the constant was a denormal, try reassociating differently.
498  // (X / C1) * C --> X / (C1 / C)
499  Constant *C1DivC = ConstantExpr::getFDiv(C1, C);
500  if (Op0->hasOneUse() && C1DivC->isNormalFP())
501  return BinaryOperator::CreateFDivFMF(X, C1DivC, &I);
502  }
503 
504  // We do not need to match 'fadd C, X' and 'fsub X, C' because they are
505  // canonicalized to 'fadd X, C'. Distributing the multiply may allow
506  // further folds and (X * C) + C2 is 'fma'.
507  if (match(Op0, m_OneUse(m_FAdd(m_Value(X), m_Constant(C1))))) {
508  // (X + C1) * C --> (X * C) + (C * C1)
510  Value *XC = Builder.CreateFMulFMF(X, C, &I);
511  return BinaryOperator::CreateFAddFMF(XC, CC1, &I);
512  }
513  if (match(Op0, m_OneUse(m_FSub(m_Constant(C1), m_Value(X))))) {
514  // (C1 - X) * C --> (C * C1) - (X * C)
516  Value *XC = Builder.CreateFMulFMF(X, C, &I);
517  return BinaryOperator::CreateFSubFMF(CC1, XC, &I);
518  }
519  }
520 
521  Value *Z;
523  m_Value(Z)))) {
524  // Sink division: (X / Y) * Z --> (X * Z) / Y
525  Value *NewFMul = Builder.CreateFMulFMF(X, Z, &I);
526  return BinaryOperator::CreateFDivFMF(NewFMul, Y, &I);
527  }
528 
529  // sqrt(X) * sqrt(Y) -> sqrt(X * Y)
530  // nnan disallows the possibility of returning a number if both operands are
531  // negative (in that case, we should return NaN).
532  if (I.hasNoNaNs() &&
533  match(Op0, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(X)))) &&
534  match(Op1, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) {
535  Value *XY = Builder.CreateFMulFMF(X, Y, &I);
536  Value *Sqrt = Builder.CreateUnaryIntrinsic(Intrinsic::sqrt, XY, &I);
537  return replaceInstUsesWith(I, Sqrt);
538  }
539 
540  // The following transforms are done irrespective of the number of uses
541  // for the expression "1.0/sqrt(X)".
542  // 1) 1.0/sqrt(X) * X -> X/sqrt(X)
543  // 2) X * 1.0/sqrt(X) -> X/sqrt(X)
544  // We always expect the backend to reduce X/sqrt(X) to sqrt(X), if it
545  // has the necessary (reassoc) fast-math-flags.
546  if (I.hasNoSignedZeros() &&
547  match(Op0, (m_FDiv(m_SpecificFP(1.0), m_Value(Y)))) &&
548  match(Y, m_Intrinsic<Intrinsic::sqrt>(m_Value(X))) && Op1 == X)
549  return BinaryOperator::CreateFDivFMF(X, Y, &I);
550  if (I.hasNoSignedZeros() &&
551  match(Op1, (m_FDiv(m_SpecificFP(1.0), m_Value(Y)))) &&
552  match(Y, m_Intrinsic<Intrinsic::sqrt>(m_Value(X))) && Op0 == X)
553  return BinaryOperator::CreateFDivFMF(X, Y, &I);
554 
555  // Like the similar transform in instsimplify, this requires 'nsz' because
556  // sqrt(-0.0) = -0.0, and -0.0 * -0.0 does not simplify to -0.0.
557  if (I.hasNoNaNs() && I.hasNoSignedZeros() && Op0 == Op1 &&
558  Op0->hasNUses(2)) {
559  // Peek through fdiv to find squaring of square root:
560  // (X / sqrt(Y)) * (X / sqrt(Y)) --> (X * X) / Y
561  if (match(Op0, m_FDiv(m_Value(X),
562  m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) {
563  Value *XX = Builder.CreateFMulFMF(X, X, &I);
564  return BinaryOperator::CreateFDivFMF(XX, Y, &I);
565  }
566  // (sqrt(Y) / X) * (sqrt(Y) / X) --> Y / (X * X)
567  if (match(Op0, m_FDiv(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y)),
568  m_Value(X)))) {
569  Value *XX = Builder.CreateFMulFMF(X, X, &I);
570  return BinaryOperator::CreateFDivFMF(Y, XX, &I);
571  }
572  }
573 
574  if (I.isOnlyUserOfAnyOperand()) {
575  // pow(x, y) * pow(x, z) -> pow(x, y + z)
576  if (match(Op0, m_Intrinsic<Intrinsic::pow>(m_Value(X), m_Value(Y))) &&
577  match(Op1, m_Intrinsic<Intrinsic::pow>(m_Specific(X), m_Value(Z)))) {
578  auto *YZ = Builder.CreateFAddFMF(Y, Z, &I);
579  auto *NewPow = Builder.CreateBinaryIntrinsic(Intrinsic::pow, X, YZ, &I);
580  return replaceInstUsesWith(I, NewPow);
581  }
582 
583  // powi(x, y) * powi(x, z) -> powi(x, y + z)
584  if (match(Op0, m_Intrinsic<Intrinsic::powi>(m_Value(X), m_Value(Y))) &&
585  match(Op1, m_Intrinsic<Intrinsic::powi>(m_Specific(X), m_Value(Z))) &&
586  Y->getType() == Z->getType()) {
587  auto *YZ = Builder.CreateAdd(Y, Z);
588  auto *NewPow = Builder.CreateIntrinsic(
589  Intrinsic::powi, {X->getType(), YZ->getType()}, {X, YZ}, &I);
590  return replaceInstUsesWith(I, NewPow);
591  }
592 
593  // exp(X) * exp(Y) -> exp(X + Y)
594  if (match(Op0, m_Intrinsic<Intrinsic::exp>(m_Value(X))) &&
595  match(Op1, m_Intrinsic<Intrinsic::exp>(m_Value(Y)))) {
596  Value *XY = Builder.CreateFAddFMF(X, Y, &I);
597  Value *Exp = Builder.CreateUnaryIntrinsic(Intrinsic::exp, XY, &I);
598  return replaceInstUsesWith(I, Exp);
599  }
600 
601  // exp2(X) * exp2(Y) -> exp2(X + Y)
602  if (match(Op0, m_Intrinsic<Intrinsic::exp2>(m_Value(X))) &&
603  match(Op1, m_Intrinsic<Intrinsic::exp2>(m_Value(Y)))) {
604  Value *XY = Builder.CreateFAddFMF(X, Y, &I);
605  Value *Exp2 = Builder.CreateUnaryIntrinsic(Intrinsic::exp2, XY, &I);
606  return replaceInstUsesWith(I, Exp2);
607  }
608  }
609 
610  // (X*Y) * X => (X*X) * Y where Y != X
611  // The purpose is two-fold:
612  // 1) to form a power expression (of X).
613  // 2) potentially shorten the critical path: After transformation, the
614  // latency of the instruction Y is amortized by the expression of X*X,
615  // and therefore Y is in a "less critical" position compared to what it
616  // was before the transformation.
617  if (match(Op0, m_OneUse(m_c_FMul(m_Specific(Op1), m_Value(Y)))) &&
618  Op1 != Y) {
619  Value *XX = Builder.CreateFMulFMF(Op1, Op1, &I);
620  return BinaryOperator::CreateFMulFMF(XX, Y, &I);
621  }
622  if (match(Op1, m_OneUse(m_c_FMul(m_Specific(Op0), m_Value(Y)))) &&
623  Op0 != Y) {
624  Value *XX = Builder.CreateFMulFMF(Op0, Op0, &I);
625  return BinaryOperator::CreateFMulFMF(XX, Y, &I);
626  }
627  }
628 
629  // log2(X * 0.5) * Y = log2(X) * Y - Y
630  if (I.isFast()) {
631  IntrinsicInst *Log2 = nullptr;
632  if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::log2>(
633  m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
634  Log2 = cast<IntrinsicInst>(Op0);
635  Y = Op1;
636  }
637  if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::log2>(
638  m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
639  Log2 = cast<IntrinsicInst>(Op1);
640  Y = Op0;
641  }
642  if (Log2) {
643  Value *Log2 = Builder.CreateUnaryIntrinsic(Intrinsic::log2, X, &I);
644  Value *LogXTimesY = Builder.CreateFMulFMF(Log2, Y, &I);
645  return BinaryOperator::CreateFSubFMF(LogXTimesY, Y, &I);
646  }
647  }
648 
649  return nullptr;
650 }
651 
652 /// Fold a divide or remainder with a select instruction divisor when one of the
653 /// select operands is zero. In that case, we can use the other select operand
654 /// because div/rem by zero is undefined.
656  SelectInst *SI = dyn_cast<SelectInst>(I.getOperand(1));
657  if (!SI)
658  return false;
659 
660  int NonNullOperand;
661  if (match(SI->getTrueValue(), m_Zero()))
662  // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
663  NonNullOperand = 2;
664  else if (match(SI->getFalseValue(), m_Zero()))
665  // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
666  NonNullOperand = 1;
667  else
668  return false;
669 
670  // Change the div/rem to use 'Y' instead of the select.
671  replaceOperand(I, 1, SI->getOperand(NonNullOperand));
672 
673  // Okay, we know we replace the operand of the div/rem with 'Y' with no
674  // problem. However, the select, or the condition of the select may have
675  // multiple uses. Based on our knowledge that the operand must be non-zero,
676  // propagate the known value for the select into other uses of it, and
677  // propagate a known value of the condition into its other users.
678 
679  // If the select and condition only have a single use, don't bother with this,
680  // early exit.
681  Value *SelectCond = SI->getCondition();
682  if (SI->use_empty() && SelectCond->hasOneUse())
683  return true;
684 
685  // Scan the current block backward, looking for other uses of SI.
686  BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin();
687  Type *CondTy = SelectCond->getType();
688  while (BBI != BBFront) {
689  --BBI;
690  // If we found an instruction that we can't assume will return, so
691  // information from below it cannot be propagated above it.
693  break;
694 
695  // Replace uses of the select or its condition with the known values.
696  for (Use &Op : BBI->operands()) {
697  if (Op == SI) {
698  replaceUse(Op, SI->getOperand(NonNullOperand));
699  Worklist.push(&*BBI);
700  } else if (Op == SelectCond) {
701  replaceUse(Op, NonNullOperand == 1 ? ConstantInt::getTrue(CondTy)
702  : ConstantInt::getFalse(CondTy));
703  Worklist.push(&*BBI);
704  }
705  }
706 
707  // If we past the instruction, quit looking for it.
708  if (&*BBI == SI)
709  SI = nullptr;
710  if (&*BBI == SelectCond)
711  SelectCond = nullptr;
712 
713  // If we ran out of things to eliminate, break out of the loop.
714  if (!SelectCond && !SI)
715  break;
716 
717  }
718  return true;
719 }
720 
721 /// True if the multiply can not be expressed in an int this size.
722 static bool multiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
723  bool IsSigned) {
724  bool Overflow;
725  Product = IsSigned ? C1.smul_ov(C2, Overflow) : C1.umul_ov(C2, Overflow);
726  return Overflow;
727 }
728 
729 /// True if C1 is a multiple of C2. Quotient contains C1/C2.
730 static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
731  bool IsSigned) {
732  assert(C1.getBitWidth() == C2.getBitWidth() && "Constant widths not equal");
733 
734  // Bail if we will divide by zero.
735  if (C2.isZero())
736  return false;
737 
738  // Bail if we would divide INT_MIN by -1.
739  if (IsSigned && C1.isMinSignedValue() && C2.isAllOnes())
740  return false;
741 
742  APInt Remainder(C1.getBitWidth(), /*val=*/0ULL, IsSigned);
743  if (IsSigned)
744  APInt::sdivrem(C1, C2, Quotient, Remainder);
745  else
746  APInt::udivrem(C1, C2, Quotient, Remainder);
747 
748  return Remainder.isMinValue();
749 }
750 
751 /// This function implements the transforms common to both integer division
752 /// instructions (udiv and sdiv). It is called by the visitors to those integer
753 /// division instructions.
754 /// Common integer divide transforms
756  if (Instruction *Phi = foldBinopWithPhiOperands(I))
757  return Phi;
758 
759  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
760  bool IsSigned = I.getOpcode() == Instruction::SDiv;
761  Type *Ty = I.getType();
762 
763  // The RHS is known non-zero.
764  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I))
765  return replaceOperand(I, 1, V);
766 
767  // Handle cases involving: [su]div X, (select Cond, Y, Z)
768  // This does not apply for fdiv.
769  if (simplifyDivRemOfSelectWithZeroOp(I))
770  return &I;
771 
772  // If the divisor is a select-of-constants, try to constant fold all div ops:
773  // C / (select Cond, TrueC, FalseC) --> select Cond, (C / TrueC), (C / FalseC)
774  // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
775  if (match(Op0, m_ImmConstant()) &&
777  if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1),
778  /*FoldWithMultiUse*/ true))
779  return R;
780  }
781 
782  const APInt *C2;
783  if (match(Op1, m_APInt(C2))) {
784  Value *X;
785  const APInt *C1;
786 
787  // (X / C1) / C2 -> X / (C1*C2)
788  if ((IsSigned && match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))) ||
789  (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_APInt(C1))))) {
790  APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
791  if (!multiplyOverflows(*C1, *C2, Product, IsSigned))
792  return BinaryOperator::Create(I.getOpcode(), X,
793  ConstantInt::get(Ty, Product));
794  }
795 
796  if ((IsSigned && match(Op0, m_NSWMul(m_Value(X), m_APInt(C1)))) ||
797  (!IsSigned && match(Op0, m_NUWMul(m_Value(X), m_APInt(C1))))) {
798  APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
799 
800  // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
801  if (isMultiple(*C2, *C1, Quotient, IsSigned)) {
802  auto *NewDiv = BinaryOperator::Create(I.getOpcode(), X,
803  ConstantInt::get(Ty, Quotient));
804  NewDiv->setIsExact(I.isExact());
805  return NewDiv;
806  }
807 
808  // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
809  if (isMultiple(*C1, *C2, Quotient, IsSigned)) {
811  ConstantInt::get(Ty, Quotient));
812  auto *OBO = cast<OverflowingBinaryOperator>(Op0);
813  Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
814  Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
815  return Mul;
816  }
817  }
818 
819  if ((IsSigned && match(Op0, m_NSWShl(m_Value(X), m_APInt(C1))) &&
820  C1->ult(C1->getBitWidth() - 1)) ||
821  (!IsSigned && match(Op0, m_NUWShl(m_Value(X), m_APInt(C1))) &&
822  C1->ult(C1->getBitWidth()))) {
823  APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
824  APInt C1Shifted = APInt::getOneBitSet(
825  C1->getBitWidth(), static_cast<unsigned>(C1->getZExtValue()));
826 
827  // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of 1 << C1.
828  if (isMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
829  auto *BO = BinaryOperator::Create(I.getOpcode(), X,
830  ConstantInt::get(Ty, Quotient));
831  BO->setIsExact(I.isExact());
832  return BO;
833  }
834 
835  // (X << C1) / C2 -> X * ((1 << C1) / C2) if 1 << C1 is a multiple of C2.
836  if (isMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
838  ConstantInt::get(Ty, Quotient));
839  auto *OBO = cast<OverflowingBinaryOperator>(Op0);
840  Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
841  Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
842  return Mul;
843  }
844  }
845 
846  if (!C2->isZero()) // avoid X udiv 0
847  if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I))
848  return FoldedDiv;
849  }
850 
851  if (match(Op0, m_One())) {
852  assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?");
853  if (IsSigned) {
854  // 1 / 0 --> undef ; 1 / 1 --> 1 ; 1 / -1 --> -1 ; 1 / anything else --> 0
855  // (Op1 + 1) u< 3 ? Op1 : 0
856  // Op1 must be frozen because we are increasing its number of uses.
857  Value *F1 = Builder.CreateFreeze(Op1, Op1->getName() + ".fr");
858  Value *Inc = Builder.CreateAdd(F1, Op0);
859  Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(Ty, 3));
860  return SelectInst::Create(Cmp, F1, ConstantInt::get(Ty, 0));
861  } else {
862  // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
863  // result is one, otherwise it's zero.
864  return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), Ty);
865  }
866  }
867 
868  // See if we can fold away this div instruction.
869  if (SimplifyDemandedInstructionBits(I))
870  return &I;
871 
872  // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
873  Value *X, *Z;
874  if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) // (X - Z) / Y; Y = Op1
875  if ((IsSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
876  (!IsSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
877  return BinaryOperator::Create(I.getOpcode(), X, Op1);
878 
879  // (X << Y) / X -> 1 << Y
880  Value *Y;
881  if (IsSigned && match(Op0, m_NSWShl(m_Specific(Op1), m_Value(Y))))
882  return BinaryOperator::CreateNSWShl(ConstantInt::get(Ty, 1), Y);
883  if (!IsSigned && match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y))))
884  return BinaryOperator::CreateNUWShl(ConstantInt::get(Ty, 1), Y);
885 
886  // X / (X * Y) -> 1 / Y if the multiplication does not overflow.
887  if (match(Op1, m_c_Mul(m_Specific(Op0), m_Value(Y)))) {
888  bool HasNSW = cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap();
889  bool HasNUW = cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap();
890  if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) {
891  replaceOperand(I, 0, ConstantInt::get(Ty, 1));
892  replaceOperand(I, 1, Y);
893  return &I;
894  }
895  }
896 
897  return nullptr;
898 }
899 
900 static const unsigned MaxDepth = 6;
901 
902 // Take the exact integer log2 of the value. If DoFold is true, create the
903 // actual instructions, otherwise return a non-null dummy value. Return nullptr
904 // on failure.
905 static Value *takeLog2(IRBuilderBase &Builder, Value *Op, unsigned Depth,
906  bool DoFold) {
907  auto IfFold = [DoFold](function_ref<Value *()> Fn) {
908  if (!DoFold)
909  return reinterpret_cast<Value *>(-1);
910  return Fn();
911  };
912 
913  // FIXME: assert that Op1 isn't/doesn't contain undef.
914 
915  // log2(2^C) -> C
916  if (match(Op, m_Power2()))
917  return IfFold([&]() {
918  Constant *C = ConstantExpr::getExactLogBase2(cast<Constant>(Op));
919  if (!C)
920  llvm_unreachable("Failed to constant fold udiv -> logbase2");
921  return C;
922  });
923 
924  // The remaining tests are all recursive, so bail out if we hit the limit.
925  if (Depth++ == MaxDepth)
926  return nullptr;
927 
928  // log2(zext X) -> zext log2(X)
929  // FIXME: Require one use?
930  Value *X, *Y;
931  if (match(Op, m_ZExt(m_Value(X))))
932  if (Value *LogX = takeLog2(Builder, X, Depth, DoFold))
933  return IfFold([&]() { return Builder.CreateZExt(LogX, Op->getType()); });
934 
935  // log2(X << Y) -> log2(X) + Y
936  // FIXME: Require one use unless X is 1?
937  if (match(Op, m_Shl(m_Value(X), m_Value(Y))))
938  if (Value *LogX = takeLog2(Builder, X, Depth, DoFold))
939  return IfFold([&]() { return Builder.CreateAdd(LogX, Y); });
940 
941  // log2(Cond ? X : Y) -> Cond ? log2(X) : log2(Y)
942  // FIXME: missed optimization: if one of the hands of select is/contains
943  // undef, just directly pick the other one.
944  // FIXME: can both hands contain undef?
945  // FIXME: Require one use?
946  if (SelectInst *SI = dyn_cast<SelectInst>(Op))
947  if (Value *LogX = takeLog2(Builder, SI->getOperand(1), Depth, DoFold))
948  if (Value *LogY = takeLog2(Builder, SI->getOperand(2), Depth, DoFold))
949  return IfFold([&]() {
950  return Builder.CreateSelect(SI->getOperand(0), LogX, LogY);
951  });
952 
953  // log2(umin(X, Y)) -> umin(log2(X), log2(Y))
954  // log2(umax(X, Y)) -> umax(log2(X), log2(Y))
955  auto *MinMax = dyn_cast<MinMaxIntrinsic>(Op);
956  if (MinMax && MinMax->hasOneUse() && !MinMax->isSigned())
957  if (Value *LogX = takeLog2(Builder, MinMax->getLHS(), Depth, DoFold))
958  if (Value *LogY = takeLog2(Builder, MinMax->getRHS(), Depth, DoFold))
959  return IfFold([&]() {
960  return Builder.CreateBinaryIntrinsic(
961  MinMax->getIntrinsicID(), LogX, LogY);
962  });
963 
964  return nullptr;
965 }
966 
967 /// If we have zero-extended operands of an unsigned div or rem, we may be able
968 /// to narrow the operation (sink the zext below the math).
971  Instruction::BinaryOps Opcode = I.getOpcode();
972  Value *N = I.getOperand(0);
973  Value *D = I.getOperand(1);
974  Type *Ty = I.getType();
975  Value *X, *Y;
976  if (match(N, m_ZExt(m_Value(X))) && match(D, m_ZExt(m_Value(Y))) &&
977  X->getType() == Y->getType() && (N->hasOneUse() || D->hasOneUse())) {
978  // udiv (zext X), (zext Y) --> zext (udiv X, Y)
979  // urem (zext X), (zext Y) --> zext (urem X, Y)
980  Value *NarrowOp = Builder.CreateBinOp(Opcode, X, Y);
981  return new ZExtInst(NarrowOp, Ty);
982  }
983 
984  Constant *C;
985  if ((match(N, m_OneUse(m_ZExt(m_Value(X)))) && match(D, m_Constant(C))) ||
986  (match(D, m_OneUse(m_ZExt(m_Value(X)))) && match(N, m_Constant(C)))) {
987  // If the constant is the same in the smaller type, use the narrow version.
988  Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
989  if (ConstantExpr::getZExt(TruncC, Ty) != C)
990  return nullptr;
991 
992  // udiv (zext X), C --> zext (udiv X, C')
993  // urem (zext X), C --> zext (urem X, C')
994  // udiv C, (zext X) --> zext (udiv C', X)
995  // urem C, (zext X) --> zext (urem C', X)
996  Value *NarrowOp = isa<Constant>(D) ? Builder.CreateBinOp(Opcode, X, TruncC)
997  : Builder.CreateBinOp(Opcode, TruncC, X);
998  return new ZExtInst(NarrowOp, Ty);
999  }
1000 
1001  return nullptr;
1002 }
1003 
1005  if (Value *V = SimplifyUDivInst(I.getOperand(0), I.getOperand(1),
1006  SQ.getWithInstruction(&I)))
1007  return replaceInstUsesWith(I, V);
1008 
1009  if (Instruction *X = foldVectorBinop(I))
1010  return X;
1011 
1012  // Handle the integer div common cases
1013  if (Instruction *Common = commonIDivTransforms(I))
1014  return Common;
1015 
1016  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1017  Value *X;
1018  const APInt *C1, *C2;
1019  if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && match(Op1, m_APInt(C2))) {
1020  // (X lshr C1) udiv C2 --> X udiv (C2 << C1)
1021  bool Overflow;
1022  APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
1023  if (!Overflow) {
1024  bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value()));
1025  BinaryOperator *BO = BinaryOperator::CreateUDiv(
1026  X, ConstantInt::get(X->getType(), C2ShlC1));
1027  if (IsExact)
1028  BO->setIsExact();
1029  return BO;
1030  }
1031  }
1032 
1033  // Op0 / C where C is large (negative) --> zext (Op0 >= C)
1034  // TODO: Could use isKnownNegative() to handle non-constant values.
1035  Type *Ty = I.getType();
1036  if (match(Op1, m_Negative())) {
1037  Value *Cmp = Builder.CreateICmpUGE(Op0, Op1);
1038  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1039  }
1040  // Op0 / (sext i1 X) --> zext (Op0 == -1) (if X is 0, the div is undefined)
1041  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1042  Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1043  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1044  }
1045 
1046  if (Instruction *NarrowDiv = narrowUDivURem(I, Builder))
1047  return NarrowDiv;
1048 
1049  // If the udiv operands are non-overflowing multiplies with a common operand,
1050  // then eliminate the common factor:
1051  // (A * B) / (A * X) --> B / X (and commuted variants)
1052  // TODO: The code would be reduced if we had m_c_NUWMul pattern matching.
1053  // TODO: If -reassociation handled this generally, we could remove this.
1054  Value *A, *B;
1055  if (match(Op0, m_NUWMul(m_Value(A), m_Value(B)))) {
1056  if (match(Op1, m_NUWMul(m_Specific(A), m_Value(X))) ||
1057  match(Op1, m_NUWMul(m_Value(X), m_Specific(A))))
1058  return BinaryOperator::CreateUDiv(B, X);
1059  if (match(Op1, m_NUWMul(m_Specific(B), m_Value(X))) ||
1060  match(Op1, m_NUWMul(m_Value(X), m_Specific(B))))
1061  return BinaryOperator::CreateUDiv(A, X);
1062  }
1063 
1064  // Op1 udiv Op2 -> Op1 lshr log2(Op2), if log2() folds away.
1065  if (takeLog2(Builder, Op1, /*Depth*/0, /*DoFold*/false)) {
1066  Value *Res = takeLog2(Builder, Op1, /*Depth*/0, /*DoFold*/true);
1067  return replaceInstUsesWith(
1068  I, Builder.CreateLShr(Op0, Res, I.getName(), I.isExact()));
1069  }
1070 
1071  return nullptr;
1072 }
1073 
1075  if (Value *V = SimplifySDivInst(I.getOperand(0), I.getOperand(1),
1076  SQ.getWithInstruction(&I)))
1077  return replaceInstUsesWith(I, V);
1078 
1079  if (Instruction *X = foldVectorBinop(I))
1080  return X;
1081 
1082  // Handle the integer div common cases
1083  if (Instruction *Common = commonIDivTransforms(I))
1084  return Common;
1085 
1086  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1087  Type *Ty = I.getType();
1088  Value *X;
1089  // sdiv Op0, -1 --> -Op0
1090  // sdiv Op0, (sext i1 X) --> -Op0 (because if X is 0, the op is undefined)
1091  if (match(Op1, m_AllOnes()) ||
1092  (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1093  return BinaryOperator::CreateNeg(Op0);
1094 
1095  // X / INT_MIN --> X == INT_MIN
1096  if (match(Op1, m_SignMask()))
1097  return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), Ty);
1098 
1099  // sdiv exact X, 1<<C --> ashr exact X, C iff 1<<C is non-negative
1100  // sdiv exact X, -1<<C --> -(ashr exact X, C)
1101  if (I.isExact() && ((match(Op1, m_Power2()) && match(Op1, m_NonNegative())) ||
1102  match(Op1, m_NegatedPower2()))) {
1103  bool DivisorWasNegative = match(Op1, m_NegatedPower2());
1104  if (DivisorWasNegative)
1105  Op1 = ConstantExpr::getNeg(cast<Constant>(Op1));
1106  auto *AShr = BinaryOperator::CreateExactAShr(
1107  Op0, ConstantExpr::getExactLogBase2(cast<Constant>(Op1)), I.getName());
1108  if (!DivisorWasNegative)
1109  return AShr;
1110  Builder.Insert(AShr);
1111  AShr->setName(I.getName() + ".neg");
1112  return BinaryOperator::CreateNeg(AShr, I.getName());
1113  }
1114 
1115  const APInt *Op1C;
1116  if (match(Op1, m_APInt(Op1C))) {
1117  // If the dividend is sign-extended and the constant divisor is small enough
1118  // to fit in the source type, shrink the division to the narrower type:
1119  // (sext X) sdiv C --> sext (X sdiv C)
1120  Value *Op0Src;
1121  if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
1122  Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) {
1123 
1124  // In the general case, we need to make sure that the dividend is not the
1125  // minimum signed value because dividing that by -1 is UB. But here, we
1126  // know that the -1 divisor case is already handled above.
1127 
1128  Constant *NarrowDivisor =
1129  ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
1130  Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
1131  return new SExtInst(NarrowOp, Ty);
1132  }
1133 
1134  // -X / C --> X / -C (if the negation doesn't overflow).
1135  // TODO: This could be enhanced to handle arbitrary vector constants by
1136  // checking if all elements are not the min-signed-val.
1137  if (!Op1C->isMinSignedValue() &&
1138  match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1139  Constant *NegC = ConstantInt::get(Ty, -(*Op1C));
1140  Instruction *BO = BinaryOperator::CreateSDiv(X, NegC);
1141  BO->setIsExact(I.isExact());
1142  return BO;
1143  }
1144  }
1145 
1146  // -X / Y --> -(X / Y)
1147  Value *Y;
1148  if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1150  Builder.CreateSDiv(X, Y, I.getName(), I.isExact()));
1151 
1152  // abs(X) / X --> X > -1 ? 1 : -1
1153  // X / abs(X) --> X > -1 ? 1 : -1
1154  if (match(&I, m_c_BinOp(
1155  m_OneUse(m_Intrinsic<Intrinsic::abs>(m_Value(X), m_One())),
1156  m_Deferred(X)))) {
1157  Value *Cond = Builder.CreateIsNotNeg(X);
1158  return SelectInst::Create(Cond, ConstantInt::get(Ty, 1),
1160  }
1161 
1162  // If the sign bits of both operands are zero (i.e. we can prove they are
1163  // unsigned inputs), turn this into a udiv.
1165  if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
1166  if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
1167  // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
1168  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1169  BO->setIsExact(I.isExact());
1170  return BO;
1171  }
1172 
1173  if (match(Op1, m_NegatedPower2())) {
1174  // X sdiv (-(1 << C)) -> -(X sdiv (1 << C)) ->
1175  // -> -(X udiv (1 << C)) -> -(X u>> C)
1177  ConstantExpr::getNeg(cast<Constant>(Op1)));
1178  Value *Shr = Builder.CreateLShr(Op0, CNegLog2, I.getName(), I.isExact());
1179  return BinaryOperator::CreateNeg(Shr);
1180  }
1181 
1182  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1183  // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1184  // Safe because the only negative value (1 << Y) can take on is
1185  // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1186  // the sign bit set.
1187  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1188  BO->setIsExact(I.isExact());
1189  return BO;
1190  }
1191  }
1192 
1193  return nullptr;
1194 }
1195 
1196 /// Remove negation and try to convert division into multiplication.
1198  Constant *C;
1199  if (!match(I.getOperand(1), m_Constant(C)))
1200  return nullptr;
1201 
1202  // -X / C --> X / -C
1203  Value *X;
1204  if (match(I.getOperand(0), m_FNeg(m_Value(X))))
1206 
1207  // If the constant divisor has an exact inverse, this is always safe. If not,
1208  // then we can still create a reciprocal if fast-math-flags allow it and the
1209  // constant is a regular number (not zero, infinite, or denormal).
1210  if (!(C->hasExactInverseFP() || (I.hasAllowReciprocal() && C->isNormalFP())))
1211  return nullptr;
1212 
1213  // Disallow denormal constants because we don't know what would happen
1214  // on all targets.
1215  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1216  // denorms are flushed?
1217  auto *RecipC = ConstantExpr::getFDiv(ConstantFP::get(I.getType(), 1.0), C);
1218  if (!RecipC->isNormalFP())
1219  return nullptr;
1220 
1221  // X / C --> X * (1 / C)
1222  return BinaryOperator::CreateFMulFMF(I.getOperand(0), RecipC, &I);
1223 }
1224 
1225 /// Remove negation and try to reassociate constant math.
1227  Constant *C;
1228  if (!match(I.getOperand(0), m_Constant(C)))
1229  return nullptr;
1230 
1231  // C / -X --> -C / X
1232  Value *X;
1233  if (match(I.getOperand(1), m_FNeg(m_Value(X))))
1235 
1236  if (!I.hasAllowReassoc() || !I.hasAllowReciprocal())
1237  return nullptr;
1238 
1239  // Try to reassociate C / X expressions where X includes another constant.
1240  Constant *C2, *NewC = nullptr;
1241  if (match(I.getOperand(1), m_FMul(m_Value(X), m_Constant(C2)))) {
1242  // C / (X * C2) --> (C / C2) / X
1243  NewC = ConstantExpr::getFDiv(C, C2);
1244  } else if (match(I.getOperand(1), m_FDiv(m_Value(X), m_Constant(C2)))) {
1245  // C / (X / C2) --> (C * C2) / X
1246  NewC = ConstantExpr::getFMul(C, C2);
1247  }
1248  // Disallow denormal constants because we don't know what would happen
1249  // on all targets.
1250  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1251  // denorms are flushed?
1252  if (!NewC || !NewC->isNormalFP())
1253  return nullptr;
1254 
1255  return BinaryOperator::CreateFDivFMF(NewC, X, &I);
1256 }
1257 
1258 /// Negate the exponent of pow/exp to fold division-by-pow() into multiply.
1261  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1262  auto *II = dyn_cast<IntrinsicInst>(Op1);
1263  if (!II || !II->hasOneUse() || !I.hasAllowReassoc() ||
1264  !I.hasAllowReciprocal())
1265  return nullptr;
1266 
1267  // Z / pow(X, Y) --> Z * pow(X, -Y)
1268  // Z / exp{2}(Y) --> Z * exp{2}(-Y)
1269  // In the general case, this creates an extra instruction, but fmul allows
1270  // for better canonicalization and optimization than fdiv.
1271  Intrinsic::ID IID = II->getIntrinsicID();
1273  switch (IID) {
1274  case Intrinsic::pow:
1275  Args.push_back(II->getArgOperand(0));
1276  Args.push_back(Builder.CreateFNegFMF(II->getArgOperand(1), &I));
1277  break;
1278  case Intrinsic::powi: {
1279  // Require 'ninf' assuming that makes powi(X, -INT_MIN) acceptable.
1280  // That is, X ** (huge negative number) is 0.0, ~1.0, or INF and so
1281  // dividing by that is INF, ~1.0, or 0.0. Code that uses powi allows
1282  // non-standard results, so this corner case should be acceptable if the
1283  // code rules out INF values.
1284  if (!I.hasNoInfs())
1285  return nullptr;
1286  Args.push_back(II->getArgOperand(0));
1287  Args.push_back(Builder.CreateNeg(II->getArgOperand(1)));
1288  Type *Tys[] = {I.getType(), II->getArgOperand(1)->getType()};
1289  Value *Pow = Builder.CreateIntrinsic(IID, Tys, Args, &I);
1290  return BinaryOperator::CreateFMulFMF(Op0, Pow, &I);
1291  }
1292  case Intrinsic::exp:
1293  case Intrinsic::exp2:
1294  Args.push_back(Builder.CreateFNegFMF(II->getArgOperand(0), &I));
1295  break;
1296  default:
1297  return nullptr;
1298  }
1299  Value *Pow = Builder.CreateIntrinsic(IID, I.getType(), Args, &I);
1300  return BinaryOperator::CreateFMulFMF(Op0, Pow, &I);
1301 }
1302 
1304  Module *M = I.getModule();
1305 
1306  if (Value *V = SimplifyFDivInst(I.getOperand(0), I.getOperand(1),
1307  I.getFastMathFlags(),
1308  SQ.getWithInstruction(&I)))
1309  return replaceInstUsesWith(I, V);
1310 
1311  if (Instruction *X = foldVectorBinop(I))
1312  return X;
1313 
1314  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1315  return Phi;
1316 
1318  return R;
1319 
1321  return R;
1322 
1323  if (Instruction *R = foldFPSignBitOps(I))
1324  return R;
1325 
1326  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1327  if (isa<Constant>(Op0))
1328  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1329  if (Instruction *R = FoldOpIntoSelect(I, SI))
1330  return R;
1331 
1332  if (isa<Constant>(Op1))
1333  if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1334  if (Instruction *R = FoldOpIntoSelect(I, SI))
1335  return R;
1336 
1337  if (I.hasAllowReassoc() && I.hasAllowReciprocal()) {
1338  Value *X, *Y;
1339  if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1340  (!isa<Constant>(Y) || !isa<Constant>(Op1))) {
1341  // (X / Y) / Z => X / (Y * Z)
1342  Value *YZ = Builder.CreateFMulFMF(Y, Op1, &I);
1343  return BinaryOperator::CreateFDivFMF(X, YZ, &I);
1344  }
1345  if (match(Op1, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1346  (!isa<Constant>(Y) || !isa<Constant>(Op0))) {
1347  // Z / (X / Y) => (Y * Z) / X
1348  Value *YZ = Builder.CreateFMulFMF(Y, Op0, &I);
1349  return BinaryOperator::CreateFDivFMF(YZ, X, &I);
1350  }
1351  // Z / (1.0 / Y) => (Y * Z)
1352  //
1353  // This is a special case of Z / (X / Y) => (Y * Z) / X, with X = 1.0. The
1354  // m_OneUse check is avoided because even in the case of the multiple uses
1355  // for 1.0/Y, the number of instructions remain the same and a division is
1356  // replaced by a multiplication.
1357  if (match(Op1, m_FDiv(m_SpecificFP(1.0), m_Value(Y))))
1358  return BinaryOperator::CreateFMulFMF(Y, Op0, &I);
1359  }
1360 
1361  if (I.hasAllowReassoc() && Op0->hasOneUse() && Op1->hasOneUse()) {
1362  // sin(X) / cos(X) -> tan(X)
1363  // cos(X) / sin(X) -> 1/tan(X) (cotangent)
1364  Value *X;
1365  bool IsTan = match(Op0, m_Intrinsic<Intrinsic::sin>(m_Value(X))) &&
1366  match(Op1, m_Intrinsic<Intrinsic::cos>(m_Specific(X)));
1367  bool IsCot =
1368  !IsTan && match(Op0, m_Intrinsic<Intrinsic::cos>(m_Value(X))) &&
1369  match(Op1, m_Intrinsic<Intrinsic::sin>(m_Specific(X)));
1370 
1371  if ((IsTan || IsCot) && hasFloatFn(M, &TLI, I.getType(), LibFunc_tan,
1372  LibFunc_tanf, LibFunc_tanl)) {
1373  IRBuilder<> B(&I);
1375  B.setFastMathFlags(I.getFastMathFlags());
1377  cast<CallBase>(Op0)->getCalledFunction()->getAttributes();
1378  Value *Res = emitUnaryFloatFnCall(X, &TLI, LibFunc_tan, LibFunc_tanf,
1379  LibFunc_tanl, B, Attrs);
1380  if (IsCot)
1381  Res = B.CreateFDiv(ConstantFP::get(I.getType(), 1.0), Res);
1382  return replaceInstUsesWith(I, Res);
1383  }
1384  }
1385 
1386  // X / (X * Y) --> 1.0 / Y
1387  // Reassociate to (X / X -> 1.0) is legal when NaNs are not allowed.
1388  // We can ignore the possibility that X is infinity because INF/INF is NaN.
1389  Value *X, *Y;
1390  if (I.hasNoNaNs() && I.hasAllowReassoc() &&
1391  match(Op1, m_c_FMul(m_Specific(Op0), m_Value(Y)))) {
1392  replaceOperand(I, 0, ConstantFP::get(I.getType(), 1.0));
1393  replaceOperand(I, 1, Y);
1394  return &I;
1395  }
1396 
1397  // X / fabs(X) -> copysign(1.0, X)
1398  // fabs(X) / X -> copysign(1.0, X)
1399  if (I.hasNoNaNs() && I.hasNoInfs() &&
1400  (match(&I, m_FDiv(m_Value(X), m_FAbs(m_Deferred(X)))) ||
1401  match(&I, m_FDiv(m_FAbs(m_Value(X)), m_Deferred(X))))) {
1402  Value *V = Builder.CreateBinaryIntrinsic(
1403  Intrinsic::copysign, ConstantFP::get(I.getType(), 1.0), X, &I);
1404  return replaceInstUsesWith(I, V);
1405  }
1406 
1408  return Mul;
1409 
1410  return nullptr;
1411 }
1412 
1413 /// This function implements the transforms common to both integer remainder
1414 /// instructions (urem and srem). It is called by the visitors to those integer
1415 /// remainder instructions.
1416 /// Common integer remainder transforms
1418  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1419  return Phi;
1420 
1421  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1422 
1423  // The RHS is known non-zero.
1424  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I))
1425  return replaceOperand(I, 1, V);
1426 
1427  // Handle cases involving: rem X, (select Cond, Y, Z)
1428  if (simplifyDivRemOfSelectWithZeroOp(I))
1429  return &I;
1430 
1431  // If the divisor is a select-of-constants, try to constant fold all rem ops:
1432  // C % (select Cond, TrueC, FalseC) --> select Cond, (C % TrueC), (C % FalseC)
1433  // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
1434  if (match(Op0, m_ImmConstant()) &&
1436  if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1),
1437  /*FoldWithMultiUse*/ true))
1438  return R;
1439  }
1440 
1441  if (isa<Constant>(Op1)) {
1442  if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1443  if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1444  if (Instruction *R = FoldOpIntoSelect(I, SI))
1445  return R;
1446  } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
1447  const APInt *Op1Int;
1448  if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
1449  (I.getOpcode() == Instruction::URem ||
1450  !Op1Int->isMinSignedValue())) {
1451  // foldOpIntoPhi will speculate instructions to the end of the PHI's
1452  // predecessor blocks, so do this only if we know the srem or urem
1453  // will not fault.
1454  if (Instruction *NV = foldOpIntoPhi(I, PN))
1455  return NV;
1456  }
1457  }
1458 
1459  // See if we can fold away this rem instruction.
1460  if (SimplifyDemandedInstructionBits(I))
1461  return &I;
1462  }
1463  }
1464 
1465  return nullptr;
1466 }
1467 
1469  if (Value *V = SimplifyURemInst(I.getOperand(0), I.getOperand(1),
1470  SQ.getWithInstruction(&I)))
1471  return replaceInstUsesWith(I, V);
1472 
1473  if (Instruction *X = foldVectorBinop(I))
1474  return X;
1475 
1476  if (Instruction *common = commonIRemTransforms(I))
1477  return common;
1478 
1479  if (Instruction *NarrowRem = narrowUDivURem(I, Builder))
1480  return NarrowRem;
1481 
1482  // X urem Y -> X and Y-1, where Y is a power of 2,
1483  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1484  Type *Ty = I.getType();
1485  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1486  // This may increase instruction count, we don't enforce that Y is a
1487  // constant.
1489  Value *Add = Builder.CreateAdd(Op1, N1);
1490  return BinaryOperator::CreateAnd(Op0, Add);
1491  }
1492 
1493  // 1 urem X -> zext(X != 1)
1494  if (match(Op0, m_One())) {
1495  Value *Cmp = Builder.CreateICmpNE(Op1, ConstantInt::get(Ty, 1));
1496  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1497  }
1498 
1499  // Op0 urem C -> Op0 < C ? Op0 : Op0 - C, where C >= signbit.
1500  // Op0 must be frozen because we are increasing its number of uses.
1501  if (match(Op1, m_Negative())) {
1502  Value *F0 = Builder.CreateFreeze(Op0, Op0->getName() + ".fr");
1503  Value *Cmp = Builder.CreateICmpULT(F0, Op1);
1504  Value *Sub = Builder.CreateSub(F0, Op1);
1505  return SelectInst::Create(Cmp, F0, Sub);
1506  }
1507 
1508  // If the divisor is a sext of a boolean, then the divisor must be max
1509  // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also
1510  // max unsigned value. In that case, the remainder is 0:
1511  // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0
1512  Value *X;
1513  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1514  Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1515  return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), Op0);
1516  }
1517 
1518  return nullptr;
1519 }
1520 
1522  if (Value *V = SimplifySRemInst(I.getOperand(0), I.getOperand(1),
1523  SQ.getWithInstruction(&I)))
1524  return replaceInstUsesWith(I, V);
1525 
1526  if (Instruction *X = foldVectorBinop(I))
1527  return X;
1528 
1529  // Handle the integer rem common cases
1530  if (Instruction *Common = commonIRemTransforms(I))
1531  return Common;
1532 
1533  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1534  {
1535  const APInt *Y;
1536  // X % -Y -> X % Y
1537  if (match(Op1, m_Negative(Y)) && !Y->isMinSignedValue())
1538  return replaceOperand(I, 1, ConstantInt::get(I.getType(), -*Y));
1539  }
1540 
1541  // -X srem Y --> -(X srem Y)
1542  Value *X, *Y;
1543  if (match(&I, m_SRem(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1544  return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y));
1545 
1546  // If the sign bits of both operands are zero (i.e. we can prove they are
1547  // unsigned inputs), turn this into a urem.
1548  APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
1549  if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1550  MaskedValueIsZero(Op0, Mask, 0, &I)) {
1551  // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1552  return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1553  }
1554 
1555  // If it's a constant vector, flip any negative values positive.
1556  if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1557  Constant *C = cast<Constant>(Op1);
1558  unsigned VWidth = cast<FixedVectorType>(C->getType())->getNumElements();
1559 
1560  bool hasNegative = false;
1561  bool hasMissing = false;
1562  for (unsigned i = 0; i != VWidth; ++i) {
1563  Constant *Elt = C->getAggregateElement(i);
1564  if (!Elt) {
1565  hasMissing = true;
1566  break;
1567  }
1568 
1569  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1570  if (RHS->isNegative())
1571  hasNegative = true;
1572  }
1573 
1574  if (hasNegative && !hasMissing) {
1575  SmallVector<Constant *, 16> Elts(VWidth);
1576  for (unsigned i = 0; i != VWidth; ++i) {
1577  Elts[i] = C->getAggregateElement(i); // Handle undef, etc.
1578  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1579  if (RHS->isNegative())
1580  Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1581  }
1582  }
1583 
1584  Constant *NewRHSV = ConstantVector::get(Elts);
1585  if (NewRHSV != C) // Don't loop on -MININT
1586  return replaceOperand(I, 1, NewRHSV);
1587  }
1588  }
1589 
1590  return nullptr;
1591 }
1592 
1594  if (Value *V = SimplifyFRemInst(I.getOperand(0), I.getOperand(1),
1595  I.getFastMathFlags(),
1596  SQ.getWithInstruction(&I)))
1597  return replaceInstUsesWith(I, V);
1598 
1599  if (Instruction *X = foldVectorBinop(I))
1600  return X;
1601 
1602  if (Instruction *Phi = foldBinopWithPhiOperands(I))
1603  return Phi;
1604 
1605  return nullptr;
1606 }
i
i
Definition: README.txt:29
llvm::InstCombinerImpl::isKnownToBeAPowerOfTwo
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
Definition: InstCombineInternal.h:479
Attrs
Function Attrs
Definition: README_ALTIVEC.txt:215
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:930
llvm::PatternMatch::m_NonNegative
cst_pred_ty< is_nonnegative > m_NonNegative()
Match an integer or vector of non-negative values.
Definition: PatternMatch.h:479
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:1228
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::ConstantExpr::getFDiv
static Constant * getFDiv(Constant *C1, Constant *C2)
Definition: Constants.cpp:2758
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:1774
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:391
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:823
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:556
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2148
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:700
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1127
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:1471
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
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:1653
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:988
foldFDivConstantDivisor
static Instruction * foldFDivConstantDivisor(BinaryOperator &I)
Remove negation and try to convert division into multiplication.
Definition: InstCombineMulDivRem.cpp:1197
ErrorHandling.h
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::InstCombinerImpl::visitSRem
Instruction * visitSRem(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1521
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:3180
llvm::InstCombinerImpl::visitFDiv
Instruction * visitFDiv(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1303
llvm::Instruction::hasNoUnsignedWrap
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
Definition: Instruction.cpp:135
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:1223
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:1423
llvm::AttributeList
Definition: Attributes.h:408
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:123
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:1133
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:2808
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:6192
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:2794
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:676
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:131
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:730
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:798
llvm::PatternMatch::m_FDiv
BinaryOp_match< LHS, RHS, Instruction::FDiv > m_FDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1079
llvm::PatternMatch::m_FAdd
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:994
llvm::PatternMatch::m_FSub
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1006
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:270
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:45
llvm::SPF_NABS
@ SPF_NABS
Absolute value.
Definition: ValueTracking.h:685
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:2221
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:1185
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
foldMulSelectToNegate
static Value * foldMulSelectToNegate(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
Definition: InstCombineMulDivRem.cpp:98
llvm::InstCombinerImpl::commonIRemTransforms
Instruction * commonIRemTransforms(BinaryOperator &I)
This function implements the transforms common to both integer remainder instructions (urem and srem)...
Definition: InstCombineMulDivRem.cpp:1417
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1768
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:1472
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:127
llvm::PatternMatch::m_Exact
Exact_match< T > m_Exact(const T &SubPattern)
Definition: PatternMatch.h:1361
llvm::PatternMatch::m_SpecificIntAllowUndef
specific_intval< true > m_SpecificIntAllowUndef(APInt V)
Definition: PatternMatch.h:871
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:207
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
InstructionWorklist.h
llvm::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1639
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:1043
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:1073
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:392
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:1182
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
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:919
llvm::PatternMatch::m_NSWSub
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1174
llvm::PatternMatch::m_URem
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1085
PatternMatch.h
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:1217
Type.h
llvm::ConstantExpr::getFNeg
static Constant * getFNeg(Constant *C)
Definition: Constants.cpp:2703
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:513
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:5330
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:2120
BasicBlock.h
llvm::PatternMatch::m_Zero
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:535
llvm::MipsISD::Ext
@ Ext
Definition: MipsISelLowering.h:159
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::UnaryOperator::CreateFNegFMF
static UnaryOperator * CreateFNegFMF(Value *Op, Instruction *FMFSource, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: InstrTypes.h:164
llvm::PatternMatch::m_ImmConstant
match_combine_and< class_match< Constant >, match_unless< class_match< ConstantExpr > > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:759
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::APInt::sdivrem
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition: APInt.cpp:1906
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1109
llvm::PatternMatch::m_AllOnes
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:445
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:1364
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:2791
llvm::InstCombinerImpl::commonIDivTransforms
Instruction * commonIDivTransforms(BinaryOperator &I)
This function implements the transforms common to both integer division instructions (udiv and sdiv).
Definition: InstCombineMulDivRem.cpp:755
llvm::PatternMatch::m_FAbs
m_Intrinsic_Ty< Opnd0 >::Ty m_FAbs(const Opnd0 &Op0)
Definition: PatternMatch.h:2182
llvm::PatternMatch::m_SRem
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1091
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:1000
llvm::SPF_ABS
@ SPF_ABS
Floating point maxnum.
Definition: ValueTracking.h:684
llvm::Negator::Negate
static LLVM_NODISCARD Value * Negate(bool LHSIsZero, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
Definition: InstCombineNegator.cpp:517
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1737
llvm::PatternMatch::m_Negative
cst_pred_ty< is_negative > m_Negative()
Match an integer or vector of negative values.
Definition: PatternMatch.h:467
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:142
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:655
llvm::InstCombinerImpl::visitSDiv
Instruction * visitSDiv(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1074
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:4819
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:1226
llvm::PatternMatch::m_SExt
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:1633
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:5393
llvm::PatternMatch::m_NUWMul
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1215
llvm::BinaryOperator
Definition: InstrTypes.h:188
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:178
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
llvm::InstCombinerImpl::visitFMul
Instruction * visitFMul(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:441
llvm::Instruction::isExact
bool isExact() const
Determine whether the exact flag is set.
Definition: Instruction.cpp:195
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1389
llvm::ConstantExpr::getFMul
static Constant * getFMul(Constant *C1, Constant *C2)
Definition: Constants.cpp:2744
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4858
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:305
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:874
MaxDepth
static const unsigned MaxDepth
Definition: InstCombineMulDivRem.cpp:900
llvm::InstCombinerImpl::visitURem
Instruction * visitURem(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1468
Constant.h
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:867
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
llvm::PatternMatch::m_UDiv
BinaryOp_match< LHS, RHS, Instruction::UDiv > m_UDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1067
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:1593
llvm::ConstantExpr::getNeg
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2696
llvm::InstCombinerImpl::visitMul
Instruction * visitMul(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:142
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:341
llvm::ConstantInt::getBool
static ConstantInt * getBool(LLVMContext &Context, bool V)
Definition: Constants.cpp:881
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:5431
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:197
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:966
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:5277
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:580
llvm::Value::hasNUses
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
Definition: Value.cpp:145
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:2810
llvm::PatternMatch::m_NSWShl
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1190
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:1259
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:802
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:2250
takeLog2
static Value * takeLog2(IRBuilderBase &Builder, Value *Op, unsigned Depth, bool DoFold)
Definition: InstCombineMulDivRem.cpp:905
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:722
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
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:1196
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:425
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:786
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:2370
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:780
llvm::Instruction::hasNoSignedWrap
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
Definition: Instruction.cpp:139
CreateMul
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:243
N
#define N
llvm::IRBuilderBase::CreateShl
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1289
InstructionSimplify.h
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:2279
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:327
llvm::IRBuilderBase::CreateSub
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1217
CreateAdd
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:231
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:378
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:3224
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:2778
llvm::PatternMatch::m_FMul
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1061
Value.h
llvm::abs
APFloat abs(APFloat X)
Returns the absolute value of the argument.
Definition: APFloat.h:1281
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:1121
llvm::APInt::ushl_ov
APInt ushl_ov(const APInt &Amt, bool &Overflow) const
Definition: APInt.cpp:2017
llvm::InstCombinerImpl::visitUDiv
Instruction * visitUDiv(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1004
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:969
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:1055
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:37