From nobody Fri Jul 21 08:56:21 2023 X-Original-To: dev-commits-src-branches@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4R6k1d469kz4dNfS; Fri, 21 Jul 2023 08:56:21 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4R6k1d2zTnz4H3x; Fri, 21 Jul 2023 08:56:21 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1689929781; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=ZxRbRuW+7AEi0Avf2kUCDjxoBRlIzfMWkATP2e0yZTQ=; b=MoL9cZQAfl/jvX9e5doxfsuaWMFd+boIsSw7afRQxfwID0yeIKVMwSWWNDEpIjihTfith+ xeSD9+8DIhA2bKwgo/mdWLX0blvGkkp+51qLCmdiNKMiIA5CrZQGaM810+J0mdrFvEwzTx NXdG3cCcram8YanydPZVh0kiSDOshwguk770rTripnVyjik6e2QHnTnOBP7l0NqIbABzMS eS+hOOmcFhYHgwS+aMl59MtiTiEKn0PiM8jyDBARocyGxpG6fNzNQ6QCWVL4tNB73ne6zu nnSrkdrES3fHGN8oxjDNLoFm2vS4uEeLjN6ZKQKf6NG6DhGnv34bNS6xKqf1TQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1689929781; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=ZxRbRuW+7AEi0Avf2kUCDjxoBRlIzfMWkATP2e0yZTQ=; b=yKI24ZZ7lr7oRazTPtuuoyv2urzBfkVTghRgFd2RCQ046gwANSikYs5jZzNt7vsqkmptyl SYFkB7+TZjtbShaJ5DjnbqKMkU9thkmO4bXkP9hpCVfTpcwHkIb/8iULLbOECUAGxPPzpF Uxm8havVClhsJr5B8TPg6XsNM9BF4CWhZrw43Yv5tZTK/f7y2BJj/PGUXVxd2VlXVjgVEb GPxB9yjTj/8PLgHXhXLaTU6nQDx8BK1ExHQ1j+kSjGTJk5fPedQRxqOFqcdUu6DOYGZ3Ek D4eSXSBTEzTA3eTw8qS/aaBUBtlttSgH/HI/aMKMa0drgf+meSQckAFsCXiLCA== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1689929781; a=rsa-sha256; cv=none; b=eHcNQZ1bDrjmUYQ060l1+jU1qFOgmyNJtHtEzhTgEGyy3937plC/DjB6X5HjWg2X3lWsO9 5Cx8uqpTfA9E8WQP9IDDTXEPNToJKwjcdd+j15RZWMrd3dmDYb3sQqFgA0U1fFJLe+3xzE Iaszpn31VFbgjzUiK14lJaQQMMWQqX8cmL0HuPOoN4f7ImExFkxRybvihOSzkwaJJc9YcZ eNK7uyTQwugzt66Q+zPviGTaCo1y/ZXqEE+HD2nrCqmFAM/5nD4Y7RtS4v079EapKd+TC+ 5kfvMSUW8zp/dQco9+fMuViGkO+nNJ3YoDeu87P+hoPHr4+Wbj8Ok2R6Bz3WwA== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4R6k1d1cS6z166v; Fri, 21 Jul 2023 08:56:21 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.17.1/8.17.1) with ESMTP id 36L8uLqe045643; Fri, 21 Jul 2023 08:56:21 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 36L8uL3Z045642; Fri, 21 Jul 2023 08:56:21 GMT (envelope-from git) Date: Fri, 21 Jul 2023 08:56:21 GMT Message-Id: <202307210856.36L8uL3Z045642@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Robert Clausecker Subject: git: 2c03221cce0b - stable/13 - lib/libc/string: replace ffs/fls implementations with clang builtins List-Id: Commits to the stable branches of the FreeBSD src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-branches List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-branches@freebsd.org X-BeenThere: dev-commits-src-branches@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: fuz X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: 2c03221cce0b7446cb681de0179349d2ee72c252 Auto-Submitted: auto-generated The branch stable/13 has been updated by fuz: URL: https://cgit.FreeBSD.org/src/commit/?id=2c03221cce0b7446cb681de0179349d2ee72c252 commit 2c03221cce0b7446cb681de0179349d2ee72c252 Author: Robert Clausecker AuthorDate: 2023-06-23 16:22:54 +0000 Commit: Robert Clausecker CommitDate: 2023-07-21 08:52:37 +0000 lib/libc/string: replace ffs/fls implementations with clang builtins Most architectures we support (except for riscv64) have instructions to compute these functions very quickly. Replace old code with the ftz and clz builtin functions, allowing clang to generate good code for all architectures. We cannot use the ffs builtins as gcc uses ffs() to implement these on some platforms, potentially causing an infinite loop. As a consequence, toss out arm and i386 ffs() implementations. Sponsored by: The FreeBSD Foundation Reported by: jlduran@gmail.com, jhb Approved by: mhorne, jhb MFC after: 1 week Differential Revision: https://reviews.freebsd.org/D40730 Differential Revision: https://reviews.freebsd.org/D40966 (cherry picked from commit ee8b0c436d7221c25e8be3c3fe1f9da78b9d5b16) (cherry picked from commit 3f5788e0ed8e85567f651ad360596b8c330af5a9) --- lib/libc/arm/string/Makefile.inc | 1 - lib/libc/arm/string/ffs.S | 57 --------------------------------------- lib/libc/i386/string/Makefile.inc | 1 - lib/libc/i386/string/ffs.S | 56 -------------------------------------- lib/libc/string/ffs.c | 12 ++++----- lib/libc/string/ffsl.c | 12 ++++----- lib/libc/string/ffsll.c | 12 ++++----- lib/libc/string/fls.c | 13 +++++---- lib/libc/string/flsl.c | 14 +++++----- lib/libc/string/flsll.c | 13 +++++---- 10 files changed, 34 insertions(+), 157 deletions(-) diff --git a/lib/libc/arm/string/Makefile.inc b/lib/libc/arm/string/Makefile.inc index cf3175ea4e8c..550de34adb0e 100644 --- a/lib/libc/arm/string/Makefile.inc +++ b/lib/libc/arm/string/Makefile.inc @@ -3,7 +3,6 @@ MDSRCS+= \ bcopy.S \ bzero.S \ - ffs.S \ memcmp.S \ memcpy.S \ memmove.S \ diff --git a/lib/libc/arm/string/ffs.S b/lib/libc/arm/string/ffs.S deleted file mode 100644 index 5756dd81d21d..000000000000 --- a/lib/libc/arm/string/ffs.S +++ /dev/null @@ -1,57 +0,0 @@ -/* $NetBSD: ffs.S,v 1.5 2003/04/05 23:08:52 bjh21 Exp $ */ -/* - * Copyright (c) 2001 Christopher Gilbert - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. The name of the company nor the name of the author may be used to - * endorse or promote products derived from this software without specific - * prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, - * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES - * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR - * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - */ - -#include - -__FBSDID("$FreeBSD$"); - -.syntax unified - -/* - * ffs - find first set bit, this algorithm isolates the first set - * bit, then multiplies the number by 0x0450fbaf which leaves the top - * 6 bits as an index into the table. This algorithm should be a win - * over the checking each bit in turn as per the C compiled version. - * - * This is the ffs algorithm devised by d.seal and posted to comp.sys.arm on - * 16 Feb 1994. - */ - -ENTRY(ffs) - /* Standard trick to isolate bottom bit in r0 or 0 if r0 = 0 on entry */ - rsb r1, r0, #0 - ands r0, r0, r1 - itt ne - clzne r0, r0 - rsbne r0, r0, #32 - RET -END(ffs) - - .section .note.GNU-stack,"",%progbits diff --git a/lib/libc/i386/string/Makefile.inc b/lib/libc/i386/string/Makefile.inc index a8c50a285cbd..f3678b93bec3 100644 --- a/lib/libc/i386/string/Makefile.inc +++ b/lib/libc/i386/string/Makefile.inc @@ -4,7 +4,6 @@ MDSRCS+= \ bcmp.S \ bcopy.S \ bzero.S \ - ffs.S \ memcmp.S \ memcpy.S \ memmove.S \ diff --git a/lib/libc/i386/string/ffs.S b/lib/libc/i386/string/ffs.S deleted file mode 100644 index 3a0431c6a845..000000000000 --- a/lib/libc/i386/string/ffs.S +++ /dev/null @@ -1,56 +0,0 @@ -/* - * Copyright (c) 1993 Winning Strategies, Inc. - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by Winning Strategies, Inc. - * 4. The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -#include -__FBSDID("$FreeBSD$"); - -/* - * ffs(value) - * finds the first bit set in value and returns the index of - * that bit. Bits are numbered starting from 1, starting at the - * rightmost bit. A return value of 0 means that the argument - * was zero. - * - * Written by: - * J.T. Conklin (jtc@wimsey.com), Winning Strategies, Inc. - */ - -ENTRY(ffs) - bsfl 4(%esp),%eax - jz L1 /* ZF is set if all bits are 0 */ - incl %eax /* bits numbered from 1, not 0 */ - ret - - .align 2 -L1: xorl %eax,%eax /* clear result */ - ret -END(ffs) - - .section .note.GNU-stack,"",%progbits diff --git a/lib/libc/string/ffs.c b/lib/libc/string/ffs.c index 738ef90ce091..34140e3e4d85 100644 --- a/lib/libc/string/ffs.c +++ b/lib/libc/string/ffs.c @@ -3,6 +3,10 @@ * * Copyright (c) 1990, 1993 * The Regents of the University of California. All rights reserved. + * Copyright (c) 2023 The FreeBSD Foundation + * + * Portions of this software were developed by Robert Clausecker + * under sponsorship from the FreeBSD Foundation. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -43,11 +47,5 @@ __FBSDID("$FreeBSD$"); int ffs(int mask) { - int bit; - - if (mask == 0) - return(0); - for (bit = 1; !(mask & 1); bit++) - mask = (unsigned int)mask >> 1; - return (bit); + return (mask == 0 ? 0 : __builtin_ctz(mask) + 1); } diff --git a/lib/libc/string/ffsl.c b/lib/libc/string/ffsl.c index dbd894b9655b..701e23cdf8f4 100644 --- a/lib/libc/string/ffsl.c +++ b/lib/libc/string/ffsl.c @@ -3,6 +3,10 @@ * * Copyright (c) 1990, 1993 * The Regents of the University of California. All rights reserved. + * Copyright (c) 2023 The FreeBSD Foundation + * + * Portions of this software were developed by Robert Clausecker + * under sponsorship from the FreeBSD Foundation. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -40,11 +44,5 @@ __FBSDID("$FreeBSD$"); int ffsl(long mask) { - int bit; - - if (mask == 0) - return (0); - for (bit = 1; !(mask & 1); bit++) - mask = (unsigned long)mask >> 1; - return (bit); + return (mask == 0 ? 0 : __builtin_ctzl(mask) + 1); } diff --git a/lib/libc/string/ffsll.c b/lib/libc/string/ffsll.c index 91886de2f127..e94fb518eb03 100644 --- a/lib/libc/string/ffsll.c +++ b/lib/libc/string/ffsll.c @@ -3,6 +3,10 @@ * * Copyright (c) 1990, 1993 * The Regents of the University of California. All rights reserved. + * Copyright (c) 2023 The FreeBSD Foundation + * + * Portions of this software were developed by Robert Clausecker + * under sponsorship from the FreeBSD Foundation. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -40,11 +44,5 @@ __FBSDID("$FreeBSD$"); int ffsll(long long mask) { - int bit; - - if (mask == 0) - return (0); - for (bit = 1; !(mask & 1); bit++) - mask = (unsigned long long)mask >> 1; - return (bit); + return (mask == 0 ? 0 : __builtin_ctzll(mask) + 1); } diff --git a/lib/libc/string/fls.c b/lib/libc/string/fls.c index d9edc41f9599..3c4719776778 100644 --- a/lib/libc/string/fls.c +++ b/lib/libc/string/fls.c @@ -3,6 +3,10 @@ * * Copyright (c) 1990, 1993 * The Regents of the University of California. All rights reserved. + * Copyright (c) 2023 The FreeBSD Foundation + * + * Portions of this software were developed by Robert Clausecker + * under sponsorship from the FreeBSD Foundation. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -32,6 +36,7 @@ #include __FBSDID("$FreeBSD$"); +#include #include /* @@ -40,11 +45,5 @@ __FBSDID("$FreeBSD$"); int fls(int mask) { - int bit; - - if (mask == 0) - return (0); - for (bit = 1; mask != 1; bit++) - mask = (unsigned int)mask >> 1; - return (bit); + return (mask == 0 ? 0 : CHAR_BIT * sizeof(mask) - __builtin_clz(mask)); } diff --git a/lib/libc/string/flsl.c b/lib/libc/string/flsl.c index 60370cf7d832..f5280b77a4e2 100644 --- a/lib/libc/string/flsl.c +++ b/lib/libc/string/flsl.c @@ -3,6 +3,11 @@ * * Copyright (c) 1990, 1993 * The Regents of the University of California. All rights reserved. + * Copyright (c) 2023 The FreeBSD Foundation + + * + * Portions of this software were developed by Robert Clausecker + * under sponsorship from the FreeBSD Foundation. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -32,6 +37,7 @@ #include __FBSDID("$FreeBSD$"); +#include #include /* @@ -40,11 +46,5 @@ __FBSDID("$FreeBSD$"); int flsl(long mask) { - int bit; - - if (mask == 0) - return (0); - for (bit = 1; mask != 1; bit++) - mask = (unsigned long)mask >> 1; - return (bit); + return (mask == 0 ? 0 : CHAR_BIT * sizeof(mask) - __builtin_clzl(mask)); } diff --git a/lib/libc/string/flsll.c b/lib/libc/string/flsll.c index 275aaa0e2e15..ab504b8e592f 100644 --- a/lib/libc/string/flsll.c +++ b/lib/libc/string/flsll.c @@ -3,6 +3,10 @@ * * Copyright (c) 1990, 1993 * The Regents of the University of California. All rights reserved. + * Copyright (c) 2023 The FreeBSD Foundation + * + * Portions of this software were developed by Robert Clausecker + * under sponsorship from the FreeBSD Foundation. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -32,6 +36,7 @@ #include __FBSDID("$FreeBSD$"); +#include #include /* @@ -40,11 +45,5 @@ __FBSDID("$FreeBSD$"); int flsll(long long mask) { - int bit; - - if (mask == 0) - return (0); - for (bit = 1; mask != 1; bit++) - mask = (unsigned long long)mask >> 1; - return (bit); + return (mask == 0 ? 0 : CHAR_BIT * sizeof(mask) - __builtin_clzll(mask)); }