Lines Matching +full:depth +full:- +full:wise
1 //===- InstCombineShifts.cpp ----------------------------------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
27 if (ShAmt0->getType() != ShAmt1->getType())
35 // (because 2 * (N-1) u<= iN -1), we have looked past extensions of
40 (Sh0->getType()->getScalarSizeInBits() - 1) +
41 (Sh1->getType()->getScalarSizeInBits() - 1);
43 APInt::getAllOnes(ShAmt0->getType()->getScalarSizeInBits());
57 // pattern has any 2 right-shifts that sum to 1 less than original bit width.
90 // ... and if it's not two right-shifts, we know the answer already.
95 // this pattern can be interpreted as a sign-bit-extraction.
96 Instruction::BinaryOps ShiftOpcode = Sh0->getOpcode();
97 bool IdenticalShOpcodes = Sh0->getOpcode() == Sh1->getOpcode();
102 // and for that one of the operands of the shift must be one-use,
114 unsigned NewShAmtBitWidth = NewShAmt->getType()->getScalarSizeInBits();
115 unsigned XBitWidth = X->getType()->getScalarSizeInBits();
119 return nullptr; // FIXME: could perform constant-folding.
121 // If there was a truncation, and we have a right-shift, we can only fold if
130 APInt(NewShAmtBitWidth, XBitWidth - 1))))
139 if (NewShAmt->getType() != X->getType()) {
141 X->getType(), SQ.DL);
154 NewShift->setHasNoUnsignedWrap(Sh0->hasNoUnsignedWrap() &&
155 Sh1->hasNoUnsignedWrap());
156 NewShift->setHasNoSignedWrap(Sh0->hasNoSignedWrap() &&
157 Sh1->hasNoSignedWrap());
159 NewShift->setIsExact(Sh0->isExact() && Sh1->isExact());
166 Ret = CastInst::Create(Instruction::Trunc, NewShift, Sh0->getType());
173 // left-shift of those bits, if none of the bits that are left after the final
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
187 // c,d,e,f) (ShiftShAmt-MaskShAmt) s>= 0 (i.e. ShiftShAmt u>= MaskShAmt)
192 assert(OuterShift->getOpcode() == Instruction::BinaryOps::Shl &&
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.
203 !Trunc->hasOneUse())
206 Type *NarrowestTy = OuterShift->getType();
207 Type *WidestTy = Masked->getType();
211 // that no bits are lost if the sum-of-shifts is wider than the base type.
212 Type *ExtendedTy = WidestTy->getExtendedType();
216 // ((1 << MaskShAmt) - 1)
218 // (~(-1 << maskNbits))
220 // (-1 l>> MaskShAmt)
222 // ((-1 << MaskShAmt) l>> MaskShAmt)
251 SumOfShAmts, ConstantInt::get(SumOfShAmts->getType()->getScalarType(),
252 ExtendedTy->getScalarSizeInBits()));
258 // And compute the mask as usual: ~(-1 << (SumOfShAmts))
277 // Can we simplify (ShiftShAmt-MaskShAmt) ?
289 unsigned WidestTyBitWidth = WidestTy->getScalarSizeInBits();
291 ShAmtsDiff, ConstantInt::get(ShAmtsDiff->getType()->getScalarType(),
292 -WidestTyBitWidth));
295 ConstantExpr::getSub(ConstantInt::get(ShAmtsDiff->getType(),
303 // And compute the mask as usual: (-1 l>> (NumHighBitsToClear))
320 if (!Masked->hasOneUse())
332 // No 'NUW'/'NSW'! We no longer know that we won't shift-out non-0 bits.
334 auto *NewShift = BinaryOperator::Create(OuterShift->getOpcode(), X,
335 OuterShift->getOperand(1));
343 /// If we have a shift-by-constant of a bin op (bitwise logic op or add/sub w/
344 /// shl) that itself has a shift-by-constant operand with identical opcode, we
353 (!BinInst->isBitwiseLogicOp() &&
354 BinInst->getOpcode() != Instruction::Add &&
355 BinInst->getOpcode() != Instruction::Sub) ||
356 !BinInst->hasOneUse())
365 if ((BinInst->getOpcode() == Instruction::Add ||
366 BinInst->getOpcode() == Instruction::Sub) &&
376 unsigned Size = Ty->getScalarSizeInBits();
379 (V->hasOneUse() || match(W, m_ImmConstant())) &&
388 if (matchFirstShift(BinInst->getOperand(0), BinInst->getOperand(1)))
389 Y = BinInst->getOperand(1);
390 else if (matchFirstShift(BinInst->getOperand(1), BinInst->getOperand(0))) {
391 Y = BinInst->getOperand(0);
392 FirstShiftIsOp1 = BinInst->getOpcode() == Instruction::Sub;
396 // shift (binop (shift X, C0), Y), C1 -> binop (shift X, C0+C1), (shift Y, C1)
402 return BinaryOperator::Create(BinInst->getOpcode(), Op1, Op2);
410 assert(Op0->getType() == Op1->getType());
413 // If the shift amount is a one-use `sext`, we can demote it to `zext`.
416 Value *NewExt = Builder.CreateZExt(Y, Ty, Op1->getName());
439 // Pre-shift a constant shifted by a variable amount with constant offset:
440 // C shift (A add nuw C1) --> (C shift C1) shift A
448 NewShiftOp->setHasNoSignedWrap(I.hasNoSignedWrap());
449 NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
451 NewShiftOp->setIsExact(I.isExact());
456 unsigned BitWidth = Ty->getScalarSizeInBits();
459 // Try to pre-shift a constant shifted by a variable amount added with a
461 // C << (X - AddC) --> (C >> AddC) << X
463 // C >> (X - AddC) --> (C << AddC) >> X
465 AddC->isNegative() && (-*AddC).ult(BitWidth)) {
466 assert(!AC->isZero() && "Expected simplify of shifted zero");
467 unsigned PosOffset = (-*AddC).getZExtValue();
475 AC->eq(AC->lshr(PosOffset).shl(PosOffset));
477 return I.isExact() && AC->eq(AC->shl(PosOffset).lshr(PosOffset));
479 return I.isExact() && AC->eq(AC->shl(PosOffset).ashr(PosOffset));
484 ? AC->lshr(PosOffset)
485 : AC->shl(PosOffset));
489 NewShiftOp->setHasNoUnsignedWrap(I.hasNoUnsignedWrap());
491 NewShiftOp->setIsExact();
497 // X shift (A srem C) -> X shift (A and (C - 1)) iff C is a power of 2.
500 if (Op1->hasOneUse() && match(Op1, m_SRem(m_Value(A), m_Constant(C))) &&
505 Value *Rem = Builder.CreateAnd(A, Mask, Op1->getName());
512 if (match(Op1, m_Or(m_Value(), m_SpecificInt(BitWidth - 1))))
513 return replaceOperand(I, 1, ConstantInt::get(Ty, BitWidth - 1));
520 match(Op1, m_SpecificInt(Ty->getScalarSizeInBits() - 1))) {
522 Builder.CreateICmp(cast<CmpIntrinsic>(CmpIntr)->getLTPredicate(),
523 CmpIntr->getOperand(0), CmpIntr->getOperand(1));
538 assert(InnerShift->isLogicalShift() && "Unexpected instruction type");
542 if (!match(InnerShift->getOperand(1), m_APInt(InnerShiftConst)))
546 // shl (shl X, C1), C2 --> shl X, C1 + C2
547 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
548 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
553 // lshr (shl X, C), C --> and X, C'
554 // shl (lshr X, C), C --> and X, C'
559 // lshr (shl X, C1), C2 --> and (shl X, C1 - C2), C3
560 // shl (lshr X, C1), C2 --> and (lshr X, C1 - C2), C3
564 unsigned TypeWidth = InnerShift->getType()->getScalarSizeInBits();
565 if (InnerShiftConst->ugt(OuterShAmt) && InnerShiftConst->ult(TypeWidth)) {
566 unsigned InnerShAmt = InnerShiftConst->getZExtValue();
568 IsInnerShl ? TypeWidth - InnerShAmt : InnerShAmt - OuterShAmt;
570 if (IC.MaskedValueIsZero(InnerShift->getOperand(0), Mask, 0, CxtI))
585 /// where the client will ask if E can be computed shifted right by 64-bits. If
598 if (!I->hasOneUse()) return false;
600 switch (I->getOpcode()) {
606 return canEvaluateShifted(I->getOperand(0), NumBits, IsLeftShift, IC, I) &&
607 canEvaluateShifted(I->getOperand(1), NumBits, IsLeftShift, IC, I);
615 Value *TrueVal = SI->getTrueValue();
616 Value *FalseVal = SI->getFalseValue();
625 for (Value *IncValue : PN->incoming_values())
632 // We can fold (shr (mul X, -(1 << C)), C) -> (and (neg X), C`)
633 return !IsLeftShift && match(I->getOperand(1), m_APInt(MulConst)) &&
634 MulConst->isNegatedPowerOf2() && MulConst->countr_zero() == NumBits;
644 bool IsInnerShl = InnerShift->getOpcode() == Instruction::Shl;
645 Type *ShType = InnerShift->getType();
646 unsigned TypeWidth = ShType->getScalarSizeInBits();
648 // We only accept shifts-by-a-constant in canEvaluateShifted().
650 match(InnerShift->getOperand(1), m_APInt(C1));
651 unsigned InnerShAmt = C1->getZExtValue();
655 InnerShift->setOperand(1, ConstantInt::get(ShType, ShAmt));
657 InnerShift->setHasNoUnsignedWrap(false);
658 InnerShift->setHasNoSignedWrap(false);
660 InnerShift->setIsExact(false);
666 // shl (shl X, C1), C2 --> shl X, C1 + C2
667 // lshr (lshr X, C1), C2 --> lshr X, C1 + C2
677 // lshr (shl X, C), C --> and X, C'
678 // shl (lshr X, C), C --> and X, C'
681 ? APInt::getLowBitsSet(TypeWidth, TypeWidth - OuterShAmt)
682 : APInt::getHighBitsSet(TypeWidth, TypeWidth - OuterShAmt);
683 Value *And = Builder.CreateAnd(InnerShift->getOperand(0),
686 AndI->moveBefore(InnerShift->getIterator());
687 AndI->takeName(InnerShift);
696 // canEvaluateShiftedShift() guarantees that the masked-off bits are not used.
697 // lshr (shl X, C1), C2 --> shl X, C1 - C2
698 // shl (lshr X, C1), C2 --> lshr X, C1 - C2
699 return NewInnerShift(InnerShAmt - OuterShAmt);
717 switch (I->getOpcode()) {
723 I->setOperand(
724 0, getShiftedValue(I->getOperand(0), NumBits, isLeftShift, IC, DL));
725 I->setOperand(
726 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
735 I->setOperand(
736 1, getShiftedValue(I->getOperand(1), NumBits, isLeftShift, IC, DL));
737 I->setOperand(
738 2, getShiftedValue(I->getOperand(2), NumBits, isLeftShift, IC, DL));
745 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
746 PN->setIncomingValue(i, getShiftedValue(PN->getIncomingValue(i), NumBits,
752 auto *Neg = BinaryOperator::CreateNeg(I->getOperand(0));
753 IC.InsertNewInstWith(Neg, I->getIterator());
754 unsigned TypeWidth = I->getType()->getScalarSizeInBits();
755 APInt Mask = APInt::getLowBitsSet(TypeWidth, TypeWidth - NumBits);
757 ConstantInt::get(I->getType(), Mask));
758 And->takeName(I);
759 return IC.InsertNewInstWith(And, I->getIterator());
768 switch (BO->getOpcode()) {
785 // (C2 << X) << C1 --> (C2 << C1) << X
786 // (C2 >> X) >> C1 --> (C2 >> C1) >> X
795 R->setHasNoUnsignedWrap(I.hasNoUnsignedWrap() &&
796 BO0->hasNoUnsignedWrap());
797 R->setHasNoSignedWrap(I.hasNoSignedWrap() && BO0->hasNoSignedWrap());
799 R->setIsExact(I.isExact() && BO0->isExact());
804 unsigned TypeBits = Ty->getScalarSizeInBits();
806 // (X / +DivC) >> (Width - 1) --> ext (X <= -DivC)
807 // (X / -DivC) >> (Width - 1) --> ext (X >= +DivC)
809 if (!IsLeftShift && match(C1, m_SpecificIntAllowPoison(TypeBits - 1)) &&
810 match(Op0, m_SDiv(m_Value(X), m_APInt(DivC))) && !DivC->isZero() &&
811 !DivC->isMinSignedValue()) {
812 Constant *NegDivC = ConstantInt::get(Ty, -(*DivC));
814 DivC->isNegative() ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_SLE;
825 assert(!Op1C->uge(TypeBits) &&
831 canEvaluateShifted(Op0, Op1C->getZExtValue(), IsLeftShift, *this, &I)) {
838 I, getShiftedValue(Op0, Op1C->getZExtValue(), IsLeftShift, *this, DL));
844 if (!Op0->hasOneUse())
851 if (match(Op0BO->getOperand(1), m_APInt(Op0C))) {
854 Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(1), C1);
857 Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), C1);
858 NewShift->takeName(Op0BO);
860 return BinaryOperator::Create(Op0BO->getOpcode(), NewShift, NewRHS);
879 if (!isa<Constant>(FalseVal) && TBO->getOperand(0) == FalseVal &&
880 match(TBO->getOperand(1), m_APInt(C)) &&
883 Builder.CreateBinOp(I.getOpcode(), TBO->getOperand(1), C1);
886 Value *NewOp = Builder.CreateBinOp(TBO->getOpcode(), NewShift, NewRHS);
896 if (!isa<Constant>(TrueVal) && FBO->getOperand(0) == TrueVal &&
897 match(FBO->getOperand(1), m_APInt(C)) &&
900 Builder.CreateBinOp(I.getOpcode(), FBO->getOperand(1), C1);
903 Value *NewOp = Builder.CreateBinOp(FBO->getOpcode(), NewShift, NewRHS);
913 // -> (icmp ult (add X, Y), X)
915 // - The add's operands are zexts from a K-bits integer to a bigger type.
916 // - The add is only used by the shr, or by iK (or narrower) truncates.
917 // - The lshr type has more than 2 bits (other types are boolean math).
918 // - K > 1
920 // - The resulting add cannot have nuw/nsw, else on overflow we get a
929 if (Ty->getScalarSizeInBits() < 3)
939 const unsigned ShAmt = ShAmtAPInt->getZExtValue();
943 // X/Y are zexts from `ShAmt`-sized ints.
944 if (X->getType()->getScalarSizeInBits() != ShAmt ||
945 Y->getType()->getScalarSizeInBits() != ShAmt)
948 // Make sure that `Add` is only used by `I` and `ShAmt`-truncates.
949 if (!Add->hasOneUse()) {
950 for (User *U : Add->users()) {
955 if (!Trunc || Trunc->getType()->getScalarSizeInBits() > ShAmt)
971 // be ShAmt-sized truncs, or the lshr itself.
972 if (!Add->hasOneUse()) {
1000 KnownBits KnownCnt = computeKnownBits(I.getOperand(1), /* Depth */ 0, Q);
1004 uint64_t MaxCnt = KnownCnt.getMaxValue().getLimitedValue(BitWidth - 1);
1006 KnownBits KnownAmt = computeKnownBits(I.getOperand(0), /* Depth */ 0, Q);
1018 MaxCnt < ComputeNumSignBits(I.getOperand(0), Q.DL, /*Depth*/ 0, Q.AC,
1053 unsigned BitWidth = Ty->getScalarSizeInBits();
1057 unsigned ShAmtC = C->getZExtValue();
1059 // shl (zext X), C --> zext (shl X, C)
1063 unsigned SrcWidth = X->getType()->getScalarSizeInBits();
1069 // (X >> C) << C --> X & (-1 << C)
1071 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));
1077 C1->ult(BitWidth)) {
1078 unsigned ShrAmt = C1->getZExtValue();
1080 // If C1 < C: (X >>?,exact C1) << C --> X << (C - C1)
1081 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt);
1083 NewShl->setHasNoUnsignedWrap(
1086 cast<Instruction>(Op0)->getOpcode() == Instruction::LShr &&
1088 NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
1092 // If C1 > C: (X >>?exact C1) << C --> X >>?exact (C1 - C)
1093 Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC);
1095 cast<BinaryOperator>(Op0)->getOpcode(), X, ShiftDiff);
1096 NewShr->setIsExact(true);
1102 C1->ult(BitWidth)) {
1103 unsigned ShrAmt = C1->getZExtValue();
1105 // If C1 < C: (X >>? C1) << C --> (X << (C - C1)) & (-1 << C)
1106 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShrAmt);
1108 NewShl->setHasNoUnsignedWrap(
1111 cast<Instruction>(Op0)->getOpcode() == Instruction::LShr &&
1113 NewShl->setHasNoSignedWrap(I.hasNoSignedWrap());
1115 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));
1119 // If C1 > C: (X >>? C1) << C --> (X >>? (C1 - C)) & (-1 << C)
1120 Constant *ShiftDiff = ConstantInt::get(Ty, ShrAmt - ShAmtC);
1123 BinaryOperator::Create(OldShr->getOpcode(), X, ShiftDiff);
1124 NewShr->setIsExact(OldShr->isExact());
1126 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));
1136 unsigned ShrAmtC = C1->getZExtValue();
1137 unsigned ShDiff = ShrAmtC > ShAmtC ? ShrAmtC - ShAmtC : ShAmtC - ShrAmtC;
1138 Constant *ShiftDiffC = ConstantInt::get(X->getType(), ShDiff);
1139 auto ShiftOpc = ShrAmtC > ShAmtC ? Shr->getOpcode() : Instruction::Shl;
1142 // (trunc (X >> C1)) << C --> (trunc (X >> (C1 - C))) && (-1 << C)
1144 // (trunc (X >> C1)) << C --> (trunc (X << (C - C1))) && (-1 << C)
1147 APInt Mask(APInt::getHighBitsSet(BitWidth, BitWidth - ShAmtC));
1163 // when the shift-right is operand 1 (RHS) of the sub.
1169 isSuitableBinOpcode(Op0BO->getOpcode())) {
1170 // Commute so shift-right is on LHS of the binop.
1171 // (Y bop (X >> C)) << C -> ((X >> C) bop Y) << C
1172 // (Y bop ((X >> C) & CC)) << C -> (((X >> C) & CC) bop Y) << C
1173 Value *Shr = Op0BO->getOperand(0);
1174 Value *Y = Op0BO->getOperand(1);
1177 if (Op0BO->isCommutative() && Y->hasOneUse() &&
1183 // ((X >> C) bop Y) << C -> (X bop (Y << C)) & (~0 << C)
1186 Value *YS = Builder.CreateShl(Y, Op1, Op0BO->getName());
1189 Builder.CreateBinOp(Op0BO->getOpcode(), X, YS, Shr->getName());
1190 unsigned Op1Val = C->getLimitedValue(BitWidth);
1191 APInt Bits = APInt::getHighBitsSet(BitWidth, BitWidth - Op1Val);
1196 // (((X >> C) & CC) bop Y) << C -> (X & (CC << C)) bop (Y << C)
1201 Value *YS = Builder.CreateShl(Y, Op1, Op0BO->getName());
1203 Value *M = Builder.CreateAnd(X, ConstantInt::get(Ty, CC->shl(*C)),
1204 X->getName() + ".mask");
1205 auto *NewOp = BinaryOperator::Create(Op0BO->getOpcode(), M, YS);
1207 Disjoint && Disjoint->isDisjoint())
1208 cast<PossiblyDisjointInst>(NewOp)->setIsDisjoint(true);
1213 // (C1 - X) << C --> (C1 << C) - (X << C)
1215 Constant *NewLHS = ConstantInt::get(Ty, C1->shl(*C));
1224 // Transform (x >> y) << y to x & (-1 << y)
1225 // Valid for any type of right-shift.
1233 // Transform (-1 >> y) << y to -1 << y
1243 // (X * C2) << C1 --> X * (C2 << C1)
1247 // shl (zext i1 X), C1 --> select (X, 1 << C1, 0)
1248 if (match(Op0, m_ZExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
1255 // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1
1256 if (match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X))))
1260 // Canonicalize "extract lowest set bit" using cttz to and-with-negate:
1261 // 1 << (cttz X) --> -X & X
1287 unsigned BitWidth = Ty->getScalarSizeInBits();
1289 // (iN (~X) u>> (N - 1)) --> zext (X > -1)
1291 match(Op1, m_SpecificIntAllowPoison(BitWidth - 1)))
1294 // ((X << nuw Z) sub nuw Y) >>u exact Z --> X sub nuw (Y >>u exact Z)
1301 NewSub->setHasNoSignedWrap(
1302 cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap());
1306 // Fold (X + Y) / 2 --> (X & Y) iff (X u<= 1) && (Y u<= 1)
1308 computeKnownBits(X, /*Depth=*/0, &I).countMaxActiveBits() <= 1 &&
1309 computeKnownBits(Y, /*Depth=*/0, &I).countMaxActiveBits() <= 1)
1312 // (sub nuw X, (Y << nuw Z)) >>u exact Z --> (X >>u exact Z) sub nuw Y
1318 NewSub->setHasNoSignedWrap(
1319 cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap());
1337 // ((X << nuw Z) binop nuw Y) >>u Z --> X binop nuw (Y >>u Z)
1341 if (isSuitableBinOpcode(Op0OB->getOpcode())) {
1343 !OBO || OBO->hasNoUnsignedWrap()) {
1345 Y, Op1, "", I.isExact() && Op0OB->getOpcode() != Instruction::And);
1346 auto *NewBinOp = BinaryOperator::Create(Op0OB->getOpcode(), NewLshr, X);
1348 NewBinOp->setHasNoUnsignedWrap(true);
1349 NewBinOp->setHasNoSignedWrap(OBO->hasNoSignedWrap());
1351 cast<PossiblyDisjointInst>(NewBinOp)->setIsDisjoint(
1352 Disjoint->isDisjoint());
1360 unsigned ShAmtC = C->getZExtValue();
1363 (II->getIntrinsicID() == Intrinsic::ctlz ||
1364 II->getIntrinsicID() == Intrinsic::cttz ||
1365 II->getIntrinsicID() == Intrinsic::ctpop)) {
1366 // ctlz.i32(x)>>5 --> zext(x == 0)
1367 // cttz.i32(x)>>5 --> zext(x == 0)
1368 // ctpop.i32(x)>>5 --> zext(x == -1)
1369 bool IsPop = II->getIntrinsicID() == Intrinsic::ctpop;
1370 Constant *RHS = ConstantInt::getSigned(Ty, IsPop ? -1 : 0);
1371 Value *Cmp = Builder.CreateICmpEQ(II->getArgOperand(0), RHS);
1376 if (match(Op0, m_Shl(m_Value(X), m_APInt(C1))) && C1->ult(BitWidth)) {
1377 if (C1->ult(ShAmtC)) {
1378 unsigned ShlAmtC = C1->getZExtValue();
1379 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmtC - ShlAmtC);
1380 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
1381 // (X <<nuw C1) >>u C --> X >>u (C - C1)
1383 NewLShr->setIsExact(I.isExact());
1386 if (Op0->hasOneUse()) {
1387 // (X << C1) >>u C --> (X >>u (C - C1)) & (-1 >> C)
1389 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));
1392 } else if (C1->ugt(ShAmtC)) {
1393 unsigned ShlAmtC = C1->getZExtValue();
1394 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmtC - ShAmtC);
1395 if (cast<BinaryOperator>(Op0)->hasNoUnsignedWrap()) {
1396 // (X <<nuw C1) >>u C --> X <<nuw/nsw (C1 - C)
1398 NewShl->setHasNoUnsignedWrap(true);
1399 NewShl->setHasNoSignedWrap(ShAmtC > 0);
1402 if (Op0->hasOneUse()) {
1403 // (X << C1) >>u C --> X << (C1 - C) & (-1 >> C)
1405 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));
1410 // (X << C) >>u C --> X & (-1 >>u C)
1411 APInt Mask(APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));
1416 // ((X << C) + Y) >>u C --> (X + (Y >>u C)) & (-1 >>u C)
1424 unsigned Op1Val = C->getLimitedValue(BitWidth);
1425 APInt Bits = APInt::getLowBitsSet(BitWidth, BitWidth - Op1Val);
1431 (!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType()))) {
1432 assert(ShAmtC < X->getType()->getScalarSizeInBits() &&
1434 // lshr (zext iM X to iN), C --> zext (lshr X, C) to iN
1440 unsigned SrcTyBitWidth = X->getType()->getScalarSizeInBits();
1441 // lshr (sext i1 X to iN), C --> select (X, -1 >> C, 0)
1444 Ty, APInt::getLowBitsSet(BitWidth, BitWidth - ShAmtC));
1448 if ((!Ty->isIntegerTy() || shouldChangeType(Ty, X->getType())) &&
1449 Op0->hasOneUse()) {
1451 // zeros? lshr (sext iM X to iN), N-1 --> zext (lshr X, M-1) to iN
1452 if (ShAmtC == BitWidth - 1) {
1453 Value *NewLShr = Builder.CreateLShr(X, SrcTyBitWidth - 1);
1457 // lshr (sext iM X to iN), N-M --> zext (ashr X, min(N-M, M-1)) to iN
1458 if (ShAmtC == BitWidth - SrcTyBitWidth) {
1460 unsigned NewShAmt = std::min(ShAmtC, SrcTyBitWidth - 1);
1467 if (ShAmtC == BitWidth - 1) {
1468 // lshr i32 or(X,-X), 31 --> zext (X != 0)
1472 // lshr i32 (X -nsw Y), 31 --> zext (X < Y)
1477 // lshr i32 (srem X, 2), 31 --> and (X >> 31), X
1483 // lshr iN (X - 1) & ~X, N-1 --> zext (X == 0)
1492 unsigned SrcWidth = X->getType()->getScalarSizeInBits();
1493 unsigned AmtSum = ShAmtC + C1->getZExtValue();
1496 // (trunc (X >>u C1)) >>u C --> and (trunc (X >>u (C1 + C)), MaskC
1501 (TruncSrc->hasOneUse() || C1->uge(SrcWidth - BitWidth))) {
1514 if (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1515 MulC->logBase2() == ShAmtC) {
1516 // Look for a "splat" mul pattern - it replicates bits across each half
1518 // lshr i[2N] (mul nuw X, (2^N)+1), N --> X
1522 // lshr (mul nuw (X, 2^N + 1)), N -> add nuw (X, lshr(X, N))
1523 if (Op0->hasOneUse()) {
1527 NewAdd->setHasNoSignedWrap(
1528 cast<OverflowingBinaryOperator>(Op0)->hasNoSignedWrap());
1533 // The one-use check is not strictly necessary, but codegen may not be
1536 if (Op0->hasOneUse()) {
1537 APInt NewMulC = MulC->lshr(ShAmtC);
1539 // lshr (mul nuw x, MulC), ShAmtC -> mul nuw nsw x, (MulC >> ShAmtC)
1540 if (MulC->eq(NewMulC.shl(ShAmtC))) {
1545 NewMul->setHasNoSignedWrap(true);
1551 // lshr (mul nsw (X, 2^N + 1)), N -> add nsw (X, lshr(X, N))
1553 if (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1554 MulC->logBase2() == ShAmtC) {
1566 unsigned SrcWidth = X->getType()->getScalarSizeInBits();
1567 unsigned WidthDiff = BitWidth - SrcWidth;
1571 // (bswap (zext X)) >> C --> zext (bswap X >> C')
1572 Value *NewShift = Builder.CreateLShr(NarrowSwap, ShAmtC - WidthDiff);
1575 // (bswap (zext X)) >> C --> (zext (bswap X)) << C'
1577 Constant *ShiftDiff = ConstantInt::get(Ty, WidthDiff - ShAmtC);
1583 // Reduce add-carry of bools to logic:
1584 // ((zext BoolX) + (zext BoolY)) >> 1 --> zext (BoolX && BoolY)
1588 BoolX->getType()->isIntOrIntVectorTy(1) &&
1589 BoolY->getType()->isIntOrIntVectorTy(1) &&
1590 (X->hasOneUse() || Y->hasOneUse() || Op0->hasOneUse())) {
1600 // Transform (x << y) >> y to x & (-1 >> y)
1607 // Transform (-1 << y) >> y to -1 >> y
1623 "Must be called with arithmetic right-shift instruction only.");
1625 // Check that constant C is a splat of the element-wise bitwidth of V.
1629 APInt(C->getType()->getScalarSizeInBits(),
1630 V->getType()->getScalarSizeInBits())));
1633 // It should look like variable-length sign-extension on the outside:
1634 // (Val << (bitwidth(Val)-Nbits)) a>> (bitwidth(Val)-Nbits)
1652 // And finally, the innermost part of the pattern must be a right-shift.
1657 // Said right-shift must extract high NBits bits - C0 must be it's bitwidth.
1668 if (HighBitExtract->getOpcode() == OldAShr.getOpcode())
1680 NewAShr->copyIRFlags(HighBitExtract); // We can preserve 'exact'-ness.
1701 unsigned BitWidth = Ty->getScalarSizeInBits();
1703 if (match(Op1, m_APInt(ShAmtAPInt)) && ShAmtAPInt->ult(BitWidth)) {
1704 unsigned ShAmt = ShAmtAPInt->getZExtValue();
1708 // ashr (shl (zext X), C), C --> sext X
1711 ShAmt == BitWidth - X->getType()->getScalarSizeInBits())
1718 ShOp1->ult(BitWidth)) {
1719 unsigned ShlAmt = ShOp1->getZExtValue();
1721 // (X <<nsw C1) >>s C2 --> X >>s (C2 - C1)
1722 Constant *ShiftDiff = ConstantInt::get(Ty, ShAmt - ShlAmt);
1724 NewAShr->setIsExact(I.isExact());
1728 // (X <<nsw C1) >>s C2 --> X <<nsw (C1 - C2)
1729 Constant *ShiftDiff = ConstantInt::get(Ty, ShlAmt - ShAmt);
1731 NewShl->setHasNoSignedWrap(true);
1737 ShOp1->ult(BitWidth)) {
1738 unsigned AmtSum = ShAmt + ShOp1->getZExtValue();
1740 AmtSum = std::min(AmtSum, BitWidth - 1);
1741 // (X >>s C1) >>s C2 --> X >>s (C1 + C2)
1746 (Ty->isVectorTy() || shouldChangeType(Ty, X->getType()))) {
1747 // ashr (sext X), C --> sext (ashr X, C')
1748 Type *SrcTy = X->getType();
1749 ShAmt = std::min(ShAmt, SrcTy->getScalarSizeInBits() - 1);
1754 if (ShAmt == BitWidth - 1) {
1755 // ashr i32 or(X,-X), 31 --> sext (X != 0)
1759 // ashr i32 (X -nsw Y), 31 --> sext (X < Y)
1764 // ashr iN (X - 1) & ~X, N-1 --> sext (X == 0)
1772 (BitWidth > 2 && (*MulC - 1).isPowerOf2() &&
1773 MulC->logBase2() == ShAmt &&
1774 (ShAmt < BitWidth - 1))) /* Minus 1 for the sign bit */ {
1776 // ashr (mul nsw (X, 2^N + 1)), N -> add nsw (X, ashr(X, N))
1780 NewAdd->setHasNoUnsignedWrap(
1781 cast<OverflowingBinaryOperator>(Op0)->hasNoUnsignedWrap());
1790 // Prefer `-(x & 1)` over `(x << (bitwidth(x)-1)) a>> (bitwidth(x)-1)`
1792 // FIXME: iff X is already masked, we don't need the one-use check.
1794 if (match(Op1, m_SpecificIntAllowPoison(BitWidth - 1)) &&
1796 m_SpecificIntAllowPoison(BitWidth - 1))))) {
1801 cast<Constant>(cast<Instruction>(Op0)->getOperand(1)));
1812 Lshr->setIsExact(I.isExact());
1816 // ashr (xor %x, -1), %y --> xor (ashr %x, %y), -1
1818 // Note that we must drop 'exact'-ness of the shift!
1819 // Note that we can't keep undef's in -1 vector constant!
1820 auto *NewAShr = Builder.CreateAShr(X, Op1, Op0->getName() + ".not");