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