From 02fdbc3567249471349474c70828cb5a5d4881c8 Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Tue, 24 Nov 2020 17:56:59 +0700 Subject: [PATCH] Revert "[NFC][SCEV] Generalize monotonicity check for full and limited iteration space" This reverts commit 2734a9ebf4a31df0131acdfc739395a5e692c342. This patch appeared to not be a NFC. It introduced an execution path where monotonicity check on limited space started relying in existing nsw/nuw flags, which is illegal. The motivating test will follow-up. --- llvm/include/llvm/Analysis/ScalarEvolution.h | 15 ++-- llvm/lib/Analysis/ScalarEvolution.cpp | 111 ++++++++++++--------------- 2 files changed, 53 insertions(+), 73 deletions(-) diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h index 677433c..9c19ec9 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -954,14 +954,9 @@ public: /// 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, - Optional NumIter = None, - const Instruction *Context = nullptr); + getMonotonicPredicateType(const SCEVAddRecExpr *LHS, + ICmpInst::Predicate Pred); struct LoopInvariantPredicate { ICmpInst::Predicate Pred; @@ -1920,9 +1915,9 @@ private: /// entry and backedge. SCEV::NoWrapFlags proveNoUnsignedWrapViaInduction(const SCEVAddRecExpr *AR); - Optional getMonotonicPredicateTypeImpl( - const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, - Optional NumIter, const Instruction *Context); + Optional + getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS, + ICmpInst::Predicate Pred); /// 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) diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index a366ad3..08ed363 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -9504,19 +9504,15 @@ bool ScalarEvolution::isKnownOnEveryIteration(ICmpInst::Predicate Pred, Optional ScalarEvolution::getMonotonicPredicateType(const SCEVAddRecExpr *LHS, - 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); + ICmpInst::Predicate Pred) { + auto Result = getMonotonicPredicateTypeImpl(LHS, Pred); #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), NumIter, Context); + auto ResultSwapped = + getMonotonicPredicateTypeImpl(LHS, ICmpInst::getSwappedPredicate(Pred)); assert(ResultSwapped.hasValue() && "should be able to analyze both!"); assert(ResultSwapped.getValue() != Result.getValue() && @@ -9529,9 +9525,7 @@ ScalarEvolution::getMonotonicPredicateType(const SCEVAddRecExpr *LHS, Optional ScalarEvolution::getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS, - ICmpInst::Predicate Pred, - Optional NumIter, - const Instruction *Context) { + ICmpInst::Predicate Pred) { // 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 @@ -9550,60 +9544,23 @@ ScalarEvolution::getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS, 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. - - const SCEV *Step = LHS->getStepRecurrence(*this); - bool IsStepNonNegative = isKnownNonNegative(Step); - bool IsStepNonPositive = isKnownNonPositive(Step); - // We need to know which direction the iteration is going. - if (!IsStepNonNegative && !IsStepNonPositive) - return None; - - auto ProvedNoWrap = [&]() { - // If the AddRec already has the flag, we are done. - if (IsUnsigned ? LHS->hasNoUnsignedWrap() : LHS->hasNoSignedWrap()) - return true; - - if (!NumIter) - return false; - // We could not prove no-wrap on all iteration space. Can we prove it for - // first iterations? In order to achieve it, check that: - // 1. The addrec does not self-wrap; - // 2. start <= end for non-negative step and start >= end for non-positive - // step. - 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) - return false; - const SCEV *Start = LHS->getStart(); - const SCEV *End = LHS->evaluateAtIteration(*NumIter, *this); - ICmpInst::Predicate NoOverflowPred = - IsStepNonNegative ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_SGE; - if (IsUnsigned) - NoOverflowPred = ICmpInst::getUnsignedPredicate(NoOverflowPred); - return isKnownPredicateAt(NoOverflowPred, Start, End, Context); - }; + // Check that AR does not wrap. + if (ICmpInst::isUnsigned(Pred)) { + if (!LHS->hasNoUnsignedWrap()) + return None; + return IsGreater ? MonotonicallyIncreasing : MonotonicallyDecreasing; + } else { + assert(ICmpInst::isSigned(Pred) && + "Relational predicate is either signed or unsigned!"); + if (!LHS->hasNoSignedWrap()) + return None; - // If nothing worked, bail. - if (!ProvedNoWrap()) - return None; + const SCEV *Step = LHS->getStepRecurrence(*this); - if (IsUnsigned) - return IsGreater ? MonotonicallyIncreasing : MonotonicallyDecreasing; - else { - if (IsStepNonNegative) + if (isKnownNonNegative(Step)) return IsGreater ? MonotonicallyIncreasing : MonotonicallyDecreasing; - if (IsStepNonPositive) + if (isKnownNonPositive(Step)) return !IsGreater ? MonotonicallyIncreasing : MonotonicallyDecreasing; return None; @@ -9664,6 +9621,7 @@ ScalarEvolution::getLoopInvariantExitCondDuringFirstIterations( // Try to prove the following set of facts: // - The predicate is monotonic in the iteration space. // - If the check does not fail on the 1st iteration: + // - No overflow will happen during first MaxIter iterations; // - It will not fail on the MaxIter'th iteration. // If the check does fail on the 1st iteration, we leave the loop and no // other checks matter. @@ -9681,7 +9639,23 @@ ScalarEvolution::getLoopInvariantExitCondDuringFirstIterations( if (!AR || AR->getLoop() != L) return None; - if (!getMonotonicPredicateType(AR, Pred, MaxIter, Context)) + // The predicate must be relational (i.e. <, <=, >=, >). + if (!ICmpInst::isRelational(Pred)) + return None; + + const SCEV *Step = AR->getStepRecurrence(*this); + bool IsStepNonPositive = isKnownNonPositive(Step); + if (!IsStepNonPositive && !isKnownNonNegative(Step)) + return None; + bool HasNoSelfWrap = AR->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 (MaxIter->getType() == AR->getType()) + if (Step == getOne(AR->getType()) || Step == getMinusOne(AR->getType())) + HasNoSelfWrap = true; + // Only proceed with non-self-wrapping ARs. + if (!HasNoSelfWrap) return None; // Value of IV on suggested last iteration. @@ -9689,9 +9663,20 @@ ScalarEvolution::getLoopInvariantExitCondDuringFirstIterations( // Does it still meet the requirement? if (!isKnownPredicateAt(Pred, Last, RHS, Context)) return None; + // We know that the addrec does not have a self-wrap. To prove that there is + // no signed/unsigned wrap, we need to check that + // Start <= Last for positive step or Start >= Last for negative step. Either + // works for zero step. + ICmpInst::Predicate NoOverflowPred = + CmpInst::isSigned(Pred) ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; + if (IsStepNonPositive) + NoOverflowPred = CmpInst::getSwappedPredicate(NoOverflowPred); + const SCEV *Start = AR->getStart(); + if (!isKnownPredicateAt(NoOverflowPred, Start, Last, Context)) + return None; // Everything is fine. - return ScalarEvolution::LoopInvariantPredicate(Pred, AR->getStart(), RHS); + return ScalarEvolution::LoopInvariantPredicate(Pred, Start, RHS); } bool ScalarEvolution::isKnownPredicateViaConstantRanges( -- 2.7.4