[InstCombine] Improve select equiv fold for plain condition

[vfdff]

Fold select if the user of its select user indicates the condition

Fix https://github.com/llvm/llvm-project/issues/83225

[llvmbot]

@llvm/pr-subscribers-llvm-transforms

Author: Allen (vfdff)

Changes

Fold select if the user of its select user indicates the condition

Fix https://github.com/llvm/llvm-project/issues/83225

---

Full diff: https://github.com/llvm/llvm-project/pull/83405.diff

2 Files Affected:

• (modified) llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp (+26)
• (modified) llvm/test/Transforms/InstCombine/select.ll (+30)

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
index 71fa9b9ba41ebb..1485fe8674b720 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
@@ -500,6 +500,29 @@ static bool isSelect01(const APInt &C1I, const APInt &C2I) {
   return C1I.isOne() || C1I.isAllOnes() || C2I.isOne() || C2I.isAllOnes();
 }
 
+/// Try to simplify a select instruction when the user of its select user
+/// indicates the condition.
+static bool simplifySeqSelectWithSameCond(Value *Cond, Value *F) {
+  Value *FalseVal = F;
+  Value *CondNext;
+  Value *FalseNext;
+  while (match(FalseVal, m_Select(m_Value(CondNext), m_Value(),
+                                  m_OneUse(m_Value(FalseNext))))) {
+    if (CondNext == Cond) {
+      auto *SI = cast<SelectInst>(FalseVal);
+      LLVM_DEBUG(dbgs() << "IC: Fold " << SI << " with " << *FalseNext << '\n');
+
+      SI->replaceAllUsesWith(FalseNext);
+      SI->eraseFromParent();
+      return true;
+    }
+
+    FalseVal = FalseNext;
+  }
+
+  return false;
+}
+
 /// Try to fold the select into one of the operands to allow further
 /// optimization.
 Instruction *InstCombinerImpl::foldSelectIntoOp(SelectInst &SI, Value *TrueVal,
@@ -557,6 +580,9 @@ Instruction *InstCombinerImpl::foldSelectIntoOp(SelectInst &SI, Value *TrueVal,
   if (Instruction *R = TryFoldSelectIntoOp(SI, FalseVal, TrueVal, true))
     return R;
 
+  if (simplifySeqSelectWithSameCond(SI.getCondition(), FalseVal))
+    return &SI;
+
   return nullptr;
 }
 
diff --git a/llvm/test/Transforms/InstCombine/select.ll b/llvm/test/Transforms/InstCombine/select.ll
index c5f1b77c6d7404..068d168876a328 100644
--- a/llvm/test/Transforms/InstCombine/select.ll
+++ b/llvm/test/Transforms/InstCombine/select.ll
@@ -3672,3 +3672,33 @@ define i32 @src_select_xxory_eq0_xorxy_y(i32 %x, i32 %y) {
   %cond = select i1 %xor0, i32 %xor, i32 %y
   ret i32 %cond
 }
+
+define i32 @sequence_select_with_same_cond (i1 %c1, i1 %c2){
+; CHECK-LABEL: @sequence_select_with_same_cond(
+; CHECK-NEXT:    [[S1:%.*]] = select i1 [[C1:%.*]], i32 23, i32 45
+; CHECK-NEXT:    [[S2:%.*]] = select i1 [[C2:%.*]], i32 666, i32 [[S1]]
+; CHECK-NEXT:    [[S3:%.*]] = select i1 [[C1]], i32 789, i32 [[S2]]
+; CHECK-NEXT:    ret i32 [[S3]]
+;
+  %s1 = select i1 %c1, i32 23, i32 45
+  %s2 = select i1 %c2, i32 666, i32 %s1
+  %s3 = select i1 %c1, i32 789, i32 %s2
+  ret i32 %s3
+}
+
+declare void @use32(i32)
+
+define i32 @sequence_select_with_same_cond_extra_use (i1 %c1, i1 %c2){
+; CHECK-LABEL: @sequence_select_with_same_cond_extra_use(
+; CHECK-NEXT:    [[S1:%.*]] = select i1 [[C1:%.*]], i32 23, i32 45
+; CHECK-NEXT:    call void @use32(i32 [[S1]])
+; CHECK-NEXT:    [[S2:%.*]] = select i1 [[C2:%.*]], i32 666, i32 [[S1]]
+; CHECK-NEXT:    [[S3:%.*]] = select i1 [[C1]], i32 789, i32 [[S2]]
+; CHECK-NEXT:    ret i32 [[S3]]
+;
+  %s1 = select i1 %c1, i32 23, i32 45
+  call void @use32(i32 %s1)
+  %s2 = select i1 %c2, i32 666, i32 %s1
+  %s3 = select i1 %c1, i32 789, i32 %s2
+  ret i32 %s3
+}

[nikic]

I think this should be a minor generalization of some existing simplifyWithOpReplaced or foldSelectValueEquivalence style fold.

[vfdff]

I think this should be a minor generalization of some existing simplifyWithOpReplaced or foldSelectValueEquivalence style fold. Thanks, refactor with simplifyWithOpReplaced. （foldSelectValueEquivalence is used for select + cmp）

[nikic]

FWIW, what I had in mind with my comment was more something along the lines of https://github.com/llvm/llvm-project/pull/85663, which generalizes the existing select equivalence fold. The disadvantage is that it does not handle the multi-use example out of the box (but could be generalized).

[vfdff]

FWIW, what I had in mind with my comment was more something along the lines of #85663, which generalizes the existing select equivalence fold. The disadvantage is that it does not handle the multi-use example out of the box (but could be generalized).

hi @nikic, I saw #85663 is closed because the compile time regression, so would you suggest I continue with current solution?

[arsenm]

Title isn't clear to me

[dtcxzyw]

@vfdff Could you please rebase this patch on main?

[github-actions[bot]]

:white_check_mark: With the latest revision this PR passed the C/C++ code formatter.

[github-actions[bot]]

:white_check_mark: With the latest revision this PR passed the Python code formatter.

[vfdff]

@vfdff Could you please rebase this patch on main?

Thanks for the reminder. I found that the test cases have been committed in advance. (commit bd9a2afa)

[goldsteinn]

LGTM.

[vfdff]

ping ？

[goldsteinn]

Still LGTM, ping @dtcxzyw @nikic

[vfdff]

According performace considerations, I deleted the support with multi-use select node and rebase to top upstream as the code conflicts.

[vfdff]

ping @dtcxzyw, @arsenm

[vfdff]

close to avoid blocking other solutions

[arsenm]

close to avoid blocking other solutions

What do you mean? If there's an alternative patch, it should be mentioned in the closing message. Otherwise, why close it

[vfdff]

Oh，sorry, I reopen it now. I close it because the solution is limit to single-use select node, which seems not perfect :)

[arsenm]

Oh，sorry, I reopen it now. I close it because the solution is limit to single-use select node, which seems not perfect :)

That is the solution to many combine problems. It's a common and reasonable restriction

[dtcxzyw]

Ping. I need this patch to unblock https://github.com/llvm/llvm-project/pull/119884. I noticed this patch when drafting an alternative with replaceInInstruction.

[vfdff]

hi @dtcxzyw I don't work on this issue now, please update your MR at your convenience