This is a little OT as it's more about compiler theory/implementation
for any garbage collected language, but my focus is Lisp in
particular. I'm hoping no one here minds.
I'm wondering if anyone here can point out some good papers or books
on methods compiler writers use for detecting short-lived objects or
how a Lisp compiler can decide to put an object on the stack vs.
allocating it from the heap (or if it's speedy enough to just allocate
everything off the stack and copy what's kept later)?
Along the same lines, does anyone have any suggested reading materials
on how this problem changes (simplifies?) for a purely functional
implementation of Lisp?
Thanks in advance!
Jeff M.
> I'm wondering if anyone here can point out some good papers or books
> on methods compiler writers use for detecting short-lived objects or
> how a Lisp compiler can decide to put an object on the stack vs.
> allocating it from the heap (or if it's speedy enough to just allocate
> everything off the stack and copy what's kept later)?
There are a number of approaches for statically determining the extent
of heap objects, but it pretty much boils down to a data flow problem:
an object allocated by a procedure must be allocated on the heap if
the procedure either returns its value, stores its value in a globally-
accessible location, or if it passes its value to any function that
(possibly transitively) does the latter. Like most data-flow problems,
you can make a solution as simple or as complex as you want.
Conservatively, you can assume an object can be stack-allocated only
when its value is not returned, stored in any global variables, or
passed to any other functions. Or, you can be more aggressive and do
context-sensitive, field-sensitive, flow-sensitive, and/or inter-
procedural analysis. The literature on those topics is largely
relevant even when it does not apply to extent analysis specifically.
As for literature, there is a lot on the subject but not much specific
to Lisp. There is one specific to Scheme:
http://www.iro.umontreal.ca/~feeley/papers/icfp96.ps.gz
There is a lot specific to Java. Search Citeseer and the ACM Digital
Library for "Java escape analysis" or "Java heap analysis".
Also see:
http://citeseer.ist.psu.edu/691154.html
On Jun 5, 6:59 pm, "Jeff M." <·······@gmail.com> wrote:
> This is a little OT as it's more about compiler theory/implementation
> for any garbage collected language, but my focus is Lisp in
> particular. I'm hoping no one here minds.
>
> I'm wondering if anyone here can point out some good papers or books
> on methods compiler writers use for detecting short-lived objects or
> how a Lisp compiler can decide to put an object on the stack vs.
> allocating it from the heap (or if it's speedy enough to just allocate
> everything off the stack and copy what's kept later)?
>
> Along the same lines, does anyone have any suggested reading materials
> on how this problem changes (simplifies?) for a purely functional
> implementation of Lisp?
Google (and Google-scholar and Citeseer) for "compile-time garbage
collection". The top results there should help get you started.