Re: paper on implementation

[David Given <dg@...>]

On Thursday 24 February 2005 06:25, Taj Khattra wrote:
> > (Ok, I wasn't plain guessing when I made those decisions, but most
> > papers I've seen on stack vs register based VMs and the like are
> > mostly theoretical, or based on prototype/proof-of-concept
> > implementations.
>
> here's a link to a (short) 1997 paper which describes the rationale
> for choosing a register-based vm for inferno, in preference to a
> stack-based vm, for easier on-the-fly compilation:

I'm currently working on resurrecting an old compiler toolchain called the 
Amsterdam Compiler Toolkit; it was originally written by Andy Tanenbaum and 
Ceriel Jacobs, and was used in Minix for years. It compiles a whole bunch of 
input languages into a whole bunch of backends --- and it does this by using 
an intermediate language, for which a VM and interpreter is provided. (So you 
can compile stuff into runnable intermediate-code binaries, run them in the 
bulletproof interpreter for debugging, and then translate them into native 
code and deploy.)

The ACK's VM, which is called EM, is stack-based. Here's a sample:

4:
 lol −2
 zle *5 ; while i > 0 do
 lol −4
 lil 0
 adi 2
 stl −4 ; j := j + r.r1
 del −2 ; i := i - 1
 bra *4

The company for which I work produces a very portable operating system by 
doing pretty much the same thing; except our VM, which is called VP, is not 
directly runnable (because stuff is translated on demand at run time).

VP is register based. Here's a sample:

label:
 bool (i1 <= 0), endloop
 cpy (i0 + [p0+0]), i0
 cpy (i1 - 1), i1
 go label
endloop:

(Frankly, I think VP is more readable!)

It's been *fascinating* looking at the differences between the two code 
generators. EM has lots of interesting technology to short-circuit the stack; 
the code generator remembers what's on the top of the stack and caches it in 
registers if at all possible. VP has lots of interesting technology to push 
registers efficiently onto the stack if the target machine has fewer 
registers than VP has (VP can have up to 65535 registers each of integers, 
longs, doubles, floats and pointers. Mapping this onto, say, the i386 with 
its five registers is interesting).

I must some day do a direct comparison between i386 code produced by EM and 
i386 code produced by VP, from the same C source...

Lots of information about the ACK here:

http://tack.sourceforge.net/

Alas, I can't point you at anything for VP because it's all private.

-- 
+- David Given --McQ-+ "If God spammed rasfw with the answer to Life, the
|  dg@cowlark.com    | Universe, and Everything, I'd report him to
| (dg@tao-group.com) | abuse@heaven.org." --- David Bilek
+- www.cowlark.com --+