LLVM  17.0.0git
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"
15 #include "llvm/IR/IntrinsicInst.h"
16 #include "llvm/IR/PatternMatch.h"
18 using namespace llvm;
19 using namespace PatternMatch;
20 
21 #define DEBUG_TYPE "instcombine"
22 
24  Value *ShAmt1) {
25  // We have two shift amounts from two different shifts. The types of those
26  // shift amounts may not match. If that's the case let's bailout now..
27  if (ShAmt0->getType() != ShAmt1->getType())
28  return false;
29 
30  // As input, we have the following pattern:
31  // Sh0 (Sh1 X, Q), K
32  // We want to rewrite that as:
33  // Sh x, (Q+K) iff (Q+K) u< bitwidth(x)
34  // While we know that originally (Q+K) would not overflow
35  // (because 2 * (N-1) u<= iN -1), we have looked past extensions of
36  // shift amounts. so it may now overflow in smaller bitwidth.
37  // To ensure that does not happen, we need to ensure that the total maximal
38  // shift amount is still representable in that smaller bit width.
39  unsigned MaximalPossibleTotalShiftAmount =
40  (Sh0->getType()->getScalarSizeInBits() - 1) +
41  (Sh1->getType()->getScalarSizeInBits() - 1);
42  APInt MaximalRepresentableShiftAmount =
44  return MaximalRepresentableShiftAmount.uge(MaximalPossibleTotalShiftAmount);
45 }
46 
47 // Given pattern:
48 // (x shiftopcode Q) shiftopcode K
49 // we should rewrite it as
50 // x shiftopcode (Q+K) iff (Q+K) u< bitwidth(x) and
51 //
52 // This is valid for any shift, but they must be identical, and we must be
53 // careful in case we have (zext(Q)+zext(K)) and look past extensions,
54 // (Q+K) must not overflow or else (Q+K) u< bitwidth(x) is bogus.
55 //
56 // AnalyzeForSignBitExtraction indicates that we will only analyze whether this
57 // pattern has any 2 right-shifts that sum to 1 less than original bit width.
59  BinaryOperator *Sh0, const SimplifyQuery &SQ,
60  bool AnalyzeForSignBitExtraction) {
61  // Look for a shift of some instruction, ignore zext of shift amount if any.
62  Instruction *Sh0Op0;
63  Value *ShAmt0;
64  if (!match(Sh0,
65  m_Shift(m_Instruction(Sh0Op0), m_ZExtOrSelf(m_Value(ShAmt0)))))
66  return nullptr;
67 
68  // If there is a truncation between the two shifts, we must make note of it
69  // and look through it. The truncation imposes additional constraints on the
70  // transform.
71  Instruction *Sh1;
72  Value *Trunc = nullptr;
73  match(Sh0Op0,
75  m_Instruction(Sh1)));
76 
77  // Inner shift: (x shiftopcode ShAmt1)
78  // Like with other shift, ignore zext of shift amount if any.
79  Value *X, *ShAmt1;
80  if (!match(Sh1, m_Shift(m_Value(X), m_ZExtOrSelf(m_Value(ShAmt1)))))
81  return nullptr;
82 
83  // Verify that it would be safe to try to add those two shift amounts.
84  if (!canTryToConstantAddTwoShiftAmounts(Sh0, ShAmt0, Sh1, ShAmt1))
85  return nullptr;
86 
87  // We are only looking for signbit extraction if we have two right shifts.
88  bool HadTwoRightShifts = match(Sh0, m_Shr(m_Value(), m_Value())) &&
89  match(Sh1, m_Shr(m_Value(), m_Value()));
90  // ... and if it's not two right-shifts, we know the answer already.
91  if (AnalyzeForSignBitExtraction && !HadTwoRightShifts)
92  return nullptr;
93 
94  // The shift opcodes must be identical, unless we are just checking whether
95  // this pattern can be interpreted as a sign-bit-extraction.
96  Instruction::BinaryOps ShiftOpcode = Sh0->getOpcode();
97  bool IdenticalShOpcodes = Sh0->getOpcode() == Sh1->getOpcode();
98  if (!IdenticalShOpcodes && !AnalyzeForSignBitExtraction)
99  return nullptr;
100 
101  // If we saw truncation, we'll need to produce extra instruction,
102  // and for that one of the operands of the shift must be one-use,
103  // unless of course we don't actually plan to produce any instructions here.
104  if (Trunc && !AnalyzeForSignBitExtraction &&
105  !match(Sh0, m_c_BinOp(m_OneUse(m_Value()), m_Value())))
106  return nullptr;
107 
108  // Can we fold (ShAmt0+ShAmt1) ?
109  auto *NewShAmt = dyn_cast_or_null<Constant>(
110  simplifyAddInst(ShAmt0, ShAmt1, /*isNSW=*/false, /*isNUW=*/false,
111  SQ.getWithInstruction(Sh0)));
112  if (!NewShAmt)
113  return nullptr; // Did not simplify.
114  unsigned NewShAmtBitWidth = NewShAmt->getType()->getScalarSizeInBits();
115  unsigned XBitWidth = X->getType()->getScalarSizeInBits();
116  // Is the new shift amount smaller than the bit width of inner/new shift?
117  if (!match(NewShAmt, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT,
118  APInt(NewShAmtBitWidth, XBitWidth))))
119  return nullptr; // FIXME: could perform constant-folding.
120 
121  // If there was a truncation, and we have a right-shift, we can only fold if
122  // we are left with the original sign bit. Likewise, if we were just checking
123  // that this is a sighbit extraction, this is the place to check it.
124  // FIXME: zero shift amount is also legal here, but we can't *easily* check
125  // more than one predicate so it's not really worth it.
126  if (HadTwoRightShifts && (Trunc || AnalyzeForSignBitExtraction)) {
127  // If it's not a sign bit extraction, then we're done.
128  if (!match(NewShAmt,
129  m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ,
130  APInt(NewShAmtBitWidth, XBitWidth - 1))))
131  return nullptr;
132  // If it is, and that was the question, return the base value.
133  if (AnalyzeForSignBitExtraction)
134  return X;
135  }
136 
137  assert(IdenticalShOpcodes && "Should not get here with different shifts.");
138 
139  // All good, we can do this fold.
140  NewShAmt = ConstantExpr::getZExtOrBitCast(NewShAmt, X->getType());
141 
142  BinaryOperator *NewShift = BinaryOperator::Create(ShiftOpcode, X, NewShAmt);
143 
144  // The flags can only be propagated if there wasn't a trunc.
145  if (!Trunc) {
146  // If the pattern did not involve trunc, and both of the original shifts
147  // had the same flag set, preserve the flag.
148  if (ShiftOpcode == Instruction::BinaryOps::Shl) {
149  NewShift->setHasNoUnsignedWrap(Sh0->hasNoUnsignedWrap() &&
150  Sh1->hasNoUnsignedWrap());
151  NewShift->setHasNoSignedWrap(Sh0->hasNoSignedWrap() &&
152  Sh1->hasNoSignedWrap());
153  } else {
154  NewShift->setIsExact(Sh0->isExact() && Sh1->isExact());
155  }
156  }
157 
158  Instruction *Ret = NewShift;
159  if (Trunc) {
160  Builder.Insert(NewShift);
161  Ret = CastInst::Create(Instruction::Trunc, NewShift, Sh0->getType());
162  }
163 
164  return Ret;
165 }
166 
167 // If we have some pattern that leaves only some low bits set, and then performs
168 // left-shift of those bits, if none of the bits that are left after the final
169 // shift are modified by the mask, we can omit the mask.
170 //
171 // There are many variants to this pattern:
172 // a) (x & ((1 << MaskShAmt) - 1)) << ShiftShAmt
173 // b) (x & (~(-1 << MaskShAmt))) << ShiftShAmt
174 // c) (x & (-1 l>> MaskShAmt)) << ShiftShAmt
175 // d) (x & ((-1 << MaskShAmt) l>> MaskShAmt)) << ShiftShAmt
176 // e) ((x << MaskShAmt) l>> MaskShAmt) << ShiftShAmt
177 // f) ((x << MaskShAmt) a>> MaskShAmt) << ShiftShAmt
178 // All these patterns can be simplified to just:
179 // x << ShiftShAmt
180 // iff:
181 // a,b) (MaskShAmt+ShiftShAmt) u>= bitwidth(x)
182 // c,d,e,f) (ShiftShAmt-MaskShAmt) s>= 0 (i.e. ShiftShAmt u>= MaskShAmt)
183 static Instruction *
185  const SimplifyQuery &Q,
187  assert(OuterShift->getOpcode() == Instruction::BinaryOps::Shl &&
188  "The input must be 'shl'!");
189 
190  Value *Masked, *ShiftShAmt;
191  match(OuterShift,
192  m_Shift(m_Value(Masked), m_ZExtOrSelf(m_Value(ShiftShAmt))));
193 
194  // *If* there is a truncation between an outer shift and a possibly-mask,
195  // then said truncation *must* be one-use, else we can't perform the fold.
196  Value *Trunc;
197  if (match(Masked, m_CombineAnd(m_Trunc(m_Value(Masked)), m_Value(Trunc))) &&
198  !Trunc->hasOneUse())
199  return nullptr;
200 
201  Type *NarrowestTy = OuterShift->getType();
202  Type *WidestTy = Masked->getType();
203  bool HadTrunc = WidestTy != NarrowestTy;
204 
205  // The mask must be computed in a type twice as wide to ensure
206  // that no bits are lost if the sum-of-shifts is wider than the base type.
207  Type *ExtendedTy = WidestTy->getExtendedType();
208 
209  Value *MaskShAmt;
210 
211  // ((1 << MaskShAmt) - 1)
212  auto MaskA = m_Add(m_Shl(m_One(), m_Value(MaskShAmt)), m_AllOnes());
213  // (~(-1 << maskNbits))
214  auto MaskB = m_Xor(m_Shl(m_AllOnes(), m_Value(MaskShAmt)), m_AllOnes());
215  // (-1 l>> MaskShAmt)
216  auto MaskC = m_LShr(m_AllOnes(), m_Value(MaskShAmt));
217  // ((-1 << MaskShAmt) l>> MaskShAmt)
218  auto MaskD =
219  m_LShr(m_Shl(m_AllOnes(), m_Value(MaskShAmt)), m_Deferred(MaskShAmt));
220 
221  Value *X;
222  Constant *NewMask;
223 
224  if (match(Masked, m_c_And(m_CombineOr(MaskA, MaskB), m_Value(X)))) {
225  // Peek through an optional zext of the shift amount.
226  match(MaskShAmt, m_ZExtOrSelf(m_Value(MaskShAmt)));
227 
228  // Verify that it would be safe to try to add those two shift amounts.
229  if (!canTryToConstantAddTwoShiftAmounts(OuterShift, ShiftShAmt, Masked,
230  MaskShAmt))
231  return nullptr;
232 
233  // Can we simplify (MaskShAmt+ShiftShAmt) ?
234  auto *SumOfShAmts = dyn_cast_or_null<Constant>(simplifyAddInst(
235  MaskShAmt, ShiftShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q));
236  if (!SumOfShAmts)
237  return nullptr; // Did not simplify.
238  // In this pattern SumOfShAmts correlates with the number of low bits
239  // that shall remain in the root value (OuterShift).
240 
241  // An extend of an undef value becomes zero because the high bits are never
242  // completely unknown. Replace the `undef` shift amounts with final
243  // shift bitwidth to ensure that the value remains undef when creating the
244  // subsequent shift op.
245  SumOfShAmts = Constant::replaceUndefsWith(
246  SumOfShAmts, ConstantInt::get(SumOfShAmts->getType()->getScalarType(),
247  ExtendedTy->getScalarSizeInBits()));
248  auto *ExtendedSumOfShAmts = ConstantExpr::getZExt(SumOfShAmts, ExtendedTy);
249  // And compute the mask as usual: ~(-1 << (SumOfShAmts))
250  auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy);
251  auto *ExtendedInvertedMask =
252  ConstantExpr::getShl(ExtendedAllOnes, ExtendedSumOfShAmts);
253  NewMask = ConstantExpr::getNot(ExtendedInvertedMask);
254  } else if (match(Masked, m_c_And(m_CombineOr(MaskC, MaskD), m_Value(X))) ||
255  match(Masked, m_Shr(m_Shl(m_Value(X), m_Value(MaskShAmt)),
256  m_Deferred(MaskShAmt)))) {
257  // Peek through an optional zext of the shift amount.
258  match(MaskShAmt, m_ZExtOrSelf(m_Value(MaskShAmt)));
259 
260  // Verify that it would be safe to try to add those two shift amounts.
261  if (!canTryToConstantAddTwoShiftAmounts(OuterShift, ShiftShAmt, Masked,
262  MaskShAmt))
263  return nullptr;
264 
265  // Can we simplify (ShiftShAmt-MaskShAmt) ?
266  auto *ShAmtsDiff = dyn_cast_or_null<Constant>(simplifySubInst(
267  ShiftShAmt, MaskShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q));
268  if (!ShAmtsDiff)
269  return nullptr; // Did not simplify.
270  // In this pattern ShAmtsDiff correlates with the number of high bits that
271  // shall be unset in the root value (OuterShift).
272 
273  // An extend of an undef value becomes zero because the high bits are never
274  // completely unknown. Replace the `undef` shift amounts with negated
275  // bitwidth of innermost shift to ensure that the value remains undef when
276  // creating the subsequent shift op.
277  unsigned WidestTyBitWidth = WidestTy->getScalarSizeInBits();
278  ShAmtsDiff = Constant::replaceUndefsWith(
279  ShAmtsDiff, ConstantInt::get(ShAmtsDiff->getType()->getScalarType(),
280  -WidestTyBitWidth));
281  auto *ExtendedNumHighBitsToClear = ConstantExpr::getZExt(
282  ConstantExpr::getSub(ConstantInt::get(ShAmtsDiff->getType(),
283  WidestTyBitWidth,
284  /*isSigned=*/false),
285  ShAmtsDiff),
286  ExtendedTy);
287  // And compute the mask as usual: (-1 l>> (NumHighBitsToClear))
288  auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy);
289  NewMask =
290  ConstantExpr::getLShr(ExtendedAllOnes, ExtendedNumHighBitsToClear);
291  } else
292  return nullptr; // Don't know anything about this pattern.
293 
294  NewMask = ConstantExpr::getTrunc(NewMask, NarrowestTy);
295 
296  // Does this mask has any unset bits? If not then we can just not apply it.
297  bool NeedMask = !match(NewMask, m_AllOnes());
298 
299  // If we need to apply a mask, there are several more restrictions we have.
300  if (NeedMask) {
301  // The old masking instruction must go away.
302  if (!Masked->hasOneUse())
303  return nullptr;
304  // The original "masking" instruction must not have been`ashr`.
305  if (match(Masked, m_AShr(m_Value(), m_Value())))
306  return nullptr;
307  }
308 
309  // If we need to apply truncation, let's do it first, since we can.
310  // We have already ensured that the old truncation will go away.
311  if (HadTrunc)
312  X = Builder.CreateTrunc(X, NarrowestTy);
313 
314  // No 'NUW'/'NSW'! We no longer know that we won't shift-out non-0 bits.
315  // We didn't change the Type of this outermost shift, so we can just do it.
316  auto *NewShift = BinaryOperator::Create(OuterShift->getOpcode(), X,
317  OuterShift->getOperand(1));
318  if (!NeedMask)
319  return NewShift;
320 
321  Builder.Insert(NewShift);
322  return BinaryOperator::Create(Instruction::And, NewShift, NewMask);
323 }
324 
325 /// If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/
326 /// shl) that itself has a shift-by-constant operand with identical opcode, we
327 /// may be able to convert that into 2 independent shifts followed by the logic
328 /// op. This eliminates a use of an intermediate value (reduces dependency
329 /// chain).
332  assert(I.isShift() && "Expected a shift as input");
333  auto *BinInst = dyn_cast<BinaryOperator>(I.getOperand(0));
334  if (!BinInst ||
335  (!BinInst->isBitwiseLogicOp() &&
336  BinInst->getOpcode() != Instruction::Add &&
337  BinInst->getOpcode() != Instruction::Sub) ||
338  !BinInst->hasOneUse())
339  return nullptr;
340 
341  Constant *C0, *C1;
342  if (!match(I.getOperand(1), m_Constant(C1)))
343  return nullptr;
344 
345  Instruction::BinaryOps ShiftOpcode = I.getOpcode();
346  // Transform for add/sub only works with shl.
347  if ((BinInst->getOpcode() == Instruction::Add ||
348  BinInst->getOpcode() == Instruction::Sub) &&
349  ShiftOpcode != Instruction::Shl)
350  return nullptr;
351 
352  Type *Ty = I.getType();
353 
354  // Find a matching one-use shift by constant. The fold is not valid if the sum
355  // of the shift values equals or exceeds bitwidth.
356  // TODO: Remove the one-use check if the other logic operand (Y) is constant.
357  Value *X, *Y;
358  auto matchFirstShift = [&](Value *V) {
359  APInt Threshold(Ty->getScalarSizeInBits(), Ty->getScalarSizeInBits());
360  return match(V,
361  m_OneUse(m_BinOp(ShiftOpcode, m_Value(X), m_Constant(C0)))) &&
364  };
365 
366  // Logic ops and Add are commutative, so check each operand for a match. Sub
367  // is not so we cannot reoder if we match operand(1) and need to keep the
368  // operands in their original positions.
369  bool FirstShiftIsOp1 = false;
370  if (matchFirstShift(BinInst->getOperand(0)))
371  Y = BinInst->getOperand(1);
372  else if (matchFirstShift(BinInst->getOperand(1))) {
373  Y = BinInst->getOperand(0);
374  FirstShiftIsOp1 = BinInst->getOpcode() == Instruction::Sub;
375  } else
376  return nullptr;
377 
378  // shift (binop (shift X, C0), Y), C1 -> binop (shift X, C0+C1), (shift Y, C1)
379  Constant *ShiftSumC = ConstantExpr::getAdd(C0, C1);
380  Value *NewShift1 = Builder.CreateBinOp(ShiftOpcode, X, ShiftSumC);
381  Value *NewShift2 = Builder.CreateBinOp(ShiftOpcode, Y, C1);
382  Value *Op1 = FirstShiftIsOp1 ? NewShift2 : NewShift1;
383  Value *Op2 = FirstShiftIsOp1 ? NewShift1 : NewShift2;
384  return BinaryOperator::Create(BinInst->getOpcode(), Op1, Op2);
385 }
386 
388  if (Instruction *Phi = foldBinopWithPhiOperands(I))
389  return Phi;
390 
391  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
392  assert(Op0->getType() == Op1->getType());
393  Type *Ty = I.getType();
394 
395  // If the shift amount is a one-use `sext`, we can demote it to `zext`.
396  Value *Y;
397  if (match(Op1, m_OneUse(m_SExt(m_Value(Y))))) {
398  Value *NewExt = Builder.CreateZExt(Y, Ty, Op1->getName());
399  return BinaryOperator::Create(I.getOpcode(), Op0, NewExt);
400  }
401 
402  // See if we can fold away this shift.
403  if (SimplifyDemandedInstructionBits(I))
404  return &I;
405 
406  // Try to fold constant and into select arguments.
407  if (isa<Constant>(Op0))
408  if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
409  if (Instruction *R = FoldOpIntoSelect(I, SI))
410  return R;
411 
412  if (Constant *CUI = dyn_cast<Constant>(Op1))
413  if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
414  return Res;
415 
416  if (auto *NewShift = cast_or_null<Instruction>(
417  reassociateShiftAmtsOfTwoSameDirectionShifts(&I, SQ)))
418  return NewShift;
419 
420  // Pre-shift a constant shifted by a variable amount with constant offset:
421  // C shift (A add nuw C1) --> (C shift C1) shift A
422  Value *A;
423  Constant *C, *C1;
424  if (match(Op0, m_Constant(C)) &&
425  match(Op1, m_NUWAdd(m_Value(A), m_Constant(C1)))) {
426  Value *NewC = Builder.CreateBinOp(I.getOpcode(), C, C1);
427  return BinaryOperator::Create(I.getOpcode(), NewC, A);
428  }
429 
430  unsigned BitWidth = Ty->getScalarSizeInBits();
431 
432  const APInt *AC, *AddC;
433  // Try to pre-shift a constant shifted by a variable amount added with a
434  // negative number:
435  // C << (X - AddC) --> (C >> AddC) << X
436  // and
437  // C >> (X - AddC) --> (C << AddC) >> X
438  if (match(Op0, m_APInt(AC)) && match(Op1, m_Add(m_Value(A), m_APInt(AddC))) &&
439  AddC->isNegative() && (-*AddC).ult(BitWidth)) {
440  assert(!AC->isZero() && "Expected simplify of shifted zero");
441  unsigned PosOffset = (-*AddC).getZExtValue();
442 
443  auto isSuitableForPreShift = [PosOffset, &I, AC]() {
444  switch (I.getOpcode()) {
445  default:
446  return false;
447  case Instruction::Shl:
448  return (I.hasNoSignedWrap() || I.hasNoUnsignedWrap()) &&
449  AC->eq(AC->lshr(PosOffset).shl(PosOffset));
450  case Instruction::LShr:
451  return I.isExact() && AC->eq(AC->shl(PosOffset).lshr(PosOffset));
452  case Instruction::AShr:
453  return I.isExact() && AC->eq(AC->shl(PosOffset).ashr(PosOffset));
454  }
455  };
456  if (isSuitableForPreShift()) {
457  Constant *NewC = ConstantInt::get(Ty, I.getOpcode() == Instruction::Shl
458  ? AC->lshr(PosOffset)
459  : AC->shl(PosOffset));
460  BinaryOperator *NewShiftOp =
461  BinaryOperator::Create(I.getOpcode(), NewC, A);
462  if (I.getOpcode() == Instruction::Shl) {
463  NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
464  } else {
465  NewShiftOp->setIsExact();
466  }
467  return NewShiftOp;
468  }
469  }
470 
471  // X shift (A srem C) -> X shift (A and (C - 1)) iff C is a power of 2.
472  // Because shifts by negative values (which could occur if A were negative)
473  // are undefined.
474  if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Constant(C))) &&
475  match(C, m_Power2())) {
476  // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't
477  // demand the sign bit (and many others) here??
479  Value *Rem = Builder.CreateAnd(A, Mask, Op1->getName());
480  return replaceOperand(I, 1, Rem);
481  }
482 
484  return Logic;
485 
486  return nullptr;
487 }
488 
489 /// Return true if we can simplify two logical (either left or right) shifts
490 /// that have constant shift amounts: OuterShift (InnerShift X, C1), C2.
491 static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl,
492  Instruction *InnerShift,
493  InstCombinerImpl &IC, Instruction *CxtI) {
494  assert(InnerShift->isLogicalShift() && "Unexpected instruction type");
495 
496  // We need constant scalar or constant splat shifts.
497  const APInt *InnerShiftConst;
498  if (!match(InnerShift->getOperand(1), m_APInt(InnerShiftConst)))
499  return false;
500 
501  // Two logical shifts in the same direction:
502  // shl (shl X, C1), C2 --> shl X, C1 + C2
503  // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
504  bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
505  if (IsInnerShl == IsOuterShl)
506  return true;
507 
508  // Equal shift amounts in opposite directions become bitwise 'and':
509  // lshr (shl X, C), C --> and X, C'
510  // shl (lshr X, C), C --> and X, C'
511  if (*InnerShiftConst == OuterShAmt)
512  return true;
513 
514  // If the 2nd shift is bigger than the 1st, we can fold:
515  // lshr (shl X, C1), C2 --> and (shl X, C1 - C2), C3
516  // shl (lshr X, C1), C2 --> and (lshr X, C1 - C2), C3
517  // but it isn't profitable unless we know the and'd out bits are already zero.
518  // Also, check that the inner shift is valid (less than the type width) or
519  // we'll crash trying to produce the bit mask for the 'and'.
520  unsigned TypeWidth = InnerShift->getType()->getScalarSizeInBits();
521  if (InnerShiftConst->ugt(OuterShAmt) && InnerShiftConst->ult(TypeWidth)) {
522  unsigned InnerShAmt = InnerShiftConst->getZExtValue();
523  unsigned MaskShift =
524  IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt;
525  APInt Mask = APInt::getLowBitsSet(TypeWidth, OuterShAmt) << MaskShift;
526  if (IC.MaskedValueIsZero(InnerShift->getOperand(0), Mask, 0, CxtI))
527  return true;
528  }
529 
530  return false;
531 }
532 
533 /// See if we can compute the specified value, but shifted logically to the left
534 /// or right by some number of bits. This should return true if the expression
535 /// can be computed for the same cost as the current expression tree. This is
536 /// used to eliminate extraneous shifting from things like:
537 /// %C = shl i128 %A, 64
538 /// %D = shl i128 %B, 96
539 /// %E = or i128 %C, %D
540 /// %F = lshr i128 %E, 64
541 /// where the client will ask if E can be computed shifted right by 64-bits. If
542 /// this succeeds, getShiftedValue() will be called to produce the value.
543 static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift,
544  InstCombinerImpl &IC, Instruction *CxtI) {
545  // We can always evaluate constants shifted.
546  if (isa<Constant>(V))
547  return true;
548 
549  Instruction *I = dyn_cast<Instruction>(V);
550  if (!I) return false;
551 
552  // We can't mutate something that has multiple uses: doing so would
553  // require duplicating the instruction in general, which isn't profitable.
554  if (!I->hasOneUse()) return false;
555 
556  switch (I->getOpcode()) {
557  default: return false;
558  case Instruction::And:
559  case Instruction::Or:
560  case Instruction::Xor:
561  // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
562  return canEvaluateShifted(I->getOperand(0), NumBits, IsLeftShift, IC, I) &&
563  canEvaluateShifted(I->getOperand(1), NumBits, IsLeftShift, IC, I);
564 
565  case Instruction::Shl:
566  case Instruction::LShr:
567  return canEvaluateShiftedShift(NumBits, IsLeftShift, I, IC, CxtI);
568 
569  case Instruction::Select: {
570  SelectInst *SI = cast<SelectInst>(I);
571  Value *TrueVal = SI->getTrueValue();
572  Value *FalseVal = SI->getFalseValue();
573  return canEvaluateShifted(TrueVal, NumBits, IsLeftShift, IC, SI) &&
574  canEvaluateShifted(FalseVal, NumBits, IsLeftShift, IC, SI);
575  }
576  case Instruction::PHI: {
577  // We can change a phi if we can change all operands. Note that we never
578  // get into trouble with cyclic PHIs here because we only consider
579  // instructions with a single use.
580  PHINode *PN = cast<PHINode>(I);
581  for (Value *IncValue : PN->incoming_values())
582  if (!canEvaluateShifted(IncValue, NumBits, IsLeftShift, IC, PN))
583  return false;
584  return true;
585  }
586  case Instruction::Mul: {
587  const APInt *MulConst;
588  // We can fold (shr (mul X, -(1 << C)), C) -> (and (neg X), C`)
589  return !IsLeftShift && match(I->getOperand(1), m_APInt(MulConst)) &&
590  MulConst->isNegatedPowerOf2() &&
591  MulConst->countTrailingZeros() == NumBits;
592  }
593  }
594 }
595 
596 /// Fold OuterShift (InnerShift X, C1), C2.
597 /// See canEvaluateShiftedShift() for the constraints on these instructions.
598 static Value *foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt,
599  bool IsOuterShl,
601  bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
602  Type *ShType = InnerShift->getType();
603  unsigned TypeWidth = ShType->getScalarSizeInBits();
604 
605  // We only accept shifts-by-a-constant in canEvaluateShifted().
606  const APInt *C1;
607  match(InnerShift->getOperand(1), m_APInt(C1));
608  unsigned InnerShAmt = C1->getZExtValue();
609 
610  // Change the shift amount and clear the appropriate IR flags.
611  auto NewInnerShift = [&](unsigned ShAmt) {
612  InnerShift->setOperand(1, ConstantInt::get(ShType, ShAmt));
613  if (IsInnerShl) {
614  InnerShift->setHasNoUnsignedWrap(false);
615  InnerShift->setHasNoSignedWrap(false);
616  } else {
617  InnerShift->setIsExact(false);
618  }
619  return InnerShift;
620  };
621 
622  // Two logical shifts in the same direction:
623  // shl (shl X, C1), C2 --> shl X, C1 + C2
624  // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
625  if (IsInnerShl == IsOuterShl) {
626  // If this is an oversized composite shift, then unsigned shifts get 0.
627  if (InnerShAmt + OuterShAmt >= TypeWidth)
628  return Constant::getNullValue(ShType);
629 
630  return NewInnerShift(InnerShAmt + OuterShAmt);
631  }
632 
633  // Equal shift amounts in opposite directions become bitwise 'and':
634  // lshr (shl X, C), C --> and X, C'
635  // shl (lshr X, C), C --> and X, C'
636  if (InnerShAmt == OuterShAmt) {
637  APInt Mask = IsInnerShl
638  ? APInt::getLowBitsSet(TypeWidth, TypeWidth - OuterShAmt)
639  : APInt::getHighBitsSet(TypeWidth, TypeWidth - OuterShAmt);
640  Value *And = Builder.CreateAnd(InnerShift->getOperand(0),
641  ConstantInt::get(ShType, Mask));
642  if (auto *AndI = dyn_cast<Instruction>(And)) {
643  AndI->moveBefore(InnerShift);
644  AndI->takeName(InnerShift);
645  }
646  return And;
647  }
648 
649  assert(InnerShAmt > OuterShAmt &&
650  "Unexpected opposite direction logical shift pair");
651 
652  // In general, we would need an 'and' for this transform, but
653  // canEvaluateShiftedShift() guarantees that the masked-off bits are not used.
654  // lshr (shl X, C1), C2 --> shl X, C1 - C2
655  // shl (lshr X, C1), C2 --> lshr X, C1 - C2
656  return NewInnerShift(InnerShAmt - OuterShAmt);
657 }
658 
659 /// When canEvaluateShifted() returns true for an expression, this function
660 /// inserts the new computation that produces the shifted value.
661 static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift,
662  InstCombinerImpl &IC, const DataLayout &DL) {
663  // We can always evaluate constants shifted.
664  if (Constant *C = dyn_cast<Constant>(V)) {
665  if (isLeftShift)
666  return IC.Builder.CreateShl(C, NumBits);
667  else
668  return IC.Builder.CreateLShr(C, NumBits);
669  }
670 
671  Instruction *I = cast<Instruction>(V);
672  IC.addToWorklist(I);
673 
674  switch (I->getOpcode()) {
675  default: llvm_unreachable("Inconsistency with CanEvaluateShifted");
676  case Instruction::And:
677  case Instruction::Or:
678  case Instruction::Xor:
679  // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
680  I->setOperand(
681  0, getShiftedValue(I->getOperand(0), NumBits, isLeftShift, IC, DL));
682  I->setOperand(
683  1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
684  return I;
685 
686  case Instruction::Shl:
687  case Instruction::LShr:
688  return foldShiftedShift(cast<BinaryOperator>(I), NumBits, isLeftShift,
689  IC.Builder);
690 
691  case Instruction::Select:
692  I->setOperand(
693  1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
694  I->setOperand(
695  2, getShiftedValue(I->getOperand(2), NumBits, isLeftShift, IC, DL));
696  return I;
697  case Instruction::PHI: {
698  // We can change a phi if we can change all operands. Note that we never
699  // get into trouble with cyclic PHIs here because we only consider
700  // instructions with a single use.
701  PHINode *PN = cast<PHINode>(I);
702  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
704  isLeftShift, IC, DL));
705  return PN;
706  }
707  case Instruction::Mul: {
708  assert(!isLeftShift && "Unexpected shift direction!");
709  auto *Neg = BinaryOperator::CreateNeg(I->getOperand(0));
710  IC.InsertNewInstWith(Neg, *I);
711  unsigned TypeWidth = I->getType()->getScalarSizeInBits();
712  APInt Mask = APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits);
713  auto *And = BinaryOperator::CreateAnd(Neg,
714  ConstantInt::get(I->getType(), Mask));
715  And->takeName(I);
716  return IC.InsertNewInstWith(And, *I);
717  }
718  }
719 }
720 
721 // If this is a bitwise operator or add with a constant RHS we might be able
722 // to pull it through a shift.
724  BinaryOperator *BO) {
725  switch (BO->getOpcode()) {
726  default:
727  return false; // Do not perform transform!
728  case Instruction::Add:
729  return Shift.getOpcode() == Instruction::Shl;
730  case Instruction::Or:
731  case Instruction::And:
732  return true;
733  case Instruction::Xor:
734  // Do not change a 'not' of logical shift because that would create a normal
735  // 'xor'. The 'not' is likely better for analysis, SCEV, and codegen.
736  return !(Shift.isLogicalShift() && match(BO, m_Not(m_Value())));
737  }
738 }
739 
741  BinaryOperator &I) {
742  // (C2 << X) << C1 --> (C2 << C1) << X
743  // (C2 >> X) >> C1 --> (C2 >> C1) >> X
744  Constant *C2;
745  Value *X;
746  if (match(Op0, m_BinOp(I.getOpcode(), m_Constant(C2), m_Value(X))))
747  return BinaryOperator::Create(
748  I.getOpcode(), Builder.CreateBinOp(I.getOpcode(), C2, C1), X);
749 
750  bool IsLeftShift = I.getOpcode() == Instruction::Shl;
751  Type *Ty = I.getType();
752  unsigned TypeBits = Ty->getScalarSizeInBits();
753 
754  // (X / +DivC) >> (Width - 1) --> ext (X <= -DivC)
755  // (X / -DivC) >> (Width - 1) --> ext (X >= +DivC)
756  const APInt *DivC;
757  if (!IsLeftShift && match(C1, m_SpecificIntAllowUndef(TypeBits - 1)) &&
758  match(Op0, m_SDiv(m_Value(X), m_APInt(DivC))) && !DivC->isZero() &&
759  !DivC->isMinSignedValue()) {
760  Constant *NegDivC = ConstantInt::get(Ty, -(*DivC));
761  ICmpInst::Predicate Pred =
763  Value *Cmp = Builder.CreateICmp(Pred, X, NegDivC);
764  auto ExtOpcode = (I.getOpcode() == Instruction::AShr) ? Instruction::SExt
765  : Instruction::ZExt;
766  return CastInst::Create(ExtOpcode, Cmp, Ty);
767  }
768 
769  const APInt *Op1C;
770  if (!match(C1, m_APInt(Op1C)))
771  return nullptr;
772 
773  assert(!Op1C->uge(TypeBits) &&
774  "Shift over the type width should have been removed already");
775 
776  // See if we can propagate this shift into the input, this covers the trivial
777  // cast of lshr(shl(x,c1),c2) as well as other more complex cases.
778  if (I.getOpcode() != Instruction::AShr &&
779  canEvaluateShifted(Op0, Op1C->getZExtValue(), IsLeftShift, *this, &I)) {
780  LLVM_DEBUG(
781  dbgs() << "ICE: GetShiftedValue propagating shift through expression"
782  " to eliminate shift:\n IN: "
783  << *Op0 << "\n SH: " << I << "\n");
784 
785  return replaceInstUsesWith(
786  I, getShiftedValue(Op0, Op1C->getZExtValue(), IsLeftShift, *this, DL));
787  }
788 
789  if (Instruction *FoldedShift = foldBinOpIntoSelectOrPhi(I))
790  return FoldedShift;
791 
792  if (!Op0->hasOneUse())
793  return nullptr;
794 
795  if (auto *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
796  // If the operand is a bitwise operator with a constant RHS, and the
797  // shift is the only use, we can pull it out of the shift.
798  const APInt *Op0C;
799  if (match(Op0BO->getOperand(1), m_APInt(Op0C))) {
800  if (canShiftBinOpWithConstantRHS(I, Op0BO)) {
801  Value *NewRHS =
802  Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(1), C1);
803 
804  Value *NewShift =
805  Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), C1);
806  NewShift->takeName(Op0BO);
807 
808  return BinaryOperator::Create(Op0BO->getOpcode(), NewShift, NewRHS);
809  }
810  }
811  }
812 
813  // If we have a select that conditionally executes some binary operator,
814  // see if we can pull it the select and operator through the shift.
815  //
816  // For example, turning:
817  // shl (select C, (add X, C1), X), C2
818  // Into:
819  // Y = shl X, C2
820  // select C, (add Y, C1 << C2), Y
821  Value *Cond;
822  BinaryOperator *TBO;
823  Value *FalseVal;
824  if (match(Op0, m_Select(m_Value(Cond), m_OneUse(m_BinOp(TBO)),
825  m_Value(FalseVal)))) {
826  const APInt *C;
827  if (!isa<Constant>(FalseVal) && TBO->getOperand(0) == FalseVal &&
828  match(TBO->getOperand(1), m_APInt(C)) &&
830  Value *NewRHS =
831  Builder.CreateBinOp(I.getOpcode(), TBO->getOperand(1), C1);
832 
833  Value *NewShift = Builder.CreateBinOp(I.getOpcode(), FalseVal, C1);
834  Value *NewOp = Builder.CreateBinOp(TBO->getOpcode(), NewShift, NewRHS);
835  return SelectInst::Create(Cond, NewOp, NewShift);
836  }
837  }
838 
839  BinaryOperator *FBO;
840  Value *TrueVal;
842  m_OneUse(m_BinOp(FBO))))) {
843  const APInt *C;
844  if (!isa<Constant>(TrueVal) && FBO->getOperand(0) == TrueVal &&
845  match(FBO->getOperand(1), m_APInt(C)) &&
847  Value *NewRHS =
848  Builder.CreateBinOp(I.getOpcode(), FBO->getOperand(1), C1);
849 
850  Value *NewShift = Builder.CreateBinOp(I.getOpcode(), TrueVal, C1);
851  Value *NewOp = Builder.CreateBinOp(FBO->getOpcode(), NewShift, NewRHS);
852  return SelectInst::Create(Cond, NewShift, NewOp);
853  }
854  }
855 
856  return nullptr;
857 }
858 
859 // Tries to perform
860 // (lshr (add (zext X), (zext Y)), K)
861 // -> (icmp ult (add X, Y), X)
862 // where
863 // - The add's operands are zexts from a K-bits integer to a bigger type.
864 // - The add is only used by the shr, or by iK (or narrower) truncates.
865 // - The lshr type has more than 2 bits (other types are boolean math).
866 // - K > 1
867 // note that
868 // - The resulting add cannot have nuw/nsw, else on overflow we get a
869 // poison value and the transform isn't legal anymore.
870 Instruction *InstCombinerImpl::foldLShrOverflowBit(BinaryOperator &I) {
871  assert(I.getOpcode() == Instruction::LShr);
872 
873  Value *Add = I.getOperand(0);
874  Value *ShiftAmt = I.getOperand(1);
875  Type *Ty = I.getType();
876 
877  if (Ty->getScalarSizeInBits() < 3)
878  return nullptr;
879 
880  const APInt *ShAmtAPInt = nullptr;
881  Value *X = nullptr, *Y = nullptr;
882  if (!match(ShiftAmt, m_APInt(ShAmtAPInt)) ||
883  !match(Add,
885  return nullptr;
886 
887  const unsigned ShAmt = ShAmtAPInt->getZExtValue();
888  if (ShAmt == 1)
889  return nullptr;
890 
891  // X/Y are zexts from `ShAmt`-sized ints.
892  if (X->getType()->getScalarSizeInBits() != ShAmt ||
893  Y->getType()->getScalarSizeInBits() != ShAmt)
894  return nullptr;
895 
896  // Make sure that `Add` is only used by `I` and `ShAmt`-truncates.
897  if (!Add->hasOneUse()) {
898  for (User *U : Add->users()) {
899  if (U == &I)
900  continue;
901 
902  TruncInst *Trunc = dyn_cast<TruncInst>(U);
903  if (!Trunc || Trunc->getType()->getScalarSizeInBits() > ShAmt)
904  return nullptr;
905  }
906  }
907 
908  // Insert at Add so that the newly created `NarrowAdd` will dominate it's
909  // users (i.e. `Add`'s users).
910  Instruction *AddInst = cast<Instruction>(Add);
911  Builder.SetInsertPoint(AddInst);
912 
913  Value *NarrowAdd = Builder.CreateAdd(X, Y, "add.narrowed");
914  Value *Overflow =
915  Builder.CreateICmpULT(NarrowAdd, X, "add.narrowed.overflow");
916 
917  // Replace the uses of the original add with a zext of the
918  // NarrowAdd's result. Note that all users at this stage are known to
919  // be ShAmt-sized truncs, or the lshr itself.
920  if (!Add->hasOneUse())
921  replaceInstUsesWith(*AddInst, Builder.CreateZExt(NarrowAdd, Ty));
922 
923  // Replace the LShr with a zext of the overflow check.
924  return new ZExtInst(Overflow, Ty);
925 }
926 
928  const SimplifyQuery Q = SQ.getWithInstruction(&I);
929 
930  if (Value *V = simplifyShlInst(I.getOperand(0), I.getOperand(1),
931  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(), Q))
932  return replaceInstUsesWith(I, V);
933 
934  if (Instruction *X = foldVectorBinop(I))
935  return X;
936 
937  if (Instruction *V = commonShiftTransforms(I))
938  return V;
939 
941  return V;
942 
943  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
944  Type *Ty = I.getType();
945  unsigned BitWidth = Ty->getScalarSizeInBits();
946 
947  const APInt *C;
948  if (match(Op1, m_APInt(C))) {
949  unsigned ShAmtC = C->getZExtValue();
950 
951  // shl (zext X), C --> zext (shl X, C)
952  // This is only valid if X would have zeros shifted out.
953  Value *X;
954  if (match(Op0, m_OneUse(m_ZExt(m_Value(X))))) {
955  unsigned SrcWidth = X->getType()->getScalarSizeInBits();
956  if (ShAmtC < SrcWidth &&
957  MaskedValueIsZero(X, APInt::getHighBitsSet(SrcWidth, ShAmtC), 0, &I))
958  return new ZExtInst(Builder.CreateShl(X, ShAmtC), Ty);
959  }
960 
961  // (X >> C) << C --> X & (-1 << C)
962  if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1)))) {
964  return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));
965  }
966 
967  const APInt *C1;
968  if (match(Op0, m_Exact(m_Shr(m_Value(X), m_APInt(C1)))) &&
969  C1->ult(BitWidth)) {
970  unsigned ShrAmt = C1->getZExtValue();
971  if (ShrAmt < ShAmtC) {
972  // If C1 < C: (X >>?,exact C1) << C --> X << (C - C1)
973  Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt);
974  auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
975  NewShl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
976  NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
977  return NewShl;
978  }
979  if (ShrAmt > ShAmtC) {
980  // If C1 > C: (X >>?exact C1) << C --> X >>?exact (C1 - C)
981  Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC);
982  auto *NewShr = BinaryOperator::Create(
983  cast<BinaryOperator>(Op0)->getOpcode(), X, ShiftDiff);
984  NewShr->setIsExact(true);
985  return NewShr;
986  }
987  }
988 
989  if (match(Op0, m_OneUse(m_Shr(m_Value(X), m_APInt(C1)))) &&
990  C1->ult(BitWidth)) {
991  unsigned ShrAmt = C1->getZExtValue();
992  if (ShrAmt < ShAmtC) {
993  // If C1 < C: (X >>? C1) << C --> (X << (C - C1)) & (-1 << C)
994  Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt);
995  auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
996  NewShl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
997  NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
998  Builder.Insert(NewShl);
1000  return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask));
1001  }
1002  if (ShrAmt > ShAmtC) {
1003  // If C1 > C: (X >>? C1) << C --> (X >>? (C1 - C)) & (-1 << C)
1004  Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC);
1005  auto *OldShr = cast<BinaryOperator>(Op0);
1006  auto *NewShr =
1007  BinaryOperator::Create(OldShr->getOpcode(), X, ShiftDiff);
1008  NewShr->setIsExact(OldShr->isExact());
1009  Builder.Insert(NewShr);
1011  return BinaryOperator::CreateAnd(NewShr, ConstantInt::get(Ty, Mask));
1012  }
1013  }
1014 
1015  // Similar to above, but look through an intermediate trunc instruction.
1016  BinaryOperator *Shr;
1017  if (match(Op0, m_OneUse(m_Trunc(m_OneUse(m_BinOp(Shr))))) &&
1018  match(Shr, m_Shr(m_Value(X), m_APInt(C1)))) {
1019  // The larger shift direction survives through the transform.
1020  unsigned ShrAmtC = C1->getZExtValue();
1021  unsigned ShDiff = ShrAmtC > ShAmtC ? ShrAmtC - ShAmtC : ShAmtC - ShrAmtC;
1022  Constant *ShiftDiffC = ConstantInt::get(X->getType(), ShDiff);
1023  auto ShiftOpc = ShrAmtC > ShAmtC ? Shr->getOpcode() : Instruction::Shl;
1024 
1025  // If C1 > C:
1026  // (trunc (X >> C1)) << C --> (trunc (X >> (C1 - C))) && (-1 << C)
1027  // If C > C1:
1028  // (trunc (X >> C1)) << C --> (trunc (X << (C - C1))) && (-1 << C)
1029  Value *NewShift = Builder.CreateBinOp(ShiftOpc, X, ShiftDiffC, "sh.diff");
1030  Value *Trunc = Builder.CreateTrunc(NewShift, Ty, "tr.sh.diff");
1032  return BinaryOperator::CreateAnd(Trunc, ConstantInt::get(Ty, Mask));
1033  }
1034 
1035  if (match(Op0, m_Shl(m_Value(X), m_APInt(C1))) && C1->ult(BitWidth)) {
1036  unsigned AmtSum = ShAmtC + C1->getZExtValue();
1037  // Oversized shifts are simplified to zero in InstSimplify.
1038  if (AmtSum < BitWidth)
1039  // (X << C1) << C2 --> X << (C1 + C2)
1040  return BinaryOperator::CreateShl(X, ConstantInt::get(Ty, AmtSum));
1041  }
1042 
1043  // If we have an opposite shift by the same amount, we may be able to
1044  // reorder binops and shifts to eliminate math/logic.
1045  auto isSuitableBinOpcode = [](Instruction::BinaryOps BinOpcode) {
1046  switch (BinOpcode) {
1047  default:
1048  return false;
1049  case Instruction::Add:
1050  case Instruction::And:
1051  case Instruction::Or:
1052  case Instruction::Xor:
1053  case Instruction::Sub:
1054  // NOTE: Sub is not commutable and the tranforms below may not be valid
1055  // when the shift-right is operand 1 (RHS) of the sub.
1056  return true;
1057  }
1058  };
1059  BinaryOperator *Op0BO;
1060  if (match(Op0, m_OneUse(m_BinOp(Op0BO))) &&
1061  isSuitableBinOpcode(Op0BO->getOpcode())) {
1062  // Commute so shift-right is on LHS of the binop.
1063  // (Y bop (X >> C)) << C -> ((X >> C) bop Y) << C
1064  // (Y bop ((X >> C) & CC)) << C -> (((X >> C) & CC) bop Y) << C
1065  Value *Shr = Op0BO->getOperand(0);
1066  Value *Y = Op0BO->getOperand(1);
1067  Value *X;
1068  const APInt *CC;
1069  if (Op0BO->isCommutative() && Y->hasOneUse() &&
1070  (match(Y, m_Shr(m_Value(), m_Specific(Op1))) ||
1072  m_APInt(CC)))))
1073  std::swap(Shr, Y);
1074 
1075  // ((X >> C) bop Y) << C -> (X bop (Y << C)) & (~0 << C)
1076  if (match(Shr, m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))))) {
1077  // Y << C
1078  Value *YS = Builder.CreateShl(Y, Op1, Op0BO->getName());
1079  // (X bop (Y << C))
1080  Value *B =
1081  Builder.CreateBinOp(Op0BO->getOpcode(), X, YS, Shr->getName());
1082  unsigned Op1Val = C->getLimitedValue(BitWidth);
1085  return BinaryOperator::CreateAnd(B, Mask);
1086  }
1087 
1088  // (((X >> C) & CC) bop Y) << C -> (X & (CC << C)) bop (Y << C)
1089  if (match(Shr,
1091  m_APInt(CC))))) {
1092  // Y << C
1093  Value *YS = Builder.CreateShl(Y, Op1, Op0BO->getName());
1094  // X & (CC << C)
1095  Value *M = Builder.CreateAnd(X, ConstantInt::get(Ty, CC->shl(*C)),
1096  X->getName() + ".mask");
1097  return BinaryOperator::Create(Op0BO->getOpcode(), M, YS);
1098  }
1099  }
1100 
1101  // (C1 - X) << C --> (C1 << C) - (X << C)
1102  if (match(Op0, m_OneUse(m_Sub(m_APInt(C1), m_Value(X))))) {
1103  Constant *NewLHS = ConstantInt::get(Ty, C1->shl(*C));
1104  Value *NewShift = Builder.CreateShl(X, Op1);
1105  return BinaryOperator::CreateSub(NewLHS, NewShift);
1106  }
1107 
1108  // If the shifted-out value is known-zero, then this is a NUW shift.
1109  if (!I.hasNoUnsignedWrap() &&
1111  &I)) {
1112  I.setHasNoUnsignedWrap();
1113  return &I;
1114  }
1115 
1116  // If the shifted-out value is all signbits, then this is a NSW shift.
1117  if (!I.hasNoSignedWrap() && ComputeNumSignBits(Op0, 0, &I) > ShAmtC) {
1118  I.setHasNoSignedWrap();
1119  return &I;
1120  }
1121  }
1122 
1123  // Transform (x >> y) << y to x & (-1 << y)
1124  // Valid for any type of right-shift.
1125  Value *X;
1126  if (match(Op0, m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))))) {
1127  Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
1128  Value *Mask = Builder.CreateShl(AllOnes, Op1);
1129  return BinaryOperator::CreateAnd(Mask, X);
1130  }
1131 
1132  Constant *C1;
1133  if (match(Op1, m_Constant(C1))) {
1134  Constant *C2;
1135  Value *X;
1136  // (X * C2) << C1 --> X * (C2 << C1)
1137  if (match(Op0, m_Mul(m_Value(X), m_Constant(C2))))
1139 
1140  // shl (zext i1 X), C1 --> select (X, 1 << C1, 0)
1141  if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1142  auto *NewC = ConstantExpr::getShl(ConstantInt::get(Ty, 1), C1);
1143  return SelectInst::Create(X, NewC, ConstantInt::getNullValue(Ty));
1144  }
1145  }
1146 
1147  if (match(Op0, m_One())) {
1148  // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1
1149  if (match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X))))
1150  return BinaryOperator::CreateLShr(
1152 
1153  // The only way to shift out the 1 is with an over-shift, so that would
1154  // be poison with or without "nuw". Undef is excluded because (undef << X)
1155  // is not undef (it is zero).
1156  Constant *ConstantOne = cast<Constant>(Op0);
1157  if (!I.hasNoUnsignedWrap() && !ConstantOne->containsUndefElement()) {
1158  I.setHasNoUnsignedWrap();
1159  return &I;
1160  }
1161  }
1162 
1163  return nullptr;
1164 }
1165 
1167  if (Value *V = simplifyLShrInst(I.getOperand(0), I.getOperand(1), I.isExact(),
1168  SQ.getWithInstruction(&I)))
1169  return replaceInstUsesWith(I, V);
1170 
1171  if (Instruction *X = foldVectorBinop(I))
1172  return X;
1173 
1174  if (Instruction *R = commonShiftTransforms(I))
1175  return R;
1176 
1177  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1178  Type *Ty = I.getType();
1179  Value *X;
1180  const APInt *C;
1181  unsigned BitWidth = Ty->getScalarSizeInBits();
1182 
1183  // (iN (~X) u>> (N - 1)) --> zext (X > -1)
1184  if (match(Op0, m_OneUse(m_Not(m_Value(X)))) &&
1186  return new ZExtInst(Builder.CreateIsNotNeg(X, "isnotneg"), Ty);
1187 
1188  if (match(Op1, m_APInt(C))) {
1189  unsigned ShAmtC = C->getZExtValue();
1190  auto *II = dyn_cast<IntrinsicInst>(Op0);
1191  if (II && isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == ShAmtC &&
1192  (II->getIntrinsicID() == Intrinsic::ctlz ||
1193  II->getIntrinsicID() == Intrinsic::cttz ||
1194  II->getIntrinsicID() == Intrinsic::ctpop)) {
1195  // ctlz.i32(x)>>5 --> zext(x == 0)
1196  // cttz.i32(x)>>5 --> zext(x == 0)
1197  // ctpop.i32(x)>>5 --> zext(x == -1)
1198  bool IsPop = II->getIntrinsicID() == Intrinsic::ctpop;
1199  Constant *RHS = ConstantInt::getSigned(Ty, IsPop ? -1 : 0);
1200  Value *Cmp = Builder.CreateICmpEQ(II->getArgOperand(0), RHS);
1201  return new ZExtInst(Cmp, Ty);
1202  }
1203 
1204  Value *X;
1205  const APInt *C1;
1206  if (match(Op0, m_Shl(m_Value(X), m_APInt(C1))) && C1->ult(BitWidth)) {
1207  if (C1->ult(ShAmtC)) {
1208  unsigned ShlAmtC = C1->getZExtValue();
1209  Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShlAmtC);
1210  if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
1211  // (X <<nuw C1) >>u C --> X >>u (C - C1)
1212  auto *NewLShr = BinaryOperator::CreateLShr(X, ShiftDiff);
1213  NewLShr->setIsExact(I.isExact());
1214  return NewLShr;
1215  }
1216  if (Op0->hasOneUse()) {
1217  // (X << C1) >>u C --> (X >>u (C - C1)) & (-1 >> C)
1218  Value *NewLShr = Builder.CreateLShr(X, ShiftDiff, "", I.isExact());
1220  return BinaryOperator::CreateAnd(NewLShr, ConstantInt::get(Ty, Mask));
1221  }
1222  } else if (C1->ugt(ShAmtC)) {
1223  unsigned ShlAmtC = C1->getZExtValue();
1224  Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmtC - ShAmtC);
1225  if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
1226  // (X <<nuw C1) >>u C --> X <<nuw (C1 - C)
1227  auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
1228  NewShl->setHasNoUnsignedWrap(true);
1229  return NewShl;
1230  }
1231  if (Op0->hasOneUse()) {
1232  // (X << C1) >>u C --> X << (C1 - C) & (-1 >> C)
1233  Value *NewShl = Builder.CreateShl(X, ShiftDiff);
1235  return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask));
1236  }
1237  } else {
1238  assert(*C1 == ShAmtC);
1239  // (X << C) >>u C --> X & (-1 >>u C)
1241  return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));
1242  }
1243  }
1244 
1245  // ((X << C) + Y) >>u C --> (X + (Y >>u C)) & (-1 >>u C)
1246  // TODO: Consolidate with the more general transform that starts from shl
1247  // (the shifts are in the opposite order).
1248  Value *Y;
1249  if (match(Op0,
1251  m_Value(Y))))) {
1252  Value *NewLshr = Builder.CreateLShr(Y, Op1);
1253  Value *NewAdd = Builder.CreateAdd(NewLshr, X);
1254  unsigned Op1Val = C->getLimitedValue(BitWidth);
1257  return BinaryOperator::CreateAnd(NewAdd, Mask);
1258  }
1259 
1260  if (match(Op0, m_OneUse(m_ZExt(m_Value(X)))) &&
1261  (!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType()))) {
1262  assert(ShAmtC < X->getType()->getScalarSizeInBits() &&
1263  "Big shift not simplified to zero?");
1264  // lshr (zext iM X to iN), C --> zext (lshr X, C) to iN
1265  Value *NewLShr = Builder.CreateLShr(X, ShAmtC);
1266  return new ZExtInst(NewLShr, Ty);
1267  }
1268 
1269  if (match(Op0, m_SExt(m_Value(X)))) {
1270  unsigned SrcTyBitWidth = X->getType()->getScalarSizeInBits();
1271  // lshr (sext i1 X to iN), C --> select (X, -1 >> C, 0)
1272  if (SrcTyBitWidth == 1) {
1273  auto *NewC = ConstantInt::get(
1274  Ty, APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));
1275  return SelectInst::Create(X, NewC, ConstantInt::getNullValue(Ty));
1276  }
1277 
1278  if ((!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType())) &&
1279  Op0->hasOneUse()) {
1280  // Are we moving the sign bit to the low bit and widening with high
1281  // zeros? lshr (sext iM X to iN), N-1 --> zext (lshr X, M-1) to iN
1282  if (ShAmtC == BitWidth - 1) {
1283  Value *NewLShr = Builder.CreateLShr(X, SrcTyBitWidth - 1);
1284  return new ZExtInst(NewLShr, Ty);
1285  }
1286 
1287  // lshr (sext iM X to iN), N-M --> zext (ashr X, min(N-M, M-1)) to iN
1288  if (ShAmtC == BitWidth - SrcTyBitWidth) {
1289  // The new shift amount can't be more than the narrow source type.
1290  unsigned NewShAmt = std::min(ShAmtC, SrcTyBitWidth - 1);
1291  Value *AShr = Builder.CreateAShr(X, NewShAmt);
1292  return new ZExtInst(AShr, Ty);
1293  }
1294  }
1295  }
1296 
1297  if (ShAmtC == BitWidth - 1) {
1298  // lshr i32 or(X,-X), 31 --> zext (X != 0)
1299  if (match(Op0, m_OneUse(m_c_Or(m_Neg(m_Value(X)), m_Deferred(X)))))
1300  return new ZExtInst(Builder.CreateIsNotNull(X), Ty);
1301 
1302  // lshr i32 (X -nsw Y), 31 --> zext (X < Y)
1303  if (match(Op0, m_OneUse(m_NSWSub(m_Value(X), m_Value(Y)))))
1304  return new ZExtInst(Builder.CreateICmpSLT(X, Y), Ty);
1305 
1306  // Check if a number is negative and odd:
1307  // lshr i32 (srem X, 2), 31 --> and (X >> 31), X
1308  if (match(Op0, m_OneUse(m_SRem(m_Value(X), m_SpecificInt(2))))) {
1309  Value *Signbit = Builder.CreateLShr(X, ShAmtC);
1310  return BinaryOperator::CreateAnd(Signbit, X);
1311  }
1312  }
1313 
1314  // (X >>u C1) >>u C --> X >>u (C1 + C)
1315  if (match(Op0, m_LShr(m_Value(X), m_APInt(C1)))) {
1316  // Oversized shifts are simplified to zero in InstSimplify.
1317  unsigned AmtSum = ShAmtC + C1->getZExtValue();
1318  if (AmtSum < BitWidth)
1319  return BinaryOperator::CreateLShr(X, ConstantInt::get(Ty, AmtSum));
1320  }
1321 
1322  Instruction *TruncSrc;
1323  if (match(Op0, m_OneUse(m_Trunc(m_Instruction(TruncSrc)))) &&
1324  match(TruncSrc, m_LShr(m_Value(X), m_APInt(C1)))) {
1325  unsigned SrcWidth = X->getType()->getScalarSizeInBits();
1326  unsigned AmtSum = ShAmtC + C1->getZExtValue();
1327 
1328  // If the combined shift fits in the source width:
1329  // (trunc (X >>u C1)) >>u C --> and (trunc (X >>u (C1 + C)), MaskC
1330  //
1331  // If the first shift covers the number of bits truncated, then the
1332  // mask instruction is eliminated (and so the use check is relaxed).
1333  if (AmtSum < SrcWidth &&
1334  (TruncSrc->hasOneUse() || C1->uge(SrcWidth - BitWidth))) {
1335  Value *SumShift = Builder.CreateLShr(X, AmtSum, "sum.shift");
1336  Value *Trunc = Builder.CreateTrunc(SumShift, Ty, I.getName());
1337 
1338  // If the first shift does not cover the number of bits truncated, then
1339  // we require a mask to get rid of high bits in the result.
1340  APInt MaskC = APInt::getAllOnes(BitWidth).lshr(ShAmtC);
1341  return BinaryOperator::CreateAnd(Trunc, ConstantInt::get(Ty, MaskC));
1342  }
1343  }
1344 
1345  const APInt *MulC;
1346  if (match(Op0, m_NUWMul(m_Value(X), m_APInt(MulC)))) {
1347  // Look for a "splat" mul pattern - it replicates bits across each half of
1348  // a value, so a right shift is just a mask of the low bits:
1349  // lshr i[2N] (mul nuw X, (2^N)+1), N --> and iN X, (2^N)-1
1350  // TODO: Generalize to allow more than just half-width shifts?
1351  if (BitWidth > 2 && ShAmtC * 2 == BitWidth && (*MulC - 1).isPowerOf2() &&
1352  MulC->logBase2() == ShAmtC)
1353  return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, *MulC - 2));
1354 
1355  // The one-use check is not strictly necessary, but codegen may not be
1356  // able to invert the transform and perf may suffer with an extra mul
1357  // instruction.
1358  if (Op0->hasOneUse()) {
1359  APInt NewMulC = MulC->lshr(ShAmtC);
1360  // if c is divisible by (1 << ShAmtC):
1361  // lshr (mul nuw x, MulC), ShAmtC -> mul nuw x, (MulC >> ShAmtC)
1362  if (MulC->eq(NewMulC.shl(ShAmtC))) {
1363  auto *NewMul =
1364  BinaryOperator::CreateNUWMul(X, ConstantInt::get(Ty, NewMulC));
1365  BinaryOperator *OrigMul = cast<BinaryOperator>(Op0);
1366  NewMul->setHasNoSignedWrap(OrigMul->hasNoSignedWrap());
1367  return NewMul;
1368  }
1369  }
1370  }
1371 
1372  // Try to narrow bswap.
1373  // In the case where the shift amount equals the bitwidth difference, the
1374  // shift is eliminated.
1375  if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::bswap>(
1376  m_OneUse(m_ZExt(m_Value(X))))))) {
1377  unsigned SrcWidth = X->getType()->getScalarSizeInBits();
1378  unsigned WidthDiff = BitWidth - SrcWidth;
1379  if (SrcWidth % 16 == 0) {
1380  Value *NarrowSwap = Builder.CreateUnaryIntrinsic(Intrinsic::bswap, X);
1381  if (ShAmtC >= WidthDiff) {
1382  // (bswap (zext X)) >> C --> zext (bswap X >> C')
1383  Value *NewShift = Builder.CreateLShr(NarrowSwap, ShAmtC - WidthDiff);
1384  return new ZExtInst(NewShift, Ty);
1385  } else {
1386  // (bswap (zext X)) >> C --> (zext (bswap X)) << C'
1387  Value *NewZExt = Builder.CreateZExt(NarrowSwap, Ty);
1388  Constant *ShiftDiff = ConstantInt::get(Ty, WidthDiff - ShAmtC);
1389  return BinaryOperator::CreateShl(NewZExt, ShiftDiff);
1390  }
1391  }
1392  }
1393 
1394  // Reduce add-carry of bools to logic:
1395  // ((zext BoolX) + (zext BoolY)) >> 1 --> zext (BoolX && BoolY)
1396  Value *BoolX, *BoolY;
1397  if (ShAmtC == 1 && match(Op0, m_Add(m_Value(X), m_Value(Y))) &&
1398  match(X, m_ZExt(m_Value(BoolX))) && match(Y, m_ZExt(m_Value(BoolY))) &&
1399  BoolX->getType()->isIntOrIntVectorTy(1) &&
1400  BoolY->getType()->isIntOrIntVectorTy(1) &&
1401  (X->hasOneUse() || Y->hasOneUse() || Op0->hasOneUse())) {
1402  Value *And = Builder.CreateAnd(BoolX, BoolY);
1403  return new ZExtInst(And, Ty);
1404  }
1405 
1406  // If the shifted-out value is known-zero, then this is an exact shift.
1407  if (!I.isExact() &&
1408  MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmtC), 0, &I)) {
1409  I.setIsExact();
1410  return &I;
1411  }
1412  }
1413 
1414  // Transform (x << y) >> y to x & (-1 >> y)
1415  if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_Specific(Op1))))) {
1416  Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
1417  Value *Mask = Builder.CreateLShr(AllOnes, Op1);
1418  return BinaryOperator::CreateAnd(Mask, X);
1419  }
1420 
1421  if (Instruction *Overflow = foldLShrOverflowBit(I))
1422  return Overflow;
1423 
1424  return nullptr;
1425 }
1426 
1427 Instruction *
1429  BinaryOperator &OldAShr) {
1430  assert(OldAShr.getOpcode() == Instruction::AShr &&
1431  "Must be called with arithmetic right-shift instruction only.");
1432 
1433  // Check that constant C is a splat of the element-wise bitwidth of V.
1434  auto BitWidthSplat = [](Constant *C, Value *V) {
1435  return match(
1436  C, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ,
1437  APInt(C->getType()->getScalarSizeInBits(),
1438  V->getType()->getScalarSizeInBits())));
1439  };
1440 
1441  // It should look like variable-length sign-extension on the outside:
1442  // (Val << (bitwidth(Val)-Nbits)) a>> (bitwidth(Val)-Nbits)
1443  Value *NBits;
1444  Instruction *MaybeTrunc;
1445  Constant *C1, *C2;
1446  if (!match(&OldAShr,
1447  m_AShr(m_Shl(m_Instruction(MaybeTrunc),
1449  m_ZExtOrSelf(m_Value(NBits))))),
1451  m_ZExtOrSelf(m_Deferred(NBits)))))) ||
1452  !BitWidthSplat(C1, &OldAShr) || !BitWidthSplat(C2, &OldAShr))
1453  return nullptr;
1454 
1455  // There may or may not be a truncation after outer two shifts.
1456  Instruction *HighBitExtract;
1457  match(MaybeTrunc, m_TruncOrSelf(m_Instruction(HighBitExtract)));
1458  bool HadTrunc = MaybeTrunc != HighBitExtract;
1459 
1460  // And finally, the innermost part of the pattern must be a right-shift.
1461  Value *X, *NumLowBitsToSkip;
1462  if (!match(HighBitExtract, m_Shr(m_Value(X), m_Value(NumLowBitsToSkip))))
1463  return nullptr;
1464 
1465  // Said right-shift must extract high NBits bits - C0 must be it's bitwidth.
1466  Constant *C0;
1467  if (!match(NumLowBitsToSkip,
1468  m_ZExtOrSelf(
1469  m_Sub(m_Constant(C0), m_ZExtOrSelf(m_Specific(NBits))))) ||
1470  !BitWidthSplat(C0, HighBitExtract))
1471  return nullptr;
1472 
1473  // Since the NBits is identical for all shifts, if the outermost and
1474  // innermost shifts are identical, then outermost shifts are redundant.
1475  // If we had truncation, do keep it though.
1476  if (HighBitExtract->getOpcode() == OldAShr.getOpcode())
1477  return replaceInstUsesWith(OldAShr, MaybeTrunc);
1478 
1479  // Else, if there was a truncation, then we need to ensure that one
1480  // instruction will go away.
1481  if (HadTrunc && !match(&OldAShr, m_c_BinOp(m_OneUse(m_Value()), m_Value())))
1482  return nullptr;
1483 
1484  // Finally, bypass two innermost shifts, and perform the outermost shift on
1485  // the operands of the innermost shift.
1486  Instruction *NewAShr =
1487  BinaryOperator::Create(OldAShr.getOpcode(), X, NumLowBitsToSkip);
1488  NewAShr->copyIRFlags(HighBitExtract); // We can preserve 'exact'-ness.
1489  if (!HadTrunc)
1490  return NewAShr;
1491 
1492  Builder.Insert(NewAShr);
1493  return TruncInst::CreateTruncOrBitCast(NewAShr, OldAShr.getType());
1494 }
1495 
1497  if (Value *V = simplifyAShrInst(I.getOperand(0), I.getOperand(1), I.isExact(),
1498  SQ.getWithInstruction(&I)))
1499  return replaceInstUsesWith(I, V);
1500 
1501  if (Instruction *X = foldVectorBinop(I))
1502  return X;
1503 
1504  if (Instruction *R = commonShiftTransforms(I))
1505  return R;
1506 
1507  Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1508  Type *Ty = I.getType();
1509  unsigned BitWidth = Ty->getScalarSizeInBits();
1510  const APInt *ShAmtAPInt;
1511  if (match(Op1, m_APInt(ShAmtAPInt)) && ShAmtAPInt->ult(BitWidth)) {
1512  unsigned ShAmt = ShAmtAPInt->getZExtValue();
1513 
1514  // If the shift amount equals the difference in width of the destination
1515  // and source scalar types:
1516  // ashr (shl (zext X), C), C --> sext X
1517  Value *X;
1518  if (match(Op0, m_Shl(m_ZExt(m_Value(X)), m_Specific(Op1))) &&
1519  ShAmt == BitWidth - X->getType()->getScalarSizeInBits())
1520  return new SExtInst(X, Ty);
1521 
1522  // We can't handle (X << C1) >>s C2. It shifts arbitrary bits in. However,
1523  // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits.
1524  const APInt *ShOp1;
1525  if (match(Op0, m_NSWShl(m_Value(X), m_APInt(ShOp1))) &&
1526  ShOp1->ult(BitWidth)) {
1527  unsigned ShlAmt = ShOp1->getZExtValue();
1528  if (ShlAmt < ShAmt) {
1529  // (X <<nsw C1) >>s C2 --> X >>s (C2 - C1)
1530  Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt);
1531  auto *NewAShr = BinaryOperator::CreateAShr(X, ShiftDiff);
1532  NewAShr->setIsExact(I.isExact());
1533  return NewAShr;
1534  }
1535  if (ShlAmt > ShAmt) {
1536  // (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2)
1537  Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt);
1538  auto *NewShl = BinaryOperator::Create(Instruction::Shl, X, ShiftDiff);
1539  NewShl->setHasNoSignedWrap(true);
1540  return NewShl;
1541  }
1542  }
1543 
1544  if (match(Op0, m_AShr(m_Value(X), m_APInt(ShOp1))) &&
1545  ShOp1->ult(BitWidth)) {
1546  unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
1547  // Oversized arithmetic shifts replicate the sign bit.
1548  AmtSum = std::min(AmtSum, BitWidth - 1);
1549  // (X >>s C1) >>s C2 --> X >>s (C1 + C2)
1550  return BinaryOperator::CreateAShr(X, ConstantInt::get(Ty, AmtSum));
1551  }
1552 
1553  if (match(Op0, m_OneUse(m_SExt(m_Value(X)))) &&
1554  (Ty->isVectorTy() || shouldChangeType(Ty, X->getType()))) {
1555  // ashr (sext X), C --> sext (ashr X, C')
1556  Type *SrcTy = X->getType();
1557  ShAmt = std::min(ShAmt, SrcTy->getScalarSizeInBits() - 1);
1558  Value *NewSh = Builder.CreateAShr(X, ConstantInt::get(SrcTy, ShAmt));
1559  return new SExtInst(NewSh, Ty);
1560  }
1561 
1562  if (ShAmt == BitWidth - 1) {
1563  // ashr i32 or(X,-X), 31 --> sext (X != 0)
1564  if (match(Op0, m_OneUse(m_c_Or(m_Neg(m_Value(X)), m_Deferred(X)))))
1565  return new SExtInst(Builder.CreateIsNotNull(X), Ty);
1566 
1567  // ashr i32 (X -nsw Y), 31 --> sext (X < Y)
1568  Value *Y;
1569  if (match(Op0, m_OneUse(m_NSWSub(m_Value(X), m_Value(Y)))))
1570  return new SExtInst(Builder.CreateICmpSLT(X, Y), Ty);
1571  }
1572 
1573  // If the shifted-out value is known-zero, then this is an exact shift.
1574  if (!I.isExact() &&
1575  MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), 0, &I)) {
1576  I.setIsExact();
1577  return &I;
1578  }
1579  }
1580 
1581  // Prefer `-(x & 1)` over `(x << (bitwidth(x)-1)) a>> (bitwidth(x)-1)`
1582  // as the pattern to splat the lowest bit.
1583  // FIXME: iff X is already masked, we don't need the one-use check.
1584  Value *X;
1585  if (match(Op1, m_SpecificIntAllowUndef(BitWidth - 1)) &&
1586  match(Op0, m_OneUse(m_Shl(m_Value(X),
1588  Constant *Mask = ConstantInt::get(Ty, 1);
1589  // Retain the knowledge about the ignored lanes.
1591  Constant::mergeUndefsWith(Mask, cast<Constant>(Op1)),
1592  cast<Constant>(cast<Instruction>(Op0)->getOperand(1)));
1593  X = Builder.CreateAnd(X, Mask);
1594  return BinaryOperator::CreateNeg(X);
1595  }
1596 
1597  if (Instruction *R = foldVariableSignZeroExtensionOfVariableHighBitExtract(I))
1598  return R;
1599 
1600  // See if we can turn a signed shr into an unsigned shr.
1601  if (MaskedValueIsZero(Op0, APInt::getSignMask(BitWidth), 0, &I)) {
1602  Instruction *Lshr = BinaryOperator::CreateLShr(Op0, Op1);
1603  Lshr->setIsExact(I.isExact());
1604  return Lshr;
1605  }
1606 
1607  // ashr (xor %x, -1), %y --> xor (ashr %x, %y), -1
1608  if (match(Op0, m_OneUse(m_Not(m_Value(X))))) {
1609  // Note that we must drop 'exact'-ness of the shift!
1610  // Note that we can't keep undef's in -1 vector constant!
1611  auto *NewAShr = Builder.CreateAShr(X, Op1, Op0->getName() + ".not");
1612  return BinaryOperator::CreateNot(NewAShr);
1613  }
1614 
1615  return nullptr;
1616 }
i
i
Definition: README.txt:29
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::simplifyAShrInst
Value * simplifyAShrInst(Value *Op0, Value *Op1, bool IsExact, const SimplifyQuery &Q)
Given operands for a AShr, fold the result or return nulll.
Definition: InstructionSimplify.cpp:1538
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::PatternMatch::m_TruncOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1617
llvm::ConstantExpr::getNot
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2651
llvm::MaskedValueIsZero
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 'V & Mask' is known to be zero.
Definition: ValueTracking.cpp:364
llvm::PHINode::incoming_values
op_range incoming_values()
Definition: Instructions.h:2784
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:114
llvm::ConstantExpr::getZExtOrBitCast
static Constant * getZExtOrBitCast(Constant *C, Type *Ty)
Definition: Constants.cpp:2012
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
InstCombiner.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
PHI
Rewrite undef for PHI
Definition: AMDGPURewriteUndefForPHI.cpp:101
IntrinsicInst.h
llvm::SimplifyQuery
Definition: InstructionSimplify.h:93
canTryToConstantAddTwoShiftAmounts
bool canTryToConstantAddTwoShiftAmounts(Value *Sh0, Value *ShAmt0, Value *Sh1, Value *ShAmt1)
Definition: InstCombineShifts.cpp:23
llvm::ConstantExpr::getZExt
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2119
llvm::InstCombinerImpl::FoldShiftByConstant
Instruction * FoldShiftByConstant(Value *Op0, Constant *Op1, BinaryOperator &I)
Definition: InstCombineShifts.cpp:740
llvm::BinaryOperator::CreateNot
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
Definition: Instructions.cpp:3006
llvm::PatternMatch::m_LShr
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1117
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
canShiftBinOpWithConstantRHS
static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift, BinaryOperator *BO)
Definition: InstCombineShifts.cpp:723
llvm::InstCombiner::Builder
BuilderTy & Builder
Definition: InstCombiner.h:58
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
llvm::PatternMatch::m_CombineOr
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:218
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::CastInst::Create
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's ...
Definition: Instructions.cpp:3354
Shift
bool Shift
Definition: README.txt:468
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
llvm::InstCombinerImpl::reassociateShiftAmtsOfTwoSameDirectionShifts
Value * reassociateShiftAmtsOfTwoSameDirectionShifts(BinaryOperator *Sh0, const SimplifyQuery &SQ, bool AnalyzeForSignBitExtraction=false)
Definition: InstCombineShifts.cpp:58
canEvaluateShiftedShift
static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl, Instruction *InnerShift, InstCombinerImpl &IC, Instruction *CxtI)
Return true if we can simplify two logical (either left or right) shifts that have constant shift amo...
Definition: InstCombineShifts.cpp:491
llvm::APInt::ugt
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1160
llvm::Instruction::setHasNoUnsignedWrap
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:161
llvm::Constant::containsUndefElement
bool containsUndefElement() const
Return true if this is a vector constant that includes any strictly undef (not poison) elements.
Definition: Constants.cpp:340
llvm::PatternMatch::m_BinOp
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
llvm::PatternMatch::m_AShr
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1123
llvm::ComputeNumSignBits
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.
Definition: ValueTracking.cpp:383
llvm::InstCombiner::addToWorklist
void addToWorklist(Instruction *I)
Definition: InstCombiner.h:367
llvm::tgtok::FalseVal
@ FalseVal
Definition: TGLexer.h:62
llvm::ARM_AM::ShiftOpc
ShiftOpc
Definition: ARMAddressingModes.h:27
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:748
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
llvm::APInt::lshr
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:839
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::isPowerOf2_32
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:288
llvm::PatternMatch::m_c_And
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.
Definition: PatternMatch.h:2262
llvm::BinaryOperator::CreateNeg
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...
Definition: Instructions.cpp:2966
llvm::Instruction::setIsExact
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:169
llvm::PHINode::setIncomingValue
void setIncomingValue(unsigned i, Value *V)
Definition: Instructions.h:2797
llvm::PatternMatch::m_Deferred
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
Definition: PatternMatch.h:790
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::PatternMatch::m_OneUse
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ConstantExpr::getSub
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2664
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:278
llvm::PatternMatch::m_c_BinOp
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
Definition: PatternMatch.h:2226
llvm::APInt::uge
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1199
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:168
llvm::APInt::isNegative
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:312
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1777
llvm::InstCombinerImpl::foldVariableSignZeroExtensionOfVariableHighBitExtract
Instruction * foldVariableSignZeroExtensionOfVariableHighBitExtract(BinaryOperator &OldAShr)
Definition: InstCombineShifts.cpp:1428
llvm::RecurKind::And
@ And
Bitwise or logical AND of integers.
hasNoUnsignedWrap
static bool hasNoUnsignedWrap(BinaryOperator &I)
Definition: InstructionCombining.cpp:301
llvm::APInt::eq
bool eq(const APInt &RHS) const
Equality comparison.
Definition: APInt.h:1057
InstCombineInternal.h
llvm::PatternMatch::m_Select
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
Definition: PatternMatch.h:1462
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2794
getScalarSizeInBits
static unsigned getScalarSizeInBits(Type *Ty)
Definition: SystemZTargetTransformInfo.cpp:403
llvm::APInt::isZero
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:366
llvm::Instruction::setHasNoSignedWrap
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
Definition: Instruction.cpp:165
llvm::User
Definition: User.h:44
llvm::PatternMatch::m_Exact
Exact_match< T > m_Exact(const T &SubPattern)
Definition: PatternMatch.h:1351
foldShiftOfShiftedBinOp
static Instruction * foldShiftOfShiftedBinOp(BinaryOperator &I, InstCombiner::BuilderTy &Builder)
If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/ shl) that itself has a shi...
Definition: InstCombineShifts.cpp:330
llvm::PatternMatch::m_SpecificIntAllowUndef
specific_intval< true > m_SpecificIntAllowUndef(APInt V)
Definition: PatternMatch.h:862
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
SI
@ SI
Definition: SIInstrInfo.cpp:7993
llvm::APInt::getAllOnes
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:258
llvm::PatternMatch::m_Instruction
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:716
llvm::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1629
llvm::Log2_32
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:373
llvm::PatternMatch::m_c_Add
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
Definition: PatternMatch.h:2248
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Constant::getAllOnesValue
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:403
llvm::PatternMatch::m_SDiv
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1063
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:391
llvm::Instruction
Definition: Instruction.h:41
llvm::Type::getScalarSizeInBits
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
Definition: Type.cpp:188
llvm::PatternMatch::m_c_Or
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
Definition: PatternMatch.h:2269
llvm::APInt::getZExtValue
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1494
llvm::APInt::getHighBitsSet
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
Definition: APInt.h:279
llvm::InstCombinerImpl
Definition: InstCombineInternal.h:61
llvm::ConstantInt::get
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:887
llvm::PatternMatch::m_NSWSub
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1164
PatternMatch.h
llvm::APInt::countTrailingZeros
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1591
llvm::CastInst::CreateTruncOrBitCast
static CastInst * CreateTruncOrBitCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a Trunc or BitCast cast instruction.
Definition: Instructions.cpp:3430
llvm::PatternMatch::m_Shift
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
Definition: PatternMatch.h:1296
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2790
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::PatternMatch::m_One
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:517
llvm::Instruction::isCommutative
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
Definition: Instruction.cpp:816
llvm::APInt::ashr
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:815
llvm::PatternMatch::m_Power2
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:544
llvm::PatternMatch::m_Xor
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1105
llvm::Type::getExtendedType
Type * getExtendedType() const
Given scalar/vector integer type, returns a type with elements twice as wide as in the original type.
Definition: DerivedTypes.h:706
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:222
llvm::PatternMatch::m_Shr
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
Definition: PatternMatch.h:1303
llvm::PatternMatch::m_ZExtOrSelf
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, OpTy > m_ZExtOrSelf(const OpTy &Op)
Definition: PatternMatch.h:1635
llvm::ConstantExpr::getTrunc
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2091
llvm::PatternMatch::m_NUWAdd
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1189
llvm::InstCombinerImpl::visitShl
Instruction * visitShl(BinaryOperator &I)
Definition: InstCombineShifts.cpp:927
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::Instruction::hasNoSignedWrap
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
Definition: Instruction.cpp:177
llvm::Instruction::isLogicalShift
bool isLogicalShift() const
Return true if this is a logical shift left or a logical shift right.
Definition: Instruction.h:209
llvm::Constant::replaceUndefsWith
static Constant * replaceUndefsWith(Constant *C, Constant *Replacement)
Try to replace undefined constant C or undefined elements in C with Replacement.
Definition: Constants.cpp:755
llvm::Instruction::hasNoUnsignedWrap
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
Definition: Instruction.cpp:173
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4813
llvm::APInt::logBase2
unsigned logBase2() const
Definition: APInt.h:1700
llvm::PatternMatch::m_AllOnes
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:453
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:31
I
#define I(x, y, z)
Definition: MD5.cpp:58
getShiftedValue
static Value * getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift, InstCombinerImpl &IC, const DataLayout &DL)
When canEvaluateShifted() returns true for an expression, this function inserts the new computation t...
Definition: InstCombineShifts.cpp:661
llvm::ConstantExpr::getShl
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2695
llvm::PatternMatch::m_And
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1093
llvm::PatternMatch::m_SRem
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1081
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PatternMatch::m_Sub
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:991
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1746
llvm::SimplifyQuery::getWithInstruction
SimplifyQuery getWithInstruction(Instruction *I) const
Definition: InstructionSimplify.h:120
llvm::simplifyAddInst
Value * simplifyAddInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
Definition: InstructionSimplify.cpp:698
llvm::PatternMatch::m_Constant
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:144
getOpcode
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:191
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4852
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::User::setOperand
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
getType
static M68kRelType getType(unsigned Kind, MCSymbolRefExpr::VariantKind &Modifier, bool &IsPCRel)
Definition: M68kELFObjectWriter.cpp:48
llvm::PatternMatch::m_SExt
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:1623
llvm::InstCombinerImpl::visitLShr
Instruction * visitLShr(BinaryOperator &I)
Definition: InstCombineShifts.cpp:1166
llvm::PatternMatch::m_SpecificInt
specific_intval< false > m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:854
llvm::PatternMatch::m_CombineAnd
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:224
llvm::PatternMatch::m_NUWMul
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1205
llvm::BinaryOperator
Definition: InstrTypes.h:187
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
llvm::PatternMatch::m_SpecificInt_ICMP
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 'pred' (eg/ne/...) to Threshold.
Definition: PatternMatch.h:598
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:743
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
llvm::InstCombiner::MaskedValueIsZero
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:477
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::simplifyLShrInst
Value * simplifyLShrInst(Value *Op0, Value *Op1, bool IsExact, const SimplifyQuery &Q)
Given operands for a LShr, fold the result or return null.
Definition: InstructionSimplify.cpp:1505
CC
auto CC
Definition: RISCVRedundantCopyElimination.cpp:79
foldShiftedShift
static Value * foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt, bool IsOuterShl, InstCombiner::BuilderTy &Builder)
Fold OuterShift (InnerShift X, C1), C2.
Definition: InstCombineShifts.cpp:598
llvm::InstCombiner::InsertNewInstWith
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
Definition: InstCombiner.h:407
llvm::APInt::ult
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1089
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4891
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
llvm::InstCombinerImpl::visitAShr
Instruction * visitAShr(BinaryOperator &I)
Definition: InstCombineShifts.cpp:1496
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:165
llvm::simplifyShlInst
Value * simplifyShlInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for a Shl, fold the result or return null.
Definition: InstructionSimplify.cpp:1468
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:356
llvm::APInt::isMinSignedValue
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:415
llvm::InstCombinerImpl::commonShiftTransforms
Instruction * commonShiftTransforms(BinaryOperator &I)
Definition: InstCombineShifts.cpp:387
llvm::ConstantExpr::getAdd
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2657
llvm::Type::isIntOrIntVectorTy
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:228
llvm::APInt::isNegatedPowerOf2
bool isNegatedPowerOf2() const
Check if this APInt's negated value is a power of two greater than zero.
Definition: APInt.h:441
llvm::ConstantInt::getSigned
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.cpp:901
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::PatternMatch::m_NSWShl
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1180
dropRedundantMaskingOfLeftShiftInput
static Instruction * dropRedundantMaskingOfLeftShiftInput(BinaryOperator *OuterShift, const SimplifyQuery &Q, InstCombiner::BuilderTy &Builder)
Definition: InstCombineShifts.cpp:184
llvm::ConstantExpr::getLShr
static Constant * getLShr(Constant *C1, Constant *C2, bool isExact=false)
Definition: Constants.cpp:2702
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:746
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:186
llvm::Constant::mergeUndefsWith
static Constant * mergeUndefsWith(Constant *C, Constant *Other)
Merges undefs of a Constant with another Constant, along with the undefs already present.
Definition: Constants.cpp:779
llvm::PatternMatch::m_Not
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
Definition: PatternMatch.h:2302
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:809
llvm::APInt::getSignMask
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:209
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:772
llvm::IRBuilderBase::CreateLShr
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1352
CreateMul
static BinaryOperator * CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp)
Definition: Reassociate.cpp:253
llvm::IRBuilderBase::CreateShl
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Definition: IRBuilder.h:1331
canEvaluateShifted
static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift, InstCombinerImpl &IC, Instruction *CxtI)
See if we can compute the specified value, but shifted logically to the left or right by some number ...
Definition: InstCombineShifts.cpp:543
InstructionSimplify.h
llvm::PHINode
Definition: Instructions.h:2708
llvm::Instruction::copyIRFlags
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
Definition: Instruction.cpp:348
llvm::PatternMatch::m_Neg
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
Definition: PatternMatch.h:2284
llvm::APInt::getLowBitsSet
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:289
llvm::Value::takeName
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:381
llvm::APInt::shl
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:861
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
llvm::PatternMatch::m_Trunc
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:1611
llvm::BinaryOperator::Create
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.
Definition: Instructions.cpp:2950
llvm::tgtok::TrueVal
@ TrueVal
Definition: TGLexer.h:62
llvm::Instruction::isExact
bool isExact() const LLVM_READONLY
Determine whether the exact flag is set.
Definition: Instruction.cpp:245
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::PatternMatch::m_Shl
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1111
llvm::PatternMatch::m_Mul
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1045
llvm::simplifySubInst
Value * simplifySubInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for a Sub, fold the result or return null.
Definition: InstructionSimplify.cpp:918