From d2fe411570ea098f14e5796a2b005553a5e5f0f2 Mon Sep 17 00:00:00 2001 From: Craig Topper Date: Sun, 2 Jul 2017 01:15:51 +0000 Subject: [PATCH] [InstCombine] Fold (a | b) ^ (~a | ~b) --> ~(a ^ b) and (a & b) ^ (~a & ~b) --> ~(a ^ b) Summary: I came across this while thinking about what would happen if one of the operands in this xor pattern was itself a inverted (A & ~B) ^ (~A & B)-> (A^B). The patterns here assume that the (~a | ~b) will be demorganed to ~(a & b) first. Though I wonder if there's a multiple use case that would prevent the demorgan. Reviewers: spatel Reviewed By: spatel Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D34870 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@306967 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | 20 ++++++++++++++++-- test/Transforms/InstCombine/and-or-not.ll | 24 ++++++++-------------- test/Transforms/InstCombine/or-xor.ll | 24 ++++++++-------------- 3 files changed, 34 insertions(+), 34 deletions(-) diff --git a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index db98be2c98f..53f61d6a9c7 100644 --- a/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -2276,7 +2276,8 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { /// A ^ B can be specified using other logic ops in a variety of patterns. We /// can fold these early and efficiently by morphing an existing instruction. -static Instruction *foldXorToXor(BinaryOperator &I) { +static Instruction *foldXorToXor(BinaryOperator &I, + InstCombiner::BuilderTy &Builder) { assert(I.getOpcode() == Instruction::Xor); Value *Op0 = I.getOperand(0); Value *Op1 = I.getOperand(1); @@ -2323,6 +2324,21 @@ static Instruction *foldXorToXor(BinaryOperator &I) { return &I; } + // For the remaining cases we need to get rid of one of the operands. + if (!Op0->hasOneUse() && !Op1->hasOneUse()) + return nullptr; + + // (A | B) ^ ~(A & B) -> ~(A ^ B) + // (A | B) ^ ~(B & A) -> ~(A ^ B) + // (A & B) ^ ~(A | B) -> ~(A ^ B) + // (A & B) ^ ~(B | A) -> ~(A ^ B) + // Complexity sorting ensures the not will be on the right side. + if ((match(Op0, m_Or(m_Value(A), m_Value(B))) && + match(Op1, m_Not(m_c_And(m_Specific(A), m_Specific(B))))) || + (match(Op0, m_And(m_Value(A), m_Value(B))) && + match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))) + return BinaryOperator::CreateNot(Builder.CreateXor(A, B)); + return nullptr; } @@ -2381,7 +2397,7 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { if (Value *V = SimplifyXorInst(Op0, Op1, SQ.getWithInstruction(&I))) return replaceInstUsesWith(I, V); - if (Instruction *NewXor = foldXorToXor(I)) + if (Instruction *NewXor = foldXorToXor(I, *Builder)) return NewXor; // (A&B)^(A&C) -> A&(B^C) etc diff --git a/test/Transforms/InstCombine/and-or-not.ll b/test/Transforms/InstCombine/and-or-not.ll index 1baecb4a13a..04f7be01eaf 100644 --- a/test/Transforms/InstCombine/and-or-not.ll +++ b/test/Transforms/InstCombine/and-or-not.ll @@ -570,10 +570,8 @@ define i32 @xor_to_xnor1(float %fa, float %fb) { ; CHECK-LABEL: @xor_to_xnor1( ; CHECK-NEXT: [[A:%.*]] = fptosi float [[FA:%.*]] to i32 ; CHECK-NEXT: [[B:%.*]] = fptosi float [[FB:%.*]] to i32 -; CHECK-NEXT: [[OR1:%.*]] = or i32 [[A]], [[B]] -; CHECK-NEXT: [[OR2_DEMORGAN:%.*]] = and i32 [[A]], [[B]] -; CHECK-NEXT: [[OR2:%.*]] = xor i32 [[OR2_DEMORGAN]], -1 -; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[OR1]], [[OR2]] +; CHECK-NEXT: [[TMP1:%.*]] = xor i32 [[A]], [[B]] +; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[TMP1]], -1 ; CHECK-NEXT: ret i32 [[XOR]] ; %a = fptosi float %fa to i32 @@ -591,10 +589,8 @@ define i32 @xor_to_xnor2(float %fa, float %fb) { ; CHECK-LABEL: @xor_to_xnor2( ; CHECK-NEXT: [[A:%.*]] = fptosi float [[FA:%.*]] to i32 ; CHECK-NEXT: [[B:%.*]] = fptosi float [[FB:%.*]] to i32 -; CHECK-NEXT: [[OR1:%.*]] = or i32 [[A]], [[B]] -; CHECK-NEXT: [[OR2_DEMORGAN:%.*]] = and i32 [[B]], [[A]] -; CHECK-NEXT: [[OR2:%.*]] = xor i32 [[OR2_DEMORGAN]], -1 -; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[OR1]], [[OR2]] +; CHECK-NEXT: [[TMP1:%.*]] = xor i32 [[A]], [[B]] +; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[TMP1]], -1 ; CHECK-NEXT: ret i32 [[XOR]] ; %a = fptosi float %fa to i32 @@ -612,10 +608,8 @@ define i32 @xor_to_xnor3(float %fa, float %fb) { ; CHECK-LABEL: @xor_to_xnor3( ; CHECK-NEXT: [[A:%.*]] = fptosi float [[FA:%.*]] to i32 ; CHECK-NEXT: [[B:%.*]] = fptosi float [[FB:%.*]] to i32 -; CHECK-NEXT: [[OR1_DEMORGAN:%.*]] = and i32 [[A]], [[B]] -; CHECK-NEXT: [[OR1:%.*]] = xor i32 [[OR1_DEMORGAN]], -1 -; CHECK-NEXT: [[OR2:%.*]] = or i32 [[A]], [[B]] -; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[OR2]], [[OR1]] +; CHECK-NEXT: [[TMP1:%.*]] = xor i32 [[A]], [[B]] +; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[TMP1]], -1 ; CHECK-NEXT: ret i32 [[XOR]] ; %a = fptosi float %fa to i32 @@ -633,10 +627,8 @@ define i32 @xor_to_xnor4(float %fa, float %fb) { ; CHECK-LABEL: @xor_to_xnor4( ; CHECK-NEXT: [[A:%.*]] = fptosi float [[FA:%.*]] to i32 ; CHECK-NEXT: [[B:%.*]] = fptosi float [[FB:%.*]] to i32 -; CHECK-NEXT: [[OR1_DEMORGAN:%.*]] = and i32 [[A]], [[B]] -; CHECK-NEXT: [[OR1:%.*]] = xor i32 [[OR1_DEMORGAN]], -1 -; CHECK-NEXT: [[OR2:%.*]] = or i32 [[B]], [[A]] -; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[OR2]], [[OR1]] +; CHECK-NEXT: [[TMP1:%.*]] = xor i32 [[B]], [[A]] +; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[TMP1]], -1 ; CHECK-NEXT: ret i32 [[XOR]] ; %a = fptosi float %fa to i32 diff --git a/test/Transforms/InstCombine/or-xor.ll b/test/Transforms/InstCombine/or-xor.ll index 2164f0df8d2..947971c6c83 100644 --- a/test/Transforms/InstCombine/or-xor.ll +++ b/test/Transforms/InstCombine/or-xor.ll @@ -348,10 +348,8 @@ define i8 @test18(i8 %A, i8 %B) { ; ((x | y) ^ (~x | ~y)) -> ~(x ^ y) define i32 @test19(i32 %x, i32 %y) { ; CHECK-LABEL: @test19( -; CHECK-NEXT: [[OR1:%.*]] = or i32 [[X:%.*]], [[Y:%.*]] -; CHECK-NEXT: [[OR2_DEMORGAN:%.*]] = and i32 [[X]], [[Y]] -; CHECK-NEXT: [[OR2:%.*]] = xor i32 [[OR2_DEMORGAN]], -1 -; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[OR1]], [[OR2]] +; CHECK-NEXT: [[TMP1:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[TMP1]], -1 ; CHECK-NEXT: ret i32 [[XOR]] ; %noty = xor i32 %y, -1 @@ -365,10 +363,8 @@ define i32 @test19(i32 %x, i32 %y) { ; ((x | y) ^ (~y | ~x)) -> ~(x ^ y) define i32 @test20(i32 %x, i32 %y) { ; CHECK-LABEL: @test20( -; CHECK-NEXT: [[OR1:%.*]] = or i32 [[X:%.*]], [[Y:%.*]] -; CHECK-NEXT: [[OR2_DEMORGAN:%.*]] = and i32 [[Y]], [[X]] -; CHECK-NEXT: [[OR2:%.*]] = xor i32 [[OR2_DEMORGAN]], -1 -; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[OR1]], [[OR2]] +; CHECK-NEXT: [[TMP1:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[TMP1]], -1 ; CHECK-NEXT: ret i32 [[XOR]] ; %noty = xor i32 %y, -1 @@ -382,10 +378,8 @@ define i32 @test20(i32 %x, i32 %y) { ; ((~x | ~y) ^ (x | y)) -> ~(x ^ y) define i32 @test21(i32 %x, i32 %y) { ; CHECK-LABEL: @test21( -; CHECK-NEXT: [[OR1_DEMORGAN:%.*]] = and i32 [[X:%.*]], [[Y:%.*]] -; CHECK-NEXT: [[OR1:%.*]] = xor i32 [[OR1_DEMORGAN]], -1 -; CHECK-NEXT: [[OR2:%.*]] = or i32 [[X]], [[Y]] -; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[OR2]], [[OR1]] +; CHECK-NEXT: [[TMP1:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]] +; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[TMP1]], -1 ; CHECK-NEXT: ret i32 [[XOR]] ; %noty = xor i32 %y, -1 @@ -399,10 +393,8 @@ define i32 @test21(i32 %x, i32 %y) { ; ((~x | ~y) ^ (y | x)) -> ~(x ^ y) define i32 @test22(i32 %x, i32 %y) { ; CHECK-LABEL: @test22( -; CHECK-NEXT: [[OR1_DEMORGAN:%.*]] = and i32 [[X:%.*]], [[Y:%.*]] -; CHECK-NEXT: [[OR1:%.*]] = xor i32 [[OR1_DEMORGAN]], -1 -; CHECK-NEXT: [[OR2:%.*]] = or i32 [[Y]], [[X]] -; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[OR2]], [[OR1]] +; CHECK-NEXT: [[TMP1:%.*]] = xor i32 [[Y:%.*]], [[X:%.*]] +; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[TMP1]], -1 ; CHECK-NEXT: ret i32 [[XOR]] ; %noty = xor i32 %y, -1 -- 2.11.0