Index: lib/Analysis/ScalarEvolution.cpp
===================================================================
--- lib/Analysis/ScalarEvolution.cpp
+++ lib/Analysis/ScalarEvolution.cpp
@@ -8718,34 +8718,71 @@
   // 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) &&
-        isLoopEntryGuardedByCond(L, Pred, LAR->getStart(), RHS) &&
-        isLoopBackedgeGuardedByCond(L, Pred, LAR->getPostIncExpr(*this), RHS)) {
-      if (!RAR) return true;
-      LeftGuarded = true;
-    }
-  }
-  if (RAR) {
-    const Loop *L = RAR->getLoop();
-    if (isAvailableAtLoopEntry(LHS, L) &&
-        isLoopEntryGuardedByCond(L, Pred, LHS, RAR->getStart()) &&
-        isLoopBackedgeGuardedByCond(L, Pred, LHS, RAR->getPostIncExpr(*this))) {
-      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;
+  getLoopUseLists(LHS, LoopsUsed);
+  getLoopUseLists(RHS, LoopsUsed);
+
+  auto MostDominatedLoop = [&]()->const Loop * {
+    const Loop *MDL = nullptr;
+    for (auto *L : LoopsUsed) {
+      if (MDL) {
+        if (DT.dominates(MDL->getHeader(), L->getHeader()))
+          MDL = L;
+        else if (!DT.dominates(L->getHeader(), MDL->getHeader()))
+          // We have two Loops which does not dominate each other, so bail out.
+          return nullptr;
+      } else
+        MDL = L;
+    }
+    return MDL;
+  };
+
+  auto CheckThroughLoop = [](ScalarEvolution &SE, const Loop *L,
+                             ICmpInst::Predicate Pred, const SCEV *LHS,
+                             const SCEV *RHS) {
+    // Compute LHS and RHS on entry of loop L.
+    // We allow other loops then L to be in LHS/RHS.
+    auto *StartLHS = SCEVInitRewriter::rewrite(LHS, L, SE, true);
+    if (StartLHS == SE.getCouldNotCompute())
+      return false;
+    auto *StartRHS = SCEVInitRewriter::rewrite(RHS, L, SE, true);
+    if (StartRHS == SE.getCouldNotCompute())
+      return false;
+    // Compute post increment of LHS and RHS for loop L.
+    // We allow other loops then L to be in LHS/RHS.
+    auto *PostIncLHS = SCEVPostIncRewriter::rewrite(LHS, L, SE, true);
+    assert(PostIncLHS != SE.getCouldNotCompute() &&
+           "Unexpected could not compute");
+    auto *PostIncRHS = SCEVPostIncRewriter::rewrite(RHS, L, SE, true);
+    assert(PostIncRHS != SE.getCouldNotCompute() &&
+           "Unexpected could not compute");
+    // Now we are ready to check.
+    return SE.isLoopEntryGuardedByCond(L, Pred, StartLHS, StartRHS) &&
+           SE.isLoopBackedgeGuardedByCond(L, Pred, PostIncLHS, PostIncRHS);
+  };
+  if (auto *L = MostDominatedLoop())
+    if (CheckThroughLoop(*this, L, Pred, LHS, RHS))
+      return true;
 
   if (isKnownPredicateViaSplitting(Pred, LHS, RHS))
     return true;