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