bytecodealliance / bytecodealliance/wasmtime

Optimize Cranelift instruction groups that lower to the same machine instruction

Open
#5,623 3 comments 0 reactions 0 assignees View on GitHub
cranelift cranelift:goal:optimize-speed cranelift:mid-end
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.