[InstSimplify] Handle (~A & ~B) | (~A ^ B) -> ~A ^ B

[craig.topper]

Summary

The code Sanjay Patel moved over from InstCombine doesn't work properly if the 'and' has both inputs as nots because we used a commuted op matcher on the 'and' first. But this will bind to the first 'not' on 'and' when there could be two 'not's. InstCombine could rely on DeMorgan to ensure the 'and' wouldn't have two 'not's eventually, but InstSimplify can't rely on that.

This patch matches the xor first then checks for the ands and allows a not of either operand of the xor.

[spatel]

Nice catch. Just curious - did you find that by inspection or did it show up as a regression somewhere? I wonder if we should ease the one-use restrictions in the DeMorgan code in instcombine.

lib/Analysis/InstructionSimplify.cpp

1887–1888 ↗

(On Diff #96482)

Can you add the other 2 patterns to the comment here? I get nervous when the listed formulas don't match the code...because usually we're missing some commuted possibility.

[craig.topper]

It was by inspection. I've been nervous about commutable matchers with m_Not (or really any opcode) that use m_Value and not m_Specific.

[craig.topper]

Add additional comments.

[spatel]

LGTM.

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyOrInst(Value *Op0, Value *Op1, const Query &Q,
 
   // A | ~(A & ?) = -1
   if (match(Op1, m_Not(m_And(m_Value(A), m_Value(B)))) &&
       (A == Op0 || B == Op0))
     return Constant::getAllOnesValue(Op0->getType());
 
   // (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_Xor(m_Specific(A), m_Specific(B))))
+  // (A & ~B) | (B ^ A) -> (B ^ A)
+  // (~B & A) | (B ^ A) -> (B ^ A)
+  if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
+      (match(Op0, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
+       match(Op0, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
     return Op1;
 
   // Commute the 'or' operands.
   // (A ^ B) | (A & ~B) -> (A ^ B)
   // (A ^ B) | (~B & A) -> (A ^ B)
-  if (match(Op1, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
-      match(Op0, m_Xor(m_Specific(A), m_Specific(B))))
+  // (B ^ A) | (A & ~B) -> (B ^ A)
+  // (B ^ A) | (~B & A) -> (B ^ A)
+  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
+      (match(Op1, m_c_And(m_Specific(A), m_Not(m_Specific(B)))) ||
+       match(Op1, m_c_And(m_Not(m_Specific(A)), m_Specific(B)))))
     return Op0;
 
   if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) {
     if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) {
       if (Value *V = SimplifyOrOfICmps(ICILHS, ICIRHS))
         return V;
       if (Value *V = SimplifyOrOfICmps(ICIRHS, ICILHS))
         return V;

llvm/trunk/test/Transforms/InstSimplify/AndOrXor.ll

 ;
   %xor = xor i32 %a, %b
   %neg = xor i32 %b, -1
   %and = and i32 %neg, %a
   %or = or i32 %xor, %and
   ret i32 %or
 }
 
+; (~A & ~B) | (~A ^ B) -> ~A ^ B
+
+define i32 @test45(i32 %a, i32 %b) {
+; CHECK-LABEL: @test45(
+; CHECK-NEXT:    [[NEGB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A:%.*]], [[NEGB]]
+; CHECK-NEXT:    ret i32 [[XOR]]
+;
+  %nega = xor i32 %a, -1
+  %negb = xor i32 %b, -1
+  %and = and i32 %nega, %negb
+  %xor = xor i32 %a, %negb
+  %or = or i32 %and, %xor
+  ret i32 %or
+}
+
+define i32 @test45_commuted_and(i32 %a, i32 %b) {
+; CHECK-LABEL: @test45(
+; CHECK-NEXT:    [[NEGB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A:%.*]], [[NEGB]]
+; CHECK-NEXT:    ret i32 [[XOR]]
+;
+  %nega = xor i32 %a, -1
+  %negb = xor i32 %b, -1
+  %and = and i32 %negb, %nega
+  %xor = xor i32 %a, %negb
+  %or = or i32 %and, %xor
+  ret i32 %or
+}
+
+; Commute operands of the 'or'.
+; (~A ^ B) | (~A & ~B) -> ~A ^ B
+
+define i32 @test46(i32 %a, i32 %b) {
+; CHECK-LABEL: @test46(
+; CHECK-NEXT:    [[NEGB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A:%.*]], [[NEGB]]
+; CHECK-NEXT:    ret i32 [[XOR]]
+;
+  %nega = xor i32 %a, -1
+  %negb = xor i32 %b, -1
+  %and = and i32 %nega, %negb
+  %xor = xor i32 %a, %negb
+  %or = or i32 %xor, %and
+  ret i32 %or
+}
+
+; (~A & ~B) | (~A ^ B) -> ~A ^ B
+
+define i32 @test46_commuted_and(i32 %a, i32 %b) {
+; CHECK-LABEL: @test45(
+; CHECK-NEXT:    [[NEGB:%.*]] = xor i32 [[B:%.*]], -1
+; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[A:%.*]], [[NEGB]]
+; CHECK-NEXT:    ret i32 [[XOR]]
+;
+  %nega = xor i32 %a, -1
+  %negb = xor i32 %b, -1
+  %and = and i32 %negb, %nega
+  %xor = xor i32 %a, %negb
+  %or = or i32 %xor, %and
+  ret i32 %or
+}