[RFC]: More efficient bitmap

[Daniel Berlin <dan at cgsoftware dot com>]

I smacked myself when I realized we could easily just use an expanding array and sbitmap
elements (and thus, not need any traversals to find where a bit goes),
taking some number of lower bits of the bit index as our index into
the array, having the element size of each sbitmap in the array be 1
<< the same number of bits.

Should be just about as fast than sbitmaps (except for the call
overhead), and use a lot less memory, as long as you don't reset tons of bits that
cause elements to clear (without ever calling compress at some point
afterward).

Replacing the bitmaps in df.[ch] with ebitmaps, makes it a lot faster,
and we use roughly the same memory, as long as you ebitmap_compress
(bb_info->r[du]_gen) at the end of df_bb_r[du]_local_compute.

As a plus, we also don't have to deal with a fixed size.
Comments, or any bugs anyone notices, before i submit this for
approval?

Parts need reformatting, obviously, i plan on just running indent on
it before submitting.
I also plan to try to common a bit more code into 5 line procedures,
rather than paste them everywhere.
7 or 8 is probably a more reasonable shift number (giving us 128 or
256 bits per element).

I haven't included the obvious varray changes here, since it's not a
patch being submitted for approval.

/* An efficient sbitmap based bitset implementation 
   Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   Contributed by Daniel Berlin <dan@cgsoftware.com>
This file is part of GNU CC.

GNU CC 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.

GNU CC 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 GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

#include "config.h"
#include "system.h"
#include "rtl.h"
#include "flags.h"
#include "obstack.h"
#include "sbitmap.h"
#include "ebitmap.h"
#define SBITMAP_OR_NULL(EBITMAP, I) I >= VARRAY_SIZE (EBITMAP->array) ? 0 : VARRAY_SBITMAP (EBITMAP->array, i)
static inline int ebitmap_free_if_exist PARAMS ((ebitmap, unsigned int));

static inline int
ebitmap_free_if_exist (bitmap, i)
	ebitmap bitmap;
	unsigned int i;
{
  if (VARRAY_SBITMAP (bitmap->array, i))
    {
      sbitmap_free (VARRAY_SBITMAP (bitmap->array, i));
      VARRAY_SBITMAP (bitmap->array, i) = 0;
      return 1;
    }
  return 0;
}
/* return first == second */
int
ebitmap_equal (first, second)
     ebitmap first;
     ebitmap second;
{
  unsigned int i;
  for (i = 0; i < MAX (VARRAY_SIZE (first->array), VARRAY_SIZE (second->array)); i++)
    {
      sbitmap one,two;
      one = SBITMAP_OR_NULL (first, i);
      two = SBITMAP_OR_NULL (second, i);
      if (!two && !one)
	continue;
      if (!two)
	return 0;
      if (!one)
	return 0;
      if (!sbitmap_equal (one, two))
	return 0;
    }
  return 1;
}
/* Clear BITMAP */
void
ebitmap_clear (bitmap)
     ebitmap bitmap;
{
  unsigned int i;
  for (i = 0; i < VARRAY_SIZE (bitmap->array); i++)
    ebitmap_free_if_exist (bitmap, i);

}

/* Copy the ebitmap at FROM into the ebitmap at TO */
void
ebitmap_copy (to, from)
     ebitmap to;
     ebitmap from;
{
  unsigned int i;
  ebitmap_clear (to);
  to->array = VARRAY_GROW (to->array, VARRAY_SIZE (from->array)+1);
  for (i = 0; i < VARRAY_SIZE (from->array); i++)
    {
      if (VARRAY_SBITMAP (from->array, i))
	{
	  VARRAY_SBITMAP (to->array, i) = sbitmap_alloc (EBITMAP_ELEMENT_SIZE);
	  sbitmap_copy (VARRAY_SBITMAP (to->array, i), VARRAY_SBITMAP (from->array, i));
	}
    }
}
void 
ebitmap_compress (bitmap)
	ebitmap bitmap;
{
  unsigned int i;
  for (i = 0; i < VARRAY_SIZE (bitmap->array); i++)
    {
      sbitmap temp;
      temp = VARRAY_SBITMAP (bitmap->array, i);
      if (temp)
	{
	  if (sbitmap_first_set_bit (temp) == -1)
	    {
	      sbitmap_free (VARRAY_SBITMAP (bitmap->array, i));
	      VARRAY_SBITMAP (bitmap->array, i) = 0;
	    }
	}
    }
}
/* Free an ebitmap */
void
ebitmap_free (bitmap)
     ebitmap bitmap;
{
  ebitmap_clear  (bitmap);
  VARRAY_FREE (bitmap->array);
  free (bitmap);
}

