Using POPCNT and other advanced bit manipulation instructions

From 64818390701a3787266fc95a39aaaf787cc906e2 Mon Sep 17 00:00:00 2001
From: "dgrowley@gmail.com" <dgrowley@gmail.com>
Date: Thu, 20 Dec 2018 17:46:35 +1300
Subject: [PATCH v2] Add basic support for using the POPCNT and SSE4.2s LZCNT
 opcodes

These opcodes have been around in the AMD world since 2007, and 2008 in
the case of intel. They're supported in GCC and Clang via some __builtin
macros.  The opcodes may be unavailable during runtime, in which case we
fall back on a C-based implementation of the code.  In order to get the
POPCNT instruction we must pass the -mpopcnt option to the compiler.  We
do this only for the pg_bitutils.c file.

David Rowley (with fragments taken from a patch by Thomas Munro)
---
 config/c-compiler.m4                    | 116 +++++++
 configure                               | 155 ++++++++++
 configure.in                            |   8 +
 src/Makefile.global.in                  |   1 +
 src/backend/access/heap/visibilitymap.c |  73 ++---
 src/backend/lib/bloomfilter.c           |  15 +-
 src/backend/nodes/bitmapset.c           | 131 ++------
 src/include/pg_config.h.in              |  18 ++
 src/include/pg_config.h.win32           |  18 ++
 src/include/port/pg_bitutils.h          |  26 ++
 src/port/Makefile                       |   5 +-
 src/port/pg_bitutils.c                  | 516 ++++++++++++++++++++++++++++++++
 src/tools/msvc/Mkvcbuild.pm             |   1 +
 13 files changed, 914 insertions(+), 169 deletions(-)
 create mode 100644 src/include/port/pg_bitutils.h
 create mode 100644 src/port/pg_bitutils.c

diff --git a/config/c-compiler.m4 b/config/c-compiler.m4
index af2dea1c2a..7cdcaee0b2 100644
--- a/config/c-compiler.m4
+++ b/config/c-compiler.m4
@@ -378,6 +378,122 @@ 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_DEFINE(HAVE__BUILTIN_POPCOUNT, 1,
+          [Define to 1 if your compiler understands __builtin_popcount.])
+fi
+undefine([Ac_cachevar])dnl
+])# PGAC_C_BUILTIN_POPCOUNT
+
+
+
+# PGAC_C_BUILTIN_POPCOUNTL
+# -------------------------
+AC_DEFUN([PGAC_C_BUILTIN_POPCOUNTL],
+[define([Ac_cachevar], [AS_TR_SH([pgac_cv_popcountl])])dnl
+AC_CACHE_CHECK([for __builtin_popcountl], [Ac_cachevar],
+[pgac_save_CFLAGS=$CFLAGS
+CFLAGS="$pgac_save_CFLAGS -mpopcnt"
+AC_COMPILE_IFELSE([AC_LANG_SOURCE(
+[static int x = __builtin_popcountl(255);])],
+[Ac_cachevar=yes],
+[Ac_cachevar=no])
+CFLAGS="$pgac_save_CFLAGS"])
+if test x"$Ac_cachevar" = x"yes"; then
+  CFLAGS_POPCNT="-mpopcnt"
+AC_DEFINE(HAVE__BUILTIN_POPCOUNTL, 1,
+          [Define to 1 if your compiler understands __builtin_popcountl.])
+fi
+undefine([Ac_cachevar])dnl
+])# PGAC_C_BUILTIN_POPCOUNTL
+
+
+
+# PGAC_C_BUILTIN_CTZ
+# -------------------------
+# Check if the C compiler understands __builtin_ctz(),
+# and define HAVE__BUILTIN_CTZ if so.
+AC_DEFUN([PGAC_C_BUILTIN_CTZ],
+[AC_CACHE_CHECK(for __builtin_ctz, pgac_cv__builtin_ctz,
+[AC_COMPILE_IFELSE([AC_LANG_SOURCE(
+[static int x = __builtin_ctz(256);]
+)],
+[pgac_cv__builtin_ctz=yes],
+[pgac_cv__builtin_ctz=no])])
+if test x"$pgac_cv__builtin_ctz" = xyes ; then
+AC_DEFINE(HAVE__BUILTIN_CTZ, 1,
+          [Define to 1 if your compiler understands __builtin_ctz.])
+fi])# PGAC_C_BUILTIN_CTZ
+
+
+
+# PGAC_C_BUILTIN_CTZL
+# -------------------------
+# Check if the C compiler understands __builtin_ctzl(),
+# and define HAVE__BUILTIN_CTZL if so.
+AC_DEFUN([PGAC_C_BUILTIN_CTZL],
+[AC_CACHE_CHECK(for __builtin_ctzl, pgac_cv__builtin_ctzl,
+[AC_COMPILE_IFELSE([AC_LANG_SOURCE(
+[static int x = __builtin_ctzl(256);]
+)],
+[pgac_cv__builtin_ctzl=yes],
+[pgac_cv__builtin_ctzl=no])])
+if test x"$pgac_cv__builtin_ctzl" = xyes ; then
+AC_DEFINE(HAVE__BUILTIN_CTZL, 1,
+          [Define to 1 if your compiler understands __builtin_ctzl.])
+fi])# PGAC_C_BUILTIN_CTZL
+
+
+
+# PGAC_C_BUILTIN_CLZ
+# -------------------------
+# Check if the C compiler understands __builtin_clz(),
+# and define HAVE__BUILTIN_CLZ if so.
+AC_DEFUN([PGAC_C_BUILTIN_CLZ],
+[AC_CACHE_CHECK(for __builtin_clz, pgac_cv__builtin_clz,
+[AC_COMPILE_IFELSE([AC_LANG_SOURCE(
+[static int x = __builtin_clz(256);]
+)],
+[pgac_cv__builtin_clz=yes],
+[pgac_cv__builtin_clz=no])])
+if test x"$pgac_cv__builtin_clz" = xyes ; then
+AC_DEFINE(HAVE__BUILTIN_CLZ, 1,
+          [Define to 1 if your compiler understands __builtin_clz.])
+fi])# PGAC_C_BUILTIN_CLZ
+
+
+
+# PGAC_C_BUILTIN_CLZL
+# -------------------------
+# Check if the C compiler understands __builtin_clzl(),
+# and define HAVE__BUILTIN_CLZL if so.
+AC_DEFUN([PGAC_C_BUILTIN_CLZL],
+[AC_CACHE_CHECK(for __builtin_clzl, pgac_cv__builtin_clzl,
+[AC_COMPILE_IFELSE([AC_LANG_SOURCE(
+[static int x = __builtin_clzl(256);]
+)],
+[pgac_cv__builtin_clzl=yes],
+[pgac_cv__builtin_clzl=no])])
+if test x"$pgac_cv__builtin_clzl" = xyes ; then
+AC_DEFINE(HAVE__BUILTIN_CLZL, 1,
+          [Define to 1 if your compiler understands __builtin_clzl.])
+fi])# PGAC_C_BUILTIN_CLZL
+
+
+
 # PGAC_C_BUILTIN_UNREACHABLE
 # --------------------------
 # Check if the C compiler understands __builtin_unreachable(),
diff --git a/configure b/configure
index ddb3c8b1ba..0e2f8da274 100755
--- a/configure
+++ b/configure
@@ -651,6 +651,7 @@ CFLAGS_ARMV8_CRC32C
 CFLAGS_SSE42
 have_win32_dbghelp
 LIBOBJS
+CFLAGS_POPCNT
 UUID_LIBS
 LDAP_LIBS_BE
 LDAP_LIBS_FE
@@ -14057,6 +14058,158 @@ if test x"$pgac_cv__builtin_constant_p" = xyes ; then
 
 $as_echo "#define HAVE__BUILTIN_CONSTANT_P 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 :
+  $as_echo_n "(cached) " >&6
+else
+  pgac_save_CFLAGS=$CFLAGS
+CFLAGS="$pgac_save_CFLAGS -mpopcnt"
+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
+else
+  pgac_cv_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 "#define HAVE__BUILTIN_POPCOUNT 1" >>confdefs.h
+
+fi
+
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_popcountl" >&5
+$as_echo_n "checking for __builtin_popcountl... " >&6; }
+if ${pgac_cv_popcountl+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  pgac_save_CFLAGS=$CFLAGS
+CFLAGS="$pgac_save_CFLAGS -mpopcnt"
+cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+/* end confdefs.h.  */
+static int x = __builtin_popcountl(255);
+_ACEOF
+if ac_fn_c_try_compile "$LINENO"; then :
+  pgac_cv_popcountl=yes
+else
+  pgac_cv_popcountl=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_popcountl" >&5
+$as_echo "$pgac_cv_popcountl" >&6; }
+if test x"$pgac_cv_popcountl" = x"yes"; then
+  CFLAGS_POPCNT="-mpopcnt"
+
+$as_echo "#define HAVE__BUILTIN_POPCOUNTL 1" >>confdefs.h
+
+fi
+
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_ctz" >&5
+$as_echo_n "checking for __builtin_ctz... " >&6; }
+if ${pgac_cv__builtin_ctz+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+/* end confdefs.h.  */
+static int x = __builtin_ctz(256);
+
+_ACEOF
+if ac_fn_c_try_compile "$LINENO"; then :
+  pgac_cv__builtin_ctz=yes
+else
+  pgac_cv__builtin_ctz=no
+fi
+rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_ctz" >&5
+$as_echo "$pgac_cv__builtin_ctz" >&6; }
+if test x"$pgac_cv__builtin_ctz" = xyes ; then
+
+$as_echo "#define HAVE__BUILTIN_CTZ 1" >>confdefs.h
+
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_ctzl" >&5
+$as_echo_n "checking for __builtin_ctzl... " >&6; }
+if ${pgac_cv__builtin_ctzl+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+/* end confdefs.h.  */
+static int x = __builtin_ctzl(256);
+
+_ACEOF
+if ac_fn_c_try_compile "$LINENO"; then :
+  pgac_cv__builtin_ctzl=yes
+else
+  pgac_cv__builtin_ctzl=no
+fi
+rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_ctzl" >&5
+$as_echo "$pgac_cv__builtin_ctzl" >&6; }
+if test x"$pgac_cv__builtin_ctzl" = xyes ; then
+
+$as_echo "#define HAVE__BUILTIN_CTZL 1" >>confdefs.h
+
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_clz" >&5
+$as_echo_n "checking for __builtin_clz... " >&6; }
+if ${pgac_cv__builtin_clz+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+/* end confdefs.h.  */
+static int x = __builtin_clz(256);
+
+_ACEOF
+if ac_fn_c_try_compile "$LINENO"; then :
+  pgac_cv__builtin_clz=yes
+else
+  pgac_cv__builtin_clz=no
+fi
+rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_clz" >&5
+$as_echo "$pgac_cv__builtin_clz" >&6; }
+if test x"$pgac_cv__builtin_clz" = xyes ; then
+
+$as_echo "#define HAVE__BUILTIN_CLZ 1" >>confdefs.h
+
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_clzl" >&5
+$as_echo_n "checking for __builtin_clzl... " >&6; }
+if ${pgac_cv__builtin_clzl+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+/* end confdefs.h.  */
+static int x = __builtin_clzl(256);
+
+_ACEOF
+if ac_fn_c_try_compile "$LINENO"; then :
+  pgac_cv__builtin_clzl=yes
+else
+  pgac_cv__builtin_clzl=no
+fi
+rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $pgac_cv__builtin_clzl" >&5
+$as_echo "$pgac_cv__builtin_clzl" >&6; }
+if test x"$pgac_cv__builtin_clzl" = xyes ; then
+
+$as_echo "#define HAVE__BUILTIN_CLZL 1" >>confdefs.h
+
 fi
 { $as_echo "$as_me:${as_lineno-$LINENO}: checking for __builtin_unreachable" >&5
 $as_echo_n "checking for __builtin_unreachable... " >&6; }
@@ -14575,6 +14728,8 @@ $as_echo "#define LOCALE_T_IN_XLOCALE 1" >>confdefs.h
 
 fi
 
+
+
 # MSVC doesn't cope well with defining restrict to __restrict, the
 # spelling it understands, because it conflicts with
 # __declspec(restrict). Therefore we define pg_restrict to the
diff --git a/configure.in b/configure.in
index 3d8888805c..e4af9aa1a8 100644
--- a/configure.in
+++ b/configure.in
@@ -1482,6 +1482,12 @@ PGAC_C_BUILTIN_BSWAP16
 PGAC_C_BUILTIN_BSWAP32
 PGAC_C_BUILTIN_BSWAP64
 PGAC_C_BUILTIN_CONSTANT_P
+PGAC_C_BUILTIN_POPCOUNT
+PGAC_C_BUILTIN_POPCOUNTL
+PGAC_C_BUILTIN_CTZ
+PGAC_C_BUILTIN_CTZL
+PGAC_C_BUILTIN_CLZ
+PGAC_C_BUILTIN_CLZL
 PGAC_C_BUILTIN_UNREACHABLE
 PGAC_C_COMPUTED_GOTO
 PGAC_STRUCT_TIMEZONE
@@ -1496,6 +1502,8 @@ AC_TYPE_LONG_LONG_INT
 
 PGAC_TYPE_LOCALE_T
 
+AC_SUBST(CFLAGS_POPCNT)
+
 # MSVC doesn't cope well with defining restrict to __restrict, the
 # spelling it understands, because it conflicts with
 # __declspec(restrict). Therefore we define pg_restrict to the
diff --git a/src/Makefile.global.in b/src/Makefile.global.in
index 6852853041..bd515376b3 100644
--- a/src/Makefile.global.in
+++ b/src/Makefile.global.in
@@ -260,6 +260,7 @@ CXX = @CXX@
 CFLAGS = @CFLAGS@
 CFLAGS_VECTOR = @CFLAGS_VECTOR@
 CFLAGS_SSE42 = @CFLAGS_SSE42@
+CFLAGS_POPCNT = @CFLAGS_POPCNT@
 CFLAGS_ARMV8_CRC32C = @CFLAGS_ARMV8_CRC32C@
 CXXFLAGS = @CXXFLAGS@
 
diff --git a/src/backend/access/heap/visibilitymap.c b/src/backend/access/heap/visibilitymap.c
index 931ae81fd6..9657cd0a63 100644
--- a/src/backend/access/heap/visibilitymap.c
+++ b/src/backend/access/heap/visibilitymap.c
@@ -89,12 +89,12 @@
 #include "access/visibilitymap.h"
 #include "access/xlog.h"
 #include "miscadmin.h"
+#include "port/pg_bitutils.h"
 #include "storage/bufmgr.h"
 #include "storage/lmgr.h"
 #include "storage/smgr.h"
 #include "utils/inval.h"
 
