ISLE: don't check identical patterns on identical inputs

[jameysharp]

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.

[jameysharp]

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.