contrib/llvm-project/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

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