jdk 8359602: Add users to IGVN worklist when type is refined in CCP

Context

During the compilation of the input program, we end up with node 591 ModI that takes 138 Phi as its divisor input. Because we are able to prove that the value of the phi node can never be 0, we would like to get rid of the control input of the modulo node as an optimization.

IGV screenshot

Detailed description

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

  // 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);)

(The role of PhaseCCP::analyze is basically to populate the side table;
at the beginning, everything is TOP.)

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, because ModINode::Value
does not reduce the type.

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.

  // 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, in debug mode,
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:

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

TODO

Progress

[ ] Change must be properly reviewed (1 review required, with at least 1 Reviewer)
[x] Change must not contain extraneous whitespace
[x] Commit message must refer to an issue

Integration blocker

⚠️ Title mismatch between PR and JBS for issue JDK-8359602

Issue

JDK-8359602: VerifyIterativeGVN fails with assert(!VerifyHashTableKeys || _hash_lock == 0) failed: remove node from hash table before modifying it (Bug - P4) ⚠️ Title mismatch between PR and JBS.

Reviewing

Using git

Checkout this PR locally:
$ git fetch https://git.openjdk.org/jdk.git pull/26017/head:pull/26017
$ git checkout pull/26017

Update a local copy of the PR:
$ git checkout pull/26017
$ git pull https://git.openjdk.org/jdk.git pull/26017/head

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 26017

View PR using the GUI difftool:
$ git pr show -t 26017

Using diff file

Download this PR as a diff file:
https://git.openjdk.org/jdk/pull/26017.diff

Jun 27 '25 10:06 benoitmaillard

:wave: Welcome back bmaillard! A progress list of the required criteria for merging this PR into master will be added to the body of your pull request. There are additional pull request commands available for use with this pull request.

Jun 27 '25 11:06 bridgekeeper[bot]

@benoitmaillard This change now passes all automated pre-integration checks.

ℹ️ This project also has non-automated pre-integration requirements. Please see the file CONTRIBUTING.md for details.

After integration, the commit message for the final commit will be:

8359602: Ideal optimizations depending on input type are missed because of missing notification mechanism from CCP

Reviewed-by: epeter, thartmann

You can use pull request commands such as /summary, /contributor and /issue to adjust it as needed.

At the time when this comment was updated there had been 35 new commits pushed to the master branch:

6c9236c80c236487a7c37dcb947c0f9192322208: 8361238: G1 tries to get CPU info from terminated threads at shutdown
1926aeb1a3b39cf2e4ea48f4c489cd023b5aa77d: 8352016: Improve java/lang/RuntimeTests/RuntimeExitLogTest.java
74822ce12acaf9816aa49b75ab5817ced3710776: 8358183: [JVMCI] crash accessing nmethod::jvmci_name in CodeCache::aggregate
... and 32 more: https://git.openjdk.org/jdk/compare/cd6caedd0a3c9ebd4c8c57e64f62b60161c5cd7c...master

As there are no conflicts, your changes will automatically be rebased on top of these commits when integrating. If you prefer to avoid this automatic rebasing, please check the documentation for the /integrate command for further details.

As you do not have Committer status in this project an existing Committer must agree to sponsor your change. Possible candidates are the reviewers of this PR (@marc-chevalier, @TobiHartmann, @eme64) but any other Committer may sponsor as well.

➡️ To flag this PR as ready for integration with the above commit message, type /integrate in a new comment. (Afterwards, your sponsor types /sponsor in a new comment to perform the integration).

Jun 27 '25 11:06 openjdk[bot]

@benoitmaillard The following label will be automatically applied to this pull request:

hotspot-compiler

When this pull request is ready to be reviewed, an "RFR" email will be sent to the corresponding mailing list. If you would like to change these labels, use the /label pull request command.

Jun 27 '25 11:06 openjdk[bot]

Webrevs

Jun 30 '25 08:06 mlbridge[bot]

@benoitmaillard Very nice work, and great description :)

Did you check if this allows enabling any of the other disabled verifications from JDK-8347273?

That may be a lot of work. Not sure if it is worth checking all of them now. @TobiHartmann how much should he invest in this now? An alternative is just tackling all the other cases later. What do you think?

@benoitmaillard One more open question for me: raise_bottom_type only sets the node internal _type. But in IGVN, we do not read from _type but phase->type(in(2)). Do you know when the phase->type(in(2)) value changes? Is that also during CCP? Before or after the _type is modified?

Jun 30 '25 13:06 eme64

@benoitmaillard Very nice work, and great description :)

Thank you! @eme64

Did you check if this allows enabling any of the other disabled verifications from JDK-8347273?

That may be a lot of work. Not sure if it is worth checking all of them now. @TobiHartmann how much should he invest in this now? An alternative is just tackling all the other cases later. What do you think?

I have started to take a look at this and it seems that there are a lot of cases to check indeed.

@benoitmaillard One more open question for me: raise_bottom_type only sets the node internal _type. But in IGVN, we do not read from _type but phase->type(in(2)). Do you know when the phase->type(in(2)) value changes? Is that also during CCP? Before or after the _type is modified?

Yes, good point, I should I have mentioned this somewhere. The phase->type(in(2)) call uses the type array from PhaseValues. The type array entry is actually modified earlier, in PhaseCCP::analyze, right after the Value call. You can see the set_type call here. When this happens, users are added to the (local) worklist but again it does not change our issue as only value optimizations occur in that context.

