; 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 i32 @basic(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) {
; CHECK-LABEL: @basic(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       left:
; CHECK-NEXT:    [[L_PHI:%.*]] = phi i32 [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ], [ [[L_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
; CHECK-NEXT:    [[L:%.*]] = add i32 [[L_PHI]], 1
; CHECK-NEXT:    br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
; CHECK:       right:
; CHECK-NEXT:    br i1 [[PREDRIGHT:%.*]], label [[LEFT:%.*]], label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    [[Z:%.*]] = phi i32 [ [[L]], [[LEFT]] ], [ [[R_PHI_MOVED]], [[RIGHT]] ]
; CHECK-NEXT:    ret i32 [[Z]]
; CHECK:       irr.guard:
; CHECK-NEXT:    [[L_PHI_MOVED]] = phi i32 [ poison, [[LEFT]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[L]], [[LEFT]] ], [ [[Y:%.*]], [[ENTRY]] ]
; CHECK-NEXT:    [[GUARD_RIGHT:%.*]] = phi i1 [ true, [[LEFT]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ]
; CHECK-NEXT:    br i1 [[GUARD_RIGHT]], label [[RIGHT]], label [[LEFT]]
;
entry:
  br i1 %PredEntry, label %left, label %right

left:
  %L.phi = phi i32 [%X, %entry], [%R.phi, %right]
  %L = add i32 %L.phi, 1
  br i1 %PredLeft, label %right, label %exit

right:
  %R.phi = phi i32 [%Y, %entry], [%L, %left]
  br i1 %PredRight, label %left, label %exit

exit:
  %Z = phi i32 [%L, %left], [%R.phi, %right]
  ret i32 %Z
}

define i32 @feedback_loop(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) {
; CHECK-LABEL: @feedback_loop(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       left:
; CHECK-NEXT:    [[L_PHI:%.*]] = phi i32 [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ], [ [[L_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
; CHECK-NEXT:    br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
; CHECK:       right:
; CHECK-NEXT:    br i1 [[PREDRIGHT:%.*]], label [[LEFT:%.*]], label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    [[Z:%.*]] = phi i32 [ [[L_PHI]], [[LEFT]] ], [ [[R_PHI_MOVED]], [[RIGHT]] ]
; CHECK-NEXT:    ret i32 [[Z]]
; CHECK:       irr.guard:
; CHECK-NEXT:    [[L_PHI_MOVED]] = phi i32 [ poison, [[LEFT]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[L_PHI]], [[LEFT]] ], [ [[Y:%.*]], [[ENTRY]] ]
; CHECK-NEXT:    [[GUARD_RIGHT:%.*]] = phi i1 [ true, [[LEFT]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ]
; CHECK-NEXT:    br i1 [[GUARD_RIGHT]], label [[RIGHT]], label [[LEFT]]
;
entry:
  br i1 %PredEntry, label %left, label %right

left:
  %L.phi = phi i32 [%X, %entry], [%R.phi, %right]
  br i1 %PredLeft, label %right, label %exit

right:
  %R.phi = phi i32 [%Y, %entry], [%L.phi, %left]
  br i1 %PredRight, label %left, label %exit

exit:
  %Z = phi i32 [%L.phi, %left], [%R.phi, %right]
  ret i32 %Z
}

define i32 @multiple_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
; CHECK-LABEL: @multiple_predecessors(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PREDB_INV:%.*]] = xor i1 [[PREDB:%.*]], true
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[X:%.*]], 1
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       B:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       C:
; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[D:%.*]], label [[EXIT:%.*]]
; CHECK:       D:
; CHECK-NEXT:    [[D_PHI:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
; CHECK-NEXT:    [[D_INC:%.*]] = add i32 [[D_PHI]], 1
; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT]], label [[IRR_GUARD]]
; CHECK:       exit:
; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED]], [[C]] ], [ [[D_INC]], [[D]] ]
; CHECK-NEXT:    ret i32 [[RET]]
; CHECK:       irr.guard:
; CHECK-NEXT:    [[D_PHI_MOVED]] = phi i32 [ poison, [[D]] ], [ [[Y:%.*]], [[B]] ], [ [[A_INC]], [[A]] ]
; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[Y]], [[B]] ], [ [[X]], [[A]] ]
; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ [[PREDB_INV]], [[B]] ], [ [[PREDA:%.*]], [[A]] ]
; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[D]]
;
entry:
  br i1 %PredEntry, label %A, label %B

A:
  %A.inc = add i32 %X, 1
  br i1 %PredA, label %C, label %D

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

C:
  %C.phi = phi i32 [%X, %A], [%Y, %B], [%D.inc, %D]
  br i1 %PredC, label %D, label %exit

D:
  %D.phi = phi i32 [%A.inc, %A], [%Y, %B], [%C.phi, %C]
  %D.inc = add i32 %D.phi, 1
  br i1 %PredD, label %exit, label %C