-
 /*#define TRACE_VISIBILITYMAP */
 
 /*
@@ -115,43 +115,9 @@
 #define HEAPBLK_TO_MAPBYTE(x) (((x) % HEAPBLOCKS_PER_PAGE) / HEAPBLOCKS_PER_BYTE)
 #define HEAPBLK_TO_OFFSET(x) (((x) % HEAPBLOCKS_PER_BYTE) * BITS_PER_HEAPBLOCK)
 
-/* tables for fast counting of set bits for visible and frozen */
-static const uint8 number_of_ones_for_visible[256] = {
-	0, 1, 0, 1, 1, 2, 1, 2, 0, 1, 0, 1, 1, 2, 1, 2,
-	1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3,
-	0, 1, 0, 1, 1, 2, 1, 2, 0, 1, 0, 1, 1, 2, 1, 2,
-	1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3,
-	1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3,
-	2, 3, 2, 3, 3, 4, 3, 4, 2, 3, 2, 3, 3, 4, 3, 4,
-	1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3,
-	2, 3, 2, 3, 3, 4, 3, 4, 2, 3, 2, 3, 3, 4, 3, 4,
-	0, 1, 0, 1, 1, 2, 1, 2, 0, 1, 0, 1, 1, 2, 1, 2,
-	1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3,
-	0, 1, 0, 1, 1, 2, 1, 2, 0, 1, 0, 1, 1, 2, 1, 2,
-	1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3,
-	1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3,
-	2, 3, 2, 3, 3, 4, 3, 4, 2, 3, 2, 3, 3, 4, 3, 4,
-	1, 2, 1, 2, 2, 3, 2, 3, 1, 2, 1, 2, 2, 3, 2, 3,
-	2, 3, 2, 3, 3, 4, 3, 4, 2, 3, 2, 3, 3, 4, 3, 4
-};
-static const uint8 number_of_ones_for_frozen[256] = {
-	0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2,
-	0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2,
-	1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3,
-	1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3,
-	0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2,
-	0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2,
-	1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3,
-	1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3,
-	1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3,
-	1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3,
-	2, 2, 3, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 3, 4, 4,
-	2, 2, 3, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 3, 4, 4,
-	1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3,
-	1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3, 2, 2, 3, 3,
-	2, 2, 3, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 3, 4, 4,
-	2, 2, 3, 3, 2, 2, 3, 3, 3, 3, 4, 4, 3, 3, 4, 4
-};
+/* Masks for bit counting bits in the visibility map. */
+#define VISIBLE_MASK64 0x5555555555555555 /* The lower bit of each bit pair */
+#define FROZEN_MASK64 0xaaaaaaaaaaaaaaaa /* The upper bit of each bit pair */
 
 /* prototypes for internal routines */
 static Buffer vm_readbuf(Relation rel, BlockNumber blkno, bool extend);
@@ -408,18 +374,16 @@ void
 visibilitymap_count(Relation rel, BlockNumber *all_visible, BlockNumber *all_frozen)
 {
 	BlockNumber mapBlock;
+	BlockNumber nvisible = 0;
+	BlockNumber nfrozen = 0;
 
 	/* all_visible must be specified */
 	Assert(all_visible);
 
-	*all_visible = 0;
-	if (all_frozen)
-		*all_frozen = 0;
-
 	for (mapBlock = 0;; mapBlock++)
 	{
 		Buffer		mapBuffer;
-		unsigned char *map;
+		uint64	   *map;
 		int			i;
 
 		/*
@@ -436,17 +400,30 @@ visibilitymap_count(Relation rel, BlockNumber *all_visible, BlockNumber *all_fro
 		 * immediately stale anyway if anyone is concurrently setting or
 		 * clearing bits, and we only really need an approximate value.
 		 */
-		map = (unsigned char *) PageGetContents(BufferGetPage(mapBuffer));
+		map = (uint64 *) PageGetContents(BufferGetPage(mapBuffer));
 
-		for (i = 0; i < MAPSIZE; i++)
+		StaticAssertStmt(MAPSIZE % sizeof(uint64) == 0,
+						 "unsupported MAPSIZE");
+		if (all_frozen == NULL)
+		{
+			for (i = 0; i < MAPSIZE / sizeof(uint64); i++)
+				nvisible += pg_popcount64(map[i] & VISIBLE_MASK64);
+		}
+		else
 		{
-			*all_visible += number_of_ones_for_visible[map[i]];
-			if (all_frozen)
-				*all_frozen += number_of_ones_for_frozen[map[i]];
+			for (i = 0; i < MAPSIZE / sizeof(uint64); i++)
+			{
+				nvisible += pg_popcount64(map[i] & VISIBLE_MASK64);
+				nfrozen += pg_popcount64(map[i] & FROZEN_MASK64);
+			}
 		}
 
 		ReleaseBuffer(mapBuffer);
 	}
+
+	*all_visible = nvisible;
+	if (all_frozen)
+		*all_frozen = nfrozen;
 }
 
 /*
diff --git a/src/backend/lib/bloomfilter.c b/src/backend/lib/bloomfilter.c
index 1e907cabc6..e2c1276f21 100644
--- a/src/backend/lib/bloomfilter.c
+++ b/src/backend/lib/bloomfilter.c
@@ -37,6 +37,7 @@
 
 #include "access/hash.h"
 #include "lib/bloomfilter.h"
+#include "port/pg_bitutils.h"
 
 #define MAX_HASH_FUNCS		10
 
@@ -187,19 +188,7 @@ double
 bloom_prop_bits_set(bloom_filter *filter)
 {
 	int			bitset_bytes = filter->m / BITS_PER_BYTE;
-	uint64		bits_set = 0;
-	int			i;
-
-	for (i = 0; i < bitset_bytes; i++)
-	{
-		unsigned char byte = filter->bitset[i];
-
-		while (byte)
-		{
-			bits_set++;
-			byte &= (byte - 1);
-		}
-	}
+	uint64		bits_set = pg_popcount((char *) filter->bitset, bitset_bytes);
 
 	return bits_set / (double) filter->m;
 }
diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
index 62cd00903c..d0380abf3e 100644
--- a/src/backend/nodes/bitmapset.c
+++ b/src/backend/nodes/bitmapset.c
@@ -22,6 +22,7 @@
 
 #include "access/hash.h"
 #include "nodes/pg_list.h"
+#include "port/pg_bitutils.h"
 
 
 #define WORDNUM(x)	((x) / BITS_PER_BITMAPWORD)
@@ -51,79 +52,23 @@
 
 #define HAS_MULTIPLE_ONES(x)	((bitmapword) RIGHTMOST_ONE(x) != (x))
 
+/* Set the bitwise macro version we must use based on the bitmapword size */
+#if BITS_PER_BITMAPWORD == 32
 
-/*
- * Lookup tables to avoid need for bit-by-bit groveling
- *
- * rightmost_one_pos[x] gives the bit number (0-7) of the rightmost one bit
- * in a nonzero byte value x.  The entry for x=0 is never used.
- *
- * leftmost_one_pos[x] gives the bit number (0-7) of the leftmost one bit in a
- * nonzero byte value x.  The entry for x=0 is never used.
- *
- * number_of_ones[x] gives the number of one-bits (0-8) in a byte value x.
- *
- * We could make these tables larger and reduce the number of iterations
- * in the functions that use them, but bytewise shifts and masks are
- * especially fast on many machines, so working a byte at a time seems best.
- */
+#define bmw_popcount(w)			pg_popcount32(w)
+#define bmw_rightmost_one(w)	pg_rightmost_one32(w)
+#define bmw_leftmost_one(w)		pg_leftmost_one32(w)
+
+#elif BITS_PER_BITMAPWORD == 64
+
+#define bmw_popcount(w)			pg_popcount64(w)
+#define bmw_rightmost_one(w)	pg_rightmost_one64(w)
+#define bmw_leftmost_one(w)		pg_leftmost_one64(w)
+
+#else
+#error "invalid BITS_PER_BITMAPWORD"
+#endif
 
-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
-};
-
-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
-};
-
-static const uint8 number_of_ones[256] = {
-	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
-	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
-};
 
 
 /*
@@ -607,12 +552,7 @@ bms_singleton_member(const Bitmapset *a)
 			if (result >= 0 || HAS_MULTIPLE_ONES(w))
 				elog(ERROR, "bitmapset has multiple members");
 			result = wordnum * BITS_PER_BITMAPWORD;
-			while ((w & 255) == 0)
-			{
-				w >>= 8;
-				result += 8;
-			}
-			result += rightmost_one_pos[w & 255];
+			result += bmw_rightmost_one(w);
 		}
 	}
 	if (result < 0)
@@ -650,12 +590,7 @@ bms_get_singleton_member(const Bitmapset *a, int *member)
 			if (result >= 0 || HAS_MULTIPLE_ONES(w))
 				return false;
 			result = wordnum * BITS_PER_BITMAPWORD;
-			while ((w & 255) == 0)
-			{
-				w >>= 8;
-				result += 8;
-			}
-			result += rightmost_one_pos[w & 255];
+			result += bmw_rightmost_one(w);
 		}
 	}
 	if (result < 0)
@@ -681,12 +616,9 @@ bms_num_members(const Bitmapset *a)
 	{
 		bitmapword	w = a->words[wordnum];
 
-		/* we assume here that bitmapword is an unsigned type */
-		while (w != 0)
-		{
-			result += number_of_ones[w & 255];
-			w >>= 8;
-		}
+		/* No need to count the bits in a zero word */
+		if (w != 0)
+			result += bmw_popcount(w);
 	}
 	return result;
 }
@@ -1041,12 +973,7 @@ bms_first_member(Bitmapset *a)
 			a->words[wordnum] &= ~w;
 
 			result = wordnum * BITS_PER_BITMAPWORD;
-			while ((w & 255) == 0)
-			{
-				w >>= 8;
-				result += 8;
-			}
-			result += rightmost_one_pos[w & 255];
+			result += bmw_rightmost_one(w);
 			return result;
 		}
 	}
@@ -1096,12 +1023,7 @@ bms_next_member(const Bitmapset *a, int prevbit)
 			int			result;
 
 			result = wordnum * BITS_PER_BITMAPWORD;
-			while ((w & 255) == 0)
-			{
-				w >>= 8;
-				result += 8;
-			}
-			result += rightmost_one_pos[w & 255];
+			result += bmw_rightmost_one(w);
 			return result;
 		}
 
@@ -1168,14 +1090,9 @@ bms_prev_member(const Bitmapset *a, int prevbit)
 		if (w != 0)
 		{
 			int			result;
-			int			shift = BITS_PER_BITMAPWORD - 8;
 
 			result = wordnum * BITS_PER_BITMAPWORD;
-
-			while ((w >> shift) == 0)
-				shift -= 8;
-
-			result += shift + leftmost_one_pos[(w >> shift) & 255];
+			result += bmw_leftmost_one(w);
 			return result;
 		}
 
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 82547f321f..e3b461a68c 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -751,6 +751,24 @@
 /* Define to 1 if your compiler understands __builtin_$op_overflow. */
 #undef HAVE__BUILTIN_OP_OVERFLOW
 
+/* Define to 1 if your compiler understands __builtin_popcount. */
+#undef HAVE__BUILTIN_POPCOUNT
+
+/* Define to 1 if your compiler understands __builtin_popcountl. */
+#undef HAVE__BUILTIN_POPCOUNTL
+
+/* Define to 1 if your compiler understands __builtin_ctz. */
+#undef HAVE__BUILTIN_CTZ
+
+/* Define to 1 if your compiler understands __builtin_ctzl. */
+#undef HAVE__BUILTIN_CTZL
+
+/* Define to 1 if your compiler understands __builtin_clz. */
+#undef HAVE__BUILTIN_CLZ
+
+/* Define to 1 if your compiler understands __builtin_clzl. */
+#undef HAVE__BUILTIN_CLZL
+
 /* Define to 1 if your compiler understands __builtin_types_compatible_p. */
 #undef HAVE__BUILTIN_TYPES_COMPATIBLE_P
 
diff --git a/src/include/pg_config.h.win32 b/src/include/pg_config.h.win32
index a3c44f0fd8..e85b42b57d 100644
--- a/src/include/pg_config.h.win32
+++ b/src/include/pg_config.h.win32
@@ -590,6 +590,24 @@
 /* Define to 1 if your compiler understands __builtin_$op_overflow. */
 /* #undef HAVE__BUILTIN_OP_OVERFLOW */
 
+/* Define to 1 if your compiler understands __builtin_popcount. */
+/* #undef HAVE__BUILTIN_POPCOUNT */
+
+/* Define to 1 if your compiler understands __builtin_popcountl. */
+/* #undef HAVE__BUILTIN_POPCOUNTL */
+
+/* Define to 1 if your compiler understands __builtin_ctz. */
+/* #undef HAVE__BUILTIN_CTZ */
+
+/* Define to 1 if your compiler understands __builtin_ctzl. */
+/* #undef HAVE__BUILTIN_CTZL */
+
+/* Define to 1 if your compiler understands __builtin_clz. */
+/* #undef HAVE__BUILTIN_CLZ */
+
+/* Define to 1 if your compiler understands __builtin_clzl. */
+/* #undef HAVE__BUILTIN_CLZL */
+
 /* Define to 1 if your compiler understands __builtin_types_compatible_p. */
 /* #undef HAVE__BUILTIN_TYPES_COMPATIBLE_P */
 
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
new file mode 100644
index 0000000000..148c555057
--- /dev/null
+++ b/src/include/port/pg_bitutils.h
@@ -0,0 +1,26 @@
+/*------------------------------------------------------------------------ -
+ *
+ * pg_bitutils.h
+ *	  miscellaneous functions for bit-wise operations.
+  *
+ *
+ * Portions Copyright(c) 2019, PostgreSQL Global Development Group
+ *
+ * src/include/port/pg_bitutils.h
+ *
+ *------------------------------------------------------------------------ -
+ */
+
+#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 uint64 pg_popcount(const char *buf, int bytes);
+
+#endif							/* PG_BITUTILS_H */
diff --git a/src/port/Makefile b/src/port/Makefile
index 9cfc0f9279..df2e26b0a1 100644
--- a/src/port/Makefile
+++ b/src/port/Makefile
@@ -36,7 +36,7 @@ override CPPFLAGS := -I$(top_builddir)/src/port -DFRONTEND $(CPPFLAGS)
 LIBS += $(PTHREAD_LIBS)
 
 OBJS = $(LIBOBJS) $(PG_CRC32C_OBJS) chklocale.o erand48.o inet_net_ntop.o \
-	noblock.o path.o pgcheckdir.o pgmkdirp.o pgsleep.o \
+	noblock.o path.o pg_bitutils.o pgcheckdir.o pgmkdirp.o pgsleep.o \
 	pg_strong_random.o pgstrcasecmp.o pgstrsignal.o pqsignal.o \
 	qsort.o qsort_arg.o quotes.o snprintf.o sprompt.o strerror.o \
 	tar.o thread.o
@@ -73,6 +73,9 @@ pg_crc32c_sse42.o: CFLAGS+=$(CFLAGS_SSE42)
 pg_crc32c_sse42_shlib.o: CFLAGS+=$(CFLAGS_SSE42)
 pg_crc32c_sse42_srv.o: CFLAGS+=$(CFLAGS_SSE42)
 
