[InstSimplify] Fold logic And to Zero

[MehrHeidar]

Summary

Add following fold opportunity:

((A | B) ^ A ) & ((A | B) ^ B) --> 0

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

[rampitec]

llvm/lib/Analysis/InstructionSimplify.cpp

2176

Could you please use X and Y in the comment, same as in the match?

2177

Commuted 'or' does not do anything, it will always match as just 'm_Or'.

2180

You could use 'm_CombineOr' for the LHS to select either deferred X or deferred Y. Then you do not need second expression.

llvm/test/Transforms/InstSimplify/and.ll

168

'or' is more complex than the argument, the xor will be commuted.
See InstCombiner::getComplexity() for the details. Search for "thwart complexity-based canonicalization" in the llvm/test/Transforms/InstCombine directory for test coverage that works around it.

[spatel]

llvm/test/Transforms/InstSimplify/and.ll

168

This is instsimplify, so we don't have to worry about the pass itself altering the input (this is shown in the baseline CHECK lines).

[rampitec]

llvm/test/Transforms/InstSimplify/and.ll

168

Ok, thanks.

[MehrHeidar]

Address review comments.

[MehrHeidar]

llvm/lib/Analysis/InstructionSimplify.cpp

2180

I replaced the comments and changed the usage of A/B with X/Y.
Also, I tried to use the idea for usage of m_CombineOr to remove the second expression.

llvm/test/Transforms/InstSimplify/and.ll

168

I think the test coverage looks fine, based on @spatel comment,

Quoted Text

Right?

168

I think according to the comment the test coverage is fine.

This is instsimplify, so we don't have to worry about the pass itself altering the input (this is shown in the baseline CHECK lines).

Right?

[rampitec]

llvm/lib/Analysis/InstructionSimplify.cpp

2180

Second match shall not use m_CombineOr. Now you would incorrectly match ((X | Y) ^ X ) & ((X | Y) ^ X). Speaking of which it deserves a negative test.

llvm/test/Transforms/InstSimplify/and.ll

168

Yes, but there are 2 more commutes: (a ^ (a | b)) & ((a | b) ^ b) and ((a | b) ^ b) & (a ^ (a | b))

[MehrHeidar]

Add negative test.

[MehrHeidar]

llvm/lib/Analysis/InstructionSimplify.cpp

2180

If I don't put the m_CombineOr on the second match, we won't be able to catch all commutes. I added a negative test now to see it won't incorrectly match your example.

I am not so confident with the current code too and prefer my first version of this patch. What do you think @rampitec ?

[rampitec]

llvm/test/Transforms/InstSimplify/and.ll

187

It shall not be '0'. Comment is misleading.

189

This is not commute. This is a wrong operand.

191

And in fact the test does not catch it. I think 'and' was simply dropped earlier. Maybe a duplicated 'or' will expose it or maybe not.

[rampitec]

llvm/lib/Analysis/InstructionSimplify.cpp

2180

m_CombineOr is not about commute. At the point of second match you already know your X and Y exactly.

[MehrHeidar]

Revert to first version and add two test cases

[MehrHeidar]

llvm/lib/Analysis/InstructionSimplify.cpp

2180

As I mentioned before, not using m_CombineOr doesn't allow me to catch all versions, so I reverted back to first version that I had.

llvm/test/Transforms/InstSimplify/and.ll

168

Right, thanks!
Added two more commutes.

191

Agree! I only added the previous test for the sake of your previous comment, I was not going to commit that=)
Thank you! Changed the code so it's not a concern anymore.

[MehrHeidar]

llvm/lib/Analysis/InstructionSimplify.cpp

2180

@rampitec Would you please take a look at the patch again and check whether it's ok or not?
Thanks

[rampitec]

llvm/lib/Analysis/InstructionSimplify.cpp

2177

I believe commuted Or is not needed here.

2180

I still do not see why m_CombineOr does not work, can you give an example?

[MehrHeidar]

llvm/lib/Analysis/InstructionSimplify.cpp

2180

Sure, if I change the pattern match to be

