[InstCombine] Fold pattern xor(and, or) to select

[bcl5980]

Summary

(A & B) ^ (A | C) --> A ? ~B : C

https://alive2.llvm.org/ce/z/KCBfXr
https://alive2.llvm.org/ce/z/Pm-zJN
https://alive2.llvm.org/ce/z/VT8uC2

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

4287

Capitalize variable name: "NeedFreeze"

llvm/test/Transforms/InstCombine/xor-and-or.ll

4

How does this example already get optimized? Can we remove the code that handled it?

200–201

Remove TODO comment.

214–215

Remove TODO comment.

[bcl5980]

llvm/test/Transforms/InstCombine/xor-and-or.ll

4

This pattern is optimized in SimplifySelectsFeedingBinaryOp.

(A ? B : C) op (A ? E : F) -> A ? (B op E) : (C op F)

I don't think we can remove the code as it can handle not only i1 types.

[spatel]

LGTM

llvm/test/Transforms/InstCombine/xor-and-or.ll

200–201

typo: through -> though

If there's evidence that this is worse in codegen, then we could restrict the transform in this patch - only change when one or more of the original instructions is a select?

[bcl5980]

llvm/test/Transforms/InstCombine/xor-and-or.ll

200–201

https://godbolt.org/z/7hPWbK9oT
It looks the drop comes from i1 vector. The case I worry looks at least no drop. Can I disable for the vector in this patch?

[spatel]

llvm/test/Transforms/InstCombine/xor-and-or.ll

200–201

I don't think that's necessary. These kind of patterns are not likely in real vector code - we would have compares generating the condition vectors, and we would not have illegal types.

If someone finds a regression from this patch, we can fix it in the backend or limit the transform here.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B)))) &&
     if (A == C)
       std::swap(C, D);
     if (A == D) {
       Value *NotA = Builder.CreateNot(A);
       return BinaryOperator::CreateAnd(Builder.CreateXor(B, C), NotA);
     }
   }
 
+  // (A & B) ^ (A | C) --> A ? ~B : C -- There are 4 commuted variants.
+  if (I.getType()->isIntOrIntVectorTy(1) &&
+      match(Op0, m_OneUse(m_LogicalAnd(m_Value(A), m_Value(B)))) &&
+      match(Op1, m_OneUse(m_LogicalOr(m_Value(C), m_Value(D))))) {
+    bool NeedFreeze = isa<SelectInst>(Op0) && isa<SelectInst>(Op1) && B == D;
+    if (B == C || B == D)
+      std::swap(A, B);
+    if (A == C)
+      std::swap(C, D);
+    if (A == D) {
+      if (NeedFreeze)
+        A = Builder.CreateFreeze(A);
+      Value *NotB = Builder.CreateNot(B);
+      return SelectInst::Create(A, NotB, C);
+    }
+  }
+
   if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
     if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
       if (Value *V = foldXorOfICmps(LHS, RHS, I))
         return replaceInstUsesWith(I, V);
 
   if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
     return CastedXor;
 

