From: jinx@zurich.ai.mit.edu (Guillermo J. Rozas)
Newsgroups: comp.arch,comp.lang.lisp
Subject: Re: Ideas for new LISP Machines
Date: 11 Apr 92 13:57:17 GMT
Article-I.D.: chamarti.JINX.92Apr11095717
	<kuca34INN4k5@boogie.cs.utexas.edu>
Reply-To: jinx@zurich.ai.mit.edu
Followup-To: comp.arch
Organization: M.I.T. Artificial Intelligence Lab.
In-reply-to: wilson@cs.utexas.edu's message of 10 Apr 92 23:44:36 GMT

In article <kuca34INN4k5@boogie.cs.utexas.edu> wilson@cs.utexas.edu (Paul Wilson) writes:

* I'm not exactly sure what you mean here.  Consider a closure to be
* a procedure object paired with a particular binding environment
* (set of captured variables).  Is it that you want to have a single
* object (say, on the heap) that contains both the variables and the
* actual executable code?  Is it insufficient to pair a code pointer
* with the variables, and call the code indirectly?

It is insufficient for two reasons:

- External constraints on procedure representation to maintain
inter-callability, e.g. Unix's qsort routine expects an ordinary
function pointer, not a closure.

- Even if the representation were uniform for a given system, that is
all procedures used two words to contain a code pointer and
environment pointer, this representation penalizes the vast majority
of procedures in the world, for which the environment pointer is
ignored!  The price of closures should be paid by closures, not by
everything else.

What he wants for GNU C, is something that other Scheme systems also
have to do.  We like to represent all procedures as addresses of
instructions.

Closures are constructed by allocating a block of memory that includes
a JSR/CALL/BL instruction to the shared code and the free variables of
the closure.

In this way, the calling convention is uniform and the caller need not
know whether it is invoking a closure or a "simple" procedure, yet
closures have pointers to their free variable block conveniently made
available when they are called.  Using such a representation, a Scheme
closure can be happily passed to a C function that need not know it is
dealing with one.

The problem is that there are two features of modern architectures (or
their new implementations, e.g. 68040) that make this difficult:

- Separate I and D caches with a copyback D cache so that the new
  instructions are not guaranteed to make it out to main memory by the
  time the I cache requests them.

- Large cache lines (whose size sometimes depends on the generation of
  the hardware) so that even if the D cache is not a copyback cache
  (e.g. most MIPS processors) stale data may already reside in the I
  cache because it was brought in when a previously-allocated closure
  was invoked.

Note that the issue is not the modification of old code, but of
creating new code on the fly!  The second problem makes it appear like
modification of old code, but that is only because the memory system
caches units larger than a single word. _Logically_, no old code is
ever over-written (except, of course, by the GC when it moves
everything around, but that is a separate story).

The second problem can be handled, if necessary, by making sure that
closures are always separated by the size of a cache line.
Unfortunately, a new version of the processor may increase that, and
old binaries will break.

Fortunately, many architecture designers provide a user-mode way to
request a cache synchronization.  Although this might be expensive if
it had to be done every time a closure was allocated, the cost can be
amortized over many closures.

The MIT Scheme compiler and its runtime library use two somewhat
different ways to represent closures and allocate them:

- There are machines on which there is no problem either because the
architecture guarantees coherence between the I and D streams (e.g.
386/486, VAX), or because there is a low-cost, fine-granularity
cache-synchronization instruction (e.g. HP-PA's FDC followed by FIC).
The code generator does the obvious thing.

- There are machines in which the way to synchronize the cache is
expensive because it requires the use of a many-cycle instruction or
may require a system call (e.g. 68040, Alpha).  In these machines, the
runtime library maintains a region of memory full of JSR/CALL/BL
instructions all pointing to a fixed address in the runtime library.

When allocating a closure, its memory is allocated from this region
and the address of the shared code of the closure is placed following
one of the JSR instructions, followed by the free variables.
If the pool is empty, a service routine is invoked to allocate a new
pool from the ordinary heap, fill it with JSR instructions, and
synchronize the caches.  In this way, by the time any of them are
invoked, the whole region has made it out to main memory and the I
cache will get the instructions.  Cache line sizes are not a problem
because, although some of the instructions will be overwritten later
with the actual free variables of closures (and perhaps their GC
headers), those instructions will never be executed.  The only
instructions in the block that are executed are those that are left
unchanged.

The fixed address in the runtime library uses the return address to
extract the target address from the closure, and jump to it.  Although
it is a pretty cheap routine, calling a closure represented in this
way is more expensive than one that directly invokes the target
address.  This can be remedied by modifying the closure-allocation
service routine to fix up the closures in the previous region
allocating a new region and synchronizing the caches (this is real
code modification, but followed by a synchronization).  Otherwise the
GC can be taught how to do this when it transports closures.  Thus
closures that stick around for a while will eventually use the more
direct sequence.
Xref: sparky comp.arch:5036 comp.ai:2002