Index: llvm/lib/Analysis/ScalarEvolution.cpp
===================================================================
--- llvm/lib/Analysis/ScalarEvolution.cpp
+++ llvm/lib/Analysis/ScalarEvolution.cpp
@@ -5669,23 +5669,26 @@
   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());
-  assert(L && L->getHeader() == P->getParent());
-  if (!L->contains(BO->getParent()))
+  if (!L || L->getHeader() != P->getParent())
+    // If we have unreachable blocks involved, then dominance collapses and
+    // we may get trivial recurrences such as:
+    // %phi = phi i64 [%start, %entry], [%step, %unreachable]
+    // %step = add i64 %phi, %step
+    // Or the phi itself may be unreachable.  In such cases, any possible
+    // enclosing loop isn't describing the trip count of the recurrence.
+    return CR;
+
+  if (!L->contains(BO->getParent())) {
     // NOTE: This bailout should be an assert instead.  However, asserting
     // the condition here exposes a case where LoopFusion is querying SCEV
     // with malformed loop information during the midst of the transform.
     // There doesn't appear to be an obvious fix, so for the moment bailout
     // until the caller issue can be fixed.  PR49566 tracks the bug.
     return CR;
+  }
 
   // TODO: Handle ashr and lshr cases to increase minimum value reported
   if (BO->getOpcode() != Instruction::Shl || BO->getOperand(0) != P)
Index: llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll
===================================================================
--- llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll
+++ llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll
@@ -440,6 +440,60 @@
   br label %for.cond2295
 }
 
+; Was pr49856.  We can match the recurrence without a loop
+; since dominance collapses in unreachable code.  Conceptually,
+; this is a recurrence which only executes one iteration.
+define void @nonloop_recurrence() {
+; CHECK-LABEL: 'nonloop_recurrence'
+; CHECK-NEXT:  Classifying expressions for: @nonloop_recurrence
+; CHECK-NEXT:    %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ]
+; CHECK-NEXT:    --> %tmp U: [1,-2147483648) S: [0,-2147483648)
+; CHECK-NEXT:    %tmp2 = add nuw nsw i32 %tmp, 1
+; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647)
+; CHECK-NEXT:  Determining loop execution counts for: @nonloop_recurrence
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb3, %bb
+  %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ]
+  %tmp2 = add nuw nsw i32 %tmp, 1
+  ret void
+
+bb3:                                              ; No predecessors!
+  br label %bb1
+}
+
+; Tweak of pr49856 test case - analogous, but there is a loop
+; it's trip count simply doesn't relate to the single iteration
+; "recurrence" we found.
+define void @nonloop_recurrence_2() {
+; CHECK-LABEL: 'nonloop_recurrence_2'
+; CHECK-NEXT:  Classifying expressions for: @nonloop_recurrence_2
+; CHECK-NEXT:    %tmp = phi i32 [ 2, %loop ], [ %tmp2, %bb3 ]
+; CHECK-NEXT:    --> %tmp U: [1,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    %tmp2 = add nuw nsw i32 %tmp, 1
+; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @nonloop_recurrence_2
+; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+bb:
+  br label %loop
+
+loop:
+  br label %bb1
+bb1:                                              ; preds = %bb3, %loop
+  %tmp = phi i32 [ 2, %loop ], [ %tmp2, %bb3 ]
+  %tmp2 = add nuw nsw i32 %tmp, 1
+  br label %loop
+
+bb3:                                              ; No predecessors!
+  br label %bb1
+}
+
+
 ; Next batch of tests show where we can get tighter ranges on ashr/lshr
 ; by using the trip count information on the loop.