RFC - Improving C2 Escape Analysis

[John Rose]

I second Mark’s request. The OpenJDK mailing lists
(like this one) and the cr.ojn pages are the official
central stable record of our shared engineering notes
and conversations about how we are evolving our
platform.

(For those few itching to have a side-conversation
about all the gritty process-related reasons why that
is so, I’m not your guy.  But it is so.)

Quick comments:

Thank you.  This is a very good line of research.
It feels good to have other folks in other teams
caring about it.

The paper touched on the factors which limit EA,
notably the path-independent approximation, and
(most of all) the inlining decisions.  I like to
think of the cumulative result of the inlining
decisions (of a particular compile task) as the
“inlining horizon” that the task works within.
Anything that happens inside the horizon can be
represented accurately by the IR of the task.

Anything outside the horizon has to be
characterized with approximations, usually
worst-case approximations.  It matters where
you place the horizon, and what assumptions
you can make on values that come in across
or go out across the horizon.

One think that I like to think about is what are
the “hard cases” that force us to make weak
assumptions about what happens outside the
inlining horizon.  Quantitative corpus analyses
can sometimes be tuned to help us understand
which “hard cases” are preventing optimization.

Characterizing those hard cases is important
because it focuses our attention where to make
changes.  Still more, because we are redefining
Java as we go alone, we can redefine the rules of
Java so that the hard cases get less hard, not
because we are more clever about what we do
inside the horizon (or expanding the horizon)
but because we change the rules in our favor
to limit what can happen outside the horizon.

Valhalla is where those rules change.  Valhalla
is intended to deeply change the results of EA.
Not to make EA unnecessary, by any means,
but rather to focus EA better on some remaining
“hard cases” while allowing EA to

Two (not the only two) of the bad things that can
happen outside of the inlining horizon are field
changes and identity reads.

When a field changes outside the horizon, the
IR has to model the new value somehow.  We
have changed the rules here by introducing final
fields.  In the future we will perhaps tighten the
rules for “trusting” final fields not to change
(some say we don’t need that) and perhaps allow
“frozen arrays” which provably cannot be mutated
even outside an inlining horizon.

Identity reads are nasty little things.  Often you don’t
care about the precise identity of an object, just its
contents.  For example, Integer.valueOf(x) or List.of(x,y)
have an identity, but you are not supposed to depend
on it.  (Don’t rely on `x==y`, use `x.equals(y)`, etc.)

We have written down some rules about value-based
classes[1] which try to tell the programmer how to
stay away from identity reads, but there are no “teeth”
in that document.  As a result, an object which crosses
into or out of an inlining horizon may or may not have
the same identity as any other object crossing the
horizon (if the contents are the same, of course).

[1]: https://docs.oracle.com/javase/8/docs/api/java/lang/doc-files/ValueBased.html 

Valhalla puts teeth into those rules, by defining a robust
type of value-based class which actively obscures its identity.
(As a corollary of that it cannot be used to post side effects
to its fields.  Maybe via fields of mutable objects referred to
by its fields, but not directly in its own fields.)

I expect that your numbers would change greatly if there
were routine use of Valhalla primitive objects wherever
VBC’s are in use today.  There would still be non-primitive
objects passing through the inlining horizon, and it would
still be incrementally profitable to track them and estimate
their behavior, but the profit margin would be elsewhere.

This is what winning looks like, actually:  If we are having
a hard time playing today’s EA game, we turn the tables over
and start a new EA game we can win at.  This can happen
because we don’t just write the JVM optimizer, we also
write the JVM rules.

Here’s a way to model what Valhalla objects can do, relative
to our sense of today’s EA optimizations.  At the IR level,
you can “split” an object (just like you “split” a register
allocation) by recopying it at all uses.  If it were a regular
Java object, you would be breaking its identity up into
a bunch of path-dependent identities.  If there are identity
reads and/or state changes in the “split” object, you have
just broken the user’s program.  But, if you can get away
with it, you have also made your worries disappear about
what can happen over the horizon, because “bad stuff”
happens only to the “split” copies which have disappeared
over the horizon.  The local “split” copies are still sitting
there in your IR graph, undisturbed.

Valhalla allows (even encourages) the optimizer to do this
splitting, routinely and frequently.  Our prototype also
records “souvenirs” of where each split came from, in
case we wish to re-box on the heap; then we can reuse
a souvenir if one is present.  But the canonical form
(apart from the souvenir) is just the tuple of field values,
with no object identity (or header) in sight.

(Headers are, in a sense, where object identity has its
“primary residence”.  The GC uses a header to forward
stateful objects accurately, and the header is also used
to manage identity reads for identityHashCode and
synchronization.)

The design of Valhalla is informed, in part, by our
understanding of the pitfalls of EA, especially with
respect to the inlining horizon.  We are designing
our way out of a trap that prevents us from doing
the EA we wish to do.  Your work will get better
with Valhalla; I hope it can also help us predict
the effects of Valhalla.

— John

On Sep 30, 2021, at 2:03 PM, mark.reinhold at oracle.com wrote:
> 
> 2021/9/30 13:51:32 -0700, divino.cesar at microsoft.com:
>> I've spent the past few weeks investigating the C2 Escape Analysis
>> implementation with the goal of identifying which part(s) of it would benefit
>> the most from a contribution.
>> 
>> As a conclusion to that investigation, I wrote a report where I list the most
>> evident points, accompanied with a _preliminary_ quantitative analysis of how
>> effective the current implementation is for finding opportunities for Scalar
>> Replacement.
>> 
>> ...
>> 
>> Here is the link to the document: 
>> https://gist.github.com/JohnTortugo/c2607821202634a6509ec3c321ebf370
> 
> Thanks for writing this up!
> 
> For IP clarity, could you please post a copy of this document either to
> this mailing list or to your directory on cr.openjdk.java.net [1]?
> 
> - Mark
> 
> 
> [1] https://openjdk.java.net/guide/codeReview.html