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 }
 390
 391 ; https://alive2.llvm.org/ce/z/3QfEHm
 392 define i8 @known_power_of_two_rust_next_power_of_two(i8 %x, i8 %y) {
 393 ; CHECK-LABEL: @known_power_of_two_rust_next_power_of_two(
 394 ; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], -1
 395 ; CHECK-NEXT:    [[TMP2:%.*]] = tail call range(i8 0, 9) i8 @llvm.ctlz.i8(i8 [[TMP1]], i1 true)
 396 ; CHECK-NEXT:    [[TMP3:%.*]] = lshr i8 -1, [[TMP2]]
 397 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ugt i8 [[X]], 1
 398 ; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i8 [[TMP3]], i8 0
 399 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[TMP5]], [[Y:%.*]]
 400 ; CHECK-NEXT:    ret i8 [[R]]
 401 ;
 402   %2 = add i8 %x, -1
 403   %3 = tail call i8 @llvm.ctlz.i8(i8 %2, i1 true)
 404   %4 = lshr i8 -1, %3
 405   %5 = add i8 %4, 1
 406   %6 = icmp ugt i8 %x, 1
 407   %p = select i1 %6, i8 %5, i8 1
 408   ; Rust's implementation of `%p = next_power_of_two(%x)`
 409
 410   %r = urem i8 %y, %p
 411   ret i8 %r
 412 }
 413
 414 define i8 @known_power_of_two_lshr_add_one_allow_zero(i8 %x, i8 %y) {
 415 ; CHECK-LABEL: @known_power_of_two_lshr_add_one_allow_zero(
 416 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 -1, [[X:%.*]]
 417 ; CHECK-NEXT:    [[R:%.*]] = and i8 [[TMP1]], [[Y:%.*]]
 418 ; CHECK-NEXT:    ret i8 [[R]]
 419 ;
 420   %4 = lshr i8 -1, %x
 421   %p = add i8 %4, 1
 422
 423   ; Note: y % p --> y & (p - 1) allows p == 0
 424   %r = urem i8 %y, %p
 425   ret i8 %r
 426 }
 427
 428 define i1 @known_power_of_two_lshr_add_one_nuw_deny_zero(i8 %x, i8 %y) {
 429 ; CHECK-LABEL: @known_power_of_two_lshr_add_one_nuw_deny_zero(
 430 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 -1, [[X:%.*]]
 431 ; CHECK-NEXT:    [[TMP2:%.*]] = sub i8 -2, [[TMP1]]
 432 ; CHECK-NEXT:    [[TMP3:%.*]] = or i8 [[TMP2]], [[Y:%.*]]
 433 ; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[TMP3]], -1
 434 ; CHECK-NEXT:    ret i1 [[R]]
 435 ;
 436   %4 = lshr i8 -1, %x
 437   %p = add nuw i8 %4, 1
 438
 439   ; Note: A & B_Pow2 != B_Pow2 --> A & B_Pow2 == 0 requires B_Pow2 != 0
 440   %and = and i8 %p, %y
 441   %r = icmp ne i8 %and, %p
 442   ret i1 %r
 443 }
 444
 445 define i1 @negative_known_power_of_two_lshr_add_one_deny_zero(i8 %x, i8 %y) {
 446 ; CHECK-LABEL: @negative_known_power_of_two_lshr_add_one_deny_zero(
 447 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 -1, [[X:%.*]]
 448 ; CHECK-NEXT:    [[TMP2:%.*]] = sub i8 -2, [[TMP1]]
 449 ; CHECK-NEXT:    [[TMP3:%.*]] = or i8 [[TMP2]], [[Y:%.*]]
 450 ; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[TMP3]], -1
 451 ; CHECK-NEXT:    ret i1 [[R]]
 452 ;
 453   %4 = lshr i8 -1, %x
 454   %p = add i8 %4, 1
 455
 456   ; Note: A & B_Pow2 != B_Pow2 --> A & B_Pow2 == 0 requires B_Pow2 != 0
 457   %and = and i8 %p, %y
 458   %r = icmp ne i8 %and, %p
 459   ret i1 %r
 460 }
 461
 462 define i1 @negative_known_power_of_two_lshr_add_one_nsw_deny_zero(i8 %x, i8 %y) {
 463 ; CHECK-LABEL: @negative_known_power_of_two_lshr_add_one_nsw_deny_zero(
 464 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 -1, [[X:%.*]]
 465 ; CHECK-NEXT:    [[TMP2:%.*]] = sub i8 -2, [[TMP1]]
 466 ; CHECK-NEXT:    [[TMP3:%.*]] = or i8 [[TMP2]], [[Y:%.*]]
 467 ; CHECK-NEXT:    [[R:%.*]] = icmp ne i8 [[TMP3]], -1
 468 ; CHECK-NEXT:    ret i1 [[R]]
 469 ;
 470   %4 = lshr i8 -1, %x
 471   %p = add nsw i8 %4, 1
 472
 473   ; Note: A & B_Pow2 != B_Pow2 --> A & B_Pow2 == 0 requires B_Pow2 != 0
 474   %and = and i8 %p, %y
 475   %r = icmp ne i8 %and, %p
 476   ret i1 %r
 477 }
 478
 479 define i8 @known_power_of_two_lshr_add_negative_1(i8 %x, i8 %y) {
 480 ; CHECK-LABEL: @known_power_of_two_lshr_add_negative_1(
 481 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 -2, [[X:%.*]]
 482 ; CHECK-NEXT:    [[P:%.*]] = add nuw i8 [[TMP1]], 1
 483 ; CHECK-NEXT:    [[R:%.*]] = urem i8 [[Y:%.*]], [[P]]
 484 ; CHECK-NEXT:    ret i8 [[R]]
 485 ;
 486   %4 = lshr i8 -2, %x
 487   %p = add i8 %4, 1
 488
 489   %r = urem i8 %y, %p
 490   ret i8 %r
 491 }
 492
 493 define i8 @known_power_of_two_lshr_add_negative_2(i8 %x, i8 %y) {
 494 ; CHECK-LABEL: @known_power_of_two_lshr_add_negative_2(
 495 ; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 -1, [[X:%.*]]
 496 ; CHECK-NEXT:    [[P:%.*]] = add nsw i8 [[TMP1]], -1
 497 ; CHECK-NEXT:    [[R:%.*]] = urem i8 [[Y:%.*]], [[P]]
 498 ; CHECK-NEXT:    ret i8 [[R]]
 499 ;
 500   %4 = lshr i8 -1, %x
 501   %p = add i8 %4, -1
 502
 503   %r = urem i8 %y, %p
 504   ret i8 %r
 505 }