RFR: 8282365: Consolidate and improve division by constant idealizations [v44]

[Raffaello Giulietti]

On Thu, 18 Jan 2024 15:26:35 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

>> Quan Anh Mai has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   update include order and license year
>
> src/hotspot/share/opto/divconstants.cpp line 122:
> 
>> 120: // c * d - m is the intersection of (0, m / v_neg] and (0, m / v_pos). Which is (0, m / v_pos)
>> 121: // if v_pos >= v_neg and (0, m / v_neg] otherwise.
>> 122: //
> 
> The analysis seem correct.

The convoluted test to break out of the while loop can be simplified if we are willing to consider two cases.

Equality in `c / m <= (1 / d) * ((v + 1) / v)` is equivalent to `c / m = b / v`, where `b = (v + 1) / d` is an integer. Note that the fraction `b / v` is irreducible: a common divisor of `b` an `v` has to divide any linear combination as well, in particular it has to divide `d * b - 1 * v = 1`. Thus, `c >= b` and `m >= v`. Since `m = 2^s`, `v` must be a power of 2.

This means that, when `m` is a power of 2, the only way to have equality is `v_neg > v_pos` _and_ `v_neg` is a power of 2 (say `v_neg = 2^e`), which should be a rare case. This can be detected cheaply early, before the loop. In such a  case, the smallest `c` is `b` and the smallest `s` is `e`, and a result meeting `s >= min_s` doesn't need any iterative algorithm.

Otherwise equality does not hold. Now, `c / m < (1 / d) * ((v + 1) / v)` is equivalent to `m > v * rc`. In turn, `m > v * rc` <=> `m / v > rc` <=> `ceil(m / v) > rc`.

Thus, rather than maintaining invariants for `qv = floor(m / v)` and `rv = m - qv * v` as currently defined, we can redefine them as `qv = ceil(m / v)` and `rv = qv * v - m` (`0 <= rv < v`) and maintain _these_ invariants instead.

  T qv = 1;
  T rv = v - 1;
    ...
    if (rv >= v - rv) { // 2 * rv >= v
      qv_ovf = qv > min_signed;
      qv = qv * 2 - 1;
      rv = rv * 2 - v;
    } else {            // 2 * rv < v
      qv_ovf = qv >= min_signed;
      qv = qv * 2;
      rv = rv * 2;
    }

The test to exit the loop then reduces to `qv > rc || qv_ovf`.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/9947#discussion_r1461743490