25#define DEBUG_TYPE "instcombine"
29 cl::desc(
"Verify that computeKnownBits() and "
30 "SimplifyDemandedBits() are consistent"),
34 "instcombine-simplify-vector-elts-depth",
36 "Depth limit when simplifying vector instructions and their operands"),
43 const APInt &Demanded) {
45 assert(OpNo < I->getNumOperands() &&
"Operand index too large");
54 if (
C->isSubsetOf(Demanded))
58 I->setOperand(OpNo, ConstantInt::get(
Op->getType(), *
C & Demanded));
69 return DL.getPointerTypeSizeInBits(Ty);
80 if (V == &Inst)
return true;
96 const APInt &DemandedMask,
99 Use &U =
I->getOperandUse(OpNo);
101 if (isa<Constant>(V)) {
107 if (DemandedMask.
isZero()) {
132 if (!NewVal)
return false;
133 if (
Instruction* OpInst = dyn_cast<Instruction>(U))
164 const APInt &DemandedMask,
168 assert(
I !=
nullptr &&
"Null pointer of Value???");
171 Type *VTy =
I->getType();
175 "Value *V, DemandedMask and Known must have same BitWidth");
181 auto disableWrapFlagsBasedOnUnusedHighBits = [](
Instruction *
I,
187 I->setHasNoSignedWrap(
false);
188 I->setHasNoUnsignedWrap(
false);
195 auto simplifyOperandsBasedOnUnusedHighBits = [&](
APInt &DemandedFromOps) {
204 disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
210 switch (
I->getOpcode()) {
214 case Instruction::And: {
232 return I->getOperand(0);
234 return I->getOperand(1);
242 case Instruction::Or: {
248 I->dropPoisonGeneratingFlags();
263 return I->getOperand(0);
265 return I->getOperand(1);
272 if (!cast<PossiblyDisjointInst>(
I)->isDisjoint()) {
274 RHSCache(
I->getOperand(1), RHSKnown);
276 cast<PossiblyDisjointInst>(
I)->setIsDisjoint(
true);
283 case Instruction::Xor: {
288 if (DemandedMask == 1 &&
309 return I->getOperand(0);
311 return I->getOperand(1);
318 BinaryOperator::CreateOr(
I->getOperand(0),
I->getOperand(1));
320 cast<PossiblyDisjointInst>(
Or)->setIsDisjoint(
true);
332 ~RHSKnown.
One & DemandedMask);
342 if ((*
C | ~DemandedMask).isAllOnes()) {
356 if (
Instruction *LHSInst = dyn_cast<Instruction>(
I->getOperand(0))) {
358 if (LHSInst->getOpcode() == Instruction::And && LHSInst->hasOneUse() &&
361 (LHSKnown.One & RHSKnown.
One & DemandedMask) != 0) {
362 APInt NewMask = ~(LHSKnown.One & RHSKnown.
One & DemandedMask);
365 Instruction *NewAnd = BinaryOperator::CreateAnd(
I->getOperand(0), AndC);
369 Instruction *NewXor = BinaryOperator::CreateXor(NewAnd, XorC);
375 case Instruction::Select: {
385 auto CanonicalizeSelectConstant = [](
Instruction *
I,
unsigned OpNo,
386 const APInt &DemandedMask) {
406 if ((*CmpC & DemandedMask) == (*SelC & DemandedMask)) {
407 I->setOperand(OpNo, ConstantInt::get(
I->getType(), *CmpC));
412 if (CanonicalizeSelectConstant(
I, 1, DemandedMask) ||
413 CanonicalizeSelectConstant(
I, 2, DemandedMask))
424 case Instruction::Trunc: {
443 case Instruction::ZExt: {
444 unsigned SrcBitWidth =
I->getOperand(0)->getType()->getScalarSizeInBits();
452 I->dropPoisonGeneratingFlags();
456 if (
I->getOpcode() == Instruction::ZExt &&
I->hasNonNeg() &&
463 case Instruction::SExt: {
465 unsigned SrcBitWidth =
I->getOperand(0)->getType()->getScalarSizeInBits();
467 APInt InputDemandedBits = DemandedMask.
trunc(SrcBitWidth);
472 InputDemandedBits.
setBit(SrcBitWidth-1);
493 case Instruction::Add: {
494 if ((DemandedMask & 1) == 0) {
500 X->getType()->isIntOrIntVectorTy(1) &&
X->getType() ==
Y->getType()) {
515 X->getType()->isIntOrIntVectorTy(1) &&
X->getType() ==
Y->getType() &&
516 (
I->getOperand(0)->hasOneUse() ||
I->getOperand(1)->hasOneUse())) {
537 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
543 APInt DemandedFromLHS = DemandedFromOps;
547 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
552 return I->getOperand(0);
553 if (DemandedFromOps.
isSubsetOf(LHSKnown.Zero))
554 return I->getOperand(1);
568 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
569 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
573 case Instruction::Sub: {
580 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
586 APInt DemandedFromLHS = DemandedFromOps;
590 return disableWrapFlagsBasedOnUnusedHighBits(
I, NLZ);
595 return I->getOperand(0);
598 if (DemandedFromOps.
isOne() && DemandedFromOps.
isSubsetOf(LHSKnown.Zero))
599 return I->getOperand(1);
611 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
612 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
616 case Instruction::Mul: {
617 APInt DemandedFromOps;
618 if (simplifyOperandsBasedOnUnusedHighBits(DemandedFromOps))
628 Constant *ShiftC = ConstantInt::get(VTy, CTZ);
629 Instruction *Shl = BinaryOperator::CreateShl(
I->getOperand(0), ShiftC);
636 if (
I->getOperand(0) ==
I->getOperand(1) && DemandedMask.
ult(4)) {
637 Constant *One = ConstantInt::get(VTy, 1);
638 Instruction *And1 = BinaryOperator::CreateAnd(
I->getOperand(0), One);
645 case Instruction::Shl: {
650 if (
Instruction *Shr = dyn_cast<Instruction>(
I->getOperand(0)))
652 DemandedMask, Known))
656 if (
I->hasOneUse()) {
657 auto *Inst = dyn_cast<Instruction>(
I->user_back());
658 if (Inst && Inst->getOpcode() == BinaryOperator::Or) {
660 auto [IID, FShiftArgs] = *Opt;
661 if ((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
662 FShiftArgs[0] == FShiftArgs[1]) {
674 if (
I->hasNoSignedWrap()) {
678 if (SignBits > ShiftAmt && SignBits - ShiftAmt >= NumHiDemandedBits)
679 return I->getOperand(0);
689 Constant *LeftShiftAmtC = ConstantInt::get(VTy, ShiftAmt);
693 LeftShiftAmtC,
DL) ==
C) {
694 Instruction *Lshr = BinaryOperator::CreateLShr(NewC,
X);
700 APInt DemandedMaskIn(DemandedMask.
lshr(ShiftAmt));
724 I->dropPoisonGeneratingFlags();
732 case Instruction::LShr: {
738 if (
I->hasOneUse()) {
739 auto *Inst = dyn_cast<Instruction>(
I->user_back());
740 if (Inst && Inst->getOpcode() == BinaryOperator::Or) {
742 auto [IID, FShiftArgs] = *Opt;
743 if ((IID == Intrinsic::fshl || IID == Intrinsic::fshr) &&
744 FShiftArgs[0] == FShiftArgs[1]) {
760 if (SignBits >= NumHiDemandedBits)
761 return I->getOperand(0);
770 Constant *RightShiftAmtC = ConstantInt::get(VTy, ShiftAmt);
774 RightShiftAmtC,
DL) ==
C) {
781 if (
match(
I->getOperand(0),
785 X, ConstantInt::get(
X->getType(), Factor->
lshr(ShiftAmt)));
791 APInt DemandedMaskIn(DemandedMask.
shl(ShiftAmt));
794 I->dropPoisonGeneratingFlags();
806 case Instruction::AShr: {
812 if (SignBits >= NumHiDemandedBits)
813 return I->getOperand(0);
819 if (DemandedMask.
isOne()) {
822 I->getOperand(0),
I->getOperand(1),
I->getName());
831 APInt DemandedMaskIn(DemandedMask.
shl(ShiftAmt));
834 bool ShiftedInBitsDemanded = DemandedMask.
countl_zero() < ShiftAmt;
835 if (ShiftedInBitsDemanded)
839 I->dropPoisonGeneratingFlags();
845 if (Known.
Zero[
BitWidth - 1] || !ShiftedInBitsDemanded) {
848 LShr->
setIsExact(cast<BinaryOperator>(
I)->isExact());
855 ShiftAmt != 0,
I->isExact());
861 case Instruction::UDiv: {
867 APInt DemandedMaskIn =
872 I->dropPoisonGeneratingFlags();
877 cast<BinaryOperator>(
I)->isExact());
883 case Instruction::SRem: {
886 if (DemandedMask.
ult(*Rem))
887 return I->getOperand(0);
889 APInt LowBits = *Rem - 1;
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, Q))
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<GEPOperator>(
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)) {
1047 I->dropPoisonGeneratingReturnAttributes();
1054 if (DemandedMaskLHS.
isSubsetOf(LHSKnown.Zero | LHSKnown.One) &&
1068 Known.
Zero = LHSKnown.Zero.
shl(ShiftAmt) |
1070 Known.
One = LHSKnown.One.
shl(ShiftAmt) |
1072 KnownBitsComputed =
true;
1075 case Intrinsic::umax: {
1082 CTZ >=
C->getActiveBits())
1083 return II->getArgOperand(0);
1086 case Intrinsic::umin: {
1094 CTZ >=
C->getBitWidth() -
C->countl_one())
1095 return II->getArgOperand(0);
1101 *
II, DemandedMask, Known, KnownBitsComputed);
1109 if (!KnownBitsComputed)
1115 if (
I->getType()->isPointerTy()) {
1116 Align Alignment =
I->getPointerAlignment(
DL);
1124 if (!
I->getType()->isPointerTy() &&
1130 if (Known != ReferenceKnown) {
1131 errs() <<
"Mismatched known bits for " << *
I <<
" in "
1132 <<
I->getFunction()->getName() <<
"\n";
1133 errs() <<
"computeKnownBits(): " << ReferenceKnown <<
"\n";
1134 errs() <<
"SimplifyDemandedBits(): " << Known <<
"\n";
1149 Type *ITy =
I->getType();
1158 switch (
I->getOpcode()) {
1159 case Instruction::And: {
1174 return I->getOperand(0);
1176 return I->getOperand(1);
1180 case Instruction::Or: {
1197 return I->getOperand(0);
1199 return I->getOperand(1);
1203 case Instruction::Xor: {
1219 return I->getOperand(0);
1221 return I->getOperand(1);
1225 case Instruction::Add: {
1233 return I->getOperand(0);
1237 return I->getOperand(1);
1239 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
1240 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
1245 case Instruction::Sub: {
1253 return I->getOperand(0);
1255 bool NSW = cast<OverflowingBinaryOperator>(
I)->hasNoSignedWrap();
1256 bool NUW = cast<OverflowingBinaryOperator>(
I)->hasNoUnsignedWrap();
1262 case Instruction::AShr: {
1275 const APInt *ShiftRC;
1276 const APInt *ShiftLC;
1324 if (!ShlOp1 || !ShrOp1)
1338 Known.
Zero &= DemandedMask;
1343 bool isLshr = (Shr->
getOpcode() == Instruction::LShr);
1344 BitMask1 = isLshr ? (BitMask1.
lshr(ShrAmt) << ShlAmt) :
1345 (BitMask1.
ashr(ShrAmt) << ShlAmt);
1347 if (ShrAmt <= ShlAmt) {
1348 BitMask2 <<= (ShlAmt - ShrAmt);
1350 BitMask2 = isLshr ? BitMask2.
lshr(ShrAmt - ShlAmt):
1351 BitMask2.
ashr(ShrAmt - ShlAmt);
1355 if ((BitMask1 & DemandedMask) == (BitMask2 & DemandedMask)) {
1356 if (ShrAmt == ShlAmt)
1363 if (ShrAmt < ShlAmt) {
1365 New = BinaryOperator::CreateShl(VarX, Amt);
1371 New = isLshr ? BinaryOperator::CreateLShr(VarX, Amt) :
1372 BinaryOperator::CreateAShr(VarX, Amt);
1373 if (cast<BinaryOperator>(Shr)->isExact())
1374 New->setIsExact(
true);
1400 bool AllowMultipleUsers) {
1403 if (isa<ScalableVectorType>(V->getType()))
1406 unsigned VWidth = cast<FixedVectorType>(V->getType())->getNumElements();
1408 assert((DemandedElts & ~EltMask) == 0 &&
"Invalid DemandedElts!");
1412 PoisonElts = EltMask;
1416 if (DemandedElts.
isZero()) {
1417 PoisonElts = EltMask;
1423 if (
auto *
C = dyn_cast<Constant>(V)) {
1429 Type *EltTy = cast<VectorType>(V->getType())->getElementType();
1432 for (
unsigned i = 0; i != VWidth; ++i) {
1433 if (!DemandedElts[i]) {
1439 Constant *Elt =
C->getAggregateElement(i);
1440 if (!Elt)
return nullptr;
1443 if (isa<PoisonValue>(Elt))
1449 return NewCV !=
C ? NewCV :
nullptr;
1456 if (!AllowMultipleUsers) {
1460 if (!V->hasOneUse()) {
1469 DemandedElts = EltMask;
1474 if (!
I)
return nullptr;
1476 bool MadeChange =
false;
1477 auto simplifyAndSetOp = [&](
Instruction *Inst,
unsigned OpNum,
1479 auto *
II = dyn_cast<IntrinsicInst>(Inst);
1487 APInt PoisonElts2(VWidth, 0);
1488 APInt PoisonElts3(VWidth, 0);
1489 switch (
I->getOpcode()) {
1492 case Instruction::GetElementPtr: {
1502 if (mayIndexStructType(cast<GetElementPtrInst>(*
I)))
1510 for (
unsigned i = 0; i <
I->getNumOperands(); i++) {
1514 PoisonElts = EltMask;
1517 if (
I->getOperand(i)->getType()->isVectorTy()) {
1518 APInt PoisonEltsOp(VWidth, 0);
1519 simplifyAndSetOp(
I, i, DemandedElts, PoisonEltsOp);
1524 PoisonElts |= PoisonEltsOp;
1530 case Instruction::InsertElement: {
1537 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts2);
1543 unsigned IdxNo =
Idx->getZExtValue();
1544 APInt PreInsertDemandedElts = DemandedElts;
1546 PreInsertDemandedElts.
clearBit(IdxNo);
1554 if (PreInsertDemandedElts == 0 &&
1561 simplifyAndSetOp(
I, 0, PreInsertDemandedElts, PoisonElts);
1565 if (IdxNo >= VWidth || !DemandedElts[IdxNo]) {
1567 return I->getOperand(0);
1574 case Instruction::ShuffleVector: {
1575 auto *Shuffle = cast<ShuffleVectorInst>(
I);
1576 assert(Shuffle->getOperand(0)->getType() ==
1577 Shuffle->getOperand(1)->getType() &&
1578 "Expected shuffle operands to have same type");
1579 unsigned OpWidth = cast<FixedVectorType>(Shuffle->getOperand(0)->getType())
1583 if (
all_of(Shuffle->getShuffleMask(), [](
int Elt) { return Elt == 0; }) &&
1585 if (!isa<PoisonValue>(
I->getOperand(1))) {
1589 APInt LeftDemanded(OpWidth, 1);
1590 APInt LHSPoisonElts(OpWidth, 0);
1591 simplifyAndSetOp(
I, 0, LeftDemanded, LHSPoisonElts);
1592 if (LHSPoisonElts[0])
1593 PoisonElts = EltMask;
1599 APInt LeftDemanded(OpWidth, 0), RightDemanded(OpWidth, 0);
1600 for (
unsigned i = 0; i < VWidth; i++) {
1601 if (DemandedElts[i]) {
1602 unsigned MaskVal = Shuffle->getMaskValue(i);
1603 if (MaskVal != -1u) {
1604 assert(MaskVal < OpWidth * 2 &&
1605 "shufflevector mask index out of range!");
1606 if (MaskVal < OpWidth)
1607 LeftDemanded.setBit(MaskVal);
1609 RightDemanded.
setBit(MaskVal - OpWidth);
1614 APInt LHSPoisonElts(OpWidth, 0);
1615 simplifyAndSetOp(
I, 0, LeftDemanded, LHSPoisonElts);
1617 APInt RHSPoisonElts(OpWidth, 0);
1618 simplifyAndSetOp(
I, 1, RightDemanded, RHSPoisonElts);
1631 if (VWidth == OpWidth) {
1632 bool IsIdentityShuffle =
true;
1633 for (
unsigned i = 0; i < VWidth; i++) {
1634 unsigned MaskVal = Shuffle->getMaskValue(i);
1635 if (DemandedElts[i] && i != MaskVal) {
1636 IsIdentityShuffle =
false;
1640 if (IsIdentityShuffle)
1641 return Shuffle->getOperand(0);
1644 bool NewPoisonElts =
false;
1645 unsigned LHSIdx = -1u, LHSValIdx = -1u;
1646 unsigned RHSIdx = -1u, RHSValIdx = -1u;
1647 bool LHSUniform =
true;
1648 bool RHSUniform =
true;
1649 for (
unsigned i = 0; i < VWidth; i++) {
1650 unsigned MaskVal = Shuffle->getMaskValue(i);
1651 if (MaskVal == -1u) {
1653 }
else if (!DemandedElts[i]) {
1654 NewPoisonElts =
true;
1656 }
else if (MaskVal < OpWidth) {
1657 if (LHSPoisonElts[MaskVal]) {
1658 NewPoisonElts =
true;
1661 LHSIdx = LHSIdx == -1u ? i : OpWidth;
1662 LHSValIdx = LHSValIdx == -1u ? MaskVal : OpWidth;
1663 LHSUniform = LHSUniform && (MaskVal == i);
1666 if (RHSPoisonElts[MaskVal - OpWidth]) {
1667 NewPoisonElts =
true;
1670 RHSIdx = RHSIdx == -1u ? i : OpWidth;
1671 RHSValIdx = RHSValIdx == -1u ? MaskVal - OpWidth : OpWidth;
1672 RHSUniform = RHSUniform && (MaskVal - OpWidth == i);
1688 if (LHSIdx < OpWidth && RHSUniform) {
1689 if (
auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(0))) {
1690 Op = Shuffle->getOperand(1);
1691 Value = CV->getOperand(LHSValIdx);
1695 if (RHSIdx < OpWidth && LHSUniform) {
1696 if (
auto *CV = dyn_cast<ConstantVector>(Shuffle->getOperand(1))) {
1697 Op = Shuffle->getOperand(0);
1698 Value = CV->getOperand(RHSValIdx);
1711 if (NewPoisonElts) {
1714 for (
unsigned i = 0; i < VWidth; ++i) {
1718 Elts.
push_back(Shuffle->getMaskValue(i));
1720 Shuffle->setShuffleMask(Elts);
1725 case Instruction::Select: {
1735 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1739 APInt DemandedLHS(DemandedElts), DemandedRHS(DemandedElts);
1740 if (
auto *CV = dyn_cast<ConstantVector>(Sel->
getCondition())) {
1741 for (
unsigned i = 0; i < VWidth; i++) {
1746 DemandedLHS.clearBit(i);
1752 simplifyAndSetOp(
I, 1, DemandedLHS, PoisonElts2);
1753 simplifyAndSetOp(
I, 2, DemandedRHS, PoisonElts3);
1757 PoisonElts = PoisonElts2 & PoisonElts3;
1760 case Instruction::BitCast: {
1762 VectorType *VTy = dyn_cast<VectorType>(
I->getOperand(0)->getType());
1764 unsigned InVWidth = cast<FixedVectorType>(VTy)->getNumElements();
1765 APInt InputDemandedElts(InVWidth, 0);
1766 PoisonElts2 =
APInt(InVWidth, 0);
1769 if (VWidth == InVWidth) {
1773 InputDemandedElts = DemandedElts;
1774 }
else if ((VWidth % InVWidth) == 0) {
1778 Ratio = VWidth / InVWidth;
1779 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1780 if (DemandedElts[OutIdx])
1781 InputDemandedElts.
setBit(OutIdx / Ratio);
1782 }
else if ((InVWidth % VWidth) == 0) {
1786 Ratio = InVWidth / VWidth;
1787 for (
unsigned InIdx = 0; InIdx != InVWidth; ++InIdx)
1788 if (DemandedElts[InIdx / Ratio])
1789 InputDemandedElts.
setBit(InIdx);
1795 simplifyAndSetOp(
I, 0, InputDemandedElts, PoisonElts2);
1797 if (VWidth == InVWidth) {
1798 PoisonElts = PoisonElts2;
1799 }
else if ((VWidth % InVWidth) == 0) {
1803 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx)
1804 if (PoisonElts2[OutIdx / Ratio])
1805 PoisonElts.
setBit(OutIdx);
1806 }
else if ((InVWidth % VWidth) == 0) {
1810 for (
unsigned OutIdx = 0; OutIdx != VWidth; ++OutIdx) {
1813 PoisonElts.
setBit(OutIdx);
1820 case Instruction::FPTrunc:
1821 case Instruction::FPExt:
1822 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1825 case Instruction::Call: {
1828 switch (
II->getIntrinsicID()) {
1829 case Intrinsic::masked_gather:
1830 case Intrinsic::masked_load: {
1835 DemandedPassThrough(DemandedElts);
1836 if (
auto *CV = dyn_cast<ConstantVector>(
II->getOperand(2)))
1837 for (
unsigned i = 0; i < VWidth; i++) {
1840 DemandedPtrs.clearBit(i);
1844 if (
II->getIntrinsicID() == Intrinsic::masked_gather)
1845 simplifyAndSetOp(
II, 0, DemandedPtrs, PoisonElts2);
1846 simplifyAndSetOp(
II, 3, DemandedPassThrough, PoisonElts3);
1850 PoisonElts = PoisonElts2 & PoisonElts3;
1856 *
II, DemandedElts, PoisonElts, PoisonElts2, PoisonElts3,
1890 if (DemandedElts == 1 && !
X->hasOneUse() && !
Y->hasOneUse() &&
1893 auto findShufBO = [&](
bool MatchShufAsOp0) ->
User * {
1898 Value *ShufOp = MatchShufAsOp0 ?
X :
Y;
1899 Value *OtherOp = MatchShufAsOp0 ?
Y :
X;
1915 if (
User *ShufBO = findShufBO(
true))
1917 if (
User *ShufBO = findShufBO(
false))
1921 simplifyAndSetOp(
I, 0, DemandedElts, PoisonElts);
1922 simplifyAndSetOp(
I, 1, DemandedElts, PoisonElts2);
1926 PoisonElts &= PoisonElts2;
1934 return MadeChange ?
I :
nullptr;
1966 Type *VTy = V->getType();
1970 if (DemandedMask ==
fcNone)
1980 Value *FoldedToConst =
1982 return FoldedToConst == V ? nullptr : FoldedToConst;
1985 if (!
I->hasOneUse())
1989 switch (
I->getOpcode()) {
1990 case Instruction::FNeg: {
1997 case Instruction::Call: {
2000 case Intrinsic::fabs:
2006 case Intrinsic::arithmetic_fence:
2010 case Intrinsic::copysign: {
2018 I->setOperand(1, ConstantFP::get(VTy, -1.0));
2040 case Instruction::Select: {
2047 return I->getOperand(2);
2049 return I->getOperand(1);
2052 Known = KnownLHS | KnownRHS;
2067 Use &U =
I->getOperandUse(OpNo);
2072 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 cl::opt< unsigned > SimplifyDemandedVectorEltsDepthLimit("instcombine-simplify-vector-elts-depth", cl::desc("Depth limit when simplifying vector instructions and their operands"), cl::Hidden, cl::init(10))
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())
static unsigned getNumElements(Type *Ty)
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".
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.
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.
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.
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 isOneValue() const
Returns true if the value is one.
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
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="")
CallInst * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *V, FMFSource FMFSource={}, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
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
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(Instruction *I, const APInt &DemandedMask, KnownBits &Known, unsigned Depth, const SimplifyQuery &Q)
Attempts to replace I 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, const SimplifyQuery &Q)
Helper routine of SimplifyDemandedUseBits.
bool SimplifyDemandedBits(Instruction *I, unsigned Op, const APInt &DemandedMask, KnownBits &Known, unsigned Depth, const SimplifyQuery &Q) override
This form of SimplifyDemandedBits simplifies the specified instruction operand if possible,...
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.
bool isAggregateType() const
Return true if the type is an aggregate 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 * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})
Look up the Function declaration of the intrinsic id in the Module M.
class_match< PoisonValue > m_Poison()
Match an arbitrary poison constant.
cst_pred_ty< is_lowbit_mask > m_LowBitMask()
Match an integer or vector with only the low bit(s) set.
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.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(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)
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, 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...
constexpr T alignDown(U Value, V Align, W Skew=0)
Returns the largest unsigned integer less than or equal to Value and is Skew mod Align.
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.
void adjustKnownBitsForSelectArm(KnownBits &Known, Value *Cond, Value *Arm, bool Invert, unsigned Depth, const SimplifyQuery &Q)
Adjust Known for the given select Arm to include information from the select Cond.
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.
@ Mul
Product of integers.
@ Xor
Bitwise or logical XOR of integers.
@ And
Bitwise or logical AND of integers.
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
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.
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 ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
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.
static KnownBits add(const KnownBits &LHS, const KnownBits &RHS, bool NSW=false, bool NUW=false)
Compute knownbits resulting from addition of LHS and RHS.
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for srem(LHS, RHS).
static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for udiv(LHS, RHS).
bool isNegative() const
Returns true if this value is known to be negative.
static KnownBits sub(const KnownBits &LHS, const KnownBits &RHS, bool NSW=false, bool NUW=false)
Compute knownbits resulting from subtraction of LHS and RHS.
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