Added InstCombine Transformation for (A^B)^((~A)&B) -> A&(~B)

[ankur29.garg]

Summary

Hi everyone,

This patch implements the transformation (A^B)^((~A)&B) -> A&(~B)

Please help in reviewing it.

Z3 Link: http://rise4fun.com/Z3/jegC

Thanks,
Ankur Garg

[majnemer]

This can be generalized.

(A ^ B) ^ ((A ^ C) & B) -> C ^ (B | (A ^ C)

[ankur29.garg]

Hi David,
Thank you for the comments.
I have made the changes as you suggested. Please review the updated revision.

Updated Transformation:
(A ^ B) ^ ((A ^ C) & B) -> (C ^ (B | (A ^ C))

New Z3 Link: http://rise4fun.com/Z3/KmnV7

Thanks,
Ankur Garg

[asl]

Again, it will be really nice if you'll provide examples in the
real-world programs which would require and benefit such matching
patterns.

[ankur29.garg]

Hi Anton,
Thank You for reviewing the patch.
The simplified expression reduces the number of operations required for the calculation of the original expression from 4 to 3. Just like most of the other transformations, it will reduce the computation. I am not exactly sure what you meant by real world examples. Can you please clarify ?

Thanks.
Regards,
Ankur Garg

[asl]

There are infinitely many expressions which one can form using logical
operations. And for given expression there surely is the minimal form
which one can use to compute.The question is how often such
transformation occur so it's profitable to explicitly match in
optimizer.

Will you please provide some numbers, for example how often such
pattern occurs in LLVM testsuite and in SPEC?

[ankur29.garg]

Hi Anton,
I understood what you are asking. I was also thinking the same thing when I was browsing through other patches. I do think there should be a general method to include simplification of all such logical expressions' simplifications. While I was going through other patches, I came across this, http://reviews.llvm.org/D4940 . Also, I was curious as to how gcc includes such expression simplifications.

Regards,
Ankur Garg

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) ^ ((A ^ C) & B) -> (C ^ (B | (A ^ C)))
+    if (match(Op0I, m_Xor(m_Value(A), m_Value(B))) &&
+        match(Op1I, m_And(m_Xor(m_Specific(A), m_Value(C)), m_Specific(B))))
+      return BinaryOperator::CreateXor(C, Builder->CreateOr(B, Builder->CreateXor(A, 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/xor2.ll

  %negb = xor i32 %b, -1
  %and = and i32 %a, %negb
  %xor = xor i32 %nega, %and
  ret i32 %xor
 ; CHECK-LABEL: @test14(
 ; CHECK-NEXT: %1 = and i32 %a, %b
 ; CHECK-NEXT: %xor = xor i32 %1, -1
 }
+
+define i32 @test15(i32 %a, i32 %b) {
+; CHECK-LABEL: test15(
+; CHECK-NEXT: %1 = xor i32 %b, -1
+; CHECK-NEXT: %xor2 = and i32 %a, %1
+; CHECK-NEXT: ret i32 %xor2
+ %xor1 = xor i32 %a, %b
+ %not = xor i32 %a, -1
+ %and = and i32 %not, %b
+ %xor2 = xor i32 %xor1, %and
+ ret i32 %xor2
+}
+
+define i32 @test16(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: test16(
+; CHECK-NEXT: %1 = xor i32 %a, %c
+; CHECK-NEXT: %2 = or i32 %1, %b
+; CHECK-NEXT: %xor2 = xor i32 %2, %c
+; CHECK-NEXT: ret i32 %xor2
+ %xor1 = xor i32 %a, %b
+ %not = xor i32 %a, %c
+ %and = and i32 %not, %b
+ %xor2 = xor i32 %xor1, %and
+ ret i32 %xor2
+}