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: {
224 return I->getOperand(0);
226 return I->getOperand(1);
234 case Instruction::Or: {
240 I->dropPoisonGeneratingFlags();
255 return I->getOperand(0);
257 return I->getOperand(1);
264 if (!cast<PossiblyDisjointInst>(
I)->isDisjoint()) {
266 RHSCache(
I->getOperand(1), RHSKnown);
268 cast<PossiblyDisjointInst>(
I)->setIsDisjoint(
true);
275 case Instruction::Xor: {
280 if (DemandedMask == 1 &&
301 return I->getOperand(0);
303 return I->getOperand(1);
310 BinaryOperator::CreateOr(
I->getOperand(0),
I->getOperand(1));
312 cast<PossiblyDisjointInst>(
Or)->setIsDisjoint(
true);
324 ~RHSKnown.
One & DemandedMask);
334 if ((*
C | ~DemandedMask).isAllOnes()) {
348 if (
Instruction *LHSInst = dyn_cast<Instruction>(
I->getOperand(0))) {
350 if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() &&
353 (LHSKnown.One & RHSKnown.
One & DemandedMask) != 0) {
354 APInt NewMask = ~(LHSKnown.One & RHSKnown.
One & DemandedMask);
357 Instruction *NewAnd = BinaryOperator::CreateAnd(
I->getOperand(0), AndC);
361 Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC);
367 case Instruction::Select: {
377 auto CanonicalizeSelectConstant = [](
Instruction *
I,
unsigned OpNo,
378 const APInt &DemandedMask) {
399 if ((*CmpC & DemandedMask) == (*SelC & DemandedMask)) {
400 I->setOperand(OpNo, ConstantInt::get(
I->getType(), *CmpC));
405 if (CanonicalizeSelectConstant(
I, 1, DemandedMask) ||
406 CanonicalizeSelectConstant(
I, 2, DemandedMask))
413 case Instruction::Trunc: {
432 case Instruction::ZExt: {
433 unsigned SrcBitWidth =
I->getOperand(0)->getType()->getScalarSizeInBits();
440 I->dropPoisonGeneratingFlags();
444 if (
I->getOpcode() == Instruction::ZExt &&
I->hasNonNeg() &&
451 case Instruction::SExt: {
453 unsigned SrcBitWidth =
I->getOperand(0)->getType()->getScalarSizeInBits();
455 APInt InputDemandedBits = DemandedMask.
trunc(SrcBitWidth);
460 InputDemandedBits.
setBit(SrcBitWidth-1);
481 case Instruction::Add: {
482 if ((DemandedMask & 1) == 0) {
488 X->getType()->isIntOrIntVectorTy(1) &&
X->getType() ==
Y->getType()) {
503 X->getType()->isIntOrIntVectorTy(1) &&
X->getType() ==
Y->getType() &&
504 (
I->getOperand(0)->hasOneUse() ||
I->getOperand(1)->hasOneUse())) {
525 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
531 APInt DemandedFromLHS = DemandedFromOps;
535 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
540 return I->getOperand(0);
541 if (DemandedFromOps.
isSubsetOf(LHSKnown.Zero))
542 return I->getOperand(1);
556 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
557 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
561 case Instruction::Sub: {
568 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
574 APInt DemandedFromLHS = DemandedFromOps;
578 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
583 return I->getOperand(0);
586 if (DemandedFromOps.
isOne() && DemandedFromOps.
isSubsetOf(LHSKnown.Zero))
587 return I->getOperand(1);
590 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
591 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
595 case Instruction::Mul: {
596 APInt DemandedFromOps;
597 if (simplifyOperandsBasedOnUnusedHighBits(DemandedFromOps))
607 Constant *ShiftC = ConstantInt::get(VTy, CTZ);
608 Instruction *Shl = BinaryOperator::CreateShl(
I->getOperand(0), ShiftC);
615 if (
I->getOperand(0) ==
I->getOperand(1) && DemandedMask.
ult(4)) {
616 Constant *One = ConstantInt::get(VTy, 1);
617 Instruction *And1 = BinaryOperator::CreateAnd(
I->getOperand(0), One);
624 case Instruction::Shl: {
629 if (
Instruction *Shr = dyn_cast<Instruction>(
I->getOperand(0)))
631 DemandedMask, Known))
635 if (
I->hasOneUse()) {
636 auto *Inst = dyn_cast<Instruction>(
I->user_back());
637 if (Inst && Inst->getOpcode() == BinaryOperator::Or) {
639 auto [IID, FShiftArgs] = *Opt;
640 if ((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
641 FShiftArgs[0] == FShiftArgs[1]) {
653 if (
I->hasNoSignedWrap()) {
657 if (SignBits > ShiftAmt && SignBits - ShiftAmt >= NumHiDemandedBits)
658 return I->getOperand(0);
668 Constant *LeftShiftAmtC = ConstantInt::get(VTy, ShiftAmt);
672 LeftShiftAmtC,
DL) ==
C) {
673 Instruction *Lshr = BinaryOperator::CreateLShr(NewC,
X);
679 APInt DemandedMaskIn(DemandedMask.
lshr(ShiftAmt));
703 I->dropPoisonGeneratingFlags();
711 case Instruction::LShr: {
717 if (
I->hasOneUse()) {
718 auto *Inst = dyn_cast<Instruction>(
I->user_back());
719 if (Inst && Inst->getOpcode() == BinaryOperator::Or) {
721 auto [IID, FShiftArgs] = *Opt;
722 if ((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
723 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();
776 case Instruction::AShr: {
782 if (SignBits >= NumHiDemandedBits)
783 return I->getOperand(0);
789 if (DemandedMask.
isOne()) {
792 I->getOperand(0),
I->getOperand(1),
I->getName());
801 APInt DemandedMaskIn(DemandedMask.
shl(ShiftAmt));
809 I->dropPoisonGeneratingFlags();
826 LShr->
setIsExact(cast<BinaryOperator>(
I)->isExact());
830 Known.
One |= HighBits;
833 Known.
Zero &= ~HighBits;
840 case Instruction::UDiv: {
846 APInt DemandedMaskIn =
851 I->dropPoisonGeneratingFlags();
856 cast<BinaryOperator>(
I)->isExact());
862 case Instruction::SRem: {
870 if (
RA.isPowerOf2()) {
871 if (DemandedMask.
ult(
RA))
872 return I->getOperand(0);
880 Known.
Zero = LHSKnown.Zero & LowBits;
881 Known.
One = LHSKnown.One & LowBits;
885 if (LHSKnown.isNonNegative() || LowBits.
isSubsetOf(LHSKnown.Zero))
886 Known.
Zero |= ~LowBits;
890 if (LHSKnown.isNegative() && LowBits.
intersects(LHSKnown.One))
891 Known.
One |= ~LowBits;
900 case Instruction::Call: {
901 bool KnownBitsComputed =
false;
903 switch (
II->getIntrinsicID()) {
904 case Intrinsic::abs: {
905 if (DemandedMask == 1)
906 return II->getArgOperand(0);
909 case Intrinsic::ctpop: {
917 II->getModule(), Intrinsic::ctpop, VTy);
922 case Intrinsic::bswap: {
939 NewVal = BinaryOperator::CreateLShr(
940 II->getArgOperand(0), ConstantInt::get(VTy, NLZ - NTZ));
942 NewVal = BinaryOperator::CreateShl(
943 II->getArgOperand(0), ConstantInt::get(VTy, NTZ - NLZ));
949 case Intrinsic::ptrmask: {
950 unsigned MaskWidth =
I->getOperand(1)->getType()->getScalarSizeInBits();
955 I, 1, (DemandedMask & ~LHSKnown.Zero).zextOrTrunc(MaskWidth),
956 RHSKnown,
Depth + 1))
962 Known = LHSKnown & RHSKnown;
963 KnownBitsComputed =
true;
978 if (DemandedMask.
isSubsetOf(RHSKnown.One | LHSKnown.Zero))
979 return I->getOperand(0);
983 I, 1, (DemandedMask & ~LHSKnown.Zero).zextOrTrunc(MaskWidth)))
993 if (
match(
I, m_Intrinsic<Intrinsic::ptrmask>(
998 if (!LHSKnown.isZero()) {
999 const unsigned trailingZeros = LHSKnown.countMinTrailingZeros();
1002 uint64_t HighBitsGEPIndex = GEPIndex & ~PointerAlignBits;
1004 GEPIndex & PointerAlignBits & PtrMaskImmediate;
1006 uint64_t MaskedGEPIndex = HighBitsGEPIndex | MaskedLowBitsGEPIndex;
1008 if (MaskedGEPIndex != GEPIndex) {
1009 auto *
GEP = cast<GetElementPtrInst>(
II->getArgOperand(0));
1011 Type *GEPIndexType =
1014 GEP->getSourceElementType(), InnerPtr,
1015 ConstantInt::get(GEPIndexType, MaskedGEPIndex),
1016 GEP->getName(),
GEP->isInBounds());
1027 case Intrinsic::fshr:
1028 case Intrinsic::fshl: {
1036 if (
II->getIntrinsicID() == Intrinsic::fshr)
1039 APInt DemandedMaskLHS(DemandedMask.
lshr(ShiftAmt));
1041 if (
I->getOperand(0) !=
I->getOperand(1)) {
1050 if (DemandedMaskLHS.
isSubsetOf(LHSKnown.Zero | LHSKnown.One) &&
1064 Known.
Zero = LHSKnown.Zero.
shl(ShiftAmt) |
1066 Known.
One = LHSKnown.One.
shl(ShiftAmt) |
1068 KnownBitsComputed =
true;
1071 case Intrinsic::umax: {
1078 CTZ >=
C->getActiveBits())
1079 return II->getArgOperand(0);
1082 case Intrinsic::umin: {
1090 CTZ >=
C->getBitWidth() -
C->countl_one())
1091 return II->getArgOperand(0);
1097 *
II, DemandedMask, Known, KnownBitsComputed);
1105 if (!KnownBitsComputed)
1111 if (V->getType()->isPointerTy()) {
1112 Align Alignment = V->getPointerAlignment(
DL);
1120 if (!V->getType()->isPointerTy() && DemandedMask.
isSubsetOf(Known.
Zero | Known.
One))
1125 if (Known != ReferenceKnown) {
1126 errs() <<
"Mismatched known bits for " << *V <<
" in "
1127 <<
I->getFunction()->getName() <<
"\n";
1128 errs() <<
"computeKnownBits(): " << ReferenceKnown <<
"\n";
1129 errs() <<
"SimplifyDemandedBits(): " << Known <<
"\n";
1144 Type *ITy =
I->getType();
1153 switch (
I->getOpcode()) {
1154 case Instruction::And: {
1169 return I->getOperand(0);
1171 return I->getOperand(1);
1175 case Instruction::Or: {
1192 return I->getOperand(0);
1194 return I->getOperand(1);
1198 case Instruction::Xor: {
1214 return I->getOperand(0);
1216 return I->getOperand(1);
1220 case Instruction::Add: {
1228 return I->getOperand(0);
1232 return I->getOperand(1);
1234 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
1235 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
1241 case Instruction::Sub: {
1249 return I->getOperand(0);
1251 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
1252 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
1259 case Instruction::AShr: {
1272 const APInt *ShiftRC;
1273 const APInt *ShiftLC;
1321 if (!ShlOp1 || !ShrOp1)
1335 Known.
Zero &= DemandedMask;
1340 bool isLshr = (Shr->
getOpcode() == Instruction::LShr);
1341 BitMask1 = isLshr ? (BitMask1.
lshr(ShrAmt) << ShlAmt) :
1342 (BitMask1.
ashr(ShrAmt) << ShlAmt);
1344 if (ShrAmt <= ShlAmt) {
1345 BitMask2 <<= (ShlAmt - ShrAmt);
1347 BitMask2 = isLshr ? BitMask2.
lshr(ShrAmt - ShlAmt):
1348 BitMask2.
ashr(ShrAmt - ShlAmt);
1352 if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) {
1353 if (ShrAmt == ShlAmt)
1360 if (ShrAmt < ShlAmt) {
1362 New = BinaryOperator::CreateShl(VarX, Amt);
1368 New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) :
1369 BinaryOperator::CreateAShr(VarX, Amt);
1370 if (cast<BinaryOperator>(Shr)->isExact())
1371 New->setIsExact(
true);
1397 bool AllowMultipleUsers) {
1400 if (isa<ScalableVectorType>(V->getType()))
1403 unsigned VWidth = cast<FixedVectorType>(V->getType())->getNumElements();
1405 assert((DemandedElts & ~EltMask) == 0 &&
"Invalid DemandedElts!");
1409 PoisonElts = EltMask;
1413 if (DemandedElts.
isZero()) {
1414 PoisonElts = EltMask;
1420 if (
auto *
C = dyn_cast<Constant>(V)) {
1426 Type *EltTy = cast<VectorType>(V->getType())->getElementType();
1429 for (
unsigned i = 0; i != VWidth; ++i) {
1430 if (!DemandedElts[i]) {
1436 Constant *Elt =
C->getAggregateElement(i);
1437 if (!Elt)
return nullptr;
1440 if (isa<PoisonValue>(Elt))
1446 return NewCV !=
C ? NewCV :
nullptr;
1453 if (!AllowMultipleUsers) {
1457 if (!V->hasOneUse()) {
1466 DemandedElts = EltMask;
1471 if (!
I)
return nullptr;
1473 bool MadeChange =
false;
1474 auto simplifyAndSetOp = [&](
Instruction *Inst,
unsigned OpNum,
1476 auto *
II = dyn_cast<IntrinsicInst>(Inst);
1484 APInt PoisonElts2(VWidth, 0);
1485 APInt PoisonElts3(VWidth, 0);
1486 switch (
I->getOpcode()) {
1489 case Instruction::GetElementPtr: {
1499 if (mayIndexStructType(cast<GetElementPtrInst>(*
I)))
1507 for (
unsigned i = 0; i <
I->getNumOperands(); i++) {
1511 PoisonElts = EltMask;
1514 if (
I->getOperand(i)->getType()->isVectorTy()) {
1515 APInt PoisonEltsOp(VWidth, 0);
1516 simplifyAndSetOp(
I, i, DemandedElts, PoisonEltsOp);
1521 PoisonElts |= PoisonEltsOp;
1527 case Instruction::InsertElement: {
1534 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts2);
1540 unsigned IdxNo =
Idx->getZExtValue();
1541 APInt PreInsertDemandedElts = DemandedElts;
1543 PreInsertDemandedElts.
clearBit(IdxNo);
1551 if (PreInsertDemandedElts == 0 &&
1558 simplifyAndSetOp(
I, 0, PreInsertDemandedElts, PoisonElts);
1562 if (IdxNo >= VWidth || !DemandedElts[IdxNo]) {
1564 return I->getOperand(0);
1571 case Instruction::ShuffleVector: {
1572 auto *Shuffle = cast<ShuffleVectorInst>(
I);
1573 assert(Shuffle->getOperand(0)->getType() ==
1574 Shuffle->getOperand(1)->getType() &&
1575 "Expected shuffle operands to have same type");
1576 unsigned OpWidth = cast<FixedVectorType>(Shuffle->getOperand(0)->getType())
1580 if (
all_of(Shuffle->getShuffleMask(), [](
int Elt) { return Elt == 0; }) &&
1582 if (!isa<PoisonValue>(
I->getOperand(1))) {
1586 APInt LeftDemanded(OpWidth, 1);
1587 APInt LHSPoisonElts(OpWidth, 0);
1588 simplifyAndSetOp(
I, 0, LeftDemanded, LHSPoisonElts);
1589 if (LHSPoisonElts[0])
1590 PoisonElts = EltMask;
1596 APInt LeftDemanded(OpWidth, 0), RightDemanded(OpWidth, 0);
1597 for (
unsigned i = 0; i < VWidth; i++) {
1598 if (DemandedElts[i]) {
1599 unsigned MaskVal = Shuffle->getMaskValue(i);
1600 if (MaskVal != -1u) {
1601 assert(MaskVal < OpWidth * 2 &&
1602 "shufflevector mask index out of range!");
1603 if (MaskVal < OpWidth)
1604 LeftDemanded.setBit(MaskVal);
1606 RightDemanded.
setBit(MaskVal - OpWidth);
1611 APInt LHSPoisonElts(OpWidth, 0);
1612 simplifyAndSetOp(
I, 0, LeftDemanded, LHSPoisonElts);
1614 APInt RHSPoisonElts(OpWidth, 0);
1615 simplifyAndSetOp(
I, 1, RightDemanded, RHSPoisonElts);
1628 if (VWidth == OpWidth) {
1629 bool IsIdentityShuffle =
true;
1630 for (
unsigned i = 0; i < VWidth; i++) {
1631 unsigned MaskVal = Shuffle->getMaskValue(i);
1632 if (DemandedElts[i] && i != MaskVal) {
1633 IsIdentityShuffle =
false;
1637 if (IsIdentityShuffle)
1638 return Shuffle->getOperand(0);
1641 bool NewPoisonElts =
false;
1642 unsigned LHSIdx = -1u, LHSValIdx = -1u;
1643 unsigned RHSIdx = -1u, RHSValIdx = -1u;
1644 bool LHSUniform =
true;
1645 bool RHSUniform =
true;
1646 for (
unsigned i = 0; i < VWidth; i++) {
1647 unsigned MaskVal = Shuffle->getMaskValue(i);
1648 if (MaskVal == -1u) {
1650 }
else if (!DemandedElts[i]) {
1651 NewPoisonElts =
true;
1653 }
else if (MaskVal < OpWidth) {
1654 if (LHSPoisonElts[MaskVal]) {
1655 NewPoisonElts =
true;
1658 LHSIdx = LHSIdx == -1u ? i : OpWidth;
1659 LHSValIdx = LHSValIdx == -1u ? MaskVal : OpWidth;
1660 LHSUniform = LHSUniform && (MaskVal == i);
1663 if (RHSPoisonElts[MaskVal - OpWidth]) {
1664 NewPoisonElts =
true;
1667 RHSIdx = RHSIdx == -1u ? i : OpWidth;
1668 RHSValIdx = RHSValIdx == -1u ? MaskVal - OpWidth : OpWidth;
1669 RHSUniform = RHSUniform && (MaskVal - OpWidth == i);
1679 cast<FixedVectorType>(Shuffle->getType())->getNumElements()) {
1685 if (LHSIdx < OpWidth && RHSUniform) {
1686 if (
auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(0))) {
1687 Op = Shuffle->getOperand(1);
1688 Value = CV->getOperand(LHSValIdx);
1692 if (RHSIdx < OpWidth && LHSUniform) {
1693 if (
auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(1))) {
1694 Op = Shuffle->getOperand(0);
1695 Value = CV->getOperand(RHSValIdx);
1708 if (NewPoisonElts) {
1711 for (
unsigned i = 0; i < VWidth; ++i) {
1715 Elts.
push_back(Shuffle->getMaskValue(i));
1717 Shuffle->setShuffleMask(Elts);
1722 case Instruction::Select: {
1732 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1736 APInt DemandedLHS(DemandedElts), DemandedRHS(DemandedElts);
1737 if (
auto *CV = dyn_cast<ConstantVector>(Sel->
getCondition())) {
1738 for (
unsigned i = 0; i < VWidth; i++) {
1742 if (isa<ConstantExpr>(CElt))
1748 DemandedLHS.clearBit(i);
1754 simplifyAndSetOp(
I, 1, DemandedLHS, PoisonElts2);
1755 simplifyAndSetOp(
I, 2, DemandedRHS, PoisonElts3);
1759 PoisonElts = PoisonElts2 & PoisonElts3;
1762 case Instruction::BitCast: {
1764 VectorType *VTy = dyn_cast<VectorType>(
I->getOperand(0)->getType());
1766 unsigned InVWidth = cast<FixedVectorType>(VTy)->getNumElements();
1767 APInt InputDemandedElts(InVWidth, 0);
1768 PoisonElts2 =
APInt(InVWidth, 0);
1771 if (VWidth == InVWidth) {
1775 InputDemandedElts = DemandedElts;
1776 }
else if ((VWidth % InVWidth) == 0) {
1780 Ratio = VWidth / InVWidth;
1781 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1782 if (DemandedElts[OutIdx])
1783 InputDemandedElts.
setBit(OutIdx / Ratio);
1784 }
else if ((InVWidth % VWidth) == 0) {
1788 Ratio = InVWidth / VWidth;
1789 for (
unsigned InIdx = 0; InIdx != InVWidth; ++InIdx)
1790 if (DemandedElts[InIdx / Ratio])
1791 InputDemandedElts.
setBit(InIdx);
1797 simplifyAndSetOp(
I, 0, InputDemandedElts, PoisonElts2);
1799 if (VWidth == InVWidth) {
1800 PoisonElts = PoisonElts2;
1801 }
else if ((VWidth % InVWidth) == 0) {
1805 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1806 if (PoisonElts2[OutIdx / Ratio])
1807 PoisonElts.
setBit(OutIdx);
1808 }
else if ((InVWidth % VWidth) == 0) {
1812 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) {
1815 PoisonElts.
setBit(OutIdx);
1822 case Instruction::FPTrunc:
1823 case Instruction::FPExt:
1824 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1827 case Instruction::Call: {
1830 switch (
II->getIntrinsicID()) {
1831 case Intrinsic::masked_gather:
1832 case Intrinsic::masked_load: {
1837 DemandedPassThrough(DemandedElts);
1838 if (
auto *CV = dyn_cast<ConstantVector>(
II->getOperand(2)))
1839 for (
unsigned i = 0; i < VWidth; i++) {
1842 DemandedPtrs.clearBit(i);
1846 if (
II->getIntrinsicID() == Intrinsic::masked_gather)
1847 simplifyAndSetOp(
II, 0, DemandedPtrs, PoisonElts2);
1848 simplifyAndSetOp(
II, 3, DemandedPassThrough, PoisonElts3);
1852 PoisonElts = PoisonElts2 & PoisonElts3;
1858 *
II, DemandedElts, PoisonElts, PoisonElts2, PoisonElts3,
1892 if (DemandedElts == 1 && !
X->hasOneUse() && !
Y->hasOneUse() &&
1895 auto findShufBO = [&](
bool MatchShufAsOp0) ->
User * {
1900 Value *ShufOp = MatchShufAsOp0 ?
X :
Y;
1901 Value *OtherOp = MatchShufAsOp0 ?
Y :
X;
1917 if (
User *ShufBO = findShufBO(
true))
1919 if (
User *ShufBO = findShufBO(
false))
1923 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1924 simplifyAndSetOp(
I, 1, DemandedElts, PoisonElts2);
1928 PoisonElts &= PoisonElts2;
1936 return MadeChange ?
I :
nullptr;
1962 Type *VTy = V->getType();
1966 if (DemandedMask ==
fcNone)
1976 Value *FoldedToConst =
1978 return FoldedToConst == V ? nullptr : FoldedToConst;
1981 if (!
I->hasOneUse())
1985 switch (
I->getOpcode()) {
1986 case Instruction::FNeg: {
1993 case Instruction::Call: {
1996 case Intrinsic::fabs:
2002 case Intrinsic::arithmetic_fence:
2006 case Intrinsic::copysign: {
2014 I->setOperand(1, ConstantFP::get(VTy, -1.0));
2036 case Instruction::Select: {
2043 return I->getOperand(2);
2045 return I->getOperand(1);
2048 Known = KnownLHS | KnownRHS;
2063 Use &U =
I->getOperandUse(OpNo);
2068 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.
uint64_t IntrinsicInst * II
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="", InsertPosition InsertBefore=nullptr)
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 * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())
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="")
static InsertElementInst * Create(Value *Vec, Value *NewElt, Value *Idx, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
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.
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.
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