[InstCombine] fold `sub + and` pattern with specific const value

[bcl5980]

Summary

C1 - ((C3 - X) & C2) --> (X & C2) + (C1 - (C2 & C3))
when:

(C3 - ((C2 & C3) - 1)) is pow2 &&
((C2 + C3) & ((C2 & C3) - 1)) == ((C2 & C3) - 1) && 
C2 is negative pow2 || (C3 - X) is nuw

https://alive2.llvm.org/ce/z/HXQJV-

Fix: #58523

[bcl5980]

Will precommit test after review.

[bcl5980]

the alive2 proof is not match the code. Need to fix.

[bcl5980]

Only detect APInt because the condition is too complicated.

[RKSimon]

vector test?

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2054

use C2AddC3 .isSubsetOf(CMinus1)?

llvm/test/Transforms/InstCombine/sub.ll

2122

Add a comment describing the general fold

[bcl5980]

Address comments by @RKSimon

[spatel]

I don't know if it would have any effect on this patch, but we seem to be missing a constant-shrinking (DemandedBits) opportunity for sub nuw:
https://alive2.llvm.org/ce/z/7Lb_Dy

We can clear high-bits of the mask constant based on the highest bit set in the subtract constant.

[bcl5980]

In D136582#3880098, @spatel wrote:

I don't know if it would have any effect on this patch, but we seem to be missing a constant-shrinking (DemandedBits) opportunity for sub nuw:
https://alive2.llvm.org/ce/z/7Lb_Dy

We can clear high-bits of the mask constant based on the highest bit set in the subtract constant.

Yeah, I also find the shrinking. And that part has no effect on this patch. Condition 1/3 don't care any high-bits for C2.

[spatel]

In D136582#3880779, @bcl5980 wrote:

In D136582#3880098, @spatel wrote:

I don't know if it would have any effect on this patch, but we seem to be missing a constant-shrinking (DemandedBits) opportunity for sub nuw:
https://alive2.llvm.org/ce/z/7Lb_Dy

We can clear high-bits of the mask constant based on the highest bit set in the subtract constant.

Yeah, I also find the shrinking. And that part has no effect on this patch. Condition 1/3 don't care any high-bits for C2.

This patch still seems too specific.
Can we generalize this as a mask-of-subtract canonicalization instead - https://alive2.llvm.org/ce/z/qz_KmH ?
If we do that, an existing fold for subtract should reduce the motivating example.

[bcl5980]

In D136582#3882251, @spatel wrote:

In D136582#3880779, @bcl5980 wrote:

In D136582#3880098, @spatel wrote:

I don't know if it would have any effect on this patch, but we seem to be missing a constant-shrinking (DemandedBits) opportunity for sub nuw:
https://alive2.llvm.org/ce/z/7Lb_Dy

We can clear high-bits of the mask constant based on the highest bit set in the subtract constant.

Yeah, I also find the shrinking. And that part has no effect on this patch. Condition 1/3 don't care any high-bits for C2.

This patch still seems too specific.
Can we generalize this as a mask-of-subtract canonicalization instead - https://alive2.llvm.org/ce/z/qz_KmH ?
If we do that, an existing fold for subtract should reduce the motivating example.

Thanks for the idea. It is a more clean and simplier way.
I only have a little concern about the subtract's combination after the canonicalization. For example:
https://alive2.llvm.org/ce/z/i5Qk9-
It will break exist and combination. Generally I think subtract's combination should be less than and.

[spatel]

In D136582#3882497, @bcl5980 wrote:

In D136582#3882251, @spatel wrote:

In D136582#3880779, @bcl5980 wrote:

In D136582#3880098, @spatel wrote:

I don't know if it would have any effect on this patch, but we seem to be missing a constant-shrinking (DemandedBits) opportunity for sub nuw:
https://alive2.llvm.org/ce/z/7Lb_Dy

We can clear high-bits of the mask constant based on the highest bit set in the subtract constant.

Yeah, I also find the shrinking. And that part has no effect on this patch. Condition 1/3 don't care any high-bits for C2.

This patch still seems too specific.
Can we generalize this as a mask-of-subtract canonicalization instead - https://alive2.llvm.org/ce/z/qz_KmH ?
If we do that, an existing fold for subtract should reduce the motivating example.

