[InstCombine] Fold ((A&B)^C)|B

Fold ((A&B)^C)|B into C|B.

https://alive2.llvm.org/ce/z/zSGSor

This addresses the issue https://github.com/llvm/llvm-project/issues/55169

Test plan: ninja check-all

Differential revision: https://reviews.llvm.org/D124710

3 files changed, 34 insertions, 60 deletions

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
index aef9ae1..c18a48f 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -2688,6 +2688,14 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) {
     if (match(Op1, m_Xor(m_Specific(B), m_Specific(A))))
       return BinaryOperator::CreateOr(Op1, C);
 
+  // ((A & B) ^ C) | B -> C | B
+  if (match(Op0, m_c_Xor(m_c_And(m_Value(A), m_Specific(Op1)), m_Value(C))))
+    return BinaryOperator::CreateOr(C, Op1);
+
+  // B | ((A & B) ^ C) -> B | C
+  if (match(Op1, m_c_Xor(m_c_And(m_Value(A), m_Specific(Op0)), m_Value(C))))
+    return BinaryOperator::CreateOr(Op0, C);
+
   // ((B | C) & A) | B -> B | (A & C)
   if (match(Op0, m_And(m_Or(m_Specific(Op1), m_Value(C)), m_Value(A))))
     return BinaryOperator::CreateOr(Op1, Builder.CreateAnd(A, C));
diff --git a/llvm/test/Transforms/InstCombine/add.ll b/llvm/test/Transforms/InstCombine/add.ll
index 8a9ee7d..4738a55 100644
--- a/llvm/test/Transforms/InstCombine/add.ll
+++ b/llvm/test/Transforms/InstCombine/add.ll
@@ -1490,9 +1490,7 @@ define i8 @add_and_xor_extra_use(i8 %x, i8 %y) {
 
 define i8 @add_xor_and_const(i8 %x) {
 ; CHECK-LABEL: @add_xor_and_const(
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], 42
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], 42
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X:%.*]], 42
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %x, 42
@@ -1518,8 +1516,7 @@ define i8 @add_xor_and_var(i8 %x, i8 %y) {
 ; CHECK-LABEL: @add_xor_and_var(
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[Y]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %x, %y
@@ -1563,8 +1560,7 @@ define i8 @add_xor_and_var_commuted1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @add_xor_and_var_commuted1(
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y:%.*]], [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[Y]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %y, %x
@@ -1580,8 +1576,7 @@ define i8 @add_xor_and_var_commuted2(i8 %_x, i8 %_y) {
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[Y]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
@@ -1598,8 +1593,7 @@ define i8 @add_xor_and_var_commuted3(i8 %x, i8 %_y) {
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[Y]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %y = udiv i8 42, %_y ; thwart complexity-based canonicalization
@@ -1615,8 +1609,7 @@ define i8 @add_xor_and_var_commuted4(i8 %_x, i8 %y) {
 ; CHECK-NEXT:    [[X:%.*]] = udiv i8 42, [[_X:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y:%.*]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
@@ -1633,8 +1626,7 @@ define i8 @add_xor_and_var_commuted5(i8 %_x, i8 %_y) {
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[X]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
@@ -1652,8 +1644,7 @@ define i8 @add_xor_and_var_commuted6(i8 %_x, i8 %_y) {
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X]], [[Y]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
@@ -1671,8 +1662,7 @@ define i8 @add_xor_and_var_commuted7(i8 %_x, i8 %_y) {
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i8 42, [[_Y:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i8 [[Y]], [[X]]
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[Y]], [[AND]]
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[XOR]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[X]], [[Y]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %x = udiv i8 42, %_x ; thwart complexity-based canonicalization
@@ -1690,7 +1680,7 @@ define i8 @add_xor_and_var_extra_use(i8 %x, i8 %y) {
 ; CHECK-NEXT:    call void @use(i8 [[AND]])
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[AND]], [[Y]]
 ; CHECK-NEXT:    call void @use(i8 [[XOR]])
-; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[XOR]], [[X]]
+; CHECK-NEXT:    [[ADD:%.*]] = or i8 [[Y]], [[X]]
 ; CHECK-NEXT:    ret i8 [[ADD]]
 ;
   %and = and i8 %x, %y
diff --git a/llvm/test/Transforms/InstCombine/and-xor-or.ll b/llvm/test/Transforms/InstCombine/and-xor-or.ll
index fbfc0725..f3ab4ac 100644
--- a/llvm/test/Transforms/InstCombine/and-xor-or.ll
+++ b/llvm/test/Transforms/InstCombine/and-xor-or.ll
@@ -172,13 +172,10 @@ define i64 @or2(i64 %x, i64 %y) {
 
 define i64 @and_xor_or1(i64 %px, i64 %py, i64 %pz) {
 ; CHECK-LABEL: @and_xor_or1(
-; CHECK-NEXT:    [[X:%.*]] = udiv i64 42, [[PX:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[TMP2]], [[Y]]
-; CHECK-NEXT:    ret i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Z:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
@@ -193,13 +190,10 @@ define i64 @and_xor_or1(i64 %px, i64 %py, i64 %pz) {
 
 define i64 @and_xor_or2(i64 %px, i64 %py, i64 %pz) {
 ; CHECK-LABEL: @and_xor_or2(
-; CHECK-NEXT:    [[X:%.*]] = udiv i64 42, [[PX:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[TMP2]], [[Y]]
-; CHECK-NEXT:    ret i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Z:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
@@ -214,13 +208,10 @@ define i64 @and_xor_or2(i64 %px, i64 %py, i64 %pz) {
 
 define i64 @and_xor_or3(i64 %px, i64 %py, i64 %pz) {
 ; CHECK-LABEL: @and_xor_or3(
-; CHECK-NEXT:    [[X:%.*]] = udiv i64 42, [[PX:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[Z:%.*]], [[TMP1]]
-; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[TMP2]], [[Y]]
-; CHECK-NEXT:    ret i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Z:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
@@ -235,13 +226,10 @@ define i64 @and_xor_or3(i64 %px, i64 %py, i64 %pz) {
 
 define i64 @and_xor_or4(i64 %px, i64 %py, i64 %pz) {
 ; CHECK-LABEL: @and_xor_or4(
-; CHECK-NEXT:    [[X:%.*]] = udiv i64 42, [[PX:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[Z:%.*]], [[TMP1]]
-; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[TMP2]], [[Y]]
-; CHECK-NEXT:    ret i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Z:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
@@ -256,13 +244,10 @@ define i64 @and_xor_or4(i64 %px, i64 %py, i64 %pz) {
 
 define i64 @and_xor_or5(i64 %px, i64 %py, i64 %pz) {
 ; CHECK-LABEL: @and_xor_or5(
-; CHECK-NEXT:    [[X:%.*]] = udiv i64 42, [[PX:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[Y]], [[TMP2]]
-; CHECK-NEXT:    ret i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y:%.*]], [[Z:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
@@ -277,13 +262,10 @@ define i64 @and_xor_or5(i64 %px, i64 %py, i64 %pz) {
 
 define i64 @and_xor_or6(i64 %px, i64 %py, i64 %pz) {
 ; CHECK-LABEL: @and_xor_or6(
-; CHECK-NEXT:    [[X:%.*]] = udiv i64 42, [[PX:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[TMP1]], [[Z:%.*]]
-; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[Y]], [[TMP2]]
-; CHECK-NEXT:    ret i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y:%.*]], [[Z:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
@@ -298,13 +280,10 @@ define i64 @and_xor_or6(i64 %px, i64 %py, i64 %pz) {
 
 define i64 @and_xor_or7(i64 %px, i64 %py, i64 %pz) {
 ; CHECK-LABEL: @and_xor_or7(
-; CHECK-NEXT:    [[X:%.*]] = udiv i64 42, [[PX:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[Z:%.*]], [[TMP1]]
-; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[Y]], [[TMP2]]
-; CHECK-NEXT:    ret i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y:%.*]], [[Z:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
   %y = udiv i64 42, %py ; thwart complexity-based canonicalization
@@ -319,13 +298,10 @@ define i64 @and_xor_or7(i64 %px, i64 %py, i64 %pz) {
 
 define i64 @and_xor_or8(i64 %px, i64 %py, i64 %pz) {
 ; CHECK-LABEL: @and_xor_or8(
-; CHECK-NEXT:    [[X:%.*]] = udiv i64 42, [[PX:%.*]]
 ; CHECK-NEXT:    [[Y:%.*]] = udiv i64 42, [[PY:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = udiv i64 42, [[PZ:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[Z:%.*]], [[TMP1]]
-; CHECK-NEXT:    [[TMP3:%.*]] = or i64 [[Y]], [[TMP2]]
-; CHECK-NEXT:    ret i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[Y:%.*]], [[Z:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP1]]
 ;
   %x = udiv i64 42, %px ; thwart complexity-based canonicalization
   %y = udiv i64 42, %py ; thwart complexity-based canonicalization