[InstSimplify] Fold !(X || Y) && X --> false

[bcl5980]

Summary

!(X || Y) && X --> false
https://alive2.llvm.org/ce/z/693Jgv

Fix: 56654
Fix: 56780

[bcl5980]

llvm/lib/Analysis/InstructionSimplify.cpp

4564–4568

I guess this pattern also can't accept undef/poision for vector case.

[bcl5980]

llvm/lib/Analysis/InstructionSimplify.cpp

4564–4568

Just ignore the comment. I am wrong.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

4566–4567

Shorten:

if (match(Cond, m_Not(m_c_LogicalOr(m_Specific(TrueVal), m_Value()))))

llvm/test/Transforms/InstSimplify/select-logical.ll

189–190

typo: comute -> commute

224

The FalseVal of %r is not zero, so this is not showing what the comment describes. This might need a TODO if we don't match the first select as logical-or?

[bcl5980]

llvm/test/Transforms/InstSimplify/select-logical.ll

224

I'm sorry , this should be a typo.

[bcl5980]

address comments.

[spatel]

LGTM

llvm/lib/Analysis/InstructionSimplify.cpp

if (match(TrueVal, m_One()) && match(FalseVal, m_ZeroInt()))
       return Cond;
 
     // (X || Y) ? false : X --> false (commuted 2 ways)
     if (match(Cond, m_c_LogicalOr(m_Specific(FalseVal), m_Value())) &&
         match(TrueVal, m_ZeroInt()))
       return ConstantInt::getFalse(Cond->getType());
 
     Value *X, *Y;
     if (match(FalseVal, m_ZeroInt())) {
+      // !(X || Y) && X --> false (commuted 2 ways)
+      if (match(Cond, m_Not(m_c_LogicalOr(m_Specific(TrueVal), m_Value()))))
+        return ConstantInt::getFalse(Cond->getType());
+
       // (X || Y) && (X || !Y) --> X (commuted 8 ways)
       if (match(Cond, m_c_LogicalOr(m_Value(X), m_Not(m_Value(Y)))) &&
           match(TrueVal, m_c_LogicalOr(m_Specific(X), m_Specific(Y))))
         return X;
       if (match(TrueVal, m_c_LogicalOr(m_Value(X), m_Not(m_Value(Y)))) &&
           match(Cond, m_c_LogicalOr(m_Specific(X), m_Specific(Y))))
         return X;
     }

llvm/test/Transforms/InstSimplify/select-logical.ll

