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

[sonamkumari]

Summary

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

Please help in reviewing the same.

Thanks,
Sonam.

[majnemer]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1287–1290

Please format the code to match the coding standards: http://llvm.org/docs/CodingStandards.html

1290

This is wasteful, we don't need an instruction if we know the result is a constant. Sounds like a candidate for InstSimplify instead of InstCombine.

test/Transforms/InstCombine/or-xor.ll

96–104 ↗

(On Diff #11937)

Please format this test to match the others.

[sonamkumari]

Hi David,

Thanks for your valuable comments.I will try to consider general case while doing any optimization in future.
But the patch which you uploaded in rL214342 fails for the following test cases as it doesn't take into consideration the symmetric case.

The test cases for which it fails are :

define i32 @test15(i32 %x, i32 %y) {
%nega = xor i32 %x, -1
%xor = xor i32 %nega, %y
%xor1 = xor i32 %x, %y
%and = and i32 %xor, %xor1
ret i32 %and
}

define i32 @test16(i32 %x, i32 %y) {
%xor = xor i32 %x, %y
%nega = xor i32 %x, -1
%xor1 = xor i32 %nega, %y
%and = and i32 %xor, %xor1
ret i32 %and
}

So, I modified the patch and submitting the same.
Kindly review it.

Thanks,
Sonam.

[suyog]

LGTM. I would wait for David to comment on it though.

[majnemer]

I don't think we need to do anything here, running the reassociate pass before instcombine makes this problem go away.

$ cat t.ll
define i32 @test15(i32 %x, i32 %y) {
 %nega = xor i32 %x, -1
 %xor = xor i32 %nega, %y
 %xor1 = xor i32 %x, %y
 %and = and i32 %xor, %xor1
 ret i32 %and
}

define i32 @test16(i32 %x, i32 %y) {
 %xor = xor i32 %x, %y
 %nega = xor i32 %x, -1
 %xor1 = xor i32 %nega, %y
 %and = and i32 %xor, %xor1
 ret i32 %and
}

$ ~/llvm/Debug+Asserts/bin/opt -reassociate -instcombine t.ll -o - -S
; ModuleID = 't.ll'

define i32 @test15(i32 %x, i32 %y) {
  ret i32 0
}

define i32 @test16(i32 %x, i32 %y) {
  ret i32 0
}

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (Value *Op0NotVal = dyn_castNotVal(Op0))
     // (A&((~A)|B)) -> A&B
     if (match(Op0, m_Or(m_Not(m_Specific(Op1)), m_Value(A))) ||
         match(Op0, m_Or(m_Value(A), m_Not(m_Specific(Op1)))))
       return BinaryOperator::CreateAnd(A, Op1);
     if (match(Op1, m_Or(m_Not(m_Specific(Op0)), m_Value(A))) ||
         match(Op1, m_Or(m_Value(A), m_Not(m_Specific(Op0)))))
       return BinaryOperator::CreateAnd(A, Op0);
 
     // (A ^ B) & ((B ^ C) ^ A) -> (A ^ B) & ~C
-    if (match(Op0, m_Xor(m_Value(A), m_Value(B))))
-      if (match(Op1, m_Xor(m_Xor(m_Specific(B), m_Value(C)), m_Specific(A))))
+    // (B ^ A) & ((B ^ C) ^ A) -> (A ^ B) & ~C
+    if (match(Op1, m_Xor(m_Xor(m_Value(B), m_Value(C)), m_Value(A))))
+      if (match(Op0, m_Xor(m_Specific(A), m_Specific(B))) ||
+          match(Op0, m_Xor(m_Specific(B), m_Specific(A))))
         if (Op1->hasOneUse() || cast<BinaryOperator>(Op1)->hasOneUse())
           return BinaryOperator::CreateAnd(Op0, Builder->CreateNot(C));
 
     // ((A ^ C) ^ B) & (B ^ A) -> (B ^ A) & ~C
+    // ((A ^ C) ^ B) & (A ^ B) -> (B ^ A) & ~C
     if (match(Op0, m_Xor(m_Xor(m_Value(A), m_Value(C)), m_Value(B))))
-      if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
+      if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))) ||
+          match(Op1, m_Xor(m_Specific(A), m_Specific(B))))
         if (Op0->hasOneUse() || cast<BinaryOperator>(Op0)->hasOneUse())
           return BinaryOperator::CreateAnd(Op1, Builder->CreateNot(C));
 
     // (A | B) & ((~A) ^ B) -> (A & B)
     if (match(Op0, m_Or(m_Value(A), m_Value(B))) &&
         match(Op1, m_Xor(m_Not(m_Specific(A)), m_Specific(B))))
       return BinaryOperator::CreateAnd(A, 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) {
+ %nega = xor i32 %x, -1
+ %xor = xor i32 %nega, %y
+ %xor1 = xor i32 %x, %y
+ %and = and i32 %xor, %xor1
+ ret i32 %and
+; CHECK-LABEL: @test15(
+; CHECK-NEXT: ret i32 0
+}
+
+define i32 @test16(i32 %x, i32 %y) {
+ %xor = xor i32 %x, %y
+ %nega = xor i32 %x, -1
+ %xor1 = xor i32 %nega, %y
+ %and = and i32 %xor, %xor1
+ ret i32 %and
+; CHECK-LABEL: @test16(
+; CHECK-NEXT: ret i32 0
+}