bitmap.h revision 117395 
1/* Functions to support general ended bitmaps.
2   Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
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/* Fundamental storage type for bitmap.  */
26
27/* typedef unsigned HOST_WIDE_INT BITMAP_WORD; */
28/* #define nBITMAP_WORD_BITS HOST_BITS_PER_WIDE_INT */
29typedef unsigned long BITMAP_WORD;
30#define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG)
31#define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS
32
33/* Number of words to use for each element in the linked list.  */
34
35#ifndef BITMAP_ELEMENT_WORDS
36#define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS)
37#endif
38
39/* Number of bits in each actual element of a bitmap.  We get slightly better
40   code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if
41   bits is unsigned, assuming it is a power of 2.  */
42
43#define BITMAP_ELEMENT_ALL_BITS \
44  ((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS))
45
46/* Bitmap set element.  We use a linked list to hold only the bits that
47   are set.  This allows for use to grow the bitset dynamically without
48   having to realloc and copy a giant bit array.  The `prev' field is
49   undefined for an element on the free list.  */
50
51typedef struct bitmap_element_def GTY(())
52{
53  struct bitmap_element_def *next;		/* Next element.  */
54  struct bitmap_element_def *prev;		/* Previous element.  */
55  unsigned int indx;			/* regno/BITMAP_ELEMENT_ALL_BITS.  */
56  BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set.  */
57} bitmap_element;
58
59/* Head of bitmap linked list.  */
60typedef struct bitmap_head_def GTY(()) {
61  bitmap_element *first;	/* First element in linked list.  */
62  bitmap_element *current;	/* Last element looked at.  */
63  unsigned int indx;		/* Index of last element looked at.  */
64  int using_obstack;		/* Are we using an obstack or ggc for
65                                   allocation?  */
66} bitmap_head;
67typedef struct bitmap_head_def *bitmap;
68
69/* Enumeration giving the various operations we support.  */
70enum bitmap_bits {
71  BITMAP_AND,			/* TO = FROM1 & FROM2 */
72  BITMAP_AND_COMPL,		/* TO = FROM1 & ~ FROM2 */
73  BITMAP_IOR,			/* TO = FROM1 | FROM2 */
74  BITMAP_XOR,			/* TO = FROM1 ^ FROM2 */
75  BITMAP_IOR_COMPL			/* TO = FROM1 | ~FROM2 */
76};
77
78/* Global data */
79extern bitmap_element bitmap_zero_bits;	/* Zero bitmap element */
80
81/* Clear a bitmap by freeing up the linked list.  */
82extern void bitmap_clear PARAMS ((bitmap));
83
84/* Copy a bitmap to another bitmap.  */
85extern void bitmap_copy PARAMS ((bitmap, bitmap));
86
87/* True if two bitmaps are identical.  */
88extern int bitmap_equal_p PARAMS ((bitmap, bitmap));
89
90/* Perform an operation on two bitmaps, yielding a third.  */
91extern int bitmap_operation PARAMS ((bitmap, bitmap, bitmap, enum bitmap_bits));
92
93/* `or' into one bitmap the `and' of a second bitmap witih the complement
94   of a third.  */
95extern void bitmap_ior_and_compl PARAMS ((bitmap, bitmap, bitmap));
96
97/* Clear a single register in a register set.  */
98extern void bitmap_clear_bit PARAMS ((bitmap, int));
99
100/* Set a single register in a register set.  */
101extern void bitmap_set_bit PARAMS ((bitmap, int));
102
103/* Return true if a register is set in a register set.  */
104extern int bitmap_bit_p PARAMS ((bitmap, int));
105
106/* Debug functions to print a bitmap linked list.  */
107extern void debug_bitmap PARAMS ((bitmap));
108extern void debug_bitmap_file PARAMS ((FILE *, bitmap));
109
110/* Print a bitmap */
111extern void bitmap_print PARAMS ((FILE *, bitmap, const char *, const char *));
112
113/* Initialize a bitmap header.  If HEAD is NULL, a new header will be
114   allocated.  USING_OBSTACK indicates how elements should be allocated.  */
115extern bitmap bitmap_initialize PARAMS ((bitmap head,
116					 int using_obstack));
117
118/* Release all memory used by the bitmap obstack.  */
119extern void bitmap_release_memory PARAMS ((void));
120
121/* A few compatibility/functions macros for compatibility with sbitmaps */
122#define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
123#define bitmap_zero(a) bitmap_clear (a)
124#define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR)
125#define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND)
126extern int bitmap_union_of_diff PARAMS((bitmap, bitmap, bitmap, bitmap));
127extern int bitmap_first_set_bit PARAMS((bitmap));
128extern int bitmap_last_set_bit PARAMS((bitmap));
129
130/* Allocate a bitmap with oballoc.  */
131#define BITMAP_OBSTACK_ALLOC(OBSTACK)				\
132  bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1)
133
134/* Allocate a bitmap with ggc_alloc.  */
135#define BITMAP_GGC_ALLOC()			\
136  bitmap_initialize (NULL, 0)
137
138/* Allocate a bitmap with xmalloc.  */
139#define BITMAP_XMALLOC()                                        \
140  bitmap_initialize ((bitmap) xmalloc (sizeof (bitmap_head)), 1)
141
142/* Do any cleanup needed on a bitmap when it is no longer used.  */
143#define BITMAP_FREE(BITMAP)			\
144do {						\
145  if (BITMAP)					\
146    {						\
147      bitmap_clear (BITMAP);			\
148      (BITMAP) = 0;				\
149    }						\
150} while (0)
151
152/* Do any cleanup needed on an xmalloced bitmap when it is no longer used.  */
153#define BITMAP_XFREE(BITMAP)			\
154do {						\
155  if (BITMAP)					\
156    {						\
157      bitmap_clear (BITMAP);			\
158      free (BITMAP);				\
159      (BITMAP) = 0;				\
160    }						\
161} while (0)
162
163/* Do any one-time initializations needed for bitmaps.  */
164#define BITMAP_INIT_ONCE()
165
166/* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the
167   bit number and executing CODE for all bits that are set.  */
168
169#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE)		\
170do {									\
171  bitmap_element *ptr_ = (BITMAP)->first;				\
172  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;			\
173  unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS;				\
174  unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;	\
175									\
176									\
177  /* Find the block the minimum bit is in.  */				\
178  while (ptr_ != 0 && ptr_->indx < indx_)				\
179    ptr_ = ptr_->next;							\
180									\
181  if (ptr_ != 0 && ptr_->indx != indx_)					\
182    {									\
183      bit_num_ = 0;							\
184      word_num_ = 0;							\
185    }									\
186									\
187  for (; ptr_ != 0; ptr_ = ptr_->next)					\
188    {									\
189      for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)		\
190	{								\
191	  BITMAP_WORD word_ = ptr_->bits[word_num_];			\
192									\
193	  if (word_ != 0)						\
194	    {								\
195	      for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++)		\
196		{							\
197		  BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_;	\
198									\
199		  if ((word_ & mask_) != 0)				\
200		    {							\
201		      word_ &= ~ mask_;					\
202		      (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS  \
203				  + word_num_ * BITMAP_WORD_BITS	\
204				  + bit_num_);				\
205		      CODE;						\
206									\
207		      if (word_ == 0)					\
208			break;						\
209		    }							\
210		}							\
211	    }								\
212									\
213	  bit_num_ = 0;							\
214	}								\
215									\
216      word_num_ = 0;							\
217    }									\
218} while (0)
219
220/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
221   BITNUM to the bit number and executing CODE for all bits that are set in
222   the first bitmap and not set in the second.  */
223
224#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \
225do {									\
226  bitmap_element *ptr1_ = (BITMAP1)->first;				\
227  bitmap_element *ptr2_ = (BITMAP2)->first;				\
228  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;			\
229  unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS;				\
230  unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;	\
231									\
232  /* Find the block the minimum bit is in in the first bitmap.  */	\
233  while (ptr1_ != 0 && ptr1_->indx < indx_)				\
234    ptr1_ = ptr1_->next;						\
235									\
236  if (ptr1_ != 0 && ptr1_->indx != indx_)				\
237    {									\
238      bit_num_ = 0;							\
239      word_num_ = 0;							\
240    }									\
241									\
242  for (; ptr1_ != 0 ; ptr1_ = ptr1_->next)				\
243    {									\
244      /* Advance BITMAP2 to the equivalent link, using an all		\
245	 zero element if an equivalent link doesn't exist.  */		\
246      bitmap_element *tmp2_;						\
247									\
248      while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx)			\
249	ptr2_ = ptr2_->next;						\
250									\
251      tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx)		\
252	       ? ptr2_ : &bitmap_zero_bits); 				\
253									\
254      for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++)		\
255	{								\
256	  BITMAP_WORD word_ = (ptr1_->bits[word_num_]			\
257			       & ~ tmp2_->bits[word_num_]);		\
258	  if (word_ != 0)						\
259	    {								\
260	      for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++)		\
261		{							\
262		  BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_;	\
263									\
264		  if ((word_ & mask_) != 0)				\
265		    {							\
266		      word_ &= ~ mask_;					\
267		      (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
268				  + word_num_ * BITMAP_WORD_BITS	\
269				  + bit_num_);				\
270									\
271		      CODE;						\
272		      if (word_ == 0)					\
273			break;						\
274		    }							\
275		}							\
276	    }								\
277									\
278	  bit_num_ = 0;							\
279	}								\
280									\
281      word_num_ = 0;							\
282    }									\
283} while (0)
284
285/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
286   BITNUM to the bit number and executing CODE for all bits that are set in
287   the both bitmaps.  */
288
289#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE)	\
290do {									\
291  bitmap_element *ptr1_ = (BITMAP1)->first;				\
292  bitmap_element *ptr2_ = (BITMAP2)->first;				\
293  unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS;			\
294  unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS;				\
295  unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % 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	  BITMAP_WORD word_ = (ptr1_->bits[word_num_]			\
328			       & ptr2_->bits[word_num_]);		\
329	  if (word_ != 0)						\
330	    {								\
331	      for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++)		\
332		{							\
333		  BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_;	\
334									\
335		  if ((word_ & mask_) != 0)				\
336		    {							\
337		      word_ &= ~ mask_;					\
338		      (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
339				  + word_num_ * BITMAP_WORD_BITS	\
340				  + bit_num_);				\
341									\
342		      CODE;						\
343		      if (word_ == 0)					\
344			break;						\
345		    }							\
346		}							\
347	    }								\
348									\
349	  bit_num_ = 0;							\
350	}								\
351									\
352      word_num_ = 0;							\
353    }									\
354} while (0)
355
356#endif /* GCC_BITMAP_H */
357