; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
; RUN: opt -S -passes=instcombine < %s | FileCheck %s --check-prefixes=CHECK,DEFAULT_ITER
; RUN: opt -S -passes='instcombine<max-iterations=1>' < %s | FileCheck %s --check-prefixes=CHECK,MAX1

declare void @dummy()
declare void @llvm.assume(i1)

define i32 @br_true(i1 %x) {
; CHECK-LABEL: define i32 @br_true
; CHECK-SAME: (i1 [[X:%.*]]) {
; CHECK-NEXT:    br i1 true, label [[IF:%.*]], label [[ELSE:%.*]]
; CHECK:       if:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    br label [[JOIN:%.*]]
; CHECK:       else:
; CHECK-NEXT:    br label [[JOIN]]
; CHECK:       join:
; CHECK-NEXT:    ret i32 1
;
  %c = or i1 %x, true
  br i1 %c, label %if, label %else

if:
  call void @dummy()
  br label %join

else:
  call void @dummy()
  br label %join

join:
  %phi = phi i32 [ 1, %if ], [ 2, %else ]
  ret i32 %phi
}

define i32 @br_false(i1 %x) {
; CHECK-LABEL: define i32 @br_false
; CHECK-SAME: (i1 [[X:%.*]]) {
; CHECK-NEXT:    br i1 false, label [[IF:%.*]], label [[ELSE:%.*]]
; CHECK:       if:
; CHECK-NEXT:    br label [[JOIN:%.*]]
; CHECK:       else:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    br label [[JOIN]]
; CHECK:       join:
; CHECK-NEXT:    ret i32 2
;
  %c = and i1 %x, false
  br i1 %c, label %if, label %else

if:
  call void @dummy()
  br label %join

else:
  call void @dummy()
  br label %join

join:
  %phi = phi i32 [ 1, %if ], [ 2, %else ]
  ret i32 %phi
}

define i32 @br_undef(i1 %x) {
; CHECK-LABEL: define i32 @br_undef
; CHECK-SAME: (i1 [[X:%.*]]) {
; CHECK-NEXT:    br i1 undef, label [[IF:%.*]], label [[ELSE:%.*]]
; CHECK:       if:
; CHECK-NEXT:    br label [[JOIN:%.*]]
; CHECK:       else:
; CHECK-NEXT:    br label [[JOIN]]
; CHECK:       join:
; CHECK-NEXT:    ret i32 poison
;
  %c = xor i1 %x, undef
  br i1 %c, label %if, label %else

if:
  call void @dummy()
  br label %join

else:
  call void @dummy()
  br label %join

join:
  %phi = phi i32 [ 1, %if ], [ 2, %else ]
  ret i32 %phi
}

define i32 @br_true_phi_with_repeated_preds(i1 %x) {
; CHECK-LABEL: define i32 @br_true_phi_with_repeated_preds
; CHECK-SAME: (i1 [[X:%.*]]) {
; CHECK-NEXT:    br i1 true, label [[IF:%.*]], label [[ELSE:%.*]]
; CHECK:       if:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    br label [[JOIN:%.*]]
; CHECK:       else:
; CHECK-NEXT:    br i1 false, label [[JOIN]], label [[JOIN]]
; CHECK:       join:
; CHECK-NEXT:    ret i32 1
;
  %c = or i1 %x, true
  br i1 %c, label %if, label %else

if:
  call void @dummy()
  br label %join

else:
  br i1 false, label %join, label %join

join:
  %phi = phi i32 [ 1, %if ], [ 2, %else ], [ 2, %else ]
  ret i32 %phi
}

define i32 @br_true_const_phi_direct_edge(i1 %x) {
; CHECK-LABEL: define i32 @br_true_const_phi_direct_edge
; CHECK-SAME: (i1 [[X:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 true, label [[IF:%.*]], label [[JOIN:%.*]]
; CHECK:       if:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    br label [[JOIN]]
; CHECK:       join:
; CHECK-NEXT:    ret i32 2
;
entry:
  br i1 true, label %if, label %join

if:
  call void @dummy()
  br label %join

join:
  %phi = phi i32 [ 1, %entry ], [ 2, %if ]
  ret i32 %phi
}

define i32 @br_true_var_phi_direct_edge(i1 %x) {
; CHECK-LABEL: define i32 @br_true_var_phi_direct_edge
; CHECK-SAME: (i1 [[X:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 true, label [[IF:%.*]], label [[JOIN:%.*]]
; CHECK:       if:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    br label [[JOIN]]
; CHECK:       join:
; CHECK-NEXT:    ret i32 2
;
entry:
  %c = or i1 %x, true
  br i1 %c, label %if, label %join

if:
  call void @dummy()
  br label %join

join:
  %phi = phi i32 [ 1, %entry ], [ 2, %if ]
  ret i32 %phi
}

define void @switch_case(i32 %x) {
; CHECK-LABEL: define void @switch_case
; CHECK-SAME: (i32 [[X:%.*]]) {
; CHECK-NEXT:    switch i32 0, label [[DEFAULT:%.*]] [
; CHECK-NEXT:    i32 0, label [[CASE0:%.*]]
; CHECK-NEXT:    ]
; CHECK:       case0:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    ret void
; CHECK:       default:
; CHECK-NEXT:    ret void
;
  %v = and i32 %x, 0
  switch i32 %v, label %default [
  i32 0, label %case0
  ]

case0:
  call void @dummy()
  ret void

default:
  call void @dummy()
  ret void
}

define void @switch_default(i32 %x) {
; CHECK-LABEL: define void @switch_default
; CHECK-SAME: (i32 [[X:%.*]]) {
; CHECK-NEXT:    switch i32 -1, label [[DEFAULT:%.*]] [
; CHECK-NEXT:    i32 0, label [[CASE0:%.*]]
; CHECK-NEXT:    ]
; CHECK:       case0:
; CHECK-NEXT:    ret void
; CHECK:       default:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    ret void
;
  %v = or i32 %x, -1
  switch i32 %v, label %default [
  i32 0, label %case0
  ]

case0:
  call void @dummy()
  ret void

default:
  call void @dummy()
  ret void
}

define void @switch_undef(i32 %x) {
; CHECK-LABEL: define void @switch_undef
; CHECK-SAME: (i32 [[X:%.*]]) {
; CHECK-NEXT:    switch i32 undef, label [[DEFAULT:%.*]] [
; CHECK-NEXT:    i32 0, label [[CASE0:%.*]]
; CHECK-NEXT:    ]
; CHECK:       case0:
; CHECK-NEXT:    ret void
; CHECK:       default:
; CHECK-NEXT:    ret void
;
  %v = xor i32 %x, undef
  switch i32 %v, label %default [
  i32 0, label %case0
  ]

case0:
  call void @dummy()
  ret void

default:
  call void @dummy()
  ret void
}

define void @non_term_unreachable() {
; CHECK-LABEL: define void @non_term_unreachable() {
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    store i1 true, ptr poison, align 1
; CHECK-NEXT:    ret void
;
  call void @dummy()
  call void @dummy() nounwind willreturn
  store i1 true, ptr poison
  call void @dummy()
  ret void
}

define i32 @non_term_unreachable_phi(i1 %c) {
; CHECK-LABEL: define i32 @non_term_unreachable_phi
; CHECK-SAME: (i1 [[C:%.*]]) {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[C]], label [[IF:%.*]], label [[JOIN:%.*]]
; CHECK:       if:
; CHECK-NEXT:    store i1 true, ptr poison, align 1
; CHECK-NEXT:    br label [[JOIN]]
; CHECK:       join:
; CHECK-NEXT:    ret i32 2
;
entry:
  br i1 %c, label %if, label %join

if:
  store i1 true, ptr poison
  call void @dummy()
  br label %join

join:
  %phi = phi i32 [ 1, %if], [ 2, %entry ]
  ret i32 %phi
}

define void @non_term_unreachable_following_blocks() {
; CHECK-LABEL: define void @non_term_unreachable_following_blocks() {
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    store i1 true, ptr poison, align 1
; CHECK-NEXT:    br label [[SPLIT:%.*]]
; CHECK:       split:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    br label [[LOOP]]
;
  call void @dummy()
  store i1 true, ptr poison
  call void @dummy()
  br label %split

split:
  call void @dummy()
  br label %loop

loop:
  call void @dummy()
  br label %loop
}

define void @br_not_into_loop(i1 %x) {
; CHECK-LABEL: define void @br_not_into_loop
; CHECK-SAME: (i1 [[X:%.*]]) {
; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    br label [[LOOP]]
; CHECK:       exit:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    ret void
;
  %c = or i1 %x, true
  br i1 %c, label %exit, label %loop

loop:
  call void @dummy()
  br label %loop

exit:
  call void @dummy()
  ret void
}

define void @br_into_loop(i1 %x) {
; CHECK-LABEL: define void @br_into_loop
; CHECK-SAME: (i1 [[X:%.*]]) {
; CHECK-NEXT:    br i1 true, label [[LOOP:%.*]], label [[EXIT:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    br label [[LOOP]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
;
  %c = or i1 %x, true
  br i1 %c, label %loop, label %exit

loop:
  call void @dummy()
  br label %loop

exit:
  call void @dummy()
  ret void
}

define void @two_br_not_into_loop(i1 %x) {
; CHECK-LABEL: define void @two_br_not_into_loop
; CHECK-SAME: (i1 [[X:%.*]]) {
; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[LOOP:%.*]]
; CHECK:       bb2:
; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[LOOP]]
; CHECK:       loop:
; CHECK-NEXT:    br label [[LOOP]]
; CHECK:       exit:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    ret void
;
  %c = or i1 %x, true
  br i1 %c, label %bb2, label %loop

bb2:
  %c2 = or i1 %x, true
  br i1 %c2, label %exit, label %loop

loop:
  call void @dummy()
  br label %loop

exit:
  call void @dummy()
  ret void
}

define void @one_br_into_loop_one_not(i1 %x, i1 %c2) {
; CHECK-LABEL: define void @one_br_into_loop_one_not
; CHECK-SAME: (i1 [[X:%.*]], i1 [[C2:%.*]]) {
; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[LOOP:%.*]]
; CHECK:       bb2:
; CHECK-NEXT:    br i1 [[C2]], label [[EXIT:%.*]], label [[LOOP]]
; CHECK:       loop:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    br label [[LOOP]]
; CHECK:       exit:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    ret void
;
  %c = or i1 %x, true
  br i1 %c, label %bb2, label %loop

bb2:
  br i1 %c2, label %exit, label %loop

loop:
  call void @dummy()
  br label %loop

exit:
  call void @dummy()
  ret void
}

define void @two_br_not_into_loop_with_split(i1 %x) {
; CHECK-LABEL: define void @two_br_not_into_loop_with_split
; CHECK-SAME: (i1 [[X:%.*]]) {
; CHECK-NEXT:    br i1 true, label [[BB2:%.*]], label [[SPLIT1:%.*]]
; CHECK:       bb2:
; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[SPLIT2:%.*]]
; CHECK:       split1:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       split2:
; CHECK-NEXT:    br label [[LOOP]]
; CHECK:       loop:
; CHECK-NEXT:    br label [[LOOP]]
; CHECK:       exit:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    ret void
;
  %c = or i1 %x, true
  br i1 %c, label %bb2, label %split1

bb2:
  %c2 = or i1 %x, true
  br i1 %c2, label %exit, label %split2

split1:
  call void @dummy()
  br label %loop

split2:
  call void @dummy()
  br label %loop

loop:
  call void @dummy()
  br label %loop

exit:
  call void @dummy()
  ret void
}

define void @irreducible() {
; CHECK-LABEL: define void @irreducible() {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 false, label [[LOOP2:%.*]], label [[LOOP1:%.*]]
; CHECK:       loop1:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    br label [[LOOP2]]
; CHECK:       loop2:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[LOOP1]]
; CHECK:       exit:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    ret void
;
entry:
  br i1 false, label %loop2, label %loop1

loop1:
  call void @dummy()
  br label %loop2

loop2:
  call void @dummy()
  br i1 true, label %exit, label %loop1

exit:
  call void @dummy()
  ret void
}

define void @really_unreachable() {
; CHECK-LABEL: define void @really_unreachable() {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    ret void
; CHECK:       unreachable:
; CHECK-NEXT:    ret void
;
entry:
  ret void

unreachable:
  call void @dummy()
  ret void
}

define void @really_unreachable_predecessor() {
; CHECK-LABEL: define void @really_unreachable_predecessor() {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 false, label [[BB:%.*]], label [[EXIT:%.*]]
; CHECK:       unreachable:
; CHECK-NEXT:    br label [[BB]]
; CHECK:       bb:
; CHECK-NEXT:    ret void
; CHECK:       exit:
; CHECK-NEXT:    call void @dummy()
; CHECK-NEXT:    ret void
;
entry:
  br i1 false, label %bb, label %exit

unreachable:
  call void @dummy()
  br label %bb

bb:
  call void @dummy()
  ret void

exit:
  call void @dummy()
  ret void
}

define i32 @pr64235() {
; CHECK-LABEL: define i32 @pr64235() {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 false, label [[BB:%.*]], label [[BB3:%.*]]
; CHECK:       bb3:
; CHECK-NEXT:    store i1 true, ptr poison, align 1
; CHECK-NEXT:    br label [[BB2:%.*]]
; CHECK:       bb:
; CHECK-NEXT:    br label [[BB2]]
; CHECK:       bb2:
; CHECK-NEXT:    br label [[BB]]
;
entry:
  br i1 false, label %bb, label %bb3

bb3:
  call void @llvm.assume(i1 false)
  br label %bb2

bb:
  br label %bb2

bb2:
  call void @llvm.assume(i1 false)
  br label %bb
}

declare void @invoke(ptr)
declare i32 @__gxx_personality_v0(...)
define void @test(i1 %x) personality ptr @__gxx_personality_v0  {
; CHECK-LABEL: define void @test
; CHECK-SAME: (i1 [[X:%.*]]) personality ptr @__gxx_personality_v0 {
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[X]], label [[IF_ELSE:%.*]], label [[CLEAN1:%.*]]
; CHECK:       if.else:
; CHECK-NEXT:    store i32 1, ptr undef, align 4
; CHECK-NEXT:    invoke void @invoke(ptr poison)
; CHECK-NEXT:            to label [[CONT:%.*]] unwind label [[LPAD5:%.*]]
; CHECK:       cont:
; CHECK-NEXT:    invoke void @invoke(ptr poison)
; CHECK-NEXT:            to label [[CLEAN1]] unwind label [[LPAD6:%.*]]
; CHECK:       lpad5:
; CHECK-NEXT:    [[TMP0:%.*]] = landingpad { ptr, i32 }
; CHECK-NEXT:            cleanup
; CHECK-NEXT:    br label [[CLEAN1]]
; CHECK:       lpad6:
; CHECK-NEXT:    [[TMP1:%.*]] = landingpad { ptr, i32 }
; CHECK-NEXT:            cleanup
; CHECK-NEXT:    br label [[CLEAN2:%.*]]
; CHECK:       clean1:
; CHECK-NEXT:    ret void
; CHECK:       clean2:
; CHECK-NEXT:    ret void
;
entry:
  %ref = alloca ptr
  br i1 %x, label %if.else, label %clean1

if.else:
  store i32 1, ptr undef
  invoke void @invoke(ptr %ref)
  to label %cont unwind label %lpad5

cont:
  invoke void @invoke(ptr %ref)
  to label %clean1 unwind label %lpad6

lpad5:
  %13 = landingpad { ptr, i32 }
  cleanup
  br label %clean1

lpad6:
  %14 = landingpad { ptr, i32 }
  cleanup
  br label %clean2

clean1:
  ret void

clean2:
  ret void
}

;; NOTE: These prefixes are unused and the list is autogenerated. Do not add tests below this line:
; DEFAULT_ITER: {{.*}}
; MAX1: {{.*}}