1; This test makes sure that these instructions are properly eliminated. 2; 3; RUN: opt < %s -instcombine -S | FileCheck %s 4 5define 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 12define 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 20define 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 27define 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 36define 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 43define 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 50define 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 57define 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 64define 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 73define 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 82define 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 91define 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 101define 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 111define 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 123define 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 133define 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) 145define 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) 157define 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 167define 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 176define 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 186define 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 197define 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 208define 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 218define 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 229define 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 240define 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 249define 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 259define 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 269define 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 281define 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 291define 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. 305define 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 316define 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 326define i8 @test28(i8 %x) { 327entry: 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 335bb1: 336 ret i8 0 337 338bb2: 339 ret i8 1 340} 341 342define i8 @test28a(i8 %x, i8 %y) { 343entry: 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 352bb1: 353 ret i8 %tmp1 354bb2: 355 %tmp2 = add i8 %tmp1, %y 356 ret i8 %tmp2 357} 358 359 360define i32 @test29(i64 %d18) { 361entry: 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 372define 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 382define 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 392define 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 403define 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 412define 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 420define 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 429define i128 @test36(i128 %A, i128 %B) { 430entry: 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 443define i64 @test37(i128 %A, i32 %B) { 444entry: 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 459define 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 471define i8 @test39(i32 %a0) { 472entry: 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 490define 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 501define 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 510define 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 518define 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 530