+# pg_bitutils.c needs CFLAGS_POPCNT
+pg_bitutils.o: CFLAGS+=$(CFLAGS_POPCNT)
+
 # all versions of pg_crc32c_armv8.o need CFLAGS_ARMV8_CRC32C
 pg_crc32c_armv8.o: CFLAGS+=$(CFLAGS_ARMV8_CRC32C)
 pg_crc32c_armv8_shlib.o: CFLAGS+=$(CFLAGS_ARMV8_CRC32C)
diff --git a/src/port/pg_bitutils.c b/src/port/pg_bitutils.c
new file mode 100644
index 0000000000..97422e0504
--- /dev/null
+++ b/src/port/pg_bitutils.c
@@ -0,0 +1,516 @@
+/*-------------------------------------------------------------------------
+ *
+ * pg_bitutils.c
+ *	  miscellaneous functions for bit-wise operations.
+ *
+ * Portions Copyright (c) 2019, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/port/pg_bitutils.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#ifdef HAVE__GET_CPUID
+#include <cpuid.h>
+#endif
+
+#ifdef HAVE__CPUID
+#include <intrin.h>
+#endif
+
+#include "port/pg_bitutils.h"
+
+#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_POPCOUNT) || defined(HAVE__BUILTIN_POPCOUNTL))
+static bool pg_popcount_available(void);
+#endif
+
+#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
+static int pg_popcount32_choose(uint32 word);
+static int pg_popcount32_sse42(uint32 word);
+#endif
+static int pg_popcount32_slow(uint32 word);
+
+#if defined(HAVE__BUILTIN_POPCOUNTL) && defined(HAVE__GET_CPUID)
+static int pg_popcount64_choose(uint64 word);
+static int pg_popcount64_sse42(uint64 word);
+#endif
+static int pg_popcount64_slow(uint64 word);
+
+#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CTZL) || defined(HAVE__BUILTIN_CLZ) || defined(HAVE__BUILTIN_CLZL))
+static bool pg_lzcnt_available(void);
+#endif
+
+#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
+static int pg_rightmost_one32_choose(uint32 word);
+static int pg_rightmost_one32_abm(uint32 word);
+#endif
+static int pg_rightmost_one32_slow(uint32 word);
+
+#if defined(HAVE__BUILTIN_CTZL) && defined(HAVE__GET_CPUID)
+static int pg_rightmost_one64_choose(uint64 word);
+static int pg_rightmost_one64_abm(uint64 word);
+#endif
+static int pg_rightmost_one64_slow(uint64 word);
+
+#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
+static int pg_leftmost_one32_choose(uint32 word);
+static int pg_leftmost_one32_abm(uint32 word);
+#endif
+static int pg_leftmost_one32_slow(uint32 word);
+
+#if defined(HAVE__BUILTIN_CLZL) && defined(HAVE__GET_CPUID)
+static int pg_leftmost_one64_choose(uint64 word);
+static int pg_leftmost_one64_abm(uint64 word);
+#endif
+static int pg_leftmost_one64_slow(uint64 word);
+
+#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
+int (*pg_popcount32) (uint32 word) = pg_popcount32_choose;
+#else
+int (*pg_popcount32) (uint32 word) = pg_popcount32_slow;
+#endif
+
+#if defined(HAVE__BUILTIN_POPCOUNTL) && defined(HAVE__GET_CPUID)
+int (*pg_popcount64) (uint64 word) = pg_popcount64_choose;
+#else
+int (*pg_popcount64) (uint64 word) = pg_popcount64_slow;
+#endif
+
+#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
+int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_choose;
+#else
+int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_slow;
+#endif
+
+#if defined(HAVE__BUILTIN_CTZL) && defined(HAVE__GET_CPUID)
+int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_choose;
+#else
+int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_slow;
+#endif
+
+#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
+int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_choose;
+#else
+int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_slow;
+#endif
+
+#if defined(HAVE__BUILTIN_CLZL) && defined(HAVE__GET_CPUID)
+int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_choose;
+#else
+int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_slow;
+#endif
+
+
+/* Array marking the number of 1-bits for each value of 0-255. */
+static const uint8 number_of_ones[256] = {
+	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
+	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
+};
+
+/*
+ * 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
+};
+
+/*
+ * 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
+};
+
+#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_POPCOUNT) || defined(HAVE__BUILTIN_POPCOUNTL))
+
+static bool
+pg_popcount_available(void)
+{
+	unsigned int exx[4] = { 0, 0, 0, 0 };
+
+#if defined(HAVE__GET_CPUID)
+	__get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
+#elif defined(HAVE__CPUID)
+	__cpuid(exx, 1);
+#else
+#error cpuid instruction not available
+#endif
+
+	return (exx[2] & (1 << 23)) != 0;	/* POPCNT */
+}
+#endif
+
+#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
+
+/*
+ * This gets called on the first call. It replaces the function pointer
+ * so that subsequent calls are routed directly to the chosen implementation.
+ */
+static int
+pg_popcount32_choose(uint32 word)
+{
+	if (pg_popcount_available())
+		pg_popcount32 = pg_popcount32_sse42;
+	else
+		pg_popcount32 = pg_popcount32_slow;
+
+	return pg_popcount32(word);
+}
+
+static int
+pg_popcount32_sse42(uint32 word)
+{
+	return __builtin_popcount(word);
+}
+#endif
+
+/*
+ * pg_popcount32_slow
+ *		Return the number of 1 bits set in word
+ */
+static int
+pg_popcount32_slow(uint32 word)
+{
+	int result = 0;
+
+	while (word != 0)
+	{
+		result += number_of_ones[word & 255];
+		word >>= 8;
+	}
+
+	return result;
+}
+
+/*
+ * pg_popcount
+ *		Returns the number of 1-bits in buf
+ */
+uint64
+pg_popcount(const char *buf, int bytes)
+{
+	uint64 popcnt = 0;
+
+#if SIZEOF_VOID_P >= 8
+	/* Process in 64-bit chunks if the buffer is aligned. */
+	if (buf == (char *) TYPEALIGN(8, buf))
+	{
+		uint64 *words = (uint64 *) buf;
+
+		while (bytes >= 8)
+		{
+			popcnt += pg_popcount64(*words++);
+			bytes -= 8;
+		}
+
+		buf = (char *) words;
+	}
+#else
+	/* Process in 32-bit chunks if the buffer is aligned. */
+	if (buf == (char *) TYPEALIGN(4, buf))
+	{
+		uint32 *words = (uint32 *) buf;
+
+		while (bytes >= 4)
+		{
+			popcnt += pg_popcount32(*words++);
+			bytes -= 4;
+		}
+
+		buf = (char *) words;
+	}
+#endif
+
+	/* Process any remaining bytes */
+	while (bytes--)
+		popcnt += number_of_ones[(unsigned char) *buf++];
+
+	return popcnt;
+}
+
+#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNTL)
+
+/*
+ * This gets called on the first call. It replaces the function pointer
+ * so that subsequent calls are routed directly to the chosen implementation.
+ */
+static int
+pg_popcount64_choose(uint64 word)
+{
+	if (pg_popcount_available())
+		pg_popcount64 = pg_popcount64_sse42;
+	else
+		pg_popcount64 = pg_popcount64_slow;
+
+	return pg_popcount64(word);
+}
+
+static int
+pg_popcount64_sse42(uint64 word)
+{
+	return __builtin_popcountl(word);
+}
+
+#endif
+
+/*
+ * pg_popcount64_slow
+ *		Return the number of 1 bits set in word
+ */
+static int
+pg_popcount64_slow(uint64 word)
+{
+	int result = 0;
+
+	while (word != 0)
+	{
+		result += number_of_ones[word & 255];
+		word >>= 8;
+	}
+
+	return result;
+}
+
+#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CTZL) || defined(HAVE__BUILTIN_CLZ) || defined(HAVE__BUILTIN_CLZL))
+
+static bool
+pg_lzcnt_available(void)
+{
+
+	unsigned int exx[4] = { 0, 0, 0, 0 };
+
+#if defined(HAVE__GET_CPUID)
+	__get_cpuid(0x80000001, &exx[0], &exx[1], &exx[2], &exx[3]);
+#elif defined(HAVE__CPUID)
+	__cpuid(exx, 0x80000001);
+#else
+#error cpuid instruction not available
+#endif
+
+	return (exx[2] & (1 << 5)) != 0;	/* LZCNT */
+}
+#endif
+
+#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ)
+/*
+ * This gets called on the first call. It replaces the function pointer
+ * so that subsequent calls are routed directly to the chosen implementation.
+ */
+static int
+pg_rightmost_one32_choose(uint32 word)
+{
+	if (pg_lzcnt_available())
+		pg_rightmost_one32 = pg_rightmost_one32_abm;
+	else
+		pg_rightmost_one32 = pg_rightmost_one32_slow;
+
+	return pg_rightmost_one32(word);
+}
+
+static int
+pg_rightmost_one32_abm(uint32 word)
+{
+	return __builtin_ctz(word);
+}
+
+#endif
+
+/*
+ * pg_rightmost_one32_slow
+ *		Returns the number of trailing 0-bits in word, starting at the least
+ *		significant bit position. word must not be 0.
+ */
+static int
+pg_rightmost_one32_slow(uint32 word)
+{
+	int result = 0;
+
+	Assert(word != 0);
+
+	while ((word & 255) == 0)
+	{
+		word >>= 8;
+		result += 8;
+	}
+	result += rightmost_one_pos[word & 255];
+
+	return result;
+}
+
+#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZL)
+/*
+ * This gets called on the first call. It replaces the function pointer
+ * so that subsequent calls are routed directly to the chosen implementation.
+ */
+static int
+pg_rightmost_one64_choose(uint64 word)
+{
+	if (pg_lzcnt_available())
+		pg_rightmost_one64 = pg_rightmost_one64_abm;
+	else
+		pg_rightmost_one64 = pg_rightmost_one64_slow;
+
+	return pg_rightmost_one64(word);
+}
+
+static int
+pg_rightmost_one64_abm(uint64 word)
+{
+	return __builtin_ctzl(word);
+}
+#endif
+
+/*
+ * pg_rightmost_one64_slow
+ *		Returns the number of trailing 0-bits in word, starting at the least
+ *		significant bit position. word must not be 0.
+ */
+static int
+pg_rightmost_one64_slow(uint64 word)
+{
+	int result = 0;
+
+	Assert(word != 0);
+
+	while ((word & 255) == 0)
+	{
+		word >>= 8;
+		result += 8;
+	}
+	result += rightmost_one_pos[word & 255];
+
+	return result;
+}
+
+#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ)
+/*
+ * This gets called on the first call. It replaces the function pointer
+ * so that subsequent calls are routed directly to the chosen implementation.
+ */
+static int
+pg_leftmost_one32_choose(uint32 word)
+{
+	if (pg_lzcnt_available())
+		pg_leftmost_one32 = pg_leftmost_one32_abm;
+	else
+		pg_leftmost_one32 = pg_leftmost_one32_slow;
+
+	return pg_leftmost_one32(word);
+}
+
+static int
+pg_leftmost_one32_abm(uint32 word)
+{
+	return 31 - __builtin_clz(word);
+}
+#endif
+
+/*
+ * pg_leftmost_one32_slow
+ *		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 int
+pg_leftmost_one32_slow(uint32 word)
+{
+	int			shift = 32 - 8;
+
+	Assert(word != 0);
+
+	while ((word >> shift) == 0)
+		shift -= 8;
+
+	return shift + leftmost_one_pos[(word >> shift) & 255];
+}
+
+#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZL)
+/*
+ * This gets called on the first call. It replaces the function pointer
+ * so that subsequent calls are routed directly to the chosen implementation.
+ */
+static int
+pg_leftmost_one64_choose(uint64 word)
+{
+	if (pg_lzcnt_available())
+		pg_leftmost_one64 = pg_leftmost_one64_abm;
+	else
+		pg_leftmost_one64 = pg_leftmost_one64_slow;
+
+	return pg_leftmost_one64(word);
+}
+
+static int
+pg_leftmost_one64_abm(uint64 word)
+{
+	return 63 - __builtin_clzl(word);
+}
+#endif
+
+/*
+ * pg_leftmost_one64_slow
+ *		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 int
+pg_leftmost_one64_slow(uint64 word)
+{
+	int			shift = 64 - 8;
+
+	Assert(word != 0);
+
+	while ((word >> shift) == 0)
+		shift -= 8;
+
+	return shift + leftmost_one_pos[(word >> shift) & 255];
+}
diff --git a/src/tools/msvc/Mkvcbuild.pm b/src/tools/msvc/Mkvcbuild.pm
index 56192f1b20..b688111801 100644
--- a/src/tools/msvc/Mkvcbuild.pm
+++ b/src/tools/msvc/Mkvcbuild.pm
@@ -110,6 +110,7 @@ sub mkvcbuild
 		push(@pgportfiles, 'pg_crc32c_sse42_choose.c');
 		push(@pgportfiles, 'pg_crc32c_sse42.c');
 		push(@pgportfiles, 'pg_crc32c_sb8.c');
+		push(@pgportfiles, 'pg_bitutils.c');
 	}
 	else
 	{
-- 
2.16.2.windows.1

diff --git a/src/port/pg_bitutils.c b/src/port/pg_bitutils.c
index 97422e05040..fe6afb9fba5 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -299,7 +299,14 @@ pg_popcount64_choose(uint64 word)
 static int
 pg_popcount64_sse42(uint64 word)
 {
+#if defined(HAVE_LONG_INT_64)
 	return __builtin_popcountl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+	return __builtin_popcountll(word);
+#else
+	/* shouldn't happen */
+#error must have a working 64-bit integer datatype
+#endif
 }
 
 #endif
@@ -407,7 +414,14 @@ pg_rightmost_one64_choose(uint64 word)
 static int
 pg_rightmost_one64_abm(uint64 word)
 {
+#if defined(HAVE_LONG_INT_64)
 	return __builtin_ctzl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+	return __builtin_ctzll(word);
+#else
+	/* shouldn't happen */
+#error must have a working 64-bit integer datatype
+#endif
 }
 #endif
 
@@ -493,7 +507,15 @@ pg_leftmost_one64_choose(uint64 word)
 static int
 pg_leftmost_one64_abm(uint64 word)
 {
+#if defined(HAVE_LONG_INT_64)
 	return 63 - __builtin_clzl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+	return 63 - __builtin_clzll(word);
+#else
+	/* shouldn't happen */
+#error must have a working 64-bit integer datatype
+#endif
+
 }
 #endif
 

commit 477cc89802effed5d80d4a82891c7ef3b5e61e63
Author:     Alvaro Herrera <alvherre@alvh.no-ip.org>
AuthorDate: Thu Feb 14 15:18:03 2019 -0300
CommitDate: Thu Feb 14 15:31:32 2019 -0300

    fix popcount etc

diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 148c5550573..53787a7ef32 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -23,4 +23,8 @@ extern int (*pg_leftmost_one64) (uint64 word);
 
 extern uint64 pg_popcount(const char *buf, int bytes);
 
+/* in pg_popcount.c */
+extern int pg_popcount32_sse42(uint32 word);
+extern int pg_popcount64_sse42(uint64 word);
+
 #endif							/* PG_BITUTILS_H */
diff --git a/src/port/Makefile b/src/port/Makefile
index 2da73260a13..d7290573c65 100644
--- a/src/port/Makefile
+++ b/src/port/Makefile
@@ -41,6 +41,13 @@ 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 flag for the POPCOUNT instruction, we compile
+# pg_popcount.o with it.  (Whether to actually use the functions therein is
+# determined at runtime by testing CPUID flags.)
+ifneq ($(CFLAGS_POPCNT),)
+OBJS += pg_popcount.o
+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 +85,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)
+# pg_popcount.c needs CFLAGS_POPCNT
+pg_popcount.o: CFLAGS+=$(CFLAGS_POPCNT)
+pg_popcount_shlib.o: CFLAGS+=$(CFLAGS_POPCNT)
+pg_popcount_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
index aac394fe927..fc8de518791 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -10,7 +10,6 @@
  *
  *-------------------------------------------------------------------------
  */
-
 #include "postgres.h"
 
 #ifdef HAVE__GET_CPUID
@@ -23,61 +22,52 @@
 
 #include "port/pg_bitutils.h"
 
-#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
+#ifdef HAVE__BUILTIN_POPCOUNT
 static bool pg_popcount_available(void);
 static int pg_popcount32_choose(uint32 word);
-static int pg_popcount32_sse42(uint32 word);
+static int pg_popcount32_builtin(uint32 word);
 static int pg_popcount64_choose(uint64 word);
-static int pg_popcount64_sse42(uint64 word);
-#endif
-static int pg_popcount32_slow(uint32 word);
-static int pg_popcount64_slow(uint64 word);
-
-#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ))
-static bool pg_lzcnt_available(void);
-#endif
-
-#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
-static int pg_rightmost_one32_choose(uint32 word);
-static int pg_rightmost_one32_abm(uint32 word);
-static int pg_rightmost_one64_choose(uint64 word);
-static int pg_rightmost_one64_abm(uint64 word);
-#endif
-static int pg_rightmost_one32_slow(uint32 word);
-static int pg_rightmost_one64_slow(uint64 word);
-
-#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
-static int pg_leftmost_one32_choose(uint32 word);
-static int pg_leftmost_one32_abm(uint32 word);
-static int pg_leftmost_one64_choose(uint64 word);
-static int pg_leftmost_one64_abm(uint64 word);
-#endif
-static int pg_leftmost_one32_slow(uint32 word);
-static int pg_leftmost_one64_slow(uint64 word);
-
-#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
+static int pg_popcount64_builtin(uint64 word);
 int (*pg_popcount32) (uint32 word) = pg_popcount32_choose;
 int (*pg_popcount64) (uint64 word) = pg_popcount64_choose;
 #else
+static int pg_popcount32_slow(uint32 word);
+static int pg_popcount64_slow(uint64 word);
 int (*pg_popcount32) (uint32 word) = pg_popcount32_slow;
 int (*pg_popcount64) (uint64 word) = pg_popcount64_slow;
 #endif
 
-#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
+#if defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ)
+static bool pg_lzcnt_available(void);
+#endif
+
+#ifdef HAVE__BUILTIN_CTZ
+static int pg_rightmost_one32_choose(uint32 word);
+static int pg_rightmost_one32_abm(uint32 word);
+static int pg_rightmost_one64_choose(uint64 word);
+static int pg_rightmost_one64_abm(uint64 word);
 int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_choose;
 int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_choose;
 #else
 int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_slow;
 int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_slow;
 #endif
+static int pg_rightmost_one32_slow(uint32 word);
+static int pg_rightmost_one64_slow(uint64 word);
 
-#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
+#ifdef HAVE__BUILTIN_CLZ
+static int pg_leftmost_one32_choose(uint32 word);
+static int pg_leftmost_one32_abm(uint32 word);
+static int pg_leftmost_one64_choose(uint64 word);
+static int pg_leftmost_one64_abm(uint64 word);
 int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_choose;
 int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_choose;
 #else
 int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_slow;
 int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_slow;
 #endif
+static int pg_leftmost_one32_slow(uint32 word);
+static int pg_leftmost_one64_slow(uint64 word);
 
 /* Array marking the number of 1-bits for each value of 0-255. */
 static const uint8 number_of_ones[256] = {
@@ -147,27 +137,27 @@ static const uint8 leftmost_one_pos[256] = {
 	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
 };
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
 
 static bool
 pg_popcount_available(void)
 {
+#if defined(HAVE__GET_CPUID) || defined(HAVE__CPUID)
 	unsigned int exx[4] = { 0, 0, 0, 0 };
 
 #if defined(HAVE__GET_CPUID)
 	__get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
 #elif defined(HAVE__CPUID)
 	__cpuid(exx, 1);
-#else
-#error cpuid instruction not available
 #endif
 
 	return (exx[2] & (1 << 23)) != 0;	/* POPCNT */
-}
+#else		/* HAVE__GET_CPUID || HAVE__CPUID */
+
+	return false;
 #endif
+}
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
+#ifdef HAVE__BUILTIN_POPCOUNT
 /*
  * This gets called on the first call. It replaces the function pointer
  * so that subsequent calls are routed directly to the chosen implementation.
@@ -178,18 +168,19 @@ pg_popcount32_choose(uint32 word)
 	if (pg_popcount_available())
 		pg_popcount32 = pg_popcount32_sse42;
 	else
-		pg_popcount32 = pg_popcount32_slow;
+		pg_popcount32 = pg_popcount32_builtin;
 
 	return pg_popcount32(word);
 }
 
 static int
-pg_popcount32_sse42(uint32 word)
+pg_popcount32_builtin(uint32 word)
 {
 	return __builtin_popcount(word);
 }
 #endif
 
+#ifndef HAVE__BUILTIN_POPCOUNT
 /*
  * pg_popcount32_slow
  *		Return the number of 1 bits set in word
@@ -207,6 +198,7 @@ pg_popcount32_slow(uint32 word)
 
 	return result;
 }
+#endif
 
 /*
  * pg_popcount
@@ -254,8 +246,7 @@ pg_popcount(const char *buf, int bytes)
 	return popcnt;
 }
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
+#ifdef HAVE__BUILTIN_POPCOUNT
 /*
  * This gets called on the first call. It replaces the function pointer
  * so that subsequent calls are routed directly to the chosen implementation.
@@ -266,26 +257,26 @@ pg_popcount64_choose(uint64 word)
 	if (pg_popcount_available())
 		pg_popcount64 = pg_popcount64_sse42;
 	else
-		pg_popcount64 = pg_popcount64_slow;
+		pg_popcount64 = pg_popcount64_builtin;
 
 	return pg_popcount64(word);
 }
 
 static int
-pg_popcount64_sse42(uint64 word)
+pg_popcount64_builtin(uint64 word)
 {
 #if defined(HAVE_LONG_INT_64)
 	return __builtin_popcountl(word);
 #elif defined(HAVE_LONG_LONG_INT_64)
 	return __builtin_popcountll(word);
 #else
-	/* shouldn't happen */
 #error must have a working 64-bit integer datatype
 #endif
 }
 
-#endif
+#endif		/* HAVE__BUILTIN_POPCOUNT */
 
+#ifndef HAVE__BUILTIN_POPCOUNT
 /*
  * pg_popcount64_slow
  *		Return the number of 1 bits set in word
@@ -303,28 +294,28 @@ pg_popcount64_slow(uint64 word)
 
 	return result;
 }
-
-#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ))
+#endif
 
 static bool
 pg_lzcnt_available(void)
 {
-
+#if (defined(HAVE__GET_CPUID) || defined(HAVE__CPUID))
 	unsigned int exx[4] = { 0, 0, 0, 0 };
 
 #if defined(HAVE__GET_CPUID)
 	__get_cpuid(0x80000001, &exx[0], &exx[1], &exx[2], &exx[3]);
 #elif defined(HAVE__CPUID)
 	__cpuid(exx, 0x80000001);
-#else
-#error cpuid instruction not available
 #endif
 
 	return (exx[2] & (1 << 5)) != 0;	/* LZCNT */
-}
-#endif
+#else		/* HAVE__GET_CPUID || HAVE__CPUID */
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ)
+	return false;
+#endif
+}
+
+#ifdef HAVE__BUILTIN_CTZ
 /*
  * This gets called on the first call. It replaces the function pointer
  * so that subsequent calls are routed directly to the chosen implementation.
@@ -346,7 +337,7 @@ pg_rightmost_one32_abm(uint32 word)
 	return __builtin_ctz(word);
 }
 
-#endif
+#endif		/* HAVE__BUILTIN_CTZ */
 
 /*
  * pg_rightmost_one32_slow
@@ -370,7 +361,7 @@ pg_rightmost_one32_slow(uint32 word)
 	return result;
 }
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ)
+#ifdef HAVE__BUILTIN_CTZ
 /*
  * This gets called on the first call. It replaces the function pointer
  * so that subsequent calls are routed directly to the chosen implementation.
@@ -394,11 +385,10 @@ pg_rightmost_one64_abm(uint64 word)
 #elif defined(HAVE_LONG_LONG_INT_64)
 	return __builtin_ctzll(word);
 #else
-	/* shouldn't happen */
 #error must have a working 64-bit integer datatype
 #endif
 }
-#endif
+#endif		/* HAVE_BUILTIN_CTZ */
 
 /*
  * pg_rightmost_one64_slow
@@ -422,7 +412,7 @@ pg_rightmost_one64_slow(uint64 word)
 	return result;
 }
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ)
+#ifdef HAVE__BUILTIN_CLZ
 /*
  * This gets called on the first call. It replaces the function pointer
  * so that subsequent calls are routed directly to the chosen implementation.
@@ -443,7 +433,7 @@ pg_leftmost_one32_abm(uint32 word)
 {
 	return 31 - __builtin_clz(word);
 }
-#endif
+#endif		/* HAVE__BUILTIN_CLZ */
 
 /*
  * pg_leftmost_one32_slow
@@ -463,7 +453,7 @@ pg_leftmost_one32_slow(uint32 word)
 	return shift + leftmost_one_pos[(word >> shift) & 255];
 }
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ)
+#ifdef HAVE__BUILTIN_CLZ
 /*
  * This gets called on the first call. It replaces the function pointer
  * so that subsequent calls are routed directly to the chosen implementation.
@@ -487,12 +477,10 @@ pg_leftmost_one64_abm(uint64 word)
 #elif defined(HAVE_LONG_LONG_INT_64)
 	return 63 - __builtin_clzll(word);
 #else
-	/* shouldn't happen */
 #error must have a working 64-bit integer datatype
 #endif
-
 }
-#endif
+#endif		/* HAVE__BUIILTIN_CLZ */
 
 /*
  * pg_leftmost_one64_slow
diff --git a/src/port/pg_popcount.c b/src/port/pg_popcount.c
new file mode 100644
index 00000000000..5254c41273f
--- /dev/null
+++ b/src/port/pg_popcount.c
@@ -0,0 +1,36 @@
+/*-------------------------------------------------------------------------
+ *
+ * pg_popcount.c
+ *	  CPU-optimized implementation of pg_popcount
+ *
+ * This file must be compiled with a compiler-specific flag to enable the
+ * POPCOUNT instruction.
+ *
+ * Portions Copyright (c) 2019, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/port/pg_popcount.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "port/pg_bitutils.h"
+
+int
+pg_popcount32_sse42(uint32 word)
+{
+	return __builtin_popcount(word);
+}
+
+int
+pg_popcount64_sse42(uint64 word)
+{
+#if defined(HAVE_LONG_INT_64)
+	return __builtin_popcountl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+	return __builtin_popcountll(word);
+#else
+#error must have a working 64-bit integer datatype
+#endif
+}

commit 6c771a4f43da0409ae5fa9ff1b1579f381c451c0
Author:     Alvaro Herrera <alvherre@alvh.no-ip.org>
AuthorDate: Thu Feb 14 15:18:03 2019 -0300
CommitDate: Thu Feb 14 19:24:03 2019 -0300

    fix popcount etc

diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 148c5550573..635eb9331af 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -10,17 +10,20 @@
  *
  *------------------------------------------------------------------------ -
  */
-
 #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_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_popcount.c */
+extern int	pg_popcount32_sse42(uint32 word);
+extern int	pg_popcount64_sse42(uint64 word);
+
 #endif							/* PG_BITUTILS_H */
diff --git a/src/port/Makefile b/src/port/Makefile
index 2da73260a13..d7290573c65 100644
--- a/src/port/Makefile
+++ b/src/port/Makefile
@@ -41,6 +41,13 @@ 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 flag for the POPCOUNT instruction, we compile
+# pg_popcount.o with it.  (Whether to actually use the functions therein is
+# determined at runtime by testing CPUID flags.)
+ifneq ($(CFLAGS_POPCNT),)
+OBJS += pg_popcount.o
+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 +85,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)
+# pg_popcount.c needs CFLAGS_POPCNT
+pg_popcount.o: CFLAGS+=$(CFLAGS_POPCNT)
+pg_popcount_shlib.o: CFLAGS+=$(CFLAGS_POPCNT)
+pg_popcount_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
index aac394fe927..23d317d111e 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -10,7 +10,6 @@
  *
  *-------------------------------------------------------------------------
  */
-
 #include "postgres.h"
 
 #ifdef HAVE__GET_CPUID
@@ -23,61 +22,21 @@
 
 #include "port/pg_bitutils.h"
 
-#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
+#ifdef HAVE__BUILTIN_POPCOUNT
 static bool pg_popcount_available(void);
-static int pg_popcount32_choose(uint32 word);
-static int pg_popcount32_sse42(uint32 word);
-static int pg_popcount64_choose(uint64 word);
-static int pg_popcount64_sse42(uint64 word);
-#endif
-static int pg_popcount32_slow(uint32 word);
-static int pg_popcount64_slow(uint64 word);
-
-#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ))
-static bool pg_lzcnt_available(void);
-#endif
-
-#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
-static int pg_rightmost_one32_choose(uint32 word);
-static int pg_rightmost_one32_abm(uint32 word);
-static int pg_rightmost_one64_choose(uint64 word);
-static int pg_rightmost_one64_abm(uint64 word);
-#endif
-static int pg_rightmost_one32_slow(uint32 word);
-static int pg_rightmost_one64_slow(uint64 word);
-
-#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
-static int pg_leftmost_one32_choose(uint32 word);
-static int pg_leftmost_one32_abm(uint32 word);
-static int pg_leftmost_one64_choose(uint64 word);
-static int pg_leftmost_one64_abm(uint64 word);
-#endif
-static int pg_leftmost_one32_slow(uint32 word);
-static int pg_leftmost_one64_slow(uint64 word);
-
-#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
-int (*pg_popcount32) (uint32 word) = pg_popcount32_choose;
-int (*pg_popcount64) (uint64 word) = pg_popcount64_choose;
+static int	pg_popcount32_choose(uint32 word);
+static int	pg_popcount32_builtin(uint32 word);
+static int	pg_popcount64_choose(uint64 word);
+static int	pg_popcount64_builtin(uint64 word);
+int			(*pg_popcount32) (uint32 word) = pg_popcount32_choose;
+int			(*pg_popcount64) (uint64 word) = pg_popcount64_choose;
 #else
