implementing escape analysis

[Andrew Haley]

Paul Biggar writes:
 > On Thu, 2006-02-16 at 09:44 -0800, David Daney wrote:
 > > 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.
 > 
 > > Is is possible to do a conversion of a heap allocation to a stack 
 > > allocation in a language independent manner in GCC?
 > 
 > Presumably there are two parts, identifying thread local variables, and
 > identifying method local variables. The first relies on the second. 

Right.  If a variable doesn't escape the local context, it doesn't
escape the thread either.

 > Is there a point in looking for thread local variables in a language
 > independent manner. There's more than 1 thread library which could be
 > used in non-java,

Do you care about anything other than POSIX threads?  Even the
embedded thread libraries often map fairly well onto POSIX semantics.

 > and its not clear to me that the theory extends very well. This
 > would point at doing it in the gcj front end (presuming that that's
 > a good place to remove synchronization?).

Synchronization is merely a pair of calls to get() and release().
Removing them, once you've found out that they can be removed, is no
big thing.

 > If this was done in the front end, it would require the results of
 > the method local analysis to be available in the front-end as
 > well. (The method local analysis may also have to go elsewhere). It
 > seems other java specific optimizations would require these
 > results, again in the front-end.
 > 
 > Its not clear to me how complicated it would be to convert heap
 > allocation in a language independent way.
 > 
 > Since the analyses seem to be required in the front-end anyway,
 > perhaps the easiest thing is to start by doing a front-end only
 > job, then seeing whether the same techniques can be applied later
 > on. Does that sound like a good approach?

The thing is that the tree optimizers have already done quite a lot of
the heavy lifting.  Consider control flow graphs, for example.  You
haven't got them in the front end.  Do you do all that work again?

I agree that representing things like inheritance and method
invocation in the tree-SSA form would be a pain, whereas the Java
front end already has these.  However, I fear that we may
unfortunately lower many constructs too early to be of use, so you'd
be forced to annotate calls with "this is a method call to foo.bar"
anyway.

Andrew.