[gclist] live variable analysis

[Eliot Moss]

In answer to David Chase's question about the analysis we did ....

Since it is my understanding that the general content of our "live variable
analysis for Java gc" paper has been approved and the legal issues revolve
around use of the trademarked word "Java", I will go ahead and describe the
analysis in a little more detail.

We considered an analysis that operates over Java byte codes, for use in a
byte code interpreter. Things would obviously need to be extended if one was
generating optimized native code after the byte codes, etc.

The analysis was a straightforward live-variable analysis, such as would come
right out of a textbook on data flow analysis techniques. We did need to
propagate liveness from variable to variable through the push/pop stack
temporaries. Any input to a byte code that does something other than just
copying data is considered live, even if the result is dead. All values stored
into heap objects are considered live, as are all values passed in method
calls. For the really fine details, you'll need to talk with Ole (Agesen) and
David (Detlefs), who did the REAL work!

One of the interesting cases is when a reference is passed in the method call,
and that use is the last use of the reference in the caller. In this case we
insure that the reference is marked dead in the caller, and if it becomes dead
in the callee and a gc occurs, then the reference object will not be retain
(unless otherwise reachable, of course). This is an example of a variable
going dead that the user cannot "fix" by assigning null (Ole or Dave noticed
this, and I think it really strengthens the case for automated analyses).

Until the paper is released I don't want to get too much into discussing
quantitaive results or measurement methodology, since you deserve to be able
to see the paper for that. However, every program that gc'ed showed some
improvement (reduction in heap size), and the geometric mean improvement for
our selected benchmarks was 7-8%, excluding one program that showed 66%
reduction in time-space product.

Regards to you all ---					Eliot Moss
============================================================================
J. Eliot B. Moss, Associate Professor      http://www.cs.umass.edu/~moss Web
Computer Science Department, LGRC          +1-413-545-4206             voice
University of Massachusetts, Box 34610     +1-413-545-1249               fax
Amherst MA  01003-4610  USA                moss@cs.umass.edu           email
============================================================================