[InstCombine] try to fold the expression "(A & ~B) + B" to "A | B"

[spatel]

Summary

Summary

Since llvm will generate the following ir:

define i32 @and_to_xor1(i32 %0, i32 %1) local_unnamed_addr #0 {
   %3 = shl nsw i32 %0, 1
   %4 = mul nsw i32 %1, %0
   %5 = xor i32 %4, -1
   %6 = and i32 %3, %5
   %7 = add nsw i32 %6, %4
   ret i32 %7
 }

but InstCombine can not simplify this code shape.
So I use this patch to achieve this.

Test Plan:

check-llvm

[lebedev.ri]

The missing fold here is: https://alive2.llvm.org/ce/z/7uIb0B (i.e. it should go into haveNoCommonBitsSet())
And this will automagically fold to or, not xor: https://godbolt.org/z/6svT3vc44

[dongAxis1944]

In D105013#2843794, @lebedev.ri wrote:

The missing fold here is: https://alive2.llvm.org/ce/z/7uIb0B (i.e. it should go into haveNoCommonBitsSet())
And this will automagically fold to or, not xor: https://godbolt.org/z/6svT3vc44

Sorry for my mistake, I just missing the right expression.

[dongAxis1944]

modify code , the original code is wrong

[dongAxis1944]

fix wrong comment

[lebedev.ri]

This pattern (A & ~B) op B should be matched in llvm::haveNoCommonBitsSet() in ValueTracking.cpp.

[dongAxis1944]

add pattern in valuetrack

[spatel]

llvm/test/Transforms/InstCombine/and-to-xor.ll

9

1. The tests should be minimized - only instructions in the most basic pattern need to be here, so something like:

https://alive2.llvm.org/ce/z/NrJRbF

2. Use llvm/utils/update_test_checks.py to auto-generate the CHECK lines.

3. You can probably add these tests in the same file where existing haveNoCommonBitSet patterns are tested (disable the existing transform and see which tests fail).

[dongAxis1944]

@spatel thanks, I update the case, and I prefer use the new file, because the old case might not be clear to find I think.

[spatel]

llvm/test/Analysis/ValueTracking/known-non-common-bits.ll

5 ↗

