[JumpThreading] Thread over BB with only an unconditional branch (#86312)

Fixes #76609
This patch does:
- relax the phis constraint in `CanRedirectPredsOfEmptyBBToSucc`
- guarantee the BB has multiple different predecessors to redirect, so
that we can handle the case without phis in BB. Without this change and
phi constraint, we may redirect the CommonPred.

The motivation is consistent with JumpThreading. We always want the
branch to jump more direct to the destination, without passing the
middle block. In this way, we can expose more other optimization
opportunities.

An obivous example proposed by @dtcxzyw is like:
```llvm
define i32 @test(...) {
entry:
   br i1 %c, label %do.end, label %if.then

if.then:                                          ; preds = %entry
   %call2 = call i32 @dummy()
   %tobool3.not = icmp eq i32 %call2, 0
   br i1 %tobool3.not, label %do.end, label %return

do.end:                                           ; preds = %entry, %if.then
   br label %return

return:                                           ; preds = %if.then, %do.end
   %retval.0 = phi i32 [ 0, %do.end ], [ %call2, %if.then ]
   ret i32 %retval.0
}
```
`entry` can directly jump to return, without passing `do.end`, and then
the if-else pattern can be simplified further:
```llvm
define i32 @test(...) {
entry:
   br i1 %c, label %return, label %if.then

if.then:                                          ; preds = %entry
   %call2 = call i32 @dummy()
   br label %return

return:                                           ; preds = %if.then
   %retval.0 = phi i32 [ 0, %entry ], [ %call2, %if.then ]
   ret i32 %retval.0
}
```

9 files changed, 284 insertions, 126 deletions

diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp
index a42ef0c4e6ae..baec51a07fcb 100644
--- a/llvm/lib/Transforms/Utils/Local.cpp
+++ b/llvm/lib/Transforms/Utils/Local.cpp
@@ -1019,12 +1019,14 @@ CanRedirectPredsOfEmptyBBToSucc(BasicBlock *BB, BasicBlock *Succ,
                                 const SmallPtrSetImpl<BasicBlock *> &SuccPreds,
                                 BasicBlock *&CommonPred) {
 
-  // There must be phis in BB, otherwise BB will be merged into Succ directly
-  if (BB->phis().empty() || Succ->phis().empty())
+  // When Succ has no phis, BB may be merged into Succ directly. We don't need
+  // to redirect the predecessors of BB in this case.
+  if (Succ->phis().empty())
     return false;
 
-  // BB must have predecessors not shared that can be redirected to Succ
-  if (!BB->hasNPredecessorsOrMore(2))
+  // BB must have multiple different predecessors, so that at least one of
+  // predecessors can be redirected to Succ, except the common predecessor.
+  if (BB->getUniquePredecessor() || pred_empty(BB))
     return false;
 
   // Get single common predecessors of both BB and Succ
diff --git a/llvm/test/CodeGen/AArch64/and-sink.ll b/llvm/test/CodeGen/AArch64/and-sink.ll
index f298a55dab72..a57e9d54f307 100644
--- a/llvm/test/CodeGen/AArch64/and-sink.ll
+++ b/llvm/test/CodeGen/AArch64/and-sink.ll
@@ -11,15 +11,14 @@
 define dso_local i32 @and_sink1(i32 %a, i1 %c) {
 ; CHECK-LABEL: and_sink1:
 ; CHECK:       // %bb.0:
-; CHECK-NEXT:    tbz w1, #0, .LBB0_3
+; CHECK-NEXT:    tbz w1, #0, .LBB0_2
 ; CHECK-NEXT:  // %bb.1: // %bb0
+; CHECK-NEXT:    tst w0, #0x4
 ; CHECK-NEXT:    adrp x8, A
+; CHECK-NEXT:    cset w0, eq
 ; CHECK-NEXT:    str wzr, [x8, :lo12:A]
-; CHECK-NEXT:    tbnz w0, #2, .LBB0_3
-; CHECK-NEXT:  // %bb.2:
-; CHECK-NEXT:    mov w0, #1 // =0x1
 ; CHECK-NEXT:    ret
-; CHECK-NEXT:  .LBB0_3: // %bb2
+; CHECK-NEXT:  .LBB0_2:
 ; CHECK-NEXT:    mov w0, wzr
 ; CHECK-NEXT:    ret
 
diff --git a/llvm/test/CodeGen/AArch64/combine-comparisons-by-cse.ll b/llvm/test/CodeGen/AArch64/combine-comparisons-by-cse.ll
index 6449c3e11d66..dde3e81833a6 100644
--- a/llvm/test/CodeGen/AArch64/combine-comparisons-by-cse.ll
+++ b/llvm/test/CodeGen/AArch64/combine-comparisons-by-cse.ll
@@ -13,10 +13,10 @@ define i32 @combine_gt_ge_10() #0 {
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    adrp x8, :got:a
 ; CHECK-NEXT:    ldr x8, [x8, :got_lo12:a]
-; CHECK-NEXT:    ldr w8, [x8]
-; CHECK-NEXT:    cmp w8, #10
+; CHECK-NEXT:    ldr w9, [x8]
 ; CHECK-NEXT:    adrp x8, :got:b
 ; CHECK-NEXT:    ldr x8, [x8, :got_lo12:b]
+; CHECK-NEXT:    cmp w9, #10
 ; CHECK-NEXT:    b.le .LBB0_3
 ; CHECK-NEXT:  // %bb.1: // %land.lhs.true
 ; CHECK-NEXT:    adrp x9, :got:c
@@ -29,18 +29,17 @@ define i32 @combine_gt_ge_10() #0 {
 ; CHECK-NEXT:    mov w0, #1 // =0x1
 ; CHECK-NEXT:    ret
 ; CHECK-NEXT:  .LBB0_3: // %lor.lhs.false
-; CHECK-NEXT:    b.lt .LBB0_6
+; CHECK-NEXT:    cmp w9, #10
+; CHECK-NEXT:    b.lt .LBB0_5
 ; CHECK-NEXT:  .LBB0_4: // %land.lhs.true3
 ; CHECK-NEXT:    adrp x9, :got:d
 ; CHECK-NEXT:    ldr x9, [x9, :got_lo12:d]
 ; CHECK-NEXT:    ldr w8, [x8]
 ; CHECK-NEXT:    ldr w9, [x9]
 ; CHECK-NEXT:    cmp w8, w9
-; CHECK-NEXT:    b.ne .LBB0_6
-; CHECK-NEXT:  // %bb.5:
-; CHECK-NEXT:    mov w0, #1 // =0x1
+; CHECK-NEXT:    cset w0, eq
 ; CHECK-NEXT:    ret
-; CHECK-NEXT:  .LBB0_6: // %if.end
+; CHECK-NEXT:  .LBB0_5:
 ; CHECK-NEXT:    mov w0, wzr
 ; CHECK-NEXT:    ret
 entry:
@@ -145,10 +144,10 @@ define i32 @combine_lt_ge_5() #0 {
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    adrp x8, :got:a
 ; CHECK-NEXT:    ldr x8, [x8, :got_lo12:a]
-; CHECK-NEXT:    ldr w8, [x8]
-; CHECK-NEXT:    cmp w8, #5
+; CHECK-NEXT:    ldr w9, [x8]
 ; CHECK-NEXT:    adrp x8, :got:b
 ; CHECK-NEXT:    ldr x8, [x8, :got_lo12:b]
+; CHECK-NEXT:    cmp w9, #5
 ; CHECK-NEXT:    b.ge .LBB2_3
 ; CHECK-NEXT:  // %bb.1: // %land.lhs.true
 ; CHECK-NEXT:    adrp x9, :got:c
@@ -161,18 +160,17 @@ define i32 @combine_lt_ge_5() #0 {
 ; CHECK-NEXT:    mov w0, #1 // =0x1
 ; CHECK-NEXT:    ret
 ; CHECK-NEXT:  .LBB2_3: // %lor.lhs.false
-; CHECK-NEXT:    b.gt .LBB2_6
+; CHECK-NEXT:    cmp w9, #5
+; CHECK-NEXT:    b.gt .LBB2_5
 ; CHECK-NEXT:  .LBB2_4: // %land.lhs.true3
 ; CHECK-NEXT:    adrp x9, :got:d
 ; CHECK-NEXT:    ldr x9, [x9, :got_lo12:d]
 ; CHECK-NEXT:    ldr w8, [x8]
 ; CHECK-NEXT:    ldr w9, [x9]
 ; CHECK-NEXT:    cmp w8, w9
-; CHECK-NEXT:    b.ne .LBB2_6
-; CHECK-NEXT:  // %bb.5:
-; CHECK-NEXT:    mov w0, #1 // =0x1
+; CHECK-NEXT:    cset w0, eq
 ; CHECK-NEXT:    ret
-; CHECK-NEXT:  .LBB2_6: // %if.end
+; CHECK-NEXT:  .LBB2_5:
 ; CHECK-NEXT:    mov w0, wzr
 ; CHECK-NEXT:    ret
 entry:
@@ -499,24 +497,17 @@ define i32 @do_nothing_if_resultant_opcodes_would_differ() #0 {
 ; CHECK-NEXT:  // %bb.3: // %while.cond.while.end_crit_edge
 ; CHECK-NEXT:    ldr w8, [x19]
 ; CHECK-NEXT:  .LBB7_4: // %while.end
-; CHECK-NEXT:    cmp w8, #1
-; CHECK-NEXT:    b.gt .LBB7_7
-; CHECK-NEXT:  // %bb.5: // %land.lhs.true
-; CHECK-NEXT:    adrp x8, :got:b
-; CHECK-NEXT:    adrp x9, :got:d
-; CHECK-NEXT:    ldr x8, [x8, :got_lo12:b]
-; CHECK-NEXT:    ldr x9, [x9, :got_lo12:d]
-; CHECK-NEXT:    ldr w8, [x8]
-; CHECK-NEXT:    ldr w9, [x9]
-; CHECK-NEXT:    cmp w8, w9
-; CHECK-NEXT:    b.ne .LBB7_7
-; CHECK-NEXT:  // %bb.6:
-; CHECK-NEXT:    mov w0, #123 // =0x7b
-; CHECK-NEXT:    b .LBB7_8
-; CHECK-NEXT:  .LBB7_7: // %if.end
-; CHECK-NEXT:    mov w0, wzr
-; CHECK-NEXT:  .LBB7_8: // %return
+; CHECK-NEXT:    adrp x9, :got:b
+; CHECK-NEXT:    adrp x10, :got:d
+; CHECK-NEXT:    ldr x9, [x9, :got_lo12:b]
+; CHECK-NEXT:    ldr x10, [x10, :got_lo12:d]
 ; CHECK-NEXT:    ldp x20, x19, [sp, #16] // 16-byte Folded Reload
+; CHECK-NEXT:    ldr w9, [x9]
+; CHECK-NEXT:    ldr w10, [x10]
+; CHECK-NEXT:    cmp w9, w10
+; CHECK-NEXT:    ccmp w8, #2, #0, eq
+; CHECK-NEXT:    mov w8, #123 // =0x7b
+; CHECK-NEXT:    csel w0, w8, wzr, lt
 ; CHECK-NEXT:    ldr x30, [sp], #32 // 8-byte Folded Reload
 ; CHECK-NEXT:    .cfi_def_cfa_offset 0
 ; CHECK-NEXT:    .cfi_restore w19
@@ -564,52 +555,42 @@ return:                                           ; preds = %if.end, %land.lhs.t
 define i32 @do_nothing_if_compares_can_not_be_adjusted_to_each_other() #0 {
 ; CHECK-LABEL: do_nothing_if_compares_can_not_be_adjusted_to_each_other:
 ; CHECK:       // %bb.0: // %entry
-; CHECK-NEXT:    stp x30, x19, [sp, #-16]! // 16-byte Folded Spill
-; CHECK-NEXT:    .cfi_def_cfa_offset 16
-; CHECK-NEXT:    .cfi_offset w19, -8
-; CHECK-NEXT:    .cfi_offset w30, -16
-; CHECK-NEXT:    .cfi_remember_state
 ; CHECK-NEXT:    adrp x8, :got:a
 ; CHECK-NEXT:    ldr x8, [x8, :got_lo12:a]
 ; CHECK-NEXT:    ldr w8, [x8]
 ; CHECK-NEXT:    cmp w8, #0
-; CHECK-NEXT:    b.gt .LBB8_3
+; CHECK-NEXT:    b.gt .LBB8_4
 ; CHECK-NEXT:  // %bb.1: // %while.body.preheader
+; CHECK-NEXT:    stp x30, x19, [sp, #-16]! // 16-byte Folded Spill
+; CHECK-NEXT:    .cfi_def_cfa_offset 16
+; CHECK-NEXT:    .cfi_offset w19, -8
+; CHECK-NEXT:    .cfi_offset w30, -16
 ; CHECK-NEXT:    sub w19, w8, #1
 ; CHECK-NEXT:  .LBB8_2: // %while.body
 ; CHECK-NEXT:    // =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    bl do_something
 ; CHECK-NEXT:    adds w19, w19, #1
 ; CHECK-NEXT:    b.mi .LBB8_2
-; CHECK-NEXT:  .LBB8_3: // %while.end
-; CHECK-NEXT:    adrp x8, :got:c
-; CHECK-NEXT:    ldr x8, [x8, :got_lo12:c]
-; CHECK-NEXT:    ldr w8, [x8]
-; CHECK-NEXT:    cmn w8, #2
-; CHECK-NEXT:    b.lt .LBB8_6
-; CHECK-NEXT:  // %bb.4: // %land.lhs.true
+; CHECK-NEXT:  // %bb.3:
+; CHECK-NEXT:    ldp x30, x19, [sp], #16 // 16-byte Folded Reload
+; CHECK-NEXT:    .cfi_def_cfa_offset 0
+; CHECK-NEXT:    .cfi_restore w19
+; CHECK-NEXT:    .cfi_restore w30
+; CHECK-NEXT:  .LBB8_4: // %while.end
 ; CHECK-NEXT:    adrp x8, :got:b
 ; CHECK-NEXT:    adrp x9, :got:d
+; CHECK-NEXT:    adrp x10, :got:c
 ; CHECK-NEXT:    ldr x8, [x8, :got_lo12:b]
 ; CHECK-NEXT:    ldr x9, [x9, :got_lo12:d]
+; CHECK-NEXT:    ldr x10, [x10, :got_lo12:c]
 ; CHECK-NEXT:    ldr w8, [x8]
 ; CHECK-NEXT:    ldr w9, [x9]
+; CHECK-NEXT:    ldr w10, [x10]
 ; CHECK-NEXT:    cmp w8, w9
-; CHECK-NEXT:    b.ne .LBB8_6
-; CHECK-NEXT:  // %bb.5:
-; CHECK-NEXT:    mov w0, #123 // =0x7b
-; CHECK-NEXT:    ldp x30, x19, [sp], #16 // 16-byte Folded Reload
-; CHECK-NEXT:    .cfi_def_cfa_offset 0
-; CHECK-NEXT:    .cfi_restore w19
-; CHECK-NEXT:    .cfi_restore w30
-; CHECK-NEXT:    ret
-; CHECK-NEXT:  .LBB8_6: // %if.end
-; CHECK-NEXT:    .cfi_restore_state
-; CHECK-NEXT:    mov w0, wzr
-; CHECK-NEXT:    ldp x30, x19, [sp], #16 // 16-byte Folded Reload
-; CHECK-NEXT:    .cfi_def_cfa_offset 0
-; CHECK-NEXT:    .cfi_restore w19
-; CHECK-NEXT:    .cfi_restore w30
+; CHECK-NEXT:    mov w8, #-3 // =0xfffffffd
+; CHECK-NEXT:    ccmp w10, w8, #4, eq
+; CHECK-NEXT:    mov w8, #123 // =0x7b
+; CHECK-NEXT:    csel w0, w8, wzr, gt
 ; CHECK-NEXT:    ret
 entry:
   %0 = load i32, ptr @a, align 4
@@ -782,12 +763,14 @@ define i32 @combine_gt_ge_sel(i64 %v, ptr %p) #0 {
 ; CHECK-NEXT:    cmp w8, #0
 ; CHECK-NEXT:    csel x9, x0, xzr, gt
 ; CHECK-NEXT:    str x9, [x1]
-; CHECK-NEXT:    b.le .LBB11_2
+; CHECK-NEXT:    b.le .LBB11_3
 ; CHECK-NEXT:  // %bb.1: // %lor.lhs.false
 ; CHECK-NEXT:    cmp w8, #2
-; CHECK-NEXT:    b.ge .LBB11_4
-; CHECK-NEXT:    b .LBB11_6
-; CHECK-NEXT:  .LBB11_2: // %land.lhs.true
+; CHECK-NEXT:    b.ge .LBB11_5
+; CHECK-NEXT:  // %bb.2:
+; CHECK-NEXT:    mov w0, wzr
+; CHECK-NEXT:    ret
+; CHECK-NEXT:  .LBB11_3: // %land.lhs.true
 ; CHECK-NEXT:    adrp x8, :got:b
 ; CHECK-NEXT:    adrp x9, :got:c
 ; CHECK-NEXT:    ldr x8, [x8, :got_lo12:b]
@@ -795,11 +778,11 @@ define i32 @combine_gt_ge_sel(i64 %v, ptr %p) #0 {
 ; CHECK-NEXT:    ldr w8, [x8]
 ; CHECK-NEXT:    ldr w9, [x9]
 ; CHECK-NEXT:    cmp w8, w9
-; CHECK-NEXT:    b.ne .LBB11_4
-; CHECK-NEXT:  // %bb.3:
+; CHECK-NEXT:    b.ne .LBB11_5
+; CHECK-NEXT:  // %bb.4:
 ; CHECK-NEXT:    mov w0, #1 // =0x1
 ; CHECK-NEXT:    ret
-; CHECK-NEXT:  .LBB11_4: // %land.lhs.true3
+; CHECK-NEXT:  .LBB11_5: // %land.lhs.true3
 ; CHECK-NEXT:    adrp x8, :got:b
 ; CHECK-NEXT:    adrp x9, :got:d
 ; CHECK-NEXT:    ldr x8, [x8, :got_lo12:b]
@@ -807,12 +790,7 @@ define i32 @combine_gt_ge_sel(i64 %v, ptr %p) #0 {
 ; CHECK-NEXT:    ldr w8, [x8]
 ; CHECK-NEXT:    ldr w9, [x9]
 ; CHECK-NEXT:    cmp w8, w9
-; CHECK-NEXT:    b.ne .LBB11_6
-; CHECK-NEXT:  // %bb.5:
-; CHECK-NEXT:    mov w0, #1 // =0x1
-; CHECK-NEXT:    ret
-; CHECK-NEXT:  .LBB11_6: // %if.end
-; CHECK-NEXT:    mov w0, wzr
+; CHECK-NEXT:    cset w0, eq
 ; CHECK-NEXT:    ret
 entry:
   %0 = load i32, ptr @a, align 4
diff --git a/llvm/test/CodeGen/Hexagon/vect/zext-v4i1.ll b/llvm/test/CodeGen/Hexagon/vect/zext-v4i1.ll
index dddc4bd953d7..c33c81841be6 100644
--- a/llvm/test/CodeGen/Hexagon/vect/zext-v4i1.ll
+++ b/llvm/test/CodeGen/Hexagon/vect/zext-v4i1.ll
@@ -10,12 +10,13 @@ define i32 @fred(ptr %a0) #0 {
 ; CHECK-LABEL: fred:
 ; CHECK:       // %bb.0: // %b0
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     if (p0) jump:nt .LBB0_2
+; CHECK-NEXT:     r1:0 = combine(r0,#0)
+; CHECK-NEXT:     if (p0) jumpr r31
 ; CHECK-NEXT:    }
-; CHECK-NEXT:  // %bb.1: // %b2
+; CHECK-NEXT:  .LBB0_1: // %b2
 ; CHECK-NEXT:    {
 ; CHECK-NEXT:     r3:2 = combine(#0,#0)
-; CHECK-NEXT:     r1:0 = memd(r0+#0)
+; CHECK-NEXT:     r1:0 = memd(r1+#0)
 ; CHECK-NEXT:    }
 ; CHECK-NEXT:    {
 ; CHECK-NEXT:     p0 = vcmph.eq(r1:0,r3:2)
@@ -27,16 +28,7 @@ define i32 @fred(ptr %a0) #0 {
 ; CHECK-NEXT:     r0 = and(r0,#1)
 ; CHECK-NEXT:    }
 ; CHECK-NEXT:    {
-; CHECK-NEXT:     p0 = cmp.eq(r0,#11)
-; CHECK-NEXT:     r0 = #1
-; CHECK-NEXT:    }
-; CHECK-NEXT:    {
-; CHECK-NEXT:     if (p0) r0 = #0
-; CHECK-NEXT:     jumpr r31
-; CHECK-NEXT:    }
-; CHECK-NEXT:  .LBB0_2: // %b14
-; CHECK-NEXT:    {
-; CHECK-NEXT:     r0 = #0
+; CHECK-NEXT:     r0 = !cmp.eq(r0,#11)
 ; CHECK-NEXT:     jumpr r31
 ; CHECK-NEXT:    }
 b0:
diff --git a/llvm/test/Transforms/JumpThreading/pr79175.ll b/llvm/test/Transforms/JumpThreading/pr79175.ll
index 2c7ee0770cdc..cce30ce07999 100644
--- a/llvm/test/Transforms/JumpThreading/pr79175.ll
+++ b/llvm/test/Transforms/JumpThreading/pr79175.ll
@@ -17,11 +17,11 @@ define i32 @test(i64 %idx, i32 %val) {
 ; CHECK:       cond.end:
 ; CHECK-NEXT:    [[CMP_I:%.*]] = icmp sgt i32 [[VAL]], 0
 ; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 [[CMP_I]]
-; CHECK-NEXT:    br i1 [[COND_FR]], label [[COND_END_THREAD]], label [[TMP0:%.*]]
-; CHECK:       cond.end.thread:
-; CHECK-NEXT:    br label [[TMP0]]
+; CHECK-NEXT:    br i1 [[COND_FR]], label [[TMP0:%.*]], label [[COND_END_THREAD]]
 ; CHECK:       0:
-; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ 0, [[COND_END_THREAD]] ], [ [[VAL]], [[COND_END]] ]
+; CHECK-NEXT:    br label [[COND_END_THREAD]]
+; CHECK:       cond.end.thread:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ [[VAL]], [[COND_END]] ], [ 0, [[TMP0]] ], [ 0, [[FOR_BODY]] ]
 ; CHECK-NEXT:    [[F_IDX:%.*]] = getelementptr inbounds i32, ptr @f, i64 [[IDX]]
 ; CHECK-NEXT:    store i32 [[TMP1]], ptr [[F_IDX]], align 4
 ; CHECK-NEXT:    [[F_RELOAD:%.*]] = load i32, ptr @f, align 4
diff --git a/llvm/test/Transforms/JumpThreading/select.ll b/llvm/test/Transforms/JumpThreading/select.ll
index 4ec55a66bb8a..27ebf4c25da5 100644
--- a/llvm/test/Transforms/JumpThreading/select.ll
+++ b/llvm/test/Transforms/JumpThreading/select.ll
@@ -1,6 +1,6 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-globals
 ; RUN: opt -S -passes="jump-threading" -debug-only=branch-prob < %s 2>&1 | FileCheck %s
-; RUN: opt -S -passes="require<branch-prob>,jump-threading" -debug-only=branch-prob < %s 2>&1 | FileCheck -check-prefixes=CHECK,CHECK-BPI %s
+; RUN: opt -S -passes="require<branch-prob>,jump-threading" -debug-only=branch-prob  -disable-output < %s 2>&1 | FileCheck -check-prefix=CHECK-BPI %s
 ; REQUIRES: asserts
 
 ; CHECK-BPI-LABEL:  ---- Branch Probability Info : unfold1 ----
@@ -21,7 +21,7 @@ declare void @quux()
 ; booleans where at least one operand is true/false/undef.
 
 ;.
-; CHECK: @[[ANCHOR:[a-zA-Z0-9_$"\\.-]+]] = constant [3 x ptr] [ptr blockaddress(@test_indirectbr, [[L1:%.*]]), ptr inttoptr (i32 1 to ptr), ptr blockaddress(@test_indirectbr, [[L3:%.*]])]
+; CHECK: @anchor = constant [3 x ptr] [ptr blockaddress(@test_indirectbr, %L1), ptr inttoptr (i32 1 to ptr), ptr blockaddress(@test_indirectbr, %L3)]
 ;.
 define void @test_br(i1 %cond, i1 %value) nounwind {
 ; CHECK-LABEL: @test_br(
@@ -66,8 +66,8 @@ define void @test_switch(i1 %cond, i8 %value) nounwind {
 ; CHECK-NEXT:    call void @quux()
 ; CHECK-NEXT:    [[EXPR:%.*]] = select i1 [[COND]], i8 1, i8 [[VALUE:%.*]]
 ; CHECK-NEXT:    switch i8 [[EXPR]], label [[L3:%.*]] [
-; CHECK-NEXT:    i8 1, label [[L1]]
-; CHECK-NEXT:    i8 2, label [[L2:%.*]]
+; CHECK-NEXT:      i8 1, label [[L1]]
+; CHECK-NEXT:      i8 2, label [[L2:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       L1:
 ; CHECK-NEXT:    call void @foo()
@@ -192,8 +192,8 @@ define void @test_switch_cmp(i1 %cond, i32 %val, i8 %value) nounwind {
 ; CHECK:       0:
 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i8 [ [[VALUE:%.*]], [[L0]] ]
 ; CHECK-NEXT:    switch i8 [[TMP1]], label [[L3:%.*]] [
-; CHECK-NEXT:    i8 1, label [[L1]]
-; CHECK-NEXT:    i8 2, label [[L2:%.*]]
+; CHECK-NEXT:      i8 1, label [[L1]]
+; CHECK-NEXT:      i8 2, label [[L2:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       L1:
 ; CHECK-NEXT:    call void @foo()
@@ -237,8 +237,8 @@ define void @test_switch_default(ptr nocapture %status) nounwind {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32, ptr [[STATUS:%.*]], align 4
 ; CHECK-NEXT:    switch i32 [[TMP0]], label [[L2:%.*]] [
-; CHECK-NEXT:    i32 5061, label [[L2_THREAD:%.*]]
-; CHECK-NEXT:    i32 0, label [[L2]]
+; CHECK-NEXT:      i32 5061, label [[L2_THREAD:%.*]]
+; CHECK-NEXT:      i32 0, label [[L2]]
 ; CHECK-NEXT:    ]
 ; CHECK:       L2.thread:
 ; CHECK-NEXT:    store i32 10025, ptr [[STATUS]], align 4
@@ -377,21 +377,21 @@ define i32 @unfold3(i32 %u, i32 %v, i32 %w, i32 %x, i32 %y, i32 %z, i32 %j) noun
 ; CHECK-NEXT:    br i1 [[CMP_I]], label [[DOTEXIT_THREAD4:%.*]], label [[COND_FALSE_I:%.*]]
 ; CHECK:       cond.false.i:
 ; CHECK-NEXT:    [[CMP4_I:%.*]] = icmp sgt i32 [[U]], [[V]]
-; CHECK-NEXT:    br i1 [[CMP4_I]], label [[DOTEXIT_THREAD:%.*]], label [[COND_FALSE_6_I:%.*]]
+; CHECK-NEXT:    br i1 [[CMP4_I]], label [[DOTEXIT_THREAD4]], label [[COND_FALSE_6_I:%.*]]
 ; CHECK:       cond.false.6.i:
 ; CHECK-NEXT:    [[CMP8_I:%.*]] = icmp slt i32 [[W:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP8_I]], label [[DOTEXIT_THREAD4]], label [[COND_FALSE_10_I:%.*]]
 ; CHECK:       cond.false.10.i:
 ; CHECK-NEXT:    [[CMP13_I:%.*]] = icmp sgt i32 [[W]], [[X]]
-; CHECK-NEXT:    br i1 [[CMP13_I]], label [[DOTEXIT_THREAD]], label [[DOTEXIT:%.*]]
+; CHECK-NEXT:    br i1 [[CMP13_I]], label [[DOTEXIT_THREAD4]], label [[DOTEXIT:%.*]]
 ; CHECK:       .exit:
 ; CHECK-NEXT:    [[PHITMP:%.*]] = icmp sge i32 [[Y:%.*]], [[Z:%.*]]
 ; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 [[PHITMP]]
-; CHECK-NEXT:    br i1 [[COND_FR]], label [[DOTEXIT_THREAD]], label [[DOTEXIT_THREAD4]]
-; CHECK:       .exit.thread:
+; CHECK-NEXT:    br i1 [[COND_FR]], label [[DOTEXIT_THREAD:%.*]], label [[DOTEXIT_THREAD4]]
+; CHECK:       0:
 ; CHECK-NEXT:    br label [[DOTEXIT_THREAD4]]
-; CHECK:       .exit.thread4:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[J]], [[DOTEXIT_THREAD]] ], [ [[ADD3]], [[DOTEXIT]] ], [ [[ADD3]], [[ENTRY:%.*]] ], [ [[ADD3]], [[COND_FALSE_6_I]] ]
+; CHECK:       .exit.thread:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[ADD3]], [[DOTEXIT]] ], [ [[J]], [[DOTEXIT_THREAD]] ], [ [[J]], [[COND_FALSE_I]] ], [ [[J]], [[COND_FALSE_10_I]] ], [ [[ADD3]], [[ENTRY:%.*]] ], [ [[ADD3]], [[COND_FALSE_6_I]] ]
 ; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
@@ -430,23 +430,23 @@ define i32 @unfold4(i32 %u, i32 %v, i32 %w, i32 %x, i32 %y, i32 %z, i32 %j) noun
 ; CHECK-NEXT:    br i1 [[CMP_I]], label [[DOTEXIT_THREAD:%.*]], label [[COND_FALSE_I:%.*]]
 ; CHECK:       cond.false.i:
 ; CHECK-NEXT:    [[CMP4_I:%.*]] = icmp sgt i32 [[U]], [[V]]
-; CHECK-NEXT:    br i1 [[CMP4_I]], label [[DOTEXIT_THREAD5:%.*]], label [[COND_FALSE_6_I:%.*]]
+; CHECK-NEXT:    br i1 [[CMP4_I]], label [[DOTEXIT_THREAD]], label [[COND_FALSE_6_I:%.*]]
 ; CHECK:       cond.false.6.i:
 ; CHECK-NEXT:    [[CMP8_I:%.*]] = icmp slt i32 [[W:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP8_I]], label [[DOTEXIT_THREAD]], label [[COND_FALSE_10_I:%.*]]
 ; CHECK:       cond.false.10.i:
 ; CHECK-NEXT:    [[CMP13_I:%.*]] = icmp sgt i32 [[W]], [[X]]
-; CHECK-NEXT:    br i1 [[CMP13_I]], label [[DOTEXIT_THREAD5]], label [[DOTEXIT:%.*]]
+; CHECK-NEXT:    br i1 [[CMP13_I]], label [[DOTEXIT_THREAD]], label [[DOTEXIT:%.*]]
 ; CHECK:       .exit:
 ; CHECK-NEXT:    [[CMP19_I:%.*]] = icmp sge i32 [[Y:%.*]], [[Z:%.*]]
 ; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP19_I]] to i32
 ; CHECK-NEXT:    [[LNOT_I18:%.*]] = icmp eq i32 [[CONV]], 1
 ; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 [[LNOT_I18]]
-; CHECK-NEXT:    br i1 [[COND_FR]], label [[DOTEXIT_THREAD]], label [[DOTEXIT_THREAD5]]
+; CHECK-NEXT:    br i1 [[COND_FR]], label [[TMP1:%.*]], label [[DOTEXIT_THREAD]]
+; CHECK:       0:
+; CHECK-NEXT:    br label [[DOTEXIT_THREAD]]
 ; CHECK:       .exit.thread:
-; CHECK-NEXT:    br label [[DOTEXIT_THREAD5]]
-; CHECK:       .exit.thread5:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[J]], [[DOTEXIT_THREAD]] ], [ [[ADD3]], [[DOTEXIT]] ], [ [[ADD3]], [[COND_FALSE_I]] ], [ [[ADD3]], [[COND_FALSE_10_I]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i32 [ [[ADD3]], [[DOTEXIT]] ], [ [[J]], [[TMP1]] ], [ [[J]], [[ENTRY:%.*]] ], [ [[J]], [[COND_FALSE_6_I]] ], [ [[ADD3]], [[COND_FALSE_I]] ], [ [[ADD3]], [[COND_FALSE_10_I]] ]
 ; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
@@ -560,10 +560,10 @@ define void @test_func(ptr nocapture readonly %a, ptr nocapture readonly %b, ptr
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[LOCAL_VAR_0:%.*]] = phi i32 [ [[TMP1]], [[FOR_BODY]] ]
 ; CHECK-NEXT:    switch i32 [[LOCAL_VAR_0]], label [[SW_DEFAULT]] [
-; CHECK-NEXT:    i32 2, label [[SW_BB]]
-; CHECK-NEXT:    i32 4, label [[SW_BB7]]
-; CHECK-NEXT:    i32 5, label [[SW_BB8:%.*]]
-; CHECK-NEXT:    i32 7, label [[SW_BB9:%.*]]
+; CHECK-NEXT:      i32 2, label [[SW_BB]]
+; CHECK-NEXT:      i32 4, label [[SW_BB7]]
+; CHECK-NEXT:      i32 5, label [[SW_BB8:%.*]]
+; CHECK-NEXT:      i32 7, label [[SW_BB9:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       sw.bb:
 ; CHECK-NEXT:    call void @foo()
@@ -674,3 +674,5 @@ if.end:
 ; CHECK: [[META0:![0-9]+]] = !{!"function_entry_count", i64 1984}
 ; CHECK: [[PROF1]] = !{!"branch_weights", i64 1073741824, i64 3221225472}
 ;.
+;; NOTE: These prefixes are unused and the list is autogenerated. Do not add tests below this line:
+; CHECK-BPI: {{.*}}
diff --git a/llvm/test/Transforms/JumpThreading/thread-prob-7.ll b/llvm/test/Transforms/JumpThreading/thread-prob-7.ll
index 8c9d89871d00..4623a579be48 100644
--- a/llvm/test/Transforms/JumpThreading/thread-prob-7.ll
+++ b/llvm/test/Transforms/JumpThreading/thread-prob-7.ll
@@ -14,15 +14,15 @@ define i32 @func0(i32 %a0, i32 %a1) !prof !0 {
 ; CHECK-NEXT:    br i1 [[CMP1]], label [[BB_JOIN_THREAD:%.*]], label [[TEST2_FALSE:%.*]], !prof [[PROF2:![0-9]+]]
 ; CHECK:       test2_false:
 ; CHECK-NEXT:    call void @foobar()
-; CHECK-NEXT:    br label [[TMP0:%.*]]
+; CHECK-NEXT:    br label [[BB_JOIN_THREAD]]
 ; CHECK:       bb_join:
 ; CHECK-NEXT:    [[C:%.*]] = phi i1 [ [[CX]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[COND_FR:%.*]] = freeze i1 [[C]]
-; CHECK-NEXT:    br i1 [[COND_FR]], label [[BB_JOIN_THREAD]], label [[TMP0]], !prof [[PROF3:![0-9]+]]
+; CHECK-NEXT:    br i1 [[COND_FR]], label [[BB_JOIN_THREAD1:%.*]], label [[BB_JOIN_THREAD]], !prof [[PROF3:![0-9]+]]
 ; CHECK:       bb_join.thread:
-; CHECK-NEXT:    br label [[TMP0]]
+; CHECK-NEXT:    br label [[BB_JOIN_THREAD]]
 ; CHECK:       0:
-; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ 42, [[BB_JOIN_THREAD]] ], [ 7, [[BB_JOIN]] ], [ 7, [[TEST2_FALSE]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i32 [ 7, [[BB_JOIN]] ], [ 7, [[TEST2_FALSE]] ], [ 42, [[TEST2]] ], [ 42, [[BB_JOIN_THREAD1]] ]
 ; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
 entry:
diff --git a/llvm/test/Transforms/JumpThreading/uncond-no-phi.ll b/llvm/test/Transforms/JumpThreading/uncond-no-phi.ll
new file mode 100644
index 000000000000..6104e8f8778b
--- /dev/null
+++ b/llvm/test/Transforms/JumpThreading/uncond-no-phi.ll
@@ -0,0 +1,123 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 4
+; RUN: opt -passes=jump-threading -S < %s | FileCheck %s
+
+define i1 @if_else(i1 %c, i1 %c1) {
+; CHECK-LABEL: define i1 @if_else(
+; CHECK-SAME: i1 [[C:%.*]], i1 [[C1:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C]], label [[THEN:%.*]], label [[RETURN:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    call void @dummy()
+; CHECK-NEXT:    br i1 [[C1]], label [[ELSE:%.*]], label [[RETURN]]
+; CHECK:       else:
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i1 [ false, [[THEN]] ], [ true, [[ENTRY:%.*]] ], [ true, [[ELSE]] ]
+; CHECK-NEXT:    ret i1 [[RETVAL_0]]
+;
+entry:
+  br i1 %c, label %then, label %else
+
+then:
+  call void @dummy()
+  br i1 %c1, label %else, label %return
+
+else:
+  br label %return
+
+return:
+  %retval.0 = phi i1 [ true, %else ], [ false, %then ]
+  ret i1 %retval.0
+}
+
+define i8 @switch_uncond(i8 %arg) {
+; CHECK-LABEL: define i8 @switch_uncond(
+; CHECK-SAME: i8 [[ARG:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i8 [[ARG]], label [[DEFAULT:%.*]] [
+; CHECK-NEXT:      i8 0, label [[BB1:%.*]]
+; CHECK-NEXT:      i8 1, label [[BB3:%.*]]
+; CHECK-NEXT:      i8 2, label [[BB2:%.*]]
+; CHECK-NEXT:      i8 3, label [[END:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       default:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb:
+; CHECK-NEXT:    call void @dummy()
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       bb1:
+; CHECK-NEXT:    call void @dummy()
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i8 [ 1, [[ENTRY:%.*]] ], [ 0, [[BB3]] ], [ 0, [[BB1]] ], [ 0, [[BB2]] ]
+; CHECK-NEXT:    ret i8 [[PHI]]
+;
+entry:
+  switch i8 %arg, label %default [
+  i8 0, label %bb
+  i8 1, label %bb1
+  i8 2, label %bb2
+  i8 3, label %end
+  ]
+
+default:
+  unreachable
+
+bb:
+  call void @dummy()
+  br label %bb2
+
+bb1:
+  call void @dummy()
+  br label %bb2
+
+; Predecessors of %bb2 are %bb and %bb1, they are not identical.
+; So we can thread %bb2.
+bb2:
+  br label %end
+
+end:
+  %phi = phi i8 [ 0, %bb2 ], [ 1, %entry ]
+  ret i8 %phi
+}
+
+define i8 @switch_uncond_fail(i8 %arg) {
+; CHECK-LABEL: define i8 @switch_uncond_fail(
+; CHECK-SAME: i8 [[ARG:%.*]]) {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    switch i8 [[ARG]], label [[DEFAULT:%.*]] [
+; CHECK-NEXT:      i8 0, label [[BB:%.*]]
+; CHECK-NEXT:      i8 1, label [[BB]]
+; CHECK-NEXT:      i8 2, label [[END:%.*]]
+; CHECK-NEXT:    ]
+; CHECK:       default:
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       bb:
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i8 [ 0, [[BB]] ], [ 1, [[ENTRY:%.*]] ], [ 2, [[DEFAULT]] ]
+; CHECK-NEXT:    ret i8 [[PHI]]
+;
+entry:
+  switch i8 %arg, label %default [
+  i8 0, label %bb
+  i8 1, label %bb
+  i8 2, label %end
+  ]
+
+default:
+  br label %end
+
+; Predecessor of %bb is only %entry (though there are two in predecessor list),
+; thus it's unthreadable.
+bb:
+  br label %end
+
+end:
+  %phi = phi i8 [ 0, %bb ], [ 1, %entry ], [ 2, %default ]
+  ret i8 %phi
+}
+
+declare void @dummy()
diff --git a/llvm/test/Transforms/PhaseOrdering/thread-uncond-bb.ll b/llvm/test/Transforms/PhaseOrdering/thread-uncond-bb.ll
new file mode 100644
index 000000000000..17146d7d5987
--- /dev/null
+++ b/llvm/test/Transforms/PhaseOrdering/thread-uncond-bb.ll
@@ -0,0 +1,62 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 4
+; RUN: opt < %s -O3 -S | FileCheck %s
+
+define i32 @thread_uncond_bb_cmp(i1 %c, i32 %v) {
+; CHECK-LABEL: define i32 @thread_uncond_bb_cmp(
+; CHECK-SAME: i1 [[C:%.*]], i32 [[V:%.*]]) local_unnamed_addr {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C]], label [[DO_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    tail call void @dummy()
+; CHECK-NEXT:    br label [[DO_END]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[V]], [[IF_THEN]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL]]
+;
+entry:
+  br i1 %c, label %do.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  call void @dummy()
+  %tobool = icmp eq i32 %v, 0
+  br i1 %tobool, label %do.end, label %return
+
+do.end:                                           ; preds = %entry, %if.then
+  br label %return
+
+return:                                           ; preds = %if.then, %do.end
+  %retval = phi i32 [ 0, %do.end ], [ %v, %if.then ]
+  ret i32 %retval
+}
+
+define i32 @thread_uncond_bb_cmp_zext(i1 %c, i32 %v) {
+; CHECK-LABEL: define i32 @thread_uncond_bb_cmp_zext(
+; CHECK-SAME: i1 [[C:%.*]], i32 [[V:%.*]]) local_unnamed_addr {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C]], label [[DO_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    tail call void @dummy()
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[V]], 0
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = zext i1 [[TOBOOL]] to i32
+; CHECK-NEXT:    br label [[DO_END]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SPEC_SELECT]], [[IF_THEN]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL]]
+;
+entry:
+  br i1 %c, label %do.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  call void @dummy()
+  %tobool = icmp eq i32 %v, 0
+  br i1 %tobool, label %do.end, label %return
+
+do.end:                                           ; preds = %entry, %if.then
+  br label %return
+
+return:                                           ; preds = %if.then, %do.end
+  %retval = phi i32 [ 0, %do.end ], [ 1, %if.then ]
+  ret i32 %retval
+}
+
+declare void @dummy()