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

On Fri, Jan 9, 2026 at 12:41 PM Stas Boukarev <[email protected]> wrote:
>
> Without modular arithmetic things turn out pretty badly if it's not
> recognized. So it's not a good idea to rely on 0 being excluded.

I'm sorry, I don't understand this at all.  As best I can tell, your
first sentence is
saying that if the operation is not constrained to fit in a word, either by type
declarations on the operand or by an explicit 'logand' or 'ldb' on the
result, and
therefore the expression is not recognized and transformed into 'tzcnt' or
equivalent, then "things turn out pretty badly" — I guess this rather vague
phrase means the generated code is not very efficient?  But why would you
expect good code if the user actually wants arbitrary-precision arithmetic,
or at least has failed to indicate that they don't?

And what does relying on zero-exclusion have to do with that?

At the risk of belaboring the obvious — if CL had a builtin function for this
operation, it would have to signal an error on zero, or at least return a
special value like -1; there's no finite correct result.  In an
arbitrary-precision
world, zero is not in the domain, just as it isn't for the reciprocal function.
Generated code would be obliged to check for zero explicitly, unless the
possibility could be ruled out statically.

Well, there's no CL builtin, so people write expressions that compute the
same result on nonzero operands as the builtin would.  On zero, these
expressions return some result, and I understand: if the compiler can't
rule out a zero operand, then it must exactly match the behavior of
the expression it was given.  But if it can rule out zero, where's the
problem in transforming it?

-- Scott

> On Fri, Jan 9, 2026 at 11:35 PM Scott L. Burson <[email protected]> wrote:
> >
> > On Wed, Dec 10, 2025 at 11:45 AM Stas Boukarev <[email protected]> wrote:
> > > 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.
> >
> > Speaking as someone who is actually using this operation -- doesn't the compiler
> > know whether n can be zero?  It seems to be so good at tracking the domains
> > of integer variables.
> >
> > I am literally doing (loop while (/= n 0) (let ((b (least-1-bit n)))
> > ...)) where least-1-bit
> > expands to one of the above expressions.  Surely, under these circumstances,
> > the compiler knows that n isn't zero, so it can match all of the three or four
> > expressions people use for this?
> >
> > -- Scott


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