Teach ComputeNumSignBits about signed divisions.
[oota-llvm.git] / test / Transforms / InstCombine / intrinsics.ll
1 ; RUN: opt -instcombine -S < %s | FileCheck %s
2
3 %overflow.result = type {i8, i1}
4 %ov.result.32 = type { i32, i1 }
5
6
7 declare %overflow.result @llvm.uadd.with.overflow.i8(i8, i8) nounwind readnone
8 declare %overflow.result @llvm.umul.with.overflow.i8(i8, i8) nounwind readnone
9 declare %ov.result.32 @llvm.sadd.with.overflow.i32(i32, i32) nounwind readnone
10 declare %ov.result.32 @llvm.uadd.with.overflow.i32(i32, i32) nounwind readnone
11 declare %ov.result.32 @llvm.ssub.with.overflow.i32(i32, i32) nounwind readnone
12 declare %ov.result.32 @llvm.usub.with.overflow.i32(i32, i32) nounwind readnone
13 declare %ov.result.32 @llvm.smul.with.overflow.i32(i32, i32) nounwind readnone
14 declare %ov.result.32 @llvm.umul.with.overflow.i32(i32, i32) nounwind readnone
15 declare double @llvm.powi.f64(double, i32) nounwind readonly
16 declare i32 @llvm.cttz.i32(i32, i1) nounwind readnone
17 declare i32 @llvm.ctlz.i32(i32, i1) nounwind readnone
18 declare i32 @llvm.ctpop.i32(i32) nounwind readnone
19 declare i8 @llvm.ctlz.i8(i8, i1) nounwind readnone
20
21 define i8 @uaddtest1(i8 %A, i8 %B) {
22   %x = call %overflow.result @llvm.uadd.with.overflow.i8(i8 %A, i8 %B)
23   %y = extractvalue %overflow.result %x, 0
24   ret i8 %y
25 ; CHECK-LABEL: @uaddtest1(
26 ; CHECK-NEXT: %y = add i8 %A, %B
27 ; CHECK-NEXT: ret i8 %y
28 }
29
30 define i8 @uaddtest2(i8 %A, i8 %B, i1* %overflowPtr) {
31   %and.A = and i8 %A, 127
32   %and.B = and i8 %B, 127
33   %x = call %overflow.result @llvm.uadd.with.overflow.i8(i8 %and.A, i8 %and.B)
34   %y = extractvalue %overflow.result %x, 0
35   %z = extractvalue %overflow.result %x, 1
36   store i1 %z, i1* %overflowPtr
37   ret i8 %y
38 ; CHECK-LABEL: @uaddtest2(
39 ; CHECK-NEXT: %and.A = and i8 %A, 127
40 ; CHECK-NEXT: %and.B = and i8 %B, 127
41 ; CHECK-NEXT: %x = add nuw i8 %and.A, %and.B
42 ; CHECK-NEXT: store i1 false, i1* %overflowPtr
43 ; CHECK-NEXT: ret i8 %x
44 }
45
46 define i8 @uaddtest3(i8 %A, i8 %B, i1* %overflowPtr) {
47   %or.A = or i8 %A, -128
48   %or.B = or i8 %B, -128
49   %x = call %overflow.result @llvm.uadd.with.overflow.i8(i8 %or.A, i8 %or.B)
50   %y = extractvalue %overflow.result %x, 0
51   %z = extractvalue %overflow.result %x, 1
52   store i1 %z, i1* %overflowPtr
53   ret i8 %y
54 ; CHECK-LABEL: @uaddtest3(
55 ; CHECK-NEXT: %or.A = or i8 %A, -128
56 ; CHECK-NEXT: %or.B = or i8 %B, -128
57 ; CHECK-NEXT: %x = add i8 %or.A, %or.B
58 ; CHECK-NEXT: store i1 true, i1* %overflowPtr
59 ; CHECK-NEXT: ret i8 %x
60 }
61
62 define i8 @uaddtest4(i8 %A, i1* %overflowPtr) {
63   %x = call %overflow.result @llvm.uadd.with.overflow.i8(i8 undef, i8 %A)
64   %y = extractvalue %overflow.result %x, 0
65   %z = extractvalue %overflow.result %x, 1
66   store i1 %z, i1* %overflowPtr
67   ret i8 %y
68 ; CHECK-LABEL: @uaddtest4(
69 ; CHECK-NEXT: ret i8 undef
70 }
71
72 define i8 @uaddtest5(i8 %A, i1* %overflowPtr) {
73   %x = call %overflow.result @llvm.uadd.with.overflow.i8(i8 0, i8 %A)
74   %y = extractvalue %overflow.result %x, 0
75   %z = extractvalue %overflow.result %x, 1
76   store i1 %z, i1* %overflowPtr
77   ret i8 %y
78 ; CHECK-LABEL: @uaddtest5(
79 ; CHECK: ret i8 %A
80 }
81
82 define i1 @uaddtest6(i8 %A, i8 %B) {
83   %x = call %overflow.result @llvm.uadd.with.overflow.i8(i8 %A, i8 -4)
84   %z = extractvalue %overflow.result %x, 1
85   ret i1 %z
86 ; CHECK-LABEL: @uaddtest6(
87 ; CHECK-NEXT: %z = icmp ugt i8 %A, 3
88 ; CHECK-NEXT: ret i1 %z
89 }
90
91 define i8 @uaddtest7(i8 %A, i8 %B) {
92   %x = call %overflow.result @llvm.uadd.with.overflow.i8(i8 %A, i8 %B)
93   %z = extractvalue %overflow.result %x, 0
94   ret i8 %z
95 ; CHECK-LABEL: @uaddtest7(
96 ; CHECK-NEXT: %z = add i8 %A, %B
97 ; CHECK-NEXT: ret i8 %z
98 }
99
100 ; PR20194
101 define %ov.result.32 @saddtest_nsw(i8 %a, i8 %b) {
102   %A = sext i8 %a to i32
103   %B = sext i8 %b to i32
104   %x = call %ov.result.32 @llvm.sadd.with.overflow.i32(i32 %A, i32 %B)
105   ret %ov.result.32 %x
106 ; CHECK-LABEL: @saddtest_nsw
107 ; CHECK: %x = add nsw i32 %A, %B
108 ; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0
109 ; CHECK-NEXT:  ret %ov.result.32 %1
110 }
111
112 define %ov.result.32 @uaddtest_nuw(i32 %a, i32 %b) {
113   %A = and i32 %a, 2147483647
114   %B = and i32 %b, 2147483647
115   %x = call %ov.result.32 @llvm.uadd.with.overflow.i32(i32 %A, i32 %B)
116   ret %ov.result.32 %x
117 ; CHECK-LABEL: @uaddtest_nuw
118 ; CHECK: %x = add nuw i32 %A, %B
119 ; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0
120 ; CHECK-NEXT:  ret %ov.result.32 %1
121 }
122
123 define %ov.result.32 @ssubtest_nsw(i8 %a, i8 %b) {
124   %A = sext i8 %a to i32
125   %B = sext i8 %b to i32
126   %x = call %ov.result.32 @llvm.ssub.with.overflow.i32(i32 %A, i32 %B)
127   ret %ov.result.32 %x
128 ; CHECK-LABEL: @ssubtest_nsw
129 ; CHECK: %x = sub nsw i32 %A, %B
130 ; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0
131 ; CHECK-NEXT:  ret %ov.result.32 %1
132 }
133
134 define %ov.result.32 @usubtest_nuw(i32 %a, i32 %b) {
135   %A = or i32 %a, 2147483648
136   %B = and i32 %b, 2147483647
137   %x = call %ov.result.32 @llvm.usub.with.overflow.i32(i32 %A, i32 %B)
138   ret %ov.result.32 %x
139 ; CHECK-LABEL: @usubtest_nuw
140 ; CHECK: %x = sub nuw i32 %A, %B
141 ; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0
142 ; CHECK-NEXT:  ret %ov.result.32 %1
143 }
144
145 define %ov.result.32 @smultest1_nsw(i32 %a, i32 %b) {
146   %A = and i32 %a, 4095 ; 0xfff
147   %B = and i32 %b, 524287; 0x7ffff
148   %x = call %ov.result.32 @llvm.smul.with.overflow.i32(i32 %A, i32 %B)
149   ret %ov.result.32 %x
150 ; CHECK-LABEL: @smultest1_nsw
151 ; CHECK: %x = mul nuw nsw i32 %A, %B
152 ; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0
153 ; CHECK-NEXT:  ret %ov.result.32 %1
154 }
155
156 define %ov.result.32 @smultest2_nsw(i32 %a, i32 %b) {
157   %A = ashr i32 %a, 16
158   %B = ashr i32 %b, 16
159   %x = call %ov.result.32 @llvm.smul.with.overflow.i32(i32 %A, i32 %B)
160   ret %ov.result.32 %x
161 ; CHECK-LABEL: @smultest2_nsw
162 ; CHECK: %x = mul nsw i32 %A, %B
163 ; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0
164 ; CHECK-NEXT:  ret %ov.result.32 %1
165 }
166
167 define %ov.result.32 @smultest3_sw(i32 %a, i32 %b) {
168   %A = ashr i32 %a, 16
169   %B = ashr i32 %b, 15
170   %x = call %ov.result.32 @llvm.smul.with.overflow.i32(i32 %A, i32 %B)
171   ret %ov.result.32 %x
172 ; CHECK-LABEL: @smultest3_sw
173 ; CHECK: %x = call %ov.result.32 @llvm.smul.with.overflow.i32(i32 %A, i32 %B)
174 ; CHECK-NEXT:  ret %ov.result.32 %x
175 }
176
177 define %ov.result.32 @umultest_nuw(i32 %a, i32 %b) {
178   %A = and i32 %a, 65535 ; 0xffff
179   %B = and i32 %b, 65535 ; 0xffff
180   %x = call %ov.result.32 @llvm.umul.with.overflow.i32(i32 %A, i32 %B)
181   ret %ov.result.32 %x
182 ; CHECK-LABEL: @umultest_nuw
183 ; CHECK: %x = mul nuw i32 %A, %B
184 ; CHECK-NEXT: %1 = insertvalue %ov.result.32 { i32 undef, i1 false }, i32 %x, 0
185 ; CHECK-NEXT:  ret %ov.result.32 %1
186 }
187
188 define i8 @umultest1(i8 %A, i1* %overflowPtr) {
189   %x = call %overflow.result @llvm.umul.with.overflow.i8(i8 0, i8 %A)
190   %y = extractvalue %overflow.result %x, 0
191   %z = extractvalue %overflow.result %x, 1
192   store i1 %z, i1* %overflowPtr
193   ret i8 %y
194 ; CHECK-LABEL: @umultest1(
195 ; CHECK-NEXT: store i1 false, i1* %overflowPtr
196 ; CHECK-NEXT: ret i8 0
197 }
198
199 define i8 @umultest2(i8 %A, i1* %overflowPtr) {
200   %x = call %overflow.result @llvm.umul.with.overflow.i8(i8 1, i8 %A)
201   %y = extractvalue %overflow.result %x, 0
202   %z = extractvalue %overflow.result %x, 1
203   store i1 %z, i1* %overflowPtr
204   ret i8 %y
205 ; CHECK-LABEL: @umultest2(
206 ; CHECK-NEXT: store i1 false, i1* %overflowPtr
207 ; CHECK-NEXT: ret i8 %A
208 }
209
210 define i32 @umultest3(i32 %n) nounwind {
211   %shr = lshr i32 %n, 2
212   %mul = call %ov.result.32 @llvm.umul.with.overflow.i32(i32 %shr, i32 3)
213   %ov = extractvalue %ov.result.32 %mul, 1
214   %res = extractvalue %ov.result.32 %mul, 0
215   %ret = select i1 %ov, i32 -1, i32 %res
216   ret i32 %ret
217 ; CHECK-LABEL: @umultest3(
218 ; CHECK-NEXT: shr
219 ; CHECK-NEXT: mul nuw
220 ; CHECK-NEXT: ret
221 }
222
223 define i32 @umultest4(i32 %n) nounwind {
224   %shr = lshr i32 %n, 1
225   %mul = call %ov.result.32 @llvm.umul.with.overflow.i32(i32 %shr, i32 4)
226   %ov = extractvalue %ov.result.32 %mul, 1
227   %res = extractvalue %ov.result.32 %mul, 0
228   %ret = select i1 %ov, i32 -1, i32 %res
229   ret i32 %ret
230 ; CHECK-LABEL: @umultest4(
231 ; CHECK: umul.with.overflow
232 }
233
234 define %ov.result.32 @umultest5(i32 %x, i32 %y) nounwind {
235   %or_x = or i32 %x, 2147483648
236   %or_y = or i32 %y, 2147483648
237   %mul = call %ov.result.32 @llvm.umul.with.overflow.i32(i32 %or_x, i32 %or_y)
238   ret %ov.result.32 %mul
239 ; CHECK-LABEL: @umultest5(
240 ; CHECK-NEXT: %[[or_x:.*]] = or i32 %x, -2147483648
241 ; CHECK-NEXT: %[[or_y:.*]] = or i32 %y, -2147483648
242 ; CHECK-NEXT: %[[mul:.*]] = mul i32 %[[or_x]], %[[or_y]]
243 ; CHECK-NEXT: %[[ret:.*]] = insertvalue %ov.result.32 { i32 undef, i1 true }, i32 %[[mul]], 0
244 ; CHECK-NEXT: ret %ov.result.32 %[[ret]]
245 }
246
247 define void @powi(double %V, double *%P) {
248 entry:
249   %A = tail call double @llvm.powi.f64(double %V, i32 -1) nounwind
250   store volatile double %A, double* %P
251
252   %B = tail call double @llvm.powi.f64(double %V, i32 0) nounwind
253   store volatile double %B, double* %P
254
255   %C = tail call double @llvm.powi.f64(double %V, i32 1) nounwind
256   store volatile double %C, double* %P
257   ret void
258 ; CHECK-LABEL: @powi(
259 ; CHECK: %A = fdiv double 1.0{{.*}}, %V
260 ; CHECK: store volatile double %A, 
261 ; CHECK: store volatile double 1.0 
262 ; CHECK: store volatile double %V
263 }
264
265 define i32 @cttz(i32 %a) {
266 entry:
267   %or = or i32 %a, 8
268   %and = and i32 %or, -8
269   %count = tail call i32 @llvm.cttz.i32(i32 %and, i1 true) nounwind readnone
270   ret i32 %count
271 ; CHECK-LABEL: @cttz(
272 ; CHECK-NEXT: entry:
273 ; CHECK-NEXT: ret i32 3
274 }
275
276 define i8 @ctlz(i8 %a) {
277 entry:
278   %or = or i8 %a, 32
279   %and = and i8 %or, 63
280   %count = tail call i8 @llvm.ctlz.i8(i8 %and, i1 true) nounwind readnone
281   ret i8 %count
282 ; CHECK-LABEL: @ctlz(
283 ; CHECK-NEXT: entry:
284 ; CHECK-NEXT: ret i8 2
285 }
286
287 define void @cmp.simplify(i32 %a, i32 %b, i1* %c) {
288 entry:
289   %lz = tail call i32 @llvm.ctlz.i32(i32 %a, i1 false) nounwind readnone
290   %lz.cmp = icmp eq i32 %lz, 32
291   store volatile i1 %lz.cmp, i1* %c
292   %tz = tail call i32 @llvm.cttz.i32(i32 %a, i1 false) nounwind readnone
293   %tz.cmp = icmp ne i32 %tz, 32
294   store volatile i1 %tz.cmp, i1* %c
295   %pop = tail call i32 @llvm.ctpop.i32(i32 %b) nounwind readnone
296   %pop.cmp = icmp eq i32 %pop, 0
297   store volatile i1 %pop.cmp, i1* %c
298   ret void
299 ; CHECK: @cmp.simplify
300 ; CHECK-NEXT: entry:
301 ; CHECK-NEXT: %lz.cmp = icmp eq i32 %a, 0
302 ; CHECK-NEXT: store volatile i1 %lz.cmp, i1* %c
303 ; CHECK-NEXT: %tz.cmp = icmp ne i32 %a, 0
304 ; CHECK-NEXT: store volatile i1 %tz.cmp, i1* %c
305 ; CHECK-NEXT: %pop.cmp = icmp eq i32 %b, 0
306 ; CHECK-NEXT: store volatile i1 %pop.cmp, i1* %c
307 }
308
309 define i32 @cttz_simplify1a(i32 %x) nounwind readnone ssp {
310   %tmp1 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 false)
311   %shr3 = lshr i32 %tmp1, 5
312   ret i32 %shr3
313
314 ; CHECK-LABEL: @cttz_simplify1a(
315 ; CHECK: icmp eq i32 %x, 0
316 ; CHECK-NEXT: zext i1
317 ; CHECK-NEXT: ret i32
318 }
319
320 define i32 @cttz_simplify1b(i32 %x) nounwind readnone ssp {
321   %tmp1 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
322   %shr3 = lshr i32 %tmp1, 5
323   ret i32 %shr3
324
325 ; CHECK-LABEL: @cttz_simplify1b(
326 ; CHECK-NEXT: ret i32 0
327 }
328
329 define i32 @ctlz_undef(i32 %Value) nounwind {
330   %ctlz = call i32 @llvm.ctlz.i32(i32 0, i1 true)
331   ret i32 %ctlz
332
333 ; CHECK-LABEL: @ctlz_undef(
334 ; CHECK-NEXT: ret i32 undef
335 }
336
337 define i32 @cttz_undef(i32 %Value) nounwind {
338   %cttz = call i32 @llvm.cttz.i32(i32 0, i1 true)
339   ret i32 %cttz
340
341 ; CHECK-LABEL: @cttz_undef(
342 ; CHECK-NEXT: ret i32 undef
343 }
344
345 define i32 @ctlz_select(i32 %Value) nounwind {
346   %tobool = icmp ne i32 %Value, 0
347   %ctlz = call i32 @llvm.ctlz.i32(i32 %Value, i1 true)
348   %s = select i1 %tobool, i32 %ctlz, i32 32
349   ret i32 %s
350
351 ; CHECK-LABEL: @ctlz_select(
352 ; CHECK-NEXT: call i32 @llvm.ctlz.i32(i32 %Value, i1 false)
353 ; CHECK-NEXT: ret i32
354 }
355
356 define i32 @cttz_select(i32 %Value) nounwind {
357   %tobool = icmp ne i32 %Value, 0
358   %cttz = call i32 @llvm.cttz.i32(i32 %Value, i1 true)
359   %s = select i1 %tobool, i32 %cttz, i32 32
360   ret i32 %s
361
362 ; CHECK-LABEL: @cttz_select(
363 ; CHECK-NEXT: call i32 @llvm.cttz.i32(i32 %Value, i1 false)
364 ; CHECK-NEXT: ret i32
365 }
366
367 ; CHECK-LABEL: @overflow_div_add(
368 ; CHECK: ret i1 false
369 define i1 @overflow_div_add(i32 %v1, i32 %v2) nounwind {
370 entry:
371   %div = sdiv i32 %v1, 2
372   %t = call %ov.result.32 @llvm.sadd.with.overflow.i32(i32 %div, i32 1)
373   %obit = extractvalue %ov.result.32 %t, 1
374   ret i1 %obit
375 }
376
377 ; CHECK-LABEL: @overflow_div_sub(
378 ; CHECK: ret i1 false
379 define i1 @overflow_div_sub(i32 %v1, i32 %v2) nounwind {
380 entry:
381   ; Check cases where the known sign bits are larger than the word size.
382   %a = ashr i32 %v1, 18
383   %div = sdiv i32 %a, 65536
384   %t = call %ov.result.32 @llvm.ssub.with.overflow.i32(i32 %div, i32 1)
385   %obit = extractvalue %ov.result.32 %t, 1
386   ret i1 %obit
387 }
388