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

define void @loop_1(i1 %PredEntry, i1 %PredB, i1 %PredC, i1 %PredD) {
; CHECK-LABEL: @loop_1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[G:%.*]]
; CHECK:       A:
; CHECK-NEXT:    br label [[B:%.*]]
; CHECK:       B:
; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[C:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
; CHECK:       C:
; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[D:%.*]], label [[LOOP_EXIT_GUARD]]
; CHECK:       D:
; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[A]], label [[LOOP_EXIT_GUARD]]
; CHECK:       E:
; CHECK-NEXT:    br label [[EXIT:%.*]]
; CHECK:       F:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       G:
; CHECK-NEXT:    br label [[Y:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[GUARD_X:%.*]] = phi i1 [ true, [[B]] ], [ false, [[C]] ], [ false, [[D]] ]
; CHECK-NEXT:    br i1 [[GUARD_X]], label [[X:%.*]], label [[Y]]
;
entry:
  br i1 %PredEntry, label %A, label %G

A:
  br label %B

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

C:
  br i1 %PredC, label %D, label %F

D:
  br i1 %PredD, label %A, label %F

E:
  br label %exit

F:
  br label %exit

G:
  br label %F

exit:
  ret void
}

define void @loop_1_callbr(i1 %PredEntry, i1 %PredB, i1 %PredC, i1 %PredD) {
; CHECK-LABEL: @loop_1_callbr(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[G:%.*]]
; CHECK:       A:
; CHECK-NEXT:    br label [[B:%.*]]
; CHECK:       B:
; CHECK-NEXT:    callbr void asm "", "r,!i"(i1 [[PREDB:%.*]])
; CHECK-NEXT:            to label [[C:%.*]] [label [[B_TARGET_E:%.*]]]
; CHECK:       C:
; CHECK-NEXT:    callbr void asm "", "r,!i"(i1 [[PREDC:%.*]])
; CHECK-NEXT:            to label [[D:%.*]] [label [[C_TARGET_F:%.*]]]
; CHECK:       D:
; CHECK-NEXT:    callbr void asm "", "r,!i"(i1 [[PREDD:%.*]])
; CHECK-NEXT:            to label [[A]] [label [[D_TARGET_F:%.*]]]
; CHECK:       E:
; CHECK-NEXT:    br label [[EXIT:%.*]]
; CHECK:       F:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       G:
; CHECK-NEXT:    br label [[F:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       B.target.E:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD:%.*]]
; CHECK:       C.target.F:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       D.target.F:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[GUARD_E:%.*]] = phi i1 [ true, [[B_TARGET_E]] ], [ false, [[C_TARGET_F]] ], [ false, [[D_TARGET_F]] ]
; CHECK-NEXT:    br i1 [[GUARD_E]], label [[E:%.*]], label [[F]]
;
entry:
  br i1 %PredEntry, label %A, label %G

A:
  br label %B

B:
  callbr void asm "", "r,!i"(i1 %PredB) to label %C [label %E]

C:
  callbr void asm "", "r,!i"(i1 %PredC) to label %D [label %F]

D:
  callbr void asm "", "r,!i"(i1 %PredD) to label %A [label %F]

E:
  br label %exit

F:
  br label %exit

G:
  br label %F

exit:
  ret void
}

define void @loop_1_switch(i1 %PredEntry, i1 %PredB, i1 %PredC, i1 %PredD) {
; CHECK-LABEL: @loop_1_switch(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    switch i1 [[PREDENTRY:%.*]], label [[A:%.*]] [
; CHECK-NEXT:      i1 false, label [[G:%.*]]
; CHECK-NEXT:    ]
; CHECK:       A:
; CHECK-NEXT:    br label [[B:%.*]]
; CHECK:       B:
; CHECK-NEXT:    switch i1 [[PREDB:%.*]], label [[C:%.*]] [
; CHECK-NEXT:      i1 false, label [[B_TARGET_E:%.*]]
; CHECK-NEXT:    ]
; CHECK:       C:
; CHECK-NEXT:    switch i1 [[PREDC:%.*]], label [[D:%.*]] [
; CHECK-NEXT:      i1 false, label [[C_TARGET_F:%.*]]
; CHECK-NEXT:    ]
; CHECK:       D:
; CHECK-NEXT:    switch i1 [[PREDD:%.*]], label [[A]] [
; CHECK-NEXT:      i1 false, label [[D_TARGET_F:%.*]]
; CHECK-NEXT:    ]
; CHECK:       E:
; CHECK-NEXT:    br label [[EXIT:%.*]]
; CHECK:       F:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       G:
; CHECK-NEXT:    br label [[F:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       B.target.E:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD:%.*]]
; CHECK:       C.target.F:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       D.target.F:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[GUARD_E:%.*]] = phi i1 [ true, [[B_TARGET_E]] ], [ false, [[C_TARGET_F]] ], [ false, [[D_TARGET_F]] ]
; CHECK-NEXT:    br i1 [[GUARD_E]], label [[E:%.*]], label [[F]]
;
entry:
  switch i1 %PredEntry, label %A [ i1 0, label %G ]

A:
  br label %B

B:
  switch i1 %PredB, label %C [ i1 0, label %E ]

C:
  switch i1 %PredC, label %D [ i1 0, label %F ]

D:
  switch i1 %PredD, label %A [ i1 0, label %F ]

E:
  br label %exit

F:
  br label %exit

G:
  br label %F

exit:
  ret void
}

