[InstSimplify] Fold (X || Y) ? false : X --> false

[bcl5980]

Summary

(X || Y) ? false : X --> false
https://alive2.llvm.org/ce/z/y93yUm

[bcl5980]

These two patterns are really simple so I merge them into one patch. If any of you think split them is better I will send another patch for the new pattern.

[bcl5980]

Note:
!(X || Y) && Y --> false
can be trigged on SpecCPU2017\benchspec\CPU\502.gcc_r\src\insn-attrtab.c

[spatel]

There are quite a few variations within these patterns, so I prefer to split it up.
Please pre-commit baseline tests and see my comment in D138744. Also, should we prefer the code placement/structure that is proposed in that patch?

[bcl5980]

In D138700#3953318, @spatel wrote:

There are quite a few variations within these patterns, so I prefer to split it up.
Please pre-commit baseline tests and see my comment in D138744. Also, should we prefer the code placement/structure that is proposed in that patch?

I prefer to keep current position. Because

1. These two patterns I add is very similar. Put them together looks better.
2. They can share m_LogicalOr match. D138744 miss logical or also. We can't put the code on there because BO is not BinaryOperator when it is a logical or.

[spatel]

There's still a lot of possibilities even with these 2 patterns, so I'd prefer to split it up again. We are missing some necessary tests.

llvm/lib/Analysis/InstructionSimplify.cpp

4565

This comment is not the same as the pattern that is matched.

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

204–205

Shouldn't there be a test like this (or the first test) with a bitwise 'or'?

https://alive2.llvm.org/ce/z/yzcA-z

219–220

We need a test similar to this, but with poison elements.

329

This is a miscompile:
https://alive2.llvm.org/ce/z/tAeZY9

[bcl5980]

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

219–220

@logical_not_or_and_vector1_poison should be the test you mentioned.

[spatel]

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

292

Here and below - the usual notation for a select op if we are writing it like C code would be:
(X | Y) ? false : X --> false

303

update comment to match test:
(X | Y) ? false : Y --> false

327

We can transform this, but it must not propagate the poison:
https://alive2.llvm.org/ce/z/MsJicP

So it should be ok to leave the match with m_ZeroInt(), but instead of returning the existing TrueVal, return a "full" false constant:

ConstantInt::getFalse(Cond->getType())

[spatel]

LGTM - see inline for code suggestion.

llvm/lib/Analysis/InstructionSimplify.cpp

4564

Use m_c_LogicalOr() and m_Specific() to make the code shorter. We do not need to capture X/Y:

if (match(Cond, m_c_LogicalOr(m_Specific(FalseVal), m_Value())) &&
    match(TrueVal, m_ZeroInt()))
  return ConstantInt::getFalse(Cond->getType());

[bcl5980]

Thanks for the review.

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
   assert(TrueVal->getType() == FalseVal->getType() &&
          "Select must have same types for true/false ops");
 
   if (Cond->getType() == TrueVal->getType()) {
     // select i1 Cond, i1 true, i1 false --> i1 Cond
     if (match(TrueVal, m_One()) && match(FalseVal, m_ZeroInt()))
       return Cond;
 
-    // (X || Y) && (X || !Y) --> X (commuted 8 ways)
+    // (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 || !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

;
   %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]]
 ;
   %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]]
 ;
   %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>

 ; CHECK-NEXT:    ret i1 [[R]]
 ;
   %or = or i1 %x, %y
   %r = select i1 %or, i1 false, i1 %z
   ret i1 %r
 }
 
 
-; (X | Y) ? false && X --> false
+; (X | Y) ? false : X --> false
 
 define i1 @or_select_false_x_case1(i1 %x, i1 %y) {
 ; CHECK-LABEL: @or_select_false_x_case1(
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[OR]], i1 false, i1 [[X]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %or = or i1 %x, %y
   %r = select i1 %or, i1 false, i1 %x
   ret i1 %r
 }
 
-; (X | Y) ? false && X --> false
+; (X | Y) ? false : X --> false
 
 define i1 @or_select_false_x_case2(i1 %x, i1 %y) {
 ; CHECK-LABEL: @or_select_false_x_case2(
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[OR]], i1 false, i1 [[Y]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %or = or i1 %x, %y
   %r = select i1 %or, i1 false, i1 %y
   ret i1 %r
 }
 
-; vector case (X | Y) ? false && X --> false
+; vector case (X | Y) ? false : X --> false
 
 define <2 x i1> @or_select_false_x_vector(<2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @or_select_false_x_vector(
-; CHECK-NEXT:    [[OR:%.*]] = or <2 x i1> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[OR]], <2 x i1> zeroinitializer, <2 x i1> [[X]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %or = or <2 x i1> %x, %y
   %r = select <2 x i1> %or, <2 x i1> <i1 false, i1 false>, <2 x i1> %x
   ret <2 x i1> %r
 }
 
-; vector poison case (X | Y) ? false && X --> false
+; vector poison case (X | Y) ? false : X --> false
 
 define <2 x i1> @or_select_false_x_vector_poison(<2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @or_select_false_x_vector_poison(
-; CHECK-NEXT:    [[OR:%.*]] = or <2 x i1> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[OR]], <2 x i1> <i1 poison, i1 false>, <2 x i1> [[X]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %or = or <2 x i1> %x, %y
   %r = select <2 x i1> %or, <2 x i1> <i1 poison, i1 false>, <2 x i1> %x
   ret <2 x i1> %r
 }
 
-; (X || Y) ? false && X --> false
+; (X || Y) ? false : X --> false
 
 define i1 @logical_or_select_false_x_case1(i1 %x, i1 %y) {
 ; CHECK-LABEL: @logical_or_select_false_x_case1(
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[OR]], i1 false, i1 [[X]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %or = select i1 %x, i1 true, i1 %y
   %r = select i1 %or, i1 false, i1 %x
   ret i1 %r
 }
 
-; (X || Y) ? false && X --> false
+; (X || Y) ? false : X --> false
 
 define i1 @logical_or_select_false_x_case2(i1 %x, i1 %y) {
 ; CHECK-LABEL: @logical_or_select_false_x_case2(
-; CHECK-NEXT:    [[OR:%.*]] = select i1 [[Y:%.*]], i1 true, i1 [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[OR]], i1 false, i1 [[X]]
-; CHECK-NEXT:    ret i1 [[R]]
+; CHECK-NEXT:    ret i1 false
 ;
   %or = select i1 %y, i1 true, i1 %x
   %r = select i1 %or, i1 false, i1 %x
   ret i1 %r
 }
 
-; vector case (X || Y) ? false && X --> false
+; vector case (X || Y) ? false : X --> false
 
 define <2 x i1> @logical_or_select_false_x_vector(<2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @logical_or_select_false_x_vector(
-; CHECK-NEXT:    [[OR:%.*]] = select <2 x i1> [[Y:%.*]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[OR]], <2 x i1> zeroinitializer, <2 x i1> [[X]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %or = select <2 x i1> %y, <2 x i1> <i1 true, i1 true>, <2 x i1> %x
   %r = select <2 x i1> %or, <2 x i1> <i1 false, i1 false>, <2 x i1> %x
   ret <2 x i1> %r
 }
 
-; vector poison case (X || Y) ? false && X --> false
+; TODO: this could transform to false
+; vector poison case (X || Y) ? false : X --> false
 
 define <2 x i1> @logical_or_select_false_x_vector_poison1(<2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @logical_or_select_false_x_vector_poison1(
 ; CHECK-NEXT:    [[OR:%.*]] = select <2 x i1> [[Y:%.*]], <2 x i1> <i1 poison, i1 true>, <2 x i1> [[X:%.*]]
 ; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[OR]], <2 x i1> zeroinitializer, <2 x i1> [[X]]
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %or = select <2 x i1> %y, <2 x i1> <i1 poison, i1 true>, <2 x i1> %x
   %r = select <2 x i1> %or, <2 x i1> <i1 false, i1 false>, <2 x i1> %x
   ret <2 x i1> %r
 }
 
-; vector poison case (X || Y) ? false && X --> false
+; vector poison case (X || Y) ? false : X --> false
 
 define <2 x i1> @logical_or_select_false_x_vector_poison2(<2 x i1> %x, <2 x i1> %y) {
 ; CHECK-LABEL: @logical_or_select_false_x_vector_poison2(
-; CHECK-NEXT:    [[OR:%.*]] = select <2 x i1> [[Y:%.*]], <2 x i1> <i1 true, i1 true>, <2 x i1> [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[OR]], <2 x i1> <i1 poison, i1 false>, <2 x i1> [[X]]
-; CHECK-NEXT:    ret <2 x i1> [[R]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %or = select <2 x i1> %y, <2 x i1> <i1 true, i1 true>, <2 x i1> %x
   %r = select <2 x i1> %or, <2 x i1> <i1 poison, i1 false>, <2 x i1> %x
   ret <2 x i1> %r
 }
 
 ; negative test - must have common operands