Add support to ValueTracking for determining that a pointer is non-null
[oota-llvm.git] / test / Transforms / InstSimplify / compare.ll
1 ; RUN: opt < %s -instsimplify -S | FileCheck %s
2 target datalayout = "p:32:32"
3
4 define i1 @ptrtoint() {
5 ; CHECK: @ptrtoint
6   %a = alloca i8
7   %tmp = ptrtoint i8* %a to i32
8   %r = icmp eq i32 %tmp, 0
9   ret i1 %r
10 ; CHECK: ret i1 false
11 }
12
13 define i1 @bitcast() {
14 ; CHECK: @bitcast
15   %a = alloca i32
16   %b = alloca i64
17   %x = bitcast i32* %a to i8*
18   %y = bitcast i64* %b to i8*
19   %cmp = icmp eq i8* %x, %y
20   ret i1 %cmp
21 ; CHECK-NEXT: ret i1 false
22 }
23
24 define i1 @gep() {
25 ; CHECK: @gep
26   %a = alloca [3 x i8], align 8
27   %x = getelementptr inbounds [3 x i8]* %a, i32 0, i32 0
28   %cmp = icmp eq i8* %x, null
29   ret i1 %cmp
30 ; CHECK-NEXT: ret i1 false
31 }
32
33 define i1 @gep2() {
34 ; CHECK: @gep2
35   %a = alloca [3 x i8], align 8
36   %x = getelementptr inbounds [3 x i8]* %a, i32 0, i32 0
37   %y = getelementptr inbounds [3 x i8]* %a, i32 0, i32 0
38   %cmp = icmp eq i8* %x, %y
39   ret i1 %cmp
40 ; CHECK-NEXT: ret i1 true
41 }
42
43 ; PR11238
44 %gept = type { i32, i32 }
45 @gepy = global %gept zeroinitializer, align 8
46 @gepz = extern_weak global %gept
47
48 define i1 @gep3() {
49 ; CHECK: @gep3
50   %x = alloca %gept, align 8
51   %a = getelementptr %gept* %x, i64 0, i32 0
52   %b = getelementptr %gept* %x, i64 0, i32 1
53   %equal = icmp eq i32* %a, %b
54   ret i1 %equal
55 ; CHECK-NEXT: ret i1 false
56 }
57
58 define i1 @gep4() {
59 ; CHECK: @gep4
60   %x = alloca %gept, align 8
61   %a = getelementptr %gept* @gepy, i64 0, i32 0
62   %b = getelementptr %gept* @gepy, i64 0, i32 1
63   %equal = icmp eq i32* %a, %b
64   ret i1 %equal
65 ; CHECK-NEXT: ret i1 false
66 }
67
68 define i1 @gep5() {
69 ; CHECK: @gep5
70   %x = alloca %gept, align 8
71   %a = getelementptr inbounds %gept* %x, i64 0, i32 1
72   %b = getelementptr %gept* @gepy, i64 0, i32 0
73   %equal = icmp eq i32* %a, %b
74   ret i1 %equal
75 ; CHECK-NEXT: ret i1 false
76 }
77
78 define i1 @gep6(%gept* %x) {
79 ; Same as @gep3 but potentially null.
80 ; CHECK: @gep6
81   %a = getelementptr %gept* %x, i64 0, i32 0
82   %b = getelementptr %gept* %x, i64 0, i32 1
83   %equal = icmp eq i32* %a, %b
84   ret i1 %equal
85 ; CHECK-NEXT: ret i1 false
86 }
87
88 define i1 @gep7(%gept* %x) {
89 ; CHECK: @gep7
90   %a = getelementptr %gept* %x, i64 0, i32 0
91   %b = getelementptr %gept* @gepz, i64 0, i32 0
92   %equal = icmp eq i32* %a, %b
93   ret i1 %equal
94 ; CHECK: ret i1 %equal
95 }
96
97 define i1 @gep8(%gept* %x) {
98 ; CHECK: @gep8
99   %a = getelementptr %gept* %x, i32 1
100   %b = getelementptr %gept* %x, i32 -1
101   %equal = icmp ugt %gept* %a, %b
102   ret i1 %equal
103 ; CHECK: ret i1 %equal
104 }
105
106 define i1 @gep9(i8* %ptr) {
107 ; CHECK: @gep9
108 ; CHECK-NOT: ret
109 ; CHECK: ret i1 true
110
111 entry:
112   %first1 = getelementptr inbounds i8* %ptr, i32 0
113   %first2 = getelementptr inbounds i8* %first1, i32 1
114   %first3 = getelementptr inbounds i8* %first2, i32 2
115   %first4 = getelementptr inbounds i8* %first3, i32 4
116   %last1 = getelementptr inbounds i8* %first2, i32 48
117   %last2 = getelementptr inbounds i8* %last1, i32 8
118   %last3 = getelementptr inbounds i8* %last2, i32 -4
119   %last4 = getelementptr inbounds i8* %last3, i32 -4
120   %first.int = ptrtoint i8* %first4 to i32
121   %last.int = ptrtoint i8* %last4 to i32
122   %cmp = icmp ne i32 %last.int, %first.int
123   ret i1 %cmp
124 }
125
126 define i1 @gep10(i8* %ptr) {
127 ; CHECK: @gep10
128 ; CHECK-NOT: ret
129 ; CHECK: ret i1 true
130
131 entry:
132   %first1 = getelementptr inbounds i8* %ptr, i32 -2
133   %first2 = getelementptr inbounds i8* %first1, i32 44
134   %last1 = getelementptr inbounds i8* %ptr, i32 48
135   %last2 = getelementptr inbounds i8* %last1, i32 -6
136   %first.int = ptrtoint i8* %first2 to i32
137   %last.int = ptrtoint i8* %last2 to i32
138   %cmp = icmp eq i32 %last.int, %first.int
139   ret i1 %cmp
140 }
141
142 define i1 @gep11(i8* %ptr) {
143 ; CHECK: @gep11
144 ; CHECK-NOT: ret
145 ; CHECK: ret i1 true
146
147 entry:
148   %first1 = getelementptr inbounds i8* %ptr, i32 -2
149   %last1 = getelementptr inbounds i8* %ptr, i32 48
150   %last2 = getelementptr inbounds i8* %last1, i32 -6
151   %cmp = icmp ult i8* %first1, %last2
152   ret i1 %cmp
153 }
154
155 define i1 @gep12(i8* %ptr) {
156 ; CHECK: @gep12
157 ; CHECK-NOT: ret
158 ; CHECK: ret i1 %cmp
159
160 entry:
161   %first1 = getelementptr inbounds i8* %ptr, i32 -2
162   %last1 = getelementptr inbounds i8* %ptr, i32 48
163   %last2 = getelementptr inbounds i8* %last1, i32 -6
164   %cmp = icmp slt i8* %first1, %last2
165   ret i1 %cmp
166 }
167
168 define i1 @gep13(i8* %ptr) {
169 ; CHECK: @gep13
170 ; We can prove this GEP is non-null because it is inbounds.
171   %x = getelementptr inbounds i8* %ptr, i32 1
172   %cmp = icmp eq i8* %x, null
173   ret i1 %cmp
174 ; CHECK-NEXT: ret i1 false
175 }
176
177 define i1 @gep14({ {}, i8 }* %ptr) {
178 ; CHECK: @gep14
179 ; We can't simplify this because the offset of one in the GEP actually doesn't
180 ; move the pointer.
181   %x = getelementptr inbounds { {}, i8 }* %ptr, i32 0, i32 1
182   %cmp = icmp eq i8* %x, null
183   ret i1 %cmp
184 ; CHECK-NOT: ret i1 false
185 }
186
187 define i1 @gep15({ {}, [4 x {i8, i8}]}* %ptr, i32 %y) {
188 ; CHECK: @gep15
189 ; We can prove this GEP is non-null even though there is a user value, as we
190 ; would necessarily violate inbounds on one side or the other.
191   %x = getelementptr inbounds { {}, [4 x {i8, i8}]}* %ptr, i32 0, i32 1, i32 %y, i32 1
192   %cmp = icmp eq i8* %x, null
193   ret i1 %cmp
194 ; CHECK-NEXT: ret i1 false
195 }
196
197 define i1 @gep16(i8* %ptr, i32 %a) {
198 ; CHECK: @gep16
199 ; We can prove this GEP is non-null because it is inbounds and because we know
200 ; %b is non-zero even though we don't know its value.
201   %b = or i32 %a, 1
202   %x = getelementptr inbounds i8* %ptr, i32 %b
203   %cmp = icmp eq i8* %x, null
204   ret i1 %cmp
205 ; CHECK-NEXT: ret i1 false
206 }
207
208 define i1 @zext(i32 %x) {
209 ; CHECK: @zext
210   %e1 = zext i32 %x to i64
211   %e2 = zext i32 %x to i64
212   %r = icmp eq i64 %e1, %e2
213   ret i1 %r
214 ; CHECK: ret i1 true
215 }
216
217 define i1 @zext2(i1 %x) {
218 ; CHECK: @zext2
219   %e = zext i1 %x to i32
220   %c = icmp ne i32 %e, 0
221   ret i1 %c
222 ; CHECK: ret i1 %x
223 }
224
225 define i1 @zext3() {
226 ; CHECK: @zext3
227   %e = zext i1 1 to i32
228   %c = icmp ne i32 %e, 0
229   ret i1 %c
230 ; CHECK: ret i1 true
231 }
232
233 define i1 @sext(i32 %x) {
234 ; CHECK: @sext
235   %e1 = sext i32 %x to i64
236   %e2 = sext i32 %x to i64
237   %r = icmp eq i64 %e1, %e2
238   ret i1 %r
239 ; CHECK: ret i1 true
240 }
241
242 define i1 @sext2(i1 %x) {
243 ; CHECK: @sext2
244   %e = sext i1 %x to i32
245   %c = icmp ne i32 %e, 0
246   ret i1 %c
247 ; CHECK: ret i1 %x
248 }
249
250 define i1 @sext3() {
251 ; CHECK: @sext3
252   %e = sext i1 1 to i32
253   %c = icmp ne i32 %e, 0
254   ret i1 %c
255 ; CHECK: ret i1 true
256 }
257
258 define i1 @add(i32 %x, i32 %y) {
259 ; CHECK: @add
260   %l = lshr i32 %x, 1
261   %q = lshr i32 %y, 1
262   %r = or i32 %q, 1
263   %s = add i32 %l, %r
264   %c = icmp eq i32 %s, 0
265   ret i1 %c
266 ; CHECK: ret i1 false
267 }
268
269 define i1 @add2(i8 %x, i8 %y) {
270 ; CHECK: @add2
271   %l = or i8 %x, 128
272   %r = or i8 %y, 129
273   %s = add i8 %l, %r
274   %c = icmp eq i8 %s, 0
275   ret i1 %c
276 ; CHECK: ret i1 false
277 }
278
279 define i1 @add3(i8 %x, i8 %y) {
280 ; CHECK: @add3
281   %l = zext i8 %x to i32
282   %r = zext i8 %y to i32
283   %s = add i32 %l, %r
284   %c = icmp eq i32 %s, 0
285   ret i1 %c
286 ; CHECK: ret i1 %c
287 }
288
289 define i1 @add4(i32 %x, i32 %y) {
290 ; CHECK: @add4
291   %z = add nsw i32 %y, 1
292   %s1 = add nsw i32 %x, %y
293   %s2 = add nsw i32 %x, %z
294   %c = icmp slt i32 %s1, %s2
295   ret i1 %c
296 ; CHECK: ret i1 true
297 }
298
299 define i1 @add5(i32 %x, i32 %y) {
300 ; CHECK: @add5
301   %z = add nuw i32 %y, 1
302   %s1 = add nuw i32 %x, %z
303   %s2 = add nuw i32 %x, %y
304   %c = icmp ugt i32 %s1, %s2
305   ret i1 %c
306 ; CHECK: ret i1 true
307 }
308
309 define i1 @add6(i64 %A, i64 %B) {
310 ; CHECK: @add6
311   %s1 = add i64 %A, %B
312   %s2 = add i64 %B, %A
313   %cmp = icmp eq i64 %s1, %s2
314   ret i1 %cmp
315 ; CHECK: ret i1 true
316 }
317
318 define i1 @addpowtwo(i32 %x, i32 %y) {
319 ; CHECK: @addpowtwo
320   %l = lshr i32 %x, 1
321   %r = shl i32 1, %y
322   %s = add i32 %l, %r
323   %c = icmp eq i32 %s, 0
324   ret i1 %c
325 ; CHECK: ret i1 false
326 }
327
328 define i1 @or(i32 %x) {
329 ; CHECK: @or
330   %o = or i32 %x, 1
331   %c = icmp eq i32 %o, 0
332   ret i1 %c
333 ; CHECK: ret i1 false
334 }
335
336 define i1 @shl(i32 %x) {
337 ; CHECK: @shl
338   %s = shl i32 1, %x
339   %c = icmp eq i32 %s, 0
340   ret i1 %c
341 ; CHECK: ret i1 false
342 }
343
344 define i1 @lshr1(i32 %x) {
345 ; CHECK: @lshr1
346   %s = lshr i32 -1, %x
347   %c = icmp eq i32 %s, 0
348   ret i1 %c
349 ; CHECK: ret i1 false
350 }
351
352 define i1 @lshr2(i32 %x) {
353 ; CHECK: @lshr2
354   %s = lshr i32 %x, 30
355   %c = icmp ugt i32 %s, 8
356   ret i1 %c
357 ; CHECK: ret i1 false
358 }
359
360 define i1 @ashr1(i32 %x) {
361 ; CHECK: @ashr1
362   %s = ashr i32 -1, %x
363   %c = icmp eq i32 %s, 0
364   ret i1 %c
365 ; CHECK: ret i1 false
366 }
367
368 define i1 @ashr2(i32 %x) {
369 ; CHECK: @ashr2
370   %s = ashr i32 %x, 30
371   %c = icmp slt i32 %s, -5
372   ret i1 %c
373 ; CHECK: ret i1 false
374 }
375
376 define i1 @select1(i1 %cond) {
377 ; CHECK: @select1
378   %s = select i1 %cond, i32 1, i32 0
379   %c = icmp eq i32 %s, 1
380   ret i1 %c
381 ; CHECK: ret i1 %cond
382 }
383
384 define i1 @select2(i1 %cond) {
385 ; CHECK: @select2
386   %x = zext i1 %cond to i32
387   %s = select i1 %cond, i32 %x, i32 0
388   %c = icmp ne i32 %s, 0
389   ret i1 %c
390 ; CHECK: ret i1 %cond
391 }
392
393 define i1 @select3(i1 %cond) {
394 ; CHECK: @select3
395   %x = zext i1 %cond to i32
396   %s = select i1 %cond, i32 1, i32 %x
397   %c = icmp ne i32 %s, 0
398   ret i1 %c
399 ; CHECK: ret i1 %cond
400 }
401
402 define i1 @select4(i1 %cond) {
403 ; CHECK: @select4
404   %invert = xor i1 %cond, 1
405   %s = select i1 %invert, i32 0, i32 1
406   %c = icmp ne i32 %s, 0
407   ret i1 %c
408 ; CHECK: ret i1 %cond
409 }
410
411 define i1 @select5(i32 %x) {
412 ; CHECK: @select5
413   %c = icmp eq i32 %x, 0
414   %s = select i1 %c, i32 1, i32 %x
415   %c2 = icmp eq i32 %s, 0
416   ret i1 %c2
417 ; CHECK: ret i1 false
418 }
419
420 define i1 @select6(i32 %x) {
421 ; CHECK: @select6
422   %c = icmp sgt i32 %x, 0
423   %s = select i1 %c, i32 %x, i32 4
424   %c2 = icmp eq i32 %s, 0
425   ret i1 %c2
426 ; CHECK: ret i1 %c2
427 }
428
429 define i1 @urem1(i32 %X, i32 %Y) {
430 ; CHECK: @urem1
431   %A = urem i32 %X, %Y
432   %B = icmp ult i32 %A, %Y
433   ret i1 %B
434 ; CHECK: ret i1 true
435 }
436
437 define i1 @urem2(i32 %X, i32 %Y) {
438 ; CHECK: @urem2
439   %A = urem i32 %X, %Y
440   %B = icmp eq i32 %A, %Y
441   ret i1 %B
442 ; CHECK: ret i1 false
443 }
444
445 define i1 @urem3(i32 %X) {
446 ; CHECK: @urem3
447   %A = urem i32 %X, 10
448   %B = icmp ult i32 %A, 15
449   ret i1 %B
450 ; CHECK: ret i1 true
451 }
452
453 define i1 @urem4(i32 %X) {
454 ; CHECK: @urem4
455   %A = urem i32 %X, 15
456   %B = icmp ult i32 %A, 10
457   ret i1 %B
458 ; CHECK: ret i1 %B
459 }
460
461 define i1 @urem5(i16 %X, i32 %Y) {
462 ; CHECK: @urem5
463   %A = zext i16 %X to i32
464   %B = urem i32 %A, %Y
465   %C = icmp slt i32 %B, %Y
466   ret i1 %C
467 ; CHECK: ret i1 true
468 }
469
470 define i1 @urem6(i32 %X, i32 %Y) {
471 ; CHECK: @urem6
472   %A = urem i32 %X, %Y
473   %B = icmp ugt i32 %Y, %A
474   ret i1 %B
475 ; CHECK: ret i1 true
476 }
477
478 define i1 @srem1(i32 %X) {
479 ; CHECK: @srem1
480   %A = srem i32 %X, -5
481   %B = icmp sgt i32 %A, 5
482   ret i1 %B
483 ; CHECK: ret i1 false
484 }
485
486 ; PR9343 #15
487 ; CHECK: @srem2
488 ; CHECK: ret i1 false
489 define i1 @srem2(i16 %X, i32 %Y) {
490   %A = zext i16 %X to i32
491   %B = add nsw i32 %A, 1
492   %C = srem i32 %B, %Y
493   %D = icmp slt i32 %C, 0
494   ret i1 %D
495 }
496
497 ; CHECK: @srem3
498 ; CHECK-NEXT: ret i1 false
499 define i1 @srem3(i16 %X, i32 %Y) {
500   %A = zext i16 %X to i32
501   %B = or i32 2147483648, %A
502   %C = sub nsw i32 1, %B
503   %D = srem i32 %C, %Y
504   %E = icmp slt i32 %D, 0
505   ret i1 %E
506 }
507
508 define i1 @udiv1(i32 %X) {
509 ; CHECK: @udiv1
510   %A = udiv i32 %X, 1000000
511   %B = icmp ult i32 %A, 5000
512   ret i1 %B
513 ; CHECK: ret i1 true
514 }
515
516 define i1 @udiv2(i32 %X, i32 %Y, i32 %Z) {
517 ; CHECK: @udiv2
518   %A = udiv exact i32 10, %Z
519   %B = udiv exact i32 20, %Z
520   %C = icmp ult i32 %A, %B
521   ret i1 %C
522 ; CHECK: ret i1 true
523 }
524
525 define i1 @udiv3(i32 %X, i32 %Y) {
526 ; CHECK: @udiv3
527   %A = udiv i32 %X, %Y
528   %C = icmp ugt i32 %A, %X
529   ret i1 %C
530 ; CHECK: ret i1 false
531 }
532
533 define i1 @udiv4(i32 %X, i32 %Y) {
534 ; CHECK: @udiv4
535   %A = udiv i32 %X, %Y
536   %C = icmp ule i32 %A, %X
537   ret i1 %C
538 ; CHECK: ret i1 true
539 }
540
541 define i1 @udiv5(i32 %X) {
542 ; CHECK: @udiv5
543   %A = udiv i32 123, %X
544   %C = icmp ugt i32 %A, 124
545   ret i1 %C
546 ; CHECK: ret i1 false
547 }
548
549 ; PR11340
550 define i1 @udiv6(i32 %X) nounwind {
551 ; CHECK: @udiv6
552   %A = udiv i32 1, %X
553   %C = icmp eq i32 %A, 0
554   ret i1 %C
555 ; CHECK: ret i1 %C
556 }
557
558
559 define i1 @sdiv1(i32 %X) {
560 ; CHECK: @sdiv1
561   %A = sdiv i32 %X, 1000000
562   %B = icmp slt i32 %A, 3000
563   ret i1 %B
564 ; CHECK: ret i1 true
565 }
566
567 define i1 @or1(i32 %X) {
568 ; CHECK: @or1
569   %A = or i32 %X, 62
570   %B = icmp ult i32 %A, 50
571   ret i1 %B
572 ; CHECK: ret i1 false
573 }
574
575 define i1 @and1(i32 %X) {
576 ; CHECK: @and1
577   %A = and i32 %X, 62
578   %B = icmp ugt i32 %A, 70
579   ret i1 %B
580 ; CHECK: ret i1 false
581 }
582
583 define i1 @mul1(i32 %X) {
584 ; CHECK: @mul1
585 ; Square of a non-zero number is non-zero if there is no overflow.
586   %Y = or i32 %X, 1
587   %M = mul nuw i32 %Y, %Y
588   %C = icmp eq i32 %M, 0
589   ret i1 %C
590 ; CHECK: ret i1 false
591 }
592
593 define i1 @mul2(i32 %X) {
594 ; CHECK: @mul2
595 ; Square of a non-zero number is positive if there is no signed overflow.
596   %Y = or i32 %X, 1
597   %M = mul nsw i32 %Y, %Y
598   %C = icmp sgt i32 %M, 0
599   ret i1 %C
600 ; CHECK: ret i1 true
601 }
602
603 define i1 @mul3(i32 %X, i32 %Y) {
604 ; CHECK: @mul3
605 ; Product of non-negative numbers is non-negative if there is no signed overflow.
606   %XX = mul nsw i32 %X, %X
607   %YY = mul nsw i32 %Y, %Y
608   %M = mul nsw i32 %XX, %YY
609   %C = icmp sge i32 %M, 0
610   ret i1 %C
611 ; CHECK: ret i1 true
612 }
613
614 define <2 x i1> @vectorselect1(<2 x i1> %cond) {
615 ; CHECK: @vectorselect1
616   %invert = xor <2 x i1> %cond, <i1 1, i1 1>
617   %s = select <2 x i1> %invert, <2 x i32> <i32 0, i32 0>, <2 x i32> <i32 1, i32 1>
618   %c = icmp ne <2 x i32> %s, <i32 0, i32 0>
619   ret <2 x i1> %c
620 ; CHECK: ret <2 x i1> %cond
621 }
622
623 ; PR11948
624 define <2 x i1> @vectorselectcrash(i32 %arg1) {
625   %tobool40 = icmp ne i32 %arg1, 0
626   %cond43 = select i1 %tobool40, <2 x i16> <i16 -5, i16 66>, <2 x i16> <i16 46, i16 1>
627   %cmp45 = icmp ugt <2 x i16> %cond43, <i16 73, i16 21>
628   ret <2 x i1> %cmp45
629 }
630
631 ; PR12013
632 define i1 @alloca_compare(i64 %idx) {
633   %sv = alloca { i32, i32, [124 x i32] }
634   %1 = getelementptr inbounds { i32, i32, [124 x i32] }* %sv, i32 0, i32 2, i64 %idx
635   %2 = icmp eq i32* %1, null
636   ret i1 %2
637   ; CHECK: alloca_compare
638   ; CHECK: ret i1 false
639 }
640
641 ; PR12075
642 define i1 @infinite_gep() {
643   ret i1 1
644
645 unreachableblock:
646   %X = getelementptr i32 *%X, i32 1
647   %Y = icmp eq i32* %X, null
648   ret i1 %Y
649 }