[gcc.git] / gcc / sbitmap.h

/* Simple bitmaps.
   Copyright (C) 1999, 2000, 2002, 2003 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, 59 Temple Place - Suite 330, Boston, MA
02111-1307, 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_WIDE_INT)
#define SBITMAP_ELT_TYPE unsigned HOST_WIDE_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))

/* Loop over all elements of SBITSET, starting with MIN.  */
#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, CODE)		\
do {									\
  unsigned int word_num_;						\
  unsigned int bit_num_ = (MIN) % (unsigned int) SBITMAP_ELT_BITS;	\
  unsigned int size_ = (SBITMAP)->size;					\
  SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms;				\
									\
  for (word_num_ = (MIN) / (unsigned int) SBITMAP_ELT_BITS;		\
       word_num_ < size_; word_num_++, bit_num_ = 0)			\
    {									\
      SBITMAP_ELT_TYPE word_ = ptr_[word_num_];				\
									\
      if (word_ != 0)							\
	for (; bit_num_ < SBITMAP_ELT_BITS; bit_num_++)			\
	  {								\
	    SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE) 1 << bit_num_;	\
									\
	    if ((word_ & _mask) != 0)					\
	      {								\
		word_ &= ~ _mask;					\
		(N) = word_num_ * SBITMAP_ELT_BITS + bit_num_;		\
		CODE;							\
		if (word_ == 0)						\
		  break;						\
	      }								\
	  }								\
    }									\
} while (0)

#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 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);
#endif /* ! GCC_SBITMAP_H */
Commit	Line	Data
5f6c11d6	1	/* Simple bitmaps.
e360ab39	2	Copyright (C) 1999, 2000, 2002, 2003 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 LB	17	along with GCC; see the file COPYING. If not, write to the Free
	18	Software Foundation, 59 Temple Place - Suite 330, Boston, MA
	19	02111-1307, 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
be200dff	28	#define SBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDE_INT)
5f6c11d6 RH	29	#define SBITMAP_ELT_TYPE unsigned HOST_WIDE_INT
5f6c11d6 RH	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 RH	57
	58	/* Loop over all elements of SBITSET, starting with MIN. */
	59	#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, CODE) \
	60	do { \
e0bf4f7b RK	61	unsigned int word_num_; \
	62	unsigned int bit_num_ = (MIN) % (unsigned int) SBITMAP_ELT_BITS; \
	63	unsigned int size_ = (SBITMAP)->size; \
	64	SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \
5f6c11d6	65	\
e0bf4f7b RK	66	for (word_num_ = (MIN) / (unsigned int) SBITMAP_ELT_BITS; \
e0bf4f7b RK	67	word_num_ < size_; word_num_++, bit_num_ = 0) \
5f6c11d6	68	{ \
e0bf4f7b	69	SBITMAP_ELT_TYPE word_ = ptr_[word_num_]; \
08158df3	70	\
e0bf4f7b RK	71	if (word_ != 0) \
e0bf4f7b RK	72	for (; bit_num_ < SBITMAP_ELT_BITS; bit_num_++) \
08158df3	73	{ \
cf403648	74	SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE) 1 << bit_num_; \
08158df3	75	\
e0bf4f7b	76	if ((word_ & _mask) != 0) \
08158df3	77	{ \
e0bf4f7b RK	78	word_ &= ~ _mask; \
e0bf4f7b RK	79	(N) = word_num_ * SBITMAP_ELT_BITS + bit_num_; \
08158df3	80	CODE; \
e0bf4f7b	81	if (word_ == 0) \
08158df3 RK	82	break; \
	83	} \
	84	} \
	85	} \
5f6c11d6 RH	86	} while (0)
5f6c11d6 RH	87
ed8d2920 MM	88	#define EXECUTE_IF_SET_IN_SBITMAP_REV(SBITMAP, N, CODE) \
	89	do { \
	90	unsigned int word_num_; \
	91	unsigned int bit_num_; \
	92	unsigned int size_ = (SBITMAP)->size; \
	93	SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \
	94	\
	95	for (word_num_ = size_; word_num_ > 0; word_num_--) \
	96	{ \
	97	SBITMAP_ELT_TYPE word_ = ptr_[word_num_ - 1]; \
	98	\
	99	if (word_ != 0) \
	100	for (bit_num_ = SBITMAP_ELT_BITS; bit_num_ > 0; bit_num_--) \
	101	{ \
	102	SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE)1 << (bit_num_ - 1);\
	103	\
	104	if ((word_ & _mask) != 0) \
	105	{ \
	106	word_ &= ~ _mask; \
	107	(N) = (word_num_ - 1) * SBITMAP_ELT_BITS + bit_num_ - 1;\
	108	CODE; \
	109	if (word_ == 0) \
	110	break; \
	111	} \
	112	} \
	113	} \
	114	} while (0)
	115
