Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -8324,11 +8324,40 @@
   if (ControlsExit && isLoopInvariant(RHS, L) && loopHasNoAbnormalExits(L) &&
       loopIsFiniteByAssumption(L)) {
 
-    // TODO: We can peel off any functions which are invertible *in L*.  Loop
-    // invariant terms are effectively constants for our purposes here.
+    // Peel off any functions which are invertible *in L*.  Loop invariant
+    // terms are effectively constants for our purposes here.
+    auto peekThroughInvertibleFunctions = [&](const SCEV *S) -> const SCEV * {
+      if (auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(S))
+        return ZExt->getOperand();
+      else if (auto *SExt = dyn_cast<SCEVSignExtendExpr>(S))
+        return SExt->getOperand();
+      else if (auto *Add = dyn_cast<SCEVAddExpr>(S)) {
+        const SCEV *NonInvariantOp = nullptr;
+        for (auto *Op : Add->operands()) {
+          if (isLoopInvariant(Op, L))
+            continue;
+          if (!NonInvariantOp) {
+            NonInvariantOp = Op;
+            continue;
+          }
+          if (Op != NonInvariantOp)
+            // Can't peak through this
+            return Add;
+        }
+        if (!NonInvariantOp)
+          // The add itself is invariant.
+          return Add;
+        return NonInvariantOp;
+      }
+      return S;
+    };
     auto *InnerLHS = LHS;
-    if (auto *ZExt = dyn_cast<SCEVZeroExtendExpr>(LHS))
-      InnerLHS = ZExt->getOperand();
+    while (true) {
+      auto *Temp = peekThroughInvertibleFunctions(InnerLHS);
+      if (Temp == InnerLHS)
+        break;
+      InnerLHS = Temp;
+    }
     if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(InnerLHS)) {
       auto *StrideC = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*this));
       if (!AR->hasNoSelfWrap() && AR->getLoop() == L && AR->isAffine() && 
Index: llvm/test/Analysis/ScalarEvolution/ne-overflow.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/ne-overflow.ll
+++ llvm/test/Analysis/ScalarEvolution/ne-overflow.ll
@@ -261,7 +261,9 @@
 ; CHECK-NEXT:  Determining loop execution counts for: @test_sext
 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (%N /u 2)
+; CHECK-NEXT:   Predicates:
+; CHECK-NEXT:    {0,+,2}<nuw><%for.body> Added Flags: <nssw>
 ;
 entry:
   br label %for.body
@@ -282,7 +284,10 @@
 ; CHECK-NEXT:  Determining loop execution counts for: @test_zext_of_sext
 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (%N /u 2)
+; CHECK-NEXT:   Predicates:
+; CHECK-NEXT:    {0,+,2}<nuw><%for.body> Added Flags: <nssw>
+; CHECK-NEXT:    {0,+,2}<nuw><%for.body> Added Flags: <nusw>
 ;
 entry:
   br label %for.body
@@ -304,7 +309,9 @@
 ; CHECK-NEXT:  Determining loop execution counts for: @test_zext_offset
 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((-21 + %N) /u 2)
+; CHECK-NEXT:   Predicates:
+; CHECK-NEXT:    {0,+,2}<nuw><%for.body> Added Flags: <nusw>
 ;
 entry:
   br label %for.body
@@ -326,7 +333,9 @@
 ; CHECK-NEXT:  Determining loop execution counts for: @test_sext_offset
 ; CHECK-NEXT:  Loop %for.body: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
-; CHECK-NEXT:  Loop %for.body: Unpredictable predicated backedge-taken count.
+; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is ((-21 + %N) /u 2)
+; CHECK-NEXT:   Predicates:
+; CHECK-NEXT:    {0,+,2}<nuw><%for.body> Added Flags: <nssw>
 ;
 entry:
   br label %for.body
Index: llvm/test/Analysis/ScalarEvolution/trip-count-implied-addrec.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/trip-count-implied-addrec.ll
+++ llvm/test/Analysis/ScalarEvolution/trip-count-implied-addrec.ll
@@ -60,7 +60,7 @@
 ; CHECK-NEXT:  Loop %for.body: Unpredictable max backedge-taken count.
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (128 + (-128 smax %n))
 ; CHECK-NEXT:   Predicates:
-; CHECK-NEXT:    {-128,+,1}<%for.body> Added Flags: <nssw>
+; CHECK-NEXT:    {-128,+,1}<nw><%for.body> Added Flags: <nssw>
 ;
 entry:
   br label %for.body