; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -fix-irreducible --verify-loop-info -S | FileCheck %s
; RUN: opt < %s -passes='fix-irreducible,verify<loops>' -S | FileCheck %s
; RUN: opt < %s -passes='verify<loops>,fix-irreducible,verify<loops>' -S | FileCheck %s

define void @nested_irr_top_level(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5) {
; CHECK-LABEL: @nested_irr_top_level(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PRED1_INV:%.*]] = xor i1 [[PRED1:%.*]], true
; CHECK-NEXT:    [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       A1:
; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
; CHECK:       B1:
; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[A3:%.*]]
; CHECK:       B2:
; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[B1:%.*]], label [[A3]]
; CHECK:       A3:
; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
; CHECK:       A2:
; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[A1:%.*]], label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[GUARD_A2:%.*]] = phi i1 [ true, [[A3]] ], [ [[PRED0_INV]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    br i1 [[GUARD_A2]], label [[A2:%.*]], label [[A1]]
; CHECK:       irr.guard1:
; CHECK-NEXT:    [[GUARD_B2:%.*]] = phi i1 [ true, [[B1]] ], [ [[PRED1_INV]], [[A1]] ]
; CHECK-NEXT:    br i1 [[GUARD_B2]], label [[B2:%.*]], label [[B1]]
;
entry:
  br i1 %Pred0, label %A1, label %A2

A1:
  br i1 %Pred1, label %B1, label %B2

B1:
  br i1 %Pred2, label %B2, label %A3

B2:
  br i1 %Pred3, label %B1, label %A3

A3:
  br i1 %Pred4, label %A2, label %exit

A2:
  br i1 %Pred5, label %A1, label %exit

exit:
  ret void
}

define void @nested_irr_in_loop(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6) {
; CHECK-LABEL: @nested_irr_in_loop(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PRED1_INV:%.*]] = xor i1 [[PRED1:%.*]], true
; CHECK-NEXT:    [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true
; CHECK-NEXT:    br label [[H1:%.*]]
; CHECK:       H1:
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       A1:
; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
; CHECK:       B1:
; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[A3:%.*]]
; CHECK:       B2:
; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[B1:%.*]], label [[A3]]
; CHECK:       A3:
; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[L1:%.*]]
; CHECK:       A2:
; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[A1:%.*]], label [[L1]]
; CHECK:       L1:
; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[EXIT:%.*]], label [[H1]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[GUARD_A2:%.*]] = phi i1 [ true, [[A3]] ], [ [[PRED0_INV]], [[H1]] ]
; CHECK-NEXT:    br i1 [[GUARD_A2]], label [[A2:%.*]], label [[A1]]
; CHECK:       irr.guard1:
; CHECK-NEXT:    [[GUARD_B2:%.*]] = phi i1 [ true, [[B1]] ], [ [[PRED1_INV]], [[A1]] ]
; CHECK-NEXT:    br i1 [[GUARD_B2]], label [[B2:%.*]], label [[B1]]
;
entry:
  br label %H1

H1:
  br i1 %Pred0, label %A1, label %A2

A1:
  br i1 %Pred1, label %B1, label %B2

B1:
  br i1 %Pred2, label %B2, label %A3

B2:
  br i1 %Pred3, label %B1, label %A3

A3:
  br i1 %Pred4, label %A2, label %L1

A2:
  br i1 %Pred5, label %A1, label %L1

L1:
  br i1 %Pred6, label %exit, label %H1

exit:
  ret void
}

