1; RUN: opt < %s -indvars -S | FileCheck %s
2;
3; Make sure that indvars can perform LFTR without a canonical IV.
4
5target 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"
6
7; Perform LFTR using the original pointer-type IV.
8
9declare void @use(double %x)
10
11;  for(char* p = base; p < base + n; ++p) {
12;    *p = p-base;
13;  }
14define void @ptriv(i8* %base, i32 %n) nounwind {
15entry:
16  %idx.ext = sext i32 %n to i64
17  %add.ptr = getelementptr inbounds i8, i8* %base, i64 %idx.ext
18  %cmp1 = icmp ult i8* %base, %add.ptr
19  br i1 %cmp1, label %for.body, label %for.end
20
21; CHECK: for.body:
22; CHECK: phi i8*
23; CHECK-NOT: phi
24; CHECK-NOT: add
25; CHECK: icmp ne i8*
26; CHECK: br i1
27for.body:
28  %p.02 = phi i8* [ %base, %entry ], [ %incdec.ptr, %for.body ]
29  ; cruft to make the IV useful
30  %sub.ptr.lhs.cast = ptrtoint i8* %p.02 to i64
31  %sub.ptr.rhs.cast = ptrtoint i8* %base to i64
32  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
33  %conv = trunc i64 %sub.ptr.sub to i8
34  store i8 %conv, i8* %p.02
35  %incdec.ptr = getelementptr inbounds i8, i8* %p.02, i32 1
36  %cmp = icmp ult i8* %incdec.ptr, %add.ptr
37  br i1 %cmp, label %for.body, label %for.end
38
39for.end:
40  ret void
41}
42
43; This test checks that SCEVExpander can handle an outer loop that has been
44; simplified, and as a result the inner loop's exit test will be rewritten.
45define void @expandOuterRecurrence(i32 %arg) nounwind {
46entry:
47  %sub1 = sub nsw i32 %arg, 1
48  %cmp1 = icmp slt i32 0, %sub1
49  br i1 %cmp1, label %outer, label %exit
50
51; CHECK: outer:
52; CHECK: icmp slt
53outer:
54  %i = phi i32 [ 0, %entry ], [ %i.inc, %outer.inc ]
55  %sub2 = sub nsw i32 %arg, %i
56  %sub3 = sub nsw i32 %sub2, 1
57  %cmp2 = icmp slt i32 0, %sub3
58  br i1 %cmp2, label %inner.ph, label %outer.inc
59
60inner.ph:
61  br label %inner
62
63; CHECK: inner:
64; CHECK: br i1
65inner:
66  %j = phi i32 [ 0, %inner.ph ], [ %j.inc, %inner ]
67  %j.inc = add nsw i32 %j, 1
68  %cmp3 = icmp slt i32 %j.inc, %sub3
69  br i1 %cmp3, label %inner, label %outer.inc
70
71; CHECK: outer.inc:
72; CHECK: icmp ne
73; CHECK: br i1
74outer.inc:
75  %i.inc = add nsw i32 %i, 1
76  %cmp4 = icmp slt i32 %i.inc, %sub1
77  br i1 %cmp4, label %outer, label %exit
78
79exit:
80  ret void
81}
82
83; Force SCEVExpander to look for an existing well-formed phi.
84; Perform LFTR without generating extra preheader code.
85define void @guardedloop([0 x double]* %matrix, [0 x double]* %vector,
86                         i32 %irow, i32 %ilead) nounwind {
87; CHECK: entry:
88; CHECK-NOT: zext
89; CHECK-NOT: add
90; CHECK: loop:
91; CHECK: phi i64
92; CHECK: phi i64
93; CHECK-NOT: phi
94; CHECK: icmp ne
95; CHECK: br i1
96entry:
97  %cmp = icmp slt i32 1, %irow
98  br i1 %cmp, label %loop, label %return
99
100loop:
101  %rowidx = phi i32 [ 0, %entry ], [ %row.inc, %loop ]
102  %i = phi i32 [ 0, %entry ], [ %i.inc, %loop ]
103  %diagidx = add nsw i32 %rowidx, %i
104  %diagidxw = sext i32 %diagidx to i64
105  %matrixp = getelementptr inbounds [0 x double], [0 x double]* %matrix, i32 0, i64 %diagidxw
106  %v1 = load double, double* %matrixp
107  call void @use(double %v1)
108  %iw = sext i32 %i to i64
109  %vectorp = getelementptr inbounds [0 x double], [0 x double]* %vector, i32 0, i64 %iw
110  %v2 = load double, double* %vectorp
111  call void @use(double %v2)
112  %row.inc = add nsw i32 %rowidx, %ilead
113  %i.inc = add nsw i32 %i, 1
114  %cmp196 = icmp slt i32 %i.inc, %irow
115  br i1 %cmp196, label %loop, label %return
116
117return:
118  ret void
119}
120
121; Avoid generating extra code to materialize a trip count. Skip LFTR.
122define void @unguardedloop([0 x double]* %matrix, [0 x double]* %vector,
123                           i32 %irow, i32 %ilead) nounwind {
124entry:
125  br label %loop
126
127; CHECK: entry:
128; CHECK-NOT: zext
129; CHECK-NOT: add
130; CHECK: loop:
131; CHECK: phi i64
132; CHECK-NOT: phi
133; CHECK: icmp slt
134; CHECK: br i1
135loop:
136  %rowidx = phi i32 [ 0, %entry ], [ %row.inc, %loop ]
137  %i = phi i32 [ 0, %entry ], [ %i.inc, %loop ]
138  %diagidx = add nsw i32 %rowidx, %i
139  %diagidxw = sext i32 %diagidx to i64
140  %matrixp = getelementptr inbounds [0 x double], [0 x double]* %matrix, i32 0, i64 %diagidxw
141  %v1 = load double, double* %matrixp
142  %iw = sext i32 %i to i64
143  %vectorp = getelementptr inbounds [0 x double], [0 x double]* %vector, i32 0, i64 %iw
144  %v2 = load double, double* %vectorp
145  %row.inc = add nsw i32 %rowidx, %ilead
146  %i.inc = add nsw i32 %i, 1
147  %cmp196 = icmp slt i32 %i.inc, %irow
148  br i1 %cmp196, label %loop, label %return
149
150return:
151  ret void
152}
153
154; Remove %i which is only used by the exit test.
155; Verify that SCEV can still compute a backedge count from the sign
156; extended %n, used for pointer comparison by LFTR.
157;
158; TODO: Fix for PR13371 currently makes this impossible. See
159; IndVarSimplify.cpp hasConcreteDef(). We may want to change to undef rules.
160define void @geplftr(i8* %base, i32 %x, i32 %y, i32 %n) nounwind {
161entry:
162  %x.ext = sext i32 %x to i64
163  %add.ptr = getelementptr inbounds i8, i8* %base, i64 %x.ext
164  %y.ext = sext i32 %y to i64
165  %add.ptr10 = getelementptr inbounds i8, i8* %add.ptr, i64 %y.ext
166  %lim = add i32 %x, %n
167  %cmp.ph = icmp ult i32 %x, %lim
168  br i1 %cmp.ph, label %loop, label %exit
169; CHECK-LABEL: @geplftr(
170; CHECK: loop:
171; CHECK: phi i8*
172; DISABLE-NOT: phi      // This check is currently disabled
173; CHECK: getelementptr
174; CHECK: store
175; DISABLE: icmp ne i8*  // This check is currently disabled
176; CHECK: br i1
177loop:
178  %i = phi i32 [ %x, %entry ], [ %inc, %loop ]
179  %aptr = phi i8* [ %add.ptr10, %entry ], [ %incdec.ptr, %loop ]
180  %incdec.ptr = getelementptr inbounds i8, i8* %aptr, i32 1
181  store i8 3, i8* %aptr
182  %inc = add i32 %i, 1
183  %cmp = icmp ult i32 %inc, %lim
184  br i1 %cmp, label %loop, label %exit
185
186exit:
187  ret void
188}
189
190; Exercise backedge taken count verification with a never-taken loop.
191define void @nevertaken() nounwind uwtable ssp {
192entry:
193  br label %loop
194; CHECK-LABEL: @nevertaken(
195; CHECK: loop:
196; CHECK-NOT: phi
197; CHECK-NOT: add
198; CHECK-NOT: icmp
199; CHECK: exit:
200loop:
201  %i = phi i32 [ 0, %entry ], [ %inc, %loop ]
202  %inc = add nsw i32 %i, 1
203  %cmp = icmp sle i32 %inc, 0
204  br i1 %cmp, label %loop, label %exit
205
206exit:
207  ret void
208}
209
210; Test LFTR on an IV whose recurrence start is a non-unit pointer type.
211define void @aryptriv([256 x i8]* %base, i32 %n) nounwind {
212entry:
213  %ivstart = getelementptr inbounds [256 x i8], [256 x i8]* %base, i32 0, i32 0
214  %ivend = getelementptr inbounds [256 x i8], [256 x i8]* %base, i32 0, i32 %n
215  %cmp.ph = icmp ult i8* %ivstart, %ivend
216  br i1 %cmp.ph, label %loop, label %exit
217
218; CHECK: loop:
219; CHECK: phi i8*
220; CHECK-NOT: phi
221; CHECK: getelementptr
222; CHECK: store
223; CHECK: icmp ne i8*
224; CHECK: br i1
225loop:
226  %aptr = phi i8* [ %ivstart, %entry ], [ %incdec.ptr, %loop ]
227  %incdec.ptr = getelementptr inbounds i8, i8* %aptr, i32 1
228  store i8 3, i8* %aptr
229  %cmp = icmp ult i8* %incdec.ptr, %ivend
230  br i1 %cmp, label %loop, label %exit
231
232exit:
233  ret void
234}
235