[SCEV][NFC] Factor out common logic into a separate method

[mkazantsev]

Summary

SCEV has multiple occurences of code when we need to prove some predicate on
every iteration of a loop and do it with invocations of couple isLoopEntryGuardedByCond,
isLoopBackedgeGuardedByCond. This patch factors out these two calls into a separate
method. It is a preparation step to extend this logic: it is not the only way how we can prove
such conditions.

[sanjoy]

include/llvm/Analysis/ScalarEvolution.h

838 ↗

(On Diff #134571)

How about calling this isKnownViaInduction?

[mkazantsev]

include/llvm/Analysis/ScalarEvolution.h

838 ↗

(On Diff #134571)

You are right, current implementation only proves via induction, but I plan a follow-up change https://reviews.llvm.org/D43375 which proves via monotonicity and not induction. So let's keep it as is.

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

public:
   /// Test if the given expression is known to be non-zero.
   bool isKnownNonZero(const SCEV *S);
 
   /// Test if the given expression is known to satisfy the condition described
   /// by Pred, LHS, and RHS.
   bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS,
                         const SCEV *RHS);
 
+  /// Test if the condition described by Pred, LHS, RHS is known to be true on
+  /// every iteration of the loop of the recurrency LHS.
+  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

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

if (AR->isAffine()) {
         // value the addrec is safe. Also, if the entry is guarded by
         // a comparison with the start value and the backedge is
         // guarded by a comparison with the post-inc value, the addrec
         // is safe.
         if (isKnownPositive(Step)) {
           const SCEV *N = getConstant(APInt::getMinValue(BitWidth) -
                                       getUnsignedRangeMax(Step));
           if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT, AR, N) ||
-              (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_ULT, Start, N) &&
-               isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_ULT,
-                                           AR->getPostIncExpr(*this), N))) {
+              isKnownOnEveryIteration(ICmpInst::ICMP_ULT, AR, N)) {
             // Cache knowledge of AR NUW, which is propagated to this
             // AddRec.
             const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNUW);
             // Return the expression with the addrec on the outside.
             return getAddRecExpr(
                 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty, this,
                                                          Depth + 1),
                 getZeroExtendExpr(Step, Ty, Depth + 1), L,
                 AR->getNoWrapFlags());
           }
         } else if (isKnownNegative(Step)) {
           const SCEV *N = getConstant(APInt::getMaxValue(BitWidth) -
                                       getSignedRangeMin(Step));
           if (isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT, AR, N) ||
-              (isLoopEntryGuardedByCond(L, ICmpInst::ICMP_UGT, Start, N) &&
-               isLoopBackedgeGuardedByCond(L, ICmpInst::ICMP_UGT,
-                                           AR->getPostIncExpr(*this), N))) {
+              isKnownOnEveryIteration(ICmpInst::ICMP_UGT, AR, N)) {
             // Cache knowledge of AR NW, which is propagated to this
             // AddRec.  Negative step causes unsigned wrap, but it
             // still can't self-wrap.
             const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNW);
             // Return the expression with the addrec on the outside.
             return getAddRecExpr(
                 getExtendAddRecStart<SCEVZeroExtendExpr>(AR, Ty, this,
                                                          Depth + 1),
if (AR->isAffine()) {
         // a comparison with the start value and the backedge is
         // guarded by a comparison with the post-inc value, the addrec
         // is safe.
         ICmpInst::Predicate Pred;
         const SCEV *OverflowLimit =
             getSignedOverflowLimitForStep(Step, &Pred, this);
         if (OverflowLimit &&
             (isLoopBackedgeGuardedByCond(L, Pred, AR, OverflowLimit) ||
-             (isLoopEntryGuardedByCond(L, Pred, Start, OverflowLimit) &&
-              isLoopBackedgeGuardedByCond(L, Pred, AR->getPostIncExpr(*this),
-                                          OverflowLimit)))) {
+             isKnownOnEveryIteration(Pred, AR, OverflowLimit))) {
           // Cache knowledge of AR NSW, then propagate NSW to the wide AddRec.
           const_cast<SCEVAddRecExpr *>(AR)->setNoWrapFlags(SCEV::FlagNSW);
           return getAddRecExpr(
               getExtendAddRecStart<SCEVSignExtendExpr>(AR, Ty, this, Depth + 1),
               getSignExtendExpr(Step, Ty, Depth + 1), L, AR->getNoWrapFlags());
         }
       }
 
bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred,
   // every iteration of the loop.
   const SCEVAddRecExpr *LAR = dyn_cast<SCEVAddRecExpr>(LHS);
   const SCEVAddRecExpr *RAR = dyn_cast<SCEVAddRecExpr>(RHS);
   bool LeftGuarded = false;
   bool RightGuarded = false;
   if (LAR) {
     const Loop *L = LAR->getLoop();
     if (isAvailableAtLoopEntry(RHS, L) &&
-        isLoopEntryGuardedByCond(L, Pred, LAR->getStart(), RHS) &&
-        isLoopBackedgeGuardedByCond(L, Pred, LAR->getPostIncExpr(*this), RHS)) {
+        isKnownOnEveryIteration(Pred, LAR, RHS)) {
       if (!RAR) return true;
       LeftGuarded = true;
     }
   }
   if (RAR) {
     const Loop *L = RAR->getLoop();
+    auto SwappedPred = ICmpInst::getSwappedPredicate(Pred);
     if (isAvailableAtLoopEntry(LHS, L) &&
-        isLoopEntryGuardedByCond(L, Pred, LHS, RAR->getStart()) &&
-        isLoopBackedgeGuardedByCond(L, Pred, LHS, RAR->getPostIncExpr(*this))) {
+        isKnownOnEveryIteration(SwappedPred, RAR, LHS)) {
       if (!LAR) return true;
       RightGuarded = true;
     }
   }
   if (LeftGuarded && RightGuarded)
     return true;
 
   if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
     return true;
 
   // Otherwise see what can be done with some simple reasoning.
   return isKnownViaNonRecursiveReasoning(Pred, LHS, RHS);
 }
 
+bool ScalarEvolution::isKnownOnEveryIteration(ICmpInst::Predicate Pred,
+                                              const SCEVAddRecExpr *LHS,
+                                              const SCEV *RHS) {
+  const Loop *L = LHS->getLoop();
+  return isLoopEntryGuardedByCond(L, Pred, LHS->getStart(), RHS) &&
+         isLoopBackedgeGuardedByCond(L, Pred, LHS->getPostIncExpr(*this), RHS);
+}
+
 bool ScalarEvolution::isMonotonicPredicate(const SCEVAddRecExpr *LHS,
                                            ICmpInst::Predicate Pred,
                                            bool &Increasing) {
   bool Result = isMonotonicPredicateImpl(LHS, Pred, Increasing);
 
 #ifndef NDEBUG
   // Verify an invariant: inverting the predicate should turn a monotonically
   // increasing change to a monotonically decreasing one, and vice versa.