exit:
  %ret = phi i32 [%C.phi, %C], [%D.inc, %D]
  ret i32 %ret
}

define i32 @separate_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
; CHECK-LABEL: @separate_predecessors(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[X:%.*]], 1
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       B:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       C:
; CHECK-NEXT:    [[C_PHI:%.*]] = phi i32 [ [[D_INC:%.*]], [[D:%.*]] ], [ [[C_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]]
; CHECK:       D:
; CHECK-NEXT:    [[D_INC]] = add i32 [[D_PHI_MOVED:%.*]], 1
; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT]], label [[C:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[C_PHI]], [[C]] ], [ [[D_INC]], [[D]] ]
; CHECK-NEXT:    ret i32 [[RET]]
; CHECK:       irr.guard:
; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ poison, [[C]] ], [ poison, [[B]] ], [ [[X]], [[A]] ]
; CHECK-NEXT:    [[D_PHI_MOVED]] = phi i32 [ [[C_PHI]], [[C]] ], [ [[Y:%.*]], [[B]] ], [ poison, [[A]] ]
; CHECK-NEXT:    [[GUARD_D:%.*]] = phi i1 [ true, [[C]] ], [ true, [[B]] ], [ false, [[A]] ]
; CHECK-NEXT:    br i1 [[GUARD_D]], label [[D]], label [[C]]
;
entry:
  br i1 %PredEntry, label %A, label %B

A:
  %A.inc = add i32 %X, 1
  br label %C

B:
  br label %D

C:
  %C.phi = phi i32 [%X, %A], [%D.inc, %D]
  br i1 %PredC, label %exit, label %D

D:
  %D.phi = phi i32 [%Y, %B], [%C.phi, %C]
  %D.inc = add i32 %D.phi, 1
  br i1 %PredD, label %exit, label %C

exit:
  %ret = phi i32 [%C.phi, %C], [%D.inc, %D]
  ret i32 %ret
}

define void @four_headers(i1 %PredEntry, i1 %PredX, i1  %PredY, i1 %PredD) {
; CHECK-LABEL: @four_headers(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PREDY_INV:%.*]] = xor i1 [[PREDY:%.*]], true
; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[X:%.*]], label [[Y:%.*]]
; CHECK:       X:
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       Y:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       A:
; CHECK-NEXT:    br label [[B:%.*]]
; CHECK:       B:
; CHECK-NEXT:    br label [[C:%.*]]
; CHECK:       C:
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       D:
; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[A:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[GUARD_D:%.*]] = phi i1 [ true, [[C]] ], [ [[PREDY_INV]], [[Y]] ], [ false, [[X]] ]
; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ false, [[C]] ], [ true, [[Y]] ], [ false, [[X]] ]
; CHECK-NEXT:    [[GUARD_A:%.*]] = phi i1 [ false, [[C]] ], [ false, [[Y]] ], [ [[PREDX:%.*]], [[X]] ]
; CHECK-NEXT:    br i1 [[GUARD_D]], label [[D:%.*]], label [[IRR_GUARD1:%.*]]
; CHECK:       irr.guard1:
; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[IRR_GUARD2:%.*]]
; CHECK:       irr.guard2:
; CHECK-NEXT:    br i1 [[GUARD_A]], label [[A]], label [[B]]
;
entry:
  br i1 %PredEntry, label %X, label %Y

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

Y:
  br i1 %PredY, label %C, label %D

A:
  br label %B

B:
  br label %C

C:
  br label %D

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

exit:
  ret void
}

