1; RUN: opt < %s -passes="loop-vectorize" -force-vector-interleave=1 -force-vector-width=4 -S | FileCheck %s
2
3target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
4
5; This test checks that we can vectorize loop with reduction variable
6; stored in an invariant address.
7;
8; int sum = 0;
9; for(i=0..N) {
10;   sum += src[i];
11;   dst[42] = sum;
12; }
13; CHECK-LABEL: @reduc_store
14; CHECK-NOT: vector.body
15define void @reduc_store(i32* %dst, i32* readonly %src) {
16entry:
17  %gep.dst = getelementptr inbounds i32, i32* %dst, i64 42
18  store i32 0, i32* %gep.dst, align 4
19  br label %for.body
20
21for.body:
22  %sum = phi i32 [ 0, %entry ], [ %add, %for.body ]
23  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
24  %gep.src = getelementptr inbounds i32, i32* %src, i64 %iv
25  %0 = load i32, i32* %gep.src, align 4
26  %add = add nsw i32 %sum, %0
27  store i32 %add, i32* %gep.dst, align 4
28  %iv.next = add nuw nsw i64 %iv, 1
29  %exitcond = icmp eq i64 %iv.next, 1000
30  br i1 %exitcond, label %exit, label %for.body
31
32exit:
33  ret void
34}
35
36; Same as above but with floating point numbers instead.
37;
38; float sum = 0;
39; for(i=0..N) {
40;   sum += src[i];
41;   dst[42] = sum;
42; }
43; CHECK-LABEL: @reduc_store_fadd_fast
44; CHECK-NOT: vector.body
45define void @reduc_store_fadd_fast(float* %dst, float* readonly %src) {
46entry:
47  %gep.dst = getelementptr inbounds float, float* %dst, i64 42
48  store float 0.000000e+00, float* %gep.dst, align 4
49  br label %for.body
50
51for.body:
52  %sum = phi float [ 0.000000e+00, %entry ], [ %add, %for.body ]
53  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
54  %gep.src = getelementptr inbounds float, float* %src, i64 %iv
55  %0 = load float, float* %gep.src, align 4
56  %add = fadd fast float %sum, %0
57  store float %add, float* %gep.dst, align 4
58  %iv.next = add nuw nsw i64 %iv, 1
59  %exitcond = icmp eq i64 %iv.next, 1000
60  br i1 %exitcond, label %exit, label %for.body
61
62exit:
63  ret void
64}
65
66; Check that if we have a read from an invariant address, we do not vectorize.
67;
68; int sum = 0;
69; for(i=0..N) {
70;   sum += src[i];
71;   dst.2[i] = dst[42];
72;   dst[42] = sum;
73; }
74; CHECK-LABEL: @reduc_store_load
75; CHECK-NOT: vector.body
76define void @reduc_store_load(i32* %dst, i32* readonly %src, i32* noalias %dst.2) {
77entry:
78  %gep.dst = getelementptr inbounds i32, i32* %dst, i64 42
79  store i32 0, i32* %gep.dst, align 4
80  br label %for.body
81
82for.body:
83  %sum = phi i32 [ 0, %entry ], [ %add, %for.body ]
84  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
85  %gep.src = getelementptr inbounds i32, i32* %src, i64 %iv
86  %0 = load i32, i32* %gep.src, align 4
87  %add = add nsw i32 %sum, %0
88  %lv = load i32, i32* %gep.dst
89  %gep.dst.2  = getelementptr inbounds i32, i32* %dst.2, i64 %iv
90  store i32 %lv, i32* %gep.dst.2, align 4
91  store i32 %add, i32* %gep.dst, align 4
92  %iv.next = add nuw nsw i64 %iv, 1
93  %exitcond = icmp eq i64 %iv.next, 1000
94  br i1 %exitcond, label %exit, label %for.body
95
96exit:
97  ret void
98}
99
100; Final value is not guaranteed to be stored in an invariant address.
101; We don't vectorize in that case.
102;
103; int sum = 0;
104; for(i=0..N) {
105;   int diff = y[i] - x[i];
106;   if (diff > 0) {
107;     sum = += diff;
108;     *t = sum;
109;   }
110; }
111; CHECK-LABEL: @reduc_cond_store
112; CHECK-NOT: vector.body
113define void @reduc_cond_store(i32* %t, i32* readonly %x, i32* readonly %y) {
114entry:
115  store i32 0, i32* %t, align 4
116  br label %for.body
117
118for.body:
119  %sum = phi i32 [ 0, %entry ], [ %sum.2, %if.end ]
120  %iv = phi i64 [ 0, %entry ], [ %iv.next, %if.end ]
121  %gep.y = getelementptr inbounds i32, i32* %y, i64 %iv
122  %0 = load i32, i32* %gep.y, align 4
123  %gep.x = getelementptr inbounds i32, i32* %x, i64 %iv
124  %1 = load i32, i32* %gep.x, align 4
125  %diff = sub nsw i32 %0, %1
126  %cmp2 = icmp sgt i32 %diff, 0
127  br i1 %cmp2, label %if.then, label %if.end
128
129if.then:
130  %sum.1 = add nsw i32 %diff, %sum
131  store i32 %sum.1, i32* %t, align 4
132  br label %if.end
133
134if.end:
135  %sum.2 = phi i32 [ %sum.1, %if.then ], [ %0, %for.body ]
136  %iv.next = add nuw nsw i64 %iv, 1
137  %exitcond = icmp eq i64 %iv.next, 1000
138  br i1 %exitcond, label %for.end, label %for.body
139
140for.end:
141  ret void
142}
143
144; Check that we can vectorize code with several stores to an invariant address
145; with condition that final reduction value is stored too.
146;
147;  int sum = 0;
148;  for(int i=0; i < 1000; i+=2) {
149;    sum += src[i];
150;    dst[42] = sum;
151;    sum += src[i+1];
152;    dst[42] = sum;
153;  }
154; CHECK-LABEL: @reduc_store_inside_unrolled
155; CHECK-NOT: vector.body
156define void @reduc_store_inside_unrolled(i32* %dst, i32* readonly %src) {
157entry:
158  %gep.dst = getelementptr inbounds i32, i32* %dst, i64 42
159  br label %for.body
160
161for.body:
162  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
163  %sum = phi i32 [ 0, %entry ], [ %sum.1, %for.body ]
164  %gep.src = getelementptr inbounds i32, i32* %src, i64 %iv
165  %0 = load i32, i32* %gep.src, align 4
166  %sum.1 = add nsw i32 %0, %sum
167  store i32 %sum.1, i32* %gep.dst, align 4
168  %1 = or i64 %iv, 1
169  %gep.src.1 = getelementptr inbounds i32, i32* %src, i64 %1
170  %2 = load i32, i32* %gep.src.1, align 4
171  %sum.2 = add nsw i32 %2, %sum.1
172  store i32 %sum.2, i32* %gep.dst, align 4
173  %iv.next = add nuw nsw i64 %iv, 2
174  %cmp = icmp slt i64 %iv.next, 1000
175  br i1 %cmp, label %for.body, label %exit
176
177exit:
178  ret void
179}
180
181; We cannot vectorize if two (or more) invariant stores exist in a loop.
182;
183;  int sum = 0;
184;  for(int i=0; i < 1000; i+=2) {
185;    sum += src[i];
186;    dst[42] = sum;
187;    sum += src[i+1];
188;    other_dst[42] = sum;
189;  }
190; CHECK-LABEL: @reduc_double_invariant_store
191; CHECK-NOT: vector.body:
192define void @reduc_double_invariant_store(i32* %dst, i32* %other_dst, i32* readonly %src) {
193entry:
194  %gep.dst = getelementptr inbounds i32, i32* %dst, i64 42
195  %gep.other_dst = getelementptr inbounds i32, i32* %other_dst, i64 42
196  br label %for.body
197
198for.body:
199  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
200  %sum = phi i32 [ 0, %entry ], [ %sum.1, %for.body ]
201  %arrayidx = getelementptr inbounds i32, i32* %src, i64 %iv
202  %0 = load i32, i32* %arrayidx, align 4
203  %sum.1 = add nsw i32 %0, %sum
204  store i32 %sum.1, i32* %gep.dst, align 4
205  %1 = or i64 %iv, 1
206  %arrayidx4 = getelementptr inbounds i32, i32* %src, i64 %1
207  %2 = load i32, i32* %arrayidx4, align 4
208  %sum.2 = add nsw i32 %2, %sum.1
209  store i32 %sum.2, i32* %gep.other_dst, align 4
210  %iv.next = add nuw nsw i64 %iv, 2
211  %cmp = icmp slt i64 %iv.next, 1000
212  br i1 %cmp, label %for.body, label %exit
213
214exit:
215  ret void
216}
217
218;  int sum = 0;
219;  for(int i=0; i < 1000; i+=2) {
220;    sum += src[i];
221;    if (src[i+1] > 0)
222;      dst[42] = sum;
223;    sum += src[i+1];
224;    dst[42] = sum;
225;  }
226; CHECK-LABEL: @reduc_store_middle_store_predicated
227; CHECK-NOT: vector.body
228define void @reduc_store_middle_store_predicated(i32* %dst, i32* readonly %src) {
229entry:
230  %gep.dst = getelementptr inbounds i32, i32* %dst, i64 42
231  br label %for.body
232
233for.body:                                         ; preds = %latch, %entry
234  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
235  %sum = phi i32 [ 0, %entry ], [ %sum.2, %latch ]
236  %gep.src = getelementptr inbounds i32, i32* %src, i64 %iv
237  %0 = load i32, i32* %gep.src, align 4
238  %sum.1 = add nsw i32 %0, %sum
239  %cmp = icmp sgt i32 %0, 0
240  br i1 %cmp, label %predicated, label %latch
241
242predicated:                                       ; preds = %for.body
243  store i32 %sum.1, i32* %gep.dst, align 4
244  br label %latch
245
246latch:                                            ; preds = %predicated, %for.body
247  %1 = or i64 %iv, 1
248  %gep.src.1 = getelementptr inbounds i32, i32* %src, i64 %1
249  %2 = load i32, i32* %gep.src.1, align 4
250  %sum.2 = add nsw i32 %2, %sum.1
251  store i32 %sum.2, i32* %gep.dst, align 4
252  %iv.next = add nuw nsw i64 %iv, 2
253  %cmp.1 = icmp slt i64 %iv.next, 1000
254  br i1 %cmp.1, label %for.body, label %exit
255
256exit:                                 ; preds = %latch
257  ret void
258}
259
260;  int sum = 0;
261;  for(int i=0; i < 1000; i+=2) {
262;    sum += src[i];
263;    dst[42] = sum;
264;    sum += src[i+1];
265;    if (src[i+1] > 0)
266;      dst[42] = sum;
267;  }
268; CHECK-LABEL: @reduc_store_final_store_predicated
269; CHECK-NOT: vector.body:
270define void @reduc_store_final_store_predicated(i32* %dst, i32* readonly %src) {
271entry:
272  %gep.dst = getelementptr inbounds i32, i32* %dst, i64 42
273  br label %for.body
274
275for.body:                                         ; preds = %latch, %entry
276  %iv = phi i64 [ 0, %entry ], [ %iv.next, %latch ]
277  %sum = phi i32 [ 0, %entry ], [ %sum.1, %latch ]
278  %arrayidx = getelementptr inbounds i32, i32* %src, i64 %iv
279  %0 = load i32, i32* %arrayidx, align 4
280  %sum.1 = add nsw i32 %0, %sum
281  store i32 %sum.1, i32* %gep.dst, align 4
282  %1 = or i64 %iv, 1
283  %gep.src.1 = getelementptr inbounds i32, i32* %src, i64 %1
284  %2 = load i32, i32* %gep.src.1, align 4
285  %sum.2 = add nsw i32 %2, %sum.1
286  %cmp1 = icmp sgt i32 %2, 0
287  br i1 %cmp1, label %predicated, label %latch
288
289predicated:                                       ; preds = %for.body
290  store i32 %sum.2, i32* %gep.dst, align 4
291  br label %latch
292
293latch:                                            ; preds = %predicated, %for.body
294  %iv.next = add nuw nsw i64 %iv, 2
295  %cmp = icmp slt i64 %iv.next, 1000
296  br i1 %cmp, label %for.body, label %exit
297
298exit:                                 ; preds = %latch
299  ret void
300}
301
302; Final value used outside of loop does not prevent vectorization
303;
304; int sum = 0;
305; for(int i=0; i < 1000; i++) {
306;   sum += src[i];
307;   dst[42] = sum;
308; }
309; dst[43] = sum;
310; CHECK-LABEL: @reduc_store_inoutside
311; CHECK-NOT: vector.body
312define void @reduc_store_inoutside(i32* %dst, i32* readonly %src) {
313entry:
314  %gep.dst = getelementptr inbounds i32, i32* %dst, i64 42
315  br label %for.body
316
317for.body:
318  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.body ]
319  %sum = phi i32 [ 0, %entry ], [ %sum.1, %for.body ]
320  %arrayidx = getelementptr inbounds i32, i32* %src, i64 %iv
321  %0 = load i32, i32* %arrayidx, align 4
322  %sum.1 = add nsw i32 %0, %sum
323  store i32 %sum.1, i32* %gep.dst, align 4
324  %iv.next = add nuw nsw i64 %iv, 1
325  %exitcond = icmp eq i64 %iv.next, 1000
326  br i1 %exitcond, label %exit, label %for.body
327
328exit:
329  %sum.lcssa = phi i32 [ %sum.1, %for.body ]
330  %gep.dst.1 = getelementptr inbounds i32, i32* %dst, i64 43
331  store i32 %sum.lcssa, i32* %gep.dst.1, align 4
332  ret void
333}
334