1; RUN: opt < %s -instcombine -S | FileCheck %s 2 3define i64 @test1(i64 %A, i32 %B) { 4 %tmp12 = zext i32 %B to i64 5 %tmp3 = shl i64 %tmp12, 32 6 %tmp5 = add i64 %tmp3, %A 7 %tmp6 = and i64 %tmp5, 123 8 ret i64 %tmp6 9; CHECK-LABEL: @test1( 10; CHECK-NEXT: and i64 %A, 123 11; CHECK-NEXT: ret i64 12} 13 14define i32 @test2(i32 %A) { 15 %B = and i32 %A, 7 16 %C = and i32 %A, 32 17 %F = add i32 %B, %C 18 ret i32 %F 19; CHECK-LABEL: @test2( 20; CHECK-NEXT: and i32 %A, 39 21; CHECK-NEXT: ret i32 22} 23 24define i32 @test3(i32 %A) { 25 %B = and i32 %A, 128 26 %C = lshr i32 %A, 30 27 %F = add i32 %B, %C 28 ret i32 %F 29; CHECK-LABEL: @test3( 30; CHECK-NEXT: and 31; CHECK-NEXT: lshr 32; CHECK-NEXT: or i32 %B, %C 33; CHECK-NEXT: ret i32 34} 35 36define i32 @test4(i32 %A) { 37 %B = add nuw i32 %A, %A 38 ret i32 %B 39; CHECK-LABEL: @test4( 40; CHECK-NEXT: %B = shl nuw i32 %A, 1 41; CHECK-NEXT: ret i32 %B 42} 43 44define <2 x i1> @test5(<2 x i1> %A, <2 x i1> %B) { 45 %add = add <2 x i1> %A, %B 46 ret <2 x i1> %add 47; CHECK-LABEL: @test5( 48; CHECK-NEXT: %add = xor <2 x i1> %A, %B 49; CHECK-NEXT: ret <2 x i1> %add 50} 51 52define <2 x i64> @test6(<2 x i64> %A) { 53 %shl = shl <2 x i64> %A, <i64 2, i64 3> 54 %add = add <2 x i64> %shl, %A 55 ret <2 x i64> %add 56; CHECK-LABEL: @test6( 57; CHECK-NEXT: %add = mul <2 x i64> %A, <i64 5, i64 9> 58; CHECK-NEXT: ret <2 x i64> %add 59} 60 61define <2 x i64> @test7(<2 x i64> %A) { 62 %shl = shl <2 x i64> %A, <i64 2, i64 3> 63 %mul = mul <2 x i64> %A, <i64 3, i64 4> 64 %add = add <2 x i64> %shl, %mul 65 ret <2 x i64> %add 66; CHECK-LABEL: @test7( 67; CHECK-NEXT: %add = mul <2 x i64> %A, <i64 7, i64 12> 68; CHECK-NEXT: ret <2 x i64> %add 69} 70 71define <2 x i64> @test8(<2 x i64> %A) { 72 %xor = xor <2 x i64> %A, <i64 -1, i64 -1> 73 %add = add <2 x i64> %xor, <i64 2, i64 3> 74 ret <2 x i64> %add 75; CHECK-LABEL: @test8( 76; CHECK-NEXT: %add = sub <2 x i64> <i64 1, i64 2>, %A 77; CHECK-NEXT: ret <2 x i64> %add 78} 79 80define i16 @test9(i16 %a) { 81 %b = mul i16 %a, 2 82 %c = mul i16 %a, 32767 83 %d = add i16 %b, %c 84 ret i16 %d 85; CHECK-LABEL: @test9( 86; CHECK-NEXT: %d = mul i16 %a, -32767 87; CHECK-NEXT: ret i16 %d 88} 89 90; y + (~((x >> 3) & 0x55555555) + 1) -> y - ((x >> 3) & 0x55555555) 91define i32 @test10(i32 %x, i32 %y) { 92 %shr = ashr i32 %x, 3 93 %shr.not = or i32 %shr, -1431655766 94 %neg = xor i32 %shr.not, 1431655765 95 %add = add i32 %y, 1 96 %add1 = add i32 %add, %neg 97 ret i32 %add1 98; CHECK-LABEL: @test10( 99; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3 100; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 [[SHR]], 1431655765 101; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] 102; CHECK-NEXT: ret i32 [[SUB]] 103} 104 105; y + (~(x & 0x55555555) + 1) -> y - (x & 0x55555555) 106define i32 @test11(i32 %x, i32 %y) { 107 %x.not = or i32 %x, -1431655766 108 %neg = xor i32 %x.not, 1431655765 109 %add = add i32 %y, 1 110 %add1 = add i32 %add, %neg 111 ret i32 %add1 112; CHECK-LABEL: @test11( 113; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655765 114; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] 115; CHECK-NEXT: ret i32 [[SUB]] 116} 117 118; (y + 1) + ~(x & 0x55555555) -> y - (x & 0x55555555) 119define i32 @test12(i32 %x, i32 %y) { 120 %add = add nsw i32 %y, 1 121 %x.not = or i32 %x, -1431655766 122 %neg = xor i32 %x.not, 1431655765 123 %add1 = add nsw i32 %add, %neg 124 ret i32 %add1 125; CHECK-LABEL: @test12( 126; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655765 127; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] 128; CHECK-NEXT: ret i32 [[SUB]] 129} 130 131; y + (~(x & 0x55555556) + 1) -> y - (x & 0x55555556) 132define i32 @test13(i32 %x, i32 %y) { 133 %x.not = or i32 %x, -1431655767 134 %neg = xor i32 %x.not, 1431655766 135 %add = add i32 %y, 1 136 %add1 = add i32 %add, %neg 137 ret i32 %add1 138; CHECK-LABEL: @test13( 139; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655766 140; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] 141; CHECK-NEXT: ret i32 [[SUB]] 142} 143 144; (y + 1) + ~(x & 0x55555556) -> y - (x & 0x55555556) 145define i32 @test14(i32 %x, i32 %y) { 146 %add = add nsw i32 %y, 1 147 %x.not = or i32 %x, -1431655767 148 %neg = xor i32 %x.not, 1431655766 149 %add1 = add nsw i32 %add, %neg 150 ret i32 %add1 151; CHECK-LABEL: @test14( 152; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655766 153; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] 154; CHECK-NEXT: ret i32 [[SUB]] 155} 156 157; y + (~(x | 0x55555556) + 1) -> y - (x | 0x55555556) 158define i32 @test15(i32 %x, i32 %y) { 159 %x.not = and i32 %x, -1431655767 160 %neg = xor i32 %x.not, -1431655767 161 %add = add i32 %y, 1 162 %add1 = add i32 %add, %neg 163 ret i32 %add1 164; CHECK-LABEL: @test15( 165; CHECK-NEXT: [[AND:%[a-z0-9]+]] = or i32 %x, 1431655766 166; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] 167; CHECK-NEXT: ret i32 [[SUB]] 168} 169 170; (y + 1) + ~(x | 0x55555556) -> y - (x | 0x555555556) 171define i32 @test16(i32 %x, i32 %y) { 172 %add = add nsw i32 %y, 1 173 %x.not = and i32 %x, -1431655767 174 %neg = xor i32 %x.not, -1431655767 175 %add1 = add nsw i32 %add, %neg 176 ret i32 %add1 177; CHECK-LABEL: @test16( 178; CHECK-NEXT: [[AND:%[a-z0-9]+]] = or i32 %x, 1431655766 179; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] 180; CHECK-NEXT: ret i32 [[SUB]] 181} 182 183; y + (~(x | 0x55555555) + 1) -> y - (x | 0x55555555) 184define i32 @test17(i32 %x, i32 %y) { 185 %x.not = and i32 %x, -1431655766 186 %add2 = xor i32 %x.not, -1431655765 187 %add1 = add nsw i32 %add2, %y 188 ret i32 %add1 189; CHECK-LABEL: @test17( 190; CHECK-NEXT: [[AND:%[a-z0-9]+]] = or i32 %x, 1431655765 191; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] 192; CHECK-NEXT: ret i32 [[SUB]] 193} 194 195; (y + 1) + ~(x | 0x55555555) -> y - (x | 0x55555555) 196define i32 @test18(i32 %x, i32 %y) { 197 %add = add nsw i32 %y, 1 198 %x.not = and i32 %x, -1431655766 199 %neg = xor i32 %x.not, -1431655766 200 %add1 = add nsw i32 %add, %neg 201 ret i32 %add1 202; CHECK-LABEL: @test18( 203; CHECK-NEXT: [[AND:%[a-z0-9]+]] = or i32 %x, 1431655765 204; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]] 205; CHECK-NEXT: ret i32 [[SUB]] 206} 207 208define i16 @add_nsw_mul_nsw(i16 %x) { 209 %add1 = add nsw i16 %x, %x 210 %add2 = add nsw i16 %add1, %x 211 ret i16 %add2 212; CHECK-LABEL: @add_nsw_mul_nsw( 213; CHECK-NEXT: %add2 = mul nsw i16 %x, 3 214; CHECK-NEXT: ret i16 %add2 215} 216 217define i16 @mul_add_to_mul_1(i16 %x) { 218 %mul1 = mul nsw i16 %x, 8 219 %add2 = add nsw i16 %x, %mul1 220 ret i16 %add2 221; CHECK-LABEL: @mul_add_to_mul_1( 222; CHECK-NEXT: %add2 = mul nsw i16 %x, 9 223; CHECK-NEXT: ret i16 %add2 224} 225 226define i16 @mul_add_to_mul_2(i16 %x) { 227 %mul1 = mul nsw i16 %x, 8 228 %add2 = add nsw i16 %mul1, %x 229 ret i16 %add2 230; CHECK-LABEL: @mul_add_to_mul_2( 231; CHECK-NEXT: %add2 = mul nsw i16 %x, 9 232; CHECK-NEXT: ret i16 %add2 233} 234 235define i16 @mul_add_to_mul_3(i16 %a) { 236 %mul1 = mul i16 %a, 2 237 %mul2 = mul i16 %a, 3 238 %add = add nsw i16 %mul1, %mul2 239 ret i16 %add 240; CHECK-LABEL: @mul_add_to_mul_3( 241; CHECK-NEXT: %add = mul i16 %a, 5 242; CHECK-NEXT: ret i16 %add 243} 244 245define i16 @mul_add_to_mul_4(i16 %a) { 246 %mul1 = mul nsw i16 %a, 2 247 %mul2 = mul nsw i16 %a, 7 248 %add = add nsw i16 %mul1, %mul2 249 ret i16 %add 250; CHECK-LABEL: @mul_add_to_mul_4( 251; CHECK-NEXT: %add = mul nsw i16 %a, 9 252; CHECK-NEXT: ret i16 %add 253} 254 255define i16 @mul_add_to_mul_5(i16 %a) { 256 %mul1 = mul nsw i16 %a, 3 257 %mul2 = mul nsw i16 %a, 7 258 %add = add nsw i16 %mul1, %mul2 259 ret i16 %add 260; CHECK-LABEL: @mul_add_to_mul_5( 261; CHECK-NEXT: %add = mul nsw i16 %a, 10 262; CHECK-NEXT: ret i16 %add 263} 264 265define i32 @mul_add_to_mul_6(i32 %x, i32 %y) { 266 %mul1 = mul nsw i32 %x, %y 267 %mul2 = mul nsw i32 %mul1, 5 268 %add = add nsw i32 %mul1, %mul2 269 ret i32 %add 270; CHECK-LABEL: @mul_add_to_mul_6( 271; CHECK-NEXT: %mul1 = mul nsw i32 %x, %y 272; CHECK-NEXT: %add = mul nsw i32 %mul1, 6 273; CHECK-NEXT: ret i32 %add 274} 275 276define i16 @mul_add_to_mul_7(i16 %x) { 277 %mul1 = mul nsw i16 %x, 32767 278 %add2 = add nsw i16 %x, %mul1 279 ret i16 %add2 280; CHECK-LABEL: @mul_add_to_mul_7( 281; CHECK-NEXT: %add2 = shl i16 %x, 15 282; CHECK-NEXT: ret i16 %add2 283} 284 285define i16 @mul_add_to_mul_8(i16 %a) { 286 %mul1 = mul nsw i16 %a, 16383 287 %mul2 = mul nsw i16 %a, 16384 288 %add = add nsw i16 %mul1, %mul2 289 ret i16 %add 290; CHECK-LABEL: @mul_add_to_mul_8( 291; CHECK-NEXT: %add = mul nsw i16 %a, 32767 292; CHECK-NEXT: ret i16 %add 293} 294 295define i16 @mul_add_to_mul_9(i16 %a) { 296 %mul1 = mul nsw i16 %a, 16384 297 %mul2 = mul nsw i16 %a, 16384 298 %add = add nsw i16 %mul1, %mul2 299 ret i16 %add 300; CHECK-LABEL: @mul_add_to_mul_9( 301; CHECK-NEXT: %add = shl i16 %a, 15 302; CHECK-NEXT: ret i16 %add 303} 304 305; This test and the next test verify that when a range metadata is attached to 306; llvm.cttz, ValueTracking correctly intersects the range specified by the 307; metadata and the range implied by the intrinsic. 308; 309; In this test, the range specified by the metadata is more strict. Therefore, 310; ValueTracking uses that range. 311define i16 @add_cttz(i16 %a) { 312; CHECK-LABEL: @add_cttz( 313 ; llvm.cttz.i16(..., /*is_zero_undefined=*/true) implies the value returned 314 ; is in [0, 16). The range metadata indicates the value returned is in [0, 8). 315 ; Intersecting these ranges, we know the value returned is in [0, 8). 316 ; Therefore, InstCombine will transform 317 ; add %cttz, 1111 1111 1111 1000 ; decimal -8 318 ; to 319 ; or %cttz, 1111 1111 1111 1000 320 %cttz = call i16 @llvm.cttz.i16(i16 %a, i1 true), !range !0 321 %b = add i16 %cttz, -8 322; CHECK: or i16 %cttz, -8 323 ret i16 %b 324} 325declare i16 @llvm.cttz.i16(i16, i1) 326!0 = !{i16 0, i16 8} 327 328; Similar to @add_cttz, but in this test, the range implied by the 329; intrinsic is more strict. Therefore, ValueTracking uses that range. 330define i16 @add_cttz_2(i16 %a) { 331; CHECK-LABEL: @add_cttz_2( 332 ; llvm.cttz.i16(..., /*is_zero_undefined=*/true) implies the value returned 333 ; is in [0, 16). The range metadata indicates the value returned is in 334 ; [0, 32). Intersecting these ranges, we know the value returned is in 335 ; [0, 16). Therefore, InstCombine will transform 336 ; add %cttz, 1111 1111 1111 0000 ; decimal -16 337 ; to 338 ; or %cttz, 1111 1111 1111 0000 339 %cttz = call i16 @llvm.cttz.i16(i16 %a, i1 true), !range !1 340 %b = add i16 %cttz, -16 341; CHECK: or i16 %cttz, -16 342 ret i16 %b 343} 344!1 = !{i16 0, i16 32} 345 346define i32 @add_or_and(i32 %x, i32 %y) { 347 %or = or i32 %x, %y 348 %and = and i32 %x, %y 349 %add = add i32 %or, %and 350 ret i32 %add 351; CHECK-LABEL: @add_or_and( 352; CHECK-NEXT: add i32 %x, %y 353; CHECK-NEXT: ret i32 354} 355 356define i32 @add_nsw_or_and(i32 %x, i32 %y) { 357 %or = or i32 %x, %y 358 %and = and i32 %x, %y 359 %add = add nsw i32 %or, %and 360 ret i32 %add 361; CHECK-LABEL: @add_nsw_or_and( 362; CHECK-NEXT: add nsw i32 %x, %y 363; CHECK-NEXT: ret i32 364} 365 366define i32 @add_nuw_or_and(i32 %x, i32 %y) { 367 %or = or i32 %x, %y 368 %and = and i32 %x, %y 369 %add = add nuw i32 %or, %and 370 ret i32 %add 371; CHECK-LABEL: @add_nuw_or_and( 372; CHECK-NEXT: add nuw i32 %x, %y 373; CHECK-NEXT: ret i32 374} 375 376define i32 @add_nuw_nsw_or_and(i32 %x, i32 %y) { 377 %or = or i32 %x, %y 378 %and = and i32 %x, %y 379 %add = add nsw nuw i32 %or, %and 380 ret i32 %add 381; CHECK-LABEL: @add_nuw_nsw_or_and( 382; CHECK-NEXT: add nuw nsw i32 %x, %y 383; CHECK-NEXT: ret i32 384} 385 386; A *nsw B + A *nsw C != A *nsw (B + C) 387; e.g. A = -1, B = 1, C = INT_SMAX 388 389define i8 @add_of_mul(i8 %x, i8 %y, i8 %z) { 390; CHECK-LABEL: @add_of_mul( 391 entry: 392 %mA = mul nsw i8 %x, %y 393 %mB = mul nsw i8 %x, %z 394; CHECK: %sum = mul i8 395 %sum = add nsw i8 %mA, %mB 396 ret i8 %sum 397} 398 399define i32 @add_of_selects(i1 %A, i32 %B) { 400 %sel0 = select i1 %A, i32 0, i32 -2 401 %sel1 = select i1 %A, i32 %B, i32 2 402 %add = add i32 %sel0, %sel1 403 ret i32 %add 404; CHECK-LABEL: @add_of_selects( 405; CHECK-NEXT: %[[sel:.*]] = select i1 %A, i32 %B, i32 0 406; CHECK-NEXT: ret i32 %[[sel]] 407} 408