define i32 @hidden_nodes(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
; CHECK-LABEL: @hidden_nodes(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[PREDENTRY_INV:%.*]] = xor i1 [[PREDENTRY:%.*]], true
; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
; CHECK:       A:
; CHECK-NEXT:    [[A_PHI:%.*]] = phi i32 [ [[C_INC:%.*]], [[E:%.*]] ], [ [[A_PHI_MOVED:%.*]], [[IRR_GUARD]] ]
; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[A_PHI]], 1
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       B:
; CHECK-NEXT:    br label [[C:%.*]]
; CHECK:       C:
; CHECK-NEXT:    [[C_INC]] = add i32 [[B_PHI_MOVED:%.*]], 1
; CHECK-NEXT:    br label [[D:%.*]]
; CHECK:       D:
; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[E]]
; CHECK:       E:
; CHECK-NEXT:    br label [[A:%.*]]
; CHECK:       exit:
; CHECK-NEXT:    ret i32 [[B_PHI_MOVED]]
; CHECK:       irr.guard:
; CHECK-NEXT:    [[A_PHI_MOVED]] = phi i32 [ poison, [[A]] ], [ [[X:%.*]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    [[B_PHI_MOVED]] = phi i32 [ [[A_INC]], [[A]] ], [ [[Y:%.*]], [[ENTRY]] ]
; CHECK-NEXT:    [[GUARD_B:%.*]] = phi i1 [ true, [[A]] ], [ [[PREDENTRY_INV]], [[ENTRY]] ]
; CHECK-NEXT:    br i1 [[GUARD_B]], label [[B:%.*]], label [[A]]
;
entry:
  br i1 %PredEntry, label %A, label %B

A:
  %A.phi = phi i32 [%X, %entry], [%C.inc, %E]
  %A.inc = add i32 %A.phi, 1
  br label %B

B:
  %B.phi = phi i32 [%A.inc, %A], [%Y, %entry]
  br label %C

C:
  %C.inc = add i32 %B.phi, 1
  br label %D

D:
  br i1 %PredD, label %exit, label %E

E:
  br label %A

exit:
  ret i32 %B.phi
}


define void @recursive_phis(i1 %cond, ptr addrspace(5) %ptr) {
; CHECK-LABEL: @recursive_phis(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[ALLOCA:%.*]] = alloca i8, align 1, addrspace(5)
; CHECK-NEXT:    br i1 [[COND:%.*]], label [[THEN:%.*]], label [[IRR_GUARD:%.*]]
; CHECK:       then:
; CHECK-NEXT:    [[PTR_INT:%.*]] = ptrtoint ptr addrspace(5) [[PTR:%.*]] to i32
; CHECK-NEXT:    [[PTR_OR:%.*]] = and i32 [[PTR_INT]], 65535
; CHECK-NEXT:    [[KB_PTR:%.*]] = inttoptr i32 [[PTR_OR]] to ptr addrspace(5)
; CHECK-NEXT:    br label [[IRR_GUARD]]
; CHECK:       else:
; CHECK-NEXT:    br i1 [[COND]], label [[IRR_GUARD]], label [[BB:%.*]]
; CHECK:       BB:
; CHECK-NEXT:    br label [[FINALLY:%.*]]
; CHECK:       finally:
; CHECK-NEXT:    [[PHI_PTR:%.*]] = phi ptr addrspace(5) [ [[OTHER_PHI_MOVED:%.*]], [[BB]] ], [ [[PHI_PTR_MOVED:%.*]], [[IRR_GUARD]] ]
; CHECK-NEXT:    [[X:%.*]] = addrspacecast ptr addrspace(5) [[PHI_PTR]] to ptr
; CHECK-NEXT:    store volatile i32 7, ptr [[X]], align 4
; CHECK-NEXT:    br i1 [[COND]], label [[IRR_GUARD]], label [[END:%.*]]
; CHECK:       end:
; CHECK-NEXT:    ret void
; CHECK:       irr.guard:
; CHECK-NEXT:    [[PHI_PTR_MOVED]] = phi ptr addrspace(5) [ poison, [[FINALLY]] ], [ poison, [[ELSE:%.*]] ], [ poison, [[ENTRY:%.*]] ], [ [[KB_PTR]], [[THEN]] ]
; CHECK-NEXT:    [[OTHER_PHI_MOVED]] = phi ptr addrspace(5) [ [[PHI_PTR]], [[FINALLY]] ], [ [[OTHER_PHI_MOVED]], [[ELSE]] ], [ [[ALLOCA]], [[ENTRY]] ], [ poison, [[THEN]] ]
; CHECK-NEXT:    [[GUARD_ELSE:%.*]] = phi i1 [ true, [[FINALLY]] ], [ true, [[ELSE]] ], [ true, [[ENTRY]] ], [ false, [[THEN]] ]
; CHECK-NEXT:    br i1 [[GUARD_ELSE]], label [[ELSE]], label [[FINALLY]]
;

entry:
  %alloca = alloca i8, align 1, addrspace(5)
  br i1 %cond, label %then, label %else

then:                                             ; preds = %entry
  %ptr.int = ptrtoint ptr addrspace(5) %ptr to i32
  %ptr.or = and i32 %ptr.int, 65535
  %kb.ptr = inttoptr i32 %ptr.or to ptr addrspace(5)
  br label %finally

else:                                             ; preds = %finally, %else, %entry
  %other.phi = phi ptr addrspace(5) [ %alloca, %entry ], [ %phi.ptr, %finally ], [ undef, %else ]
  br i1 %cond, label %else, label %BB

BB:                                               ; preds = %else
  br label %finally

finally:                                          ; preds = %BB, %then
  %phi.ptr = phi ptr addrspace(5) [ %kb.ptr, %then ], [ %other.phi, %BB ]
  %x = addrspacecast ptr addrspace(5) %phi.ptr to ptr
  store volatile i32 7, ptr %x, align 4
  br i1 %cond, label %else, label %end

end:                                              ; preds = %finally
  ret void
}