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: opt should match rules through phis #53300

Open
Jorropo opened this issue Jun 9, 2022 · 5 comments
Open

cmd/compile: opt should match rules through phis #53300

Jorropo opened this issue Jun 9, 2022 · 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
Milestone
Unplanned

Comments

@Jorropo
Copy link
Member

Jorropo commented Jun 9, 2022 •
edited

The ssa opt pass currently abort matching if the rule go through a phis.

For example:

if c {
  y = -y
} else {
  y *= 2
}
x += y

Should be rewriten:

if c {
  x -= y
} else {
  x += y * 2
}

The necessary rules for that optimization already exists, but they can't be applied since a phi node is in the way.

When encountering a phi node opt should start a routine to apply the rule on all branches where that would remove uses of the previous values in that branch (this is because we don't want to generate dupped code that would slower) (and generate a new fallback block that applies the current operation for branches that didn't matched).

This could lead to a jump in codesize since multiple branches might have the same rules applies to them.
A pass that perform CSE but downward in the control flow would regain that lost space.

The extra compilation time cost might not be worth it.
@gopherbot
Copy link

Change https://go.dev/cl/411218 mentions this issue: cmd/compile: add new ssa pass csedown

@cherrymui cherrymui added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Jun 9, 2022
@cherrymui cherrymui added this to the Unplanned milestone Jun 9, 2022
@cherrymui
Copy link
Member

cc @randall77 @dr2chase

@randall77
Copy link
Contributor

I guess I'm missing the motivation here. In your given example the generated code would be a little bit better, sure. But I feel like that example is kind of contrived. Does this happen in real code? Can you point to some examples?

My other worry is that applying this transformation blindly would make some cases worse (at least, in code size) and maybe not help execution time at all. Is there any way to understand when performing this transformation might actually help?

@Jorropo
Copy link
Member Author

Jorropo commented Jun 10, 2022

I think so, I have seen this annecdotally.

I dont think there is much discussion to have without numbers.
However coding a thing to do stats on how much this optimisation would applies is I think about as much work than doing it in the first place.

In case that not clear i'm not asking for you to take time to code this, I'll (probably) send patches if my implementation is worth it.

@jake-volvo
Copy link

@Jorropo Hi, please try using compilecmp, it’s very handy. It will make it easy for you to spot code differences.

It would also be nice to see pass timings and run compilebench to see the impact on compile speed. AFAIK every optimization should try to “pay for itself” meaning it should improve the codegen enough to offset the extra time doing the optimization. I think this is extra important given the 10-15% compile time increases we have seen from generics.

I also recommend running the /tests/go1 test suite on a non noisy machine and then use benchstat to show the impact.

@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
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
5 participants
@randall77 @gopherbot @cherrymui @Jorropo @jake-volvo