[InstSimplify] (~A & B) | ~(A | B) --> ~A with logical and

[dmgreen]

Summary

According to https://alive2.llvm.org/ce/z/opsdrb, it is valid to convert (~A & B) | ~(A | B) --> ~A even if the And is a Logical And. This came up from the vector masking of predicated blocks.

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

2267

m_c_LogicalAnd also matches m_c_And, no need for both.

2270

From a quick try, it looks like this can also be LogicalOr?

[dmgreen]

llvm/lib/Analysis/InstructionSimplify.cpp

2267

Yeah I had that originally, but according to the tests m_c_LogicalAnd only matches i1 types and the original pattern works for an Or of any size.

2270

Sounds good to me.

[dmgreen]

Use LogicalOr

[spatel]

I wonder if we could replace all of the matchers in this whole function. We can't leak poison when simplifying to an existing value? This will need a pile of tests...

Also, if any logic expression folds to a constant, then a transform must be safe to match with logical and/or sub-expressions too?

[spatel]

LGTM - but please add a TODO comment that other (maybe all) of the similar transforms near here could be enhanced in the same way. And so we probably want to wrap the matchers or create a new matcher that works with both logical and bitwise ops.

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
 
   return nullptr;
 }
 
 Value *llvm::simplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::simplifyAndInst(Op0, Op1, Q, RecursionLimit);
 }
 
