[thirdparty/gcc.git] / gcc / sbitmap.h

/* Simple bitmaps.
   Copyright (C) 1999-2014 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 3, 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 COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#ifndef GCC_SBITMAP_H
#define GCC_SBITMAP_H

/* Implementation of sets using simple bitmap vectors.

   This set representation is suitable for non-sparse sets with a known
   (a priori) universe.  The set is represented as a simple array of the
   host's fastest unsigned integer.  For a given member I in the set:
     - the element for I will be at sbitmap[I / (bits per element)]
     - the position for I within element is I % (bits per element)

   This representation is very space-efficient for large non-sparse sets
   with random access patterns.

   The following operations can be performed in O(1) time:

     * set_size			: SBITMAP_SIZE
     * member_p			: bitmap_bit_p
     * add_member		: bitmap_set_bit
     * remove_member		: bitmap_clear_bit

   Most other operations on this set representation are O(U) where U is
   the size of the set universe:

     * clear			: bitmap_clear
     * choose_one		: bitmap_first_set_bit /
				  bitmap_last_set_bit
     * forall			: EXECUTE_IF_SET_IN_BITMAP
     * set_copy			: bitmap_copy
     * set_intersection		: bitmap_and
     * set_union		: bitmap_ior
     * set_difference		: bitmap_and_compl
     * set_disjuction		: (not implemented)
     * set_compare		: bitmap_equal_p

   Some operations on 3 sets that occur frequently in in data flow problems
   are also implemented:

      * A | (B & C)		: bitmap_or_and
      * A | (B & ~C)		: bitmap_ior_and_compl
      * A & (B | C)		: bitmap_and_or

   Most of the set functions have two variants: One that returns non-zero
   if members were added or removed from the target set, and one that just
   performs the operation without feedback.  The former operations are a
   bit more expensive but the result can often be used to avoid iterations
   on other sets.

   Allocating a bitmap is done with sbitmap_alloc, and resizing is
   performed with sbitmap_resize.

   The storage requirements for simple bitmap sets is O(U) where U is the
   size of the set universe (colloquially the number of bits in the bitmap).

   This set representation works well for relatively small data flow problems
   (there are special routines for that, see sbitmap_vector_*).  The set
   operations can be vectorized and there is almost no computating overhead,
   so that even sparse simple bitmap sets outperform dedicated sparse set
   representations like linked-list bitmaps.  For larger problems, the size
   overhead of simple bitmap sets gets too high and other set representations
   have to be used.  */

#define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)
#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT

struct simple_bitmap_def
{
  unsigned char *popcount;      /* Population count.  */
  unsigned int n_bits;		/* Number of bits.  */
  unsigned int size;		/* Size in elements.  */
  SBITMAP_ELT_TYPE elms[1];	/* The elements.  */
};

/* Return the set size needed for N elements.  */
#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)

/* Return the number of bits in BITMAP.  */
#define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits)

/* Test if bit number bitno in the bitmap is set.  */
static inline SBITMAP_ELT_TYPE
bitmap_bit_p (const_sbitmap map, int bitno)
{
  size_t i = bitno / SBITMAP_ELT_BITS;
  unsigned int s = bitno % SBITMAP_ELT_BITS;
  return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1;
}

/* Set bit number BITNO in the sbitmap MAP.  */

static inline void
bitmap_set_bit (sbitmap map, int bitno)
{
  gcc_checking_assert (! map->popcount);
  map->elms[bitno / SBITMAP_ELT_BITS]
    |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
}

/* Reset bit number BITNO in the sbitmap MAP.  */

static inline void
bitmap_clear_bit (sbitmap map, int bitno)
{
  gcc_checking_assert (! map->popcount);
  map->elms[bitno / SBITMAP_ELT_BITS]
    &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
}

/* The iterator for sbitmap.  */
struct sbitmap_iterator {
  /* The pointer to the first word of the bitmap.  */
  const SBITMAP_ELT_TYPE *ptr;

  /* The size of the bitmap.  */
  unsigned int size;

  /* The current word index.  */
  unsigned int word_num;

