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

1284–1287

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

1287

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

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) & ((~(A)^B) -> 0
+  if(match(Op0,m_Xor(m_Value(A),m_Value(B)))
+          && match(Op1,m_Xor(m_Not(m_Specific(A)),m_Specific(B))))
+      return BinaryOperator::CreateAnd(A, Builder->CreateNot(A));
   }
 
   if (ICmpInst *RHS = dyn_cast<ICmpInst>(Op1))
     if (ICmpInst *LHS = dyn_cast<ICmpInst>(Op0))
       if (Value *Res = FoldAndOfICmps(LHS, RHS))
         return ReplaceInstUsesWith(I, Res);
 
   // If and'ing two fcmp, try combine them into one.

test/Transforms/InstCombine/or-xor.ll

define i32 @test9(i32 %x, i32 %y) nounwind {
   %xor = xor i32 %not, %y
   %z = or i32 %x, %xor
   ret i32 %z
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT: %y.not = xor i32 %y, -1
 ; CHECK-NEXT: %z = or i32 %y.not, %x
 ; CHECK-NEXT: ret i32 %z
 }
+
+define i32 @test10(i32%x,i32%y){
+;CHECK-LABEL: @test10(
+;CHECK-NEXT: ret i32 0
+%xor = xor i32%x,%y
+%nega = xor i32%x,-1
+%xor1 = xor i32%nega,%y
+%and = and i32%xor,%xor1
+ret i32 %and
+}