1 ; This test makes sure that these instructions are properly eliminated.
3 ; RUN: opt < %s -instcombine -S | FileCheck %s
5 define i32 @test1(i32 %A) {
8 %B = shl i32 %A, 0 ; <i32> [#uses=1]
12 define i32 @test2(i8 %A) {
13 ; CHECK-LABEL: @test2(
15 %shift.upgrd.1 = zext i8 %A to i32 ; <i32> [#uses=1]
16 %B = shl i32 0, %shift.upgrd.1 ; <i32> [#uses=1]
20 define i32 @test3(i32 %A) {
21 ; CHECK-LABEL: @test3(
23 %B = ashr i32 %A, 0 ; <i32> [#uses=1]
27 define i32 @test4(i8 %A) {
28 ; CHECK-LABEL: @test4(
30 %shift.upgrd.2 = zext i8 %A to i32 ; <i32> [#uses=1]
31 %B = ashr i32 0, %shift.upgrd.2 ; <i32> [#uses=1]
36 define i32 @test5(i32 %A) {
37 ; CHECK-LABEL: @test5(
38 ; CHECK: ret i32 undef
39 %B = lshr i32 %A, 32 ;; shift all bits out
43 define i32 @test5a(i32 %A) {
44 ; CHECK-LABEL: @test5a(
45 ; CHECK: ret i32 undef
46 %B = shl i32 %A, 32 ;; shift all bits out
50 define i32 @test5b() {
51 ; CHECK-LABEL: @test5b(
53 %B = ashr i32 undef, 2 ;; top two bits must be equal, so not undef
57 define i32 @test5b2(i32 %A) {
58 ; CHECK-LABEL: @test5b2(
60 %B = ashr i32 undef, %A ;; top %A bits must be equal, so not undef
64 define i32 @test6(i32 %A) {
65 ; CHECK-LABEL: @test6(
66 ; CHECK-NEXT: mul i32 %A, 6
68 %B = shl i32 %A, 1 ;; convert to an mul instruction
73 define i32 @test6a(i32 %A) {
74 ; CHECK-LABEL: @test6a(
75 ; CHECK-NEXT: mul i32 %A, 6
78 %C = shl i32 %B, 1 ;; convert to an mul instruction
82 define i32 @test7(i8 %A) {
83 ; CHECK-LABEL: @test7(
84 ; CHECK-NEXT: ret i32 -1
85 %shift.upgrd.3 = zext i8 %A to i32
86 %B = ashr i32 -1, %shift.upgrd.3 ;; Always equal to -1
90 ;; (A << 5) << 3 === A << 8 == 0
91 define i8 @test8(i8 %A) {
92 ; CHECK-LABEL: @test8(
94 %B = shl i8 %A, 5 ; <i8> [#uses=1]
95 %C = shl i8 %B, 3 ; <i8> [#uses=1]
99 ;; (A << 7) >> 7 === A & 1
100 define i8 @test9(i8 %A) {
101 ; CHECK-LABEL: @test9(
102 ; CHECK-NEXT: and i8 %A, 1
104 %B = shl i8 %A, 7 ; <i8> [#uses=1]
105 %C = lshr i8 %B, 7 ; <i8> [#uses=1]
109 ;; This transformation is deferred to DAGCombine:
110 ;; (A >> 7) << 7 === A & 128
111 ;; The shl may be valuable to scalar evolution.
112 define i8 @test10(i8 %A) {
113 ; CHECK-LABEL: @test10(
114 ; CHECK-NEXT: and i8 %A, -128
116 %B = lshr i8 %A, 7 ; <i8> [#uses=1]
117 %C = shl i8 %B, 7 ; <i8> [#uses=1]
121 ;; Allow the simplification when the lshr shift is exact.
122 define i8 @test10a(i8 %A) {
123 ; CHECK-LABEL: @test10a(
124 ; CHECK-NEXT: ret i8 %A
125 %B = lshr exact i8 %A, 7
130 ;; This transformation is deferred to DAGCombine:
131 ;; (A >> 3) << 4 === (A & 0x1F) << 1
132 ;; The shl may be valuable to scalar evolution.
133 define i8 @test11(i8 %A) {
134 ; CHECK-LABEL: @test11(
137 %a = mul i8 %A, 3 ; <i8> [#uses=1]
138 %B = lshr i8 %a, 3 ; <i8> [#uses=1]
139 %C = shl i8 %B, 4 ; <i8> [#uses=1]
143 ;; Allow the simplification in InstCombine when the lshr shift is exact.
144 define i8 @test11a(i8 %A) {
145 ; CHECK-LABEL: @test11a(
146 ; CHECK-NEXT: mul i8 %A, 6
149 %B = lshr exact i8 %a, 3
154 ;; This is deferred to DAGCombine unless %B is single-use.
155 ;; (A >> 8) << 8 === A & -256
156 define i32 @test12(i32 %A) {
157 ; CHECK-LABEL: @test12(
158 ; CHECK-NEXT: and i32 %A, -256
159 ; CHECK-NEXT: ret i32
160 %B = ashr i32 %A, 8 ; <i32> [#uses=1]
161 %C = shl i32 %B, 8 ; <i32> [#uses=1]
165 ;; This transformation is deferred to DAGCombine:
166 ;; (A >> 3) << 4 === (A & -8) * 2
167 ;; The shl may be valuable to scalar evolution.
168 define i8 @test13(i8 %A) {
169 ; CHECK-LABEL: @test13(
172 %a = mul i8 %A, 3 ; <i8> [#uses=1]
173 %B = ashr i8 %a, 3 ; <i8> [#uses=1]
174 %C = shl i8 %B, 4 ; <i8> [#uses=1]
178 define i8 @test13a(i8 %A) {
179 ; CHECK-LABEL: @test13a(
180 ; CHECK-NEXT: mul i8 %A, 6
183 %B = ashr exact i8 %a, 3
188 ;; D = ((B | 1234) << 4) === ((B << 4)|(1234 << 4)
189 define i32 @test14(i32 %A) {
190 ; CHECK-LABEL: @test14(
191 ; CHECK-NEXT: %B = and i32 %A, -19760
192 ; CHECK-NEXT: or i32 %B, 19744
193 ; CHECK-NEXT: ret i32
194 %B = lshr i32 %A, 4 ; <i32> [#uses=1]
195 %C = or i32 %B, 1234 ; <i32> [#uses=1]
196 %D = shl i32 %C, 4 ; <i32> [#uses=1]
200 ;; D = ((B | 1234) << 4) === ((B << 4)|(1234 << 4)
201 define i32 @test14a(i32 %A) {
202 ; CHECK-LABEL: @test14a(
203 ; CHECK-NEXT: and i32 %A, 77
204 ; CHECK-NEXT: ret i32
205 %B = shl i32 %A, 4 ; <i32> [#uses=1]
206 %C = and i32 %B, 1234 ; <i32> [#uses=1]
207 %D = lshr i32 %C, 4 ; <i32> [#uses=1]
211 define i32 @test15(i1 %C) {
212 ; CHECK-LABEL: @test15(
213 ; CHECK-NEXT: select i1 %C, i32 12, i32 4
214 ; CHECK-NEXT: ret i32
215 %A = select i1 %C, i32 3, i32 1 ; <i32> [#uses=1]
216 %V = shl i32 %A, 2 ; <i32> [#uses=1]
220 define i32 @test15a(i1 %C) {
221 ; CHECK-LABEL: @test15a(
222 ; CHECK-NEXT: select i1 %C, i32 512, i32 128
223 ; CHECK-NEXT: ret i32
224 %A = select i1 %C, i8 3, i8 1 ; <i8> [#uses=1]
225 %shift.upgrd.4 = zext i8 %A to i32 ; <i32> [#uses=1]
226 %V = shl i32 64, %shift.upgrd.4 ; <i32> [#uses=1]
230 define i1 @test16(i32 %X) {
231 ; CHECK-LABEL: @test16(
232 ; CHECK-NEXT: and i32 %X, 16
233 ; CHECK-NEXT: icmp ne i32
235 %tmp.3 = ashr i32 %X, 4
236 %tmp.6 = and i32 %tmp.3, 1
237 %tmp.7 = icmp ne i32 %tmp.6, 0
241 define i1 @test17(i32 %A) {
242 ; CHECK-LABEL: @test17(
243 ; CHECK-NEXT: and i32 %A, -8
244 ; CHECK-NEXT: icmp eq i32
246 %B = lshr i32 %A, 3 ; <i32> [#uses=1]
247 %C = icmp eq i32 %B, 1234 ; <i1> [#uses=1]
252 define i1 @test18(i8 %A) {
253 ; CHECK-LABEL: @test18(
254 ; CHECK: ret i1 false
256 %B = lshr i8 %A, 7 ; <i8> [#uses=1]
258 %C = icmp eq i8 %B, 123 ; <i1> [#uses=1]
262 define i1 @test19(i32 %A) {
263 ; CHECK-LABEL: @test19(
264 ; CHECK-NEXT: icmp ult i32 %A, 4
266 %B = ashr i32 %A, 2 ; <i32> [#uses=1]
268 %C = icmp eq i32 %B, 0 ; <i1> [#uses=1]
273 define i1 @test19a(i32 %A) {
274 ; CHECK-LABEL: @test19a(
275 ; CHECK-NEXT: icmp ugt i32 %A, -5
277 %B = ashr i32 %A, 2 ; <i32> [#uses=1]
279 %C = icmp eq i32 %B, -1 ; <i1> [#uses=1]
283 define i1 @test20(i8 %A) {
284 ; CHECK-LABEL: @test20(
285 ; CHECK: ret i1 false
286 %B = ashr i8 %A, 7 ; <i8> [#uses=1]
288 %C = icmp eq i8 %B, 123 ; <i1> [#uses=1]
292 define i1 @test21(i8 %A) {
293 ; CHECK-LABEL: @test21(
294 ; CHECK-NEXT: and i8 %A, 15
295 ; CHECK-NEXT: icmp eq i8
297 %B = shl i8 %A, 4 ; <i8> [#uses=1]
298 %C = icmp eq i8 %B, -128 ; <i1> [#uses=1]
302 define i1 @test22(i8 %A) {
303 ; CHECK-LABEL: @test22(
304 ; CHECK-NEXT: and i8 %A, 15
305 ; CHECK-NEXT: icmp eq i8
307 %B = shl i8 %A, 4 ; <i8> [#uses=1]
308 %C = icmp eq i8 %B, 0 ; <i1> [#uses=1]
312 define i8 @test23(i32 %A) {
313 ; CHECK-LABEL: @test23(
314 ; CHECK-NEXT: trunc i32 %A to i8
318 %B = shl i32 %A, 24 ; <i32> [#uses=1]
319 %C = ashr i32 %B, 24 ; <i32> [#uses=1]
320 %D = trunc i32 %C to i8 ; <i8> [#uses=1]
324 define i8 @test24(i8 %X) {
325 ; CHECK-LABEL: @test24(
326 ; CHECK-NEXT: and i8 %X, 3
328 %Y = and i8 %X, -5 ; <i8> [#uses=1]
329 %Z = shl i8 %Y, 5 ; <i8> [#uses=1]
330 %Q = ashr i8 %Z, 5 ; <i8> [#uses=1]
334 define i32 @test25(i32 %tmp.2, i32 %AA) {
335 ; CHECK-LABEL: @test25(
336 ; CHECK-NEXT: and i32 %tmp.2, -131072
337 ; CHECK-NEXT: add i32 %{{[^,]*}}, %AA
338 ; CHECK-NEXT: and i32 %{{[^,]*}}, -131072
339 ; CHECK-NEXT: ret i32
340 %x = lshr i32 %AA, 17 ; <i32> [#uses=1]
341 %tmp.3 = lshr i32 %tmp.2, 17 ; <i32> [#uses=1]
342 %tmp.5 = add i32 %tmp.3, %x ; <i32> [#uses=1]
343 %tmp.6 = shl i32 %tmp.5, 17 ; <i32> [#uses=1]
347 ;; handle casts between shifts.
348 define i32 @test26(i32 %A) {
349 ; CHECK-LABEL: @test26(
350 ; CHECK-NEXT: and i32 %A, -2
351 ; CHECK-NEXT: ret i32
352 %B = lshr i32 %A, 1 ; <i32> [#uses=1]
353 %C = bitcast i32 %B to i32 ; <i32> [#uses=1]
354 %D = shl i32 %C, 1 ; <i32> [#uses=1]
359 define i1 @test27(i32 %x) nounwind {
360 ; CHECK-LABEL: @test27(
361 ; CHECK-NEXT: and i32 %x, 8
362 ; CHECK-NEXT: icmp ne i32
365 %z = trunc i32 %y to i1
369 define i8 @test28(i8 %x) {
371 ; CHECK-LABEL: @test28(
372 ; CHECK: icmp slt i8 %x, 0
374 %tmp1 = lshr i8 %x, 7
375 %cond1 = icmp ne i8 %tmp1, 0
376 br i1 %cond1, label %bb1, label %bb2
385 define i8 @test28a(i8 %x, i8 %y) {
387 ; This shouldn't be transformed.
388 ; CHECK-LABEL: @test28a(
389 ; CHECK: %tmp1 = lshr i8 %x, 7
390 ; CHECK: %cond1 = icmp eq i8 %tmp1, 0
391 ; CHECK: br i1 %cond1, label %bb2, label %bb1
392 %tmp1 = lshr i8 %x, 7
393 %cond1 = icmp ne i8 %tmp1, 0
394 br i1 %cond1, label %bb1, label %bb2
398 %tmp2 = add i8 %tmp1, %y
403 define i32 @test29(i64 %d18) {
405 %tmp916 = lshr i64 %d18, 32
406 %tmp917 = trunc i64 %tmp916 to i32
407 %tmp10 = lshr i32 %tmp917, 31
409 ; CHECK-LABEL: @test29(
410 ; CHECK: %tmp916 = lshr i64 %d18, 63
411 ; CHECK: %tmp10 = trunc i64 %tmp916 to i32
415 define i32 @test30(i32 %A, i32 %B, i32 %C) {
420 ; CHECK-LABEL: @test30(
421 ; CHECK: %X1 = and i32 %A, %B
422 ; CHECK: %Z = shl i32 %X1, %C
425 define i32 @test31(i32 %A, i32 %B, i32 %C) {
430 ; CHECK-LABEL: @test31(
431 ; CHECK: %X1 = or i32 %A, %B
432 ; CHECK: %Z = lshr i32 %X1, %C
435 define i32 @test32(i32 %A, i32 %B, i32 %C) {
440 ; CHECK-LABEL: @test32(
441 ; CHECK: %X1 = xor i32 %A, %B
442 ; CHECK: %Z = ashr i32 %X1, %C
446 define i1 @test33(i32 %X) {
447 %tmp1 = shl i32 %X, 7
448 %tmp2 = icmp slt i32 %tmp1, 0
450 ; CHECK-LABEL: @test33(
451 ; CHECK: %tmp1.mask = and i32 %X, 16777216
452 ; CHECK: %tmp2 = icmp ne i32 %tmp1.mask, 0
455 define i1 @test34(i32 %X) {
456 %tmp1 = lshr i32 %X, 7
457 %tmp2 = icmp slt i32 %tmp1, 0
459 ; CHECK-LABEL: @test34(
460 ; CHECK: ret i1 false
463 define i1 @test35(i32 %X) {
464 %tmp1 = ashr i32 %X, 7
465 %tmp2 = icmp slt i32 %tmp1, 0
467 ; CHECK-LABEL: @test35(
468 ; CHECK: %tmp2 = icmp slt i32 %X, 0
469 ; CHECK: ret i1 %tmp2
472 define i128 @test36(i128 %A, i128 %B) {
474 %tmp27 = shl i128 %A, 64
475 %tmp23 = shl i128 %B, 64
476 %ins = or i128 %tmp23, %tmp27
477 %tmp45 = lshr i128 %ins, 64
480 ; CHECK-LABEL: @test36(
481 ; CHECK: %tmp231 = or i128 %B, %A
482 ; CHECK: %ins = and i128 %tmp231, 18446744073709551615
483 ; CHECK: ret i128 %ins
486 define i64 @test37(i128 %A, i32 %B) {
488 %tmp27 = shl i128 %A, 64
489 %tmp22 = zext i32 %B to i128
490 %tmp23 = shl i128 %tmp22, 96
491 %ins = or i128 %tmp23, %tmp27
492 %tmp45 = lshr i128 %ins, 64
493 %tmp46 = trunc i128 %tmp45 to i64
496 ; CHECK-LABEL: @test37(
497 ; CHECK: %tmp23 = shl nuw nsw i128 %tmp22, 32
498 ; CHECK: %ins = or i128 %tmp23, %A
499 ; CHECK: %tmp46 = trunc i128 %ins to i64
502 define i32 @test38(i32 %x) nounwind readnone {
503 %rem = srem i32 %x, 32
504 %shl = shl i32 1, %rem
506 ; CHECK-LABEL: @test38(
507 ; CHECK-NEXT: and i32 %x, 31
508 ; CHECK-NEXT: shl i32 1
509 ; CHECK-NEXT: ret i32
512 ; <rdar://problem/8756731>
513 ; CHECK-LABEL: @test39(
514 define i8 @test39(i32 %a0) {
516 %tmp4 = trunc i32 %a0 to i8
517 ; CHECK: and i8 %tmp49, 64
518 %tmp5 = shl i8 %tmp4, 5
519 %tmp48 = and i8 %tmp5, 32
520 %tmp49 = lshr i8 %tmp48, 5
521 %tmp50 = mul i8 %tmp49, 64
522 %tmp51 = xor i8 %tmp50, %tmp5
523 %tmp52 = and i8 %tmp51, -128
524 %tmp53 = lshr i8 %tmp52, 7
525 %tmp54 = mul i8 %tmp53, 16
526 ; CHECK: %0 = shl i8 %tmp4, 2
527 ; CHECK: %tmp54 = and i8 %0, 16
528 %tmp55 = xor i8 %tmp54, %tmp51
529 ; CHECK: ret i8 %tmp551
534 define i32 @test40(i32 %a, i32 %b) nounwind {
535 %shl1 = shl i32 1, %b
536 %shl2 = shl i32 %shl1, 2
537 %div = udiv i32 %a, %shl2
539 ; CHECK-LABEL: @test40(
540 ; CHECK-NEXT: add i32 %b, 2
541 ; CHECK-NEXT: lshr i32 %a
542 ; CHECK-NEXT: ret i32
545 define i32 @test41(i32 %a, i32 %b) nounwind {
549 ; CHECK-LABEL: @test41(
550 ; CHECK-NEXT: shl i32 8, %b
551 ; CHECK-NEXT: ret i32
554 define i32 @test42(i32 %a, i32 %b) nounwind {
555 %div = lshr i32 4096, %b ; must be exact otherwise we'd divide by zero
556 %div2 = udiv i32 %a, %div
558 ; CHECK-LABEL: @test42(
559 ; CHECK-NEXT: lshr exact i32 4096, %b
562 define i32 @test43(i32 %a, i32 %b) nounwind {
563 %div = shl i32 4096, %b ; must be exact otherwise we'd divide by zero
564 %div2 = udiv i32 %a, %div
566 ; CHECK-LABEL: @test43(
567 ; CHECK-NEXT: add i32 %b, 12
572 define i32 @test44(i32 %a) nounwind {
573 %y = shl nuw i32 %a, 1
576 ; CHECK-LABEL: @test44(
577 ; CHECK-NEXT: %y = shl i32 %a, 5
578 ; CHECK-NEXT: ret i32 %y
581 define i32 @test45(i32 %a) nounwind {
582 %y = lshr exact i32 %a, 1
585 ; CHECK-LABEL: @test45(
586 ; CHECK-NEXT: %y = lshr i32 %a, 5
587 ; CHECK-NEXT: ret i32 %y
590 define i32 @test46(i32 %a) {
591 %y = ashr exact i32 %a, 3
594 ; CHECK-LABEL: @test46(
595 ; CHECK-NEXT: %z = ashr exact i32 %a, 2
596 ; CHECK-NEXT: ret i32 %z
599 define i32 @test47(i32 %a) {
600 %y = lshr exact i32 %a, 3
603 ; CHECK-LABEL: @test47(
604 ; CHECK-NEXT: %z = lshr exact i32 %a, 2
605 ; CHECK-NEXT: ret i32 %z
608 define i32 @test48(i32 %x) {
609 %A = lshr exact i32 %x, 1
612 ; CHECK-LABEL: @test48(
613 ; CHECK-NEXT: %B = shl i32 %x, 2
614 ; CHECK-NEXT: ret i32 %B
617 define i32 @test49(i32 %x) {
618 %A = ashr exact i32 %x, 1
621 ; CHECK-LABEL: @test49(
622 ; CHECK-NEXT: %B = shl i32 %x, 2
623 ; CHECK-NEXT: ret i32 %B
626 define i32 @test50(i32 %x) {
627 %A = shl nsw i32 %x, 1
630 ; CHECK-LABEL: @test50(
631 ; CHECK-NEXT: %B = ashr i32 %x, 2
632 ; CHECK-NEXT: ret i32 %B
635 define i32 @test51(i32 %x) {
636 %A = shl nuw i32 %x, 1
639 ; CHECK-LABEL: @test51(
640 ; CHECK-NEXT: %B = lshr i32 %x, 2
641 ; CHECK-NEXT: ret i32 %B
644 define i32 @test52(i32 %x) {
645 %A = shl nsw i32 %x, 3
648 ; CHECK-LABEL: @test52(
649 ; CHECK-NEXT: %B = shl nsw i32 %x, 2
650 ; CHECK-NEXT: ret i32 %B
653 define i32 @test53(i32 %x) {
654 %A = shl nuw i32 %x, 3
657 ; CHECK-LABEL: @test53(
658 ; CHECK-NEXT: %B = shl nuw i32 %x, 2
659 ; CHECK-NEXT: ret i32 %B
662 define i32 @test54(i32 %x) {
663 %shr2 = lshr i32 %x, 1
664 %shl = shl i32 %shr2, 4
665 %and = and i32 %shl, 16
667 ; CHECK-LABEL: @test54(
668 ; CHECK: shl i32 %x, 3
672 define i32 @test55(i32 %x) {
673 %shr2 = lshr i32 %x, 1
674 %shl = shl i32 %shr2, 4
677 ; CHECK-LABEL: @test55(
678 ; CHECK: shl i32 %x, 3
681 define i32 @test56(i32 %x) {
682 %shr2 = lshr i32 %x, 1
683 %shl = shl i32 %shr2, 4
686 ; CHECK-LABEL: @test56(
687 ; CHECK: shl i32 %shr2, 4
691 define i32 @test57(i32 %x) {
692 %shr = lshr i32 %x, 1
693 %shl = shl i32 %shr, 4
694 %and = and i32 %shl, 16
696 ; CHECK-LABEL: @test57(
697 ; CHECK: shl i32 %x, 3
700 define i32 @test58(i32 %x) {
701 %shr = lshr i32 %x, 1
702 %shl = shl i32 %shr, 4
705 ; CHECK-LABEL: @test58(
706 ; CHECK: shl i32 %x, 3
709 define i32 @test59(i32 %x) {
710 %shr = ashr i32 %x, 1
711 %shl = shl i32 %shr, 4
714 ; CHECK-LABEL: @test59(
715 ; CHECK: %shl = shl i32 %shr1, 4
719 define i32 @test60(i32 %x) {
720 %shr = ashr i32 %x, 4
721 %shl = shl i32 %shr, 1
724 ; CHECK-LABEL: @test60(
725 ; CHECK: ashr i32 %x, 3
729 define i32 @test61(i32 %x) {
730 %shr = ashr i32 %x, 4
731 %shl = shl i32 %shr, 1
734 ; CHECK-LABEL: @test61(
735 ; CHECK: ashr i32 %x, 4
738 ; propagate "exact" trait
739 define i32 @test62(i32 %x) {
740 %shr = ashr exact i32 %x, 4
741 %shl = shl i32 %shr, 1
744 ; CHECK-LABEL: @test62(
745 ; CHECK: ashr exact i32 %x, 3