[gclist] Compiler lifetime analysis

[Paul Haahr]

Jeremy Fitzhardinge wrote
> 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.

Mads Tofte has done some work on what I would call the extreme end of
this approach:  associating every object, at allocation time, with a
stack frame, and deallocating it when that frame exits.  Obviously, the
designated frame can be much earlier in the stack than the one in which
the allocation occurs.

As I remember, the work was done with closed-world analysis of ML
programs, called region analysis, where type signatures are extended
with annotations describing lifetimes of allocated objects.

For details, see Tofte's publications, which generally can be found from
http://www.diku.dk/users/tofte/publ/publ.html.  A couple of the more
relevant sounding titles are:

  A Theory of Stack Allocation in Polymorphically Typed Languages

    http://www.diku.dk/users/tofte/publ/93.15.dvi

  From region inference to von Neumann Machines via region
  representation inference

    http://www.diku.dk/users/tofte/publ/popl96.dvi

I'm not sure how amenable his ideas are to hybrid approaches, but it's
worth looking at them.  Apologies if I'm misrepresenting the ideas;
it's been a while since I thought about this.

Paul