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

[Erik Österlund]

On Thu, 18 Feb 2021 17:05:08 GMT, Vladimir Ivanov <vlivanov 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

It looks like there is a traversal bug lurking here, unless I missed something. Looks great otherwise.

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.

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.

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

Changes requested by eosterlund (Reviewer).

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