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 7define 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 [[SIZE:%.*]], [[PHI1]] 23; CHECK-NEXT: ret i64 [[UREM]] 24; 25entry: 26 br i1 %cmp, label %cond.true, label %cond.end 27 28cond.true: 29 br i1 %cmp1, label %cond.true.true, label %cond.true.false 30 31cond.true.true: 32 br label %cond.true.end 33 34cond.true.false: 35 br label %cond.true.end 36 37cond.true.end: 38 %phi = phi i64 [ 2, %cond.true.true ], [ 4, %cond.true.false ] 39 br label %cond.end 40 41cond.end: 42 %phi1 = phi i64 [ 4096, %entry ], [ %phi, %cond.true.end ] 43 %urem = urem i64 %size, %phi1 44 ret i64 %urem 45} 46 47define 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 [[SIZE:%.*]], [[TMP2]] 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; 66entry: 67 br i1 %cmp, label %cond.true, label %cond.false 68 69cond.true: 70 %1 = shl nuw i64 1, %0 71 br label %cond.end 72 73cond.false: 74 %select = select i1 %cmp1, i64 2, i64 8 75 br label %cond.end 76 77cond.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 84end: 85 ret i64 %urem 86} 87 88define 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; 101entry: 102 br i1 %cmp, label %cond.true, label %cond.end 103 104cond.true: 105 br label %cond.end 106 107cond.end: 108 %phi = phi i64 [ 4, %entry ], [ %0, %cond.true ] 109 %urem = urem i64 %size, %phi 110 ret i64 %urem 111} 112 113define 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 [[SIZE:%.*]], [[TMP0]] 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; 130entry: 131 %start = shl nuw i64 1, %a 132 br label %for.body 133 134for.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 143for.end: 144 %r = phi i64 [ %sum, %for.body ] 145 ret i64 %r 146} 147 148define 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; 166entry: 167 %start = shl nuw i64 1, %a 168 br label %for.body 169 170for.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 179for.end: 180 %r = phi i64 [ %sum, %for.body ] 181 ret i64 %r 182} 183 184define 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 [[SIZE:%.*]], [[TMP0]] 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; 201entry: 202 %start = shl nuw i64 1, %a 203 br label %for.body 204 205for.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 214for.end: 215 %r = phi i64 [ %sum, %for.body ] 216 ret i64 %r 217} 218 219define 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 [[SIZE:%.*]], [[TMP0]] 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; 236entry: 237 %start = shl nuw i64 1, %a 238 br label %for.body 239 240for.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 249for.end: 250 %r = phi i64 [ %sum, %for.body ] 251 ret i64 %r 252} 253 254 255define 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 [[SIZE:%.*]], [[TMP0]] 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; 271entry: 272 br label %for.body 273 274for.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 283for.end: 284 %r = phi i64 [ %sum, %for.body ] 285 ret i64 %r 286} 287 288define 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; 300entry: 301 br label %for.body 302 303for.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 312for.end: 313 %r = phi i64 [ %sum, %for.body ] 314 ret i64 %r 315} 316 317define 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; 336entry: 337 %start = shl nuw i64 1, %a 338 br label %for.body 339 340for.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 349for.end: 350 %r = phi i64 [ %sum, %for.body ] 351 ret i64 %r 352} 353 354define 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; 373entry: 374 %start = shl nuw i64 1, %a 375 br label %for.body 376 377for.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 386for.end: 387 %r = phi i64 [ %sum, %for.body ] 388 ret i64 %r 389} 390 391; https://alive2.llvm.org/ce/z/3QfEHm 392define 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 [[Y:%.*]], [[TMP5]] 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 414define 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 [[Y:%.*]], [[TMP1]] 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 428define 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 [[Y:%.*]], [[TMP2]] 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 445define 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 [[Y:%.*]], [[TMP2]] 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 462define 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 [[Y:%.*]], [[TMP2]] 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 479define 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 493define 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} 506