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