[InstSimplify] fold xor logic of 2 variables

[spatel]

Summary

(a & b) ^ (~a | b) --> ~a

I was looking for a shortcut to reduce some of the complex logic folds that are currently up for review (D113216 and others in that stack), and I found this missing from instcombine/instsimplify.

There is a trade-off in putting it into instsimplify: because we can't create new values here, we need a strict 'not' op (no undef elements). Otherwise, the fold is not valid:
https://alive2.llvm.org/ce/z/k_AGGj

If this was in instcombine instead, we could create the proper 'not'. But having the fold here benefits other passes like GVN that use instsimplify as an analysis. If I'm seeing it correctly, this is enough to catch the cases in D113216 at -O2 without needing to add more pattern matching to instcombine.

[spatel]

Note: we miss the sibling with swapped and/or too, and it doesn't need a 'not' op, so it would clearly be best placed in instsimplify:
https://alive2.llvm.org/ce/z/7LbWeV

[rampitec]

LGTM.

Thanks Sanjay! This really helps D113216 with -O3, but then not a more complex version of it which needs demorganing and reassociation:

; (~a & ~b & c) | ~(a | (b | c)) -> ~(a | b)
; (~a & ~b & c) | ~(b | (a | c)) -> ~(a | b)

define i32 @not_and_not_and_or_not_or_or(i32 %a, i32 %b, i32 %c) {
; CHECK-LABEL: @not_and_not_and_or_not_or_or(
; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
; CHECK-NEXT:    ret i32 [[NOT2]]
;
  %or1 = or i32 %b, %c
  %or2 = or i32 %or1, %a
  %not1 = xor i32 %or2, -1
  %nota = xor i32 %a, -1
  %notb = xor i32 %b, -1
  %and1 = and i32 %nota, %notb
  %and2 = and i32 %and1, %c
  %or4 = or i32 %and2, %not1
  call void @use(i32 %nota)
  call void @use(i32 %notb)
  ret i32 %or4
}

declare void @use(i32)

In this case reassociation is blocked by uses, so I was looking into extending LHS match in D113216 to catch (~a & ~b & c) in addition to (~(a | b) & c). I still need to look into that, but this is clearly LGTM.

[spatel]

In D114462#3149477, @rampitec wrote:

LGTM.

Thanks Sanjay! This really helps D113216 with -O3, but then not a more complex version of it which needs demorganing and reassociation:

; (~a & ~b & c) | ~(a | (b | c)) -> ~(a | b)
; (~a & ~b & c) | ~(b | (a | c)) -> ~(a | b)

define i32 @not_and_not_and_or_not_or_or(i32 %a, i32 %b, i32 %c) {
; CHECK-LABEL: @not_and_not_and_or_not_or_or(
; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR3]], -1
; CHECK-NEXT:    ret i32 [[NOT2]]
;
  %or1 = or i32 %b, %c
  %or2 = or i32 %or1, %a
  %not1 = xor i32 %or2, -1
  %nota = xor i32 %a, -1
  %notb = xor i32 %b, -1
  %and1 = and i32 %nota, %notb
  %and2 = and i32 %and1, %c
  %or4 = or i32 %and2, %not1
  call void @use(i32 %nota)
  call void @use(i32 %notb)
  ret i32 %or4
}

declare void @use(i32)

In this case reassociation is blocked by uses, so I was looking into extending LHS match in D113216 to catch (~a & ~b & c) in addition to (~(a | b) & c). I still need to look into that, but this is clearly LGTM.

Thanks!
Yes, I think we'll always be able to find cracks in the logic folds that allow some cases to get through.
If we can find a few more of these simplifications/combines though, I wonder if that will be enough to handle all of the patterns in the source example that you showed in D112276?

[rampitec]

In D114462#3149622, @spatel wrote:

Thanks!
Yes, I think we'll always be able to find cracks in the logic folds that allow some cases to get through.
If we can find a few more of these simplifications/combines though, I wonder if that will be enough to handle all of the patterns in the source example that you showed in D112276?

I just have to say I have tried.
JBTW, cases pre-commited for D113216 probably need to move into pass pipeline after this.

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
   if (Op0 == Op1)
     return Constant::getNullValue(Op0->getType());
 
   // A ^ ~A  =  ~A ^ A  =  -1
   if (match(Op0, m_Not(m_Specific(Op1))) ||
       match(Op1, m_Not(m_Specific(Op0))))
     return Constant::getAllOnesValue(Op0->getType());
 
