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

[Dean Long]

On Mon, 3 May 2021 18:45:07 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!
>
> Vladimir Ivanov has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Cover abstract method case

Looks good.

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

Marked as reviewed by dlong (Reviewer).

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