/* Allocate a new ebitmap */
ebitmap
ebitmap_alloc (void)
{
  ebitmap new = (ebitmap) xmalloc (sizeof (struct ebitmap_def));
  VARRAY_SBITMAP_INIT (new->array, 8, "ebitmap array");
  
  return new;
}

/* Set a bit in the bitmap */
void
ebitmap_set_bit (bitmap, bit)
     ebitmap bitmap;
     unsigned int bit;
{
  unsigned int base;
  sbitmap curr;
  base = bit >> EBITMAP_SHIFT;
  if (base >= VARRAY_SIZE (bitmap->array))
    VARRAY_GROW (bitmap->array, base+1);
  curr = VARRAY_SBITMAP (bitmap->array, base);
  if (!curr)
    {
      VARRAY_SBITMAP (bitmap->array, base) = curr = sbitmap_alloc (EBITMAP_ELEMENT_SIZE);
      sbitmap_zero (curr);
    }
  SET_BIT (curr, bit & EBITMAP_MASK);
}

/* Clear a bit. 
   Note that this doesn't compress the bitmap to remove empty sbitmaps, use ebitmap_compress for that.*/
void
ebitmap_clear_bit (bitmap, bit)
     ebitmap bitmap;
     unsigned int bit;
{
  unsigned int base;
  sbitmap curr;
  base = bit >> EBITMAP_SHIFT;
  if (base >= VARRAY_SIZE (bitmap->array))
    VARRAY_GROW (bitmap->array, base+1);
  curr = VARRAY_SBITMAP (bitmap->array, base);
  if (!curr)
    {
      VARRAY_SBITMAP (bitmap->array, base) = curr = sbitmap_alloc (EBITMAP_ELEMENT_SIZE);
      sbitmap_zero (curr);
      return;
    }
  RESET_BIT (curr, bit & EBITMAP_MASK);
}

/* Test whether BIT is set in BITMAP */
unsigned int
ebitmap_bit_p (bitmap, bit)
     ebitmap bitmap;
     unsigned int bit;
{
  unsigned int base;
  sbitmap curr;
  base = bit >> EBITMAP_SHIFT;
  if (base >= VARRAY_SIZE (bitmap->array))
	return 0;
  curr = VARRAY_SBITMAP (bitmap->array, base);
  return TEST_BIT (curr, bit & EBITMAP_MASK);
}

/* dest = first & second */
int
ebitmap_a_and_b (dest, first, second)
     ebitmap dest;
     ebitmap first;
     ebitmap second;
{
  unsigned int i;
  int changed = 0;
  VARRAY_GROW (dest->array, MAX (VARRAY_SIZE (first->array), VARRAY_SIZE (second->array))+1);
  for (i = 0; i < VARRAY_SIZE (dest->array); i++)
    {
      sbitmap one,two;
      if (i >= VARRAY_SIZE (second->array) || i >= VARRAY_SIZE (first->array))
	{
	  ebitmap_free_if_exist (dest, i);
	  continue;
	}
      one = SBITMAP_OR_NULL (first, i);
      two = SBITMAP_OR_NULL (second, i);
      if (!two || !one)
	{
	  if (ebitmap_free_if_exist (dest, i))
	    changed = 1;
	  continue;
	}
      if (!VARRAY_SBITMAP (dest->array, i))
	{
	  VARRAY_SBITMAP (dest->array, i) = sbitmap_alloc (EBITMAP_ELEMENT_SIZE);
	  sbitmap_zero (VARRAY_SBITMAP (dest->array, i));
	}
      changed |= sbitmap_a_and_b (VARRAY_SBITMAP (dest->array, i), one, two);
    }
  return changed;
}

/* dest = first | second */
int
ebitmap_a_or_b (dest, first, second)
     ebitmap dest;
     ebitmap first;
     ebitmap second;
{
  unsigned int i;
  int changed = 0;
  VARRAY_GROW (dest->array, MAX (VARRAY_SIZE (first->array), VARRAY_SIZE (second->array))+1);
  for (i = 0; i < VARRAY_SIZE (dest->array); i++)
    {
      sbitmap one,two;
      if (i >= VARRAY_SIZE (second->array) && i >= VARRAY_SIZE (first->array))
	{
	  ebitmap_free_if_exist (dest, i);
	  continue;
	}
      one = SBITMAP_OR_NULL (first, i);
      two = SBITMAP_OR_NULL (second, i);
      if (!two && !one)
	{
	  if (ebitmap_free_if_exist (dest, i))
	    changed = 1;
	  continue;
	}
      if (!VARRAY_SBITMAP (dest->array, i))
	{
	  VARRAY_SBITMAP (dest->array, i) = sbitmap_alloc (EBITMAP_ELEMENT_SIZE);
	  sbitmap_zero (VARRAY_SBITMAP (dest->array, i));
	}
      if (! one || ! two)
	{
	  if (!one && !sbitmap_equal (VARRAY_SBITMAP (dest->array, i), two))
	    {
	      changed = 1;
	      sbitmap_copy (VARRAY_SBITMAP (dest->array, i), two);
	    }
	  else if (!two && !sbitmap_equal (VARRAY_SBITMAP (dest->array, i), one))
	    {
	      changed = 1;
	      sbitmap_copy (VARRAY_SBITMAP (dest->array, i), one);
	    }
	  continue;
	}
      changed |= sbitmap_a_or_b (VARRAY_SBITMAP (dest->array, i), one, two);
    }
  return changed;
}

