1 //===- InstCombineShifts.cpp ----------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the visitShl, visitLShr, and visitAShr functions.
12 //===----------------------------------------------------------------------===//
14 #include "InstCombineInternal.h"
15 #include "llvm/Analysis/ConstantFolding.h"
16 #include "llvm/Analysis/InstructionSimplify.h"
17 #include "llvm/IR/IntrinsicInst.h"
18 #include "llvm/IR/PatternMatch.h"
20 using namespace PatternMatch;
22 #define DEBUG_TYPE "instcombine"
24 Instruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) {
25 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
26 assert(Op0->getType() == Op1->getType());
28 // See if we can fold away this shift.
29 if (SimplifyDemandedInstructionBits(I))
32 // Try to fold constant and into select arguments.
33 if (isa<Constant>(Op0))
34 if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
35 if (Instruction *R = FoldOpIntoSelect(I, SI))
38 if (Constant *CUI = dyn_cast<Constant>(Op1))
39 if (Instruction *Res = FoldShiftByConstant(Op0, CUI, I))
42 // (C1 shift (A add C2)) -> (C1 shift C2) shift A)
43 // iff A and C2 are both positive.
46 if (match(Op0, m_Constant()) && match(Op1, m_Add(m_Value(A), m_Constant(C))))
47 if (isKnownNonNegative(A, DL) && isKnownNonNegative(C, DL))
48 return BinaryOperator::Create(
49 I.getOpcode(), Builder->CreateBinOp(I.getOpcode(), Op0, C), A);
51 // X shift (A srem B) -> X shift (A and B-1) iff B is a power of 2.
52 // Because shifts by negative values (which could occur if A were negative)
55 if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Power2(B)))) {
56 // FIXME: Should this get moved into SimplifyDemandedBits by saying we don't
57 // demand the sign bit (and many others) here??
58 Value *Rem = Builder->CreateAnd(A, ConstantInt::get(I.getType(), *B-1),
67 /// Return true if we can simplify two logical (either left or right) shifts
68 /// that have constant shift amounts: OuterShift (InnerShift X, C1), C2.
69 static bool canEvaluateShiftedShift(unsigned OuterShAmt, bool IsOuterShl,
70 Instruction *InnerShift, InstCombiner &IC,
72 assert(InnerShift->isLogicalShift() && "Unexpected instruction type");
74 // We need constant scalar or constant splat shifts.
75 const APInt *InnerShiftConst;
76 if (!match(InnerShift->getOperand(1), m_APInt(InnerShiftConst)))
79 // Two logical shifts in the same direction:
80 // shl (shl X, C1), C2 --> shl X, C1 + C2
81 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
82 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
83 if (IsInnerShl == IsOuterShl)
86 // Equal shift amounts in opposite directions become bitwise 'and':
87 // lshr (shl X, C), C --> and X, C'
88 // shl (lshr X, C), C --> and X, C'
89 unsigned InnerShAmt = InnerShiftConst->getZExtValue();
90 if (InnerShAmt == OuterShAmt)
93 // If the 2nd shift is bigger than the 1st, we can fold:
94 // lshr (shl X, C1), C2 --> and (shl X, C1 - C2), C3
95 // shl (lshr X, C1), C2 --> and (lshr X, C1 - C2), C3
96 // but it isn't profitable unless we know the and'd out bits are already zero.
97 // Also, check that the inner shift is valid (less than the type width) or
98 // we'll crash trying to produce the bit mask for the 'and'.
99 unsigned TypeWidth = InnerShift->getType()->getScalarSizeInBits();
100 if (InnerShAmt > OuterShAmt && InnerShAmt < TypeWidth) {
102 IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt;
103 APInt Mask = APInt::getLowBitsSet(TypeWidth, OuterShAmt) << MaskShift;
104 if (IC.MaskedValueIsZero(InnerShift->getOperand(0), Mask, 0, CxtI))
111 /// See if we can compute the specified value, but shifted logically to the left
112 /// or right by some number of bits. This should return true if the expression
113 /// can be computed for the same cost as the current expression tree. This is
114 /// used to eliminate extraneous shifting from things like:
115 /// %C = shl i128 %A, 64
116 /// %D = shl i128 %B, 96
117 /// %E = or i128 %C, %D
118 /// %F = lshr i128 %E, 64
119 /// where the client will ask if E can be computed shifted right by 64-bits. If
120 /// this succeeds, getShiftedValue() will be called to produce the value.
121 static bool canEvaluateShifted(Value *V, unsigned NumBits, bool IsLeftShift,
122 InstCombiner &IC, Instruction *CxtI) {
123 // We can always evaluate constants shifted.
124 if (isa<Constant>(V))
127 Instruction *I = dyn_cast<Instruction>(V);
128 if (!I) return false;
130 // If this is the opposite shift, we can directly reuse the input of the shift
131 // if the needed bits are already zero in the input. This allows us to reuse
132 // the value which means that we don't care if the shift has multiple uses.
133 // TODO: Handle opposite shift by exact value.
134 ConstantInt *CI = nullptr;
135 if ((IsLeftShift && match(I, m_LShr(m_Value(), m_ConstantInt(CI)))) ||
136 (!IsLeftShift && match(I, m_Shl(m_Value(), m_ConstantInt(CI))))) {
137 if (CI->getZExtValue() == NumBits) {
138 // TODO: Check that the input bits are already zero with MaskedValueIsZero
140 // If this is a truncate of a logical shr, we can truncate it to a smaller
141 // lshr iff we know that the bits we would otherwise be shifting in are
143 uint32_t OrigBitWidth = OrigTy->getScalarSizeInBits();
144 uint32_t BitWidth = Ty->getScalarSizeInBits();
145 if (MaskedValueIsZero(I->getOperand(0),
146 APInt::getHighBitsSet(OrigBitWidth, OrigBitWidth-BitWidth)) &&
147 CI->getLimitedValue(BitWidth) < BitWidth) {
148 return CanEvaluateTruncated(I->getOperand(0), Ty);
155 // We can't mutate something that has multiple uses: doing so would
156 // require duplicating the instruction in general, which isn't profitable.
157 if (!I->hasOneUse()) return false;
159 switch (I->getOpcode()) {
160 default: return false;
161 case Instruction::And:
162 case Instruction::Or:
163 case Instruction::Xor:
164 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
165 return canEvaluateShifted(I->getOperand(0), NumBits, IsLeftShift, IC, I) &&
166 canEvaluateShifted(I->getOperand(1), NumBits, IsLeftShift, IC, I);
168 case Instruction::Shl:
169 case Instruction::LShr:
170 return canEvaluateShiftedShift(NumBits, IsLeftShift, I, IC, CxtI);
172 case Instruction::Select: {
173 SelectInst *SI = cast<SelectInst>(I);
174 Value *TrueVal = SI->getTrueValue();
175 Value *FalseVal = SI->getFalseValue();
176 return canEvaluateShifted(TrueVal, NumBits, IsLeftShift, IC, SI) &&
177 canEvaluateShifted(FalseVal, NumBits, IsLeftShift, IC, SI);
179 case Instruction::PHI: {
180 // We can change a phi if we can change all operands. Note that we never
181 // get into trouble with cyclic PHIs here because we only consider
182 // instructions with a single use.
183 PHINode *PN = cast<PHINode>(I);
184 for (Value *IncValue : PN->incoming_values())
185 if (!canEvaluateShifted(IncValue, NumBits, IsLeftShift, IC, PN))
192 /// Fold OuterShift (InnerShift X, C1), C2.
193 /// See canEvaluateShiftedShift() for the constraints on these instructions.
194 static Value *foldShiftedShift(BinaryOperator *InnerShift, unsigned OuterShAmt,
196 InstCombiner::BuilderTy &Builder) {
197 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
198 Type *ShType = InnerShift->getType();
199 unsigned TypeWidth = ShType->getScalarSizeInBits();
201 // We only accept shifts-by-a-constant in canEvaluateShifted().
203 match(InnerShift->getOperand(1), m_APInt(C1));
204 unsigned InnerShAmt = C1->getZExtValue();
206 // Change the shift amount and clear the appropriate IR flags.
207 auto NewInnerShift = [&](unsigned ShAmt) {
208 InnerShift->setOperand(1, ConstantInt::get(ShType, ShAmt));
210 InnerShift->setHasNoUnsignedWrap(false);
211 InnerShift->setHasNoSignedWrap(false);
213 InnerShift->setIsExact(false);
218 // Two logical shifts in the same direction:
219 // shl (shl X, C1), C2 --> shl X, C1 + C2
220 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
221 if (IsInnerShl == IsOuterShl) {
222 // If this is an oversized composite shift, then unsigned shifts get 0.
223 if (InnerShAmt + OuterShAmt >= TypeWidth)
224 return Constant::getNullValue(ShType);
226 return NewInnerShift(InnerShAmt + OuterShAmt);
229 // Equal shift amounts in opposite directions become bitwise 'and':
230 // lshr (shl X, C), C --> and X, C'
231 // shl (lshr X, C), C --> and X, C'
232 if (InnerShAmt == OuterShAmt) {
233 APInt Mask = IsInnerShl
234 ? APInt::getLowBitsSet(TypeWidth, TypeWidth - OuterShAmt)
235 : APInt::getHighBitsSet(TypeWidth, TypeWidth - OuterShAmt);
236 Value *And = Builder.CreateAnd(InnerShift->getOperand(0),
237 ConstantInt::get(ShType, Mask));
238 if (auto *AndI = dyn_cast<Instruction>(And)) {
239 AndI->moveBefore(InnerShift);
240 AndI->takeName(InnerShift);
245 assert(InnerShAmt > OuterShAmt &&
246 "Unexpected opposite direction logical shift pair");
248 // In general, we would need an 'and' for this transform, but
249 // canEvaluateShiftedShift() guarantees that the masked-off bits are not used.
250 // lshr (shl X, C1), C2 --> shl X, C1 - C2
251 // shl (lshr X, C1), C2 --> lshr X, C1 - C2
252 return NewInnerShift(InnerShAmt - OuterShAmt);
255 /// When canEvaluateShifted() returns true for an expression, this function
256 /// inserts the new computation that produces the shifted value.
257 static Value *getShiftedValue(Value *V, unsigned NumBits, bool isLeftShift,
258 InstCombiner &IC, const DataLayout &DL) {
259 // We can always evaluate constants shifted.
260 if (Constant *C = dyn_cast<Constant>(V)) {
262 V = IC.Builder->CreateShl(C, NumBits);
264 V = IC.Builder->CreateLShr(C, NumBits);
265 // If we got a constantexpr back, try to simplify it with TD info.
266 if (auto *C = dyn_cast<Constant>(V))
268 ConstantFoldConstant(C, DL, &IC.getTargetLibraryInfo()))
273 Instruction *I = cast<Instruction>(V);
276 switch (I->getOpcode()) {
277 default: llvm_unreachable("Inconsistency with CanEvaluateShifted");
278 case Instruction::And:
279 case Instruction::Or:
280 case Instruction::Xor:
281 // Bitwise operators can all arbitrarily be arbitrarily evaluated shifted.
283 0, getShiftedValue(I->getOperand(0), NumBits, isLeftShift, IC, DL));
285 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
288 case Instruction::Shl:
289 case Instruction::LShr:
290 return foldShiftedShift(cast<BinaryOperator>(I), NumBits, isLeftShift,
293 case Instruction::Select:
295 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
297 2, getShiftedValue(I->getOperand(2), NumBits, isLeftShift, IC, DL));
299 case Instruction::PHI: {
300 // We can change a phi if we can change all operands. Note that we never
301 // get into trouble with cyclic PHIs here because we only consider
302 // instructions with a single use.
303 PHINode *PN = cast<PHINode>(I);
304 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
305 PN->setIncomingValue(i, getShiftedValue(PN->getIncomingValue(i), NumBits,
306 isLeftShift, IC, DL));
312 Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, Constant *Op1,
314 bool isLeftShift = I.getOpcode() == Instruction::Shl;
317 if (!match(Op1, m_APInt(Op1C)))
320 // See if we can propagate this shift into the input, this covers the trivial
321 // cast of lshr(shl(x,c1),c2) as well as other more complex cases.
322 if (I.getOpcode() != Instruction::AShr &&
323 canEvaluateShifted(Op0, Op1C->getZExtValue(), isLeftShift, *this, &I)) {
324 DEBUG(dbgs() << "ICE: GetShiftedValue propagating shift through expression"
325 " to eliminate shift:\n IN: " << *Op0 << "\n SH: " << I <<"\n");
327 return replaceInstUsesWith(
328 I, getShiftedValue(Op0, Op1C->getZExtValue(), isLeftShift, *this, DL));
331 // See if we can simplify any instructions used by the instruction whose sole
332 // purpose is to compute bits we don't care about.
333 unsigned TypeBits = Op0->getType()->getScalarSizeInBits();
335 assert(!Op1C->uge(TypeBits) &&
336 "Shift over the type width should have been removed already");
338 if (Instruction *FoldedShift = foldOpWithConstantIntoOperand(I))
341 // Fold shift2(trunc(shift1(x,c1)), c2) -> trunc(shift2(shift1(x,c1),c2))
342 if (TruncInst *TI = dyn_cast<TruncInst>(Op0)) {
343 Instruction *TrOp = dyn_cast<Instruction>(TI->getOperand(0));
344 // If 'shift2' is an ashr, we would have to get the sign bit into a funny
345 // place. Don't try to do this transformation in this case. Also, we
346 // require that the input operand is a shift-by-constant so that we have
347 // confidence that the shifts will get folded together. We could do this
348 // xform in more cases, but it is unlikely to be profitable.
349 if (TrOp && I.isLogicalShift() && TrOp->isShift() &&
350 isa<ConstantInt>(TrOp->getOperand(1))) {
351 // Okay, we'll do this xform. Make the shift of shift.
353 ConstantExpr::getZExt(cast<Constant>(Op1), TrOp->getType());
354 // (shift2 (shift1 & 0x00FF), c2)
355 Value *NSh = Builder->CreateBinOp(I.getOpcode(), TrOp, ShAmt,I.getName());
357 // For logical shifts, the truncation has the effect of making the high
358 // part of the register be zeros. Emulate this by inserting an AND to
359 // clear the top bits as needed. This 'and' will usually be zapped by
360 // other xforms later if dead.
361 unsigned SrcSize = TrOp->getType()->getScalarSizeInBits();
362 unsigned DstSize = TI->getType()->getScalarSizeInBits();
363 APInt MaskV(APInt::getLowBitsSet(SrcSize, DstSize));
365 // The mask we constructed says what the trunc would do if occurring
366 // between the shifts. We want to know the effect *after* the second
367 // shift. We know that it is a logical shift by a constant, so adjust the
368 // mask as appropriate.
369 if (I.getOpcode() == Instruction::Shl)
370 MaskV <<= Op1C->getZExtValue();
372 assert(I.getOpcode() == Instruction::LShr && "Unknown logical shift");
373 MaskV.lshrInPlace(Op1C->getZExtValue());
377 Value *And = Builder->CreateAnd(NSh,
378 ConstantInt::get(I.getContext(), MaskV),
381 // Return the value truncated to the interesting size.
382 return new TruncInst(And, I.getType());
386 if (Op0->hasOneUse()) {
387 if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
388 // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C)
391 switch (Op0BO->getOpcode()) {
393 case Instruction::Add:
394 case Instruction::And:
395 case Instruction::Or:
396 case Instruction::Xor: {
397 // These operators commute.
398 // Turn (Y + (X >> C)) << C -> (X + (Y << C)) & (~0 << C)
399 if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() &&
400 match(Op0BO->getOperand(1), m_Shr(m_Value(V1),
402 Value *YS = // (Y << C)
403 Builder->CreateShl(Op0BO->getOperand(0), Op1, Op0BO->getName());
405 Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), YS, V1,
406 Op0BO->getOperand(1)->getName());
407 unsigned Op1Val = Op1C->getLimitedValue(TypeBits);
409 APInt Bits = APInt::getHighBitsSet(TypeBits, TypeBits - Op1Val);
410 Constant *Mask = ConstantInt::get(I.getContext(), Bits);
411 if (VectorType *VT = dyn_cast<VectorType>(X->getType()))
412 Mask = ConstantVector::getSplat(VT->getNumElements(), Mask);
413 return BinaryOperator::CreateAnd(X, Mask);
416 // Turn (Y + ((X >> C) & CC)) << C -> ((X & (CC << C)) + (Y << C))
417 Value *Op0BOOp1 = Op0BO->getOperand(1);
418 if (isLeftShift && Op0BOOp1->hasOneUse() &&
420 m_And(m_OneUse(m_Shr(m_Value(V1), m_Specific(Op1))),
421 m_ConstantInt(CC)))) {
422 Value *YS = // (Y << C)
423 Builder->CreateShl(Op0BO->getOperand(0), Op1,
426 Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1),
427 V1->getName()+".mask");
428 return BinaryOperator::Create(Op0BO->getOpcode(), YS, XM);
433 case Instruction::Sub: {
434 // Turn ((X >> C) + Y) << C -> (X + (Y << C)) & (~0 << C)
435 if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
436 match(Op0BO->getOperand(0), m_Shr(m_Value(V1),
438 Value *YS = // (Y << C)
439 Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName());
441 Value *X = Builder->CreateBinOp(Op0BO->getOpcode(), V1, YS,
442 Op0BO->getOperand(0)->getName());
443 unsigned Op1Val = Op1C->getLimitedValue(TypeBits);
445 APInt Bits = APInt::getHighBitsSet(TypeBits, TypeBits - Op1Val);
446 Constant *Mask = ConstantInt::get(I.getContext(), Bits);
447 if (VectorType *VT = dyn_cast<VectorType>(X->getType()))
448 Mask = ConstantVector::getSplat(VT->getNumElements(), Mask);
449 return BinaryOperator::CreateAnd(X, Mask);
452 // Turn (((X >> C)&CC) + Y) << C -> (X + (Y << C)) & (CC << C)
453 if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
454 match(Op0BO->getOperand(0),
455 m_And(m_OneUse(m_Shr(m_Value(V1), m_Value(V2))),
456 m_ConstantInt(CC))) && V2 == Op1) {
457 Value *YS = // (Y << C)
458 Builder->CreateShl(Op0BO->getOperand(1), Op1, Op0BO->getName());
460 Value *XM = Builder->CreateAnd(V1, ConstantExpr::getShl(CC, Op1),
461 V1->getName()+".mask");
463 return BinaryOperator::Create(Op0BO->getOpcode(), XM, YS);
471 // If the operand is a bitwise operator with a constant RHS, and the
472 // shift is the only use, we can pull it out of the shift.
473 if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
474 bool isValid = true; // Valid only for And, Or, Xor
475 bool highBitSet = false; // Transform if high bit of constant set?
477 switch (Op0BO->getOpcode()) {
478 default: isValid = false; break; // Do not perform transform!
479 case Instruction::Add:
480 isValid = isLeftShift;
482 case Instruction::Or:
483 case Instruction::Xor:
486 case Instruction::And:
491 // If this is a signed shift right, and the high bit is modified
492 // by the logical operation, do not perform the transformation.
493 // The highBitSet boolean indicates the value of the high bit of
494 // the constant which would cause it to be modified for this
497 if (isValid && I.getOpcode() == Instruction::AShr)
498 isValid = Op0C->getValue()[TypeBits-1] == highBitSet;
501 Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, Op1);
504 Builder->CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1);
505 NewShift->takeName(Op0BO);
507 return BinaryOperator::Create(Op0BO->getOpcode(), NewShift,
517 Instruction *InstCombiner::visitShl(BinaryOperator &I) {
518 if (Value *V = SimplifyVectorOp(I))
519 return replaceInstUsesWith(I, V);
521 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
522 if (Value *V = SimplifyShlInst(Op0, Op1, I.hasNoSignedWrap(),
523 I.hasNoUnsignedWrap(), SQ))
524 return replaceInstUsesWith(I, V);
526 if (Instruction *V = commonShiftTransforms(I))
529 const APInt *ShAmtAPInt;
530 if (match(Op1, m_APInt(ShAmtAPInt))) {
531 unsigned ShAmt = ShAmtAPInt->getZExtValue();
532 unsigned BitWidth = I.getType()->getScalarSizeInBits();
533 Type *Ty = I.getType();
535 // shl (zext X), ShAmt --> zext (shl X, ShAmt)
536 // This is only valid if X would have zeros shifted out.
538 if (match(Op0, m_ZExt(m_Value(X)))) {
539 unsigned SrcWidth = X->getType()->getScalarSizeInBits();
540 if (ShAmt < SrcWidth &&
541 MaskedValueIsZero(X, APInt::getHighBitsSet(SrcWidth, ShAmt), 0, &I))
542 return new ZExtInst(Builder->CreateShl(X, ShAmt), Ty);
545 // (X >>u C) << C --> X & (-1 << C)
546 if (match(Op0, m_LShr(m_Value(X), m_Specific(Op1)))) {
547 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmt));
548 return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));
551 // Be careful about hiding shl instructions behind bit masks. They are used
552 // to represent multiplies by a constant, and it is important that simple
553 // arithmetic expressions are still recognizable by scalar evolution.
554 // The inexact versions are deferred to DAGCombine, so we don't hide shl
555 // behind a bit mask.
557 if (match(Op0, m_CombineOr(m_Exact(m_LShr(m_Value(X), m_APInt(ShOp1))),
558 m_Exact(m_AShr(m_Value(X), m_APInt(ShOp1)))))) {
559 unsigned ShrAmt = ShOp1->getZExtValue();
560 if (ShrAmt < ShAmt) {
561 // If C1 < C2: (X >>?,exact C1) << C2 --> X << (C2 - C1)
562 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShrAmt);
563 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
564 NewShl->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
565 NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
568 if (ShrAmt > ShAmt) {
569 // If C1 > C2: (X >>?exact C1) << C2 --> X >>?exact (C1 - C2)
570 Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmt);
571 auto *NewShr = BinaryOperator::Create(
572 cast<BinaryOperator>(Op0)->getOpcode(), X, ShiftDiff);
573 NewShr->setIsExact(true);
578 if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1)))) {
579 unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
580 // Oversized shifts are simplified to zero in InstSimplify.
581 if (AmtSum < BitWidth)
582 // (X << C1) << C2 --> X << (C1 + C2)
583 return BinaryOperator::CreateShl(X, ConstantInt::get(Ty, AmtSum));
586 // If the shifted-out value is known-zero, then this is a NUW shift.
587 if (!I.hasNoUnsignedWrap() &&
588 MaskedValueIsZero(Op0, APInt::getHighBitsSet(BitWidth, ShAmt), 0, &I)) {
589 I.setHasNoUnsignedWrap();
593 // If the shifted-out value is all signbits, then this is a NSW shift.
594 if (!I.hasNoSignedWrap() && ComputeNumSignBits(Op0, 0, &I) > ShAmt) {
595 I.setHasNoSignedWrap();
601 if (match(Op1, m_Constant(C1))) {
604 // (C2 << X) << C1 --> (C2 << C1) << X
605 if (match(Op0, m_OneUse(m_Shl(m_Constant(C2), m_Value(X)))))
606 return BinaryOperator::CreateShl(ConstantExpr::getShl(C2, C1), X);
608 // (X * C2) << C1 --> X * (C2 << C1)
609 if (match(Op0, m_Mul(m_Value(X), m_Constant(C2))))
610 return BinaryOperator::CreateMul(X, ConstantExpr::getShl(C2, C1));
616 Instruction *InstCombiner::visitLShr(BinaryOperator &I) {
617 if (Value *V = SimplifyVectorOp(I))
618 return replaceInstUsesWith(I, V);
620 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
621 if (Value *V = SimplifyLShrInst(Op0, Op1, I.isExact(), SQ))
622 return replaceInstUsesWith(I, V);
624 if (Instruction *R = commonShiftTransforms(I))
627 Type *Ty = I.getType();
628 const APInt *ShAmtAPInt;
629 if (match(Op1, m_APInt(ShAmtAPInt))) {
630 unsigned ShAmt = ShAmtAPInt->getZExtValue();
631 unsigned BitWidth = Ty->getScalarSizeInBits();
632 auto *II = dyn_cast<IntrinsicInst>(Op0);
633 if (II && isPowerOf2_32(BitWidth) && Log2_32(BitWidth) == ShAmt &&
634 (II->getIntrinsicID() == Intrinsic::ctlz ||
635 II->getIntrinsicID() == Intrinsic::cttz ||
636 II->getIntrinsicID() == Intrinsic::ctpop)) {
637 // ctlz.i32(x)>>5 --> zext(x == 0)
638 // cttz.i32(x)>>5 --> zext(x == 0)
639 // ctpop.i32(x)>>5 --> zext(x == -1)
640 bool IsPop = II->getIntrinsicID() == Intrinsic::ctpop;
641 Constant *RHS = ConstantInt::getSigned(Ty, IsPop ? -1 : 0);
642 Value *Cmp = Builder->CreateICmpEQ(II->getArgOperand(0), RHS);
643 return new ZExtInst(Cmp, Ty);
648 if (match(Op0, m_Shl(m_Value(X), m_APInt(ShOp1)))) {
649 unsigned ShlAmt = ShOp1->getZExtValue();
650 if (ShlAmt < ShAmt) {
651 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt);
652 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
653 // (X <<nuw C1) >>u C2 --> X >>u (C2 - C1)
654 auto *NewLShr = BinaryOperator::CreateLShr(X, ShiftDiff);
655 NewLShr->setIsExact(I.isExact());
658 // (X << C1) >>u C2 --> (X >>u (C2 - C1)) & (-1 >> C2)
659 Value *NewLShr = Builder->CreateLShr(X, ShiftDiff, "", I.isExact());
660 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt));
661 return BinaryOperator::CreateAnd(NewLShr, ConstantInt::get(Ty, Mask));
663 if (ShlAmt > ShAmt) {
664 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt);
665 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
666 // (X <<nuw C1) >>u C2 --> X <<nuw (C1 - C2)
667 auto *NewShl = BinaryOperator::CreateShl(X, ShiftDiff);
668 NewShl->setHasNoUnsignedWrap(true);
671 // (X << C1) >>u C2 --> X << (C1 - C2) & (-1 >> C2)
672 Value *NewShl = Builder->CreateShl(X, ShiftDiff);
673 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt));
674 return BinaryOperator::CreateAnd(NewShl, ConstantInt::get(Ty, Mask));
676 assert(ShlAmt == ShAmt);
677 // (X << C) >>u C --> X & (-1 >>u C)
678 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmt));
679 return BinaryOperator::CreateAnd(X, ConstantInt::get(Ty, Mask));
682 if (match(Op0, m_LShr(m_Value(X), m_APInt(ShOp1)))) {
683 unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
684 // Oversized shifts are simplified to zero in InstSimplify.
685 if (AmtSum < BitWidth)
686 // (X >>u C1) >>u C2 --> X >>u (C1 + C2)
687 return BinaryOperator::CreateLShr(X, ConstantInt::get(Ty, AmtSum));
690 // If the shifted-out value is known-zero, then this is an exact shift.
692 MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), 0, &I)) {
700 Instruction *InstCombiner::visitAShr(BinaryOperator &I) {
701 if (Value *V = SimplifyVectorOp(I))
702 return replaceInstUsesWith(I, V);
704 Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
705 if (Value *V = SimplifyAShrInst(Op0, Op1, I.isExact(), SQ))
706 return replaceInstUsesWith(I, V);
708 if (Instruction *R = commonShiftTransforms(I))
711 Type *Ty = I.getType();
712 unsigned BitWidth = Ty->getScalarSizeInBits();
713 const APInt *ShAmtAPInt;
714 if (match(Op1, m_APInt(ShAmtAPInt))) {
715 unsigned ShAmt = ShAmtAPInt->getZExtValue();
717 // If the shift amount equals the difference in width of the destination
718 // and source scalar types:
719 // ashr (shl (zext X), C), C --> sext X
721 if (match(Op0, m_Shl(m_ZExt(m_Value(X)), m_Specific(Op1))) &&
722 ShAmt == BitWidth - X->getType()->getScalarSizeInBits())
723 return new SExtInst(X, Ty);
725 // We can't handle (X << C1) >>s C2. It shifts arbitrary bits in. However,
726 // we can handle (X <<nsw C1) >>s C2 since it only shifts in sign bits.
728 if (match(Op0, m_NSWShl(m_Value(X), m_APInt(ShOp1)))) {
729 unsigned ShlAmt = ShOp1->getZExtValue();
730 if (ShlAmt < ShAmt) {
731 // (X <<nsw C1) >>s C2 --> X >>s (C2 - C1)
732 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt);
733 auto *NewAShr = BinaryOperator::CreateAShr(X, ShiftDiff);
734 NewAShr->setIsExact(I.isExact());
737 if (ShlAmt > ShAmt) {
738 // (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2)
739 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt);
740 auto *NewShl = BinaryOperator::Create(Instruction::Shl, X, ShiftDiff);
741 NewShl->setHasNoSignedWrap(true);
746 if (match(Op0, m_AShr(m_Value(X), m_APInt(ShOp1)))) {
747 unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
748 // Oversized arithmetic shifts replicate the sign bit.
749 AmtSum = std::min(AmtSum, BitWidth - 1);
750 // (X >>s C1) >>s C2 --> X >>s (C1 + C2)
751 return BinaryOperator::CreateAShr(X, ConstantInt::get(Ty, AmtSum));
754 // If the shifted-out value is known-zero, then this is an exact shift.
756 MaskedValueIsZero(Op0, APInt::getLowBitsSet(BitWidth, ShAmt), 0, &I)) {
762 // See if we can turn a signed shr into an unsigned shr.
763 if (MaskedValueIsZero(Op0, APInt::getSignMask(BitWidth), 0, &I))
764 return BinaryOperator::CreateLShr(Op0, Op1);