1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -passes=instcombine -S | FileCheck %s 3 4define i64 @test1(i64 %A, i32 %B) { 5; CHECK-LABEL: @test1( 6; CHECK-NEXT: [[TMP6:%.*]] = and i64 [[A:%.*]], 123 7; CHECK-NEXT: ret i64 [[TMP6]] 8; 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 14} 15 16define i32 @test2(i32 %A) { 17; CHECK-LABEL: @test2( 18; CHECK-NEXT: [[F:%.*]] = and i32 [[A:%.*]], 39 19; CHECK-NEXT: ret i32 [[F]] 20; 21 %B = and i32 %A, 7 22 %C = and i32 %A, 32 23 %F = add i32 %B, %C 24 ret i32 %F 25} 26 27define 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 disjoint i32 [[B]], [[C]] 32; CHECK-NEXT: ret i32 [[F]] 33; 34 %B = and i32 %A, 128 35 %C = lshr i32 %A, 30 36 %F = add i32 %B, %C 37 ret i32 %F 38} 39 40define i32 @test4(i32 %A) { 41; CHECK-LABEL: @test4( 42; CHECK-NEXT: [[B:%.*]] = shl nuw i32 [[A:%.*]], 1 43; CHECK-NEXT: ret i32 [[B]] 44; 45 %B = add nuw i32 %A, %A 46 ret i32 %B 47} 48 49define <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]] 53; 54 %add = add <2 x i1> %A, %B 55 ret <2 x i1> %add 56} 57 58define <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]] 62; 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 66} 67 68define <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]] 72; 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 77} 78 79define i16 @test9(i16 %a) { 80; CHECK-LABEL: @test9( 81; CHECK-NEXT: [[D:%.*]] = mul i16 [[A:%.*]], -32767 82; CHECK-NEXT: ret i16 [[D]] 83; 84 %b = mul i16 %a, 2 85 %c = mul i16 %a, 32767 86 %d = add i16 %b, %c 87 ret i16 %d 88} 89 90; y + (~((x >> 3) & 0x55555555) + 1) -> y - ((x >> 3) & 0x55555555) 91define 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: [[ADD1:%.*]] = sub i32 [[Y:%.*]], [[TMP1]] 96; CHECK-NEXT: ret i32 [[ADD1]] 97; 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 104} 105 106; y + (~(x & 0x55555555) + 1) -> y - (x & 0x55555555) 107define i32 @test11(i32 %x, i32 %y) { 108; CHECK-LABEL: @test11( 109; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655765 110; CHECK-NEXT: [[ADD1:%.*]] = sub i32 [[Y:%.*]], [[TMP1]] 111; CHECK-NEXT: ret i32 [[ADD1]] 112; 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 118} 119 120; (y + 1) + ~(x & 0x55555555) -> y - (x & 0x55555555) 121define i32 @test12(i32 %x, i32 %y) { 122; CHECK-LABEL: @test12( 123; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655765 124; CHECK-NEXT: [[ADD1:%.*]] = sub i32 [[Y:%.*]], [[TMP1]] 125; CHECK-NEXT: ret i32 [[ADD1]] 126; 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 132} 133 134; y + (~(x & 0x55555556) + 1) -> y - (x & 0x55555556) 135define i32 @test13(i32 %x, i32 %y) { 136; CHECK-LABEL: @test13( 137; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655766 138; CHECK-NEXT: [[ADD1:%.*]] = sub i32 [[Y:%.*]], [[TMP1]] 139; CHECK-NEXT: ret i32 [[ADD1]] 140; 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 146} 147 148; (y + 1) + ~(x & 0x55555556) -> y - (x & 0x55555556) 149define i32 @test14(i32 %x, i32 %y) { 150; CHECK-LABEL: @test14( 151; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[X:%.*]], 1431655766 152; CHECK-NEXT: [[ADD1:%.*]] = sub i32 [[Y:%.*]], [[TMP1]] 153; CHECK-NEXT: ret i32 [[ADD1]] 154; 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 160} 161 162; y + (~(x | 0x55555556) + 1) -> y - (x | 0x55555556) 163define 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]] 168; 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 174} 175 176; (y + 1) + ~(x | 0x55555556) -> y - (x | 0x555555556) 177define 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]] 182; 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 188} 189 190; y + (~(x | 0x55555555) + 1) -> y - (x | 0x55555555) 191define 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]] 196; 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 201} 202 203; (y + 1) + ~(x | 0x55555555) -> y - (x | 0x55555555) 204define 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]] 209; 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 215} 216 217define 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]] 221; 222 %add1 = add nsw i16 %x, %x 223 %add2 = add nsw i16 %add1, %x 224 ret i16 %add2 225} 226 227define 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]] 231; 232 %mul1 = mul nsw i16 %x, 8 233 %add2 = add nsw i16 %x, %mul1 234 ret i16 %add2 235} 236 237define 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]] 241; 242 %mul1 = mul nsw i16 %x, 8 243 %add2 = add nsw i16 %mul1, %x 244 ret i16 %add2 245} 246 247define 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]] 251; 252 %mul1 = mul i16 %a, 2 253 %mul2 = mul i16 %a, 3 254 %add = add nsw i16 %mul1, %mul2 255 ret i16 %add 256} 257 258define 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]] 262; 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 267} 268 269define 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]] 273; 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 278} 279 280define 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]] 285; 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 290} 291 292define 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]] 296; 297 %mul1 = mul nsw i16 %x, 32767 298 %add2 = add nsw i16 %x, %mul1 299 ret i16 %add2 300} 301 302define 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]] 306; 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 311} 312 313define 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]] 317; 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 322} 323 324@g = external global i8 325 326define i32 @shl_add_to_shl_constexpr() { 327; CHECK-LABEL: @shl_add_to_shl_constexpr( 328; CHECK-NEXT: ret i32 mul (i32 ptrtoint (ptr @g to i32), i32 4) 329; 330 %shl = shl i32 ptrtoint (ptr @g to i32), 1 331 %add = add i32 %shl, %shl 332 ret i32 %add 333} 334 335; This test and the next test verify that when a range metadata is attached to 336; llvm.cttz, ValueTracking correctly intersects the range specified by the 337; metadata and the range implied by the intrinsic. 338; 339; In this test, the range specified by the metadata is more strict. Therefore, 340; ValueTracking uses that range. 341define i16 @add_cttz(i16 %a) { 342; CHECK-LABEL: @add_cttz( 343; CHECK-NEXT: [[CTTZ:%.*]] = call i16 @llvm.cttz.i16(i16 [[A:%.*]], i1 true), !range [[RNG0:![0-9]+]] 344; CHECK-NEXT: [[B:%.*]] = or disjoint i16 [[CTTZ]], -8 345; CHECK-NEXT: ret i16 [[B]] 346; 347 ; llvm.cttz.i16(..., /*is_zero_undefined=*/true) implies the value returned 348 ; is in [0, 16). The range metadata indicates the value returned is in [0, 8). 349 ; Intersecting these ranges, we know the value returned is in [0, 8). 350 ; Therefore, InstCombine will transform 351 ; add %cttz, 1111 1111 1111 1000 ; decimal -8 352 ; to 353 ; or %cttz, 1111 1111 1111 1000 354 %cttz = call i16 @llvm.cttz.i16(i16 %a, i1 true), !range !0 355 %b = add i16 %cttz, -8 356 ret i16 %b 357} 358declare i16 @llvm.cttz.i16(i16, i1) 359!0 = !{i16 0, i16 8} 360 361; Similar to @add_cttz, but in this test, the range implied by the 362; intrinsic is more strict. Therefore, ValueTracking uses that range. 363define i16 @add_cttz_2(i16 %a) { 364; CHECK-LABEL: @add_cttz_2( 365; CHECK-NEXT: [[CTTZ:%.*]] = call i16 @llvm.cttz.i16(i16 [[A:%.*]], i1 true), !range [[RNG1:![0-9]+]] 366; CHECK-NEXT: [[B:%.*]] = or disjoint i16 [[CTTZ]], -16 367; CHECK-NEXT: ret i16 [[B]] 368; 369 ; llvm.cttz.i16(..., /*is_zero_undefined=*/true) implies the value returned 370 ; is in [0, 16). The range metadata indicates the value returned is in 371 ; [0, 32). Intersecting these ranges, we know the value returned is in 372 ; [0, 16). Therefore, InstCombine will transform 373 ; add %cttz, 1111 1111 1111 0000 ; decimal -16 374 ; to 375 ; or %cttz, 1111 1111 1111 0000 376 %cttz = call i16 @llvm.cttz.i16(i16 %a, i1 true), !range !1 377 %b = add i16 %cttz, -16 378 ret i16 %b 379} 380!1 = !{i16 0, i16 32} 381 382define i32 @add_or_and(i32 %x, i32 %y) { 383; CHECK-LABEL: @add_or_and( 384; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]] 385; CHECK-NEXT: ret i32 [[ADD]] 386; 387 %or = or i32 %x, %y 388 %and = and i32 %x, %y 389 %add = add i32 %or, %and 390 ret i32 %add 391} 392 393define i32 @add_or_and_commutative(i32 %x, i32 %y) { 394; CHECK-LABEL: @add_or_and_commutative( 395; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]] 396; CHECK-NEXT: ret i32 [[ADD]] 397; 398 %or = or i32 %x, %y 399 %and = and i32 %y, %x ; swapped 400 %add = add i32 %or, %and 401 ret i32 %add 402} 403 404define i32 @add_and_or(i32 %x, i32 %y) { 405; CHECK-LABEL: @add_and_or( 406; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]] 407; CHECK-NEXT: ret i32 [[ADD]] 408; 409 %or = or i32 %x, %y 410 %and = and i32 %x, %y 411 %add = add i32 %and, %or 412 ret i32 %add 413} 414 415define i32 @add_and_or_commutative(i32 %x, i32 %y) { 416; CHECK-LABEL: @add_and_or_commutative( 417; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], [[Y:%.*]] 418; CHECK-NEXT: ret i32 [[ADD]] 419; 420 %or = or i32 %x, %y 421 %and = and i32 %y, %x ; swapped 422 %add = add i32 %and, %or 423 ret i32 %add 424} 425 426define i32 @add_nsw_or_and(i32 %x, i32 %y) { 427; CHECK-LABEL: @add_nsw_or_and( 428; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[X:%.*]], [[Y:%.*]] 429; CHECK-NEXT: ret i32 [[ADD]] 430; 431 %or = or i32 %x, %y 432 %and = and i32 %x, %y 433 %add = add nsw i32 %or, %and 434 ret i32 %add 435} 436 437define i32 @add_nuw_or_and(i32 %x, i32 %y) { 438; CHECK-LABEL: @add_nuw_or_and( 439; CHECK-NEXT: [[ADD:%.*]] = add nuw i32 [[X:%.*]], [[Y:%.*]] 440; CHECK-NEXT: ret i32 [[ADD]] 441; 442 %or = or i32 %x, %y 443 %and = and i32 %x, %y 444 %add = add nuw i32 %or, %and 445 ret i32 %add 446} 447 448define i32 @add_nuw_nsw_or_and(i32 %x, i32 %y) { 449; CHECK-LABEL: @add_nuw_nsw_or_and( 450; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i32 [[X:%.*]], [[Y:%.*]] 451; CHECK-NEXT: ret i32 [[ADD]] 452; 453 %or = or i32 %x, %y 454 %and = and i32 %x, %y 455 %add = add nsw nuw i32 %or, %and 456 ret i32 %add 457} 458 459; A *nsw B + A *nsw C != A *nsw (B + C) 460; e.g. A = -1, B = 1, C = INT_SMAX 461 462define i8 @add_of_mul(i8 %x, i8 %y, i8 %z) { 463; CHECK-LABEL: @add_of_mul( 464; CHECK-NEXT: entry: 465; CHECK-NEXT: [[MB1:%.*]] = add i8 [[Y:%.*]], [[Z:%.*]] 466; CHECK-NEXT: [[SUM:%.*]] = mul i8 [[X:%.*]], [[MB1]] 467; CHECK-NEXT: ret i8 [[SUM]] 468; 469 entry: 470 %mA = mul nsw i8 %x, %y 471 %mB = mul nsw i8 %x, %z 472 %sum = add nsw i8 %mA, %mB 473 ret i8 %sum 474} 475 476define i32 @add_of_selects(i1 %A, i32 %B) { 477; CHECK-LABEL: @add_of_selects( 478; CHECK-NEXT: [[ADD:%.*]] = select i1 [[A:%.*]], i32 [[B:%.*]], i32 0 479; CHECK-NEXT: ret i32 [[ADD]] 480; 481 %sel0 = select i1 %A, i32 0, i32 -2 482 %sel1 = select i1 %A, i32 %B, i32 2 483 %add = add i32 %sel0, %sel1 484 ret i32 %add 485} 486 487; The ADD can't cause overflow out of the low 4 bits so the OR can be removed. 488 489define i32 @add_undemanded_low_bits(i32 %x) { 490; CHECK-LABEL: @add_undemanded_low_bits( 491; CHECK-NEXT: [[ADD:%.*]] = add i32 [[X:%.*]], 1616 492; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[ADD]], 4 493; CHECK-NEXT: ret i32 [[SHR]] 494; 495 %or = or i32 %x, 15 496 %add = add i32 %or, 1616 497 %shr = lshr i32 %add, 4 498 ret i32 %shr 499} 500 501define i32 @sub_undemanded_low_bits(i32 %x) { 502; CHECK-LABEL: @sub_undemanded_low_bits( 503; CHECK-NEXT: [[SUB:%.*]] = add i32 [[X:%.*]], -1616 504; CHECK-NEXT: [[SHR:%.*]] = lshr i32 [[SUB]], 4 505; CHECK-NEXT: ret i32 [[SHR]] 506; 507 %or = or i32 %x, 15 508 %sub = sub i32 %or, 1616 509 %shr = lshr i32 %sub, 4 510 ret i32 %shr 511} 512