Index: lib/Transforms/Scalar/JumpThreading.cpp
===================================================================
--- lib/Transforms/Scalar/JumpThreading.cpp
+++ lib/Transforms/Scalar/JumpThreading.cpp
@@ -1661,8 +1661,21 @@
   // threadable destination (the common case) we can avoid this.
   BasicBlock *MostPopularDest = OnlyDest;
 
-  if (MostPopularDest == MultipleDestSentinel)
+  if (MostPopularDest == MultipleDestSentinel) {
+    // Remove any loop headers from the Dest list, ThreadEdge conservatively
+    // won't process them, but we might have other destination that are eligible
+    // and we still want to process.
+    erase_if(PredToDestList,
+             [&](const std::pair<BasicBlock *, BasicBlock *> &PredToDest) {
+               return LoopHeaders.count(PredToDest.second) != 0;
+             });
+
+    if (PredToDestList.empty()) {
+      return false;
+    }
+
     MostPopularDest = FindMostPopularDest(BB, PredToDestList);
+  }
 
   // Now that we know what the most popular destination is, factor all
   // predecessors that will jump to it into a single predecessor.
Index: test/Transforms/JumpThreading/header-succ.ll
===================================================================
--- /dev/null
+++ test/Transforms/JumpThreading/header-succ.ll
@@ -0,0 +1,72 @@
+; RUN: opt -S -jump-threading < %s | FileCheck %s
+
+; Check that the heuristic for avoiding accidental introduction of irreducible
+; loops doesn't also prevent us from threading simple constructs where this
+; isn't a problem.
+
+declare void @opaque_body()
+
+define void @jump_threading_loopheader() {
+; CHECK-LABEL: @jump_threading_loopheader
+top:
+    br label %entry
+
+entry:
+    %ind = phi i32 [0, %top], [%nextind, %latch]
+    %nextind = add i32 %ind, 1
+    %cmp = icmp ule i32 %ind, 10
+; CHECK: br i1 %cmp, label %latch, label %exit
+    br i1 %cmp, label %body, label %latch
+
+body:
+    call void @opaque_body()
+; CHECK: br label %entry
+    br label %latch
+
+latch:
+    %cond = phi i2 [1, %entry], [2, %body]
+    switch i2 %cond, label %unreach [
+        i2 2, label %entry
+        i2 1, label %exit
+    ]
+
+unreach:
+    unreachable
+
+exit:
+    ret void
+}
+
+; We also need to check the opposite order of the branches, in the switch
+; instruction because jump-threading relies on that to decide which edge to
+; try to thread first
+define void @jump_threading_loopheader2() {
+; CHECK-LABEL: @jump_threading_loopheader2
+top:
+    br label %entry
+
+entry:
+    %ind = phi i32 [0, %top], [%nextind, %latch]
+    %nextind = add i32 %ind, 1
+    %cmp = icmp ule i32 %ind, 10
+; CHECK: br i1 %cmp, label %latch, label %exit
+    br i1 %cmp, label %body, label %latch
+
+body:
+    call void @opaque_body()
+; CHECK: br label %entry
+    br label %latch
+
+latch:
+    %cond = phi i2 [1, %entry], [2, %body]
+    switch i2 %cond, label %unreach [
+        i2 2, label %entry
+        i2 1, label %exit
+    ]
+
+unreach:
+    unreachable
+
+exit:
+    ret void
+}