[InstCombine] Fold (a | b) ^ (~a | ~b) --> ~(a ^ b) and (a & b) ^ (~a & ~b) --> ~(a ^ b)

[craig.topper]

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.

[spatel]

LGTM.

llvm/trunk/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

// that this transformation will allow the new ORs to be optimized.
     }
   }
 
   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) {
+static Instruction *foldXorToXor(BinaryOperator &I,
+                                 InstCombiner::BuilderTy &Builder) {
   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
if ((match(Op0, m_And(m_Value(A), m_Not(m_Value(B)))) &&
        match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))) ||
       (match(Op0, m_And(m_Not(m_Value(A)), m_Value(B))) &&
        match(Op1, m_c_And(m_Specific(A), m_Not(m_Specific(B)))))) {
     I.setOperand(0, A);
     I.setOperand(1, B);
     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;
 }
 
 Value *InstCombiner::foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
   if (PredicatesFoldable(LHS->getPredicate(), RHS->getPredicate())) {
     if (LHS->getOperand(0) == RHS->getOperand(1) &&
         LHS->getOperand(1) == RHS->getOperand(0))
       LHS->swapOperands();
Instruction *InstCombiner::visitXor(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   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
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
   // See if we can simplify any instructions used by the instruction whose sole
   // purpose is to compute bits we don't care about.

llvm/trunk/test/Transforms/InstCombine/and-or-not.ll

;
   ret i32 %mul2
 }
 
 ; (a | b) ^ (~a | ~b) --> ~(a ^ b)
 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
   %b = fptosi float %fb to i32
   %nota = xor i32 %a, -1
   %notb = xor i32 %b, -1
   %or1 = or i32 %a, %b
   %or2 = or i32 %nota, %notb
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }
 
 ; (a | b) ^ (~b | ~a) --> ~(a ^ b)
 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
   %b = fptosi float %fb to i32
   %nota = xor i32 %a, -1
   %notb = xor i32 %b, -1
   %or1 = or i32 %a, %b
   %or2 = or i32 %notb, %nota
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }
 
 ; (~a | ~b) ^ (a | b) --> ~(a ^ b)
 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
   %b = fptosi float %fb to i32
   %nota = xor i32 %a, -1
   %notb = xor i32 %b, -1
   %or1 = or i32 %nota, %notb
   %or2 = or i32 %a, %b
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }
 
 ; (~a | ~b) ^ (b | a) --> ~(a ^ b)
 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
   %b = fptosi float %fb to i32
   %nota = xor i32 %a, -1
   %notb = xor i32 %b, -1
   %or1 = or i32 %nota, %notb
   %or2 = or i32 %b, %a
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }

llvm/trunk/test/Transforms/InstCombine/or-xor.ll

;
   %or = or i8 %xor2, %xor1
   %res = mul i8 %or, %xor2 ; to increase the use count for the xor
   ret i8 %res
 }
 
 ; ((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
   %notx = xor i32 %x, -1
   %or1 = or i32 %x, %y
   %or2 = or i32 %notx, %noty
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }
 
 ; ((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
   %notx = xor i32 %x, -1
   %or1 = or i32 %x, %y
   %or2 = or i32 %noty, %notx
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }
 
 ; ((~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
   %notx = xor i32 %x, -1
   %or1 = or i32 %notx, %noty
   %or2 = or i32 %x, %y
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }
 
 ; ((~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
   %notx = xor i32 %x, -1
   %or1 = or i32 %notx, %noty
   %or2 = or i32 %y, %x
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }