InstCombine transform pattern "(A ^ B) | ~(A | B) -> ~(A & B)" added

[Jac1494]

Summary

This patch implements transform for pattern "(A ^ B) | ~(A | B) -> ~(A & B)".

And this pattern is already implemented in gcc.

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2699

m_Specific ?

2703

Does this work for commuted case? @spatel

llvm/test/Transforms/InstCombine/or-and.ll

14

Add vector tests

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2698–2699

Indeed, this doesn't ensure that it's the same A/B each time, so it's a miscompile

This should be

if(match(&I, m_c_Or(m_Xor(m_Value(A), m_Value(B)), m_Not(m_c_Or(m_Deferred(A), m_Deferred(B))))))

[Jac1494]

Addressed @lebedev.ri review comments.Thanks

[Jac1494]

llvm/test/Transforms/InstCombine/or-and.ll

14

Could you please clarify , what you meant by "vector tests"..?

[xbolva00]

llvm/test/Transforms/InstCombine/or-and.ll

14

instead of i32, try use vector type, eg. <4 x i32>

define <4 x i32> @vec( <4 x i32> %0, <4 x i32> %1) {

%3 = xor  <4 x i32> %0, %1
%4 = or  <4 x i32> %0, %1
%5 = xor  <4 x i32> %4, <i32 -1, i32 -1, i32 -1, i32 -1>
%6 = or  <4 x i32> %3, %5
ret  <4 x i32> %6

}

[Jac1494]

Addressed @xbolva00 review comments. Thanks

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2703

Off-topic for this review, but no it doesn't.
If I'm seeing that correctly, there are 16 potential commuted variants, and we only handle 2.
Looks like the motivating cases had a constant operand, so the more general patterns weren't noticed even though the matchers were generalized:
rG42af360

The 'and' variant of this pattern is also missing commutes. We could sprinkle around more "m_c_Xor" and probably get these, but it's not something instcombine can handle in the general case - it's a job for reassociation + CSE, and they seem to work as expected here. So I think the best thing is to add some code comments and/or restrict these to matching a pattern with a constant. Also, add some PhaseOrdering tests for all of those commute tests to make sure they are not escaping through "-O1".

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2703

Passing-by remark:
At some point i'd maybe like to take a more fundamental approach at this,
the rules for these logic ops are well-defined and known,
it's a shame the best we do is just add even more patternmatching..

[Jac1494]

Are you ok with this..?

[Jac1494]

New pattern "~(A | B) | (A ^ B) -> ~(A & B)" and Test cases are added.

[Jac1494]

Removed unnecessary code.

[Jac1494]

Gentle Ping !!

[lebedev.ri]

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

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

         return replaceInstUsesWith(I, V);
       if (Value *V = matchSelectFromAndOr(D, B, A, C))
         return replaceInstUsesWith(I, V);
       if (Value *V = matchSelectFromAndOr(D, B, C, A))
         return replaceInstUsesWith(I, V);
     }
   }
 
+  // (A ^ B) | ~(A | B) -> ~(A & B)
+  if (match(&I, m_c_Or(m_Xor(m_Value(A), m_Value(B)),
+                       m_Not(m_c_Or(m_Deferred(A), m_Deferred(B))))))
+    return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
+
   // (A ^ B) | ((B ^ C) ^ A) -> (A ^ B) | C
   if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
     if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
       return BinaryOperator::CreateOr(Op0, C);
 
   // ((A ^ C) ^ B) | (B ^ A) -> (B ^ A) | C
   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);
 

llvm/test/Transforms/InstCombine/or-and.ll

