Added InstCombine transform for pattern "(A & B) ^ (A ^ B) -> (A | B)"

[suyog]

Summary

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

Please help in reviewing the same.

Thanks,
Suyog

[silvas]

Hi Suyog,

In the future, if it's not too much trouble, could you please include a link like http://rise4fun.com/Z3/Evslo along with any identities just to verify that no errors are slipping through? It's an easy way to save the reviewer some head scratching and increase confidence in correctness.

Z3 is pretty easy to use and has a good tutorial http://rise4fun.com/Z3/tutorial/guide . You don't need to read all of it, just skip to the "bit vectors" section for the list of operations and just reuse the boilerplate in my link. Basically, if your identity is "foo == bar", then what you ask Z3 to do is check that the statement "foo != bar" is unsatisfiable. The online Z3 "permalink" feature is what gives you a URL like the above.

(The lisp syntax is kind of annoying, but it's workable; they used to have a Python version that was more syntactically convenient, but I can't seem to find it)

[suyog]

Accepting revision as per review :

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140721/226835.html

[suyog]

Closed by commit rL213677 (authored by @suyog).

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op0I, m_And(m_Value(A), m_Value(B))) &&
         return BinaryOperator::CreateXor(A, B);
     }
     // (A | B)^(A & B) -> A ^ B
     if (match(Op0I, m_Or(m_Value(A), m_Value(B))) &&
         match(Op1I, m_And(m_Value(C), m_Value(D)))) {
       if ((A == C && B == D) || (A == D && B == C))
         return BinaryOperator::CreateXor(A, B);
     }
+    // (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);
   }
 
   // (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))

test/Transforms/InstCombine/xor2.ll

define i32 @test6(i32 %x) {
   %xor = xor i32 %x, 1234
   %shr = lshr i32 %xor, 16
   %add = add i32 %shr, %xor
   ret i32 %add
 ; CHECK-LABEL: @test6(
 ; CHECK: lshr i32 %x, 16
 ; CHECK: ret
 }
+
+; (A & B) ^ (A ^ B) -> (A | B)
+define i32 @test9(i32 %b, i32 %c) {
+  %and = and i32 %b, %c
+  %xor = xor i32 %b, %c
+  %xor2 = xor i32 %and, %xor
+  ret i32 %xor2
+; CHECK-LABEL: @test9(
+; CHECK-NEXT: %xor2 = or i32 %b, %c
+}
+
+; (A ^ B) ^ (A & B) -> (A | B)
+define i32 @test10(i32 %b, i32 %c) {
+  %xor = xor i32 %b, %c
+  %and = and i32 %b, %c
+  %xor2 = xor i32 %xor, %and
+  ret i32 %xor2
+; CHECK-LABEL: @test10(
+; CHECK-NEXT: %xor2 = or i32 %b, %c
+}