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`).

### 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