HYDROGEN: Code generation (by alaric)
SHUFFLE and locals
Traditional FORTH has stack manipulation words that do things like discard elements from the stack, duplicate the top element, locate an element from further down the stack and copy it to the top, and so on. These are required, since sometimes things aren't on the stack in the order you need to work on them, sometimes you need to use some value but keep a copy of it to use again later, and sometimes something is on the stack that you don't need.
But, they are instructions that basically get nothing done. Sure, with an optimising compiler as I discussed above, they can be implemented to produce no actual code (except maybe a register->register move in the case of duplications) but simply to alter the register mappings; but the effects of them can be hard to read by eye. And, as I mentioned above, it becomes tricky to perform stack rearrangement in portable systems like HYDROGEN where the size of different types of values on the stack can vary between platforms, and some values may not even be on the same stack.
So, we provide a word called SHUFFLE[. This word parses a description of what the top few elements of the stack currently are - their types, and identifying names for them, such as c.foo c.bar f.baz for two cells (where 'cell' means 'machine word') called foo and bar and a float called baz. This is terminated by the string --, and after that is parsed a description of what we'd like the stack to now be like, written in the same format, and this time terminated with ]. The parse subroutine pushes a representation of the required stack machinations, and run implements them, while compile compiles code to do them.
So one can write SHUFFLE[ c.foo u32.bar f.baz -- f.baz f.baz f.bar ] to say "Expect the top element of the stack to be a float, with a u32 (an unsigned word of at least 32 bits) and a single machine word beneath it; replace them with two copies of the float, followed by the u32 converted into a float". That has discarded c.foo, duplicated f.baz, converted u32.bar into f.bar, and generally rearranged everything.
This is a fairly complex word in itself, but it replaces a complex horde of words to convert between numeric types, to duplicate and discard members of various types, and to work out how to rearrange the stack; and all of these functions are accessible with a single easy-to-use syntax.
And, of course, the effect of SHUFFLE['s compile subroutine is probably to compile code to push the representation of the stack machination onto the stack followed by call to SHUFFLE['s run subroutine - which the peephole optimiser will notice and then handle by fixing up the stack->register mappings, and compiling code to perform any required duplications or type conversions.
But a major source of stack machinations in FORTH can be avoided directly with a more specialised tool: local variables. These are implemented with the BEGIN[ word, which like SHUFFLE[ also parses a set of <type>.<name> tokens, this time terminated by ]. It compiles code to pop all the mentioned values off of the data stack and to squirrel them away into an implementation-private "locals stack" frame that's large enough for them, then it places word definitions onto the current word list for each of the names mentioned, pointing at words whose run subroutine copies the corresponding slot out of the locals stack frame onto the data stack; and words called SET-<name>! for each name, that overwrite the corresponding slot in the stack frame with a value taken from the top of the stack. A corresponding END word removes the local word definitions, freeing up the subroutines and the word definitions, and compiles code to pop the locals off of the stack to reclaim the space.
Needless to say, if a BEGIN[ is nested within another BEGIN[, then the offsets onto the locals stack are suitably modified to make sure that the outer definitions still work!
Tue 14th Jul 2009 2:40 pm 
Subscribe
By Gavan, Thu 16th Jul 2009 @ 11:53 am
Do you have any mechanism for assuring that a certain bit of code which will be used later must be compiled by a certain point in the code?
I can think of several cases (mostly within device drivers) where the latency of certain routines is critically important, and having to wait (even the first time) for the parser to do its thing could lead to lots of unpleasantness.
By alaric, Thu 16th Jul 2009 @ 12:35 pm
The definition of a subroutine with
( ... )compiles it there and then, in the implementations I have planned (except for the case of tethered systems, but you'll have to wait to hear about them). Either way, by the time you call a subroutine, it ought to be compiled.It's all up to the implementation, though - weird JIT stuff could be done. It's just that those implementations would suck for real time stuff, and should say so on the tin 🙂
By alaric, Fri 17th Jul 2009 @ 2:07 pm
This is also interesting reading:
http://factor-language.blogspot.com/2009/07/improved-value-numbering-branch.html