From 87f8e12bd0c7848b94953326d941c48d13cedd2b Mon Sep 17 00:00:00 2001 From: segher Date: Thu, 28 Apr 2016 18:43:12 +0000 Subject: [PATCH] sbitmap: Remove popcount In r193072 sbitmap_popcount was removed, so we cannot ask for the popcount of an sbitmap anymore. Nothing calls sbitmap_alloc_with_popcount either. This patch removes everything else popcount-related from sbitmap. * cfganal.c (bitmap_intersection_of_succs): Delete assert checking dst->popcount. (bitmap_intersection_of_preds): Ditto. (bitmap_union_of_succs): Ditto. (bitmap_union_of_preds): Ditto. * sbitmap.c (do_popcount): Delete. (BITMAP_DEBUGGING): Delete. (sbitmap_verify_popcount): Delete. (sbitmap_alloc): Don't initialize the popcount field. (sbitmap_alloc_with_popcount): Delete. (sbitmap_resize): Don't resize the popcount array. (sbitmap_vector_alloc): Don't initialize the popcount field. (bitmap_copy): Don't copy the popcount array. (bitmap_clear): Don't clear the popcount array. (bitmap_clear): Delete the popcount array handling. (bitmap_ior_and_compl): Delete the popcount assert. (bitmap_not): Ditto. (bitmap_and_compl): Ditto. (bitmap_and): Delete the popcount array handling. (bitmap_xor): Ditto. (bitmap_ior): Ditto. (bitmap_or_and): Delete the popcount assert. (bitmap_and_or): Ditto. (popcount_table): Delete. (sbitmap_elt_popcount): Delete. * sbitmap.h (simple_bitmap_def): Delete the popcount field. (bitmap_set_bit): Delete the popcount assert. (bitmap_clear_bit): Ditto. (sbitmap_free): Don't free the popcount array. (sbitmap_alloc_with_popcount): Delete declaration. (sbitmap_popcount): Ditto. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@235592 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 34 ++++++++++++ gcc/cfganal.c | 8 --- gcc/sbitmap.c | 167 ++-------------------------------------------------------- gcc/sbitmap.h | 6 --- 4 files changed, 39 insertions(+), 176 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index cf51826dd6e..a7b3a69d670 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,37 @@ +2016-04-28 Segher Boessenkool + + * cfganal.c (bitmap_intersection_of_succs): Delete assert checking + dst->popcount. + (bitmap_intersection_of_preds): Ditto. + (bitmap_union_of_succs): Ditto. + (bitmap_union_of_preds): Ditto. + * sbitmap.c (do_popcount): Delete. + (BITMAP_DEBUGGING): Delete. + (sbitmap_verify_popcount): Delete. + (sbitmap_alloc): Don't initialize the popcount field. + (sbitmap_alloc_with_popcount): Delete. + (sbitmap_resize): Don't resize the popcount array. + (sbitmap_vector_alloc): Don't initialize the popcount field. + (bitmap_copy): Don't copy the popcount array. + (bitmap_clear): Don't clear the popcount array. + (bitmap_clear): Delete the popcount array handling. + (bitmap_ior_and_compl): Delete the popcount assert. + (bitmap_not): Ditto. + (bitmap_and_compl): Ditto. + (bitmap_and): Delete the popcount array handling. + (bitmap_xor): Ditto. + (bitmap_ior): Ditto. + (bitmap_or_and): Delete the popcount assert. + (bitmap_and_or): Ditto. + (popcount_table): Delete. + (sbitmap_elt_popcount): Delete. + * sbitmap.h (simple_bitmap_def): Delete the popcount field. + (bitmap_set_bit): Delete the popcount assert. + (bitmap_clear_bit): Ditto. + (sbitmap_free): Don't free the popcount array. + (sbitmap_alloc_with_popcount): Delete declaration. + (sbitmap_popcount): Ditto. + 2016-04-28 Joern Rennecke Andrew Burgess diff --git a/gcc/cfganal.c b/gcc/cfganal.c index bf9866b21d5..189762cba8e 100644 --- a/gcc/cfganal.c +++ b/gcc/cfganal.c @@ -1378,8 +1378,6 @@ bitmap_intersection_of_succs (sbitmap dst, sbitmap *src, basic_block b) edge e; unsigned ix; - gcc_assert (!dst->popcount); - for (e = NULL, ix = 0; ix < EDGE_COUNT (b->succs); ix++) { e = EDGE_SUCC (b, ix); @@ -1419,8 +1417,6 @@ bitmap_intersection_of_preds (sbitmap dst, sbitmap *src, basic_block b) edge e; unsigned ix; - gcc_assert (!dst->popcount); - for (e = NULL, ix = 0; ix < EDGE_COUNT (b->preds); ix++) { e = EDGE_PRED (b, ix); @@ -1460,8 +1456,6 @@ bitmap_union_of_succs (sbitmap dst, sbitmap *src, basic_block b) edge e; unsigned ix; - gcc_assert (!dst->popcount); - for (ix = 0; ix < EDGE_COUNT (b->succs); ix++) { e = EDGE_SUCC (b, ix); @@ -1501,8 +1495,6 @@ bitmap_union_of_preds (sbitmap dst, sbitmap *src, basic_block b) edge e; unsigned ix; - gcc_assert (!dst->popcount); - for (ix = 0; ix < EDGE_COUNT (b->preds); ix++) { e = EDGE_PRED (b, ix); diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c index 87e5c514612..10b4347d65b 100644 --- a/gcc/sbitmap.c +++ b/gcc/sbitmap.c @@ -22,25 +22,6 @@ along with GCC; see the file COPYING3. If not see #include "coretypes.h" #include "sbitmap.h" -/* This suffices for roughly 99% of the hosts we run on, and the rest - don't have 256 bit integers. */ -#if SBITMAP_ELT_BITS > 255 -#error Need to increase size of datatype used for popcount -#endif - -#if GCC_VERSION >= 3400 -# if SBITMAP_ELT_BITS == HOST_BITS_PER_LONG -# define do_popcount(x) __builtin_popcountl (x) -# elif SBITMAP_ELT_BITS == HOST_BITS_PER_LONGLONG -# define do_popcount(x) __builtin_popcountll (x) -# else -# error "internal error: sbitmap.h and hwint.h are inconsistent" -# endif -#else -static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE); -# define do_popcount(x) sbitmap_elt_popcount (x) -#endif - typedef SBITMAP_ELT_TYPE *sbitmap_ptr; typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr; @@ -51,29 +32,6 @@ static inline unsigned int sbitmap_size_bytes (const_sbitmap map) return map->size * sizeof (SBITMAP_ELT_TYPE); } -/* This macro controls debugging that is as expensive as the - operations it verifies. */ - -/* #define BITMAP_DEBUGGING */ -#ifdef BITMAP_DEBUGGING - -/* Verify the population count of sbitmap A matches the cached value, - if there is a cached value. */ - -static void -sbitmap_verify_popcount (const_sbitmap a) -{ - unsigned ix; - unsigned int lastword; - - if (!a->popcount) - return; - - lastword = a->size; - for (ix = 0; ix < lastword; ix++) - gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix])); -} -#endif /* Bitmap manipulation routines. */ @@ -92,17 +50,6 @@ sbitmap_alloc (unsigned int n_elms) bmap = (sbitmap) xmalloc (amt); bmap->n_bits = n_elms; bmap->size = size; - bmap->popcount = NULL; - return bmap; -} - -/* Allocate a simple bitmap of N_ELMS bits, and a popcount array. */ - -sbitmap -sbitmap_alloc_with_popcount (unsigned int n_elms) -{ - sbitmap const bmap = sbitmap_alloc (n_elms); - bmap->popcount = XNEWVEC (unsigned char, bmap->size); return bmap; } @@ -123,8 +70,6 @@ sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) amt = (sizeof (struct simple_bitmap_def) + bytes - sizeof (SBITMAP_ELT_TYPE)); bmap = (sbitmap) xrealloc (bmap, amt); - if (bmap->popcount) - bmap->popcount = XRESIZEVEC (unsigned char, bmap->popcount, size); } if (n_elms > bmap->n_bits) @@ -147,27 +92,15 @@ sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); } else - { - memset (bmap->elms + bmap->size, 0, - bytes - sbitmap_size_bytes (bmap)); - if (bmap->popcount) - memset (bmap->popcount + bmap->size, 0, - (size * sizeof (unsigned char)) - - (bmap->size * sizeof (unsigned char))); - - } + memset (bmap->elms + bmap->size, 0, bytes - sbitmap_size_bytes (bmap)); } else if (n_elms < bmap->n_bits) { /* Clear the surplus bits in the last word. */ last_bit = n_elms % SBITMAP_ELT_BITS; if (last_bit) - { - bmap->elms[size - 1] - &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); - if (bmap->popcount) - bmap->popcount[size - 1] = do_popcount (bmap->elms[size - 1]); - } + bmap->elms[size - 1] + &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); } bmap->n_bits = n_elms; @@ -236,7 +169,6 @@ sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms) bitmap_vector[i] = b; b->n_bits = n_elms; b->size = size; - b->popcount = NULL; } return bitmap_vector; @@ -248,8 +180,6 @@ void bitmap_copy (sbitmap dst, const_sbitmap src) { memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); - if (dst->popcount) - memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size); } /* Determine if a == b. */ @@ -279,8 +209,6 @@ void bitmap_clear (sbitmap bmap) { memset (bmap->elms, 0, sbitmap_size_bytes (bmap)); - if (bmap->popcount) - memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char)); } /* Set all elements in a bitmap to ones. */ @@ -291,18 +219,11 @@ bitmap_ones (sbitmap bmap) unsigned int last_bit; memset (bmap->elms, -1, sbitmap_size_bytes (bmap)); - if (bmap->popcount) - memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char)); last_bit = bmap->n_bits % SBITMAP_ELT_BITS; if (last_bit) - { - bmap->elms[bmap->size - 1] - = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); - if (bmap->popcount) - bmap->popcount[bmap->size - 1] - = do_popcount (bmap->elms[bmap->size - 1]); - } + bmap->elms[bmap->size - 1] + = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); } /* Zero a vector of N_VECS bitmaps. */ @@ -341,8 +262,6 @@ bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitm const_sbitmap_ptr cp = c->elms; SBITMAP_ELT_TYPE changed = 0; - gcc_assert (!dst->popcount); - for (i = 0; i < n; i++) { const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++); @@ -363,8 +282,6 @@ bitmap_not (sbitmap dst, const_sbitmap src) const_sbitmap_ptr srcp = src->elms; unsigned int last_bit; - gcc_assert (!dst->popcount); - for (i = 0; i < n; i++) *dstp++ = ~*srcp++; @@ -387,8 +304,6 @@ bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b) const_sbitmap_ptr ap = a->elms; const_sbitmap_ptr bp = b->elms; - gcc_assert (!dst->popcount); - /* A should be at least as large as DEST, to have a defined source. */ gcc_assert (a->size >= dst_size); /* If minuend is smaller, we simply pretend it to be zero bits, i.e. @@ -432,27 +347,15 @@ bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b) sbitmap_ptr dstp = dst->elms; const_sbitmap_ptr ap = a->elms; const_sbitmap_ptr bp = b->elms; - bool has_popcount = dst->popcount != NULL; - unsigned char *popcountp = dst->popcount; SBITMAP_ELT_TYPE changed = 0; for (i = 0; i < n; i++) { const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++; SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp; - if (has_popcount) - { - if (wordchanged) - *popcountp = do_popcount (tmp); - popcountp++; - } *dstp++ = tmp; changed |= wordchanged; } -#ifdef BITMAP_DEBUGGING - if (has_popcount) - sbitmap_verify_popcount (dst); -#endif return changed != 0; } @@ -466,27 +369,15 @@ bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b) sbitmap_ptr dstp = dst->elms; const_sbitmap_ptr ap = a->elms; const_sbitmap_ptr bp = b->elms; - bool has_popcount = dst->popcount != NULL; - unsigned char *popcountp = dst->popcount; SBITMAP_ELT_TYPE changed = 0; for (i = 0; i < n; i++) { const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++; SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp; - if (has_popcount) - { - if (wordchanged) - *popcountp = do_popcount (tmp); - popcountp++; - } *dstp++ = tmp; changed |= wordchanged; } -#ifdef BITMAP_DEBUGGING - if (has_popcount) - sbitmap_verify_popcount (dst); -#endif return changed != 0; } @@ -500,27 +391,15 @@ bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b) sbitmap_ptr dstp = dst->elms; const_sbitmap_ptr ap = a->elms; const_sbitmap_ptr bp = b->elms; - bool has_popcount = dst->popcount != NULL; - unsigned char *popcountp = dst->popcount; SBITMAP_ELT_TYPE changed = 0; for (i = 0; i < n; i++) { const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++; SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp; - if (has_popcount) - { - if (wordchanged) - *popcountp = do_popcount (tmp); - popcountp++; - } *dstp++ = tmp; changed |= wordchanged; } -#ifdef BITMAP_DEBUGGING - if (has_popcount) - sbitmap_verify_popcount (dst); -#endif return changed != 0; } @@ -552,8 +431,6 @@ bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) const_sbitmap_ptr cp = c->elms; SBITMAP_ELT_TYPE changed = 0; - gcc_assert (!dst->popcount); - for (i = 0; i < n; i++) { const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++); @@ -577,8 +454,6 @@ bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) const_sbitmap_ptr cp = c->elms; SBITMAP_ELT_TYPE changed = 0; - gcc_assert (!dst->popcount); - for (i = 0; i < n; i++) { const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++); @@ -729,35 +604,3 @@ dump_bitmap_vector (FILE *file, const char *title, const char *subtitle, fprintf (file, "\n"); } - -#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, -}; - -/* Count the bits in an SBITMAP element A. */ - -static unsigned long -sbitmap_elt_popcount (SBITMAP_ELT_TYPE a) -{ - unsigned long ret = 0; - unsigned i; - - if (a == 0) - return 0; - - /* Just do this the table way for now */ - for (i = 0; i < SBITMAP_ELT_BITS; i += 8) - ret += popcount_table[(a >> i) & 0xff]; - return ret; -} -#endif diff --git a/gcc/sbitmap.h b/gcc/sbitmap.h index c9de88a335a..c2081710bd2 100644 --- a/gcc/sbitmap.h +++ b/gcc/sbitmap.h @@ -84,7 +84,6 @@ along with GCC; see the file COPYING3. If not see struct simple_bitmap_def { - unsigned char *popcount; /* Population count. */ unsigned int n_bits; /* Number of bits. */ unsigned int size; /* Size in elements. */ SBITMAP_ELT_TYPE elms[1]; /* The elements. */ @@ -110,7 +109,6 @@ bitmap_bit_p (const_sbitmap map, int bitno) static inline void bitmap_set_bit (sbitmap map, int bitno) { - gcc_checking_assert (! map->popcount); map->elms[bitno / SBITMAP_ELT_BITS] |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS; } @@ -120,7 +118,6 @@ bitmap_set_bit (sbitmap map, int bitno) static inline void bitmap_clear_bit (sbitmap map, int bitno) { - gcc_checking_assert (! map->popcount); map->elms[bitno / SBITMAP_ELT_BITS] &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS); } @@ -213,7 +210,6 @@ bmp_iter_next (sbitmap_iterator *i, unsigned *bit_no ATTRIBUTE_UNUSED) inline void sbitmap_free (sbitmap map) { - free (map->popcount); free (map); } @@ -231,7 +227,6 @@ extern void debug (const simple_bitmap_def *ptr); extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap *, int); extern sbitmap sbitmap_alloc (unsigned int); -extern sbitmap sbitmap_alloc_with_popcount (unsigned int); extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int); extern sbitmap sbitmap_resize (sbitmap, unsigned int, int); extern void bitmap_copy (sbitmap, const_sbitmap); @@ -261,5 +256,4 @@ extern int bitmap_last_set_bit (const_sbitmap); extern void debug_bitmap (const_sbitmap); extern sbitmap sbitmap_realloc (sbitmap, unsigned int); -extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long); #endif /* ! GCC_SBITMAP_H */ -- 2.11.4.GIT