Thanks for the idea. It is a more clean and simplier way.
I only have a little concern about the subtract's combination after the canonicalization. For example:
https://alive2.llvm.org/ce/z/i5Qk9-
It will break exist and combination. Generally I think subtract's combination should be less than and.

Good point. It seems we are missing some family of canonicalizations with subtract-from-constant and bitwise logic. There may be some common pre-condition with a low-bit mask and any logic op?
https://alive2.llvm.org/ce/z/qrsyWe

[bcl5980]

In D136582#3882587, @spatel wrote:

In D136582#3882497, @bcl5980 wrote:

In D136582#3882251, @spatel wrote:

In D136582#3880779, @bcl5980 wrote:

In D136582#3880098, @spatel wrote:

I don't know if it would have any effect on this patch, but we seem to be missing a constant-shrinking (DemandedBits) opportunity for sub nuw:
https://alive2.llvm.org/ce/z/7Lb_Dy

We can clear high-bits of the mask constant based on the highest bit set in the subtract constant.

Yeah, I also find the shrinking. And that part has no effect on this patch. Condition 1/3 don't care any high-bits for C2.

This patch still seems too specific.
Can we generalize this as a mask-of-subtract canonicalization instead - https://alive2.llvm.org/ce/z/qz_KmH ?
If we do that, an existing fold for subtract should reduce the motivating example.

Thanks for the idea. It is a more clean and simplier way.
I only have a little concern about the subtract's combination after the canonicalization. For example:
https://alive2.llvm.org/ce/z/i5Qk9-
It will break exist and combination. Generally I think subtract's combination should be less than and.

Good point. It seems we are missing some family of canonicalizations with subtract-from-constant and bitwise logic. There may be some common pre-condition with a low-bit mask and any logic op?
https://alive2.llvm.org/ce/z/qrsyWe

The pattern is still complicate:
https://alive2.llvm.org/ce/z/Mx5tNC

And to avoid potential regression I prefer this pattern:
https://alive2.llvm.org/ce/z/TdYIkn

[spatel]

In D136582#3884899, @bcl5980 wrote:

In D136582#3882587, @spatel wrote:

In D136582#3882497, @bcl5980 wrote:

In D136582#3882251, @spatel wrote:

In D136582#3880779, @bcl5980 wrote:

In D136582#3880098, @spatel wrote:

I don't know if it would have any effect on this patch, but we seem to be missing a constant-shrinking (DemandedBits) opportunity for sub nuw:
https://alive2.llvm.org/ce/z/7Lb_Dy

We can clear high-bits of the mask constant based on the highest bit set in the subtract constant.

Yeah, I also find the shrinking. And that part has no effect on this patch. Condition 1/3 don't care any high-bits for C2.

This patch still seems too specific.
Can we generalize this as a mask-of-subtract canonicalization instead - https://alive2.llvm.org/ce/z/qz_KmH ?
If we do that, an existing fold for subtract should reduce the motivating example.

Thanks for the idea. It is a more clean and simplier way.
I only have a little concern about the subtract's combination after the canonicalization. For example:
https://alive2.llvm.org/ce/z/i5Qk9-
It will break exist and combination. Generally I think subtract's combination should be less than and.

Good point. It seems we are missing some family of canonicalizations with subtract-from-constant and bitwise logic. There may be some common pre-condition with a low-bit mask and any logic op?
https://alive2.llvm.org/ce/z/qrsyWe

The pattern is still complicate:
https://alive2.llvm.org/ce/z/Mx5tNC

I think this can be reduced to low-bit mask constraints:
https://alive2.llvm.org/ce/z/dJqQHN
I also noticed a deficiency in demanded bits for sub. I don't know if that would cause trouble for this patch, but we probably want to do it to be consistent with add:
D136788

[bcl5980]

In D136582#3886568, @spatel wrote:

In D136582#3884899, @bcl5980 wrote:

In D136582#3882587, @spatel wrote:

In D136582#3882497, @bcl5980 wrote:

In D136582#3882251, @spatel wrote:

In D136582#3880779, @bcl5980 wrote:

In D136582#3880098, @spatel wrote:

