Fix compiler builtin usage in new pg_bitutils.c

alvherre · alvherre · commit fc6c72747ae6 · 2019-02-15T13:39:56.000-03:00
Split out these new functions in three parts: one in a new file that uses the compiler builtin and gets compiled with the -mpopcnt compiler option if it exists; another one that uses the compiler builtin but not the compiler option; and finally the fallback with open-coded algorithms. Split out the configure logic: in the original commit, it was selecting to use the -mpopcnt compiler switch together with deciding whether to use the compiler builtin, but those two things are really separate. Split them out. Also, expose whether the builtin exists to Makefile.global, so that src/port's Makefile can decide whether to compile the hw-optimized file. Remove CPUID test for CTZ/CLZ. Make pg_{right,left}most_ones use either the compiler intrinsic or open-coded algo; trying to use the HW-optimized version is a waste of time. Make them static inline functions. Discussion: https://postgr.es/m/20190213221719.GA15976@alvherre.pgsql
diff --git a/config/c-compiler.m4 b/config/c-compiler.m4
@@ -381,22 +381,16 @@ fi])# PGAC_C_BUILTIN_OP_OVERFLOW
 # PGAC_C_BUILTIN_POPCOUNT
 # -------------------------
 AC_DEFUN([PGAC_C_BUILTIN_POPCOUNT],
-[define([Ac_cachevar], [AS_TR_SH([pgac_cv_popcount])])dnl
-AC_CACHE_CHECK([for __builtin_popcount], [Ac_cachevar],
-[pgac_save_CFLAGS=$CFLAGS
-CFLAGS="$pgac_save_CFLAGS -mpopcnt"
-AC_COMPILE_IFELSE([AC_LANG_SOURCE(
-[static int x = __builtin_popcount(255);])],
-[Ac_cachevar=yes],
-[Ac_cachevar=no])
-CFLAGS="$pgac_save_CFLAGS"])
-if test x"$Ac_cachevar" = x"yes"; then
-  CFLAGS_POPCNT="-mpopcnt"
+[AC_CACHE_CHECK([for __builtin_popcount], pgac_cv__builtin_popcount,
+[AC_COMPILE_IFELSE([AC_LANG_SOURCE(
+[static int x = __builtin_popcount(255);]
+)],
+[pgac_cv__builtin_popcount=yes],
+[pgac_cv__builtin_popcount=no])])
+if test x"$pgac_cv__builtin_popcount" = x"yes"; then
 AC_DEFINE(HAVE__BUILTIN_POPCOUNT, 1,
           [Define to 1 if your compiler understands __builtin_popcount.])
-fi
-undefine([Ac_cachevar])dnl
-])# PGAC_C_BUILTIN_POPCOUNT
+fi])# PGAC_C_BUILTIN_POPCOUNT
 
 
 
diff --git a/configure b/configure
@@ -651,7 +651,7 @@ CFLAGS_ARMV8_CRC32C
 CFLAGS_SSE42
 have_win32_dbghelp
 LIBOBJS
-CFLAGS_POPCNT
+have__builtin_popcount
 UUID_LIBS
 LDAP_LIBS_BE
 LDAP_LIBS_FE
@@ -733,6 +733,7 @@ CPP
 BITCODE_CXXFLAGS
 BITCODE_CFLAGS
 CFLAGS_VECTOR
+CFLAGS_POPCNT
 PERMIT_DECLARATION_AFTER_STATEMENT
 LLVM_BINPATH
 LLVM_CXXFLAGS
@@ -6581,6 +6582,48 @@ fi
 
 fi
 
