]>
Commit | Line | Data |
---|---|---|
096ab9ea | 1 | /* Functions to support general ended bitmaps. |
3ef42a0c KH |
2 | Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002 |
3 | Free Software Foundation, Inc. | |
096ab9ea | 4 | |
1322177d | 5 | This file is part of GCC. |
096ab9ea | 6 | |
1322177d LB |
7 | GCC is free software; you can redistribute it and/or modify it under |
8 | the terms of the GNU General Public License as published by the Free | |
9 | Software Foundation; either version 2, or (at your option) any later | |
10 | version. | |
096ab9ea | 11 | |
1322177d LB |
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
096ab9ea RK |
16 | |
17 | You should have received a copy of the GNU General Public License | |
1322177d LB |
18 | along with GCC; see the file COPYING. If not, write to the Free |
19 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
20 | 02111-1307, USA. */ | |
096ab9ea | 21 | |
88657302 | 22 | #ifndef GCC_BITMAP_H |
ca7fd9cd | 23 | #define GCC_BITMAP_H |
a05924f9 | 24 | |
096ab9ea RK |
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 | ||
43 | typedef struct bitmap_element_def | |
44 | { | |
eebedaa5 KH |
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. */ | |
096ab9ea RK |
49 | } bitmap_element; |
50 | ||
51 | /* Head of bitmap linked list. */ | |
52 | typedef struct bitmap_head_def { | |
eebedaa5 KH |
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. */ | |
ea193996 | 56 | |
096ab9ea RK |
57 | } bitmap_head, *bitmap; |
58 | ||
59 | /* Enumeration giving the various operations we support. */ | |
60 | enum bitmap_bits { | |
61 | BITMAP_AND, /* TO = FROM1 & FROM2 */ | |
62 | BITMAP_AND_COMPL, /* TO = FROM1 & ~ FROM2 */ | |
8229306b | 63 | BITMAP_IOR, /* TO = FROM1 | FROM2 */ |
ea193996 DB |
64 | BITMAP_XOR, /* TO = FROM1 ^ FROM2 */ |
65 | BITMAP_IOR_COMPL /* TO = FROM1 | ~FROM2 */ | |
096ab9ea RK |
66 | }; |
67 | ||
68 | /* Global data */ | |
ae0ed63a | 69 | extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ |
096ab9ea RK |
70 | |
71 | /* Clear a bitmap by freeing up the linked list. */ | |
3d994c6b | 72 | extern void bitmap_clear PARAMS ((bitmap)); |
096ab9ea | 73 | |
eebedaa5 | 74 | /* Copy a bitmap to another bitmap. */ |
3d994c6b | 75 | extern void bitmap_copy PARAMS ((bitmap, bitmap)); |
096ab9ea | 76 | |
8229306b | 77 | /* True if two bitmaps are identical. */ |
3d994c6b | 78 | extern int bitmap_equal_p PARAMS ((bitmap, bitmap)); |
8229306b | 79 | |
096ab9ea | 80 | /* Perform an operation on two bitmaps, yielding a third. */ |
3d994c6b | 81 | extern int bitmap_operation PARAMS ((bitmap, bitmap, bitmap, enum bitmap_bits)); |
096ab9ea RK |
82 | |
83 | /* `or' into one bitmap the `and' of a second bitmap witih the complement | |
84 | of a third. */ | |
3d994c6b | 85 | extern void bitmap_ior_and_compl PARAMS ((bitmap, bitmap, bitmap)); |
096ab9ea RK |
86 | |
87 | /* Clear a single register in a register set. */ | |
3d994c6b | 88 | extern void bitmap_clear_bit PARAMS ((bitmap, int)); |
096ab9ea RK |
89 | |
90 | /* Set a single register in a register set. */ | |
3d994c6b | 91 | extern void bitmap_set_bit PARAMS ((bitmap, int)); |
096ab9ea RK |
92 | |
93 | /* Return true if a register is set in a register set. */ | |
3d994c6b | 94 | extern int bitmap_bit_p PARAMS ((bitmap, int)); |
096ab9ea RK |
95 | |
96 | /* Debug functions to print a bitmap linked list. */ | |
3d994c6b KG |
97 | extern void debug_bitmap PARAMS ((bitmap)); |
98 | extern void debug_bitmap_file PARAMS ((FILE *, bitmap)); | |
096ab9ea | 99 | |
22fa5b8a | 100 | /* Print a bitmap */ |
3d994c6b | 101 | extern void bitmap_print PARAMS ((FILE *, bitmap, const char *, const char *)); |
22fa5b8a | 102 | |
096ab9ea | 103 | /* Initialize a bitmap header. */ |
3d994c6b | 104 | extern bitmap bitmap_initialize PARAMS ((bitmap)); |
096ab9ea RK |
105 | |
106 | /* Release all memory held by bitmaps. */ | |
3d994c6b | 107 | extern void bitmap_release_memory PARAMS ((void)); |
096ab9ea | 108 | |
ea193996 DB |
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) | |
114 | extern int bitmap_union_of_diff PARAMS((bitmap, bitmap, bitmap, bitmap)); | |
115 | extern int bitmap_first_set_bit PARAMS((bitmap)); | |
116 | extern int bitmap_last_set_bit PARAMS((bitmap)); | |
117 | ||
096ab9ea RK |
118 | /* Allocate a bitmap with oballoc. */ |
119 | #define BITMAP_OBSTACK_ALLOC(OBSTACK) \ | |
120 | bitmap_initialize ((bitmap) obstack_alloc (OBSTACK, sizeof (bitmap_head))) | |
121 | ||
266aae9b KG |
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) \ | |
128 | do { \ | |
129 | bitmap temp_bitmap_ = (bitmap) alloca (sizeof (bitmap_head)); \ | |
130 | (PTR) = bitmap_initialize (temp_bitmap_); \ | |
131 | } while (0) | |
ca7fd9cd | 132 | |
67289ea6 MM |
133 | /* Allocate a bitmap with xmalloc. */ |
134 | #define BITMAP_XMALLOC() \ | |
135 | bitmap_initialize ((bitmap) xmalloc (sizeof (bitmap_head))) | |
136 | ||
096ab9ea | 137 | /* Do any cleanup needed on a bitmap when it is no longer used. */ |
e7749837 RH |
138 | #define BITMAP_FREE(BITMAP) \ |
139 | do { \ | |
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) \ | |
149 | do { \ | |
150 | if (BITMAP) \ | |
151 | { \ | |
152 | bitmap_clear (BITMAP); \ | |
153 | free (BITMAP); \ | |
154 | (BITMAP) = 0; \ | |
155 | } \ | |
096ab9ea RK |
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 | |
eebedaa5 | 162 | bit number and executing CODE for all bits that are set. */ |
096ab9ea RK |
163 | |
164 | #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE) \ | |
165 | do { \ | |
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 | |
eebedaa5 | 219 | the first bitmap and not set in the second. */ |
096ab9ea RK |
220 | |
221 | #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ | |
222 | do { \ | |
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 \ | |
956d6950 | 243 | zero element if an equivalent link doesn't exist. */ \ |
096ab9ea RK |
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) \ | |
ae0ed63a | 250 | ? ptr2_ : &bitmap_zero_bits); \ |
096ab9ea RK |
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) | |
22fa5b8a MM |
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 | |
eebedaa5 | 286 | the both bitmaps. */ |
22fa5b8a MM |
287 | |
288 | #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ | |
289 | do { \ | |
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 | { \ | |
3ef42a0c | 315 | /* If there are no more elements in BITMAP2, exit loop now. */ \ |
22fa5b8a MM |
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) | |
a05924f9 | 356 | |
88657302 | 357 | #endif /* GCC_BITMAP_H */ |