From patchwork Wed Jun  9 15:07:19 2010
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: Speedup bitmap iterators
Date: Wed, 09 Jun 2010 05:07:19 -0000
From: Jan Hubicka <hubicka@ucw.cz>
X-Patchwork-Id: 55104
Message-Id: <20100609150718.GC15770@kam.mff.cuni.cz>
To: Paolo Carlini <paolo.carlini@oracle.com>
Cc: Richard Guenther <richard.guenther@gmail.com>,
 Jan Hubicka <hubicka@ucw.cz>, gcc-patches@gcc.gnu.org

Hi,
here is updated patch addressing the code duplication.  With __builtin_ctzl
I really believe we should fix it at codegen side if it turns out to be slow
on hosts we care about.  It is codegen bug, __builtin_ctzl exists for this
purpose IMO.

On i386 the codegen is good even if the topmost bit is usually set. It is
slower than test+jcc case but not by that big margin.  I might make some
statistics on average amount of bits skipped, but build time testing+oprofiling
definitly didn't found any regression here. 

Honza

	* bitmap.h (bmp_iter_next_bit): New.
	(bmp_iter_set, bmp_iter_and, bmp_iter_and_compl):
	Use it.


Index: bitmap.h
===================================================================
--- bitmap.h	(revision 160447)
+++ bitmap.h	(working copy)
@@ -385,6 +385,27 @@ bmp_iter_next (bitmap_iterator *bi, unsi
   *bit_no += 1;
 }
 
+/* Advance to first set bit in BI.  */
+
+static inline void
+bmp_iter_next_bit (bitmap_iterator * bi, unsigned *bit_no)
+{
+#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
+}
+
 /* Advance to the next nonzero bit of a single bitmap, we will have
    already advanced past the just iterated bit.  Return true if there
    is a bit to iterate.  */
@@ -396,11 +417,7 @@ bmp_iter_set (bitmap_iterator *bi, unsig
   if (bi->bits)
     {
     next_bit:
-      while (!(bi->bits & 1))
-	{
-	  bi->bits >>= 1;
-	  *bit_no += 1;
-	}
+      bmp_iter_next_bit (bi, bit_no);
       return true;
     }
 
@@ -443,11 +460,7 @@ bmp_iter_and (bitmap_iterator *bi, unsig
   if (bi->bits)
     {
     next_bit:
-      while (!(bi->bits & 1))
-	{
-	  bi->bits >>= 1;
-	  *bit_no += 1;
-	}
+      bmp_iter_next_bit (bi, bit_no);
       return true;
     }
 
@@ -510,11 +523,7 @@ bmp_iter_and_compl (bitmap_iterator *bi,
   if (bi->bits)
     {
     next_bit:
-      while (!(bi->bits & 1))
-	{
-	  bi->bits >>= 1;
-	  *bit_no += 1;
-	}
+      bmp_iter_next_bit (bi, bit_no);
       return true;
     }