+// TODO: Many of these folds could use LogicalAnd/LogicalOr.
 static Value *simplifyOrLogic(Value *X, Value *Y) {
   assert(X->getType() == Y->getType() && "Expected same type for 'or' ops");
   Type *Ty = X->getType();
 
   // X | ~X --> -1
   if (match(Y, m_Not(m_Specific(X))))
     return ConstantInt::getAllOnesValue(Ty);
 
static Value *simplifyOrLogic(Value *X, Value *Y) {
   // (B & ~A) | ~(A | B) --> ~A
   // (B & ~A) | ~(B | A) --> ~A
   Value *NotA;
   if (match(X,
             m_c_And(m_CombineAnd(m_Value(NotA), m_NotForbidUndef(m_Value(A))),
                     m_Value(B))) &&
       match(Y, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
     return NotA;
+  // The same is true of Logical And
+  // TODO: This could share the logic of the version above if there was a
+  // version of LogicalAnd that allowed more than just i1 types.
+  if (match(X, m_c_LogicalAnd(
+                   m_CombineAnd(m_Value(NotA), m_NotForbidUndef(m_Value(A))),
+                   m_Value(B))) &&
+      match(Y, m_Not(m_c_LogicalOr(m_Specific(A), m_Specific(B)))))
+    return NotA;
 
   // ~(A ^ B) | (A & B) --> ~(A ^ B)
   // ~(A ^ B) | (B & A) --> ~(A ^ B)
   Value *NotAB;
   if (match(X, m_CombineAnd(m_NotForbidUndef(m_Xor(m_Value(A), m_Value(B))),
                             m_Value(NotAB))) &&
       match(Y, m_c_And(m_Specific(A), m_Specific(B))))
     return NotAB;

llvm/test/Transforms/InstCombine/or.ll

;
   %x = and i32 %p, 7
   %m = mul i32 %x, 12
   %r = or i32 %m, %x
   ret i32 %r
 }
 
 define <4 x i1> @and_or_not_or_logical_vec(<4 x i32> %ap, <4 x i32> %bp) {
 ; CHECK-LABEL: @and_or_not_or_logical_vec(
-; CHECK-NEXT:    [[A:%.*]] = icmp eq <4 x i32> [[AP:%.*]], zeroinitializer
-; CHECK-NEXT:    [[B:%.*]] = icmp eq <4 x i32> [[BP:%.*]], zeroinitializer
-; CHECK-NEXT:    [[V:%.*]] = xor <4 x i1> [[A]], <i1 true, i1 true, i1 true, i1 true>
-; CHECK-NEXT:    [[X:%.*]] = select <4 x i1> [[B]], <4 x i1> [[V]], <4 x i1> zeroinitializer
-; CHECK-NEXT:    [[W:%.*]] = or <4 x i1> [[B]], [[A]]
-; CHECK-NEXT:    [[Y:%.*]] = xor <4 x i1> [[W]], <i1 true, i1 true, i1 true, i1 true>
-; CHECK-NEXT:    [[Z:%.*]] = or <4 x i1> [[X]], [[Y]]
-; CHECK-NEXT:    ret <4 x i1> [[Z]]
+; CHECK-NEXT:    [[A:%.*]] = icmp ne <4 x i32> [[AP:%.*]], zeroinitializer
+; CHECK-NEXT:    ret <4 x i1> [[A]]
 ;
   %A = icmp eq <4 x i32> %ap, zeroinitializer
   %B = icmp eq <4 x i32> %bp, zeroinitializer
   %V = xor <4 x i1> %A, <i1 true, i1 true, i1 true, i1 true>
   %X = select <4 x i1> %B, <4 x i1> %V, <4 x i1> zeroinitializer
   %W = or <4 x i1> %B, %A
   %Y = xor <4 x i1> %W, <i1 true, i1 true, i1 true, i1 true>
   %Z = or <4 x i1> %X, %Y
   ret <4 x i1> %Z
 }

llvm/test/Transforms/InstSimplify/or.ll

;
   %r = or <2 x i4> %notab, %and
   ret <2 x i4> %r
 }
 
 ; (~A & B) | ~(A | B) --> ~A with logical and
 define i1 @and_or_not_or_logical(i1 %A, i1 %B) {
 ; CHECK-LABEL: @and_or_not_or_logical(
 ; CHECK-NEXT:    [[V:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[X:%.*]] = select i1 [[V]], i1 [[B:%.*]], i1 false
-; CHECK-NEXT:    [[W:%.*]] = or i1 [[B]], [[A]]
-; CHECK-NEXT:    [[Y:%.*]] = xor i1 [[W]], true
-; CHECK-NEXT:    [[Z:%.*]] = or i1 [[X]], [[Y]]
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 [[V]]
 ;
   %V = xor i1 %A, true
   %X = select i1 %V, i1 %B, i1 false
   %W = or i1 %B, %A
   %Y = xor i1 %W, true
   %Z = or i1 %X, %Y
   ret i1 %Z
 }
 
 ; (~B & A) | ~(A | B) --> ~A with logical and
 define i1 @and_or_not_or_logical_rev(i1 %A, i1 %B) {
 ; CHECK-LABEL: @and_or_not_or_logical_rev(
 ; CHECK-NEXT:    [[V:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[X:%.*]] = select i1 [[B:%.*]], i1 [[V]], i1 false
-; CHECK-NEXT:    [[W:%.*]] = or i1 [[B]], [[A]]
-; CHECK-NEXT:    [[Y:%.*]] = xor i1 [[W]], true
-; CHECK-NEXT:    [[Z:%.*]] = or i1 [[X]], [[Y]]
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 [[V]]
 ;
   %V = xor i1 %A, true
   %X = select i1 %B, i1 %V, i1 false
   %W = or i1 %B, %A
   %Y = xor i1 %W, true
   %Z = or i1 %X, %Y
   ret i1 %Z
 }
 
 ; (~A & B) | ~(A | B) --> ~A with logical And and logical Or
 define i1 @and_or_not_logical_or_logical_rev(i1 %A, i1 %B) {
 ; CHECK-LABEL: @and_or_not_logical_or_logical_rev(
 ; CHECK-NEXT:    [[V:%.*]] = xor i1 [[A:%.*]], true
-; CHECK-NEXT:    [[X:%.*]] = select i1 [[B:%.*]], i1 [[V]], i1 false
-; CHECK-NEXT:    [[W:%.*]] = select i1 [[B]], i1 true, i1 [[A]]
-; CHECK-NEXT:    [[Y:%.*]] = xor i1 [[W]], true
-; CHECK-NEXT:    [[Z:%.*]] = or i1 [[X]], [[Y]]
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 [[V]]
 ;
   %V = xor i1 %A, true
   %X = select i1 %B, i1 %V, i1 false
   %W = select i1 %B, i1 true, i1 %A
   %Y = xor i1 %W, true
   %Z = or i1 %X, %Y
   ret i1 %Z
 }