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