Escape Analysis and Stack Allocation

[Vladimir Kozlov]

Hi Benedict,

Thank you for your detailed analysis.

You did not point the paper you are referencing. I assume it is "Escape Analysis in the Context of Dynamic Compilation 
and Deoptimization" from Linz. Note, the implementation described in the paper was done for Client compiler (C1). In 
production Hotspot Server compiler (C2) we use only "Interprocedural Analysis" from that work (code in 
bcEscapeAnalyzer). The escape analysis for compiled method in C2 (escape.cpp) is based on different paper: "Escape 
Analysis for Java" [Choi99].

There is big difference how "Interprocedural Analysis" is used in C2. In the first paper "the interprocedural analysis 
supports the compiler in inlining decisions". In current implementation in C2 it is only used to determine the GLOBAL 
escaping state of arguments passed to non-inlined methods. The escape state of arguments is already ArgEscape since we 
have to pass parameters to a call in generated code.

I agree that current usage of interprocedural analysis is too conservative and we could modify code in bcEscapeAnalyzer 
to serve better for C2.

About set_method_escape(). You are right, it is used to indicate that we need to keep pointer to object and can't scalar 
replace it. In current implementation the only important case is the load from an object fields or from an object array. 
This information is used in escape.cpp to indicate that fields or array elements can globally escape: 
set_fields_escape_state. I agree that using set_method_escape() for stores into primitive arrays is useless but it is 
harmless. But we should not do that for stores into object arrays or into field because the store does not modify the 
state of objects in array or in field. And, yes, it is inconsistent with putfield code which does use set_method_escape().

About set_global_escape() for an object stored into an array or a field. The Interprocedural analysis is done using only 
one pass over bytecode. We don't know if the array or the object into which we store will globally escape later. We 
conservatively assume it does escape. The code doesn't keep a record which object is stored into which array (or field), 
so we can't adjust its state after analysis is finished.

I agree that functions names are confusing and not always reflect the meaning.

I filed RFE: "Improve Inter-procedural Escape Analysis" to cleanup bcEscapeAnalyzer:

https://bugs.openjdk.java.net/browse/JDK-8032761

Currently C2 does not allocate non-escaped objects on native stack. Such objects are still allocated in java heap. We 
only remove locks for such objects. Allocation on stack would require significant changes in JIT code and especially in 
GC. Currently GC only supports java objects in CONTINUES java heap. Note, allocation in java heap is very fast (pointer 
arithmetic) so stack allocation will not help to throughput performance. It may only help to reduce frequency of GC. But 
GC time may increase since GC have to do special casing for stack allocated objects.

But it would be interesting to see an actual data from a research anyway.

Regards,
Vladimir

On 1/25/14 10:04 PM, Benedict Elliott Smith wrote:
> Hi,
>
> I was digging into some (to me) unexpected behaviour of escape analysis,
> namely that some references that clearly weren't escaping, and easily
> determined to be so, were not being stack allocated.
>
> So, after some digging through the hotspot code, I discovered some things
> that were probably obvious to everyone on this list, but also some things
> I'm still a little perplexed about. I was hoping somebody could enlighten
> me about the latter.
>
> 1) I cannot see a reason why stores to a primitive array, for instance,
> should cause the argument to escape in bcEscapeAnalyser.cpp
> *iterate_one_block()*; most interestingly, a store to an object array does
> not result in this, which seems incongruous;
>
> 2) An object array store *does* however result in *set_global_escape()* for
> the value being stored, which makes sense, except that this should only be
> *set_method_escape()*, as per the paper, in the case where the target array
> is one of the method arguments. This seems to be missing, here and for
> *putfield*.
>
> Some other weird ones are *arraylength*, *getfield*, *ifnonnull*, etc. The
> fact that these all result in *set_method_escape()*, and that *putfield*and
> *aastore* don't optimise *set_global_escape()* to
> *set_method_escape()*where possible, seem to point to the conclusion
> that *_is_arg_stack
> / set_method_escape()* actually encode only *!is_scalar_replaceable*. Is
> this the case? If so, why the confusing name?*
>
>
> Which leads to a much trickier but more interesting question, which is:
> what are the barriers to performing actual stack allocation of full
> objects, instead of scalar replacement? It is something I would be keen to
> investigate, but given my lack of familiarity with the codebase, it would
> be immensely helpful to hear what the major difficulties / showstoppers
> might be before trying to attack it.
>
> Thanks in advance,
>
> Benedict
>
>
> *I do note that in escape.cpp *ArgEscape* is defined and is explicitly
> overloaded to include some of the characteristics of *is_scalar_replaceable*.
> However the *is_arg_stack()* method is commented with "The given argument
> escapes the callee, but does not become globally reachable." which seems to
> correspond to *ArgEscape* in the paper, but only *invoke()* seems to follow
> the spec, when invoking a method that cannot be analysed, and this would
> also be true for *!is_scalar_replaceable.*
>