shylie/llvm-project
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
llvm-project/llvm/test/Transforms/FixIrreducible/nested.ll
Sameer Sahasrabuddhe fa4cc9ddd5
[FixIrreducible] Use CycleInfo instead of a custom SCC traversal (#101386) 
[FixIrreducible] Use CycleInfo instead of a custom SCC traversal

1. CycleInfo efficiently locates all cycles in a single pass, while the
SCC is
   repeated inside every natural loop.

2. CycleInfo provides a hierarchy of irreducible cycles, and the new
implementation transforms each cycle in this hierarchy separately
instead of
reducing an entire irreducible SCC in a single step. This reduces the
number
of control-flow paths that pass through the header of each newly created
loop. This is evidenced by the reduced number of predecessors on the
"guard"
blocks in the lit tests, and fewer operands on the corresponding PHI
nodes.

3. When an entry of an irreducible cycle is the header of a child
natural loop,
the original implementation destroyed that loop. This is now preserved,
   since the incoming edges on non-header entries are not touched.

4. In the new implementation, if an irreducible cycle is a superset of a
natural
loop with the same header, then that natural loop is destroyed and
replaced
   by the newly created loop.
2024-08-26 15:51:34 +05:30

530 lines
15 KiB
LLVM
Raw Permalink Blame History

; 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
}
Reference in New Issue View Git Blame Copy Permalink