EDIT: Lutz Euler points out that the NEXT sequence (used to) encode
an effective address with an index register but no base. The mistake
doesn’t affect the meaning of the instruction, but forces a wasteful
encoding. The difference in machine code are as follows.
Before (14 bytes):
1 2 3 4 |
|
Now (9 bytes):
1 2 3 4 |
|
I fixed the definition of NEXT, but not the disassembly snippets
below; they still show the old machine code.
Earlier this week, I took another look at the
F18. As usual with Chuck Moore’s
work, it’s hard to tell the difference between insanity and mere
brilliance ;) One thing that struck me is how small the stack is: 10
slots, with no fancy overflow/underflow trap. The rationale is that,
if you need more slots, you’re doing it wrong, and that silent
overflow is useful when you know what you’re doing. That certainly
jibes with my experience on the HP-41C and with x87. It also reminds
me of a
post of djb’s decrying our misuse of x87’s rotating stack:
his thesis was that, with careful scheduling, a “free” FXCH makes
the stack equivalent – if not superior – to registers. The post
ends with a (non-pipelined) loop that wastes no cycle on shuffling
data, thanks to the x87’s implicit stack rotation.
That lead me to wonder what implementation techniques become available
for stack-based VMs that restrict their stack to, e.g., 8 slots.
Obviously, it would be ideal to keep everything in registers.
However, if we do that naïvely, push and pop become a lot more
complicated; there’s a reason why Forth engines usually cache only the
top 1-2 elements of the stack.
I decided to mimic the x87 and the F18 (EDIT: modulo the latter’s two
TOS cache registers): pushing/popping doesn’t cause any data movement.
Instead, like the drawing below shows, they decrement/increment a modular
counter that points to the top of the stack (TOS). That would still be
slow in software (most ISAs can’t index registers). The key is that
the counter can’t take too many values: only 8 values if there are 8
slots in the stack. Stack VMs already duplicate primops for performance
reasons (e.g., to help the BTB by spreading out execution of the same
primitive between multiple addresses), so it seems reasonable to specialise
primitives for all 8 values the stack counter can take.
In a regular direct threaded VM, most primops would end with a code
sequence that jumps to the next one (NEXT), something like
add rsi, 8 ; increment virtual IP before jumping
jmp [rsi-8] ; jump to the address RSI previously pointed to
where rsi is the virtual instruction pointer, and VM instructions
are simply pointers to the machine code for the relevant primitive.
I’ll make two changes to this sequence. I don’t like hardcoding
addresses in bytecode, and 64 bits per virtual instruction is overly
wasteful. Instead, I’ll encode offsets from the primop code block:
mov eax, [rsi]
add rsi, 4
add rax, rdi
jmp rax
where rdi is the base address for primops.
I also need to dispatch based on the new value of the implicit stack
counter. I decided to make the dispatch as easy as possible by
storing the variants of each primop at regular intervals (e.g. one
page). I rounded that up to 64 * 67 = 4288 bytes to minimise
aliasing accidents. NEXT becomes something like
mov eax, [rsi]
add rsi, 4
lea rax, [rax + rdi + variant_offset]
jmp rax
The trick is that variant_offset = 4288 * stack_counter, and the
stack counter is (usually) known when the primitive is compiled. If
the stack is left as is, so is the counter; pushing a value decrements
the counter and popping one increments it.
That seems reasonable enough. Let’s see if we can make it work.
I want to explore a problem for which I’ll emit a lot of repetitive
machine code. SLIME’s REPL and SBCL’s assembler are perfect for the
task! (I hope it’s clear that I’m using unsupported internals; if it
breaks, you keep the pieces.)
The basic design of the VM is:
r8–r15: stack slots (32 bits);rsi: base address for machine code primitives;rdi: virtual instruction pointer (points to the next instruction);rax,rbx,rcx,rdx: scratch registers;rsp: (virtual) return stack pointer.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
The idea is that we’ll define functions to emit assembly code for each
primitive; these functions will be implicitly parameterised on
*stack-pointer* thanks to @. We can then call them as many times
as needed to cover all values of *stack-pointer*. The only
complication is that code sequences will differ in length, so we must
insert padding to keep everything in sync. That’s what emit-code
does:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
This function is used by emit-all-code to emit the machine code for
a bunch of primitives, while tracking the start offset for each
primitive.
1 2 3 4 5 6 7 8 9 10 |
|
Now, the pièce de résistance:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
Let’s add a few simple primitives.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
The code for swap lives between bytes 0 and 32. Let’s take a look
at the version for *stack-pointer* = 0 and *stack-pointer* = 1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
dup is at 32-64, and sub at 128-152:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
