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 i32 @basic(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) {
5; CHECK-LABEL: @basic(
6; CHECK-NEXT:  entry:
7; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
8; CHECK:       left:
9; CHECK-NEXT:    [[L:%.*]] = add i32 [[L_PHI_MOVED:%.*]], 1
10; CHECK-NEXT:    br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
11; CHECK:       right:
12; CHECK-NEXT:    br i1 [[PREDRIGHT:%.*]], label [[IRR_GUARD]], label [[EXIT]]
13; CHECK:       exit:
14; CHECK-NEXT:    [[Z:%.*]] = phi i32 [ [[L]], [[LEFT:%.*]] ], [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ]
15; CHECK-NEXT:    ret i32 [[Z]]
16; CHECK:       irr.guard:
17; CHECK-NEXT:    [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[LEFT]] ]
18; CHECK-NEXT:    [[L_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ]
19; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[L]], [[LEFT]] ]
20; CHECK-NEXT:    br i1 [[GUARD_LEFT]], label [[LEFT]], label [[RIGHT]]
21;
22entry:
23  br i1 %PredEntry, label %left, label %right
24
25left:
26  %L.phi = phi i32 [%X, %entry], [%R.phi, %right]
27  %L = add i32 %L.phi, 1
28  br i1 %PredLeft, label %right, label %exit
29
30right:
31  %R.phi = phi i32 [%Y, %entry], [%L, %left]
32  br i1 %PredRight, label %left, label %exit
33
34exit:
35  %Z = phi i32 [%L, %left], [%R.phi, %right]
36  ret i32 %Z
37}
38
39define i32 @feedback_loop(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) {
40; CHECK-LABEL: @feedback_loop(
41; CHECK-NEXT:  entry:
42; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
43; CHECK:       left:
44; CHECK-NEXT:    br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
45; CHECK:       right:
46; CHECK-NEXT:    br i1 [[PREDRIGHT:%.*]], label [[IRR_GUARD]], label [[EXIT]]
47; CHECK:       exit:
48; CHECK-NEXT:    [[Z:%.*]] = phi i32 [ [[L_PHI_MOVED:%.*]], [[LEFT:%.*]] ], [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ]
49; CHECK-NEXT:    ret i32 [[Z]]
50; CHECK:       irr.guard:
51; CHECK-NEXT:    [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[LEFT]] ]
52; CHECK-NEXT:    [[L_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ]
53; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ]
54; CHECK-NEXT:    br i1 [[GUARD_LEFT]], label [[LEFT]], label [[RIGHT]]
55;
56entry:
57  br i1 %PredEntry, label %left, label %right
58
59left:
60  %L.phi = phi i32 [%X, %entry], [%R.phi, %right]
61  br i1 %PredLeft, label %right, label %exit
62
63right:
64  %R.phi = phi i32 [%Y, %entry], [%L.phi, %left]
65  br i1 %PredRight, label %left, label %exit
66
67exit:
68  %Z = phi i32 [%L.phi, %left], [%R.phi, %right]
69  ret i32 %Z
70}
71
72define i32 @multiple_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
73; CHECK-LABEL: @multiple_predecessors(
74; CHECK-NEXT:  entry:
75; CHECK-NEXT:    [[PREDB_INV:%.*]] = xor i1 [[PREDB:%.*]], true
76; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]]
77; CHECK:       A:
78; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[X:%.*]], 1
79; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
80; CHECK:       B:
81; CHECK-NEXT:    br label [[IRR_GUARD]]
82; CHECK:       C:
83; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
84; CHECK:       D:
85; CHECK-NEXT:    [[D_INC:%.*]] = add i32 [[D_PHI_MOVED:%.*]], 1
86; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT]], label [[IRR_GUARD]]
87; CHECK:       exit:
88; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_INC]], [[D:%.*]] ]
89; CHECK-NEXT:    ret i32 [[RET]]
90; CHECK:       irr.guard:
91; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ [[PREDB_INV]], [[B]] ], [ [[PREDA:%.*]], [[A]] ], [ false, [[C]] ]
92; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[Y:%.*]], [[B]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ]
93; CHECK-NEXT:    [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ [[Y]], [[B]] ], [ [[A_INC]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ]
94; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[D]]
95;
96entry:
97  br i1 %PredEntry, label %A, label %B
98
99A:
100  %A.inc = add i32 %X, 1
101  br i1 %PredA, label %C, label %D
102
103B:
104  br i1 %PredB, label %D, label %C
105
106C:
107  %C.phi = phi i32 [%X, %A], [%Y, %B], [%D.inc, %D]
108  br i1 %PredC, label %D, label %exit
109
110D:
111  %D.phi = phi i32 [%A.inc, %A], [%Y, %B], [%C.phi, %C]
112  %D.inc = add i32 %D.phi, 1
113  br i1 %PredD, label %exit, label %C
114
115exit:
116  %ret = phi i32 [%C.phi, %C], [%D.inc, %D]
117  ret i32 %ret
118}
119
120define i32 @separate_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
121; CHECK-LABEL: @separate_predecessors(
122; CHECK-NEXT:  entry:
123; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]]
124; CHECK:       A:
125; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[X:%.*]], 1
126; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
127; CHECK:       B:
128; CHECK-NEXT:    br label [[IRR_GUARD]]
129; CHECK:       C:
130; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]]
131; CHECK:       D:
132; CHECK-NEXT:    [[D_INC:%.*]] = add i32 [[D_PHI_MOVED:%.*]], 1
133; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT]], label [[IRR_GUARD]]
134; CHECK:       exit:
135; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_INC]], [[D:%.*]] ]
136; CHECK-NEXT:    ret i32 [[RET]]
137; CHECK:       irr.guard:
138; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ true, [[A]] ], [ false, [[C]] ], [ false, [[B]] ]
139; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ], [ undef, [[B]] ]
140; CHECK-NEXT:    [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ undef, [[A]] ], [ [[C_PHI_MOVED]], [[C]] ], [ [[Y:%.*]], [[B]] ]
141; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[D]]
142;
143entry:
144  br i1 %PredEntry, label %A, label %B
145
146A:
147  %A.inc = add i32 %X, 1
148  br label %C
149
150B:
151  br label %D
152
153C:
154  %C.phi = phi i32 [%X, %A], [%D.inc, %D]
155  br i1 %PredC, label %exit, label %D
156
157D:
158  %D.phi = phi i32 [%Y, %B], [%C.phi, %C]
159  %D.inc = add i32 %D.phi, 1
160  br i1 %PredD, label %exit, label %C
161
162exit:
163  %ret = phi i32 [%C.phi, %C], [%D.inc, %D]
164  ret i32 %ret
165}
166
167define void @four_headers(i1 %PredEntry, i1 %PredX, i1  %PredY, i1 %PredD) {
168; CHECK-LABEL: @four_headers(
169; CHECK-NEXT:  entry:
170; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[X:%.*]], label [[Y:%.*]]
171; CHECK:       X:
172; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
173; CHECK:       Y:
174; CHECK-NEXT:    br label [[IRR_GUARD]]
175; CHECK:       A:
176; CHECK-NEXT:    br label [[IRR_GUARD]]
177; CHECK:       B:
178; CHECK-NEXT:    br label [[IRR_GUARD]]
179; CHECK:       C:
180; CHECK-NEXT:    br label [[IRR_GUARD]]
181; CHECK:       D:
182; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]]
183; CHECK:       exit:
184; CHECK-NEXT:    ret void
185; CHECK:       irr.guard:
186; CHECK-NEXT:    [[GUARD_A:%.*]] = phi i1 [ true, [[D:%.*]] ], [ [[PREDX:%.*]], [[X]] ], [ false, [[A:%.*]] ], [ false, [[B:%.*]] ], [ false, [[Y]] ], [ false, [[C:%.*]] ]
187; CHECK-NEXT:    [[GUARD_B:%.*]] = phi i1 [ false, [[D]] ], [ true, [[X]] ], [ true, [[A]] ], [ false, [[B]] ], [ false, [[Y]] ], [ false, [[C]] ]
188; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ false, [[D]] ], [ false, [[X]] ], [ false, [[A]] ], [ true, [[B]] ], [ [[PREDY:%.*]], [[Y]] ], [ false, [[C]] ]
189; CHECK-NEXT:    br i1 [[GUARD_A]], label [[A]], label [[IRR_GUARD1:%.*]]
190; CHECK:       irr.guard1:
191; CHECK-NEXT:    br i1 [[GUARD_B]], label [[B]], label [[IRR_GUARD2:%.*]]
192; CHECK:       irr.guard2:
193; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[D]]
194;
195entry:
196  br i1 %PredEntry, label %X, label %Y
197
198X:
199  br i1 %PredX, label %A, label %B
200
201Y:
202  br i1 %PredY, label %C, label %D
203
204A:
205  br label %B
206
207B:
208  br label %C
209
210C:
211  br label %D
212
213D:
214  br i1 %PredD, label %exit, label %A
215
216exit:
217  ret void
218}
219
220define i32 @hidden_nodes(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
221; CHECK-LABEL: @hidden_nodes(
222; CHECK-NEXT:  entry:
223; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
224; CHECK:       A:
225; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[A_PHI_MOVED:%.*]], 1
226; CHECK-NEXT:    br label [[IRR_GUARD]]
227; CHECK:       B:
228; CHECK-NEXT:    br label [[C:%.*]]
229; CHECK:       C:
230; CHECK-NEXT:    [[C_INC:%.*]] = add i32 [[B_PHI_MOVED:%.*]], 1
231; CHECK-NEXT:    br label [[D:%.*]]
232; CHECK:       D:
233; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[E:%.*]]
234; CHECK:       E:
235; CHECK-NEXT:    br label [[IRR_GUARD]]
236; CHECK:       exit:
237; CHECK-NEXT:    ret i32 [[B_PHI_MOVED]]
238; CHECK:       irr.guard:
239; CHECK-NEXT:    [[GUARD_A:%.*]] = phi i1 [ true, [[E]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[A:%.*]] ]
240; CHECK-NEXT:    [[A_PHI_MOVED]] = phi i32 [ [[C_INC]], [[E]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[A_PHI_MOVED]], [[A]] ]
241; CHECK-NEXT:    [[B_PHI_MOVED]] = phi i32 [ undef, [[E]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[A_INC]], [[A]] ]
242; CHECK-NEXT:    br i1 [[GUARD_A]], label [[A]], label [[B:%.*]]
243;
244entry:
245  br i1 %PredEntry, label %A, label %B
246
247A:
248  %A.phi = phi i32 [%X, %entry], [%C.inc, %E]
249  %A.inc = add i32 %A.phi, 1
250  br label %B
251
252B:
253  %B.phi = phi i32 [%A.inc, %A], [%Y, %entry]
254  br label %C
255
256C:
257  %C.inc = add i32 %B.phi, 1
258  br label %D
259
260D:
261  br i1 %PredD, label %exit, label %E
262
263E:
264  br label %A
265
266exit:
267  ret i32 %B.phi
268}
269