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