-int (*pg_popcount32) (uint32 word) = pg_popcount32_slow;
-int (*pg_popcount64) (uint64 word) = pg_popcount64_slow;
-#endif
+static int	pg_popcount32_slow(uint32 word);
+static int	pg_popcount64_slow(uint64 word);
+int			(*pg_popcount32) (uint32 word) = pg_popcount32_slow;
+int			(*pg_popcount64) (uint64 word) = pg_popcount64_slow;
+#endif							/* !HAVE_BUILTIN_POPCOUNT */
 
-#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
-int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_choose;
-int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_choose;
-#else
-int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_slow;
-int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_slow;
-#endif
-
-#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
-int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_choose;
-int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_choose;
-#else
-int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_slow;
-int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_slow;
-#endif
 
 /* Array marking the number of 1-bits for each value of 0-255. */
 static const uint8 number_of_ones[256] = {
@@ -99,6 +58,7 @@ static const uint8 number_of_ones[256] = {
 	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
 };
 
+#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
@@ -122,7 +82,9 @@ static const uint8 rightmost_one_pos[256] = {
 	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 */
 
+#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
@@ -146,31 +108,36 @@ static const uint8 leftmost_one_pos[256] = {
 	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 */
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
+/*
+ * Return true iff we have CPUID support and it indicates that the POPCNT
+ * instruction is available.
+ */
 static bool
 pg_popcount_available(void)
 {
-	unsigned int exx[4] = { 0, 0, 0, 0 };
+#if defined(HAVE__GET_CPUID) || defined(HAVE__CPUID)
+	unsigned int exx[4] = {0, 0, 0, 0};
 
 #if defined(HAVE__GET_CPUID)
 	__get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
 #elif defined(HAVE__CPUID)
 	__cpuid(exx, 1);
-#else
-#error cpuid instruction not available
 #endif
 
 	return (exx[2] & (1 << 23)) != 0;	/* POPCNT */
-}
+#else							/* HAVE__GET_CPUID || HAVE__CPUID */
+
+	return false;
 #endif
+}
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
+#ifdef HAVE__BUILTIN_POPCOUNT
 /*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
+ * This gets called on the first call to pg_popcount32. It replaces the
+ * function pointer so that subsequent calls are routed directly to the chosen
+ * implementation.
  */
 static int
 pg_popcount32_choose(uint32 word)
@@ -178,18 +145,17 @@ pg_popcount32_choose(uint32 word)
 	if (pg_popcount_available())
 		pg_popcount32 = pg_popcount32_sse42;
 	else
-		pg_popcount32 = pg_popcount32_slow;
+		pg_popcount32 = pg_popcount32_builtin;
 
 	return pg_popcount32(word);
 }
 
 static int
-pg_popcount32_sse42(uint32 word)
+pg_popcount32_builtin(uint32 word)
 {
 	return __builtin_popcount(word);
 }
-#endif
-
+#else							/* HAVE__BUILTIN_POPCOUNT */
 /*
  * pg_popcount32_slow
  *		Return the number of 1 bits set in word
@@ -197,7 +163,7 @@ pg_popcount32_sse42(uint32 word)
 static int
 pg_popcount32_slow(uint32 word)
 {
-	int result = 0;
+	int			result = 0;
 
 	while (word != 0)
 	{
@@ -207,6 +173,7 @@ pg_popcount32_slow(uint32 word)
 
 	return result;
 }
+#endif
 
 /*
  * pg_popcount
@@ -215,13 +182,13 @@ pg_popcount32_slow(uint32 word)
 uint64
 pg_popcount(const char *buf, int bytes)
 {
-	uint64 popcnt = 0;
+	uint64		popcnt = 0;
 
 #if SIZEOF_VOID_P >= 8
 	/* Process in 64-bit chunks if the buffer is aligned. */
 	if (buf == (char *) TYPEALIGN(8, buf))
 	{
-		uint64 *words = (uint64 *) buf;
+		uint64	   *words = (uint64 *) buf;
 
 		while (bytes >= 8)
 		{
@@ -235,7 +202,7 @@ pg_popcount(const char *buf, int bytes)
 	/* Process in 32-bit chunks if the buffer is aligned. */
 	if (buf == (char *) TYPEALIGN(4, buf))
 	{
-		uint32 *words = (uint32 *) buf;
+		uint32	   *words = (uint32 *) buf;
 
 		while (bytes >= 4)
 		{
@@ -254,11 +221,11 @@ pg_popcount(const char *buf, int bytes)
 	return popcnt;
 }
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
+#ifdef HAVE__BUILTIN_POPCOUNT
 /*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
+ * This gets called on the first call to pg_popcount64. It replaces the
+ * function pointer so that subsequent calls are routed directly to the chosen
+ * implementation.
  */
 static int
 pg_popcount64_choose(uint64 word)
@@ -266,26 +233,24 @@ pg_popcount64_choose(uint64 word)
 	if (pg_popcount_available())
 		pg_popcount64 = pg_popcount64_sse42;
 	else
-		pg_popcount64 = pg_popcount64_slow;
+		pg_popcount64 = pg_popcount64_builtin;
 
 	return pg_popcount64(word);
 }
 
 static int
-pg_popcount64_sse42(uint64 word)
+pg_popcount64_builtin(uint64 word)
 {
 #if defined(HAVE_LONG_INT_64)
 	return __builtin_popcountl(word);
 #elif defined(HAVE_LONG_LONG_INT_64)
 	return __builtin_popcountll(word);
 #else
-	/* shouldn't happen */
 #error must have a working 64-bit integer datatype
 #endif
 }
 
-#endif
-
+#else							/* HAVE__BUILTIN_POPCOUNT */
 /*
  * pg_popcount64_slow
  *		Return the number of 1 bits set in word
@@ -293,7 +258,7 @@ pg_popcount64_sse42(uint64 word)
 static int
 pg_popcount64_slow(uint64 word)
 {
-	int result = 0;
+	int			result = 0;
 
 	while (word != 0)
 	{
@@ -303,156 +268,77 @@ pg_popcount64_slow(uint64 word)
 
 	return result;
 }
-
-#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ))
-
-static bool
-pg_lzcnt_available(void)
-{
-
-	unsigned int exx[4] = { 0, 0, 0, 0 };
-
-#if defined(HAVE__GET_CPUID)
-	__get_cpuid(0x80000001, &exx[0], &exx[1], &exx[2], &exx[3]);
-#elif defined(HAVE__CPUID)
-	__cpuid(exx, 0x80000001);
-#else
-#error cpuid instruction not available
-#endif
-
-	return (exx[2] & (1 << 5)) != 0;	/* LZCNT */
-}
-#endif
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_rightmost_one32_choose(uint32 word)
-{
-	if (pg_lzcnt_available())
-		pg_rightmost_one32 = pg_rightmost_one32_abm;
-	else
-		pg_rightmost_one32 = pg_rightmost_one32_slow;
-
-	return pg_rightmost_one32(word);
-}
-
-static int
-pg_rightmost_one32_abm(uint32 word)
-{
-	return __builtin_ctz(word);
-}
-
 #endif
 
 /*
- * pg_rightmost_one32_slow
+ * 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 int
-pg_rightmost_one32_slow(uint32 word)
+int
+pg_rightmost_one32(uint32 word)
 {
-	int result = 0;
+	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;
 }
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ)
 /*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
+ * 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 int
-pg_rightmost_one64_choose(uint64 word)
+int
+pg_rightmost_one64(uint64 word)
 {
-	if (pg_lzcnt_available())
-		pg_rightmost_one64 = pg_rightmost_one64_abm;
-	else
-		pg_rightmost_one64 = pg_rightmost_one64_slow;
+	int			result = 0;
 
-	return pg_rightmost_one64(word);
-}
+	Assert(word != 0);
 
-static int
-pg_rightmost_one64_abm(uint64 word)
-{
+#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
-	/* shouldn't happen */
 #error must have a working 64-bit integer datatype
 #endif
-}
-#endif
-
-/*
- * pg_rightmost_one64_slow
- *		Returns the number of trailing 0-bits in word, starting at the least
- *		significant bit position. word must not be 0.
- */
-static int
-pg_rightmost_one64_slow(uint64 word)
-{
-	int result = 0;
-
-	Assert(word != 0);
-
+#else							/* HAVE__BUILTIN_CTZ */
 	while ((word & 255) == 0)
 	{
 		word >>= 8;
 		result += 8;
 	}
 	result += rightmost_one_pos[word & 255];
+#endif
 
 	return result;
 }
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ)
 /*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_leftmost_one32_choose(uint32 word)
-{
-	if (pg_lzcnt_available())
-		pg_leftmost_one32 = pg_leftmost_one32_abm;
-	else
-		pg_leftmost_one32 = pg_leftmost_one32_slow;
-
-	return pg_leftmost_one32(word);
-}
-
-static int
-pg_leftmost_one32_abm(uint32 word)
-{
-	return 31 - __builtin_clz(word);
-}
-#endif
-
-/*
- * pg_leftmost_one32_slow
+ * 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 int
-pg_leftmost_one32_slow(uint32 word)
+int
+pg_leftmost_one32(uint32 word)
 {
+#ifdef HAVE__BUILTIN_CLZ
+	return 31 - __builtin_clz(word);
+#else
 	int			shift = 32 - 8;
 
 	Assert(word != 0);
@@ -461,53 +347,32 @@ pg_leftmost_one32_slow(uint32 word)
 		shift -= 8;
 
 	return shift + leftmost_one_pos[(word >> shift) & 255];
+#endif							/* HAVE__BUILTIN_CLZ */
 }
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ)
 /*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
+ * 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 int
-pg_leftmost_one64_choose(uint64 word)
-{
-	if (pg_lzcnt_available())
-		pg_leftmost_one64 = pg_leftmost_one64_abm;
-	else
-		pg_leftmost_one64 = pg_leftmost_one64_slow;
-
-	return pg_leftmost_one64(word);
-}
-
-static int
-pg_leftmost_one64_abm(uint64 word)
+int
+pg_leftmost_one64(uint64 word)
 {
+#ifdef HAVE__BUILTIN_CLZ
 #if defined(HAVE_LONG_INT_64)
 	return 63 - __builtin_clzl(word);
 #elif defined(HAVE_LONG_LONG_INT_64)
 	return 63 - __builtin_clzll(word);
 #else
-	/* shouldn't happen */
 #error must have a working 64-bit integer datatype
 #endif
-
-}
-#endif
-
-/*
- * pg_leftmost_one64_slow
- *		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 int
-pg_leftmost_one64_slow(uint64 word)
-{
+#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 */
 }
diff --git a/src/port/pg_popcount.c b/src/port/pg_popcount.c
new file mode 100644
index 00000000000..5254c41273f
--- /dev/null
+++ b/src/port/pg_popcount.c
@@ -0,0 +1,36 @@
+/*-------------------------------------------------------------------------
+ *
+ * pg_popcount.c
+ *	  CPU-optimized implementation of pg_popcount
+ *
+ * This file must be compiled with a compiler-specific flag to enable the
+ * POPCOUNT instruction.
+ *
+ * Portions Copyright (c) 2019, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/port/pg_popcount.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "port/pg_bitutils.h"
+
+int
+pg_popcount32_sse42(uint32 word)
+{
+	return __builtin_popcount(word);
+}
+
+int
+pg_popcount64_sse42(uint64 word)
+{
+#if defined(HAVE_LONG_INT_64)
+	return __builtin_popcountl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+	return __builtin_popcountll(word);
+#else
+#error must have a working 64-bit integer datatype
+#endif
+}

commit d4265b36754720f85bf2ac6fd9ae2c58b8e1abc2
Author:     Alvaro Herrera <alvherre@alvh.no-ip.org>
AuthorDate: Thu Feb 14 15:18:03 2019 -0300
CommitDate: Thu Feb 14 19:41:41 2019 -0300

    fix popcount etc

diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 148c5550573..72dfd1d2695 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -10,17 +10,175 @@
  *
  *------------------------------------------------------------------------ -
  */
-
 #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_popcount.c */
+extern int	pg_popcount32_sse42(uint32 word);
+extern int	pg_popcount64_sse42(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
+	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
+#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
index 2da73260a13..d7290573c65 100644
--- a/src/port/Makefile
+++ b/src/port/Makefile
@@ -41,6 +41,13 @@ 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 flag for the POPCOUNT instruction, we compile
+# pg_popcount.o with it.  (Whether to actually use the functions therein is
+# determined at runtime by testing CPUID flags.)
+ifneq ($(CFLAGS_POPCNT),)
+OBJS += pg_popcount.o
+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 +85,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)
+# pg_popcount.c needs CFLAGS_POPCNT
+pg_popcount.o: CFLAGS+=$(CFLAGS_POPCNT)
+pg_popcount_shlib.o: CFLAGS+=$(CFLAGS_POPCNT)
+pg_popcount_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
index aac394fe927..3d26883111f 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -10,7 +10,6 @@
  *
  *-------------------------------------------------------------------------
  */
-
 #include "postgres.h"
 
 #ifdef HAVE__GET_CPUID
@@ -23,61 +22,21 @@
 
 #include "port/pg_bitutils.h"
 
-#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
+#ifdef HAVE__BUILTIN_POPCOUNT
 static bool pg_popcount_available(void);
-static int pg_popcount32_choose(uint32 word);
-static int pg_popcount32_sse42(uint32 word);
-static int pg_popcount64_choose(uint64 word);
-static int pg_popcount64_sse42(uint64 word);
-#endif
-static int pg_popcount32_slow(uint32 word);
-static int pg_popcount64_slow(uint64 word);
-
-#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ))
-static bool pg_lzcnt_available(void);
-#endif
-
-#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
-static int pg_rightmost_one32_choose(uint32 word);
-static int pg_rightmost_one32_abm(uint32 word);
-static int pg_rightmost_one64_choose(uint64 word);
-static int pg_rightmost_one64_abm(uint64 word);
-#endif
-static int pg_rightmost_one32_slow(uint32 word);
-static int pg_rightmost_one64_slow(uint64 word);
-
-#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
-static int pg_leftmost_one32_choose(uint32 word);
-static int pg_leftmost_one32_abm(uint32 word);
-static int pg_leftmost_one64_choose(uint64 word);
-static int pg_leftmost_one64_abm(uint64 word);
-#endif
-static int pg_leftmost_one32_slow(uint32 word);
-static int pg_leftmost_one64_slow(uint64 word);
-
-#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
-int (*pg_popcount32) (uint32 word) = pg_popcount32_choose;
-int (*pg_popcount64) (uint64 word) = pg_popcount64_choose;
+static int	pg_popcount32_choose(uint32 word);
+static int	pg_popcount32_builtin(uint32 word);
+static int	pg_popcount64_choose(uint64 word);
+static int	pg_popcount64_builtin(uint64 word);
+int			(*pg_popcount32) (uint32 word) = pg_popcount32_choose;
+int			(*pg_popcount64) (uint64 word) = pg_popcount64_choose;
 #else
