[InstCombine] Fuse checks for LHS (~(A | B) & C) | ... NFC.

[spatel]

I think we need to step back before we add a bunch of other matches.
For an expression with and/or/not, there should always be a Demorgan sibling where the and/or are swapped, right?
https://alive2.llvm.org/ce/z/ziSbZa

But we're transforming that into something that ends in 'xor', so it suggests we're missing some other 'xor' fold (and possibly another 'or' fold?).

Can we generalize the existing transforms or at least group them so we don't have a mess of incomplete logic folds?

[rampitec]

In D113132#3112041, @spatel wrote:

I think we need to step back before we add a bunch of other matches.
For an expression with and/or/not, there should always be a Demorgan sibling where the and/or are swapped, right?
https://alive2.llvm.org/ce/z/ziSbZa

But we're transforming that into something that ends in 'xor', so it suggests we're missing some other 'xor' fold (and possibly another 'or' fold?).

Can we generalize the existing transforms or at least group them so we don't have a mess of incomplete logic folds?

What I realized we have couple deficiencies: we do not always reassociate as needed, in particular if a subexpression has multiple uses, and we do not demorgan to increase a number of operations even when that will lead to a further combining. I am not sure if that can be generalized without exploding compile time.

At the same time here I am trying at least to organize folds with a same LHS into a single block (and a single LHS match) which I have not done initially. For the demorganing I also have a subsequent patch (not yet ready, I am still working on tests) to add one more LHS. This LHS is ~(A | B) & C and the demorganed form I am adding is ~A & ~B & C. matchDeMorgansLaws does not convert latter to the former because we have a second use of the inner 'and'. I'd say in general it should not do it for multiply used values, but given the overall cost of the expressions here the benefit outweights it.

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

I see what you mean, yes it looks like yet another missing fold.

[rampitec]

In D113132#3112041, @spatel wrote:

I think we need to step back before we add a bunch of other matches.
For an expression with and/or/not, there should always be a Demorgan sibling where the and/or are swapped, right?
https://alive2.llvm.org/ce/z/ziSbZa

But we're transforming that into something that ends in 'xor', so it suggests we're missing some other 'xor' fold (and possibly another 'or' fold?).

Can we generalize the existing transforms or at least group them so we don't have a mess of incomplete logic folds?

As far as I understand the difference between visitOr and visintAnd in this case: both are calling InstCombinerImpl::SimplifyUsingDistributiveLaws. The problem is:

For 'and' it creates (~(a & c) | b) & (~(a & b)) -> (a & b) ^ (~(a & c) | b). This is beneficial as it is one instruction less.
For 'or' it would create (~(a | c) & b) | (~(a | b)) -> ~((a | b) ^ (~(a | c) & b)) using the same rules, same amount of operations, not beneficial.

The case (a & b) ^ (~(a & c) | b) -> ~(a & (b | c)) can use a separate match in the visitXor but given that extra 'not' operation which is created after swapping 'and' and 'or' operations in the source pattern I do not see how this can be generalized for a case where target is just one operation less and the same complexity if has to be inverted. In turn the pattern (~(a | c) & b) | (~(a | b)) -> ~(a | (b & c)) saves a lot specifically due to its source complexity. I wish we have infrastructure though to express a pattern with swapped 'and' and 'or' in general.

[rampitec]

Quite similarly we are not handling inverted case from D112276: https://alive2.llvm.org/ce/z/ywuzdS
This is done: (c & ~(a | b)) | (b & ~(a | c)) --> ~a & (b ^ c), and this is not: (c | ~(a & b)) & (b | ~(a & c)) --> ~(a & (b ^ c)).

[rampitec]

With all that said it looks like these patterns have to be extracted into a separate function and called for both 'or' and 'and'. But I don't think this shall preclude this NFC and the next D113141 to wait for it, these are mostly orthogonal to me.

[spatel]

In D113132#3117026, @rampitec wrote:

With all that said it looks like these patterns have to be extracted into a separate function and called for both 'or' and 'and'. But I don't think this shall preclude this NFC and the next D113141 to wait for it, these are mostly orthogonal to me.

I agree (just wanted to raise the idea of generalizing if possible) - this one looks like good cleanup / NFC. LGTM.

[rampitec]

In D113132#3118870, @spatel wrote:

In D113132#3117026, @rampitec wrote:

With all that said it looks like these patterns have to be extracted into a separate function and called for both 'or' and 'and'. But I don't think this shall preclude this NFC and the next D113141 to wait for it, these are mostly orthogonal to me.

I agree (just wanted to raise the idea of generalizing if possible) - this one looks like good cleanup / NFC. LGTM.

This is both grouping and generalizing: D113526.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) {
   if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
     if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
       return BinaryOperator::CreateOr(Op1, C);
 
   // ((B | C) & A) | B -> B | (A & C)
   if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
     return BinaryOperator::CreateOr(Op1, Builder.CreateAnd(A, C));
 
-  // (~(A | B) & C) | (~(A | C) & B) --> (B ^ C) & ~A
-  // TODO: One use checks are conservative. We have 7 operations in the source
-  //       expression and 3 in the target. We could allow 3 multiple used values
-  //       in RHS and LHS combined, but there is no common infrastructure to
-  //       conveniently do so no.
+  // (~(A | B) & C) | ... --> ...
+  // TODO: One use checks are conservative. We just need to check that a total
+  //       number of multiple used values does not exceed reduction
+  //       in operations.
   if (match(Op0, m_OneUse(m_c_And(m_OneUse(m_Not(m_Or(m_Value(A), m_Value(B)))),
                                   m_Value(C))))) {
+    // (~(A | B) & C) | (~(A | C) & B) --> (B ^ C) & ~A
     if (match(Op1, m_OneUse(m_c_And(
                        m_OneUse(m_Not(m_c_Or(m_Specific(A), m_Specific(C)))),
                        m_Specific(B))))) {
       Value *Xor = Builder.CreateXor(B, C);
       return BinaryOperator::CreateAnd(Xor, Builder.CreateNot(A));
     }
 
+    // (~(A | B) & C) | (~(B | C) & A) --> (A ^ C) & ~B
     if (match(Op1, m_OneUse(m_c_And(
                        m_OneUse(m_Not(m_c_Or(m_Specific(B), m_Specific(C)))),
                        m_Specific(A))))) {
       Value *Xor = Builder.CreateXor(A, C);
       return BinaryOperator::CreateAnd(Xor, Builder.CreateNot(B));
     }
-  }
 
     // (~(A | B) & C) | ~(A | C) --> ~((B & C) | A)
-  // TODO: One use checks are conservative. We just need to check that a total
-  //       number of multiple used values does not exceed 3.
-  if (match(Op0, m_OneUse(m_c_And(m_OneUse(m_Not(m_Or(m_Value(A), m_Value(B)))),
-                                  m_Value(C))))) {
     if (match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(C)))))
       return BinaryOperator::CreateNot(
           Builder.CreateOr(Builder.CreateAnd(B, C), A));
 
+    // (~(A | B) & C) | ~(B | C) --> ~((A & C) | B)
     if (match(Op1, m_Not(m_c_Or(m_Specific(B), m_Specific(C)))))
       return BinaryOperator::CreateNot(
           Builder.CreateOr(Builder.CreateAnd(A, C), B));
   }
 
   if (Instruction *DeMorgan = matchDeMorgansLaws(I, Builder))
     return DeMorgan;