[opaque pointer type] Add textual IR support for explicit type parameter to getelemen...
[oota-llvm.git] / test / Transforms / IndVarSimplify / no-iv-rewrite.ll
1 ; RUN: opt < %s -indvars -S | FileCheck %s
2 ;
3 ; Make sure that indvars isn't inserting canonical IVs.
4 ; This is kinda hard to do until linear function test replacement is removed.
5
6 target 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"
7
8 define i32 @sum(i32* %arr, i32 %n) nounwind {
9 entry:
10   %precond = icmp slt i32 0, %n
11   br i1 %precond, label %ph, label %return
12
13 ph:
14   br label %loop
15
16 ; CHECK: loop:
17 ;
18 ; We should only have 2 IVs.
19 ; CHECK: phi
20 ; CHECK: phi
21 ; CHECK-NOT: phi
22 ;
23 ; sext should be eliminated while preserving gep inboundsness.
24 ; CHECK-NOT: sext
25 ; CHECK: getelementptr inbounds
26 ; CHECK: exit:
27 loop:
28   %i.02 = phi i32 [ 0, %ph ], [ %iinc, %loop ]
29   %s.01 = phi i32 [ 0, %ph ], [ %sinc, %loop ]
30   %ofs = sext i32 %i.02 to i64
31   %adr = getelementptr inbounds i32, i32* %arr, i64 %ofs
32   %val = load i32* %adr
33   %sinc = add nsw i32 %s.01, %val
34   %iinc = add nsw i32 %i.02, 1
35   %cond = icmp slt i32 %iinc, %n
36   br i1 %cond, label %loop, label %exit
37
38 exit:
39   %s.lcssa = phi i32 [ %sinc, %loop ]
40   br label %return
41
42 return:
43   %s.0.lcssa = phi i32 [ %s.lcssa, %exit ], [ 0, %entry ]
44   ret i32 %s.0.lcssa
45 }
46
47 define i64 @suml(i32* %arr, i32 %n) nounwind {
48 entry:
49   %precond = icmp slt i32 0, %n
50   br i1 %precond, label %ph, label %return
51
52 ph:
53   br label %loop
54
55 ; CHECK: loop:
56 ;
57 ; We should only have 2 IVs.
58 ; CHECK: phi
59 ; CHECK: phi
60 ; CHECK-NOT: phi
61 ;
62 ; %ofs sext should be eliminated while preserving gep inboundsness.
63 ; CHECK-NOT: sext
64 ; CHECK: getelementptr inbounds
65 ; %vall sext should obviously not be eliminated
66 ; CHECK: sext
67 ; CHECK: exit:
68 loop:
69   %i.02 = phi i32 [ 0, %ph ], [ %iinc, %loop ]
70   %s.01 = phi i64 [ 0, %ph ], [ %sinc, %loop ]
71   %ofs = sext i32 %i.02 to i64
72   %adr = getelementptr inbounds i32, i32* %arr, i64 %ofs
73   %val = load i32* %adr
74   %vall = sext i32 %val to i64
75   %sinc = add nsw i64 %s.01, %vall
76   %iinc = add nsw i32 %i.02, 1
77   %cond = icmp slt i32 %iinc, %n
78   br i1 %cond, label %loop, label %exit
79
80 exit:
81   %s.lcssa = phi i64 [ %sinc, %loop ]
82   br label %return
83
84 return:
85   %s.0.lcssa = phi i64 [ %s.lcssa, %exit ], [ 0, %entry ]
86   ret i64 %s.0.lcssa
87 }
88
89 define void @outofbounds(i32* %first, i32* %last, i32 %idx) nounwind {
90   %precond = icmp ne i32* %first, %last
91   br i1 %precond, label %ph, label %return
92
93 ; CHECK: ph:
94 ; It's not indvars' job to perform LICM on %ofs
95 ; CHECK-NOT: sext
96 ph:
97   br label %loop
98
99 ; CHECK: loop:
100 ;
101 ; Preserve exactly one pointer type IV.
102 ; CHECK: phi i32*
103 ; CHECK-NOT: phi
104 ;
105 ; Don't create any extra adds.
106 ; CHECK-NOT: add
107 ;
108 ; Preserve gep inboundsness, and don't factor it.
109 ; CHECK: getelementptr inbounds i32, i32* %ptriv, i32 1
110 ; CHECK-NOT: add
111 ; CHECK: exit:
112 loop:
113   %ptriv = phi i32* [ %first, %ph ], [ %ptrpost, %loop ]
114   %ofs = sext i32 %idx to i64
115   %adr = getelementptr inbounds i32, i32* %ptriv, i64 %ofs
116   store i32 3, i32* %adr
117   %ptrpost = getelementptr inbounds i32, i32* %ptriv, i32 1
118   %cond = icmp ne i32* %ptrpost, %last
119   br i1 %cond, label %loop, label %exit
120
121 exit:
122   br label %return
123
124 return:
125   ret void
126 }
127
128 %structI = type { i32 }
129
130 define void @bitcastiv(i32 %start, i32 %limit, i32 %step, %structI* %base)
131 nounwind
132 {
133 entry:
134   br label %loop
135
136 ; CHECK: loop:
137 ;
138 ; Preserve casts
139 ; CHECK: phi i32
140 ; CHECK: bitcast
141 ; CHECK: getelementptr
142 ; CHECK: exit:
143 loop:
144   %iv = phi i32 [%start, %entry], [%next, %loop]
145   %p = phi %structI* [%base, %entry], [%pinc, %loop]
146   %adr = getelementptr %structI, %structI* %p, i32 0, i32 0
147   store i32 3, i32* %adr
148   %pp = bitcast %structI* %p to i32*
149   store i32 4, i32* %pp
150   %pinc = getelementptr %structI, %structI* %p, i32 1
151   %next = add i32 %iv, 1
152   %cond = icmp ne i32 %next, %limit
153   br i1 %cond, label %loop, label %exit
154
155 exit:
156   ret void
157 }
158
159 define void @maxvisitor(i32 %limit, i32* %base) nounwind {
160 entry:
161  br label %loop
162
163 ; Test inserting a truncate at a phi use.
164 ;
165 ; CHECK: loop:
166 ; CHECK: phi i64
167 ; CHECK: trunc
168 ; CHECK: exit:
169 loop:
170   %idx = phi i32 [ 0, %entry ], [ %idx.next, %loop.inc ]
171   %max = phi i32 [ 0, %entry ], [ %max.next, %loop.inc ]
172   %idxprom = sext i32 %idx to i64
173   %adr = getelementptr inbounds i32, i32* %base, i64 %idxprom
174   %val = load i32* %adr
175   %cmp19 = icmp sgt i32 %val, %max
176   br i1 %cmp19, label %if.then, label %if.else
177
178 if.then:
179   br label %loop.inc
180
181 if.else:
182   br label %loop.inc
183
184 loop.inc:
185   %max.next = phi i32 [ %idx, %if.then ], [ %max, %if.else ]
186   %idx.next = add nsw i32 %idx, 1
187   %cmp = icmp slt i32 %idx.next, %limit
188   br i1 %cmp, label %loop, label %exit
189
190 exit:
191   ret void
192 }
193
194 define void @identityphi(i32 %limit) nounwind {
195 entry:
196   br label %loop
197
198 ; Test an edge case of removing an identity phi that directly feeds
199 ; back to the loop iv.
200 ;
201 ; CHECK: loop:
202 ; CHECK-NOT: phi
203 ; CHECK: exit:
204 loop:
205   %iv = phi i32 [ 0, %entry], [ %iv.next, %control ]
206   br i1 undef, label %if.then, label %control
207
208 if.then:
209   br label %control
210
211 control:
212   %iv.next = phi i32 [ %iv, %loop ], [ undef, %if.then ]
213   %cmp = icmp slt i32 %iv.next, %limit
214   br i1 %cmp, label %loop, label %exit
215
216 exit:
217   ret void
218 }
219
220 define i64 @cloneOr(i32 %limit, i64* %base) nounwind {
221 entry:
222   ; ensure that the loop can't overflow
223   %halfLim = ashr i32 %limit, 2
224   br label %loop
225
226 ; This test originally checked that the OR instruction was cloned. Now the
227 ; ScalarEvolution is able to understand the loop evolution and that '%iv' at the
228 ; end of the loop is an even value. Thus '%val' is computed at the end of the
229 ; loop and the OR instruction is replaced by an ADD keeping the result
230 ; equivalent.
231 ;
232 ; CHECK: sext
233 ; CHECK: loop:
234 ; CHECK: phi i64
235 ; CHECK-NOT: sext
236 ; CHECK: icmp slt i64
237 ; CHECK: exit:
238 ; CHECK: add i64
239 loop:
240   %iv = phi i32 [ 0, %entry], [ %iv.next, %loop ]
241   %t1 = sext i32 %iv to i64
242   %adr = getelementptr i64, i64* %base, i64 %t1
243   %val = load i64* %adr
244   %t2 = or i32 %iv, 1
245   %t3 = sext i32 %t2 to i64
246   %iv.next = add i32 %iv, 2
247   %cmp = icmp slt i32 %iv.next, %halfLim
248   br i1 %cmp, label %loop, label %exit
249
250 exit:
251   %result = and i64 %val, %t3
252   ret i64 %result
253 }
254
255 ; The i induction variable looks like a wrap-around, but it really is just
256 ; a simple affine IV.  Make sure that indvars simplifies through.
257 define i32 @indirectRecurrence() nounwind {
258 entry:
259   br label %loop
260
261 ; ReplaceLoopExitValue should fold the return value to constant 9.
262 ; CHECK: loop:
263 ; CHECK: phi i32
264 ; CHECK: ret i32 9
265 loop:
266   %j.0 = phi i32 [ 1, %entry ], [ %j.next, %cond_true ]
267   %i.0 = phi i32 [ 0, %entry ], [ %j.0, %cond_true ]
268   %tmp = icmp ne i32 %j.0, 10
269   br i1 %tmp, label %cond_true, label %return
270
271 cond_true:
272   %j.next = add i32 %j.0, 1
273   br label %loop
274
275 return:
276   ret i32 %i.0
277 }
278
279 ; Eliminate the congruent phis j, k, and l.
280 ; Eliminate the redundant IV increments k.next and l.next.
281 ; Two phis should remain, one starting at %init, and one at %init1.
282 ; Two increments should remain, one by %step and one by %step1.
283 ; CHECK: loop:
284 ; CHECK: phi i32
285 ; CHECK: phi i32
286 ; CHECK-NOT: phi
287 ; CHECK: add i32
288 ; CHECK: add i32
289 ; CHECK: add i32
290 ; CHECK-NOT: add
291 ; CHECK: return:
292 ;
293 ; Five live-outs should remain.
294 ; CHECK: lcssa = phi
295 ; CHECK: lcssa = phi
296 ; CHECK: lcssa = phi
297 ; CHECK: lcssa = phi
298 ; CHECK: lcssa = phi
299 ; CHECK-NOT: phi
300 ; CHECK: ret
301 define i32 @isomorphic(i32 %init, i32 %step, i32 %lim) nounwind {
302 entry:
303   %step1 = add i32 %step, 1
304   %init1 = add i32 %init, %step1
305   %l.0 = sub i32 %init1, %step1
306   br label %loop
307
308 loop:
309   %ii = phi i32 [ %init1, %entry ], [ %ii.next, %loop ]
310   %i = phi i32 [ %init, %entry ], [ %ii, %loop ]
311   %j = phi i32 [ %init, %entry ], [ %j.next, %loop ]
312   %k = phi i32 [ %init1, %entry ], [ %k.next, %loop ]
313   %l = phi i32 [ %l.0, %entry ], [ %l.next, %loop ]
314   %ii.next = add i32 %ii, %step1
315   %j.next = add i32 %j, %step1
316   %k.next = add i32 %k, %step1
317   %l.step = add i32 %l, %step
318   %l.next = add i32 %l.step, 1
319   %cmp = icmp ne i32 %ii.next, %lim
320   br i1 %cmp, label %loop, label %return
321
322 return:
323   %sum1 = add i32 %i, %j.next
324   %sum2 = add i32 %sum1, %k.next
325   %sum3 = add i32 %sum1, %l.step
326   %sum4 = add i32 %sum1, %l.next
327   ret i32 %sum4
328 }
329
330 ; Test a GEP IV that is derived from another GEP IV by a nop gep that
331 ; lowers the type without changing the expression.
332 %structIF = type { i32, float }
333
334 define void @congruentgepiv(%structIF* %base) nounwind uwtable ssp {
335 entry:
336   %first = getelementptr inbounds %structIF, %structIF* %base, i64 0, i32 0
337   br label %loop
338
339 ; CHECK: loop:
340 ; CHECK: phi %structIF*
341 ; CHECK-NOT: phi
342 ; CHECK: getelementptr inbounds
343 ; CHECK-NOT: getelementptr
344 ; CHECK: exit:
345 loop:
346   %ptr.iv = phi %structIF* [ %ptr.inc, %latch ], [ %base, %entry ]
347   %next = phi i32* [ %next.inc, %latch ], [ %first, %entry ]
348   store i32 4, i32* %next
349   br i1 undef, label %latch, label %exit
350
351 latch:                         ; preds = %for.inc50.i
352   %ptr.inc = getelementptr inbounds %structIF, %structIF* %ptr.iv, i64 1
353   %next.inc = getelementptr inbounds %structIF, %structIF* %ptr.inc, i64 0, i32 0
354   br label %loop
355
356 exit:
357   ret void
358 }
359
360 ; Test a widened IV that is used by a phi on different paths within the loop.
361 ;
362 ; CHECK: for.body:
363 ; CHECK: phi i64
364 ; CHECK: trunc i64
365 ; CHECK: if.then:
366 ; CHECK: for.inc:
367 ; CHECK: phi i32
368 ; CHECK: for.end:
369 define void @phiUsesTrunc() nounwind {
370 entry:
371   br i1 undef, label %for.body, label %for.end
372
373 for.body:
374   %iv = phi i32 [ %inc, %for.inc ], [ 1, %entry ]
375   br i1 undef, label %if.then, label %if.else
376
377 if.then:
378   br i1 undef, label %if.then33, label %for.inc
379
380 if.then33:
381   br label %for.inc
382
383 if.else:
384   br i1 undef, label %if.then97, label %for.inc
385
386 if.then97:
387   %idxprom100 = sext i32 %iv to i64
388   br label %for.inc
389
390 for.inc:
391   %kmin.1 = phi i32 [ %iv, %if.then33 ], [ 0, %if.then ], [ %iv, %if.then97 ], [ 0, %if.else ]
392   %inc = add nsw i32 %iv, 1
393   br i1 undef, label %for.body, label %for.end
394
395 for.end:
396   ret void
397 }