xref: /freebsd-src/contrib/llvm-project/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
10b57cec5SDimitry Andric //===- InstCombineShifts.cpp ----------------------------------------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // This file implements the visitShl, visitLShr, and visitAShr functions.
100b57cec5SDimitry Andric //
110b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
120b57cec5SDimitry Andric 
130b57cec5SDimitry Andric #include "InstCombineInternal.h"
140b57cec5SDimitry Andric #include "llvm/Analysis/InstructionSimplify.h"
150b57cec5SDimitry Andric #include "llvm/IR/IntrinsicInst.h"
160b57cec5SDimitry Andric #include "llvm/IR/PatternMatch.h"
17e8d8bef9SDimitry Andric #include "llvm/Transforms/InstCombine/InstCombiner.h"
180b57cec5SDimitry Andric using namespace llvm;
190b57cec5SDimitry Andric using namespace PatternMatch;
200b57cec5SDimitry Andric 
210b57cec5SDimitry Andric #define DEBUG_TYPE "instcombine"
220b57cec5SDimitry Andric 
2323408297SDimitry Andric bool canTryToConstantAddTwoShiftAmounts(Value *Sh0, Value *ShAmt0, Value *Sh1,
2423408297SDimitry Andric                                         Value *ShAmt1) {
2523408297SDimitry Andric   // We have two shift amounts from two different shifts. The types of those
2623408297SDimitry Andric   // shift amounts may not match. If that's the case let's bailout now..
2723408297SDimitry Andric   if (ShAmt0->getType() != ShAmt1->getType())
2823408297SDimitry Andric     return false;
2923408297SDimitry Andric 
3023408297SDimitry Andric   // As input, we have the following pattern:
3123408297SDimitry Andric   //   Sh0 (Sh1 X, Q), K
3223408297SDimitry Andric   // We want to rewrite that as:
3323408297SDimitry Andric   //   Sh x, (Q+K)  iff (Q+K) u< bitwidth(x)
3423408297SDimitry Andric   // While we know that originally (Q+K) would not overflow
3523408297SDimitry Andric   // (because  2 * (N-1) u<= iN -1), we have looked past extensions of
3623408297SDimitry Andric   // shift amounts. so it may now overflow in smaller bitwidth.
3723408297SDimitry Andric   // To ensure that does not happen, we need to ensure that the total maximal
3823408297SDimitry Andric   // shift amount is still representable in that smaller bit width.
3923408297SDimitry Andric   unsigned MaximalPossibleTotalShiftAmount =
4023408297SDimitry Andric       (Sh0->getType()->getScalarSizeInBits() - 1) +
4123408297SDimitry Andric       (Sh1->getType()->getScalarSizeInBits() - 1);
4223408297SDimitry Andric   APInt MaximalRepresentableShiftAmount =
43349cc55cSDimitry Andric       APInt::getAllOnes(ShAmt0->getType()->getScalarSizeInBits());
4423408297SDimitry Andric   return MaximalRepresentableShiftAmount.uge(MaximalPossibleTotalShiftAmount);
4523408297SDimitry Andric }
4623408297SDimitry Andric 
470b57cec5SDimitry Andric // Given pattern:
480b57cec5SDimitry Andric //   (x shiftopcode Q) shiftopcode K
490b57cec5SDimitry Andric // we should rewrite it as
5047395794SDimitry Andric //   x shiftopcode (Q+K)  iff (Q+K) u< bitwidth(x) and
5147395794SDimitry Andric //
5247395794SDimitry Andric // This is valid for any shift, but they must be identical, and we must be
5347395794SDimitry Andric // careful in case we have (zext(Q)+zext(K)) and look past extensions,
5447395794SDimitry Andric // (Q+K) must not overflow or else (Q+K) u< bitwidth(x) is bogus.
558bcb0991SDimitry Andric //
568bcb0991SDimitry Andric // AnalyzeForSignBitExtraction indicates that we will only analyze whether this
578bcb0991SDimitry Andric // pattern has any 2 right-shifts that sum to 1 less than original bit width.
58e8d8bef9SDimitry Andric Value *InstCombinerImpl::reassociateShiftAmtsOfTwoSameDirectionShifts(
598bcb0991SDimitry Andric     BinaryOperator *Sh0, const SimplifyQuery &SQ,
608bcb0991SDimitry Andric     bool AnalyzeForSignBitExtraction) {
618bcb0991SDimitry Andric   // Look for a shift of some instruction, ignore zext of shift amount if any.
628bcb0991SDimitry Andric   Instruction *Sh0Op0;
638bcb0991SDimitry Andric   Value *ShAmt0;
648bcb0991SDimitry Andric   if (!match(Sh0,
658bcb0991SDimitry Andric              m_Shift(m_Instruction(Sh0Op0), m_ZExtOrSelf(m_Value(ShAmt0)))))
660b57cec5SDimitry Andric     return nullptr;
670b57cec5SDimitry Andric 
688bcb0991SDimitry Andric   // If there is a truncation between the two shifts, we must make note of it
698bcb0991SDimitry Andric   // and look through it. The truncation imposes additional constraints on the
708bcb0991SDimitry Andric   // transform.
718bcb0991SDimitry Andric   Instruction *Sh1;
728bcb0991SDimitry Andric   Value *Trunc = nullptr;
738bcb0991SDimitry Andric   match(Sh0Op0,
748bcb0991SDimitry Andric         m_CombineOr(m_CombineAnd(m_Trunc(m_Instruction(Sh1)), m_Value(Trunc)),
758bcb0991SDimitry Andric                     m_Instruction(Sh1)));
768bcb0991SDimitry Andric 
778bcb0991SDimitry Andric   // Inner shift: (x shiftopcode ShAmt1)
788bcb0991SDimitry Andric   // Like with other shift, ignore zext of shift amount if any.
798bcb0991SDimitry Andric   Value *X, *ShAmt1;
808bcb0991SDimitry Andric   if (!match(Sh1, m_Shift(m_Value(X), m_ZExtOrSelf(m_Value(ShAmt1)))))
810b57cec5SDimitry Andric     return nullptr;
828bcb0991SDimitry Andric 
8323408297SDimitry Andric   // Verify that it would be safe to try to add those two shift amounts.
8423408297SDimitry Andric   if (!canTryToConstantAddTwoShiftAmounts(Sh0, ShAmt0, Sh1, ShAmt1))
8547395794SDimitry Andric     return nullptr;
8647395794SDimitry Andric 
878bcb0991SDimitry Andric   // We are only looking for signbit extraction if we have two right shifts.
888bcb0991SDimitry Andric   bool HadTwoRightShifts = match(Sh0, m_Shr(m_Value(), m_Value())) &&
898bcb0991SDimitry Andric                            match(Sh1, m_Shr(m_Value(), m_Value()));
908bcb0991SDimitry Andric   // ... and if it's not two right-shifts, we know the answer already.
918bcb0991SDimitry Andric   if (AnalyzeForSignBitExtraction && !HadTwoRightShifts)
928bcb0991SDimitry Andric     return nullptr;
938bcb0991SDimitry Andric 
948bcb0991SDimitry Andric   // The shift opcodes must be identical, unless we are just checking whether
958bcb0991SDimitry Andric   // this pattern can be interpreted as a sign-bit-extraction.
968bcb0991SDimitry Andric   Instruction::BinaryOps ShiftOpcode = Sh0->getOpcode();
978bcb0991SDimitry Andric   bool IdenticalShOpcodes = Sh0->getOpcode() == Sh1->getOpcode();
988bcb0991SDimitry Andric   if (!IdenticalShOpcodes && !AnalyzeForSignBitExtraction)
998bcb0991SDimitry Andric     return nullptr;
1008bcb0991SDimitry Andric 
1018bcb0991SDimitry Andric   // If we saw truncation, we'll need to produce extra instruction,
1028bcb0991SDimitry Andric   // and for that one of the operands of the shift must be one-use,
1038bcb0991SDimitry Andric   // unless of course we don't actually plan to produce any instructions here.
1048bcb0991SDimitry Andric   if (Trunc && !AnalyzeForSignBitExtraction &&
1058bcb0991SDimitry Andric       !match(Sh0, m_c_BinOp(m_OneUse(m_Value()), m_Value())))
1068bcb0991SDimitry Andric     return nullptr;
1078bcb0991SDimitry Andric 
1080b57cec5SDimitry Andric   // Can we fold (ShAmt0+ShAmt1) ?
1098bcb0991SDimitry Andric   auto *NewShAmt = dyn_cast_or_null<Constant>(
11081ad6265SDimitry Andric       simplifyAddInst(ShAmt0, ShAmt1, /*isNSW=*/false, /*isNUW=*/false,
1118bcb0991SDimitry Andric                       SQ.getWithInstruction(Sh0)));
1120b57cec5SDimitry Andric   if (!NewShAmt)
1130b57cec5SDimitry Andric     return nullptr; // Did not simplify.
1148bcb0991SDimitry Andric   unsigned NewShAmtBitWidth = NewShAmt->getType()->getScalarSizeInBits();
1158bcb0991SDimitry Andric   unsigned XBitWidth = X->getType()->getScalarSizeInBits();
1168bcb0991SDimitry Andric   // Is the new shift amount smaller than the bit width of inner/new shift?
1170b57cec5SDimitry Andric   if (!match(NewShAmt, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT,
1188bcb0991SDimitry Andric                                           APInt(NewShAmtBitWidth, XBitWidth))))
1198bcb0991SDimitry Andric     return nullptr; // FIXME: could perform constant-folding.
1208bcb0991SDimitry Andric 
1218bcb0991SDimitry Andric   // If there was a truncation, and we have a right-shift, we can only fold if
1228bcb0991SDimitry Andric   // we are left with the original sign bit. Likewise, if we were just checking
1238bcb0991SDimitry Andric   // that this is a sighbit extraction, this is the place to check it.
1248bcb0991SDimitry Andric   // FIXME: zero shift amount is also legal here, but we can't *easily* check
1258bcb0991SDimitry Andric   // more than one predicate so it's not really worth it.
1268bcb0991SDimitry Andric   if (HadTwoRightShifts && (Trunc || AnalyzeForSignBitExtraction)) {
1278bcb0991SDimitry Andric     // If it's not a sign bit extraction, then we're done.
1288bcb0991SDimitry Andric     if (!match(NewShAmt,
1298bcb0991SDimitry Andric                m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ,
1308bcb0991SDimitry Andric                                   APInt(NewShAmtBitWidth, XBitWidth - 1))))
1310b57cec5SDimitry Andric       return nullptr;
1328bcb0991SDimitry Andric     // If it is, and that was the question, return the base value.
1338bcb0991SDimitry Andric     if (AnalyzeForSignBitExtraction)
1348bcb0991SDimitry Andric       return X;
1358bcb0991SDimitry Andric   }
1368bcb0991SDimitry Andric 
1378bcb0991SDimitry Andric   assert(IdenticalShOpcodes && "Should not get here with different shifts.");
1388bcb0991SDimitry Andric 
1395f757f3fSDimitry Andric   if (NewShAmt->getType() != X->getType()) {
1405f757f3fSDimitry Andric     NewShAmt = ConstantFoldCastOperand(Instruction::ZExt, NewShAmt,
1415f757f3fSDimitry Andric                                        X->getType(), SQ.DL);
1425f757f3fSDimitry Andric     if (!NewShAmt)
1435f757f3fSDimitry Andric       return nullptr;
1445f757f3fSDimitry Andric   }
1458bcb0991SDimitry Andric 
1465f757f3fSDimitry Andric   // All good, we can do this fold.
1470b57cec5SDimitry Andric   BinaryOperator *NewShift = BinaryOperator::Create(ShiftOpcode, X, NewShAmt);
1488bcb0991SDimitry Andric 
1498bcb0991SDimitry Andric   // The flags can only be propagated if there wasn't a trunc.
1508bcb0991SDimitry Andric   if (!Trunc) {
1518bcb0991SDimitry Andric     // If the pattern did not involve trunc, and both of the original shifts
1528bcb0991SDimitry Andric     // had the same flag set, preserve the flag.
1530b57cec5SDimitry Andric     if (ShiftOpcode == Instruction::BinaryOps::Shl) {
1540b57cec5SDimitry Andric       NewShift->setHasNoUnsignedWrap(Sh0->hasNoUnsignedWrap() &&
1550b57cec5SDimitry Andric                                      Sh1->hasNoUnsignedWrap());
1560b57cec5SDimitry Andric       NewShift->setHasNoSignedWrap(Sh0->hasNoSignedWrap() &&
1570b57cec5SDimitry Andric                                    Sh1->hasNoSignedWrap());
1580b57cec5SDimitry Andric     } else {
1590b57cec5SDimitry Andric       NewShift->setIsExact(Sh0->isExact() && Sh1->isExact());
1600b57cec5SDimitry Andric     }
1618bcb0991SDimitry Andric   }
1628bcb0991SDimitry Andric 
1638bcb0991SDimitry Andric   Instruction *Ret = NewShift;
1648bcb0991SDimitry Andric   if (Trunc) {
1658bcb0991SDimitry Andric     Builder.Insert(NewShift);
1668bcb0991SDimitry Andric     Ret = CastInst::Create(Instruction::Trunc, NewShift, Sh0->getType());
1678bcb0991SDimitry Andric   }
1688bcb0991SDimitry Andric 
1698bcb0991SDimitry Andric   return Ret;
1708bcb0991SDimitry Andric }
1718bcb0991SDimitry Andric 
1728bcb0991SDimitry Andric // If we have some pattern that leaves only some low bits set, and then performs
1738bcb0991SDimitry Andric // left-shift of those bits, if none of the bits that are left after the final
1748bcb0991SDimitry Andric // shift are modified by the mask, we can omit the mask.
1758bcb0991SDimitry Andric //
1768bcb0991SDimitry Andric // There are many variants to this pattern:
1778bcb0991SDimitry Andric //   a)  (x & ((1 << MaskShAmt) - 1)) << ShiftShAmt
1788bcb0991SDimitry Andric //   b)  (x & (~(-1 << MaskShAmt))) << ShiftShAmt
179349cc55cSDimitry Andric //   c)  (x & (-1 l>> MaskShAmt)) << ShiftShAmt
180349cc55cSDimitry Andric //   d)  (x & ((-1 << MaskShAmt) l>> MaskShAmt)) << ShiftShAmt
1818bcb0991SDimitry Andric //   e)  ((x << MaskShAmt) l>> MaskShAmt) << ShiftShAmt
1828bcb0991SDimitry Andric //   f)  ((x << MaskShAmt) a>> MaskShAmt) << ShiftShAmt
1838bcb0991SDimitry Andric // All these patterns can be simplified to just:
1848bcb0991SDimitry Andric //   x << ShiftShAmt
1858bcb0991SDimitry Andric // iff:
1868bcb0991SDimitry Andric //   a,b)     (MaskShAmt+ShiftShAmt) u>= bitwidth(x)
1878bcb0991SDimitry Andric //   c,d,e,f) (ShiftShAmt-MaskShAmt) s>= 0 (i.e. ShiftShAmt u>= MaskShAmt)
1888bcb0991SDimitry Andric static Instruction *
1898bcb0991SDimitry Andric dropRedundantMaskingOfLeftShiftInput(BinaryOperator *OuterShift,
1908bcb0991SDimitry Andric                                      const SimplifyQuery &Q,
1918bcb0991SDimitry Andric                                      InstCombiner::BuilderTy &Builder) {
1928bcb0991SDimitry Andric   assert(OuterShift->getOpcode() == Instruction::BinaryOps::Shl &&
1938bcb0991SDimitry Andric          "The input must be 'shl'!");
1948bcb0991SDimitry Andric 
1958bcb0991SDimitry Andric   Value *Masked, *ShiftShAmt;
196480093f4SDimitry Andric   match(OuterShift,
197480093f4SDimitry Andric         m_Shift(m_Value(Masked), m_ZExtOrSelf(m_Value(ShiftShAmt))));
198480093f4SDimitry Andric 
199480093f4SDimitry Andric   // *If* there is a truncation between an outer shift and a possibly-mask,
200480093f4SDimitry Andric   // then said truncation *must* be one-use, else we can't perform the fold.
201480093f4SDimitry Andric   Value *Trunc;
202480093f4SDimitry Andric   if (match(Masked, m_CombineAnd(m_Trunc(m_Value(Masked)), m_Value(Trunc))) &&
203480093f4SDimitry Andric       !Trunc->hasOneUse())
204480093f4SDimitry Andric     return nullptr;
2058bcb0991SDimitry Andric 
2068bcb0991SDimitry Andric   Type *NarrowestTy = OuterShift->getType();
2078bcb0991SDimitry Andric   Type *WidestTy = Masked->getType();
208480093f4SDimitry Andric   bool HadTrunc = WidestTy != NarrowestTy;
209480093f4SDimitry Andric 
2108bcb0991SDimitry Andric   // The mask must be computed in a type twice as wide to ensure
2118bcb0991SDimitry Andric   // that no bits are lost if the sum-of-shifts is wider than the base type.
2128bcb0991SDimitry Andric   Type *ExtendedTy = WidestTy->getExtendedType();
2138bcb0991SDimitry Andric 
2148bcb0991SDimitry Andric   Value *MaskShAmt;
2158bcb0991SDimitry Andric 
2168bcb0991SDimitry Andric   // ((1 << MaskShAmt) - 1)
2178bcb0991SDimitry Andric   auto MaskA = m_Add(m_Shl(m_One(), m_Value(MaskShAmt)), m_AllOnes());
2188bcb0991SDimitry Andric   // (~(-1 << maskNbits))
219*0fca6ea1SDimitry Andric   auto MaskB = m_Not(m_Shl(m_AllOnes(), m_Value(MaskShAmt)));
220349cc55cSDimitry Andric   // (-1 l>> MaskShAmt)
221349cc55cSDimitry Andric   auto MaskC = m_LShr(m_AllOnes(), m_Value(MaskShAmt));
222349cc55cSDimitry Andric   // ((-1 << MaskShAmt) l>> MaskShAmt)
2238bcb0991SDimitry Andric   auto MaskD =
224349cc55cSDimitry Andric       m_LShr(m_Shl(m_AllOnes(), m_Value(MaskShAmt)), m_Deferred(MaskShAmt));
2258bcb0991SDimitry Andric 
2268bcb0991SDimitry Andric   Value *X;
2278bcb0991SDimitry Andric   Constant *NewMask;
2288bcb0991SDimitry Andric 
2298bcb0991SDimitry Andric   if (match(Masked, m_c_And(m_CombineOr(MaskA, MaskB), m_Value(X)))) {
230480093f4SDimitry Andric     // Peek through an optional zext of the shift amount.
231480093f4SDimitry Andric     match(MaskShAmt, m_ZExtOrSelf(m_Value(MaskShAmt)));
232480093f4SDimitry Andric 
23323408297SDimitry Andric     // Verify that it would be safe to try to add those two shift amounts.
23423408297SDimitry Andric     if (!canTryToConstantAddTwoShiftAmounts(OuterShift, ShiftShAmt, Masked,
23523408297SDimitry Andric                                             MaskShAmt))
236480093f4SDimitry Andric       return nullptr;
237480093f4SDimitry Andric 
2388bcb0991SDimitry Andric     // Can we simplify (MaskShAmt+ShiftShAmt) ?
23981ad6265SDimitry Andric     auto *SumOfShAmts = dyn_cast_or_null<Constant>(simplifyAddInst(
2408bcb0991SDimitry Andric         MaskShAmt, ShiftShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q));
2418bcb0991SDimitry Andric     if (!SumOfShAmts)
2428bcb0991SDimitry Andric       return nullptr; // Did not simplify.
2438bcb0991SDimitry Andric     // In this pattern SumOfShAmts correlates with the number of low bits
2448bcb0991SDimitry Andric     // that shall remain in the root value (OuterShift).
2458bcb0991SDimitry Andric 
2468bcb0991SDimitry Andric     // An extend of an undef value becomes zero because the high bits are never
247349cc55cSDimitry Andric     // completely unknown. Replace the `undef` shift amounts with final
2488bcb0991SDimitry Andric     // shift bitwidth to ensure that the value remains undef when creating the
2498bcb0991SDimitry Andric     // subsequent shift op.
250480093f4SDimitry Andric     SumOfShAmts = Constant::replaceUndefsWith(
2518bcb0991SDimitry Andric         SumOfShAmts, ConstantInt::get(SumOfShAmts->getType()->getScalarType(),
2528bcb0991SDimitry Andric                                       ExtendedTy->getScalarSizeInBits()));
2535f757f3fSDimitry Andric     auto *ExtendedSumOfShAmts = ConstantFoldCastOperand(
2545f757f3fSDimitry Andric         Instruction::ZExt, SumOfShAmts, ExtendedTy, Q.DL);
2555f757f3fSDimitry Andric     if (!ExtendedSumOfShAmts)
2565f757f3fSDimitry Andric       return nullptr;
2575f757f3fSDimitry Andric 
2588bcb0991SDimitry Andric     // And compute the mask as usual: ~(-1 << (SumOfShAmts))
2598bcb0991SDimitry Andric     auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy);
260*0fca6ea1SDimitry Andric     Constant *ExtendedInvertedMask = ConstantFoldBinaryOpOperands(
261*0fca6ea1SDimitry Andric         Instruction::Shl, ExtendedAllOnes, ExtendedSumOfShAmts, Q.DL);
262*0fca6ea1SDimitry Andric     if (!ExtendedInvertedMask)
263*0fca6ea1SDimitry Andric       return nullptr;
264*0fca6ea1SDimitry Andric 
2658bcb0991SDimitry Andric     NewMask = ConstantExpr::getNot(ExtendedInvertedMask);
2668bcb0991SDimitry Andric   } else if (match(Masked, m_c_And(m_CombineOr(MaskC, MaskD), m_Value(X))) ||
2678bcb0991SDimitry Andric              match(Masked, m_Shr(m_Shl(m_Value(X), m_Value(MaskShAmt)),
2688bcb0991SDimitry Andric                                  m_Deferred(MaskShAmt)))) {
269480093f4SDimitry Andric     // Peek through an optional zext of the shift amount.
270480093f4SDimitry Andric     match(MaskShAmt, m_ZExtOrSelf(m_Value(MaskShAmt)));
271480093f4SDimitry Andric 
27223408297SDimitry Andric     // Verify that it would be safe to try to add those two shift amounts.
27323408297SDimitry Andric     if (!canTryToConstantAddTwoShiftAmounts(OuterShift, ShiftShAmt, Masked,
27423408297SDimitry Andric                                             MaskShAmt))
275480093f4SDimitry Andric       return nullptr;
276480093f4SDimitry Andric 
2778bcb0991SDimitry Andric     // Can we simplify (ShiftShAmt-MaskShAmt) ?
27881ad6265SDimitry Andric     auto *ShAmtsDiff = dyn_cast_or_null<Constant>(simplifySubInst(
2798bcb0991SDimitry Andric         ShiftShAmt, MaskShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q));
2808bcb0991SDimitry Andric     if (!ShAmtsDiff)
2818bcb0991SDimitry Andric       return nullptr; // Did not simplify.
2828bcb0991SDimitry Andric     // In this pattern ShAmtsDiff correlates with the number of high bits that
2838bcb0991SDimitry Andric     // shall be unset in the root value (OuterShift).
2848bcb0991SDimitry Andric 
2858bcb0991SDimitry Andric     // An extend of an undef value becomes zero because the high bits are never
286349cc55cSDimitry Andric     // completely unknown. Replace the `undef` shift amounts with negated
2878bcb0991SDimitry Andric     // bitwidth of innermost shift to ensure that the value remains undef when
2888bcb0991SDimitry Andric     // creating the subsequent shift op.
2898bcb0991SDimitry Andric     unsigned WidestTyBitWidth = WidestTy->getScalarSizeInBits();
290480093f4SDimitry Andric     ShAmtsDiff = Constant::replaceUndefsWith(
2918bcb0991SDimitry Andric         ShAmtsDiff, ConstantInt::get(ShAmtsDiff->getType()->getScalarType(),
2928bcb0991SDimitry Andric                                      -WidestTyBitWidth));
2935f757f3fSDimitry Andric     auto *ExtendedNumHighBitsToClear = ConstantFoldCastOperand(
2945f757f3fSDimitry Andric         Instruction::ZExt,
2958bcb0991SDimitry Andric         ConstantExpr::getSub(ConstantInt::get(ShAmtsDiff->getType(),
2968bcb0991SDimitry Andric                                               WidestTyBitWidth,
2978bcb0991SDimitry Andric                                               /*isSigned=*/false),
2988bcb0991SDimitry Andric                              ShAmtsDiff),
2995f757f3fSDimitry Andric         ExtendedTy, Q.DL);
3005f757f3fSDimitry Andric     if (!ExtendedNumHighBitsToClear)
3015f757f3fSDimitry Andric       return nullptr;
3025f757f3fSDimitry Andric 
3038bcb0991SDimitry Andric     // And compute the mask as usual: (-1 l>> (NumHighBitsToClear))
3048bcb0991SDimitry Andric     auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(ExtendedTy);
3055f757f3fSDimitry Andric     NewMask = ConstantFoldBinaryOpOperands(Instruction::LShr, ExtendedAllOnes,
3065f757f3fSDimitry Andric                                            ExtendedNumHighBitsToClear, Q.DL);
3075f757f3fSDimitry Andric     if (!NewMask)
3085f757f3fSDimitry Andric       return nullptr;
3098bcb0991SDimitry Andric   } else
3108bcb0991SDimitry Andric     return nullptr; // Don't know anything about this pattern.
3118bcb0991SDimitry Andric 
3128bcb0991SDimitry Andric   NewMask = ConstantExpr::getTrunc(NewMask, NarrowestTy);
3138bcb0991SDimitry Andric 
3148bcb0991SDimitry Andric   // Does this mask has any unset bits? If not then we can just not apply it.
3158bcb0991SDimitry Andric   bool NeedMask = !match(NewMask, m_AllOnes());
3168bcb0991SDimitry Andric 
3178bcb0991SDimitry Andric   // If we need to apply a mask, there are several more restrictions we have.
3188bcb0991SDimitry Andric   if (NeedMask) {
3198bcb0991SDimitry Andric     // The old masking instruction must go away.
3208bcb0991SDimitry Andric     if (!Masked->hasOneUse())
3218bcb0991SDimitry Andric       return nullptr;
3228bcb0991SDimitry Andric     // The original "masking" instruction must not have been`ashr`.
3238bcb0991SDimitry Andric     if (match(Masked, m_AShr(m_Value(), m_Value())))
3248bcb0991SDimitry Andric       return nullptr;
3258bcb0991SDimitry Andric   }
3268bcb0991SDimitry Andric 
327480093f4SDimitry Andric   // If we need to apply truncation, let's do it first, since we can.
328480093f4SDimitry Andric   // We have already ensured that the old truncation will go away.
329480093f4SDimitry Andric   if (HadTrunc)
330480093f4SDimitry Andric     X = Builder.CreateTrunc(X, NarrowestTy);
331480093f4SDimitry Andric 
3328bcb0991SDimitry Andric   // No 'NUW'/'NSW'! We no longer know that we won't shift-out non-0 bits.
333480093f4SDimitry Andric   // We didn't change the Type of this outermost shift, so we can just do it.
3348bcb0991SDimitry Andric   auto *NewShift = BinaryOperator::Create(OuterShift->getOpcode(), X,
3358bcb0991SDimitry Andric                                           OuterShift->getOperand(1));
3368bcb0991SDimitry Andric   if (!NeedMask)
3370b57cec5SDimitry Andric     return NewShift;
3388bcb0991SDimitry Andric 
3398bcb0991SDimitry Andric   Builder.Insert(NewShift);
3408bcb0991SDimitry Andric   return BinaryOperator::Create(Instruction::And, NewShift, NewMask);
3410b57cec5SDimitry Andric }
3420b57cec5SDimitry Andric 
34306c3fb27SDimitry Andric /// If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/
34406c3fb27SDimitry Andric /// shl) that itself has a shift-by-constant operand with identical opcode, we
34506c3fb27SDimitry Andric /// may be able to convert that into 2 independent shifts followed by the logic
34606c3fb27SDimitry Andric /// op. This eliminates a use of an intermediate value (reduces dependency
34706c3fb27SDimitry Andric /// chain).
34806c3fb27SDimitry Andric static Instruction *foldShiftOfShiftedBinOp(BinaryOperator &I,
349480093f4SDimitry Andric                                             InstCombiner::BuilderTy &Builder) {
350480093f4SDimitry Andric   assert(I.isShift() && "Expected a shift as input");
35106c3fb27SDimitry Andric   auto *BinInst = dyn_cast<BinaryOperator>(I.getOperand(0));
35206c3fb27SDimitry Andric   if (!BinInst ||
35306c3fb27SDimitry Andric       (!BinInst->isBitwiseLogicOp() &&
35406c3fb27SDimitry Andric        BinInst->getOpcode() != Instruction::Add &&
35506c3fb27SDimitry Andric        BinInst->getOpcode() != Instruction::Sub) ||
35606c3fb27SDimitry Andric       !BinInst->hasOneUse())
357480093f4SDimitry Andric     return nullptr;
358480093f4SDimitry Andric 
359e8d8bef9SDimitry Andric   Constant *C0, *C1;
360e8d8bef9SDimitry Andric   if (!match(I.getOperand(1), m_Constant(C1)))
361480093f4SDimitry Andric     return nullptr;
362480093f4SDimitry Andric 
363480093f4SDimitry Andric   Instruction::BinaryOps ShiftOpcode = I.getOpcode();
36406c3fb27SDimitry Andric   // Transform for add/sub only works with shl.
36506c3fb27SDimitry Andric   if ((BinInst->getOpcode() == Instruction::Add ||
36606c3fb27SDimitry Andric        BinInst->getOpcode() == Instruction::Sub) &&
36706c3fb27SDimitry Andric       ShiftOpcode != Instruction::Shl)
36806c3fb27SDimitry Andric     return nullptr;
36906c3fb27SDimitry Andric 
370480093f4SDimitry Andric   Type *Ty = I.getType();
371480093f4SDimitry Andric 
3727a6dacacSDimitry Andric   // Find a matching shift by constant. The fold is not valid if the sum
373480093f4SDimitry Andric   // of the shift values equals or exceeds bitwidth.
374480093f4SDimitry Andric   Value *X, *Y;
3757a6dacacSDimitry Andric   auto matchFirstShift = [&](Value *V, Value *W) {
3767a6dacacSDimitry Andric     unsigned Size = Ty->getScalarSizeInBits();
3777a6dacacSDimitry Andric     APInt Threshold(Size, Size);
3787a6dacacSDimitry Andric     return match(V, m_BinOp(ShiftOpcode, m_Value(X), m_Constant(C0))) &&
3797a6dacacSDimitry Andric            (V->hasOneUse() || match(W, m_ImmConstant())) &&
380e8d8bef9SDimitry Andric            match(ConstantExpr::getAdd(C0, C1),
381e8d8bef9SDimitry Andric                  m_SpecificInt_ICMP(ICmpInst::ICMP_ULT, Threshold));
382480093f4SDimitry Andric   };
383480093f4SDimitry Andric 
38406c3fb27SDimitry Andric   // Logic ops and Add are commutative, so check each operand for a match. Sub
38506c3fb27SDimitry Andric   // is not so we cannot reoder if we match operand(1) and need to keep the
38606c3fb27SDimitry Andric   // operands in their original positions.
38706c3fb27SDimitry Andric   bool FirstShiftIsOp1 = false;
3887a6dacacSDimitry Andric   if (matchFirstShift(BinInst->getOperand(0), BinInst->getOperand(1)))
38906c3fb27SDimitry Andric     Y = BinInst->getOperand(1);
3907a6dacacSDimitry Andric   else if (matchFirstShift(BinInst->getOperand(1), BinInst->getOperand(0))) {
39106c3fb27SDimitry Andric     Y = BinInst->getOperand(0);
39206c3fb27SDimitry Andric     FirstShiftIsOp1 = BinInst->getOpcode() == Instruction::Sub;
39306c3fb27SDimitry Andric   } else
394480093f4SDimitry Andric     return nullptr;
395480093f4SDimitry Andric 
39606c3fb27SDimitry Andric   // shift (binop (shift X, C0), Y), C1 -> binop (shift X, C0+C1), (shift Y, C1)
397e8d8bef9SDimitry Andric   Constant *ShiftSumC = ConstantExpr::getAdd(C0, C1);
398480093f4SDimitry Andric   Value *NewShift1 = Builder.CreateBinOp(ShiftOpcode, X, ShiftSumC);
399bdd1243dSDimitry Andric   Value *NewShift2 = Builder.CreateBinOp(ShiftOpcode, Y, C1);
40006c3fb27SDimitry Andric   Value *Op1 = FirstShiftIsOp1 ? NewShift2 : NewShift1;
40106c3fb27SDimitry Andric   Value *Op2 = FirstShiftIsOp1 ? NewShift1 : NewShift2;
40206c3fb27SDimitry Andric   return BinaryOperator::Create(BinInst->getOpcode(), Op1, Op2);
403480093f4SDimitry Andric }
404480093f4SDimitry Andric 
405e8d8bef9SDimitry Andric Instruction *InstCombinerImpl::commonShiftTransforms(BinaryOperator &I) {
40604eeddc0SDimitry Andric   if (Instruction *Phi = foldBinopWithPhiOperands(I))
40704eeddc0SDimitry Andric     return Phi;
40804eeddc0SDimitry Andric 
4090b57cec5SDimitry Andric   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
4100b57cec5SDimitry Andric   assert(Op0->getType() == Op1->getType());
41181ad6265SDimitry Andric   Type *Ty = I.getType();
4120b57cec5SDimitry Andric 
4138bcb0991SDimitry Andric   // If the shift amount is a one-use `sext`, we can demote it to `zext`.
4148bcb0991SDimitry Andric   Value *Y;
4158bcb0991SDimitry Andric   if (match(Op1, m_OneUse(m_SExt(m_Value(Y))))) {
41681ad6265SDimitry Andric     Value *NewExt = Builder.CreateZExt(Y, Ty, Op1->getName());
4178bcb0991SDimitry Andric     return BinaryOperator::Create(I.getOpcode(), Op0, NewExt);
4188bcb0991SDimitry Andric   }
4198bcb0991SDimitry Andric 
4200b57cec5SDimitry Andric   // See if we can fold away this shift.
4210b57cec5SDimitry Andric   if (SimplifyDemandedInstructionBits(I))
4220b57cec5SDimitry Andric     return &I;
4230b57cec5SDimitry Andric 
4240b57cec5SDimitry Andric   // Try to fold constant and into select arguments.
4250b57cec5SDimitry Andric   if (isa<Constant>(Op0))
4260b57cec5SDimitry Andric     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
4270b57cec5SDimitry Andric       if (Instruction *R = FoldOpIntoSelect(I, SI))
4280b57cec5SDimitry Andric         return R;
4290b57cec5SDimitry Andric 
4300b57cec5SDimitry Andric   if (Constant *CUI = dyn_cast<Constant>(Op1))
4310b57cec5SDimitry Andric     if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
4320b57cec5SDimitry Andric       return Res;
4330b57cec5SDimitry Andric 
4348bcb0991SDimitry Andric   if (auto *NewShift = cast_or_null<Instruction>(
4358bcb0991SDimitry Andric           reassociateShiftAmtsOfTwoSameDirectionShifts(&I, SQ)))
4360b57cec5SDimitry Andric     return NewShift;
4370b57cec5SDimitry Andric 
43881ad6265SDimitry Andric   // Pre-shift a constant shifted by a variable amount with constant offset:
43981ad6265SDimitry Andric   // C shift (A add nuw C1) --> (C shift C1) shift A
4400b57cec5SDimitry Andric   Value *A;
44181ad6265SDimitry Andric   Constant *C, *C1;
44281ad6265SDimitry Andric   if (match(Op0, m_Constant(C)) &&
443*0fca6ea1SDimitry Andric       match(Op1, m_NUWAddLike(m_Value(A), m_Constant(C1)))) {
44481ad6265SDimitry Andric     Value *NewC = Builder.CreateBinOp(I.getOpcode(), C, C1);
445*0fca6ea1SDimitry Andric     BinaryOperator *NewShiftOp = BinaryOperator::Create(I.getOpcode(), NewC, A);
446*0fca6ea1SDimitry Andric     if (I.getOpcode() == Instruction::Shl) {
447*0fca6ea1SDimitry Andric       NewShiftOp->setHasNoSignedWrap(I.hasNoSignedWrap());
448*0fca6ea1SDimitry Andric       NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
449*0fca6ea1SDimitry Andric     } else {
450*0fca6ea1SDimitry Andric       NewShiftOp->setIsExact(I.isExact());
451*0fca6ea1SDimitry Andric     }
452*0fca6ea1SDimitry Andric     return NewShiftOp;
45381ad6265SDimitry Andric   }
45481ad6265SDimitry Andric 
45581ad6265SDimitry Andric   unsigned BitWidth = Ty->getScalarSizeInBits();
45681ad6265SDimitry Andric 
45781ad6265SDimitry Andric   const APInt *AC, *AddC;
45881ad6265SDimitry Andric   // Try to pre-shift a constant shifted by a variable amount added with a
45981ad6265SDimitry Andric   // negative number:
46081ad6265SDimitry Andric   // C << (X - AddC) --> (C >> AddC) << X
46181ad6265SDimitry Andric   // and
46281ad6265SDimitry Andric   // C >> (X - AddC) --> (C << AddC) >> X
46381ad6265SDimitry Andric   if (match(Op0, m_APInt(AC)) && match(Op1, m_Add(m_Value(A), m_APInt(AddC))) &&
46481ad6265SDimitry Andric       AddC->isNegative() && (-*AddC).ult(BitWidth)) {
46581ad6265SDimitry Andric     assert(!AC->isZero() && "Expected simplify of shifted zero");
46681ad6265SDimitry Andric     unsigned PosOffset = (-*AddC).getZExtValue();
46781ad6265SDimitry Andric 
46881ad6265SDimitry Andric     auto isSuitableForPreShift = [PosOffset, &I, AC]() {
46981ad6265SDimitry Andric       switch (I.getOpcode()) {
47081ad6265SDimitry Andric       default:
47181ad6265SDimitry Andric         return false;
47281ad6265SDimitry Andric       case Instruction::Shl:
47381ad6265SDimitry Andric         return (I.hasNoSignedWrap() || I.hasNoUnsignedWrap()) &&
47481ad6265SDimitry Andric                AC->eq(AC->lshr(PosOffset).shl(PosOffset));
47581ad6265SDimitry Andric       case Instruction::LShr:
47681ad6265SDimitry Andric         return I.isExact() && AC->eq(AC->shl(PosOffset).lshr(PosOffset));
47781ad6265SDimitry Andric       case Instruction::AShr:
47881ad6265SDimitry Andric         return I.isExact() && AC->eq(AC->shl(PosOffset).ashr(PosOffset));
47981ad6265SDimitry Andric       }
48081ad6265SDimitry Andric     };
48181ad6265SDimitry Andric     if (isSuitableForPreShift()) {
48281ad6265SDimitry Andric       Constant *NewC = ConstantInt::get(Ty, I.getOpcode() == Instruction::Shl
48381ad6265SDimitry Andric                                                 ? AC->lshr(PosOffset)
48481ad6265SDimitry Andric                                                 : AC->shl(PosOffset));
48581ad6265SDimitry Andric       BinaryOperator *NewShiftOp =
48681ad6265SDimitry Andric           BinaryOperator::Create(I.getOpcode(), NewC, A);
48781ad6265SDimitry Andric       if (I.getOpcode() == Instruction::Shl) {
48881ad6265SDimitry Andric         NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
48981ad6265SDimitry Andric       } else {
49081ad6265SDimitry Andric         NewShiftOp->setIsExact();
49181ad6265SDimitry Andric       }
49281ad6265SDimitry Andric       return NewShiftOp;
49381ad6265SDimitry Andric     }
49481ad6265SDimitry Andric   }
4950b57cec5SDimitry Andric 
496e8d8bef9SDimitry Andric   // X shift (A srem C) -> X shift (A and (C - 1)) iff C is a power of 2.
4970b57cec5SDimitry Andric   // Because shifts by negative values (which could occur if A were negative)
4980b57cec5SDimitry Andric   // are undefined.
499e8d8bef9SDimitry Andric   if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Constant(C))) &&
500e8d8bef9SDimitry Andric       match(C, m_Power2())) {
5010b57cec5SDimitry Andric     // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't
5020b57cec5SDimitry Andric     // demand the sign bit (and many others) here??
50381ad6265SDimitry Andric     Constant *Mask = ConstantExpr::getSub(C, ConstantInt::get(Ty, 1));
504e8d8bef9SDimitry Andric     Value *Rem = Builder.CreateAnd(A, Mask, Op1->getName());
5055ffd83dbSDimitry Andric     return replaceOperand(I, 1, Rem);
5060b57cec5SDimitry Andric   }
5070b57cec5SDimitry Andric 
50806c3fb27SDimitry Andric   if (Instruction *Logic = foldShiftOfShiftedBinOp(I, Builder))
509480093f4SDimitry Andric     return Logic;
510480093f4SDimitry Andric 
51106c3fb27SDimitry Andric   if (match(Op1, m_Or(m_Value(), m_SpecificInt(BitWidth - 1))))
51206c3fb27SDimitry Andric     return replaceOperand(I, 1, ConstantInt::get(Ty, BitWidth - 1));
51306c3fb27SDimitry Andric 
5140b57cec5SDimitry Andric   return nullptr;
5150b57cec5SDimitry Andric }
5160b57cec5SDimitry Andric 
5170b57cec5SDimitry Andric /// Return true if we can simplify two logical (either left or right) shifts
5180b57cec5SDimitry Andric /// that have constant shift amounts: OuterShift (InnerShift X, C1), C2.
5190b57cec5SDimitry Andric static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl,
520e8d8bef9SDimitry Andric                                     Instruction *InnerShift,
521e8d8bef9SDimitry Andric                                     InstCombinerImpl &IC, Instruction *CxtI) {
5220b57cec5SDimitry Andric   assert(InnerShift->isLogicalShift() && "Unexpected instruction type");
5230b57cec5SDimitry Andric 
5240b57cec5SDimitry Andric   // We need constant scalar or constant splat shifts.
5250b57cec5SDimitry Andric   const APInt *InnerShiftConst;
5260b57cec5SDimitry Andric   if (!match(InnerShift->getOperand(1), m_APInt(InnerShiftConst)))
5270b57cec5SDimitry Andric     return false;
5280b57cec5SDimitry Andric 
5290b57cec5SDimitry Andric   // Two logical shifts in the same direction:
5300b57cec5SDimitry Andric   // shl (shl X, C1), C2 -->  shl X, C1 + C2
5310b57cec5SDimitry Andric   // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
5320b57cec5SDimitry Andric   bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
5330b57cec5SDimitry Andric   if (IsInnerShl == IsOuterShl)
5340b57cec5SDimitry Andric     return true;
5350b57cec5SDimitry Andric 
5360b57cec5SDimitry Andric   // Equal shift amounts in opposite directions become bitwise 'and':
5370b57cec5SDimitry Andric   // lshr (shl X, C), C --> and X, C'
5380b57cec5SDimitry Andric   // shl (lshr X, C), C --> and X, C'
5390b57cec5SDimitry Andric   if (*InnerShiftConst == OuterShAmt)
5400b57cec5SDimitry Andric     return true;
5410b57cec5SDimitry Andric 
5420b57cec5SDimitry Andric   // If the 2nd shift is bigger than the 1st, we can fold:
5430b57cec5SDimitry Andric   // lshr (shl X, C1), C2 -->  and (shl X, C1 - C2), C3
5440b57cec5SDimitry Andric   // shl (lshr X, C1), C2 --> and (lshr X, C1 - C2), C3
5450b57cec5SDimitry Andric   // but it isn't profitable unless we know the and'd out bits are already zero.
5460b57cec5SDimitry Andric   // Also, check that the inner shift is valid (less than the type width) or
5470b57cec5SDimitry Andric   // we'll crash trying to produce the bit mask for the 'and'.
5480b57cec5SDimitry Andric   unsigned TypeWidth = InnerShift->getType()->getScalarSizeInBits();
5490b57cec5SDimitry Andric   if (InnerShiftConst->ugt(OuterShAmt) && InnerShiftConst->ult(TypeWidth)) {
5500b57cec5SDimitry Andric     unsigned InnerShAmt = InnerShiftConst->getZExtValue();
5510b57cec5SDimitry Andric     unsigned MaskShift =
5520b57cec5SDimitry Andric         IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt;
5530b57cec5SDimitry Andric     APInt Mask = APInt::getLowBitsSet(TypeWidth, OuterShAmt) << MaskShift;
5540b57cec5SDimitry Andric     if (IC.MaskedValueIsZero(InnerShift->getOperand(0), Mask, 0, CxtI))
5550b57cec5SDimitry Andric       return true;
5560b57cec5SDimitry Andric   }
5570b57cec5SDimitry Andric 
5580b57cec5SDimitry Andric   return false;
5590b57cec5SDimitry Andric }
5600b57cec5SDimitry Andric 
5610b57cec5SDimitry Andric /// See if we can compute the specified value, but shifted logically to the left
5620b57cec5SDimitry Andric /// or right by some number of bits. This should return true if the expression
5630b57cec5SDimitry Andric /// can be computed for the same cost as the current expression tree. This is
5640b57cec5SDimitry Andric /// used to eliminate extraneous shifting from things like:
5650b57cec5SDimitry Andric ///      %C = shl i128 %A, 64
5660b57cec5SDimitry Andric ///      %D = shl i128 %B, 96
5670b57cec5SDimitry Andric ///      %E = or i128 %C, %D
5680b57cec5SDimitry Andric ///      %F = lshr i128 %E, 64
5690b57cec5SDimitry Andric /// where the client will ask if E can be computed shifted right by 64-bits. If
5700b57cec5SDimitry Andric /// this succeeds, getShiftedValue() will be called to produce the value.
5710b57cec5SDimitry Andric static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift,
572e8d8bef9SDimitry Andric                                InstCombinerImpl &IC, Instruction *CxtI) {
5735f757f3fSDimitry Andric   // We can always evaluate immediate constants.
5745f757f3fSDimitry Andric   if (match(V, m_ImmConstant()))
5750b57cec5SDimitry Andric     return true;
5760b57cec5SDimitry Andric 
5770b57cec5SDimitry Andric   Instruction *I = dyn_cast<Instruction>(V);
5780b57cec5SDimitry Andric   if (!I) return false;
5790b57cec5SDimitry Andric 
5800b57cec5SDimitry Andric   // We can't mutate something that has multiple uses: doing so would
5810b57cec5SDimitry Andric   // require duplicating the instruction in general, which isn't profitable.
5820b57cec5SDimitry Andric   if (!I->hasOneUse()) return false;
5830b57cec5SDimitry Andric 
5840b57cec5SDimitry Andric   switch (I->getOpcode()) {
5850b57cec5SDimitry Andric   default: return false;
5860b57cec5SDimitry Andric   case Instruction::And:
5870b57cec5SDimitry Andric   case Instruction::Or:
5880b57cec5SDimitry Andric   case Instruction::Xor:
5890b57cec5SDimitry Andric     // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
5900b57cec5SDimitry Andric     return canEvaluateShifted(I->getOperand(0), NumBits, IsLeftShift, IC, I) &&
5910b57cec5SDimitry Andric            canEvaluateShifted(I->getOperand(1), NumBits, IsLeftShift, IC, I);
5920b57cec5SDimitry Andric 
5930b57cec5SDimitry Andric   case Instruction::Shl:
5940b57cec5SDimitry Andric   case Instruction::LShr:
5950b57cec5SDimitry Andric     return canEvaluateShiftedShift(NumBits, IsLeftShift, I, IC, CxtI);
5960b57cec5SDimitry Andric 
5970b57cec5SDimitry Andric   case Instruction::Select: {
5980b57cec5SDimitry Andric     SelectInst *SI = cast<SelectInst>(I);
5990b57cec5SDimitry Andric     Value *TrueVal = SI->getTrueValue();
6000b57cec5SDimitry Andric     Value *FalseVal = SI->getFalseValue();
6010b57cec5SDimitry Andric     return canEvaluateShifted(TrueVal, NumBits, IsLeftShift, IC, SI) &&
6020b57cec5SDimitry Andric            canEvaluateShifted(FalseVal, NumBits, IsLeftShift, IC, SI);
6030b57cec5SDimitry Andric   }
6040b57cec5SDimitry Andric   case Instruction::PHI: {
6050b57cec5SDimitry Andric     // We can change a phi if we can change all operands.  Note that we never
6060b57cec5SDimitry Andric     // get into trouble with cyclic PHIs here because we only consider
6070b57cec5SDimitry Andric     // instructions with a single use.
6080b57cec5SDimitry Andric     PHINode *PN = cast<PHINode>(I);
6090b57cec5SDimitry Andric     for (Value *IncValue : PN->incoming_values())
6100b57cec5SDimitry Andric       if (!canEvaluateShifted(IncValue, NumBits, IsLeftShift, IC, PN))
6110b57cec5SDimitry Andric         return false;
6120b57cec5SDimitry Andric     return true;
6130b57cec5SDimitry Andric   }
614fcaf7f86SDimitry Andric   case Instruction::Mul: {
615fcaf7f86SDimitry Andric     const APInt *MulConst;
616fcaf7f86SDimitry Andric     // We can fold (shr (mul X, -(1 << C)), C) -> (and (neg X), C`)
617fcaf7f86SDimitry Andric     return !IsLeftShift && match(I->getOperand(1), m_APInt(MulConst)) &&
61806c3fb27SDimitry Andric            MulConst->isNegatedPowerOf2() && MulConst->countr_zero() == NumBits;
619fcaf7f86SDimitry Andric   }
6200b57cec5SDimitry Andric   }
6210b57cec5SDimitry Andric }
6220b57cec5SDimitry Andric 
6230b57cec5SDimitry Andric /// Fold OuterShift (InnerShift X, C1), C2.
6240b57cec5SDimitry Andric /// See canEvaluateShiftedShift() for the constraints on these instructions.
6250b57cec5SDimitry Andric static Value *foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt,
6260b57cec5SDimitry Andric                                bool IsOuterShl,
6270b57cec5SDimitry Andric                                InstCombiner::BuilderTy &Builder) {
6280b57cec5SDimitry Andric   bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
6290b57cec5SDimitry Andric   Type *ShType = InnerShift->getType();
6300b57cec5SDimitry Andric   unsigned TypeWidth = ShType->getScalarSizeInBits();
6310b57cec5SDimitry Andric 
6320b57cec5SDimitry Andric   // We only accept shifts-by-a-constant in canEvaluateShifted().
6330b57cec5SDimitry Andric   const APInt *C1;
6340b57cec5SDimitry Andric   match(InnerShift->getOperand(1), m_APInt(C1));
6350b57cec5SDimitry Andric   unsigned InnerShAmt = C1->getZExtValue();
6360b57cec5SDimitry Andric 
6370b57cec5SDimitry Andric   // Change the shift amount and clear the appropriate IR flags.
6380b57cec5SDimitry Andric   auto NewInnerShift = [&](unsigned ShAmt) {
6390b57cec5SDimitry Andric     InnerShift->setOperand(1, ConstantInt::get(ShType, ShAmt));
6400b57cec5SDimitry Andric     if (IsInnerShl) {
6410b57cec5SDimitry Andric       InnerShift->setHasNoUnsignedWrap(false);
6420b57cec5SDimitry Andric       InnerShift->setHasNoSignedWrap(false);
6430b57cec5SDimitry Andric     } else {
6440b57cec5SDimitry Andric       InnerShift->setIsExact(false);
6450b57cec5SDimitry Andric     }
6460b57cec5SDimitry Andric     return InnerShift;
6470b57cec5SDimitry Andric   };
6480b57cec5SDimitry Andric 
6490b57cec5SDimitry Andric   // Two logical shifts in the same direction:
6500b57cec5SDimitry Andric   // shl (shl X, C1), C2 -->  shl X, C1 + C2
6510b57cec5SDimitry Andric   // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
6520b57cec5SDimitry Andric   if (IsInnerShl == IsOuterShl) {
6530b57cec5SDimitry Andric     // If this is an oversized composite shift, then unsigned shifts get 0.
6540b57cec5SDimitry Andric     if (InnerShAmt + OuterShAmt >= TypeWidth)
6550b57cec5SDimitry Andric       return Constant::getNullValue(ShType);
6560b57cec5SDimitry Andric 
6570b57cec5SDimitry Andric     return NewInnerShift(InnerShAmt + OuterShAmt);
6580b57cec5SDimitry Andric   }
6590b57cec5SDimitry Andric 
6600b57cec5SDimitry Andric   // Equal shift amounts in opposite directions become bitwise 'and':
6610b57cec5SDimitry Andric   // lshr (shl X, C), C --> and X, C'
6620b57cec5SDimitry Andric   // shl (lshr X, C), C --> and X, C'
6630b57cec5SDimitry Andric   if (InnerShAmt == OuterShAmt) {
6640b57cec5SDimitry Andric     APInt Mask = IsInnerShl
6650b57cec5SDimitry Andric                      ? APInt::getLowBitsSet(TypeWidth, TypeWidth - OuterShAmt)
6660b57cec5SDimitry Andric                      : APInt::getHighBitsSet(TypeWidth, TypeWidth - OuterShAmt);
6670b57cec5SDimitry Andric     Value *And = Builder.CreateAnd(InnerShift->getOperand(0),
6680b57cec5SDimitry Andric                                    ConstantInt::get(ShType, Mask));
6690b57cec5SDimitry Andric     if (auto *AndI = dyn_cast<Instruction>(And)) {
6700b57cec5SDimitry Andric       AndI->moveBefore(InnerShift);
6710b57cec5SDimitry Andric       AndI->takeName(InnerShift);
6720b57cec5SDimitry Andric     }
6730b57cec5SDimitry Andric     return And;
6740b57cec5SDimitry Andric   }
6750b57cec5SDimitry Andric 
6760b57cec5SDimitry Andric   assert(InnerShAmt > OuterShAmt &&
6770b57cec5SDimitry Andric          "Unexpected opposite direction logical shift pair");
6780b57cec5SDimitry Andric 
6790b57cec5SDimitry Andric   // In general, we would need an 'and' for this transform, but
6800b57cec5SDimitry Andric   // canEvaluateShiftedShift() guarantees that the masked-off bits are not used.
6810b57cec5SDimitry Andric   // lshr (shl X, C1), C2 -->  shl X, C1 - C2
6820b57cec5SDimitry Andric   // shl (lshr X, C1), C2 --> lshr X, C1 - C2
6830b57cec5SDimitry Andric   return NewInnerShift(InnerShAmt - OuterShAmt);
6840b57cec5SDimitry Andric }
6850b57cec5SDimitry Andric 
6860b57cec5SDimitry Andric /// When canEvaluateShifted() returns true for an expression, this function
6870b57cec5SDimitry Andric /// inserts the new computation that produces the shifted value.
6880b57cec5SDimitry Andric static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift,
689e8d8bef9SDimitry Andric                               InstCombinerImpl &IC, const DataLayout &DL) {
6900b57cec5SDimitry Andric   // We can always evaluate constants shifted.
6910b57cec5SDimitry Andric   if (Constant *C = dyn_cast<Constant>(V)) {
6920b57cec5SDimitry Andric     if (isLeftShift)
6935ffd83dbSDimitry Andric       return IC.Builder.CreateShl(C, NumBits);
6940b57cec5SDimitry Andric     else
6955ffd83dbSDimitry Andric       return IC.Builder.CreateLShr(C, NumBits);
6960b57cec5SDimitry Andric   }
6970b57cec5SDimitry Andric 
6980b57cec5SDimitry Andric   Instruction *I = cast<Instruction>(V);
699e8d8bef9SDimitry Andric   IC.addToWorklist(I);
7000b57cec5SDimitry Andric 
7010b57cec5SDimitry Andric   switch (I->getOpcode()) {
7020b57cec5SDimitry Andric   default: llvm_unreachable("Inconsistency with CanEvaluateShifted");
7030b57cec5SDimitry Andric   case Instruction::And:
7040b57cec5SDimitry Andric   case Instruction::Or:
7050b57cec5SDimitry Andric   case Instruction::Xor:
7060b57cec5SDimitry Andric     // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
7070b57cec5SDimitry Andric     I->setOperand(
7080b57cec5SDimitry Andric         0, getShiftedValue(I->getOperand(0), NumBits, isLeftShift, IC, DL));
7090b57cec5SDimitry Andric     I->setOperand(
7100b57cec5SDimitry Andric         1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
7110b57cec5SDimitry Andric     return I;
7120b57cec5SDimitry Andric 
7130b57cec5SDimitry Andric   case Instruction::Shl:
7140b57cec5SDimitry Andric   case Instruction::LShr:
7150b57cec5SDimitry Andric     return foldShiftedShift(cast<BinaryOperator>(I), NumBits, isLeftShift,
7160b57cec5SDimitry Andric                             IC.Builder);
7170b57cec5SDimitry Andric 
7180b57cec5SDimitry Andric   case Instruction::Select:
7190b57cec5SDimitry Andric     I->setOperand(
7200b57cec5SDimitry Andric         1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
7210b57cec5SDimitry Andric     I->setOperand(
7220b57cec5SDimitry Andric         2, getShiftedValue(I->getOperand(2), NumBits, isLeftShift, IC, DL));
7230b57cec5SDimitry Andric     return I;
7240b57cec5SDimitry Andric   case Instruction::PHI: {
7250b57cec5SDimitry Andric     // We can change a phi if we can change all operands.  Note that we never
7260b57cec5SDimitry Andric     // get into trouble with cyclic PHIs here because we only consider
7270b57cec5SDimitry Andric     // instructions with a single use.
7280b57cec5SDimitry Andric     PHINode *PN = cast<PHINode>(I);
7290b57cec5SDimitry Andric     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
7300b57cec5SDimitry Andric       PN->setIncomingValue(i, getShiftedValue(PN->getIncomingValue(i), NumBits,
7310b57cec5SDimitry Andric                                               isLeftShift, IC, DL));
7320b57cec5SDimitry Andric     return PN;
7330b57cec5SDimitry Andric   }
734fcaf7f86SDimitry Andric   case Instruction::Mul: {
735fcaf7f86SDimitry Andric     assert(!isLeftShift && "Unexpected shift direction!");
736fcaf7f86SDimitry Andric     auto *Neg = BinaryOperator::CreateNeg(I->getOperand(0));
7375f757f3fSDimitry Andric     IC.InsertNewInstWith(Neg, I->getIterator());
738fcaf7f86SDimitry Andric     unsigned TypeWidth = I->getType()->getScalarSizeInBits();
739fcaf7f86SDimitry Andric     APInt Mask = APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits);
740fcaf7f86SDimitry Andric     auto *And = BinaryOperator::CreateAnd(Neg,
741fcaf7f86SDimitry Andric                                           ConstantInt::get(I->getType(), Mask));
742fcaf7f86SDimitry Andric     And->takeName(I);
7435f757f3fSDimitry Andric     return IC.InsertNewInstWith(And, I->getIterator());
744fcaf7f86SDimitry Andric   }
7450b57cec5SDimitry Andric   }
7460b57cec5SDimitry Andric }
7470b57cec5SDimitry Andric 
7480b57cec5SDimitry Andric // If this is a bitwise operator or add with a constant RHS we might be able
7490b57cec5SDimitry Andric // to pull it through a shift.
7500b57cec5SDimitry Andric static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift,
7510b57cec5SDimitry Andric                                          BinaryOperator *BO) {
7520b57cec5SDimitry Andric   switch (BO->getOpcode()) {
7530b57cec5SDimitry Andric   default:
7540b57cec5SDimitry Andric     return false; // Do not perform transform!
7550b57cec5SDimitry Andric   case Instruction::Add:
7560b57cec5SDimitry Andric     return Shift.getOpcode() == Instruction::Shl;
7570b57cec5SDimitry Andric   case Instruction::Or:
7580b57cec5SDimitry Andric   case Instruction::And:
7590b57cec5SDimitry Andric     return true;
760e8d8bef9SDimitry Andric   case Instruction::Xor:
761e8d8bef9SDimitry Andric     // Do not change a 'not' of logical shift because that would create a normal
762e8d8bef9SDimitry Andric     // 'xor'. The 'not' is likely better for analysis, SCEV, and codegen.
763e8d8bef9SDimitry Andric     return !(Shift.isLogicalShift() && match(BO, m_Not(m_Value())));
7640b57cec5SDimitry Andric   }
7650b57cec5SDimitry Andric }
7660b57cec5SDimitry Andric 
76781ad6265SDimitry Andric Instruction *InstCombinerImpl::FoldShiftByConstant(Value *Op0, Constant *C1,
7680b57cec5SDimitry Andric                                                    BinaryOperator &I) {
76981ad6265SDimitry Andric   // (C2 << X) << C1 --> (C2 << C1) << X
77081ad6265SDimitry Andric   // (C2 >> X) >> C1 --> (C2 >> C1) >> X
77181ad6265SDimitry Andric   Constant *C2;
77281ad6265SDimitry Andric   Value *X;
773bdd1243dSDimitry Andric   bool IsLeftShift = I.getOpcode() == Instruction::Shl;
774*0fca6ea1SDimitry Andric   if (match(Op0, m_BinOp(I.getOpcode(), m_ImmConstant(C2), m_Value(X)))) {
775*0fca6ea1SDimitry Andric     Instruction *R = BinaryOperator::Create(
776*0fca6ea1SDimitry Andric         I.getOpcode(), Builder.CreateBinOp(I.getOpcode(), C2, C1), X);
777*0fca6ea1SDimitry Andric     BinaryOperator *BO0 = cast<BinaryOperator>(Op0);
778*0fca6ea1SDimitry Andric     if (IsLeftShift) {
779*0fca6ea1SDimitry Andric       R->setHasNoUnsignedWrap(I.hasNoUnsignedWrap() &&
780*0fca6ea1SDimitry Andric                               BO0->hasNoUnsignedWrap());
781*0fca6ea1SDimitry Andric       R->setHasNoSignedWrap(I.hasNoSignedWrap() && BO0->hasNoSignedWrap());
782*0fca6ea1SDimitry Andric     } else
783*0fca6ea1SDimitry Andric       R->setIsExact(I.isExact() && BO0->isExact());
784*0fca6ea1SDimitry Andric     return R;
785*0fca6ea1SDimitry Andric   }
786*0fca6ea1SDimitry Andric 
787bdd1243dSDimitry Andric   Type *Ty = I.getType();
788bdd1243dSDimitry Andric   unsigned TypeBits = Ty->getScalarSizeInBits();
789bdd1243dSDimitry Andric 
790bdd1243dSDimitry Andric   // (X / +DivC) >> (Width - 1) --> ext (X <= -DivC)
791bdd1243dSDimitry Andric   // (X / -DivC) >> (Width - 1) --> ext (X >= +DivC)
792bdd1243dSDimitry Andric   const APInt *DivC;
793*0fca6ea1SDimitry Andric   if (!IsLeftShift && match(C1, m_SpecificIntAllowPoison(TypeBits - 1)) &&
794bdd1243dSDimitry Andric       match(Op0, m_SDiv(m_Value(X), m_APInt(DivC))) && !DivC->isZero() &&
795bdd1243dSDimitry Andric       !DivC->isMinSignedValue()) {
796bdd1243dSDimitry Andric     Constant *NegDivC = ConstantInt::get(Ty, -(*DivC));
797bdd1243dSDimitry Andric     ICmpInst::Predicate Pred =
798bdd1243dSDimitry Andric         DivC->isNegative() ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_SLE;
799bdd1243dSDimitry Andric     Value *Cmp = Builder.CreateICmp(Pred, X, NegDivC);
800bdd1243dSDimitry Andric     auto ExtOpcode = (I.getOpcode() == Instruction::AShr) ? Instruction::SExt
801bdd1243dSDimitry Andric                                                           : Instruction::ZExt;
802bdd1243dSDimitry Andric     return CastInst::Create(ExtOpcode, Cmp, Ty);
803bdd1243dSDimitry Andric   }
804bdd1243dSDimitry Andric 
8050b57cec5SDimitry Andric   const APInt *Op1C;
80681ad6265SDimitry Andric   if (!match(C1, m_APInt(Op1C)))
8070b57cec5SDimitry Andric     return nullptr;
8080b57cec5SDimitry Andric 
809bdd1243dSDimitry Andric   assert(!Op1C->uge(TypeBits) &&
810bdd1243dSDimitry Andric          "Shift over the type width should have been removed already");
811bdd1243dSDimitry Andric 
8120b57cec5SDimitry Andric   // See if we can propagate this shift into the input, this covers the trivial
8130b57cec5SDimitry Andric   // cast of lshr(shl(x,c1),c2) as well as other more complex cases.
8140b57cec5SDimitry Andric   if (I.getOpcode() != Instruction::AShr &&
815349cc55cSDimitry Andric       canEvaluateShifted(Op0, Op1C->getZExtValue(), IsLeftShift, *this, &I)) {
8160b57cec5SDimitry Andric     LLVM_DEBUG(
8170b57cec5SDimitry Andric         dbgs() << "ICE: GetShiftedValue propagating shift through expression"
8180b57cec5SDimitry Andric                   " to eliminate shift:\n  IN: "
8190b57cec5SDimitry Andric                << *Op0 << "\n  SH: " << I << "\n");
8200b57cec5SDimitry Andric 
8210b57cec5SDimitry Andric     return replaceInstUsesWith(
822349cc55cSDimitry Andric         I, getShiftedValue(Op0, Op1C->getZExtValue(), IsLeftShift, *this, DL));
8230b57cec5SDimitry Andric   }
8240b57cec5SDimitry Andric 
8250b57cec5SDimitry Andric   if (Instruction *FoldedShift = foldBinOpIntoSelectOrPhi(I))
8260b57cec5SDimitry Andric     return FoldedShift;
8270b57cec5SDimitry Andric 
828349cc55cSDimitry Andric   if (!Op0->hasOneUse())
829349cc55cSDimitry Andric     return nullptr;
830e8d8bef9SDimitry Andric 
831349cc55cSDimitry Andric   if (auto *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
8320b57cec5SDimitry Andric     // If the operand is a bitwise operator with a constant RHS, and the
8330b57cec5SDimitry Andric     // shift is the only use, we can pull it out of the shift.
8340b57cec5SDimitry Andric     const APInt *Op0C;
8350b57cec5SDimitry Andric     if (match(Op0BO->getOperand(1), m_APInt(Op0C))) {
8360b57cec5SDimitry Andric       if (canShiftBinOpWithConstantRHS(I, Op0BO)) {
83781ad6265SDimitry Andric         Value *NewRHS =
83881ad6265SDimitry Andric             Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(1), C1);
8390b57cec5SDimitry Andric 
8400b57cec5SDimitry Andric         Value *NewShift =
84181ad6265SDimitry Andric             Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), C1);
8420b57cec5SDimitry Andric         NewShift->takeName(Op0BO);
8430b57cec5SDimitry Andric 
844349cc55cSDimitry Andric         return BinaryOperator::Create(Op0BO->getOpcode(), NewShift, NewRHS);
8450b57cec5SDimitry Andric       }
8460b57cec5SDimitry Andric     }
8470b57cec5SDimitry Andric   }
8480b57cec5SDimitry Andric 
8490b57cec5SDimitry Andric   // If we have a select that conditionally executes some binary operator,
8500b57cec5SDimitry Andric   // see if we can pull it the select and operator through the shift.
8510b57cec5SDimitry Andric   //
8520b57cec5SDimitry Andric   // For example, turning:
8530b57cec5SDimitry Andric   //   shl (select C, (add X, C1), X), C2
8540b57cec5SDimitry Andric   // Into:
8550b57cec5SDimitry Andric   //   Y = shl X, C2
8560b57cec5SDimitry Andric   //   select C, (add Y, C1 << C2), Y
8570b57cec5SDimitry Andric   Value *Cond;
8580b57cec5SDimitry Andric   BinaryOperator *TBO;
8590b57cec5SDimitry Andric   Value *FalseVal;
8600b57cec5SDimitry Andric   if (match(Op0, m_Select(m_Value(Cond), m_OneUse(m_BinOp(TBO)),
8610b57cec5SDimitry Andric                           m_Value(FalseVal)))) {
8620b57cec5SDimitry Andric     const APInt *C;
8630b57cec5SDimitry Andric     if (!isa<Constant>(FalseVal) && TBO->getOperand(0) == FalseVal &&
8640b57cec5SDimitry Andric         match(TBO->getOperand(1), m_APInt(C)) &&
8650b57cec5SDimitry Andric         canShiftBinOpWithConstantRHS(I, TBO)) {
86681ad6265SDimitry Andric       Value *NewRHS =
86781ad6265SDimitry Andric           Builder.CreateBinOp(I.getOpcode(), TBO->getOperand(1), C1);
8680b57cec5SDimitry Andric 
86981ad6265SDimitry Andric       Value *NewShift = Builder.CreateBinOp(I.getOpcode(), FalseVal, C1);
870349cc55cSDimitry Andric       Value *NewOp = Builder.CreateBinOp(TBO->getOpcode(), NewShift, NewRHS);
8710b57cec5SDimitry Andric       return SelectInst::Create(Cond, NewOp, NewShift);
8720b57cec5SDimitry Andric     }
8730b57cec5SDimitry Andric   }
8740b57cec5SDimitry Andric 
8750b57cec5SDimitry Andric   BinaryOperator *FBO;
8760b57cec5SDimitry Andric   Value *TrueVal;
8770b57cec5SDimitry Andric   if (match(Op0, m_Select(m_Value(Cond), m_Value(TrueVal),
8780b57cec5SDimitry Andric                           m_OneUse(m_BinOp(FBO))))) {
8790b57cec5SDimitry Andric     const APInt *C;
8800b57cec5SDimitry Andric     if (!isa<Constant>(TrueVal) && FBO->getOperand(0) == TrueVal &&
8810b57cec5SDimitry Andric         match(FBO->getOperand(1), m_APInt(C)) &&
8820b57cec5SDimitry Andric         canShiftBinOpWithConstantRHS(I, FBO)) {
88381ad6265SDimitry Andric       Value *NewRHS =
88481ad6265SDimitry Andric           Builder.CreateBinOp(I.getOpcode(), FBO->getOperand(1), C1);
8850b57cec5SDimitry Andric 
88681ad6265SDimitry Andric       Value *NewShift = Builder.CreateBinOp(I.getOpcode(), TrueVal, C1);
887349cc55cSDimitry Andric       Value *NewOp = Builder.CreateBinOp(FBO->getOpcode(), NewShift, NewRHS);
8880b57cec5SDimitry Andric       return SelectInst::Create(Cond, NewShift, NewOp);
8890b57cec5SDimitry Andric     }
8900b57cec5SDimitry Andric   }
8910b57cec5SDimitry Andric 
8920b57cec5SDimitry Andric   return nullptr;
8930b57cec5SDimitry Andric }
8940b57cec5SDimitry Andric 
895bdd1243dSDimitry Andric // Tries to perform
896bdd1243dSDimitry Andric //    (lshr (add (zext X), (zext Y)), K)
897bdd1243dSDimitry Andric //      -> (icmp ult (add X, Y), X)
898bdd1243dSDimitry Andric //    where
899bdd1243dSDimitry Andric //      - The add's operands are zexts from a K-bits integer to a bigger type.
900bdd1243dSDimitry Andric //      - The add is only used by the shr, or by iK (or narrower) truncates.
901bdd1243dSDimitry Andric //      - The lshr type has more than 2 bits (other types are boolean math).
902bdd1243dSDimitry Andric //      - K > 1
903bdd1243dSDimitry Andric //    note that
904bdd1243dSDimitry Andric //      - The resulting add cannot have nuw/nsw, else on overflow we get a
905bdd1243dSDimitry Andric //        poison value and the transform isn't legal anymore.
906bdd1243dSDimitry Andric Instruction *InstCombinerImpl::foldLShrOverflowBit(BinaryOperator &I) {
907bdd1243dSDimitry Andric   assert(I.getOpcode() == Instruction::LShr);
908bdd1243dSDimitry Andric 
909bdd1243dSDimitry Andric   Value *Add = I.getOperand(0);
910bdd1243dSDimitry Andric   Value *ShiftAmt = I.getOperand(1);
911bdd1243dSDimitry Andric   Type *Ty = I.getType();
912bdd1243dSDimitry Andric 
913bdd1243dSDimitry Andric   if (Ty->getScalarSizeInBits() < 3)
914bdd1243dSDimitry Andric     return nullptr;
915bdd1243dSDimitry Andric 
916bdd1243dSDimitry Andric   const APInt *ShAmtAPInt = nullptr;
917bdd1243dSDimitry Andric   Value *X = nullptr, *Y = nullptr;
918bdd1243dSDimitry Andric   if (!match(ShiftAmt, m_APInt(ShAmtAPInt)) ||
919bdd1243dSDimitry Andric       !match(Add,
920bdd1243dSDimitry Andric              m_Add(m_OneUse(m_ZExt(m_Value(X))), m_OneUse(m_ZExt(m_Value(Y))))))
921bdd1243dSDimitry Andric     return nullptr;
922bdd1243dSDimitry Andric 
923bdd1243dSDimitry Andric   const unsigned ShAmt = ShAmtAPInt->getZExtValue();
924bdd1243dSDimitry Andric   if (ShAmt == 1)
925bdd1243dSDimitry Andric     return nullptr;
926bdd1243dSDimitry Andric 
927bdd1243dSDimitry Andric   // X/Y are zexts from `ShAmt`-sized ints.
928bdd1243dSDimitry Andric   if (X->getType()->getScalarSizeInBits() != ShAmt ||
929bdd1243dSDimitry Andric       Y->getType()->getScalarSizeInBits() != ShAmt)
930bdd1243dSDimitry Andric     return nullptr;
931bdd1243dSDimitry Andric 
932bdd1243dSDimitry Andric   // Make sure that `Add` is only used by `I` and `ShAmt`-truncates.
933bdd1243dSDimitry Andric   if (!Add->hasOneUse()) {
934bdd1243dSDimitry Andric     for (User *U : Add->users()) {
935bdd1243dSDimitry Andric       if (U == &I)
936bdd1243dSDimitry Andric         continue;
937bdd1243dSDimitry Andric 
938bdd1243dSDimitry Andric       TruncInst *Trunc = dyn_cast<TruncInst>(U);
939bdd1243dSDimitry Andric       if (!Trunc || Trunc->getType()->getScalarSizeInBits() > ShAmt)
940bdd1243dSDimitry Andric         return nullptr;
941bdd1243dSDimitry Andric     }
942bdd1243dSDimitry Andric   }
943bdd1243dSDimitry Andric 
944bdd1243dSDimitry Andric   // Insert at Add so that the newly created `NarrowAdd` will dominate it's
945bdd1243dSDimitry Andric   // users (i.e. `Add`'s users).
946bdd1243dSDimitry Andric   Instruction *AddInst = cast<Instruction>(Add);
947bdd1243dSDimitry Andric   Builder.SetInsertPoint(AddInst);
948bdd1243dSDimitry Andric 
949bdd1243dSDimitry Andric   Value *NarrowAdd = Builder.CreateAdd(X, Y, "add.narrowed");
950bdd1243dSDimitry Andric   Value *Overflow =
951bdd1243dSDimitry Andric       Builder.CreateICmpULT(NarrowAdd, X, "add.narrowed.overflow");
952bdd1243dSDimitry Andric 
953bdd1243dSDimitry Andric   // Replace the uses of the original add with a zext of the
954bdd1243dSDimitry Andric   // NarrowAdd's result. Note that all users at this stage are known to
955bdd1243dSDimitry Andric   // be ShAmt-sized truncs, or the lshr itself.
95606c3fb27SDimitry Andric   if (!Add->hasOneUse()) {
957bdd1243dSDimitry Andric     replaceInstUsesWith(*AddInst, Builder.CreateZExt(NarrowAdd, Ty));
95806c3fb27SDimitry Andric     eraseInstFromFunction(*AddInst);
95906c3fb27SDimitry Andric   }
960bdd1243dSDimitry Andric 
961bdd1243dSDimitry Andric   // Replace the LShr with a zext of the overflow check.
962bdd1243dSDimitry Andric   return new ZExtInst(Overflow, Ty);
963bdd1243dSDimitry Andric }
964bdd1243dSDimitry Andric 
9655f757f3fSDimitry Andric // Try to set nuw/nsw flags on shl or exact flag on lshr/ashr using knownbits.
9665f757f3fSDimitry Andric static bool setShiftFlags(BinaryOperator &I, const SimplifyQuery &Q) {
9675f757f3fSDimitry Andric   assert(I.isShift() && "Expected a shift as input");
9685f757f3fSDimitry Andric   // We already have all the flags.
9695f757f3fSDimitry Andric   if (I.getOpcode() == Instruction::Shl) {
9705f757f3fSDimitry Andric     if (I.hasNoUnsignedWrap() && I.hasNoSignedWrap())
9715f757f3fSDimitry Andric       return false;
9725f757f3fSDimitry Andric   } else {
9735f757f3fSDimitry Andric     if (I.isExact())
9745f757f3fSDimitry Andric       return false;
9755f757f3fSDimitry Andric 
9765f757f3fSDimitry Andric     // shr (shl X, Y), Y
9775f757f3fSDimitry Andric     if (match(I.getOperand(0), m_Shl(m_Value(), m_Specific(I.getOperand(1))))) {
9785f757f3fSDimitry Andric       I.setIsExact();
9795f757f3fSDimitry Andric       return true;
9805f757f3fSDimitry Andric     }
9815f757f3fSDimitry Andric   }
9825f757f3fSDimitry Andric 
9835f757f3fSDimitry Andric   // Compute what we know about shift count.
9845f757f3fSDimitry Andric   KnownBits KnownCnt = computeKnownBits(I.getOperand(1), /* Depth */ 0, Q);
9855f757f3fSDimitry Andric   unsigned BitWidth = KnownCnt.getBitWidth();
9865f757f3fSDimitry Andric   // Since shift produces a poison value if RHS is equal to or larger than the
9875f757f3fSDimitry Andric   // bit width, we can safely assume that RHS is less than the bit width.
9885f757f3fSDimitry Andric   uint64_t MaxCnt = KnownCnt.getMaxValue().getLimitedValue(BitWidth - 1);
9895f757f3fSDimitry Andric 
9905f757f3fSDimitry Andric   KnownBits KnownAmt = computeKnownBits(I.getOperand(0), /* Depth */ 0, Q);
9915f757f3fSDimitry Andric   bool Changed = false;
9925f757f3fSDimitry Andric 
9935f757f3fSDimitry Andric   if (I.getOpcode() == Instruction::Shl) {
9945f757f3fSDimitry Andric     // If we have as many leading zeros than maximum shift cnt we have nuw.
9955f757f3fSDimitry Andric     if (!I.hasNoUnsignedWrap() && MaxCnt <= KnownAmt.countMinLeadingZeros()) {
9965f757f3fSDimitry Andric       I.setHasNoUnsignedWrap();
9975f757f3fSDimitry Andric       Changed = true;
9985f757f3fSDimitry Andric     }
9995f757f3fSDimitry Andric     // If we have more sign bits than maximum shift cnt we have nsw.
10005f757f3fSDimitry Andric     if (!I.hasNoSignedWrap()) {
10015f757f3fSDimitry Andric       if (MaxCnt < KnownAmt.countMinSignBits() ||
10025f757f3fSDimitry Andric           MaxCnt < ComputeNumSignBits(I.getOperand(0), Q.DL, /*Depth*/ 0, Q.AC,
10035f757f3fSDimitry Andric                                       Q.CxtI, Q.DT)) {
10045f757f3fSDimitry Andric         I.setHasNoSignedWrap();
10055f757f3fSDimitry Andric         Changed = true;
10065f757f3fSDimitry Andric       }
10075f757f3fSDimitry Andric     }
10085f757f3fSDimitry Andric     return Changed;
10095f757f3fSDimitry Andric   }
10105f757f3fSDimitry Andric 
10115f757f3fSDimitry Andric   // If we have at least as many trailing zeros as maximum count then we have
10125f757f3fSDimitry Andric   // exact.
10135f757f3fSDimitry Andric   Changed = MaxCnt <= KnownAmt.countMinTrailingZeros();
10145f757f3fSDimitry Andric   I.setIsExact(Changed);
10155f757f3fSDimitry Andric 
10165f757f3fSDimitry Andric   return Changed;
10175f757f3fSDimitry Andric }
10185f757f3fSDimitry Andric 
1019e8d8bef9SDimitry Andric Instruction *InstCombinerImpl::visitShl(BinaryOperator &I) {
10208bcb0991SDimitry Andric   const SimplifyQuery Q = SQ.getWithInstruction(&I);
10218bcb0991SDimitry Andric 
102281ad6265SDimitry Andric   if (Value *V = simplifyShlInst(I.getOperand(0), I.getOperand(1),
10238bcb0991SDimitry Andric                                  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(), Q))
10240b57cec5SDimitry Andric     return replaceInstUsesWith(I, V);
10250b57cec5SDimitry Andric 
10260b57cec5SDimitry Andric   if (Instruction *X = foldVectorBinop(I))
10270b57cec5SDimitry Andric     return X;
10280b57cec5SDimitry Andric 
10290b57cec5SDimitry Andric   if (Instruction *V = commonShiftTransforms(I))
10300b57cec5SDimitry Andric     return V;
10310b57cec5SDimitry Andric 
10328bcb0991SDimitry Andric   if (Instruction *V = dropRedundantMaskingOfLeftShiftInput(&I, Q, Builder))
10338bcb0991SDimitry Andric     return V;
10348bcb0991SDimitry Andric 
10350b57cec5SDimitry Andric   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
10360b57cec5SDimitry Andric   Type *Ty = I.getType();
10370b57cec5SDimitry Andric   unsigned BitWidth = Ty->getScalarSizeInBits();
10380b57cec5SDimitry Andric 
1039349cc55cSDimitry Andric   const APInt *C;
1040349cc55cSDimitry Andric   if (match(Op1, m_APInt(C))) {
1041349cc55cSDimitry Andric     unsigned ShAmtC = C->getZExtValue();
10420b57cec5SDimitry Andric 
1043349cc55cSDimitry Andric     // shl (zext X), C --> zext (shl X, C)
10440b57cec5SDimitry Andric     // This is only valid if X would have zeros shifted out.
10450b57cec5SDimitry Andric     Value *X;
10468bcb0991SDimitry Andric     if (match(Op0, m_OneUse(m_ZExt(m_Value(X))))) {
10470b57cec5SDimitry Andric       unsigned SrcWidth = X->getType()->getScalarSizeInBits();
1048349cc55cSDimitry Andric       if (ShAmtC < SrcWidth &&
1049349cc55cSDimitry Andric           MaskedValueIsZero(X, APInt::getHighBitsSet(SrcWidth, ShAmtC), 0, &I))
1050349cc55cSDimitry Andric         return new ZExtInst(Builder.CreateShl(X, ShAmtC), Ty);
10510b57cec5SDimitry Andric     }
10520b57cec5SDimitry Andric 
10530b57cec5SDimitry Andric     // (X >> C) << C --> X & (-1 << C)
10540b57cec5SDimitry Andric     if (match(Op0, m_Shr(m_Value(X), m_Specific(Op1)))) {
1055349cc55cSDimitry Andric       APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));
10560b57cec5SDimitry Andric       return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));
10570b57cec5SDimitry Andric     }
10580b57cec5SDimitry Andric 
1059349cc55cSDimitry Andric     const APInt *C1;
1060349cc55cSDimitry Andric     if (match(Op0, m_Exact(m_Shr(m_Value(X), m_APInt(C1)))) &&
1061349cc55cSDimitry Andric         C1->ult(BitWidth)) {
1062349cc55cSDimitry Andric       unsigned ShrAmt = C1->getZExtValue();
1063349cc55cSDimitry Andric       if (ShrAmt < ShAmtC) {
1064349cc55cSDimitry Andric         // If C1 < C: (X >>?,exact C1) << C --> X << (C - C1)
1065349cc55cSDimitry Andric         Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt);
10660b57cec5SDimitry Andric         auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
10675f757f3fSDimitry Andric         NewShl->setHasNoUnsignedWrap(
10685f757f3fSDimitry Andric             I.hasNoUnsignedWrap() ||
10695f757f3fSDimitry Andric             (ShrAmt &&
10705f757f3fSDimitry Andric              cast<Instruction>(Op0)->getOpcode() == Instruction::LShr &&
10715f757f3fSDimitry Andric              I.hasNoSignedWrap()));
10720b57cec5SDimitry Andric         NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
10730b57cec5SDimitry Andric         return NewShl;
10740b57cec5SDimitry Andric       }
1075349cc55cSDimitry Andric       if (ShrAmt > ShAmtC) {
1076349cc55cSDimitry Andric         // If C1 > C: (X >>?exact C1) << C --> X >>?exact (C1 - C)
1077349cc55cSDimitry Andric         Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC);
10780b57cec5SDimitry Andric         auto *NewShr = BinaryOperator::Create(
10790b57cec5SDimitry Andric             cast<BinaryOperator>(Op0)->getOpcode(), X, ShiftDiff);
10800b57cec5SDimitry Andric         NewShr->setIsExact(true);
10810b57cec5SDimitry Andric         return NewShr;
10820b57cec5SDimitry Andric       }
10830b57cec5SDimitry Andric     }
10840b57cec5SDimitry Andric 
1085349cc55cSDimitry Andric     if (match(Op0, m_OneUse(m_Shr(m_Value(X), m_APInt(C1)))) &&
1086349cc55cSDimitry Andric         C1->ult(BitWidth)) {
1087349cc55cSDimitry Andric       unsigned ShrAmt = C1->getZExtValue();
1088349cc55cSDimitry Andric       if (ShrAmt < ShAmtC) {
1089349cc55cSDimitry Andric         // If C1 < C: (X >>? C1) << C --> (X << (C - C1)) & (-1 << C)
1090349cc55cSDimitry Andric         Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt);
1091e8d8bef9SDimitry Andric         auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
10925f757f3fSDimitry Andric         NewShl->setHasNoUnsignedWrap(
10935f757f3fSDimitry Andric             I.hasNoUnsignedWrap() ||
10945f757f3fSDimitry Andric             (ShrAmt &&
10955f757f3fSDimitry Andric              cast<Instruction>(Op0)->getOpcode() == Instruction::LShr &&
10965f757f3fSDimitry Andric              I.hasNoSignedWrap()));
1097e8d8bef9SDimitry Andric         NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
1098e8d8bef9SDimitry Andric         Builder.Insert(NewShl);
1099349cc55cSDimitry Andric         APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));
1100e8d8bef9SDimitry Andric         return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask));
1101e8d8bef9SDimitry Andric       }
1102349cc55cSDimitry Andric       if (ShrAmt > ShAmtC) {
1103349cc55cSDimitry Andric         // If C1 > C: (X >>? C1) << C --> (X >>? (C1 - C)) & (-1 << C)
1104349cc55cSDimitry Andric         Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC);
1105e8d8bef9SDimitry Andric         auto *OldShr = cast<BinaryOperator>(Op0);
1106e8d8bef9SDimitry Andric         auto *NewShr =
1107e8d8bef9SDimitry Andric             BinaryOperator::Create(OldShr->getOpcode(), X, ShiftDiff);
1108e8d8bef9SDimitry Andric         NewShr->setIsExact(OldShr->isExact());
1109e8d8bef9SDimitry Andric         Builder.Insert(NewShr);
1110349cc55cSDimitry Andric         APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));
1111e8d8bef9SDimitry Andric         return BinaryOperator::CreateAnd(NewShr, ConstantInt::get(Ty, Mask));
1112e8d8bef9SDimitry Andric       }
1113e8d8bef9SDimitry Andric     }
1114e8d8bef9SDimitry Andric 
1115349cc55cSDimitry Andric     // Similar to above, but look through an intermediate trunc instruction.
1116349cc55cSDimitry Andric     BinaryOperator *Shr;
1117349cc55cSDimitry Andric     if (match(Op0, m_OneUse(m_Trunc(m_OneUse(m_BinOp(Shr))))) &&
1118349cc55cSDimitry Andric         match(Shr, m_Shr(m_Value(X), m_APInt(C1)))) {
1119349cc55cSDimitry Andric       // The larger shift direction survives through the transform.
1120349cc55cSDimitry Andric       unsigned ShrAmtC = C1->getZExtValue();
1121349cc55cSDimitry Andric       unsigned ShDiff = ShrAmtC > ShAmtC ? ShrAmtC - ShAmtC : ShAmtC - ShrAmtC;
1122349cc55cSDimitry Andric       Constant *ShiftDiffC = ConstantInt::get(X->getType(), ShDiff);
1123349cc55cSDimitry Andric       auto ShiftOpc = ShrAmtC > ShAmtC ? Shr->getOpcode() : Instruction::Shl;
1124349cc55cSDimitry Andric 
1125349cc55cSDimitry Andric       // If C1 > C:
1126349cc55cSDimitry Andric       // (trunc (X >> C1)) << C --> (trunc (X >> (C1 - C))) && (-1 << C)
1127349cc55cSDimitry Andric       // If C > C1:
1128349cc55cSDimitry Andric       // (trunc (X >> C1)) << C --> (trunc (X << (C - C1))) && (-1 << C)
1129349cc55cSDimitry Andric       Value *NewShift = Builder.CreateBinOp(ShiftOpc, X, ShiftDiffC, "sh.diff");
1130349cc55cSDimitry Andric       Value *Trunc = Builder.CreateTrunc(NewShift, Ty, "tr.sh.diff");
1131349cc55cSDimitry Andric       APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));
1132349cc55cSDimitry Andric       return BinaryOperator::CreateAnd(Trunc, ConstantInt::get(Ty, Mask));
1133349cc55cSDimitry Andric     }
1134349cc55cSDimitry Andric 
1135349cc55cSDimitry Andric     // If we have an opposite shift by the same amount, we may be able to
1136349cc55cSDimitry Andric     // reorder binops and shifts to eliminate math/logic.
1137349cc55cSDimitry Andric     auto isSuitableBinOpcode = [](Instruction::BinaryOps BinOpcode) {
1138349cc55cSDimitry Andric       switch (BinOpcode) {
1139349cc55cSDimitry Andric       default:
1140349cc55cSDimitry Andric         return false;
1141349cc55cSDimitry Andric       case Instruction::Add:
1142349cc55cSDimitry Andric       case Instruction::And:
1143349cc55cSDimitry Andric       case Instruction::Or:
1144349cc55cSDimitry Andric       case Instruction::Xor:
1145349cc55cSDimitry Andric       case Instruction::Sub:
1146349cc55cSDimitry Andric         // NOTE: Sub is not commutable and the tranforms below may not be valid
1147349cc55cSDimitry Andric         //       when the shift-right is operand 1 (RHS) of the sub.
1148349cc55cSDimitry Andric         return true;
1149349cc55cSDimitry Andric       }
1150349cc55cSDimitry Andric     };
1151349cc55cSDimitry Andric     BinaryOperator *Op0BO;
1152349cc55cSDimitry Andric     if (match(Op0, m_OneUse(m_BinOp(Op0BO))) &&
1153349cc55cSDimitry Andric         isSuitableBinOpcode(Op0BO->getOpcode())) {
1154349cc55cSDimitry Andric       // Commute so shift-right is on LHS of the binop.
1155349cc55cSDimitry Andric       // (Y bop (X >> C)) << C         ->  ((X >> C) bop Y) << C
1156349cc55cSDimitry Andric       // (Y bop ((X >> C) & CC)) << C  ->  (((X >> C) & CC) bop Y) << C
1157349cc55cSDimitry Andric       Value *Shr = Op0BO->getOperand(0);
1158349cc55cSDimitry Andric       Value *Y = Op0BO->getOperand(1);
1159349cc55cSDimitry Andric       Value *X;
1160349cc55cSDimitry Andric       const APInt *CC;
1161349cc55cSDimitry Andric       if (Op0BO->isCommutative() && Y->hasOneUse() &&
1162349cc55cSDimitry Andric           (match(Y, m_Shr(m_Value(), m_Specific(Op1))) ||
1163349cc55cSDimitry Andric            match(Y, m_And(m_OneUse(m_Shr(m_Value(), m_Specific(Op1))),
1164349cc55cSDimitry Andric                           m_APInt(CC)))))
1165349cc55cSDimitry Andric         std::swap(Shr, Y);
1166349cc55cSDimitry Andric 
1167349cc55cSDimitry Andric       // ((X >> C) bop Y) << C  ->  (X bop (Y << C)) & (~0 << C)
1168349cc55cSDimitry Andric       if (match(Shr, m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))))) {
1169349cc55cSDimitry Andric         // Y << C
1170349cc55cSDimitry Andric         Value *YS = Builder.CreateShl(Y, Op1, Op0BO->getName());
1171349cc55cSDimitry Andric         // (X bop (Y << C))
1172349cc55cSDimitry Andric         Value *B =
1173349cc55cSDimitry Andric             Builder.CreateBinOp(Op0BO->getOpcode(), X, YS, Shr->getName());
1174349cc55cSDimitry Andric         unsigned Op1Val = C->getLimitedValue(BitWidth);
1175349cc55cSDimitry Andric         APInt Bits = APInt::getHighBitsSet(BitWidth, BitWidth - Op1Val);
1176349cc55cSDimitry Andric         Constant *Mask = ConstantInt::get(Ty, Bits);
1177349cc55cSDimitry Andric         return BinaryOperator::CreateAnd(B, Mask);
1178349cc55cSDimitry Andric       }
1179349cc55cSDimitry Andric 
1180349cc55cSDimitry Andric       // (((X >> C) & CC) bop Y) << C  ->  (X & (CC << C)) bop (Y << C)
1181349cc55cSDimitry Andric       if (match(Shr,
1182349cc55cSDimitry Andric                 m_OneUse(m_And(m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))),
1183349cc55cSDimitry Andric                                m_APInt(CC))))) {
1184349cc55cSDimitry Andric         // Y << C
1185349cc55cSDimitry Andric         Value *YS = Builder.CreateShl(Y, Op1, Op0BO->getName());
1186349cc55cSDimitry Andric         // X & (CC << C)
1187349cc55cSDimitry Andric         Value *M = Builder.CreateAnd(X, ConstantInt::get(Ty, CC->shl(*C)),
1188349cc55cSDimitry Andric                                      X->getName() + ".mask");
1189*0fca6ea1SDimitry Andric         auto *NewOp = BinaryOperator::Create(Op0BO->getOpcode(), M, YS);
1190*0fca6ea1SDimitry Andric         if (auto *Disjoint = dyn_cast<PossiblyDisjointInst>(Op0BO);
1191*0fca6ea1SDimitry Andric             Disjoint && Disjoint->isDisjoint())
1192*0fca6ea1SDimitry Andric           cast<PossiblyDisjointInst>(NewOp)->setIsDisjoint(true);
1193*0fca6ea1SDimitry Andric         return NewOp;
1194349cc55cSDimitry Andric       }
1195349cc55cSDimitry Andric     }
1196349cc55cSDimitry Andric 
1197349cc55cSDimitry Andric     // (C1 - X) << C --> (C1 << C) - (X << C)
1198349cc55cSDimitry Andric     if (match(Op0, m_OneUse(m_Sub(m_APInt(C1), m_Value(X))))) {
1199349cc55cSDimitry Andric       Constant *NewLHS = ConstantInt::get(Ty, C1->shl(*C));
1200349cc55cSDimitry Andric       Value *NewShift = Builder.CreateShl(X, Op1);
1201349cc55cSDimitry Andric       return BinaryOperator::CreateSub(NewLHS, NewShift);
1202349cc55cSDimitry Andric     }
12030b57cec5SDimitry Andric   }
12040b57cec5SDimitry Andric 
12055f757f3fSDimitry Andric   if (setShiftFlags(I, Q))
12060b57cec5SDimitry Andric     return &I;
12070b57cec5SDimitry Andric 
12080b57cec5SDimitry Andric   // Transform  (x >> y) << y  to  x & (-1 << y)
12090b57cec5SDimitry Andric   // Valid for any type of right-shift.
12100b57cec5SDimitry Andric   Value *X;
12110b57cec5SDimitry Andric   if (match(Op0, m_OneUse(m_Shr(m_Value(X), m_Specific(Op1))))) {
12120b57cec5SDimitry Andric     Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
12130b57cec5SDimitry Andric     Value *Mask = Builder.CreateShl(AllOnes, Op1);
12140b57cec5SDimitry Andric     return BinaryOperator::CreateAnd(Mask, X);
12150b57cec5SDimitry Andric   }
12160b57cec5SDimitry Andric 
1217*0fca6ea1SDimitry Andric   // Transform  (-1 >> y) << y  to -1 << y
1218*0fca6ea1SDimitry Andric   if (match(Op0, m_LShr(m_AllOnes(), m_Specific(Op1)))) {
1219*0fca6ea1SDimitry Andric     Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
1220*0fca6ea1SDimitry Andric     return BinaryOperator::CreateShl(AllOnes, Op1);
1221*0fca6ea1SDimitry Andric   }
1222*0fca6ea1SDimitry Andric 
12230b57cec5SDimitry Andric   Constant *C1;
1224*0fca6ea1SDimitry Andric   if (match(Op1, m_ImmConstant(C1))) {
12250b57cec5SDimitry Andric     Constant *C2;
12260b57cec5SDimitry Andric     Value *X;
12270b57cec5SDimitry Andric     // (X * C2) << C1 --> X * (C2 << C1)
1228*0fca6ea1SDimitry Andric     if (match(Op0, m_Mul(m_Value(X), m_ImmConstant(C2))))
1229*0fca6ea1SDimitry Andric       return BinaryOperator::CreateMul(X, Builder.CreateShl(C2, C1));
12308bcb0991SDimitry Andric 
12318bcb0991SDimitry Andric     // shl (zext i1 X), C1 --> select (X, 1 << C1, 0)
12328bcb0991SDimitry Andric     if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1233*0fca6ea1SDimitry Andric       auto *NewC = Builder.CreateShl(ConstantInt::get(Ty, 1), C1);
12348bcb0991SDimitry Andric       return SelectInst::Create(X, NewC, ConstantInt::getNullValue(Ty));
12358bcb0991SDimitry Andric     }
12360b57cec5SDimitry Andric   }
12370b57cec5SDimitry Andric 
1238bdd1243dSDimitry Andric   if (match(Op0, m_One())) {
12390b57cec5SDimitry Andric     // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1
1240bdd1243dSDimitry Andric     if (match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X))))
12410b57cec5SDimitry Andric       return BinaryOperator::CreateLShr(
12420b57cec5SDimitry Andric           ConstantInt::get(Ty, APInt::getSignMask(BitWidth)), X);
12430b57cec5SDimitry Andric 
124406c3fb27SDimitry Andric     // Canonicalize "extract lowest set bit" using cttz to and-with-negate:
124506c3fb27SDimitry Andric     // 1 << (cttz X) --> -X & X
124606c3fb27SDimitry Andric     if (match(Op1,
124706c3fb27SDimitry Andric               m_OneUse(m_Intrinsic<Intrinsic::cttz>(m_Value(X), m_Value())))) {
124806c3fb27SDimitry Andric       Value *NegX = Builder.CreateNeg(X, "neg");
124906c3fb27SDimitry Andric       return BinaryOperator::CreateAnd(NegX, X);
125006c3fb27SDimitry Andric     }
1251bdd1243dSDimitry Andric   }
1252bdd1243dSDimitry Andric 
12530b57cec5SDimitry Andric   return nullptr;
12540b57cec5SDimitry Andric }
12550b57cec5SDimitry Andric 
1256e8d8bef9SDimitry Andric Instruction *InstCombinerImpl::visitLShr(BinaryOperator &I) {
125781ad6265SDimitry Andric   if (Value *V = simplifyLShrInst(I.getOperand(0), I.getOperand(1), I.isExact(),
12580b57cec5SDimitry Andric                                   SQ.getWithInstruction(&I)))
12590b57cec5SDimitry Andric     return replaceInstUsesWith(I, V);
12600b57cec5SDimitry Andric 
12610b57cec5SDimitry Andric   if (Instruction *X = foldVectorBinop(I))
12620b57cec5SDimitry Andric     return X;
12630b57cec5SDimitry Andric 
12640b57cec5SDimitry Andric   if (Instruction *R = commonShiftTransforms(I))
12650b57cec5SDimitry Andric     return R;
12660b57cec5SDimitry Andric 
12670b57cec5SDimitry Andric   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
12680b57cec5SDimitry Andric   Type *Ty = I.getType();
1269bdd1243dSDimitry Andric   Value *X;
1270349cc55cSDimitry Andric   const APInt *C;
1271bdd1243dSDimitry Andric   unsigned BitWidth = Ty->getScalarSizeInBits();
1272bdd1243dSDimitry Andric 
1273bdd1243dSDimitry Andric   // (iN (~X) u>> (N - 1)) --> zext (X > -1)
1274bdd1243dSDimitry Andric   if (match(Op0, m_OneUse(m_Not(m_Value(X)))) &&
1275*0fca6ea1SDimitry Andric       match(Op1, m_SpecificIntAllowPoison(BitWidth - 1)))
1276bdd1243dSDimitry Andric     return new ZExtInst(Builder.CreateIsNotNeg(X, "isnotneg"), Ty);
1277bdd1243dSDimitry Andric 
1278*0fca6ea1SDimitry Andric   // ((X << nuw Z) sub nuw Y) >>u exact Z --> X sub nuw (Y >>u exact Z)
1279*0fca6ea1SDimitry Andric   Value *Y;
1280*0fca6ea1SDimitry Andric   if (I.isExact() &&
1281*0fca6ea1SDimitry Andric       match(Op0, m_OneUse(m_NUWSub(m_NUWShl(m_Value(X), m_Specific(Op1)),
1282*0fca6ea1SDimitry Andric                                    m_Value(Y))))) {
1283*0fca6ea1SDimitry Andric     Value *NewLshr = Builder.CreateLShr(Y, Op1, "", /*isExact=*/true);
1284*0fca6ea1SDimitry Andric     auto *NewSub = BinaryOperator::CreateNUWSub(X, NewLshr);
1285*0fca6ea1SDimitry Andric     NewSub->setHasNoSignedWrap(
1286*0fca6ea1SDimitry Andric         cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap());
1287*0fca6ea1SDimitry Andric     return NewSub;
1288*0fca6ea1SDimitry Andric   }
1289*0fca6ea1SDimitry Andric 
1290*0fca6ea1SDimitry Andric   // Fold (X + Y) / 2 --> (X & Y) iff (X u<= 1) && (Y u<= 1)
1291*0fca6ea1SDimitry Andric   if (match(Op0, m_Add(m_Value(X), m_Value(Y))) && match(Op1, m_One()) &&
1292*0fca6ea1SDimitry Andric       computeKnownBits(X, /*Depth=*/0, &I).countMaxActiveBits() <= 1 &&
1293*0fca6ea1SDimitry Andric       computeKnownBits(Y, /*Depth=*/0, &I).countMaxActiveBits() <= 1)
1294*0fca6ea1SDimitry Andric     return BinaryOperator::CreateAnd(X, Y);
1295*0fca6ea1SDimitry Andric 
1296*0fca6ea1SDimitry Andric   // (sub nuw X, (Y << nuw Z)) >>u exact Z --> (X >>u exact Z) sub nuw Y
1297*0fca6ea1SDimitry Andric   if (I.isExact() &&
1298*0fca6ea1SDimitry Andric       match(Op0, m_OneUse(m_NUWSub(m_Value(X),
1299*0fca6ea1SDimitry Andric                                    m_NUWShl(m_Value(Y), m_Specific(Op1)))))) {
1300*0fca6ea1SDimitry Andric     Value *NewLshr = Builder.CreateLShr(X, Op1, "", /*isExact=*/true);
1301*0fca6ea1SDimitry Andric     auto *NewSub = BinaryOperator::CreateNUWSub(NewLshr, Y);
1302*0fca6ea1SDimitry Andric     NewSub->setHasNoSignedWrap(
1303*0fca6ea1SDimitry Andric         cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap());
1304*0fca6ea1SDimitry Andric     return NewSub;
1305*0fca6ea1SDimitry Andric   }
1306*0fca6ea1SDimitry Andric 
1307*0fca6ea1SDimitry Andric   auto isSuitableBinOpcode = [](Instruction::BinaryOps BinOpcode) {
1308*0fca6ea1SDimitry Andric     switch (BinOpcode) {
1309*0fca6ea1SDimitry Andric     default:
1310*0fca6ea1SDimitry Andric       return false;
1311*0fca6ea1SDimitry Andric     case Instruction::Add:
1312*0fca6ea1SDimitry Andric     case Instruction::And:
1313*0fca6ea1SDimitry Andric     case Instruction::Or:
1314*0fca6ea1SDimitry Andric     case Instruction::Xor:
1315*0fca6ea1SDimitry Andric       // Sub is handled separately.
1316*0fca6ea1SDimitry Andric       return true;
1317*0fca6ea1SDimitry Andric     }
1318*0fca6ea1SDimitry Andric   };
1319*0fca6ea1SDimitry Andric 
1320*0fca6ea1SDimitry Andric   // If both the binop and the shift are nuw, then:
1321*0fca6ea1SDimitry Andric   // ((X << nuw Z) binop nuw Y) >>u Z --> X binop nuw (Y >>u Z)
1322*0fca6ea1SDimitry Andric   if (match(Op0, m_OneUse(m_c_BinOp(m_NUWShl(m_Value(X), m_Specific(Op1)),
1323*0fca6ea1SDimitry Andric                                     m_Value(Y))))) {
1324*0fca6ea1SDimitry Andric     BinaryOperator *Op0OB = cast<BinaryOperator>(Op0);
1325*0fca6ea1SDimitry Andric     if (isSuitableBinOpcode(Op0OB->getOpcode())) {
1326*0fca6ea1SDimitry Andric       if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(Op0);
1327*0fca6ea1SDimitry Andric           !OBO || OBO->hasNoUnsignedWrap()) {
1328*0fca6ea1SDimitry Andric         Value *NewLshr = Builder.CreateLShr(
1329*0fca6ea1SDimitry Andric             Y, Op1, "", I.isExact() && Op0OB->getOpcode() != Instruction::And);
1330*0fca6ea1SDimitry Andric         auto *NewBinOp = BinaryOperator::Create(Op0OB->getOpcode(), NewLshr, X);
1331*0fca6ea1SDimitry Andric         if (OBO) {
1332*0fca6ea1SDimitry Andric           NewBinOp->setHasNoUnsignedWrap(true);
1333*0fca6ea1SDimitry Andric           NewBinOp->setHasNoSignedWrap(OBO->hasNoSignedWrap());
1334*0fca6ea1SDimitry Andric         } else if (auto *Disjoint = dyn_cast<PossiblyDisjointInst>(Op0)) {
1335*0fca6ea1SDimitry Andric           cast<PossiblyDisjointInst>(NewBinOp)->setIsDisjoint(
1336*0fca6ea1SDimitry Andric               Disjoint->isDisjoint());
1337*0fca6ea1SDimitry Andric         }
1338*0fca6ea1SDimitry Andric         return NewBinOp;
1339*0fca6ea1SDimitry Andric       }
1340*0fca6ea1SDimitry Andric     }
1341*0fca6ea1SDimitry Andric   }
1342*0fca6ea1SDimitry Andric 
1343349cc55cSDimitry Andric   if (match(Op1, m_APInt(C))) {
1344349cc55cSDimitry Andric     unsigned ShAmtC = C->getZExtValue();
13450b57cec5SDimitry Andric     auto *II = dyn_cast<IntrinsicInst>(Op0);
1346349cc55cSDimitry Andric     if (II && isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == ShAmtC &&
13470b57cec5SDimitry Andric         (II->getIntrinsicID() == Intrinsic::ctlz ||
13480b57cec5SDimitry Andric          II->getIntrinsicID() == Intrinsic::cttz ||
13490b57cec5SDimitry Andric          II->getIntrinsicID() == Intrinsic::ctpop)) {
13500b57cec5SDimitry Andric       // ctlz.i32(x)>>5  --> zext(x == 0)
13510b57cec5SDimitry Andric       // cttz.i32(x)>>5  --> zext(x == 0)
13520b57cec5SDimitry Andric       // ctpop.i32(x)>>5 --> zext(x == -1)
13530b57cec5SDimitry Andric       bool IsPop = II->getIntrinsicID() == Intrinsic::ctpop;
13540b57cec5SDimitry Andric       Constant *RHS = ConstantInt::getSigned(Ty, IsPop ? -1 : 0);
13550b57cec5SDimitry Andric       Value *Cmp = Builder.CreateICmpEQ(II->getArgOperand(0), RHS);
13560b57cec5SDimitry Andric       return new ZExtInst(Cmp, Ty);
13570b57cec5SDimitry Andric     }
13580b57cec5SDimitry Andric 
1359349cc55cSDimitry Andric     const APInt *C1;
1360349cc55cSDimitry Andric     if (match(Op0, m_Shl(m_Value(X), m_APInt(C1))) && C1->ult(BitWidth)) {
1361349cc55cSDimitry Andric       if (C1->ult(ShAmtC)) {
1362349cc55cSDimitry Andric         unsigned ShlAmtC = C1->getZExtValue();
1363349cc55cSDimitry Andric         Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShlAmtC);
13640b57cec5SDimitry Andric         if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
1365349cc55cSDimitry Andric           // (X <<nuw C1) >>u C --> X >>u (C - C1)
13660b57cec5SDimitry Andric           auto *NewLShr = BinaryOperator::CreateLShr(X, ShiftDiff);
13670b57cec5SDimitry Andric           NewLShr->setIsExact(I.isExact());
13680b57cec5SDimitry Andric           return NewLShr;
13690b57cec5SDimitry Andric         }
137004eeddc0SDimitry Andric         if (Op0->hasOneUse()) {
1371349cc55cSDimitry Andric           // (X << C1) >>u C  --> (X >>u (C - C1)) & (-1 >> C)
13720b57cec5SDimitry Andric           Value *NewLShr = Builder.CreateLShr(X, ShiftDiff, "", I.isExact());
1373349cc55cSDimitry Andric           APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));
13740b57cec5SDimitry Andric           return BinaryOperator::CreateAnd(NewLShr, ConstantInt::get(Ty, Mask));
13750b57cec5SDimitry Andric         }
137604eeddc0SDimitry Andric       } else if (C1->ugt(ShAmtC)) {
1377349cc55cSDimitry Andric         unsigned ShlAmtC = C1->getZExtValue();
1378349cc55cSDimitry Andric         Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmtC - ShAmtC);
13790b57cec5SDimitry Andric         if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
13805f757f3fSDimitry Andric           // (X <<nuw C1) >>u C --> X <<nuw/nsw (C1 - C)
13810b57cec5SDimitry Andric           auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
13820b57cec5SDimitry Andric           NewShl->setHasNoUnsignedWrap(true);
13835f757f3fSDimitry Andric           NewShl->setHasNoSignedWrap(ShAmtC > 0);
13840b57cec5SDimitry Andric           return NewShl;
13850b57cec5SDimitry Andric         }
138604eeddc0SDimitry Andric         if (Op0->hasOneUse()) {
1387349cc55cSDimitry Andric           // (X << C1) >>u C  --> X << (C1 - C) & (-1 >> C)
13880b57cec5SDimitry Andric           Value *NewShl = Builder.CreateShl(X, ShiftDiff);
1389349cc55cSDimitry Andric           APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));
13900b57cec5SDimitry Andric           return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask));
13910b57cec5SDimitry Andric         }
139204eeddc0SDimitry Andric       } else {
1393349cc55cSDimitry Andric         assert(*C1 == ShAmtC);
13940b57cec5SDimitry Andric         // (X << C) >>u C --> X & (-1 >>u C)
1395349cc55cSDimitry Andric         APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));
13960b57cec5SDimitry Andric         return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));
13970b57cec5SDimitry Andric       }
139804eeddc0SDimitry Andric     }
139904eeddc0SDimitry Andric 
140004eeddc0SDimitry Andric     // ((X << C) + Y) >>u C --> (X + (Y >>u C)) & (-1 >>u C)
140104eeddc0SDimitry Andric     // TODO: Consolidate with the more general transform that starts from shl
140204eeddc0SDimitry Andric     //       (the shifts are in the opposite order).
140304eeddc0SDimitry Andric     if (match(Op0,
140404eeddc0SDimitry Andric               m_OneUse(m_c_Add(m_OneUse(m_Shl(m_Value(X), m_Specific(Op1))),
140504eeddc0SDimitry Andric                                m_Value(Y))))) {
140604eeddc0SDimitry Andric       Value *NewLshr = Builder.CreateLShr(Y, Op1);
140704eeddc0SDimitry Andric       Value *NewAdd = Builder.CreateAdd(NewLshr, X);
140804eeddc0SDimitry Andric       unsigned Op1Val = C->getLimitedValue(BitWidth);
140904eeddc0SDimitry Andric       APInt Bits = APInt::getLowBitsSet(BitWidth, BitWidth - Op1Val);
141004eeddc0SDimitry Andric       Constant *Mask = ConstantInt::get(Ty, Bits);
141104eeddc0SDimitry Andric       return BinaryOperator::CreateAnd(NewAdd, Mask);
141204eeddc0SDimitry Andric     }
14130b57cec5SDimitry Andric 
14140b57cec5SDimitry Andric     if (match(Op0, m_OneUse(m_ZExt(m_Value(X)))) &&
14150b57cec5SDimitry Andric         (!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType()))) {
1416349cc55cSDimitry Andric       assert(ShAmtC < X->getType()->getScalarSizeInBits() &&
14170b57cec5SDimitry Andric              "Big shift not simplified to zero?");
14180b57cec5SDimitry Andric       // lshr (zext iM X to iN), C --> zext (lshr X, C) to iN
1419349cc55cSDimitry Andric       Value *NewLShr = Builder.CreateLShr(X, ShAmtC);
14200b57cec5SDimitry Andric       return new ZExtInst(NewLShr, Ty);
14210b57cec5SDimitry Andric     }
14220b57cec5SDimitry Andric 
1423349cc55cSDimitry Andric     if (match(Op0, m_SExt(m_Value(X)))) {
14240b57cec5SDimitry Andric       unsigned SrcTyBitWidth = X->getType()->getScalarSizeInBits();
1425349cc55cSDimitry Andric       // lshr (sext i1 X to iN), C --> select (X, -1 >> C, 0)
1426349cc55cSDimitry Andric       if (SrcTyBitWidth == 1) {
1427349cc55cSDimitry Andric         auto *NewC = ConstantInt::get(
1428349cc55cSDimitry Andric             Ty, APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));
1429349cc55cSDimitry Andric         return SelectInst::Create(X, NewC, ConstantInt::getNullValue(Ty));
1430349cc55cSDimitry Andric       }
14310b57cec5SDimitry Andric 
1432349cc55cSDimitry Andric       if ((!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType())) &&
1433349cc55cSDimitry Andric           Op0->hasOneUse()) {
1434349cc55cSDimitry Andric         // Are we moving the sign bit to the low bit and widening with high
1435349cc55cSDimitry Andric         // zeros? lshr (sext iM X to iN), N-1 --> zext (lshr X, M-1) to iN
1436349cc55cSDimitry Andric         if (ShAmtC == BitWidth - 1) {
14370b57cec5SDimitry Andric           Value *NewLShr = Builder.CreateLShr(X, SrcTyBitWidth - 1);
14380b57cec5SDimitry Andric           return new ZExtInst(NewLShr, Ty);
14390b57cec5SDimitry Andric         }
14400b57cec5SDimitry Andric 
14410b57cec5SDimitry Andric         // lshr (sext iM X to iN), N-M --> zext (ashr X, min(N-M, M-1)) to iN
1442349cc55cSDimitry Andric         if (ShAmtC == BitWidth - SrcTyBitWidth) {
14430b57cec5SDimitry Andric           // The new shift amount can't be more than the narrow source type.
1444349cc55cSDimitry Andric           unsigned NewShAmt = std::min(ShAmtC, SrcTyBitWidth - 1);
14450b57cec5SDimitry Andric           Value *AShr = Builder.CreateAShr(X, NewShAmt);
14460b57cec5SDimitry Andric           return new ZExtInst(AShr, Ty);
14470b57cec5SDimitry Andric         }
14480b57cec5SDimitry Andric       }
1449349cc55cSDimitry Andric     }
14500b57cec5SDimitry Andric 
1451349cc55cSDimitry Andric     if (ShAmtC == BitWidth - 1) {
1452fe6060f1SDimitry Andric       // lshr i32 or(X,-X), 31 --> zext (X != 0)
1453fe6060f1SDimitry Andric       if (match(Op0, m_OneUse(m_c_Or(m_Neg(m_Value(X)), m_Deferred(X)))))
1454fe6060f1SDimitry Andric         return new ZExtInst(Builder.CreateIsNotNull(X), Ty);
1455fe6060f1SDimitry Andric 
1456fe6060f1SDimitry Andric       // lshr i32 (X -nsw Y), 31 --> zext (X < Y)
1457fe6060f1SDimitry Andric       if (match(Op0, m_OneUse(m_NSWSub(m_Value(X), m_Value(Y)))))
1458e8d8bef9SDimitry Andric         return new ZExtInst(Builder.CreateICmpSLT(X, Y), Ty);
1459e8d8bef9SDimitry Andric 
1460fe6060f1SDimitry Andric       // Check if a number is negative and odd:
1461fe6060f1SDimitry Andric       // lshr i32 (srem X, 2), 31 --> and (X >> 31), X
1462fe6060f1SDimitry Andric       if (match(Op0, m_OneUse(m_SRem(m_Value(X), m_SpecificInt(2))))) {
1463349cc55cSDimitry Andric         Value *Signbit = Builder.CreateLShr(X, ShAmtC);
1464fe6060f1SDimitry Andric         return BinaryOperator::CreateAnd(Signbit, X);
1465fe6060f1SDimitry Andric       }
1466fe6060f1SDimitry Andric     }
1467fe6060f1SDimitry Andric 
1468349cc55cSDimitry Andric     Instruction *TruncSrc;
1469349cc55cSDimitry Andric     if (match(Op0, m_OneUse(m_Trunc(m_Instruction(TruncSrc)))) &&
1470349cc55cSDimitry Andric         match(TruncSrc, m_LShr(m_Value(X), m_APInt(C1)))) {
1471349cc55cSDimitry Andric       unsigned SrcWidth = X->getType()->getScalarSizeInBits();
1472349cc55cSDimitry Andric       unsigned AmtSum = ShAmtC + C1->getZExtValue();
1473349cc55cSDimitry Andric 
1474349cc55cSDimitry Andric       // If the combined shift fits in the source width:
1475349cc55cSDimitry Andric       // (trunc (X >>u C1)) >>u C --> and (trunc (X >>u (C1 + C)), MaskC
1476349cc55cSDimitry Andric       //
1477349cc55cSDimitry Andric       // If the first shift covers the number of bits truncated, then the
1478349cc55cSDimitry Andric       // mask instruction is eliminated (and so the use check is relaxed).
1479349cc55cSDimitry Andric       if (AmtSum < SrcWidth &&
1480349cc55cSDimitry Andric           (TruncSrc->hasOneUse() || C1->uge(SrcWidth - BitWidth))) {
1481349cc55cSDimitry Andric         Value *SumShift = Builder.CreateLShr(X, AmtSum, "sum.shift");
1482349cc55cSDimitry Andric         Value *Trunc = Builder.CreateTrunc(SumShift, Ty, I.getName());
1483349cc55cSDimitry Andric 
1484349cc55cSDimitry Andric         // If the first shift does not cover the number of bits truncated, then
1485349cc55cSDimitry Andric         // we require a mask to get rid of high bits in the result.
1486349cc55cSDimitry Andric         APInt MaskC = APInt::getAllOnes(BitWidth).lshr(ShAmtC);
1487349cc55cSDimitry Andric         return BinaryOperator::CreateAnd(Trunc, ConstantInt::get(Ty, MaskC));
1488349cc55cSDimitry Andric       }
1489349cc55cSDimitry Andric     }
1490349cc55cSDimitry Andric 
149181ad6265SDimitry Andric     const APInt *MulC;
149281ad6265SDimitry Andric     if (match(Op0, m_NUWMul(m_Value(X), m_APInt(MulC)))) {
1493*0fca6ea1SDimitry Andric       if (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1494*0fca6ea1SDimitry Andric           MulC->logBase2() == ShAmtC) {
1495*0fca6ea1SDimitry Andric         // Look for a "splat" mul pattern - it replicates bits across each half
1496*0fca6ea1SDimitry Andric         // of a value, so a right shift simplifies back to just X:
1497*0fca6ea1SDimitry Andric         // lshr i[2N] (mul nuw X, (2^N)+1), N --> X
1498*0fca6ea1SDimitry Andric         if (ShAmtC * 2 == BitWidth)
1499*0fca6ea1SDimitry Andric           return replaceInstUsesWith(I, X);
1500*0fca6ea1SDimitry Andric 
1501*0fca6ea1SDimitry Andric         // lshr (mul nuw (X, 2^N + 1)), N -> add nuw (X, lshr(X, N))
1502*0fca6ea1SDimitry Andric         if (Op0->hasOneUse()) {
1503*0fca6ea1SDimitry Andric           auto *NewAdd = BinaryOperator::CreateNUWAdd(
1504*0fca6ea1SDimitry Andric               X, Builder.CreateLShr(X, ConstantInt::get(Ty, ShAmtC), "",
1505*0fca6ea1SDimitry Andric                                     I.isExact()));
1506*0fca6ea1SDimitry Andric           NewAdd->setHasNoSignedWrap(
1507*0fca6ea1SDimitry Andric               cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap());
1508*0fca6ea1SDimitry Andric           return NewAdd;
1509*0fca6ea1SDimitry Andric         }
1510*0fca6ea1SDimitry Andric       }
1511fe6060f1SDimitry Andric 
151281ad6265SDimitry Andric       // The one-use check is not strictly necessary, but codegen may not be
151381ad6265SDimitry Andric       // able to invert the transform and perf may suffer with an extra mul
151481ad6265SDimitry Andric       // instruction.
151581ad6265SDimitry Andric       if (Op0->hasOneUse()) {
151681ad6265SDimitry Andric         APInt NewMulC = MulC->lshr(ShAmtC);
151781ad6265SDimitry Andric         // if c is divisible by (1 << ShAmtC):
15185f757f3fSDimitry Andric         // lshr (mul nuw x, MulC), ShAmtC -> mul nuw nsw x, (MulC >> ShAmtC)
151981ad6265SDimitry Andric         if (MulC->eq(NewMulC.shl(ShAmtC))) {
152081ad6265SDimitry Andric           auto *NewMul =
152181ad6265SDimitry Andric               BinaryOperator::CreateNUWMul(X, ConstantInt::get(Ty, NewMulC));
15225f757f3fSDimitry Andric           assert(ShAmtC != 0 &&
15235f757f3fSDimitry Andric                  "lshr X, 0 should be handled by simplifyLShrInst.");
15245f757f3fSDimitry Andric           NewMul->setHasNoSignedWrap(true);
152581ad6265SDimitry Andric           return NewMul;
152681ad6265SDimitry Andric         }
152781ad6265SDimitry Andric       }
152881ad6265SDimitry Andric     }
152981ad6265SDimitry Andric 
1530*0fca6ea1SDimitry Andric     // lshr (mul nsw (X, 2^N + 1)), N -> add nsw (X, lshr(X, N))
1531*0fca6ea1SDimitry Andric     if (match(Op0, m_OneUse(m_NSWMul(m_Value(X), m_APInt(MulC))))) {
1532*0fca6ea1SDimitry Andric       if (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1533*0fca6ea1SDimitry Andric           MulC->logBase2() == ShAmtC) {
1534*0fca6ea1SDimitry Andric         return BinaryOperator::CreateNSWAdd(
1535*0fca6ea1SDimitry Andric             X, Builder.CreateLShr(X, ConstantInt::get(Ty, ShAmtC), "",
1536*0fca6ea1SDimitry Andric                                   I.isExact()));
1537*0fca6ea1SDimitry Andric       }
1538*0fca6ea1SDimitry Andric     }
1539*0fca6ea1SDimitry Andric 
154081ad6265SDimitry Andric     // Try to narrow bswap.
154181ad6265SDimitry Andric     // In the case where the shift amount equals the bitwidth difference, the
154281ad6265SDimitry Andric     // shift is eliminated.
154381ad6265SDimitry Andric     if (match(Op0, m_OneUse(m_Intrinsic<Intrinsic::bswap>(
154481ad6265SDimitry Andric                        m_OneUse(m_ZExt(m_Value(X))))))) {
154581ad6265SDimitry Andric       unsigned SrcWidth = X->getType()->getScalarSizeInBits();
154681ad6265SDimitry Andric       unsigned WidthDiff = BitWidth - SrcWidth;
154781ad6265SDimitry Andric       if (SrcWidth % 16 == 0) {
154881ad6265SDimitry Andric         Value *NarrowSwap = Builder.CreateUnaryIntrinsic(Intrinsic::bswap, X);
154981ad6265SDimitry Andric         if (ShAmtC >= WidthDiff) {
155081ad6265SDimitry Andric           // (bswap (zext X)) >> C --> zext (bswap X >> C')
155181ad6265SDimitry Andric           Value *NewShift = Builder.CreateLShr(NarrowSwap, ShAmtC - WidthDiff);
155281ad6265SDimitry Andric           return new ZExtInst(NewShift, Ty);
155381ad6265SDimitry Andric         } else {
155481ad6265SDimitry Andric           // (bswap (zext X)) >> C --> (zext (bswap X)) << C'
155581ad6265SDimitry Andric           Value *NewZExt = Builder.CreateZExt(NarrowSwap, Ty);
155681ad6265SDimitry Andric           Constant *ShiftDiff = ConstantInt::get(Ty, WidthDiff - ShAmtC);
155781ad6265SDimitry Andric           return BinaryOperator::CreateShl(NewZExt, ShiftDiff);
155881ad6265SDimitry Andric         }
155981ad6265SDimitry Andric       }
156081ad6265SDimitry Andric     }
156181ad6265SDimitry Andric 
1562bdd1243dSDimitry Andric     // Reduce add-carry of bools to logic:
1563bdd1243dSDimitry Andric     // ((zext BoolX) + (zext BoolY)) >> 1 --> zext (BoolX && BoolY)
1564bdd1243dSDimitry Andric     Value *BoolX, *BoolY;
1565bdd1243dSDimitry Andric     if (ShAmtC == 1 && match(Op0, m_Add(m_Value(X), m_Value(Y))) &&
1566bdd1243dSDimitry Andric         match(X, m_ZExt(m_Value(BoolX))) && match(Y, m_ZExt(m_Value(BoolY))) &&
1567bdd1243dSDimitry Andric         BoolX->getType()->isIntOrIntVectorTy(1) &&
1568bdd1243dSDimitry Andric         BoolY->getType()->isIntOrIntVectorTy(1) &&
1569bdd1243dSDimitry Andric         (X->hasOneUse() || Y->hasOneUse() || Op0->hasOneUse())) {
1570bdd1243dSDimitry Andric       Value *And = Builder.CreateAnd(BoolX, BoolY);
1571bdd1243dSDimitry Andric       return new ZExtInst(And, Ty);
1572bdd1243dSDimitry Andric     }
15735f757f3fSDimitry Andric   }
1574bdd1243dSDimitry Andric 
15755f757f3fSDimitry Andric   const SimplifyQuery Q = SQ.getWithInstruction(&I);
15765f757f3fSDimitry Andric   if (setShiftFlags(I, Q))
15770b57cec5SDimitry Andric     return &I;
15780b57cec5SDimitry Andric 
15790b57cec5SDimitry Andric   // Transform  (x << y) >> y  to  x & (-1 >> y)
15800b57cec5SDimitry Andric   if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_Specific(Op1))))) {
15810b57cec5SDimitry Andric     Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
15820b57cec5SDimitry Andric     Value *Mask = Builder.CreateLShr(AllOnes, Op1);
15830b57cec5SDimitry Andric     return BinaryOperator::CreateAnd(Mask, X);
15840b57cec5SDimitry Andric   }
15850b57cec5SDimitry Andric 
1586*0fca6ea1SDimitry Andric   // Transform  (-1 << y) >> y  to -1 >> y
1587*0fca6ea1SDimitry Andric   if (match(Op0, m_Shl(m_AllOnes(), m_Specific(Op1)))) {
1588*0fca6ea1SDimitry Andric     Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
1589*0fca6ea1SDimitry Andric     return BinaryOperator::CreateLShr(AllOnes, Op1);
1590*0fca6ea1SDimitry Andric   }
1591*0fca6ea1SDimitry Andric 
1592bdd1243dSDimitry Andric   if (Instruction *Overflow = foldLShrOverflowBit(I))
1593bdd1243dSDimitry Andric     return Overflow;
1594bdd1243dSDimitry Andric 
15950b57cec5SDimitry Andric   return nullptr;
15960b57cec5SDimitry Andric }
15970b57cec5SDimitry Andric 
15988bcb0991SDimitry Andric Instruction *
1599e8d8bef9SDimitry Andric InstCombinerImpl::foldVariableSignZeroExtensionOfVariableHighBitExtract(
16008bcb0991SDimitry Andric     BinaryOperator &OldAShr) {
16018bcb0991SDimitry Andric   assert(OldAShr.getOpcode() == Instruction::AShr &&
16028bcb0991SDimitry Andric          "Must be called with arithmetic right-shift instruction only.");
16038bcb0991SDimitry Andric 
16048bcb0991SDimitry Andric   // Check that constant C is a splat of the element-wise bitwidth of V.
16058bcb0991SDimitry Andric   auto BitWidthSplat = [](Constant *C, Value *V) {
16068bcb0991SDimitry Andric     return match(
16078bcb0991SDimitry Andric         C, m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ,
16088bcb0991SDimitry Andric                               APInt(C->getType()->getScalarSizeInBits(),
16098bcb0991SDimitry Andric                                     V->getType()->getScalarSizeInBits())));
16108bcb0991SDimitry Andric   };
16118bcb0991SDimitry Andric 
16128bcb0991SDimitry Andric   // It should look like variable-length sign-extension on the outside:
16138bcb0991SDimitry Andric   //   (Val << (bitwidth(Val)-Nbits)) a>> (bitwidth(Val)-Nbits)
16148bcb0991SDimitry Andric   Value *NBits;
16158bcb0991SDimitry Andric   Instruction *MaybeTrunc;
16168bcb0991SDimitry Andric   Constant *C1, *C2;
16178bcb0991SDimitry Andric   if (!match(&OldAShr,
16188bcb0991SDimitry Andric              m_AShr(m_Shl(m_Instruction(MaybeTrunc),
16198bcb0991SDimitry Andric                           m_ZExtOrSelf(m_Sub(m_Constant(C1),
16208bcb0991SDimitry Andric                                              m_ZExtOrSelf(m_Value(NBits))))),
16218bcb0991SDimitry Andric                     m_ZExtOrSelf(m_Sub(m_Constant(C2),
16228bcb0991SDimitry Andric                                        m_ZExtOrSelf(m_Deferred(NBits)))))) ||
16238bcb0991SDimitry Andric       !BitWidthSplat(C1, &OldAShr) || !BitWidthSplat(C2, &OldAShr))
16248bcb0991SDimitry Andric     return nullptr;
16258bcb0991SDimitry Andric 
16268bcb0991SDimitry Andric   // There may or may not be a truncation after outer two shifts.
16278bcb0991SDimitry Andric   Instruction *HighBitExtract;
16288bcb0991SDimitry Andric   match(MaybeTrunc, m_TruncOrSelf(m_Instruction(HighBitExtract)));
16298bcb0991SDimitry Andric   bool HadTrunc = MaybeTrunc != HighBitExtract;
16308bcb0991SDimitry Andric 
16318bcb0991SDimitry Andric   // And finally, the innermost part of the pattern must be a right-shift.
16328bcb0991SDimitry Andric   Value *X, *NumLowBitsToSkip;
16338bcb0991SDimitry Andric   if (!match(HighBitExtract, m_Shr(m_Value(X), m_Value(NumLowBitsToSkip))))
16348bcb0991SDimitry Andric     return nullptr;
16358bcb0991SDimitry Andric 
16368bcb0991SDimitry Andric   // Said right-shift must extract high NBits bits - C0 must be it's bitwidth.
16378bcb0991SDimitry Andric   Constant *C0;
16388bcb0991SDimitry Andric   if (!match(NumLowBitsToSkip,
16398bcb0991SDimitry Andric              m_ZExtOrSelf(
16408bcb0991SDimitry Andric                  m_Sub(m_Constant(C0), m_ZExtOrSelf(m_Specific(NBits))))) ||
16418bcb0991SDimitry Andric       !BitWidthSplat(C0, HighBitExtract))
16428bcb0991SDimitry Andric     return nullptr;
16438bcb0991SDimitry Andric 
16448bcb0991SDimitry Andric   // Since the NBits is identical for all shifts, if the outermost and
16458bcb0991SDimitry Andric   // innermost shifts are identical, then outermost shifts are redundant.
16468bcb0991SDimitry Andric   // If we had truncation, do keep it though.
16478bcb0991SDimitry Andric   if (HighBitExtract->getOpcode() == OldAShr.getOpcode())
16488bcb0991SDimitry Andric     return replaceInstUsesWith(OldAShr, MaybeTrunc);
16498bcb0991SDimitry Andric 
16508bcb0991SDimitry Andric   // Else, if there was a truncation, then we need to ensure that one
16518bcb0991SDimitry Andric   // instruction will go away.
16528bcb0991SDimitry Andric   if (HadTrunc && !match(&OldAShr, m_c_BinOp(m_OneUse(m_Value()), m_Value())))
16538bcb0991SDimitry Andric     return nullptr;
16548bcb0991SDimitry Andric 
16558bcb0991SDimitry Andric   // Finally, bypass two innermost shifts, and perform the outermost shift on
16568bcb0991SDimitry Andric   // the operands of the innermost shift.
16578bcb0991SDimitry Andric   Instruction *NewAShr =
16588bcb0991SDimitry Andric       BinaryOperator::Create(OldAShr.getOpcode(), X, NumLowBitsToSkip);
16598bcb0991SDimitry Andric   NewAShr->copyIRFlags(HighBitExtract); // We can preserve 'exact'-ness.
16608bcb0991SDimitry Andric   if (!HadTrunc)
16618bcb0991SDimitry Andric     return NewAShr;
16628bcb0991SDimitry Andric 
16638bcb0991SDimitry Andric   Builder.Insert(NewAShr);
16648bcb0991SDimitry Andric   return TruncInst::CreateTruncOrBitCast(NewAShr, OldAShr.getType());
16658bcb0991SDimitry Andric }
16668bcb0991SDimitry Andric 
1667e8d8bef9SDimitry Andric Instruction *InstCombinerImpl::visitAShr(BinaryOperator &I) {
166881ad6265SDimitry Andric   if (Value *V = simplifyAShrInst(I.getOperand(0), I.getOperand(1), I.isExact(),
16690b57cec5SDimitry Andric                                   SQ.getWithInstruction(&I)))
16700b57cec5SDimitry Andric     return replaceInstUsesWith(I, V);
16710b57cec5SDimitry Andric 
16720b57cec5SDimitry Andric   if (Instruction *X = foldVectorBinop(I))
16730b57cec5SDimitry Andric     return X;
16740b57cec5SDimitry Andric 
16750b57cec5SDimitry Andric   if (Instruction *R = commonShiftTransforms(I))
16760b57cec5SDimitry Andric     return R;
16770b57cec5SDimitry Andric 
16780b57cec5SDimitry Andric   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
16790b57cec5SDimitry Andric   Type *Ty = I.getType();
16800b57cec5SDimitry Andric   unsigned BitWidth = Ty->getScalarSizeInBits();
16810b57cec5SDimitry Andric   const APInt *ShAmtAPInt;
16820b57cec5SDimitry Andric   if (match(Op1, m_APInt(ShAmtAPInt)) && ShAmtAPInt->ult(BitWidth)) {
16830b57cec5SDimitry Andric     unsigned ShAmt = ShAmtAPInt->getZExtValue();
16840b57cec5SDimitry Andric 
16850b57cec5SDimitry Andric     // If the shift amount equals the difference in width of the destination
16860b57cec5SDimitry Andric     // and source scalar types:
16870b57cec5SDimitry Andric     // ashr (shl (zext X), C), C --> sext X
16880b57cec5SDimitry Andric     Value *X;
16890b57cec5SDimitry Andric     if (match(Op0, m_Shl(m_ZExt(m_Value(X)), m_Specific(Op1))) &&
16900b57cec5SDimitry Andric         ShAmt == BitWidth - X->getType()->getScalarSizeInBits())
16910b57cec5SDimitry Andric       return new SExtInst(X, Ty);
16920b57cec5SDimitry Andric 
16930b57cec5SDimitry Andric     // We can't handle (X << C1) >>s C2. It shifts arbitrary bits in. However,
16940b57cec5SDimitry Andric     // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits.
16950b57cec5SDimitry Andric     const APInt *ShOp1;
16960b57cec5SDimitry Andric     if (match(Op0, m_NSWShl(m_Value(X), m_APInt(ShOp1))) &&
16970b57cec5SDimitry Andric         ShOp1->ult(BitWidth)) {
16980b57cec5SDimitry Andric       unsigned ShlAmt = ShOp1->getZExtValue();
16990b57cec5SDimitry Andric       if (ShlAmt < ShAmt) {
17000b57cec5SDimitry Andric         // (X <<nsw C1) >>s C2 --> X >>s (C2 - C1)
17010b57cec5SDimitry Andric         Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt);
17020b57cec5SDimitry Andric         auto *NewAShr = BinaryOperator::CreateAShr(X, ShiftDiff);
17030b57cec5SDimitry Andric         NewAShr->setIsExact(I.isExact());
17040b57cec5SDimitry Andric         return NewAShr;
17050b57cec5SDimitry Andric       }
17060b57cec5SDimitry Andric       if (ShlAmt > ShAmt) {
17070b57cec5SDimitry Andric         // (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2)
17080b57cec5SDimitry Andric         Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt);
17090b57cec5SDimitry Andric         auto *NewShl = BinaryOperator::Create(Instruction::Shl, X, ShiftDiff);
17100b57cec5SDimitry Andric         NewShl->setHasNoSignedWrap(true);
17110b57cec5SDimitry Andric         return NewShl;
17120b57cec5SDimitry Andric       }
17130b57cec5SDimitry Andric     }
17140b57cec5SDimitry Andric 
17150b57cec5SDimitry Andric     if (match(Op0, m_AShr(m_Value(X), m_APInt(ShOp1))) &&
17160b57cec5SDimitry Andric         ShOp1->ult(BitWidth)) {
17170b57cec5SDimitry Andric       unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
17180b57cec5SDimitry Andric       // Oversized arithmetic shifts replicate the sign bit.
17190b57cec5SDimitry Andric       AmtSum = std::min(AmtSum, BitWidth - 1);
17200b57cec5SDimitry Andric       // (X >>s C1) >>s C2 --> X >>s (C1 + C2)
17210b57cec5SDimitry Andric       return BinaryOperator::CreateAShr(X, ConstantInt::get(Ty, AmtSum));
17220b57cec5SDimitry Andric     }
17230b57cec5SDimitry Andric 
17240b57cec5SDimitry Andric     if (match(Op0, m_OneUse(m_SExt(m_Value(X)))) &&
17250b57cec5SDimitry Andric         (Ty->isVectorTy() || shouldChangeType(Ty, X->getType()))) {
17260b57cec5SDimitry Andric       // ashr (sext X), C --> sext (ashr X, C')
17270b57cec5SDimitry Andric       Type *SrcTy = X->getType();
17280b57cec5SDimitry Andric       ShAmt = std::min(ShAmt, SrcTy->getScalarSizeInBits() - 1);
17290b57cec5SDimitry Andric       Value *NewSh = Builder.CreateAShr(X, ConstantInt::get(SrcTy, ShAmt));
17300b57cec5SDimitry Andric       return new SExtInst(NewSh, Ty);
17310b57cec5SDimitry Andric     }
17320b57cec5SDimitry Andric 
1733fe6060f1SDimitry Andric     if (ShAmt == BitWidth - 1) {
1734fe6060f1SDimitry Andric       // ashr i32 or(X,-X), 31 --> sext (X != 0)
1735fe6060f1SDimitry Andric       if (match(Op0, m_OneUse(m_c_Or(m_Neg(m_Value(X)), m_Deferred(X)))))
1736fe6060f1SDimitry Andric         return new SExtInst(Builder.CreateIsNotNull(X), Ty);
1737fe6060f1SDimitry Andric 
1738e8d8bef9SDimitry Andric       // ashr i32 (X -nsw Y), 31 --> sext (X < Y)
1739e8d8bef9SDimitry Andric       Value *Y;
1740fe6060f1SDimitry Andric       if (match(Op0, m_OneUse(m_NSWSub(m_Value(X), m_Value(Y)))))
1741e8d8bef9SDimitry Andric         return new SExtInst(Builder.CreateICmpSLT(X, Y), Ty);
1742fe6060f1SDimitry Andric     }
1743*0fca6ea1SDimitry Andric 
1744*0fca6ea1SDimitry Andric     const APInt *MulC;
1745*0fca6ea1SDimitry Andric     if (match(Op0, m_OneUse(m_NSWMul(m_Value(X), m_APInt(MulC)))) &&
1746*0fca6ea1SDimitry Andric         (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1747*0fca6ea1SDimitry Andric          MulC->logBase2() == ShAmt &&
1748*0fca6ea1SDimitry Andric          (ShAmt < BitWidth - 1))) /* Minus 1 for the sign bit */ {
1749*0fca6ea1SDimitry Andric 
1750*0fca6ea1SDimitry Andric       // ashr (mul nsw (X, 2^N + 1)), N -> add nsw (X, ashr(X, N))
1751*0fca6ea1SDimitry Andric       auto *NewAdd = BinaryOperator::CreateNSWAdd(
1752*0fca6ea1SDimitry Andric           X,
1753*0fca6ea1SDimitry Andric           Builder.CreateAShr(X, ConstantInt::get(Ty, ShAmt), "", I.isExact()));
1754*0fca6ea1SDimitry Andric       NewAdd->setHasNoUnsignedWrap(
1755*0fca6ea1SDimitry Andric           cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap());
1756*0fca6ea1SDimitry Andric       return NewAdd;
1757*0fca6ea1SDimitry Andric     }
17585f757f3fSDimitry Andric   }
1759e8d8bef9SDimitry Andric 
17605f757f3fSDimitry Andric   const SimplifyQuery Q = SQ.getWithInstruction(&I);
17615f757f3fSDimitry Andric   if (setShiftFlags(I, Q))
17620b57cec5SDimitry Andric     return &I;
17630b57cec5SDimitry Andric 
1764349cc55cSDimitry Andric   // Prefer `-(x & 1)` over `(x << (bitwidth(x)-1)) a>> (bitwidth(x)-1)`
1765349cc55cSDimitry Andric   // as the pattern to splat the lowest bit.
1766349cc55cSDimitry Andric   // FIXME: iff X is already masked, we don't need the one-use check.
1767349cc55cSDimitry Andric   Value *X;
1768*0fca6ea1SDimitry Andric   if (match(Op1, m_SpecificIntAllowPoison(BitWidth - 1)) &&
1769349cc55cSDimitry Andric       match(Op0, m_OneUse(m_Shl(m_Value(X),
1770*0fca6ea1SDimitry Andric                                 m_SpecificIntAllowPoison(BitWidth - 1))))) {
1771349cc55cSDimitry Andric     Constant *Mask = ConstantInt::get(Ty, 1);
1772349cc55cSDimitry Andric     // Retain the knowledge about the ignored lanes.
1773349cc55cSDimitry Andric     Mask = Constant::mergeUndefsWith(
1774349cc55cSDimitry Andric         Constant::mergeUndefsWith(Mask, cast<Constant>(Op1)),
1775349cc55cSDimitry Andric         cast<Constant>(cast<Instruction>(Op0)->getOperand(1)));
1776349cc55cSDimitry Andric     X = Builder.CreateAnd(X, Mask);
1777349cc55cSDimitry Andric     return BinaryOperator::CreateNeg(X);
1778349cc55cSDimitry Andric   }
1779349cc55cSDimitry Andric 
17808bcb0991SDimitry Andric   if (Instruction *R = foldVariableSignZeroExtensionOfVariableHighBitExtract(I))
17818bcb0991SDimitry Andric     return R;
17828bcb0991SDimitry Andric 
17830b57cec5SDimitry Andric   // See if we can turn a signed shr into an unsigned shr.
1784bdd1243dSDimitry Andric   if (MaskedValueIsZero(Op0, APInt::getSignMask(BitWidth), 0, &I)) {
1785bdd1243dSDimitry Andric     Instruction *Lshr = BinaryOperator::CreateLShr(Op0, Op1);
1786bdd1243dSDimitry Andric     Lshr->setIsExact(I.isExact());
1787bdd1243dSDimitry Andric     return Lshr;
1788bdd1243dSDimitry Andric   }
17890b57cec5SDimitry Andric 
1790fe6060f1SDimitry Andric   // ashr (xor %x, -1), %y  -->  xor (ashr %x, %y), -1
1791fe6060f1SDimitry Andric   if (match(Op0, m_OneUse(m_Not(m_Value(X))))) {
1792fe6060f1SDimitry Andric     // Note that we must drop 'exact'-ness of the shift!
1793fe6060f1SDimitry Andric     // Note that we can't keep undef's in -1 vector constant!
1794fe6060f1SDimitry Andric     auto *NewAShr = Builder.CreateAShr(X, Op1, Op0->getName() + ".not");
1795fe6060f1SDimitry Andric     return BinaryOperator::CreateNot(NewAShr);
1796fe6060f1SDimitry Andric   }
1797fe6060f1SDimitry Andric 
17980b57cec5SDimitry Andric   return nullptr;
17990b57cec5SDimitry Andric }
1800