It's Finally Time to Write Some Optimizations (Almost)

Wherein I dash your hopes of spending the weekend hacking on making your favorite HLL compiler generate better code only to give you hope at the end that it will not be long at all before you can:

From the beginning, the ultimate goal of my project has been to be able to write optimizations and add them to PCT compilers. I checked in the ability to do actual working tree transformations with PAST::Transformer 2 or so weeks ago, but PAST::Transformer isn't much more pleasant than TGE(although now that NQP has multis, you can do it in NQP without the performance hit of PAST::Transformer::Dynamic, which is an advantage over PIR-only TGE).

PAST::Pattern is intended to be the way to conveniently write PAST optimizations. Transformer/Walker have always been intended as a more low-level interface: a tool with which to implement things like PAST::Pattern, and also a tool for writing the actual transformations once PAST::Pattern gives you the parts of the tree you want to modify. Soon, you will be able to write optimizations with PAST::Pattern. I was planning to have this done by today. In fact, I thought I had this done Wednesday. I'll explain why it isn't ready yet in a moment, but first, I'll describe what I have done. Earlier this week, I implemented global matching. You can call $aPattern.ACCEPTS($aTree, :g(1)), and the result will be a PAST::Pattern::Match object whose array part contains in sequential, depth-first order a match result for every matching subtree of $subTree.

Initially, I tried to implement it solely by modifying the PAST::Pattern::Node.ACCEPTS method I already had. It turned out to be extremely difficult to get it to work and understand what it was doing when I had it doing so many things: deciding whether or not to search globally, searching children for matches when the called node didn't match, collecting the list of matches for global matches, and wrapping the boolean result of the subclass .ACCEPTSEXACTLY() into a PAST::Pattern::Match object. So, after a late night of unsuccessful attempt after attempt to fix the many things my first implementation broke: I gave up and went to bed. In the morning, I refactored the code so that the individual subclasses built up their own match result object so that PAST::Pattern::Node.ACCEPTS could deal with only options, trying to recursively match children if the top node doesn't match, and collecting the result of global matches. The code was relatively effortless. It was easier to understand, less buggy, and easier to debug.

After that, I implemented a PAST::Transformer subclass called PAST::Pattern::Transformer as a helper for the PAST::Pattern.transform method, and used it to implement the .transform method. With that done, PAST::Pattern was essentially complete, I thought. All that remained was to write some optimizations using it and some documentation so that others could start doing so as well. So, I set out to implement a basic constant-folding optimization for Integer addition in NQP-rx. After some difficulty understanding the (as it turns out, quite simple) bootstrapping procedure and some brief attempts to find another PCT language suitable for testing the optimization(surprisingly few languages seem to actually use :pirop with integer values for integer addition), I got it building, but oddly, it was utterly breaking the resulting compiler. Anything at all would produce a syntax error in the comp_unit rule in the grammar.

Eventually I realized the cause: when I check the child and attribute sub-patterns, I call .ACCEPTS on them, which recurses into the children of the node if the node itself doesn't match the pattern. So "," would match any PAST::Op node whose first and second children both have a PAST::Val node anywhere in the tree below them! I spent most of tonight trying to fix this, but as with :g, it just isn't going to be done with simply adding more code paths to existing methods. I finally gave up on my attempts to fix it tonight half an hour ago. Tomorrow, I will heed the lesson global matching taught me and refactor the code in order to make fixing the bug easier. Once the bug is gone and I've written tests for the desired behavior, I will make sure that my example optimization for NQP-rx works and use it to start writing documentation so all of you can start writing optimizations of your own.

Watch for another blog post describing how to write optimizations with PAST::Pattern very soon(as soon as I have PAST::Pattern and my own first PAST optimization working).