-
Notifications
You must be signed in to change notification settings - Fork 11.4k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[SimplifyCFG] Forward indirect switch condition value if it can help fold the PHI #95932
Conversation
@llvm/pr-subscribers-backend-aarch64 @llvm/pr-subscribers-llvm-transforms Author: DianQK (DianQK) ChangesFixes #95919. To me, this limit doesn't make sense. Full diff: https://github.com/llvm/llvm-project/pull/95932.diff 4 Files Affected:
diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index 4e2dc7f2b2f4e..5a4c258937a27 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -5818,8 +5818,6 @@ static bool ForwardSwitchConditionToPHI(SwitchInst *SI) {
for (auto &ForwardingNode : ForwardingNodes) {
PHINode *Phi = ForwardingNode.first;
SmallVectorImpl<int> &Indexes = ForwardingNode.second;
- if (Indexes.size() < 2)
- continue;
for (int Index : Indexes)
Phi->setIncomingValue(Index, SI->getCondition());
diff --git a/llvm/test/CodeGen/AArch64/arm64-jumptable.ll b/llvm/test/CodeGen/AArch64/arm64-jumptable.ll
index 7d9adf92a6a95..40b8f721c0505 100644
--- a/llvm/test/CodeGen/AArch64/arm64-jumptable.ll
+++ b/llvm/test/CodeGen/AArch64/arm64-jumptable.ll
@@ -18,7 +18,7 @@ bb3:
bb4:
br label %exit.sink.split
exit.sink.split:
- %.sink = phi i32 [ 5, %bb4 ], [ %b, %bb1 ], [ 3, %bb3 ], [ %a, %entry ]
+ %.sink = phi i32 [ 5, %bb4 ], [ %b, %bb1 ], [ 7, %bb3 ], [ %a, %entry ]
store i32 %.sink, ptr %to
br label %exit
exit:
diff --git a/llvm/test/Transforms/SimplifyCFG/ForwardSwitchConditionToPHI.ll b/llvm/test/Transforms/SimplifyCFG/ForwardSwitchConditionToPHI.ll
index 5c266f4867398..5e00a4b098f68 100644
--- a/llvm/test/Transforms/SimplifyCFG/ForwardSwitchConditionToPHI.ll
+++ b/llvm/test/Transforms/SimplifyCFG/ForwardSwitchConditionToPHI.ll
@@ -59,6 +59,75 @@ return: ; preds = %entry, %sw.bb4, %sw
ret i32 %retval.0
}
+define i32 @forward_one(i32 %m) {
+; NO_FWD-LABEL: @forward_one(
+; NO_FWD-NEXT: entry:
+; NO_FWD-NEXT: switch i32 [[M:%.*]], label [[SW_BB4:%.*]] [
+; NO_FWD-NEXT: i32 0, label [[RETURN:%.*]]
+; NO_FWD-NEXT: i32 1, label [[SW_BB1:%.*]]
+; NO_FWD-NEXT: i32 2, label [[SW_BB2:%.*]]
+; NO_FWD-NEXT: i32 3, label [[SW_BB3:%.*]]
+; NO_FWD-NEXT: ]
+; NO_FWD: sw.bb1:
+; NO_FWD-NEXT: br label [[RETURN]]
+; NO_FWD: sw.bb2:
+; NO_FWD-NEXT: br label [[RETURN]]
+; NO_FWD: sw.bb3:
+; NO_FWD-NEXT: br label [[RETURN]]
+; NO_FWD: sw.bb4:
+; NO_FWD-NEXT: br label [[RETURN]]
+; NO_FWD: return:
+; NO_FWD-NEXT: [[RETVAL_0:%.*]] = phi i32 [ 4, [[SW_BB4]] ], [ 5, [[SW_BB3]] ], [ 6, [[SW_BB2]] ], [ 1, [[SW_BB1]] ], [ 8, [[ENTRY:%.*]] ]
+; NO_FWD-NEXT: ret i32 [[RETVAL_0]]
+;
+; FWD-LABEL: @forward_one(
+; FWD-NEXT: entry:
+; FWD-NEXT: switch i32 [[M:%.*]], label [[SW_BB4:%.*]] [
+; FWD-NEXT: i32 0, label [[RETURN:%.*]]
+; FWD-NEXT: i32 1, label [[SW_BB1:%.*]]
+; FWD-NEXT: i32 2, label [[SW_BB2:%.*]]
+; FWD-NEXT: i32 3, label [[SW_BB3:%.*]]
+; FWD-NEXT: ]
+; FWD: sw.bb1:
+; FWD-NEXT: br label [[RETURN]]
+; FWD: sw.bb2:
+; FWD-NEXT: br label [[RETURN]]
+; FWD: sw.bb3:
+; FWD-NEXT: br label [[RETURN]]
+; FWD: sw.bb4:
+; FWD-NEXT: br label [[RETURN]]
+; FWD: return:
+; FWD-NEXT: [[RETVAL_0:%.*]] = phi i32 [ 4, [[SW_BB4]] ], [ 5, [[SW_BB3]] ], [ 6, [[SW_BB2]] ], [ [[M]], [[SW_BB1]] ], [ 8, [[ENTRY:%.*]] ]
+; FWD-NEXT: ret i32 [[RETVAL_0]]
+;
+entry:
+ switch i32 %m, label %sw.bb4 [
+ i32 0, label %sw.bb0
+ i32 1, label %sw.bb1
+ i32 2, label %sw.bb2
+ i32 3, label %sw.bb3
+ ]
+
+sw.bb0: ; preds = %entry
+ br label %return
+
+sw.bb1: ; preds = %entry
+ br label %return
+
+sw.bb2: ; preds = %entry
+ br label %return
+
+sw.bb3: ; preds = %entry
+ br label %return
+
+sw.bb4: ; preds = %entry
+ br label %return
+
+return: ; preds = %entry, %sw.bb4, %sw.bb3, %sw.bb2, %sw.bb1
+ %retval.0 = phi i32 [ 4, %sw.bb4 ], [ 5, %sw.bb3 ], [ 6, %sw.bb2 ], [ 1, %sw.bb1 ], [ 8, %sw.bb0 ]
+ ret i32 %retval.0
+}
+
; If 1 incoming phi value is a case constant of a switch, convert it to the switch condition:
; https://bugs.llvm.org/show_bug.cgi?id=34471
; This then subsequently should allow squashing of the other trivial case blocks.
diff --git a/llvm/test/Transforms/SimplifyCFG/Hexagon/switch-to-lookup-table.ll b/llvm/test/Transforms/SimplifyCFG/Hexagon/switch-to-lookup-table.ll
index 47dd24e194c39..b3b6abe314e6f 100644
--- a/llvm/test/Transforms/SimplifyCFG/Hexagon/switch-to-lookup-table.ll
+++ b/llvm/test/Transforms/SimplifyCFG/Hexagon/switch-to-lookup-table.ll
@@ -43,7 +43,7 @@ define i32 @foo(i32 %x) #0 section ".tcm_text" {
; DISABLE: sw.default:
; DISABLE-NEXT: br label [[RETURN]]
; DISABLE: return:
-; DISABLE-NEXT: [[RETVAL_0:%.*]] = phi i32 [ 19, [[SW_DEFAULT]] ], [ 5, [[SW_BB5]] ], [ 12, [[SW_BB4]] ], [ 22, [[SW_BB3]] ], [ 14, [[SW_BB2]] ], [ 20, [[SW_BB1]] ], [ 9, [[ENTRY:%.*]] ]
+; DISABLE-NEXT: [[RETVAL_0:%.*]] = phi i32 [ 19, [[SW_DEFAULT]] ], [ 33, [[SW_BB5]] ], [ 12, [[SW_BB4]] ], [ 22, [[SW_BB3]] ], [ 14, [[SW_BB2]] ], [ 20, [[SW_BB1]] ], [ 9, [[ENTRY:%.*]] ]
; DISABLE-NEXT: ret i32 [[RETVAL_0]]
;
entry:
@@ -81,7 +81,7 @@ sw.bb4: ; preds = %entry
br label %return
sw.bb5: ; preds = %entry
- store i32 5, ptr %retval, align 4
+ store i32 33, ptr %retval, align 4
br label %return
sw.default: ; preds = %entry
|
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Is it possible to also add a test case where this shows an actual benefit like in #95919? Or does this require multiple passes?
26955f3
to
5cb0f4d
Compare
Yes, the existing |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
LGTM. Thank you!
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
LGTM
Looks like I added this in 4ab4a8e I think the point of the llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp Lines 5774 to 5776 in 9cbedd9
The point of the forwarding is to make multiple blocks produce the same value for the phi node (the switch condition), so that they can be folded into one block. If we're forwarding the condition value for just a single block, that's just replacing a constant with a non-constant which seems counter-productive in general. Looking at the example in #95919
What makes that beneficial is that the incoming value for
|
Thank you for your explanation. However, I still think is meaningful. I've chosen some examples to demonstrate the final results in assembly code. Analyzing more practical changes might be challenging, so I'm comparing the number of instructions, which might not be ideal but should at least show that this transformation is not harmful.
I suspect the main optimization here comes from register reuse. I'm not sure how this would perform within a large function body, as it might complicate instruction selection. For me, another important point is that we can easily revert this forward if needed for other Passes. However, turning constants back into variables requires the dominance information. |
(I can't access the alive2 links, the server seems to be down?) I don't have any strong opinion about whether always "forwarding" the switch condition is right or wrong. I suppose it comes down to what the following passes are best able to handle, and @nikic is probably the right person to answer that. On the one hand, it seems bad to replace constants with a variable -- that's why 4ab4a8e was conservative and only does it when it's likely to cause blocks to get folded. On the other hand, as you say, it's easy to propagate such constants later. I do think my diff above would fix your use case? So if we do decide to "always forward" I think we need some motivation, and we should update the comment for |
It's a tricky question. I'd generally say that having constants instead of variables is "more canonical" -- and in fact, we have quite a lot of passes that will undo what SimplifyCFG does here. At least IPSCCP, CVP and GVN do this. This is bad in itself, because it means that IR toggles back and forth between two forms. Conversely, it also means that many passes have a chance to optimize IR in both forms. The backend generally prefers phi operands not to be constants (though this is a pretty generic problem and SimplifyCFG isn't really the place to address it I think). |
Fixed. GitHub seems to not recognize
I think so, but it would also make this part of the code a bit more complex. In fact, I don't have a clear choice for the change here. |
I have seen some similar things. These transforms are just back and forth, and it doesn't seem like they are being utilized. |
In this PR, I will change it to forward when it finds phi folding, which aligns more with SimplifyCFG behavior. |
This patch will cause values in the PHI to become switch condition values, leading to an infinite loop. Additionally, it doesn't align well with the intent of the function. I have changed it to check if the PHI already contains the switch condition value. Forwarding is meaningful for the test case in this PR: https://alive2.llvm.org/ce/z/Z46qt6.
|
@zmodem Any more comments? :) |
https://lab.llvm.org/buildbot/#/builders/72/builds/483 is likely flake |
😄 I should wait for the next result. |
…an help fold the PHI (#95932)" This reverts commit 0c56fd0. This is breaking https://lab.llvm.org/buildbot/#/builders/72/builds/483.
…an help fold the PHI (#95932)" This reverts commit 0c56fd0. This is breaking https://lab.llvm.org/buildbot/#/builders/72/builds/483.
…an help fold the PHI (#95932)" This reverts commit 0c56fd0. This is breaking https://lab.llvm.org/buildbot/#/builders/72/builds/483.
…an help fold the PHI (#95932)" This reverts commit 0c56fd0. This is breaking https://lab.llvm.org/buildbot/#/builders/72/builds/483.
…an help fold the PHI (#95932)" This reverts commit 0c56fd0. This is breaking https://lab.llvm.org/buildbot/#/builders/72/builds/483.
…fold the PHI (llvm#95932) Fixes llvm#95919.
…an help fold the PHI (llvm#95932)" This reverts commit 0c56fd0. This is breaking https://lab.llvm.org/buildbot/#/builders/72/builds/483.
…can help fold the PHI (llvm#95932)" This reverts commit c7adfb5.
…an help fold the PHI (#95932)" This reverts commit 0c56fd0. This is breaking https://lab.llvm.org/buildbot/#/builders/72/builds/483.
…fold the PHI (llvm#95932) Fixes llvm#95919.
…an help fold the PHI (llvm#95932)" This reverts commit 0c56fd0. This is breaking https://lab.llvm.org/buildbot/#/builders/72/builds/483.
…can help fold the PHI (llvm#95932)" This reverts commit c7adfb5.
Fixes #95919.