1 ; RUN: opt < %s -instcombine -S | FileCheck %s 2 3 define 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 14 define 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 24 define 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 36 define 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 44 define <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 52 define <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 61 define <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 71 define <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 80 define 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) 91 define 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) 106 define 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) 119 define 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) 132 define 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) 145 define 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) 158 define 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) 171 define 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) 184 define 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) 196 define 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 208 define 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 217 define 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 226 define 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 235 define 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 245 define 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 255 define 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 265 define 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 276 define 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 285 define 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 295 define 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. 311 define 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 } 325 declare 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. 330 define 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 346 define 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 356 define 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 366 define 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 376 define 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 389 define 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 399 define 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
