/* Simple bitmaps.
- Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007
+ Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007, 2008
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
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
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "hard-reg-set.h"
#include "obstack.h"
#include "basic-block.h"
+#include "sbitmap.h"
#if GCC_VERSION >= 3400
#if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG
{
unsigned ix;
unsigned int lastword;
-
+
if (!a->popcount)
return;
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;
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;
}
{
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. */
}
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)
}
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)
{
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);
}
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
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]);
}
}
SBITMAP_ELT_TYPE changed = 0;
gcc_assert (!dst->popcount);
-
+
for (i = 0; i < n; i++)
{
const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++);
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++;
if (wordchanged)
*popcountp = do_popcount (tmp);
popcountp++;
- }
+ }
*dstp++ = tmp;
}
#ifdef BITMAP_DEBUGGING
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++)
if (wordchanged)
*popcountp = do_popcount (tmp);
popcountp++;
- }
+ }
*dstp++ = tmp;
}
#ifdef BITMAP_DEBUGGING
if (wordchanged)
*popcountp = do_popcount (tmp);
popcountp++;
- }
+ }
*dstp++ = tmp;
}
#ifdef BITMAP_DEBUGGING
e = EDGE_SUCC (b, ix);
if (e->dest == EXIT_BLOCK_PTR)
continue;
-
+
sbitmap_copy (dst, src[e->dest->index]);
break;
}
if (maxbit == 0)
return 0;
-
+
if (maxbit >= a->n_bits)
maxbit = a->n_bits;