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