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

[sonamkumari]

Summary

This patch implements transform for pattern "(A ^ B) | ((~A) ^ B) -> True".

Please help in reviewing the same.

Thanks,
Sonam.

[majnemer]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2519–2522

This is incorrect, it should be something like:

// (A & B) ^ ((A ^ C) | B) -> (B | C) ^ A
if (match(Op0I, m_And(m_Value(A), m_Value(B))) &&
    match(Op1I, m_Or(m_Xor(m_Specific(A), m_Value(C)), m_Specific(B))))
  return BinaryOperator::CreateXor(Builder->CreateOr(B, C), A);

[suyog]

Hi Sonam,

I would strongly suggest you to 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 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.

[sonamkumari]

Hi David,Suyog,

Thanks David for pointing out the mistake.I have submitted the patch related to the expression you mentioned.

Thanks Suyog for this valuable information.I have attached the Z3 link for this expression.

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

Please help in reviewing the patch.

Regards,
Sonam.

[sonamkumari]

Gentle Ping !

[sonamkumari]

Gentle Ping !!

Patch won't take much time to review :)

[majnemer]

LGTM.

[sonamkumari]

Hi David,

Can you please commit this patch as I don't have the access. :)

Regards,
Sonam.

[sonamkumari]

Gentle Ping !

[sonamkumari]

Gentle Ping !

[asl]

Please provide the information asked in other thread for similar pattern:

1. How often this transformation triggers in LLVM testsuite. Where, in which tests.
2. How often this transformation triggers in SPEC. Where, in which tests.

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) -> (~A)
+    if (match(Op0I, m_And(m_Value(A), m_Value(B))) &&
+        match(Op1I, m_Or(m_Xor(m_Specific(A), m_Value(C)), m_Specific(B))))
+      return BinaryOperator::CreateNot(A);
   }
 
   // (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 %x, i32 %y) {
+  %and = and i32 %x, %y
+  %nega = xor i32 %x, -1
+  %or = or i32 %nega, %y
+  %and1 = xor i32 %and, %or
+  ret i32 %and1
+; CHECK-LABEL: @test15(
+; CHECK-NEXT: %and1 = xor i32 %x, -1
+; CHECK-NEXT: ret i32 %and1
+}