[InstSimplify] with logical ops: (X | Y) ? 0 : X --> 0

[Allen]

Summary

Use simplifySelectWithICmpEq to handle the implied equalities from the icmp-or,
then both of ICMP_NE and ICMP_EQ will be addressed

(X | Y) == 0 ?  X : 0 --> 0 (commuted 2 ways)
(X | Y) != 0 ?  0 : X --> 0 (commuted 2 ways) --> will transform to above in instcombine

Fixes https://github.com/llvm/llvm-project/issues/62263

[RKSimon]

llvm/test/Transforms/InstSimplify/select.ll

1408 ↗

(On Diff #516048)

is noundef necessary?

1416 ↗

(On Diff #516048)

commutation test?

[RKSimon]

llvm/lib/Analysis/InstructionSimplify.cpp

4733

Also - is this safe when matching zero vectors with undef elements?

[nikic]

As this is the second special case for this pattern, we should generalize it.

1. Extract https://github.com/llvm/llvm-project/blob/9ea3fcfa380c6097fddd0d9a9b2c13f0f20bc41a/llvm/lib/Analysis/InstructionSimplify.cpp#L4569-L4582 in one direction into a helper, and call it in both directions there.
2. Add a special case for or equals zero and and equals minus one where we try the replacement with the operands of the or/and.
3. Remove https://github.com/llvm/llvm-project/blob/9ea3fcfa380c6097fddd0d9a9b2c13f0f20bc41a/llvm/lib/Analysis/InstructionSimplify.cpp#L4585-L4598, which is subsumed.

[floatshadow]

In D148986#4289600, @nikic wrote:

As this is the second special case for this pattern, we should generalize it.

1. Extract https://github.com/llvm/llvm-project/blob/9ea3fcfa380c6097fddd0d9a9b2c13f0f20bc41a/llvm/lib/Analysis/InstructionSimplify.cpp#L4569-L4582 in one direction into a helper, and call it in both directions there.
2. Add a special case for or equals zero and and equals minus one where we try the replacement with the operands of the or/and.
3. Remove https://github.com/llvm/llvm-project/blob/9ea3fcfa380c6097fddd0d9a9b2c13f0f20bc41a/llvm/lib/Analysis/InstructionSimplify.cpp#L4585-L4598, which is subsumed.

My concern mentioned in this issue is the case the condition of ternary operator contains multiple ORs/ANDs. There seems a need to do a recursive check (?)
Current simplifyWithOpReplaced will dispatch OR simplification into a some fold check and fail to do further inductions.

[nikic]

In D148986#4289607, @floatshadow wrote:

In D148986#4289600, @nikic wrote:

As this is the second special case for this pattern, we should generalize it.

1. Extract https://github.com/llvm/llvm-project/blob/9ea3fcfa380c6097fddd0d9a9b2c13f0f20bc41a/llvm/lib/Analysis/InstructionSimplify.cpp#L4569-L4582 in one direction into a helper, and call it in both directions there.
2. Add a special case for or equals zero and and equals minus one where we try the replacement with the operands of the or/and.
3. Remove https://github.com/llvm/llvm-project/blob/9ea3fcfa380c6097fddd0d9a9b2c13f0f20bc41a/llvm/lib/Analysis/InstructionSimplify.cpp#L4585-L4598, which is subsumed.

My concern mentioned in this issue is the case the condition of ternary operator contains multiple ORs/ANDs. There seems a need to do a recursive check (?)

Unless there is reason to believe that such patterns occur in practice, there is no need for premature over-generalization. There are lots of places where we could be doing recursive checks, but in most places that just unnecessarily complicates things without providing tangible benefit.

[Allen]

hi @nikic, Why do we need delete the following modifications? I find some regression with some case, such as select_or_1

Remove https://github.com/llvm/llvm-project/blob/9ea3fcfa380c6097fddd0d9a9b2c13f0f20bc41a/llvm/lib/Analysis/InstructionSimplify.cpp#L4585-L4598

+++ b/llvm/test/Transforms/InstSimplify/select_or_and.ll
@@ -5,7 +5,9 @@
 define i32 @select_or_1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_or_1(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    ret i32 [[OR]]
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[OR]], 0
+; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[OR]]
+; CHECK-NEXT:    ret i32 [[RET]]

[nikic]

@Allen My bad -- we need an additional change in order to remove that code. For now you can just leave it.

[Allen]

Address comment

1. with some refactor to extract InstructionSimplify.cpp#L4569-L4582 in one direction into a helper, and call it in both directions there
2. Add extra case select_icmp_and_eq for equals minus one with TODO
3. Delete noundef for tests
4. Add commutation test select_icmp_or_eq_commuted
5. Add vector test select_icmp_or_eq_vec
6. change the match pattern from ICMP_NE to ICMP_EQ, as the instcombine will normalize the ICMP_NE to ICMP_EQ

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

4597

Not quite the code structure I had in mind. Rather than handling or in simplifySelectWithICmpEq, I'd expect something like this in here:

if (match(CmpLHS, m_Or(m_Value(X), m_Value(Y))) && match(CmpRHS, m_Zero())) {
  // X | Y == 0 implies X == 0 and Y == 0.
  if (Value *V = simplifySelectWithICmpEq(X, CmpRHS, TrueVal, FalseVal, Q,
                                          MaxRecurse))
      return V;
  if (Value *V = simplifySelectWithICmpEq(Y, CmpRHS, TrueVal, FalseVal, Q,
                                          MaxRecurse))
      return V;
}

That is, we handle the straightforward equality, and then we try to handle the implied equalities from the icmp or.

llvm/test/Transforms/InstSimplify/select-cmp-or.ll

2 ↗

(On Diff #516147)

Why does this also run instcombine?

[Allen]

Address comment
1、Use simplifySelectWithICmpEq to handle the implied equalities from the icmp-or according the suggestion
2、Delete the instcombine for test select-cmp-or.ll as it is not need with above refactoring

[Allen]

llvm/lib/Analysis/InstructionSimplify.cpp

4597

Thanks for detail suggestion, apply your comment.

4733

Thanks, added with select_icmp_or_eq_vec

llvm/test/Transforms/InstSimplify/select-cmp-or.ll

2 ↗

(On Diff #516147)

Delete it now,thanks.
I added this because the scenario of the case select_icmp_or_ne cannot be directly addressed, while I hope this scenario can also be monitored and verified.

llvm/test/Transforms/InstSimplify/select.ll

1408 ↗

(On Diff #516048)

I deleted the noundef, thanks

1416 ↗

(On Diff #516048)

Added with case select_icmp_or_eq_commuted

[nikic]

In D148986#4290283, @nikic wrote:

@Allen My bad -- we need an additional change in order to remove that code. For now you can just leave it.

Actually, I think I confused myself here. We should be able to remove this code now. From a local test, this works. (Well, if you also handle the and / -1 case.)

llvm/test/Transforms/InstCombine/select-ctlz-to-cttz.ll

144 ↗

(On Diff #516219)

Unrelated change?

[Allen]

Delete the or part according comment

[Allen]

In D148986#4292191, @nikic wrote:

In D148986#4290283, @nikic wrote:

@Allen My bad -- we need an additional change in order to remove that code. For now you can just leave it.

Actually, I think I confused myself here. We should be able to remove this code now. From a local test, this works. (Well, if you also handle the and / -1 case.)

Yes, the or/ 0 part can be deleted now. And the and / -1 case should be deleted with a following MR

llvm/test/Transforms/InstCombine/select-ctlz-to-cttz.ll

144 ↗

(On Diff #516219)

Yes, I add the TODO as it is a potential optimization points

[nikic]

Implementation looks good, can you please precommit the tests?

llvm/test/Transforms/InstSimplify/select-cmp-or.ll

33 ↗

(On Diff #516376)

Not needed for instsimplify tests.

60 ↗

(On Diff #516376)

Could you please add a negative test where the icmp constant is not zero?

[Allen]

rebase after precommit tests

[Allen]

In D148986#4292300, @nikic wrote:

Implementation looks good, can you please precommit the tests?

Thanks, apply your comment. Precommit the tests on D149115, and also add negative case with icmp constant is not zero as suggestion.

llvm/test/Transforms/InstSimplify/select-cmp-or.ll

33 ↗

(On Diff #516376)

Delete the thwart complexity-based canonicalization

[nikic]

LGTM

llvm/test/Transforms/InstSimplify/select-cmp-or.ll

50 ↗

(On Diff #516602)

This doesn't require InstCombine, this code internally canonicalizes to EQ predicate.

[Allen]

rebase as the test merged into select_or_and.ll

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifySelectWithFakeICmpEq(Value *CmpLHS, Value *CmpRHS,
   if (!decomposeBitTestICmp(CmpLHS, CmpRHS, Pred, X, Mask))
     return nullptr;
 
   return simplifySelectBitTest(TrueVal, FalseVal, X, &Mask,
                                Pred == ICmpInst::ICMP_EQ);
 }
 
 /// Try to simplify a select instruction when its condition operand is an
+/// integer equality comparison.
+static Value *simplifySelectWithICmpEq(Value *CmpLHS, Value *CmpRHS,
+                                       Value *TrueVal, Value *FalseVal,
+                                       const SimplifyQuery &Q,
+                                       unsigned MaxRecurse) {
+  if (simplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q,
+                             /* AllowRefinement */ false,
+                             MaxRecurse) == TrueVal)
+    return FalseVal;
+  if (simplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q,
+                             /* AllowRefinement */ true,
+                             MaxRecurse) == FalseVal)
+    return FalseVal;
+
+  return nullptr;
+}
+
+/// Try to simplify a select instruction when its condition operand is an
 /// integer comparison.
 static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
                                          Value *FalseVal,
                                          const SimplifyQuery &Q,
                                          unsigned MaxRecurse) {
   ICmpInst::Predicate Pred;
   Value *CmpLHS, *CmpRHS;
   if (!match(CondVal, m_ICmp(Pred, m_Value(CmpLHS), m_Value(CmpRHS))))
static Value *simplifySelectWithICmpCond(Value *CondVal, Value *TrueVal,
   if (Value *V =
           simplifySelectWithFakeICmpEq(CmpLHS, CmpRHS, Pred, TrueVal, FalseVal))
     return V;
 
   // If we have a scalar equality comparison, then we know the value in one of
   // the arms of the select. See if substituting this value into the arm and
   // simplifying the result yields the same value as the other arm.
   if (Pred == ICmpInst::ICMP_EQ) {
-    if (simplifyWithOpReplaced(FalseVal, CmpLHS, CmpRHS, Q,
-                               /* AllowRefinement */ false,
-                               MaxRecurse) == TrueVal ||
-        simplifyWithOpReplaced(FalseVal, CmpRHS, CmpLHS, Q,
-                               /* AllowRefinement */ false,
-                               MaxRecurse) == TrueVal)
-      return FalseVal;
-    if (simplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q,
-                               /* AllowRefinement */ true,
-                               MaxRecurse) == FalseVal ||
-        simplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q,
-                               /* AllowRefinement */ true,
-                               MaxRecurse) == FalseVal)
-      return FalseVal;
+    if (Value *V = simplifySelectWithICmpEq(CmpLHS, CmpRHS, TrueVal, FalseVal,
+                                            Q, MaxRecurse))
+      return V;
+    if (Value *V = simplifySelectWithICmpEq(CmpRHS, CmpLHS, TrueVal, FalseVal,
+                                            Q, MaxRecurse))
+      return V;
+
+    // select(X | Y == 0 ?  X : 0) --> 0 (commuted 2 ways)
+    Value *X;
+    Value *Y;
+    if (match(CmpLHS, m_Or(m_Value(X), m_Value(Y))) &&
+        match(CmpRHS, m_Zero())) {
+      // X | Y == 0 implies X == 0 and Y == 0.
+      if (Value *V = simplifySelectWithICmpEq(X, CmpRHS, TrueVal, FalseVal, Q,
+                                              MaxRecurse))
+        return V;
+      if (Value *V = simplifySelectWithICmpEq(Y, CmpRHS, TrueVal, FalseVal, Q,
+                                              MaxRecurse))
+        return V;
+    }
   }
 
   if (Pred == ICmpInst::Predicate::ICMP_EQ) {
     Value *X;
     Value *Y;
-    // select(X | Y == 0, X or Y, X | Y) -> X | Y
-    if (match(CondVal, m_ICmp(Pred, m_Specific(FalseVal), m_Zero())) &&
-        match(FalseVal, m_Or(m_Value(X), m_Value(Y))) &&
-        (TrueVal == X || TrueVal == Y))
-      return FalseVal;
     // select(X & Y == -1, X or Y, X & Y) -> X & Y
     if (match(CondVal, m_ICmp(Pred, m_Specific(FalseVal), m_AllOnes())) &&
         match(FalseVal, m_And(m_Value(X), m_Value(Y))) &&
         (TrueVal == X || TrueVal == Y))
       return FalseVal;
   }
 
   return nullptr;
if (match(FalseVal, m_ZeroInt())) {
           match(Cond, m_c_LogicalOr(m_Specific(X), m_Specific(Y))))
         return X;
     }
 
     // Match patterns that end in logical-or.
     if (match(TrueVal, m_One())) {
       // !(X && Y) || X --> true (commuted 2 ways)
       if (match(Cond, m_Not(m_c_LogicalAnd(m_Specific(FalseVal), m_Value()))))
         return ConstantInt::getTrue(Cond->getType());
       // X || !(X && Y) --> true (commuted 2 ways)
       if (match(FalseVal, m_Not(m_c_LogicalAnd(m_Specific(Cond), m_Value()))))
         return ConstantInt::getTrue(Cond->getType());
 
       // (X && Y) || Y --> Y (commuted 2 ways)
       if (match(Cond, m_c_LogicalAnd(m_Specific(FalseVal), m_Value())))
         return FalseVal;
       // Y || (X && Y) --> Y (commuted 2 ways)

llvm/test/Transforms/InstSimplify/select_or_and.ll

;
   %cmp = icmp ne <4 x i32> %or, zeroinitializer
   %ret = select <4 x i1> %cmp, <4 x i32> %or, <4 x i32> %y
   ret <4 x i32> %ret
 }
 
 ; select(Y | X == 0, Y | X, Y)
 define i32 @select_or_not_1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_or_not_1(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[OR]], 0
-; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 [[OR]], i32 [[Y]]
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 [[Y:%.*]]
 ;
   %or = or i32 %y, %x
   %cmp = icmp eq i32 %or, 0
   %ret = select i1 %cmp, i32 %or, i32 %y
   ret i32 %ret
 }
 ; select(Y | X != 0, Y, Y | X)
 define i32 @select_or_not_2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_or_not_2(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[OR]], 0
-; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[OR]]
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 [[Y:%.*]]
 ;
   %or = or i32 %y, %x
   %cmp = icmp ne i32 %or, 0
   %ret = select i1 %cmp, i32 %y, i32 %or
   ret i32 %ret
 }
 ; select(Y | X != 1, Y, Y | X)
 define i32 @select_or_not_3(i32 %x, i32 %y) {
;
   %tobool = icmp eq i32 %and, -1
   %cond = select i1 %tobool, i32 %a, i32 -1
   ret i32 %cond
 }
 
 ; https://alive2.llvm.org/ce/z/hSyCuR
 define i32 @select_icmp_or_eq(i32 %a, i32 %b) {
 ; CHECK-LABEL: @select_icmp_or_eq(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[OR]], 0
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 [[A]], i32 0
-; CHECK-NEXT:    ret i32 [[COND]]
+; CHECK-NEXT:    ret i32 0
 ;
   %or = or i32 %a, %b
   %tobool = icmp eq i32 %or, 0
   %cond = select i1 %tobool, i32 %a, i32 0
   ret i32 %cond
 }
 
 define i32 @select_icmp_or_eq_commuted(i32 %a, i32 %b) {
 ; CHECK-LABEL: @select_icmp_or_eq_commuted(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[OR]], 0
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 [[B]], i32 0
-; CHECK-NEXT:    ret i32 [[COND]]
+; CHECK-NEXT:    ret i32 0
 ;
   %or = or i32 %a, %b
   %tobool = icmp eq i32 %or, 0
   %cond = select i1 %tobool, i32 %b, i32 0
   ret i32 %cond
 }
 
 ; https://alive2.llvm.org/ce/z/S_pQek
 define <2 x i16> @select_icmp_or_eq_vec(<2 x i16> %a, <2 x i16> %b) {
 ; CHECK-LABEL: @select_icmp_or_eq_vec(
-; CHECK-NEXT:    [[OR:%.*]] = or <2 x i16> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq <2 x i16> [[OR]], zeroinitializer
-; CHECK-NEXT:    [[COND:%.*]] = select <2 x i1> [[TOBOOL]], <2 x i16> [[A]], <2 x i16> zeroinitializer
-; CHECK-NEXT:    ret <2 x i16> [[COND]]
+; CHECK-NEXT:    ret <2 x i16> zeroinitializer
 ;
   %or = or <2 x i16> %a, %b
   %tobool = icmp eq <2 x i16> %or, <i16 0, i16 0>
   %cond = select <2 x i1> %tobool, <2 x i16> %a, <2 x i16> zeroinitializer
   ret <2 x i16> %cond
 }
 
 ; The ne will also be matched
 define i32 @select_icmp_or_ne(i32 %a, i32 %b) {
 ; CHECK-LABEL: @select_icmp_or_ne(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[OR]], 0
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[TOBOOL]], i32 0, i32 [[A]]
-; CHECK-NEXT:    ret i32 [[COND]]
+; CHECK-NEXT:    ret i32 0
 ;
   %or = or i32 %a, %b
   %tobool = icmp ne i32 %or, 0
   %cond = select i1 %tobool, i32 0, i32 %a
   ret i32 %cond
 }
 
 ; Negative test: Incorrect const value for icmp