Instcombine ( ( ~A ^ B ) ^ ( A & ~B ) ) to A | ~B

[karthikthecool]

Summary

Hi David,
Another small patch in instcombine to transform ( ( ~A ^ B ) ^ ( A & ~B ) ) to A | ~B .
Please if you could let me know your i/p's on the same.

Proof-
$ cat t.cvc
A, B : BITVECTOR(32);
QUERY BVXOR(BVXOR(~A, B), (A &~B) ) = A|~B;

$ cvc3 t.cvc
Valid.

Thanks
Karthik Bhat

[majnemer]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2546–2569

You have what appear to be eight different patterns you are trying to match but only one test case. Are you sure we need all of them? What happens if you ran a reassociate pass first?

test/Transforms/InstCombine/or-xor.ll

153–161

Please give these variables better names.

[karthikthecool]

Hi David,
Thanks for the review and comments. Yes reassociate does reduce the number of patterns to match. Updated the patch accordingly.
Also updated the test case variable names which was missed out in my previous commit. Please let me know your i/p's on the same.

Thanks once again for your time and support.
Regards
Karthik Bhat

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (Op0I && Op1I) {
     // (A & B) ^ (A ^ B) -> (A | B)
     if (match(Op0I, m_And(m_Value(A), m_Value(B))) &&
         match(Op1I, m_Xor(m_Specific(A), m_Specific(B))))
       return BinaryOperator::CreateOr(A, B);
     // (A ^ B) ^ (A & B) -> (A | B)
     if (match(Op0I, m_Xor(m_Value(A), m_Value(B))) &&
         match(Op1I, m_And(m_Specific(A), m_Specific(B))))
       return BinaryOperator::CreateOr(A, B);
+    // (~A ^ B) ^ (~B & A) -> (A | ~B)
+    if (match(Op0I, m_Xor(m_Not(m_Value(A)), m_Value(B))) &&
+        match(Op1I, m_And(m_Not(m_Specific(B)), m_Specific(A))))
+      return BinaryOperator::CreateOr(A, Builder->CreateNot(B));
+    // (A & ~B) ^ (B ^ ~A) -> (A | ~B)
+    if (match(Op0I, m_And(m_Value(A), m_Not(m_Value(B)))) &&
+        match(Op1I, m_Xor(m_Specific(B), m_Not(m_Specific(A)))))
+      return BinaryOperator::CreateOr(A, Builder->CreateNot(B));
   }
 
   // (A | B)^(~A) -> (A | ~B)
   Value *A = nullptr, *B = nullptr;
   if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
       match(Op1, m_Not(m_Specific(A))))
     return BinaryOperator::CreateOr(A, Builder->CreateNot(B));
 
   // (A & ~B) ^ (~A) -> ~(A & B)
   if (match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
       match(Op1, m_Not(m_Specific(A))))
     return BinaryOperator::CreateNot(Builder->CreateAnd(A, B));
 
   // (icmp1 A, B) ^ (icmp2 A, B) --> (icmp3 A, B)
   if (ICmpInst *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
     if (ICmpInst *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
       if (PredicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
         if (LHS->getOperand(0) == RHS->getOperand(1) &&
             LHS->getOperand(1) == RHS->getOperand(0))
           LHS->swapOperands();
         if (LHS->getOperand(0) == RHS->getOperand(0) &&
             LHS->getOperand(1) == RHS->getOperand(1)) {
           Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1);
           unsigned Code = getICmpCode(LHS) ^ getICmpCode(RHS);
           bool isSigned = LHS->isSigned() || RHS->isSigned();

test/Transforms/InstCombine/or-xor.ll

  ret i32 %and
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT: %and = and i32 %x, %y
 ; CHECK-NEXT: ret i32 %and
 }
 
 ; ((x | y) ^ (x ^ y)) -> (x & y)
 define i32 @test15(i32 %x, i32 %y) {
-  %1 = xor i32 %y, %x
-  %2 = or i32 %y, %x
-  %3 = xor i32 %2, %1
-  ret i32 %3
+  %xor = xor i32 %y, %x
+  %or = or i32 %y, %x
+  %xor1 = xor i32 %or, %xor
+  ret i32 %xor1
 ; CHECK-LABEL: @test15(
-; CHECK-NEXT: %1 = and i32 %y, %x
-; CHECK-NEXT: ret i32 %1
+; CHECK-NEXT: %xor1 = and i32 %y, %x
+; CHECK-NEXT: ret i32 %xor1
 }
 
 ; ((x | ~y) ^ (~x | y)) -> x ^ y
 define i32 @test16(i32 %x, i32 %y) {
   %noty = xor i32 %y, -1
   %notx = xor i32 %x, -1
   %or1 = or i32 %x, %noty
   %or2 = or i32 %notx, %y
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 ; CHECK-LABEL: @test16(
 ; CHECK-NEXT: %xor = xor i32 %x, %y
 ; CHECK-NEXT: ret i32 %xor
 }
+
+; ((~x ^ y) ^ (~y & x)) -> (x | ~y)
+define i32 @test17(i32 %x, i32 %y) {
+  %notx = xor i32 %x, -1
+  %xor1 = xor i32 %notx, %y
+  %noty = xor i32 %y, -1
+  %and = and i32 %noty, %x
+  %xor2 = xor i32 %xor1, %and
+  ret i32 %xor2
+; CHECK-LABEL: @test17(
+; CHECK-NEXT: %1 = xor i32 %y, -1
+; CHECK-NEXT: %xor2 = or i32 %x, %1
+; CHECK-NEXT: ret i32 %xor2
+}