; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -unify-loop-exits -enable-new-pm=0 -S | FileCheck %s
; RUN: opt < %s -passes=unify-loop-exits -S | FileCheck %s

; A loop has exit blocks, B and D, that branch to the same successor.
; We reduce the number of guard blocks needed by creating the loop
; exit guard block after B and D rather than before B and D.

define void @unreachable_from_loop(i1 %PredEntry, i1 %PredA, i1 %PredB) {
; CHECK-LABEL: @unreachable_from_loop(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[G:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[E:%.*]] ]
; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[B:%.*]], label [[C:%.*]]
; CHECK:       B:
; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0:[0-9]+]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD:%.*]]
; CHECK:       C:
; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[D:%.*]], label [[E]]
; CHECK:       D:
; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       E:
; 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:       F:
; CHECK-NEXT:    unreachable
; CHECK:       G:
; CHECK-NEXT:    ret void
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[GUARD_G:%.*]] = phi i1 [ true, [[E]] ], [ false, [[B]] ], [ false, [[D]] ]
; CHECK-NEXT:    br i1 [[GUARD_G]], label [[G]], label [[F:%.*]]
;
entry:
  br i1 %PredEntry, label %A, label %G

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

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

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

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

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

F:
  unreachable

G:
  ret void
}

; A test when the loop exit blocks appear in an inner loop.

define void @unreachable_from_inner_loop(i1 %PredEntry, i1 %PredA, i1 %PredB) {
; CHECK-LABEL: @unreachable_from_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 [[C:%.*]]
; CHECK:       C:
; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD1:%.*]]
; CHECK:       D:
; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[E:%.*]], label [[F]]
; CHECK:       E:
; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD1]]
; 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_GUARD1]]
; 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:    [[GUARD_I:%.*]] = phi i1 [ true, [[G]] ], [ [[GUARD_I_MOVED:%.*]], [[LOOP_EXIT_GUARD1]] ]
; CHECK-NEXT:    br i1 [[GUARD_I]], label [[I]], label [[H:%.*]]
; CHECK:       loop.exit.guard1:
; CHECK-NEXT:    [[GUARD_G:%.*]] = phi i1 [ true, [[F]] ], [ false, [[C]] ], [ false, [[E]] ]
; CHECK-NEXT:    [[GUARD_I_MOVED]] = phi i1 [ undef, [[F]] ], [ false, [[C]] ], [ false, [[E]] ]
; CHECK-NEXT:    br i1 [[GUARD_G]], label [[G]], label [[LOOP_EXIT_GUARD]]
;
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
}

; Test with 3 nested loops to show the case when we need to change the loop for
; the predecessors of the loop guard. Since UnifyLoopExits works from the outer
; loop to the inner loop, the predecessors are added to the outermost loop.
; When a guard block is added to the exit of the inner loop, the predecessor
; block loops need to change to the middle loop.

define void @three_loops(i1 %PredEntry, i1 %PredA, i1 %PredB) {
; CHECK-LABEL: @three_loops(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[L1:%.*]], label [[H:%.*]]
; CHECK:       L1:
; CHECK-NEXT:    [[I1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I2:%.*]], [[F:%.*]] ]
; CHECK-NEXT:    br label [[L2:%.*]]
; CHECK:       L2:
; CHECK-NEXT:    [[J1:%.*]] = phi i32 [ 0, [[L1]] ], [ [[J2:%.*]], [[E:%.*]] ]
; CHECK-NEXT:    br label [[L3:%.*]]
; CHECK:       L3:
; CHECK-NEXT:    [[K1:%.*]] = phi i32 [ 0, [[L2]] ], [ [[K2:%.*]], [[D:%.*]] ]
; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[A:%.*]], label [[B:%.*]]
; CHECK:       A:
; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD2:%.*]]
; CHECK:       B:
; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[C:%.*]], label [[D]]
; CHECK:       C:
; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD2]]
; CHECK:       D:
; CHECK-NEXT:    [[K2]] = add i32 [[K1]], 1
; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[K2]], 20
; CHECK-NEXT:    br i1 [[CMP1]], label [[L3]], label [[LOOP_EXIT_GUARD2]]
; CHECK:       E:
; CHECK-NEXT:    [[J2]] = add i32 [[J1]], 1
; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[J2]], 10
; CHECK-NEXT:    br i1 [[CMP2]], label [[L2]], label [[LOOP_EXIT_GUARD1:%.*]]
; CHECK:       F:
; CHECK-NEXT:    [[I2]] = add i32 [[I1]], 1
; CHECK-NEXT:    [[CMP3:%.*]] = icmp ult i32 [[I2]], 5
; CHECK-NEXT:    br i1 [[CMP3]], label [[L1]], label [[LOOP_EXIT_GUARD:%.*]]
; CHECK:       G:
; CHECK-NEXT:    unreachable
; CHECK:       H:
; CHECK-NEXT:    ret void
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[GUARD_H:%.*]] = phi i1 [ true, [[F]] ], [ [[GUARD_H_MOVED:%.*]], [[LOOP_EXIT_GUARD1]] ]
; CHECK-NEXT:    br i1 [[GUARD_H]], label [[H]], label [[G:%.*]]
; CHECK:       loop.exit.guard1:
; CHECK-NEXT:    [[GUARD_F:%.*]] = phi i1 [ true, [[E]] ], [ [[GUARD_F_MOVED:%.*]], [[LOOP_EXIT_GUARD2]] ]
; CHECK-NEXT:    [[GUARD_H_MOVED]] = phi i1 [ undef, [[E]] ], [ [[GUARD_H_MOVED_MOVED:%.*]], [[LOOP_EXIT_GUARD2]] ]
; CHECK-NEXT:    br i1 [[GUARD_F]], label [[F]], label [[LOOP_EXIT_GUARD]]
; CHECK:       loop.exit.guard2:
; CHECK-NEXT:    [[GUARD_E:%.*]] = phi i1 [ true, [[D]] ], [ false, [[A]] ], [ false, [[C]] ]
; CHECK-NEXT:    [[GUARD_F_MOVED]] = phi i1 [ undef, [[D]] ], [ false, [[A]] ], [ false, [[C]] ]
; CHECK-NEXT:    [[GUARD_H_MOVED_MOVED]] = phi i1 [ undef, [[D]] ], [ false, [[A]] ], [ false, [[C]] ]
; CHECK-NEXT:    br i1 [[GUARD_E]], label [[E]], label [[LOOP_EXIT_GUARD1]]
;
entry:
  br i1 %PredEntry, label %L1, label %H