-int (*pg_popcount32) (uint32 word) = pg_popcount32_slow;
-int (*pg_popcount64) (uint64 word) = pg_popcount64_slow;
-#endif
+static int	pg_popcount32_slow(uint32 word);
+static int	pg_popcount64_slow(uint64 word);
+int			(*pg_popcount32) (uint32 word) = pg_popcount32_slow;
+int			(*pg_popcount64) (uint64 word) = pg_popcount64_slow;
+#endif							/* !HAVE_BUILTIN_POPCOUNT */
 
-#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
-int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_choose;
-int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_choose;
-#else
-int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_slow;
-int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_slow;
-#endif
-
-#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
-int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_choose;
-int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_choose;
-#else
-int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_slow;
-int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_slow;
-#endif
 
 /* Array marking the number of 1-bits for each value of 0-255. */
 static const uint8 number_of_ones[256] = {
@@ -100,77 +59,33 @@ static const uint8 number_of_ones[256] = {
 };
 
 /*
- * 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.
+ * Return true iff we have CPUID support and it indicates that the POPCNT
+ * instruction is available.
  */
-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
-};
-
-/*
- * 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
-};
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
 static bool
 pg_popcount_available(void)
 {
-	unsigned int exx[4] = { 0, 0, 0, 0 };
+#if defined(HAVE__GET_CPUID) || defined(HAVE__CPUID)
+	unsigned int exx[4] = {0, 0, 0, 0};
 
 #if defined(HAVE__GET_CPUID)
 	__get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
 #elif defined(HAVE__CPUID)
 	__cpuid(exx, 1);
-#else
-#error cpuid instruction not available
 #endif
 
 	return (exx[2] & (1 << 23)) != 0;	/* POPCNT */
-}
+#else							/* HAVE__GET_CPUID || HAVE__CPUID */
+
+	return false;
 #endif
+}
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
+#ifdef HAVE__BUILTIN_POPCOUNT
 /*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
+ * This gets called on the first call to pg_popcount32. It replaces the
+ * function pointer so that subsequent calls are routed directly to the chosen
+ * implementation.
  */
 static int
 pg_popcount32_choose(uint32 word)
@@ -178,18 +93,17 @@ pg_popcount32_choose(uint32 word)
 	if (pg_popcount_available())
 		pg_popcount32 = pg_popcount32_sse42;
 	else
-		pg_popcount32 = pg_popcount32_slow;
+		pg_popcount32 = pg_popcount32_builtin;
 
 	return pg_popcount32(word);
 }
 
 static int
-pg_popcount32_sse42(uint32 word)
+pg_popcount32_builtin(uint32 word)
 {
 	return __builtin_popcount(word);
 }
-#endif
-
+#else							/* HAVE__BUILTIN_POPCOUNT */
 /*
  * pg_popcount32_slow
  *		Return the number of 1 bits set in word
@@ -197,7 +111,7 @@ pg_popcount32_sse42(uint32 word)
 static int
 pg_popcount32_slow(uint32 word)
 {
-	int result = 0;
+	int			result = 0;
 
 	while (word != 0)
 	{
@@ -207,6 +121,7 @@ pg_popcount32_slow(uint32 word)
 
 	return result;
 }
+#endif
 
 /*
  * pg_popcount
@@ -215,13 +130,13 @@ pg_popcount32_slow(uint32 word)
 uint64
 pg_popcount(const char *buf, int bytes)
 {
-	uint64 popcnt = 0;
+	uint64		popcnt = 0;
 
 #if SIZEOF_VOID_P >= 8
 	/* Process in 64-bit chunks if the buffer is aligned. */
 	if (buf == (char *) TYPEALIGN(8, buf))
 	{
-		uint64 *words = (uint64 *) buf;
+		uint64	   *words = (uint64 *) buf;
 
 		while (bytes >= 8)
 		{
@@ -235,7 +150,7 @@ pg_popcount(const char *buf, int bytes)
 	/* Process in 32-bit chunks if the buffer is aligned. */
 	if (buf == (char *) TYPEALIGN(4, buf))
 	{
-		uint32 *words = (uint32 *) buf;
+		uint32	   *words = (uint32 *) buf;
 
 		while (bytes >= 4)
 		{
@@ -254,11 +169,11 @@ pg_popcount(const char *buf, int bytes)
 	return popcnt;
 }
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
+#ifdef HAVE__BUILTIN_POPCOUNT
 /*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
+ * This gets called on the first call to pg_popcount64. It replaces the
+ * function pointer so that subsequent calls are routed directly to the chosen
+ * implementation.
  */
 static int
 pg_popcount64_choose(uint64 word)
@@ -266,26 +181,24 @@ pg_popcount64_choose(uint64 word)
 	if (pg_popcount_available())
 		pg_popcount64 = pg_popcount64_sse42;
 	else
-		pg_popcount64 = pg_popcount64_slow;
+		pg_popcount64 = pg_popcount64_builtin;
 
 	return pg_popcount64(word);
 }
 
 static int
-pg_popcount64_sse42(uint64 word)
+pg_popcount64_builtin(uint64 word)
 {
 #if defined(HAVE_LONG_INT_64)
 	return __builtin_popcountl(word);
 #elif defined(HAVE_LONG_LONG_INT_64)
 	return __builtin_popcountll(word);
 #else
-	/* shouldn't happen */
 #error must have a working 64-bit integer datatype
 #endif
 }
 
-#endif
-
+#else							/* HAVE__BUILTIN_POPCOUNT */
 /*
  * pg_popcount64_slow
  *		Return the number of 1 bits set in word
@@ -293,7 +206,7 @@ pg_popcount64_sse42(uint64 word)
 static int
 pg_popcount64_slow(uint64 word)
 {
-	int result = 0;
+	int			result = 0;
 
 	while (word != 0)
 	{
@@ -303,211 +216,4 @@ pg_popcount64_slow(uint64 word)
 
 	return result;
 }
-
-#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ))
-
-static bool
-pg_lzcnt_available(void)
-{
-
-	unsigned int exx[4] = { 0, 0, 0, 0 };
-
-#if defined(HAVE__GET_CPUID)
-	__get_cpuid(0x80000001, &exx[0], &exx[1], &exx[2], &exx[3]);
-#elif defined(HAVE__CPUID)
-	__cpuid(exx, 0x80000001);
-#else
-#error cpuid instruction not available
 #endif
-
-	return (exx[2] & (1 << 5)) != 0;	/* LZCNT */
-}
-#endif
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_rightmost_one32_choose(uint32 word)
-{
-	if (pg_lzcnt_available())
-		pg_rightmost_one32 = pg_rightmost_one32_abm;
-	else
-		pg_rightmost_one32 = pg_rightmost_one32_slow;
-
-	return pg_rightmost_one32(word);
-}
-
-static int
-pg_rightmost_one32_abm(uint32 word)
-{
-	return __builtin_ctz(word);
-}
-
-#endif
-
-/*
- * pg_rightmost_one32_slow
- *		Returns the number of trailing 0-bits in word, starting at the least
- *		significant bit position. word must not be 0.
- */
-static int
-pg_rightmost_one32_slow(uint32 word)
-{
-	int result = 0;
-
-	Assert(word != 0);
-
-	while ((word & 255) == 0)
-	{
-		word >>= 8;
-		result += 8;
-	}
-	result += rightmost_one_pos[word & 255];
-
-	return result;
-}
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_rightmost_one64_choose(uint64 word)
-{
-	if (pg_lzcnt_available())
-		pg_rightmost_one64 = pg_rightmost_one64_abm;
-	else
-		pg_rightmost_one64 = pg_rightmost_one64_slow;
-
-	return pg_rightmost_one64(word);
-}
-
-static int
-pg_rightmost_one64_abm(uint64 word)
-{
-#if defined(HAVE_LONG_INT_64)
-	return __builtin_ctzl(word);
-#elif defined(HAVE_LONG_LONG_INT_64)
-	return __builtin_ctzll(word);
-#else
-	/* shouldn't happen */
-#error must have a working 64-bit integer datatype
-#endif
-}
-#endif
-
-/*
- * pg_rightmost_one64_slow
- *		Returns the number of trailing 0-bits in word, starting at the least
- *		significant bit position. word must not be 0.
- */
-static int
-pg_rightmost_one64_slow(uint64 word)
-{
-	int result = 0;
-
-	Assert(word != 0);
-
-	while ((word & 255) == 0)
-	{
-		word >>= 8;
-		result += 8;
-	}
-	result += rightmost_one_pos[word & 255];
-
-	return result;
-}
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_leftmost_one32_choose(uint32 word)
-{
-	if (pg_lzcnt_available())
-		pg_leftmost_one32 = pg_leftmost_one32_abm;
-	else
-		pg_leftmost_one32 = pg_leftmost_one32_slow;
-
-	return pg_leftmost_one32(word);
-}
-
-static int
-pg_leftmost_one32_abm(uint32 word)
-{
-	return 31 - __builtin_clz(word);
-}
-#endif
-
-/*
- * pg_leftmost_one32_slow
- *		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 int
-pg_leftmost_one32_slow(uint32 word)
-{
-	int			shift = 32 - 8;
-
-	Assert(word != 0);
-
-	while ((word >> shift) == 0)
-		shift -= 8;
-
-	return shift + leftmost_one_pos[(word >> shift) & 255];
-}
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_leftmost_one64_choose(uint64 word)
-{
-	if (pg_lzcnt_available())
-		pg_leftmost_one64 = pg_leftmost_one64_abm;
-	else
-		pg_leftmost_one64 = pg_leftmost_one64_slow;
-
-	return pg_leftmost_one64(word);
-}
-
-static int
-pg_leftmost_one64_abm(uint64 word)
-{
-#if defined(HAVE_LONG_INT_64)
-	return 63 - __builtin_clzl(word);
-#elif defined(HAVE_LONG_LONG_INT_64)
-	return 63 - __builtin_clzll(word);
-#else
-	/* shouldn't happen */
-#error must have a working 64-bit integer datatype
-#endif
-
-}
-#endif
-
-/*
- * pg_leftmost_one64_slow
- *		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 int
-pg_leftmost_one64_slow(uint64 word)
-{
-	int			shift = 64 - 8;
-
-	Assert(word != 0);
-
-	while ((word >> shift) == 0)
-		shift -= 8;
-
-	return shift + leftmost_one_pos[(word >> shift) & 255];
-}
diff --git a/src/port/pg_popcount.c b/src/port/pg_popcount.c
new file mode 100644
index 00000000000..5254c41273f
--- /dev/null
+++ b/src/port/pg_popcount.c
@@ -0,0 +1,36 @@
+/*-------------------------------------------------------------------------
+ *
+ * pg_popcount.c
+ *	  CPU-optimized implementation of pg_popcount
+ *
+ * This file must be compiled with a compiler-specific flag to enable the
+ * POPCOUNT instruction.
+ *
+ * Portions Copyright (c) 2019, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/port/pg_popcount.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "port/pg_bitutils.h"
+
+int
+pg_popcount32_sse42(uint32 word)
+{
+	return __builtin_popcount(word);
+}
+
+int
+pg_popcount64_sse42(uint64 word)
+{
+#if defined(HAVE_LONG_INT_64)
+	return __builtin_popcountl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+	return __builtin_popcountll(word);
+#else
+#error must have a working 64-bit integer datatype
+#endif
+}

From a3c654f9446ed0f8ead57d4f7202554311135dbf Mon Sep 17 00:00:00 2001
From: Alvaro Herrera <alvherre@alvh.no-ip.org>
Date: Fri, 15 Feb 2019 11:14:04 -0300
Subject: [PATCH] Fix compiler builtin usage in new pg_bitutils.c

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 to use the
compiler builtin.  However, some compilers implement the builtin even
though they don't have the compiler switch, so split both things.  Also,
expose whether the builtin exists to Makefile.global, so that src/port's
can decide whether to compile the special file.

Remove CPUID test for CTZ/CLZ.
---
 config/c-compiler.m4           |  22 +-
 configure                      | 105 +++++++--
 configure.in                   |   7 +-
 src/Makefile.global.in         |   3 +
 src/include/port/pg_bitutils.h | 176 +++++++++++++++-
 src/port/Makefile              |  16 +-
 src/port/pg_bitutils.c         | 374 ++++-----------------------------
 src/port/pg_bitutils_sse42.c   |  36 ++++
 8 files changed, 365 insertions(+), 374 deletions(-)
 create mode 100644 src/port/pg_bitutils_sse42.c

diff --git a/config/c-compiler.m4 b/config/c-compiler.m4
index 05fa82518f8..7c0d52b515f 100644
--- 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
index 73e9c235b69..fa0f1216a0a 100755
--- 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,87 @@ 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
+
+
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking whether ${CC} supports -mpopcntb, for CFLAGS_POPCNT" >&5
+$as_echo_n "checking whether ${CC} supports -mpopcntb, for CFLAGS_POPCNT... " >&6; }
+if ${pgac_cv_prog_CC_cflags__mpopcntb+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  pgac_save_CFLAGS=$CFLAGS
+pgac_save_CC=$CC
+CC=${CC}
+CFLAGS="${CFLAGS_POPCNT} -mpopcntb"
+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__mpopcntb=yes
+else
+  pgac_cv_prog_CC_cflags__mpopcntb=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__mpopcntb" >&5
+$as_echo "$pgac_cv_prog_CC_cflags__mpopcntb" >&6; }
+if test x"$pgac_cv_prog_CC_cflags__mpopcntb" = x"yes"; then
+  CFLAGS_POPCNT="${CFLAGS_POPCNT} -mpopcntb"
+fi
+
+
+
+
 CFLAGS_VECTOR=$CFLAGS_VECTOR
 
 
@@ -14111,32 +14193,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 +14732,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
index 9c4d5f0691e..4a5f1fd62c1 100644
--- a/configure.in
+++ b/configure.in
@@ -547,6 +547,11 @@ 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])
+PGAC_PROG_CC_VAR_OPT(CFLAGS_POPCNT, [-mpopcntb])
+AC_SUBST(CFLAGS_POPCNT)
+
 AC_SUBST(CFLAGS_VECTOR, $CFLAGS_VECTOR)
 
 # Determine flags used to emit bitcode for JIT inlining. Need to test
@@ -1506,7 +1511,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
index aa16da3e0f2..0f4dd195845 100644
--- 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
index 148c5550573..7b76a138f89 100644
--- 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_popcount.c */
+extern int	pg_popcount32_sse42(uint32 word);
+extern int	pg_popcount64_sse42(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
index 2da73260a13..237cc625e19 100644
--- 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_sse42.o.
+ifneq ($(CFLAGS_POPCNT),)
+ifeq ($(have__builtin_popcount),yes)
+OBJS += pg_bitutils_sse42.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)
+# pg_popcount.c needs CFLAGS_POPCNT
+pg_popcount.o: CFLAGS+=$(CFLAGS_POPCNT)
+pg_popcount_shlib.o: CFLAGS+=$(CFLAGS_POPCNT)
+pg_popcount_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
index aac394fe927..3d26883111f 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -10,7 +10,6 @@
  *
  *-------------------------------------------------------------------------
  */
