Re: [Sbcl-commits] master: Recognize (integer-length (ldb (byte 64 0) (1- (logand n (- n))))) as ctz

stassats via Sbcl-commits <[email protected]> writes:

> The branch "master" has been updated in SBCL:
>        via  2c3722ef6c309045afe6804fc99bc9e8d9b6c75a (commit)
>       from  ab3fb8c0ecd1dbe07f6b4fcdd3d13a5ac084f00a (commit)
>
> - Log -----------------------------------------------------------------
> commit 2c3722ef6c309045afe6804fc99bc9e8d9b6c75a
> Author: Stas Boukarev <[email protected]>
> Date:   Wed Dec 10 17:48:31 2025 +0300
>
>     Recognize (integer-length (ldb (byte 64 0) (1- (logand n (- n))))) as ctz
> ---
>  doc/manual/efficiency.texinfo  | 22 ++++++++++++++++

Nice!  I think since this is documented, potentially fragile, and not
directly exercised by anything else, this is a prime candidate for
having a test that verifies that this recognition actually takes place.
Whether that's a test of the emitted assembly, or a test that the
`integer-length` transform fires successfully, I don't know.  I guess
I want to encourage adding tests of desired properties by default,
whether that's from adding a new feature like this or fixing a bug.

The transform itself looks pretty horrible, and we're still tied to
working from the outside operator?

What does the equivalent for rotation look like?  The idiom is

  (ldb (byte 64 0) (logior (ash x <n>) (ash x <n-64>)))

but then does the modular rewriting happen first, so we'd need in fact
to be recognizing

  (logior/mod64 (ash/mod64 ...) (ash/mod64 ...))?

(We'd presumably then want to bring the guts of sb-rotate-byte into the
core system and leave just the interface as the contrib)

Thanks,

Christophe