bitmap.h revision 90075 
1/* Functions to support general ended bitmaps.
2   Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002
3   Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING.  If not, write to the Free
19Software Foundation, 59 Temple Place - Suite 330, Boston, MA
2002111-1307, USA.  */
21
22#ifndef GCC_BITMAP_H
23#define GCC_BITMAP_H
24
25/* Number of words to use for each element in the linked list.  */
26
27#ifndef BITMAP_ELEMENT_WORDS
28#define BITMAP_ELEMENT_WORDS 2
29#endif
30
31/* Number of bits in each actual element of a bitmap.  We get slightly better
32   code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if
33   bits is unsigned, assuming it is a power of 2.  */
34
35#define BITMAP_ELEMENT_ALL_BITS \
36  ((unsigned) (BITMAP_ELEMENT_WORDS * HOST_BITS_PER_WIDE_INT))
37
38/* Bitmap set element.  We use a linked list to hold only the bits that
39   are set.  This allows for use to grow the bitset dynamically without
40   having to realloc and copy a giant bit array.  The `prev' field is
41   undefined for an element on the free list.  */
42
43typedef struct bitmap_element_def
44{
45  struct bitmap_element_def *next;		/* Next element.  */
46  struct bitmap_element_def *prev;		/* Previous element.  */
47  unsigned int indx;			/* regno/BITMAP_ELEMENT_ALL_BITS.  */
48  unsigned HOST_WIDE_INT bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set.  */
49} bitmap_element;
50
51/* Head of bitmap linked list.  */
52typedef struct bitmap_head_def {
53  bitmap_element *first;	/* First element in linked list.  */
54  bitmap_element *current;	/* Last element looked at.  */
55  unsigned int indx;		/* Index of last element looked at.  */
56
57} bitmap_head, *bitmap;
58
59/* Enumeration giving the various operations we support.  */
60enum bitmap_bits {
61  BITMAP_AND,			/* TO = FROM1 & FROM2 */
62  BITMAP_AND_COMPL,		/* TO = FROM1 & ~ FROM2 */
63  BITMAP_IOR,			/* TO = FROM1 | FROM2 */
64  BITMAP_XOR,			/* TO = FROM1 ^ FROM2 */
65  BITMAP_IOR_COMPL			/* TO = FROM1 | ~FROM2 */
66};
67
68/* Global data */
69extern bitmap_element bitmap_zero_bits;	/* Zero bitmap element */
70
71/* Clear a bitmap by freeing up the linked list.  */
72extern void bitmap_clear PARAMS ((bitmap));
73
74/* Copy a bitmap to another bitmap.  */
75extern void bitmap_copy PARAMS ((bitmap, bitmap));
76
77/* True if two bitmaps are identical.  */
78extern int bitmap_equal_p PARAMS ((bitmap, bitmap));
79
80/* Perform an operation on two bitmaps, yielding a third.  */
81extern int bitmap_operation PARAMS ((bitmap, bitmap, bitmap, enum bitmap_bits));
82
83/* `or' into one bitmap the `and' of a second bitmap witih the complement
84   of a third.  */
85extern void bitmap_ior_and_compl PARAMS ((bitmap, bitmap, bitmap));
86
87/* Clear a single register in a register set.  */
88extern void bitmap_clear_bit PARAMS ((bitmap, int));
89
90/* Set a single register in a register set.  */
91extern void bitmap_set_bit PARAMS ((bitmap, int));
92
93/* Return true if a register is set in a register set.  */
94extern int bitmap_bit_p PARAMS ((bitmap, int));
95
96/* Debug functions to print a bitmap linked list.  */
97extern void debug_bitmap PARAMS ((bitmap));
98extern void debug_bitmap_file PARAMS ((FILE *, bitmap));
99
100/* Print a bitmap */
101extern void bitmap_print PARAMS ((FILE *, bitmap, const char *, const char *));
102
103/* Initialize a bitmap header.  */
104extern bitmap bitmap_initialize PARAMS ((bitmap));
105
106/* Release all memory held by bitmaps.  */
107extern void bitmap_release_memory PARAMS ((void));
108
109/* A few compatibility/functions macros for compatibility with sbitmaps */
110#define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
111#define bitmap_zero(a) bitmap_clear (a)
112#define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR)
113#define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND)
114extern int bitmap_union_of_diff PARAMS((bitmap, bitmap, bitmap, bitmap));
115extern int bitmap_first_set_bit PARAMS((bitmap));
116extern int bitmap_last_set_bit PARAMS((bitmap));
117
118/* Allocate a bitmap with oballoc.  */
119#define BITMAP_OBSTACK_ALLOC(OBSTACK)				\
120  bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head)))
121
122/* Allocate a bitmap with alloca.  Note alloca cannot be passed as an
123   argument to a function, so we set a temporary variable to the value
124   returned by alloca and pass that variable to bitmap_initialize().
125   PTR is then set to the value returned from bitmap_initialize() to
126   avoid having it appear more than once in case it has side effects.  */
127#define BITMAP_ALLOCA(PTR) \
128do { \
129  bitmap temp_bitmap_ = (bitmap) alloca (sizeof (bitmap_head)); \
130  (PTR) = bitmap_initialize (temp_bitmap_); \
131} while (0)
132
133/* Allocate a bitmap with xmalloc.  */
134#define BITMAP_XMALLOC()                                        \
135  bitmap_initialize ((bitmap) xmalloc (sizeof (bitmap_head)))
136
137/* Do any cleanup needed on a bitmap when it is no longer used.  */
138#define BITMAP_FREE(BITMAP)			\
139do {						\
140  if (BITMAP)					\
141    {						\
142      bitmap_clear (BITMAP);			\
143      (BITMAP) = 0;				\
144    }						\
145} while (0)
146
147/* Do any cleanup needed on an xmalloced bitmap when it is no longer used.  */
148#define BITMAP_XFREE(BITMAP)			\
149do {						\
150  if (BITMAP)					\
151    {						\
152      bitmap_clear (BITMAP);			\
153      free (BITMAP);				\
154      (BITMAP) = 0;				\
155    }						\
156} while (0)
157
158/* Do any one-time initializations needed for bitmaps.  */
159#define BITMAP_INIT_ONCE()
160
161/* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the
162   bit number and executing CODE for all bits that are set.  */
163
164#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE)		\
165do {									\
166  bitmap_element *ptr_ = (BITMAP)->first;				\
167  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;			\
168  unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);	\
169  unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))	\
170			% BITMAP_ELEMENT_WORDS);			\
171									\
172									\
173  /* Find the block the minimum bit is in.  */				\
174  while (ptr_ != 0 && ptr_->indx < indx_)				\
175    ptr_ = ptr_->next;							\
176									\
177  if (ptr_ != 0 && ptr_->indx != indx_)					\
178    {									\
179      bit_num_ = 0;							\
180      word_num_ = 0;							\
181    }									\
182									\
183  for (; ptr_ != 0; ptr_ = ptr_->next)					\
184    {									\
185      for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)		\
186	{								\
187	  unsigned HOST_WIDE_INT word_ = ptr_->bits[word_num_];		\
188									\
189	  if (word_ != 0)						\
190	    {								\
191	      for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)	\
192		{							\
193		  unsigned HOST_WIDE_INT mask_				\
194		    = ((unsigned HOST_WIDE_INT) 1) << bit_num_;		\
195									\
196		  if ((word_ & mask_) != 0)				\
197		    {							\
198		      word_ &= ~ mask_;					\
199		      (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS  \
200				  + word_num_ * HOST_BITS_PER_WIDE_INT  \
201				  + bit_num_);				\
202		      CODE;						\
203									\
204		      if (word_ == 0)					\
205			break;						\
206		    }							\
207		}							\
208	    }								\
209									\
210	  bit_num_ = 0;							\
211	}								\
212									\
213      word_num_ = 0;							\
214    }									\
215} while (0)
216
217/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
218   BITNUM to the bit number and executing CODE for all bits that are set in
219   the first bitmap and not set in the second.  */
220
221#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \
222do {									\
223  bitmap_element *ptr1_ = (BITMAP1)->first;				\
224  bitmap_element *ptr2_ = (BITMAP2)->first;				\
225  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;			\
226  unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);	\
227  unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))	\
228			% BITMAP_ELEMENT_WORDS);			\
229									\
230  /* Find the block the minimum bit is in in the first bitmap.  */	\
231  while (ptr1_ != 0 && ptr1_->indx < indx_)				\
232    ptr1_ = ptr1_->next;						\
233									\
234  if (ptr1_ != 0 && ptr1_->indx != indx_)				\
235    {									\
236      bit_num_ = 0;							\
237      word_num_ = 0;							\
238    }									\
239									\
240  for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)				\
241    {									\
242      /* Advance BITMAP2 to the equivalent link, using an all		\
243	 zero element if an equivalent link doesn't exist.  */		\
244      bitmap_element *tmp2_;						\
245									\
246      while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)			\
247	ptr2_ = ptr2_->next;						\
248									\
249      tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx)		\
250	       ? ptr2_ : &bitmap_zero_bits); 				\
251									\
252      for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)		\
253	{								\
254	  unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]	\
255					  & ~ tmp2_->bits[word_num_]);	\
256	  if (word_ != 0)						\
257	    {								\
258	      for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)	\
259		{							\
260		  unsigned HOST_WIDE_INT mask_				\
261		    = ((unsigned HOST_WIDE_INT)1) << bit_num_;		\
262									\
263		  if ((word_ & mask_) != 0)				\
264		    {							\
265		      word_ &= ~ mask_;					\
266		      (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
267				  + word_num_ * HOST_BITS_PER_WIDE_INT  \
268				  + bit_num_);				\
269									\
270		      CODE;						\
271		      if (word_ == 0)					\
272			break;						\
273		    }							\
274		}							\
275	    }								\
276									\
277	  bit_num_ = 0;							\
278	}								\
279									\
280      word_num_ = 0;							\
281    }									\
282} while (0)
283
284/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
285   BITNUM to the bit number and executing CODE for all bits that are set in
286   the both bitmaps.  */
287
288#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE)	\
289do {									\
290  bitmap_element *ptr1_ = (BITMAP1)->first;				\
291  bitmap_element *ptr2_ = (BITMAP2)->first;				\
292  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;			\
293  unsigned bit_num_ = (MIN) % ((unsigned) HOST_BITS_PER_WIDE_INT);	\
294  unsigned word_num_ = (((MIN) / ((unsigned) HOST_BITS_PER_WIDE_INT))	\
295			% BITMAP_ELEMENT_WORDS);			\
296									\
297  /* Find the block the minimum bit is in in the first bitmap.  */	\
298  while (ptr1_ != 0 && ptr1_->indx < indx_)				\
299    ptr1_ = ptr1_->next;						\
300									\
301  if (ptr1_ != 0 && ptr1_->indx != indx_)				\
302    {									\
303      bit_num_ = 0;							\
304      word_num_ = 0;							\
305    }									\
306									\
307  for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)				\
308    {									\
309      /* Advance BITMAP2 to the equivalent link */			\
310      while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)			\
311	ptr2_ = ptr2_->next;						\
312									\
313      if (ptr2_ == 0)							\
314	{								\
315	  /* If there are no more elements in BITMAP2, exit loop now.  */ \
316	  ptr1_ = (bitmap_element *)0;					\
317	  break;							\
318	}								\
319      else if (ptr2_->indx > ptr1_->indx)				\
320	{								\
321	  bit_num_ = word_num_ = 0;					\
322	  continue;							\
323	}								\
324									\
325      for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)		\
326	{								\
327	  unsigned HOST_WIDE_INT word_ = (ptr1_->bits[word_num_]	\
328					  & ptr2_->bits[word_num_]);	\
329	  if (word_ != 0)						\
330	    {								\
331	      for (; bit_num_ < HOST_BITS_PER_WIDE_INT; bit_num_++)	\
332		{							\
333		  unsigned HOST_WIDE_INT mask_				\
334		    = ((unsigned HOST_WIDE_INT)1) << bit_num_;		\
335									\
336		  if ((word_ & mask_) != 0)				\
337		    {							\
338		      word_ &= ~ mask_;					\
339		      (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
340				  + word_num_ * HOST_BITS_PER_WIDE_INT  \
341				  + bit_num_);				\
342									\
343		      CODE;						\
344		      if (word_ == 0)					\
345			break;						\
346		    }							\
347		}							\
348	    }								\
349									\
350	  bit_num_ = 0;							\
351	}								\
352									\
353      word_num_ = 0;							\
354    }									\
355} while (0)
356
357#endif /* GCC_BITMAP_H */
358