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