[go] cmd/compile: optimize sccp for faster convergence
Gerrit Bot (Gerrit)
Gerrit Bot has uploaded the change for review![]( "Open in Gerrit")
Commit message
cmd/compile: optimize sccp for faster convergence
While investigating other optimizations, I found several opportunities to accelerate sccp convergence.
- avoid adding duplicate ueses to the re-visit worklist
- prevent queueing uses of values that have already reached Bottom
- add an early exit when processing a value that is already Bottom
These changes provide an overall speedup of ~9% for sccp during a full make.bash run
Updates #77325
Change diff
diff --git a/src/cmd/compile/internal/ssa/sccp.go b/src/cmd/compile/internal/ssa/sccp.go
index ecc0f94..613b0ff 100644
--- a/src/cmd/compile/internal/ssa/sccp.go
+++ b/src/cmd/compile/internal/ssa/sccp.go
@@ -54,6 +54,7 @@
type worklist struct {
f *Func // the target function to be optimized out
edges []Edge // propagate constant facts through edges
+ inUses *sparseSet // IDs already in uses, for duplicate check
uses []*Value // re-visiting set
visited map[Edge]bool // visited edges
latticeCells map[*Value]lattice // constant lattices
@@ -75,6 +76,8 @@
t.defBlock = make(map[*Value][]*Block)
t.latticeCells = make(map[*Value]lattice)
t.visitedBlock = f.Cache.allocBoolSlice(f.NumBlocks())
+ t.inUses = f.newSparseSet(f.NumValues())
+ defer f.retSparseSet(t.inUses)
defer f.Cache.freeBoolSlice(t.visitedBlock)
// build it early since we rely heavily on the def-use chain later
@@ -108,6 +111,7 @@
if len(t.uses) > 0 {
use := t.uses[0]
t.uses = t.uses[1:]
+ t.inUses.remove(use.ID)
t.visitValue(use)
continue
}
@@ -274,12 +278,20 @@
// addUses finds all uses of value and appends them into work list for further process
func (t *worklist) addUses(val *Value) {
for _, use := range t.defUse[val] {
+ // Phi may refer to itself as uses, avoid duplicate visits
if val == use {
- // Phi may refer to itself as uses, ignore them to avoid re-visiting phi
- // for performance reason
continue
}
- t.uses = append(t.uses, use)
+ // Provenly not a constant, ignore
+ useLt := t.getLatticeCell(use)
+ if useLt.tag == bottom {
+ continue
+ }
+ // Avoid duplicate visits
+ if !t.inUses.contains(use.ID) {
+ t.inUses.add(use.ID)
+ t.uses = append(t.uses, use)
+ }
}
for _, block := range t.defBlock[val] {
if t.visitedBlock[block.ID] {
@@ -366,15 +378,19 @@
}
func (t *worklist) visitValue(val *Value) {
+ // Impossible to be a constant, fast fail
if !possibleConst(val) {
- // fast fail for always worst Values, i.e. there is no lowering happen
- // on them, their lattices must be initially worse Bottom.
return
}
+ // Provenly not a constant, fast fail
oldLt := t.getLatticeCell(val)
+ if oldLt.tag == bottom {
+ return
+ }
+
+ // Re-visit all uses of value if its lattice is changed
defer func() {
- // re-visit all uses of value if its lattice is changed
newLt := t.getLatticeCell(val)
if !equals(newLt, oldLt) {
if int8(oldLt.tag) > int8(newLt.tag) {
Change information
- M src/cmd/compile/internal/ssa/sccp.go
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gopher Robot (Gerrit)
Gopher Robot added 1 comment![]( "Open in Gerrit")
I spotted some possible problems with your PR:
1. You have a long 102 character line in the commit message body. Please add line breaks to long lines that should be wrapped. Lines in the commit message body should be wrapped at ~76 characters unless needed for things like URLs or tables. (Note: GitHub might render long lines as soft-wrapped, so double-check in the Gerrit commit message shown above.)
Please address any problems by updating the GitHub PR.
When complete, mark this comment as 'Done' and click the [blue 'Reply' button](https://go.dev/wiki/GerritBot#i-left-a-reply-to-a-comment-in-gerrit-but-no-one-but-me-can-see-it) above. These findings are based on heuristics; if a finding does not apply, briefly reply here saying so.
To update the commit title or commit message body shown here in Gerrit, you must edit the GitHub PR title and PR description (the first comment) in the GitHub web interface using the 'Edit' button or 'Edit' menu entry there. Note: pushing a new commit to the PR will not automatically update the commit message used by Gerrit.
For more details, see:
- [how to update commit messages](https://go.dev/wiki/GerritBot/#how-does-gerritbot-determine-the-final-commit-message) for PRs imported into Gerrit.
- the Go project's [conventions for commit messages](https://go.dev/doc/contribute#commit_messages) that you should follow.
(In general for Gerrit code reviews, the change author is expected to [log in to Gerrit](https://go-review.googlesource.com/login/) with a Gmail or other Google account and then close out each piece of feedback by marking it as 'Done' if implemented as suggested or otherwise reply to each review comment. See the [Review](https://go.dev/doc/contribute#review) section of the Contributing Guide for details.)
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gerrit Bot (Gerrit)
Gerrit Bot uploaded new patchset![]( "Open in Gerrit")
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Yi Yang (Gerrit)
Yi Yang added 1 comment![]( "Open in Gerrit")
I spotted some possible problems with your PR:
1. You have a long 102 character line in the commit message body. Please add line breaks to long lines that should be wrapped. Lines in the commit message body should be wrapped at ~76 characters unless needed for things like URLs or tables. (Note: GitHub might render long lines as soft-wrapped, so double-check in the Gerrit commit message shown above.)Please address any problems by updating the GitHub PR.
When complete, mark this comment as 'Done' and click the [blue 'Reply' button](https://go.dev/wiki/GerritBot#i-left-a-reply-to-a-comment-in-gerrit-but-no-one-but-me-can-see-it) above. These findings are based on heuristics; if a finding does not apply, briefly reply here saying so.
To update the commit title or commit message body shown here in Gerrit, you must edit the GitHub PR title and PR description (the first comment) in the GitHub web interface using the 'Edit' button or 'Edit' menu entry there. Note: pushing a new commit to the PR will not automatically update the commit message used by Gerrit.
For more details, see:
- [how to update commit messages](https://go.dev/wiki/GerritBot/#how-does-gerritbot-determine-the-final-commit-message) for PRs imported into Gerrit.
- the Go project's [conventions for commit messages](https://go.dev/doc/contribute#commit_messages) that you should follow.
(In general for Gerrit code reviews, the change author is expected to [log in to Gerrit](https://go-review.googlesource.com/login/) with a Gmail or other Google account and then close out each piece of feedback by marking it as 'Done' if implemented as suggested or otherwise reply to each review comment. See the [Review](https://go.dev/doc/contribute#review) section of the Contributing Guide for details.)
Done
Related details
- Keith Randall
- Martin Möhrmann
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Jorropo (Gerrit)
Jorropo voted and added 4 comments![]( "Open in Gerrit")
Votes added by Jorropo
| Commit-Queue | +1 |
4 comments
Updates #77325That number looks wrong:
> optimize string concatenation to avoid runtime calls
inUses *sparseSet // IDs already in uses, for duplicate checkIt looks to me like you want to use a bitset instead.
Since SCCP visits most values in the function and you want to store one bit per value.
(value IDs are dense)
latticeCells map[*Value]lattice // constant latticesIf you want an other optimization to try all the maps in this struct shouldn't be maps.
You can use the assumption that IDs are dense (thanks to the ID allocator and value cache).
And theses should be slices indexed by `val.ID`.
The only slightly involved change is `latticeCells` since it ranges over the map and there is no simple `id` → `*Value` lookup (a simple fix is to use a type like `[]struct{v *Value; l lattice}`).
Related details
- Keith Randall
- Martin Möhrmann
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Yi Yang (Gerrit)
Yi Yang added 3 comments![]( "Open in Gerrit")
Updates #77325That number looks wrong:
> optimize string concatenation to avoid runtime calls
I'm referencing #77325 as this patch is a prerequisite for it.
inUses *sparseSet // IDs already in uses, for duplicate checkIt looks to me like you want to use a bitset instead.
Since SCCP visits most values in the function and you want to store one bit per value.
(value IDs are dense)
SCCP is sparse, it only visits a small number of values, not most of them.
Do you mean I should use a `uses []*Value` slice indexed by val.ID, instead of the inUses+uses combination?
latticeCells map[*Value]lattice // constant latticesIf you want an other optimization to try all the maps in this struct shouldn't be maps.
You can use the assumption that IDs are dense (thanks to the ID allocator and value cache).
And theses should be slices indexed by `val.ID`.The only slightly involved change is `latticeCells` since it ranges over the map and there is no simple `id` → `*Value` lookup (a simple fix is to use a type like `[]struct{v *Value; l lattice}`).
I suspect `visited map[Edge]bool` is the main performance bottleneck here. We could probably replace it with a slice later on. The others seem less critical.
Related details
- Jorropo
- Keith Randall
- Martin Möhrmann
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Yi Yang (Gerrit)
Yi Yang added 1 comment![]( "Open in Gerrit")
inUses *sparseSet // IDs already in uses, for duplicate checkYi YangIt looks to me like you want to use a bitset instead.
Since SCCP visits most values in the function and you want to store one bit per value.
(value IDs are dense)
SCCP is sparse, it only visits a small number of values, not most of them.
Do you mean I should use a `uses []*Value` slice indexed by val.ID, instead of the inUses+uses combination?
it only visits -> it only propagates
Gerrit Bot (Gerrit)
Gerrit Bot uploaded new patchset![]( "Open in Gerrit")
- TryBots-Pass: LUCI-TryBot-Result-1 by Go LUCI
Related details
- Jorropo
- Keith Randall
- Martin Möhrmann
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Yi Yang (Gerrit)
Yi Yang added 1 comment![]( "Open in Gerrit")
The TryBot error seems unrelated to this patch. I suspect it was caused by my branch not being up-to-date with master. I have merged master now. Could a reviewer please help re-trigger the TryBot run?
Related details
- Jorropo
- Keith Randall
- Martin Möhrmann
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Keith Randall (Gerrit)
Keith Randall voted Commit-Queue+1![]( "Open in Gerrit")
- Jorropo
- Martin Möhrmann
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Yi Yang (Gerrit)
Yi Yang added 1 comment![]( "Open in Gerrit")
So what should I do next? Can the review be taken a step further? Thanks
Related details
- Jorropo
- Martin Möhrmann
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Keith Randall (Gerrit)
Keith Randall added 1 comment![]( "Open in Gerrit")
So what should I do next? Can the review be taken a step further? Thanks
Sorry, generally we only revisit CLs once all comments have been resolved.
You should act on any comments from reviewers so far (do what they ask, or explain why it isn't a good idea, or whatever) and mark those comments as resolved.
Related details
- Jorropo
- Martin Möhrmann
- Yi Yang
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Yi Yang (Gerrit)
Yi Yang added 2 comments![]( "Open in Gerrit")
Thanks for the detailed explanation, @Keith, I get it now.
I think I've addressed all the comments. @Jorropo, please let me know if you have any other concerns.
I've marked the threads as resolved to keep things moving.
inUses *sparseSet // IDs already in uses, for duplicate checkYi YangIt looks to me like you want to use a bitset instead.
Since SCCP visits most values in the function and you want to store one bit per value.
(value IDs are dense)
Yi YangSCCP is sparse, it only visits a small number of values, not most of them.
Do you mean I should use a `uses []*Value` slice indexed by val.ID, instead of the inUses+uses combination?
it only visits -> it only propagates
Done
Related details
- Jorropo
- Martin Möhrmann
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Keith Randall (Gerrit)
Keith Randall voted and added 1 comment![]( "Open in Gerrit")
Votes added by Keith Randall
| Code-Review | +2 |
1 comment
if val == use {This seems like it would be better fixed by just not putting the use in the defUse map in the first place.
Related details
- Jorropo
- Martin Möhrmann
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Keith Randall (Gerrit)
Keith Randall voted Code-Review+1![]( "Open in Gerrit")
| Code-Review | +1 |
Related details
- Jorropo
- Martin Möhrmann
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |