Skip to content
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.

Sign up for GitHub

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

Jump to bottom

cmd/compile: create cheapdeadcode #39918

Open
josharian opened this issue Jun 29, 2020 · 5 comments
Open

cmd/compile: create cheapdeadcode #39918

josharian opened this issue Jun 29, 2020 · 5 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance ToolSpeed
Milestone
Unplanned

Comments

@josharian
Copy link
Contributor

There are a number of places in the SSA pipeline where it would produce better code if we could run deadcode. However, deadcode is expensive.

I suspect we could create a cheaper, only slightly less effective version of deadcode:

  • Instead of building a full value liveness graph, eliminate only values that have v.Uses == 0.
  • Continue eliminating dead blocks.

One complication is line number handling, which currently depends on an ordering map which is created while building the full value liveness graph. I am not sure how best to address this; I find the existing code confusing. Perhaps @dr2chase has ideas.

We could use it in more places; we could probably also replace many uses of the full deadcode pass with it. I suspect this would end up improving both compiled code quality and compiler performance.

This is a reminder issue to investigate this. It's probably not a good introduction to the compiler, but help is definitely welcome!
@josharian josharian added Performance ToolSpeed NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Jun 29, 2020
@josharian josharian added this to the Unplanned milestone Jun 29, 2020
@dr2chase
Copy link
Contributor

A line-numbering hack is to remember which ones were "lost" in a block, then do a second pass, looking for an "eligible" new home. Eligible means that it hits certain requirements for Op type, and ties are broken by "has no inputs from same line" (i.e., the "first" instruction in the line). Ineligible ops are encoded in isPoorStatementOp(op).

If there's no replacement in the same block, other heuristics might help. If the eliminated instruction has an eligible input on the same line (this should not be common, goal of line-numbering heuristics is to find the first "real" Op on a line), go there. Otherwise if blocks are in flow order, a successor might contain a new home, so carry that it forward.

@mundaym
Copy link
Member

mundaym commented Jun 29, 2020 •
edited

eliminate only values that have v.Uses == 0

Some optimization rules result in dangling values without any uses. Having a cheaper deadcode that ran as part of the rewrite passes would be very handy for helping v.Uses == 1 constraints fire reliably, and should allow us to drop the clobberIfDead function that is currently used as a workaround for this issue (usually to allow unaligned load/store ops to be matched).

@randall77
Copy link
Contributor

A little bit ago I hacked a CL that eliminates Uses==0 values during rewrite. I needed it to force some Uses==1 rules to trigger. Unfortunately, it caused the assembler to enter an infinite loop. Not sure what that was about, and never tracked it down.

@erifan
Copy link

erifan commented Jun 30, 2020

I suspect this would end up improving both compiled code quality and compiler performance.

It is definitely true. If there is a cheaper DCE, then we can call it in more places where it is needed and more optimization opportunities will appear. For example, the fuse pass, if we can clean up dead blocks in time, we can handle more situations.

@gopherbot
Copy link

Change https://golang.org/cl/249463 mentions this issue: cmd/compile: invalidate zero-use values during rewrite

gopherbot pushed a commit that referenced this issue Aug 27, 2020
@randall77
cmd/compile: invalidate zero-use values during rewrite
cdc6355 
This helps remove uses that aren't needed any more.
That in turn helps other rules with Uses==1 conditions fire.

Update #39918

Change-Id: I68635b675472f1d59e59604e4d34b949a0016533
Reviewed-on: https://go-review.googlesource.com/c/go/+/249463
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com>
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance ToolSpeed
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
6 participants
@josharian @dr2chase @randall77 @gopherbot @mundaym @erifan