Integrated: 8266074: Vtable-based CHA implementation

[Vladimir Ivanov]

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 pull request has now been integrated.

Changeset: 127bfe44
Author:    Vladimir Ivanov <vlivanov at openjdk.org>
URL:       https://git.openjdk.java.net/jdk/commit/127bfe44f7d09f272a08f97bfc5d168eb22474a2
Stats:     557 lines in 11 files changed: 482 ins; 6 del; 69 mod

8266074: Vtable-based CHA implementation

Reviewed-by: kvn, jrose, dlong

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

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