[gclist] Re: gclist-digest V1 #102

[Greg Morrisett]

> I'm looking for information on compiler techniques to do lifetime
> analysis of allocated objects, with a view to replacing calls to a
> general allocator with faster allocation techniques where possible.
> 
> The best case would be if the compiler can prove that an object only has
> local scope, and therefore replace the call to the allocator with stack
> allocation.  Another possibility is that it could generate an explicit
> free of an allocated object, though its less clear that that would have
> dramatic performance improvements.
> 

See the work of Tofte and Talpin on Region Inference.
Basically, region inference uses ML-style type inference
(combined with an effects system) to determine a "region"
that an object is to be placed in.  The regions are
[de-]allocated in a stack-like fashion and their allocation and 
deallocation points can be determined statically.   (Effectively,
you're batching the "free" operation for a bunch of objects
that have the same lifetime.)  The key thing that makes this
work well is that the analysis is polyvariant.  The drawback
is that routines that are polymorphic with respect to the
region in which they allocate must take pointers to these
regions as arguments at run-time and do a bit more work
to allocate an object.  

The original paper appears in the 1995 Proceedings on
Principles of Programming Languages (PoPL).  A more recent
paper by Tofte and Birkedal (1996 PoPL) describes further
analyses used to make region inference a reality.  For
instance, the original paper did not try to infer the sizes
of regions at compile time.  The '96 paper tries to do this --
when it succeeds, regions whose sizes are known statically
can be allocated/de-allocated as usual.  Regions whose
sizes are unknown are dealt with using linked lists of
pages of fixed size.  

I think there was a paper by Aiken and some other folks
at Berkeley in the 1996 Proceedings of Programming Language
Design and Implementation (PLDI) on extending the original Tofte/Talpin 
work to allocate and free regions as late as possible.

> As an aside, this seems to be related to the general case of the problem
> of tail call elimination being discussed on this list.

Well, yes an no.  For "well-behaved" languages, it's possible
to statically determine when a call site is a tail-call.  I
qualify with well-behaved, because C is not well-behaved as
many folks have pointed out.  (You could, for instance, take
an address of a variable allocated on the stack frame and
pass it as an argument to the recursive call.  There are
other problems with C, too.)  

-Greg Morrisett
 jgm@cs.cornell.edu