Of Values


In the interest of the common interest in my little project, I think it's time for me to blog again. Today marks the end of the fifth week of my project period, since my project was planned to take 10 weeks, that means I'm now halfway. So what have I achieved, and what have I learned?

Well, I promised to deliver the following things:
  1. An implementation of the code generation algorithm described below, including instruction selection tables for the x64 architecture
  2. A runtime representation of machine operations ('expressions') that will form the input to the code generator and is suitable for targeting to different architectures
  3. A patched version of DynASM capable of addressing the extended registers of x64
  4. Conversion of large parts of the current JIT to the new algorithm
  5. An extension API for REPR ops to insert (inline) expressions into the JIT in place of some operations
  6. A set of automated tests known to trigger JIT compilation to either the NQP or Rakudo Perl 6 test suite.
  7. Reports and documentation explaining the JIT and it's API
I have delivered 2, and 3, and the main reason I haven't done 4 yet is that 1 is not completely done. (The consequence of converting everything to the expression tree format would be that testing the soundness of compilation algorithms would become much more difficult). I have delivered tooling (i.e. a preprocessor) to elegantly and efficiently transform MoarVM bytecode segments to the expression tree format.

I think my almost-weekly blog reports do something for 7, but real documentation is still lacking. In the case of 6 (the test suite), it turns out that practically any NQP program - including bootstrapping NQP itself - already exercises the JIT quite a bit, including the new expression tree pseudocompiler. Thus, during development it has not yet been necessary to develop an explicit test suite, but I expect it will become more useful when the core compiler has stabilized. So in short, although I am not quite near the finish line, I think I am well underway to delivering a usable and useful compiler.

What have I learned that I think will help me go forward?
  1. A lot of things that look like simple expressions in MoarVM are quite complex underneath. Some things include conditional evaluation, some include evaluation lists. Many things have common subexpressions. Many other things are really statements.
  2. A MoarVM basic block is a much larger unit than a machine basic block, and the former may include many of the latter. A basic block in the expression tree is also quite conceptually difficult, given that
  3. Lazy evaluation is not compatible with single evaluation in case of conditional evaluation.
  4. The issues of evaluation order, value management, register management and instruction selection are distinct but closely related. Each greatly influences the order. For instance,
    1. A register can hold multiple values (values can be aliased to the same register).
    2. Values may be classified as intermediaries (single use not representing a final variable), temporaries (multiple uses not representing a final variable) and locals (that do represent a final variable).
    3. Value uniqueness falls directly out of the expression tree format.
    4. Instruction selection influences the amount of registers required and should precede register management.
    5. Register selection benefits from a consistent way to get a 'free register', and either a heap or a stack are decent ways to provide this; more importantly, it benefits from a way to efficiently subset the register set.
  5. It's nearly impossible to compile decent code using only a single pass traversal, because you don't know where values will end up, and to which of the 3 classes above it belongs.
  6. The expression tree is really a Directed Acyclic Graph, and traversal and compilation can be significantly more complex for a DAG than they are for a tree.
Accordingly, I've spent most of my last week learning these things, in various degrees of hard and easy ways to learn them. This is why, as far as features are concerned, I don't have so much news to report this week. I hope next week I'll have more exciting news to report. See you then!

Reacties

Populaire posts van deze blog

Reverse Linear Scan Allocation is probably a good idea

Retrospective of the MoarVM JIT

Something about IR optimization