1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -unify-loop-exits -structurizecfg -S | FileCheck %s
3
4; The structurizer uses an RPO traversal over a region, along with a
5; manual hack that is meant to sort ensure that blocks within a loop
6; are all visited before visiting blocks outside the loop. But this
7; does not always work as expected. For example the results are
8; incorrect when multiple nested loops are involved.
9
10; The workaround for this is to unify loop exits. Each loop now
11; becomes an SESE region with a single header and a single exit. The
12; structurizer is a region pass, and it no longer sees the entire loop
13; nest in a single region. More importantly, for each loop, the only
14; block reachable outside the loop is the region exit, which avoids
15; any confusion in the hacked RPO traversal.
16
17; In the function below, B1 is an exiting block in outer loop H1. It's
18; successor inside the loop is the header of another loop H2. Due to
19; the incorrect traversal, B1 dominates all the blocks in the
20; structurized program, except the header H1.
21
22define void @exiting-block(i1 %PredH1, i1 %PredB2, i1 %PredB1, i1 %PredH2) {
23; CHECK-LABEL: @exiting-block(
24; CHECK-NEXT:  entry:
25; CHECK-NEXT:    [[PREDH1_INV:%.*]] = xor i1 [[PREDH1:%.*]], true
26; CHECK-NEXT:    [[PREDB2_INV:%.*]] = xor i1 [[PREDB2:%.*]], true
27; CHECK-NEXT:    br label [[H1:%.*]]
28; CHECK:       H1:
29; CHECK-NEXT:    br i1 [[PREDH1_INV]], label [[B1:%.*]], label [[FLOW3:%.*]]
30; CHECK:       Flow3:
31; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ [[PREDB1:%.*]], [[B1]] ], [ [[PREDH1]], [[H1]] ]
32; CHECK-NEXT:    br i1 [[TMP0]], label [[H2:%.*]], label [[FLOW4:%.*]]
33; CHECK:       H2:
34; CHECK-NEXT:    br i1 [[PREDH2:%.*]], label [[B2:%.*]], label [[FLOW:%.*]]
35; CHECK:       B2:
36; CHECK-NEXT:    br i1 [[PREDB2_INV]], label [[L2:%.*]], label [[FLOW2:%.*]]
37; CHECK:       Flow:
38; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ false, [[FLOW2]] ], [ true, [[H2]] ]
39; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[TMP4:%.*]], [[FLOW2]] ], [ true, [[H2]] ]
40; CHECK-NEXT:    br i1 [[TMP2]], label [[LOOP_EXIT_GUARD1:%.*]], label [[H2]]
41; CHECK:       L2:
42; CHECK-NEXT:    br label [[FLOW2]]
43; CHECK:       L1:
44; CHECK-NEXT:    br label [[FLOW5:%.*]]
45; CHECK:       B1:
46; CHECK-NEXT:    br label [[FLOW3]]
47; CHECK:       C:
48; CHECK-NEXT:    br label [[EXIT:%.*]]
49; CHECK:       exit:
50; CHECK-NEXT:    ret void
51; CHECK:       Flow5:
52; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ false, [[L1:%.*]] ], [ true, [[LOOP_EXIT_GUARD1]] ]
53; CHECK-NEXT:    br label [[FLOW4]]
54; CHECK:       loop.exit.guard:
55; CHECK-NEXT:    br i1 [[TMP5:%.*]], label [[C:%.*]], label [[EXIT]]
56; CHECK:       Flow2:
57; CHECK-NEXT:    [[TMP4]] = phi i1 [ false, [[L2]] ], [ true, [[B2]] ]
58; CHECK-NEXT:    br label [[FLOW]]
59; CHECK:       Flow4:
60; CHECK-NEXT:    [[TMP5]] = phi i1 [ false, [[FLOW5]] ], [ true, [[FLOW3]] ]
61; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ [[TMP3]], [[FLOW5]] ], [ true, [[FLOW3]] ]
62; CHECK-NEXT:    br i1 [[TMP6]], label [[LOOP_EXIT_GUARD:%.*]], label [[H1]]
63; CHECK:       loop.exit.guard1:
64; CHECK-NEXT:    br i1 [[TMP1]], label [[L1]], label [[FLOW5]]
65;
66entry:
67  br label %H1
68
69H1:                                               ; preds = %L1, %entry
70  br i1 %PredH1, label %H2, label %B1
71
72H2:                                               ; preds = %B1, %L2, %H1
73  br i1 %PredH2, label %B2, label %L1
74
75B2:                                               ; preds = %H2
76  br i1 %PredB2, label %exit, label %L2
77
78L2:                                               ; preds = %B2
79  br label %H2
80
81L1:                                               ; preds = %H2
82  br label %H1
83
84B1:                                               ; preds = %H1
85  br i1 %PredB1, label %H2, label %C
86
87C:                                                ; preds = %B1
88  br label %exit
89
90exit:                                             ; preds = %C, %B2
91  ret void
92}
93
94; The function below has three nested loops. Due to the incorrect
95; traversal, H2 dominates H3 in the structurized program, and the
96; backedge from L13 to H3 has no equivalent path.
97
98define void @incorrect-backedge(i1 %PredH2, i1 %PredH3, i1 %PredL2, i1 %PredL13, i1 %PredL1)
99; CHECK-LABEL: @incorrect-backedge(
100; CHECK-NEXT:  entry:
101; CHECK-NEXT:    [[PREDH2_INV:%.*]] = xor i1 [[PREDH2:%.*]], true
102; CHECK-NEXT:    [[PREDL2_INV:%.*]] = xor i1 [[PREDL2:%.*]], true
103; CHECK-NEXT:    [[PREDH3_INV:%.*]] = xor i1 [[PREDH3:%.*]], true
104; CHECK-NEXT:    [[PREDL13_INV:%.*]] = xor i1 [[PREDL13:%.*]], true
105; CHECK-NEXT:    br label [[H1:%.*]]
106; CHECK:       H1:
107; CHECK-NEXT:    br label [[H2:%.*]]
108; CHECK:       H2:
109; CHECK-NEXT:    br i1 [[PREDH2_INV]], label [[H3:%.*]], label [[FLOW4:%.*]]
110; CHECK:       H3:
111; CHECK-NEXT:    br i1 [[PREDH3_INV]], label [[L2:%.*]], label [[FLOW:%.*]]
112; CHECK:       L2:
113; CHECK-NEXT:    br i1 [[PREDL2_INV]], label [[L13:%.*]], label [[FLOW3:%.*]]
114; CHECK:       Flow:
115; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ false, [[FLOW3]] ], [ true, [[H3]] ]
116; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[TMP6:%.*]], [[FLOW3]] ], [ true, [[H3]] ]
117; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[TMP7:%.*]], [[FLOW3]] ], [ true, [[H3]] ]
118; CHECK-NEXT:    br i1 [[TMP2]], label [[LOOP_EXIT_GUARD2:%.*]], label [[H3]]
119; CHECK:       L13:
120; CHECK-NEXT:    br label [[FLOW3]]
121; CHECK:       Flow5:
122; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ [[TMP8:%.*]], [[LOOP_EXIT_GUARD1:%.*]] ], [ true, [[LOOP_EXIT_GUARD:%.*]] ]
123; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ false, [[LOOP_EXIT_GUARD1]] ], [ true, [[LOOP_EXIT_GUARD]] ]
124; CHECK-NEXT:    br i1 [[TMP4]], label [[L1:%.*]], label [[FLOW6:%.*]]
125; CHECK:       L1:
126; CHECK-NEXT:    br label [[FLOW6]]
127; CHECK:       Flow6:
128; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ [[PREDL1:%.*]], [[L1]] ], [ [[TMP3]], [[FLOW5:%.*]] ]
129; CHECK-NEXT:    br i1 [[TMP5]], label [[EXIT:%.*]], label [[H1]]
130; CHECK:       exit:
131; CHECK-NEXT:    ret void
132; CHECK:       loop.exit.guard:
133; CHECK-NEXT:    br i1 [[TMP11:%.*]], label [[LOOP_EXIT_GUARD1]], label [[FLOW5]]
134; CHECK:       loop.exit.guard1:
135; CHECK-NEXT:    br label [[FLOW5]]
136; CHECK:       Flow3:
137; CHECK-NEXT:    [[TMP6]] = phi i1 [ true, [[L13]] ], [ false, [[L2]] ]
138; CHECK-NEXT:    [[TMP7]] = phi i1 [ [[PREDL13_INV]], [[L13]] ], [ true, [[L2]] ]
139; CHECK-NEXT:    br label [[FLOW]]
140; CHECK:       Flow4:
141; CHECK-NEXT:    [[TMP8]] = phi i1 [ [[TMP0]], [[LOOP_EXIT_GUARD2]] ], [ false, [[H2]] ]
142; CHECK-NEXT:    [[TMP9:%.*]] = phi i1 [ false, [[LOOP_EXIT_GUARD2]] ], [ true, [[H2]] ]
143; CHECK-NEXT:    [[TMP10:%.*]] = phi i1 [ [[TMP1]], [[LOOP_EXIT_GUARD2]] ], [ true, [[H2]] ]
144; CHECK-NEXT:    [[TMP11]] = xor i1 [[TMP9]], true
145; CHECK-NEXT:    br i1 [[TMP10]], label [[LOOP_EXIT_GUARD]], label [[H2]]
146; CHECK:       loop.exit.guard2:
147; CHECK-NEXT:    br label [[FLOW4]]
148;
149{
150entry:
151  br label %H1
152
153H1:
154  br label %H2
155
156H2:
157  br i1 %PredH2, label %L1, label %H3
158
159H3:
160  br i1 %PredH3, label %exit, label %L2
161
162L2:
163  br i1 %PredL2, label %H2, label %L13
164
165L13:
166  br i1 %PredL13, label %H3, label %H1
167
168L1:
169  br i1 %PredL1, label %exit, label %H1
170
171exit:
172  ret void
173}
174