This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH]: Updated new sparse bitmap patch


Here is the updated patch, with all the fixes for things mentioned in
this thread.

For the moment, it uses the pos += fprintf.  I have no aversion to
changing that if rth (or anyone else) wants it done :)


On 3/20/07, Daniel Berlin <dberlin@dberlin.org> wrote:
On 3/20/07, Seongbae Park <seongbae.park@gmail.com> wrote:
> On 3/20/07, Daniel Berlin <dberlin@dberlin.org> wrote:
> ...
> > Copied from sbitmap.c so it matched exactly the output style for sbitmaps.  :)
> > I've discovered that GCC  people are less likely to use new code if
> > the debugging dumps don't look like what they are used to.
> > Of course I personally have no aversion to changing it to whatever people want.
>
> Sounds like we should at least take Chris's suggestion
> and fix both your ebitmap.c and the existing sbitmap.c.
Sure.

>
> We can then spend the rest of our email bandwidth
> on an endless discussion of which output format is better :)
>
> More seriously,
> I wish we have a way to unittest the basic datastructure implementations
> without building the whole thing.
I agree.
The reason the header list is so small is because i built it
separately for a long time while working on it.

> Then we should be able to do away with the internal checking code in ebitmap.c
> as well as having much better testing...
I agree.

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 123086)
+++ ChangeLog	(working copy)
@@ -1,3 +1,9 @@
+2007-03-20  Daniel Berlin  <dberlin@dberlin.org>
+
+	* ebitmap.h: New file
+	* ebitmap.c: New file
+	* Makefile.in (ebitmap.o): New target.
+
 2007-03-20  Nathan Sidwell  <nathan@codesourcery.com>
 
 	* config/vxlib.c (tls_delete_hook): Use TCB for kernel tasks.