  /* The current bit index (not modulo SBITMAP_ELT_BITS).  */
  unsigned int bit_num;

  /* The words currently visited.  */
  SBITMAP_ELT_TYPE word;
};

/* Initialize the iterator I with sbitmap BMP and the initial index
   MIN.  */

static inline void
bmp_iter_set_init (sbitmap_iterator *i, const_sbitmap bmp,
		   unsigned int min, unsigned *bit_no ATTRIBUTE_UNUSED)
{
  i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
  i->bit_num = min;
  i->size = bmp->size;
  i->ptr = bmp->elms;

  if (i->word_num >= i->size)
    i->word = 0;
  else
    i->word = (i->ptr[i->word_num]
	       >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
}

/* Return true if we have more bits to visit, in which case *N is set
   to the index of the bit to be visited.  Otherwise, return
   false.  */

static inline bool
bmp_iter_set (sbitmap_iterator *i, unsigned int *n)
{
  /* Skip words that are zeros.  */
  for (; i->word == 0; i->word = i->ptr[i->word_num])
    {
      i->word_num++;

      /* If we have reached the end, break.  */
      if (i->word_num >= i->size)
	return false;

      i->bit_num = i->word_num * SBITMAP_ELT_BITS;
    }

  /* Skip bits that are zero.  */
  for (; (i->word & 1) == 0; i->word >>= 1)
    i->bit_num++;

  *n = i->bit_num;

  return true;
}

/* Advance to the next bit.  */

static inline void
bmp_iter_next (sbitmap_iterator *i, unsigned *bit_no ATTRIBUTE_UNUSED)
{
  i->word >>= 1;
  i->bit_num++;
}

/* Loop over all elements of SBITMAP, starting with MIN.  In each
   iteration, N is set to the index of the bit being visited.  ITER is
   an instance of sbitmap_iterator used to iterate the bitmap.  */

#ifndef EXECUTE_IF_SET_IN_BITMAP
/* See bitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP.  */
#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)	\
  for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));	\
       bmp_iter_set (&(ITER), &(BITNUM));			\
       bmp_iter_next (&(ITER), &(BITNUM)))
#endif

inline void sbitmap_free (sbitmap map)
{
  free (map->popcount);
  free (map);
}

inline void sbitmap_vector_free (sbitmap * vec)
{
  free (vec);
}

extern void dump_bitmap (FILE *, const_sbitmap);
extern void debug_raw (const simple_bitmap_def &ref);
extern void debug_raw (const simple_bitmap_def *ptr);
extern void dump_bitmap_file (FILE *, const_sbitmap);
extern void debug (const simple_bitmap_def &ref);
extern void debug (const simple_bitmap_def *ptr);
extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap *,
				 int);
extern sbitmap sbitmap_alloc (unsigned int);
extern sbitmap sbitmap_alloc_with_popcount (unsigned int);
extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
extern void bitmap_copy (sbitmap, const_sbitmap);
extern int bitmap_equal_p (const_sbitmap, const_sbitmap);
extern bool bitmap_empty_p (const_sbitmap);
extern void bitmap_clear (sbitmap);
extern void bitmap_ones (sbitmap);
extern void bitmap_vector_clear (sbitmap *, unsigned int);
extern void bitmap_vector_ones (sbitmap *, unsigned int);

extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap,
				      const_sbitmap, const_sbitmap);
extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap);
extern void bitmap_not (sbitmap, const_sbitmap);
extern bool bitmap_or_and (sbitmap, const_sbitmap,
				     const_sbitmap, const_sbitmap);
extern bool bitmap_and_or (sbitmap, const_sbitmap,
				     const_sbitmap, const_sbitmap);
extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap);
extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap);
extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap);
extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap);
extern bool bitmap_subset_p (const_sbitmap, const_sbitmap);

extern int bitmap_first_set_bit (const_sbitmap);
extern int bitmap_last_set_bit (const_sbitmap);

