[v2,02/18] bitops: Optimize parity8() using __builtin_parity()

Commit Message

Kuan-Wei Chiu March 1, 2025, 2:23 p.m. UTC

Refactor parity8() to use __builtin_parity() when no
architecture-specific implementation is available. If the input is a
compile-time constant, expand it using the _parity_const() macro to
enable constant folding, allowing the compiler to optimize it at
compile time.

Additionally, mark parity8() with __attribute_const__ to indicate its
pure nature, ensuring better optimization opportunities.

This change improves efficiency by leveraging compiler intrinsics while
maintaining a fallback mechanism for architectures without specific
implementations.

Co-developed-by: Yu-Chun Lin <[e-mail]>
Signed-off-by: Yu-Chun Lin <[e-mail]>
Signed-off-by: Kuan-Wei Chiu <[e-mail]>
---
 include/linux/bitops.h | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)

Patch

diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index c1cb53cf2f0f..4c307d9c1545 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -229,6 +229,27 @@  static inline int get_count_order_long(unsigned long l)
 	return (int)fls_long(--l);
 }
 
+#define _parity_const(val)	\
+({				\
+	u64 __v = (val);	\
+	int __ret;		\
+	__v ^= __v >> 32;	\
+	__v ^= __v >> 16;	\
+	__v ^= __v >> 8;	\
+	__v ^= __v >> 4;	\
+	__v ^= __v >> 2;	\
+	__v ^= __v >> 1;	\
+	__ret = __v & 1;	\
+	__ret;			\
+})
+
+#ifndef _parity8
+static inline __attribute_const__ int _parity8(u8 val)
+{
+	return __builtin_parity(val);
+}
+#endif
+
 /**
  * parity8 - get the parity of an u8 value
  * @value: the value to be examined
@@ -250,14 +271,9 @@  static inline int get_count_order_long(unsigned long l)
  *	if (parity8(val) == 0)
  *		val ^= BIT(7);
  */
-static inline int parity8(u8 val)
+static inline __attribute_const__ int parity8(u8 val)
 {
-	/*
-	 * One explanation of this algorithm:
-	 * https://funloop.org/codex/problem/parity/README.html
-	 */
-	val ^= val >> 4;
-	return (0x6996 >> (val & 0xf)) & 1;
+	return __builtin_constant_p(val) ? _parity_const(val) : _parity8(val);
 }
 
 /**