1; RUN: opt < %s -basic-aa -loop-interchange -pass-remarks-missed='loop-interchange' -verify-loop-lcssa -pass-remarks-output=%t -S
2; RUN: FileCheck --input-file %t --check-prefix REMARK %s
3
4target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
5target triple = "x86_64-unknown-linux-gnu"
6
7@A = common global [100 x [100 x i32]] zeroinitializer
8@C = common global [100 x [100 x i32]] zeroinitializer
9@X = common global i32 0
10@Y = common global i64 0
11@F = common global float 0.0
12
13; We cannot interchange this loop at the moment, because iv.outer.next is
14; produced in the outer loop latch and used in the loop exit block. If the inner
15; loop body is not executed, the outer loop latch won't be executed either
16; after interchanging.
17; REMARK: UnsupportedExitPHI
18; REMARK-NEXT: lcssa_01
19
20define void @lcssa_01() {
21entry:
22  %cmp21 = icmp sgt i64 100, 1
23  br i1 %cmp21, label %outer.ph, label %for.end16
24
25outer.ph:                                         ; preds = %entry
26  %cmp218 = icmp sgt i64 100, 1
27  br label %outer.header
28
29outer.header:                                     ; preds = %outer.inc, %outer.ph
30  %iv.outer = phi i64 [ 1, %outer.ph ], [ %iv.outer.next, %outer.inc ]
31  br i1 %cmp218, label %for.body3, label %outer.inc
32
33for.body3:                                        ; preds = %for.body3, %outer.header
34  %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
35  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
36  %vA = load i32, i32* %arrayidx5
37  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
38  %vC = load i32, i32* %arrayidx9
39  %add = add nsw i32 %vA, %vC
40  store i32 %add, i32* %arrayidx5
41  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
42  %exitcond = icmp eq i64 %iv.inner.next, 100
43  br i1 %exitcond, label %outer.inc, label %for.body3
44
45outer.inc:                                        ; preds = %for.body3, %outer.header
46  %iv.outer.next = add nsw i64 %iv.outer, 1
47  %cmp = icmp eq i64 %iv.outer.next, 100
48  br i1 %cmp, label %outer.header, label %for.exit
49
50for.exit:                                         ; preds = %outer.inc
51  %iv.outer.next.lcssa = phi i64 [ %iv.outer.next, %outer.inc ]
52  store i64 %iv.outer.next.lcssa, i64* @Y
53  br label %for.end16
54
55for.end16:                                        ; preds = %for.exit, %entry
56  ret void
57}
58
59; REMARK: UnsupportedExitPHI
60; REMARK-NEXT: lcssa_02
61define void @lcssa_02() {
62entry:
63  %cmp21 = icmp sgt i64 100, 1
64  br i1 %cmp21, label %outer.ph, label %for.end16
65
66outer.ph:                                         ; preds = %entry
67  %cmp218 = icmp sgt i64 100, 1
68  br label %outer.header
69
70outer.header:                                     ; preds = %outer.inc, %outer.ph
71  %iv.outer = phi i64 [ 1, %outer.ph ], [ %iv.outer.next, %outer.inc ]
72  br i1 %cmp218, label %for.body3, label %outer.inc
73
74for.body3:                                        ; preds = %for.body3, %outer.header
75  %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
76  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
77  %vA = load i32, i32* %arrayidx5
78  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
79  %vC = load i32, i32* %arrayidx9
80  %add = add nsw i32 %vA, %vC
81  store i32 %add, i32* %arrayidx5
82  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
83  %exitcond = icmp eq i64 %iv.inner.next, 100
84  br i1 %exitcond, label %outer.inc, label %for.body3
85
86outer.inc:                                        ; preds = %for.body3, %outer.header
87  %iv.inner.end = phi i64 [ 0, %outer.header ], [ %iv.inner.next, %for.body3 ]
88  %iv.outer.next = add nsw i64 %iv.outer, 1
89  %cmp = icmp eq i64 %iv.outer.next, 100
90  br i1 %cmp, label %outer.header, label %for.exit
91
92for.exit:                                         ; preds = %outer.inc
93  %iv.inner.end.lcssa = phi i64 [ %iv.inner.end, %outer.inc ]
94  store i64 %iv.inner.end.lcssa, i64* @Y
95  br label %for.end16
96
97for.end16:                                        ; preds = %for.exit, %entry
98  ret void
99}
100
101; REMARK: Interchanged
102; REMARK-NEXT: lcssa_03
103define void @lcssa_03() {
104entry:
105  br label %outer.header
106
107outer.header:                                     ; preds = %outer.inc, %entry
108  %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
109  br label %for.body3
110
111for.body3:                                        ; preds = %for.body3, %outer.header
112  %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
113  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
114  %vA = load i32, i32* %arrayidx5
115  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
116  %vC = load i32, i32* %arrayidx9
117  %add = add nsw i32 %vA, %vC
118  store i32 %add, i32* %arrayidx5
119  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
120  %exitcond = icmp eq i64 %iv.inner.next, 100
121  br i1 %exitcond, label %outer.inc, label %for.body3
122
123outer.inc:                                        ; preds = %for.body3
124  %iv.inner.lcssa = phi i64 [ %iv.inner, %for.body3 ]
125  %iv.outer.next = add nsw i64 %iv.outer, 1
126  %cmp = icmp eq i64 %iv.outer.next, 100
127  br i1 %cmp, label %outer.header, label %for.exit
128
129for.exit:                                         ; preds = %outer.inc
130  %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
131  store i64 %iv.inner.lcssa.lcssa, i64* @Y
132  br label %for.end16
133
134for.end16:                                        ; preds = %for.exit
135  ret void
136}
137
138; Loops with floating point reductions are interchanged with fastmath.
139; REMARK: Interchanged
140; REMARK-NEXT: lcssa_04
141
142define void @lcssa_04() {
143entry:
144  br label %outer.header
145
146outer.header:                                     ; preds = %outer.inc, %entry
147  %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
148  %float.outer = phi float [ 1.000000e+00, %entry ], [ %float.outer.next, %outer.inc ]
149  br label %for.body3
150
151for.body3:                                        ; preds = %for.body3, %outer.header
152  %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
153  %float.inner = phi float [ %float.inner.next, %for.body3 ], [ %float.outer, %outer.header ]
154  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
155  %vA = load i32, i32* %arrayidx5
156  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
157  %vC = load i32, i32* %arrayidx9
158  %add = add nsw i32 %vA, %vC
159  %float.inner.next = fadd fast float %float.inner, 1.000000e+00
160  store i32 %add, i32* %arrayidx5
161  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
162  %exitcond = icmp eq i64 %iv.inner.next, 100
163  br i1 %exitcond, label %outer.inc, label %for.body3
164
165outer.inc:                                        ; preds = %for.body3
166  %float.outer.next = phi float [ %float.inner.next, %for.body3 ]
167  %iv.outer.next = add nsw i64 %iv.outer, 1
168  %cmp = icmp eq i64 %iv.outer.next, 100
169  br i1 %cmp, label %outer.header, label %for.exit
170
171for.exit:                                         ; preds = %outer.inc
172  %float.outer.lcssa = phi float [ %float.outer.next, %outer.inc ]
173  store float %float.outer.lcssa, float* @F
174  br label %for.end16
175
176for.end16:                                        ; preds = %for.exit
177  ret void
178}
179
180; PHI node in inner latch with multiple predecessors.
181; REMARK: Interchanged
182; REMARK-NEXT: lcssa_05
183
184define void @lcssa_05(i32* %ptr) {
185entry:
186  br label %outer.header
187
188outer.header:                                     ; preds = %outer.inc, %entry
189  %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
190  br label %for.body3
191
192for.body3:                                        ; preds = %bb3, %outer.header
193  %iv.inner = phi i64 [ %iv.inner.next, %bb3 ], [ 1, %outer.header ]
194  br i1 undef, label %bb2, label %bb3
195
196bb2:                                              ; preds = %for.body3
197  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
198  %vA = load i32, i32* %arrayidx5
199  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
200  %vC = load i32, i32* %arrayidx9
201  %add = add nsw i32 %vA, %vC
202  br label %bb3
203
204bb3:                                              ; preds = %bb2, %for.body3
205  %addp = phi i32 [ %add, %bb2 ], [ 0, %for.body3 ]
206  store i32 %addp, i32* %ptr
207  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
208  %exitcond = icmp eq i64 %iv.inner.next, 100
209  br i1 %exitcond, label %outer.inc, label %for.body3
210
211outer.inc:                                        ; preds = %bb3
212  %iv.inner.lcssa = phi i64 [ %iv.inner, %bb3 ]
213  %iv.outer.next = add nsw i64 %iv.outer, 1
214  %cmp = icmp eq i64 %iv.outer.next, 100
215  br i1 %cmp, label %outer.header, label %for.exit
216
217for.exit:                                         ; preds = %outer.inc
218  %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
219  store i64 %iv.inner.lcssa.lcssa, i64* @Y
220  br label %for.end16
221
222for.end16:                                        ; preds = %for.exit
223  ret void
224}
225
226; REMARK: UnsupportedExitPHI
227; REMARK-NEXT: lcssa_06
228
229define void @lcssa_06(i64* %ptr, i32* %ptr1) {
230entry:
231  br label %outer.header
232
233outer.header:                                     ; preds = %outer.inc, %entry
234  %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
235  br i1 undef, label %for.body3, label %outer.inc
236
237for.body3:                                        ; preds = %for.body3, %outer.header
238  %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
239  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
240  %vA = load i32, i32* %arrayidx5
241  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
242  %vC = load i32, i32* %arrayidx9
243  %add = add nsw i32 %vA, %vC
244  store i32 %add, i32* %ptr1
245  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
246  %exitcond = icmp eq i64 %iv.inner.next, 100
247  br i1 %exitcond, label %outer.inc, label %for.body3
248
249outer.inc:                                        ; preds = %for.body3, %outer.header
250  %sv = phi i64 [ 0, %outer.header ], [ 1, %for.body3 ]
251  %iv.outer.next = add nsw i64 %iv.outer, 1
252  %cmp = icmp eq i64 %iv.outer.next, 100
253  br i1 %cmp, label %outer.header, label %for.exit
254
255for.exit:                                         ; preds = %outer.inc
256  %sv.lcssa = phi i64 [ %sv, %outer.inc ]
257  store i64 %sv.lcssa, i64* @Y
258  br label %for.end16
259
260for.end16:                                        ; preds = %for.exit
261  ret void
262}
263
264; REMARK: Interchanged
265; REMARK-NEXT: lcssa_07
266define void @lcssa_07() {
267entry:
268  br label %outer.header
269
270outer.header:                                     ; preds = %outer.inc, %entry
271  %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
272  br label %for.body3
273
274for.body3:                                        ; preds = %for.body3, %outer.header
275  %iv.inner = phi i64 [ %iv.inner.next, %for.body3 ], [ 1, %outer.header ]
276  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
277  %vA = load i32, i32* %arrayidx5
278  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
279  %vC = load i32, i32* %arrayidx9
280  %add = add nsw i32 %vA, %vC
281  store i32 %add, i32* %arrayidx5
282  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
283  %exitcond = icmp eq i64 %iv.inner.next, 100
284  br i1 %exitcond, label %outer.bb, label %for.body3
285
286outer.bb:                                         ; preds = %for.body3
287  %iv.inner.lcssa = phi i64 [ %iv.inner, %for.body3 ]
288  br label %outer.inc
289
290outer.inc:                                        ; preds = %outer.bb
291  %iv.outer.next = add nsw i64 %iv.outer, 1
292  %cmp = icmp eq i64 %iv.outer.next, 100
293  br i1 %cmp, label %outer.header, label %for.exit
294
295for.exit:                                         ; preds = %outer.inc
296  %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
297  store i64 %iv.inner.lcssa.lcssa, i64* @Y
298  br label %for.end16
299
300for.end16:                                        ; preds = %for.exit
301  ret void
302}
303
304; Should not crash when the outer header branches to
305; both the inner loop and the outer latch, and there
306; is an lcssa phi node outside the loopnest.
307; REMARK: Interchanged
308; REMARK-NEXT: lcssa_08
309define i64 @lcssa_08([100 x [100 x i64]]* %Arr) {
310entry:
311  br label %for1.header
312
313for1.header:                                         ; preds = %for1.inc, %entry
314  %indvars.iv23 = phi i64 [ 0, %entry ], [ %indvars.iv.next24, %for1.inc ]
315  br i1 undef, label %for2, label %for1.inc
316
317for2:                                        ; preds = %for2, %for1.header
318  %indvars.iv = phi i64 [ 0, %for1.header ], [ %indvars.iv.next.3, %for2 ]
319  %arrayidx = getelementptr inbounds [100 x [100 x i64]], [100 x [100 x i64]]* %Arr, i64 0, i64 %indvars.iv, i64 %indvars.iv23
320  %lv = load i64, i64* %arrayidx, align 4
321  %indvars.iv.next.3 = add nuw nsw i64 %indvars.iv, 1
322  %exit1 = icmp eq i64 %indvars.iv.next.3, 100
323  br i1 %exit1, label %for1.inc, label %for2
324
325for1.inc:                                ; preds = %for2, %for1.header
326  %indvars.iv.next24 = add nuw nsw i64 %indvars.iv23, 1
327  %exit2 = icmp eq i64 %indvars.iv.next24, 100
328  br i1 %exit2, label %for1.loopexit, label %for1.header
329
330for1.loopexit:                                 ; preds = %for1.inc
331  %sum.outer.lcssa = phi i64 [ %indvars.iv23, %for1.inc ]
332  ret i64 %sum.outer.lcssa
333}
334
335