X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fsbitmap.c;h=23d459ec30935300c0926c0593dfa8adf4ae4f10;hb=43c5cb7038177164b1675b51a587cb9c72b369d4;hp=acc40a1f87f35010d0e457c7e84bd95d224e8b13;hpb=ac0ff66f4b7881469a4a569679227e6f83c36630;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/sbitmap.c b/gcc/sbitmap.c index acc40a1f87f..23d459ec309 100644 --- a/gcc/sbitmap.c +++ b/gcc/sbitmap.c @@ -1,12 +1,12 @@ /* Simple bitmaps. - Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007 + Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007, 2008, 2010 Free Software Foundation, Inc. This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later +Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY @@ -15,33 +15,39 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" #include "coretypes.h" -#include "tm.h" -#include "rtl.h" -#include "flags.h" -#include "hard-reg-set.h" -#include "obstack.h" +#include "sbitmap.h" + +#ifdef IN_GCC +/* FIXME: sbitmap is just a data structure, but we define dataflow functions + here also. This is conditional on IN_GCC (see second #ifdef IN_GCC + further down). + For now, also only conditionally include basic-block.h, but we should + find a better place for the dataflow functions. Perhaps cfganal.c? */ #include "basic-block.h" +#endif #if GCC_VERSION >= 3400 -#if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG -#define do_popcount(x) __builtin_popcountl(x) -#elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG -#define do_popcount(x) __builtin_popcountll(x) -#else -#error "internal error: sbitmap.h and hwint.h are inconsistent" -#endif +# if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG +# define do_popcount(x) __builtin_popcountl(x) +# elif HOST_BITS_PER_WIDEST_FAST_INT == 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)) +# define do_popcount(x) sbitmap_elt_popcount((x)) #endif +typedef SBITMAP_ELT_TYPE *sbitmap_ptr; +typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr; + /* This macro controls debugging that is as expensive as the operations it verifies. */ @@ -56,7 +62,7 @@ sbitmap_verify_popcount (const_sbitmap a) { unsigned ix; unsigned int lastword; - + if (!a->popcount) return; @@ -80,7 +86,7 @@ sbitmap_alloc (unsigned int n_elms) bytes = size * sizeof (SBITMAP_ELT_TYPE); amt = (sizeof (struct simple_bitmap_def) + bytes - sizeof (SBITMAP_ELT_TYPE)); - bmap = xmalloc (amt); + bmap = (sbitmap) xmalloc (amt); bmap->n_bits = n_elms; bmap->size = size; bmap->popcount = NULL; @@ -92,8 +98,8 @@ sbitmap_alloc (unsigned int n_elms) sbitmap sbitmap_alloc_with_popcount (unsigned int n_elms) { - sbitmap const bmap = sbitmap_alloc (n_elms); - bmap->popcount = xmalloc (bmap->size * sizeof (unsigned char)); + sbitmap const bmap = sbitmap_alloc (n_elms); + bmap->popcount = XNEWVEC (unsigned char, bmap->size); return bmap; } @@ -113,17 +119,16 @@ sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) { amt = (sizeof (struct simple_bitmap_def) + bytes - sizeof (SBITMAP_ELT_TYPE)); - bmap = xrealloc (bmap, amt); + bmap = (sbitmap) xrealloc (bmap, amt); if (bmap->popcount) - bmap->popcount = xrealloc (bmap->popcount, - size * sizeof (unsigned char)); + bmap->popcount = XRESIZEVEC (unsigned char, bmap->popcount, size); } if (n_elms > bmap->n_bits) { if (def) { - memset (bmap->elms + bmap->size, -1, + memset (bmap->elms + bmap->size, -1, bytes - SBITMAP_SIZE_BYTES (bmap)); /* Set the new bits if the original last element. */ @@ -140,13 +145,13 @@ sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) } else { - memset (bmap->elms + bmap->size, 0, + memset (bmap->elms + bmap->size, 0, bytes - SBITMAP_SIZE_BYTES (bmap)); if (bmap->popcount) memset (bmap->popcount + bmap->size, 0, - (size * sizeof (unsigned char)) + (size * sizeof (unsigned char)) - (bmap->size * sizeof (unsigned char))); - + } } else if (n_elms < bmap->n_bits) @@ -219,7 +224,7 @@ sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms) } amt = vector_bytes + (n_vecs * elm_bytes); - bitmap_vector = xmalloc (amt); + bitmap_vector = (sbitmap *) xmalloc (amt); for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes) { @@ -249,7 +254,7 @@ sbitmap_copy (sbitmap dst, const_sbitmap src) void sbitmap_copy_n (sbitmap dst, const_sbitmap src, unsigned int n) { - memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n); + memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * n); if (dst->popcount) memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * n); } @@ -274,6 +279,57 @@ sbitmap_empty_p (const_sbitmap bmap) return true; } +/* Return false if any of the N bits are set in MAP starting at + START. */ + +bool +sbitmap_range_empty_p (const_sbitmap bmap, unsigned int start, unsigned int n) +{ + unsigned int i = start / SBITMAP_ELT_BITS; + SBITMAP_ELT_TYPE elm; + unsigned int shift = start % SBITMAP_ELT_BITS; + + gcc_assert (bmap->n_bits >= start + n); + + elm = bmap->elms[i]; + elm = elm >> shift; + + if (shift + n <= SBITMAP_ELT_BITS) + { + /* The bits are totally contained in a single element. */ + if (shift + n < SBITMAP_ELT_BITS) + elm &= ((1 << n) - 1); + return (elm == 0); + } + + if (elm) + return false; + + n -= SBITMAP_ELT_BITS - shift; + i++; + + /* Deal with full elts. */ + while (n >= SBITMAP_ELT_BITS) + { + if (bmap->elms[i]) + return false; + i++; + n -= SBITMAP_ELT_BITS; + } + + /* The leftover bits. */ + if (n) + { + elm = bmap->elms[i]; + elm &= ((1 << n) - 1); + return (elm == 0); + } + + return true; +} + + + /* Zero all elements in a bitmap. */ void @@ -301,7 +357,7 @@ sbitmap_ones (sbitmap bmap) bmap->elms[bmap->size - 1] = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); if (bmap->popcount) - bmap->popcount[bmap->size - 1] + bmap->popcount[bmap->size - 1] = do_popcount (bmap->elms[bmap->size - 1]); } } @@ -343,7 +399,7 @@ sbitmap_union_of_diff_cg (sbitmap dst, const_sbitmap a, const_sbitmap b, const_s SBITMAP_ELT_TYPE changed = 0; gcc_assert (!dst->popcount); - + for (i = 0; i < n; i++) { const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++); @@ -380,7 +436,7 @@ sbitmap_not (sbitmap dst, const_sbitmap src) const_sbitmap_ptr srcp = src->elms; unsigned int last_bit; - gcc_assert (!dst->popcount); + gcc_assert (!dst->popcount); for (i = 0; i < n; i++) *dstp++ = ~*srcp++; @@ -482,7 +538,7 @@ sbitmap_a_and_b (sbitmap dst, const_sbitmap a, const_sbitmap b) if (wordchanged) *popcountp = do_popcount (tmp); popcountp++; - } + } *dstp++ = tmp; } #ifdef BITMAP_DEBUGGING @@ -502,7 +558,7 @@ sbitmap_a_xor_b_cg (sbitmap dst, const_sbitmap a, const_sbitmap b) const_sbitmap_ptr ap = a->elms; const_sbitmap_ptr bp = b->elms; SBITMAP_ELT_TYPE changed = 0; - + gcc_assert (!dst->popcount); for (i = 0; i < n; i++) @@ -534,7 +590,7 @@ sbitmap_a_xor_b (sbitmap dst, const_sbitmap a, const_sbitmap b) if (wordchanged) *popcountp = do_popcount (tmp); popcountp++; - } + } *dstp++ = tmp; } #ifdef BITMAP_DEBUGGING @@ -586,7 +642,7 @@ sbitmap_a_or_b (sbitmap dst, const_sbitmap a, const_sbitmap b) if (wordchanged) *popcountp = do_popcount (tmp); popcountp++; - } + } *dstp++ = tmp; } #ifdef BITMAP_DEBUGGING @@ -689,6 +745,14 @@ sbitmap_a_and_b_or_c (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitm } #ifdef IN_GCC +/* FIXME: depends on basic-block.h, see comment at start of this file. + + Ironically, the comments before the functions below suggest they do + dataflow using the "new flow graph structures", but that's the *old* + new data structures. The functions receive basic block numbers and + use BASIC_BLOCK(idx) to get the basic block. They should receive + the basic block directly, *sigh*. */ + /* Set the bitmap DST to the intersection of SRC of successors of block number BB, using the new flow graph structures. */ @@ -707,7 +771,7 @@ sbitmap_intersection_of_succs (sbitmap dst, sbitmap *src, int bb) e = EDGE_SUCC (b, ix); if (e->dest == EXIT_BLOCK_PTR) continue; - + sbitmap_copy (dst, src[e->dest->index]); break; } @@ -947,7 +1011,7 @@ dump_sbitmap_file (FILE *file, const_sbitmap bmap) fprintf (file, "}\n"); } -void +DEBUG_FUNCTION void debug_sbitmap (const_sbitmap bmap) { dump_sbitmap_file (stderr, bmap); @@ -1012,7 +1076,7 @@ sbitmap_popcount (const_sbitmap a, unsigned long maxbit) if (maxbit == 0) return 0; - + if (maxbit >= a->n_bits) maxbit = a->n_bits;