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  // If the divisor is a select-of-constants, try to constant fold all div ops:
759  // C / (select Cond, TrueC, FalseC) --> select Cond, (C / TrueC), (C / FalseC)
760  // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
761  if (match(Op0, m_ImmConstant()) &&
763  if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1)))
764  return R;
765  }
766 
767  const APInt *C2;
768  if (match(Op1, m_APInt(C2))) {
769  Value *X;
770  const APInt *C1;
771 
772  // (X / C1) / C2 -> X / (C1*C2)
773  if ((IsSigned && match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))) ||
774  (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_APInt(C1))))) {
775  APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
776  if (!multiplyOverflows(*C1, *C2, Product, IsSigned))
777  return BinaryOperator::Create(I.getOpcode(), X,
778  ConstantInt::get(Ty, Product));
779  }
780 
781  if ((IsSigned && match(Op0, m_NSWMul(m_Value(X), m_APInt(C1)))) ||
782  (!IsSigned && match(Op0, m_NUWMul(m_Value(X), m_APInt(C1))))) {
783  APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
784 
785  // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
786  if (isMultiple(*C2, *C1, Quotient, IsSigned)) {
787  auto *NewDiv = BinaryOperator::Create(I.getOpcode(), X,
788  ConstantInt::get(Ty, Quotient));
789  NewDiv->setIsExact(I.isExact());
790  return NewDiv;
791  }
792 
793  // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
794  if (isMultiple(*C1, *C2, Quotient, IsSigned)) {
796  ConstantInt::get(Ty, Quotient));
797  auto *OBO = cast<OverflowingBinaryOperator>(Op0);
798  Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
799  Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
800  return Mul;
801  }
802  }
803 
804  if ((IsSigned && match(Op0, m_NSWShl(m_Value(X), m_APInt(C1))) &&
805  C1->ult(C1->getBitWidth() - 1)) ||
806  (!IsSigned && match(Op0, m_NUWShl(m_Value(X), m_APInt(C1))) &&
807  C1->ult(C1->getBitWidth()))) {
808  APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
809  APInt C1Shifted = APInt::getOneBitSet(
810  C1->getBitWidth(), static_cast<unsigned>(C1->getZExtValue()));
811 
812  // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of 1 << C1.
813  if (isMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
814  auto *BO = BinaryOperator::Create(I.getOpcode(), X,
815  ConstantInt::get(Ty, Quotient));
816  BO->setIsExact(I.isExact());
817  return BO;
818  }
819 
820  // (X << C1) / C2 -> X * ((1 << C1) / C2) if 1 << C1 is a multiple of C2.
821  if (isMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
823  ConstantInt::get(Ty, Quotient));
824  auto *OBO = cast<OverflowingBinaryOperator>(Op0);
825  Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
826  Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
827  return Mul;
828  }
829  }
830 
831  if (!C2->isZero()) // avoid X udiv 0
832  if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I))
833  return FoldedDiv;
834  }
835 
836  if (match(Op0, m_One())) {
837  assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?");
838  if (IsSigned) {
839  // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the
840  // result is one, if Op1 is -1 then the result is minus one, otherwise
841  // it's zero.
842  Value *Inc = Builder.CreateAdd(Op1, Op0);
843  Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(Ty, 3));
844  return SelectInst::Create(Cmp, Op1, ConstantInt::get(Ty, 0));
845  } else {
846  // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
847  // result is one, otherwise it's zero.
848  return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), Ty);
849  }
850  }
851 
852  // See if we can fold away this div instruction.
853  if (SimplifyDemandedInstructionBits(I))
854  return &I;
855 
856  // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
857  Value *X, *Z;
858  if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) // (X - Z) / Y; Y = Op1
859  if ((IsSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
860  (!IsSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
861  return BinaryOperator::Create(I.getOpcode(), X, Op1);
862 
863  // (X << Y) / X -> 1 << Y
864  Value *Y;
865  if (IsSigned && match(Op0, m_NSWShl(m_Specific(Op1), m_Value(Y))))
866  return BinaryOperator::CreateNSWShl(ConstantInt::get(Ty, 1), Y);
867  if (!IsSigned && match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y))))
868  return BinaryOperator::CreateNUWShl(ConstantInt::get(Ty, 1), Y);
869 
870  // X / (X * Y) -> 1 / Y if the multiplication does not overflow.
871  if (match(Op1, m_c_Mul(m_Specific(Op0), m_Value(Y)))) {
872  bool HasNSW = cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap();
873  bool HasNUW = cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap();
874  if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) {
875  replaceOperand(I, 0, ConstantInt::get(Ty, 1));
876  replaceOperand(I, 1, Y);
877  return &I;
878  }
879  }
880 
881  return nullptr;
882 }
883 
884 static const unsigned MaxDepth = 6;
885 
886 namespace {
887 
888 using FoldUDivOperandCb = Instruction *(*)(Value *Op0, Value *Op1,
889  const BinaryOperator &I,
890  InstCombinerImpl &IC);
891 
892 /// Used to maintain state for visitUDivOperand().
893 struct UDivFoldAction {
894  /// Informs visitUDiv() how to fold this operand. This can be zero if this
895  /// action joins two actions together.
896  FoldUDivOperandCb FoldAction;
897 
898  /// Which operand to fold.
899  Value *OperandToFold;
900 
901  union {
902  /// The instruction returned when FoldAction is invoked.
903  Instruction *FoldResult;
904 
905  /// Stores the LHS action index if this action joins two actions together.
906  size_t SelectLHSIdx;
907  };
908 
909  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
910  : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
911  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
912  : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
913 };
914 
915 } // end anonymous namespace
916 
917 // X udiv 2^C -> X >> C
919  const BinaryOperator &I,
920  InstCombinerImpl &IC) {
921  Constant *C1 = ConstantExpr::getExactLogBase2(cast<Constant>(Op1));
922  if (!C1)
923  llvm_unreachable("Failed to constant fold udiv -> logbase2");
924  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, C1);
925  if (I.isExact())
926  LShr->setIsExact();
927  return LShr;
928 }
929 
930 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
931 // X udiv (zext (C1 << N)), where C1 is "1<<C2" --> X >> (N+C2)
932 static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
933  InstCombinerImpl &IC) {
934  Value *ShiftLeft;
935  if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
936  ShiftLeft = Op1;
937 
938  Constant *CI;
939  Value *N;
940  if (!match(ShiftLeft, m_Shl(m_Constant(CI), m_Value(N))))
941  llvm_unreachable("match should never fail here!");
943  if (!Log2Base)
944  llvm_unreachable("getLogBase2 should never fail here!");
945  N = IC.Builder.CreateAdd(N, Log2Base);
946  if (Op1 != ShiftLeft)
947  N = IC.Builder.CreateZExt(N, Op1->getType());
948  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
949  if (I.isExact())
950  LShr->setIsExact();
951  return LShr;
952 }
953 
954 // Recursively visits the possible right hand operands of a udiv
955 // instruction, seeing through select instructions, to determine if we can
956 // replace the udiv with something simpler. If we find that an operand is not
957 // able to simplify the udiv, we abort the entire transformation.
958 static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
960  unsigned Depth = 0) {
961  // FIXME: assert that Op1 isn't/doesn't contain undef.
962 
963  // Check to see if this is an unsigned division with an exact power of 2,
964  // if so, convert to a right shift.
965  if (match(Op1, m_Power2())) {
966  Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1));
967  return Actions.size();
968  }
969 
970  // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
971  if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
972  match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
973  Actions.push_back(UDivFoldAction(foldUDivShl, Op1));
974  return Actions.size();
975  }
976 
977  // The remaining tests are all recursive, so bail out if we hit the limit.
978  if (Depth++ == MaxDepth)
979  return 0;
980 
981  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
982  // FIXME: missed optimization: if one of the hands of select is/contains
983  // undef, just directly pick the other one.
984  // FIXME: can both hands contain undef?
985  if (size_t LHSIdx =
986  visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth))
987  if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) {
988  Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1));
989  return Actions.size();
990  }
991 
992  return 0;
993 }
994 
995 /// If we have zero-extended operands of an unsigned div or rem, we may be able
996 /// to narrow the operation (sink the zext below the math).
999  Instruction::BinaryOps Opcode = I.getOpcode();
1000  Value *N = I.getOperand(0);
1001  Value *D = I.getOperand(1);
1002  Type *Ty = I.getType();
1003  Value *X, *Y;
1004  if (match(N, m_ZExt(m_Value(X))) && match(D, m_ZExt(m_Value(Y))) &&
1005  X->getType() == Y->getType() && (N->hasOneUse() || D->hasOneUse())) {
1006  // udiv (zext X), (zext Y) --> zext (udiv X, Y)
1007  // urem (zext X), (zext Y) --> zext (urem X, Y)
1008  Value *NarrowOp = Builder.CreateBinOp(Opcode, X, Y);
1009  return new ZExtInst(NarrowOp, Ty);
1010  }
1011 
1012  Constant *C;
1013  if ((match(N, m_OneUse(m_ZExt(m_Value(X)))) && match(D, m_Constant(C))) ||
1014  (match(D, m_OneUse(m_ZExt(m_Value(X)))) && match(N, m_Constant(C)))) {
1015  // If the constant is the same in the smaller type, use the narrow version.
1016  Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
1017  if (ConstantExpr::getZExt(TruncC, Ty) != C)
1018  return nullptr;
1019 
1020  // udiv (zext X), C --> zext (udiv X, C')
1021  // urem (zext X), C --> zext (urem X, C')
1022  // udiv C, (zext X) --> zext (udiv C', X)
1023  // urem C, (zext X) --> zext (urem C', X)
1024  Value *NarrowOp = isa<Constant>(D) ? Builder.CreateBinOp(Opcode, X, TruncC)
1025  : Builder.CreateBinOp(Opcode, TruncC, X);
1026  return new ZExtInst(NarrowOp, Ty);
1027  }
1028 
1029  return nullptr;
1030 }
1031 
1033  if (Value *V = SimplifyUDivInst(I.getOperand(0), I.getOperand(1),
1034  SQ.getWithInstruction(&I)))
1035  return replaceInstUsesWith(I, V);
1036 
1037  if (Instruction *X = foldVectorBinop(I))
1038  return X;
1039 
1040  // Handle the integer div common cases
1041  if (Instruction *Common = commonIDivTransforms(I))
1042  return Common;
1043 
1044  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1045  Value *X;
1046  const APInt *C1, *C2;
1047  if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && match(Op1, m_APInt(C2))) {
1048  // (X lshr C1) udiv C2 --> X udiv (C2 << C1)
1049  bool Overflow;
1050  APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
1051  if (!Overflow) {
1052  bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value()));
1053  BinaryOperator *BO = BinaryOperator::CreateUDiv(
1054  X, ConstantInt::get(X->getType(), C2ShlC1));
1055  if (IsExact)
1056  BO->setIsExact();
1057  return BO;
1058  }
1059  }
1060 
1061  // Op0 / C where C is large (negative) --> zext (Op0 >= C)
1062  // TODO: Could use isKnownNegative() to handle non-constant values.
1063  Type *Ty = I.getType();
1064  if (match(Op1, m_Negative())) {
1065  Value *Cmp = Builder.CreateICmpUGE(Op0, Op1);
1066  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1067  }
1068  // Op0 / (sext i1 X) --> zext (Op0 == -1) (if X is 0, the div is undefined)
1069  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1070  Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1071  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1072  }
1073 
1074  if (Instruction *NarrowDiv = narrowUDivURem(I, Builder))
1075  return NarrowDiv;
1076 
1077  // If the udiv operands are non-overflowing multiplies with a common operand,
1078  // then eliminate the common factor:
1079  // (A * B) / (A * X) --> B / X (and commuted variants)
1080  // TODO: The code would be reduced if we had m_c_NUWMul pattern matching.
1081  // TODO: If -reassociation handled this generally, we could remove this.
1082  Value *A, *B;
1083  if (match(Op0, m_NUWMul(m_Value(A), m_Value(B)))) {
1084  if (match(Op1, m_NUWMul(m_Specific(A), m_Value(X))) ||
1085  match(Op1, m_NUWMul(m_Value(X), m_Specific(A))))
1086  return BinaryOperator::CreateUDiv(B, X);
1087  if (match(Op1, m_NUWMul(m_Specific(B), m_Value(X))) ||
1088  match(Op1, m_NUWMul(m_Value(X), m_Specific(B))))
1089  return BinaryOperator::CreateUDiv(A, X);
1090  }
1091 
1092  // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
1093  SmallVector<UDivFoldAction, 6> UDivActions;
1094  if (visitUDivOperand(Op0, Op1, I, UDivActions))
1095  for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) {
1096  FoldUDivOperandCb Action = UDivActions[i].FoldAction;
1097  Value *ActionOp1 = UDivActions[i].OperandToFold;
1098  Instruction *Inst;
1099  if (Action)
1100  Inst = Action(Op0, ActionOp1, I, *this);
1101  else {
1102  // This action joins two actions together. The RHS of this action is
1103  // simply the last action we processed, we saved the LHS action index in
1104  // the joining action.
1105  size_t SelectRHSIdx = i - 1;
1106  Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult;
1107  size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx;
1108  Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult;
1109  Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
1110  SelectLHS, SelectRHS);
1111  }
1112 
1113  // If this is the last action to process, return it to the InstCombiner.
1114  // Otherwise, we insert it before the UDiv and record it so that we may
1115  // use it as part of a joining action (i.e., a SelectInst).
1116  if (e - i != 1) {
1117  Inst->insertBefore(&I);
1118  UDivActions[i].FoldResult = Inst;
1119  } else
1120  return Inst;
1121  }
1122 
1123  return nullptr;
1124 }
1125 
1127  if (Value *V = SimplifySDivInst(I.getOperand(0), I.getOperand(1),
1128  SQ.getWithInstruction(&I)))
1129  return replaceInstUsesWith(I, V);
1130 
1131  if (Instruction *X = foldVectorBinop(I))
1132  return X;
1133 
1134  // Handle the integer div common cases
1135  if (Instruction *Common = commonIDivTransforms(I))
1136  return Common;
1137 
1138  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1139  Type *Ty = I.getType();
1140  Value *X;
1141  // sdiv Op0, -1 --> -Op0
1142  // sdiv Op0, (sext i1 X) --> -Op0 (because if X is 0, the op is undefined)
1143  if (match(Op1, m_AllOnes()) ||
1144  (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1145  return BinaryOperator::CreateNeg(Op0);
1146 
1147  // X / INT_MIN --> X == INT_MIN
1148  if (match(Op1, m_SignMask()))
1149  return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), Ty);
1150 
1151  // sdiv exact X, 1<<C --> ashr exact X, C iff 1<<C is non-negative
1152  // sdiv exact X, -1<<C --> -(ashr exact X, C)
1153  if (I.isExact() && ((match(Op1, m_Power2()) && match(Op1, m_NonNegative())) ||
1154  match(Op1, m_NegatedPower2()))) {
1155  bool DivisorWasNegative = match(Op1, m_NegatedPower2());
1156  if (DivisorWasNegative)
1157  Op1 = ConstantExpr::getNeg(cast<Constant>(Op1));
1158  auto *AShr = BinaryOperator::CreateExactAShr(
1159  Op0, ConstantExpr::getExactLogBase2(cast<Constant>(Op1)), I.getName());
1160  if (!DivisorWasNegative)
1161  return AShr;
1162  Builder.Insert(AShr);
1163  AShr->setName(I.getName() + ".neg");
1164  return BinaryOperator::CreateNeg(AShr, I.getName());
1165  }
1166 
1167  const APInt *Op1C;
1168  if (match(Op1, m_APInt(Op1C))) {
1169  // If the dividend is sign-extended and the constant divisor is small enough
1170  // to fit in the source type, shrink the division to the narrower type:
1171  // (sext X) sdiv C --> sext (X sdiv C)
1172  Value *Op0Src;
1173  if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
1174  Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) {
1175 
1176  // In the general case, we need to make sure that the dividend is not the
1177  // minimum signed value because dividing that by -1 is UB. But here, we
1178  // know that the -1 divisor case is already handled above.
1179 
1180  Constant *NarrowDivisor =
1181  ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
1182  Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
1183  return new SExtInst(NarrowOp, Ty);
1184  }
1185 
1186  // -X / C --> X / -C (if the negation doesn't overflow).
1187  // TODO: This could be enhanced to handle arbitrary vector constants by
1188  // checking if all elements are not the min-signed-val.
1189  if (!Op1C->isMinSignedValue() &&
1190  match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1191  Constant *NegC = ConstantInt::get(Ty, -(*Op1C));
1192  Instruction *BO = BinaryOperator::CreateSDiv(X, NegC);
1193  BO->setIsExact(I.isExact());
1194  return BO;
1195  }
1196  }
1197 
1198  // -X / Y --> -(X / Y)
1199  Value *Y;
1200  if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1202  Builder.CreateSDiv(X, Y, I.getName(), I.isExact()));
1203 
1204  // abs(X) / X --> X > -1 ? 1 : -1
1205  // X / abs(X) --> X > -1 ? 1 : -1
1206  if (match(&I, m_c_BinOp(
1207  m_OneUse(m_Intrinsic<Intrinsic::abs>(m_Value(X), m_One())),
1208  m_Deferred(X)))) {
1209  Constant *NegOne = ConstantInt::getAllOnesValue(Ty);
1210  Value *Cond = Builder.CreateICmpSGT(X, NegOne);
1211  return SelectInst::Create(Cond, ConstantInt::get(Ty, 1), NegOne);
1212  }
1213 
1214  // If the sign bits of both operands are zero (i.e. we can prove they are
1215  // unsigned inputs), turn this into a udiv.
1217  if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
1218  if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
1219  // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
1220  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1221  BO->setIsExact(I.isExact());
1222  return BO;
1223  }
1224 
1225  if (match(Op1, m_NegatedPower2())) {
1226  // X sdiv (-(1 << C)) -> -(X sdiv (1 << C)) ->
1227  // -> -(X udiv (1 << C)) -> -(X u>> C)
1229  Op0, ConstantExpr::getNeg(cast<Constant>(Op1)), I, *this)));
1230  }
1231 
1232  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1233  // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1234  // Safe because the only negative value (1 << Y) can take on is
1235  // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1236  // the sign bit set.
1237  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1238  BO->setIsExact(I.isExact());
1239  return BO;
1240  }
1241  }
1242 
1243  return nullptr;
1244 }
1245 
1246 /// Remove negation and try to convert division into multiplication.
1248  Constant *C;
1249  if (!match(I.getOperand(1), m_Constant(C)))
1250  return nullptr;
1251 
1252  // -X / C --> X / -C
1253  Value *X;
1254  if (match(I.getOperand(0), m_FNeg(m_Value(X))))
1256 
1257  // If the constant divisor has an exact inverse, this is always safe. If not,
1258  // then we can still create a reciprocal if fast-math-flags allow it and the
1259  // constant is a regular number (not zero, infinite, or denormal).
1260  if (!(C->hasExactInverseFP() || (I.hasAllowReciprocal() && C->isNormalFP())))
1261  return nullptr;
1262 
1263  // Disallow denormal constants because we don't know what would happen
1264  // on all targets.
1265  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1266  // denorms are flushed?
1267  auto *RecipC = ConstantExpr::getFDiv(ConstantFP::get(I.getType(), 1.0), C);
1268  if (!RecipC->isNormalFP())
1269  return nullptr;
1270 
1271  // X / C --> X * (1 / C)
1272  return BinaryOperator::CreateFMulFMF(I.getOperand(0), RecipC, &I);
1273 }
1274 
1275 /// Remove negation and try to reassociate constant math.
1277  Constant *C;
1278  if (!match(I.getOperand(0), m_Constant(C)))
1279  return nullptr;
1280 
1281  // C / -X --> -C / X
1282  Value *X;
1283  if (match(I.getOperand(1), m_FNeg(m_Value(X))))
1285 
1286  if (!I.hasAllowReassoc() || !I.hasAllowReciprocal())
1287  return nullptr;
1288 
1289  // Try to reassociate C / X expressions where X includes another constant.
1290  Constant *C2, *NewC = nullptr;
1291  if (match(I.getOperand(1), m_FMul(m_Value(X), m_Constant(C2)))) {
1292  // C / (X * C2) --> (C / C2) / X
1293  NewC = ConstantExpr::getFDiv(C, C2);
1294  } else if (match(I.getOperand(1), m_FDiv(m_Value(X), m_Constant(C2)))) {
1295  // C / (X / C2) --> (C * C2) / X
1296  NewC = ConstantExpr::getFMul(C, C2);
1297  }
1298  // Disallow denormal constants because we don't know what would happen
1299  // on all targets.
1300  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1301  // denorms are flushed?
1302  if (!NewC || !NewC->isNormalFP())
1303  return nullptr;
1304 
1305  return BinaryOperator::CreateFDivFMF(NewC, X, &I);
1306 }
1307 
1308 /// Negate the exponent of pow/exp to fold division-by-pow() into multiply.
1311  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1312  auto *II = dyn_cast<IntrinsicInst>(Op1);
1313  if (!II || !II->hasOneUse() || !I.hasAllowReassoc() ||
1314  !I.hasAllowReciprocal())
1315  return nullptr;
1316 
1317  // Z / pow(X, Y) --> Z * pow(X, -Y)
1318  // Z / exp{2}(Y) --> Z * exp{2}(-Y)
1319  // In the general case, this creates an extra instruction, but fmul allows
1320  // for better canonicalization and optimization than fdiv.
1321  Intrinsic::ID IID = II->getIntrinsicID();
1323  switch (IID) {
1324  case Intrinsic::pow:
1325  Args.push_back(II->getArgOperand(0));
1326  Args.push_back(Builder.CreateFNegFMF(II->getArgOperand(1), &I));
1327  break;
1328  case Intrinsic::powi: {
1329  // Require 'ninf' assuming that makes powi(X, -INT_MIN) acceptable.
1330  // That is, X ** (huge negative number) is 0.0, ~1.0, or INF and so
1331  // dividing by that is INF, ~1.0, or 0.0. Code that uses powi allows
1332  // non-standard results, so this corner case should be acceptable if the
1333  // code rules out INF values.
1334  if (!I.hasNoInfs())
1335  return nullptr;
1336  Args.push_back(II->getArgOperand(0));
1337  Args.push_back(Builder.CreateNeg(II->getArgOperand(1)));
1338  Type *Tys[] = {I.getType(), II->getArgOperand(1)->getType()};
1339  Value *Pow = Builder.CreateIntrinsic(IID, Tys, Args, &I);
1340  return BinaryOperator::CreateFMulFMF(Op0, Pow, &I);
1341  }
1342  case Intrinsic::exp:
1343  case Intrinsic::exp2:
1344  Args.push_back(Builder.CreateFNegFMF(II->getArgOperand(0), &I));
1345  break;
1346  default:
1347  return nullptr;
1348  }
1349  Value *Pow = Builder.CreateIntrinsic(IID, I.getType(), Args, &I);
1350  return BinaryOperator::CreateFMulFMF(Op0, Pow, &I);
1351 }
1352 
1354  if (Value *V = SimplifyFDivInst(I.getOperand(0), I.getOperand(1),
1355  I.getFastMathFlags(),
1356  SQ.getWithInstruction(&I)))
1357  return replaceInstUsesWith(I, V);
1358 
1359  if (Instruction *X = foldVectorBinop(I))
1360  return X;
1361 
1363  return R;
1364 
1366  return R;
1367 
1368  if (Instruction *R = foldFPSignBitOps(I))
1369  return R;
1370 
1371  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1372  if (isa<Constant>(Op0))
1373  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1374  if (Instruction *R = FoldOpIntoSelect(I, SI))
1375  return R;
1376 
1377  if (isa<Constant>(Op1))
1378  if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1379  if (Instruction *R = FoldOpIntoSelect(I, SI))
1380  return R;
1381 
1382  if (I.hasAllowReassoc() && I.hasAllowReciprocal()) {
1383  Value *X, *Y;
1384  if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1385  (!isa<Constant>(Y) || !isa<Constant>(Op1))) {
1386  // (X / Y) / Z => X / (Y * Z)
1387  Value *YZ = Builder.CreateFMulFMF(Y, Op1, &I);
1388  return BinaryOperator::CreateFDivFMF(X, YZ, &I);
1389  }
1390  if (match(Op1, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1391  (!isa<Constant>(Y) || !isa<Constant>(Op0))) {
1392  // Z / (X / Y) => (Y * Z) / X
1393  Value *YZ = Builder.CreateFMulFMF(Y, Op0, &I);
1394  return BinaryOperator::CreateFDivFMF(YZ, X, &I);
1395  }
1396  // Z / (1.0 / Y) => (Y * Z)
1397  //
1398  // This is a special case of Z / (X / Y) => (Y * Z) / X, with X = 1.0. The
1399  // m_OneUse check is avoided because even in the case of the multiple uses
1400  // for 1.0/Y, the number of instructions remain the same and a division is
1401  // replaced by a multiplication.
1402  if (match(Op1, m_FDiv(m_SpecificFP(1.0), m_Value(Y))))
1403  return BinaryOperator::CreateFMulFMF(Y, Op0, &I);
1404  }
1405 
1406  if (I.hasAllowReassoc() && Op0->hasOneUse() && Op1->hasOneUse()) {
1407  // sin(X) / cos(X) -> tan(X)
1408  // cos(X) / sin(X) -> 1/tan(X) (cotangent)
1409  Value *X;
1410  bool IsTan = match(Op0, m_Intrinsic<Intrinsic::sin>(m_Value(X))) &&
1411  match(Op1, m_Intrinsic<Intrinsic::cos>(m_Specific(X)));
1412  bool IsCot =
1413  !IsTan && match(Op0, m_Intrinsic<Intrinsic::cos>(m_Value(X))) &&
1414  match(Op1, m_Intrinsic<Intrinsic::sin>(m_Specific(X)));
1415 
1416  if ((IsTan || IsCot) &&
1417  hasFloatFn(&TLI, I.getType(), LibFunc_tan, LibFunc_tanf, LibFunc_tanl)) {
1418  IRBuilder<> B(&I);
1420  B.setFastMathFlags(I.getFastMathFlags());
1422  cast<CallBase>(Op0)->getCalledFunction()->getAttributes();
1423  Value *Res = emitUnaryFloatFnCall(X, &TLI, LibFunc_tan, LibFunc_tanf,
1424  LibFunc_tanl, B, Attrs);
1425  if (IsCot)
1426  Res = B.CreateFDiv(ConstantFP::get(I.getType(), 1.0), Res);
1427  return replaceInstUsesWith(I, Res);
1428  }
1429  }
1430 
1431  // X / (X * Y) --> 1.0 / Y
1432  // Reassociate to (X / X -> 1.0) is legal when NaNs are not allowed.
1433  // We can ignore the possibility that X is infinity because INF/INF is NaN.
1434  Value *X, *Y;
1435  if (I.hasNoNaNs() && I.hasAllowReassoc() &&
1436  match(Op1, m_c_FMul(m_Specific(Op0), m_Value(Y)))) {
1437  replaceOperand(I, 0, ConstantFP::get(I.getType(), 1.0));
1438  replaceOperand(I, 1, Y);
1439  return &I;
1440  }
1441 
1442  // X / fabs(X) -> copysign(1.0, X)
1443  // fabs(X) / X -> copysign(1.0, X)
1444  if (I.hasNoNaNs() && I.hasNoInfs() &&
1445  (match(&I, m_FDiv(m_Value(X), m_FAbs(m_Deferred(X)))) ||
1446  match(&I, m_FDiv(m_FAbs(m_Value(X)), m_Deferred(X))))) {
1447  Value *V = Builder.CreateBinaryIntrinsic(
1448  Intrinsic::copysign, ConstantFP::get(I.getType(), 1.0), X, &I);
1449  return replaceInstUsesWith(I, V);
1450  }
1451 
1453  return Mul;
1454 
1455  return nullptr;
1456 }
1457 
1458 /// This function implements the transforms common to both integer remainder
1459 /// instructions (urem and srem). It is called by the visitors to those integer
1460 /// remainder instructions.
1461 /// Common integer remainder transforms
1463  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1464 
1465  // The RHS is known non-zero.
1466  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I))
1467  return replaceOperand(I, 1, V);
1468 
1469  // Handle cases involving: rem X, (select Cond, Y, Z)
1470  if (simplifyDivRemOfSelectWithZeroOp(I))
1471  return &I;
1472 
1473  // If the divisor is a select-of-constants, try to constant fold all rem ops:
1474  // C % (select Cond, TrueC, FalseC) --> select Cond, (C % TrueC), (C % FalseC)
1475  // TODO: Adapt simplifyDivRemOfSelectWithZeroOp to allow this and other folds.
1476  if (match(Op0, m_ImmConstant()) &&
1478  if (Instruction *R = FoldOpIntoSelect(I, cast<SelectInst>(Op1)))
1479  return R;
1480  }
1481 
1482  if (isa<Constant>(Op1)) {
1483  if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1484  if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1485  if (Instruction *R = FoldOpIntoSelect(I, SI))
1486  return R;
1487  } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
1488  const APInt *Op1Int;
1489  if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
1490  (I.getOpcode() == Instruction::URem ||
1491  !Op1Int->isMinSignedValue())) {
1492  // foldOpIntoPhi will speculate instructions to the end of the PHI's
1493  // predecessor blocks, so do this only if we know the srem or urem
1494  // will not fault.
1495  if (Instruction *NV = foldOpIntoPhi(I, PN))
1496  return NV;
1497  }
1498  }
1499 
1500  // See if we can fold away this rem instruction.
1501  if (SimplifyDemandedInstructionBits(I))
1502  return &I;
1503  }
1504  }
1505 
1506  return nullptr;
1507 }
1508 
1510  if (Value *V = SimplifyURemInst(I.getOperand(0), I.getOperand(1),
1511  SQ.getWithInstruction(&I)))
1512  return replaceInstUsesWith(I, V);
1513 
1514  if (Instruction *X = foldVectorBinop(I))
1515  return X;
1516 
1517  if (Instruction *common = commonIRemTransforms(I))
1518  return common;
1519 
1520  if (Instruction *NarrowRem = narrowUDivURem(I, Builder))
1521  return NarrowRem;
1522 
1523  // X urem Y -> X and Y-1, where Y is a power of 2,
1524  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1525  Type *Ty = I.getType();
1526  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1527  // This may increase instruction count, we don't enforce that Y is a
1528  // constant.
1530  Value *Add = Builder.CreateAdd(Op1, N1);
1531  return BinaryOperator::CreateAnd(Op0, Add);
1532  }
1533 
1534  // 1 urem X -> zext(X != 1)
1535  if (match(Op0, m_One())) {
1536  Value *Cmp = Builder.CreateICmpNE(Op1, ConstantInt::get(Ty, 1));
1537  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
1538  }
1539 
1540  // X urem C -> X < C ? X : X - C, where C >= signbit.
1541  if (match(Op1, m_Negative())) {
1542  Value *Cmp = Builder.CreateICmpULT(Op0, Op1);
1543  Value *Sub = Builder.CreateSub(Op0, Op1);
1544  return SelectInst::Create(Cmp, Op0, Sub);
1545  }
1546 
1547  // If the divisor is a sext of a boolean, then the divisor must be max
1548  // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also
1549  // max unsigned value. In that case, the remainder is 0:
1550  // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0
1551  Value *X;
1552  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1553  Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1554  return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), Op0);
1555  }
1556 
1557  return nullptr;
1558 }
1559 
1561  if (Value *V = SimplifySRemInst(I.getOperand(0), I.getOperand(1),
1562  SQ.getWithInstruction(&I)))
1563  return replaceInstUsesWith(I, V);
1564 
1565  if (Instruction *X = foldVectorBinop(I))
1566  return X;
1567 
1568  // Handle the integer rem common cases
1569  if (Instruction *Common = commonIRemTransforms(I))
1570  return Common;
1571 
1572  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1573  {
1574  const APInt *Y;
1575  // X % -Y -> X % Y
1576  if (match(Op1, m_Negative(Y)) && !Y->isMinSignedValue())
1577  return replaceOperand(I, 1, ConstantInt::get(I.getType(), -*Y));
1578  }
1579 
1580  // -X srem Y --> -(X srem Y)
1581  Value *X, *Y;
1582  if (match(&I, m_SRem(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1583  return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y));
1584 
1585  // If the sign bits of both operands are zero (i.e. we can prove they are
1586  // unsigned inputs), turn this into a urem.
1587  APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
1588  if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1589  MaskedValueIsZero(Op0, Mask, 0, &I)) {
1590  // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1591  return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1592  }
1593 
1594  // If it's a constant vector, flip any negative values positive.
1595  if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1596  Constant *C = cast<Constant>(Op1);
1597  unsigned VWidth = cast<FixedVectorType>(C->getType())->getNumElements();
1598 
1599  bool hasNegative = false;
1600  bool hasMissing = false;
1601  for (unsigned i = 0; i != VWidth; ++i) {
1602  Constant *Elt = C->getAggregateElement(i);
1603  if (!Elt) {
1604  hasMissing = true;
1605  break;
1606  }
1607 
1608  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1609  if (RHS->isNegative())
1610  hasNegative = true;
1611  }
1612 
1613  if (hasNegative && !hasMissing) {
1614  SmallVector<Constant *, 16> Elts(VWidth);
1615  for (unsigned i = 0; i != VWidth; ++i) {
1616  Elts[i] = C->getAggregateElement(i); // Handle undef, etc.
1617  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1618  if (RHS->isNegative())
1619  Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1620  }
1621  }
1622 
1623  Constant *NewRHSV = ConstantVector::get(Elts);
1624  if (NewRHSV != C) // Don't loop on -MININT
1625  return replaceOperand(I, 1, NewRHSV);
1626  }
1627  }
1628 
1629  return nullptr;
1630 }
1631 
1633  if (Value *V = SimplifyFRemInst(I.getOperand(0), I.getOperand(1),
1634  I.getFastMathFlags(),
1635  SQ.getWithInstruction(&I)))
1636  return replaceInstUsesWith(I, V);
1637 
1638  if (Instruction *X = foldVectorBinop(I))
1639  return X;
1640 
1641  return nullptr;
1642 }
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:476
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:939
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: 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:1237
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:2782
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:367
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: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:2172
llvm::BinaryOperator::CreateWithCopiedFlags
static BinaryOperator * CreateWithCopiedFlags(BinaryOps Opc, Value *V1, Value *V2, Instruction *CopyO, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: InstrTypes.h:251
llvm::SelectPatternResult::Flavor
SelectPatternFlavor Flavor
Definition: ValueTracking.h:709
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:1460
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1177
llvm::InstCombiner::Builder
BuilderTy & Builder
Definition: InstCombiner.h:58
foldUDivPow2Cst
static Instruction * foldUDivPow2Cst(Value *Op0, Value *Op1, const BinaryOperator &I, InstCombinerImpl &IC)
Definition: InstCombineMulDivRem.cpp:918
llvm::BinaryOperator::CreateFDivFMF
static BinaryOperator * CreateFDivFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:274
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:1247
ErrorHandling.h
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::InstCombinerImpl::visitSRem
Instruction * visitSRem(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1560
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:3152
llvm::InstCombinerImpl::visitFDiv
Instruction * visitFDiv(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1353
llvm::Instruction::hasNoUnsignedWrap
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
Definition: Instruction.cpp:136
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: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:1412
llvm::AttributeList
Definition: Attributes.h:404
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: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:2832
RHS
Value * RHS
Definition: X86PartialReduction.cpp:74
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:6234
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:2766
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:685
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: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
KnownBits.h
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
visitUDivOperand
static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I, SmallVectorImpl< UDivFoldAction > &Actions, unsigned Depth=0)
Definition: InstCombineMulDivRem.cpp:958
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:694
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:1194
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:1462
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1772
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: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:405
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:394
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: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: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:932
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:1226
Type.h
llvm::ConstantExpr::getFNeg
static Constant * getFNeg(Constant *C)
Definition: Constants.cpp:2727
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:5237
llvm::Function::getAttributes
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:316
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:1887
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:2144
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:166
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:269
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: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::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:932
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:2815
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: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:693
llvm::Negator::Negate
static LLVM_NODISCARD Value * Negate(bool LHSIsZero, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
Definition: InstCombineNegator.cpp:503
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1741
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:1126
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:4812
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:1276
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:5300
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:190
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:68
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:196
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1402
llvm::ConstantExpr::getFMul
static Constant * getFMul(Constant *C1, Constant *C2)
Definition: Constants.cpp:2768
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4851
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:1465
llvm::ConstantInt::getFalse
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:887
MaxDepth
static const unsigned MaxDepth
Definition: InstCombineMulDivRem.cpp:884
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:1180
llvm::InstCombinerImpl::visitURem
Instruction * visitURem(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1509
Constant.h
llvm::NVPTX::PTXLdStInstCode::V2
@ V2
Definition: NVPTX.h:123
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:880
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: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:259
llvm::InstCombinerImpl::visitFRem
Instruction * visitFRem(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:1632
llvm::ConstantExpr::getNeg
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2720
llvm::InstCombinerImpl::visitMul
Instruction * visitMul(BinaryOperator &I)
Definition: InstCombineMulDivRem.cpp:147
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:325
llvm::ConstantInt::getBool
static ConstantInt * getBool(LLVMContext &Context, bool V)
Definition: Constants.cpp:894
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:5338
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:979
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:5305
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:2782
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:1309
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:801
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:2242
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:1205
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:422
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:789
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:2362
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:140
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:1300
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:2271
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:303
llvm::IRBuilderBase::CreateSub
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1228
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:3196
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:2750
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: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:1121
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:1032
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:997
llvm::BinaryOperator::CreateFSubFMF
static BinaryOperator * CreateFSubFMF(Value *V1, Value *V2, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:264
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:44
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38