270 lines
9.4 KiB
LLVM
270 lines
9.4 KiB
LLVM
|
; 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
|
||
|
|
}
|