RFR: 8261954: Dependencies: Improve iteration over class hierarchy under context class

[Vladimir Ivanov]

On Fri, 19 Feb 2021 13:52:35 GMT, Erik Österlund <eosterlund at openjdk.org> wrote:

>> Simplify `ClassHierarchyWalker::find_witness_anywhere()` which iterates over class hierarchy under context class searching for witnesses.
>> 
>> Current implementation traverses the hierarchy in a breadth-first manner and keeps a stack-allocated array to keep a worklist.
>> But all the subclasses are already part of a singly linked list formed by `Klass::subklass()`/`next_sibling()`/`superklass()`.
>> 
>> Proposed refactoring gets rid of the explicit worklist and switches to the traversal over the linked list (encapsulated into `ClassHierarchyIterator`). It performs depth-first pre-order hierarchy traversal. 
>> 
>> (There are some other minor refactorings applied in `ClassHierarchyWalker` along the way.) 
>> 
>> Testing:
>> - [x] hs-tier1 - hs-tier8
>> - [x] additional verification that CHA decisions aren't affected
>
> src/hotspot/share/oops/instanceKlass.hpp line 1461:
> 
>> 1459:     if (_visit_subclasses && _current->subklass() != NULL) {
>> 1460:       _current = _current->subklass();
>> 1461:       return; // visit next subclass
> 
> _visit_subclasses is initially true in the constructor. That seems to imply that after the first call to next(), we will take this path, just returning the subklass() without walking the siblings. The _visit_subclasses variable is never mutated away from the true state at all if it was already true, until we get to the bottom of the class hierarchy. That seems to imply that the next() iterator won't visit any siblings at all until we get to the bottom of the class hierarchy, essentially breaking the DFS traversal. Therefore, it looks to me like the use of the _visit_subclasses variable needs to be looked over a bit in this function in general, unless I misunderstood something.

`_visit_subclasses` is mutated only from the outside (there's `ClassHierarchyIterator::skip_subclasses()` specificlaly for that) when user code needs to ignore subclasses:

https://github.com/openjdk/jdk/blob/ae78e51e4248c2ccfa73c772fb1db1baad2c2903/src/hotspot/share/code/dependencies.cpp#L1359:

  for (ClassHierarchyIterator iter(context_type); !iter.done(); iter.next()) {
    Klass* sub = iter.klass();

    // Do not report participant types.
    if (is_participant(sub)) {
      // Walk beneath a participant only when it doesn't hide witnesses.
      if (participants_hide_witnesses) {
        iter.skip_subclasses();
      }

And `_visit_subclasses` is cleared to the initial state on the very next call to `next()`.

> That seems to imply that the next() iterator won't visit any siblings at all until we get to the bottom of the class hierarchy, essentially breaking the DFS traversal.

Yes, that's the intended behavior. Why do think it doesn't obey depth-first order? `next_sibling()` points to a class on the same level of class hierarchy.

> src/hotspot/share/oops/instanceKlass.hpp line 1457:
> 
>> 1455:   // Make a step iterating over the class hierarchy under the root class.
>> 1456:   // Skips subclasses if requested.
>> 1457:   void next() {
> 
> Since this method is a bit involved, I think it might want to move to the cpp file.

Good point.

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

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