Adding Optimizations to HLL Compilers with PAST::Pattern

Parrot Abstract Syntax Trees(PASTs) are one of the forms code being compiled in a PCT-based compiler takes before being evaluated or compiled to bytecode. With PAST::Pattern, you can find all the sub-trees of a PAST that match a certain pattern and transform them. This can be used to perform optimizations at the PAST level.

In this post, I'll describe how you can now start writing and testing optimizations using it. This post is just an overview and tutorial, though. For more detailed documentation(that is only partially written currently), see the docs/pct/pattern/. You can follow along with the tutorial with the example code repository beginning with this commit.

We need the gsoc_past_optimization branch of Parrot's Subversion repository. You can get it with the command svn co https://svn.parrot.org/parrot/branches/gsoc_past_optimization past_optimization_parrot, which will download the source code to the "past_optimization_parrot" directory. Build it and install it somewhere with perl Configure.pl --prefix=$PASTOPTPARROT && make && make install-dev, replacing $PASTOPTPARROT with the prefix under which you want to install it. When we build NQP, we'll supply its Configure.pl script with the location of the parrot_config executable for this installation(which should be --parrot-config =$PASTOPTPARROT/bin/parrot_config).

We also need to get the source code of the HLL compiler we're going to be testing our optimizations with and update the build process to include our optimizations. This tutorial will use NQP-rx, but that won't help you if your optimization is tuned specifically towards optimizing another HLL, so I'll also explain how to do this generally. If you're testing your optimization with NQP-rx, you can either follow the more general instructions or clone this git repository . To do this, install git and issue the command git clone git://github.com/ekiru/nqp-rx.git from your terminal.

Updating the build process to include our optimizations is a little more work for other HLLs or if you don't want to clone my NQP-rx repository. As shown here I added an NQP file containing my optimizations and used ".include" in NQP's Compiler.pir to include the generated PIR. I also modified the build process to build my optimization file before building Compiler.pir. Another option is to "load_bytecode" the bytecode of the optimizations instead of including the PIR. This also works if your compiler has a "Compiler.pm" file instead of "Compiler.pir". You could also simply include your optimization methods in the Compiler.pir or Compiler.pm file, but separating the optimizations from the compiler itself can improve both readability and the ease with which you can migrate your optimization from one compiler to another.

Now that we have our compiler and its build process is ready for our optimizations, it's time to start writing our optimizations. PAST optimizations are compiler stages that need to be ran sometime between the "past" and "post" stages. Like all PCT compiler stages, they are implemented by methods on the compiler object.

First, let's add an empty method to our compiler object and verify that our stage is getting ran. I'll include example source code in NQP for the rest of this article. If you're using a compiler other than NQP, replace any references to NQP::Compiler with Perl6::Compiler or Partcl::Compiler or whatever the relevant compiler class is.

If you're not using my NQP-rx repository, then you'll need to start by creating a skeleton file for your optimizations. You need to load 'PAST/Pattern.pbc' for PAST::Pattern and specify that you're in the NQP::Compiler namespace.

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

module NQP::Compiler {

}

We're going to be implementing a constant folding optimization, but first, let's set up our optimization stage and make sure it's being ran. Our optimization will be implemented as a method in the NQP::Compiler namespace called "constantfold". It will take a PAST as its argument and return another PAST. But, for now, it's simply going to output "Constant fold pass running." and return the supplied PAST so that we know we're running it properly.

So, let's add to Optimizer.pm the following:

Place this inside the module NQP::Compiler { } block:

method constantfold ($past) {
    say("Constant fold pass running.");
    $past;
}

Now, add in Compiler.pir at the end of the .sub '' :anon :load :init subroutine the following:
nqpproto.'addstage'('constantfold', 'after'=>'past')

Now, let's build it and make sure that everything works properly. If you haven't already, run perl Configure.pl --parrot-config=the path to your parrot_config. Now use make to build NQP. You should see Constant fold pass running. when the stage2 files are being compiled. Finally, run make test to verify that we haven't managed to break NQP.

Congratulations! You have an optimization that does nothing! Now let's make it work.

As a start, let's just constant fold something very simple: Integer addition. An addition is usually represented in PASTs with a PAST::Op node with the pirop attribute set to "add". If it's an addition of two constant integers, then the PAST::Op node will have two PAST::Val children whose value attributes are Integer constants.

First, we need to add the following at the beginning of the constantfold method in Optimizer.pm:

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


This will ensure that the pirop attribute of the PAST::Op node is "add". Later, we'll expand this and the rest of the optimization to work on more than just addition.

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


This will check that the value attributes of the PAST::Val nodes are actually integer constants.

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


