57#include "llvm/IR/IntrinsicsAArch64.h"
58#include "llvm/IR/IntrinsicsAMDGPU.h"
59#include "llvm/IR/IntrinsicsRISCV.h"
60#include "llvm/IR/IntrinsicsX86.h"
96 return DL.getPointerTypeSizeInBits(Ty);
108 CxtI = dyn_cast<Instruction>(V);
122 CxtI = dyn_cast<Instruction>(V1);
126 CxtI = dyn_cast<Instruction>(V2);
134 const APInt &DemandedElts,
136 if (isa<ScalableVectorType>(Shuf->
getType())) {
138 DemandedLHS = DemandedRHS = DemandedElts;
145 DemandedElts, DemandedLHS, DemandedRHS);
157 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
178 V, DemandedElts, Known,
Depth,
195 V, DemandedElts,
Depth,
206 "LHS and RHS should have the same type");
208 "LHS and RHS should be integers");
258 return !
I->user_empty() &&
all_of(
I->users(), [](
const User *U) {
259 ICmpInst::Predicate P;
260 return match(U, m_ICmp(P, m_Value(), m_Zero())) && ICmpInst::isEquality(P);
268 bool OrZero,
unsigned Depth,
271 return ::isKnownToBeAPowerOfTwo(
285 return ::isKnownNonZero(
300 if (
auto *CI = dyn_cast<ConstantInt>(V))
301 return CI->getValue().isStrictlyPositive();
323 return ::isKnownNonEqual(
335 return ::MaskedValueIsZero(
345 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
355 return ::ComputeNumSignBits(
364 return V->getType()->getScalarSizeInBits() - SignBits + 1;
368 bool NSW,
const APInt &DemandedElts,
400 bool isKnownNegativeOp0 = Known2.
isNegative();
403 (isKnownNonNegativeOp1 && isKnownNonNegativeOp0);
408 (isKnownNegativeOp1 && isKnownNonNegativeOp0 &&
410 (isKnownNegativeOp0 && isKnownNonNegativeOp1 && Known.
isNonZero());
414 bool SelfMultiply = Op0 == Op1;
435 unsigned NumRanges = Ranges.getNumOperands() / 2;
441 for (
unsigned i = 0; i < NumRanges; ++i) {
443 mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
445 mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
449 unsigned CommonPrefixBits =
450 (Range.getUnsignedMax() ^ Range.getUnsignedMin()).
countl_zero();
452 APInt UnsignedMax = Range.getUnsignedMax().zextOrTrunc(
BitWidth);
453 Known.
One &= UnsignedMax & Mask;
454 Known.
Zero &= ~UnsignedMax & Mask;
469 while (!WorkSet.
empty()) {
471 if (!Visited.
insert(V).second)
476 return EphValues.count(U);
481 if (V ==
I || (isa<Instruction>(V) &&
483 !cast<Instruction>(V)->isTerminator())) {
485 if (
const User *U = dyn_cast<User>(V))
497 return CI->isAssumeLikeIntrinsic();
557 if (Pred == ICmpInst::ICMP_UGT)
561 if (Pred == ICmpInst::ICMP_NE)
572 auto *VC = dyn_cast<ConstantDataVector>(
RHS);
576 for (
unsigned ElemIdx = 0, NElem = VC->getNumElements(); ElemIdx < NElem;
579 Pred, VC->getElementAsAPInt(ElemIdx));
598 "Got assumption for the wrong function!");
601 if (!V->getType()->isPointerTy())
604 *
I,
I->bundle_op_info_begin()[Elem.Index])) {
606 (RK.AttrKind == Attribute::NonNull ||
607 (RK.AttrKind == Attribute::Dereferenceable &&
609 V->getType()->getPointerAddressSpace()))) &&
644 QueryNoAC.
AC =
nullptr;
653 switch (Cmp->getPredicate()) {
654 case ICmpInst::ICMP_EQ:
660 }
else if (
match(Cmp,
668 Known.
One |= RHSKnown.
One & MaskKnown.
One;
670 }
else if (
match(Cmp,
680 }
else if (
match(Cmp,
711 Known.
One |= RHSKnown.
One <<
C;
714 case ICmpInst::ICMP_NE: {
757 "Got assumption for the wrong function!");
760 if (!V->getType()->isPointerTy())
763 *
I,
I->bundle_op_info_begin()[Elem.Index])) {
764 if (RK.WasOn == V && RK.AttrKind == Attribute::Alignment &&
776 Value *Arg =
I->getArgOperand(0);
796 ICmpInst *Cmp = dyn_cast<ICmpInst>(Arg);
832 Known = KF(Known2, Known, ShAmtNonZero);
843 Value *
X =
nullptr, *
Y =
nullptr;
845 switch (
I->getOpcode()) {
846 case Instruction::And:
847 KnownOut = KnownLHS & KnownRHS;
857 KnownOut = KnownLHS.
blsi();
859 KnownOut = KnownRHS.
blsi();
862 case Instruction::Or:
863 KnownOut = KnownLHS | KnownRHS;
865 case Instruction::Xor:
866 KnownOut = KnownLHS ^ KnownRHS;
876 const KnownBits &XBits =
I->getOperand(0) ==
X ? KnownLHS : KnownRHS;
877 KnownOut = XBits.
blsmsk();
890 if (!KnownOut.
Zero[0] && !KnownOut.
One[0] &&
911 auto *FVTy = dyn_cast<FixedVectorType>(
I->getType());
916 I, DemandedElts, KnownLHS, KnownRHS,
Depth,
921 Attribute Attr =
F->getFnAttribute(Attribute::VScaleRange);
929 return ConstantRange::getEmpty(
BitWidth);
940 const APInt &DemandedElts,
946 switch (
I->getOpcode()) {
948 case Instruction::Load:
953 case Instruction::And:
959 case Instruction::Or:
965 case Instruction::Xor:
971 case Instruction::Mul: {
974 Known, Known2,
Depth, Q);
977 case Instruction::UDiv: {
984 case Instruction::SDiv: {
991 case Instruction::Select: {
1033 case Instruction::FPTrunc:
1034 case Instruction::FPExt:
1035 case Instruction::FPToUI:
1036 case Instruction::FPToSI:
1037 case Instruction::SIToFP:
1038 case Instruction::UIToFP:
1040 case Instruction::PtrToInt:
1041 case Instruction::IntToPtr:
1044 case Instruction::ZExt:
1045 case Instruction::Trunc: {
1046 Type *SrcTy =
I->getOperand(0)->getType();
1048 unsigned SrcBitWidth;
1056 assert(SrcBitWidth &&
"SrcBitWidth can't be zero");
1059 if (
auto *Inst = dyn_cast<PossiblyNonNegInst>(
I);
1060 Inst && Inst->hasNonNeg() && !Known.
isNegative())
1065 case Instruction::BitCast: {
1066 Type *SrcTy =
I->getOperand(0)->getType();
1070 !
I->getType()->isVectorTy()) {
1076 auto *SrcVecTy = dyn_cast<FixedVectorType>(SrcTy);
1077 if (!SrcVecTy || !SrcVecTy->getElementType()->isIntegerTy() ||
1078 !
I->getType()->isIntOrIntVectorTy() ||
1079 isa<ScalableVectorType>(
I->getType()))
1084 unsigned SubBitWidth = SrcVecTy->getScalarSizeInBits();
1101 unsigned SubScale =
BitWidth / SubBitWidth;
1103 for (
unsigned i = 0; i != NumElts; ++i) {
1104 if (DemandedElts[i])
1105 SubDemandedElts.
setBit(i * SubScale);
1109 for (
unsigned i = 0; i != SubScale; ++i) {
1113 Known.
insertBits(KnownSrc, ShiftElt * SubBitWidth);
1118 case Instruction::SExt: {
1120 unsigned SrcBitWidth =
I->getOperand(0)->getType()->getScalarSizeInBits();
1122 Known = Known.
trunc(SrcBitWidth);
1129 case Instruction::Shl: {
1133 bool ShAmtNonZero) {
1134 return KnownBits::shl(KnownVal, KnownAmt, NUW, NSW, ShAmtNonZero);
1144 case Instruction::LShr: {
1146 bool ShAmtNonZero) {
1157 case Instruction::AShr: {
1159 bool ShAmtNonZero) {
1166 case Instruction::Sub: {
1169 DemandedElts, Known, Known2,
Depth, Q);
1172 case Instruction::Add: {
1175 DemandedElts, Known, Known2,
Depth, Q);
1178 case Instruction::SRem:
1184 case Instruction::URem:
1189 case Instruction::Alloca:
1192 case Instruction::GetElementPtr: {
1201 for (
unsigned i = 1, e =
I->getNumOperands(); i != e; ++i, ++GTI) {
1217 "Access to structure field must be known at compile time");
1222 unsigned Idx = cast<ConstantInt>(
Index)->getZExtValue();
1225 AccConstIndices +=
Offset;
1236 unsigned IndexBitWidth =
Index->getType()->getScalarSizeInBits();
1250 APInt ScalingFactor(IndexBitWidth, TypeSizeInBytes);
1251 IndexConst *= ScalingFactor;
1268 true,
false, Known, IndexBits);
1273 true,
false, Known,
Index);
1277 case Instruction::PHI: {
1280 Value *R =
nullptr, *L =
nullptr;
1290 if ((
Opcode == Instruction::LShr ||
Opcode == Instruction::AShr ||
1291 Opcode == Instruction::Shl) &&
1306 case Instruction::Shl:
1310 case Instruction::LShr:
1315 case Instruction::AShr:
1326 if (
Opcode == Instruction::Add ||
1327 Opcode == Instruction::Sub ||
1328 Opcode == Instruction::And ||
1329 Opcode == Instruction::Or ||
1330 Opcode == Instruction::Mul) {
1337 unsigned OpNum =
P->getOperand(0) == R ? 0 : 1;
1338 Instruction *RInst =
P->getIncomingBlock(OpNum)->getTerminator();
1339 Instruction *LInst =
P->getIncomingBlock(1-OpNum)->getTerminator();
1354 auto *OverflowOp = dyn_cast<OverflowingBinaryOperator>(BO);
1365 if (
Opcode == Instruction::Add) {
1392 if (
P->getNumIncomingValues() == 0)
1399 if (isa_and_nonnull<UndefValue>(
P->hasConstantValue()))
1404 for (
unsigned u = 0, e =
P->getNumIncomingValues(); u < e; ++u) {
1405 Value *IncValue =
P->getIncomingValue(u);
1407 if (IncValue ==
P)
continue;
1414 RecQ.
CxtI =
P->getIncomingBlock(u)->getTerminator();
1435 if ((TrueSucc ==
P->getParent()) != (FalseSucc ==
P->getParent())) {
1437 if (FalseSucc ==
P->getParent())
1451 Known2 = KnownUnion;
1465 case Instruction::Call:
1466 case Instruction::Invoke:
1473 if (
const Value *RV = cast<CallBase>(
I)->getReturnedArgOperand()) {
1478 switch (II->getIntrinsicID()) {
1480 case Intrinsic::abs: {
1482 bool IntMinIsPoison =
match(II->getArgOperand(1),
m_One());
1483 Known = Known2.
abs(IntMinIsPoison);
1486 case Intrinsic::bitreverse:
1491 case Intrinsic::bswap:
1496 case Intrinsic::ctlz: {
1502 PossibleLZ = std::min(PossibleLZ,
BitWidth - 1);
1507 case Intrinsic::cttz: {
1513 PossibleTZ = std::min(PossibleTZ,
BitWidth - 1);
1518 case Intrinsic::ctpop: {
1529 case Intrinsic::fshr:
1530 case Intrinsic::fshl: {
1537 if (II->getIntrinsicID() == Intrinsic::fshr)
1550 case Intrinsic::uadd_sat:
1555 case Intrinsic::usub_sat:
1560 case Intrinsic::sadd_sat:
1565 case Intrinsic::ssub_sat:
1570 case Intrinsic::umin:
1575 case Intrinsic::umax:
1580 case Intrinsic::smin:
1585 case Intrinsic::smax:
1590 case Intrinsic::ptrmask: {
1593 const Value *Mask =
I->getOperand(1);
1594 Known2 =
KnownBits(Mask->getType()->getScalarSizeInBits());
1600 case Intrinsic::x86_sse42_crc32_64_64:
1603 case Intrinsic::riscv_vsetvli:
1604 case Intrinsic::riscv_vsetvlimax:
1610 case Intrinsic::vscale: {
1611 if (!II->getParent() || !II->getFunction())
1620 case Instruction::ShuffleVector: {
1621 auto *Shuf = dyn_cast<ShuffleVectorInst>(
I);
1629 APInt DemandedLHS, DemandedRHS;
1636 if (!!DemandedLHS) {
1637 const Value *
LHS = Shuf->getOperand(0);
1643 if (!!DemandedRHS) {
1644 const Value *
RHS = Shuf->getOperand(1);
1650 case Instruction::InsertElement: {
1651 if (isa<ScalableVectorType>(
I->getType())) {
1655 const Value *Vec =
I->getOperand(0);
1656 const Value *Elt =
I->getOperand(1);
1657 auto *CIdx = dyn_cast<ConstantInt>(
I->getOperand(2));
1660 if (!CIdx || CIdx->getValue().uge(NumElts)) {
1666 unsigned EltIdx = CIdx->getZExtValue();
1668 if (DemandedElts[EltIdx]) {
1675 APInt DemandedVecElts = DemandedElts;
1677 if (!!DemandedVecElts) {
1683 case Instruction::ExtractElement: {
1686 const Value *Vec =
I->getOperand(0);
1688 auto *CIdx = dyn_cast<ConstantInt>(
Idx);
1689 if (isa<ScalableVectorType>(Vec->
getType())) {
1694 unsigned NumElts = cast<FixedVectorType>(Vec->
getType())->getNumElements();
1696 if (CIdx && CIdx->getValue().ult(NumElts))
1701 case Instruction::ExtractValue:
1702 if (
IntrinsicInst *II = dyn_cast<IntrinsicInst>(
I->getOperand(0))) {
1706 switch (II->getIntrinsicID()) {
1708 case Intrinsic::uadd_with_overflow:
1709 case Intrinsic::sadd_with_overflow:
1711 II->getArgOperand(1),
false, DemandedElts,
1712 Known, Known2,
Depth, Q);
1714 case Intrinsic::usub_with_overflow:
1715 case Intrinsic::ssub_with_overflow:
1717 II->getArgOperand(1),
false, DemandedElts,
1718 Known, Known2,
Depth, Q);
1720 case Intrinsic::umul_with_overflow:
1721 case Intrinsic::smul_with_overflow:
1723 DemandedElts, Known, Known2,
Depth, Q);
1729 case Instruction::Freeze:
1773 if (!DemandedElts) {
1779 assert(V &&
"No Value?");
1783 Type *Ty = V->getType();
1787 "Not integer or pointer type!");
1789 if (
auto *FVTy = dyn_cast<FixedVectorType>(Ty)) {
1791 FVTy->getNumElements() == DemandedElts.
getBitWidth() &&
1792 "DemandedElt width should equal the fixed vector number of elements");
1795 "DemandedElt width should be 1 for scalars or scalable vectors");
1801 "V and Known should have same BitWidth");
1804 "V and Known should have same BitWidth");
1815 if (isa<ConstantPointerNull>(V) || isa<ConstantAggregateZero>(V)) {
1822 assert(!isa<ScalableVectorType>(V->getType()));
1826 for (
unsigned i = 0, e = CDV->getNumElements(); i != e; ++i) {
1827 if (!DemandedElts[i])
1829 APInt Elt = CDV->getElementAsAPInt(i);
1836 if (
const auto *CV = dyn_cast<ConstantVector>(V)) {
1837 assert(!isa<ScalableVectorType>(V->getType()));
1841 for (
unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
1842 if (!DemandedElts[i])
1845 if (isa<PoisonValue>(Element))
1847 auto *ElementCI = dyn_cast_or_null<ConstantInt>(Element);
1852 const APInt &Elt = ElementCI->getValue();
1863 if (isa<UndefValue>(V))
1868 assert(!isa<ConstantData>(V) &&
"Unhandled constant data!");
1876 if (
const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
1877 if (!GA->isInterposable())
1882 if (
const Operator *
I = dyn_cast<Operator>(V))
1884 else if (
const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
1885 if (std::optional<ConstantRange> CR = GV->getAbsoluteSymbolRange())
1886 Known = CR->toKnownBits();
1890 if (isa<PointerType>(V->getType())) {
1891 Align Alignment = V->getPointerAlignment(Q.
DL);
1901 assert((Known.
Zero & Known.
One) == 0 &&
"Bits known to be one AND zero?");
1909 Value *Start =
nullptr, *Step =
nullptr;
1915 if (U.get() == Start) {
1931 case Instruction::Mul:
1936 case Instruction::SDiv:
1942 case Instruction::UDiv:
1948 case Instruction::Shl:
1950 case Instruction::AShr:
1954 case Instruction::LShr:
1969 if (isa<Constant>(V))
1973 if (OrZero && V->getType()->getScalarSizeInBits() == 1)
1976 auto *
I = dyn_cast<Instruction>(V);
1983 return F->hasFnAttribute(Attribute::VScaleRange);
2000 switch (
I->getOpcode()) {
2001 case Instruction::ZExt:
2003 case Instruction::Trunc:
2005 case Instruction::Shl:
2009 case Instruction::LShr:
2010 if (OrZero || Q.
IIQ.
isExact(cast<BinaryOperator>(
I)))
2013 case Instruction::UDiv:
2017 case Instruction::Mul:
2021 case Instruction::And:
2032 case Instruction::Add: {
2038 if (
match(
I->getOperand(0),
2042 if (
match(
I->getOperand(1),
2047 unsigned BitWidth = V->getType()->getScalarSizeInBits();
2056 if ((~(LHSBits.
Zero & RHSBits.
Zero)).isPowerOf2())
2064 case Instruction::Select:
2067 case Instruction::PHI: {
2071 auto *PN = cast<PHINode>(
I);
2088 RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator();
2089 return isKnownToBeAPowerOfTwo(U.get(), OrZero, NewDepth, RecQ);
2092 case Instruction::Invoke:
2093 case Instruction::Call: {
2094 if (
auto *II = dyn_cast<IntrinsicInst>(
I)) {
2095 switch (II->getIntrinsicID()) {
2096 case Intrinsic::umax:
2097 case Intrinsic::smax:
2098 case Intrinsic::umin:
2099 case Intrinsic::smin:
2104 case Intrinsic::bitreverse:
2105 case Intrinsic::bswap:
2107 case Intrinsic::fshr:
2108 case Intrinsic::fshl:
2110 if (II->getArgOperand(0) == II->getArgOperand(1))
2134 F =
I->getFunction();
2136 if (!
GEP->isInBounds() ||
2141 assert(
GEP->getType()->isPointerTy() &&
"We only support plain pointer GEP");
2152 GTI != GTE; ++GTI) {
2154 if (
StructType *STy = GTI.getStructTypeOrNull()) {
2155 ConstantInt *OpC = cast<ConstantInt>(GTI.getOperand());
2159 if (ElementOffset > 0)
2170 if (
ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand())) {
2194 assert(!isa<Constant>(V) &&
"Called for constant?");
2199 unsigned NumUsesExplored = 0;
2200 for (
const auto *U : V->users()) {
2208 if (
const auto *CB = dyn_cast<CallBase>(U))
2209 if (
auto *CalledFunc = CB->getCalledFunction())
2210 for (
const Argument &Arg : CalledFunc->args())
2211 if (CB->getArgOperand(Arg.getArgNo()) == V &&
2212 Arg.hasNonNullAttr(
false) &&
2220 V->getType()->getPointerAddressSpace()) &&
2237 NonNullIfTrue =
true;
2239 NonNullIfTrue =
false;
2245 for (
const auto *CmpU : U->users()) {
2247 if (Visited.
insert(CmpU).second)
2250 while (!WorkList.
empty()) {
2259 for (
const auto *CurrU : Curr->users())
2260 if (Visited.
insert(CurrU).second)
2265 if (
const BranchInst *BI = dyn_cast<BranchInst>(Curr)) {
2266 assert(BI->isConditional() &&
"uses a comparison!");
2269 BI->getSuccessor(NonNullIfTrue ? 0 : 1);
2273 }
else if (NonNullIfTrue &&
isGuard(Curr) &&
2274 DT->
dominates(cast<Instruction>(Curr), CtxI)) {
2288 const unsigned NumRanges = Ranges->getNumOperands() / 2;
2290 for (
unsigned i = 0; i < NumRanges; ++i) {
2292 mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 0));
2294 mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 1));
2296 if (Range.contains(
Value))
2306 Value *Start =
nullptr, *Step =
nullptr;
2307 const APInt *StartC, *StepC;
2313 case Instruction::Add:
2319 case Instruction::Mul:
2322 case Instruction::Shl:
2324 case Instruction::AShr:
2325 case Instruction::LShr:
2374 if (
auto *
C = dyn_cast<Constant>(
X))
2392 auto ShiftOp = [&](
const APInt &Lhs,
const APInt &Rhs) {
2393 switch (
I->getOpcode()) {
2394 case Instruction::Shl:
2395 return Lhs.
shl(Rhs);
2396 case Instruction::LShr:
2397 return Lhs.
lshr(Rhs);
2398 case Instruction::AShr:
2399 return Lhs.
ashr(Rhs);
2405 auto InvShiftOp = [&](
const APInt &Lhs,
const APInt &Rhs) {
2406 switch (
I->getOpcode()) {
2407 case Instruction::Shl:
2408 return Lhs.
lshr(Rhs);
2409 case Instruction::LShr:
2410 case Instruction::AShr:
2411 return Lhs.
shl(Rhs);
2424 if (MaxShift.
uge(NumBits))
2427 if (!ShiftOp(KnownVal.
One, MaxShift).isZero())
2432 if (InvShiftOp(KnownVal.
Zero, NumBits - MaxShift)
2441 const APInt &DemandedElts,
2444 switch (
I->getOpcode()) {
2445 case Instruction::Alloca:
2447 return I->getType()->getPointerAddressSpace() == 0;
2448 case Instruction::GetElementPtr:
2449 if (
I->getType()->isPointerTy())
2452 case Instruction::BitCast: {
2480 Type *FromTy =
I->getOperand(0)->getType();
2485 case Instruction::IntToPtr:
2489 if (!isa<ScalableVectorType>(
I->getType()) &&
2494 case Instruction::PtrToInt:
2497 if (!isa<ScalableVectorType>(
I->getType()) &&
2502 case Instruction::Sub:
2505 case Instruction::Or:
2509 case Instruction::SExt:
2510 case Instruction::ZExt:
2514 case Instruction::Shl: {
2529 case Instruction::LShr:
2530 case Instruction::AShr: {
2545 case Instruction::UDiv:
2546 case Instruction::SDiv: {
2549 if (cast<PossiblyExactOperator>(
I)->isExact())
2552 std::optional<bool> XUgeY;
2562 if (
I->getOpcode() == Instruction::SDiv) {
2564 XKnown = XKnown.
abs(
false);
2565 YKnown = YKnown.
abs(
false);
2571 return XUgeY && *XUgeY;
2573 case Instruction::Add: {
2578 auto *BO = cast<OverflowingBinaryOperator>(
I);
2586 case Instruction::Mul: {
2615 case Instruction::Select: {
2622 auto SelectArmIsNonZero = [&](
bool IsTrueArm) {
2624 Op = IsTrueArm ?
I->getOperand(1) :
I->getOperand(2);
2637 Pred = ICmpInst::getInversePredicate(Pred);
2642 if (SelectArmIsNonZero(
true) &&
2643 SelectArmIsNonZero(
false))
2647 case Instruction::PHI: {
2648 auto *PN = cast<PHINode>(
I);
2658 RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator();
2660 ICmpInst::Predicate Pred;
2662 BasicBlock *TrueSucc, *FalseSucc;
2663 if (match(RecQ.CxtI,
2664 m_Br(m_c_ICmp(Pred, m_Specific(U.get()), m_Value(X)),
2665 m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc)))) {
2667 if ((TrueSucc == PN->getParent()) != (FalseSucc == PN->getParent())) {
2669 if (FalseSucc == PN->getParent())
2670 Pred = CmpInst::getInversePredicate(Pred);
2671 if (cmpExcludesZero(Pred, X))
2679 case Instruction::ExtractElement:
2680 if (
const auto *EEI = dyn_cast<ExtractElementInst>(
I)) {
2681 const Value *Vec = EEI->getVectorOperand();
2682 const Value *
Idx = EEI->getIndexOperand();
2683 auto *CIdx = dyn_cast<ConstantInt>(
Idx);
2684 if (
auto *VecTy = dyn_cast<FixedVectorType>(Vec->
getType())) {
2685 unsigned NumElts = VecTy->getNumElements();
2687 if (CIdx && CIdx->getValue().ult(NumElts))
2693 case Instruction::Freeze:
2697 case Instruction::Load: {
2698 auto *LI = cast<LoadInst>(
I);
2701 if (
auto *PtrT = dyn_cast<PointerType>(
I->getType()))
2711 case Instruction::Call:
2712 case Instruction::Invoke:
2713 if (
I->getType()->isPointerTy()) {
2714 const auto *Call = cast<CallBase>(
I);
2715 if (Call->isReturnNonNull())
2719 }
else if (
const Value *RV = cast<CallBase>(
I)->getReturnedArgOperand()) {
2724 if (
auto *II = dyn_cast<IntrinsicInst>(
I)) {
2725 switch (II->getIntrinsicID()) {
2726 case Intrinsic::sshl_sat:
2727 case Intrinsic::ushl_sat:
2728 case Intrinsic::abs:
2729 case Intrinsic::bitreverse:
2730 case Intrinsic::bswap:
2731 case Intrinsic::ctpop:
2733 case Intrinsic::ssub_sat:
2735 II->getArgOperand(0), II->getArgOperand(1));
2736 case Intrinsic::sadd_sat:
2738 II->getArgOperand(0), II->getArgOperand(1),
2740 case Intrinsic::umax:
2741 case Intrinsic::uadd_sat:
2744 case Intrinsic::smin:
2745 case Intrinsic::smax: {
2746 auto KnownOpImpliesNonZero = [&](
const KnownBits &K) {
2747 return II->getIntrinsicID() == Intrinsic::smin
2749 : K.isStrictlyPositive();
2753 if (KnownOpImpliesNonZero(XKnown))
2757 if (KnownOpImpliesNonZero(YKnown))
2764 case Intrinsic::umin:
2767 case Intrinsic::cttz:
2770 case Intrinsic::ctlz:
2773 case Intrinsic::fshr:
2774 case Intrinsic::fshl:
2776 if (II->getArgOperand(0) == II->getArgOperand(1))
2779 case Intrinsic::vscale:
2792 return Known.
One != 0;
2805 Type *Ty = V->getType();
2808 if (
auto *FVTy = dyn_cast<FixedVectorType>(Ty)) {
2810 FVTy->getNumElements() == DemandedElts.
getBitWidth() &&
2811 "DemandedElt width should equal the fixed vector number of elements");
2814 "DemandedElt width should be 1 for scalars");
2818 if (
auto *
C = dyn_cast<Constant>(V)) {
2819 if (
C->isNullValue())
2821 if (isa<ConstantInt>(
C))
2827 if (
auto *VecTy = dyn_cast<FixedVectorType>(
C->getType())) {
2828 for (
unsigned i = 0, e = VecTy->getNumElements(); i != e; ++i) {
2829 if (!DemandedElts[i])
2831 Constant *Elt =
C->getAggregateElement(i);
2834 if (!isa<UndefValue>(Elt) && !isa<ConstantInt>(Elt))
2843 if (
const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
2844 if (!GV->isAbsoluteSymbolRef() && !GV->hasExternalWeakLinkage() &&
2845 GV->getType()->getAddressSpace() == 0)
2850 if (!isa<ConstantExpr>(V))
2854 if (
auto *
I = dyn_cast<Instruction>(V)) {
2858 if (
auto *Ty = dyn_cast<IntegerType>(V->getType())) {
2859 const APInt ZeroValue(Ty->getBitWidth(), 0);
2875 if (
PointerType *PtrTy = dyn_cast<PointerType>(V->getType())) {
2878 if (
const Argument *
A = dyn_cast<Argument>(V)) {
2879 if (((
A->hasPassPointeeByValueCopyAttr() &&
2881 A->hasNonNullAttr()))
2886 if (
const auto *
I = dyn_cast<Operator>(V))
2890 if (!isa<Constant>(V) &&
2898 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
2899 APInt DemandedElts =
2910static std::optional<std::pair<Value*, Value*>>
2914 return std::nullopt;
2923 case Instruction::Add:
2924 case Instruction::Sub:
2930 case Instruction::Mul: {
2934 auto *OBO1 = cast<OverflowingBinaryOperator>(Op1);
2935 auto *OBO2 = cast<OverflowingBinaryOperator>(Op2);
2936 if ((!OBO1->hasNoUnsignedWrap() || !OBO2->hasNoUnsignedWrap()) &&
2937 (!OBO1->hasNoSignedWrap() || !OBO2->hasNoSignedWrap()))
2943 !cast<ConstantInt>(Op1->
getOperand(1))->isZero())
2947 case Instruction::Shl: {
2950 auto *OBO1 = cast<OverflowingBinaryOperator>(Op1);
2951 auto *OBO2 = cast<OverflowingBinaryOperator>(Op2);
2952 if ((!OBO1->hasNoUnsignedWrap() || !OBO2->hasNoUnsignedWrap()) &&
2953 (!OBO1->hasNoSignedWrap() || !OBO2->hasNoSignedWrap()))
2960 case Instruction::AShr:
2961 case Instruction::LShr: {
2962 auto *PEO1 = cast<PossiblyExactOperator>(Op1);
2963 auto *PEO2 = cast<PossiblyExactOperator>(Op2);
2964 if (!PEO1->isExact() || !PEO2->isExact())
2971 case Instruction::SExt:
2972 case Instruction::ZExt:
2976 case Instruction::PHI: {
2977 const PHINode *PN1 = cast<PHINode>(Op1);
2978 const PHINode *PN2 = cast<PHINode>(Op2);
2984 Value *Start1 =
nullptr, *Step1 =
nullptr;
2986 Value *Start2 =
nullptr, *Step2 =
nullptr;
2993 cast<Operator>(BO2));
3002 if (Values->first != PN1 || Values->second != PN2)
3005 return std::make_pair(Start1, Start2);
3008 return std::nullopt;
3015 if (!BO || BO->
getOpcode() != Instruction::Add)
3031 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(V2)) {
3034 (OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap()) &&
3044 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(V2)) {
3047 (OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap()) &&
3060 bool UsedFullRecursion =
false;
3062 if (!VisitedBBs.
insert(IncomBB).second)
3066 const APInt *C1, *C2;
3071 if (UsedFullRecursion)
3075 RecQ.
CxtI = IncomBB->getTerminator();
3078 UsedFullRecursion =
true;
3085 const SelectInst *SI1 = dyn_cast<SelectInst>(V1);
3089 if (
const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) {
3091 const Value *Cond2 = SI2->getCondition();
3107 if (V1->
getType() != V2->getType())
3117 auto *O1 = dyn_cast<Operator>(V1);
3118 auto *O2 = dyn_cast<Operator>(V2);
3119 if (O1 && O2 && O1->getOpcode() == O2->getOpcode()) {
3123 if (
const PHINode *PN1 = dyn_cast<PHINode>(V1)) {
3124 const PHINode *PN2 = cast<PHINode>(V2);
3171 return Mask.isSubsetOf(Known.
Zero);
3180 "Input should be a Select!");
3190 const Value *LHS2 =
nullptr, *RHS2 =
nullptr;
3202 return CLow->
sle(*CHigh);
3207 const APInt *&CHigh) {
3209 II->
getIntrinsicID() == Intrinsic::smax) &&
"Must be smin/smax");
3212 auto *InnerII = dyn_cast<IntrinsicInst>(II->
getArgOperand(0));
3213 if (!InnerII || InnerII->getIntrinsicID() != InverseID ||
3220 return CLow->
sle(*CHigh);
3228 const APInt &DemandedElts,
3230 const auto *CV = dyn_cast<Constant>(V);
3231 if (!CV || !isa<FixedVectorType>(CV->getType()))
3234 unsigned MinSignBits = TyBits;
3235 unsigned NumElts = cast<FixedVectorType>(CV->getType())->getNumElements();
3236 for (
unsigned i = 0; i != NumElts; ++i) {
3237 if (!DemandedElts[i])
3240 auto *Elt = dyn_cast_or_null<ConstantInt>(CV->getAggregateElement(i));
3244 MinSignBits = std::min(MinSignBits, Elt->getValue().getNumSignBits());
3251 const APInt &DemandedElts,
3257 assert(Result > 0 &&
"At least one sign bit needs to be present!");
3269 const APInt &DemandedElts,
3271 Type *Ty = V->getType();
3275 if (
auto *FVTy = dyn_cast<FixedVectorType>(Ty)) {
3277 FVTy->getNumElements() == DemandedElts.
getBitWidth() &&
3278 "DemandedElt width should equal the fixed vector number of elements");
3281 "DemandedElt width should be 1 for scalars");
3295 unsigned FirstAnswer = 1;
3303 if (
auto *U = dyn_cast<Operator>(V)) {
3306 case Instruction::SExt:
3307 Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits();
3310 case Instruction::SDiv: {
3311 const APInt *Denominator;
3323 return std::min(TyBits, NumBits + Denominator->
logBase2());
3328 case Instruction::SRem: {
3331 const APInt *Denominator;
3352 unsigned ResBits = TyBits - Denominator->
ceilLogBase2();
3353 Tmp = std::max(Tmp, ResBits);
3359 case Instruction::AShr: {
3364 if (ShAmt->
uge(TyBits))
3367 Tmp += ShAmtLimited;
3368 if (Tmp > TyBits) Tmp = TyBits;
3372 case Instruction::Shl: {
3377 if (ShAmt->
uge(TyBits) ||
3378 ShAmt->
uge(Tmp))
break;
3384 case Instruction::And:
3385 case Instruction::Or:
3386 case Instruction::Xor:
3391 FirstAnswer = std::min(Tmp, Tmp2);
3398 case Instruction::Select: {
3402 const APInt *CLow, *CHigh;
3407 if (Tmp == 1)
break;
3409 return std::min(Tmp, Tmp2);
3412 case Instruction::Add:
3416 if (Tmp == 1)
break;
3419 if (
const auto *CRHS = dyn_cast<Constant>(U->getOperand(1)))
3420 if (CRHS->isAllOnesValue()) {
3426 if ((Known.
Zero | 1).isAllOnes())
3436 if (Tmp2 == 1)
break;
3437 return std::min(Tmp, Tmp2) - 1;
3439 case Instruction::Sub:
3441 if (Tmp2 == 1)
break;
3444 if (
const auto *CLHS = dyn_cast<Constant>(U->getOperand(0)))
3445 if (CLHS->isNullValue()) {
3450 if ((Known.
Zero | 1).isAllOnes())
3465 if (Tmp == 1)
break;
3466 return std::min(Tmp, Tmp2) - 1;
3468 case Instruction::Mul: {
3472 if (SignBitsOp0 == 1)
break;
3474 if (SignBitsOp1 == 1)
break;
3475 unsigned OutValidBits =
3476 (TyBits - SignBitsOp0 + 1) + (TyBits - SignBitsOp1 + 1);
3477 return OutValidBits > TyBits ? 1 : TyBits - OutValidBits + 1;
3480 case Instruction::PHI: {
3481 const PHINode *PN = cast<PHINode>(U);
3484 if (NumIncomingValues > 4)
break;
3486 if (NumIncomingValues == 0)
break;
3492 for (
unsigned i = 0, e = NumIncomingValues; i != e; ++i) {
3493 if (Tmp == 1)
return Tmp;
3501 case Instruction::Trunc: {
3506 unsigned OperandTyBits = U->getOperand(0)->getType()->getScalarSizeInBits();
3507 if (Tmp > (OperandTyBits - TyBits))
3508 return Tmp - (OperandTyBits - TyBits);
3513 case Instruction::ExtractElement:
3520 case Instruction::ShuffleVector: {
3523 auto *Shuf = dyn_cast<ShuffleVectorInst>(U);
3528 APInt DemandedLHS, DemandedRHS;
3533 Tmp = std::numeric_limits<unsigned>::max();
3534 if (!!DemandedLHS) {
3535 const Value *
LHS = Shuf->getOperand(0);
3542 if (!!DemandedRHS) {
3543 const Value *
RHS = Shuf->getOperand(1);
3545 Tmp = std::min(Tmp, Tmp2);
3551 assert(Tmp <= TyBits &&
"Failed to determine minimum sign bits");
3554 case Instruction::Call: {
3555 if (
const auto *II = dyn_cast<IntrinsicInst>(U)) {
3556 switch (II->getIntrinsicID()) {
3558 case Intrinsic::abs:
3560 if (Tmp == 1)
break;
3564 case Intrinsic::smin:
3565 case Intrinsic::smax: {
3566 const APInt *CLow, *CHigh;
3581 if (
unsigned VecSignBits =
3599 if (
F->isIntrinsic())
3600 return F->getIntrinsicID();
3606 if (
F->hasLocalLinkage() || !TLI || !TLI->
getLibFunc(CB, Func) ||
3616 return Intrinsic::sin;
3620 return Intrinsic::cos;
3624 return Intrinsic::exp;
3628 return Intrinsic::exp2;
3632 return Intrinsic::log;
3634 case LibFunc_log10f:
3635 case LibFunc_log10l:
3636 return Intrinsic::log10;
3640 return Intrinsic::log2;
3644 return Intrinsic::fabs;
3648 return Intrinsic::minnum;
3652 return Intrinsic::maxnum;
3653 case LibFunc_copysign:
3654 case LibFunc_copysignf:
3655 case LibFunc_copysignl:
3656 return Intrinsic::copysign;
3658 case LibFunc_floorf:
3659 case LibFunc_floorl:
3660 return Intrinsic::floor;
3664 return Intrinsic::ceil;
3666 case LibFunc_truncf:
3667 case LibFunc_truncl:
3668 return Intrinsic::trunc;
3672 return Intrinsic::rint;
3673 case LibFunc_nearbyint:
3674 case LibFunc_nearbyintf:
3675 case LibFunc_nearbyintl:
3676 return Intrinsic::nearbyint;
3678 case LibFunc_roundf:
3679 case LibFunc_roundl:
3680 return Intrinsic::round;
3681 case LibFunc_roundeven:
3682 case LibFunc_roundevenf:
3683 case LibFunc_roundevenl:
3684 return Intrinsic::roundeven;
3688 return Intrinsic::pow;
3692 return Intrinsic::sqrt;
3706 bool SignBitOnly,
unsigned Depth) {
3712 if (
const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) {
3713 return !CFP->getValueAPF().isNegative() ||
3714 (!SignBitOnly && CFP->getValueAPF().isZero());
3718 if (
auto *CV = dyn_cast<Constant>(V)) {
3719 if (
auto *CVFVTy = dyn_cast<FixedVectorType>(CV->getType())) {
3720 unsigned NumElts = CVFVTy->getNumElements();
3721 for (
unsigned i = 0; i != NumElts; ++i) {
3722 auto *CFP = dyn_cast_or_null<ConstantFP>(CV->getAggregateElement(i));
3725 if (CFP->getValueAPF().isNegative() &&
3726 (SignBitOnly || !CFP->getValueAPF().isZero()))
3738 const Operator *
I = dyn_cast<Operator>(V);
3742 switch (
I->getOpcode()) {
3746 case Instruction::UIToFP:
3748 case Instruction::FDiv:
3750 if (
I->getOperand(0) ==
I->getOperand(1) &&
3751 (!SignBitOnly || cast<FPMathOperator>(
I)->hasNoNaNs()))
3756 SignBitOnly,
Depth + 1) &&
3759 case Instruction::FMul:
3761 if (
I->getOperand(0) ==
I->getOperand(1) &&
3762 (!SignBitOnly || cast<FPMathOperator>(
I)->hasNoNaNs()))
3766 case Instruction::FAdd:
3767 case Instruction::FRem:
3769 SignBitOnly,
Depth + 1) &&
3771 SignBitOnly,
Depth + 1);
3772 case Instruction::Select:
3774 SignBitOnly,
Depth + 1) &&
3776 SignBitOnly,
Depth + 1);
3777 case Instruction::FPExt:
3778 case Instruction::FPTrunc:
3781 SignBitOnly,
Depth + 1);
3782 case Instruction::ExtractElement:
3787 SignBitOnly,
Depth + 1);
3788 case Instruction::Call:
3789 const auto *CI = cast<CallInst>(
I);
3794 case Intrinsic::canonicalize:
3795 case Intrinsic::arithmetic_fence:
3796 case Intrinsic::floor:
3797 case Intrinsic::ceil:
3798 case Intrinsic::trunc:
3799 case Intrinsic::rint:
3800 case Intrinsic::nearbyint:
3801 case Intrinsic::round:
3802 case Intrinsic::roundeven:
3803 case Intrinsic::fptrunc_round:
3805 SignBitOnly,
Depth + 1);
3806 case Intrinsic::maxnum: {
3807 Value *V0 =
I->getOperand(0), *V1 =
I->getOperand(1);
3808 auto isPositiveNum = [&](
Value *V) {
3826 return isPositiveNum(V0) || isPositiveNum(V1);
3829 case Intrinsic::maximum:
3831 SignBitOnly,
Depth + 1) ||
3833 SignBitOnly,
Depth + 1);
3834 case Intrinsic::minnum:
3835 case Intrinsic::minimum:
3837 SignBitOnly,
Depth + 1) &&
3839 SignBitOnly,
Depth + 1);
3840 case Intrinsic::exp:
3841 case Intrinsic::exp2:
3842 case Intrinsic::fabs:
3844 case Intrinsic::copysign:
3848 case Intrinsic::sqrt:
3852 return CI->hasNoNaNs() &&
3853 (CI->hasNoSignedZeros() ||
3856 case Intrinsic::powi:
3876 SignBitOnly,
Depth + 1);
3878 case Intrinsic::fma:
3879 case Intrinsic::fmuladd:
3881 return I->getOperand(0) ==
I->getOperand(1) &&
3882 (!SignBitOnly || cast<FPMathOperator>(
I)->hasNoNaNs()) &&
3884 SignBitOnly,
Depth + 1);
3939 switch (Mode.Input) {
3959 if (!Src.isKnownNeverPosZero() && !Src.isKnownNeverNegZero())
3963 if (Src.isKnownNeverSubnormal())
3994 bool LookThroughSrc) {
4002std::pair<Value *, FPClassTest>
4004 const APFloat *ConstRHS,
bool LookThroughSrc) {
4007 return {
LHS, ~fcNan};
4013 if (ConstRHS->
isZero()) {
4027 return {
LHS, ~fcZero};
4029 return {
LHS, ~fcNan & ~fcZero};
4033 return {
LHS, ~fcNan};
4106 Mask = ~fcNegInf & ~fcNan;
4110 Mask = ~fcPosInf & ~fcNan;
4204 }
else if (ConstRHS->
isNaN()) {
4231 "Got assumption for the wrong function!");
4232 assert(
I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
4233 "must be an assume intrinsic");
4242 auto [TestedValue, TestedMask] =
4245 if (TestedValue == V)
4246 KnownFromAssume &= TestedMask;
4250 auto [TestedValue, TestedMask] =
4252 if (TestedValue == V)
4253 KnownFromAssume &= TestedMask;
4255 }
else if (
match(
I->getArgOperand(0),
4256 m_Intrinsic<Intrinsic::is_fpclass>(
4258 KnownFromAssume &=
static_cast<FPClassTest>(ClassVal);
4262 return KnownFromAssume;
4272 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
4273 APInt DemandedElts =
4279 const APInt &DemandedElts,
4283 if ((InterestedClasses &
4289 KnownSrc,
Depth + 1, Q);
4305 assert(Known.
isUnknown() &&
"should not be called with known information");
4307 if (!DemandedElts) {
4315 if (
auto *CFP = dyn_cast_or_null<ConstantFP>(V)) {
4317 Known.
SignBit = CFP->isNegative();
4322 auto *VFVTy = dyn_cast<FixedVectorType>(V->getType());
4323 const Constant *CV = dyn_cast<Constant>(V);
4328 unsigned NumElts = VFVTy->getNumElements();
4329 for (
unsigned i = 0; i != NumElts; ++i) {
4335 if (isa<UndefValue>(Elt))
4337 auto *CElt = dyn_cast<ConstantFP>(Elt);
4343 KnownFPClass KnownElt{CElt->getValueAPF().classify(), CElt->isNegative()};
4351 if (
const auto *CB = dyn_cast<CallBase>(V))
4352 KnownNotFromFlags |= CB->getRetNoFPClass();
4353 else if (
const auto *Arg = dyn_cast<Argument>(V))
4354 KnownNotFromFlags |= Arg->getNoFPClass();
4358 if (FPOp->hasNoNaNs())
4359 KnownNotFromFlags |=
fcNan;
4360 if (FPOp->hasNoInfs())
4361 KnownNotFromFlags |=
fcInf;
4366 KnownNotFromFlags |= ~AssumedClasses;
4371 InterestedClasses &= ~KnownNotFromFlags;
4384 const unsigned Opc =
Op->getOpcode();
4386 case Instruction::FNeg: {
4388 Known,
Depth + 1, Q);
4392 case Instruction::Select: {
4400 Value *TestedValue =
nullptr;
4403 const Function *
F = cast<Instruction>(
Op)->getFunction();
4405 Value *CmpLHS, *CmpRHS;
4412 bool LookThroughFAbsFNeg = CmpLHS !=
LHS && CmpLHS !=
RHS;
4413 std::tie(TestedValue, TestedMask) =
4416 m_Intrinsic<Intrinsic::is_fpclass>(
4421 if (TestedValue ==
LHS) {
4423 FilterLHS = TestedMask;
4424 }
else if (TestedValue ==
RHS) {
4426 FilterRHS = ~TestedMask;
4435 Known2,
Depth + 1, Q);
4441 case Instruction::Call: {
4445 case Intrinsic::fabs: {
4450 InterestedClasses, Known,
Depth + 1, Q);
4456 case Intrinsic::copysign: {
4460 Known,
Depth + 1, Q);
4462 KnownSign,
Depth + 1, Q);
4466 case Intrinsic::fma:
4467 case Intrinsic::fmuladd: {
4480 KnownAddend,
Depth + 1, Q);
4487 case Intrinsic::sqrt:
4488 case Intrinsic::experimental_constrained_sqrt: {
4491 if (InterestedClasses &
fcNan)
4495 KnownSrc,
Depth + 1, Q);