Pattern matching

[dmlloyd]

The sequential BasicBlockBuilder chain implementation is useful for getting us off the ground, but to support serious mutually-recursive optimization with a reasonable time complexity, we're eventually going to need a proper pattern matching engine. Fortunately Java lends itself fairly well to such things.

It should be possible to write methods like this:

@Rule
public Value add(BasicBlockBuilder self, Add v1, Value v1v1, Literal v1v2, Literal v2) {
    return self.add(v1v1, self.add(v1v2, v2));
}

And have a tool that can look at that method (and others like it) and combine them into a single BasicBlockBuilder implementation whose add method will:

• examine its first parameter "v1" (using a ValueVisitor implementation), and if it is an Add...
• examine the add's second parameter "v1v2" (using a ValueVisitor implementation), and if it's a Literal...
• example the outer add's second parameter "v2" (using a ValueVisitor implementation), and if it's a Literal...
• generate a method call to the given method, providing...
• itself as the first parameter
• the outer add's first value, cast as an Add, as the second parameter
• the inner add's first value as the third parameter
• the inner add's second value, cast as a Literal, as the fourth parameter
• the outer add's second value, cast as a Literal, as the fifth parameter

Furthermore, it would recognize that Add is commutative, and so generate matches for all four equivalent permutations automatically. The information above should be extracted from method name and return type along with the the types, names, and possibly order of the method parameters. It could be done as an annotation processor during the build of QCC, so that the entire data structure is ready to go when QCC runs.

It should be possible to inject BasicBlockBuilders that delegate back to the current pattern matcher (self) or to the next block builder (next), allowing pattern matches to terminate or recurse.

In addition to matching the type of the node and its values, it should also be possible to match value.getType(), for example:

@Rule
public Value add(BasicBlockBuilder self, Value v1, FloatType v1Type, Value v2, SignedIntegerType v2Type) {
    // ...
}

This would match calls to add with a value whose type is a FloatType and another value whose type is a SignedIntegerType,again recognizing commutativity to generate both permutations, again using a visitor to match the types. Note that there is no visitor interface for types yet, but this will be necessary and should be introduced regardless.

By using visitors for double dispatch and generating nested levels during build as needed (effectively a DFA), each pattern can be matched in effectively constant time relative to the number of rules or linear time relative to the rule depth (which is typically extremely small), and a pattern can match arbitrarily deep constructs, limited only by the maximum number of arguments on a method.

This feature could be implemented as an annotation processor or as a Maven mojo. The plugin or mojo would find all classes within a module with rule methods and assemble them into one single rule set during the build of that module. Merging rules between modules is probably not feasible and is not necessary at any rate.

It may be worth exploring using the same engine to produce handlers for the copying and visiting stages. A visitor pattern matcher would greatly simplify lowering to LLVM, for example, eliminating if/else constructs.