On Wed, Jun 05, 2002 at 04:52:22PM -0400, Dan Sugalski wrote:
> Could be wrong, of course. Wouldn't be the first time. I'll need more
> convincing for that, though.
Is this enough? :)
Stack usage
===========
First, the stack are going to be used quite heavily: we need to save
all live registers before performing any function call. The
alternative is to save them on the heap, rather than on a stack (this
is the design choice made for SML/NJ), but then we need a really good
GC to collect all the generated garbage.
A typical function will call some other functions and perform some
computations. So, let us consider a function that call a first
function, perform a computation, and call a second function. If we
use the stack frame stack, we are going to save all registers twice and
reload them all twice (once per function). If we use a generic stack,
we can do the following:
- save all live registers before calling the first function
- call the first function
- reload only the registers we need for the computation and the next
function call
- perform the computation
- save only the registers that contain the result of the computation
- call the second function
- reload only the registers needed for the remainder of the function.
The per-register cost may be higher when saving/loading individual
registers, but I think we save and load a lot less registers this way.
GC
==
The GC need a way to know which stack entries to follow.
There are different options:
(1) Homogeneous stacks: all entries have the same type
(2) Typed entries: a type is stored with each entry
(3) Typed frames:
the stack is divided in frames; a frame descriptor is stored
whithin each frame and indicates to the GC which entries need to
be followed
(4) Frames typed based on the return address:
there is a table indicating for each return address which entries
of the frame need to be followed by the GC
At the moment, we use (1) for the register frame stacks, and (2) for
the generic stack. I'm proposing to use (3) initially, and eventually
move to (4).
A common problem to (1), (2) and (3) is that they may induce memory
leaks. Indeed, the GC may follow a dead entry. Of course, it is
possible to clear the dead registers before saving all registers, or
clear a stack entry when it becomes dead. But this has some runtime
cost.
Performance
===========
If we assume that a lot of registers are live, the register frame
stack is a really efficient way to save them. But I think this
assumption is rarely satisfied.
Currently, the generic stack has a lot of overhead:
- there needs to be an overflow check each time something is pushed on
the stack
- similarly, there need to be an underflow check each time something
is popped
- each stack entry contain both a value and its type
We can reduce the overhead if we have an operation that reserves some
space (a frame) on the stack, and one that releases this space. Then,
we can eliminate the overflow and underflow checks for each individual
read an write operations on the stack. We can also avoid storing the
type of each value if the operation that reserves a frame also pushes
a pointer to a description of the frame. But then we are really close
to my proposal...
Once all the overhead has been removed, the basic stack
operations (saving and loading a register) becomes really cheap.
Actually, accessing the stack could be made just as fast as accessing
a register.
The above is especially true with the JIT compiler. With the
interpreter, we still have a pretty high per-instruction cost. But
this cost can be reduced by combining several instructions into a
super-instruction: for instance, an instruction that saves several
registers at once.
Callcc
======
I'm really interested on how you intend to implement callcc. It does
not seem obvious to me how to do it with multiple stacks which are not
explicitely divided in frames.
Exceptions
==========
Exceptions are much easier to implement than callcc. For the sake of
simplicity, let us assume we only have one stack. The interpreter
structure should contain an exception handler pointer.
To set-up an exception handler:
- save all live registers
- push the address of the exception handler on the stack
- push the previous exception handler pointer
- set the exception handler pointer to the top of the stack
To raise an exception:
- set the top of the stack to the exception handler pointer
(we may need to free some stack chunks here)
- restore the previous exception handler pointer
- pop the exception handler address
- jump to this address
To remove an exception handler:
- restore the previous exception handler
- pop the exception handler address
