1; RUN: opt < %s -loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -dce -instcombine -S | FileCheck %s
2; RUN: opt < %s -loop-vectorize -force-vector-width=4 -force-vector-interleave=2 -dce -instcombine -S | FileCheck %s --check-prefix=UNROLL
3; RUN: opt < %s -loop-vectorize -force-vector-width=4 -force-vector-interleave=2 -S | FileCheck %s --check-prefix=UNROLL-NO-IC
4
5target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
6
7; void recurrence_1(int *a, int *b, int n) {
8;   for(int i = 0; i < n; i++)
9;     b[i] =  a[i] + a[i - 1]
10; }
11;
12; CHECK-LABEL: @recurrence_1(
13; CHECK:       vector.ph:
14; CHECK:         %vector.recur.init = insertelement <4 x i32> undef, i32 %pre_load, i32 3
15; CHECK:       vector.body:
16; CHECK:         %vector.recur = phi <4 x i32> [ %vector.recur.init, %vector.ph ], [ [[L1:%[a-zA-Z0-9.]+]], %vector.body ]
17; CHECK:         [[L1]] = load <4 x i32>
18; CHECK:         {{.*}} = shufflevector <4 x i32> %vector.recur, <4 x i32> [[L1]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
19; CHECK:       middle.block:
20; CHECK:         %vector.recur.extract = extractelement <4 x i32> [[L1]], i32 3
21; CHECK:       scalar.ph:
22; CHECK:         %scalar.recur.init = phi i32 [ %vector.recur.extract, %middle.block ], [ %pre_load, %vector.memcheck ], [ %pre_load, %min.iters.checked ], [ %pre_load, %for.preheader ]
23; CHECK:       scalar.body:
24; CHECK:         %scalar.recur = phi i32 [ %scalar.recur.init, %scalar.ph ], [ {{.*}}, %scalar.body ]
25;
26; UNROLL-LABEL: @recurrence_1(
27; UNROLL:       vector.body:
28; UNROLL:         %vector.recur = phi <4 x i32> [ %vector.recur.init, %vector.ph ], [ [[L2:%[a-zA-Z0-9.]+]], %vector.body ]
29; UNROLL:         [[L1:%[a-zA-Z0-9.]+]] = load <4 x i32>
30; UNROLL:         [[L2]] = load <4 x i32>
31; UNROLL:         {{.*}} = shufflevector <4 x i32> %vector.recur, <4 x i32> [[L1]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
32; UNROLL:         {{.*}} = shufflevector <4 x i32> [[L1]], <4 x i32> [[L2]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
33; UNROLL:       middle.block:
34; UNROLL:         %vector.recur.extract = extractelement <4 x i32> [[L2]], i32 3
35;
36define void @recurrence_1(i32* nocapture readonly %a, i32* nocapture %b, i32 %n) {
37entry:
38  br label %for.preheader
39
40for.preheader:
41  %arrayidx.phi.trans.insert = getelementptr inbounds i32, i32* %a, i64 0
42  %pre_load = load i32, i32* %arrayidx.phi.trans.insert
43  br label %scalar.body
44
45scalar.body:
46  %0 = phi i32 [ %pre_load, %for.preheader ], [ %1, %scalar.body ]
47  %indvars.iv = phi i64 [ 0, %for.preheader ], [ %indvars.iv.next, %scalar.body ]
48  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
49  %arrayidx32 = getelementptr inbounds i32, i32* %a, i64 %indvars.iv.next
50  %1 = load i32, i32* %arrayidx32
51  %arrayidx34 = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
52  %add35 = add i32 %1, %0
53  store i32 %add35, i32* %arrayidx34
54  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
55  %exitcond = icmp eq i32 %lftr.wideiv, %n
56  br i1 %exitcond, label %for.exit, label %scalar.body
57
58for.exit:
59  ret void
60}
61
62; int recurrence_2(int *a, int n) {
63;   int minmax;
64;   for (int i = 0; i < n; ++i)
65;     minmax = min(minmax, max(a[i] - a[i-1], 0));
66;   return minmax;
67; }
68;
69; CHECK-LABEL: @recurrence_2(
70; CHECK:       vector.ph:
71; CHECK:         %vector.recur.init = insertelement <4 x i32> undef, i32 %.pre, i32 3
72; CHECK:       vector.body:
73; CHECK:         %vector.recur = phi <4 x i32> [ %vector.recur.init, %vector.ph ], [ [[L1:%[a-zA-Z0-9.]+]], %vector.body ]
74; CHECK:         [[L1]] = load <4 x i32>
75; CHECK:         {{.*}} = shufflevector <4 x i32> %vector.recur, <4 x i32> [[L1]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
76; CHECK:       middle.block:
77; CHECK:         %vector.recur.extract = extractelement <4 x i32> [[L1]], i32 3
78; CHECK:       scalar.ph:
79; CHECK:         %scalar.recur.init = phi i32 [ %vector.recur.extract, %middle.block ], [ %.pre, %min.iters.checked ], [ %.pre, %for.preheader ]
80; CHECK:       scalar.body:
81; CHECK:         %scalar.recur = phi i32 [ %scalar.recur.init, %scalar.ph ], [ {{.*}}, %scalar.body ]
82;
83; UNROLL-LABEL: @recurrence_2(
84; UNROLL:       vector.body:
85; UNROLL:         %vector.recur = phi <4 x i32> [ %vector.recur.init, %vector.ph ], [ [[L2:%[a-zA-Z0-9.]+]], %vector.body ]
86; UNROLL:         [[L1:%[a-zA-Z0-9.]+]] = load <4 x i32>
87; UNROLL:         [[L2]] = load <4 x i32>
88; UNROLL:         {{.*}} = shufflevector <4 x i32> %vector.recur, <4 x i32> [[L1]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
89; UNROLL:         {{.*}} = shufflevector <4 x i32> [[L1]], <4 x i32> [[L2]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
90; UNROLL:       middle.block:
91; UNROLL:         %vector.recur.extract = extractelement <4 x i32> [[L2]], i32 3
92;
93define i32 @recurrence_2(i32* nocapture readonly %a, i32 %n) {
94entry:
95  %cmp27 = icmp sgt i32 %n, 0
96  br i1 %cmp27, label %for.preheader, label %for.cond.cleanup
97
98for.preheader:
99  %arrayidx2.phi.trans.insert = getelementptr inbounds i32, i32* %a, i64 -1
100  %.pre = load i32, i32* %arrayidx2.phi.trans.insert, align 4
101  br label %scalar.body
102
103for.cond.cleanup.loopexit:
104  %minmax.0.cond.lcssa = phi i32 [ %minmax.0.cond, %scalar.body ]
105  br label %for.cond.cleanup
106
107for.cond.cleanup:
108  %minmax.0.lcssa = phi i32 [ undef, %entry ], [ %minmax.0.cond.lcssa, %for.cond.cleanup.loopexit ]
109  ret i32 %minmax.0.lcssa
110
111scalar.body:
112  %0 = phi i32 [ %.pre, %for.preheader ], [ %1, %scalar.body ]
113  %indvars.iv = phi i64 [ 0, %for.preheader ], [ %indvars.iv.next, %scalar.body ]
114  %minmax.028 = phi i32 [ undef, %for.preheader ], [ %minmax.0.cond, %scalar.body ]
115  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %indvars.iv
116  %1 = load i32, i32* %arrayidx, align 4
117  %sub3 = sub nsw i32 %1, %0
118  %cmp4 = icmp sgt i32 %sub3, 0
119  %cond = select i1 %cmp4, i32 %sub3, i32 0
120  %cmp5 = icmp slt i32 %minmax.028, %cond
121  %minmax.0.cond = select i1 %cmp5, i32 %minmax.028, i32 %cond
122  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
123  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
124  %exitcond = icmp eq i32 %lftr.wideiv, %n
125  br i1 %exitcond, label %for.cond.cleanup.loopexit, label %scalar.body
126}
127
128; void recurrence_3(short *a, double *b, int n, float f, short p) {
129;   b[0] = (double)a[0] - f * (double)p;
130;   for (int i = 1; i < n; i++)
131;     b[i] = (double)a[i] - f * (double)a[i - 1];
132; }
133;
134; CHECK-LABEL: @recurrence_3(
135; CHECK:       vector.ph:
136; CHECK:         %vector.recur.init = insertelement <4 x i16> undef, i16 %0, i32 3
137; CHECK:       vector.body:
138; CHECK:         %vector.recur = phi <4 x i16> [ %vector.recur.init, %vector.ph ], [ [[L1:%[a-zA-Z0-9.]+]], %vector.body ]
139; CHECK:         [[L1]] = load <4 x i16>
140; CHECK:         {{.*}} = shufflevector <4 x i16> %vector.recur, <4 x i16> [[L1]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
141; CHECK:       middle.block:
142; CHECK:         %vector.recur.extract = extractelement <4 x i16> [[L1]], i32 3
143; CHECK:       scalar.ph:
144; CHECK:         %scalar.recur.init = phi i16 [ %vector.recur.extract, %middle.block ], [ %0, %vector.memcheck ], [ %0, %min.iters.checked ], [ %0, %for.preheader ]
145; CHECK:       scalar.body:
146; CHECK:         %scalar.recur = phi i16 [ %scalar.recur.init, %scalar.ph ], [ {{.*}}, %scalar.body ]
147;
148; UNROLL-LABEL: @recurrence_3(
149; UNROLL:       vector.body:
150; UNROLL:         %vector.recur = phi <4 x i16> [ %vector.recur.init, %vector.ph ], [ [[L2:%[a-zA-Z0-9.]+]], %vector.body ]
151; UNROLL:         [[L1:%[a-zA-Z0-9.]+]] = load <4 x i16>
152; UNROLL:         [[L2]] = load <4 x i16>
153; UNROLL:         {{.*}} = shufflevector <4 x i16> %vector.recur, <4 x i16> [[L1]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
154; UNROLL:         {{.*}} = shufflevector <4 x i16> [[L1]], <4 x i16> [[L2]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
155; UNROLL:       middle.block:
156; UNROLL:         %vector.recur.extract = extractelement <4 x i16> [[L2]], i32 3
157;
158define void @recurrence_3(i16* nocapture readonly %a, double* nocapture %b, i32 %n, float %f, i16 %p) {
159entry:
160  %0 = load i16, i16* %a, align 2
161  %conv = sitofp i16 %0 to double
162  %conv1 = fpext float %f to double
163  %conv2 = sitofp i16 %p to double
164  %mul = fmul fast double %conv2, %conv1
165  %sub = fsub fast double %conv, %mul
166  store double %sub, double* %b, align 8
167  %cmp25 = icmp sgt i32 %n, 1
168  br i1 %cmp25, label %for.preheader, label %for.end
169
170for.preheader:
171  br label %scalar.body
172
173scalar.body:
174  %1 = phi i16 [ %0, %for.preheader ], [ %2, %scalar.body ]
175  %advars.iv = phi i64 [ %advars.iv.next, %scalar.body ], [ 1, %for.preheader ]
176  %arrayidx5 = getelementptr inbounds i16, i16* %a, i64 %advars.iv
177  %2 = load i16, i16* %arrayidx5, align 2
178  %conv6 = sitofp i16 %2 to double
179  %conv11 = sitofp i16 %1 to double
180  %mul12 = fmul fast double %conv11, %conv1
181  %sub13 = fsub fast double %conv6, %mul12
182  %arrayidx15 = getelementptr inbounds double, double* %b, i64 %advars.iv
183  store double %sub13, double* %arrayidx15, align 8
184  %advars.iv.next = add nuw nsw i64 %advars.iv, 1
185  %lftr.wideiv = trunc i64 %advars.iv.next to i32
186  %exitcond = icmp eq i32 %lftr.wideiv, %n
187  br i1 %exitcond, label %for.end.loopexit, label %scalar.body
188
189for.end.loopexit:
190  br label %for.end
191
192for.end:
193  ret void
194}
195
196; void PR26734(short *a, int *b, int *c, int d, short *e) {
197;   for (; d != 21; d++) {
198;     *b &= *c;
199;     *e = *a - 6;
200;     *c = *e;
201;   }
202; }
203;
204; CHECK-LABEL: @PR26734(
205; CHECK-NOT:   vector.ph:
206; CHECK:       }
207;
208define void @PR26734(i16* %a, i32* %b, i32* %c, i32 %d, i16* %e) {
209entry:
210  %cmp4 = icmp eq i32 %d, 21
211  br i1 %cmp4, label %entry.for.end_crit_edge, label %for.body.lr.ph
212
213entry.for.end_crit_edge:
214  %.pre = load i32, i32* %b, align 4
215  br label %for.end
216
217for.body.lr.ph:
218  %0 = load i16, i16* %a, align 2
219  %sub = add i16 %0, -6
220  %conv2 = sext i16 %sub to i32
221  %c.promoted = load i32, i32* %c, align 4
222  %b.promoted = load i32, i32* %b, align 4
223  br label %for.body
224
225for.body:
226  %inc7 = phi i32 [ %d, %for.body.lr.ph ], [ %inc, %for.body ]
227  %and6 = phi i32 [ %b.promoted, %for.body.lr.ph ], [ %and, %for.body ]
228  %conv25 = phi i32 [ %c.promoted, %for.body.lr.ph ], [ %conv2, %for.body ]
229  %and = and i32 %and6, %conv25
230  %inc = add nsw i32 %inc7, 1
231  %cmp = icmp eq i32 %inc, 21
232  br i1 %cmp, label %for.cond.for.end_crit_edge, label %for.body
233
234for.cond.for.end_crit_edge:
235  %and.lcssa = phi i32 [ %and, %for.body ]
236  store i32 %conv2, i32* %c, align 4
237  store i32 %and.lcssa, i32* %b, align 4
238  store i16 %sub, i16* %e, align 2
239  br label %for.end
240
241for.end:
242  ret void
243}
244
245; int PR27246() {
246;   unsigned int e, n;
247;   for (int i = 1; i < 49; ++i) {
248;     for (int k = i; k > 1; --k)
249;       e = k;
250;     n = e;
251;   }
252;   return n;
253; }
254;
255; CHECK-LABEL: @PR27246(
256; CHECK-NOT:   vector.ph:
257; CHECK:       }
258;
259define i32 @PR27246() {
260entry:
261  br label %for.cond1.preheader
262
263for.cond1.preheader:
264  %i.016 = phi i32 [ 1, %entry ], [ %inc, %for.cond.cleanup3 ]
265  %e.015 = phi i32 [ undef, %entry ], [ %e.1.lcssa, %for.cond.cleanup3 ]
266  br label %for.cond1
267
268for.cond.cleanup:
269  %e.1.lcssa.lcssa = phi i32 [ %e.1.lcssa, %for.cond.cleanup3 ]
270  ret i32 %e.1.lcssa.lcssa
271
272for.cond1:
273  %e.1 = phi i32 [ %k.0, %for.cond1 ], [ %e.015, %for.cond1.preheader ]
274  %k.0 = phi i32 [ %dec, %for.cond1 ], [ %i.016, %for.cond1.preheader ]
275  %cmp2 = icmp sgt i32 %k.0, 1
276  %dec = add nsw i32 %k.0, -1
277  br i1 %cmp2, label %for.cond1, label %for.cond.cleanup3
278
279for.cond.cleanup3:
280  %e.1.lcssa = phi i32 [ %e.1, %for.cond1 ]
281  %inc = add nuw nsw i32 %i.016, 1
282  %exitcond = icmp eq i32 %inc, 49
283  br i1 %exitcond, label %for.cond.cleanup, label %for.cond1.preheader
284}
285
286; UNROLL-NO-IC-LABEL: @PR30183(
287; UNROLL-NO-IC:       vector.ph:
288; UNROLL-NO-IC-NEXT:    [[VECTOR_RECUR_INIT:%.*]] = insertelement <4 x i32> undef, i32 [[PRE_LOAD:%.*]], i32 3
289; UNROLL-NO-IC-NEXT:    br label %vector.body
290; UNROLL-NO-IC:       vector.body:
291; UNROLL-NO-IC-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
292; UNROLL-NO-IC-NEXT:    [[VECTOR_RECUR:%.*]] = phi <4 x i32> [ [[VECTOR_RECUR_INIT]], %vector.ph ], [ [[TMP42:%.*]], %vector.body ]
293; UNROLL-NO-IC:         [[TMP27:%.*]] = load i32, i32* {{.*}}
294; UNROLL-NO-IC-NEXT:    [[TMP28:%.*]] = load i32, i32* {{.*}}
295; UNROLL-NO-IC-NEXT:    [[TMP29:%.*]] = load i32, i32* {{.*}}
296; UNROLL-NO-IC-NEXT:    [[TMP30:%.*]] = load i32, i32* {{.*}}
297; UNROLL-NO-IC-NEXT:    [[TMP31:%.*]] = load i32, i32* {{.*}}
298; UNROLL-NO-IC-NEXT:    [[TMP32:%.*]] = load i32, i32* {{.*}}
299; UNROLL-NO-IC-NEXT:    [[TMP33:%.*]] = load i32, i32* {{.*}}
300; UNROLL-NO-IC-NEXT:    [[TMP34:%.*]] = load i32, i32* {{.*}}
301; UNROLL-NO-IC-NEXT:    [[TMP35:%.*]] = insertelement <4 x i32> undef, i32 [[TMP27]], i32 0
302; UNROLL-NO-IC-NEXT:    [[TMP36:%.*]] = insertelement <4 x i32> [[TMP35]], i32 [[TMP28]], i32 1
303; UNROLL-NO-IC-NEXT:    [[TMP37:%.*]] = insertelement <4 x i32> [[TMP36]], i32 [[TMP29]], i32 2
304; UNROLL-NO-IC-NEXT:    [[TMP38:%.*]] = insertelement <4 x i32> [[TMP37]], i32 [[TMP30]], i32 3
305; UNROLL-NO-IC-NEXT:    [[TMP39:%.*]] = insertelement <4 x i32> undef, i32 [[TMP31]], i32 0
306; UNROLL-NO-IC-NEXT:    [[TMP40:%.*]] = insertelement <4 x i32> [[TMP39]], i32 [[TMP32]], i32 1
307; UNROLL-NO-IC-NEXT:    [[TMP41:%.*]] = insertelement <4 x i32> [[TMP40]], i32 [[TMP33]], i32 2
308; UNROLL-NO-IC-NEXT:    [[TMP42]] = insertelement <4 x i32> [[TMP41]], i32 [[TMP34]], i32 3
309; UNROLL-NO-IC-NEXT:    [[TMP43:%.*]] = shufflevector <4 x i32> [[VECTOR_RECUR]], <4 x i32> [[TMP38]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
310; UNROLL-NO-IC-NEXT:    [[TMP44:%.*]] = shufflevector <4 x i32> [[TMP38]], <4 x i32> [[TMP42]], <4 x i32> <i32 3, i32 4, i32 5, i32 6>
311; UNROLL-NO-IC-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 8
312; UNROLL-NO-IC:         br i1 {{.*}}, label %middle.block, label %vector.body
313;
314define void @PR30183(i32 %pre_load, i32* %a, i32* %b, i64 %n) {
315entry:
316  br label %scalar.body
317
318scalar.body:
319  %i = phi i64 [ 0, %entry ], [ %i.next, %scalar.body ]
320  %tmp0 = phi i32 [ %pre_load, %entry ], [ %tmp2, %scalar.body ]
321  %i.next = add nuw nsw i64 %i, 2
322  %tmp1 = getelementptr inbounds i32, i32* %a, i64 %i.next
323  %tmp2 = load i32, i32* %tmp1
324  %cond = icmp eq i64 %i.next,%n
325  br i1 %cond, label %for.end, label %scalar.body
326
327for.end:
328  ret void
329}
330
331; UNROLL-NO-IC-LABEL: @constant_folded_previous_value(
332; UNROLL-NO-IC:       vector.body:
333; UNROLL-NO-IC:         [[VECTOR_RECUR:%.*]] = phi <4 x i64> [ <i64 undef, i64 undef, i64 undef, i64 0>, %vector.ph ], [ <i64 1, i64 1, i64 1, i64 1>, %vector.body ]
334; UNROLL-NO-IC-NEXT:    [[TMP0:%.*]] = shufflevector <4 x i64> [[VECTOR_RECUR]], <4 x i64> <i64 1, i64 1, i64 1, i64 1>, <4 x i32> <i32 3, i32 4, i32 5, i32 6>
335; UNROLL-NO-IC:         br i1 {{.*}}, label %middle.block, label %vector.body
336;
337define void @constant_folded_previous_value() {
338entry:
339  br label %scalar.body
340
341scalar.body:
342  %i = phi i64 [ 0, %entry ], [ %i.next, %scalar.body ]
343  %tmp2 = phi i64 [ 0, %entry ], [ %tmp3, %scalar.body ]
344  %tmp3 = add i64 0, 1
345  %i.next = add nuw nsw i64 %i, 1
346  %cond = icmp eq i64 %i.next, undef
347  br i1 %cond, label %for.end, label %scalar.body
348
349for.end:
350  ret void
351}
352
353; FIXME: we can vectorize this first order recurrence, by generating two
354; extracts - one for the phi `val.phi` and other for the phi update `addx`.
355; val.phi at end of loop is 94 + x.
356; CHECK-LABEL: extract_second_last_iteration
357; CHECK-NOT: vector.body
358define i32 @extract_second_last_iteration(i32* %cval, i32 %x)  {
359entry:
360  br label %for.body
361
362for.body:
363  %inc.phi = phi i32 [ 0, %entry ], [ %inc, %for.body ]
364  %val.phi = phi i32 [ 0, %entry ], [ %addx, %for.body ]
365  %inc = add i32 %inc.phi, 1
366  %bc = zext i32 %inc.phi to i64
367  %addx = add i32 %inc.phi, %x
368  %cmp = icmp eq i32 %inc.phi, 95
369  br i1 %cmp, label %for.end, label %for.body
370
371for.end:
372  ret i32 %val.phi
373}
374