InstCombine ((x | ~y) ^ (~x ^ y)) to (x & ~y)

[mayurp]

Summary

Hi David,

Another small patch in instcombine. Can you please review the patch.

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

Thanks,
Mayur

[asl]

I'm really curios - how often such patterns happen in real world code?

[mayurp]

Hi Anton,

I think we should not miss out on any optimization opportunity in general. The number of instructions saved in this case is a big win wherever such pattern occurs.
In general most of the patterns handled in Instcombine module are not very commonly used, but still it is better to handle them.

Saying that, I strongly believe that there should be a general approach to combining instructions. A discussion is going on regarding the same at:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-August/075532.html

Thanks,
Mayur

[majnemer]

This can be generalized:

(X | (Y ^ Z)) ^ ((X ^ Z) ^ Y) -> X & (Y ^ Z)

[mayurp]

Hi David,

Updated the patch as per your comments to make it more generalized. Please help in reviewing the same.

Thanks,
Mayur

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 ^ C)) ^ ((A ^ C) ^ B) -> A & (B ^ C)
+    if (match(Op0I, m_Or(m_Value(A), m_Xor(m_Value(B), m_Value(C)))) &&
+        match(Op1I, m_Xor(m_Xor(m_Specific(A), m_Specific(C)), m_Specific(B))))
+      return BinaryOperator::CreateAnd(A, Builder->CreateXor(B,C));
+    // ( (B ^ C) | A ) ^ ((A ^ C) ^ B) -> A & (B ^ C)
+    if (match(Op0I, m_Or(m_Xor(m_Value(B), m_Value(C)), m_Value(A))) &&
+        match(Op1I, m_Xor( m_Xor(m_Specific(A), m_Specific(C)), m_Specific(B))))
+      return BinaryOperator::CreateAnd(A, Builder->CreateXor(B,C));
+    // ((A ^ B) ^ C) ^ (A | (B ^ C))   -> A & (B ^ C)
+    if (match(Op0I, m_Xor(m_Xor(m_Value(A), m_Value(B)), m_Value(C))) &&
+        match(Op1I, m_Or(m_Specific(A), m_Xor(m_Specific(B), m_Specific(C)))))
+      return BinaryOperator::CreateAnd(A, Builder->CreateXor(B,C));
+    // ((A ^ B) ^ C) ^ (B ^ C) | A )) -> A & (B ^ C)
+    if (match(Op0I, m_Xor(m_Xor(m_Value(A), m_Value(B)), m_Value(C))) &&
+        match(Op1I, m_Or(m_Xor(m_Specific(B), m_Specific(C)), m_Specific(A))))
+      return BinaryOperator::CreateAnd(A, Builder->CreateXor(B,C));
   }
 
   // (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));
 

test/Transforms/InstCombine/or-xor.ll

 
 define i32 @test18(i32 %a, i32 %b) {
   %or = xor i32 %a, %b
   %and1 = and i32 %or, 1
   %and2 = and i32 %b, -2
   %xor = or i32 %and1, %and2
   ret i32 %xor
 }
+
+; (x | (y ^ z)) ^ ((x ^ z) ^ y) -> x & (y ^ z)
+define i32 @test19(i32 %x, i32 %y, i32 %z) {
+  %xor1 = xor i32 %y, %z
+  %or = or i32 %x, %xor1
+  %xor2 = xor i32 %x, %z
+  %xor3 = xor i32 %xor2, %y
+  %res = xor i32 %or, %xor3
+  ret i32 %res
+; CHECK-LABEL: @test19(
+; CHECK-NEXT: %1 = xor i32 %y, %z
+; CHECK-NEXT: %res = and i32 %1, %x
+; CHECK-NEXT: ret i32 %res
+}
+
+; ((x | ~y) ^ (~x ^ y)) -> (x & ~y)
+define i32 @test20(i32 %x, i32 %y) {
+  %noty = xor i32 %y, -1
+  %or = or i32 %x, %noty
+  %notx = xor i32 %x, -1
+  %xor = xor i32 %notx, %y
+  %res = xor i32 %or, %xor
+  ret i32 %res
+; CHECK-LABEL: @test20(
+; CHECK-NEXT: %1 = xor i32 %y, -1
+; CHECK-NEXT: %res = and i32 %x, %1
+; CHECK-NEXT: ret i32 %res
+}