RFR: 8266074: Vtable-based CHA implementation

[Vladimir Ivanov]

On Fri, 30 Apr 2021 20:08:39 GMT, John R Rose <jrose 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!
>
> src/hotspot/share/code/dependencies.cpp line 1521:
> 
>> 1519:     selected_method = recv_klass->method_at_itable_or_null(_declaring_klass, _vtable_index,
>> 1520:                                                            implements_interface); // out parameter
>> 1521:     assert(implements_interface, "not implemented");
> 
> Looking at `recv_klass->method_at_itable_or_null`, I wonder if there can be “holes” in the itable for missing methods.  They would lead to `AME` if called.  They might also trigger your assert here:  `assert(implements_interface, "not implemented")`.  Is there some reason that `select_method` cannot possibly encounter a missing method?
> 
> Answer to self:  I don't remember whether the JVM creates itable methods on the fly, but I suppose it does, so the code would see an synthetic abstract method.  (Decades ago we named those Miranda Methods because if you don't have a responding method "one will be provided for you".)  And itables are just aliases of vtable slices, so the miranda placed in the vtable will be seen also in the itable.
> 
> (Overall comment on this area of the code:  It looks great, much better than when I touched it last.  Thanks!)

Regarding "holes" in itables: yes, it happens in practice. `select_method` is allowed to return a `NULL` and it is used by `LinkedConcreteMethodFinder` as a sentinel value for `AME` (when placed in `_found_methods` array). That's why `Dependencies::find_unique_concrete_method()` check `participant(0)`:

   Method* fm = wf.found_method(0);  // Will be NULL if num_parts == 0.
   Klass*   p = wf.participant(0);   // Will be NULL if num_parts == 0.
   ...
   if (Dependencies::is_concrete_method(m, ctxk)) {
     if (fm == NULL && p == NULL) {
       // It turns out that m was always the only implementation.
       fm = m;
     }


Now I think that it's not clear enough from the code. I'll elaborate on it in the additional comments.

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

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