/* 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.
#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. */
{
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
}
#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. */
e = EDGE_SUCC (b, ix);
if (e->dest == EXIT_BLOCK_PTR)
continue;
-
+
sbitmap_copy (dst, src[e->dest->index]);
break;
}
fprintf (file, "}\n");
}
-void
+DEBUG_FUNCTION void
debug_sbitmap (const_sbitmap bmap)
{
dump_sbitmap_file (stderr, bmap);
if (maxbit == 0)
return 0;
-
+
if (maxbit >= a->n_bits)
maxbit = a->n_bits;