On Fri, Jan 13, 2017 at 4:36 AM, Jeff Law <l...@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);
>