I don't know if it would have any effect on this patch, but we seem to be missing a constant-shrinking (DemandedBits) opportunity for sub nuw:
https://alive2.llvm.org/ce/z/7Lb_Dy

We can clear high-bits of the mask constant based on the highest bit set in the subtract constant.

Yeah, I also find the shrinking. And that part has no effect on this patch. Condition 1/3 don't care any high-bits for C2.

This patch still seems too specific.
Can we generalize this as a mask-of-subtract canonicalization instead - https://alive2.llvm.org/ce/z/qz_KmH ?
If we do that, an existing fold for subtract should reduce the motivating example.

Thanks for the idea. It is a more clean and simplier way.
I only have a little concern about the subtract's combination after the canonicalization. For example:
https://alive2.llvm.org/ce/z/i5Qk9-
It will break exist and combination. Generally I think subtract's combination should be less than and.

Good point. It seems we are missing some family of canonicalizations with subtract-from-constant and bitwise logic. There may be some common pre-condition with a low-bit mask and any logic op?
https://alive2.llvm.org/ce/z/qrsyWe

The pattern is still complicate:
https://alive2.llvm.org/ce/z/Mx5tNC

I think this can be reduced to low-bit mask constraints:
https://alive2.llvm.org/ce/z/dJqQHN
I also noticed a deficiency in demanded bits for sub. I don't know if that would cause trouble for this patch, but we probably want to do it to be consistent with add:
D136788

Yeah, only consider sub without nuw can be this pattern. But if we consider nuw, we still need to use the condition I send before I think.

[spatel]

Please pre-commit the baseline tests, so we will see the diffs here.

I'm still not sure if we want to add some more general transforms in addition to or instead of this fold.

Should we have the subtract version of this patch for consistency?
D130080

In case it was not clear, that was a transform I suggested earlier. Depending where it is added, I think the patch would look something like this:

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
index c3dabc2d4a07..e7ae1a9be39c 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -2035,6 +2035,18 @@ Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) {
                                 ConstantInt::getNullValue(Ty));
     }
 
+    // If all bits affected by a sub are included in a high-bit-mask, do the
+    // mask op before the adjusted sub. Example:
+    // (0x0f - X) & 0xf8 --> 0x08 - (X & 0xf8)
+    const APInt *SubC;
+    if (C->isNegatedPowerOf2() &&
+        match(Op0, m_OneUse(m_Sub(m_APInt(SubC), m_Value(X)))) &&
+        (~*C).isSubsetOf(*SubC)) {
+      Value *NewAnd = Builder.CreateAnd(X, *C);
+      Constant *NewSubC = ConstantInt::get(Ty, *C & *SubC);
+      return BinaryOperator::CreateSub(NewSubC, NewAnd);
+    }
+
     Constant *C1, *C2;
     const APInt *C3 = C;
     Value *X;

I didn't see any immediate failures in regression tests with that patch applied.

[bcl5980]

In D136582#3896480, @spatel wrote:

Please pre-commit the baseline tests, so we will see the diffs here.

I'm still not sure if we want to add some more general transforms in addition to or instead of this fold.

Should we have the subtract version of this patch for consistency?
D130080

In case it was not clear, that was a transform I suggested earlier. Depending where it is added, I think the patch would look something like this:

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
index c3dabc2d4a07..e7ae1a9be39c 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -2035,6 +2035,18 @@ Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) {
                                 ConstantInt::getNullValue(Ty));
     }
 
+    // If all bits affected by a sub are included in a high-bit-mask, do the
+    // mask op before the adjusted sub. Example:
+    // (0x0f - X) & 0xf8 --> 0x08 - (X & 0xf8)
+    const APInt *SubC;
+    if (C->isNegatedPowerOf2() &&
+        match(Op0, m_OneUse(m_Sub(m_APInt(SubC), m_Value(X)))) &&
+        (~*C).isSubsetOf(*SubC)) {
+      Value *NewAnd = Builder.CreateAnd(X, *C);
+      Constant *NewSubC = ConstantInt::get(Ty, *C & *SubC);
+      return BinaryOperator::CreateSub(NewSubC, NewAnd);
+    }
+
     Constant *C1, *C2;
     const APInt *C3 = C;
     Value *X;

I didn't see any immediate failures in regression tests with that patch applied.

