cmd/compile: opt should match rules through phis

[Jorropo]

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]

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

[cherrymui]

cc @randall77 @dr2chase

[randall77]

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]

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]

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