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