1; RUN: opt -S -passes='print<loopnest>' < %s 2>&1 > /dev/null | FileCheck %s
2
3; int f(int N, int M) {
4;   int res = 0;
5;   for (int i = 0; i < N; ++i) {
6;     for (int j = 0; j < M; ++j) res += i * j;
7;   }
8;   return res;
9; }
10
11define i32 @f(i32 %N, i32 %M) #0 {
12; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.j, Loops: ( for.j )
13; CHECK: IsPerfect=true, Depth=2, OutermostLoop: for.i, Loops: ( for.i for.j )
14entry:
15  %cmp4 = icmp slt i32 0, %N
16  br i1 %cmp4, label %for.i.ph, label %for.i.end
17
18for.i.ph:                                         ; preds = %entry
19  br label %for.i
20
21for.i:                                            ; preds = %for.i.ph, %for.i.inc
22  %i.06 = phi i32 [ 0, %for.i.ph ], [ %inc5, %for.i.inc ]
23  %res.05 = phi i32 [ 0, %for.i.ph ], [ %res.1.lcssa, %for.i.inc ]
24  %cmp21 = icmp slt i32 0, %M
25  br i1 %cmp21, label %for.j.ph, label %for.j.end
26
27for.j.ph:                                         ; preds = %for.i
28  br label %for.j
29
30for.j:                                            ; preds = %for.j.ph, %for.j.inc
31  %j.03 = phi i32 [ 0, %for.j.ph ], [ %inc, %for.j.inc ]
32  %res.12 = phi i32 [ %res.05, %for.j.ph ], [ %add, %for.j.inc ]
33  %mul = mul nsw i32 %i.06, %j.03
34  %add = add nsw i32 %res.12, %mul
35  br label %for.j.inc
36
37for.j.inc:                                        ; preds = %for.j
38  %inc = add nsw i32 %j.03, 1
39  %cmp2 = icmp slt i32 %inc, %M
40  br i1 %cmp2, label %for.j, label %for.j.end_crit_edge
41
42for.j.end_crit_edge:                              ; preds = %for.j.inc
43  %split = phi i32 [ %add, %for.j.inc ]
44  br label %for.j.end
45
46for.j.end:                                        ; preds = %for.j.end_crit_edge, %for.i
47  %res.1.lcssa = phi i32 [ %split, %for.j.end_crit_edge ], [ %res.05, %for.i ]
48  br label %for.i.inc
49
50for.i.inc:                                        ; preds = %for.j.end
51  %inc5 = add nsw i32 %i.06, 1
52  %cmp = icmp slt i32 %inc5, %N
53  br i1 %cmp, label %for.i, label %for.i.end_crit_edge
54
55for.i.end_crit_edge:                              ; preds = %for.i.inc
56  %split7 = phi i32 [ %res.1.lcssa, %for.i.inc ]
57  br label %for.i.end
58
59for.i.end:                                        ; preds = %for.i.end_crit_edge, %entry
60  %res.0.lcssa = phi i32 [ %split7, %for.i.end_crit_edge ], [ 0, %entry ]
61  ret i32 %res.0.lcssa
62}
63
64; int g(int N, int M, int K) {
65;   int sum = 0, prod = 1;
66;   for (int i = 0; i < N; ++i) {
67;     for (int j = 0; j < M; ++j) {
68;       for (int k = 0; k < K; ++k) {
69;         sum += i * j * k;
70;       }
71;       prod *= (i + j);
72;     }
73;   }
74;   return sum + prod;
75; }
76define i32 @g(i32 %N, i32 %M, i32 %K) #0 {
77; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.k, Loops: ( for.k )
78; CHECK: IsPerfect=false, Depth=2, OutermostLoop: for.j, Loops: ( for.j for.k )
79; CHECK: IsPerfect=false, Depth=3, OutermostLoop: for.i, Loops: ( for.i for.j for.k )
80entry:
81  %cmp10 = icmp slt i32 0, %N
82  br i1 %cmp10, label %for.i.ph, label %for.i.end
83
84for.i.ph:                                         ; preds = %entry
85  br label %for.i
86
87for.i:                                            ; preds = %for.i.ph, %for.i.inc
88  %i.013 = phi i32 [ 0, %for.i.ph ], [ %inc14, %for.i.inc ]
89  %sum.012 = phi i32 [ 0, %for.i.ph ], [ %sum.1.lcssa, %for.i.inc ]
90  %prod.011 = phi i32 [ 1, %for.i.ph ], [ %prod.1.lcssa, %for.i.inc ]
91  %cmp24 = icmp slt i32 0, %M
92  br i1 %cmp24, label %for.j.ph, label %for.j.end
93
94for.j.ph:                                         ; preds = %for.i
95  br label %for.j
96
97for.j:                                            ; preds = %for.j.ph, %for.j.inc
98  %j.07 = phi i32 [ 0, %for.j.ph ], [ %inc11, %for.j.inc ]
99  %sum.16 = phi i32 [ %sum.012, %for.j.ph ], [ %sum.2.lcssa, %for.j.inc ]
100  %prod.15 = phi i32 [ %prod.011, %for.j.ph ], [ %mul9, %for.j.inc ]
101  %cmp51 = icmp slt i32 0, %K
102  br i1 %cmp51, label %for.k.ph, label %for.k.end
103
104for.k.ph:                                         ; preds = %for.j
105  br label %for.k
106
107for.k:                                            ; preds = %for.k.ph, %for.k.inc
108  %k.03 = phi i32 [ 0, %for.k.ph ], [ %inc, %for.k.inc ]
109  %sum.22 = phi i32 [ %sum.16, %for.k.ph ], [ %add, %for.k.inc ]
110  %mul = mul nsw i32 %i.013, %j.07
111  %mul7 = mul nsw i32 %mul, %k.03
112  %add = add nsw i32 %sum.22, %mul7
113  br label %for.k.inc
114
115for.k.inc:                                        ; preds = %for.k
116  %inc = add nsw i32 %k.03, 1
117  %cmp5 = icmp slt i32 %inc, %K
118  br i1 %cmp5, label %for.k, label %for.k.end_crit_edge
119
120for.k.end_crit_edge:                              ; preds = %for.k.inc
121  %split = phi i32 [ %add, %for.k.inc ]
122  br label %for.k.end
123
124for.k.end:                                        ; preds = %for.k.end_crit_edge, %for.j
125  %sum.2.lcssa = phi i32 [ %split, %for.k.end_crit_edge ], [ %sum.16, %for.j ]
126  %add8 = add nsw i32 %i.013, %j.07
127  %mul9 = mul nsw i32 %prod.15, %add8
128  br label %for.j.inc
129
130for.j.inc:                                        ; preds = %for.k.end
131  %inc11 = add nsw i32 %j.07, 1
132  %cmp2 = icmp slt i32 %inc11, %M
133  br i1 %cmp2, label %for.j, label %for.j.end_crit_edge
134
135for.j.end_crit_edge:                              ; preds = %for.j.inc
136  %split8 = phi i32 [ %mul9, %for.j.inc ]
137  %split9 = phi i32 [ %sum.2.lcssa, %for.j.inc ]
138  br label %for.j.end
139
140for.j.end:                                        ; preds = %for.j.end1crit_edge, %for.i
141  %prod.1.lcssa = phi i32 [ %split8, %for.j.end_crit_edge ], [ %prod.011, %for.i ]
142  %sum.1.lcssa = phi i32 [ %split9, %for.j.end_crit_edge ], [ %sum.012, %for.i ]
143  br label %for.i.inc
144
145for.i.inc:                                        ; preds = %for.j.end
146  %inc14 = add nsw i32 %i.013, 1
147  %cmp = icmp slt i32 %inc14, %N
148  br i1 %cmp, label %for.i, label %for.i.end_crit_edge
149
150for.i.end_crit_edge:                              ; preds = %for.i.inc
151  %split14 = phi i32 [ %prod.1.lcssa, %for.i.inc ]
152  %split15 = phi i32 [ %sum.1.lcssa, %for.i.inc ]
153  br label %for.i.end
154
155for.i.end:                                        ; preds = %for.i.end_crit_edge, %entry
156  %prod.0.lcssa = phi i32 [ %split14, %for.i.end_crit_edge ], [ 1, %entry ]
157  %sum.0.lcssa = phi i32 [ %split15, %for.i.end_crit_edge ], [ 0, %entry ]
158  %add16 = add nsw i32 %sum.0.lcssa, %prod.0.lcssa
159  ret i32 %add16
160}
161
162; int h(int N, int M, int K) {
163;   int sum = 0;
164;   for (int i = 0; i < N; ++i) {
165;     for (int j = 0; j < M; ++j) {
166;       for (int k = 0; k < K; ++k) {
167;         sum += i * j * k;
168;       }
169;     }
170;   }
171;   return sum;
172; }
173define i32 @h(i32 %N, i32 %M, i32 %K) #0 {
174; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.k, Loops: ( for.k )
175; CHECK: IsPerfect=true, Depth=2, OutermostLoop: for.j, Loops: ( for.j for.k )
176; CHECK: IsPerfect=true, Depth=3, OutermostLoop: for.i, Loops: ( for.i for.j for.k )
177entry:
178  %cmp8 = icmp slt i32 0, %N
179  br i1 %cmp8, label %for.i.ph, label %for.i.end
180
181for.i.ph:                                         ; preds = %entry
182  br label %for.i
183
184for.i:                                            ; preds = %for.i.ph, %for.i.inc
185  %i.010 = phi i32 [ 0, %for.i.ph ], [ %inc12, %for.i.inc ]
186  %sum.09 = phi i32 [ 0, %for.i.ph ], [ %sum.1.lcssa, %for.i.inc ]
187  %cmp24 = icmp slt i32 0, %M
188  br i1 %cmp24, label %for.j.ph, label %for.j.end
189
190for.j.ph:                                         ; preds = %for.i
191  br label %for.j
192
193for.j:                                            ; preds = %for.j.ph, %for.j.inc
194  %j.06 = phi i32 [ 0, %for.j.ph ], [ %inc9, %for.j.inc ]
195  %sum.15 = phi i32 [ %sum.09, %for.j.ph ], [ %sum.2.lcssa, %for.j.inc ]
196  %cmp51 = icmp slt i32 0, %K
197  br i1 %cmp51, label %for.k.ph, label %for.k.end
198
199for.k.ph:                                         ; preds = %for.j
200  br label %for.k
201
202for.k:                                            ; preds = %for.k.ph, %for.k.inc
203  %k.03 = phi i32 [ 0, %for.k.ph ], [ %inc, %for.k.inc ]
204  %sum.22 = phi i32 [ %sum.15, %for.k.ph ], [ %add, %for.k.inc ]
205  %mul = mul nsw i32 %i.010, %j.06
206  %mul7 = mul nsw i32 %mul, %k.03
207  %add = add nsw i32 %sum.22, %mul7
208  br label %for.k.inc
209
210for.k.inc:                                        ; preds = %for.k
211  %inc = add nsw i32 %k.03, 1
212  %cmp5 = icmp slt i32 %inc, %K
213  br i1 %cmp5, label %for.k, label %for.k.end_crit_edge
214
215for.k.end_crit_edge:                              ; preds = %for.k.inc
216  %split = phi i32 [ %add, %for.k.inc ]
217  br label %for.k.end
218
219for.k.end:                                        ; preds = %for.k.end_crit_edge, %for.j
220  %sum.2.lcssa = phi i32 [ %split, %for.k.end_crit_edge ], [ %sum.15, %for.j ]
221  br label %for.j.inc
222
223for.j.inc:                                        ; preds = %for.k.end
224  %inc9 = add nsw i32 %j.06, 1
225  %cmp2 = icmp slt i32 %inc9, %M
226  br i1 %cmp2, label %for.j, label %for.j.end_crit_edge
227
228for.j.end_crit_edge:                              ; preds = %for.j.inc
229  %split7 = phi i32 [ %sum.2.lcssa, %for.j.inc ]
230  br label %for.j.end
231
232for.j.end:                                        ; preds = %for.j.end_crit_edge, %for.i
233  %sum.1.lcssa = phi i32 [ %split7, %for.j.end_crit_edge ], [ %sum.09, %for.i ]
234  br label %for.i.inc
235
236for.i.inc:                                        ; preds = %for.j.end
237  %inc12 = add nsw i32 %i.010, 1
238  %cmp = icmp slt i32 %inc12, %N
239  br i1 %cmp, label %for.i, label %for.i.end_crit_edge
240
241for.i.end_crit_edge:                              ; preds = %for.i.inc
242  %split11 = phi i32 [ %sum.1.lcssa, %for.i.inc ]
243  br label %for.i.end
244
245for.i.end:                                        ; preds = %for.i.end_crit_edge, %entry
246  %sum.0.lcssa = phi i32 [ %split11, %for.i.end_crit_edge ], [ 0, %entry ]
247  ret i32 %sum.0.lcssa
248}
249