define void @loop_2(i1 %PredA, i1 %PredB, i1 %PredC) {
; CHECK-LABEL: @loop_2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[A:%.*]]
; CHECK:       A:
; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[B:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
; CHECK:       B:
; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[C:%.*]], label [[LOOP_EXIT_GUARD]]
; CHECK:       C:
; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[D:%.*]], label [[LOOP_EXIT_GUARD]]
; CHECK:       D:
; CHECK-NEXT:    br label [[A]]
; CHECK:       X:
; CHECK-NEXT:    br label [[EXIT:%.*]]
; CHECK:       Y:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       Z:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[GUARD_X:%.*]] = phi i1 [ true, [[A]] ], [ false, [[B]] ], [ false, [[C]] ]
; CHECK-NEXT:    [[GUARD_Y:%.*]] = phi i1 [ false, [[A]] ], [ true, [[B]] ], [ false, [[C]] ]
; CHECK-NEXT:    br i1 [[GUARD_X]], label [[X:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
; CHECK:       loop.exit.guard1:
; CHECK-NEXT:    br i1 [[GUARD_Y]], label [[Y:%.*]], label [[Z:%.*]]
;
entry:
  br label %A

A:
  br i1 %PredA, label %B, label %X

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

C:
  br i1 %PredC, label %D, label %Z

D:
  br label %A

X:
  br label %exit

Y:
  br label %exit

Z:
  br label %exit

exit:
  ret void
}

define void @loop_2_callbr(i1 %PredA, i1 %PredB, i1 %PredC) {
; CHECK-LABEL: @loop_2_callbr(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[A:%.*]]
; CHECK:       A:
; CHECK-NEXT:    callbr void asm "", "r,!i"(i1 [[PREDA:%.*]])
; CHECK-NEXT:            to label [[B:%.*]] [label [[A_TARGET_X:%.*]]]
; CHECK:       B:
; CHECK-NEXT:    callbr void asm "", "r,!i"(i1 [[PREDB:%.*]])
; CHECK-NEXT:            to label [[C:%.*]] [label [[B_TARGET_Y:%.*]]]
; CHECK:       C:
; CHECK-NEXT:    callbr void asm "", "r,!i"(i1 [[PREDC:%.*]])
; CHECK-NEXT:            to label [[D:%.*]] [label [[C_TARGET_Z:%.*]]]
; CHECK:       D:
; CHECK-NEXT:    br label [[A]]
; CHECK:       X:
; CHECK-NEXT:    br label [[EXIT:%.*]]
; CHECK:       Y:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       Z:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       A.target.X:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD:%.*]]
; CHECK:       B.target.Y:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       C.target.Z:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[GUARD_X:%.*]] = phi i1 [ true, [[A_TARGET_X]] ], [ false, [[B_TARGET_Y]] ], [ false, [[C_TARGET_Z]] ]
; CHECK-NEXT:    [[GUARD_Y:%.*]] = phi i1 [ false, [[A_TARGET_X]] ], [ true, [[B_TARGET_Y]] ], [ false, [[C_TARGET_Z]] ]
; CHECK-NEXT:    br i1 [[GUARD_X]], label [[X:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
; CHECK:       loop.exit.guard1:
; CHECK-NEXT:    br i1 [[GUARD_Y]], label [[Y:%.*]], label [[Z:%.*]]
;
entry:
  br label %A

A:
  callbr void asm "", "r,!i"(i1 %PredA) to label %B [label %X]

B:
  callbr void asm "", "r,!i"(i1 %PredB) to label %C [label %Y]

C:
  callbr void asm "", "r,!i"(i1 %PredC) to label %D [label %Z]

D:
  br label %A

X:
  br label %exit

Y:
  br label %exit

Z:
  br label %exit

exit:
  ret void
}

define void @loop_2_switch(i1 %PredA, i1 %PredB, i1 %PredC) {
; CHECK-LABEL: @loop_2_switch(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[A:%.*]]
; CHECK:       A:
; CHECK-NEXT:    switch i1 [[PREDA:%.*]], label [[B:%.*]] [
; CHECK-NEXT:      i1 false, label [[A_TARGET_X:%.*]]
; CHECK-NEXT:    ]
; CHECK:       B:
; CHECK-NEXT:    switch i1 [[PREDB:%.*]], label [[C:%.*]] [
; CHECK-NEXT:      i1 false, label [[B_TARGET_Y:%.*]]
; CHECK-NEXT:    ]
; CHECK:       C:
; CHECK-NEXT:    switch i1 [[PREDC:%.*]], label [[D:%.*]] [
; CHECK-NEXT:      i1 false, label [[C_TARGET_Z:%.*]]
; CHECK-NEXT:    ]
; CHECK:       D:
; CHECK-NEXT:    br label [[A]]
; CHECK:       X:
; CHECK-NEXT:    br label [[EXIT:%.*]]
; CHECK:       Y:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       Z:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       A.target.X:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD:%.*]]
; CHECK:       B.target.Y:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       C.target.Z:
; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
; CHECK:       loop.exit.guard:
; CHECK-NEXT:    [[GUARD_X:%.*]] = phi i1 [ true, [[A_TARGET_X]] ], [ false, [[B_TARGET_Y]] ], [ false, [[C_TARGET_Z]] ]
; CHECK-NEXT:    [[GUARD_Y:%.*]] = phi i1 [ false, [[A_TARGET_X]] ], [ true, [[B_TARGET_Y]] ], [ false, [[C_TARGET_Z]] ]
; CHECK-NEXT:    br i1 [[GUARD_X]], label [[X:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
; CHECK:       loop.exit.guard1:
; CHECK-NEXT:    br i1 [[GUARD_Y]], label [[Y:%.*]], label [[Z:%.*]]
;
entry:
  br label %A

A:
  switch i1 %PredA, label %B [ i1 0, label %X ]

B:
  switch i1 %PredB, label %C [ i1 0, label %Y ]

C:
  switch i1 %PredC, label %D [ i1 0, label %Z ]

D:
  br label %A

X:
  br label %exit

Y:
  br label %exit

Z:
  br label %exit

exit:
  ret void
}

; Test that UnifyLoopExits handles callbr with duplicate successors correctly.
; The exit block appears twice as a successor of the callbr instruction.
define void @callbr_duplicate_successors() {
; CHECK-LABEL: @callbr_duplicate_successors(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    callbr void asm sideeffect "", "!i,!i"()
; CHECK-NEXT:            to label [[LOOP_TARGET_EXIT:%.*]] [label [[LOOP]], label [[LOOP_TARGET_EXIT]]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       loop.target.exit:
; CHECK-NEXT:    br label [[EXIT:%.*]]
;
entry:
  br label %loop

loop:
  callbr void asm sideeffect "", "!i,!i"()
  to label %exit [label %loop, label %exit]

exit:
  ret void
}

define void @switch_duplicate_successors(i1 %Pred) {
; CHECK-LABEL: @switch_duplicate_successors(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[LOOP:%.*]]
; CHECK:       loop:
; CHECK-NEXT:    switch i1 [[PRED:%.*]], label [[LOOP_TARGET_EXIT:%.*]] [
; CHECK-NEXT:      i1 false, label [[LOOP]]
; CHECK-NEXT:      i1 true, label [[LOOP_TARGET_EXIT]]
; CHECK-NEXT:    ]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       loop.target.exit:
; CHECK-NEXT:    br label [[EXIT:%.*]]
;
entry:
  br label %loop

loop:
  switch i1 %Pred, label %exit [
  i1 0, label %loop
  i1 1, label %exit
  ]

exit:
  ret void
}