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