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/InstructionSimplify.h"
15#include "llvm/IR/IntrinsicInst.h"
16#include "llvm/IR/PatternMatch.h"
17#include "llvm/Transforms/InstCombine/InstCombiner.h"
18using namespace llvm;
19using namespace PatternMatch;
20
21#define DEBUG_TYPE "instcombine"
22
23bool canTryToConstantAddTwoShiftAmounts(Value *Sh0, Value *ShAmt0, Value *Sh1,
24 Value *ShAmt1) {
25 // We have two shift amounts from two different shifts. The types of those
26 // shift amounts may not match. If that's the case let's bailout now..
27 if (ShAmt0->getType() != ShAmt1->getType())
28 return false;
29
30 // As input, we have the following pattern:
31 // Sh0 (Sh1 X, Q), K
32 // We want to rewrite that as:
33 // Sh x, (Q+K) iff (Q+K) u< bitwidth(x)
34 // While we know that originally (Q+K) would not overflow
35 // (because 2 * (N-1) u<= iN -1), we have looked past extensions of
36 // shift amounts. so it may now overflow in smaller bitwidth.
37 // To ensure that does not happen, we need to ensure that the total maximal
38 // shift amount is still representable in that smaller bit width.
39 unsigned MaximalPossibleTotalShiftAmount =
40 (Sh0->getType()->getScalarSizeInBits() - 1) +
41 (Sh1->getType()->getScalarSizeInBits() - 1);
42 APInt MaximalRepresentableShiftAmount =
43 APInt::getAllOnes(numBits: ShAmt0->getType()->getScalarSizeInBits());
44 return MaximalRepresentableShiftAmount.uge(RHS: MaximalPossibleTotalShiftAmount);
45}
46
47// Given pattern:
48// (x shiftopcode Q) shiftopcode K
49// we should rewrite it as
50// x shiftopcode (Q+K) iff (Q+K) u< bitwidth(x) and
51//
52// This is valid for any shift, but they must be identical, and we must be
53// careful in case we have (zext(Q)+zext(K)) and look past extensions,
54// (Q+K) must not overflow or else (Q+K) u< bitwidth(x) is bogus.
55//
56// AnalyzeForSignBitExtraction indicates that we will only analyze whether this
57// pattern has any 2 right-shifts that sum to 1 less than original bit width.
58Value *InstCombinerImpl::reassociateShiftAmtsOfTwoSameDirectionShifts(
59 BinaryOperator *Sh0, const SimplifyQuery &SQ,
60 bool AnalyzeForSignBitExtraction) {
61 // Look for a shift of some instruction, ignore zext of shift amount if any.
62 Instruction *Sh0Op0;
63 Value *ShAmt0;
64 if (!match(V: Sh0,
65 P: m_Shift(L: m_Instruction(I&: Sh0Op0), R: m_ZExtOrSelf(Op: m_Value(V&: ShAmt0)))))
66 return nullptr;
67
68 // If there is a truncation between the two shifts, we must make note of it
69 // and look through it. The truncation imposes additional constraints on the
70 // transform.
71 Instruction *Sh1;
72 Value *Trunc = nullptr;
73 match(V: Sh0Op0,
74 P: m_CombineOr(L: m_CombineAnd(L: m_Trunc(Op: m_Instruction(I&: Sh1)), R: m_Value(V&: Trunc)),
75 R: m_Instruction(I&: Sh1)));
76
77 // Inner shift: (x shiftopcode ShAmt1)
78 // Like with other shift, ignore zext of shift amount if any.
79 Value *X, *ShAmt1;
80 if (!match(V: Sh1, P: m_Shift(L: m_Value(V&: X), R: m_ZExtOrSelf(Op: m_Value(V&: ShAmt1)))))
81 return nullptr;
82
83 // Verify that it would be safe to try to add those two shift amounts.
84 if (!canTryToConstantAddTwoShiftAmounts(Sh0, ShAmt0, Sh1, ShAmt1))
85 return nullptr;
86
87 // We are only looking for signbit extraction if we have two right shifts.
88 bool HadTwoRightShifts = match(V: Sh0, P: m_Shr(L: m_Value(), R: m_Value())) &&
89 match(V: Sh1, P: m_Shr(L: m_Value(), R: m_Value()));
90 // ... and if it's not two right-shifts, we know the answer already.
91 if (AnalyzeForSignBitExtraction && !HadTwoRightShifts)
92 return nullptr;
93
94 // The shift opcodes must be identical, unless we are just checking whether
95 // this pattern can be interpreted as a sign-bit-extraction.
96 Instruction::BinaryOps ShiftOpcode = Sh0->getOpcode();
97 bool IdenticalShOpcodes = Sh0->getOpcode() == Sh1->getOpcode();
98 if (!IdenticalShOpcodes && !AnalyzeForSignBitExtraction)
99 return nullptr;
100
101 // If we saw truncation, we'll need to produce extra instruction,
102 // and for that one of the operands of the shift must be one-use,
103 // unless of course we don't actually plan to produce any instructions here.
104 if (Trunc && !AnalyzeForSignBitExtraction &&
105 !match(V: Sh0, P: m_c_BinOp(L: m_OneUse(SubPattern: m_Value()), R: m_Value())))
106 return nullptr;
107
108 // Can we fold (ShAmt0+ShAmt1) ?
109 auto *NewShAmt = dyn_cast_or_null<Constant>(
110 Val: simplifyAddInst(LHS: ShAmt0, RHS: ShAmt1, /*isNSW=*/IsNSW: false, /*isNUW=*/IsNUW: false,
111 Q: SQ.getWithInstruction(I: Sh0)));
112 if (!NewShAmt)
113 return nullptr; // Did not simplify.
114 unsigned NewShAmtBitWidth = NewShAmt->getType()->getScalarSizeInBits();
115 unsigned XBitWidth = X->getType()->getScalarSizeInBits();
116 // Is the new shift amount smaller than the bit width of inner/new shift?
117 if (!match(V: NewShAmt, P: m_SpecificInt_ICMP(Predicate: ICmpInst::Predicate::ICMP_ULT,
118 Threshold: APInt(NewShAmtBitWidth, XBitWidth))))
119 return nullptr; // FIXME: could perform constant-folding.
120
121 // If there was a truncation, and we have a right-shift, we can only fold if
122 // we are left with the original sign bit. Likewise, if we were just checking
123 // that this is a sighbit extraction, this is the place to check it.
124 // FIXME: zero shift amount is also legal here, but we can't *easily* check
125 // more than one predicate so it's not really worth it.
126 if (HadTwoRightShifts && (Trunc || AnalyzeForSignBitExtraction)) {
127 // If it's not a sign bit extraction, then we're done.
128 if (!match(V: NewShAmt,
129 P: m_SpecificInt_ICMP(Predicate: ICmpInst::Predicate::ICMP_EQ,
130 Threshold: APInt(NewShAmtBitWidth, XBitWidth - 1))))
131 return nullptr;
132 // If it is, and that was the question, return the base value.
133 if (AnalyzeForSignBitExtraction)
134 return X;
135 }
136
137 assert(IdenticalShOpcodes && "Should not get here with different shifts.");
138
139 if (NewShAmt->getType() != X->getType()) {
140 NewShAmt = ConstantFoldCastOperand(Opcode: Instruction::ZExt, C: NewShAmt,
141 DestTy: X->getType(), DL: SQ.DL);
142 if (!NewShAmt)
143 return nullptr;
144 }
145
146 // All good, we can do this fold.
147 BinaryOperator *NewShift = BinaryOperator::Create(Op: ShiftOpcode, S1: X, S2: NewShAmt);
148
149 // The flags can only be propagated if there wasn't a trunc.
150 if (!Trunc) {
151 // If the pattern did not involve trunc, and both of the original shifts
152 // had the same flag set, preserve the flag.
153 if (ShiftOpcode == Instruction::BinaryOps::Shl) {
154 NewShift->setHasNoUnsignedWrap(Sh0->hasNoUnsignedWrap() &&
155 Sh1->hasNoUnsignedWrap());
156 NewShift->setHasNoSignedWrap(Sh0->hasNoSignedWrap() &&
157 Sh1->hasNoSignedWrap());
158 } else {
159 NewShift->setIsExact(Sh0->isExact() && Sh1->isExact());
160 }
161 }
162
163 Instruction *Ret = NewShift;
164 if (Trunc) {
165 Builder.Insert(I: NewShift);
166 Ret = CastInst::Create(Instruction::Trunc, S: NewShift, Ty: Sh0->getType());
167 }
168
169 return Ret;
170}
171
172// If we have some pattern that leaves only some low bits set, and then performs
173// left-shift of those bits, if none of the bits that are left after the final
174// shift are modified by the mask, we can omit the mask.
175//
176// There are many variants to this pattern:
177// a) (x & ((1 << MaskShAmt) - 1)) << ShiftShAmt
178// b) (x & (~(-1 << MaskShAmt))) << ShiftShAmt
179// c) (x & (-1 l>> MaskShAmt)) << ShiftShAmt
180// d) (x & ((-1 << MaskShAmt) l>> MaskShAmt)) << ShiftShAmt
181// e) ((x << MaskShAmt) l>> MaskShAmt) << ShiftShAmt
182// f) ((x << MaskShAmt) a>> MaskShAmt) << ShiftShAmt
183// All these patterns can be simplified to just:
184// x << ShiftShAmt
185// iff:
186// a,b) (MaskShAmt+ShiftShAmt) u>= bitwidth(x)
187// c,d,e,f) (ShiftShAmt-MaskShAmt) s>= 0 (i.e. ShiftShAmt u>= MaskShAmt)
188static Instruction *
189dropRedundantMaskingOfLeftShiftInput(BinaryOperator *OuterShift,
190 const SimplifyQuery &Q,
191 InstCombiner::BuilderTy &Builder) {
192 assert(OuterShift->getOpcode() == Instruction::BinaryOps::Shl &&
193 "The input must be 'shl'!");
194
195 Value *Masked, *ShiftShAmt;
196 match(V: OuterShift,
197 P: m_Shift(L: m_Value(V&: Masked), R: m_ZExtOrSelf(Op: m_Value(V&: ShiftShAmt))));
198
199 // *If* there is a truncation between an outer shift and a possibly-mask,
200 // then said truncation *must* be one-use, else we can't perform the fold.
201 Value *Trunc;
202 if (match(V: Masked, P: m_CombineAnd(L: m_Trunc(Op: m_Value(V&: Masked)), R: m_Value(V&: Trunc))) &&
203 !Trunc->hasOneUse())
204 return nullptr;
205
206 Type *NarrowestTy = OuterShift->getType();
207 Type *WidestTy = Masked->getType();
208 bool HadTrunc = WidestTy != NarrowestTy;
209
210 // Check if the type can be extended.
211 if ((WidestTy->getScalarSizeInBits() * 2) > IntegerType::MAX_INT_BITS)
212 return nullptr;
213
214 // The mask must be computed in a type twice as wide to ensure
215 // that no bits are lost if the sum-of-shifts is wider than the base type.
216 Type *ExtendedTy = WidestTy->getExtendedType();
217
218 Value *MaskShAmt;
219
220 // ((1 << MaskShAmt) - 1)
221 auto MaskA = m_Add(L: m_Shl(L: m_One(), R: m_Value(V&: MaskShAmt)), R: m_AllOnes());
222 // (~(-1 << maskNbits))
223 auto MaskB = m_Not(V: m_Shl(L: m_AllOnes(), R: m_Value(V&: MaskShAmt)));
224 // (-1 l>> MaskShAmt)
225 auto MaskC = m_LShr(L: m_AllOnes(), R: m_Value(V&: MaskShAmt));
226 // ((-1 << MaskShAmt) l>> MaskShAmt)
227 auto MaskD =
228 m_LShr(L: m_Shl(L: m_AllOnes(), R: m_Value(V&: MaskShAmt)), R: m_Deferred(V: MaskShAmt));
229
230 Value *X;
231 Constant *NewMask;
232
233 if (match(V: Masked, P: m_c_And(L: m_CombineOr(L: MaskA, R: MaskB), R: m_Value(V&: X)))) {
234 // Peek through an optional zext of the shift amount.
235 match(V: MaskShAmt, P: m_ZExtOrSelf(Op: m_Value(V&: MaskShAmt)));
236
237 // Verify that it would be safe to try to add those two shift amounts.
238 if (!canTryToConstantAddTwoShiftAmounts(Sh0: OuterShift, ShAmt0: ShiftShAmt, Sh1: Masked,
239 ShAmt1: MaskShAmt))
240 return nullptr;
241
242 // Can we simplify (MaskShAmt+ShiftShAmt) ?
243 auto *SumOfShAmts = dyn_cast_or_null<Constant>(Val: simplifyAddInst(
244 LHS: MaskShAmt, RHS: ShiftShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q));
245 if (!SumOfShAmts)
246 return nullptr; // Did not simplify.
247 // In this pattern SumOfShAmts correlates with the number of low bits
248 // that shall remain in the root value (OuterShift).
249
250 // An extend of an undef value becomes zero because the high bits are never
251 // completely unknown. Replace the `undef` shift amounts with final
252 // shift bitwidth to ensure that the value remains undef when creating the
253 // subsequent shift op.
254 SumOfShAmts = Constant::replaceUndefsWith(
255 C: SumOfShAmts, Replacement: ConstantInt::get(Ty: SumOfShAmts->getType()->getScalarType(),
256 V: ExtendedTy->getScalarSizeInBits()));
257 auto *ExtendedSumOfShAmts = ConstantFoldCastOperand(
258 Opcode: Instruction::ZExt, C: SumOfShAmts, DestTy: ExtendedTy, DL: Q.DL);
259 if (!ExtendedSumOfShAmts)
260 return nullptr;
261
262 // And compute the mask as usual: ~(-1 << (SumOfShAmts))
263 auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(Ty: ExtendedTy);
264 Constant *ExtendedInvertedMask = ConstantFoldBinaryOpOperands(
265 Opcode: Instruction::Shl, LHS: ExtendedAllOnes, RHS: ExtendedSumOfShAmts, DL: Q.DL);
266 if (!ExtendedInvertedMask)
267 return nullptr;
268
269 NewMask = ConstantExpr::getNot(C: ExtendedInvertedMask);
270 } else if (match(V: Masked, P: m_c_And(L: m_CombineOr(L: MaskC, R: MaskD), R: m_Value(V&: X))) ||
271 match(V: Masked, P: m_Shr(L: m_Shl(L: m_Value(V&: X), R: m_Value(V&: MaskShAmt)),
272 R: m_Deferred(V: MaskShAmt)))) {
273 // Peek through an optional zext of the shift amount.
274 match(V: MaskShAmt, P: m_ZExtOrSelf(Op: m_Value(V&: MaskShAmt)));
275
276 // Verify that it would be safe to try to add those two shift amounts.
277 if (!canTryToConstantAddTwoShiftAmounts(Sh0: OuterShift, ShAmt0: ShiftShAmt, Sh1: Masked,
278 ShAmt1: MaskShAmt))
279 return nullptr;
280
281 // Can we simplify (ShiftShAmt-MaskShAmt) ?
282 auto *ShAmtsDiff = dyn_cast_or_null<Constant>(Val: simplifySubInst(
283 LHS: ShiftShAmt, RHS: MaskShAmt, /*IsNSW=*/false, /*IsNUW=*/false, Q));
284 if (!ShAmtsDiff)
285 return nullptr; // Did not simplify.
286 // In this pattern ShAmtsDiff correlates with the number of high bits that
287 // shall be unset in the root value (OuterShift).
288
289 // An extend of an undef value becomes zero because the high bits are never
290 // completely unknown. Replace the `undef` shift amounts with negated
291 // bitwidth of innermost shift to ensure that the value remains undef when
292 // creating the subsequent shift op.
293 unsigned WidestTyBitWidth = WidestTy->getScalarSizeInBits();
294 ShAmtsDiff = Constant::replaceUndefsWith(
295 C: ShAmtsDiff,
296 Replacement: ConstantInt::getSigned(Ty: ShAmtsDiff->getType()->getScalarType(),
297 V: -(int)WidestTyBitWidth));
298 auto *ExtendedNumHighBitsToClear = ConstantFoldCastOperand(
299 Opcode: Instruction::ZExt,
300 C: ConstantExpr::getSub(C1: ConstantInt::get(Ty: ShAmtsDiff->getType(),
301 V: WidestTyBitWidth,
302 /*isSigned=*/IsSigned: false),
303 C2: ShAmtsDiff),
304 DestTy: ExtendedTy, DL: Q.DL);
305 if (!ExtendedNumHighBitsToClear)
306 return nullptr;
307
308 // And compute the mask as usual: (-1 l>> (NumHighBitsToClear))
309 auto *ExtendedAllOnes = ConstantExpr::getAllOnesValue(Ty: ExtendedTy);
310 NewMask = ConstantFoldBinaryOpOperands(Opcode: Instruction::LShr, LHS: ExtendedAllOnes,
311 RHS: ExtendedNumHighBitsToClear, DL: Q.DL);
312 if (!NewMask)
313 return nullptr;
314 } else
315 return nullptr; // Don't know anything about this pattern.
316
317 NewMask = ConstantExpr::getTrunc(C: NewMask, Ty: NarrowestTy);
318
319 // Does this mask has any unset bits? If not then we can just not apply it.
320 bool NeedMask = !match(V: NewMask, P: m_AllOnes());
321
322 // If we need to apply a mask, there are several more restrictions we have.
323 if (NeedMask) {
324 // The old masking instruction must go away.
325 if (!Masked->hasOneUse())
326 return nullptr;
327 // The original "masking" instruction must not have been`ashr`.
328 if (match(V: Masked, P: m_AShr(L: m_Value(), R: m_Value())))
329 return nullptr;
330 }
331
332 // If we need to apply truncation, let's do it first, since we can.
333 // We have already ensured that the old truncation will go away.
334 if (HadTrunc)
335 X = Builder.CreateTrunc(V: X, DestTy: NarrowestTy);
336
337 // No 'NUW'/'NSW'! We no longer know that we won't shift-out non-0 bits.
338 // We didn't change the Type of this outermost shift, so we can just do it.
339 auto *NewShift = BinaryOperator::Create(Op: OuterShift->getOpcode(), S1: X,
340 S2: OuterShift->getOperand(i_nocapture: 1));
341 if (!NeedMask)
342 return NewShift;
343
344 Builder.Insert(I: NewShift);
345 return BinaryOperator::Create(Op: Instruction::And, S1: NewShift, S2: NewMask);
346}
347
348/// If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/
349/// shl) that itself has a shift-by-constant operand with identical opcode, we
350/// may be able to convert that into 2 independent shifts followed by the logic
351/// op. This eliminates a use of an intermediate value (reduces dependency
352/// chain).
353static Instruction *foldShiftOfShiftedBinOp(BinaryOperator &I,
354 InstCombiner::BuilderTy &Builder) {
355 assert(I.isShift() && "Expected a shift as input");
356 auto *BinInst = dyn_cast<BinaryOperator>(Val: I.getOperand(i_nocapture: 0));
357 if (!BinInst ||
358 (!BinInst->isBitwiseLogicOp() &&
359 BinInst->getOpcode() != Instruction::Add &&
360 BinInst->getOpcode() != Instruction::Sub) ||
361 !BinInst->hasOneUse())
362 return nullptr;
363
364 Constant *C0, *C1;
365 if (!match(V: I.getOperand(i_nocapture: 1), P: m_Constant(C&: C1)))
366 return nullptr;
367
368 Instruction::BinaryOps ShiftOpcode = I.getOpcode();
369 // Transform for add/sub only works with shl.
370 if ((BinInst->getOpcode() == Instruction::Add ||
371 BinInst->getOpcode() == Instruction::Sub) &&
372 ShiftOpcode != Instruction::Shl)
373 return nullptr;
374
375 Type *Ty = I.getType();
376
377 // Find a matching shift by constant. The fold is not valid if the sum
378 // of the shift values equals or exceeds bitwidth.
379 Value *X, *Y;
380 auto matchFirstShift = [&](Value *V, Value *W) {
381 unsigned Size = Ty->getScalarSizeInBits();
382 APInt Threshold(Size, Size);
383 return match(V, P: m_BinOp(Opcode: ShiftOpcode, L: m_Value(V&: X), R: m_Constant(C&: C0))) &&
384 (V->hasOneUse() || match(V: W, P: m_ImmConstant())) &&
385 match(V: ConstantExpr::getAdd(C1: C0, C2: C1),
386 P: m_SpecificInt_ICMP(Predicate: ICmpInst::ICMP_ULT, Threshold));
387 };
388
389 // Logic ops and Add are commutative, so check each operand for a match. Sub
390 // is not so we cannot reoder if we match operand(1) and need to keep the
391 // operands in their original positions.
392 bool FirstShiftIsOp1 = false;
393 if (matchFirstShift(BinInst->getOperand(i_nocapture: 0), BinInst->getOperand(i_nocapture: 1)))
394 Y = BinInst->getOperand(i_nocapture: 1);
395 else if (matchFirstShift(BinInst->getOperand(i_nocapture: 1), BinInst->getOperand(i_nocapture: 0))) {
396 Y = BinInst->getOperand(i_nocapture: 0);
397 FirstShiftIsOp1 = BinInst->getOpcode() == Instruction::Sub;
398 } else
399 return nullptr;
400
401 // shift (binop (shift X, C0), Y), C1 -> binop (shift X, C0+C1), (shift Y, C1)
402 Constant *ShiftSumC = ConstantExpr::getAdd(C1: C0, C2: C1);
403 Value *NewShift1 = Builder.CreateBinOp(Opc: ShiftOpcode, LHS: X, RHS: ShiftSumC);
404 Value *NewShift2 = Builder.CreateBinOp(Opc: ShiftOpcode, LHS: Y, RHS: C1);
405 Value *Op1 = FirstShiftIsOp1 ? NewShift2 : NewShift1;
406 Value *Op2 = FirstShiftIsOp1 ? NewShift1 : NewShift2;
407 return BinaryOperator::Create(Op: BinInst->getOpcode(), S1: Op1, S2: Op2);
408}
409
410Instruction *InstCombinerImpl::commonShiftTransforms(BinaryOperator &I) {
411 if (Instruction *Phi = foldBinopWithPhiOperands(BO&: I))
412 return Phi;
413
414 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
415 assert(Op0->getType() == Op1->getType());
416 Type *Ty = I.getType();
417
418 // If the shift amount is a one-use `sext`, we can demote it to `zext`.
419 Value *Y;
420 if (match(V: Op1, P: m_OneUse(SubPattern: m_SExt(Op: m_Value(V&: Y))))) {
421 Value *NewExt = Builder.CreateZExt(V: Y, DestTy: Ty, Name: Op1->getName());
422 return BinaryOperator::Create(Op: I.getOpcode(), S1: Op0, S2: NewExt);
423 }
424
425 // See if we can fold away this shift.
426 if (SimplifyDemandedInstructionBits(Inst&: I))
427 return &I;
428
429 // Try to fold constant and into select arguments.
430 if (isa<Constant>(Val: Op0))
431 if (SelectInst *SI = dyn_cast<SelectInst>(Val: Op1))
432 if (Instruction *R = FoldOpIntoSelect(Op&: I, SI))
433 return R;
434
435 Constant *CUI;
436 if (match(V: Op1, P: m_ImmConstant(C&: CUI)))
437 if (Instruction *Res = FoldShiftByConstant(Op0, Op1: CUI, I))
438 return Res;
439
440 if (auto *NewShift = cast_or_null<Instruction>(
441 Val: reassociateShiftAmtsOfTwoSameDirectionShifts(Sh0: &I, SQ)))
442 return NewShift;
443
444 // Pre-shift a constant shifted by a variable amount with constant offset:
445 // C shift (A add nuw C1) --> (C shift C1) shift A
446 Value *A;
447 Constant *C, *C1;
448 if (match(V: Op0, P: m_Constant(C)) &&
449 match(V: Op1, P: m_NUWAddLike(L: m_Value(V&: A), R: m_Constant(C&: C1)))) {
450 Value *NewC = Builder.CreateBinOp(Opc: I.getOpcode(), LHS: C, RHS: C1);
451 BinaryOperator *NewShiftOp = BinaryOperator::Create(Op: I.getOpcode(), S1: NewC, S2: A);
452 if (I.getOpcode() == Instruction::Shl) {
453 NewShiftOp->setHasNoSignedWrap(I.hasNoSignedWrap());
454 NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
455 } else {
456 NewShiftOp->setIsExact(I.isExact());
457 }
458 return NewShiftOp;
459 }
460
461 unsigned BitWidth = Ty->getScalarSizeInBits();
462
463 const APInt *AC, *AddC;
464 // Try to pre-shift a constant shifted by a variable amount added with a
465 // negative number:
466 // C << (X - AddC) --> (C >> AddC) << X
467 // and
468 // C >> (X - AddC) --> (C << AddC) >> X
469 if (match(V: Op0, P: m_APInt(Res&: AC)) && match(V: Op1, P: m_Add(L: m_Value(V&: A), R: m_APInt(Res&: AddC))) &&
470 AddC->isNegative() && (-*AddC).ult(RHS: BitWidth)) {
471 assert(!AC->isZero() && "Expected simplify of shifted zero");
472 unsigned PosOffset = (-*AddC).getZExtValue();
473
474 auto isSuitableForPreShift = [PosOffset, &I, AC]() {
475 switch (I.getOpcode()) {
476 default:
477 return false;
478 case Instruction::Shl:
479 return (I.hasNoSignedWrap() || I.hasNoUnsignedWrap()) &&
480 AC->eq(RHS: AC->lshr(shiftAmt: PosOffset).shl(shiftAmt: PosOffset));
481 case Instruction::LShr:
482 return I.isExact() && AC->eq(RHS: AC->shl(shiftAmt: PosOffset).lshr(shiftAmt: PosOffset));
483 case Instruction::AShr:
484 return I.isExact() && AC->eq(RHS: AC->shl(shiftAmt: PosOffset).ashr(ShiftAmt: PosOffset));
485 }
486 };
487 if (isSuitableForPreShift()) {
488 Constant *NewC = ConstantInt::get(Ty, V: I.getOpcode() == Instruction::Shl
489 ? AC->lshr(shiftAmt: PosOffset)
490 : AC->shl(shiftAmt: PosOffset));
491 BinaryOperator *NewShiftOp =
492 BinaryOperator::Create(Op: I.getOpcode(), S1: NewC, S2: A);
493 if (I.getOpcode() == Instruction::Shl) {
494 NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
495 } else {
496 NewShiftOp->setIsExact();
497 }
498 return NewShiftOp;
499 }
500 }
501
502 // X shift (A srem C) -> X shift (A and (C - 1)) iff C is a power of 2.
503 // Because shifts by negative values (which could occur if A were negative)
504 // are undefined.
505 if (Op1->hasOneUse() && match(V: Op1, P: m_SRem(L: m_Value(V&: A), R: m_Constant(C))) &&
506 match(V: C, P: m_Power2())) {
507 // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't
508 // demand the sign bit (and many others) here??
509 Constant *Mask = ConstantExpr::getSub(C1: C, C2: ConstantInt::get(Ty, V: 1));
510 Value *Rem = Builder.CreateAnd(LHS: A, RHS: Mask, Name: Op1->getName());
511 return replaceOperand(I, OpNum: 1, V: Rem);
512 }
513
514 if (Instruction *Logic = foldShiftOfShiftedBinOp(I, Builder))
515 return Logic;
516
517 if (match(V: Op1, P: m_Or(L: m_Value(), R: m_SpecificInt(V: BitWidth - 1))))
518 return replaceOperand(I, OpNum: 1, V: ConstantInt::get(Ty, V: BitWidth - 1));
519
520 Instruction *CmpIntr;
521 if ((I.getOpcode() == Instruction::LShr ||
522 I.getOpcode() == Instruction::AShr) &&
523 match(V: Op0, P: m_OneUse(SubPattern: m_Instruction(I&: CmpIntr))) &&
524 isa<CmpIntrinsic>(Val: CmpIntr) &&
525 match(V: Op1, P: m_SpecificInt(V: Ty->getScalarSizeInBits() - 1))) {
526 Value *Cmp =
527 Builder.CreateICmp(P: cast<CmpIntrinsic>(Val: CmpIntr)->getLTPredicate(),
528 LHS: CmpIntr->getOperand(i: 0), RHS: CmpIntr->getOperand(i: 1));
529 return CastInst::Create(I.getOpcode() == Instruction::LShr
530 ? Instruction::ZExt
531 : Instruction::SExt,
532 S: Cmp, Ty);
533 }
534
535 return nullptr;
536}
537
538/// Return true if we can simplify two logical (either left or right) shifts
539/// that have constant shift amounts: OuterShift (InnerShift X, C1), C2.
540static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl,
541 Instruction *InnerShift,
542 InstCombinerImpl &IC, Instruction *CxtI) {
543 assert(InnerShift->isLogicalShift() && "Unexpected instruction type");
544
545 // We need constant scalar or constant splat shifts.
546 const APInt *InnerShiftConst;
547 if (!match(V: InnerShift->getOperand(i: 1), P: m_APInt(Res&: InnerShiftConst)))
548 return false;
549
550 // Two logical shifts in the same direction:
551 // shl (shl X, C1), C2 --> shl X, C1 + C2
552 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
553 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
554 if (IsInnerShl == IsOuterShl)
555 return true;
556
557 // Equal shift amounts in opposite directions become bitwise 'and':
558 // lshr (shl X, C), C --> and X, C'
559 // shl (lshr X, C), C --> and X, C'
560 if (*InnerShiftConst == OuterShAmt)
561 return true;
562
563 // If the 2nd shift is bigger than the 1st, we can fold:
564 // lshr (shl X, C1), C2 --> and (shl X, C1 - C2), C3
565 // shl (lshr X, C1), C2 --> and (lshr X, C1 - C2), C3
566 // but it isn't profitable unless we know the and'd out bits are already zero.
567 // Also, check that the inner shift is valid (less than the type width) or
568 // we'll crash trying to produce the bit mask for the 'and'.
569 unsigned TypeWidth = InnerShift->getType()->getScalarSizeInBits();
570 if (InnerShiftConst->ugt(RHS: OuterShAmt) && InnerShiftConst->ult(RHS: TypeWidth)) {
571 unsigned InnerShAmt = InnerShiftConst->getZExtValue();
572 unsigned MaskShift =
573 IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt;
574 APInt Mask = APInt::getLowBitsSet(numBits: TypeWidth, loBitsSet: OuterShAmt) << MaskShift;
575 if (IC.MaskedValueIsZero(V: InnerShift->getOperand(i: 0), Mask, CxtI))
576 return true;
577 }
578
579 return false;
580}
581
582/// See if we can compute the specified value, but shifted logically to the left
583/// or right by some number of bits. This should return true if the expression
584/// can be computed for the same cost as the current expression tree. This is
585/// used to eliminate extraneous shifting from things like:
586/// %C = shl i128 %A, 64
587/// %D = shl i128 %B, 96
588/// %E = or i128 %C, %D
589/// %F = lshr i128 %E, 64
590/// where the client will ask if E can be computed shifted right by 64-bits. If
591/// this succeeds, getShiftedValue() will be called to produce the value.
592static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift,
593 InstCombinerImpl &IC, Instruction *CxtI) {
594 // We can always evaluate immediate constants.
595 if (match(V, P: m_ImmConstant()))
596 return true;
597
598 Instruction *I = dyn_cast<Instruction>(Val: V);
599 if (!I) return false;
600
601 // We can't mutate something that has multiple uses: doing so would
602 // require duplicating the instruction in general, which isn't profitable.
603 if (!I->hasOneUse()) return false;
604
605 switch (I->getOpcode()) {
606 default: return false;
607 case Instruction::And:
608 case Instruction::Or:
609 case Instruction::Xor:
610 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
611 return canEvaluateShifted(V: I->getOperand(i: 0), NumBits, IsLeftShift, IC, CxtI: I) &&
612 canEvaluateShifted(V: I->getOperand(i: 1), NumBits, IsLeftShift, IC, CxtI: I);
613
614 case Instruction::Shl:
615 case Instruction::LShr:
616 return canEvaluateShiftedShift(OuterShAmt: NumBits, IsOuterShl: IsLeftShift, InnerShift: I, IC, CxtI);
617
618 case Instruction::Select: {
619 SelectInst *SI = cast<SelectInst>(Val: I);
620 Value *TrueVal = SI->getTrueValue();
621 Value *FalseVal = SI->getFalseValue();
622 return canEvaluateShifted(V: TrueVal, NumBits, IsLeftShift, IC, CxtI: SI) &&
623 canEvaluateShifted(V: FalseVal, NumBits, IsLeftShift, IC, CxtI: SI);
624 }
625 case Instruction::PHI: {
626 // We can change a phi if we can change all operands. Note that we never
627 // get into trouble with cyclic PHIs here because we only consider
628 // instructions with a single use.
629 PHINode *PN = cast<PHINode>(Val: I);
630 for (Value *IncValue : PN->incoming_values())
631 if (!canEvaluateShifted(V: IncValue, NumBits, IsLeftShift, IC, CxtI: PN))
632 return false;
633 return true;
634 }
635 case Instruction::Mul: {
636 const APInt *MulConst;
637 // We can fold (shr (mul X, -(1 << C)), C) -> (and (neg X), C`)
638 return !IsLeftShift && match(V: I->getOperand(i: 1), P: m_APInt(Res&: MulConst)) &&
639 MulConst->isNegatedPowerOf2() && MulConst->countr_zero() == NumBits;
640 }
641 }
642}
643
644/// Fold OuterShift (InnerShift X, C1), C2.
645/// See canEvaluateShiftedShift() for the constraints on these instructions.
646static Value *foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt,
647 bool IsOuterShl,
648 InstCombiner::BuilderTy &Builder) {
649 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
650 Type *ShType = InnerShift->getType();
651 unsigned TypeWidth = ShType->getScalarSizeInBits();
652
653 // We only accept shifts-by-a-constant in canEvaluateShifted().
654 const APInt *C1;
655 match(V: InnerShift->getOperand(i_nocapture: 1), P: m_APInt(Res&: C1));
656 unsigned InnerShAmt = C1->getZExtValue();
657
658 // Change the shift amount and clear the appropriate IR flags.
659 auto NewInnerShift = [&](unsigned ShAmt) {
660 InnerShift->setOperand(i_nocapture: 1, Val_nocapture: ConstantInt::get(Ty: ShType, V: ShAmt));
661 if (IsInnerShl) {
662 InnerShift->setHasNoUnsignedWrap(false);
663 InnerShift->setHasNoSignedWrap(false);
664 } else {
665 InnerShift->setIsExact(false);
666 }
667 return InnerShift;
668 };
669
670 // Two logical shifts in the same direction:
671 // shl (shl X, C1), C2 --> shl X, C1 + C2
672 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
673 if (IsInnerShl == IsOuterShl) {
674 // If this is an oversized composite shift, then unsigned shifts get 0.
675 if (InnerShAmt + OuterShAmt >= TypeWidth)
676 return Constant::getNullValue(Ty: ShType);
677
678 return NewInnerShift(InnerShAmt + OuterShAmt);
679 }
680
681 // Equal shift amounts in opposite directions become bitwise 'and':
682 // lshr (shl X, C), C --> and X, C'
683 // shl (lshr X, C), C --> and X, C'
684 if (InnerShAmt == OuterShAmt) {
685 APInt Mask = IsInnerShl
686 ? APInt::getLowBitsSet(numBits: TypeWidth, loBitsSet: TypeWidth - OuterShAmt)
687 : APInt::getHighBitsSet(numBits: TypeWidth, hiBitsSet: TypeWidth - OuterShAmt);
688 Value *And = Builder.CreateAnd(LHS: InnerShift->getOperand(i_nocapture: 0),
689 RHS: ConstantInt::get(Ty: ShType, V: Mask));
690 if (auto *AndI = dyn_cast<Instruction>(Val: And)) {
691 AndI->moveBefore(InsertPos: InnerShift->getIterator());
692 AndI->takeName(V: InnerShift);
693 }
694 return And;
695 }
696
697 assert(InnerShAmt > OuterShAmt &&
698 "Unexpected opposite direction logical shift pair");
699
700 // In general, we would need an 'and' for this transform, but
701 // canEvaluateShiftedShift() guarantees that the masked-off bits are not used.
702 // lshr (shl X, C1), C2 --> shl X, C1 - C2
703 // shl (lshr X, C1), C2 --> lshr X, C1 - C2
704 return NewInnerShift(InnerShAmt - OuterShAmt);
705}
706
707/// When canEvaluateShifted() returns true for an expression, this function
708/// inserts the new computation that produces the shifted value.
709static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift,
710 InstCombinerImpl &IC, const DataLayout &DL) {
711 // We can always evaluate constants shifted.
712 if (Constant *C = dyn_cast<Constant>(Val: V)) {
713 if (isLeftShift)
714 return IC.Builder.CreateShl(LHS: C, RHS: NumBits);
715 else
716 return IC.Builder.CreateLShr(LHS: C, RHS: NumBits);
717 }
718
719 Instruction *I = cast<Instruction>(Val: V);
720 IC.addToWorklist(I);
721
722 switch (I->getOpcode()) {
723 default: llvm_unreachable("Inconsistency with CanEvaluateShifted");
724 case Instruction::And:
725 case Instruction::Or:
726 case Instruction::Xor:
727 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
728 I->setOperand(
729 i: 0, Val: getShiftedValue(V: I->getOperand(i: 0), NumBits, isLeftShift, IC, DL));
730 I->setOperand(
731 i: 1, Val: getShiftedValue(V: I->getOperand(i: 1), NumBits, isLeftShift, IC, DL));
732 return I;
733
734 case Instruction::Shl:
735 case Instruction::LShr:
736 return foldShiftedShift(InnerShift: cast<BinaryOperator>(Val: I), OuterShAmt: NumBits, IsOuterShl: isLeftShift,
737 Builder&: IC.Builder);
738
739 case Instruction::Select:
740 I->setOperand(
741 i: 1, Val: getShiftedValue(V: I->getOperand(i: 1), NumBits, isLeftShift, IC, DL));
742 I->setOperand(
743 i: 2, Val: getShiftedValue(V: I->getOperand(i: 2), NumBits, isLeftShift, IC, DL));
744 return I;
745 case Instruction::PHI: {
746 // We can change a phi if we can change all operands. Note that we never
747 // get into trouble with cyclic PHIs here because we only consider
748 // instructions with a single use.
749 PHINode *PN = cast<PHINode>(Val: I);
750 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
751 PN->setIncomingValue(i, V: getShiftedValue(V: PN->getIncomingValue(i), NumBits,
752 isLeftShift, IC, DL));
753 return PN;
754 }
755 case Instruction::Mul: {
756 assert(!isLeftShift && "Unexpected shift direction!");
757 auto *Neg = BinaryOperator::CreateNeg(Op: I->getOperand(i: 0));
758 IC.InsertNewInstWith(New: Neg, Old: I->getIterator());
759 unsigned TypeWidth = I->getType()->getScalarSizeInBits();
760 APInt Mask = APInt::getLowBitsSet(numBits: TypeWidth, loBitsSet: TypeWidth - NumBits);
761 auto *And = BinaryOperator::CreateAnd(V1: Neg,
762 V2: ConstantInt::get(Ty: I->getType(), V: Mask));
763 And->takeName(V: I);
764 return IC.InsertNewInstWith(New: And, Old: I->getIterator());
765 }
766 }
767}
768
769// If this is a bitwise operator or add with a constant RHS we might be able
770// to pull it through a shift.
771static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift,
772 BinaryOperator *BO) {
773 switch (BO->getOpcode()) {
774 default:
775 return false; // Do not perform transform!
776 case Instruction::Add:
777 return Shift.getOpcode() == Instruction::Shl;
778 case Instruction::Or:
779 case Instruction::And:
780 return true;
781 case Instruction::Xor:
782 // Do not change a 'not' of logical shift because that would create a normal
783 // 'xor'. The 'not' is likely better for analysis, SCEV, and codegen.
784 return !(Shift.isLogicalShift() && match(V: BO, P: m_Not(V: m_Value())));
785 }
786}
787
788Instruction *InstCombinerImpl::FoldShiftByConstant(Value *Op0, Constant *C1,
789 BinaryOperator &I) {
790 // (C2 << X) << C1 --> (C2 << C1) << X
791 // (C2 >> X) >> C1 --> (C2 >> C1) >> X
792 Constant *C2;
793 Value *X;
794 bool IsLeftShift = I.getOpcode() == Instruction::Shl;
795 if (match(V: Op0, P: m_BinOp(Opcode: I.getOpcode(), L: m_ImmConstant(C&: C2), R: m_Value(V&: X)))) {
796 Instruction *R = BinaryOperator::Create(
797 Op: I.getOpcode(), S1: Builder.CreateBinOp(Opc: I.getOpcode(), LHS: C2, RHS: C1), S2: X);
798 BinaryOperator *BO0 = cast<BinaryOperator>(Val: Op0);
799 if (IsLeftShift) {
800 R->setHasNoUnsignedWrap(I.hasNoUnsignedWrap() &&
801 BO0->hasNoUnsignedWrap());
802 R->setHasNoSignedWrap(I.hasNoSignedWrap() && BO0->hasNoSignedWrap());
803 } else
804 R->setIsExact(I.isExact() && BO0->isExact());
805 return R;
806 }
807
808 Type *Ty = I.getType();
809 unsigned TypeBits = Ty->getScalarSizeInBits();
810
811 // (X / +DivC) >> (Width - 1) --> ext (X <= -DivC)
812 // (X / -DivC) >> (Width - 1) --> ext (X >= +DivC)
813 const APInt *DivC;
814 if (!IsLeftShift && match(V: C1, P: m_SpecificIntAllowPoison(V: TypeBits - 1)) &&
815 match(V: Op0, P: m_SDiv(L: m_Value(V&: X), R: m_APInt(Res&: DivC))) && !DivC->isZero() &&
816 !DivC->isMinSignedValue()) {
817 Constant *NegDivC = ConstantInt::get(Ty, V: -(*DivC));
818 ICmpInst::Predicate Pred =
819 DivC->isNegative() ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_SLE;
820 Value *Cmp = Builder.CreateICmp(P: Pred, LHS: X, RHS: NegDivC);
821 auto ExtOpcode = (I.getOpcode() == Instruction::AShr) ? Instruction::SExt
822 : Instruction::ZExt;
823 return CastInst::Create(ExtOpcode, S: Cmp, Ty);
824 }
825
826 const APInt *Op1C;
827 if (!match(V: C1, P: m_APInt(Res&: Op1C)))
828 return nullptr;
829
830 assert(!Op1C->uge(TypeBits) &&
831 "Shift over the type width should have been removed already");
832
833 // See if we can propagate this shift into the input, this covers the trivial
834 // cast of lshr(shl(x,c1),c2) as well as other more complex cases.
835 if (I.getOpcode() != Instruction::AShr &&
836 canEvaluateShifted(V: Op0, NumBits: Op1C->getZExtValue(), IsLeftShift, IC&: *this, CxtI: &I)) {
837 LLVM_DEBUG(
838 dbgs() << "ICE: GetShiftedValue propagating shift through expression"
839 " to eliminate shift:\n IN: "
840 << *Op0 << "\n SH: " << I << "\n");
841
842 return replaceInstUsesWith(
843 I, V: getShiftedValue(V: Op0, NumBits: Op1C->getZExtValue(), isLeftShift: IsLeftShift, IC&: *this, DL));
844 }
845
846 if (Instruction *FoldedShift = foldBinOpIntoSelectOrPhi(I))
847 return FoldedShift;
848
849 if (!Op0->hasOneUse())
850 return nullptr;
851
852 if (auto *Op0BO = dyn_cast<BinaryOperator>(Val: Op0)) {
853 // If the operand is a bitwise operator with a constant RHS, and the
854 // shift is the only use, we can pull it out of the shift.
855 const APInt *Op0C;
856 if (match(V: Op0BO->getOperand(i_nocapture: 1), P: m_APInt(Res&: Op0C))) {
857 if (canShiftBinOpWithConstantRHS(Shift&: I, BO: Op0BO)) {
858 Value *NewRHS =
859 Builder.CreateBinOp(Opc: I.getOpcode(), LHS: Op0BO->getOperand(i_nocapture: 1), RHS: C1);
860
861 Value *NewShift =
862 Builder.CreateBinOp(Opc: I.getOpcode(), LHS: Op0BO->getOperand(i_nocapture: 0), RHS: C1);
863 NewShift->takeName(V: Op0BO);
864
865 return BinaryOperator::Create(Op: Op0BO->getOpcode(), S1: NewShift, S2: NewRHS);
866 }
867 }
868 }
869
870 // If we have a select that conditionally executes some binary operator,
871 // see if we can pull it the select and operator through the shift.
872 //
873 // For example, turning:
874 // shl (select C, (add X, C1), X), C2
875 // Into:
876 // Y = shl X, C2
877 // select C, (add Y, C1 << C2), Y
878 Value *Cond;
879 BinaryOperator *TBO;
880 Value *FalseVal;
881 if (match(V: Op0, P: m_Select(C: m_Value(V&: Cond), L: m_OneUse(SubPattern: m_BinOp(I&: TBO)),
882 R: m_Value(V&: FalseVal)))) {
883 const APInt *C;
884 if (!isa<Constant>(Val: FalseVal) && TBO->getOperand(i_nocapture: 0) == FalseVal &&
885 match(V: TBO->getOperand(i_nocapture: 1), P: m_APInt(Res&: C)) &&
886 canShiftBinOpWithConstantRHS(Shift&: I, BO: TBO)) {
887 Value *NewRHS =
888 Builder.CreateBinOp(Opc: I.getOpcode(), LHS: TBO->getOperand(i_nocapture: 1), RHS: C1);
889
890 Value *NewShift = Builder.CreateBinOp(Opc: I.getOpcode(), LHS: FalseVal, RHS: C1);
891 Value *NewOp = Builder.CreateBinOp(Opc: TBO->getOpcode(), LHS: NewShift, RHS: NewRHS);
892 return SelectInst::Create(C: Cond, S1: NewOp, S2: NewShift);
893 }
894 }
895
896 BinaryOperator *FBO;
897 Value *TrueVal;
898 if (match(V: Op0, P: m_Select(C: m_Value(V&: Cond), L: m_Value(V&: TrueVal),
899 R: m_OneUse(SubPattern: m_BinOp(I&: FBO))))) {
900 const APInt *C;
901 if (!isa<Constant>(Val: TrueVal) && FBO->getOperand(i_nocapture: 0) == TrueVal &&
902 match(V: FBO->getOperand(i_nocapture: 1), P: m_APInt(Res&: C)) &&
903 canShiftBinOpWithConstantRHS(Shift&: I, BO: FBO)) {
904 Value *NewRHS =
905 Builder.CreateBinOp(Opc: I.getOpcode(), LHS: FBO->getOperand(i_nocapture: 1), RHS: C1);
906
907 Value *NewShift = Builder.CreateBinOp(Opc: I.getOpcode(), LHS: TrueVal, RHS: C1);
908 Value *NewOp = Builder.CreateBinOp(Opc: FBO->getOpcode(), LHS: NewShift, RHS: NewRHS);
909 return SelectInst::Create(C: Cond, S1: NewShift, S2: NewOp);
910 }
911 }
912
913 return nullptr;
914}
915
916// Tries to perform
917// (lshr (add (zext X), (zext Y)), K)
918// -> (icmp ult (add X, Y), X)
919// where
920// - The add's operands are zexts from a K-bits integer to a bigger type.
921// - The add is only used by the shr, or by iK (or narrower) truncates.
922// - The lshr type has more than 2 bits (other types are boolean math).
923// - K > 1
924// note that
925// - The resulting add cannot have nuw/nsw, else on overflow we get a
926// poison value and the transform isn't legal anymore.
927Instruction *InstCombinerImpl::foldLShrOverflowBit(BinaryOperator &I) {
928 assert(I.getOpcode() == Instruction::LShr);
929
930 Value *Add = I.getOperand(i_nocapture: 0);
931 Value *ShiftAmt = I.getOperand(i_nocapture: 1);
932 Type *Ty = I.getType();
933
934 if (Ty->getScalarSizeInBits() < 3)
935 return nullptr;
936
937 const APInt *ShAmtAPInt = nullptr;
938 Value *X = nullptr, *Y = nullptr;
939 if (!match(V: ShiftAmt, P: m_APInt(Res&: ShAmtAPInt)) ||
940 !match(V: Add,
941 P: m_Add(L: m_OneUse(SubPattern: m_ZExt(Op: m_Value(V&: X))), R: m_OneUse(SubPattern: m_ZExt(Op: m_Value(V&: Y))))))
942 return nullptr;
943
944 const unsigned ShAmt = ShAmtAPInt->getZExtValue();
945 if (ShAmt == 1)
946 return nullptr;
947
948 // X/Y are zexts from `ShAmt`-sized ints.
949 if (X->getType()->getScalarSizeInBits() != ShAmt ||
950 Y->getType()->getScalarSizeInBits() != ShAmt)
951 return nullptr;
952
953 // Make sure that `Add` is only used by `I` and `ShAmt`-truncates.
954 if (!Add->hasOneUse()) {
955 for (User *U : Add->users()) {
956 if (U == &I)
957 continue;
958
959 TruncInst *Trunc = dyn_cast<TruncInst>(Val: U);
960 if (!Trunc || Trunc->getType()->getScalarSizeInBits() > ShAmt)
961 return nullptr;
962 }
963 }
964
965 // Insert at Add so that the newly created `NarrowAdd` will dominate it's
966 // users (i.e. `Add`'s users).
967 Instruction *AddInst = cast<Instruction>(Val: Add);
968 Builder.SetInsertPoint(AddInst);
969
970 Value *NarrowAdd = Builder.CreateAdd(LHS: X, RHS: Y, Name: "add.narrowed");
971 Value *Overflow =
972 Builder.CreateICmpULT(LHS: NarrowAdd, RHS: X, Name: "add.narrowed.overflow");
973
974 // Replace the uses of the original add with a zext of the
975 // NarrowAdd's result. Note that all users at this stage are known to
976 // be ShAmt-sized truncs, or the lshr itself.
977 if (!Add->hasOneUse()) {
978 replaceInstUsesWith(I&: *AddInst, V: Builder.CreateZExt(V: NarrowAdd, DestTy: Ty));
979 eraseInstFromFunction(I&: *AddInst);
980 }
981
982 // Replace the LShr with a zext of the overflow check.
983 return new ZExtInst(Overflow, Ty);
984}
985
986// Try to set nuw/nsw flags on shl or exact flag on lshr/ashr using knownbits.
987static bool setShiftFlags(BinaryOperator &I, const SimplifyQuery &Q) {
988 assert(I.isShift() && "Expected a shift as input");
989 // We already have all the flags.
990 if (I.getOpcode() == Instruction::Shl) {
991 if (I.hasNoUnsignedWrap() && I.hasNoSignedWrap())
992 return false;
993 } else {
994 if (I.isExact())
995 return false;
996
997 // shr (shl X, Y), Y
998 if (match(V: I.getOperand(i_nocapture: 0), P: m_Shl(L: m_Value(), R: m_Specific(V: I.getOperand(i_nocapture: 1))))) {
999 I.setIsExact();
1000 return true;
1001 }
1002 // Infer 'exact' flag if shift amount is cttz(x) on the same operand.
1003 if (match(V: I.getOperand(i_nocapture: 1), P: m_Intrinsic<Intrinsic::cttz>(
1004 Op0: m_Specific(V: I.getOperand(i_nocapture: 0)), Op1: m_Value()))) {
1005 I.setIsExact();
1006 return true;
1007 }
1008 }
1009
1010 // Compute what we know about shift count.
1011 KnownBits KnownCnt = computeKnownBits(V: I.getOperand(i_nocapture: 1), Q);
1012 unsigned BitWidth = KnownCnt.getBitWidth();
1013 // Since shift produces a poison value if RHS is equal to or larger than the
1014 // bit width, we can safely assume that RHS is less than the bit width.
1015 uint64_t MaxCnt = KnownCnt.getMaxValue().getLimitedValue(Limit: BitWidth - 1);
1016
1017 KnownBits KnownAmt = computeKnownBits(V: I.getOperand(i_nocapture: 0), Q);
1018 bool Changed = false;
1019
1020 if (I.getOpcode() == Instruction::Shl) {
1021 // If we have as many leading zeros than maximum shift cnt we have nuw.
1022 if (!I.hasNoUnsignedWrap() && MaxCnt <= KnownAmt.countMinLeadingZeros()) {
1023 I.setHasNoUnsignedWrap();
1024 Changed = true;
1025 }
1026 // If we have more sign bits than maximum shift cnt we have nsw.
1027 if (!I.hasNoSignedWrap()) {
1028 if (MaxCnt < KnownAmt.countMinSignBits() ||
1029 MaxCnt <
1030 ComputeNumSignBits(Op: I.getOperand(i_nocapture: 0), DL: Q.DL, AC: Q.AC, CxtI: Q.CxtI, DT: Q.DT)) {
1031 I.setHasNoSignedWrap();
1032 Changed = true;
1033 }
1034 }
1035 return Changed;
1036 }
1037
1038 // If we have at least as many trailing zeros as maximum count then we have
1039 // exact.
1040 Changed = MaxCnt <= KnownAmt.countMinTrailingZeros();
1041 I.setIsExact(Changed);
1042
1043 return Changed;
1044}
1045
1046Instruction *InstCombinerImpl::visitShl(BinaryOperator &I) {
1047 const SimplifyQuery Q = SQ.getWithInstruction(I: &I);
1048
1049 if (Value *V = simplifyShlInst(Op0: I.getOperand(i_nocapture: 0), Op1: I.getOperand(i_nocapture: 1),
1050 IsNSW: I.hasNoSignedWrap(), IsNUW: I.hasNoUnsignedWrap(), Q))
1051 return replaceInstUsesWith(I, V);
1052
1053 if (Instruction *X = foldVectorBinop(Inst&: I))
1054 return X;
1055
1056 if (Instruction *V = commonShiftTransforms(I))
1057 return V;
1058
1059 if (Instruction *V = dropRedundantMaskingOfLeftShiftInput(OuterShift: &I, Q, Builder))
1060 return V;
1061
1062 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
1063 Type *Ty = I.getType();
1064 unsigned BitWidth = Ty->getScalarSizeInBits();
1065
1066 const APInt *C;
1067 if (match(V: Op1, P: m_APInt(Res&: C))) {
1068 unsigned ShAmtC = C->getZExtValue();
1069
1070 // shl (zext X), C --> zext (shl X, C)
1071 // This is only valid if X would have zeros shifted out.
1072 Value *X;
1073 if (match(V: Op0, P: m_OneUse(SubPattern: m_ZExt(Op: m_Value(V&: X))))) {
1074 unsigned SrcWidth = X->getType()->getScalarSizeInBits();
1075 if (ShAmtC < SrcWidth &&
1076 MaskedValueIsZero(V: X, Mask: APInt::getHighBitsSet(numBits: SrcWidth, hiBitsSet: ShAmtC), CxtI: &I))
1077 return new ZExtInst(Builder.CreateShl(LHS: X, RHS: ShAmtC), Ty);
1078 }
1079
1080 // (X >> C) << C --> X & (-1 << C)
1081 if (match(V: Op0, P: m_Shr(L: m_Value(V&: X), R: m_Specific(V: Op1)))) {
1082 APInt Mask(APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: BitWidth - ShAmtC));
1083 return BinaryOperator::CreateAnd(V1: X, V2: ConstantInt::get(Ty, V: Mask));
1084 }
1085
1086 const APInt *C1;
1087 if (match(V: Op0, P: m_Exact(SubPattern: m_Shr(L: m_Value(V&: X), R: m_APInt(Res&: C1)))) &&
1088 C1->ult(RHS: BitWidth)) {
1089 unsigned ShrAmt = C1->getZExtValue();
1090 if (ShrAmt < ShAmtC) {
1091 // If C1 < C: (X >>?,exact C1) << C --> X << (C - C1)
1092 Constant *ShiftDiff = ConstantInt::get(Ty, V: ShAmtC - ShrAmt);
1093 auto *NewShl = BinaryOperator::CreateShl(V1: X, V2: ShiftDiff);
1094 NewShl->setHasNoUnsignedWrap(
1095 I.hasNoUnsignedWrap() ||
1096 (ShrAmt &&
1097 cast<Instruction>(Val: Op0)->getOpcode() == Instruction::LShr &&
1098 I.hasNoSignedWrap()));
1099 NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
1100 return NewShl;
1101 }
1102 if (ShrAmt > ShAmtC) {
1103 // If C1 > C: (X >>?exact C1) << C --> X >>?exact (C1 - C)
1104 Constant *ShiftDiff = ConstantInt::get(Ty, V: ShrAmt - ShAmtC);
1105 auto *NewShr = BinaryOperator::Create(
1106 Op: cast<BinaryOperator>(Val: Op0)->getOpcode(), S1: X, S2: ShiftDiff);
1107 NewShr->setIsExact(true);
1108 return NewShr;
1109 }
1110 }
1111
1112 if (match(V: Op0, P: m_OneUse(SubPattern: m_Shr(L: m_Value(V&: X), R: m_APInt(Res&: C1)))) &&
1113 C1->ult(RHS: BitWidth)) {
1114 unsigned ShrAmt = C1->getZExtValue();
1115 if (ShrAmt < ShAmtC) {
1116 // If C1 < C: (X >>? C1) << C --> (X << (C - C1)) & (-1 << C)
1117 Constant *ShiftDiff = ConstantInt::get(Ty, V: ShAmtC - ShrAmt);
1118 auto *NewShl = BinaryOperator::CreateShl(V1: X, V2: ShiftDiff);
1119 NewShl->setHasNoUnsignedWrap(
1120 I.hasNoUnsignedWrap() ||
1121 (ShrAmt &&
1122 cast<Instruction>(Val: Op0)->getOpcode() == Instruction::LShr &&
1123 I.hasNoSignedWrap()));
1124 NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
1125 Builder.Insert(I: NewShl);
1126 APInt Mask(APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: BitWidth - ShAmtC));
1127 return BinaryOperator::CreateAnd(V1: NewShl, V2: ConstantInt::get(Ty, V: Mask));
1128 }
1129 if (ShrAmt > ShAmtC) {
1130 // If C1 > C: (X >>? C1) << C --> (X >>? (C1 - C)) & (-1 << C)
1131 Constant *ShiftDiff = ConstantInt::get(Ty, V: ShrAmt - ShAmtC);
1132 auto *OldShr = cast<BinaryOperator>(Val: Op0);
1133 auto *NewShr =
1134 BinaryOperator::Create(Op: OldShr->getOpcode(), S1: X, S2: ShiftDiff);
1135 NewShr->setIsExact(OldShr->isExact());
1136 Builder.Insert(I: NewShr);
1137 APInt Mask(APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: BitWidth - ShAmtC));
1138 return BinaryOperator::CreateAnd(V1: NewShr, V2: ConstantInt::get(Ty, V: Mask));
1139 }
1140 }
1141
1142 // Similar to above, but look through an intermediate trunc instruction.
1143 BinaryOperator *Shr;
1144 if (match(V: Op0, P: m_OneUse(SubPattern: m_Trunc(Op: m_OneUse(SubPattern: m_BinOp(I&: Shr))))) &&
1145 match(V: Shr, P: m_Shr(L: m_Value(V&: X), R: m_APInt(Res&: C1)))) {
1146 // The larger shift direction survives through the transform.
1147 unsigned ShrAmtC = C1->getZExtValue();
1148 unsigned ShDiff = ShrAmtC > ShAmtC ? ShrAmtC - ShAmtC : ShAmtC - ShrAmtC;
1149 Constant *ShiftDiffC = ConstantInt::get(Ty: X->getType(), V: ShDiff);
1150 auto ShiftOpc = ShrAmtC > ShAmtC ? Shr->getOpcode() : Instruction::Shl;
1151
1152 // If C1 > C:
1153 // (trunc (X >> C1)) << C --> (trunc (X >> (C1 - C))) && (-1 << C)
1154 // If C > C1:
1155 // (trunc (X >> C1)) << C --> (trunc (X << (C - C1))) && (-1 << C)
1156 Value *NewShift = Builder.CreateBinOp(Opc: ShiftOpc, LHS: X, RHS: ShiftDiffC, Name: "sh.diff");
1157 Value *Trunc = Builder.CreateTrunc(V: NewShift, DestTy: Ty, Name: "tr.sh.diff");
1158 APInt Mask(APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: BitWidth - ShAmtC));
1159 return BinaryOperator::CreateAnd(V1: Trunc, V2: ConstantInt::get(Ty, V: Mask));
1160 }
1161
1162 // If we have an opposite shift by the same amount, we may be able to
1163 // reorder binops and shifts to eliminate math/logic.
1164 auto isSuitableBinOpcode = [](Instruction::BinaryOps BinOpcode) {
1165 switch (BinOpcode) {
1166 default:
1167 return false;
1168 case Instruction::Add:
1169 case Instruction::And:
1170 case Instruction::Or:
1171 case Instruction::Xor:
1172 case Instruction::Sub:
1173 // NOTE: Sub is not commutable and the tranforms below may not be valid
1174 // when the shift-right is operand 1 (RHS) of the sub.
1175 return true;
1176 }
1177 };
1178 BinaryOperator *Op0BO;
1179 if (match(V: Op0, P: m_OneUse(SubPattern: m_BinOp(I&: Op0BO))) &&
1180 isSuitableBinOpcode(Op0BO->getOpcode())) {
1181 // Commute so shift-right is on LHS of the binop.
1182 // (Y bop (X >> C)) << C -> ((X >> C) bop Y) << C
1183 // (Y bop ((X >> C) & CC)) << C -> (((X >> C) & CC) bop Y) << C
1184 Value *Shr = Op0BO->getOperand(i_nocapture: 0);
1185 Value *Y = Op0BO->getOperand(i_nocapture: 1);
1186 Value *X;
1187 const APInt *CC;
1188 if (Op0BO->isCommutative() && Y->hasOneUse() &&
1189 (match(V: Y, P: m_Shr(L: m_Value(), R: m_Specific(V: Op1))) ||
1190 match(V: Y, P: m_And(L: m_OneUse(SubPattern: m_Shr(L: m_Value(), R: m_Specific(V: Op1))),
1191 R: m_APInt(Res&: CC)))))
1192 std::swap(a&: Shr, b&: Y);
1193
1194 // ((X >> C) bop Y) << C -> (X bop (Y << C)) & (~0 << C)
1195 if (match(V: Shr, P: m_OneUse(SubPattern: m_Shr(L: m_Value(V&: X), R: m_Specific(V: Op1))))) {
1196 // Y << C
1197 Value *YS = Builder.CreateShl(LHS: Y, RHS: Op1, Name: Op0BO->getName());
1198 // (X bop (Y << C))
1199 Value *B =
1200 Builder.CreateBinOp(Opc: Op0BO->getOpcode(), LHS: X, RHS: YS, Name: Shr->getName());
1201 unsigned Op1Val = C->getLimitedValue(Limit: BitWidth);
1202 APInt Bits = APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: BitWidth - Op1Val);
1203 Constant *Mask = ConstantInt::get(Ty, V: Bits);
1204 return BinaryOperator::CreateAnd(V1: B, V2: Mask);
1205 }
1206
1207 // (((X >> C) & CC) bop Y) << C -> (X & (CC << C)) bop (Y << C)
1208 if (match(V: Shr,
1209 P: m_OneUse(SubPattern: m_And(L: m_OneUse(SubPattern: m_Shr(L: m_Value(V&: X), R: m_Specific(V: Op1))),
1210 R: m_APInt(Res&: CC))))) {
1211 // Y << C
1212 Value *YS = Builder.CreateShl(LHS: Y, RHS: Op1, Name: Op0BO->getName());
1213 // X & (CC << C)
1214 Value *M = Builder.CreateAnd(LHS: X, RHS: ConstantInt::get(Ty, V: CC->shl(ShiftAmt: *C)),
1215 Name: X->getName() + ".mask");
1216 auto *NewOp = BinaryOperator::Create(Op: Op0BO->getOpcode(), S1: M, S2: YS);
1217 if (auto *Disjoint = dyn_cast<PossiblyDisjointInst>(Val: Op0BO);
1218 Disjoint && Disjoint->isDisjoint())
1219 cast<PossiblyDisjointInst>(Val: NewOp)->setIsDisjoint(true);
1220 return NewOp;
1221 }
1222 }
1223
1224 // (C1 - X) << C --> (C1 << C) - (X << C)
1225 if (match(V: Op0, P: m_OneUse(SubPattern: m_Sub(L: m_APInt(Res&: C1), R: m_Value(V&: X))))) {
1226 Constant *NewLHS = ConstantInt::get(Ty, V: C1->shl(ShiftAmt: *C));
1227 Value *NewShift = Builder.CreateShl(LHS: X, RHS: Op1);
1228 return BinaryOperator::CreateSub(V1: NewLHS, V2: NewShift);
1229 }
1230 }
1231
1232 if (setShiftFlags(I, Q))
1233 return &I;
1234
1235 // Transform (x >> y) << y to x & (-1 << y)
1236 // Valid for any type of right-shift.
1237 Value *X;
1238 if (match(V: Op0, P: m_OneUse(SubPattern: m_Shr(L: m_Value(V&: X), R: m_Specific(V: Op1))))) {
1239 Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
1240 Value *Mask = Builder.CreateShl(LHS: AllOnes, RHS: Op1);
1241 return BinaryOperator::CreateAnd(V1: Mask, V2: X);
1242 }
1243
1244 // Transform (-1 >> y) << y to -1 << y
1245 if (match(V: Op0, P: m_LShr(L: m_AllOnes(), R: m_Specific(V: Op1)))) {
1246 Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
1247 return BinaryOperator::CreateShl(V1: AllOnes, V2: Op1);
1248 }
1249
1250 Constant *C1;
1251 if (match(V: Op1, P: m_ImmConstant(C&: C1))) {
1252 Constant *C2;
1253 Value *X;
1254 // (X * C2) << C1 --> X * (C2 << C1)
1255 if (match(V: Op0, P: m_Mul(L: m_Value(V&: X), R: m_ImmConstant(C&: C2))))
1256 return BinaryOperator::CreateMul(V1: X, V2: Builder.CreateShl(LHS: C2, RHS: C1));
1257
1258 // shl (zext i1 X), C1 --> select (X, 1 << C1, 0)
1259 if (match(V: Op0, P: m_ZExt(Op: m_Value(V&: X))) && X->getType()->isIntOrIntVectorTy(BitWidth: 1)) {
1260 auto *NewC = Builder.CreateShl(LHS: ConstantInt::get(Ty, V: 1), RHS: C1);
1261 return createSelectInstWithUnknownProfile(C: X, S1: NewC,
1262 S2: ConstantInt::getNullValue(Ty));
1263 }
1264 }
1265
1266 if (match(V: Op0, P: m_One())) {
1267 // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1
1268 if (match(V: Op1, P: m_Sub(L: m_SpecificInt(V: BitWidth - 1), R: m_Value(V&: X))))
1269 return BinaryOperator::CreateLShr(
1270 V1: ConstantInt::get(Ty, V: APInt::getSignMask(BitWidth)), V2: X);
1271
1272 // Canonicalize "extract lowest set bit" using cttz to and-with-negate:
1273 // 1 << (cttz X) --> -X & X
1274 if (match(V: Op1,
1275 P: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::cttz>(Op0: m_Value(V&: X), Op1: m_Value())))) {
1276 Value *NegX = Builder.CreateNeg(V: X, Name: "neg");
1277 return BinaryOperator::CreateAnd(V1: NegX, V2: X);
1278 }
1279 }
1280
1281 return nullptr;
1282}
1283
1284Instruction *InstCombinerImpl::visitLShr(BinaryOperator &I) {
1285 if (Value *V = simplifyLShrInst(Op0: I.getOperand(i_nocapture: 0), Op1: I.getOperand(i_nocapture: 1), IsExact: I.isExact(),
1286 Q: SQ.getWithInstruction(I: &I)))
1287 return replaceInstUsesWith(I, V);
1288
1289 if (Instruction *X = foldVectorBinop(Inst&: I))
1290 return X;
1291
1292 if (Instruction *R = commonShiftTransforms(I))
1293 return R;
1294
1295 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
1296 Type *Ty = I.getType();
1297 Value *X;
1298 const APInt *C;
1299 unsigned BitWidth = Ty->getScalarSizeInBits();
1300
1301 // (iN (~X) u>> (N - 1)) --> zext (X > -1)
1302 if (match(V: Op0, P: m_OneUse(SubPattern: m_Not(V: m_Value(V&: X)))) &&
1303 match(V: Op1, P: m_SpecificIntAllowPoison(V: BitWidth - 1)))
1304 return new ZExtInst(Builder.CreateIsNotNeg(Arg: X, Name: "isnotneg"), Ty);
1305
1306 // ((X << nuw Z) sub nuw Y) >>u exact Z --> X sub nuw (Y >>u exact Z)
1307 Value *Y;
1308 if (I.isExact() &&
1309 match(V: Op0, P: m_OneUse(SubPattern: m_NUWSub(L: m_NUWShl(L: m_Value(V&: X), R: m_Specific(V: Op1)),
1310 R: m_Value(V&: Y))))) {
1311 Value *NewLshr = Builder.CreateLShr(LHS: Y, RHS: Op1, Name: "", /*isExact=*/true);
1312 auto *NewSub = BinaryOperator::CreateNUWSub(V1: X, V2: NewLshr);
1313 NewSub->setHasNoSignedWrap(
1314 cast<OverflowingBinaryOperator>(Val: Op0)->hasNoSignedWrap());
1315 return NewSub;
1316 }
1317
1318 // Fold (X + Y) / 2 --> (X & Y) iff (X u<= 1) && (Y u<= 1)
1319 if (match(V: Op0, P: m_Add(L: m_Value(V&: X), R: m_Value(V&: Y))) && match(V: Op1, P: m_One()) &&
1320 computeKnownBits(V: X, CxtI: &I).countMaxActiveBits() <= 1 &&
1321 computeKnownBits(V: Y, CxtI: &I).countMaxActiveBits() <= 1)
1322 return BinaryOperator::CreateAnd(V1: X, V2: Y);
1323
1324 // (sub nuw X, (Y << nuw Z)) >>u exact Z --> (X >>u exact Z) sub nuw Y
1325 if (I.isExact() &&
1326 match(V: Op0, P: m_OneUse(SubPattern: m_NUWSub(L: m_Value(V&: X),
1327 R: m_NUWShl(L: m_Value(V&: Y), R: m_Specific(V: Op1)))))) {
1328 Value *NewLshr = Builder.CreateLShr(LHS: X, RHS: Op1, Name: "", /*isExact=*/true);
1329 auto *NewSub = BinaryOperator::CreateNUWSub(V1: NewLshr, V2: Y);
1330 NewSub->setHasNoSignedWrap(
1331 cast<OverflowingBinaryOperator>(Val: Op0)->hasNoSignedWrap());
1332 return NewSub;
1333 }
1334
1335 auto isSuitableBinOpcode = [](Instruction::BinaryOps BinOpcode) {
1336 switch (BinOpcode) {
1337 default:
1338 return false;
1339 case Instruction::Add:
1340 case Instruction::And:
1341 case Instruction::Or:
1342 case Instruction::Xor:
1343 // Sub is handled separately.
1344 return true;
1345 }
1346 };
1347
1348 // If both the binop and the shift are nuw, then:
1349 // ((X << nuw Z) binop nuw Y) >>u Z --> X binop nuw (Y >>u Z)
1350 if (match(V: Op0, P: m_OneUse(SubPattern: m_c_BinOp(L: m_NUWShl(L: m_Value(V&: X), R: m_Specific(V: Op1)),
1351 R: m_Value(V&: Y))))) {
1352 BinaryOperator *Op0OB = cast<BinaryOperator>(Val: Op0);
1353 if (isSuitableBinOpcode(Op0OB->getOpcode())) {
1354 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(Val: Op0);
1355 !OBO || OBO->hasNoUnsignedWrap()) {
1356 Value *NewLshr = Builder.CreateLShr(
1357 LHS: Y, RHS: Op1, Name: "", isExact: I.isExact() && Op0OB->getOpcode() != Instruction::And);
1358 auto *NewBinOp = BinaryOperator::Create(Op: Op0OB->getOpcode(), S1: NewLshr, S2: X);
1359 if (OBO) {
1360 NewBinOp->setHasNoUnsignedWrap(true);
1361 NewBinOp->setHasNoSignedWrap(OBO->hasNoSignedWrap());
1362 } else if (auto *Disjoint = dyn_cast<PossiblyDisjointInst>(Val: Op0)) {
1363 cast<PossiblyDisjointInst>(Val: NewBinOp)->setIsDisjoint(
1364 Disjoint->isDisjoint());
1365 }
1366 return NewBinOp;
1367 }
1368 }
1369 }
1370
1371 if (match(V: Op1, P: m_APInt(Res&: C))) {
1372 unsigned ShAmtC = C->getZExtValue();
1373 auto *II = dyn_cast<IntrinsicInst>(Val: Op0);
1374 if (II && isPowerOf2_32(Value: BitWidth) && Log2_32(Value: BitWidth) == ShAmtC &&
1375 (II->getIntrinsicID() == Intrinsic::ctlz ||
1376 II->getIntrinsicID() == Intrinsic::cttz ||
1377 II->getIntrinsicID() == Intrinsic::ctpop)) {
1378 // ctlz.i32(x)>>5 --> zext(x == 0)
1379 // cttz.i32(x)>>5 --> zext(x == 0)
1380 // ctpop.i32(x)>>5 --> zext(x == -1)
1381 bool IsPop = II->getIntrinsicID() == Intrinsic::ctpop;
1382 Constant *RHS = ConstantInt::getSigned(Ty, V: IsPop ? -1 : 0);
1383 Value *Cmp = Builder.CreateICmpEQ(LHS: II->getArgOperand(i: 0), RHS);
1384 return new ZExtInst(Cmp, Ty);
1385 }
1386
1387 const APInt *C1;
1388 if (match(V: Op0, P: m_Shl(L: m_Value(V&: X), R: m_APInt(Res&: C1))) && C1->ult(RHS: BitWidth)) {
1389 if (C1->ult(RHS: ShAmtC)) {
1390 unsigned ShlAmtC = C1->getZExtValue();
1391 Constant *ShiftDiff = ConstantInt::get(Ty, V: ShAmtC - ShlAmtC);
1392 if (cast<BinaryOperator>(Val: Op0)->hasNoUnsignedWrap()) {
1393 // (X <<nuw C1) >>u C --> X >>u (C - C1)
1394 auto *NewLShr = BinaryOperator::CreateLShr(V1: X, V2: ShiftDiff);
1395 NewLShr->setIsExact(I.isExact());
1396 return NewLShr;
1397 }
1398 if (Op0->hasOneUse()) {
1399 // (X << C1) >>u C --> (X >>u (C - C1)) & (-1 >> C)
1400 Value *NewLShr = Builder.CreateLShr(LHS: X, RHS: ShiftDiff, Name: "", isExact: I.isExact());
1401 APInt Mask(APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth - ShAmtC));
1402 return BinaryOperator::CreateAnd(V1: NewLShr, V2: ConstantInt::get(Ty, V: Mask));
1403 }
1404 } else if (C1->ugt(RHS: ShAmtC)) {
1405 unsigned ShlAmtC = C1->getZExtValue();
1406 Constant *ShiftDiff = ConstantInt::get(Ty, V: ShlAmtC - ShAmtC);
1407 if (cast<BinaryOperator>(Val: Op0)->hasNoUnsignedWrap()) {
1408 // (X <<nuw C1) >>u C --> X <<nuw/nsw (C1 - C)
1409 auto *NewShl = BinaryOperator::CreateShl(V1: X, V2: ShiftDiff);
1410 NewShl->setHasNoUnsignedWrap(true);
1411 NewShl->setHasNoSignedWrap(ShAmtC > 0);
1412 return NewShl;
1413 }
1414 if (Op0->hasOneUse()) {
1415 // (X << C1) >>u C --> X << (C1 - C) & (-1 >> C)
1416 Value *NewShl = Builder.CreateShl(LHS: X, RHS: ShiftDiff);
1417 APInt Mask(APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth - ShAmtC));
1418 return BinaryOperator::CreateAnd(V1: NewShl, V2: ConstantInt::get(Ty, V: Mask));
1419 }
1420 } else {
1421 assert(*C1 == ShAmtC);
1422 // (X << C) >>u C --> X & (-1 >>u C)
1423 APInt Mask(APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth - ShAmtC));
1424 return BinaryOperator::CreateAnd(V1: X, V2: ConstantInt::get(Ty, V: Mask));
1425 }
1426 }
1427
1428 // ((X << C) + Y) >>u C --> (X + (Y >>u C)) & (-1 >>u C)
1429 // TODO: Consolidate with the more general transform that starts from shl
1430 // (the shifts are in the opposite order).
1431 if (match(V: Op0,
1432 P: m_OneUse(SubPattern: m_c_Add(L: m_OneUse(SubPattern: m_Shl(L: m_Value(V&: X), R: m_Specific(V: Op1))),
1433 R: m_Value(V&: Y))))) {
1434 Value *NewLshr = Builder.CreateLShr(LHS: Y, RHS: Op1);
1435 Value *NewAdd = Builder.CreateAdd(LHS: NewLshr, RHS: X);
1436 unsigned Op1Val = C->getLimitedValue(Limit: BitWidth);
1437 APInt Bits = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth - Op1Val);
1438 Constant *Mask = ConstantInt::get(Ty, V: Bits);
1439 return BinaryOperator::CreateAnd(V1: NewAdd, V2: Mask);
1440 }
1441
1442 if (match(V: Op0, P: m_OneUse(SubPattern: m_ZExt(Op: m_Value(V&: X)))) &&
1443 (!Ty->isIntegerTy() || shouldChangeType(From: Ty, To: X->getType()))) {
1444 assert(ShAmtC < X->getType()->getScalarSizeInBits() &&
1445 "Big shift not simplified to zero?");
1446 // lshr (zext iM X to iN), C --> zext (lshr X, C) to iN
1447 Value *NewLShr = Builder.CreateLShr(LHS: X, RHS: ShAmtC);
1448 return new ZExtInst(NewLShr, Ty);
1449 }
1450
1451 if (match(V: Op0, P: m_SExt(Op: m_Value(V&: X)))) {
1452 unsigned SrcTyBitWidth = X->getType()->getScalarSizeInBits();
1453 // lshr (sext i1 X to iN), C --> select (X, -1 >> C, 0)
1454 if (SrcTyBitWidth == 1) {
1455 auto *NewC = ConstantInt::get(
1456 Ty, V: APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: BitWidth - ShAmtC));
1457 return SelectInst::Create(C: X, S1: NewC, S2: ConstantInt::getNullValue(Ty));
1458 }
1459
1460 if ((!Ty->isIntegerTy() || shouldChangeType(From: Ty, To: X->getType())) &&
1461 Op0->hasOneUse()) {
1462 // Are we moving the sign bit to the low bit and widening with high
1463 // zeros? lshr (sext iM X to iN), N-1 --> zext (lshr X, M-1) to iN
1464 if (ShAmtC == BitWidth - 1) {
1465 Value *NewLShr = Builder.CreateLShr(LHS: X, RHS: SrcTyBitWidth - 1);
1466 return new ZExtInst(NewLShr, Ty);
1467 }
1468
1469 // lshr (sext iM X to iN), N-M --> zext (ashr X, min(N-M, M-1)) to iN
1470 if (ShAmtC == BitWidth - SrcTyBitWidth) {
1471 // The new shift amount can't be more than the narrow source type.
1472 unsigned NewShAmt = std::min(a: ShAmtC, b: SrcTyBitWidth - 1);
1473 Value *AShr = Builder.CreateAShr(LHS: X, RHS: NewShAmt);
1474 return new ZExtInst(AShr, Ty);
1475 }
1476 }
1477 }
1478
1479 if (ShAmtC == BitWidth - 1) {
1480 // lshr i32 or(X,-X), 31 --> zext (X != 0)
1481 if (match(V: Op0, P: m_OneUse(SubPattern: m_c_Or(L: m_Neg(V: m_Value(V&: X)), R: m_Deferred(V: X)))))
1482 return new ZExtInst(Builder.CreateIsNotNull(Arg: X), Ty);
1483
1484 // lshr i32 (X -nsw Y), 31 --> zext (X < Y)
1485 if (match(V: Op0, P: m_OneUse(SubPattern: m_NSWSub(L: m_Value(V&: X), R: m_Value(V&: Y)))))
1486 return new ZExtInst(Builder.CreateICmpSLT(LHS: X, RHS: Y), Ty);
1487
1488 // Check if a number is negative and odd:
1489 // lshr i32 (srem X, 2), 31 --> and (X >> 31), X
1490 if (match(V: Op0, P: m_OneUse(SubPattern: m_SRem(L: m_Value(V&: X), R: m_SpecificInt(V: 2))))) {
1491 Value *Signbit = Builder.CreateLShr(LHS: X, RHS: ShAmtC);
1492 return BinaryOperator::CreateAnd(V1: Signbit, V2: X);
1493 }
1494
1495 // lshr iN (X - 1) & ~X, N-1 --> zext (X == 0)
1496 if (match(V: Op0, P: m_OneUse(SubPattern: m_c_And(L: m_Add(L: m_Value(V&: X), R: m_AllOnes()),
1497 R: m_Not(V: m_Deferred(V: X))))))
1498 return new ZExtInst(Builder.CreateIsNull(Arg: X), Ty);
1499 }
1500
1501 Instruction *TruncSrc;
1502 if (match(V: Op0, P: m_OneUse(SubPattern: m_Trunc(Op: m_Instruction(I&: TruncSrc)))) &&
1503 match(V: TruncSrc, P: m_LShr(L: m_Value(V&: X), R: m_APInt(Res&: C1)))) {
1504 unsigned SrcWidth = X->getType()->getScalarSizeInBits();
1505 unsigned AmtSum = ShAmtC + C1->getZExtValue();
1506
1507 // If the combined shift fits in the source width:
1508 // (trunc (X >>u C1)) >>u C --> and (trunc (X >>u (C1 + C)), MaskC
1509 //
1510 // If the first shift covers the number of bits truncated, then the
1511 // mask instruction is eliminated (and so the use check is relaxed).
1512 if (AmtSum < SrcWidth &&
1513 (TruncSrc->hasOneUse() || C1->uge(RHS: SrcWidth - BitWidth))) {
1514 Value *SumShift = Builder.CreateLShr(LHS: X, RHS: AmtSum, Name: "sum.shift");
1515 Value *Trunc = Builder.CreateTrunc(V: SumShift, DestTy: Ty, Name: I.getName());
1516
1517 // If the first shift does not cover the number of bits truncated, then
1518 // we require a mask to get rid of high bits in the result.
1519 APInt MaskC = APInt::getAllOnes(numBits: BitWidth).lshr(shiftAmt: ShAmtC);
1520 return BinaryOperator::CreateAnd(V1: Trunc, V2: ConstantInt::get(Ty, V: MaskC));
1521 }
1522 }
1523
1524 const APInt *MulC;
1525 if (match(V: Op0, P: m_NUWMul(L: m_Value(V&: X), R: m_APInt(Res&: MulC)))) {
1526 if (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1527 MulC->logBase2() == ShAmtC) {
1528 // Look for a "splat" mul pattern - it replicates bits across each half
1529 // of a value, so a right shift simplifies back to just X:
1530 // lshr i[2N] (mul nuw X, (2^N)+1), N --> X
1531 if (ShAmtC * 2 == BitWidth)
1532 return replaceInstUsesWith(I, V: X);
1533
1534 // lshr (mul nuw (X, 2^N + 1)), N -> add nuw (X, lshr(X, N))
1535 if (Op0->hasOneUse()) {
1536 auto *NewAdd = BinaryOperator::CreateNUWAdd(
1537 V1: X, V2: Builder.CreateLShr(LHS: X, RHS: ConstantInt::get(Ty, V: ShAmtC), Name: "",
1538 isExact: I.isExact()));
1539 NewAdd->setHasNoSignedWrap(
1540 cast<OverflowingBinaryOperator>(Val: Op0)->hasNoSignedWrap());
1541 return NewAdd;
1542 }
1543 }
1544
1545 // The one-use check is not strictly necessary, but codegen may not be
1546 // able to invert the transform and perf may suffer with an extra mul
1547 // instruction.
1548 if (Op0->hasOneUse()) {
1549 APInt NewMulC = MulC->lshr(shiftAmt: ShAmtC);
1550 // if c is divisible by (1 << ShAmtC):
1551 // lshr (mul nuw x, MulC), ShAmtC -> mul nuw nsw x, (MulC >> ShAmtC)
1552 if (MulC->eq(RHS: NewMulC.shl(shiftAmt: ShAmtC))) {
1553 auto *NewMul =
1554 BinaryOperator::CreateNUWMul(V1: X, V2: ConstantInt::get(Ty, V: NewMulC));
1555 assert(ShAmtC != 0 &&
1556 "lshr X, 0 should be handled by simplifyLShrInst.");
1557 NewMul->setHasNoSignedWrap(true);
1558 return NewMul;
1559 }
1560 }
1561 }
1562
1563 // lshr (mul nsw (X, 2^N + 1)), N -> add nsw (X, lshr(X, N))
1564 if (match(V: Op0, P: m_OneUse(SubPattern: m_NSWMul(L: m_Value(V&: X), R: m_APInt(Res&: MulC))))) {
1565 if (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1566 MulC->logBase2() == ShAmtC) {
1567 return BinaryOperator::CreateNSWAdd(
1568 V1: X, V2: Builder.CreateLShr(LHS: X, RHS: ConstantInt::get(Ty, V: ShAmtC), Name: "",
1569 isExact: I.isExact()));
1570 }
1571 }
1572
1573 // Try to narrow bswap.
1574 // In the case where the shift amount equals the bitwidth difference, the
1575 // shift is eliminated.
1576 if (match(V: Op0, P: m_OneUse(SubPattern: m_Intrinsic<Intrinsic::bswap>(
1577 Op0: m_OneUse(SubPattern: m_ZExt(Op: m_Value(V&: X))))))) {
1578 unsigned SrcWidth = X->getType()->getScalarSizeInBits();
1579 unsigned WidthDiff = BitWidth - SrcWidth;
1580 if (SrcWidth % 16 == 0) {
1581 Value *NarrowSwap = Builder.CreateUnaryIntrinsic(ID: Intrinsic::bswap, V: X);
1582 if (ShAmtC >= WidthDiff) {
1583 // (bswap (zext X)) >> C --> zext (bswap X >> C')
1584 Value *NewShift = Builder.CreateLShr(LHS: NarrowSwap, RHS: ShAmtC - WidthDiff);
1585 return new ZExtInst(NewShift, Ty);
1586 } else {
1587 // (bswap (zext X)) >> C --> (zext (bswap X)) << C'
1588 Value *NewZExt = Builder.CreateZExt(V: NarrowSwap, DestTy: Ty);
1589 Constant *ShiftDiff = ConstantInt::get(Ty, V: WidthDiff - ShAmtC);
1590 return BinaryOperator::CreateShl(V1: NewZExt, V2: ShiftDiff);
1591 }
1592 }
1593 }
1594
1595 // Reduce add-carry of bools to logic:
1596 // ((zext BoolX) + (zext BoolY)) >> 1 --> zext (BoolX && BoolY)
1597 Value *BoolX, *BoolY;
1598 if (ShAmtC == 1 && match(V: Op0, P: m_Add(L: m_Value(V&: X), R: m_Value(V&: Y))) &&
1599 match(V: X, P: m_ZExt(Op: m_Value(V&: BoolX))) && match(V: Y, P: m_ZExt(Op: m_Value(V&: BoolY))) &&
1600 BoolX->getType()->isIntOrIntVectorTy(BitWidth: 1) &&
1601 BoolY->getType()->isIntOrIntVectorTy(BitWidth: 1) &&
1602 (X->hasOneUse() || Y->hasOneUse() || Op0->hasOneUse())) {
1603 Value *And = Builder.CreateAnd(LHS: BoolX, RHS: BoolY);
1604 return new ZExtInst(And, Ty);
1605 }
1606 }
1607
1608 const SimplifyQuery Q = SQ.getWithInstruction(I: &I);
1609 if (setShiftFlags(I, Q))
1610 return &I;
1611
1612 // Transform (x << y) >> y to x & (-1 >> y)
1613 if (match(V: Op0, P: m_OneUse(SubPattern: m_Shl(L: m_Value(V&: X), R: m_Specific(V: Op1))))) {
1614 Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
1615 Value *Mask = Builder.CreateLShr(LHS: AllOnes, RHS: Op1);
1616 return BinaryOperator::CreateAnd(V1: Mask, V2: X);
1617 }
1618
1619 // Transform (-1 << y) >> y to -1 >> y
1620 if (match(V: Op0, P: m_Shl(L: m_AllOnes(), R: m_Specific(V: Op1)))) {
1621 Constant *AllOnes = ConstantInt::getAllOnesValue(Ty);
1622 return BinaryOperator::CreateLShr(V1: AllOnes, V2: Op1);
1623 }
1624
1625 if (Instruction *Overflow = foldLShrOverflowBit(I))
1626 return Overflow;
1627
1628 // Transform ((pow2 << x) >> cttz(pow2 << y)) -> ((1 << x) >> y)
1629 Value *Shl0_Op0, *Shl0_Op1, *Shl1_Op1;
1630 BinaryOperator *Shl1;
1631 if (match(V: Op0, P: m_Shl(L: m_Value(V&: Shl0_Op0), R: m_Value(V&: Shl0_Op1))) &&
1632 match(V: Op1, P: m_Intrinsic<Intrinsic::cttz>(Op0: m_BinOp(I&: Shl1))) &&
1633 match(V: Shl1, P: m_Shl(L: m_Specific(V: Shl0_Op0), R: m_Value(V&: Shl1_Op1))) &&
1634 isKnownToBeAPowerOfTwo(V: Shl0_Op0, /*OrZero=*/true, CxtI: &I)) {
1635 auto *Shl0 = cast<BinaryOperator>(Val: Op0);
1636 bool HasNUW = Shl0->hasNoUnsignedWrap() && Shl1->hasNoUnsignedWrap();
1637 bool HasNSW = Shl0->hasNoSignedWrap() && Shl1->hasNoSignedWrap();
1638 if (HasNUW || HasNSW) {
1639 Value *NewShl = Builder.CreateShl(LHS: ConstantInt::get(Ty: Shl1->getType(), V: 1),
1640 RHS: Shl0_Op1, Name: "", HasNUW, HasNSW);
1641 return BinaryOperator::CreateLShr(V1: NewShl, V2: Shl1_Op1);
1642 }
1643 }
1644 return nullptr;
1645}
1646
1647Instruction *
1648InstCombinerImpl::foldVariableSignZeroExtensionOfVariableHighBitExtract(
1649 BinaryOperator &OldAShr) {
1650 assert(OldAShr.getOpcode() == Instruction::AShr &&
1651 "Must be called with arithmetic right-shift instruction only.");
1652
1653 // Check that constant C is a splat of the element-wise bitwidth of V.
1654 auto BitWidthSplat = [](Constant *C, Value *V) {
1655 return match(
1656 V: C, P: m_SpecificInt_ICMP(Predicate: ICmpInst::Predicate::ICMP_EQ,
1657 Threshold: APInt(C->getType()->getScalarSizeInBits(),
1658 V->getType()->getScalarSizeInBits())));
1659 };
1660
1661 // It should look like variable-length sign-extension on the outside:
1662 // (Val << (bitwidth(Val)-Nbits)) a>> (bitwidth(Val)-Nbits)
1663 Value *NBits;
1664 Instruction *MaybeTrunc;
1665 Constant *C1, *C2;
1666 if (!match(V: &OldAShr,
1667 P: m_AShr(L: m_Shl(L: m_Instruction(I&: MaybeTrunc),
1668 R: m_ZExtOrSelf(Op: m_Sub(L: m_Constant(C&: C1),
1669 R: m_ZExtOrSelf(Op: m_Value(V&: NBits))))),
1670 R: m_ZExtOrSelf(Op: m_Sub(L: m_Constant(C&: C2),
1671 R: m_ZExtOrSelf(Op: m_Deferred(V: NBits)))))) ||
1672 !BitWidthSplat(C1, &OldAShr) || !BitWidthSplat(C2, &OldAShr))
1673 return nullptr;
1674
1675 // There may or may not be a truncation after outer two shifts.
1676 Instruction *HighBitExtract;
1677 match(V: MaybeTrunc, P: m_TruncOrSelf(Op: m_Instruction(I&: HighBitExtract)));
1678 bool HadTrunc = MaybeTrunc != HighBitExtract;
1679
1680 // And finally, the innermost part of the pattern must be a right-shift.
1681 Value *X, *NumLowBitsToSkip;
1682 if (!match(V: HighBitExtract, P: m_Shr(L: m_Value(V&: X), R: m_Value(V&: NumLowBitsToSkip))))
1683 return nullptr;
1684
1685 // Said right-shift must extract high NBits bits - C0 must be it's bitwidth.
1686 Constant *C0;
1687 if (!match(V: NumLowBitsToSkip,
1688 P: m_ZExtOrSelf(
1689 Op: m_Sub(L: m_Constant(C&: C0), R: m_ZExtOrSelf(Op: m_Specific(V: NBits))))) ||
1690 !BitWidthSplat(C0, HighBitExtract))
1691 return nullptr;
1692
1693 // Since the NBits is identical for all shifts, if the outermost and
1694 // innermost shifts are identical, then outermost shifts are redundant.
1695 // If we had truncation, do keep it though.
1696 if (HighBitExtract->getOpcode() == OldAShr.getOpcode())
1697 return replaceInstUsesWith(I&: OldAShr, V: MaybeTrunc);
1698
1699 // Else, if there was a truncation, then we need to ensure that one
1700 // instruction will go away.
1701 if (HadTrunc && !match(V: &OldAShr, P: m_c_BinOp(L: m_OneUse(SubPattern: m_Value()), R: m_Value())))
1702 return nullptr;
1703
1704 // Finally, bypass two innermost shifts, and perform the outermost shift on
1705 // the operands of the innermost shift.
1706 Instruction *NewAShr =
1707 BinaryOperator::Create(Op: OldAShr.getOpcode(), S1: X, S2: NumLowBitsToSkip);
1708 NewAShr->copyIRFlags(V: HighBitExtract); // We can preserve 'exact'-ness.
1709 if (!HadTrunc)
1710 return NewAShr;
1711
1712 Builder.Insert(I: NewAShr);
1713 return TruncInst::CreateTruncOrBitCast(S: NewAShr, Ty: OldAShr.getType());
1714}
1715
1716Instruction *InstCombinerImpl::visitAShr(BinaryOperator &I) {
1717 if (Value *V = simplifyAShrInst(Op0: I.getOperand(i_nocapture: 0), Op1: I.getOperand(i_nocapture: 1), IsExact: I.isExact(),
1718 Q: SQ.getWithInstruction(I: &I)))
1719 return replaceInstUsesWith(I, V);
1720
1721 if (Instruction *X = foldVectorBinop(Inst&: I))
1722 return X;
1723
1724 if (Instruction *R = commonShiftTransforms(I))
1725 return R;
1726
1727 Value *Op0 = I.getOperand(i_nocapture: 0), *Op1 = I.getOperand(i_nocapture: 1);
1728 Type *Ty = I.getType();
1729 unsigned BitWidth = Ty->getScalarSizeInBits();
1730 const APInt *ShAmtAPInt;
1731 if (match(V: Op1, P: m_APInt(Res&: ShAmtAPInt)) && ShAmtAPInt->ult(RHS: BitWidth)) {
1732 unsigned ShAmt = ShAmtAPInt->getZExtValue();
1733
1734 // If the shift amount equals the difference in width of the destination
1735 // and source scalar types:
1736 // ashr (shl (zext X), C), C --> sext X
1737 Value *X;
1738 if (match(V: Op0, P: m_Shl(L: m_ZExt(Op: m_Value(V&: X)), R: m_Specific(V: Op1))) &&
1739 ShAmt == BitWidth - X->getType()->getScalarSizeInBits())
1740 return new SExtInst(X, Ty);
1741
1742 // We can't handle (X << C1) >>s C2. It shifts arbitrary bits in. However,
1743 // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits.
1744 const APInt *ShOp1;
1745 if (match(V: Op0, P: m_NSWShl(L: m_Value(V&: X), R: m_APInt(Res&: ShOp1))) &&
1746 ShOp1->ult(RHS: BitWidth)) {
1747 unsigned ShlAmt = ShOp1->getZExtValue();
1748 if (ShlAmt < ShAmt) {
1749 // (X <<nsw C1) >>s C2 --> X >>s (C2 - C1)
1750 Constant *ShiftDiff = ConstantInt::get(Ty, V: ShAmt - ShlAmt);
1751 auto *NewAShr = BinaryOperator::CreateAShr(V1: X, V2: ShiftDiff);
1752 NewAShr->setIsExact(I.isExact());
1753 return NewAShr;
1754 }
1755 if (ShlAmt > ShAmt) {
1756 // (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2)
1757 Constant *ShiftDiff = ConstantInt::get(Ty, V: ShlAmt - ShAmt);
1758 auto *NewShl = BinaryOperator::Create(Op: Instruction::Shl, S1: X, S2: ShiftDiff);
1759 NewShl->setHasNoSignedWrap(true);
1760 return NewShl;
1761 }
1762 }
1763
1764 if (match(V: Op0, P: m_AShr(L: m_Value(V&: X), R: m_APInt(Res&: ShOp1))) &&
1765 ShOp1->ult(RHS: BitWidth)) {
1766 unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
1767 // Oversized arithmetic shifts replicate the sign bit.
1768 AmtSum = std::min(a: AmtSum, b: BitWidth - 1);
1769 // (X >>s C1) >>s C2 --> X >>s (C1 + C2)
1770 return BinaryOperator::CreateAShr(V1: X, V2: ConstantInt::get(Ty, V: AmtSum));
1771 }
1772
1773 if (match(V: Op0, P: m_OneUse(SubPattern: m_SExt(Op: m_Value(V&: X)))) &&
1774 (Ty->isVectorTy() || shouldChangeType(From: Ty, To: X->getType()))) {
1775 // ashr (sext X), C --> sext (ashr X, C')
1776 Type *SrcTy = X->getType();
1777 ShAmt = std::min(a: ShAmt, b: SrcTy->getScalarSizeInBits() - 1);
1778 Value *NewSh = Builder.CreateAShr(LHS: X, RHS: ConstantInt::get(Ty: SrcTy, V: ShAmt));
1779 return new SExtInst(NewSh, Ty);
1780 }
1781
1782 if (ShAmt == BitWidth - 1) {
1783 // ashr i32 or(X,-X), 31 --> sext (X != 0)
1784 if (match(V: Op0, P: m_OneUse(SubPattern: m_c_Or(L: m_Neg(V: m_Value(V&: X)), R: m_Deferred(V: X)))))
1785 return new SExtInst(Builder.CreateIsNotNull(Arg: X), Ty);
1786
1787 // ashr i32 (X -nsw Y), 31 --> sext (X < Y)
1788 Value *Y;
1789 if (match(V: Op0, P: m_OneUse(SubPattern: m_NSWSub(L: m_Value(V&: X), R: m_Value(V&: Y)))))
1790 return new SExtInst(Builder.CreateICmpSLT(LHS: X, RHS: Y), Ty);
1791
1792 // ashr iN (X - 1) & ~X, N-1 --> sext (X == 0)
1793 if (match(V: Op0, P: m_OneUse(SubPattern: m_c_And(L: m_Add(L: m_Value(V&: X), R: m_AllOnes()),
1794 R: m_Not(V: m_Deferred(V: X))))))
1795 return new SExtInst(Builder.CreateIsNull(Arg: X), Ty);
1796 }
1797
1798 const APInt *MulC;
1799 if (match(V: Op0, P: m_OneUse(SubPattern: m_NSWMul(L: m_Value(V&: X), R: m_APInt(Res&: MulC)))) &&
1800 (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1801 MulC->logBase2() == ShAmt &&
1802 (ShAmt < BitWidth - 1))) /* Minus 1 for the sign bit */ {
1803
1804 // ashr (mul nsw (X, 2^N + 1)), N -> add nsw (X, ashr(X, N))
1805 auto *NewAdd = BinaryOperator::CreateNSWAdd(
1806 V1: X,
1807 V2: Builder.CreateAShr(LHS: X, RHS: ConstantInt::get(Ty, V: ShAmt), Name: "", isExact: I.isExact()));
1808 NewAdd->setHasNoUnsignedWrap(
1809 cast<OverflowingBinaryOperator>(Val: Op0)->hasNoUnsignedWrap());
1810 return NewAdd;
1811 }
1812 }
1813
1814 const SimplifyQuery Q = SQ.getWithInstruction(I: &I);
1815 if (setShiftFlags(I, Q))
1816 return &I;
1817
1818 // Prefer `-(x & 1)` over `(x << (bitwidth(x)-1)) a>> (bitwidth(x)-1)`
1819 // as the pattern to splat the lowest bit.
1820 // FIXME: iff X is already masked, we don't need the one-use check.
1821 Value *X;
1822 if (match(V: Op1, P: m_SpecificIntAllowPoison(V: BitWidth - 1)) &&
1823 match(V: Op0, P: m_OneUse(SubPattern: m_Shl(L: m_Value(V&: X),
1824 R: m_SpecificIntAllowPoison(V: BitWidth - 1))))) {
1825 Constant *Mask = ConstantInt::get(Ty, V: 1);
1826 // Retain the knowledge about the ignored lanes.
1827 Mask = Constant::mergeUndefsWith(
1828 C: Constant::mergeUndefsWith(C: Mask, Other: cast<Constant>(Val: Op1)),
1829 Other: cast<Constant>(Val: cast<Instruction>(Val: Op0)->getOperand(i: 1)));
1830 X = Builder.CreateAnd(LHS: X, RHS: Mask);
1831 return BinaryOperator::CreateNeg(Op: X);
1832 }
1833
1834 if (Instruction *R = foldVariableSignZeroExtensionOfVariableHighBitExtract(OldAShr&: I))
1835 return R;
1836
1837 // See if we can turn a signed shr into an unsigned shr.
1838 if (MaskedValueIsZero(V: Op0, Mask: APInt::getSignMask(BitWidth), CxtI: &I)) {
1839 Instruction *Lshr = BinaryOperator::CreateLShr(V1: Op0, V2: Op1);
1840 Lshr->setIsExact(I.isExact());
1841 return Lshr;
1842 }
1843
1844 // ashr (xor %x, -1), %y --> xor (ashr %x, %y), -1
1845 if (match(V: Op0, P: m_OneUse(SubPattern: m_Not(V: m_Value(V&: X))))) {
1846 // Note that we must drop 'exact'-ness of the shift!
1847 // Note that we can't keep undef's in -1 vector constant!
1848 auto *NewAShr = Builder.CreateAShr(LHS: X, RHS: Op1, Name: Op0->getName() + ".not");
1849 return BinaryOperator::CreateNot(Op: NewAShr);
1850 }
1851
1852 return nullptr;
1853}
1854