(On Diff #355120)

There are 4 commuted variations of this pattern, so we should have a test for each. Other transforms will try to normalize the code structure, so the tests will have to overcome that to provide full coverage.

Search for "thwart complexity-based canonicalization" in the test dir for examples.

You may vary the value types across those 4 tests for more coverage as well (try unusual widths or vectors).

5 ↗

(On Diff #355120)

Remove "dso_local" and mangling artifacts from the function name.

It's easier to read the tests if the values are named the same as in the code comment ("A" and "B" in this case).

[spatel]

llvm/test/Analysis/ValueTracking/known-non-common-bits.ll

16 ↗

(On Diff #355120)

If I'm seeing it correctly, this test does not change with this patch. Why is it included?

[dongAxis1944]

remove useless ut

[dongAxis1944]

llvm/test/Analysis/ValueTracking/known-non-common-bits.ll

5 ↗

(On Diff #355120)

thanks., I will update later

[dongAxis1944]

address the comment

[dongAxis1944]

format the patch

[dongAxis1944]

address comment

[dongAxis1944]

gentle ping @spatel @lebedev.ri

[spatel]

In D105013#2866272, @dongAxis1944 wrote:

gentle ping @spatel @lebedev.ri

I don't think you've accounted for commutation in the tests. Did you see the existing test examples that have the comment "thwart complexity-based canonicalization"?
Do you have commit access? If so, please commit the tests only without the code change (and so with baseline CHECK lines), so we can confirm.

llvm/test/Analysis/ValueTracking/known-non-common-bits.ll

4 ↗

(On Diff #355606)

Remove mangling artifacts (_Z11, 1ii) from all function names.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

[spatel]

This is a subset of:
D124763 / 2171a896ed0059e3576fd9c36d0021a3d

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(Op0, m_OneUse(m_ZExt(m_NUWAdd(m_Value(X), m_Constant(NarrowC)))))) {
     Constant *NewC = ConstantExpr::getAdd(WideC, Op1C);
     Value *WideX = Builder.CreateZExt(X, Ty);
     return BinaryOperator::CreateAdd(WideX, NewC);
   }
 
   return nullptr;
 }
 
+// If we get the pattern "(A & ~B) + B", we transfer this pattern to "(A &
+// ~B) | B", And InstCombine will finally fold "(A & ~B) | B" to "A or B"
+Instruction *InstCombinerImpl::foldAddWithOr(BinaryOperator &Add) {
+  Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);
+  if (match(Op0, m_c_And(m_Not(m_Specific(Op1)), m_Value())) ||
+      match(Op1, m_c_And(m_Not(m_Specific(Op0)), m_Value())))
+    return BinaryOperator::CreateOr(Op0, Op1);
+  return nullptr;
+}
+
 Instruction *InstCombinerImpl::foldAddWithConstant(BinaryOperator &Add) {
   Value *Op0 = Add.getOperand(0), *Op1 = Add.getOperand(1);
   Constant *Op1C;
   if (!match(Op1, m_ImmConstant(Op1C)))
     return nullptr;
 
   if (Instruction *NV = foldBinOpIntoSelectOrPhi(Add))
     return NV;
if (Instruction *R = factorizeMathWithShlOps(I, Builder))
     return R;
 
   if (Instruction *X = foldAddWithConstant(I))
     return X;
 
   if (Instruction *X = foldNoWrapAdd(I, Builder))
     return X;
 
+  if (Instruction *X = foldAddWithOr(I))
+    return X;
+
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   Type *Ty = I.getType();
   if (Ty->isIntOrIntVectorTy(1))
     return BinaryOperator::CreateXor(LHS, RHS);
 
   // X + X --> X << 1
   if (LHS == RHS) {
     auto *Shl = BinaryOperator::CreateShl(LHS, ConstantInt::get(Ty, 1));

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   /// This also works for Cast instructions, which obviously do not have a
   /// second operand.
   Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
 
   /// This is a convenience wrapper function for the above two functions.
   Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
 
   Instruction *foldAddWithConstant(BinaryOperator &Add);
+  Instruction *foldAddWithOr(BinaryOperator &Add);
 
   /// Try to rotate an operation below a PHI node, using PHI nodes for
   /// its operands.
   Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
   Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
   Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
   Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
   Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);

llvm/test/Transforms/InstCombine/and-to-xor.ll

+; Try to fold (A & ~B) + B to A | B
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; CHECK: define i32 @and_to_xor1(i32 %0, i32 %1) local_unnamed_addr
+; CHECK-NOT: %{{[0-9]+}} = xor i32 %{{[0-9]+}}, -1
+; CHECK-NOT:  %{{[0-9]+}} = and i32 %{{[0-9]+}}, %{{[0-9]+}}
+; CHECK: %{{[0-9]+}} = or i32 %{{[0-9]+}}, %{{[0-9]+}}
+define i32 @and_to_xor1(i32 %0, i32 %1) local_unnamed_addr #0 {
+  %3 = shl nsw i32 %0, 1
+  %4 = mul nsw i32 %1, %0
+  %5 = xor i32 %4, -1
+  %6 = and i32 %3, %5
+  %7 = add nsw i32 %6, %4
+  ret i32 %7
+}
+
+; CHECK: define i32 @and_to_xor2(i32 %0, i32 %1)
+; CHECK-NOT: %{{[0-9]+}} = xor i32 %{{[0-9]+}}, -1
+; CHECK-NOT:  %{{[0-9]+}} = and i32 %{{[0-9]+}}, %{{[0-9]+}}
+; CHECK: %{{[0-9]+}} = or i32 %{{[0-9]+}}, %{{[0-9]+}}
+define i32 @and_to_xor2(i32 %0, i32 %1) local_unnamed_addr #0 {
+  %3 = shl nsw i32 %0, 1
+  %4 = mul nsw i32 %1, %0
+  %5 = xor i32 %4, -1
+  %6 = and i32 %3, %5
+  %7 = add nsw i32 %4, %6
+  ret i32 %7
+}