From: Daniel Engel <gnu@danielengel.com>
To: Richard Earnshaw <Richard.Earnshaw@foss.arm.com>,
gcc-patches@gcc.gnu.org
Cc: Daniel Engel <gnu@danielengel.com>,
Christophe Lyon <christophe.lyon@linaro.org>
Subject: [PATCH v7 15/34] Import 'popcnt' functions from the CM0 library
Date: Mon, 31 Oct 2022 08:45:10 -0700 [thread overview]
Message-ID: <20221031154529.3627576-16-gnu@danielengel.com> (raw)
In-Reply-To: <20221031154529.3627576-1-gnu@danielengel.com>
The functional overlap between the single- and double-word functions
makes this implementation about 30% smaller than the C functions
if both functions are linked together in the same appliation.
gcc/libgcc/ChangeLog:
2022-10-09 Daniel Engel <gnu@danielengel.com>
* config/arm/popcnt.S (__popcountsi, __popcountdi2): New file.
* config/arm/lib1funcs.S: #include bit/popcnt.S
* config/arm/t-elf (LIB1ASMFUNCS): Add _popcountsi2/di2.
---
libgcc/config/arm/lib1funcs.S | 1 +
libgcc/config/arm/popcnt.S | 189 ++++++++++++++++++++++++++++++++++
libgcc/config/arm/t-elf | 2 +
3 files changed, 192 insertions(+)
create mode 100644 libgcc/config/arm/popcnt.S
diff --git a/libgcc/config/arm/lib1funcs.S b/libgcc/config/arm/lib1funcs.S
index 3f7b9e739f0..0eb6d1d52a7 100644
--- a/libgcc/config/arm/lib1funcs.S
+++ b/libgcc/config/arm/lib1funcs.S
@@ -1705,6 +1705,7 @@ LSYM(Lover12):
#include "clz2.S"
#include "ctz2.S"
#include "parity.S"
+#include "popcnt.S"
/* ------------------------------------------------------------------------ */
/* These next two sections are here despite the fact that they contain Thumb
diff --git a/libgcc/config/arm/popcnt.S b/libgcc/config/arm/popcnt.S
new file mode 100644
index 00000000000..4613ea475b0
--- /dev/null
+++ b/libgcc/config/arm/popcnt.S
@@ -0,0 +1,189 @@
+/* popcnt.S: ARM optimized popcount functions
+
+ Copyright (C) 2020-2022 Free Software Foundation, Inc.
+ Contributed by Daniel Engel (gnu@danielengel.com)
+
+ This file is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 3, or (at your option) any
+ later version.
+
+ This file is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ Under Section 7 of GPL version 3, you are granted additional
+ permissions described in the GCC Runtime Library Exception, version
+ 3.1, as published by the Free Software Foundation.
+
+ You should have received a copy of the GNU General Public License and
+ a copy of the GCC Runtime Library Exception along with this program;
+ see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+ <http://www.gnu.org/licenses/>. */
+
+
+#ifdef L_popcountdi2
+
+// int __popcountdi2(int)
+// Returns the number of bits set in $r1:$r0.
+// Returns the result in $r0.
+FUNC_START_SECTION popcountdi2 .text.sorted.libgcc.popcountdi2
+ CFI_START_FUNCTION
+
+ #if defined(__OPTIMIZE_SIZE__) && __OPTIMIZE_SIZE__
+ // Initialize the result.
+ // Compensate for the two extra loop (one for each word)
+ // required to detect zero arguments.
+ movs r2, #2
+
+ LLSYM(__popcountd_loop):
+ // Same as __popcounts_loop below, except for $r1.
+ subs r2, #1
+ subs r3, r1, #1
+ ands r1, r3
+ bcs LLSYM(__popcountd_loop)
+
+ // Repeat the operation for the second word.
+ b LLSYM(__popcounts_loop)
+
+ #else /* !__OPTIMIZE_SIZE__ */
+ // Load the one-bit alternating mask.
+ ldr r3, =0x55555555
+
+ // Reduce the second word.
+ lsrs r2, r1, #1
+ ands r2, r3
+ subs r1, r2
+
+ // Reduce the first word.
+ lsrs r2, r0, #1
+ ands r2, r3
+ subs r0, r2
+
+ // Load the two-bit alternating mask.
+ ldr r3, =0x33333333
+
+ // Reduce the second word.
+ lsrs r2, r1, #2
+ ands r2, r3
+ ands r1, r3
+ adds r1, r2
+
+ // Reduce the first word.
+ lsrs r2, r0, #2
+ ands r2, r3
+ ands r0, r3
+ adds r0, r2
+
+ // There will be a maximum of 8 bits in each 4-bit field.
+ // Jump into the single word flow to combine and complete.
+ b LLSYM(__popcounts_merge)
+
+ #endif /* !__OPTIMIZE_SIZE__ */
+#endif /* L_popcountdi2 */
+
+
+// The implementation of __popcountdi2() tightly couples with __popcountsi2(),
+// such that instructions must appear consecutively in the same memory
+// section for proper flow control. However, this construction inhibits
+// the ability to discard __popcountdi2() when only using __popcountsi2().
+// Therefore, this block configures __popcountsi2() for compilation twice.
+// The first version is a minimal standalone implementation, and the second
+// version is the continuation of __popcountdi2(). The standalone version must
+// be declared WEAK, so that the combined version can supersede it and
+// provide both symbols when required.
+// '_popcountsi2' should appear before '_popcountdi2' in LIB1ASMFUNCS.
+#if defined(L_popcountsi2) || defined(L_popcountdi2)
+
+#ifdef L_popcountsi2
+// int __popcountsi2(int)
+// Returns '0' if the number of bits set in $r0 is even, and '1' otherwise.
+// Returns the result in $r0.
+// Uses $r2 as scratch space.
+WEAK_START_SECTION popcountsi2 .text.sorted.libgcc.popcountsi2
+ CFI_START_FUNCTION
+
+#else /* L_popcountdi2 */
+FUNC_ENTRY popcountsi2
+
+#endif
+
+ #if defined(__OPTIMIZE_SIZE__) && __OPTIMIZE_SIZE__
+ // Initialize the result.
+ // Compensate for the extra loop required to detect zero.
+ movs r2, #1
+
+ // Kernighan's algorithm for __popcount(x):
+ // for (c = 0; x; c++)
+ // x &= x - 1;
+
+ LLSYM(__popcounts_loop):
+ // Every loop counts for a '1' set in the argument.
+ // Count down since it's easier to initialize positive compensation,
+ // and the negation before function return is free.
+ subs r2, #1
+
+ // Clear one bit per loop.
+ subs r3, r0, #1
+ ands r0, r3
+
+ // If this is a test for zero, it will be impossible to distinguish
+ // between zero and one bits set: both terminate after one loop.
+ // Instead, subtraction underflow flags when zero entered the loop.
+ bcs LLSYM(__popcounts_loop)
+
+ // Invert the result, since we have been counting negative.
+ rsbs r0, r2, #0
+ RET
+
+ #else /* !__OPTIMIZE_SIZE__ */
+
+ // Load the one-bit alternating mask.
+ ldr r3, =0x55555555
+
+ // Reduce the word.
+ lsrs r1, r0, #1
+ ands r1, r3
+ subs r0, r1
+
+ // Load the two-bit alternating mask.
+ ldr r3, =0x33333333
+
+ // Reduce the word.
+ lsrs r1, r0, #2
+ ands r0, r3
+ ands r1, r3
+ LLSYM(__popcounts_merge):
+ adds r0, r1
+
+ // Load the four-bit alternating mask.
+ ldr r3, =0x0F0F0F0F
+
+ // Reduce the word.
+ lsrs r1, r0, #4
+ ands r0, r3
+ ands r1, r3
+ adds r0, r1
+
+ // Accumulate individual byte sums into the MSB.
+ lsls r1, r0, #8
+ adds r0, r1
+ lsls r1, r0, #16
+ adds r0, r1
+
+ // Isolate the cumulative sum.
+ lsrs r0, #24
+ RET
+
+ #endif /* !__OPTIMIZE_SIZE__ */
+
+ CFI_END_FUNCTION
+FUNC_END popcountsi2
+
+#ifdef L_popcountdi2
+FUNC_END popcountdi2
+#endif
+
+#endif /* L_popcountsi2 || L_popcountdi2 */
+
diff --git a/libgcc/config/arm/t-elf b/libgcc/config/arm/t-elf
index 0e9b9ce21af..2e3f04aa2f0 100644
--- a/libgcc/config/arm/t-elf
+++ b/libgcc/config/arm/t-elf
@@ -25,6 +25,7 @@ LIB1ASMFUNCS += \
_clzsi2 \
_ctzsi2 \
_paritysi2 \
+ _popcountsi2 \
# Group 1: Integer function objects.
@@ -39,6 +40,7 @@ LIB1ASMFUNCS += \
_ffssi2 \
_ffsdi2 \
_paritydi2 \
+ _popcountdi2 \
_dvmd_tls \
_divsi3 \
_modsi3 \
--
2.34.1
next prev parent reply other threads:[~2022-10-31 15:47 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-10-31 15:44 [PATCH v7 00/34] libgcc: Thumb-1 Floating-Point Assembly for Cortex M0 Daniel Engel
2022-10-31 15:44 ` [PATCH v7 01/34] Add and restructure function declaration macros Daniel Engel
2022-10-31 15:44 ` [PATCH v7 02/34] Rename THUMB_FUNC_START to THUMB_FUNC_ENTRY Daniel Engel
2022-10-31 15:44 ` [PATCH v7 03/34] Fix syntax warnings on conditional instructions Daniel Engel
2022-10-31 15:44 ` [PATCH v7 04/34] Reorganize LIB1ASMFUNCS object wrapper macros Daniel Engel
2022-10-31 15:45 ` [PATCH v7 05/34] Add the __HAVE_FEATURE_IT and IT() macros Daniel Engel
2022-10-31 15:45 ` [PATCH v7 06/34] Refactor 'clz' functions into a new file Daniel Engel
2022-10-31 15:45 ` [PATCH v7 07/34] Refactor 'ctz' " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 08/34] Refactor 64-bit shift " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 09/34] Import 'clz' functions from the CM0 library Daniel Engel
2022-10-31 15:45 ` [PATCH v7 10/34] Import 'ctz' " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 11/34] Import 64-bit shift " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 12/34] Import 'clrsb' " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 13/34] Import 'ffs' " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 14/34] Import 'parity' " Daniel Engel
2022-10-31 15:45 ` Daniel Engel [this message]
2022-10-31 15:45 ` [PATCH v7 16/34] Refactor Thumb-1 64-bit comparison into a new file Daniel Engel
2022-10-31 15:45 ` [PATCH v7 17/34] Import 64-bit comparison from CM0 library Daniel Engel
2022-10-31 15:45 ` [PATCH v7 18/34] Merge Thumb-2 optimizations for 64-bit comparison Daniel Engel
2022-10-31 15:45 ` [PATCH v7 19/34] Import 32-bit division from the CM0 library Daniel Engel
2022-10-31 15:45 ` [PATCH v7 20/34] Refactor Thumb-1 64-bit division into a new file Daniel Engel
2022-10-31 15:45 ` [PATCH v7 21/34] Import 64-bit division from the CM0 library Daniel Engel
2022-10-31 15:45 ` [PATCH v7 22/34] Import integer multiplication " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 23/34] Refactor Thumb-1 float comparison into a new file Daniel Engel
2022-10-31 15:45 ` [PATCH v7 24/34] Import float comparison from the CM0 library Daniel Engel
2022-10-31 15:45 ` [PATCH v7 25/34] Refactor Thumb-1 float subtraction into a new file Daniel Engel
2022-10-31 15:45 ` [PATCH v7 26/34] Import float addition and subtraction from the CM0 library Daniel Engel
2022-10-31 15:45 ` [PATCH v7 27/34] Import float multiplication " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 28/34] Import float division " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 29/34] Import integer-to-float conversion " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 30/34] Import float-to-integer " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 31/34] Import float<->double " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 32/34] Import float<->__fp16 " Daniel Engel
2022-10-31 15:45 ` [PATCH v7 33/34] Drop single-precision Thumb-1 soft-float functions Daniel Engel
2022-10-31 15:45 ` [PATCH v7 34/34] Add -mpure-code support to the CM0 functions Daniel Engel
2022-11-15 15:27 ` [PING] Re: [PATCH v7 00/34] libgcc: Thumb-1 Floating-Point Assembly for Cortex M0 Daniel Engel
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20221031154529.3627576-16-gnu@danielengel.com \
--to=gnu@danielengel.com \
--cc=Richard.Earnshaw@foss.arm.com \
--cc=christophe.lyon@linaro.org \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).