llvm/test/Analysis/ValueTracking/known-power-of-two-urem.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -S -passes=instcombine < %s | FileCheck %s
   3
   4 ; Check if a value can be deduced as a power of 2, allowing urem optimization.
   5 ; i.e. A urem B = A & (B - 1) if B is a power of 2.
   6
   7 define i64 @known_power_of_two_urem_phi(i64 %size, i1 %cmp, i1 %cmp1) {
   8 ; CHECK-LABEL: @known_power_of_two_urem_phi(
   9 ; CHECK-NEXT:  entry:
  10 ; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
  11 ; CHECK:       cond.true:
  12 ; CHECK-NEXT:    br i1 [[CMP1:%.*]], label [[COND_TRUE_TRUE:%.*]], label [[COND_TRUE_FALSE:%.*]]
  13 ; CHECK:       cond.true.true:
  14 ; CHECK-NEXT:    br label [[COND_TRUE_END:%.*]]
  15 ; CHECK:       cond.true.false:
  16 ; CHECK-NEXT:    br label [[COND_TRUE_END]]
  17 ; CHECK:       cond.true.end:
  18 ; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ 1, [[COND_TRUE_TRUE]] ], [ 3, [[COND_TRUE_FALSE]] ]
  19 ; CHECK-NEXT:    br label [[COND_END]]
  20 ; CHECK:       cond.end:
  21 ; CHECK-NEXT:    [[PHI1:%.*]] = phi i64 [ 4095, [[ENTRY:%.*]] ], [ [[PHI]], [[COND_TRUE_END]] ]
  22 ; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[PHI1]], [[SIZE:%.*]]
  23 ; CHECK-NEXT:    ret i64 [[UREM]]
  24 ;
  25 entry:
  26   br i1 %cmp, label %cond.true, label %cond.end
  27
  28 cond.true:
  29   br i1 %cmp1, label %cond.true.true, label %cond.true.false
  30
  31 cond.true.true:
  32   br label %cond.true.end
  33
  34 cond.true.false:
  35   br label %cond.true.end
  36
  37 cond.true.end:
  38   %phi = phi i64 [ 2, %cond.true.true ], [ 4, %cond.true.false ]
  39   br label %cond.end
  40
  41 cond.end:
  42   %phi1 = phi i64 [ 4096, %entry ], [ %phi, %cond.true.end ]
  43   %urem = urem i64 %size, %phi1
  44   ret i64 %urem
  45 }
  46
  47 define i64 @known_power_of_two_urem_nested_expr(i64 %size, i1 %cmp, i1 %cmp1, i64 %0) {
  48 ; CHECK-LABEL: @known_power_of_two_urem_nested_expr(
  49 ; CHECK-NEXT:  entry:
  50 ; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[COND_TRUE:%.*]], label [[COND_FALSE:%.*]]
  51 ; CHECK:       cond.true:
  52 ; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw i64 1, [[TMP0:%.*]]
  53 ; CHECK-NEXT:    br label [[COND_END:%.*]]
  54 ; CHECK:       cond.false:
  55 ; CHECK-NEXT:    [[SELECT:%.*]] = select i1 [[CMP1:%.*]], i64 2, i64 8
  56 ; CHECK-NEXT:    br label [[COND_END]]
  57 ; CHECK:       cond.end:
  58 ; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[SELECT]], [[COND_FALSE]] ], [ [[TMP1]], [[COND_TRUE]] ], [ [[PHI]], [[COND_END]] ]
  59 ; CHECK-NEXT:    [[TMP2:%.*]] = add i64 [[PHI]], -1
  60 ; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP2]], [[SIZE:%.*]]
  61 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i64 [[UREM]], 10
  62 ; CHECK-NEXT:    br i1 [[CMP2]], label [[COND_END]], label [[END:%.*]]
  63 ; CHECK:       end:
  64 ; CHECK-NEXT:    ret i64 [[UREM]]
  65 ;
  66 entry:
  67   br i1 %cmp, label %cond.true, label %cond.false
  68
  69 cond.true:
  70   %1 = shl nuw i64 1, %0
  71   br label %cond.end
  72
  73 cond.false:
  74   %select = select i1 %cmp1, i64 2, i64 8
  75   br label %cond.end
  76
  77 cond.end:
  78   %phi = phi i64 [ %select, %cond.false ], [ %1, %cond.true ], [ %phi, %cond.end ]
  79   %2 = phi i64 [ %size, %cond.false ], [ %size, %cond.true ], [ %0, %cond.end ]
  80   %urem = urem i64 %size, %phi
  81   %cmp2 = icmp ult i64 %urem, 10
  82   br i1 %cmp2, label %cond.end, label %end
  83
  84 end:
  85   ret i64 %urem
  86 }
  87
  88 define i64 @known_power_of_two_urem_negative(i64 %size, i1 %cmp, i64 %0) {
  89 ; urem is not replaced if not all operands are power of 2.
  90 ;
  91 ; CHECK-LABEL: @known_power_of_two_urem_negative(
  92 ; CHECK-NEXT:  entry:
  93 ; CHECK-NEXT:    br i1 [[CMP:%.*]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
  94 ; CHECK:       cond.true:
  95 ; CHECK-NEXT:    br label [[COND_END]]
  96 ; CHECK:       cond.end:
  97 ; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ 4, [[ENTRY:%.*]] ], [ [[TMP0:%.*]], [[COND_TRUE]] ]
  98 ; CHECK-NEXT:    [[UREM:%.*]] = urem i64 [[SIZE:%.*]], [[PHI]]
  99 ; CHECK-NEXT:    ret i64 [[UREM]]
 100 ;
 101 entry:
 102   br i1 %cmp, label %cond.true, label %cond.end
 103
 104 cond.true:
 105   br label %cond.end
 106
 107 cond.end:
 108   %phi = phi i64 [ 4, %entry ], [ %0, %cond.true ]
 109   %urem = urem i64 %size, %phi
 110   ret i64 %urem
 111 }
 112
 113 define i64 @known_power_of_two_urem_loop_mul(i64 %size, i64 %a) {
 114 ; CHECK-LABEL: @known_power_of_two_urem_loop_mul(
 115 ; CHECK-NEXT:  entry:
 116 ; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
 117 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 118 ; CHECK:       for.body:
 119 ; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
 120 ; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 121 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[PHI]], -1
 122 ; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP0]], [[SIZE:%.*]]
 123 ; CHECK-NEXT:    [[ADD]] = add nuw i64 [[SUM]], [[UREM]]
 124 ; CHECK-NEXT:    [[I]] = shl nuw i64 [[PHI]], 2
 125 ; CHECK-NEXT:    [[ICMP:%.*]] = icmp ult i64 [[PHI]], 25000000
 126 ; CHECK-NEXT:    br i1 [[ICMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 127 ; CHECK:       for.end:
 128 ; CHECK-NEXT:    ret i64 [[SUM]]
 129 ;
 130 entry:
 131   %start = shl nuw i64 1, %a
 132   br label %for.body
 133
 134 for.body:
 135   %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
 136   %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
 137   %urem = urem i64 %size, %phi
 138   %add = add nuw i64 %sum, %urem
 139   %i = mul nuw i64 %phi, 4
 140   %icmp = icmp ult i64 %i, 100000000
 141   br i1 %icmp, label %for.body, label %for.end
 142
 143 for.end:
 144   %r = phi i64 [ %sum, %for.body ]
 145   ret i64 %r
 146 }
 147
 148 define i64 @known_power_of_two_urem_loop_mul_negative(i64 %size, i64 %a) {
 149 ; Cannot deduce induction variable is a power of 2 if it is multiplied by 3.
 150 ;
 151 ; CHECK-LABEL: @known_power_of_two_urem_loop_mul_negative(
 152 ; CHECK-NEXT:  entry:
 153 ; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
 154 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 155 ; CHECK:       for.body:
 156 ; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
 157 ; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 158 ; CHECK-NEXT:    [[UREM:%.*]] = urem i64 [[SIZE:%.*]], [[PHI]]
 159 ; CHECK-NEXT:    [[ADD]] = add nuw i64 [[SUM]], [[UREM]]
 160 ; CHECK-NEXT:    [[I]] = mul nuw i64 [[PHI]], 3
 161 ; CHECK-NEXT:    [[ICMP:%.*]] = icmp ult i64 [[PHI]], 33333334
 162 ; CHECK-NEXT:    br i1 [[ICMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 163 ; CHECK:       for.end:
 164 ; CHECK-NEXT:    ret i64 [[SUM]]
 165 ;
 166 entry:
 167   %start = shl nuw i64 1, %a
 168   br label %for.body
 169
 170 for.body:
 171   %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
 172   %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
 173   %urem = urem i64 %size, %phi
 174   %add = add nuw i64 %sum, %urem
 175   %i = mul nuw i64 %phi, 3
 176   %icmp = icmp ult i64 %i, 100000000
 177   br i1 %icmp, label %for.body, label %for.end
 178
 179 for.end:
 180   %r = phi i64 [ %sum, %for.body ]
 181   ret i64 %r
 182 }
 183
 184 define i64 @known_power_of_two_urem_loop_shl(i64 %size, i64 %a) {
 185 ; CHECK-LABEL: @known_power_of_two_urem_loop_shl(
 186 ; CHECK-NEXT:  entry:
 187 ; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
 188 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 189 ; CHECK:       for.body:
 190 ; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
 191 ; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 192 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[PHI]], -1
 193 ; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP0]], [[SIZE:%.*]]
 194 ; CHECK-NEXT:    [[ADD]] = add nuw i64 [[SUM]], [[UREM]]
 195 ; CHECK-NEXT:    [[I]] = shl nuw i64 [[PHI]], 1
 196 ; CHECK-NEXT:    [[ICMP:%.*]] = icmp ult i64 [[PHI]], 50000000
 197 ; CHECK-NEXT:    br i1 [[ICMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 198 ; CHECK:       for.end:
 199 ; CHECK-NEXT:    ret i64 [[SUM]]
 200 ;
 201 entry:
 202   %start = shl nuw i64 1, %a
 203   br label %for.body
 204
 205 for.body:
 206   %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
 207   %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
 208   %urem = urem i64 %size, %phi
 209   %add = add nuw i64 %sum, %urem
 210   %i = shl nuw i64 %phi, 1
 211   %icmp = icmp ult i64 %i, 100000000
 212   br i1 %icmp, label %for.body, label %for.end
 213
 214 for.end:
 215   %r = phi i64 [ %sum, %for.body ]
 216   ret i64 %r
 217 }
 218
 219 define i64 @known_power_of_two_urem_loop_lshr(i64 %size, i64 %a) {
 220 ; CHECK-LABEL: @known_power_of_two_urem_loop_lshr(
 221 ; CHECK-NEXT:  entry:
 222 ; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
 223 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 224 ; CHECK:       for.body:
 225 ; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
 226 ; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 227 ; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[PHI]], -1
 228 ; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP0]], [[SIZE:%.*]]
 229 ; CHECK-NEXT:    [[ADD]] = add nuw i64 [[SUM]], [[UREM]]
 230 ; CHECK-NEXT:    [[I]] = lshr i64 [[PHI]], 1
 231 ; CHECK-NEXT:    [[ICMP_NOT:%.*]] = icmp ult i64 [[PHI]], 2
 232 ; CHECK-NEXT:    br i1 [[ICMP_NOT]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 233 ; CHECK:       for.end:
 234 ; CHECK-NEXT:    ret i64 [[SUM]]
 235 ;
 236 entry:
 237   %start = shl nuw i64 1, %a
 238   br label %for.body
 239
 240 for.body:
 241   %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
 242   %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
 243   %urem = urem i64 %size, %phi
 244   %add = add nuw i64 %sum, %urem
 245   %i = lshr i64 %phi, 1
 246   %icmp = icmp ugt i64 %i, 0
 247   br i1 %icmp, label %for.body, label %for.end
 248
 249 for.end:
 250   %r = phi i64 [ %sum, %for.body ]
 251   ret i64 %r
 252 }
 253
 254
 255 define i64 @known_power_of_two_urem_loop_ashr(i64 %size, i64 %a) {
 256 ; CHECK-LABEL: @known_power_of_two_urem_loop_ashr(
 257 ; CHECK-NEXT:  entry:
 258 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 259 ; CHECK:       for.body:
 260 ; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ 4096, [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
 261 ; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 262 ; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[PHI]], -1
 263 ; CHECK-NEXT:    [[UREM:%.*]] = and i64 [[TMP0]], [[SIZE:%.*]]
 264 ; CHECK-NEXT:    [[ADD]] = add nsw i64 [[SUM]], [[UREM]]
 265 ; CHECK-NEXT:    [[I]] = lshr i64 [[PHI]], [[A:%.*]]
 266 ; CHECK-NEXT:    [[ICMP_NOT:%.*]] = icmp eq i64 [[I]], 0
 267 ; CHECK-NEXT:    br i1 [[ICMP_NOT]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 268 ; CHECK:       for.end:
 269 ; CHECK-NEXT:    ret i64 [[SUM]]
 270 ;
 271 entry:
 272   br label %for.body
 273
 274 for.body:
 275   %phi = phi i64 [ 4096, %entry ], [ %i, %for.body ]
 276   %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
 277   %urem = urem i64 %size, %phi
 278   %add = add nsw i64 %sum, %urem
 279   %i = ashr i64 %phi, %a
 280   %icmp = icmp ugt i64 %i, 0
 281   br i1 %icmp, label %for.body, label %for.end
 282
 283 for.end:
 284   %r = phi i64 [ %sum, %for.body ]
 285   ret i64 %r
 286 }
 287
 288 define i64 @known_power_of_two_urem_loop_ashr_negative(i64 %size, i64 %a) {
 289 ; Cannot deduce induction variable is a power of 2 for ashr if its starting
 290 ; value is equal to sign bit
 291 ;
 292 ; CHECK-LABEL: @known_power_of_two_urem_loop_ashr_negative(
 293 ; CHECK-NEXT:  entry:
 294 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 295 ; CHECK:       for.body:
 296 ; CHECK-NEXT:    br i1 true, label [[FOR_BODY]], label [[FOR_END:%.*]]
 297 ; CHECK:       for.end:
 298 ; CHECK-NEXT:    ret i64 poison
 299 ;
 300 entry:
 301   br label %for.body
 302
 303 for.body:
 304   %phi = phi i64 [ u0x8000000000000000, %entry ], [ %i, %for.body ]
 305   %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
 306   %urem = urem i64 %size, %phi
 307   %add = add nsw i64 %sum, %urem
 308   %i = ashr i64 %phi, %a
 309   %icmp = icmp ugt i64 %i, 1
 310   br i1 %icmp, label %for.body, label %for.end
 311
 312 for.end:
 313   %r = phi i64 [ %sum, %for.body ]
 314   ret i64 %r
 315 }
 316
 317 define i64 @known_power_of_two_urem_loop_ashr_negative_2(i64 %size, i64 %a) {
 318 ; Cannot deduce induction variable is a power of 2 for ashr if its starting
 319 ; value may equal to sign bit.
 320 ;
 321 ; CHECK-LABEL: @known_power_of_two_urem_loop_ashr_negative_2(
 322 ; CHECK-NEXT:  entry:
 323 ; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
 324 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 325 ; CHECK:       for.body:
 326 ; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
 327 ; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 328 ; CHECK-NEXT:    [[UREM:%.*]] = urem i64 [[SIZE:%.*]], [[PHI]]
 329 ; CHECK-NEXT:    [[ADD]] = add nsw i64 [[SUM]], [[UREM]]
 330 ; CHECK-NEXT:    [[I]] = ashr i64 [[PHI]], 2
 331 ; CHECK-NEXT:    [[ICMP_NOT:%.*]] = icmp ult i64 [[PHI]], 4
 332 ; CHECK-NEXT:    br i1 [[ICMP_NOT]], label [[FOR_END:%.*]], label [[FOR_BODY]]
 333 ; CHECK:       for.end:
 334 ; CHECK-NEXT:    ret i64 [[SUM]]
 335 ;
 336 entry:
 337   %start = shl nuw i64 1, %a
 338   br label %for.body
 339
 340 for.body:
 341   %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
 342   %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
 343   %urem = urem i64 %size, %phi
 344   %add = add nsw i64 %sum, %urem
 345   %i = ashr i64 %phi, 2
 346   %icmp = icmp ugt i64 %i, 0
 347   br i1 %icmp, label %for.body, label %for.end
 348
 349 for.end:
 350   %r = phi i64 [ %sum, %for.body ]
 351   ret i64 %r
 352 }
 353
 354 define i64 @known_power_of_two_urem_loop_negative(i64 %size, i64 %a) {
 355 ; Cannot deduce induction variable is a power of 2 if the recurrence is not one
 356 ; of the valid arithmetic operations.
 357 ;
 358 ; CHECK-LABEL: @known_power_of_two_urem_loop_negative(
 359 ; CHECK-NEXT:  entry:
 360 ; CHECK-NEXT:    [[START:%.*]] = shl nuw i64 1, [[A:%.*]]
 361 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 362 ; CHECK:       for.body:
 363 ; CHECK-NEXT:    [[PHI:%.*]] = phi i64 [ [[START]], [[ENTRY:%.*]] ], [ [[I:%.*]], [[FOR_BODY]] ]
 364 ; CHECK-NEXT:    [[SUM:%.*]] = phi i64 [ 0, [[ENTRY]] ], [ [[ADD:%.*]], [[FOR_BODY]] ]
 365 ; CHECK-NEXT:    [[UREM:%.*]] = urem i64 [[SIZE:%.*]], [[PHI]]
 366 ; CHECK-NEXT:    [[ADD]] = add nuw i64 [[SUM]], [[UREM]]
 367 ; CHECK-NEXT:    [[I]] = add nuw i64 [[PHI]], 1
 368 ; CHECK-NEXT:    [[ICMP:%.*]] = icmp ugt i64 [[PHI]], 1
 369 ; CHECK-NEXT:    br i1 [[ICMP]], label [[FOR_BODY]], label [[FOR_END:%.*]]
 370 ; CHECK:       for.end:
 371 ; CHECK-NEXT:    ret i64 [[SUM]]
 372 ;
 373 entry:
 374   %start = shl nuw i64 1, %a
 375   br label %for.body
 376
 377 for.body:
 378   %phi = phi i64 [ %start, %entry ], [ %i, %for.body ]
 379   %sum = phi i64 [ 0, %entry ], [ %add, %for.body ]
 380   %urem = urem i64 %size, %phi
 381   %add = add nuw i64 %sum, %urem
 382   %i = add nuw i64 %phi, 1
 383   %icmp = icmp ugt i64 %i, 2
 384   br i1 %icmp, label %for.body, label %for.end
 385
 386 for.end:
 387   %r = phi i64 [ %sum, %for.body ]
 388   ret i64 %r
 389 }