08158df3 RK	116	#define sbitmap_free(MAP) free(MAP)
08158df3 RK	117	#define sbitmap_vector_free(VEC) free(VEC)
5f6c11d6	118
08158df3	119	struct int_list;
5f6c11d6	120
46c5ad27 AJ	121	extern void dump_sbitmap (FILE *, sbitmap);
	122	extern void dump_sbitmap_file (FILE *, sbitmap);
	123	extern void dump_sbitmap_vector (FILE , const char , const char , sbitmap ,
	124	int);
	125	extern sbitmap sbitmap_alloc (unsigned int);
	126	extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
	127	extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
	128	extern void sbitmap_copy (sbitmap, sbitmap);
	129	extern int sbitmap_equal (sbitmap, sbitmap);
	130	extern void sbitmap_zero (sbitmap);
	131	extern void sbitmap_ones (sbitmap);
	132	extern void sbitmap_vector_zero (sbitmap *, unsigned int);
	133	extern void sbitmap_vector_ones (sbitmap *, unsigned int);
	134
	135	extern void sbitmap_union_of_diff (sbitmap, sbitmap, sbitmap, sbitmap);
	136	extern bool sbitmap_union_of_diff_cg (sbitmap, sbitmap, sbitmap, sbitmap);
	137	extern void sbitmap_difference (sbitmap, sbitmap, sbitmap);
	138	extern void sbitmap_not (sbitmap, sbitmap);
	139	extern void sbitmap_a_or_b_and_c (sbitmap, sbitmap, sbitmap, sbitmap);
	140	extern bool sbitmap_a_or_b_and_c_cg (sbitmap, sbitmap, sbitmap, sbitmap);
	141	extern void sbitmap_a_and_b_or_c (sbitmap, sbitmap, sbitmap, sbitmap);
	142	extern bool sbitmap_a_and_b_or_c_cg (sbitmap, sbitmap, sbitmap, sbitmap);
	143	extern void sbitmap_a_and_b (sbitmap, sbitmap, sbitmap);
	144	extern bool sbitmap_a_and_b_cg (sbitmap, sbitmap, sbitmap);
	145	extern void sbitmap_a_or_b (sbitmap, sbitmap, sbitmap);
	146	extern bool sbitmap_a_or_b_cg (sbitmap, sbitmap, sbitmap);
	147	extern void sbitmap_a_xor_b (sbitmap, sbitmap, sbitmap);
	148	extern bool sbitmap_a_xor_b_cg (sbitmap, sbitmap, sbitmap);
	149	extern bool sbitmap_a_subset_b_p (sbitmap, sbitmap);
	150
	151	extern int sbitmap_first_set_bit (sbitmap);
	152	extern int sbitmap_last_set_bit (sbitmap);
	153
	154	extern void sbitmap_intersect_of_predsucc (sbitmap, sbitmap *, int,
	155	struct int_list **);
5f6c11d6 RH	156	#define sbitmap_intersect_of_predecessors sbitmap_intersect_of_predsucc
	157	#define sbitmap_intersect_of_successors sbitmap_intersect_of_predsucc
	158
46c5ad27 AJ	159	extern void sbitmap_union_of_predsucc (sbitmap, sbitmap *, int,
46c5ad27 AJ	160	struct int_list **);
5f6c11d6 RH	161	#define sbitmap_union_of_predecessors sbitmap_union_of_predsucc
5f6c11d6 RH	162	#define sbitmap_union_of_successors sbitmap_union_of_predsucc
36349f8b	163
46c5ad27	164	/* Intersection and Union of preds/succs using the new flow graph
36349f8b AM	165	structure instead of the pred/succ arrays. */
36349f8b AM	166
46c5ad27 AJ	167	extern void sbitmap_intersection_of_succs (sbitmap, sbitmap *, int);
	168	extern void sbitmap_intersection_of_preds (sbitmap, sbitmap *, int);
	169	extern void sbitmap_union_of_succs (sbitmap, sbitmap *, int);
	170	extern void sbitmap_union_of_preds (sbitmap, sbitmap *, int);
36349f8b	171
46c5ad27	172	extern void debug_sbitmap (sbitmap);
88657302	173	#endif /* ! GCC_SBITMAP_H */