lib/libc/string: replace ffs/fls implementations with clang builtins

[fuz]

Summary

Most architectures we support (except for riscv64) have instructions
to compute these functions very quickly. Replace old code with the
ctz and clz builtin functions, allowing clang to generate good code
for all architectures.

As a consequence, toss out arm and i386 ffs() implementations as
clang generates comparable code (for i386) or better code (for arm)
than the assembly implementations.

Unit tests are proposed in D40729 to these these new implementations.

Sponsored by: FreeBSD Foundation

Test Plan

See unit tests added in D40729. These pass with both the
old and the new implementations on amd64.

[andrew]

See D40698 for something similar in the kernel

[fuz]

@andrew Thanks, I was unaware that a similar idea is already being tried in the kernel. Could you recommend some people to add as reviewers to this and related changesets? I'm planning to submit a bunch of SIMD-enhanced libc functions for amd64 in the near future.

[mjg]

I don't know if these functions are worth patching, really nothing but total cruft should be using these to begin with.

There is indeed some duplication with kernel code, but sorting that out is probably also a waste of time.

That said, I don't think there is a problem landing the patch provided it lines up with's in the kernel past D40698

[kevans]

Let's add mhorne as well for some collaboration; IMO it'd be nice if we could structure things in such a way that libc just provides the libkern versions like we may do, e.g., with some string functions. I appreciate that that might ugly'ify libkern.h as well, since we would need to either rename all of the relevant functions around an include to libkern.h or use, say, an FFS_STATIC macro in libkern.h that defaults to static.

[mhorne]

In D40730#928317, @kevans wrote:

Let's add mhorne as well for some collaboration; IMO it'd be nice if we could structure things in such a way that libc just provides the libkern versions like we may do, e.g., with some string functions. I appreciate that that might ugly'ify libkern.h as well, since we would need to either rename all of the relevant functions around an include to libkern.h or use, say, an FFS_STATIC macro in libkern.h that defaults to static.

I think the libc-provided functions are few and simple enough that I'd prefer to avoid the interdependence. Which functions do we do this for currently?

lib/libc/string/ffs.c

50

This could be just return (__builtin_ffs(mask));, same goes for ffsl and ffsll. Unless there is some difference?

[fuz]

lib/libc/string/ffs.c

50

Oh I totally forgot about these! Let me quickly go ahead and update the diff.

[fuz]

Switch to __builtin_ffs*()

As @mhorne noted, these are more suitable. Totally forgot that they
exist.

[mjg]

again if someone insists on it i'm not going to stand in the way, but i'm not acking this eithe., so given that other people are involved i suggest you guys sort this out as you see fit

[jlduran]

This broke builds using GCC 12 (https://cirrus-ci.com/task/6627586759983104). Is this being currently addressed?

[fuz]

In D40730#931286, @jlduran_gmail.com wrote:

This broke builds using GCC 12 (https://cirrus-ci.com/task/6627586759983104). Is this being currently addressed?

I have a workaround for this breakage which I plan to investigate next week. The idea is to switch back to __builtin_ctz when building with gcc, which does not trigger the warning.

[jlduran]

In D40730#931752, @fuz wrote:

In D40730#931286, @jlduran_gmail.com wrote:

This broke builds using GCC 12 (https://cirrus-ci.com/task/6627586759983104). Is this being currently addressed?

I have a workaround for this breakage which I plan to investigate next week. The idea is to switch back to __builtin_ctz when building with gcc, which does not trigger the warning.

Thank you!

[jhb]

In D40730#931752, @fuz wrote:

In D40730#931286, @jlduran_gmail.com wrote:

This broke builds using GCC 12 (https://cirrus-ci.com/task/6627586759983104). Is this being currently addressed?

I have a workaround for this breakage which I plan to investigate next week. The idea is to switch back to __builtin_ctz when building with gcc, which does not trigger the warning.

Actually, that's probably always the right solution.

Compilers view the C library versions of several "standard" routines as the fallback to use in case they can't inline a builtin, e.g. memset or memcpy. When it's not a constant value, they instead resort to calling the C library routine. GCC is a bit less willing to inline some things than clang, but clang will do this too. Using __builtin_foo in the C library function foo is I think always wrong and always recursive. Imagine if you had changed memcpy in libc to just be __builtin_memcpy. That's what you've done here. You need to use a lower-level primitive like ctz that maps to compiler intrinsics provided by libcompiler-rt.