Stream: git-wasmtime

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

Wasmtime GitHub notifications bot (May 14 2020 at 17:44):

fitzgen opened 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.

Wasmtime GitHub notifications bot (May 14 2020 at 17:44):

fitzgen labeled 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.

Wasmtime GitHub notifications bot (May 14 2020 at 17:44):

github-actions[bot] commented on Issue #1707:

Subscribe to Label Action

cc @fitzgen

<details>
This issue or pull request has been labeled: "cranelift:area:peepmatic"

Thus the following users have been cc'd because of the following labels:

• fitzgen: cranelift:area:peepmatic

To subscribe or unsubscribe from this label, edit the <code>.github/subscribe-to-label.json</code> configuration file.

Learn more.
</details>

Last updated: Nov 22 2024 at 16:03 UTC