define void @loop_in_irr(i1 %Pred0, i1 %Pred1, i1 %Pred2) {
; CHECK-LABEL: @loop_in_irr(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       A1:
; CHECK-NEXT:    br label [[H1:%.*]]
; CHECK:       H1:
; CHECK-NEXT:    br label [[L1:%.*]]
; CHECK:       L1:
; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[H1]], label [[A3:%.*]]
; CHECK:       A3:
; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
; CHECK:       A2:
; CHECK-NEXT:    br label [[A1:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[GUARD_A2:%.*]] = phi i1 [ true, [[A3]] ], [ [[PRED0_INV]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    br i1 [[GUARD_A2]], label [[A2:%.*]], label [[A1]]
;
entry:
  br i1 %Pred0, label %A1, label %A2

A1:
  br label %H1

H1:
  br label %L1

L1:
  br i1 %Pred1, label %H1, label %A3

A3:
  br i1 %Pred2, label %A2, label %exit

A2:
  br label %A1

exit:
  ret void
}

define void @loop_in_irr_shared_entry(i1 %Pred0, i1 %Pred1, i1 %Pred2) {
; CHECK-LABEL: @loop_in_irr_shared_entry(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       H1:
; CHECK-NEXT:    br label [[L1:%.*]]
; CHECK:       L1:
; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[H1:%.*]], label [[A3:%.*]]
; CHECK:       A3:
; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
; CHECK:       A2:
; CHECK-NEXT:    br label [[H1]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[GUARD_A2:%.*]] = phi i1 [ true, [[A3]] ], [ [[PRED0_INV]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    br i1 [[GUARD_A2]], label [[A2:%.*]], label [[H1]]
;
entry:
  br i1 %Pred0, label %H1, label %A2

H1:
  br label %L1

L1:
  br i1 %Pred1, label %H1, label %A3

A3:
  br i1 %Pred2, label %A2, label %exit

A2:
  br label %H1

exit:
  ret void
}

define void @loop_in_irr_shared_header(i1 %Pred0, i1 %Pred1, i1 %Pred2) {
; CHECK-LABEL: @loop_in_irr_shared_header(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       H1:
; CHECK-NEXT:    br label [[L1:%.*]]
; CHECK:       L1:
; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[IRR_GUARD]], label [[A3:%.*]]
; CHECK:       A3:
; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[A2:%.*]], label [[EXIT:%.*]]
; CHECK:       A2:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[GUARD_H1:%.*]] = phi i1 [ true, [[A2]] ], [ true, [[L1]] ], [ [[PRED0_INV]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    br i1 [[GUARD_H1]], label [[H1:%.*]], label [[A2]]
;
entry:
  br i1 %Pred0, label %A2, label %H1

H1:
  br label %L1

L1:
  br i1 %Pred1, label %H1, label %A3

A3:
  br i1 %Pred2, label %A2, label %exit

A2:
  br label %H1

exit:
  ret void
}

define void @loop_irr_loop_shared_header(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3) {
; CHECK-LABEL: @loop_irr_loop_shared_header(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true
; CHECK-NEXT:    br label [[H2:%.*]]
; CHECK:       H2:
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       H1:
; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[A3:%.*]], label [[IRR_GUARD]]
; CHECK:       A3:
; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[A2:%.*]], label [[L2:%.*]]
; CHECK:       A2:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       L2:
; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[H2]], label [[EXIT:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[GUARD_H1:%.*]] = phi i1 [ true, [[A2]] ], [ true, [[H1:%.*]] ], [ [[PRED0_INV]], [[H2]] ]
; CHECK-NEXT:    br i1 [[GUARD_H1]], label [[H1]], label [[A2]]
;
entry:
  br label %H2

H2:
  br i1 %Pred0, label %A2, label %H1

H1:
  br i1 %Pred1, label %A3, label %H1

A3:
  br i1 %Pred2, label %A2, label %L2

A2:
  br label %H1

L2:
  br i1 %Pred3, label %H2, label %exit

exit:
  ret void
}

define void @siblings_top_level(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6) {
; CHECK-LABEL: @siblings_top_level(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PRED4_INV:%.*]] = xor i1 [[PRED4:%.*]], true
; CHECK-NEXT:    [[PRED1_INV:%.*]] = xor i1 [[PRED1:%.*]], true
; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]]
; CHECK:       H1:
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       A1:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       A2:
; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[A1:%.*]], label [[L1:%.*]]
; CHECK:       L1:
; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[H1]], label [[EXIT:%.*]]
; CHECK:       fork1:
; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
; CHECK:       B1:
; CHECK-NEXT:    br label [[H2:%.*]]
; CHECK:       H2:
; CHECK-NEXT:    br label [[L2:%.*]]
; CHECK:       L2:
; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD1]]
; CHECK:       B2:
; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[B1:%.*]], label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[GUARD_A2:%.*]] = phi i1 [ true, [[A1]] ], [ [[PRED1_INV]], [[H1]] ]
; CHECK-NEXT:    br i1 [[GUARD_A2]], label [[A2:%.*]], label [[A1]]
; CHECK:       irr.guard1:
; CHECK-NEXT:    [[GUARD_B2:%.*]] = phi i1 [ true, [[L2]] ], [ [[PRED4_INV]], [[FORK1]] ]
; CHECK-NEXT:    br i1 [[GUARD_B2]], label [[B2:%.*]], label [[B1]]
;
entry:
  br i1 %Pred0, label %H1, label %fork1

