]>
Commit | Line | Data |
---|---|---|
096ab9ea | 1 | /* Functions to support general ended bitmaps. |
72e42e26 | 2 | Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003 |
3ef42a0c | 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 | |
72e42e26 SB |
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 */ | |
29 | typedef unsigned long BITMAP_WORD; | |
30 | #define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG) | |
31 | #define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS | |
32 | ||
096ab9ea RK |
33 | /* Number of words to use for each element in the linked list. */ |
34 | ||
35 | #ifndef BITMAP_ELEMENT_WORDS | |
72e42e26 | 36 | #define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS) |
096ab9ea RK |
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 \ | |
72e42e26 | 44 | ((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)) |
096ab9ea RK |
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 | ||
e2500fed | 51 | typedef struct bitmap_element_def GTY(()) |
096ab9ea | 52 | { |
eebedaa5 KH |
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. */ | |
72e42e26 | 56 | BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */ |
096ab9ea RK |
57 | } bitmap_element; |
58 | ||
59 | /* Head of bitmap linked list. */ | |
e2500fed | 60 | typedef struct bitmap_head_def GTY(()) { |
eebedaa5 KH |
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. */ | |
e2500fed GK |
64 | int using_obstack; /* Are we using an obstack or ggc for |
65 | allocation? */ | |
66 | } bitmap_head; | |
67 | typedef struct bitmap_head_def *bitmap; | |
096ab9ea RK |
68 | |
69 | /* Enumeration giving the various operations we support. */ | |
70 | enum bitmap_bits { | |
71 | BITMAP_AND, /* TO = FROM1 & FROM2 */ | |
72 | BITMAP_AND_COMPL, /* TO = FROM1 & ~ FROM2 */ | |
8229306b | 73 | BITMAP_IOR, /* TO = FROM1 | FROM2 */ |
ea193996 DB |
74 | BITMAP_XOR, /* TO = FROM1 ^ FROM2 */ |
75 | BITMAP_IOR_COMPL /* TO = FROM1 | ~FROM2 */ | |
096ab9ea RK |
76 | }; |
77 | ||
78 | /* Global data */ | |
ae0ed63a | 79 | extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ |
096ab9ea RK |
80 | |
81 | /* Clear a bitmap by freeing up the linked list. */ | |
4682ae04 | 82 | extern void bitmap_clear (bitmap); |
096ab9ea | 83 | |
eebedaa5 | 84 | /* Copy a bitmap to another bitmap. */ |
4682ae04 | 85 | extern void bitmap_copy (bitmap, bitmap); |
096ab9ea | 86 | |
8229306b | 87 | /* True if two bitmaps are identical. */ |
4682ae04 | 88 | extern int bitmap_equal_p (bitmap, bitmap); |
8229306b | 89 | |
096ab9ea | 90 | /* Perform an operation on two bitmaps, yielding a third. */ |
4682ae04 | 91 | extern int bitmap_operation (bitmap, bitmap, bitmap, enum bitmap_bits); |
096ab9ea RK |
92 | |
93 | /* `or' into one bitmap the `and' of a second bitmap witih the complement | |
94 | of a third. */ | |
4682ae04 | 95 | extern void bitmap_ior_and_compl (bitmap, bitmap, bitmap); |
096ab9ea RK |
96 | |
97 | /* Clear a single register in a register set. */ | |
4682ae04 | 98 | extern void bitmap_clear_bit (bitmap, int); |
096ab9ea RK |
99 | |
100 | /* Set a single register in a register set. */ | |
4682ae04 | 101 | extern void bitmap_set_bit (bitmap, int); |
096ab9ea RK |
102 | |
103 | /* Return true if a register is set in a register set. */ | |
4682ae04 | 104 | extern int bitmap_bit_p (bitmap, int); |
096ab9ea RK |
105 | |
106 | /* Debug functions to print a bitmap linked list. */ | |
4682ae04 AJ |
107 | extern void debug_bitmap (bitmap); |
108 | extern void debug_bitmap_file (FILE *, bitmap); | |
096ab9ea | 109 | |
f9da5064 | 110 | /* Print a bitmap. */ |
4682ae04 | 111 | extern void bitmap_print (FILE *, bitmap, const char *, const char *); |
22fa5b8a | 112 | |
e2500fed GK |
113 | /* Initialize a bitmap header. If HEAD is NULL, a new header will be |
114 | allocated. USING_OBSTACK indicates how elements should be allocated. */ | |
4682ae04 | 115 | extern bitmap bitmap_initialize (bitmap head, int using_obstack); |
096ab9ea | 116 | |
e2500fed | 117 | /* Release all memory used by the bitmap obstack. */ |
4682ae04 | 118 | extern void bitmap_release_memory (void); |
096ab9ea | 119 | |
ea193996 DB |
120 | /* A few compatibility/functions macros for compatibility with sbitmaps */ |
121 | #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n") | |
122 | #define bitmap_zero(a) bitmap_clear (a) | |
123 | #define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR) | |
124 | #define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND) | |
4682ae04 AJ |
125 | extern int bitmap_union_of_diff (bitmap, bitmap, bitmap, bitmap); |
126 | extern int bitmap_first_set_bit (bitmap); | |
127 | extern int bitmap_last_set_bit (bitmap); | |
ea193996 | 128 | |
096ab9ea RK |
129 | /* Allocate a bitmap with oballoc. */ |
130 | #define BITMAP_OBSTACK_ALLOC(OBSTACK) \ | |
703ad42b | 131 | bitmap_initialize (obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1) |
e2500fed GK |
132 | |
133 | /* Allocate a bitmap with ggc_alloc. */ | |
134 | #define BITMAP_GGC_ALLOC() \ | |
135 | bitmap_initialize (NULL, 0) | |
ca7fd9cd | 136 | |
67289ea6 MM |
137 | /* Allocate a bitmap with xmalloc. */ |
138 | #define BITMAP_XMALLOC() \ | |
703ad42b | 139 | bitmap_initialize (xmalloc (sizeof (bitmap_head)), 1) |
67289ea6 | 140 | |
096ab9ea | 141 | /* Do any cleanup needed on a bitmap when it is no longer used. */ |
e7749837 RH |
142 | #define BITMAP_FREE(BITMAP) \ |
143 | do { \ | |
144 | if (BITMAP) \ | |
145 | { \ | |
146 | bitmap_clear (BITMAP); \ | |
147 | (BITMAP) = 0; \ | |
148 | } \ | |
149 | } while (0) | |
150 | ||
151 | /* Do any cleanup needed on an xmalloced bitmap when it is no longer used. */ | |
152 | #define BITMAP_XFREE(BITMAP) \ | |
153 | do { \ | |
154 | if (BITMAP) \ | |
155 | { \ | |
156 | bitmap_clear (BITMAP); \ | |
157 | free (BITMAP); \ | |
158 | (BITMAP) = 0; \ | |
159 | } \ | |
096ab9ea RK |
160 | } while (0) |
161 | ||
162 | /* Do any one-time initializations needed for bitmaps. */ | |
163 | #define BITMAP_INIT_ONCE() | |
164 | ||
165 | /* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the | |
eebedaa5 | 166 | bit number and executing CODE for all bits that are set. */ |
096ab9ea RK |
167 | |
168 | #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE) \ | |
169 | do { \ | |
170 | bitmap_element *ptr_ = (BITMAP)->first; \ | |
171 | unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ | |
72e42e26 SB |
172 | unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ |
173 | unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ | |
096ab9ea RK |
174 | \ |
175 | \ | |
176 | /* Find the block the minimum bit is in. */ \ | |
177 | while (ptr_ != 0 && ptr_->indx < indx_) \ | |
178 | ptr_ = ptr_->next; \ | |
179 | \ | |
180 | if (ptr_ != 0 && ptr_->indx != indx_) \ | |
181 | { \ | |
182 | bit_num_ = 0; \ | |
183 | word_num_ = 0; \ | |
184 | } \ | |
185 | \ | |
186 | for (; ptr_ != 0; ptr_ = ptr_->next) \ | |
187 | { \ | |
188 | for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ | |
189 | { \ | |
72e42e26 | 190 | BITMAP_WORD word_ = ptr_->bits[word_num_]; \ |
096ab9ea RK |
191 | \ |
192 | if (word_ != 0) \ | |
193 | { \ | |
72e42e26 | 194 | for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ |
096ab9ea | 195 | { \ |
72e42e26 | 196 | BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ |
096ab9ea RK |
197 | \ |
198 | if ((word_ & mask_) != 0) \ | |
199 | { \ | |
200 | word_ &= ~ mask_; \ | |
201 | (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS \ | |
72e42e26 | 202 | + word_num_ * BITMAP_WORD_BITS \ |
096ab9ea RK |
203 | + bit_num_); \ |
204 | CODE; \ | |
205 | \ | |
206 | if (word_ == 0) \ | |
207 | break; \ | |
208 | } \ | |
209 | } \ | |
210 | } \ | |
211 | \ | |
212 | bit_num_ = 0; \ | |
213 | } \ | |
214 | \ | |
215 | word_num_ = 0; \ | |
216 | } \ | |
217 | } while (0) | |
218 | ||
219 | /* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting | |
220 | BITNUM to the bit number and executing CODE for all bits that are set in | |
eebedaa5 | 221 | the first bitmap and not set in the second. */ |
096ab9ea RK |
222 | |
223 | #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \ | |
224 | do { \ | |
225 | bitmap_element *ptr1_ = (BITMAP1)->first; \ | |
226 | bitmap_element *ptr2_ = (BITMAP2)->first; \ | |
227 | unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \ | |
72e42e26 SB |
228 | unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ |
229 | unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ | |
096ab9ea RK |
230 | \ |
231 | /* Find the block the minimum bit is in in the first bitmap. */ \ | |
232 | while (ptr1_ != 0 && ptr1_->indx < indx_) \ | |
233 | ptr1_ = ptr1_->next; \ | |
234 | \ | |
235 | if (ptr1_ != 0 && ptr1_->indx != indx_) \ | |
236 | { \ | |
237 | bit_num_ = 0; \ | |
238 | word_num_ = 0; \ | |
239 | } \ | |
240 | \ | |
241 | for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ | |
242 | { \ | |
243 | /* Advance BITMAP2 to the equivalent link, using an all \ | |
956d6950 | 244 | zero element if an equivalent link doesn't exist. */ \ |
096ab9ea RK |
245 | bitmap_element *tmp2_; \ |
246 | \ | |
247 | while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ | |
248 | ptr2_ = ptr2_->next; \ | |
249 | \ | |
250 | tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx) \ | |
4682ae04 | 251 | ? ptr2_ : &bitmap_zero_bits); \ |
096ab9ea RK |
252 | \ |
253 | for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ | |
254 | { \ | |
72e42e26 SB |
255 | BITMAP_WORD word_ = (ptr1_->bits[word_num_] \ |
256 | & ~ tmp2_->bits[word_num_]); \ | |
096ab9ea RK |
257 | if (word_ != 0) \ |
258 | { \ | |
72e42e26 | 259 | for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ |
096ab9ea | 260 | { \ |
72e42e26 | 261 | BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ |
096ab9ea RK |
262 | \ |
263 | if ((word_ & mask_) != 0) \ | |
264 | { \ | |
265 | word_ &= ~ mask_; \ | |
266 | (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ | |
72e42e26 | 267 | + word_num_ * BITMAP_WORD_BITS \ |
096ab9ea RK |
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; \ | |
72e42e26 SB |
293 | unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \ |
294 | unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \ | |
22fa5b8a MM |
295 | \ |
296 | /* Find the block the minimum bit is in in the first bitmap. */ \ | |
297 | while (ptr1_ != 0 && ptr1_->indx < indx_) \ | |
298 | ptr1_ = ptr1_->next; \ | |
299 | \ | |
300 | if (ptr1_ != 0 && ptr1_->indx != indx_) \ | |
301 | { \ | |
302 | bit_num_ = 0; \ | |
303 | word_num_ = 0; \ | |
304 | } \ | |
305 | \ | |
306 | for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \ | |
307 | { \ | |
6614fd40 | 308 | /* Advance BITMAP2 to the equivalent link. */ \ |
22fa5b8a MM |
309 | while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \ |
310 | ptr2_ = ptr2_->next; \ | |
311 | \ | |
312 | if (ptr2_ == 0) \ | |
313 | { \ | |
3ef42a0c | 314 | /* If there are no more elements in BITMAP2, exit loop now. */ \ |
22fa5b8a MM |
315 | ptr1_ = (bitmap_element *)0; \ |
316 | break; \ | |
317 | } \ | |
318 | else if (ptr2_->indx > ptr1_->indx) \ | |
319 | { \ | |
320 | bit_num_ = word_num_ = 0; \ | |
321 | continue; \ | |
322 | } \ | |
323 | \ | |
324 | for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \ | |
325 | { \ | |
72e42e26 SB |
326 | BITMAP_WORD word_ = (ptr1_->bits[word_num_] \ |
327 | & ptr2_->bits[word_num_]); \ | |
22fa5b8a MM |
328 | if (word_ != 0) \ |
329 | { \ | |
72e42e26 | 330 | for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \ |
22fa5b8a | 331 | { \ |
72e42e26 | 332 | BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \ |
22fa5b8a MM |
333 | \ |
334 | if ((word_ & mask_) != 0) \ | |
335 | { \ | |
336 | word_ &= ~ mask_; \ | |
337 | (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \ | |
72e42e26 | 338 | + word_num_ * BITMAP_WORD_BITS \ |
22fa5b8a MM |
339 | + bit_num_); \ |
340 | \ | |
341 | CODE; \ | |
342 | if (word_ == 0) \ | |
343 | break; \ | |
344 | } \ | |
345 | } \ | |
346 | } \ | |
347 | \ | |
348 | bit_num_ = 0; \ | |
349 | } \ | |
350 | \ | |
351 | word_num_ = 0; \ | |
352 | } \ | |
353 | } while (0) | |
a05924f9 | 354 | |
88657302 | 355 | #endif /* GCC_BITMAP_H */ |