Index: llvm/lib/Transforms/Scalar/JumpThreading.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/JumpThreading.cpp
+++ llvm/lib/Transforms/Scalar/JumpThreading.cpp
@@ -447,8 +447,15 @@
           // BB's parent until a DTU->getDomTree() event.
           LVI->eraseBlock(&BB);
           Changed = true;
+          continue;
         }
       }
+
+      // We may hit cycles, just add it to Unreachable.
+      if (!DTU->getDomTree().isReachableFromEntry(&BB)) {
+        Unreachable.insert(&BB);
+        Changed = true;
+      }
     }
     EverChanged |= Changed;
   } while (Changed);
Index: llvm/test/Transforms/JumpThreading/PR33357-lvi-recursion.ll
===================================================================
--- llvm/test/Transforms/JumpThreading/PR33357-lvi-recursion.ll
+++ llvm/test/Transforms/JumpThreading/PR33357-lvi-recursion.ll
@@ -5,9 +5,9 @@
 ; CHECK: bb6:
 ; CHECK: bb2:
 ; CHECK: bb3:
+; CHECK: bb4:
 ; CHECK-NOT: bb0:
 ; CHECK-NOT: bb1:
-; CHECK-NOT: bb4:
 ; CHECK-NOT: bb5:
 define void @f(i32 %p1) {
 bb0:
Index: llvm/test/Transforms/JumpThreading/PR44611-across-header-hang.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/JumpThreading/PR44611-across-header-hang.ll
@@ -0,0 +1,55 @@
+; RUN: opt -S < %s -jump-threading -jump-threading-across-loop-headers | FileCheck %s
+
+; CHECK-LABEL: @func
+; Just check that we don't hang on this test.
+
+define void @func() {
+bb:
+  %tmp3 = alloca [2 x [3 x [2 x i32]]], align 4
+  br label %bb6
+
+bb6:                                              ; preds = %bb7, %bb
+  %tmp1.0 = phi i32 [ undef, %bb ], [ %tmp1.1, %bb7 ]
+  %tmp2.0 = phi i32 [ undef, %bb ], [ %tmp2.1, %bb7 ]
+  br label %bb7
+
+bb7:                                              ; preds = %bb56, %bb6
+  %tmp1.1 = phi i32 [ %tmp1.0, %bb6 ], [ 1, %bb56 ]
+  %tmp2.1 = phi i32 [ %tmp2.0, %bb6 ], [ %tmp25, %bb56 ]
+  %tmp9 = icmp slt i32 %tmp1.1, 2
+  br i1 %tmp9, label %bb10, label %bb6
+
+bb10:                                             ; preds = %bb7
+  %tmp12 = sext i32 %tmp1.1 to i64
+  %tmp19 = getelementptr inbounds [2 x [3 x [2 x i32]]], [2 x [3 x [2 x i32]]]* %tmp3, i64 0, i64 %tmp12, i64 %tmp12, i64 %tmp12
+  %tmp20 = load i32, i32* %tmp19, align 4
+  %0 = and i32 %tmp20, 1
+  %tmp25 = or i32 %tmp2.1, %0
+  br label %bb27
+
+bb27:                                             ; preds = %bb53, %bb10
+  %tmp.0 = phi i64 [ -3, %bb10 ], [ %tmp55, %bb53 ]
+  %tmp29 = icmp eq i64 %tmp.0, 17
+  br i1 %tmp29, label %bb56, label %bb31
+
+bb31:                                             ; preds = %bb27, %bb34
+  %tmp5.0 = phi i32 [ %tmp36, %bb34 ], [ 0, %bb27 ]
+  %tmp33 = icmp ult i32 %tmp5.0, 6
+  br i1 %tmp33, label %bb34, label %bb37
+
+bb34:                                             ; preds = %bb31
+  %tmp36 = add nuw nsw i32 %tmp5.0, 1
+  br label %bb31
+
+bb37:                                             ; preds = %bb31
+  %tmp48 = icmp eq i32 %tmp20, 0
+  br i1 %tmp48, label %bb53, label %bb56
+
+bb53:                                             ; preds = %bb37
+  %tmp55 = add nsw i64 %tmp.0, 1
+  br label %bb27
+
+bb56:                                             ; preds = %bb27, %bb37
+  br label %bb7
+}
+
Index: llvm/test/Transforms/JumpThreading/removed-use.ll
===================================================================
--- llvm/test/Transforms/JumpThreading/removed-use.ll
+++ llvm/test/Transforms/JumpThreading/removed-use.ll
@@ -3,7 +3,10 @@
 ; CHECK: bb6:
 ; CHECK-NEXT: ret void
 ; CHECK: bb3:
+; CHECK: br i1 %p, label %bb4, label %bb3
+; CHECK: bb4:
 ; CHECK: br label %bb3
+
 define void @foo() {
 entry:
   br i1 true, label %bb6, label %bb3
@@ -21,7 +24,7 @@
   %x1 = phi i32 [ %x0, %bb3 ], [ %x0, %bb4 ]
   %z  = phi i32 [ 0, %bb3 ], [ 1, %bb4 ]
   %q  = icmp eq i32 %z, 0
-  br i1 %q, label %bb3, label %bb6
+  br label %bb3
 
 bb6:
   ret void