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

[Quan Anh Mai]

On Wed, 20 Mar 2024 12:02:06 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:
>> 
>>   fix tests
>
> src/hotspot/share/opto/divnode.cpp line 245:
> 
>> 243:   // to rounding down, now it is guaranteed to be correct, according to
>> 244:   // N-Bit Unsigned Division Via N-Bit Multiply-Add by Arch D. Robison
>> 245:   magic_divide_constants_round_down(divisor, magic_const, shift_const);
> 
> I think there's no need for `magic_divide_constants_round_down()`.
> 
> Firstly, we recover the previous value of `magic_const` and `shift_const`, just before the overflow:
> 
>   magic_const = magic_const + 1 >> 1 | 0x8000_0000;
>   shift_const -= 1;
> 
> Then we decrement `magic_const` by one:
> 
>   magic_const -= 1;
> 
> That's it.
> If desired, we can additionally reduce `magic_const` to an odd value by right-shifting it by the number of trailing zero bits, and updating `shift_const` accordingly. But for the usage here, I think it makes no real difference.
> 
> We can thus avoid the division in `magic_divide_constants_round_down()`, and can get rid of the method altogether, as it seems to be used only here.
> This might even open similar code for the `julong` case.

@rgiulietti I think that is a brilliant observation. However, I think that doing so would not reduce the code complexity and it also puts another burden of proof on us for the mathematical lemma.

Regarding the `julong` case. rounding down is interesting, as we can emit code like this:

    addq dividend, 1
    je overflow
    ... (the remaining calculation)

And if `dividend` is known to be different from `max_julong` then the `je` can be removed.

As a result, I think it would be possible to address your idea in a next RFE. As I think the patch is dense enough in mathematical proofs.

Thanks a lot.

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

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