Seven days of PIRATE and Tree::Pattern hacking

Last week, I generalized PAST::Pattern to Tree::Pattern. This week, I put that to use.

I've spent much of the week working on optimizations for bacek's PIR compiler PIRATE. Not only does PIRATE not use PAST, it doesn't even use the standard PCT version of POST. Instead, it uses its own special variant of POST that is less string-focused. First, I had to create new POST::Pattern subclasses for the new POST::Node subclasses PIRATE uses. This would have been very unpleasant and repetitive before the refactoring of Tree::Pattern I did last week. Now it was only a little repetitive and fairly concise.

I implemented constant folding for all of the core arithmetic ops that IMCC folds(except for div and fdiv when the second input is 0). I also implemented constant folding for most of the conditional ops. If and unless are still not folded(simply because I didn't think about them at the time). This isn't really a case of optimization so much as making the code work, since the ops I'm optimizing away for PIRATE don't actually exist. If PIRATE's PBC-generation phase sees an add_i_ic_ic add, it won't know what do with it because it doesn't exist.

Moritz++ has continued to work on trying out optimizations for Rakudo. He's been a wonderful source of feedback and bug reports.

Here's a quick summary of the changes I've made in the last week as a result of Moritz's feedback:

  • Changed the .from attribute of Tree::Pattern::Match to .orig to more closely parallel regexes.
  • Added a :min_depth option to .transform that causes it to ignore the first n levels of the tree.
  • Added a :descend_until option to .transform that allows you to specify a pattern such that the transformation will not attempt to transform any descendants of any node that matches the limit pattern.
  • Made the last two work together so that you can transform any nodes within a PAST::Block that aren't within a child PAST::Block, for example.
  • Fixed Tree::Pattern::Patternize to work correctly, even if the can op says that Subs have an "ACCEPTS" method, but the "ACCEPTS" method doesn't actually work. This was probably due to even the NQP-rx parts of Rakudo being in the "perl6" HLL.

I also worked on documentation, largely thanks to cotto++'s urging, and wrote some more tests. The documentation for my project now lives in docs/user/library in the gsoc_past_optimizations branch.

In the coming week, I plan to finish up with the constant-folding for PIRATE and implement some simple other optimizations for both PIRATE and NQP-rx.

I'll also be implementing a new feature allowing transformations to return multiple nodes to replace the one. This will allow some more optimizations, especially at the POST level.

Other items on my to-do list, though not necessarily for this week, include new patterns for sequences of events in nodes like PAST::Stmts, PAST::Block, POST::Sub, etc. This would be very helpful for small-scale optimizations, but I'm still uncertain about how best to implement them. Another item on my to-do-eventually list is an analysis using PAST::Pattern that looks through a PAST for global variables and functions that are used to detect at least some of the modules and specific functions within them that it depends on. It would certainly be far from perfect, but it might be useful for some things, and it would serve as an excellent experiment in larger-scale pattern matching.

That's all for now. Happy hacking!