tcurtis's blog

Seven days of PIRATE and Tree::Pattern hacking

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

Generalization: Tree::Pattern, Tree::Transformer, and Tree::Walker

Earlier this summer, when I was considering what sort of interface would be best for the PAST pattern matching and transformation I've been building, Bacek suggested an XPath-like syntax. XPath is, nominally, a language for pattern matching on XML, but it is applicable to any tree-like data structure where each node may have both attributes and children. It's a general-purpose tree-matching language.

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.

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.

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:

The Last Week and a Half in PAST Optimization

I noticed yesterday that I forgot to post a blog post last week. I'll try to make up for that with double the blog post goodness this week(expect a second post Thursday or Friday).

PAST::Transformer and the Foundation for PAST Optimization

Coding for GSoC officially began this Monday, but I decided to get a head start and started working on PAST::Walker Thursday. PAST::Walker is the foundation for the rest of what I will be doing regarding PAST Optimization, and the foundation is largely laid. There have been a few complications, and a few decisions remain to be made(and implemented) before I can say that PAST::Walker and PAST::Transformer are finished, but implementing PAST::Walker has gone smoothly and quickly for the most part.

PAST Pattern Matching

Last Wednesday, I discussed a little bit of the rationale behind my GSoC project and summarized the most low-level portion of my project: PAST::Walker. Today, I want to describe another portion of my project: PAST::Pattern. PAST::Walker provides a very powerful and complete interface. Any possible transformation or other traversal of a PAST should be implementable using it. However, it will not be very convenient if you only want to turn return nodes containing only a call node into tail-call nodes.

PAST Optimization

One of the advantages of a common virtual machine for various languages is the ability to apply the same optimizations to all of those languages. For example, LLVM includes optimization passes to propagate constants, eliminate dead arguments, code, and globals, inline functions, and eliminate recursive tail calls, among others. Any language with a compiler to LLVM can easily take advantage of these optimizations without any additional work by the compiler writer.

Syndicate content