[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

is noundef necessary?

1416

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

I deleted the noundef, thanks

1416

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

       if (match(Cond, m_c_LogicalAnd(m_Specific(FalseVal), m_Value())))
         return FalseVal;
       // Y || (X && Y) --> Y (commuted 2 ways)
       if (match(FalseVal, m_c_LogicalAnd(m_Specific(Cond), m_Value())))
         return Cond;
     }
   }
 
+  // (X | Y) ? 0 : X --> 0 (commuted 2 ways)
+  ICmpInst::Predicate Pred;
+  if (match(Cond,
+            m_ICmp(Pred, m_c_Or(m_Specific(FalseVal), m_Value()), m_Zero())) &&
+      match(TrueVal, m_ZeroInt()) && Pred == ICmpInst::ICMP_NE)
+    return TrueVal;
+
   // select ?, X, X -> X
   if (TrueVal == FalseVal)
     return TrueVal;
 
   if (Cond == TrueVal) {
     // select i1 X, i1 X, i1 false --> X (logical-and)
     if (match(FalseVal, m_ZeroInt()))
       return Cond;

llvm/test/Transforms/InstSimplify/select.ll

 ; CHECK-NEXT:    ret <2 x i32> [[COND]]
 ;
   %shl.mask = and <2 x i32> %x, <i32 1073741823, i32 1073741823>
   %tobool.not = icmp ne <2 x i32> %shl.mask, zeroinitializer
   %mul = shl <2 x i32> %x, <i32 2, i32 2>
   %cond = select <2 x i1> %tobool.not, <2 x i32> %mul, <2 x i32> zeroinitializer
   ret <2 x i32> %cond
 }
+
+define i32 @select_icmp_or(i32 noundef %a, i32 noundef %b) {
+; CHECK-LABEL: @select_icmp_or(
+; 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
+}