Re: Optimizing jit_divi_u()

[Paulo César Pereira de Andrade]

Em sex., 18 de ago. de 2023 às 09:41, Paul Cercueil
<paul@crapouillou.net> escreveu:
>
> Hi Paulo,

  Hi Paul,

> I'm implementing an algorithm in my JIT to handle divisions by known
> immediate values:
> https://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html
>
> This could totally be a default implementation for jit_divi_u(), by the
> way.
>
> It does require a "64 <- 32 * 32" multiplication and needs the high 32
> bits. Since we already have jit_mulr() to retrieve the low bits, I
> wonder if it would be a good idea to have a jit_mulhr() to only get the
> high bits.
>
> This algorithm above is for 32-bit values, but I see no reason why it
> wouldn't work for 64-bit values as well, as long as we have a "128 <-
> 64 * 64" multiplication.

  Most cpus have a mulh or similar instructions. Lightning uses them
for "qmul". It could be modified to avoid 2 instructions for the use
case you show, and have 4 new codes, mulhr, mulhi, mulhr_u
and mulhi_u.

  I will consider it for Lightning 2.2.3. For most ports it should be
trivial. But for some it might not be so easy as there is only an unsigned
variant to get the top word, but most code is already in place and
would just require adapting the qmul{r,i}{,_u} implementation.

> Cheers,
> -Paul

Thanks,
Paulo