/* dest = first & ~second */
void
ebitmap_difference (dest, first, second)
     ebitmap dest;
     ebitmap first;
     ebitmap second;
{
  unsigned int i;
  int changed = 0;
  VARRAY_GROW (dest->array, MAX (VARRAY_SIZE (first->array), VARRAY_SIZE (second->array))+1);
  for (i = 0; i < VARRAY_SIZE (dest->array); i++)
    {
      sbitmap one,two;
      if (i >= VARRAY_SIZE (second->array) && i >= VARRAY_SIZE (first->array))
	{
	  ebitmap_free_if_exist (dest, i);
	  continue;
	}
      one = SBITMAP_OR_NULL (first, i);
      two = SBITMAP_OR_NULL (second, i);
      if (!one)
	{
	  if (ebitmap_free_if_exist (dest, i))
	    changed = 1;
	  continue;
	}
      if (!VARRAY_SBITMAP (dest->array, i))
	{
	  VARRAY_SBITMAP (dest->array, i) = sbitmap_alloc (EBITMAP_ELEMENT_SIZE);
	  sbitmap_zero (VARRAY_SBITMAP (dest->array, i));
	}
      if (! two)
	{
	  sbitmap_copy (VARRAY_SBITMAP (dest->array, i), one);
	  continue;
	}
      sbitmap_difference (VARRAY_SBITMAP (dest->array, i), one, two);
    }
}

/* dest = first ^ second */
int
ebitmap_a_xor_b (dest, first, second)
     ebitmap dest;
     ebitmap first;
     ebitmap second;
{
  unsigned int i;
  int changed = 0;
  VARRAY_GROW (dest->array, MAX (VARRAY_SIZE (first->array), VARRAY_SIZE (second->array))+1);
  for (i = 0; i < VARRAY_SIZE (dest->array); i++)
    {
      sbitmap one,two;
      if (i >= VARRAY_SIZE (second->array) && i >= VARRAY_SIZE (first->array))
	{
	  ebitmap_free_if_exist (dest, i);
	  continue;
	}
      one = SBITMAP_OR_NULL (first, i);
      two = SBITMAP_OR_NULL (second, i);
      if (!two && !one)
	{
	  if (ebitmap_free_if_exist (dest, i))
	    changed = 1;
	  continue;
	}
      if (!VARRAY_SBITMAP (dest->array, i))
	{
	  VARRAY_SBITMAP (dest->array, i) = sbitmap_alloc (EBITMAP_ELEMENT_SIZE);
	  sbitmap_zero (VARRAY_SBITMAP (dest->array, i));
	}
      changed |= sbitmap_a_xor_b (VARRAY_SBITMAP (dest->array, i), one, two);
    }
  return changed;
}

/* dest = a | (b & ~c).
   I know, not the most efficient implementation ever.
 */
int
ebitmap_union_of_diff (dest, a, b, c)
     ebitmap dest;
     ebitmap a;
     ebitmap b;
     ebitmap c;
{
  int changed = 0;
  ebitmap temp = ebitmap_alloc ();
  ebitmap_clear (temp);
  ebitmap_difference (temp, b, c);
  ebitmap_a_or_b (temp, a, temp);
  changed = !ebitmap_equal (temp, dest);
  if (changed)
    {
      ebitmap_clear (dest);
      ebitmap_copy (dest, temp);
    }
  ebitmap_free (temp);
  return changed;
}

/* Dump the contents of an ebitmap to a file */
void
dump_ebitmap (file, bitmap)
     FILE *file;
     ebitmap bitmap;
{
  unsigned int i;
  fprintf (file, "Dump of ebitmap:\n");
  for (i = 0; i < VARRAY_SIZE (bitmap->array); i++)
    {
      if (VARRAY_SBITMAP (bitmap->array, i))
	{
	  fprintf (file, "Bits %d-%d:", i << EBITMAP_SHIFT, (i << EBITMAP_SHIFT) + EBITMAP_ELEMENT_SIZE);
	  dump_sbitmap (file, VARRAY_SBITMAP (bitmap->array, i));
	}
    }
}

