Stack allocation prototype for C2

[Vladimir Ivanov]

Hi Charlie and Nikola,

> Here is the prototype code for our work on adding stack allocation to the HotSpot C2 compiler. We are looking for any and all feedback
> as we hope to move from a prototype to something that could be contributed. A change of this size is difficult to review so we
> understand the process will be thorough and will take time to complete. Any suggestions on how to allow for collaboration with others,
> if they wanted to, would also be appreciated (i.e., a repo somewhere).
> 
> For a quick refresher here is a link to Nikola’s talk at FOSDEM:
> https://fosdem.org/2020/schedule/event/reducing_gc_times/
> 
> Here is a link to our initial webrev:
> http://cr.openjdk.java.net/~adityam/charlie/stack_alloc/
> 
> Expecting that a change like this will require a JEP, we have prepared a document describing our work based off of the JEP submission
> form. Our document has a few extra sections at the end discussing areas that we are looking for guidance on and some initial
> performance results. This document can be found here:
> https://github.com/microsoft/openjdk-proposals/blob/master/stack_allocation/Stack_Allocation_JEP.md

Very nice write-up and design overview!

   "To implement stack allocation, we need to modify the C2 compiler, 
the GCs and some of the VM runtime interfaces"

 From the design overview and the implementation, I'm concerned about 
far-reaching consequences of the chosen approach. It's not limited just 
to existing set of JVM features, but as Andrew noted will affect the 
design of forthcoming functionality as well.

I think it's worth to start a broad discussion (HotSpot-wide) and decide 
  how much JVM design complexity budged it is worth spending on such an 
optimization.

Personally, I'm not convinced that supporting stack allocated objects in 
the JVM is justified.


As we discussed off-line (right after FOSDEM), I do see the benefits of 
in-memory representation for non-escaping objects: memory aliasing 
(either indeterminate base or indexed access) imposes inherent 
constraints on the escape analysis (both partial and conservative 
approaches suffer from it). Nevertheless, some of the problematic cases 
can be addressed by improving existing approach or introducing a more 
powerful analysis: covering more cases and making the analysis 
control-sensitive should improve the situation.

Also, the alternative approach (called zone-based heap allocation) looks 
very attractive to me. I haven't thought it through, but it looks like 
keeping the objects on the Java heap can save us a lot of complexity on 
the implementation side (more memory available for allocation - not 
necessarily fixed amount, no need to migrate objects from stack to heap, 
GC barriers are unaffected, etc.). For example, reserving a dedicated 
TLAB (or a stack of TLABs?) and do nmethod-scoped allocations from C2 
code looks attractive. It can simplify many aspects of the 
implementation: much more space available, free migration of 
non-escaping objects to heap on deoptimization.


Another idea:

"When dealing with stack allocated objects in loops we need a lifetime 
overlap check."

It doesn't look specific to stack-allocated objects. Non-overlapping 
live ranges can be coalesced the same way for on-heap freshly allocated 
objects. It should get comparable reduction in allocation pressure 
(single allocation per loop vs allocation per iteration) and doesn't 
require stack allocation support at all (as an example [1]).

If such improvements are enabled for non-escaping on-heap objects, how 
much benefit will stack allocation bring on top of that? IMO the 
performance gap should become much narrower.

Best regards,
Vladimir Ivanov

[1]

   MyObject a = new MyObject(x1); // no aliasing: always accessed 
through "a"
   for (...) {
     ...
     a = new MyObject(x2);
     ...
   }
   return a.x;

can be turned into:

   MyObject a = new MyObject(x1);
   for (...) {
     ...
     a.x = x2; // plus, re-initialize other instance fields
     ...
   }
   return a.x;

It can even be extended for escaping objects in some cases (while the 
object is provably not escaped).