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