LLVM  6.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"
17 #include "llvm/IR/IntrinsicInst.h"
18 #include "llvm/IR/PatternMatch.h"
19 using namespace llvm;
20 using namespace PatternMatch;
21 
22 #define DEBUG_TYPE "instcombine"
23 
24 
25 /// The specific integer value is used in a context where it is known to be
26 /// non-zero. If this allows us to simplify the computation, do so and return
27 /// the new operand, otherwise return null.
29  Instruction &CxtI) {
30  // If V has multiple uses, then we would have to do more analysis to determine
31  // if this is safe. For example, the use could be in dynamically unreached
32  // code.
33  if (!V->hasOneUse()) return nullptr;
34 
35  bool MadeChange = false;
36 
37  // ((1 << A) >>u B) --> (1 << (A-B))
38  // Because V cannot be zero, we know that B is less than A.
39  Value *A = nullptr, *B = nullptr, *One = nullptr;
40  if (match(V, m_LShr(m_OneUse(m_Shl(m_Value(One), m_Value(A))), m_Value(B))) &&
41  match(One, m_One())) {
42  A = IC.Builder.CreateSub(A, B);
43  return IC.Builder.CreateShl(One, A);
44  }
45 
46  // (PowerOfTwo >>u B) --> isExact since shifting out the result would make it
47  // inexact. Similarly for <<.
49  if (I && I->isLogicalShift() &&
50  IC.isKnownToBeAPowerOfTwo(I->getOperand(0), false, 0, &CxtI)) {
51  // We know that this is an exact/nuw shift and that the input is a
52  // non-zero context as well.
53  if (Value *V2 = simplifyValueKnownNonZero(I->getOperand(0), IC, CxtI)) {
54  I->setOperand(0, V2);
55  MadeChange = true;
56  }
57 
58  if (I->getOpcode() == Instruction::LShr && !I->isExact()) {
59  I->setIsExact();
60  MadeChange = true;
61  }
62 
63  if (I->getOpcode() == Instruction::Shl && !I->hasNoUnsignedWrap()) {
65  MadeChange = true;
66  }
67  }
68 
69  // TODO: Lots more we could do here:
70  // If V is a phi node, we can call this on each of its operands.
71  // "select cond, X, 0" can simplify to "X".
72 
73  return MadeChange ? V : nullptr;
74 }
75 
76 
77 /// True if the multiply can not be expressed in an int this size.
78 static bool MultiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
79  bool IsSigned) {
80  bool Overflow;
81  if (IsSigned)
82  Product = C1.smul_ov(C2, Overflow);
83  else
84  Product = C1.umul_ov(C2, Overflow);
85 
86  return Overflow;
87 }
88 
89 /// \brief True if C2 is a multiple of C1. Quotient contains C2/C1.
90 static bool IsMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
91  bool IsSigned) {
92  assert(C1.getBitWidth() == C2.getBitWidth() &&
93  "Inconsistent width of constants!");
94 
95  // Bail if we will divide by zero.
96  if (C2.isMinValue())
97  return false;
98 
99  // Bail if we would divide INT_MIN by -1.
100  if (IsSigned && C1.isMinSignedValue() && C2.isAllOnesValue())
101  return false;
102 
103  APInt Remainder(C1.getBitWidth(), /*Val=*/0ULL, IsSigned);
104  if (IsSigned)
105  APInt::sdivrem(C1, C2, Quotient, Remainder);
106  else
107  APInt::udivrem(C1, C2, Quotient, Remainder);
108 
109  return Remainder.isMinValue();
110 }
111 
112 /// \brief A helper routine of InstCombiner::visitMul().
113 ///
114 /// If C is a vector of known powers of 2, then this function returns
115 /// a new vector obtained from C replacing each element with its logBase2.
116 /// Return a null pointer otherwise.
118  const APInt *IVal;
120 
121  for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) {
122  Constant *Elt = CV->getElementAsConstant(I);
123  if (!match(Elt, m_APInt(IVal)) || !IVal->isPowerOf2())
124  return nullptr;
125  Elts.push_back(ConstantInt::get(Elt->getType(), IVal->logBase2()));
126  }
127 
128  return ConstantVector::get(Elts);
129 }
130 
131 /// \brief Return true if we can prove that:
132 /// (mul LHS, RHS) === (mul nsw LHS, RHS)
133 bool InstCombiner::willNotOverflowSignedMul(const Value *LHS,
134  const Value *RHS,
135  const Instruction &CxtI) const {
136  // Multiplying n * m significant bits yields a result of n + m significant
137  // bits. If the total number of significant bits does not exceed the
138  // result bit width (minus 1), there is no overflow.
139  // This means if we have enough leading sign bits in the operands
140  // we can guarantee that the result does not overflow.
141  // Ref: "Hacker's Delight" by Henry Warren
142  unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
143 
144  // Note that underestimating the number of sign bits gives a more
145  // conservative answer.
146  unsigned SignBits =
147  ComputeNumSignBits(LHS, 0, &CxtI) + ComputeNumSignBits(RHS, 0, &CxtI);
148 
149  // First handle the easy case: if we have enough sign bits there's
150  // definitely no overflow.
151  if (SignBits > BitWidth + 1)
152  return true;
153 
154  // There are two ambiguous cases where there can be no overflow:
155  // SignBits == BitWidth + 1 and
156  // SignBits == BitWidth
157  // The second case is difficult to check, therefore we only handle the
158  // first case.
159  if (SignBits == BitWidth + 1) {
160  // It overflows only when both arguments are negative and the true
161  // product is exactly the minimum negative number.
162  // E.g. mul i16 with 17 sign bits: 0xff00 * 0xff80 = 0x8000
163  // For simplicity we just check if at least one side is not negative.
164  KnownBits LHSKnown = computeKnownBits(LHS, /*Depth=*/0, &CxtI);
165  KnownBits RHSKnown = computeKnownBits(RHS, /*Depth=*/0, &CxtI);
166  if (LHSKnown.isNonNegative() || RHSKnown.isNonNegative())
167  return true;
168  }
169  return false;
170 }
171 
173  bool Changed = SimplifyAssociativeOrCommutative(I);
174  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
175 
176  if (Value *V = SimplifyVectorOp(I))
177  return replaceInstUsesWith(I, V);
178 
179  if (Value *V = SimplifyMulInst(Op0, Op1, SQ.getWithInstruction(&I)))
180  return replaceInstUsesWith(I, V);
181 
182  if (Value *V = SimplifyUsingDistributiveLaws(I))
183  return replaceInstUsesWith(I, V);
184 
185  // X * -1 == 0 - X
186  if (match(Op1, m_AllOnes())) {
188  if (I.hasNoSignedWrap())
189  BO->setHasNoSignedWrap();
190  return BO;
191  }
192 
193  // Also allow combining multiply instructions on vectors.
194  {
195  Value *NewOp;
196  Constant *C1, *C2;
197  const APInt *IVal;
198  if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
199  m_Constant(C1))) &&
200  match(C1, m_APInt(IVal))) {
201  // ((X << C2)*C1) == (X * (C1 << C2))
202  Constant *Shl = ConstantExpr::getShl(C1, C2);
203  BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0));
204  BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl);
205  if (I.hasNoUnsignedWrap() && Mul->hasNoUnsignedWrap())
206  BO->setHasNoUnsignedWrap();
207  if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap() &&
208  Shl->isNotMinSignedValue())
209  BO->setHasNoSignedWrap();
210  return BO;
211  }
212 
213  if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
214  Constant *NewCst = nullptr;
215  if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2())
216  // Replace X*(2^C) with X << C, where C is either a scalar or a splat.
217  NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2());
218  else if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(C1))
219  // Replace X*(2^C) with X << C, where C is a vector of known
220  // constant powers of 2.
221  NewCst = getLogBase2Vector(CV);
222 
223  if (NewCst) {
224  unsigned Width = NewCst->getType()->getPrimitiveSizeInBits();
225  BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
226 
227  if (I.hasNoUnsignedWrap())
228  Shl->setHasNoUnsignedWrap();
229  if (I.hasNoSignedWrap()) {
230  const APInt *V;
231  if (match(NewCst, m_APInt(V)) && *V != Width - 1)
232  Shl->setHasNoSignedWrap();
233  }
234 
235  return Shl;
236  }
237  }
238  }
239 
240  if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
241  // (Y - X) * (-(2**n)) -> (X - Y) * (2**n), for positive nonzero n
242  // (Y + const) * (-(2**n)) -> (-constY) * (2**n), for positive nonzero n
243  // The "* (2**n)" thus becomes a potential shifting opportunity.
244  {
245  const APInt & Val = CI->getValue();
246  const APInt &PosVal = Val.abs();
247  if (Val.isNegative() && PosVal.isPowerOf2()) {
248  Value *X = nullptr, *Y = nullptr;
249  if (Op0->hasOneUse()) {
250  ConstantInt *C1;
251  Value *Sub = nullptr;
252  if (match(Op0, m_Sub(m_Value(Y), m_Value(X))))
253  Sub = Builder.CreateSub(X, Y, "suba");
254  else if (match(Op0, m_Add(m_Value(Y), m_ConstantInt(C1))))
255  Sub = Builder.CreateSub(Builder.CreateNeg(C1), Y, "subc");
256  if (Sub)
257  return
259  ConstantInt::get(Y->getType(), PosVal));
260  }
261  }
262  }
263  }
264 
265  // Simplify mul instructions with a constant RHS.
266  if (isa<Constant>(Op1)) {
267  if (Instruction *FoldedMul = foldOpWithConstantIntoOperand(I))
268  return FoldedMul;
269 
270  // Canonicalize (X+C1)*CI -> X*CI+C1*CI.
271  {
272  Value *X;
273  Constant *C1;
274  if (match(Op0, m_OneUse(m_Add(m_Value(X), m_Constant(C1))))) {
275  Value *Mul = Builder.CreateMul(C1, Op1);
276  // Only go forward with the transform if C1*CI simplifies to a tidier
277  // constant.
278  if (!match(Mul, m_Mul(m_Value(), m_Value())))
279  return BinaryOperator::CreateAdd(Builder.CreateMul(X, Op1), Mul);
280  }
281  }
282  }
283 
284  if (Value *Op0v = dyn_castNegVal(Op0)) { // -X * -Y = X*Y
285  if (Value *Op1v = dyn_castNegVal(Op1)) {
286  BinaryOperator *BO = BinaryOperator::CreateMul(Op0v, Op1v);
287  if (I.hasNoSignedWrap() &&
288  match(Op0, m_NSWSub(m_Value(), m_Value())) &&
289  match(Op1, m_NSWSub(m_Value(), m_Value())))
290  BO->setHasNoSignedWrap();
291  return BO;
292  }
293  }
294 
295  // (X / Y) * Y = X - (X % Y)
296  // (X / Y) * -Y = (X % Y) - X
297  {
298  Value *Y = Op1;
300  if (!Div || (Div->getOpcode() != Instruction::UDiv &&
301  Div->getOpcode() != Instruction::SDiv)) {
302  Y = Op0;
303  Div = dyn_cast<BinaryOperator>(Op1);
304  }
305  Value *Neg = dyn_castNegVal(Y);
306  if (Div && Div->hasOneUse() &&
307  (Div->getOperand(1) == Y || Div->getOperand(1) == Neg) &&
308  (Div->getOpcode() == Instruction::UDiv ||
309  Div->getOpcode() == Instruction::SDiv)) {
310  Value *X = Div->getOperand(0), *DivOp1 = Div->getOperand(1);
311 
312  // If the division is exact, X % Y is zero, so we end up with X or -X.
313  if (Div->isExact()) {
314  if (DivOp1 == Y)
315  return replaceInstUsesWith(I, X);
316  return BinaryOperator::CreateNeg(X);
317  }
318 
319  auto RemOpc = Div->getOpcode() == Instruction::UDiv ? Instruction::URem
320  : Instruction::SRem;
321  Value *Rem = Builder.CreateBinOp(RemOpc, X, DivOp1);
322  if (DivOp1 == Y)
323  return BinaryOperator::CreateSub(X, Rem);
324  return BinaryOperator::CreateSub(Rem, X);
325  }
326  }
327 
328  /// i1 mul -> i1 and.
329  if (I.getType()->isIntOrIntVectorTy(1))
330  return BinaryOperator::CreateAnd(Op0, Op1);
331 
332  // X*(1 << Y) --> X << Y
333  // (1 << Y)*X --> X << Y
334  {
335  Value *Y;
336  BinaryOperator *BO = nullptr;
337  bool ShlNSW = false;
338  if (match(Op0, m_Shl(m_One(), m_Value(Y)))) {
339  BO = BinaryOperator::CreateShl(Op1, Y);
340  ShlNSW = cast<ShlOperator>(Op0)->hasNoSignedWrap();
341  } else if (match(Op1, m_Shl(m_One(), m_Value(Y)))) {
342  BO = BinaryOperator::CreateShl(Op0, Y);
343  ShlNSW = cast<ShlOperator>(Op1)->hasNoSignedWrap();
344  }
345  if (BO) {
346  if (I.hasNoUnsignedWrap())
347  BO->setHasNoUnsignedWrap();
348  if (I.hasNoSignedWrap() && ShlNSW)
349  BO->setHasNoSignedWrap();
350  return BO;
351  }
352  }
353 
354  // If one of the operands of the multiply is a cast from a boolean value, then
355  // we know the bool is either zero or one, so this is a 'masking' multiply.
356  // X * Y (where Y is 0 or 1) -> X & (0-Y)
357  if (!I.getType()->isVectorTy()) {
358  // -2 is "-1 << 1" so it is all bits set except the low one.
359  APInt Negative2(I.getType()->getPrimitiveSizeInBits(), (uint64_t)-2, true);
360 
361  Value *BoolCast = nullptr, *OtherOp = nullptr;
362  if (MaskedValueIsZero(Op0, Negative2, 0, &I)) {
363  BoolCast = Op0;
364  OtherOp = Op1;
365  } else if (MaskedValueIsZero(Op1, Negative2, 0, &I)) {
366  BoolCast = Op1;
367  OtherOp = Op0;
368  }
369 
370  if (BoolCast) {
371  Value *V = Builder.CreateSub(Constant::getNullValue(I.getType()),
372  BoolCast);
373  return BinaryOperator::CreateAnd(V, OtherOp);
374  }
375  }
376 
377  // Check for (mul (sext x), y), see if we can merge this into an
378  // integer mul followed by a sext.
379  if (SExtInst *Op0Conv = dyn_cast<SExtInst>(Op0)) {
380  // (mul (sext x), cst) --> (sext (mul x, cst'))
381  if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
382  if (Op0Conv->hasOneUse()) {
383  Constant *CI =
384  ConstantExpr::getTrunc(Op1C, Op0Conv->getOperand(0)->getType());
385  if (ConstantExpr::getSExt(CI, I.getType()) == Op1C &&
386  willNotOverflowSignedMul(Op0Conv->getOperand(0), CI, I)) {
387  // Insert the new, smaller mul.
388  Value *NewMul =
389  Builder.CreateNSWMul(Op0Conv->getOperand(0), CI, "mulconv");
390  return new SExtInst(NewMul, I.getType());
391  }
392  }
393  }
394 
395  // (mul (sext x), (sext y)) --> (sext (mul int x, y))
396  if (SExtInst *Op1Conv = dyn_cast<SExtInst>(Op1)) {
397  // Only do this if x/y have the same type, if at last one of them has a
398  // single use (so we don't increase the number of sexts), and if the
399  // integer mul will not overflow.
400  if (Op0Conv->getOperand(0)->getType() ==
401  Op1Conv->getOperand(0)->getType() &&
402  (Op0Conv->hasOneUse() || Op1Conv->hasOneUse()) &&
403  willNotOverflowSignedMul(Op0Conv->getOperand(0),
404  Op1Conv->getOperand(0), I)) {
405  // Insert the new integer mul.
406  Value *NewMul = Builder.CreateNSWMul(
407  Op0Conv->getOperand(0), Op1Conv->getOperand(0), "mulconv");
408  return new SExtInst(NewMul, I.getType());
409  }
410  }
411  }
412 
413  // Check for (mul (zext x), y), see if we can merge this into an
414  // integer mul followed by a zext.
415  if (auto *Op0Conv = dyn_cast<ZExtInst>(Op0)) {
416  // (mul (zext x), cst) --> (zext (mul x, cst'))
417  if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
418  if (Op0Conv->hasOneUse()) {
419  Constant *CI =
420  ConstantExpr::getTrunc(Op1C, Op0Conv->getOperand(0)->getType());
421  if (ConstantExpr::getZExt(CI, I.getType()) == Op1C &&
422  willNotOverflowUnsignedMul(Op0Conv->getOperand(0), CI, I)) {
423  // Insert the new, smaller mul.
424  Value *NewMul =
425  Builder.CreateNUWMul(Op0Conv->getOperand(0), CI, "mulconv");
426  return new ZExtInst(NewMul, I.getType());
427  }
428  }
429  }
430 
431  // (mul (zext x), (zext y)) --> (zext (mul int x, y))
432  if (auto *Op1Conv = dyn_cast<ZExtInst>(Op1)) {
433  // Only do this if x/y have the same type, if at last one of them has a
434  // single use (so we don't increase the number of zexts), and if the
435  // integer mul will not overflow.
436  if (Op0Conv->getOperand(0)->getType() ==
437  Op1Conv->getOperand(0)->getType() &&
438  (Op0Conv->hasOneUse() || Op1Conv->hasOneUse()) &&
439  willNotOverflowUnsignedMul(Op0Conv->getOperand(0),
440  Op1Conv->getOperand(0), I)) {
441  // Insert the new integer mul.
442  Value *NewMul = Builder.CreateNUWMul(
443  Op0Conv->getOperand(0), Op1Conv->getOperand(0), "mulconv");
444  return new ZExtInst(NewMul, I.getType());
445  }
446  }
447  }
448 
449  if (!I.hasNoSignedWrap() && willNotOverflowSignedMul(Op0, Op1, I)) {
450  Changed = true;
451  I.setHasNoSignedWrap(true);
452  }
453 
454  if (!I.hasNoUnsignedWrap() && willNotOverflowUnsignedMul(Op0, Op1, I)) {
455  Changed = true;
456  I.setHasNoUnsignedWrap(true);
457  }
458 
459  return Changed ? &I : nullptr;
460 }
461 
462 /// Detect pattern log2(Y * 0.5) with corresponding fast math flags.
464  if (!Op->hasOneUse())
465  return;
466 
468  if (!II)
469  return;
470  if (II->getIntrinsicID() != Intrinsic::log2 || !II->hasUnsafeAlgebra())
471  return;
472  Log2 = II;
473 
474  Value *OpLog2Of = II->getArgOperand(0);
475  if (!OpLog2Of->hasOneUse())
476  return;
477 
478  Instruction *I = dyn_cast<Instruction>(OpLog2Of);
479  if (!I)
480  return;
481  if (I->getOpcode() != Instruction::FMul || !I->hasUnsafeAlgebra())
482  return;
483 
484  if (match(I->getOperand(0), m_SpecificFP(0.5)))
485  Y = I->getOperand(1);
486  else if (match(I->getOperand(1), m_SpecificFP(0.5)))
487  Y = I->getOperand(0);
488 }
489 
490 static bool isFiniteNonZeroFp(Constant *C) {
491  if (C->getType()->isVectorTy()) {
492  for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E;
493  ++I) {
494  ConstantFP *CFP = dyn_cast_or_null<ConstantFP>(C->getAggregateElement(I));
495  if (!CFP || !CFP->getValueAPF().isFiniteNonZero())
496  return false;
497  }
498  return true;
499  }
500 
501  return isa<ConstantFP>(C) &&
502  cast<ConstantFP>(C)->getValueAPF().isFiniteNonZero();
503 }
504 
505 static bool isNormalFp(Constant *C) {
506  if (C->getType()->isVectorTy()) {
507  for (unsigned I = 0, E = C->getType()->getVectorNumElements(); I != E;
508  ++I) {
509  ConstantFP *CFP = dyn_cast_or_null<ConstantFP>(C->getAggregateElement(I));
510  if (!CFP || !CFP->getValueAPF().isNormal())
511  return false;
512  }
513  return true;
514  }
515 
516  return isa<ConstantFP>(C) && cast<ConstantFP>(C)->getValueAPF().isNormal();
517 }
518 
519 /// Helper function of InstCombiner::visitFMul(BinaryOperator(). It returns
520 /// true iff the given value is FMul or FDiv with one and only one operand
521 /// being a normal constant (i.e. not Zero/NaN/Infinity).
524  if (!I || (I->getOpcode() != Instruction::FMul &&
525  I->getOpcode() != Instruction::FDiv))
526  return false;
527 
528  Constant *C0 = dyn_cast<Constant>(I->getOperand(0));
529  Constant *C1 = dyn_cast<Constant>(I->getOperand(1));
530 
531  if (C0 && C1)
532  return false;
533 
534  return (C0 && isFiniteNonZeroFp(C0)) || (C1 && isFiniteNonZeroFp(C1));
535 }
536 
537 /// foldFMulConst() is a helper routine of InstCombiner::visitFMul().
538 /// The input \p FMulOrDiv is a FMul/FDiv with one and only one operand
539 /// being a constant (i.e. isFMulOrFDivWithConstant(FMulOrDiv) == true).
540 /// This function is to simplify "FMulOrDiv * C" and returns the
541 /// resulting expression. Note that this function could return NULL in
542 /// case the constants cannot be folded into a normal floating-point.
543 ///
545  Instruction *InsertBefore) {
546  assert(isFMulOrFDivWithConstant(FMulOrDiv) && "V is invalid");
547 
548  Value *Opnd0 = FMulOrDiv->getOperand(0);
549  Value *Opnd1 = FMulOrDiv->getOperand(1);
550 
551  Constant *C0 = dyn_cast<Constant>(Opnd0);
552  Constant *C1 = dyn_cast<Constant>(Opnd1);
553 
554  BinaryOperator *R = nullptr;
555 
556  // (X * C0) * C => X * (C0*C)
557  if (FMulOrDiv->getOpcode() == Instruction::FMul) {
558  Constant *F = ConstantExpr::getFMul(C1 ? C1 : C0, C);
559  if (isNormalFp(F))
560  R = BinaryOperator::CreateFMul(C1 ? Opnd0 : Opnd1, F);
561  } else {
562  if (C0) {
563  // (C0 / X) * C => (C0 * C) / X
564  if (FMulOrDiv->hasOneUse()) {
565  // It would otherwise introduce another div.
566  Constant *F = ConstantExpr::getFMul(C0, C);
567  if (isNormalFp(F))
568  R = BinaryOperator::CreateFDiv(F, Opnd1);
569  }
570  } else {
571  // (X / C1) * C => X * (C/C1) if C/C1 is not a denormal
572  Constant *F = ConstantExpr::getFDiv(C, C1);
573  if (isNormalFp(F)) {
574  R = BinaryOperator::CreateFMul(Opnd0, F);
575  } else {
576  // (X / C1) * C => X / (C1/C)
577  Constant *F = ConstantExpr::getFDiv(C1, C);
578  if (isNormalFp(F))
579  R = BinaryOperator::CreateFDiv(Opnd0, F);
580  }
581  }
582  }
583 
584  if (R) {
585  R->setHasUnsafeAlgebra(true);
586  InsertNewInstWith(R, *InsertBefore);
587  }
588 
589  return R;
590 }
591 
593  bool Changed = SimplifyAssociativeOrCommutative(I);
594  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
595 
596  if (Value *V = SimplifyVectorOp(I))
597  return replaceInstUsesWith(I, V);
598 
599  if (isa<Constant>(Op0))
600  std::swap(Op0, Op1);
601 
602  if (Value *V = SimplifyFMulInst(Op0, Op1, I.getFastMathFlags(),
603  SQ.getWithInstruction(&I)))
604  return replaceInstUsesWith(I, V);
605 
606  bool AllowReassociate = I.hasUnsafeAlgebra();
607 
608  // Simplify mul instructions with a constant RHS.
609  if (isa<Constant>(Op1)) {
610  if (Instruction *FoldedMul = foldOpWithConstantIntoOperand(I))
611  return FoldedMul;
612 
613  // (fmul X, -1.0) --> (fsub -0.0, X)
614  if (match(Op1, m_SpecificFP(-1.0))) {
615  Constant *NegZero = ConstantFP::getNegativeZero(Op1->getType());
616  Instruction *RI = BinaryOperator::CreateFSub(NegZero, Op0);
617  RI->copyFastMathFlags(&I);
618  return RI;
619  }
620 
621  Constant *C = cast<Constant>(Op1);
622  if (AllowReassociate && isFiniteNonZeroFp(C)) {
623  // Let MDC denote an expression in one of these forms:
624  // X * C, C/X, X/C, where C is a constant.
625  //
626  // Try to simplify "MDC * Constant"
627  if (isFMulOrFDivWithConstant(Op0))
628  if (Value *V = foldFMulConst(cast<Instruction>(Op0), C, &I))
629  return replaceInstUsesWith(I, V);
630 
631  // (MDC +/- C1) * C => (MDC * C) +/- (C1 * C)
632  Instruction *FAddSub = dyn_cast<Instruction>(Op0);
633  if (FAddSub &&
634  (FAddSub->getOpcode() == Instruction::FAdd ||
635  FAddSub->getOpcode() == Instruction::FSub)) {
636  Value *Opnd0 = FAddSub->getOperand(0);
637  Value *Opnd1 = FAddSub->getOperand(1);
638  Constant *C0 = dyn_cast<Constant>(Opnd0);
639  Constant *C1 = dyn_cast<Constant>(Opnd1);
640  bool Swap = false;
641  if (C0) {
642  std::swap(C0, C1);
643  std::swap(Opnd0, Opnd1);
644  Swap = true;
645  }
646 
647  if (C1 && isFiniteNonZeroFp(C1) && isFMulOrFDivWithConstant(Opnd0)) {
648  Value *M1 = ConstantExpr::getFMul(C1, C);
649  Value *M0 = isNormalFp(cast<Constant>(M1)) ?
650  foldFMulConst(cast<Instruction>(Opnd0), C, &I) :
651  nullptr;
652  if (M0 && M1) {
653  if (Swap && FAddSub->getOpcode() == Instruction::FSub)
654  std::swap(M0, M1);
655 
656  Instruction *RI = (FAddSub->getOpcode() == Instruction::FAdd)
657  ? BinaryOperator::CreateFAdd(M0, M1)
658  : BinaryOperator::CreateFSub(M0, M1);
659  RI->copyFastMathFlags(&I);
660  return RI;
661  }
662  }
663  }
664  }
665  }
666 
667  if (Op0 == Op1) {
668  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op0)) {
669  // sqrt(X) * sqrt(X) -> X
670  if (AllowReassociate && II->getIntrinsicID() == Intrinsic::sqrt)
671  return replaceInstUsesWith(I, II->getOperand(0));
672 
673  // fabs(X) * fabs(X) -> X * X
674  if (II->getIntrinsicID() == Intrinsic::fabs) {
675  Instruction *FMulVal = BinaryOperator::CreateFMul(II->getOperand(0),
676  II->getOperand(0),
677  I.getName());
678  FMulVal->copyFastMathFlags(&I);
679  return FMulVal;
680  }
681  }
682  }
683 
684  // Under unsafe algebra do:
685  // X * log2(0.5*Y) = X*log2(Y) - X
686  if (AllowReassociate) {
687  Value *OpX = nullptr;
688  Value *OpY = nullptr;
690  detectLog2OfHalf(Op0, OpY, Log2);
691  if (OpY) {
692  OpX = Op1;
693  } else {
694  detectLog2OfHalf(Op1, OpY, Log2);
695  if (OpY) {
696  OpX = Op0;
697  }
698  }
699  // if pattern detected emit alternate sequence
700  if (OpX && OpY) {
701  BuilderTy::FastMathFlagGuard Guard(Builder);
702  Builder.setFastMathFlags(Log2->getFastMathFlags());
703  Log2->setArgOperand(0, OpY);
704  Value *FMulVal = Builder.CreateFMul(OpX, Log2);
705  Value *FSub = Builder.CreateFSub(FMulVal, OpX);
706  FSub->takeName(&I);
707  return replaceInstUsesWith(I, FSub);
708  }
709  }
710 
711  // Handle symmetric situation in a 2-iteration loop
712  Value *Opnd0 = Op0;
713  Value *Opnd1 = Op1;
714  for (int i = 0; i < 2; i++) {
715  bool IgnoreZeroSign = I.hasNoSignedZeros();
716  if (BinaryOperator::isFNeg(Opnd0, IgnoreZeroSign)) {
717  BuilderTy::FastMathFlagGuard Guard(Builder);
718  Builder.setFastMathFlags(I.getFastMathFlags());
719 
720  Value *N0 = dyn_castFNegVal(Opnd0, IgnoreZeroSign);
721  Value *N1 = dyn_castFNegVal(Opnd1, IgnoreZeroSign);
722 
723  // -X * -Y => X*Y
724  if (N1) {
725  Value *FMul = Builder.CreateFMul(N0, N1);
726  FMul->takeName(&I);
727  return replaceInstUsesWith(I, FMul);
728  }
729 
730  if (Opnd0->hasOneUse()) {
731  // -X * Y => -(X*Y) (Promote negation as high as possible)
732  Value *T = Builder.CreateFMul(N0, Opnd1);
733  Value *Neg = Builder.CreateFNeg(T);
734  Neg->takeName(&I);
735  return replaceInstUsesWith(I, Neg);
736  }
737  }
738 
739  // Handle specials cases for FMul with selects feeding the operation
740  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
741  return replaceInstUsesWith(I, V);
742 
743  // (X*Y) * X => (X*X) * Y where Y != X
744  // The purpose is two-fold:
745  // 1) to form a power expression (of X).
746  // 2) potentially shorten the critical path: After transformation, the
747  // latency of the instruction Y is amortized by the expression of X*X,
748  // and therefore Y is in a "less critical" position compared to what it
749  // was before the transformation.
750  //
751  if (AllowReassociate) {
752  Value *Opnd0_0, *Opnd0_1;
753  if (Opnd0->hasOneUse() &&
754  match(Opnd0, m_FMul(m_Value(Opnd0_0), m_Value(Opnd0_1)))) {
755  Value *Y = nullptr;
756  if (Opnd0_0 == Opnd1 && Opnd0_1 != Opnd1)
757  Y = Opnd0_1;
758  else if (Opnd0_1 == Opnd1 && Opnd0_0 != Opnd1)
759  Y = Opnd0_0;
760 
761  if (Y) {
762  BuilderTy::FastMathFlagGuard Guard(Builder);
763  Builder.setFastMathFlags(I.getFastMathFlags());
764  Value *T = Builder.CreateFMul(Opnd1, Opnd1);
765  Value *R = Builder.CreateFMul(T, Y);
766  R->takeName(&I);
767  return replaceInstUsesWith(I, R);
768  }
769  }
770  }
771 
772  if (!isa<Constant>(Op1))
773  std::swap(Opnd0, Opnd1);
774  else
775  break;
776  }
777 
778  return Changed ? &I : nullptr;
779 }
780 
781 /// Try to fold a divide or remainder of a select instruction.
783  SelectInst *SI = cast<SelectInst>(I.getOperand(1));
784 
785  // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
786  int NonNullOperand = -1;
787  if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1)))
788  if (ST->isNullValue())
789  NonNullOperand = 2;
790  // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
791  if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2)))
792  if (ST->isNullValue())
793  NonNullOperand = 1;
794 
795  if (NonNullOperand == -1)
796  return false;
797 
798  Value *SelectCond = SI->getOperand(0);
799 
800  // Change the div/rem to use 'Y' instead of the select.
801  I.setOperand(1, SI->getOperand(NonNullOperand));
802 
803  // Okay, we know we replace the operand of the div/rem with 'Y' with no
804  // problem. However, the select, or the condition of the select may have
805  // multiple uses. Based on our knowledge that the operand must be non-zero,
806  // propagate the known value for the select into other uses of it, and
807  // propagate a known value of the condition into its other users.
808 
809  // If the select and condition only have a single use, don't bother with this,
810  // early exit.
811  if (SI->use_empty() && SelectCond->hasOneUse())
812  return true;
813 
814  // Scan the current block backward, looking for other uses of SI.
815  BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin();
816 
817  while (BBI != BBFront) {
818  --BBI;
819  // If we found a call to a function, we can't assume it will return, so
820  // information from below it cannot be propagated above it.
821  if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI))
822  break;
823 
824  // Replace uses of the select or its condition with the known values.
825  for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end();
826  I != E; ++I) {
827  if (*I == SI) {
828  *I = SI->getOperand(NonNullOperand);
829  Worklist.Add(&*BBI);
830  } else if (*I == SelectCond) {
831  *I = Builder.getInt1(NonNullOperand == 1);
832  Worklist.Add(&*BBI);
833  }
834  }
835 
836  // If we past the instruction, quit looking for it.
837  if (&*BBI == SI)
838  SI = nullptr;
839  if (&*BBI == SelectCond)
840  SelectCond = nullptr;
841 
842  // If we ran out of things to eliminate, break out of the loop.
843  if (!SelectCond && !SI)
844  break;
845 
846  }
847  return true;
848 }
849 
850 
851 /// This function implements the transforms common to both integer division
852 /// instructions (udiv and sdiv). It is called by the visitors to those integer
853 /// division instructions.
854 /// @brief Common integer divide transforms
856  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
857 
858  // The RHS is known non-zero.
859  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
860  I.setOperand(1, V);
861  return &I;
862  }
863 
864  // Handle cases involving: [su]div X, (select Cond, Y, Z)
865  // This does not apply for fdiv.
866  if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
867  return &I;
868 
869  if (Instruction *LHS = dyn_cast<Instruction>(Op0)) {
870  const APInt *C2;
871  if (match(Op1, m_APInt(C2))) {
872  Value *X;
873  const APInt *C1;
874  bool IsSigned = I.getOpcode() == Instruction::SDiv;
875 
876  // (X / C1) / C2 -> X / (C1*C2)
877  if ((IsSigned && match(LHS, m_SDiv(m_Value(X), m_APInt(C1)))) ||
878  (!IsSigned && match(LHS, m_UDiv(m_Value(X), m_APInt(C1))))) {
879  APInt Product(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
880  if (!MultiplyOverflows(*C1, *C2, Product, IsSigned))
881  return BinaryOperator::Create(I.getOpcode(), X,
882  ConstantInt::get(I.getType(), Product));
883  }
884 
885  if ((IsSigned && match(LHS, m_NSWMul(m_Value(X), m_APInt(C1)))) ||
886  (!IsSigned && match(LHS, m_NUWMul(m_Value(X), m_APInt(C1))))) {
887  APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
888 
889  // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
890  if (IsMultiple(*C2, *C1, Quotient, IsSigned)) {
892  I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient));
893  BO->setIsExact(I.isExact());
894  return BO;
895  }
896 
897  // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
898  if (IsMultiple(*C1, *C2, Quotient, IsSigned)) {
900  Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient));
902  !IsSigned &&
903  cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap());
904  BO->setHasNoSignedWrap(
905  cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap());
906  return BO;
907  }
908  }
909 
910  if ((IsSigned && match(LHS, m_NSWShl(m_Value(X), m_APInt(C1))) &&
911  *C1 != C1->getBitWidth() - 1) ||
912  (!IsSigned && match(LHS, m_NUWShl(m_Value(X), m_APInt(C1))))) {
913  APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
914  APInt C1Shifted = APInt::getOneBitSet(
915  C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue()));
916 
917  // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of C1.
918  if (IsMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
920  I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient));
921  BO->setIsExact(I.isExact());
922  return BO;
923  }
924 
925  // (X << C1) / C2 -> X * (C2 >> C1) if C1 is a multiple of C2.
926  if (IsMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
928  Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient));
930  !IsSigned &&
931  cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap());
932  BO->setHasNoSignedWrap(
933  cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap());
934  return BO;
935  }
936  }
937 
938  if (!C2->isNullValue()) // avoid X udiv 0
939  if (Instruction *FoldedDiv = foldOpWithConstantIntoOperand(I))
940  return FoldedDiv;
941  }
942  }
943 
944  if (match(Op0, m_One())) {
945  assert(!I.getType()->isIntOrIntVectorTy(1) && "i1 divide not removed?");
946  if (I.getOpcode() == Instruction::SDiv) {
947  // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the
948  // result is one, if Op1 is -1 then the result is minus one, otherwise
949  // it's zero.
950  Value *Inc = Builder.CreateAdd(Op1, Op0);
951  Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(I.getType(), 3));
952  return SelectInst::Create(Cmp, Op1, ConstantInt::get(I.getType(), 0));
953  } else {
954  // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
955  // result is one, otherwise it's zero.
956  return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), I.getType());
957  }
958  }
959 
960  // See if we can fold away this div instruction.
961  if (SimplifyDemandedInstructionBits(I))
962  return &I;
963 
964  // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
965  Value *X = nullptr, *Z = nullptr;
966  if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1
967  bool isSigned = I.getOpcode() == Instruction::SDiv;
968  if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
969  (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
970  return BinaryOperator::Create(I.getOpcode(), X, Op1);
971  }
972 
973  return nullptr;
974 }
975 
976 namespace {
977 const unsigned MaxDepth = 6;
978 typedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1,
979  const BinaryOperator &I,
980  InstCombiner &IC);
981 
982 /// \brief Used to maintain state for visitUDivOperand().
983 struct UDivFoldAction {
984  FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this
985  ///< operand. This can be zero if this action
986  ///< joins two actions together.
987 
988  Value *OperandToFold; ///< Which operand to fold.
989  union {
990  Instruction *FoldResult; ///< The instruction returned when FoldAction is
991  ///< invoked.
992 
993  size_t SelectLHSIdx; ///< Stores the LHS action index if this action
994  ///< joins two actions together.
995  };
996 
997  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
998  : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
999  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
1000  : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
1001 };
1002 }
1003 
1004 // X udiv 2^C -> X >> C
1006  const BinaryOperator &I, InstCombiner &IC) {
1007  const APInt &C = cast<Constant>(Op1)->getUniqueInteger();
1008  BinaryOperator *LShr = BinaryOperator::CreateLShr(
1009  Op0, ConstantInt::get(Op0->getType(), C.logBase2()));
1010  if (I.isExact())
1011  LShr->setIsExact();
1012  return LShr;
1013 }
1014 
1015 // X udiv C, where C >= signbit
1017  const BinaryOperator &I, InstCombiner &IC) {
1018  Value *ICI = IC.Builder.CreateICmpULT(Op0, cast<ConstantInt>(Op1));
1019 
1021  ConstantInt::get(I.getType(), 1));
1022 }
1023 
1024 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
1025 // X udiv (zext (C1 << N)), where C1 is "1<<C2" --> X >> (N+C2)
1026 static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
1027  InstCombiner &IC) {
1028  Value *ShiftLeft;
1029  if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
1030  ShiftLeft = Op1;
1031 
1032  const APInt *CI;
1033  Value *N;
1034  if (!match(ShiftLeft, m_Shl(m_APInt(CI), m_Value(N))))
1035  llvm_unreachable("match should never fail here!");
1036  if (*CI != 1)
1037  N = IC.Builder.CreateAdd(N, ConstantInt::get(N->getType(), CI->logBase2()));
1038  if (Op1 != ShiftLeft)
1039  N = IC.Builder.CreateZExt(N, Op1->getType());
1040  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
1041  if (I.isExact())
1042  LShr->setIsExact();
1043  return LShr;
1044 }
1045 
1046 // \brief Recursively visits the possible right hand operands of a udiv
1047 // instruction, seeing through select instructions, to determine if we can
1048 // replace the udiv with something simpler. If we find that an operand is not
1049 // able to simplify the udiv, we abort the entire transformation.
1050 static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
1052  unsigned Depth = 0) {
1053  // Check to see if this is an unsigned division with an exact power of 2,
1054  // if so, convert to a right shift.
1055  if (match(Op1, m_Power2())) {
1056  Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1));
1057  return Actions.size();
1058  }
1059 
1060  if (ConstantInt *C = dyn_cast<ConstantInt>(Op1))
1061  // X udiv C, where C >= signbit
1062  if (C->getValue().isNegative()) {
1063  Actions.push_back(UDivFoldAction(foldUDivNegCst, C));
1064  return Actions.size();
1065  }
1066 
1067  // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
1068  if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
1069  match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
1070  Actions.push_back(UDivFoldAction(foldUDivShl, Op1));
1071  return Actions.size();
1072  }
1073 
1074  // The remaining tests are all recursive, so bail out if we hit the limit.
1075  if (Depth++ == MaxDepth)
1076  return 0;
1077 
1078  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1079  if (size_t LHSIdx =
1080  visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth))
1081  if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) {
1082  Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1));
1083  return Actions.size();
1084  }
1085 
1086  return 0;
1087 }
1088 
1089 /// If we have zero-extended operands of an unsigned div or rem, we may be able
1090 /// to narrow the operation (sink the zext below the math).
1092  InstCombiner::BuilderTy &Builder) {
1093  Instruction::BinaryOps Opcode = I.getOpcode();
1094  Value *N = I.getOperand(0);
1095  Value *D = I.getOperand(1);
1096  Type *Ty = I.getType();
1097  Value *X, *Y;
1098  if (match(N, m_ZExt(m_Value(X))) && match(D, m_ZExt(m_Value(Y))) &&
1099  X->getType() == Y->getType() && (N->hasOneUse() || D->hasOneUse())) {
1100  // udiv (zext X), (zext Y) --> zext (udiv X, Y)
1101  // urem (zext X), (zext Y) --> zext (urem X, Y)
1102  Value *NarrowOp = Builder.CreateBinOp(Opcode, X, Y);
1103  return new ZExtInst(NarrowOp, Ty);
1104  }
1105 
1106  Constant *C;
1107  if ((match(N, m_OneUse(m_ZExt(m_Value(X)))) && match(D, m_Constant(C))) ||
1108  (match(D, m_OneUse(m_ZExt(m_Value(X)))) && match(N, m_Constant(C)))) {
1109  // If the constant is the same in the smaller type, use the narrow version.
1110  Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
1111  if (ConstantExpr::getZExt(TruncC, Ty) != C)
1112  return nullptr;
1113 
1114  // udiv (zext X), C --> zext (udiv X, C')
1115  // urem (zext X), C --> zext (urem X, C')
1116  // udiv C, (zext X) --> zext (udiv C', X)
1117  // urem C, (zext X) --> zext (urem C', X)
1118  Value *NarrowOp = isa<Constant>(D) ? Builder.CreateBinOp(Opcode, X, TruncC)
1119  : Builder.CreateBinOp(Opcode, TruncC, X);
1120  return new ZExtInst(NarrowOp, Ty);
1121  }
1122 
1123  return nullptr;
1124 }
1125 
1127  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1128 
1129  if (Value *V = SimplifyVectorOp(I))
1130  return replaceInstUsesWith(I, V);
1131 
1132  if (Value *V = SimplifyUDivInst(Op0, Op1, SQ.getWithInstruction(&I)))
1133  return replaceInstUsesWith(I, V);
1134 
1135  // Handle the integer div common cases
1136  if (Instruction *Common = commonIDivTransforms(I))
1137  return Common;
1138 
1139  // (x lshr C1) udiv C2 --> x udiv (C2 << C1)
1140  {
1141  Value *X;
1142  const APInt *C1, *C2;
1143  if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) &&
1144  match(Op1, m_APInt(C2))) {
1145  bool Overflow;
1146  APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
1147  if (!Overflow) {
1148  bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value()));
1149  BinaryOperator *BO = BinaryOperator::CreateUDiv(
1150  X, ConstantInt::get(X->getType(), C2ShlC1));
1151  if (IsExact)
1152  BO->setIsExact();
1153  return BO;
1154  }
1155  }
1156  }
1157 
1158  if (Instruction *NarrowDiv = narrowUDivURem(I, Builder))
1159  return NarrowDiv;
1160 
1161  // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
1162  SmallVector<UDivFoldAction, 6> UDivActions;
1163  if (visitUDivOperand(Op0, Op1, I, UDivActions))
1164  for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) {
1165  FoldUDivOperandCb Action = UDivActions[i].FoldAction;
1166  Value *ActionOp1 = UDivActions[i].OperandToFold;
1167  Instruction *Inst;
1168  if (Action)
1169  Inst = Action(Op0, ActionOp1, I, *this);
1170  else {
1171  // This action joins two actions together. The RHS of this action is
1172  // simply the last action we processed, we saved the LHS action index in
1173  // the joining action.
1174  size_t SelectRHSIdx = i - 1;
1175  Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult;
1176  size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx;
1177  Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult;
1178  Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
1179  SelectLHS, SelectRHS);
1180  }
1181 
1182  // If this is the last action to process, return it to the InstCombiner.
1183  // Otherwise, we insert it before the UDiv and record it so that we may
1184  // use it as part of a joining action (i.e., a SelectInst).
1185  if (e - i != 1) {
1186  Inst->insertBefore(&I);
1187  UDivActions[i].FoldResult = Inst;
1188  } else
1189  return Inst;
1190  }
1191 
1192  return nullptr;
1193 }
1194 
1196  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1197 
1198  if (Value *V = SimplifyVectorOp(I))
1199  return replaceInstUsesWith(I, V);
1200 
1201  if (Value *V = SimplifySDivInst(Op0, Op1, SQ.getWithInstruction(&I)))
1202  return replaceInstUsesWith(I, V);
1203 
1204  // Handle the integer div common cases
1205  if (Instruction *Common = commonIDivTransforms(I))
1206  return Common;
1207 
1208  const APInt *Op1C;
1209  if (match(Op1, m_APInt(Op1C))) {
1210  // sdiv X, -1 == -X
1211  if (Op1C->isAllOnesValue())
1212  return BinaryOperator::CreateNeg(Op0);
1213 
1214  // sdiv exact X, C --> ashr exact X, log2(C)
1215  if (I.isExact() && Op1C->isNonNegative() && Op1C->isPowerOf2()) {
1216  Value *ShAmt = ConstantInt::get(Op1->getType(), Op1C->exactLogBase2());
1217  return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName());
1218  }
1219 
1220  // If the dividend is sign-extended and the constant divisor is small enough
1221  // to fit in the source type, shrink the division to the narrower type:
1222  // (sext X) sdiv C --> sext (X sdiv C)
1223  Value *Op0Src;
1224  if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
1225  Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) {
1226 
1227  // In the general case, we need to make sure that the dividend is not the
1228  // minimum signed value because dividing that by -1 is UB. But here, we
1229  // know that the -1 divisor case is already handled above.
1230 
1231  Constant *NarrowDivisor =
1232  ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
1233  Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
1234  return new SExtInst(NarrowOp, Op0->getType());
1235  }
1236  }
1237 
1238  if (Constant *RHS = dyn_cast<Constant>(Op1)) {
1239  // X/INT_MIN -> X == INT_MIN
1240  if (RHS->isMinSignedValue())
1241  return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), I.getType());
1242 
1243  // -X/C --> X/-C provided the negation doesn't overflow.
1244  Value *X;
1245  if (match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1246  auto *BO = BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(RHS));
1247  BO->setIsExact(I.isExact());
1248  return BO;
1249  }
1250  }
1251 
1252  // If the sign bits of both operands are zero (i.e. we can prove they are
1253  // unsigned inputs), turn this into a udiv.
1255  if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
1256  if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
1257  // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
1258  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1259  BO->setIsExact(I.isExact());
1260  return BO;
1261  }
1262 
1263  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1264  // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1265  // Safe because the only negative value (1 << Y) can take on is
1266  // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1267  // the sign bit set.
1268  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1269  BO->setIsExact(I.isExact());
1270  return BO;
1271  }
1272  }
1273 
1274  return nullptr;
1275 }
1276 
1277 /// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special
1278 /// FP value and:
1279 /// 1) 1/C is exact, or
1280 /// 2) reciprocal is allowed.
1281 /// If the conversion was successful, the simplified expression "X * 1/C" is
1282 /// returned; otherwise, NULL is returned.
1283 ///
1285  bool AllowReciprocal) {
1286  if (!isa<ConstantFP>(Divisor)) // TODO: handle vectors.
1287  return nullptr;
1288 
1289  const APFloat &FpVal = cast<ConstantFP>(Divisor)->getValueAPF();
1290  APFloat Reciprocal(FpVal.getSemantics());
1291  bool Cvt = FpVal.getExactInverse(&Reciprocal);
1292 
1293  if (!Cvt && AllowReciprocal && FpVal.isFiniteNonZero()) {
1294  Reciprocal = APFloat(FpVal.getSemantics(), 1.0f);
1295  (void)Reciprocal.divide(FpVal, APFloat::rmNearestTiesToEven);
1296  Cvt = !Reciprocal.isDenormal();
1297  }
1298 
1299  if (!Cvt)
1300  return nullptr;
1301 
1302  ConstantFP *R;
1303  R = ConstantFP::get(Dividend->getType()->getContext(), Reciprocal);
1304  return BinaryOperator::CreateFMul(Dividend, R);
1305 }
1306 
1308  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1309 
1310  if (Value *V = SimplifyVectorOp(I))
1311  return replaceInstUsesWith(I, V);
1312 
1313  if (Value *V = SimplifyFDivInst(Op0, Op1, I.getFastMathFlags(),
1314  SQ.getWithInstruction(&I)))
1315  return replaceInstUsesWith(I, V);
1316 
1317  if (isa<Constant>(Op0))
1318  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1319  if (Instruction *R = FoldOpIntoSelect(I, SI))
1320  return R;
1321 
1322  bool AllowReassociate = I.hasUnsafeAlgebra();
1323  bool AllowReciprocal = I.hasAllowReciprocal();
1324 
1325  if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
1326  if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1327  if (Instruction *R = FoldOpIntoSelect(I, SI))
1328  return R;
1329 
1330  if (AllowReassociate) {
1331  Constant *C1 = nullptr;
1332  Constant *C2 = Op1C;
1333  Value *X;
1334  Instruction *Res = nullptr;
1335 
1336  if (match(Op0, m_FMul(m_Value(X), m_Constant(C1)))) {
1337  // (X*C1)/C2 => X * (C1/C2)
1338  //
1339  Constant *C = ConstantExpr::getFDiv(C1, C2);
1340  if (isNormalFp(C))
1341  Res = BinaryOperator::CreateFMul(X, C);
1342  } else if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
1343  // (X/C1)/C2 => X /(C2*C1) [=> X * 1/(C2*C1) if reciprocal is allowed]
1344  //
1345  Constant *C = ConstantExpr::getFMul(C1, C2);
1346  if (isNormalFp(C)) {
1347  Res = CvtFDivConstToReciprocal(X, C, AllowReciprocal);
1348  if (!Res)
1349  Res = BinaryOperator::CreateFDiv(X, C);
1350  }
1351  }
1352 
1353  if (Res) {
1355  return Res;
1356  }
1357  }
1358 
1359  // X / C => X * 1/C
1360  if (Instruction *T = CvtFDivConstToReciprocal(Op0, Op1C, AllowReciprocal)) {
1361  T->copyFastMathFlags(&I);
1362  return T;
1363  }
1364 
1365  return nullptr;
1366  }
1367 
1368  if (AllowReassociate && isa<Constant>(Op0)) {
1369  Constant *C1 = cast<Constant>(Op0), *C2;
1370  Constant *Fold = nullptr;
1371  Value *X;
1372  bool CreateDiv = true;
1373 
1374  // C1 / (X*C2) => (C1/C2) / X
1375  if (match(Op1, m_FMul(m_Value(X), m_Constant(C2))))
1376  Fold = ConstantExpr::getFDiv(C1, C2);
1377  else if (match(Op1, m_FDiv(m_Value(X), m_Constant(C2)))) {
1378  // C1 / (X/C2) => (C1*C2) / X
1379  Fold = ConstantExpr::getFMul(C1, C2);
1380  } else if (match(Op1, m_FDiv(m_Constant(C2), m_Value(X)))) {
1381  // C1 / (C2/X) => (C1/C2) * X
1382  Fold = ConstantExpr::getFDiv(C1, C2);
1383  CreateDiv = false;
1384  }
1385 
1386  if (Fold && isNormalFp(Fold)) {
1387  Instruction *R = CreateDiv ? BinaryOperator::CreateFDiv(Fold, X)
1388  : BinaryOperator::CreateFMul(X, Fold);
1390  return R;
1391  }
1392  return nullptr;
1393  }
1394 
1395  if (AllowReassociate) {
1396  Value *X, *Y;
1397  Value *NewInst = nullptr;
1398  Instruction *SimpR = nullptr;
1399 
1400  if (Op0->hasOneUse() && match(Op0, m_FDiv(m_Value(X), m_Value(Y)))) {
1401  // (X/Y) / Z => X / (Y*Z)
1402  //
1403  if (!isa<Constant>(Y) || !isa<Constant>(Op1)) {
1404  NewInst = Builder.CreateFMul(Y, Op1);
1405  if (Instruction *RI = dyn_cast<Instruction>(NewInst)) {
1407  Flags &= cast<Instruction>(Op0)->getFastMathFlags();
1408  RI->setFastMathFlags(Flags);
1409  }
1410  SimpR = BinaryOperator::CreateFDiv(X, NewInst);
1411  }
1412  } else if (Op1->hasOneUse() && match(Op1, m_FDiv(m_Value(X), m_Value(Y)))) {
1413  // Z / (X/Y) => Z*Y / X
1414  //
1415  if (!isa<Constant>(Y) || !isa<Constant>(Op0)) {
1416  NewInst = Builder.CreateFMul(Op0, Y);
1417  if (Instruction *RI = dyn_cast<Instruction>(NewInst)) {
1419  Flags &= cast<Instruction>(Op1)->getFastMathFlags();
1420  RI->setFastMathFlags(Flags);
1421  }
1422  SimpR = BinaryOperator::CreateFDiv(NewInst, X);
1423  }
1424  }
1425 
1426  if (NewInst) {
1427  if (Instruction *T = dyn_cast<Instruction>(NewInst))
1428  T->setDebugLoc(I.getDebugLoc());
1429  SimpR->setFastMathFlags(I.getFastMathFlags());
1430  return SimpR;
1431  }
1432  }
1433 
1434  Value *LHS;
1435  Value *RHS;
1436 
1437  // -x / -y -> x / y
1438  if (match(Op0, m_FNeg(m_Value(LHS))) && match(Op1, m_FNeg(m_Value(RHS)))) {
1439  I.setOperand(0, LHS);
1440  I.setOperand(1, RHS);
1441  return &I;
1442  }
1443 
1444  return nullptr;
1445 }
1446 
1447 /// This function implements the transforms common to both integer remainder
1448 /// instructions (urem and srem). It is called by the visitors to those integer
1449 /// remainder instructions.
1450 /// @brief Common integer remainder transforms
1452  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1453 
1454  // The RHS is known non-zero.
1455  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
1456  I.setOperand(1, V);
1457  return &I;
1458  }
1459 
1460  // Handle cases involving: rem X, (select Cond, Y, Z)
1461  if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
1462  return &I;
1463 
1464  if (isa<Constant>(Op1)) {
1465  if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1466  if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1467  if (Instruction *R = FoldOpIntoSelect(I, SI))
1468  return R;
1469  } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
1470  using namespace llvm::PatternMatch;
1471  const APInt *Op1Int;
1472  if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
1473  (I.getOpcode() == Instruction::URem ||
1474  !Op1Int->isMinSignedValue())) {
1475  // foldOpIntoPhi will speculate instructions to the end of the PHI's
1476  // predecessor blocks, so do this only if we know the srem or urem
1477  // will not fault.
1478  if (Instruction *NV = foldOpIntoPhi(I, PN))
1479  return NV;
1480  }
1481  }
1482 
1483  // See if we can fold away this rem instruction.
1484  if (SimplifyDemandedInstructionBits(I))
1485  return &I;
1486  }
1487  }
1488 
1489  return nullptr;
1490 }
1491 
1493  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1494 
1495  if (Value *V = SimplifyVectorOp(I))
1496  return replaceInstUsesWith(I, V);
1497 
1498  if (Value *V = SimplifyURemInst(Op0, Op1, SQ.getWithInstruction(&I)))
1499  return replaceInstUsesWith(I, V);
1500 
1501  if (Instruction *common = commonIRemTransforms(I))
1502  return common;
1503 
1504  if (Instruction *NarrowRem = narrowUDivURem(I, Builder))
1505  return NarrowRem;
1506 
1507  // X urem Y -> X and Y-1, where Y is a power of 2,
1508  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1510  Value *Add = Builder.CreateAdd(Op1, N1);
1511  return BinaryOperator::CreateAnd(Op0, Add);
1512  }
1513 
1514  // 1 urem X -> zext(X != 1)
1515  if (match(Op0, m_One())) {
1516  Value *Cmp = Builder.CreateICmpNE(Op1, Op0);
1517  Value *Ext = Builder.CreateZExt(Cmp, I.getType());
1518  return replaceInstUsesWith(I, Ext);
1519  }
1520 
1521  // X urem C -> X < C ? X : X - C, where C >= signbit.
1522  const APInt *DivisorC;
1523  if (match(Op1, m_APInt(DivisorC)) && DivisorC->isNegative()) {
1524  Value *Cmp = Builder.CreateICmpULT(Op0, Op1);
1525  Value *Sub = Builder.CreateSub(Op0, Op1);
1526  return SelectInst::Create(Cmp, Op0, Sub);
1527  }
1528 
1529  return nullptr;
1530 }
1531 
1533  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1534 
1535  if (Value *V = SimplifyVectorOp(I))
1536  return replaceInstUsesWith(I, V);
1537 
1538  if (Value *V = SimplifySRemInst(Op0, Op1, SQ.getWithInstruction(&I)))
1539  return replaceInstUsesWith(I, V);
1540 
1541  // Handle the integer rem common cases
1542  if (Instruction *Common = commonIRemTransforms(I))
1543  return Common;
1544 
1545  {
1546  const APInt *Y;
1547  // X % -Y -> X % Y
1548  if (match(Op1, m_APInt(Y)) && Y->isNegative() && !Y->isMinSignedValue()) {
1549  Worklist.AddValue(I.getOperand(1));
1550  I.setOperand(1, ConstantInt::get(I.getType(), -*Y));
1551  return &I;
1552  }
1553  }
1554 
1555  // If the sign bits of both operands are zero (i.e. we can prove they are
1556  // unsigned inputs), turn this into a urem.
1558  if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1559  MaskedValueIsZero(Op0, Mask, 0, &I)) {
1560  // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1561  return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1562  }
1563 
1564  // If it's a constant vector, flip any negative values positive.
1565  if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1566  Constant *C = cast<Constant>(Op1);
1567  unsigned VWidth = C->getType()->getVectorNumElements();
1568 
1569  bool hasNegative = false;
1570  bool hasMissing = false;
1571  for (unsigned i = 0; i != VWidth; ++i) {
1572  Constant *Elt = C->getAggregateElement(i);
1573  if (!Elt) {
1574  hasMissing = true;
1575  break;
1576  }
1577 
1578  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1579  if (RHS->isNegative())
1580  hasNegative = true;
1581  }
1582 
1583  if (hasNegative && !hasMissing) {
1584  SmallVector<Constant *, 16> Elts(VWidth);
1585  for (unsigned i = 0; i != VWidth; ++i) {
1586  Elts[i] = C->getAggregateElement(i); // Handle undef, etc.
1587  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1588  if (RHS->isNegative())
1589  Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1590  }
1591  }
1592 
1593  Constant *NewRHSV = ConstantVector::get(Elts);
1594  if (NewRHSV != C) { // Don't loop on -MININT
1595  Worklist.AddValue(I.getOperand(1));
1596  I.setOperand(1, NewRHSV);
1597  return &I;
1598  }
1599  }
1600  }
1601 
1602  return nullptr;
1603 }
1604 
1606  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1607 
1608  if (Value *V = SimplifyVectorOp(I))
1609  return replaceInstUsesWith(I, V);
1610 
1611  if (Value *V = SimplifyFRemInst(Op0, Op1, I.getFastMathFlags(),
1612  SQ.getWithInstruction(&I)))
1613  return replaceInstUsesWith(I, V);
1614 
1615  // Handle cases involving: rem X, (select Cond, Y, Z)
1616  if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
1617  return &I;
1618 
1619  return nullptr;
1620 }
APInt abs() const
Get the absolute value;.
Definition: APInt.h:1779
A vector constant whose element type is a simple 1/2/4/8-byte integer or float/double, and whose elements are just simple data values (i.e.
Definition: Constants.h:735
static Instruction * foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I, InstCombiner &IC)
uint64_t CallInst * C
Instruction * visitSDiv(BinaryOperator &I)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:645
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")
void setFastMathFlags(FastMathFlags FMF)
Convenience function for setting multiple fast-math flags on this instruction, which must be an opera...
bool hasNoSignedZeros() const
Determine whether the no-signed-zeros flag is set.
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1108
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:514
DiagnosticInfoOptimizationBase::Argument NV
bool SimplifyDivRemOfSelect(BinaryOperator &I)
Try to fold a divide or remainder of a select instruction.
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. ...
struct fuzzer::@309 Flags
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:523
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1558
Constant * getElementAsConstant(unsigned i) const
Return a Constant for a specified index&#39;s element.
Definition: Constants.cpp:2645
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
BinaryOp_match< LHS, RHS, Instruction::FDiv > m_FDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:550
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:562
match_zero m_Zero()
Match an arbitrary zero/null constant.
Definition: PatternMatch.h:145
This class represents zero extension of integer types.
Instruction * visitFRem(BinaryOperator &I)
static Constant * getLogBase2Vector(ConstantDataVector *CV)
A helper routine of InstCombiner::visitMul().
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:526
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:91
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition: APInt.cpp:1835
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:1938
F(f)
const fltSemantics & getSemantics() const
Definition: APFloat.h:1140
This class represents a sign extension of integer types.
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:227
fneg_match< LHS > m_FNeg(const LHS &L)
Match a floating point negate.
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1488
Instruction * visitFMul(BinaryOperator &I)
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:130
Instruction * visitFDiv(BinaryOperator &I)
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:207
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
Instruction * visitMul(BinaryOperator &I)
static Constant * getFMul(Constant *C1, Constant *C2)
Definition: Constants.cpp:2144
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:404
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:362
static Constant * getNegativeZero(Type *Ty)
Definition: Constants.cpp:664
Exact_match< T > m_Exact(const T &SubPattern)
Definition: PatternMatch.h:799
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:664
The core instruction combiner logic.
bool hasUnsafeAlgebra() const
Determine whether the unsafe-algebra flag is set.
static Constant * getSExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1556
static bool isFiniteNonZeroFp(Constant *C)
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:889
Instruction * commonIDivTransforms(BinaryOperator &I)
This function implements the transforms common to both integer division instructions (udiv and sdiv)...
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:502
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1570
Instruction * visitSRem(BinaryOperator &I)
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.
Definition: PatternMatch.h:924
#define T
int32_t exactLogBase2() const
Definition: APInt.h:1767
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
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:911
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:330
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1383
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:290
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:686
static Constant * getFDiv(Constant *C1, Constant *C2)
Definition: Constants.cpp:2158
static BinaryOperator * CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Value * getOperand(unsigned i) const
Definition: User.h:154
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:277
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:357
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:598
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:389
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:260
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:544
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:694
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:75
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)
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.
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:264
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:581
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:382
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:436
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:592
Value * foldFMulConst(Instruction *FMulOrDiv, Constant *C, Instruction *InsertBefore)
foldFMulConst() is a helper routine of InstCombiner::visitFMul().
Value * SimplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FDiv, fold the result or return null.
self_iterator getIterator()
Definition: ilist_node.h:82
static Instruction * foldUDivNegCst(Value *Op0, Value *Op1, const BinaryOperator &I, InstCombiner &IC)
static bool isNormalFp(Constant *C)
static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I, SmallVectorImpl< UDivFoldAction > &Actions, unsigned Depth=0)
static double log2(double V)
static Constant * getAllOnesValue(Type *Ty)
Get the all ones value.
Definition: Constants.cpp:261
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...
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.
const APFloat & getValueAPF() const
Definition: Constants.h:294
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:918
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:51
const unsigned MaxDepth
static bool isFMulOrFDivWithConstant(Value *V)
Helper function of InstCombiner::visitFMul(BinaryOperator().
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:548
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag...
Iterator for intrusive lists based on ilist_node.
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return the number of times the sign bit of the register is replicated into the other bits...
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:520
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
bool isFiniteNonZero() const
Definition: APFloat.h:1142
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:556
static Instruction * CvtFDivConstToReciprocal(Value *Dividend, Constant *Divisor, bool AllowReciprocal)
CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special FP value and: 1) 1/C is e...
BinaryOp_match< LHS, RHS, Instruction::UDiv > m_UDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:538
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:1542
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:560
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.
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:623
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:532
void setOperand(unsigned i, Value *Val)
Definition: User.h:159
unsigned logBase2() const
Definition: APInt.h:1727
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:462
bool getExactInverse(APFloat *inv) const
Definition: APFloat.h:1161
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:457
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:1008
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:2096
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:284
Instruction * visitURem(BinaryOperator &I)
match_one m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:194
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:475
static bool isFNeg(const Value *V, bool IgnoreZeroSign=false)
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
APInt smul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1905
#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:661
static bool IsMultiple(const APInt &C1, const APInt &C2, APInt &Quotient, bool IsSigned)
True if C2 is a multiple of C1. Quotient contains C2/C1.
void setArgOperand(unsigned i, Value *v)
bool isNormal() const
Definition: APFloat.h:1136
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:2186
bool isLogicalShift() const
Return true if this is a logical shift left or a logical shift right.
Definition: Instruction.h:150
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:430
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:1915
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nsw 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:1531
match_all_ones m_AllOnes()
Match an integer or vector with all bits set to true.
Definition: PatternMatch.h:205
unsigned getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:115
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:1704
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:653
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
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:179
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:408
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:160
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
unsigned getNumElements() const
Return the number of elements in the array or vector.
Definition: Constants.cpp:2294
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
static void detectLog2OfHalf(Value *&Op, Value *&Y, IntrinsicInst *&Log2)
Detect pattern log2(Y * 0.5) with corresponding fast math flags.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool use_empty() const
Definition: Value.h:322
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:984
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:399
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
const BasicBlock * getParent() const
Definition: Instruction.h:66