[DAGCombiner] Add target hook function to decide folding (mul (add x, c1), c2)
[llvm-project.git] / llvm / test / Transforms / InstCombine / add2.ll
blobed99936e081e62caa39997346fac5606b57c1fa2
1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2 ; RUN: opt < %s -instcombine -S | FileCheck %s
4 define i64 @test1(i64 %A, i32 %B) {
5 ; CHECK-LABEL: @test1(
6 ; CHECK-NEXT:    [[TMP6:%.*]] = and i64 [[A:%.*]], 123
7 ; CHECK-NEXT:    ret i64 [[TMP6]]
9   %tmp12 = zext i32 %B to i64
10   %tmp3 = shl i64 %tmp12, 32
11   %tmp5 = add i64 %tmp3, %A
12   %tmp6 = and i64 %tmp5, 123
13   ret i64 %tmp6
16 define i32 @test2(i32 %A) {
17 ; CHECK-LABEL: @test2(
18 ; CHECK-NEXT:    [[F:%.*]] = and i32 [[A:%.*]], 39
19 ; CHECK-NEXT:    ret i32 [[F]]
21   %B = and i32 %A, 7
22   %C = and i32 %A, 32
23   %F = add i32 %B, %C
24   ret i32 %F
27 define i32 @test3(i32 %A) {
28 ; CHECK-LABEL: @test3(
29 ; CHECK-NEXT:    [[B:%.*]] = and i32 [[A:%.*]], 128
30 ; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[A]], 30
31 ; CHECK-NEXT:    [[F:%.*]] = or i32 [[B]], [[C]]
32 ; CHECK-NEXT:    ret i32 [[F]]
34   %B = and i32 %A, 128
35   %C = lshr i32 %A, 30
36   %F = add i32 %B, %C
37   ret i32 %F
40 define i32 @test4(i32 %A) {
41 ; CHECK-LABEL: @test4(
42 ; CHECK-NEXT:    [[B:%.*]] = shl nuw i32 [[A:%.*]], 1
43 ; CHECK-NEXT:    ret i32 [[B]]
45   %B = add nuw i32 %A, %A
46   ret i32 %B
49 define <2 x i1> @test5(<2 x i1> %A, <2 x i1> %B) {
50 ; CHECK-LABEL: @test5(
51 ; CHECK-NEXT:    [[ADD:%.*]] = xor <2 x i1> [[A:%.*]], [[B:%.*]]
52 ; CHECK-NEXT:    ret <2 x i1> [[ADD]]
54   %add = add <2 x i1> %A, %B
55   ret <2 x i1> %add
58 define <2 x i64> @test6(<2 x i64> %A) {
59 ; CHECK-LABEL: @test6(
60 ; CHECK-NEXT:    [[ADD:%.*]] = mul <2 x i64> [[A:%.*]], <i64 5, i64 9>
61 ; CHECK-NEXT:    ret <2 x i64> [[ADD]]
63   %shl = shl <2 x i64> %A, <i64 2, i64 3>
64   %add = add <2 x i64> %shl, %A
65   ret <2 x i64> %add
68 define <2 x i64> @test7(<2 x i64> %A) {
69 ; CHECK-LABEL: @test7(
70 ; CHECK-NEXT:    [[ADD:%.*]] = mul <2 x i64> [[A:%.*]], <i64 7, i64 12>
71 ; CHECK-NEXT:    ret <2 x i64> [[ADD]]
73   %shl = shl <2 x i64> %A, <i64 2, i64 3>
74   %mul = mul <2 x i64> %A, <i64 3, i64 4>
75   %add = add <2 x i64> %shl, %mul
76   ret <2 x i64> %add
79 define i16 @test9(i16 %a) {
80 ; CHECK-LABEL: @test9(
81 ; CHECK-NEXT:    [[D:%.*]] = mul i16 [[A:%.*]], -32767
82 ; CHECK-NEXT:    ret i16 [[D]]
84   %b = mul i16 %a, 2
85   %c = mul i16 %a, 32767
86   %d = add i16 %b, %c
87   ret i16 %d
90 ; y + (~((x >> 3) & 0x55555555) + 1) -> y - ((x >> 3) & 0x55555555)
91 define i32 @test10(i32 %x, i32 %y) {
92 ; CHECK-LABEL: @test10(
93 ; CHECK-NEXT:    [[SHR:%.*]] = ashr i32 [[X:%.*]], 3
94 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[SHR]], 1431655765
95 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]
96 ; CHECK-NEXT:    ret i32 [[SUB]]
98   %shr = ashr i32 %x, 3
99   %shr.not = or i32 %shr, -1431655766
100   %neg = xor i32 %shr.not, 1431655765
101   %add = add i32 %y, 1
102   %add1 = add i32 %add, %neg
103   ret i32 %add1
106 ; y + (~(x & 0x55555555) + 1) -> y - (x & 0x55555555)
107 define i32 @test11(i32 %x, i32 %y) {
108 ; CHECK-LABEL: @test11(
109 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655765
110 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]
111 ; CHECK-NEXT:    ret i32 [[SUB]]
113   %x.not = or i32 %x, -1431655766
114   %neg = xor i32 %x.not, 1431655765
115   %add = add i32 %y, 1
116   %add1 = add i32 %add, %neg
117   ret i32 %add1
120 ; (y + 1) + ~(x & 0x55555555) -> y - (x & 0x55555555)
121 define i32 @test12(i32 %x, i32 %y) {
122 ; CHECK-LABEL: @test12(
123 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655765
124 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]
125 ; CHECK-NEXT:    ret i32 [[SUB]]
127   %add = add nsw i32 %y, 1
128   %x.not = or i32 %x, -1431655766
129   %neg = xor i32 %x.not, 1431655765
130   %add1 = add nsw i32 %add, %neg
131   ret i32 %add1
134 ; y + (~(x & 0x55555556) + 1) -> y - (x & 0x55555556)
135 define i32 @test13(i32 %x, i32 %y) {
136 ; CHECK-LABEL: @test13(
137 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655766
138 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]
139 ; CHECK-NEXT:    ret i32 [[SUB]]
141   %x.not = or i32 %x, -1431655767
142   %neg = xor i32 %x.not, 1431655766
143   %add = add i32 %y, 1
144   %add1 = add i32 %add, %neg
145   ret i32 %add1
148 ; (y + 1) + ~(x & 0x55555556) -> y - (x & 0x55555556)
149 define i32 @test14(i32 %x, i32 %y) {
150 ; CHECK-LABEL: @test14(
151 ; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655766
152 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]
153 ; CHECK-NEXT:    ret i32 [[SUB]]
155   %add = add nsw i32 %y, 1
156   %x.not = or i32 %x, -1431655767
157   %neg = xor i32 %x.not, 1431655766
158   %add1 = add nsw i32 %add, %neg
159   ret i32 %add1
162 ; y + (~(x | 0x55555556) + 1) -> y - (x | 0x55555556)
163 define i32 @test15(i32 %x, i32 %y) {
164 ; CHECK-LABEL: @test15(
165 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[X:%.*]], 1431655766
166 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]
167 ; CHECK-NEXT:    ret i32 [[SUB]]
169   %x.not = and i32 %x, -1431655767
170   %neg = xor i32 %x.not, -1431655767
171   %add = add i32 %y, 1
172   %add1 = add i32 %add, %neg
173   ret i32 %add1
176 ; (y + 1) + ~(x | 0x55555556) -> y - (x | 0x555555556)
177 define i32 @test16(i32 %x, i32 %y) {
178 ; CHECK-LABEL: @test16(
179 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[X:%.*]], 1431655766
180 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]
181 ; CHECK-NEXT:    ret i32 [[SUB]]
183   %add = add nsw i32 %y, 1
184   %x.not = and i32 %x, -1431655767
185   %neg = xor i32 %x.not, -1431655767
186   %add1 = add nsw i32 %add, %neg
187   ret i32 %add1
190 ; y + (~(x | 0x55555555) + 1) -> y - (x | 0x55555555)
191 define i32 @test17(i32 %x, i32 %y) {
192 ; CHECK-LABEL: @test17(
193 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[X:%.*]], 1431655765
194 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]
195 ; CHECK-NEXT:    ret i32 [[SUB]]
197   %x.not = and i32 %x, -1431655766
198   %add2 = xor i32 %x.not, -1431655765
199   %add1 = add nsw i32 %add2, %y
200   ret i32 %add1
203 ; (y + 1) + ~(x | 0x55555555) -> y - (x | 0x55555555)
204 define i32 @test18(i32 %x, i32 %y) {
205 ; CHECK-LABEL: @test18(
206 ; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[X:%.*]], 1431655765
207 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]]
208 ; CHECK-NEXT:    ret i32 [[SUB]]
210   %add = add nsw i32 %y, 1
211   %x.not = and i32 %x, -1431655766
212   %neg = xor i32 %x.not, -1431655766
213   %add1 = add nsw i32 %add, %neg
214   ret i32 %add1
217 define i16 @add_nsw_mul_nsw(i16 %x) {
218 ; CHECK-LABEL: @add_nsw_mul_nsw(
219 ; CHECK-NEXT:    [[ADD2:%.*]] = mul nsw i16 [[X:%.*]], 3
220 ; CHECK-NEXT:    ret i16 [[ADD2]]
222   %add1 = add nsw i16 %x, %x
223   %add2 = add nsw i16 %add1, %x
224   ret i16 %add2
227 define i16 @mul_add_to_mul_1(i16 %x) {
228 ; CHECK-LABEL: @mul_add_to_mul_1(
229 ; CHECK-NEXT:    [[ADD2:%.*]] = mul nsw i16 [[X:%.*]], 9
230 ; CHECK-NEXT:    ret i16 [[ADD2]]
232   %mul1 = mul nsw i16 %x, 8
233   %add2 = add nsw i16 %x, %mul1
234   ret i16 %add2
237 define i16 @mul_add_to_mul_2(i16 %x) {
238 ; CHECK-LABEL: @mul_add_to_mul_2(
239 ; CHECK-NEXT:    [[ADD2:%.*]] = mul nsw i16 [[X:%.*]], 9
240 ; CHECK-NEXT:    ret i16 [[ADD2]]
242   %mul1 = mul nsw i16 %x, 8
243   %add2 = add nsw i16 %mul1, %x
244   ret i16 %add2
247 define i16 @mul_add_to_mul_3(i16 %a) {
248 ; CHECK-LABEL: @mul_add_to_mul_3(
249 ; CHECK-NEXT:    [[ADD:%.*]] = mul i16 [[A:%.*]], 5
250 ; CHECK-NEXT:    ret i16 [[ADD]]
252   %mul1 = mul i16 %a, 2
253   %mul2 = mul i16 %a, 3
254   %add = add nsw i16 %mul1, %mul2
255   ret i16 %add
258 define i16 @mul_add_to_mul_4(i16 %a) {
259 ; CHECK-LABEL: @mul_add_to_mul_4(
260 ; CHECK-NEXT:    [[ADD:%.*]] = mul nsw i16 [[A:%.*]], 9
261 ; CHECK-NEXT:    ret i16 [[ADD]]
263   %mul1 = mul nsw i16 %a, 2
264   %mul2 = mul nsw i16 %a, 7
265   %add = add nsw i16 %mul1, %mul2
266   ret i16 %add
269 define i16 @mul_add_to_mul_5(i16 %a) {
270 ; CHECK-LABEL: @mul_add_to_mul_5(
271 ; CHECK-NEXT:    [[ADD:%.*]] = mul nsw i16 [[A:%.*]], 10
272 ; CHECK-NEXT:    ret i16 [[ADD]]
274   %mul1 = mul nsw i16 %a, 3
275   %mul2 = mul nsw i16 %a, 7
276   %add = add nsw i16 %mul1, %mul2
277   ret i16 %add
280 define i32 @mul_add_to_mul_6(i32 %x, i32 %y) {
281 ; CHECK-LABEL: @mul_add_to_mul_6(
282 ; CHECK-NEXT:    [[MUL1:%.*]] = mul nsw i32 [[X:%.*]], [[Y:%.*]]
283 ; CHECK-NEXT:    [[ADD:%.*]] = mul nsw i32 [[MUL1]], 6
284 ; CHECK-NEXT:    ret i32 [[ADD]]
286   %mul1 = mul nsw i32 %x, %y
287   %mul2 = mul nsw i32 %mul1, 5
288   %add = add nsw i32 %mul1, %mul2
289   ret i32 %add
292 define i16 @mul_add_to_mul_7(i16 %x) {
293 ; CHECK-LABEL: @mul_add_to_mul_7(
294 ; CHECK-NEXT:    [[ADD2:%.*]] = shl i16 [[X:%.*]], 15
295 ; CHECK-NEXT:    ret i16 [[ADD2]]
297   %mul1 = mul nsw i16 %x, 32767
298   %add2 = add nsw i16 %x, %mul1
299   ret i16 %add2
302 define i16 @mul_add_to_mul_8(i16 %a) {
303 ; CHECK-LABEL: @mul_add_to_mul_8(
304 ; CHECK-NEXT:    [[ADD:%.*]] = mul nsw i16 [[A:%.*]], 32767
305 ; CHECK-NEXT:    ret i16 [[ADD]]
307   %mul1 = mul nsw i16 %a, 16383
308   %mul2 = mul nsw i16 %a, 16384
309   %add = add nsw i16 %mul1, %mul2
310   ret i16 %add
313 define i16 @mul_add_to_mul_9(i16 %a) {
314 ; CHECK-LABEL: @mul_add_to_mul_9(
315 ; CHECK-NEXT:    [[ADD:%.*]] = shl i16 [[A:%.*]], 15
316 ; CHECK-NEXT:    ret i16 [[ADD]]
318   %mul1 = mul nsw i16 %a, 16384
319   %mul2 = mul nsw i16 %a, 16384
320   %add = add nsw i16 %mul1, %mul2
321   ret i16 %add
324 ; This test and the next test verify that when a range metadata is attached to
325 ; llvm.cttz, ValueTracking correctly intersects the range specified by the
326 ; metadata and the range implied by the intrinsic.
328 ; In this test, the range specified by the metadata is more strict. Therefore,
329 ; ValueTracking uses that range.
330 define i16 @add_cttz(i16 %a) {
331 ; CHECK-LABEL: @add_cttz(
332 ; CHECK-NEXT:    [[CTTZ:%.*]] = call i16 @llvm.cttz.i16(i16 [[A:%.*]], i1 true), !range !0
333 ; CHECK-NEXT:    [[B:%.*]] = or i16 [[CTTZ]], -8
334 ; CHECK-NEXT:    ret i16 [[B]]
336   ; llvm.cttz.i16(..., /*is_zero_undefined=*/true) implies the value returned
337   ; is in [0, 16). The range metadata indicates the value returned is in [0, 8).
338   ; Intersecting these ranges, we know the value returned is in [0, 8).
339   ; Therefore, InstCombine will transform
340   ;     add %cttz, 1111 1111 1111 1000 ; decimal -8
341   ; to
342   ;     or  %cttz, 1111 1111 1111 1000
343   %cttz = call i16 @llvm.cttz.i16(i16 %a, i1 true), !range !0
344   %b = add i16 %cttz, -8
345   ret i16 %b
347 declare i16 @llvm.cttz.i16(i16, i1)
348 !0 = !{i16 0, i16 8}
350 ; Similar to @add_cttz, but in this test, the range implied by the
351 ; intrinsic is more strict. Therefore, ValueTracking uses that range.
352 define i16 @add_cttz_2(i16 %a) {
353 ; CHECK-LABEL: @add_cttz_2(
354 ; CHECK-NEXT:    [[CTTZ:%.*]] = call i16 @llvm.cttz.i16(i16 [[A:%.*]], i1 true), !range !1
355 ; CHECK-NEXT:    [[B:%.*]] = or i16 [[CTTZ]], -16
356 ; CHECK-NEXT:    ret i16 [[B]]
358   ; llvm.cttz.i16(..., /*is_zero_undefined=*/true) implies the value returned
359   ; is in [0, 16). The range metadata indicates the value returned is in
360   ; [0, 32). Intersecting these ranges, we know the value returned is in
361   ; [0, 16). Therefore, InstCombine will transform
362   ;     add %cttz, 1111 1111 1111 0000 ; decimal -16
363   ; to
364   ;     or  %cttz, 1111 1111 1111 0000
365   %cttz = call i16 @llvm.cttz.i16(i16 %a, i1 true), !range !1
366   %b = add i16 %cttz, -16
367   ret i16 %b
369 !1 = !{i16 0, i16 32}
371 define i32 @add_or_and(i32 %x, i32 %y) {
372 ; CHECK-LABEL: @add_or_and(
373 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]
374 ; CHECK-NEXT:    ret i32 [[ADD]]
376   %or = or i32 %x, %y
377   %and = and i32 %x, %y
378   %add = add i32 %or, %and
379   ret i32 %add
382 define i32 @add_or_and_commutative(i32 %x, i32 %y) {
383 ; CHECK-LABEL: @add_or_and_commutative(
384 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]
385 ; CHECK-NEXT:    ret i32 [[ADD]]
387   %or = or i32 %x, %y
388   %and = and i32 %y, %x ; swapped
389   %add = add i32 %or, %and
390   ret i32 %add
393 define i32 @add_and_or(i32 %x, i32 %y) {
394 ; CHECK-LABEL: @add_and_or(
395 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]
396 ; CHECK-NEXT:    ret i32 [[ADD]]
398   %or = or i32 %x, %y
399   %and = and i32 %x, %y
400   %add = add i32 %and, %or
401   ret i32 %add
404 define i32 @add_and_or_commutative(i32 %x, i32 %y) {
405 ; CHECK-LABEL: @add_and_or_commutative(
406 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]
407 ; CHECK-NEXT:    ret i32 [[ADD]]
409   %or = or i32 %x, %y
410   %and = and i32 %y, %x ; swapped
411   %add = add i32 %and, %or
412   ret i32 %add
415 define i32 @add_nsw_or_and(i32 %x, i32 %y) {
416 ; CHECK-LABEL: @add_nsw_or_and(
417 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[X:%.*]], [[Y:%.*]]
418 ; CHECK-NEXT:    ret i32 [[ADD]]
420   %or = or i32 %x, %y
421   %and = and i32 %x, %y
422   %add = add nsw i32 %or, %and
423   ret i32 %add
426 define i32 @add_nuw_or_and(i32 %x, i32 %y) {
427 ; CHECK-LABEL: @add_nuw_or_and(
428 ; CHECK-NEXT:    [[ADD:%.*]] = add nuw i32 [[X:%.*]], [[Y:%.*]]
429 ; CHECK-NEXT:    ret i32 [[ADD]]
431   %or = or i32 %x, %y
432   %and = and i32 %x, %y
433   %add = add nuw i32 %or, %and
434   ret i32 %add
437 define i32 @add_nuw_nsw_or_and(i32 %x, i32 %y) {
438 ; CHECK-LABEL: @add_nuw_nsw_or_and(
439 ; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[X:%.*]], [[Y:%.*]]
440 ; CHECK-NEXT:    ret i32 [[ADD]]
442   %or = or i32 %x, %y
443   %and = and i32 %x, %y
444   %add = add nsw nuw i32 %or, %and
445   ret i32 %add
448 ; A *nsw B + A *nsw C != A *nsw (B + C)
449 ; e.g. A = -1, B = 1, C = INT_SMAX
451 define i8 @add_of_mul(i8 %x, i8 %y, i8 %z) {
452 ; CHECK-LABEL: @add_of_mul(
453 ; CHECK-NEXT:  entry:
454 ; CHECK-NEXT:    [[MB1:%.*]] = add i8 [[Y:%.*]], [[Z:%.*]]
455 ; CHECK-NEXT:    [[SUM:%.*]] = mul i8 [[MB1]], [[X:%.*]]
456 ; CHECK-NEXT:    ret i8 [[SUM]]
458   entry:
459   %mA = mul nsw i8 %x, %y
460   %mB = mul nsw i8 %x, %z
461   %sum = add nsw i8 %mA, %mB
462   ret i8 %sum
465 define i32 @add_of_selects(i1 %A, i32 %B) {
466 ; CHECK-LABEL: @add_of_selects(
467 ; CHECK-NEXT:    [[ADD:%.*]] = select i1 [[A:%.*]], i32 [[B:%.*]], i32 0
468 ; CHECK-NEXT:    ret i32 [[ADD]]
470   %sel0 = select i1 %A, i32 0, i32 -2
471   %sel1 = select i1 %A, i32 %B, i32 2
472   %add = add i32 %sel0, %sel1
473   ret i32 %add