/* Determine the first set bit in BITMAP.  */
int
ebitmap_first_set_bit (bitmap)
     ebitmap bitmap;
{
  unsigned int i;
  for (i = 0; i < VARRAY_SIZE (bitmap->array); i++)
    {
      int temp;
      if (!VARRAY_SBITMAP (bitmap->array, i))
	continue;
      temp = sbitmap_first_set_bit (VARRAY_SBITMAP (bitmap->array, i));
      if (temp >= 0)
	return temp + (i << EBITMAP_SHIFT);
    }
  return -1;
}

/* Determine the last set bit in BITMAP. */
int
ebitmap_last_set_bit (bitmap)
     ebitmap bitmap;
{
  int i;
  for (i = VARRAY_SIZE (bitmap->array); i >= 0; i--)
    {
      int temp;
      if (!VARRAY_SBITMAP (bitmap->array, i))
	continue;
      temp = sbitmap_last_set_bit (VARRAY_SBITMAP (bitmap->array, i));
      if (temp >= 0)
	return temp + (i << EBITMAP_SHIFT);
    }
  return -1;
}
/* Functions to support an efficient sbitmap based bitset. 
   Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   Contributed by Daniel Berlin <dan@cgsoftware.com>
This file is part of GNU CC.

GNU CC 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.

GNU CC 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 GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

#ifndef GCC_EBITMAP_H
#define GCC_EBITMAP_H
#include "varray.h"
#define EBITMAP_SHIFT 6
#define EBITMAP_ELEMENT_SIZE (1 << EBITMAP_SHIFT)
#define EBITMAP_MASK (EBITMAP_ELEMENT_SIZE - 1)
typedef struct ebitmap_def
{
    varray_type array;
} *ebitmap;

void ebitmap_free PARAMS ((ebitmap));
#define EBITMAP_XFREE(x) ebitmap_free(x)
ebitmap ebitmap_alloc PARAMS ((void));
#define EBITMAP_XMALLOC() ebitmap_alloc()
void ebitmap_set_bit PARAMS ((ebitmap, unsigned int));
void ebitmap_clear_bit PARAMS ((ebitmap, unsigned int));
unsigned int ebitmap_bit_p PARAMS ((ebitmap, unsigned int));
void ebitmap_clear PARAMS ((ebitmap));
#define ebitmap_zero ebitmap_clear
void ebitmap_copy PARAMS ((ebitmap, ebitmap));
int ebitmap_a_or_b PARAMS ((ebitmap, ebitmap, ebitmap));
int ebitmap_a_and_b PARAMS ((ebitmap, ebitmap, ebitmap));
int ebitmap_a_xor_b PARAMS ((ebitmap, ebitmap, ebitmap));
int ebitmap_union_of_diff PARAMS ((ebitmap, ebitmap, ebitmap, ebitmap));
void ebitmap_difference PARAMS ((ebitmap, ebitmap, ebitmap));
sbitmap ebitmap_to_sbitmap PARAMS ((ebitmap));
int ebitmap_first_set_bit PARAMS ((ebitmap));
int ebitmap_last_set_bit PARAMS ((ebitmap));
int ebitmap_equal PARAMS ((ebitmap, ebitmap));
void ebitmap_compress PARAMS ((ebitmap));
void dump_ebitmap PARAMS ((FILE *, ebitmap));
/* This is tricky to get right. In particular, don't change the names
   of the variables unless you make sure they don't conflict with
   those used in EXECUTE_IF_IN_SBITMAP. */
#define EXECUTE_IF_SET_IN_EBITMAP(EBITMAP, MIN2, N2, CODE2) \
do { \
   unsigned int indx2_ = (MIN2) >> EBITMAP_SHIFT \
   unsigned int bit_num2_ = (MIN2) & EBITMAP_MASK; \
   for (indx2_; indx2_ < VARRAY_SIZE (EBITMAP->array); indx2_++) \
     { \
       if (VARRAY_SBITMAP (EBITMAP->array, indx2_)) \
	 { \
	   EXECUTE_IF_SET_IN_SBITMAP (VARRAY_SBITMAP (EBITMAP->array, indx2_), bit_num2_, (N2), \
	   { \
	     (N2) += (indx2_ << EBITMAP_SHIFT); \
	     CODE2 \
	   }); \
	 } \
     } \
  } while (0)
#endif /* GCC_BITMAP_H */


-- 
"When I was a little kid we had a sand box.  It was a quicksand
box.  I was an only child...  Eventually.
"-Steven Wright