diff options
Diffstat (limited to 'llvm/lib/Analysis/ValueTracking.cpp')
| -rw-r--r-- | llvm/lib/Analysis/ValueTracking.cpp | 1001 |
1 files changed, 597 insertions, 404 deletions
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index 2dd671b4ab9e..a13bdade320f 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -15,8 +15,6 @@ #include "llvm/ADT/APFloat.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/None.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" @@ -34,6 +32,7 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Analysis/VectorUtils.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" @@ -73,6 +72,7 @@ #include <algorithm> #include <cassert> #include <cstdint> +#include <optional> #include <utility> using namespace llvm; @@ -83,15 +83,6 @@ using namespace llvm::PatternMatch; static cl::opt<unsigned> DomConditionsMaxUses("dom-conditions-max-uses", cl::Hidden, cl::init(20)); -// According to the LangRef, branching on a poison condition is absolutely -// immediate full UB. However, historically we haven't implemented that -// consistently as we had an important transformation (non-trivial unswitch) -// which introduced instances of branch on poison/undef to otherwise well -// defined programs. This issue has since been fixed, but the flag is -// temporarily retained to easily diagnose potential regressions. -static cl::opt<bool> BranchOnPoisonAsUB("branch-on-poison-as-ub", - cl::Hidden, cl::init(true)); - /// Returns the bitwidth of the given scalar or pointer type. For vector types, /// returns the element type's bitwidth. @@ -166,39 +157,16 @@ static const Instruction *safeCxtI(const Value *V1, const Value *V2, const Instr static bool getShuffleDemandedElts(const ShuffleVectorInst *Shuf, const APInt &DemandedElts, APInt &DemandedLHS, APInt &DemandedRHS) { - // The length of scalable vectors is unknown at compile time, thus we - // cannot check their values - if (isa<ScalableVectorType>(Shuf->getType())) - return false; - - int NumElts = - cast<FixedVectorType>(Shuf->getOperand(0)->getType())->getNumElements(); - int NumMaskElts = cast<FixedVectorType>(Shuf->getType())->getNumElements(); - DemandedLHS = DemandedRHS = APInt::getZero(NumElts); - if (DemandedElts.isZero()) - return true; - // Simple case of a shuffle with zeroinitializer. - if (all_of(Shuf->getShuffleMask(), [](int Elt) { return Elt == 0; })) { - DemandedLHS.setBit(0); + if (isa<ScalableVectorType>(Shuf->getType())) { + assert(DemandedElts == APInt(1,1)); + DemandedLHS = DemandedRHS = DemandedElts; return true; } - for (int i = 0; i != NumMaskElts; ++i) { - if (!DemandedElts[i]) - continue; - int M = Shuf->getMaskValue(i); - assert(M < (NumElts * 2) && "Invalid shuffle mask constant"); - - // For undef elements, we don't know anything about the common state of - // the shuffle result. - if (M == -1) - return false; - if (M < NumElts) - DemandedLHS.setBit(M % NumElts); - else - DemandedRHS.setBit(M % NumElts); - } - return true; + int NumElts = + cast<FixedVectorType>(Shuf->getOperand(0)->getType())->getNumElements(); + return llvm::getShuffleDemandedElts(NumElts, Shuf->getShuffleMask(), + DemandedElts, DemandedLHS, DemandedRHS); } static void computeKnownBits(const Value *V, const APInt &DemandedElts, @@ -206,13 +174,9 @@ static void computeKnownBits(const Value *V, const APInt &DemandedElts, static void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Query &Q) { - // FIXME: We currently have no way to represent the DemandedElts of a scalable - // vector - if (isa<ScalableVectorType>(V->getType())) { - Known.resetAll(); - return; - } - + // Since the number of lanes in a scalable vector is unknown at compile time, + // we track one bit which is implicitly broadcast to all lanes. This means + // that all lanes in a scalable vector are considered demanded. auto *FVTy = dyn_cast<FixedVectorType>(V->getType()); APInt DemandedElts = FVTy ? APInt::getAllOnes(FVTy->getNumElements()) : APInt(1, 1); @@ -296,6 +260,15 @@ bool llvm::haveNoCommonBitsSet(const Value *LHS, const Value *RHS, match(LHS, m_c_Xor(m_c_And(m_Specific(RHS), m_Value(Y)), m_Deferred(Y)))) return true; + // Peek through extends to find a 'not' of the other side: + // (ext Y) op ext(~Y) + // (ext ~Y) op ext(Y) + if ((match(LHS, m_ZExtOrSExt(m_Value(Y))) && + match(RHS, m_ZExtOrSExt(m_Not(m_Specific(Y))))) || + (match(RHS, m_ZExtOrSExt(m_Value(Y))) && + match(LHS, m_ZExtOrSExt(m_Not(m_Specific(Y)))))) + return true; + // Look for: (A & B) op ~(A | B) { Value *A, *B; @@ -401,11 +374,6 @@ static unsigned ComputeNumSignBits(const Value *V, const APInt &DemandedElts, static unsigned ComputeNumSignBits(const Value *V, unsigned Depth, const Query &Q) { - // FIXME: We currently have no way to represent the DemandedElts of a scalable - // vector - if (isa<ScalableVectorType>(V->getType())) - return 1; - auto *FVTy = dyn_cast<FixedVectorType>(V->getType()); APInt DemandedElts = FVTy ? APInt::getAllOnes(FVTy->getNumElements()) : APInt(1, 1); @@ -648,7 +616,7 @@ static bool isKnownNonZeroFromAssume(const Value *V, const Query &Q) { for (auto &AssumeVH : Q.AC->assumptionsFor(V)) { if (!AssumeVH) continue; - CallInst *I = cast<CallInst>(AssumeVH); + CondGuardInst *I = cast<CondGuardInst>(AssumeVH); assert(I->getFunction() == Q.CxtI->getFunction() && "Got assumption for the wrong function!"); @@ -656,9 +624,6 @@ static bool isKnownNonZeroFromAssume(const Value *V, const Query &Q) { // We're running this loop for once for each value queried resulting in a // runtime of ~O(#assumes * #values). - assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume && - "must be an assume intrinsic"); - Value *RHS; CmpInst::Predicate Pred; auto m_V = m_CombineOr(m_Specific(V), m_PtrToInt(m_Specific(V))); @@ -696,7 +661,7 @@ static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known, for (auto &AssumeVH : Q.AC->assumptionsFor(V)) { if (!AssumeVH) continue; - CallInst *I = cast<CallInst>(AssumeVH); + CondGuardInst *I = cast<CondGuardInst>(AssumeVH); assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() && "Got assumption for the wrong function!"); @@ -704,9 +669,6 @@ static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known, // We're running this loop for once for each value queried resulting in a // runtime of ~O(#assumes * #values). - assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume && - "must be an assume intrinsic"); - Value *Arg = I->getArgOperand(0); if (Arg == V && isValidAssumeForContext(I, Q.CxtI, Q.DT)) { @@ -972,6 +934,14 @@ static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known, Known.Zero.setHighBits(RHSKnown.countMinLeadingZeros()); } break; + case ICmpInst::ICMP_NE: { + // assume (v & b != 0) where b is a power of 2 + const APInt *BPow2; + if (match(Cmp, m_ICmp(Pred, m_c_And(m_V, m_Power2(BPow2)), m_Zero())) && + isValidAssumeForContext(I, Q.CxtI, Q.DT)) { + Known.One |= BPow2->zextOrTrunc(BitWidth); + } + } break; } } @@ -1047,7 +1017,7 @@ static void computeKnownBitsFromShiftOperator( // If we know the shifter operand is nonzero, we can sometimes infer more // known bits. However this is expensive to compute, so be lazy about it and // only compute it when absolutely necessary. - Optional<bool> ShifterOperandIsNonZero; + std::optional<bool> ShifterOperandIsNonZero; // Early exit if we can't constrain any well-defined shift amount. if (!(ShiftAmtKZ & (PowerOf2Ceil(BitWidth) - 1)) && @@ -1200,7 +1170,7 @@ static void computeKnownBitsFromOperator(const Operator *I, case Instruction::PtrToInt: case Instruction::IntToPtr: // Fall through and handle them the same as zext/trunc. - LLVM_FALLTHROUGH; + [[fallthrough]]; case Instruction::ZExt: case Instruction::Trunc: { Type *SrcTy = I->getOperand(0)->getType(); @@ -1232,7 +1202,8 @@ static void computeKnownBitsFromOperator(const Operator *I, // Handle cast from vector integer type to scalar or vector integer. auto *SrcVecTy = dyn_cast<FixedVectorType>(SrcTy); if (!SrcVecTy || !SrcVecTy->getElementType()->isIntegerTy() || - !I->getType()->isIntOrIntVectorTy()) + !I->getType()->isIntOrIntVectorTy() || + isa<ScalableVectorType>(I->getType())) break; // Look through a cast from narrow vector elements to wider type. @@ -1398,7 +1369,7 @@ static void computeKnownBitsFromOperator(const Operator *I, KnownBits IndexBits(IndexBitWidth); computeKnownBits(Index, IndexBits, Depth + 1, Q); TypeSize IndexTypeSize = Q.DL.getTypeAllocSize(IndexedTy); - uint64_t TypeSizeInBytes = IndexTypeSize.getKnownMinSize(); + uint64_t TypeSizeInBytes = IndexTypeSize.getKnownMinValue(); KnownBits ScalingFactor(IndexBitWidth); // Multiply by current sizeof type. // &A[i] == A + i * sizeof(*A[i]). @@ -1575,9 +1546,45 @@ static void computeKnownBitsFromOperator(const Operator *I, RecQ.CxtI = P->getIncomingBlock(u)->getTerminator(); Known2 = KnownBits(BitWidth); + // Recurse, but cap the recursion to one level, because we don't // want to waste time spinning around in loops. computeKnownBits(IncValue, Known2, MaxAnalysisRecursionDepth - 1, RecQ); + + // If this failed, see if we can use a conditional branch into the phi + // to help us determine the range of the value. + if (Known2.isUnknown()) { + ICmpInst::Predicate Pred; + const APInt *RHSC; + BasicBlock *TrueSucc, *FalseSucc; + // TODO: Use RHS Value and compute range from its known bits. + if (match(RecQ.CxtI, + m_Br(m_c_ICmp(Pred, m_Specific(IncValue), m_APInt(RHSC)), + m_BasicBlock(TrueSucc), m_BasicBlock(FalseSucc)))) { + // Check for cases of duplicate successors. + if ((TrueSucc == P->getParent()) != (FalseSucc == P->getParent())) { + // If we're using the false successor, invert the predicate. + if (FalseSucc == P->getParent()) + Pred = CmpInst::getInversePredicate(Pred); + + switch (Pred) { + case CmpInst::Predicate::ICMP_EQ: + Known2 = KnownBits::makeConstant(*RHSC); + break; + case CmpInst::Predicate::ICMP_ULE: + Known2.Zero.setHighBits(RHSC->countLeadingZeros()); + break; + case CmpInst::Predicate::ICMP_ULT: + Known2.Zero.setHighBits((*RHSC - 1).countLeadingZeros()); + break; + default: + // TODO - add additional integer predicate handling. + break; + } + } + } + } + Known = KnownBits::commonBits(Known, Known2); // If all bits have been ruled out, there's no need to check // more operands. @@ -1626,7 +1633,7 @@ static void computeKnownBitsFromOperator(const Operator *I, // If this call is poison for 0 input, the result will be less than 2^n. if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext())) PossibleLZ = std::min(PossibleLZ, BitWidth - 1); - unsigned LowBits = Log2_32(PossibleLZ)+1; + unsigned LowBits = llvm::bit_width(PossibleLZ); Known.Zero.setBitsFrom(LowBits); break; } @@ -1637,7 +1644,7 @@ static void computeKnownBitsFromOperator(const Operator *I, // If this call is poison for 0 input, the result will be less than 2^n. if (II->getArgOperand(1) == ConstantInt::getTrue(II->getContext())) PossibleTZ = std::min(PossibleTZ, BitWidth - 1); - unsigned LowBits = Log2_32(PossibleTZ)+1; + unsigned LowBits = llvm::bit_width(PossibleTZ); Known.Zero.setBitsFrom(LowBits); break; } @@ -1646,7 +1653,7 @@ static void computeKnownBitsFromOperator(const Operator *I, // We can bound the space the count needs. Also, bits known to be zero // can't contribute to the population. unsigned BitsPossiblySet = Known2.countMaxPopulation(); - unsigned LowBits = Log2_32(BitsPossiblySet)+1; + unsigned LowBits = llvm::bit_width(BitsPossiblySet); Known.Zero.setBitsFrom(LowBits); // TODO: we could bound KnownOne using the lower bound on the number // of bits which might be set provided by popcnt KnownOne2. @@ -1740,7 +1747,7 @@ static void computeKnownBitsFromOperator(const Operator *I, break; auto Attr = II->getFunction()->getFnAttribute(Attribute::VScaleRange); - Optional<unsigned> VScaleMax = Attr.getVScaleRangeMax(); + std::optional<unsigned> VScaleMax = Attr.getVScaleRangeMax(); if (!VScaleMax) break; @@ -1756,7 +1763,7 @@ static void computeKnownBitsFromOperator(const Operator *I, break; } - unsigned FirstZeroHighBit = 32 - countLeadingZeros(*VScaleMax); + unsigned FirstZeroHighBit = llvm::bit_width(*VScaleMax); if (FirstZeroHighBit < BitWidth) Known.Zero.setBitsFrom(FirstZeroHighBit); @@ -1796,6 +1803,10 @@ static void computeKnownBitsFromOperator(const Operator *I, break; } case Instruction::InsertElement: { + if (isa<ScalableVectorType>(I->getType())) { + Known.resetAll(); + return; + } const Value *Vec = I->getOperand(0); const Value *Elt = I->getOperand(1); auto *CIdx = dyn_cast<ConstantInt>(I->getOperand(2)); @@ -1912,9 +1923,8 @@ KnownBits computeKnownBits(const Value *V, unsigned Depth, const Query &Q) { /// for all of the demanded elements in the vector specified by DemandedElts. void computeKnownBits(const Value *V, const APInt &DemandedElts, KnownBits &Known, unsigned Depth, const Query &Q) { - if (!DemandedElts || isa<ScalableVectorType>(V->getType())) { - // No demanded elts or V is a scalable vector, better to assume we don't - // know anything. + if (!DemandedElts) { + // No demanded elts, better to assume we don't know anything. Known.resetAll(); return; } @@ -1935,7 +1945,7 @@ void computeKnownBits(const Value *V, const APInt &DemandedElts, "DemandedElt width should equal the fixed vector number of elements"); } else { assert(DemandedElts == APInt(1, 1) && - "DemandedElt width should be 1 for scalars"); + "DemandedElt width should be 1 for scalars or scalable vectors"); } Type *ScalarTy = Ty->getScalarType(); @@ -1962,6 +1972,7 @@ void computeKnownBits(const Value *V, const APInt &DemandedElts, // Handle a constant vector by taking the intersection of the known bits of // each element. if (const ConstantDataVector *CDV = dyn_cast<ConstantDataVector>(V)) { + assert(!isa<ScalableVectorType>(V->getType())); // We know that CDV must be a vector of integers. Take the intersection of // each element. Known.Zero.setAllBits(); Known.One.setAllBits(); @@ -1976,6 +1987,7 @@ void computeKnownBits(const Value *V, const APInt &DemandedElts, } if (const auto *CV = dyn_cast<ConstantVector>(V)) { + assert(!isa<ScalableVectorType>(V->getType())); // We know that CV must be a vector of integers. Take the intersection of // each element. Known.Zero.setAllBits(); Known.One.setAllBits(); @@ -2073,7 +2085,7 @@ static bool isPowerOfTwoRecurrence(const PHINode *PN, bool OrZero, // power of two is not sufficient, and it has to be a constant. if (!match(Start, m_Power2()) || match(Start, m_SignMask())) return false; - LLVM_FALLTHROUGH; + [[fallthrough]]; case Instruction::UDiv: // Divisor must be a power of two. // If OrZero is false, cannot guarantee induction variable is non-zero after @@ -2085,7 +2097,7 @@ static bool isPowerOfTwoRecurrence(const PHINode *PN, bool OrZero, case Instruction::AShr: if (!match(Start, m_Power2()) || match(Start, m_SignMask())) return false; - LLVM_FALLTHROUGH; + [[fallthrough]]; case Instruction::LShr: return OrZero || Q.IIQ.isExact(BO); default: @@ -2261,7 +2273,7 @@ static bool isGEPKnownNonNull(const GEPOperator *GEP, unsigned Depth, } // If we have a zero-sized type, the index doesn't matter. Keep looping. - if (Q.DL.getTypeAllocSize(GTI.getIndexedType()).getKnownMinSize() == 0) + if (Q.DL.getTypeAllocSize(GTI.getIndexedType()).isZero()) continue; // Fast path the constant operand case both for efficiency and so we don't @@ -2433,10 +2445,20 @@ static bool isNonZeroRecurrence(const PHINode *PN) { /// Supports values with integer or pointer type and vectors of integers. bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, const Query &Q) { - // FIXME: We currently have no way to represent the DemandedElts of a scalable - // vector - if (isa<ScalableVectorType>(V->getType())) - return false; + +#ifndef NDEBUG + Type *Ty = V->getType(); + assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth"); + + if (auto *FVTy = dyn_cast<FixedVectorType>(Ty)) { + assert( + FVTy->getNumElements() == DemandedElts.getBitWidth() && + "DemandedElt width should equal the fixed vector number of elements"); + } else { + assert(DemandedElts == APInt(1, 1) && + "DemandedElt width should be 1 for scalars"); + } +#endif if (auto *C = dyn_cast<Constant>(V)) { if (C->isNullValue()) @@ -2445,16 +2467,6 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, // Must be non-zero due to null test above. return true; - if (auto *CE = dyn_cast<ConstantExpr>(C)) { - // See the comment for IntToPtr/PtrToInt instructions below. - if (CE->getOpcode() == Instruction::IntToPtr || - CE->getOpcode() == Instruction::PtrToInt) - if (Q.DL.getTypeSizeInBits(CE->getOperand(0)->getType()) - .getFixedSize() <= - Q.DL.getTypeSizeInBits(CE->getType()).getFixedSize()) - return isKnownNonZero(CE->getOperand(0), Depth, Q); - } - // For constant vectors, check that all elements are undefined or known // non-zero to determine that the whole vector is known non-zero. if (auto *VecTy = dyn_cast<FixedVectorType>(C->getType())) { @@ -2477,7 +2489,10 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, if (!GV->isAbsoluteSymbolRef() && !GV->hasExternalWeakLinkage() && GV->getType()->getAddressSpace() == 0) return true; - } else + } + + // For constant expressions, fall through to the Operator code below. + if (!isa<ConstantExpr>(V)) return false; } @@ -2493,7 +2508,7 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, } } - if (isKnownNonZeroFromAssume(V, Q)) + if (!isa<Constant>(V) && isKnownNonZeroFromAssume(V, Q)) return true; // Some of the tests below are recursive, so bail out if we hit the limit. @@ -2529,101 +2544,110 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, } } - if (isKnownNonNullFromDominatingCondition(V, Q.CxtI, Q.DT)) + if (!isa<Constant>(V) && + isKnownNonNullFromDominatingCondition(V, Q.CxtI, Q.DT)) return true; - // Check for recursive pointer simplifications. - if (V->getType()->isPointerTy()) { - // Look through bitcast operations, GEPs, and int2ptr instructions as they - // do not alter the value, or at least not the nullness property of the - // value, e.g., int2ptr is allowed to zero/sign extend the value. - // + const Operator *I = dyn_cast<Operator>(V); + if (!I) + return false; + + unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), Q.DL); + switch (I->getOpcode()) { + case Instruction::GetElementPtr: + if (I->getType()->isPointerTy()) + return isGEPKnownNonNull(cast<GEPOperator>(I), Depth, Q); + break; + case Instruction::BitCast: + if (I->getType()->isPointerTy()) + return isKnownNonZero(I->getOperand(0), Depth, Q); + break; + case Instruction::IntToPtr: // Note that we have to take special care to avoid looking through // truncating casts, e.g., int2ptr/ptr2int with appropriate sizes, as well // as casts that can alter the value, e.g., AddrSpaceCasts. - if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) - return isGEPKnownNonNull(GEP, Depth, Q); - - if (auto *BCO = dyn_cast<BitCastOperator>(V)) - return isKnownNonZero(BCO->getOperand(0), Depth, Q); - - if (auto *I2P = dyn_cast<IntToPtrInst>(V)) - if (Q.DL.getTypeSizeInBits(I2P->getSrcTy()).getFixedSize() <= - Q.DL.getTypeSizeInBits(I2P->getDestTy()).getFixedSize()) - return isKnownNonZero(I2P->getOperand(0), Depth, Q); - } - - // Similar to int2ptr above, we can look through ptr2int here if the cast - // is a no-op or an extend and not a truncate. - if (auto *P2I = dyn_cast<PtrToIntInst>(V)) - if (Q.DL.getTypeSizeInBits(P2I->getSrcTy()).getFixedSize() <= - Q.DL.getTypeSizeInBits(P2I->getDestTy()).getFixedSize()) - return isKnownNonZero(P2I->getOperand(0), Depth, Q); - - unsigned BitWidth = getBitWidth(V->getType()->getScalarType(), Q.DL); - - // X | Y != 0 if X != 0 or Y != 0. - Value *X = nullptr, *Y = nullptr; - if (match(V, m_Or(m_Value(X), m_Value(Y)))) - return isKnownNonZero(X, DemandedElts, Depth, Q) || - isKnownNonZero(Y, DemandedElts, Depth, Q); - - // ext X != 0 if X != 0. - if (isa<SExtInst>(V) || isa<ZExtInst>(V)) - return isKnownNonZero(cast<Instruction>(V)->getOperand(0), Depth, Q); + if (!isa<ScalableVectorType>(I->getType()) && + Q.DL.getTypeSizeInBits(I->getOperand(0)->getType()).getFixedValue() <= + Q.DL.getTypeSizeInBits(I->getType()).getFixedValue()) + return isKnownNonZero(I->getOperand(0), Depth, Q); + break; + case Instruction::PtrToInt: + // Similar to int2ptr above, we can look through ptr2int here if the cast + // is a no-op or an extend and not a truncate. + if (!isa<ScalableVectorType>(I->getType()) && + Q.DL.getTypeSizeInBits(I->getOperand(0)->getType()).getFixedValue() <= + Q.DL.getTypeSizeInBits(I->getType()).getFixedValue()) + return isKnownNonZero(I->getOperand(0), Depth, Q); + break; + case Instruction::Or: + // X | Y != 0 if X != 0 or Y != 0. + return isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q) || + isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q); + case Instruction::SExt: + case Instruction::ZExt: + // ext X != 0 if X != 0. + return isKnownNonZero(I->getOperand(0), Depth, Q); - // shl X, Y != 0 if X is odd. Note that the value of the shift is undefined - // if the lowest bit is shifted off the end. - if (match(V, m_Shl(m_Value(X), m_Value(Y)))) { + case Instruction::Shl: { // shl nuw can't remove any non-zero bits. const OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); if (Q.IIQ.hasNoUnsignedWrap(BO)) - return isKnownNonZero(X, Depth, Q); + return isKnownNonZero(I->getOperand(0), Depth, Q); + // shl X, Y != 0 if X is odd. Note that the value of the shift is undefined + // if the lowest bit is shifted off the end. KnownBits Known(BitWidth); - computeKnownBits(X, DemandedElts, Known, Depth, Q); + computeKnownBits(I->getOperand(0), DemandedElts, Known, Depth, Q); if (Known.One[0]) return true; + break; } - // shr X, Y != 0 if X is negative. Note that the value of the shift is not - // defined if the sign bit is shifted off the end. - else if (match(V, m_Shr(m_Value(X), m_Value(Y)))) { + case Instruction::LShr: + case Instruction::AShr: { // shr exact can only shift out zero bits. const PossiblyExactOperator *BO = cast<PossiblyExactOperator>(V); if (BO->isExact()) - return isKnownNonZero(X, Depth, Q); + return isKnownNonZero(I->getOperand(0), Depth, Q); - KnownBits Known = computeKnownBits(X, DemandedElts, Depth, Q); + // shr X, Y != 0 if X is negative. Note that the value of the shift is not + // defined if the sign bit is shifted off the end. + KnownBits Known = + computeKnownBits(I->getOperand(0), DemandedElts, Depth, Q); if (Known.isNegative()) return true; // If the shifter operand is a constant, and all of the bits shifted // out are known to be zero, and X is known non-zero then at least one // non-zero bit must remain. - if (ConstantInt *Shift = dyn_cast<ConstantInt>(Y)) { + if (ConstantInt *Shift = dyn_cast<ConstantInt>(I->getOperand(1))) { auto ShiftVal = Shift->getLimitedValue(BitWidth - 1); // Is there a known one in the portion not shifted out? if (Known.countMaxLeadingZeros() < BitWidth - ShiftVal) return true; // Are all the bits to be shifted out known zero? if (Known.countMinTrailingZeros() >= ShiftVal) - return isKnownNonZero(X, DemandedElts, Depth, Q); + return isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q); } + break; } - // div exact can only produce a zero if the dividend is zero. - else if (match(V, m_Exact(m_IDiv(m_Value(X), m_Value())))) { - return isKnownNonZero(X, DemandedElts, Depth, Q); - } - // X + Y. - else if (match(V, m_Add(m_Value(X), m_Value(Y)))) { - KnownBits XKnown = computeKnownBits(X, DemandedElts, Depth, Q); - KnownBits YKnown = computeKnownBits(Y, DemandedElts, Depth, Q); + case Instruction::UDiv: + case Instruction::SDiv: + // div exact can only produce a zero if the dividend is zero. + if (cast<PossiblyExactOperator>(I)->isExact()) + return isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q); + break; + case Instruction::Add: { + // X + Y. + KnownBits XKnown = + computeKnownBits(I->getOperand(0), DemandedElts, Depth, Q); + KnownBits YKnown = + computeKnownBits(I->getOperand(1), DemandedElts, Depth, Q); // If X and Y are both non-negative (as signed values) then their sum is not // zero unless both X and Y are zero. if (XKnown.isNonNegative() && YKnown.isNonNegative()) - if (isKnownNonZero(X, DemandedElts, Depth, Q) || - isKnownNonZero(Y, DemandedElts, Depth, Q)) + if (isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q) || + isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q)) return true; // If X and Y are both negative (as signed values) then their sum is not @@ -2642,30 +2666,31 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, // The sum of a non-negative number and a power of two is not zero. if (XKnown.isNonNegative() && - isKnownToBeAPowerOfTwo(Y, /*OrZero*/ false, Depth, Q)) + isKnownToBeAPowerOfTwo(I->getOperand(1), /*OrZero*/ false, Depth, Q)) return true; if (YKnown.isNonNegative() && - isKnownToBeAPowerOfTwo(X, /*OrZero*/ false, Depth, Q)) + isKnownToBeAPowerOfTwo(I->getOperand(0), /*OrZero*/ false, Depth, Q)) return true; + break; } - // X * Y. - else if (match(V, m_Mul(m_Value(X), m_Value(Y)))) { - const OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); + case Instruction::Mul: { // If X and Y are non-zero then so is X * Y as long as the multiplication // does not overflow. + const OverflowingBinaryOperator *BO = cast<OverflowingBinaryOperator>(V); if ((Q.IIQ.hasNoSignedWrap(BO) || Q.IIQ.hasNoUnsignedWrap(BO)) && - isKnownNonZero(X, DemandedElts, Depth, Q) && - isKnownNonZero(Y, DemandedElts, Depth, Q)) + isKnownNonZero(I->getOperand(0), DemandedElts, Depth, Q) && + isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q)) return true; + break; } - // (C ? X : Y) != 0 if X != 0 and Y != 0. - else if (const SelectInst *SI = dyn_cast<SelectInst>(V)) { - if (isKnownNonZero(SI->getTrueValue(), DemandedElts, Depth, Q) && - isKnownNonZero(SI->getFalseValue(), DemandedElts, Depth, Q)) + case Instruction::Select: + // (C ? X : Y) != 0 if X != 0 and Y != 0. + if (isKnownNonZero(I->getOperand(1), DemandedElts, Depth, Q) && + isKnownNonZero(I->getOperand(2), DemandedElts, Depth, Q)) return true; - } - // PHI - else if (const PHINode *PN = dyn_cast<PHINode>(V)) { + break; + case Instruction::PHI: { + auto *PN = cast<PHINode>(I); if (Q.IIQ.UseInstrInfo && isNonZeroRecurrence(PN)) return true; @@ -2679,28 +2704,28 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, return isKnownNonZero(U.get(), DemandedElts, NewDepth, RecQ); }); } - // ExtractElement - else if (const auto *EEI = dyn_cast<ExtractElementInst>(V)) { - const Value *Vec = EEI->getVectorOperand(); - const Value *Idx = EEI->getIndexOperand(); - auto *CIdx = dyn_cast<ConstantInt>(Idx); - if (auto *VecTy = dyn_cast<FixedVectorType>(Vec->getType())) { - unsigned NumElts = VecTy->getNumElements(); - APInt DemandedVecElts = APInt::getAllOnes(NumElts); - if (CIdx && CIdx->getValue().ult(NumElts)) - DemandedVecElts = APInt::getOneBitSet(NumElts, CIdx->getZExtValue()); - return isKnownNonZero(Vec, DemandedVecElts, Depth, Q); - } - } - // Freeze - else if (const FreezeInst *FI = dyn_cast<FreezeInst>(V)) { - auto *Op = FI->getOperand(0); - if (isKnownNonZero(Op, Depth, Q) && - isGuaranteedNotToBePoison(Op, Q.AC, Q.CxtI, Q.DT, Depth)) - return true; - } else if (const auto *II = dyn_cast<IntrinsicInst>(V)) { - if (II->getIntrinsicID() == Intrinsic::vscale) + case Instruction::ExtractElement: + if (const auto *EEI = dyn_cast<ExtractElementInst>(V)) { + const Value *Vec = EEI->getVectorOperand(); + const Value *Idx = EEI->getIndexOperand(); + auto *CIdx = dyn_cast<ConstantInt>(Idx); + if (auto *VecTy = dyn_cast<FixedVectorType>(Vec->getType())) { + unsigned NumElts = VecTy->getNumElements(); + APInt DemandedVecElts = APInt::getAllOnes(NumElts); + if (CIdx && CIdx->getValue().ult(NumElts)) + DemandedVecElts = APInt::getOneBitSet(NumElts, CIdx->getZExtValue()); + return isKnownNonZero(Vec, DemandedVecElts, Depth, Q); + } + } + break; + case Instruction::Freeze: + return isKnownNonZero(I->getOperand(0), Depth, Q) && + isGuaranteedNotToBePoison(I->getOperand(0), Q.AC, Q.CxtI, Q.DT, + Depth); + case Instruction::Call: + if (cast<CallInst>(I)->getIntrinsicID() == Intrinsic::vscale) return true; + break; } KnownBits Known(BitWidth); @@ -2709,11 +2734,6 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, } bool isKnownNonZero(const Value* V, unsigned Depth, const Query& Q) { - // FIXME: We currently have no way to represent the DemandedElts of a scalable - // vector - if (isa<ScalableVectorType>(V->getType())) - return false; - auto *FVTy = dyn_cast<FixedVectorType>(V->getType()); APInt DemandedElts = FVTy ? APInt::getAllOnes(FVTy->getNumElements()) : APInt(1, 1); @@ -2722,15 +2742,15 @@ bool isKnownNonZero(const Value* V, unsigned Depth, const Query& Q) { /// If the pair of operators are the same invertible function, return the /// the operands of the function corresponding to each input. Otherwise, -/// return None. An invertible function is one that is 1-to-1 and maps +/// return std::nullopt. An invertible function is one that is 1-to-1 and maps /// every input value to exactly one output value. This is equivalent to /// saying that Op1 and Op2 are equal exactly when the specified pair of /// operands are equal, (except that Op1 and Op2 may be poison more often.) -static Optional<std::pair<Value*, Value*>> +static std::optional<std::pair<Value*, Value*>> getInvertibleOperands(const Operator *Op1, const Operator *Op2) { if (Op1->getOpcode() != Op2->getOpcode()) - return None; + return std::nullopt; auto getOperands = [&](unsigned OpNum) -> auto { return std::make_pair(Op1->getOperand(OpNum), Op2->getOperand(OpNum)); @@ -2824,7 +2844,7 @@ getInvertibleOperands(const Operator *Op1, return std::make_pair(Start1, Start2); } } - return None; + return std::nullopt; } /// Return true if V2 == V1 + X, where X is known non-zero. @@ -3065,12 +3085,6 @@ static unsigned ComputeNumSignBitsImpl(const Value *V, const APInt &DemandedElts, unsigned Depth, const Query &Q) { Type *Ty = V->getType(); - - // FIXME: We currently have no way to represent the DemandedElts of a scalable - // vector - if (isa<ScalableVectorType>(Ty)) - return 1; - #ifndef NDEBUG assert(Depth <= MaxAnalysisRecursionDepth && "Limit Search Depth"); @@ -3300,10 +3314,17 @@ static unsigned ComputeNumSignBitsImpl(const Value *V, return Tmp; } - case Instruction::Trunc: - // FIXME: it's tricky to do anything useful for this, but it is an - // important case for targets like X86. - break; + case Instruction::Trunc: { + // If the input contained enough sign bits that some remain after the + // truncation, then we can make use of that. Otherwise we don't know + // anything. + Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q); + unsigned OperandTyBits = U->getOperand(0)->getType()->getScalarSizeInBits(); + if (Tmp > (OperandTyBits - TyBits)) + return Tmp - (OperandTyBits - TyBits); + + return 1; + } case Instruction::ExtractElement: // Look through extract element. At the moment we keep this simple and @@ -3593,15 +3614,24 @@ static bool cannotBeOrderedLessThanZeroImpl(const Value *V, // Unsigned integers are always nonnegative. case Instruction::UIToFP: return true; - case Instruction::FMul: case Instruction::FDiv: - // X * X is always non-negative or a NaN. // X / X is always exactly 1.0 or a NaN. if (I->getOperand(0) == I->getOperand(1) && (!SignBitOnly || cast<FPMathOperator>(I)->hasNoNaNs())) return true; - LLVM_FALLTHROUGH; + // Set SignBitOnly for RHS, because X / -0.0 is -Inf (or NaN). + return cannotBeOrderedLessThanZeroImpl(I->getOperand(0), TLI, SignBitOnly, + Depth + 1) && + cannotBeOrderedLessThanZeroImpl(I->getOperand(1), TLI, + /*SignBitOnly*/ true, Depth + 1); + case Instruction::FMul: + // X * X is always non-negative or a NaN. + if (I->getOperand(0) == I->getOperand(1) && + (!SignBitOnly || cast<FPMathOperator>(I)->hasNoNaNs())) + return true; + + [[fallthrough]]; case Instruction::FAdd: case Instruction::FRem: return cannotBeOrderedLessThanZeroImpl(I->getOperand(0), TLI, SignBitOnly, @@ -3630,6 +3660,17 @@ static bool cannotBeOrderedLessThanZeroImpl(const Value *V, switch (IID) { default: break; + case Intrinsic::canonicalize: + case Intrinsic::arithmetic_fence: + case Intrinsic::floor: + case Intrinsic::ceil: + case Intrinsic::trunc: + case Intrinsic::rint: + case Intrinsic::nearbyint: + case Intrinsic::round: + case Intrinsic::roundeven: + case Intrinsic::fptrunc_round: + return cannotBeOrderedLessThanZeroImpl(I->getOperand(0), TLI, SignBitOnly, Depth + 1); case Intrinsic::maxnum: { Value *V0 = I->getOperand(0), *V1 = I->getOperand(1); auto isPositiveNum = [&](Value *V) { @@ -3668,7 +3709,10 @@ static bool cannotBeOrderedLessThanZeroImpl(const Value *V, case Intrinsic::exp2: case Intrinsic::fabs: return true; - + case Intrinsic::copysign: + // Only the sign operand matters. + return cannotBeOrderedLessThanZeroImpl(I->getOperand(1), TLI, true, + Depth + 1); case Intrinsic::sqrt: // sqrt(x) is always >= -0 or NaN. Moreover, sqrt(x) == -0 iff x == -0. if (!SignBitOnly) @@ -3756,9 +3800,73 @@ bool llvm::isKnownNeverInfinity(const Value *V, const TargetLibraryInfo *TLI, Type *FPTy = Inst->getType()->getScalarType(); return ilogb(APFloat::getLargest(FPTy->getFltSemantics())) >= IntSize; } + case Instruction::FNeg: + case Instruction::FPExt: { + // Peek through to source op. If it is not infinity, this is not infinity. + return isKnownNeverInfinity(Inst->getOperand(0), TLI, Depth + 1); + } + case Instruction::FPTrunc: { + // Need a range check. + return false; + } default: break; } + + if (const auto *II = dyn_cast<IntrinsicInst>(V)) { + switch (II->getIntrinsicID()) { + case Intrinsic::sin: + case Intrinsic::cos: + // Return NaN on infinite inputs. + return true; + case Intrinsic::fabs: + case Intrinsic::sqrt: + case Intrinsic::canonicalize: + case Intrinsic::copysign: + case Intrinsic::arithmetic_fence: + case Intrinsic::trunc: + return isKnownNeverInfinity(Inst->getOperand(0), TLI, Depth + 1); + case Intrinsic::floor: + case Intrinsic::ceil: + case Intrinsic::rint: + case Intrinsic::nearbyint: + case Intrinsic::round: + case Intrinsic::roundeven: + // PPC_FP128 is a special case. + if (V->getType()->isMultiUnitFPType()) + return false; + return isKnownNeverInfinity(Inst->getOperand(0), TLI, Depth + 1); + case Intrinsic::fptrunc_round: + // Requires knowing the value range. + return false; + case Intrinsic::minnum: + case Intrinsic::maxnum: + case Intrinsic::minimum: + case Intrinsic::maximum: + return isKnownNeverInfinity(Inst->getOperand(0), TLI, Depth + 1) && + isKnownNeverInfinity(Inst->getOperand(1), TLI, Depth + 1); + case Intrinsic::log: + case Intrinsic::log10: + case Intrinsic::log2: + // log(+inf) -> +inf + // log([+-]0.0) -> -inf + // log(-inf) -> nan + // log(-x) -> nan + // TODO: We lack API to check the == 0 case. + return false; + case Intrinsic::exp: + case Intrinsic::exp2: + case Intrinsic::pow: + case Intrinsic::powi: + case Intrinsic::fma: + case Intrinsic::fmuladd: + // These can return infinities on overflow cases, so it's hard to prove + // anything about it. + return false; + default: + break; + } + } } // try to handle fixed width vector constants @@ -3832,6 +3940,7 @@ bool llvm::isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI, return true; case Instruction::FPTrunc: case Instruction::FPExt: + case Instruction::FNeg: return isKnownNeverNaN(Inst->getOperand(0), TLI, Depth + 1); default: break; @@ -3852,6 +3961,7 @@ bool llvm::isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI, case Intrinsic::nearbyint: case Intrinsic::round: case Intrinsic::roundeven: + case Intrinsic::arithmetic_fence: return isKnownNeverNaN(II->getArgOperand(0), TLI, Depth + 1); case Intrinsic::sqrt: return isKnownNeverNaN(II->getArgOperand(0), TLI, Depth + 1) && @@ -4039,8 +4149,8 @@ static Value *BuildSubAggregate(Value *From, Value* To, Type *IndexedType, return nullptr; // Insert the value in the new (sub) aggregate - return InsertValueInst::Create(To, V, makeArrayRef(Idxs).slice(IdxSkip), - "tmp", InsertBefore); + return InsertValueInst::Create(To, V, ArrayRef(Idxs).slice(IdxSkip), "tmp", + InsertBefore); } // This helper takes a nested struct and extracts a part of it (which is again a @@ -4060,7 +4170,7 @@ static Value *BuildSubAggregate(Value *From, ArrayRef<unsigned> idx_range, assert(InsertBefore && "Must have someplace to insert!"); Type *IndexedType = ExtractValueInst::getIndexedType(From->getType(), idx_range); - Value *To = UndefValue::get(IndexedType); + Value *To = PoisonValue::get(IndexedType); SmallVector<unsigned, 10> Idxs(idx_range.begin(), idx_range.end()); unsigned IdxSkip = Idxs.size(); @@ -4112,7 +4222,7 @@ Value *llvm::FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range, // %C = insertvalue {i32, i32 } %A, i32 11, 1 // which allows the unused 0,0 element from the nested struct to be // removed. - return BuildSubAggregate(V, makeArrayRef(idx_range.begin(), req_idx), + return BuildSubAggregate(V, ArrayRef(idx_range.begin(), req_idx), InsertBefore); } @@ -4127,8 +4237,7 @@ Value *llvm::FindInsertedValue(Value *V, ArrayRef<unsigned> idx_range, // requested (though possibly only partially). Now we recursively look at // the inserted value, passing any remaining indices. return FindInsertedValue(I->getInsertedValueOperand(), - makeArrayRef(req_idx, idx_range.end()), - InsertBefore); + ArrayRef(req_idx, idx_range.end()), InsertBefore); } if (ExtractValueInst *I = dyn_cast<ExtractValueInst>(V)) { @@ -4182,10 +4291,14 @@ bool llvm::isGEPBasedOnPointerToString(const GEPOperator *GEP, // its initializer if the size of its elements equals ElementSize, or, // for ElementSize == 8, to its representation as an array of unsiged // char. Return true on success. +// Offset is in the unit "nr of ElementSize sized elements". bool llvm::getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice, unsigned ElementSize, uint64_t Offset) { - assert(V); + assert(V && "V should not be null."); + assert((ElementSize % 8) == 0 && + "ElementSize expected to be a multiple of the size of a byte."); + unsigned ElementSizeInBytes = ElementSize / 8; // Drill down into the pointer expression V, ignoring any intervening // casts, and determine the identity of the object it references along @@ -4209,15 +4322,19 @@ bool llvm::getConstantDataArrayInfo(const Value *V, // Fail if the constant offset is excessive. return false; - Offset += StartIdx; + // Off/StartIdx is in the unit of bytes. So we need to convert to number of + // elements. Simply bail out if that isn't possible. + if ((StartIdx % ElementSizeInBytes) != 0) + return false; + Offset += StartIdx / ElementSizeInBytes; ConstantDataArray *Array = nullptr; ArrayType *ArrayTy = nullptr; if (GV->getInitializer()->isNullValue()) { Type *GVTy = GV->getValueType(); - uint64_t SizeInBytes = DL.getTypeStoreSize(GVTy).getFixedSize(); - uint64_t Length = SizeInBytes / (ElementSize / 8); + uint64_t SizeInBytes = DL.getTypeStoreSize(GVTy).getFixedValue(); + uint64_t Length = SizeInBytes / ElementSizeInBytes; Slice.Array = nullptr; Slice.Offset = 0; @@ -4271,9 +4388,9 @@ bool llvm::getConstantDataArrayInfo(const Value *V, /// return true. When TrimAtNul is set, Str will contain only the bytes up /// to but not including the first nul. Return false on failure. bool llvm::getConstantStringInfo(const Value *V, StringRef &Str, - uint64_t Offset, bool TrimAtNul) { + bool TrimAtNul) { ConstantDataArraySlice Slice; - if (!getConstantDataArrayInfo(V, Slice, 8, Offset)) + if (!getConstantDataArrayInfo(V, Slice, 8)) return false; if (Slice.Array == nullptr) { @@ -4682,15 +4799,17 @@ bool llvm::mustSuppressSpeculation(const LoadInst &LI) { bool llvm::isSafeToSpeculativelyExecute(const Instruction *Inst, const Instruction *CtxI, + AssumptionCache *AC, const DominatorTree *DT, const TargetLibraryInfo *TLI) { return isSafeToSpeculativelyExecuteWithOpcode(Inst->getOpcode(), Inst, CtxI, - DT, TLI); + AC, DT, TLI); } bool llvm::isSafeToSpeculativelyExecuteWithOpcode( unsigned Opcode, const Instruction *Inst, const Instruction *CtxI, - const DominatorTree *DT, const TargetLibraryInfo *TLI) { + AssumptionCache *AC, const DominatorTree *DT, + const TargetLibraryInfo *TLI) { #ifndef NDEBUG if (Inst->getOpcode() != Opcode) { // Check that the operands are actually compatible with the Opcode override. @@ -4748,9 +4867,9 @@ bool llvm::isSafeToSpeculativelyExecuteWithOpcode( if (mustSuppressSpeculation(*LI)) return false; const DataLayout &DL = LI->getModule()->getDataLayout(); - return isDereferenceableAndAlignedPointer( - LI->getPointerOperand(), LI->getType(), LI->getAlign(), DL, CtxI, DT, - TLI); + return isDereferenceableAndAlignedPointer(LI->getPointerOperand(), + LI->getType(), LI->getAlign(), DL, + CtxI, AC, DT, TLI); } case Instruction::Call: { auto *CI = dyn_cast<const CallInst>(Inst); @@ -5085,10 +5204,35 @@ bool llvm::isOverflowIntrinsicNoWrap(const WithOverflowInst *WO, return llvm::any_of(GuardingBranches, AllUsesGuardedByBranch); } +/// Shifts return poison if shiftwidth is larger than the bitwidth. +static bool shiftAmountKnownInRange(const Value *ShiftAmount) { + auto *C = dyn_cast<Constant>(ShiftAmount); + if (!C) + return false; + + // Shifts return poison if shiftwidth is larger than the bitwidth. + SmallVector<const Constant *, 4> ShiftAmounts; + if (auto *FVTy = dyn_cast<FixedVectorType>(C->getType())) { + unsigned NumElts = FVTy->getNumElements(); + for (unsigned i = 0; i < NumElts; ++i) + ShiftAmounts.push_back(C->getAggregateElement(i)); + } else if (isa<ScalableVectorType>(C->getType())) + return false; // Can't tell, just return false to be safe + else + ShiftAmounts.push_back(C); + + bool Safe = llvm::all_of(ShiftAmounts, [](const Constant *C) { + auto *CI = dyn_cast_or_null<ConstantInt>(C); + return CI && CI->getValue().ult(C->getType()->getIntegerBitWidth()); + }); + + return Safe; +} + static bool canCreateUndefOrPoison(const Operator *Op, bool PoisonOnly, - bool ConsiderFlags) { + bool ConsiderFlagsAndMetadata) { - if (ConsiderFlags && Op->hasPoisonGeneratingFlags()) + if (ConsiderFlagsAndMetadata && Op->hasPoisonGeneratingFlagsOrMetadata()) return true; unsigned Opcode = Op->getOpcode(); @@ -5097,27 +5241,8 @@ static bool canCreateUndefOrPoison(const Operator *Op, bool PoisonOnly, switch (Opcode) { case Instruction::Shl: case Instruction::AShr: - case Instruction::LShr: { - // Shifts return poison if shiftwidth is larger than the bitwidth. - if (auto *C = dyn_cast<Constant>(Op->getOperand(1))) { - SmallVector<Constant *, 4> ShiftAmounts; - if (auto *FVTy = dyn_cast<FixedVectorType>(C->getType())) { - unsigned NumElts = FVTy->getNumElements(); - for (unsigned i = 0; i < NumElts; ++i) - ShiftAmounts.push_back(C->getAggregateElement(i)); - } else if (isa<ScalableVectorType>(C->getType())) - return true; // Can't tell, just return true to be safe - else - ShiftAmounts.push_back(C); - - bool Safe = llvm::all_of(ShiftAmounts, [](Constant *C) { - auto *CI = dyn_cast_or_null<ConstantInt>(C); - return CI && CI->getValue().ult(C->getType()->getIntegerBitWidth()); - }); - return !Safe; - } - return true; - } + case Instruction::LShr: + return !shiftAmountKnownInRange(Op->getOperand(1)); case Instruction::FPToSI: case Instruction::FPToUI: // fptosi/ui yields poison if the resulting value does not fit in the @@ -5127,17 +5252,78 @@ static bool canCreateUndefOrPoison(const Operator *Op, bool PoisonOnly, if (auto *II = dyn_cast<IntrinsicInst>(Op)) { switch (II->getIntrinsicID()) { // TODO: Add more intrinsics. + case Intrinsic::ctlz: + case Intrinsic::cttz: + case Intrinsic::abs: + if (cast<ConstantInt>(II->getArgOperand(1))->isNullValue()) + return false; + break; case Intrinsic::ctpop: + case Intrinsic::bswap: + case Intrinsic::bitreverse: + case Intrinsic::fshl: + case Intrinsic::fshr: + case Intrinsic::smax: + case Intrinsic::smin: + case Intrinsic::umax: + case Intrinsic::umin: + case Intrinsic::ptrmask: + case Intrinsic::fptoui_sat: + case Intrinsic::fptosi_sat: case Intrinsic::sadd_with_overflow: case Intrinsic::ssub_with_overflow: case Intrinsic::smul_with_overflow: case Intrinsic::uadd_with_overflow: case Intrinsic::usub_with_overflow: case Intrinsic::umul_with_overflow: + case Intrinsic::sadd_sat: + case Intrinsic::uadd_sat: + case Intrinsic::ssub_sat: + case Intrinsic::usub_sat: + return false; + case Intrinsic::sshl_sat: + case Intrinsic::ushl_sat: + return !shiftAmountKnownInRange(II->getArgOperand(1)); + case Intrinsic::fma: + case Intrinsic::fmuladd: + case Intrinsic::sqrt: + case Intrinsic::powi: + case Intrinsic::sin: + case Intrinsic::cos: + case Intrinsic::pow: + case Intrinsic::log: + case Intrinsic::log10: + case Intrinsic::log2: + case Intrinsic::exp: + case Intrinsic::exp2: + case Intrinsic::fabs: + case Intrinsic::copysign: + case Intrinsic::floor: + case Intrinsic::ceil: + case Intrinsic::trunc: + case Intrinsic::rint: + case Intrinsic::nearbyint: + case Intrinsic::round: + case Intrinsic::roundeven: + case Intrinsic::fptrunc_round: + case Intrinsic::canonicalize: + case Intrinsic::arithmetic_fence: + case Intrinsic::minnum: + case Intrinsic::maxnum: + case Intrinsic::minimum: + case Intrinsic::maximum: + case Intrinsic::is_fpclass: + return false; + case Intrinsic::lround: + case Intrinsic::llround: + case Intrinsic::lrint: + case Intrinsic::llrint: + // If the value doesn't fit an unspecified value is returned (but this + // is not poison). return false; } } - LLVM_FALLTHROUGH; + [[fallthrough]]; case Instruction::CallBr: case Instruction::Invoke: { const auto *CB = cast<CallBase>(Op); @@ -5172,6 +5358,11 @@ static bool canCreateUndefOrPoison(const Operator *Op, bool PoisonOnly, case Instruction::Freeze: case Instruction::ICmp: case Instruction::FCmp: + case Instruction::FAdd: + case Instruction::FSub: + case Instruction::FMul: + case Instruction::FDiv: + case Instruction::FRem: return false; case Instruction::GetElementPtr: // inbounds is handled above @@ -5189,12 +5380,15 @@ static bool canCreateUndefOrPoison(const Operator *Op, bool PoisonOnly, } } -bool llvm::canCreateUndefOrPoison(const Operator *Op, bool ConsiderFlags) { - return ::canCreateUndefOrPoison(Op, /*PoisonOnly=*/false, ConsiderFlags); +bool llvm::canCreateUndefOrPoison(const Operator *Op, + bool ConsiderFlagsAndMetadata) { + return ::canCreateUndefOrPoison(Op, /*PoisonOnly=*/false, + ConsiderFlagsAndMetadata); } -bool llvm::canCreatePoison(const Operator *Op, bool ConsiderFlags) { - return ::canCreateUndefOrPoison(Op, /*PoisonOnly=*/true, ConsiderFlags); +bool llvm::canCreatePoison(const Operator *Op, bool ConsiderFlagsAndMetadata) { + return ::canCreateUndefOrPoison(Op, /*PoisonOnly=*/true, + ConsiderFlagsAndMetadata); } static bool directlyImpliesPoison(const Value *ValAssumedPoison, @@ -5207,15 +5401,12 @@ static bool directlyImpliesPoison(const Value *ValAssumedPoison, return false; if (const auto *I = dyn_cast<Instruction>(V)) { - if (propagatesPoison(cast<Operator>(I))) - return any_of(I->operands(), [=](const Value *Op) { - return directlyImpliesPoison(ValAssumedPoison, Op, Depth + 1); - }); + if (any_of(I->operands(), [=](const Use &Op) { + return propagatesPoison(Op) && + directlyImpliesPoison(ValAssumedPoison, Op, Depth + 1); + })) + return true; - // 'select ValAssumedPoison, _, _' is poison. - if (const auto *SI = dyn_cast<SelectInst>(I)) - return directlyImpliesPoison(ValAssumedPoison, SI->getCondition(), - Depth + 1); // V = extractvalue V0, idx // V2 = extractvalue V0, idx2 // V0's elements are all poison or not. (e.g., add_with_overflow) @@ -5373,7 +5564,8 @@ static bool isGuaranteedNotToBeUndefOrPoison(const Value *V, else if (PoisonOnly && isa<Operator>(Cond)) { // For poison, we can analyze further auto *Opr = cast<Operator>(Cond); - if (propagatesPoison(Opr) && is_contained(Opr->operand_values(), V)) + if (any_of(Opr->operands(), + [V](const Use &U) { return V == U && propagatesPoison(U); })) return true; } } @@ -5495,13 +5687,15 @@ bool llvm::isGuaranteedToExecuteForEveryIteration(const Instruction *I, llvm_unreachable("Instruction not contained in its own parent basic block."); } -bool llvm::propagatesPoison(const Operator *I) { +bool llvm::propagatesPoison(const Use &PoisonOp) { + const Operator *I = cast<Operator>(PoisonOp.getUser()); switch (I->getOpcode()) { case Instruction::Freeze: - case Instruction::Select: case Instruction::PHI: case Instruction::Invoke: return false; + case Instruction::Select: + return PoisonOp.getOperandNo() == 0; case Instruction::Call: if (auto *II = dyn_cast<IntrinsicInst>(I)) { switch (II->getIntrinsicID()) { @@ -5535,49 +5729,58 @@ bool llvm::propagatesPoison(const Operator *I) { } void llvm::getGuaranteedWellDefinedOps( - const Instruction *I, SmallPtrSetImpl<const Value *> &Operands) { + const Instruction *I, SmallVectorImpl<const Value *> &Operands) { switch (I->getOpcode()) { case Instruction::Store: - Operands.insert(cast<StoreInst>(I)->getPointerOperand()); + Operands.push_back(cast<StoreInst>(I)->getPointerOperand()); break; case Instruction::Load: - Operands.insert(cast<LoadInst>(I)->getPointerOperand()); + Operands.push_back(cast<LoadInst>(I)->getPointerOperand()); break; // Since dereferenceable attribute imply noundef, atomic operations // also implicitly have noundef pointers too case Instruction::AtomicCmpXchg: - Operands.insert(cast<AtomicCmpXchgInst>(I)->getPointerOperand()); + Operands.push_back(cast<AtomicCmpXchgInst>(I)->getPointerOperand()); break; case Instruction::AtomicRMW: - Operands.insert(cast<AtomicRMWInst>(I)->getPointerOperand()); + Operands.push_back(cast<AtomicRMWInst>(I)->getPointerOperand()); break; case Instruction::Call: case Instruction::Invoke: { const CallBase *CB = cast<CallBase>(I); if (CB->isIndirectCall()) - Operands.insert(CB->getCalledOperand()); + Operands.push_back(CB->getCalledOperand()); for (unsigned i = 0; i < CB->arg_size(); ++i) { if (CB->paramHasAttr(i, Attribute::NoUndef) || CB->paramHasAttr(i, Attribute::Dereferenceable)) - Operands.insert(CB->getArgOperand(i)); + Operands.push_back(CB->getArgOperand(i)); } break; } case Instruction::Ret: if (I->getFunction()->hasRetAttribute(Attribute::NoUndef)) - Operands.insert(I->getOperand(0)); + Operands.push_back(I->getOperand(0)); break; + case Instruction::Switch: + Operands.push_back(cast<SwitchInst>(I)->getCondition()); + break; + case Instruction::Br: { + auto *BR = cast<BranchInst>(I); + if (BR->isConditional()) + Operands.push_back(BR->getCondition()); + break; + } default: break; } } void llvm::getGuaranteedNonPoisonOps(const Instruction *I, - SmallPtrSetImpl<const Value *> &Operands) { + SmallVectorImpl<const Value *> &Operands) { getGuaranteedWellDefinedOps(I, Operands); switch (I->getOpcode()) { // Divisors of these operations are allowed to be partially undef. @@ -5585,18 +5788,8 @@ void llvm::getGuaranteedNonPoisonOps(const Instruction *I, case Instruction::SDiv: case Instruction::URem: case Instruction::SRem: - Operands.insert(I->getOperand(1)); + Operands.push_back(I->getOperand(1)); break; - case Instruction::Switch: - if (BranchOnPoisonAsUB) - Operands.insert(cast<SwitchInst>(I)->getCondition()); - break; - case Instruction::Br: { - auto *BR = cast<BranchInst>(I); - if (BranchOnPoisonAsUB && BR->isConditional()) - Operands.insert(BR->getCondition()); - break; - } default: break; } @@ -5604,7 +5797,7 @@ void llvm::getGuaranteedNonPoisonOps(const Instruction *I, bool llvm::mustTriggerUB(const Instruction *I, const SmallSet<const Value *, 16>& KnownPoison) { - SmallPtrSet<const Value *, 4> NonPoisonOps; + SmallVector<const Value *, 4> NonPoisonOps; getGuaranteedNonPoisonOps(I, NonPoisonOps); for (const auto *V : NonPoisonOps) @@ -5652,9 +5845,9 @@ static bool programUndefinedIfUndefOrPoison(const Value *V, if (--ScanLimit == 0) break; - SmallPtrSet<const Value *, 4> WellDefinedOps; + SmallVector<const Value *, 4> WellDefinedOps; getGuaranteedWellDefinedOps(&I, WellDefinedOps); - if (WellDefinedOps.contains(V)) + if (is_contained(WellDefinedOps, V)) return true; if (!isGuaranteedToTransferExecutionToSuccessor(&I)) @@ -5669,11 +5862,6 @@ static bool programUndefinedIfUndefOrPoison(const Value *V, SmallSet<const BasicBlock *, 4> Visited; YieldsPoison.insert(V); - auto Propagate = [&](const User *User) { - if (propagatesPoison(cast<Operator>(User))) - YieldsPoison.insert(User); - }; - for_each(V->users(), Propagate); Visited.insert(BB); while (true) { @@ -5687,9 +5875,13 @@ static bool programUndefinedIfUndefOrPoison(const Value *V, if (!isGuaranteedToTransferExecutionToSuccessor(&I)) return false; - // Mark poison that propagates from I through uses of I. - if (YieldsPoison.count(&I)) - for_each(I.users(), Propagate); + // If an operand is poison and propagates it, mark I as yielding poison. + for (const Use &Op : I.operands()) { + if (YieldsPoison.count(Op) && propagatesPoison(Op)) { + YieldsPoison.insert(&I); + break; + } + } } BB = BB->getSingleSuccessor(); @@ -6049,6 +6241,7 @@ static SelectPatternResult matchSelectPattern(CmpInst::Predicate Pred, Value *TrueVal, Value *FalseVal, Value *&LHS, Value *&RHS, unsigned Depth) { + bool HasMismatchedZeros = false; if (CmpInst::isFPPredicate(Pred)) { // IEEE-754 ignores the sign of 0.0 in comparisons. So if the select has one // 0.0 operand, set the compare's 0.0 operands to that same value for the @@ -6063,10 +6256,14 @@ static SelectPatternResult matchSelectPattern(CmpInst::Predicate Pred, OutputZeroVal = FalseVal; if (OutputZeroVal) { - if (match(CmpLHS, m_AnyZeroFP())) + if (match(CmpLHS, m_AnyZeroFP()) && CmpLHS != OutputZeroVal) { + HasMismatchedZeros = true; CmpLHS = OutputZeroVal; - if (match(CmpRHS, m_AnyZeroFP())) + } + if (match(CmpRHS, m_AnyZeroFP()) && CmpRHS != OutputZeroVal) { + HasMismatchedZeros = true; CmpRHS = OutputZeroVal; + } } } @@ -6080,7 +6277,11 @@ static SelectPatternResult matchSelectPattern(CmpInst::Predicate Pred, // operands is known to not be zero or if we don't care about signed zero. switch (Pred) { default: break; - // FIXME: Include OGT/OLT/UGT/ULT. + case CmpInst::FCMP_OGT: case CmpInst::FCMP_OLT: + case CmpInst::FCMP_UGT: case CmpInst::FCMP_ULT: + if (!HasMismatchedZeros) + break; + [[fallthrough]]; case CmpInst::FCMP_OGE: case CmpInst::FCMP_OLE: case CmpInst::FCMP_UGE: case CmpInst::FCMP_ULE: if (!FMF.noSignedZeros() && !isKnownNonZero(CmpLHS) && @@ -6421,10 +6622,6 @@ Intrinsic::ID llvm::getInverseMinMaxIntrinsic(Intrinsic::ID MinMaxID) { } } -CmpInst::Predicate llvm::getInverseMinMaxPred(SelectPatternFlavor SPF) { - return getMinMaxPred(getInverseMinMaxFlavor(SPF)); -} - APInt llvm::getMinMaxLimit(SelectPatternFlavor SPF, unsigned BitWidth) { switch (SPF) { case SPF_SMAX: return APInt::getSignedMaxValue(BitWidth); @@ -6502,7 +6699,8 @@ bool llvm::matchSimpleRecurrence(const PHINode *P, BinaryOperator *&BO, case Instruction::Sub: case Instruction::And: case Instruction::Or: - case Instruction::Mul: { + case Instruction::Mul: + case Instruction::FMul: { Value *LL = LU->getOperand(0); Value *LR = LU->getOperand(1); // Find a recurrence. @@ -6599,119 +6797,114 @@ static bool isTruePredicate(CmpInst::Predicate Pred, const Value *LHS, } /// Return true if "icmp Pred BLHS BRHS" is true whenever "icmp Pred -/// ALHS ARHS" is true. Otherwise, return None. -static Optional<bool> +/// ALHS ARHS" is true. Otherwise, return std::nullopt. +static std::optional<bool> isImpliedCondOperands(CmpInst::Predicate Pred, const Value *ALHS, const Value *ARHS, const Value *BLHS, const Value *BRHS, const DataLayout &DL, unsigned Depth) { switch (Pred) { default: - return None; + return std::nullopt; case CmpInst::ICMP_SLT: case CmpInst::ICMP_SLE: if (isTruePredicate(CmpInst::ICMP_SLE, BLHS, ALHS, DL, Depth) && isTruePredicate(CmpInst::ICMP_SLE, ARHS, BRHS, DL, Depth)) return true; - return None; + return std::nullopt; case CmpInst::ICMP_ULT: case CmpInst::ICMP_ULE: if (isTruePredicate(CmpInst::ICMP_ULE, BLHS, ALHS, DL, Depth) && isTruePredicate(CmpInst::ICMP_ULE, ARHS, BRHS, DL, Depth)) return true; - return None; + return std::nullopt; } } -/// Return true if the operands of the two compares match. IsSwappedOps is true -/// when the operands match, but are swapped. -static bool isMatchingOps(const Value *ALHS, const Value *ARHS, - const Value *BLHS, const Value *BRHS, - bool &IsSwappedOps) { - - bool IsMatchingOps = (ALHS == BLHS && ARHS == BRHS); - IsSwappedOps = (ALHS == BRHS && ARHS == BLHS); - return IsMatchingOps || IsSwappedOps; +/// Return true if the operands of two compares (expanded as "L0 pred L1" and +/// "R0 pred R1") match. IsSwappedOps is true when the operands match, but are +/// swapped. +static bool areMatchingOperands(const Value *L0, const Value *L1, const Value *R0, + const Value *R1, bool &AreSwappedOps) { + bool AreMatchingOps = (L0 == R0 && L1 == R1); + AreSwappedOps = (L0 == R1 && L1 == R0); + return AreMatchingOps || AreSwappedOps; } -/// Return true if "icmp1 APred X, Y" implies "icmp2 BPred X, Y" is true. -/// Return false if "icmp1 APred X, Y" implies "icmp2 BPred X, Y" is false. -/// Otherwise, return None if we can't infer anything. -static Optional<bool> isImpliedCondMatchingOperands(CmpInst::Predicate APred, - CmpInst::Predicate BPred, - bool AreSwappedOps) { +/// Return true if "icmp1 LPred X, Y" implies "icmp2 RPred X, Y" is true. +/// Return false if "icmp1 LPred X, Y" implies "icmp2 RPred X, Y" is false. +/// Otherwise, return std::nullopt if we can't infer anything. +static std::optional<bool> +isImpliedCondMatchingOperands(CmpInst::Predicate LPred, + CmpInst::Predicate RPred, bool AreSwappedOps) { // Canonicalize the predicate as if the operands were not commuted. if (AreSwappedOps) - BPred = ICmpInst::getSwappedPredicate(BPred); + RPred = ICmpInst::getSwappedPredicate(RPred); - if (CmpInst::isImpliedTrueByMatchingCmp(APred, BPred)) + if (CmpInst::isImpliedTrueByMatchingCmp(LPred, RPred)) return true; - if (CmpInst::isImpliedFalseByMatchingCmp(APred, BPred)) + if (CmpInst::isImpliedFalseByMatchingCmp(LPred, RPred)) return false; - return None; + return std::nullopt; } -/// Return true if "icmp APred X, C1" implies "icmp BPred X, C2" is true. -/// Return false if "icmp APred X, C1" implies "icmp BPred X, C2" is false. -/// Otherwise, return None if we can't infer anything. -static Optional<bool> isImpliedCondMatchingImmOperands(CmpInst::Predicate APred, - const APInt &C1, - CmpInst::Predicate BPred, - const APInt &C2) { - ConstantRange DomCR = ConstantRange::makeExactICmpRegion(APred, C1); - ConstantRange CR = ConstantRange::makeExactICmpRegion(BPred, C2); +/// Return true if "icmp LPred X, LC" implies "icmp RPred X, RC" is true. +/// Return false if "icmp LPred X, LC" implies "icmp RPred X, RC" is false. +/// Otherwise, return std::nullopt if we can't infer anything. +static std::optional<bool> isImpliedCondCommonOperandWithConstants( + CmpInst::Predicate LPred, const APInt &LC, CmpInst::Predicate RPred, + const APInt &RC) { + ConstantRange DomCR = ConstantRange::makeExactICmpRegion(LPred, LC); + ConstantRange CR = ConstantRange::makeExactICmpRegion(RPred, RC); ConstantRange Intersection = DomCR.intersectWith(CR); ConstantRange Difference = DomCR.difference(CR); if (Intersection.isEmptySet()) return false; if (Difference.isEmptySet()) return true; - return None; + return std::nullopt; } -/// Return true if LHS implies RHS is true. Return false if LHS implies RHS is -/// false. Otherwise, return None if we can't infer anything. -static Optional<bool> isImpliedCondICmps(const ICmpInst *LHS, - CmpInst::Predicate BPred, - const Value *BLHS, const Value *BRHS, - const DataLayout &DL, bool LHSIsTrue, - unsigned Depth) { - Value *ALHS = LHS->getOperand(0); - Value *ARHS = LHS->getOperand(1); +/// Return true if LHS implies RHS (expanded to its components as "R0 RPred R1") +/// is true. Return false if LHS implies RHS is false. Otherwise, return +/// std::nullopt if we can't infer anything. +static std::optional<bool> isImpliedCondICmps(const ICmpInst *LHS, + CmpInst::Predicate RPred, + const Value *R0, const Value *R1, + const DataLayout &DL, + bool LHSIsTrue, unsigned Depth) { + Value *L0 = LHS->getOperand(0); + Value *L1 = LHS->getOperand(1); // The rest of the logic assumes the LHS condition is true. If that's not the // case, invert the predicate to make it so. - CmpInst::Predicate APred = + CmpInst::Predicate LPred = LHSIsTrue ? LHS->getPredicate() : LHS->getInversePredicate(); // Can we infer anything when the two compares have matching operands? bool AreSwappedOps; - if (isMatchingOps(ALHS, ARHS, BLHS, BRHS, AreSwappedOps)) { - if (Optional<bool> Implication = isImpliedCondMatchingOperands( - APred, BPred, AreSwappedOps)) - return Implication; - // No amount of additional analysis will infer the second condition, so - // early exit. - return None; - } + if (areMatchingOperands(L0, L1, R0, R1, AreSwappedOps)) + return isImpliedCondMatchingOperands(LPred, RPred, AreSwappedOps); - // Can we infer anything when the LHS operands match and the RHS operands are + // Can we infer anything when the 0-operands match and the 1-operands are // constants (not necessarily matching)? - const APInt *AC, *BC; - if (ALHS == BLHS && match(ARHS, m_APInt(AC)) && match(BRHS, m_APInt(BC))) - return isImpliedCondMatchingImmOperands(APred, *AC, BPred, *BC); + const APInt *LC, *RC; + if (L0 == R0 && match(L1, m_APInt(LC)) && match(R1, m_APInt(RC))) + return isImpliedCondCommonOperandWithConstants(LPred, *LC, RPred, *RC); + + if (LPred == RPred) + return isImpliedCondOperands(LPred, L0, L1, R0, R1, DL, Depth); - if (APred == BPred) - return isImpliedCondOperands(APred, ALHS, ARHS, BLHS, BRHS, DL, Depth); - return None; + return std::nullopt; } /// Return true if LHS implies RHS is true. Return false if LHS implies RHS is -/// false. Otherwise, return None if we can't infer anything. We expect the -/// RHS to be an icmp and the LHS to be an 'and', 'or', or a 'select' instruction. -static Optional<bool> +/// false. Otherwise, return std::nullopt if we can't infer anything. We +/// expect the RHS to be an icmp and the LHS to be an 'and', 'or', or a 'select' +/// instruction. +static std::optional<bool> isImpliedCondAndOr(const Instruction *LHS, CmpInst::Predicate RHSPred, const Value *RHSOp0, const Value *RHSOp1, const DataLayout &DL, bool LHSIsTrue, unsigned Depth) { @@ -6730,29 +6923,29 @@ isImpliedCondAndOr(const Instruction *LHS, CmpInst::Predicate RHSPred, if ((!LHSIsTrue && match(LHS, m_LogicalOr(m_Value(ALHS), m_Value(ARHS)))) || (LHSIsTrue && match(LHS, m_LogicalAnd(m_Value(ALHS), m_Value(ARHS))))) { // FIXME: Make this non-recursion. - if (Optional<bool> Implication = isImpliedCondition( + if (std::optional<bool> Implication = isImpliedCondition( ALHS, RHSPred, RHSOp0, RHSOp1, DL, LHSIsTrue, Depth + 1)) return Implication; - if (Optional<bool> Implication = isImpliedCondition( + if (std::optional<bool> Implication = isImpliedCondition( ARHS, RHSPred, RHSOp0, RHSOp1, DL, LHSIsTrue, Depth + 1)) return Implication; - return None; + return std::nullopt; } - return None; + return std::nullopt; } -Optional<bool> +std::optional<bool> llvm::isImpliedCondition(const Value *LHS, CmpInst::Predicate RHSPred, const Value *RHSOp0, const Value *RHSOp1, const DataLayout &DL, bool LHSIsTrue, unsigned Depth) { // Bail out when we hit the limit. if (Depth == MaxAnalysisRecursionDepth) - return None; + return std::nullopt; // A mismatch occurs when we compare a scalar cmp to a vector cmp, for // example. if (RHSOp0->getType()->isVectorTy() != LHS->getType()->isVectorTy()) - return None; + return std::nullopt; assert(LHS->getType()->isIntOrIntVectorTy(1) && "Expected integer type only!"); @@ -6773,12 +6966,12 @@ llvm::isImpliedCondition(const Value *LHS, CmpInst::Predicate RHSPred, return isImpliedCondAndOr(LHSI, RHSPred, RHSOp0, RHSOp1, DL, LHSIsTrue, Depth); } - return None; + return std::nullopt; } -Optional<bool> llvm::isImpliedCondition(const Value *LHS, const Value *RHS, - const DataLayout &DL, bool LHSIsTrue, - unsigned Depth) { +std::optional<bool> llvm::isImpliedCondition(const Value *LHS, const Value *RHS, + const DataLayout &DL, + bool LHSIsTrue, unsigned Depth) { // LHS ==> RHS by definition if (LHS == RHS) return LHSIsTrue; @@ -6789,33 +6982,33 @@ Optional<bool> llvm::isImpliedCondition(const Value *LHS, const Value *RHS, LHSIsTrue, Depth); if (Depth == MaxAnalysisRecursionDepth) - return None; + return std::nullopt; // LHS ==> (RHS1 || RHS2) if LHS ==> RHS1 or LHS ==> RHS2 // LHS ==> !(RHS1 && RHS2) if LHS ==> !RHS1 or LHS ==> !RHS2 const Value *RHS1, *RHS2; if (match(RHS, m_LogicalOr(m_Value(RHS1), m_Value(RHS2)))) { - if (Optional<bool> Imp = + if (std::optional<bool> Imp = isImpliedCondition(LHS, RHS1, DL, LHSIsTrue, Depth + 1)) if (*Imp == true) return true; - if (Optional<bool> Imp = + if (std::optional<bool> Imp = isImpliedCondition(LHS, RHS2, DL, LHSIsTrue, Depth + 1)) if (*Imp == true) return true; } if (match(RHS, m_LogicalAnd(m_Value(RHS1), m_Value(RHS2)))) { - if (Optional<bool> Imp = + if (std::optional<bool> Imp = isImpliedCondition(LHS, RHS1, DL, LHSIsTrue, Depth + 1)) if (*Imp == false) return false; - if (Optional<bool> Imp = + if (std::optional<bool> Imp = isImpliedCondition(LHS, RHS2, DL, LHSIsTrue, Depth + 1)) if (*Imp == false) return false; } - return None; + return std::nullopt; } // Returns a pair (Condition, ConditionIsTrue), where Condition is a branch @@ -6849,25 +7042,26 @@ getDomPredecessorCondition(const Instruction *ContextI) { return {PredCond, TrueBB == ContextBB}; } -Optional<bool> llvm::isImpliedByDomCondition(const Value *Cond, - const Instruction *ContextI, - const DataLayout &DL) { +std::optional<bool> llvm::isImpliedByDomCondition(const Value *Cond, + const Instruction *ContextI, + const DataLayout &DL) { assert(Cond->getType()->isIntOrIntVectorTy(1) && "Condition must be bool"); auto PredCond = getDomPredecessorCondition(ContextI); if (PredCond.first) return isImpliedCondition(PredCond.first, Cond, DL, PredCond.second); - return None; + return std::nullopt; } -Optional<bool> llvm::isImpliedByDomCondition(CmpInst::Predicate Pred, - const Value *LHS, const Value *RHS, - const Instruction *ContextI, - const DataLayout &DL) { +std::optional<bool> llvm::isImpliedByDomCondition(CmpInst::Predicate Pred, + const Value *LHS, + const Value *RHS, + const Instruction *ContextI, + const DataLayout &DL) { auto PredCond = getDomPredecessorCondition(ContextI); if (PredCond.first) return isImpliedCondition(PredCond.first, Pred, LHS, RHS, DL, PredCond.second); - return None; + return std::nullopt; } static void setLimitsForBinOp(const BinaryOperator &BO, APInt &Lower, @@ -7246,11 +7440,9 @@ ConstantRange llvm::computeConstantRange(const Value *V, bool ForSigned, for (auto &AssumeVH : AC->assumptionsFor(V)) { if (!AssumeVH) continue; - CallInst *I = cast<CallInst>(AssumeVH); + IntrinsicInst *I = cast<IntrinsicInst>(AssumeVH); assert(I->getParent()->getParent() == CtxI->getParent()->getParent() && "Got assumption for the wrong function!"); - assert(I->getCalledFunction()->getIntrinsicID() == Intrinsic::assume && - "must be an assume intrinsic"); if (!isValidAssumeForContext(I, CtxI, DT)) continue; @@ -7271,7 +7463,7 @@ ConstantRange llvm::computeConstantRange(const Value *V, bool ForSigned, return CR; } -static Optional<int64_t> +static std::optional<int64_t> getOffsetFromIndex(const GEPOperator *GEP, unsigned Idx, const DataLayout &DL) { // Skip over the first indices. gep_type_iterator GTI = gep_type_begin(GEP); @@ -7283,7 +7475,7 @@ getOffsetFromIndex(const GEPOperator *GEP, unsigned Idx, const DataLayout &DL) { for (unsigned i = Idx, e = GEP->getNumOperands(); i != e; ++i, ++GTI) { ConstantInt *OpC = dyn_cast<ConstantInt>(GEP->getOperand(i)); if (!OpC) - return None; + return std::nullopt; if (OpC->isZero()) continue; // No offset. @@ -7297,15 +7489,16 @@ getOffsetFromIndex(const GEPOperator *GEP, unsigned Idx, const DataLayout &DL) { // vector. Multiply the index by the ElementSize. TypeSize Size = DL.getTypeAllocSize(GTI.getIndexedType()); if (Size.isScalable()) - return None; - Offset += Size.getFixedSize() * OpC->getSExtValue(); + return std::nullopt; + Offset += Size.getFixedValue() * OpC->getSExtValue(); } return Offset; } -Optional<int64_t> llvm::isPointerOffset(const Value *Ptr1, const Value *Ptr2, - const DataLayout &DL) { +std::optional<int64_t> llvm::isPointerOffset(const Value *Ptr1, + const Value *Ptr2, + const DataLayout &DL) { APInt Offset1(DL.getIndexTypeSizeInBits(Ptr1->getType()), 0); APInt Offset2(DL.getIndexTypeSizeInBits(Ptr2->getType()), 0); Ptr1 = Ptr1->stripAndAccumulateConstantOffsets(DL, Offset1, true); @@ -7325,7 +7518,7 @@ Optional<int64_t> llvm::isPointerOffset(const Value *Ptr1, const Value *Ptr2, // handle no other case. if (!GEP1 || !GEP2 || GEP1->getOperand(0) != GEP2->getOperand(0) || GEP1->getSourceElementType() != GEP2->getSourceElementType()) - return None; + return std::nullopt; // Skip any common indices and track the GEP types. unsigned Idx = 1; @@ -7336,7 +7529,7 @@ Optional<int64_t> llvm::isPointerOffset(const Value *Ptr1, const Value *Ptr2, auto IOffset1 = getOffsetFromIndex(GEP1, Idx, DL); auto IOffset2 = getOffsetFromIndex(GEP2, Idx, DL); if (!IOffset1 || !IOffset2) - return None; + return std::nullopt; return *IOffset2 - *IOffset1 + Offset2.getSExtValue() - Offset1.getSExtValue(); } |