bytecodealliance / bytecodealliance/wasmtime

egraphs: consider supporting recursive rematerialization

Open
#7,313 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
18.6k
Forks
1.8k
Avg merge
1d 18h
Merged PRs (30d)
126

Description

After #7306, we have a rematerialization mechanism that can remat a single operator into the block where it's used. To solve another decision-ordering issue w.r.t. LICM, remat was moved very late: just before using args. As a result, it no longer participates in the main elaboration pass and so we don't automatically get "recursive" remat. This might occur in cases where we have, e.g.:

```
block0(...):
v10 = iconst.i32 42
v11 = iadd.i32 v1, v10

blockN(...):
store v11, ...
```

if we had marked both `v10` and `v11` as rematerializable. The old mechanism would move both into `blockN`, but the new mechanism moves only `iadd`.

This is solvable if we add a new recursion site, but in the egraphs code we've been careful to avoid any native recursion, using an explicit stack and open-coded state machine instead. The only reason we haven't done that for this issue is complexity.

The current situation (post-#7306) is possibly OK for a while: we remat constants, and adds-with-one-constant-arg; the latter will fold small (common) constants into the instruction on most architectures. If it ever becomes an issue, though, we could add the recursion and solve this issue in the general way.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.