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.

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

cmd/compile: create cheapdeadcode #39918

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

cmd/compile: create cheapdeadcode #39918

josharian opened this issue Jun 29, 2020 · 4 comments

Comments

@josharian
Copy link
Contributor

@josharian josharian commented Jun 29, 2020

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!

@dr2chase
Copy link
Contributor

@dr2chase dr2chase commented Jun 29, 2020

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 mundaym commented Jun 29, 2020

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

@randall77 randall77 commented Jun 29, 2020

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
Contributor

@erifan 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
5 participants
You can’t perform that action at this time.