Re: Framed Stack vs. Two Stack Architecture
- From: George Neuner <gneuner2@xxxxxxxxxxx>
- Date: 23 Apr 2006 10:06:33 -0400
On 21 Apr 2006 23:49:01 -0400, "Avatar" <acampbellb@xxxxxxxxxxx>
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
.
- References:
- Framed Stack vs. Two Stack Architecture
- From: Avatar
- Framed Stack vs. Two Stack Architecture
- Prev by Date: Re: understanding the intuition behind LL(k) parsers and LR(k) parsers
- Next by Date: Re: Framed Stack vs. Two Stack Architecture
- Previous by thread: Re: Framed Stack vs. Two Stack Architecture
- Next by thread: Re: Framed Stack vs. Two Stack Architecture
- Index(es):
Relevant Pages
|
|
