I am currently implementing a Lisp->C translator, and have
stumbled across an implementation problem for which I can
think of no decent solution. I need suggestions - Help!
The problem: how can I keep data in CPU registers? The
requirements of the garbage collector seem to make this
nearly impossible.
Warning: long, rambling discussion follows.
Suppose I want to translate this:
(defun foo ()
(let ((i (list 'a))(j (list 'b)))
(cons i j)))
This translation is wrong:
lispobj FOO()
{
register lispobj I;
register lispobj J;
I=list_of_one_elt(SYMBOL_A);
J=list_of_one_elt(SYMBOL_B);
return cons(I,J);
}
because the garbage collector cannot "See" the variables
I and J. If the second "list_of_one_elt" triggers a garbage
collection, the garbage collector will have no way of knowing
that the variable I exists, much less points to a list
containing the symbol A.
So, suppose that the garbage collector keeps a table of all
the local variables in existence. Of course, this function
will need to add its local variables to the table, and
then subtract them when it's done:
lispobj FOO()
{
lispobj I;
lispobj J;
lispobj result;
gc_add_var(&I);
gc_add_var(&J);
gc_add_var(&result);
I=list_of_one_elt(SYMBOL_A);
J=list_of_one_elt(SYMBOL_B);
result = cons(I,J);
gc_del_var(&result);
gc_del_var(&J);
gc_del_var(&I);
}
This is legal, but I had to discard the register declarations
in order to take the address of the variables I and J.
Another possibility would be to use register variables
as caches, and spill them into memory whenever a garbage
collection could conceivably occur. This sounds like an
awful lot of register spilling to me, though, and it could
easily take longer than the other approach.
······@m.cs.uiuc.edu (Josh Yelon) writes:
>I am currently implementing a Lisp->C translator, and have
>stumbled across an implementation problem for which I can
>think of no decent solution. I need suggestions - Help!
>The problem: how can I keep data in CPU registers? The
>requirements of the garbage collector seem to make this
>nearly impossible.
>Warning: long, rambling discussion follows.
>Suppose I want to translate this:
> (defun foo ()
> (let ((i (list 'a))(j (list 'b)))
> (cons i j)))
[trimmed]
>So, suppose that the garbage collector keeps a table of all
>the local variables in existence. Of course, this function
>will need to add its local variables to the table, and
>then subtract them when it's done:
> lispobj FOO()
> {
> lispobj I;
> lispobj J;
> lispobj result;
> gc_add_var(&I);
> gc_add_var(&J);
> gc_add_var(&result);
This still isn't correct; the values of the variables are uninitialized,
and are probably going to cause problems for the GC. You don't really want
to protect the variables, anyhow; you want to protect the *values*.
Registering the variables is one approach to protecting the values, but
some others might be more feasible.
Consider:
> I=list_of_one_elt(SYMBOL_A);
I is "live" and another cell is about to be allocated; this is a possible
GC problem. Protect the value (or protect all values from the cell
generator, and unprotect them when done).
Assuming a special register reserved for protection (global value, whatever;
the point is that it is a register for the lisp virtual machine), this looks
something like:
prot = cons(I, prot);
> J=list_of_one_elt(SYMBOL_B);
J is "live"
> result = cons(I,J);
If cons() protects its inputs, no protection needs to be done across the
call to cons, as all the live values are passed to it.
And at the end, clean up the protected values:
prot = cdr(prot);
This sort of approach is the style that we use in PSI; while the code that
I'm discussing is *not* generated by a compiler (the primitives are
currently hand-written), this is the sort of analysis which one performs
to prevent the garbage collector from running away with live values.
Regards,
Dak
--
David A. 'Dak' Keldsen of SoftQuad, Inc. email: ···@sq.com phone: 416-963-8337
"However, let's assume that we want the program to run faster. A
dangerous assumption, but it's a wretched, miserable, rainy night out
and I want to have a little fun." -- (Andrew Koenig, in comp.lang.c)
On 15 Jul 91 03:55:00 GMT, ······@m.cs.uiuc.edu (Josh Yelon) said:
jyelon> I am currently implementing a Lisp->C translator, and have
jyelon> stumbled across an implementation problem for which I can
jyelon> think of no decent solution. I need suggestions - Help!
jyelon> The problem: how can I keep data in CPU registers? The
jyelon> requirements of the garbage collector seem to make this
jyelon> nearly impossible.
Well, the problem is that you generate code for the C virtual machine,
but your collector is running on the real machine, and you cannot
(portably) make assumptions about how the C compiler maps the C virtual
machine into the real machine.
Putting it this way the problem is nearly insoluble, in that every
solution is less efficient than just not using 'register' and the like.
Another poster remarks that you do not really want to protect the
register, but the value pointed to by the register, so instead of GC
protecting the register, you can GC protect the value denoted by the
register, and then keep using the register for accessing that value.
I mean
lispobj Ival,Jval;
register lispobj I, J;
I = GC_set_and_protect(&Ival,list_of_one_elt(SYMBOL_A));
J = GC_set_and_protect(&Jval,list_of_one_elt(SYMBOL_J));
...
GC_unprotect(Ival,Jval,(void *) 0);
In this way you have fast accesses using registers, and protection using
regular variables, at the price of an explicit protect/unprotect job.
But have youn considered solving the problem by using a conservative
garbage collector? Your problems would be easily solved with the
smallest overhead. The conservative collector could simply scan all
registers, and take as a pointer anything in them that could be taken as
a pointer.
--
Piercarlo Grandi | ARPA: ··············@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: ···@aber.ac.uk