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])
670 Constant *LeftShiftAmtC = ConstantInt::get(VTy, ShiftAmt);
675 Instruction *Lshr = BinaryOperator::CreateLShr(NewC,
X);
680 APInt DemandedMaskIn(DemandedMask.
lshr(ShiftAmt));
705 I->dropPoisonGeneratingFlags();
713 case Instruction::LShr: {
719 if (
I->hasOneUse()) {
720 auto *Inst = dyn_cast<Instruction>(
I->user_back());
721 if (Inst && Inst->getOpcode() == BinaryOperator::Or) {
723 auto [IID, FShiftArgs] = *Opt;
724 if ((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
725 FShiftArgs[0] == FShiftArgs[1])
739 if (SignBits >= NumHiDemandedBits)
740 return I->getOperand(0);
749 Constant *RightShiftAmtC = ConstantInt::get(VTy, ShiftAmt);
753 RightShiftAmtC,
DL) ==
C) {
761 APInt DemandedMaskIn(DemandedMask.
shl(ShiftAmt));
764 I->dropPoisonGeneratingFlags();
777 case Instruction::AShr: {
783 if (SignBits >= NumHiDemandedBits)
784 return I->getOperand(0);
790 if (DemandedMask.
isOne()) {
793 I->getOperand(0),
I->getOperand(1),
I->getName());
802 APInt DemandedMaskIn(DemandedMask.
shl(ShiftAmt));
810 I->dropPoisonGeneratingFlags();
828 LShr->
setIsExact(cast<BinaryOperator>(
I)->isExact());
832 Known.
One |= HighBits;
835 Known.
Zero &= ~HighBits;
842 case Instruction::UDiv: {
848 APInt DemandedMaskIn =
853 I->dropPoisonGeneratingFlags();
858 cast<BinaryOperator>(
I)->isExact());
864 case Instruction::SRem: {
872 if (
RA.isPowerOf2()) {
873 if (DemandedMask.
ult(
RA))
874 return I->getOperand(0);
882 Known.
Zero = LHSKnown.Zero & LowBits;
883 Known.
One = LHSKnown.One & LowBits;
887 if (LHSKnown.isNonNegative() || LowBits.
isSubsetOf(LHSKnown.Zero))
888 Known.
Zero |= ~LowBits;
892 if (LHSKnown.isNegative() && LowBits.
intersects(LHSKnown.One))
893 Known.
One |= ~LowBits;
903 case Instruction::URem: {
912 case Instruction::Call: {
913 bool KnownBitsComputed =
false;
915 switch (II->getIntrinsicID()) {
916 case Intrinsic::abs: {
917 if (DemandedMask == 1)
918 return II->getArgOperand(0);
921 case Intrinsic::ctpop: {
929 II->getModule(), Intrinsic::ctpop, VTy);
934 case Intrinsic::bswap: {
951 NewVal = BinaryOperator::CreateLShr(
952 II->getArgOperand(0), ConstantInt::get(VTy, NLZ - NTZ));
954 NewVal = BinaryOperator::CreateShl(
955 II->getArgOperand(0), ConstantInt::get(VTy, NTZ - NLZ));
961 case Intrinsic::ptrmask: {
962 unsigned MaskWidth =
I->getOperand(1)->getType()->getScalarSizeInBits();
967 I, 1, (DemandedMask & ~LHSKnown.Zero).zextOrTrunc(MaskWidth),
968 RHSKnown,
Depth + 1))
974 assert(!LHSKnown.hasConflict() &&
"Bits known to be one AND zero?");
976 Known = LHSKnown & RHSKnown;
977 KnownBitsComputed =
true;
992 if (DemandedMask.
isSubsetOf(RHSKnown.One | LHSKnown.Zero))
993 return I->getOperand(0);
997 I, 1, (DemandedMask & ~LHSKnown.Zero).zextOrTrunc(MaskWidth)))
1007 if (
match(
I, m_Intrinsic<Intrinsic::ptrmask>(
1012 if (!LHSKnown.isZero()) {
1013 const unsigned trailingZeros = LHSKnown.countMinTrailingZeros();
1016 uint64_t HighBitsGEPIndex = GEPIndex & ~PointerAlignBits;
1018 GEPIndex & PointerAlignBits & PtrMaskImmediate;
1020 uint64_t MaskedGEPIndex = HighBitsGEPIndex | MaskedLowBitsGEPIndex;
1022 if (MaskedGEPIndex != GEPIndex) {
1023 auto *
GEP = cast<GetElementPtrInst>(II->getArgOperand(0));
1025 Type *GEPIndexType =
1028 GEP->getSourceElementType(), InnerPtr,
1029 ConstantInt::get(GEPIndexType, MaskedGEPIndex),
1030 GEP->getName(),
GEP->isInBounds());
1041 case Intrinsic::fshr:
1042 case Intrinsic::fshl: {
1050 if (II->getIntrinsicID() == Intrinsic::fshr)
1053 APInt DemandedMaskLHS(DemandedMask.
lshr(ShiftAmt));
1055 if (
I->getOperand(0) !=
I->getOperand(1)) {
1064 if (DemandedMaskLHS.
isSubsetOf(LHSKnown.Zero | LHSKnown.One) &&
1078 Known.
Zero = LHSKnown.Zero.
shl(ShiftAmt) |
1080 Known.
One = LHSKnown.One.
shl(ShiftAmt) |
1082 KnownBitsComputed =
true;
1085 case Intrinsic::umax: {
1092 CTZ >=
C->getActiveBits())
1093 return II->getArgOperand(0);
1096 case Intrinsic::umin: {
1104 CTZ >=
C->getBitWidth() -
C->countl_one())
1105 return II->getArgOperand(0);
1111 *II, DemandedMask, Known, KnownBitsComputed);
1119 if (!KnownBitsComputed)
1125 if (V->getType()->isPointerTy()) {
1126 Align Alignment = V->getPointerAlignment(
DL);
1134 if (!V->getType()->isPointerTy() && DemandedMask.
isSubsetOf(Known.
Zero | Known.
One))
1139 if (Known != ReferenceKnown) {
1140 errs() <<
"Mismatched known bits for " << *V <<
" in "
1141 <<
I->getFunction()->getName() <<
"\n";
1142 errs() <<
"computeKnownBits(): " << ReferenceKnown <<
"\n";
1143 errs() <<
"SimplifyDemandedBits(): " << Known <<
"\n";
1158 Type *ITy =
I->getType();
1167 switch (
I->getOpcode()) {
1168 case Instruction::And: {
1183 return I->getOperand(0);
1185 return I->getOperand(1);
1189 case Instruction::Or: {
1206 return I->getOperand(0);
1208 return I->getOperand(1);
1212 case Instruction::Xor: {
1228 return I->getOperand(0);
1230 return I->getOperand(1);
1234 case Instruction::Add: {
1242 return I->getOperand(0);
1246 return I->getOperand(1);
1248 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
1249 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
1255 case Instruction::Sub: {
1263 return I->getOperand(0);
1265 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
1266 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
1273 case Instruction::AShr: {
1286 const APInt *ShiftRC;
1287 const APInt *ShiftLC;
1335 if (!ShlOp1 || !ShrOp1)
1349 Known.
Zero &= DemandedMask;
1354 bool isLshr = (Shr->
getOpcode() == Instruction::LShr);
1355 BitMask1 = isLshr ? (BitMask1.
lshr(ShrAmt) << ShlAmt) :
1356 (BitMask1.
ashr(ShrAmt) << ShlAmt);
1358 if (ShrAmt <= ShlAmt) {
1359 BitMask2 <<= (ShlAmt - ShrAmt);
1361 BitMask2 = isLshr ? BitMask2.
lshr(ShrAmt - ShlAmt):
1362 BitMask2.
ashr(ShrAmt - ShlAmt);
1366 if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) {
1367 if (ShrAmt == ShlAmt)
1374 if (ShrAmt < ShlAmt) {
1376 New = BinaryOperator::CreateShl(VarX, Amt);
1382 New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) :
1383 BinaryOperator::CreateAShr(VarX, Amt);
1384 if (cast<BinaryOperator>(Shr)->isExact())
1385 New->setIsExact(
true);
1411 bool AllowMultipleUsers) {
1414 if (isa<ScalableVectorType>(V->getType()))
1417 unsigned VWidth = cast<FixedVectorType>(V->getType())->getNumElements();
1419 assert((DemandedElts & ~EltMask) == 0 &&
"Invalid DemandedElts!");
1423 PoisonElts = EltMask;
1427 if (DemandedElts.
isZero()) {
1428 PoisonElts = EltMask;
1434 if (
auto *
C = dyn_cast<Constant>(V)) {
1440 Type *EltTy = cast<VectorType>(V->getType())->getElementType();
1443 for (
unsigned i = 0; i != VWidth; ++i) {
1444 if (!DemandedElts[i]) {
1450 Constant *Elt =
C->getAggregateElement(i);
1451 if (!Elt)
return nullptr;
1454 if (isa<PoisonValue>(Elt))
1460 return NewCV !=
C ? NewCV :
nullptr;
1467 if (!AllowMultipleUsers) {
1471 if (!V->hasOneUse()) {
1480 DemandedElts = EltMask;
1485 if (!
I)
return nullptr;
1487 bool MadeChange =
false;
1488 auto simplifyAndSetOp = [&](
Instruction *Inst,
unsigned OpNum,
1490 auto *II = dyn_cast<IntrinsicInst>(Inst);
1498 APInt PoisonElts2(VWidth, 0);
1499 APInt PoisonElts3(VWidth, 0);
1500 switch (
I->getOpcode()) {
1503 case Instruction::GetElementPtr: {
1513 if (mayIndexStructType(cast<GetElementPtrInst>(*
I)))
1521 for (
unsigned i = 0; i <
I->getNumOperands(); i++) {
1525 PoisonElts = EltMask;
1528 if (
I->getOperand(i)->getType()->isVectorTy()) {
1529 APInt PoisonEltsOp(VWidth, 0);
1530 simplifyAndSetOp(
I, i, DemandedElts, PoisonEltsOp);
1535 PoisonElts |= PoisonEltsOp;
1541 case Instruction::InsertElement: {
1548 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts2);
1554 unsigned IdxNo =
Idx->getZExtValue();
1555 APInt PreInsertDemandedElts = DemandedElts;
1557 PreInsertDemandedElts.
clearBit(IdxNo);
1565 if (PreInsertDemandedElts == 0 &&
1572 simplifyAndSetOp(
I, 0, PreInsertDemandedElts, PoisonElts);
1576 if (IdxNo >= VWidth || !DemandedElts[IdxNo]) {
1578 return I->getOperand(0);
1585 case Instruction::ShuffleVector: {
1586 auto *Shuffle = cast<ShuffleVectorInst>(
I);
1587 assert(Shuffle->getOperand(0)->getType() ==
1588 Shuffle->getOperand(1)->getType() &&
1589 "Expected shuffle operands to have same type");
1590 unsigned OpWidth = cast<FixedVectorType>(Shuffle->getOperand(0)->getType())
1594 if (
all_of(Shuffle->getShuffleMask(), [](
int Elt) { return Elt == 0; }) &&
1596 if (!isa<PoisonValue>(
I->getOperand(1))) {
1600 APInt LeftDemanded(OpWidth, 1);
1601 APInt LHSPoisonElts(OpWidth, 0);
1602 simplifyAndSetOp(
I, 0, LeftDemanded, LHSPoisonElts);
1603 if (LHSPoisonElts[0])
1604 PoisonElts = EltMask;
1610 APInt LeftDemanded(OpWidth, 0), RightDemanded(OpWidth, 0);
1611 for (
unsigned i = 0; i < VWidth; i++) {
1612 if (DemandedElts[i]) {
1613 unsigned MaskVal = Shuffle->getMaskValue(i);
1614 if (MaskVal != -1u) {
1615 assert(MaskVal < OpWidth * 2 &&
1616 "shufflevector mask index out of range!");
1617 if (MaskVal < OpWidth)
1618 LeftDemanded.setBit(MaskVal);
1620 RightDemanded.
setBit(MaskVal - OpWidth);
1625 APInt LHSPoisonElts(OpWidth, 0);
1626 simplifyAndSetOp(
I, 0, LeftDemanded, LHSPoisonElts);
1628 APInt RHSPoisonElts(OpWidth, 0);
1629 simplifyAndSetOp(
I, 1, RightDemanded, RHSPoisonElts);
1642 if (VWidth == OpWidth) {
1643 bool IsIdentityShuffle =
true;
1644 for (
unsigned i = 0; i < VWidth; i++) {
1645 unsigned MaskVal = Shuffle->getMaskValue(i);
1646 if (DemandedElts[i] && i != MaskVal) {
1647 IsIdentityShuffle =
false;
1651 if (IsIdentityShuffle)
1652 return Shuffle->getOperand(0);
1655 bool NewPoisonElts =
false;
1656 unsigned LHSIdx = -1u, LHSValIdx = -1u;
1657 unsigned RHSIdx = -1u, RHSValIdx = -1u;
1658 bool LHSUniform =
true;
1659 bool RHSUniform =
true;
1660 for (
unsigned i = 0; i < VWidth; i++) {
1661 unsigned MaskVal = Shuffle->getMaskValue(i);
1662 if (MaskVal == -1u) {
1664 }
else if (!DemandedElts[i]) {
1665 NewPoisonElts =
true;
1667 }
else if (MaskVal < OpWidth) {
1668 if (LHSPoisonElts[MaskVal]) {
1669 NewPoisonElts =
true;
1672 LHSIdx = LHSIdx == -1u ? i : OpWidth;
1673 LHSValIdx = LHSValIdx == -1u ? MaskVal : OpWidth;
1674 LHSUniform = LHSUniform && (MaskVal == i);
1677 if (RHSPoisonElts[MaskVal - OpWidth]) {
1678 NewPoisonElts =
true;
1681 RHSIdx = RHSIdx == -1u ? i : OpWidth;
1682 RHSValIdx = RHSValIdx == -1u ? MaskVal - OpWidth : OpWidth;
1683 RHSUniform = RHSUniform && (MaskVal - OpWidth == i);
1693 cast<FixedVectorType>(Shuffle->getType())->getNumElements()) {
1699 if (LHSIdx < OpWidth && RHSUniform) {
1700 if (
auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(0))) {
1701 Op = Shuffle->getOperand(1);
1702 Value = CV->getOperand(LHSValIdx);
1706 if (RHSIdx < OpWidth && LHSUniform) {
1707 if (
auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(1))) {
1708 Op = Shuffle->getOperand(0);
1709 Value = CV->getOperand(RHSValIdx);
1722 if (NewPoisonElts) {
1725 for (
unsigned i = 0; i < VWidth; ++i) {
1729 Elts.
push_back(Shuffle->getMaskValue(i));
1731 Shuffle->setShuffleMask(Elts);
1736 case Instruction::Select: {
1746 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1750 APInt DemandedLHS(DemandedElts), DemandedRHS(DemandedElts);
1751 if (
auto *CV = dyn_cast<ConstantVector>(Sel->
getCondition())) {
1752 for (
unsigned i = 0; i < VWidth; i++) {
1756 if (isa<ConstantExpr>(CElt))
1762 DemandedLHS.clearBit(i);
1768 simplifyAndSetOp(
I, 1, DemandedLHS, PoisonElts2);
1769 simplifyAndSetOp(
I, 2, DemandedRHS, PoisonElts3);
1773 PoisonElts = PoisonElts2 & PoisonElts3;
1776 case Instruction::BitCast: {
1778 VectorType *VTy = dyn_cast<VectorType>(
I->getOperand(0)->getType());
1780 unsigned InVWidth = cast<FixedVectorType>(VTy)->getNumElements();
1781 APInt InputDemandedElts(InVWidth, 0);
1782 PoisonElts2 =
APInt(InVWidth, 0);
1785 if (VWidth == InVWidth) {
1789 InputDemandedElts = DemandedElts;
1790 }
else if ((VWidth % InVWidth) == 0) {
1794 Ratio = VWidth / InVWidth;
1795 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1796 if (DemandedElts[OutIdx])
1797 InputDemandedElts.
setBit(OutIdx / Ratio);
1798 }
else if ((InVWidth % VWidth) == 0) {
1802 Ratio = InVWidth / VWidth;
1803 for (
unsigned InIdx = 0; InIdx != InVWidth; ++InIdx)
1804 if (DemandedElts[InIdx / Ratio])
1805 InputDemandedElts.
setBit(InIdx);
1811 simplifyAndSetOp(
I, 0, InputDemandedElts, PoisonElts2);
1813 if (VWidth == InVWidth) {
1814 PoisonElts = PoisonElts2;
1815 }
else if ((VWidth % InVWidth) == 0) {
1819 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1820 if (PoisonElts2[OutIdx / Ratio])
1821 PoisonElts.
setBit(OutIdx);
1822 }
else if ((InVWidth % VWidth) == 0) {
1826 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) {
1829 PoisonElts.
setBit(OutIdx);
1836 case Instruction::FPTrunc:
1837 case Instruction::FPExt:
1838 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1841 case Instruction::Call: {
1845 case Intrinsic::masked_gather:
1846 case Intrinsic::masked_load: {
1851 DemandedPassThrough(DemandedElts);
1852 if (
auto *CV = dyn_cast<ConstantVector>(II->
getOperand(2)))
1853 for (
unsigned i = 0; i < VWidth; i++) {
1856 DemandedPtrs.clearBit(i);
1861 simplifyAndSetOp(II, 0, DemandedPtrs, PoisonElts2);
1862 simplifyAndSetOp(II, 3, DemandedPassThrough, PoisonElts3);
1866 PoisonElts = PoisonElts2 & PoisonElts3;
1872 *II, DemandedElts, PoisonElts, PoisonElts2, PoisonElts3,
1906 if (DemandedElts == 1 && !
X->hasOneUse() && !
Y->hasOneUse() &&
1909 auto findShufBO = [&](
bool MatchShufAsOp0) ->
User * {
1914 Value *ShufOp = MatchShufAsOp0 ?
X :
Y;
1915 Value *OtherOp = MatchShufAsOp0 ?
Y :
X;
1931 if (
User *ShufBO = findShufBO(
true))
1933 if (
User *ShufBO = findShufBO(
false))
1937 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1938 simplifyAndSetOp(
I, 1, DemandedElts, PoisonElts2);
1942 PoisonElts &= PoisonElts2;
1950 return MadeChange ?
I :
nullptr;
1976 Type *VTy = V->getType();
1980 if (DemandedMask ==
fcNone)
1990 Value *FoldedToConst =
1992 return FoldedToConst == V ? nullptr : FoldedToConst;
1995 if (!
I->hasOneUse())
1999 switch (
I->getOpcode()) {
2000 case Instruction::FNeg: {
2007 case Instruction::Call: {
2010 case Intrinsic::fabs:
2016 case Intrinsic::arithmetic_fence:
2020 case Intrinsic::copysign: {
2028 I->setOperand(1, ConstantFP::get(VTy, -1.0));
2050 case Instruction::Select: {
2057 return I->getOperand(2);
2059 return I->getOperand(1);
2062 Known = KnownLHS | KnownRHS;
2077 Use &U =
I->getOperandUse(OpNo);
2082 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 * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
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 * 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