extern void debug_bitmap (const_sbitmap);
extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long);
#endif /* ! GCC_SBITMAP_H */
Commit	Line	Data
5f6c11d6	1	/* Simple bitmaps.
23a5b65a	2	Copyright (C) 1999-2014 Free Software Foundation, Inc.
5f6c11d6	3
1322177d	4	This file is part of GCC.
5f6c11d6	5
1322177d LB	6	GCC is free software; you can redistribute it and/or modify it under
1322177d LB	7	the terms of the GNU General Public License as published by the Free
9dcd6f09	8	Software Foundation; either version 3, or (at your option) any later
1322177d	9	version.
5f6c11d6	10
1322177d LB	11	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
	12	WARRANTY; without even the implied warranty of MERCHANTABILITY or
	13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	14	for more details.
5f6c11d6 RH	15
5f6c11d6 RH	16	You should have received a copy of the GNU General Public License
9dcd6f09 NC	17	along with GCC; see the file COPYING3. If not see
9dcd6f09 NC	18	<http://www.gnu.org/licenses/>. */
5f6c11d6	19
88657302	20	#ifndef GCC_SBITMAP_H
46c5ad27	21	#define GCC_SBITMAP_H
4dc9341c	22
0263463d SB	23	/* Implementation of sets using simple bitmap vectors.
	24
	25	This set representation is suitable for non-sparse sets with a known
	26	(a priori) universe. The set is represented as a simple array of the
	27	host's fastest unsigned integer. For a given member I in the set:
	28	- the element for I will be at sbitmap[I / (bits per element)]
	29	- the position for I within element is I % (bits per element)
	30
	31	This representation is very space-efficient for large non-sparse sets
	32	with random access patterns.
	33
	34	The following operations can be performed in O(1) time:
	35
	36	* set_size : SBITMAP_SIZE
d7c028c0 LC	37	* member_p : bitmap_bit_p
	38	* add_member : bitmap_set_bit
	39	* remove_member : bitmap_clear_bit
0263463d SB	40
	41	Most other operations on this set representation are O(U) where U is
	42	the size of the set universe:
	43
f61e445a	44	* clear : bitmap_clear
f61e445a LC	45	* choose_one : bitmap_first_set_bit /
f61e445a LC	46	bitmap_last_set_bit
d4ac4ce2	47	* forall : EXECUTE_IF_SET_IN_BITMAP
5fd39ce6	48	* set_copy : bitmap_copy
f61e445a LC	49	* set_intersection : bitmap_and
	50	* set_union : bitmap_ior
	51	* set_difference : bitmap_and_compl
0263463d	52	* set_disjuction : (not implemented)
f61e445a	53	* set_compare : bitmap_equal_p
0263463d SB	54
	55	Some operations on 3 sets that occur frequently in in data flow problems
	56	are also implemented:
	57
f61e445a LC	58	* A \| (B & C) : bitmap_or_and
	59	* A \| (B & ~C) : bitmap_ior_and_compl
	60	* A & (B \| C) : bitmap_and_or
0263463d SB	61
	62	Most of the set functions have two variants: One that returns non-zero
	63	if members were added or removed from the target set, and one that just
	64	performs the operation without feedback. The former operations are a
	65	bit more expensive but the result can often be used to avoid iterations
	66	on other sets.
	67
	68	Allocating a bitmap is done with sbitmap_alloc, and resizing is
	69	performed with sbitmap_resize.
	70
	71	The storage requirements for simple bitmap sets is O(U) where U is the
	72	size of the set universe (colloquially the number of bits in the bitmap).
	73
	74	This set representation works well for relatively small data flow problems
	75	(there are special routines for that, see sbitmap_vector_*). The set
	76	operations can be vectorized and there is almost no computating overhead,
	77	so that even sparse simple bitmap sets outperform dedicated sparse set
	78	representations like linked-list bitmaps. For larger problems, the size
	79	overhead of simple bitmap sets gets too high and other set representations
	80	have to be used. */
