Lines Matching +full:input +full:- +full:depth
1 //===- ValueTracking.cpp - Walk computations to compute properties --------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
12 //===----------------------------------------------------------------------===//
88 static cl::opt<unsigned> DomConditionsMaxUses("dom-conditions-max-uses",
95 if (unsigned BitWidth = Ty->getScalarSizeInBits())
106 if (CxtI && CxtI->getParent())
109 // If the value is really an already-inserted instruction, then use that.
111 if (CxtI && CxtI->getParent())
120 if (CxtI && CxtI->getParent())
123 // If the value is really an already-inserted instruction, then use that.
125 if (CxtI && CxtI->getParent())
129 if (CxtI && CxtI->getParent())
138 if (isa<ScalableVectorType>(Shuf->getType())) {
145 cast<FixedVectorType>(Shuf->getOperand(0)->getType())->getNumElements();
146 return llvm::getShuffleDemandedElts(NumElts, Shuf->getShuffleMask(),
151 KnownBits &Known, unsigned Depth,
154 void llvm::computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
159 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
161 FVTy ? APInt::getAllOnes(FVTy->getNumElements()) : APInt(1, 1);
162 ::computeKnownBits(V, DemandedElts, Known, Depth, Q);
166 const DataLayout &DL, unsigned Depth,
170 V, Known, Depth,
175 unsigned Depth, AssumptionCache *AC,
179 V, Depth, SimplifyQuery(DL, DT, AC, safeCxtI(V, CxtI), UseInstrInfo));
183 const DataLayout &DL, unsigned Depth,
187 V, DemandedElts, Depth,
207 // X op ((X & Y) ^ Y) -- this is the canonical form of the previous pattern
242 assert(LHS->getType() == RHS->getType() &&
244 assert(LHS->getType()->isIntOrIntVectorTy() &&
256 return !I->user_empty() && all_of(I->users(), [](const User *U) {
263 return !I->user_empty() && all_of(I->users(), [](const User *U) {
269 static bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth,
273 bool OrZero, unsigned Depth,
277 V, OrZero, Depth,
282 const SimplifyQuery &Q, unsigned Depth);
285 unsigned Depth) {
286 return computeKnownBits(V, Depth, SQ).isNonNegative();
290 unsigned Depth) {
292 return CI->getValue().isStrictlyPositive();
296 KnownBits Known = computeKnownBits(V, Depth, SQ);
298 (Known.isNonZero() || isKnownNonZero(V, SQ, Depth));
302 unsigned Depth) {
303 return computeKnownBits(V, Depth, SQ).isNegative();
307 const APInt &DemandedElts, unsigned Depth,
314 assert(V1->getType() == V2->getType() &&
315 "Testing equality of non-equal types!");
316 auto *FVTy = dyn_cast<FixedVectorType>(V1->getType());
318 FVTy ? APInt::getAllOnes(FVTy->getNumElements()) : APInt(1, 1);
325 const SimplifyQuery &SQ, unsigned Depth) {
327 computeKnownBits(V, Known, Depth, SQ);
332 unsigned Depth, const SimplifyQuery &Q);
334 static unsigned ComputeNumSignBits(const Value *V, unsigned Depth,
336 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
338 FVTy ? APInt::getAllOnes(FVTy->getNumElements()) : APInt(1, 1);
339 return ComputeNumSignBits(V, DemandedElts, Depth, Q);
343 unsigned Depth, AssumptionCache *AC,
347 V, Depth, SimplifyQuery(DL, DT, AC, safeCxtI(V, CxtI), UseInstrInfo));
351 unsigned Depth, AssumptionCache *AC,
354 unsigned SignBits = ComputeNumSignBits(V, DL, Depth, AC, CxtI, DT);
355 return V->getType()->getScalarSizeInBits() - SignBits + 1;
362 unsigned Depth, const SimplifyQuery &Q) {
363 computeKnownBits(Op1, DemandedElts, KnownOut, Depth + 1, Q);
370 computeKnownBits(Op0, DemandedElts, Known2, Depth + 1, Q);
376 KnownBits &Known2, unsigned Depth,
378 computeKnownBits(Op1, DemandedElts, Known, Depth + 1, Q);
379 computeKnownBits(Op0, DemandedElts, Known2, Depth + 1, Q);
386 // The product of a number with itself is non-negative.
393 // The product of two numbers with the same sign is non-negative.
396 // The product of a negative number and a non-negative number is either
409 isGuaranteedNotToBeUndef(Op0, Q.AC, Q.CxtI, Q.DT, Depth + 1);
412 // Only make use of no-wrap flags if we failed to compute the sign bit
437 ConstantRange Range(Lower->getValue(), Upper->getValue());
456 // non-ephemeral users). See r246696's test case for an example.
457 if (is_contained(I->operands(), E))
466 if (llvm::all_of(V->users(), [&](const User *U) {
473 !cast<Instruction>(V)->mayHaveSideEffects() &&
474 !cast<Instruction>(V)->isTerminator())) {
477 append_range(WorkSet, U->operands());
488 return CI->isAssumeLikeIntrinsic();
505 if (Inv->getParent() == CxtI->getParent()) {
508 if (Inv->comesBefore(CxtI))
511 // Don't let an assume affect itself - this would cause the problems
521 // to avoid a compile-time explosion. This limit is chosen arbitrarily, so
523 auto Range = make_range(CxtI->getIterator(), Inv->getIterator());
532 if (DT->dominates(Inv, CxtI))
534 } else if (Inv->getParent() == CxtI->getParent()->getSinglePredecessor()) {
542 // TODO: cmpExcludesZero misses many cases where `RHS` is non-constant but
543 // we still have enough information about `RHS` to conclude non-zero. For
552 // Special-case v != 0 to also handle v != null.
556 // All other predicates - rely on generic ConstantRange handling.
558 auto Zero = APInt::getZero(RHS->getType()->getScalarSizeInBits());
568 for (unsigned ElemIdx = 0, NElem = VC->getNumElements(); ElemIdx < NElem;
571 Pred, VC->getElementAsAPInt(ElemIdx));
579 // Use of assumptions is context-sensitive. If we don't have a context, we
584 for (AssumptionCache::ResultElem &Elem : Q.AC->assumptionsFor(V)) {
589 assert(I->getFunction() == Q.CxtI->getFunction() &&
593 if (!V->getType()->isPointerTy())
596 *I, I->bundle_op_info_begin()[Elem.Index])) {
600 !NullPointerIsDefined(Q.CxtI->getFunction(),
601 V->getType()->getPointerAddressSpace()))) &&
615 if (!match(I->getArgOperand(0), m_c_ICmp(Pred, m_V, m_Value(RHS))))
628 if (RHS->getType()->isPointerTy()) {
716 // X & Y u> C -> X u> C && Y u> C
717 // X nuw- Y u> C -> X u> C
724 // X | Y u< C -> X u< C && Y u< C
725 // X nuw+ Y u< C -> X u< C && Y u< C
729 (*C - (Pred == ICmpInst::ICMP_ULT)).countLeadingZeros());
741 Invert ? Cmp->getInversePredicate() : Cmp->getPredicate();
742 Value *LHS = Cmp->getOperand(0);
743 Value *RHS = Cmp->getOperand(1);
747 KnownBits DstKnown(LHS->getType()->getScalarSizeInBits());
757 KnownBits &Known, unsigned Depth,
760 if (Depth < MaxAnalysisRecursionDepth &&
764 computeKnownBitsFromCond(V, A, Known2, Depth + 1, SQ, Invert);
765 computeKnownBitsFromCond(V, B, Known3, Depth + 1, SQ, Invert);
779 unsigned Depth, const SimplifyQuery &Q) {
781 if (Q.CC && Q.CC->AffectedValues.contains(V))
782 computeKnownBitsFromCond(V, Q.CC->Cond, Known, Depth, Q, Q.CC->Invert);
789 for (BranchInst *BI : Q.DC->conditionsFor(V)) {
790 BasicBlockEdge Edge0(BI->getParent(), BI->getSuccessor(0));
791 if (Q.DT->dominates(Edge0, Q.CxtI->getParent()))
792 computeKnownBitsFromCond(V, BI->getCondition(), Known, Depth, Q,
795 BasicBlockEdge Edge1(BI->getParent(), BI->getSuccessor(1));
796 if (Q.DT->dominates(Edge1, Q.CxtI->getParent()))
797 computeKnownBitsFromCond(V, BI->getCondition(), Known, Depth, Q,
813 for (AssumptionCache::ResultElem &Elem : Q.AC->assumptionsFor(V)) {
818 assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() &&
822 if (!V->getType()->isPointerTy())
825 *I, I->bundle_op_info_begin()[Elem.Index])) {
838 Value *Arg = I->getArgOperand(0);
855 if (Depth == MaxAnalysisRecursionDepth)
875 /// non-constant shift amount. Known is the output of this function. Known2 is a
876 /// pre-allocated temporary with the same bit width as Known and on return
878 /// operator-specific function that, given the known-bits and a shift amount,
879 /// compute the implied known-bits of the shift operator's result respectively
884 KnownBits &Known2, unsigned Depth, const SimplifyQuery &Q,
886 computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
887 computeKnownBits(I->getOperand(1), DemandedElts, Known, Depth + 1, Q);
888 // To limit compile-time impact, only query isKnownNonZero() if we know at
893 isKnownNonZero(I->getOperand(1), DemandedElts, Q, Depth + 1));
900 unsigned Depth, const SimplifyQuery &Q) {
907 switch (I->getOpcode()) {
911 // and(x, -x) is common idioms that will clear all but lowest set
915 // this pattern. Try to match and(x, and(-x, y)) / and(and(x, y), -x).
917 // -(-x) == x so using whichever (LHS/RHS) gets us a better result.
929 // xor(x, x-1) is common idioms that will clear all but lowest set
932 // TODO: xor(x, x-1) is often rewritting as xor(x, x-C) where C !=
933 // -1 but for the purpose of demanded bits (xor(x, x-C) &
934 // Demanded) == (xor(x, x-1) & Demanded). Extend the xor pattern
935 // to use arbitrary C if xor(x, x-C) as the same as xor(x, x-1).
938 const KnownBits &XBits = I->getOperand(0) == X ? KnownLHS : KnownRHS;
946 // and(x, add (x, -1)) is a common idiom that always clears the low bit;
947 // xor/or(x, add (x, -1)) is an idiom that will always set the low bit.
957 computeKnownBits(Y, DemandedElts, KnownY, Depth + 1, Q);
969 const Operator *I, const APInt &DemandedElts, unsigned Depth,
974 getHorizDemandedEltsForFirstOperand(Q.DL.getTypeSizeInBits(I->getType()),
979 [Depth, &Q, KnownBitsFunc](const Value *Op, APInt &DemandedEltsOp) {
981 computeKnownBits(Op, DemandedEltsOp, Depth + 1, Q),
982 computeKnownBits(Op, DemandedEltsOp << 1, Depth + 1, Q));
986 return ComputeForSingleOpFunc(I->getOperand(0), DemandedEltsLHS);
988 return ComputeForSingleOpFunc(I->getOperand(1), DemandedEltsRHS);
990 return ComputeForSingleOpFunc(I->getOperand(0), DemandedEltsLHS)
991 .intersectWith(ComputeForSingleOpFunc(I->getOperand(1), DemandedEltsRHS));
998 unsigned Depth,
1000 auto *FVTy = dyn_cast<FixedVectorType>(I->getType());
1002 FVTy ? APInt::getAllOnes(FVTy->getNumElements()) : APInt(1, 1);
1004 return getKnownBitsFromAndXorOr(I, DemandedElts, KnownLHS, KnownRHS, Depth,
1009 Attribute Attr = F->getFnAttribute(Attribute::VScaleRange);
1010 // Without vscale_range, we only know that vscale is non-zero.
1028 Value *Arm, bool Invert, unsigned Depth,
1036 computeKnownBitsFromCond(Arm, Cond, CondRes, Depth + 1, Q, Invert);
1053 if (!isGuaranteedNotToBeUndef(Arm, Q.AC, Q.CxtI, Q.DT, Depth + 1))
1063 KnownBits &Known, unsigned Depth,
1068 switch (I->getOpcode()) {
1076 computeKnownBits(I->getOperand(1), DemandedElts, Known, Depth + 1, Q);
1077 computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
1079 Known = getKnownBitsFromAndXorOr(I, DemandedElts, Known2, Known, Depth, Q);
1082 computeKnownBits(I->getOperand(1), DemandedElts, Known, Depth + 1, Q);
1083 computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
1085 Known = getKnownBitsFromAndXorOr(I, DemandedElts, Known2, Known, Depth, Q);
1088 computeKnownBits(I->getOperand(1), DemandedElts, Known, Depth + 1, Q);
1089 computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
1091 Known = getKnownBitsFromAndXorOr(I, DemandedElts, Known2, Known, Depth, Q);
1095 computeKnownBitsMul(I->getOperand(0), I->getOperand(1), NSW, DemandedElts,
1096 Known, Known2, Depth, Q);
1100 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1101 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1107 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1108 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1116 computeKnownBits(Arm, DemandedElts, Res, Depth + 1, Q);
1117 adjustKnownBitsForSelectArm(Res, I->getOperand(0), Arm, Invert, Depth, Q);
1122 ComputeForArm(I->getOperand(1), /*Invert=*/false)
1123 .intersectWith(ComputeForArm(I->getOperand(2), /*Invert=*/true));
1139 Type *SrcTy = I->getOperand(0)->getType();
1144 Type *ScalarTy = SrcTy->getScalarType();
1145 SrcBitWidth = ScalarTy->isPointerTy() ?
1151 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1153 Inst && Inst->hasNonNeg() && !Known.isNegative())
1159 Type *SrcTy = I->getOperand(0)->getType();
1160 if (SrcTy->isIntOrPtrTy() &&
1163 !I->getType()->isVectorTy()) {
1164 computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1171 V->getType()->isFPOrFPVectorTy()) {
1172 Type *FPType = V->getType()->getScalarType();
1174 computeKnownFPClass(V, DemandedElts, fcAllFlags, Depth + 1, Q);
1187 APFloat::getInf(FPType->getFltSemantics()).bitcastToAPInt()));
1191 APInt::getZero(FPType->getScalarSizeInBits())));
1209 if (!SrcVecTy || !SrcVecTy->getElementType()->isIntegerTy() ||
1210 !I->getType()->isIntOrIntVectorTy() ||
1211 isa<ScalableVectorType>(I->getType()))
1215 // Examples: v4i32 -> v2i64, v3i8 -> v24
1216 unsigned SubBitWidth = SrcVecTy->getScalarSizeInBits();
1222 // For this bitcast, each demanded element of the output is sub-divided
1225 // bits for each sub-element sequentially. This is done by shifting the
1226 // one-set-bit demanded elements parameter across the sub-elements for
1230 // The known bits of each sub-element are then inserted into place
1242 computeKnownBits(I->getOperand(0), SubDemandedElts.shl(i), KnownSrc,
1243 Depth + 1, Q);
1244 unsigned ShiftElt = Q.DL.isLittleEndian() ? i : SubScale - 1 - i;
1251 // Compute the bits in the result that are not present in the input.
1252 unsigned SrcBitWidth = I->getOperand(0)->getType()->getScalarSizeInBits();
1255 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1256 // If the sign bit of the input is known set or clear, then we know the
1268 computeKnownBitsFromShiftOperator(I, DemandedElts, Known, Known2, Depth, Q,
1270 // Trailing zeros of a right-shifted constant never decrease.
1272 if (match(I->getOperand(0), m_APInt(C)))
1273 Known.Zero.setLowBits(C->countr_zero());
1282 computeKnownBitsFromShiftOperator(I, DemandedElts, Known, Known2, Depth, Q,
1284 // Leading zeros of a left-shifted constant never decrease.
1286 if (match(I->getOperand(0), m_APInt(C)))
1287 Known.Zero.setHighBits(C->countl_zero());
1296 computeKnownBitsFromShiftOperator(I, DemandedElts, Known, Known2, Depth, Q,
1303 computeKnownBitsAddSub(false, I->getOperand(0), I->getOperand(1), NSW, NUW,
1304 DemandedElts, Known, Known2, Depth, Q);
1310 computeKnownBitsAddSub(true, I->getOperand(0), I->getOperand(1), NSW, NUW,
1311 DemandedElts, Known, Known2, Depth, Q);
1315 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1316 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1321 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1322 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1326 Known.Zero.setLowBits(Log2(cast<AllocaInst>(I)->getAlign()));
1331 computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1337 for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) {
1338 // TrailZ can only become smaller, short-circuit if we hit zero.
1342 Value *Index = I->getOperand(i);
1346 if (CIndex && CIndex->isZeroValue())
1355 if (CIndex->getType()->isVectorTy())
1356 Index = CIndex->getSplatValue();
1358 unsigned Idx = cast<ConstantInt>(Index)->getZExtValue();
1360 uint64_t Offset = SL->getElementOffset(Idx);
1367 if (!IndexedTy->isSized()) {
1372 unsigned IndexBitWidth = Index->getType()->getScalarSizeInBits();
1374 computeKnownBits(Index, IndexBits, Depth + 1, Q);
1397 // to the language reference we need to sign-extend or truncate them
1418 // Handle the case of a simple two-predecessor recurrence PHI.
1421 unsigned Opcode = BO->getOpcode();
1428 BO->getOperand(0) == I) {
1440 computeKnownBits(R, DemandedElts, Known2, Depth + 1, RecQ);
1473 unsigned OpNum = P->getOperand(0) == R ? 0 : 1;
1474 Instruction *RInst = P->getIncomingBlock(OpNum)->getTerminator();
1475 Instruction *LInst = P->getIncomingBlock(1 - OpNum)->getTerminator();
1480 computeKnownBits(R, DemandedElts, Known2, Depth + 1, RecQ);
1485 computeKnownBits(L, DemandedElts, Known3, Depth + 1, RecQ);
1499 // (add non-negative, non-negative) --> non-negative
1500 // (add negative, negative) --> negative
1508 // (sub nsw non-negative, negative) --> non-negative
1509 // (sub nsw negative, non-negative) --> negative
1510 else if (Opcode == Instruction::Sub && BO->getOperand(0) == I) {
1517 // (mul nsw non-negative, non-negative) --> non-negative
1527 // Unreachable blocks may have zero-operand PHI nodes.
1528 if (P->getNumIncomingValues() == 0)
1533 if (Depth < MaxAnalysisRecursionDepth - 1 && Known.isUnknown()) {
1535 if (isa_and_nonnull<UndefValue>(P->hasConstantValue()))
1540 for (unsigned u = 0, e = P->getNumIncomingValues(); u < e; ++u) {
1541 Value *IncValue = P->getIncomingValue(u);
1550 RecQ.CxtI = P->getIncomingBlock(u)->getTerminator();
1559 MaxAnalysisRecursionDepth - 1, RecQ);
1572 if ((TrueSucc == P->getParent()) != (FalseSucc == P->getParent())) {
1574 if (FalseSucc == P->getParent())
1613 if (std::optional<ConstantRange> Range = CB->getRange())
1614 Known = Known.unionWith(Range->toKnownBits());
1616 if (const Value *RV = CB->getReturnedArgOperand()) {
1617 if (RV->getType() == I->getType()) {
1618 computeKnownBits(RV, Known2, Depth + 1, Q);
1620 // If the function doesn't return properly for all input values
1629 switch (II->getIntrinsicID()) {
1633 computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
1634 bool IntMinIsPoison = match(II->getArgOperand(1), m_One());
1639 computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
1644 computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
1649 computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
1652 // If this call is poison for 0 input, the result will be less than 2^n.
1653 if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext()))
1654 PossibleLZ = std::min(PossibleLZ, BitWidth - 1);
1660 computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
1663 // If this call is poison for 0 input, the result will be less than 2^n.
1664 if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext()))
1665 PossibleTZ = std::min(PossibleTZ, BitWidth - 1);
1671 computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
1684 if (!match(I->getOperand(2), m_APInt(SA)))
1688 uint64_t ShiftAmt = SA->urem(BitWidth);
1689 if (II->getIntrinsicID() == Intrinsic::fshr)
1690 ShiftAmt = BitWidth - ShiftAmt;
1693 computeKnownBits(I->getOperand(0), DemandedElts, Known2, Depth + 1, Q);
1694 computeKnownBits(I->getOperand(1), DemandedElts, Known3, Depth + 1, Q);
1697 Known2.Zero.shl(ShiftAmt) | Known3.Zero.lshr(BitWidth - ShiftAmt);
1699 Known2.One.shl(ShiftAmt) | Known3.One.lshr(BitWidth - ShiftAmt);
1703 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1704 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1708 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1709 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1713 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1714 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1718 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1719 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1722 // Vec reverse preserves bits from input vec.
1724 computeKnownBits(I->getOperand(0), DemandedElts.reverseBits(), Known,
1725 Depth + 1, Q);
1728 // input vec is set in the output.
1735 computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1738 computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1742 auto *VecTy = cast<VectorType>(I->getOperand(0)->getType());
1744 bool EvenCnt = VecTy->getElementCount().isKnownEven();
1748 if (VecTy->isScalableTy() || EvenCnt)
1753 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1754 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1758 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1759 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1763 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1764 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1768 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1769 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1773 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1775 const Value *Mask = I->getOperand(1);
1776 Known2 = KnownBits(Mask->getType()->getScalarSizeInBits());
1777 computeKnownBits(Mask, DemandedElts, Known2, Depth + 1, Q);
1778 // TODO: 1-extend would be more precise.
1785 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1786 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1792 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth + 1, Q);
1793 computeKnownBits(I->getOperand(1), DemandedElts, Known2, Depth + 1, Q);
1804 I, DemandedElts, Depth, Q,
1814 Known = computeKnownBitsForHorizontalOperation(I, DemandedElts, Depth,
1823 I, DemandedElts, Depth, Q,
1833 Known = computeKnownBitsForHorizontalOperation(I, DemandedElts, Depth,
1839 bool HasAVL = II->getIntrinsicID() == Intrinsic::riscv_vsetvli;
1840 const ConstantRange Range = getVScaleRange(II->getFunction(), BitWidth);
1842 cast<ConstantInt>(II->getArgOperand(HasAVL))->getZExtValue());
1844 cast<ConstantInt>(II->getArgOperand(1 + HasAVL))->getZExtValue());
1851 if (auto *CI = dyn_cast<ConstantInt>(II->getArgOperand(0)))
1852 MaxVL = std::min(MaxVL, CI->getZExtValue());
1860 if (!II->getParent() || !II->getFunction())
1863 Known = getVScaleRange(II->getFunction(), BitWidth).toKnownBits();
1887 const Value *LHS = Shuf->getOperand(0);
1888 computeKnownBits(LHS, DemandedLHS, Known, Depth + 1, Q);
1894 const Value *RHS = Shuf->getOperand(1);
1895 computeKnownBits(RHS, DemandedRHS, Known2, Depth + 1, Q);
1901 if (isa<ScalableVectorType>(I->getType())) {
1905 const Value *Vec = I->getOperand(0);
1906 const Value *Elt = I->getOperand(1);
1907 auto *CIdx = dyn_cast<ConstantInt>(I->getOperand(2));
1912 if (CIdx && CIdx->getValue().ult(NumElts)) {
1913 DemandedVecElts.clearBit(CIdx->getZExtValue());
1914 NeedsElt = DemandedElts[CIdx->getZExtValue()];
1920 computeKnownBits(Elt, Known, Depth + 1, Q);
1927 computeKnownBits(Vec, DemandedVecElts, Known2, Depth + 1, Q);
1933 // Look through extract element. If the index is non-constant or
1934 // out-of-range demand all elements, otherwise just the extracted element.
1935 const Value *Vec = I->getOperand(0);
1936 const Value *Idx = I->getOperand(1);
1938 if (isa<ScalableVectorType>(Vec->getType())) {
1943 unsigned NumElts = cast<FixedVectorType>(Vec->getType())->getNumElements();
1945 if (CIdx && CIdx->getValue().ult(NumElts))
1946 DemandedVecElts = APInt::getOneBitSet(NumElts, CIdx->getZExtValue());
1947 computeKnownBits(Vec, DemandedVecElts, Known, Depth + 1, Q);
1951 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I->getOperand(0))) {
1953 if (EVI->getNumIndices() != 1) break;
1954 if (EVI->getIndices()[0] == 0) {
1955 switch (II->getIntrinsicID()) {
1960 true, II->getArgOperand(0), II->getArgOperand(1), /*NSW=*/false,
1961 /* NUW=*/false, DemandedElts, Known, Known2, Depth, Q);
1966 false, II->getArgOperand(0), II->getArgOperand(1), /*NSW=*/false,
1967 /* NUW=*/false, DemandedElts, Known, Known2, Depth, Q);
1971 computeKnownBitsMul(II->getArgOperand(0), II->getArgOperand(1), false,
1972 DemandedElts, Known, Known2, Depth, Q);
1979 if (isGuaranteedNotToBePoison(I->getOperand(0), Q.AC, Q.CxtI, Q.DT,
1980 Depth + 1))
1981 computeKnownBits(I->getOperand(0), Known, Depth + 1, Q);
1989 unsigned Depth, const SimplifyQuery &Q) {
1990 KnownBits Known(getBitWidth(V->getType(), Q.DL));
1991 ::computeKnownBits(V, DemandedElts, Known, Depth, Q);
1997 KnownBits llvm::computeKnownBits(const Value *V, unsigned Depth,
1999 KnownBits Known(getBitWidth(V->getType(), Q.DL));
2000 computeKnownBits(V, Known, Depth, Q);
2010 /// optimized based on the contradictory assumption that it is non-zero.
2020 KnownBits &Known, unsigned Depth,
2029 assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
2032 Type *Ty = V->getType();
2035 assert((Ty->isIntOrIntVectorTy(BitWidth) || Ty->isPtrOrPtrVectorTy()) &&
2040 FVTy->getNumElements() == DemandedElts.getBitWidth() &&
2047 Type *ScalarTy = Ty->getScalarType();
2048 if (ScalarTy->isPointerTy()) {
2063 // Null and aggregate-zero are all-zeros.
2071 assert(!isa<ScalableVectorType>(V->getType()));
2075 for (unsigned i = 0, e = CDV->getNumElements(); i != e; ++i) {
2078 APInt Elt = CDV->getElementAsAPInt(i);
2088 assert(!isa<ScalableVectorType>(V->getType()));
2092 for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
2095 Constant *Element = CV->getAggregateElement(i);
2103 const APInt &Elt = ElementCI->getValue();
2124 if (std::optional<ConstantRange> Range = A->getRange())
2125 Known = Range->toKnownBits();
2127 // All recursive calls that increase depth must come after this.
2128 if (Depth == MaxAnalysisRecursionDepth)
2131 // A weak GlobalAlias is totally unknown. A non-weak GlobalAlias has
2134 if (!GA->isInterposable())
2135 computeKnownBits(GA->getAliasee(), Known, Depth + 1, Q);
2140 computeKnownBitsFromOperator(I, DemandedElts, Known, Depth, Q);
2142 if (std::optional<ConstantRange> CR = GV->getAbsoluteSymbolRange())
2143 Known = CR->toKnownBits();
2146 // Aligned pointers have trailing zeros - refine Known.Zero set
2147 if (isa<PointerType>(V->getType())) {
2148 Align Alignment = V->getPointerAlignment(Q.DL);
2156 computeKnownBitsFromContext(V, Known, Depth, Q);
2162 unsigned Depth, SimplifyQuery &Q) {
2169 for (const Use &U : PN->operands()) {
2173 Q.CxtI = PN->getIncomingBlock(U)->getTerminator();
2174 if (!isKnownToBeAPowerOfTwo(Start, OrZero, Depth, Q))
2181 if (BO->getOpcode() != Instruction::Mul && BO->getOperand(1) != Step)
2184 Q.CxtI = BO->getParent()->getTerminator();
2185 switch (BO->getOpcode()) {
2190 isKnownToBeAPowerOfTwo(Step, OrZero, Depth, Q);
2199 // If OrZero is false, cannot guarantee induction variable is non-zero after
2202 isKnownToBeAPowerOfTwo(Step, false, Depth, Q);
2220 bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth,
2222 assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
2228 if (OrZero && V->getType()->getScalarSizeInBits() == 1)
2236 const Function *F = Q.CxtI->getFunction();
2237 // The vscale_range indicates vscale is a power-of-two.
2238 return F->hasFnAttribute(Attribute::VScaleRange);
2252 if (Depth++ == MaxAnalysisRecursionDepth)
2255 switch (I->getOpcode()) {
2257 return isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q);
2259 return OrZero && isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q);
2262 return isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q);
2266 return isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q);
2270 return isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q);
2273 return isKnownToBeAPowerOfTwo(I->getOperand(1), OrZero, Depth, Q) &&
2274 isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q) &&
2275 (OrZero || isKnownNonZero(I, Q, Depth));
2279 (isKnownToBeAPowerOfTwo(I->getOperand(1), /*OrZero*/ true, Depth, Q) ||
2280 isKnownToBeAPowerOfTwo(I->getOperand(0), /*OrZero*/ true, Depth, Q)))
2282 // X & (-X) is always a power of two or zero.
2283 if (match(I->getOperand(0), m_Neg(m_Specific(I->getOperand(1)))) ||
2284 match(I->getOperand(1), m_Neg(m_Specific(I->getOperand(0)))))
2285 return OrZero || isKnownNonZero(I->getOperand(0), Q, Depth);
2288 // Adding a power-of-two or zero to the same power-of-two or zero yields
2289 // either the original power-of-two, a larger power-of-two or zero.
2293 if (match(I->getOperand(0),
2294 m_c_And(m_Specific(I->getOperand(1)), m_Value())) &&
2295 isKnownToBeAPowerOfTwo(I->getOperand(1), OrZero, Depth, Q))
2297 if (match(I->getOperand(1),
2298 m_c_And(m_Specific(I->getOperand(0)), m_Value())) &&
2299 isKnownToBeAPowerOfTwo(I->getOperand(0), OrZero, Depth, Q))
2302 unsigned BitWidth = V->getType()->getScalarSizeInBits();
2304 computeKnownBits(I->getOperand(0), LHSBits, Depth, Q);
2307 computeKnownBits(I->getOperand(1), RHSBits, Depth, Q);
2325 return isKnownToBeAPowerOfTwo(I->getOperand(1), OrZero, Depth, Q) &&
2326 isKnownToBeAPowerOfTwo(I->getOperand(2), OrZero, Depth, Q);
2335 if (isPowerOfTwoRecurrence(PN, OrZero, Depth, RecQ))
2340 unsigned NewDepth = std::max(Depth, MaxAnalysisRecursionDepth - 1);
2341 return llvm::all_of(PN->operands(), [&](const Use &U) {
2348 RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator();
2355 switch (II->getIntrinsicID()) {
2360 return isKnownToBeAPowerOfTwo(II->getArgOperand(1), OrZero, Depth, Q) &&
2361 isKnownToBeAPowerOfTwo(II->getArgOperand(0), OrZero, Depth, Q);
2363 // thus dont change pow2/non-pow2 status.
2366 return isKnownToBeAPowerOfTwo(II->getArgOperand(0), OrZero, Depth, Q);
2370 if (II->getArgOperand(0) == II->getArgOperand(1))
2371 return isKnownToBeAPowerOfTwo(II->getArgOperand(0), OrZero, Depth, Q);
2384 /// Test whether a GEP's result is known to be non-null.
2387 /// to be non-null.
2390 static bool isGEPKnownNonNull(const GEPOperator *GEP, unsigned Depth,
2394 F = I->getFunction();
2398 if (!GEP->hasNoUnsignedWrap() &&
2399 !(GEP->isInBounds() &&
2400 !NullPointerIsDefined(F, GEP->getPointerAddressSpace())))
2403 // FIXME: Support vector-GEPs.
2404 assert(GEP->getType()->isPointerTy() && "We only support plain pointer GEP");
2406 // If the base pointer is non-null, we cannot walk to a null address with an
2408 if (isKnownNonZero(GEP->getPointerOperand(), Q, Depth))
2411 // Walk the GEP operands and see if any operand introduces a non-zero offset.
2416 // Struct types are easy -- they must always be indexed by a constant.
2419 unsigned ElementIdx = OpC->getZExtValue();
2421 uint64_t ElementOffset = SL->getElementOffset(ElementIdx);
2427 // If we have a zero-sized type, the index doesn't matter. Keep looping.
2432 // increment Depth when just zipping down an all-constant GEP.
2434 if (!OpC->isZero())
2439 // We post-increment Depth here because while isKnownNonZero increments it
2443 // of depth.
2444 if (Depth++ >= MaxAnalysisRecursionDepth)
2447 if (isKnownNonZero(GTI.getOperand(), Q, Depth))
2463 for (const auto *U : V->users()) {
2470 // attributes may provide an answer about null-ness.
2472 if (auto *CalledFunc = CB->getCalledFunction())
2473 for (const Argument &Arg : CalledFunc->args())
2474 if (CB->getArgOperand(Arg.getArgNo()) == V &&
2476 DT->dominates(CB, CtxI))
2482 if (!NullPointerIsDefined(I->getFunction(),
2483 V->getType()->getPointerAddressSpace()) &&
2484 DT->dominates(I, CtxI))
2509 for (const auto *CmpU : U->users()) {
2523 for (const auto *CurrU : Curr->users())
2530 assert(BI->isConditional() && "uses a comparison!");
2533 BI->getSuccessor(NonNullIfTrue ? 0 : 1);
2534 BasicBlockEdge Edge(BI->getParent(), NonNullSuccessor);
2535 if (Edge.isSingleEdge() && DT->dominates(Edge, CtxI->getParent()))
2538 DT->dominates(cast<Instruction>(Curr), CtxI)) {
2552 const unsigned NumRanges = Ranges->getNumOperands() / 2;
2556 mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 0));
2558 mdconst::extract<ConstantInt>(Ranges->getOperand(2 * i + 1));
2559 ConstantRange Range(Lower->getValue(), Upper->getValue());
2567 /// non-zero starting value. These are common as induction variables.
2573 !match(Start, m_APInt(StartC)) || StartC->isZero())
2576 switch (BO->getOpcode()) {
2578 // Starting from non-zero and stepping away from zero can never wrap back
2580 return BO->hasNoUnsignedWrap() ||
2581 (BO->hasNoSignedWrap() && match(Step, m_APInt(StepC)) &&
2582 StartC->isNegative() == StepC->isNegative());
2584 return (BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap()) &&
2585 match(Step, m_APInt(StepC)) && !StepC->isZero();
2587 return BO->hasNoUnsignedWrap() || BO->hasNoSignedWrap();
2590 return BO->isExact();
2603 static bool isNonZeroAdd(const APInt &DemandedElts, unsigned Depth,
2611 return isKnownNonZero(Y, DemandedElts, Q, Depth) ||
2612 isKnownNonZero(X, DemandedElts, Q, Depth);
2614 KnownBits XKnown = computeKnownBits(X, DemandedElts, Depth, Q);
2615 KnownBits YKnown = computeKnownBits(Y, DemandedElts, Depth, Q);
2617 // If X and Y are both non-negative (as signed values) then their sum is not
2620 if (isKnownNonZero(Y, DemandedElts, Q, Depth) ||
2621 isKnownNonZero(X, DemandedElts, Q, Depth))
2638 // The sum of a non-negative number and a power of two is not zero.
2640 isKnownToBeAPowerOfTwo(Y, /*OrZero*/ false, Depth, Q))
2643 isKnownToBeAPowerOfTwo(X, /*OrZero*/ false, Depth, Q))
2650 static bool isNonZeroSub(const APInt &DemandedElts, unsigned Depth,
2653 // (X - (X != 0)) is non zero
2654 // ((X != 0) - X) is non zero
2660 if (C->isNullValue() && isKnownNonZero(Y, DemandedElts, Q, Depth))
2663 return ::isKnownNonEqual(X, Y, DemandedElts, Depth, Q);
2666 static bool isNonZeroMul(const APInt &DemandedElts, unsigned Depth,
2669 // If X and Y are non-zero then so is X * Y as long as the multiplication
2672 return isKnownNonZero(X, DemandedElts, Q, Depth) &&
2673 isKnownNonZero(Y, DemandedElts, Q, Depth);
2675 // If either X or Y is odd, then if the other is non-zero the result can't
2677 KnownBits XKnown = computeKnownBits(X, DemandedElts, Depth, Q);
2679 return isKnownNonZero(Y, DemandedElts, Q, Depth);
2681 KnownBits YKnown = computeKnownBits(Y, DemandedElts, Depth, Q);
2683 return XKnown.isNonZero() || isKnownNonZero(X, DemandedElts, Q, Depth);
2686 // non-zero, then X * Y is non-zero. We can find sX and sY by just taking
2687 // the lowest known One of X and Y. If they are non-zero, the result
2688 // must be non-zero. We can check if LSB(X) * LSB(Y) != 0 by doing
2695 unsigned Depth, const SimplifyQuery &Q,
2698 switch (I->getOpcode()) {
2711 switch (I->getOpcode()) {
2726 computeKnownBits(I->getOperand(1), DemandedElts, Depth, Q);
2736 // non-zero then at least one non-zero bit must remain.
2737 if (InvShiftOp(KnownVal.Zero, NumBits - MaxShift)
2738 .eq(InvShiftOp(APInt::getAllOnes(NumBits), NumBits - MaxShift)) &&
2739 isKnownNonZero(I->getOperand(0), DemandedElts, Q, Depth))
2747 unsigned Depth, const SimplifyQuery &Q) {
2748 unsigned BitWidth = getBitWidth(I->getType()->getScalarType(), Q.DL);
2749 switch (I->getOpcode()) {
2752 return I->getType()->getPointerAddressSpace() == 0;
2754 if (I->getType()->isPointerTy())
2755 return isGEPKnownNonNull(cast<GEPOperator>(I), Depth, Q);
2765 // %NonZero can have 2 non-zero i16 elements, but isKnownNonZero on a
2766 // <4 x i8> requires that all 4 i8 elements be non-zero which isn't
2781 // This is always safe as non-zero in the 4 i8 elements implies
2782 // non-zero in the combination of any two adjacent ones. Since i8 is a
2784 // This all implies the 2 i16 elements are non-zero.
2785 Type *FromTy = I->getOperand(0)->getType();
2786 if ((FromTy->isIntOrIntVectorTy() || FromTy->isPtrOrPtrVectorTy()) &&
2787 (BitWidth % getBitWidth(FromTy->getScalarType(), Q.DL)) == 0)
2788 return isKnownNonZero(I->getOperand(0), Q, Depth);
2794 if (!isa<ScalableVectorType>(I->getType()) &&
2795 Q.DL.getTypeSizeInBits(I->getOperand(0)->getType()).getFixedValue() <=
2796 Q.DL.getTypeSizeInBits(I->getType()).getFixedValue())
2797 return isKnownNonZero(I->getOperand(0), DemandedElts, Q, Depth);
2801 // is a no-op or an extend and not a truncate.
2802 if (!isa<ScalableVectorType>(I->getType()) &&
2803 Q.DL.getTypeSizeInBits(I->getOperand(0)->getType()).getFixedValue() <=
2804 Q.DL.getTypeSizeInBits(I->getType()).getFixedValue())
2805 return isKnownNonZero(I->getOperand(0), DemandedElts, Q, Depth);
2808 // nuw/nsw trunc preserves zero/non-zero status of input.
2810 if (TI->hasNoSignedWrap() || TI->hasNoUnsignedWrap())
2811 return isKnownNonZero(TI->getOperand(0), DemandedElts, Q, Depth);
2815 return isNonZeroSub(DemandedElts, Depth, Q, BitWidth, I->getOperand(0),
2816 I->getOperand(1));
2819 if (matchOpWithOpEqZero(I->getOperand(0), I->getOperand(1)))
2824 if (matchOpWithOpEqZero(I->getOperand(0), I->getOperand(1)))
2827 return isKnownNonZero(I->getOperand(1), DemandedElts, Q, Depth) ||
2828 isKnownNonZero(I->getOperand(0), DemandedElts, Q, Depth);
2832 return isKnownNonZero(I->getOperand(0), DemandedElts, Q, Depth);
2835 // shl nsw/nuw can't remove any non-zero bits.
2838 return isKnownNonZero(I->getOperand(0), DemandedElts, Q, Depth);
2843 computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth, Q);
2847 return isNonZeroShift(I, DemandedElts, Depth, Q, Known);
2853 if (BO->isExact())
2854 return isKnownNonZero(I->getOperand(0), DemandedElts, Q, Depth);
2859 computeKnownBits(I->getOperand(0), DemandedElts, Depth, Q);
2863 return isNonZeroShift(I, DemandedElts, Depth, Q, Known);
2869 if (cast<PossiblyExactOperator>(I)->isExact())
2870 return isKnownNonZero(I->getOperand(0), DemandedElts, Q, Depth);
2873 computeKnownBits(I->getOperand(0), DemandedElts, Depth, Q);
2880 computeKnownBits(I->getOperand(1), DemandedElts, Depth, Q);
2881 if (I->getOpcode() == Instruction::SDiv) {
2888 // If X is total unknown or X u< Y we won't be able to prove non-zero
2895 // If Add has nuw wrap flag, then if either X or Y is non-zero the result is
2896 // non-zero.
2898 return isNonZeroAdd(DemandedElts, Depth, Q, BitWidth, I->getOperand(0),
2899 I->getOperand(1), Q.IIQ.hasNoSignedWrap(BO),
2904 return isNonZeroMul(DemandedElts, Depth, Q, BitWidth, I->getOperand(0),
2905 I->getOperand(1), Q.IIQ.hasNoSignedWrap(BO),
2911 // First check if the arm is non-zero using `isKnownNonZero`. If that fails,
2912 // then see if the select condition implies the arm is non-zero. For example
2913 // (X != 0 ? X : Y), we know the true arm is non-zero as the `X` "return" is
2917 Op = IsTrueArm ? I->getOperand(1) : I->getOperand(2);
2918 // Op is trivially non-zero.
2919 if (isKnownNonZero(Op, DemandedElts, Q, Depth))
2923 // condition implies that a given arm is non-zero.
2926 if (!match(I->getOperand(0), m_c_ICmp(Pred, m_Specific(Op), m_Value(X))))
2945 // Check if all incoming values are non-zero using recursion.
2947 unsigned NewDepth = std::max(Depth, MaxAnalysisRecursionDepth - 1);
2948 return llvm::all_of(PN->operands(), [&](const Use &U) {
2951 RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator();
2960 if ((TrueSucc == PN->getParent()) != (FalseSucc == PN->getParent())) {
2962 if (FalseSucc == PN->getParent())
2973 if (isa<ScalableVectorType>(I->getType()))
2976 const Value *Vec = I->getOperand(0);
2977 const Value *Elt = I->getOperand(1);
2978 auto *CIdx = dyn_cast<ConstantInt>(I->getOperand(2));
2984 if (CIdx && CIdx->getValue().ult(NumElts)) {
2985 DemandedVecElts.clearBit(CIdx->getZExtValue());
2986 SkipElt = !DemandedElts[CIdx->getZExtValue()];
2989 // Result is zero if Elt is non-zero and rest of the demanded elts in Vec
2990 // are non-zero.
2991 return (SkipElt || isKnownNonZero(Elt, Q, Depth)) &&
2993 isKnownNonZero(Vec, DemandedVecElts, Q, Depth));
2997 const Value *Vec = EEI->getVectorOperand();
2998 const Value *Idx = EEI->getIndexOperand();
3000 if (auto *VecTy = dyn_cast<FixedVectorType>(Vec->getType())) {
3001 unsigned NumElts = VecTy->getNumElements();
3003 if (CIdx && CIdx->getValue().ult(NumElts))
3004 DemandedVecElts = APInt::getOneBitSet(NumElts, CIdx->getZExtValue());
3005 return isKnownNonZero(Vec, DemandedVecElts, Q, Depth);
3018 // If demanded elements for both vecs are non-zero, the shuffle is non-zero.
3020 isKnownNonZero(Shuf->getOperand(1), DemandedRHS, Q, Depth)) &&
3022 isKnownNonZero(Shuf->getOperand(0), DemandedLHS, Q, Depth));
3025 return isKnownNonZero(I->getOperand(0), Q, Depth) &&
3026 isGuaranteedNotToBePoison(I->getOperand(0), Q.AC, Q.CxtI, Q.DT,
3027 Depth);
3032 if (auto *PtrT = dyn_cast<PointerType>(I->getType())) {
3035 !NullPointerIsDefined(LI->getFunction(), PtrT->getAddressSpace())))
3048 switch (WO->getBinaryOp()) {
3052 return isNonZeroAdd(DemandedElts, Depth, Q, BitWidth,
3053 WO->getArgOperand(0), WO->getArgOperand(1),
3057 return isNonZeroSub(DemandedElts, Depth, Q, BitWidth,
3058 WO->getArgOperand(0), WO->getArgOperand(1));
3060 return isNonZeroMul(DemandedElts, Depth, Q, BitWidth,
3061 WO->getArgOperand(0), WO->getArgOperand(1),
3071 if (I->getType()->isPointerTy()) {
3072 if (Call->isReturnNonNull())
3075 return isKnownNonZero(RP, Q, Depth);
3079 if (std::optional<ConstantRange> Range = Call->getRange()) {
3080 const APInt ZeroValue(Range->getBitWidth(), 0);
3081 if (!Range->contains(ZeroValue))
3084 if (const Value *RV = Call->getReturnedArgOperand())
3085 if (RV->getType() == I->getType() && isKnownNonZero(RV, Q, Depth))
3090 switch (II->getIntrinsicID()) {
3097 return isKnownNonZero(II->getArgOperand(0), DemandedElts, Q, Depth);
3099 // non-zero, we will fold it to `sub nuw` in InstCombine.
3101 return isNonZeroSub(DemandedElts, Depth, Q, BitWidth,
3102 II->getArgOperand(0), II->getArgOperand(1));
3104 return isNonZeroAdd(DemandedElts, Depth, Q, BitWidth,
3105 II->getArgOperand(0), II->getArgOperand(1),
3107 // Vec reverse preserves zero/non-zero status from input vec.
3109 return isKnownNonZero(II->getArgOperand(0), DemandedElts.reverseBits(),
3110 Q, Depth);
3111 // umin/smin/smax/smin/or of all non-zero elements is always non-zero.
3117 return isKnownNonZero(II->getArgOperand(0), Q, Depth);
3122 if (matchOpWithOpEqZero(II->getArgOperand(0), II->getArgOperand(1)))
3125 return isKnownNonZero(II->getArgOperand(1), DemandedElts, Q, Depth) ||
3126 isKnownNonZero(II->getArgOperand(0), DemandedElts, Q, Depth);
3128 // If either arg is strictly positive the result is non-zero. Otherwise
3129 // the result is non-zero if both ops are non-zero.
3134 isKnownNonZero(Op, DemandedElts, Q, Depth);
3137 // Avoid re-computing isKnownNonZero.
3140 computeKnownBits(II->getArgOperand(1), DemandedElts, Depth, Q);
3142 IsNonZero(II->getArgOperand(1), Op1NonZero, Op1Known))
3145 computeKnownBits(II->getArgOperand(0), DemandedElts, Depth, Q);
3147 IsNonZero(II->getArgOperand(0), Op0NonZero, Op0Known))
3149 return IsNonZero(II->getArgOperand(1), Op1NonZero, Op1Known) &&
3150 IsNonZero(II->getArgOperand(0), Op0NonZero, Op0Known);
3153 // If either arg is negative the result is non-zero. Otherwise
3154 // the result is non-zero if both ops are non-zero.
3156 computeKnownBits(II->getArgOperand(1), DemandedElts, Depth, Q);
3160 computeKnownBits(II->getArgOperand(0), DemandedElts, Depth, Q);
3169 return isKnownNonZero(II->getArgOperand(0), DemandedElts, Q, Depth) &&
3170 isKnownNonZero(II->getArgOperand(1), DemandedElts, Q, Depth);
3172 return computeKnownBits(II->getArgOperand(0), DemandedElts, Depth, Q)
3175 return computeKnownBits(II->getArgOperand(0), DemandedElts, Depth, Q)
3180 if (II->getArgOperand(0) == II->getArgOperand(1))
3181 return isKnownNonZero(II->getArgOperand(0), DemandedElts, Q, Depth);
3186 return isKnownNonZero(I->getOperand(0), Q, Depth);
3198 computeKnownBits(I, DemandedElts, Known, Depth, Q);
3202 /// Return true if the given value is known to be non-zero when defined. For
3203 /// vectors, return true if every demanded element is known to be non-zero when
3205 /// specified, perform context-sensitive analysis and return true if the
3209 const SimplifyQuery &Q, unsigned Depth) {
3210 Type *Ty = V->getType();
3213 assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
3217 FVTy->getNumElements() == DemandedElts.getBitWidth() &&
3226 if (C->isNullValue())
3229 // Must be non-zero due to null test above.
3233 // non-zero to determine that the whole vector is known non-zero.
3235 for (unsigned i = 0, e = VecTy->getNumElements(); i != e; ++i) {
3238 Constant *Elt = C->getAggregateElement(i);
3239 if (!Elt || Elt->isNullValue())
3249 return isKnownNonZero(CPA->getPointer(), DemandedElts, Q, Depth);
3255 if (!GV->isAbsoluteSymbolRef() && !GV->hasExternalWeakLinkage() &&
3256 GV->getType()->getAddressSpace() == 0)
3266 if (std::optional<ConstantRange> Range = A->getRange()) {
3267 const APInt ZeroValue(Range->getBitWidth(), 0);
3268 if (!Range->contains(ZeroValue))
3276 if (Depth++ >= MaxAnalysisRecursionDepth)
3282 // A byval, inalloca may not be null in a non-default addres space. A
3285 if (((A->hasPassPointeeByValueCopyAttr() &&
3286 !NullPointerIsDefined(A->getParent(), PtrTy->getAddressSpace())) ||
3287 A->hasNonNullAttr()))
3293 if (isKnownNonZeroFromOperator(I, DemandedElts, Depth, Q))
3304 unsigned Depth) {
3305 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
3307 FVTy ? APInt::getAllOnes(FVTy->getNumElements()) : APInt(1, 1);
3308 return ::isKnownNonZero(V, DemandedElts, Q, Depth);
3312 /// the operands of the function corresponding to each input. Otherwise,
3313 /// return std::nullopt. An invertible function is one that is 1-to-1 and maps
3314 /// every input value to exactly one output value. This is equivalent to
3320 if (Op1->getOpcode() != Op2->getOpcode())
3323 auto getOperands = [&](unsigned OpNum) -> auto {
3324 return std::make_pair(Op1->getOperand(OpNum), Op2->getOperand(OpNum));
3327 switch (Op1->getOpcode()) {
3331 if (!cast<PossiblyDisjointInst>(Op1)->isDisjoint() ||
3332 !cast<PossiblyDisjointInst>(Op2)->isDisjoint())
3338 if (match(Op2, m_c_BinOp(m_Specific(Op1->getOperand(0)), m_Value(Other))))
3339 return std::make_pair(Op1->getOperand(1), Other);
3340 if (match(Op2, m_c_BinOp(m_Specific(Op1->getOperand(1)), m_Value(Other))))
3341 return std::make_pair(Op1->getOperand(0), Other);
3345 if (Op1->getOperand(0) == Op2->getOperand(0))
3347 if (Op1->getOperand(1) == Op2->getOperand(1))
3352 // and N is the bitwdith. The nsw case is non-obvious, but proven by
3356 if ((!OBO1->hasNoUnsignedWrap() || !OBO2->hasNoUnsignedWrap()) &&
3357 (!OBO1->hasNoSignedWrap() || !OBO2->hasNoSignedWrap()))
3361 if (Op1->getOperand(1) == Op2->getOperand(1) &&
3362 isa<ConstantInt>(Op1->getOperand(1)) &&
3363 !cast<ConstantInt>(Op1->getOperand(1))->isZero())
3369 // for a non-zero multiply. Shifts always multiply by non-zero.
3372 if ((!OBO1->hasNoUnsignedWrap() || !OBO2->hasNoUnsignedWrap()) &&
3373 (!OBO1->hasNoSignedWrap() || !OBO2->hasNoSignedWrap()))
3376 if (Op1->getOperand(1) == Op2->getOperand(1))
3384 if (!PEO1->isExact() || !PEO2->isExact())
3387 if (Op1->getOperand(1) == Op2->getOperand(1))
3393 if (Op1->getOperand(0)->getType() == Op2->getOperand(0)->getType())
3407 if (PN1->getParent() != PN2->getParent() ||
3418 // * X_i = X_(i-1) OP Y_(i-1), and Y_i = X_(i-1) OP V
3419 // * X_i = Y_i = X_(i-1) OP Y_(i-1)
3422 if (Values->first != PN1 || Values->second != PN2)
3431 /// Return true if V1 == (binop V2, X), where X is known non-zero.
3432 /// Only handle a small subset of binops where (binop V2, X) with non-zero X
3435 const APInt &DemandedElts, unsigned Depth,
3440 switch (BO->getOpcode()) {
3444 if (!cast<PossiblyDisjointInst>(V1)->isDisjoint())
3450 if (V2 == BO->getOperand(0))
3451 Op = BO->getOperand(1);
3452 else if (V2 == BO->getOperand(1))
3453 Op = BO->getOperand(0);
3456 return isKnownNonZero(Op, DemandedElts, Q, Depth + 1);
3461 /// Return true if V2 == V1 * C, where V1 is known non-zero, C is not 0/1 and
3464 const APInt &DemandedElts, unsigned Depth,
3469 (OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap()) &&
3470 !C->isZero() && !C->isOne() &&
3471 isKnownNonZero(V1, DemandedElts, Q, Depth + 1);
3476 /// Return true if V2 == V1 << C, where V1 is known non-zero, C is not 0 and
3479 const APInt &DemandedElts, unsigned Depth,
3484 (OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap()) &&
3485 !C->isZero() && isKnownNonZero(V1, DemandedElts, Q, Depth + 1);
3491 const APInt &DemandedElts, unsigned Depth,
3494 if (PN1->getParent() != PN2->getParent())
3499 for (const BasicBlock *IncomBB : PN1->blocks()) {
3502 const Value *IV1 = PN1->getIncomingValueForBlock(IncomBB);
3503 const Value *IV2 = PN2->getIncomingValueForBlock(IncomBB);
3513 RecQ.CxtI = IncomBB->getTerminator();
3514 if (!isKnownNonEqual(IV1, IV2, DemandedElts, Depth + 1, RecQ))
3522 const APInt &DemandedElts, unsigned Depth,
3529 const Value *Cond1 = SI1->getCondition();
3530 const Value *Cond2 = SI2->getCondition();
3532 return isKnownNonEqual(SI1->getTrueValue(), SI2->getTrueValue(),
3533 DemandedElts, Depth + 1, Q) &&
3534 isKnownNonEqual(SI1->getFalseValue(), SI2->getFalseValue(),
3535 DemandedElts, Depth + 1, Q);
3537 return isKnownNonEqual(SI1->getTrueValue(), V2, DemandedElts, Depth + 1, Q) &&
3538 isKnownNonEqual(SI1->getFalseValue(), V2, DemandedElts, Depth + 1, Q);
3548 if (!A->getType()->isPointerTy() || !B->getType()->isPointerTy())
3552 if (!GEPA || GEPA->getNumIndices() != 1 || !isa<Constant>(GEPA->idx_begin()))
3556 auto *PN = dyn_cast<PHINode>(GEPA->getPointerOperand());
3557 if (!PN || PN->getNumIncomingValues() != 2)
3564 if (PN->getIncomingValue(0) == Step)
3565 Start = PN->getIncomingValue(1);
3566 else if (PN->getIncomingValue(1) == Step)
3567 Start = PN->getIncomingValue(0);
3574 // Is non-equal if above are true.
3577 unsigned IndexWidth = Q.DL.getIndexTypeSizeInBits(Start->getType());
3579 Start = Start->stripAndAccumulateInBoundsConstantOffsets(Q.DL, StartOffset);
3581 Step = Step->stripAndAccumulateInBoundsConstantOffsets(Q.DL, StepOffset);
3587 B = B->stripAndAccumulateInBoundsConstantOffsets(Q.DL, OffsetB);
3595 const APInt &DemandedElts, unsigned Depth,
3599 if (V1->getType() != V2->getType())
3603 if (Depth >= MaxAnalysisRecursionDepth)
3607 // requires our operation be 1-to-1 and map every input value to exactly
3611 if (O1 && O2 && O1->getOpcode() == O2->getOpcode()) {
3613 return isKnownNonEqual(Values->first, Values->second, DemandedElts,
3614 Depth + 1, Q);
3620 if (isNonEqualPHIs(PN1, PN2, DemandedElts, Depth, Q))
3625 if (isModifyingBinopOfNonZero(V1, V2, DemandedElts, Depth, Q) ||
3626 isModifyingBinopOfNonZero(V2, V1, DemandedElts, Depth, Q))
3629 if (isNonEqualMul(V1, V2, DemandedElts, Depth, Q) ||
3630 isNonEqualMul(V2, V1, DemandedElts, Depth, Q))
3633 if (isNonEqualShl(V1, V2, DemandedElts, Depth, Q) ||
3634 isNonEqualShl(V2, V1, DemandedElts, Depth, Q))
3637 if (V1->getType()->isIntOrIntVectorTy()) {
3640 KnownBits Known1 = computeKnownBits(V1, DemandedElts, Depth, Q);
3642 KnownBits Known2 = computeKnownBits(V2, DemandedElts, Depth, Q);
3649 if (isNonEqualSelect(V1, V2, DemandedElts, Depth, Q) ||
3650 isNonEqualSelect(V2, V1, DemandedElts, Depth, Q))
3662 return isKnownNonEqual(A, B, DemandedElts, Depth + 1, Q);
3668 // Returns the input and lower/upper bounds.
3672 cast<Operator>(Select)->getOpcode() == Instruction::Select &&
3673 "Input should be a Select!");
3695 return CLow->sle(*CHigh);
3701 assert((II->getIntrinsicID() == Intrinsic::smin ||
3702 II->getIntrinsicID() == Intrinsic::smax) && "Must be smin/smax");
3704 Intrinsic::ID InverseID = getInverseMinMaxIntrinsic(II->getIntrinsicID());
3705 auto *InnerII = dyn_cast<IntrinsicInst>(II->getArgOperand(0));
3706 if (!InnerII || InnerII->getIntrinsicID() != InverseID ||
3707 !match(II->getArgOperand(1), m_APInt(CLow)) ||
3708 !match(InnerII->getArgOperand(1), m_APInt(CHigh)))
3711 if (II->getIntrinsicID() == Intrinsic::smin)
3713 return CLow->sle(*CHigh);
3724 if (!CV || !isa<FixedVectorType>(CV->getType()))
3728 unsigned NumElts = cast<FixedVectorType>(CV->getType())->getNumElements();
3732 // If we find a non-ConstantInt, bail out.
3733 auto *Elt = dyn_cast_or_null<ConstantInt>(CV->getAggregateElement(i));
3737 MinSignBits = std::min(MinSignBits, Elt->getValue().getNumSignBits());
3745 unsigned Depth, const SimplifyQuery &Q);
3748 unsigned Depth, const SimplifyQuery &Q) {
3749 unsigned Result = ComputeNumSignBitsImpl(V, DemandedElts, Depth, Q);
3763 unsigned Depth, const SimplifyQuery &Q) {
3764 Type *Ty = V->getType();
3766 assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
3770 FVTy->getNumElements() == DemandedElts.getBitWidth() &&
3780 // same behavior for poison though -- that's a FIXME today.
3782 Type *ScalarTy = Ty->getScalarType();
3783 unsigned TyBits = ScalarTy->isPointerTy() ?
3793 if (Depth == MaxAnalysisRecursionDepth)
3800 Tmp = TyBits - U->getOperand(0)->getType()->getScalarSizeInBits();
3801 return ComputeNumSignBits(U->getOperand(0), DemandedElts, Depth + 1, Q) +
3806 // sdiv X, C -> adds log(C) sign bits.
3807 if (match(U->getOperand(1), m_APInt(Denominator))) {
3809 // Ignore non-positive denominator.
3810 if (!Denominator->isStrictlyPositive())
3815 ComputeNumSignBits(U->getOperand(0), DemandedElts, Depth + 1, Q);
3818 return std::min(TyBits, NumBits + Denominator->logBase2());
3824 Tmp = ComputeNumSignBits(U->getOperand(0), DemandedElts, Depth + 1, Q);
3827 // srem X, C -> we know that the result is within [-C+1,C) when C is a
3830 if (match(U->getOperand(1), m_APInt(Denominator))) {
3832 // Ignore non-positive denominator.
3833 if (Denominator->isStrictlyPositive()) {
3841 // 2. The numerator is negative. Then the result range is (-C,0] and
3842 // integers in (-C,0] are either 0 or >u (-1 << ceilLogBase2(C)).
3844 // Thus a lower bound on the number of sign bits is `TyBits -
3847 unsigned ResBits = TyBits - Denominator->ceilLogBase2();
3855 Tmp = ComputeNumSignBits(U->getOperand(0), DemandedElts, Depth + 1, Q);
3856 // ashr X, C -> adds C sign bits. Vectors too.
3858 if (match(U->getOperand(1), m_APInt(ShAmt))) {
3859 if (ShAmt->uge(TyBits))
3861 unsigned ShAmtLimited = ShAmt->getZExtValue();
3870 if (match(U->getOperand(1), m_APInt(ShAmt))) {
3872 if (ShAmt->uge(TyBits))
3876 if (match(U->getOperand(0), m_ZExt(m_Value(X))) &&
3877 ShAmt->uge(TyBits - X->getType()->getScalarSizeInBits())) {
3878 Tmp = ComputeNumSignBits(X, DemandedElts, Depth + 1, Q);
3879 Tmp += TyBits - X->getType()->getScalarSizeInBits();
3882 ComputeNumSignBits(U->getOperand(0), DemandedElts, Depth + 1, Q);
3883 if (ShAmt->uge(Tmp))
3885 Tmp2 = ShAmt->getZExtValue();
3886 return Tmp - Tmp2;
3894 Tmp = ComputeNumSignBits(U->getOperand(0), DemandedElts, Depth + 1, Q);
3896 Tmp2 = ComputeNumSignBits(U->getOperand(1), DemandedElts, Depth + 1, Q);
3910 return std::min(CLow->getNumSignBits(), CHigh->getNumSignBits());
3912 Tmp = ComputeNumSignBits(U->getOperand(1), DemandedElts, Depth + 1, Q);
3915 Tmp2 = ComputeNumSignBits(U->getOperand(2), DemandedElts, Depth + 1, Q);
3922 Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
3925 // Special case decrementing a value (ADD X, -1):
3926 if (const auto *CRHS = dyn_cast<Constant>(U->getOperand(1)))
3927 if (CRHS->isAllOnesValue()) {
3929 computeKnownBits(U->getOperand(0), DemandedElts, Known, Depth + 1, Q);
3931 // If the input is known to be 0 or 1, the output is 0/-1, which is
3942 Tmp2 = ComputeNumSignBits(U->getOperand(1), DemandedElts, Depth + 1, Q);
3945 return std::min(Tmp, Tmp2) - 1;
3948 Tmp2 = ComputeNumSignBits(U->getOperand(1), DemandedElts, Depth + 1, Q);
3953 if (const auto *CLHS = dyn_cast<Constant>(U->getOperand(0)))
3954 if (CLHS->isNullValue()) {
3956 computeKnownBits(U->getOperand(1), DemandedElts, Known, Depth + 1, Q);
3957 // If the input is known to be 0 or 1, the output is 0/-1, which is
3962 // If the input is known to be positive (the sign bit is known clear),
3964 // input.
3973 Tmp = ComputeNumSignBits(U->getOperand(0), DemandedElts, Depth + 1, Q);
3976 return std::min(Tmp, Tmp2) - 1;
3982 ComputeNumSignBits(U->getOperand(0), DemandedElts, Depth + 1, Q);
3986 ComputeNumSignBits(U->getOperand(1), DemandedElts, Depth + 1, Q);
3990 (TyBits - SignBitsOp0 + 1) + (TyBits - SignBitsOp1 + 1);
3991 return OutValidBits > TyBits ? 1 : TyBits - OutValidBits + 1;
3996 unsigned NumIncomingValues = PN->getNumIncomingValues();
3997 // Don't analyze large in-degree PHIs.
3999 // Unreachable blocks may have zero-operand PHI nodes.
4003 // because of our depth threshold.
4008 RecQ.CxtI = PN->getIncomingBlock(i)->getTerminator();
4009 Tmp = std::min(Tmp, ComputeNumSignBits(PN->getIncomingValue(i),
4010 DemandedElts, Depth + 1, RecQ));
4016 // If the input contained enough sign bits that some remain after the
4019 Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
4020 unsigned OperandTyBits = U->getOperand(0)->getType()->getScalarSizeInBits();
4021 if (Tmp > (OperandTyBits - TyBits))
4022 return Tmp - (OperandTyBits - TyBits);
4032 return ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
4049 const Value *LHS = Shuf->getOperand(0);
4050 Tmp = ComputeNumSignBits(LHS, DemandedLHS, Depth + 1, Q);
4053 // fall-back.
4057 const Value *RHS = Shuf->getOperand(1);
4058 Tmp2 = ComputeNumSignBits(RHS, DemandedRHS, Depth + 1, Q);
4062 // fall-back.
4070 switch (II->getIntrinsicID()) {
4075 ComputeNumSignBits(U->getOperand(0), DemandedElts, Depth + 1, Q);
4080 return Tmp - 1;
4085 return std::min(CLow->getNumSignBits(), CHigh->getNumSignBits());
4103 computeKnownBits(V, DemandedElts, Known, Depth, Q);
4106 // identical bits in the top of the input value.
4116 if (F->isIntrinsic())
4117 return F->getIntrinsicID();
4123 if (F->hasLocalLinkage() || !TLI || !TLI->getLibFunc(CB, Func) ||
4219 /// Return true if it's possible to assume IEEE treatment of input denormals in
4222 Ty = Ty->getScalarType();
4223 return F.getDenormalMode(Ty->getFltSemantics()).Input == DenormalMode::IEEE;
4227 Ty = Ty->getScalarType();
4228 DenormalMode Mode = F.getDenormalMode(Ty->getFltSemantics());
4229 return Mode.Input == DenormalMode::IEEE ||
4230 Mode.Input == DenormalMode::PositiveZero;
4234 Ty = Ty->getScalarType();
4235 DenormalMode Mode = F.getDenormalMode(Ty->getFltSemantics());
4260 DenormalMode Mode = F.getDenormalMode(Ty->getScalarType()->getFltSemantics());
4261 switch (Mode.Input) {
4280 // a denormal input could be flushed.
4284 // If we know the input can't be a denormal, it can't be flushed to 0.
4288 DenormalMode Mode = F.getDenormalMode(Ty->getScalarType()->getFltSemantics());
4297 if (Mode.Input == DenormalMode::PositiveZero ||
4299 Mode.Input == DenormalMode::Dynamic ||
4313 /// the result of the comparison is true when the input value is signed.
4320 case ICmpInst::ICMP_SLE: // True if LHS s<= -1
4323 case ICmpInst::ICMP_SGT: // True if LHS s> -1
4330 // True if LHS u> RHS and RHS == sign-bit-mask - 1
4334 // True if LHS u>= RHS and RHS == sign-bit-mask (2^7, 2^15, 2^31, etc)
4338 // True if LHS u< RHS and RHS == sign-bit-mask (2^7, 2^15, 2^31, etc)
4342 // True if LHS u<= RHS and RHS == sign-bit-mask - 1
4400 // fcmp o__ x, nan -> false
4401 // fcmp u__ x, nan -> true
4405 // fcmp ord x, zero|normal|subnormal|inf -> ~fcNan
4409 // fcmp uno x, zero|normal|subnormal|inf -> fcNan
4420 // Compares with fcNone are only exactly equal to fcZero if input denormals
4423 if (!inputDenormalIsIEEE(F, LHS->getType()))
4437 // non-canonical other non-NaN constants or LHS == RHS.
4475 // fcmp oeq x, +inf -> is_fpclass x, fcPosInf
4476 // fcmp oeq fabs(x), +inf -> is_fpclass x, fcInf
4477 // fcmp oeq x, -inf -> is_fpclass x, fcNegInf
4478 // fcmp oeq fabs(x), -inf -> is_fpclass x, 0 -> false
4480 // fcmp une x, +inf -> is_fpclass x, ~fcPosInf
4481 // fcmp une fabs(x), +inf -> is_fpclass x, ~fcInf
4482 // fcmp une x, -inf -> is_fpclass x, ~fcNegInf
4483 // fcmp une fabs(x), -inf -> is_fpclass x, fcAllFlags -> true
4498 // fcmp one x, -inf -> is_fpclass x, fcNegInf
4499 // fcmp one fabs(x), -inf -> is_fpclass x, ~fcNegInf & ~fcNan
4500 // fcmp one x, +inf -> is_fpclass x, ~fcNegInf & ~fcNan
4501 // fcmp one fabs(x), +inf -> is_fpclass x, ~fcInf & fcNan
4503 // fcmp ueq x, +inf -> is_fpclass x, fcPosInf|fcNan
4504 // fcmp ueq (fabs x), +inf -> is_fpclass x, fcInf|fcNan
4505 // fcmp ueq x, -inf -> is_fpclass x, fcNegInf|fcNan
4506 // fcmp ueq fabs(x), -inf -> is_fpclass x, fcNan
4524 // fcmp olt x, -inf -> false
4525 // fcmp uge x, -inf -> true
4530 // fcmp olt fabs(x), +inf -> fcFinite
4531 // fcmp uge fabs(x), +inf -> ~fcFinite
4532 // fcmp olt x, +inf -> fcFinite|fcNegInf
4533 // fcmp uge x, +inf -> ~(fcFinite|fcNegInf)
4542 // fcmp oge x, -inf -> ~fcNan
4543 // fcmp oge fabs(x), -inf -> ~fcNan
4544 // fcmp ult x, -inf -> fcNan
4545 // fcmp ult fabs(x), -inf -> fcNan
4550 // fcmp oge fabs(x), +inf -> fcInf
4551 // fcmp oge x, +inf -> fcPosInf
4552 // fcmp ult fabs(x), +inf -> ~fcInf
4553 // fcmp ult x, +inf -> ~fcPosInf
4562 // fcmp ogt x, -inf -> fcmp one x, -inf
4563 // fcmp ogt fabs(x), -inf -> fcmp ord x, x
4564 // fcmp ule x, -inf -> fcmp ueq x, -inf
4565 // fcmp ule fabs(x), -inf -> fcmp uno x, x
4581 // fcmp ole x, +inf -> fcmp ord x, x
4582 // fcmp ole fabs(x), +inf -> fcmp ord x, x
4583 // fcmp ole x, -inf -> fcmp oeq x, -inf
4584 // fcmp ole fabs(x), -inf -> false
4622 // fabs(x) o> -k -> fcmp ord x, x
4623 // fabs(x) u> -k -> true
4624 // fabs(x) o< -k -> false
4625 // fabs(x) u< -k -> fcmp uno x, x
4718 // fcmp olt x, smallest_normal -> fcNegInf|fcNegNormal|fcSubnormal|fcZero
4719 // fcmp olt fabs(x), smallest_normal -> fcSubnormal|fcZero
4720 // fcmp uge x, smallest_normal -> fcNan|fcPosNormal|fcPosInf
4721 // fcmp uge fabs(x), smallest_normal -> ~(fcSubnormal|fcZero)
4730 // fcmp oge x, smallest_normal -> fcPosNormal | fcPosInf
4731 // fcmp oge fabs(x), smallest_normal -> fcInf | fcNormal
4732 // fcmp ult x, smallest_normal -> ~(fcPosNormal | fcPosInf)
4733 // fcmp ult fabs(x), smallest_normal -> ~(fcInf | fcNormal)
4761 // TODO: Just call computeKnownFPClass for RHS to handle non-constants.
4776 Pred, *CxtI->getParent()->getParent(), LHS, *CRHS, LHS != V);
4804 for (BranchInst *BI : Q.DC->conditionsFor(V)) {
4805 Value *Cond = BI->getCondition();
4807 BasicBlockEdge Edge0(BI->getParent(), BI->getSuccessor(0));
4808 if (Q.DT->dominates(Edge0, Q.CxtI->getParent()))
4812 BasicBlockEdge Edge1(BI->getParent(), BI->getSuccessor(1));
4813 if (Q.DT->dominates(Edge1, Q.CxtI->getParent()))
4822 // Try to restrict the floating-point classes based on information from
4824 for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
4829 assert(I->getFunction() == Q.CxtI->getParent()->getParent() &&
4831 assert(I->getIntrinsicID() == Intrinsic::assume &&
4837 computeKnownFPClassFromCond(V, I->getArgOperand(0), /*CondIsTrue=*/true,
4846 unsigned Depth, const SimplifyQuery &Q);
4849 FPClassTest InterestedClasses, unsigned Depth,
4851 auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
4853 FVTy ? APInt::getAllOnes(FVTy->getNumElements()) : APInt(1, 1);
4854 computeKnownFPClass(V, DemandedElts, InterestedClasses, Known, Depth, Q);
4860 KnownFPClass &Known, unsigned Depth,
4867 computeKnownFPClass(Op->getOperand(0), DemandedElts, InterestedClasses,
4868 KnownSrc, Depth + 1, Q);
4882 unsigned Depth, const SimplifyQuery &Q) {
4891 assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth");
4894 Known.KnownFPClasses = CFP->getValueAPF().classify();
4895 Known.SignBit = CFP->isNegative();
4912 auto *VFVTy = dyn_cast<FixedVectorType>(V->getType());
4920 unsigned NumElts = VFVTy->getNumElements();
4925 Constant *Elt = CV->getAggregateElement(i);
4938 const APFloat &C = CElt->getValueAPF();
4952 KnownNotFromFlags |= CB->getRetNoFPClass();
4954 KnownNotFromFlags |= Arg->getNoFPClass();
4958 if (FPOp->hasNoNaNs())
4960 if (FPOp->hasNoInfs())
4984 // All recursive calls that increase depth must come after this.
4985 if (Depth == MaxAnalysisRecursionDepth)
4988 const unsigned Opc = Op->getOpcode();
4991 computeKnownFPClass(Op->getOperand(0), DemandedElts, InterestedClasses,
4992 Known, Depth + 1, Q);
4997 Value *Cond = Op->getOperand(0);
4998 Value *LHS = Op->getOperand(1);
4999 Value *RHS = Op->getOperand(2);
5008 const Function *F = cast<Instruction>(Op)->getFunction();
5038 Depth + 1, Q);
5042 Known2, Depth + 1, Q);
5050 const Intrinsic::ID IID = II->getIntrinsicID();
5056 computeKnownFPClass(II->getArgOperand(0), DemandedElts,
5057 InterestedClasses, Known, Depth + 1, Q);
5066 computeKnownFPClass(II->getArgOperand(0), DemandedElts, InterestedClasses,
5067 Known, Depth + 1, Q);
5068 computeKnownFPClass(II->getArgOperand(1), DemandedElts, InterestedClasses,
5069 KnownSign, Depth + 1, Q);
5078 if (II->getArgOperand(0) != II->getArgOperand(1))
5081 // The multiply cannot be -0 and therefore the add can't be -0
5084 // x * x + y is non-negative if y is non-negative.
5086 computeKnownFPClass(II->getArgOperand(2), DemandedElts, InterestedClasses,
5087 KnownAddend, Depth + 1, Q);
5100 computeKnownFPClass(II->getArgOperand(0), DemandedElts, InterestedSrcs,
5101 KnownSrc, Depth + 1, Q);
5108 // Any negative value besides -0 returns a nan.
5112 // The only negative value that can be returned is -0 for -0 inputs.
5115 // If the input denormal mode could be PreserveSign, a negative
5116 // subnormal input could produce a negative zero output.
5117 const Function *F = II->getFunction();
5119 (F && KnownSrc.isKnownNeverLogicalNegZero(*F, II->getType())))
5128 computeKnownFPClass(II->getArgOperand(0), DemandedElts, InterestedClasses,
5129 KnownSrc, Depth + 1, Q);
5140 computeKnownFPClass(II->getArgOperand(0), DemandedElts, InterestedClasses,
5141 KnownLHS, Depth + 1, Q);
5142 computeKnownFPClass(II->getArgOperand(1), DemandedElts, InterestedClasses,
5143 KnownRHS, Depth + 1, Q);
5191 const Function *Parent = II->getFunction();
5195 DenormalMode Mode = Parent->getDenormalMode(
5196 II->getType()->getScalarType()->getFltSemantics());
5225 computeKnownFPClass(II->getArgOperand(0), DemandedElts, InterestedClasses,
5226 KnownSrc, Depth + 1, Q);
5233 // denormal mode to preserve known-not-0 knowledge.
5243 const Function *F = II->getFunction();
5250 II->getType()->getScalarType()->getFltSemantics();
5251 DenormalMode DenormMode = F->getDenormalMode(FPType);
5263 if (DenormMode.Input == DenormalMode::PositiveZero ||
5265 DenormMode.Input == DenormalMode::IEEE))
5276 Known = computeKnownFPClass(II->getArgOperand(0), II->getFastMathFlags(),
5277 InterestedClasses, Depth + 1, Q);
5283 // reverse preserves all characteristics of the input vec's element.
5286 II->getArgOperand(0), DemandedElts.reverseBits(),
5287 II->getFastMathFlags(), InterestedClasses, Depth + 1, Q);
5302 computeKnownFPClass(II->getArgOperand(0), DemandedElts, InterestedSrcs,
5303 KnownSrc, Depth + 1, Q);
5312 if (IID == Intrinsic::trunc || !V->getType()->isMultiUnitFPType()) {
5319 // Negative round ups to 0 produce -0
5335 computeKnownFPClass(II->getArgOperand(0), DemandedElts, InterestedClasses,
5336 KnownSrc, Depth + 1, Q);
5346 Depth, Q);
5355 // log(+inf) -> +inf
5356 // log([+-]0.0) -> -inf
5357 // log(-inf) -> nan
5358 // log(-x) -> nan
5369 computeKnownFPClass(II->getArgOperand(0), DemandedElts, InterestedSrcs,
5370 KnownSrc, Depth + 1, Q);
5378 const Function *F = II->getFunction();
5379 if (F && KnownSrc.isKnownNeverLogicalZero(*F, II->getType()))
5388 const Value *Exp = II->getArgOperand(1);
5389 Type *ExpTy = Exp->getType();
5390 unsigned BitWidth = ExpTy->getScalarType()->getIntegerBitWidth();
5393 ExponentKnownBits, Depth + 1, Q);
5403 // pow(-x, exp) --> negative if exp is odd and x is negative.
5404 // pow(-0, exp) --> -inf if exp is negative odd.
5405 // pow(-0, exp) --> -0 if exp is positive odd.
5406 // pow(-inf, exp) --> -0 if exp is negative odd.
5407 // pow(-inf, exp) --> -inf if exp is positive odd.
5409 computeKnownFPClass(II->getArgOperand(0), DemandedElts, fcNegative,
5410 KnownSrc, Depth + 1, Q);
5417 computeKnownFPClass(II->getArgOperand(0), DemandedElts, InterestedClasses,
5418 KnownSrc, Depth + 1, Q);
5440 II->getType()->getScalarType()->getFltSemantics();
5442 const Value *ExpArg = II->getArgOperand(1);
5444 ExpArg, true, Q.IIQ.UseInstrInfo, Q.AC, Q.CxtI, Q.DT, Depth + 1);
5446 const int MantissaBits = Precision - 1;
5450 const Function *F = II->getFunction();
5452 if (ConstVal && ConstVal->isZero()) {
5453 // ldexp(x, 0) -> x, so propagate everything.
5454 Known.propagateCanonicalizingSrc(KnownSrc, *F, II->getType());
5467 if (F && KnownSrc.isKnownNeverLogicalPosZero(*F, II->getType()))
5469 if (F && KnownSrc.isKnownNeverLogicalNegZero(*F, II->getType()))
5476 computeKnownFPClass(II->getArgOperand(0), DemandedElts, InterestedClasses,
5477 Known, Depth + 1, Q);
5506 Op->getOpcode() == Instruction::FAdd &&
5519 computeKnownFPClass(Op->getOperand(1), DemandedElts, InterestedSrcs,
5520 KnownRHS, Depth + 1, Q);
5528 computeKnownFPClass(Op->getOperand(0), DemandedElts, InterestedSrcs,
5529 KnownLHS, Depth + 1, Q);
5537 const Function *F = cast<Instruction>(Op)->getFunction();
5539 if (Op->getOpcode() == Instruction::FAdd) {
5546 // (fadd x, 0.0) is guaranteed to return +0.0, not -0.0.
5547 if ((KnownLHS.isKnownNeverLogicalNegZero(*F, Op->getType()) ||
5548 KnownRHS.isKnownNeverLogicalNegZero(*F, Op->getType())) &&
5549 // Make sure output negative denormal can't flush to -0
5550 outputDenormalIsIEEEOrPosZero(*F, Op->getType()))
5556 // Only fsub -0, +0 can return -0
5557 if ((KnownLHS.isKnownNeverLogicalNegZero(*F, Op->getType()) ||
5558 KnownRHS.isKnownNeverLogicalPosZero(*F, Op->getType())) &&
5559 // Make sure output negative denormal can't flush to -0
5560 outputDenormalIsIEEEOrPosZero(*F, Op->getType()))
5568 // X * X is always non-negative or a NaN.
5569 if (Op->getOperand(0) == Op->getOperand(1))
5579 computeKnownFPClass(Op->getOperand(1), DemandedElts, NeedForNan, KnownRHS,
5580 Depth + 1, Q);
5584 computeKnownFPClass(Op->getOperand(0), DemandedElts, NeedForNan, KnownLHS,
5585 Depth + 1, Q);
5596 // If 0 * +/-inf produces NaN.
5602 const Function *F = cast<Instruction>(Op)->getFunction();
5607 KnownLHS.isKnownNeverLogicalZero(*F, Op->getType())) &&
5609 KnownRHS.isKnownNeverLogicalZero(*F, Op->getType())))
5616 if (Op->getOperand(0) == Op->getOperand(1)) {
5618 if (Op->getOpcode() == Instruction::FDiv) {
5622 // X % X is always exactly [+-]0.0 or a NaN.
5638 computeKnownFPClass(Op->getOperand(1), DemandedElts,
5640 Depth + 1, Q);
5650 computeKnownFPClass(Op->getOperand(0), DemandedElts,
5652 Depth + 1, Q);
5655 const Function *F = cast<Instruction>(Op)->getFunction();
5657 if (Op->getOpcode() == Instruction::FDiv) {
5662 ((F && KnownLHS.isKnownNeverLogicalZero(*F, Op->getType())) ||
5663 (F && KnownRHS.isKnownNeverLogicalZero(*F, Op->getType())))) {
5667 // X / -0.0 is -Inf (or NaN).
5675 KnownRHS.isKnownNeverLogicalZero(*F, Op->getType())) {
5696 computeKnownFPClass(Op->getOperand(0), DemandedElts, InterestedClasses,
5697 Known, Depth + 1, Q);
5700 Op->getType()->getScalarType()->getFltSemantics();
5702 Op->getOperand(0)->getType()->getScalarType()->getFltSemantics();
5720 Depth, Q);
5733 if (Op->getOpcode() == Instruction::UIToFP)
5740 int IntSize = Op->getOperand(0)->getType()->getScalarSizeInBits();
5741 if (Op->getOpcode() == Instruction::SIToFP)
5742 --IntSize;
5746 Type *FPTy = Op->getType()->getScalarType();
5747 if (ilogb(APFloat::getLargest(FPTy->getFltSemantics())) >= IntSize)
5754 // Look through extract element. If the index is non-constant or
5755 // out-of-range demand all elements, otherwise just the extracted element.
5756 const Value *Vec = Op->getOperand(0);
5757 const Value *Idx = Op->getOperand(1);
5760 if (auto *VecTy = dyn_cast<FixedVectorType>(Vec->getType())) {
5761 unsigned NumElts = VecTy->getNumElements();
5763 if (CIdx && CIdx->getValue().ult(NumElts))
5764 DemandedVecElts = APInt::getOneBitSet(NumElts, CIdx->getZExtValue());
5766 Depth + 1, Q);
5772 if (isa<ScalableVectorType>(Op->getType()))
5775 const Value *Vec = Op->getOperand(0);
5776 const Value *Elt = Op->getOperand(1);
5777 auto *CIdx = dyn_cast<ConstantInt>(Op->getOperand(2));
5782 if (CIdx && CIdx->getValue().ult(NumElts)) {
5783 DemandedVecElts.clearBit(CIdx->getZExtValue());
5784 NeedsElt = DemandedElts[CIdx->getZExtValue()];
5789 computeKnownFPClass(Elt, Known, InterestedClasses, Depth + 1, Q);
5801 Depth + 1, Q);
5816 const Value *LHS = Shuf->getOperand(0);
5818 Depth + 1, Q);
5829 const Value *RHS = Shuf->getOperand(1);
5831 Depth + 1, Q);
5839 ArrayRef<unsigned> Indices = Extract->getIndices();
5840 const Value *Src = Extract->getAggregateOperand();
5841 if (isa<StructType>(Src->getType()) && Indices.size() == 1 &&
5844 switch (II->getIntrinsicID()) {
5849 computeKnownFPClass(II->getArgOperand(0), DemandedElts,
5850 InterestedClasses, KnownSrc, Depth + 1, Q);
5852 const Function *F = cast<Instruction>(Op)->getFunction();
5857 if (F && KnownSrc.isKnownNeverLogicalNegZero(*F, Op->getType()))
5866 if (F && KnownSrc.isKnownNeverLogicalPosZero(*F, Op->getType()))
5881 computeKnownFPClass(Src, DemandedElts, InterestedClasses, Known, Depth + 1,
5887 // Unreachable blocks may have zero-operand PHI nodes.
5888 if (P->getNumIncomingValues() == 0)
5893 const unsigned PhiRecursionLimit = MaxAnalysisRecursionDepth - 2;
5895 if (Depth < PhiRecursionLimit) {
5897 if (isa_and_nonnull<UndefValue>(P->hasConstantValue()))
5902 for (const Use &U : P->operands()) {
5910 // to waste time spinning around in loops. We need at least depth 2 to
5915 P->getIncomingBlock(U)->getTerminator()));
5939 unsigned Depth,
5942 ::computeKnownFPClass(V, DemandedElts, InterestedClasses, KnownClasses, Depth,
5949 unsigned Depth,
5952 ::computeKnownFPClass(V, Known, InterestedClasses, Depth, SQ);
5958 // All byte-wide stores are splatable, even of arbitrary variables.
5959 if (V->getType()->isIntegerTy(8))
5962 LLVMContext &Ctx = V->getContext();
5969 // Return Undef for zero-sized type.
5970 if (DL.getTypeStoreSize(V->getType()).isZero())
5985 if (C->isNullValue())
5988 // Constant floating-point values can be handled as integer values if the
5992 if (CFP->getType()->isHalfTy())
5994 else if (CFP->getType()->isFloatTy())
5996 else if (CFP->getType()->isDoubleTy())
6005 if (CI->getBitWidth() % 8 == 0) {
6006 assert(CI->getBitWidth() > 8 && "8 bits should be handled above!");
6007 if (!CI->getValue().isSplat(8))
6009 return ConstantInt::get(Ctx, CI->getValue().trunc(8));
6014 if (CE->getOpcode() == Instruction::IntToPtr) {
6015 if (auto *PtrTy = dyn_cast<PointerType>(CE->getType())) {
6016 unsigned BitWidth = DL.getPointerSizeInBits(PtrTy->getAddressSpace());
6018 CE->getOperand(0), Type::getIntNTy(Ctx, BitWidth), false, DL))
6024 auto Merge = [&](Value *LHS, Value *RHS) -> Value * {
6038 for (unsigned I = 0, E = CA->getNumElements(); I != E; ++I)
6039 if (!(Val = Merge(Val, isBytewiseValue(CA->getElementAsConstant(I), DL))))
6046 for (unsigned I = 0, E = C->getNumOperands(); I != E; ++I)
6047 if (!(Val = Merge(Val, isBytewiseValue(C->getOperand(I), DL))))
6071 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
6075 To = BuildSubAggregate(From, To, STy->getElementType(i), Idxs, IdxSkip,
6082 PrevTo = Del->getAggregateOperand();
6083 Del->eraseFromParent();
6123 Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(),
6146 assert((V->getType()->isStructTy() || V->getType()->isArrayTy()) &&
6148 assert(ExtractValueInst::getIndexedType(V->getType(), idx_range) &&
6152 C = C->getAggregateElement(idx_range[0]);
6161 for (const unsigned *i = I->idx_begin(), *e = I->idx_end();
6186 return FindInsertedValue(I->getAggregateOperand(), idx_range,
6192 return FindInsertedValue(I->getInsertedValueOperand(),
6202 unsigned size = I->getNumIndices() + idx_range.size();
6207 Idxs.append(I->idx_begin(), I->idx_end());
6215 return FindInsertedValue(I->getAggregateOperand(), Idxs, InsertBefore);
6225 if (GEP->getNumOperands() != 3)
6228 // Make sure the index-ee is a pointer to array of \p CharSize integers.
6230 ArrayType *AT = dyn_cast<ArrayType>(GEP->getSourceElementType());
6231 if (!AT || !AT->getElementType()->isIntegerTy(CharSize))
6236 const ConstantInt *FirstIdx = dyn_cast<ConstantInt>(GEP->getOperand(1));
6237 if (!FirstIdx || !FirstIdx->isZero())
6261 if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer())
6265 const DataLayout &DL = GV->getDataLayout();
6266 APInt Off(DL.getIndexTypeSizeInBits(V->getType()), 0);
6268 if (GV != V->stripAndAccumulateConstantOffsets(DL, Off,
6287 if (GV->getInitializer()->isNullValue()) {
6288 Type *GVTy = GV->getValueType();
6295 // transform even undefined library calls into simpler, well-defined
6298 Slice.Length = Length < Offset ? 0 : Length - Offset;
6302 auto *Init = const_cast<Constant *>(GV->getInitializer());
6304 Type *InitElTy = ArrayInit->getElementType();
6305 if (InitElTy->isIntegerTy(ElementSize)) {
6309 ArrayTy = ArrayInit->getType();
6326 ArrayTy = dyn_cast<ArrayType>(Init->getType());
6329 uint64_t NumElts = ArrayTy->getArrayNumElements();
6335 Slice.Length = NumElts - Offset;
6340 /// not be a nul-terminated string. On success, store the bytes in Str and
6351 // Return a nul-terminated string even for an empty Slice. This is
6370 Str = Slice.Array->getAsString();
6377 // some other way that the string is length-bound.
6393 V = V->stripPointerCasts();
6401 // If it was new, see if all the input strings are the same length.
6403 for (Value *IncValue : PN->incoming_values()) {
6405 if (Len == 0) return 0; // Unknown length -> unknown.
6410 return 0; // Disagree -> unknown.
6418 // strlen(select(c,x,y)) -> strlen(x) ^ strlen(y)
6420 uint64_t Len1 = GetStringLengthH(SI->getTrueValue(), PHIs, CharSize);
6422 uint64_t Len2 = GetStringLengthH(SI->getFalseValue(), PHIs, CharSize);
6445 if (Slice.Array->getElementAsInteger(Slice.Offset + NullIndex) == 0)
6455 if (!V->getType()->isPointerTy())
6470 if (const Value *RV = Call->getReturnedArgOperand())
6475 return Call->getArgOperand(0);
6481 switch (Call->getIntrinsicID()) {
6487 // input pointer (and thus preserve null-ness for the purposes of escape
6502 return !Call->getParent()->getParent()->isPresplitCoroutine();
6508 /// \p PN defines a loop-variant pointer to an object. Check if the
6512 // Find the loop-defined value.
6513 Loop *L = LI->getLoopFor(PN->getParent());
6514 if (PN->getNumIncomingValues() != 2)
6518 auto *PrevValue = dyn_cast<Instruction>(PN->getIncomingValue(0));
6519 if (!PrevValue || LI->getLoopFor(PrevValue->getParent()) != L)
6520 PrevValue = dyn_cast<Instruction>(PN->getIncomingValue(1));
6521 if (!PrevValue || LI->getLoopFor(PrevValue->getParent()) != L)
6530 if (!L->isLoopInvariant(Load->getPointerOperand()))
6536 if (!V->getType()->isPointerTy())
6540 V = GEP->getPointerOperand();
6543 Value *NewV = cast<Operator>(V)->getOperand(0);
6544 if (!NewV->getType()->isPointerTy())
6548 if (GA->isInterposable())
6550 V = GA->getAliasee();
6553 // Look through single-arg phi nodes created by LCSSA.
6554 if (PHI->getNumIncomingValues() == 1) {
6555 V = PHI->getIncomingValue(0);
6576 assert(V->getType()->isPointerTy() && "Unexpected operand type!");
6595 Worklist.push_back(SI->getTrueValue());
6596 Worklist.push_back(SI->getFalseValue());
6611 if (!LI || !LI->isLoopHeader(PN->getParent()) ||
6613 append_range(Worklist, PN->incoming_values());
6646 Worklist.push_back(SI->getTrueValue());
6647 Worklist.push_back(SI->getFalseValue());
6652 append_range(Worklist, PN->incoming_values());
6672 if (U->getOpcode() == Instruction::PtrToInt)
6673 return U->getOperand(0);
6680 if (U->getOpcode() != Instruction::Add ||
6681 (!isa<ConstantInt>(U->getOperand(1)) &&
6682 Operator::getOpcode(U->getOperand(1)) != Instruction::Mul &&
6683 !isa<PHINode>(U->getOperand(1))))
6685 V = U->getOperand(0);
6689 assert(V->getType()->isIntegerTy() && "Unexpected operand type!");
6711 getUnderlyingObjectFromInt(cast<User>(V)->getOperand(0));
6712 if (O->getType()->isPointerTy()) {
6749 AddWork(CI->getOperand(0));
6751 for (Value *IncValue : PN->incoming_values())
6754 AddWork(SI->getTrueValue());
6755 AddWork(SI->getFalseValue());
6757 if (OffsetZero && !GEP->hasAllZeroIndices())
6759 AddWork(GEP->getPointerOperand());
6761 Value *Returned = CB->getReturnedArgOperand();
6776 for (const User *U : V->users()) {
6781 if (AllowLifetime && II->isLifetimeStartOrEnd())
6784 if (AllowDroppable && II->isDroppable())
6818 return isSafeToSpeculativelyExecuteWithOpcode(Inst->getOpcode(), Inst, CtxI,
6827 if (Inst->getOpcode() != Opcode) {
6831 if (Inst->getNumOperands() < NumLeadingOperands)
6833 const Type *ExpectedType = Inst->getType();
6835 if (Inst->getOperand(ItOp)->getType() != ExpectedType)
6853 if (match(Inst->getOperand(1), m_APInt(V)))
6859 // x / y is undefined if y == 0 or x == INT_MIN and y == -1
6861 if (!match(Inst->getOperand(1), m_APInt(Denominator)))
6866 // It's safe to hoist if the denominator is not 0 or -1.
6867 if (!Denominator->isAllOnes())
6869 // At this point we know that the denominator is -1. It is safe to hoist as
6871 if (match(Inst->getOperand(0), m_APInt(Numerator)))
6872 return !Numerator->isMinSignedValue();
6885 const DataLayout &DL = LI->getDataLayout();
6886 return isDereferenceableAndAlignedPointer(LI->getPointerOperand(),
6887 LI->getType(), LI->getAlign(), DL,
6894 const Function *Callee = CI->getCalledFunction();
6896 // The called function could have undefined behavior or side-effects, even
6898 return Callee && Callee->isSpeculatable();
6934 // 1) Can't reorder two inf-loop calls, even if readonly
6935 // 2) Also can't reorder an inf-loop call below a instruction which isn't
6973 KnownBits LHSKnown = computeKnownBits(LHS, /*Depth=*/0, SQ);
6974 KnownBits RHSKnown = computeKnownBits(RHS, /*Depth=*/0, SQ);
6976 // mul nsw of two non-negative numbers is also nuw.
6994 unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
7016 KnownBits LHSKnown = computeKnownBits(LHS, /*Depth=*/0, SQ);
7017 KnownBits RHSKnown = computeKnownBits(RHS, /*Depth=*/0, SQ);
7039 if (Add && Add->hasNoSignedWrap()) {
7085 computeKnownBitsFromContext(Add, AddKnown, /*Depth=*/0, SQ);
7097 // X - (X % ?)
7101 // X - (X -nuw ?)
7104 // then determining no-overflow may allow other transforms.
7133 // X - (X % ?)
7137 // X - (X -nsw ?)
7140 // then determining no-overflow may allow other transforms.
7164 for (const User *U : WO->users()) {
7166 assert(EVI->getNumIndices() == 1 && "Obvious from CI's type");
7168 if (EVI->getIndices()[0] == 0)
7171 assert(EVI->getIndices()[0] == 1 && "Obvious from CI's type");
7173 for (const auto *U : EVI->users())
7175 assert(B->isConditional() && "How else is it using an i1?");
7187 BasicBlockEdge NoWrapEdge(BI->getParent(), BI->getSuccessor(1));
7191 // Check if all users of the add are provably no-wrap.
7195 if (DT.dominates(NoWrapEdge, Result->getParent()))
7198 for (const auto &RU : Result->uses())
7217 if (auto *FVTy = dyn_cast<FixedVectorType>(C->getType())) {
7218 unsigned NumElts = FVTy->getNumElements();
7220 ShiftAmounts.push_back(C->getAggregateElement(i));
7221 } else if (isa<ScalableVectorType>(C->getType()))
7228 return CI && CI->getValue().ult(C->getType()->getIntegerBitWidth());
7252 Op->hasPoisonGeneratingAnnotations())
7255 unsigned Opcode = Op->getOpcode();
7257 // Check whether opcode is a poison/undef-generating operation
7262 return includesPoison(Kind) && !shiftAmountKnownInRange(Op->getOperand(1));
7270 switch (II->getIntrinsicID()) {
7275 if (cast<ConstantInt>(II->getArgOperand(1))->isNullValue())
7304 !shiftAmountKnownInRange(II->getArgOperand(1));
7351 return !CB->hasRetAttr(Attribute::NoUndef);
7356 auto *VTy = cast<VectorType>(Op->getOperand(0)->getType());
7357 unsigned IdxOp = Op->getOpcode() == Instruction::InsertElement ? 2 : 1;
7358 auto *Idx = dyn_cast<ConstantInt>(Op->getOperand(IdxOp));
7361 Idx->getValue().uge(VTy->getElementCount().getKnownMinValue());
7366 ? cast<ConstantExpr>(Op)->getShuffleMask()
7367 : cast<ShuffleVectorInst>(Op)->getShuffleMask();
7392 if (isa<CastInst>(Op) || (CE && CE->isCast()))
7414 unsigned Depth) {
7419 if (Depth >= MaxDepth)
7423 if (any_of(I->operands(), [=](const Use &Op) {
7425 directlyImpliesPoison(ValAssumedPoison, Op, Depth + 1);
7435 llvm::is_contained(II->args(), ValAssumedPoison)))
7442 unsigned Depth) {
7446 if (directlyImpliesPoison(ValAssumedPoison, V, /* Depth */ 0))
7450 if (Depth >= MaxDepth)
7455 return all_of(I->operands(), [=](const Value *Op) {
7456 return impliesPoison(Op, V, Depth + 1);
7463 return ::impliesPoison(ValAssumedPoison, V, /* Depth */ 0);
7470 const DominatorTree *DT, unsigned Depth, UndefPoisonKind Kind) {
7471 if (Depth >= MaxAnalysisRecursionDepth)
7478 if (A->hasAttribute(Attribute::NoUndef) ||
7479 A->hasAttribute(Attribute::Dereferenceable) ||
7480 A->hasAttribute(Attribute::DereferenceableOrNull))
7495 if (C->getType()->isVectorTy() && !isa<ConstantExpr>(C)) {
7496 if (includesUndef(Kind) && C->containsUndefElement())
7498 if (includesPoison(Kind) && C->containsPoisonElement())
7500 return !C->containsConstantExpression();
7511 // well. We believe that such addrspacecast is equivalent to no-op.
7512 auto *StrippedV = V->stripPointerCastsSameRepresentation();
7518 return isGuaranteedNotToBeUndefOrPoison(V, AC, CtxI, DT, Depth + 1, Kind);
7528 if (CB->hasRetAttr(Attribute::NoUndef) ||
7529 CB->hasRetAttr(Attribute::Dereferenceable) ||
7530 CB->hasRetAttr(Attribute::DereferenceableOrNull))
7535 unsigned Num = PN->getNumIncomingValues();
7538 auto *TI = PN->getIncomingBlock(i)->getTerminator();
7539 if (!isGuaranteedNotToBeUndefOrPoison(PN->getIncomingValue(i), AC, TI,
7540 DT, Depth + 1, Kind)) {
7549 all_of(Opr->operands(), OpCheck))
7554 if (I->hasMetadata(LLVMContext::MD_noundef) ||
7555 I->hasMetadata(LLVMContext::MD_dereferenceable) ||
7556 I->hasMetadata(LLVMContext::MD_dereferenceable_or_null))
7563 if (!CtxI || !CtxI->getParent() || !DT)
7566 auto *DNode = DT->getNode(CtxI->getParent());
7576 auto *Dominator = DNode->getIDom();
7579 if (!includesUndef(Kind) || V->getType()->isIntegerTy())
7581 auto *TI = Dominator->getBlock()->getTerminator();
7585 if (BI->isConditional())
7586 Cond = BI->getCondition();
7588 Cond = SI->getCondition();
7597 if (any_of(Opr->operands(), [V](const Use &U) {
7604 Dominator = Dominator->getIDom();
7616 unsigned Depth) {
7617 return ::isGuaranteedNotToBeUndefOrPoison(V, AC, CtxI, DT, Depth,
7623 const DominatorTree *DT, unsigned Depth) {
7624 return ::isGuaranteedNotToBeUndefOrPoison(V, AC, CtxI, DT, Depth,
7630 const DominatorTree *DT, unsigned Depth) {
7631 return ::isGuaranteedNotToBeUndefOrPoison(V, AC, CtxI, DT, Depth,
7659 if (mustTriggerUB(I, KnownPoison) && DT->dominates(I, OnPathTo))
7664 if (I != Root && !any_of(I->operands(), [&KnownPoison](const Use &U) {
7670 for (const User *User : I->users())
7674 // Might be non-UB, or might have a path we couldn't prove must execute on
7681 return ::computeOverflowForSignedAdd(Add->getOperand(0), Add->getOperand(1),
7708 switch (classifyEHPersonality(I->getFunction()->getPersonalityFn())) {
7721 return !I->mayThrow() && I->willReturn();
7742 assert(ScanLimit && "scan limit must be non-zero");
7746 if (--ScanLimit == 0)
7760 if (I->getParent() != L->getHeader()) return false;
7762 for (const Instruction &LI : *L->getHeader()) {
7771 switch (I->getOpcode()) {
7780 switch (II->getIntrinsicID()) {
7788 // If an input is a vector containing a poison element, the
7831 switch (I->getOpcode()) {
7833 if (Handle(cast<StoreInst>(I)->getPointerOperand()))
7838 if (Handle(cast<LoadInst>(I)->getPointerOperand()))
7845 if (Handle(cast<AtomicCmpXchgInst>(I)->getPointerOperand()))
7850 if (Handle(cast<AtomicRMWInst>(I)->getPointerOperand()))
7857 if (CB->isIndirectCall() && Handle(CB->getCalledOperand()))
7859 for (unsigned i = 0; i < CB->arg_size(); ++i)
7860 if ((CB->paramHasAttr(i, Attribute::NoUndef) ||
7861 CB->paramHasAttr(i, Attribute::Dereferenceable) ||
7862 CB->paramHasAttr(i, Attribute::DereferenceableOrNull)) &&
7863 Handle(CB->getArgOperand(i)))
7868 if (I->getFunction()->hasRetAttribute(Attribute::NoUndef) &&
7869 Handle(I->getOperand(0)))
7873 if (Handle(cast<SwitchInst>(I)->getCondition()))
7878 if (BR->isConditional() && Handle(BR->getCondition()))
7903 switch (I->getOpcode()) {
7909 return Handle(I->getOperand(1));
7936 // this, look out for the distinction between post-dominance and strong
7937 // post-dominance.
7941 BB = Inst->getParent();
7942 Begin = Inst->getIterator();
7945 if (Arg->getParent()->isDeclaration())
7947 BB = &Arg->getParent()->getEntryBlock();
7948 Begin = BB->begin();
7956 BasicBlock::const_iterator End = BB->end();
7961 // well-defined operands.
7966 if (--ScanLimit == 0)
7992 if (--ScanLimit == 0)
8017 BB = BB->getSingleSuccessor();
8021 Begin = BB->getFirstNonPHI()->getIterator();
8022 End = BB->end();
8040 return !C->isNaN();
8043 if (!C->getElementType()->isFloatingPointTy())
8045 for (unsigned I = 0, E = C->getNumElements(); I < E; ++I) {
8046 if (C->getElementAsAPFloat(I).isNaN())
8060 return !C->isZero();
8063 if (!C->getElementType()->isFloatingPointTy())
8065 for (unsigned I = 0, E = C->getNumElements(); I < E; ++I) {
8066 if (C->getElementAsAPFloat(I).isZero())
8076 /// Given non-min/max outer cmp/select from the clamp pattern this
8084 // X < C1 ? C1 : Min(X, C2) --> Max(C1, Min(X, C2))
8085 // X > C1 ? C1 : Max(X, C2) --> Min(C1, Max(X, C2))
8099 if (CmpRHS != TrueVal || !match(CmpRHS, m_APFloat(FC1)) || !FC1->isFinite())
8146 C1->slt(*C2) && Pred == CmpInst::ICMP_SLT)
8151 C1->sgt(*C2) && Pred == CmpInst::ICMP_SGT)
8156 C1->ult(*C2) && Pred == CmpInst::ICMP_ULT)
8161 C1->ugt(*C2) && Pred == CmpInst::ICMP_UGT)
8172 unsigned Depth) {
8177 SelectPatternResult L = matchSelectPattern(TVal, A, B, nullptr, Depth + 1);
8182 SelectPatternResult R = matchSelectPattern(FVal, C, D, nullptr, Depth + 1);
8230 // a pred c ? m(a, b) : m(c, b) --> m(m(a, b), m(c, b))
8231 // ~c pred ~a ? m(a, b) : m(c, b) --> m(m(a, b), m(c, b))
8237 // a pred d ? m(a, b) : m(b, d) --> m(m(a, b), m(b, d))
8238 // ~d pred ~a ? m(a, b) : m(b, d) --> m(m(a, b), m(b, d))
8244 // b pred c ? m(a, b) : m(c, a) --> m(m(a, b), m(c, a))
8245 // ~c pred ~b ? m(a, b) : m(c, a) --> m(m(a, b), m(c, a))
8251 // b pred d ? m(a, b) : m(a, d) --> m(m(a, b), m(a, d))
8252 // ~d pred ~b ? m(a, b) : m(a, d) --> m(m(a, b), m(a, d))
8262 /// If the input value is the result of a 'not' op, constant integer, or vector
8263 /// splat of a constant integer, return the bitwise-not source value.
8264 /// TODO: This could be extended to handle non-splat vector integer constants.
8272 return ConstantInt::get(V->getType(), ~(*C));
8277 /// Match non-obvious integer minimum and maximum sequences.
8282 unsigned Depth) {
8291 SPR = matchMinMaxOfMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, Depth);
8334 if (Pred == CmpInst::ICMP_SLT && C1->isZero() && C2->isMaxSignedValue())
8338 // (X >s -1) ? MINVAL : X ==> (X <u MINVAL) ? MINVAL : X ==> UMAX
8339 // (X >s -1) ? X : MINVAL ==> (X <u MINVAL) ? X : MINVAL ==> UMIN
8340 if (Pred == CmpInst::ICMP_SGT && C1->isAllOnes() && C2->isMinSignedValue())
8356 if (NeedNSW && !BO->hasNoSignedWrap())
8359 auto *Zero = cast<Constant>(BO->getOperand(0));
8360 if (!AllowPoison && !Zero->isNullValue())
8366 // X = -Y or Y = -X
8405 unsigned Depth) {
8408 // IEEE-754 ignores the sign of 0.0 in comparisons. So if the select has one
8411 // elements because those can not be back-propagated for analysis.
8414 !cast<Constant>(TrueVal)->containsUndefOrPoisonElement())
8417 !cast<Constant>(FalseVal)->containsUndefOrPoisonElement())
8436 // (0.0 <= -0.0) ? 0.0 : -0.0 // Returns 0.0
8437 // minNum(0.0, -0.0) // May return -0.0 or 0.0 (IEEE 754-2008 5.3.1)
8457 // When given one NaN and one non-NaN input:
8458 // - maxnum/minnum (C99 fmaxf()/fminf()) return the non-NaN input.
8459 // - A simple C99 (a < b ? a : b) construction will return 'b' (as the
8460 // ordered comparison fails), which could be NaN or non-NaN.
8467 // Both operands are known non-NaN.
8474 // LHS is non-NaN, so if RHS is NaN then NaN will be returned.
8486 // LHS is non-NaN, so if RHS is NaN then non-NaN will be returned.
8530 // Sign-extending LHS does not change its sign, so TrueVal/FalseVal can
8537 // Set the return values. If the compare uses the negated value (-X >s 0),
8544 // (X >s 0) ? X : -X or (X >s -1) ? X : -X --> ABS(X)
8545 // (-X >s 0) ? -X : X or (-X >s -1) ? -X : X --> ABS(X)
8549 // (X >=s 0) ? X : -X or (X >=s 1) ? X : -X --> ABS(X)
8553 // (X <s 0) ? X : -X or (X <s 1) ? X : -X --> NABS(X)
8554 // (-X <s 0) ? -X : X or (-X <s 1) ? -X : X --> NABS(X)
8559 // Set the return values. If the compare uses the negated value (-X >s 0),
8566 // (X >s 0) ? -X : X or (X >s -1) ? -X : X --> NABS(X)
8567 // (-X >s 0) ? X : -X or (-X >s -1) ? X : -X --> NABS(X)
8571 // (X <s 0) ? -X : X or (X <s 1) ? -X : X --> ABS(X)
8572 // (-X <s 0) ? X : -X or (-X <s 1) ? X : -X --> ABS(X)
8579 return matchMinMax(Pred, CmpLHS, CmpRHS, TrueVal, FalseVal, LHS, RHS, Depth);
8581 // According to (IEEE 754-2008 5.3.1), minNum(0.0, -0.0) and similar
8582 // may return either -0.0 or 0.0, so fcmp/select pair has stricter
8612 *CastOp = Cast1->getOpcode();
8613 Type *SrcTy = Cast1->getSrcTy();
8616 if (*CastOp == Cast2->getOpcode() && SrcTy == Cast2->getSrcTy())
8617 return Cast2->getOperand(0);
8625 const DataLayout &DL = CmpI->getDataLayout();
8629 if (CmpI->isUnsigned())
8633 if (CmpI->isSigned())
8638 if (match(CmpI->getOperand(1), m_Constant(CmpConst)) &&
8639 CmpConst->getType() == SrcTy) {
8656 // select i1 %cond, x, -x.
8663 unsigned ExtOp = CmpI->isSigned() ? Instruction::SExt : Instruction::ZExt;
8694 ConstantFoldCastOperand(*CastOp, CastedTo, C->getType(), DL);
8703 unsigned Depth) {
8704 if (Depth >= MaxAnalysisRecursionDepth)
8710 CmpInst *CmpI = dyn_cast<CmpInst>(SI->getCondition());
8713 Value *TrueVal = SI->getTrueValue();
8714 Value *FalseVal = SI->getFalseValue();
8717 CastOp, Depth);
8722 Instruction::CastOps *CastOp, unsigned Depth) {
8723 CmpInst::Predicate Pred = CmpI->getPredicate();
8724 Value *CmpLHS = CmpI->getOperand(0);
8725 Value *CmpRHS = CmpI->getOperand(1);
8728 FMF = CmpI->getFastMathFlags();
8731 if (CmpI->isEquality())
8735 if (CastOp && CmpLHS->getType() != TrueVal->getType()) {
8738 // -0.0 because there is no corresponding integer value.
8742 cast<CastInst>(TrueVal)->getOperand(0), C,
8743 LHS, RHS, Depth);
8747 // -0.0 because there is no corresponding integer value.
8751 C, cast<CastInst>(FalseVal)->getOperand(0),
8752 LHS, RHS, Depth);
8756 LHS, RHS, Depth);
8848 // Handle the case of a simple two-predecessor recurrence PHI.
8851 if (P->getNumIncomingValues() != 2)
8855 Value *L = P->getIncomingValue(i);
8856 Value *R = P->getIncomingValue(!i);
8860 unsigned Opcode = LU->getOpcode();
8865 // TODO: Expand list -- xor, div, gep, uaddo, etc..
8875 Value *LL = LU->getOperand(0);
8876 Value *LR = LU->getOperand(1);
8906 P = dyn_cast<PHINode>(I->getOperand(0));
8908 P = dyn_cast<PHINode>(I->getOperand(1));
8929 return !C->isNegative();
8944 return CLHS->sle(*CRHS);
8952 cast<OverflowingBinaryOperator>(RHS)->hasNoUnsignedWrap())
8969 if (match(LHS, m_UDiv(m_Specific(RHS), m_APInt(C))) && C->ugt(1))
8985 return CLHS->ule(*CRHS);
9070 Value *L0 = LHS->getOperand(0);
9071 Value *L1 = LHS->getOperand(1);
9076 LHSIsTrue ? LHS->getPredicate() : LHS->getInversePredicate();
9078 // We can have non-canonical operands, so try to normalize any common operand
9098 // See if we can infer anything if operand-0 matches and we have at least one
9108 /*CxtI=*/nullptr, /*DT=*/nullptr, MaxAnalysisRecursionDepth - 1);
9111 /*CxtI=*/nullptr, /*DT=*/nullptr, MaxAnalysisRecursionDepth - 1);
9146 const DataLayout &DL, bool LHSIsTrue, unsigned Depth) {
9148 assert((LHS->getOpcode() == Instruction::And ||
9149 LHS->getOpcode() == Instruction::Or ||
9150 LHS->getOpcode() == Instruction::Select) &&
9153 assert(Depth <= MaxAnalysisRecursionDepth && "Hit recursion limit");
9161 // FIXME: Make this non-recursion.
9163 ALHS, RHSPred, RHSOp0, RHSOp1, DL, LHSIsTrue, Depth + 1))
9166 ARHS, RHSPred, RHSOp0, RHSOp1, DL, LHSIsTrue, Depth + 1))
9176 const DataLayout &DL, bool LHSIsTrue, unsigned Depth) {
9178 if (Depth == MaxAnalysisRecursionDepth)
9183 if (RHSOp0->getType()->isVectorTy() != LHS->getType()->isVectorTy())
9186 assert(LHS->getType()->isIntOrIntVectorTy(1) &&
9202 if ((LHSI->getOpcode() == Instruction::And ||
9203 LHSI->getOpcode() == Instruction::Or ||
9204 LHSI->getOpcode() == Instruction::Select))
9206 Depth);
9213 bool LHSIsTrue, unsigned Depth) {
9228 LHS, RHSCmp->getPredicate(), RHSCmp->getOperand(0),
9229 RHSCmp->getOperand(1), DL, LHSIsTrue, Depth))
9234 if (Depth == MaxAnalysisRecursionDepth)
9242 isImpliedCondition(LHS, RHS1, DL, LHSIsTrue, Depth + 1))
9246 isImpliedCondition(LHS, RHS2, DL, LHSIsTrue, Depth + 1))
9252 isImpliedCondition(LHS, RHS1, DL, LHSIsTrue, Depth + 1))
9256 isImpliedCondition(LHS, RHS2, DL, LHSIsTrue, Depth + 1))
9268 if (!ContextI || !ContextI->getParent())
9273 const BasicBlock *ContextBB = ContextI->getParent();
9274 const BasicBlock *PredBB = ContextBB->getSinglePredecessor();
9281 if (!match(PredBB->getTerminator(), m_Br(m_Value(PredCond), TrueBB, FalseBB)))
9298 assert(Cond->getType()->isIntOrIntVectorTy(1) && "Condition must be bool");
9324 if (match(BO.getOperand(1), m_APInt(C)) && !C->isZero()) {
9329 // Otherwise if both no-wraps are set, use the unsigned range because it
9331 // "add nuw nsw i8 X, -2" is unsigned [254,255] vs. signed [-128, 125].
9339 if (C->isNegative()) {
9340 // 'add nsw x, -C' produces [SINT_MIN, SINT_MAX - C].
9356 // X & -X is a power of two or zero. So we can cap the value at max power of
9370 if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
9375 unsigned ShiftAmount = Width - 1;
9376 if (!C->isZero() && IIQ.isExact(&BO))
9377 ShiftAmount = C->countr_zero();
9378 if (C->isNegative()) {
9379 // 'ashr C, x' produces [C, C >> (Width-1)]
9381 Upper = C->ashr(ShiftAmount) + 1;
9383 // 'ashr C, x' produces [C >> (Width-1), C]
9384 Lower = C->ashr(ShiftAmount);
9391 if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
9395 // 'lshr C, x' produces [C >> (Width-1), C].
9396 unsigned ShiftAmount = Width - 1;
9397 if (!C->isZero() && IIQ.isExact(&BO))
9398 ShiftAmount = C->countr_zero();
9399 Lower = C->lshr(ShiftAmount);
9411 if (C->isNegative()) {
9412 // 'shl nsw C, x' produces [C << CLO(C)-1, C]
9413 unsigned ShiftAmount = C->countl_one() - 1;
9414 Lower = C->shl(ShiftAmount);
9417 // 'shl nsw C, x' produces [C, C << CLZ(C)-1]
9418 unsigned ShiftAmount = C->countl_zero() - 1;
9420 Upper = C->shl(ShiftAmount) + 1;
9432 Upper = APInt::getHighBitsSet(Width, C->popcount()) + 1;
9434 } else if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) {
9435 Upper = APInt::getBitsSetFrom(Width, C->getZExtValue()) + 1;
9443 if (C->isAllOnes()) {
9444 // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX]
9445 // where C != -1 and C != 0 and C != 1
9448 } else if (C->countl_zero() < Width - 1) {
9450 // where C != -1 and C != 0 and C != 1
9459 if (C->isMinSignedValue()) {
9460 // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2].
9464 // 'sdiv C, x' produces [-|C|, |C|].
9465 Upper = C->abs() + 1;
9466 Lower = (-Upper) + 1;
9472 if (match(BO.getOperand(1), m_APInt(C)) && !C->isZero()) {
9483 // 'srem x, C' produces (-|C|, |C|).
9484 Upper = C->abs();
9485 Lower = (-Upper) + 1;
9487 if (C->isNegative()) {
9488 // 'srem -|C|, x' produces [-|C|, 0].
9513 unsigned Width = II.getType()->getScalarSizeInBits();
9531 if (C->isNegative())
9532 // sadd.sat(x, -C) produces [SINT_MIN, SINT_MAX + (-C)].
9547 // usub.sat(x, C) produces [0, UINT_MAX - C].
9550 APInt::getMaxValue(Width) - *C + 1);
9554 if (C->isNegative())
9555 // ssub.sat(-C, x) produces [SINT_MIN, -SINT_MIN + (-C)].
9557 *C - APInt::getSignedMinValue(Width) +
9560 // ssub.sat(+C, x) produces [-SINT_MAX + C, SINT_MAX].
9561 return ConstantRange::getNonEmpty(*C - APInt::getSignedMaxValue(Width),
9564 if (C->isNegative())
9565 // ssub.sat(x, -C) produces [SINT_MIN - (-C), SINT_MAX]:
9566 return ConstantRange::getNonEmpty(APInt::getSignedMinValue(Width) - *C,
9569 // ssub.sat(x, +C) produces [SINT_MIN, SINT_MAX - C].
9571 APInt::getSignedMaxValue(Width) - *C +
9600 // otherwise it is [0..SIGNED_MIN], as -SIGNED_MIN == SIGNED_MIN.
9624 unsigned BitWidth = SI.getType()->getScalarSizeInBits();
9633 // otherwise it is [0..SIGNED_MIN], as -SIGNED_MIN == SIGNED_MIN.
9644 // The result of -abs(X) is <= 0.
9672 unsigned BitWidth = I->getType()->getScalarSizeInBits();
9673 if (!I->getOperand(0)->getType()->getScalarType()->isHalfTy())
9676 Lower = APInt(BitWidth, -65504);
9690 unsigned Depth) {
9691 assert(V->getType()->isIntOrIntVectorTy() && "Expected integer instruction");
9693 if (Depth == MaxAnalysisRecursionDepth)
9694 return ConstantRange::getFull(V->getType()->getScalarSizeInBits());
9697 return C->toConstantRange();
9699 unsigned BitWidth = V->getType()->getScalarSizeInBits();
9712 SI->getTrueValue(), ForSigned, UseInstrInfo, AC, CtxI, DT, Depth + 1);
9714 SI->getFalseValue(), ForSigned, UseInstrInfo, AC, CtxI, DT, Depth + 1);
9724 if (std::optional<ConstantRange> Range = A->getRange())
9732 if (std::optional<ConstantRange> Range = CB->getRange())
9738 for (auto &AssumeVH : AC->assumptionsFor(V)) {
9742 assert(I->getParent()->getParent() == CtxI->getParent()->getParent() &&
9744 assert(I->getIntrinsicID() == Intrinsic::assume &&
9749 Value *Arg = I->getArgOperand(0);
9752 if (!Cmp || Cmp->getOperand(0) != V)
9754 // TODO: Set "ForSigned" parameter via Cmp->isSigned()?
9756 computeConstantRange(Cmp->getOperand(1), /* ForSigned */ false,
9757 UseInstrInfo, AC, I, DT, Depth + 1);
9759 ConstantRange::makeAllowedICmpRegion(Cmp->getPredicate(), RHS));
9816 // assume(A && B) is split to -> assume(A); assume(B);
9817 // assume(!(A || B)) is split to -> assume(!A); assume(!B);
9851 // X & Y u> C -> X >u C && Y >u C
9852 // X | Y u< C -> X u< C && Y u< C
9853 // X nuw+ Y u< C -> X u< C && Y u< C
9860 // X nuw- Y u> C -> X u> C
9866 // Handle icmp slt/sgt (bitcast X to int), 0/-1, which is supported