This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Speedup bitmap iterators


On Wed, Jun 9, 2010 at 5:07 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> 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.

This is ok if it bootstraps & regtests.  Please let other maintainers
the chance to complain thouhg.

Thanks,
Richard.

> 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;
> ? ? }
>
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]