From ecf79300dd78b561f138c5d543b6d27d9ab766de Mon Sep 17 00:00:00 2001 From: John Brawn Date: Tue, 18 Oct 2016 10:10:53 +0000 Subject: [SCEV] More accurate calculation of max backedge count of some less-than loops In loops that look something like i = n; do { ... } while(i++ < n+k); where k is a constant, the maximum backedge count is k (in fact the backedge count will be either 0 or k, depending on whether n+k wraps). More generally for LHS < RHS if RHS-(LHS of first comparison) is a constant then the loop will iterate either 0 or that constant number of times. This allows for more loop unrolling with the recent upper bound loop unrolling changes, and I'm working on a patch that will let loop unrolling additionally make use of the loop being executed either 0 or k times (we need to retain the loop comparison only on the first unrolled iteration). Differential Revision: https://reviews.llvm.org/D25607 llvm-svn: 284465 --- llvm/lib/Analysis/ScalarEvolution.cpp | 81 +++++++++++++++++++++++------------ 1 file changed, 53 insertions(+), 28 deletions(-) (limited to 'llvm/lib/Analysis/ScalarEvolution.cpp') diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index f8dadd13f72..cd8909cbc2e 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -8655,43 +8655,68 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS, : ICmpInst::ICMP_ULT; const SCEV *Start = IV->getStart(); const SCEV *End = RHS; - if (!isLoopEntryGuardedByCond(L, Cond, getMinusSCEV(Start, Stride), RHS)) + // If the backedge is taken at least once, then it will be taken + // (End-Start)/Stride times (rounded up to a multiple of Stride), where Start + // is the LHS value of the less-than comparison the first time it is evaluated + // and End is the RHS. + const SCEV *BECountIfBackedgeTaken = + computeBECount(getMinusSCEV(End, Start), Stride, false); + // If the loop entry is guarded by the result of the backedge test of the + // first loop iteration, then we know the backedge will be taken at least + // once and so the backedge taken count is as above. If not then we use the + // expression (max(End,Start)-Start)/Stride to describe the backedge count, + // as if the backedge is taken at least once max(End,Start) is End and so the + // result is as above, and if not max(End,Start) is Start so we get a backedge + // count of zero. + const SCEV *BECount; + if (isLoopEntryGuardedByCond(L, Cond, getMinusSCEV(Start, Stride), RHS)) + BECount = BECountIfBackedgeTaken; + else { End = IsSigned ? getSMaxExpr(RHS, Start) : getUMaxExpr(RHS, Start); + BECount = computeBECount(getMinusSCEV(End, Start), Stride, false); + } - const SCEV *BECount = computeBECount(getMinusSCEV(End, Start), Stride, false); - - APInt MinStart = IsSigned ? getSignedRange(Start).getSignedMin() - : getUnsignedRange(Start).getUnsignedMin(); - - unsigned BitWidth = getTypeSizeInBits(LHS->getType()); - - APInt StrideForMaxBECount; - - if (PositiveStride) - StrideForMaxBECount = IsSigned ? getSignedRange(Stride).getSignedMin() - : getUnsignedRange(Stride).getUnsignedMin(); - else - // Using a stride of 1 is safe when computing max backedge taken count for - // a loop with unknown stride. - StrideForMaxBECount = APInt(BitWidth, 1, IsSigned); + const SCEV *MaxBECount; + if (isa(BECount)) + MaxBECount = BECount; + else if (isa(BECountIfBackedgeTaken)) + // If we know exactly how many times the backedge will be taken if it's + // taken at least once, then the backedge count will either be that or + // zero. + MaxBECount = BECountIfBackedgeTaken; + else { + // Calculate the maximum backedge count based on the range of values + // permitted by Start, End, and Stride. + APInt MinStart = IsSigned ? getSignedRange(Start).getSignedMin() + : getUnsignedRange(Start).getUnsignedMin(); + + unsigned BitWidth = getTypeSizeInBits(LHS->getType()); + + APInt StrideForMaxBECount; + + if (PositiveStride) + StrideForMaxBECount = + IsSigned ? getSignedRange(Stride).getSignedMin() + : getUnsignedRange(Stride).getUnsignedMin(); + else + // Using a stride of 1 is safe when computing max backedge taken count for + // a loop with unknown stride. + StrideForMaxBECount = APInt(BitWidth, 1, IsSigned); - APInt Limit = + APInt Limit = IsSigned ? APInt::getSignedMaxValue(BitWidth) - (StrideForMaxBECount - 1) : APInt::getMaxValue(BitWidth) - (StrideForMaxBECount - 1); - // Although End can be a MAX expression we estimate MaxEnd considering only - // the case End = RHS. This is safe because in the other case (End - Start) - // is zero, leading to a zero maximum backedge taken count. - APInt MaxEnd = - IsSigned ? APIntOps::smin(getSignedRange(RHS).getSignedMax(), Limit) - : APIntOps::umin(getUnsignedRange(RHS).getUnsignedMax(), Limit); + // Although End can be a MAX expression we estimate MaxEnd considering only + // the case End = RHS. This is safe because in the other case (End - Start) + // is zero, leading to a zero maximum backedge taken count. + APInt MaxEnd = + IsSigned ? APIntOps::smin(getSignedRange(RHS).getSignedMax(), Limit) + : APIntOps::umin(getUnsignedRange(RHS).getUnsignedMax(), Limit); - const SCEV *MaxBECount; - if (isa(BECount)) - MaxBECount = BECount; - else MaxBECount = computeBECount(getConstant(MaxEnd - MinStart), getConstant(StrideForMaxBECount), false); + } if (isa(MaxBECount)) MaxBECount = BECount; -- cgit v1.2.3