Index: llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/include/llvm/Analysis/ScalarEvolution.h +++ llvm/include/llvm/Analysis/ScalarEvolution.h @@ -953,9 +953,14 @@ /// monotonically increasing or decreasing, returns /// Some(MonotonicallyIncreasing) and Some(MonotonicallyDecreasing) /// respectively. If we could not prove either of these facts, returns None. + /// + /// If NumIter was provided, then we are proving monotonicity during at least + /// NumIter first iterations. If it was not provided, then we are proving + /// monotonicity on all iteration space. Optional - getMonotonicPredicateType(const SCEVAddRecExpr *LHS, - ICmpInst::Predicate Pred); + getMonotonicPredicateType(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, + Optional NumIter = None, + const Instruction *Context = nullptr); /// Return true if the result of the predicate LHS `Pred` RHS is loop /// invariant with respect to L. Set InvariantPred, InvariantLHS and @@ -1887,9 +1892,9 @@ /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation. SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR); - Optional - getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS, - ICmpInst::Predicate Pred); + Optional getMonotonicPredicateTypeImpl( + const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, + Optional NumIter, const Instruction *Context); /// Return SCEV no-wrap flags that can be proven based on reasoning about /// how poison produced from no-wrap flags on this value (e.g. a nuw add) Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -9238,15 +9238,19 @@ Optional ScalarEvolution::getMonotonicPredicateType(const SCEVAddRecExpr *LHS, - ICmpInst::Predicate Pred) { - auto Result = getMonotonicPredicateTypeImpl(LHS, Pred); + ICmpInst::Predicate Pred, + Optional NumIter, + const Instruction *Context) { + assert((!NumIter || !isa(*NumIter)) && + "provided number of iterations must be computable!"); + auto Result = getMonotonicPredicateTypeImpl(LHS, Pred, NumIter, Context); #ifndef NDEBUG // Verify an invariant: inverting the predicate should turn a monotonically // increasing change to a monotonically decreasing one, and vice versa. if (Result) { - auto ResultSwapped = - getMonotonicPredicateTypeImpl(LHS, ICmpInst::getSwappedPredicate(Pred)); + auto ResultSwapped = getMonotonicPredicateTypeImpl( + LHS, ICmpInst::getSwappedPredicate(Pred), NumIter, Context); assert(ResultSwapped.hasValue() && "should be able to analyze both!"); assert(ResultSwapped.getValue() != Result.getValue() && @@ -9259,7 +9263,9 @@ Optional ScalarEvolution::getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS, - ICmpInst::Predicate Pred) { + ICmpInst::Predicate Pred, + Optional NumIter, + const Instruction *Context) { // A zero step value for LHS means the induction variable is essentially a // loop invariant value. We don't really depend on the predicate actually // flipping from false to true (for increasing predicates, and the other way @@ -9277,24 +9283,54 @@ bool IsGreater = ICmpInst::isGE(Pred) || ICmpInst::isGT(Pred); assert((IsGreater || ICmpInst::isLE(Pred) || ICmpInst::isLT(Pred)) && "Should be greater or less!"); + bool IsUnsigned = ICmpInst::isUnsigned(Pred); + assert((IsUnsigned || ICmpInst::isSigned(Pred)) && + "Should be either signed or unsigned!"); + + // Check if we can prove no-wrap in the relevant range. + bool ProvedNoWrap = + IsUnsigned ? LHS->hasNoUnsignedWrap() : LHS->hasNoSignedWrap(); + const SCEV *Step = LHS->getStepRecurrence(*this); + bool IsStepNonNegative = isKnownNonNegative(Step); + bool IsStepNonPositive = isKnownNonPositive(Step); + + // If we only care about first several iterations, check that start <= end for + // non-negative step and start >= end for non-positive step. + if (!ProvedNoWrap && NumIter && (IsStepNonNegative || IsStepNonPositive)) { + bool HasNoSelfWrap = LHS->hasNoSelfWrap(); + if (!HasNoSelfWrap) + // If num iter has same type as the AddRec, and step is +/- 1, even max + // possible number of iterations is not enough to self-wrap. + if (NumIter.getValue()->getType() == LHS->getType()) + if (Step == getOne(LHS->getType()) || + Step == getMinusOne(LHS->getType())) + HasNoSelfWrap = true; + if (HasNoSelfWrap) { + const SCEV *Start = LHS->getStart(); + const SCEV *End = LHS->evaluateAtIteration(*NumIter, *this); + ICmpInst::Predicate NoOverflowPred; + if (IsStepNonNegative) + NoOverflowPred = ICmpInst::ICMP_SLE; + else + NoOverflowPred = ICmpInst::ICMP_SGE; + if (IsUnsigned) + NoOverflowPred = ICmpInst::getUnsignedPredicate(NoOverflowPred); + if (isKnownPredicateAt(NoOverflowPred, Start, End, Context)) + ProvedNoWrap = true; + } + } - // Check that AR does not wrap. - if (ICmpInst::isUnsigned(Pred)) { - if (!LHS->hasNoUnsignedWrap()) - return None; + // If nothing worked, bail. + if (!ProvedNoWrap) + return None; + + if (IsUnsigned) { return IsGreater ? MonotonicallyIncreasing : MonotonicallyDecreasing; } else { - assert(ICmpInst::isSigned(Pred) && - "Relational predicate is either signed or unsigned!"); - if (!LHS->hasNoSignedWrap()) - return None; - - const SCEV *Step = LHS->getStepRecurrence(*this); - - if (isKnownNonNegative(Step)) + if (IsStepNonNegative) return IsGreater ? MonotonicallyIncreasing : MonotonicallyDecreasing; - if (isKnownNonPositive(Step)) + if (IsStepNonPositive) return !IsGreater ? MonotonicallyIncreasing : MonotonicallyDecreasing; return None; @@ -9374,25 +9410,11 @@ } auto *AR = dyn_cast(LHS); - // TODO: Lift affinity limitation in the future. - if (!AR || AR->getLoop() != L || !AR->isAffine()) - return false; - - // The predicate must be relational (i.e. <, <=, >=, >). - if (!ICmpInst::isRelational(Pred)) + if (!AR || AR->getLoop() != L) return false; - // TODO: Support steps other than +/- 1. - const SCEV *Step = AR->getOperand(1); - auto *One = getOne(Step->getType()); - auto *MinusOne = getNegativeSCEV(One); - if (Step != One && Step != MinusOne) - return false; - - // Type mismatch here means that MaxIter is potentially larger than max - // unsigned value in start type, which mean we cannot prove no wrap for the - // indvar. - if (AR->getType() != MaxIter->getType()) + // The predicate must be monotonic (i.e. <, <=, >=, >). + if (!getMonotonicPredicateType(AR, Pred, MaxIter, Context)) return false; // Value of IV on suggested last iteration. @@ -9400,22 +9422,10 @@ // Does it still meet the requirement? if (!isKnownPredicateAt(Pred, Last, RHS, Context)) return false; - // Because step is +/- 1 and MaxIter has same type as Start (i.e. it does - // not exceed max unsigned value of this type), this effectively proves - // that there is no wrap during the iteration. To prove that there is no - // signed/unsigned wrap, we need to check that - // Start <= Last for step = 1 or Start >= Last for step = -1. - ICmpInst::Predicate NoOverflowPred = - CmpInst::isSigned(Pred) ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; - if (Step == MinusOne) - NoOverflowPred = CmpInst::getSwappedPredicate(NoOverflowPred); - const SCEV *Start = AR->getStart(); - if (!isKnownPredicateAt(NoOverflowPred, Start, Last, Context)) - return false; // Everything is fine. InvariantPred = Pred; - InvariantLHS = Start; + InvariantLHS = AR->getStart(); InvariantRHS = RHS; return true; }