jdk 8364766: C2: Improve Value() of DivI and DivL for non-constant inputs

This PR improves the value of interger division nodes. Currently, we only emit a good type if either input is constant. But we can also cover the generic case. It does that by finding the four corners of the division. This is guranteed to find the extrema that we can use for min/max. Some special logic is required for MIN_INT / -1, though, as this is a special case We also need some special logic to handle ranges that cross zero, but in this case, we just need to check for the negative and positive range once. This also cleans up and unifies the code paths for DivINode and DivLNode. I've added some tests to validate the optimization. Without the changes, some of these tests fail.

Progress

[x] 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

Issue

JDK-8364766: C2: Improve Value() of DivI and DivL for non-constant inputs (Enhancement - P4)

Reviewers

Manuel Hässig (@mhaessig - Committer)
Benoît Maillard (@benoitmaillard - Committer) Review applies to bb9151e4
Emanuel Peter (@eme64 - Reviewer)

Reviewing

Using git

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

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

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 26143

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

Using diff file

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

Using Webrev

Link to Webrev Comment

Jul 06 '25 08:07 ichttt

:wave: Welcome back ichttt! 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.

Jul 06 '25 08:07 bridgekeeper[bot]

@ichttt 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:

8364766: C2: Improve Value() of DivI and DivL for non-constant inputs

Reviewed-by: mhaessig, epeter, bmaillard

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 814 new commits pushed to the master branch:

9862f8f0d351448803f8930333d5a7286e6c3565: 8373513: C2: Move ProjNode::other_if_proj() to IfProjNode
39306d7ab901a1d27d9bfd80f04d917b4d17d07f: 8373800: Remove ScopedValueBindingsResolver
5e7ae281326ca306339aaba101d4206dffdb9ca0: 8373677: Clear text HttpServer connection could fail fast if receiving SSL ClientHello
... and 811 more: https://git.openjdk.org/jdk/compare/32697bf652429fa7247047465e365835dfa24b39...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 (@mhaessig, @benoitmaillard, @eme64, @SirYwell) 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).

Jul 06 '25 08:07 openjdk[bot]

@ichttt 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.

Jul 06 '25 08:07 openjdk[bot]

@ichttt This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply issue a /touch or /keepalive command to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!

Aug 03 '25 12:08 bridgekeeper[bot]

Webrevs

Aug 06 '25 19:08 mlbridge[bot]

Testing is all green.

Aug 08 '25 14:08 mhaessig

Thanks for the fast review! The main reason for all the if cases is that min_int / (-1) is undefined behavior in C++, as it overflows. All code has to be careful that this special case can't happen in C++ code, and that's the main motivation behind all the ifs. I've added a comment that describes that. Otherwise, you would be right: Redudant calculations are no problem, min and max would take care of that.

Regarding testing: I only ran tier1 tests on my machine and GHA

Aug 10 '25 12:08 ichttt

The main reason for all the if cases is that min_int / (-1) is undefined behavior in C++, as it overflows. All code has to be careful that this special case can't happen in C++ code, and that's the main motivation behind all the ifs. I've added a comment that describes that. Otherwise, you would be right: Redudant calculations are no problem, min and max would take care of that.

Then I would suggest restructuring the code to express that intent. Reading it currently, gives me the impression that you care about handling the four corners carefully when you really only care about the UB case. The following pseudocode uses ifs to only avoid the corner case. It's only slightly different from your version, but I find it a bit clearer to guess its intent. What do you think?

if i1.lo == MIN_INT && (i2.lo == -1 || i2.hi  == -1) {
    new_lo = MIN_INT
    if i1.hi == MIN_INT { // is_con()
        new_hi = MAX_INT // (MIN_INT + 1) / -1
        return (new_lo, new_hi) // This is already the entire domain, so we can return early
    }
    if i2.lo != i2.hi {
        corner i1.lo, (i2.lo == -1 ? i2.hi : i2.lo) // corner is just shorthand for setting new_lo and new_hi
    }
} else {
    // i1.lo > MIN_INT
    corner i1.lo, i2.lo
    corner i1.lo, i2.hi
}
// i1.hi > MIN_INT because of early return
corner i1.hi, i2.lo
corner i1.hi, i2.hi

Aug 11 '25 07:08 mhaessig

@ichttt This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply issue a /touch or /keepalive command to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!

Sep 22 '25 18:09 bridgekeeper[bot]

@ichttt, are you still working on this? :slightly_smiling_face:

Oct 01 '25 07:10 mhaessig

Thanks for all your reviews! I've adjusted the tests and comments as per your suggestions. Please review again. And sorry for the long delay @mhaessig !

Oct 19 '25 10:10 ichttt

Yeah this sucks, as it stands I do not have enough info to debug this... I noticed that the new types looks wrong if I read the input nodes correctly. It should be min_long / -2, but it is min_long / -1024. I can however not reproduce this locally: grafik I have the same input nodes in this example, but the correct type for the div node here. I've starred at the code now for a bit and I am still not sure what could have caused this. And I am afraid I can't debug without the test case...

Oct 25 '25 13:10 ichttt

@mhaessig I've added some new asserts to try and detect where it went wrong and merged the latest upstream. Can you run the failing test again please?

Oct 30 '25 06:10 ichttt

Thank you @ichttt, I will kick off a run. I have been trying to extract a reproducer for you, but was not able to reproduce the failure again. Perhaps the asserts will help.

Oct 30 '25 07:10 mhaessig

Also, I would suggest that we integrate this only after the branch of the JDK 26 branch on December 4th. This has interactions with a bunch of PRs that are in flight and it would be good to give this some time to bake on mainline before being released.

Nov 28 '25 10:11 mhaessig

@eme64 do you have time to do another review? :)

Dec 15 '25 08:12 ichttt

Thanks everybody! /integrate

Dec 17 '25 17:12 ichttt

@ichttt Your change (at version 313215bb7faa955d5fd5d9e453c2c57b02fdbc21) is now ready to be sponsored by a Committer.

Dec 17 '25 17:12 openjdk[bot]

/sponsor

Dec 18 '25 07:12 mhaessig

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

e67805067a8f537862200e808e20464f12d21c9c: 8367341: C2: apply KnownBits and unsigned bounds to And / Or operations
00050f84d44f3ec23e9c6da52bffd68770010749: 8373502: C2 SuperWord: speculative check uses VPointer variable was pinned after speculative check, leading to bad graph
b4462625413e7c2c12778eaad1f2f21d81f59c52: 8373682: Test compiler/loopopts/superword/TestReinterpretAndCast.java fails on x86_64 with AVX but without f16c
... and 823 more: https://git.openjdk.org/jdk/compare/32697bf652429fa7247047465e365835dfa24b39...master

Your commit was automatically rebased without conflicts.

Dec 18 '25 07:12 openjdk[bot]

@mhaessig @ichttt Pushed as commit 859830694b3db0b81b422bf9b2ce9c7ab9a19a85.

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

Dec 18 '25 07:12 openjdk[bot]