56#include "llvm/IR/IntrinsicsAArch64.h"
57#include "llvm/IR/IntrinsicsRISCV.h"
58#include "llvm/IR/IntrinsicsX86.h"
94 return DL.getPointerTypeSizeInBits(Ty);
106 CxtI = dyn_cast<Instruction>(V);
120 CxtI = dyn_cast<Instruction>(V1);
124 CxtI = dyn_cast<Instruction>(V2);
132 const APInt &DemandedElts,
134 if (isa<ScalableVectorType>(Shuf->
getType())) {
136 DemandedLHS = DemandedRHS = DemandedElts;
143 DemandedElts, DemandedLHS, DemandedRHS);
155 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
190 return ::computeKnownBits(V,
Depth,
199 return ::computeKnownBits(V, DemandedElts,
Depth,
209 "LHS and RHS should have the same type");
211 "LHS and RHS should be integers");
264 return !
I->user_empty() &&
all_of(
I->users(), [](
const User *U) {
265 ICmpInst::Predicate P;
266 return match(U, m_ICmp(P, m_Value(), m_Zero())) && ICmpInst::isEquality(P);
274 bool OrZero,
unsigned Depth,
277 return ::isKnownToBeAPowerOfTwo(V, OrZero,
Depth,
292 return ::isKnownNonZero(V,
Depth,
308 if (
auto *CI = dyn_cast<ConstantInt>(V))
309 return CI->getValue().isStrictlyPositive();
331 return ::isKnownNonEqual(V1, V2, 0,
333 safeCxtI(V2, V1, CxtI), UseInstrInfo));
343 return ::MaskedValueIsZero(V, Mask,
Depth,
353 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
363 return ::ComputeNumSignBits(V,
Depth,
373 return V->getType()->getScalarSizeInBits() - SignBits + 1;
377 bool NSW,
const APInt &DemandedElts,
409 bool isKnownNegativeOp0 = Known2.
isNegative();
412 (isKnownNonNegativeOp1 && isKnownNonNegativeOp0);
417 (isKnownNegativeOp1 && isKnownNonNegativeOp0 &&
419 (isKnownNegativeOp0 && isKnownNonNegativeOp1 && Known.
isNonZero());
423 bool SelfMultiply = Op0 == Op1;
444 unsigned NumRanges = Ranges.getNumOperands() / 2;
450 for (
unsigned i = 0; i < NumRanges; ++i) {
452 mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
454 mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
458 unsigned CommonPrefixBits =
459 (Range.getUnsignedMax() ^ Range.getUnsignedMin()).
countl_zero();
461 APInt UnsignedMax = Range.getUnsignedMax().zextOrTrunc(
BitWidth);
462 Known.
One &= UnsignedMax & Mask;
463 Known.
Zero &= ~UnsignedMax & Mask;
478 while (!WorkSet.
empty()) {
480 if (!Visited.
insert(V).second)
485 return EphValues.count(U);
490 if (V ==
I || (isa<Instruction>(V) &&
492 !cast<Instruction>(V)->isTerminator())) {
494 if (
const User *U = dyn_cast<User>(V))
506 return CI->isAssumeLikeIntrinsic();
566 if (Pred == ICmpInst::ICMP_UGT)
570 if (Pred == ICmpInst::ICMP_NE)
588 if (Q.
CxtI && V->getType()->isPointerTy()) {
591 V->getType()->getPointerAddressSpace()))
592 AttrKinds.
push_back(Attribute::Dereferenceable);
603 "Got assumption for the wrong function!");
609 assert(
I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
610 "must be an assume intrinsic");
636 QueryNoAC.
AC =
nullptr;
644 switch (Cmp->getPredicate()) {
647 case ICmpInst::ICMP_EQ:
654 }
else if (
match(Cmp,
664 Known.
One |= RHSKnown.
One & MaskKnown.
One;
678 }
else if (
match(Cmp,
702 }
else if (
match(Cmp,
764 Known.
One |= RHSKnown.
One <<
C;
777 case ICmpInst::ICMP_SGE:
789 case ICmpInst::ICMP_SGT:
801 case ICmpInst::ICMP_SLE:
813 case ICmpInst::ICMP_SLT:
825 case ICmpInst::ICMP_ULE:
835 case ICmpInst::ICMP_ULT:
857 case ICmpInst::ICMP_NE: {
877 if (V->getType()->isPointerTy()) {
879 V, { Attribute::Alignment }, Q.
CxtI, Q.
DT, Q.
AC)) {
893 "Got assumption for the wrong function!");
899 assert(
I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
900 "must be an assume intrinsic");
958 Known = KF(Known2, Known, ShAmtNonZero);
969 Value *
X =
nullptr, *
Y =
nullptr;
971 switch (
I->getOpcode()) {
972 case Instruction::And:
973 KnownOut = KnownLHS & KnownRHS;
983 KnownOut = KnownLHS.
blsi();
985 KnownOut = KnownRHS.
blsi();
988 case Instruction::Or:
989 KnownOut = KnownLHS | KnownRHS;
991 case Instruction::Xor:
992 KnownOut = KnownLHS ^ KnownRHS;
1002 const KnownBits &XBits =
I->getOperand(0) ==
X ? KnownLHS : KnownRHS;
1003 KnownOut = XBits.
blsmsk();
1016 if (!KnownOut.
Zero[0] && !KnownOut.
One[0] &&
1037 auto *FVTy = dyn_cast<FixedVectorType>(
I->getType());
1038 APInt DemandedElts =
1048 Attribute Attr =
F->getFnAttribute(Attribute::VScaleRange);
1056 return ConstantRange::getEmpty(
BitWidth);
1067 const APInt &DemandedElts,
1073 switch (
I->getOpcode()) {
1075 case Instruction::Load:
1080 case Instruction::And:
1086 case Instruction::Or:
1092 case Instruction::Xor:
1098 case Instruction::Mul: {
1101 Known, Known2,
Depth, Q);
1104 case Instruction::UDiv: {
1111 case Instruction::SDiv: {
1118 case Instruction::Select: {
1160 case Instruction::FPTrunc:
1161 case Instruction::FPExt:
1162 case Instruction::FPToUI:
1163 case Instruction::FPToSI:
1164 case Instruction::SIToFP:
1165 case Instruction::UIToFP:
1167 case Instruction::PtrToInt:
1168 case Instruction::IntToPtr:
1171 case Instruction::ZExt:
1172 case Instruction::Trunc: {
1173 Type *SrcTy =
I->getOperand(0)->getType();
1175 unsigned SrcBitWidth;
1183 assert(SrcBitWidth &&
"SrcBitWidth can't be zero");
1189 case Instruction::BitCast: {
1190 Type *SrcTy =
I->getOperand(0)->getType();
1194 !
I->getType()->isVectorTy()) {
1200 auto *SrcVecTy = dyn_cast<FixedVectorType>(SrcTy);
1201 if (!SrcVecTy || !SrcVecTy->getElementType()->isIntegerTy() ||
1202 !
I->getType()->isIntOrIntVectorTy() ||
1203 isa<ScalableVectorType>(
I->getType()))
1208 unsigned SubBitWidth = SrcVecTy->getScalarSizeInBits();
1225 unsigned SubScale =
BitWidth / SubBitWidth;
1227 for (
unsigned i = 0; i != NumElts; ++i) {
1228 if (DemandedElts[i])
1229 SubDemandedElts.
setBit(i * SubScale);
1233 for (
unsigned i = 0; i != SubScale; ++i) {
1237 Known.
insertBits(KnownSrc, ShiftElt * SubBitWidth);
1242 case Instruction::SExt: {
1244 unsigned SrcBitWidth =
I->getOperand(0)->getType()->getScalarSizeInBits();
1246 Known = Known.
trunc(SrcBitWidth);
1253 case Instruction::Shl: {
1257 bool ShAmtNonZero) {
1258 return KnownBits::shl(KnownVal, KnownAmt, NUW, NSW, ShAmtNonZero);
1268 case Instruction::LShr: {
1270 bool ShAmtNonZero) {
1281 case Instruction::AShr: {
1283 bool ShAmtNonZero) {
1290 case Instruction::Sub: {
1293 DemandedElts, Known, Known2,
Depth, Q);
1296 case Instruction::Add: {
1299 DemandedElts, Known, Known2,
Depth, Q);
1302 case Instruction::SRem:
1308 case Instruction::URem:
1313 case Instruction::Alloca:
1316 case Instruction::GetElementPtr: {
1325 for (
unsigned i = 1, e =
I->getNumOperands(); i != e; ++i, ++GTI) {
1341 "Access to structure field must be known at compile time");
1346 unsigned Idx = cast<ConstantInt>(
Index)->getZExtValue();
1349 AccConstIndices +=
Offset;
1360 unsigned IndexBitWidth =
Index->getType()->getScalarSizeInBits();
1374 APInt ScalingFactor(IndexBitWidth, TypeSizeInBytes);
1375 IndexConst *= ScalingFactor;
1392 true,
false, Known, IndexBits);
1397 true,
false, Known,
Index);
1401 case Instruction::PHI: {
1404 Value *R =
nullptr, *L =
nullptr;
1414 if ((Opcode == Instruction::LShr || Opcode == Instruction::AShr ||
1415 Opcode == Instruction::Shl) &&
1430 case Instruction::Shl:
1434 case Instruction::LShr:
1439 case Instruction::AShr:
1450 if (Opcode == Instruction::Add ||
1451 Opcode == Instruction::Sub ||
1452 Opcode == Instruction::And ||
1453 Opcode == Instruction::Or ||
1454 Opcode == Instruction::Mul) {
1461 unsigned OpNum =
P->getOperand(0) == R ? 0 : 1;
1462 Instruction *RInst =
P->getIncomingBlock(OpNum)->getTerminator();
1463 Instruction *LInst =
P->getIncomingBlock(1-OpNum)->getTerminator();
1478 auto *OverflowOp = dyn_cast<OverflowingBinaryOperator>(BO);
1489 if (Opcode == Instruction::Add) {
1498 else if (Opcode == Instruction::Sub && BO->
getOperand(0) ==
I) {
1506 else if (Opcode == Instruction::Mul && Known2.
isNonNegative() &&
1516 if (
P->getNumIncomingValues() == 0)
1523 if (isa_and_nonnull<UndefValue>(
P->hasConstantValue()))
1528 for (
unsigned u = 0, e =
P->getNumIncomingValues(); u < e; ++u) {
1529 Value *IncValue =
P->getIncomingValue(u);
1531 if (IncValue ==
P)
continue;
1538 RecQ.
CxtI =
P->getIncomingBlock(u)->getTerminator();
1557 if ((TrueSucc ==
P->getParent()) != (FalseSucc ==
P->getParent())) {
1559 if (FalseSucc ==
P->getParent())
1563 case CmpInst::Predicate::ICMP_EQ:
1566 case CmpInst::Predicate::ICMP_ULE:
1569 case CmpInst::Predicate::ICMP_ULT:
1589 case Instruction::Call:
1590 case Instruction::Invoke:
1597 if (
const Value *RV = cast<CallBase>(
I)->getReturnedArgOperand()) {
1602 switch (II->getIntrinsicID()) {
1604 case Intrinsic::abs: {
1606 bool IntMinIsPoison =
match(II->getArgOperand(1),
m_One());
1607 Known = Known2.
abs(IntMinIsPoison);
1610 case Intrinsic::bitreverse:
1615 case Intrinsic::bswap:
1620 case Intrinsic::ctlz: {
1626 PossibleLZ = std::min(PossibleLZ,
BitWidth - 1);
1631 case Intrinsic::cttz: {
1637 PossibleTZ = std::min(PossibleTZ,
BitWidth - 1);
1642 case Intrinsic::ctpop: {
1653 case Intrinsic::fshr:
1654 case Intrinsic::fshl: {
1661 if (II->getIntrinsicID() == Intrinsic::fshr)
1674 case Intrinsic::uadd_sat:
1679 case Intrinsic::usub_sat:
1684 case Intrinsic::sadd_sat:
1689 case Intrinsic::ssub_sat:
1694 case Intrinsic::umin:
1699 case Intrinsic::umax:
1704 case Intrinsic::smin:
1709 case Intrinsic::smax:
1714 case Intrinsic::x86_sse42_crc32_64_64:
1717 case Intrinsic::riscv_vsetvli:
1718 case Intrinsic::riscv_vsetvlimax:
1724 case Intrinsic::vscale: {
1725 if (!II->getParent() || !II->getFunction())
1734 case Instruction::ShuffleVector: {
1735 auto *Shuf = dyn_cast<ShuffleVectorInst>(
I);
1743 APInt DemandedLHS, DemandedRHS;
1750 if (!!DemandedLHS) {
1751 const Value *
LHS = Shuf->getOperand(0);
1757 if (!!DemandedRHS) {
1758 const Value *
RHS = Shuf->getOperand(1);
1764 case Instruction::InsertElement: {
1765 if (isa<ScalableVectorType>(
I->getType())) {
1769 const Value *Vec =
I->getOperand(0);
1770 const Value *Elt =
I->getOperand(1);
1771 auto *CIdx = dyn_cast<ConstantInt>(
I->getOperand(2));
1774 if (!CIdx || CIdx->getValue().uge(NumElts)) {
1780 unsigned EltIdx = CIdx->getZExtValue();
1782 if (DemandedElts[EltIdx]) {
1789 APInt DemandedVecElts = DemandedElts;
1791 if (!!DemandedVecElts) {
1797 case Instruction::ExtractElement: {
1800 const Value *Vec =
I->getOperand(0);
1802 auto *CIdx = dyn_cast<ConstantInt>(
Idx);
1803 if (isa<ScalableVectorType>(Vec->
getType())) {
1808 unsigned NumElts = cast<FixedVectorType>(Vec->
getType())->getNumElements();
1810 if (CIdx && CIdx->getValue().ult(NumElts))
1815 case Instruction::ExtractValue:
1816 if (
IntrinsicInst *II = dyn_cast<IntrinsicInst>(
I->getOperand(0))) {
1820 switch (II->getIntrinsicID()) {
1822 case Intrinsic::uadd_with_overflow:
1823 case Intrinsic::sadd_with_overflow:
1825 II->getArgOperand(1),
false, DemandedElts,
1826 Known, Known2,
Depth, Q);
1828 case Intrinsic::usub_with_overflow:
1829 case Intrinsic::ssub_with_overflow:
1831 II->getArgOperand(1),
false, DemandedElts,
1832 Known, Known2,
Depth, Q);
1834 case Intrinsic::umul_with_overflow:
1835 case Intrinsic::smul_with_overflow:
1837 DemandedElts, Known, Known2,
Depth, Q);
1843 case Instruction::Freeze:
1887 if (!DemandedElts) {
1893 assert(V &&
"No Value?");
1897 Type *Ty = V->getType();
1901 "Not integer or pointer type!");
1903 if (
auto *FVTy = dyn_cast<FixedVectorType>(Ty)) {
1905 FVTy->getNumElements() == DemandedElts.
getBitWidth() &&
1906 "DemandedElt width should equal the fixed vector number of elements");
1909 "DemandedElt width should be 1 for scalars or scalable vectors");
1915 "V and Known should have same BitWidth");
1918 "V and Known should have same BitWidth");
1929 if (isa<ConstantPointerNull>(V) || isa<ConstantAggregateZero>(V)) {
1936 assert(!isa<ScalableVectorType>(V->getType()));
1940 for (
unsigned i = 0, e = CDV->getNumElements(); i != e; ++i) {
1941 if (!DemandedElts[i])
1943 APInt Elt = CDV->getElementAsAPInt(i);
1950 if (
const auto *CV = dyn_cast<ConstantVector>(V)) {
1951 assert(!isa<ScalableVectorType>(V->getType()));
1955 for (
unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
1956 if (!DemandedElts[i])
1959 auto *ElementCI = dyn_cast_or_null<ConstantInt>(Element);
1964 const APInt &Elt = ElementCI->getValue();
1975 if (isa<UndefValue>(V))
1980 assert(!isa<ConstantData>(V) &&
"Unhandled constant data!");
1988 if (
const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
1989 if (!GA->isInterposable())
1994 if (
const Operator *
I = dyn_cast<Operator>(V))
1998 if (isa<PointerType>(V->getType())) {
1999 Align Alignment = V->getPointerAlignment(Q.
DL);
2009 assert((Known.
Zero & Known.
One) == 0 &&
"Bits known to be one AND zero?");
2017 Value *Start =
nullptr, *Step =
nullptr;
2023 if (U.get() == Start) {
2039 case Instruction::Mul:
2044 case Instruction::SDiv:
2050 case Instruction::UDiv:
2056 case Instruction::Shl:
2058 case Instruction::AShr:
2062 case Instruction::LShr:
2097 Value *
X =
nullptr, *
Y =
nullptr;
2104 if (
const ZExtInst *ZI = dyn_cast<ZExtInst>(V))
2143 unsigned BitWidth = V->getType()->getScalarSizeInBits();
2152 if ((~(LHSBits.
Zero & RHSBits.
Zero)).isPowerOf2())
2162 if (
const PHINode *PN = dyn_cast<PHINode>(V)) {
2179 RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator();
2180 return isKnownToBeAPowerOfTwo(U.get(), OrZero, NewDepth, RecQ);
2206 F =
I->getFunction();
2208 if (!
GEP->isInBounds() ||
2213 assert(
GEP->getType()->isPointerTy() &&
"We only support plain pointer GEP");
2224 GTI != GTE; ++GTI) {
2226 if (
StructType *STy = GTI.getStructTypeOrNull()) {
2227 ConstantInt *OpC = cast<ConstantInt>(GTI.getOperand());
2231 if (ElementOffset > 0)
2242 if (
ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand())) {
2266 assert(!isa<Constant>(V) &&
"Called for constant?");
2271 unsigned NumUsesExplored = 0;
2272 for (
const auto *U : V->users()) {
2280 if (
const auto *CB = dyn_cast<CallBase>(U))
2281 if (
auto *CalledFunc = CB->getCalledFunction())
2283 if (CB->getArgOperand(
Arg.getArgNo()) == V &&
2284 Arg.hasNonNullAttr(
false) &&
2292 V->getType()->getPointerAddressSpace()) &&
2305 NonNullIfTrue =
true;
2307 NonNullIfTrue =
false;
2313 for (
const auto *CmpU : U->users()) {
2315 if (Visited.
insert(CmpU).second)
2318 while (!WorkList.
empty()) {
2327 for (
const auto *CurrU : Curr->users())
2328 if (Visited.
insert(CurrU).second)
2333 if (
const BranchInst *BI = dyn_cast<BranchInst>(Curr)) {
2334 assert(BI->isConditional() &&
"uses a comparison!");
2337 BI->getSuccessor(NonNullIfTrue ? 0 : 1);
2341 }
else if (NonNullIfTrue &&
isGuard(Curr) &&
2342 DT->
dominates(cast<Instruction>(Curr), CtxI)) {
2356 const unsigned NumRanges = Ranges->getNumOperands() / 2;
2358 for (
unsigned i = 0; i < NumRanges; ++i) {
2360 mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 0));
2362 mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 1));
2364 if (Range.contains(
Value))
2374 Value *Start =
nullptr, *Step =
nullptr;
2375 const APInt *StartC, *StepC;
2381 case Instruction::Add:
2387 case Instruction::Mul:
2390 case Instruction::Shl:
2392 case Instruction::AShr:
2393 case Instruction::LShr:
2442 if (
auto *
C = dyn_cast<Constant>(
X))
2460 auto ShiftOp = [&](
const APInt &Lhs,
const APInt &Rhs) {
2461 switch (
I->getOpcode()) {
2462 case Instruction::Shl:
2463 return Lhs.
shl(Rhs);
2464 case Instruction::LShr:
2465 return Lhs.
lshr(Rhs);
2466 case Instruction::AShr:
2467 return Lhs.
ashr(Rhs);
2473 auto InvShiftOp = [&](
const APInt &Lhs,
const APInt &Rhs) {
2474 switch (
I->getOpcode()) {
2475 case Instruction::Shl:
2476 return Lhs.
lshr(Rhs);
2477 case Instruction::LShr:
2478 case Instruction::AShr:
2479 return Lhs.
shl(Rhs);
2492 if (MaxShift.
uge(NumBits))
2495 if (!ShiftOp(KnownVal.
One, MaxShift).isZero())
2500 if (InvShiftOp(KnownVal.
Zero, NumBits - MaxShift)
2518 Type *Ty = V->getType();
2521 if (
auto *FVTy = dyn_cast<FixedVectorType>(Ty)) {
2523 FVTy->getNumElements() == DemandedElts.
getBitWidth() &&
2524 "DemandedElt width should equal the fixed vector number of elements");
2527 "DemandedElt width should be 1 for scalars");
2531 if (
auto *
C = dyn_cast<Constant>(V)) {
2532 if (
C->isNullValue())
2534 if (isa<ConstantInt>(
C))
2540 if (
auto *VecTy = dyn_cast<FixedVectorType>(
C->getType())) {
2541 for (
unsigned i = 0, e = VecTy->getNumElements(); i != e; ++i) {
2542 if (!DemandedElts[i])
2544 Constant *Elt =
C->getAggregateElement(i);
2547 if (!isa<UndefValue>(Elt) && !isa<ConstantInt>(Elt))
2556 if (
const GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
2557 if (!GV->isAbsoluteSymbolRef() && !GV->hasExternalWeakLinkage() &&
2558 GV->getType()->getAddressSpace() == 0)
2563 if (!isa<ConstantExpr>(V))
2567 if (
auto *
I = dyn_cast<Instruction>(V)) {
2571 if (
auto *Ty = dyn_cast<IntegerType>(V->getType())) {
2572 const APInt ZeroValue(Ty->getBitWidth(), 0);
2588 if (
PointerType *PtrTy = dyn_cast<PointerType>(V->getType())) {
2595 if (
const Argument *
A = dyn_cast<Argument>(V)) {
2596 if (((
A->hasPassPointeeByValueCopyAttr() &&
2598 A->hasNonNullAttr()))
2603 if (
const LoadInst *LI = dyn_cast<LoadInst>(V))
2607 if (
const auto *Call = dyn_cast<CallBase>(V)) {
2608 if (Call->isReturnNonNull())
2615 if (!isa<Constant>(V) &&
2619 const Operator *
I = dyn_cast<Operator>(V);
2624 switch (
I->getOpcode()) {
2625 case Instruction::GetElementPtr:
2626 if (
I->getType()->isPointerTy())
2629 case Instruction::BitCast: {
2657 Type *FromTy =
I->getOperand(0)->getType();
2662 case Instruction::IntToPtr:
2666 if (!isa<ScalableVectorType>(
I->getType()) &&
2671 case Instruction::PtrToInt:
2674 if (!isa<ScalableVectorType>(
I->getType()) &&
2679 case Instruction::Sub:
2682 case Instruction::Or:
2686 case Instruction::SExt:
2687 case Instruction::ZExt:
2691 case Instruction::Shl: {
2706 case Instruction::LShr:
2707 case Instruction::AShr: {
2722 case Instruction::UDiv:
2723 case Instruction::SDiv:
2726 if (cast<PossiblyExactOperator>(
I)->isExact())
2728 if (
I->getOpcode() == Instruction::UDiv) {
2729 std::optional<bool> XUgeY;
2740 return XUgeY && *XUgeY;
2743 case Instruction::Add: {
2748 auto *BO = cast<OverflowingBinaryOperator>(V);
2756 case Instruction::Mul: {
2785 case Instruction::Select: {
2792 auto SelectArmIsNonZero = [&](
bool IsTrueArm) {
2794 Op = IsTrueArm ?
I->getOperand(1) :
I->getOperand(2);
2807 Pred = ICmpInst::getInversePredicate(Pred);
2812 if (SelectArmIsNonZero(
true) &&
2813 SelectArmIsNonZero(
false))
2817 case Instruction::PHI: {
2818 auto *PN = cast<PHINode>(
I);
2828 RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator();
2829 return isKnownNonZero(U.get(), DemandedElts, NewDepth, RecQ);
2832 case Instruction::ExtractElement:
2833 if (
const auto *EEI = dyn_cast<ExtractElementInst>(V)) {
2834 const Value *Vec = EEI->getVectorOperand();
2835 const Value *
Idx = EEI->getIndexOperand();
2836 auto *CIdx = dyn_cast<ConstantInt>(
Idx);
2837 if (
auto *VecTy = dyn_cast<FixedVectorType>(Vec->
getType())) {
2838 unsigned NumElts = VecTy->getNumElements();
2840 if (CIdx && CIdx->getValue().ult(NumElts))
2846 case Instruction::Freeze:
2850 case Instruction::Call:
2851 if (
auto *II = dyn_cast<IntrinsicInst>(
I)) {
2852 switch (II->getIntrinsicID()) {
2853 case Intrinsic::sshl_sat:
2854 case Intrinsic::ushl_sat:
2855 case Intrinsic::abs:
2856 case Intrinsic::bitreverse:
2857 case Intrinsic::bswap:
2858 case Intrinsic::ctpop:
2860 case Intrinsic::ssub_sat:
2862 II->getArgOperand(0), II->getArgOperand(1));
2863 case Intrinsic::sadd_sat:
2865 II->getArgOperand(0), II->getArgOperand(1),
2867 case Intrinsic::umax:
2868 case Intrinsic::uadd_sat:
2871 case Intrinsic::smin:
2872 case Intrinsic::smax: {
2873 auto KnownOpImpliesNonZero = [&](
const KnownBits &K) {
2874 return II->getIntrinsicID() == Intrinsic::smin
2876 : K.isStrictlyPositive();
2880 if (KnownOpImpliesNonZero(XKnown))
2884 if (KnownOpImpliesNonZero(YKnown))
2891 case Intrinsic::umin:
2894 case Intrinsic::cttz:
2897 case Intrinsic::ctlz:
2900 case Intrinsic::fshr:
2901 case Intrinsic::fshl:
2903 if (II->getArgOperand(0) == II->getArgOperand(1))
2906 case Intrinsic::vscale:
2917 return Known.
One != 0;
2921 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
2922 APInt DemandedElts =
2933static std::optional<std::pair<Value*, Value*>>
2937 return std::nullopt;
2946 case Instruction::Add:
2947 case Instruction::Sub:
2953 case Instruction::Mul: {
2957 auto *OBO1 = cast<OverflowingBinaryOperator>(Op1);
2958 auto *OBO2 = cast<OverflowingBinaryOperator>(Op2);
2959 if ((!OBO1->hasNoUnsignedWrap() || !OBO2->hasNoUnsignedWrap()) &&
2960 (!OBO1->hasNoSignedWrap() || !OBO2->hasNoSignedWrap()))
2966 !cast<ConstantInt>(Op1->
getOperand(1))->isZero())
2970 case Instruction::Shl: {
2973 auto *OBO1 = cast<OverflowingBinaryOperator>(Op1);
2974 auto *OBO2 = cast<OverflowingBinaryOperator>(Op2);
2975 if ((!OBO1->hasNoUnsignedWrap() || !OBO2->hasNoUnsignedWrap()) &&
2976 (!OBO1->hasNoSignedWrap() || !OBO2->hasNoSignedWrap()))
2983 case Instruction::AShr:
2984 case Instruction::LShr: {
2985 auto *PEO1 = cast<PossiblyExactOperator>(Op1);
2986 auto *PEO2 = cast<PossiblyExactOperator>(Op2);
2987 if (!PEO1->isExact() || !PEO2->isExact())
2994 case Instruction::SExt:
2995 case Instruction::ZExt:
2999 case Instruction::PHI: {
3000 const PHINode *PN1 = cast<PHINode>(Op1);
3001 const PHINode *PN2 = cast<PHINode>(Op2);
3007 Value *Start1 =
nullptr, *Step1 =
nullptr;
3009 Value *Start2 =
nullptr, *Step2 =
nullptr;
3016 cast<Operator>(BO2));
3025 if (Values->first != PN1 || Values->second != PN2)
3028 return std::make_pair(Start1, Start2);
3031 return std::nullopt;
3038 if (!BO || BO->
getOpcode() != Instruction::Add)
3040 Value *Op =
nullptr;
3054 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(V2)) {
3057 (OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap()) &&
3067 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(V2)) {
3070 (OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap()) &&
3083 bool UsedFullRecursion =
false;
3085 if (!VisitedBBs.
insert(IncomBB).second)
3089 const APInt *C1, *C2;
3094 if (UsedFullRecursion)
3098 RecQ.
CxtI = IncomBB->getTerminator();
3101 UsedFullRecursion =
true;
3111 if (V1->
getType() != V2->getType())
3121 auto *O1 = dyn_cast<Operator>(V1);
3122 auto *O2 = dyn_cast<Operator>(V2);
3123 if (O1 && O2 && O1->getOpcode() == O2->getOpcode()) {
3127 if (
const PHINode *PN1 = dyn_cast<PHINode>(V1)) {
3128 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;
3705 if (
auto *CFP = dyn_cast<ConstantFP>(V))
3706 return !CFP->getValueAPF().isNegZero();
3711 auto *Op = dyn_cast<Operator>(V);
3720 if (isa<SIToFPInst>(Op) || isa<UIToFPInst>(Op))
3723 if (
auto *Call = dyn_cast<CallInst>(Op)) {
3728 case Intrinsic::sqrt:
3729 case Intrinsic::experimental_constrained_sqrt:
3732 case Intrinsic::canonicalize:
3735 case Intrinsic::fabs:
3738 case Intrinsic::experimental_constrained_sitofp:
3739 case Intrinsic::experimental_constrained_uitofp:
3753 bool SignBitOnly,
unsigned Depth) {
3759 if (
const ConstantFP *CFP = dyn_cast<ConstantFP>(V)) {
3760 return !CFP->getValueAPF().isNegative() ||
3761 (!SignBitOnly && CFP->getValueAPF().isZero());
3765 if (
auto *CV = dyn_cast<Constant>(V)) {
3766 if (
auto *CVFVTy = dyn_cast<FixedVectorType>(CV->getType())) {
3767 unsigned NumElts = CVFVTy->getNumElements();
3768 for (
unsigned i = 0; i != NumElts; ++i) {
3769 auto *CFP = dyn_cast_or_null<ConstantFP>(CV->getAggregateElement(i));
3772 if (CFP->getValueAPF().isNegative() &&
3773 (SignBitOnly || !CFP->getValueAPF().isZero()))
3785 const Operator *
I = dyn_cast<Operator>(V);
3789 switch (
I->getOpcode()) {
3793 case Instruction::UIToFP:
3795 case Instruction::FDiv:
3797 if (
I->getOperand(0) ==
I->getOperand(1) &&
3798 (!SignBitOnly || cast<FPMathOperator>(
I)->hasNoNaNs()))
3803 SignBitOnly,
Depth + 1) &&
3806 case Instruction::FMul:
3808 if (
I->getOperand(0) ==
I->getOperand(1) &&
3809 (!SignBitOnly || cast<FPMathOperator>(
I)->hasNoNaNs()))
3813 case Instruction::FAdd:
3814 case Instruction::FRem:
3816 SignBitOnly,
Depth + 1) &&
3818 SignBitOnly,
Depth + 1);
3819 case Instruction::Select:
3821 SignBitOnly,
Depth + 1) &&
3823 SignBitOnly,
Depth + 1);
3824 case Instruction::FPExt:
3825 case Instruction::FPTrunc:
3828 SignBitOnly,
Depth + 1);
3829 case Instruction::ExtractElement:
3834 SignBitOnly,
Depth + 1);
3835 case Instruction::Call:
3836 const auto *CI = cast<CallInst>(
I);
3841 case Intrinsic::canonicalize:
3842 case Intrinsic::arithmetic_fence:
3843 case Intrinsic::floor:
3844 case Intrinsic::ceil:
3845 case Intrinsic::trunc:
3846 case Intrinsic::rint:
3847 case Intrinsic::nearbyint:
3848 case Intrinsic::round:
3849 case Intrinsic::roundeven:
3850 case Intrinsic::fptrunc_round:
3852 SignBitOnly,
Depth + 1);
3853 case Intrinsic::maxnum: {
3854 Value *V0 =
I->getOperand(0), *V1 =
I->getOperand(1);
3855 auto isPositiveNum = [&](
Value *V) {
3873 return isPositiveNum(V0) || isPositiveNum(V1);
3876 case Intrinsic::maximum:
3878 SignBitOnly,
Depth + 1) ||
3880 SignBitOnly,
Depth + 1);
3881 case Intrinsic::minnum:
3882 case Intrinsic::minimum:
3884 SignBitOnly,
Depth + 1) &&
3886 SignBitOnly,
Depth + 1);
3887 case Intrinsic::exp:
3888 case Intrinsic::exp2:
3889 case Intrinsic::fabs:
3891 case Intrinsic::copysign:
3895 case Intrinsic::sqrt:
3899 return CI->hasNoNaNs() && (CI->hasNoSignedZeros() ||
3902 case Intrinsic::powi:
3922 SignBitOnly,
Depth + 1);
3924 case Intrinsic::fma:
3925 case Intrinsic::fmuladd:
3927 return I->getOperand(0) ==
I->getOperand(1) &&
3928 (!SignBitOnly || cast<FPMathOperator>(
I)->hasNoNaNs()) &&
3930 SignBitOnly,
Depth + 1);
3989 switch (Mode.Input) {
4009 bool LookThroughSrc) {
4012 return {
nullptr,
fcNone};
4014 if (ConstRHS->
isZero()) {
4020 return {
nullptr,
fcNone};
4028 return {
LHS, ~fcZero};
4030 return {
LHS, ~fcNan & ~fcZero};
4034 return {
LHS, ~fcNan};
4057 return {
nullptr,
fcNone};
4107 Mask = ~fcNegInf & ~fcNan;
4111 Mask = ~fcPosInf & ~fcNan;
4121 return {
nullptr,
fcNone};
4135 return {
nullptr,
fcNone};
4147 return {
nullptr,
fcNone};
4176 return {
nullptr,
fcNone};
4179 return {
nullptr,
fcNone};
4201 "Got assumption for the wrong function!");
4202 assert(
I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume &&
4203 "must be an assume intrinsic");
4212 auto [TestedValue, TestedMask] =
4215 if (TestedValue == V)
4216 KnownFromAssume &= TestedMask;
4220 auto [TestedValue, TestedMask] =
4222 if (TestedValue == V)
4223 KnownFromAssume &= TestedMask;
4225 }
else if (
match(
I->getArgOperand(0),
4226 m_Intrinsic<Intrinsic::is_fpclass>(
4228 KnownFromAssume &=
static_cast<FPClassTest>(ClassVal);
4232 return KnownFromAssume;
4242 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
4243 APInt DemandedElts =
4249 const APInt &DemandedElts,
4253 if ((InterestedClasses &
4259 KnownSrc,
Depth + 1, Q);
4276 assert(Known.
isUnknown() &&
"should not be called with known information");
4278 if (!DemandedElts) {
4286 if (
auto *CFP = dyn_cast_or_null<ConstantFP>(V)) {
4288 Known.
SignBit = CFP->isNegative();
4293 auto *VFVTy = dyn_cast<FixedVectorType>(V->getType());
4294 const Constant *CV = dyn_cast<Constant>(V);
4299 unsigned NumElts = VFVTy->getNumElements();
4300 for (
unsigned i = 0; i != NumElts; ++i) {
4306 if (isa<UndefValue>(Elt))
4308 auto *CElt = dyn_cast<ConstantFP>(Elt);
4314 KnownFPClass KnownElt{CElt->getValueAPF().classify(), CElt->isNegative()};
4322 if (
const auto *CB = dyn_cast<CallBase>(V))
4323 KnownNotFromFlags |= CB->getRetNoFPClass();
4324 else if (
const auto *
Arg = dyn_cast<Argument>(V))
4325 KnownNotFromFlags |=
Arg->getNoFPClass();
4327 const Operator *Op = dyn_cast<Operator>(V);
4328 if (
const FPMathOperator *FPOp = dyn_cast_or_null<FPMathOperator>(Op)) {
4329 if (FPOp->hasNoNaNs())
4330 KnownNotFromFlags |=
fcNan;
4331 if (FPOp->hasNoInfs())
4332 KnownNotFromFlags |=
fcInf;
4337 KnownNotFromFlags |= ~AssumedClasses;
4342 InterestedClasses &= ~KnownNotFromFlags;
4355 const unsigned Opc = Op->getOpcode();
4357 case Instruction::FNeg: {
4359 Known,
Depth + 1, Q);
4363 case Instruction::Select: {
4366 Known,
Depth + 1, Q);
4368 Known2,
Depth + 1, Q);
4372 case Instruction::Call: {
4373 if (
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Op)) {
4376 case Intrinsic::fabs: {
4381 InterestedClasses, Known,
Depth + 1, Q);
4387 case Intrinsic::copysign: {
4391 InterestedClasses, Known,
Depth + 1, Q);
4393 InterestedClasses, KnownSign,
Depth + 1, Q);
4397 case Intrinsic::fma:
4398 case Intrinsic::fmuladd: {
4402 if (II->getArgOperand(0) != II->getArgOperand(1))
4411 InterestedClasses, KnownAddend,
Depth + 1, Q);
4418 case Intrinsic::sqrt:
4419 case Intrinsic::experimental_constrained_sqrt: {
4422 if (InterestedClasses &
fcNan)
4426 InterestedSrcs, KnownSrc,
Depth + 1, Q);
4452 case Intrinsic::sin:
4453 case Intrinsic::cos: {
4457 InterestedClasses, KnownSrc,
Depth + 1, Q);