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

Maybe (integer-length (ldb (byte 64 0) (lognor n (- n)))) is a better pattern.

On Wed, Dec 10, 2025 at 10:44 PM Stas Boukarev <[email protected]> wrote:
>
> 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