1; RUN: llc < %s -O3 -march=x86-64 -mcpu=core2 | FileCheck %s -check-prefix=X64
2; RUN: llc < %s -O3 -march=x86 -mcpu=core2 | FileCheck %s -check-prefix=X32
3; RUN: llc < %s -O3 -march=x86-64 -mcpu=core2 -addr-sink-using-gep=1 | FileCheck %s -check-prefix=X64
4; RUN: llc < %s -O3 -march=x86 -mcpu=core2 -addr-sink-using-gep=1 | FileCheck %s -check-prefix=X32
5
6; @simple is the most basic chain of address induction variables. Chaining
7; saves at least one register and avoids complex addressing and setup
8; code.
9;
10; X64: @simple
11; %x * 4
12; X64: shlq $2
13; no other address computation in the preheader
14; X64-NEXT: xorl
15; X64-NEXT: .align
16; X64: %loop
17; no complex address modes
18; X64-NOT: (%{{[^)]+}},%{{[^)]+}},
19;
20; X32: @simple
21; no expensive address computation in the preheader
22; X32-NOT: imul
23; X32: %loop
24; no complex address modes
25; X32-NOT: (%{{[^)]+}},%{{[^)]+}},
26define i32 @simple(i32* %a, i32* %b, i32 %x) nounwind {
27entry:
28  br label %loop
29loop:
30  %iv = phi i32* [ %a, %entry ], [ %iv4, %loop ]
31  %s = phi i32 [ 0, %entry ], [ %s4, %loop ]
32  %v = load i32, i32* %iv
33  %iv1 = getelementptr inbounds i32, i32* %iv, i32 %x
34  %v1 = load i32, i32* %iv1
35  %iv2 = getelementptr inbounds i32, i32* %iv1, i32 %x
36  %v2 = load i32, i32* %iv2
37  %iv3 = getelementptr inbounds i32, i32* %iv2, i32 %x
38  %v3 = load i32, i32* %iv3
39  %s1 = add i32 %s, %v
40  %s2 = add i32 %s1, %v1
41  %s3 = add i32 %s2, %v2
42  %s4 = add i32 %s3, %v3
43  %iv4 = getelementptr inbounds i32, i32* %iv3, i32 %x
44  %cmp = icmp eq i32* %iv4, %b
45  br i1 %cmp, label %exit, label %loop
46exit:
47  ret i32 %s4
48}
49
50; @user is not currently chained because the IV is live across memory ops.
51;
52; X64: @user
53; X64: shlq $4
54; X64: lea
55; X64: lea
56; X64: %loop
57; complex address modes
58; X64: (%{{[^)]+}},%{{[^)]+}},
59;
60; X32: @user
61; expensive address computation in the preheader
62; X32: shll $4
63; X32: lea
64; X32: lea
65; X32: %loop
66; complex address modes
67; X32: (%{{[^)]+}},%{{[^)]+}},
68define i32 @user(i32* %a, i32* %b, i32 %x) nounwind {
69entry:
70  br label %loop
71loop:
72  %iv = phi i32* [ %a, %entry ], [ %iv4, %loop ]
73  %s = phi i32 [ 0, %entry ], [ %s4, %loop ]
74  %v = load i32, i32* %iv
75  %iv1 = getelementptr inbounds i32, i32* %iv, i32 %x
76  %v1 = load i32, i32* %iv1
77  %iv2 = getelementptr inbounds i32, i32* %iv1, i32 %x
78  %v2 = load i32, i32* %iv2
79  %iv3 = getelementptr inbounds i32, i32* %iv2, i32 %x
80  %v3 = load i32, i32* %iv3
81  %s1 = add i32 %s, %v
82  %s2 = add i32 %s1, %v1
83  %s3 = add i32 %s2, %v2
84  %s4 = add i32 %s3, %v3
85  %iv4 = getelementptr inbounds i32, i32* %iv3, i32 %x
86  store i32 %s4, i32* %iv
87  %cmp = icmp eq i32* %iv4, %b
88  br i1 %cmp, label %exit, label %loop
89exit:
90  ret i32 %s4
91}
92
93; @extrastride is a slightly more interesting case of a single
94; complete chain with multiple strides. The test case IR is what LSR
95; used to do, and exactly what we don't want to do. LSR's new IV
96; chaining feature should now undo the damage.
97;
98; X64: extrastride:
99; We currently don't handle this on X64 because the sexts cause
100; strange increment expressions like this:
101; IV + ((sext i32 (2 * %s) to i64) + (-1 * (sext i32 %s to i64)))
102;
103; X32: extrastride:
104; no spills in the preheader
105; X32-NOT: mov{{.*}}(%esp){{$}}
106; X32: %for.body{{$}}
107; no complex address modes
108; X32-NOT: (%{{[^)]+}},%{{[^)]+}},
109; no reloads
110; X32-NOT: (%esp)
111define void @extrastride(i8* nocapture %main, i32 %main_stride, i32* nocapture %res, i32 %x, i32 %y, i32 %z) nounwind {
112entry:
113  %cmp8 = icmp eq i32 %z, 0
114  br i1 %cmp8, label %for.end, label %for.body.lr.ph
115
116for.body.lr.ph:                                   ; preds = %entry
117  %add.ptr.sum = shl i32 %main_stride, 1 ; s*2
118  %add.ptr1.sum = add i32 %add.ptr.sum, %main_stride ; s*3
119  %add.ptr2.sum = add i32 %x, %main_stride ; s + x
120  %add.ptr4.sum = shl i32 %main_stride, 2 ; s*4
121  %add.ptr3.sum = add i32 %add.ptr2.sum, %add.ptr4.sum ; total IV stride = s*5+x
122  br label %for.body
123
124for.body:                                         ; preds = %for.body.lr.ph, %for.body
125  %main.addr.011 = phi i8* [ %main, %for.body.lr.ph ], [ %add.ptr6, %for.body ]
126  %i.010 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
127  %res.addr.09 = phi i32* [ %res, %for.body.lr.ph ], [ %add.ptr7, %for.body ]
128  %0 = bitcast i8* %main.addr.011 to i32*
129  %1 = load i32, i32* %0, align 4
130  %add.ptr = getelementptr inbounds i8, i8* %main.addr.011, i32 %main_stride
131  %2 = bitcast i8* %add.ptr to i32*
132  %3 = load i32, i32* %2, align 4
133  %add.ptr1 = getelementptr inbounds i8, i8* %main.addr.011, i32 %add.ptr.sum
134  %4 = bitcast i8* %add.ptr1 to i32*
135  %5 = load i32, i32* %4, align 4
136  %add.ptr2 = getelementptr inbounds i8, i8* %main.addr.011, i32 %add.ptr1.sum
137  %6 = bitcast i8* %add.ptr2 to i32*
138  %7 = load i32, i32* %6, align 4
139  %add.ptr3 = getelementptr inbounds i8, i8* %main.addr.011, i32 %add.ptr4.sum
140  %8 = bitcast i8* %add.ptr3 to i32*
141  %9 = load i32, i32* %8, align 4
142  %add = add i32 %3, %1
143  %add4 = add i32 %add, %5
144  %add5 = add i32 %add4, %7
145  %add6 = add i32 %add5, %9
146  store i32 %add6, i32* %res.addr.09, align 4
147  %add.ptr6 = getelementptr inbounds i8, i8* %main.addr.011, i32 %add.ptr3.sum
148  %add.ptr7 = getelementptr inbounds i32, i32* %res.addr.09, i32 %y
149  %inc = add i32 %i.010, 1
150  %cmp = icmp eq i32 %inc, %z
151  br i1 %cmp, label %for.end, label %for.body
152
153for.end:                                          ; preds = %for.body, %entry
154  ret void
155}
156
157; @foldedidx is an unrolled variant of this loop:
158;  for (unsigned long i = 0; i < len; i += s) {
159;    c[i] = a[i] + b[i];
160;  }
161; where 's' can be folded into the addressing mode.
162; Consequently, we should *not* form any chains.
163;
164; X64: foldedidx:
165; X64: movzbl -3(
166;
167; X32: foldedidx:
168; X32: movzbl -3(
169define void @foldedidx(i8* nocapture %a, i8* nocapture %b, i8* nocapture %c) nounwind ssp {
170entry:
171  br label %for.body
172
173for.body:                                         ; preds = %for.body, %entry
174  %i.07 = phi i32 [ 0, %entry ], [ %inc.3, %for.body ]
175  %arrayidx = getelementptr inbounds i8, i8* %a, i32 %i.07
176  %0 = load i8, i8* %arrayidx, align 1
177  %conv5 = zext i8 %0 to i32
178  %arrayidx1 = getelementptr inbounds i8, i8* %b, i32 %i.07
179  %1 = load i8, i8* %arrayidx1, align 1
180  %conv26 = zext i8 %1 to i32
181  %add = add nsw i32 %conv26, %conv5
182  %conv3 = trunc i32 %add to i8
183  %arrayidx4 = getelementptr inbounds i8, i8* %c, i32 %i.07
184  store i8 %conv3, i8* %arrayidx4, align 1
185  %inc1 = or i32 %i.07, 1
186  %arrayidx.1 = getelementptr inbounds i8, i8* %a, i32 %inc1
187  %2 = load i8, i8* %arrayidx.1, align 1
188  %conv5.1 = zext i8 %2 to i32
189  %arrayidx1.1 = getelementptr inbounds i8, i8* %b, i32 %inc1
190  %3 = load i8, i8* %arrayidx1.1, align 1
191  %conv26.1 = zext i8 %3 to i32
192  %add.1 = add nsw i32 %conv26.1, %conv5.1
193  %conv3.1 = trunc i32 %add.1 to i8
194  %arrayidx4.1 = getelementptr inbounds i8, i8* %c, i32 %inc1
195  store i8 %conv3.1, i8* %arrayidx4.1, align 1
196  %inc.12 = or i32 %i.07, 2
197  %arrayidx.2 = getelementptr inbounds i8, i8* %a, i32 %inc.12
198  %4 = load i8, i8* %arrayidx.2, align 1
199  %conv5.2 = zext i8 %4 to i32
200  %arrayidx1.2 = getelementptr inbounds i8, i8* %b, i32 %inc.12
201  %5 = load i8, i8* %arrayidx1.2, align 1
202  %conv26.2 = zext i8 %5 to i32
203  %add.2 = add nsw i32 %conv26.2, %conv5.2
204  %conv3.2 = trunc i32 %add.2 to i8
205  %arrayidx4.2 = getelementptr inbounds i8, i8* %c, i32 %inc.12
206  store i8 %conv3.2, i8* %arrayidx4.2, align 1
207  %inc.23 = or i32 %i.07, 3
208  %arrayidx.3 = getelementptr inbounds i8, i8* %a, i32 %inc.23
209  %6 = load i8, i8* %arrayidx.3, align 1
210  %conv5.3 = zext i8 %6 to i32
211  %arrayidx1.3 = getelementptr inbounds i8, i8* %b, i32 %inc.23
212  %7 = load i8, i8* %arrayidx1.3, align 1
213  %conv26.3 = zext i8 %7 to i32
214  %add.3 = add nsw i32 %conv26.3, %conv5.3
215  %conv3.3 = trunc i32 %add.3 to i8
216  %arrayidx4.3 = getelementptr inbounds i8, i8* %c, i32 %inc.23
217  store i8 %conv3.3, i8* %arrayidx4.3, align 1
218  %inc.3 = add nsw i32 %i.07, 4
219  %exitcond.3 = icmp eq i32 %inc.3, 400
220  br i1 %exitcond.3, label %for.end, label %for.body
221
222for.end:                                          ; preds = %for.body
223  ret void
224}
225
226; @multioper tests instructions with multiple IV user operands. We
227; should be able to chain them independent of each other.
228;
229; X64: @multioper
230; X64: %for.body
231; X64: movl %{{.*}},4)
232; X64-NEXT: leal 1(
233; X64-NEXT: movl %{{.*}},4)
234; X64-NEXT: leal 2(
235; X64-NEXT: movl %{{.*}},4)
236; X64-NEXT: leal 3(
237; X64-NEXT: movl %{{.*}},4)
238;
239; X32: @multioper
240; X32: %for.body
241; X32: movl %{{.*}},4)
242; X32-NEXT: leal 1(
243; X32-NEXT: movl %{{.*}},4)
244; X32-NEXT: leal 2(
245; X32-NEXT: movl %{{.*}},4)
246; X32-NEXT: leal 3(
247; X32-NEXT: movl %{{.*}},4)
248define void @multioper(i32* %a, i32 %n) nounwind {
249entry:
250  br label %for.body
251
252for.body:
253  %p = phi i32* [ %p.next, %for.body ], [ %a, %entry ]
254  %i = phi i32 [ %inc4, %for.body ], [ 0, %entry ]
255  store i32 %i, i32* %p, align 4
256  %inc1 = or i32 %i, 1
257  %add.ptr.i1 = getelementptr inbounds i32, i32* %p, i32 1
258  store i32 %inc1, i32* %add.ptr.i1, align 4
259  %inc2 = add nsw i32 %i, 2
260  %add.ptr.i2 = getelementptr inbounds i32, i32* %p, i32 2
261  store i32 %inc2, i32* %add.ptr.i2, align 4
262  %inc3 = add nsw i32 %i, 3
263  %add.ptr.i3 = getelementptr inbounds i32, i32* %p, i32 3
264  store i32 %inc3, i32* %add.ptr.i3, align 4
265  %p.next = getelementptr inbounds i32, i32* %p, i32 4
266  %inc4 = add nsw i32 %i, 4
267  %cmp = icmp slt i32 %inc4, %n
268  br i1 %cmp, label %for.body, label %exit
269
270exit:
271  ret void
272}
273
274; @testCmpZero has a ICmpZero LSR use that should not be hidden from
275; LSR. Profitable chains should have more than one nonzero increment
276; anyway.
277;
278; X32: @testCmpZero
279; X32: %for.body82.us
280; X32: dec
281; X32: jne
282define void @testCmpZero(i8* %src, i8* %dst, i32 %srcidx, i32 %dstidx, i32 %len) nounwind ssp {
283entry:
284  %dest0 = getelementptr inbounds i8, i8* %src, i32 %srcidx
285  %source0 = getelementptr inbounds i8, i8* %dst, i32 %dstidx
286  %add.ptr79.us.sum = add i32 %srcidx, %len
287  %lftr.limit = getelementptr i8, i8* %src, i32 %add.ptr79.us.sum
288  br label %for.body82.us
289
290for.body82.us:
291  %dest = phi i8* [ %dest0, %entry ], [ %incdec.ptr91.us, %for.body82.us ]
292  %source = phi i8* [ %source0, %entry ], [ %add.ptr83.us, %for.body82.us ]
293  %0 = bitcast i8* %source to i32*
294  %1 = load i32, i32* %0, align 4
295  %trunc = trunc i32 %1 to i8
296  %add.ptr83.us = getelementptr inbounds i8, i8* %source, i32 4
297  %incdec.ptr91.us = getelementptr inbounds i8, i8* %dest, i32 1
298  store i8 %trunc, i8* %dest, align 1
299  %exitcond = icmp eq i8* %incdec.ptr91.us, %lftr.limit
300  br i1 %exitcond, label %return, label %for.body82.us
301
302return:
303  ret void
304}
305