Index: llvm/lib/Transforms/Scalar/JumpThreading.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/JumpThreading.cpp
+++ llvm/lib/Transforms/Scalar/JumpThreading.cpp
@@ -2009,6 +2009,14 @@
       PredTerm->setSuccessor(i, NewBB);
     }
 
+  // Enqueue required DT updates.
+  DDT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
+                     {DominatorTree::Insert, PredBB, NewBB},
+                     {DominatorTree::Delete, PredBB, BB}});
+
+  // Apply all updates we queued with DDT and get the updated Dominator Tree.
+  DominatorTree *DT = &DDT->flush();
+
   // If there were values defined in BB that are used outside the block, then we
   // now have to update all uses of the value to use either the original value,
   // the cloned value, or some PHI derived value.  This can require arbitrary
@@ -2027,7 +2035,7 @@
         if (UserPN->getIncomingBlock(U) == BB ||
             UserPN->getIncomingBlock(U) == PredBB)
           continue;
-      } else if (User->getParent() == BB)
+      } else if (DT->dominates(&I, U))
         continue;
 
       UsesToRename.push_back(&U);
@@ -2046,12 +2054,6 @@
       SSAUpdate.AddUse(VarNum, U);
   }
 
-  DDT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
-                     {DominatorTree::Insert, PredBB, NewBB},
-                     {DominatorTree::Delete, PredBB, BB}});
-
-  // Apply all updates we queued with DDT and get the updated Dominator Tree.
-  DominatorTree *DT = &DDT->flush();
   SSAUpdate.RewriteAllUses(DT);
 
   // At this point, the IR is fully up to date and consistent.  Do a quick scan
Index: llvm/test/Transforms/JumpThreading/PR37745.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/JumpThreading/PR37745.ll
@@ -0,0 +1,19 @@
+; RUN: opt -jump-threading -verify-each -S -mtriple=x86_64-- -o - %s
+
+define void @foo() {
+entry:
+  br i1 false, label %A, label %B
+
+A:
+  %x = phi i32 [ undef, %entry ], [ %z, %B ]
+  br label %B
+
+B:
+  %y = phi i32 [ undef, %entry ], [ %x, %A ]
+  %z = add i32 %y, 1
+  %cmp = icmp ne i32 %z, 0
+  br i1 %cmp, label %exit, label %A
+
+exit:
+  ret void
+}