Re: Framed Stack vs. Two Stack Architecture

"Avatar" <acampbellb@hotmail.com> writes:
>We are implementing a stack-based VM for a small interpretive
>language. I am currently investigating stack architectures and would
>like to better understand the advantages / dis-advantages of a
>framed-stack vs. two stack approach.
>
>I understand that the JVM architecture implements a framed-stack: one
>frame per activation record (method call) with an embedded operand
>stack. So essentially they have rolled the execution stack and operand
>stack into one. Right?


That's a good way to implement the JVM, but you could actually also
implement it in different ways, say, one stack for operand evaluation,
one for locals, and one for return addressses and maybe old frame
pointers; if you have separate operand and locals stacks, you would
have to move the function parameters from the operand to the locals
stack on function calls.


>I also understand that there are architectures (although I have been
>unable to find a reference implementation for this) that maintain two
>separate stacks: a execution (control) stack for function calls, and a
>separate data stack for (bytecode) instruction evaluation.


Forth has at least two stacks: The main purpose of the return stack is
to store return addresses, but it is typically also used for values
that would be in the way on the data stack, such as count values for
counted loops and locals (unless the system has a separate stack for
those). The data stack is used for most other purposes, in particular
computation.


As for reference implementations, there are lots of Forth
implementations around, e.g., Gforth.


An advantage of this approach is that in some cases you need less or
no copying of function parameters when calling another function.
Consider:


foo(int a, int b, int c)
{
    return bar(a,b,c)+1;
}


With a separate return stack and appropriate call semantics this can
be compiled to:


#parameters already on the stack from call to foo
call bar
iconst 1
iadd
ireturn


whereas in the JVM (where the call removes the parameters from the
operand stack) you would have to start this with a string of iloads.


Also, in such a setting it is easier to get by without a frame pointer
(but you need a second stack pointer).


Which of these two approaches is better in your case depends on how
you want to compile the code. I think that, for an Algol-style
language (like Java) and a simple (non-optimizing) compiler, the JVM
approach is probably better.


Another issue where you might consider using an additional stack is
floating-point computations: it makes it easier to deal with a
possible size and alignment mismatches between the integer and the FP
values. More importantly, if you want to gain speed by keeping stack
items in registers (with is relatively easy at least with one stack
item), having an FP value (or part of it) in an integer register makes
code dealing with FP values relatively slow; with an FP stack, you can
keep them in an FP register.


The downside, again, is the use of an additional stack pointer
register.


>The language we are implementing is dynamic in nature (dynamic typing
>and alllows for on-the-fly code evaluation) so we would not have the
>advantage that the JVM has in knowing the max stack depth (operand
>stack) at compile time. At any point code can be evaluated on-the-fly
>within a function. Which I am guessing would eliminate the
>stacked-frame approach?


Dynamic typing should not have an influence; you will usually only put
pointers to boxed values on the stack (which is another solution to
the FP value problem), so it does not change the stack depth at all.


For on-the-fly code evaluation, you can determine the maximum stack
depth when you translate it from source form to VM form. If you
allocate the frame before that time, and if it turns out that there is
not enough space in it, and if the operand stack must not overflow the
frame, then you certainly have to change something, but I can imagine
many correct ways that use frames.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html

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