Re: Optimizing stack access for a stack based VM

On Sep 11, 10:13 am, Jiri Svoboda <jirik.svob...@seznam.cz> wrote:
> I'm working on a compiler of a Pascal-like language for a specific
> stack-based virtual machine. To produce small code, I would like to
> optimize the storage of variables and temporaries akin to register
> allocation on a register-based machine.
>
> Local variables should occur as natural operands of instructions (on
> the stack top) as much as possible, removing the need to fetch them
> from the middle of the stack (and encode displacement values).
>
> (More detailed description below.)
>
> Do you know if anyone already tried something like this, can you point me
> to any algorithms/articles/software?


Much of what you describe is accomplished by Forth.


> Target machine description:
>
> In short: Imagine a classical Harvard-style RISC processor, only that there
> are no registers, instruction operands are on the stack.
>
> There are separate address space for (1) code, (2) data, (3) stack.


The separation between code and data isn't required in Forth (although
there may be advantages in certain architectures that treat each space
differently, or don't like mixing of code and data).


> Code - classical linear sequence of instructions with conditional jumps
> for branching


Or token-threaded code; it doesn't need to be executable code.


> Arithmetic instructions - for example "add" - pops two values off the stack,
> adds them and pushes the result onto the stack
>
> Data - "ld [<addr>]" loads a word from the given address and pushes it
> on the stack; "st [<addr>]" pops a word off the stack and stores it
> to the given address. "Static" variables are stored here.


Forth uses addresses on the stack, and a @ (fetch contents of address)
and ! (store into address the value 2nd on the stack).


variable x
10 x ! \ set x to 10; x puts the address on the stack for the 2
operand !


> Stack - direct access to stack is possible, "stkld [<offs>]", "stkst [<offs>]"
> similar to ld/st, but <offs> is relative to the stack top. Auxiliary
> instructions: "dup" duplicate value on stack top, "trash" remove value from
> stack top, "swap" exchange two values on stack top. "Automatic" variables
> and temporaries are stored here.


Most operations in a stack based VM only require access to the top 2
stack entries. Forth provides your basic arithmetic instructions,
along with stack juggling words; SWAP and DUP you mention, and "trash"
is DROP. Also consider having an OVER ( a b -> a b a ).


The stack offset word you describe is Forth's PICK; but it is
infrequently used, and can be eliminated entirely for most code.
Digging down on the stack is frowned on in Forth, because many of the
machines on which it is implemented do not have an item addressable
stack. In general, it's not required, and 99 times out of 100
indicates a loss of stack control on the part of the programmer.


> Obviously anytime we want to execute an arithmetic operation it
> would be beneficial to have its operands on the stack top removing
> the need for stkld/stkst (and coding <offs>).


"Variables" in Forth are words that push their addresses on the stack,
as in the @ and ! example given above. Forth also has a value, or a
self fetching variable.


> While we get this for free for temporaries (= temporary results in
> arithmetic expressions) just by producing stack-based code from the
> source code, I'd like to extend it to work for variables, too.


> I suppose an algorithm for an accumulator-based machine (which has 1
> accumulator register) could also be used (with less efficiency).


It might be more efficient if stack accesses are more expensive than
accumulator accesses. Just consider the accumulator as the top entry
of the stack, and the stack holds entries below that.


> TIA


See comp.lang.forth,
Anton Ertl's website at http://www.complang.tuwien.ac.at/anton/home.html,
the comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html,
and this thread on clf; http://groups.google.com/group/comp.lang.forth/browse_frm/thread/3171c3f0aba6b972/?hl=en#


--
Regards
Alex McDonald

Return to the comp.compilers page.
Search the comp.compilers archives again.