From 308ca349cbc5fa891b08c525084fc86017bdc498 Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Sat, 2 Apr 2022 23:54:33 +0300 Subject: [PATCH] [InstCombine] Fold `(X | C2) ^ C1 --> (X & ~C2) ^ (C1^C2)` These two are equivalent, and i *think* the `and` form is more-ish canonical. General proof: https://alive2.llvm.org/ce/z/RrF5s6 If constant on the (outer) `xor` is an `undef`, the whole lane is dead: https://alive2.llvm.org/ce/z/mu4Sh2 However, if the constant on the (inner) `or` is an `undef`, we must sanitize it first: https://alive2.llvm.org/ce/z/MHYJL7 I guess, producing a zero `and`-mask is optimal in that case. alive-tv is happy about the entirety of `xor-of-or.ll`. --- .../Transforms/InstCombine/InstCombineAndOrXor.cpp | 14 ++++++++- llvm/test/Transforms/InstCombine/and.ll | 4 +-- llvm/test/Transforms/InstCombine/apint-and.ll | 8 ++--- llvm/test/Transforms/InstCombine/demorgan.ll | 4 +-- llvm/test/Transforms/InstCombine/or-xor.ll | 20 ++++++------ llvm/test/Transforms/InstCombine/xor-of-or.ll | 36 +++++++++++----------- llvm/test/Transforms/InstCombine/xor.ll | 4 +-- 7 files changed, 51 insertions(+), 39 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index d5f7a1f..f68787a 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -3566,8 +3566,20 @@ Instruction *InstCombinerImpl::visitXor(BinaryOperator &I) { Value *X, *Y; Constant *C1; if (match(Op1, m_Constant(C1))) { - // Use DeMorgan and reassociation to eliminate a 'not' op. Constant *C2; + + if (match(Op0, m_OneUse(m_Or(m_Value(X), m_ImmConstant(C2)))) && + match(C1, m_ImmConstant())) { + // (X | C2) ^ C1 --> (X & ~C2) ^ (C1^C2) + C2 = Constant::replaceUndefsWith( + C2, Constant::getAllOnesValue(C2->getType()->getScalarType())); + Value *And = Builder.CreateAnd( + X, Constant::mergeUndefsWith(ConstantExpr::getNot(C2), C1)); + return BinaryOperator::CreateXor( + And, Constant::mergeUndefsWith(ConstantExpr::getXor(C1, C2), C1)); + } + + // Use DeMorgan and reassociation to eliminate a 'not' op. if (match(Op0, m_OneUse(m_Or(m_Not(m_Value(X)), m_Constant(C2))))) { // (~X | C2) ^ C1 --> ((X & ~C2) ^ -1) ^ C1 --> (X & ~C2) ^ ~C1 Value *And = Builder.CreateAnd(X, ConstantExpr::getNot(C2)); diff --git a/llvm/test/Transforms/InstCombine/and.ll b/llvm/test/Transforms/InstCombine/and.ll index b249115..6c6556a 100644 --- a/llvm/test/Transforms/InstCombine/and.ll +++ b/llvm/test/Transforms/InstCombine/and.ll @@ -133,8 +133,8 @@ define i32 @test10(i32 %A) { define i32 @test11(i32 %A, i32* %P) { ; CHECK-LABEL: @test11( -; CHECK-NEXT: [[B:%.*]] = or i32 [[A:%.*]], 3 -; CHECK-NEXT: [[C:%.*]] = xor i32 [[B]], 12 +; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[A:%.*]], -4 +; CHECK-NEXT: [[C:%.*]] = xor i32 [[TMP1]], 15 ; CHECK-NEXT: store i32 [[C]], i32* [[P:%.*]], align 4 ; CHECK-NEXT: ret i32 3 ; diff --git a/llvm/test/Transforms/InstCombine/apint-and.ll b/llvm/test/Transforms/InstCombine/apint-and.ll index 35bf904..793b25e5 100644 --- a/llvm/test/Transforms/InstCombine/apint-and.ll +++ b/llvm/test/Transforms/InstCombine/apint-and.ll @@ -42,8 +42,8 @@ define i1 @test4(i37 %x) { define i7 @test5(i7 %A, i7* %P) { ; CHECK-LABEL: @test5( -; CHECK-NEXT: [[B:%.*]] = or i7 [[A:%.*]], 3 -; CHECK-NEXT: [[C:%.*]] = xor i7 [[B]], 12 +; CHECK-NEXT: [[TMP1:%.*]] = and i7 [[A:%.*]], -4 +; CHECK-NEXT: [[C:%.*]] = xor i7 [[TMP1]], 15 ; CHECK-NEXT: store i7 [[C]], i7* [[P:%.*]], align 1 ; CHECK-NEXT: ret i7 3 ; @@ -103,8 +103,8 @@ define i1 @test11(i737 %x) { define i117 @test12(i117 %A, i117* %P) { ; CHECK-LABEL: @test12( -; CHECK-NEXT: [[B:%.*]] = or i117 [[A:%.*]], 3 -; CHECK-NEXT: [[C:%.*]] = xor i117 [[B]], 12 +; CHECK-NEXT: [[TMP1:%.*]] = and i117 [[A:%.*]], -4 +; CHECK-NEXT: [[C:%.*]] = xor i117 [[TMP1]], 15 ; CHECK-NEXT: store i117 [[C]], i117* [[P:%.*]], align 4 ; CHECK-NEXT: ret i117 3 ; diff --git a/llvm/test/Transforms/InstCombine/demorgan.ll b/llvm/test/Transforms/InstCombine/demorgan.ll index 9ef17bb..bbc2475 100644 --- a/llvm/test/Transforms/InstCombine/demorgan.ll +++ b/llvm/test/Transforms/InstCombine/demorgan.ll @@ -384,8 +384,8 @@ define i32 @demorganize_constant1(i32 %a) { define i32 @demorganize_constant2(i32 %a) { ; CHECK-LABEL: @demorganize_constant2( -; CHECK-NEXT: [[AND:%.*]] = or i32 [[A:%.*]], 15 -; CHECK-NEXT: [[AND1:%.*]] = xor i32 [[AND]], -1 +; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[A:%.*]], -16 +; CHECK-NEXT: [[AND1:%.*]] = xor i32 [[TMP1]], -16 ; CHECK-NEXT: ret i32 [[AND1]] ; %and = or i32 %a, 15 diff --git a/llvm/test/Transforms/InstCombine/or-xor.ll b/llvm/test/Transforms/InstCombine/or-xor.ll index 0784c07..79c2141 100644 --- a/llvm/test/Transforms/InstCombine/or-xor.ll +++ b/llvm/test/Transforms/InstCombine/or-xor.ll @@ -433,8 +433,8 @@ define i8 @not_or(i8 %x) { define i8 @not_or_xor(i8 %x) { ; CHECK-LABEL: @not_or_xor( -; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[X:%.*]], -8 -; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[TMP1]], -13 +; CHECK-NEXT: [[NOTX:%.*]] = and i8 [[X:%.*]], -8 +; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[NOTX]], -13 ; CHECK-NEXT: ret i8 [[XOR]] ; %notx = xor i8 %x, -1 @@ -445,8 +445,8 @@ define i8 @not_or_xor(i8 %x) { define i8 @xor_or(i8 %x) { ; CHECK-LABEL: @xor_or( -; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[X:%.*]], 7 -; CHECK-NEXT: [[OR:%.*]] = xor i8 [[TMP1]], 32 +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[X:%.*]], -8 +; CHECK-NEXT: [[OR:%.*]] = xor i8 [[TMP1]], 39 ; CHECK-NEXT: ret i8 [[OR]] ; %xor = xor i8 %x, 32 @@ -456,8 +456,8 @@ define i8 @xor_or(i8 %x) { define i8 @xor_or2(i8 %x) { ; CHECK-LABEL: @xor_or2( -; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[X:%.*]], 7 -; CHECK-NEXT: [[OR:%.*]] = xor i8 [[TMP1]], 32 +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[X:%.*]], -8 +; CHECK-NEXT: [[OR:%.*]] = xor i8 [[TMP1]], 39 ; CHECK-NEXT: ret i8 [[OR]] ; %xor = xor i8 %x, 33 @@ -467,8 +467,8 @@ define i8 @xor_or2(i8 %x) { define i8 @xor_or_xor(i8 %x) { ; CHECK-LABEL: @xor_or_xor( -; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[X:%.*]], 7 -; CHECK-NEXT: [[XOR2:%.*]] = xor i8 [[TMP1]], 44 +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[X:%.*]], -8 +; CHECK-NEXT: [[XOR2:%.*]] = xor i8 [[TMP1]], 43 ; CHECK-NEXT: ret i8 [[XOR2]] ; %xor1 = xor i8 %x, 33 @@ -479,8 +479,8 @@ define i8 @xor_or_xor(i8 %x) { define i8 @or_xor_or(i8 %x) { ; CHECK-LABEL: @or_xor_or( -; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[X:%.*]], 39 -; CHECK-NEXT: [[OR2:%.*]] = xor i8 [[TMP1]], 8 +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[X:%.*]], -40 +; CHECK-NEXT: [[OR2:%.*]] = xor i8 [[TMP1]], 47 ; CHECK-NEXT: ret i8 [[OR2]] ; %or1 = or i8 %x, 33 diff --git a/llvm/test/Transforms/InstCombine/xor-of-or.ll b/llvm/test/Transforms/InstCombine/xor-of-or.ll index bfbe250..71690d2 100644 --- a/llvm/test/Transforms/InstCombine/xor-of-or.ll +++ b/llvm/test/Transforms/InstCombine/xor-of-or.ll @@ -16,8 +16,8 @@ define i4 @t0(i4 %x, i4 %y, i4 %z) { ; If the second operands are immediate constants, we can perform the fold. define i4 @t1(i4 %x) { ; CHECK-LABEL: @t1( -; CHECK-NEXT: [[I0:%.*]] = or i4 [[X:%.*]], -4 -; CHECK-NEXT: [[I1:%.*]] = xor i4 [[I0]], -6 +; CHECK-NEXT: [[TMP1:%.*]] = and i4 [[X:%.*]], 3 +; CHECK-NEXT: [[I1:%.*]] = xor i4 [[TMP1]], 6 ; CHECK-NEXT: ret i4 [[I1]] ; %i0 = or i4 %x, 12 ; 0b1100 @@ -42,8 +42,8 @@ define i4 @t2(i4 %x) { ; Splat constants are fine too. define <2 x i4> @t3(<2 x i4> %x) { ; CHECK-LABEL: @t3( -; CHECK-NEXT: [[I0:%.*]] = or <2 x i4> [[X:%.*]], -; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[I0]], +; CHECK-NEXT: [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], +; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[TMP1]], ; CHECK-NEXT: ret <2 x i4> [[I1]] ; %i0 = or <2 x i4> %x, @@ -54,8 +54,8 @@ define <2 x i4> @t3(<2 x i4> %x) { ; Non-splat constants are fine too. define <2 x i4> @t4(<2 x i4> %x) { ; CHECK-LABEL: @t4( -; CHECK-NEXT: [[I0:%.*]] = or <2 x i4> [[X:%.*]], -; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[I0]], +; CHECK-NEXT: [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], +; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[TMP1]], ; CHECK-NEXT: ret <2 x i4> [[I1]] ; %i0 = or <2 x i4> %x, @@ -66,8 +66,8 @@ define <2 x i4> @t4(<2 x i4> %x) { ; Partially-undef constants are fine. define <2 x i4> @t5(<2 x i4> %x) { ; CHECK-LABEL: @t5( -; CHECK-NEXT: [[I0:%.*]] = or <2 x i4> [[X:%.*]], -; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[I0]], +; CHECK-NEXT: [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], +; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[TMP1]], ; CHECK-NEXT: ret <2 x i4> [[I1]] ; %i0 = or <2 x i4> %x, @@ -76,8 +76,8 @@ define <2 x i4> @t5(<2 x i4> %x) { } define <2 x i4> @t6(<2 x i4> %x) { ; CHECK-LABEL: @t6( -; CHECK-NEXT: [[I0:%.*]] = or <2 x i4> [[X:%.*]], -; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[I0]], +; CHECK-NEXT: [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], +; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[TMP1]], ; CHECK-NEXT: ret <2 x i4> [[I1]] ; %i0 = or <2 x i4> %x, @@ -86,8 +86,8 @@ define <2 x i4> @t6(<2 x i4> %x) { } define <2 x i4> @t7(<2 x i4> %x) { ; CHECK-LABEL: @t7( -; CHECK-NEXT: [[I0:%.*]] = or <2 x i4> [[X:%.*]], -; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[I0]], +; CHECK-NEXT: [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], +; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[TMP1]], ; CHECK-NEXT: ret <2 x i4> [[I1]] ; %i0 = or <2 x i4> %x, @@ -98,8 +98,8 @@ define <2 x i4> @t7(<2 x i4> %x) { ; Partially-poison constants are fine. define <2 x i4> @t8(<2 x i4> %x) { ; CHECK-LABEL: @t8( -; CHECK-NEXT: [[I0:%.*]] = or <2 x i4> [[X:%.*]], -; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[I0]], +; CHECK-NEXT: [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], +; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[TMP1]], ; CHECK-NEXT: ret <2 x i4> [[I1]] ; %i0 = or <2 x i4> %x, @@ -108,8 +108,8 @@ define <2 x i4> @t8(<2 x i4> %x) { } define <2 x i4> @t9(<2 x i4> %x) { ; CHECK-LABEL: @t9( -; CHECK-NEXT: [[I0:%.*]] = or <2 x i4> [[X:%.*]], -; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[I0]], +; CHECK-NEXT: [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], +; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[TMP1]], ; CHECK-NEXT: ret <2 x i4> [[I1]] ; %i0 = or <2 x i4> %x, @@ -118,8 +118,8 @@ define <2 x i4> @t9(<2 x i4> %x) { } define <2 x i4> @t10(<2 x i4> %x) { ; CHECK-LABEL: @t10( -; CHECK-NEXT: [[I0:%.*]] = or <2 x i4> [[X:%.*]], -; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[I0]], +; CHECK-NEXT: [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], +; CHECK-NEXT: [[I1:%.*]] = xor <2 x i4> [[TMP1]], ; CHECK-NEXT: ret <2 x i4> [[I1]] ; %i0 = or <2 x i4> %x, diff --git a/llvm/test/Transforms/InstCombine/xor.ll b/llvm/test/Transforms/InstCombine/xor.ll index d06460a..ec61b37 100644 --- a/llvm/test/Transforms/InstCombine/xor.ll +++ b/llvm/test/Transforms/InstCombine/xor.ll @@ -623,8 +623,8 @@ define i8 @xor_and_not(i8 %x, i8* %p) { ; CHECK-LABEL: @xor_and_not( ; CHECK-NEXT: [[NX:%.*]] = xor i8 [[X:%.*]], -1 ; CHECK-NEXT: store i8 [[NX]], i8* [[P:%.*]], align 1 -; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[X]], -43 -; CHECK-NEXT: [[R:%.*]] = xor i8 [[TMP1]], -32 +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[X]], 42 +; CHECK-NEXT: [[R:%.*]] = xor i8 [[TMP1]], 53 ; CHECK-NEXT: ret i8 [[R]] ; %nx = xor i8 %x, -1 -- 2.7.4