+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+; (A ^ B) | ~(A | B) --> ~(A & B)
+define i32 @test1(i32 %0, i32 %1) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT: %3 = and i32 %1, %0
+; CHECK-NEXT: %4 = xor i32 %3, -1
+; CHECK-NEXT: ret i32 %4
+  %3 = xor i32 %1, %0
+  %4 = or i32 %1, %0
+  %5 = xor i32 %4, -1
+  %6 = or i32 %3, %5
+  ret i32 %6
+}
+
+; (A ^ B) | ~(A | B) --> ~(A & B)
+define <4 x i32> @test1_vec(<4 x i32> %0, <4 x i32> %1) {
+; CHECK-LABEL: @test1_vec(
+; CHECK-NEXT: %3 = and <4 x i32> %1, %0
+; CHECK-NEXT: %4 = xor <4 x i32> %3, <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT: ret <4 x i32> %4
+  %3 = xor <4 x i32> %1, %0
+  %4 = or <4 x i32> %1, %0
+  %5 = xor <4 x i32> %4, <i32 -1, i32 -1, i32 -1, i32 -1>
+  %6 = or <4 x i32> %3, %5
+  ret <4 x i32> %6
+}
+
+; ~(A | B) | (A ^ B) --> ~(A & B)
+define i32 @test2(i32 %0, i32 %1) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT: %3 = and i32 %1, %0
+; CHECK-NEXT: %4 = xor i32 %3, -1
+; CHECK-NEXT: ret i32 %4
+  %3 = or i32 %1, %0
+  %4 = xor i32 %3, -1
+  %5 = xor i32 %1, %0
+  %6 = or i32 %5, %4
+  ret i32 %6
+}
+
+; ~(A | B) | (A ^ B) --> ~(A & B)
+define <4 x i32> @test2_vec(<4 x i32> %0, <4 x i32> %1) {
+; CHECK-LABEL: @test2_vec(
+; CHECK-NEXT: %3 = and <4 x i32> %1, %0
+; CHECK-NEXT: %4 = xor <4 x i32> %3, <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT: ret <4 x i32> %4
+  %3 = or <4 x i32> %1, %0
+  %4 = xor <4 x i32> %3, <i32 -1, i32 -1, i32 -1, i32 -1>
+  %5 = xor <4 x i32> %1, %0
+  %6 = or <4 x i32> %5, %4
+  ret <4 x i32> %6
+}
+
+; (B ^ A) | ~(B | A) --> ~(A & B)
+define i32 @test3(i32 %0, i32 %1) {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT: %3 = and i32 %1, %0
+; CHECK-NEXT: %4 = xor i32 %3, -1
+; CHECK-NEXT: ret i32 %4
+  %3 = xor i32 %1, %0
+  %4 = or i32 %1, %0
+  %5 = xor i32 %4, -1
+  %6 = or i32 %3, %5
+  ret i32 %6
+}
+
+; (B ^ A) | ~(B | A) --> ~(A & B)
+define <4 x i32> @test3_vec(<4 x i32> %0, <4 x i32> %1) {
+; CHECK-LABEL: @test3_vec(
+; CHECK-NEXT: %3 = and <4 x i32> %1, %0
+; CHECK-NEXT: %4 = xor <4 x i32> %3, <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT: ret <4 x i32> %4
+  %3 = xor <4 x i32> %1, %0
+  %4 = or <4 x i32> %1, %0
+  %5 = xor <4 x i32> %4, <i32 -1, i32 -1, i32 -1, i32 -1>
+  %6 = or <4 x i32> %3, %5
+  ret <4 x i32> %6
+}
+
+; ~(B | A) | (B ^ A) --> ~(A & B)
+define i32 @test4(i32 %0, i32 %1) {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT: %3 = and i32 %1, %0
+; CHECK-NEXT: %4 = xor i32 %3, -1
+; CHECK-NEXT: ret i32 %4
+  %3 = or i32 %1, %0
+  %4 = xor i32 %3, -1
+  %5 = xor i32 %1, %0
+  %6 = or i32 %5, %4
+  ret i32 %6
+}
+
+; ~(B | A) | (B ^ A) --> ~(A & B)
+define <4 x i32> @test4_vec(<4 x i32> %0, <4 x i32> %1) {
+; CHECK-LABEL: @test4_vec(
+; CHECK-NEXT: %3 = and <4 x i32> %1, %0
+; CHECK-NEXT: %4 = xor <4 x i32> %3, <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT: ret <4 x i32> %4
+  %3 = or <4 x i32> %1, %0
+  %4 = xor <4 x i32> %3, <i32 -1, i32 -1, i32 -1, i32 -1>
+  %5 = xor <4 x i32> %1, %0
+  %6 = or <4 x i32> %5, %4
+  ret <4 x i32> %6
+}