[InstCombine] support fold select(X|Y,X|Y,X) to X|Y

[HerrCai0907]

Summary

Fixed: https://github.com/llvm/llvm-project/issues/62113
Add addtional check in visitSelectInst to:

1. match select(X|Y==0, X, X|Y) and replaced with X|Y
2. match select(X&Y==-1, X, X&Y) and replaced with X&Y

alive proof:
https://alive2.llvm.org/ce/z/4qHmv-
https://alive2.llvm.org/ce/z/c2MBGy

[bcl5980]

We can extend it to and also:

X & Y == -1 ? X : X & Y --> X & Y

And please try to attach or pattern's alive2 proof like this:
https://alive2.llvm.org/ce/z/c2MBGy

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

3585 ↗

(On Diff #513376)

If the cmp LHS is FalseVal, pred should be ne here.
If the cmp LHS is TrueVal, pred should be eq I guess.

3587 ↗

(On Diff #513376)

TrueVal == X || TrueVal == Y?

[HerrCai0907]

add select(X&Y==-1, X, X&Y) -> X&Y

[HerrCai0907]

remove dbg header

[nikic]

As this does not produce new instructions, it should be part of InstSimplify, somewhere around simplifySelectWithICmpCond.

[HerrCai0907]

move to simplifySelectWithICmpCond

[HerrCai0907]

move test

[nikic]

Please add one test using vectors, and a negative test with the wrong constant in the icmp.

llvm/lib/Analysis/InstructionSimplify.cpp

4594

Already checked above.

llvm/test/Transforms/InstSimplify/select_or_and.ll

2

instsimplify

5

Please name instructions in test (run through -passes=instnamer).

[HerrCai0907]

add vector and more negative testcase

[nikic]

llvm/test/Transforms/InstSimplify/select_or_and.ll

2

What I meant is to run the test through opt -passes=instnamer and commit the result, so the input does not contain any %0 etc. instnamer shouldn't be part of the RUN line.

[HerrCai0907]

update test

[HerrCai0907]

sorry for misunderstanding, fixed.

[goldstein.w.n]

llvm/lib/Analysis/InstructionSimplify.cpp

4585

Should we also have select(X|Y != 0, X | Y, X or Y)?

4588

You could also do:
select(X | Y == X, X, X | Y) -> X | Y
and
select (X|Y == Y, Y, X|Y) -> X|Y
https://alive2.llvm.org/ce/z/hawAog

[goldstein.w.n]

llvm/test/Transforms/InstSimplify/select_or_and.ll

11

Can you split the next tests to a prior patch so we can see the diff this patch generates?

[HerrCai0907]

llvm/lib/Analysis/InstructionSimplify.cpp

4585

ne will be changed to eq in line 4498

4588

I think it can be done in next patch

llvm/test/Transforms/InstSimplify/select_or_and.ll

11

before this patch, opt won't do any optimization for this code. Diff between the original code and the checked code is what this patch does.

[junaire]

llvm/test/Transforms/InstSimplify/select_or_and.ll

11

That's expected. We want to see opt does no optimization for the tests so if you can split the tests into a parent revision then we can see very clearly the changes your patch does in the Phab. Similar to (https://github.com/llvm/llvm-project/commit/87c97d052cfd6dc0c03e5e36be1315f659f9f0ac)

[nikic]

llvm/lib/Analysis/InstructionSimplify.cpp

4588

We already handle this case using generic select equivalence replacement. The only reason we need this patch is that the select replacement needs to follow the implication X | Y == 0 => X == 0. (We could generalize the generic code to do that, but I'm fine with keeping it as a special case for now.)

[HerrCai0907]

split two patch, one for add test, another for add optimization

[HerrCai0907]

done. Thanks for your advice

[nikic]

LGTM

llvm/lib/Analysis/InstructionSimplify.cpp

if (simplifyWithOpReplaced(TrueVal, CmpLHS, CmpRHS, Q,
                                /* AllowRefinement */ true,
                                MaxRecurse) == FalseVal ||
         simplifyWithOpReplaced(TrueVal, CmpRHS, CmpLHS, Q,
                                /* AllowRefinement */ true,
                                MaxRecurse) == FalseVal)
       return FalseVal;
   }
 
+  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;
 }
 
 /// Try to simplify a select instruction when its condition operand is a
 /// floating-point comparison.
 static Value *simplifySelectWithFCmp(Value *Cond, Value *T, Value *F,
                                      const SimplifyQuery &Q) {
   FCmpInst::Predicate Pred;

llvm/test/Transforms/InstSimplify/select_or_and.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes=instsimplify < %s | FileCheck %s
 
 ; select(Y | X == 0, X, Y | X)
 define i32 @select_or_1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_or_1(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[OR]], 0
-; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[OR]]
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %or = or i32 %y, %x
   %cmp = icmp eq i32 %or, 0
   %ret = select i1 %cmp, i32 %x, i32 %or
   ret i32 %ret
 }
 
 ; select(Y | X == 0, Y, Y | X)
 define i32 @select_or_2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_or_2(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[OR]], 0
-; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[OR]]
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %or = or i32 %y, %x
   %cmp = icmp eq i32 %or, 0
   %ret = select i1 %cmp, i32 %y, i32 %or
   ret i32 %ret
 }
 
 ; select(Y | X != 0, Y | X, X)
 define i32 @select_or_3(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_or_3(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[OR]], 0
-; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 [[OR]], i32 [[X]]
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %or = or i32 %y, %x
   %cmp = icmp ne i32 %or, 0
   %ret = select i1 %cmp, i32 %or, i32 %x
   ret i32 %ret
 }
 
 ; select(Y | X != 0, Y | X, Y)
 define i32 @select_or_4(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_or_4(
 ; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[OR]], 0
-; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 [[OR]], i32 [[Y]]
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %or = or i32 %y, %x
   %cmp = icmp ne i32 %or, 0
   %ret = select i1 %cmp, i32 %or, i32 %y
   ret i32 %ret
 }
 
 ; select(Y | X != 0, Y | X, Y)
 define <4 x i32> @select_or_vec(<4 x i32> %x, <4 x i32> %y) {
 ; CHECK-LABEL: @select_or_vec(
 ; CHECK-NEXT:    [[OR:%.*]] = or <4 x i32> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne <4 x i32> [[OR]], zeroinitializer
-; CHECK-NEXT:    [[RET:%.*]] = select <4 x i1> [[CMP]], <4 x i32> [[OR]], <4 x i32> [[Y]]
-; CHECK-NEXT:    ret <4 x i32> [[RET]]
+; CHECK-NEXT:    ret <4 x i32> [[OR]]
 ;
   %or = or <4 x i32> %y, %x
   %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)
;
   %ret = select i1 %cmp, i32 %y, i32 %or
   ret i32 %ret
 }
 
 ; select(Y & X == -1, X, Y & X)
 define i32 @select_and_1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_and_1(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], -1
-; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[AND]]
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %and = and i32 %y, %x
   %cmp = icmp eq i32 %and, -1
   %ret = select i1 %cmp, i32 %x, i32 %and
   ret i32 %ret
 }
 
 ; select(Y & X == -1, Y, Y & X)
 define i32 @select_and_2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_and_2(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[AND]], -1
-; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 [[Y]], i32 [[AND]]
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %and = and i32 %y, %x
   %cmp = icmp eq i32 %and, -1
   %ret = select i1 %cmp, i32 %y, i32 %and
   ret i32 %ret
 }
 
 
 ; select(Y & X != -1, Y & X, X)
 define i32 @select_and_3(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_and_3(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], -1
-; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 [[AND]], i32 [[X]]
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %and = and i32 %y, %x
   %cmp = icmp ne i32 %and, -1
   %ret = select i1 %cmp, i32 %and, i32 %x
   ret i32 %ret
 }
 
 ; select(Y & X != -1, Y & X, Y)
 define i32 @select_and_4(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_and_4(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[AND]], -1
-; CHECK-NEXT:    [[RET:%.*]] = select i1 [[CMP]], i32 [[AND]], i32 [[Y]]
-; CHECK-NEXT:    ret i32 [[RET]]
+; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %and = and i32 %y, %x
   %cmp = icmp ne i32 %and, -1
   %ret = select i1 %cmp, i32 %and, i32 %y
   ret i32 %ret
 }
 
 ; select(Y & X != -1, Y, Y & X)