I guess D130080's motivation is AMDGPU's load/store instruction have very strong address pattern that they prefer add close to load/store.
But for the sub, as far as I know they can't get any benifit from it. Actually, I think most of the backend can't support sub in load/store.
I prefer to keep sub+and except we make sure the sub can be optimized.

I update the code you paste in https://reviews.llvm.org/D136582?id=472123. This code doesn't consider the nuw flag, so it misses some cases. And if we add constant shrink for this case later, it works even worse I think.

[bcl5980]

Update based on @spatel 's suggestion.
I haven't update the summary for now because we can't make sure this patch is the final solution or not.

[bcl5980]

origin version rebased.

[spatel]

I still think this is a very specific/narrow transform, but if this is important to optimize, then I won't hold it up. The code seems correct.
See inline comments for a few nits.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2045

Should this be:

// (C3 - (C2 & C3) - 1) is pow2

llvm/test/Transforms/InstCombine/sub.ll

2231–2232

Remove TODO comment

2247–2248

Remove TODO comment

[bcl5980]

In D136582#3905964, @spatel wrote:

I still think this is a very specific/narrow transform, but if this is important to optimize, then I won't hold it up. The code seems correct.
See inline comments for a few nits.

I agree that the code is very limited, but I also worry about the solution canonicalize sub + and to and + sub.
If we find more cases get benefit from general canonicalization in the future, we can change to the canonicalization.

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2045

If we want to match the alive2 proof, it should be:

(C3 - ((C2 & C3) - 1)) is pow2

and it is the same to

(C3 - (C2 & C3) + 1) is pow2

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (Constant *C = dyn_cast<Constant>(Op0)) {
     Constant *C2;
 
     // C-(C2-X) --> X+(C-C2)
     if (match(Op1, m_Sub(m_ImmConstant(C2), m_Value(X))))
       return BinaryOperator::CreateAdd(X, ConstantExpr::getSub(C, C2));
   }
 
   const APInt *Op0C;
