[gcc.git] / gcc / sbitmap.h

/* Simple bitmaps.
   Copyright (C) 1999, 2000, 2002, 2003, 2004 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_SBITMAP_H
#define GCC_SBITMAP_H

/* It's not clear yet whether using bitmap.[ch] will be a win.
   It should be straightforward to convert so for now we keep things simple
   while more important issues are dealt with.  */

#define SBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT

typedef struct simple_bitmap_def
{
  unsigned int n_bits;		/* Number of bits.  */
  unsigned int size;		/* Size in elements.  */
  unsigned int bytes;		/* Size in bytes.  */
  SBITMAP_ELT_TYPE elms[1];	/* The elements.  */
} *sbitmap;

typedef SBITMAP_ELT_TYPE *sbitmap_ptr;

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

/* Set bit number bitno in the bitmap.  */
#define SET_BIT(BITMAP, BITNO)					\
  ((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS]			\
   |= (SBITMAP_ELT_TYPE) 1 << (BITNO) % SBITMAP_ELT_BITS)

/* Test if bit number bitno in the bitmap is set.  */
#define TEST_BIT(BITMAP, BITNO) \
((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] >> (BITNO) % SBITMAP_ELT_BITS & 1)

/* Reset bit number bitno in the bitmap.  */
#define RESET_BIT(BITMAP, BITNO)				\
  ((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS]			\
   &= ~((SBITMAP_ELT_TYPE) 1 << (BITNO) % SBITMAP_ELT_BITS))

/* The iterator for sbitmap.  */
typedef struct {
  /* The pointer to the first word of the bitmap.  */
  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;
} sbitmap_iterator;

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

