[InstCombine] (~A | B) & (A ^ B) -> ~A & B

This is part of a set of 2-variable logic optimizations
suggested here:
https://lists.llvm.org/pipermail/llvm-dev/2021-December/154470.html

The 'not' op must not propagate undef elements of a vector,
so this patch creates a new 'full' not, but I am not counting
that as an extra-use restriction because it should get folded
with the existing value by CSE.

https://alive2.llvm.org/ce/z/7v65im

2 files changed, 41 insertions, 32 deletions

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
index ada294122667..fe6a6c1203fd 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -2081,21 +2081,37 @@ Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) {
         if (Op0->hasOneUse() || isFreeToInvert(C, C->hasOneUse()))
           return BinaryOperator::CreateAnd(Op1, Builder.CreateNot(C));
 
-    // (A | B) & ((~A) ^ B) -> (A & B)
-    // (A | B) & (B ^ (~A)) -> (A & B)
-    // (B | A) & ((~A) ^ B) -> (A & B)
-    // (B | A) & (B ^ (~A)) -> (A & B)
+    // (A | B) & (~A ^ B) -> A & B
+    // (A | B) & (B ^ ~A) -> A & B
+    // (B | A) & (~A ^ B) -> A & B
+    // (B | A) & (B ^ ~A) -> A & B
     if (match(Op1, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
         match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
       return BinaryOperator::CreateAnd(A, B);
 
-    // ((~A) ^ B) & (A | B) -> (A & B)
-    // ((~A) ^ B) & (B | A) -> (A & B)
-    // (B ^ (~A)) & (A | B) -> (A & B)
-    // (B ^ (~A)) & (B | A) -> (A & B)
+    // (~A ^ B) & (A | B) -> A & B
+    // (~A ^ B) & (B | A) -> A & B
+    // (B ^ ~A) & (A | B) -> A & B
+    // (B ^ ~A) & (B | A) -> A & B
     if (match(Op0, m_c_Xor(m_Not(m_Value(A)), m_Value(B))) &&
         match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
       return BinaryOperator::CreateAnd(A, B);
+
+    // (~A | B) & (A ^ B) -> ~A & B
+    // (~A | B) & (B ^ A) -> ~A & B
+    // (B | ~A) & (A ^ B) -> ~A & B
+    // (B | ~A) & (B ^ A) -> ~A & B
+    if (match(Op0, m_c_Or(m_Not(m_Value(A)), m_Value(B))) &&
+        match(Op1, m_c_Xor(m_Specific(A), m_Specific(B))))
+      return BinaryOperator::CreateAnd(Builder.CreateNot(A), B);
+
+    // (A ^ B) & (~A | B) -> ~A & B
+    // (B ^ A) & (~A | B) -> ~A & B
+    // (A ^ B) & (B | ~A) -> ~A & B
+    // (B ^ A) & (B | ~A) -> ~A & B
+    if (match(Op1, m_c_Or(m_Not(m_Value(A)), m_Value(B))) &&
+        match(Op0, m_c_Xor(m_Specific(A), m_Specific(B))))
+      return BinaryOperator::CreateAnd(Builder.CreateNot(A), B);
   }
 
   {
diff --git a/llvm/test/Transforms/InstCombine/and-xor-or.ll b/llvm/test/Transforms/InstCombine/and-xor-or.ll
index ccbfcd65c60c..e070f1269d87 100644
--- a/llvm/test/Transforms/InstCombine/and-xor-or.ll
+++ b/llvm/test/Transforms/InstCombine/and-xor-or.ll
@@ -3641,10 +3641,8 @@ define i32 @not_or_or_and_no_and_use8(i32 %a, i32 %b, i32 %c) {
 
 define i4 @and_orn_xor(i4 %a, i4 %b) {
 ; CHECK-LABEL: @and_orn_xor(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i4 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i4 [[A]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i4 [[NOTA]], [[B]]
-; CHECK-NEXT:    [[R:%.*]] = and i4 [[OR]], [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i4 [[A:%.*]], -1
+; CHECK-NEXT:    [[R:%.*]] = and i4 [[TMP1]], [[B:%.*]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %xor = xor i4 %a, %b
@@ -3656,10 +3654,8 @@ define i4 @and_orn_xor(i4 %a, i4 %b) {
 
 define <2 x i4> @and_orn_xor_commute1(<2 x i4> %a, <2 x i4> %b) {
 ; CHECK-LABEL: @and_orn_xor_commute1(
-; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i4> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor <2 x i4> [[A]], <i4 -1, i4 undef>
-; CHECK-NEXT:    [[OR:%.*]] = or <2 x i4> [[NOTA]], [[B]]
-; CHECK-NEXT:    [[R:%.*]] = and <2 x i4> [[XOR]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i4> [[A:%.*]], <i4 -1, i4 -1>
+; CHECK-NEXT:    [[R:%.*]] = and <2 x i4> [[TMP1]], [[B:%.*]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %xor = xor <2 x i4> %a, %b
@@ -3673,9 +3669,8 @@ define i32 @and_orn_xor_commute2(i32 %a, i32 %b) {
 ; CHECK-LABEL: @and_orn_xor_commute2(
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    call void @use(i32 [[XOR]])
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[NOTA]], [[B]]
-; CHECK-NEXT:    [[R:%.*]] = and i32 [[OR]], [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[R:%.*]] = and i32 [[TMP1]], [[B]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %xor = xor i32 %b, %a
@@ -3688,11 +3683,10 @@ define i32 @and_orn_xor_commute2(i32 %a, i32 %b) {
 
 define i32 @and_orn_xor_commute3(i32 %a, i32 %b) {
 ; CHECK-LABEL: @and_orn_xor_commute3(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A:%.*]], -1
 ; CHECK-NEXT:    call void @use(i32 [[NOTA]])
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[NOTA]], [[B]]
-; CHECK-NEXT:    [[R:%.*]] = and i32 [[XOR]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[R:%.*]] = and i32 [[TMP1]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %xor = xor i32 %b, %a
@@ -3707,11 +3701,11 @@ define i32 @and_orn_xor_commute5(i32 %pa, i32 %pb) {
 ; CHECK-LABEL: @and_orn_xor_commute5(
 ; CHECK-NEXT:    [[A:%.*]] = mul i32 [[PA:%.*]], [[PA]]
 ; CHECK-NEXT:    [[B:%.*]] = mul i32 [[PB:%.*]], [[PB]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A]], [[B]]
 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[B]], [[NOTA]]
 ; CHECK-NEXT:    call void @use(i32 [[OR]])
-; CHECK-NEXT:    [[R:%.*]] = and i32 [[OR]], [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[R:%.*]] = and i32 [[B]], [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = mul i32 %pa, %pa
@@ -3732,8 +3726,8 @@ define i32 @and_orn_xor_commute6(i32 %pa, i32 %pb) {
 ; CHECK-NEXT:    call void @use(i32 [[XOR]])
 ; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
 ; CHECK-NEXT:    call void @use(i32 [[NOTA]])
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[B]], [[NOTA]]
-; CHECK-NEXT:    [[R:%.*]] = and i32 [[XOR]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[R:%.*]] = and i32 [[B]], [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = mul i32 %pa, %pa
@@ -3757,7 +3751,8 @@ define i32 @and_orn_xor_commute7(i32 %pa, i32 %pb) {
 ; CHECK-NEXT:    call void @use(i32 [[NOTA]])
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[B]], [[NOTA]]
 ; CHECK-NEXT:    call void @use(i32 [[OR]])
-; CHECK-NEXT:    [[R:%.*]] = and i32 [[OR]], [[XOR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[R:%.*]] = and i32 [[B]], [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = mul i32 %pa, %pa
@@ -3776,10 +3771,8 @@ define i32 @and_orn_xor_commute8(i32 %pa, i32 %pb) {
 ; CHECK-LABEL: @and_orn_xor_commute8(
 ; CHECK-NEXT:    [[A:%.*]] = mul i32 [[PA:%.*]], [[PA]]
 ; CHECK-NEXT:    [[B:%.*]] = mul i32 [[PB:%.*]], [[PB]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[B]], [[A]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[B]], [[NOTA]]
-; CHECK-NEXT:    [[R:%.*]] = and i32 [[XOR]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[R:%.*]] = and i32 [[B]], [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = mul i32 %pa, %pa