* [RFA][PATCH 1a/4] [PR tree-optimization/33562] New sbitmap functions
@ 2017-01-13 3:36 Jeff Law
2017-01-13 8:42 ` Richard Biener
0 siblings, 1 reply; 2+ messages in thread
From: Jeff Law @ 2017-01-13 3:36 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1223 bytes --]
Per Richi's request, this breaks out the new sbitmap functions into
their own patch.
This patch should address all the concerns Richi raised in the prior
review. Namely the performance of the range set/clear and bootstrapping
with older or non-GCC C++ compilers and added missing docs.
The range set/clear functions work by first handling any partial changes
in the first word by building and applying a single bitmask. Then all
full word changes are handled by a call to memset, then finally
residuals in the last word with another bitmask application.
Internally I tested these by having both implementations and verifying
they gave identical results during a bootstrap and regression test cycle
(with the subsequent DSE patches that utilize the new functions).
I also tested the old gcc/non-gcc path by forcing it to be used rather
than the builtin popcount paths. Again, this was bootstrapped and
regression tested against the full DSE patches.
After those tests were complete, I ripped out the debugging/verification
bits and did another bootstrap and regression test of just the sbitmap
changes as well as a bootstrap and regression test of each stage in the
patchkit.
OK for the trunk?
Jeff
[-- Attachment #2: P0 --]
[-- Type: text/plain, Size: 6399 bytes --]
PR tree-optimization/33562
* sbitmap.h (bitmap_count_bits): Prototype.
(bitmap_clear_range, bitmap_set_range): Likewise.
* sbitmap.c (bitmap_clear_range): New function.
(bitmap_set_range, sbitmap_popcount, bitmap_count_bits): Likewise.
diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c
index c9bcea9..c065d13 100644
--- a/gcc/sbitmap.c
+++ b/gcc/sbitmap.c
@@ -202,6 +202,170 @@ bitmap_empty_p (const_sbitmap bmap)
return true;
}
+/* Clear COUNT bits from START in BMAP. */
+
+void
+bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count)
+{
+ if (count == 0)
+ return;
+
+ unsigned int start_word = start / SBITMAP_ELT_BITS;
+ unsigned int start_bitno = start % SBITMAP_ELT_BITS;
+
+ /* Clearing less than a full word, starting at the beginning of a word. */
+ if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
+ {
+ SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
+ bmap->elms[start_word] &= ~mask;
+ return;
+ }
+
+ unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
+ unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
+
+ /* Clearing starts somewhere in the middle of the first word. Clear up to
+ the end of the first word or the end of the requested region, whichever
+ comes first. */
+ if (start_bitno != 0)
+ {
+ unsigned int nbits = ((start_word == end_word)
+ ? end_bitno - start_bitno
+ : SBITMAP_ELT_BITS - start_bitno);
+ SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
+ mask <<= start_bitno;
+ bmap->elms[start_word] &= ~mask;
+ start_word++;
+ count -= nbits;
+ }
+
+ if (count == 0)
+ return;
+
+ /* Now clear words at a time until we hit a partial word. */
+ unsigned int nwords = (end_word - start_word);
+ if (nwords)
+ {
+ memset (&bmap->elms[start_word], 0, nwords * sizeof (SBITMAP_ELT_TYPE));
+ count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
+ start_word += nwords;
+ }
+
+ if (count == 0)
+ return;
+
+ /* Now handle residuals in the last word. */
+ SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
+ bmap->elms[start_word] &= ~mask;
+}
+
+/* Set COUNT bits from START in BMAP. */
+void
+bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count)
+{
+ if (count == 0)
+ return;
+
+ unsigned int start_word = start / SBITMAP_ELT_BITS;
+ unsigned int start_bitno = start % SBITMAP_ELT_BITS;
+
+ /* Setting less than a full word, starting at the beginning of a word. */
+ if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
+ {
+ SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
+ bmap->elms[start_word] |= mask;
+ return;
+ }
+
+ unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
+ unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
+
+ /* Setting starts somewhere in the middle of the first word. Set up to
+ the end of the first word or the end of the requested region, whichever
+ comes first. */
+ if (start_bitno != 0)
+ {
+ unsigned int nbits = ((start_word == end_word)
+ ? end_bitno - start_bitno
+ : SBITMAP_ELT_BITS - start_bitno);
+ SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
+ mask <<= start_bitno;
+ bmap->elms[start_word] |= mask;
+ start_word++;
+ count -= nbits;
+ }
+
+ if (count == 0)
+ return;
+
+ /* Now set words at a time until we hit a partial word. */
+ unsigned int nwords = (end_word - start_word);
+ if (nwords)
+ {
+ memset (&bmap->elms[start_word], 0xff,
+ nwords * sizeof (SBITMAP_ELT_TYPE));
+ count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
+ start_word += nwords;
+ }
+
+ if (count == 0)
+ return;
+
+ /* Now handle residuals in the last word. */
+ SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
+ bmap->elms[start_word] |= mask;
+}
+
+#if GCC_VERSION < 3400
+/* Table of number of set bits in a character, indexed by value of char. */
+static const unsigned char popcount_table[] =
+{
+ 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
+ 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
+};
+
+static unsigned long
+sbitmap_popcount (SBITMAP_ELT_TYPE a)
+{
+ unsigned long ret = 0;
+ unsigned i;
+
+ /* Just do this the table way for now */
+ for (i = 0; i < HOST_BITS_PER_WIDEST_FAST_INT; i += 8)
+ ret += popcount_table[(a >> i) & 0xff];
+ return ret;
+}
+#endif
+
+/* Count and return the number of bits set in the bitmap BMAP. */
+
+unsigned int
+bitmap_count_bits (const_sbitmap bmap)
+{
+ unsigned int count = 0;
+ for (unsigned int i = 0; i < bmap->size; i++)
+ if (bmap->elms[i])
+ {
+#if GCC_VERSION < 3400
+ count += sbitmap_popcount (bmap->elms[i]);
+#else
+# if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
+ count += __builtin_popcountl (bmap->elms[i]);
+# elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
+ count += __builtin_popcountll (bmap->elms[i]);
+# else
+ count += __builtin_popcount (bmap->elms[i]);
+# endif
+#endif
+ }
+ return count;
+}
/* Zero all elements in a bitmap. */
diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h
index 26fe3db..ce4d27d 100644
--- a/gcc/sbitmap.h
+++ b/gcc/sbitmap.h
@@ -231,8 +231,11 @@ extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
extern void bitmap_copy (sbitmap, const_sbitmap);
extern int bitmap_equal_p (const_sbitmap, const_sbitmap);
+extern unsigned int bitmap_count_bits (const_sbitmap);
extern bool bitmap_empty_p (const_sbitmap);
extern void bitmap_clear (sbitmap);
+extern void bitmap_clear_range (sbitmap, unsigned, unsigned);
+extern void bitmap_set_range (sbitmap, unsigned, unsigned);
extern void bitmap_ones (sbitmap);
extern void bitmap_vector_clear (sbitmap *, unsigned int);
extern void bitmap_vector_ones (sbitmap *, unsigned int);
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [RFA][PATCH 1a/4] [PR tree-optimization/33562] New sbitmap functions
2017-01-13 3:36 [RFA][PATCH 1a/4] [PR tree-optimization/33562] New sbitmap functions Jeff Law
@ 2017-01-13 8:42 ` Richard Biener
0 siblings, 0 replies; 2+ messages in thread
From: Richard Biener @ 2017-01-13 8:42 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Fri, Jan 13, 2017 at 4:36 AM, Jeff Law <law@redhat.com> wrote:
> Per Richi's request, this breaks out the new sbitmap functions into their
> own patch.
>
> This patch should address all the concerns Richi raised in the prior review.
> Namely the performance of the range set/clear and bootstrapping with older
> or non-GCC C++ compilers and added missing docs.
>
> The range set/clear functions work by first handling any partial changes in
> the first word by building and applying a single bitmask. Then all full
> word changes are handled by a call to memset, then finally residuals in the
> last word with another bitmask application.
>
> Internally I tested these by having both implementations and verifying they
> gave identical results during a bootstrap and regression test cycle (with
> the subsequent DSE patches that utilize the new functions).
>
> I also tested the old gcc/non-gcc path by forcing it to be used rather than
> the builtin popcount paths. Again, this was bootstrapped and regression
> tested against the full DSE patches.
>
> After those tests were complete, I ripped out the debugging/verification
> bits and did another bootstrap and regression test of just the sbitmap
> changes as well as a bootstrap and regression test of each stage in the
> patchkit.
>
> OK for the trunk?
Ok.
Thanks,
Richard.
> Jeff
>
>
>
> PR tree-optimization/33562
> * sbitmap.h (bitmap_count_bits): Prototype.
> (bitmap_clear_range, bitmap_set_range): Likewise.
> * sbitmap.c (bitmap_clear_range): New function.
> (bitmap_set_range, sbitmap_popcount, bitmap_count_bits): Likewise.
>
> diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c
> index c9bcea9..c065d13 100644
> --- a/gcc/sbitmap.c
> +++ b/gcc/sbitmap.c
> @@ -202,6 +202,170 @@ bitmap_empty_p (const_sbitmap bmap)
> return true;
> }
>
> +/* Clear COUNT bits from START in BMAP. */
> +
> +void
> +bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count)
> +{
> + if (count == 0)
> + return;
> +
> + unsigned int start_word = start / SBITMAP_ELT_BITS;
> + unsigned int start_bitno = start % SBITMAP_ELT_BITS;
> +
> + /* Clearing less than a full word, starting at the beginning of a word.
> */
> + if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
> + {
> + SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
> + bmap->elms[start_word] &= ~mask;
> + return;
> + }
> +
> + unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
> + unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
> +
> + /* Clearing starts somewhere in the middle of the first word. Clear up
> to
> + the end of the first word or the end of the requested region,
> whichever
> + comes first. */
> + if (start_bitno != 0)
> + {
> + unsigned int nbits = ((start_word == end_word)
> + ? end_bitno - start_bitno
> + : SBITMAP_ELT_BITS - start_bitno);
> + SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
> + mask <<= start_bitno;
> + bmap->elms[start_word] &= ~mask;
> + start_word++;
> + count -= nbits;
> + }
> +
> + if (count == 0)
> + return;
> +
> + /* Now clear words at a time until we hit a partial word. */
> + unsigned int nwords = (end_word - start_word);
> + if (nwords)
> + {
> + memset (&bmap->elms[start_word], 0, nwords * sizeof
> (SBITMAP_ELT_TYPE));
> + count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
> + start_word += nwords;
> + }
> +
> + if (count == 0)
> + return;
> +
> + /* Now handle residuals in the last word. */
> + SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
> + bmap->elms[start_word] &= ~mask;
> +}
> +
> +/* Set COUNT bits from START in BMAP. */
> +void
> +bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count)
> +{
> + if (count == 0)
> + return;
> +
> + unsigned int start_word = start / SBITMAP_ELT_BITS;
> + unsigned int start_bitno = start % SBITMAP_ELT_BITS;
> +
> + /* Setting less than a full word, starting at the beginning of a word.
> */
> + if (start_bitno == 0 && count < SBITMAP_ELT_BITS)
> + {
> + SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
> + bmap->elms[start_word] |= mask;
> + return;
> + }
> +
> + unsigned int end_word = (start + count) / SBITMAP_ELT_BITS;
> + unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS;
> +
> + /* Setting starts somewhere in the middle of the first word. Set up to
> + the end of the first word or the end of the requested region,
> whichever
> + comes first. */
> + if (start_bitno != 0)
> + {
> + unsigned int nbits = ((start_word == end_word)
> + ? end_bitno - start_bitno
> + : SBITMAP_ELT_BITS - start_bitno);
> + SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1;
> + mask <<= start_bitno;
> + bmap->elms[start_word] |= mask;
> + start_word++;
> + count -= nbits;
> + }
> +
> + if (count == 0)
> + return;
> +
> + /* Now set words at a time until we hit a partial word. */
> + unsigned int nwords = (end_word - start_word);
> + if (nwords)
> + {
> + memset (&bmap->elms[start_word], 0xff,
> + nwords * sizeof (SBITMAP_ELT_TYPE));
> + count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT;
> + start_word += nwords;
> + }
> +
> + if (count == 0)
> + return;
> +
> + /* Now handle residuals in the last word. */
> + SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1;
> + bmap->elms[start_word] |= mask;
> +}
> +
> +#if GCC_VERSION < 3400
> +/* Table of number of set bits in a character, indexed by value of char.
> */
> +static const unsigned char popcount_table[] =
> +{
> + 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
> + 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
> + 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
> + 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
> + 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
> + 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
> + 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
> + 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
> +};
> +
> +static unsigned long
> +sbitmap_popcount (SBITMAP_ELT_TYPE a)
> +{
> + unsigned long ret = 0;
> + unsigned i;
> +
> + /* Just do this the table way for now */
> + for (i = 0; i < HOST_BITS_PER_WIDEST_FAST_INT; i += 8)
> + ret += popcount_table[(a >> i) & 0xff];
> + return ret;
> +}
> +#endif
> +
> +/* Count and return the number of bits set in the bitmap BMAP. */
> +
> +unsigned int
> +bitmap_count_bits (const_sbitmap bmap)
> +{
> + unsigned int count = 0;
> + for (unsigned int i = 0; i < bmap->size; i++)
> + if (bmap->elms[i])
> + {
> +#if GCC_VERSION < 3400
> + count += sbitmap_popcount (bmap->elms[i]);
> +#else
> +# if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
> + count += __builtin_popcountl (bmap->elms[i]);
> +# elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG
> + count += __builtin_popcountll (bmap->elms[i]);
> +# else
> + count += __builtin_popcount (bmap->elms[i]);
> +# endif
> +#endif
> + }
> + return count;
> +}
>
> /* Zero all elements in a bitmap. */
>
> diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h
> index 26fe3db..ce4d27d 100644
> --- a/gcc/sbitmap.h
> +++ b/gcc/sbitmap.h
> @@ -231,8 +231,11 @@ extern sbitmap *sbitmap_vector_alloc (unsigned int,
> unsigned int);
> extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
> extern void bitmap_copy (sbitmap, const_sbitmap);
> extern int bitmap_equal_p (const_sbitmap, const_sbitmap);
> +extern unsigned int bitmap_count_bits (const_sbitmap);
> extern bool bitmap_empty_p (const_sbitmap);
> extern void bitmap_clear (sbitmap);
> +extern void bitmap_clear_range (sbitmap, unsigned, unsigned);
> +extern void bitmap_set_range (sbitmap, unsigned, unsigned);
> extern void bitmap_ones (sbitmap);
> extern void bitmap_vector_clear (sbitmap *, unsigned int);
> extern void bitmap_vector_ones (sbitmap *, unsigned int);
>
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2017-01-13 8:42 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-01-13 3:36 [RFA][PATCH 1a/4] [PR tree-optimization/33562] New sbitmap functions Jeff Law
2017-01-13 8:42 ` Richard Biener
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).