blob: fe34ac9b93bc786c65b60fb95c50d9fc6921e9d2 [file] [log] [blame]
; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -fix-irreducible -S | FileCheck %s -check-prefix=CHECK
; RUN: opt < %s -passes=fix-irreducible -S | FileCheck %s -check-prefix=CHECK
define i32 @basic(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) {
; CHECK-LABEL: @basic(
; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[IRR_GUARD:%.*]]
; CHECK: left:
; CHECK-NEXT: [[L:%.*]] = add i32 [[L_PHI_MOVED:%.*]], 1
; CHECK-NEXT: br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
; CHECK: right:
; CHECK-NEXT: br i1 [[PREDRIGHT:%.*]], label [[IRR_GUARD]], 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: [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[LEFT]] ]
; CHECK-NEXT: [[L_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ]
; CHECK-NEXT: [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[L]], [[LEFT]] ]
; CHECK-NEXT: br i1 [[GUARD_LEFT]], label [[LEFT]], label [[RIGHT]]
;
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: br label [[IRR_GUARD:%.*]]
; CHECK: left:
; CHECK-NEXT: br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
; CHECK: right:
; CHECK-NEXT: br i1 [[PREDRIGHT:%.*]], label [[IRR_GUARD]], label [[EXIT]]
; CHECK: exit:
; CHECK-NEXT: [[Z:%.*]] = phi i32 [ [[L_PHI_MOVED:%.*]], [[LEFT:%.*]] ], [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ]
; CHECK-NEXT: ret i32 [[Z]]
; CHECK: irr.guard:
; CHECK-NEXT: [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[LEFT]] ]
; CHECK-NEXT: [[L_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ]
; CHECK-NEXT: [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ]
; CHECK-NEXT: br i1 [[GUARD_LEFT]], label [[LEFT]], label [[RIGHT]]
;
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 [[IRR_GUARD]], label [[EXIT:%.*]]
; CHECK: D:
; CHECK-NEXT: [[D_INC:%.*]] = add i32 [[D_PHI_MOVED:%.*]], 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: [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ [[PREDB_INV]], [[B]] ], [ [[PREDA:%.*]], [[A]] ], [ false, [[C]] ]
; CHECK-NEXT: [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[Y:%.*]], [[B]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ]
; CHECK-NEXT: [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ [[Y]], [[B]] ], [ [[A_INC]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ]
; 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: 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 [[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: [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ true, [[A]] ], [ false, [[C]] ], [ false, [[B]] ]
; CHECK-NEXT: [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ], [ undef, [[B]] ]
; CHECK-NEXT: [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ undef, [[A]] ], [ [[C_PHI_MOVED]], [[C]] ], [ [[Y:%.*]], [[B]] ]
; 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 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: 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 [[IRR_GUARD]]
; CHECK: B:
; CHECK-NEXT: br label [[IRR_GUARD]]
; CHECK: C:
; CHECK-NEXT: br label [[IRR_GUARD]]
; CHECK: D:
; CHECK-NEXT: br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]]
; CHECK: exit:
; CHECK-NEXT: ret void
; CHECK: irr.guard:
; CHECK-NEXT: [[GUARD_A:%.*]] = phi i1 [ true, [[D:%.*]] ], [ [[PREDX:%.*]], [[X]] ], [ false, [[A:%.*]] ], [ false, [[B:%.*]] ], [ false, [[Y]] ], [ false, [[C:%.*]] ]
; CHECK-NEXT: [[GUARD_B:%.*]] = phi i1 [ false, [[D]] ], [ true, [[X]] ], [ true, [[A]] ], [ false, [[B]] ], [ false, [[Y]] ], [ false, [[C]] ]
; CHECK-NEXT: [[GUARD_C:%.*]] = phi i1 [ false, [[D]] ], [ false, [[X]] ], [ false, [[A]] ], [ true, [[B]] ], [ [[PREDY:%.*]], [[Y]] ], [ false, [[C]] ]
; CHECK-NEXT: br i1 [[GUARD_A]], label [[A]], label [[IRR_GUARD1:%.*]]
; CHECK: irr.guard1:
; CHECK-NEXT: br i1 [[GUARD_B]], label [[B]], label [[IRR_GUARD2:%.*]]
; CHECK: irr.guard2:
; CHECK-NEXT: br i1 [[GUARD_C]], label [[C]], label [[D]]
;
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: br label [[IRR_GUARD:%.*]]
; CHECK: A:
; CHECK-NEXT: [[A_INC:%.*]] = add i32 [[A_PHI_MOVED:%.*]], 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 [[IRR_GUARD]]
; CHECK: exit:
; CHECK-NEXT: ret i32 [[B_PHI_MOVED]]
; CHECK: irr.guard:
; CHECK-NEXT: [[GUARD_A:%.*]] = phi i1 [ true, [[E]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[A:%.*]] ]
; CHECK-NEXT: [[A_PHI_MOVED]] = phi i32 [ [[C_INC]], [[E]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[A_PHI_MOVED]], [[A]] ]
; CHECK-NEXT: [[B_PHI_MOVED]] = phi i32 [ undef, [[E]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[A_INC]], [[A]] ]
; CHECK-NEXT: br i1 [[GUARD_A]], label [[A]], label [[B:%.*]]
;
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
}