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  // (X*Y) * X => (X*X) * Y where Y != X
740  // The purpose is two-fold:
741  // 1) to form a power expression (of X).
742  // 2) potentially shorten the critical path: After transformation, the
743  // latency of the instruction Y is amortized by the expression of X*X,
744  // and therefore Y is in a "less critical" position compared to what it
745  // was before the transformation.
746  //
747  if (AllowReassociate) {
748  Value *Opnd0_0, *Opnd0_1;
749  if (Opnd0->hasOneUse() &&
750  match(Opnd0, m_FMul(m_Value(Opnd0_0), m_Value(Opnd0_1)))) {
751  Value *Y = nullptr;
752  if (Opnd0_0 == Opnd1 && Opnd0_1 != Opnd1)
753  Y = Opnd0_1;
754  else if (Opnd0_1 == Opnd1 && Opnd0_0 != Opnd1)
755  Y = Opnd0_0;
756 
757  if (Y) {
758  BuilderTy::FastMathFlagGuard Guard(Builder);
759  Builder.setFastMathFlags(I.getFastMathFlags());
760  Value *T = Builder.CreateFMul(Opnd1, Opnd1);
761  Value *R = Builder.CreateFMul(T, Y);
762  R->takeName(&I);
763  return replaceInstUsesWith(I, R);
764  }
765  }
766  }
767 
768  if (!isa<Constant>(Op1))
769  std::swap(Opnd0, Opnd1);
770  else
771  break;
772  }
773 
774  return Changed ? &I : nullptr;
775 }
776 
777 /// Try to fold a divide or remainder of a select instruction.
779  SelectInst *SI = cast<SelectInst>(I.getOperand(1));
780 
781  // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
782  int NonNullOperand = -1;
783  if (Constant *ST = dyn_cast<Constant>(SI->getOperand(1)))
784  if (ST->isNullValue())
785  NonNullOperand = 2;
786  // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
787  if (Constant *ST = dyn_cast<Constant>(SI->getOperand(2)))
788  if (ST->isNullValue())
789  NonNullOperand = 1;
790 
791  if (NonNullOperand == -1)
792  return false;
793 
794  Value *SelectCond = SI->getOperand(0);
795 
796  // Change the div/rem to use 'Y' instead of the select.
797  I.setOperand(1, SI->getOperand(NonNullOperand));
798 
799  // Okay, we know we replace the operand of the div/rem with 'Y' with no
800  // problem. However, the select, or the condition of the select may have
801  // multiple uses. Based on our knowledge that the operand must be non-zero,
802  // propagate the known value for the select into other uses of it, and
803  // propagate a known value of the condition into its other users.
804 
805  // If the select and condition only have a single use, don't bother with this,
806  // early exit.
807  if (SI->use_empty() && SelectCond->hasOneUse())
808  return true;
809 
810  // Scan the current block backward, looking for other uses of SI.
811  BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin();
812 
813  while (BBI != BBFront) {
814  --BBI;
815  // If we found a call to a function, we can't assume it will return, so
816  // information from below it cannot be propagated above it.
817  if (isa<CallInst>(BBI) && !isa<IntrinsicInst>(BBI))
818  break;
819 
820  // Replace uses of the select or its condition with the known values.
821  for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end();
822  I != E; ++I) {
823  if (*I == SI) {
824  *I = SI->getOperand(NonNullOperand);
825  Worklist.Add(&*BBI);
826  } else if (*I == SelectCond) {
827  *I = Builder.getInt1(NonNullOperand == 1);
828  Worklist.Add(&*BBI);
829  }
830  }
831 
832  // If we past the instruction, quit looking for it.
833  if (&*BBI == SI)
834  SI = nullptr;
835  if (&*BBI == SelectCond)
836  SelectCond = nullptr;
837 
838  // If we ran out of things to eliminate, break out of the loop.
839  if (!SelectCond && !SI)
840  break;
841 
842  }
843  return true;
844 }
845 
846 
847 /// This function implements the transforms common to both integer division
848 /// instructions (udiv and sdiv). It is called by the visitors to those integer
849 /// division instructions.
850 /// @brief Common integer divide transforms
852  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
853 
854  // The RHS is known non-zero.
855  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
856  I.setOperand(1, V);
857  return &I;
858  }
859 
860  // Handle cases involving: [su]div X, (select Cond, Y, Z)
861  // This does not apply for fdiv.
862  if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
863  return &I;
864 
865  if (Instruction *LHS = dyn_cast<Instruction>(Op0)) {
866  const APInt *C2;
867  if (match(Op1, m_APInt(C2))) {
868  Value *X;
869  const APInt *C1;
870  bool IsSigned = I.getOpcode() == Instruction::SDiv;
871 
872  // (X / C1) / C2 -> X / (C1*C2)
873  if ((IsSigned && match(LHS, m_SDiv(m_Value(X), m_APInt(C1)))) ||
874  (!IsSigned && match(LHS, m_UDiv(m_Value(X), m_APInt(C1))))) {
875  APInt Product(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
876  if (!MultiplyOverflows(*C1, *C2, Product, IsSigned))
877  return BinaryOperator::Create(I.getOpcode(), X,
878  ConstantInt::get(I.getType(), Product));
879  }
880 
881  if ((IsSigned && match(LHS, m_NSWMul(m_Value(X), m_APInt(C1)))) ||
882  (!IsSigned && match(LHS, m_NUWMul(m_Value(X), m_APInt(C1))))) {
883  APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
884 
885  // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
886  if (IsMultiple(*C2, *C1, Quotient, IsSigned)) {
888  I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient));
889  BO->setIsExact(I.isExact());
890  return BO;
891  }
892 
893  // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
894  if (IsMultiple(*C1, *C2, Quotient, IsSigned)) {
896  Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient));
898  !IsSigned &&
899  cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap());
900  BO->setHasNoSignedWrap(
901  cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap());
902  return BO;
903  }
904  }
905 
906  if ((IsSigned && match(LHS, m_NSWShl(m_Value(X), m_APInt(C1))) &&
907  *C1 != C1->getBitWidth() - 1) ||
908  (!IsSigned && match(LHS, m_NUWShl(m_Value(X), m_APInt(C1))))) {
909  APInt Quotient(C1->getBitWidth(), /*Val=*/0ULL, IsSigned);
910  APInt C1Shifted = APInt::getOneBitSet(
911  C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue()));
912 
913  // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of C1.
914  if (IsMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
916  I.getOpcode(), X, ConstantInt::get(X->getType(), Quotient));
917  BO->setIsExact(I.isExact());
918  return BO;
919  }
920 
921  // (X << C1) / C2 -> X * (C2 >> C1) if C1 is a multiple of C2.
922  if (IsMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
924  Instruction::Mul, X, ConstantInt::get(X->getType(), Quotient));
926  !IsSigned &&
927  cast<OverflowingBinaryOperator>(LHS)->hasNoUnsignedWrap());
928  BO->setHasNoSignedWrap(
929  cast<OverflowingBinaryOperator>(LHS)->hasNoSignedWrap());
930  return BO;
931  }
932  }
933 
934  if (!C2->isNullValue()) // avoid X udiv 0
935  if (Instruction *FoldedDiv = foldOpWithConstantIntoOperand(I))
936  return FoldedDiv;
937  }
938  }
939 
940  if (match(Op0, m_One())) {
941  assert(!I.getType()->isIntOrIntVectorTy(1) && "i1 divide not removed?");
942  if (I.getOpcode() == Instruction::SDiv) {
943  // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the
944  // result is one, if Op1 is -1 then the result is minus one, otherwise
945  // it's zero.
946  Value *Inc = Builder.CreateAdd(Op1, Op0);
947  Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(I.getType(), 3));
948  return SelectInst::Create(Cmp, Op1, ConstantInt::get(I.getType(), 0));
949  } else {
950  // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
951  // result is one, otherwise it's zero.
952  return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), I.getType());
953  }
954  }
955 
956  // See if we can fold away this div instruction.
957  if (SimplifyDemandedInstructionBits(I))
958  return &I;
959 
960  // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
961  Value *X = nullptr, *Z = nullptr;
962  if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) { // (X - Z) / Y; Y = Op1
963  bool isSigned = I.getOpcode() == Instruction::SDiv;
964  if ((isSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
965  (!isSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
966  return BinaryOperator::Create(I.getOpcode(), X, Op1);
967  }
968 
969  return nullptr;
970 }
971 
972 /// dyn_castZExtVal - Checks if V is a zext or constant that can
973 /// be truncated to Ty without losing bits.
974 static Value *dyn_castZExtVal(Value *V, Type *Ty) {
975  if (ZExtInst *Z = dyn_cast<ZExtInst>(V)) {
976  if (Z->getSrcTy() == Ty)
977  return Z->getOperand(0);
978  } else if (ConstantInt *C = dyn_cast<ConstantInt>(V)) {
979  if (C->getValue().getActiveBits() <= cast<IntegerType>(Ty)->getBitWidth())
980  return ConstantExpr::getTrunc(C, Ty);
981  }
982  return nullptr;
983 }
984 
985 namespace {
986 const unsigned MaxDepth = 6;
987 typedef Instruction *(*FoldUDivOperandCb)(Value *Op0, Value *Op1,
988  const BinaryOperator &I,
989  InstCombiner &IC);
990 
991 /// \brief Used to maintain state for visitUDivOperand().
992 struct UDivFoldAction {
993  FoldUDivOperandCb FoldAction; ///< Informs visitUDiv() how to fold this
994  ///< operand. This can be zero if this action
995  ///< joins two actions together.
996 
997  Value *OperandToFold; ///< Which operand to fold.
998  union {
999  Instruction *FoldResult; ///< The instruction returned when FoldAction is
1000  ///< invoked.
1001 
1002  size_t SelectLHSIdx; ///< Stores the LHS action index if this action
1003  ///< joins two actions together.
1004  };
1005 
1006  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
1007  : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
1008  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
1009  : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
1010 };
1011 }
1012 
1013 // X udiv 2^C -> X >> C
1015  const BinaryOperator &I, InstCombiner &IC) {
1016  const APInt &C = cast<Constant>(Op1)->getUniqueInteger();
1017  BinaryOperator *LShr = BinaryOperator::CreateLShr(
1018  Op0, ConstantInt::get(Op0->getType(), C.logBase2()));
1019  if (I.isExact())
1020  LShr->setIsExact();
1021  return LShr;
1022 }
1023 
1024 // X udiv C, where C >= signbit
1026  const BinaryOperator &I, InstCombiner &IC) {
1027  Value *ICI = IC.Builder.CreateICmpULT(Op0, cast<ConstantInt>(Op1));
1028 
1030  ConstantInt::get(I.getType(), 1));
1031 }
1032 
1033 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
1034 // X udiv (zext (C1 << N)), where C1 is "1<<C2" --> X >> (N+C2)
1035 static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
1036  InstCombiner &IC) {
1037  Value *ShiftLeft;
1038  if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
1039  ShiftLeft = Op1;
1040 
1041  const APInt *CI;
1042  Value *N;
1043  if (!match(ShiftLeft, m_Shl(m_APInt(CI), m_Value(N))))
1044  llvm_unreachable("match should never fail here!");
1045  if (*CI != 1)
1046  N = IC.Builder.CreateAdd(N, ConstantInt::get(N->getType(), CI->logBase2()));
1047  if (Op1 != ShiftLeft)
1048  N = IC.Builder.CreateZExt(N, Op1->getType());
1049  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
1050  if (I.isExact())
1051  LShr->setIsExact();
1052  return LShr;
1053 }
1054 
1055 // \brief Recursively visits the possible right hand operands of a udiv
1056 // instruction, seeing through select instructions, to determine if we can
1057 // replace the udiv with something simpler. If we find that an operand is not
1058 // able to simplify the udiv, we abort the entire transformation.
1059 static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
1061  unsigned Depth = 0) {
1062  // Check to see if this is an unsigned division with an exact power of 2,
1063  // if so, convert to a right shift.
1064  if (match(Op1, m_Power2())) {
1065  Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1));
1066  return Actions.size();
1067  }
1068 
1069  if (ConstantInt *C = dyn_cast<ConstantInt>(Op1))
1070  // X udiv C, where C >= signbit
1071  if (C->getValue().isNegative()) {
1072  Actions.push_back(UDivFoldAction(foldUDivNegCst, C));
1073  return Actions.size();
1074  }
1075 
1076  // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
1077  if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
1078  match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
1079  Actions.push_back(UDivFoldAction(foldUDivShl, Op1));
1080  return Actions.size();
1081  }
1082 
1083  // The remaining tests are all recursive, so bail out if we hit the limit.
1084  if (Depth++ == MaxDepth)
1085  return 0;
1086 
1087  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1088  if (size_t LHSIdx =
1089  visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth))
1090  if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) {
1091  Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1));
1092  return Actions.size();
1093  }
1094 
1095  return 0;
1096 }
1097 
1099  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1100 
1101  if (Value *V = SimplifyVectorOp(I))
1102  return replaceInstUsesWith(I, V);
1103 
1104  if (Value *V = SimplifyUDivInst(Op0, Op1, SQ.getWithInstruction(&I)))
1105  return replaceInstUsesWith(I, V);
1106 
1107  // Handle the integer div common cases
1108  if (Instruction *Common = commonIDivTransforms(I))
1109  return Common;
1110 
1111  // (x lshr C1) udiv C2 --> x udiv (C2 << C1)
1112  {
1113  Value *X;
1114  const APInt *C1, *C2;
1115  if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) &&
1116  match(Op1, m_APInt(C2))) {
1117  bool Overflow;
1118  APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
1119  if (!Overflow) {
1120  bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value()));
1121  BinaryOperator *BO = BinaryOperator::CreateUDiv(
1122  X, ConstantInt::get(X->getType(), C2ShlC1));
1123  if (IsExact)
1124  BO->setIsExact();
1125  return BO;
1126  }
1127  }
1128  }
1129 
1130  // (zext A) udiv (zext B) --> zext (A udiv B)
1131  if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0))
1132  if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy()))
1133  return new ZExtInst(
1134  Builder.CreateUDiv(ZOp0->getOperand(0), ZOp1, "div", I.isExact()),
1135  I.getType());
1136 
1137  // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
1138  SmallVector<UDivFoldAction, 6> UDivActions;
1139  if (visitUDivOperand(Op0, Op1, I, UDivActions))
1140  for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) {
1141  FoldUDivOperandCb Action = UDivActions[i].FoldAction;
1142  Value *ActionOp1 = UDivActions[i].OperandToFold;
1143  Instruction *Inst;
1144  if (Action)
1145  Inst = Action(Op0, ActionOp1, I, *this);
1146  else {
1147  // This action joins two actions together. The RHS of this action is
1148  // simply the last action we processed, we saved the LHS action index in
1149  // the joining action.
1150  size_t SelectRHSIdx = i - 1;
1151  Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult;
1152  size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx;
1153  Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult;
1154  Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
1155  SelectLHS, SelectRHS);
1156  }
1157 
1158  // If this is the last action to process, return it to the InstCombiner.
1159  // Otherwise, we insert it before the UDiv and record it so that we may
1160  // use it as part of a joining action (i.e., a SelectInst).
1161  if (e - i != 1) {
1162  Inst->insertBefore(&I);
1163  UDivActions[i].FoldResult = Inst;
1164  } else
1165  return Inst;
1166  }
1167 
1168  return nullptr;
1169 }
1170 
1172  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1173 
1174  if (Value *V = SimplifyVectorOp(I))
1175  return replaceInstUsesWith(I, V);
1176 
1177  if (Value *V = SimplifySDivInst(Op0, Op1, SQ.getWithInstruction(&I)))
1178  return replaceInstUsesWith(I, V);
1179 
1180  // Handle the integer div common cases
1181  if (Instruction *Common = commonIDivTransforms(I))
1182  return Common;
1183 
1184  const APInt *Op1C;
1185  if (match(Op1, m_APInt(Op1C))) {
1186  // sdiv X, -1 == -X
1187  if (Op1C->isAllOnesValue())
1188  return BinaryOperator::CreateNeg(Op0);
1189 
1190  // sdiv exact X, C --> ashr exact X, log2(C)
1191  if (I.isExact() && Op1C->isNonNegative() && Op1C->isPowerOf2()) {
1192  Value *ShAmt = ConstantInt::get(Op1->getType(), Op1C->exactLogBase2());
1193  return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName());
1194  }
1195 
1196  // If the dividend is sign-extended and the constant divisor is small enough
1197  // to fit in the source type, shrink the division to the narrower type:
1198  // (sext X) sdiv C --> sext (X sdiv C)
1199  Value *Op0Src;
1200  if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
1201  Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) {
1202 
1203  // In the general case, we need to make sure that the dividend is not the
1204  // minimum signed value because dividing that by -1 is UB. But here, we
1205  // know that the -1 divisor case is already handled above.
1206 
1207  Constant *NarrowDivisor =
1208  ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
1209  Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
1210  return new SExtInst(NarrowOp, Op0->getType());
1211  }
1212  }
1213 
1214  if (Constant *RHS = dyn_cast<Constant>(Op1)) {
1215  // X/INT_MIN -> X == INT_MIN
1216  if (RHS->isMinSignedValue())
1217  return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), I.getType());
1218 
1219  // -X/C --> X/-C provided the negation doesn't overflow.
1220  Value *X;
1221  if (match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1222  auto *BO = BinaryOperator::CreateSDiv(X, ConstantExpr::getNeg(RHS));
1223  BO->setIsExact(I.isExact());
1224  return BO;
1225  }
1226  }
1227 
1228  // If the sign bits of both operands are zero (i.e. we can prove they are
1229  // unsigned inputs), turn this into a udiv.
1231  if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
1232  if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
1233  // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
1234  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1235  BO->setIsExact(I.isExact());
1236  return BO;
1237  }
1238 
1239  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1240  // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1241  // Safe because the only negative value (1 << Y) can take on is
1242  // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1243  // the sign bit set.
1244  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1245  BO->setIsExact(I.isExact());
1246  return BO;
1247  }
1248  }
1249 
1250  return nullptr;
1251 }
1252 
1253 /// CvtFDivConstToReciprocal tries to convert X/C into X*1/C if C not a special
1254 /// FP value and:
1255 /// 1) 1/C is exact, or
1256 /// 2) reciprocal is allowed.
1257 /// If the conversion was successful, the simplified expression "X * 1/C" is
1258 /// returned; otherwise, NULL is returned.
1259 ///
1261  bool AllowReciprocal) {
1262  if (!isa<ConstantFP>(Divisor)) // TODO: handle vectors.
1263  return nullptr;
1264 
1265  const APFloat &FpVal = cast<ConstantFP>(Divisor)->getValueAPF();
1266  APFloat Reciprocal(FpVal.getSemantics());
1267  bool Cvt = FpVal.getExactInverse(&Reciprocal);
1268 
1269  if (!Cvt && AllowReciprocal && FpVal.isFiniteNonZero()) {
1270  Reciprocal = APFloat(FpVal.getSemantics(), 1.0f);
1271  (void)Reciprocal.divide(FpVal, APFloat::rmNearestTiesToEven);
1272  Cvt = !Reciprocal.isDenormal();
1273  }
1274 
1275  if (!Cvt)
1276  return nullptr;
1277 
1278  ConstantFP *R;
1279  R = ConstantFP::get(Dividend->getType()->getContext(), Reciprocal);
1280  return BinaryOperator::CreateFMul(Dividend, R);
1281 }
1282 
1284  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1285 
1286  if (Value *V = SimplifyVectorOp(I))
1287  return replaceInstUsesWith(I, V);
1288 
1289  if (Value *V = SimplifyFDivInst(Op0, Op1, I.getFastMathFlags(),
1290  SQ.getWithInstruction(&I)))
1291  return replaceInstUsesWith(I, V);
1292 
1293  if (isa<Constant>(Op0))
1294  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1295  if (Instruction *R = FoldOpIntoSelect(I, SI))
1296  return R;
1297 
1298  bool AllowReassociate = I.hasUnsafeAlgebra();
1299  bool AllowReciprocal = I.hasAllowReciprocal();
1300 
1301  if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
1302  if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1303  if (Instruction *R = FoldOpIntoSelect(I, SI))
1304  return R;
1305 
1306  if (AllowReassociate) {
1307  Constant *C1 = nullptr;
1308  Constant *C2 = Op1C;
1309  Value *X;
1310  Instruction *Res = nullptr;
1311 
1312  if (match(Op0, m_FMul(m_Value(X), m_Constant(C1)))) {
1313  // (X*C1)/C2 => X * (C1/C2)
1314  //
1315  Constant *C = ConstantExpr::getFDiv(C1, C2);
1316  if (isNormalFp(C))
1317  Res = BinaryOperator::CreateFMul(X, C);
1318  } else if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
1319  // (X/C1)/C2 => X /(C2*C1) [=> X * 1/(C2*C1) if reciprocal is allowed]
1320  //
1321  Constant *C = ConstantExpr::getFMul(C1, C2);
1322  if (isNormalFp(C)) {
1323  Res = CvtFDivConstToReciprocal(X, C, AllowReciprocal);
1324  if (!Res)
1325  Res = BinaryOperator::CreateFDiv(X, C);
1326  }
1327  }
1328 
1329  if (Res) {
1331  return Res;
1332  }
1333  }
1334 
1335  // X / C => X * 1/C
1336  if (Instruction *T = CvtFDivConstToReciprocal(Op0, Op1C, AllowReciprocal)) {
1337  T->copyFastMathFlags(&I);
1338  return T;
1339  }
1340 
1341  return nullptr;
1342  }
1343 
1344  if (AllowReassociate && isa<Constant>(Op0)) {
1345  Constant *C1 = cast<Constant>(Op0), *C2;
1346  Constant *Fold = nullptr;
1347  Value *X;
1348  bool CreateDiv = true;
1349 
1350  // C1 / (X*C2) => (C1/C2) / X
1351  if (match(Op1, m_FMul(m_Value(X), m_Constant(C2))))
1352  Fold = ConstantExpr::getFDiv(C1, C2);
1353  else if (match(Op1, m_FDiv(m_Value(X), m_Constant(C2)))) {
1354  // C1 / (X/C2) => (C1*C2) / X
1355  Fold = ConstantExpr::getFMul(C1, C2);
1356  } else if (match(Op1, m_FDiv(m_Constant(C2), m_Value(X)))) {
1357  // C1 / (C2/X) => (C1/C2) * X
1358  Fold = ConstantExpr::getFDiv(C1, C2);
1359  CreateDiv = false;
1360  }
1361 
1362  if (Fold && isNormalFp(Fold)) {
1363  Instruction *R = CreateDiv ? BinaryOperator::CreateFDiv(Fold, X)
1364  : BinaryOperator::CreateFMul(X, Fold);
1366  return R;
1367  }
1368  return nullptr;
1369  }
1370 
1371  if (AllowReassociate) {
1372  Value *X, *Y;
1373  Value *NewInst = nullptr;
1374  Instruction *SimpR = nullptr;
1375 
1376  if (Op0->hasOneUse() && match(Op0, m_FDiv(m_Value(X), m_Value(Y)))) {
1377  // (X/Y) / Z => X / (Y*Z)
1378  //
1379  if (!isa<Constant>(Y) || !isa<Constant>(Op1)) {
1380  NewInst = Builder.CreateFMul(Y, Op1);
1381  if (Instruction *RI = dyn_cast<Instruction>(NewInst)) {
1383  Flags &= cast<Instruction>(Op0)->getFastMathFlags();
1384  RI->setFastMathFlags(Flags);
1385  }
1386  SimpR = BinaryOperator::CreateFDiv(X, NewInst);
1387  }
1388  } else if (Op1->hasOneUse() && match(Op1, m_FDiv(m_Value(X), m_Value(Y)))) {
1389  // Z / (X/Y) => Z*Y / X
1390  //
1391  if (!isa<Constant>(Y) || !isa<Constant>(Op0)) {
1392  NewInst = Builder.CreateFMul(Op0, Y);
1393  if (Instruction *RI = dyn_cast<Instruction>(NewInst)) {
1395  Flags &= cast<Instruction>(Op1)->getFastMathFlags();
1396  RI->setFastMathFlags(Flags);
1397  }
1398  SimpR = BinaryOperator::CreateFDiv(NewInst, X);
1399  }
1400  }
1401 
1402  if (NewInst) {
1403  if (Instruction *T = dyn_cast<Instruction>(NewInst))
1404  T->setDebugLoc(I.getDebugLoc());
1405  SimpR->setFastMathFlags(I.getFastMathFlags());
1406  return SimpR;
1407  }
1408  }
1409 
1410  Value *LHS;
1411  Value *RHS;
1412 
1413  // -x / -y -> x / y
1414  if (match(Op0, m_FNeg(m_Value(LHS))) && match(Op1, m_FNeg(m_Value(RHS)))) {
1415  I.setOperand(0, LHS);
1416  I.setOperand(1, RHS);
1417  return &I;
1418  }
1419 
1420  return nullptr;
1421 }
1422 
1423 /// This function implements the transforms common to both integer remainder
1424 /// instructions (urem and srem). It is called by the visitors to those integer
1425 /// remainder instructions.
1426 /// @brief Common integer remainder transforms
1428  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1429 
1430  // The RHS is known non-zero.
1431  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
1432  I.setOperand(1, V);
1433  return &I;
1434  }
1435 
1436  // Handle cases involving: rem X, (select Cond, Y, Z)
1437  if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
1438  return &I;
1439 
1440  if (isa<Constant>(Op1)) {
1441  if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1442  if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1443  if (Instruction *R = FoldOpIntoSelect(I, SI))
1444  return R;
1445  } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
1446  using namespace llvm::PatternMatch;
1447  const APInt *Op1Int;
1448  if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
1449  (I.getOpcode() == Instruction::URem ||
1450  !Op1Int->isMinSignedValue())) {
1451  // foldOpIntoPhi will speculate instructions to the end of the PHI's
1452  // predecessor blocks, so do this only if we know the srem or urem
1453  // will not fault.
1454  if (Instruction *NV = foldOpIntoPhi(I, PN))
1455  return NV;
1456  }
1457  }
1458 
1459  // See if we can fold away this rem instruction.
1460  if (SimplifyDemandedInstructionBits(I))
1461  return &I;
1462  }
1463  }
1464 
1465  return nullptr;
1466 }
1467 
1469  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1470 
1471  if (Value *V = SimplifyVectorOp(I))
1472  return replaceInstUsesWith(I, V);
1473 
1474  if (Value *V = SimplifyURemInst(Op0, Op1, SQ.getWithInstruction(&I)))
1475  return replaceInstUsesWith(I, V);
1476 
1477  if (Instruction *common = commonIRemTransforms(I))
1478  return common;
1479 
1480  // (zext A) urem (zext B) --> zext (A urem B)
1481  if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0))
1482  if (Value *ZOp1 = dyn_castZExtVal(Op1, ZOp0->getSrcTy()))
1483  return new ZExtInst(Builder.CreateURem(ZOp0->getOperand(0), ZOp1),
1484  I.getType());
1485 
1486  // X urem Y -> X and Y-1, where Y is a power of 2,
1487  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1489  Value *Add = Builder.CreateAdd(Op1, N1);
1490  return BinaryOperator::CreateAnd(Op0, Add);
1491  }
1492 
1493  // 1 urem X -> zext(X != 1)
1494  if (match(Op0, m_One())) {
1495  Value *Cmp = Builder.CreateICmpNE(Op1, Op0);
1496  Value *Ext = Builder.CreateZExt(Cmp, I.getType());
1497  return replaceInstUsesWith(I, Ext);
1498  }
1499 
1500  // X urem C -> X < C ? X : X - C, where C >= signbit.
1501  const APInt *DivisorC;
1502  if (match(Op1, m_APInt(DivisorC)) && DivisorC->isNegative()) {
1503  Value *Cmp = Builder.CreateICmpULT(Op0, Op1);
1504  Value *Sub = Builder.CreateSub(Op0, Op1);
1505  return SelectInst::Create(Cmp, Op0, Sub);
1506  }
1507 
1508  return nullptr;
1509 }
1510 
1512  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1513 
1514  if (Value *V = SimplifyVectorOp(I))
1515  return replaceInstUsesWith(I, V);
1516 
1517  if (Value *V = SimplifySRemInst(Op0, Op1, SQ.getWithInstruction(&I)))
1518  return replaceInstUsesWith(I, V);
1519 
1520  // Handle the integer rem common cases
1521  if (Instruction *Common = commonIRemTransforms(I))
1522  return Common;
1523 
1524  {
1525  const APInt *Y;
1526  // X % -Y -> X % Y
1527  if (match(Op1, m_APInt(Y)) && Y->isNegative() && !Y->isMinSignedValue()) {
1528  Worklist.AddValue(I.getOperand(1));
1529  I.setOperand(1, ConstantInt::get(I.getType(), -*Y));
1530  return &I;
1531  }
1532  }
1533 
1534  // If the sign bits of both operands are zero (i.e. we can prove they are
1535  // unsigned inputs), turn this into a urem.
1537  if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1538  MaskedValueIsZero(Op0, Mask, 0, &I)) {
1539  // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1540  return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1541  }
1542 
1543  // If it's a constant vector, flip any negative values positive.
1544  if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1545  Constant *C = cast<Constant>(Op1);
1546  unsigned VWidth = C->getType()->getVectorNumElements();
1547 
1548  bool hasNegative = false;
1549  bool hasMissing = false;
1550  for (unsigned i = 0; i != VWidth; ++i) {
1551  Constant *Elt = C->getAggregateElement(i);
1552  if (!Elt) {
1553  hasMissing = true;
1554  break;
1555  }
1556 
1557  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1558  if (RHS->isNegative())
1559  hasNegative = true;
1560  }
1561 
1562  if (hasNegative && !hasMissing) {
1563  SmallVector<Constant *, 16> Elts(VWidth);
1564  for (unsigned i = 0; i != VWidth; ++i) {
1565  Elts[i] = C->getAggregateElement(i); // Handle undef, etc.
1566  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1567  if (RHS->isNegative())
1568  Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1569  }
1570  }
1571 
1572  Constant *NewRHSV = ConstantVector::get(Elts);
1573  if (NewRHSV != C) { // Don't loop on -MININT
1574  Worklist.AddValue(I.getOperand(1));
1575  I.setOperand(1, NewRHSV);
1576  return &I;
1577  }
1578  }
1579  }
1580 
1581  return nullptr;
1582 }
1583 
1585  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1586 
1587  if (Value *V = SimplifyVectorOp(I))
1588  return replaceInstUsesWith(I, V);
1589 
1590  if (Value *V = SimplifyFRemInst(Op0, Op1, I.getFastMathFlags(),
1591  SQ.getWithInstruction(&I)))
1592  return replaceInstUsesWith(I, V);
1593 
1594  // Handle cases involving: rem X, (select Cond, Y, Z)
1595  if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
1596  return &I;
1597 
1598  return nullptr;
1599 }
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
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:621
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.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:490
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. ...
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:526
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:538
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:502
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
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:380
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:775
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
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)...
zlib-gnu style compression
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:478
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...
#define F(x, y, z)
Definition: MD5.cpp:55
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:900
#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:121
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:306
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:662
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:574
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:389
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:240
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:520
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:670
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.
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.
#define A
Definition: LargeTest.cpp:12
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:358
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:568
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 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:894
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.
#define E
Definition: LargeTest.cpp:27
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
#define B
Definition: LargeTest.cpp:24
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:532
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:514
const size_t N
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:508
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
static std::vector< std::string > Flags
Definition: FlagsTest.cpp:8
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:280
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
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:637
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:146
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...
Definition: Instruction.cpp:98
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:629
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
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 Value * dyn_castZExtVal(Value *V, Type *Ty)
dyn_castZExtVal - Checks if V is a zext or constant that can be truncated to Ty without losing bits...
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