For those in-twitter-visible, here is a, poorly formatted, copy of the twitter thread, for a forth with some interesting ideas:
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, l...
4 comments
[ 3.4 ms ] story [ 20.4 ms ] threadI 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, l...