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