Optimizing stack access for a stack based VM

Hello everyone,


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?




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.


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


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.


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.


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>).


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).


TIA


Regards
Jiri

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