+# Optimization flags and options for bit-twiddling
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking whether ${CC} supports -mpopcnt, for CFLAGS_POPCNT" >&5
+$as_echo_n "checking whether ${CC} supports -mpopcnt, for CFLAGS_POPCNT... " >&6; }
+if ${pgac_cv_prog_CC_cflags__mpopcnt+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  pgac_save_CFLAGS=$CFLAGS
+pgac_save_CC=$CC
+CC=${CC}
+CFLAGS="${CFLAGS_POPCNT} -mpopcnt"
+ac_save_c_werror_flag=$ac_c_werror_flag
+ac_c_werror_flag=yes
+cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+/* end confdefs.h.  */
+
+int
+main ()
+{
+
+  ;
+  return 0;
+}
+_ACEOF
+if ac_fn_c_try_compile "$LINENO"; then :
+  pgac_cv_prog_CC_cflags__mpopcnt=yes
+else
+  pgac_cv_prog_CC_cflags__mpopcnt=no
+fi
+rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
+ac_c_werror_flag=$ac_save_c_werror_flag
+CFLAGS="$pgac_save_CFLAGS"
+CC="$pgac_save_CC"
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv_prog_CC_cflags__mpopcnt" >&5
+$as_echo "$pgac_cv_prog_CC_cflags__mpopcnt" >&6; }
+if test x"$pgac_cv_prog_CC_cflags__mpopcnt" = x"yes"; then
+  CFLAGS_POPCNT="${CFLAGS_POPCNT} -mpopcnt"
+fi
+
+
+
+
 CFLAGS_VECTOR=$CFLAGS_VECTOR
 
 
@@ -14111,32 +14154,28 @@ $as_echo "#define HAVE__BUILTIN_CTZ 1" >>confdefs.h
 fi
 { $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_popcount" >&5
 $as_echo_n "checking for __builtin_popcount... " >&6; }
-if ${pgac_cv_popcount+:} false; then :
+if ${pgac_cv__builtin_popcount+:} false; then :
   $as_echo_n "(cached) " >&6
 else
-  pgac_save_CFLAGS=$CFLAGS
-CFLAGS="$pgac_save_CFLAGS -mpopcnt"
-cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
 /* end confdefs.h.  */
 static int x = __builtin_popcount(255);
+
 _ACEOF
 if ac_fn_c_try_compile "$LINENO"; then :
-  pgac_cv_popcount=yes
+  pgac_cv__builtin_popcount=yes
 else
-  pgac_cv_popcount=no
+  pgac_cv__builtin_popcount=no
 fi
 rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
-CFLAGS="$pgac_save_CFLAGS"
 fi
-{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv_popcount" >&5
-$as_echo "$pgac_cv_popcount" >&6; }
-if test x"$pgac_cv_popcount" = x"yes"; then
-  CFLAGS_POPCNT="-mpopcnt"
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_popcount" >&5
+$as_echo "$pgac_cv__builtin_popcount" >&6; }
+if test x"$pgac_cv__builtin_popcount" = x"yes"; then
 
 $as_echo "#define HAVE__BUILTIN_POPCOUNT 1" >>confdefs.h
 
 fi
-
 { $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_unreachable" >&5
 $as_echo_n "checking for __builtin_unreachable... " >&6; }
 if ${pgac_cv__builtin_unreachable+:} false; then :
@@ -14654,6 +14693,7 @@ $as_echo "#define LOCALE_T_IN_XLOCALE 1" >>confdefs.h
 
 fi
 
+have__builtin_popcount=$pgac_cv__builtin_popcount
 
 
 # MSVC doesn't cope well with defining restrict to __restrict, the
diff --git a/configure.in b/configure.in
@@ -547,6 +547,10 @@ elif test "$PORTNAME" = "hpux"; then
   PGAC_PROG_CXX_CFLAGS_OPT([+Olibmerrno])
 fi
 
+# Optimization flags and options for bit-twiddling
+PGAC_PROG_CC_VAR_OPT(CFLAGS_POPCNT, [-mpopcnt])
+AC_SUBST(CFLAGS_POPCNT)
+
 AC_SUBST(CFLAGS_VECTOR, $CFLAGS_VECTOR)
 
 # Determine flags used to emit bitcode for JIT inlining. Need to test
@@ -1506,7 +1510,7 @@ AC_TYPE_LONG_LONG_INT
 
 PGAC_TYPE_LOCALE_T
 
