1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -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 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: [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]] 96; CHECK-NEXT: ret i32 [[SUB]] 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: [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]] 111; CHECK-NEXT: ret i32 [[SUB]] 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: [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]] 125; CHECK-NEXT: ret i32 [[SUB]] 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: [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]] 139; CHECK-NEXT: ret i32 [[SUB]] 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: [[SUB:%.*]] = sub i32 [[Y:%.*]], [[TMP1]] 153; CHECK-NEXT: ret i32 [[SUB]] 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; 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. 327; 328; In this test, the range specified by the metadata is more strict. Therefore, 329; ValueTracking uses that range. 330define 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]] 335; 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 346} 347declare i16 @llvm.cttz.i16(i16, i1) 348!0 = !{i16 0, i16 8} 349 350; Similar to @add_cttz, but in this test, the range implied by the 351; intrinsic is more strict. Therefore, ValueTracking uses that range. 352define 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]] 357; 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 368} 369!1 = !{i16 0, i16 32} 370 371define 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]] 375; 376 %or = or i32 %x, %y 377 %and = and i32 %x, %y 378 %add = add i32 %or, %and 379 ret i32 %add 380} 381 382define 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]] 386; 387 %or = or i32 %x, %y 388 %and = and i32 %y, %x ; swapped 389 %add = add i32 %or, %and 390 ret i32 %add 391} 392 393define 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]] 397; 398 %or = or i32 %x, %y 399 %and = and i32 %x, %y 400 %add = add i32 %and, %or 401 ret i32 %add 402} 403 404define 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]] 408; 409 %or = or i32 %x, %y 410 %and = and i32 %y, %x ; swapped 411 %add = add i32 %and, %or 412 ret i32 %add 413} 414 415define 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]] 419; 420 %or = or i32 %x, %y 421 %and = and i32 %x, %y 422 %add = add nsw i32 %or, %and 423 ret i32 %add 424} 425 426define 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]] 430; 431 %or = or i32 %x, %y 432 %and = and i32 %x, %y 433 %add = add nuw i32 %or, %and 434 ret i32 %add 435} 436 437define 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]] 441; 442 %or = or i32 %x, %y 443 %and = and i32 %x, %y 444 %add = add nsw nuw i32 %or, %and 445 ret i32 %add 446} 447 448; A *nsw B + A *nsw C != A *nsw (B + C) 449; e.g. A = -1, B = 1, C = INT_SMAX 450 451define 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]] 457; 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 463} 464 465define 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]] 469; 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 474} 475