match(Op0, m_c_Xor(m_c_Or(m_Value(X), m_Value(Y)), m_CombineOr(m_Deferred(X), m_Deferred(Y))) &&
      match(Op1, m_c_Xor(m_c_Or(m_Specific(X), m_Specific(Y)), m_Specific(X)))
     return Constant::getNullValue(Op0->getType());

I can't match this case ((X | Y) ^ X ) & ((X | Y) ^ Y) ;
If I change it to

match(Op0, m_c_Xor(m_c_Or(m_Value(X), m_Value(Y)), m_CombineOr(m_Deferred(X), m_Deferred(Y))) &&
      match(Op1, m_c_Xor(m_c_Or(m_Specific(X), m_Specific(Y)), m_Specific(Y)))
     return Constant::getNullValue(Op0->getType());

I can't match this case ((X | Y) ^ Y ) & ((X | Y) ^ X) ; And, if I use m_CombineOr on second match it's going to incorrectly match ((X | Y) ^ X ) & ((X | Y) ^ X) this pattern.

So, I couldn't fully cover all cases.

[rampitec]

There are still 2 comments around tests.

llvm/lib/Analysis/InstructionSimplify.cpp

2180

OK, I am not sure why but let it be.

[spatel]

The code seems more complicated than necessary (and the tests less thorough than necessary).
We know that the 'or' instruction is a shared op, so let's match that first and then match it again as a specific value?
If I'm seeing it correctly, that means there are 8 potential commutes:

BinaryOperator *Or;
if (match(Op0, m_c_Xor(m_Value(X), m_BinOp(Or))))
  if (match(Or, m_c_Or(m_Specific(X), m_Value(Y))) &&
      match(Op1, m_c_Xor(m_Specific(Or), m_Specific(Y))))
    return Constant::getNullValue(Op0->getType());

[spatel]

In D115755#3204659, @spatel wrote:

The code seems more complicated than necessary (and the tests less thorough than necessary).
We know that the 'or' instruction is a shared op, so let's match that first and then match it again as a specific value?
If I'm seeing it correctly, that means there are 8 potential commutes:

BinaryOperator *Or;
if (match(Op0, m_c_Xor(m_Value(X), m_BinOp(Or))))
  if (match(Or, m_c_Or(m_Specific(X), m_Value(Y))) &&
      match(Op1, m_c_Xor(m_Specific(Or), m_Specific(Y))))
    return Constant::getNullValue(Op0->getType());

On 2nd thought, that might not be complicated enough. :)
I think this could match a "wrong" binop first (for example Y is an add instruction) and then fail to match the pattern (so we could use even more tests...).
We probably need to use m_CombineAnd to get this to accurately match Op0 and capture the 'or' in one shot:

BinaryOperator *Or;
if (match(Op0, m_c_Xor(m_Value(X),
                       m_CombineAnd(m_BinOp(Or),
                                    m_c_Or(m_Deferred(X), m_Value(Y))))) &&
    match(Op1, m_c_Xor(m_Specific(Or), m_Specific(Y))))
  return Constant::getNullValue(Op0->getType());

[MehrHeidar]

In D115755#3204690, @spatel wrote:

In D115755#3204659, @spatel wrote:

The code seems more complicated than necessary (and the tests less thorough than necessary).
We know that the 'or' instruction is a shared op, so let's match that first and then match it again as a specific value?
If I'm seeing it correctly, that means there are 8 potential commutes:

BinaryOperator *Or;
if (match(Op0, m_c_Xor(m_Value(X), m_BinOp(Or))))
  if (match(Or, m_c_Or(m_Specific(X), m_Value(Y))) &&
      match(Op1, m_c_Xor(m_Specific(Or), m_Specific(Y))))
    return Constant::getNullValue(Op0->getType());

On 2nd thought, that might not be complicated enough. :)
I think this could match a "wrong" binop first (for example Y is an add instruction) and then fail to match the pattern (so we could use even more tests...).
We probably need to use m_CombineAnd to get this to accurately match Op0 and capture the 'or' in one shot:

BinaryOperator *Or;
if (match(Op0, m_c_Xor(m_Value(X),
                       m_CombineAnd(m_BinOp(Or),
                                    m_c_Or(m_Deferred(X), m_Value(Y))))) &&
    match(Op1, m_c_Xor(m_Specific(Or), m_Specific(Y))))
  return Constant::getNullValue(Op0->getType());

