; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=unify-loop-exits -max-booleans-in-control-flow-hub=1 -S | FileCheck %s
; RUN: opt < %s -passes=unify-loop-exits -S | FileCheck --check-prefix=BOOLEAN %s

; A loop with multiple exit blocks.

define void @loop_two_exits(i1 %PredEntry, i1 %PredA) {
; CHECK-LABEL: @loop_two_exits(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[E:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[C:%.*]] ]
; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[LOOP_EXIT_GUARD:%.*]], label [[C]]
; CHECK:       B:
; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0:[0-9]+]]
; CHECK-NEXT:    br label [[D:%.*]]
; CHECK:       C:
; CHECK-NEXT:    [[INC2]] = add i32 [[INC1]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[INC2]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
; CHECK:       D:
; CHECK-NEXT:    unreachable
; CHECK:       E:
; CHECK-NEXT:    ret void
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[MERGED_BB_IDX:%.*]] = phi i32 [ 0, [[A]] ], [ 1, [[C]] ]
; CHECK-NEXT:    [[B_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 0
; CHECK-NEXT:    br i1 [[B_PREDICATE]], label [[B:%.*]], label [[E]]
;
; BOOLEAN-LABEL: @loop_two_exits(
; BOOLEAN-NEXT:  entry:
; BOOLEAN-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[E:%.*]]
; BOOLEAN:       A:
; BOOLEAN-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[C:%.*]] ]
; BOOLEAN-NEXT:    br i1 [[PREDA:%.*]], label [[LOOP_EXIT_GUARD:%.*]], label [[C]]
; BOOLEAN:       B:
; BOOLEAN-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0:[0-9]+]]
; BOOLEAN-NEXT:    br label [[D:%.*]]
; BOOLEAN:       C:
; BOOLEAN-NEXT:    [[INC2]] = add i32 [[INC1]], 1
; BOOLEAN-NEXT:    [[CMP:%.*]] = icmp ult i32 [[INC2]], 10
; BOOLEAN-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
; BOOLEAN:       D:
; BOOLEAN-NEXT:    unreachable
; BOOLEAN:       E:
; BOOLEAN-NEXT:    ret void
; BOOLEAN:       loop.exit.guard:
; BOOLEAN-NEXT:    [[GUARD_B:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
; BOOLEAN-NEXT:    br i1 [[GUARD_B]], label [[B:%.*]], label [[E]]
;
entry:
  br i1 %PredEntry, label %A, label %E

A:
  %inc1 = phi i32 [ 0, %entry ], [ %inc2, %C ]
  br i1 %PredA, label %B, label %C

B:
  tail call fastcc void @check(i32 1) #0
  br label %D

C:
  %inc2 = add i32 %inc1, 1
  %cmp = icmp ult i32 %inc2, 10
  br i1 %cmp, label %A, label %E

D:
  unreachable

E:
  ret void
}

; The loop exit blocks appear in an inner loop.

define void @inner_loop(i1 %PredEntry, i1 %PredA, i1 %PredB) {
; CHECK-LABEL: @inner_loop(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[I:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[OUTER1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER2:%.*]], [[G:%.*]] ]
; CHECK-NEXT:    br label [[B:%.*]]
; CHECK:       B:
; CHECK-NEXT:    [[INNER1:%.*]] = phi i32 [ 0, [[A]] ], [ [[INNER2:%.*]], [[F:%.*]] ]
; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[D:%.*]], label [[LOOP_EXIT_GUARD2:%.*]]
; CHECK:       C:
; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
; CHECK-NEXT:    br label [[H:%.*]]
; CHECK:       D:
; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[LOOP_EXIT_GUARD2]], label [[F]]
; CHECK:       E:
; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
; CHECK-NEXT:    br label [[H]]
; CHECK:       F:
; CHECK-NEXT:    [[INNER2]] = add i32 [[INNER1]], 1
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[INNER2]], 20
; CHECK-NEXT:    br i1 [[CMP1]], label [[B]], label [[LOOP_EXIT_GUARD2]]
; CHECK:       G:
; CHECK-NEXT:    [[OUTER2]] = add i32 [[OUTER1]], 1
; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[OUTER2]], 10
; CHECK-NEXT:    br i1 [[CMP2]], label [[A]], label [[LOOP_EXIT_GUARD:%.*]]
; CHECK:       H:
; CHECK-NEXT:    unreachable
; CHECK:       I:
; CHECK-NEXT:    ret void
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[MERGED_BB_IDX:%.*]] = phi i32 [ 2, [[G]] ], [ [[MERGED_BB_IDX_MOVED:%.*]], [[LOOP_EXIT_GUARD2]] ]
; CHECK-NEXT:    [[C_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 0
; CHECK-NEXT:    br i1 [[C_PREDICATE]], label [[C:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
; CHECK:       loop.exit.guard1:
; CHECK-NEXT:    [[E_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 1
; CHECK-NEXT:    br i1 [[E_PREDICATE]], label [[E:%.*]], label [[I]]
; CHECK:       loop.exit.guard2:
; CHECK-NEXT:    [[MERGED_BB_IDX_MOVED]] = phi i32 [ 0, [[B]] ], [ 1, [[D]] ], [ undef, [[F]] ]
; CHECK-NEXT:    [[MERGED_BB_IDX3:%.*]] = phi i32 [ 0, [[B]] ], [ 0, [[D]] ], [ 1, [[F]] ]
; CHECK-NEXT:    [[LOOP_EXIT_GUARD_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX3]], 0
; CHECK-NEXT:    br i1 [[LOOP_EXIT_GUARD_PREDICATE]], label [[LOOP_EXIT_GUARD]], label [[G]]
;
; BOOLEAN-LABEL: @inner_loop(
; BOOLEAN-NEXT:  entry:
; BOOLEAN-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[I:%.*]]
; BOOLEAN:       A:
; BOOLEAN-NEXT:    [[OUTER1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER2:%.*]], [[G:%.*]] ]
; BOOLEAN-NEXT:    br label [[B:%.*]]
; BOOLEAN:       B:
; BOOLEAN-NEXT:    [[INNER1:%.*]] = phi i32 [ 0, [[A]] ], [ [[INNER2:%.*]], [[F:%.*]] ]
; BOOLEAN-NEXT:    br i1 [[PREDA:%.*]], label [[D:%.*]], label [[LOOP_EXIT_GUARD2:%.*]]
; BOOLEAN:       C:
; BOOLEAN-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
; BOOLEAN-NEXT:    br label [[H:%.*]]
; BOOLEAN:       D:
; BOOLEAN-NEXT:    br i1 [[PREDB:%.*]], label [[LOOP_EXIT_GUARD2]], label [[F]]
; BOOLEAN:       E:
; BOOLEAN-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
; BOOLEAN-NEXT:    br label [[H]]
; BOOLEAN:       F:
; BOOLEAN-NEXT:    [[INNER2]] = add i32 [[INNER1]], 1
; BOOLEAN-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[INNER2]], 20
; BOOLEAN-NEXT:    br i1 [[CMP1]], label [[B]], label [[LOOP_EXIT_GUARD2]]
; BOOLEAN:       G:
; BOOLEAN-NEXT:    [[OUTER2]] = add i32 [[OUTER1]], 1
; BOOLEAN-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[OUTER2]], 10
; BOOLEAN-NEXT:    br i1 [[CMP2]], label [[A]], label [[LOOP_EXIT_GUARD:%.*]]
; BOOLEAN:       H:
; BOOLEAN-NEXT:    unreachable
; BOOLEAN:       I:
; BOOLEAN-NEXT:    ret void
; BOOLEAN:       loop.exit.guard:
; BOOLEAN-NEXT:    [[GUARD_C:%.*]] = phi i1 [ false, [[G]] ], [ [[GUARD_C_MOVED:%.*]], [[LOOP_EXIT_GUARD2]] ]
; BOOLEAN-NEXT:    [[GUARD_E:%.*]] = phi i1 [ false, [[G]] ], [ [[GUARD_E_MOVED:%.*]], [[LOOP_EXIT_GUARD2]] ]
; BOOLEAN-NEXT:    br i1 [[GUARD_C]], label [[C:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
; BOOLEAN:       loop.exit.guard1:
; BOOLEAN-NEXT:    br i1 [[GUARD_E]], label [[E:%.*]], label [[I]]
; BOOLEAN:       loop.exit.guard2:
; BOOLEAN-NEXT:    [[GUARD_E_MOVED]] = phi i1 [ false, [[B]] ], [ true, [[D]] ], [ undef, [[F]] ]
; BOOLEAN-NEXT:    [[GUARD_C_MOVED]] = phi i1 [ true, [[B]] ], [ false, [[D]] ], [ undef, [[F]] ]
; BOOLEAN-NEXT:    [[GUARD_LOOP_EXIT_GUARD:%.*]] = phi i1 [ true, [[B]] ], [ true, [[D]] ], [ false, [[F]] ]
; BOOLEAN-NEXT:    br i1 [[GUARD_LOOP_EXIT_GUARD]], label [[LOOP_EXIT_GUARD]], label [[G]]
;
entry:
  br i1 %PredEntry, label %A, label %I

A:
  %outer1 = phi i32 [ 0, %entry ], [ %outer2, %G ]
  br label %B

B:
  %inner1 = phi i32 [ 0, %A ], [ %inner2, %F ]
  br i1 %PredA, label %D, label %C

C:
  tail call fastcc void @check(i32 1) #0
  br label %H

D:
  br i1 %PredB, label %E, label %F

E:
  tail call fastcc void @check(i32 2) #0
  br label %H

F:
  %inner2 = add i32 %inner1, 1
  %cmp1 = icmp ult i32 %inner2, 20
  br i1 %cmp1, label %B, label %G

G:
  %outer2 = add i32 %outer1, 1
  %cmp2 = icmp ult i32 %outer2, 10
  br i1 %cmp2, label %A, label %I

H:
  unreachable

I:
  ret void
}

; A loop with more exit blocks.

define void @loop_five_exits(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD) {
; CHECK-LABEL: @loop_five_exits(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[L:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[I:%.*]] ]
; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[LOOP_EXIT_GUARD:%.*]], label [[C:%.*]]
; CHECK:       B:
; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
; CHECK-NEXT:    br label [[J:%.*]]
; CHECK:       C:
; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[LOOP_EXIT_GUARD]], label [[E:%.*]]
; CHECK:       D:
; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
; CHECK-NEXT:    br label [[J]]
; CHECK:       E:
; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[LOOP_EXIT_GUARD]], label [[G:%.*]]
; CHECK:       F:
; CHECK-NEXT:    tail call fastcc void @check(i32 3) #[[ATTR0]]
; CHECK-NEXT:    br label [[K:%.*]]
; CHECK:       G:
; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[LOOP_EXIT_GUARD]], label [[I]]
; CHECK:       H:
; CHECK-NEXT:    tail call fastcc void @check(i32 4) #[[ATTR0]]
; CHECK-NEXT:    br label [[K]]
; CHECK:       I:
; CHECK-NEXT:    [[INC2]] = add i32 [[INC1]], 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[INC2]], 10
; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
; CHECK:       J:
; CHECK-NEXT:    br label [[L]]
; CHECK:       K:
; CHECK-NEXT:    br label [[L]]
; CHECK:       L:
; CHECK-NEXT:    ret void
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[MERGED_BB_IDX:%.*]] = phi i32 [ 0, [[A]] ], [ 1, [[C]] ], [ 2, [[E]] ], [ 3, [[G]] ], [ 4, [[I]] ]
; CHECK-NEXT:    [[B_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 0
; CHECK-NEXT:    br i1 [[B_PREDICATE]], label [[B:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
; CHECK:       loop.exit.guard1:
; CHECK-NEXT:    [[D_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 1
; CHECK-NEXT:    br i1 [[D_PREDICATE]], label [[D:%.*]], label [[LOOP_EXIT_GUARD2:%.*]]
; CHECK:       loop.exit.guard2:
; CHECK-NEXT:    [[F_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 2
; CHECK-NEXT:    br i1 [[F_PREDICATE]], label [[F:%.*]], label [[LOOP_EXIT_GUARD3:%.*]]
; CHECK:       loop.exit.guard3:
; CHECK-NEXT:    [[H_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 3
; CHECK-NEXT:    br i1 [[H_PREDICATE]], label [[H:%.*]], label [[L]]
;
; BOOLEAN-LABEL: @loop_five_exits(
; BOOLEAN-NEXT:  entry:
; BOOLEAN-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[L:%.*]]
; BOOLEAN:       A:
; BOOLEAN-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[I:%.*]] ]
; BOOLEAN-NEXT:    br i1 [[PREDA:%.*]], label [[LOOP_EXIT_GUARD:%.*]], label [[C:%.*]]
; BOOLEAN:       B:
; BOOLEAN-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
; BOOLEAN-NEXT:    br label [[J:%.*]]
; BOOLEAN:       C:
; BOOLEAN-NEXT:    br i1 [[PREDB:%.*]], label [[LOOP_EXIT_GUARD]], label [[E:%.*]]
; BOOLEAN:       D:
; BOOLEAN-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
; BOOLEAN-NEXT:    br label [[J]]
; BOOLEAN:       E:
; BOOLEAN-NEXT:    br i1 [[PREDC:%.*]], label [[LOOP_EXIT_GUARD]], label [[G:%.*]]
; BOOLEAN:       F:
; BOOLEAN-NEXT:    tail call fastcc void @check(i32 3) #[[ATTR0]]
; BOOLEAN-NEXT:    br label [[K:%.*]]
; BOOLEAN:       G:
; BOOLEAN-NEXT:    br i1 [[PREDD:%.*]], label [[LOOP_EXIT_GUARD]], label [[I]]
; BOOLEAN:       H:
; BOOLEAN-NEXT:    tail call fastcc void @check(i32 4) #[[ATTR0]]
; BOOLEAN-NEXT:    br label [[K]]
; BOOLEAN:       I:
; BOOLEAN-NEXT:    [[INC2]] = add i32 [[INC1]], 1
; BOOLEAN-NEXT:    [[CMP:%.*]] = icmp ult i32 [[INC2]], 10
; BOOLEAN-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
; BOOLEAN:       J:
; BOOLEAN-NEXT:    br label [[L]]
; BOOLEAN:       K:
; BOOLEAN-NEXT:    br label [[L]]
; BOOLEAN:       L:
; BOOLEAN-NEXT:    ret void
; BOOLEAN:       loop.exit.guard:
; BOOLEAN-NEXT:    [[GUARD_B:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ], [ false, [[E]] ], [ false, [[G]] ], [ false, [[I]] ]
; BOOLEAN-NEXT:    [[GUARD_D:%.*]] = phi i1 [ false, [[A]] ], [ true, [[C]] ], [ false, [[E]] ], [ false, [[G]] ], [ false, [[I]] ]
; BOOLEAN-NEXT:    [[GUARD_F:%.*]] = phi i1 [ false, [[A]] ], [ false, [[C]] ], [ true, [[E]] ], [ false, [[G]] ], [ false, [[I]] ]
; BOOLEAN-NEXT:    [[GUARD_H:%.*]] = phi i1 [ false, [[A]] ], [ false, [[C]] ], [ false, [[E]] ], [ true, [[G]] ], [ false, [[I]] ]
; BOOLEAN-NEXT:    br i1 [[GUARD_B]], label [[B:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
; BOOLEAN:       loop.exit.guard1:
; BOOLEAN-NEXT:    br i1 [[GUARD_D]], label [[D:%.*]], label [[LOOP_EXIT_GUARD2:%.*]]
; BOOLEAN:       loop.exit.guard2:
; BOOLEAN-NEXT:    br i1 [[GUARD_F]], label [[F:%.*]], label [[LOOP_EXIT_GUARD3:%.*]]
; BOOLEAN:       loop.exit.guard3:
; BOOLEAN-NEXT:    br i1 [[GUARD_H]], label [[H:%.*]], label [[L]]
;
entry:
  br i1 %PredEntry, label %A, label %L

A:
  %inc1 = phi i32 [ 0, %entry ], [ %inc2, %I ]
  br i1 %PredA, label %B, label %C

B:
  tail call fastcc void @check(i32 1) #0
  br label %J

C:
  br i1 %PredB, label %D, label %E

D:
  tail call fastcc void @check(i32 2) #0
  br label %J

E:
  br i1 %PredC, label %F, label %G

F:
  tail call fastcc void @check(i32 3) #0
  br label %K

G:
  br i1 %PredD, label %H, label %I

H:
  tail call fastcc void @check(i32 4) #0
  br label %K

I:
  %inc2 = add i32 %inc1, 1
  %cmp = icmp ult i32 %inc2, 10
  br i1 %cmp, label %A, label %L

J:
  br label %L

K:
  br label %L

L:
  ret void
}


declare void @check(i32 noundef %i) #0

attributes #0 = { noreturn nounwind }