[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

3

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

12

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

12

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

12

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 (Pred == ICmpInst::Predicate::ICMP_EQ &&
+        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=instcombine < %s | FileCheck %s
+
+; select(Y | X == 0, X, Y | X)
+define i32 @select_or_1(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_or_1(
+; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
+  %3 = or i32 %1, %0
+  %4 = icmp eq i32 %3, 0
+  %5 = select i1 %4, i32 %0, i32 %3
+  ret i32 %5
+}
+
+; select(Y | X == 0, Y, Y | X)
+define i32 @select_or_2(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_or_2(
+; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
+  %3 = or i32 %1, %0
+  %4 = icmp eq i32 %3, 0
+  %5 = select i1 %4, i32 %1, i32 %3
+  ret i32 %5
+}
+
+; select(Y | X != 0, Y | X, X)
+define i32 @select_or_3(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_or_3(
+; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
+  %3 = or i32 %1, %0
+  %4 = icmp ne i32 %3, 0
+  %5 = select i1 %4, i32 %3, i32 %0
+  ret i32 %5
+}
+
+; select(Y | X != 0, Y | X, Y)
+define i32 @select_or_4(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_or_4(
+; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
+  %3 = or i32 %1, %0
+  %4 = icmp ne i32 %3, 0
+  %5 = select i1 %4, i32 %3, i32 %1
+  ret i32 %5
+}
+
+; select(Y | X == 0, Y | X, Y)
+define i32 @select_or_not_1(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_or_not_1(
+; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 0
+; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i32 0, i32 [[TMP1]]
+; CHECK-NEXT:    ret i32 [[TMP5]]
+;
+  %3 = or i32 %1, %0
+  %4 = icmp eq i32 %3, 0
+  %5 = select i1 %4, i32 %3, i32 %1
+  ret i32 %5
+}
+; select(Y | X != 0, Y, Y | X)
+define i32 @select_or_not_2(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_or_not_2(
+; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], 0
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[DOTNOT]], i32 0, i32 [[TMP1]]
+; CHECK-NEXT:    ret i32 [[TMP4]]
+;
+  %3 = or i32 %1, %0
+  %4 = icmp ne i32 %3, 0
+  %5 = select i1 %4, i32 %1, i32 %3
+  ret i32 %5
+}
+
+; select(Y & X == -1, X, Y & X)
+define i32 @select_and_1(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_and_1(
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
+  %3 = and i32 %1, %0
+  %4 = icmp eq i32 %3, -1
+  %5 = select i1 %4, i32 %0, i32 %3
+  ret i32 %5
+}
+
+; select(Y & X == -1, Y, Y & X)
+define i32 @select_and_2(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_and_2(
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
+  %3 = and i32 %1, %0
+  %4 = icmp eq i32 %3, -1
+  %5 = select i1 %4, i32 %1, i32 %3
+  ret i32 %5
+}
+
+
+; select(Y & X != -1, Y & X, X)
+define i32 @select_and_3(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_and_3(
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
+  %3 = and i32 %1, %0
+  %4 = icmp ne i32 %3, -1
+  %5 = select i1 %4, i32 %3, i32 %0
+  ret i32 %5
+}
+
+; select(Y & X != -1, Y & X, Y)
+define i32 @select_and_4(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_and_4(
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
+  %3 = and i32 %1, %0
+  %4 = icmp ne i32 %3, -1
+  %5 = select i1 %4, i32 %3, i32 %1
+  ret i32 %5
+}
+
+; select(Y & X != -1, Y, Y & X)
+define i32 @select_and_not_1(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_and_not_1(
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP3]], -1
+; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i32 -1, i32 [[TMP1]]
+; CHECK-NEXT:    ret i32 [[TMP5]]
+;
+  %3 = and i32 %1, %0
+  %4 = icmp eq i32 %3, -1
+  %5 = select i1 %4, i32 %3, i32 %1
+  ret i32 %5
+}
+
+; select(Y & X != -1, Y, Y & X)
+define i32 @select_and_not_2(i32 %0, i32 %1) {
+; CHECK-LABEL: @select_and_not_2(
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i32 [[TMP3]], -1
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[DOTNOT]], i32 -1, i32 [[TMP1]]
+; CHECK-NEXT:    ret i32 [[TMP4]]
+;
+  %3 = and i32 %1, %0
+  %4 = icmp ne i32 %3, -1
+  %5 = select i1 %4, i32 %1, i32 %3
+  ret i32 %5
+}