Stream: git-wasmtime

Topic: wasmtime / issue #5699 ISLE: don't check identical patter...

Wasmtime GitHub notifications bot (Feb 02 2023 at 23:56):

jameysharp opened issue #5699:

Feature

If ISLE sees a pattern like (rule (simplify foo (bar x) (bar x))), after checking the first (bar x) condition it should check whether the second argument to foo is equal to the first argument. If so, then we know (bar x) will match on the second argument as well, and don't need to check it again. If they arguments are not equal, we should go ahead and check the subpattern like we do today.

Benefit

These kinds of patterns show up in mid-end optimization rules. During those rules we've already done GVN, so if the pattern matches both values, then the values will be the same. As a result, this proposed optimization should fire a lot.

Implementation

I haven't thought that hard about this yet.

Wasmtime GitHub notifications bot (Feb 02 2023 at 23:56):

jameysharp edited issue #5699:

Feature

If ISLE sees a pattern like (rule (simplify foo (bar x) (bar x))), after checking the first (bar x) condition it should check whether the second argument to foo is equal to the first argument. If so, then we know (bar x) will match on the second argument as well, and don't need to check it again. If the arguments are not equal, we should go ahead and check the subpattern like we do today.

Benefit

These kinds of patterns show up in mid-end optimization rules. During those rules we've already done GVN, so if the pattern matches both values, then the values will be the same. As a result, this proposed optimization should fire a lot.

Implementation

I haven't thought that hard about this yet.

Wasmtime GitHub notifications bot (Feb 02 2023 at 23:59):

jameysharp edited issue #5699:

Feature

If ISLE sees a pattern like (rule (simplify foo (bar x) (bar x))), after checking the first (bar x) condition it should check whether the second argument to foo is equal to the first argument. If so, then we know (bar x) will match on the second argument as well, and don't need to check it again. If the arguments are not equal, we should go ahead and check the subpattern like we do today.

Benefit

These kinds of patterns show up in mid-end optimization rules. During those rules we've already done GVN, so if the pattern matches both values, then the values will be the same. As a result, this proposed optimization should fire a lot.

Implementation

I haven't thought that hard about this yet.

This partially undoes a transformation that trie_again does, except that we have to fall back to checking each subpattern in some cases. Looking at that transformation might provide some inspiration.

Wasmtime GitHub notifications bot (Feb 03 2023 at 02:41):

jameysharp commented on issue #5699:

After discussion with @elliottt, I can see I didn't say this very clearly.

In ISLE pattern matching, every pattern is "pure" in the functional programming sense. In particular, a==b always implies that f(a)==f(b). So if we've computed f(a) and we check that a==b, we can skip computing f(b) and reuse the result of f(a) instead.

The reverse isn't true in general though: a!=b does _not_ generally imply that f(a)!=f(b). So if the check that a==b turns out to be false, we still have to go ahead and compute f(b).

We have some extractors and some situations where a==b if _and only if_ f(a)==f(b). In particular, as long as we've done GVN, this holds for any instruction extractor. It might be interesting to tell ISLE which extractors have this property. That's more complicated to get right than what I'm proposing here, though.

This proposal is just: If we use the same extractor multiple times in a rule, we may be able to avoid actually calling it more than once in common cases by short-circuiting when we're calling it with arguments which are dynamically the same.

Wasmtime GitHub notifications bot (Mar 31 2023 at 00:47):

jameysharp labeled issue #5699:

Feature

If ISLE sees a pattern like (rule (simplify foo (bar x) (bar x))), after checking the first (bar x) condition it should check whether the second argument to foo is equal to the first argument. If so, then we know (bar x) will match on the second argument as well, and don't need to check it again. If the arguments are not equal, we should go ahead and check the subpattern like we do today.

Benefit

These kinds of patterns show up in mid-end optimization rules. During those rules we've already done GVN, so if the pattern matches both values, then the values will be the same. As a result, this proposed optimization should fire a lot.

Implementation

I haven't thought that hard about this yet.

This partially undoes a transformation that trie_again does, except that we have to fall back to checking each subpattern in some cases. Looking at that transformation might provide some inspiration.

Last updated: Oct 23 2024 at 20:03 UTC