Index: ebitmap.c
===================================================================
--- ebitmap.c	(revision 0)
+++ ebitmap.c	(revision 0)
@@ -0,0 +1,1021 @@
+/* Sparse array-based bitmaps.
+   Copyright (C) 2007 Free Software Foundation, Inc.
+   Contributed by Daniel Berlin <dberlin@dberlin.org>
+
+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
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+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.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "flags.h"
+#include "obstack.h"
+#include "ebitmap.h"
+
+/* The ebitmap data structure is a sparse bitmap structure that works
+   by having two pieces:
+   1. An array of all non-zero words in the structures, organized as
+   an array of HOST_WIDE_INT's.
+   2. A non-sparse bitmap saying which bitmap words are present in the
+   array.
+
+   As a consequence of this representation, testing whether a bit
+   exists in the bitmap is faster than linked-list bitmaps.  For bits
+   in words that are all zero, the time to test is O(1).  For bits in
+   words that exist, it requires O(n/sizeof(word)) time to perform the
+   test (ignoring the one element cache).  It also has much better
+   locality than linked list bitmaps.
+
+   To test whether a bit exists, we do the following:
+   1. Test whether the word the bit would appear in exists in the
+   bitmap (O(1) check of the mask).  If not, fail.
+
+   2. Population count the mask up to the word containing the bit, to
+   find the place in the array the word would be (popcount is cached,
+   but this is just as slow as the linked list bitmap)
+   3. Test the word to see if the bit exists.
+
+   Just like linked list bitmaps, we cache the last element that has
+   been tested in order to speed up common access patterns.
+
+   Most of the other speedups are simply due to better locality of the
+   single contiguous array.
+
+   As would be expected in a structure like this, insertion into an
+   empty word in the middle requires moving bits to make room for the
+   new word.   As most operations that perform sets perform them in
+   order, this is rarely a problem.  We also take advantage of the
+   same element cache to make repeated sets to the same word O(1).
+
+   Operations on the entire bitmap are also more efficient than
+   bitmaps, as they are all operating on contiguous memory, and can be
+   easily vectorized.  They are all O(number of words) + O(number of
+   bits that may end up in the destination), as the appropriate
+   operation is first performed on the word mask, and then only those
+   elements that may generate results are touched.
+
+   Memory wise, the ebitmap starts out using less memory than the
+   linked list bitmap, but it's size in memory is technically bounded
+   by (size of the highest set bit) / (size of a word).  This is
+   because the mask is non-sparse.  The mask could be transformed into
+   a sparse bitmap at the cost of making bit testing *theoretically*
+   slower (real world numbers have not been computed yet as to whether
+   it matters or not).  */
+
+/* #define EBITMAP_DEBUGGING  */
+
+/* Find the last set bit in EBITMAP map.  */
+
+unsigned int
+ebitmap_last_set_bit (ebitmap map)
+{
+  unsigned int i = 0;
+  ebitmap_iterator ebi;
+
+  /* This is not the fastest way to do this, we could simply look for
+     the popcount, and start there, but this function is not used
+     anywhere speed critical.  */
+  EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi);
+
+  return i;
+}
+
+/* Grow or shrink the internal word array for MAP to NEWSIZE
+   elements.  */
+
+static inline void
+ebitmap_array_grow (ebitmap map, unsigned int newsize)
+{
+  if (newsize <= map->n_elts)
+    {
+      map->n_elts = newsize;
+      return;
+    }
+
+  newsize += newsize / 4;
+
+  map->n_elts = newsize;
+  map->elts = xrealloc (map->elts, sizeof (EBITMAP_ELT_TYPE) * newsize);
+}
+
+/* Grow the internal word array for MAP so it is at least SIZE
+   elements.  Will not shrink the array if it is already big
+   enough.  */
+
+static inline void
+ebitmap_array_maybe_grow (ebitmap map, unsigned int size)
+{
+  if (size >= map->n_elts)
+    ebitmap_array_grow (map, size + 1);
+}
+
+/* Retrieve the IDX'th element from the word array for MAP.  */
+
+static inline EBITMAP_ELT_TYPE
+ebitmap_array_get (ebitmap map, unsigned int idx)
+{
+  gcc_assert (idx < map->n_elts);
+  return map->elts[idx];
+}
+
+/* Retrieve a pointer to the IDX'th element from the word array for
+   MAP.  If the element index is greater than the size of the array,
+   the array will be grown to the correct size.  */
+
+static inline EBITMAP_ELT_TYPE *
+ebitmap_array_grow_get (ebitmap map, unsigned int idx)
+{
+  if (idx >= map->n_elts)
+    ebitmap_array_grow (map, idx + 1);
+  return &map->elts[idx];
+}
+
+/* Initialize the internal word array for MAP, so that it is SIZE
+   elements.  */
+
+static inline void
+ebitmap_array_init (ebitmap map, unsigned int size)
+{
+  if (size > 0)
+    {
+      map->elts = xmalloc (sizeof (EBITMAP_ELT_TYPE) * size);
+      map->n_elts = size;
+    }
+  else
+    {
+      map->n_elts = 0;
+      map->elts = NULL;
+    }
+}
+
+/* Free the internal word array for MAP.  */
+
+static inline void
+ebitmap_array_clear (ebitmap map)
+{
+  if (map->elts) 
+    {
+      free (map->elts);
+      map->elts = NULL;
+    }
+  map->n_elts = 0;
+}
+
+/* Clear ebitmap MAP.  */
+
+void
+ebitmap_clear (ebitmap map)
+{
+  ebitmap_array_clear (map);
+  sbitmap_zero (map->wordmask);
+  map->wordmask = sbitmap_resize (map->wordmask, 1, 0);
+  map->numwords = 0;
+  map->cache = NULL;
+  map->cacheindex = 0;
+}
+
+ebitmap
+ebitmap_alloc (unsigned int size)
+{
+  ebitmap ret = xmalloc (sizeof (struct ebitmap_def));
+  if (size == 0)
+    size = EBITMAP_ELT_BITS;
+  ebitmap_array_init (ret, size / EBITMAP_ELT_BITS);
+  ret->wordmask = sbitmap_alloc_with_popcount (size);
+  sbitmap_zero (ret->wordmask);
+  ret->numwords = 0;
+  ret->cache = NULL;
+  ret->cacheindex = 0;
+
+  return ret;
+}
+
+/* Clear BIT from ebitmap MAP.  */
+
+void
+ebitmap_clear_bit (ebitmap map, unsigned int bit)
+{
+  unsigned int wordindex = bit / EBITMAP_ELT_BITS;
+  unsigned int eltwordindex;
+  unsigned int bitindex, shift;
+
+  /* If the bit can't exist in our bitmap, just return.  */
+  if (map->numwords == 0)
+    return;
+
+  if (wordindex >= map->wordmask->n_bits
+      || !TEST_BIT (map->wordmask, wordindex))
+    return;
+
+  eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
+
+  bitindex = bit % EBITMAP_ELT_BITS;
+  shift = bitindex;
+
+  map->elts[eltwordindex] &= ~(((EBITMAP_ELT_TYPE)1) << shift);
+
+  /* Clear out the empty words.  */
+  if (map->elts[eltwordindex] == 0)
+    {
+      unsigned int ix;
+
+      if (map->cache != NULL && map->cacheindex == eltwordindex)
+	map->cache = NULL;
+
+      RESET_BIT (map->wordmask, wordindex);
+
+      for (ix = eltwordindex; ix < map->numwords-1; ix++)
+	map->elts[ix] = map->elts[ix + 1];
+      map->numwords--;
+    }
+}
+
+/* Set BIT in ebitmap MAP.  */
+
+void
+ebitmap_set_bit (ebitmap map, unsigned int bit)
+{
+  unsigned int wordindex = bit / EBITMAP_ELT_BITS;
+  unsigned int eltwordindex;
+  unsigned int bitindex;
+
+
+  /* If we have this element cached, just set the bit in it.  */
+  if (map->cache && map->cacheindex == wordindex)
+    {
+      (*map->cache) |= (EBITMAP_ELT_TYPE)1 << bitindex;
+      return;
+    }
+
+  /* Resize the wordmask if necessary.  */
+  if (wordindex >= map->wordmask->n_bits)
+    map->wordmask = sbitmap_resize (map->wordmask, wordindex + 1, 0);
+
+  /* Allocate a new word in the array and move whatever is in it's
+     place, if necessary. */
+  if (!TEST_BIT (map->wordmask, wordindex))
+    {
+      unsigned long count;
+      unsigned int i;
+
+      SET_BIT (map->wordmask, wordindex);
+      count = sbitmap_popcount (map->wordmask, wordindex);
+      gcc_assert (count <= map->numwords);
+
+      for (i = map->numwords; i > count; i--)
+	{
+	  EBITMAP_ELT_TYPE *newelt;
+	  newelt = ebitmap_array_grow_get (map, i);
+	  *newelt = ebitmap_array_get (map, i - 1);
+	}
+      map->numwords++;
+      eltwordindex = count;
+      ebitmap_array_maybe_grow (map, eltwordindex);
+      map->elts[eltwordindex] = 0;
+    }
+  else
+    {
+      eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
+    }
+
+  /* Set the actual bit.  */
+  bitindex = bit % EBITMAP_ELT_BITS;
+
+  map->elts[eltwordindex] |= (EBITMAP_ELT_TYPE)1 << bitindex;
+  map->cache = &map->elts[eltwordindex];
+  map->cacheindex = wordindex;
+}
+
+
+/* Return true if MAP contains BIT.  */
+
+bool
+ebitmap_bit_p (ebitmap map, unsigned int bit)
+{
+  unsigned int wordindex = bit / EBITMAP_ELT_BITS;
+  unsigned int bitindex= bit % EBITMAP_ELT_BITS;
+
+  /* Trivial empty ebitmap case.  */
+  if (map->numwords == 0)
+    return false;
+
+  if (map->cache && map->cacheindex == wordindex)
+    return ((*map->cache) >> bitindex) & 1;
+
+  /* If the wordindex is greater than the size of the wordmask, *or*
+     it's not set in the wordmask, this bit can't exist in our
+     ebitmap.  */
+  if (wordindex >= map->wordmask->n_bits
+      || !TEST_BIT (map->wordmask, wordindex))
+    return false;
+
+  /* Find the bit and test it.  */
+  map->cacheindex = wordindex;
+  wordindex = sbitmap_popcount (map->wordmask, wordindex);
+  map->cache = &map->elts[wordindex];
+
+  return (map->elts[wordindex] >> bitindex) & 1;
+}
+
+/* Copy ebitmap SRC to DST.  */
+
+void
+ebitmap_copy (ebitmap dst, ebitmap src)
+{
+  /* Blow away any existing wordmask, and copy the new one.  */
+  sbitmap_free (dst->wordmask);
+  dst->wordmask = sbitmap_alloc_with_popcount (src->wordmask->n_bits);
+  sbitmap_copy (dst->wordmask, src->wordmask);
+
+  /* Make sure our destination array is big enough, and then copy the
+     actual words.  */
+  ebitmap_array_grow (dst, src->numwords);
+  memcpy (dst->elts, src->elts,
+	  src->numwords * sizeof (EBITMAP_ELT_TYPE));
+  dst->numwords = src->numwords;
+  dst->cache = NULL;
+}
+
+/* Dump ebitmap BMAP to FILE.  */
+
+void
+dump_ebitmap (FILE *file, ebitmap bmap)
+{
+  unsigned int pos;
+  unsigned int i;
+  int res;
+  unsigned int size;
+
+  res = sbitmap_last_set_bit (bmap->wordmask);
+  if (res == -1)
+    size = 0;
+  else
+    size = (res + 1) * EBITMAP_ELT_BITS;
+
+  fprintf (file, "n_words = %d, set = {", bmap->numwords);
+
+  for (pos = 30, i = 0; i < size; i++)
+    if (ebitmap_bit_p (bmap, i))
+      {
+	if (pos > 70)
+	  {
+	    fprintf (file, "\n  ");
+	    pos = 0;
+	  }
+
+	pos += fprintf (file, "%d ", i);
+      }
+
+  fprintf (file, "}\n");
+}
+
+/* Dump ebitmap BMAP to stderr.  */
+
+void
+debug_ebitmap (ebitmap bmap)
+{
+  dump_ebitmap (stderr, bmap);
+}
+
+/* Perform the operation DST &= SRC.  */
+
+void
+ebitmap_and_into (ebitmap dst, ebitmap src)
+{
+  sbitmap_iterator sbi;
+  unsigned int i;
+  unsigned int neweltindex = 0;
+  unsigned int dsteltindex = 0;
+  unsigned int srceltindex = 0;
+
+  gcc_assert (dst != src);
+
+  dst->cache = NULL;
+
+  /* Short circuit the empty bitmap cases.  */
+  if (src->numwords == 0 || dst->numwords == 0)
+    {
+      ebitmap_clear (dst);
+      return;
+    }
+
+  /* AND the masks, then walk the words that may actually appear in
+     the result, AND'ing them.  */
+  sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask);
+
+  EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
+    {
+      bool srchasword;
+
+      /* If it really made a speed difference, we could iterate both
+	 masks in parallel so the src testing didn't look like random
+	 bittests.  */
+      srchasword = TEST_BIT (src->wordmask, i);
+
+      if (srchasword)
+	{
+	  EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
+	  tmpword &= ebitmap_array_get (dst, dsteltindex++);
+	  if (tmpword != 0)
+	    {
+	      EBITMAP_ELT_TYPE *dstplace;
+	      dstplace = ebitmap_array_grow_get (dst, neweltindex++);
+	      *dstplace = tmpword;
+	    }
+	  else
+	    RESET_BIT (dst->wordmask, i);
+	}
+      else
+	{
+	  dsteltindex++;
+	  RESET_BIT (dst->wordmask, i);
+	}
+    }
+#ifdef EBITMAP_DEBUGGING
+  {
+    unsigned int i;
+
+    for (i = 0; i <  dst->numwords; i++)
+      gcc_assert (dst->elts[i] != 0);
+
+    verify_popcount (dst->wordmask);
+    gcc_assert (sbitmap_popcount (dst->wordmask,
+				  dst->wordmask->n_bits) == dst->numwords);
+    gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);
+  }
+#endif
+  dst->numwords = neweltindex;
+}
+
+/* Perform the operation DST = SRC1 & SRC2.  */
+
+void
+ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2)
+{
+  sbitmap_iterator sbi;
+  unsigned int i;
+  unsigned int neweltindex = 0;
+  unsigned int src1eltindex = 0;
+  unsigned int src2eltindex = 0;
+
+  dst->cache = NULL;
+  if (src1->numwords == 0 || src2->numwords == 0)
+    {
+      ebitmap_clear (dst);
+      return;
+    }
+
+  dst->wordmask
+    = sbitmap_resize (dst->wordmask,
+		      MAX (src1->wordmask->n_bits, src2->wordmask->n_bits),
+		      0);
+  sbitmap_a_and_b (dst->wordmask, src1->wordmask, src2->wordmask);
+
+  EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
+    {
+      bool src1hasword, src2hasword;
+
+      src1hasword = TEST_BIT (src1->wordmask, i);
+      src2hasword = TEST_BIT (src2->wordmask, i);
+
+      if (src1hasword && src2hasword)
+	{
+	  EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src1, src1eltindex++);
+	  tmpword &= ebitmap_array_get (src2, src2eltindex++);
+	  if (tmpword != 0)
+	    {
+	      EBITMAP_ELT_TYPE *dstplace;
+	      dstplace = ebitmap_array_grow_get (dst, neweltindex++);
+	      *dstplace = tmpword;
+	    }
+	  else
+	    RESET_BIT (dst->wordmask, i);
+	}
+      else if (src1hasword)
+	src1eltindex++;
+      else
+	src2eltindex++;
+    }
+#ifdef EBITMAP_DEBUGGING
+  {
+    ebitmap_iterator ebi;
+    unsigned int i;
+
+    for (i = 0; i <  dst->numwords; i++)
+      gcc_assert (dst->elts[i] != 0);
+
+    EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
+      if (ebitmap_bit_p (src2, i))
+	gcc_assert (ebitmap_bit_p (dst, i));
+
+    for (i = 0; i <  dst->numwords; i++)
+      gcc_assert (dst->elts[i] != 0);
+
+    verify_popcount (dst->wordmask);
+    gcc_assert (sbitmap_popcount (dst->wordmask,
+				  dst->wordmask->n_bits) == dst->numwords);
+    gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);
+  }
+#endif
+  dst->numwords = neweltindex;
+}
+
+/* Perform the operation DST |= SRC.  */
+
+bool
+ebitmap_ior_into (ebitmap dst, ebitmap src)
+{
+  unsigned int dstsize = dst->wordmask->n_bits;
+  unsigned int srcsize = src->wordmask->n_bits;
+  sbitmap_iterator sbi;
+  unsigned int i;
+  sbitmap tempmask;
+  unsigned int neweltindex = 0;
+  unsigned int dsteltindex = 0;
+  unsigned int srceltindex = 0;
+  bool changed = false;
+  EBITMAP_ELT_TYPE *newarray;
+  unsigned int newarraysize;
+#ifdef EBITMAP_DEBUGGING
+  ebitmap dstcopy = ebitmap_alloc (1);
+  ebitmap_copy (dstcopy, dst);
+#endif
+
+  dst->cache = NULL;
+  if (dst == src)
+    return false;
+
+  if (dst->numwords == 0 && src->numwords != 0)
+    {
+      ebitmap_copy (dst, src);
+      return true;
+    }
+  else if (src->numwords == 0)
+    return false;
+
+  /* We can do without the temp mask if it's faster, but it would mean
+     touching more words in the actual dense vector.  */
+  tempmask = sbitmap_alloc (MAX (srcsize, dstsize));
+  sbitmap_zero (tempmask);
+  if (srcsize == dstsize)
+    {
+      sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask);
+    }
+  else
+    {
+      dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize),
+				      0);
+      if (MAX (srcsize, dstsize) == srcsize)
+	{
+	  sbitmap_copy_n (tempmask, dst->wordmask, dst->wordmask->size);
+	  sbitmap_a_or_b (tempmask, tempmask, src->wordmask);
+	}
+      else
+	{
+	  sbitmap_copy_n (tempmask, src->wordmask, src->wordmask->size);
+	  sbitmap_a_or_b (tempmask, tempmask, dst->wordmask);
+	}
+    }
+  newarraysize = src->numwords + dst->numwords;
+  newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
+
+  EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
+    {
+      bool dsthasword, srchasword;
+
+      dsthasword = (i < dst->wordmask->n_bits
+		    && TEST_BIT (dst->wordmask, i));
+      srchasword = (i < src->wordmask->n_bits
+		    && TEST_BIT (src->wordmask, i));
+
+      if (dsthasword && srchasword)
+	{
+	  EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
+	  tmpword |= ebitmap_array_get (dst, dsteltindex);
+	  if (!changed)
+	    changed |= tmpword != ebitmap_array_get (dst, dsteltindex);
+	  dsteltindex++;
+	  newarray[neweltindex++] = tmpword;
+	}
+      else if (dsthasword)
+	{
+	  newarray [neweltindex++] = ebitmap_array_get (dst, dsteltindex++);
+	}
+      else
+	{
+	  newarray [neweltindex++] = ebitmap_array_get (src, srceltindex++);
+	  gcc_assert (i < dst->wordmask->n_bits);
+	  SET_BIT (dst->wordmask, i);
+	  changed |= true;
+	}
+    }
+
+  sbitmap_free (tempmask);
+  if (changed)
+    {
+      dst->numwords = neweltindex;
+      free (dst->elts);
+      dst->elts = newarray;
+      dst->n_elts = newarraysize;
+    }
+  else
+    free (newarray);
+
+#ifdef EBITMAP_DEBUGGING
+  {
+    ebitmap_iterator ebi;
+    unsigned int i;
+
+    for (i = 0; i <  dst->numwords; i++)
+      gcc_assert (dst->elts[i] != 0);
+
+    EXECUTE_IF_SET_IN_EBITMAP (src, 0, i, ebi)
+      gcc_assert (ebitmap_bit_p (dst, i));
+    EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
+      gcc_assert (ebitmap_bit_p (dst, i));
+
+    verify_popcount (dst->wordmask);
+    gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
+    gcc_assert (sbitmap_popcount (dst->wordmask,
+				  dst->wordmask->n_bits) == dst->numwords);
+    gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);
+  }
+#endif
+  return changed;
+}
+
+/* Perform the operation DST = SRC1 | SRC2.  */
+
+bool
+ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2)
+{
+  unsigned int src1size = src1->wordmask->n_bits;
+  unsigned int src2size = src2->wordmask->n_bits;
+  sbitmap_iterator sbi;
+  unsigned int i;
+  sbitmap tempmask;
+  unsigned int neweltindex = 0;
+  unsigned int src1eltindex = 0;
+  unsigned int src2eltindex = 0;
+  bool changed = false;
+  EBITMAP_ELT_TYPE *newarray;
+  unsigned int newarraysize;
+#ifdef EBITMAP_DEBUGGING
+  ebitmap dstcopy = ebitmap_alloc (1);
+  ebitmap_copy (dstcopy, dst);
+#endif
+
+  dst->cache = NULL;
+  tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size));
+  sbitmap_zero (tempmask);
+  if (src1size == src2size)
+    {
+      sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask);
+    }
+  else
+    {
+      if (MAX (src1size, src2size) == src1size)
+	{
+	  sbitmap_copy_n (tempmask, src2->wordmask, src2->wordmask->size);
+	  sbitmap_a_or_b (tempmask, tempmask, src1->wordmask);
+	}
+      else
+	{
+	  sbitmap_copy_n (tempmask, src1->wordmask, src1->wordmask->size);
+	  sbitmap_a_or_b (tempmask, tempmask, src2->wordmask);
+	}
+    }
+  newarraysize = src1->numwords + src2->numwords;
+  newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
+
+  EXECUTE_IF_SET_IN_SBITMAP (tempmask, 0, i, sbi)
+    {
+      bool src1hasword, src2hasword;
+      EBITMAP_ELT_TYPE tmpword;
+      src1hasword = (i < src1->wordmask->n_bits
+		    && TEST_BIT (src1->wordmask, i));
+      src2hasword = (i < src2->wordmask->n_bits
+		    && TEST_BIT (src2->wordmask, i));
+
+      if (src1hasword && src2hasword)
+	{
+	  tmpword = ebitmap_array_get (src1, src1eltindex++)
+	    | ebitmap_array_get (src2, src2eltindex++);
+	  newarray[neweltindex++] = tmpword;
+	}
+      else if (src1hasword)
+	{
+	  tmpword = ebitmap_array_get (src1, src1eltindex++);
+	  newarray [neweltindex++] = tmpword;
+	}
+      else
+	{
+	  tmpword = ebitmap_array_get (src2, src2eltindex++);
+	  newarray [neweltindex++] = tmpword;
+	}
+
+      if (i >= dst->wordmask->n_bits ||!TEST_BIT (dst->wordmask, i))
+	{
+	  changed = true;
+	}
+      else if (!changed)
+	{
+	  unsigned int count = sbitmap_popcount (dst->wordmask, i);
+	  changed |= ebitmap_array_get (dst, count) != tmpword;
+	}
+    }
+
+  if (changed)
+    {
+      sbitmap_free (dst->wordmask);
+      dst->wordmask = tempmask;
+      dst->numwords = neweltindex;
+      free (dst->elts);
+      dst->elts = newarray;
+      dst->n_elts = newarraysize;
+    }
+  else
+    {
+      sbitmap_free (tempmask);
+      free (newarray);
+    }
+
+#ifdef EBITMAP_DEBUGGING
+  {
+    ebitmap_iterator ebi;
+    unsigned int i;
+
+    for (i = 0; i <  dst->numwords; i++)
+      gcc_assert (dst->elts[i] != 0);
+
+    EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
+      gcc_assert (ebitmap_bit_p (dst, i));
+
+    EXECUTE_IF_SET_IN_EBITMAP (src2, 0, i, ebi)
+      gcc_assert (ebitmap_bit_p (dst, i));
+  }
+  verify_popcount (dst->wordmask);
+  gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
+  gcc_assert (sbitmap_popcount (dst->wordmask,
+				dst->wordmask->n_bits) == dst->numwords);
+  gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);
+#endif
+
+  return changed;
+}
+
+/* Perform the operation DST &= ~SRC.  */
+
+bool
+ebitmap_and_compl_into (ebitmap dst, ebitmap src)
+{
+  bool changed = false;
+  unsigned int i;
+  unsigned int neweltindex = 0;
+  unsigned int dsteltindex = 0;
+  sbitmap_iterator sbi;
+#ifdef EBITMAP_DEBUGGING
+  ebitmap dstcopy = ebitmap_alloc (1);
+  ebitmap_copy (dstcopy, dst);
+#endif
+
+  gcc_assert (dst != src);
+  dst->cache = NULL;
+  if (src->numwords == 0)
+    return false;
+
+  EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
+    {
+      bool srchasword;
+
+      srchasword = (i < src->wordmask->n_bits
+		    && TEST_BIT (src->wordmask, i));
+
+      if (srchasword)
+	{
+	  unsigned int srccount = sbitmap_popcount (src->wordmask, i);
+	  EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (dst, dsteltindex);
+	  tmpword &= ~(ebitmap_array_get (src, srccount));
+	  if (!changed)
+	    changed |= ebitmap_array_get (dst, dsteltindex) != tmpword;
+	  dsteltindex++;
+	  if (tmpword != 0)
+	    {
+	      EBITMAP_ELT_TYPE *dstplace;
+	      dstplace = ebitmap_array_grow_get (dst, neweltindex++);
+	      *dstplace = tmpword;
+	    }
+	  else
+	    RESET_BIT (dst->wordmask, i);
+	}
+      else
+	{
+	  dsteltindex++;
+	  neweltindex++;
+	}
+    }
+#ifdef EBITMAP_DEBUGGING
+  {
+    unsigned int i;
+    ebitmap_iterator ebi;
+
+    EXECUTE_IF_SET_IN_EBITMAP (dstcopy, 0, i, ebi)
+      {
+	if (!ebitmap_bit_p (src, i))
+	  gcc_assert (ebitmap_bit_p (dst, i));
+      }
+
+    for (i = 0; i <  dst->numwords; i++)
+      gcc_assert (dst->elts[i] != 0);
+
+    gcc_assert (sbitmap_popcount (dst->wordmask,
+				  dst->wordmask->n_bits) == neweltindex);
+    verify_popcount (dst->wordmask);
+    gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
+    gcc_assert (sbitmap_popcount (dst->wordmask,
+				  dst->wordmask->n_bits) == dst->numwords);
+    gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);
+  }
+#endif
+  dst->numwords = neweltindex;
+  /* sbitmap_popcount (dst->wordmask, -1); */
+
+  return changed;
+}
+
+/* Perform the operation DST = SRC1 & ~SRC2.  */
+
+bool
+ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2)
+{
+  unsigned int src1size = src1->wordmask->n_bits;
+  sbitmap_iterator sbi;
+  unsigned int i;
+  sbitmap tempmask;
+  unsigned int neweltindex = 0;
+  unsigned int src1eltindex = 0;
+  bool changed = false;
+  EBITMAP_ELT_TYPE *newarray;
+  unsigned int newarraysize;
+
+  /* XXX: Optimize like the into version.  */
+  dst->cache = NULL;
+  tempmask = sbitmap_alloc_with_popcount (src1size);
+  sbitmap_zero (tempmask);
+  sbitmap_copy (tempmask, src1->wordmask);
+
+  newarraysize = src1->numwords;
+  newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
+
+  EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi)
+    {
+      bool src2hasword;
+      EBITMAP_ELT_TYPE tmpword;
+
+      src2hasword = (i < src2->wordmask->n_bits
+		    && TEST_BIT (src2->wordmask, i));
+
+      if (src2hasword)
+	{
+	  unsigned int src2count = sbitmap_popcount (src2->wordmask, i);
+	  tmpword = ebitmap_array_get (src1, src1eltindex++)
+	    & ~(ebitmap_array_get (src2, src2count));
+	  if (tmpword)
+	    {
+	      newarray[neweltindex++] = tmpword;
+	    }
+	  else
+	    RESET_BIT (tempmask, i);
+
+	}
+      else
+	{
+	  tmpword = ebitmap_array_get (src1, src1eltindex++);
+	  gcc_assert (tmpword != 0);
+	  newarray[neweltindex++] = tmpword;
+	}
+
+      if (i >= dst->wordmask->n_bits || !TEST_BIT (dst->wordmask, i))
+	{
+	  changed = true;
+	}
+      else if (!changed)
+	{
+	  unsigned int count = sbitmap_popcount (dst->wordmask, i);
+	  changed |= ebitmap_array_get (dst, count) != tmpword;
+	}
+    }
+  if (changed)
+    {
+      sbitmap_free (dst->wordmask);
+      dst->wordmask = tempmask;
+      dst->numwords = neweltindex;
+      free (dst->elts);
+      dst->elts = newarray;
+      dst->n_elts = newarraysize;
+    }
+  else
+    {
+      free (tempmask);
+      free (newarray);
+    }
+#ifdef EBITMAP_DEBUGGING
+  {
+    unsigned int i;
+    ebitmap_iterator ebi;
+
+    EXECUTE_IF_SET_IN_EBITMAP (src1, 0, i, ebi)
+      {
+	if (!ebitmap_bit_p (src2, i))
+	  gcc_assert (ebitmap_bit_p (dst, i));
+      }
+  for (i = 0; i <  dst->numwords; i++)
+    gcc_assert (dst->elts[i] != 0);
+
+  verify_popcount (dst->wordmask);
+  gcc_assert (sbitmap_popcount (dst->wordmask,
+				dst->wordmask->n_bits) == dst->numwords);
+  gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);
+  }
+#endif
+  return changed;
+}
+
+/* Perform the operation DST = A | (B & ~C).  */
+
+bool
+ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c)
+{
+  bool changed;
+  ebitmap temp = ebitmap_alloc (1);
+#ifdef EBITMAP_DEBUGGING
+  ebitmap dstcopy = ebitmap_alloc (1);
+  ebitmap_copy (dstcopy, dst);
+#endif
+
+  dst->cache = NULL;
+  ebitmap_and_compl (temp, b, c);
+  changed = ebitmap_ior (dst, a, temp);
+#ifdef EBITMAP_DEBUGGING
+  {
+    ebitmap_iterator ebi;
+    unsigned int i;
+
+    EXECUTE_IF_SET_IN_EBITMAP (a, 0, i, ebi)
+      gcc_assert (ebitmap_bit_p (dst, i));
+
+    EXECUTE_IF_SET_IN_EBITMAP (b, 0, i, ebi)
+      if (!ebitmap_bit_p (c, i))
+	gcc_assert (ebitmap_bit_p (dst, i));
+    gcc_assert (changed == !ebitmap_equal_p (dst, dstcopy));
+  }
+#endif
+  ebitmap_free (temp);
+
+  return changed;
+}
+
+/* Return true if ebitmap DST is equal to ebitmap SRC.  */
+
+bool
+ebitmap_equal_p (ebitmap dst, ebitmap src)
+{
+  unsigned int i;
+  unsigned int which = MIN (dst->wordmask->size, src->wordmask->size);
+
+  if (dst->numwords != src->numwords)
+    return false;
+
+  /* sbitmap_equal compares up to the size of the first argument, so
+     if the two sbitmaps are not equally sized, we need to pass the
+     smaller one as the first argument, or it will crash.  */
+  if (which == dst->wordmask->size
+      && !sbitmap_equal (dst->wordmask, src->wordmask))
+    return false;
+  else if (which == src->wordmask->size
+	   && !sbitmap_equal (src->wordmask, dst->wordmask))
+    return false;
+
+  for (i = 0; i < dst->numwords; i++)
+    {
+      if (dst->elts[i] != src->elts[i])
+	return false;
+    }
+  return true;
+}
Index: ebitmap.h
===================================================================
--- ebitmap.h	(revision 0)
+++ ebitmap.h	(revision 0)
@@ -0,0 +1,162 @@
+/* Sparse array based bitmaps.
+   Copyright (C) 2007 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
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+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.  */
+
+#ifndef GCC_EBITMAP_H
+#define GCC_EBITMAP_H
+#include "sbitmap.h"
+
+#define EBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
+#define EBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
+
+typedef struct ebitmap_def
+{  
+  EBITMAP_ELT_TYPE *elts;	/* non-zero element array.  */
+  unsigned int n_elts;		/* number of elements in the array.  */
+  sbitmap wordmask;		/* wordmask saying which words are
+				   non-zero.  */
+  unsigned int numwords;	/* number of non-zero words.  */
+  EBITMAP_ELT_TYPE *cache;	/* last tested element, or NULL.  */
+  unsigned int cacheindex;	/* which word cache is.  */
+} *ebitmap;
+
+
+#define ebitmap_empty_p(MAP) ((MAP)->numwords == 0)
+#define ebitmap_free(MAP)  (free((MAP)->elts), sbitmap_free ((MAP)->wordmask), free((MAP)))
+
+extern void ebitmap_set_bit (ebitmap, unsigned int);
+extern void ebitmap_clear_bit (ebitmap, unsigned int);
+extern bool ebitmap_bit_p (ebitmap, unsigned int);
+extern void dump_ebitmap (FILE *, ebitmap);
+extern void dump_ebitmap_file (FILE *, ebitmap);
+extern void dump_ebitmap_vector (FILE *, const char *, const char *, ebitmap *,
+				 int);
+extern ebitmap ebitmap_alloc (unsigned int);
+extern ebitmap *ebitmap_vector_alloc (unsigned int, unsigned int);
+extern void ebitmap_copy (ebitmap, ebitmap);
+extern void ebitmap_and (ebitmap, ebitmap, ebitmap);
+extern void ebitmap_and_into (ebitmap, ebitmap);
+extern bool ebitmap_and_compl (ebitmap, ebitmap, ebitmap);
+extern bool ebitmap_and_compl_into (ebitmap, ebitmap);
+extern bool ebitmap_ior_into (ebitmap, ebitmap);
+extern bool ebitmap_ior (ebitmap, ebitmap, ebitmap);
+extern bool ebitmap_ior_and_compl (ebitmap, ebitmap, ebitmap, ebitmap);
+extern bool ebitmap_ior_and_compl_into (ebitmap, ebitmap, ebitmap);
+extern bool ebitmap_equal_p (ebitmap, ebitmap);
+extern void ebitmap_clear (ebitmap);
+extern unsigned int ebitmap_last_set_bit (ebitmap);
+extern void debug_ebitmap (ebitmap);
+extern void dump_ebitmap (FILE *, ebitmap);
+extern unsigned long ebitmap_popcount(ebitmap, unsigned long);
+
+/* The iterator for ebitmap.  */
+typedef struct {
+  /* The pointer to the first word of the bitmap.  */
+  EBITMAP_ELT_TYPE *ptr;
+
+  /* Element number inside ptr that we are at.  */
+  unsigned int eltnum;
+
+  /* The size of the bitmap.  */
+  unsigned int size;
+
+  /* Current bit index.  */
+  unsigned int bit_num;
+
+  /* The words currently visited.  */
+  EBITMAP_ELT_TYPE word;
+
+  /* The word mask iterator.  */
+  sbitmap_iterator maskiter;
+} ebitmap_iterator;
+  
+static inline void
+ebitmap_iter_init (ebitmap_iterator *i, ebitmap bmp, unsigned int min)
+{
+  sbitmap_iter_init (&i->maskiter, bmp->wordmask, 
+		     min / EBITMAP_ELT_BITS);
+  i->size = bmp->numwords;
+  if (i->size == 0)
+    return;
+  i->ptr = bmp->elts;
+  i->bit_num = min;
+  i->eltnum = 0;
+
+  if ((min / EBITMAP_ELT_BITS) >= bmp->wordmask->n_bits)
+    {
+      i->word = 0;
+    }
+  else
+    {
+      if (TEST_BIT (bmp->wordmask, min / EBITMAP_ELT_BITS) == 0)
+	i->word = 0;
+      else
+	{
+	  unsigned int wordindex = min / EBITMAP_ELT_BITS;
+	  unsigned int count = sbitmap_popcount (bmp->wordmask, wordindex);
+	  i->word = i->ptr[count] >> (i->bit_num % (unsigned int)EBITMAP_ELT_BITS);
+	  i->eltnum = count + 1;
+	}
+    }
+}
+
+static inline bool
+ebitmap_iter_cond (ebitmap_iterator *i, unsigned int *n)
+{
+  unsigned int ourn;
+
+  if (i->size == 0)
+    return false;
+
+  if (i->word == 0)
+    {
+      sbitmap_iter_next (&i->maskiter);
+      if (!sbitmap_iter_cond (&i->maskiter, &ourn))
+	return false;
+      i->bit_num = ourn * EBITMAP_ELT_BITS;
+      i->word = i->ptr[i->eltnum++];
+    }
+
+  /* Skip bits that are zero.  */
+
+  for (; (i->word & 1) == 0; i->word >>= 1)
+    i->bit_num++;
+
+  *n = i->bit_num;
+  return true;
+}
+
+static inline void
+ebitmap_iter_next (ebitmap_iterator *i)
+{
+  i->word >>= 1;
+  i->bit_num ++;
+}
+
+/* Loop over all elements of EBITMAP, starting with MIN.  In each
+   iteration, N is set to the index of the bit being visited.  ITER is
+   an instance of ebitmap_iterator used to iterate the bitmap.  */
+
+#define EXECUTE_IF_SET_IN_EBITMAP(EBITMAP, MIN, N, ITER)	\
+  for (ebitmap_iter_init (&(ITER), (EBITMAP), (MIN));		\
+       ebitmap_iter_cond (&(ITER), &(N));			\
+       ebitmap_iter_next (&(ITER)))
+
+
+#endif /* ! GCC_EBITMAP_H */
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 123086)
+++ Makefile.in	(working copy)
@@ -1152,7 +1152,8 @@ OBJS-common = \
 	version.o \
 	vmsdbgout.o \
 	web.o \
-	xcoffout.o
+	xcoffout.o \
+	ebitmap.o
 
 # Target object files.
 OBJS-md = $(out_object_file)
@@ -1745,6 +1746,8 @@ graph.o: graph.c $(SYSTEM_H) coretypes.h
     $(RTL_H) $(FUNCTION_H) hard-reg-set.h $(BASIC_BLOCK_H) graph.h $(OBSTACK_H)
 sbitmap.o: sbitmap.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
     $(FLAGS_H) hard-reg-set.h $(BASIC_BLOCK_H) $(OBSTACK_H)
+ebitmap.o: ebitmap.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
+    $(FLAGS_H) $(OBSTACK_H) ebitmap.h sbitmap.h
 
 COLLECT2_OBJS = collect2.o tlink.o intl.o version.o
 COLLECT2_LIBS = @COLLECT2_LIBS@

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]