RFR: 8359602: VerifyIterativeGVN fails with assert(!VerifyHashTableKeys || _hash_lock == 0) failed: remove node from hash table before modifying it

Benoît Maillard bmaillard at openjdk.org
Mon Jun 30 08:42:57 UTC 2025


This PR prevents some missed ideal optimizations in IGVN by notifying users of type refinements made during CCP, addressing a missed optimization that caused a verification failure with `-XX:VerifyIterativeGVN=1110`.

### Context
During the compilation of the input program (obtained from the fuzzer, then simplified and added as a test) by C2, we end up with node `591 ModI` that takes `138 Phi` as its divisor input. An existing `Ideal` optimization is to get rid of the control input of a `ModINode` when we can prove that the divisor is never `0`.

In this specific case, the type of the `PhiNode` gets refined during CCP, but the refinement fails to propagate to its users for the IGVN phase and the ideal optimization for the `ModINode` never happens. This results in a missed optimization and hits an assert in the verification phase of IGVN (when using `-XX:VerifyIterativeGVN=1110`).

![IGV screenshot](https://github.com/user-attachments/assets/5dee1ae6-9146-4115-922d-df33b7ccbd37)

### Detailed Analysis

In `PhaseCCP::analyze`, we call `Value` for the `PhiNode`, which  
results in a type refinement: the range gets restricted to `int:-13957..-1191`.

```c++
  // Pull from worklist; compute new value; push changes out.
  // This loop is the meat of CCP.
  while (worklist.size() != 0) {
    Node* n = fetch_next_node(worklist);
    DEBUG_ONLY(worklist_verify.push(n);)
    if (n->is_SafePoint()) {
      // Make sure safepoints are processed by PhaseCCP::transform even if they are
      // not reachable from the bottom. Otherwise, infinite loops would be removed.
      _root_and_safepoints.push(n);
    }
    const Type* new_type = n->Value(this);
    if (new_type != type(n)) {
      DEBUG_ONLY(verify_type(n, new_type, type(n));)
      dump_type_and_node(n, new_type);
      set_type(n, new_type);
      push_child_nodes_to_worklist(worklist, n);
    }
    if (KillPathsReachableByDeadTypeNode && n->is_Type() && new_type == Type::TOP) {
      // Keep track of Type nodes to kill CFG paths that use Type
      // nodes that become dead.
      _maybe_top_type_nodes.push(n);
    }
  }
  DEBUG_ONLY(verify_analyze(worklist_verify);)


At the end of `PhaseCCP::analyze`, we obtain the following types in the side table:
- `int` for node `591` (`ModINode`)
- `int:-13957..-1191` for node `138` (`PhiNode`)

If we call `find_node(138)->bottom_type()`, we get:
- `int` for both nodes

There is no progress on the type of `ModINode` during CCP, because `ModINode::Value`  
is not able to refine the type in this case.

Then, in `PhaseCCP::transform_once`, nodes get added to the worklist  
based on the progress made in `PhaseCCP::analyze`.

The type from the side table is compared to the one returned  
by `n->bottom_type()`:
- For the `PhiNode`, this is the `_type` field for `TypeNode`
- For the `ModINode`, this is always `TypeInt::INT`

If these types are not equal for a given node, the node gets added to the IGVN worklist  
for later processing.

```c++
  // If x is a TypeNode, capture any more-precise type permanently into Node
  if (t != n->bottom_type()) {
    hash_delete(n);             // changing bottom type may force a rehash
    n->raise_bottom_type(t);
    _worklist.push(n);          // n re-enters the hash table via the worklist
  }


Because `Value` was able to refine the type for the `PhiNode` but not for the  
`ModINode`, only the `PhiNode` gets added to the IGVN worklist.

The `n->raise_bottom_type(t)` call also has the effect that the `_type` field is  
set for the `PhiNode`.

At the end of CCP, the `PhiNode` is in the worklist, but the `ModINode` is not.

An IGVN phase takes place after CCP. In `PhaseIterGVN::optimize`, we pop nodes  
from the worklist and apply ideal, value, and identity optimizations.  
If any of these lead to progress on a given node, the users of the node get added  
to the worklist.

For the `PhiNode`, however, no progress can be made at this phase (the type was  
already refined to the maximum during CCP).

As a result, the `ModINode` never makes it to the worklist and `ModINode::Value`  
is never called. Before returning from `PhaseIterGVN::optimize`,  
we run the verifications with `PhaseIterGVN::verify_optimize`. There,  
we call `Value` on the `ModINode` to attempt to optimize further.

In `ModINode::Ideal`, we check the type of the divisor and get rid of the  
control input if we can prove that the divisor can never be `0`:

```c++
  // Check for useless control input
  // Check for excluding mod-zero case
  if (in(0) && (ti->_hi < 0 || ti->_lo > 0)) {
    set_req(0, nullptr);        // Yank control input
    return this;
  }


Because the type range of the `PhiNode` was refined during CCP to  
`int:-13957..-1191`, the condition evaluates to `true`, and the node  
gets modified with `set_req(0, nullptr)`. Since an optimization is not expected  
to take place during verification, the assert gets triggered.

In summary, this optimization is missed because it is an `Ideal` optimization  
that depends on the type of the input, and because that type changes during CCP,  
right before the IGVN phase. Since there is no direct notification from the input  
to its users in CCP when the type changes, the optimization never gets triggered.

### Proposed Fix
There currently exists no mechanism to propagate a type update in CCP to an ideal optimization in IGVN. In many cases, a type refinement on the input will propagate to the type of the users, but it is not the case when no value optimization is available for the user. This can happen with a `ModINode`, but could probably also happen in other scenarios.

The proposed fix is simply to notify users by adding them to the IGVN worklist when a type refinement happens in CCP. We simply add a call to `add_users_to_worklist(n)` in `PhaseCCP::transform_once`:

```c++
  // If x is a TypeNode, capture any more-precise type permanently into Node
  if (t != n->bottom_type()) {
    hash_delete(n);             // changing bottom type may force a rehash
    n->raise_bottom_type(t);
    _worklist.push(n);          // n re-enters the hash table via the worklist
    add_users_to_worklist(n);   // if ideal or identity optimizations depend on the input type, users need to be notified
  }


### Testing
- [x] [GitHub Actions](https://github.com/benoitmaillard/jdk/actions?query=branch%3AJDK-8359602)
- [x] tier1-3, plus some internal testing
- [x] Added (modified) test from the fuzzer with `-XX:VerifyIterativeGVN=1110` to make sure the optimization is not missed anymore 
- [x] Manual testing with `-XX:+CITime` flag to make sure compilation time does not increase

Thank you for reviewing!

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

Commit messages:
 - 8359602: add comment
 - 8359602: add test summary and comments
 - 8359602: tag requires vm.debug == true
 - 8359602: Add test from fuzzer
 - 8359602: Add users to IGVN worklist when type is refined in CCP

Changes: https://git.openjdk.org/jdk/pull/26017/files
  Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=26017&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8359602
  Stats: 62 lines in 2 files changed: 62 ins; 0 del; 0 mod
  Patch: https://git.openjdk.org/jdk/pull/26017.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/26017/head:pull/26017

PR: https://git.openjdk.org/jdk/pull/26017


More information about the hotspot-compiler-dev mailing list