1 ; RUN: opt < %s -disable-output "-passes=print<ddg>" 2>&1 | FileCheck %s
4 ; CHECK-LABEL: 'DDG' for loop 'test1.for.cond1.preheader':
5 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
6 ; CHECK-NEXT: Instructions:
7 ; CHECK-NEXT: %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test1.for.cond1.preheader.preheader ]
9 ; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]]
10 ; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]]
11 ; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]]
12 ; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]]
14 ; CHECK: Node Address:[[N6:0x[0-9a-f]*]]:single-instruction
15 ; CHECK-NEXT: Instructions:
16 ; CHECK-NEXT: %sub = add i64 %n, -1
18 ; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]]
19 ; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]]
21 ; CHECK: Node Address:[[N8]]:single-instruction
22 ; CHECK-NEXT: Instructions:
23 ; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub
25 ; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]]
27 ; CHECK: Node Address:[[N9]]:single-instruction
28 ; CHECK-NEXT: Instructions:
29 ; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12
30 ; CHECK-NEXT: Edges:none!
32 ; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction
33 ; CHECK-NEXT: Instructions:
34 ; CHECK-NEXT: %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
36 ; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]]
37 ; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]]
38 ; CHECK-NEXT: [def-use] to [[N13:0x[0-9a-f]*]]
39 ; CHECK-NEXT: [def-use] to [[N14:0x[0-9a-f]*]]
41 ; CHECK: Node Address:[[N5]]:single-instruction
42 ; CHECK-NEXT: Instructions:
43 ; CHECK-NEXT: %0 = mul nsw i64 %i.04, %n
45 ; CHECK-NEXT: [def-use] to [[N15:0x[0-9a-f]*]]
47 ; CHECK: Node Address:[[N15]]:single-instruction
48 ; CHECK-NEXT: Instructions:
49 ; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %0
51 ; CHECK-NEXT: [def-use] to [[N14]]
53 ; CHECK: Node Address:[[N14]]:single-instruction
54 ; CHECK-NEXT: Instructions:
55 ; CHECK-NEXT: %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
57 ; CHECK-NEXT: [def-use] to [[N16:0x[0-9a-f]*]]
59 ; CHECK: Node Address:[[N16]]:single-instruction
60 ; CHECK-NEXT: Instructions:
61 ; CHECK-NEXT: %1 = load float, float* %arrayidx5, align 4
63 ; CHECK-NEXT: [def-use] to [[N17:0x[0-9a-f]*]]
65 ; CHECK: Node Address:[[N4]]:single-instruction
66 ; CHECK-NEXT: Instructions:
67 ; CHECK-NEXT: %2 = mul nsw i64 %i.04, %n
69 ; CHECK-NEXT: [def-use] to [[N18:0x[0-9a-f]*]]
71 ; CHECK: Node Address:[[N18]]:single-instruction
72 ; CHECK-NEXT: Instructions:
73 ; CHECK-NEXT: %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2
75 ; CHECK-NEXT: [def-use] to [[N19:0x[0-9a-f]*]]
77 ; CHECK: Node Address:[[N13]]:single-instruction
78 ; CHECK-NEXT: Instructions:
79 ; CHECK-NEXT: %sub7 = add i64 %j.02, -1
81 ; CHECK-NEXT: [def-use] to [[N19]]
83 ; CHECK: Node Address:[[N19]]:single-instruction
84 ; CHECK-NEXT: Instructions:
85 ; CHECK-NEXT: %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %sub7
87 ; CHECK-NEXT: [def-use] to [[N20:0x[0-9a-f]*]]
89 ; CHECK: Node Address:[[N20]]:single-instruction
90 ; CHECK-NEXT: Instructions:
91 ; CHECK-NEXT: %3 = load float, float* %arrayidx8, align 4
93 ; CHECK-NEXT: [def-use] to [[N17]]
95 ; CHECK: Node Address:[[N17]]:single-instruction
96 ; CHECK-NEXT: Instructions:
97 ; CHECK-NEXT: %add = fadd float %1, %3
99 ; CHECK-NEXT: [def-use] to [[N26:0x[0-9a-f]*]]
101 ; CHECK: Node Address:[[N3]]:single-instruction
102 ; CHECK-NEXT: Instructions:
103 ; CHECK-NEXT: %4 = mul nsw i64 %i.04, %n
105 ; CHECK-NEXT: [def-use] to [[N27:0x[0-9a-f]*]]
107 ; CHECK: Node Address:[[N27]]:single-instruction
108 ; CHECK-NEXT: Instructions:
109 ; CHECK-NEXT: %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4
111 ; CHECK-NEXT: [def-use] to [[N12]]
113 ; CHECK: Node Address:[[N12]]:single-instruction
114 ; CHECK-NEXT: Instructions:
115 ; CHECK-NEXT: %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02
117 ; CHECK-NEXT: [def-use] to [[N26]]
119 ; CHECK: Node Address:[[N26]]:single-instruction
120 ; CHECK-NEXT: Instructions:
121 ; CHECK-NEXT: store float %add, float* %arrayidx11, align 4
123 ; CHECK-NEXT: [memory] to [[N20]]
125 ; CHECK: Node Address:[[N11]]:single-instruction
126 ; CHECK-NEXT: Instructions:
127 ; CHECK-NEXT: %inc = add i64 %j.02, 1
129 ; CHECK-NEXT: [def-use] to [[N7]]
130 ; CHECK-NEXT: [def-use] to [[N10]]
132 ; CHECK: Node Address:[[N7]]:single-instruction
133 ; CHECK-NEXT: Instructions:
134 ; CHECK-NEXT: %cmp2 = icmp ult i64 %inc, %sub
136 ; CHECK-NEXT: [def-use] to [[N21:0x[0-9a-f]*]]
138 ; CHECK: Node Address:[[N21]]:single-instruction
139 ; CHECK-NEXT: Instructions:
140 ; CHECK-NEXT: br i1 %cmp2, label %for.body4, label %for.inc12.loopexit
141 ; CHECK-NEXT: Edges:none!
143 ; CHECK: Node Address:[[N2]]:single-instruction
144 ; CHECK-NEXT: Instructions:
145 ; CHECK-NEXT: %inc13 = add i64 %i.04, 1
147 ; CHECK-NEXT: [def-use] to [[N22:0x[0-9a-f]*]]
148 ; CHECK-NEXT: [def-use] to [[N1]]
150 ; CHECK: Node Address:[[N22]]:single-instruction
151 ; CHECK-NEXT: Instructions:
152 ; CHECK-NEXT: %exitcond = icmp ne i64 %inc13, %n
154 ; CHECK-NEXT: [def-use] to [[N23:0x[0-9a-f]*]]
156 ; CHECK: Node Address:[[N23]]:single-instruction
157 ; CHECK-NEXT: Instructions:
158 ; CHECK-NEXT: br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14.loopexit
159 ; CHECK-NEXT: Edges:none!
161 ; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:single-instruction
162 ; CHECK-NEXT: Instructions:
163 ; CHECK-NEXT: br label %for.body4
164 ; CHECK-NEXT: Edges:none!
166 ; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction
167 ; CHECK-NEXT: Instructions:
168 ; CHECK-NEXT: br label %for.inc12
169 ; CHECK-NEXT: Edges:none!
173 ;; This test has a cycle.
174 ;; void test1(unsigned long n, float a[][n], float b[][n]) {
175 ;; for (unsigned long i = 0; i < n; i++)
176 ;; for (unsigned long j = 1; j < n-1; j++)
177 ;; a[i][j] = b[i][j] + a[i][j-1];
180 define void @test1(i64 %n, float* noalias %a, float* noalias %b) {
182 %exitcond3 = icmp ne i64 0, %n
183 br i1 %exitcond3, label %test1.for.cond1.preheader, label %for.end14
185 test1.for.cond1.preheader: ; preds = %entry, %for.inc12
186 %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %entry ]
187 %sub = add i64 %n, -1
188 %cmp21 = icmp ult i64 1, %sub
189 br i1 %cmp21, label %for.body4, label %for.inc12
191 for.body4: ; preds = %test1.for.cond1.preheader, %for.body4
192 %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %test1.for.cond1.preheader ]
193 %0 = mul nsw i64 %i.04, %n
194 %arrayidx = getelementptr inbounds float, float* %b, i64 %0
195 %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
196 %1 = load float, float* %arrayidx5, align 4
197 %2 = mul nsw i64 %i.04, %n
198 %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2
199 %sub7 = add i64 %j.02, -1
200 %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %sub7
201 %3 = load float, float* %arrayidx8, align 4
202 %add = fadd float %1, %3
203 %4 = mul nsw i64 %i.04, %n
204 %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4
205 %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02
206 store float %add, float* %arrayidx11, align 4
207 %inc = add i64 %j.02, 1
208 %cmp2 = icmp ult i64 %inc, %sub
209 br i1 %cmp2, label %for.body4, label %for.inc12
211 for.inc12: ; preds = %for.body4, %test1.for.cond1.preheader
212 %inc13 = add i64 %i.04, 1
213 %exitcond = icmp ne i64 %inc13, %n
214 br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14
216 for.end14: ; preds = %for.inc12, %entry
222 ; CHECK-LABEL: 'DDG' for loop 'test2.for.cond1.preheader':
223 ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction
224 ; CHECK-NEXT: Instructions:
225 ; CHECK-NEXT: %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test2.for.cond1.preheader.preheader ]
227 ; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]]
228 ; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]]
229 ; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]]
230 ; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]]
232 ; CHECK: Node Address:[[N6:0x[0-9a-f]*]]:single-instruction
233 ; CHECK-NEXT: Instructions:
234 ; CHECK-NEXT: %sub = add i64 %n, -1
236 ; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]]
237 ; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]]
239 ; CHECK: Node Address:[[N8]]:single-instruction
240 ; CHECK-NEXT: Instructions:
241 ; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub
243 ; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]]
245 ; CHECK: Node Address:[[N9]]:single-instruction
246 ; CHECK-NEXT: Instructions:
247 ; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12
248 ; CHECK-NEXT: Edges:none!
250 ; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction
251 ; CHECK-NEXT: Instructions:
252 ; CHECK-NEXT: %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ]
254 ; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]]
255 ; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]]
256 ; CHECK-NEXT: [def-use] to [[N13:0x[0-9a-f]*]]
257 ; CHECK-NEXT: [def-use] to [[N14:0x[0-9a-f]*]]
259 ; CHECK: Node Address:[[N5]]:single-instruction
260 ; CHECK-NEXT: Instructions:
261 ; CHECK-NEXT: %0 = mul nsw i64 %i.04, %n
263 ; CHECK-NEXT: [def-use] to [[N15:0x[0-9a-f]*]]
265 ; CHECK: Node Address:[[N15]]:single-instruction
266 ; CHECK-NEXT: Instructions:
267 ; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %0
269 ; CHECK-NEXT: [def-use] to [[N14]]
271 ; CHECK: Node Address:[[N14]]:single-instruction
272 ; CHECK-NEXT: Instructions:
273 ; CHECK-NEXT: %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
275 ; CHECK-NEXT: [def-use] to [[N16:0x[0-9a-f]*]]
277 ; CHECK: Node Address:[[N16]]:single-instruction
278 ; CHECK-NEXT: Instructions:
279 ; CHECK-NEXT: %1 = load float, float* %arrayidx5, align 4
281 ; CHECK-NEXT: [def-use] to [[N17:0x[0-9a-f]*]]
283 ; CHECK: Node Address:[[N4]]:single-instruction
284 ; CHECK-NEXT: Instructions:
285 ; CHECK-NEXT: %2 = mul nsw i64 %i.04, %n
287 ; CHECK-NEXT: [def-use] to [[N18:0x[0-9a-f]*]]
289 ; CHECK: Node Address:[[N18]]:single-instruction
290 ; CHECK-NEXT: Instructions:
291 ; CHECK-NEXT: %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2
293 ; CHECK-NEXT: [def-use] to [[N19:0x[0-9a-f]*]]
295 ; CHECK: Node Address:[[N13]]:single-instruction
296 ; CHECK-NEXT: Instructions:
297 ; CHECK-NEXT: %add7 = add i64 %j.02, 1
299 ; CHECK-NEXT: [def-use] to [[N19]]
301 ; CHECK: Node Address:[[N19]]:single-instruction
302 ; CHECK-NEXT: Instructions:
303 ; CHECK-NEXT: %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %add7
305 ; CHECK-NEXT: [def-use] to [[N20:0x[0-9a-f]*]]
307 ; CHECK: Node Address:[[N20]]:single-instruction
308 ; CHECK-NEXT: Instructions:
309 ; CHECK-NEXT: %3 = load float, float* %arrayidx8, align 4
311 ; CHECK-NEXT: [def-use] to [[N17]]
312 ; CHECK-NEXT: [memory] to [[N26:0x[0-9a-f]*]]
314 ; CHECK: Node Address:[[N17]]:single-instruction
315 ; CHECK-NEXT: Instructions:
316 ; CHECK-NEXT: %add = fadd float %1, %3
318 ; CHECK-NEXT: [def-use] to [[N26]]
320 ; CHECK: Node Address:[[N3]]:single-instruction
321 ; CHECK-NEXT: Instructions:
322 ; CHECK-NEXT: %4 = mul nsw i64 %i.04, %n
324 ; CHECK-NEXT: [def-use] to [[N27:0x[0-9a-f]*]]
326 ; CHECK: Node Address:[[N27]]:single-instruction
327 ; CHECK-NEXT: Instructions:
328 ; CHECK-NEXT: %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4
330 ; CHECK-NEXT: [def-use] to [[N12]]
332 ; CHECK: Node Address:[[N12]]:single-instruction
333 ; CHECK-NEXT: Instructions:
334 ; CHECK-NEXT: %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02
336 ; CHECK-NEXT: [def-use] to [[N26]]
338 ; CHECK: Node Address:[[N26]]:single-instruction
339 ; CHECK-NEXT: Instructions:
340 ; CHECK-NEXT: store float %add, float* %arrayidx11, align 4
341 ; CHECK-NEXT: Edges:none!
343 ; CHECK: Node Address:[[N11]]:single-instruction
344 ; CHECK-NEXT: Instructions:
345 ; CHECK-NEXT: %inc = add i64 %j.02, 1
347 ; CHECK-NEXT: [def-use] to [[N7]]
348 ; CHECK-NEXT: [def-use] to [[N10]]
350 ; CHECK: Node Address:[[N7]]:single-instruction
351 ; CHECK-NEXT: Instructions:
352 ; CHECK-NEXT: %cmp2 = icmp ult i64 %inc, %sub
354 ; CHECK-NEXT: [def-use] to [[N21:0x[0-9a-f]*]]
356 ; CHECK: Node Address:[[N21]]:single-instruction
357 ; CHECK-NEXT: Instructions:
358 ; CHECK-NEXT: br i1 %cmp2, label %for.body4, label %for.inc12.loopexit
359 ; CHECK-NEXT: Edges:none!
361 ; CHECK: Node Address:[[N2]]:single-instruction
362 ; CHECK-NEXT: Instructions:
363 ; CHECK-NEXT: %inc13 = add i64 %i.04, 1
365 ; CHECK-NEXT: [def-use] to [[N22:0x[0-9a-f]*]]
366 ; CHECK-NEXT: [def-use] to [[N1]]
368 ; CHECK: Node Address:[[N22]]:single-instruction
369 ; CHECK-NEXT: Instructions:
370 ; CHECK-NEXT: %exitcond = icmp ne i64 %inc13, %n
372 ; CHECK-NEXT: [def-use] to [[N23:0x[0-9a-f]*]]
374 ; CHECK: Node Address:[[N23]]:single-instruction
375 ; CHECK-NEXT: Instructions:
376 ; CHECK-NEXT: br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14.loopexit
377 ; CHECK-NEXT: Edges:none!
379 ; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:single-instruction
380 ; CHECK-NEXT: Instructions:
381 ; CHECK-NEXT: br label %for.body4
382 ; CHECK-NEXT: Edges:none!
384 ; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction
385 ; CHECK-NEXT: Instructions:
386 ; CHECK-NEXT: br label %for.inc12
387 ; CHECK-NEXT: Edges:none!
389 ;; This test has no cycles.
390 ;; void test2(unsigned long n, float a[][n], float b[][n]) {
391 ;; for (unsigned long i = 0; i < n; i++)
392 ;; for (unsigned long j = 1; j < n-1; j++)
393 ;; a[i][j] = b[i][j] + a[i][j+1];
396 define void @test2(i64 %n, float* noalias %a, float* noalias %b) {
398 %exitcond3 = icmp ne i64 0, %n
399 br i1 %exitcond3, label %test2.for.cond1.preheader, label %for.end14
401 test2.for.cond1.preheader: ; preds = %entry, %for.inc12
402 %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %entry ]
403 %sub = add i64 %n, -1
404 %cmp21 = icmp ult i64 1, %sub
405 br i1 %cmp21, label %for.body4, label %for.inc12
407 for.body4: ; preds = %test2.for.cond1.preheader, %for.body4
408 %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %test2.for.cond1.preheader ]
409 %0 = mul nsw i64 %i.04, %n
410 %arrayidx = getelementptr inbounds float, float* %b, i64 %0
411 %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02
412 %1 = load float, float* %arrayidx5, align 4
413 %2 = mul nsw i64 %i.04, %n
414 %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2
415 %add7 = add i64 %j.02, 1
416 %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %add7
417 %3 = load float, float* %arrayidx8, align 4
418 %add = fadd float %1, %3
419 %4 = mul nsw i64 %i.04, %n
420 %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4
421 %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02
422 store float %add, float* %arrayidx11, align 4
423 %inc = add i64 %j.02, 1
424 %cmp2 = icmp ult i64 %inc, %sub
425 br i1 %cmp2, label %for.body4, label %for.inc12
427 for.inc12: ; preds = %for.body4, %test2.for.cond1.preheader
428 %inc13 = add i64 %i.04, 1
429 %exitcond = icmp ne i64 %inc13, %n
430 br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14
432 for.end14: ; preds = %for.inc12, %entry