Jul 01 '25 07:07 benoitmaillard

@benoitmaillard One more open question for me: raise_bottom_type only sets the node internal _type. But in IGVN, we do not read from _type but phase->type(in(2)). Do you know when the phase->type(in(2)) value changes? Is that also during CCP? Before or after the _type is modified?

Yes, good point, I should I have mentioned this somewhere. The phase->type(in(2)) call uses the type array from PhaseValues. The type array entry is actually modified earlier, in PhaseCCP::analyze, right after the Value call. You can see the set_type call here. When this happens, users are added to the (local) worklist but again it does not change our issue as only value optimizations occur in that context.

Thanks for the explanation! So it seems that CCP and IGVN share the type array, right? Ah yes, it is the Compile::_types:

   461   // Shared type array for GVN, IGVN and CCP. It maps node idx -> Type*. 
   462   Type_Array*           _types;

If the value behind phase->type(in(2)) (the type array entry) is modified in PhaseCCP::analyze, right after the Value call, then why not do the notification there? If we did that, we would do more notification than what you now proposed (to do the notification in PhaseCCP::transform_once on the nodes that have a type that is different than the bottom_type). Are we possibly missing any important case with your approach now? Probably not, I would argue: with your approach we still notify for all live nodes that have a modified type, or are replaced with a constant. If we notified after every type update in PhaseCCP::analyze, we might notify for nodes multiple times, and we would also notify for nodes that are dead after CCP - both are unnecessary overheads. Alright, I just wanted to think this through - but it seems your approach is good :)

Jul 01 '25 11:07 eme64

@benoitmaillard One more open question for me: raise_bottom_type only sets the node internal _type. But in IGVN, we do not read from _type but phase->type(in(2)). Do you know when the phase->type(in(2)) value changes? Is that also during CCP? Before or after the _type is modified?

Yes, good point, I should I have mentioned this somewhere. The phase->type(in(2)) call uses the type array from PhaseValues. The type array entry is actually modified earlier, in PhaseCCP::analyze, right after the Value call. You can see the set_type call here. When this happens, users are added to the (local) worklist but again it does not change our issue as only value optimizations occur in that context.

Thanks for the explanation! So it seems that CCP and IGVN share the type array, right? Ah yes, it is the Compile::_types:
   461   // Shared type array for GVN, IGVN and CCP. It maps node idx -> Type*. 
   462   Type_Array*           _types;
If the value behind phase->type(in(2)) (the type array entry) is modified in PhaseCCP::analyze, right after the Value call, then why not do the notification there? If we did that, we would do more notification than what you now proposed (to do the notification in PhaseCCP::transform_once on the nodes that have a type that is different than the bottom_type). Are we possibly missing any important case with your approach now? Probably not, I would argue: with your approach we still notify for all live nodes that have a modified type, or are replaced with a constant. If we notified after every type update in PhaseCCP::analyze, we might notify for nodes multiple times, and we would also notify for nodes that are dead after CCP - both are unnecessary overheads. Alright, I just wanted to think this through - but it seems your approach is good :)

I also considered doing it there in PhaseCCP::analyze, but I reached the same conclusion. Thanks for your help!

Jul 01 '25 13:07 benoitmaillard

@benoitmaillard Please do not rebase or force-push to an active PR as it invalidates existing review comments. Note for future reference, the bots always squash all changes into a single commit automatically as part of the integration. See OpenJDK Developers’ Guide for more information.

Jul 02 '25 07:07 openjdk[bot]

@TobiHartmann how much should he invest in this now? An alternative is just tackling all the other cases later. What do you think?

Yes, agreed. Let's handle this later.

(Sorry, somehow I thought I had replied to this already - must have missed pressing the Comment button..)

Jul 02 '25 07:07 TobiHartmann

/integrate

Jul 03 '25 07:07 benoitmaillard

@benoitmaillard Your change (at version a66d3fb492541a17e28b3e0fe0f60080c14bdc2c) is now ready to be sponsored by a Committer.

Jul 03 '25 07:07 openjdk[bot]

/sponsor

Jul 03 '25 07:07 eme64

Going to push as commit c75df634be9a0073fa246d42e5c362a09f1734f3. Since your change was applied there have been 36 commits pushed to the master branch:

fd13e1ce9805a903ab60ad9b476eb5a6687d22ee: 8358801: javac produces class that does not pass verifier.
6c9236c80c236487a7c37dcb947c0f9192322208: 8361238: G1 tries to get CPU info from terminated threads at shutdown
1926aeb1a3b39cf2e4ea48f4c489cd023b5aa77d: 8352016: Improve java/lang/RuntimeTests/RuntimeExitLogTest.java
... and 33 more: https://git.openjdk.org/jdk/compare/cd6caedd0a3c9ebd4c8c57e64f62b60161c5cd7c...master

Your commit was automatically rebased without conflicts.

Jul 03 '25 07:07 openjdk[bot]

@eme64 @benoitmaillard Pushed as commit c75df634be9a0073fa246d42e5c362a09f1734f3.

:bulb: You may see a message that your pull request was closed with unmerged commits. This can be safely ignored.

Jul 03 '25 07:07 openjdk[bot]