+  // (~A | B) ^ (A & B) --> ~A -- There are 8 commuted variants.
+  // The 'not' op must contain a complete -1 operand (no undef elements for
+  // vector) for the transform to be safe.
+  auto matchNotA = [](Value *X, Value *Y) -> Value * {
+    Value *A, *B, *NotA;
+    const APInt *C;
+    if (match(X, m_c_Or(m_CombineAnd(m_Xor(m_Value(A), m_APIntForbidUndef(C)),
+                                     m_Value(NotA)),
+                        m_Value(B))) &&
+        match(Y, m_c_And(m_Specific(A), m_Specific(B))) && C->isAllOnes())
+      return NotA;
+    return nullptr;
+  };
+  if (Value *NotA = matchNotA(Op0, Op1))
+    return NotA;
+  if (Value *NotA = matchNotA(Op1, Op0))
+    return NotA;
+
   if (Value *V = simplifyLogicOfAddSub(Op0, Op1, Instruction::Xor))
     return V;
 
   // Try some generic simplifications for associative operations.
   if (Value *V = SimplifyAssociativeBinOp(Instruction::Xor, Op0, Op1, Q,
                                           MaxRecurse))
     return V;
 

llvm/test/Transforms/InstSimplify/xor.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
 define i32 @poison(i32 %x) {
 ; CHECK-LABEL: @poison(
 ; CHECK-NEXT:    ret i32 poison
 ;
   %v = xor i32 %x, poison
   ret i32 %v
 }
 
 define i4 @xor_and_or_not_commute0(i4 %a, i4 %b) {
 ; CHECK-LABEL: @xor_and_or_not_commute0(
-; CHECK-NEXT:    [[AND:%.*]] = and i4 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i4 [[A]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i4 [[NOT]], [[B]]
-; CHECK-NEXT:    [[R:%.*]] = xor i4 [[AND]], [[OR]]
-; CHECK-NEXT:    ret i4 [[R]]
+; CHECK-NEXT:    [[NOT:%.*]] = xor i4 [[A:%.*]], -1
+; CHECK-NEXT:    ret i4 [[NOT]]
 ;
   %and = and i4 %a, %b
   %not = xor i4 %a, -1
   %or = or i4 %not, %b
   %r = xor i4 %and, %or
   ret i4 %r
 }
 
 define <2 x i4> @xor_and_or_not_commute1(<2 x i4> %a, <2 x i4> %b) {
 ; CHECK-LABEL: @xor_and_or_not_commute1(
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i4> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i4> [[A]], <i4 -1, i4 -1>
-; CHECK-NEXT:    [[OR:%.*]] = or <2 x i4> [[NOT]], [[B]]
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[OR]], [[AND]]
-; CHECK-NEXT:    ret <2 x i4> [[R]]
+; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i4> [[A:%.*]], <i4 -1, i4 -1>
+; CHECK-NEXT:    ret <2 x i4> [[NOT]]
 ;
   %and = and <2 x i4> %a, %b
   %not = xor <2 x i4> %a, <i4 -1, i4 -1>
   %or = or <2 x i4> %not, %b
   %r = xor <2 x i4> %or, %and
   ret <2 x i4> %r
 }
 
 define i74 @xor_and_or_not_commute2(i74 %a, i74 %b) {
 ; CHECK-LABEL: @xor_and_or_not_commute2(
-; CHECK-NEXT:    [[AND:%.*]] = and i74 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i74 [[A]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i74 [[NOT]], [[B]]
-; CHECK-NEXT:    [[R:%.*]] = xor i74 [[AND]], [[OR]]
-; CHECK-NEXT:    ret i74 [[R]]
+; CHECK-NEXT:    [[NOT:%.*]] = xor i74 [[A:%.*]], -1
+; CHECK-NEXT:    ret i74 [[NOT]]
 ;
   %and = and i74 %b, %a
   %not = xor i74 %a, -1
   %or = or i74 %not, %b
   %r = xor i74 %and, %or
   ret i74 %r
 }
 
 define <2 x i4> @xor_and_or_not_commute3(<2 x i4> %a, <2 x i4> %b) {
 ; CHECK-LABEL: @xor_and_or_not_commute3(
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i4> [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i4> [[A]], <i4 -1, i4 -1>
-; CHECK-NEXT:    [[OR:%.*]] = or <2 x i4> [[NOT]], [[B]]
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[OR]], [[AND]]
-; CHECK-NEXT:    ret <2 x i4> [[R]]
+; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i4> [[A:%.*]], <i4 -1, i4 -1>
+; CHECK-NEXT:    ret <2 x i4> [[NOT]]
 ;
   %and = and <2 x i4> %b, %a
   %not = xor <2 x i4> %a, <i4 -1, i4 -1>
   %or = or <2 x i4> %not, %b
   %r = xor <2 x i4> %or, %and
   ret <2 x i4> %r
 }
 
 define i8 @xor_and_or_not_commute4(i8 %a, i8 %b) {
 ; CHECK-LABEL: @xor_and_or_not_commute4(
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[A]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[B]], [[NOT]]
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[AND]], [[OR]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[A:%.*]], -1
+; CHECK-NEXT:    ret i8 [[NOT]]
 ;
   %and = and i8 %a, %b
   %not = xor i8 %a, -1
   %or = or i8 %b, %not
   %r = xor i8 %and, %or
   ret i8 %r
 }
 
 define i8 @xor_and_or_not_commute5(i8 %a, i8 %b) {
 ; CHECK-LABEL: @xor_and_or_not_commute5(
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[A]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[B]], [[NOT]]
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[OR]], [[AND]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[A:%.*]], -1
+; CHECK-NEXT:    ret i8 [[NOT]]
 ;
   %and = and i8 %a, %b
   %not = xor i8 %a, -1
   %or = or i8 %b, %not
   %r = xor i8 %or, %and
   ret i8 %r
 }
 
 define i8 @xor_and_or_not_commute6(i8 %a, i8 %b) {
 ; CHECK-LABEL: @xor_and_or_not_commute6(
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[A]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[B]], [[NOT]]
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[AND]], [[OR]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[A:%.*]], -1
+; CHECK-NEXT:    ret i8 [[NOT]]
 ;
   %and = and i8 %b, %a
   %not = xor i8 %a, -1
   %or = or i8 %b, %not
   %r = xor i8 %and, %or
   ret i8 %r
 }
 
 define i8 @xor_and_or_not_commute7(i8 %a, i8 %b) {
 ; CHECK-LABEL: @xor_and_or_not_commute7(
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[A]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[B]], [[NOT]]
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[OR]], [[AND]]
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[A:%.*]], -1
+; CHECK-NEXT:    ret i8 [[NOT]]
 ;
   %and = and i8 %b, %a
   %not = xor i8 %a, -1
   %or = or i8 %b, %not
   %r = xor i8 %or, %and
   ret i8 %r
 }
 
+; negative test - must match specific values
+
 define i4 @xor_and_or_not_wrong_val1(i4 %a, i4 %b, i4 %c) {
 ; CHECK-LABEL: @xor_and_or_not_wrong_val1(
 ; CHECK-NEXT:    [[AND:%.*]] = and i4 [[A:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i4 [[A]], -1
 ; CHECK-NEXT:    [[OR:%.*]] = or i4 [[NOT]], [[B:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = xor i4 [[AND]], [[OR]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %and = and i4 %a, %c
   %not = xor i4 %a, -1
   %or = or i4 %not, %b
   %r = xor i4 %and, %or
   ret i4 %r
 }
 
+; negative test - must match specific values
+
 define i4 @xor_and_or_not_wrong_val2(i4 %a, i4 %b, i4 %c) {
 ; CHECK-LABEL: @xor_and_or_not_wrong_val2(
 ; CHECK-NEXT:    [[AND:%.*]] = and i4 [[C:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i4 [[A:%.*]], -1
 ; CHECK-NEXT:    [[OR:%.*]] = or i4 [[NOT]], [[B]]
 ; CHECK-NEXT:    [[R:%.*]] = xor i4 [[AND]], [[OR]]
 ; CHECK-NEXT:    ret i4 [[R]]
 ;
   %and = and i4 %c, %b
   %not = xor i4 %a, -1
   %or = or i4 %not, %b
   %r = xor i4 %and, %or
   ret i4 %r
 }
 
+; negative test - incorrect to propagate undef element
+
 define <2 x i4> @xor_and_or_not_undef_elt(<2 x i4> %a, <2 x i4> %b) {
 ; CHECK-LABEL: @xor_and_or_not_undef_elt(
 ; CHECK-NEXT:    [[AND:%.*]] = and <2 x i4> [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i4> [[A]], <i4 -1, i4 undef>
 ; CHECK-NEXT:    [[OR:%.*]] = or <2 x i4> [[NOT]], [[B]]
 ; CHECK-NEXT:    [[R:%.*]] = xor <2 x i4> [[OR]], [[AND]]
 ; CHECK-NEXT:    ret <2 x i4> [[R]]
 ;
   %and = and <2 x i4> %b, %a
   %not = xor <2 x i4> %a, <i4 -1, i4 undef>
   %or = or <2 x i4> %not, %b
   %r = xor <2 x i4> %or, %and
   ret <2 x i4> %r
 }