Re: implementing escape analysis

[Andrew Haley <aph at redhat dot com>]

David Daney writes:
 > Andrew Haley wrote:
 > > Diego Novillo writes:
 > >  > Andrew Haley wrote:
 > >  > 
 > >  > > http://www.research.ibm.com/people/g/gupta/escape.ps
 > >  > > 
 > >  > > But I probably wouldn't recommend you to do it in a gcj-specific way.
 > >  > > gcj is merely the Java language front-end for gcc, and there may be a
 > >  > > plan for escape analysis that will suit all gcc's languages that can
 > >  > > use it.
 > >  > > 
 > >  > Oh, excellent.  It's been in my wish list for a while.  I agree with
 > >  > Andrew, this analysis should not be done in the individual front ends.
 > >  > At worst, I could envision langhooks if we needed to get some
 > >  > FE-specific information.
 > >  > 
 > >  > Choi's paper is a good start.  I remember it being quite reasonable, but
 > >  > I am not aware of recent results in the literature.  We already have
 > >  > some primitive (well, embarrassing) support for determining escape
 > >  > points.  See tree-ssa-alias.c:is_escape_site.
 > > 
 > > I remember the weird thing about that paper (it's been a long time
 > > since I read it) is that it didn't talk much about inheritance.  It
 > > seems to me that inheritance is one of the greatest problems for an
 > > object-oriented language...
 > > 
 > >  > Essentially, a good escape analysis technique should probably be
 > >  > incorporated at that point.  I have not yet thought about the details,
 > >  > but I'd be happy to help with the implementation.
 > > 
 > > In theory it doesn't look all that difficult do do in the simple
 > > cases, but a good implementation would need a lot of knowledge about
 > > the way the class library behaves, and therefore what might escape.  A
 > > database, I suppose.  But just a skeleton implementation that does a
 > > few simple things would be nice.
 > 
 > Is is possible to do a conversion of a heap allocation to a stack 
 > allocation in a language independent manner in GCC?

I think so, yes.  Once you know that a call is to a function that
allocates memory, you then have to be able to determine if that memory
escapes.  As Diego said, you'd might need langhooks for this.

 > I keep threatening to do this for gcj, but was thinking that the best 
 > place to do it may be the front end.  Once in tree-ssa form it is more 
 > difficult to figure out that a call to _Jv_AllocObject followed by a 
 > call to the constructor is the equivalent of the 'new' operator.

We'd perhaps need to annotate trees, but that doesn't seem like a
show-stopper.

 > Also replacing calls to a general purpose type 
 > (StringBuilder/StringBuffer) to an optimized version 
 > (gnu.gcj.runtime.StringBuffer) requires very large changes to the 
 > tree-ssa form, but in the front-end it is quite simple.
 > 
 > The ability to do a good job of both of these transformations has
 > to be based on (at least a simplified form of) escape analysis of
 > the runtime library.

Indeed, yes.  But there's no reason not to start small: if you know
that the args of System.out.println() don't escape, for example, then
you can handle just that.  You don't have to have a total analysis of
all of libgcj.

I agree that doing the job in a langauge-specific way might be a pain
to start with, but it seems like a better plan in the long term.

Andrew.