Fix broken check lines.
[oota-llvm.git] / test / Transforms / GVN / rle.ll
1 ; RUN: opt < %s -basicaa -gvn -S -die | FileCheck %s
2
3 ; 32-bit little endian target.
4 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128-n8:16:32"
5
6 ;; Trivial RLE test.
7 define i32 @test0(i32 %V, i32* %P) {
8   store i32 %V, i32* %P
9
10   %A = load i32* %P
11   ret i32 %A
12 ; CHECK: @test0
13 ; CHECK: ret i32 %V
14 }
15
16
17 ;;===----------------------------------------------------------------------===;;
18 ;; Tests for crashers
19 ;;===----------------------------------------------------------------------===;;
20
21 ;; PR5016
22 define i8 @crash0({i32, i32} %A, {i32, i32}* %P) {
23   store {i32, i32} %A, {i32, i32}* %P
24   %X = bitcast {i32, i32}* %P to i8*
25   %Y = load i8* %X
26   ret i8 %Y
27 }
28
29 ;; No PR filed, crashed in CaptureTracker.
30 declare void @helper()
31 define void @crash1() {
32   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* undef, i8* undef, i64 undef, i32 1, i1 false) nounwind
33   %tmp = load i8* bitcast (void ()* @helper to i8*)
34   %x = icmp eq i8 %tmp, 15
35   ret void
36 }
37
38
39 ;;===----------------------------------------------------------------------===;;
40 ;; Store -> Load  and  Load -> Load forwarding where src and dst are different
41 ;; types, but where the base pointer is a must alias.
42 ;;===----------------------------------------------------------------------===;;
43
44 ;; i32 -> f32 forwarding.
45 define float @coerce_mustalias1(i32 %V, i32* %P) {
46   store i32 %V, i32* %P
47    
48   %P2 = bitcast i32* %P to float*
49
50   %A = load float* %P2
51   ret float %A
52 ; CHECK: @coerce_mustalias1
53 ; CHECK-NOT: load
54 ; CHECK: ret float 
55 }
56
57 ;; i32* -> float forwarding.
58 define float @coerce_mustalias2(i32* %V, i32** %P) {
59   store i32* %V, i32** %P
60    
61   %P2 = bitcast i32** %P to float*
62
63   %A = load float* %P2
64   ret float %A
65 ; CHECK: @coerce_mustalias2
66 ; CHECK-NOT: load
67 ; CHECK: ret float 
68 }
69
70 ;; float -> i32* forwarding.
71 define i32* @coerce_mustalias3(float %V, float* %P) {
72   store float %V, float* %P
73    
74   %P2 = bitcast float* %P to i32**
75
76   %A = load i32** %P2
77   ret i32* %A
78 ; CHECK: @coerce_mustalias3
79 ; CHECK-NOT: load
80 ; CHECK: ret i32* 
81 }
82
83 ;; i32 -> f32 load forwarding.
84 define float @coerce_mustalias4(i32* %P, i1 %cond) {
85   %A = load i32* %P
86   
87   %P2 = bitcast i32* %P to float*
88   %B = load float* %P2
89   br i1 %cond, label %T, label %F
90 T:
91   ret float %B
92   
93 F:
94   %X = bitcast i32 %A to float
95   ret float %X
96
97 ; CHECK: @coerce_mustalias4
98 ; CHECK: %A = load i32* %P
99 ; CHECK-NOT: load
100 ; CHECK: ret float
101 ; CHECK: F:
102 }
103
104 ;; i32 -> i8 forwarding
105 define i8 @coerce_mustalias5(i32 %V, i32* %P) {
106   store i32 %V, i32* %P
107    
108   %P2 = bitcast i32* %P to i8*
109
110   %A = load i8* %P2
111   ret i8 %A
112 ; CHECK: @coerce_mustalias5
113 ; CHECK-NOT: load
114 ; CHECK: ret i8
115 }
116
117 ;; i64 -> float forwarding
118 define float @coerce_mustalias6(i64 %V, i64* %P) {
119   store i64 %V, i64* %P
120    
121   %P2 = bitcast i64* %P to float*
122
123   %A = load float* %P2
124   ret float %A
125 ; CHECK: @coerce_mustalias6
126 ; CHECK-NOT: load
127 ; CHECK: ret float
128 }
129
130 ;; i64 -> i8* (32-bit) forwarding
131 define i8* @coerce_mustalias7(i64 %V, i64* %P) {
132   store i64 %V, i64* %P
133    
134   %P2 = bitcast i64* %P to i8**
135
136   %A = load i8** %P2
137   ret i8* %A
138 ; CHECK: @coerce_mustalias7
139 ; CHECK-NOT: load
140 ; CHECK: ret i8*
141 }
142
143 ; memset -> i16 forwarding.
144 define signext i16 @memset_to_i16_local(i16* %A) nounwind ssp {
145 entry:
146   %conv = bitcast i16* %A to i8* 
147   tail call void @llvm.memset.p0i8.i64(i8* %conv, i8 1, i64 200, i32 1, i1 false)
148   %arrayidx = getelementptr inbounds i16* %A, i64 42
149   %tmp2 = load i16* %arrayidx
150   ret i16 %tmp2
151 ; CHECK: @memset_to_i16_local
152 ; CHECK-NOT: load
153 ; CHECK: ret i16 257
154 }
155
156 ; memset -> float forwarding.
157 define float @memset_to_float_local(float* %A, i8 %Val) nounwind ssp {
158 entry:
159   %conv = bitcast float* %A to i8*                ; <i8*> [#uses=1]
160   tail call void @llvm.memset.p0i8.i64(i8* %conv, i8 %Val, i64 400, i32 1, i1 false)
161   %arrayidx = getelementptr inbounds float* %A, i64 42 ; <float*> [#uses=1]
162   %tmp2 = load float* %arrayidx                   ; <float> [#uses=1]
163   ret float %tmp2
164 ; CHECK: @memset_to_float_local
165 ; CHECK-NOT: load
166 ; CHECK: zext
167 ; CHECK-NEXT: shl
168 ; CHECK-NEXT: or
169 ; CHECK-NEXT: shl
170 ; CHECK-NEXT: or
171 ; CHECK-NEXT: bitcast
172 ; CHECK-NEXT: ret float
173 }
174
175 ;; non-local memset -> i16 load forwarding.
176 define i16 @memset_to_i16_nonlocal0(i16* %P, i1 %cond) {
177   %P3 = bitcast i16* %P to i8*
178   br i1 %cond, label %T, label %F
179 T:
180   tail call void @llvm.memset.p0i8.i64(i8* %P3, i8 1, i64 400, i32 1, i1 false)
181   br label %Cont
182   
183 F:
184   tail call void @llvm.memset.p0i8.i64(i8* %P3, i8 2, i64 400, i32 1, i1 false)
185   br label %Cont
186
187 Cont:
188   %P2 = getelementptr i16* %P, i32 4
189   %A = load i16* %P2
190   ret i16 %A
191
192 ; CHECK: @memset_to_i16_nonlocal0
193 ; CHECK: Cont:
194 ; CHECK-NEXT:   %A = phi i16 [ 514, %F ], [ 257, %T ]
195 ; CHECK-NOT: load
196 ; CHECK: ret i16 %A
197 }
198
199 @GCst = constant {i32, float, i32 } { i32 42, float 14., i32 97 }
200
201 ; memset -> float forwarding.
202 define float @memcpy_to_float_local(float* %A) nounwind ssp {
203 entry:
204   %conv = bitcast float* %A to i8*                ; <i8*> [#uses=1]
205   tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %conv, i8* bitcast ({i32, float, i32 }* @GCst to i8*), i64 12, i32 1, i1 false)
206   %arrayidx = getelementptr inbounds float* %A, i64 1 ; <float*> [#uses=1]
207   %tmp2 = load float* %arrayidx                   ; <float> [#uses=1]
208   ret float %tmp2
209 ; CHECK: @memcpy_to_float_local
210 ; CHECK-NOT: load
211 ; CHECK: ret float 1.400000e+01
212 }
213
214
215
216 ;; non-local i32/float -> i8 load forwarding.
217 define i8 @coerce_mustalias_nonlocal0(i32* %P, i1 %cond) {
218   %P2 = bitcast i32* %P to float*
219   %P3 = bitcast i32* %P to i8*
220   br i1 %cond, label %T, label %F
221 T:
222   store i32 42, i32* %P
223   br label %Cont
224   
225 F:
226   store float 1.0, float* %P2
227   br label %Cont
228
229 Cont:
230   %A = load i8* %P3
231   ret i8 %A
232
233 ; CHECK: @coerce_mustalias_nonlocal0
234 ; CHECK: Cont:
235 ; CHECK:   %A = phi i8 [
236 ; CHECK-NOT: load
237 ; CHECK: ret i8 %A
238 }
239
240
241 ;; non-local i32/float -> i8 load forwarding.  This also tests that the "P3"
242 ;; bitcast equivalence can be properly phi translated.
243 define i8 @coerce_mustalias_nonlocal1(i32* %P, i1 %cond) {
244   %P2 = bitcast i32* %P to float*
245   br i1 %cond, label %T, label %F
246 T:
247   store i32 42, i32* %P
248   br label %Cont
249   
250 F:
251   store float 1.0, float* %P2
252   br label %Cont
253
254 Cont:
255   %P3 = bitcast i32* %P to i8*
256   %A = load i8* %P3
257   ret i8 %A
258
259 ;; FIXME: This is disabled because this caused a miscompile in the llvm-gcc
260 ;; bootstrap, see r82411
261 ;
262 ; HECK: @coerce_mustalias_nonlocal1
263 ; HECK: Cont:
264 ; HECK:   %A = phi i8 [
265 ; HECK-NOT: load
266 ; HECK: ret i8 %A
267 }
268
269
270 ;; non-local i32 -> i8 partial redundancy load forwarding.
271 define i8 @coerce_mustalias_pre0(i32* %P, i1 %cond) {
272   %P3 = bitcast i32* %P to i8*
273   br i1 %cond, label %T, label %F
274 T:
275   store i32 42, i32* %P
276   br label %Cont
277   
278 F:
279   br label %Cont
280
281 Cont:
282   %A = load i8* %P3
283   ret i8 %A
284
285 ; CHECK: @coerce_mustalias_pre0
286 ; CHECK: F:
287 ; CHECK:   load i8* %P3
288 ; CHECK: Cont:
289 ; CHECK:   %A = phi i8 [
290 ; CHECK-NOT: load
291 ; CHECK: ret i8 %A
292 }
293
294 ;;===----------------------------------------------------------------------===;;
295 ;; Store -> Load  and  Load -> Load forwarding where src and dst are different
296 ;; types, and the reload is an offset from the store pointer.
297 ;;===----------------------------------------------------------------------===;;
298
299 ;; i32 -> i8 forwarding.
300 ;; PR4216
301 define i8 @coerce_offset0(i32 %V, i32* %P) {
302   store i32 %V, i32* %P
303    
304   %P2 = bitcast i32* %P to i8*
305   %P3 = getelementptr i8* %P2, i32 2
306
307   %A = load i8* %P3
308   ret i8 %A
309 ; CHECK: @coerce_offset0
310 ; CHECK-NOT: load
311 ; CHECK: ret i8
312 }
313
314 ;; non-local i32/float -> i8 load forwarding.
315 define i8 @coerce_offset_nonlocal0(i32* %P, i1 %cond) {
316   %P2 = bitcast i32* %P to float*
317   %P3 = bitcast i32* %P to i8*
318   %P4 = getelementptr i8* %P3, i32 2
319   br i1 %cond, label %T, label %F
320 T:
321   store i32 42, i32* %P
322   br label %Cont
323   
324 F:
325   store float 1.0, float* %P2
326   br label %Cont
327
328 Cont:
329   %A = load i8* %P4
330   ret i8 %A
331
332 ; CHECK: @coerce_offset_nonlocal0
333 ; CHECK: Cont:
334 ; CHECK:   %A = phi i8 [
335 ; CHECK-NOT: load
336 ; CHECK: ret i8 %A
337 }
338
339
340 ;; non-local i32 -> i8 partial redundancy load forwarding.
341 define i8 @coerce_offset_pre0(i32* %P, i1 %cond) {
342   %P3 = bitcast i32* %P to i8*
343   %P4 = getelementptr i8* %P3, i32 2
344   br i1 %cond, label %T, label %F
345 T:
346   store i32 42, i32* %P
347   br label %Cont
348   
349 F:
350   br label %Cont
351
352 Cont:
353   %A = load i8* %P4
354   ret i8 %A
355
356 ; CHECK: @coerce_offset_pre0
357 ; CHECK: F:
358 ; CHECK:   load i8* %P4
359 ; CHECK: Cont:
360 ; CHECK:   %A = phi i8 [
361 ; CHECK-NOT: load
362 ; CHECK: ret i8 %A
363 }
364
365 define i32 @chained_load(i32** %p) {
366 block1:
367   %A = alloca i32*
368
369   %z = load i32** %p
370   store i32* %z, i32** %A
371   br i1 true, label %block2, label %block3
372
373 block2:
374  %a = load i32** %p
375  br label %block4
376
377 block3:
378   %b = load i32** %p
379   br label %block4
380
381 block4:
382   %c = load i32** %p
383   %d = load i32* %c
384   ret i32 %d
385   
386 ; CHECK: @chained_load
387 ; CHECK: %z = load i32** %p
388 ; CHECK-NOT: load
389 ; CHECK: %d = load i32* %z
390 ; CHECK-NEXT: ret i32 %d
391 }
392
393
394 declare i1 @cond() readonly
395 declare i1 @cond2() readonly
396
397 define i32 @phi_trans2() {
398 ; CHECK: @phi_trans2
399 entry:
400   %P = alloca i32, i32 400
401   br label %F1
402   
403 F1:
404   %A = phi i32 [1, %entry], [2, %F]
405   %cond2 = call i1 @cond()
406   br i1 %cond2, label %T1, label %TY
407   
408 T1:
409   %P2 = getelementptr i32* %P, i32 %A
410   %x = load i32* %P2
411   %cond = call i1 @cond2()
412   br i1 %cond, label %TX, label %F
413   
414 F:
415   %P3 = getelementptr i32* %P, i32 2
416   store i32 17, i32* %P3
417   
418   store i32 42, i32* %P2  ; Provides "P[A]".
419   br label %F1
420
421 TX:
422   ; This load should not be compiled to 'ret i32 42'.  An overly clever
423   ; implementation of GVN would see that we're returning 17 if the loop
424   ; executes once or 42 if it executes more than that, but we'd have to do
425   ; loop restructuring to expose this, and GVN shouldn't do this sort of CFG
426   ; transformation.
427   
428 ; CHECK: TX:
429 ; CHECK: ret i32 %x
430   ret i32 %x
431 TY:
432   ret i32 0
433 }
434
435 define i32 @phi_trans3(i32* %p) {
436 ; CHECK: @phi_trans3
437 block1:
438   br i1 true, label %block2, label %block3
439
440 block2:
441  store i32 87, i32* %p
442  br label %block4
443
444 block3:
445   %p2 = getelementptr i32* %p, i32 43
446   store i32 97, i32* %p2
447   br label %block4
448
449 block4:
450   %A = phi i32 [-1, %block2], [42, %block3]
451   br i1 true, label %block5, label %exit
452   
453 ; CHECK: block4:
454 ; CHECK-NEXT: %D = phi i32 [ 87, %block2 ], [ 97, %block3 ]  
455 ; CHECK-NOT: load
456
457 block5:
458   %B = add i32 %A, 1
459   br i1 true, label %block6, label %exit
460   
461 block6:
462   %C = getelementptr i32* %p, i32 %B
463   br i1 true, label %block7, label %exit
464   
465 block7:
466   %D = load i32* %C
467   ret i32 %D
468   
469 ; CHECK: block7:
470 ; CHECK-NEXT: ret i32 %D
471
472 exit:
473   ret i32 -1
474 }
475
476 define i8 @phi_trans4(i8* %p) {
477 ; CHECK: @phi_trans4
478 entry:
479   %X3 = getelementptr i8* %p, i32 192
480   store i8 192, i8* %X3
481   
482   %X = getelementptr i8* %p, i32 4
483   %Y = load i8* %X
484   br label %loop
485
486 loop:
487   %i = phi i32 [4, %entry], [192, %loop]
488   %X2 = getelementptr i8* %p, i32 %i
489   %Y2 = load i8* %X2
490   
491 ; CHECK: loop:
492 ; CHECK-NEXT: %Y2 = phi i8 [ %Y, %entry ], [ 0, %loop ]
493 ; CHECK-NOT: load i8
494   
495   %cond = call i1 @cond2()
496
497   %Z = bitcast i8 *%X3 to i32*
498   store i32 0, i32* %Z
499   br i1 %cond, label %loop, label %out
500   
501 out:
502   %R = add i8 %Y, %Y2
503   ret i8 %R
504 }
505
506 define i8 @phi_trans5(i8* %p) {
507 ; CHECK: @phi_trans5
508 entry:
509   
510   %X4 = getelementptr i8* %p, i32 2
511   store i8 19, i8* %X4
512   
513   %X = getelementptr i8* %p, i32 4
514   %Y = load i8* %X
515   br label %loop
516
517 loop:
518   %i = phi i32 [4, %entry], [3, %cont]
519   %X2 = getelementptr i8* %p, i32 %i
520   %Y2 = load i8* %X2  ; Ensure this load is not being incorrectly replaced.
521   %cond = call i1 @cond2()
522   br i1 %cond, label %cont, label %out
523
524 cont:
525   %Z = getelementptr i8* %X2, i32 -1
526   %Z2 = bitcast i8 *%Z to i32*
527   store i32 50462976, i32* %Z2  ;; (1 << 8) | (2 << 16) | (3 << 24)
528
529
530 ; CHECK: store i32
531 ; CHECK-NEXT: getelementptr i8* %p, i32 3
532 ; CHECK-NEXT: load i8*
533   br label %loop
534   
535 out:
536   %R = add i8 %Y, %Y2
537   ret i8 %R
538 }
539
540
541 ; PR6642
542 define i32 @memset_to_load() nounwind readnone {
543 entry:
544   %x = alloca [256 x i32], align 4                ; <[256 x i32]*> [#uses=2]
545   %tmp = bitcast [256 x i32]* %x to i8*           ; <i8*> [#uses=1]
546   call void @llvm.memset.p0i8.i64(i8* %tmp, i8 0, i64 1024, i32 4, i1 false)
547   %arraydecay = getelementptr inbounds [256 x i32]* %x, i32 0, i32 0 ; <i32*>
548   %tmp1 = load i32* %arraydecay                   ; <i32> [#uses=1]
549   ret i32 %tmp1
550 ; CHECK: @memset_to_load
551 ; CHECK: ret i32 0
552 }
553
554
555 ;;===----------------------------------------------------------------------===;;
556 ;; Load -> Load forwarding in partial alias case.
557 ;;===----------------------------------------------------------------------===;;
558
559 define i32 @load_load_partial_alias(i8* %P) nounwind ssp {
560 entry:
561   %0 = bitcast i8* %P to i32*
562   %tmp2 = load i32* %0
563   %add.ptr = getelementptr inbounds i8* %P, i64 1
564   %tmp5 = load i8* %add.ptr
565   %conv = zext i8 %tmp5 to i32
566   %add = add nsw i32 %tmp2, %conv
567   ret i32 %add
568
569 ; TEMPORARILYDISABLED: @load_load_partial_alias
570 ; TEMPORARILYDISABLED: load i32*
571 ; TEMPORARILYDISABLED-NOT: load
572 ; TEMPORARILYDISABLED: lshr i32 {{.*}}, 8
573 ; TEMPORARILYDISABLED-NOT: load
574 ; TEMPORARILYDISABLED: trunc i32 {{.*}} to i8
575 ; TEMPORARILYDISABLED-NOT: load
576 ; TEMPORARILYDISABLED: ret i32
577 }
578
579
580 ; Cross block partial alias case.
581 define i32 @load_load_partial_alias_cross_block(i8* %P) nounwind ssp {
582 entry:
583   %xx = bitcast i8* %P to i32*
584   %x1 = load i32* %xx, align 4
585   %cmp = icmp eq i32 %x1, 127
586   br i1 %cmp, label %land.lhs.true, label %if.end
587
588 land.lhs.true:                                    ; preds = %entry
589   %arrayidx4 = getelementptr inbounds i8* %P, i64 1
590   %tmp5 = load i8* %arrayidx4, align 1
591   %conv6 = zext i8 %tmp5 to i32
592   ret i32 %conv6
593
594 if.end:
595   ret i32 52
596 ; TEMPORARILY_DISABLED: @load_load_partial_alias_cross_block
597 ; TEMPORARILY_DISABLED: land.lhs.true:
598 ; TEMPORARILY_DISABLED-NOT: load i8
599 ; TEMPORARILY_DISABLED: ret i32 %conv6
600 }
601
602
603 ;;===----------------------------------------------------------------------===;;
604 ;; Load Widening
605 ;;===----------------------------------------------------------------------===;;
606
607 %widening1 = type { i32, i8, i8, i8, i8 }
608
609 @f = global %widening1 zeroinitializer, align 4
610
611 define i32 @test_widening1(i8* %P) nounwind ssp noredzone {
612 entry:
613   %tmp = load i8* getelementptr inbounds (%widening1* @f, i64 0, i32 1), align 4
614   %conv = zext i8 %tmp to i32
615   %tmp1 = load i8* getelementptr inbounds (%widening1* @f, i64 0, i32 2), align 1
616   %conv2 = zext i8 %tmp1 to i32
617   %add = add nsw i32 %conv, %conv2
618   ret i32 %add
619 ; CHECK: @test_widening1
620 ; CHECK-NOT: load
621 ; CHECK: load i16*
622 ; CHECK-NOT: load
623 ; CHECK: ret i32
624 }
625
626 define i32 @test_widening2() nounwind ssp noredzone {
627 entry:
628   %tmp = load i8* getelementptr inbounds (%widening1* @f, i64 0, i32 1), align 4
629   %conv = zext i8 %tmp to i32
630   %tmp1 = load i8* getelementptr inbounds (%widening1* @f, i64 0, i32 2), align 1
631   %conv2 = zext i8 %tmp1 to i32
632   %add = add nsw i32 %conv, %conv2
633
634   %tmp2 = load i8* getelementptr inbounds (%widening1* @f, i64 0, i32 3), align 2
635   %conv3 = zext i8 %tmp2 to i32
636   %add2 = add nsw i32 %add, %conv3
637
638   %tmp3 = load i8* getelementptr inbounds (%widening1* @f, i64 0, i32 4), align 1
639   %conv4 = zext i8 %tmp3 to i32
640   %add3 = add nsw i32 %add2, %conv3
641
642   ret i32 %add3
643 ; CHECK: @test_widening2
644 ; CHECK-NOT: load
645 ; CHECK: load i32*
646 ; CHECK-NOT: load
647 ; CHECK: ret i32
648 }
649
650 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
651
652 declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1) nounwind
653
654 ;;===----------------------------------------------------------------------===;;
655 ;; Load -> Store dependency which isn't interfered with by a call that happens
656 ;; before the pointer was captured.
657 ;;===----------------------------------------------------------------------===;;
658
659 %class.X = type { [8 x i8] }
660
661 @_ZTV1X = weak_odr constant [5 x i8*] zeroinitializer
662 @_ZTV1Y = weak_odr constant [5 x i8*] zeroinitializer
663
664 declare void @use()
665 declare void @use3(i8***, i8**)
666
667 ; PR8908
668 define void @test_escape1() nounwind {
669   %x = alloca i8**, align 8
670   store i8** getelementptr inbounds ([5 x i8*]* @_ZTV1X, i64 0, i64 2), i8*** %x, align 8
671   call void @use() nounwind
672   %DEAD = load i8*** %x, align 8
673   call void @use3(i8*** %x, i8** %DEAD) nounwind
674   ret void
675 ; CHECK: test_escape1
676 ; CHECK-NOT: DEAD
677 ; CHECK: ret
678 }