llvm/test/Transforms/DivRemPairs/X86/div-expanded-rem-pair.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -div-rem-pairs -S -mtriple=x86_64-unknown-unknown    | FileCheck %s
   3
   4 declare void @foo(i32, i32)
   5
   6 define void @decompose_illegal_srem_same_block(i32 %a, i32 %b) {
   7 ; CHECK-LABEL: @decompose_illegal_srem_same_block(
   8 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
   9 ; CHECK-NEXT:    [[T0:%.*]] = mul i32 [[DIV]], [[B]]
  10 ; CHECK-NEXT:    [[REM_RECOMPOSED:%.*]] = srem i32 [[A]], [[B]]
  11 ; CHECK-NEXT:    call void @foo(i32 [[REM_RECOMPOSED]], i32 [[DIV]])
  12 ; CHECK-NEXT:    ret void
  13 ;
  14   %div = sdiv i32 %a, %b
  15   %t0 = mul i32 %div, %b
  16   %rem = sub i32 %a, %t0
  17   call void @foo(i32 %rem, i32 %div)
  18   ret void
  19 }
  20
  21 define void @decompose_illegal_urem_same_block(i32 %a, i32 %b) {
  22 ; CHECK-LABEL: @decompose_illegal_urem_same_block(
  23 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[A:%.*]], [[B:%.*]]
  24 ; CHECK-NEXT:    [[T0:%.*]] = mul i32 [[DIV]], [[B]]
  25 ; CHECK-NEXT:    [[REM_RECOMPOSED:%.*]] = urem i32 [[A]], [[B]]
  26 ; CHECK-NEXT:    call void @foo(i32 [[REM_RECOMPOSED]], i32 [[DIV]])
  27 ; CHECK-NEXT:    ret void
  28 ;
  29   %div = udiv i32 %a, %b
  30   %t0 = mul i32 %div, %b
  31   %rem = sub i32 %a, %t0
  32   call void @foo(i32 %rem, i32 %div)
  33   ret void
  34 }
  35
  36 ; Recompose and hoist the srem if it's safe and free, otherwise keep as-is..
  37
  38 define i16 @hoist_srem(i16 %a, i16 %b) {
  39 ; CHECK-LABEL: @hoist_srem(
  40 ; CHECK-NEXT:  entry:
  41 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i16 [[A:%.*]], [[B:%.*]]
  42 ; CHECK-NEXT:    [[REM_RECOMPOSED:%.*]] = srem i16 [[A]], [[B]]
  43 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[DIV]], 42
  44 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
  45 ; CHECK:       if:
  46 ; CHECK-NEXT:    [[T0:%.*]] = mul i16 [[DIV]], [[B]]
  47 ; CHECK-NEXT:    br label [[END]]
  48 ; CHECK:       end:
  49 ; CHECK-NEXT:    [[RET:%.*]] = phi i16 [ [[REM_RECOMPOSED]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
  50 ; CHECK-NEXT:    ret i16 [[RET]]
  51 ;
  52 entry:
  53   %div = sdiv i16 %a, %b
  54   %cmp = icmp eq i16 %div, 42
  55   br i1 %cmp, label %if, label %end
  56
  57 if:
  58   %t0 = mul i16 %div, %b
  59   %rem = sub i16 %a, %t0
  60   br label %end
  61
  62 end:
  63   %ret = phi i16 [ %rem, %if ], [ 3, %entry ]
  64   ret i16 %ret
  65 }
  66
  67 ; Recompose and hoist the urem if it's safe and free, otherwise keep as-is..
  68
  69 define i8 @hoist_urem(i8 %a, i8 %b) {
  70 ; CHECK-LABEL: @hoist_urem(
  71 ; CHECK-NEXT:  entry:
  72 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i8 [[A:%.*]], [[B:%.*]]
  73 ; CHECK-NEXT:    [[REM_RECOMPOSED:%.*]] = urem i8 [[A]], [[B]]
  74 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[DIV]], 42
  75 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
  76 ; CHECK:       if:
  77 ; CHECK-NEXT:    [[T0:%.*]] = mul i8 [[DIV]], [[B]]
  78 ; CHECK-NEXT:    br label [[END]]
  79 ; CHECK:       end:
  80 ; CHECK-NEXT:    [[RET:%.*]] = phi i8 [ [[REM_RECOMPOSED]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
  81 ; CHECK-NEXT:    ret i8 [[RET]]
  82 ;
  83 entry:
  84   %div = udiv i8 %a, %b
  85   %cmp = icmp eq i8 %div, 42
  86   br i1 %cmp, label %if, label %end
  87
  88 if:
  89   %t0 = mul i8 %div, %b
  90   %rem = sub i8 %a, %t0
  91   br label %end
  92
  93 end:
  94   %ret = phi i8 [ %rem, %if ], [ 3, %entry ]
  95   ret i8 %ret
  96 }
  97
  98 ; Be careful with RAUW/invalidation if this is a srem-of-srem.
  99
 100 define i32 @srem_of_srem_unexpanded(i32 %X, i32 %Y, i32 %Z) {
 101 ; CHECK-LABEL: @srem_of_srem_unexpanded(
 102 ; CHECK-NEXT:    [[T0:%.*]] = mul nsw i32 [[Z:%.*]], [[Y:%.*]]
 103 ; CHECK-NEXT:    [[T1:%.*]] = sdiv i32 [[X:%.*]], [[T0]]
 104 ; CHECK-NEXT:    [[T2:%.*]] = mul nsw i32 [[T0]], [[T1]]
 105 ; CHECK-NEXT:    [[T3:%.*]] = srem i32 [[X]], [[T0]]
 106 ; CHECK-NEXT:    [[T4:%.*]] = sdiv i32 [[T3]], [[Y]]
 107 ; CHECK-NEXT:    [[T5:%.*]] = mul nsw i32 [[T4]], [[Y]]
 108 ; CHECK-NEXT:    [[T6:%.*]] = srem i32 [[T3]], [[Y]]
 109 ; CHECK-NEXT:    ret i32 [[T6]]
 110 ;
 111   %t0 = mul nsw i32 %Z, %Y
 112   %t1 = sdiv i32 %X, %t0
 113   %t2 = mul nsw i32 %t0, %t1
 114   %t3 = srem i32 %X, %t0
 115   %t4 = sdiv i32 %t3, %Y
 116   %t5 = mul nsw i32 %t4, %Y
 117   %t6 = srem i32 %t3, %Y
 118   ret i32 %t6
 119 }
 120 define i32 @srem_of_srem_expanded(i32 %X, i32 %Y, i32 %Z) {
 121 ; CHECK-LABEL: @srem_of_srem_expanded(
 122 ; CHECK-NEXT:    [[T0:%.*]] = mul nsw i32 [[Z:%.*]], [[Y:%.*]]
 123 ; CHECK-NEXT:    [[T1:%.*]] = sdiv i32 [[X:%.*]], [[T0]]
 124 ; CHECK-NEXT:    [[T2:%.*]] = mul nsw i32 [[T0]], [[T1]]
 125 ; CHECK-NEXT:    [[T3_RECOMPOSED:%.*]] = srem i32 [[X]], [[T0]]
 126 ; CHECK-NEXT:    [[T4:%.*]] = sdiv i32 [[T3_RECOMPOSED]], [[Y]]
 127 ; CHECK-NEXT:    [[T5:%.*]] = mul nsw i32 [[T4]], [[Y]]
 128 ; CHECK-NEXT:    [[T6_RECOMPOSED:%.*]] = srem i32 [[T3_RECOMPOSED]], [[Y]]
 129 ; CHECK-NEXT:    ret i32 [[T6_RECOMPOSED]]
 130 ;
 131   %t0 = mul nsw i32 %Z, %Y
 132   %t1 = sdiv i32 %X, %t0
 133   %t2 = mul nsw i32 %t0, %t1
 134   %t3 = sub nsw i32 %X, %t2
 135   %t4 = sdiv i32 %t3, %Y
 136   %t5 = mul nsw i32 %t4, %Y
 137   %t6 = sub nsw i32 %t3, %t5
 138   ret i32 %t6
 139 }
 140
 141 ; If the target doesn't have a unified div/rem op for the type, keep decomposed rem
 142
 143 define i128 @dont_hoist_urem(i128 %a, i128 %b) {
 144 ; CHECK-LABEL: @dont_hoist_urem(
 145 ; CHECK-NEXT:  entry:
 146 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i128 [[A:%.*]], [[B:%.*]]
 147 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i128 [[DIV]], 42
 148 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
 149 ; CHECK:       if:
 150 ; CHECK-NEXT:    [[T0:%.*]] = mul i128 [[DIV]], [[B]]
 151 ; CHECK-NEXT:    [[REM:%.*]] = sub i128 [[A]], [[T0]]
 152 ; CHECK-NEXT:    br label [[END]]
 153 ; CHECK:       end:
 154 ; CHECK-NEXT:    [[RET:%.*]] = phi i128 [ [[REM]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
 155 ; CHECK-NEXT:    ret i128 [[RET]]
 156 ;
 157 entry:
 158   %div = udiv i128 %a, %b
 159   %cmp = icmp eq i128 %div, 42
 160   br i1 %cmp, label %if, label %end
 161
 162 if:
 163   %t0 = mul i128 %div, %b
 164   %rem = sub i128 %a, %t0
 165   br label %end
 166
 167 end:
 168   %ret = phi i128 [ %rem, %if ], [ 3, %entry ]
 169   ret i128 %ret
 170 }
 171
 172 ; Even in expanded form, we can end up with div and rem in different basic
 173 ; blocks neither of which dominates each another.
 174 define i32 @can_have_divrem_in_mutually_nondominating_bbs(i1 %cmp, i32 %a, i32 %b) {
 175 ; CHECK-LABEL: @can_have_divrem_in_mutually_nondominating_bbs(
 176 ; CHECK-NEXT:  entry:
 177 ; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 178 ; CHECK:       if.then:
 179 ; CHECK-NEXT:    [[T0:%.*]] = udiv i32 [[A:%.*]], [[B:%.*]]
 180 ; CHECK-NEXT:    [[T1:%.*]] = mul nuw i32 [[T0]], [[B]]
 181 ; CHECK-NEXT:    [[T2_RECOMPOSED:%.*]] = urem i32 [[A]], [[B]]
 182 ; CHECK-NEXT:    br label [[END:%.*]]
 183 ; CHECK:       if.else:
 184 ; CHECK-NEXT:    [[T3:%.*]] = udiv i32 [[A]], [[B]]
 185 ; CHECK-NEXT:    br label [[END]]
 186 ; CHECK:       end:
 187 ; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[T2_RECOMPOSED]], [[IF_THEN]] ], [ [[T3]], [[IF_ELSE]] ]
 188 ; CHECK-NEXT:    ret i32 [[RET]]
 189 ;
 190 entry:
 191   br i1 %cmp, label %if.then, label %if.else
 192
 193 if.then:
 194   %t0 = udiv i32 %a, %b
 195   %t1 = mul nuw i32 %t0, %b
 196   %t2 = sub i32 %a, %t1
 197   br label %end
 198
 199 if.else:
 200   %t3 = udiv i32 %a, %b
 201   br label %end
 202
 203 end:
 204   %ret = phi i32 [ %t2, %if.then ], [ %t3, %if.else ]
 205   ret i32 %ret
 206 }
 207
 208 ; Test for hoisting a udiv to dominate a urem to allow udivrem.
 209 define i64 @remainder_triangle_i64(i64 %a, i64 %b, i64* %rp) {
 210 ; CHECK-LABEL: @remainder_triangle_i64(
 211 ; CHECK-NEXT:  entry:
 212 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64* [[RP:%.*]], null
 213 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i64 [[A:%.*]], [[B:%.*]]
 214 ; CHECK-NEXT:    [[REM:%.*]] = urem i64 [[A]], [[B]]
 215 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[END:%.*]]
 216 ; CHECK:       if.then:
 217 ; CHECK-NEXT:    store i64 [[REM]], i64* [[RP]], align 4
 218 ; CHECK-NEXT:    br label [[END]]
 219 ; CHECK:       end:
 220 ; CHECK-NEXT:    ret i64 [[DIV]]
 221 ;
 222 entry:
 223   %cmp = icmp ne i64* %rp, null
 224   br i1 %cmp, label %if.then, label %end
 225
 226 if.then:
 227   %rem = urem i64 %a, %b
 228   store i64 %rem, i64* %rp
 229   br label %end
 230
 231 end:
 232   %div = udiv i64 %a, %b
 233   ret i64 %div
 234 }
 235
 236 ; Test for hoisting a udiv to dominate a urem to allow the urem to be expanded
 237 ; into mul+sub.
 238 define i128 @remainder_triangle_i128(i128 %a, i128 %b, i128* %rp) {
 239 ; CHECK-LABEL: @remainder_triangle_i128(
 240 ; CHECK-NEXT:  entry:
 241 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i128* [[RP:%.*]], null
 242 ; CHECK-NEXT:    [[A_FROZEN:%.*]] = freeze i128 [[A:%.*]]
 243 ; CHECK-NEXT:    [[B_FROZEN:%.*]] = freeze i128 [[B:%.*]]
 244 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i128 [[A_FROZEN]], [[B_FROZEN]]
 245 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[END:%.*]]
 246 ; CHECK:       if.then:
 247 ; CHECK-NEXT:    [[TMP0:%.*]] = mul i128 [[DIV]], [[B_FROZEN]]
 248 ; CHECK-NEXT:    [[REM_DECOMPOSED:%.*]] = sub i128 [[A_FROZEN]], [[TMP0]]
 249 ; CHECK-NEXT:    store i128 [[REM_DECOMPOSED]], i128* [[RP]], align 4
 250 ; CHECK-NEXT:    br label [[END]]
 251 ; CHECK:       end:
 252 ; CHECK-NEXT:    ret i128 [[DIV]]
 253 ;
 254 entry:
 255   %cmp = icmp ne i128* %rp, null
 256   br i1 %cmp, label %if.then, label %end
 257
 258 if.then:
 259   %rem = urem i128 %a, %b
 260   store i128 %rem, i128* %rp
 261   br label %end
 262
 263 end:
 264   %div = udiv i128 %a, %b
 265   ret i128 %div
 266 }
 267
 268 define i64 @remainder_triangle_i64_multiple_rem_edges(i64 %a, i64 %b, i64 %c, i64* %rp) {
 269 ; CHECK-LABEL: @remainder_triangle_i64_multiple_rem_edges(
 270 ; CHECK-NEXT:  entry:
 271 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i64 [[A:%.*]], [[B:%.*]]
 272 ; CHECK-NEXT:    [[REM:%.*]] = urem i64 [[A]], [[B]]
 273 ; CHECK-NEXT:    switch i64 [[C:%.*]], label [[SW_DEFAULT:%.*]] [
 274 ; CHECK-NEXT:    i64 0, label [[SW_BB:%.*]]
 275 ; CHECK-NEXT:    i64 2, label [[SW_BB]]
 276 ; CHECK-NEXT:    ]
 277 ; CHECK:       sw.bb:
 278 ; CHECK-NEXT:    store i64 [[REM]], i64* [[RP:%.*]], align 4
 279 ; CHECK-NEXT:    br label [[SW_DEFAULT]]
 280 ; CHECK:       sw.default:
 281 ; CHECK-NEXT:    ret i64 [[DIV]]
 282 ;
 283 entry:
 284   switch i64 %c, label %sw.default [
 285   i64 0, label %sw.bb
 286   i64 2, label %sw.bb
 287   ]
 288
 289 sw.bb:                                            ; preds = %entry, %entry
 290   %rem = urem i64 %a, %b
 291   store i64 %rem, i64* %rp
 292   br label %sw.default
 293
 294 sw.default:                                       ; preds = %entry, %sw.bb
 295   %div = udiv i64 %a, %b
 296   ret i64 %div
 297 }
 298
 299 define i64 @remainder_triangle_i64_multiple_div_edges(i64 %a, i64 %b, i64 %c, i64* %rp) {
 300 ; CHECK-LABEL: @remainder_triangle_i64_multiple_div_edges(
 301 ; CHECK-NEXT:  entry:
 302 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i64 [[A:%.*]], [[B:%.*]]
 303 ; CHECK-NEXT:    [[REM:%.*]] = urem i64 [[A]], [[B]]
 304 ; CHECK-NEXT:    switch i64 [[C:%.*]], label [[SW_DEFAULT:%.*]] [
 305 ; CHECK-NEXT:    i64 0, label [[SW_BB:%.*]]
 306 ; CHECK-NEXT:    i64 2, label [[SW_BB]]
 307 ; CHECK-NEXT:    ]
 308 ; CHECK:       sw.default:
 309 ; CHECK-NEXT:    store i64 [[REM]], i64* [[RP:%.*]], align 4
 310 ; CHECK-NEXT:    br label [[SW_BB]]
 311 ; CHECK:       sw.bb:
 312 ; CHECK-NEXT:    ret i64 [[DIV]]
 313 ;
 314 entry:
 315   switch i64 %c, label %sw.default [
 316   i64 0, label %sw.bb
 317   i64 2, label %sw.bb
 318   ]
 319
 320 sw.default:                                       ; preds = %entry, %entry
 321   %rem = urem i64 %a, %b
 322   store i64 %rem, i64* %rp
 323   br label %sw.bb
 324
 325 sw.bb:                                            ; preds = %entry, %sw.default
 326   %div = udiv i64 %a, %b
 327   ret i64 %div
 328 }
 329
 330 declare void @maythrow()
 331
 332 ; Negative test. make sure we don't transform if there are instructions before
 333 ; the rem that might throw.
 334 define i64 @remainder_triangle_i64_maythrow_rem(i64 %a, i64 %b, i64* %rp) {
 335 ; CHECK-LABEL: @remainder_triangle_i64_maythrow_rem(
 336 ; CHECK-NEXT:  entry:
 337 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64* [[RP:%.*]], null
 338 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[END:%.*]]
 339 ; CHECK:       if.then:
 340 ; CHECK-NEXT:    call void @maythrow()
 341 ; CHECK-NEXT:    [[REM:%.*]] = urem i64 [[A:%.*]], [[B:%.*]]
 342 ; CHECK-NEXT:    store i64 [[REM]], i64* [[RP]], align 4
 343 ; CHECK-NEXT:    br label [[END]]
 344 ; CHECK:       end:
 345 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i64 [[A]], [[B]]
 346 ; CHECK-NEXT:    ret i64 [[DIV]]
 347 ;
 348 entry:
 349   %cmp = icmp ne i64* %rp, null
 350   br i1 %cmp, label %if.then, label %end
 351
 352 if.then:
 353   call void @maythrow()
 354   %rem = urem i64 %a, %b
 355   store i64 %rem, i64* %rp
 356   br label %end
 357
 358 end:
 359   %div = udiv i64 %a, %b
 360   ret i64 %div
 361 }
 362
 363 ; Negative test. make sure we don't transform if there are instructions before
 364 ; the div that might throw.
 365 define i64 @remainder_triangle_i64_maythrow_div(i64 %a, i64 %b, i64* %rp) {
 366 ; CHECK-LABEL: @remainder_triangle_i64_maythrow_div(
 367 ; CHECK-NEXT:  entry:
 368 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i64* [[RP:%.*]], null
 369 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[END:%.*]]
 370 ; CHECK:       if.then:
 371 ; CHECK-NEXT:    [[REM:%.*]] = urem i64 [[A:%.*]], [[B:%.*]]
 372 ; CHECK-NEXT:    store i64 [[REM]], i64* [[RP]], align 4
 373 ; CHECK-NEXT:    br label [[END]]
 374 ; CHECK:       end:
 375 ; CHECK-NEXT:    call void @maythrow()
 376 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i64 [[A]], [[B]]
 377 ; CHECK-NEXT:    ret i64 [[DIV]]
 378 ;
 379 entry:
 380   %cmp = icmp ne i64* %rp, null
 381   br i1 %cmp, label %if.then, label %end
 382
 383 if.then:
 384   %rem = urem i64 %a, %b
 385   store i64 %rem, i64* %rp
 386   br label %end
 387
 388 end:
 389   call void @maythrow()
 390   %div = udiv i64 %a, %b
 391   ret i64 %div
 392 }
 393
 394 ; Negative test, Make sure we don't transform if there are instructions before
 395 ; the rem that might throw.
 396 define i128 @remainder_triangle_i128_maythrow_rem(i128 %a, i128 %b, i128* %rp) {
 397 ; CHECK-LABEL: @remainder_triangle_i128_maythrow_rem(
 398 ; CHECK-NEXT:  entry:
 399 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i128* [[RP:%.*]], null
 400 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[END:%.*]]
 401 ; CHECK:       if.then:
 402 ; CHECK-NEXT:    call void @maythrow()
 403 ; CHECK-NEXT:    [[REM:%.*]] = urem i128 [[A:%.*]], [[B:%.*]]
 404 ; CHECK-NEXT:    store i128 [[REM]], i128* [[RP]], align 4
 405 ; CHECK-NEXT:    br label [[END]]
 406 ; CHECK:       end:
 407 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i128 [[A]], [[B]]
 408 ; CHECK-NEXT:    ret i128 [[DIV]]
 409 ;
 410 entry:
 411   %cmp = icmp ne i128* %rp, null
 412   br i1 %cmp, label %if.then, label %end
 413
 414 if.then:
 415   call void @maythrow()
 416   %rem = urem i128 %a, %b
 417   store i128 %rem, i128* %rp
 418   br label %end
 419
 420 end:
 421   %div = udiv i128 %a, %b
 422   ret i128 %div
 423 }
 424
 425 ; Negative test. Make sure we don't transform if there are instructions before
 426 ; the div that might throw.
 427 define i128 @remainder_triangle_i128_maythrow_div(i128 %a, i128 %b, i128* %rp) {
 428 ; CHECK-LABEL: @remainder_triangle_i128_maythrow_div(
 429 ; CHECK-NEXT:  entry:
 430 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i128* [[RP:%.*]], null
 431 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[END:%.*]]
 432 ; CHECK:       if.then:
 433 ; CHECK-NEXT:    [[REM:%.*]] = urem i128 [[A:%.*]], [[B:%.*]]
 434 ; CHECK-NEXT:    store i128 [[REM]], i128* [[RP]], align 4
 435 ; CHECK-NEXT:    br label [[END]]
 436 ; CHECK:       end:
 437 ; CHECK-NEXT:    call void @maythrow()
 438 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i128 [[A]], [[B]]
 439 ; CHECK-NEXT:    ret i128 [[DIV]]
 440 ;
 441 entry:
 442   %cmp = icmp ne i128* %rp, null
 443   br i1 %cmp, label %if.then, label %end
 444
 445 if.then:
 446   %rem = urem i128 %a, %b
 447   store i128 %rem, i128* %rp
 448   br label %end
 449
 450 end:
 451   call void @maythrow()
 452   %div = udiv i128 %a, %b
 453   ret i128 %div
 454 }
 455
 456 ; Negative test. The common predecessor has another successor so we can't hoist
 457 ; the udiv to the common predecessor.
 458 define i64 @remainder_not_triangle_i32(i64 %a, i64 %b, i64 %c, i64*%rp) {
 459 ; CHECK-LABEL: @remainder_not_triangle_i32(
 460 ; CHECK-NEXT:  entry:
 461 ; CHECK-NEXT:    switch i64 [[C:%.*]], label [[RETURN:%.*]] [
 462 ; CHECK-NEXT:    i64 0, label [[SW_BB:%.*]]
 463 ; CHECK-NEXT:    i64 1, label [[SW_BB1:%.*]]
 464 ; CHECK-NEXT:    ]
 465 ; CHECK:       sw.bb:
 466 ; CHECK-NEXT:    [[REM:%.*]] = urem i64 [[A:%.*]], [[B:%.*]]
 467 ; CHECK-NEXT:    store i64 [[REM]], i64* [[RP:%.*]], align 4
 468 ; CHECK-NEXT:    br label [[SW_BB1]]
 469 ; CHECK:       sw.bb1:
 470 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i64 [[A]], [[B]]
 471 ; CHECK-NEXT:    br label [[RETURN]]
 472 ; CHECK:       return:
 473 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i64 [ [[DIV]], [[SW_BB1]] ], [ 0, [[ENTRY:%.*]] ]
 474 ; CHECK-NEXT:    ret i64 [[RETVAL_0]]
 475 ;
 476 entry:
 477   switch i64 %c, label %return [
 478   i64 0, label %sw.bb
 479   i64 1, label %sw.bb1
 480   ]
 481
 482 sw.bb:                                            ; preds = %entry
 483   %rem = urem i64 %a, %b
 484   store i64 %rem, i64* %rp
 485   br label %sw.bb1
 486
 487 sw.bb1:                                           ; preds = %entry, %sw.bb
 488   %div = udiv i64 %a, %b
 489   br label %return
 490
 491 return:                                           ; preds = %entry, %sw.bb1
 492   %retval.0 = phi i64 [ %div, %sw.bb1 ], [ 0, %entry ]
 493   ret i64 %retval.0
 494 }
 495
 496 ; Negative test. The urem block has a successor that isn't udiv.
 497 define i64 @remainder_not_triangle_i32_2(i64 %a, i64 %b, i64 %c, i64* %rp) {
 498 ; CHECK-LABEL: @remainder_not_triangle_i32_2(
 499 ; CHECK-NEXT:  entry:
 500 ; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i64* [[RP:%.*]], null
 501 ; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[IF_END3:%.*]], label [[IF_THEN:%.*]]
 502 ; CHECK:       if.then:
 503 ; CHECK-NEXT:    [[REM:%.*]] = urem i64 [[A:%.*]], [[B:%.*]]
 504 ; CHECK-NEXT:    store i64 [[REM]], i64* [[RP]], align 4
 505 ; CHECK-NEXT:    [[TOBOOL1_NOT:%.*]] = icmp eq i64 [[C:%.*]], 0
 506 ; CHECK-NEXT:    br i1 [[TOBOOL1_NOT]], label [[IF_END3]], label [[RETURN:%.*]]
 507 ; CHECK:       if.end3:
 508 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i64 [[A]], [[B]]
 509 ; CHECK-NEXT:    br label [[RETURN]]
 510 ; CHECK:       return:
 511 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i64 [ [[DIV]], [[IF_END3]] ], [ 0, [[IF_THEN]] ]
 512 ; CHECK-NEXT:    ret i64 [[RETVAL_0]]
 513 ;
 514 entry:
 515   %tobool.not = icmp eq i64* %rp, null
 516   br i1 %tobool.not, label %if.end3, label %if.then
 517
 518 if.then:                                          ; preds = %entry
 519   %rem = urem i64 %a, %b
 520   store i64 %rem, i64* %rp
 521   %tobool1.not = icmp eq i64 %c, 0
 522   br i1 %tobool1.not, label %if.end3, label %return
 523
 524 if.end3:                                          ; preds = %if.then, %entry
 525   %div = udiv i64 %a, %b
 526   br label %return
 527
 528 return:                                           ; preds = %if.then, %if.end3
 529   %retval.0 = phi i64 [ %div, %if.end3 ], [ 0, %if.then ]
 530   ret i64 %retval.0
 531 }
 532
 533 ; Negative test (this would create invalid IR and crash).
 534 ; The div block can't have predecessors other than the rem block
 535 ; and the common single pred block (it is reachable from entry here).
 536
 537 define i32 @PR51241(i1 %b1, i1 %b2, i32 %t0) {
 538 ; CHECK-LABEL: @PR51241(
 539 ; CHECK-NEXT:  entry:
 540 ; CHECK-NEXT:    br i1 [[B1:%.*]], label [[DIVBB:%.*]], label [[PREDBB:%.*]]
 541 ; CHECK:       predbb:
 542 ; CHECK-NEXT:    br i1 [[B2:%.*]], label [[DIVBB]], label [[REMBB:%.*]]
 543 ; CHECK:       rembb:
 544 ; CHECK-NEXT:    [[REM2:%.*]] = srem i32 7, [[T0:%.*]]
 545 ; CHECK-NEXT:    br label [[DIVBB]]
 546 ; CHECK:       divbb:
 547 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 7, [[T0]]
 548 ; CHECK-NEXT:    ret i32 [[DIV]]
 549 ;
 550 entry:
 551   br i1 %b1, label %divbb, label %predbb
 552
 553 predbb:
 554   br i1 %b2, label %divbb, label %rembb
 555
 556 rembb:
 557   %rem2 = srem i32 7, %t0
 558   br label %divbb
 559
 560 divbb:
 561   %div = sdiv i32 7, %t0
 562   ret i32 %div
 563 }