From b066195b3f026d319ee06b6c0285762d9a042a3a Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Thu, 18 Aug 2022 15:26:32 -0400 Subject: [PATCH] [InstCombine] fold bitwise logic or+or+xor+not (~A | C) | (A ^ B) --> ~(A & B) | C https://alive2.llvm.org/ce/z/Qw3aiJ This extends the existing fold (just above the new match) to peek through another 'or' instruction. This should let the motivating case from issue #57174 simplify completely. --- .../Transforms/InstCombine/InstCombineAndOrXor.cpp | 9 ++++ llvm/test/Transforms/InstCombine/or-xor.ll | 59 ++++++++++------------ 2 files changed, 37 insertions(+), 31 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index 2667954..f037305 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -2933,6 +2933,15 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) { (match(Op0, m_Not(m_Specific(A))) || match(Op0, m_Not(m_Specific(B))))) return BinaryOperator::CreateNot(Builder.CreateAnd(A, B)); + // (~A | C) | (A ^ B) --> ~(A & B) | C + // (~B | C) | (A ^ B) --> ~(A & B) | C + if (Op0->hasOneUse() && Op1->hasOneUse() && + (match(Op0, m_c_Or(m_Not(m_Specific(A)), m_Value(C))) || + match(Op0, m_c_Or(m_Not(m_Specific(B)), m_Value(C))))) { + Value *Nand = Builder.CreateNot(Builder.CreateAnd(A, B), "nand"); + return BinaryOperator::CreateOr(Nand, C); + } + // A | (~A ^ B) --> ~B | A // B | (A ^ ~B) --> ~A | B if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) { diff --git a/llvm/test/Transforms/InstCombine/or-xor.ll b/llvm/test/Transforms/InstCombine/or-xor.ll index 8141775..63be159 100644 --- a/llvm/test/Transforms/InstCombine/or-xor.ll +++ b/llvm/test/Transforms/InstCombine/or-xor.ll @@ -798,10 +798,9 @@ define i8 @or_xor_notcommon_op(i8 %x, i8 %y, i8 %z, i8 %q) { define i4 @or_not_xor_common_op_commute0(i4 %x, i4 %y, i4 %z) { ; CHECK-LABEL: @or_not_xor_common_op_commute0( -; CHECK-NEXT: [[NOTX:%.*]] = xor i4 [[X:%.*]], -1 -; CHECK-NEXT: [[XOR:%.*]] = xor i4 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[O1:%.*]] = or i4 [[NOTX]], [[Z:%.*]] -; CHECK-NEXT: [[O2:%.*]] = or i4 [[O1]], [[XOR]] +; CHECK-NEXT: [[TMP1:%.*]] = and i4 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[NAND:%.*]] = xor i4 [[TMP1]], -1 +; CHECK-NEXT: [[O2:%.*]] = or i4 [[NAND]], [[Z:%.*]] ; CHECK-NEXT: ret i4 [[O2]] ; %notx = xor i4 %x, -1 @@ -815,9 +814,9 @@ define i8 @or_not_xor_common_op_commute1(i8 %x, i8 %y, i8 %z) { ; CHECK-LABEL: @or_not_xor_common_op_commute1( ; CHECK-NEXT: [[NOTX:%.*]] = xor i8 [[X:%.*]], -1 ; CHECK-NEXT: call void @use(i8 [[NOTX]]) -; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[O1:%.*]] = or i8 [[NOTX]], [[Z:%.*]] -; CHECK-NEXT: [[O2:%.*]] = or i8 [[XOR]], [[O1]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[X]], [[Y:%.*]] +; CHECK-NEXT: [[NAND:%.*]] = xor i8 [[TMP1]], -1 +; CHECK-NEXT: [[O2:%.*]] = or i8 [[NAND]], [[Z:%.*]] ; CHECK-NEXT: ret i8 [[O2]] ; %notx = xor i8 %x, -1 @@ -831,10 +830,9 @@ define i8 @or_not_xor_common_op_commute1(i8 %x, i8 %y, i8 %z) { define i8 @or_not_xor_common_op_commute2(i8 %x, i8 %y, i8 %p) { ; CHECK-LABEL: @or_not_xor_common_op_commute2( ; CHECK-NEXT: [[Z:%.*]] = sub i8 0, [[P:%.*]] -; CHECK-NEXT: [[NOTX:%.*]] = xor i8 [[X:%.*]], -1 -; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[O1:%.*]] = or i8 [[Z]], [[NOTX]] -; CHECK-NEXT: [[O2:%.*]] = or i8 [[XOR]], [[O1]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[NAND:%.*]] = xor i8 [[TMP1]], -1 +; CHECK-NEXT: [[O2:%.*]] = or i8 [[NAND]], [[Z]] ; CHECK-NEXT: ret i8 [[O2]] ; %z = sub i8 0, %p ; thwart complexity-based canonicalizaion @@ -848,10 +846,9 @@ define i8 @or_not_xor_common_op_commute2(i8 %x, i8 %y, i8 %p) { define i8 @or_not_xor_common_op_commute3(i8 %x, i8 %y, i8 %p) { ; CHECK-LABEL: @or_not_xor_common_op_commute3( ; CHECK-NEXT: [[Z:%.*]] = sub i8 0, [[P:%.*]] -; CHECK-NEXT: [[NOTX:%.*]] = xor i8 [[X:%.*]], -1 -; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[X]], [[Y:%.*]] -; CHECK-NEXT: [[O1:%.*]] = or i8 [[Z]], [[NOTX]] -; CHECK-NEXT: [[O2:%.*]] = or i8 [[O1]], [[XOR]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[NAND:%.*]] = xor i8 [[TMP1]], -1 +; CHECK-NEXT: [[O2:%.*]] = or i8 [[NAND]], [[Z]] ; CHECK-NEXT: ret i8 [[O2]] ; %z = sub i8 0, %p ; thwart complexity-based canonicalizaion @@ -864,10 +861,9 @@ define i8 @or_not_xor_common_op_commute3(i8 %x, i8 %y, i8 %p) { define <2 x i4> @or_not_xor_common_op_commute4(<2 x i4> %x, <2 x i4> %y, <2 x i4> %z) { ; CHECK-LABEL: @or_not_xor_common_op_commute4( -; CHECK-NEXT: [[NOTX:%.*]] = xor <2 x i4> [[X:%.*]], -; CHECK-NEXT: [[XOR:%.*]] = xor <2 x i4> [[Y:%.*]], [[X]] -; CHECK-NEXT: [[O1:%.*]] = or <2 x i4> [[NOTX]], [[Z:%.*]] -; CHECK-NEXT: [[O2:%.*]] = or <2 x i4> [[O1]], [[XOR]] +; CHECK-NEXT: [[TMP1:%.*]] = and <2 x i4> [[Y:%.*]], [[X:%.*]] +; CHECK-NEXT: [[NAND:%.*]] = xor <2 x i4> [[TMP1]], +; CHECK-NEXT: [[O2:%.*]] = or <2 x i4> [[NAND]], [[Z:%.*]] ; CHECK-NEXT: ret <2 x i4> [[O2]] ; %notx = xor <2 x i4> %x, @@ -879,10 +875,9 @@ define <2 x i4> @or_not_xor_common_op_commute4(<2 x i4> %x, <2 x i4> %y, <2 x i4 define i8 @or_not_xor_common_op_commute5(i8 %x, i8 %y, i8 %z) { ; CHECK-LABEL: @or_not_xor_common_op_commute5( -; CHECK-NEXT: [[NOTX:%.*]] = xor i8 [[X:%.*]], -1 -; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[Y:%.*]], [[X]] -; CHECK-NEXT: [[O1:%.*]] = or i8 [[NOTX]], [[Z:%.*]] -; CHECK-NEXT: [[O2:%.*]] = or i8 [[XOR]], [[O1]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[Y:%.*]], [[X:%.*]] +; CHECK-NEXT: [[NAND:%.*]] = xor i8 [[TMP1]], -1 +; CHECK-NEXT: [[O2:%.*]] = or i8 [[NAND]], [[Z:%.*]] ; CHECK-NEXT: ret i8 [[O2]] ; %notx = xor i8 %x, -1 @@ -895,10 +890,9 @@ define i8 @or_not_xor_common_op_commute5(i8 %x, i8 %y, i8 %z) { define i8 @or_not_xor_common_op_commute6(i8 %x, i8 %y, i8 %p) { ; CHECK-LABEL: @or_not_xor_common_op_commute6( ; CHECK-NEXT: [[Z:%.*]] = sub i8 0, [[P:%.*]] -; CHECK-NEXT: [[NOTX:%.*]] = xor i8 [[X:%.*]], -1 -; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[Y:%.*]], [[X]] -; CHECK-NEXT: [[O1:%.*]] = or i8 [[Z]], [[NOTX]] -; CHECK-NEXT: [[O2:%.*]] = or i8 [[XOR]], [[O1]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[Y:%.*]], [[X:%.*]] +; CHECK-NEXT: [[NAND:%.*]] = xor i8 [[TMP1]], -1 +; CHECK-NEXT: [[O2:%.*]] = or i8 [[NAND]], [[Z]] ; CHECK-NEXT: ret i8 [[O2]] ; %z = sub i8 0, %p ; thwart complexity-based canonicalizaion @@ -912,10 +906,9 @@ define i8 @or_not_xor_common_op_commute6(i8 %x, i8 %y, i8 %p) { define i8 @or_not_xor_common_op_commute7(i8 %x, i8 %y, i8 %p) { ; CHECK-LABEL: @or_not_xor_common_op_commute7( ; CHECK-NEXT: [[Z:%.*]] = sub i8 0, [[P:%.*]] -; CHECK-NEXT: [[NOTX:%.*]] = xor i8 [[X:%.*]], -1 -; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[Y:%.*]], [[X]] -; CHECK-NEXT: [[O1:%.*]] = or i8 [[Z]], [[NOTX]] -; CHECK-NEXT: [[O2:%.*]] = or i8 [[O1]], [[XOR]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[Y:%.*]], [[X:%.*]] +; CHECK-NEXT: [[NAND:%.*]] = xor i8 [[TMP1]], -1 +; CHECK-NEXT: [[O2:%.*]] = or i8 [[NAND]], [[Z]] ; CHECK-NEXT: ret i8 [[O2]] ; %z = sub i8 0, %p ; thwart complexity-based canonicalizaion @@ -926,6 +919,8 @@ define i8 @or_not_xor_common_op_commute7(i8 %x, i8 %y, i8 %p) { ret i8 %o2 } +; negative test - too many uses for basic check (but this could be enhanced) + define i8 @or_not_xor_common_op_use1(i8 %x, i8 %y, i8 %z) { ; CHECK-LABEL: @or_not_xor_common_op_use1( ; CHECK-NEXT: [[NOTX:%.*]] = xor i8 [[X:%.*]], -1 @@ -943,6 +938,8 @@ define i8 @or_not_xor_common_op_use1(i8 %x, i8 %y, i8 %z) { ret i8 %o2 } +; negative test - too many uses + define i8 @or_not_xor_common_op_use2(i8 %x, i8 %y, i8 %z) { ; CHECK-LABEL: @or_not_xor_common_op_use2( ; CHECK-NEXT: [[NOTX:%.*]] = xor i8 [[X:%.*]], -1 -- 2.7.4