5f6c11d6	81
7aa6d18a	82	#define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)
99fa8911	83	#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
5f6c11d6	84
7a8cba34	85	struct simple_bitmap_def
08158df3	86	{
97508a6b	87	unsigned char popcount; / Population count. */
08158df3 RK	88	unsigned int n_bits; /* Number of bits. */
08158df3 RK	89	unsigned int size; /* Size in elements. */
08158df3	90	SBITMAP_ELT_TYPE elms[1]; /* The elements. */
7a8cba34	91	};
5f6c11d6	92
5f6c11d6	93	/* Return the set size needed for N elements. */
08158df3	94	#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
5f6c11d6	95
0263463d SB	96	/* Return the number of bits in BITMAP. */
	97	#define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits)
	98
08158df3	99	/* Test if bit number bitno in the bitmap is set. */
0263463d	100	static inline SBITMAP_ELT_TYPE
d7c028c0	101	bitmap_bit_p (const_sbitmap map, int bitno)
0263463d SB	102	{
	103	size_t i = bitno / SBITMAP_ELT_BITS;
	104	unsigned int s = bitno % SBITMAP_ELT_BITS;
	105	return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1;
	106	}
5f6c11d6	107
0263463d	108	/* Set bit number BITNO in the sbitmap MAP. */
97508a6b DB	109
97508a6b DB	110	static inline void
d7c028c0	111	bitmap_set_bit (sbitmap map, int bitno)
97508a6b	112	{
0263463d	113	gcc_checking_assert (! map->popcount);
97508a6b DB	114	map->elms[bitno / SBITMAP_ELT_BITS]
	115	\|= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
	116	}
	117
0263463d	118	/* Reset bit number BITNO in the sbitmap MAP. */
97508a6b DB	119
97508a6b DB	120	static inline void
d7c028c0	121	bitmap_clear_bit (sbitmap map, int bitno)
97508a6b	122	{
0263463d SB	123	gcc_checking_assert (! map->popcount);
	124	map->elms[bitno / SBITMAP_ELT_BITS]
	125	&= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
	126	}
	127
b6e7e9af	128	/* The iterator for sbitmap. */
84562394	129	struct sbitmap_iterator {
b6e7e9af	130	/* The pointer to the first word of the bitmap. */
be5b01f3	131	const SBITMAP_ELT_TYPE *ptr;
b6e7e9af KH	132
	133	/* The size of the bitmap. */
	134	unsigned int size;
	135
	136	/* The current word index. */
	137	unsigned int word_num;
	138
108267cd	139	/* The current bit index (not modulo SBITMAP_ELT_BITS). */
b6e7e9af KH	140	unsigned int bit_num;
	141
	142	/* The words currently visited. */
	143	SBITMAP_ELT_TYPE word;
84562394	144	};
b6e7e9af KH	145
	146	/* Initialize the iterator I with sbitmap BMP and the initial index
	147	MIN. */
	148
	149	static inline void
d4ac4ce2 LC	150	bmp_iter_set_init (sbitmap_iterator *i, const_sbitmap bmp,
d4ac4ce2 LC	151	unsigned int min, unsigned *bit_no ATTRIBUTE_UNUSED)
b6e7e9af KH	152	{
b6e7e9af KH	153	i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
108267cd	154	i->bit_num = min;
b6e7e9af KH	155	i->size = bmp->size;
	156	i->ptr = bmp->elms;
	157
	158	if (i->word_num >= i->size)
	159	i->word = 0;
	160	else
108267cd KH	161	i->word = (i->ptr[i->word_num]
108267cd KH	162	>> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
b6e7e9af KH	163	}
	164
	165	/* Return true if we have more bits to visit, in which case *N is set
	166	to the index of the bit to be visited. Otherwise, return
	167	false. */
	168
	169	static inline bool
d4ac4ce2	170	bmp_iter_set (sbitmap_iterator i, unsigned int n)
b6e7e9af KH	171	{
	172	/* Skip words that are zeros. */
	173	for (; i->word == 0; i->word = i->ptr[i->word_num])
	174	{
	175	i->word_num++;
	176
	177	/* If we have reached the end, break. */
	178	if (i->word_num >= i->size)
	179	return false;
	180
	181	i->bit_num = i->word_num * SBITMAP_ELT_BITS;
	182	}
	183
	184	/* Skip bits that are zero. */
	185	for (; (i->word & 1) == 0; i->word >>= 1)
	186	i->bit_num++;
	187
	188	*n = i->bit_num;
	189
	190	return true;
	191	}
	192
	193	/* Advance to the next bit. */
	194
	195	static inline void
d4ac4ce2	196	bmp_iter_next (sbitmap_iterator i, unsigned bit_no ATTRIBUTE_UNUSED)
b6e7e9af KH	197	{
	198	i->word >>= 1;
	199	i->bit_num++;
	200	}
	201
	202	/* Loop over all elements of SBITMAP, starting with MIN. In each
	203	iteration, N is set to the index of the bit being visited. ITER is
	204	an instance of sbitmap_iterator used to iterate the bitmap. */
	205
d4ac4ce2 LC	206	#ifndef EXECUTE_IF_SET_IN_BITMAP
	207	/* See bitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */
	208	#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
	209	for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
	210	bmp_iter_set (&(ITER), &(BITNUM)); \
	211	bmp_iter_next (&(ITER), &(BITNUM)))
	212	#endif