-AC_SUBST(CFLAGS_POPCNT)
+AC_SUBST(have__builtin_popcount, $pgac_cv__builtin_popcount)
 
 # MSVC doesn't cope well with defining restrict to __restrict, the
 # spelling it understands, because it conflicts with
diff --git a/src/Makefile.global.in b/src/Makefile.global.in
@@ -517,6 +517,9 @@ WIN32_STACK_RLIMIT=4194304
 # Set if we have a working win32 crashdump header
 have_win32_dbghelp = @have_win32_dbghelp@
 
+# Set if __builtin_popcount() is supported by $(CC)
+have__builtin_popcount = @have__builtin_popcount@
+
 # Pull in platform-specific magic
 include $(top_builddir)/src/Makefile.port
 
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
@@ -10,17 +10,177 @@
  *
  *------------------------------------------------------------------------ -
  */
-
 #ifndef PG_BITUTILS_H
 #define PG_BITUTILS_H
 
-extern int (*pg_popcount32) (uint32 word);
-extern int (*pg_popcount64) (uint64 word);
-extern int (*pg_rightmost_one32) (uint32 word);
-extern int (*pg_rightmost_one64) (uint64 word);
-extern int (*pg_leftmost_one32) (uint32 word);
-extern int (*pg_leftmost_one64) (uint64 word);
-
+extern int	(*pg_popcount32) (uint32 word);
+extern int	(*pg_popcount64) (uint64 word);
 extern uint64 pg_popcount(const char *buf, int bytes);
 
+/* in pg_bitutils_hwpopcnt.c */
+extern int	pg_popcount32_hw(uint32 word);
+extern int	pg_popcount64_hw(uint64 word);
+
+
+#ifndef HAVE__BUILTIN_CTZ
+/*
+ * Array marking the position of the right-most set bit for each value of
+ * 1-255.  We count the right-most position as the 0th bit, and the
+ * left-most the 7th bit.  The 0th index of the array must not be used.
+ */
+static const uint8 rightmost_one_pos[256] = {
+	0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+	4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
+};
+#endif							/* !HAVE__BUILTIN_CTZ */
+
+/*
+ * pg_rightmost_one32
+ *		Returns the number of trailing 0-bits in word, starting at the least
+ *		significant bit position. word must not be 0.
+ */
+static inline int
+pg_rightmost_one32(uint32 word)
+{
+	int			result = 0;
+
+	Assert(word != 0);
+
+#ifdef HAVE__BUILTIN_CTZ
+	result = __builtin_ctz(word);
+#else
+	while ((word & 255) == 0)
+	{
+		word >>= 8;
+		result += 8;
+	}
+	result += rightmost_one_pos[word & 255];
+#endif							/* HAVE__BUILTIN_CTZ */
+
+	return result;
+}
+
+/*
+ * pg_rightmost_one64
+ *		Returns the number of trailing 0-bits in word, starting at the least
+ *		significant bit position. word must not be 0.
+ */
+static inline int
+pg_rightmost_one64(uint64 word)
+{
+	int			result = 0;
+
+	Assert(word != 0);
+#ifdef HAVE__BUILTIN_CTZ
+#if defined(HAVE_LONG_INT_64)
+	return __builtin_ctzl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+	return __builtin_ctzll(word);
+#else
+#error must have a working 64-bit integer datatype
+#endif
+#else							/* HAVE__BUILTIN_CTZ */
+	while ((word & 255) == 0)
+	{
+		word >>= 8;
+		result += 8;
+	}
+	result += rightmost_one_pos[word & 255];
+#endif
+
+	return result;
+}
+
+#ifndef HAVE__BUILTIN_CLZ
+/*
+ * Array marking the position of the left-most set bit for each value of
+ * 1-255.  We count the right-most position as the 0th bit, and the
+ * left-most the 7th bit.  The 0th index of the array must not be used.
+ */
+static const uint8 leftmost_one_pos[256] = {
+	0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
+	4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
+	5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+	5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
+};
+#endif							/* !HAVE_BUILTIN_CLZ */
+
+/*
+ * pg_leftmost_one32
+ *		Returns the 0-based position of the most significant set bit in word
+ *		measured from the least significant bit.  word must not be 0.
+ */
+static inline int
+pg_leftmost_one32(uint32 word)
+{
+#ifdef HAVE__BUILTIN_CLZ
+	Assert(word != 0);
+
+	return 31 - __builtin_clz(word);
+#else
+	int			shift = 32 - 8;
+
+	Assert(word != 0);
+
+	while ((word >> shift) == 0)
+		shift -= 8;
+
+	return shift + leftmost_one_pos[(word >> shift) & 255];
+#endif							/* HAVE__BUILTIN_CLZ */
+}
+
+/*
+ * pg_leftmost_one64
+ *		Returns the 0-based position of the most significant set bit in word
+ *		measured from the least significant bit.  word must not be 0.
+ */
+static inline int
+pg_leftmost_one64(uint64 word)
+{
+#ifdef HAVE__BUILTIN_CLZ
+	Assert(word != 0);
+#if defined(HAVE_LONG_INT_64)
+	return 63 - __builtin_clzl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+	return 63 - __builtin_clzll(word);
+#else
+#error must have a working 64-bit integer datatype
+#endif
+#else							/* HAVE__BUILTIN_CLZ */
+	int			shift = 64 - 8;
+
+	Assert(word != 0);
+	while ((word >> shift) == 0)
+		shift -= 8;
+
+	return shift + leftmost_one_pos[(word >> shift) & 255];
+#endif							/* !HAVE__BUIILTIN_CLZ */
+}
+
 #endif							/* PG_BITUTILS_H */