-
 #include "postgres.h"
 
 #ifdef HAVE__GET_CPUID
@@ -23,61 +22,21 @@
 
 #include "port/pg_bitutils.h"
 
-#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
+#ifdef HAVE__BUILTIN_POPCOUNT
 static bool pg_popcount_available(void);
-static int pg_popcount32_choose(uint32 word);
-static int pg_popcount32_sse42(uint32 word);
-static int pg_popcount64_choose(uint64 word);
-static int pg_popcount64_sse42(uint64 word);
-#endif
-static int pg_popcount32_slow(uint32 word);
-static int pg_popcount64_slow(uint64 word);
-
-#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ))
-static bool pg_lzcnt_available(void);
-#endif
-
-#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
-static int pg_rightmost_one32_choose(uint32 word);
-static int pg_rightmost_one32_abm(uint32 word);
-static int pg_rightmost_one64_choose(uint64 word);
-static int pg_rightmost_one64_abm(uint64 word);
-#endif
-static int pg_rightmost_one32_slow(uint32 word);
-static int pg_rightmost_one64_slow(uint64 word);
-
-#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
-static int pg_leftmost_one32_choose(uint32 word);
-static int pg_leftmost_one32_abm(uint32 word);
-static int pg_leftmost_one64_choose(uint64 word);
-static int pg_leftmost_one64_abm(uint64 word);
-#endif
-static int pg_leftmost_one32_slow(uint32 word);
-static int pg_leftmost_one64_slow(uint64 word);
-
-#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
-int (*pg_popcount32) (uint32 word) = pg_popcount32_choose;
-int (*pg_popcount64) (uint64 word) = pg_popcount64_choose;
+static int	pg_popcount32_choose(uint32 word);
+static int	pg_popcount32_builtin(uint32 word);
+static int	pg_popcount64_choose(uint64 word);
+static int	pg_popcount64_builtin(uint64 word);
+int			(*pg_popcount32) (uint32 word) = pg_popcount32_choose;
+int			(*pg_popcount64) (uint64 word) = pg_popcount64_choose;
 #else
-int (*pg_popcount32) (uint32 word) = pg_popcount32_slow;
-int (*pg_popcount64) (uint64 word) = pg_popcount64_slow;
-#endif
+static int	pg_popcount32_slow(uint32 word);
+static int	pg_popcount64_slow(uint64 word);
+int			(*pg_popcount32) (uint32 word) = pg_popcount32_slow;
+int			(*pg_popcount64) (uint64 word) = pg_popcount64_slow;
+#endif							/* !HAVE_BUILTIN_POPCOUNT */
 
-#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
-int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_choose;
-int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_choose;
-#else
-int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_slow;
-int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_slow;
-#endif
-
-#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
-int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_choose;
-int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_choose;
-#else
-int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_slow;
-int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_slow;
-#endif
 
 /* Array marking the number of 1-bits for each value of 0-255. */
 static const uint8 number_of_ones[256] = {
@@ -100,77 +59,33 @@ static const uint8 number_of_ones[256] = {
 };
 
 /*
- * 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.
+ * Return true iff we have CPUID support and it indicates that the POPCNT
+ * instruction is available.
  */
-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
-};
-
-/*
- * 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
-};
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
 static bool
 pg_popcount_available(void)
 {
-	unsigned int exx[4] = { 0, 0, 0, 0 };
+#if defined(HAVE__GET_CPUID) || defined(HAVE__CPUID)
+	unsigned int exx[4] = {0, 0, 0, 0};
 
 #if defined(HAVE__GET_CPUID)
 	__get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
 #elif defined(HAVE__CPUID)
 	__cpuid(exx, 1);
-#else
-#error cpuid instruction not available
 #endif
 
 	return (exx[2] & (1 << 23)) != 0;	/* POPCNT */
-}
+#else							/* HAVE__GET_CPUID || HAVE__CPUID */
+
+	return false;
 #endif
+}
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
+#ifdef HAVE__BUILTIN_POPCOUNT
 /*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
+ * This gets called on the first call to pg_popcount32. It replaces the
+ * function pointer so that subsequent calls are routed directly to the chosen
+ * implementation.
  */
 static int
 pg_popcount32_choose(uint32 word)
@@ -178,18 +93,17 @@ pg_popcount32_choose(uint32 word)
 	if (pg_popcount_available())
 		pg_popcount32 = pg_popcount32_sse42;
 	else
-		pg_popcount32 = pg_popcount32_slow;
+		pg_popcount32 = pg_popcount32_builtin;
 
 	return pg_popcount32(word);
 }
 
 static int
-pg_popcount32_sse42(uint32 word)
+pg_popcount32_builtin(uint32 word)
 {
 	return __builtin_popcount(word);
 }
-#endif
-
+#else							/* HAVE__BUILTIN_POPCOUNT */
 /*
  * pg_popcount32_slow
  *		Return the number of 1 bits set in word
@@ -197,7 +111,7 @@ pg_popcount32_sse42(uint32 word)
 static int
 pg_popcount32_slow(uint32 word)
 {
-	int result = 0;
+	int			result = 0;
 
 	while (word != 0)
 	{
@@ -207,6 +121,7 @@ pg_popcount32_slow(uint32 word)
 
 	return result;
 }
+#endif
 
 /*
  * pg_popcount
@@ -215,13 +130,13 @@ pg_popcount32_slow(uint32 word)
 uint64
 pg_popcount(const char *buf, int bytes)
 {
-	uint64 popcnt = 0;
+	uint64		popcnt = 0;
 
 #if SIZEOF_VOID_P >= 8
 	/* Process in 64-bit chunks if the buffer is aligned. */
 	if (buf == (char *) TYPEALIGN(8, buf))
 	{
-		uint64 *words = (uint64 *) buf;
+		uint64	   *words = (uint64 *) buf;
 
 		while (bytes >= 8)
 		{
@@ -235,7 +150,7 @@ pg_popcount(const char *buf, int bytes)
 	/* Process in 32-bit chunks if the buffer is aligned. */
 	if (buf == (char *) TYPEALIGN(4, buf))
 	{
-		uint32 *words = (uint32 *) buf;
+		uint32	   *words = (uint32 *) buf;
 
 		while (bytes >= 4)
 		{
@@ -254,11 +169,11 @@ pg_popcount(const char *buf, int bytes)
 	return popcnt;
 }
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
+#ifdef HAVE__BUILTIN_POPCOUNT
 /*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
+ * This gets called on the first call to pg_popcount64. It replaces the
+ * function pointer so that subsequent calls are routed directly to the chosen
+ * implementation.
  */
 static int
 pg_popcount64_choose(uint64 word)
@@ -266,26 +181,24 @@ pg_popcount64_choose(uint64 word)
 	if (pg_popcount_available())
 		pg_popcount64 = pg_popcount64_sse42;
 	else
-		pg_popcount64 = pg_popcount64_slow;
+		pg_popcount64 = pg_popcount64_builtin;
 
 	return pg_popcount64(word);
 }
 
 static int
-pg_popcount64_sse42(uint64 word)
+pg_popcount64_builtin(uint64 word)
 {
 #if defined(HAVE_LONG_INT_64)
 	return __builtin_popcountl(word);
 #elif defined(HAVE_LONG_LONG_INT_64)
 	return __builtin_popcountll(word);
 #else
-	/* shouldn't happen */
 #error must have a working 64-bit integer datatype
 #endif
 }
 
-#endif
-
+#else							/* HAVE__BUILTIN_POPCOUNT */
 /*
  * pg_popcount64_slow
  *		Return the number of 1 bits set in word
@@ -293,7 +206,7 @@ pg_popcount64_sse42(uint64 word)
 static int
 pg_popcount64_slow(uint64 word)
 {
-	int result = 0;
+	int			result = 0;
 
 	while (word != 0)
 	{
@@ -303,211 +216,4 @@ pg_popcount64_slow(uint64 word)
 
 	return result;
 }
-
-#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ))
-
-static bool
-pg_lzcnt_available(void)
-{
-
-	unsigned int exx[4] = { 0, 0, 0, 0 };
-
-#if defined(HAVE__GET_CPUID)
-	__get_cpuid(0x80000001, &exx[0], &exx[1], &exx[2], &exx[3]);
-#elif defined(HAVE__CPUID)
-	__cpuid(exx, 0x80000001);
-#else
-#error cpuid instruction not available
 #endif
-
-	return (exx[2] & (1 << 5)) != 0;	/* LZCNT */
-}
-#endif
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_rightmost_one32_choose(uint32 word)
-{
-	if (pg_lzcnt_available())
-		pg_rightmost_one32 = pg_rightmost_one32_abm;
-	else
-		pg_rightmost_one32 = pg_rightmost_one32_slow;
-
-	return pg_rightmost_one32(word);
-}
-
-static int
-pg_rightmost_one32_abm(uint32 word)
-{
-	return __builtin_ctz(word);
-}
-
-#endif
-
-/*
- * pg_rightmost_one32_slow
- *		Returns the number of trailing 0-bits in word, starting at the least
- *		significant bit position. word must not be 0.
- */
-static int
-pg_rightmost_one32_slow(uint32 word)
-{
-	int result = 0;
-
-	Assert(word != 0);
-
-	while ((word & 255) == 0)
-	{
-		word >>= 8;
-		result += 8;
-	}
-	result += rightmost_one_pos[word & 255];
-
-	return result;
-}
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_rightmost_one64_choose(uint64 word)
-{
-	if (pg_lzcnt_available())
-		pg_rightmost_one64 = pg_rightmost_one64_abm;
-	else
-		pg_rightmost_one64 = pg_rightmost_one64_slow;
-
-	return pg_rightmost_one64(word);
-}
-
-static int
-pg_rightmost_one64_abm(uint64 word)
-{
-#if defined(HAVE_LONG_INT_64)
-	return __builtin_ctzl(word);
-#elif defined(HAVE_LONG_LONG_INT_64)
-	return __builtin_ctzll(word);
-#else
-	/* shouldn't happen */
-#error must have a working 64-bit integer datatype
-#endif
-}
-#endif
-
-/*
- * pg_rightmost_one64_slow
- *		Returns the number of trailing 0-bits in word, starting at the least
- *		significant bit position. word must not be 0.
- */
-static int
-pg_rightmost_one64_slow(uint64 word)
-{
-	int result = 0;
-
-	Assert(word != 0);
-
-	while ((word & 255) == 0)
-	{
-		word >>= 8;
-		result += 8;
-	}
-	result += rightmost_one_pos[word & 255];
-
-	return result;
-}
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_leftmost_one32_choose(uint32 word)
-{
-	if (pg_lzcnt_available())
-		pg_leftmost_one32 = pg_leftmost_one32_abm;
-	else
-		pg_leftmost_one32 = pg_leftmost_one32_slow;
-
-	return pg_leftmost_one32(word);
-}
-
-static int
-pg_leftmost_one32_abm(uint32 word)
-{
-	return 31 - __builtin_clz(word);
-}
-#endif
-
-/*
- * pg_leftmost_one32_slow
- *		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 int
-pg_leftmost_one32_slow(uint32 word)
-{
-	int			shift = 32 - 8;
-
-	Assert(word != 0);
-
-	while ((word >> shift) == 0)
-		shift -= 8;
-
-	return shift + leftmost_one_pos[(word >> shift) & 255];
-}
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_leftmost_one64_choose(uint64 word)
-{
-	if (pg_lzcnt_available())
-		pg_leftmost_one64 = pg_leftmost_one64_abm;
-	else
-		pg_leftmost_one64 = pg_leftmost_one64_slow;
-
-	return pg_leftmost_one64(word);
-}
-
-static int
-pg_leftmost_one64_abm(uint64 word)
-{
-#if defined(HAVE_LONG_INT_64)
-	return 63 - __builtin_clzl(word);
-#elif defined(HAVE_LONG_LONG_INT_64)
-	return 63 - __builtin_clzll(word);
-#else
-	/* shouldn't happen */
-#error must have a working 64-bit integer datatype
-#endif
-
-}
-#endif
-
-/*
- * pg_leftmost_one64_slow
- *		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 int
-pg_leftmost_one64_slow(uint64 word)
-{
-	int			shift = 64 - 8;
-
-	Assert(word != 0);
-
-	while ((word >> shift) == 0)
-		shift -= 8;
-
-	return shift + leftmost_one_pos[(word >> shift) & 255];
-}
diff --git a/src/port/pg_bitutils_sse42.c b/src/port/pg_bitutils_sse42.c
new file mode 100644
index 00000000000..9945e5c103d
--- /dev/null
+++ b/src/port/pg_bitutils_sse42.c
@@ -0,0 +1,36 @@
+/*-------------------------------------------------------------------------
+ *
+ * pg_popcount.c
+ *	  CPU-optimized implementation of pg_popcount
+ *
+ * This file must be compiled with a compiler-specific flag to enable the
+ * POPCNT instruction.
+ *
+ * Portions Copyright (c) 2019, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/port/pg_popcount.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "port/pg_bitutils.h"
+
+int
+pg_popcount32_sse42(uint32 word)
+{
+	return __builtin_popcount(word);
+}
+
+int
+pg_popcount64_sse42(uint64 word)
+{
+#if defined(HAVE_LONG_INT_64)
+	return __builtin_popcountl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+	return __builtin_popcountll(word);
+#else
+#error must have a working 64-bit integer datatype
+#endif
+}
-- 
2.17.1

From 085650a174ff080f578bb289d3707173aaf4f07b Mon Sep 17 00:00:00 2001
From: Alvaro Herrera <alvherre@alvh.no-ip.org>
Date: Fri, 15 Feb 2019 13:07:02 -0300
Subject: [PATCH v2] Fix compiler builtin usage in new pg_bitutils.c

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
---
 config/c-compiler.m4            |  22 +-
 configure                       |  66 ++++--
 configure.in                    |   6 +-
 src/Makefile.global.in          |   3 +
 src/include/port/pg_bitutils.h  | 176 ++++++++++++++-
 src/port/Makefile               |  16 +-
 src/port/pg_bitutils.c          | 378 ++++----------------------------
 src/port/pg_bitutils_hwpopcnt.c |  36 +++
 8 files changed, 327 insertions(+), 376 deletions(-)
 create mode 100644 src/port/pg_bitutils_hwpopcnt.c

diff --git a/config/c-compiler.m4 b/config/c-compiler.m4
index 05fa82518f8..7c0d52b515f 100644
--- 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
index 73e9c235b69..2e3cc372a6e 100755
--- 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
index 9c4d5f0691e..e12d5b14f56 100644
--- 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
index aa16da3e0f2..0f4dd195845 100644
--- 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
index 148c5550573..70aae5128fa 100644
--- 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
index 2da73260a13..a7f8fd2e668 100644
--- 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
index aac394fe927..97bfcebe4e1 100644
--- a/src/port/pg_bitutils.c
+++ b/src/port/pg_bitutils.c
@@ -10,7 +10,6 @@
  *
  *-------------------------------------------------------------------------
  */
