bytecodealliance / bytecodealliance/wasmtime
Optimize Cranelift instruction groups that lower to the same machine instruction
- Dominant language
- Rust
- Stars
- 18.6k
- Forks
- 1.8k
- Avg merge
- 1d 14h
- Merged PRs (30d)
- 135
Description
#### Feature
On some backends, different Cranelift instructions may lower to the same machine instruction, producing multiple results at once.
For example, if a function evaluates both `udiv v0, v1` and `urem v0, v1`, then on x86 both results are produced with the same `div` instruction.
Currently, Cranelift emits the same `div` instruction twice in that case (see #5573) but we'd like to deduplicate this.
I believe the same optimization is relevant for `imul`/`umulhi`, `imul`/`smulhi`, and probably other pairs of instructions.
#### Benefit
Fewer instructions retired to compute the same result. Also, since these x86 instructions use the same fixed registers for input and output, evaluating the same instruction back to back requires a bunch of register moves, so deduplicating the instructions relieves local register pressure. On the other hand, merging these ops may increase the length of live ranges, so it may increase global register pressure.
#### Implementation
@cfallin suggests introducing a mid-end egraph optimization, but only for backends which benefit from it. We'd introduce Cranelift instructions such as `udivrem` representing the combined operation with multiple results. We'd then have egraph rules indicating that `udiv` can be replaced by the first result of `udivrem`, but at the same time that the second result of `udivrem` can be replaced by `urem`. (And also _vice versa_.)
That way, if we encounter a `udiv`, then we'll add the corresponding `urem` as an available expression; if we later encounter an equivalent `urem`, we'll find that it's already available and de-duplicate it.
#### Alternatives
We could try to deduplicate machine instructions after lowering but before register allocation.
Contributor guide
Research direction
Start by reading the existing duplicate-lowering behavior described in #5573, then examine Cranelift's egraph optimization and instruction-lowering paths. Define combined operations such as udivrem and the rules connecting their results to udiv and urem, limiting the optimization to backends that benefit. Done means equivalent instruction groups lower to one machine instruction without regressing other backends.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100