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

On Wed, Dec 10, 2025 at 10:19 PM Christophe Rhodes via Sbcl-devel
<[email protected]> wrote:
>
> 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.

IR1 can be matched. Although the ir1 tests only work with sb-devel.

> 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.

I like adding tests, but I also like being lazy.

> 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>)))

It also has to be non-horrible if it doesn't get translated. I had
trouble figuring out how to deal with 0, some code in the wild uses
things like
(1- (integer-length (logand n (- n)))) or (1- (logcount (logxor n (1-
n)))), but they return a different thing on 0. Maybe they should be
matched anyway and 0 handled with a conditional move or something.
And I decided against (logcount (ldb (byte 64 0) (lognor n (- n))))
because popcount is potentially expensive.

> but then does the modular rewriting happen first, so we'd need in fact
> to be recognizing
>
>   (logior/mod64 (ash/mod64 ...) (ash/mod64 ...))?

I specifically added (delay-ir1-transform node :ir1-phases) to reduce
variation, so that just the modular funs have to be chcked. Although
they get inserted first anyway, due to DFS, some unoptimized casts
added by cut-to-width were interfering. And, since it's matching
multiple forms, relevant reoptimizations do not always reach the outer
function of interest.


> (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
>
>
> _______________________________________________
> Sbcl-devel mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/sbcl-devel


_______________________________________________
Sbcl-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/sbcl-devel