[gclist] region inferencing

[David Chase]

At 10:45 AM 11/6/97 +0100, Christian Fabre wrote:
> ... what is "region inferencing"
>actually?
>
>A full dissertation is not necessary, a few lines would be fine.

Given sufficient analysis of a program, it is possible to determine
an upper bound on the lifetime of any memory allocation, and choose
some method of reclamation that is not garbage collection.  "Region"
refers to discovering what region of the program a piece of storage
is used in, and reclaiming that storage sometime after it is no longer
in use.  In a seemingly-stupid-but-actually-useful case, you can
bound the lifetime of all storage allocated in a terminating program
by the termination of the program; that is, when the process dies,
the operating system reclaims all resources allocated to it.  Obviously,
that's not what's begin discussed here, but in practice people do this
all the time, and are quite satisified with the results.

Limited forms of this have been around for quite some time; the
SETL people did a lot of work on this, for instance.  I think
Jeff Barth's (CACM?) reference-counting paper included a mention
of reclamation if the inferred reference count fell to zero.
Christina Ruggieri wrote a dissertation on this in 1987, mine
(which covered overlapping material) was finished shortly
afterwards in 1987.  "Escape analysis" (I think that is what it
is called) for local variables can be view as a form of this --
in a language with first-class-functions, if all local variables
are seen not to "escape" the frame in which they are allocated,
then that frame can be stack allocated.  In general, I think you
have to view this as either a no-garbage-collector-at-all
optimization (no pauses, for example) or else a space-optimization;
if you try to do all the allocation on the stack, you can get
yourself into trouble, for various definitions of trouble.

The ML work that goes by the name "region analysis" is very 
ambitious, but I'm not sure if it is there yet.  I don't know
as much about it as I should.

One possible system-level problem with region analysis is that if
it is used in combination with a generational garbage collector,
both the region analysis and the garbage collector are going to
be chasing the same short-lived objects, so the performance
of the system might not be as good as you might hope.  Of course,
not all systems will be built that way.

David Chase