]>
Commit | Line | Data |
---|---|---|
2f925a60 | 1 | /* Functions to support general ended bitmaps. |
d353bf18 | 2 | Copyright (C) 1997-2015 Free Software Foundation, Inc. |
2f925a60 | 3 | |
f12b58b3 | 4 | This file is part of GCC. |
2f925a60 | 5 | |
f12b58b3 | 6 | GCC is free software; you can redistribute it and/or modify it under |
7 | the terms of the GNU General Public License as published by the Free | |
8c4c00c1 | 8 | Software Foundation; either version 3, or (at your option) any later |
f12b58b3 | 9 | version. |
2f925a60 | 10 | |
f12b58b3 | 11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
12 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
2f925a60 | 15 | |
16 | You should have received a copy of the GNU General Public License | |
8c4c00c1 | 17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
2f925a60 | 19 | |
2f925a60 | 20 | #include "config.h" |
405711de | 21 | #include "system.h" |
805e22b2 | 22 | #include "coretypes.h" |
2f925a60 | 23 | #include "obstack.h" |
d6cb6164 | 24 | #include "bitmap.h" |
f65ffe0d | 25 | |
0ff42de5 | 26 | /* Memory allocation statistics purpose instance. */ |
27 | mem_alloc_description<bitmap_usage> bitmap_mem_desc; | |
f65ffe0d | 28 | |
29 | /* Register new bitmap. */ | |
30 | void | |
31 | bitmap_register (bitmap b MEM_STAT_DECL) | |
32 | { | |
a80feb6c | 33 | bitmap_mem_desc.register_descriptor (b, BITMAP_ORIGIN, false |
34 | FINAL_PASS_MEM_STAT); | |
f65ffe0d | 35 | } |
36 | ||
37 | /* Account the overhead. */ | |
38 | static void | |
39 | register_overhead (bitmap b, int amount) | |
40 | { | |
0ff42de5 | 41 | if (bitmap_mem_desc.contains_descriptor_for_instance (b)) |
42 | bitmap_mem_desc.register_instance_overhead (amount, b); | |
f65ffe0d | 43 | } |
2f925a60 | 44 | |
2f925a60 | 45 | /* Global data */ |
42fe97ed | 46 | bitmap_element bitmap_zero_bits; /* An element of all zero bits. */ |
47 | bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */ | |
fd6481cf | 48 | static int bitmap_default_obstack_depth; |
42fe97ed | 49 | static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of |
50 | GC'd elements. */ | |
2f925a60 | 51 | |
aecda0d6 | 52 | static void bitmap_elem_to_freelist (bitmap, bitmap_element *); |
53 | static void bitmap_element_free (bitmap, bitmap_element *); | |
54 | static bitmap_element *bitmap_element_allocate (bitmap); | |
056755a1 | 55 | static int bitmap_element_zerop (const bitmap_element *); |
aecda0d6 | 56 | static void bitmap_element_link (bitmap, bitmap_element *); |
5669bd62 | 57 | static bitmap_element *bitmap_elt_insert_after (bitmap, bitmap_element *, unsigned int); |
b6e72c17 | 58 | static void bitmap_elt_clear_from (bitmap, bitmap_element *); |
aecda0d6 | 59 | static bitmap_element *bitmap_find_bit (bitmap, unsigned int); |
2f925a60 | 60 | \f |
b6e72c17 | 61 | |
1f3233d1 | 62 | /* Add ELEM to the appropriate freelist. */ |
702216e3 | 63 | static inline void |
aecda0d6 | 64 | bitmap_elem_to_freelist (bitmap head, bitmap_element *elt) |
1f3233d1 | 65 | { |
42fe97ed | 66 | bitmap_obstack *bit_obstack = head->obstack; |
a0c938f0 | 67 | |
4bc590db | 68 | elt->next = NULL; |
42fe97ed | 69 | if (bit_obstack) |
1f3233d1 | 70 | { |
4bc590db | 71 | elt->prev = bit_obstack->elements; |
42fe97ed | 72 | bit_obstack->elements = elt; |
1f3233d1 | 73 | } |
74 | else | |
75 | { | |
4bc590db | 76 | elt->prev = bitmap_ggc_free; |
1f3233d1 | 77 | bitmap_ggc_free = elt; |
78 | } | |
79 | } | |
80 | ||
ca2968e9 | 81 | /* Free a bitmap element. Since these are allocated off the |
82 | bitmap_obstack, "free" actually means "put onto the freelist". */ | |
2f925a60 | 83 | |
702216e3 | 84 | static inline void |
aecda0d6 | 85 | bitmap_element_free (bitmap head, bitmap_element *elt) |
2f925a60 | 86 | { |
87 | bitmap_element *next = elt->next; | |
88 | bitmap_element *prev = elt->prev; | |
89 | ||
90 | if (prev) | |
91 | prev->next = next; | |
92 | ||
93 | if (next) | |
94 | next->prev = prev; | |
95 | ||
96 | if (head->first == elt) | |
97 | head->first = next; | |
98 | ||
99 | /* Since the first thing we try is to insert before current, | |
100 | make current the next entry in preference to the previous. */ | |
101 | if (head->current == elt) | |
8cbee12e | 102 | { |
103 | head->current = next != 0 ? next : prev; | |
104 | if (head->current) | |
105 | head->indx = head->current->indx; | |
a0c938f0 | 106 | else |
5669bd62 | 107 | head->indx = 0; |
8cbee12e | 108 | } |
ecd52ea9 | 109 | |
110 | if (GATHER_STATISTICS) | |
111 | register_overhead (head, -((int)sizeof (bitmap_element))); | |
112 | ||
1f3233d1 | 113 | bitmap_elem_to_freelist (head, elt); |
2f925a60 | 114 | } |
115 | \f | |
116 | /* Allocate a bitmap element. The bits are cleared, but nothing else is. */ | |
117 | ||
702216e3 | 118 | static inline bitmap_element * |
aecda0d6 | 119 | bitmap_element_allocate (bitmap head) |
2f925a60 | 120 | { |
121 | bitmap_element *element; | |
42fe97ed | 122 | bitmap_obstack *bit_obstack = head->obstack; |
a0c938f0 | 123 | |
42fe97ed | 124 | if (bit_obstack) |
23ec99a1 | 125 | { |
42fe97ed | 126 | element = bit_obstack->elements; |
a0c938f0 | 127 | |
42fe97ed | 128 | if (element) |
4bc590db | 129 | /* Use up the inner list first before looking at the next |
130 | element of the outer list. */ | |
131 | if (element->next) | |
132 | { | |
133 | bit_obstack->elements = element->next; | |
134 | bit_obstack->elements->prev = element->prev; | |
135 | } | |
136 | else | |
137 | /* Inner list was just a singleton. */ | |
138 | bit_obstack->elements = element->prev; | |
1f3233d1 | 139 | else |
42fe97ed | 140 | element = XOBNEW (&bit_obstack->obstack, bitmap_element); |
1f3233d1 | 141 | } |
142 | else | |
143 | { | |
42fe97ed | 144 | element = bitmap_ggc_free; |
145 | if (element) | |
4bc590db | 146 | /* Use up the inner list first before looking at the next |
147 | element of the outer list. */ | |
148 | if (element->next) | |
149 | { | |
150 | bitmap_ggc_free = element->next; | |
151 | bitmap_ggc_free->prev = element->prev; | |
152 | } | |
153 | else | |
154 | /* Inner list was just a singleton. */ | |
155 | bitmap_ggc_free = element->prev; | |
1f3233d1 | 156 | else |
25a27413 | 157 | element = ggc_alloc<bitmap_element> (); |
23ec99a1 | 158 | } |
2f925a60 | 159 | |
ecd52ea9 | 160 | if (GATHER_STATISTICS) |
161 | register_overhead (head, sizeof (bitmap_element)); | |
162 | ||
ca2968e9 | 163 | memset (element->bits, 0, sizeof (element->bits)); |
2f925a60 | 164 | |
165 | return element; | |
166 | } | |
167 | ||
42fe97ed | 168 | /* Remove ELT and all following elements from bitmap HEAD. */ |
114c7df6 | 169 | |
170 | void | |
42fe97ed | 171 | bitmap_elt_clear_from (bitmap head, bitmap_element *elt) |
172 | { | |
4bc590db | 173 | bitmap_element *prev; |
174 | bitmap_obstack *bit_obstack = head->obstack; | |
175 | ||
176 | if (!elt) return; | |
ecd52ea9 | 177 | |
178 | if (GATHER_STATISTICS) | |
179 | { | |
180 | int n = 0; | |
181 | for (prev = elt; prev; prev = prev->next) | |
182 | n++; | |
183 | register_overhead (head, -sizeof (bitmap_element) * n); | |
184 | } | |
42fe97ed | 185 | |
4bc590db | 186 | prev = elt->prev; |
187 | if (prev) | |
188 | { | |
189 | prev->next = NULL; | |
190 | if (head->current->indx > prev->indx) | |
191 | { | |
192 | head->current = prev; | |
193 | head->indx = prev->indx; | |
194 | } | |
a0c938f0 | 195 | } |
4bc590db | 196 | else |
197 | { | |
198 | head->first = NULL; | |
199 | head->current = NULL; | |
200 | head->indx = 0; | |
201 | } | |
202 | ||
a0c938f0 | 203 | /* Put the entire list onto the free list in one operation. */ |
4bc590db | 204 | if (bit_obstack) |
42fe97ed | 205 | { |
a0c938f0 | 206 | elt->prev = bit_obstack->elements; |
4bc590db | 207 | bit_obstack->elements = elt; |
208 | } | |
209 | else | |
210 | { | |
211 | elt->prev = bitmap_ggc_free; | |
212 | bitmap_ggc_free = elt; | |
42fe97ed | 213 | } |
214 | } | |
215 | ||
216 | /* Clear a bitmap by freeing the linked list. */ | |
217 | ||
c623bf22 | 218 | void |
42fe97ed | 219 | bitmap_clear (bitmap head) |
114c7df6 | 220 | { |
4bc590db | 221 | if (head->first) |
222 | bitmap_elt_clear_from (head, head->first); | |
42fe97ed | 223 | } |
224 | \f | |
225 | /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize | |
226 | the default bitmap obstack. */ | |
227 | ||
228 | void | |
229 | bitmap_obstack_initialize (bitmap_obstack *bit_obstack) | |
230 | { | |
231 | if (!bit_obstack) | |
fd6481cf | 232 | { |
233 | if (bitmap_default_obstack_depth++) | |
234 | return; | |
235 | bit_obstack = &bitmap_default_obstack; | |
236 | } | |
42fe97ed | 237 | |
238 | #if !defined(__GNUC__) || (__GNUC__ < 2) | |
239 | #define __alignof__(type) 0 | |
240 | #endif | |
241 | ||
242 | bit_obstack->elements = NULL; | |
243 | bit_obstack->heads = NULL; | |
244 | obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE, | |
245 | __alignof__ (bitmap_element), | |
246 | obstack_chunk_alloc, | |
247 | obstack_chunk_free); | |
114c7df6 | 248 | } |
249 | ||
42fe97ed | 250 | /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, |
251 | release the default bitmap obstack. */ | |
252 | ||
253 | void | |
254 | bitmap_obstack_release (bitmap_obstack *bit_obstack) | |
255 | { | |
256 | if (!bit_obstack) | |
fd6481cf | 257 | { |
258 | if (--bitmap_default_obstack_depth) | |
259 | { | |
260 | gcc_assert (bitmap_default_obstack_depth > 0); | |
261 | return; | |
262 | } | |
263 | bit_obstack = &bitmap_default_obstack; | |
264 | } | |
a0c938f0 | 265 | |
42fe97ed | 266 | bit_obstack->elements = NULL; |
267 | bit_obstack->heads = NULL; | |
268 | obstack_free (&bit_obstack->obstack, NULL); | |
269 | } | |
270 | ||
271 | /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create | |
272 | it on the default bitmap obstack. */ | |
273 | ||
274 | bitmap | |
f65ffe0d | 275 | bitmap_obstack_alloc_stat (bitmap_obstack *bit_obstack MEM_STAT_DECL) |
42fe97ed | 276 | { |
277 | bitmap map; | |
278 | ||
279 | if (!bit_obstack) | |
280 | bit_obstack = &bitmap_default_obstack; | |
281 | map = bit_obstack->heads; | |
282 | if (map) | |
b3e7c666 | 283 | bit_obstack->heads = (struct bitmap_head *) map->first; |
42fe97ed | 284 | else |
285 | map = XOBNEW (&bit_obstack->obstack, bitmap_head); | |
f65ffe0d | 286 | bitmap_initialize_stat (map, bit_obstack PASS_MEM_STAT); |
ecd52ea9 | 287 | |
288 | if (GATHER_STATISTICS) | |
289 | register_overhead (map, sizeof (bitmap_head)); | |
42fe97ed | 290 | |
291 | return map; | |
292 | } | |
293 | ||
294 | /* Create a new GCd bitmap. */ | |
295 | ||
296 | bitmap | |
f65ffe0d | 297 | bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL) |
42fe97ed | 298 | { |
299 | bitmap map; | |
300 | ||
25a27413 | 301 | map = ggc_alloc<bitmap_head> (); |
f65ffe0d | 302 | bitmap_initialize_stat (map, NULL PASS_MEM_STAT); |
ecd52ea9 | 303 | |
304 | if (GATHER_STATISTICS) | |
305 | register_overhead (map, sizeof (bitmap_head)); | |
42fe97ed | 306 | |
307 | return map; | |
308 | } | |
309 | ||
42fe97ed | 310 | /* Release an obstack allocated bitmap. */ |
311 | ||
312 | void | |
313 | bitmap_obstack_free (bitmap map) | |
314 | { | |
0e06d11a | 315 | if (map) |
316 | { | |
317 | bitmap_clear (map); | |
76cd80c7 | 318 | map->first = (bitmap_element *) map->obstack->heads; |
ecd52ea9 | 319 | |
320 | if (GATHER_STATISTICS) | |
321 | register_overhead (map, -((int)sizeof (bitmap_head))); | |
322 | ||
0e06d11a | 323 | map->obstack->heads = map; |
324 | } | |
42fe97ed | 325 | } |
326 | ||
42fe97ed | 327 | \f |
2f925a60 | 328 | /* Return nonzero if all bits in an element are zero. */ |
329 | ||
702216e3 | 330 | static inline int |
056755a1 | 331 | bitmap_element_zerop (const bitmap_element *element) |
2f925a60 | 332 | { |
333 | #if BITMAP_ELEMENT_WORDS == 2 | |
334 | return (element->bits[0] | element->bits[1]) == 0; | |
335 | #else | |
84199e4b | 336 | unsigned i; |
2f925a60 | 337 | |
338 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
339 | if (element->bits[i] != 0) | |
340 | return 0; | |
341 | ||
342 | return 1; | |
343 | #endif | |
344 | } | |
345 | \f | |
346 | /* Link the bitmap element into the current bitmap linked list. */ | |
347 | ||
702216e3 | 348 | static inline void |
aecda0d6 | 349 | bitmap_element_link (bitmap head, bitmap_element *element) |
2f925a60 | 350 | { |
351 | unsigned int indx = element->indx; | |
352 | bitmap_element *ptr; | |
353 | ||
354 | /* If this is the first and only element, set it in. */ | |
355 | if (head->first == 0) | |
356 | { | |
357 | element->next = element->prev = 0; | |
358 | head->first = element; | |
359 | } | |
360 | ||
361 | /* If this index is less than that of the current element, it goes someplace | |
362 | before the current element. */ | |
363 | else if (indx < head->indx) | |
364 | { | |
365 | for (ptr = head->current; | |
366 | ptr->prev != 0 && ptr->prev->indx > indx; | |
367 | ptr = ptr->prev) | |
368 | ; | |
369 | ||
370 | if (ptr->prev) | |
371 | ptr->prev->next = element; | |
372 | else | |
373 | head->first = element; | |
374 | ||
375 | element->prev = ptr->prev; | |
376 | element->next = ptr; | |
377 | ptr->prev = element; | |
378 | } | |
379 | ||
380 | /* Otherwise, it must go someplace after the current element. */ | |
381 | else | |
382 | { | |
383 | for (ptr = head->current; | |
384 | ptr->next != 0 && ptr->next->indx < indx; | |
385 | ptr = ptr->next) | |
386 | ; | |
387 | ||
388 | if (ptr->next) | |
389 | ptr->next->prev = element; | |
390 | ||
391 | element->next = ptr->next; | |
392 | element->prev = ptr; | |
393 | ptr->next = element; | |
394 | } | |
395 | ||
396 | /* Set up so this is the first element searched. */ | |
397 | head->current = element; | |
398 | head->indx = indx; | |
399 | } | |
b6e72c17 | 400 | |
401 | /* Insert a new uninitialized element into bitmap HEAD after element | |
402 | ELT. If ELT is NULL, insert the element at the start. Return the | |
403 | new element. */ | |
404 | ||
405 | static bitmap_element * | |
5669bd62 | 406 | bitmap_elt_insert_after (bitmap head, bitmap_element *elt, unsigned int indx) |
b6e72c17 | 407 | { |
408 | bitmap_element *node = bitmap_element_allocate (head); | |
5669bd62 | 409 | node->indx = indx; |
b6e72c17 | 410 | |
411 | if (!elt) | |
412 | { | |
413 | if (!head->current) | |
5669bd62 | 414 | { |
415 | head->current = node; | |
416 | head->indx = indx; | |
417 | } | |
b6e72c17 | 418 | node->next = head->first; |
419 | if (node->next) | |
420 | node->next->prev = node; | |
421 | head->first = node; | |
422 | node->prev = NULL; | |
423 | } | |
424 | else | |
425 | { | |
d16af188 | 426 | gcc_checking_assert (head->current); |
b6e72c17 | 427 | node->next = elt->next; |
428 | if (node->next) | |
429 | node->next->prev = node; | |
430 | elt->next = node; | |
431 | node->prev = elt; | |
432 | } | |
433 | return node; | |
434 | } | |
2f925a60 | 435 | \f |
ca2968e9 | 436 | /* Copy a bitmap to another bitmap. */ |
2f925a60 | 437 | |
438 | void | |
056755a1 | 439 | bitmap_copy (bitmap to, const_bitmap from) |
2f925a60 | 440 | { |
056755a1 | 441 | const bitmap_element *from_ptr; |
442 | bitmap_element *to_ptr = 0; | |
2f925a60 | 443 | |
444 | bitmap_clear (to); | |
445 | ||
2358393e | 446 | /* Copy elements in forward direction one at a time. */ |
2f925a60 | 447 | for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) |
448 | { | |
1f3233d1 | 449 | bitmap_element *to_elt = bitmap_element_allocate (to); |
2f925a60 | 450 | |
451 | to_elt->indx = from_ptr->indx; | |
3c47d200 | 452 | memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits)); |
2f925a60 | 453 | |
454 | /* Here we have a special case of bitmap_element_link, for the case | |
455 | where we know the links are being entered in sequence. */ | |
456 | if (to_ptr == 0) | |
457 | { | |
458 | to->first = to->current = to_elt; | |
459 | to->indx = from_ptr->indx; | |
460 | to_elt->next = to_elt->prev = 0; | |
461 | } | |
462 | else | |
463 | { | |
464 | to_elt->prev = to_ptr; | |
465 | to_elt->next = 0; | |
466 | to_ptr->next = to_elt; | |
467 | } | |
468 | ||
469 | to_ptr = to_elt; | |
470 | } | |
471 | } | |
472 | \f | |
473 | /* Find a bitmap element that would hold a bitmap's bit. | |
474 | Update the `current' field even if we can't find an element that | |
475 | would hold the bitmap's bit to make eventual allocation | |
476 | faster. */ | |
477 | ||
702216e3 | 478 | static inline bitmap_element * |
aecda0d6 | 479 | bitmap_find_bit (bitmap head, unsigned int bit) |
2f925a60 | 480 | { |
481 | bitmap_element *element; | |
e5c8f082 | 482 | unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; |
2f925a60 | 483 | |
28d3effc | 484 | if (head->current == NULL |
9a3823f4 | 485 | || head->indx == indx) |
486 | return head->current; | |
28d3effc | 487 | if (head->current == head->first |
488 | && head->first->next == NULL) | |
489 | return NULL; | |
ecd52ea9 | 490 | |
0ff42de5 | 491 | /* Usage can be NULL due to allocated bitmaps for which we do not |
492 | call initialize function. */ | |
493 | bitmap_usage *usage = bitmap_mem_desc.get_descriptor_for_instance (head); | |
494 | ||
28d3effc | 495 | /* This bitmap has more than one element, and we're going to look |
496 | through the elements list. Count that as a search. */ | |
0ff42de5 | 497 | if (GATHER_STATISTICS && usage) |
498 | usage->m_nsearches++; | |
2f925a60 | 499 | |
4afe5544 | 500 | if (head->indx < indx) |
501 | /* INDX is beyond head->indx. Search from head->current | |
502 | forward. */ | |
503 | for (element = head->current; | |
504 | element->next != 0 && element->indx < indx; | |
505 | element = element->next) | |
ecd52ea9 | 506 | { |
0ff42de5 | 507 | if (GATHER_STATISTICS && usage) |
508 | usage->m_search_iter++; | |
ecd52ea9 | 509 | } |
4afe5544 | 510 | |
511 | else if (head->indx / 2 < indx) | |
512 | /* INDX is less than head->indx and closer to head->indx than to | |
513 | 0. Search from head->current backward. */ | |
2f925a60 | 514 | for (element = head->current; |
515 | element->prev != 0 && element->indx > indx; | |
516 | element = element->prev) | |
ecd52ea9 | 517 | { |
0ff42de5 | 518 | if (GATHER_STATISTICS && usage) |
519 | usage->m_search_iter++; | |
ecd52ea9 | 520 | } |
2f925a60 | 521 | |
522 | else | |
4afe5544 | 523 | /* INDX is less than head->indx and closer to 0 than to |
524 | head->indx. Search from head->first forward. */ | |
525 | for (element = head->first; | |
2f925a60 | 526 | element->next != 0 && element->indx < indx; |
527 | element = element->next) | |
0ff42de5 | 528 | if (GATHER_STATISTICS && usage) |
ecd52ea9 | 529 | { |
0ff42de5 | 530 | usage->m_search_iter++; |
ecd52ea9 | 531 | } |
2f925a60 | 532 | |
533 | /* `element' is the nearest to the one we want. If it's not the one we | |
534 | want, the one we want doesn't exist. */ | |
535 | head->current = element; | |
536 | head->indx = element->indx; | |
537 | if (element != 0 && element->indx != indx) | |
538 | element = 0; | |
539 | ||
540 | return element; | |
541 | } | |
542 | \f | |
b64035d2 | 543 | /* Clear a single bit in a bitmap. Return true if the bit changed. */ |
2f925a60 | 544 | |
b64035d2 | 545 | bool |
aecda0d6 | 546 | bitmap_clear_bit (bitmap head, int bit) |
2f925a60 | 547 | { |
056755a1 | 548 | bitmap_element *const ptr = bitmap_find_bit (head, bit); |
2f925a60 | 549 | |
550 | if (ptr != 0) | |
551 | { | |
e5c8f082 | 552 | unsigned bit_num = bit % BITMAP_WORD_BITS; |
553 | unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
b64035d2 | 554 | BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; |
555 | bool res = (ptr->bits[word_num] & bit_val) != 0; | |
556 | if (res) | |
a98d46f2 | 557 | { |
558 | ptr->bits[word_num] &= ~bit_val; | |
559 | /* If we cleared the entire word, free up the element. */ | |
560 | if (!ptr->bits[word_num] | |
561 | && bitmap_element_zerop (ptr)) | |
562 | bitmap_element_free (head, ptr); | |
563 | } | |
b64035d2 | 564 | |
565 | return res; | |
2f925a60 | 566 | } |
b64035d2 | 567 | |
568 | return false; | |
2f925a60 | 569 | } |
570 | ||
b64035d2 | 571 | /* Set a single bit in a bitmap. Return true if the bit changed. */ |
2f925a60 | 572 | |
b64035d2 | 573 | bool |
aecda0d6 | 574 | bitmap_set_bit (bitmap head, int bit) |
2f925a60 | 575 | { |
576 | bitmap_element *ptr = bitmap_find_bit (head, bit); | |
e5c8f082 | 577 | unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; |
578 | unsigned bit_num = bit % BITMAP_WORD_BITS; | |
579 | BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; | |
2f925a60 | 580 | |
581 | if (ptr == 0) | |
582 | { | |
1f3233d1 | 583 | ptr = bitmap_element_allocate (head); |
2f925a60 | 584 | ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; |
585 | ptr->bits[word_num] = bit_val; | |
586 | bitmap_element_link (head, ptr); | |
b64035d2 | 587 | return true; |
2f925a60 | 588 | } |
589 | else | |
b64035d2 | 590 | { |
591 | bool res = (ptr->bits[word_num] & bit_val) == 0; | |
592 | if (res) | |
593 | ptr->bits[word_num] |= bit_val; | |
594 | return res; | |
595 | } | |
2f925a60 | 596 | } |
ca2968e9 | 597 | |
2f925a60 | 598 | /* Return whether a bit is set within a bitmap. */ |
599 | ||
600 | int | |
aecda0d6 | 601 | bitmap_bit_p (bitmap head, int bit) |
2f925a60 | 602 | { |
603 | bitmap_element *ptr; | |
604 | unsigned bit_num; | |
605 | unsigned word_num; | |
606 | ||
607 | ptr = bitmap_find_bit (head, bit); | |
608 | if (ptr == 0) | |
609 | return 0; | |
610 | ||
e5c8f082 | 611 | bit_num = bit % BITMAP_WORD_BITS; |
612 | word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
2f925a60 | 613 | |
66b5ac3c | 614 | return (ptr->bits[word_num] >> bit_num) & 1; |
2f925a60 | 615 | } |
616 | \f | |
5669bd62 | 617 | #if GCC_VERSION < 3400 |
618 | /* Table of number of set bits in a character, indexed by value of char. */ | |
056755a1 | 619 | static const unsigned char popcount_table[] = |
5669bd62 | 620 | { |
621 | 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, | |
622 | 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, | |
623 | 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, | |
624 | 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, | |
625 | 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, | |
626 | 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, | |
627 | 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, | |
628 | 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8, | |
629 | }; | |
630 | ||
631 | static unsigned long | |
632 | bitmap_popcount (BITMAP_WORD a) | |
633 | { | |
634 | unsigned long ret = 0; | |
635 | unsigned i; | |
636 | ||
637 | /* Just do this the table way for now */ | |
638 | for (i = 0; i < BITMAP_WORD_BITS; i+= 8) | |
639 | ret += popcount_table[(a >> i) & 0xff]; | |
640 | return ret; | |
641 | } | |
642 | #endif | |
643 | /* Count the number of bits set in the bitmap, and return it. */ | |
644 | ||
645 | unsigned long | |
056755a1 | 646 | bitmap_count_bits (const_bitmap a) |
5669bd62 | 647 | { |
648 | unsigned long count = 0; | |
056755a1 | 649 | const bitmap_element *elt; |
5669bd62 | 650 | unsigned ix; |
651 | ||
652 | for (elt = a->first; elt; elt = elt->next) | |
653 | { | |
654 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
655 | { | |
656 | #if GCC_VERSION >= 3400 | |
657 | /* Note that popcountl matches BITMAP_WORD in type, so the actual size | |
658 | of BITMAP_WORD is not material. */ | |
659 | count += __builtin_popcountl (elt->bits[ix]); | |
660 | #else | |
a0c938f0 | 661 | count += bitmap_popcount (elt->bits[ix]); |
5669bd62 | 662 | #endif |
663 | } | |
664 | } | |
665 | return count; | |
666 | } | |
a0c938f0 | 667 | |
6bd6739a | 668 | /* Return true if the bitmap has a single bit set. Otherwise return |
669 | false. */ | |
670 | ||
671 | bool | |
672 | bitmap_single_bit_set_p (const_bitmap a) | |
673 | { | |
674 | unsigned long count = 0; | |
675 | const bitmap_element *elt; | |
676 | unsigned ix; | |
677 | ||
678 | if (bitmap_empty_p (a)) | |
679 | return false; | |
680 | ||
681 | elt = a->first; | |
682 | /* As there are no completely empty bitmap elements, a second one | |
683 | means we have more than one bit set. */ | |
684 | if (elt->next != NULL) | |
685 | return false; | |
686 | ||
687 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
688 | { | |
689 | #if GCC_VERSION >= 3400 | |
690 | /* Note that popcountl matches BITMAP_WORD in type, so the actual size | |
691 | of BITMAP_WORD is not material. */ | |
692 | count += __builtin_popcountl (elt->bits[ix]); | |
693 | #else | |
694 | count += bitmap_popcount (elt->bits[ix]); | |
695 | #endif | |
696 | if (count > 1) | |
697 | return false; | |
698 | } | |
699 | ||
700 | return count == 1; | |
701 | } | |
5669bd62 | 702 | |
703 | ||
84199e4b | 704 | /* Return the bit number of the first set bit in the bitmap. The |
705 | bitmap must be non-empty. */ | |
114c7df6 | 706 | |
84199e4b | 707 | unsigned |
056755a1 | 708 | bitmap_first_set_bit (const_bitmap a) |
114c7df6 | 709 | { |
056755a1 | 710 | const bitmap_element *elt = a->first; |
84199e4b | 711 | unsigned bit_no; |
e5c8f082 | 712 | BITMAP_WORD word; |
84199e4b | 713 | unsigned ix; |
a0c938f0 | 714 | |
d16af188 | 715 | gcc_checking_assert (elt); |
84199e4b | 716 | bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; |
717 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
718 | { | |
719 | word = elt->bits[ix]; | |
720 | if (word) | |
721 | goto found_bit; | |
722 | } | |
64db345d | 723 | gcc_unreachable (); |
84199e4b | 724 | found_bit: |
725 | bit_no += ix * BITMAP_WORD_BITS; | |
114c7df6 | 726 | |
84199e4b | 727 | #if GCC_VERSION >= 3004 |
9af5ce0c | 728 | gcc_assert (sizeof (long) == sizeof (word)); |
84199e4b | 729 | bit_no += __builtin_ctzl (word); |
114c7df6 | 730 | #else |
84199e4b | 731 | /* Binary search for the first set bit. */ |
732 | #if BITMAP_WORD_BITS > 64 | |
733 | #error "Fill out the table." | |
114c7df6 | 734 | #endif |
84199e4b | 735 | #if BITMAP_WORD_BITS > 32 |
736 | if (!(word & 0xffffffff)) | |
737 | word >>= 32, bit_no += 32; | |
114c7df6 | 738 | #endif |
84199e4b | 739 | if (!(word & 0xffff)) |
740 | word >>= 16, bit_no += 16; | |
741 | if (!(word & 0xff)) | |
742 | word >>= 8, bit_no += 8; | |
743 | if (!(word & 0xf)) | |
744 | word >>= 4, bit_no += 4; | |
745 | if (!(word & 0x3)) | |
746 | word >>= 2, bit_no += 2; | |
747 | if (!(word & 0x1)) | |
748 | word >>= 1, bit_no += 1; | |
a0c938f0 | 749 | |
d16af188 | 750 | gcc_checking_assert (word & 1); |
114c7df6 | 751 | #endif |
84199e4b | 752 | return bit_no; |
114c7df6 | 753 | } |
ffa800d1 | 754 | |
755 | /* Return the bit number of the first set bit in the bitmap. The | |
756 | bitmap must be non-empty. */ | |
757 | ||
758 | unsigned | |
759 | bitmap_last_set_bit (const_bitmap a) | |
760 | { | |
761 | const bitmap_element *elt = a->current ? a->current : a->first; | |
762 | unsigned bit_no; | |
763 | BITMAP_WORD word; | |
764 | int ix; | |
765 | ||
d16af188 | 766 | gcc_checking_assert (elt); |
ffa800d1 | 767 | while (elt->next) |
768 | elt = elt->next; | |
769 | bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; | |
770 | for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 0; ix--) | |
771 | { | |
772 | word = elt->bits[ix]; | |
773 | if (word) | |
774 | goto found_bit; | |
775 | } | |
776 | gcc_unreachable (); | |
777 | found_bit: | |
778 | bit_no += ix * BITMAP_WORD_BITS; | |
ffa800d1 | 779 | #if GCC_VERSION >= 3004 |
9af5ce0c | 780 | gcc_assert (sizeof (long) == sizeof (word)); |
7bf60644 | 781 | bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1; |
ffa800d1 | 782 | #else |
7bf60644 | 783 | /* Hopefully this is a twos-complement host... */ |
784 | BITMAP_WORD x = word; | |
785 | x |= (x >> 1); | |
786 | x |= (x >> 2); | |
787 | x |= (x >> 4); | |
788 | x |= (x >> 8); | |
789 | x |= (x >> 16); | |
ffa800d1 | 790 | #if BITMAP_WORD_BITS > 32 |
7bf60644 | 791 | x |= (x >> 32); |
ffa800d1 | 792 | #endif |
7bf60644 | 793 | bit_no += bitmap_popcount (x) - 1; |
ffa800d1 | 794 | #endif |
795 | ||
7bf60644 | 796 | return bit_no; |
ffa800d1 | 797 | } |
114c7df6 | 798 | \f |
2f925a60 | 799 | |
621a25ae | 800 | /* DST = A & B. */ |
b6e72c17 | 801 | |
802 | void | |
056755a1 | 803 | bitmap_and (bitmap dst, const_bitmap a, const_bitmap b) |
2f925a60 | 804 | { |
b6e72c17 | 805 | bitmap_element *dst_elt = dst->first; |
056755a1 | 806 | const bitmap_element *a_elt = a->first; |
807 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 808 | bitmap_element *dst_prev = NULL; |
66b5ac3c | 809 | |
07913396 | 810 | gcc_assert (dst != a && dst != b); |
811 | ||
812 | if (a == b) | |
813 | { | |
814 | bitmap_copy (dst, a); | |
815 | return; | |
816 | } | |
817 | ||
b6e72c17 | 818 | while (a_elt && b_elt) |
819 | { | |
820 | if (a_elt->indx < b_elt->indx) | |
821 | a_elt = a_elt->next; | |
822 | else if (b_elt->indx < a_elt->indx) | |
823 | b_elt = b_elt->next; | |
824 | else | |
825 | { | |
826 | /* Matching elts, generate A & B. */ | |
827 | unsigned ix; | |
828 | BITMAP_WORD ior = 0; | |
829 | ||
830 | if (!dst_elt) | |
5669bd62 | 831 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); |
a0c938f0 | 832 | else |
5669bd62 | 833 | dst_elt->indx = a_elt->indx; |
4399d500 | 834 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 835 | { |
836 | BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; | |
2f925a60 | 837 | |
b6e72c17 | 838 | dst_elt->bits[ix] = r; |
839 | ior |= r; | |
840 | } | |
841 | if (ior) | |
842 | { | |
843 | dst_prev = dst_elt; | |
844 | dst_elt = dst_elt->next; | |
845 | } | |
846 | a_elt = a_elt->next; | |
847 | b_elt = b_elt->next; | |
848 | } | |
849 | } | |
c926c35f | 850 | /* Ensure that dst->current is valid. */ |
851 | dst->current = dst->first; | |
b6e72c17 | 852 | bitmap_elt_clear_from (dst, dst_elt); |
0ea2d350 | 853 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 854 | if (dst->current) |
855 | dst->indx = dst->current->indx; | |
856 | } | |
857 | ||
ea9538fb | 858 | /* A &= B. Return true if A changed. */ |
b6e72c17 | 859 | |
ea9538fb | 860 | bool |
056755a1 | 861 | bitmap_and_into (bitmap a, const_bitmap b) |
b6e72c17 | 862 | { |
863 | bitmap_element *a_elt = a->first; | |
056755a1 | 864 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 865 | bitmap_element *next; |
ea9538fb | 866 | bool changed = false; |
2f925a60 | 867 | |
a0c938f0 | 868 | if (a == b) |
ea9538fb | 869 | return false; |
07913396 | 870 | |
b6e72c17 | 871 | while (a_elt && b_elt) |
2f925a60 | 872 | { |
b6e72c17 | 873 | if (a_elt->indx < b_elt->indx) |
874 | { | |
875 | next = a_elt->next; | |
876 | bitmap_element_free (a, a_elt); | |
877 | a_elt = next; | |
ea9538fb | 878 | changed = true; |
b6e72c17 | 879 | } |
880 | else if (b_elt->indx < a_elt->indx) | |
881 | b_elt = b_elt->next; | |
882 | else | |
2f925a60 | 883 | { |
b6e72c17 | 884 | /* Matching elts, generate A &= B. */ |
885 | unsigned ix; | |
886 | BITMAP_WORD ior = 0; | |
887 | ||
4399d500 | 888 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 889 | { |
890 | BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; | |
ea9538fb | 891 | if (a_elt->bits[ix] != r) |
892 | changed = true; | |
b6e72c17 | 893 | a_elt->bits[ix] = r; |
894 | ior |= r; | |
895 | } | |
896 | next = a_elt->next; | |
897 | if (!ior) | |
898 | bitmap_element_free (a, a_elt); | |
899 | a_elt = next; | |
900 | b_elt = b_elt->next; | |
2f925a60 | 901 | } |
b6e72c17 | 902 | } |
ea9538fb | 903 | |
904 | if (a_elt) | |
905 | { | |
906 | changed = true; | |
907 | bitmap_elt_clear_from (a, a_elt); | |
908 | } | |
909 | ||
0ea2d350 | 910 | gcc_checking_assert (!a->current == !a->first |
911 | && (!a->current || a->indx == a->current->indx)); | |
ea9538fb | 912 | |
913 | return changed; | |
b6e72c17 | 914 | } |
915 | ||
3072d30e | 916 | |
917 | /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT | |
918 | if non-NULL. CHANGED is true if the destination bitmap had already been | |
919 | changed; the new value of CHANGED is returned. */ | |
920 | ||
921 | static inline bool | |
922 | bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, | |
056755a1 | 923 | const bitmap_element *src_elt, bool changed) |
3072d30e | 924 | { |
925 | if (!changed && dst_elt && dst_elt->indx == src_elt->indx) | |
926 | { | |
927 | unsigned ix; | |
928 | ||
4399d500 | 929 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 930 | if (src_elt->bits[ix] != dst_elt->bits[ix]) |
931 | { | |
932 | dst_elt->bits[ix] = src_elt->bits[ix]; | |
933 | changed = true; | |
934 | } | |
935 | } | |
936 | else | |
937 | { | |
938 | changed = true; | |
939 | if (!dst_elt) | |
940 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, src_elt->indx); | |
941 | else | |
942 | dst_elt->indx = src_elt->indx; | |
943 | memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits)); | |
944 | } | |
945 | return changed; | |
946 | } | |
947 | ||
948 | ||
949 | ||
b6e72c17 | 950 | /* DST = A & ~B */ |
951 | ||
3072d30e | 952 | bool |
056755a1 | 953 | bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b) |
b6e72c17 | 954 | { |
955 | bitmap_element *dst_elt = dst->first; | |
056755a1 | 956 | const bitmap_element *a_elt = a->first; |
957 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 958 | bitmap_element *dst_prev = NULL; |
3072d30e | 959 | bitmap_element **dst_prev_pnext = &dst->first; |
960 | bool changed = false; | |
b6e72c17 | 961 | |
07913396 | 962 | gcc_assert (dst != a && dst != b); |
a0c938f0 | 963 | |
07913396 | 964 | if (a == b) |
965 | { | |
3072d30e | 966 | changed = !bitmap_empty_p (dst); |
07913396 | 967 | bitmap_clear (dst); |
3072d30e | 968 | return changed; |
07913396 | 969 | } |
970 | ||
b6e72c17 | 971 | while (a_elt) |
972 | { | |
3072d30e | 973 | while (b_elt && b_elt->indx < a_elt->indx) |
974 | b_elt = b_elt->next; | |
975 | ||
976 | if (!b_elt || b_elt->indx > a_elt->indx) | |
2f925a60 | 977 | { |
3072d30e | 978 | changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed); |
979 | dst_prev = *dst_prev_pnext; | |
980 | dst_prev_pnext = &dst_prev->next; | |
981 | dst_elt = *dst_prev_pnext; | |
b6e72c17 | 982 | a_elt = a_elt->next; |
2f925a60 | 983 | } |
3072d30e | 984 | |
2f925a60 | 985 | else |
986 | { | |
b6e72c17 | 987 | /* Matching elts, generate A & ~B. */ |
988 | unsigned ix; | |
989 | BITMAP_WORD ior = 0; | |
990 | ||
3072d30e | 991 | if (!changed && dst_elt && dst_elt->indx == a_elt->indx) |
992 | { | |
4399d500 | 993 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 994 | { |
995 | BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; | |
996 | ||
997 | if (dst_elt->bits[ix] != r) | |
998 | { | |
999 | changed = true; | |
1000 | dst_elt->bits[ix] = r; | |
1001 | } | |
1002 | ior |= r; | |
1003 | } | |
1004 | } | |
a0c938f0 | 1005 | else |
b6e72c17 | 1006 | { |
3072d30e | 1007 | bool new_element; |
1008 | if (!dst_elt || dst_elt->indx > a_elt->indx) | |
1009 | { | |
1010 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | |
1011 | new_element = true; | |
1012 | } | |
1013 | else | |
1014 | { | |
1015 | dst_elt->indx = a_elt->indx; | |
1016 | new_element = false; | |
1017 | } | |
b6e72c17 | 1018 | |
4399d500 | 1019 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1020 | { |
1021 | BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; | |
1022 | ||
1023 | dst_elt->bits[ix] = r; | |
1024 | ior |= r; | |
1025 | } | |
1026 | ||
1027 | if (ior) | |
1028 | changed = true; | |
1029 | else | |
1030 | { | |
1031 | changed |= !new_element; | |
1032 | bitmap_element_free (dst, dst_elt); | |
1033 | dst_elt = *dst_prev_pnext; | |
1034 | } | |
b6e72c17 | 1035 | } |
3072d30e | 1036 | |
b6e72c17 | 1037 | if (ior) |
1038 | { | |
3072d30e | 1039 | dst_prev = *dst_prev_pnext; |
1040 | dst_prev_pnext = &dst_prev->next; | |
1041 | dst_elt = *dst_prev_pnext; | |
b6e72c17 | 1042 | } |
1043 | a_elt = a_elt->next; | |
1044 | b_elt = b_elt->next; | |
2f925a60 | 1045 | } |
b6e72c17 | 1046 | } |
3072d30e | 1047 | |
c926c35f | 1048 | /* Ensure that dst->current is valid. */ |
1049 | dst->current = dst->first; | |
3072d30e | 1050 | |
1051 | if (dst_elt) | |
1052 | { | |
1053 | changed = true; | |
1054 | bitmap_elt_clear_from (dst, dst_elt); | |
1055 | } | |
0ea2d350 | 1056 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 1057 | if (dst->current) |
1058 | dst->indx = dst->current->indx; | |
3072d30e | 1059 | |
1060 | return changed; | |
b6e72c17 | 1061 | } |
1062 | ||
0db4e233 | 1063 | /* A &= ~B. Returns true if A changes */ |
2f925a60 | 1064 | |
0db4e233 | 1065 | bool |
056755a1 | 1066 | bitmap_and_compl_into (bitmap a, const_bitmap b) |
b6e72c17 | 1067 | { |
1068 | bitmap_element *a_elt = a->first; | |
056755a1 | 1069 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 1070 | bitmap_element *next; |
0db4e233 | 1071 | BITMAP_WORD changed = 0; |
b6e72c17 | 1072 | |
07913396 | 1073 | if (a == b) |
1074 | { | |
1075 | if (bitmap_empty_p (a)) | |
1076 | return false; | |
1077 | else | |
1078 | { | |
1079 | bitmap_clear (a); | |
1080 | return true; | |
1081 | } | |
1082 | } | |
1083 | ||
b6e72c17 | 1084 | while (a_elt && b_elt) |
1085 | { | |
1086 | if (a_elt->indx < b_elt->indx) | |
1087 | a_elt = a_elt->next; | |
1088 | else if (b_elt->indx < a_elt->indx) | |
1089 | b_elt = b_elt->next; | |
1090 | else | |
66b5ac3c | 1091 | { |
b6e72c17 | 1092 | /* Matching elts, generate A &= ~B. */ |
1093 | unsigned ix; | |
1094 | BITMAP_WORD ior = 0; | |
1095 | ||
4399d500 | 1096 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 1097 | { |
0db4e233 | 1098 | BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; |
1099 | BITMAP_WORD r = a_elt->bits[ix] ^ cleared; | |
b6e72c17 | 1100 | |
1101 | a_elt->bits[ix] = r; | |
0db4e233 | 1102 | changed |= cleared; |
b6e72c17 | 1103 | ior |= r; |
1104 | } | |
1105 | next = a_elt->next; | |
1106 | if (!ior) | |
1107 | bitmap_element_free (a, a_elt); | |
1108 | a_elt = next; | |
1109 | b_elt = b_elt->next; | |
66b5ac3c | 1110 | } |
b6e72c17 | 1111 | } |
0ea2d350 | 1112 | gcc_checking_assert (!a->current == !a->first |
1113 | && (!a->current || a->indx == a->current->indx)); | |
0db4e233 | 1114 | return changed != 0; |
b6e72c17 | 1115 | } |
1116 | ||
3072d30e | 1117 | /* Set COUNT bits from START in HEAD. */ |
1118 | void | |
1119 | bitmap_set_range (bitmap head, unsigned int start, unsigned int count) | |
1120 | { | |
1121 | unsigned int first_index, end_bit_plus1, last_index; | |
1122 | bitmap_element *elt, *elt_prev; | |
1123 | unsigned int i; | |
1124 | ||
1125 | if (!count) | |
1126 | return; | |
1127 | ||
837d3ea8 | 1128 | if (count == 1) |
1129 | { | |
1130 | bitmap_set_bit (head, start); | |
1131 | return; | |
1132 | } | |
1133 | ||
3072d30e | 1134 | first_index = start / BITMAP_ELEMENT_ALL_BITS; |
1135 | end_bit_plus1 = start + count; | |
1136 | last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | |
1137 | elt = bitmap_find_bit (head, start); | |
1138 | ||
1139 | /* If bitmap_find_bit returns zero, the current is the closest block | |
1140 | to the result. Otherwise, just use bitmap_element_allocate to | |
1141 | ensure ELT is set; in the loop below, ELT == NULL means "insert | |
1142 | at the end of the bitmap". */ | |
1143 | if (!elt) | |
1144 | { | |
1145 | elt = bitmap_element_allocate (head); | |
1146 | elt->indx = first_index; | |
1147 | bitmap_element_link (head, elt); | |
1148 | } | |
1149 | ||
d16af188 | 1150 | gcc_checking_assert (elt->indx == first_index); |
3072d30e | 1151 | elt_prev = elt->prev; |
1152 | for (i = first_index; i <= last_index; i++) | |
1153 | { | |
1154 | unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS; | |
1155 | unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; | |
1156 | ||
1157 | unsigned int first_word_to_mod; | |
1158 | BITMAP_WORD first_mask; | |
1159 | unsigned int last_word_to_mod; | |
1160 | BITMAP_WORD last_mask; | |
1161 | unsigned int ix; | |
1162 | ||
1163 | if (!elt || elt->indx != i) | |
1164 | elt = bitmap_elt_insert_after (head, elt_prev, i); | |
1165 | ||
1166 | if (elt_start_bit <= start) | |
1167 | { | |
1168 | /* The first bit to turn on is somewhere inside this | |
1169 | elt. */ | |
1170 | first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; | |
1171 | ||
1172 | /* This mask should have 1s in all bits >= start position. */ | |
1173 | first_mask = | |
1174 | (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; | |
1175 | first_mask = ~first_mask; | |
1176 | } | |
1177 | else | |
1178 | { | |
1179 | /* The first bit to turn on is below this start of this elt. */ | |
1180 | first_word_to_mod = 0; | |
1181 | first_mask = ~(BITMAP_WORD) 0; | |
1182 | } | |
1183 | ||
1184 | if (elt_end_bit_plus1 <= end_bit_plus1) | |
1185 | { | |
1186 | /* The last bit to turn on is beyond this elt. */ | |
1187 | last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; | |
1188 | last_mask = ~(BITMAP_WORD) 0; | |
1189 | } | |
1190 | else | |
1191 | { | |
1192 | /* The last bit to turn on is inside to this elt. */ | |
1193 | last_word_to_mod = | |
1194 | (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; | |
1195 | ||
1196 | /* The last mask should have 1s below the end bit. */ | |
1197 | last_mask = | |
1198 | (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1; | |
1199 | } | |
1200 | ||
1201 | if (first_word_to_mod == last_word_to_mod) | |
1202 | { | |
1203 | BITMAP_WORD mask = first_mask & last_mask; | |
1204 | elt->bits[first_word_to_mod] |= mask; | |
1205 | } | |
1206 | else | |
1207 | { | |
1208 | elt->bits[first_word_to_mod] |= first_mask; | |
1209 | if (BITMAP_ELEMENT_WORDS > 2) | |
1210 | for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++) | |
1211 | elt->bits[ix] = ~(BITMAP_WORD) 0; | |
1212 | elt->bits[last_word_to_mod] |= last_mask; | |
1213 | } | |
1214 | ||
1215 | elt_prev = elt; | |
1216 | elt = elt->next; | |
1217 | } | |
1218 | ||
1219 | head->current = elt ? elt : elt_prev; | |
1220 | head->indx = head->current->indx; | |
1221 | } | |
1222 | ||
5669bd62 | 1223 | /* Clear COUNT bits from START in HEAD. */ |
1224 | void | |
1225 | bitmap_clear_range (bitmap head, unsigned int start, unsigned int count) | |
1226 | { | |
3072d30e | 1227 | unsigned int first_index, end_bit_plus1, last_index; |
1228 | bitmap_element *elt; | |
1229 | ||
1230 | if (!count) | |
1231 | return; | |
1232 | ||
837d3ea8 | 1233 | if (count == 1) |
1234 | { | |
1235 | bitmap_clear_bit (head, start); | |
1236 | return; | |
1237 | } | |
1238 | ||
3072d30e | 1239 | first_index = start / BITMAP_ELEMENT_ALL_BITS; |
1240 | end_bit_plus1 = start + count; | |
1241 | last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | |
1242 | elt = bitmap_find_bit (head, start); | |
5669bd62 | 1243 | |
1244 | /* If bitmap_find_bit returns zero, the current is the closest block | |
1245 | to the result. If the current is less than first index, find the | |
1246 | next one. Otherwise, just set elt to be current. */ | |
1247 | if (!elt) | |
a0c938f0 | 1248 | { |
5669bd62 | 1249 | if (head->current) |
1250 | { | |
1251 | if (head->indx < first_index) | |
1252 | { | |
1253 | elt = head->current->next; | |
1254 | if (!elt) | |
1255 | return; | |
1256 | } | |
a0c938f0 | 1257 | else |
5669bd62 | 1258 | elt = head->current; |
1259 | } | |
1260 | else | |
1261 | return; | |
1262 | } | |
1263 | ||
1264 | while (elt && (elt->indx <= last_index)) | |
1265 | { | |
1266 | bitmap_element * next_elt = elt->next; | |
1267 | unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS; | |
1268 | unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; | |
1269 | ||
1270 | ||
1271 | if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1) | |
1272 | /* Get rid of the entire elt and go to the next one. */ | |
1273 | bitmap_element_free (head, elt); | |
a0c938f0 | 1274 | else |
5669bd62 | 1275 | { |
1276 | /* Going to have to knock out some bits in this elt. */ | |
a0c938f0 | 1277 | unsigned int first_word_to_mod; |
1278 | BITMAP_WORD first_mask; | |
5669bd62 | 1279 | unsigned int last_word_to_mod; |
1280 | BITMAP_WORD last_mask; | |
1281 | unsigned int i; | |
1282 | bool clear = true; | |
1283 | ||
1284 | if (elt_start_bit <= start) | |
1285 | { | |
1286 | /* The first bit to turn off is somewhere inside this | |
1287 | elt. */ | |
1288 | first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; | |
1289 | ||
1290 | /* This mask should have 1s in all bits >= start position. */ | |
a0c938f0 | 1291 | first_mask = |
5669bd62 | 1292 | (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; |
1293 | first_mask = ~first_mask; | |
1294 | } | |
1295 | else | |
1296 | { | |
1297 | /* The first bit to turn off is below this start of this elt. */ | |
1298 | first_word_to_mod = 0; | |
1299 | first_mask = 0; | |
1300 | first_mask = ~first_mask; | |
a0c938f0 | 1301 | } |
1302 | ||
5669bd62 | 1303 | if (elt_end_bit_plus1 <= end_bit_plus1) |
1304 | { | |
1305 | /* The last bit to turn off is beyond this elt. */ | |
1306 | last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; | |
1307 | last_mask = 0; | |
1308 | last_mask = ~last_mask; | |
1309 | } | |
1310 | else | |
1311 | { | |
1312 | /* The last bit to turn off is inside to this elt. */ | |
a0c938f0 | 1313 | last_word_to_mod = |
5669bd62 | 1314 | (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; |
1315 | ||
1316 | /* The last mask should have 1s below the end bit. */ | |
a0c938f0 | 1317 | last_mask = |
5669bd62 | 1318 | (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1; |
1319 | } | |
1320 | ||
1321 | ||
1322 | if (first_word_to_mod == last_word_to_mod) | |
1323 | { | |
1324 | BITMAP_WORD mask = first_mask & last_mask; | |
1325 | elt->bits[first_word_to_mod] &= ~mask; | |
1326 | } | |
1327 | else | |
1328 | { | |
1329 | elt->bits[first_word_to_mod] &= ~first_mask; | |
3072d30e | 1330 | if (BITMAP_ELEMENT_WORDS > 2) |
1331 | for (i = first_word_to_mod + 1; i < last_word_to_mod; i++) | |
1332 | elt->bits[i] = 0; | |
5669bd62 | 1333 | elt->bits[last_word_to_mod] &= ~last_mask; |
1334 | } | |
1335 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
1336 | if (elt->bits[i]) | |
1337 | { | |
1338 | clear = false; | |
1339 | break; | |
1340 | } | |
1341 | /* Check to see if there are any bits left. */ | |
1342 | if (clear) | |
1343 | bitmap_element_free (head, elt); | |
1344 | } | |
1345 | elt = next_elt; | |
1346 | } | |
a0c938f0 | 1347 | |
5669bd62 | 1348 | if (elt) |
1349 | { | |
1350 | head->current = elt; | |
1351 | head->indx = head->current->indx; | |
1352 | } | |
1353 | } | |
1354 | ||
1355 | /* A = ~A & B. */ | |
1356 | ||
1357 | void | |
056755a1 | 1358 | bitmap_compl_and_into (bitmap a, const_bitmap b) |
5669bd62 | 1359 | { |
1360 | bitmap_element *a_elt = a->first; | |
056755a1 | 1361 | const bitmap_element *b_elt = b->first; |
5669bd62 | 1362 | bitmap_element *a_prev = NULL; |
1363 | bitmap_element *next; | |
1364 | ||
1365 | gcc_assert (a != b); | |
1366 | ||
1367 | if (bitmap_empty_p (a)) | |
1368 | { | |
1369 | bitmap_copy (a, b); | |
1370 | return; | |
1371 | } | |
1372 | if (bitmap_empty_p (b)) | |
1373 | { | |
1374 | bitmap_clear (a); | |
1375 | return; | |
1376 | } | |
1377 | ||
1378 | while (a_elt || b_elt) | |
1379 | { | |
1380 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
1381 | { | |
1382 | /* A is before B. Remove A */ | |
1383 | next = a_elt->next; | |
1384 | a_prev = a_elt->prev; | |
1385 | bitmap_element_free (a, a_elt); | |
1386 | a_elt = next; | |
1387 | } | |
1388 | else if (!a_elt || b_elt->indx < a_elt->indx) | |
1389 | { | |
1390 | /* B is before A. Copy B. */ | |
1391 | next = bitmap_elt_insert_after (a, a_prev, b_elt->indx); | |
1392 | memcpy (next->bits, b_elt->bits, sizeof (next->bits)); | |
1393 | a_prev = next; | |
1394 | b_elt = b_elt->next; | |
1395 | } | |
1396 | else | |
1397 | { | |
1398 | /* Matching elts, generate A = ~A & B. */ | |
1399 | unsigned ix; | |
1400 | BITMAP_WORD ior = 0; | |
1401 | ||
4399d500 | 1402 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
5669bd62 | 1403 | { |
1404 | BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; | |
1405 | BITMAP_WORD r = b_elt->bits[ix] ^ cleared; | |
1406 | ||
1407 | a_elt->bits[ix] = r; | |
1408 | ior |= r; | |
1409 | } | |
1410 | next = a_elt->next; | |
1411 | if (!ior) | |
1412 | bitmap_element_free (a, a_elt); | |
1413 | else | |
1414 | a_prev = a_elt; | |
1415 | a_elt = next; | |
1416 | b_elt = b_elt->next; | |
1417 | } | |
1418 | } | |
0ea2d350 | 1419 | gcc_checking_assert (!a->current == !a->first |
1420 | && (!a->current || a->indx == a->current->indx)); | |
5669bd62 | 1421 | return; |
1422 | } | |
1423 | ||
3072d30e | 1424 | |
1425 | /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV, | |
1426 | overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap | |
1427 | had already been changed; the new value of CHANGED is returned. */ | |
1428 | ||
1429 | static inline bool | |
1430 | bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, | |
056755a1 | 1431 | const bitmap_element *a_elt, const bitmap_element *b_elt, |
3072d30e | 1432 | bool changed) |
1433 | { | |
1434 | gcc_assert (a_elt || b_elt); | |
1435 | ||
1436 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
1437 | { | |
1438 | /* Matching elts, generate A | B. */ | |
1439 | unsigned ix; | |
1440 | ||
1441 | if (!changed && dst_elt && dst_elt->indx == a_elt->indx) | |
1442 | { | |
4399d500 | 1443 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1444 | { |
1445 | BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; | |
1446 | if (r != dst_elt->bits[ix]) | |
1447 | { | |
1448 | dst_elt->bits[ix] = r; | |
1449 | changed = true; | |
1450 | } | |
1451 | } | |
1452 | } | |
1453 | else | |
1454 | { | |
1455 | changed = true; | |
1456 | if (!dst_elt) | |
1457 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); | |
1458 | else | |
1459 | dst_elt->indx = a_elt->indx; | |
4399d500 | 1460 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1461 | { |
1462 | BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; | |
1463 | dst_elt->bits[ix] = r; | |
1464 | } | |
1465 | } | |
1466 | } | |
1467 | else | |
1468 | { | |
1469 | /* Copy a single element. */ | |
056755a1 | 1470 | const bitmap_element *src; |
3072d30e | 1471 | |
1472 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
1473 | src = a_elt; | |
1474 | else | |
1475 | src = b_elt; | |
1476 | ||
d16af188 | 1477 | gcc_checking_assert (src); |
3072d30e | 1478 | changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed); |
1479 | } | |
1480 | return changed; | |
1481 | } | |
1482 | ||
1483 | ||
b6e72c17 | 1484 | /* DST = A | B. Return true if DST changes. */ |
1485 | ||
1486 | bool | |
056755a1 | 1487 | bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b) |
b6e72c17 | 1488 | { |
1489 | bitmap_element *dst_elt = dst->first; | |
056755a1 | 1490 | const bitmap_element *a_elt = a->first; |
1491 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 1492 | bitmap_element *dst_prev = NULL; |
3072d30e | 1493 | bitmap_element **dst_prev_pnext = &dst->first; |
a0c938f0 | 1494 | bool changed = false; |
b6e72c17 | 1495 | |
07913396 | 1496 | gcc_assert (dst != a && dst != b); |
1497 | ||
b6e72c17 | 1498 | while (a_elt || b_elt) |
1499 | { | |
3072d30e | 1500 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed); |
1501 | ||
b6e72c17 | 1502 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) |
66b5ac3c | 1503 | { |
b6e72c17 | 1504 | a_elt = a_elt->next; |
1505 | b_elt = b_elt->next; | |
66b5ac3c | 1506 | } |
1507 | else | |
2f925a60 | 1508 | { |
3072d30e | 1509 | if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) |
1510 | a_elt = a_elt->next; | |
1511 | else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) | |
1512 | b_elt = b_elt->next; | |
2f925a60 | 1513 | } |
3072d30e | 1514 | |
1515 | dst_prev = *dst_prev_pnext; | |
1516 | dst_prev_pnext = &dst_prev->next; | |
1517 | dst_elt = *dst_prev_pnext; | |
b6e72c17 | 1518 | } |
1519 | ||
1520 | if (dst_elt) | |
1521 | { | |
1522 | changed = true; | |
85ac1c40 | 1523 | /* Ensure that dst->current is valid. */ |
1524 | dst->current = dst->first; | |
b6e72c17 | 1525 | bitmap_elt_clear_from (dst, dst_elt); |
1526 | } | |
0ea2d350 | 1527 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 1528 | if (dst->current) |
1529 | dst->indx = dst->current->indx; | |
1530 | return changed; | |
1531 | } | |
2f925a60 | 1532 | |
b6e72c17 | 1533 | /* A |= B. Return true if A changes. */ |
1534 | ||
1535 | bool | |
056755a1 | 1536 | bitmap_ior_into (bitmap a, const_bitmap b) |
b6e72c17 | 1537 | { |
1538 | bitmap_element *a_elt = a->first; | |
056755a1 | 1539 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 1540 | bitmap_element *a_prev = NULL; |
3072d30e | 1541 | bitmap_element **a_prev_pnext = &a->first; |
b6e72c17 | 1542 | bool changed = false; |
1543 | ||
07913396 | 1544 | if (a == b) |
1545 | return false; | |
1546 | ||
b6e72c17 | 1547 | while (b_elt) |
1548 | { | |
3072d30e | 1549 | /* If A lags behind B, just advance it. */ |
1550 | if (!a_elt || a_elt->indx == b_elt->indx) | |
b6e72c17 | 1551 | { |
3072d30e | 1552 | changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed); |
b6e72c17 | 1553 | b_elt = b_elt->next; |
d587687f | 1554 | } |
3072d30e | 1555 | else if (a_elt->indx > b_elt->indx) |
d587687f | 1556 | { |
3072d30e | 1557 | changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed); |
b6e72c17 | 1558 | b_elt = b_elt->next; |
2f925a60 | 1559 | } |
3072d30e | 1560 | |
1561 | a_prev = *a_prev_pnext; | |
1562 | a_prev_pnext = &a_prev->next; | |
1563 | a_elt = *a_prev_pnext; | |
2f925a60 | 1564 | } |
3072d30e | 1565 | |
0ea2d350 | 1566 | gcc_checking_assert (!a->current == !a->first); |
b6e72c17 | 1567 | if (a->current) |
1568 | a->indx = a->current->indx; | |
1569 | return changed; | |
1570 | } | |
1571 | ||
1572 | /* DST = A ^ B */ | |
2f925a60 | 1573 | |
b6e72c17 | 1574 | void |
056755a1 | 1575 | bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b) |
b6e72c17 | 1576 | { |
1577 | bitmap_element *dst_elt = dst->first; | |
056755a1 | 1578 | const bitmap_element *a_elt = a->first; |
1579 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 1580 | bitmap_element *dst_prev = NULL; |
1581 | ||
07913396 | 1582 | gcc_assert (dst != a && dst != b); |
1583 | if (a == b) | |
1584 | { | |
1585 | bitmap_clear (dst); | |
1586 | return; | |
1587 | } | |
1588 | ||
b6e72c17 | 1589 | while (a_elt || b_elt) |
2f925a60 | 1590 | { |
b6e72c17 | 1591 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) |
1f3233d1 | 1592 | { |
b6e72c17 | 1593 | /* Matching elts, generate A ^ B. */ |
1594 | unsigned ix; | |
1595 | BITMAP_WORD ior = 0; | |
1596 | ||
1597 | if (!dst_elt) | |
5669bd62 | 1598 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, a_elt->indx); |
1599 | else | |
1600 | dst_elt->indx = a_elt->indx; | |
4399d500 | 1601 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 1602 | { |
1603 | BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; | |
1604 | ||
1605 | ior |= r; | |
1606 | dst_elt->bits[ix] = r; | |
1607 | } | |
1608 | a_elt = a_elt->next; | |
1609 | b_elt = b_elt->next; | |
1610 | if (ior) | |
1611 | { | |
1612 | dst_prev = dst_elt; | |
1613 | dst_elt = dst_elt->next; | |
1614 | } | |
1f3233d1 | 1615 | } |
1616 | else | |
1617 | { | |
b6e72c17 | 1618 | /* Copy a single element. */ |
056755a1 | 1619 | const bitmap_element *src; |
b6e72c17 | 1620 | |
1621 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
1622 | { | |
1623 | src = a_elt; | |
1624 | a_elt = a_elt->next; | |
1625 | } | |
1626 | else | |
1627 | { | |
1628 | src = b_elt; | |
1629 | b_elt = b_elt->next; | |
1630 | } | |
1631 | ||
1632 | if (!dst_elt) | |
5669bd62 | 1633 | dst_elt = bitmap_elt_insert_after (dst, dst_prev, src->indx); |
a0c938f0 | 1634 | else |
5669bd62 | 1635 | dst_elt->indx = src->indx; |
b6e72c17 | 1636 | memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); |
1637 | dst_prev = dst_elt; | |
1638 | dst_elt = dst_elt->next; | |
1f3233d1 | 1639 | } |
2f925a60 | 1640 | } |
c926c35f | 1641 | /* Ensure that dst->current is valid. */ |
1642 | dst->current = dst->first; | |
b6e72c17 | 1643 | bitmap_elt_clear_from (dst, dst_elt); |
0ea2d350 | 1644 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 1645 | if (dst->current) |
1646 | dst->indx = dst->current->indx; | |
1647 | } | |
2f925a60 | 1648 | |
b6e72c17 | 1649 | /* A ^= B */ |
66b5ac3c | 1650 | |
b6e72c17 | 1651 | void |
056755a1 | 1652 | bitmap_xor_into (bitmap a, const_bitmap b) |
b6e72c17 | 1653 | { |
1654 | bitmap_element *a_elt = a->first; | |
056755a1 | 1655 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 1656 | bitmap_element *a_prev = NULL; |
1657 | ||
07913396 | 1658 | if (a == b) |
1659 | { | |
1660 | bitmap_clear (a); | |
1661 | return; | |
1662 | } | |
1663 | ||
b6e72c17 | 1664 | while (b_elt) |
1665 | { | |
1666 | if (!a_elt || b_elt->indx < a_elt->indx) | |
1667 | { | |
1668 | /* Copy b_elt. */ | |
5669bd62 | 1669 | bitmap_element *dst = bitmap_elt_insert_after (a, a_prev, b_elt->indx); |
b6e72c17 | 1670 | memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); |
1671 | a_prev = dst; | |
1672 | b_elt = b_elt->next; | |
1673 | } | |
1674 | else if (a_elt->indx < b_elt->indx) | |
1675 | { | |
1676 | a_prev = a_elt; | |
1677 | a_elt = a_elt->next; | |
1678 | } | |
1679 | else | |
1680 | { | |
1681 | /* Matching elts, generate A ^= B. */ | |
1682 | unsigned ix; | |
1683 | BITMAP_WORD ior = 0; | |
1684 | bitmap_element *next = a_elt->next; | |
1685 | ||
4399d500 | 1686 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 1687 | { |
1688 | BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; | |
1689 | ||
1690 | ior |= r; | |
1691 | a_elt->bits[ix] = r; | |
1692 | } | |
1693 | b_elt = b_elt->next; | |
1694 | if (ior) | |
1695 | a_prev = a_elt; | |
1696 | else | |
1697 | bitmap_element_free (a, a_elt); | |
1698 | a_elt = next; | |
1699 | } | |
1700 | } | |
0ea2d350 | 1701 | gcc_checking_assert (!a->current == !a->first); |
b6e72c17 | 1702 | if (a->current) |
1703 | a->indx = a->current->indx; | |
66b5ac3c | 1704 | } |
1705 | ||
21576831 | 1706 | /* Return true if two bitmaps are identical. |
1707 | We do not bother with a check for pointer equality, as that never | |
1708 | occurs in practice. */ | |
66b5ac3c | 1709 | |
21576831 | 1710 | bool |
056755a1 | 1711 | bitmap_equal_p (const_bitmap a, const_bitmap b) |
66b5ac3c | 1712 | { |
056755a1 | 1713 | const bitmap_element *a_elt; |
1714 | const bitmap_element *b_elt; | |
21576831 | 1715 | unsigned ix; |
a0c938f0 | 1716 | |
21576831 | 1717 | for (a_elt = a->first, b_elt = b->first; |
1718 | a_elt && b_elt; | |
1719 | a_elt = a_elt->next, b_elt = b_elt->next) | |
1720 | { | |
1721 | if (a_elt->indx != b_elt->indx) | |
1722 | return false; | |
4399d500 | 1723 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
21576831 | 1724 | if (a_elt->bits[ix] != b_elt->bits[ix]) |
1725 | return false; | |
1726 | } | |
1727 | return !a_elt && !b_elt; | |
1728 | } | |
1729 | ||
1730 | /* Return true if A AND B is not empty. */ | |
1731 | ||
1732 | bool | |
056755a1 | 1733 | bitmap_intersect_p (const_bitmap a, const_bitmap b) |
21576831 | 1734 | { |
056755a1 | 1735 | const bitmap_element *a_elt; |
1736 | const bitmap_element *b_elt; | |
21576831 | 1737 | unsigned ix; |
a0c938f0 | 1738 | |
21576831 | 1739 | for (a_elt = a->first, b_elt = b->first; |
1740 | a_elt && b_elt;) | |
1741 | { | |
1742 | if (a_elt->indx < b_elt->indx) | |
1743 | a_elt = a_elt->next; | |
1744 | else if (b_elt->indx < a_elt->indx) | |
1745 | b_elt = b_elt->next; | |
1746 | else | |
1747 | { | |
4399d500 | 1748 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
21576831 | 1749 | if (a_elt->bits[ix] & b_elt->bits[ix]) |
1750 | return true; | |
1751 | a_elt = a_elt->next; | |
1752 | b_elt = b_elt->next; | |
1753 | } | |
1754 | } | |
1755 | return false; | |
1756 | } | |
66b5ac3c | 1757 | |
21576831 | 1758 | /* Return true if A AND NOT B is not empty. */ |
66b5ac3c | 1759 | |
21576831 | 1760 | bool |
056755a1 | 1761 | bitmap_intersect_compl_p (const_bitmap a, const_bitmap b) |
21576831 | 1762 | { |
056755a1 | 1763 | const bitmap_element *a_elt; |
1764 | const bitmap_element *b_elt; | |
21576831 | 1765 | unsigned ix; |
1766 | for (a_elt = a->first, b_elt = b->first; | |
1767 | a_elt && b_elt;) | |
1768 | { | |
1769 | if (a_elt->indx < b_elt->indx) | |
1770 | return true; | |
1771 | else if (b_elt->indx < a_elt->indx) | |
1772 | b_elt = b_elt->next; | |
1773 | else | |
1774 | { | |
4399d500 | 1775 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
21576831 | 1776 | if (a_elt->bits[ix] & ~b_elt->bits[ix]) |
1777 | return true; | |
1778 | a_elt = a_elt->next; | |
1779 | b_elt = b_elt->next; | |
1780 | } | |
1781 | } | |
1782 | return a_elt != NULL; | |
2f925a60 | 1783 | } |
21576831 | 1784 | |
2f925a60 | 1785 | \f |
b6e72c17 | 1786 | /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */ |
2f925a60 | 1787 | |
79d6d448 | 1788 | bool |
056755a1 | 1789 | bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill) |
2f925a60 | 1790 | { |
3072d30e | 1791 | bool changed = false; |
42fe97ed | 1792 | |
3072d30e | 1793 | bitmap_element *dst_elt = dst->first; |
056755a1 | 1794 | const bitmap_element *a_elt = a->first; |
1795 | const bitmap_element *b_elt = b->first; | |
1796 | const bitmap_element *kill_elt = kill->first; | |
3072d30e | 1797 | bitmap_element *dst_prev = NULL; |
1798 | bitmap_element **dst_prev_pnext = &dst->first; | |
1799 | ||
1800 | gcc_assert (dst != a && dst != b && dst != kill); | |
1801 | ||
1802 | /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */ | |
1803 | if (b == kill || bitmap_empty_p (b)) | |
1804 | { | |
1805 | changed = !bitmap_equal_p (dst, a); | |
1806 | if (changed) | |
1807 | bitmap_copy (dst, a); | |
1808 | return changed; | |
1809 | } | |
1810 | if (bitmap_empty_p (kill)) | |
1811 | return bitmap_ior (dst, a, b); | |
1812 | if (bitmap_empty_p (a)) | |
1813 | return bitmap_and_compl (dst, b, kill); | |
1814 | ||
1815 | while (a_elt || b_elt) | |
1816 | { | |
1817 | bool new_element = false; | |
1818 | ||
1819 | if (b_elt) | |
1820 | while (kill_elt && kill_elt->indx < b_elt->indx) | |
1821 | kill_elt = kill_elt->next; | |
1822 | ||
1823 | if (b_elt && kill_elt && kill_elt->indx == b_elt->indx | |
1824 | && (!a_elt || a_elt->indx >= b_elt->indx)) | |
1825 | { | |
1826 | bitmap_element tmp_elt; | |
1827 | unsigned ix; | |
1828 | ||
1829 | BITMAP_WORD ior = 0; | |
1830 | tmp_elt.indx = b_elt->indx; | |
4399d500 | 1831 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1832 | { |
1833 | BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix]; | |
1834 | ior |= r; | |
1835 | tmp_elt.bits[ix] = r; | |
1836 | } | |
1837 | ||
1838 | if (ior) | |
1839 | { | |
1840 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, | |
1841 | a_elt, &tmp_elt, changed); | |
1842 | new_element = true; | |
1843 | if (a_elt && a_elt->indx == b_elt->indx) | |
1844 | a_elt = a_elt->next; | |
1845 | } | |
1846 | ||
1847 | b_elt = b_elt->next; | |
1848 | kill_elt = kill_elt->next; | |
1849 | } | |
1850 | else | |
1851 | { | |
1852 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, | |
1853 | a_elt, b_elt, changed); | |
1854 | new_element = true; | |
1855 | ||
1856 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
1857 | { | |
1858 | a_elt = a_elt->next; | |
1859 | b_elt = b_elt->next; | |
1860 | } | |
1861 | else | |
1862 | { | |
1863 | if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) | |
1864 | a_elt = a_elt->next; | |
1865 | else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) | |
1866 | b_elt = b_elt->next; | |
1867 | } | |
1868 | } | |
1869 | ||
1870 | if (new_element) | |
1871 | { | |
1872 | dst_prev = *dst_prev_pnext; | |
1873 | dst_prev_pnext = &dst_prev->next; | |
1874 | dst_elt = *dst_prev_pnext; | |
1875 | } | |
1876 | } | |
1877 | ||
1878 | if (dst_elt) | |
1879 | { | |
1880 | changed = true; | |
85ac1c40 | 1881 | /* Ensure that dst->current is valid. */ |
1882 | dst->current = dst->first; | |
3072d30e | 1883 | bitmap_elt_clear_from (dst, dst_elt); |
1884 | } | |
0ea2d350 | 1885 | gcc_checking_assert (!dst->current == !dst->first); |
3072d30e | 1886 | if (dst->current) |
1887 | dst->indx = dst->current->indx; | |
b6e72c17 | 1888 | |
604efc01 | 1889 | return changed; |
2f925a60 | 1890 | } |
114c7df6 | 1891 | |
b6e72c17 | 1892 | /* A |= (FROM1 & ~FROM2). Return true if A changes. */ |
79d6d448 | 1893 | |
1894 | bool | |
056755a1 | 1895 | bitmap_ior_and_compl_into (bitmap a, const_bitmap from1, const_bitmap from2) |
114c7df6 | 1896 | { |
1897 | bitmap_head tmp; | |
b6e72c17 | 1898 | bool changed; |
a0c938f0 | 1899 | |
42fe97ed | 1900 | bitmap_initialize (&tmp, &bitmap_default_obstack); |
b6e72c17 | 1901 | bitmap_and_compl (&tmp, from1, from2); |
1902 | changed = bitmap_ior_into (a, &tmp); | |
114c7df6 | 1903 | bitmap_clear (&tmp); |
1904 | ||
1905 | return changed; | |
1906 | } | |
3072d30e | 1907 | |
d7f2555b | 1908 | /* A |= (B & C). Return true if A changes. */ |
1909 | ||
1910 | bool | |
1911 | bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c) | |
1912 | { | |
1913 | bitmap_element *a_elt = a->first; | |
1914 | const bitmap_element *b_elt = b->first; | |
1915 | const bitmap_element *c_elt = c->first; | |
1916 | bitmap_element and_elt; | |
1917 | bitmap_element *a_prev = NULL; | |
1918 | bitmap_element **a_prev_pnext = &a->first; | |
1919 | bool changed = false; | |
1920 | unsigned ix; | |
1921 | ||
1922 | if (b == c) | |
1923 | return bitmap_ior_into (a, b); | |
1924 | if (bitmap_empty_p (b) || bitmap_empty_p (c)) | |
1925 | return false; | |
1926 | ||
1927 | and_elt.indx = -1; | |
1928 | while (b_elt && c_elt) | |
1929 | { | |
1930 | BITMAP_WORD overall; | |
1931 | ||
1932 | /* Find a common item of B and C. */ | |
1933 | while (b_elt->indx != c_elt->indx) | |
1934 | { | |
1935 | if (b_elt->indx < c_elt->indx) | |
1936 | { | |
1937 | b_elt = b_elt->next; | |
1938 | if (!b_elt) | |
1939 | goto done; | |
1940 | } | |
1941 | else | |
1942 | { | |
1943 | c_elt = c_elt->next; | |
1944 | if (!c_elt) | |
1945 | goto done; | |
1946 | } | |
1947 | } | |
1948 | ||
1949 | overall = 0; | |
1950 | and_elt.indx = b_elt->indx; | |
4399d500 | 1951 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
d7f2555b | 1952 | { |
1953 | and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix]; | |
1954 | overall |= and_elt.bits[ix]; | |
1955 | } | |
1956 | ||
1957 | b_elt = b_elt->next; | |
1958 | c_elt = c_elt->next; | |
1959 | if (!overall) | |
1960 | continue; | |
1961 | ||
1962 | /* Now find a place to insert AND_ELT. */ | |
1963 | do | |
1964 | { | |
1965 | ix = a_elt ? a_elt->indx : and_elt.indx; | |
1966 | if (ix == and_elt.indx) | |
1967 | changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed); | |
1968 | else if (ix > and_elt.indx) | |
1969 | changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed); | |
1970 | ||
1971 | a_prev = *a_prev_pnext; | |
1972 | a_prev_pnext = &a_prev->next; | |
1973 | a_elt = *a_prev_pnext; | |
1974 | ||
1975 | /* If A lagged behind B/C, we advanced it so loop once more. */ | |
1976 | } | |
1977 | while (ix < and_elt.indx); | |
1978 | } | |
1979 | ||
1980 | done: | |
0ea2d350 | 1981 | gcc_checking_assert (!a->current == !a->first); |
d7f2555b | 1982 | if (a->current) |
1983 | a->indx = a->current->indx; | |
1984 | return changed; | |
1985 | } | |
ecd52ea9 | 1986 | |
1987 | /* Compute hash of bitmap (for purposes of hashing). */ | |
1988 | hashval_t | |
1989 | bitmap_hash (const_bitmap head) | |
1990 | { | |
1991 | const bitmap_element *ptr; | |
1992 | BITMAP_WORD hash = 0; | |
1993 | int ix; | |
1994 | ||
1995 | for (ptr = head->first; ptr; ptr = ptr->next) | |
1996 | { | |
1997 | hash ^= ptr->indx; | |
1998 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
1999 | hash ^= ptr->bits[ix]; | |
2000 | } | |
2001 | return (hashval_t)hash; | |
2002 | } | |
2003 | ||
2f925a60 | 2004 | \f |
2f925a60 | 2005 | /* Debugging function to print out the contents of a bitmap. */ |
2006 | ||
4b987fac | 2007 | DEBUG_FUNCTION void |
056755a1 | 2008 | debug_bitmap_file (FILE *file, const_bitmap head) |
2f925a60 | 2009 | { |
056755a1 | 2010 | const bitmap_element *ptr; |
2f925a60 | 2011 | |
038ca0d1 | 2012 | fprintf (file, "\nfirst = " HOST_PTR_PRINTF |
2013 | " current = " HOST_PTR_PRINTF " indx = %u\n", | |
6f817829 | 2014 | (void *) head->first, (void *) head->current, head->indx); |
2f925a60 | 2015 | |
2016 | for (ptr = head->first; ptr; ptr = ptr->next) | |
2017 | { | |
e5c8f082 | 2018 | unsigned int i, j, col = 26; |
2f925a60 | 2019 | |
038ca0d1 | 2020 | fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF |
2021 | " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {", | |
056755a1 | 2022 | (const void*) ptr, (const void*) ptr->next, |
2023 | (const void*) ptr->prev, ptr->indx); | |
2f925a60 | 2024 | |
2025 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
e5c8f082 | 2026 | for (j = 0; j < BITMAP_WORD_BITS; j++) |
66b5ac3c | 2027 | if ((ptr->bits[i] >> j) & 1) |
2f925a60 | 2028 | { |
2029 | if (col > 70) | |
2030 | { | |
2031 | fprintf (file, "\n\t\t\t"); | |
2032 | col = 24; | |
2033 | } | |
2034 | ||
2035 | fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS | |
e5c8f082 | 2036 | + i * BITMAP_WORD_BITS + j)); |
2f925a60 | 2037 | col += 4; |
2038 | } | |
2039 | ||
2040 | fprintf (file, " }\n"); | |
2041 | } | |
2042 | } | |
ca2968e9 | 2043 | |
2f925a60 | 2044 | /* Function to be called from the debugger to print the contents |
2045 | of a bitmap. */ | |
2046 | ||
4b987fac | 2047 | DEBUG_FUNCTION void |
056755a1 | 2048 | debug_bitmap (const_bitmap head) |
2f925a60 | 2049 | { |
d72243e8 | 2050 | debug_bitmap_file (stderr, head); |
2f925a60 | 2051 | } |
ca2968e9 | 2052 | |
64c25516 | 2053 | /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file, |
23ec99a1 | 2054 | it does not print anything but the bits. */ |
2055 | ||
4b987fac | 2056 | DEBUG_FUNCTION void |
c7d89805 | 2057 | bitmap_print (FILE *file, const_bitmap head, const char *prefix, |
2058 | const char *suffix) | |
23ec99a1 | 2059 | { |
ba1d8f67 | 2060 | const char *comma = ""; |
4f917ffe | 2061 | unsigned i; |
0cc4271a | 2062 | bitmap_iterator bi; |
23ec99a1 | 2063 | |
2064 | fputs (prefix, file); | |
0cc4271a | 2065 | EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi) |
2066 | { | |
2067 | fprintf (file, "%s%d", comma, i); | |
2068 | comma = ", "; | |
2069 | } | |
23ec99a1 | 2070 | fputs (suffix, file); |
2071 | } | |
f65ffe0d | 2072 | |
f65ffe0d | 2073 | /* Output per-bitmap memory usage statistics. */ |
2074 | void | |
2075 | dump_bitmap_statistics (void) | |
2076 | { | |
f34a836c | 2077 | if (!GATHER_STATISTICS) |
ecd52ea9 | 2078 | return; |
2079 | ||
a80feb6c | 2080 | bitmap_mem_desc.dump (BITMAP_ORIGIN); |
844ea20e | 2081 | } |
2082 | ||
c7d89805 | 2083 | DEBUG_FUNCTION void |
b3e7c666 | 2084 | debug (const bitmap_head &ref) |
c7d89805 | 2085 | { |
2086 | dump_bitmap (stderr, &ref); | |
2087 | } | |
2088 | ||
2089 | DEBUG_FUNCTION void | |
b3e7c666 | 2090 | debug (const bitmap_head *ptr) |
c7d89805 | 2091 | { |
2092 | if (ptr) | |
2093 | debug (*ptr); | |
2094 | else | |
2095 | fprintf (stderr, "<nil>\n"); | |
2096 | } | |
2097 | ||
2098 | ||
1f3233d1 | 2099 | #include "gt-bitmap.h" |