I am working on building a LISP->C translator, and was
struggling with a difficult design question, so I called
out unto the network: "Help!" And yea verily, the network
did come to mine aid....
Here is an abbreviated "problem definition:"
The problem: how can I keep data in CPU registers? The
requirements of the garbage collector seem to make this
nearly impossible. The garbage collector needs to be able
to "see" all of the local variables, so that it can tell
which heap objects are in-use, and which aren't. You can
enable the garbage collector to "see" a variable by passing
a pointer to the variable to the garbage collector, but
by taking a pointer to the variable, you prevent it from
being in a register.
There were several ideas on the subject. The following
is a collection of ideas from many sources, thanks to all who
replied.
Idea 1: Avoid the problem whenever possible.
There are at least two conditions under which the garbage collector
doesn't need to see variables:
1. If a given variable contains only embedded values (ie,
an integer or a character), the garbage collector won't
need to mark it.
2. If a given variable becomes dead (no longer used) before
every call to a function which could involve garbage
collection, the garbage collector doesn't need to see it.
These two techniques could probably enable a moderate proportion
of the variables to become "register", and the only negative
aspect of this solution is that the compiler becomes a wee bit
slower for doing the necessary analysis (of course, I have to
delve into the dark and forbidden magicks of dataflow analysis
in order to pull it off...)
Idea 2: Don't enable the garbage collector to see variables,
enable it to see values.
The idea here is this: the reason the garbage collector needs to
see a variable is to make sure that it doesn't dispose the object
to which the variable points. Really all the garbage collector needs
to know is a list of all the objects to which variables point.
This can be satisfied by notifying the garbage collector every time
a new value is stored in a variable:
UnNotify_GC(C);
C := cons(A,B);
Notify_GC(C);
The UnNotify tells the garbage collector that there is one less
variable pointing at what used to be in C, and the Notify tells the
garbage collector that there is one more variable pointing at the
object newly stored in C.
This can be refined as in part 1: the garbage collector doesn't
always need to be notified, if we are dealing with embedded values
or values that die before garbage collection.
Unfortunately, this method looks more expensive to me than just
not using register variables at all. The NOTIFY and UNNOTIFY macros
probably each require (bare minimum) one memory cycle - which
defeats the whole point of storing the value in a register.
Idea 3: Don't "notify" the garbage collector as to where the variables
are, let it figure out where the variables are itself.
The basic idea is this: all local variables are stored on the stack,
or in registers. There is no other place. So, why bother to notify
the garbage collector as to where the variables are at all? It can
find them. Just scan the stack and the registers.
There are two distint variants of this scheme:
1. The GC can exactly locate each individual variable.
2. The GC can make a conservative estimate of where the variables are.
Method 1, unfortunately, requires exact knowledge of the way the
C compiler lays out activation records and registers. So much for
portability.
Method 2 is more interesting. The idea is this: the GC scans the stack,
looking at every byte it sees. Whenever it sees a machine word that
"could be a valid heap pointer", it marks the object being pointed to
just to be on the safe side. It must scan the registers in the same
way.
This has two disadvantages:
1. Suppose I have an integer variable containing X, and X
just happens to be the address of a heap object. The heap
object will be kept for no reason, and memory will be wasted.
2. Suppose that a pointer to heap object X is found on the
stack. The garbage collector wishes to relocate object X
for the purpose of heap compaction. It would also have to
change the pointer to X on the stack. But what if it wasn't
really a pointer to X, but was in fact a pair of unsigned
short integers that happened to look like a heap pointer?
The integers would have been trashed. Therefore, since the
garbage collector doesn't know where the variables REALLY are,
it can't compact the heap.
On the other hand, it has these advantages:
1. Variables don't need to be initialized. The garbage
collector is quite capable of dealing with nonsense data.
It sees it all the time when scanning the stack. This saves
CPU time.
2. Variables don't need to be notified.
3. Register variables can be used.
4. There are no longer any formal conventions definining
how functions need to cooperate with the garbage collector,
other than simply "variables need to be on the stack or in
registers". Since this is practically inevitable anyway, it
becomes trivial to hand-code C routines that interface with lisp.
It is my feeling that these speed and convenience advantages outweigh
the memory-comsumption disadvantages, and this is the scheme I will
chose.
Portably scanning the stack requires finding the stack bounds at
runtime. Any local variable in C funcion main will be low on the
stack. Any local variable in C function garbage_collect will necessarily
be at the top of the stack during a garbage collection. Everything
in-between is "the stack". This is reasonably portable.
Portably scanning the registers is more of a problem. One strategy
suggested to me was to save the current register environment in a
jmp_buf via setjmp, and then scan that. I don't exactly trust this
method, since people use a lot of wierd tricks when saving the
register environment in a jmp_buf. Another strategy would be to write
a piece of code that is so hairy that it fills all the register
variables with nonsense data, causing the real data to be spilled to
the stack (where it gets scanned). I don't like that method either -
sounds wobbly to me. In the end, though, I suspect that I'll use
the setjmp method, and provide a hook in case that doesn't work on
your cpu.
Thanks again!
Josh