This is our pattern. It matches any PAST::Op node whose pirop attribute satisfies &foldable with two child PAST::Val nodes whose value attributes satisfy &integral.

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


We'll use this subroutine to transform any parts of our tree that match the pattern. It receives a PAST::Pattern::Match object whose .from attribute is the matching node. In addition, the child pattern match results are in the children of the match object and can be accessed by treating it as an array. Similarly, the attribute pattern match results can be accessed with $/<pirop>, for example, or with the shorthand $<pirop>. The value attributes of the matched node's children are added together and used to create a new PAST::Val node which replaces the original PAST::Op node.

Finally, we'll replace the $past; line in constantfold with $pattern.transform($past, fold);. The transform method on PAST::Pattern takes a PAST and a subroutine and calls the subroutine on any parts of the PAST that match the pattern, replacing them with the result of the sub.

Build NQP and run the test suite again. All tests successful. Clearly, our little optimization hasn't broken NQP, but is it optimizing?

Let's create a test program add.nqp to see. Save the following as add.nqp
say(1+2);

We'll use the --target= option to nqp to test our optimizations. First, we'll see the PAST version of our test program:

$ ./nqp --target=past add.nqp

Constant fold pass running.
"past" => PMC 'PAST;Block'  {
    <pos> => 0
    <source> => "say(1+2);\n"
    [0] => PMC 'PAST;Stmts' 
    [1] => PMC 'PAST;Op'  {
        <inline> => ResizablePMCArray (size:6) [
            "    $P0 = find_dynamic_lex \"$*CTXSAVE\"",
            "    if null $P0 goto ctxsave_done",
            "    $I0 = can $P0, \"ctxsave\"",
            "    unless $I0 goto ctxsave_done",
            "    $P0.\"ctxsave\"()",
            "  ctxsave_done:"
        ]
    }
    [2] => PMC 'PAST;Op'  {
        <pirop> => "return"
        [0] => PMC 'PAST;Stmts'  {
            <pos> => 0
            <source> => \past
            [0] => PMC 'PAST;Op'  {
                <name> => "say"
                <pasttype> => "call"
                <pos> => 4
                <source> => \past
                [0] => PMC 'PAST;Op'  {
                    <name> => "&infix:<+>"
                    <pirop> => "add"
                    <pos> => 5
                    <source> => \past
                    [0] => PMC 'PAST;Val'  {
                        <value> => 1
                    }
                    [1] => PMC 'PAST;Val'  {
                        <value> => 2
                    }
                }
            }
        }
    }
    [3] => PMC 'PAST;Block'  {
        <lexical> => 0
        <namespace> => ""
        <pirflags> => ":load"
        [0] => PMC 'PAST;Op'  {
            <pasttype> => "call"
            [0] => PMC 'PAST;Val'  {
                <value> => \past
            }
        }
    }
}


$ ./nqp --target=constantfold add.nqp

Constant fold pass running.
"constantfold" => PMC 'PAST;Block'  {
    <pos> => 0
    <source> => "say(1+2);\n"
    [0] => PMC 'PAST;Stmts' 
    [1] => PMC 'PAST;Op'  {
        <inline> => ResizablePMCArray (size:6) [
            "    $P0 = find_dynamic_lex \"$*CTXSAVE\"",
            "    if null $P0 goto ctxsave_done",
            "    $I0 = can $P0, \"ctxsave\"",
            "    unless $I0 goto ctxsave_done",
            "    $P0.\"ctxsave\"()",
            "  ctxsave_done:"
        ]
    }
    [2] => PMC 'PAST;Op'  {
        <pirop> => "return"
        [0] => PMC 'PAST;Stmts'  {
            <pos> => 0
            <source> => \constantfold
            [0] => PMC 'PAST;Op'  {
                <name> => "say"
                <pasttype> => "call"
                <pos> => 4
                <source> => \constantfold
                <b>[0] => PMC 'PAST;Val'  {
                    <value> => 3
                }</b>
            }
        }
    }
    [3] => PMC 'PAST;Block'  {
        <lexical> => 0
        <namespace> => ""
        <pirflags> => ":load"
        [0] => PMC 'PAST;Op'  {
            <pasttype> => "call"
            [0] => PMC 'PAST;Val'  {
                <value> => \constantfold
            }
        }
    }
}

As the bolded section demonstrates, our pass is successfully turning 1+2 into 3.

That's a start to optimizing PASTs using PAST::Pattern. In my next post, I'll show how to extend it to more operations.

For more details about PAST::Pattern, see the documentation in docs/pct/pattern/.

If you have any questions, feedback, etc., feel free to contact me in the comments, on parrot-dev, by email, or on #parrot.