-
 #include "postgres.h"
 
 #ifdef HAVE__GET_CPUID
@@ -23,61 +22,21 @@
 
 #include "port/pg_bitutils.h"
 
-#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
+#ifdef HAVE__BUILTIN_POPCOUNT
 static bool pg_popcount_available(void);
-static int pg_popcount32_choose(uint32 word);
-static int pg_popcount32_sse42(uint32 word);
-static int pg_popcount64_choose(uint64 word);
-static int pg_popcount64_sse42(uint64 word);
-#endif
-static int pg_popcount32_slow(uint32 word);
-static int pg_popcount64_slow(uint64 word);
-
-#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ))
-static bool pg_lzcnt_available(void);
-#endif
-
-#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
-static int pg_rightmost_one32_choose(uint32 word);
-static int pg_rightmost_one32_abm(uint32 word);
-static int pg_rightmost_one64_choose(uint64 word);
-static int pg_rightmost_one64_abm(uint64 word);
-#endif
-static int pg_rightmost_one32_slow(uint32 word);
-static int pg_rightmost_one64_slow(uint64 word);
-
-#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
-static int pg_leftmost_one32_choose(uint32 word);
-static int pg_leftmost_one32_abm(uint32 word);
-static int pg_leftmost_one64_choose(uint64 word);
-static int pg_leftmost_one64_abm(uint64 word);
-#endif
-static int pg_leftmost_one32_slow(uint32 word);
-static int pg_leftmost_one64_slow(uint64 word);
-
-#if defined(HAVE__BUILTIN_POPCOUNT) && defined(HAVE__GET_CPUID)
-int (*pg_popcount32) (uint32 word) = pg_popcount32_choose;
-int (*pg_popcount64) (uint64 word) = pg_popcount64_choose;
+static int	pg_popcount32_choose(uint32 word);
+static int	pg_popcount32_builtin(uint32 word);
+static int	pg_popcount64_choose(uint64 word);
+static int	pg_popcount64_builtin(uint64 word);
+int			(*pg_popcount32) (uint32 word) = pg_popcount32_choose;
+int			(*pg_popcount64) (uint64 word) = pg_popcount64_choose;
 #else
-int (*pg_popcount32) (uint32 word) = pg_popcount32_slow;
-int (*pg_popcount64) (uint64 word) = pg_popcount64_slow;
-#endif
+static int	pg_popcount32_slow(uint32 word);
+static int	pg_popcount64_slow(uint64 word);
+int			(*pg_popcount32) (uint32 word) = pg_popcount32_slow;
+int			(*pg_popcount64) (uint64 word) = pg_popcount64_slow;
+#endif							/* !HAVE_BUILTIN_POPCOUNT */
 
-#if defined(HAVE__BUILTIN_CTZ) && defined(HAVE__GET_CPUID)
-int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_choose;
-int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_choose;
-#else
-int (*pg_rightmost_one32) (uint32 word) = pg_rightmost_one32_slow;
-int (*pg_rightmost_one64) (uint64 word) = pg_rightmost_one64_slow;
-#endif
-
-#if defined(HAVE__BUILTIN_CLZ) && defined(HAVE__GET_CPUID)
-int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_choose;
-int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_choose;
-#else
-int (*pg_leftmost_one32) (uint32 word) = pg_leftmost_one32_slow;
-int (*pg_leftmost_one64) (uint64 word) = pg_leftmost_one64_slow;
-#endif
 
 /* Array marking the number of 1-bits for each value of 0-255. */
 static const uint8 number_of_ones[256] = {
@@ -100,96 +59,51 @@ static const uint8 number_of_ones[256] = {
 };
 
 /*
- * 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.
+ * Return true iff we have CPUID support and it indicates that the POPCNT
+ * instruction is available.
  */
-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
-};
-
-/*
- * 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
-};
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
 static bool
 pg_popcount_available(void)
 {
-	unsigned int exx[4] = { 0, 0, 0, 0 };
+#if defined(HAVE__GET_CPUID) || defined(HAVE__CPUID)
+	unsigned int exx[4] = {0, 0, 0, 0};
 
 #if defined(HAVE__GET_CPUID)
 	__get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
 #elif defined(HAVE__CPUID)
 	__cpuid(exx, 1);
-#else
-#error cpuid instruction not available
 #endif
 
 	return (exx[2] & (1 << 23)) != 0;	/* POPCNT */
-}
+#else							/* HAVE__GET_CPUID || HAVE__CPUID */
+
+	return false;
 #endif
+}
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
+#ifdef HAVE__BUILTIN_POPCOUNT
 /*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
+ * This gets called on the first call to pg_popcount32. It replaces the
+ * function pointer so that subsequent calls are routed directly to the chosen
+ * implementation.
  */
 static int
 pg_popcount32_choose(uint32 word)
 {
 	if (pg_popcount_available())
-		pg_popcount32 = pg_popcount32_sse42;
+		pg_popcount32 = pg_popcount32_hw;
 	else
-		pg_popcount32 = pg_popcount32_slow;
+		pg_popcount32 = pg_popcount32_builtin;
 
 	return pg_popcount32(word);
 }
 
 static int
-pg_popcount32_sse42(uint32 word)
+pg_popcount32_builtin(uint32 word)
 {
 	return __builtin_popcount(word);
 }
-#endif
-
+#else							/* HAVE__BUILTIN_POPCOUNT */
 /*
  * pg_popcount32_slow
  *		Return the number of 1 bits set in word
@@ -197,7 +111,7 @@ pg_popcount32_sse42(uint32 word)
 static int
 pg_popcount32_slow(uint32 word)
 {
-	int result = 0;
+	int			result = 0;
 
 	while (word != 0)
 	{
@@ -207,6 +121,7 @@ pg_popcount32_slow(uint32 word)
 
 	return result;
 }
+#endif
 
 /*
  * pg_popcount
@@ -215,13 +130,13 @@ pg_popcount32_slow(uint32 word)
 uint64
 pg_popcount(const char *buf, int bytes)
 {
-	uint64 popcnt = 0;
+	uint64		popcnt = 0;
 
 #if SIZEOF_VOID_P >= 8
 	/* Process in 64-bit chunks if the buffer is aligned. */
 	if (buf == (char *) TYPEALIGN(8, buf))
 	{
-		uint64 *words = (uint64 *) buf;
+		uint64	   *words = (uint64 *) buf;
 
 		while (bytes >= 8)
 		{
@@ -235,7 +150,7 @@ pg_popcount(const char *buf, int bytes)
 	/* Process in 32-bit chunks if the buffer is aligned. */
 	if (buf == (char *) TYPEALIGN(4, buf))
 	{
-		uint32 *words = (uint32 *) buf;
+		uint32	   *words = (uint32 *) buf;
 
 		while (bytes >= 4)
 		{
@@ -254,38 +169,36 @@ pg_popcount(const char *buf, int bytes)
 	return popcnt;
 }
 
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_POPCOUNT)
-
+#ifdef HAVE__BUILTIN_POPCOUNT
 /*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
+ * This gets called on the first call to pg_popcount64. It replaces the
+ * function pointer so that subsequent calls are routed directly to the chosen
+ * implementation.
  */
 static int
 pg_popcount64_choose(uint64 word)
 {
 	if (pg_popcount_available())
-		pg_popcount64 = pg_popcount64_sse42;
+		pg_popcount64 = pg_popcount64_hw;
 	else
-		pg_popcount64 = pg_popcount64_slow;
+		pg_popcount64 = pg_popcount64_builtin;
 
 	return pg_popcount64(word);
 }
 
 static int
-pg_popcount64_sse42(uint64 word)
+pg_popcount64_builtin(uint64 word)
 {
 #if defined(HAVE_LONG_INT_64)
 	return __builtin_popcountl(word);
 #elif defined(HAVE_LONG_LONG_INT_64)
 	return __builtin_popcountll(word);
 #else
-	/* shouldn't happen */
 #error must have a working 64-bit integer datatype
 #endif
 }
 
-#endif
-
+#else							/* HAVE__BUILTIN_POPCOUNT */
 /*
  * pg_popcount64_slow
  *		Return the number of 1 bits set in word
@@ -293,7 +206,7 @@ pg_popcount64_sse42(uint64 word)
 static int
 pg_popcount64_slow(uint64 word)
 {
-	int result = 0;
+	int			result = 0;
 
 	while (word != 0)
 	{
@@ -303,211 +216,4 @@ pg_popcount64_slow(uint64 word)
 
 	return result;
 }
-
-#if defined(HAVE__GET_CPUID) && (defined(HAVE__BUILTIN_CTZ) || defined(HAVE__BUILTIN_CLZ))
-
-static bool
-pg_lzcnt_available(void)
-{
-
-	unsigned int exx[4] = { 0, 0, 0, 0 };
-
-#if defined(HAVE__GET_CPUID)
-	__get_cpuid(0x80000001, &exx[0], &exx[1], &exx[2], &exx[3]);
-#elif defined(HAVE__CPUID)
-	__cpuid(exx, 0x80000001);
-#else
-#error cpuid instruction not available
 #endif
-
-	return (exx[2] & (1 << 5)) != 0;	/* LZCNT */
-}
-#endif
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_rightmost_one32_choose(uint32 word)
-{
-	if (pg_lzcnt_available())
-		pg_rightmost_one32 = pg_rightmost_one32_abm;
-	else
-		pg_rightmost_one32 = pg_rightmost_one32_slow;
-
-	return pg_rightmost_one32(word);
-}
-
-static int
-pg_rightmost_one32_abm(uint32 word)
-{
-	return __builtin_ctz(word);
-}
-
-#endif
-
-/*
- * pg_rightmost_one32_slow
- *		Returns the number of trailing 0-bits in word, starting at the least
- *		significant bit position. word must not be 0.
- */
-static int
-pg_rightmost_one32_slow(uint32 word)
-{
-	int result = 0;
-
-	Assert(word != 0);
-
-	while ((word & 255) == 0)
-	{
-		word >>= 8;
-		result += 8;
-	}
-	result += rightmost_one_pos[word & 255];
-
-	return result;
-}
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CTZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_rightmost_one64_choose(uint64 word)
-{
-	if (pg_lzcnt_available())
-		pg_rightmost_one64 = pg_rightmost_one64_abm;
-	else
-		pg_rightmost_one64 = pg_rightmost_one64_slow;
-
-	return pg_rightmost_one64(word);
-}
-
-static int
-pg_rightmost_one64_abm(uint64 word)
-{
-#if defined(HAVE_LONG_INT_64)
-	return __builtin_ctzl(word);
-#elif defined(HAVE_LONG_LONG_INT_64)
-	return __builtin_ctzll(word);
-#else
-	/* shouldn't happen */
-#error must have a working 64-bit integer datatype
-#endif
-}
-#endif
-
-/*
- * pg_rightmost_one64_slow
- *		Returns the number of trailing 0-bits in word, starting at the least
- *		significant bit position. word must not be 0.
- */
-static int
-pg_rightmost_one64_slow(uint64 word)
-{
-	int result = 0;
-
-	Assert(word != 0);
-
-	while ((word & 255) == 0)
-	{
-		word >>= 8;
-		result += 8;
-	}
-	result += rightmost_one_pos[word & 255];
-
-	return result;
-}
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_leftmost_one32_choose(uint32 word)
-{
-	if (pg_lzcnt_available())
-		pg_leftmost_one32 = pg_leftmost_one32_abm;
-	else
-		pg_leftmost_one32 = pg_leftmost_one32_slow;
-
-	return pg_leftmost_one32(word);
-}
-
-static int
-pg_leftmost_one32_abm(uint32 word)
-{
-	return 31 - __builtin_clz(word);
-}
-#endif
-
-/*
- * pg_leftmost_one32_slow
- *		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 int
-pg_leftmost_one32_slow(uint32 word)
-{
-	int			shift = 32 - 8;
-
-	Assert(word != 0);
-
-	while ((word >> shift) == 0)
-		shift -= 8;
-
-	return shift + leftmost_one_pos[(word >> shift) & 255];
-}
-
-#if defined(HAVE__GET_CPUID) && defined(HAVE__BUILTIN_CLZ)
-/*
- * This gets called on the first call. It replaces the function pointer
- * so that subsequent calls are routed directly to the chosen implementation.
- */
-static int
-pg_leftmost_one64_choose(uint64 word)
-{
-	if (pg_lzcnt_available())
-		pg_leftmost_one64 = pg_leftmost_one64_abm;
-	else
-		pg_leftmost_one64 = pg_leftmost_one64_slow;
-
-	return pg_leftmost_one64(word);
-}
-
-static int
-pg_leftmost_one64_abm(uint64 word)
-{
-#if defined(HAVE_LONG_INT_64)
-	return 63 - __builtin_clzl(word);
-#elif defined(HAVE_LONG_LONG_INT_64)
-	return 63 - __builtin_clzll(word);
-#else
-	/* shouldn't happen */
-#error must have a working 64-bit integer datatype
-#endif
-
-}
-#endif
-
-/*
- * pg_leftmost_one64_slow
- *		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 int
-pg_leftmost_one64_slow(uint64 word)
-{
-	int			shift = 64 - 8;
-
-	Assert(word != 0);
-
-	while ((word >> shift) == 0)
-		shift -= 8;
-
-	return shift + leftmost_one_pos[(word >> shift) & 255];
-}
diff --git a/src/port/pg_bitutils_hwpopcnt.c b/src/port/pg_bitutils_hwpopcnt.c
new file mode 100644
index 00000000000..516efd586dd
--- /dev/null
+++ b/src/port/pg_bitutils_hwpopcnt.c
@@ -0,0 +1,36 @@
+/*-------------------------------------------------------------------------
+ *
+ * pg_bitutils_hwpopcnt.c
+ *	  CPU-optimized implementation of pg_popcount variants
+ *
+ * This file must be compiled with a compiler-specific flag to enable the
+ * POPCNT instruction.
+ *
+ * Portions Copyright (c) 2019, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/port/pg_bitutils_hwpopcnt.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "port/pg_bitutils.h"
+
+int
+pg_popcount32_hw(uint32 word)
+{
+	return __builtin_popcount(word);
+}
+
+int
+pg_popcount64_hw(uint64 word)
+{
+#if defined(HAVE_LONG_INT_64)
+	return __builtin_popcountl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+	return __builtin_popcountll(word);
+#else
+#error must have a working 64-bit integer datatype
+#endif
+}
-- 
2.17.1