A first optimization with PAST::Pattern, in detail

In my previous post, I described in tutorial form how to implement a very simple constant folding optimization for Integer addition. In this very brief post, I describe in greater detail how that optimization works.

In my next post, I will describe how to extend this optimization to be more general. These posts have a tutorial and example focus. If you want to know every detail of the PAST::Pattern API, the documentation in the gsoc_past_optimization branch of the Parrot subversion repository in the docs/pct/pattern/ directory is what you need.

Here are the contents of the file src/NQP/Optimizer.pm in the example code repository as of the end of the previous post:

INIT {
    pir::load_bytecode('PAST/Pattern.pbc');
}

module NQP::Compiler {
    method constantfold ($past) {
        my &foldable := sub ($opName) {
            $opName eq "add";
        }
        my &integral := sub ($val) {
            pir::isa__iPP($val, Integer);
        }
        my $pattern := 
          PAST::Pattern::Op.new(:pirop(&foldable),
                                PAST::Pattern::Val.new(:value(&integral)),
                                PAST::Pattern::Val.new(:value(&integral)));
        my &fold := sub ($/) {
            my $value := $/[0]<value>.from() + $/[1]<value>.from();
            PAST::Val.new(:value($value));
        };
        say("Constant fold pass running.");

        $pattern.transform($past, &fold);
    }
}

I'll dissect this line by line(or more accurately: meaningful chunk by meaningful chunk).

INIT {
    pir::load_bytecode('PAST/Pattern.pbc');
}

This INIT block loads the PBC "PAST/Pattern.pbc", which contains the PAST::Pattern classes and related code. In addition to defining PAST::Pattern, its subclasses, and PAST:Pattern::Transformer(a helper class for the transform method), it adds match and subst methods to PAST::Node that call ACCEPTS and transform methods, respectively, of a supplied pattern, paralleling the Str methods for regex matching and substitution in Perl 6. This is what you must load to access the PAST::Pattern library.

module NQP::Compiler {

This module declaration specifies that all of the code contained in the following block belongs in the NQP::Compiler namespace. If you were optimizating a different compiler, you would replace with NQP::Compiler with the name of the compiler class of your compiler.

method constantfold ($past) {

This marks the beginning of the declaration of a method named constantfold in the NQP::Compiler namespace. In our Compiler.pir file, the constantfold stage is added to the compiler object after the past stage. This means that after the past stage is run, the constantfold method of the compiler will be called with the resulting PAST.

my &foldable := sub ($opName) {
    $opName eq "add";
}

This declares a local variable &foldable containing a subroutine that we will use to determine whether the op is of the right type to fold. It simply performs a string comparison to "add". Using a subroutine is unnecessarily complex for this simple case, but it can be simply extended to other opcodes. All we'd have to do to make it match "sub" ops, as well as "add" ops, is to add || $opName eq "sub".

my &integral := sub ($val) {
    pir::isa__iPP($val, Integer);
}

This defines another local subroutine variable &integral that we will use to check that the value attributes of the op's children are integers. It uses the pir:: syntax to use the isa opcode on $val and the Integer class. The __iPP part tells the NQP-rx compiler that we want the version of the isa opcode that has an integer as its first parameter(which, in this case, is the result) and PMCs as its second and third parameters.

my $pattern := 
    PAST::Pattern::Op.new(:pirop(&foldable),
                          PAST::Pattern::Val.new(:value(&integral)),
                          PAST::Pattern::Val.new(:value(&integral)));

Now we use the &foldable and &integral subroutines and the PAST::Pattern::Op and PAST::Pattern::Val classes to create a pattern specifying which nodes we should transform. The PAST::Pattern::Op, PAST::Pattern::Val, etc. classes match PAST::Nodes based on their type. There is one for each standard PAST::Node subclass. They can also have sub-patterns to match the children or attributes of the node. If the node has the wrong number of children or lacks an attribute that the pattern has, the match will fail. If any of the sub-patterns does not match the corresponding attribute or child of the node, the match will also fail.

As the PAST::Pattern::Val children of $pattern demonstrate, the sub-patterns can be other PAST::Patterns. This example doesn't use this, but they can also be other objects with a ACCEPTS method, include NQP-rx regexes. As the value and pirop attributes demonstrate, they can also be predicate subroutines. Any object that provide the invokable role will be treated as a predicate subroutine. Any other value will be treated as a constant which matches any object which is_equal to the constant. Instead of the subroutine &foldable, we could have simply used the constant "add", as shown here.

my &fold := sub ($/) {
    my $value := $/[0]<value>.from() + $/[1]<value>.from();
    PAST::Val.new(:value($value));
};

This defines another local subroutine variable named &fold that we'll use to perform the actual transformation. It will be called with each successful match result and should return the node with which to replace the matched node. We use array indexing on the match result($/[0]) to get the match result of the first and second children sub-patterns and hash indexing($/[0]<value>) to get the match results of the "value" sub-patterns of those children. To access the node or other object that matched a pattern, we use the .from() method of a match result.

This subroutine adds the value attributes of the two PAST::Val children and returns a new PAST::Val with that sum as the value, which will replace the original PAST::Op node in the optimized PAST.

After outputting a message for diagnostic purposes, we reach the final line of our optimization pass:

$pattern.transform($past, &fold);

This calls the transform method of the pattern with the PAST and &fold as arguments. This recursively traverses $past, calling &fold on any nodes that match the pattern and replacing them with the result.

In the next few days, expect both an update to the PAST::Pattern library to add PAST::Pattern::any and PAST::Pattern::all subroutines to create patterns specifying that any or all of their sub-patterns must match a node for the pattern as a whole to match and another tutorial demonstrating how we can use this to conveniently expand the functionality of our optimization pass. Until then, happy hacking!