1067484 - IonMonkey: A pattern-matching framework for MIR nodes

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine: JIT, enhancement, P5)

Description

[Dan Gohman [:sunfish]]

Attachment: pattern-match.patch

While thinking about bug 1064374, I found myself (inevitably) wanting more expressive pattern-matching utilities for MIR nodes to go with it, both for use in that bug, and for use in foldsTo methods and elsewhere. At the same time, I don't want to build a completely new DSL, which is always a temptation in this space.

The attached patch implements a pattern-matching framework as a C++ library. As a quick example, here's what code to do a mul-add pattern-match might look like:

  using namespace patterns;
  MDefinition *x, *y, *z;
  if (match(ins, def<MAdd>(oneUse(def<MMul>(bind(x), bind(y)), bind(z))))) {
     // do a mul-add with x, y, and z
  }

It is inspired by LLVM's PatternMatch.h header, and the design is similar, but it's written from scratch and specialized for use with MIR nodes, and it has some different ideas about syntax sugar.

See also the top-level comment in MIRPatterns.h for more introduction. The patch also converts several foldsTo methods to use the framework, just to test it out a little.

I'm open to feedback and also opinions here, including "the metaprogramming is too complex" or "I don't like how the match syntax looks".

Comment 1

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8489475 [details] [diff] [review]
pattern-match.patch

Review of attachment 8489475 [details] [diff] [review]:
-----------------------------------------------------------------

As I am coming from a program transformation background, I really like having this kind of abstractions.

Still, I think there is a problem in the current implementation.  The problem is that every time we would be evaluating one of these expressions, we would be reconstructing the expression and initializing the classes with references before doing a match.  The reason of this issue is coming from the fact that the expressions are stateful, the bind expression should not hold a pointer.

By adding an extra argument to the match function, you can both remove the state hold by bind, and only pay the construction cost for the free variables.  This implies that bind no longer bind a variable, but a member in an environment class.

> typedef bind(_1) Pattern;
> static Pattern matchAny;
> Pattern::FreeVars env;
> if (matchAny(env, this)) {
>   …
> }

I agree that this would be more verbose, but extracting the environment from the Matching method would reduce the composition cost.  And this also allow to have more expression later where a variable can be scoped under an expression.

Also as you added any* I suggest that it might make sense to have functions named all*, see Modal logic [1].

[1] http://en.wikipedia.org/wiki/Modal_logic

::: js/src/jit/MIR.cpp
@@ +1842,5 @@
> +    if (match(this, def<MAdd>(bind(op), 0)))
> +        return op;
> +
> +    if (match(this, def<MAdd>(bind(other), def<MSub>(bind(op), other))))
> +        return op;

Note that this is not true, because of double precisions.

@@ +1845,5 @@
> +    if (match(this, def<MAdd>(bind(other), def<MSub>(bind(op), other))))
> +        return op;
> +
> +    if (match(this, def<MAdd>(bind(op), def<MNot>(op))))
> +        return MConstant::New(alloc, Int32Value(-1));

Nor this one unless we have a MAdd specialized to an int32.

Comment 2

[Dan Gohman [:sunfish]]

Attachment: pattern-match.patch

> Still, I think there is a problem in the current implementation.  The
> problem is that every time we would be evaluating one of these expressions,
> we would be reconstructing the expression and initializing the classes with
> references before doing a match.  The reason of this issue is coming from
> the fact that the expressions are stateful, the bind expression should not
> hold a pointer.
> 
> By adding an extra argument to the match function, you can both remove the
> state hold by bind, and only pay the construction cost for the free
> variables.  This implies that bind no longer bind a variable, but a member
> in an environment class.
> 
> > typedef bind(_1) Pattern;
> > static Pattern matchAny;
> > Pattern::FreeVars env;
> > if (matchAny(env, this)) {
> >   …
> > }
> 
> I agree that this would be more verbose, but extracting the environment from
> the Matching method would reduce the composition cost.  And this also allow
> to have more expression later where a variable can be scoped under an
> expression.

I agree that a clean separation between matching code and matching state has an appeal. However, the composition cost is low in the current patch. I'm comparing the generated assembly for a pattern match to the generated assembly I get hand-written matching code, and it's almost exactly the same. All the pattern-matching code gets inlined away, and the pattern objects get SROA'd, so in the end there's no actual composition happening at run time.

Also, verbosity is a significant concern here. Here's a sketch of what I imagine add-sub example could look like in a pure type API:

  typedef def<MAdd, bind<_0>, def<MSub, bind<_1>, _0>> matchAddSub;
  matchAddSub::FreeFars env;
  if (matchAddSub::match(this, env)) {
     do_stuff_with(env._0);
  }

Heres the same pattern in the API in the patch:

  MDefinition *x, *y;
  if (match(this, def<MAdd>(bind(x), def<MSub>(bind(y), x)))) {
     do_stuff_with(y);
  }

It's shorter, and the user-defined names (x, y) are things that the user cares about. The pure type API has user-defined names that the API cares about (matchAddSub, env), and fixed names for things the user cares about (_0, _1). I claim it's more readable.

> Also as you added any* I suggest that it might make sense to have functions
> named all*, see Modal logic [1].
> 
> [1] http://en.wikipedia.org/wiki/Modal_logic

The "any" functions mean "match a node with any opcode". What would "all" functions mean?

> ::: js/src/jit/MIR.cpp
> @@ +1842,5 @@
> > +    if (match(this, def<MAdd>(bind(op), 0)))
> > +        return op;
> > +
> > +    if (match(this, def<MAdd>(bind(other), def<MSub>(bind(op), other))))
> > +        return op;
> 
> Note that this is not true, because of double precisions.
> 
> @@ +1845,5 @@
> > +    if (match(this, def<MAdd>(bind(other), def<MSub>(bind(op), other))))
> > +        return op;
> > +
> > +    if (match(this, def<MAdd>(bind(op), def<MNot>(op))))
> > +        return MConstant::New(alloc, Int32Value(-1));
> 
> Nor this one unless we have a MAdd specialized to an int32.

Quite true. I had only been thinking of making an example for the API. I've now added specialization checks.

Comment 3

[Dan Gohman [:sunfish]]

Attachment: pattern-match.patch

Updated patch.

Comment 4

[Nicolas B. Pierron [:nbp]]

Should we continue on this track?

Comment 5

[Dan Gohman [:sunfish]]

I wouldn't object if someone wanted to pick this up and carry it forward, but it's not a priority for me right now.