| ; 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 |
| } |