H1:
  br i1 %Pred1, label %A1, label %A2

A1:
  br label %A2

A2:
  br i1 %Pred2, label %A1, label %L1

L1:
  br i1 %Pred3, label %H1, label %exit

fork1:
  br i1 %Pred4, label %B1, label %B2

B1:
  br label %H2

H2:
  br label %L2

L2:
  br i1 %Pred5, label %H2, label %B2

B2:
  br i1 %Pred6, label %B1, label %exit

exit:
  ret void
}

define void @siblings_in_loop(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6, i1 %Pred7) {
; CHECK-LABEL: @siblings_in_loop(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PRED4_INV:%.*]] = xor i1 [[PRED4:%.*]], true
; CHECK-NEXT:    [[PRED1_INV:%.*]] = xor i1 [[PRED1:%.*]], true
; CHECK-NEXT:    br label [[H0:%.*]]
; CHECK:       H0:
; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]]
; CHECK:       H1:
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       A1:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       A2:
; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[A1:%.*]], label [[L1:%.*]]
; CHECK:       L1:
; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[H1]], label [[L0:%.*]]
; CHECK:       fork1:
; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
; CHECK:       B1:
; CHECK-NEXT:    br label [[H2:%.*]]
; CHECK:       H2:
; CHECK-NEXT:    br label [[L2:%.*]]
; CHECK:       L2:
; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD1]]
; CHECK:       B2:
; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[B1:%.*]], label [[L0]]
; CHECK:       L0:
; CHECK-NEXT:    br i1 [[PRED7:%.*]], label [[EXIT:%.*]], label [[H0]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[GUARD_A2:%.*]] = phi i1 [ true, [[A1]] ], [ [[PRED1_INV]], [[H1]] ]
; CHECK-NEXT:    br i1 [[GUARD_A2]], label [[A2:%.*]], label [[A1]]
; CHECK:       irr.guard1:
; CHECK-NEXT:    [[GUARD_B2:%.*]] = phi i1 [ true, [[L2]] ], [ [[PRED4_INV]], [[FORK1]] ]
; CHECK-NEXT:    br i1 [[GUARD_B2]], label [[B2:%.*]], label [[B1]]
;
entry:
  br label %H0

H0:
  br i1 %Pred0, label %H1, label %fork1

H1:
  br i1 %Pred1, label %A1, label %A2

A1:
  br label %A2

A2:
  br i1 %Pred2, label %A1, label %L1

L1:
  br i1 %Pred3, label %H1, label %L0

fork1:
  br i1 %Pred4, label %B1, label %B2

B1:
  br label %H2

H2:
  br label %L2

L2:
  br i1 %Pred5, label %H2, label %B2

B2:
  br i1 %Pred6, label %B1, label %L0

L0:
  br i1 %Pred7, label %exit, label %H0

exit:
  ret void
}

