From d13b0bfdacb84b1653245fa1d0ac66819b84cd62 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Sun, 23 Apr 2017 16:03:00 +0000 Subject: [PATCH] [InstCombine] add pattern matches for commuted variants of xor-to-xor There's probably some better way to write this that eliminates the code duplication without hurting readability, but at least this eliminates the logic holes and is hopefully slightly more efficient than creating new instructions. llvm-svn: 301129 --- .../Transforms/InstCombine/InstCombineAndOrXor.cpp | 89 +++++++++++++--------- llvm/test/Transforms/InstCombine/and-or-not.ll | 14 +--- 2 files changed, 58 insertions(+), 45 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index f320f12..17a6fb9 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -2374,6 +2374,58 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) { return Changed ? &I : nullptr; } +/// 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) { + assert(I.getOpcode() == Instruction::Xor); + Value *Op0 = I.getOperand(0); + Value *Op1 = I.getOperand(1); + Value *A, *B; + + // There are 4 commuted variants for each of the basic patterns. + + // (A & B) ^ (A | B) -> A ^ B + // (A & B) ^ (B | A) -> A ^ B + // (A | B) ^ (A & B) -> A ^ B + // (A | B) ^ (B & A) -> A ^ B + if ((match(Op0, m_And(m_Value(A), m_Value(B))) && + match(Op1, m_c_Or(m_Specific(A), m_Specific(B)))) || + (match(Op0, m_Or(m_Value(A), m_Value(B))) && + match(Op1, m_c_And(m_Specific(A), m_Specific(B))))) { + I.setOperand(0, A); + I.setOperand(1, B); + return &I; + } + + // (A | ~B) ^ (~A | B) -> A ^ B + // (~B | A) ^ (~A | B) -> A ^ B + // (~A | B) ^ (A | ~B) -> A ^ B + // (B | ~A) ^ (A | ~B) -> A ^ B + if ((match(Op0, m_c_Or(m_Value(A), m_Not(m_Value(B)))) && + match(Op1, m_Or(m_Not(m_Specific(A)), m_Specific(B)))) || + (match(Op0, m_c_Or(m_Not(m_Value(A)), m_Value(B))) && + match(Op1, m_Or(m_Specific(A), m_Not(m_Specific(B)))))) { + I.setOperand(0, A); + I.setOperand(1, B); + return &I; + } + + // (A & ~B) ^ (~A & B) -> A ^ B + // (~B & A) ^ (~A & B) -> A ^ B + // (~A & B) ^ (A & ~B) -> A ^ B + // (B & ~A) ^ (A & ~B) -> A ^ B + if ((match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) && + match(Op1, m_And(m_Not(m_Specific(A)), m_Specific(B)))) || + (match(Op0, m_c_And(m_Not(m_Value(A)), m_Value(B))) && + match(Op1, m_And(m_Specific(A), m_Not(m_Specific(B)))))) { + I.setOperand(0, A); + I.setOperand(1, B); + return &I; + } + + return nullptr; +} + // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches // here. We should standardize that construct where it is needed or choose some // other way to ensure that commutated variants of patterns are not missed. @@ -2387,6 +2439,9 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { if (Value *V = SimplifyXorInst(Op0, Op1, DL, &TLI, &DT, &AC)) return replaceInstUsesWith(I, V); + if (Instruction *NewXor = foldXorToXor(I)) + return NewXor; + // (A&B)^(A&C) -> A&(B^C) etc if (Value *V = SimplifyUsingDistributiveLaws(I)) return replaceInstUsesWith(I, V); @@ -2569,40 +2624,6 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) { { Value *A, *B, *C, *D; - // (A & B)^(A | B) -> A ^ B - if (match(Op0, m_And(m_Value(A), m_Value(B))) && - match(Op1, m_Or(m_Value(C), m_Value(D)))) { - if ((A == C && B == D) || (A == D && B == C)) - return BinaryOperator::CreateXor(A, B); - } - // (A | B)^(A & B) -> A ^ B - if (match(Op0, m_Or(m_Value(A), m_Value(B))) && - match(Op1, m_And(m_Value(C), m_Value(D)))) { - if ((A == C && B == D) || (A == D && B == C)) - return BinaryOperator::CreateXor(A, B); - } - // (A | ~B) ^ (~A | B) -> A ^ B - // (~B | A) ^ (~A | B) -> A ^ B - if (match(Op0, m_c_Or(m_Value(A), m_Not(m_Value(B)))) && - match(Op1, m_Or(m_Not(m_Specific(A)), m_Specific(B)))) - return BinaryOperator::CreateXor(A, B); - - // (~A | B) ^ (A | ~B) -> A ^ B - if (match(Op0, m_Or(m_Not(m_Value(A)), m_Value(B))) && - match(Op1, m_Or(m_Specific(A), m_Not(m_Specific(B))))) { - return BinaryOperator::CreateXor(A, B); - } - // (A & ~B) ^ (~A & B) -> A ^ B - // (~B & A) ^ (~A & B) -> A ^ B - if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) && - match(Op1, m_And(m_Not(m_Specific(A)), m_Specific(B)))) - return BinaryOperator::CreateXor(A, B); - - // (~A & B) ^ (A & ~B) -> A ^ B - if (match(Op0, m_And(m_Not(m_Value(A)), m_Value(B))) && - match(Op1, m_And(m_Specific(A), m_Not(m_Specific(B))))) { - return BinaryOperator::CreateXor(A, B); - } // (A ^ C)^(A | B) -> ((~A) & B) ^ C if (match(Op0, m_Xor(m_Value(D), m_Value(C))) && match(Op1, m_Or(m_Value(A), m_Value(B)))) { diff --git a/llvm/test/Transforms/InstCombine/and-or-not.ll b/llvm/test/Transforms/InstCombine/and-or-not.ll index 48ae620..2f7afdf 100644 --- a/llvm/test/Transforms/InstCombine/and-or-not.ll +++ b/llvm/test/Transforms/InstCombine/and-or-not.ll @@ -124,7 +124,7 @@ define i32 @xor_to_xor4(i32 %a, i32 %b) { ; (a | ~b) ^ (~a | b) --> a ^ b -; In the next 8 tests, cast instructions are used to thwart operand complexity +; In the next 8 tests, cast instructions are used to thwart operand complexity ; canonicalizations, so we can test all of the commuted patterns. define i32 @xor_to_xor5(float %fa, float %fb) { @@ -150,11 +150,7 @@ define i32 @xor_to_xor6(float %fa, float %fb) { ; CHECK-LABEL: @xor_to_xor6( ; CHECK-NEXT: [[A:%.*]] = fptosi float %fa to i32 ; CHECK-NEXT: [[B:%.*]] = fptosi float %fb to i32 -; CHECK-NEXT: [[NOTA:%.*]] = xor i32 [[A]], -1 -; CHECK-NEXT: [[NOTB:%.*]] = xor i32 [[B]], -1 -; CHECK-NEXT: [[OR1:%.*]] = or i32 [[A]], [[NOTB]] -; CHECK-NEXT: [[OR2:%.*]] = or i32 [[B]], [[NOTA]] -; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[OR1]], [[OR2]] +; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[B]], [[A]] ; CHECK-NEXT: ret i32 [[XOR]] ; %a = fptosi float %fa to i32 @@ -230,11 +226,7 @@ define i32 @xor_to_xor10(float %fa, float %fb) { ; CHECK-LABEL: @xor_to_xor10( ; CHECK-NEXT: [[A:%.*]] = fptosi float %fa to i32 ; CHECK-NEXT: [[B:%.*]] = fptosi float %fb to i32 -; CHECK-NEXT: [[NOTA:%.*]] = xor i32 [[A]], -1 -; CHECK-NEXT: [[NOTB:%.*]] = xor i32 [[B]], -1 -; CHECK-NEXT: [[AND1:%.*]] = and i32 [[A]], [[NOTB]] -; CHECK-NEXT: [[AND2:%.*]] = and i32 [[B]], [[NOTA]] -; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[AND1]], [[AND2]] +; CHECK-NEXT: [[XOR:%.*]] = xor i32 [[B]], [[A]] ; CHECK-NEXT: ret i32 [[XOR]] ; %a = fptosi float %fa to i32 -- 2.7.4