Stream: git-wasmtime

Topic: wasmtime / issue #7313 egraphs: consider supporting recur...

Wasmtime GitHub notifications bot (Oct 20 2023 at 19:34):

cfallin opened issue #7313:

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.

Last updated: Nov 22 2024 at 16:03 UTC