In D115755#3204690, @spatel wrote:

In D115755#3204659, @spatel wrote:

The code seems more complicated than necessary (and the tests less thorough than necessary).
We know that the 'or' instruction is a shared op, so let's match that first and then match it again as a specific value?
If I'm seeing it correctly, that means there are 8 potential commutes:

BinaryOperator *Or;
if (match(Op0, m_c_Xor(m_Value(X), m_BinOp(Or))))
  if (match(Or, m_c_Or(m_Specific(X), m_Value(Y))) &&
      match(Op1, m_c_Xor(m_Specific(Or), m_Specific(Y))))
    return Constant::getNullValue(Op0->getType());

On 2nd thought, that might not be complicated enough. :)
I think this could match a "wrong" binop first (for example Y is an add instruction) and then fail to match the pattern (so we could use even more tests...).
We probably need to use m_CombineAnd to get this to accurately match Op0 and capture the 'or' in one shot:

BinaryOperator *Or;
if (match(Op0, m_c_Xor(m_Value(X),
                       m_CombineAnd(m_BinOp(Or),
                                    m_c_Or(m_Deferred(X), m_Value(Y))))) &&
    match(Op1, m_c_Xor(m_Specific(Or), m_Specific(Y))))
  return Constant::getNullValue(Op0->getType());

Thank you!
But, this one is not complicated enough to catch this pattern : ) -->(Y ^ (Y | X) ) & ((X | Y) ^ X) --> 0

%or1 = or i32 %y, %x
 %or2 = or i32 %x, %y
 %xor1 = xor i32 %y, %or1
 %xor2 = xor i32 %or2, %x
 %and = and i32 %xor1, %xor2
 ret i32 %and

[spatel]

In D115755#3204851, @MehrHeidar wrote:

But, this one is not complicated enough to catch this pattern : ) -->(Y ^ (Y | X) ) & ((X | Y) ^ X) --> 0

%or1 = or i32 %y, %x
 %or2 = or i32 %x, %y
 %xor1 = xor i32 %y, %or1
 %xor2 = xor i32 %or2, %x
 %and = and i32 %xor1, %xor2
 ret i32 %and

Unless we have some evidence that this pattern can escape a typical -O1 pipeline, I don't think we need to care about it. %or1 and %or2 should be CSE'd independently of instsimplify. In other words, I think the positive tests only need to include a single 'or' instruction. If you want to include a test with different 'or' instructions to show the limits of instsimplify, that's fine.

[MehrHeidar]

Adding more tests and revising the code for pattern match.

[MehrHeidar]

Fix name issue in test cases.

[MehrHeidar]

llvm/lib/Analysis/InstructionSimplify.cpp

2180

Changed the code according to @spatel recommendation.

llvm/test/Transforms/InstSimplify/and.ll

191

These comments were related to a test that I added temporary; so they are not valid anymore.

[MehrHeidar]

In D115755#3204863, @spatel wrote:

In D115755#3204851, @MehrHeidar wrote:

But, this one is not complicated enough to catch this pattern : ) -->(Y ^ (Y | X) ) & ((X | Y) ^ X) --> 0

%or1 = or i32 %y, %x
 %or2 = or i32 %x, %y
 %xor1 = xor i32 %y, %or1
 %xor2 = xor i32 %or2, %x
 %and = and i32 %xor1, %xor2
 ret i32 %and

Unless we have some evidence that this pattern can escape a typical -O1 pipeline, I don't think we need to care about it. %or1 and %or2 should be CSE'd independently of instsimplify. In other words, I think the positive tests only need to include a single 'or' instruction. If you want to include a test with different 'or' instructions to show the limits of instsimplify, that's fine.

Thank you for explaining the reason behind this. I checked the test case and it did get simplified and we ended up with a single or; So I updated the code and test cases.

[spatel]

LGTM - but please wait to push until @rampitec has another look.

[MehrHeidar]

In D115755#3205587, @spatel wrote:

LGTM - but please wait to push until @rampitec has another look.