;
   %and = select i1 %xorynot, i1 %xorz, i1 false
   ret i1 %and
 }
 
 ; !(X | Y) && X --> false
 
 define i1 @or_not_and(i1 %x, i1 %y) {
 ; CHECK-LABEL: @or_not_and(
-; CHECK-NEXT:    [[L_AND:%.*]] = or i1 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[L_AND]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOT]], i1 [[X]], i1 false
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %l.and = or i1 %x, %y
   %not = xor i1 %l.and, true
   %r = select i1 %not, i1 %x, i1 false
   ret i1 %r
 }
 
 ; vector case !(X | Y) && X --> false
 
 define <2 x i1> @or_not_and_vector(<2 x i1>  %x, <2 x i1>  %y) {
 ; CHECK-LABEL: @or_not_and_vector(
-; CHECK-NEXT:    [[L_AND:%.*]] = or <2 x i1> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i1> [[L_AND]], <i1 true, i1 true>
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[NOT]], <2 x i1> [[X]], <2 x i1> zeroinitializer
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %l.and = or <2 x i1> %x, %y
   %not = xor <2 x i1> %l.and, <i1 true, i1 true>
   %r = select <2 x i1>  %not, <2 x i1>  %x, <2 x i1> <i1 false, i1 false>
   ret <2 x i1>  %r
 }
 
 ; vector case !(X | Y) && X --> false
 
 define <2 x i1> @or_not_and_vector_poison1(<2 x i1>  %x, <2 x i1>  %y) {
 ; CHECK-LABEL: @or_not_and_vector_poison1(
-; CHECK-NEXT:    [[L_AND:%.*]] = or <2 x i1> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i1> [[L_AND]], <i1 poison, i1 true>
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[NOT]], <2 x i1> [[X]], <2 x i1> zeroinitializer
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %l.and = or <2 x i1> %x, %y
   %not = xor <2 x i1> %l.and, <i1 poison, i1 true>
   %r = select <2 x i1>  %not, <2 x i1>  %x, <2 x i1> <i1 false, i1 false>
   ret <2 x i1>  %r
 }
 
 ; vector case !(X | Y) && X --> false
 
 define <2 x i1> @or_not_and_vector_poison2(<2 x i1>  %x, <2 x i1>  %y) {
 ; CHECK-LABEL: @or_not_and_vector_poison2(
-; CHECK-NEXT:    [[L_AND:%.*]] = or <2 x i1> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor <2 x i1> [[L_AND]], <i1 true, i1 true>
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[NOT]], <2 x i1> [[X]], <2 x i1> <i1 poison, i1 false>
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %l.and = or <2 x i1> %x, %y
   %not = xor <2 x i1> %l.and, <i1 true, i1 true>
   %r = select <2 x i1>  %not, <2 x i1>  %x, <2 x i1> <i1 poison, i1 false>
   ret <2 x i1>  %r
 }
 
 
 ; !(X || Y) && X --> false
 
 define i1 @logical_or_not_and(i1 %x, i1 %y) {
 ; CHECK-LABEL: @logical_or_not_and(
-; CHECK-NEXT:    [[L_AND:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[L_AND]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOT]], i1 [[X]], i1 false
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %l.and = select i1 %x, i1 true, i1 %y
   %not = xor i1 %l.and, true
   %r = select i1 %not, i1 %x, i1 false
   ret i1 %r
 }
 
 
 ; !(X || Y) && Y --> false
 
-define i1 @logical_or_not_and_comute_or(i1 %x, i1 %y) {
-; CHECK-LABEL: @logical_or_not_and_comute_or(
-; CHECK-NEXT:    [[L_AND:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i1 [[L_AND]], true
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[NOT]], i1 [[Y]], i1 false
-; CHECK-NEXT:    ret i1 [[R]]
+define i1 @logical_or_not_and_commute_or(i1 %x, i1 %y) {
+; CHECK-LABEL: @logical_or_not_and_commute_or(
+; CHECK-NEXT:    ret i1 false
 ;
   %l.and = select i1 %x, i1 true, i1 %y
   %not = xor i1 %l.and, true
   %r = select i1 %not, i1 %y, i1 false
   ret i1 %r
 }
 
 ; vector case !(X || Y) && X --> false
 
 define <3 x i1> @logical_or_not_and_vector1(<3 x i1> %x, <3 x i1> %y) {
 ; CHECK-LABEL: @logical_or_not_and_vector1(
-; CHECK-NEXT:    [[L_AND:%.*]] = select <3 x i1> [[X:%.*]], <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> [[Y:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor <3 x i1> [[L_AND]], <i1 true, i1 true, i1 true>
-; CHECK-NEXT:    [[R:%.*]] = select <3 x i1> [[NOT]], <3 x i1> [[X]], <3 x i1> zeroinitializer
-; CHECK-NEXT:    ret <3 x i1> [[R]]
+; CHECK-NEXT:    ret <3 x i1> zeroinitializer
 ;
   %l.and = select <3 x i1> %x, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %y
   %not = xor <3 x i1> %l.and, <i1 true, i1 true, i1 true>
   %r = select <3 x i1> %not, <3 x i1> %x, <3 x i1> <i1 false, i1 false, i1 false>
   ret <3 x i1> %r
 }
 
+; TODO: this could transform to false
 ; vector case !(X || Y) && X --> false
 
 define <3 x i1> @logical_or_not_and_vector1_poison1(<3 x i1> %x, <3 x i1> %y) {
 ; CHECK-LABEL: @logical_or_not_and_vector1_poison1(
 ; CHECK-NEXT:    [[L_AND:%.*]] = select <3 x i1> [[X:%.*]], <3 x i1> <i1 true, i1 true, i1 poison>, <3 x i1> [[Y:%.*]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor <3 x i1> [[L_AND]], <i1 true, i1 true, i1 true>
-; CHECK-NEXT:    [[R:%.*]] = select <3 x i1> [[NOT]], <3 x i1> [[X]], <3 x i1> <i1 true, i1 false, i1 false>
+; CHECK-NEXT:    [[R:%.*]] = select <3 x i1> [[NOT]], <3 x i1> [[X]], <3 x i1> zeroinitializer
 ; CHECK-NEXT:    ret <3 x i1> [[R]]
 ;
   %l.and = select <3 x i1> %x, <3 x i1> <i1 true, i1 true, i1 poison>, <3 x i1> %y
   %not = xor <3 x i1> %l.and, <i1 true, i1 true, i1 true>
-  %r = select <3 x i1> %not, <3 x i1> %x, <3 x i1> <i1 true, i1 false, i1 false>
+  %r = select <3 x i1> %not, <3 x i1> %x, <3 x i1> <i1 false, i1 false, i1 false>
   ret <3 x i1> %r
 }
 
 ; vector case !(X || Y) && X --> false
 
 define <3 x i1> @logical_or_not_and_vector1_poison2(<3 x i1> %x, <3 x i1> %y) {
 ; CHECK-LABEL: @logical_or_not_and_vector1_poison2(
-; CHECK-NEXT:    [[L_AND:%.*]] = select <3 x i1> [[X:%.*]], <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> [[Y:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor <3 x i1> [[L_AND]], <i1 true, i1 poison, i1 true>
-; CHECK-NEXT:    [[R:%.*]] = select <3 x i1> [[NOT]], <3 x i1> [[X]], <3 x i1> zeroinitializer
-; CHECK-NEXT:    ret <3 x i1> [[R]]
+; CHECK-NEXT:    ret <3 x i1> zeroinitializer
 ;
   %l.and = select <3 x i1> %x, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %y
   %not = xor <3 x i1> %l.and, <i1 true, i1 poison, i1 true>
   %r = select <3 x i1> %not, <3 x i1> %x, <3 x i1> <i1 false, i1 false, i1 false>
   ret <3 x i1> %r
 }
 
 ; vector case !(X || Y) && X --> false
 
 define <3 x i1> @logical_or_not_and_vector1_poison3(<3 x i1> %x, <3 x i1> %y) {
 ; CHECK-LABEL: @logical_or_not_and_vector1_poison3(
-; CHECK-NEXT:    [[L_AND:%.*]] = select <3 x i1> [[X:%.*]], <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> [[Y:%.*]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor <3 x i1> [[L_AND]], <i1 true, i1 true, i1 true>
-; CHECK-NEXT:    [[R:%.*]] = select <3 x i1> [[NOT]], <3 x i1> [[X]], <3 x i1> <i1 poison, i1 false, i1 false>
-; CHECK-NEXT:    ret <3 x i1> [[R]]
+; CHECK-NEXT:    ret <3 x i1> zeroinitializer
 ;
   %l.and = select <3 x i1> %x, <3 x i1> <i1 true, i1 true, i1 true>, <3 x i1> %y
   %not = xor <3 x i1> %l.and, <i1 true, i1 true, i1 true>
   %r = select <3 x i1> %not, <3 x i1> %x, <3 x i1> <i1 poison, i1 false, i1 false>
   ret <3 x i1> %r
 }
 
 ; negative test - must have common operands