LLVM  7.0.0svn
InstCombineMulDivRem.cpp
Go to the documentation of this file.
1 //===- InstCombineMulDivRem.cpp -------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the visit functions for mul, fmul, sdiv, udiv, fdiv,
11 // srem, urem, frem.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "InstCombineInternal.h"
16 #include "llvm/ADT/APFloat.h"
17 #include "llvm/ADT/APInt.h"
18 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/IR/BasicBlock.h"
21 #include "llvm/IR/Constant.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/InstrTypes.h"
24 #include "llvm/IR/Instruction.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/IR/IntrinsicInst.h"
27 #include "llvm/IR/Intrinsics.h"
28 #include "llvm/IR/Operator.h"
29 #include "llvm/IR/PatternMatch.h"
30 #include "llvm/IR/Type.h"
31 #include "llvm/IR/Value.h"
32 #include "llvm/Support/Casting.h"
34 #include "llvm/Support/KnownBits.h"
37 #include <cassert>
38 #include <cstddef>
39 #include <cstdint>
40 #include <utility>
41 
42 using namespace llvm;
43 using namespace PatternMatch;
44 
45 #define DEBUG_TYPE "instcombine"
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 <<.
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  I->setOperand(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()) {
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 /// A helper routine of InstCombiner::visitMul().
99 ///
100 /// If C is a scalar/vector of known powers of 2, then this function returns
101 /// a new scalar/vector obtained from logBase2 of C.
102 /// Return a null pointer otherwise.
104  const APInt *IVal;
105  if (match(C, m_APInt(IVal)) && IVal->isPowerOf2())
106  return ConstantInt::get(Ty, IVal->logBase2());
107 
108  if (!Ty->isVectorTy())
109  return nullptr;
110 
112  for (unsigned I = 0, E = Ty->getVectorNumElements(); I != E; ++I) {
113  Constant *Elt = C->getAggregateElement(I);
114  if (!Elt)
115  return nullptr;
116  if (isa<UndefValue>(Elt)) {
118  continue;
119  }
120  if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2())
121  return nullptr;
122  Elts.push_back(ConstantInt::get(Ty->getScalarType(), IVal->logBase2()));
123  }
124 
125  return ConstantVector::get(Elts);
126 }
127 
129  if (Value *V = SimplifyMulInst(I.getOperand(0), I.getOperand(1),
130  SQ.getWithInstruction(&I)))
131  return replaceInstUsesWith(I, V);
132 
133  if (SimplifyAssociativeOrCommutative(I))
134  return &I;
135 
136  if (Instruction *X = foldShuffledBinop(I))
137  return X;
138 
139  if (Value *V = SimplifyUsingDistributiveLaws(I))
140  return replaceInstUsesWith(I, V);
141 
142  // X * -1 == 0 - X
143  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
144  if (match(Op1, m_AllOnes())) {
146  if (I.hasNoSignedWrap())
147  BO->setHasNoSignedWrap();
148  return BO;
149  }
150 
151  // Also allow combining multiply instructions on vectors.
152  {
153  Value *NewOp;
154  Constant *C1, *C2;
155  const APInt *IVal;
156  if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
157  m_Constant(C1))) &&
158  match(C1, m_APInt(IVal))) {
159  // ((X << C2)*C1) == (X * (C1 << C2))
160  Constant *Shl = ConstantExpr::getShl(C1, C2);
161  BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0));
162  BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl);
163  if (I.hasNoUnsignedWrap() && Mul->hasNoUnsignedWrap())
164  BO->setHasNoUnsignedWrap();
165  if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap() &&
166  Shl->isNotMinSignedValue())
167  BO->setHasNoSignedWrap();
168  return BO;
169  }
170 
171  if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
172  // Replace X*(2^C) with X << C, where C is either a scalar or a vector.
173  if (Constant *NewCst = getLogBase2(NewOp->getType(), C1)) {
174  unsigned Width = NewCst->getType()->getPrimitiveSizeInBits();
175  BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
176 
177  if (I.hasNoUnsignedWrap())
178  Shl->setHasNoUnsignedWrap();
179  if (I.hasNoSignedWrap()) {
180  const APInt *V;
181  if (match(NewCst, m_APInt(V)) && *V != Width - 1)
182  Shl->setHasNoSignedWrap();
183  }
184 
185  return Shl;
186  }
187  }
188  }
189 
190  if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
191  // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n
192  // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n
193  // The "* (2**n)" thus becomes a potential shifting opportunity.
194  {
195  const APInt & Val = CI->getValue();
196  const APInt &PosVal = Val.abs();
197  if (Val.isNegative() && PosVal.isPowerOf2()) {
198  Value *X = nullptr, *Y = nullptr;
199  if (Op0->hasOneUse()) {
200  ConstantInt *C1;
201  Value *Sub = nullptr;
202  if (match(Op0, m_Sub(m_Value(Y), m_Value(X))))
203  Sub = Builder.CreateSub(X, Y, "suba");
204  else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1))))
205  Sub = Builder.CreateSub(Builder.CreateNeg(C1), Y, "subc");
206  if (Sub)
207  return
209  ConstantInt::get(Y->getType(), PosVal));
210  }
211  }
212  }
213  }
214 
215  if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
216  return FoldedMul;
217 
218  // Simplify mul instructions with a constant RHS.
219  if (isa<Constant>(Op1)) {
220  // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
221  Value *X;
222  Constant *C1;
223  if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) {
224  Value *Mul = Builder.CreateMul(C1, Op1);
225  // Only go forward with the transform if C1*CI simplifies to a tidier
226  // constant.
227  if (!match(Mul, m_Mul(m_Value(), m_Value())))
228  return BinaryOperator::CreateAdd(Builder.CreateMul(X, Op1), Mul);
229  }
230  }
231 
232  // -X * C --> X * -C
233  Value *X, *Y;
234  Constant *Op1C;
235  if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Constant(Op1C)))
237 
238  // -X * -Y --> X * Y
239  if (match(Op0, m_Neg(m_Value(X))) && match(Op1, m_Neg(m_Value(Y)))) {
240  auto *NewMul = BinaryOperator::CreateMul(X, Y);
241  if (I.hasNoSignedWrap() &&
242  cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap() &&
243  cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap())
244  NewMul->setHasNoSignedWrap();
245  return NewMul;
246  }
247 
248  // (X / Y) * Y = X - (X % Y)
249  // (X / Y) * -Y = (X % Y) - X
250  {
251  Value *Y = Op1;
253  if (!Div || (Div->getOpcode() != Instruction::UDiv &&
254  Div->getOpcode() != Instruction::SDiv)) {
255  Y = Op0;
256  Div = dyn_cast<BinaryOperator>(Op1);
257  }
258  Value *Neg = dyn_castNegVal(Y);
259  if (Div && Div->hasOneUse() &&
260  (Div->getOperand(1) == Y || Div->getOperand(1) == Neg) &&
261  (Div->getOpcode() == Instruction::UDiv ||
262  Div->getOpcode() == Instruction::SDiv)) {
263  Value *X = Div->getOperand(0), *DivOp1 = Div->getOperand(1);
264 
265  // If the division is exact, X % Y is zero, so we end up with X or -X.
266  if (Div->isExact()) {
267  if (DivOp1 == Y)
268  return replaceInstUsesWith(I, X);
269  return BinaryOperator::CreateNeg(X);
270  }
271 
272  auto RemOpc = Div->getOpcode() == Instruction::UDiv ? Instruction::URem
273  : Instruction::SRem;
274  Value *Rem = Builder.CreateBinOp(RemOpc, X, DivOp1);
275  if (DivOp1 == Y)
276  return BinaryOperator::CreateSub(X, Rem);
277  return BinaryOperator::CreateSub(Rem, X);
278  }
279  }
280 
281  /// i1 mul -> i1 and.
282  if (I.getType()->isIntOrIntVectorTy(1))
283  return BinaryOperator::CreateAnd(Op0, Op1);
284 
285  // X*(1 << Y) --> X << Y
286  // (1 << Y)*X --> X << Y
287  {
288  Value *Y;
289  BinaryOperator *BO = nullptr;
290  bool ShlNSW = false;
291  if (match(Op0, m_Shl(m_One(), m_Value(Y)))) {
292  BO = BinaryOperator::CreateShl(Op1, Y);
293  ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap();
294  } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) {
295  BO = BinaryOperator::CreateShl(Op0, Y);
296  ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap();
297  }
298  if (BO) {
299  if (I.hasNoUnsignedWrap())
300  BO->setHasNoUnsignedWrap();
301  if (I.hasNoSignedWrap() && ShlNSW)
302  BO->setHasNoSignedWrap();
303  return BO;
304  }
305  }
306 
307  // (bool X) * Y --> X ? Y : 0
308  // Y * (bool X) --> X ? Y : 0
309  if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
310  return SelectInst::Create(X, Op1, ConstantInt::get(I.getType(), 0));
311  if (match(Op1, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1))
312  return SelectInst::Create(X, Op0, ConstantInt::get(I.getType(), 0));
313 
314  // (lshr X, 31) * Y --> (ashr X, 31) & Y
315  // Y * (lshr X, 31) --> (ashr X, 31) & Y
316  // TODO: We are not checking one-use because the elimination of the multiply
317  // is better for analysis?
318  // TODO: Should we canonicalize to '(X < 0) ? Y : 0' instead? That would be
319  // more similar to what we're doing above.
320  const APInt *C;
321  if (match(Op0, m_LShr(m_Value(X), m_APInt(C))) && *C == C->getBitWidth() - 1)
322  return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op1);
323  if (match(Op1, m_LShr(m_Value(X), m_APInt(C))) && *C == C->getBitWidth() - 1)
324  return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op0);
325 
326  // Check for (mul (sext x), y), see if we can merge this into an
327  // integer mul followed by a sext.
328  if (SExtInst *Op0Conv = dyn_cast<SExtInst>(Op0)) {
329  // (mul (sext x), cst) --> (sext (mul x, cst'))
330  if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
331  if (Op0Conv->hasOneUse()) {
332  Constant *CI =
333  ConstantExpr::getTrunc(Op1C, Op0Conv->getOperand(0)->getType());
334  if (ConstantExpr::getSExt(CI, I.getType()) == Op1C &&
335  willNotOverflowSignedMul(Op0Conv->getOperand(0), CI, I)) {
336  // Insert the new, smaller mul.
337  Value *NewMul =
338  Builder.CreateNSWMul(Op0Conv->getOperand(0), CI, "mulconv");
339  return new SExtInst(NewMul, I.getType());
340  }
341  }
342  }
343 
344  // (mul (sext x), (sext y)) --> (sext (mul int x, y))
345  if (SExtInst *Op1Conv = dyn_cast<SExtInst>(Op1)) {
346  // Only do this if x/y have the same type, if at last one of them has a
347  // single use (so we don't increase the number of sexts), and if the
348  // integer mul will not overflow.
349  if (Op0Conv->getOperand(0)->getType() ==
350  Op1Conv->getOperand(0)->getType() &&
351  (Op0Conv->hasOneUse() || Op1Conv->hasOneUse()) &&
352  willNotOverflowSignedMul(Op0Conv->getOperand(0),
353  Op1Conv->getOperand(0), I)) {
354  // Insert the new integer mul.
355  Value *NewMul = Builder.CreateNSWMul(
356  Op0Conv->getOperand(0), Op1Conv->getOperand(0), "mulconv");
357  return new SExtInst(NewMul, I.getType());
358  }
359  }
360  }
361 
362  // Check for (mul (zext x), y), see if we can merge this into an
363  // integer mul followed by a zext.
364  if (auto *Op0Conv = dyn_cast<ZExtInst>(Op0)) {
365  // (mul (zext x), cst) --> (zext (mul x, cst'))
366  if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
367  if (Op0Conv->hasOneUse()) {
368  Constant *CI =
369  ConstantExpr::getTrunc(Op1C, Op0Conv->getOperand(0)->getType());
370  if (ConstantExpr::getZExt(CI, I.getType()) == Op1C &&
371  willNotOverflowUnsignedMul(Op0Conv->getOperand(0), CI, I)) {
372  // Insert the new, smaller mul.
373  Value *NewMul =
374  Builder.CreateNUWMul(Op0Conv->getOperand(0), CI, "mulconv");
375  return new ZExtInst(NewMul, I.getType());
376  }
377  }
378  }
379 
380  // (mul (zext x), (zext y)) --> (zext (mul int x, y))
381  if (auto *Op1Conv = dyn_cast<ZExtInst>(Op1)) {
382  // Only do this if x/y have the same type, if at last one of them has a
383  // single use (so we don't increase the number of zexts), and if the
384  // integer mul will not overflow.
385  if (Op0Conv->getOperand(0)->getType() ==
386  Op1Conv->getOperand(0)->getType() &&
387  (Op0Conv->hasOneUse() || Op1Conv->hasOneUse()) &&
388  willNotOverflowUnsignedMul(Op0Conv->getOperand(0),
389  Op1Conv->getOperand(0), I)) {
390  // Insert the new integer mul.
391  Value *NewMul = Builder.CreateNUWMul(
392  Op0Conv->getOperand(0), Op1Conv->getOperand(0), "mulconv");
393  return new ZExtInst(NewMul, I.getType());
394  }
395  }
396  }
397 
398  bool Changed = false;
399  if (!I.hasNoSignedWrap() && willNotOverflowSignedMul(Op0, Op1, I)) {
400  Changed = true;
401  I.setHasNoSignedWrap(true);
402  }
403 
404  if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedMul(Op0, Op1, I)) {
405  Changed = true;
406  I.setHasNoUnsignedWrap(true);
407  }
408 
409  return Changed ? &I : nullptr;
410 }
411 
413  if (Value *V = SimplifyFMulInst(I.getOperand(0), I.getOperand(1),
414  I.getFastMathFlags(),
415  SQ.getWithInstruction(&I)))
416  return replaceInstUsesWith(I, V);
417 
418  if (SimplifyAssociativeOrCommutative(I))
419  return &I;
420 
421  if (Instruction *X = foldShuffledBinop(I))
422  return X;
423 
424  if (Instruction *FoldedMul = foldBinOpIntoSelectOrPhi(I))
425  return FoldedMul;
426 
427  // X * -1.0 --> -X
428  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
429  if (match(Op1, m_SpecificFP(-1.0)))
430  return BinaryOperator::CreateFNegFMF(Op0, &I);
431 
432  // -X * -Y --> X * Y
433  Value *X, *Y;
434  if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y))))
435  return BinaryOperator::CreateFMulFMF(X, Y, &I);
436 
437  // -X * C --> X * -C
438  Constant *C;
439  if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_Constant(C)))
441 
442  // Sink negation: -X * Y --> -(X * Y)
443  if (match(Op0, m_OneUse(m_FNeg(m_Value(X)))))
444  return BinaryOperator::CreateFNegFMF(Builder.CreateFMulFMF(X, Op1, &I), &I);
445 
446  // Sink negation: Y * -X --> -(X * Y)
447  if (match(Op1, m_OneUse(m_FNeg(m_Value(X)))))
448  return BinaryOperator::CreateFNegFMF(Builder.CreateFMulFMF(X, Op0, &I), &I);
449 
450  // fabs(X) * fabs(X) -> X * X
451  if (Op0 == Op1 && match(Op0, m_Intrinsic<Intrinsic::fabs>(m_Value(X))))
452  return BinaryOperator::CreateFMulFMF(X, X, &I);
453 
454  // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E)
455  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
456  return replaceInstUsesWith(I, V);
457 
458  if (I.hasAllowReassoc()) {
459  // Reassociate constant RHS with another constant to form constant
460  // expression.
461  if (match(Op1, m_Constant(C)) && C->isFiniteNonZeroFP()) {
462  Constant *C1;
463  if (match(Op0, m_OneUse(m_FDiv(m_Constant(C1), m_Value(X))))) {
464  // (C1 / X) * C --> (C * C1) / X
465  Constant *CC1 = ConstantExpr::getFMul(C, C1);
466  if (CC1->isNormalFP())
467  return BinaryOperator::CreateFDivFMF(CC1, X, &I);
468  }
469  if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
470  // (X / C1) * C --> X * (C / C1)
471  Constant *CDivC1 = ConstantExpr::getFDiv(C, C1);
472  if (CDivC1->isNormalFP())
473  return BinaryOperator::CreateFMulFMF(X, CDivC1, &I);
474 
475  // If the constant was a denormal, try reassociating differently.
476  // (X / C1) * C --> X / (C1 / C)
477  Constant *C1DivC = ConstantExpr::getFDiv(C1, C);
478  if (Op0->hasOneUse() && C1DivC->isNormalFP())
479  return BinaryOperator::CreateFDivFMF(X, C1DivC, &I);
480  }
481 
482  // We do not need to match 'fadd C, X' and 'fsub X, C' because they are
483  // canonicalized to 'fadd X, C'. Distributing the multiply may allow
484  // further folds and (X * C) + C2 is 'fma'.
485  if (match(Op0, m_OneUse(m_FAdd(m_Value(X), m_Constant(C1))))) {
486  // (X + C1) * C --> (X * C) + (C * C1)
487  Constant *CC1 = ConstantExpr::getFMul(C, C1);
488  Value *XC = Builder.CreateFMulFMF(X, C, &I);
489  return BinaryOperator::CreateFAddFMF(XC, CC1, &I);
490  }
491  if (match(Op0, m_OneUse(m_FSub(m_Constant(C1), m_Value(X))))) {
492  // (C1 - X) * C --> (C * C1) - (X * C)
493  Constant *CC1 = ConstantExpr::getFMul(C, C1);
494  Value *XC = Builder.CreateFMulFMF(X, C, &I);
495  return BinaryOperator::CreateFSubFMF(CC1, XC, &I);
496  }
497  }
498 
499  // sqrt(X) * sqrt(Y) -> sqrt(X * Y)
500  // nnan disallows the possibility of returning a number if both operands are
501  // negative (in that case, we should return NaN).
502  if (I.hasNoNaNs() &&
503  match(Op0, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(X)))) &&
504  match(Op1, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) {
505  Value *XY = Builder.CreateFMulFMF(X, Y, &I);
506  Value *Sqrt = Builder.CreateIntrinsic(Intrinsic::sqrt, { XY }, &I);
507  return replaceInstUsesWith(I, Sqrt);
508  }
509 
510  // (X*Y) * X => (X*X) * Y where Y != X
511  // The purpose is two-fold:
512  // 1) to form a power expression (of X).
513  // 2) potentially shorten the critical path: After transformation, the
514  // latency of the instruction Y is amortized by the expression of X*X,
515  // and therefore Y is in a "less critical" position compared to what it
516  // was before the transformation.
517  if (match(Op0, m_OneUse(m_c_FMul(m_Specific(Op1), m_Value(Y)))) &&
518  Op1 != Y) {
519  Value *XX = Builder.CreateFMulFMF(Op1, Op1, &I);
520  return BinaryOperator::CreateFMulFMF(XX, Y, &I);
521  }
522  if (match(Op1, m_OneUse(m_c_FMul(m_Specific(Op0), m_Value(Y)))) &&
523  Op0 != Y) {
524  Value *XX = Builder.CreateFMulFMF(Op0, Op0, &I);
525  return BinaryOperator::CreateFMulFMF(XX, Y, &I);
526  }
527  }
528 
529  // log2(X * 0.5) * Y = log2(X) * Y - Y
530  if (I.isFast()) {
531  IntrinsicInst *Log2 = nullptr;
532  if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::log2>(
533  m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
534  Log2 = cast<IntrinsicInst>(Op0);
535  Y = Op1;
536  }
537  if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::log2>(
538  m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
539  Log2 = cast<IntrinsicInst>(Op1);
540  Y = Op0;
541  }
542  if (Log2) {
543  Log2->setArgOperand(0, X);
544  Log2->copyFastMathFlags(&I);
545  Value *LogXTimesY = Builder.CreateFMulFMF(Log2, Y, &I);
546  return BinaryOperator::CreateFSubFMF(LogXTimesY, Y, &I);
547  }
548  }
549 
550  return nullptr;
551 }
552 
553 /// Fold a divide or remainder with a select instruction divisor when one of the
554 /// select operands is zero. In that case, we can use the other select operand
555 /// because div/rem by zero is undefined.
558  if (!SI)
559  return false;
560 
561  int NonNullOperand;
562  if (match(SI->getTrueValue(), m_Zero()))
563  // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
564  NonNullOperand = 2;
565  else if (match(SI->getFalseValue(), m_Zero()))
566  // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
567  NonNullOperand = 1;
568  else
569  return false;
570 
571  // Change the div/rem to use 'Y' instead of the select.
572  I.setOperand(1, SI->getOperand(NonNullOperand));
573 
574  // Okay, we know we replace the operand of the div/rem with 'Y' with no
575  // problem. However, the select, or the condition of the select may have
576  // multiple uses. Based on our knowledge that the operand must be non-zero,
577  // propagate the known value for the select into other uses of it, and
578  // propagate a known value of the condition into its other users.
579 
580  // If the select and condition only have a single use, don't bother with this,
581  // early exit.
582  Value *SelectCond = SI->getCondition();
583  if (SI->use_empty() && SelectCond->hasOneUse())
584  return true;
585 
586  // Scan the current block backward, looking for other uses of SI.
587  BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin();
588  Type *CondTy = SelectCond->getType();
589  while (BBI != BBFront) {
590  --BBI;
591  // If we found an instruction that we can't assume will return, so
592  // information from below it cannot be propagated above it.
594  break;
595 
596  // Replace uses of the select or its condition with the known values.
597  for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end();
598  I != E; ++I) {
599  if (*I == SI) {
600  *I = SI->getOperand(NonNullOperand);
601  Worklist.Add(&*BBI);
602  } else if (*I == SelectCond) {
603  *I = NonNullOperand == 1 ? ConstantInt::getTrue(CondTy)
604  : ConstantInt::getFalse(CondTy);
605  Worklist.Add(&*BBI);
606  }
607  }
608 
609  // If we past the instruction, quit looking for it.
610  if (&*BBI == SI)
611  SI = nullptr;
612  if (&*BBI == SelectCond)
613  SelectCond = nullptr;
614 
615  // If we ran out of things to eliminate, break out of the loop.
616  if (!SelectCond && !SI)
617  break;
618 
619  }
620  return true;
621 }
622 
623 /// True if the multiply can not be expressed in an int this size.
624 static bool multiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
625  bool IsSigned) {
626  bool Overflow;
627  Product = IsSigned ? C1.smul_ov(C2, Overflow) : C1.umul_ov(C2, Overflow);
628  return Overflow;
629 }
630 
631 /// True if C1 is a multiple of C2. Quotient contains C1/C2.
632 static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
633  bool IsSigned) {
634  assert(C1.getBitWidth() == C2.getBitWidth() && "Constant widths not equal");
635 
636  // Bail if we will divide by zero.
637  if (C2.isNullValue())
638  return false;
639 
640  // Bail if we would divide INT_MIN by -1.
641  if (IsSigned && C1.isMinSignedValue() && C2.isAllOnesValue())
642  return false;
643 
644  APInt Remainder(C1.getBitWidth(), /*Val=*/0ULL, IsSigned);
645  if (IsSigned)
646  APInt::sdivrem(C1, C2, Quotient, Remainder);
647  else
648  APInt::udivrem(C1, C2, Quotient, Remainder);
649 
650  return Remainder.isMinValue();
651 }
652 
653 /// This function implements the transforms common to both integer division
654 /// instructions (udiv and sdiv). It is called by the visitors to those integer
655 /// division instructions.
656 /// Common integer divide transforms
658  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
659  bool IsSigned = I.getOpcode() == Instruction::SDiv;
660  Type *Ty = I.getType();
661 
662  // The RHS is known non-zero.
663  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
664  I.setOperand(1, V);
665  return &I;
666  }
667 
668  // Handle cases involving: [su]div X, (select Cond, Y, Z)
669  // This does not apply for fdiv.
670  if (simplifyDivRemOfSelectWithZeroOp(I))
671  return &I;
672 
673  const APInt *C2;
674  if (match(Op1, m_APInt(C2))) {
675  Value *X;
676  const APInt *C1;
677 
678  // (X / C1) / C2 -> X / (C1*C2)
679  if ((IsSigned && match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))) ||
680  (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_APInt(C1))))) {
681  APInt Product(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
682  if (!multiplyOverflows(*C1, *C2, Product, IsSigned))
683  return BinaryOperator::Create(I.getOpcode(), X,
684  ConstantInt::get(Ty, Product));
685  }
686 
687  if ((IsSigned && match(Op0, m_NSWMul(m_Value(X), m_APInt(C1)))) ||
688  (!IsSigned && match(Op0, m_NUWMul(m_Value(X), m_APInt(C1))))) {
689  APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
690 
691  // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
692  if (isMultiple(*C2, *C1, Quotient, IsSigned)) {
693  auto *NewDiv = BinaryOperator::Create(I.getOpcode(), X,
694  ConstantInt::get(Ty, Quotient));
695  NewDiv->setIsExact(I.isExact());
696  return NewDiv;
697  }
698 
699  // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
700  if (isMultiple(*C1, *C2, Quotient, IsSigned)) {
701  auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
702  ConstantInt::get(Ty, Quotient));
703  auto *OBO = cast<OverflowingBinaryOperator>(Op0);
704  Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
705  Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
706  return Mul;
707  }
708  }
709 
710  if ((IsSigned && match(Op0, m_NSWShl(m_Value(X), m_APInt(C1))) &&
711  *C1 != C1->getBitWidth() - 1) ||
712  (!IsSigned && match(Op0, m_NUWShl(m_Value(X), m_APInt(C1))))) {
713  APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
714  APInt C1Shifted = APInt::getOneBitSet(
715  C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue()));
716 
717  // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of 1 << C1.
718  if (isMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
719  auto *BO = BinaryOperator::Create(I.getOpcode(), X,
720  ConstantInt::get(Ty, Quotient));
721  BO->setIsExact(I.isExact());
722  return BO;
723  }
724 
725  // (X << C1) / C2 -> X * ((1 << C1) / C2) if 1 << C1 is a multiple of C2.
726  if (isMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
727  auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
728  ConstantInt::get(Ty, Quotient));
729  auto *OBO = cast<OverflowingBinaryOperator>(Op0);
730  Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
731  Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
732  return Mul;
733  }
734  }
735 
736  if (!C2->isNullValue()) // avoid X udiv 0
737  if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I))
738  return FoldedDiv;
739  }
740 
741  if (match(Op0, m_One())) {
742  assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?");
743  if (IsSigned) {
744  // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the
745  // result is one, if Op1 is -1 then the result is minus one, otherwise
746  // it's zero.
747  Value *Inc = Builder.CreateAdd(Op1, Op0);
748  Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(Ty, 3));
749  return SelectInst::Create(Cmp, Op1, ConstantInt::get(Ty, 0));
750  } else {
751  // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
752  // result is one, otherwise it's zero.
753  return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), Ty);
754  }
755  }
756 
757  // See if we can fold away this div instruction.
758  if (SimplifyDemandedInstructionBits(I))
759  return &I;
760 
761  // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
762  Value *X, *Z;
763  if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) // (X - Z) / Y; Y = Op1
764  if ((IsSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
765  (!IsSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
766  return BinaryOperator::Create(I.getOpcode(), X, Op1);
767 
768  // (X << Y) / X -> 1 << Y
769  Value *Y;
770  if (IsSigned && match(Op0, m_NSWShl(m_Specific(Op1), m_Value(Y))))
771  return BinaryOperator::CreateNSWShl(ConstantInt::get(Ty, 1), Y);
772  if (!IsSigned && match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y))))
773  return BinaryOperator::CreateNUWShl(ConstantInt::get(Ty, 1), Y);
774 
775  // X / (X * Y) -> 1 / Y if the multiplication does not overflow.
776  if (match(Op1, m_c_Mul(m_Specific(Op0), m_Value(Y)))) {
777  bool HasNSW = cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap();
778  bool HasNUW = cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap();
779  if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) {
780  I.setOperand(0, ConstantInt::get(Ty, 1));
781  I.setOperand(1, Y);
782  return &I;
783  }
784  }
785 
786  return nullptr;
787 }
788 
789 static const unsigned MaxDepth = 6;
790 
791 namespace {
792 
793 using FoldUDivOperandCb = Instruction *(*)(Value *Op0, Value *Op1,
794  const BinaryOperator &I,
795  InstCombiner &IC);
796 
797 /// Used to maintain state for visitUDivOperand().
798 struct UDivFoldAction {
799  /// Informs visitUDiv() how to fold this operand. This can be zero if this
800  /// action joins two actions together.
801  FoldUDivOperandCb FoldAction;
802 
803  /// Which operand to fold.
804  Value *OperandToFold;
805 
806  union {
807  /// The instruction returned when FoldAction is invoked.
808  Instruction *FoldResult;
809 
810  /// Stores the LHS action index if this action joins two actions together.
811  size_t SelectLHSIdx;
812  };
813 
814  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
815  : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
816  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
817  : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
818 };
819 
820 } // end anonymous namespace
821 
822 // X udiv 2^C -> X >> C
824  const BinaryOperator &I, InstCombiner &IC) {
825  Constant *C1 = getLogBase2(Op0->getType(), cast<Constant>(Op1));
826  if (!C1)
827  llvm_unreachable("Failed to constant fold udiv -> logbase2");
828  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, C1);
829  if (I.isExact())
830  LShr->setIsExact();
831  return LShr;
832 }
833 
834 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
835 // X udiv (zext (C1 << N)), where C1 is "1<<C2" --> X >> (N+C2)
836 static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
837  InstCombiner &IC) {
838  Value *ShiftLeft;
839  if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
840  ShiftLeft = Op1;
841 
842  Constant *CI;
843  Value *N;
844  if (!match(ShiftLeft, m_Shl(m_Constant(CI), m_Value(N))))
845  llvm_unreachable("match should never fail here!");
846  Constant *Log2Base = getLogBase2(N->getType(), CI);
847  if (!Log2Base)
848  llvm_unreachable("getLogBase2 should never fail here!");
849  N = IC.Builder.CreateAdd(N, Log2Base);
850  if (Op1 != ShiftLeft)
851  N = IC.Builder.CreateZExt(N, Op1->getType());
852  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
853  if (I.isExact())
854  LShr->setIsExact();
855  return LShr;
856 }
857 
858 // Recursively visits the possible right hand operands of a udiv
859 // instruction, seeing through select instructions, to determine if we can
860 // replace the udiv with something simpler. If we find that an operand is not
861 // able to simplify the udiv, we abort the entire transformation.
862 static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
864  unsigned Depth = 0) {
865  // Check to see if this is an unsigned division with an exact power of 2,
866  // if so, convert to a right shift.
867  if (match(Op1, m_Power2())) {
868  Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1));
869  return Actions.size();
870  }
871 
872  // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
873  if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
874  match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
875  Actions.push_back(UDivFoldAction(foldUDivShl, Op1));
876  return Actions.size();
877  }
878 
879  // The remaining tests are all recursive, so bail out if we hit the limit.
880  if (Depth++ == MaxDepth)
881  return 0;
882 
883  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
884  if (size_t LHSIdx =
885  visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth))
886  if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) {
887  Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1));
888  return Actions.size();
889  }
890 
891  return 0;
892 }
893 
894 /// If we have zero-extended operands of an unsigned div or rem, we may be able
895 /// to narrow the operation (sink the zext below the math).
897  InstCombiner::BuilderTy &Builder) {
898  Instruction::BinaryOps Opcode = I.getOpcode();
899  Value *N = I.getOperand(0);
900  Value *D = I.getOperand(1);
901  Type *Ty = I.getType();
902  Value *X, *Y;
903  if (match(N, m_ZExt(m_Value(X))) && match(D, m_ZExt(m_Value(Y))) &&
904  X->getType() == Y->getType() && (N->hasOneUse() || D->hasOneUse())) {
905  // udiv (zext X), (zext Y) --> zext (udiv X, Y)
906  // urem (zext X), (zext Y) --> zext (urem X, Y)
907  Value *NarrowOp = Builder.CreateBinOp(Opcode, X, Y);
908  return new ZExtInst(NarrowOp, Ty);
909  }
910 
911  Constant *C;
912  if ((match(N, m_OneUse(m_ZExt(m_Value(X)))) && match(D, m_Constant(C))) ||
913  (match(D, m_OneUse(m_ZExt(m_Value(X)))) && match(N, m_Constant(C)))) {
914  // If the constant is the same in the smaller type, use the narrow version.
915  Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
916  if (ConstantExpr::getZExt(TruncC, Ty) != C)
917  return nullptr;
918 
919  // udiv (zext X), C --> zext (udiv X, C')
920  // urem (zext X), C --> zext (urem X, C')
921  // udiv C, (zext X) --> zext (udiv C', X)
922  // urem C, (zext X) --> zext (urem C', X)
923  Value *NarrowOp = isa<Constant>(D) ? Builder.CreateBinOp(Opcode, X, TruncC)
924  : Builder.CreateBinOp(Opcode, TruncC, X);
925  return new ZExtInst(NarrowOp, Ty);
926  }
927 
928  return nullptr;
929 }
930 
932  if (Value *V = SimplifyUDivInst(I.getOperand(0), I.getOperand(1),
933  SQ.getWithInstruction(&I)))
934  return replaceInstUsesWith(I, V);
935 
936  if (Instruction *X = foldShuffledBinop(I))
937  return X;
938 
939  // Handle the integer div common cases
940  if (Instruction *Common = commonIDivTransforms(I))
941  return Common;
942 
943  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
944  Value *X;
945  const APInt *C1, *C2;
946  if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && match(Op1, m_APInt(C2))) {
947  // (X lshr C1) udiv C2 --> X udiv (C2 << C1)
948  bool Overflow;
949  APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
950  if (!Overflow) {
951  bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value()));
952  BinaryOperator *BO = BinaryOperator::CreateUDiv(
953  X, ConstantInt::get(X->getType(), C2ShlC1));
954  if (IsExact)
955  BO->setIsExact();
956  return BO;
957  }
958  }
959 
960  // Op0 / C where C is large (negative) --> zext (Op0 >= C)
961  // TODO: Could use isKnownNegative() to handle non-constant values.
962  Type *Ty = I.getType();
963  if (match(Op1, m_Negative())) {
964  Value *Cmp = Builder.CreateICmpUGE(Op0, Op1);
965  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
966  }
967  // Op0 / (sext i1 X) --> zext (Op0 == -1) (if X is 0, the div is undefined)
968  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
969  Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
970  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
971  }
972 
973  if (Instruction *NarrowDiv = narrowUDivURem(I, Builder))
974  return NarrowDiv;
975 
976  // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
977  SmallVector<UDivFoldAction, 6> UDivActions;
978  if (visitUDivOperand(Op0, Op1, I, UDivActions))
979  for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) {
980  FoldUDivOperandCb Action = UDivActions[i].FoldAction;
981  Value *ActionOp1 = UDivActions[i].OperandToFold;
982  Instruction *Inst;
983  if (Action)
984  Inst = Action(Op0, ActionOp1, I, *this);
985  else {
986  // This action joins two actions together. The RHS of this action is
987  // simply the last action we processed, we saved the LHS action index in
988  // the joining action.
989  size_t SelectRHSIdx = i - 1;
990  Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult;
991  size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx;
992  Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult;
993  Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
994  SelectLHS, SelectRHS);
995  }
996 
997  // If this is the last action to process, return it to the InstCombiner.
998  // Otherwise, we insert it before the UDiv and record it so that we may
999  // use it as part of a joining action (i.e., a SelectInst).
1000  if (e - i != 1) {
1001  Inst->insertBefore(&I);
1002  UDivActions[i].FoldResult = Inst;
1003  } else
1004  return Inst;
1005  }
1006 
1007  return nullptr;
1008 }
1009 
1011  if (Value *V = SimplifySDivInst(I.getOperand(0), I.getOperand(1),
1012  SQ.getWithInstruction(&I)))
1013  return replaceInstUsesWith(I, V);
1014 
1015  if (Instruction *X = foldShuffledBinop(I))
1016  return X;
1017 
1018  // Handle the integer div common cases
1019  if (Instruction *Common = commonIDivTransforms(I))
1020  return Common;
1021 
1022  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1023  Value *X;
1024  // sdiv Op0, -1 --> -Op0
1025  // sdiv Op0, (sext i1 X) --> -Op0 (because if X is 0, the op is undefined)
1026  if (match(Op1, m_AllOnes()) ||
1027  (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1028  return BinaryOperator::CreateNeg(Op0);
1029 
1030  const APInt *Op1C;
1031  if (match(Op1, m_APInt(Op1C))) {
1032  // sdiv exact X, C --> ashr exact X, log2(C)
1033  if (I.isExact() && Op1C->isNonNegative() && Op1C->isPowerOf2()) {
1034  Value *ShAmt = ConstantInt::get(Op1->getType(), Op1C->exactLogBase2());
1035  return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName());
1036  }
1037 
1038  // If the dividend is sign-extended and the constant divisor is small enough
1039  // to fit in the source type, shrink the division to the narrower type:
1040  // (sext X) sdiv C --> sext (X sdiv C)
1041  Value *Op0Src;
1042  if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
1043  Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) {
1044 
1045  // In the general case, we need to make sure that the dividend is not the
1046  // minimum signed value because dividing that by -1 is UB. But here, we
1047  // know that the -1 divisor case is already handled above.
1048 
1049  Constant *NarrowDivisor =
1050  ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
1051  Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
1052  return new SExtInst(NarrowOp, Op0->getType());
1053  }
1054  }
1055 
1056  if (Constant *RHS = dyn_cast<Constant>(Op1)) {
1057  // X/INT_MIN -> X == INT_MIN
1058  if (RHS->isMinSignedValue())
1059  return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), I.getType());
1060 
1061  // -X/C --> X/-C provided the negation doesn't overflow.
1062  Value *X;
1063  if (match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1064  auto *BO = BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(RHS));
1065  BO->setIsExact(I.isExact());
1066  return BO;
1067  }
1068  }
1069 
1070  // If the sign bits of both operands are zero (i.e. we can prove they are
1071  // unsigned inputs), turn this into a udiv.
1073  if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
1074  if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
1075  // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
1076  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1077  BO->setIsExact(I.isExact());
1078  return BO;
1079  }
1080 
1081  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1082  // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1083  // Safe because the only negative value (1 << Y) can take on is
1084  // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1085  // the sign bit set.
1086  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1087  BO->setIsExact(I.isExact());
1088  return BO;
1089  }
1090  }
1091 
1092  return nullptr;
1093 }
1094 
1095 /// Remove negation and try to convert division into multiplication.
1097  Constant *C;
1098  if (!match(I.getOperand(1), m_Constant(C)))
1099  return nullptr;
1100 
1101  // -X / C --> X / -C
1102  Value *X;
1103  if (match(I.getOperand(0), m_FNeg(m_Value(X))))
1105 
1106  // If the constant divisor has an exact inverse, this is always safe. If not,
1107  // then we can still create a reciprocal if fast-math-flags allow it and the
1108  // constant is a regular number (not zero, infinite, or denormal).
1109  if (!(C->hasExactInverseFP() || (I.hasAllowReciprocal() && C->isNormalFP())))
1110  return nullptr;
1111 
1112  // Disallow denormal constants because we don't know what would happen
1113  // on all targets.
1114  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1115  // denorms are flushed?
1116  auto *RecipC = ConstantExpr::getFDiv(ConstantFP::get(I.getType(), 1.0), C);
1117  if (!RecipC->isNormalFP())
1118  return nullptr;
1119 
1120  // X / C --> X * (1 / C)
1121  return BinaryOperator::CreateFMulFMF(I.getOperand(0), RecipC, &I);
1122 }
1123 
1124 /// Remove negation and try to reassociate constant math.
1126  Constant *C;
1127  if (!match(I.getOperand(0), m_Constant(C)))
1128  return nullptr;
1129 
1130  // C / -X --> -C / X
1131  Value *X;
1132  if (match(I.getOperand(1), m_FNeg(m_Value(X))))
1134 
1135  if (!I.hasAllowReassoc() || !I.hasAllowReciprocal())
1136  return nullptr;
1137 
1138  // Try to reassociate C / X expressions where X includes another constant.
1139  Constant *C2, *NewC = nullptr;
1140  if (match(I.getOperand(1), m_FMul(m_Value(X), m_Constant(C2)))) {
1141  // C / (X * C2) --> (C / C2) / X
1142  NewC = ConstantExpr::getFDiv(C, C2);
1143  } else if (match(I.getOperand(1), m_FDiv(m_Value(X), m_Constant(C2)))) {
1144  // C / (X / C2) --> (C * C2) / X
1145  NewC = ConstantExpr::getFMul(C, C2);
1146  }
1147  // Disallow denormal constants because we don't know what would happen
1148  // on all targets.
1149  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1150  // denorms are flushed?
1151  if (!NewC || !NewC->isNormalFP())
1152  return nullptr;
1153 
1154  return BinaryOperator::CreateFDivFMF(NewC, X, &I);
1155 }
1156 
1158  if (Value *V = SimplifyFDivInst(I.getOperand(0), I.getOperand(1),
1159  I.getFastMathFlags(),
1160  SQ.getWithInstruction(&I)))
1161  return replaceInstUsesWith(I, V);
1162 
1163  if (Instruction *X = foldShuffledBinop(I))
1164  return X;
1165 
1167  return R;
1168 
1170  return R;
1171 
1172  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1173  if (isa<Constant>(Op0))
1174  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1175  if (Instruction *R = FoldOpIntoSelect(I, SI))
1176  return R;
1177 
1178  if (isa<Constant>(Op1))
1179  if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1180  if (Instruction *R = FoldOpIntoSelect(I, SI))
1181  return R;
1182 
1183  if (I.hasAllowReassoc() && I.hasAllowReciprocal()) {
1184  Value *X, *Y;
1185  if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1186  (!isa<Constant>(Y) || !isa<Constant>(Op1))) {
1187  // (X / Y) / Z => X / (Y * Z)
1188  Value *YZ = Builder.CreateFMulFMF(Y, Op1, &I);
1189  return BinaryOperator::CreateFDivFMF(X, YZ, &I);
1190  }
1191  if (match(Op1, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1192  (!isa<Constant>(Y) || !isa<Constant>(Op0))) {
1193  // Z / (X / Y) => (Y * Z) / X
1194  Value *YZ = Builder.CreateFMulFMF(Y, Op0, &I);
1195  return BinaryOperator::CreateFDivFMF(YZ, X, &I);
1196  }
1197  }
1198 
1199  if (I.hasAllowReassoc() && Op0->hasOneUse() && Op1->hasOneUse()) {
1200  // sin(X) / cos(X) -> tan(X)
1201  // cos(X) / sin(X) -> 1/tan(X) (cotangent)
1202  Value *X;
1203  bool IsTan = match(Op0, m_Intrinsic<Intrinsic::sin>(m_Value(X))) &&
1204  match(Op1, m_Intrinsic<Intrinsic::cos>(m_Specific(X)));
1205  bool IsCot =
1206  !IsTan && match(Op0, m_Intrinsic<Intrinsic::cos>(m_Value(X))) &&
1207  match(Op1, m_Intrinsic<Intrinsic::sin>(m_Specific(X)));
1208 
1209  if ((IsTan || IsCot) && hasUnaryFloatFn(&TLI, I.getType(), LibFunc_tan,
1210  LibFunc_tanf, LibFunc_tanl)) {
1211  IRBuilder<> B(&I);
1212  IRBuilder<>::FastMathFlagGuard FMFGuard(B);
1215  Value *Res = emitUnaryFloatFnCall(X, TLI.getName(LibFunc_tan), B, Attrs);
1216  if (IsCot)
1217  Res = B.CreateFDiv(ConstantFP::get(I.getType(), 1.0), Res);
1218  return replaceInstUsesWith(I, Res);
1219  }
1220  }
1221 
1222  // -X / -Y -> X / Y
1223  Value *X, *Y;
1224  if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y)))) {
1225  I.setOperand(0, X);
1226  I.setOperand(1, Y);
1227  return &I;
1228  }
1229 
1230  // X / (X * Y) --> 1.0 / Y
1231  // Reassociate to (X / X -> 1.0) is legal when NaNs are not allowed.
1232  // We can ignore the possibility that X is infinity because INF/INF is NaN.
1233  if (I.hasNoNaNs() && I.hasAllowReassoc() &&
1234  match(Op1, m_c_FMul(m_Specific(Op0), m_Value(Y)))) {
1235  I.setOperand(0, ConstantFP::get(I.getType(), 1.0));
1236  I.setOperand(1, Y);
1237  return &I;
1238  }
1239 
1240  return nullptr;
1241 }
1242 
1243 /// This function implements the transforms common to both integer remainder
1244 /// instructions (urem and srem). It is called by the visitors to those integer
1245 /// remainder instructions.
1246 /// Common integer remainder transforms
1248  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1249 
1250  // The RHS is known non-zero.
1251  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
1252  I.setOperand(1, V);
1253  return &I;
1254  }
1255 
1256  // Handle cases involving: rem X, (select Cond, Y, Z)
1257  if (simplifyDivRemOfSelectWithZeroOp(I))
1258  return &I;
1259 
1260  if (isa<Constant>(Op1)) {
1261  if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1262  if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1263  if (Instruction *R = FoldOpIntoSelect(I, SI))
1264  return R;
1265  } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
1266  const APInt *Op1Int;
1267  if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
1268  (I.getOpcode() == Instruction::URem ||
1269  !Op1Int->isMinSignedValue())) {
1270  // foldOpIntoPhi will speculate instructions to the end of the PHI's
1271  // predecessor blocks, so do this only if we know the srem or urem
1272  // will not fault.
1273  if (Instruction *NV = foldOpIntoPhi(I, PN))
1274  return NV;
1275  }
1276  }
1277 
1278  // See if we can fold away this rem instruction.
1279  if (SimplifyDemandedInstructionBits(I))
1280  return &I;
1281  }
1282  }
1283 
1284  return nullptr;
1285 }
1286 
1288  if (Value *V = SimplifyURemInst(I.getOperand(0), I.getOperand(1),
1289  SQ.getWithInstruction(&I)))
1290  return replaceInstUsesWith(I, V);
1291 
1292  if (Instruction *X = foldShuffledBinop(I))
1293  return X;
1294 
1295  if (Instruction *common = commonIRemTransforms(I))
1296  return common;
1297 
1298  if (Instruction *NarrowRem = narrowUDivURem(I, Builder))
1299  return NarrowRem;
1300 
1301  // X urem Y -> X and Y-1, where Y is a power of 2,
1302  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1303  Type *Ty = I.getType();
1304  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1306  Value *Add = Builder.CreateAdd(Op1, N1);
1307  return BinaryOperator::CreateAnd(Op0, Add);
1308  }
1309 
1310  // 1 urem X -> zext(X != 1)
1311  if (match(Op0, m_One()))
1312  return CastInst::CreateZExtOrBitCast(Builder.CreateICmpNE(Op1, Op0), Ty);
1313 
1314  // X urem C -> X < C ? X : X - C, where C >= signbit.
1315  if (match(Op1, m_Negative())) {
1316  Value *Cmp = Builder.CreateICmpULT(Op0, Op1);
1317  Value *Sub = Builder.CreateSub(Op0, Op1);
1318  return SelectInst::Create(Cmp, Op0, Sub);
1319  }
1320 
1321  // If the divisor is a sext of a boolean, then the divisor must be max
1322  // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also
1323  // max unsigned value. In that case, the remainder is 0:
1324  // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0
1325  Value *X;
1326  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1327  Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1328  return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), Op0);
1329  }
1330 
1331  return nullptr;
1332 }
1333 
1335  if (Value *V = SimplifySRemInst(I.getOperand(0), I.getOperand(1),
1336  SQ.getWithInstruction(&I)))
1337  return replaceInstUsesWith(I, V);
1338 
1339  if (Instruction *X = foldShuffledBinop(I))
1340  return X;
1341 
1342  // Handle the integer rem common cases
1343  if (Instruction *Common = commonIRemTransforms(I))
1344  return Common;
1345 
1346  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1347  {
1348  const APInt *Y;
1349  // X % -Y -> X % Y
1350  if (match(Op1, m_Negative(Y)) && !Y->isMinSignedValue()) {
1351  Worklist.AddValue(I.getOperand(1));
1352  I.setOperand(1, ConstantInt::get(I.getType(), -*Y));
1353  return &I;
1354  }
1355  }
1356 
1357  // If the sign bits of both operands are zero (i.e. we can prove they are
1358  // unsigned inputs), turn this into a urem.
1360  if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1361  MaskedValueIsZero(Op0, Mask, 0, &I)) {
1362  // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1363  return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1364  }
1365 
1366  // If it's a constant vector, flip any negative values positive.
1367  if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1368  Constant *C = cast<Constant>(Op1);
1369  unsigned VWidth = C->getType()->getVectorNumElements();
1370 
1371  bool hasNegative = false;
1372  bool hasMissing = false;
1373  for (unsigned i = 0; i != VWidth; ++i) {
1374  Constant *Elt = C->getAggregateElement(i);
1375  if (!Elt) {
1376  hasMissing = true;
1377  break;
1378  }
1379 
1380  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1381  if (RHS->isNegative())
1382  hasNegative = true;
1383  }
1384 
1385  if (hasNegative && !hasMissing) {
1386  SmallVector<Constant *, 16> Elts(VWidth);
1387  for (unsigned i = 0; i != VWidth; ++i) {
1388  Elts[i] = C->getAggregateElement(i); // Handle undef, etc.
1389  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1390  if (RHS->isNegative())
1391  Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1392  }
1393  }
1394 
1395  Constant *NewRHSV = ConstantVector::get(Elts);
1396  if (NewRHSV != C) { // Don't loop on -MININT
1397  Worklist.AddValue(I.getOperand(1));
1398  I.setOperand(1, NewRHSV);
1399  return &I;
1400  }
1401  }
1402  }
1403 
1404  return nullptr;
1405 }
1406 
1408  if (Value *V = SimplifyFRemInst(I.getOperand(0), I.getOperand(1),
1409  I.getFastMathFlags(),
1410  SQ.getWithInstruction(&I)))
1411  return replaceInstUsesWith(I, V);
1412 
1413  if (Instruction *X = foldShuffledBinop(I))
1414  return X;
1415 
1416  return nullptr;
1417 }
APInt abs() const
Get the absolute value;.
Definition: APInt.h:1793
static BinaryOperator * CreateFMulFMF(Value *V1, Value *V2, BinaryOperator *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:405
static Instruction * foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I, InstCombiner &IC)
uint64_t CallInst * C
Instruction * visitSDiv(BinaryOperator &I)
BinaryOp_match< cstfp_pred_ty< is_neg_zero_fp >, RHS, Instruction::FSub > m_FNeg(const RHS &X)
Match &#39;fneg X&#39; as &#39;fsub -0.0, X&#39;.
Definition: PatternMatch.h:665
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:789
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:584
void copyFastMathFlags(FastMathFlags FMF)
Convenience function for transferring all fast-math flag values to this instruction, which must be an operator which supports these flags.
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)
Return true if the given value is known to have exactly one bit set when defined. ...
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1246
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:651
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:373
DiagnosticInfoOptimizationBase::Argument NV
bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I)
Fold a divide or remainder with a select instruction divisor when one of the select operands is zero...
static Value * simplifyValueKnownNonZero(Value *V, InstCombiner &IC, Instruction &CxtI)
The specific integer value is used in a context where it is known to be non-zero. ...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:555
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:645
BinaryOp_match< LHS, RHS, Instruction::FDiv > m_FDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:694
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:706
This class represents zero extension of integer types.
Instruction * visitFRem(BinaryOperator &I)
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:670
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:91
const Value * getTrueValue() const
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition: APInt.cpp:1847
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Value * SimplifySDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an SDiv, fold the result or return null.
Value * SimplifyUDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a UDiv, fold the result or return null.
APInt ushl_ov(const APInt &Amt, bool &Overflow) const
Definition: APInt.cpp:1950
This class represents a sign extension of integer types.
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:657
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:230
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
static BinaryOperator * CreateFSubFMF(Value *V1, Value *V2, BinaryOperator *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:400
static Instruction * foldFDivConstantDivisor(BinaryOperator &I)
Remove negation and try to convert division into multiplication.
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.
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1502
Instruction * visitFMul(BinaryOperator &I)
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:268
Instruction * visitFDiv(BinaryOperator &I)
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
Instruction * visitMul(BinaryOperator &I)
static Constant * getFMul(Constant *C1, Constant *C2)
Definition: Constants.cpp:2215
Instruction * commonIRemTransforms(BinaryOperator &I)
This function implements the transforms common to both integer remainder instructions (urem and srem)...
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
specific_fpval m_SpecificFP(double V)
Match a specific floating point value or vector with all elements equal to the value.
Definition: PatternMatch.h:537
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
This class represents the LLVM &#39;select&#39; instruction.
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:368
Exact_match< T > m_Exact(const T &SubPattern)
Definition: PatternMatch.h:943
bool hasAllowReciprocal() const
Determine whether the allow-reciprocal flag is set.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:731
The core instruction combiner logic.
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.
static Constant * getLogBase2(Type *Ty, Constant *C)
A helper routine of InstCombiner::visitMul().
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1628
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:962
Value * emitUnaryFloatFnCall(Value *Op, StringRef Name, IRBuilder<> &B, const AttributeList &Attrs)
Emit a call to the unary function named &#39;Name&#39; (e.g.
Instruction * commonIDivTransforms(BinaryOperator &I)
This function implements the transforms common to both integer division instructions (udiv and sdiv)...
This file implements a class to represent arbitrary precision integral constant values and operations...
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:639
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1642
Instruction * visitSRem(BinaryOperator &I)
static BinaryOperator * CreateFAddFMF(Value *V1, Value *V2, BinaryOperator *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:395
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag...
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
int32_t exactLogBase2() const
Definition: APInt.h:1781
Value * SimplifyMulInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a Mul, fold the result or return null.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
bool isFiniteNonZeroFP() const
Return true if this is a finite and non-zero floating-point scalar constant or a vector constant with...
Definition: Constants.cpp:205
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:979
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:210
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:203
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:382
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1556
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:830
static Constant * getFDiv(Constant *C1, Constant *C2)
Definition: Constants.cpp:2229
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Value * getOperand(unsigned i) const
Definition: User.h:170
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:338
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return &#39;this&#39;.
Definition: Type.h:304
Instruction * visitUDiv(BinaryOperator &I)
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:63
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:363
static Constant * getFNeg(Constant *C)
Definition: Constants.cpp:2174
bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:742
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:395
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:177
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:688
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:838
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:74
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
Value * SimplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a URem, fold the result or return null.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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)
Return true if &#39;V & Mask&#39; is known to be zero.
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:306
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:587
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:499
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:442
This file declares a class to represent arbitrary precision floating point values and provide a varie...
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:736
bool isFast() const
Determine whether all fast-math-flags are set.
Value * SimplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FDiv, fold the result or return null.
void setArgOperand(unsigned i, Value *v)
self_iterator getIterator()
Definition: ilist_node.h:82
static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I, SmallVectorImpl< UDivFoldAction > &Actions, unsigned Depth=0)
const Value * getCondition() const
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:322
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...
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1392
size_t size() const
Definition: SmallVector.h:53
static CastInst * CreateZExtOrBitCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a ZExt or BitCast cast instruction.
bool isExact() const
Determine whether the exact flag is set.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Value * SimplifyFRemInst(Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FRem, fold the result or return null.
bool isNormalFP() const
Return true if this is a normal (as opposed to denormal) floating-point scalar constant or a vector c...
Definition: Constants.cpp:218
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:554
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag...
cst_pred_ty< is_negative > m_Negative()
Match an integer or vector of negative values.
Definition: PatternMatch.h:328
Iterator for intrusive lists based on ilist_node.
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:130
double Log2(double Value)
Return the log base 2 of the specified value.
Definition: MathExtras.h:528
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:700
BinaryOp_match< LHS, RHS, Instruction::UDiv > m_UDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:682
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1614
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:621
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.
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:684
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:676
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:577
static BinaryOperator * CreateFDivFMF(Value *V1, Value *V2, BinaryOperator *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:410
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
unsigned logBase2() const
Definition: APInt.h:1741
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a &#39;Neg&#39; as &#39;sub 0, V&#39;.
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:462
Class for arbitrary precision integers.
Definition: APInt.h:69
bool isPowerOf2() const
Check if this APInt&#39;s value is a power of two greater than zero.
Definition: APInt.h:463
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.
static Instruction * foldUDivPow2Cst(Value *Op0, Value *Op1, const BinaryOperator &I, InstCombiner &IC)
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1051
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.
const Value * getFalseValue() const
Value * SimplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FMul, fold the result or return null.
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2167
Instruction * visitURem(BinaryOperator &I)
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value...
Definition: APInt.h:481
static Instruction * foldFDivConstantDividend(BinaryOperator &I)
Remove negation and try to reassociate constant math.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
APInt smul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1917
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:805
static BinaryOperator * CreateFNegFMF(Value *Op, BinaryOperator *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:420
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2257
bool isLogicalShift() const
Return true if this is a logical shift left or a logical shift right.
Definition: Instruction.h:156
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:436
Value * CreateFDiv(Value *L, Value *R, const Twine &Name="", MDNode *FPMD=nullptr)
Definition: IRBuilder.h:1212
Value * SimplifySRemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an SRem, fold the result or return null.
APInt umul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1927
FunTy * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it&#39;s an indirect...
Definition: CallSite.h:107
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getMinSignedBits() const
Get the minimum bit size for this signed APInt.
Definition: APInt.h:1545
LLVM Value Representation.
Definition: Value.h:73
static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Dual division/remainder interface.
Definition: APInt.cpp:1715
This file provides internal interfaces used to implement the InstCombine.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:797
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:352
bool hasAllowReassoc() const
Determine whether the allow-reassociation flag is set.
bool hasExactInverseFP() const
Return true if this scalar has an exact multiplicative inverse or this vector has an exact multiplica...
Definition: Constants.cpp:231
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
void setFastMathFlags(FastMathFlags NewFMF)
Set the fast-math flags to be used with generated fp-math operators.
Definition: IRBuilder.h:220
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 (...
bool isNotMinSignedValue() const
Return true if the value is not the smallest signed value.
Definition: Constants.cpp:178
bool hasNoNaNs() const
Determine whether the no-NaNs flag is set.
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:412
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
bool hasUnaryFloatFn(const TargetLibraryInfo *TLI, Type *Ty, LibFunc DoubleFn, LibFunc FloatFn, LibFunc LongDoubleFn)
Check whether the overloaded unary floating point function corresponding to Ty is available...
bool use_empty() const
Definition: Value.h:322
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1056
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:405
static const unsigned MaxDepth
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:67