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

[Quan Anh Mai]

On Thu, 10 Aug 2023 11:00:15 GMT, Emanuel Peter <epeter at openjdk.org> wrote:

>> @eme64 Thanks a lot for taking a look at this patch, I will address your remaining comments soon.
>> 
>> The basic idea of the transformation in `javaArithmetic.hpp` is to find `M` and `s` such that `x / c = floor(x * M / 2**s)` for every interesting value of `x`. The remaining transformation in `divnode.cpp` is to convert this calculation from integer arithmetic to modular arithmetic. This is easy if the representative in the congruence class of an operand is always equal to itself, in which case we can do the calculation directly. For other cases, we have to do additional calculation to take into consideration the difference between arithmetic calculations in 2 domains.
>
> @merykitty I'm mostly out of the office until September 9 (FYI).
> 
> It would be really cool if this made it in. I'm currently playing with `MethodHandles.constant`, and it is really easy to have "random" compile time constants.

@eme64 Thanks a lot for your support and sorry for the delay, I came across [this article](https://arxiv.org/abs/2012.12369) which motivated me to come up with a more general and optimal algorithm. This also consolidates the magic constant calculation across different division operations.

The underlying theory is given in the function `magic_divide_constant`, which I will restate here. Given positive integers `d <= N`, call `v` the largest nonnegative integer not larger than `N` such that `v + 1` is divisible by `d` then:

For all nonnegative integers `c`, `m` such that:

    m <= c * d < m + m / v

We have:

    floor(x / d) = floor(x * c / m) for all integers x in [0, N] (1)

For all nonnegative integers `c`, `m` such that:

    m < c * d <= m + m / v

We have:

    ceil(x / d) = floor(x * c / m) for all integers x in [-N, 0) (2)

As a result, to calculate the constant `c`, `m` corresponding to a division `x / d` with `x` in `[lo, hi]`, we divide the dividend range into negative and nonnegative intervals `[lo, 0)` and `[0, hi]`. Then, call `v_neg` the largest integer not larger than `-lo` such that `v_neg + 1` is divisible by `d`, and `v_pos` the largest integer not larger than `hi` such that `v_pos + 1` is divisible by `d`. We then need to find constant `c`, `m` such that:

    m <= c * d < m + m / v_pos
    m < c * d <= m + m / v_neg

This is applicable for both signed and unsigned types (with unsigned types we do not need to consider the negative range).

Substitute `x = v, x = v - d + 1` into (1), as well as `x = -v, x = -v + d - 1` into (2) shows that these bounds are indeed optimal.

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

PR Comment: https://git.openjdk.org/jdk/pull/9947#issuecomment-1684894863