]>
Commit | Line | Data |
---|---|---|
2f925a60 | 1 | /* Functions to support general ended bitmaps. |
fbd26352 | 2 | Copyright (C) 1997-2019 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" |
d6cb6164 | 23 | #include "bitmap.h" |
99b4f3a2 | 24 | #include "selftest.h" |
f65ffe0d | 25 | |
0ff42de5 | 26 | /* Memory allocation statistics purpose instance. */ |
27 | mem_alloc_description<bitmap_usage> bitmap_mem_desc; | |
f65ffe0d | 28 | |
7da7f1c6 | 29 | /* Static zero-initialized bitmap obstack used for default initialization |
30 | of bitmap_head. */ | |
31 | bitmap_obstack bitmap_head::crashme; | |
32 | ||
e35f850e | 33 | static bitmap_element *bitmap_tree_listify_from (bitmap, bitmap_element *); |
34 | ||
f65ffe0d | 35 | /* Register new bitmap. */ |
36 | void | |
37 | bitmap_register (bitmap b MEM_STAT_DECL) | |
38 | { | |
ebaae53f | 39 | static unsigned alloc_descriptor_max_uid = 1; |
40 | gcc_assert (b->alloc_descriptor == 0); | |
41 | b->alloc_descriptor = alloc_descriptor_max_uid++; | |
42 | ||
43 | bitmap_mem_desc.register_descriptor (b->get_descriptor (), BITMAP_ORIGIN, | |
44 | false FINAL_PASS_MEM_STAT); | |
f65ffe0d | 45 | } |
46 | ||
47 | /* Account the overhead. */ | |
48 | static void | |
462aa751 | 49 | register_overhead (bitmap b, size_t amount) |
f65ffe0d | 50 | { |
ebaae53f | 51 | unsigned *d = b->get_descriptor (); |
52 | if (bitmap_mem_desc.contains_descriptor_for_instance (d)) | |
53 | bitmap_mem_desc.register_instance_overhead (amount, d); | |
54 | } | |
55 | ||
56 | /* Release the overhead. */ | |
57 | static void | |
58 | release_overhead (bitmap b, size_t amount, bool remove_from_map) | |
59 | { | |
60 | unsigned *d = b->get_descriptor (); | |
61 | if (bitmap_mem_desc.contains_descriptor_for_instance (d)) | |
62 | bitmap_mem_desc.release_instance_overhead (d, amount, remove_from_map); | |
f65ffe0d | 63 | } |
2f925a60 | 64 | |
ebaae53f | 65 | |
2f925a60 | 66 | /* Global data */ |
42fe97ed | 67 | bitmap_element bitmap_zero_bits; /* An element of all zero bits. */ |
68 | bitmap_obstack bitmap_default_obstack; /* The default bitmap obstack. */ | |
fd6481cf | 69 | static int bitmap_default_obstack_depth; |
42fe97ed | 70 | static GTY((deletable)) bitmap_element *bitmap_ggc_free; /* Freelist of |
71 | GC'd elements. */ | |
2f925a60 | 72 | |
2f925a60 | 73 | \f |
e35f850e | 74 | /* Bitmap memory management. */ |
b6e72c17 | 75 | |
e35f850e | 76 | /* Add ELT to the appropriate freelist. */ |
702216e3 | 77 | static inline void |
aecda0d6 | 78 | bitmap_elem_to_freelist (bitmap head, bitmap_element *elt) |
1f3233d1 | 79 | { |
42fe97ed | 80 | bitmap_obstack *bit_obstack = head->obstack; |
a0c938f0 | 81 | |
e35f850e | 82 | if (GATHER_STATISTICS) |
ebaae53f | 83 | release_overhead (head, sizeof (bitmap_element), false); |
e35f850e | 84 | |
4bc590db | 85 | elt->next = NULL; |
f79643b7 | 86 | elt->indx = -1; |
42fe97ed | 87 | if (bit_obstack) |
1f3233d1 | 88 | { |
4bc590db | 89 | elt->prev = bit_obstack->elements; |
42fe97ed | 90 | bit_obstack->elements = elt; |
1f3233d1 | 91 | } |
92 | else | |
93 | { | |
4bc590db | 94 | elt->prev = bitmap_ggc_free; |
1f3233d1 | 95 | bitmap_ggc_free = elt; |
96 | } | |
97 | } | |
98 | ||
2f925a60 | 99 | /* Allocate a bitmap element. The bits are cleared, but nothing else is. */ |
100 | ||
702216e3 | 101 | static inline bitmap_element * |
aecda0d6 | 102 | bitmap_element_allocate (bitmap head) |
2f925a60 | 103 | { |
104 | bitmap_element *element; | |
42fe97ed | 105 | bitmap_obstack *bit_obstack = head->obstack; |
a0c938f0 | 106 | |
42fe97ed | 107 | if (bit_obstack) |
23ec99a1 | 108 | { |
42fe97ed | 109 | element = bit_obstack->elements; |
a0c938f0 | 110 | |
42fe97ed | 111 | if (element) |
4bc590db | 112 | /* Use up the inner list first before looking at the next |
113 | element of the outer list. */ | |
114 | if (element->next) | |
115 | { | |
116 | bit_obstack->elements = element->next; | |
117 | bit_obstack->elements->prev = element->prev; | |
118 | } | |
119 | else | |
120 | /* Inner list was just a singleton. */ | |
121 | bit_obstack->elements = element->prev; | |
1f3233d1 | 122 | else |
42fe97ed | 123 | element = XOBNEW (&bit_obstack->obstack, bitmap_element); |
1f3233d1 | 124 | } |
125 | else | |
126 | { | |
42fe97ed | 127 | element = bitmap_ggc_free; |
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 | bitmap_ggc_free = element->next; | |
134 | bitmap_ggc_free->prev = element->prev; | |
135 | } | |
136 | else | |
137 | /* Inner list was just a singleton. */ | |
138 | bitmap_ggc_free = element->prev; | |
1f3233d1 | 139 | else |
25a27413 | 140 | element = ggc_alloc<bitmap_element> (); |
23ec99a1 | 141 | } |
2f925a60 | 142 | |
ecd52ea9 | 143 | if (GATHER_STATISTICS) |
144 | register_overhead (head, sizeof (bitmap_element)); | |
145 | ||
ca2968e9 | 146 | memset (element->bits, 0, sizeof (element->bits)); |
2f925a60 | 147 | |
148 | return element; | |
149 | } | |
150 | ||
e35f850e | 151 | /* Remove ELT and all following elements from bitmap HEAD. |
152 | Put the released elements in the freelist for HEAD. */ | |
114c7df6 | 153 | |
154 | void | |
42fe97ed | 155 | bitmap_elt_clear_from (bitmap head, bitmap_element *elt) |
156 | { | |
4bc590db | 157 | bitmap_element *prev; |
158 | bitmap_obstack *bit_obstack = head->obstack; | |
159 | ||
e35f850e | 160 | if (!elt) |
161 | return; | |
162 | ||
163 | if (head->tree_form) | |
164 | elt = bitmap_tree_listify_from (head, elt); | |
ecd52ea9 | 165 | |
166 | if (GATHER_STATISTICS) | |
167 | { | |
168 | int n = 0; | |
169 | for (prev = elt; prev; prev = prev->next) | |
170 | n++; | |
ebaae53f | 171 | release_overhead (head, sizeof (bitmap_element) * n, false); |
ecd52ea9 | 172 | } |
42fe97ed | 173 | |
4bc590db | 174 | prev = elt->prev; |
175 | if (prev) | |
176 | { | |
177 | prev->next = NULL; | |
178 | if (head->current->indx > prev->indx) | |
179 | { | |
180 | head->current = prev; | |
181 | head->indx = prev->indx; | |
182 | } | |
a0c938f0 | 183 | } |
4bc590db | 184 | else |
185 | { | |
186 | head->first = NULL; | |
187 | head->current = NULL; | |
188 | head->indx = 0; | |
189 | } | |
190 | ||
e35f850e | 191 | /* Put the entire list onto the freelist in one operation. */ |
4bc590db | 192 | if (bit_obstack) |
42fe97ed | 193 | { |
a0c938f0 | 194 | elt->prev = bit_obstack->elements; |
4bc590db | 195 | bit_obstack->elements = elt; |
196 | } | |
197 | else | |
198 | { | |
e35f850e | 199 | elt->prev = bitmap_ggc_free; |
200 | bitmap_ggc_free = elt; | |
201 | } | |
202 | } | |
203 | \f | |
204 | /* Linked-list view of bitmaps. | |
205 | ||
206 | In this representation, the bitmap elements form a double-linked list | |
207 | with elements sorted by increasing index. */ | |
208 | ||
209 | /* Link the bitmap element into the current bitmap linked list. */ | |
210 | ||
211 | static inline void | |
212 | bitmap_list_link_element (bitmap head, bitmap_element *element) | |
213 | { | |
214 | unsigned int indx = element->indx; | |
215 | bitmap_element *ptr; | |
216 | ||
217 | gcc_checking_assert (!head->tree_form); | |
218 | ||
219 | /* If this is the first and only element, set it in. */ | |
220 | if (head->first == 0) | |
221 | { | |
222 | element->next = element->prev = 0; | |
223 | head->first = element; | |
224 | } | |
225 | ||
226 | /* If this index is less than that of the current element, it goes someplace | |
227 | before the current element. */ | |
228 | else if (indx < head->indx) | |
229 | { | |
230 | for (ptr = head->current; | |
231 | ptr->prev != 0 && ptr->prev->indx > indx; | |
232 | ptr = ptr->prev) | |
233 | ; | |
234 | ||
235 | if (ptr->prev) | |
236 | ptr->prev->next = element; | |
237 | else | |
238 | head->first = element; | |
239 | ||
240 | element->prev = ptr->prev; | |
241 | element->next = ptr; | |
242 | ptr->prev = element; | |
243 | } | |
244 | ||
245 | /* Otherwise, it must go someplace after the current element. */ | |
246 | else | |
247 | { | |
248 | for (ptr = head->current; | |
249 | ptr->next != 0 && ptr->next->indx < indx; | |
250 | ptr = ptr->next) | |
251 | ; | |
252 | ||
253 | if (ptr->next) | |
254 | ptr->next->prev = element; | |
255 | ||
256 | element->next = ptr->next; | |
257 | element->prev = ptr; | |
258 | ptr->next = element; | |
259 | } | |
260 | ||
261 | /* Set up so this is the first element searched. */ | |
262 | head->current = element; | |
263 | head->indx = indx; | |
264 | } | |
265 | ||
266 | /* Unlink the bitmap element from the current bitmap linked list, | |
267 | and return it to the freelist. */ | |
268 | ||
269 | static inline void | |
80c7cb9d | 270 | bitmap_list_unlink_element (bitmap head, bitmap_element *element, |
271 | bool to_freelist = true) | |
e35f850e | 272 | { |
273 | bitmap_element *next = element->next; | |
274 | bitmap_element *prev = element->prev; | |
275 | ||
276 | gcc_checking_assert (!head->tree_form); | |
277 | ||
278 | if (prev) | |
279 | prev->next = next; | |
280 | ||
281 | if (next) | |
282 | next->prev = prev; | |
283 | ||
284 | if (head->first == element) | |
285 | head->first = next; | |
286 | ||
287 | /* Since the first thing we try is to insert before current, | |
288 | make current the next entry in preference to the previous. */ | |
289 | if (head->current == element) | |
290 | { | |
291 | head->current = next != 0 ? next : prev; | |
292 | if (head->current) | |
293 | head->indx = head->current->indx; | |
294 | else | |
295 | head->indx = 0; | |
296 | } | |
297 | ||
80c7cb9d | 298 | if (to_freelist) |
299 | bitmap_elem_to_freelist (head, element); | |
e35f850e | 300 | } |
301 | ||
80c7cb9d | 302 | /* Insert a new uninitialized element (or NODE if not NULL) into bitmap |
303 | HEAD after element ELT. If ELT is NULL, insert the element at the start. | |
304 | Return the new element. */ | |
e35f850e | 305 | |
306 | static bitmap_element * | |
307 | bitmap_list_insert_element_after (bitmap head, | |
80c7cb9d | 308 | bitmap_element *elt, unsigned int indx, |
309 | bitmap_element *node = NULL) | |
e35f850e | 310 | { |
80c7cb9d | 311 | if (!node) |
312 | node = bitmap_element_allocate (head); | |
e35f850e | 313 | node->indx = indx; |
314 | ||
315 | gcc_checking_assert (!head->tree_form); | |
316 | ||
317 | if (!elt) | |
318 | { | |
319 | if (!head->current) | |
320 | { | |
321 | head->current = node; | |
322 | head->indx = indx; | |
323 | } | |
324 | node->next = head->first; | |
325 | if (node->next) | |
326 | node->next->prev = node; | |
327 | head->first = node; | |
328 | node->prev = NULL; | |
329 | } | |
330 | else | |
331 | { | |
332 | gcc_checking_assert (head->current); | |
333 | node->next = elt->next; | |
334 | if (node->next) | |
335 | node->next->prev = node; | |
336 | elt->next = node; | |
337 | node->prev = elt; | |
338 | } | |
339 | return node; | |
340 | } | |
341 | ||
342 | /* Return the element for INDX, or NULL if the element doesn't exist. | |
343 | Update the `current' field even if we can't find an element that | |
344 | would hold the bitmap's bit to make eventual allocation | |
345 | faster. */ | |
346 | ||
347 | static inline bitmap_element * | |
348 | bitmap_list_find_element (bitmap head, unsigned int indx) | |
349 | { | |
350 | bitmap_element *element; | |
351 | ||
352 | if (head->current == NULL | |
353 | || head->indx == indx) | |
354 | return head->current; | |
355 | ||
356 | if (head->current == head->first | |
357 | && head->first->next == NULL) | |
358 | return NULL; | |
359 | ||
360 | /* Usage can be NULL due to allocated bitmaps for which we do not | |
361 | call initialize function. */ | |
362 | bitmap_usage *usage = NULL; | |
363 | if (GATHER_STATISTICS) | |
364 | usage = bitmap_mem_desc.get_descriptor_for_instance (head); | |
365 | ||
366 | /* This bitmap has more than one element, and we're going to look | |
367 | through the elements list. Count that as a search. */ | |
368 | if (GATHER_STATISTICS && usage) | |
369 | usage->m_nsearches++; | |
370 | ||
371 | if (head->indx < indx) | |
372 | /* INDX is beyond head->indx. Search from head->current | |
373 | forward. */ | |
374 | for (element = head->current; | |
375 | element->next != 0 && element->indx < indx; | |
376 | element = element->next) | |
377 | { | |
378 | if (GATHER_STATISTICS && usage) | |
379 | usage->m_search_iter++; | |
380 | } | |
381 | ||
382 | else if (head->indx / 2 < indx) | |
383 | /* INDX is less than head->indx and closer to head->indx than to | |
384 | 0. Search from head->current backward. */ | |
385 | for (element = head->current; | |
386 | element->prev != 0 && element->indx > indx; | |
387 | element = element->prev) | |
388 | { | |
389 | if (GATHER_STATISTICS && usage) | |
390 | usage->m_search_iter++; | |
391 | } | |
392 | ||
393 | else | |
394 | /* INDX is less than head->indx and closer to 0 than to | |
395 | head->indx. Search from head->first forward. */ | |
396 | for (element = head->first; | |
397 | element->next != 0 && element->indx < indx; | |
398 | element = element->next) | |
399 | { | |
400 | if (GATHER_STATISTICS && usage) | |
401 | usage->m_search_iter++; | |
402 | } | |
403 | ||
404 | /* `element' is the nearest to the one we want. If it's not the one we | |
405 | want, the one we want doesn't exist. */ | |
406 | gcc_checking_assert (element != NULL); | |
407 | head->current = element; | |
408 | head->indx = element->indx; | |
409 | if (element->indx != indx) | |
410 | element = 0; | |
411 | return element; | |
412 | } | |
413 | ||
414 | \f | |
415 | /* Splay-tree view of bitmaps. | |
416 | ||
417 | This is an almost one-to-one the implementatin of the simple top-down | |
418 | splay tree in Sleator and Tarjan's "Self-adjusting Binary Search Trees". | |
419 | It is probably not the most efficient form of splay trees, but it should | |
420 | be good enough to experiment with this idea of bitmaps-as-trees. | |
421 | ||
422 | For all functions below, the variable or function argument "t" is a node | |
423 | in the tree, and "e" is a temporary or new node in the tree. The rest | |
424 | is sufficiently straigh-forward (and very well explained in the paper) | |
425 | that comment would only clutter things. */ | |
426 | ||
427 | static inline void | |
428 | bitmap_tree_link_left (bitmap_element * &t, bitmap_element * &l) | |
429 | { | |
430 | l->next = t; | |
431 | l = t; | |
432 | t = t->next; | |
433 | } | |
434 | ||
435 | static inline void | |
436 | bitmap_tree_link_right (bitmap_element * &t, bitmap_element * &r) | |
437 | { | |
438 | r->prev = t; | |
439 | r = t; | |
440 | t = t->prev; | |
441 | } | |
442 | ||
443 | static inline void | |
444 | bitmap_tree_rotate_left (bitmap_element * &t) | |
445 | { | |
446 | bitmap_element *e = t->next; | |
447 | t->next = t->next->prev; | |
448 | e->prev = t; | |
449 | t = e; | |
450 | } | |
451 | ||
452 | static inline void | |
453 | bitmap_tree_rotate_right (bitmap_element * &t) | |
454 | { | |
455 | bitmap_element *e = t->prev; | |
456 | t->prev = t->prev->next; | |
457 | e->next = t; | |
458 | t = e; | |
459 | } | |
460 | ||
461 | static bitmap_element * | |
462 | bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx) | |
463 | { | |
464 | bitmap_element N, *l, *r; | |
465 | ||
466 | if (t == NULL) | |
467 | return NULL; | |
468 | ||
469 | bitmap_usage *usage = NULL; | |
470 | if (GATHER_STATISTICS) | |
471 | usage = bitmap_mem_desc.get_descriptor_for_instance (head); | |
472 | ||
473 | N.prev = N.next = NULL; | |
474 | l = r = &N; | |
475 | ||
476 | while (indx != t->indx) | |
477 | { | |
478 | if (GATHER_STATISTICS && usage) | |
479 | usage->m_search_iter++; | |
480 | ||
481 | if (indx < t->indx) | |
482 | { | |
483 | if (t->prev != NULL && indx < t->prev->indx) | |
484 | bitmap_tree_rotate_right (t); | |
485 | if (t->prev == NULL) | |
486 | break; | |
487 | bitmap_tree_link_right (t, r); | |
488 | } | |
489 | else if (indx > t->indx) | |
490 | { | |
491 | if (t->next != NULL && indx > t->next->indx) | |
492 | bitmap_tree_rotate_left (t); | |
493 | if (t->next == NULL) | |
494 | break; | |
495 | bitmap_tree_link_left (t, l); | |
496 | } | |
497 | } | |
498 | ||
499 | l->next = t->prev; | |
500 | r->prev = t->next; | |
501 | t->prev = N.next; | |
502 | t->next = N.prev; | |
503 | return t; | |
504 | } | |
505 | ||
506 | /* Link bitmap element E into the current bitmap splay tree. */ | |
507 | ||
508 | static inline void | |
509 | bitmap_tree_link_element (bitmap head, bitmap_element *e) | |
510 | { | |
511 | if (head->first == NULL) | |
512 | e->prev = e->next = NULL; | |
513 | else | |
514 | { | |
515 | bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx); | |
516 | if (e->indx < t->indx) | |
517 | { | |
518 | e->prev = t->prev; | |
519 | e->next = t; | |
520 | t->prev = NULL; | |
521 | } | |
522 | else if (e->indx > t->indx) | |
523 | { | |
524 | e->next = t->next; | |
525 | e->prev = t; | |
526 | t->next = NULL; | |
527 | } | |
528 | else | |
529 | gcc_unreachable (); | |
530 | } | |
531 | head->first = e; | |
532 | head->current = e; | |
533 | head->indx = e->indx; | |
534 | } | |
535 | ||
536 | /* Unlink bitmap element E from the current bitmap splay tree, | |
537 | and return it to the freelist. */ | |
538 | ||
539 | static void | |
540 | bitmap_tree_unlink_element (bitmap head, bitmap_element *e) | |
541 | { | |
542 | bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx); | |
543 | ||
544 | gcc_checking_assert (t == e); | |
545 | ||
546 | if (e->prev == NULL) | |
547 | t = e->next; | |
548 | else | |
549 | { | |
550 | t = bitmap_tree_splay (head, e->prev, e->indx); | |
551 | t->next = e->next; | |
552 | } | |
553 | head->first = t; | |
554 | head->current = t; | |
555 | head->indx = (t != NULL) ? t->indx : 0; | |
556 | ||
557 | bitmap_elem_to_freelist (head, e); | |
558 | } | |
559 | ||
560 | /* Return the element for INDX, or NULL if the element doesn't exist. */ | |
561 | ||
562 | static inline bitmap_element * | |
563 | bitmap_tree_find_element (bitmap head, unsigned int indx) | |
564 | { | |
565 | if (head->current == NULL | |
566 | || head->indx == indx) | |
567 | return head->current; | |
568 | ||
569 | /* Usage can be NULL due to allocated bitmaps for which we do not | |
570 | call initialize function. */ | |
571 | bitmap_usage *usage = NULL; | |
572 | if (GATHER_STATISTICS) | |
573 | usage = bitmap_mem_desc.get_descriptor_for_instance (head); | |
574 | ||
575 | /* This bitmap has more than one element, and we're going to look | |
576 | through the elements list. Count that as a search. */ | |
577 | if (GATHER_STATISTICS && usage) | |
578 | usage->m_nsearches++; | |
579 | ||
580 | bitmap_element *element = bitmap_tree_splay (head, head->first, indx); | |
581 | gcc_checking_assert (element != NULL); | |
582 | head->first = element; | |
583 | head->current = element; | |
584 | head->indx = element->indx; | |
585 | if (element->indx != indx) | |
586 | element = 0; | |
587 | return element; | |
588 | } | |
589 | \f | |
590 | /* Converting bitmap views from linked-list to tree and vice versa. */ | |
591 | ||
592 | /* Splice element E and all elements with a larger index from | |
593 | bitmap HEAD, convert the spliced elements to the linked-list | |
594 | view, and return the head of the list (which should be E again), */ | |
595 | ||
596 | static bitmap_element * | |
597 | bitmap_tree_listify_from (bitmap head, bitmap_element *e) | |
598 | { | |
599 | bitmap_element *t, *erb; | |
600 | ||
601 | /* Detach the right branch from E (all elements with indx > E->indx), | |
602 | and splay E to the root. */ | |
603 | erb = e->next; | |
604 | e->next = NULL; | |
605 | t = bitmap_tree_splay (head, head->first, e->indx); | |
606 | gcc_checking_assert (t == e); | |
607 | ||
608 | /* Because E has no right branch, and we rotated it to the root, | |
609 | the left branch is the new root. */ | |
610 | t = e->prev; | |
611 | head->first = t; | |
612 | head->current = t; | |
613 | head->indx = (t != NULL) ? t->indx : 0; | |
614 | ||
615 | /* Detach the tree from E, and re-attach the right branch of E. */ | |
616 | e->prev = NULL; | |
617 | e->next = erb; | |
618 | ||
619 | /* The tree is now valid again. Now we need to "un-tree" E. | |
620 | It is imperative that a non-recursive implementation is used | |
621 | for this, because splay trees have a worst case depth of O(N) | |
622 | for a tree with N nodes. A recursive implementation could | |
623 | result in a stack overflow for a sufficiently large, unbalanced | |
624 | bitmap tree. */ | |
625 | ||
626 | auto_vec<bitmap_element *, 32> stack; | |
627 | auto_vec<bitmap_element *, 32> sorted_elements; | |
628 | bitmap_element *n = e; | |
629 | ||
630 | while (true) | |
631 | { | |
632 | while (n != NULL) | |
633 | { | |
634 | stack.safe_push (n); | |
635 | n = n->prev; | |
636 | } | |
637 | ||
638 | if (stack.is_empty ()) | |
639 | break; | |
640 | ||
641 | n = stack.pop (); | |
642 | sorted_elements.safe_push (n); | |
643 | n = n->next; | |
644 | } | |
645 | ||
646 | gcc_assert (sorted_elements[0] == e); | |
647 | ||
648 | bitmap_element *prev = NULL; | |
649 | unsigned ix; | |
650 | FOR_EACH_VEC_ELT (sorted_elements, ix, n) | |
651 | { | |
652 | if (prev != NULL) | |
653 | prev->next = n; | |
654 | n->prev = prev; | |
655 | n->next = NULL; | |
656 | prev = n; | |
657 | } | |
658 | ||
659 | return e; | |
660 | } | |
661 | ||
662 | /* Convert bitmap HEAD from splay-tree view to linked-list view. */ | |
663 | ||
664 | void | |
665 | bitmap_list_view (bitmap head) | |
666 | { | |
667 | bitmap_element *ptr; | |
668 | ||
669 | gcc_assert (head->tree_form); | |
670 | ||
671 | ptr = head->first; | |
672 | if (ptr) | |
673 | { | |
674 | while (ptr->prev) | |
675 | bitmap_tree_rotate_right (ptr); | |
676 | head->first = ptr; | |
677 | head->first = bitmap_tree_listify_from (head, ptr); | |
42fe97ed | 678 | } |
e35f850e | 679 | |
680 | head->tree_form = false; | |
42fe97ed | 681 | } |
682 | ||
e35f850e | 683 | /* Convert bitmap HEAD from linked-list view to splay-tree view. |
684 | This is simply a matter of dropping the prev or next pointers | |
685 | and setting the tree_form flag. The tree will balance itself | |
686 | if and when it is used. */ | |
687 | ||
688 | void | |
689 | bitmap_tree_view (bitmap head) | |
690 | { | |
691 | bitmap_element *ptr; | |
692 | ||
693 | gcc_assert (! head->tree_form); | |
694 | ||
695 | ptr = head->first; | |
696 | while (ptr) | |
697 | { | |
698 | ptr->prev = NULL; | |
699 | ptr = ptr->next; | |
700 | } | |
701 | ||
702 | head->tree_form = true; | |
703 | } | |
704 | \f | |
705 | /* Clear a bitmap by freeing all its elements. */ | |
42fe97ed | 706 | |
c623bf22 | 707 | void |
42fe97ed | 708 | bitmap_clear (bitmap head) |
114c7df6 | 709 | { |
e35f850e | 710 | if (head->first == NULL) |
711 | return; | |
712 | if (head->tree_form) | |
713 | { | |
714 | bitmap_element *e, *t; | |
715 | for (e = head->first; e->prev; e = e->prev) | |
716 | /* Loop to find the element with the smallest index. */ ; | |
717 | t = bitmap_tree_splay (head, head->first, e->indx); | |
718 | gcc_checking_assert (t == e); | |
719 | head->first = t; | |
720 | } | |
721 | bitmap_elt_clear_from (head, head->first); | |
42fe97ed | 722 | } |
723 | \f | |
724 | /* Initialize a bitmap obstack. If BIT_OBSTACK is NULL, initialize | |
725 | the default bitmap obstack. */ | |
726 | ||
727 | void | |
728 | bitmap_obstack_initialize (bitmap_obstack *bit_obstack) | |
729 | { | |
730 | if (!bit_obstack) | |
fd6481cf | 731 | { |
732 | if (bitmap_default_obstack_depth++) | |
733 | return; | |
734 | bit_obstack = &bitmap_default_obstack; | |
735 | } | |
42fe97ed | 736 | |
737 | #if !defined(__GNUC__) || (__GNUC__ < 2) | |
738 | #define __alignof__(type) 0 | |
739 | #endif | |
740 | ||
741 | bit_obstack->elements = NULL; | |
742 | bit_obstack->heads = NULL; | |
743 | obstack_specify_allocation (&bit_obstack->obstack, OBSTACK_CHUNK_SIZE, | |
744 | __alignof__ (bitmap_element), | |
745 | obstack_chunk_alloc, | |
746 | obstack_chunk_free); | |
114c7df6 | 747 | } |
748 | ||
42fe97ed | 749 | /* Release the memory from a bitmap obstack. If BIT_OBSTACK is NULL, |
750 | release the default bitmap obstack. */ | |
751 | ||
752 | void | |
753 | bitmap_obstack_release (bitmap_obstack *bit_obstack) | |
754 | { | |
755 | if (!bit_obstack) | |
fd6481cf | 756 | { |
757 | if (--bitmap_default_obstack_depth) | |
758 | { | |
759 | gcc_assert (bitmap_default_obstack_depth > 0); | |
760 | return; | |
761 | } | |
762 | bit_obstack = &bitmap_default_obstack; | |
763 | } | |
a0c938f0 | 764 | |
42fe97ed | 765 | bit_obstack->elements = NULL; |
766 | bit_obstack->heads = NULL; | |
767 | obstack_free (&bit_obstack->obstack, NULL); | |
768 | } | |
769 | ||
770 | /* Create a new bitmap on an obstack. If BIT_OBSTACK is NULL, create | |
771 | it on the default bitmap obstack. */ | |
772 | ||
773 | bitmap | |
c163347d | 774 | bitmap_alloc (bitmap_obstack *bit_obstack MEM_STAT_DECL) |
42fe97ed | 775 | { |
776 | bitmap map; | |
777 | ||
778 | if (!bit_obstack) | |
779 | bit_obstack = &bitmap_default_obstack; | |
780 | map = bit_obstack->heads; | |
781 | if (map) | |
2e966e2a | 782 | bit_obstack->heads = (class bitmap_head *) map->first; |
42fe97ed | 783 | else |
784 | map = XOBNEW (&bit_obstack->obstack, bitmap_head); | |
076121e0 | 785 | bitmap_initialize (map, bit_obstack PASS_MEM_STAT); |
ecd52ea9 | 786 | |
787 | if (GATHER_STATISTICS) | |
788 | register_overhead (map, sizeof (bitmap_head)); | |
42fe97ed | 789 | |
790 | return map; | |
791 | } | |
792 | ||
793 | /* Create a new GCd bitmap. */ | |
794 | ||
795 | bitmap | |
c163347d | 796 | bitmap_gc_alloc (ALONE_MEM_STAT_DECL) |
42fe97ed | 797 | { |
798 | bitmap map; | |
799 | ||
25a27413 | 800 | map = ggc_alloc<bitmap_head> (); |
076121e0 | 801 | bitmap_initialize (map, NULL PASS_MEM_STAT); |
ecd52ea9 | 802 | |
803 | if (GATHER_STATISTICS) | |
804 | register_overhead (map, sizeof (bitmap_head)); | |
42fe97ed | 805 | |
806 | return map; | |
807 | } | |
808 | ||
42fe97ed | 809 | /* Release an obstack allocated bitmap. */ |
810 | ||
811 | void | |
812 | bitmap_obstack_free (bitmap map) | |
813 | { | |
0e06d11a | 814 | if (map) |
815 | { | |
816 | bitmap_clear (map); | |
76cd80c7 | 817 | map->first = (bitmap_element *) map->obstack->heads; |
ecd52ea9 | 818 | |
819 | if (GATHER_STATISTICS) | |
ebaae53f | 820 | release_overhead (map, sizeof (bitmap_head), true); |
ecd52ea9 | 821 | |
0e06d11a | 822 | map->obstack->heads = map; |
823 | } | |
42fe97ed | 824 | } |
825 | ||
42fe97ed | 826 | \f |
2f925a60 | 827 | /* Return nonzero if all bits in an element are zero. */ |
828 | ||
702216e3 | 829 | static inline int |
056755a1 | 830 | bitmap_element_zerop (const bitmap_element *element) |
2f925a60 | 831 | { |
832 | #if BITMAP_ELEMENT_WORDS == 2 | |
833 | return (element->bits[0] | element->bits[1]) == 0; | |
834 | #else | |
84199e4b | 835 | unsigned i; |
2f925a60 | 836 | |
837 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
838 | if (element->bits[i] != 0) | |
839 | return 0; | |
840 | ||
841 | return 1; | |
842 | #endif | |
843 | } | |
844 | \f | |
ca2968e9 | 845 | /* Copy a bitmap to another bitmap. */ |
2f925a60 | 846 | |
847 | void | |
056755a1 | 848 | bitmap_copy (bitmap to, const_bitmap from) |
2f925a60 | 849 | { |
056755a1 | 850 | const bitmap_element *from_ptr; |
851 | bitmap_element *to_ptr = 0; | |
2f925a60 | 852 | |
e35f850e | 853 | gcc_checking_assert (!to->tree_form && !from->tree_form); |
854 | ||
2f925a60 | 855 | bitmap_clear (to); |
856 | ||
2358393e | 857 | /* Copy elements in forward direction one at a time. */ |
2f925a60 | 858 | for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next) |
859 | { | |
1f3233d1 | 860 | bitmap_element *to_elt = bitmap_element_allocate (to); |
2f925a60 | 861 | |
862 | to_elt->indx = from_ptr->indx; | |
3c47d200 | 863 | memcpy (to_elt->bits, from_ptr->bits, sizeof (to_elt->bits)); |
2f925a60 | 864 | |
e35f850e | 865 | /* Here we have a special case of bitmap_list_link_element, |
866 | for the case where we know the links are being entered | |
867 | in sequence. */ | |
2f925a60 | 868 | if (to_ptr == 0) |
869 | { | |
870 | to->first = to->current = to_elt; | |
871 | to->indx = from_ptr->indx; | |
872 | to_elt->next = to_elt->prev = 0; | |
873 | } | |
874 | else | |
875 | { | |
876 | to_elt->prev = to_ptr; | |
877 | to_elt->next = 0; | |
878 | to_ptr->next = to_elt; | |
879 | } | |
880 | ||
881 | to_ptr = to_elt; | |
882 | } | |
883 | } | |
462aa751 | 884 | |
885 | /* Move a bitmap to another bitmap. */ | |
886 | ||
887 | void | |
888 | bitmap_move (bitmap to, bitmap from) | |
889 | { | |
890 | gcc_assert (to->obstack == from->obstack); | |
891 | ||
892 | bitmap_clear (to); | |
893 | ||
ebaae53f | 894 | size_t sz = 0; |
462aa751 | 895 | if (GATHER_STATISTICS) |
896 | { | |
462aa751 | 897 | for (bitmap_element *e = to->first; e; e = e->next) |
898 | sz += sizeof (bitmap_element); | |
899 | register_overhead (to, sz); | |
462aa751 | 900 | } |
ebaae53f | 901 | |
902 | *to = *from; | |
903 | ||
904 | if (GATHER_STATISTICS) | |
905 | release_overhead (from, sz, false); | |
462aa751 | 906 | } |
2f925a60 | 907 | \f |
b64035d2 | 908 | /* Clear a single bit in a bitmap. Return true if the bit changed. */ |
2f925a60 | 909 | |
b64035d2 | 910 | bool |
aecda0d6 | 911 | bitmap_clear_bit (bitmap head, int bit) |
2f925a60 | 912 | { |
e35f850e | 913 | unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; |
914 | bitmap_element *ptr; | |
2f925a60 | 915 | |
e35f850e | 916 | if (!head->tree_form) |
917 | ptr = bitmap_list_find_element (head, indx); | |
918 | else | |
919 | ptr = bitmap_tree_find_element (head, indx); | |
2f925a60 | 920 | if (ptr != 0) |
921 | { | |
e5c8f082 | 922 | unsigned bit_num = bit % BITMAP_WORD_BITS; |
923 | unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
b64035d2 | 924 | BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; |
925 | bool res = (ptr->bits[word_num] & bit_val) != 0; | |
926 | if (res) | |
a98d46f2 | 927 | { |
928 | ptr->bits[word_num] &= ~bit_val; | |
929 | /* If we cleared the entire word, free up the element. */ | |
930 | if (!ptr->bits[word_num] | |
931 | && bitmap_element_zerop (ptr)) | |
e35f850e | 932 | { |
933 | if (!head->tree_form) | |
934 | bitmap_list_unlink_element (head, ptr); | |
935 | else | |
936 | bitmap_tree_unlink_element (head, ptr); | |
937 | } | |
a98d46f2 | 938 | } |
b64035d2 | 939 | |
940 | return res; | |
2f925a60 | 941 | } |
b64035d2 | 942 | |
943 | return false; | |
2f925a60 | 944 | } |
945 | ||
b64035d2 | 946 | /* Set a single bit in a bitmap. Return true if the bit changed. */ |
2f925a60 | 947 | |
b64035d2 | 948 | bool |
aecda0d6 | 949 | bitmap_set_bit (bitmap head, int bit) |
2f925a60 | 950 | { |
e35f850e | 951 | unsigned indx = bit / BITMAP_ELEMENT_ALL_BITS; |
952 | bitmap_element *ptr; | |
953 | if (!head->tree_form) | |
954 | ptr = bitmap_list_find_element (head, indx); | |
955 | else | |
956 | ptr = bitmap_tree_find_element (head, indx); | |
e5c8f082 | 957 | unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; |
958 | unsigned bit_num = bit % BITMAP_WORD_BITS; | |
959 | BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num; | |
2f925a60 | 960 | |
e35f850e | 961 | if (ptr != 0) |
b64035d2 | 962 | { |
963 | bool res = (ptr->bits[word_num] & bit_val) == 0; | |
964 | if (res) | |
965 | ptr->bits[word_num] |= bit_val; | |
966 | return res; | |
967 | } | |
e35f850e | 968 | |
969 | ptr = bitmap_element_allocate (head); | |
970 | ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS; | |
971 | ptr->bits[word_num] = bit_val; | |
972 | if (!head->tree_form) | |
973 | bitmap_list_link_element (head, ptr); | |
974 | else | |
975 | bitmap_tree_link_element (head, ptr); | |
976 | return true; | |
2f925a60 | 977 | } |
ca2968e9 | 978 | |
2f925a60 | 979 | /* Return whether a bit is set within a bitmap. */ |
980 | ||
981 | int | |
aecda0d6 | 982 | bitmap_bit_p (bitmap head, int bit) |
2f925a60 | 983 | { |
e35f850e | 984 | unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS; |
2f925a60 | 985 | bitmap_element *ptr; |
986 | unsigned bit_num; | |
987 | unsigned word_num; | |
988 | ||
e35f850e | 989 | if (!head->tree_form) |
990 | ptr = bitmap_list_find_element (head, indx); | |
991 | else | |
992 | ptr = bitmap_tree_find_element (head, indx); | |
2f925a60 | 993 | if (ptr == 0) |
994 | return 0; | |
995 | ||
e5c8f082 | 996 | bit_num = bit % BITMAP_WORD_BITS; |
997 | word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
2f925a60 | 998 | |
66b5ac3c | 999 | return (ptr->bits[word_num] >> bit_num) & 1; |
2f925a60 | 1000 | } |
1001 | \f | |
5669bd62 | 1002 | #if GCC_VERSION < 3400 |
1003 | /* Table of number of set bits in a character, indexed by value of char. */ | |
056755a1 | 1004 | static const unsigned char popcount_table[] = |
5669bd62 | 1005 | { |
1006 | 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, | |
1007 | 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, | |
1008 | 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, | |
1009 | 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, | |
1010 | 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, | |
1011 | 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, | |
1012 | 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, | |
1013 | 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, | |
1014 | }; | |
1015 | ||
1016 | static unsigned long | |
1017 | bitmap_popcount (BITMAP_WORD a) | |
1018 | { | |
1019 | unsigned long ret = 0; | |
1020 | unsigned i; | |
1021 | ||
1022 | /* Just do this the table way for now */ | |
1023 | for (i = 0; i < BITMAP_WORD_BITS; i+= 8) | |
1024 | ret += popcount_table[(a >> i) & 0xff]; | |
1025 | return ret; | |
1026 | } | |
1027 | #endif | |
db176279 | 1028 | |
1029 | /* Count and return the number of bits set in the bitmap word BITS. */ | |
1030 | static unsigned long | |
1031 | bitmap_count_bits_in_word (const BITMAP_WORD *bits) | |
1032 | { | |
1033 | unsigned long count = 0; | |
1034 | ||
1035 | for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
1036 | { | |
1037 | #if GCC_VERSION >= 3400 | |
1038 | /* Note that popcountl matches BITMAP_WORD in type, so the actual size | |
1039 | of BITMAP_WORD is not material. */ | |
1040 | count += __builtin_popcountl (bits[ix]); | |
1041 | #else | |
1042 | count += bitmap_popcount (bits[ix]); | |
1043 | #endif | |
1044 | } | |
1045 | return count; | |
1046 | } | |
1047 | ||
5669bd62 | 1048 | /* Count the number of bits set in the bitmap, and return it. */ |
1049 | ||
1050 | unsigned long | |
056755a1 | 1051 | bitmap_count_bits (const_bitmap a) |
5669bd62 | 1052 | { |
1053 | unsigned long count = 0; | |
056755a1 | 1054 | const bitmap_element *elt; |
5669bd62 | 1055 | |
e35f850e | 1056 | gcc_checking_assert (!a->tree_form); |
5669bd62 | 1057 | for (elt = a->first; elt; elt = elt->next) |
db176279 | 1058 | count += bitmap_count_bits_in_word (elt->bits); |
1059 | ||
1060 | return count; | |
1061 | } | |
1062 | ||
1063 | /* Count the number of unique bits set in A and B and return it. */ | |
1064 | ||
1065 | unsigned long | |
1066 | bitmap_count_unique_bits (const_bitmap a, const_bitmap b) | |
1067 | { | |
1068 | unsigned long count = 0; | |
1069 | const bitmap_element *elt_a, *elt_b; | |
1070 | ||
1071 | for (elt_a = a->first, elt_b = b->first; elt_a && elt_b; ) | |
5669bd62 | 1072 | { |
db176279 | 1073 | /* If we're at different indices, then count all the bits |
1074 | in the lower element. If we're at the same index, then | |
1075 | count the bits in the IOR of the two elements. */ | |
1076 | if (elt_a->indx < elt_b->indx) | |
5669bd62 | 1077 | { |
db176279 | 1078 | count += bitmap_count_bits_in_word (elt_a->bits); |
1079 | elt_a = elt_a->next; | |
1080 | } | |
1081 | else if (elt_b->indx < elt_a->indx) | |
1082 | { | |
1083 | count += bitmap_count_bits_in_word (elt_b->bits); | |
1084 | elt_b = elt_b->next; | |
1085 | } | |
1086 | else | |
1087 | { | |
1088 | BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; | |
1089 | for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
1090 | bits[ix] = elt_a->bits[ix] | elt_b->bits[ix]; | |
1091 | count += bitmap_count_bits_in_word (bits); | |
1092 | elt_a = elt_a->next; | |
1093 | elt_b = elt_b->next; | |
5669bd62 | 1094 | } |
1095 | } | |
1096 | return count; | |
1097 | } | |
a0c938f0 | 1098 | |
6bd6739a | 1099 | /* Return true if the bitmap has a single bit set. Otherwise return |
1100 | false. */ | |
1101 | ||
1102 | bool | |
1103 | bitmap_single_bit_set_p (const_bitmap a) | |
1104 | { | |
1105 | unsigned long count = 0; | |
1106 | const bitmap_element *elt; | |
1107 | unsigned ix; | |
1108 | ||
1109 | if (bitmap_empty_p (a)) | |
1110 | return false; | |
1111 | ||
1112 | elt = a->first; | |
e35f850e | 1113 | |
6bd6739a | 1114 | /* As there are no completely empty bitmap elements, a second one |
1115 | means we have more than one bit set. */ | |
e35f850e | 1116 | if (elt->next != NULL |
1117 | && (!a->tree_form || elt->prev != NULL)) | |
6bd6739a | 1118 | return false; |
1119 | ||
1120 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
1121 | { | |
1122 | #if GCC_VERSION >= 3400 | |
1123 | /* Note that popcountl matches BITMAP_WORD in type, so the actual size | |
1124 | of BITMAP_WORD is not material. */ | |
1125 | count += __builtin_popcountl (elt->bits[ix]); | |
1126 | #else | |
1127 | count += bitmap_popcount (elt->bits[ix]); | |
1128 | #endif | |
1129 | if (count > 1) | |
1130 | return false; | |
1131 | } | |
1132 | ||
1133 | return count == 1; | |
1134 | } | |
5669bd62 | 1135 | |
1136 | ||
84199e4b | 1137 | /* Return the bit number of the first set bit in the bitmap. The |
1138 | bitmap must be non-empty. */ | |
114c7df6 | 1139 | |
84199e4b | 1140 | unsigned |
056755a1 | 1141 | bitmap_first_set_bit (const_bitmap a) |
114c7df6 | 1142 | { |
056755a1 | 1143 | const bitmap_element *elt = a->first; |
84199e4b | 1144 | unsigned bit_no; |
e5c8f082 | 1145 | BITMAP_WORD word; |
84199e4b | 1146 | unsigned ix; |
a0c938f0 | 1147 | |
d16af188 | 1148 | gcc_checking_assert (elt); |
e35f850e | 1149 | |
1150 | if (a->tree_form) | |
1151 | while (elt->prev) | |
1152 | elt = elt->prev; | |
1153 | ||
84199e4b | 1154 | bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; |
1155 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
1156 | { | |
1157 | word = elt->bits[ix]; | |
1158 | if (word) | |
1159 | goto found_bit; | |
1160 | } | |
64db345d | 1161 | gcc_unreachable (); |
84199e4b | 1162 | found_bit: |
1163 | bit_no += ix * BITMAP_WORD_BITS; | |
114c7df6 | 1164 | |
84199e4b | 1165 | #if GCC_VERSION >= 3004 |
9af5ce0c | 1166 | gcc_assert (sizeof (long) == sizeof (word)); |
84199e4b | 1167 | bit_no += __builtin_ctzl (word); |
114c7df6 | 1168 | #else |
84199e4b | 1169 | /* Binary search for the first set bit. */ |
1170 | #if BITMAP_WORD_BITS > 64 | |
1171 | #error "Fill out the table." | |
114c7df6 | 1172 | #endif |
84199e4b | 1173 | #if BITMAP_WORD_BITS > 32 |
1174 | if (!(word & 0xffffffff)) | |
1175 | word >>= 32, bit_no += 32; | |
114c7df6 | 1176 | #endif |
84199e4b | 1177 | if (!(word & 0xffff)) |
1178 | word >>= 16, bit_no += 16; | |
1179 | if (!(word & 0xff)) | |
1180 | word >>= 8, bit_no += 8; | |
1181 | if (!(word & 0xf)) | |
1182 | word >>= 4, bit_no += 4; | |
1183 | if (!(word & 0x3)) | |
1184 | word >>= 2, bit_no += 2; | |
1185 | if (!(word & 0x1)) | |
1186 | word >>= 1, bit_no += 1; | |
a0c938f0 | 1187 | |
d16af188 | 1188 | gcc_checking_assert (word & 1); |
114c7df6 | 1189 | #endif |
84199e4b | 1190 | return bit_no; |
114c7df6 | 1191 | } |
ffa800d1 | 1192 | |
1193 | /* Return the bit number of the first set bit in the bitmap. The | |
1194 | bitmap must be non-empty. */ | |
1195 | ||
1196 | unsigned | |
1197 | bitmap_last_set_bit (const_bitmap a) | |
1198 | { | |
e35f850e | 1199 | const bitmap_element *elt; |
ffa800d1 | 1200 | unsigned bit_no; |
1201 | BITMAP_WORD word; | |
1202 | int ix; | |
1203 | ||
e35f850e | 1204 | if (a->tree_form) |
1205 | elt = a->first; | |
1206 | else | |
1207 | elt = a->current ? a->current : a->first; | |
d16af188 | 1208 | gcc_checking_assert (elt); |
e35f850e | 1209 | |
ffa800d1 | 1210 | while (elt->next) |
1211 | elt = elt->next; | |
e35f850e | 1212 | |
ffa800d1 | 1213 | bit_no = elt->indx * BITMAP_ELEMENT_ALL_BITS; |
693a7077 | 1214 | for (ix = BITMAP_ELEMENT_WORDS - 1; ix >= 1; ix--) |
ffa800d1 | 1215 | { |
1216 | word = elt->bits[ix]; | |
1217 | if (word) | |
1218 | goto found_bit; | |
1219 | } | |
693a7077 | 1220 | gcc_assert (elt->bits[ix] != 0); |
ffa800d1 | 1221 | found_bit: |
1222 | bit_no += ix * BITMAP_WORD_BITS; | |
ffa800d1 | 1223 | #if GCC_VERSION >= 3004 |
9af5ce0c | 1224 | gcc_assert (sizeof (long) == sizeof (word)); |
7bf60644 | 1225 | bit_no += BITMAP_WORD_BITS - __builtin_clzl (word) - 1; |
ffa800d1 | 1226 | #else |
7bf60644 | 1227 | /* Hopefully this is a twos-complement host... */ |
1228 | BITMAP_WORD x = word; | |
1229 | x |= (x >> 1); | |
1230 | x |= (x >> 2); | |
1231 | x |= (x >> 4); | |
1232 | x |= (x >> 8); | |
1233 | x |= (x >> 16); | |
ffa800d1 | 1234 | #if BITMAP_WORD_BITS > 32 |
7bf60644 | 1235 | x |= (x >> 32); |
ffa800d1 | 1236 | #endif |
7bf60644 | 1237 | bit_no += bitmap_popcount (x) - 1; |
ffa800d1 | 1238 | #endif |
1239 | ||
7bf60644 | 1240 | return bit_no; |
ffa800d1 | 1241 | } |
114c7df6 | 1242 | \f |
2f925a60 | 1243 | |
621a25ae | 1244 | /* DST = A & B. */ |
b6e72c17 | 1245 | |
1246 | void | |
056755a1 | 1247 | bitmap_and (bitmap dst, const_bitmap a, const_bitmap b) |
2f925a60 | 1248 | { |
b6e72c17 | 1249 | bitmap_element *dst_elt = dst->first; |
056755a1 | 1250 | const bitmap_element *a_elt = a->first; |
1251 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 1252 | bitmap_element *dst_prev = NULL; |
66b5ac3c | 1253 | |
e35f850e | 1254 | gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form); |
07913396 | 1255 | gcc_assert (dst != a && dst != b); |
1256 | ||
1257 | if (a == b) | |
1258 | { | |
1259 | bitmap_copy (dst, a); | |
1260 | return; | |
1261 | } | |
1262 | ||
b6e72c17 | 1263 | while (a_elt && b_elt) |
1264 | { | |
1265 | if (a_elt->indx < b_elt->indx) | |
1266 | a_elt = a_elt->next; | |
1267 | else if (b_elt->indx < a_elt->indx) | |
1268 | b_elt = b_elt->next; | |
1269 | else | |
1270 | { | |
1271 | /* Matching elts, generate A & B. */ | |
1272 | unsigned ix; | |
1273 | BITMAP_WORD ior = 0; | |
1274 | ||
1275 | if (!dst_elt) | |
e35f850e | 1276 | dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
1277 | a_elt->indx); | |
a0c938f0 | 1278 | else |
5669bd62 | 1279 | dst_elt->indx = a_elt->indx; |
4399d500 | 1280 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 1281 | { |
1282 | BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; | |
2f925a60 | 1283 | |
b6e72c17 | 1284 | dst_elt->bits[ix] = r; |
1285 | ior |= r; | |
1286 | } | |
1287 | if (ior) | |
1288 | { | |
1289 | dst_prev = dst_elt; | |
1290 | dst_elt = dst_elt->next; | |
1291 | } | |
1292 | a_elt = a_elt->next; | |
1293 | b_elt = b_elt->next; | |
1294 | } | |
1295 | } | |
c926c35f | 1296 | /* Ensure that dst->current is valid. */ |
1297 | dst->current = dst->first; | |
b6e72c17 | 1298 | bitmap_elt_clear_from (dst, dst_elt); |
0ea2d350 | 1299 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 1300 | if (dst->current) |
1301 | dst->indx = dst->current->indx; | |
1302 | } | |
1303 | ||
ea9538fb | 1304 | /* A &= B. Return true if A changed. */ |
b6e72c17 | 1305 | |
ea9538fb | 1306 | bool |
056755a1 | 1307 | bitmap_and_into (bitmap a, const_bitmap b) |
b6e72c17 | 1308 | { |
1309 | bitmap_element *a_elt = a->first; | |
056755a1 | 1310 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 1311 | bitmap_element *next; |
ea9538fb | 1312 | bool changed = false; |
2f925a60 | 1313 | |
e35f850e | 1314 | gcc_checking_assert (!a->tree_form && !b->tree_form); |
1315 | ||
a0c938f0 | 1316 | if (a == b) |
ea9538fb | 1317 | return false; |
07913396 | 1318 | |
b6e72c17 | 1319 | while (a_elt && b_elt) |
2f925a60 | 1320 | { |
b6e72c17 | 1321 | if (a_elt->indx < b_elt->indx) |
1322 | { | |
1323 | next = a_elt->next; | |
e35f850e | 1324 | bitmap_list_unlink_element (a, a_elt); |
b6e72c17 | 1325 | a_elt = next; |
ea9538fb | 1326 | changed = true; |
b6e72c17 | 1327 | } |
1328 | else if (b_elt->indx < a_elt->indx) | |
1329 | b_elt = b_elt->next; | |
1330 | else | |
2f925a60 | 1331 | { |
b6e72c17 | 1332 | /* Matching elts, generate A &= B. */ |
1333 | unsigned ix; | |
1334 | BITMAP_WORD ior = 0; | |
1335 | ||
4399d500 | 1336 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 1337 | { |
1338 | BITMAP_WORD r = a_elt->bits[ix] & b_elt->bits[ix]; | |
ea9538fb | 1339 | if (a_elt->bits[ix] != r) |
1340 | changed = true; | |
b6e72c17 | 1341 | a_elt->bits[ix] = r; |
1342 | ior |= r; | |
1343 | } | |
1344 | next = a_elt->next; | |
1345 | if (!ior) | |
e35f850e | 1346 | bitmap_list_unlink_element (a, a_elt); |
b6e72c17 | 1347 | a_elt = next; |
1348 | b_elt = b_elt->next; | |
2f925a60 | 1349 | } |
b6e72c17 | 1350 | } |
ea9538fb | 1351 | |
1352 | if (a_elt) | |
1353 | { | |
1354 | changed = true; | |
1355 | bitmap_elt_clear_from (a, a_elt); | |
1356 | } | |
1357 | ||
0ea2d350 | 1358 | gcc_checking_assert (!a->current == !a->first |
1359 | && (!a->current || a->indx == a->current->indx)); | |
ea9538fb | 1360 | |
1361 | return changed; | |
b6e72c17 | 1362 | } |
1363 | ||
3072d30e | 1364 | |
1365 | /* Insert an element equal to SRC_ELT after DST_PREV, overwriting DST_ELT | |
1366 | if non-NULL. CHANGED is true if the destination bitmap had already been | |
1367 | changed; the new value of CHANGED is returned. */ | |
1368 | ||
1369 | static inline bool | |
1370 | bitmap_elt_copy (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, | |
056755a1 | 1371 | const bitmap_element *src_elt, bool changed) |
3072d30e | 1372 | { |
1373 | if (!changed && dst_elt && dst_elt->indx == src_elt->indx) | |
1374 | { | |
1375 | unsigned ix; | |
1376 | ||
4399d500 | 1377 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1378 | if (src_elt->bits[ix] != dst_elt->bits[ix]) |
1379 | { | |
1380 | dst_elt->bits[ix] = src_elt->bits[ix]; | |
1381 | changed = true; | |
1382 | } | |
1383 | } | |
1384 | else | |
1385 | { | |
1386 | changed = true; | |
1387 | if (!dst_elt) | |
e35f850e | 1388 | dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
1389 | src_elt->indx); | |
3072d30e | 1390 | else |
1391 | dst_elt->indx = src_elt->indx; | |
1392 | memcpy (dst_elt->bits, src_elt->bits, sizeof (dst_elt->bits)); | |
1393 | } | |
1394 | return changed; | |
1395 | } | |
1396 | ||
1397 | ||
1398 | ||
b6e72c17 | 1399 | /* DST = A & ~B */ |
1400 | ||
3072d30e | 1401 | bool |
056755a1 | 1402 | bitmap_and_compl (bitmap dst, const_bitmap a, const_bitmap b) |
b6e72c17 | 1403 | { |
1404 | bitmap_element *dst_elt = dst->first; | |
056755a1 | 1405 | const bitmap_element *a_elt = a->first; |
1406 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 1407 | bitmap_element *dst_prev = NULL; |
3072d30e | 1408 | bitmap_element **dst_prev_pnext = &dst->first; |
1409 | bool changed = false; | |
b6e72c17 | 1410 | |
e35f850e | 1411 | gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form); |
07913396 | 1412 | gcc_assert (dst != a && dst != b); |
a0c938f0 | 1413 | |
07913396 | 1414 | if (a == b) |
1415 | { | |
3072d30e | 1416 | changed = !bitmap_empty_p (dst); |
07913396 | 1417 | bitmap_clear (dst); |
3072d30e | 1418 | return changed; |
07913396 | 1419 | } |
1420 | ||
b6e72c17 | 1421 | while (a_elt) |
1422 | { | |
3072d30e | 1423 | while (b_elt && b_elt->indx < a_elt->indx) |
1424 | b_elt = b_elt->next; | |
1425 | ||
1426 | if (!b_elt || b_elt->indx > a_elt->indx) | |
2f925a60 | 1427 | { |
3072d30e | 1428 | changed = bitmap_elt_copy (dst, dst_elt, dst_prev, a_elt, changed); |
1429 | dst_prev = *dst_prev_pnext; | |
1430 | dst_prev_pnext = &dst_prev->next; | |
1431 | dst_elt = *dst_prev_pnext; | |
b6e72c17 | 1432 | a_elt = a_elt->next; |
2f925a60 | 1433 | } |
3072d30e | 1434 | |
2f925a60 | 1435 | else |
1436 | { | |
b6e72c17 | 1437 | /* Matching elts, generate A & ~B. */ |
1438 | unsigned ix; | |
1439 | BITMAP_WORD ior = 0; | |
1440 | ||
3072d30e | 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 | ||
1447 | if (dst_elt->bits[ix] != r) | |
1448 | { | |
1449 | changed = true; | |
1450 | dst_elt->bits[ix] = r; | |
1451 | } | |
1452 | ior |= r; | |
1453 | } | |
1454 | } | |
a0c938f0 | 1455 | else |
b6e72c17 | 1456 | { |
3072d30e | 1457 | bool new_element; |
1458 | if (!dst_elt || dst_elt->indx > a_elt->indx) | |
1459 | { | |
e35f850e | 1460 | dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
1461 | a_elt->indx); | |
3072d30e | 1462 | new_element = true; |
1463 | } | |
1464 | else | |
1465 | { | |
1466 | dst_elt->indx = a_elt->indx; | |
1467 | new_element = false; | |
1468 | } | |
b6e72c17 | 1469 | |
4399d500 | 1470 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1471 | { |
1472 | BITMAP_WORD r = a_elt->bits[ix] & ~b_elt->bits[ix]; | |
1473 | ||
1474 | dst_elt->bits[ix] = r; | |
1475 | ior |= r; | |
1476 | } | |
1477 | ||
1478 | if (ior) | |
1479 | changed = true; | |
1480 | else | |
1481 | { | |
1482 | changed |= !new_element; | |
e35f850e | 1483 | bitmap_list_unlink_element (dst, dst_elt); |
3072d30e | 1484 | dst_elt = *dst_prev_pnext; |
1485 | } | |
b6e72c17 | 1486 | } |
3072d30e | 1487 | |
b6e72c17 | 1488 | if (ior) |
1489 | { | |
3072d30e | 1490 | dst_prev = *dst_prev_pnext; |
1491 | dst_prev_pnext = &dst_prev->next; | |
1492 | dst_elt = *dst_prev_pnext; | |
b6e72c17 | 1493 | } |
1494 | a_elt = a_elt->next; | |
1495 | b_elt = b_elt->next; | |
2f925a60 | 1496 | } |
b6e72c17 | 1497 | } |
3072d30e | 1498 | |
c926c35f | 1499 | /* Ensure that dst->current is valid. */ |
1500 | dst->current = dst->first; | |
3072d30e | 1501 | |
1502 | if (dst_elt) | |
1503 | { | |
1504 | changed = true; | |
1505 | bitmap_elt_clear_from (dst, dst_elt); | |
1506 | } | |
0ea2d350 | 1507 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 1508 | if (dst->current) |
1509 | dst->indx = dst->current->indx; | |
3072d30e | 1510 | |
1511 | return changed; | |
b6e72c17 | 1512 | } |
1513 | ||
0db4e233 | 1514 | /* A &= ~B. Returns true if A changes */ |
2f925a60 | 1515 | |
0db4e233 | 1516 | bool |
056755a1 | 1517 | bitmap_and_compl_into (bitmap a, const_bitmap b) |
b6e72c17 | 1518 | { |
1519 | bitmap_element *a_elt = a->first; | |
056755a1 | 1520 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 1521 | bitmap_element *next; |
0db4e233 | 1522 | BITMAP_WORD changed = 0; |
b6e72c17 | 1523 | |
e35f850e | 1524 | gcc_checking_assert (!a->tree_form && !b->tree_form); |
1525 | ||
07913396 | 1526 | if (a == b) |
1527 | { | |
1528 | if (bitmap_empty_p (a)) | |
1529 | return false; | |
1530 | else | |
1531 | { | |
1532 | bitmap_clear (a); | |
1533 | return true; | |
1534 | } | |
1535 | } | |
1536 | ||
b6e72c17 | 1537 | while (a_elt && b_elt) |
1538 | { | |
1539 | if (a_elt->indx < b_elt->indx) | |
1540 | a_elt = a_elt->next; | |
1541 | else if (b_elt->indx < a_elt->indx) | |
1542 | b_elt = b_elt->next; | |
1543 | else | |
66b5ac3c | 1544 | { |
b6e72c17 | 1545 | /* Matching elts, generate A &= ~B. */ |
1546 | unsigned ix; | |
1547 | BITMAP_WORD ior = 0; | |
1548 | ||
4399d500 | 1549 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 1550 | { |
0db4e233 | 1551 | BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; |
1552 | BITMAP_WORD r = a_elt->bits[ix] ^ cleared; | |
b6e72c17 | 1553 | |
1554 | a_elt->bits[ix] = r; | |
0db4e233 | 1555 | changed |= cleared; |
b6e72c17 | 1556 | ior |= r; |
1557 | } | |
1558 | next = a_elt->next; | |
1559 | if (!ior) | |
e35f850e | 1560 | bitmap_list_unlink_element (a, a_elt); |
b6e72c17 | 1561 | a_elt = next; |
1562 | b_elt = b_elt->next; | |
66b5ac3c | 1563 | } |
b6e72c17 | 1564 | } |
0ea2d350 | 1565 | gcc_checking_assert (!a->current == !a->first |
1566 | && (!a->current || a->indx == a->current->indx)); | |
0db4e233 | 1567 | return changed != 0; |
b6e72c17 | 1568 | } |
1569 | ||
3072d30e | 1570 | /* Set COUNT bits from START in HEAD. */ |
1571 | void | |
1572 | bitmap_set_range (bitmap head, unsigned int start, unsigned int count) | |
1573 | { | |
1574 | unsigned int first_index, end_bit_plus1, last_index; | |
1575 | bitmap_element *elt, *elt_prev; | |
1576 | unsigned int i; | |
1577 | ||
e35f850e | 1578 | gcc_checking_assert (!head->tree_form); |
1579 | ||
3072d30e | 1580 | if (!count) |
1581 | return; | |
1582 | ||
837d3ea8 | 1583 | if (count == 1) |
1584 | { | |
1585 | bitmap_set_bit (head, start); | |
1586 | return; | |
1587 | } | |
1588 | ||
3072d30e | 1589 | first_index = start / BITMAP_ELEMENT_ALL_BITS; |
1590 | end_bit_plus1 = start + count; | |
1591 | last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | |
e35f850e | 1592 | elt = bitmap_list_find_element (head, first_index); |
3072d30e | 1593 | |
e35f850e | 1594 | /* If bitmap_list_find_element returns zero, the current is the closest block |
3072d30e | 1595 | to the result. Otherwise, just use bitmap_element_allocate to |
1596 | ensure ELT is set; in the loop below, ELT == NULL means "insert | |
1597 | at the end of the bitmap". */ | |
1598 | if (!elt) | |
1599 | { | |
1600 | elt = bitmap_element_allocate (head); | |
1601 | elt->indx = first_index; | |
e35f850e | 1602 | bitmap_list_link_element (head, elt); |
3072d30e | 1603 | } |
1604 | ||
d16af188 | 1605 | gcc_checking_assert (elt->indx == first_index); |
3072d30e | 1606 | elt_prev = elt->prev; |
1607 | for (i = first_index; i <= last_index; i++) | |
1608 | { | |
1609 | unsigned elt_start_bit = i * BITMAP_ELEMENT_ALL_BITS; | |
1610 | unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; | |
1611 | ||
1612 | unsigned int first_word_to_mod; | |
1613 | BITMAP_WORD first_mask; | |
1614 | unsigned int last_word_to_mod; | |
1615 | BITMAP_WORD last_mask; | |
1616 | unsigned int ix; | |
1617 | ||
1618 | if (!elt || elt->indx != i) | |
e35f850e | 1619 | elt = bitmap_list_insert_element_after (head, elt_prev, i); |
3072d30e | 1620 | |
1621 | if (elt_start_bit <= start) | |
1622 | { | |
1623 | /* The first bit to turn on is somewhere inside this | |
1624 | elt. */ | |
1625 | first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; | |
1626 | ||
1627 | /* This mask should have 1s in all bits >= start position. */ | |
1628 | first_mask = | |
1629 | (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; | |
1630 | first_mask = ~first_mask; | |
1631 | } | |
1632 | else | |
1633 | { | |
1634 | /* The first bit to turn on is below this start of this elt. */ | |
1635 | first_word_to_mod = 0; | |
1636 | first_mask = ~(BITMAP_WORD) 0; | |
1637 | } | |
1638 | ||
1639 | if (elt_end_bit_plus1 <= end_bit_plus1) | |
1640 | { | |
1641 | /* The last bit to turn on is beyond this elt. */ | |
1642 | last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; | |
1643 | last_mask = ~(BITMAP_WORD) 0; | |
1644 | } | |
1645 | else | |
1646 | { | |
1647 | /* The last bit to turn on is inside to this elt. */ | |
1648 | last_word_to_mod = | |
1649 | (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; | |
1650 | ||
1651 | /* The last mask should have 1s below the end bit. */ | |
1652 | last_mask = | |
1653 | (((BITMAP_WORD) 1) << ((end_bit_plus1 % BITMAP_WORD_BITS))) - 1; | |
1654 | } | |
1655 | ||
1656 | if (first_word_to_mod == last_word_to_mod) | |
1657 | { | |
1658 | BITMAP_WORD mask = first_mask & last_mask; | |
1659 | elt->bits[first_word_to_mod] |= mask; | |
1660 | } | |
1661 | else | |
1662 | { | |
1663 | elt->bits[first_word_to_mod] |= first_mask; | |
1664 | if (BITMAP_ELEMENT_WORDS > 2) | |
1665 | for (ix = first_word_to_mod + 1; ix < last_word_to_mod; ix++) | |
1666 | elt->bits[ix] = ~(BITMAP_WORD) 0; | |
1667 | elt->bits[last_word_to_mod] |= last_mask; | |
1668 | } | |
1669 | ||
1670 | elt_prev = elt; | |
1671 | elt = elt->next; | |
1672 | } | |
1673 | ||
1674 | head->current = elt ? elt : elt_prev; | |
1675 | head->indx = head->current->indx; | |
1676 | } | |
1677 | ||
5669bd62 | 1678 | /* Clear COUNT bits from START in HEAD. */ |
1679 | void | |
1680 | bitmap_clear_range (bitmap head, unsigned int start, unsigned int count) | |
1681 | { | |
3072d30e | 1682 | unsigned int first_index, end_bit_plus1, last_index; |
1683 | bitmap_element *elt; | |
1684 | ||
e35f850e | 1685 | gcc_checking_assert (!head->tree_form); |
1686 | ||
3072d30e | 1687 | if (!count) |
1688 | return; | |
1689 | ||
837d3ea8 | 1690 | if (count == 1) |
1691 | { | |
1692 | bitmap_clear_bit (head, start); | |
1693 | return; | |
1694 | } | |
1695 | ||
3072d30e | 1696 | first_index = start / BITMAP_ELEMENT_ALL_BITS; |
1697 | end_bit_plus1 = start + count; | |
1698 | last_index = (end_bit_plus1 - 1) / BITMAP_ELEMENT_ALL_BITS; | |
e35f850e | 1699 | elt = bitmap_list_find_element (head, first_index); |
5669bd62 | 1700 | |
e35f850e | 1701 | /* If bitmap_list_find_element returns zero, the current is the closest block |
5669bd62 | 1702 | to the result. If the current is less than first index, find the |
1703 | next one. Otherwise, just set elt to be current. */ | |
1704 | if (!elt) | |
a0c938f0 | 1705 | { |
5669bd62 | 1706 | if (head->current) |
1707 | { | |
1708 | if (head->indx < first_index) | |
1709 | { | |
1710 | elt = head->current->next; | |
1711 | if (!elt) | |
1712 | return; | |
1713 | } | |
a0c938f0 | 1714 | else |
5669bd62 | 1715 | elt = head->current; |
1716 | } | |
1717 | else | |
1718 | return; | |
1719 | } | |
1720 | ||
1721 | while (elt && (elt->indx <= last_index)) | |
1722 | { | |
1723 | bitmap_element * next_elt = elt->next; | |
1724 | unsigned elt_start_bit = (elt->indx) * BITMAP_ELEMENT_ALL_BITS; | |
1725 | unsigned elt_end_bit_plus1 = elt_start_bit + BITMAP_ELEMENT_ALL_BITS; | |
1726 | ||
1727 | ||
1728 | if (elt_start_bit >= start && elt_end_bit_plus1 <= end_bit_plus1) | |
1729 | /* Get rid of the entire elt and go to the next one. */ | |
e35f850e | 1730 | bitmap_list_unlink_element (head, elt); |
a0c938f0 | 1731 | else |
5669bd62 | 1732 | { |
1733 | /* Going to have to knock out some bits in this elt. */ | |
a0c938f0 | 1734 | unsigned int first_word_to_mod; |
1735 | BITMAP_WORD first_mask; | |
5669bd62 | 1736 | unsigned int last_word_to_mod; |
1737 | BITMAP_WORD last_mask; | |
1738 | unsigned int i; | |
1739 | bool clear = true; | |
1740 | ||
1741 | if (elt_start_bit <= start) | |
1742 | { | |
1743 | /* The first bit to turn off is somewhere inside this | |
1744 | elt. */ | |
1745 | first_word_to_mod = (start - elt_start_bit) / BITMAP_WORD_BITS; | |
1746 | ||
1747 | /* This mask should have 1s in all bits >= start position. */ | |
a0c938f0 | 1748 | first_mask = |
5669bd62 | 1749 | (((BITMAP_WORD) 1) << ((start % BITMAP_WORD_BITS))) - 1; |
1750 | first_mask = ~first_mask; | |
1751 | } | |
1752 | else | |
1753 | { | |
1754 | /* The first bit to turn off is below this start of this elt. */ | |
1755 | first_word_to_mod = 0; | |
1756 | first_mask = 0; | |
1757 | first_mask = ~first_mask; | |
a0c938f0 | 1758 | } |
1759 | ||
5669bd62 | 1760 | if (elt_end_bit_plus1 <= end_bit_plus1) |
1761 | { | |
1762 | /* The last bit to turn off is beyond this elt. */ | |
1763 | last_word_to_mod = BITMAP_ELEMENT_WORDS - 1; | |
1764 | last_mask = 0; | |
1765 | last_mask = ~last_mask; | |
1766 | } | |
1767 | else | |
1768 | { | |
1769 | /* The last bit to turn off is inside to this elt. */ | |
a0c938f0 | 1770 | last_word_to_mod = |
5669bd62 | 1771 | (end_bit_plus1 - elt_start_bit) / BITMAP_WORD_BITS; |
1772 | ||
1773 | /* The last mask should have 1s below the end bit. */ | |
a0c938f0 | 1774 | last_mask = |
5669bd62 | 1775 | (((BITMAP_WORD) 1) << (((end_bit_plus1) % BITMAP_WORD_BITS))) - 1; |
1776 | } | |
1777 | ||
1778 | ||
1779 | if (first_word_to_mod == last_word_to_mod) | |
1780 | { | |
1781 | BITMAP_WORD mask = first_mask & last_mask; | |
1782 | elt->bits[first_word_to_mod] &= ~mask; | |
1783 | } | |
1784 | else | |
1785 | { | |
1786 | elt->bits[first_word_to_mod] &= ~first_mask; | |
3072d30e | 1787 | if (BITMAP_ELEMENT_WORDS > 2) |
1788 | for (i = first_word_to_mod + 1; i < last_word_to_mod; i++) | |
1789 | elt->bits[i] = 0; | |
5669bd62 | 1790 | elt->bits[last_word_to_mod] &= ~last_mask; |
1791 | } | |
1792 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
1793 | if (elt->bits[i]) | |
1794 | { | |
1795 | clear = false; | |
1796 | break; | |
1797 | } | |
1798 | /* Check to see if there are any bits left. */ | |
1799 | if (clear) | |
e35f850e | 1800 | bitmap_list_unlink_element (head, elt); |
5669bd62 | 1801 | } |
1802 | elt = next_elt; | |
1803 | } | |
a0c938f0 | 1804 | |
5669bd62 | 1805 | if (elt) |
1806 | { | |
1807 | head->current = elt; | |
1808 | head->indx = head->current->indx; | |
1809 | } | |
1810 | } | |
1811 | ||
1812 | /* A = ~A & B. */ | |
1813 | ||
1814 | void | |
056755a1 | 1815 | bitmap_compl_and_into (bitmap a, const_bitmap b) |
5669bd62 | 1816 | { |
1817 | bitmap_element *a_elt = a->first; | |
056755a1 | 1818 | const bitmap_element *b_elt = b->first; |
5669bd62 | 1819 | bitmap_element *a_prev = NULL; |
1820 | bitmap_element *next; | |
1821 | ||
e35f850e | 1822 | gcc_checking_assert (!a->tree_form && !b->tree_form); |
5669bd62 | 1823 | gcc_assert (a != b); |
1824 | ||
1825 | if (bitmap_empty_p (a)) | |
1826 | { | |
1827 | bitmap_copy (a, b); | |
1828 | return; | |
1829 | } | |
1830 | if (bitmap_empty_p (b)) | |
1831 | { | |
1832 | bitmap_clear (a); | |
1833 | return; | |
1834 | } | |
1835 | ||
1836 | while (a_elt || b_elt) | |
1837 | { | |
1838 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
1839 | { | |
1840 | /* A is before B. Remove A */ | |
1841 | next = a_elt->next; | |
1842 | a_prev = a_elt->prev; | |
e35f850e | 1843 | bitmap_list_unlink_element (a, a_elt); |
5669bd62 | 1844 | a_elt = next; |
1845 | } | |
1846 | else if (!a_elt || b_elt->indx < a_elt->indx) | |
1847 | { | |
1848 | /* B is before A. Copy B. */ | |
e35f850e | 1849 | next = bitmap_list_insert_element_after (a, a_prev, b_elt->indx); |
5669bd62 | 1850 | memcpy (next->bits, b_elt->bits, sizeof (next->bits)); |
1851 | a_prev = next; | |
1852 | b_elt = b_elt->next; | |
1853 | } | |
1854 | else | |
1855 | { | |
1856 | /* Matching elts, generate A = ~A & B. */ | |
1857 | unsigned ix; | |
1858 | BITMAP_WORD ior = 0; | |
1859 | ||
4399d500 | 1860 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
5669bd62 | 1861 | { |
1862 | BITMAP_WORD cleared = a_elt->bits[ix] & b_elt->bits[ix]; | |
1863 | BITMAP_WORD r = b_elt->bits[ix] ^ cleared; | |
1864 | ||
1865 | a_elt->bits[ix] = r; | |
1866 | ior |= r; | |
1867 | } | |
1868 | next = a_elt->next; | |
1869 | if (!ior) | |
e35f850e | 1870 | bitmap_list_unlink_element (a, a_elt); |
5669bd62 | 1871 | else |
1872 | a_prev = a_elt; | |
1873 | a_elt = next; | |
1874 | b_elt = b_elt->next; | |
1875 | } | |
1876 | } | |
0ea2d350 | 1877 | gcc_checking_assert (!a->current == !a->first |
1878 | && (!a->current || a->indx == a->current->indx)); | |
5669bd62 | 1879 | return; |
1880 | } | |
1881 | ||
3072d30e | 1882 | |
1883 | /* Insert an element corresponding to A_ELT | B_ELT after DST_PREV, | |
1884 | overwriting DST_ELT if non-NULL. CHANGED is true if the destination bitmap | |
1885 | had already been changed; the new value of CHANGED is returned. */ | |
1886 | ||
1887 | static inline bool | |
1888 | bitmap_elt_ior (bitmap dst, bitmap_element *dst_elt, bitmap_element *dst_prev, | |
056755a1 | 1889 | const bitmap_element *a_elt, const bitmap_element *b_elt, |
3072d30e | 1890 | bool changed) |
1891 | { | |
1892 | gcc_assert (a_elt || b_elt); | |
1893 | ||
1894 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
1895 | { | |
1896 | /* Matching elts, generate A | B. */ | |
1897 | unsigned ix; | |
1898 | ||
1899 | if (!changed && dst_elt && dst_elt->indx == a_elt->indx) | |
1900 | { | |
4399d500 | 1901 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1902 | { |
1903 | BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; | |
1904 | if (r != dst_elt->bits[ix]) | |
1905 | { | |
1906 | dst_elt->bits[ix] = r; | |
1907 | changed = true; | |
1908 | } | |
1909 | } | |
1910 | } | |
1911 | else | |
1912 | { | |
1913 | changed = true; | |
1914 | if (!dst_elt) | |
e35f850e | 1915 | dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
1916 | a_elt->indx); | |
3072d30e | 1917 | else |
1918 | dst_elt->indx = a_elt->indx; | |
4399d500 | 1919 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 1920 | { |
1921 | BITMAP_WORD r = a_elt->bits[ix] | b_elt->bits[ix]; | |
1922 | dst_elt->bits[ix] = r; | |
1923 | } | |
1924 | } | |
1925 | } | |
1926 | else | |
1927 | { | |
1928 | /* Copy a single element. */ | |
056755a1 | 1929 | const bitmap_element *src; |
3072d30e | 1930 | |
1931 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
1932 | src = a_elt; | |
1933 | else | |
1934 | src = b_elt; | |
1935 | ||
d16af188 | 1936 | gcc_checking_assert (src); |
3072d30e | 1937 | changed = bitmap_elt_copy (dst, dst_elt, dst_prev, src, changed); |
1938 | } | |
1939 | return changed; | |
1940 | } | |
1941 | ||
1942 | ||
b6e72c17 | 1943 | /* DST = A | B. Return true if DST changes. */ |
1944 | ||
1945 | bool | |
056755a1 | 1946 | bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b) |
b6e72c17 | 1947 | { |
1948 | bitmap_element *dst_elt = dst->first; | |
056755a1 | 1949 | const bitmap_element *a_elt = a->first; |
1950 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 1951 | bitmap_element *dst_prev = NULL; |
3072d30e | 1952 | bitmap_element **dst_prev_pnext = &dst->first; |
a0c938f0 | 1953 | bool changed = false; |
b6e72c17 | 1954 | |
e35f850e | 1955 | gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form); |
07913396 | 1956 | gcc_assert (dst != a && dst != b); |
1957 | ||
b6e72c17 | 1958 | while (a_elt || b_elt) |
1959 | { | |
3072d30e | 1960 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, a_elt, b_elt, changed); |
1961 | ||
b6e72c17 | 1962 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) |
66b5ac3c | 1963 | { |
b6e72c17 | 1964 | a_elt = a_elt->next; |
1965 | b_elt = b_elt->next; | |
66b5ac3c | 1966 | } |
1967 | else | |
2f925a60 | 1968 | { |
3072d30e | 1969 | if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) |
1970 | a_elt = a_elt->next; | |
1971 | else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) | |
1972 | b_elt = b_elt->next; | |
2f925a60 | 1973 | } |
3072d30e | 1974 | |
1975 | dst_prev = *dst_prev_pnext; | |
1976 | dst_prev_pnext = &dst_prev->next; | |
1977 | dst_elt = *dst_prev_pnext; | |
b6e72c17 | 1978 | } |
1979 | ||
1980 | if (dst_elt) | |
1981 | { | |
1982 | changed = true; | |
85ac1c40 | 1983 | /* Ensure that dst->current is valid. */ |
1984 | dst->current = dst->first; | |
b6e72c17 | 1985 | bitmap_elt_clear_from (dst, dst_elt); |
1986 | } | |
0ea2d350 | 1987 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 1988 | if (dst->current) |
1989 | dst->indx = dst->current->indx; | |
1990 | return changed; | |
1991 | } | |
2f925a60 | 1992 | |
b6e72c17 | 1993 | /* A |= B. Return true if A changes. */ |
1994 | ||
1995 | bool | |
056755a1 | 1996 | bitmap_ior_into (bitmap a, const_bitmap b) |
b6e72c17 | 1997 | { |
1998 | bitmap_element *a_elt = a->first; | |
056755a1 | 1999 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 2000 | bitmap_element *a_prev = NULL; |
3072d30e | 2001 | bitmap_element **a_prev_pnext = &a->first; |
b6e72c17 | 2002 | bool changed = false; |
2003 | ||
e35f850e | 2004 | gcc_checking_assert (!a->tree_form && !b->tree_form); |
07913396 | 2005 | if (a == b) |
2006 | return false; | |
2007 | ||
b6e72c17 | 2008 | while (b_elt) |
2009 | { | |
3072d30e | 2010 | /* If A lags behind B, just advance it. */ |
2011 | if (!a_elt || a_elt->indx == b_elt->indx) | |
b6e72c17 | 2012 | { |
3072d30e | 2013 | changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed); |
b6e72c17 | 2014 | b_elt = b_elt->next; |
d587687f | 2015 | } |
3072d30e | 2016 | else if (a_elt->indx > b_elt->indx) |
d587687f | 2017 | { |
3072d30e | 2018 | changed = bitmap_elt_copy (a, NULL, a_prev, b_elt, changed); |
b6e72c17 | 2019 | b_elt = b_elt->next; |
2f925a60 | 2020 | } |
3072d30e | 2021 | |
2022 | a_prev = *a_prev_pnext; | |
2023 | a_prev_pnext = &a_prev->next; | |
2024 | a_elt = *a_prev_pnext; | |
2f925a60 | 2025 | } |
3072d30e | 2026 | |
0ea2d350 | 2027 | gcc_checking_assert (!a->current == !a->first); |
b6e72c17 | 2028 | if (a->current) |
2029 | a->indx = a->current->indx; | |
2030 | return changed; | |
2031 | } | |
2032 | ||
80c7cb9d | 2033 | /* A |= B. Return true if A changes. Free B (re-using its storage |
2034 | for the result). */ | |
2035 | ||
2036 | bool | |
2037 | bitmap_ior_into_and_free (bitmap a, bitmap *b_) | |
2038 | { | |
2039 | bitmap b = *b_; | |
2040 | bitmap_element *a_elt = a->first; | |
2041 | bitmap_element *b_elt = b->first; | |
2042 | bitmap_element *a_prev = NULL; | |
2043 | bitmap_element **a_prev_pnext = &a->first; | |
2044 | bool changed = false; | |
2045 | ||
2046 | gcc_checking_assert (!a->tree_form && !b->tree_form); | |
2047 | gcc_assert (a->obstack == b->obstack); | |
2048 | if (a == b) | |
2049 | return false; | |
2050 | ||
2051 | while (b_elt) | |
2052 | { | |
2053 | /* If A lags behind B, just advance it. */ | |
2054 | if (!a_elt || a_elt->indx == b_elt->indx) | |
2055 | { | |
2056 | changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed); | |
2057 | b_elt = b_elt->next; | |
2058 | } | |
2059 | else if (a_elt->indx > b_elt->indx) | |
2060 | { | |
2061 | bitmap_element *b_elt_next = b_elt->next; | |
2062 | bitmap_list_unlink_element (b, b_elt, false); | |
2063 | bitmap_list_insert_element_after (a, a_prev, b_elt->indx, b_elt); | |
2064 | b_elt = b_elt_next; | |
2065 | } | |
2066 | ||
2067 | a_prev = *a_prev_pnext; | |
2068 | a_prev_pnext = &a_prev->next; | |
2069 | a_elt = *a_prev_pnext; | |
2070 | } | |
2071 | ||
2072 | gcc_checking_assert (!a->current == !a->first); | |
2073 | if (a->current) | |
2074 | a->indx = a->current->indx; | |
2075 | ||
2076 | if (b->obstack) | |
2077 | BITMAP_FREE (*b_); | |
2078 | else | |
2079 | bitmap_clear (b); | |
2080 | return changed; | |
2081 | } | |
2082 | ||
b6e72c17 | 2083 | /* DST = A ^ B */ |
2f925a60 | 2084 | |
b6e72c17 | 2085 | void |
056755a1 | 2086 | bitmap_xor (bitmap dst, const_bitmap a, const_bitmap b) |
b6e72c17 | 2087 | { |
2088 | bitmap_element *dst_elt = dst->first; | |
056755a1 | 2089 | const bitmap_element *a_elt = a->first; |
2090 | const bitmap_element *b_elt = b->first; | |
b6e72c17 | 2091 | bitmap_element *dst_prev = NULL; |
2092 | ||
e35f850e | 2093 | gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form); |
07913396 | 2094 | gcc_assert (dst != a && dst != b); |
e35f850e | 2095 | |
07913396 | 2096 | if (a == b) |
2097 | { | |
2098 | bitmap_clear (dst); | |
2099 | return; | |
2100 | } | |
2101 | ||
b6e72c17 | 2102 | while (a_elt || b_elt) |
2f925a60 | 2103 | { |
b6e72c17 | 2104 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) |
1f3233d1 | 2105 | { |
b6e72c17 | 2106 | /* Matching elts, generate A ^ B. */ |
2107 | unsigned ix; | |
2108 | BITMAP_WORD ior = 0; | |
2109 | ||
2110 | if (!dst_elt) | |
e35f850e | 2111 | dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
2112 | a_elt->indx); | |
5669bd62 | 2113 | else |
2114 | dst_elt->indx = a_elt->indx; | |
4399d500 | 2115 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 2116 | { |
2117 | BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; | |
2118 | ||
2119 | ior |= r; | |
2120 | dst_elt->bits[ix] = r; | |
2121 | } | |
2122 | a_elt = a_elt->next; | |
2123 | b_elt = b_elt->next; | |
2124 | if (ior) | |
2125 | { | |
2126 | dst_prev = dst_elt; | |
2127 | dst_elt = dst_elt->next; | |
2128 | } | |
1f3233d1 | 2129 | } |
2130 | else | |
2131 | { | |
b6e72c17 | 2132 | /* Copy a single element. */ |
056755a1 | 2133 | const bitmap_element *src; |
b6e72c17 | 2134 | |
2135 | if (!b_elt || (a_elt && a_elt->indx < b_elt->indx)) | |
2136 | { | |
2137 | src = a_elt; | |
2138 | a_elt = a_elt->next; | |
2139 | } | |
2140 | else | |
2141 | { | |
2142 | src = b_elt; | |
2143 | b_elt = b_elt->next; | |
2144 | } | |
2145 | ||
2146 | if (!dst_elt) | |
e35f850e | 2147 | dst_elt = bitmap_list_insert_element_after (dst, dst_prev, |
2148 | src->indx); | |
a0c938f0 | 2149 | else |
5669bd62 | 2150 | dst_elt->indx = src->indx; |
b6e72c17 | 2151 | memcpy (dst_elt->bits, src->bits, sizeof (dst_elt->bits)); |
2152 | dst_prev = dst_elt; | |
2153 | dst_elt = dst_elt->next; | |
1f3233d1 | 2154 | } |
2f925a60 | 2155 | } |
c926c35f | 2156 | /* Ensure that dst->current is valid. */ |
2157 | dst->current = dst->first; | |
b6e72c17 | 2158 | bitmap_elt_clear_from (dst, dst_elt); |
0ea2d350 | 2159 | gcc_checking_assert (!dst->current == !dst->first); |
b6e72c17 | 2160 | if (dst->current) |
2161 | dst->indx = dst->current->indx; | |
2162 | } | |
2f925a60 | 2163 | |
b6e72c17 | 2164 | /* A ^= B */ |
66b5ac3c | 2165 | |
b6e72c17 | 2166 | void |
056755a1 | 2167 | bitmap_xor_into (bitmap a, const_bitmap b) |
b6e72c17 | 2168 | { |
2169 | bitmap_element *a_elt = a->first; | |
056755a1 | 2170 | const bitmap_element *b_elt = b->first; |
b6e72c17 | 2171 | bitmap_element *a_prev = NULL; |
2172 | ||
e35f850e | 2173 | gcc_checking_assert (!a->tree_form && !b->tree_form); |
2174 | ||
07913396 | 2175 | if (a == b) |
2176 | { | |
2177 | bitmap_clear (a); | |
2178 | return; | |
2179 | } | |
2180 | ||
b6e72c17 | 2181 | while (b_elt) |
2182 | { | |
2183 | if (!a_elt || b_elt->indx < a_elt->indx) | |
2184 | { | |
2185 | /* Copy b_elt. */ | |
e35f850e | 2186 | bitmap_element *dst = bitmap_list_insert_element_after (a, a_prev, |
2187 | b_elt->indx); | |
b6e72c17 | 2188 | memcpy (dst->bits, b_elt->bits, sizeof (dst->bits)); |
2189 | a_prev = dst; | |
2190 | b_elt = b_elt->next; | |
2191 | } | |
2192 | else if (a_elt->indx < b_elt->indx) | |
2193 | { | |
2194 | a_prev = a_elt; | |
2195 | a_elt = a_elt->next; | |
2196 | } | |
2197 | else | |
2198 | { | |
2199 | /* Matching elts, generate A ^= B. */ | |
2200 | unsigned ix; | |
2201 | BITMAP_WORD ior = 0; | |
2202 | bitmap_element *next = a_elt->next; | |
2203 | ||
4399d500 | 2204 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
b6e72c17 | 2205 | { |
2206 | BITMAP_WORD r = a_elt->bits[ix] ^ b_elt->bits[ix]; | |
2207 | ||
2208 | ior |= r; | |
2209 | a_elt->bits[ix] = r; | |
2210 | } | |
2211 | b_elt = b_elt->next; | |
2212 | if (ior) | |
2213 | a_prev = a_elt; | |
2214 | else | |
e35f850e | 2215 | bitmap_list_unlink_element (a, a_elt); |
b6e72c17 | 2216 | a_elt = next; |
2217 | } | |
2218 | } | |
0ea2d350 | 2219 | gcc_checking_assert (!a->current == !a->first); |
b6e72c17 | 2220 | if (a->current) |
2221 | a->indx = a->current->indx; | |
66b5ac3c | 2222 | } |
2223 | ||
21576831 | 2224 | /* Return true if two bitmaps are identical. |
2225 | We do not bother with a check for pointer equality, as that never | |
2226 | occurs in practice. */ | |
66b5ac3c | 2227 | |
21576831 | 2228 | bool |
056755a1 | 2229 | bitmap_equal_p (const_bitmap a, const_bitmap b) |
66b5ac3c | 2230 | { |
056755a1 | 2231 | const bitmap_element *a_elt; |
2232 | const bitmap_element *b_elt; | |
21576831 | 2233 | unsigned ix; |
a0c938f0 | 2234 | |
e35f850e | 2235 | gcc_checking_assert (!a->tree_form && !b->tree_form); |
2236 | ||
21576831 | 2237 | for (a_elt = a->first, b_elt = b->first; |
2238 | a_elt && b_elt; | |
2239 | a_elt = a_elt->next, b_elt = b_elt->next) | |
2240 | { | |
2241 | if (a_elt->indx != b_elt->indx) | |
2242 | return false; | |
4399d500 | 2243 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
21576831 | 2244 | if (a_elt->bits[ix] != b_elt->bits[ix]) |
2245 | return false; | |
2246 | } | |
2247 | return !a_elt && !b_elt; | |
2248 | } | |
2249 | ||
2250 | /* Return true if A AND B is not empty. */ | |
2251 | ||
2252 | bool | |
056755a1 | 2253 | bitmap_intersect_p (const_bitmap a, const_bitmap b) |
21576831 | 2254 | { |
056755a1 | 2255 | const bitmap_element *a_elt; |
2256 | const bitmap_element *b_elt; | |
21576831 | 2257 | unsigned ix; |
a0c938f0 | 2258 | |
e35f850e | 2259 | gcc_checking_assert (!a->tree_form && !b->tree_form); |
2260 | ||
21576831 | 2261 | for (a_elt = a->first, b_elt = b->first; |
2262 | a_elt && b_elt;) | |
2263 | { | |
2264 | if (a_elt->indx < b_elt->indx) | |
2265 | a_elt = a_elt->next; | |
2266 | else if (b_elt->indx < a_elt->indx) | |
2267 | b_elt = b_elt->next; | |
2268 | else | |
2269 | { | |
4399d500 | 2270 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
21576831 | 2271 | if (a_elt->bits[ix] & b_elt->bits[ix]) |
2272 | return true; | |
2273 | a_elt = a_elt->next; | |
2274 | b_elt = b_elt->next; | |
2275 | } | |
2276 | } | |
2277 | return false; | |
2278 | } | |
66b5ac3c | 2279 | |
21576831 | 2280 | /* Return true if A AND NOT B is not empty. */ |
66b5ac3c | 2281 | |
21576831 | 2282 | bool |
056755a1 | 2283 | bitmap_intersect_compl_p (const_bitmap a, const_bitmap b) |
21576831 | 2284 | { |
056755a1 | 2285 | const bitmap_element *a_elt; |
2286 | const bitmap_element *b_elt; | |
21576831 | 2287 | unsigned ix; |
e35f850e | 2288 | |
2289 | gcc_checking_assert (!a->tree_form && !b->tree_form); | |
2290 | ||
21576831 | 2291 | for (a_elt = a->first, b_elt = b->first; |
2292 | a_elt && b_elt;) | |
2293 | { | |
2294 | if (a_elt->indx < b_elt->indx) | |
2295 | return true; | |
2296 | else if (b_elt->indx < a_elt->indx) | |
2297 | b_elt = b_elt->next; | |
2298 | else | |
2299 | { | |
4399d500 | 2300 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
21576831 | 2301 | if (a_elt->bits[ix] & ~b_elt->bits[ix]) |
2302 | return true; | |
2303 | a_elt = a_elt->next; | |
2304 | b_elt = b_elt->next; | |
2305 | } | |
2306 | } | |
2307 | return a_elt != NULL; | |
2f925a60 | 2308 | } |
21576831 | 2309 | |
2f925a60 | 2310 | \f |
b6e72c17 | 2311 | /* DST = A | (FROM1 & ~FROM2). Return true if DST changes. */ |
2f925a60 | 2312 | |
79d6d448 | 2313 | bool |
056755a1 | 2314 | bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap kill) |
2f925a60 | 2315 | { |
3072d30e | 2316 | bool changed = false; |
42fe97ed | 2317 | |
3072d30e | 2318 | bitmap_element *dst_elt = dst->first; |
056755a1 | 2319 | const bitmap_element *a_elt = a->first; |
2320 | const bitmap_element *b_elt = b->first; | |
2321 | const bitmap_element *kill_elt = kill->first; | |
3072d30e | 2322 | bitmap_element *dst_prev = NULL; |
2323 | bitmap_element **dst_prev_pnext = &dst->first; | |
2324 | ||
e35f850e | 2325 | gcc_checking_assert (!dst->tree_form && !a->tree_form && !b->tree_form |
2326 | && !kill->tree_form); | |
3072d30e | 2327 | gcc_assert (dst != a && dst != b && dst != kill); |
2328 | ||
2329 | /* Special cases. We don't bother checking for bitmap_equal_p (b, kill). */ | |
2330 | if (b == kill || bitmap_empty_p (b)) | |
2331 | { | |
2332 | changed = !bitmap_equal_p (dst, a); | |
2333 | if (changed) | |
2334 | bitmap_copy (dst, a); | |
2335 | return changed; | |
2336 | } | |
2337 | if (bitmap_empty_p (kill)) | |
2338 | return bitmap_ior (dst, a, b); | |
2339 | if (bitmap_empty_p (a)) | |
2340 | return bitmap_and_compl (dst, b, kill); | |
2341 | ||
2342 | while (a_elt || b_elt) | |
2343 | { | |
2344 | bool new_element = false; | |
2345 | ||
2346 | if (b_elt) | |
2347 | while (kill_elt && kill_elt->indx < b_elt->indx) | |
2348 | kill_elt = kill_elt->next; | |
2349 | ||
2350 | if (b_elt && kill_elt && kill_elt->indx == b_elt->indx | |
2351 | && (!a_elt || a_elt->indx >= b_elt->indx)) | |
2352 | { | |
2353 | bitmap_element tmp_elt; | |
2354 | unsigned ix; | |
2355 | ||
2356 | BITMAP_WORD ior = 0; | |
2357 | tmp_elt.indx = b_elt->indx; | |
4399d500 | 2358 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
3072d30e | 2359 | { |
2360 | BITMAP_WORD r = b_elt->bits[ix] & ~kill_elt->bits[ix]; | |
2361 | ior |= r; | |
2362 | tmp_elt.bits[ix] = r; | |
2363 | } | |
2364 | ||
2365 | if (ior) | |
2366 | { | |
2367 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, | |
2368 | a_elt, &tmp_elt, changed); | |
2369 | new_element = true; | |
2370 | if (a_elt && a_elt->indx == b_elt->indx) | |
2371 | a_elt = a_elt->next; | |
2372 | } | |
2373 | ||
2374 | b_elt = b_elt->next; | |
2375 | kill_elt = kill_elt->next; | |
2376 | } | |
2377 | else | |
2378 | { | |
2379 | changed = bitmap_elt_ior (dst, dst_elt, dst_prev, | |
2380 | a_elt, b_elt, changed); | |
2381 | new_element = true; | |
2382 | ||
2383 | if (a_elt && b_elt && a_elt->indx == b_elt->indx) | |
2384 | { | |
2385 | a_elt = a_elt->next; | |
2386 | b_elt = b_elt->next; | |
2387 | } | |
2388 | else | |
2389 | { | |
2390 | if (a_elt && (!b_elt || a_elt->indx <= b_elt->indx)) | |
2391 | a_elt = a_elt->next; | |
2392 | else if (b_elt && (!a_elt || b_elt->indx <= a_elt->indx)) | |
2393 | b_elt = b_elt->next; | |
2394 | } | |
2395 | } | |
2396 | ||
2397 | if (new_element) | |
2398 | { | |
2399 | dst_prev = *dst_prev_pnext; | |
2400 | dst_prev_pnext = &dst_prev->next; | |
2401 | dst_elt = *dst_prev_pnext; | |
2402 | } | |
2403 | } | |
2404 | ||
2405 | if (dst_elt) | |
2406 | { | |
2407 | changed = true; | |
85ac1c40 | 2408 | /* Ensure that dst->current is valid. */ |
2409 | dst->current = dst->first; | |
3072d30e | 2410 | bitmap_elt_clear_from (dst, dst_elt); |
2411 | } | |
0ea2d350 | 2412 | gcc_checking_assert (!dst->current == !dst->first); |
3072d30e | 2413 | if (dst->current) |
2414 | dst->indx = dst->current->indx; | |
b6e72c17 | 2415 | |
604efc01 | 2416 | return changed; |
2f925a60 | 2417 | } |
114c7df6 | 2418 | |
e35f850e | 2419 | /* A |= (B & ~C). Return true if A changes. */ |
79d6d448 | 2420 | |
2421 | bool | |
e35f850e | 2422 | bitmap_ior_and_compl_into (bitmap a, const_bitmap b, const_bitmap c) |
114c7df6 | 2423 | { |
84ce34d9 | 2424 | bitmap_element *a_elt = a->first; |
2425 | const bitmap_element *b_elt = b->first; | |
2426 | const bitmap_element *c_elt = c->first; | |
2427 | bitmap_element and_elt; | |
2428 | bitmap_element *a_prev = NULL; | |
2429 | bitmap_element **a_prev_pnext = &a->first; | |
2430 | bool changed = false; | |
2431 | unsigned ix; | |
a0c938f0 | 2432 | |
e35f850e | 2433 | gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form); |
2434 | ||
84ce34d9 | 2435 | if (a == b) |
2436 | return false; | |
2437 | if (bitmap_empty_p (c)) | |
2438 | return bitmap_ior_into (a, b); | |
2439 | else if (bitmap_empty_p (a)) | |
2440 | return bitmap_and_compl (a, b, c); | |
114c7df6 | 2441 | |
84ce34d9 | 2442 | and_elt.indx = -1; |
2443 | while (b_elt) | |
2444 | { | |
2445 | /* Advance C. */ | |
2446 | while (c_elt && c_elt->indx < b_elt->indx) | |
2447 | c_elt = c_elt->next; | |
2448 | ||
2449 | const bitmap_element *and_elt_ptr; | |
2450 | if (c_elt && c_elt->indx == b_elt->indx) | |
2451 | { | |
2452 | BITMAP_WORD overall = 0; | |
2453 | and_elt_ptr = &and_elt; | |
2454 | and_elt.indx = b_elt->indx; | |
2455 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) | |
2456 | { | |
2457 | and_elt.bits[ix] = b_elt->bits[ix] & ~c_elt->bits[ix]; | |
2458 | overall |= and_elt.bits[ix]; | |
2459 | } | |
2460 | if (!overall) | |
2461 | { | |
2462 | b_elt = b_elt->next; | |
2463 | continue; | |
2464 | } | |
2465 | } | |
2466 | else | |
2467 | and_elt_ptr = b_elt; | |
2468 | ||
2469 | b_elt = b_elt->next; | |
2470 | ||
2471 | /* Now find a place to insert AND_ELT. */ | |
2472 | do | |
2473 | { | |
2474 | ix = a_elt ? a_elt->indx : and_elt_ptr->indx; | |
2475 | if (ix == and_elt_ptr->indx) | |
2476 | changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, | |
2477 | and_elt_ptr, changed); | |
2478 | else if (ix > and_elt_ptr->indx) | |
2479 | changed = bitmap_elt_copy (a, NULL, a_prev, and_elt_ptr, changed); | |
2480 | ||
2481 | a_prev = *a_prev_pnext; | |
2482 | a_prev_pnext = &a_prev->next; | |
2483 | a_elt = *a_prev_pnext; | |
2484 | ||
2485 | /* If A lagged behind B/C, we advanced it so loop once more. */ | |
2486 | } | |
2487 | while (ix < and_elt_ptr->indx); | |
2488 | } | |
2489 | ||
2490 | gcc_checking_assert (!a->current == !a->first); | |
2491 | if (a->current) | |
2492 | a->indx = a->current->indx; | |
114c7df6 | 2493 | return changed; |
2494 | } | |
3072d30e | 2495 | |
d7f2555b | 2496 | /* A |= (B & C). Return true if A changes. */ |
2497 | ||
2498 | bool | |
2499 | bitmap_ior_and_into (bitmap a, const_bitmap b, const_bitmap c) | |
2500 | { | |
2501 | bitmap_element *a_elt = a->first; | |
2502 | const bitmap_element *b_elt = b->first; | |
2503 | const bitmap_element *c_elt = c->first; | |
2504 | bitmap_element and_elt; | |
2505 | bitmap_element *a_prev = NULL; | |
2506 | bitmap_element **a_prev_pnext = &a->first; | |
2507 | bool changed = false; | |
2508 | unsigned ix; | |
2509 | ||
e35f850e | 2510 | gcc_checking_assert (!a->tree_form && !b->tree_form && !c->tree_form); |
2511 | ||
d7f2555b | 2512 | if (b == c) |
2513 | return bitmap_ior_into (a, b); | |
2514 | if (bitmap_empty_p (b) || bitmap_empty_p (c)) | |
2515 | return false; | |
2516 | ||
2517 | and_elt.indx = -1; | |
2518 | while (b_elt && c_elt) | |
2519 | { | |
2520 | BITMAP_WORD overall; | |
2521 | ||
2522 | /* Find a common item of B and C. */ | |
2523 | while (b_elt->indx != c_elt->indx) | |
2524 | { | |
2525 | if (b_elt->indx < c_elt->indx) | |
2526 | { | |
2527 | b_elt = b_elt->next; | |
2528 | if (!b_elt) | |
2529 | goto done; | |
2530 | } | |
2531 | else | |
2532 | { | |
2533 | c_elt = c_elt->next; | |
2534 | if (!c_elt) | |
2535 | goto done; | |
2536 | } | |
2537 | } | |
2538 | ||
2539 | overall = 0; | |
2540 | and_elt.indx = b_elt->indx; | |
4399d500 | 2541 | for (ix = 0; ix < BITMAP_ELEMENT_WORDS; ix++) |
d7f2555b | 2542 | { |
2543 | and_elt.bits[ix] = b_elt->bits[ix] & c_elt->bits[ix]; | |
2544 | overall |= and_elt.bits[ix]; | |
2545 | } | |
2546 | ||
2547 | b_elt = b_elt->next; | |
2548 | c_elt = c_elt->next; | |
2549 | if (!overall) | |
2550 | continue; | |
2551 | ||
2552 | /* Now find a place to insert AND_ELT. */ | |
2553 | do | |
2554 | { | |
2555 | ix = a_elt ? a_elt->indx : and_elt.indx; | |
2556 | if (ix == and_elt.indx) | |
2557 | changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, &and_elt, changed); | |
2558 | else if (ix > and_elt.indx) | |
2559 | changed = bitmap_elt_copy (a, NULL, a_prev, &and_elt, changed); | |
2560 | ||
2561 | a_prev = *a_prev_pnext; | |
2562 | a_prev_pnext = &a_prev->next; | |
2563 | a_elt = *a_prev_pnext; | |
2564 | ||
2565 | /* If A lagged behind B/C, we advanced it so loop once more. */ | |
2566 | } | |
2567 | while (ix < and_elt.indx); | |
2568 | } | |
2569 | ||
2570 | done: | |
0ea2d350 | 2571 | gcc_checking_assert (!a->current == !a->first); |
d7f2555b | 2572 | if (a->current) |
2573 | a->indx = a->current->indx; | |
2574 | return changed; | |
2575 | } | |
ecd52ea9 | 2576 | |
2577 | /* Compute hash of bitmap (for purposes of hashing). */ | |
e35f850e | 2578 | |
ecd52ea9 | 2579 | hashval_t |
2580 | bitmap_hash (const_bitmap head) | |
2581 | { | |
2582 | const bitmap_element *ptr; | |
2583 | BITMAP_WORD hash = 0; | |
2584 | int ix; | |
2585 | ||
e35f850e | 2586 | gcc_checking_assert (!head->tree_form); |
2587 | ||
ecd52ea9 | 2588 | for (ptr = head->first; ptr; ptr = ptr->next) |
2589 | { | |
2590 | hash ^= ptr->indx; | |
2591 | for (ix = 0; ix != BITMAP_ELEMENT_WORDS; ix++) | |
2592 | hash ^= ptr->bits[ix]; | |
2593 | } | |
2594 | return (hashval_t)hash; | |
2595 | } | |
2596 | ||
2f925a60 | 2597 | \f |
e35f850e | 2598 | /* Function to obtain a vector of bitmap elements in bit order from |
2599 | HEAD in tree view. */ | |
2600 | ||
2601 | static void | |
2602 | bitmap_tree_to_vec (vec<bitmap_element *> &elts, const_bitmap head) | |
2603 | { | |
2604 | gcc_checking_assert (head->tree_form); | |
2605 | auto_vec<bitmap_element *, 32> stack; | |
2606 | bitmap_element *e = head->first; | |
2607 | while (true) | |
2608 | { | |
2609 | while (e != NULL) | |
2610 | { | |
2611 | stack.safe_push (e); | |
2612 | e = e->prev; | |
2613 | } | |
2614 | if (stack.is_empty ()) | |
2615 | break; | |
2616 | ||
2617 | e = stack.pop (); | |
2618 | elts.safe_push (e); | |
2619 | e = e->next; | |
2620 | } | |
2621 | } | |
2622 | ||
2623 | /* Debugging function to print out the contents of a bitmap element. */ | |
2624 | ||
2625 | DEBUG_FUNCTION void | |
2626 | debug_bitmap_elt_file (FILE *file, const bitmap_element *ptr) | |
2627 | { | |
2628 | unsigned int i, j, col = 26; | |
2629 | ||
2630 | fprintf (file, "\t" HOST_PTR_PRINTF " next = " HOST_PTR_PRINTF | |
2631 | " prev = " HOST_PTR_PRINTF " indx = %u\n\t\tbits = {", | |
2632 | (const void*) ptr, (const void*) ptr->next, | |
2633 | (const void*) ptr->prev, ptr->indx); | |
2634 | ||
2635 | for (i = 0; i < BITMAP_ELEMENT_WORDS; i++) | |
2636 | for (j = 0; j < BITMAP_WORD_BITS; j++) | |
2637 | if ((ptr->bits[i] >> j) & 1) | |
2638 | { | |
2639 | if (col > 70) | |
2640 | { | |
2641 | fprintf (file, "\n\t\t\t"); | |
2642 | col = 24; | |
2643 | } | |
2644 | ||
2645 | fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS | |
2646 | + i * BITMAP_WORD_BITS + j)); | |
2647 | col += 4; | |
2648 | } | |
2649 | ||
2650 | fprintf (file, " }\n"); | |
2651 | } | |
2652 | ||
2f925a60 | 2653 | /* Debugging function to print out the contents of a bitmap. */ |
2654 | ||
4b987fac | 2655 | DEBUG_FUNCTION void |
056755a1 | 2656 | debug_bitmap_file (FILE *file, const_bitmap head) |
2f925a60 | 2657 | { |
056755a1 | 2658 | const bitmap_element *ptr; |
2f925a60 | 2659 | |
038ca0d1 | 2660 | fprintf (file, "\nfirst = " HOST_PTR_PRINTF |
2661 | " current = " HOST_PTR_PRINTF " indx = %u\n", | |
6f817829 | 2662 | (void *) head->first, (void *) head->current, head->indx); |
2f925a60 | 2663 | |
e35f850e | 2664 | if (head->tree_form) |
2f925a60 | 2665 | { |
e35f850e | 2666 | auto_vec<bitmap_element *, 32> elts; |
2667 | bitmap_tree_to_vec (elts, head); | |
2668 | for (unsigned i = 0; i < elts.length (); ++i) | |
2669 | debug_bitmap_elt_file (file, elts[i]); | |
2f925a60 | 2670 | } |
e35f850e | 2671 | else |
2672 | for (ptr = head->first; ptr; ptr = ptr->next) | |
2673 | debug_bitmap_elt_file (file, ptr); | |
2f925a60 | 2674 | } |
ca2968e9 | 2675 | |
2f925a60 | 2676 | /* Function to be called from the debugger to print the contents |
2677 | of a bitmap. */ | |
2678 | ||
4b987fac | 2679 | DEBUG_FUNCTION void |
056755a1 | 2680 | debug_bitmap (const_bitmap head) |
2f925a60 | 2681 | { |
d72243e8 | 2682 | debug_bitmap_file (stderr, head); |
2f925a60 | 2683 | } |
ca2968e9 | 2684 | |
64c25516 | 2685 | /* Function to print out the contents of a bitmap. Unlike debug_bitmap_file, |
23ec99a1 | 2686 | it does not print anything but the bits. */ |
2687 | ||
4b987fac | 2688 | DEBUG_FUNCTION void |
c7d89805 | 2689 | bitmap_print (FILE *file, const_bitmap head, const char *prefix, |
2690 | const char *suffix) | |
23ec99a1 | 2691 | { |
ba1d8f67 | 2692 | const char *comma = ""; |
4f917ffe | 2693 | unsigned i; |
23ec99a1 | 2694 | |
2695 | fputs (prefix, file); | |
e35f850e | 2696 | if (head->tree_form) |
2697 | { | |
2698 | auto_vec<bitmap_element *, 32> elts; | |
2699 | bitmap_tree_to_vec (elts, head); | |
2700 | for (i = 0; i < elts.length (); ++i) | |
2701 | for (unsigned ix = 0; ix != BITMAP_ELEMENT_WORDS; ++ix) | |
2702 | { | |
2703 | BITMAP_WORD word = elts[i]->bits[ix]; | |
2704 | for (unsigned bit = 0; bit != BITMAP_WORD_BITS; ++bit) | |
2705 | if (word & ((BITMAP_WORD)1 << bit)) | |
2706 | { | |
2707 | fprintf (file, "%s%d", comma, | |
2708 | (bit + BITMAP_WORD_BITS * ix | |
2709 | + elts[i]->indx * BITMAP_ELEMENT_ALL_BITS)); | |
2710 | comma = ", "; | |
2711 | } | |
2712 | } | |
2713 | } | |
2714 | else | |
0cc4271a | 2715 | { |
e35f850e | 2716 | bitmap_iterator bi; |
2717 | EXECUTE_IF_SET_IN_BITMAP (head, 0, i, bi) | |
2718 | { | |
2719 | fprintf (file, "%s%d", comma, i); | |
2720 | comma = ", "; | |
2721 | } | |
0cc4271a | 2722 | } |
23ec99a1 | 2723 | fputs (suffix, file); |
2724 | } | |
f65ffe0d | 2725 | |
f65ffe0d | 2726 | /* Output per-bitmap memory usage statistics. */ |
2727 | void | |
2728 | dump_bitmap_statistics (void) | |
2729 | { | |
f34a836c | 2730 | if (!GATHER_STATISTICS) |
ecd52ea9 | 2731 | return; |
2732 | ||
a80feb6c | 2733 | bitmap_mem_desc.dump (BITMAP_ORIGIN); |
844ea20e | 2734 | } |
2735 | ||
c7d89805 | 2736 | DEBUG_FUNCTION void |
b3e7c666 | 2737 | debug (const bitmap_head &ref) |
c7d89805 | 2738 | { |
2739 | dump_bitmap (stderr, &ref); | |
2740 | } | |
2741 | ||
2742 | DEBUG_FUNCTION void | |
b3e7c666 | 2743 | debug (const bitmap_head *ptr) |
c7d89805 | 2744 | { |
2745 | if (ptr) | |
2746 | debug (*ptr); | |
2747 | else | |
2748 | fprintf (stderr, "<nil>\n"); | |
2749 | } | |
2750 | ||
be44111e | 2751 | void |
2752 | bitmap_head::dump () | |
2753 | { | |
2754 | debug (this); | |
2755 | } | |
2756 | ||
99b4f3a2 | 2757 | #if CHECKING_P |
2758 | ||
2759 | namespace selftest { | |
2760 | ||
2761 | /* Selftests for bitmaps. */ | |
2762 | ||
2763 | /* Freshly-created bitmaps ought to be empty. */ | |
2764 | ||
2765 | static void | |
2766 | test_gc_alloc () | |
2767 | { | |
2768 | bitmap b = bitmap_gc_alloc (); | |
2769 | ASSERT_TRUE (bitmap_empty_p (b)); | |
2770 | } | |
2771 | ||
2772 | /* Verify bitmap_set_range. */ | |
2773 | ||
2774 | static void | |
2775 | test_set_range () | |
2776 | { | |
2777 | bitmap b = bitmap_gc_alloc (); | |
2778 | ASSERT_TRUE (bitmap_empty_p (b)); | |
2779 | ||
2780 | bitmap_set_range (b, 7, 5); | |
2781 | ASSERT_FALSE (bitmap_empty_p (b)); | |
2782 | ASSERT_EQ (5, bitmap_count_bits (b)); | |
2783 | ||
2784 | /* Verify bitmap_bit_p at the boundaries. */ | |
2785 | ASSERT_FALSE (bitmap_bit_p (b, 6)); | |
2786 | ASSERT_TRUE (bitmap_bit_p (b, 7)); | |
2787 | ASSERT_TRUE (bitmap_bit_p (b, 11)); | |
2788 | ASSERT_FALSE (bitmap_bit_p (b, 12)); | |
2789 | } | |
2790 | ||
2791 | /* Verify splitting a range into two pieces using bitmap_clear_bit. */ | |
2792 | ||
2793 | static void | |
2794 | test_clear_bit_in_middle () | |
2795 | { | |
2796 | bitmap b = bitmap_gc_alloc (); | |
2797 | ||
2798 | /* Set b to [100..200]. */ | |
2799 | bitmap_set_range (b, 100, 100); | |
2800 | ASSERT_EQ (100, bitmap_count_bits (b)); | |
2801 | ||
2802 | /* Clear a bit in the middle. */ | |
2803 | bool changed = bitmap_clear_bit (b, 150); | |
2804 | ASSERT_TRUE (changed); | |
2805 | ASSERT_EQ (99, bitmap_count_bits (b)); | |
2806 | ASSERT_TRUE (bitmap_bit_p (b, 149)); | |
2807 | ASSERT_FALSE (bitmap_bit_p (b, 150)); | |
2808 | ASSERT_TRUE (bitmap_bit_p (b, 151)); | |
2809 | } | |
2810 | ||
2811 | /* Verify bitmap_copy. */ | |
2812 | ||
2813 | static void | |
2814 | test_copying () | |
2815 | { | |
2816 | bitmap src = bitmap_gc_alloc (); | |
2817 | bitmap_set_range (src, 40, 10); | |
2818 | ||
2819 | bitmap dst = bitmap_gc_alloc (); | |
2820 | ASSERT_FALSE (bitmap_equal_p (src, dst)); | |
2821 | bitmap_copy (dst, src); | |
2822 | ASSERT_TRUE (bitmap_equal_p (src, dst)); | |
2823 | ||
2824 | /* Verify that we can make them unequal again... */ | |
2825 | bitmap_set_range (src, 70, 5); | |
2826 | ASSERT_FALSE (bitmap_equal_p (src, dst)); | |
2827 | ||
2828 | /* ...and that changing src after the copy didn't affect | |
2829 | the other: */ | |
2830 | ASSERT_FALSE (bitmap_bit_p (dst, 70)); | |
2831 | } | |
2832 | ||
2833 | /* Verify bitmap_single_bit_set_p. */ | |
2834 | ||
2835 | static void | |
2836 | test_bitmap_single_bit_set_p () | |
2837 | { | |
2838 | bitmap b = bitmap_gc_alloc (); | |
2839 | ||
2840 | ASSERT_FALSE (bitmap_single_bit_set_p (b)); | |
2841 | ||
2842 | bitmap_set_range (b, 42, 1); | |
2843 | ASSERT_TRUE (bitmap_single_bit_set_p (b)); | |
2844 | ASSERT_EQ (42, bitmap_first_set_bit (b)); | |
2845 | ||
2846 | bitmap_set_range (b, 1066, 1); | |
2847 | ASSERT_FALSE (bitmap_single_bit_set_p (b)); | |
2848 | ASSERT_EQ (42, bitmap_first_set_bit (b)); | |
2849 | ||
2850 | bitmap_clear_range (b, 0, 100); | |
2851 | ASSERT_TRUE (bitmap_single_bit_set_p (b)); | |
2852 | ASSERT_EQ (1066, bitmap_first_set_bit (b)); | |
2853 | } | |
2854 | ||
2855 | /* Run all of the selftests within this file. */ | |
2856 | ||
2857 | void | |
2858 | bitmap_c_tests () | |
2859 | { | |
2860 | test_gc_alloc (); | |
2861 | test_set_range (); | |
2862 | test_clear_bit_in_middle (); | |
2863 | test_copying (); | |
2864 | test_bitmap_single_bit_set_p (); | |
2865 | } | |
2866 | ||
2867 | } // namespace selftest | |
2868 | #endif /* CHECKING_P */ | |
c7d89805 | 2869 | |
1f3233d1 | 2870 | #include "gt-bitmap.h" |