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  // But don't transform constant expressions because there's an inverse fold.
378  if (match(Op0, m_OneUse(m_FNeg(m_Value(X)))) && !isa<ConstantExpr>(Op0))
379  return BinaryOperator::CreateFNegFMF(Builder.CreateFMulFMF(X, Op1, &I), &I);
380 
381  // Sink negation: Y * -X --> -(X * Y)
382  // But don't transform constant expressions because there's an inverse fold.
383  if (match(Op1, m_OneUse(m_FNeg(m_Value(X)))) && !isa<ConstantExpr>(Op1))
384  return BinaryOperator::CreateFNegFMF(Builder.CreateFMulFMF(X, Op0, &I), &I);
385 
386  // fabs(X) * fabs(X) -> X * X
387  if (Op0 == Op1 && match(Op0, m_Intrinsic<Intrinsic::fabs>(m_Value(X))))
388  return BinaryOperator::CreateFMulFMF(X, X, &I);
389 
390  // (select A, B, C) * (select A, D, E) --> select A, (B*D), (C*E)
391  if (Value *V = SimplifySelectsFeedingBinaryOp(I, Op0, Op1))
392  return replaceInstUsesWith(I, V);
393 
394  if (I.hasAllowReassoc()) {
395  // Reassociate constant RHS with another constant to form constant
396  // expression.
397  if (match(Op1, m_Constant(C)) && C->isFiniteNonZeroFP()) {
398  Constant *C1;
399  if (match(Op0, m_OneUse(m_FDiv(m_Constant(C1), m_Value(X))))) {
400  // (C1 / X) * C --> (C * C1) / X
401  Constant *CC1 = ConstantExpr::getFMul(C, C1);
402  if (CC1->isNormalFP())
403  return BinaryOperator::CreateFDivFMF(CC1, X, &I);
404  }
405  if (match(Op0, m_FDiv(m_Value(X), m_Constant(C1)))) {
406  // (X / C1) * C --> X * (C / C1)
407  Constant *CDivC1 = ConstantExpr::getFDiv(C, C1);
408  if (CDivC1->isNormalFP())
409  return BinaryOperator::CreateFMulFMF(X, CDivC1, &I);
410 
411  // If the constant was a denormal, try reassociating differently.
412  // (X / C1) * C --> X / (C1 / C)
413  Constant *C1DivC = ConstantExpr::getFDiv(C1, C);
414  if (Op0->hasOneUse() && C1DivC->isNormalFP())
415  return BinaryOperator::CreateFDivFMF(X, C1DivC, &I);
416  }
417 
418  // We do not need to match 'fadd C, X' and 'fsub X, C' because they are
419  // canonicalized to 'fadd X, C'. Distributing the multiply may allow
420  // further folds and (X * C) + C2 is 'fma'.
421  if (match(Op0, m_OneUse(m_FAdd(m_Value(X), m_Constant(C1))))) {
422  // (X + C1) * C --> (X * C) + (C * C1)
423  Constant *CC1 = ConstantExpr::getFMul(C, C1);
424  Value *XC = Builder.CreateFMulFMF(X, C, &I);
425  return BinaryOperator::CreateFAddFMF(XC, CC1, &I);
426  }
427  if (match(Op0, m_OneUse(m_FSub(m_Constant(C1), m_Value(X))))) {
428  // (C1 - X) * C --> (C * C1) - (X * C)
429  Constant *CC1 = ConstantExpr::getFMul(C, C1);
430  Value *XC = Builder.CreateFMulFMF(X, C, &I);
431  return BinaryOperator::CreateFSubFMF(CC1, XC, &I);
432  }
433  }
434 
435  Value *Z;
436  if (match(&I, m_c_FMul(m_OneUse(m_FDiv(m_Value(X), m_Value(Y))),
437  m_Value(Z)))) {
438  // Sink division: (X / Y) * Z --> (X * Z) / Y
439  Value *NewFMul = Builder.CreateFMulFMF(X, Z, &I);
440  return BinaryOperator::CreateFDivFMF(NewFMul, Y, &I);
441  }
442 
443  // sqrt(X) * sqrt(Y) -> sqrt(X * Y)
444  // nnan disallows the possibility of returning a number if both operands are
445  // negative (in that case, we should return NaN).
446  if (I.hasNoNaNs() &&
447  match(Op0, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(X)))) &&
448  match(Op1, m_OneUse(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) {
449  Value *XY = Builder.CreateFMulFMF(X, Y, &I);
450  Value *Sqrt = Builder.CreateUnaryIntrinsic(Intrinsic::sqrt, XY, &I);
451  return replaceInstUsesWith(I, Sqrt);
452  }
453 
454  // Like the similar transform in instsimplify, this requires 'nsz' because
455  // sqrt(-0.0) = -0.0, and -0.0 * -0.0 does not simplify to -0.0.
456  if (I.hasNoNaNs() && I.hasNoSignedZeros() && Op0 == Op1 &&
457  Op0->hasNUses(2)) {
458  // Peek through fdiv to find squaring of square root:
459  // (X / sqrt(Y)) * (X / sqrt(Y)) --> (X * X) / Y
460  if (match(Op0, m_FDiv(m_Value(X),
461  m_Intrinsic<Intrinsic::sqrt>(m_Value(Y))))) {
462  Value *XX = Builder.CreateFMulFMF(X, X, &I);
463  return BinaryOperator::CreateFDivFMF(XX, Y, &I);
464  }
465  // (sqrt(Y) / X) * (sqrt(Y) / X) --> Y / (X * X)
466  if (match(Op0, m_FDiv(m_Intrinsic<Intrinsic::sqrt>(m_Value(Y)),
467  m_Value(X)))) {
468  Value *XX = Builder.CreateFMulFMF(X, X, &I);
469  return BinaryOperator::CreateFDivFMF(Y, XX, &I);
470  }
471  }
472 
473  // exp(X) * exp(Y) -> exp(X + Y)
474  // Match as long as at least one of exp has only one use.
475  if (match(Op0, m_Intrinsic<Intrinsic::exp>(m_Value(X))) &&
476  match(Op1, m_Intrinsic<Intrinsic::exp>(m_Value(Y))) &&
477  (Op0->hasOneUse() || Op1->hasOneUse())) {
478  Value *XY = Builder.CreateFAddFMF(X, Y, &I);
479  Value *Exp = Builder.CreateUnaryIntrinsic(Intrinsic::exp, XY, &I);
480  return replaceInstUsesWith(I, Exp);
481  }
482 
483  // exp2(X) * exp2(Y) -> exp2(X + Y)
484  // Match as long as at least one of exp2 has only one use.
485  if (match(Op0, m_Intrinsic<Intrinsic::exp2>(m_Value(X))) &&
486  match(Op1, m_Intrinsic<Intrinsic::exp2>(m_Value(Y))) &&
487  (Op0->hasOneUse() || Op1->hasOneUse())) {
488  Value *XY = Builder.CreateFAddFMF(X, Y, &I);
489  Value *Exp2 = Builder.CreateUnaryIntrinsic(Intrinsic::exp2, XY, &I);
490  return replaceInstUsesWith(I, Exp2);
491  }
492 
493  // (X*Y) * X => (X*X) * Y where Y != X
494  // The purpose is two-fold:
495  // 1) to form a power expression (of X).
496  // 2) potentially shorten the critical path: After transformation, the
497  // latency of the instruction Y is amortized by the expression of X*X,
498  // and therefore Y is in a "less critical" position compared to what it
499  // was before the transformation.
500  if (match(Op0, m_OneUse(m_c_FMul(m_Specific(Op1), m_Value(Y)))) &&
501  Op1 != Y) {
502  Value *XX = Builder.CreateFMulFMF(Op1, Op1, &I);
503  return BinaryOperator::CreateFMulFMF(XX, Y, &I);
504  }
505  if (match(Op1, m_OneUse(m_c_FMul(m_Specific(Op0), m_Value(Y)))) &&
506  Op0 != Y) {
507  Value *XX = Builder.CreateFMulFMF(Op0, Op0, &I);
508  return BinaryOperator::CreateFMulFMF(XX, Y, &I);
509  }
510  }
511 
512  // log2(X * 0.5) * Y = log2(X) * Y - Y
513  if (I.isFast()) {
514  IntrinsicInst *Log2 = nullptr;
515  if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::log2>(
516  m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
517  Log2 = cast<IntrinsicInst>(Op0);
518  Y = Op1;
519  }
520  if (match(Op1, m_OneUse(m_Intrinsic<Intrinsic::log2>(
521  m_OneUse(m_FMul(m_Value(X), m_SpecificFP(0.5))))))) {
522  Log2 = cast<IntrinsicInst>(Op1);
523  Y = Op0;
524  }
525  if (Log2) {
526  Log2->setArgOperand(0, X);
527  Log2->copyFastMathFlags(&I);
528  Value *LogXTimesY = Builder.CreateFMulFMF(Log2, Y, &I);
529  return BinaryOperator::CreateFSubFMF(LogXTimesY, Y, &I);
530  }
531  }
532 
533  return nullptr;
534 }
535 
536 /// Fold a divide or remainder with a select instruction divisor when one of the
537 /// select operands is zero. In that case, we can use the other select operand
538 /// because div/rem by zero is undefined.
541  if (!SI)
542  return false;
543 
544  int NonNullOperand;
545  if (match(SI->getTrueValue(), m_Zero()))
546  // div/rem X, (Cond ? 0 : Y) -> div/rem X, Y
547  NonNullOperand = 2;
548  else if (match(SI->getFalseValue(), m_Zero()))
549  // div/rem X, (Cond ? Y : 0) -> div/rem X, Y
550  NonNullOperand = 1;
551  else
552  return false;
553 
554  // Change the div/rem to use 'Y' instead of the select.
555  I.setOperand(1, SI->getOperand(NonNullOperand));
556 
557  // Okay, we know we replace the operand of the div/rem with 'Y' with no
558  // problem. However, the select, or the condition of the select may have
559  // multiple uses. Based on our knowledge that the operand must be non-zero,
560  // propagate the known value for the select into other uses of it, and
561  // propagate a known value of the condition into its other users.
562 
563  // If the select and condition only have a single use, don't bother with this,
564  // early exit.
565  Value *SelectCond = SI->getCondition();
566  if (SI->use_empty() && SelectCond->hasOneUse())
567  return true;
568 
569  // Scan the current block backward, looking for other uses of SI.
570  BasicBlock::iterator BBI = I.getIterator(), BBFront = I.getParent()->begin();
571  Type *CondTy = SelectCond->getType();
572  while (BBI != BBFront) {
573  --BBI;
574  // If we found an instruction that we can't assume will return, so
575  // information from below it cannot be propagated above it.
577  break;
578 
579  // Replace uses of the select or its condition with the known values.
580  for (Instruction::op_iterator I = BBI->op_begin(), E = BBI->op_end();
581  I != E; ++I) {
582  if (*I == SI) {
583  *I = SI->getOperand(NonNullOperand);
584  Worklist.Add(&*BBI);
585  } else if (*I == SelectCond) {
586  *I = NonNullOperand == 1 ? ConstantInt::getTrue(CondTy)
587  : ConstantInt::getFalse(CondTy);
588  Worklist.Add(&*BBI);
589  }
590  }
591 
592  // If we past the instruction, quit looking for it.
593  if (&*BBI == SI)
594  SI = nullptr;
595  if (&*BBI == SelectCond)
596  SelectCond = nullptr;
597 
598  // If we ran out of things to eliminate, break out of the loop.
599  if (!SelectCond && !SI)
600  break;
601 
602  }
603  return true;
604 }
605 
606 /// True if the multiply can not be expressed in an int this size.
607 static bool multiplyOverflows(const APInt &C1, const APInt &C2, APInt &Product,
608  bool IsSigned) {
609  bool Overflow;
610  Product = IsSigned ? C1.smul_ov(C2, Overflow) : C1.umul_ov(C2, Overflow);
611  return Overflow;
612 }
613 
614 /// True if C1 is a multiple of C2. Quotient contains C1/C2.
615 static bool isMultiple(const APInt &C1, const APInt &C2, APInt &Quotient,
616  bool IsSigned) {
617  assert(C1.getBitWidth() == C2.getBitWidth() && "Constant widths not equal");
618 
619  // Bail if we will divide by zero.
620  if (C2.isNullValue())
621  return false;
622 
623  // Bail if we would divide INT_MIN by -1.
624  if (IsSigned && C1.isMinSignedValue() && C2.isAllOnesValue())
625  return false;
626 
627  APInt Remainder(C1.getBitWidth(), /*val=*/0ULL, IsSigned);
628  if (IsSigned)
629  APInt::sdivrem(C1, C2, Quotient, Remainder);
630  else
631  APInt::udivrem(C1, C2, Quotient, Remainder);
632 
633  return Remainder.isMinValue();
634 }
635 
636 /// This function implements the transforms common to both integer division
637 /// instructions (udiv and sdiv). It is called by the visitors to those integer
638 /// division instructions.
639 /// Common integer divide transforms
641  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
642  bool IsSigned = I.getOpcode() == Instruction::SDiv;
643  Type *Ty = I.getType();
644 
645  // The RHS is known non-zero.
646  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
647  I.setOperand(1, V);
648  return &I;
649  }
650 
651  // Handle cases involving: [su]div X, (select Cond, Y, Z)
652  // This does not apply for fdiv.
653  if (simplifyDivRemOfSelectWithZeroOp(I))
654  return &I;
655 
656  const APInt *C2;
657  if (match(Op1, m_APInt(C2))) {
658  Value *X;
659  const APInt *C1;
660 
661  // (X / C1) / C2 -> X / (C1*C2)
662  if ((IsSigned && match(Op0, m_SDiv(m_Value(X), m_APInt(C1)))) ||
663  (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_APInt(C1))))) {
664  APInt Product(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
665  if (!multiplyOverflows(*C1, *C2, Product, IsSigned))
666  return BinaryOperator::Create(I.getOpcode(), X,
667  ConstantInt::get(Ty, Product));
668  }
669 
670  if ((IsSigned && match(Op0, m_NSWMul(m_Value(X), m_APInt(C1)))) ||
671  (!IsSigned && match(Op0, m_NUWMul(m_Value(X), m_APInt(C1))))) {
672  APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
673 
674  // (X * C1) / C2 -> X / (C2 / C1) if C2 is a multiple of C1.
675  if (isMultiple(*C2, *C1, Quotient, IsSigned)) {
676  auto *NewDiv = BinaryOperator::Create(I.getOpcode(), X,
677  ConstantInt::get(Ty, Quotient));
678  NewDiv->setIsExact(I.isExact());
679  return NewDiv;
680  }
681 
682  // (X * C1) / C2 -> X * (C1 / C2) if C1 is a multiple of C2.
683  if (isMultiple(*C1, *C2, Quotient, IsSigned)) {
684  auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
685  ConstantInt::get(Ty, Quotient));
686  auto *OBO = cast<OverflowingBinaryOperator>(Op0);
687  Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
688  Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
689  return Mul;
690  }
691  }
692 
693  if ((IsSigned && match(Op0, m_NSWShl(m_Value(X), m_APInt(C1))) &&
694  *C1 != C1->getBitWidth() - 1) ||
695  (!IsSigned && match(Op0, m_NUWShl(m_Value(X), m_APInt(C1))))) {
696  APInt Quotient(C1->getBitWidth(), /*val=*/0ULL, IsSigned);
697  APInt C1Shifted = APInt::getOneBitSet(
698  C1->getBitWidth(), static_cast<unsigned>(C1->getLimitedValue()));
699 
700  // (X << C1) / C2 -> X / (C2 >> C1) if C2 is a multiple of 1 << C1.
701  if (isMultiple(*C2, C1Shifted, Quotient, IsSigned)) {
702  auto *BO = BinaryOperator::Create(I.getOpcode(), X,
703  ConstantInt::get(Ty, Quotient));
704  BO->setIsExact(I.isExact());
705  return BO;
706  }
707 
708  // (X << C1) / C2 -> X * ((1 << C1) / C2) if 1 << C1 is a multiple of C2.
709  if (isMultiple(C1Shifted, *C2, Quotient, IsSigned)) {
710  auto *Mul = BinaryOperator::Create(Instruction::Mul, X,
711  ConstantInt::get(Ty, Quotient));
712  auto *OBO = cast<OverflowingBinaryOperator>(Op0);
713  Mul->setHasNoUnsignedWrap(!IsSigned && OBO->hasNoUnsignedWrap());
714  Mul->setHasNoSignedWrap(OBO->hasNoSignedWrap());
715  return Mul;
716  }
717  }
718 
719  if (!C2->isNullValue()) // avoid X udiv 0
720  if (Instruction *FoldedDiv = foldBinOpIntoSelectOrPhi(I))
721  return FoldedDiv;
722  }
723 
724  if (match(Op0, m_One())) {
725  assert(!Ty->isIntOrIntVectorTy(1) && "i1 divide not removed?");
726  if (IsSigned) {
727  // If Op1 is 0 then it's undefined behaviour, if Op1 is 1 then the
728  // result is one, if Op1 is -1 then the result is minus one, otherwise
729  // it's zero.
730  Value *Inc = Builder.CreateAdd(Op1, Op0);
731  Value *Cmp = Builder.CreateICmpULT(Inc, ConstantInt::get(Ty, 3));
732  return SelectInst::Create(Cmp, Op1, ConstantInt::get(Ty, 0));
733  } else {
734  // If Op1 is 0 then it's undefined behaviour. If Op1 is 1 then the
735  // result is one, otherwise it's zero.
736  return new ZExtInst(Builder.CreateICmpEQ(Op1, Op0), Ty);
737  }
738  }
739 
740  // See if we can fold away this div instruction.
741  if (SimplifyDemandedInstructionBits(I))
742  return &I;
743 
744  // (X - (X rem Y)) / Y -> X / Y; usually originates as ((X / Y) * Y) / Y
745  Value *X, *Z;
746  if (match(Op0, m_Sub(m_Value(X), m_Value(Z)))) // (X - Z) / Y; Y = Op1
747  if ((IsSigned && match(Z, m_SRem(m_Specific(X), m_Specific(Op1)))) ||
748  (!IsSigned && match(Z, m_URem(m_Specific(X), m_Specific(Op1)))))
749  return BinaryOperator::Create(I.getOpcode(), X, Op1);
750 
751  // (X << Y) / X -> 1 << Y
752  Value *Y;
753  if (IsSigned && match(Op0, m_NSWShl(m_Specific(Op1), m_Value(Y))))
754  return BinaryOperator::CreateNSWShl(ConstantInt::get(Ty, 1), Y);
755  if (!IsSigned && match(Op0, m_NUWShl(m_Specific(Op1), m_Value(Y))))
756  return BinaryOperator::CreateNUWShl(ConstantInt::get(Ty, 1), Y);
757 
758  // X / (X * Y) -> 1 / Y if the multiplication does not overflow.
759  if (match(Op1, m_c_Mul(m_Specific(Op0), m_Value(Y)))) {
760  bool HasNSW = cast<OverflowingBinaryOperator>(Op1)->hasNoSignedWrap();
761  bool HasNUW = cast<OverflowingBinaryOperator>(Op1)->hasNoUnsignedWrap();
762  if ((IsSigned && HasNSW) || (!IsSigned && HasNUW)) {
763  I.setOperand(0, ConstantInt::get(Ty, 1));
764  I.setOperand(1, Y);
765  return &I;
766  }
767  }
768 
769  return nullptr;
770 }
771 
772 static const unsigned MaxDepth = 6;
773 
774 namespace {
775 
776 using FoldUDivOperandCb = Instruction *(*)(Value *Op0, Value *Op1,
777  const BinaryOperator &I,
778  InstCombiner &IC);
779 
780 /// Used to maintain state for visitUDivOperand().
781 struct UDivFoldAction {
782  /// Informs visitUDiv() how to fold this operand. This can be zero if this
783  /// action joins two actions together.
784  FoldUDivOperandCb FoldAction;
785 
786  /// Which operand to fold.
787  Value *OperandToFold;
788 
789  union {
790  /// The instruction returned when FoldAction is invoked.
791  Instruction *FoldResult;
792 
793  /// Stores the LHS action index if this action joins two actions together.
794  size_t SelectLHSIdx;
795  };
796 
797  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand)
798  : FoldAction(FA), OperandToFold(InputOperand), FoldResult(nullptr) {}
799  UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
800  : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
801 };
802 
803 } // end anonymous namespace
804 
805 // X udiv 2^C -> X >> C
807  const BinaryOperator &I, InstCombiner &IC) {
808  Constant *C1 = getLogBase2(Op0->getType(), cast<Constant>(Op1));
809  if (!C1)
810  llvm_unreachable("Failed to constant fold udiv -> logbase2");
811  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, C1);
812  if (I.isExact())
813  LShr->setIsExact();
814  return LShr;
815 }
816 
817 // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
818 // X udiv (zext (C1 << N)), where C1 is "1<<C2" --> X >> (N+C2)
819 static Instruction *foldUDivShl(Value *Op0, Value *Op1, const BinaryOperator &I,
820  InstCombiner &IC) {
821  Value *ShiftLeft;
822  if (!match(Op1, m_ZExt(m_Value(ShiftLeft))))
823  ShiftLeft = Op1;
824 
825  Constant *CI;
826  Value *N;
827  if (!match(ShiftLeft, m_Shl(m_Constant(CI), m_Value(N))))
828  llvm_unreachable("match should never fail here!");
829  Constant *Log2Base = getLogBase2(N->getType(), CI);
830  if (!Log2Base)
831  llvm_unreachable("getLogBase2 should never fail here!");
832  N = IC.Builder.CreateAdd(N, Log2Base);
833  if (Op1 != ShiftLeft)
834  N = IC.Builder.CreateZExt(N, Op1->getType());
835  BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, N);
836  if (I.isExact())
837  LShr->setIsExact();
838  return LShr;
839 }
840 
841 // Recursively visits the possible right hand operands of a udiv
842 // instruction, seeing through select instructions, to determine if we can
843 // replace the udiv with something simpler. If we find that an operand is not
844 // able to simplify the udiv, we abort the entire transformation.
845 static size_t visitUDivOperand(Value *Op0, Value *Op1, const BinaryOperator &I,
847  unsigned Depth = 0) {
848  // Check to see if this is an unsigned division with an exact power of 2,
849  // if so, convert to a right shift.
850  if (match(Op1, m_Power2())) {
851  Actions.push_back(UDivFoldAction(foldUDivPow2Cst, Op1));
852  return Actions.size();
853  }
854 
855  // X udiv (C1 << N), where C1 is "1<<C2" --> X >> (N+C2)
856  if (match(Op1, m_Shl(m_Power2(), m_Value())) ||
857  match(Op1, m_ZExt(m_Shl(m_Power2(), m_Value())))) {
858  Actions.push_back(UDivFoldAction(foldUDivShl, Op1));
859  return Actions.size();
860  }
861 
862  // The remaining tests are all recursive, so bail out if we hit the limit.
863  if (Depth++ == MaxDepth)
864  return 0;
865 
866  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
867  if (size_t LHSIdx =
868  visitUDivOperand(Op0, SI->getOperand(1), I, Actions, Depth))
869  if (visitUDivOperand(Op0, SI->getOperand(2), I, Actions, Depth)) {
870  Actions.push_back(UDivFoldAction(nullptr, Op1, LHSIdx - 1));
871  return Actions.size();
872  }
873 
874  return 0;
875 }
876 
877 /// If we have zero-extended operands of an unsigned div or rem, we may be able
878 /// to narrow the operation (sink the zext below the math).
880  InstCombiner::BuilderTy &Builder) {
881  Instruction::BinaryOps Opcode = I.getOpcode();
882  Value *N = I.getOperand(0);
883  Value *D = I.getOperand(1);
884  Type *Ty = I.getType();
885  Value *X, *Y;
886  if (match(N, m_ZExt(m_Value(X))) && match(D, m_ZExt(m_Value(Y))) &&
887  X->getType() == Y->getType() && (N->hasOneUse() || D->hasOneUse())) {
888  // udiv (zext X), (zext Y) --> zext (udiv X, Y)
889  // urem (zext X), (zext Y) --> zext (urem X, Y)
890  Value *NarrowOp = Builder.CreateBinOp(Opcode, X, Y);
891  return new ZExtInst(NarrowOp, Ty);
892  }
893 
894  Constant *C;
895  if ((match(N, m_OneUse(m_ZExt(m_Value(X)))) && match(D, m_Constant(C))) ||
896  (match(D, m_OneUse(m_ZExt(m_Value(X)))) && match(N, m_Constant(C)))) {
897  // If the constant is the same in the smaller type, use the narrow version.
898  Constant *TruncC = ConstantExpr::getTrunc(C, X->getType());
899  if (ConstantExpr::getZExt(TruncC, Ty) != C)
900  return nullptr;
901 
902  // udiv (zext X), C --> zext (udiv X, C')
903  // urem (zext X), C --> zext (urem X, C')
904  // udiv C, (zext X) --> zext (udiv C', X)
905  // urem C, (zext X) --> zext (urem C', X)
906  Value *NarrowOp = isa<Constant>(D) ? Builder.CreateBinOp(Opcode, X, TruncC)
907  : Builder.CreateBinOp(Opcode, TruncC, X);
908  return new ZExtInst(NarrowOp, Ty);
909  }
910 
911  return nullptr;
912 }
913 
915  if (Value *V = SimplifyUDivInst(I.getOperand(0), I.getOperand(1),
916  SQ.getWithInstruction(&I)))
917  return replaceInstUsesWith(I, V);
918 
919  if (Instruction *X = foldVectorBinop(I))
920  return X;
921 
922  // Handle the integer div common cases
923  if (Instruction *Common = commonIDivTransforms(I))
924  return Common;
925 
926  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
927  Value *X;
928  const APInt *C1, *C2;
929  if (match(Op0, m_LShr(m_Value(X), m_APInt(C1))) && match(Op1, m_APInt(C2))) {
930  // (X lshr C1) udiv C2 --> X udiv (C2 << C1)
931  bool Overflow;
932  APInt C2ShlC1 = C2->ushl_ov(*C1, Overflow);
933  if (!Overflow) {
934  bool IsExact = I.isExact() && match(Op0, m_Exact(m_Value()));
935  BinaryOperator *BO = BinaryOperator::CreateUDiv(
936  X, ConstantInt::get(X->getType(), C2ShlC1));
937  if (IsExact)
938  BO->setIsExact();
939  return BO;
940  }
941  }
942 
943  // Op0 / C where C is large (negative) --> zext (Op0 >= C)
944  // TODO: Could use isKnownNegative() to handle non-constant values.
945  Type *Ty = I.getType();
946  if (match(Op1, m_Negative())) {
947  Value *Cmp = Builder.CreateICmpUGE(Op0, Op1);
948  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
949  }
950  // Op0 / (sext i1 X) --> zext (Op0 == -1) (if X is 0, the div is undefined)
951  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
952  Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
953  return CastInst::CreateZExtOrBitCast(Cmp, Ty);
954  }
955 
956  if (Instruction *NarrowDiv = narrowUDivURem(I, Builder))
957  return NarrowDiv;
958 
959  // If the udiv operands are non-overflowing multiplies with a common operand,
960  // then eliminate the common factor:
961  // (A * B) / (A * X) --> B / X (and commuted variants)
962  // TODO: The code would be reduced if we had m_c_NUWMul pattern matching.
963  // TODO: If -reassociation handled this generally, we could remove this.
964  Value *A, *B;
965  if (match(Op0, m_NUWMul(m_Value(A), m_Value(B)))) {
966  if (match(Op1, m_NUWMul(m_Specific(A), m_Value(X))) ||
967  match(Op1, m_NUWMul(m_Value(X), m_Specific(A))))
968  return BinaryOperator::CreateUDiv(B, X);
969  if (match(Op1, m_NUWMul(m_Specific(B), m_Value(X))) ||
970  match(Op1, m_NUWMul(m_Value(X), m_Specific(B))))
971  return BinaryOperator::CreateUDiv(A, X);
972  }
973 
974  // (LHS udiv (select (select (...)))) -> (LHS >> (select (select (...))))
975  SmallVector<UDivFoldAction, 6> UDivActions;
976  if (visitUDivOperand(Op0, Op1, I, UDivActions))
977  for (unsigned i = 0, e = UDivActions.size(); i != e; ++i) {
978  FoldUDivOperandCb Action = UDivActions[i].FoldAction;
979  Value *ActionOp1 = UDivActions[i].OperandToFold;
980  Instruction *Inst;
981  if (Action)
982  Inst = Action(Op0, ActionOp1, I, *this);
983  else {
984  // This action joins two actions together. The RHS of this action is
985  // simply the last action we processed, we saved the LHS action index in
986  // the joining action.
987  size_t SelectRHSIdx = i - 1;
988  Value *SelectRHS = UDivActions[SelectRHSIdx].FoldResult;
989  size_t SelectLHSIdx = UDivActions[i].SelectLHSIdx;
990  Value *SelectLHS = UDivActions[SelectLHSIdx].FoldResult;
991  Inst = SelectInst::Create(cast<SelectInst>(ActionOp1)->getCondition(),
992  SelectLHS, SelectRHS);
993  }
994 
995  // If this is the last action to process, return it to the InstCombiner.
996  // Otherwise, we insert it before the UDiv and record it so that we may
997  // use it as part of a joining action (i.e., a SelectInst).
998  if (e - i != 1) {
999  Inst->insertBefore(&I);
1000  UDivActions[i].FoldResult = Inst;
1001  } else
1002  return Inst;
1003  }
1004 
1005  return nullptr;
1006 }
1007 
1009  if (Value *V = SimplifySDivInst(I.getOperand(0), I.getOperand(1),
1010  SQ.getWithInstruction(&I)))
1011  return replaceInstUsesWith(I, V);
1012 
1013  if (Instruction *X = foldVectorBinop(I))
1014  return X;
1015 
1016  // Handle the integer div common cases
1017  if (Instruction *Common = commonIDivTransforms(I))
1018  return Common;
1019 
1020  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1021  Value *X;
1022  // sdiv Op0, -1 --> -Op0
1023  // sdiv Op0, (sext i1 X) --> -Op0 (because if X is 0, the op is undefined)
1024  if (match(Op1, m_AllOnes()) ||
1025  (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
1026  return BinaryOperator::CreateNeg(Op0);
1027 
1028  // X / INT_MIN --> X == INT_MIN
1029  if (match(Op1, m_SignMask()))
1030  return new ZExtInst(Builder.CreateICmpEQ(Op0, Op1), I.getType());
1031 
1032  const APInt *Op1C;
1033  if (match(Op1, m_APInt(Op1C))) {
1034  // sdiv exact X, C --> ashr exact X, log2(C)
1035  if (I.isExact() && Op1C->isNonNegative() && Op1C->isPowerOf2()) {
1036  Value *ShAmt = ConstantInt::get(Op1->getType(), Op1C->exactLogBase2());
1037  return BinaryOperator::CreateExactAShr(Op0, ShAmt, I.getName());
1038  }
1039 
1040  // If the dividend is sign-extended and the constant divisor is small enough
1041  // to fit in the source type, shrink the division to the narrower type:
1042  // (sext X) sdiv C --> sext (X sdiv C)
1043  Value *Op0Src;
1044  if (match(Op0, m_OneUse(m_SExt(m_Value(Op0Src)))) &&
1045  Op0Src->getType()->getScalarSizeInBits() >= Op1C->getMinSignedBits()) {
1046 
1047  // In the general case, we need to make sure that the dividend is not the
1048  // minimum signed value because dividing that by -1 is UB. But here, we
1049  // know that the -1 divisor case is already handled above.
1050 
1051  Constant *NarrowDivisor =
1052  ConstantExpr::getTrunc(cast<Constant>(Op1), Op0Src->getType());
1053  Value *NarrowOp = Builder.CreateSDiv(Op0Src, NarrowDivisor);
1054  return new SExtInst(NarrowOp, Op0->getType());
1055  }
1056 
1057  // -X / C --> X / -C (if the negation doesn't overflow).
1058  // TODO: This could be enhanced to handle arbitrary vector constants by
1059  // checking if all elements are not the min-signed-val.
1060  if (!Op1C->isMinSignedValue() &&
1061  match(Op0, m_NSWSub(m_Zero(), m_Value(X)))) {
1062  Constant *NegC = ConstantInt::get(I.getType(), -(*Op1C));
1063  Instruction *BO = BinaryOperator::CreateSDiv(X, NegC);
1064  BO->setIsExact(I.isExact());
1065  return BO;
1066  }
1067  }
1068 
1069  // -X / Y --> -(X / Y)
1070  Value *Y;
1071  if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1073  Builder.CreateSDiv(X, Y, I.getName(), I.isExact()));
1074 
1075  // If the sign bits of both operands are zero (i.e. we can prove they are
1076  // unsigned inputs), turn this into a udiv.
1078  if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
1079  if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
1080  // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
1081  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1082  BO->setIsExact(I.isExact());
1083  return BO;
1084  }
1085 
1086  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1087  // X sdiv (1 << Y) -> X udiv (1 << Y) ( -> X u>> Y)
1088  // Safe because the only negative value (1 << Y) can take on is
1089  // INT_MIN, and X sdiv INT_MIN == X udiv INT_MIN == 0 if X doesn't have
1090  // the sign bit set.
1091  auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
1092  BO->setIsExact(I.isExact());
1093  return BO;
1094  }
1095  }
1096 
1097  return nullptr;
1098 }
1099 
1100 /// Remove negation and try to convert division into multiplication.
1102  Constant *C;
1103  if (!match(I.getOperand(1), m_Constant(C)))
1104  return nullptr;
1105 
1106  // -X / C --> X / -C
1107  Value *X;
1108  if (match(I.getOperand(0), m_FNeg(m_Value(X))))
1110 
1111  // If the constant divisor has an exact inverse, this is always safe. If not,
1112  // then we can still create a reciprocal if fast-math-flags allow it and the
1113  // constant is a regular number (not zero, infinite, or denormal).
1114  if (!(C->hasExactInverseFP() || (I.hasAllowReciprocal() && C->isNormalFP())))
1115  return nullptr;
1116 
1117  // Disallow denormal constants because we don't know what would happen
1118  // on all targets.
1119  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1120  // denorms are flushed?
1121  auto *RecipC = ConstantExpr::getFDiv(ConstantFP::get(I.getType(), 1.0), C);
1122  if (!RecipC->isNormalFP())
1123  return nullptr;
1124 
1125  // X / C --> X * (1 / C)
1126  return BinaryOperator::CreateFMulFMF(I.getOperand(0), RecipC, &I);
1127 }
1128 
1129 /// Remove negation and try to reassociate constant math.
1131  Constant *C;
1132  if (!match(I.getOperand(0), m_Constant(C)))
1133  return nullptr;
1134 
1135  // C / -X --> -C / X
1136  Value *X;
1137  if (match(I.getOperand(1), m_FNeg(m_Value(X))))
1139 
1140  if (!I.hasAllowReassoc() || !I.hasAllowReciprocal())
1141  return nullptr;
1142 
1143  // Try to reassociate C / X expressions where X includes another constant.
1144  Constant *C2, *NewC = nullptr;
1145  if (match(I.getOperand(1), m_FMul(m_Value(X), m_Constant(C2)))) {
1146  // C / (X * C2) --> (C / C2) / X
1147  NewC = ConstantExpr::getFDiv(C, C2);
1148  } else if (match(I.getOperand(1), m_FDiv(m_Value(X), m_Constant(C2)))) {
1149  // C / (X / C2) --> (C * C2) / X
1150  NewC = ConstantExpr::getFMul(C, C2);
1151  }
1152  // Disallow denormal constants because we don't know what would happen
1153  // on all targets.
1154  // TODO: Use Intrinsic::canonicalize or let function attributes tell us that
1155  // denorms are flushed?
1156  if (!NewC || !NewC->isNormalFP())
1157  return nullptr;
1158 
1159  return BinaryOperator::CreateFDivFMF(NewC, X, &I);
1160 }
1161 
1163  if (Value *V = SimplifyFDivInst(I.getOperand(0), I.getOperand(1),
1164  I.getFastMathFlags(),
1165  SQ.getWithInstruction(&I)))
1166  return replaceInstUsesWith(I, V);
1167 
1168  if (Instruction *X = foldVectorBinop(I))
1169  return X;
1170 
1172  return R;
1173 
1175  return R;
1176 
1177  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1178  if (isa<Constant>(Op0))
1179  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1180  if (Instruction *R = FoldOpIntoSelect(I, SI))
1181  return R;
1182 
1183  if (isa<Constant>(Op1))
1184  if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1185  if (Instruction *R = FoldOpIntoSelect(I, SI))
1186  return R;
1187 
1188  if (I.hasAllowReassoc() && I.hasAllowReciprocal()) {
1189  Value *X, *Y;
1190  if (match(Op0, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1191  (!isa<Constant>(Y) || !isa<Constant>(Op1))) {
1192  // (X / Y) / Z => X / (Y * Z)
1193  Value *YZ = Builder.CreateFMulFMF(Y, Op1, &I);
1194  return BinaryOperator::CreateFDivFMF(X, YZ, &I);
1195  }
1196  if (match(Op1, m_OneUse(m_FDiv(m_Value(X), m_Value(Y)))) &&
1197  (!isa<Constant>(Y) || !isa<Constant>(Op0))) {
1198  // Z / (X / Y) => (Y * Z) / X
1199  Value *YZ = Builder.CreateFMulFMF(Y, Op0, &I);
1200  return BinaryOperator::CreateFDivFMF(YZ, X, &I);
1201  }
1202  }
1203 
1204  if (I.hasAllowReassoc() && Op0->hasOneUse() && Op1->hasOneUse()) {
1205  // sin(X) / cos(X) -> tan(X)
1206  // cos(X) / sin(X) -> 1/tan(X) (cotangent)
1207  Value *X;
1208  bool IsTan = match(Op0, m_Intrinsic<Intrinsic::sin>(m_Value(X))) &&
1209  match(Op1, m_Intrinsic<Intrinsic::cos>(m_Specific(X)));
1210  bool IsCot =
1211  !IsTan && match(Op0, m_Intrinsic<Intrinsic::cos>(m_Value(X))) &&
1212  match(Op1, m_Intrinsic<Intrinsic::sin>(m_Specific(X)));
1213 
1214  if ((IsTan || IsCot) && hasUnaryFloatFn(&TLI, I.getType(), LibFunc_tan,
1215  LibFunc_tanf, LibFunc_tanl)) {
1216  IRBuilder<> B(&I);
1217  IRBuilder<>::FastMathFlagGuard FMFGuard(B);
1220  cast<CallBase>(Op0)->getCalledFunction()->getAttributes();
1221  Value *Res = emitUnaryFloatFnCall(X, &TLI, LibFunc_tan, LibFunc_tanf,
1222  LibFunc_tanl, B, Attrs);
1223  if (IsCot)
1224  Res = B.CreateFDiv(ConstantFP::get(I.getType(), 1.0), Res);
1225  return replaceInstUsesWith(I, Res);
1226  }
1227  }
1228 
1229  // -X / -Y -> X / Y
1230  Value *X, *Y;
1231  if (match(Op0, m_FNeg(m_Value(X))) && match(Op1, m_FNeg(m_Value(Y)))) {
1232  I.setOperand(0, X);
1233  I.setOperand(1, Y);
1234  return &I;
1235  }
1236 
1237  // X / (X * Y) --> 1.0 / Y
1238  // Reassociate to (X / X -> 1.0) is legal when NaNs are not allowed.
1239  // We can ignore the possibility that X is infinity because INF/INF is NaN.
1240  if (I.hasNoNaNs() && I.hasAllowReassoc() &&
1241  match(Op1, m_c_FMul(m_Specific(Op0), m_Value(Y)))) {
1242  I.setOperand(0, ConstantFP::get(I.getType(), 1.0));
1243  I.setOperand(1, Y);
1244  return &I;
1245  }
1246 
1247  return nullptr;
1248 }
1249 
1250 /// This function implements the transforms common to both integer remainder
1251 /// instructions (urem and srem). It is called by the visitors to those integer
1252 /// remainder instructions.
1253 /// Common integer remainder transforms
1255  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1256 
1257  // The RHS is known non-zero.
1258  if (Value *V = simplifyValueKnownNonZero(I.getOperand(1), *this, I)) {
1259  I.setOperand(1, V);
1260  return &I;
1261  }
1262 
1263  // Handle cases involving: rem X, (select Cond, Y, Z)
1264  if (simplifyDivRemOfSelectWithZeroOp(I))
1265  return &I;
1266 
1267  if (isa<Constant>(Op1)) {
1268  if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1269  if (SelectInst *SI = dyn_cast<SelectInst>(Op0I)) {
1270  if (Instruction *R = FoldOpIntoSelect(I, SI))
1271  return R;
1272  } else if (auto *PN = dyn_cast<PHINode>(Op0I)) {
1273  const APInt *Op1Int;
1274  if (match(Op1, m_APInt(Op1Int)) && !Op1Int->isMinValue() &&
1275  (I.getOpcode() == Instruction::URem ||
1276  !Op1Int->isMinSignedValue())) {
1277  // foldOpIntoPhi will speculate instructions to the end of the PHI's
1278  // predecessor blocks, so do this only if we know the srem or urem
1279  // will not fault.
1280  if (Instruction *NV = foldOpIntoPhi(I, PN))
1281  return NV;
1282  }
1283  }
1284 
1285  // See if we can fold away this rem instruction.
1286  if (SimplifyDemandedInstructionBits(I))
1287  return &I;
1288  }
1289  }
1290 
1291  return nullptr;
1292 }
1293 
1295  if (Value *V = SimplifyURemInst(I.getOperand(0), I.getOperand(1),
1296  SQ.getWithInstruction(&I)))
1297  return replaceInstUsesWith(I, V);
1298 
1299  if (Instruction *X = foldVectorBinop(I))
1300  return X;
1301 
1302  if (Instruction *common = commonIRemTransforms(I))
1303  return common;
1304 
1305  if (Instruction *NarrowRem = narrowUDivURem(I, Builder))
1306  return NarrowRem;
1307 
1308  // X urem Y -> X and Y-1, where Y is a power of 2,
1309  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1310  Type *Ty = I.getType();
1311  if (isKnownToBeAPowerOfTwo(Op1, /*OrZero*/ true, 0, &I)) {
1313  Value *Add = Builder.CreateAdd(Op1, N1);
1314  return BinaryOperator::CreateAnd(Op0, Add);
1315  }
1316 
1317  // 1 urem X -> zext(X != 1)
1318  if (match(Op0, m_One()))
1319  return CastInst::CreateZExtOrBitCast(Builder.CreateICmpNE(Op1, Op0), Ty);
1320 
1321  // X urem C -> X < C ? X : X - C, where C >= signbit.
1322  if (match(Op1, m_Negative())) {
1323  Value *Cmp = Builder.CreateICmpULT(Op0, Op1);
1324  Value *Sub = Builder.CreateSub(Op0, Op1);
1325  return SelectInst::Create(Cmp, Op0, Sub);
1326  }
1327 
1328  // If the divisor is a sext of a boolean, then the divisor must be max
1329  // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also
1330  // max unsigned value. In that case, the remainder is 0:
1331  // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0
1332  Value *X;
1333  if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1334  Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
1335  return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), Op0);
1336  }
1337 
1338  return nullptr;
1339 }
1340 
1342  if (Value *V = SimplifySRemInst(I.getOperand(0), I.getOperand(1),
1343  SQ.getWithInstruction(&I)))
1344  return replaceInstUsesWith(I, V);
1345 
1346  if (Instruction *X = foldVectorBinop(I))
1347  return X;
1348 
1349  // Handle the integer rem common cases
1350  if (Instruction *Common = commonIRemTransforms(I))
1351  return Common;
1352 
1353  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1354  {
1355  const APInt *Y;
1356  // X % -Y -> X % Y
1357  if (match(Op1, m_Negative(Y)) && !Y->isMinSignedValue()) {
1358  Worklist.AddValue(I.getOperand(1));
1359  I.setOperand(1, ConstantInt::get(I.getType(), -*Y));
1360  return &I;
1361  }
1362  }
1363 
1364  // -X srem Y --> -(X srem Y)
1365  Value *X, *Y;
1366  if (match(&I, m_SRem(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
1367  return BinaryOperator::CreateNSWNeg(Builder.CreateSRem(X, Y));
1368 
1369  // If the sign bits of both operands are zero (i.e. we can prove they are
1370  // unsigned inputs), turn this into a urem.
1372  if (MaskedValueIsZero(Op1, Mask, 0, &I) &&
1373  MaskedValueIsZero(Op0, Mask, 0, &I)) {
1374  // X srem Y -> X urem Y, iff X and Y don't have sign bit set
1375  return BinaryOperator::CreateURem(Op0, Op1, I.getName());
1376  }
1377 
1378  // If it's a constant vector, flip any negative values positive.
1379  if (isa<ConstantVector>(Op1) || isa<ConstantDataVector>(Op1)) {
1380  Constant *C = cast<Constant>(Op1);
1381  unsigned VWidth = C->getType()->getVectorNumElements();
1382 
1383  bool hasNegative = false;
1384  bool hasMissing = false;
1385  for (unsigned i = 0; i != VWidth; ++i) {
1386  Constant *Elt = C->getAggregateElement(i);
1387  if (!Elt) {
1388  hasMissing = true;
1389  break;
1390  }
1391 
1392  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elt))
1393  if (RHS->isNegative())
1394  hasNegative = true;
1395  }
1396 
1397  if (hasNegative && !hasMissing) {
1398  SmallVector<Constant *, 16> Elts(VWidth);
1399  for (unsigned i = 0; i != VWidth; ++i) {
1400  Elts[i] = C->getAggregateElement(i); // Handle undef, etc.
1401  if (ConstantInt *RHS = dyn_cast<ConstantInt>(Elts[i])) {
1402  if (RHS->isNegative())
1403  Elts[i] = cast<ConstantInt>(ConstantExpr::getNeg(RHS));
1404  }
1405  }
1406 
1407  Constant *NewRHSV = ConstantVector::get(Elts);
1408  if (NewRHSV != C) { // Don't loop on -MININT
1409  Worklist.AddValue(I.getOperand(1));
1410  I.setOperand(1, NewRHSV);
1411  return &I;
1412  }
1413  }
1414  }
1415 
1416  return nullptr;
1417 }
1418 
1420  if (Value *V = SimplifyFRemInst(I.getOperand(0), I.getOperand(1),
1421  I.getFastMathFlags(),
1422  SQ.getWithInstruction(&I)))
1423  return replaceInstUsesWith(I, V);
1424 
1425  if (Instruction *X = foldVectorBinop(I))
1426  return X;
1427 
1428  return nullptr;
1429 }
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:867
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:1458
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:693
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:402
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:687
BinaryOp_match< LHS, RHS, Instruction::FDiv > m_FDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:772
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:784
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:748
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:1841
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:1951
void setArgOperand(unsigned i, Value *v)
Definition: InstrTypes.h:1246
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:699
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:579
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)
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:1118
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:681
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:268
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:1135
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:1878
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:908
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:820
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:766
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:916
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:541
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:814
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
static bool hasNoUnsignedWrap(BinaryOperator &I)
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:837
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:778
BinaryOp_match< LHS, RHS, Instruction::UDiv > m_UDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:760
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:754
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:535
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:1207
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:273
static BinaryOperator * CreateFNegFMF(Value *Op, Instruction *FMFSource, const Twine &Name="")
Definition: InstrTypes.h:283
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:736
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:1911
#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:883
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:258
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:1408
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:1921
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:1709
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:875
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:225
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:263
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