JIT Compiler for Forth(twitter.com) |
JIT Compiler for Forth(twitter.com) |
I want to talk a little about my JIT forth compiler -- the one that sometimes manages to beat C. I want to talk about how what is going on, because I think it's interesting & have some ideas for how to build on it. The idea for this engine was to take the STC (Subroutine Threaded Code) technique and adapt it to a register machine with a single stack, like x86. The big idea is that each word will be given a "type signature", and it will take its inputs & outputs entirely in registers. To this end I defined these immediate words: If the type signature is given, the word doesn't have to receive any arguments on the stack, it receives them all in registers.
Likewise, all the word's outputs are given in registers instead of the stack. The word never needs to dig into the stack for any of its operation. This means we can actually leave the return address on the stack! I.e. when we call a word like FIB, the compiler leaves the return address on the stack, so that "RET" just works as usual. It's a simple CALL/RET. By contrast, if we didn't have any of the "type signatures", like in a standard forth, we need two stacks -- one for passing data and one for return addresses. This works well for the compiler, because it can manage registers (e.g. using a finite state machine, which is what I did) when compiling a definition. But forth systems also include an interpreter, which is used to interpret the text file in the first place.
There's also the question of words like EXECUTE, which have to work with any XT (execution token -- basically a pointer to a word). How does the interpreter (or EXECUTE) manage all the different ways needed to call a word? Well, there's a very nice solution. Actually I didn't change the text interpreter (or EXECUTE) at all when I adapted my STC engine to this new approach. As far as they are concerned, this is still a typical forth system with two stacks. How it works is that each word's XT actually points to a "preamble" that will expose a uniform calling convention for this word. This preamble is responsible for popping inputs from the stack into registers, calling the word, and then pushing the word's outputs on the stack. Thus each word has two entry points: the preamble which has a uniform calling convention that fits well with the surrounding forth system, and the actual word definition which has a calling convention tailored to this specific word. This also allows us to mix "typed" and "untyped" word. An untyped word simply doesn't have the second entry, it uses the uniform calling convention, and anyone can call it if they push the (virtual) stack values on the actual stack.
But when the compiler sees a word with a type signature, it bypasses the preamble. So we only pay for the preamble when we use the uniform calling convention, e.g. in the text interpreter, or when calling EXECUTE. Actually it would be possible to have a typed EXECUTE, one for each type signature. E.g. EXECUTE-(X--X), which would skip the preamble. I didn't implement this because I don't need to, but it's a possibility. So, this pretty much describes how I managed to make a forth engine that compiles fast machine code. There's lots more details about, e.g., how to pick registers, how to inline primitives, dealing with branches, optimization ... But it's too much for this thread. What I did want to talk about is how working on this implementation finally gave me a good idea for how to integrate a type system into forth! One of the challenges of adding a type system to forth, is that forth is very dynamic. There's a complex mixture of execution and compilation going on at all times. E.g. you are compiling a word, say "dup", so now you have to execute dup's compiler, which is also a word. A dynamic type system, like Lisp or Python, would work fine, but it kind of clashes with the idea that forth is a low level language.
Also it doesn't solve the issue of type checking, which is more critical in forth IMO than in those languages, because of its stack-y nature. OTOH a fully static type system doesn't make it easy to implement the dynamic text interpreter, or compile time execution in general. I implemented a fully statically typed forth and it missed this side of the language completely. So my idea is to adapt the approach that worked well for "calling conventions". Each word will actually have two entry points: a "dynamic" entry point, which is the preamble, and a "static" entry point, which is the main definition of the word. Values on the data stack will actually be tagged with their type (& size), like they would be in a dynamic language. But once you call a compiled word with a type signature, the preamble will check that the tag is acceptable, and pass along only the payload, in a register. This would also let us have values that are larger than one cell, e.g. an array slice can be passed around as a single value that takes up two cells on the return stack, and so has two registers. So with this approach we can have this weird mixture of strong statically typed code, with lots of dynamic hooks into it, and a dynamic text interpreter. This is a kind of gradual typing, I guess.
It seems very promising as an approach for building a typed forth engine. Anyway, I'm super excited to try this out! Thanks for reading! If you're interested in this "typed forth" that I'm working on, and want to support me, please join my Patreon!