From 892648b18a8cc3b8a08528112adfa74bdd432f8b Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Tue, 23 Nov 2021 16:46:55 -0500 Subject: [PATCH] [InstSimplify] fold xor logic of 2 variables (a & b) ^ (~a | b) --> ~a I was looking for a shortcut to reduce some of the complex logic folds that are currently up for review (D113216 and others in that stack), and I found this missing from instcombine/instsimplify. There is a trade-off in putting it into instsimplify: because we can't create new values here, we need a strict 'not' op (no undef elements). Otherwise, the fold is not valid: https://alive2.llvm.org/ce/z/k_AGGj If this was in instcombine instead, we could create the proper 'not'. But having the fold here benefits other passes like GVN that use instsimplify as an analysis. There is a related fold where 'and' and 'or' are swapped, and that is planned as a follow-up commit. Differential Revision: https://reviews.llvm.org/D114462 --- llvm/lib/Analysis/InstructionSimplify.cpp | 18 +++++++++ llvm/test/Transforms/InstSimplify/xor.ll | 62 +++++++++++-------------------- 2 files changed, 40 insertions(+), 40 deletions(-) diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp index 864eeea..863533c 100644 --- a/llvm/lib/Analysis/InstructionSimplify.cpp +++ b/llvm/lib/Analysis/InstructionSimplify.cpp @@ -2414,6 +2414,24 @@ static Value *SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q, match(Op1, m_Not(m_Specific(Op0)))) return Constant::getAllOnesValue(Op0->getType()); + // (~A | B) ^ (A & B) --> ~A -- There are 8 commuted variants. + // The 'not' op must contain a complete -1 operand (no undef elements for + // vector) for the transform to be safe. + auto matchNotA = [](Value *X, Value *Y) -> Value * { + Value *A, *B, *NotA; + const APInt *C; + if (match(X, m_c_Or(m_CombineAnd(m_Xor(m_Value(A), m_APIntForbidUndef(C)), + m_Value(NotA)), + m_Value(B))) && + match(Y, m_c_And(m_Specific(A), m_Specific(B))) && C->isAllOnes()) + return NotA; + return nullptr; + }; + if (Value *NotA = matchNotA(Op0, Op1)) + return NotA; + if (Value *NotA = matchNotA(Op1, Op0)) + return NotA; + if (Value *V = simplifyLogicOfAddSub(Op0, Op1, Instruction::Xor)) return V; diff --git a/llvm/test/Transforms/InstSimplify/xor.ll b/llvm/test/Transforms/InstSimplify/xor.ll index 9202489..481096b 100644 --- a/llvm/test/Transforms/InstSimplify/xor.ll +++ b/llvm/test/Transforms/InstSimplify/xor.ll @@ -11,11 +11,8 @@ define i32 @poison(i32 %x) { define i4 @xor_and_or_not_commute0(i4 %a, i4 %b) { ; CHECK-LABEL: @xor_and_or_not_commute0( -; CHECK-NEXT: [[AND:%.*]] = and i4 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[NOT:%.*]] = xor i4 [[A]], -1 -; CHECK-NEXT: [[OR:%.*]] = or i4 [[NOT]], [[B]] -; CHECK-NEXT: [[R:%.*]] = xor i4 [[AND]], [[OR]] -; CHECK-NEXT: ret i4 [[R]] +; CHECK-NEXT: [[NOT:%.*]] = xor i4 [[A:%.*]], -1 +; CHECK-NEXT: ret i4 [[NOT]] ; %and = and i4 %a, %b %not = xor i4 %a, -1 @@ -26,11 +23,8 @@ define i4 @xor_and_or_not_commute0(i4 %a, i4 %b) { define <2 x i4> @xor_and_or_not_commute1(<2 x i4> %a, <2 x i4> %b) { ; CHECK-LABEL: @xor_and_or_not_commute1( -; CHECK-NEXT: [[AND:%.*]] = and <2 x i4> [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[NOT:%.*]] = xor <2 x i4> [[A]], -; CHECK-NEXT: [[OR:%.*]] = or <2 x i4> [[NOT]], [[B]] -; CHECK-NEXT: [[R:%.*]] = xor <2 x i4> [[OR]], [[AND]] -; CHECK-NEXT: ret <2 x i4> [[R]] +; CHECK-NEXT: [[NOT:%.*]] = xor <2 x i4> [[A:%.*]], +; CHECK-NEXT: ret <2 x i4> [[NOT]] ; %and = and <2 x i4> %a, %b %not = xor <2 x i4> %a, @@ -41,11 +35,8 @@ define <2 x i4> @xor_and_or_not_commute1(<2 x i4> %a, <2 x i4> %b) { define i74 @xor_and_or_not_commute2(i74 %a, i74 %b) { ; CHECK-LABEL: @xor_and_or_not_commute2( -; CHECK-NEXT: [[AND:%.*]] = and i74 [[B:%.*]], [[A:%.*]] -; CHECK-NEXT: [[NOT:%.*]] = xor i74 [[A]], -1 -; CHECK-NEXT: [[OR:%.*]] = or i74 [[NOT]], [[B]] -; CHECK-NEXT: [[R:%.*]] = xor i74 [[AND]], [[OR]] -; CHECK-NEXT: ret i74 [[R]] +; CHECK-NEXT: [[NOT:%.*]] = xor i74 [[A:%.*]], -1 +; CHECK-NEXT: ret i74 [[NOT]] ; %and = and i74 %b, %a %not = xor i74 %a, -1 @@ -56,11 +47,8 @@ define i74 @xor_and_or_not_commute2(i74 %a, i74 %b) { define <2 x i4> @xor_and_or_not_commute3(<2 x i4> %a, <2 x i4> %b) { ; CHECK-LABEL: @xor_and_or_not_commute3( -; CHECK-NEXT: [[AND:%.*]] = and <2 x i4> [[B:%.*]], [[A:%.*]] -; CHECK-NEXT: [[NOT:%.*]] = xor <2 x i4> [[A]], -; CHECK-NEXT: [[OR:%.*]] = or <2 x i4> [[NOT]], [[B]] -; CHECK-NEXT: [[R:%.*]] = xor <2 x i4> [[OR]], [[AND]] -; CHECK-NEXT: ret <2 x i4> [[R]] +; CHECK-NEXT: [[NOT:%.*]] = xor <2 x i4> [[A:%.*]], +; CHECK-NEXT: ret <2 x i4> [[NOT]] ; %and = and <2 x i4> %b, %a %not = xor <2 x i4> %a, @@ -71,11 +59,8 @@ define <2 x i4> @xor_and_or_not_commute3(<2 x i4> %a, <2 x i4> %b) { define i8 @xor_and_or_not_commute4(i8 %a, i8 %b) { ; CHECK-LABEL: @xor_and_or_not_commute4( -; CHECK-NEXT: [[AND:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[NOT:%.*]] = xor i8 [[A]], -1 -; CHECK-NEXT: [[OR:%.*]] = or i8 [[B]], [[NOT]] -; CHECK-NEXT: [[R:%.*]] = xor i8 [[AND]], [[OR]] -; CHECK-NEXT: ret i8 [[R]] +; CHECK-NEXT: [[NOT:%.*]] = xor i8 [[A:%.*]], -1 +; CHECK-NEXT: ret i8 [[NOT]] ; %and = and i8 %a, %b %not = xor i8 %a, -1 @@ -86,11 +71,8 @@ define i8 @xor_and_or_not_commute4(i8 %a, i8 %b) { define i8 @xor_and_or_not_commute5(i8 %a, i8 %b) { ; CHECK-LABEL: @xor_and_or_not_commute5( -; CHECK-NEXT: [[AND:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[NOT:%.*]] = xor i8 [[A]], -1 -; CHECK-NEXT: [[OR:%.*]] = or i8 [[B]], [[NOT]] -; CHECK-NEXT: [[R:%.*]] = xor i8 [[OR]], [[AND]] -; CHECK-NEXT: ret i8 [[R]] +; CHECK-NEXT: [[NOT:%.*]] = xor i8 [[A:%.*]], -1 +; CHECK-NEXT: ret i8 [[NOT]] ; %and = and i8 %a, %b %not = xor i8 %a, -1 @@ -101,11 +83,8 @@ define i8 @xor_and_or_not_commute5(i8 %a, i8 %b) { define i8 @xor_and_or_not_commute6(i8 %a, i8 %b) { ; CHECK-LABEL: @xor_and_or_not_commute6( -; CHECK-NEXT: [[AND:%.*]] = and i8 [[B:%.*]], [[A:%.*]] -; CHECK-NEXT: [[NOT:%.*]] = xor i8 [[A]], -1 -; CHECK-NEXT: [[OR:%.*]] = or i8 [[B]], [[NOT]] -; CHECK-NEXT: [[R:%.*]] = xor i8 [[AND]], [[OR]] -; CHECK-NEXT: ret i8 [[R]] +; CHECK-NEXT: [[NOT:%.*]] = xor i8 [[A:%.*]], -1 +; CHECK-NEXT: ret i8 [[NOT]] ; %and = and i8 %b, %a %not = xor i8 %a, -1 @@ -116,11 +95,8 @@ define i8 @xor_and_or_not_commute6(i8 %a, i8 %b) { define i8 @xor_and_or_not_commute7(i8 %a, i8 %b) { ; CHECK-LABEL: @xor_and_or_not_commute7( -; CHECK-NEXT: [[AND:%.*]] = and i8 [[B:%.*]], [[A:%.*]] -; CHECK-NEXT: [[NOT:%.*]] = xor i8 [[A]], -1 -; CHECK-NEXT: [[OR:%.*]] = or i8 [[B]], [[NOT]] -; CHECK-NEXT: [[R:%.*]] = xor i8 [[OR]], [[AND]] -; CHECK-NEXT: ret i8 [[R]] +; CHECK-NEXT: [[NOT:%.*]] = xor i8 [[A:%.*]], -1 +; CHECK-NEXT: ret i8 [[NOT]] ; %and = and i8 %b, %a %not = xor i8 %a, -1 @@ -129,6 +105,8 @@ define i8 @xor_and_or_not_commute7(i8 %a, i8 %b) { ret i8 %r } +; negative test - must match specific values + define i4 @xor_and_or_not_wrong_val1(i4 %a, i4 %b, i4 %c) { ; CHECK-LABEL: @xor_and_or_not_wrong_val1( ; CHECK-NEXT: [[AND:%.*]] = and i4 [[A:%.*]], [[C:%.*]] @@ -144,6 +122,8 @@ define i4 @xor_and_or_not_wrong_val1(i4 %a, i4 %b, i4 %c) { ret i4 %r } +; negative test - must match specific values + define i4 @xor_and_or_not_wrong_val2(i4 %a, i4 %b, i4 %c) { ; CHECK-LABEL: @xor_and_or_not_wrong_val2( ; CHECK-NEXT: [[AND:%.*]] = and i4 [[C:%.*]], [[B:%.*]] @@ -159,6 +139,8 @@ define i4 @xor_and_or_not_wrong_val2(i4 %a, i4 %b, i4 %c) { ret i4 %r } +; negative test - incorrect to propagate undef element + define <2 x i4> @xor_and_or_not_undef_elt(<2 x i4> %a, <2 x i4> %b) { ; CHECK-LABEL: @xor_and_or_not_undef_elt( ; CHECK-NEXT: [[AND:%.*]] = and <2 x i4> [[B:%.*]], [[A:%.*]] -- 2.7.4