Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -7822,9 +7822,10 @@
   Idx = getSCEVAtScope(Idx, L);
 
   // We can only recognize very limited forms of loop index expressions, in
-  // particular, only affine AddRec's like {C1,+,C2}.
+  // particular, only affine AddRec's like {C1,+,C2}<L2> where L is inside L2.
   const SCEVAddRecExpr *IdxExpr = dyn_cast<SCEVAddRecExpr>(Idx);
-  if (!IdxExpr || !IdxExpr->isAffine() || isLoopInvariant(IdxExpr, L) ||
+  if (!IdxExpr || !IdxExpr->getLoop()->contains(L) || !IdxExpr->isAffine() ||
+      isLoopInvariant(IdxExpr, L) ||
       !isa<SCEVConstant>(IdxExpr->getOperand(0)) ||
       !isa<SCEVConstant>(IdxExpr->getOperand(1)))
     return getCouldNotCompute();
Index: llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
===================================================================
--- /dev/null
+++ llvm/test/Analysis/ScalarEvolution/incorrect-exit-count.ll
@@ -0,0 +1,136 @@
+; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
+
+@b = dso_local global i32 5, align 4
+@__const.f.g = private unnamed_addr constant [1 x [4 x i16]] [[4 x i16] [i16 5, i16 0, i16 0, i16 2]], align 2
+@a = common dso_local global i32 0, align 4
+@c = common dso_local global i32 0, align 4
+@d = common dso_local global i32 0, align 4
+@e = common dso_local global i32 0, align 4
+
+define dso_local i32 @f() {
+; CHECK:  -->  {2,+,-1}<nsw><%for.cond1.preheader> U: [0,3) S: [0,3)    Exits: <<Unknown>>
+; CHECK:    Loop %for.cond1.preheader: <multiple exits> Unpredictable backedge-taken count.
+; CHECK:    exit count for for.cond6: ***COULDNOTCOMPUTE***
+; CHECK:    exit count for for.cond6.1: ***COULDNOTCOMPUTE***
+; CHECK:    exit count for for.cond6.2: ***COULDNOTCOMPUTE***
+; CHECK:    exit count for for.cond6.3: ***COULDNOTCOMPUTE***
+; CHECK:    exit count for for.inc13.3: 2
+; CHECK:  Loop %for.cond1.preheader: max backedge-taken count is 2
+; CHECK:  Loop %for.cond1.preheader: Unpredictable predicated backedge-taken count.
+
+entry:
+  store i32 3, i32* @a, align 4
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %entry, %for.inc13.3
+  %storemerge23 = phi i32 [ 3, %entry ], [ %dec16, %for.inc13.3 ]
+  br label %for.cond3.preheader
+
+for.cond3.preheader:                              ; preds = %for.cond1.preheader
+  br label %for.cond6
+
+for.cond6:                                        ; preds = %for.end, %for.cond3.preheader
+  %storemerge1921 = phi i32 [ 3, %for.cond3.preheader ], [ %dec, %for.end ]
+  %idxprom20 = zext i32 %storemerge1921 to i64
+  %arrayidx7 = getelementptr inbounds [1 x [4 x i16]], [1 x [4 x i16]]* @__const.f.g, i64 0, i64 0, i64 %idxprom20
+  %0 = load i16, i16* %arrayidx7, align 2
+  %tobool8 = icmp eq i16 %0, 0
+  br i1 %tobool8, label %if.end.loopexit, label %for.end
+
+if.end.loopexit:                                  ; preds = %for.cond6
+  %storemerge1822.lcssa.ph = phi i32 [ 0, %for.cond6 ]
+  br label %if.end
+
+if.end.loopexit27:                                ; preds = %for.cond6.1
+  %storemerge1822.lcssa.ph28 = phi i32 [ 1, %for.cond6.1 ]
+  br label %if.end
+
+if.end.loopexit29:                                ; preds = %for.cond6.2
+  %storemerge1822.lcssa.ph30 = phi i32 [ 2, %for.cond6.2 ]
+  br label %if.end
+
+if.end.loopexit31:                                ; preds = %for.cond6.3
+  %storemerge1822.lcssa.ph32 = phi i32 [ 3, %for.cond6.3 ]
+  br label %if.end
+
+if.end:                                           ; preds = %if.end.loopexit31, %if.end.loopexit29, %if.end.loopexit27, %if.end.loopexit
+  %storemerge1822.lcssa = phi i32 [ %storemerge1822.lcssa.ph, %if.end.loopexit ], [ %storemerge1822.lcssa.ph28, %if.end.loopexit27 ], [ %storemerge1822.lcssa.ph30, %if.end.loopexit29 ], [ %storemerge1822.lcssa.ph32, %if.end.loopexit31 ]
+  store i32 %storemerge1822.lcssa, i32* @c, align 4
+  store i32 2, i32* @d, align 4
+  %1 = load i32, i32* @e, align 4
+  br label %cleanup
+
+for.end:                                          ; preds = %for.cond6
+  %2 = load volatile i32, i32* @b, align 4
+  %tobool9 = icmp eq i32 %2, 0
+  %dec = add nsw i32 %storemerge1921, -1
+  br i1 %tobool9, label %for.cond6, label %for.inc13
+
+for.inc13:                                        ; preds = %for.end
+  br label %for.cond6.1
+
+cleanup.loopexit:                                 ; preds = %for.inc13.3
+  %inc.lcssa.lcssa = phi i32 [ 4, %for.inc13.3 ]
+  store i32 %inc.lcssa.lcssa, i32* @c, align 4
+  br label %cleanup
+
+cleanup:                                          ; preds = %cleanup.loopexit, %if.end
+  %retval.0 = phi i32 [ %1, %if.end ], [ 0, %cleanup.loopexit ]
+  ret i32 %retval.0
+
+for.cond6.1:                                      ; preds = %for.end.1, %for.inc13
+  %storemerge1921.1 = phi i32 [ 3, %for.inc13 ], [ %dec.1, %for.end.1 ]
+  %idxprom20.1 = zext i32 %storemerge1921.1 to i64
+  %arrayidx7.1 = getelementptr inbounds [1 x [4 x i16]], [1 x [4 x i16]]* @__const.f.g, i64 0, i64 0, i64 %idxprom20.1
+  %3 = load i16, i16* %arrayidx7.1, align 2
+  %tobool8.1 = icmp eq i16 %3, 0
+  br i1 %tobool8.1, label %if.end.loopexit27, label %for.end.1
+
+for.end.1:                                        ; preds = %for.cond6.1
+  %4 = load volatile i32, i32* @b, align 4
+  %tobool9.1 = icmp eq i32 %4, 0
+  %dec.1 = add nsw i32 %storemerge1921.1, -1
+  br i1 %tobool9.1, label %for.cond6.1, label %for.inc13.1
+
+for.inc13.1:                                      ; preds = %for.end.1
+  br label %for.cond6.2
+
+for.cond6.2:                                      ; preds = %for.end.2, %for.inc13.1
+  %storemerge1921.2 = phi i32 [ 3, %for.inc13.1 ], [ %dec.2, %for.end.2 ]
+  %idxprom20.2 = zext i32 %storemerge1921.2 to i64
+  %arrayidx7.2 = getelementptr inbounds [1 x [4 x i16]], [1 x [4 x i16]]* @__const.f.g, i64 0, i64 0, i64 %idxprom20.2
+  %5 = load i16, i16* %arrayidx7.2, align 2
+  %tobool8.2 = icmp eq i16 %5, 0
+  br i1 %tobool8.2, label %if.end.loopexit29, label %for.end.2
+
+for.end.2:                                        ; preds = %for.cond6.2
+  %6 = load volatile i32, i32* @b, align 4
+  %tobool9.2 = icmp eq i32 %6, 0
+  %dec.2 = add nsw i32 %storemerge1921.2, -1
+  br i1 %tobool9.2, label %for.cond6.2, label %for.inc13.2
+
+for.inc13.2:                                      ; preds = %for.end.2
+  br label %for.cond6.3
+
+for.cond6.3:                                      ; preds = %for.end.3, %for.inc13.2
+  %storemerge1921.3 = phi i32 [ 3, %for.inc13.2 ], [ %dec.3, %for.end.3 ]
+  %idxprom20.3 = zext i32 %storemerge1921.3 to i64
+  %arrayidx7.3 = getelementptr inbounds [1 x [4 x i16]], [1 x [4 x i16]]* @__const.f.g, i64 0, i64 0, i64 %idxprom20.3
+  %7 = load i16, i16* %arrayidx7.3, align 2
+  %tobool8.3 = icmp eq i16 %7, 0
+  br i1 %tobool8.3, label %if.end.loopexit31, label %for.end.3
+
+for.end.3:                                        ; preds = %for.cond6.3
+  %8 = load volatile i32, i32* @b, align 4
+  %tobool9.3 = icmp eq i32 %8, 0
+  %dec.3 = add nsw i32 %storemerge1921.3, -1
+  br i1 %tobool9.3, label %for.cond6.3, label %for.inc13.3
+
+for.inc13.3:                                      ; preds = %for.end.3
+  %storemerge1921.lcssa25.3 = phi i32 [ %storemerge1921.3, %for.end.3 ]
+  store i32 %storemerge1921.lcssa25.3, i32* @d, align 4
+  %dec16 = add nsw i32 %storemerge23, -1
+  store i32 %dec16, i32* @a, align 4
+  %tobool = icmp eq i32 %dec16, 0
+  br i1 %tobool, label %cleanup.loopexit, label %for.cond1.preheader
+}