define void @irr_in_irr_shared_entry(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6, i1 %Pred7, i1 %Pred8, i1 %Pred9, i1 %Pred10, i1 %Pred11, i1 %Pred12, i1 %Pred13) {
; CHECK-LABEL: @irr_in_irr_shared_entry(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
; CHECK:       if.end:
; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[IF_THEN7:%.*]], label [[IF_ELSE:%.*]]
; CHECK:       if.then7:
; CHECK-NEXT:    br label [[IF_END16:%.*]]
; CHECK:       if.else:
; CHECK-NEXT:    br label [[IF_END16]]
; CHECK:       if.end16:
; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[WHILE_COND_PREHEADER:%.*]], label [[IF_THEN39:%.*]]
; CHECK:       while.cond.preheader:
; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
; CHECK:       while.cond:
; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[IRR_GUARD:%.*]], label [[LOR_RHS:%.*]]
; CHECK:       cond.true49:
; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IF_THEN69:%.*]], label [[IRR_GUARD1:%.*]]
; CHECK:       while.body63:
; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[EXIT:%.*]], label [[WHILE_COND47:%.*]]
; CHECK:       while.cond47:
; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[COND_TRUE49:%.*]], label [[IRR_GUARD]]
; CHECK:       cond.end61:
; CHECK-NEXT:    br i1 [[PRED7:%.*]], label [[IRR_GUARD1]], label [[WHILE_COND]]
; CHECK:       if.then69:
; CHECK-NEXT:    br i1 [[PRED8:%.*]], label [[EXIT]], label [[WHILE_COND]]
; CHECK:       lor.rhs:
; CHECK-NEXT:    br i1 [[PRED9:%.*]], label [[IRR_GUARD]], label [[WHILE_END76:%.*]]
; CHECK:       while.end76:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       if.then39:
; CHECK-NEXT:    br i1 [[PRED10:%.*]], label [[EXIT]], label [[IF_END_I145:%.*]]
; CHECK:       if.end.i145:
; CHECK-NEXT:    br i1 [[PRED11:%.*]], label [[EXIT]], label [[IF_END8_I149:%.*]]
; CHECK:       if.end8.i149:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       if.then:
; CHECK-NEXT:    br i1 [[PRED12:%.*]], label [[EXIT]], label [[IF_END_I:%.*]]
; CHECK:       if.end.i:
; CHECK-NEXT:    br i1 [[PRED13:%.*]], label [[EXIT]], label [[IF_END8_I:%.*]]
; CHECK:       if.end8.i:
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[GUARD_COND_END61:%.*]] = phi i1 [ true, [[WHILE_COND47]] ], [ true, [[LOR_RHS]] ], [ false, [[WHILE_COND]] ]
; CHECK-NEXT:    br i1 [[GUARD_COND_END61]], label [[COND_END61:%.*]], label [[IRR_GUARD1]]
; CHECK:       irr.guard1:
; CHECK-NEXT:    [[GUARD_WHILE_BODY63:%.*]] = phi i1 [ true, [[COND_TRUE49]] ], [ true, [[COND_END61]] ], [ false, [[IRR_GUARD]] ]
; CHECK-NEXT:    br i1 [[GUARD_WHILE_BODY63]], label [[WHILE_BODY63:%.*]], label [[COND_TRUE49]]
;
entry:
  br i1 %Pred0, label %if.end, label %if.then

if.end:
  br i1 %Pred1, label %if.then7, label %if.else

if.then7:
  br label %if.end16

if.else:
  br label %if.end16

if.end16:
  br i1 %Pred2, label %while.cond.preheader, label %if.then39

while.cond.preheader:
  br label %while.cond

while.cond:
  br i1 %Pred3, label %cond.true49, label %lor.rhs

cond.true49:
  br i1 %Pred4, label %if.then69, label %while.body63

while.body63:
  br i1 %Pred5, label %exit, label %while.cond47

while.cond47:
  br i1 %Pred6, label %cond.true49, label %cond.end61

cond.end61:
  br i1 %Pred7, label %while.body63, label %while.cond

if.then69:
  br i1 %Pred8, label %exit, label %while.cond

lor.rhs:
  br i1 %Pred9, label %cond.end61, label %while.end76

while.end76:
  br label %exit

if.then39:
  br i1 %Pred10, label %exit, label %if.end.i145

if.end.i145:
  br i1 %Pred11, label %exit, label %if.end8.i149

if.end8.i149:
  br label %exit

if.then:
  br i1 %Pred12, label %exit, label %if.end.i

if.end.i:
  br i1 %Pred13, label %exit, label %if.end8.i

if.end8.i:
  br label %exit

exit:
  ret void
}