| Message ID | 20100609150718.GC15770@kam.mff.cuni.cz |
|---|---|
| State | New |
| Headers | show |
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; > } > >
On Wed, 9 Jun 2010, Jan Hubicka wrote: > Hi, > here is updated patch addressing the code duplication. With __builtin_ctzl Not an objection to this patch as there are several existing cases of this issue, but I think scattering GCC_VERSION conditionals across the source tree (a few places also have __GNUC__ conditionals) is bad style. It would be better to define inline functions, or macros describing if a language feature is supported, in one place (with appropriate conditionals in their definitions) and use them everywhere. toplev.h has an example of this with definitions of floor_log2 and exact_log2, though on the whole I think system.h would be a better place for a central collection of such definitions - it has some already.
On 06/09/2010 10:46 PM, Joseph S. Myers wrote: > On Wed, 9 Jun 2010, Jan Hubicka wrote: > >> Hi, >> here is updated patch addressing the code duplication. With __builtin_ctzl > > Not an objection to this patch as there are several existing cases of this > issue, but I think scattering GCC_VERSION conditionals across the source > tree (a few places also have __GNUC__ conditionals) is bad style. There are also a number of comparisons GCC_VERSION >= 3400 which, while working in practice (only 3.4 is filtered out), are wrong. Paolo
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; }