RFR: 8282365: Optimize divideUnsigned and remainderUnsigned for constants [v8]

[John R Rose]

On Mon, 3 Oct 2022 16:12:37 GMT, Quan Anh Mai <qamai at openjdk.org> wrote:

>> This patch implements idealisation for unsigned divisions to change a division by a constant into a series of multiplication and shift. I also change the idealisation of `DivI` to get a more efficient series when the magic constant overflows an int32.
>> 
>> In general, the idea behind a signed division transformation is that for a positive constant `d`, we would need to find constants `c` and `m` so that:
>> 
>>     floor(x / d) = floor(x * c / 2**m) for 0 < x < 2**(N - 1) (1)
>>     ceil(x / d) = floor(x * c / 2**m) + 1 for -2**(N - 1) <= x < 0 (2)
>> 
>> The implementation in the original book takes into consideration that the machine may not be able to perform the full multiplication `x * c`, so the constant overflow and we need to add back the dividend as in `DivLNode::Ideal` cases. However, for int32 division, `x * c` cannot overflow an int64. As a result, it is always feasible to just calculate the product and shift the result.
>> 
>> For unsigned multiplication, the situation is somewhat trickier because the condition needs to be twice as strong (the condition (1) and (2) above are mostly the same). This results in the magic constant `c` calculated based on the method presented in Hacker's Delight by Henry S. Warren, Jr. may overflow an uintN. For int division, we can depend on the theorem devised by Arch D. Robison in N-Bit Unsigned Division Via N-Bit Multiply-Add, which states that there exists either:
>> 
>>     c1 in uint32 and m1, such that floor(x / d) = floor(x * c1 / 2**m1) for 0 < x < 2**32 (3)
>>     c2 in uint32 and m2, such that floor(x / d) = floor((x + 1) * c2 / 2**m2) for 0 < x < 2**32 (4)
>> 
>> which means that either `x * c1` never overflows an uint64 or `(x + 1) * c2` never overflows an uint64. And we can perform a full multiplication.
>> 
>> For longs, there is no way to do a full multiplication so we do some basic transformations to achieve a computable formula. The details I have written as comments in the overflow case.
>> 
>> More tests are added to cover the possible patterns.
>> 
>> Please take a look and have some reviews. Thank you very much.
>
> Quan Anh Mai has updated the pull request incrementally with one additional commit since the last revision:
> 
>   limit tests

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

> 50: // minor type name and parameter changes.
> 51: 
> 52: static void magic_int_divide_constants(jint d, jlong &M, jint &s) {

I would prefer to see a strategy for applying gtest to these magic* functions (all of them, I think that's six).

One way to go about it would simply make them extern and write the gtests accordingly.

That would make me much happier than seeing tests for 7, 13, and a couple other constants!

An example of what I mean by using gtest is in the fix for JDK-8291649 which also applied to C2 constant folding logic.

I think we need this kind of test for any non-trivial constant folding or strength reduction logic, at least moving forward.

If the static magic functions were moved into a header file (not required but surely the high road here) I'd call it javaArithmetic.hpp.  And I'd consider moving java_add etc into there as well.  Alternatively, the static magic functions could be moved into globalDefinitions.hpp which is surprising but perhaps less disruptive than making a new header file for Java arithmetic but not factoring in the existing functions.  I don't recommend making a header file just for this particular algorithm all by itself; I'd rather lump more "stuff" into a single header file.

(I mildly disagree with  count_leading_zeros and count_trailing_zeroes being all by their lonesomes, and would expect a lumpier design putting more such stuff into powerOfTwo.hpp or a similar place.  Naming and grouping is hard.)

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

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