[SCEV] Fix isKnownPredicate

IsKnownPredicate is updated to implement the following algorithm
proposed by @sanjoy and @mkazantsev :
isKnownPredicate(Pred, LHS, RHS) {
  Collect set S all loops on which either LHS or RHS depend.
  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))
Return true if Pred, L, R is known from ranges, splitting etc.
}
This is follow-up for https://reviews.llvm.org/D42417.

Reviewers: sanjoy, mkazantsev, reames
Reviewed By: sanjoy, mkazantsev
Subscribers: llvm-commits
Differential Revision: https://reviews.llvm.org/D43507

llvm-svn: 327362

1 files changed, 67 insertions, 27 deletions

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 5aea3a4752e..72f4b1bfdfa 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -8727,38 +8727,78 @@ bool ScalarEvolution::isKnownNonZero(const SCEV *S) {
   return isKnownNegative(S) || isKnownPositive(S);
 }
 
+std::pair<const SCEV *, const SCEV *>
+ScalarEvolution::SplitIntoInitAndPostInc(const Loop *L, const SCEV *S) {
+  // Compute SCEV on entry of loop L.
+  const SCEV *Start = SCEVInitRewriter::rewrite(S, L, *this);
+  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,
                                        const SCEV *LHS, const SCEV *RHS) {
   // Canonicalize the inputs first.
   (void)SimplifyICmpOperands(Pred, LHS, RHS);
 
-  // If LHS or RHS is an addrec, check to see if the condition is true in
-  // every iteration of the loop.
-  // If LHS and RHS are both addrec, both conditions must be true in
-  // 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) &&
-        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) &&
-        isKnownOnEveryIteration(SwappedPred, RAR, LHS)) {
-      if (!LAR) return true;
-      RightGuarded = true;
-    }
-  }
-  if (LeftGuarded && RightGuarded)
-    return true;
+  // 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);
+
+  // 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.
+        if (isLoopEntryGuardedByCond(MDL, Pred, SplitLHS.first,
+                                     SplitRHS.first) &&
+            isLoopBackedgeGuardedByCond(MDL, Pred, SplitLHS.second,
+                                        SplitRHS.second))
+          return true;
+      }
+    }
+  }
 
   if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
     return true;