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