This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Speedup bitmap iterators
- From: Jan Hubicka <hubicka at ucw dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Wed, 9 Jun 2010 11:51:37 +0200
- Subject: Speedup bitmap iterators
Hi,
this patch avoid dififcult to predict branch in bmp walking. Improving:
:static inline bool
:bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
:{
: /* If our current word is nonzero, it contains the bit we want. */
1551 0.1115 : if (bi->bits)
: {
: next_bit:
7282 0.5237 : while (!(bi->bits & 1))
: {
5312 0.3820 : bi->bits >>= 1;
7904 0.5685 : *bit_no += 1;
: }
: return true;
: }
to:
: bool
:bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
:{
: /* If our current word is nonzero, it contains the bit we want. */
1274 0.0973 : if (bi->bits)
: {
: next_bit:
:#if (GCC_VERSION >= 3004)
: {
1106 0.0845 : unsigned int n = __builtin_ctzl (bi->bits);
: gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
1811 0.1384 : bi->bits >>= n;
1892 0.1446 : *bit_no += n;
: }
:#else
The code (including checking for 3.4) is the same as one present in
bitmap_first_bit already.
Bootstrapped/regtested x86_64-linux, OK?
Honza
* bitmap.h (bmp_iter_set, bmp_iter_and, bmp_iter_and_compl):
Use __builtin_ctzl where possible.
Index: bitmap.h
===================================================================
--- bitmap.h (revision 160447)
+++ bitmap.h (working copy)
@@ -396,11 +396,20 @@ bmp_iter_set (bitmap_iterator *bi, unsig
if (bi->bits)
{
next_bit:
+#if (GCC_VERSION >= 3004)
+ {
+ unsigned int n = __builtin_ctzl (bi->bits);
+ gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
+ bi->bits >>= n;
+ *bit_no += n;
+ }
+#else
while (!(bi->bits & 1))
{
bi->bits >>= 1;
*bit_no += 1;
}
+#endif
return true;
}
@@ -443,11 +452,20 @@ bmp_iter_and (bitmap_iterator *bi, unsig
if (bi->bits)
{
next_bit:
+#if (GCC_VERSION >= 3004)
+ {
+ unsigned int n = __builtin_ctzl (bi->bits);
+ gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
+ bi->bits >>= n;
+ *bit_no += n;
+ }
+#else
while (!(bi->bits & 1))
{
bi->bits >>= 1;
*bit_no += 1;
}
+#endif
return true;
}
@@ -510,11 +528,20 @@ bmp_iter_and_compl (bitmap_iterator *bi,
if (bi->bits)
{
next_bit:
+#if (GCC_VERSION >= 3004)
+ {
+ unsigned int n = __builtin_ctzl (bi->bits);
+ gcc_assert (sizeof (unsigned long) == sizeof (BITMAP_WORD));
+ bi->bits >>= n;
+ *bit_no += n;
+ }
+#else
while (!(bi->bits & 1))
{
bi->bits >>= 1;
*bit_no += 1;
}
+#endif
return true;
}