RFR: 8266074: Vtable-based CHA implementation

[John R Rose]

On Tue, 27 Apr 2021 20:15:25 GMT, Vladimir Ivanov <vlivanov at openjdk.org> wrote:

> As of now, Class Hierarchy Analysis (CHA) employs an approximate algorithm to enumerate all non-abstract methods in a class hierarchy.
> 
> It served quite well for many years, but it accumulated significant complexity
> to support different corner cases over time and inevitable evolution of the JVM
> stretched the whole approach way too much (to the point where it become almost
> impossible to extend the analysis any further).
> 
> It turns out the root problem is the decision to reimplement method resolution
> and method selection logic from scratch and to perform it on JVM internal
> representation. It makes it very hard to reason about correctness and the
> implementation becomes sensitive to changes in internal representation.
> 
> So, the main motivation for the redesign is twofold: 
>  * reduce maintenance burden and increase confidence in the code;
>  * unlock some long-awaited enhancements.
> 
> Though I did experiment with relaxing existing constraints (e.g., enable default method support), 
> any possible enhancements are deliberately kept out of scope for the current PR.
> (It does deliver a bit of minor enhancements front as the changes in
> compiler/cha/StrengthReduceInterfaceCall.java manifest, but it's a side effect
> of the other changes and was not the goal of the current work.)
> 
> Proposed implementation (`LinkedConcreteMethodFinder`) mimics method invocation
> and relies on vtable/itable information to detect target method for every
> subclass it visits. It removes all the complexity associated with method
> resolution and method selection logic and leaves only essential logic to prepare for method selection.
> 
> Vtables are filled during class linkage, so new logic doesn't work on not yet linked classed. 
> Instead of supporting not yet linked case, it is simply ignored. It is safe to
> skip them (treat as "effectively non-concrete") since it is guaranteed there
> are no instances created yet. But it requires VM to check dependencies once a
> class is linked.
> 
> I ended up with 2 separate dependency validation passes (when class is loaded
> and when it is linked). To avoid duplicated work, only dependencies
> which may be affected by class initialization state change
> (`unique_concrete_method_4`) are visited. 
> 
> (I experimented with merging passes into a single pass (delay the pass until
> linkage is over), but it severely affected other class-related dependencies and
> relevant optimizations.code.)
> 
> Compiler Interface (CI) is changed to require users to provide complete information about the call site being analyzed.
> 
> Old implementation is kept intact for now (will be removed later) to:
>   - JVMCI hasn't been migrated to the new implementation yet;
>   - enable verification that 2 implementations (old and new) agree on the results;
>   - temporarily keep an option to revert to the original implementation in case any regressions show up.
> 
> Testing:
> - [x] hs-tier1 - hs-tier9
> - [x] hs-tier1 - hs-tier4 w/ `-XX:-UseVtableBasedCHA`
> - [x] performance testing
>   
> Thanks!

This is a major bit of stewardship.  Here's a bit of old history:  The approximate dependencies walk code was hacked in the earliest days, for devirtualization—a new and cool thing back then.  At the same time the vtable code was hacked in, and both sets of logic were hacked until the bugs went away.  It took a while for all of us to fully understand the VM we were building.  (This is why we had to add ACC_SUPER and class loader ~dependencies~ constraints, for example.)   A couple engineers cleaned up the vtable stuff to its present state, and I and others cleaned up the CHA logic to its present state, before you touched it.  It’s great to see those two bodies of code converging; thank you very very much.

Reviewed!

One question, which the review doesn't depend on:  Are get getting closer to being able to apply CHA to interfaces? Unique-implementor and unique-method optimizations on interfaces are important.  I ask because of some comments that throw shade on interfaces in the unit tests.

src/hotspot/share/code/dependencies.cpp line 1521:

> 1519:     selected_method = recv_klass->method_at_itable_or_null(_declaring_klass, _vtable_index,
> 1520:                                                            implements_interface); // out parameter
> 1521:     assert(implements_interface, "not implemented");

Looking at `recv_klass->method_at_itable_or_null`, I wonder if there can be “holes” in the itable for missing methods.  They would lead to `AME` if called.  They might also trigger your assert here:  `assert(implements_interface, "not implemented")`.  Is there some reason that `select_method` cannot possibly encounter a missing method?

Answer to self:  I don't remember whether the JVM creates itable methods on the fly, but I suppose it does, so the code would see an synthetic abstract method.  (Decades ago we named those Miranda Methods because if you don't have a responding method "one will be provided for you".)  And itables are just aliases of vtable slices, so the miranda placed in the vtable will be seen also in the itable.

(Overall comment on this area of the code:  It looks great, much better than when I touched it last.  Thanks!)

-------------

Marked as reviewed by jrose (Reviewer).

PR: https://git.openjdk.java.net/jdk/pull/3727