llvm/test/Transforms/DivRemPairs/Mips/div-rem-pairs.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -div-rem-pairs -S -mtriple=mips-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:    [[A_FROZEN:%.*]] = freeze i32 [[A:%.*]]
   9 ; CHECK-NEXT:    [[B_FROZEN:%.*]] = freeze i32 [[B:%.*]]
  10 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A_FROZEN]], [[B_FROZEN]]
  11 ; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[DIV]], [[B_FROZEN]]
  12 ; CHECK-NEXT:    [[REM_DECOMPOSED:%.*]] = sub i32 [[A_FROZEN]], [[TMP1]]
  13 ; CHECK-NEXT:    call void @foo(i32 [[REM_DECOMPOSED]], i32 [[DIV]])
  14 ; CHECK-NEXT:    ret void
  15 ;
  16   %rem = srem i32 %a, %b
  17   %div = sdiv i32 %a, %b
  18   call void @foo(i32 %rem, i32 %div)
  19   ret void
  20 }
  21
  22 define void @decompose_illegal_urem_same_block(i32 %a, i32 %b) {
  23 ; CHECK-LABEL: @decompose_illegal_urem_same_block(
  24 ; CHECK-NEXT:    [[A_FROZEN:%.*]] = freeze i32 [[A:%.*]]
  25 ; CHECK-NEXT:    [[B_FROZEN:%.*]] = freeze i32 [[B:%.*]]
  26 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[A_FROZEN]], [[B_FROZEN]]
  27 ; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[DIV]], [[B_FROZEN]]
  28 ; CHECK-NEXT:    [[REM_DECOMPOSED:%.*]] = sub i32 [[A_FROZEN]], [[TMP1]]
  29 ; CHECK-NEXT:    call void @foo(i32 [[REM_DECOMPOSED]], i32 [[DIV]])
  30 ; CHECK-NEXT:    ret void
  31 ;
  32   %div = udiv i32 %a, %b
  33   %rem = urem i32 %a, %b
  34   call void @foo(i32 %rem, i32 %div)
  35   ret void
  36 }
  37
  38 ; Hoist and optionally decompose the sdiv because it's safe and free.
  39 ; PR31028 - https://bugs.llvm.org/show_bug.cgi?id=31028
  40
  41 define i32 @hoist_sdiv(i32 %a, i32 %b) {
  42 ; CHECK-LABEL: @hoist_sdiv(
  43 ; CHECK-NEXT:  entry:
  44 ; CHECK-NEXT:    [[A_FROZEN:%.*]] = freeze i32 [[A:%.*]]
  45 ; CHECK-NEXT:    [[B_FROZEN:%.*]] = freeze i32 [[B:%.*]]
  46 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A_FROZEN]], [[B_FROZEN]]
  47 ; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[DIV]], [[B_FROZEN]]
  48 ; CHECK-NEXT:    [[REM_DECOMPOSED:%.*]] = sub i32 [[A_FROZEN]], [[TMP0]]
  49 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM_DECOMPOSED]], 42
  50 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
  51 ; CHECK:       if:
  52 ; CHECK-NEXT:    br label [[END]]
  53 ; CHECK:       end:
  54 ; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[DIV]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
  55 ; CHECK-NEXT:    ret i32 [[RET]]
  56 ;
  57 entry:
  58   %rem = srem i32 %a, %b
  59   %cmp = icmp eq i32 %rem, 42
  60   br i1 %cmp, label %if, label %end
  61
  62 if:
  63   %div = sdiv i32 %a, %b
  64   br label %end
  65
  66 end:
  67   %ret = phi i32 [ %div, %if ], [ 3, %entry ]
  68   ret i32 %ret
  69 }
  70
  71 ; Hoist and optionally decompose the udiv because it's safe and free.
  72
  73 define i64 @hoist_udiv(i64 %a, i64 %b) {
  74 ; CHECK-LABEL: @hoist_udiv(
  75 ; CHECK-NEXT:  entry:
  76 ; CHECK-NEXT:    [[A_FROZEN:%.*]] = freeze i64 [[A:%.*]]
  77 ; CHECK-NEXT:    [[B_FROZEN:%.*]] = freeze i64 [[B:%.*]]
  78 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i64 [[A_FROZEN]], [[B_FROZEN]]
  79 ; CHECK-NEXT:    [[TMP0:%.*]] = mul i64 [[DIV]], [[B_FROZEN]]
  80 ; CHECK-NEXT:    [[REM_DECOMPOSED:%.*]] = sub i64 [[A_FROZEN]], [[TMP0]]
  81 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i64 [[REM_DECOMPOSED]], 42
  82 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
  83 ; CHECK:       if:
  84 ; CHECK-NEXT:    br label [[END]]
  85 ; CHECK:       end:
  86 ; CHECK-NEXT:    [[RET:%.*]] = phi i64 [ [[DIV]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
  87 ; CHECK-NEXT:    ret i64 [[RET]]
  88 ;
  89 entry:
  90   %rem = urem i64 %a, %b
  91   %cmp = icmp eq i64 %rem, 42
  92   br i1 %cmp, label %if, label %end
  93
  94 if:
  95   %div = udiv i64 %a, %b
  96   br label %end
  97
  98 end:
  99   %ret = phi i64 [ %div, %if ], [ 3, %entry ]
 100   ret i64 %ret
 101 }
 102
 103 ; Hoist the srem if it's safe and free, otherwise decompose it.
 104
 105 define i16 @hoist_srem(i16 %a, i16 %b) {
 106 ; CHECK-LABEL: @hoist_srem(
 107 ; CHECK-NEXT:  entry:
 108 ; CHECK-NEXT:    [[A_FROZEN:%.*]] = freeze i16 [[A:%.*]]
 109 ; CHECK-NEXT:    [[B_FROZEN:%.*]] = freeze i16 [[B:%.*]]
 110 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i16 [[A_FROZEN]], [[B_FROZEN]]
 111 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i16 [[DIV]], 42
 112 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
 113 ; CHECK:       if:
 114 ; CHECK-NEXT:    [[TMP0:%.*]] = mul i16 [[DIV]], [[B_FROZEN]]
 115 ; CHECK-NEXT:    [[REM_DECOMPOSED:%.*]] = sub i16 [[A_FROZEN]], [[TMP0]]
 116 ; CHECK-NEXT:    br label [[END]]
 117 ; CHECK:       end:
 118 ; CHECK-NEXT:    [[RET:%.*]] = phi i16 [ [[REM_DECOMPOSED]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
 119 ; CHECK-NEXT:    ret i16 [[RET]]
 120 ;
 121 entry:
 122   %div = sdiv i16 %a, %b
 123   %cmp = icmp eq i16 %div, 42
 124   br i1 %cmp, label %if, label %end
 125
 126 if:
 127   %rem = srem i16 %a, %b
 128   br label %end
 129
 130 end:
 131   %ret = phi i16 [ %rem, %if ], [ 3, %entry ]
 132   ret i16 %ret
 133 }
 134
 135 ; Hoist the urem if it's safe and free, otherwise decompose it.
 136
 137 define i8 @hoist_urem(i8 %a, i8 %b) {
 138 ; CHECK-LABEL: @hoist_urem(
 139 ; CHECK-NEXT:  entry:
 140 ; CHECK-NEXT:    [[A_FROZEN:%.*]] = freeze i8 [[A:%.*]]
 141 ; CHECK-NEXT:    [[B_FROZEN:%.*]] = freeze i8 [[B:%.*]]
 142 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i8 [[A_FROZEN]], [[B_FROZEN]]
 143 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[DIV]], 42
 144 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
 145 ; CHECK:       if:
 146 ; CHECK-NEXT:    [[TMP0:%.*]] = mul i8 [[DIV]], [[B_FROZEN]]
 147 ; CHECK-NEXT:    [[REM_DECOMPOSED:%.*]] = sub i8 [[A_FROZEN]], [[TMP0]]
 148 ; CHECK-NEXT:    br label [[END]]
 149 ; CHECK:       end:
 150 ; CHECK-NEXT:    [[RET:%.*]] = phi i8 [ [[REM_DECOMPOSED]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
 151 ; CHECK-NEXT:    ret i8 [[RET]]
 152 ;
 153 entry:
 154   %div = udiv i8 %a, %b
 155   %cmp = icmp eq i8 %div, 42
 156   br i1 %cmp, label %if, label %end
 157
 158 if:
 159   %rem = urem i8 %a, %b
 160   br label %end
 161
 162 end:
 163   %ret = phi i8 [ %rem, %if ], [ 3, %entry ]
 164   ret i8 %ret
 165 }
 166
 167 ; Be careful with RAUW/invalidation if this is a srem-of-srem.
 168
 169 define i32 @srem_of_srem_unexpanded(i32 %X, i32 %Y, i32 %Z) {
 170 ; CHECK-LABEL: @srem_of_srem_unexpanded(
 171 ; CHECK-NEXT:    [[T0:%.*]] = mul nsw i32 [[Z:%.*]], [[Y:%.*]]
 172 ; CHECK-NEXT:    [[X_FROZEN:%.*]] = freeze i32 [[X:%.*]]
 173 ; CHECK-NEXT:    [[T0_FROZEN:%.*]] = freeze i32 [[T0]]
 174 ; CHECK-NEXT:    [[T1:%.*]] = sdiv i32 [[X_FROZEN]], [[T0_FROZEN]]
 175 ; CHECK-NEXT:    [[T2:%.*]] = mul nsw i32 [[T0]], [[T1]]
 176 ; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[T1]], [[T0_FROZEN]]
 177 ; CHECK-NEXT:    [[T3_DECOMPOSED:%.*]] = sub i32 [[X_FROZEN]], [[TMP1]]
 178 ; CHECK-NEXT:    [[Y_FROZEN:%.*]] = freeze i32 [[Y]]
 179 ; CHECK-NEXT:    [[T4:%.*]] = sdiv i32 [[T3_DECOMPOSED]], [[Y_FROZEN]]
 180 ; CHECK-NEXT:    [[T5:%.*]] = mul nsw i32 [[T4]], [[Y]]
 181 ; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 [[T4]], [[Y_FROZEN]]
 182 ; CHECK-NEXT:    [[T6_DECOMPOSED:%.*]] = sub i32 [[T3_DECOMPOSED]], [[TMP2]]
 183 ; CHECK-NEXT:    ret i32 [[T6_DECOMPOSED]]
 184 ;
 185   %t0 = mul nsw i32 %Z, %Y
 186   %t1 = sdiv i32 %X, %t0
 187   %t2 = mul nsw i32 %t0, %t1
 188   %t3 = srem i32 %X, %t0
 189   %t4 = sdiv i32 %t3, %Y
 190   %t5 = mul nsw i32 %t4, %Y
 191   %t6 = srem i32 %t3, %Y
 192   ret i32 %t6
 193 }
 194 define i32 @srem_of_srem_expanded(i32 %X, i32 %Y, i32 %Z) {
 195 ; CHECK-LABEL: @srem_of_srem_expanded(
 196 ; CHECK-NEXT:    [[T0:%.*]] = mul nsw i32 [[Z:%.*]], [[Y:%.*]]
 197 ; CHECK-NEXT:    [[T1:%.*]] = sdiv i32 [[X:%.*]], [[T0]]
 198 ; CHECK-NEXT:    [[T2:%.*]] = mul nsw i32 [[T0]], [[T1]]
 199 ; CHECK-NEXT:    [[T3:%.*]] = sub nsw i32 [[X]], [[T2]]
 200 ; CHECK-NEXT:    [[T4:%.*]] = sdiv i32 [[T3]], [[Y]]
 201 ; CHECK-NEXT:    [[T5:%.*]] = mul nsw i32 [[T4]], [[Y]]
 202 ; CHECK-NEXT:    [[T6:%.*]] = sub nsw i32 [[T3]], [[T5]]
 203 ; CHECK-NEXT:    ret i32 [[T6]]
 204 ;
 205   %t0 = mul nsw i32 %Z, %Y
 206   %t1 = sdiv i32 %X, %t0
 207   %t2 = mul nsw i32 %t0, %t1
 208   %t3 = sub nsw i32 %X, %t2
 209   %t4 = sdiv i32 %t3, %Y
 210   %t5 = mul nsw i32 %t4, %Y
 211   %t6 = sub nsw i32 %t3, %t5
 212   ret i32 %t6
 213 }
 214
 215 ; If the ops don't match, don't do anything: signedness.
 216
 217 define i32 @dont_hoist_udiv(i32 %a, i32 %b) {
 218 ; CHECK-LABEL: @dont_hoist_udiv(
 219 ; CHECK-NEXT:  entry:
 220 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[A:%.*]], [[B:%.*]]
 221 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 42
 222 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
 223 ; CHECK:       if:
 224 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[A]], [[B]]
 225 ; CHECK-NEXT:    br label [[END]]
 226 ; CHECK:       end:
 227 ; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[DIV]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
 228 ; CHECK-NEXT:    ret i32 [[RET]]
 229 ;
 230 entry:
 231   %rem = srem i32 %a, %b
 232   %cmp = icmp eq i32 %rem, 42
 233   br i1 %cmp, label %if, label %end
 234
 235 if:
 236   %div = udiv i32 %a, %b
 237   br label %end
 238
 239 end:
 240   %ret = phi i32 [ %div, %if ], [ 3, %entry ]
 241   ret i32 %ret
 242 }
 243
 244 ; If the ops don't match, don't do anything: operation.
 245
 246 define i32 @dont_hoist_srem(i32 %a, i32 %b) {
 247 ; CHECK-LABEL: @dont_hoist_srem(
 248 ; CHECK-NEXT:  entry:
 249 ; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[A:%.*]], [[B:%.*]]
 250 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 42
 251 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
 252 ; CHECK:       if:
 253 ; CHECK-NEXT:    [[REM2:%.*]] = srem i32 [[A]], [[B]]
 254 ; CHECK-NEXT:    br label [[END]]
 255 ; CHECK:       end:
 256 ; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[REM2]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
 257 ; CHECK-NEXT:    ret i32 [[RET]]
 258 ;
 259 entry:
 260   %rem = urem i32 %a, %b
 261   %cmp = icmp eq i32 %rem, 42
 262   br i1 %cmp, label %if, label %end
 263
 264 if:
 265   %rem2 = srem i32 %a, %b
 266   br label %end
 267
 268 end:
 269   %ret = phi i32 [ %rem2, %if ], [ 3, %entry ]
 270   ret i32 %ret
 271 }
 272
 273 ; If the ops don't match, don't do anything: operands.
 274
 275 define i32 @dont_hoist_sdiv(i32 %a, i32 %b, i32 %c) {
 276 ; CHECK-LABEL: @dont_hoist_sdiv(
 277 ; CHECK-NEXT:  entry:
 278 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[A:%.*]], [[B:%.*]]
 279 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 42
 280 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
 281 ; CHECK:       if:
 282 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A]], [[C:%.*]]
 283 ; CHECK-NEXT:    br label [[END]]
 284 ; CHECK:       end:
 285 ; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[DIV]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
 286 ; CHECK-NEXT:    ret i32 [[RET]]
 287 ;
 288 entry:
 289   %rem = srem i32 %a, %b
 290   %cmp = icmp eq i32 %rem, 42
 291   br i1 %cmp, label %if, label %end
 292
 293 if:
 294   %div = sdiv i32 %a, %c
 295   br label %end
 296
 297 end:
 298   %ret = phi i32 [ %div, %if ], [ 3, %entry ]
 299   ret i32 %ret
 300 }
 301
 302 ; If the target doesn't have a unified div/rem op for the type, decompose rem in-place to mul+sub.
 303
 304 define i128 @dont_hoist_urem(i128 %a, i128 %b) {
 305 ; CHECK-LABEL: @dont_hoist_urem(
 306 ; CHECK-NEXT:  entry:
 307 ; CHECK-NEXT:    [[A_FROZEN:%.*]] = freeze i128 [[A:%.*]]
 308 ; CHECK-NEXT:    [[B_FROZEN:%.*]] = freeze i128 [[B:%.*]]
 309 ; CHECK-NEXT:    [[DIV:%.*]] = udiv i128 [[A_FROZEN]], [[B_FROZEN]]
 310 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i128 [[DIV]], 42
 311 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
 312 ; CHECK:       if:
 313 ; CHECK-NEXT:    [[TMP0:%.*]] = mul i128 [[DIV]], [[B_FROZEN]]
 314 ; CHECK-NEXT:    [[REM_DECOMPOSED:%.*]] = sub i128 [[A_FROZEN]], [[TMP0]]
 315 ; CHECK-NEXT:    br label [[END]]
 316 ; CHECK:       end:
 317 ; CHECK-NEXT:    [[RET:%.*]] = phi i128 [ [[REM_DECOMPOSED]], [[IF]] ], [ 3, [[ENTRY:%.*]] ]
 318 ; CHECK-NEXT:    ret i128 [[RET]]
 319 ;
 320 entry:
 321   %div = udiv i128 %a, %b
 322   %cmp = icmp eq i128 %div, 42
 323   br i1 %cmp, label %if, label %end
 324
 325 if:
 326   %rem = urem i128 %a, %b
 327   br label %end
 328
 329 end:
 330   %ret = phi i128 [ %rem, %if ], [ 3, %entry ]
 331   ret i128 %ret
 332 }
 333
 334 ; We don't hoist if one op does not dominate the other,
 335 ; but we could hoist both ops to the common predecessor block?
 336
 337 define i32 @no_domination(i1 %cmp, i32 %a, i32 %b) {
 338 ; CHECK-LABEL: @no_domination(
 339 ; CHECK-NEXT:  entry:
 340 ; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 341 ; CHECK:       if:
 342 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[A:%.*]], [[B:%.*]]
 343 ; CHECK-NEXT:    br label [[END:%.*]]
 344 ; CHECK:       else:
 345 ; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[A]], [[B]]
 346 ; CHECK-NEXT:    br label [[END]]
 347 ; CHECK:       end:
 348 ; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[DIV]], [[IF]] ], [ [[REM]], [[ELSE]] ]
 349 ; CHECK-NEXT:    ret i32 [[RET]]
 350 ;
 351 entry:
 352   br i1 %cmp, label %if, label %else
 353
 354 if:
 355   %div = sdiv i32 %a, %b
 356   br label %end
 357
 358 else:
 359   %rem = srem i32 %a, %b
 360   br label %end
 361
 362 end:
 363   %ret = phi i32 [ %div, %if ], [ %rem, %else ]
 364   ret i32 %ret
 365 }
 366