ed8d2920	213
f61e445a LC	214	inline void sbitmap_free (sbitmap map)
	215	{
	216	free (map->popcount);
	217	free (map);
	218	}
5f6c11d6	219
f61e445a LC	220	inline void sbitmap_vector_free (sbitmap * vec)
	221	{
	222	free (vec);
	223	}
	224
	225	extern void dump_bitmap (FILE *, const_sbitmap);
7b3b6ae4 LC	226	extern void debug_raw (const simple_bitmap_def &ref);
7b3b6ae4 LC	227	extern void debug_raw (const simple_bitmap_def *ptr);
f61e445a	228	extern void dump_bitmap_file (FILE *, const_sbitmap);
7b3b6ae4 LC	229	extern void debug (const simple_bitmap_def &ref);
7b3b6ae4 LC	230	extern void debug (const simple_bitmap_def *ptr);
f61e445a	231	extern void dump_bitmap_vector (FILE , const char , const char , sbitmap ,
46c5ad27 AJ	232	int);
46c5ad27 AJ	233	extern sbitmap sbitmap_alloc (unsigned int);
97508a6b	234	extern sbitmap sbitmap_alloc_with_popcount (unsigned int);
46c5ad27 AJ	235	extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
46c5ad27 AJ	236	extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
f61e445a	237	extern void bitmap_copy (sbitmap, const_sbitmap);
f61e445a LC	238	extern int bitmap_equal_p (const_sbitmap, const_sbitmap);
f61e445a LC	239	extern bool bitmap_empty_p (const_sbitmap);
f61e445a LC	240	extern void bitmap_clear (sbitmap);
	241	extern void bitmap_ones (sbitmap);
	242	extern void bitmap_vector_clear (sbitmap *, unsigned int);
	243	extern void bitmap_vector_ones (sbitmap *, unsigned int);
	244
	245	extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap,
0263463d	246	const_sbitmap, const_sbitmap);
f61e445a LC	247	extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap);
	248	extern void bitmap_not (sbitmap, const_sbitmap);
	249	extern bool bitmap_or_and (sbitmap, const_sbitmap,
0263463d	250	const_sbitmap, const_sbitmap);
f61e445a	251	extern bool bitmap_and_or (sbitmap, const_sbitmap,
0263463d	252	const_sbitmap, const_sbitmap);
f61e445a LC	253	extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap);
	254	extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap);
	255	extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap);
	256	extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap);
	257	extern bool bitmap_subset_p (const_sbitmap, const_sbitmap);
	258
	259	extern int bitmap_first_set_bit (const_sbitmap);
	260	extern int bitmap_last_set_bit (const_sbitmap);
	261
	262	extern void debug_bitmap (const_sbitmap);
6de9cd9a	263	extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
3c2c4f22	264	extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long);
88657302	265	#endif /* ! GCC_SBITMAP_H */