[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

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

3587

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 ↗

(On Diff #513473)

Already checked above.

llvm/test/Transforms/InstSimplify/select_or_and.ll

2 ↗

(On Diff #513473)

instsimplify

5 ↗

(On Diff #513473)

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 ↗

(On Diff #513987)

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 ↗

(On Diff #514038)

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

4588 ↗

(On Diff #514038)

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 ↗

(On Diff #514038)

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 ↗

(On Diff #514038)

ne will be changed to eq in line 4498

4588 ↗

(On Diff #514038)

I think it can be done in next patch

llvm/test/Transforms/InstSimplify/select_or_and.ll

11 ↗

(On Diff #514038)

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 ↗

(On Diff #514038)

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 ↗

(On Diff #514038)

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/Transforms/InstCombine/InstCombineSelect.cpp

if (FalseSI->getCondition()->getType() == CondVal->getType()) {
         Value *Or = Builder.CreateLogicalOr(CondVal, FalseSI->getCondition());
         replaceOperand(SI, 0, Or);
         replaceOperand(SI, 2, FalseSI->getFalseValue());
         return &SI;
       }
     }
   }
 
+  ICmpInst::Predicate Pred;
+  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())) &&
+      Pred == ICmpInst::Predicate::ICMP_EQ &&
+      match(FalseVal, m_Or(m_Value(X), m_Value(Y))) &&
+      (TrueVal == X || TrueVal == Y))
+    return replaceInstUsesWith(SI, FalseVal);
+  // select(X & Y == -1, X or Y, X & Y) -> X & Y
+  if (match(CondVal, m_ICmp(Pred, m_Specific(FalseVal), m_AllOnes())) &&
+      Pred == ICmpInst::Predicate::ICMP_EQ &&
+      match(FalseVal, m_And(m_Value(X), m_Value(Y))) &&
+      (TrueVal == X || TrueVal == Y))
+    return replaceInstUsesWith(SI, FalseVal);
+  
+
   // Try to simplify a binop sandwiched between 2 selects with the same
   // condition. This is not valid for div/rem because the select might be
   // preventing a division-by-zero.
   // TODO: A div/rem restriction is conservative; use something like
   //       isSafeToSpeculativelyExecute().
   // select(C, binop(select(C, X, Y), W), Z) -> select(C, binop(X, W), Z)
   BinaryOperator *TrueBO;
   if (match(TrueVal, m_OneUse(m_BinOp(TrueBO))) && !TrueBO->isIntDivRem()) {

llvm/test/Transforms/InstCombine/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
+}