Re: Framed Stack vs. Two Stack Architecture

On 21 Apr 2006 23:49:01 -0400, "Avatar" <acampbellb@hotmail.com>
wrote:


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


It's not an either/or question ... you can frame stacks regardless of
how many you have.


Separating data from control makes implementing proper tail recursion
easier. If you don't care about that, then how many you use is a
matter of convenience and taste.




>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?


Yes. (see below).




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


Just to clear up a misunderstanding ... by "stack depth" you really
mean "call depth" and the JVM does _not_ know this. The JVM knows the
frame size for each function,but it has no way to determine how many
nested calls may be made to a recursive function.




>At any point code can be evaluated on-the-fly
>within a function. Which I am guessing would eliminate the
>stacked-frame approach? As the frames need to be allocated to a
>certain size (can't grow based upon the demands for operand stack
>space).


You seem to think that "framed" equates to "fixed size". The
conventional stack frame is more of a window defined relative to the
middle.


Technically a "frame" is just a standardized layout. The frame for a
function defines a place for saving each piece of information ...
return address, link to previous frame, parameters, locals, etc.


In a single stack implementation, where the control information and
data are interspersed on the stack, each frame (typically) contains
some data above and below the associated control information.
Information common to all functions (call/return, save/restore regs,
etc.) is placed in the middle at fixed offsets and variably sized
things like parameters and locals are located at the top and bottom
and referenced by relative offsets. A register holds a pointer to the
current frame. Frames on the stack can overlap - one frame's locals
may be another's parameters.


With a separate data and control stack, every function's control frame
layout is (or can be) identical. This makes the control stack simple
because it can be just an array of fixed sized structures. But you
can also implement framing in the (more dynamic) data stack by having
each control frame keep indexing information for its corresponding
"data frame".


You would do well to pick up a few books on language implementation
and read about run time memory layouts.


George

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