[InstCombine] Fold (A & 2^C1) + A => A & (2^C1 - 1) iff bit C1 in A is a sign bit (PR21929)

[RKSimon]

Summary

This is the final missing fold to handle the modulo2 simplification: https://github.com/llvm/llvm-project/issues/22303

Alive2: https://alive2.llvm.org/ce/z/Ygq26C

[RKSimon]

ping?

[nikic]

Can you please add some explicit tests for the actual pattern being folded? I don't think you're testing the commuted case currently, as well as some of the pre-conditions (like the fact that the and must be a power of two).

[RKSimon]

rebase with additional tests

[RKSimon]

ping?

[nikic]

Unless I overlooked it, I think this is still missing a test with a non-pow2 mask.

[RKSimon]

rebase now that we have a (negative) non-pow2 test

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(LHS, m_Shl(m_SDiv(m_Specific(RHS), m_APInt(C1)), m_APInt(C2)))) {
     APInt one(C2->getBitWidth(), 1);
     APInt minusC1 = -(*C1);
     if (minusC1 == (one << *C2)) {
       Constant *NewRHS = ConstantInt::get(RHS->getType(), minusC1);
       return BinaryOperator::CreateSRem(RHS, NewRHS);
     }
   }
 
+  // (A & 2^C1) + A => A & (2^C1 - 1) iff bit C1 in A is a sign bit
+  if (match(&I, m_c_Add(m_And(m_Value(A), m_APInt(C1)), m_Deferred(A))) &&
+      C1->isPowerOf2() && (ComputeNumSignBits(A) > C1->countLeadingZeros())) {
+    Constant *NewMask = ConstantInt::get(RHS->getType(), *C1 - 1);
+    return BinaryOperator::CreateAnd(A, NewMask);
+  }
+
   // A+B --> A|B iff A and B have no bits set in common.
   if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
     return BinaryOperator::CreateOr(LHS, RHS);
 
   // add (select X 0 (sub n A)) A  -->  select X A n
   {
     SelectInst *SI = dyn_cast<SelectInst>(LHS);
     Value *A = RHS;

llvm/test/Transforms/InstCombine/add-mask.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 ;
 ; (A & 2^C1) + A => A & (2^C1 - 1) iff bit C1 in A is a sign bit
 ;
 
 define i32 @add_mask_sign_i32(i32 %x) {
 ; CHECK-LABEL: @add_mask_sign_i32(
-; CHECK-NEXT:    [[A:%.*]] = ashr i32 [[X:%.*]], 31
-; CHECK-NEXT:    [[M:%.*]] = and i32 [[A]], 8
-; CHECK-NEXT:    [[R:%.*]] = add nsw i32 [[M]], [[A]]
+; CHECK-NEXT:    [[ISNEG:%.*]] = icmp slt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[ISNEG]], i32 7, i32 0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = ashr i32 %x, 31
   %m = and i32 %a, 8
   %r = add i32 %m, %a
   ret i32 %r
 }
 
 define i32 @add_mask_sign_commute_i32(i32 %x) {
 ; CHECK-LABEL: @add_mask_sign_commute_i32(
-; CHECK-NEXT:    [[A:%.*]] = ashr i32 [[X:%.*]], 31
-; CHECK-NEXT:    [[M:%.*]] = and i32 [[A]], 8
-; CHECK-NEXT:    [[R:%.*]] = add nsw i32 [[A]], [[M]]
+; CHECK-NEXT:    [[ISNEG:%.*]] = icmp slt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[ISNEG]], i32 7, i32 0
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = ashr i32 %x, 31
   %m = and i32 %a, 8
   %r = add i32 %a, %m
   ret i32 %r
 }
 
 define <2 x i32> @add_mask_sign_v2i32(<2 x i32> %x) {
 ; CHECK-LABEL: @add_mask_sign_v2i32(
-; CHECK-NEXT:    [[A:%.*]] = ashr <2 x i32> [[X:%.*]], <i32 31, i32 31>
-; CHECK-NEXT:    [[M:%.*]] = and <2 x i32> [[A]], <i32 8, i32 8>
-; CHECK-NEXT:    [[R:%.*]] = add nsw <2 x i32> [[M]], [[A]]
+; CHECK-NEXT:    [[ISNEG:%.*]] = icmp slt <2 x i32> [[X:%.*]], zeroinitializer
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[ISNEG]], <2 x i32> <i32 7, i32 7>, <2 x i32> zeroinitializer
 ; CHECK-NEXT:    ret <2 x i32> [[R]]
 ;
   %a = ashr <2 x i32> %x, <i32 31, i32 31>
   %m = and <2 x i32> %a, <i32 8, i32 8>
   %r = add <2 x i32> %m, %a
   ret <2 x i32> %r
 }
 
 define <2 x i32> @add_mask_sign_v2i32_nonuniform(<2 x i32> %x) {
 ; CHECK-LABEL: @add_mask_sign_v2i32_nonuniform(
 ; CHECK-NEXT:    [[A:%.*]] = ashr <2 x i32> [[X:%.*]], <i32 30, i32 31>
 ; CHECK-NEXT:    [[M:%.*]] = and <2 x i32> [[A]], <i32 8, i32 16>
 ; CHECK-NEXT:    [[R:%.*]] = add <2 x i32> [[M]], [[A]]
 ; CHECK-NEXT:    ret <2 x i32> [[R]]
 ;
   %a = ashr <2 x i32> %x, <i32 30, i32 31>
   %m = and <2 x i32> %a, <i32 8, i32 16>
   %r = add <2 x i32> %m, %a
   ret <2 x i32> %r
 }
 
 define i32 @add_mask_ashr28_i32(i32 %x) {
 ; CHECK-LABEL: @add_mask_ashr28_i32(
-; CHECK-NEXT:    [[A:%.*]] = ashr i32 [[X:%.*]], 28
-; CHECK-NEXT:    [[M:%.*]] = and i32 [[A]], 8
-; CHECK-NEXT:    [[R:%.*]] = add nsw i32 [[M]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 28
+; CHECK-NEXT:    [[R:%.*]] = and i32 [[TMP1]], 7
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = ashr i32 %x, 28
   %m = and i32 %a, 8
   %r = add i32 %m, %a
   ret i32 %r
 }
 

llvm/test/Transforms/InstCombine/modulo.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -passes=instcombine | FileCheck %s
 
 ; PR21929
 define i32 @modulo2(i32 %x) {
 ; CHECK-LABEL: @modulo2(
-; CHECK-NEXT:    [[REM_I:%.*]] = srem i32 [[X:%.*]], 2
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[REM_I]], 2
-; CHECK-NEXT:    [[RET_I:%.*]] = add nsw i32 [[TMP1]], [[REM_I]]
+; CHECK-NEXT:    [[RET_I:%.*]] = and i32 [[X:%.*]], 1
 ; CHECK-NEXT:    ret i32 [[RET_I]]
 ;
   %rem.i = srem i32 %x, 2
   %cmp.i = icmp slt i32 %rem.i, 0
   %add.i = select i1 %cmp.i, i32 2, i32 0
   %ret.i = add nsw i32 %add.i, %rem.i
   ret i32 %ret.i
 }
 
 define <2 x i32> @modulo2_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @modulo2_vec(
-; CHECK-NEXT:    [[REM_I:%.*]] = srem <2 x i32> [[X:%.*]], <i32 2, i32 2>
-; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[REM_I]], <i32 2, i32 2>
-; CHECK-NEXT:    [[RET_I:%.*]] = add nsw <2 x i32> [[TMP1]], [[REM_I]]
+; CHECK-NEXT:    [[RET_I:%.*]] = and <2 x i32> [[X:%.*]], <i32 1, i32 1>
 ; CHECK-NEXT:    ret <2 x i32> [[RET_I]]
 ;
   %rem.i = srem <2 x i32> %x, <i32 2, i32 2>
   %cmp.i = icmp slt <2 x i32> %rem.i, zeroinitializer
   %add.i = select <2 x i1> %cmp.i, <2 x i32> <i32 2, i32 2>, <2 x i32> zeroinitializer
   %ret.i = add nsw <2 x i32> %add.i, %rem.i
   ret <2 x i32> %ret.i
 }
;
   %cmp.i = icmp slt <2 x i32> %rem.i, zeroinitializer
   %add.i = select <2 x i1> %cmp.i, <2 x i32> <i32 3, i32 3>, <2 x i32> zeroinitializer
   %ret.i = add nsw <2 x i32> %add.i, %rem.i
   ret <2 x i32> %ret.i
 }
 
 define i32 @modulo4(i32 %x) {
 ; CHECK-LABEL: @modulo4(
-; CHECK-NEXT:    [[REM_I:%.*]] = srem i32 [[X:%.*]], 4
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[REM_I]], 4
-; CHECK-NEXT:    [[RET_I:%.*]] = add nsw i32 [[TMP1]], [[REM_I]]
+; CHECK-NEXT:    [[RET_I:%.*]] = and i32 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i32 [[RET_I]]
 ;
   %rem.i = srem i32 %x, 4
   %cmp.i = icmp slt i32 %rem.i, 0
   %add.i = select i1 %cmp.i, i32 4, i32 0
   %ret.i = add nsw i32 %add.i, %rem.i
   ret i32 %ret.i
 }
 
 define <2 x i32> @modulo4_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @modulo4_vec(
-; CHECK-NEXT:    [[REM_I:%.*]] = srem <2 x i32> [[X:%.*]], <i32 4, i32 4>
-; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[REM_I]], <i32 4, i32 4>
-; CHECK-NEXT:    [[RET_I:%.*]] = add nsw <2 x i32> [[TMP1]], [[REM_I]]
+; CHECK-NEXT:    [[RET_I:%.*]] = and <2 x i32> [[X:%.*]], <i32 3, i32 3>
 ; CHECK-NEXT:    ret <2 x i32> [[RET_I]]
 ;
   %rem.i = srem <2 x i32> %x, <i32 4, i32 4>
   %cmp.i = icmp slt <2 x i32> %rem.i, zeroinitializer
   %add.i = select <2 x i1> %cmp.i, <2 x i32> <i32 4, i32 4>, <2 x i32> zeroinitializer
   %ret.i = add nsw <2 x i32> %add.i, %rem.i
   ret <2 x i32> %ret.i
 }
;
   %cmp.i = icmp slt <2 x i32> %rem.i, zeroinitializer
   %add.i = select <2 x i1> %cmp.i, <2 x i32> <i32 7, i32 7>, <2 x i32> zeroinitializer
   %ret.i = add nsw <2 x i32> %add.i, %rem.i
   ret <2 x i32> %ret.i
 }
 
 define i32 @modulo32(i32 %x) {
 ; CHECK-LABEL: @modulo32(
-; CHECK-NEXT:    [[REM_I:%.*]] = srem i32 [[X:%.*]], 32
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[REM_I]], 32
-; CHECK-NEXT:    [[RET_I:%.*]] = add nsw i32 [[TMP1]], [[REM_I]]
+; CHECK-NEXT:    [[RET_I:%.*]] = and i32 [[X:%.*]], 31
 ; CHECK-NEXT:    ret i32 [[RET_I]]
 ;
   %rem.i = srem i32 %x, 32
   %cmp.i = icmp slt i32 %rem.i, 0
   %add.i = select i1 %cmp.i, i32 32, i32 0
   %ret.i = add nsw i32 %add.i, %rem.i
   ret i32 %ret.i
 }
 
 define <2 x i32> @modulo32_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @modulo32_vec(
-; CHECK-NEXT:    [[REM_I:%.*]] = srem <2 x i32> [[X:%.*]], <i32 32, i32 32>
-; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[REM_I]], <i32 32, i32 32>
-; CHECK-NEXT:    [[RET_I:%.*]] = add nsw <2 x i32> [[TMP1]], [[REM_I]]
+; CHECK-NEXT:    [[RET_I:%.*]] = and <2 x i32> [[X:%.*]], <i32 31, i32 31>
 ; CHECK-NEXT:    ret <2 x i32> [[RET_I]]
 ;
   %rem.i = srem <2 x i32> %x, <i32 32, i32 32>
   %cmp.i = icmp slt <2 x i32> %rem.i, zeroinitializer
   %add.i = select <2 x i1> %cmp.i, <2 x i32> <i32 32, i32 32>, <2 x i32> zeroinitializer
   %ret.i = add nsw <2 x i32> %add.i, %rem.i
   ret <2 x i32> %ret.i
 }