llvm/test/Transforms/InstCombine/xor-and-or.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 define i1 @xor_logic_and_logic_or1(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @xor_logic_and_logic_or1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], true
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %o = select i1 %c, i1 true, i1 %y
   %a = select i1 %c, i1 %x, i1 false
   %r = xor i1 %a, %o
   ret i1 %r
 }
 
 define i1 @xor_logic_and_logic_or2(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @xor_logic_and_logic_or2(
-; CHECK-NEXT:    [[O:%.*]] = select i1 [[Y:%.*]], i1 true, i1 [[C:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = select i1 [[C]], i1 [[X:%.*]], i1 false
-; CHECK-NEXT:    [[R:%.*]] = xor i1 [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %o = select i1 %y, i1 true, i1 %c
   %a = select i1 %c, i1 %x, i1 false
   %r = xor i1 %a, %o
   ret i1 %r
 }
 
 define i1 @xor_logic_and_logic_or3(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @xor_logic_and_logic_or3(
-; CHECK-NEXT:    [[O:%.*]] = select i1 [[Y:%.*]], i1 true, i1 [[C:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = select i1 [[X:%.*]], i1 [[C]], i1 false
-; CHECK-NEXT:    [[R:%.*]] = xor i1 [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i1 [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[TMP1]], i1 [[TMP2]], i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %o = select i1 %y, i1 true, i1 %c
   %a = select i1 %x, i1 %c, i1 false
   %r = xor i1 %a, %o
   ret i1 %r
 }
 
 define i1 @xor_logic_and_logic_or4(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @xor_logic_and_logic_or4(
-; CHECK-NEXT:    [[O:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[Y:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = select i1 [[X:%.*]], i1 [[C]], i1 false
-; CHECK-NEXT:    [[R:%.*]] = xor i1 [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %o = select i1 %c, i1 true, i1 %y
   %a = select i1 %x, i1 %c, i1 false
   %r = xor i1 %a, %o
   ret i1 %r
 }
 
 define <3 x i1> @xor_logic_and_logic_or_vector1(<3 x i1> %c, <3 x i1> %x, <3 x i1> %y) {
 ; CHECK-LABEL: @xor_logic_and_logic_or_vector1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = xor <3 x i1> [[X:%.*]], <i1 true, i1 true, i1 true>
 ; CHECK-NEXT:    [[R:%.*]] = select <3 x i1> [[C:%.*]], <3 x i1> [[TMP1]], <3 x i1> [[Y:%.*]]
 ; CHECK-NEXT:    ret <3 x i1> [[R]]
 ;
   %o = select <3 x i1> %c, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %y
   %a = select <3 x i1> %c, <3 x i1> %x, <3 x i1> <i1 false, i1 false, i1 false>
   %r = xor <3 x i1> %a, %o
   ret <3 x i1> %r
 }
 
 define <3 x i1> @xor_logic_and_logic_or_vector2(<3 x i1> %c, <3 x i1> %x, <3 x i1> %y) {
 ; CHECK-LABEL: @xor_logic_and_logic_or_vector2(
-; CHECK-NEXT:    [[O:%.*]] = select <3 x i1> [[Y:%.*]], <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> [[C:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = select <3 x i1> [[X:%.*]], <3 x i1> [[C]], <3 x i1> zeroinitializer
-; CHECK-NEXT:    [[R:%.*]] = xor <3 x i1> [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze <3 x i1> [[C:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor <3 x i1> [[X:%.*]], <i1 true, i1 true, i1 true>
+; CHECK-NEXT:    [[R:%.*]] = select <3 x i1> [[TMP1]], <3 x i1> [[TMP2]], <3 x i1> [[Y:%.*]]
 ; CHECK-NEXT:    ret <3 x i1> [[R]]
 ;
   %o = select <3 x i1> %y, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %c
   %a = select <3 x i1> %x, <3 x i1> %c, <3 x i1> <i1 false, i1 false, i1 false>
   %r = xor <3 x i1> %a, %o
   ret <3 x i1> %r
 }
 
;
   %o = select <3 x i1> %c, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %y
   %a = select <3 x i1> %c, <3 x i1> %x, <3 x i1> <i1 false, i1 poison, i1 false>
   %r = xor <3 x i1> %a, %o
   ret <3 x i1> %r
 }
 
 define i1 @xor_and_logic_or1(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @xor_and_logic_or1(
-; CHECK-NEXT:    [[O:%.*]] = select i1 [[C:%.*]], i1 true, i1 [[Y:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = and i1 [[C]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = xor i1 [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %o = select i1 %c, i1 true, i1 %y
   %a = and i1 %c, %x
   %r = xor i1 %a, %o
   ret i1 %r
 }
 
 define i1 @xor_and_logic_or2(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @xor_and_logic_or2(
-; CHECK-NEXT:    [[O:%.*]] = select i1 [[Y:%.*]], i1 true, i1 [[C:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = and i1 [[X:%.*]], [[C]]
-; CHECK-NEXT:    [[R:%.*]] = xor i1 [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %o = select i1 %y, i1 true, i1 %c
   %a = and i1 %x, %c
   %r = xor i1 %a, %o
   ret i1 %r
 }
 
 define <2 x i1> @xor_and_logic_or_vector(<2 x i1> %c, <2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @xor_and_logic_or_vector(
-; CHECK-NEXT:    [[O:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[Y:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = and <2 x i1> [[C]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i1> [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i1> [[X:%.*]], <i1 true, i1 true>
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> [[TMP1]], <2 x i1> [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %o = select <2 x i1> %c, <2 x i1> <i1 true, i1 true>, <2 x i1> %y
   %a = and <2 x i1> %c, %x
   %r = xor <2 x i1> %a, %o
   ret <2 x i1> %r
 }
 
 define <2 x i1> @xor_and_logic_or_vector_poison(<2 x i1> %c, <2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @xor_and_logic_or_vector_poison(
 ; CHECK-NEXT:    [[O:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> <i1 poison, i1 true>, <2 x i1> [[Y:%.*]]
 ; CHECK-NEXT:    [[A:%.*]] = and <2 x i1> [[C]], [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = xor <2 x i1> [[A]], [[O]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %o = select <2 x i1> %c, <2 x i1> <i1 poison, i1 true>, <2 x i1> %y
   %a = and <2 x i1> %c, %x
   %r = xor <2 x i1> %a, %o
   ret <2 x i1> %r
 }
 
 define i1 @xor_logic_and_or1(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @xor_logic_and_or1(
-; CHECK-NEXT:    [[O:%.*]] = or i1 [[Y:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = select i1 [[C]], i1 [[X:%.*]], i1 false
-; CHECK-NEXT:    [[R:%.*]] = xor i1 [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %o = or i1 %y, %c
   %a = select i1 %c, i1 %x, i1 false
   %r = xor i1 %a, %o
   ret i1 %r
 }
 
 define i1 @xor_logic_and_or2(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @xor_logic_and_or2(
-; CHECK-NEXT:    [[O:%.*]] = or i1 [[C:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = select i1 [[X:%.*]], i1 [[C]], i1 false
-; CHECK-NEXT:    [[R:%.*]] = xor i1 [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %o = or i1 %c, %y
   %a = select i1 %x, i1 %c, i1 false
   %r = xor i1 %a, %o
   ret i1 %r
 }
 
 define <2 x i1> @xor_logic_and_or_vector(<2 x i1> %c, <2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @xor_logic_and_or_vector(
-; CHECK-NEXT:    [[O:%.*]] = or <2 x i1> [[Y:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = select <2 x i1> [[C]], <2 x i1> [[X:%.*]], <2 x i1> zeroinitializer
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i1> [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i1> [[X:%.*]], <i1 true, i1 true>
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[C:%.*]], <2 x i1> [[TMP1]], <2 x i1> [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %o = or <2 x i1> %y, %c
   %a = select <2 x i1> %c, <2 x i1> %x, <2 x i1> <i1 false, i1 false>
   %r = xor <2 x i1> %a, %o
   ret <2 x i1> %r
 }
 
 define <2 x i1> @xor_logic_and_or_vector_poison(<2 x i1> %c, <2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @xor_logic_and_or_vector_poison(
 ; CHECK-NEXT:    [[O:%.*]] = or <2 x i1> [[Y:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[A:%.*]] = select <2 x i1> [[C]], <2 x i1> [[X:%.*]], <2 x i1> <i1 poison, i1 false>
 ; CHECK-NEXT:    [[R:%.*]] = xor <2 x i1> [[A]], [[O]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %o = or <2 x i1> %y, %c
   %a = select <2 x i1> %c, <2 x i1> %x, <2 x i1> <i1 poison, i1 false>
   %r = xor <2 x i1> %a, %o
   ret <2 x i1> %r
 }
 
-;; TODO: do we really need to do this transform?
+;; even through we save a instruction here, select is heavier than normal 
+;; and/or/xor on most backend,  do we really need to do this transform?
 define i1 @xor_and_or(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @xor_and_or(
-; CHECK-NEXT:    [[O:%.*]] = or i1 [[Y:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = and i1 [[C]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = xor i1 [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i1 [[X:%.*]], true
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C:%.*]], i1 [[TMP1]], i1 [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %o = or i1 %y, %c
   %a = and i1 %c, %x
   %r = xor i1 %a, %o
   ret i1 %r
 }
 
-;; TODO: do we really need to do this transform?
+;; even through we save a instruction here, select is heavier than normal 
+;; and/or/xor on most backend,  do we really need to do this transform?
 define <4 x i1> @xor_and_or_vector(<4 x i1> %c, <4 x i1> %x, <4 x i1> %y) {
 ; CHECK-LABEL: @xor_and_or_vector(
-; CHECK-NEXT:    [[O:%.*]] = or <4 x i1> [[Y:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[A:%.*]] = and <4 x i1> [[C]], [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = xor <4 x i1> [[A]], [[O]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i1> [[X:%.*]], <i1 true, i1 true, i1 true, i1 true>
+; CHECK-NEXT:    [[R:%.*]] = select <4 x i1> [[C:%.*]], <4 x i1> [[TMP1]], <4 x i1> [[Y:%.*]]
 ; CHECK-NEXT:    ret <4 x i1> [[R]]
 ;
   %o = or <4 x i1> %y, %c
   %a = and <4 x i1> %c, %x
   %r = xor <4 x i1> %a, %o
   ret <4 x i1> %r
 }
 
+; Negative test, more than one use
 define i1 @xor_and_or_negative_oneuse(i1 %c, i1 %x, i1 %y) {
 ; CHECK-LABEL: @xor_and_or_negative_oneuse(
 ; CHECK-NEXT:    [[O:%.*]] = or i1 [[Y:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[A:%.*]] = and i1 [[C]], [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = xor i1 [[A]], [[O]]
 ; CHECK-NEXT:    call void @use(i1 [[O]])
 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %o = or i1 %y, %c
   %a = and i1 %c, %x
   %r = xor i1 %a, %o
   call void @use(i1 %o)
   ret i1 %r
 }
 
 declare void @use(i1)