L1:
  %i1 = phi i32 [ 0, %entry ], [ %i2, %F ]
  br label %L2

L2:
  %j1 = phi i32 [ 0, %L1 ], [ %j2, %E ]
  br label %L3

L3:
  %k1 = phi i32 [ 0, %L2 ], [ %k2, %D ]
  br i1 %PredA, label %A, label %B

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

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

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

D:
  %k2 = add i32 %k1, 1
  %cmp1 = icmp ult i32 %k2, 20
  br i1 %cmp1, label %L3, label %E

E:
  %j2 = add i32 %j1, 1
  %cmp2 = icmp ult i32 %j2, 10
  br i1 %cmp2, label %L2, label %F

F:
  %i2 = add i32 %i1, 1
  %cmp3 = icmp ult i32 %i2, 5
  br i1 %cmp3, label %L1, label %H

G:
  unreachable

H:
  ret void
}


; The common successor does not have to be an unreachable block.

define void @common_exit(i1 %PredEntry, i1 %PredA, i1 %PredB) {
; CHECK-LABEL: @common_exit(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[G:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[E:%.*]] ]
; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[B:%.*]], label [[C:%.*]]
; CHECK:       B:
; CHECK-NEXT:    tail call fastcc void @check1(i32 1) #[[ATTR1:[0-9]+]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD:%.*]]
; CHECK:       C:
; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[D:%.*]], label [[E]]
; CHECK:       D:
; CHECK-NEXT:    tail call fastcc void @check1(i32 2) #[[ATTR1]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       E:
; 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:       F:
; CHECK-NEXT:    br label [[G]]
; CHECK:       G:
; CHECK-NEXT:    ret void
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[GUARD_G:%.*]] = phi i1 [ true, [[E]] ], [ false, [[B]] ], [ false, [[D]] ]
; CHECK-NEXT:    br i1 [[GUARD_G]], label [[G]], label [[F:%.*]]
;
entry:
  br i1 %PredEntry, label %A, label %G

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

B:
  tail call fastcc void @check1(i32 1) #1
  br label %F

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

D:
  tail call fastcc void @check1(i32 2) #1
  br label %F

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

F:
  br label %G

G:
  ret void
}

; A test with multiple common exits.

define void @multiple_common_successors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD) {
; CHECK-LABEL: @multiple_common_successors(
; 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 [[B:%.*]], label [[C:%.*]]
; CHECK:       B:
; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD:%.*]]
; CHECK:       C:
; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[D:%.*]], label [[E:%.*]]
; CHECK:       D:
; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       E:
; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[F:%.*]], label [[G:%.*]]
; CHECK:       F:
; CHECK-NEXT:    tail call fastcc void @check(i32 3) #[[ATTR0]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       G:
; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[H:%.*]], label [[I]]
; CHECK:       H:
; CHECK-NEXT:    tail call fastcc void @check(i32 4) #[[ATTR0]]
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; 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:    [[GUARD_L:%.*]] = phi i1 [ true, [[I]] ], [ false, [[B]] ], [ false, [[D]] ], [ false, [[F]] ], [ false, [[H]] ]
; CHECK-NEXT:    [[GUARD_J:%.*]] = phi i1 [ false, [[I]] ], [ true, [[B]] ], [ true, [[D]] ], [ false, [[F]] ], [ false, [[H]] ]
; CHECK-NEXT:    br i1 [[GUARD_L]], label [[L]], label [[LOOP_EXIT_GUARD1:%.*]]
; CHECK:       loop.exit.guard1:
; CHECK-NEXT:    br i1 [[GUARD_J]], label [[J:%.*]], label [[K:%.*]]
;
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
}

; Test when the loop exit block is tha same as a common successor
; block. The number of guard blocks is unchanged.

define void @common_successor_exit(i1 %PredEntry, i1 %PredA, i1 %PredB) {
; CHECK-LABEL: @common_successor_exit(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[G:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[E:%.*]] ]
; 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 [[G]]
; 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 [[G]]
; CHECK:       E:
; 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:       G:
; CHECK-NEXT:    ret void
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[GUARD_B:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ], [ false, [[E]] ]
; CHECK-NEXT:    [[GUARD_D:%.*]] = phi i1 [ false, [[A]] ], [ true, [[C]] ], [ false, [[E]] ]
; CHECK-NEXT:    br i1 [[GUARD_B]], label [[B:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
; CHECK:       loop.exit.guard1:
; CHECK-NEXT:    br i1 [[GUARD_D]], label [[D:%.*]], label [[G]]
;
entry:
  br i1 %PredEntry, label %A, label %G

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

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

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

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

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

G:
  ret void
}

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

attributes #0 = { noreturn nounwind }
attributes #1 = { nounwind }