I wrote:
> Attached is a quick-and-dirty attempt to add MSVC support for the
rightmost/leftmost-one-pos functions.
>
> 0001 adds asserts to the existing coding.
> 0002 adds MSVC support. Tests pass on CI, but it's of course possible
that there is some bug that prevents hitting the fastpath. I've mostly used
the platform specific types, so some further cleanup might be needed.
I've cleaned these up and verified on godbolt.org that they work as
intended and still pass CI. I kept the Windows types as does other Winows
code in the tree, but used bool instead of unsigned char because it's used
like a boolean.
0003 is separate because I'm not quite sure how detailed to comment the
#ifdef maze. Could be left out.
0004 simplifies AllocSetFreeIndex() in the course of supporting MSVC. The
output is identical to HEAD in non-assert builds using gcc.
0002 through 0004 could be squashed together.
This plugs a hole in our platform-specific intrinsic support and is fairly
straightforward. Review welcome, but if there is none I intend to commit in
a week or two.
--
John Naylor
EDB: http://www.enterprisedb.com
From eb2e7f6aad9447010f34ce8d7230be754c61f6fb Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Wed, 8 Feb 2023 12:34:13 +0700
Subject: [PATCH v4 3/4] Add more comments to #else directives
WIP: squash or leave out
---
src/include/port/pg_bitutils.h | 10 +++++-----
1 file changed, 5 insertions(+), 5 deletions(-)
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index 9150789aaf..04f2fe8d3e 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -18,7 +18,7 @@
#define HAVE_BITSCAN_FORWARD
#define HAVE_BITSCAN_REVERSE
-#else
+#else /* ! _MSC_VER */
#if defined(HAVE__BUILTIN_CTZ)
#define HAVE_BITSCAN_FORWARD
#endif
@@ -70,7 +70,7 @@ pg_leftmost_one_pos32(uint32 word)
Assert(bitscan_result == result);
return bitscan_result;
-#else
+#else /* ! HAVE_BITSCAN_REVERSE */
return result;
#endif /* HAVE_BITSCAN_REVERSE */
}
@@ -119,7 +119,7 @@ pg_leftmost_one_pos64(uint64 word)
Assert(bitscan_result == result);
return bitscan_result;
-#else
+#else /* ! HAVE_BITSCAN_REVERSE */
return result;
#endif /* HAVE_BITSCAN_REVERSE */
}
@@ -165,7 +165,7 @@ pg_rightmost_one_pos32(uint32 word)
Assert(bitscan_result == result);
return bitscan_result;
-#else
+#else /* ! HAVE_BITSCAN_FORWARD */
return result;
#endif /* HAVE_BITSCAN_FORWARD */
}
@@ -217,7 +217,7 @@ pg_rightmost_one_pos64(uint64 word)
Assert(bitscan_result == result);
return bitscan_result;
-#else
+#else /* ! HAVE_BITSCAN_FORWARD */
return result;
#endif /* HAVE_BITSCAN_FORWARD */
}
--
2.39.1
From 4a84bb6980fa05ae3bde84179b8427799d6ee538 Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Fri, 3 Feb 2023 16:54:39 +0700
Subject: [PATCH v4 4/4] Rationalize platform support in AllocSetFreeIndex
Previously, we directly tested for HAVE__BUILTIN_CLZ and copied the
internals of pg_leftmost_one_pos32(), with a special fallback that does
less work than the general fallback for that function. In the wake of
<prev commit>, we have MSVC support for bitscan intrinsics, and a more
general way to test for them, so just call pg_leftmost_one_pos32()
directly.
On gcc at least, there is no difference in the binary, showing that
compilers can do constant folding across the boundary of an inlined
function.
---
src/backend/utils/mmgr/aset.c | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/src/backend/utils/mmgr/aset.c b/src/backend/utils/mmgr/aset.c
index 740729b5d0..d12977b7b5 100644
--- a/src/backend/utils/mmgr/aset.c
+++ b/src/backend/utils/mmgr/aset.c
@@ -289,7 +289,7 @@ AllocSetFreeIndex(Size size)
* or equivalently
* pg_leftmost_one_pos32(size - 1) - ALLOC_MINBITS + 1
*
- * However, rather than just calling that function, we duplicate the
+ * However, for platforms without intrinsic support, we duplicate the
* logic here, allowing an additional optimization. It's reasonable
* to assume that ALLOC_CHUNK_LIMIT fits in 16 bits, so we can unroll
* the byte-at-a-time loop in pg_leftmost_one_pos32 and just handle
@@ -299,8 +299,8 @@ AllocSetFreeIndex(Size size)
* much trouble.
*----------
*/
-#ifdef HAVE__BUILTIN_CLZ
- idx = 31 - __builtin_clz((uint32) size - 1) - ALLOC_MINBITS + 1;
+#ifdef HAVE_BITSCAN_REVERSE
+ idx = pg_leftmost_one_pos32(size - 1) - ALLOC_MINBITS + 1;
#else
uint32 t,
tsize;
--
2.39.1
From 3b75d2b05a1ed02525b86152168151300a827613 Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Wed, 8 Feb 2023 12:05:58 +0700
Subject: [PATCH v4 2/4] Add MSVC support for bitscan reverse/forward
---
src/include/port/pg_bitutils.h | 75 ++++++++++++++++++++++++++++++----
1 file changed, 67 insertions(+), 8 deletions(-)
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index a5df4f1a35..9150789aaf 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -13,6 +13,21 @@
#ifndef PG_BITUTILS_H
#define PG_BITUTILS_H
+#ifdef _MSC_VER
+#include <intrin.h>
+#define HAVE_BITSCAN_FORWARD
+#define HAVE_BITSCAN_REVERSE
+
+#else
+#if defined(HAVE__BUILTIN_CTZ)
+#define HAVE_BITSCAN_FORWARD
+#endif
+
+#if defined(HAVE__BUILTIN_CLZ)
+#define HAVE_BITSCAN_REVERSE
+#endif
+#endif /* _MSC_VER */
+
extern PGDLLIMPORT const uint8 pg_leftmost_one_pos[256];
extern PGDLLIMPORT const uint8 pg_rightmost_one_pos[256];
extern PGDLLIMPORT const uint8 pg_number_of_ones[256];
@@ -27,9 +42,12 @@ pg_leftmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CLZ
int bitscan_result;
+#elif defined(_MSC_VER)
+ unsigned long bitscan_result;
+ bool non_zero;
#endif
-#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(HAVE_BITSCAN_REVERSE) || defined(USE_ASSERT_CHECKING)
int result;
int shift = 32 - 8;
@@ -41,13 +59,20 @@ pg_leftmost_one_pos32(uint32 word)
result = shift + pg_leftmost_one_pos[(word >> shift) & 255];
#endif
+#ifdef HAVE_BITSCAN_REVERSE
+
#if defined(HAVE__BUILTIN_CLZ)
bitscan_result = 31 - __builtin_clz(word);
+#elif defined(_MSC_VER)
+ non_zero = _BitScanReverse(&bitscan_result, word);
+ Assert(non_zero);
+#endif
Assert(bitscan_result == result);
return bitscan_result;
+
#else
return result;
-#endif /* HAVE__BUILTIN_CLZ */
+#endif /* HAVE_BITSCAN_REVERSE */
}
/*
@@ -59,9 +84,12 @@ pg_leftmost_one_pos64(uint64 word)
{
#ifdef HAVE__BUILTIN_CLZ
int bitscan_result;
+#elif defined(_MSC_VER)
+ unsigned long bitscan_result;
+ bool non_zero;
#endif
-#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(HAVE_BITSCAN_REVERSE) || defined(USE_ASSERT_CHECKING)
int result;
int shift = 64 - 8;
@@ -73,6 +101,8 @@ pg_leftmost_one_pos64(uint64 word)
result = shift + pg_leftmost_one_pos[(word >> shift) & 255];
#endif
+#ifdef HAVE_BITSCAN_REVERSE
+
#if defined(HAVE__BUILTIN_CLZ)
#if defined(HAVE_LONG_INT_64)
bitscan_result = 63 - __builtin_clzl(word);
@@ -81,11 +111,17 @@ pg_leftmost_one_pos64(uint64 word)
#else
#error must have a working 64-bit integer datatype
#endif /* HAVE_LONG_INT_64 */
+
+#elif defined(_MSC_VER)
+ non_zero = _BitScanReverse64(&bitscan_result, word);
+ Assert(non_zero);
+#endif /* HAVE__BUILTIN_CLZ */
Assert(bitscan_result == result);
return bitscan_result;
+
#else
return result;
-#endif /* HAVE__BUILTIN_CLZ */
+#endif /* HAVE_BITSCAN_REVERSE */
}
/*
@@ -99,9 +135,13 @@ pg_rightmost_one_pos32(uint32 word)
#ifdef HAVE__BUILTIN_CTZ
const uint32 orig_word = word;
int bitscan_result;
+#elif defined(_MSC_VER)
+ const unsigned long orig_word = word;
+ unsigned long bitscan_result;
+ bool non_zero;
#endif
-#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(HAVE_BITSCAN_FORWARD) || defined(USE_ASSERT_CHECKING)
int result = 0;
Assert(word != 0);
@@ -114,13 +154,20 @@ pg_rightmost_one_pos32(uint32 word)
result += pg_rightmost_one_pos[word & 255];
#endif
+#ifdef HAVE_BITSCAN_FORWARD
+
#if defined(HAVE__BUILTIN_CTZ)
bitscan_result = __builtin_ctz(orig_word);
+#elif defined(_MSC_VER)
+ non_zero = _BitScanForward(&bitscan_result, orig_word);
+ Assert(non_zero);
+#endif
Assert(bitscan_result == result);
return bitscan_result;
+
#else
return result;
-#endif /* HAVE__BUILTIN_CTZ */
+#endif /* HAVE_BITSCAN_FORWARD */
}
/*
@@ -133,9 +180,13 @@ pg_rightmost_one_pos64(uint64 word)
#ifdef HAVE__BUILTIN_CTZ
const uint64 orig_word = word;
int bitscan_result;
+#elif defined(_MSC_VER)
+ const unsigned __int64 orig_word = word;
+ unsigned long bitscan_result;
+ bool non_zero;
#endif
-#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
+#if !defined(HAVE_BITSCAN_FORWARD) || defined(USE_ASSERT_CHECKING)
int result = 0;
Assert(word != 0);
@@ -148,6 +199,8 @@ pg_rightmost_one_pos64(uint64 word)
result += pg_rightmost_one_pos[word & 255];
#endif
+#ifdef HAVE_BITSCAN_FORWARD
+
#if defined(HAVE__BUILTIN_CTZ)
#if defined(HAVE_LONG_INT_64)
bitscan_result = __builtin_ctzl(orig_word);
@@ -156,11 +209,17 @@ pg_rightmost_one_pos64(uint64 word)
#else
#error must have a working 64-bit integer datatype
#endif /* HAVE_LONG_INT_64 */
+
+#elif defined(_MSC_VER)
+ non_zero = _BitScanForward64(&bitscan_result, orig_word);
+ Assert(non_zero);
+#endif /* HAVE__BUILTIN_CTZ */
Assert(bitscan_result == result);
return bitscan_result;
+
#else
return result;
-#endif /* HAVE__BUILTIN_CTZ */
+#endif /* HAVE_BITSCAN_FORWARD */
}
/*
--
2.39.1
From 1f78f76ba5ed45cc8cf9c330512ffcfdb186dc05 Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Tue, 24 Jan 2023 14:39:26 +0700
Subject: [PATCH v4 1/4] Add asserts to verify bitscan intrinsics
---
src/include/port/pg_bitutils.h | 86 ++++++++++++++++++++++++----------
1 file changed, 60 insertions(+), 26 deletions(-)
diff --git a/src/include/port/pg_bitutils.h b/src/include/port/pg_bitutils.h
index a49a9c03d9..a5df4f1a35 100644
--- a/src/include/port/pg_bitutils.h
+++ b/src/include/port/pg_bitutils.h
@@ -26,10 +26,11 @@ static inline int
pg_leftmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CLZ
- Assert(word != 0);
+ int bitscan_result;
+#endif
- return 31 - __builtin_clz(word);
-#else
+#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
+ int result;
int shift = 32 - 8;
Assert(word != 0);
@@ -37,7 +38,15 @@ pg_leftmost_one_pos32(uint32 word)
while ((word >> shift) == 0)
shift -= 8;
- return shift + pg_leftmost_one_pos[(word >> shift) & 255];
+ result = shift + pg_leftmost_one_pos[(word >> shift) & 255];
+#endif
+
+#if defined(HAVE__BUILTIN_CLZ)
+ bitscan_result = 31 - __builtin_clz(word);
+ Assert(bitscan_result == result);
+ return bitscan_result;
+#else
+ return result;
#endif /* HAVE__BUILTIN_CLZ */
}
@@ -49,16 +58,11 @@ static inline int
pg_leftmost_one_pos64(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
+ int bitscan_result;
#endif
-#else /* !HAVE__BUILTIN_CLZ */
+
+#if !defined(HAVE__BUILTIN_CLZ) || defined(USE_ASSERT_CHECKING)
+ int result;
int shift = 64 - 8;
Assert(word != 0);
@@ -66,7 +70,21 @@ pg_leftmost_one_pos64(uint64 word)
while ((word >> shift) == 0)
shift -= 8;
- return shift + pg_leftmost_one_pos[(word >> shift) & 255];
+ result = shift + pg_leftmost_one_pos[(word >> shift) & 255];
+#endif
+
+#if defined(HAVE__BUILTIN_CLZ)
+#if defined(HAVE_LONG_INT_64)
+ bitscan_result = 63 - __builtin_clzl(word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+ bitscan_result = 63 - __builtin_clzll(word);
+#else
+#error must have a working 64-bit integer datatype
+#endif /* HAVE_LONG_INT_64 */
+ Assert(bitscan_result == result);
+ return bitscan_result;
+#else
+ return result;
#endif /* HAVE__BUILTIN_CLZ */
}
@@ -79,10 +97,11 @@ static inline int
pg_rightmost_one_pos32(uint32 word)
{
#ifdef HAVE__BUILTIN_CTZ
- Assert(word != 0);
+ const uint32 orig_word = word;
+ int bitscan_result;
+#endif
- return __builtin_ctz(word);
-#else
+#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
int result = 0;
Assert(word != 0);
@@ -93,6 +112,13 @@ pg_rightmost_one_pos32(uint32 word)
result += 8;
}
result += pg_rightmost_one_pos[word & 255];
+#endif
+
+#if defined(HAVE__BUILTIN_CTZ)
+ bitscan_result = __builtin_ctz(orig_word);
+ Assert(bitscan_result == result);
+ return bitscan_result;
+#else
return result;
#endif /* HAVE__BUILTIN_CTZ */
}
@@ -105,16 +131,11 @@ static inline int
pg_rightmost_one_pos64(uint64 word)
{
#ifdef HAVE__BUILTIN_CTZ
- Assert(word != 0);
-
-#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
+ const uint64 orig_word = word;
+ int bitscan_result;
#endif
-#else /* !HAVE__BUILTIN_CTZ */
+
+#if !defined(HAVE__BUILTIN_CTZ) || defined(USE_ASSERT_CHECKING)
int result = 0;
Assert(word != 0);
@@ -125,6 +146,19 @@ pg_rightmost_one_pos64(uint64 word)
result += 8;
}
result += pg_rightmost_one_pos[word & 255];
+#endif
+
+#if defined(HAVE__BUILTIN_CTZ)
+#if defined(HAVE_LONG_INT_64)
+ bitscan_result = __builtin_ctzl(orig_word);
+#elif defined(HAVE_LONG_LONG_INT_64)
+ bitscan_result = __builtin_ctzll(orig_word);
+#else
+#error must have a working 64-bit integer datatype
+#endif /* HAVE_LONG_INT_64 */
+ Assert(bitscan_result == result);
+ return bitscan_result;
+#else
return result;
#endif /* HAVE__BUILTIN_CTZ */
}
--
2.39.1
