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.
reassociateShiftAmtsOfTwoSameDirectionShifts(BinaryOperator * Sh0,const SimplifyQuery & SQ,bool AnalyzeForSignBitExtraction)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 *
dropRedundantMaskingOfLeftShiftInput(BinaryOperator * OuterShift,const SimplifyQuery & Q,InstCombiner::BuilderTy & Builder)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).
foldShiftOfShiftedLogic(BinaryOperator & I,InstCombiner::BuilderTy & Builder)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 
commonShiftTransforms(BinaryOperator & I)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.
canEvaluateShiftedShift(unsigned OuterShAmt,bool IsOuterShl,Instruction * InnerShift,InstCombiner & IC,Instruction * CxtI)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.
canEvaluateShifted(Value * V,unsigned NumBits,bool IsLeftShift,InstCombiner & IC,Instruction * CxtI)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.
foldShiftedShift(BinaryOperator * InnerShift,unsigned OuterShAmt,bool IsOuterShl,InstCombiner::BuilderTy & Builder)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.
getShiftedValue(Value * V,unsigned NumBits,bool isLeftShift,InstCombiner & IC,const DataLayout & DL)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.
canShiftBinOpWithConstantRHS(BinaryOperator & Shift,BinaryOperator * BO)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 
FoldShiftByConstant(Value * Op0,Constant * Op1,BinaryOperator & I)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 
visitShl(BinaryOperator & I)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 
visitLShr(BinaryOperator & I)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 *
foldVariableSignZeroExtensionOfVariableHighBitExtract(BinaryOperator & OldAShr)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 
visitAShr(BinaryOperator & I)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 }
1328