RFR: 8266074: Vtable-based CHA implementation

Vladimir Ivanov vlivanov at openjdk.java.net
Thu Apr 29 12:01:14 UTC 2021

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.

- [x] hs-tier1 - hs-tier9
- [x] hs-tier1 - hs-tier4 w/ `-XX:-UseVtableBasedCHA`
- [x] performance testing


Commit messages:
 - Introduce NewKlassDepChange and KlassInitDepChange
 - LinkedConcreteMethodFinder
 - Dependencies::assert_unique_concrete_method
 - 4-arg dependency support: Dependencies::assert_common_4 et al

Changes: https://git.openjdk.java.net/jdk/pull/3727/files
 Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=3727&range=00
  Issue: https://bugs.openjdk.java.net/browse/JDK-8266074
  Stats: 542 lines in 11 files changed: 468 ins; 6 del; 68 mod
  Patch: https://git.openjdk.java.net/jdk/pull/3727.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/3727/head:pull/3727

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

More information about the hotspot-compiler-dev mailing list