LLVM  10.0.0svn
InstCombineShifts.cpp
Go to the documentation of this file.
1 //===- InstCombineShifts.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 visitShl, visitLShr, and visitAShr functions.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "InstCombineInternal.h"
16 #include "llvm/IR/IntrinsicInst.h"
17 #include "llvm/IR/PatternMatch.h"
18 using namespace llvm;
19 using namespace PatternMatch;
20 
21 #define DEBUG_TYPE "instcombine"
22 
23 // Given pattern:
24 // (x shiftopcode Q) shiftopcode K
25 // we should rewrite it as
26 // x shiftopcode (Q+K) iff (Q+K) u< bitwidth(x)
27 // This is valid for any shift, but they must be identical.
28 //
29 // AnalyzeForSignBitExtraction indicates that we will only analyze whether this
30 // pattern has any 2 right-shifts that sum to 1 less than original bit width.
32  BinaryOperator *Sh0, const SimplifyQuery &SQ,
33  bool AnalyzeForSignBitExtraction) {
34  // Look for a shift of some instruction, ignore zext of shift amount if any.
35  Instruction *Sh0Op0;
36  Value *ShAmt0;
37  if (!match(Sh0,
38  m_Shift(m_Instruction(Sh0Op0), m_ZExtOrSelf(m_Value(ShAmt0)))))
39  return nullptr;
40 
41  // If there is a truncation between the two shifts, we must make note of it
42  // and look through it. The truncation imposes additional constraints on the
43  // transform.
44  Instruction *Sh1;
45  Value *Trunc = nullptr;
46  match(Sh0Op0,
48  m_Instruction(Sh1)));
49 
50  // Inner shift: (x shiftopcode ShAmt1)
51  // Like with other shift, ignore zext of shift amount if any.
52  Value *X, *ShAmt1;
53  if (!match(Sh1, m_Shift(m_Value(X), m_ZExtOrSelf(m_Value(ShAmt1)))))
54  return nullptr;
55 
56  // We have two shift amounts from two different shifts. The types of those
57  // shift amounts may not match. If that's the case let's bailout now..
58  if (ShAmt0->getType() != ShAmt1->getType())
59  return nullptr;
60 
61  // We are only looking for signbit extraction if we have two right shifts.
62  bool HadTwoRightShifts = match(Sh0, m_Shr(m_Value(), m_Value())) &&
63  match(Sh1, m_Shr(m_Value(), m_Value()));
64  // ... and if it's not two right-shifts, we know the answer already.
65  if (AnalyzeForSignBitExtraction && !HadTwoRightShifts)
66  return nullptr;
67 
68  // The shift opcodes must be identical, unless we are just checking whether
69  // this pattern can be interpreted as a sign-bit-extraction.
70  Instruction::BinaryOps ShiftOpcode = Sh0->getOpcode();
71  bool IdenticalShOpcodes = Sh0->getOpcode() == Sh1->getOpcode();
72  if (!IdenticalShOpcodes && !AnalyzeForSignBitExtraction)
73  return nullptr;
74 
75  // If we saw truncation, we'll need to produce extra instruction,
76  // and for that one of the operands of the shift must be one-use,
77  // unless of course we don't actually plan to produce any instructions here.
78  if (Trunc && !AnalyzeForSignBitExtraction &&
79  !match(Sh0, m_c_BinOp(m_OneUse(m_Value()), m_Value())))
80  return nullptr;
81 
82  // Can we fold (ShAmt0+ShAmt1) ?
83  auto *NewShAmt = dyn_cast_or_null<Constant>(
84  SimplifyAddInst(ShAmt0, ShAmt1, /*isNSW=*/false, /*isNUW=*/false,
85  SQ.getWithInstruction(Sh0)));
86  if (!NewShAmt)
87  return nullptr; // Did not simplify.
88  unsigned NewShAmtBitWidth = NewShAmt->getType()->getScalarSizeInBits();
89  unsigned XBitWidth = X->getType()->getScalarSizeInBits();
90  // Is the new shift amount smaller than the bit width of inner/new shift?
91  if (!match(NewShAmt, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT,
92  APInt(NewShAmtBitWidth, XBitWidth))))
93  return nullptr; // FIXME: could perform constant-folding.
94 
95  // If there was a truncation, and we have a right-shift, we can only fold if
96  // we are left with the original sign bit. Likewise, if we were just checking
97  // that this is a sighbit extraction, this is the place to check it.
98  // FIXME: zero shift amount is also legal here, but we can't *easily* check
99  // more than one predicate so it's not really worth it.
100  if (HadTwoRightShifts && (Trunc || AnalyzeForSignBitExtraction)) {
101  // If it's not a sign bit extraction, then we're done.
102  if (!match(NewShAmt,
103  m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ,
104  APInt(NewShAmtBitWidth, XBitWidth - 1))))
105  return nullptr;
106  // If it is, and that was the question, return the base value.
107  if (AnalyzeForSignBitExtraction)
108  return X;
109  }
110 
111  assert(IdenticalShOpcodes && "Should not get here with different shifts.");
112 
113  // All good, we can do this fold.
114  NewShAmt = ConstantExpr::getZExtOrBitCast(NewShAmt, X->getType());
115 
116  BinaryOperator *NewShift = BinaryOperator::Create(ShiftOpcode, X, NewShAmt);
117 
118  // The flags can only be propagated if there wasn't a trunc.
119  if (!Trunc) {
120  // If the pattern did not involve trunc, and both of the original shifts
121  // had the same flag set, preserve the flag.
122  if (ShiftOpcode == Instruction::BinaryOps::Shl) {
123  NewShift->setHasNoUnsignedWrap(Sh0->hasNoUnsignedWrap() &&
124  Sh1->hasNoUnsignedWrap());
125  NewShift->setHasNoSignedWrap(Sh0->hasNoSignedWrap() &&
126  Sh1->hasNoSignedWrap());
127  } else {
128  NewShift->setIsExact(Sh0->isExact() && Sh1->isExact());
129  }
130  }
131 
132  Instruction *Ret = NewShift;
133  if (Trunc) {
134  Builder.Insert(NewShift);
135  Ret = CastInst::Create(Instruction::Trunc, NewShift, Sh0->getType());
136  }
137 
138  return Ret;
139 }
140 
141 // Try to replace `undef` constants in C with Replacement.
142 static Constant *replaceUndefsWith(Constant *C, Constant *Replacement) {
143  if (C && match(C, m_Undef()))
144  return Replacement;
145 
146  if (auto *CV = dyn_cast<ConstantVector>(C)) {
147  llvm::SmallVector<Constant *, 32> NewOps(CV->getNumOperands());
148  for (unsigned i = 0, NumElts = NewOps.size(); i != NumElts; ++i) {
149  Constant *EltC = CV->getOperand(i);
150  NewOps[i] = EltC && match(EltC, m_Undef()) ? Replacement : EltC;
151  }
152  return ConstantVector::get(NewOps);
153  }
154 
155  // Don't know how to deal with this constant.
156  return C;
157 }
158 
159 // If we have some pattern that leaves only some low bits set, and then performs
160 // left-shift of those bits, if none of the bits that are left after the final
161 // shift are modified by the mask, we can omit the mask.
162 //
163 // There are many variants to this pattern:
164 // a) (x & ((1 << MaskShAmt) - 1)) << ShiftShAmt
165 // b) (x & (~(-1 << MaskShAmt))) << ShiftShAmt
166 // c) (x & (-1 >> MaskShAmt)) << ShiftShAmt
167 // d) (x & ((-1 << MaskShAmt) >> MaskShAmt)) << ShiftShAmt
168 // e) ((x << MaskShAmt) l>> MaskShAmt) << ShiftShAmt
169 // f) ((x << MaskShAmt) a>> MaskShAmt) << ShiftShAmt
170 // All these patterns can be simplified to just:
171 // x << ShiftShAmt
172 // iff:
173 // a,b) (MaskShAmt+ShiftShAmt) u>= bitwidth(x)
174 // c,d,e,f) (ShiftShAmt-MaskShAmt) s>= 0 (i.e. ShiftShAmt u>= MaskShAmt)
175 static Instruction *
177  const SimplifyQuery &Q,
178  InstCombiner::BuilderTy &Builder) {
179  assert(OuterShift->getOpcode() == Instruction::BinaryOps::Shl &&
180  "The input must be 'shl'!");
181 
182  Value *Masked, *ShiftShAmt;
183  match(OuterShift, m_Shift(m_Value(Masked), m_Value(ShiftShAmt)));
184 
185  Type *NarrowestTy = OuterShift->getType();
186  Type *WidestTy = Masked->getType();
187  // The mask must be computed in a type twice as wide to ensure
188  // that no bits are lost if the sum-of-shifts is wider than the base type.
189  Type *ExtendedTy = WidestTy->getExtendedType();
190 
191  Value *MaskShAmt;
192 
193  // ((1 << MaskShAmt) - 1)
194  auto MaskA = m_Add(m_Shl(m_One(), m_Value(MaskShAmt)), m_AllOnes());
195  // (~(-1 << maskNbits))
196  auto MaskB = m_Xor(m_Shl(m_AllOnes(), m_Value(MaskShAmt)), m_AllOnes());
197  // (-1 >> MaskShAmt)
198  auto MaskC = m_Shr(m_AllOnes(), m_Value(MaskShAmt));
199  // ((-1 << MaskShAmt) >> MaskShAmt)
200  auto MaskD =
201  m_Shr(m_Shl(m_AllOnes(), m_Value(MaskShAmt)), m_Deferred(MaskShAmt));
202 
203  Value *X;
204  Constant *NewMask;
205 
206  if (match(Masked, m_c_And(m_CombineOr(MaskA, MaskB), m_Value(X)))) {
207  // Can we simplify (MaskShAmt+ShiftShAmt) ?
208  auto *SumOfShAmts = dyn_cast_or_null<Constant>(SimplifyAddInst(
209  MaskShAmt, ShiftShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q));
210  if (!SumOfShAmts)
211  return nullptr; // Did not simplify.
212  // In this pattern SumOfShAmts correlates with the number of low bits
213  // that shall remain in the root value (OuterShift).
214 
215  // An extend of an undef value becomes zero because the high bits are never
216  // completely unknown. Replace the the `undef` shift amounts with final
217  // shift bitwidth to ensure that the value remains undef when creating the
218  // subsequent shift op.
219  SumOfShAmts = replaceUndefsWith(
220  SumOfShAmts, ConstantInt::get(SumOfShAmts->getType()->getScalarType(),
221  ExtendedTy->getScalarSizeInBits()));
222  auto *ExtendedSumOfShAmts = ConstantExpr::getZExt(SumOfShAmts, ExtendedTy);
223  // And compute the mask as usual: ~(-1 << (SumOfShAmts))
224  auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy);
225  auto *ExtendedInvertedMask =
226  ConstantExpr::getShl(ExtendedAllOnes, ExtendedSumOfShAmts);
227  NewMask = ConstantExpr::getNot(ExtendedInvertedMask);
228  } else if (match(Masked, m_c_And(m_CombineOr(MaskC, MaskD), m_Value(X))) ||
229  match(Masked, m_Shr(m_Shl(m_Value(X), m_Value(MaskShAmt)),
230  m_Deferred(MaskShAmt)))) {
231  // Can we simplify (ShiftShAmt-MaskShAmt) ?
232  auto *ShAmtsDiff = dyn_cast_or_null<Constant>(SimplifySubInst(
233  ShiftShAmt, MaskShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q));
234  if (!ShAmtsDiff)
235  return nullptr; // Did not simplify.
236  // In this pattern ShAmtsDiff correlates with the number of high bits that
237  // shall be unset in the root value (OuterShift).
238 
239  // An extend of an undef value becomes zero because the high bits are never
240  // completely unknown. Replace the the `undef` shift amounts with negated
241  // bitwidth of innermost shift to ensure that the value remains undef when
242  // creating the subsequent shift op.
243  unsigned WidestTyBitWidth = WidestTy->getScalarSizeInBits();
244  ShAmtsDiff = replaceUndefsWith(
245  ShAmtsDiff, ConstantInt::get(ShAmtsDiff->getType()->getScalarType(),
246  -WidestTyBitWidth));
247  auto *ExtendedNumHighBitsToClear = ConstantExpr::getZExt(
248  ConstantExpr::getSub(ConstantInt::get(ShAmtsDiff->getType(),
249  WidestTyBitWidth,
250  /*isSigned=*/false),
251  ShAmtsDiff),
252  ExtendedTy);
253  // And compute the mask as usual: (-1 l>> (NumHighBitsToClear))
254  auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy);
255  NewMask =
256  ConstantExpr::getLShr(ExtendedAllOnes, ExtendedNumHighBitsToClear);
257  } else
258  return nullptr; // Don't know anything about this pattern.
259 
260  NewMask = ConstantExpr::getTrunc(NewMask, NarrowestTy);
261 
262  // Does this mask has any unset bits? If not then we can just not apply it.
263  bool NeedMask = !match(NewMask, m_AllOnes());
264 
265  // If we need to apply a mask, there are several more restrictions we have.
266  if (NeedMask) {
267  // The old masking instruction must go away.
268  if (!Masked->hasOneUse())
269  return nullptr;
270  // The original "masking" instruction must not have been`ashr`.
271  if (match(Masked, m_AShr(m_Value(), m_Value())))
272  return nullptr;
273  }
274 
275  // No 'NUW'/'NSW'! We no longer know that we won't shift-out non-0 bits.
276  auto *NewShift = BinaryOperator::Create(OuterShift->getOpcode(), X,
277  OuterShift->getOperand(1));
278 
279  if (!NeedMask)
280  return NewShift;
281 
282  Builder.Insert(NewShift);
283  return BinaryOperator::Create(Instruction::And, NewShift, NewMask);
284 }
285 
287  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
288  assert(Op0->getType() == Op1->getType());
289 
290  // If the shift amount is a one-use `sext`, we can demote it to `zext`.
291  Value *Y;
292  if (match(Op1, m_OneUse(m_SExt(m_Value(Y))))) {
293  Value *NewExt = Builder.CreateZExt(Y, I.getType(), Op1->getName());
294  return BinaryOperator::Create(I.getOpcode(), Op0, NewExt);
295  }
296 
297  // See if we can fold away this shift.
298  if (SimplifyDemandedInstructionBits(I))
299  return &I;
300 
301  // Try to fold constant and into select arguments.
302  if (isa<Constant>(Op0))
303  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
304  if (Instruction *R = FoldOpIntoSelect(I, SI))
305  return R;
306 
307  if (Constant *CUI = dyn_cast<Constant>(Op1))
308  if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
309  return Res;
310 
311  if (auto *NewShift = cast_or_null<Instruction>(
312  reassociateShiftAmtsOfTwoSameDirectionShifts(&I, SQ)))
313  return NewShift;
314 
315  // (C1 shift (A add C2)) -> (C1 shift C2) shift A)
316  // iff A and C2 are both positive.
317  Value *A;
318  Constant *C;
319  if (match(Op0, m_Constant()) && match(Op1, m_Add(m_Value(A), m_Constant(C))))
320  if (isKnownNonNegative(A, DL, 0, &AC, &I, &DT) &&
321  isKnownNonNegative(C, DL, 0, &AC, &I, &DT))
322  return BinaryOperator::Create(
323  I.getOpcode(), Builder.CreateBinOp(I.getOpcode(), Op0, C), A);
324 
325  // X shift (A srem B) -> X shift (A and B-1) iff B is a power of 2.
326  // Because shifts by negative values (which could occur if A were negative)
327  // are undefined.
328  const APInt *B;
329  if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Power2(B)))) {
330  // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't
331  // demand the sign bit (and many others) here??
332  Value *Rem = Builder.CreateAnd(A, ConstantInt::get(I.getType(), *B - 1),
333  Op1->getName());
334  I.setOperand(1, Rem);
335  return &I;
336  }
337 
338  return nullptr;
339 }
340 
341 /// Return true if we can simplify two logical (either left or right) shifts
342 /// that have constant shift amounts: OuterShift (InnerShift X, C1), C2.
343 static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl,
344  Instruction *InnerShift, InstCombiner &IC,
345  Instruction *CxtI) {
346  assert(InnerShift->isLogicalShift() && "Unexpected instruction type");
347 
348  // We need constant scalar or constant splat shifts.
349  const APInt *InnerShiftConst;
350  if (!match(InnerShift->getOperand(1), m_APInt(InnerShiftConst)))
351  return false;
352 
353  // Two logical shifts in the same direction:
354  // shl (shl X, C1), C2 --> shl X, C1 + C2
355  // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
356  bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
357  if (IsInnerShl == IsOuterShl)
358  return true;
359 
360  // Equal shift amounts in opposite directions become bitwise 'and':
361  // lshr (shl X, C), C --> and X, C'
362  // shl (lshr X, C), C --> and X, C'
363  if (*InnerShiftConst == OuterShAmt)
364  return true;
365 
366  // If the 2nd shift is bigger than the 1st, we can fold:
367  // lshr (shl X, C1), C2 --> and (shl X, C1 - C2), C3
368  // shl (lshr X, C1), C2 --> and (lshr X, C1 - C2), C3
369  // but it isn't profitable unless we know the and'd out bits are already zero.
370  // Also, check that the inner shift is valid (less than the type width) or
371  // we'll crash trying to produce the bit mask for the 'and'.
372  unsigned TypeWidth = InnerShift->getType()->getScalarSizeInBits();
373  if (InnerShiftConst->ugt(OuterShAmt) && InnerShiftConst->ult(TypeWidth)) {
374  unsigned InnerShAmt = InnerShiftConst->getZExtValue();
375  unsigned MaskShift =
376  IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt;
377  APInt Mask = APInt::getLowBitsSet(TypeWidth, OuterShAmt) << MaskShift;
378  if (IC.MaskedValueIsZero(InnerShift->getOperand(0), Mask, 0, CxtI))
379  return true;
380  }
381 
382  return false;
383 }
384 
385 /// See if we can compute the specified value, but shifted logically to the left
386 /// or right by some number of bits. This should return true if the expression
387 /// can be computed for the same cost as the current expression tree. This is
388 /// used to eliminate extraneous shifting from things like:
389 /// %C = shl i128 %A, 64
390 /// %D = shl i128 %B, 96
391 /// %E = or i128 %C, %D
392 /// %F = lshr i128 %E, 64
393 /// where the client will ask if E can be computed shifted right by 64-bits. If
394 /// this succeeds, getShiftedValue() will be called to produce the value.
395 static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift,
396  InstCombiner &IC, Instruction *CxtI) {
397  // We can always evaluate constants shifted.
398  if (isa<Constant>(V))
399  return true;
400 
402  if (!I) return false;
403 
404  // If this is the opposite shift, we can directly reuse the input of the shift
405  // if the needed bits are already zero in the input. This allows us to reuse
406  // the value which means that we don't care if the shift has multiple uses.
407  // TODO: Handle opposite shift by exact value.
408  ConstantInt *CI = nullptr;
409  if ((IsLeftShift && match(I, m_LShr(m_Value(), m_ConstantInt(CI)))) ||
410  (!IsLeftShift && match(I, m_Shl(m_Value(), m_ConstantInt(CI))))) {
411  if (CI->getValue() == NumBits) {
412  // TODO: Check that the input bits are already zero with MaskedValueIsZero
413 #if 0
414  // If this is a truncate of a logical shr, we can truncate it to a smaller
415  // lshr iff we know that the bits we would otherwise be shifting in are
416  // already zeros.
417  uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
418  uint32_t BitWidth = Ty->getScalarSizeInBits();
419  if (MaskedValueIsZero(I->getOperand(0),
420  APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) &&
421  CI->getLimitedValue(BitWidth) < BitWidth) {
422  return CanEvaluateTruncated(I->getOperand(0), Ty);
423  }
424 #endif
425 
426  }
427  }
428 
429  // We can't mutate something that has multiple uses: doing so would
430  // require duplicating the instruction in general, which isn't profitable.
431  if (!I->hasOneUse()) return false;
432 
433  switch (I->getOpcode()) {
434  default: return false;
435  case Instruction::And:
436  case Instruction::Or:
437  case Instruction::Xor:
438  // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
439  return canEvaluateShifted(I->getOperand(0), NumBits, IsLeftShift, IC, I) &&
440  canEvaluateShifted(I->getOperand(1), NumBits, IsLeftShift, IC, I);
441 
442  case Instruction::Shl:
443  case Instruction::LShr:
444  return canEvaluateShiftedShift(NumBits, IsLeftShift, I, IC, CxtI);
445 
446  case Instruction::Select: {
447  SelectInst *SI = cast<SelectInst>(I);
448  Value *TrueVal = SI->getTrueValue();
449  Value *FalseVal = SI->getFalseValue();
450  return canEvaluateShifted(TrueVal, NumBits, IsLeftShift, IC, SI) &&
451  canEvaluateShifted(FalseVal, NumBits, IsLeftShift, IC, SI);
452  }
453  case Instruction::PHI: {
454  // We can change a phi if we can change all operands. Note that we never
455  // get into trouble with cyclic PHIs here because we only consider
456  // instructions with a single use.
457  PHINode *PN = cast<PHINode>(I);
458  for (Value *IncValue : PN->incoming_values())
459  if (!canEvaluateShifted(IncValue, NumBits, IsLeftShift, IC, PN))
460  return false;
461  return true;
462  }
463  }
464 }
465 
466 /// Fold OuterShift (InnerShift X, C1), C2.
467 /// See canEvaluateShiftedShift() for the constraints on these instructions.
468 static Value *foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt,
469  bool IsOuterShl,
470  InstCombiner::BuilderTy &Builder) {
471  bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
472  Type *ShType = InnerShift->getType();
473  unsigned TypeWidth = ShType->getScalarSizeInBits();
474 
475  // We only accept shifts-by-a-constant in canEvaluateShifted().
476  const APInt *C1;
477  match(InnerShift->getOperand(1), m_APInt(C1));
478  unsigned InnerShAmt = C1->getZExtValue();
479 
480  // Change the shift amount and clear the appropriate IR flags.
481  auto NewInnerShift = [&](unsigned ShAmt) {
482  InnerShift->setOperand(1, ConstantInt::get(ShType, ShAmt));
483  if (IsInnerShl) {
484  InnerShift->setHasNoUnsignedWrap(false);
485  InnerShift->setHasNoSignedWrap(false);
486  } else {
487  InnerShift->setIsExact(false);
488  }
489  return InnerShift;
490  };
491 
492  // Two logical shifts in the same direction:
493  // shl (shl X, C1), C2 --> shl X, C1 + C2
494  // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
495  if (IsInnerShl == IsOuterShl) {
496  // If this is an oversized composite shift, then unsigned shifts get 0.
497  if (InnerShAmt + OuterShAmt >= TypeWidth)
498  return Constant::getNullValue(ShType);
499 
500  return NewInnerShift(InnerShAmt + OuterShAmt);
501  }
502 
503  // Equal shift amounts in opposite directions become bitwise 'and':
504  // lshr (shl X, C), C --> and X, C'
505  // shl (lshr X, C), C --> and X, C'
506  if (InnerShAmt == OuterShAmt) {
507  APInt Mask = IsInnerShl
508  ? APInt::getLowBitsSet(TypeWidth, TypeWidth - OuterShAmt)
509  : APInt::getHighBitsSet(TypeWidth, TypeWidth - OuterShAmt);
510  Value *And = Builder.CreateAnd(InnerShift->getOperand(0),
511  ConstantInt::get(ShType, Mask));
512  if (auto *AndI = dyn_cast<Instruction>(And)) {
513  AndI->moveBefore(InnerShift);
514  AndI->takeName(InnerShift);
515  }
516  return And;
517  }
518 
519  assert(InnerShAmt > OuterShAmt &&
520  "Unexpected opposite direction logical shift pair");
521 
522  // In general, we would need an 'and' for this transform, but
523  // canEvaluateShiftedShift() guarantees that the masked-off bits are not used.
524  // lshr (shl X, C1), C2 --> shl X, C1 - C2
525  // shl (lshr X, C1), C2 --> lshr X, C1 - C2
526  return NewInnerShift(InnerShAmt - OuterShAmt);
527 }
528 
529 /// When canEvaluateShifted() returns true for an expression, this function
530 /// inserts the new computation that produces the shifted value.
531 static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift,
532  InstCombiner &IC, const DataLayout &DL) {
533  // We can always evaluate constants shifted.
534  if (Constant *C = dyn_cast<Constant>(V)) {
535  if (isLeftShift)
536  V = IC.Builder.CreateShl(C, NumBits);
537  else
538  V = IC.Builder.CreateLShr(C, NumBits);
539  // If we got a constantexpr back, try to simplify it with TD info.
540  if (auto *C = dyn_cast<Constant>(V))
541  if (auto *FoldedC =
543  V = FoldedC;
544  return V;
545  }
546 
547  Instruction *I = cast<Instruction>(V);
548  IC.Worklist.Add(I);
549 
550  switch (I->getOpcode()) {
551  default: llvm_unreachable("Inconsistency with CanEvaluateShifted");
552  case Instruction::And:
553  case Instruction::Or:
554  case Instruction::Xor:
555  // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
556  I->setOperand(
557  0, getShiftedValue(I->getOperand(0), NumBits, isLeftShift, IC, DL));
558  I->setOperand(
559  1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
560  return I;
561 
562  case Instruction::Shl:
563  case Instruction::LShr:
564  return foldShiftedShift(cast<BinaryOperator>(I), NumBits, isLeftShift,
565  IC.Builder);
566 
567  case Instruction::Select:
568  I->setOperand(
569  1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
570  I->setOperand(
571  2, getShiftedValue(I->getOperand(2), NumBits, isLeftShift, IC, DL));
572  return I;
573  case Instruction::PHI: {
574  // We can change a phi if we can change all operands. Note that we never
575  // get into trouble with cyclic PHIs here because we only consider
576  // instructions with a single use.
577  PHINode *PN = cast<PHINode>(I);
578  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
579  PN->setIncomingValue(i, getShiftedValue(PN->getIncomingValue(i), NumBits,
580  isLeftShift, IC, DL));
581  return PN;
582  }
583  }
584 }
585 
586 // If this is a bitwise operator or add with a constant RHS we might be able
587 // to pull it through a shift.
589  BinaryOperator *BO) {
590  switch (BO->getOpcode()) {
591  default:
592  return false; // Do not perform transform!
593  case Instruction::Add:
594  return Shift.getOpcode() == Instruction::Shl;
595  case Instruction::Or:
596  case Instruction::Xor:
597  case Instruction::And:
598  return true;
599  }
600 }
601 
603  BinaryOperator &I) {
604  bool isLeftShift = I.getOpcode() == Instruction::Shl;
605 
606  const APInt *Op1C;
607  if (!match(Op1, m_APInt(Op1C)))
608  return nullptr;
609 
610  // See if we can propagate this shift into the input, this covers the trivial
611  // cast of lshr(shl(x,c1),c2) as well as other more complex cases.
612  if (I.getOpcode() != Instruction::AShr &&
613  canEvaluateShifted(Op0, Op1C->getZExtValue(), isLeftShift, *this, &I)) {
614  LLVM_DEBUG(
615  dbgs() << "ICE: GetShiftedValue propagating shift through expression"
616  " to eliminate shift:\n IN: "
617  << *Op0 << "\n SH: " << I << "\n");
618 
619  return replaceInstUsesWith(
620  I, getShiftedValue(Op0, Op1C->getZExtValue(), isLeftShift, *this, DL));
621  }
622 
623  // See if we can simplify any instructions used by the instruction whose sole
624  // purpose is to compute bits we don't care about.
625  unsigned TypeBits = Op0->getType()->getScalarSizeInBits();
626 
627  assert(!Op1C->uge(TypeBits) &&
628  "Shift over the type width should have been removed already");
629 
630  if (Instruction *FoldedShift = foldBinOpIntoSelectOrPhi(I))
631  return FoldedShift;
632 
633  // Fold shift2(trunc(shift1(x,c1)), c2) -> trunc(shift2(shift1(x,c1),c2))
634  if (TruncInst *TI = dyn_cast<TruncInst>(Op0)) {
635  Instruction *TrOp = dyn_cast<Instruction>(TI->getOperand(0));
636  // If 'shift2' is an ashr, we would have to get the sign bit into a funny
637  // place. Don't try to do this transformation in this case. Also, we
638  // require that the input operand is a shift-by-constant so that we have
639  // confidence that the shifts will get folded together. We could do this
640  // xform in more cases, but it is unlikely to be profitable.
641  if (TrOp && I.isLogicalShift() && TrOp->isShift() &&
642  isa<ConstantInt>(TrOp->getOperand(1))) {
643  // Okay, we'll do this xform. Make the shift of shift.
644  Constant *ShAmt =
645  ConstantExpr::getZExt(cast<Constant>(Op1), TrOp->getType());
646  // (shift2 (shift1 & 0x00FF), c2)
647  Value *NSh = Builder.CreateBinOp(I.getOpcode(), TrOp, ShAmt, I.getName());
648 
649  // For logical shifts, the truncation has the effect of making the high
650  // part of the register be zeros. Emulate this by inserting an AND to
651  // clear the top bits as needed. This 'and' will usually be zapped by
652  // other xforms later if dead.
653  unsigned SrcSize = TrOp->getType()->getScalarSizeInBits();
654  unsigned DstSize = TI->getType()->getScalarSizeInBits();
655  APInt MaskV(APInt::getLowBitsSet(SrcSize, DstSize));
656 
657  // The mask we constructed says what the trunc would do if occurring
658  // between the shifts. We want to know the effect *after* the second
659  // shift. We know that it is a logical shift by a constant, so adjust the
660  // mask as appropriate.
661  if (I.getOpcode() == Instruction::Shl)
662  MaskV <<= Op1C->getZExtValue();
663  else {
664  assert(I.getOpcode() == Instruction::LShr && "Unknown logical shift");
665  MaskV.lshrInPlace(Op1C->getZExtValue());
666  }
667 
668  // shift1 & 0x00FF
669  Value *And = Builder.CreateAnd(NSh,
670  ConstantInt::get(I.getContext(), MaskV),
671  TI->getName());
672 
673  // Return the value truncated to the interesting size.
674  return new TruncInst(And, I.getType());
675  }
676  }
677 
678  if (Op0->hasOneUse()) {
679  if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
680  // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C)
681  Value *V1, *V2;
682  ConstantInt *CC;
683  switch (Op0BO->getOpcode()) {
684  default: break;
685  case Instruction::Add:
686  case Instruction::And:
687  case Instruction::Or:
688  case Instruction::Xor: {
689  // These operators commute.
690  // Turn (Y + (X >> C)) << C -> (X + (Y << C)) & (~0 << C)
691  if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() &&
692  match(Op0BO->getOperand(1), m_Shr(m_Value(V1),
693  m_Specific(Op1)))) {
694  Value *YS = // (Y << C)
695  Builder.CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName());
696  // (X + (Y << C))
697  Value *X = Builder.CreateBinOp(Op0BO->getOpcode(), YS, V1,
698  Op0BO->getOperand(1)->getName());
699  unsigned Op1Val = Op1C->getLimitedValue(TypeBits);
700 
701  APInt Bits = APInt::getHighBitsSet(TypeBits, TypeBits - Op1Val);
703  if (VectorType *VT = dyn_cast<VectorType>(X->getType()))
704  Mask = ConstantVector::getSplat(VT->getNumElements(), Mask);
705  return BinaryOperator::CreateAnd(X, Mask);
706  }
707 
708  // Turn (Y + ((X >> C) & CC)) << C -> ((X & (CC << C)) + (Y << C))
709  Value *Op0BOOp1 = Op0BO->getOperand(1);
710  if (isLeftShift && Op0BOOp1->hasOneUse() &&
711  match(Op0BOOp1,
712  m_And(m_OneUse(m_Shr(m_Value(V1), m_Specific(Op1))),
713  m_ConstantInt(CC)))) {
714  Value *YS = // (Y << C)
715  Builder.CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName());
716  // X & (CC << C)
717  Value *XM = Builder.CreateAnd(V1, ConstantExpr::getShl(CC, Op1),
718  V1->getName()+".mask");
719  return BinaryOperator::Create(Op0BO->getOpcode(), YS, XM);
720  }
722  }
723 
724  case Instruction::Sub: {
725  // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C)
726  if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
727  match(Op0BO->getOperand(0), m_Shr(m_Value(V1),
728  m_Specific(Op1)))) {
729  Value *YS = // (Y << C)
730  Builder.CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName());
731  // (X + (Y << C))
732  Value *X = Builder.CreateBinOp(Op0BO->getOpcode(), V1, YS,
733  Op0BO->getOperand(0)->getName());
734  unsigned Op1Val = Op1C->getLimitedValue(TypeBits);
735 
736  APInt Bits = APInt::getHighBitsSet(TypeBits, TypeBits - Op1Val);
738  if (VectorType *VT = dyn_cast<VectorType>(X->getType()))
739  Mask = ConstantVector::getSplat(VT->getNumElements(), Mask);
740  return BinaryOperator::CreateAnd(X, Mask);
741  }
742 
743  // Turn (((X >> C)&CC) + Y) << C -> (X + (Y << C)) & (CC << C)
744  if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
745  match(Op0BO->getOperand(0),
746  m_And(m_OneUse(m_Shr(m_Value(V1), m_Value(V2))),
747  m_ConstantInt(CC))) && V2 == Op1) {
748  Value *YS = // (Y << C)
749  Builder.CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName());
750  // X & (CC << C)
751  Value *XM = Builder.CreateAnd(V1, ConstantExpr::getShl(CC, Op1),
752  V1->getName()+".mask");
753 
754  return BinaryOperator::Create(Op0BO->getOpcode(), XM, YS);
755  }
756 
757  break;
758  }
759  }
760 
761 
762  // If the operand is a bitwise operator with a constant RHS, and the
763  // shift is the only use, we can pull it out of the shift.
764  const APInt *Op0C;
765  if (match(Op0BO->getOperand(1), m_APInt(Op0C))) {
766  if (canShiftBinOpWithConstantRHS(I, Op0BO)) {
767  Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
768  cast<Constant>(Op0BO->getOperand(1)), Op1);
769 
770  Value *NewShift =
771  Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1);
772  NewShift->takeName(Op0BO);
773 
774  return BinaryOperator::Create(Op0BO->getOpcode(), NewShift,
775  NewRHS);
776  }
777  }
778 
779  // If the operand is a subtract with a constant LHS, and the shift
780  // is the only use, we can pull it out of the shift.
781  // This folds (shl (sub C1, X), C2) -> (sub (C1 << C2), (shl X, C2))
782  if (isLeftShift && Op0BO->getOpcode() == Instruction::Sub &&
783  match(Op0BO->getOperand(0), m_APInt(Op0C))) {
784  Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
785  cast<Constant>(Op0BO->getOperand(0)), Op1);
786 
787  Value *NewShift = Builder.CreateShl(Op0BO->getOperand(1), Op1);
788  NewShift->takeName(Op0BO);
789 
790  return BinaryOperator::CreateSub(NewRHS, NewShift);
791  }
792  }
793 
794  // If we have a select that conditionally executes some binary operator,
795  // see if we can pull it the select and operator through the shift.
796  //
797  // For example, turning:
798  // shl (select C, (add X, C1), X), C2
799  // Into:
800  // Y = shl X, C2
801  // select C, (add Y, C1 << C2), Y
802  Value *Cond;
803  BinaryOperator *TBO;
804  Value *FalseVal;
805  if (match(Op0, m_Select(m_Value(Cond), m_OneUse(m_BinOp(TBO)),
806  m_Value(FalseVal)))) {
807  const APInt *C;
808  if (!isa<Constant>(FalseVal) && TBO->getOperand(0) == FalseVal &&
809  match(TBO->getOperand(1), m_APInt(C)) &&
811  Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
812  cast<Constant>(TBO->getOperand(1)), Op1);
813 
814  Value *NewShift =
815  Builder.CreateBinOp(I.getOpcode(), FalseVal, Op1);
816  Value *NewOp = Builder.CreateBinOp(TBO->getOpcode(), NewShift,
817  NewRHS);
818  return SelectInst::Create(Cond, NewOp, NewShift);
819  }
820  }
821 
822  BinaryOperator *FBO;
823  Value *TrueVal;
824  if (match(Op0, m_Select(m_Value(Cond), m_Value(TrueVal),
825  m_OneUse(m_BinOp(FBO))))) {
826  const APInt *C;
827  if (!isa<Constant>(TrueVal) && FBO->getOperand(0) == TrueVal &&
828  match(FBO->getOperand(1), m_APInt(C)) &&
830  Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
831  cast<Constant>(FBO->getOperand(1)), Op1);
832 
833  Value *NewShift =
834  Builder.CreateBinOp(I.getOpcode(), TrueVal, Op1);
835  Value *NewOp = Builder.CreateBinOp(FBO->getOpcode(), NewShift,
836  NewRHS);
837  return SelectInst::Create(Cond, NewShift, NewOp);
838  }
839  }
840  }
841 
842  return nullptr;
843 }
844 
846  const SimplifyQuery Q = SQ.getWithInstruction(&I);
847 
848  if (Value *V = SimplifyShlInst(I.getOperand(0), I.getOperand(1),
849  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(), Q))
850  return replaceInstUsesWith(I, V);
851 
852  if (Instruction *X = foldVectorBinop(I))
853  return X;
854 
855  if (Instruction *V = commonShiftTransforms(I))
856  return V;
857 
858  if (Instruction *V = dropRedundantMaskingOfLeftShiftInput(&I, Q, Builder))
859  return V;
860 
861  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
862  Type *Ty = I.getType();
863  unsigned BitWidth = Ty->getScalarSizeInBits();
864 
865  const APInt *ShAmtAPInt;
866  if (match(Op1, m_APInt(ShAmtAPInt))) {
867  unsigned ShAmt = ShAmtAPInt->getZExtValue();
868 
869  // shl (zext X), ShAmt --> zext (shl X, ShAmt)
870  // This is only valid if X would have zeros shifted out.
871  Value *X;
872  if (match(Op0, m_OneUse(m_ZExt(m_Value(X))))) {
873  unsigned SrcWidth = X->getType()->getScalarSizeInBits();
874  if (ShAmt < SrcWidth &&
875  MaskedValueIsZero(X, APInt::getHighBitsSet(SrcWidth, ShAmt), 0, &I))
876  return new ZExtInst(Builder.CreateShl(X, ShAmt), Ty);
877  }
878 
879  // (X >> C) << C --> X & (-1 << C)
880  if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1)))) {
881  APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmt));
882  return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));
883  }
884 
885  // FIXME: we do not yet transform non-exact shr's. The backend (DAGCombine)
886  // needs a few fixes for the rotate pattern recognition first.
887  const APInt *ShOp1;
888  if (match(Op0, m_Exact(m_Shr(m_Value(X), m_APInt(ShOp1))))) {
889  unsigned ShrAmt = ShOp1->getZExtValue();
890  if (ShrAmt < ShAmt) {
891  // If C1 < C2: (X >>?,exact C1) << C2 --> X << (C2 - C1)
892  Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShrAmt);
893  auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
894  NewShl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
895  NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
896  return NewShl;
897  }
898  if (ShrAmt > ShAmt) {
899  // If C1 > C2: (X >>?exact C1) << C2 --> X >>?exact (C1 - C2)
900  Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmt);
901  auto *NewShr = BinaryOperator::Create(
902  cast<BinaryOperator>(Op0)->getOpcode(), X, ShiftDiff);
903  NewShr->setIsExact(true);
904  return NewShr;
905  }
906  }
907 
908  if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1)))) {
909  unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
910  // Oversized shifts are simplified to zero in InstSimplify.
911  if (AmtSum < BitWidth)
912  // (X << C1) << C2 --> X << (C1 + C2)
913  return BinaryOperator::CreateShl(X, ConstantInt::get(Ty, AmtSum));
914  }
915 
916  // If the shifted-out value is known-zero, then this is a NUW shift.
917  if (!I.hasNoUnsignedWrap() &&
918  MaskedValueIsZero(Op0, APInt::getHighBitsSet(BitWidth, ShAmt), 0, &I)) {
920  return &I;
921  }
922 
923  // If the shifted-out value is all signbits, then this is a NSW shift.
924  if (!I.hasNoSignedWrap() && ComputeNumSignBits(Op0, 0, &I) > ShAmt) {
925  I.setHasNoSignedWrap();
926  return &I;
927  }
928  }
929 
930  // Transform (x >> y) << y to x & (-1 << y)
931  // Valid for any type of right-shift.
932  Value *X;
933  if (match(Op0, m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))))) {
934  Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
935  Value *Mask = Builder.CreateShl(AllOnes, Op1);
936  return BinaryOperator::CreateAnd(Mask, X);
937  }
938 
939  Constant *C1;
940  if (match(Op1, m_Constant(C1))) {
941  Constant *C2;
942  Value *X;
943  // (C2 << X) << C1 --> (C2 << C1) << X
944  if (match(Op0, m_OneUse(m_Shl(m_Constant(C2), m_Value(X)))))
945  return BinaryOperator::CreateShl(ConstantExpr::getShl(C2, C1), X);
946 
947  // (X * C2) << C1 --> X * (C2 << C1)
948  if (match(Op0, m_Mul(m_Value(X), m_Constant(C2))))
950 
951  // shl (zext i1 X), C1 --> select (X, 1 << C1, 0)
952  if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
953  auto *NewC = ConstantExpr::getShl(ConstantInt::get(Ty, 1), C1);
954  return SelectInst::Create(X, NewC, ConstantInt::getNullValue(Ty));
955  }
956  }
957 
958  // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1
959  if (match(Op0, m_One()) &&
960  match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X))))
961  return BinaryOperator::CreateLShr(
962  ConstantInt::get(Ty, APInt::getSignMask(BitWidth)), X);
963 
964  return nullptr;
965 }
966 
968  if (Value *V = SimplifyLShrInst(I.getOperand(0), I.getOperand(1), I.isExact(),
969  SQ.getWithInstruction(&I)))
970  return replaceInstUsesWith(I, V);
971 
972  if (Instruction *X = foldVectorBinop(I))
973  return X;
974 
975  if (Instruction *R = commonShiftTransforms(I))
976  return R;
977 
978  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
979  Type *Ty = I.getType();
980  const APInt *ShAmtAPInt;
981  if (match(Op1, m_APInt(ShAmtAPInt))) {
982  unsigned ShAmt = ShAmtAPInt->getZExtValue();
983  unsigned BitWidth = Ty->getScalarSizeInBits();
984  auto *II = dyn_cast<IntrinsicInst>(Op0);
985  if (II && isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == ShAmt &&
986  (II->getIntrinsicID() == Intrinsic::ctlz ||
987  II->getIntrinsicID() == Intrinsic::cttz ||
988  II->getIntrinsicID() == Intrinsic::ctpop)) {
989  // ctlz.i32(x)>>5 --> zext(x == 0)
990  // cttz.i32(x)>>5 --> zext(x == 0)
991  // ctpop.i32(x)>>5 --> zext(x == -1)
992  bool IsPop = II->getIntrinsicID() == Intrinsic::ctpop;
993  Constant *RHS = ConstantInt::getSigned(Ty, IsPop ? -1 : 0);
994  Value *Cmp = Builder.CreateICmpEQ(II->getArgOperand(0), RHS);
995  return new ZExtInst(Cmp, Ty);
996  }
997 
998  Value *X;
999  const APInt *ShOp1;
1000  if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1))) && ShOp1->ult(BitWidth)) {
1001  if (ShOp1->ult(ShAmt)) {
1002  unsigned ShlAmt = ShOp1->getZExtValue();
1003  Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt);
1004  if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
1005  // (X <<nuw C1) >>u C2 --> X >>u (C2 - C1)
1006  auto *NewLShr = BinaryOperator::CreateLShr(X, ShiftDiff);
1007  NewLShr->setIsExact(I.isExact());
1008  return NewLShr;
1009  }
1010  // (X << C1) >>u C2 --> (X >>u (C2 - C1)) & (-1 >> C2)
1011  Value *NewLShr = Builder.CreateLShr(X, ShiftDiff, "", I.isExact());
1012  APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt));
1013  return BinaryOperator::CreateAnd(NewLShr, ConstantInt::get(Ty, Mask));
1014  }
1015  if (ShOp1->ugt(ShAmt)) {
1016  unsigned ShlAmt = ShOp1->getZExtValue();
1017  Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt);
1018  if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
1019  // (X <<nuw C1) >>u C2 --> X <<nuw (C1 - C2)
1020  auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
1021  NewShl->setHasNoUnsignedWrap(true);
1022  return NewShl;
1023  }
1024  // (X << C1) >>u C2 --> X << (C1 - C2) & (-1 >> C2)
1025  Value *NewShl = Builder.CreateShl(X, ShiftDiff);
1026  APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt));
1027  return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask));
1028  }
1029  assert(*ShOp1 == ShAmt);
1030  // (X << C) >>u C --> X & (-1 >>u C)
1031  APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt));
1032  return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));
1033  }
1034 
1035  if (match(Op0, m_OneUse(m_ZExt(m_Value(X)))) &&
1036  (!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType()))) {
1037  assert(ShAmt < X->getType()->getScalarSizeInBits() &&
1038  "Big shift not simplified to zero?");
1039  // lshr (zext iM X to iN), C --> zext (lshr X, C) to iN
1040  Value *NewLShr = Builder.CreateLShr(X, ShAmt);
1041  return new ZExtInst(NewLShr, Ty);
1042  }
1043 
1044  if (match(Op0, m_SExt(m_Value(X))) &&
1045  (!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType()))) {
1046  // Are we moving the sign bit to the low bit and widening with high zeros?
1047  unsigned SrcTyBitWidth = X->getType()->getScalarSizeInBits();
1048  if (ShAmt == BitWidth - 1) {
1049  // lshr (sext i1 X to iN), N-1 --> zext X to iN
1050  if (SrcTyBitWidth == 1)
1051  return new ZExtInst(X, Ty);
1052 
1053  // lshr (sext iM X to iN), N-1 --> zext (lshr X, M-1) to iN
1054  if (Op0->hasOneUse()) {
1055  Value *NewLShr = Builder.CreateLShr(X, SrcTyBitWidth - 1);
1056  return new ZExtInst(NewLShr, Ty);
1057  }
1058  }
1059 
1060  // lshr (sext iM X to iN), N-M --> zext (ashr X, min(N-M, M-1)) to iN
1061  if (ShAmt == BitWidth - SrcTyBitWidth && Op0->hasOneUse()) {
1062  // The new shift amount can't be more than the narrow source type.
1063  unsigned NewShAmt = std::min(ShAmt, SrcTyBitWidth - 1);
1064  Value *AShr = Builder.CreateAShr(X, NewShAmt);
1065  return new ZExtInst(AShr, Ty);
1066  }
1067  }
1068 
1069  if (match(Op0, m_LShr(m_Value(X), m_APInt(ShOp1)))) {
1070  unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
1071  // Oversized shifts are simplified to zero in InstSimplify.
1072  if (AmtSum < BitWidth)
1073  // (X >>u C1) >>u C2 --> X >>u (C1 + C2)
1074  return BinaryOperator::CreateLShr(X, ConstantInt::get(Ty, AmtSum));
1075  }
1076 
1077  // If the shifted-out value is known-zero, then this is an exact shift.
1078  if (!I.isExact() &&
1079  MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), 0, &I)) {
1080  I.setIsExact();
1081  return &I;
1082  }
1083  }
1084 
1085  // Transform (x << y) >> y to x & (-1 >> y)
1086  Value *X;
1087  if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_Specific(Op1))))) {
1088  Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
1089  Value *Mask = Builder.CreateLShr(AllOnes, Op1);
1090  return BinaryOperator::CreateAnd(Mask, X);
1091  }
1092 
1093  return nullptr;
1094 }
1095 
1096 Instruction *
1098  BinaryOperator &OldAShr) {
1099  assert(OldAShr.getOpcode() == Instruction::AShr &&
1100  "Must be called with arithmetic right-shift instruction only.");
1101 
1102  // Check that constant C is a splat of the element-wise bitwidth of V.
1103  auto BitWidthSplat = [](Constant *C, Value *V) {
1104  return match(
1105  C, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ,
1107  V->getType()->getScalarSizeInBits())));
1108  };
1109 
1110  // It should look like variable-length sign-extension on the outside:
1111  // (Val << (bitwidth(Val)-Nbits)) a>> (bitwidth(Val)-Nbits)
1112  Value *NBits;
1113  Instruction *MaybeTrunc;
1114  Constant *C1, *C2;
1115  if (!match(&OldAShr,
1116  m_AShr(m_Shl(m_Instruction(MaybeTrunc),
1118  m_ZExtOrSelf(m_Value(NBits))))),
1120  m_ZExtOrSelf(m_Deferred(NBits)))))) ||
1121  !BitWidthSplat(C1, &OldAShr) || !BitWidthSplat(C2, &OldAShr))
1122  return nullptr;
1123 
1124  // There may or may not be a truncation after outer two shifts.
1125  Instruction *HighBitExtract;
1126  match(MaybeTrunc, m_TruncOrSelf(m_Instruction(HighBitExtract)));
1127  bool HadTrunc = MaybeTrunc != HighBitExtract;
1128 
1129  // And finally, the innermost part of the pattern must be a right-shift.
1130  Value *X, *NumLowBitsToSkip;
1131  if (!match(HighBitExtract, m_Shr(m_Value(X), m_Value(NumLowBitsToSkip))))
1132  return nullptr;
1133 
1134  // Said right-shift must extract high NBits bits - C0 must be it's bitwidth.
1135  Constant *C0;
1136  if (!match(NumLowBitsToSkip,
1137  m_ZExtOrSelf(
1138  m_Sub(m_Constant(C0), m_ZExtOrSelf(m_Specific(NBits))))) ||
1139  !BitWidthSplat(C0, HighBitExtract))
1140  return nullptr;
1141 
1142  // Since the NBits is identical for all shifts, if the outermost and
1143  // innermost shifts are identical, then outermost shifts are redundant.
1144  // If we had truncation, do keep it though.
1145  if (HighBitExtract->getOpcode() == OldAShr.getOpcode())
1146  return replaceInstUsesWith(OldAShr, MaybeTrunc);
1147 
1148  // Else, if there was a truncation, then we need to ensure that one
1149  // instruction will go away.
1150  if (HadTrunc && !match(&OldAShr, m_c_BinOp(m_OneUse(m_Value()), m_Value())))
1151  return nullptr;
1152 
1153  // Finally, bypass two innermost shifts, and perform the outermost shift on
1154  // the operands of the innermost shift.
1155  Instruction *NewAShr =
1156  BinaryOperator::Create(OldAShr.getOpcode(), X, NumLowBitsToSkip);
1157  NewAShr->copyIRFlags(HighBitExtract); // We can preserve 'exact'-ness.
1158  if (!HadTrunc)
1159  return NewAShr;
1160 
1161  Builder.Insert(NewAShr);
1162  return TruncInst::CreateTruncOrBitCast(NewAShr, OldAShr.getType());
1163 }
1164 
1166  if (Value *V = SimplifyAShrInst(I.getOperand(0), I.getOperand(1), I.isExact(),
1167  SQ.getWithInstruction(&I)))
1168  return replaceInstUsesWith(I, V);
1169 
1170  if (Instruction *X = foldVectorBinop(I))
1171  return X;
1172 
1173  if (Instruction *R = commonShiftTransforms(I))
1174  return R;
1175 
1176  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1177  Type *Ty = I.getType();
1178  unsigned BitWidth = Ty->getScalarSizeInBits();
1179  const APInt *ShAmtAPInt;
1180  if (match(Op1, m_APInt(ShAmtAPInt)) && ShAmtAPInt->ult(BitWidth)) {
1181  unsigned ShAmt = ShAmtAPInt->getZExtValue();
1182 
1183  // If the shift amount equals the difference in width of the destination
1184  // and source scalar types:
1185  // ashr (shl (zext X), C), C --> sext X
1186  Value *X;
1187  if (match(Op0, m_Shl(m_ZExt(m_Value(X)), m_Specific(Op1))) &&
1188  ShAmt == BitWidth - X->getType()->getScalarSizeInBits())
1189  return new SExtInst(X, Ty);
1190 
1191  // We can't handle (X << C1) >>s C2. It shifts arbitrary bits in. However,
1192  // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits.
1193  const APInt *ShOp1;
1194  if (match(Op0, m_NSWShl(m_Value(X), m_APInt(ShOp1))) &&
1195  ShOp1->ult(BitWidth)) {
1196  unsigned ShlAmt = ShOp1->getZExtValue();
1197  if (ShlAmt < ShAmt) {
1198  // (X <<nsw C1) >>s C2 --> X >>s (C2 - C1)
1199  Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt);
1200  auto *NewAShr = BinaryOperator::CreateAShr(X, ShiftDiff);
1201  NewAShr->setIsExact(I.isExact());
1202  return NewAShr;
1203  }
1204  if (ShlAmt > ShAmt) {
1205  // (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2)
1206  Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt);
1207  auto *NewShl = BinaryOperator::Create(Instruction::Shl, X, ShiftDiff);
1208  NewShl->setHasNoSignedWrap(true);
1209  return NewShl;
1210  }
1211  }
1212 
1213  if (match(Op0, m_AShr(m_Value(X), m_APInt(ShOp1))) &&
1214  ShOp1->ult(BitWidth)) {
1215  unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
1216  // Oversized arithmetic shifts replicate the sign bit.
1217  AmtSum = std::min(AmtSum, BitWidth - 1);
1218  // (X >>s C1) >>s C2 --> X >>s (C1 + C2)
1219  return BinaryOperator::CreateAShr(X, ConstantInt::get(Ty, AmtSum));
1220  }
1221 
1222  if (match(Op0, m_OneUse(m_SExt(m_Value(X)))) &&
1223  (Ty->isVectorTy() || shouldChangeType(Ty, X->getType()))) {
1224  // ashr (sext X), C --> sext (ashr X, C')
1225  Type *SrcTy = X->getType();
1226  ShAmt = std::min(ShAmt, SrcTy->getScalarSizeInBits() - 1);
1227  Value *NewSh = Builder.CreateAShr(X, ConstantInt::get(SrcTy, ShAmt));
1228  return new SExtInst(NewSh, Ty);
1229  }
1230 
1231  // If the shifted-out value is known-zero, then this is an exact shift.
1232  if (!I.isExact() &&
1233  MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), 0, &I)) {
1234  I.setIsExact();
1235  return &I;
1236  }
1237  }
1238 
1239  if (Instruction *R = foldVariableSignZeroExtensionOfVariableHighBitExtract(I))
1240  return R;
1241 
1242  // See if we can turn a signed shr into an unsigned shr.
1243  if (MaskedValueIsZero(Op0, APInt::getSignMask(BitWidth), 0, &I))
1244  return BinaryOperator::CreateLShr(Op0, Op1);
1245 
1246  return nullptr;
1247 }
cst_pred_ty< icmp_pred_with_threshold > m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold)
Match an integer or vector with every element comparing &#39;pred&#39; (eg/ne/...) to Threshold.
Definition: PatternMatch.h:494
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:874
uint64_t CallInst * C
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
class_match< UndefValue > m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:86
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1571
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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
SimplifyQuery getWithInstruction(Instruction *I) const
BinaryOps getOpcode() const
Definition: InstrTypes.h:402
static Instruction * dropRedundantMaskingOfLeftShiftInput(BinaryOperator *OuterShift, const SimplifyQuery &Q, InstCombiner::BuilderTy &Builder)
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.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:826
static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift, InstCombiner &IC, Instruction *CxtI)
See if we can compute the specified value, but shifted logically to the left or right by some number ...
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Get a value with low bits set.
Definition: APInt.h:647
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:89
const Value * getTrueValue() const
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:904
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:743
void Add(Instruction *I)
Add - Add the specified instruction to the worklist if it isn&#39;t already in it.
This class represents a sign extension of integer types.
Value * SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, const SimplifyQuery &Q)
Given operands for a Shl, fold the result or return null.
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2261
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:230
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:289
Value * SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, const SimplifyQuery &Q)
Given operands for a LShr, fold the result or return null.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, OpTy > m_ZExtOrSelf(const OpTy &Op)
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:886
This class represents the LLVM &#39;select&#39; instruction.
Instruction * commonShiftTransforms(BinaryOperator &I)
Exact_match< T > m_Exact(const T &SubPattern)
static Constant * getLShr(Constant *C1, Constant *C2, bool isExact=false)
Definition: Constants.cpp:2328
static Optional< unsigned > getOpcode(ArrayRef< VPValue *> Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:196
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
The core instruction combiner logic.
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.
void lshrInPlace(unsigned ShiftAmt)
Logical right-shift this APInt by ShiftAmt in place.
Definition: APInt.h:977
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:759
static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift, BinaryOperator *BO)
Constant * ConstantFoldConstant(const Constant *C, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldConstant - Attempt to fold the constant using the specified DataLayout.
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1696
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
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:142
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:81
Instruction * foldVariableSignZeroExtensionOfVariableHighBitExtract(BinaryOperator &OldAShr)
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:137
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:203
bool isKnownNonNegative(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Returns true if the give value is known to be non-negative.
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:412
match_combine_or< CastClass_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
Type * getExtendedType() const
Given scalar/vector integer type, returns a type with elements twice as wide as in the original type...
Definition: DerivedTypes.h:615
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:291
This class represents a truncation of integer types.
static Constant * replaceUndefsWith(Constant *C, Constant *Replacement)
Value * getOperand(unsigned i) const
Definition: User.h:169
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Get a value with high bits set.
Definition: APInt.h:635
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:61
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits...
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:898
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:194
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:465
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1184
This is an important base class in LLVM.
Definition: Constant.h:41
Value * reassociateShiftAmtsOfTwoSameDirectionShifts(BinaryOperator *Sh0, const SimplifyQuery &SQ, bool AnalyzeForSignBitExtraction=false)
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
static unsigned getScalarSizeInBits(Type *Ty)
specific_intval m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:664
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:336
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:587
Value * SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:892
constexpr double e
Definition: MathExtras.h:57
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:73
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2244
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:343
Instruction * visitLShr(BinaryOperator &I)
static bool hasNoUnsignedWrap(BinaryOperator &I)
static wasm::ValType getType(const TargetRegisterClass *RC)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
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
TargetLibraryInfo & getTargetLibraryInfo() const
InstCombineWorklist & Worklist
A worklist of the instructions that need to be simplified.
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:50
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:554
static Constant * getSplat(unsigned NumElts, Constant *Elt)
Return a ConstantVector with the specified constant in each element.
Definition: Constants.cpp:1150
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag...
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
Definition: Constants.h:250
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
static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl, Instruction *InnerShift, InstCombiner &IC, Instruction *CxtI)
Return true if we can simplify two logical (either left or right) shifts that have constant shift amo...
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1668
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
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.cpp:667
unsigned getNumIncomingValues() const
Return the number of incoming edges.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1292
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:585
Class to represent vector types.
Definition: DerivedTypes.h:432
Class for arbitrary precision integers.
Definition: APInt.h:69
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.
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1207
const Value * getFalseValue() const
static Constant * getZExtOrBitCast(Constant *C, Type *Ty)
Definition: Constants.cpp:1600
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass&#39;s ...
bool ugt(const APInt &RHS) const
Unsigned greather than comparison.
Definition: APInt.h:1254
static CastInst * CreateTruncOrBitCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a Trunc or BitCast cast instruction.
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
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
Value * SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, const SimplifyQuery &Q)
Given operands for a AShr, fold the result or return nulll.
#define I(x, y, z)
Definition: MD5.cpp:58
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:961
static Value * getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift, InstCombiner &IC, const DataLayout &DL)
When canEvaluateShifted() returns true for an expression, this function inserts the new computation t...
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
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1268
InstTy * Insert(InstTy *I, const Twine &Name="") const
Insert and return the specified instruction.
Definition: IRBuilder.h:830
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())
static Value * foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt, bool IsOuterShl, InstCombiner::BuilderTy &Builder)
Fold OuterShift (InnerShift X, C1), C2.
LLVM Value Representation.
Definition: Value.h:74
This file provides internal interfaces used to implement the InstCombine.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:382
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:273
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
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1228
Value * SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, const SimplifyQuery &Q)
Given operands for a Sub, fold the result or return null.
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:148
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:433
Instruction * visitAShr(BinaryOperator &I)
void setIncomingValue(unsigned i, Value *V)
Instruction * visitShl(BinaryOperator &I)
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
op_range incoming_values()
Instruction * FoldShiftByConstant(Value *Op0, Constant *Op1, BinaryOperator &I)
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1110
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:558
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
static Constant * get(unsigned Opcode, Constant *C1, unsigned Flags=0, Type *OnlyIfReducedTy=nullptr)
get - Return a unary operator constant expression, folding if possible.
Definition: Constants.cpp:1837