RFR: 8266074: Vtable-based CHA implementation

[Vladimir Kozlov]

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!

In general looks good. I have few comments.

src/hotspot/share/code/dependencies.hpp line 138:

> 136:     // than {M1}.
> 137:     unique_concrete_method_2, // one unique concrete method under CX
> 138:     unique_concrete_method_4, // one unique concrete method under CX

Needs comment to distinguish from `unique_concrete_method_2`.

test/hotspot/jtreg/compiler/cha/StrengthReduceInterfaceCall.java line 35:

> 33:  *
> 34:  * @run main/othervm -Xbootclasspath/a:. -XX:+IgnoreUnrecognizedVMOptions -XX:+UnlockDiagnosticVMOptions
> 35:  *                   -XX:+UseVtableBasedCHA

`UseVtableBasedCHA` is `true` by default. May be duplicate these `runs` for both cases: on and off.

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

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