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!