diff --git a/src/port/Makefile b/src/port/Makefile
@@ -41,6 +41,14 @@ OBJS = $(LIBOBJS) $(PG_CRC32C_OBJS) chklocale.o erand48.o inet_net_ntop.o \
 	qsort.o qsort_arg.o quotes.o snprintf.o sprompt.o strerror.o \
 	tar.o thread.o
 
+# If the compiler supports a special flag for the POPCOUNT instruction and it
+# has __builtin_popcount, add pg_bitutils_hwpopcnt.o.
+ifneq ($(CFLAGS_POPCNT),)
+ifeq ($(have__builtin_popcount),yes)
+OBJS += pg_bitutils_hwpopcnt.o
+endif
+endif
+
 # libpgport.a, libpgport_shlib.a, and libpgport_srv.a contain the same files
 # foo.o, foo_shlib.o, and foo_srv.o are all built from foo.c
 OBJS_SHLIB = $(OBJS:%.o=%_shlib.o)
@@ -78,10 +86,10 @@ pg_crc32c_armv8.o: CFLAGS+=$(CFLAGS_ARMV8_CRC32C)
 pg_crc32c_armv8_shlib.o: CFLAGS+=$(CFLAGS_ARMV8_CRC32C)
 pg_crc32c_armv8_srv.o: CFLAGS+=$(CFLAGS_ARMV8_CRC32C)
 
-# pg_bitutils.c needs CFLAGS_POPCNT
-pg_bitutils.o: CFLAGS+=$(CFLAGS_POPCNT)
-pg_bitutils_shlib.o: CFLAGS+=$(CFLAGS_POPCNT)
-pg_bitutils_srv.o: CFLAGS+=$(CFLAGS_POPCNT)
+# all versions of pg_bitutils_hwpopcnt.c need CFLAGS_POPCNT
+pg_bitutils_hwpopcnt.o: CFLAGS+=$(CFLAGS_POPCNT)
+pg_bitutils_hwpopcnt_shlib.o: CFLAGS+=$(CFLAGS_POPCNT)
+pg_bitutils_hwpopcnt_srv.o: CFLAGS+=$(CFLAGS_POPCNT)
 
 #
 # Shared library versions of object files
diff --git a/src/port/pg_bitutils.c b/src/port/pg_bitutils.c
diff --git a/src/port/pg_bitutils_hwpopcnt.c b/src/port/pg_bitutils_hwpopcnt.c
