From a5b2e795c3b26fae16d774a48694e7419ad652f1 Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Thu, 29 Oct 2020 15:27:21 +0700 Subject: [PATCH] [NFC][SCEV] Refactor monotonic predicate checks to return enums instead of bools This patch gets rid of output parameter which is not needed for most users and prepares this API for further refactoring. --- llvm/include/llvm/Analysis/ScalarEvolution.h | 23 +++++++---- llvm/lib/Analysis/ScalarEvolution.cpp | 57 +++++++++++++------------- llvm/lib/Transforms/Scalar/LoopPredication.cpp | 3 +- llvm/lib/Transforms/Utils/LoopPeel.cpp | 4 +- 4 files changed, 46 insertions(+), 41 deletions(-) diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h index 017efb9..37f4ad4 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -939,17 +939,23 @@ public: bool isKnownOnEveryIteration(ICmpInst::Predicate Pred, const SCEVAddRecExpr *LHS, const SCEV *RHS); - /// Return true if, for all loop invariant X, the predicate "LHS `Pred` X" - /// is monotonically increasing or decreasing. In the former case set - /// `Increasing` to true and in the latter case set `Increasing` to false. - /// /// A predicate is said to be monotonically increasing if may go from being /// false to being true as the loop iterates, but never the other way /// around. A predicate is said to be monotonically decreasing if may go /// from being true to being false as the loop iterates, but never the other /// way around. - bool isMonotonicPredicate(const SCEVAddRecExpr *LHS, ICmpInst::Predicate Pred, - bool &Increasing); + enum MonotonicPredicateType { + MonotonicallyIncreasing, + MonotonicallyDecreasing + }; + + /// If, for all loop invariant X, the predicate "LHS `Pred` X" is + /// monotonically increasing or decreasing, returns + /// Some(MonotonicallyIncreasing) and Some(MonotonicallyDecreasing) + /// respectively. If we could not prove either of these facts, returns None. + Optional + getMonotonicPredicateType(const SCEVAddRecExpr *LHS, + ICmpInst::Predicate Pred); /// Return true if the result of the predicate LHS `Pred` RHS is loop /// invariant with respect to L. Set InvariantPred, InvariantLHS and @@ -1881,8 +1887,9 @@ private: /// Try to prove NSW or NUW on \p AR relying on ConstantRange manipulation. SCEV::NoWrapFlags proveNoWrapViaConstantRanges(const SCEVAddRecExpr *AR); - bool isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS, - ICmpInst::Predicate Pred, bool &Increasing); + 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 bca8e28..8bc2595 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -9236,31 +9236,30 @@ bool ScalarEvolution::isKnownOnEveryIteration(ICmpInst::Predicate Pred, isLoopBackedgeGuardedByCond(L, Pred, LHS->getPostIncExpr(*this), RHS); } -bool ScalarEvolution::isMonotonicPredicate(const SCEVAddRecExpr *LHS, - ICmpInst::Predicate Pred, - bool &Increasing) { - bool Result = isMonotonicPredicateImpl(LHS, Pred, Increasing); +Optional +ScalarEvolution::getMonotonicPredicateType(const SCEVAddRecExpr *LHS, + 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. - bool IncreasingSwapped; - bool ResultSwapped = isMonotonicPredicateImpl( - LHS, ICmpInst::getSwappedPredicate(Pred), IncreasingSwapped); + if (Result) { + auto ResultSwapped = + getMonotonicPredicateTypeImpl(LHS, ICmpInst::getSwappedPredicate(Pred)); - assert(Result == ResultSwapped && "should be able to analyze both!"); - if (ResultSwapped) - assert(Increasing == !IncreasingSwapped && + assert(ResultSwapped.hasValue() && "should be able to analyze both!"); + assert(ResultSwapped.getValue() != Result.getValue() && "monotonicity should flip as we flip the predicate"); + } #endif return Result; } -bool ScalarEvolution::isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS, - ICmpInst::Predicate Pred, - bool &Increasing) { - +Optional +ScalarEvolution::getMonotonicPredicateTypeImpl(const SCEVAddRecExpr *LHS, + 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 @@ -9273,38 +9272,41 @@ bool ScalarEvolution::isMonotonicPredicateImpl(const SCEVAddRecExpr *LHS, switch (Pred) { default: - return false; // Conservative answer + return None; // Conservative answer case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_UGE: case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: if (!LHS->hasNoUnsignedWrap()) - return false; + return None; - Increasing = Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE; - return true; + return Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE + ? MonotonicallyIncreasing + : MonotonicallyDecreasing; case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_SGE: case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_SLE: { if (!LHS->hasNoSignedWrap()) - return false; + return None; const SCEV *Step = LHS->getStepRecurrence(*this); if (isKnownNonNegative(Step)) { - Increasing = Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE; - return true; + return Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SGE + ? MonotonicallyIncreasing + : MonotonicallyDecreasing; } if (isKnownNonPositive(Step)) { - Increasing = Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE; - return true; + return Pred == ICmpInst::ICMP_SLT || Pred == ICmpInst::ICMP_SLE + ? MonotonicallyIncreasing + : MonotonicallyDecreasing; } - return false; + return None; } } @@ -9330,10 +9332,9 @@ bool ScalarEvolution::isLoopInvariantPredicate( if (!ArLHS || ArLHS->getLoop() != L) return false; - bool Increasing; - if (!isMonotonicPredicate(ArLHS, Pred, Increasing)) + auto MonotonicType = getMonotonicPredicateType(ArLHS, Pred); + if (!MonotonicType) return false; - // If the predicate "ArLHS `Pred` RHS" monotonically increases from false to // true as the loop iterates, and the backedge is control dependent on // "ArLHS `Pred` RHS" == true then we can reason as follows: @@ -9351,7 +9352,7 @@ bool ScalarEvolution::isLoopInvariantPredicate( // // A similar reasoning applies for a monotonically decreasing predicate, by // replacing true with false and false with true in the above two bullets. - + bool Increasing = *MonotonicType == ScalarEvolution::MonotonicallyIncreasing; auto P = Increasing ? Pred : ICmpInst::getInversePredicate(Pred); if (!isLoopBackedgeGuardedByCond(L, P, LHS, RHS)) diff --git a/llvm/lib/Transforms/Scalar/LoopPredication.cpp b/llvm/lib/Transforms/Scalar/LoopPredication.cpp index 27df56f..3ca5b98 100644 --- a/llvm/lib/Transforms/Scalar/LoopPredication.cpp +++ b/llvm/lib/Transforms/Scalar/LoopPredication.cpp @@ -454,8 +454,7 @@ static bool isSafeToTruncateWideIVType(const DataLayout &DL, // LatchEnd = 2, rangeCheckType = i32. If it's not a monotonic predicate, the // IV wraps around, and the truncation of the IV would lose the range of // iterations between 2^32 and 2^64. - bool Increasing; - if (!SE.isMonotonicPredicate(LatchCheck.IV, LatchCheck.Pred, Increasing)) + if (!SE.getMonotonicPredicateType(LatchCheck.IV, LatchCheck.Pred)) return false; // The active bits should be less than the bits in the RangeCheckType. This // guarantees that truncating the latch check to RangeCheckType is a safe diff --git a/llvm/lib/Transforms/Utils/LoopPeel.cpp b/llvm/lib/Transforms/Utils/LoopPeel.cpp index a08b578..27a61a2 100644 --- a/llvm/lib/Transforms/Utils/LoopPeel.cpp +++ b/llvm/lib/Transforms/Utils/LoopPeel.cpp @@ -227,11 +227,9 @@ static unsigned countToEliminateCompares(Loop &L, unsigned MaxPeelCount, // consider AddRecs of the loop we are trying to peel. if (!LeftAR->isAffine() || LeftAR->getLoop() != &L) continue; - bool Increasing; if (!(ICmpInst::isEquality(Pred) && LeftAR->hasNoSelfWrap()) && - !SE.isMonotonicPredicate(LeftAR, Pred, Increasing)) + !SE.getMonotonicPredicateType(LeftAR, Pred)) continue; - (void)Increasing; // Check if extending the current DesiredPeelCount lets us evaluate Pred // or !Pred in the loop body statically. -- 2.7.4