Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -5664,17 +5664,18 @@
   if (!P)
     return CR;
 
+  // Make sure that no Phi input comes from an unreachable block. Otherwise,
+  // even the values that are not available in these blocks may come from them,
+  // and this leads to false-positive recurrence test.
+  for (auto *Pred : predecessors(P->getParent()))
+    if (!DT.isReachableFromEntry(Pred))
+      return CR;
+
   BinaryOperator *BO;
   Value *Start, *Step;
   if (!matchSimpleRecurrence(P, BO, Start, Step))
     return CR;
 
-  if (!DT.isReachableFromEntry(P->getParent()) ||
-      !DT.isReachableFromEntry(BO->getParent()))
-    // If either is in unreachable code, dominance collapses and none of our
-    // expected post conditions about loops hold.
-    return CR;
-
   // If we found a recurrence in reachable code, we must be in a loop. Note
   // that BO might be in some subloop of L, and that's completely okay.
   auto *L = LI.getLoopFor(P->getParent());
Index: llvm/test/Analysis/ScalarEvolution/pr49856.ll
===================================================================
--- /dev/null
+++ llvm/test/Analysis/ScalarEvolution/pr49856.ll
@@ -0,0 +1,76 @@
+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt < %s -analyze -enable-new-pm=0 -scalar-evolution | FileCheck %s
+; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @test() {
+; CHECK-LABEL: 'test'
+; CHECK-NEXT:  Classifying expressions for: @test
+; CHECK-NEXT:    %tmp = phi i32 [ 2, %bb1 ], [ %tmp6, %bb9 ]
+; CHECK-NEXT:    --> %tmp U: [1,-2147483648) S: [0,-2147483648)
+; CHECK-NEXT:    %tmp6 = add nuw nsw i32 %tmp, 1
+; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647)
+; CHECK-NEXT:    %tmp15 = phi i32 [ %tmp16, %bb14 ], [ undef, %bb13 ]
+; CHECK-NEXT:    --> {undef,+,1}<nsw><%bb14> U: full-set S: full-set Exits: (-1 + (26 smax (1 + undef)))<nsw> LoopDispositions: { %bb14: Computable }
+; CHECK-NEXT:    %tmp16 = add nsw i32 %tmp15, 1
+; CHECK-NEXT:    --> {(1 + undef),+,1}<nsw><%bb14> U: full-set S: full-set Exits: (26 smax (1 + undef)) LoopDispositions: { %bb14: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @test
+; CHECK-NEXT:  Loop %bb14: backedge-taken count is (-1 + (-1 * undef) + (26 smax (1 + undef)))
+; CHECK-NEXT:  Loop %bb14: max backedge-taken count is -2147483622
+; CHECK-NEXT:  Loop %bb14: Predicated backedge-taken count is (-1 + (-1 * undef) + (26 smax (1 + undef)))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %bb14: Trip multiple is 1
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb
+  br label %bb5
+
+bb2:                                              ; preds = %bb2
+  br label %bb2
+
+bb3:                                              ; preds = %bb3
+  br label %bb3
+
+bb4:                                              ; preds = %bb4
+  br label %bb4
+
+bb5:                                              ; preds = %bb9, %bb1
+  %tmp = phi i32 [ 2, %bb1 ], [ %tmp6, %bb9 ]
+  %tmp6 = add nuw nsw i32 %tmp, 1
+  %tmp7 = icmp ult i32 %tmp6, undef
+  br i1 %tmp7, label %bb13, label %bb18
+
+bb8:                                              ; preds = %bb8
+  br label %bb8
+
+bb9:                                              ; No predecessors!
+  br label %bb5
+
+bb10:                                             ; preds = %bb10
+  br label %bb10
+
+bb11:                                             ; preds = %bb11
+  br label %bb11
+
+bb12:                                             ; preds = %bb12
+  br label %bb12
+
+bb13:                                             ; preds = %bb5
+  br label %bb14
+
+bb14:                                             ; preds = %bb14, %bb13
+  %tmp15 = phi i32 [ %tmp16, %bb14 ], [ undef, %bb13 ]
+  %tmp16 = add nsw i32 %tmp15, 1
+  %tmp17 = icmp sgt i32 %tmp16, 25
+  br i1 %tmp17, label %bb19, label %bb14
+
+bb18:                                             ; preds = %bb5
+  unreachable
+
+bb19:                                             ; preds = %bb14
+  ret void
+}