-  if (match(Op0, m_APInt(Op0C)) && Op0C->isMask()) {
+  if (match(Op0, m_APInt(Op0C))) {
+    if (Op0C->isMask()) {
       // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known
       // zero.
       KnownBits RHSKnown = computeKnownBits(Op1, 0, &I);
       if ((*Op0C | RHSKnown.Zero).isAllOnes())
         return BinaryOperator::CreateXor(Op1, Op0);
     }
 
+    // C - ((C3 -nuw X) & C2) --> (C - (C2 & C3)) + (X & C2) when:
+    // (C3 - ((C2 & C3) - 1)) is pow2
+    // ((C2 + C3) & ((C2 & C3) - 1)) == ((C2 & C3) - 1)
+    // C2 is negative pow2 || sub nuw
+    const APInt *C2, *C3;
+    BinaryOperator *InnerSub;
+    if (match(Op1, m_OneUse(m_And(m_BinOp(InnerSub), m_APInt(C2)))) &&
+        match(InnerSub, m_Sub(m_APInt(C3), m_Value(X))) &&
+        (InnerSub->hasNoUnsignedWrap() || C2->isNegatedPowerOf2())) {
+      APInt C2AndC3 = *C2 & *C3;
+      APInt C2AndC3Minus1 = C2AndC3 - 1;
+      APInt C2AddC3 = *C2 + *C3;
+      if ((*C3 - C2AndC3Minus1).isPowerOf2() &&
+          C2AndC3Minus1.isSubsetOf(C2AddC3)) {
+        Value *And = Builder.CreateAnd(X, ConstantInt::get(I.getType(), *C2));
+        return BinaryOperator::CreateAdd(
+            And, ConstantInt::get(I.getType(), *Op0C - C2AndC3));
+      }
+    }
+  }
+
   {
     Value *Y;
     // X-(X+Y) == -Y    X-(Y+X) == -Y
     if (match(Op1, m_c_Add(m_Specific(Op0), m_Value(Y))))
       return BinaryOperator::CreateNeg(Y);
 
     // (X-Y)-X == -Y
     if (match(Op0, m_Sub(m_Specific(Op1), m_Value(Y))))

llvm/test/Transforms/InstCombine/sub.ll

 ;
   %m = and i8 %x, -64 ; 0xC0
   %a = sub i8 %m, %y
   call void @use8(i8 %a)
   %s = sub i8 %a, %z
   %r = shl i8 %s, 2
   ret i8 %r
 }
 
 ; sub becomes negate and combines with shl
 
 define i8 @shrink_sub_from_constant_lowbits(i8 %x) {
 ; CHECK-LABEL: @shrink_sub_from_constant_lowbits(
 ; CHECK-NEXT:    [[X000_NEG:%.*]] = mul i8 [[X:%.*]], -8
 ; CHECK-NEXT:    ret i8 [[X000_NEG]]
 ;
   %x000 = shl i8 %x, 3   ; 3 low bits are known zero

 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %x0000 = shl i8 %x, 4   ; 4 low bits are known zero
   %y00000 = and i8 %y, -32
   %sub = sub i8 %y00000, %x0000
   %r = lshr i8 %sub, 4    ; 4 low bits are not demanded
   ret i8 %r
 }
 
-; TODO:
 ; C - ((C3 - X) & C2) --> (C - (C2 & C3)) + (X & C2) when:
-; (C3 - (C2 & C3) + 1) is pow2
+; (C3 - ((C2 & C3) - 1)) is pow2
 ; ((C2 + C3) & ((C2 & C3) - 1)) == ((C2 & C3) - 1)
 ; C2 is negative pow2
 define i10 @sub_to_and_nuw(i10 %x) {
 ; CHECK-LABEL: @sub_to_and_nuw(
-; CHECK-NEXT:    [[SUB:%.*]] = sub nuw i10 71, [[X:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i10 [[SUB]], 120
-; CHECK-NEXT:    [[R:%.*]] = sub nuw nsw i10 443, [[AND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i10 [[X:%.*]], 120
+; CHECK-NEXT:    [[R:%.*]] = add nuw nsw i10 [[TMP1]], 379
 ; CHECK-NEXT:    ret i10 [[R]]
 ;
   %sub = sub nuw i10 71, %x
   %and = and i10 %sub, 120
   %r = sub i10 443, %and
   ret i10 %r
 }
 
-; TODO:
 ; C - ((C3 -nuw X) & C2) --> (C - (C2 & C3)) + (X & C2) when:
-; (C3 - (C2 & C3) + 1) is pow2
+; (C3 - ((C2 & C3) - 1)) is pow2
 ; ((C2 + C3) & ((C2 & C3) - 1)) == ((C2 & C3) - 1)
 define i10 @sub_to_and_negpow2(i10 %x) {
 ; CHECK-LABEL: @sub_to_and_negpow2(
-; CHECK-NEXT:    [[SUB:%.*]] = sub i10 71, [[X:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and i10 [[SUB]], -8
-; CHECK-NEXT:    [[R:%.*]] = sub i10 33, [[AND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i10 [[X:%.*]], -8
+; CHECK-NEXT:    [[R:%.*]] = add i10 [[TMP1]], -31
 ; CHECK-NEXT:    ret i10 [[R]]
 ;
   %sub = sub i10 71, %x
   %and = and i10 %sub, -8
   %r = sub i10 33, %and
   ret i10 %r
 }
 
;
   %r = sub i10 64, %and
   call void @use10(i10 %and)
   ret i10 %r
 }
 
 
 define <2 x i8> @sub_to_and_vector1(<2 x i8> %x) {
 ; CHECK-LABEL: @sub_to_and_vector1(
-; CHECK-NEXT:    [[SUB:%.*]] = sub nuw <2 x i8> <i8 71, i8 71>, [[X:%.*]]
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i8> [[SUB]], <i8 120, i8 120>
-; CHECK-NEXT:    [[R:%.*]] = sub nsw <2 x i8> <i8 55, i8 55>, [[AND]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> [[X:%.*]], <i8 120, i8 120>
+; CHECK-NEXT:    [[R:%.*]] = add nsw <2 x i8> [[TMP1]], <i8 -9, i8 -9>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %sub = sub nuw <2 x i8> <i8 71, i8 71>, %x
   %and = and <2 x i8> %sub, <i8 120, i8 120>
   %r = sub <2 x i8>  <i8 55, i8 55>, %and
   ret <2 x i8> %r
 }