25#define DEBUG_TYPE "instcombine"
29 cl::desc(
"Verify that computeKnownBits() and "
30 "SimplifyDemandedBits() are consistent"),
37 const APInt &Demanded) {
39 assert(OpNo < I->getNumOperands() &&
"Operand index too large");
48 if (
C->isSubsetOf(Demanded))
52 I->setOperand(OpNo, ConstantInt::get(
Op->getType(), *
C & Demanded));
63 return DL.getPointerTypeSizeInBits(Ty);
74 if (V == &Inst)
return true;
90 const APInt &DemandedMask,
92 Use &U =
I->getOperandUse(OpNo);
95 if (!NewVal)
return false;
130 assert(V !=
nullptr &&
"Null pointer of Value???");
133 Type *VTy = V->getType();
137 "Value *V, DemandedMask and Known must have same BitWidth");
139 if (isa<Constant>(V)) {
145 if (DemandedMask.
isZero())
160 if (
Depth != 0 && !
I->hasOneUse())
168 if (
Depth == 0 && !V->hasOneUse())
173 auto disableWrapFlagsBasedOnUnusedHighBits = [](
Instruction *
I,
179 I->setHasNoSignedWrap(
false);
180 I->setHasNoUnsignedWrap(
false);
187 auto simplifyOperandsBasedOnUnusedHighBits = [&](
APInt &DemandedFromOps) {
196 disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
202 switch (
I->getOpcode()) {
206 case Instruction::And: {
213 assert(!LHSKnown.hasConflict() &&
"Bits known to be one AND zero?");
226 return I->getOperand(0);
228 return I->getOperand(1);
236 case Instruction::Or: {
242 I->dropPoisonGeneratingFlags();
246 assert(!LHSKnown.hasConflict() &&
"Bits known to be one AND zero?");
259 return I->getOperand(0);
261 return I->getOperand(1);
268 if (!cast<PossiblyDisjointInst>(
I)->isDisjoint()) {
270 RHSCache(
I->getOperand(1), RHSKnown);
272 cast<PossiblyDisjointInst>(
I)->setIsDisjoint(
true);
279 case Instruction::Xor: {
284 if (DemandedMask == 1 &&
295 assert(!LHSKnown.hasConflict() &&
"Bits known to be one AND zero?");
308 return I->getOperand(0);
310 return I->getOperand(1);
317 BinaryOperator::CreateOr(
I->getOperand(0),
I->getOperand(1));
319 cast<PossiblyDisjointInst>(
Or)->setIsDisjoint(
true);
331 ~RHSKnown.
One & DemandedMask);
341 if ((*
C | ~DemandedMask).isAllOnes()) {
355 if (
Instruction *LHSInst = dyn_cast<Instruction>(
I->getOperand(0))) {
357 if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() &&
360 (LHSKnown.One & RHSKnown.
One & DemandedMask) != 0) {
361 APInt NewMask = ~(LHSKnown.One & RHSKnown.
One & DemandedMask);
364 Instruction *NewAnd = BinaryOperator::CreateAnd(
I->getOperand(0), AndC);
368 Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC);
374 case Instruction::Select: {
379 assert(!LHSKnown.hasConflict() &&
"Bits known to be one AND zero?");
386 auto CanonicalizeSelectConstant = [](
Instruction *
I,
unsigned OpNo,
387 const APInt &DemandedMask) {
408 if ((*CmpC & DemandedMask) == (*SelC & DemandedMask)) {
409 I->setOperand(OpNo, ConstantInt::get(
I->getType(), *CmpC));
414 if (CanonicalizeSelectConstant(
I, 1, DemandedMask) ||
415 CanonicalizeSelectConstant(
I, 2, DemandedMask))
422 case Instruction::Trunc: {
441 case Instruction::ZExt: {
442 unsigned SrcBitWidth =
I->getOperand(0)->getType()->getScalarSizeInBits();
449 I->dropPoisonGeneratingFlags();
453 if (
I->getOpcode() == Instruction::ZExt &&
I->hasNonNeg() &&
461 case Instruction::SExt: {
463 unsigned SrcBitWidth =
I->getOperand(0)->getType()->getScalarSizeInBits();
465 APInt InputDemandedBits = DemandedMask.
trunc(SrcBitWidth);
470 InputDemandedBits.
setBit(SrcBitWidth-1);
492 case Instruction::Add: {
493 if ((DemandedMask & 1) == 0) {
499 X->getType()->isIntOrIntVectorTy(1) &&
X->getType() ==
Y->getType()) {
516 X->getType()->isIntOrIntVectorTy(1) &&
X->getType() ==
Y->getType()) {
536 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
542 APInt DemandedFromLHS = DemandedFromOps;
546 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
551 return I->getOperand(0);
552 if (DemandedFromOps.
isSubsetOf(LHSKnown.Zero))
553 return I->getOperand(1);
567 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
568 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
572 case Instruction::Sub: {
579 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
585 APInt DemandedFromLHS = DemandedFromOps;
589 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
594 return I->getOperand(0);
597 if (DemandedFromOps.
isOne() && DemandedFromOps.
isSubsetOf(LHSKnown.Zero))
598 return I->getOperand(1);
601 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
602 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
606 case Instruction::Mul: {
607 APInt DemandedFromOps;
608 if (simplifyOperandsBasedOnUnusedHighBits(DemandedFromOps))
618 Constant *ShiftC = ConstantInt::get(VTy, CTZ);
619 Instruction *Shl = BinaryOperator::CreateShl(
I->getOperand(0), ShiftC);
626 if (
I->getOperand(0) ==
I->getOperand(1) && DemandedMask.
ult(4)) {
627 Constant *One = ConstantInt::get(VTy, 1);
628 Instruction *And1 = BinaryOperator::CreateAnd(
I->getOperand(0), One);
635 case Instruction::Shl: {
640 if (
Instruction *Shr = dyn_cast<Instruction>(
I->getOperand(0)))
642 DemandedMask, Known))
646 if (
I->hasOneUse()) {
647 auto *Inst = dyn_cast<Instruction>(
I->user_back());
648 if (Inst && Inst->getOpcode() == BinaryOperator::Or) {
650 auto [IID, FShiftArgs] = *Opt;
651 if ((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
652 FShiftArgs[0] == FShiftArgs[1])
662 if (
I->hasNoSignedWrap()) {
666 if (SignBits > ShiftAmt && SignBits - ShiftAmt >= NumHiDemandedBits)
667 return I->getOperand(0);
677 Constant *LeftShiftAmtC = ConstantInt::get(VTy, ShiftAmt);
681 LeftShiftAmtC,
DL) ==
C) {
682 Instruction *Lshr = BinaryOperator::CreateLShr(NewC,
X);
688 APInt DemandedMaskIn(DemandedMask.
lshr(ShiftAmt));
713 I->dropPoisonGeneratingFlags();
721 case Instruction::LShr: {
727 if (
I->hasOneUse()) {
728 auto *Inst = dyn_cast<Instruction>(
I->user_back());
729 if (Inst && Inst->getOpcode() == BinaryOperator::Or) {
731 auto [IID, FShiftArgs] = *Opt;
732 if ((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
733 FShiftArgs[0] == FShiftArgs[1])
747 if (SignBits >= NumHiDemandedBits)
748 return I->getOperand(0);
757 Constant *RightShiftAmtC = ConstantInt::get(VTy, ShiftAmt);
761 RightShiftAmtC,
DL) ==
C) {
769 APInt DemandedMaskIn(DemandedMask.
shl(ShiftAmt));
772 I->dropPoisonGeneratingFlags();
785 case Instruction::AShr: {
791 if (SignBits >= NumHiDemandedBits)
792 return I->getOperand(0);
798 if (DemandedMask.
isOne()) {
801 I->getOperand(0),
I->getOperand(1),
I->getName());
810 APInt DemandedMaskIn(DemandedMask.
shl(ShiftAmt));
818 I->dropPoisonGeneratingFlags();
836 LShr->
setIsExact(cast<BinaryOperator>(
I)->isExact());
840 Known.
One |= HighBits;
843 Known.
Zero &= ~HighBits;
850 case Instruction::UDiv: {
856 APInt DemandedMaskIn =
861 I->dropPoisonGeneratingFlags();
866 cast<BinaryOperator>(
I)->isExact());
872 case Instruction::SRem: {
880 if (
RA.isPowerOf2()) {
881 if (DemandedMask.
ult(
RA))
882 return I->getOperand(0);
890 Known.
Zero = LHSKnown.Zero & LowBits;
891 Known.
One = LHSKnown.One & LowBits;
895 if (LHSKnown.isNonNegative() || LowBits.
isSubsetOf(LHSKnown.Zero))
896 Known.
Zero |= ~LowBits;
900 if (LHSKnown.isNegative() && LowBits.
intersects(LHSKnown.One))
901 Known.
One |= ~LowBits;
911 case Instruction::URem: {
920 case Instruction::Call: {
921 bool KnownBitsComputed =
false;
923 switch (II->getIntrinsicID()) {
924 case Intrinsic::abs: {
925 if (DemandedMask == 1)
926 return II->getArgOperand(0);
929 case Intrinsic::ctpop: {
937 II->getModule(), Intrinsic::ctpop, VTy);
942 case Intrinsic::bswap: {
959 NewVal = BinaryOperator::CreateLShr(
960 II->getArgOperand(0), ConstantInt::get(VTy, NLZ - NTZ));
962 NewVal = BinaryOperator::CreateShl(
963 II->getArgOperand(0), ConstantInt::get(VTy, NTZ - NLZ));
969 case Intrinsic::ptrmask: {
970 unsigned MaskWidth =
I->getOperand(1)->getType()->getScalarSizeInBits();
975 I, 1, (DemandedMask & ~LHSKnown.Zero).zextOrTrunc(MaskWidth),
976 RHSKnown,
Depth + 1))
982 assert(!LHSKnown.hasConflict() &&
"Bits known to be one AND zero?");
984 Known = LHSKnown & RHSKnown;
985 KnownBitsComputed =
true;
1000 if (DemandedMask.
isSubsetOf(RHSKnown.One | LHSKnown.Zero))
1001 return I->getOperand(0);
1005 I, 1, (DemandedMask & ~LHSKnown.Zero).zextOrTrunc(MaskWidth)))
1015 if (
match(
I, m_Intrinsic<Intrinsic::ptrmask>(
1020 if (!LHSKnown.isZero()) {
1021 const unsigned trailingZeros = LHSKnown.countMinTrailingZeros();
1024 uint64_t HighBitsGEPIndex = GEPIndex & ~PointerAlignBits;
1026 GEPIndex & PointerAlignBits & PtrMaskImmediate;
1028 uint64_t MaskedGEPIndex = HighBitsGEPIndex | MaskedLowBitsGEPIndex;
1030 if (MaskedGEPIndex != GEPIndex) {
1031 auto *
GEP = cast<GetElementPtrInst>(II->getArgOperand(0));
1033 Type *GEPIndexType =
1036 GEP->getSourceElementType(), InnerPtr,
1037 ConstantInt::get(GEPIndexType, MaskedGEPIndex),
1038 GEP->getName(),
GEP->isInBounds());
1049 case Intrinsic::fshr:
1050 case Intrinsic::fshl: {
1058 if (II->getIntrinsicID() == Intrinsic::fshr)
1061 APInt DemandedMaskLHS(DemandedMask.
lshr(ShiftAmt));
1063 if (
I->getOperand(0) !=
I->getOperand(1)) {
1072 if (DemandedMaskLHS.
isSubsetOf(LHSKnown.Zero | LHSKnown.One) &&
1086 Known.
Zero = LHSKnown.Zero.
shl(ShiftAmt) |
1088 Known.
One = LHSKnown.One.
shl(ShiftAmt) |
1090 KnownBitsComputed =
true;
1093 case Intrinsic::umax: {
1100 CTZ >=
C->getActiveBits())
1101 return II->getArgOperand(0);
1104 case Intrinsic::umin: {
1112 CTZ >=
C->getBitWidth() -
C->countl_one())
1113 return II->getArgOperand(0);
1119 *II, DemandedMask, Known, KnownBitsComputed);
1127 if (!KnownBitsComputed)
1133 if (V->getType()->isPointerTy()) {
1134 Align Alignment = V->getPointerAlignment(
DL);
1142 if (!V->getType()->isPointerTy() && DemandedMask.
isSubsetOf(Known.
Zero | Known.
One))
1147 if (Known != ReferenceKnown) {
1148 errs() <<
"Mismatched known bits for " << *V <<
" in "
1149 <<
I->getFunction()->getName() <<
"\n";
1150 errs() <<
"computeKnownBits(): " << ReferenceKnown <<
"\n";
1151 errs() <<
"SimplifyDemandedBits(): " << Known <<
"\n";
1166 Type *ITy =
I->getType();
1175 switch (
I->getOpcode()) {
1176 case Instruction::And: {
1191 return I->getOperand(0);
1193 return I->getOperand(1);
1197 case Instruction::Or: {
1214 return I->getOperand(0);
1216 return I->getOperand(1);
1220 case Instruction::Xor: {
1236 return I->getOperand(0);
1238 return I->getOperand(1);
1242 case Instruction::Add: {
1250 return I->getOperand(0);
1254 return I->getOperand(1);
1256 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
1257 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
1263 case Instruction::Sub: {
1271 return I->getOperand(0);
1273 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
1274 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
1281 case Instruction::AShr: {
1294 const APInt *ShiftRC;
1295 const APInt *ShiftLC;
1343 if (!ShlOp1 || !ShrOp1)
1357 Known.
Zero &= DemandedMask;
1362 bool isLshr = (Shr->
getOpcode() == Instruction::LShr);
1363 BitMask1 = isLshr ? (BitMask1.
lshr(ShrAmt) << ShlAmt) :
1364 (BitMask1.
ashr(ShrAmt) << ShlAmt);
1366 if (ShrAmt <= ShlAmt) {
1367 BitMask2 <<= (ShlAmt - ShrAmt);
1369 BitMask2 = isLshr ? BitMask2.
lshr(ShrAmt - ShlAmt):
1370 BitMask2.
ashr(ShrAmt - ShlAmt);
1374 if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) {
1375 if (ShrAmt == ShlAmt)
1382 if (ShrAmt < ShlAmt) {
1384 New = BinaryOperator::CreateShl(VarX, Amt);
1390 New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) :
1391 BinaryOperator::CreateAShr(VarX, Amt);
1392 if (cast<BinaryOperator>(Shr)->isExact())
1393 New->setIsExact(
true);
1419 bool AllowMultipleUsers) {
1422 if (isa<ScalableVectorType>(V->getType()))
1425 unsigned VWidth = cast<FixedVectorType>(V->getType())->getNumElements();
1427 assert((DemandedElts & ~EltMask) == 0 &&
"Invalid DemandedElts!");
1431 PoisonElts = EltMask;
1435 if (DemandedElts.
isZero()) {
1436 PoisonElts = EltMask;
1442 if (
auto *
C = dyn_cast<Constant>(V)) {
1448 Type *EltTy = cast<VectorType>(V->getType())->getElementType();
1451 for (
unsigned i = 0; i != VWidth; ++i) {
1452 if (!DemandedElts[i]) {
1458 Constant *Elt =
C->getAggregateElement(i);
1459 if (!Elt)
return nullptr;
1462 if (isa<PoisonValue>(Elt))
1468 return NewCV !=
C ? NewCV :
nullptr;
1475 if (!AllowMultipleUsers) {
1479 if (!V->hasOneUse()) {
1488 DemandedElts = EltMask;
1493 if (!
I)
return nullptr;
1495 bool MadeChange =
false;
1496 auto simplifyAndSetOp = [&](
Instruction *Inst,
unsigned OpNum,
1498 auto *II = dyn_cast<IntrinsicInst>(Inst);
1506 APInt PoisonElts2(VWidth, 0);
1507 APInt PoisonElts3(VWidth, 0);
1508 switch (
I->getOpcode()) {
1511 case Instruction::GetElementPtr: {
1521 if (mayIndexStructType(cast<GetElementPtrInst>(*
I)))
1529 for (
unsigned i = 0; i <
I->getNumOperands(); i++) {
1533 PoisonElts = EltMask;
1536 if (
I->getOperand(i)->getType()->isVectorTy()) {
1537 APInt PoisonEltsOp(VWidth, 0);
1538 simplifyAndSetOp(
I, i, DemandedElts, PoisonEltsOp);
1543 PoisonElts |= PoisonEltsOp;
1549 case Instruction::InsertElement: {
1556 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts2);
1562 unsigned IdxNo =
Idx->getZExtValue();
1563 APInt PreInsertDemandedElts = DemandedElts;
1565 PreInsertDemandedElts.
clearBit(IdxNo);
1573 if (PreInsertDemandedElts == 0 &&
1580 simplifyAndSetOp(
I, 0, PreInsertDemandedElts, PoisonElts);
1584 if (IdxNo >= VWidth || !DemandedElts[IdxNo]) {
1586 return I->getOperand(0);
1593 case Instruction::ShuffleVector: {
1594 auto *Shuffle = cast<ShuffleVectorInst>(
I);
1595 assert(Shuffle->getOperand(0)->getType() ==
1596 Shuffle->getOperand(1)->getType() &&
1597 "Expected shuffle operands to have same type");
1598 unsigned OpWidth = cast<FixedVectorType>(Shuffle->getOperand(0)->getType())
1602 if (
all_of(Shuffle->getShuffleMask(), [](
int Elt) { return Elt == 0; }) &&
1604 if (!isa<PoisonValue>(
I->getOperand(1))) {
1608 APInt LeftDemanded(OpWidth, 1);
1609 APInt LHSPoisonElts(OpWidth, 0);
1610 simplifyAndSetOp(
I, 0, LeftDemanded, LHSPoisonElts);
1611 if (LHSPoisonElts[0])
1612 PoisonElts = EltMask;
1618 APInt LeftDemanded(OpWidth, 0), RightDemanded(OpWidth, 0);
1619 for (
unsigned i = 0; i < VWidth; i++) {
1620 if (DemandedElts[i]) {
1621 unsigned MaskVal = Shuffle->getMaskValue(i);
1622 if (MaskVal != -1u) {
1623 assert(MaskVal < OpWidth * 2 &&
1624 "shufflevector mask index out of range!");
1625 if (MaskVal < OpWidth)
1626 LeftDemanded.setBit(MaskVal);
1628 RightDemanded.
setBit(MaskVal - OpWidth);
1633 APInt LHSPoisonElts(OpWidth, 0);
1634 simplifyAndSetOp(
I, 0, LeftDemanded, LHSPoisonElts);
1636 APInt RHSPoisonElts(OpWidth, 0);
1637 simplifyAndSetOp(
I, 1, RightDemanded, RHSPoisonElts);
1650 if (VWidth == OpWidth) {
1651 bool IsIdentityShuffle =
true;
1652 for (
unsigned i = 0; i < VWidth; i++) {
1653 unsigned MaskVal = Shuffle->getMaskValue(i);
1654 if (DemandedElts[i] && i != MaskVal) {
1655 IsIdentityShuffle =
false;
1659 if (IsIdentityShuffle)
1660 return Shuffle->getOperand(0);
1663 bool NewPoisonElts =
false;
1664 unsigned LHSIdx = -1u, LHSValIdx = -1u;
1665 unsigned RHSIdx = -1u, RHSValIdx = -1u;
1666 bool LHSUniform =
true;
1667 bool RHSUniform =
true;
1668 for (
unsigned i = 0; i < VWidth; i++) {
1669 unsigned MaskVal = Shuffle->getMaskValue(i);
1670 if (MaskVal == -1u) {
1672 }
else if (!DemandedElts[i]) {
1673 NewPoisonElts =
true;
1675 }
else if (MaskVal < OpWidth) {
1676 if (LHSPoisonElts[MaskVal]) {
1677 NewPoisonElts =
true;
1680 LHSIdx = LHSIdx == -1u ? i : OpWidth;
1681 LHSValIdx = LHSValIdx == -1u ? MaskVal : OpWidth;
1682 LHSUniform = LHSUniform && (MaskVal == i);
1685 if (RHSPoisonElts[MaskVal - OpWidth]) {
1686 NewPoisonElts =
true;
1689 RHSIdx = RHSIdx == -1u ? i : OpWidth;
1690 RHSValIdx = RHSValIdx == -1u ? MaskVal - OpWidth : OpWidth;
1691 RHSUniform = RHSUniform && (MaskVal - OpWidth == i);
1701 cast<FixedVectorType>(Shuffle->getType())->getNumElements()) {
1707 if (LHSIdx < OpWidth && RHSUniform) {
1708 if (
auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(0))) {
1709 Op = Shuffle->getOperand(1);
1710 Value = CV->getOperand(LHSValIdx);
1714 if (RHSIdx < OpWidth && LHSUniform) {
1715 if (
auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(1))) {
1716 Op = Shuffle->getOperand(0);
1717 Value = CV->getOperand(RHSValIdx);
1730 if (NewPoisonElts) {
1733 for (
unsigned i = 0; i < VWidth; ++i) {
1737 Elts.
push_back(Shuffle->getMaskValue(i));
1739 Shuffle->setShuffleMask(Elts);
1744 case Instruction::Select: {
1754 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1758 APInt DemandedLHS(DemandedElts), DemandedRHS(DemandedElts);
1759 if (
auto *CV = dyn_cast<ConstantVector>(Sel->
getCondition())) {
1760 for (
unsigned i = 0; i < VWidth; i++) {
1764 if (isa<ConstantExpr>(CElt))
1770 DemandedLHS.clearBit(i);
1776 simplifyAndSetOp(
I, 1, DemandedLHS, PoisonElts2);
1777 simplifyAndSetOp(
I, 2, DemandedRHS, PoisonElts3);
1781 PoisonElts = PoisonElts2 & PoisonElts3;
1784 case Instruction::BitCast: {
1786 VectorType *VTy = dyn_cast<VectorType>(
I->getOperand(0)->getType());
1788 unsigned InVWidth = cast<FixedVectorType>(VTy)->getNumElements();
1789 APInt InputDemandedElts(InVWidth, 0);
1790 PoisonElts2 =
APInt(InVWidth, 0);
1793 if (VWidth == InVWidth) {
1797 InputDemandedElts = DemandedElts;
1798 }
else if ((VWidth % InVWidth) == 0) {
1802 Ratio = VWidth / InVWidth;
1803 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1804 if (DemandedElts[OutIdx])
1805 InputDemandedElts.
setBit(OutIdx / Ratio);
1806 }
else if ((InVWidth % VWidth) == 0) {
1810 Ratio = InVWidth / VWidth;
1811 for (
unsigned InIdx = 0; InIdx != InVWidth; ++InIdx)
1812 if (DemandedElts[InIdx / Ratio])
1813 InputDemandedElts.
setBit(InIdx);
1819 simplifyAndSetOp(
I, 0, InputDemandedElts, PoisonElts2);
1821 if (VWidth == InVWidth) {
1822 PoisonElts = PoisonElts2;
1823 }
else if ((VWidth % InVWidth) == 0) {
1827 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1828 if (PoisonElts2[OutIdx / Ratio])
1829 PoisonElts.
setBit(OutIdx);
1830 }
else if ((InVWidth % VWidth) == 0) {
1834 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) {
1837 PoisonElts.
setBit(OutIdx);
1844 case Instruction::FPTrunc:
1845 case Instruction::FPExt:
1846 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1849 case Instruction::Call: {
1853 case Intrinsic::masked_gather:
1854 case Intrinsic::masked_load: {
1859 DemandedPassThrough(DemandedElts);
1860 if (
auto *CV = dyn_cast<ConstantVector>(II->
getOperand(2)))
1861 for (
unsigned i = 0; i < VWidth; i++) {
1864 DemandedPtrs.clearBit(i);
1869 simplifyAndSetOp(II, 0, DemandedPtrs, PoisonElts2);
1870 simplifyAndSetOp(II, 3, DemandedPassThrough, PoisonElts3);
1874 PoisonElts = PoisonElts2 & PoisonElts3;
1880 *II, DemandedElts, PoisonElts, PoisonElts2, PoisonElts3,
1914 if (DemandedElts == 1 && !
X->hasOneUse() && !
Y->hasOneUse() &&
1917 auto findShufBO = [&](
bool MatchShufAsOp0) ->
User * {
1922 Value *ShufOp = MatchShufAsOp0 ?
X :
Y;
1923 Value *OtherOp = MatchShufAsOp0 ?
Y :
X;
1939 if (
User *ShufBO = findShufBO(
true))
1941 if (
User *ShufBO = findShufBO(
false))
1945 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1946 simplifyAndSetOp(
I, 1, DemandedElts, PoisonElts2);
1950 PoisonElts &= PoisonElts2;
1958 return MadeChange ?
I :
nullptr;
1984 Type *VTy = V->getType();
1988 if (DemandedMask ==
fcNone)
1998 Value *FoldedToConst =
2000 return FoldedToConst == V ? nullptr : FoldedToConst;
2003 if (!
I->hasOneUse())
2007 switch (
I->getOpcode()) {
2008 case Instruction::FNeg: {
2015 case Instruction::Call: {
2018 case Intrinsic::fabs:
2024 case Intrinsic::arithmetic_fence:
2028 case Intrinsic::copysign: {
2036 I->setOperand(1, ConstantFP::get(VTy, -1.0));
2058 case Instruction::Select: {
2065 return I->getOperand(2);
2067 return I->getOperand(1);
2070 Known = KnownLHS | KnownRHS;
2085 Use &U =
I->getOperandUse(OpNo);
2090 if (
Instruction *OpInst = dyn_cast<Instruction>(U))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file provides internal interfaces used to implement the InstCombine.
static Constant * getFPClassConstant(Type *Ty, FPClassTest Mask)
For floating-point classes that resolve to a single bit pattern, return that value.
static cl::opt< bool > VerifyKnownBits("instcombine-verify-known-bits", cl::desc("Verify that computeKnownBits() and " "SimplifyDemandedBits() are consistent"), cl::Hidden, cl::init(false))
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static bool ShrinkDemandedConstant(Instruction *I, unsigned OpNo, const APInt &Demanded)
Check to see if the specified operand of the specified instruction is a constant integer.
This file provides the interface for the instcombine pass implementation.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
void clearBit(unsigned BitPosition)
Set a given bit to 0.
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
uint64_t getZExtValue() const
Get zero extended value.
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
unsigned popcount() const
Count the number of bits set.
APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
unsigned getActiveBits() const
Compute the number of active bits in the value.
APInt trunc(unsigned width) const
Truncate to new width.
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
APInt abs() const
Get the absolute value.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
void setSignBit()
Set the sign bit to 1.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
void clearAllBits()
Set every bit to 0.
unsigned countr_zero() const
Count the number of trailing zero bits.
unsigned countl_zero() const
The APInt version of std::countl_zero.
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
void setAllBits()
Set every bit to 1.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
void setLowBits(unsigned loBits)
Set the bottom loBits bits.
bool isOne() const
Determine if this is a value of 1.
void lshrInPlace(unsigned ShiftAmt)
Logical right-shift this APInt by ShiftAmt in place.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
BinaryOps getOpcode() const
Intrinsic::ID getIntrinsicID() const
Returns the intrinsic ID of the intrinsic called or Intrinsic::not_intrinsic if the called function i...
This class represents a function call, abstracting a target machine's calling convention.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr, BasicBlock::iterator InsertBefore)
This is the base class for all instructions that perform data casts.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
static Constant * getInfinity(Type *Ty, bool Negative=false)
static Constant * getZero(Type *Ty, bool Negative=false)
This is the shared class of boolean and integer constants.
const APInt & getValue() const
Return the constant as an APInt value reference.
static Constant * get(ArrayRef< Constant * > V)
This is an important base class in LLVM.
static Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
static Constant * getAllOnesValue(Type *Ty)
bool isAllOnesValue() const
Return true if this is the value that would be returned by getAllOnesValue.
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
CallInst * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *V, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
Value * CreateSExt(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Value * CreateNot(Value *V, const Twine &Name="")
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=false)
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", bool IsInBounds=false)
static InsertElementInst * Create(Value *Vec, Value *NewElt, Value *Idx, const Twine &NameStr, BasicBlock::iterator InsertBefore)
KnownFPClass computeKnownFPClass(Value *Val, FastMathFlags FMF, FPClassTest Interested=fcAllFlags, const Instruction *CtxI=nullptr, unsigned Depth=0) const
bool SimplifyDemandedBits(Instruction *I, unsigned Op, const APInt &DemandedMask, KnownBits &Known, unsigned Depth=0) override
This form of SimplifyDemandedBits simplifies the specified instruction operand if possible,...
Value * SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &PoisonElts, unsigned Depth=0, bool AllowMultipleUsers=false) override
The specified value produces a vector with any number of elements.
Value * SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known, unsigned Depth, Instruction *CxtI)
Attempts to replace V with a simpler value based on the demanded bits.
std::optional< std::pair< Intrinsic::ID, SmallVector< Value *, 3 > > > convertOrOfShiftsToFunnelShift(Instruction &Or)
Value * SimplifyMultipleUseDemandedBits(Instruction *I, const APInt &DemandedMask, KnownBits &Known, unsigned Depth, Instruction *CxtI)
Helper routine of SimplifyDemandedUseBits.
Value * simplifyShrShlDemandedBits(Instruction *Shr, const APInt &ShrOp1, Instruction *Shl, const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known)
Helper routine of SimplifyDemandedUseBits.
Value * SimplifyDemandedUseFPClass(Value *V, FPClassTest DemandedMask, KnownFPClass &Known, unsigned Depth, Instruction *CxtI)
Attempts to replace V with a simpler value based on the demanded floating-point classes.
bool SimplifyDemandedFPClass(Instruction *I, unsigned Op, FPClassTest DemandedMask, KnownFPClass &Known, unsigned Depth=0)
bool SimplifyDemandedInstructionBits(Instruction &Inst)
Tries to simplify operands to an integer instruction based on its demanded bits.
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Instruction * InsertNewInstWith(Instruction *New, BasicBlock::iterator Old)
Same as InsertNewInstBefore, but also sets the debug loc.
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
std::optional< Value * > targetSimplifyDemandedVectorEltsIntrinsic(IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts, APInt &UndefElts2, APInt &UndefElts3, std::function< void(Instruction *, unsigned, APInt, APInt &)> SimplifyAndSetOp)
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
std::optional< Value * > targetSimplifyDemandedUseBitsIntrinsic(IntrinsicInst &II, APInt DemandedMask, KnownBits &Known, bool &KnownBitsComputed)
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
void push(Instruction *I)
Push the instruction onto the worklist stack.
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This class represents the LLVM 'select' instruction.
const Value * getCondition() const
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isVectorTy() const
True if this is an instance of VectorType.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static IntegerType * getInt64Ty(LLVMContext &C)
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
iterator_range< user_iterator > users()
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
Base class of all SIMD vector types.
This class represents zero extension of integer types.
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
class_match< PoisonValue > m_Poison()
Match an arbitrary poison constant.
PtrAdd_match< PointerOpTy, OffsetOpTy > m_PtrAdd(const PointerOpTy &PointerOp, const OffsetOpTy &OffsetOp)
Matches GEP with i8 source element type.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
TwoOps_match< Val_t, Idx_t, Instruction::ExtractElement > m_ExtractElt(const Val_t &Val, const Idx_t &Idx)
Matches ExtractElementInst.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
auto m_Undef()
Match an arbitrary undef constant.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
bool haveNoCommonBitsSet(const WithCache< const Value * > &LHSCache, const WithCache< const Value * > &RHSCache, const SimplifyQuery &SQ)
Return true if LHS and RHS have no common bits set.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int countr_one(T Value)
Count the number of ones from the least significant bit to the first zero bit.
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
gep_type_iterator gep_type_end(const User *GEP)
void computeKnownBitsFromContext(const Value *V, KnownBits &Known, unsigned Depth, const SimplifyQuery &Q)
Merge bits known from context-dependent facts into Known.
KnownBits analyzeKnownBitsFromAndXorOr(const Operator *I, const KnownBits &KnownLHS, const KnownBits &KnownRHS, unsigned Depth, const SimplifyQuery &SQ)
Using KnownBits LHS/RHS produce the known bits for logic op (and/xor/or).
constexpr unsigned MaxAnalysisRecursionDepth
FPClassTest fneg(FPClassTest Mask)
Return the test mask which returns true if the value's sign bit is flipped.
FPClassTest
Floating-point class tests, supported by 'is_fpclass' intrinsic.
FPClassTest inverse_fabs(FPClassTest Mask)
Return the test mask which returns true after fabs is applied to the value.
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
constexpr int PoisonMaskElem
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
@ Or
Bitwise or logical OR of integers.
@ Xor
Bitwise or logical XOR of integers.
@ And
Bitwise or logical AND of integers.
FPClassTest unknown_sign(FPClassTest Mask)
Return the test mask which returns true if the value could have the same set of classes,...
constexpr unsigned BitWidth
gep_type_iterator gep_type_begin(const User *GEP)
unsigned Log2(Align A)
Returns the log2 of the alignment.
uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the largest uint64_t less than or equal to Value and is Skew mod Align.
This struct is a compact representation of a valid (non-zero power of two) alignment.
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
KnownBits anyextOrTrunc(unsigned BitWidth) const
Return known bits for an "any" extension or truncation of the value we're tracking.
bool isNonNegative() const
Returns true if this value is known to be non-negative.
void makeNonNegative()
Make this value non-negative.
static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for urem(LHS, RHS).
bool hasConflict() const
Returns true if there is conflicting information.
unsigned getBitWidth() const
Get the bit width of this value.
void resetAll()
Resets the known state of all bits.
KnownBits intersectWith(const KnownBits &RHS) const
Returns KnownBits information that is known to be true for both this and RHS.
KnownBits sext(unsigned BitWidth) const
Return known bits for a sign extension of the value we're tracking.
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for udiv(LHS, RHS).
static KnownBits computeForAddSub(bool Add, bool NSW, bool NUW, const KnownBits &LHS, const KnownBits &RHS)
Compute known bits resulting from adding LHS and RHS.
bool isNegative() const
Returns true if this value is known to be negative.
static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
FPClassTest KnownFPClasses
Floating-point classes the value could be one of.
void copysign(const KnownFPClass &Sign)
bool isKnownNever(FPClassTest Mask) const
Return true if it's known this can never be one of the mask entries.
SimplifyQuery getWithInstruction(const Instruction *I) const