llvm/test/Transforms/InstSimplify/rem.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -passes=instsimplify -S | FileCheck %s
   3
   4 define i32 @zero_dividend(i32 %A) {
   5 ; CHECK-LABEL: @zero_dividend(
   6 ; CHECK-NEXT:    ret i32 0
   7 ;
   8   %B = urem i32 0, %A
   9   ret i32 %B
  10 }
  11
  12 define <2 x i32> @zero_dividend_vector(<2 x i32> %A) {
  13 ; CHECK-LABEL: @zero_dividend_vector(
  14 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
  15 ;
  16   %B = srem <2 x i32> zeroinitializer, %A
  17   ret <2 x i32> %B
  18 }
  19
  20 define <2 x i32> @zero_dividend_vector_undef_elt(<2 x i32> %A) {
  21 ; CHECK-LABEL: @zero_dividend_vector_undef_elt(
  22 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
  23 ;
  24   %B = urem <2 x i32> <i32 undef, i32 0>, %A
  25   ret <2 x i32> %B
  26 }
  27
  28 ; Division-by-zero is poison. UB in any vector lane means the whole op is poison.
  29
  30 define <2 x i8> @srem_zero_elt_vec_constfold(<2 x i8> %x) {
  31 ; CHECK-LABEL: @srem_zero_elt_vec_constfold(
  32 ; CHECK-NEXT:    ret <2 x i8> poison
  33 ;
  34   %rem = srem <2 x i8> <i8 1, i8 2>, <i8 0, i8 -42>
  35   ret <2 x i8> %rem
  36 }
  37
  38 define <2 x i8> @urem_zero_elt_vec_constfold(<2 x i8> %x) {
  39 ; CHECK-LABEL: @urem_zero_elt_vec_constfold(
  40 ; CHECK-NEXT:    ret <2 x i8> poison
  41 ;
  42   %rem = urem <2 x i8> <i8 1, i8 2>, <i8 42, i8 0>
  43   ret <2 x i8> %rem
  44 }
  45
  46 define <2 x i8> @srem_zero_elt_vec(<2 x i8> %x) {
  47 ; CHECK-LABEL: @srem_zero_elt_vec(
  48 ; CHECK-NEXT:    ret <2 x i8> poison
  49 ;
  50   %rem = srem <2 x i8> %x, <i8 -42, i8 0>
  51   ret <2 x i8> %rem
  52 }
  53
  54 define <2 x i8> @urem_zero_elt_vec(<2 x i8> %x) {
  55 ; CHECK-LABEL: @urem_zero_elt_vec(
  56 ; CHECK-NEXT:    ret <2 x i8> poison
  57 ;
  58   %rem = urem <2 x i8> %x, <i8 0, i8 42>
  59   ret <2 x i8> %rem
  60 }
  61
  62 define <2 x i8> @srem_undef_elt_vec(<2 x i8> %x) {
  63 ; CHECK-LABEL: @srem_undef_elt_vec(
  64 ; CHECK-NEXT:    ret <2 x i8> poison
  65 ;
  66   %rem = srem <2 x i8> %x, <i8 -42, i8 undef>
  67   ret <2 x i8> %rem
  68 }
  69
  70 define <2 x i8> @urem_undef_elt_vec(<2 x i8> %x) {
  71 ; CHECK-LABEL: @urem_undef_elt_vec(
  72 ; CHECK-NEXT:    ret <2 x i8> poison
  73 ;
  74   %rem = urem <2 x i8> %x, <i8 undef, i8 42>
  75   ret <2 x i8> %rem
  76 }
  77
  78 ; Division-by-zero is undef. UB in any vector lane means the whole op is undef.
  79 ; Thus, we can simplify this: if any element of 'y' is 0, we can do anything.
  80 ; Therefore, assume that all elements of 'y' must be 1.
  81
  82 define <2 x i1> @srem_bool_vec(<2 x i1> %x, <2 x i1> %y) {
  83 ; CHECK-LABEL: @srem_bool_vec(
  84 ; CHECK-NEXT:    ret <2 x i1> zeroinitializer
  85 ;
  86   %rem = srem <2 x i1> %x, %y
  87   ret <2 x i1> %rem
  88 }
  89
  90 define <2 x i1> @urem_bool_vec(<2 x i1> %x, <2 x i1> %y) {
  91 ; CHECK-LABEL: @urem_bool_vec(
  92 ; CHECK-NEXT:    ret <2 x i1> zeroinitializer
  93 ;
  94   %rem = urem <2 x i1> %x, %y
  95   ret <2 x i1> %rem
  96 }
  97
  98 define <2 x i32> @zext_bool_urem_divisor_vec(<2 x i1> %x, <2 x i32> %y) {
  99 ; CHECK-LABEL: @zext_bool_urem_divisor_vec(
 100 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 101 ;
 102   %ext = zext <2 x i1> %x to <2 x i32>
 103   %r = urem <2 x i32> %y, %ext
 104   ret <2 x i32> %r
 105 }
 106
 107 define i32 @zext_bool_srem_divisor(i1 %x, i32 %y) {
 108 ; CHECK-LABEL: @zext_bool_srem_divisor(
 109 ; CHECK-NEXT:    ret i32 0
 110 ;
 111   %ext = zext i1 %x to i32
 112   %r = srem i32 %y, %ext
 113   ret i32 %r
 114 }
 115
 116 define i32 @select1(i32 %x, i1 %b) {
 117 ; CHECK-LABEL: @select1(
 118 ; CHECK-NEXT:    ret i32 0
 119 ;
 120   %rhs = select i1 %b, i32 %x, i32 1
 121   %rem = srem i32 %x, %rhs
 122   ret i32 %rem
 123 }
 124
 125 define i32 @select2(i32 %x, i1 %b) {
 126 ; CHECK-LABEL: @select2(
 127 ; CHECK-NEXT:    ret i32 0
 128 ;
 129   %rhs = select i1 %b, i32 %x, i32 1
 130   %rem = urem i32 %x, %rhs
 131   ret i32 %rem
 132 }
 133
 134 define i32 @rem1(i32 %x, i32 %n) {
 135 ; CHECK-LABEL: @rem1(
 136 ; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[X:%.*]], [[N:%.*]]
 137 ; CHECK-NEXT:    ret i32 [[MOD]]
 138 ;
 139   %mod = srem i32 %x, %n
 140   %mod1 = srem i32 %mod, %n
 141   ret i32 %mod1
 142 }
 143
 144 define i32 @rem2(i32 %x, i32 %n) {
 145 ; CHECK-LABEL: @rem2(
 146 ; CHECK-NEXT:    [[MOD:%.*]] = urem i32 [[X:%.*]], [[N:%.*]]
 147 ; CHECK-NEXT:    ret i32 [[MOD]]
 148 ;
 149   %mod = urem i32 %x, %n
 150   %mod1 = urem i32 %mod, %n
 151   ret i32 %mod1
 152 }
 153
 154 define i32 @rem3(i32 %x, i32 %n) {
 155 ; CHECK-LABEL: @rem3(
 156 ; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[X:%.*]], [[N:%.*]]
 157 ; CHECK-NEXT:    [[MOD1:%.*]] = urem i32 [[MOD]], [[N]]
 158 ; CHECK-NEXT:    ret i32 [[MOD1]]
 159 ;
 160   %mod = srem i32 %x, %n
 161   %mod1 = urem i32 %mod, %n
 162   ret i32 %mod1
 163 }
 164
 165 define i32 @urem_dividend_known_smaller_than_constant_divisor(i32 %x) {
 166 ; CHECK-LABEL: @urem_dividend_known_smaller_than_constant_divisor(
 167 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 250
 168 ; CHECK-NEXT:    ret i32 [[AND]]
 169 ;
 170   %and = and i32 %x, 250
 171   %r = urem i32 %and, 251
 172   ret i32 %r
 173 }
 174
 175 define i32 @not_urem_dividend_known_smaller_than_constant_divisor(i32 %x) {
 176 ; CHECK-LABEL: @not_urem_dividend_known_smaller_than_constant_divisor(
 177 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 251
 178 ; CHECK-NEXT:    [[R:%.*]] = urem i32 [[AND]], 251
 179 ; CHECK-NEXT:    ret i32 [[R]]
 180 ;
 181   %and = and i32 %x, 251
 182   %r = urem i32 %and, 251
 183   ret i32 %r
 184 }
 185
 186 define i8 @urem_dividend_known_smaller_than_constant_divisor2(i1 %b) {
 187 ; CHECK-LABEL: @urem_dividend_known_smaller_than_constant_divisor2(
 188 ; CHECK-NEXT:    [[T0:%.*]] = zext i1 [[B:%.*]] to i8
 189 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[T0]], 12
 190 ; CHECK-NEXT:    ret i8 [[XOR]]
 191 ;
 192   %t0 = zext i1 %b to i8
 193   %xor = xor i8 %t0, 12
 194   %r = urem i8 %xor, 14
 195   ret i8 %r
 196 }
 197
 198 ; negative test - dividend can equal 13
 199
 200 define i8 @not_urem_dividend_known_smaller_than_constant_divisor2(i1 %b) {
 201 ; CHECK-LABEL: @not_urem_dividend_known_smaller_than_constant_divisor2(
 202 ; CHECK-NEXT:    [[T0:%.*]] = zext i1 [[B:%.*]] to i8
 203 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[T0]], 12
 204 ; CHECK-NEXT:    [[R:%.*]] = urem i8 [[XOR]], 13
 205 ; CHECK-NEXT:    ret i8 [[R]]
 206 ;
 207   %t0 = zext i1 %b to i8
 208   %xor = xor i8 %t0, 12
 209   %r = urem i8 %xor, 13
 210   ret i8 %r
 211 }
 212
 213 define i32 @urem_constant_dividend_known_smaller_than_divisor(i32 %x) {
 214 ; CHECK-LABEL: @urem_constant_dividend_known_smaller_than_divisor(
 215 ; CHECK-NEXT:    ret i32 250
 216 ;
 217   %or = or i32 %x, 251
 218   %r = urem i32 250, %or
 219   ret i32 %r
 220 }
 221
 222 define i32 @not_urem_constant_dividend_known_smaller_than_divisor(i32 %x) {
 223 ; CHECK-LABEL: @not_urem_constant_dividend_known_smaller_than_divisor(
 224 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], 251
 225 ; CHECK-NEXT:    [[R:%.*]] = urem i32 251, [[OR]]
 226 ; CHECK-NEXT:    ret i32 [[R]]
 227 ;
 228   %or = or i32 %x, 251
 229   %r = urem i32 251, %or
 230   ret i32 %r
 231 }
 232
 233 ; This would require computing known bits on both x and y. Is it worth doing?
 234
 235 define i32 @urem_dividend_known_smaller_than_divisor(i32 %x, i32 %y) {
 236 ; CHECK-LABEL: @urem_dividend_known_smaller_than_divisor(
 237 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 250
 238 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], 251
 239 ; CHECK-NEXT:    [[R:%.*]] = urem i32 [[AND]], [[OR]]
 240 ; CHECK-NEXT:    ret i32 [[R]]
 241 ;
 242   %and = and i32 %x, 250
 243   %or = or i32 %y, 251
 244   %r = urem i32 %and, %or
 245   ret i32 %r
 246 }
 247
 248 define i32 @not_urem_dividend_known_smaller_than_divisor(i32 %x, i32 %y) {
 249 ; CHECK-LABEL: @not_urem_dividend_known_smaller_than_divisor(
 250 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 251
 251 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], 251
 252 ; CHECK-NEXT:    [[R:%.*]] = urem i32 [[AND]], [[OR]]
 253 ; CHECK-NEXT:    ret i32 [[R]]
 254 ;
 255   %and = and i32 %x, 251
 256   %or = or i32 %y, 251
 257   %r = urem i32 %and, %or
 258   ret i32 %r
 259 }
 260
 261 declare i32 @external()
 262
 263 define i32 @rem4() {
 264 ; CHECK-LABEL: @rem4(
 265 ; CHECK-NEXT:    [[CALL:%.*]] = call i32 @external(), !range [[RNG0:![0-9]+]]
 266 ; CHECK-NEXT:    ret i32 [[CALL]]
 267 ;
 268   %call = call i32 @external(), !range !0
 269   %urem = urem i32 %call, 3
 270   ret i32 %urem
 271 }
 272
 273 !0 = !{i32 0, i32 3}
 274
 275 define i32 @rem5(i32 %x, i32 %y) {
 276 ; CHECK-LABEL: @rem5(
 277 ; CHECK-NEXT:    ret i32 0
 278 ;
 279   %shl = shl nsw i32 %x, %y
 280   %mod = srem i32 %shl, %x
 281   ret i32 %mod
 282 }
 283
 284 define <2 x i32> @rem6(<2 x i32> %x, <2 x i32> %y) {
 285 ; CHECK-LABEL: @rem6(
 286 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 287 ;
 288   %shl = shl nsw <2 x i32> %x, %y
 289   %mod = srem <2 x i32> %shl, %x
 290   ret <2 x i32> %mod
 291 }
 292
 293 ; make sure the previous fold doesn't take place for wrapped shifts
 294
 295 define i32 @rem7(i32 %x, i32 %y) {
 296 ; CHECK-LABEL: @rem7(
 297 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
 298 ; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[SHL]], [[X]]
 299 ; CHECK-NEXT:    ret i32 [[MOD]]
 300 ;
 301   %shl = shl i32 %x, %y
 302   %mod = srem i32 %shl, %x
 303   ret i32 %mod
 304 }
 305
 306 define i32 @rem8(i32 %x, i32 %y) {
 307 ; CHECK-LABEL: @rem8(
 308 ; CHECK-NEXT:    ret i32 0
 309 ;
 310   %shl = shl nuw i32 %x, %y
 311   %mod = urem i32 %shl, %x
 312   ret i32 %mod
 313 }
 314
 315 define <2 x i32> @rem9(<2 x i32> %x, <2 x i32> %y) {
 316 ; CHECK-LABEL: @rem9(
 317 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 318 ;
 319   %shl = shl nuw <2 x i32> %x, %y
 320   %mod = urem <2 x i32> %shl, %x
 321   ret <2 x i32> %mod
 322 }
 323
 324 ; make sure the previous fold doesn't take place for wrapped shifts
 325
 326 define i32 @rem10(i32 %x, i32 %y) {
 327 ; CHECK-LABEL: @rem10(
 328 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
 329 ; CHECK-NEXT:    [[MOD:%.*]] = urem i32 [[SHL]], [[X]]
 330 ; CHECK-NEXT:    ret i32 [[MOD]]
 331 ;
 332   %shl = shl i32 %x, %y
 333   %mod = urem i32 %shl, %x
 334   ret i32 %mod
 335 }
 336
 337 define i32 @srem_with_sext_bool_divisor(i1 %x, i32 %y) {
 338 ; CHECK-LABEL: @srem_with_sext_bool_divisor(
 339 ; CHECK-NEXT:    ret i32 0
 340 ;
 341   %s = sext i1 %x to i32
 342   %r = srem i32 %y, %s
 343   ret i32 %r
 344 }
 345
 346 define <2 x i32> @srem_with_sext_bool_divisor_vec(<2 x i1> %x, <2 x i32> %y) {
 347 ; CHECK-LABEL: @srem_with_sext_bool_divisor_vec(
 348 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 349 ;
 350   %s = sext <2 x i1> %x to <2 x i32>
 351   %r = srem <2 x i32> %y, %s
 352   ret <2 x i32> %r
 353 }
 354
 355 define i8 @srem_minusone_divisor() {
 356 ; CHECK-LABEL: @srem_minusone_divisor(
 357 ; CHECK-NEXT:    ret i8 poison
 358 ;
 359   %v = srem i8 -128, -1
 360   ret i8 %v
 361 }
 362
 363 define i32 @srem_of_mul_nsw(i32 %x, i32 %y) {
 364 ; CHECK-LABEL: @srem_of_mul_nsw(
 365 ; CHECK-NEXT:    ret i32 0
 366 ;
 367   %mul = mul nsw i32 %x, %y
 368   %mod = srem i32 %mul, %y
 369   ret i32 %mod
 370 }
 371
 372 ; Verify that the optimization kicks in for:
 373 ;   - Y * X % Y as well as X * Y % Y
 374 ;   - vector types
 375 define <2 x i32> @srem_of_mul_nsw_vec_commuted(<2 x i32> %x, <2 x i32> %y) {
 376 ; CHECK-LABEL: @srem_of_mul_nsw_vec_commuted(
 377 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 378 ;
 379   %mul = mul nsw <2 x i32> %y, %x
 380   %mod = srem <2 x i32> %mul, %y
 381   ret <2 x i32> %mod
 382 }
 383
 384 define i32 @srem_of_mul_nuw(i32 %x, i32 %y) {
 385 ; CHECK-LABEL: @srem_of_mul_nuw(
 386 ; CHECK-NEXT:    [[MUL:%.*]] = mul nuw i32 [[X:%.*]], [[Y:%.*]]
 387 ; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[MUL]], [[Y]]
 388 ; CHECK-NEXT:    ret i32 [[MOD]]
 389 ;
 390   %mul = mul nuw i32 %x, %y
 391   %mod = srem i32 %mul, %y
 392   ret i32 %mod
 393 }
 394
 395 define i32 @srem_of_mul(i32 %x, i32 %y) {
 396 ; CHECK-LABEL: @srem_of_mul(
 397 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
 398 ; CHECK-NEXT:    [[MOD:%.*]] = srem i32 [[MUL]], [[Y]]
 399 ; CHECK-NEXT:    ret i32 [[MOD]]
 400 ;
 401   %mul = mul i32 %x, %y
 402   %mod = srem i32 %mul, %y
 403   ret i32 %mod
 404 }
 405
 406 define i32 @urem_of_mul_nsw(i32 %x, i32 %y) {
 407 ; CHECK-LABEL: @urem_of_mul_nsw(
 408 ; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i32 [[X:%.*]], [[Y:%.*]]
 409 ; CHECK-NEXT:    [[MOD:%.*]] = urem i32 [[MUL]], [[Y]]
 410 ; CHECK-NEXT:    ret i32 [[MOD]]
 411 ;
 412   %mul = mul nsw i32 %x, %y
 413   %mod = urem i32 %mul, %y
 414   ret i32 %mod
 415 }
 416
 417 define i32 @urem_of_mul_nuw(i32 %x, i32 %y) {
 418 ; CHECK-LABEL: @urem_of_mul_nuw(
 419 ; CHECK-NEXT:    ret i32 0
 420 ;
 421   %mul = mul nuw i32 %x, %y
 422   %mod = urem i32 %mul, %y
 423   ret i32 %mod
 424 }
 425
 426 define <2 x i32> @srem_of_mul_nuw_vec_commuted(<2 x i32> %x, <2 x i32> %y) {
 427 ; CHECK-LABEL: @srem_of_mul_nuw_vec_commuted(
 428 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 429 ;
 430   %mul = mul nuw <2 x i32> %y, %x
 431   %mod = urem <2 x i32> %mul, %y
 432   ret <2 x i32> %mod
 433 }
 434
 435 define i32 @urem_of_mul(i32 %x, i32 %y) {
 436 ; CHECK-LABEL: @urem_of_mul(
 437 ; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
 438 ; CHECK-NEXT:    [[MOD:%.*]] = urem i32 [[MUL]], [[Y]]
 439 ; CHECK-NEXT:    ret i32 [[MOD]]
 440 ;
 441   %mul = mul i32 %x, %y
 442   %mod = urem i32 %mul, %y
 443   ret i32 %mod
 444 }
 445
 446 define i4 @srem_mul_sdiv(i4 %x, i4 %y) {
 447 ; CHECK-LABEL: @srem_mul_sdiv(
 448 ; CHECK-NEXT:    ret i4 0
 449 ;
 450   %d = sdiv i4 %x, %y
 451   %mul = mul i4 %d, %y
 452   %mod = srem i4 %mul, %y
 453   ret i4 %mod
 454 }
 455
 456 define i8 @srem_mul_udiv(i8 %x, i8 %y) {
 457 ; CHECK-LABEL: @srem_mul_udiv(
 458 ; CHECK-NEXT:    [[D:%.*]] = udiv i8 [[X:%.*]], [[Y:%.*]]
 459 ; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[D]], [[Y]]
 460 ; CHECK-NEXT:    [[MOD:%.*]] = srem i8 [[MUL]], [[Y]]
 461 ; CHECK-NEXT:    ret i8 [[MOD]]
 462 ;
 463   %d = udiv i8 %x, %y
 464   %mul = mul i8 %d, %y
 465   %mod = srem i8 %mul, %y
 466   ret i8 %mod
 467 }
 468
 469 define <3 x i7> @urem_mul_udiv_vec_commuted(<3 x i7> %x, <3 x i7> %y) {
 470 ; CHECK-LABEL: @urem_mul_udiv_vec_commuted(
 471 ; CHECK-NEXT:    ret <3 x i7> zeroinitializer
 472 ;
 473   %d = udiv <3 x i7> %x, %y
 474   %mul = mul <3 x i7> %y, %d
 475   %mod = urem <3 x i7> %mul, %y
 476   ret <3 x i7> %mod
 477 }
 478
 479 define i8 @urem_mul_sdiv(i8 %x, i8 %y) {
 480 ; CHECK-LABEL: @urem_mul_sdiv(
 481 ; CHECK-NEXT:    [[D:%.*]] = sdiv i8 [[X:%.*]], [[Y:%.*]]
 482 ; CHECK-NEXT:    [[MUL:%.*]] = mul i8 [[Y]], [[D]]
 483 ; CHECK-NEXT:    [[MOD:%.*]] = urem i8 [[MUL]], [[Y]]
 484 ; CHECK-NEXT:    ret i8 [[MOD]]
 485 ;
 486   %d = sdiv i8 %x, %y
 487   %mul = mul i8 %y, %d
 488   %mod = urem i8 %mul, %y
 489   ret i8 %mod
 490 }