RFR: 8266074: Vtable-based CHA implementation [v2]

[Vladimir Ivanov]

> 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!

Vladimir Ivanov has updated the pull request incrementally with two additional commits since the last revision:

 - Improve comments
 - Use vm.opt.final.UseVtableBasedCHA

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

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/3727/files
  - new: https://git.openjdk.java.net/jdk/pull/3727/files/3063f97d..02f615b2

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=3727&range=01
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=3727&range=00-01

  Stats: 14 lines in 2 files changed: 7 ins; 2 del; 5 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