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

[Emanuel Peter]

On Sat, 23 Aug 2025 09:05:10 GMT, Tobias Hotz <duke at openjdk.org> wrote:

>> 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.
>
> Tobias Hotz has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Remove too strict assert from old code path

Looks like a nice idea, thanks for the work!

I started reading through a part of it and have a few questions / suggestions.

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

A more general suggestion (could also be a future RFE):
You could also use the `unsigned` bounds here. And you could also address `UDIvI/L`.

Now that we have unsigned bounds we could use them: https://github.com/openjdk/jdk/pull/17508

You can read up in `type.hpp`, that an integer type has one or two simple intervals.

   708  * 4. Either _lo == jint(_ulo) and _hi == jint(_uhi), or each element of a
   709  *   TypeInt lies in either interval [_lo, jint(_uhi)] or [jint(_ulo), _hi]
   710  *   (note that these intervals are disjoint in this case).

I think with this, you could do an even more powerful optimization.

-----------

Also: where ever I see these optimizations that work on ranges, and not just constants: we should do some more rigorous testing on those resulting ranges.

I see that you already have some concrete examples. It would be good to extend those with a completely randomized version. See for inspiration:

https://github.com/openjdk/jdk/pull/25254/files#diff-0e3d89ac8cf0548b69d9bdb0859380bc31de0a772fa7ff211f446a4a5abd4197R220-R248

src/hotspot/share/opto/divnode.cpp line 508:

> 506: 
> 507: template<typename IntegerType>
> 508: static const IntegerType* compute_generic_div_type(const IntegerType* i1, const IntegerType* i2, int widen) {

Do we need the `generic` in the name? The `template` already suggests that it can be used for different types, right?

Also: I'm wondering if we can somehow extend this for `UDivI` and `UDIvL`.
I suppose you would have to use the `_ulo` and `_uhi` instead of `_lo` and `_hi`.

I'm not saying this all has to be done in this PR, but we could at least anticipate the extension to unsigned division.

src/hotspot/share/opto/divnode.cpp line 532:

> 530:   // Case B: divisor range does NOT span zero.
> 531:   // Here i2 is entirely negative or entirely positive.
> 532:   // Let d_min and d_max be the nonzero endpoints of i2.

Seems you define `d_min` and `d_max` here, but you don't use them anywhere. You should probably use names here that you will use further down.

src/hotspot/share/opto/divnode.cpp line 533:

> 531:   // Here i2 is entirely negative or entirely positive.
> 532:   // Let d_min and d_max be the nonzero endpoints of i2.
> 533:   // Then a/b is monotonic in a and in b (when b keeps the same sign).

I think you should talk about `i1` and `i2`. You have not defined `a` and `b` up to now.

src/hotspot/share/opto/divnode.cpp line 547:

> 545:   // Special overflow case: min_val / (-1) == min_val (cf. JVMS§6.5 idiv/ldiv)
> 546:   // We need to be careful that we never run min_val / (-1) in C++ code, as this overflow is UB there
> 547:   // We also must include min_val in the output if i1->_lo == min_val and i2->_hi.

`if i1->_lo == min_val and i2->_hi` I cannot parse this.
The `if` suggests that there will be a condition following. The `and` confirms that.
Then I see `i1->_lo == min_val` which is a boolean condition. But `i2->_hi` is not.
Ah, did you mean this the condition from below?
Suggestion:

  // We also must include min_val in the output if i1->_lo == min_val and i2->_hi == -1.

src/hotspot/share/opto/divnode.cpp line 552:

> 550:     NativeType new_lo = min_val;
> 551:     NativeType new_hi;
> 552:     // compute new_hi for non-constant divisor and/or dividend.

You suggest we only land here in non-constant cases. Is that true?
What if `i1=min_val` and `i2=-1`?

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

Changes requested by epeter (Reviewer).

PR Review: https://git.openjdk.org/jdk/pull/26143#pullrequestreview-3151213349
PR Review Comment: https://git.openjdk.org/jdk/pull/26143#discussion_r2297964702
PR Review Comment: https://git.openjdk.org/jdk/pull/26143#discussion_r2297970256
PR Review Comment: https://git.openjdk.org/jdk/pull/26143#discussion_r2297971528
PR Review Comment: https://git.openjdk.org/jdk/pull/26143#discussion_r2297986773
PR Review Comment: https://git.openjdk.org/jdk/pull/26143#discussion_r2297995321