A Progress Report

Another week, another moment for reporting JIT compiler progress. I don't really have an interesting story to tell, so I'll keep it to a list of goals achieved.

I implemented a macro facility in the expression tree template builder, and changed the parser to use s-expressions throughout, making it much simpler.  I've used it to implement some opcode templates, learning much about what is required of the expression tree.

I've introduced a macro-based dynamic array implementation and refactored the JIT graph builder and expression tree builder to use it. This is necessary to allow the expression tree builder to use JIT graph labels. (For the record, the graph is the structure representing the whole routine or frame, and the expression tree represents a small part of interconnected expressions or statements. Expression tree is a misnomer for the data type I'm manipulating, because it is a DAG rather than a tree, and it holds statements rather than expressions. But the name is there, and I haven't really got a replacement ready).

I've implemented a 'generic' tree-walking mechanism on the expression tree, and designed some algorithms for it to help compiling, such as live-range calculations and common subexpression elimination (CSE). CSE is not just a useful optimization, but as a result of it, all sorts of useful information can be calculated, informing register allocation and/or spill decisions. Another useful optimization, and not a very difficult one, is constant folding.

I've added and changed and removed a bunch of expression tree node types and macro's. There are some interesting language-design details there; for instance that all and any can stand in for boolean or and and when these are used for binary computations, as is the case for machine code.

I've started writing a 'pseudocompiler', that is to say, a routine that logs the machine code statements that would be produced by the expression tree compiler to the JIT log, allowing me to inspect the logs to find bugs rather than deep down in GDB. Predictably, there were many bugs, most of which I think I've now fixed.

I've implemented the worlds most naive register allocator, based on a ring of usable registers and spilling to stack. This was more complex than I had assumed, so doing so was another learning experience. I noticed that without use information, there is no way to insert spills

I've also encountered some difficulties. The notion of a basic block - an uninterrupted sequence of operations - differs between the JIT compiler and spesh, because many MoarVM-level instructions are implemented as function calls. Function calls imply spills (because registers are not persisted between calls); but because the call may be conditional, there is potentially a path with and without spills; implying the load will be garbage. Or in other words, spills should precede conditionals, because conditionals break up the basic block. I think the SSA information from spesh could be useful here, but I have so far not figured out how to combine this information with the expression tree.

Some things (pure operations without side effects) can potentially be recalculated rather than spilled. Address calculations, which can be done inline (for the most part) in x64 instructions, are a prime example of this. (The current pseudocompiler computes these values into real registers, because the current pseudocompiler is dumb).

That is most of it, I guess. See you next week, when it's milestone time.

Reacties

Populaire posts van deze blog

Reverse Linear Scan Allocation is probably a good idea

Retrospective of the MoarVM JIT

Something about IR optimization