Stream: git-wasmtime

Topic: wasmtime / issue #1707 Investigate ways to de-duplicate e...

Wasmtime GitHub notifications bot (Nov 19 2021 at 18:26):

fitzgen commented on issue #1707:

Peepmatic was removed in https://github.com/bytecodealliance/wasmtime/pull/3543

Wasmtime GitHub notifications bot (Nov 19 2021 at 18:26):

fitzgen closed issue #1707:

Right now, if there are two subtrees of LHS match ops that are the same, except they check different paths (e.g. checking if a first operand is the result of an iadd and checking if a second operand is the result of an iadd) we create different states because each state is associated with a MatchOp and a MatchOp embeds the path of the thing it is operating on within itself.

We should investigate ways to de-duplicate these states and match operations.

One idea is to implicitly maintain a stack of what the current instruction we're operating against is, and expand our generated automata to be pushdown automata. It is unclear to me how to expand our existing algorithm for transducer automata construction to add pushdown support. I don't know whether there is anything in the literature describing how to do this or not.

Another idea is to add MatchOp opcodes that don't actually do any matching, but just do traversal-through-the-data-flow-graph operations. Things like push and pop operations, or register-assignment operations. The downside here is that we have more operations to process, and it isn't clear that the size of the automata will actually get smaller, even if we can de-duplicate more than we did before, because there would be so many more extra operations.

Last updated: Nov 22 2024 at 16:03 UTC