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