Sure, Thank you!

[rampitec]

llvm/lib/Analysis/InstructionSimplify.cpp

2179

It may probably fail to match if X is an 'or' itself. Just an independent 'or'. If I am not mistaken in this case it will not be important what to record as X and what as Y for LHS. Looks like yet another limitation. But I guess we have a lot of such cases anyway, so LGTM.

llvm/lib/Analysis/InstructionSimplify.cpp

if (EffWidthY <= ShftCnt) {
       // this AND op.
       if (EffBitsY.isSubsetOf(*Mask) && !EffBitsX.intersects(*Mask))
         return Y;
       if (EffBitsX.isSubsetOf(*Mask) && !EffBitsY.intersects(*Mask))
         return XShifted;
     }
   }
 
+  // ((X | Y) ^ X ) & ((X | Y) ^ Y) --> 0
+  // ((X | Y) ^ Y ) & ((X | Y) ^ X) --> 0
+  BinaryOperator *Or;
+  if (match(Op0, m_c_Xor(m_Value(X),
+                         m_CombineAnd(m_BinOp(Or),
+                                      m_c_Or(m_Deferred(X), m_Value(Y))))) &&
+      match(Op1, m_c_Xor(m_Specific(Or), m_Specific(Y))))
+    return Constant::getNullValue(Op0->getType());
+
   return nullptr;
 }
 
 Value *llvm::SimplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::SimplifyAndInst(Op0, Op1, Q, RecursionLimit);
 }
 
 static Value *simplifyOrLogic(Value *X, Value *Y) {

llvm/test/Transforms/InstSimplify/and.ll

 ;
   %xorz = or i8 %z, %x
   %ynot = xor i8 %y, -1
   %xorynot = or i8 %x, %ynot
   %and = and i8 %xorynot, %xorz
   ret i8 %and
 }
 
