bytecodealliance / bytecodealliance/wasmtime
egraphs: consider supporting recursive rematerialization
- 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
Assessment
This issue has not been assessed yet.