From 087310c71e5c1c70818ac62acd781860d59a6ce7 Mon Sep 17 00:00:00 2001 From: Philip Reames Date: Tue, 13 Jul 2021 11:51:02 -0700 Subject: [PATCH] [SCEV] Strengthen inference of RHS > Start in howManyLessThans Split off from D105216 to simplify review. Rewritten with a lambda to be easier to follow. Comments clarified. Sorry for no test case, this is tricky to exercise with the current structure of the code. It's about to be hit more frequently in a follow up patch, and the change itself is simple. --- llvm/lib/Analysis/ScalarEvolution.cpp | 23 +++++++++++++++++++++-- 1 file changed, 21 insertions(+), 2 deletions(-) diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 5cb96a2..c6a1328 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -11742,10 +11742,29 @@ ScalarEvolution::howManyLessThans(const SCEV *LHS, const SCEV *RHS, if (isLoopEntryGuardedByCond(L, Cond, getMinusSCEV(OrigStart, Stride), OrigRHS)) BECount = BECountIfBackedgeTaken; else { + auto canProveRHSGreaterThanEqualStart = [&]() { + auto CondGE = IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; + if (isLoopEntryGuardedByCond(L, CondGE, OrigRHS, OrigStart)) + return true; + + // (RHS > Start - 1) implies RHS >= Start. + // * "RHS >= Start" is trivially equivalent to "RHS > Start - 1" if + // "Start - 1" doesn't overflow. + // * For signed comparison, if Start - 1 does overflow, it's equal + // to INT_MAX, and "RHS >s INT_MAX" is trivially false. + // * For unsigned comparison, if Start - 1 does overflow, it's equal + // to UINT_MAX, and "RHS >u UINT_MAX" is trivially false. + // + // FIXME: Should isLoopEntryGuardedByCond do this for us? + auto CondGT = IsSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; + auto *StartMinusOne = getAddExpr(OrigStart, + getMinusOne(OrigStart->getType())); + return isLoopEntryGuardedByCond(L, CondGT, OrigRHS, StartMinusOne); + }; + // If we know that RHS >= Start in the context of loop, then we know that // max(RHS, Start) = RHS at this point. - if (isLoopEntryGuardedByCond( - L, IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE, OrigRHS, OrigStart)) + if (canProveRHSGreaterThanEqualStart()) End = RHS; else End = IsSigned ? getSMaxExpr(RHS, Start) : getUMaxExpr(RHS, Start); -- 2.7.4