-; ((A | B) ^ A ) & ((A | B) ^ B)
+; ((X | Y) ^ X ) & ((X | Y) ^ Y) --> 0
 
 define i8 @or_xor(i8 %x, i8 %y) {
 ; CHECK-LABEL: @or_xor(
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i8 [[OR]], [[X]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i8 [[OR]], [[Y]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[XOR1]], [[XOR2]]
-; CHECK-NEXT:    ret i8 [[AND]]
+; CHECK-NEXT:    ret i8 0
 ;
   %or = or i8 %x, %y
   %xor1 = xor i8 %or, %x
   %xor2 = xor i8 %or, %y
   %and = and i8 %xor1, %xor2
   ret i8 %and
 }
 
-; ((A | B) ^ B ) & ((A | B) ^ A)
+; ((X | Y) ^ Y ) & ((X | Y) ^ X) --> 0
 
 define i8 @or_xor_commute1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @or_xor_commute1(
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i8 [[OR]], [[X]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i8 [[OR]], [[Y]]
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[XOR2]], [[XOR1]]
-; CHECK-NEXT:    ret i8 [[AND]]
+; CHECK-NEXT:    ret i8 0
 ;
   %or = or i8 %x, %y
   %xor1 = xor i8 %or, %x
   %xor2 = xor i8 %or, %y
   %and = and i8 %xor2, %xor1
   ret i8 %and
 }
 
-; (A ^ (A | B) ) & (B ^ (A | B))
+; (X ^ (X | Y) ) & (Y ^ (X | Y)) --> 0
 
 define i71 @or_xor_commute2(i71 %x, i71 %y) {
 ; CHECK-LABEL: @or_xor_commute2(
-; CHECK-NEXT:    [[OR:%.*]] = or i71 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i71 [[X]], [[OR]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i71 [[Y]], [[OR]]
-; CHECK-NEXT:    [[AND:%.*]] = and i71 [[XOR1]], [[XOR2]]
-; CHECK-NEXT:    ret i71 [[AND]]
+; CHECK-NEXT:    ret i71 0
 ;
   %or = or i71 %x, %y
   %xor1 = xor i71 %x, %or
   %xor2 = xor i71 %y, %or
   %and = and i71 %xor1, %xor2
   ret i71 %and
 }
 
-; (B ^ (A | B) ) & (A ^ (A | B))
+; (Y ^ (X | Y) ) & (X ^ (X | Y)) --> 0
 
 define <2 x i64> @or_xor_commute3(<2 x i64> %x, <2 x i64> %y) {
 ; CHECK-LABEL: @or_xor_commute3(
-; CHECK-NEXT:    [[OR:%.*]] = or <2 x i64> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor <2 x i64> [[Y]], [[OR]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor <2 x i64> [[X]], [[OR]]
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i64> [[XOR1]], [[XOR2]]
-; CHECK-NEXT:    ret <2 x i64> [[AND]]
+; CHECK-NEXT:    ret <2 x i64> zeroinitializer
 ;
   %or = or <2 x i64> %x, %y
   %xor1 = xor <2 x i64> %y, %or
   %xor2 = xor <2 x i64> %x, %or
   %and = and <2 x i64> %xor1, %xor2
   ret <2 x i64> %and
 }
+
+; ((X | Y) ^ X ) & (Y ^ (X | Y)) --> 0
+
+define i32 @or_xor_commute4(i32 %x, i32 %y) {
+; CHECK-LABEL: @or_xor_commute4(
+; CHECK-NEXT:    ret i32 0
+;
+  %or = or i32 %x, %y
+  %xor1 = xor i32 %or, %x
+  %xor2 = xor i32 %y, %or
+  %and = and i32 %xor1, %xor2
+  ret i32 %and
+}
+
+; ((X | Y) ^ Y ) & (X ^ (X | Y)) --> 0
+
+define i32 @or_xor_commute5(i32 %x, i32 %y) {
+; CHECK-LABEL: @or_xor_commute5(
+; CHECK-NEXT:    ret i32 0
+;
+  %or = or i32 %x, %y
+  %xor1 = xor i32 %or, %y
+  %xor2 = xor i32 %x, %or
+  %and = and i32 %xor1, %xor2
+  ret i32 %and
+}
+
+; (X ^ (X | Y) ) & ((X | Y) ^ Y) --> 0
+
+define i32 @or_xor_commute6(i32 %x, i32 %y) {
+; CHECK-LABEL: @or_xor_commute6(
+; CHECK-NEXT:    ret i32 0
+;
+  %or = or i32 %x, %y
+  %xor1 = xor i32 %x, %or
+  %xor2 = xor i32 %or, %y
+  %and = and i32 %xor1, %xor2
+  ret i32 %and
+}
+
+; (Y ^ (X | Y) ) & ((X | Y) ^ X) --> 0
+
+define i32 @or_xor_commute7(i32 %x, i32 %y) {
+; CHECK-LABEL: @or_xor_commute7(
+; CHECK-NEXT:    ret i32 0
+;
+  %or = or i32 %x, %y
+  %xor1 = xor i32 %y, %or
+  %xor2 = xor i32 %or, %x
+  %and = and i32 %xor1, %xor2
+  ret i32 %and
+}
+
+; (Y ^ (X | Y) ) & ((X | Y) ^ X) --> 0
+
+define i32 @or_xor_complex_op(i32 %x, i32 %in) {
+; CHECK-LABEL: @or_xor_complex_op(
+; CHECK-NEXT:    ret i32 0
+;
+  %y = or i32 %in, 1
+  %or = or i32 %x, %y
+  %xor1 = xor i32 %y, %or
+  %xor2 = xor i32 %or, %x
+  %and = and i32 %xor1, %xor2
+  ret i32 %and
+}
+
+define i32 @or_xor_limitation(i32 %x, i32 %y) {
+; CHECK-LABEL: @or_xor_limitation(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[Y]], [[OR1]]
+; CHECK-NEXT:    [[XOR2:%.*]] = xor i32 [[OR2]], [[X]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[XOR1]], [[XOR2]]
+; CHECK-NEXT:    ret i32 [[AND]]
+;
+  %or1 = or i32 %y, %x
+  %or2 = or i32 %x, %y
+  %xor1 = xor i32 %y, %or1
+  %xor2 = xor i32 %or2, %x
+  %and = and i32 %xor1, %xor2
+  ret i32 %and
+}