1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -fix-irreducible -S | FileCheck %s -check-prefix=CHECK
3
4define void @nested_irr_top_level(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5) {
5; CHECK-LABEL: @nested_irr_top_level(
6; CHECK-NEXT:  entry:
7; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
8; CHECK:       A1:
9; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
10; CHECK:       B1:
11; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[A3:%.*]]
12; CHECK:       B2:
13; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[IRR_GUARD1]], label [[A3]]
14; CHECK:       A3:
15; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
16; CHECK:       A2:
17; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[IRR_GUARD]], label [[EXIT]]
18; CHECK:       exit:
19; CHECK-NEXT:    ret void
20; CHECK:       irr.guard:
21; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ]
22; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]]
23; CHECK:       irr.guard1:
24; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED1:%.*]], [[A1]] ], [ false, [[B1:%.*]] ]
25; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1]], label [[B2]]
26;
27entry:
28  br i1 %Pred0, label %A1, label %A2
29
30A1:
31  br i1 %Pred1, label %B1, label %B2
32
33B1:
34  br i1 %Pred2, label %B2, label %A3
35
36B2:
37  br i1 %Pred3, label %B1, label %A3
38
39A3:
40  br i1 %Pred4, label %A2, label %exit
41
42A2:
43  br i1 %Pred5, label %A1, label %exit
44
45exit:
46  ret void
47}
48
49define void @nested_irr_in_loop(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6) {
50; CHECK-LABEL: @nested_irr_in_loop(
51; CHECK-NEXT:  entry:
52; CHECK-NEXT:    br label [[H1:%.*]]
53; CHECK:       H1:
54; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
55; CHECK:       A1:
56; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
57; CHECK:       B1:
58; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[A3:%.*]]
59; CHECK:       B2:
60; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[IRR_GUARD1]], label [[A3]]
61; CHECK:       A3:
62; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[L1:%.*]]
63; CHECK:       A2:
64; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[IRR_GUARD]], label [[L1]]
65; CHECK:       L1:
66; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[EXIT:%.*]], label [[H1]]
67; CHECK:       exit:
68; CHECK-NEXT:    ret void
69; CHECK:       irr.guard:
70; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[H1]] ], [ false, [[A3]] ]
71; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]]
72; CHECK:       irr.guard1:
73; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED1:%.*]], [[A1]] ], [ false, [[B1:%.*]] ]
74; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1]], label [[B2]]
75;
76entry:
77  br label %H1
78
79H1:
80  br i1 %Pred0, label %A1, label %A2
81
82A1:
83  br i1 %Pred1, label %B1, label %B2
84
85B1:
86  br i1 %Pred2, label %B2, label %A3
87
88B2:
89  br i1 %Pred3, label %B1, label %A3
90
91A3:
92  br i1 %Pred4, label %A2, label %L1
93
94A2:
95  br i1 %Pred5, label %A1, label %L1
96
97L1:
98  br i1 %Pred6, label %exit, label %H1
99
100exit:
101  ret void
102}
103
104define void @loop_in_irr(i1 %Pred0, i1 %Pred1, i1 %Pred2) {
105; CHECK-LABEL: @loop_in_irr(
106; CHECK-NEXT:  entry:
107; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
108; CHECK:       A1:
109; CHECK-NEXT:    br label [[H1:%.*]]
110; CHECK:       H1:
111; CHECK-NEXT:    br label [[L1:%.*]]
112; CHECK:       L1:
113; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[H1]], label [[A3:%.*]]
114; CHECK:       A3:
115; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
116; CHECK:       A2:
117; CHECK-NEXT:    br label [[IRR_GUARD]]
118; CHECK:       exit:
119; CHECK-NEXT:    ret void
120; CHECK:       irr.guard:
121; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ]
122; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]]
123;
124entry:
125  br i1 %Pred0, label %A1, label %A2
126
127A1:
128  br label %H1
129
130H1:
131  br label %L1
132
133L1:
134  br i1 %Pred1, label %H1, label %A3
135
136A3:
137  br i1 %Pred2, label %A2, label %exit
138
139A2:
140  br label %A1
141
142exit:
143  ret void
144}
145
146define void @loop_in_irr_shared_header(i1 %Pred0, i1 %Pred1, i1 %Pred2) {
147; CHECK-LABEL: @loop_in_irr_shared_header(
148; CHECK-NEXT:  entry:
149; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
150; CHECK:       H1:
151; CHECK-NEXT:    br label [[L1:%.*]]
152; CHECK:       L1:
153; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[IRR_GUARD]], label [[A3:%.*]]
154; CHECK:       A3:
155; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
156; CHECK:       A2:
157; CHECK-NEXT:    br label [[IRR_GUARD]]
158; CHECK:       exit:
159; CHECK-NEXT:    ret void
160; CHECK:       irr.guard:
161; CHECK-NEXT:    [[GUARD_H1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ true, [[L1]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ]
162; CHECK-NEXT:    br i1 [[GUARD_H1]], label [[H1:%.*]], label [[A2]]
163;
164entry:
165  br i1 %Pred0, label %H1, label %A2
166
167H1:
168  br label %L1
169
170L1:
171  br i1 %Pred1, label %H1, label %A3
172
173A3:
174  br i1 %Pred2, label %A2, label %exit
175
176A2:
177  br label %H1
178
179exit:
180  ret void
181}
182
183define void @siblings_top_level(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6) {
184; CHECK-LABEL: @siblings_top_level(
185; CHECK-NEXT:  entry:
186; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]]
187; CHECK:       H1:
188; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
189; CHECK:       A1:
190; CHECK-NEXT:    br label [[IRR_GUARD1]]
191; CHECK:       A2:
192; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[L1:%.*]]
193; CHECK:       L1:
194; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[H1]], label [[EXIT:%.*]]
195; CHECK:       fork1:
196; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
197; CHECK:       B1:
198; CHECK-NEXT:    br label [[H2:%.*]]
199; CHECK:       H2:
200; CHECK-NEXT:    br label [[L2:%.*]]
201; CHECK:       L2:
202; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD]]
203; CHECK:       B2:
204; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[IRR_GUARD]], label [[EXIT]]
205; CHECK:       exit:
206; CHECK-NEXT:    ret void
207; CHECK:       irr.guard:
208; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED4:%.*]], [[FORK1]] ], [ false, [[L2]] ]
209; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1:%.*]], label [[B2]]
210; CHECK:       irr.guard1:
211; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED1:%.*]], [[H1]] ], [ false, [[A1:%.*]] ]
212; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1]], label [[A2]]
213;
214entry:
215  br i1 %Pred0, label %H1, label %fork1
216
217H1:
218  br i1 %Pred1, label %A1, label %A2
219
220A1:
221  br label %A2
222
223A2:
224  br i1 %Pred2, label %A1, label %L1
225
226L1:
227  br i1 %Pred3, label %H1, label %exit
228
229fork1:
230  br i1 %Pred4, label %B1, label %B2
231
232B1:
233  br label %H2
234
235H2:
236  br label %L2
237
238L2:
239  br i1 %Pred5, label %H2, label %B2
240
241B2:
242  br i1 %Pred6, label %B1, label %exit
243
244exit:
245  ret void
246}
247
248define void @siblings_in_loop(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6, i1 %Pred7) {
249; CHECK-LABEL: @siblings_in_loop(
250; CHECK-NEXT:  entry:
251; CHECK-NEXT:    br label [[H0:%.*]]
252; CHECK:       H0:
253; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]]
254; CHECK:       H1:
255; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
256; CHECK:       A1:
257; CHECK-NEXT:    br label [[IRR_GUARD1]]
258; CHECK:       A2:
259; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[L1:%.*]]
260; CHECK:       L1:
261; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[H1]], label [[L0:%.*]]
262; CHECK:       fork1:
263; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
264; CHECK:       B1:
265; CHECK-NEXT:    br label [[H2:%.*]]
266; CHECK:       H2:
267; CHECK-NEXT:    br label [[L2:%.*]]
268; CHECK:       L2:
269; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD]]
270; CHECK:       B2:
271; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[IRR_GUARD]], label [[L0]]
272; CHECK:       L0:
273; CHECK-NEXT:    br i1 [[PRED7:%.*]], label [[EXIT:%.*]], label [[H0]]
274; CHECK:       exit:
275; CHECK-NEXT:    ret void
276; CHECK:       irr.guard:
277; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED4:%.*]], [[FORK1]] ], [ false, [[L2]] ]
278; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1:%.*]], label [[B2]]
279; CHECK:       irr.guard1:
280; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED1:%.*]], [[H1]] ], [ false, [[A1:%.*]] ]
281; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1]], label [[A2]]
282;
283entry:
284  br label %H0
285
286H0:
287  br i1 %Pred0, label %H1, label %fork1
288
289H1:
290  br i1 %Pred1, label %A1, label %A2
291
292A1:
293  br label %A2
294
295A2:
296  br i1 %Pred2, label %A1, label %L1
297
298L1:
299  br i1 %Pred3, label %H1, label %L0
300
301fork1:
302  br i1 %Pred4, label %B1, label %B2
303
304B1:
305  br label %H2
306
307H2:
308  br label %L2
309
310L2:
311  br i1 %Pred5, label %H2, label %B2
312
313B2:
314  br i1 %Pred6, label %B1, label %L0
315
316L0:
317  br i1 %Pred7, label %exit, label %H0
318
319exit:
320  ret void
321}
322
323define void @irreducible_mountain_bug(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) {
324; CHECK-LABEL: @irreducible_mountain_bug(
325; CHECK-NEXT:  entry:
326; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
327; CHECK:       if.end:
328; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[IF_THEN7:%.*]], label [[IF_ELSE:%.*]]
329; CHECK:       if.then7:
330; CHECK-NEXT:    br label [[IF_END16:%.*]]
331; CHECK:       if.else:
332; CHECK-NEXT:    br label [[IF_END16]]
333; CHECK:       if.end16:
334; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[WHILE_COND_PREHEADER:%.*]], label [[IF_THEN39:%.*]]
335; CHECK:       while.cond.preheader:
336; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
337; CHECK:       while.cond:
338; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[IRR_GUARD:%.*]], label [[LOR_RHS:%.*]]
339; CHECK:       cond.true49:
340; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IF_THEN69:%.*]], label [[WHILE_BODY63:%.*]]
341; CHECK:       while.body63:
342; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[EXIT:%.*]], label [[WHILE_COND47:%.*]]
343; CHECK:       while.cond47:
344; CHECK-NEXT:    br label [[IRR_GUARD]]
345; CHECK:       cond.end61:
346; CHECK-NEXT:    br i1 [[PRED7:%.*]], label [[WHILE_BODY63]], label [[WHILE_COND]]
347; CHECK:       if.then69:
348; CHECK-NEXT:    br i1 [[PRED8:%.*]], label [[EXIT]], label [[WHILE_COND]]
349; CHECK:       lor.rhs:
350; CHECK-NEXT:    br i1 [[PRED9:%.*]], label [[IRR_GUARD]], label [[WHILE_END76:%.*]]
351; CHECK:       while.end76:
352; CHECK-NEXT:    br label [[EXIT]]
353; CHECK:       if.then39:
354; CHECK-NEXT:    br i1 [[PRED10:%.*]], label [[EXIT]], label [[IF_END_I145:%.*]]
355; CHECK:       if.end.i145:
356; CHECK-NEXT:    br i1 [[PRED11:%.*]], label [[EXIT]], label [[IF_END8_I149:%.*]]
357; CHECK:       if.end8.i149:
358; CHECK-NEXT:    br label [[EXIT]]
359; CHECK:       if.then:
360; CHECK-NEXT:    br i1 [[PRED12:%.*]], label [[EXIT]], label [[IF_END_I:%.*]]
361; CHECK:       if.end.i:
362; CHECK-NEXT:    br i1 [[PRED13:%.*]], label [[EXIT]], label [[IF_END8_I:%.*]]
363; CHECK:       if.end8.i:
364; CHECK-NEXT:    br label [[EXIT]]
365; CHECK:       exit:
366; CHECK-NEXT:    ret void
367; CHECK:       irr.guard:
368; CHECK-NEXT:    [[GUARD_COND_TRUE49:%.*]] = phi i1 [ [[PRED6:%.*]], [[WHILE_COND47]] ], [ true, [[WHILE_COND]] ], [ false, [[LOR_RHS]] ]
369; CHECK-NEXT:    br i1 [[GUARD_COND_TRUE49]], label [[COND_TRUE49:%.*]], label [[COND_END61:%.*]]
370;
371entry:
372  br i1 %Pred0, label %if.end, label %if.then
373
374if.end:
375  br i1 %Pred1, label %if.then7, label %if.else
376
377if.then7:
378  br label %if.end16
379
380if.else:
381  br label %if.end16
382
383if.end16:
384  br i1 %Pred2, label %while.cond.preheader, label %if.then39
385
386while.cond.preheader:
387  br label %while.cond
388
389while.cond:
390  br i1 %Pred3, label %cond.true49, label %lor.rhs
391
392cond.true49:
393  br i1 %Pred4, label %if.then69, label %while.body63
394
395while.body63:
396  br i1 %Pred5, label %exit, label %while.cond47
397
398while.cond47:
399  br i1 %Pred6, label %cond.true49, label %cond.end61
400
401cond.end61:
402  br i1 %Pred7, label %while.body63, label %while.cond
403
404if.then69:
405  br i1 %Pred8, label %exit, label %while.cond
406
407lor.rhs:
408  br i1 %Pred9, label %cond.end61, label %while.end76
409
410while.end76:
411  br label %exit
412
413if.then39:
414  br i1 %Pred10, label %exit, label %if.end.i145
415
416if.end.i145:
417  br i1 %Pred11, label %exit, label %if.end8.i149
418
419if.end8.i149:
420  br label %exit
421
422if.then:
423  br i1 %Pred12, label %exit, label %if.end.i
424
425if.end.i:
426  br i1 %Pred13, label %exit, label %if.end8.i
427
428if.end8.i:
429  br label %exit
430
431exit:
432  ret void
433}
434