static inline void
sbitmap_iter_init (sbitmap_iterator *i, sbitmap bmp, unsigned int min)
{
  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
sbitmap_iter_cond (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
sbitmap_iter_next (sbitmap_iterator *i)
{
  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.  */

#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, ITER)	\
  for (sbitmap_iter_init (&(ITER), (SBITMAP), (MIN));		\
       sbitmap_iter_cond (&(ITER), &(N));			\
       sbitmap_iter_next (&(ITER)))

#define EXECUTE_IF_SET_IN_SBITMAP_REV(SBITMAP, N, CODE)			\
do {									\
  unsigned int word_num_;						\
  unsigned int bit_num_;						\
  unsigned int size_ = (SBITMAP)->size;					\
  SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms;				\
									\
  for (word_num_ = size_; word_num_ > 0; word_num_--)			\
    {									\
      SBITMAP_ELT_TYPE word_ = ptr_[word_num_ - 1];			\
									\
      if (word_ != 0)							\
	for (bit_num_ = SBITMAP_ELT_BITS; bit_num_ > 0; bit_num_--)	\
	  {								\
	    SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE)1 << (bit_num_ - 1);\
									\
	    if ((word_ & _mask) != 0)					\
	      {								\
		word_ &= ~ _mask;					\
		(N) = (word_num_ - 1) * SBITMAP_ELT_BITS + bit_num_ - 1;\
		CODE;							\
		if (word_ == 0)						\
		  break;						\
	      }								\
	  }								\
    }									\
} while (0)

#define sbitmap_free(MAP)		free(MAP)
#define sbitmap_vector_free(VEC)	free(VEC)

struct int_list;

extern void dump_sbitmap (FILE *, sbitmap);
extern void dump_sbitmap_file (FILE *, sbitmap);
extern void dump_sbitmap_vector (FILE *, const char *, const char *, sbitmap *,
				 int);
extern sbitmap sbitmap_alloc (unsigned int);
extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
extern void sbitmap_copy (sbitmap, sbitmap);
extern int sbitmap_equal (sbitmap, sbitmap);
extern void sbitmap_zero (sbitmap);
extern void sbitmap_ones (sbitmap);
extern void sbitmap_vector_zero (sbitmap *, unsigned int);
extern void sbitmap_vector_ones (sbitmap *, unsigned int);

extern void sbitmap_union_of_diff (sbitmap, sbitmap, sbitmap, sbitmap);
extern bool sbitmap_union_of_diff_cg (sbitmap, sbitmap, sbitmap, sbitmap);
extern void sbitmap_difference (sbitmap, sbitmap, sbitmap);
extern void sbitmap_not (sbitmap, sbitmap);
extern void sbitmap_a_or_b_and_c (sbitmap, sbitmap, sbitmap, sbitmap);
extern bool sbitmap_a_or_b_and_c_cg (sbitmap, sbitmap, sbitmap, sbitmap);
extern void sbitmap_a_and_b_or_c (sbitmap, sbitmap, sbitmap, sbitmap);
extern bool sbitmap_a_and_b_or_c_cg (sbitmap, sbitmap, sbitmap, sbitmap);
extern bool sbitmap_any_common_bits (sbitmap, sbitmap);
extern void sbitmap_a_and_b (sbitmap, sbitmap, sbitmap);
extern bool sbitmap_a_and_b_cg (sbitmap, sbitmap, sbitmap);
extern void sbitmap_a_or_b (sbitmap, sbitmap, sbitmap);
extern bool sbitmap_a_or_b_cg (sbitmap, sbitmap, sbitmap);
extern void sbitmap_a_xor_b (sbitmap, sbitmap, sbitmap);
extern bool sbitmap_a_xor_b_cg (sbitmap, sbitmap, sbitmap);
extern bool sbitmap_a_subset_b_p (sbitmap, sbitmap);

extern int sbitmap_first_set_bit (sbitmap);
extern int sbitmap_last_set_bit (sbitmap);

extern void sbitmap_intersect_of_predsucc (sbitmap, sbitmap *, int,
					   struct int_list **);
#define sbitmap_intersect_of_predecessors  sbitmap_intersect_of_predsucc
#define sbitmap_intersect_of_successors    sbitmap_intersect_of_predsucc

extern void sbitmap_union_of_predsucc (sbitmap, sbitmap *, int,
				       struct int_list **);
#define sbitmap_union_of_predecessors  sbitmap_union_of_predsucc
#define sbitmap_union_of_successors    sbitmap_union_of_predsucc

/* Intersection and Union of preds/succs using the new flow graph
   structure instead of the pred/succ arrays.  */

extern void sbitmap_intersection_of_succs (sbitmap, sbitmap *, int);
extern void sbitmap_intersection_of_preds (sbitmap, sbitmap *, int);
extern void sbitmap_union_of_succs (sbitmap, sbitmap *, int);
extern void sbitmap_union_of_preds (sbitmap, sbitmap *, int);

extern void debug_sbitmap (sbitmap);
extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
#endif /* ! GCC_SBITMAP_H */
Commit	Line	Data
5f6c11d6	1	/* Simple bitmaps.
f30278e8	2	Copyright (C) 1999, 2000, 2002, 2003, 2004 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
	7	the terms of the GNU General Public License as published by the Free
	8	Software Foundation; either version 2, or (at your option) any later
	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
1322177d	17	along with GCC; see the file COPYING. If not, write to the Free
366ccddb KC	18	Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
366ccddb KC	19	02110-1301, USA. */
5f6c11d6	20
88657302	21	#ifndef GCC_SBITMAP_H
46c5ad27	22	#define GCC_SBITMAP_H
4dc9341c	23
5f6c11d6 RH	24	/* It's not clear yet whether using bitmap.[ch] will be a win.
	25	It should be straightforward to convert so for now we keep things simple
	26	while more important issues are dealt with. */
	27
99fa8911 AP	28	#define SBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
99fa8911 AP	29	#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
5f6c11d6	30
08158df3 RK	31	typedef struct simple_bitmap_def
	32	{
	33	unsigned int n_bits; /* Number of bits. */
	34	unsigned int size; /* Size in elements. */
	35	unsigned int bytes; /* Size in bytes. */
	36	SBITMAP_ELT_TYPE elms[1]; /* The elements. */
5f6c11d6 RH	37	} *sbitmap;
	38
	39	typedef SBITMAP_ELT_TYPE *sbitmap_ptr;
	40
	41	/* Return the set size needed for N elements. */
08158df3	42	#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
5f6c11d6	43
08158df3 RK	44	/* Set bit number bitno in the bitmap. */
	45	#define SET_BIT(BITMAP, BITNO) \
	46	((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] \
	47	\|= (SBITMAP_ELT_TYPE) 1 << (BITNO) % SBITMAP_ELT_BITS)
5f6c11d6	48
08158df3 RK	49	/* Test if bit number bitno in the bitmap is set. */
	50	#define TEST_BIT(BITMAP, BITNO) \
	51	((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] >> (BITNO) % SBITMAP_ELT_BITS & 1)
5f6c11d6	52
08158df3 RK	53	/* Reset bit number bitno in the bitmap. */
	54	#define RESET_BIT(BITMAP, BITNO) \
	55	((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] \
	56	&= ~((SBITMAP_ELT_TYPE) 1 << (BITNO) % SBITMAP_ELT_BITS))
5f6c11d6	57
b6e7e9af KH	58	/* The iterator for sbitmap. */
	59	typedef struct {
	60	/* The pointer to the first word of the bitmap. */
	61	SBITMAP_ELT_TYPE *ptr;
	62
	63	/* The size of the bitmap. */
	64	unsigned int size;
	65
	66	/* The current word index. */
	67	unsigned int word_num;
	68
108267cd	69	/* The current bit index (not modulo SBITMAP_ELT_BITS). */
b6e7e9af KH	70	unsigned int bit_num;
	71
	72	/* The words currently visited. */
	73	SBITMAP_ELT_TYPE word;
	74	} sbitmap_iterator;
	75
	76	/* Initialize the iterator I with sbitmap BMP and the initial index
	77	MIN. */
	78
	79	static inline void
	80	sbitmap_iter_init (sbitmap_iterator *i, sbitmap bmp, unsigned int min)
	81	{
	82	i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
108267cd	83	i->bit_num = min;
b6e7e9af KH	84	i->size = bmp->size;
	85	i->ptr = bmp->elms;
	86
	87	if (i->word_num >= i->size)
	88	i->word = 0;
	89	else
108267cd KH	90	i->word = (i->ptr[i->word_num]
108267cd KH	91	>> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
b6e7e9af KH	92	}
	93
	94	/* Return true if we have more bits to visit, in which case *N is set
	95	to the index of the bit to be visited. Otherwise, return
	96	false. */
	97
	98	static inline bool
	99	sbitmap_iter_cond (sbitmap_iterator i, unsigned int n)
	100	{
	101	/* Skip words that are zeros. */
	102	for (; i->word == 0; i->word = i->ptr[i->word_num])
	103	{
	104	i->word_num++;
	105
	106	/* If we have reached the end, break. */
	107	if (i->word_num >= i->size)
	108	return false;
	109
	110	i->bit_num = i->word_num * SBITMAP_ELT_BITS;
	111	}
	112
	113	/* Skip bits that are zero. */
	114	for (; (i->word & 1) == 0; i->word >>= 1)
	115	i->bit_num++;
	116
	117	*n = i->bit_num;
	118
	119	return true;
	120	}
	121
	122	/* Advance to the next bit. */
	123
	124	static inline void
	125	sbitmap_iter_next (sbitmap_iterator *i)
	126	{
	127	i->word >>= 1;
	128	i->bit_num++;
	129	}
	130
	131	/* Loop over all elements of SBITMAP, starting with MIN. In each
	132	iteration, N is set to the index of the bit being visited. ITER is
	133	an instance of sbitmap_iterator used to iterate the bitmap. */
	134
	135	#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, ITER) \
	136	for (sbitmap_iter_init (&(ITER), (SBITMAP), (MIN)); \
	137	sbitmap_iter_cond (&(ITER), &(N)); \
	138	sbitmap_iter_next (&(ITER)))
5f6c11d6	139
ed8d2920 MM	140	#define EXECUTE_IF_SET_IN_SBITMAP_REV(SBITMAP, N, CODE) \
	141	do { \
	142	unsigned int word_num_; \
	143	unsigned int bit_num_; \
	144	unsigned int size_ = (SBITMAP)->size; \
	145	SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \
	146	\
	147	for (word_num_ = size_; word_num_ > 0; word_num_--) \
	148	{ \
	149	SBITMAP_ELT_TYPE word_ = ptr_[word_num_ - 1]; \
	150	\
	151	if (word_ != 0) \
	152	for (bit_num_ = SBITMAP_ELT_BITS; bit_num_ > 0; bit_num_--) \
	153	{ \
	154	SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE)1 << (bit_num_ - 1);\
	155	\
	156	if ((word_ & _mask) != 0) \
	157	{ \
	158	word_ &= ~ _mask; \
	159	(N) = (word_num_ - 1) * SBITMAP_ELT_BITS + bit_num_ - 1;\
	160	CODE; \
	161	if (word_ == 0) \
	162	break; \
	163	} \
	164	} \
	165	} \
	166	} while (0)
	167
08158df3 RK	168	#define sbitmap_free(MAP) free(MAP)
08158df3 RK	169	#define sbitmap_vector_free(VEC) free(VEC)
5f6c11d6	170
08158df3	171	struct int_list;
5f6c11d6	172
46c5ad27 AJ	173	extern void dump_sbitmap (FILE *, sbitmap);
	174	extern void dump_sbitmap_file (FILE *, sbitmap);
	175	extern void dump_sbitmap_vector (FILE , const char , const char , sbitmap ,
	176	int);
	177	extern sbitmap sbitmap_alloc (unsigned int);
	178	extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
	179	extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
	180	extern void sbitmap_copy (sbitmap, sbitmap);
	181	extern int sbitmap_equal (sbitmap, sbitmap);
	182	extern void sbitmap_zero (sbitmap);
	183	extern void sbitmap_ones (sbitmap);
	184	extern void sbitmap_vector_zero (sbitmap *, unsigned int);
	185	extern void sbitmap_vector_ones (sbitmap *, unsigned int);
	186
	187	extern void sbitmap_union_of_diff (sbitmap, sbitmap, sbitmap, sbitmap);
	188	extern bool sbitmap_union_of_diff_cg (sbitmap, sbitmap, sbitmap, sbitmap);
	189	extern void sbitmap_difference (sbitmap, sbitmap, sbitmap);
	190	extern void sbitmap_not (sbitmap, sbitmap);
	191	extern void sbitmap_a_or_b_and_c (sbitmap, sbitmap, sbitmap, sbitmap);
	192	extern bool sbitmap_a_or_b_and_c_cg (sbitmap, sbitmap, sbitmap, sbitmap);
	193	extern void sbitmap_a_and_b_or_c (sbitmap, sbitmap, sbitmap, sbitmap);
	194	extern bool sbitmap_a_and_b_or_c_cg (sbitmap, sbitmap, sbitmap, sbitmap);
874437bc	195	extern bool sbitmap_any_common_bits (sbitmap, sbitmap);
46c5ad27 AJ	196	extern void sbitmap_a_and_b (sbitmap, sbitmap, sbitmap);
	197	extern bool sbitmap_a_and_b_cg (sbitmap, sbitmap, sbitmap);
	198	extern void sbitmap_a_or_b (sbitmap, sbitmap, sbitmap);
	199	extern bool sbitmap_a_or_b_cg (sbitmap, sbitmap, sbitmap);
	200	extern void sbitmap_a_xor_b (sbitmap, sbitmap, sbitmap);
	201	extern bool sbitmap_a_xor_b_cg (sbitmap, sbitmap, sbitmap);
	202	extern bool sbitmap_a_subset_b_p (sbitmap, sbitmap);
	203
	204	extern int sbitmap_first_set_bit (sbitmap);
	205	extern int sbitmap_last_set_bit (sbitmap);
	206
	207	extern void sbitmap_intersect_of_predsucc (sbitmap, sbitmap *, int,
	208	struct int_list **);
5f6c11d6 RH	209	#define sbitmap_intersect_of_predecessors sbitmap_intersect_of_predsucc
	210	#define sbitmap_intersect_of_successors sbitmap_intersect_of_predsucc
	211
46c5ad27 AJ	212	extern void sbitmap_union_of_predsucc (sbitmap, sbitmap *, int,
46c5ad27 AJ	213	struct int_list **);
5f6c11d6 RH	214	#define sbitmap_union_of_predecessors sbitmap_union_of_predsucc
5f6c11d6 RH	215	#define sbitmap_union_of_successors sbitmap_union_of_predsucc
36349f8b	216
46c5ad27	217	/* Intersection and Union of preds/succs using the new flow graph
36349f8b AM	218	structure instead of the pred/succ arrays. */
36349f8b AM	219
46c5ad27 AJ	220	extern void sbitmap_intersection_of_succs (sbitmap, sbitmap *, int);
	221	extern void sbitmap_intersection_of_preds (sbitmap, sbitmap *, int);
	222	extern void sbitmap_union_of_succs (sbitmap, sbitmap *, int);
	223	extern void sbitmap_union_of_preds (sbitmap, sbitmap *, int);
36349f8b	224
46c5ad27	225	extern void debug_sbitmap (sbitmap);
6de9cd9a	226	extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
88657302	227	#endif /* ! GCC_SBITMAP_H */