Cranelift: Revive division-by-constant magic sequences #11129
Conversation
The application of these sequences have been ported to ISLE now to better integrate with our existing mid-end optimizations and to allow for recursive rule application in the optimized right-hand sides. Fixes bytecodealliance#6049
There was a problem hiding this comment.
Very nice 👍. Review-wise the main thing I did was double-check that the eval_* functions match the ISLE lowerings of the instructions to ensure that all the goodness of the proptest/test suite/etc mirrors into ISLE well. Very much appreciate the extensive test suite here!
A few thoughts:
- Could the proptest bits be expanded to
{u,s}remas well as division? That way the final bits of ISLE can all additionally be mapped into Rust/proptest as well. - Is it true that in all cases this expansion is better than whatever the hardware does?
- More of a curiosity, but how do egraphs know to favor these instruction sequences? This is expanding to quite a few more instrunctions than a div so do we have the cost of div/rem set really high?
I guess I'm becoming the resident instruction latency/throughput oracle today but yes definitely -- 64-bit integer divide has a latency of 35-88 cycles (!) on Skylake, with a throughput of 1/6 (so not fully pipelined), while 64-bit integer multiply is 3 cycles and is fully pipelined (1 per cycle). I vaguely recall some issue discussion from when we first switched over to the egraph mid-end where we noticed some benchmarks where this showed up as minor regressions, too. Very happy to see this finally ported over! |
Subscribe to Label Action
This issue or pull request has been labeled: "cranelift", "cranelift:meta", "isle"
Thus the following users have been cc'd because of the following labels:
To subscribe or unsubscribe from this label, edit the |
We don't put the values defined by side-effectful instructions into the egraph, so we have a slightly different path. This is why we use the ISLE Concretely, in this case there will be one RHS candidate (the new magic sequence), the one RHS is trivially the best RHS, and for |
Revive the old module for generating division-by-constant magic numbers
Add proptests for divide-by-constant magic number generators, just for a little extra correctness assurances
Apply division-by-constant magic sequences in the ISLE mid-end.
The application of these sequences have been ported to ISLE now to better integrate with our existing mid-end optimizations and to allow for recursive rule application in the optimized right-hand sides.
Fixes #6049