[InstCombine] sub(xor(x, y), or(x, y)) -> neg(and(x, y))

[xbolva00]

Summary

Name: sub(xor(x, y), or(x, y)) -> neg(and(x, y))
%or = or i32 %y, %x
%xor = xor i32 %x, %y
%sub = sub i32 %xor, %or
  =>
%sub1 = and i32 %x, %y
%sub = sub i32 0, %sub1

Optimization: sub(xor(x, y), or(x, y)) -> neg(and(x, y))
Done: 1
Optimization is correct!

https://rise4fun.com/Alive/8OI

[lebedev.ri]

LG, thanks.

I wonder what other similar 3-instruction folds are missing.

[xbolva00]

Thank you.

Next one which we miss: (~a & b) ^ a -> (a | b)

lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombiner::visitSub(BinaryOperator &I) {
   // (sub (or A, B), (xor A, B)) --> (and A, B)
   {
     Value *A, *B;
     if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
         match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
       return BinaryOperator::CreateAnd(A, B);
   }
 
+  // (sub (xor A, B) (or A, B)) --> neg (and A, B)
+  {
+    Value *A, *B;
+    if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
+        match(Op1, m_c_Or(m_Specific(A), m_Specific(B))) &&
+        (Op0->hasOneUse() || Op1->hasOneUse()))
+      return BinaryOperator::CreateNeg(Builder.CreateAnd(A, B));
+  }
+
   {
     Value *Y;
     // ((X | Y) - X) --> (~X & Y)
     if (match(Op0, m_OneUse(m_c_Or(m_Value(Y), m_Specific(Op1)))))
       return BinaryOperator::CreateAnd(
           Y, Builder.CreateNot(Op1, Op1->getName() + ".not"));
   }
 

test/Transforms/InstCombine/sub-xor-or-neg-and.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 declare void @use(i32)
 
 define i32 @sub_to_and(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_to_and(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[XOR]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ;
   %or = or i32 %x, %y
   %xor = xor i32 %x, %y
   %sub = sub i32 %xor, %or
   ret i32 %sub
 }
 
 define i32 @sub_to_and_extra_use_sub(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_to_and_extra_use_sub(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[XOR]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[TMP1]]
 ; CHECK-NEXT:    call void @use(i32 [[SUB]])
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ;
   %or = or i32 %x, %y
   %xor = xor i32 %x, %y
   %sub = sub i32 %xor, %or
   call void @use(i32 %sub)
   ret i32 %sub
 }
 
 define i32 @sub_to_and_extra_use_and(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_to_and_extra_use_and(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i32 [[XOR]])
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[XOR]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ;
   %or = or i32 %x, %y
   %xor = xor i32 %x, %y
   call void @use(i32 %xor)
   %sub = sub i32 %xor, %or
   ret i32 %sub
 }
 
 define i32 @sub_to_and_extra_use_or(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_to_and_extra_use_or(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i32 [[OR]])
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[XOR]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X]], [[Y]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ;
   %or = or i32 %x, %y
   call void @use(i32 %or)
   %xor = xor i32 %x, %y
   %sub = sub i32 %xor, %or
   ret i32 %sub
 }
 
 define i32 @sub_to_and_or_commuted(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_to_and_or_commuted(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X]], [[Y]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[XOR]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ;
   %or = or i32 %y, %x
   %xor = xor i32 %x, %y
   %sub = sub i32 %xor, %or
   ret i32 %sub
 }
 
 define i32 @sub_to_and_and_commuted(i32 %x, i32 %y) {
 ; CHECK-LABEL: @sub_to_and_and_commuted(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[Y]], [[X]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[XOR]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[SUB]]
 ;
   %or = or i32 %x, %y
   %xor = xor i32 %y, %x
   %sub = sub i32 %xor, %or
   ret i32 %sub
 }
 
 define <2 x i32> @sub_to_and_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @sub_to_and_vec(
-; CHECK-NEXT:    [[OR:%.*]] = or <2 x i32> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i32> [[Y]], [[X]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub <2 x i32> [[XOR]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[SUB:%.*]] = sub <2 x i32> zeroinitializer, [[TMP1]]
 ; CHECK-NEXT:    ret <2 x i32> [[SUB]]
 ;
   %or = or <2 x i32> %x, %y
   %xor = xor <2 x i32> %y, %x
   %sub = sub <2 x i32> %xor, %or
   ret <2 x i32> %sub
 }