[SCEV] Factor out isKnownViaInduction. NFC.

[skatkov]

Summary

This just extracts the isKnownViaInduction from isKnownPredicate.

[mkazantsev]

LGTM with nits. We also have method isKnownOnEveryIteration which, I believe, is a weaker version of this one. We should consider replacing of it with this one I think.

lib/Analysis/ScalarEvolution.cpp

8724 ↗

(On Diff #138672)

Assert that SplitLHS.second and SplitRHS.second are also not getCouldNotCompute() at this point?

8731 ↗

(On Diff #138672)

Please clang-format that.

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

public:
   /// second = {1, +, 1}<L1> + {0, +, 1}<L2>
   /// We can see that for the first AddRec sub-expression it was replaced with
   /// 0 (initial value) for the first element and to {1, +, 1}<L1> (post
   /// increment value) for the second one. In both cases AddRec expression
   /// related to L2 remains the same.
   std::pair<const SCEV *, const SCEV *> SplitIntoInitAndPostInc(const Loop *L,
                                                                 const SCEV *S);
 
+  /// We'd like to check the predicate on every iteration of the most dominated
+  /// loop between loops used in LHS and RHS.
+  /// To do this we use the following list of steps:
+  /// 1. Collect set S all loops on which either LHS or RHS depend.
+  /// 2. If S is non-empty
+  /// a. Let PD be the element of S which is dominated by all other elements.
+  /// b. Let E(LHS) be value of LHS on entry of PD.
+  ///    To get E(LHS), we should just take LHS and replace all AddRecs that are
+  ///    attached to PD on with their entry values.
+  ///    Define E(RHS) in the same way.
+  /// c. Let B(LHS) be value of L on backedge of PD.
+  ///    To get B(LHS), we should just take LHS and replace all AddRecs that are
+  ///    attached to PD on with their backedge values.
+  ///    Define B(RHS) in the same way.
+  /// d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
+  ///    so we can assert on that.
+  /// e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
+  ///                   isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
+  bool isKnownViaInduction(ICmpInst::Predicate Pred, const SCEV *LHS,
+                           const SCEV *RHS);
+
   /// 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,

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::SplitIntoInitAndPostInc(const Loop *L, const SCEV *S) {
   if (Start == getCouldNotCompute())
     return { Start, Start };
   // Compute post increment SCEV for loop L.
   const SCEV *PostInc = SCEVPostIncRewriter::rewrite(S, L, *this);
   assert(PostInc != getCouldNotCompute() && "Unexpected could not compute");
   return { Start, PostInc };
 }
 
-bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred,
+bool ScalarEvolution::isKnownViaInduction(ICmpInst::Predicate Pred,
                                           const SCEV *LHS, const SCEV *RHS) {
-  // Canonicalize the inputs first.
-  (void)SimplifyICmpOperands(Pred, LHS, RHS);
-
-  // We'd like to check the predicate on every iteration of the most dominated
-  // loop between loops used in LHS and RHS.
-  // To do this we use the following list of steps:
-  // 1. Collect set S all loops on which either LHS or RHS depend.
-  // 2. If S is non-empty
-  // a. Let PD be the element of S which is dominated by all other elements of S
-  // b. Let E(LHS) be value of LHS on entry of PD.
-  //    To get E(LHS), we should just take LHS and replace all AddRecs that are
-  //    attached to PD on with their entry values.
-  //    Define E(RHS) in the same way.
-  // c. Let B(LHS) be value of L on backedge of PD.
-  //    To get B(LHS), we should just take LHS and replace all AddRecs that are
-  //    attached to PD on with their backedge values.
-  //    Define B(RHS) in the same way.
-  // d. Note that E(LHS) and E(RHS) are automatically available on entry of PD,
-  //    so we can assert on that.
-  // e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) &&
-  //                   isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
-
   // First collect all loops.
   SmallPtrSet<const Loop *, 8> LoopsUsed;
   getUsedLoops(LHS, LoopsUsed);
   getUsedLoops(RHS, LoopsUsed);
 
+  if (LoopsUsed.empty())
+    return false;
+
   // Domination relationship must be a linear order on collected loops.
 #ifndef NDEBUG
   for (auto *L1 : LoopsUsed)
     for (auto *L2 : LoopsUsed)
       assert((DT.dominates(L1->getHeader(), L2->getHeader()) ||
               DT.dominates(L2->getHeader(), L1->getHeader())) &&
              "Domination relationship is not a linear order");
 #endif
-  if (!LoopsUsed.empty()) {
-    const Loop *MDL = *std::max_element(LoopsUsed.begin(), LoopsUsed.end(),
+  
                                         [&](const Loop *L1, const Loop *L2) {
                          return DT.dominates(L1->getHeader(), L2->getHeader());
                        });
 
-    // Get init and post increment value for LHS.
-    auto SplitLHS = SplitIntoInitAndPostInc(MDL, LHS);
-    if (SplitLHS.first != getCouldNotCompute()) {
-      // if LHS does not contain unknown non-invariant SCEV then
-      // get init and post increment value for RHS.
-      auto SplitRHS = SplitIntoInitAndPostInc(MDL, RHS);
-      if (SplitRHS.first != getCouldNotCompute()) {
-        // if RHS does not contain unknown non-invariant SCEV then
-        // check whether implication is possible.
-        // It is possible that init SCEV contains an invariant load but it does
-        // not dominate MDL and is not available at MDL loop entry, so we should
-        // check it here.
-        if (isAvailableAtLoopEntry(SplitLHS.first, MDL) &&
-            isAvailableAtLoopEntry(SplitRHS.first, MDL)) {
-          if (isLoopEntryGuardedByCond(MDL, Pred, SplitLHS.first,
-                                       SplitRHS.first) &&
-              isLoopBackedgeGuardedByCond(MDL, Pred, SplitLHS.second,
-                                          SplitRHS.second))
-            return true;
-        }
-      }
-    }
-  }
+  // if LHS contains unknown non-invariant SCEV then bail out.
+  if (SplitLHS.first == getCouldNotCompute())
+    return false;
+  assert (SplitLHS.first != getCouldNotCompute() && "Unexpected CNC");
+  // Get init and post increment value for RHS.
+  // if RHS contains unknown non-invariant SCEV then bail out.
+  if (SplitRHS.first == getCouldNotCompute())
+    return false;
+  assert (SplitRHS.first != getCouldNotCompute() && "Unexpected CNC");
+  if (!isAvailableAtLoopEntry(SplitLHS.first, MDL) ||
+      !isAvailableAtLoopEntry(SplitRHS.first, MDL))
+    return false;
+
+  return isLoopEntryGuardedByCond(MDL, Pred, SplitLHS.first, SplitRHS.first) &&
+                                     SplitRHS.second);
 
+bool ScalarEvolution::isKnownPredicate(ICmpInst::Predicate Pred,
+                                       const SCEV *LHS, const SCEV *RHS) {
+  // Canonicalize the inputs first.
+  (void)SimplifyICmpOperands(Pred, LHS, RHS);
+
+  if (isKnownViaInduction(Pred, LHS, RHS))
+    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,