Re: Optimizing stack access for a stack based VM

Alex McDonald <>
Thu, 13 Sep 2007 03:51:38 -0700

          From comp.compilers

Related articles
Optimizing stack access for a stack based VM (Jiri Svoboda) (2007-09-11)
Re: Optimizing stack access for a stack based VM (Hans-Peter Diettrich) (2007-09-13)
Re: Optimizing stack access for a stack based VM (Alex McDonald) (2007-09-13)
Re: Optimizing stack access for a stack based VM (Louis Krupp) (2007-09-13)
Re: Optimizing stack access for a stack based VM (Hans-Peter Diettrich) (2007-09-13)
Re: Optimizing stack access for a stack based VM (Hans-Peter Diettrich) (2007-09-13)
Re: Optimizing stack access for a stack based VM (=?ISO-8859-1?Q?Jan_Vorbr=FCggen?=) (2007-09-14)
Re: Optimizing stack access for a stack based VM (Alex McDonald) (2007-09-14)
Re: Optimizing stack access for a stack based VM (2007-09-14)
[3 later articles]
| List of all articles for this month |

From: Alex McDonald <>
Newsgroups: comp.compilers
Date: Thu, 13 Sep 2007 03:51:38 -0700
Organization: Compilers Central
References: 07-09-030
Keywords: storage, optimize
Posted-Date: 13 Sep 2007 13:32:59 EDT

On Sep 11, 10:13 am, Jiri Svoboda <> 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.


See comp.lang.forth,
Anton Ertl's website at,
the comp.lang.forth FAQs:,
and this thread on clf;

Alex McDonald

Post a followup to this message

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