Use clz, ctz for msb_pos, lsb_pos, if available

On many modern platforms these functions can be replaced by a single
machine instruction or two.  This commit looks for this possibility and
uses it if possible.

1 files changed, 109 insertions, 2 deletions

diff --git a/inline.h b/inline.h
index 7ce872b1bf..c8a88f7a6d 100644
--- a/inline.h
+++ b/inline.h
@@ -664,6 +664,59 @@ Perl_is_utf8_invariant_string_loc(const U8* const s, STRLEN len, const U8 ** ep)
     return TRUE;
 }
 
+/* See if the platform has builtins for finding the most/least significant bit,
+ * and which one is right for using on 32 and 64 bit operands */
+#if (__has_builtin(__builtin_clz) || PERL_GCC_VERSION_GE(3,4,0))
+#  if U32SIZE == INTSIZE
+#    define PERL_CLZ_32 __builtin_clz
+#  endif
+#  if defined(U64TYPE) && U64SIZE == INTSIZE
+#    define PERL_CLZ_64 __builtin_clz
+#  endif
+#endif
+#if (__has_builtin(__builtin_ctz) || PERL_GCC_VERSION_GE(3,4,0))
+#  if U32SIZE == INTSIZE
+#    define PERL_CTZ_32 __builtin_ctz
+#  endif
+#  if defined(U64TYPE) && U64SIZE == INTSIZE
+#    define PERL_CTZ_64 __builtin_ctz
+#  endif
+#endif
+
+#if (__has_builtin(__builtin_clzl) || PERL_GCC_VERSION_GE(3,4,0))
+#  if U32SIZE == LONGSIZE && ! defined(PERL_CLZ_32)
+#    define PERL_CLZ_32 __builtin_clzl
+#  endif
+#  if defined(U64TYPE) && U64SIZE == LONGSIZE && ! defined(PERL_CLZ_64)
+#    define PERL_CLZ_64 __builtin_clzl
+#  endif
+#endif
+#if (__has_builtin(__builtin_ctzl) || PERL_GCC_VERSION_GE(3,4,0))
+#  if U32SIZE == LONGSIZE && ! defined(PERL_CTZ_32)
+#    define PERL_CTZ_32 __builtin_ctzl
+#  endif
+#  if defined(U64TYPE) && U64SIZE == LONGSIZE && ! defined(PERL_CTZ_64)
+#    define PERL_CTZ_64 __builtin_ctzl
+#  endif
+#endif
+
+#if (__has_builtin(__builtin_clzll) || PERL_GCC_VERSION_GE(3,4,0))
+#  if U32SIZE == LONGLONGSIZE && ! defined(PERL_CLZ_32)
+#    define PERL_CLZ_32 __builtin_clzll
+#  endif
+#  if defined(U64TYPE) && U64SIZE == LONGLONGSIZE && ! defined(PERL_CLZ_64)
+#    define PERL_CLZ_64 __builtin_clzll
+#  endif
+#endif
+#if (__has_builtin(__builtin_ctzll) || PERL_GCC_VERSION_GE(3,4,0))
+#  if U32SIZE == LONGLONGSIZE && ! defined(PERL_CTZ_32)
+#    define PERL_CTZ_32 __builtin_ctzll
+#  endif
+#  if defined(U64TYPE) && U64SIZE == LONGLONGSIZE && ! defined(PERL_CTZ_64)
+#    define PERL_CTZ_64 __builtin_ctzll
+#  endif
+#endif
+
 /* Below are functions to find the first, last, or only set bit in a word.  On
  * platforms with 64-bit capability, there is a pair for each operation; the
  * first taking a 64 bit operand, and the second a 32 bit one.  The logic is
@@ -679,7 +732,20 @@ Perl_lsbit_pos64(U64 word)
 
     ASSUME(word != 0);
 
-    /*  Isolate the lsb;
+    /* If we can determine that the platform has a usable fast method to get
+     * this info, use that */
+
+#  if defined(PERL_CTZ_64)
+
+    return (unsigned) PERL_CTZ_64(word);
+
+#  else
+
+    /* Here, we didn't find a fast method for finding the lsb.  Fall back to
+     * making the lsb the only set bit in the word, and use our function that
+     * works on words with a single bit set.
+     *
+     * Isolate the lsb;
      * https://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set
      *
      * The word will look like this, with a rightmost set bit in position 's':
@@ -695,6 +761,9 @@ Perl_lsbit_pos64(U64 word)
      *  complain about negating an unsigned.)
      */
     return single_1bit_pos64(word & (~word + 1));
+
+#  endif
+
 }
 
 #  define lsbit_pos_uintmax_(word) lsbit_pos64(word)
@@ -710,9 +779,22 @@ Perl_lsbit_pos32(U32 word)
 
     ASSUME(word != 0);
 
+#if defined(PERL_CTZ_32)
+
+    return (unsigned) PERL_CTZ_32(word);
+
+#else
+
     return single_1bit_pos32(word & (~word + 1));
+
+#endif
+
 }
 
+/* Convert the leading zeros count to the bit position of the first set bit.
+ * This just subtracts from the highest position, 31 or 63 */
+#define LZC_TO_MSBIT_POS_(size, lzc)  ((size##SIZE * CHARBITS - 1) - (lzc))
+
 #ifdef U64TYPE  /* HAS_QUAD not usable outside the core */
 
 PERL_STATIC_INLINE unsigned
@@ -723,7 +805,20 @@ Perl_msbit_pos64(U64 word)
 
     ASSUME(word != 0);
 
-    /* Isolate the msb; http://codeforces.com/blog/entry/10330
+    /* If we can determine that the platform has a usable fast method to get
+     * this, use that */
+
+#  if defined(PERL_CLZ_64)
+
+    return (unsigned) LZC_TO_MSBIT_POS_(U64, PERL_CLZ_64(word));
+
+#  else
+
+    /* Here, we didn't find a fast method for finding the msb.  Fall back to
+     * making the msb the only set bit in the word, and use our function that
+     * works on words with a single bit set.
+     *
+     * Isolate the msb; http://codeforces.com/blog/entry/10330
      *
      * Only the most significant set bit matters.  Or'ing word with its right
      * shift of 1 makes that bit and the next one to its right both 1.
@@ -742,6 +837,9 @@ Perl_msbit_pos64(U64 word)
 
     /* Now we have a single bit set */
     return single_1bit_pos64(word);
+
+#  endif
+
 }
 
 #  define msbit_pos_uintmax_(word) msbit_pos64(word)
@@ -757,6 +855,12 @@ Perl_msbit_pos32(U32 word)
 
     ASSUME(word != 0);
 
+#if defined(PERL_CLZ_32)
+
+    return (unsigned) LZC_TO_MSBIT_POS_(U32, PERL_CLZ_32(word));
+
+#else
+
     word |= (word >>  1);
     word |= (word >>  2);
     word |= (word >>  4);
@@ -764,6 +868,9 @@ Perl_msbit_pos32(U32 word)
     word |= (word >> 16);
     word -= (word >> 1);
     return single_1bit_pos32(word);
+
+#endif
+
 }
 
 #ifdef U64TYPE  /* HAS_QUAD not usable outside the core */