test/Transforms/InstCombine/shift.ll

   1 ; This test makes sure that these instructions are properly eliminated.
   2 ;
   3 ; RUN: opt < %s -instcombine -S | FileCheck %s
   4
   5 define i32 @test1(i32 %A) {
   6 ; CHECK: @test1
   7 ; CHECK: ret i32 %A
   8         %B = shl i32 %A, 0              ; <i32> [#uses=1]
   9         ret i32 %B
  10 }
  11
  12 define i32 @test2(i8 %A) {
  13 ; CHECK: @test2
  14 ; CHECK: ret i32 0
  15         %shift.upgrd.1 = zext i8 %A to i32              ; <i32> [#uses=1]
  16         %B = shl i32 0, %shift.upgrd.1          ; <i32> [#uses=1]
  17         ret i32 %B
  18 }
  19
  20 define i32 @test3(i32 %A) {
  21 ; CHECK: @test3
  22 ; CHECK: ret i32 %A
  23         %B = ashr i32 %A, 0             ; <i32> [#uses=1]
  24         ret i32 %B
  25 }
  26
  27 define i32 @test4(i8 %A) {
  28 ; CHECK: @test4
  29 ; CHECK: ret i32 0
  30         %shift.upgrd.2 = zext i8 %A to i32              ; <i32> [#uses=1]
  31         %B = ashr i32 0, %shift.upgrd.2         ; <i32> [#uses=1]
  32         ret i32 %B
  33 }
  34
  35
  36 define i32 @test5(i32 %A) {
  37 ; CHECK: @test5
  38 ; CHECK: ret i32 undef
  39         %B = lshr i32 %A, 32  ;; shift all bits out
  40         ret i32 %B
  41 }
  42
  43 define i32 @test5a(i32 %A) {
  44 ; CHECK: @test5a
  45 ; CHECK: ret i32 undef
  46         %B = shl i32 %A, 32     ;; shift all bits out
  47         ret i32 %B
  48 }
  49
  50 define i32 @test5b() {
  51 ; CHECK: @test5b
  52 ; CHECK: ret i32 -1
  53         %B = ashr i32 undef, 2  ;; top two bits must be equal, so not undef
  54         ret i32 %B
  55 }
  56
  57 define i32 @test5b2(i32 %A) {
  58 ; CHECK: @test5b2
  59 ; CHECK: ret i32 -1
  60         %B = ashr i32 undef, %A  ;; top %A bits must be equal, so not undef
  61         ret i32 %B
  62 }
  63
  64 define i32 @test6(i32 %A) {
  65 ; CHECK: @test6
  66 ; CHECK-NEXT: mul i32 %A, 6
  67 ; CHECK-NEXT: ret i32
  68         %B = shl i32 %A, 1      ;; convert to an mul instruction
  69         %C = mul i32 %B, 3
  70         ret i32 %C
  71 }
  72
  73 define i32 @test7(i8 %A) {
  74 ; CHECK: @test7
  75 ; CHECK-NEXT: ret i32 -1
  76         %shift.upgrd.3 = zext i8 %A to i32
  77         %B = ashr i32 -1, %shift.upgrd.3  ;; Always equal to -1
  78         ret i32 %B
  79 }
  80
  81 ;; (A << 5) << 3 === A << 8 == 0
  82 define i8 @test8(i8 %A) {
  83 ; CHECK: @test8
  84 ; CHECK: ret i8 0
  85         %B = shl i8 %A, 5               ; <i8> [#uses=1]
  86         %C = shl i8 %B, 3               ; <i8> [#uses=1]
  87         ret i8 %C
  88 }
  89
  90 ;; (A << 7) >> 7 === A & 1
  91 define i8 @test9(i8 %A) {
  92 ; CHECK: @test9
  93 ; CHECK-NEXT: and i8 %A, 1
  94 ; CHECK-NEXT: ret i8
  95         %B = shl i8 %A, 7               ; <i8> [#uses=1]
  96         %C = lshr i8 %B, 7              ; <i8> [#uses=1]
  97         ret i8 %C
  98 }
  99
 100 ;; (A >> 7) << 7 === A & 128
 101 define i8 @test10(i8 %A) {
 102 ; CHECK: @test10
 103 ; CHECK-NEXT: and i8 %A, -128
 104 ; CHECK-NEXT: ret i8
 105         %B = lshr i8 %A, 7              ; <i8> [#uses=1]
 106         %C = shl i8 %B, 7               ; <i8> [#uses=1]
 107         ret i8 %C
 108 }
 109
 110 ;; (A >> 3) << 4 === (A & 0x1F) << 1
 111 define i8 @test11(i8 %A) {
 112 ; CHECK: @test11
 113 ; CHECK-NEXT: mul i8 %A, 6
 114 ; CHECK-NEXT: and i8
 115 ; CHECK-NEXT: ret i8
 116         %a = mul i8 %A, 3               ; <i8> [#uses=1]
 117         %B = lshr i8 %a, 3              ; <i8> [#uses=1]
 118         %C = shl i8 %B, 4               ; <i8> [#uses=1]
 119         ret i8 %C
 120 }
 121
 122 ;; (A >> 8) << 8 === A & -256
 123 define i32 @test12(i32 %A) {
 124 ; CHECK: @test12
 125 ; CHECK-NEXT: and i32 %A, -256
 126 ; CHECK-NEXT: ret i32
 127         %B = ashr i32 %A, 8             ; <i32> [#uses=1]
 128         %C = shl i32 %B, 8              ; <i32> [#uses=1]
 129         ret i32 %C
 130 }
 131
 132 ;; (A >> 3) << 4 === (A & -8) * 2
 133 define i8 @test13(i8 %A) {
 134 ; CHECK: @test13
 135 ; CHECK-NEXT: mul i8 %A, 6
 136 ; CHECK-NEXT: and i8
 137 ; CHECK-NEXT: ret i8
 138         %a = mul i8 %A, 3               ; <i8> [#uses=1]
 139         %B = ashr i8 %a, 3              ; <i8> [#uses=1]
 140         %C = shl i8 %B, 4               ; <i8> [#uses=1]
 141         ret i8 %C
 142 }
 143
 144 ;; D = ((B | 1234) << 4) === ((B << 4)|(1234 << 4)
 145 define i32 @test14(i32 %A) {
 146 ; CHECK: @test14
 147 ; CHECK-NEXT: %B = and i32 %A, -19760
 148 ; CHECK-NEXT: or i32 %B, 19744
 149 ; CHECK-NEXT: ret i32
 150         %B = lshr i32 %A, 4             ; <i32> [#uses=1]
 151         %C = or i32 %B, 1234            ; <i32> [#uses=1]
 152         %D = shl i32 %C, 4              ; <i32> [#uses=1]
 153         ret i32 %D
 154 }
 155
 156 ;; D = ((B | 1234) << 4) === ((B << 4)|(1234 << 4)
 157 define i32 @test14a(i32 %A) {
 158 ; CHECK: @test14a
 159 ; CHECK-NEXT: and i32 %A, 77
 160 ; CHECK-NEXT: ret i32
 161         %B = shl i32 %A, 4              ; <i32> [#uses=1]
 162         %C = and i32 %B, 1234           ; <i32> [#uses=1]
 163         %D = lshr i32 %C, 4             ; <i32> [#uses=1]
 164         ret i32 %D
 165 }
 166
 167 define i32 @test15(i1 %C) {
 168 ; CHECK: @test15
 169 ; CHECK-NEXT: select i1 %C, i32 12, i32 4
 170 ; CHECK-NEXT: ret i32
 171         %A = select i1 %C, i32 3, i32 1         ; <i32> [#uses=1]
 172         %V = shl i32 %A, 2              ; <i32> [#uses=1]
 173         ret i32 %V
 174 }
 175
 176 define i32 @test15a(i1 %C) {
 177 ; CHECK: @test15a
 178 ; CHECK-NEXT: select i1 %C, i32 512, i32 128
 179 ; CHECK-NEXT: ret i32
 180         %A = select i1 %C, i8 3, i8 1           ; <i8> [#uses=1]
 181         %shift.upgrd.4 = zext i8 %A to i32              ; <i32> [#uses=1]
 182         %V = shl i32 64, %shift.upgrd.4         ; <i32> [#uses=1]
 183         ret i32 %V
 184 }
 185
 186 define i1 @test16(i32 %X) {
 187 ; CHECK: @test16
 188 ; CHECK-NEXT: and i32 %X, 16
 189 ; CHECK-NEXT: icmp ne i32
 190 ; CHECK-NEXT: ret i1
 191         %tmp.3 = ashr i32 %X, 4
 192         %tmp.6 = and i32 %tmp.3, 1
 193         %tmp.7 = icmp ne i32 %tmp.6, 0
 194         ret i1 %tmp.7
 195 }
 196
 197 define i1 @test17(i32 %A) {
 198 ; CHECK: @test17
 199 ; CHECK-NEXT: and i32 %A, -8
 200 ; CHECK-NEXT: icmp eq i32
 201 ; CHECK-NEXT: ret i1
 202         %B = lshr i32 %A, 3             ; <i32> [#uses=1]
 203         %C = icmp eq i32 %B, 1234               ; <i1> [#uses=1]
 204         ret i1 %C
 205 }
 206
 207
 208 define i1 @test18(i8 %A) {
 209 ; CHECK: @test18
 210 ; CHECK: ret i1 false
 211
 212         %B = lshr i8 %A, 7              ; <i8> [#uses=1]
 213         ;; false
 214         %C = icmp eq i8 %B, 123         ; <i1> [#uses=1]
 215         ret i1 %C
 216 }
 217
 218 define i1 @test19(i32 %A) {
 219 ; CHECK: @test19
 220 ; CHECK-NEXT: icmp ult i32 %A, 4
 221 ; CHECK-NEXT: ret i1
 222         %B = ashr i32 %A, 2             ; <i32> [#uses=1]
 223         ;; (X & -4) == 0
 224         %C = icmp eq i32 %B, 0          ; <i1> [#uses=1]
 225         ret i1 %C
 226 }
 227
 228
 229 define i1 @test19a(i32 %A) {
 230 ; CHECK: @test19a
 231 ; CHECK-NEXT: and i32 %A, -4
 232 ; CHECK-NEXT: icmp eq i32
 233 ; CHECK-NEXT: ret i1
 234         %B = ashr i32 %A, 2             ; <i32> [#uses=1]
 235         ;; (X & -4) == -4
 236         %C = icmp eq i32 %B, -1         ; <i1> [#uses=1]
 237         ret i1 %C
 238 }
 239
 240 define i1 @test20(i8 %A) {
 241 ; CHECK: @test20
 242 ; CHECK: ret i1 false
 243         %B = ashr i8 %A, 7              ; <i8> [#uses=1]
 244         ;; false
 245         %C = icmp eq i8 %B, 123         ; <i1> [#uses=1]
 246         ret i1 %C
 247 }
 248
 249 define i1 @test21(i8 %A) {
 250 ; CHECK: @test21
 251 ; CHECK-NEXT: and i8 %A, 15
 252 ; CHECK-NEXT: icmp eq i8
 253 ; CHECK-NEXT: ret i1
 254         %B = shl i8 %A, 4               ; <i8> [#uses=1]
 255         %C = icmp eq i8 %B, -128                ; <i1> [#uses=1]
 256         ret i1 %C
 257 }
 258
 259 define i1 @test22(i8 %A) {
 260 ; CHECK: @test22
 261 ; CHECK-NEXT: and i8 %A, 15
 262 ; CHECK-NEXT: icmp eq i8
 263 ; CHECK-NEXT: ret i1
 264         %B = shl i8 %A, 4               ; <i8> [#uses=1]
 265         %C = icmp eq i8 %B, 0           ; <i1> [#uses=1]
 266         ret i1 %C
 267 }
 268
 269 define i8 @test23(i32 %A) {
 270 ; CHECK: @test23
 271 ; CHECK-NEXT: trunc i32 %A to i8
 272 ; CHECK-NEXT: ret i8
 273
 274         ;; casts not needed
 275         %B = shl i32 %A, 24             ; <i32> [#uses=1]
 276         %C = ashr i32 %B, 24            ; <i32> [#uses=1]
 277         %D = trunc i32 %C to i8         ; <i8> [#uses=1]
 278         ret i8 %D
 279 }
 280
 281 define i8 @test24(i8 %X) {
 282 ; CHECK: @test24
 283 ; CHECK-NEXT: and i8 %X, 3
 284 ; CHECK-NEXT: ret i8
 285         %Y = and i8 %X, -5              ; <i8> [#uses=1]
 286         %Z = shl i8 %Y, 5               ; <i8> [#uses=1]
 287         %Q = ashr i8 %Z, 5              ; <i8> [#uses=1]
 288         ret i8 %Q
 289 }
 290
 291 define i32 @test25(i32 %tmp.2, i32 %AA) {
 292 ; CHECK: @test25
 293 ; CHECK-NEXT: and i32 %tmp.2, -131072
 294 ; CHECK-NEXT: add i32 %{{[^,]*}}, %AA
 295 ; CHECK-NEXT: and i32 %{{[^,]*}}, -131072
 296 ; CHECK-NEXT: ret i32
 297         %x = lshr i32 %AA, 17           ; <i32> [#uses=1]
 298         %tmp.3 = lshr i32 %tmp.2, 17            ; <i32> [#uses=1]
 299         %tmp.5 = add i32 %tmp.3, %x             ; <i32> [#uses=1]
 300         %tmp.6 = shl i32 %tmp.5, 17             ; <i32> [#uses=1]
 301         ret i32 %tmp.6
 302 }
 303
 304 ;; handle casts between shifts.
 305 define i32 @test26(i32 %A) {
 306 ; CHECK: @test26
 307 ; CHECK-NEXT: and i32 %A, -2
 308 ; CHECK-NEXT: ret i32
 309         %B = lshr i32 %A, 1             ; <i32> [#uses=1]
 310         %C = bitcast i32 %B to i32              ; <i32> [#uses=1]
 311         %D = shl i32 %C, 1              ; <i32> [#uses=1]
 312         ret i32 %D
 313 }
 314
 315
 316 define i1 @test27(i32 %x) nounwind {
 317 ; CHECK: @test27
 318 ; CHECK-NEXT: and i32 %x, 8
 319 ; CHECK-NEXT: icmp ne i32
 320 ; CHECK-NEXT: ret i1
 321   %y = lshr i32 %x, 3
 322   %z = trunc i32 %y to i1
 323   ret i1 %z
 324 }
 325
 326 define i8 @test28(i8 %x) {
 327 entry:
 328 ; CHECK: @test28
 329 ; CHECK:     icmp slt i8 %x, 0
 330 ; CHECK-NEXT:     br i1
 331         %tmp1 = lshr i8 %x, 7
 332         %cond1 = icmp ne i8 %tmp1, 0
 333         br i1 %cond1, label %bb1, label %bb2
 334
 335 bb1:
 336         ret i8 0
 337
 338 bb2:
 339         ret i8 1
 340 }
 341
 342 define i8 @test28a(i8 %x, i8 %y) {
 343 entry:
 344 ; This shouldn't be transformed.
 345 ; CHECK: @test28a
 346 ; CHECK:     %tmp1 = lshr i8 %x, 7
 347 ; CHECK:     %cond1 = icmp eq i8 %tmp1, 0
 348 ; CHECK:     br i1 %cond1, label %bb2, label %bb1
 349         %tmp1 = lshr i8 %x, 7
 350         %cond1 = icmp ne i8 %tmp1, 0
 351         br i1 %cond1, label %bb1, label %bb2
 352 bb1:
 353         ret i8 %tmp1
 354 bb2:
 355         %tmp2 = add i8 %tmp1, %y
 356         ret i8 %tmp2
 357 }
 358
 359
 360 define i32 @test29(i64 %d18) {
 361 entry:
 362         %tmp916 = lshr i64 %d18, 32
 363         %tmp917 = trunc i64 %tmp916 to i32
 364         %tmp10 = lshr i32 %tmp917, 31
 365         ret i32 %tmp10
 366 ; CHECK: @test29
 367 ; CHECK:  %tmp916 = lshr i64 %d18, 63
 368 ; CHECK:  %tmp10 = trunc i64 %tmp916 to i32
 369 }
 370
 371
 372 define i32 @test30(i32 %A, i32 %B, i32 %C) {
 373         %X = shl i32 %A, %C
 374         %Y = shl i32 %B, %C
 375         %Z = and i32 %X, %Y
 376         ret i32 %Z
 377 ; CHECK: @test30
 378 ; CHECK: %X1 = and i32 %A, %B
 379 ; CHECK: %Z = shl i32 %X1, %C
 380 }
 381
 382 define i32 @test31(i32 %A, i32 %B, i32 %C) {
 383         %X = lshr i32 %A, %C
 384         %Y = lshr i32 %B, %C
 385         %Z = or i32 %X, %Y
 386         ret i32 %Z
 387 ; CHECK: @test31
 388 ; CHECK: %X1 = or i32 %A, %B
 389 ; CHECK: %Z = lshr i32 %X1, %C
 390 }
 391
 392 define i32 @test32(i32 %A, i32 %B, i32 %C) {
 393         %X = ashr i32 %A, %C
 394         %Y = ashr i32 %B, %C
 395         %Z = xor i32 %X, %Y
 396         ret i32 %Z
 397 ; CHECK: @test32
 398 ; CHECK: %X1 = xor i32 %A, %B
 399 ; CHECK: %Z = ashr i32 %X1, %C
 400 ; CHECK: ret i32 %Z
 401 }
 402
 403 define i1 @test33(i32 %X) {
 404         %tmp1 = shl i32 %X, 7
 405         %tmp2 = icmp slt i32 %tmp1, 0
 406         ret i1 %tmp2
 407 ; CHECK: @test33
 408 ; CHECK: %tmp1.mask = and i32 %X, 16777216
 409 ; CHECK: %tmp2 = icmp ne i32 %tmp1.mask, 0
 410 }
 411
 412 define i1 @test34(i32 %X) {
 413         %tmp1 = lshr i32 %X, 7
 414         %tmp2 = icmp slt i32 %tmp1, 0
 415         ret i1 %tmp2
 416 ; CHECK: @test34
 417 ; CHECK: ret i1 false
 418 }
 419
 420 define i1 @test35(i32 %X) {
 421         %tmp1 = ashr i32 %X, 7
 422         %tmp2 = icmp slt i32 %tmp1, 0
 423         ret i1 %tmp2
 424 ; CHECK: @test35
 425 ; CHECK: %tmp2 = icmp slt i32 %X, 0
 426 ; CHECK: ret i1 %tmp2
 427 }
 428
 429 define i128 @test36(i128 %A, i128 %B) {
 430 entry:
 431   %tmp27 = shl i128 %A, 64
 432   %tmp23 = shl i128 %B, 64
 433   %ins = or i128 %tmp23, %tmp27
 434   %tmp45 = lshr i128 %ins, 64
 435   ret i128 %tmp45
 436
 437 ; CHECK: @test36
 438 ; CHECK:  %tmp231 = or i128 %B, %A
 439 ; CHECK:  %ins = and i128 %tmp231, 18446744073709551615
 440 ; CHECK:  ret i128 %ins
 441 }
 442
 443 define i64 @test37(i128 %A, i32 %B) {
 444 entry:
 445   %tmp27 = shl i128 %A, 64
 446   %tmp22 = zext i32 %B to i128
 447   %tmp23 = shl i128 %tmp22, 96
 448   %ins = or i128 %tmp23, %tmp27
 449   %tmp45 = lshr i128 %ins, 64
 450   %tmp46 = trunc i128 %tmp45 to i64
 451   ret i64 %tmp46
 452
 453 ; CHECK: @test37
 454 ; CHECK:  %tmp23 = shl nuw nsw i128 %tmp22, 32
 455 ; CHECK:  %ins = or i128 %tmp23, %A
 456 ; CHECK:  %tmp46 = trunc i128 %ins to i64
 457 }
 458
 459 define i32 @test38(i32 %x) nounwind readnone {
 460   %rem = srem i32 %x, 32
 461   %shl = shl i32 1, %rem
 462   ret i32 %shl
 463 ; CHECK: @test38
 464 ; CHECK-NEXT: and i32 %x, 31
 465 ; CHECK-NEXT: shl i32 1
 466 ; CHECK-NEXT: ret i32
 467 }
 468
 469 ; <rdar://problem/8756731>
 470 ; CHECK: @test39
 471 define i8 @test39(i32 %a0) {
 472 entry:
 473   %tmp4 = trunc i32 %a0 to i8
 474 ; CHECK: and i8 %tmp49, 64
 475   %tmp5 = shl i8 %tmp4, 5
 476   %tmp48 = and i8 %tmp5, 32
 477   %tmp49 = lshr i8 %tmp48, 5
 478   %tmp50 = mul i8 %tmp49, 64
 479   %tmp51 = xor i8 %tmp50, %tmp5
 480 ; CHECK: and i8 %0, 16
 481   %tmp52 = and i8 %tmp51, -128
 482   %tmp53 = lshr i8 %tmp52, 7
 483   %tmp54 = mul i8 %tmp53, 16
 484   %tmp55 = xor i8 %tmp54, %tmp51
 485 ; CHECK: ret i8 %tmp551
 486   ret i8 %tmp55
 487 }
 488
 489 ; PR9809
 490 define i32 @test40(i32 %a, i32 %b) nounwind {
 491   %shl1 = shl i32 1, %b
 492   %shl2 = shl i32 %shl1, 2
 493   %div = udiv i32 %a, %shl2
 494   ret i32 %div
 495 ; CHECK: @test40
 496 ; CHECK-NEXT: add i32 %b, 2
 497 ; CHECK-NEXT: lshr i32 %a
 498 ; CHECK-NEXT: ret i32
 499 }
 500
 501 define i32 @test41(i32 %a, i32 %b) nounwind {
 502   %1 = shl i32 1, %b
 503   %2 = shl i32 %1, 3
 504   ret i32 %2
 505 ; CHECK: @test41
 506 ; CHECK-NEXT: shl i32 8, %b
 507 ; CHECK-NEXT: ret i32
 508 }
 509
 510 define i32 @test42(i32 %a, i32 %b) nounwind {
 511   %div = lshr i32 4096, %b    ; must be exact otherwise we'd divide by zero
 512   %div2 = udiv i32 %a, %div
 513   ret i32 %div2
 514 ; CHECK: @test42
 515 ; CHECK-NEXT: lshr exact i32 4096, %b
 516 }
 517
 518 define i32 @test43(i32 %a, i32 %b) nounwind {
 519   %div = shl i32 4096, %b    ; must be exact otherwise we'd divide by zero
 520   %div2 = udiv i32 %a, %div
 521   ret i32 %div2
 522 ; CHECK: @test43
 523 ; CHECK-NEXT: add i32 %b, 12
 524 ; CHECK-NEXT: lshr
 525 ; CHECK-NEXT: ret
 526 }
 527
 528
 529