zondag 16 augustus 2015

Tiler Update

In my last blog I talked a bit about a problem I had with generating all possible sets of rules from the tile 'grammar'. I've since solved that problem, and thought it'd be nice to share my results. (NB: I use the word 'grammar' loosely today and on other days. In compiler jargon a grammar is usually a thing that matches a linear stream of lexical tokens to a tree structure. In this case, it's really the other way around, because it's used to match a tree and output a linear sequence. However, these things are quite similar, so I hope you'll forgive me for using the term).

It may help if I state the problem as clearly as I can. The input is a list of rules mapping a head and up to two child nodes to a tile and a nonterminal symbol. A tile, to reiterate, is ultimately a piece of code that emits machine code. The nonterminal symbol (from now on: symbol) is what takes the place of a node after a tile has been selected for it. This abstraction is what allows the tiler to determine the rule(set) for a node by looking only at it's direct children.  Note that tile rules that refer to nested structures are 'flattened' by replacing nested children by special one-off symbols.

Many rules can be matched together. Take for instance these tiles starting with an add node. For x64, we can compile a register-to-register addition, a constant-to-register addition, and a memory-to-register addition. (x86 can also add from register to memory, but we ignore that).

Rule 1: Adding register to register

Rule 2: A tile that adds a constant value to a register

Rule 3: A tile that adds a register to a value loaded from memory

Given that both a (load mem) and a (const) node can be tiled to reg symbols, we can always match (add reg reg) when matching an add node. But it's not always possible to match (add reg (const)) or (add reg (load mem)). And the last two certainly cannot be combined. So when the tiler inspects the add node, it can emit the following tree combinations of tiles: {1}, {1,2} and {1,3}. The problem I had was given the complete set of rules, how can we find all permissible combinations that the tiler can generate?

(As an aside, I don't think generating only the necessary rulesets is an optimization, but very much necessary for the feasibility of the tiler. The tiler tables otherwise become either prohibitively large, or incomplete).

Why can we combine 1 and 3? Because the (load mem) node can generate a reg symbol as well as the 'placeholder' symbol generated in rule 3 (let's call that the 3a symbol). Similarly, the (const) node can generate a reg as well as the 2a symbol. Indeed, rules can be combined whenever the symbols they refer to can be combined. And they are separate whenever the symbols they refer to can occur separately. So the key to finding all permissible combinations is finding all possible combinations of symbols. That is something of a simpler problem.

First of all, all rules that refer to the same combination-of-terminals can be combined themselves, generating new combinations of terminals. Second, some terminal combinations may not be generated at all (3a will never occur in isolation, for example). Finally, when we do have all possible sets of terminals, applying all rules to each set will continue to generate these combinations. We can find rules which combine in such a way easily using a trie. So the solution to finding all permissible combinations of rules is this:
  1. Apply each rule to a trie of symbol combinations and store the rule number and symbol in each leaf.
  2. Extract all combinations of symbols that resolve to a single trie leaf.
  3. Compare the symbol combinations to those used in step 1. If there are any changes, repeat from step 1.
  4. The trie leafs also now also contain all possible rule combination, which simply need to be given a number.
The idea for this algorithm I derived from the table generation algorithm for parser generators, to which it is also quite similar.

A further change I had to make was to split the finding of rulesets - a bottom-up procedure - to the selection of the right rules, which is a top-down procedure. It is top-down, because the rule selected at a node determines the rules that can be applied for it's child nodes. All that is needed is a table that stores the minimum-cost rule to generate a given symbol for a given tile set, and a root rule to start with. (NB: I'm not 100% sure that's true, but it's my working hypothesis, and it can't generate wrong code, only suboptimal code.)

So that was my update. See you next time!

donderdag 13 augustus 2015

Inching Closer

Hi everybody, I realise I haven't blogged in a while now, and it'd be a good time to write you an update. I've hit a few problems, but am still making progress.

I've written the tiler algorithm for the JIT compiler. This caused a difficulty because the input graph is not a tree but a DAG, meaning that a node may have more than one 'parent' or 'consumer' nodes. Since consumers decide the tiling of their child nodes, this may mean that the tiles conflict. I resolve such tile conflicts simply by adding a new node to replace the old one.

I've also been busy adding the tile implementations. These are pieces of C code that emit assembly code corresponding to the part of the input tree they represent. This caused some challenges in that tiles sometimes refer to nodes deep in the tree. I solve this by adding traced paths to the nonterminals to the JIT tile table, allowing the JIT compiler to find the nodes refered to and make them easily available. For example:

(add reg (load mem))

The second 'value' argument to this tile is the mem node, not the load. These value arguments are important for managing state between tiles, like the register containing the computed value, or a computed memory address.

To the expression template compiler, I've added the facility to mark certain templates as 'destructive', meaning that they write the value they yield directly to memory. Thus, this value does not become directly available for the JIT tree. Many MoarVM instructions are actually implemented that way, which I noticed when timotimo kindly offered to help write an automated translation tool from the 'old' JIT graph to the new format.

I've changed the JIT-to-interpreter interface to be simpler and deal more sensibly with exits. It used to be the case that the interpreter had to return control out from the JIT-ted frame, so that it'd know when it had unwound the last stack and had to exit. Now the JIT-ted frame is responsible for unwinding the stack itself, much like interpreted code is. The unwound stack check was simple enough to replicate in the JIT interpreter driver instruction.

I've completed the changes to DynASM that allow us to address all x64 general-purpose-registers in all different sizes. This required the addition of a new facility that registered if a so-called REX byte - indicating the use of extended register - was required for addressing the registers supplied to DynASM. Because many fields on MoarVM internal structures are less than 64 bits in size, this was more important than I had realized. At the same time, I've also added value size information to the expression tree, so that these sizes are used correctly.

I've designed, but not yet implemented, a proper register allocator. The key abstraction, I think, is to distinguish between registers which are in use in contrast with registers that are allocated. Allocated registers may be spilt and reused, but used registers may not.

I've documented the syntax and structure of the expression tree format. I hope this will help other people to write JIT extensions and/or optimizations. Documentation on the tiler is work in progress.

My current problem is that the method I had designed last time to derive all possible tiler states is wrong, because it tried to apply a topological sort on a graph that had cycles. Breaking these cycles leads to not generating all permissible tile states, which leads to runtime failure for the tiler. So this has to be avoided, at the same time it is also very important not to generate more tiler states than necessary because otherwise the tile table (and the time spent constructing it) becomes prohibitively large. Despite helpful suggestions by the community, I'm still not sure how to solve this. (It's a similar problem to parser table construction, but... not the same).

All in all, I think I've come very close to really starting to apply the new code generator. I had expected to reach this state earlier, but what I had not realized is that a 'real' compiler requires many moving parts working correctly. Fortunately, I've tried to test new parts as they are being written, so I'm confident that most of them works as expected. Nevertheless, the next weeks are quite exciting, as I'm sure there will be many bugs to find.

Finally, the schedule for this years' YAPC::EU is online, and I'm due to present at 12:00 on Wednesday, in the Aula Magna. For those who'll be there I hope to have an interesting story to tell. See you next weeks!